← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

  • Committer: Robert Collins
  • Date: 2007-10-07 22:04:49 UTC
  • mto: (2592.3.168 repository)
  • mto: This revision was merged to the branch mainline in revision 2908.
  • Revision ID: robertc@robertcollins.net-20071007220449-stt24xz9eaaj703l
Create a content lookup function for bisection in GraphIndex.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
19
19
from bzrlib import errors
20
20
from bzrlib.index import *
21
21
from bzrlib.tests import TestCaseWithMemoryTransport
 
22
from bzrlib.transport import get_transport
22
23
 
23
24
 
24
25
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
357
358
        for key, value, references in nodes:
358
359
            builder.add_node(key, value, references)
359
360
        stream = builder.finish()
360
 
        trans = self.get_transport()
 
361
        trans = get_transport('trace+' + self.get_url())
361
362
        size = trans.put_file('index', stream)
362
363
        return GraphIndex(trans, 'index', size)
363
364
 
369
370
    def test_open_sets_parsed_map_empty(self):
370
371
        index = self.make_index()
371
372
        self.assertEqual([], index._parsed_byte_map)
 
373
        self.assertEqual([], index._parsed_key_map)
 
374
 
 
375
    def test_first_lookup_key_via_location(self):
 
376
        index = self.make_index()
 
377
        # reset the transport log
 
378
        del index._transport._activity[:]
 
379
        # do a lookup_keys_via_location call for the middle of the file, which
 
380
        # is what bisection uses.
 
381
        result = index.lookup_keys_via_location(
 
382
            [(index._size // 2, ('missing', ))])
 
383
        # this should have asked for a readv request, with adjust_for_latency,
 
384
        # and two regions: the header, and half-way into the file.
 
385
        self.assertEqual([
 
386
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
 
387
            ],
 
388
            index._transport._activity)
 
389
        # and the result should be that the key cannot be present, because this
 
390
        # is a trivial index.
 
391
        self.assertEqual([((index._size // 2, ('missing', )), False)],
 
392
            result)
 
393
        # And the regions of the file that have been parsed - in this case the
 
394
        # entire file - should be in the parsed region map.
 
395
        self.assertEqual([(0, 60)], index._parsed_byte_map)
 
396
        self.assertEqual([(None, None)], index._parsed_key_map)
 
397
 
 
398
    def test_parsing_parses_data_adjacent_to_parsed_regions(self):
 
399
        # we trim data we recieve to remove the first and trailing
 
400
        # partial lines, except when they start at the end/finish at the start
 
401
        # of a region we've alread parsed/ the end of the file. The trivial
 
402
        # test for this is an index with 1 key.
 
403
        index = self.make_index(nodes=[(('name', ), 'data', ())])
 
404
        # reset the transport log
 
405
        del index._transport._activity[:]
 
406
        result = index.lookup_keys_via_location(
 
407
            [(index._size // 2, ('missing', ))])
 
408
        # this should have asked for a readv request, with adjust_for_latency,
 
409
        # and two regions: the header, and half-way into the file.
 
410
        self.assertEqual([
 
411
            ('readv', 'index', [(36, 36), (0, 200)], True, 72),
 
412
            ],
 
413
            index._transport._activity)
 
414
        # and the result should be that the key cannot be present, because this
 
415
        # is a trivial index and we should not have to do more round trips.
 
416
        self.assertEqual([((index._size // 2, ('missing', )), False)],
 
417
            result)
 
418
        # The whole file should be parsed at this point.
 
419
        self.assertEqual([(0, 72)], index._parsed_byte_map)
 
420
        self.assertEqual([(None, ('name',))], index._parsed_key_map)
 
421
 
 
422
    ### - tests:
 
423
    # data with a reference that won't be accessed by the default readv request
 
424
    # change the _nodes dict to a bisectable list, or perhaps an adjacent list.
 
425
    # on result generation,
 
426
 
 
427
    def test_parsing_non_adjacent_data_trims(self):
 
428
        # generate a big enough index that we only read some of it on a typical
 
429
        # bisection lookup.
 
430
        nodes = []
 
431
        def make_key(number):
 
432
            return (str(number) + 'X'*100,)
 
433
        for counter in range(64):
 
434
            nodes.append((make_key(counter), 'Y'*100, ()))
 
435
        index = self.make_index(nodes=nodes)
 
436
        result = index.lookup_keys_via_location(
 
437
            [(index._size // 2, ('40', ))])
 
438
        # and the result should be that the key cannot be present, because key is
 
439
        # in the middle of the observed data from a 4K read - the smallest transport
 
440
        # will do today with this api.
 
441
        self.assertEqual([((index._size // 2, ('40', )), False)],
 
442
            result)
 
443
        # and we should have a parse map that includes the header and the
 
444
        # region that was parsed after trimming.
 
445
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
446
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
447
            index._parsed_key_map)
 
448
 
 
449
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
 
450
        # generate a big enough index that we only read some of it on a typical
 
451
        # bisection lookup.
 
452
        nodes = []
 
453
        def make_key(number):
 
454
            return (str(number) + 'X'*100,)
 
455
        for counter in range(64):
 
456
            nodes.append((make_key(counter), 'Y'*100, ()))
 
457
        index = self.make_index(nodes=nodes)
 
458
        # lookup the keys in the middle of the file
 
459
        result =index.lookup_keys_via_location(
 
460
            [(index._size // 2, ('40', ))])
 
461
        # check the parse map, this determines the test validity
 
462
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
463
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
464
            index._parsed_key_map)
 
465
        # reset the transport log
 
466
        del index._transport._activity[:]
 
467
        # now looking up a key in the portion of the file already parsed should
 
468
        # not create a new transport request, and should return False (cannot
 
469
        # be in the index) - even when the byte location we ask for is outside
 
470
        # the parsed region
 
471
        # 
 
472
        result = index.lookup_keys_via_location(
 
473
            [(4000, ('40', ))])
 
474
        self.assertEqual([((4000, ('40', )), False)],
 
475
            result)
 
476
        self.assertEqual([], index._transport._activity)
 
477
 
 
478
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
 
479
        # generate a big enough index that we only read some of it on a typical
 
480
        # bisection lookup.
 
481
        nodes = []
 
482
        def make_key(number):
 
483
            return (str(number) + 'X'*100,)
 
484
        def make_value(number):
 
485
            return str(number) + 'Y'*100
 
486
        for counter in range(64):
 
487
            nodes.append((make_key(counter), make_value(counter), ()))
 
488
        index = self.make_index(nodes=nodes)
 
489
        # lookup the keys in the middle of the file
 
490
        result =index.lookup_keys_via_location(
 
491
            [(index._size // 2, ('40', ))])
 
492
        # check the parse map, this determines the test validity
 
493
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
494
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
495
            index._parsed_key_map)
 
496
        # reset the transport log
 
497
        del index._transport._activity[:]
 
498
        # now looking up a key in the portion of the file already parsed should
 
499
        # not create a new transport request, and should return False (cannot
 
500
        # be in the index) - even when the byte location we ask for is outside
 
501
        # the parsed region
 
502
        # 
 
503
        result = index.lookup_keys_via_location([(4000, make_key(40))])
 
504
        self.assertEqual(
 
505
            [((4000, make_key(40)), (index, make_key(40), make_value(40)))],
 
506
            result)
 
507
        self.assertEqual([], index._transport._activity)
 
508
 
 
509
    def test_lookup_key_below_probed_area(self):
 
510
        # generate a big enough index that we only read some of it on a typical
 
511
        # bisection lookup.
 
512
        nodes = []
 
513
        def make_key(number):
 
514
            return (str(number) + 'X'*100,)
 
515
        for counter in range(64):
 
516
            nodes.append((make_key(counter), 'Y'*100, ()))
 
517
        index = self.make_index(nodes=nodes)
 
518
        # ask for the key in the middle, but a key that is located in the
 
519
        # unparsed region before the middle.
 
520
        result =index.lookup_keys_via_location(
 
521
            [(index._size // 2, ('30', ))])
 
522
        # check the parse map, this determines the test validity
 
523
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
524
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
525
            index._parsed_key_map)
 
526
        self.assertEqual([((index._size // 2, ('30', )), -1)],
 
527
            result)
 
528
 
 
529
    def test_lookup_key_above_probed_area(self):
 
530
        # generate a big enough index that we only read some of it on a typical
 
531
        # bisection lookup.
 
532
        nodes = []
 
533
        def make_key(number):
 
534
            return (str(number) + 'X'*100,)
 
535
        for counter in range(64):
 
536
            nodes.append((make_key(counter), 'Y'*100, ()))
 
537
        index = self.make_index(nodes=nodes)
 
538
        # ask for the key in the middle, but a key that is located in the
 
539
        # unparsed region after the middle.
 
540
        result =index.lookup_keys_via_location(
 
541
            [(index._size // 2, ('50', ))])
 
542
        # check the parse map, this determines the test validity
 
543
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
544
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
545
            index._parsed_key_map)
 
546
        self.assertEqual([((index._size // 2, ('50', )), +1)],
 
547
            result)
372
548
 
373
549
    def test_iter_all_entries_empty(self):
374
550
        index = self.make_index()