/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: John Arbash Meinel
  • Date: 2008-07-09 21:42:24 UTC
  • mto: This revision was merged to the branch mainline in revision 3543.
  • Revision ID: john@arbash-meinel.com-20080709214224-r75k87r6a01pfc3h
Restore a real weave merge to 'bzr merge --weave'.

To do so efficiently, we only add the simple LCAs to the final weave
object, unless we run into complexities with the merge graph.
This gives the same effective result as adding all the texts,
with the advantage of not having to extract all of them.

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
 
173
173
            "key\x00\x00\t\x00data\n"
174
174
            "\n", contents)
175
175
 
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
176
    def test_node_references_are_byte_offsets(self):
182
177
        builder = GraphIndexBuilder(reference_lists=1)
183
178
        builder.add_node(('reference', ), 'data', ([], ))
235
230
        builder.add_node(('2-key', ), '', (references, ))
236
231
        stream = builder.finish()
237
232
        contents = stream.read()
238
 
        self.assertEqualDiff(
 
233
        self.assertEqual(
239
234
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
240
235
            "0\x00a\x00\x00\n"
241
236
            "1\x00a\x00\x00\n"
355
350
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
356
351
        builder.add_node(('reference', 'tokey'), 'data', ([],))
357
352
 
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
353
 
366
354
class TestGraphIndex(TestCaseWithMemoryTransport):
367
355
 
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
356
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
383
357
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
384
358
        for key, value, references in nodes:
388
362
        size = trans.put_file('index', stream)
389
363
        return GraphIndex(trans, 'index', size)
390
364
 
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
 
        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()
407
 
 
408
365
    def test_open_bad_index_no_error(self):
409
366
        trans = self.get_transport()
410
367
        trans.put_bytes('name', "not an index\n")
411
368
        index = GraphIndex(trans, 'name', 13)
412
369
 
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
370
    def test_open_sets_parsed_map_empty(self):
434
371
        index = self.make_index()
435
372
        self.assertEqual([], index._parsed_byte_map)
436
373
        self.assertEqual([], index._parsed_key_map)
437
374
 
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):
 
375
    def test_first_lookup_key_via_location(self):
453
376
        index = self.make_index()
454
377
        # reset the transport log
455
378
        del index._transport._activity[:]
467
390
        # is a trivial index.
468
391
        self.assertEqual([((index._size // 2, ('missing', )), False)],
469
392
            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)
 
393
        # And the regions of the file that have been parsed - in this case the
 
394
        # entire file - should be in the parsed region map.
 
395
        self.assertEqual([(0, 60)], index._parsed_byte_map)
 
396
        self.assertEqual([(None, None)], index._parsed_key_map)
473
397
 
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))
 
398
    def test_parsing_parses_data_adjacent_to_parsed_regions(self):
 
399
        # we trim data we recieve to remove the first and trailing
 
400
        # partial lines, except when they start at the end/finish at the start
 
401
        # of a region we've alread parsed/ the end of the file. The trivial
 
402
        # test for this is an index with 1 key.
 
403
        index = self.make_index(nodes=[(('name', ), 'data', ())])
483
404
        # reset the transport log
484
405
        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
406
        result = index._lookup_keys_via_location(
489
 
            [(start_lookup, ('40missing', ))])
 
407
            [(index._size // 2, ('missing', ))])
490
408
        # this should have asked for a readv request, with adjust_for_latency,
491
409
        # and two regions: the header, and half-way into the file.
492
410
        self.assertEqual([
493
 
            ('readv', 'index',
494
 
             [(start_lookup, 800), (0, 200)], True, index._size),
 
411
            ('readv', 'index', [(36, 36), (0, 200)], True, 72),
495
412
            ],
496
413
            index._transport._activity)
497
414
        # 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)],
 
415
        # is a trivial index and we should not have to do more round trips.
 
416
        self.assertEqual([((index._size // 2, ('missing', )), False)],
500
417
            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)
 
418
        # The whole file should be parsed at this point.
 
419
        self.assertEqual([(0, 72)], index._parsed_byte_map)
 
420
        self.assertEqual([(None, ('name',))], index._parsed_key_map)
509
421
 
510
422
    def test_parsing_non_adjacent_data_trims(self):
511
 
        index = self.make_index(nodes=self.make_nodes(64))
 
423
        # generate a big enough index that we only read some of it on a typical
 
424
        # bisection lookup.
 
425
        nodes = []
 
426
        def make_key(number):
 
427
            return (str(number) + 'X'*100,)
 
428
        for counter in range(64):
 
429
            nodes.append((make_key(counter), 'Y'*100, ()))
 
430
        index = self.make_index(nodes=nodes)
512
431
        result = index._lookup_keys_via_location(
513
432
            [(index._size // 2, ('40', ))])
514
433
        # and the result should be that the key cannot be present, because key is
518
437
            result)
519
438
        # and we should have a parse map that includes the header and the
520
439
        # 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))],
 
440
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
441
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
524
442
            index._parsed_key_map)
525
443
 
526
444
    def test_parsing_data_handles_parsed_contained_regions(self):
530
448
        # which then trims the start and end so the parsed size is < readv
531
449
        # miniumum.
532
450
        # 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
 
451
        # abuts or overlaps the parsed region on both sides will need to 
534
452
        # discard the data in the middle, but parse the end as well.
535
453
        #
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 -
 
454
        # we test this by doing a single lookup to seed the data, then 
 
455
        # a lookup for two keys that are present, and adjacent - 
538
456
        # we except both to be found, and the parsed byte map to include the
539
457
        # locations of both keys.
540
 
        index = self.make_index(nodes=self.make_nodes(128))
 
458
        nodes = []
 
459
        def make_key(number):
 
460
            return (str(number) + 'X'*100,)
 
461
        def make_value(number):
 
462
            return 'Y'*100
 
463
        for counter in range(128):
 
464
            nodes.append((make_key(counter), make_value(counter), ()))
 
465
        index = self.make_index(nodes=nodes)
541
466
        result = index._lookup_keys_via_location(
542
467
            [(index._size // 2, ('40', ))])
543
468
        # and we should have a parse map that includes the header and the
544
469
        # 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))],
 
470
        self.assertEqual([(0, 3991), (11622, 15534)], index._parsed_byte_map)
 
471
        self.assertEqual([(None, make_key(116)), (make_key(35), make_key(51))],
548
472
            index._parsed_key_map)
549
473
        # now ask for two keys, right before and after the parsed region
550
474
        result = index._lookup_keys_via_location(
551
 
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
 
475
            [(11450, make_key(34)), (15534, make_key(52))])
552
476
        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))),
 
477
            ((11450, make_key(34)), (index, make_key(34), make_value(34))),
 
478
            ((15534, make_key(52)), (index, make_key(52), make_value(52))),
557
479
            ],
558
480
            result)
559
 
        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
 
481
        self.assertEqual([(0, 3991), (9975, 17799)], index._parsed_byte_map)
560
482
 
561
483
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
562
484
        # generate a big enough index that we only read some of it on a typical
563
485
        # bisection lookup.
564
 
        index = self.make_index(nodes=self.make_nodes(64))
 
486
        nodes = []
 
487
        def make_key(number):
 
488
            return (str(number) + 'X'*100,)
 
489
        for counter in range(64):
 
490
            nodes.append((make_key(counter), 'Y'*100, ()))
 
491
        index = self.make_index(nodes=nodes)
565
492
        # lookup the keys in the middle of the file
566
493
        result =index._lookup_keys_via_location(
567
494
            [(index._size // 2, ('40', ))])
568
495
        # 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))],
 
496
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
497
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
572
498
            index._parsed_key_map)
573
499
        # reset the transport log
574
500
        del index._transport._activity[:]
576
502
        # not create a new transport request, and should return False (cannot
577
503
        # be in the index) - even when the byte location we ask for is outside
578
504
        # the parsed region
 
505
        # 
579
506
        result = index._lookup_keys_via_location(
580
507
            [(4000, ('40', ))])
581
508
        self.assertEqual([((4000, ('40', )), False)],
585
512
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
586
513
        # generate a big enough index that we only read some of it on a typical
587
514
        # bisection lookup.
588
 
        index = self.make_index(nodes=self.make_nodes(64))
 
515
        nodes = []
 
516
        def make_key(number):
 
517
            return (str(number) + 'X'*100,)
 
518
        def make_value(number):
 
519
            return str(number) + 'Y'*100
 
520
        for counter in range(64):
 
521
            nodes.append((make_key(counter), make_value(counter), ()))
 
522
        index = self.make_index(nodes=nodes)
589
523
        # lookup the keys in the middle of the file
590
524
        result =index._lookup_keys_via_location(
591
525
            [(index._size // 2, ('40', ))])
592
526
        # check the parse map, this determines the test validity
593
527
        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))],
 
528
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
596
529
            index._parsed_key_map)
597
530
        # reset the transport log
598
531
        del index._transport._activity[:]
600
533
        # not create a new transport request, and should return False (cannot
601
534
        # be in the index) - even when the byte location we ask for is outside
602
535
        # the parsed region
603
 
        #
604
 
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
 
536
        # 
 
537
        result = index._lookup_keys_via_location([(4000, make_key(40))])
605
538
        self.assertEqual(
606
 
            [((4000, self.make_key(40)),
607
 
              (index, self.make_key(40), self.make_value(40)))],
 
539
            [((4000, make_key(40)), (index, make_key(40), make_value(40)))],
608
540
            result)
609
541
        self.assertEqual([], index._transport._activity)
610
542
 
611
543
    def test_lookup_key_below_probed_area(self):
612
544
        # generate a big enough index that we only read some of it on a typical
613
545
        # bisection lookup.
614
 
        index = self.make_index(nodes=self.make_nodes(64))
 
546
        nodes = []
 
547
        def make_key(number):
 
548
            return (str(number) + 'X'*100,)
 
549
        for counter in range(64):
 
550
            nodes.append((make_key(counter), 'Y'*100, ()))
 
551
        index = self.make_index(nodes=nodes)
615
552
        # ask for the key in the middle, but a key that is located in the
616
553
        # unparsed region before the middle.
617
554
        result =index._lookup_keys_via_location(
618
555
            [(index._size // 2, ('30', ))])
619
556
        # 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))],
 
557
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
558
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
623
559
            index._parsed_key_map)
624
560
        self.assertEqual([((index._size // 2, ('30', )), -1)],
625
561
            result)
627
563
    def test_lookup_key_above_probed_area(self):
628
564
        # generate a big enough index that we only read some of it on a typical
629
565
        # bisection lookup.
630
 
        index = self.make_index(nodes=self.make_nodes(64))
 
566
        nodes = []
 
567
        def make_key(number):
 
568
            return (str(number) + 'X'*100,)
 
569
        for counter in range(64):
 
570
            nodes.append((make_key(counter), 'Y'*100, ()))
 
571
        index = self.make_index(nodes=nodes)
631
572
        # ask for the key in the middle, but a key that is located in the
632
573
        # unparsed region after the middle.
633
574
        result =index._lookup_keys_via_location(
634
575
            [(index._size // 2, ('50', ))])
635
576
        # 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))],
 
577
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
578
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
639
579
            index._parsed_key_map)
640
580
        self.assertEqual([((index._size // 2, ('50', )), +1)],
641
581
            result)
644
584
        # generate a big enough index that we only read some of it on a typical
645
585
        # bisection lookup.
646
586
        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 = []
 
587
        def make_key(number):
 
588
            return (str(number) + 'X'*100,)
 
589
        def make_value(number):
 
590
            return str(number) + 'Y'*100
683
591
        for counter in range(64):
684
 
            nodes.append((self.make_key(counter), self.make_value(counter),
685
 
                ((self.make_key(counter + 20),),)  ))
 
592
            nodes.append((make_key(counter), make_value(counter),
 
593
                ((make_key(counter + 20),),)  ))
686
594
        index = self.make_index(ref_lists=1, nodes=nodes)
687
595
        # lookup a key in the middle that does not exist, so that when we can
688
596
        # 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', ))])
 
597
        result =index._lookup_keys_via_location(
 
598
            [(index._size // 2, ('40', ))])
692
599
        # check the parse map - only the start and middle should have been
693
600
        # parsed.
694
601
        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))],
 
602
        self.assertEqual([(None, make_key(25)), (make_key(37), make_key(52))],
697
603
            index._parsed_key_map)
698
604
        # and check the transport activity likewise.
699
605
        self.assertEqual(
700
 
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
701
 
                                  index_size)],
 
606
            [('readv', 'index', [(7906, 800), (0, 200)], True, 15813)],
702
607
            index._transport._activity)
703
608
        # reset the transport log for testing the reference lookup
704
609
        del index._transport._activity[:]
705
610
        # now looking up a key in the portion of the file already parsed should
706
611
        # only perform IO to resolve its key references.
707
 
        result = index._lookup_keys_via_location([(7000, self.make_key(40))])
 
612
        result = index._lookup_keys_via_location([(4000, make_key(40))])
708
613
        self.assertEqual(
709
 
            [((7000, self.make_key(40)),
710
 
              (index, self.make_key(40), self.make_value(40),
711
 
               ((self.make_key(60),),)))],
 
614
            [((4000, make_key(40)),
 
615
              (index, make_key(40), make_value(40), ((make_key(60),),)))],
712
616
            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)
 
617
        self.assertEqual([('readv', 'index', [(11976, 800)], True, 15813)],
 
618
            index._transport._activity)
716
619
 
717
620
    def test_iter_all_entries_empty(self):
718
621
        index = self.make_index()
737
640
            (index, ('ref', ), 'refdata', ((), ))]),
738
641
            set(index.iter_all_entries()))
739
642
 
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
643
    def test_iter_entries_references_resolved(self):
783
644
        index = self.make_index(1, nodes=[
784
645
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
902
763
            (('name', ), '', ()), (('foo', ), '', ())])
903
764
        self.assertEqual(2, index.key_count())
904
765
 
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
766
    def test_validate_bad_index_errors(self):
929
767
        trans = self.get_transport()
930
768
        trans.put_bytes('name', "not an index\n")
964
802
        index = self.make_index(nodes=[(('key', ), 'value', ())])
965
803
        index.validate()
966
804
 
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
805
 
1061
806
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1062
807
 
1069
814
        size = trans.put_file(name, stream)
1070
815
        return GraphIndex(trans, name, size)
1071
816
 
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
1104
 
 
1105
817
    def test_open_missing_index_no_error(self):
1106
818
        trans = self.get_transport()
1107
819
        index1 = GraphIndex(trans, 'missing', 100)
1113
825
        index.insert_index(0, index1)
1114
826
        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1115
827
 
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
828
    def test_iter_all_entries_empty(self):
1141
829
        index = CombinedGraphIndex([])
1142
830
        self.assertEqual([], list(index.iter_all_entries()))
1206
894
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1207
895
            (index2, ('ref', ), 'refdata', ((), ))]),
1208
896
            set(index.iter_entries([('name', ), ('ref', )])))
1209
 
 
 
897
 
1210
898
    def test_iter_all_keys_dup_entry(self):
1211
899
        index1 = self.make_index('1', 1, nodes=[
1212
900
            (('name', ), 'data', ([('ref', )], )),
1217
905
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1218
906
            (index1, ('ref', ), 'refdata', ((), ))]),
1219
907
            set(index.iter_entries([('name', ), ('ref', )])))
1220
 
 
 
908
 
1221
909
    def test_iter_missing_entry_empty(self):
1222
910
        index = CombinedGraphIndex([])
1223
911
        self.assertEqual([], list(index.iter_entries([('a', )])))
1232
920
        index2 = self.make_index('2')
1233
921
        index = CombinedGraphIndex([index1, index2])
1234
922
        self.assertEqual([], list(index.iter_entries([('a', )])))
1235
 
 
 
923
 
1236
924
    def test_iter_entry_present_one_index_only(self):
1237
925
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1238
926
        index2 = self.make_index('2', nodes=[])
1269
957
        index = CombinedGraphIndex([])
1270
958
        index.validate()
1271
959
 
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
960
 
1527
961
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1528
962