/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

Merge bzr.dev.

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.put_file('index', stream)
362
 
        return GraphIndex(trans, 'index')
 
361
        trans = get_transport('trace+' + self.get_url())
 
362
        size = trans.put_file('index', stream)
 
363
        return GraphIndex(trans, 'index', size)
363
364
 
364
365
    def test_open_bad_index_no_error(self):
365
366
        trans = self.get_transport()
366
367
        trans.put_bytes('name', "not an index\n")
367
 
        index = GraphIndex(trans, 'name')
 
368
        index = GraphIndex(trans, 'name', 13)
 
369
 
 
370
    def test_open_sets_parsed_map_empty(self):
 
371
        index = self.make_index()
 
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
    def test_parsing_non_adjacent_data_trims(self):
 
423
        # generate a big enough index that we only read some of it on a typical
 
424
        # bisection lookup.
 
425
        nodes = []
 
426
        def make_key(number):
 
427
            return (str(number) + 'X'*100,)
 
428
        for counter in range(64):
 
429
            nodes.append((make_key(counter), 'Y'*100, ()))
 
430
        index = self.make_index(nodes=nodes)
 
431
        result = index._lookup_keys_via_location(
 
432
            [(index._size // 2, ('40', ))])
 
433
        # and the result should be that the key cannot be present, because key is
 
434
        # in the middle of the observed data from a 4K read - the smallest transport
 
435
        # will do today with this api.
 
436
        self.assertEqual([((index._size // 2, ('40', )), False)],
 
437
            result)
 
438
        # and we should have a parse map that includes the header and the
 
439
        # region that was parsed after trimming.
 
440
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
441
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
442
            index._parsed_key_map)
 
443
 
 
444
    def test_parsing_data_handles_parsed_contained_regions(self):
 
445
        # the following patten creates a parsed region that is wholly within a
 
446
        # single result from the readv layer:
 
447
        # .... single-read (readv-minimum-size) ...
 
448
        # which then trims the start and end so the parsed size is < readv
 
449
        # miniumum.
 
450
        # then a dual lookup (or a reference lookup for that matter) which
 
451
        # abuts or overlaps the parsed region on both sides will need to 
 
452
        # discard the data in the middle, but parse the end as well.
 
453
        #
 
454
        # we test this by doing a single lookup to seed the data, then 
 
455
        # a lookup for two keys that are present, and adjacent - 
 
456
        # we except both to be found, and the parsed byte map to include the
 
457
        # locations of both keys.
 
458
        nodes = []
 
459
        def make_key(number):
 
460
            return (str(number) + 'X'*100,)
 
461
        def make_value(number):
 
462
            return 'Y'*100
 
463
        for counter in range(128):
 
464
            nodes.append((make_key(counter), make_value(counter), ()))
 
465
        index = self.make_index(nodes=nodes)
 
466
        result = index._lookup_keys_via_location(
 
467
            [(index._size // 2, ('40', ))])
 
468
        # and we should have a parse map that includes the header and the
 
469
        # region that was parsed after trimming.
 
470
        self.assertEqual([(0, 3991), (11622, 15534)], index._parsed_byte_map)
 
471
        self.assertEqual([(None, make_key(116)), (make_key(35), make_key(51))],
 
472
            index._parsed_key_map)
 
473
        # now ask for two keys, right before and after the parsed region
 
474
        result = index._lookup_keys_via_location(
 
475
            [(11450, make_key(34)), (15534, make_key(52))])
 
476
        self.assertEqual([
 
477
            ((11450, make_key(34)), (index, make_key(34), make_value(34))),
 
478
            ((15534, make_key(52)), (index, make_key(52), make_value(52))),
 
479
            ],
 
480
            result)
 
481
        self.assertEqual([(0, 3991), (9975, 17799)], index._parsed_byte_map)
 
482
 
 
483
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
 
484
        # generate a big enough index that we only read some of it on a typical
 
485
        # bisection lookup.
 
486
        nodes = []
 
487
        def make_key(number):
 
488
            return (str(number) + 'X'*100,)
 
489
        for counter in range(64):
 
490
            nodes.append((make_key(counter), 'Y'*100, ()))
 
491
        index = self.make_index(nodes=nodes)
 
492
        # lookup the keys in the middle of the file
 
493
        result =index._lookup_keys_via_location(
 
494
            [(index._size // 2, ('40', ))])
 
495
        # check the parse map, this determines the test validity
 
496
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
497
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
498
            index._parsed_key_map)
 
499
        # reset the transport log
 
500
        del index._transport._activity[:]
 
501
        # now looking up a key in the portion of the file already parsed should
 
502
        # not create a new transport request, and should return False (cannot
 
503
        # be in the index) - even when the byte location we ask for is outside
 
504
        # the parsed region
 
505
        # 
 
506
        result = index._lookup_keys_via_location(
 
507
            [(4000, ('40', ))])
 
508
        self.assertEqual([((4000, ('40', )), False)],
 
509
            result)
 
510
        self.assertEqual([], index._transport._activity)
 
511
 
 
512
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
 
513
        # generate a big enough index that we only read some of it on a typical
 
514
        # bisection lookup.
 
515
        nodes = []
 
516
        def make_key(number):
 
517
            return (str(number) + 'X'*100,)
 
518
        def make_value(number):
 
519
            return str(number) + 'Y'*100
 
520
        for counter in range(64):
 
521
            nodes.append((make_key(counter), make_value(counter), ()))
 
522
        index = self.make_index(nodes=nodes)
 
523
        # lookup the keys in the middle of the file
 
524
        result =index._lookup_keys_via_location(
 
525
            [(index._size // 2, ('40', ))])
 
526
        # check the parse map, this determines the test validity
 
527
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
528
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
529
            index._parsed_key_map)
 
530
        # reset the transport log
 
531
        del index._transport._activity[:]
 
532
        # now looking up a key in the portion of the file already parsed should
 
533
        # not create a new transport request, and should return False (cannot
 
534
        # be in the index) - even when the byte location we ask for is outside
 
535
        # the parsed region
 
536
        # 
 
537
        result = index._lookup_keys_via_location([(4000, make_key(40))])
 
538
        self.assertEqual(
 
539
            [((4000, make_key(40)), (index, make_key(40), make_value(40)))],
 
540
            result)
 
541
        self.assertEqual([], index._transport._activity)
 
542
 
 
543
    def test_lookup_key_below_probed_area(self):
 
544
        # generate a big enough index that we only read some of it on a typical
 
545
        # bisection lookup.
 
546
        nodes = []
 
547
        def make_key(number):
 
548
            return (str(number) + 'X'*100,)
 
549
        for counter in range(64):
 
550
            nodes.append((make_key(counter), 'Y'*100, ()))
 
551
        index = self.make_index(nodes=nodes)
 
552
        # ask for the key in the middle, but a key that is located in the
 
553
        # unparsed region before the middle.
 
554
        result =index._lookup_keys_via_location(
 
555
            [(index._size // 2, ('30', ))])
 
556
        # check the parse map, this determines the test validity
 
557
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
558
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
559
            index._parsed_key_map)
 
560
        self.assertEqual([((index._size // 2, ('30', )), -1)],
 
561
            result)
 
562
 
 
563
    def test_lookup_key_above_probed_area(self):
 
564
        # generate a big enough index that we only read some of it on a typical
 
565
        # bisection lookup.
 
566
        nodes = []
 
567
        def make_key(number):
 
568
            return (str(number) + 'X'*100,)
 
569
        for counter in range(64):
 
570
            nodes.append((make_key(counter), 'Y'*100, ()))
 
571
        index = self.make_index(nodes=nodes)
 
572
        # ask for the key in the middle, but a key that is located in the
 
573
        # unparsed region after the middle.
 
574
        result =index._lookup_keys_via_location(
 
575
            [(index._size // 2, ('50', ))])
 
576
        # check the parse map, this determines the test validity
 
577
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
578
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
579
            index._parsed_key_map)
 
580
        self.assertEqual([((index._size // 2, ('50', )), +1)],
 
581
            result)
 
582
 
 
583
    def test_lookup_key_resolves_references(self):
 
584
        # generate a big enough index that we only read some of it on a typical
 
585
        # bisection lookup.
 
586
        nodes = []
 
587
        def make_key(number):
 
588
            return (str(number) + 'X'*100,)
 
589
        def make_value(number):
 
590
            return str(number) + 'Y'*100
 
591
        for counter in range(64):
 
592
            nodes.append((make_key(counter), make_value(counter),
 
593
                ((make_key(counter + 20),),)  ))
 
594
        index = self.make_index(ref_lists=1, nodes=nodes)
 
595
        # lookup a key in the middle that does not exist, so that when we can
 
596
        # check that the referred-to-keys are not accessed automatically.
 
597
        result =index._lookup_keys_via_location(
 
598
            [(index._size // 2, ('40', ))])
 
599
        # check the parse map - only the start and middle should have been
 
600
        # parsed.
 
601
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
 
602
        self.assertEqual([(None, make_key(25)), (make_key(37), make_key(52))],
 
603
            index._parsed_key_map)
 
604
        # and check the transport activity likewise.
 
605
        self.assertEqual(
 
606
            [('readv', 'index', [(7906, 800), (0, 200)], True, 15813)],
 
607
            index._transport._activity)
 
608
        # reset the transport log for testing the reference lookup
 
609
        del index._transport._activity[:]
 
610
        # now looking up a key in the portion of the file already parsed should
 
611
        # only perform IO to resolve its key references.
 
612
        result = index._lookup_keys_via_location([(4000, make_key(40))])
 
613
        self.assertEqual(
 
614
            [((4000, make_key(40)),
 
615
              (index, make_key(40), make_value(40), ((make_key(60),),)))],
 
616
            result)
 
617
        self.assertEqual([('readv', 'index', [(11976, 800)], True, 15813)],
 
618
            index._transport._activity)
368
619
 
369
620
    def test_iter_all_entries_empty(self):
370
621
        index = self.make_index()
389
640
            (index, ('ref', ), 'refdata', ((), ))]),
390
641
            set(index.iter_all_entries()))
391
642
 
 
643
    def test_iter_entries_references_resolved(self):
 
644
        index = self.make_index(1, nodes=[
 
645
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
 
646
            (('ref', ), 'refdata', ([], ))])
 
647
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
 
648
            (index, ('ref', ), 'refdata', ((), ))]),
 
649
            set(index.iter_entries([('name',), ('ref',)])))
 
650
 
 
651
    def test_iter_entries_references_2_refs_resolved(self):
 
652
        index = self.make_index(2, nodes=[
 
653
            (('name', ), 'data', ([('ref', )], [('ref', )])),
 
654
            (('ref', ), 'refdata', ([], []))])
 
655
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
 
656
            (index, ('ref', ), 'refdata', ((), ()))]),
 
657
            set(index.iter_entries([('name',), ('ref',)])))
 
658
 
392
659
    def test_iteration_absent_skipped(self):
393
660
        index = self.make_index(1, nodes=[
394
661
            (('name', ), 'data', ([('ref', )], ))])
423
690
        index = self.make_index()
424
691
        self.assertEqual([], list(index.iter_entries([('a', )])))
425
692
 
 
693
    def test_iter_missing_entry_empty_no_size(self):
 
694
        index = self.make_index()
 
695
        index = GraphIndex(index._transport, 'index', None)
 
696
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
697
 
426
698
    def test_iter_key_prefix_1_element_key_None(self):
427
699
        index = self.make_index()
428
700
        self.assertRaises(errors.BadIndexKey, list,
494
766
    def test_validate_bad_index_errors(self):
495
767
        trans = self.get_transport()
496
768
        trans.put_bytes('name', "not an index\n")
497
 
        index = GraphIndex(trans, 'name')
 
769
        index = GraphIndex(trans, 'name', 13)
498
770
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
499
771
 
500
772
    def test_validate_bad_node_refs(self):
539
811
            builder.add_node(key, value, references)
540
812
        stream = builder.finish()
541
813
        trans = self.get_transport()
542
 
        trans.put_file(name, stream)
543
 
        return GraphIndex(trans, name)
 
814
        size = trans.put_file(name, stream)
 
815
        return GraphIndex(trans, name, size)
544
816
 
545
817
    def test_open_missing_index_no_error(self):
546
818
        trans = self.get_transport()
547
 
        index1 = GraphIndex(trans, 'missing')
 
819
        index1 = GraphIndex(trans, 'missing', 100)
548
820
        index = CombinedGraphIndex([index1])
549
821
 
550
822
    def test_add_index(self):
677
949
    def test_validate_bad_child_index_errors(self):
678
950
        trans = self.get_transport()
679
951
        trans.put_bytes('name', "not an index\n")
680
 
        index1 = GraphIndex(trans, 'name')
 
952
        index1 = GraphIndex(trans, 'name', 13)
681
953
        index = CombinedGraphIndex([index1])
682
954
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
683
955