/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

  • Committer: Martin Pool
  • Date: 2007-10-03 08:06:44 UTC
  • mto: This revision was merged to the branch mainline in revision 2901.
  • Revision ID: mbp@sourcefrog.net-20071003080644-oivy0gkg98sex0ed
Avoid internal error tracebacks on failure to lock on readonly transport (#129701).

Add new LockFailed, which doesn't imply that we failed to get it because of
contention.  Raise this if we fail to create the pending or lock directories
because of Transport errors.

UnlockableTransport is not an internal error.

ReadOnlyLockError has a message which didn't match its name or usage; it's now
deprecated and callers are updated to use LockFailed which is more appropriate.

Add zero_ninetytwo deprecation symbol.

Unify assertMatchesRe with TestCase.assertContainsRe.

When the constructor is deprecated, just say that the class is deprecated, not
the __init__ method - this works better with applyDeprecated in tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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
23
22
 
24
23
 
25
24
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
173
172
            "key\x00\x00\t\x00data\n"
174
173
            "\n", contents)
175
174
 
176
 
    def test_clear_cache(self):
177
 
        builder = GraphIndexBuilder(reference_lists=2)
178
 
        # This is a no-op, but the api should exist
179
 
        builder.clear_cache()
180
 
 
181
175
    def test_node_references_are_byte_offsets(self):
182
176
        builder = GraphIndexBuilder(reference_lists=1)
183
177
        builder.add_node(('reference', ), 'data', ([], ))
235
229
        builder.add_node(('2-key', ), '', (references, ))
236
230
        stream = builder.finish()
237
231
        contents = stream.read()
238
 
        self.assertEqualDiff(
 
232
        self.assertEqual(
239
233
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
240
234
            "0\x00a\x00\x00\n"
241
235
            "1\x00a\x00\x00\n"
355
349
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
356
350
        builder.add_node(('reference', 'tokey'), 'data', ([],))
357
351
 
358
 
    def test_set_optimize(self):
359
 
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
360
 
        builder.set_optimize(for_size=True)
361
 
        self.assertTrue(builder._optimize_for_size)
362
 
        builder.set_optimize(for_size=False)
363
 
        self.assertFalse(builder._optimize_for_size)
364
 
 
365
352
 
366
353
class TestGraphIndex(TestCaseWithMemoryTransport):
367
354
 
368
 
    def make_key(self, number):
369
 
        return (str(number) + 'X'*100,)
370
 
 
371
 
    def make_value(self, number):
372
 
            return str(number) + 'Y'*100
373
 
 
374
 
    def make_nodes(self, count=64):
375
 
        # generate a big enough index that we only read some of it on a typical
376
 
        # bisection lookup.
377
 
        nodes = []
378
 
        for counter in range(count):
379
 
            nodes.append((self.make_key(counter), self.make_value(counter), ()))
380
 
        return nodes
381
 
 
382
355
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
383
356
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
384
357
        for key, value, references in nodes:
385
358
            builder.add_node(key, value, references)
386
359
        stream = builder.finish()
387
 
        trans = get_transport('trace+' + self.get_url())
388
 
        size = trans.put_file('index', stream)
389
 
        return GraphIndex(trans, 'index', size)
390
 
 
391
 
    def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
392
 
                               offset=0):
393
 
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
394
 
        for key, value, references in nodes:
395
 
            builder.add_node(key, value, references)
396
 
        content = builder.finish().read()
397
 
        size = len(content)
398
360
        trans = self.get_transport()
399
 
        trans.put_bytes('index', (' '*offset) + content)
400
 
        return GraphIndex(trans, 'index', size, offset=offset)
401
 
 
402
 
    def test_clear_cache(self):
403
 
        index = self.make_index()
404
 
        # For now, we just want to make sure the api is available. As this is
405
 
        # old code, we don't really worry if it *does* anything.
406
 
        index.clear_cache()
 
361
        trans.put_file('index', stream)
 
362
        return GraphIndex(trans, 'index')
407
363
 
408
364
    def test_open_bad_index_no_error(self):
409
365
        trans = self.get_transport()
410
366
        trans.put_bytes('name', "not an index\n")
411
 
        index = GraphIndex(trans, 'name', 13)
412
 
 
413
 
    def test_with_offset(self):
414
 
        nodes = self.make_nodes(200)
415
 
        index = self.make_index_with_offset(offset=1234567, nodes=nodes)
416
 
        self.assertEqual(200, index.key_count())
417
 
 
418
 
    def test_buffer_all_with_offset(self):
419
 
        nodes = self.make_nodes(200)
420
 
        index = self.make_index_with_offset(offset=1234567, nodes=nodes)
421
 
        index._buffer_all()
422
 
        self.assertEqual(200, index.key_count())
423
 
 
424
 
    def test_side_effect_buffering_with_offset(self):
425
 
        nodes = self.make_nodes(20)
426
 
        index = self.make_index_with_offset(offset=1234567, nodes=nodes)
427
 
        index._transport.recommended_page_size = lambda:64*1024
428
 
        subset_nodes = [nodes[0][0], nodes[10][0], nodes[19][0]]
429
 
        entries = [n[1] for n in index.iter_entries(subset_nodes)]
430
 
        self.assertEqual(sorted(subset_nodes), sorted(entries))
431
 
        self.assertEqual(20, index.key_count())
432
 
 
433
 
    def test_open_sets_parsed_map_empty(self):
434
 
        index = self.make_index()
435
 
        self.assertEqual([], index._parsed_byte_map)
436
 
        self.assertEqual([], index._parsed_key_map)
437
 
 
438
 
    def test_key_count_buffers(self):
439
 
        index = self.make_index(nodes=self.make_nodes(2))
440
 
        # reset the transport log
441
 
        del index._transport._activity[:]
442
 
        self.assertEqual(2, index.key_count())
443
 
        # We should have requested reading the header bytes
444
 
        self.assertEqual([
445
 
            ('readv', 'index', [(0, 200)], True, index._size),
446
 
            ],
447
 
            index._transport._activity)
448
 
        # And that should have been enough to trigger reading the whole index
449
 
        # with buffering
450
 
        self.assertIsNot(None, index._nodes)
451
 
 
452
 
    def test_lookup_key_via_location_buffers(self):
453
 
        index = self.make_index()
454
 
        # reset the transport log
455
 
        del index._transport._activity[:]
456
 
        # do a _lookup_keys_via_location call for the middle of the file, which
457
 
        # is what bisection uses.
458
 
        result = index._lookup_keys_via_location(
459
 
            [(index._size // 2, ('missing', ))])
460
 
        # this should have asked for a readv request, with adjust_for_latency,
461
 
        # and two regions: the header, and half-way into the file.
462
 
        self.assertEqual([
463
 
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
464
 
            ],
465
 
            index._transport._activity)
466
 
        # and the result should be that the key cannot be present, because this
467
 
        # is a trivial index.
468
 
        self.assertEqual([((index._size // 2, ('missing', )), False)],
469
 
            result)
470
 
        # And this should have caused the file to be fully buffered
471
 
        self.assertIsNot(None, index._nodes)
472
 
        self.assertEqual([], index._parsed_byte_map)
473
 
 
474
 
    def test_first_lookup_key_via_location(self):
475
 
        # We need enough data so that the _HEADER_READV doesn't consume the
476
 
        # whole file. We always read 800 bytes for every key, and the local
477
 
        # transport natural expansion is 4096 bytes. So we have to have >8192
478
 
        # bytes or we will trigger "buffer_all".
479
 
        # We also want the 'missing' key to fall within the range that *did*
480
 
        # read
481
 
        nodes = []
482
 
        index = self.make_index(nodes=self.make_nodes(64))
483
 
        # reset the transport log
484
 
        del index._transport._activity[:]
485
 
        # do a _lookup_keys_via_location call for the middle of the file, which
486
 
        # is what bisection uses.
487
 
        start_lookup = index._size // 2
488
 
        result = index._lookup_keys_via_location(
489
 
            [(start_lookup, ('40missing', ))])
490
 
        # this should have asked for a readv request, with adjust_for_latency,
491
 
        # and two regions: the header, and half-way into the file.
492
 
        self.assertEqual([
493
 
            ('readv', 'index',
494
 
             [(start_lookup, 800), (0, 200)], True, index._size),
495
 
            ],
496
 
            index._transport._activity)
497
 
        # and the result should be that the key cannot be present, because this
498
 
        # is a trivial index.
499
 
        self.assertEqual([((start_lookup, ('40missing', )), False)],
500
 
            result)
501
 
        # And this should not have caused the file to be fully buffered
502
 
        self.assertIs(None, index._nodes)
503
 
        # And the regions of the file that have been parsed should be in the
504
 
        # parsed_byte_map and the parsed_key_map
505
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
506
 
        self.assertEqual([(None, self.make_key(26)),
507
 
                          (self.make_key(31), self.make_key(48))],
508
 
                         index._parsed_key_map)
509
 
 
510
 
    def test_parsing_non_adjacent_data_trims(self):
511
 
        index = self.make_index(nodes=self.make_nodes(64))
512
 
        result = index._lookup_keys_via_location(
513
 
            [(index._size // 2, ('40', ))])
514
 
        # and the result should be that the key cannot be present, because key is
515
 
        # in the middle of the observed data from a 4K read - the smallest transport
516
 
        # will do today with this api.
517
 
        self.assertEqual([((index._size // 2, ('40', )), False)],
518
 
            result)
519
 
        # and we should have a parse map that includes the header and the
520
 
        # region that was parsed after trimming.
521
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
522
 
        self.assertEqual([(None, self.make_key(26)),
523
 
                          (self.make_key(31), self.make_key(48))],
524
 
            index._parsed_key_map)
525
 
 
526
 
    def test_parsing_data_handles_parsed_contained_regions(self):
527
 
        # the following patten creates a parsed region that is wholly within a
528
 
        # single result from the readv layer:
529
 
        # .... single-read (readv-minimum-size) ...
530
 
        # which then trims the start and end so the parsed size is < readv
531
 
        # miniumum.
532
 
        # then a dual lookup (or a reference lookup for that matter) which
533
 
        # abuts or overlaps the parsed region on both sides will need to
534
 
        # discard the data in the middle, but parse the end as well.
535
 
        #
536
 
        # we test this by doing a single lookup to seed the data, then
537
 
        # a lookup for two keys that are present, and adjacent -
538
 
        # we except both to be found, and the parsed byte map to include the
539
 
        # locations of both keys.
540
 
        index = self.make_index(nodes=self.make_nodes(128))
541
 
        result = index._lookup_keys_via_location(
542
 
            [(index._size // 2, ('40', ))])
543
 
        # and we should have a parse map that includes the header and the
544
 
        # region that was parsed after trimming.
545
 
        self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
546
 
        self.assertEqual([(None, self.make_key(116)),
547
 
                          (self.make_key(35), self.make_key(51))],
548
 
            index._parsed_key_map)
549
 
        # now ask for two keys, right before and after the parsed region
550
 
        result = index._lookup_keys_via_location(
551
 
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
552
 
        self.assertEqual([
553
 
            ((11450, self.make_key(34)),
554
 
             (index, self.make_key(34), self.make_value(34))),
555
 
            ((15707, self.make_key(52)),
556
 
             (index, self.make_key(52), self.make_value(52))),
557
 
            ],
558
 
            result)
559
 
        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
560
 
 
561
 
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
562
 
        # generate a big enough index that we only read some of it on a typical
563
 
        # bisection lookup.
564
 
        index = self.make_index(nodes=self.make_nodes(64))
565
 
        # lookup the keys in the middle of the file
566
 
        result =index._lookup_keys_via_location(
567
 
            [(index._size // 2, ('40', ))])
568
 
        # check the parse map, this determines the test validity
569
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
570
 
        self.assertEqual([(None, self.make_key(26)),
571
 
                          (self.make_key(31), self.make_key(48))],
572
 
            index._parsed_key_map)
573
 
        # reset the transport log
574
 
        del index._transport._activity[:]
575
 
        # now looking up a key in the portion of the file already parsed should
576
 
        # not create a new transport request, and should return False (cannot
577
 
        # be in the index) - even when the byte location we ask for is outside
578
 
        # the parsed region
579
 
        result = index._lookup_keys_via_location(
580
 
            [(4000, ('40', ))])
581
 
        self.assertEqual([((4000, ('40', )), False)],
582
 
            result)
583
 
        self.assertEqual([], index._transport._activity)
584
 
 
585
 
    def test_lookup_present_key_answers_without_io_when_map_permits(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
 
        # lookup the keys in the middle of the file
590
 
        result =index._lookup_keys_via_location(
591
 
            [(index._size // 2, ('40', ))])
592
 
        # check the parse map, this determines the test validity
593
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
594
 
        self.assertEqual([(None, self.make_key(26)),
595
 
                          (self.make_key(31), self.make_key(48))],
596
 
            index._parsed_key_map)
597
 
        # reset the transport log
598
 
        del index._transport._activity[:]
599
 
        # now looking up a key in the portion of the file already parsed should
600
 
        # not create a new transport request, and should return False (cannot
601
 
        # be in the index) - even when the byte location we ask for is outside
602
 
        # the parsed region
603
 
        #
604
 
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
605
 
        self.assertEqual(
606
 
            [((4000, self.make_key(40)),
607
 
              (index, self.make_key(40), self.make_value(40)))],
608
 
            result)
609
 
        self.assertEqual([], index._transport._activity)
610
 
 
611
 
    def test_lookup_key_below_probed_area(self):
612
 
        # generate a big enough index that we only read some of it on a typical
613
 
        # bisection lookup.
614
 
        index = self.make_index(nodes=self.make_nodes(64))
615
 
        # ask for the key in the middle, but a key that is located in the
616
 
        # unparsed region before the middle.
617
 
        result =index._lookup_keys_via_location(
618
 
            [(index._size // 2, ('30', ))])
619
 
        # check the parse map, this determines the test validity
620
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
621
 
        self.assertEqual([(None, self.make_key(26)),
622
 
                          (self.make_key(31), self.make_key(48))],
623
 
            index._parsed_key_map)
624
 
        self.assertEqual([((index._size // 2, ('30', )), -1)],
625
 
            result)
626
 
 
627
 
    def test_lookup_key_above_probed_area(self):
628
 
        # generate a big enough index that we only read some of it on a typical
629
 
        # bisection lookup.
630
 
        index = self.make_index(nodes=self.make_nodes(64))
631
 
        # ask for the key in the middle, but a key that is located in the
632
 
        # unparsed region after the middle.
633
 
        result =index._lookup_keys_via_location(
634
 
            [(index._size // 2, ('50', ))])
635
 
        # check the parse map, this determines the test validity
636
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
637
 
        self.assertEqual([(None, self.make_key(26)),
638
 
                          (self.make_key(31), self.make_key(48))],
639
 
            index._parsed_key_map)
640
 
        self.assertEqual([((index._size // 2, ('50', )), +1)],
641
 
            result)
642
 
 
643
 
    def test_lookup_key_resolves_references(self):
644
 
        # generate a big enough index that we only read some of it on a typical
645
 
        # bisection lookup.
646
 
        nodes = []
647
 
        for counter in range(99):
648
 
            nodes.append((self.make_key(counter), self.make_value(counter),
649
 
                ((self.make_key(counter + 20),),)  ))
650
 
        index = self.make_index(ref_lists=1, nodes=nodes)
651
 
        # lookup a key in the middle that does not exist, so that when we can
652
 
        # check that the referred-to-keys are not accessed automatically.
653
 
        index_size = index._size
654
 
        index_center = index_size // 2
655
 
        result = index._lookup_keys_via_location(
656
 
            [(index_center, ('40', ))])
657
 
        # check the parse map - only the start and middle should have been
658
 
        # parsed.
659
 
        self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
660
 
        self.assertEqual([(None, self.make_key(17)),
661
 
                          (self.make_key(44), self.make_key(5))],
662
 
            index._parsed_key_map)
663
 
        # and check the transport activity likewise.
664
 
        self.assertEqual(
665
 
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
666
 
                                  index_size)],
667
 
            index._transport._activity)
668
 
        # reset the transport log for testing the reference lookup
669
 
        del index._transport._activity[:]
670
 
        # now looking up a key in the portion of the file already parsed should
671
 
        # only perform IO to resolve its key references.
672
 
        result = index._lookup_keys_via_location([(11000, self.make_key(45))])
673
 
        self.assertEqual(
674
 
            [((11000, self.make_key(45)),
675
 
              (index, self.make_key(45), self.make_value(45),
676
 
               ((self.make_key(65),),)))],
677
 
            result)
678
 
        self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
679
 
            index._transport._activity)
680
 
 
681
 
    def test_lookup_key_can_buffer_all(self):
682
 
        nodes = []
683
 
        for counter in range(64):
684
 
            nodes.append((self.make_key(counter), self.make_value(counter),
685
 
                ((self.make_key(counter + 20),),)  ))
686
 
        index = self.make_index(ref_lists=1, nodes=nodes)
687
 
        # lookup a key in the middle that does not exist, so that when we can
688
 
        # check that the referred-to-keys are not accessed automatically.
689
 
        index_size = index._size
690
 
        index_center = index_size // 2
691
 
        result = index._lookup_keys_via_location([(index_center, ('40', ))])
692
 
        # check the parse map - only the start and middle should have been
693
 
        # parsed.
694
 
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
695
 
        self.assertEqual([(None, self.make_key(25)),
696
 
                          (self.make_key(37), self.make_key(52))],
697
 
            index._parsed_key_map)
698
 
        # and check the transport activity likewise.
699
 
        self.assertEqual(
700
 
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
701
 
                                  index_size)],
702
 
            index._transport._activity)
703
 
        # reset the transport log for testing the reference lookup
704
 
        del index._transport._activity[:]
705
 
        # now looking up a key in the portion of the file already parsed should
706
 
        # only perform IO to resolve its key references.
707
 
        result = index._lookup_keys_via_location([(7000, self.make_key(40))])
708
 
        self.assertEqual(
709
 
            [((7000, self.make_key(40)),
710
 
              (index, self.make_key(40), self.make_value(40),
711
 
               ((self.make_key(60),),)))],
712
 
            result)
713
 
        # Resolving the references would have required more data read, and we
714
 
        # are already above the 50% threshold, so it triggered a _buffer_all
715
 
        self.assertEqual([('get', 'index')], index._transport._activity)
 
367
        index = GraphIndex(trans, 'name')
716
368
 
717
369
    def test_iter_all_entries_empty(self):
718
370
        index = self.make_index()
737
389
            (index, ('ref', ), 'refdata', ((), ))]),
738
390
            set(index.iter_all_entries()))
739
391
 
740
 
    def test_iter_entries_buffers_once(self):
741
 
        index = self.make_index(nodes=self.make_nodes(2))
742
 
        # reset the transport log
743
 
        del index._transport._activity[:]
744
 
        self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
745
 
                         set(index.iter_entries([self.make_key(1)])))
746
 
        # We should have requested reading the header bytes
747
 
        # But not needed any more than that because it would have triggered a
748
 
        # buffer all
749
 
        self.assertEqual([
750
 
            ('readv', 'index', [(0, 200)], True, index._size),
751
 
            ],
752
 
            index._transport._activity)
753
 
        # And that should have been enough to trigger reading the whole index
754
 
        # with buffering
755
 
        self.assertIsNot(None, index._nodes)
756
 
 
757
 
    def test_iter_entries_buffers_by_bytes_read(self):
758
 
        index = self.make_index(nodes=self.make_nodes(64))
759
 
        list(index.iter_entries([self.make_key(10)]))
760
 
        # The first time through isn't enough to trigger a buffer all
761
 
        self.assertIs(None, index._nodes)
762
 
        self.assertEqual(4096, index._bytes_read)
763
 
        # Grabbing a key in that same page won't trigger a buffer all, as we
764
 
        # still haven't read 50% of the file
765
 
        list(index.iter_entries([self.make_key(11)]))
766
 
        self.assertIs(None, index._nodes)
767
 
        self.assertEqual(4096, index._bytes_read)
768
 
        # We haven't read more data, so reading outside the range won't trigger
769
 
        # a buffer all right away
770
 
        list(index.iter_entries([self.make_key(40)]))
771
 
        self.assertIs(None, index._nodes)
772
 
        self.assertEqual(8192, index._bytes_read)
773
 
        # On the next pass, we will not trigger buffer all if the key is
774
 
        # available without reading more
775
 
        list(index.iter_entries([self.make_key(32)]))
776
 
        self.assertIs(None, index._nodes)
777
 
        # But if we *would* need to read more to resolve it, then we will
778
 
        # buffer all.
779
 
        list(index.iter_entries([self.make_key(60)]))
780
 
        self.assertIsNot(None, index._nodes)
781
 
 
782
 
    def test_iter_entries_references_resolved(self):
783
 
        index = self.make_index(1, nodes=[
784
 
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
785
 
            (('ref', ), 'refdata', ([], ))])
786
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
787
 
            (index, ('ref', ), 'refdata', ((), ))]),
788
 
            set(index.iter_entries([('name',), ('ref',)])))
789
 
 
790
 
    def test_iter_entries_references_2_refs_resolved(self):
791
 
        index = self.make_index(2, nodes=[
792
 
            (('name', ), 'data', ([('ref', )], [('ref', )])),
793
 
            (('ref', ), 'refdata', ([], []))])
794
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
795
 
            (index, ('ref', ), 'refdata', ((), ()))]),
796
 
            set(index.iter_entries([('name',), ('ref',)])))
797
 
 
798
392
    def test_iteration_absent_skipped(self):
799
393
        index = self.make_index(1, nodes=[
800
394
            (('name', ), 'data', ([('ref', )], ))])
829
423
        index = self.make_index()
830
424
        self.assertEqual([], list(index.iter_entries([('a', )])))
831
425
 
832
 
    def test_iter_missing_entry_empty_no_size(self):
833
 
        index = self.make_index()
834
 
        index = GraphIndex(index._transport, 'index', None)
835
 
        self.assertEqual([], list(index.iter_entries([('a', )])))
836
 
 
837
426
    def test_iter_key_prefix_1_element_key_None(self):
838
427
        index = self.make_index()
839
428
        self.assertRaises(errors.BadIndexKey, list,
902
491
            (('name', ), '', ()), (('foo', ), '', ())])
903
492
        self.assertEqual(2, index.key_count())
904
493
 
905
 
    def test_read_and_parse_tracks_real_read_value(self):
906
 
        index = self.make_index(nodes=self.make_nodes(10))
907
 
        del index._transport._activity[:]
908
 
        index._read_and_parse([(0, 200)])
909
 
        self.assertEqual([
910
 
            ('readv', 'index', [(0, 200)], True, index._size),
911
 
            ],
912
 
            index._transport._activity)
913
 
        # The readv expansion code will expand the initial request to 4096
914
 
        # bytes, which is more than enough to read the entire index, and we
915
 
        # will track the fact that we read that many bytes.
916
 
        self.assertEqual(index._size, index._bytes_read)
917
 
 
918
 
    def test_read_and_parse_triggers_buffer_all(self):
919
 
        index = self.make_index(key_elements=2, nodes=[
920
 
            (('name', 'fin1'), 'data', ()),
921
 
            (('name', 'fin2'), 'beta', ()),
922
 
            (('ref', 'erence'), 'refdata', ())])
923
 
        self.assertTrue(index._size > 0)
924
 
        self.assertIs(None, index._nodes)
925
 
        index._read_and_parse([(0, index._size)])
926
 
        self.assertIsNot(None, index._nodes)
927
 
 
928
494
    def test_validate_bad_index_errors(self):
929
495
        trans = self.get_transport()
930
496
        trans.put_bytes('name', "not an index\n")
931
 
        index = GraphIndex(trans, 'name', 13)
 
497
        index = GraphIndex(trans, 'name')
932
498
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
933
499
 
934
500
    def test_validate_bad_node_refs(self):
964
530
        index = self.make_index(nodes=[(('key', ), 'value', ())])
965
531
        index.validate()
966
532
 
967
 
    # XXX: external_references tests are duplicated in test_btree_index.  We
968
 
    # probably should have per_graph_index tests...
969
 
    def test_external_references_no_refs(self):
970
 
        index = self.make_index(ref_lists=0, nodes=[])
971
 
        self.assertRaises(ValueError, index.external_references, 0)
972
 
 
973
 
    def test_external_references_no_results(self):
974
 
        index = self.make_index(ref_lists=1, nodes=[
975
 
            (('key',), 'value', ([],))])
976
 
        self.assertEqual(set(), index.external_references(0))
977
 
 
978
 
    def test_external_references_missing_ref(self):
979
 
        missing_key = ('missing',)
980
 
        index = self.make_index(ref_lists=1, nodes=[
981
 
            (('key',), 'value', ([missing_key],))])
982
 
        self.assertEqual(set([missing_key]), index.external_references(0))
983
 
 
984
 
    def test_external_references_multiple_ref_lists(self):
985
 
        missing_key = ('missing',)
986
 
        index = self.make_index(ref_lists=2, nodes=[
987
 
            (('key',), 'value', ([], [missing_key]))])
988
 
        self.assertEqual(set([]), index.external_references(0))
989
 
        self.assertEqual(set([missing_key]), index.external_references(1))
990
 
 
991
 
    def test_external_references_two_records(self):
992
 
        index = self.make_index(ref_lists=1, nodes=[
993
 
            (('key-1',), 'value', ([('key-2',)],)),
994
 
            (('key-2',), 'value', ([],)),
995
 
            ])
996
 
        self.assertEqual(set([]), index.external_references(0))
997
 
 
998
 
    def test__find_ancestors(self):
999
 
        key1 = ('key-1',)
1000
 
        key2 = ('key-2',)
1001
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1002
 
            (key1, 'value', ([key2],)),
1003
 
            (key2, 'value', ([],)),
1004
 
            ])
1005
 
        parent_map = {}
1006
 
        missing_keys = set()
1007
 
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1008
 
        self.assertEqual({key1: (key2,)}, parent_map)
1009
 
        self.assertEqual(set(), missing_keys)
1010
 
        self.assertEqual(set([key2]), search_keys)
1011
 
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1012
 
                                            missing_keys)
1013
 
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1014
 
        self.assertEqual(set(), missing_keys)
1015
 
        self.assertEqual(set(), search_keys)
1016
 
 
1017
 
    def test__find_ancestors_w_missing(self):
1018
 
        key1 = ('key-1',)
1019
 
        key2 = ('key-2',)
1020
 
        key3 = ('key-3',)
1021
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1022
 
            (key1, 'value', ([key2],)),
1023
 
            (key2, 'value', ([],)),
1024
 
            ])
1025
 
        parent_map = {}
1026
 
        missing_keys = set()
1027
 
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1028
 
                                            missing_keys)
1029
 
        self.assertEqual({key2: ()}, parent_map)
1030
 
        self.assertEqual(set([key3]), missing_keys)
1031
 
        self.assertEqual(set(), search_keys)
1032
 
 
1033
 
    def test__find_ancestors_dont_search_known(self):
1034
 
        key1 = ('key-1',)
1035
 
        key2 = ('key-2',)
1036
 
        key3 = ('key-3',)
1037
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1038
 
            (key1, 'value', ([key2],)),
1039
 
            (key2, 'value', ([key3],)),
1040
 
            (key3, 'value', ([],)),
1041
 
            ])
1042
 
        # We already know about key2, so we won't try to search for key3
1043
 
        parent_map = {key2: (key3,)}
1044
 
        missing_keys = set()
1045
 
        search_keys = index._find_ancestors([key1], 0, parent_map,
1046
 
                                            missing_keys)
1047
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1048
 
        self.assertEqual(set(), missing_keys)
1049
 
        self.assertEqual(set(), search_keys)
1050
 
 
1051
 
    def test_supports_unlimited_cache(self):
1052
 
        builder = GraphIndexBuilder(0, key_elements=1)
1053
 
        stream = builder.finish()
1054
 
        trans = get_transport(self.get_url())
1055
 
        size = trans.put_file('index', stream)
1056
 
        # It doesn't matter what unlimited_cache does here, just that it can be
1057
 
        # passed
1058
 
        index = GraphIndex(trans, 'index', size, unlimited_cache=True)
1059
 
 
1060
533
 
1061
534
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1062
535
 
1066
539
            builder.add_node(key, value, references)
1067
540
        stream = builder.finish()
1068
541
        trans = self.get_transport()
1069
 
        size = trans.put_file(name, stream)
1070
 
        return GraphIndex(trans, name, size)
1071
 
 
1072
 
    def make_combined_index_with_missing(self, missing=['1', '2']):
1073
 
        """Create a CombinedGraphIndex which will have missing indexes.
1074
 
 
1075
 
        This creates a CGI which thinks it has 2 indexes, however they have
1076
 
        been deleted. If CGI._reload_func() is called, then it will repopulate
1077
 
        with a new index.
1078
 
 
1079
 
        :param missing: The underlying indexes to delete
1080
 
        :return: (CombinedGraphIndex, reload_counter)
1081
 
        """
1082
 
        index1 = self.make_index('1', nodes=[(('1',), '', ())])
1083
 
        index2 = self.make_index('2', nodes=[(('2',), '', ())])
1084
 
        index3 = self.make_index('3', nodes=[
1085
 
            (('1',), '', ()),
1086
 
            (('2',), '', ())])
1087
 
 
1088
 
        # total_reloads, num_changed, num_unchanged
1089
 
        reload_counter = [0, 0, 0]
1090
 
        def reload():
1091
 
            reload_counter[0] += 1
1092
 
            new_indices = [index3]
1093
 
            if index._indices == new_indices:
1094
 
                reload_counter[2] += 1
1095
 
                return False
1096
 
            reload_counter[1] += 1
1097
 
            index._indices[:] = new_indices
1098
 
            return True
1099
 
        index = CombinedGraphIndex([index1, index2], reload_func=reload)
1100
 
        trans = self.get_transport()
1101
 
        for fname in missing:
1102
 
            trans.delete(fname)
1103
 
        return index, reload_counter
 
542
        trans.put_file(name, stream)
 
543
        return GraphIndex(trans, name)
1104
544
 
1105
545
    def test_open_missing_index_no_error(self):
1106
546
        trans = self.get_transport()
1107
 
        index1 = GraphIndex(trans, 'missing', 100)
 
547
        index1 = GraphIndex(trans, 'missing')
1108
548
        index = CombinedGraphIndex([index1])
1109
549
 
1110
550
    def test_add_index(self):
1113
553
        index.insert_index(0, index1)
1114
554
        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1115
555
 
1116
 
    def test_clear_cache(self):
1117
 
        log = []
1118
 
 
1119
 
        class ClearCacheProxy(object):
1120
 
 
1121
 
            def __init__(self, index):
1122
 
                self._index = index
1123
 
 
1124
 
            def __getattr__(self, name):
1125
 
                return getattr(self._index)
1126
 
 
1127
 
            def clear_cache(self):
1128
 
                log.append(self._index)
1129
 
                return self._index.clear_cache()
1130
 
 
1131
 
        index = CombinedGraphIndex([])
1132
 
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1133
 
        index.insert_index(0, ClearCacheProxy(index1))
1134
 
        index2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1135
 
        index.insert_index(1, ClearCacheProxy(index2))
1136
 
        # CombinedGraphIndex should call 'clear_cache()' on all children
1137
 
        index.clear_cache()
1138
 
        self.assertEqual(sorted([index1, index2]), sorted(log))
1139
 
 
1140
556
    def test_iter_all_entries_empty(self):
1141
557
        index = CombinedGraphIndex([])
1142
558
        self.assertEqual([], list(index.iter_all_entries()))
1206
622
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1207
623
            (index2, ('ref', ), 'refdata', ((), ))]),
1208
624
            set(index.iter_entries([('name', ), ('ref', )])))
1209
 
 
 
625
 
1210
626
    def test_iter_all_keys_dup_entry(self):
1211
627
        index1 = self.make_index('1', 1, nodes=[
1212
628
            (('name', ), 'data', ([('ref', )], )),
1217
633
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1218
634
            (index1, ('ref', ), 'refdata', ((), ))]),
1219
635
            set(index.iter_entries([('name', ), ('ref', )])))
1220
 
 
 
636
 
1221
637
    def test_iter_missing_entry_empty(self):
1222
638
        index = CombinedGraphIndex([])
1223
639
        self.assertEqual([], list(index.iter_entries([('a', )])))
1232
648
        index2 = self.make_index('2')
1233
649
        index = CombinedGraphIndex([index1, index2])
1234
650
        self.assertEqual([], list(index.iter_entries([('a', )])))
1235
 
 
 
651
 
1236
652
    def test_iter_entry_present_one_index_only(self):
1237
653
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1238
654
        index2 = self.make_index('2', nodes=[])
1261
677
    def test_validate_bad_child_index_errors(self):
1262
678
        trans = self.get_transport()
1263
679
        trans.put_bytes('name', "not an index\n")
1264
 
        index1 = GraphIndex(trans, 'name', 13)
 
680
        index1 = GraphIndex(trans, 'name')
1265
681
        index = CombinedGraphIndex([index1])
1266
682
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1267
683
 
1269
685
        index = CombinedGraphIndex([])
1270
686
        index.validate()
1271
687
 
1272
 
    def test_key_count_reloads(self):
1273
 
        index, reload_counter = self.make_combined_index_with_missing()
1274
 
        self.assertEqual(2, index.key_count())
1275
 
        self.assertEqual([1, 1, 0], reload_counter)
1276
 
 
1277
 
    def test_key_count_no_reload(self):
1278
 
        index, reload_counter = self.make_combined_index_with_missing()
1279
 
        index._reload_func = None
1280
 
        # Without a _reload_func we just raise the exception
1281
 
        self.assertRaises(errors.NoSuchFile, index.key_count)
1282
 
 
1283
 
    def test_key_count_reloads_and_fails(self):
1284
 
        # We have deleted all underlying indexes, so we will try to reload, but
1285
 
        # still fail. This is mostly to test we don't get stuck in an infinite
1286
 
        # loop trying to reload
1287
 
        index, reload_counter = self.make_combined_index_with_missing(
1288
 
                                    ['1', '2', '3'])
1289
 
        self.assertRaises(errors.NoSuchFile, index.key_count)
1290
 
        self.assertEqual([2, 1, 1], reload_counter)
1291
 
 
1292
 
    def test_iter_entries_reloads(self):
1293
 
        index, reload_counter = self.make_combined_index_with_missing()
1294
 
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1295
 
        index3 = index._indices[0]
1296
 
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1297
 
                         result)
1298
 
        self.assertEqual([1, 1, 0], reload_counter)
1299
 
 
1300
 
    def test_iter_entries_reloads_midway(self):
1301
 
        # The first index still looks present, so we get interrupted mid-way
1302
 
        # through
1303
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1304
 
        index1, index2 = index._indices
1305
 
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1306
 
        index3 = index._indices[0]
1307
 
        # We had already yielded '1', so we just go on to the next, we should
1308
 
        # not yield '1' twice.
1309
 
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1310
 
                         result)
1311
 
        self.assertEqual([1, 1, 0], reload_counter)
1312
 
 
1313
 
    def test_iter_entries_no_reload(self):
1314
 
        index, reload_counter = self.make_combined_index_with_missing()
1315
 
        index._reload_func = None
1316
 
        # Without a _reload_func we just raise the exception
1317
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1318
 
 
1319
 
    def test_iter_entries_reloads_and_fails(self):
1320
 
        index, reload_counter = self.make_combined_index_with_missing(
1321
 
                                    ['1', '2', '3'])
1322
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1323
 
        self.assertEqual([2, 1, 1], reload_counter)
1324
 
 
1325
 
    def test_iter_all_entries_reloads(self):
1326
 
        index, reload_counter = self.make_combined_index_with_missing()
1327
 
        result = list(index.iter_all_entries())
1328
 
        index3 = index._indices[0]
1329
 
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1330
 
                         result)
1331
 
        self.assertEqual([1, 1, 0], reload_counter)
1332
 
 
1333
 
    def test_iter_all_entries_reloads_midway(self):
1334
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1335
 
        index1, index2 = index._indices
1336
 
        result = list(index.iter_all_entries())
1337
 
        index3 = index._indices[0]
1338
 
        # We had already yielded '1', so we just go on to the next, we should
1339
 
        # not yield '1' twice.
1340
 
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1341
 
                         result)
1342
 
        self.assertEqual([1, 1, 0], reload_counter)
1343
 
 
1344
 
    def test_iter_all_entries_no_reload(self):
1345
 
        index, reload_counter = self.make_combined_index_with_missing()
1346
 
        index._reload_func = None
1347
 
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1348
 
 
1349
 
    def test_iter_all_entries_reloads_and_fails(self):
1350
 
        index, reload_counter = self.make_combined_index_with_missing(
1351
 
                                    ['1', '2', '3'])
1352
 
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1353
 
 
1354
 
    def test_iter_entries_prefix_reloads(self):
1355
 
        index, reload_counter = self.make_combined_index_with_missing()
1356
 
        result = list(index.iter_entries_prefix([('1',)]))
1357
 
        index3 = index._indices[0]
1358
 
        self.assertEqual([(index3, ('1',), '')], result)
1359
 
        self.assertEqual([1, 1, 0], reload_counter)
1360
 
 
1361
 
    def test_iter_entries_prefix_reloads_midway(self):
1362
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1363
 
        index1, index2 = index._indices
1364
 
        result = list(index.iter_entries_prefix([('1',)]))
1365
 
        index3 = index._indices[0]
1366
 
        # We had already yielded '1', so we just go on to the next, we should
1367
 
        # not yield '1' twice.
1368
 
        self.assertEqual([(index1, ('1',), '')], result)
1369
 
        self.assertEqual([1, 1, 0], reload_counter)
1370
 
 
1371
 
    def test_iter_entries_prefix_no_reload(self):
1372
 
        index, reload_counter = self.make_combined_index_with_missing()
1373
 
        index._reload_func = None
1374
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1375
 
                                                 [('1',)])
1376
 
 
1377
 
    def test_iter_entries_prefix_reloads_and_fails(self):
1378
 
        index, reload_counter = self.make_combined_index_with_missing(
1379
 
                                    ['1', '2', '3'])
1380
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1381
 
                                                 [('1',)])
1382
 
 
1383
 
 
1384
 
    def make_index_with_simple_nodes(self, name, num_nodes=1):
1385
 
        """Make an index named after 'name', with keys named after 'name' too.
1386
 
 
1387
 
        Nodes will have a value of '' and no references.
1388
 
        """
1389
 
        nodes = [
1390
 
            (('index-%s-key-%s' % (name, n),), '', ())
1391
 
            for n in range(1, num_nodes+1)]
1392
 
        return self.make_index('index-%s' % name, 0, nodes=nodes)
1393
 
 
1394
 
    def test_reorder_after_iter_entries(self):
1395
 
        # Four indices: [key1] in index1, [key2,key3] in index2, [] in index3,
1396
 
        # [key4] in index4.
1397
 
        index = CombinedGraphIndex([])
1398
 
        index.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
1399
 
        index.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
1400
 
        index.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
1401
 
        index.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
1402
 
        index1, index2, index3, index4 = index._indices
1403
 
        # Query a key from index4 and index2.
1404
 
        self.assertLength(2, list(index.iter_entries(
1405
 
            [('index-4-key-1',), ('index-2-key-1',)])))
1406
 
        # Now index2 and index4 should be moved to the front (and index1 should
1407
 
        # still be before index3).
1408
 
        self.assertEqual([index2, index4, index1, index3], index._indices)
1409
 
        self.assertEqual(['2', '4', '1', '3'], index._index_names)
1410
 
 
1411
 
    def test_reorder_propagates_to_siblings(self):
1412
 
        # Two CombinedGraphIndex objects, with the same number of indicies with
1413
 
        # matching names.
1414
 
        cgi1 = CombinedGraphIndex([])
1415
 
        cgi2 = CombinedGraphIndex([])
1416
 
        cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
1417
 
        cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
1418
 
        cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
1419
 
        cgi2.insert_index(1, self.make_index_with_simple_nodes('2-2'), 'two')
1420
 
        index2_1, index2_2 = cgi2._indices
1421
 
        cgi1.set_sibling_indices([cgi2])
1422
 
        # Trigger a reordering in cgi1.  cgi2 will be reordered as well.
1423
 
        list(cgi1.iter_entries([('index-1-2-key-1',)]))
1424
 
        self.assertEqual([index2_2, index2_1], cgi2._indices)
1425
 
        self.assertEqual(['two', 'one'], cgi2._index_names)
1426
 
 
1427
 
    def test_validate_reloads(self):
1428
 
        index, reload_counter = self.make_combined_index_with_missing()
1429
 
        index.validate()
1430
 
        self.assertEqual([1, 1, 0], reload_counter)
1431
 
 
1432
 
    def test_validate_reloads_midway(self):
1433
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1434
 
        index.validate()
1435
 
 
1436
 
    def test_validate_no_reload(self):
1437
 
        index, reload_counter = self.make_combined_index_with_missing()
1438
 
        index._reload_func = None
1439
 
        self.assertRaises(errors.NoSuchFile, index.validate)
1440
 
 
1441
 
    def test_validate_reloads_and_fails(self):
1442
 
        index, reload_counter = self.make_combined_index_with_missing(
1443
 
                                    ['1', '2', '3'])
1444
 
        self.assertRaises(errors.NoSuchFile, index.validate)
1445
 
 
1446
 
    def test_find_ancestors_across_indexes(self):
1447
 
        key1 = ('key-1',)
1448
 
        key2 = ('key-2',)
1449
 
        key3 = ('key-3',)
1450
 
        key4 = ('key-4',)
1451
 
        index1 = self.make_index('12', ref_lists=1, nodes=[
1452
 
            (key1, 'value', ([],)),
1453
 
            (key2, 'value', ([key1],)),
1454
 
            ])
1455
 
        index2 = self.make_index('34', ref_lists=1, nodes=[
1456
 
            (key3, 'value', ([key2],)),
1457
 
            (key4, 'value', ([key3],)),
1458
 
            ])
1459
 
        c_index = CombinedGraphIndex([index1, index2])
1460
 
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1461
 
        self.assertEqual({key1: ()}, parent_map)
1462
 
        self.assertEqual(set(), missing_keys)
1463
 
        # Now look for a key from index2 which requires us to find the key in
1464
 
        # the second index, and then continue searching for parents in the
1465
 
        # first index
1466
 
        parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1467
 
        self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1468
 
        self.assertEqual(set(), missing_keys)
1469
 
 
1470
 
    def test_find_ancestors_missing_keys(self):
1471
 
        key1 = ('key-1',)
1472
 
        key2 = ('key-2',)
1473
 
        key3 = ('key-3',)
1474
 
        key4 = ('key-4',)
1475
 
        index1 = self.make_index('12', ref_lists=1, nodes=[
1476
 
            (key1, 'value', ([],)),
1477
 
            (key2, 'value', ([key1],)),
1478
 
            ])
1479
 
        index2 = self.make_index('34', ref_lists=1, nodes=[
1480
 
            (key3, 'value', ([key2],)),
1481
 
            ])
1482
 
        c_index = CombinedGraphIndex([index1, index2])
1483
 
        # Searching for a key which is actually not present at all should
1484
 
        # eventually converge
1485
 
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1486
 
        self.assertEqual({}, parent_map)
1487
 
        self.assertEqual(set([key4]), missing_keys)
1488
 
 
1489
 
    def test_find_ancestors_no_indexes(self):
1490
 
        c_index = CombinedGraphIndex([])
1491
 
        key1 = ('key-1',)
1492
 
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1493
 
        self.assertEqual({}, parent_map)
1494
 
        self.assertEqual(set([key1]), missing_keys)
1495
 
 
1496
 
    def test_find_ancestors_ghost_parent(self):
1497
 
        key1 = ('key-1',)
1498
 
        key2 = ('key-2',)
1499
 
        key3 = ('key-3',)
1500
 
        key4 = ('key-4',)
1501
 
        index1 = self.make_index('12', ref_lists=1, nodes=[
1502
 
            (key1, 'value', ([],)),
1503
 
            (key2, 'value', ([key1],)),
1504
 
            ])
1505
 
        index2 = self.make_index('34', ref_lists=1, nodes=[
1506
 
            (key4, 'value', ([key2, key3],)),
1507
 
            ])
1508
 
        c_index = CombinedGraphIndex([index1, index2])
1509
 
        # Searching for a key which is actually not present at all should
1510
 
        # eventually converge
1511
 
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1512
 
        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1513
 
                         parent_map)
1514
 
        self.assertEqual(set([key3]), missing_keys)
1515
 
 
1516
 
    def test__find_ancestors_empty_index(self):
1517
 
        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1518
 
        parent_map = {}
1519
 
        missing_keys = set()
1520
 
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1521
 
                                            missing_keys)
1522
 
        self.assertEqual(set(), search_keys)
1523
 
        self.assertEqual({}, parent_map)
1524
 
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1525
 
 
1526
688
 
1527
689
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1528
690