← 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: John Arbash Meinel
  • Date: 2009-08-25 18:45:40 UTC
  • mto: (4634.6.15 2.0)
  • mto: This revision was merged to the branch mainline in revision 4667.
  • Revision ID: john@arbash-meinel.com-20090825184540-6dn3xjq62xhgj2gq
Add support for skipping ghost nodes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""Tests for indices."""
18
18
 
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):
349
350
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
350
351
        builder.add_node(('reference', 'tokey'), 'data', ([],))
351
352
 
 
353
    def test_set_optimize(self):
 
354
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
 
355
        builder.set_optimize(for_size=True)
 
356
        self.assertTrue(builder._optimize_for_size)
 
357
        builder.set_optimize(for_size=False)
 
358
        self.assertFalse(builder._optimize_for_size)
 
359
 
352
360
 
353
361
class TestGraphIndex(TestCaseWithMemoryTransport):
354
362
 
 
363
    def make_key(self, number):
 
364
        return (str(number) + 'X'*100,)
 
365
 
 
366
    def make_value(self, number):
 
367
            return str(number) + 'Y'*100
 
368
 
 
369
    def make_nodes(self, count=64):
 
370
        # generate a big enough index that we only read some of it on a typical
 
371
        # bisection lookup.
 
372
        nodes = []
 
373
        for counter in range(count):
 
374
            nodes.append((self.make_key(counter), self.make_value(counter), ()))
 
375
        return nodes
 
376
 
355
377
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
356
378
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
357
379
        for key, value, references in nodes:
358
380
            builder.add_node(key, value, references)
359
381
        stream = builder.finish()
360
 
        trans = self.get_transport()
361
 
        trans.put_file('index', stream)
362
 
        return GraphIndex(trans, 'index')
 
382
        trans = get_transport('trace+' + self.get_url())
 
383
        size = trans.put_file('index', stream)
 
384
        return GraphIndex(trans, 'index', size)
363
385
 
364
386
    def test_open_bad_index_no_error(self):
365
387
        trans = self.get_transport()
366
388
        trans.put_bytes('name', "not an index\n")
367
 
        index = GraphIndex(trans, 'name')
 
389
        index = GraphIndex(trans, 'name', 13)
 
390
 
 
391
    def test_open_sets_parsed_map_empty(self):
 
392
        index = self.make_index()
 
393
        self.assertEqual([], index._parsed_byte_map)
 
394
        self.assertEqual([], index._parsed_key_map)
 
395
 
 
396
    def test_key_count_buffers(self):
 
397
        index = self.make_index(nodes=self.make_nodes(2))
 
398
        # reset the transport log
 
399
        del index._transport._activity[:]
 
400
        self.assertEqual(2, index.key_count())
 
401
        # We should have requested reading the header bytes
 
402
        self.assertEqual([
 
403
            ('readv', 'index', [(0, 200)], True, index._size),
 
404
            ],
 
405
            index._transport._activity)
 
406
        # And that should have been enough to trigger reading the whole index
 
407
        # with buffering
 
408
        self.assertIsNot(None, index._nodes)
 
409
 
 
410
    def test_lookup_key_via_location_buffers(self):
 
411
        index = self.make_index()
 
412
        # reset the transport log
 
413
        del index._transport._activity[:]
 
414
        # do a _lookup_keys_via_location call for the middle of the file, which
 
415
        # is what bisection uses.
 
416
        result = index._lookup_keys_via_location(
 
417
            [(index._size // 2, ('missing', ))])
 
418
        # this should have asked for a readv request, with adjust_for_latency,
 
419
        # and two regions: the header, and half-way into the file.
 
420
        self.assertEqual([
 
421
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
 
422
            ],
 
423
            index._transport._activity)
 
424
        # and the result should be that the key cannot be present, because this
 
425
        # is a trivial index.
 
426
        self.assertEqual([((index._size // 2, ('missing', )), False)],
 
427
            result)
 
428
        # And this should have caused the file to be fully buffered
 
429
        self.assertIsNot(None, index._nodes)
 
430
        self.assertEqual([], index._parsed_byte_map)
 
431
 
 
432
    def test_first_lookup_key_via_location(self):
 
433
        # We need enough data so that the _HEADER_READV doesn't consume the
 
434
        # whole file. We always read 800 bytes for every key, and the local
 
435
        # transport natural expansion is 4096 bytes. So we have to have >8192
 
436
        # bytes or we will trigger "buffer_all".
 
437
        # We also want the 'missing' key to fall within the range that *did*
 
438
        # read
 
439
        nodes = []
 
440
        index = self.make_index(nodes=self.make_nodes(64))
 
441
        # reset the transport log
 
442
        del index._transport._activity[:]
 
443
        # do a _lookup_keys_via_location call for the middle of the file, which
 
444
        # is what bisection uses.
 
445
        start_lookup = index._size // 2
 
446
        result = index._lookup_keys_via_location(
 
447
            [(start_lookup, ('40missing', ))])
 
448
        # this should have asked for a readv request, with adjust_for_latency,
 
449
        # and two regions: the header, and half-way into the file.
 
450
        self.assertEqual([
 
451
            ('readv', 'index',
 
452
             [(start_lookup, 800), (0, 200)], True, index._size),
 
453
            ],
 
454
            index._transport._activity)
 
455
        # and the result should be that the key cannot be present, because this
 
456
        # is a trivial index.
 
457
        self.assertEqual([((start_lookup, ('40missing', )), False)],
 
458
            result)
 
459
        # And this should not have caused the file to be fully buffered
 
460
        self.assertIs(None, index._nodes)
 
461
        # And the regions of the file that have been parsed should be in the
 
462
        # parsed_byte_map and the parsed_key_map
 
463
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
464
        self.assertEqual([(None, self.make_key(26)),
 
465
                          (self.make_key(31), self.make_key(48))],
 
466
                         index._parsed_key_map)
 
467
 
 
468
    def test_parsing_non_adjacent_data_trims(self):
 
469
        index = self.make_index(nodes=self.make_nodes(64))
 
470
        result = index._lookup_keys_via_location(
 
471
            [(index._size // 2, ('40', ))])
 
472
        # and the result should be that the key cannot be present, because key is
 
473
        # in the middle of the observed data from a 4K read - the smallest transport
 
474
        # will do today with this api.
 
475
        self.assertEqual([((index._size // 2, ('40', )), False)],
 
476
            result)
 
477
        # and we should have a parse map that includes the header and the
 
478
        # region that was parsed after trimming.
 
479
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
480
        self.assertEqual([(None, self.make_key(26)),
 
481
                          (self.make_key(31), self.make_key(48))],
 
482
            index._parsed_key_map)
 
483
 
 
484
    def test_parsing_data_handles_parsed_contained_regions(self):
 
485
        # the following patten creates a parsed region that is wholly within a
 
486
        # single result from the readv layer:
 
487
        # .... single-read (readv-minimum-size) ...
 
488
        # which then trims the start and end so the parsed size is < readv
 
489
        # miniumum.
 
490
        # then a dual lookup (or a reference lookup for that matter) which
 
491
        # abuts or overlaps the parsed region on both sides will need to
 
492
        # discard the data in the middle, but parse the end as well.
 
493
        #
 
494
        # we test this by doing a single lookup to seed the data, then
 
495
        # a lookup for two keys that are present, and adjacent -
 
496
        # we except both to be found, and the parsed byte map to include the
 
497
        # locations of both keys.
 
498
        index = self.make_index(nodes=self.make_nodes(128))
 
499
        result = index._lookup_keys_via_location(
 
500
            [(index._size // 2, ('40', ))])
 
501
        # and we should have a parse map that includes the header and the
 
502
        # region that was parsed after trimming.
 
503
        self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
 
504
        self.assertEqual([(None, self.make_key(116)),
 
505
                          (self.make_key(35), self.make_key(51))],
 
506
            index._parsed_key_map)
 
507
        # now ask for two keys, right before and after the parsed region
 
508
        result = index._lookup_keys_via_location(
 
509
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
 
510
        self.assertEqual([
 
511
            ((11450, self.make_key(34)),
 
512
             (index, self.make_key(34), self.make_value(34))),
 
513
            ((15707, self.make_key(52)),
 
514
             (index, self.make_key(52), self.make_value(52))),
 
515
            ],
 
516
            result)
 
517
        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
 
518
 
 
519
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
 
520
        # generate a big enough index that we only read some of it on a typical
 
521
        # bisection lookup.
 
522
        index = self.make_index(nodes=self.make_nodes(64))
 
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, self.make_key(26)),
 
529
                          (self.make_key(31), self.make_key(48))],
 
530
            index._parsed_key_map)
 
531
        # reset the transport log
 
532
        del index._transport._activity[:]
 
533
        # now looking up a key in the portion of the file already parsed should
 
534
        # not create a new transport request, and should return False (cannot
 
535
        # be in the index) - even when the byte location we ask for is outside
 
536
        # the parsed region
 
537
        result = index._lookup_keys_via_location(
 
538
            [(4000, ('40', ))])
 
539
        self.assertEqual([((4000, ('40', )), False)],
 
540
            result)
 
541
        self.assertEqual([], index._transport._activity)
 
542
 
 
543
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
 
544
        # generate a big enough index that we only read some of it on a typical
 
545
        # bisection lookup.
 
546
        index = self.make_index(nodes=self.make_nodes(64))
 
547
        # lookup the keys in the middle of the file
 
548
        result =index._lookup_keys_via_location(
 
549
            [(index._size // 2, ('40', ))])
 
550
        # check the parse map, this determines the test validity
 
551
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
552
        self.assertEqual([(None, self.make_key(26)),
 
553
                          (self.make_key(31), self.make_key(48))],
 
554
            index._parsed_key_map)
 
555
        # reset the transport log
 
556
        del index._transport._activity[:]
 
557
        # now looking up a key in the portion of the file already parsed should
 
558
        # not create a new transport request, and should return False (cannot
 
559
        # be in the index) - even when the byte location we ask for is outside
 
560
        # the parsed region
 
561
        #
 
562
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
 
563
        self.assertEqual(
 
564
            [((4000, self.make_key(40)),
 
565
              (index, self.make_key(40), self.make_value(40)))],
 
566
            result)
 
567
        self.assertEqual([], index._transport._activity)
 
568
 
 
569
    def test_lookup_key_below_probed_area(self):
 
570
        # generate a big enough index that we only read some of it on a typical
 
571
        # bisection lookup.
 
572
        index = self.make_index(nodes=self.make_nodes(64))
 
573
        # ask for the key in the middle, but a key that is located in the
 
574
        # unparsed region before the middle.
 
575
        result =index._lookup_keys_via_location(
 
576
            [(index._size // 2, ('30', ))])
 
577
        # check the parse map, this determines the test validity
 
578
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
579
        self.assertEqual([(None, self.make_key(26)),
 
580
                          (self.make_key(31), self.make_key(48))],
 
581
            index._parsed_key_map)
 
582
        self.assertEqual([((index._size // 2, ('30', )), -1)],
 
583
            result)
 
584
 
 
585
    def test_lookup_key_above_probed_area(self):
 
586
        # generate a big enough index that we only read some of it on a typical
 
587
        # bisection lookup.
 
588
        index = self.make_index(nodes=self.make_nodes(64))
 
589
        # ask for the key in the middle, but a key that is located in the
 
590
        # unparsed region after the middle.
 
591
        result =index._lookup_keys_via_location(
 
592
            [(index._size // 2, ('50', ))])
 
593
        # check the parse map, this determines the test validity
 
594
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
595
        self.assertEqual([(None, self.make_key(26)),
 
596
                          (self.make_key(31), self.make_key(48))],
 
597
            index._parsed_key_map)
 
598
        self.assertEqual([((index._size // 2, ('50', )), +1)],
 
599
            result)
 
600
 
 
601
    def test_lookup_key_resolves_references(self):
 
602
        # generate a big enough index that we only read some of it on a typical
 
603
        # bisection lookup.
 
604
        nodes = []
 
605
        for counter in range(99):
 
606
            nodes.append((self.make_key(counter), self.make_value(counter),
 
607
                ((self.make_key(counter + 20),),)  ))
 
608
        index = self.make_index(ref_lists=1, nodes=nodes)
 
609
        # lookup a key in the middle that does not exist, so that when we can
 
610
        # check that the referred-to-keys are not accessed automatically.
 
611
        index_size = index._size
 
612
        index_center = index_size // 2
 
613
        result = index._lookup_keys_via_location(
 
614
            [(index_center, ('40', ))])
 
615
        # check the parse map - only the start and middle should have been
 
616
        # parsed.
 
617
        self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
 
618
        self.assertEqual([(None, self.make_key(17)),
 
619
                          (self.make_key(44), self.make_key(5))],
 
620
            index._parsed_key_map)
 
621
        # and check the transport activity likewise.
 
622
        self.assertEqual(
 
623
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
 
624
                                  index_size)],
 
625
            index._transport._activity)
 
626
        # reset the transport log for testing the reference lookup
 
627
        del index._transport._activity[:]
 
628
        # now looking up a key in the portion of the file already parsed should
 
629
        # only perform IO to resolve its key references.
 
630
        result = index._lookup_keys_via_location([(11000, self.make_key(45))])
 
631
        self.assertEqual(
 
632
            [((11000, self.make_key(45)),
 
633
              (index, self.make_key(45), self.make_value(45),
 
634
               ((self.make_key(65),),)))],
 
635
            result)
 
636
        self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
 
637
            index._transport._activity)
 
638
 
 
639
    def test_lookup_key_can_buffer_all(self):
 
640
        nodes = []
 
641
        for counter in range(64):
 
642
            nodes.append((self.make_key(counter), self.make_value(counter),
 
643
                ((self.make_key(counter + 20),),)  ))
 
644
        index = self.make_index(ref_lists=1, nodes=nodes)
 
645
        # lookup a key in the middle that does not exist, so that when we can
 
646
        # check that the referred-to-keys are not accessed automatically.
 
647
        index_size = index._size
 
648
        index_center = index_size // 2
 
649
        result = index._lookup_keys_via_location([(index_center, ('40', ))])
 
650
        # check the parse map - only the start and middle should have been
 
651
        # parsed.
 
652
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
 
653
        self.assertEqual([(None, self.make_key(25)),
 
654
                          (self.make_key(37), self.make_key(52))],
 
655
            index._parsed_key_map)
 
656
        # and check the transport activity likewise.
 
657
        self.assertEqual(
 
658
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
 
659
                                  index_size)],
 
660
            index._transport._activity)
 
661
        # reset the transport log for testing the reference lookup
 
662
        del index._transport._activity[:]
 
663
        # now looking up a key in the portion of the file already parsed should
 
664
        # only perform IO to resolve its key references.
 
665
        result = index._lookup_keys_via_location([(7000, self.make_key(40))])
 
666
        self.assertEqual(
 
667
            [((7000, self.make_key(40)),
 
668
              (index, self.make_key(40), self.make_value(40),
 
669
               ((self.make_key(60),),)))],
 
670
            result)
 
671
        # Resolving the references would have required more data read, and we
 
672
        # are already above the 50% threshold, so it triggered a _buffer_all
 
673
        self.assertEqual([('get', 'index')], index._transport._activity)
368
674
 
369
675
    def test_iter_all_entries_empty(self):
370
676
        index = self.make_index()
389
695
            (index, ('ref', ), 'refdata', ((), ))]),
390
696
            set(index.iter_all_entries()))
391
697
 
 
698
    def test_iter_entries_buffers_once(self):
 
699
        index = self.make_index(nodes=self.make_nodes(2))
 
700
        # reset the transport log
 
701
        del index._transport._activity[:]
 
702
        self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
 
703
                         set(index.iter_entries([self.make_key(1)])))
 
704
        # We should have requested reading the header bytes
 
705
        # But not needed any more than that because it would have triggered a
 
706
        # buffer all
 
707
        self.assertEqual([
 
708
            ('readv', 'index', [(0, 200)], True, index._size),
 
709
            ],
 
710
            index._transport._activity)
 
711
        # And that should have been enough to trigger reading the whole index
 
712
        # with buffering
 
713
        self.assertIsNot(None, index._nodes)
 
714
 
 
715
    def test_iter_entries_buffers_by_bytes_read(self):
 
716
        index = self.make_index(nodes=self.make_nodes(64))
 
717
        list(index.iter_entries([self.make_key(10)]))
 
718
        # The first time through isn't enough to trigger a buffer all
 
719
        self.assertIs(None, index._nodes)
 
720
        self.assertEqual(4096, index._bytes_read)
 
721
        # Grabbing a key in that same page won't trigger a buffer all, as we
 
722
        # still haven't read 50% of the file
 
723
        list(index.iter_entries([self.make_key(11)]))
 
724
        self.assertIs(None, index._nodes)
 
725
        self.assertEqual(4096, index._bytes_read)
 
726
        # We haven't read more data, so reading outside the range won't trigger
 
727
        # a buffer all right away
 
728
        list(index.iter_entries([self.make_key(40)]))
 
729
        self.assertIs(None, index._nodes)
 
730
        self.assertEqual(8192, index._bytes_read)
 
731
        # On the next pass, we will not trigger buffer all if the key is
 
732
        # available without reading more
 
733
        list(index.iter_entries([self.make_key(32)]))
 
734
        self.assertIs(None, index._nodes)
 
735
        # But if we *would* need to read more to resolve it, then we will
 
736
        # buffer all.
 
737
        list(index.iter_entries([self.make_key(60)]))
 
738
        self.assertIsNot(None, index._nodes)
 
739
 
 
740
    def test_iter_entries_references_resolved(self):
 
741
        index = self.make_index(1, nodes=[
 
742
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
 
743
            (('ref', ), 'refdata', ([], ))])
 
744
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
 
745
            (index, ('ref', ), 'refdata', ((), ))]),
 
746
            set(index.iter_entries([('name',), ('ref',)])))
 
747
 
 
748
    def test_iter_entries_references_2_refs_resolved(self):
 
749
        index = self.make_index(2, nodes=[
 
750
            (('name', ), 'data', ([('ref', )], [('ref', )])),
 
751
            (('ref', ), 'refdata', ([], []))])
 
752
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
 
753
            (index, ('ref', ), 'refdata', ((), ()))]),
 
754
            set(index.iter_entries([('name',), ('ref',)])))
 
755
 
392
756
    def test_iteration_absent_skipped(self):
393
757
        index = self.make_index(1, nodes=[
394
758
            (('name', ), 'data', ([('ref', )], ))])
423
787
        index = self.make_index()
424
788
        self.assertEqual([], list(index.iter_entries([('a', )])))
425
789
 
 
790
    def test_iter_missing_entry_empty_no_size(self):
 
791
        index = self.make_index()
 
792
        index = GraphIndex(index._transport, 'index', None)
 
793
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
794
 
426
795
    def test_iter_key_prefix_1_element_key_None(self):
427
796
        index = self.make_index()
428
797
        self.assertRaises(errors.BadIndexKey, list,
491
860
            (('name', ), '', ()), (('foo', ), '', ())])
492
861
        self.assertEqual(2, index.key_count())
493
862
 
 
863
    def test_read_and_parse_tracks_real_read_value(self):
 
864
        index = self.make_index(nodes=self.make_nodes(10))
 
865
        del index._transport._activity[:]
 
866
        index._read_and_parse([(0, 200)])
 
867
        self.assertEqual([
 
868
            ('readv', 'index', [(0, 200)], True, index._size),
 
869
            ],
 
870
            index._transport._activity)
 
871
        # The readv expansion code will expand the initial request to 4096
 
872
        # bytes, which is more than enough to read the entire index, and we
 
873
        # will track the fact that we read that many bytes.
 
874
        self.assertEqual(index._size, index._bytes_read)
 
875
 
 
876
    def test_read_and_parse_triggers_buffer_all(self):
 
877
        index = self.make_index(key_elements=2, nodes=[
 
878
            (('name', 'fin1'), 'data', ()),
 
879
            (('name', 'fin2'), 'beta', ()),
 
880
            (('ref', 'erence'), 'refdata', ())])
 
881
        self.assertTrue(index._size > 0)
 
882
        self.assertIs(None, index._nodes)
 
883
        index._read_and_parse([(0, index._size)])
 
884
        self.assertIsNot(None, index._nodes)
 
885
 
494
886
    def test_validate_bad_index_errors(self):
495
887
        trans = self.get_transport()
496
888
        trans.put_bytes('name', "not an index\n")
497
 
        index = GraphIndex(trans, 'name')
 
889
        index = GraphIndex(trans, 'name', 13)
498
890
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
499
891
 
500
892
    def test_validate_bad_node_refs(self):
530
922
        index = self.make_index(nodes=[(('key', ), 'value', ())])
531
923
        index.validate()
532
924
 
 
925
    # XXX: external_references tests are duplicated in test_btree_index.  We
 
926
    # probably should have per_graph_index tests...
 
927
    def test_external_references_no_refs(self):
 
928
        index = self.make_index(ref_lists=0, nodes=[])
 
929
        self.assertRaises(ValueError, index.external_references, 0)
 
930
 
 
931
    def test_external_references_no_results(self):
 
932
        index = self.make_index(ref_lists=1, nodes=[
 
933
            (('key',), 'value', ([],))])
 
934
        self.assertEqual(set(), index.external_references(0))
 
935
 
 
936
    def test_external_references_missing_ref(self):
 
937
        missing_key = ('missing',)
 
938
        index = self.make_index(ref_lists=1, nodes=[
 
939
            (('key',), 'value', ([missing_key],))])
 
940
        self.assertEqual(set([missing_key]), index.external_references(0))
 
941
 
 
942
    def test_external_references_multiple_ref_lists(self):
 
943
        missing_key = ('missing',)
 
944
        index = self.make_index(ref_lists=2, nodes=[
 
945
            (('key',), 'value', ([], [missing_key]))])
 
946
        self.assertEqual(set([]), index.external_references(0))
 
947
        self.assertEqual(set([missing_key]), index.external_references(1))
 
948
 
 
949
    def test_external_references_two_records(self):
 
950
        index = self.make_index(ref_lists=1, nodes=[
 
951
            (('key-1',), 'value', ([('key-2',)],)),
 
952
            (('key-2',), 'value', ([],)),
 
953
            ])
 
954
        self.assertEqual(set([]), index.external_references(0))
 
955
 
 
956
    def test__find_ancestors(self):
 
957
        key1 = ('key-1',)
 
958
        key2 = ('key-2',)
 
959
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
960
            (key1, 'value', ([key2],)),
 
961
            (key2, 'value', ([],)),
 
962
            ])
 
963
        parent_map = {}
 
964
        missing_keys = set()
 
965
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
966
        self.assertEqual({key1: (key2,)}, parent_map)
 
967
        self.assertEqual(set(), missing_keys)
 
968
        self.assertEqual(set([key2]), search_keys)
 
969
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
970
                                            missing_keys)
 
971
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
972
        self.assertEqual(set(), missing_keys)
 
973
        self.assertEqual(set(), search_keys)
 
974
 
 
975
    def test__find_ancestors_w_missing(self):
 
976
        key1 = ('key-1',)
 
977
        key2 = ('key-2',)
 
978
        key3 = ('key-3',)
 
979
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
980
            (key1, 'value', ([key2],)),
 
981
            (key2, 'value', ([],)),
 
982
            ])
 
983
        parent_map = {}
 
984
        missing_keys = set()
 
985
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
986
                                            missing_keys)
 
987
        self.assertEqual({key2: ()}, parent_map)
 
988
        self.assertEqual(set([key3]), missing_keys)
 
989
        self.assertEqual(set(), search_keys)
 
990
 
 
991
    def test__find_ancestors_dont_search_known(self):
 
992
        key1 = ('key-1',)
 
993
        key2 = ('key-2',)
 
994
        key3 = ('key-3',)
 
995
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
996
            (key1, 'value', ([key2],)),
 
997
            (key2, 'value', ([key3],)),
 
998
            (key3, 'value', ([],)),
 
999
            ])
 
1000
        # We already know about key2, so we won't try to search for key3
 
1001
        parent_map = {key2: (key3,)}
 
1002
        missing_keys = set()
 
1003
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1004
                                            missing_keys)
 
1005
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1006
        self.assertEqual(set(), missing_keys)
 
1007
        self.assertEqual(set(), search_keys)
 
1008
 
533
1009
 
534
1010
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
535
1011
 
539
1015
            builder.add_node(key, value, references)
540
1016
        stream = builder.finish()
541
1017
        trans = self.get_transport()
542
 
        trans.put_file(name, stream)
543
 
        return GraphIndex(trans, name)
 
1018
        size = trans.put_file(name, stream)
 
1019
        return GraphIndex(trans, name, size)
 
1020
 
 
1021
    def make_combined_index_with_missing(self, missing=['1', '2']):
 
1022
        """Create a CombinedGraphIndex which will have missing indexes.
 
1023
 
 
1024
        This creates a CGI which thinks it has 2 indexes, however they have
 
1025
        been deleted. If CGI._reload_func() is called, then it will repopulate
 
1026
        with a new index.
 
1027
 
 
1028
        :param missing: The underlying indexes to delete
 
1029
        :return: (CombinedGraphIndex, reload_counter)
 
1030
        """
 
1031
        index1 = self.make_index('1', nodes=[(('1',), '', ())])
 
1032
        index2 = self.make_index('2', nodes=[(('2',), '', ())])
 
1033
        index3 = self.make_index('3', nodes=[
 
1034
            (('1',), '', ()),
 
1035
            (('2',), '', ())])
 
1036
 
 
1037
        # total_reloads, num_changed, num_unchanged
 
1038
        reload_counter = [0, 0, 0]
 
1039
        def reload():
 
1040
            reload_counter[0] += 1
 
1041
            new_indices = [index3]
 
1042
            if index._indices == new_indices:
 
1043
                reload_counter[2] += 1
 
1044
                return False
 
1045
            reload_counter[1] += 1
 
1046
            index._indices[:] = new_indices
 
1047
            return True
 
1048
        index = CombinedGraphIndex([index1, index2], reload_func=reload)
 
1049
        trans = self.get_transport()
 
1050
        for fname in missing:
 
1051
            trans.delete(fname)
 
1052
        return index, reload_counter
544
1053
 
545
1054
    def test_open_missing_index_no_error(self):
546
1055
        trans = self.get_transport()
547
 
        index1 = GraphIndex(trans, 'missing')
 
1056
        index1 = GraphIndex(trans, 'missing', 100)
548
1057
        index = CombinedGraphIndex([index1])
549
1058
 
550
1059
    def test_add_index(self):
622
1131
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
623
1132
            (index2, ('ref', ), 'refdata', ((), ))]),
624
1133
            set(index.iter_entries([('name', ), ('ref', )])))
625
 
 
 
1134
 
626
1135
    def test_iter_all_keys_dup_entry(self):
627
1136
        index1 = self.make_index('1', 1, nodes=[
628
1137
            (('name', ), 'data', ([('ref', )], )),
633
1142
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
634
1143
            (index1, ('ref', ), 'refdata', ((), ))]),
635
1144
            set(index.iter_entries([('name', ), ('ref', )])))
636
 
 
 
1145
 
637
1146
    def test_iter_missing_entry_empty(self):
638
1147
        index = CombinedGraphIndex([])
639
1148
        self.assertEqual([], list(index.iter_entries([('a', )])))
648
1157
        index2 = self.make_index('2')
649
1158
        index = CombinedGraphIndex([index1, index2])
650
1159
        self.assertEqual([], list(index.iter_entries([('a', )])))
651
 
 
 
1160
 
652
1161
    def test_iter_entry_present_one_index_only(self):
653
1162
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
654
1163
        index2 = self.make_index('2', nodes=[])
677
1186
    def test_validate_bad_child_index_errors(self):
678
1187
        trans = self.get_transport()
679
1188
        trans.put_bytes('name', "not an index\n")
680
 
        index1 = GraphIndex(trans, 'name')
 
1189
        index1 = GraphIndex(trans, 'name', 13)
681
1190
        index = CombinedGraphIndex([index1])
682
1191
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
683
1192
 
685
1194
        index = CombinedGraphIndex([])
686
1195
        index.validate()
687
1196
 
 
1197
    def test_key_count_reloads(self):
 
1198
        index, reload_counter = self.make_combined_index_with_missing()
 
1199
        self.assertEqual(2, index.key_count())
 
1200
        self.assertEqual([1, 1, 0], reload_counter)
 
1201
 
 
1202
    def test_key_count_no_reload(self):
 
1203
        index, reload_counter = self.make_combined_index_with_missing()
 
1204
        index._reload_func = None
 
1205
        # Without a _reload_func we just raise the exception
 
1206
        self.assertRaises(errors.NoSuchFile, index.key_count)
 
1207
 
 
1208
    def test_key_count_reloads_and_fails(self):
 
1209
        # We have deleted all underlying indexes, so we will try to reload, but
 
1210
        # still fail. This is mostly to test we don't get stuck in an infinite
 
1211
        # loop trying to reload
 
1212
        index, reload_counter = self.make_combined_index_with_missing(
 
1213
                                    ['1', '2', '3'])
 
1214
        self.assertRaises(errors.NoSuchFile, index.key_count)
 
1215
        self.assertEqual([2, 1, 1], reload_counter)
 
1216
 
 
1217
    def test_iter_entries_reloads(self):
 
1218
        index, reload_counter = self.make_combined_index_with_missing()
 
1219
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
 
1220
        index3 = index._indices[0]
 
1221
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
 
1222
                         result)
 
1223
        self.assertEqual([1, 1, 0], reload_counter)
 
1224
 
 
1225
    def test_iter_entries_reloads_midway(self):
 
1226
        # The first index still looks present, so we get interrupted mid-way
 
1227
        # through
 
1228
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1229
        index1, index2 = index._indices
 
1230
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
 
1231
        index3 = index._indices[0]
 
1232
        # We had already yielded '1', so we just go on to the next, we should
 
1233
        # not yield '1' twice.
 
1234
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
 
1235
                         result)
 
1236
        self.assertEqual([1, 1, 0], reload_counter)
 
1237
 
 
1238
    def test_iter_entries_no_reload(self):
 
1239
        index, reload_counter = self.make_combined_index_with_missing()
 
1240
        index._reload_func = None
 
1241
        # Without a _reload_func we just raise the exception
 
1242
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
 
1243
 
 
1244
    def test_iter_entries_reloads_and_fails(self):
 
1245
        index, reload_counter = self.make_combined_index_with_missing(
 
1246
                                    ['1', '2', '3'])
 
1247
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
 
1248
        self.assertEqual([2, 1, 1], reload_counter)
 
1249
 
 
1250
    def test_iter_all_entries_reloads(self):
 
1251
        index, reload_counter = self.make_combined_index_with_missing()
 
1252
        result = list(index.iter_all_entries())
 
1253
        index3 = index._indices[0]
 
1254
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
 
1255
                         result)
 
1256
        self.assertEqual([1, 1, 0], reload_counter)
 
1257
 
 
1258
    def test_iter_all_entries_reloads_midway(self):
 
1259
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1260
        index1, index2 = index._indices
 
1261
        result = list(index.iter_all_entries())
 
1262
        index3 = index._indices[0]
 
1263
        # We had already yielded '1', so we just go on to the next, we should
 
1264
        # not yield '1' twice.
 
1265
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
 
1266
                         result)
 
1267
        self.assertEqual([1, 1, 0], reload_counter)
 
1268
 
 
1269
    def test_iter_all_entries_no_reload(self):
 
1270
        index, reload_counter = self.make_combined_index_with_missing()
 
1271
        index._reload_func = None
 
1272
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
 
1273
 
 
1274
    def test_iter_all_entries_reloads_and_fails(self):
 
1275
        index, reload_counter = self.make_combined_index_with_missing(
 
1276
                                    ['1', '2', '3'])
 
1277
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
 
1278
 
 
1279
    def test_iter_entries_prefix_reloads(self):
 
1280
        index, reload_counter = self.make_combined_index_with_missing()
 
1281
        result = list(index.iter_entries_prefix([('1',)]))
 
1282
        index3 = index._indices[0]
 
1283
        self.assertEqual([(index3, ('1',), '')], result)
 
1284
        self.assertEqual([1, 1, 0], reload_counter)
 
1285
 
 
1286
    def test_iter_entries_prefix_reloads_midway(self):
 
1287
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1288
        index1, index2 = index._indices
 
1289
        result = list(index.iter_entries_prefix([('1',)]))
 
1290
        index3 = index._indices[0]
 
1291
        # We had already yielded '1', so we just go on to the next, we should
 
1292
        # not yield '1' twice.
 
1293
        self.assertEqual([(index1, ('1',), '')], result)
 
1294
        self.assertEqual([1, 1, 0], reload_counter)
 
1295
 
 
1296
    def test_iter_entries_prefix_no_reload(self):
 
1297
        index, reload_counter = self.make_combined_index_with_missing()
 
1298
        index._reload_func = None
 
1299
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
 
1300
                                                 [('1',)])
 
1301
 
 
1302
    def test_iter_entries_prefix_reloads_and_fails(self):
 
1303
        index, reload_counter = self.make_combined_index_with_missing(
 
1304
                                    ['1', '2', '3'])
 
1305
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
 
1306
                                                 [('1',)])
 
1307
 
 
1308
    def test_validate_reloads(self):
 
1309
        index, reload_counter = self.make_combined_index_with_missing()
 
1310
        index.validate()
 
1311
        self.assertEqual([1, 1, 0], reload_counter)
 
1312
 
 
1313
    def test_validate_reloads_midway(self):
 
1314
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1315
        index.validate()
 
1316
 
 
1317
    def test_validate_no_reload(self):
 
1318
        index, reload_counter = self.make_combined_index_with_missing()
 
1319
        index._reload_func = None
 
1320
        self.assertRaises(errors.NoSuchFile, index.validate)
 
1321
 
 
1322
    def test_validate_reloads_and_fails(self):
 
1323
        index, reload_counter = self.make_combined_index_with_missing(
 
1324
                                    ['1', '2', '3'])
 
1325
        self.assertRaises(errors.NoSuchFile, index.validate)
 
1326
 
 
1327
    def test_find_ancestors_across_indexes(self):
 
1328
        key1 = ('key-1',)
 
1329
        key2 = ('key-2',)
 
1330
        key3 = ('key-3',)
 
1331
        key4 = ('key-4',)
 
1332
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1333
            (key1, 'value', ([],)),
 
1334
            (key2, 'value', ([key1],)),
 
1335
            ])
 
1336
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1337
            (key3, 'value', ([key2],)),
 
1338
            (key4, 'value', ([key3],)),
 
1339
            ])
 
1340
        c_index = CombinedGraphIndex([index1, index2])
 
1341
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1342
        self.assertEqual({key1: ()}, parent_map)
 
1343
        self.assertEqual(set(), missing_keys)
 
1344
        # Now look for a key from index2 which requires us to find the key in
 
1345
        # the second index, and then continue searching for parents in the
 
1346
        # first index
 
1347
        parent_map, missing_keys = c_index.find_ancestry([key3], 0)
 
1348
        self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
 
1349
        self.assertEqual(set(), missing_keys)
 
1350
 
 
1351
    def test_find_ancestors_missing_keys(self):
 
1352
        key1 = ('key-1',)
 
1353
        key2 = ('key-2',)
 
1354
        key3 = ('key-3',)
 
1355
        key4 = ('key-4',)
 
1356
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1357
            (key1, 'value', ([],)),
 
1358
            (key2, 'value', ([key1],)),
 
1359
            ])
 
1360
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1361
            (key3, 'value', ([key2],)),
 
1362
            ])
 
1363
        c_index = CombinedGraphIndex([index1, index2])
 
1364
        # Searching for a key which is actually not present at all should
 
1365
        # eventually converge
 
1366
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1367
        self.assertEqual({}, parent_map)
 
1368
        self.assertEqual(set([key4]), missing_keys)
 
1369
 
 
1370
    def test_find_ancestors_no_indexes(self):
 
1371
        c_index = CombinedGraphIndex([])
 
1372
        key1 = ('key-1',)
 
1373
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1374
        self.assertEqual({}, parent_map)
 
1375
        self.assertEqual(set([key1]), missing_keys)
 
1376
 
 
1377
    def test_find_ancestors_ghost_parent(self):
 
1378
        key1 = ('key-1',)
 
1379
        key2 = ('key-2',)
 
1380
        key3 = ('key-3',)
 
1381
        key4 = ('key-4',)
 
1382
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1383
            (key1, 'value', ([],)),
 
1384
            (key2, 'value', ([key1],)),
 
1385
            ])
 
1386
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1387
            (key4, 'value', ([key2, key3],)),
 
1388
            ])
 
1389
        c_index = CombinedGraphIndex([index1, index2])
 
1390
        # Searching for a key which is actually not present at all should
 
1391
        # eventually converge
 
1392
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1393
        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
 
1394
                         parent_map)
 
1395
        self.assertEqual(set([key3]), missing_keys)
 
1396
 
 
1397
    def test__find_ancestors_empty_index(self):
 
1398
        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
 
1399
        parent_map = {}
 
1400
        missing_keys = set()
 
1401
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1402
                                            missing_keys)
 
1403
        self.assertEqual(set(), search_keys)
 
1404
        self.assertEqual({}, parent_map)
 
1405
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1406
 
688
1407
 
689
1408
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
690
1409