← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

  • Committer: Ian Clatworthy
  • Date: 2008-03-27 07:51:10 UTC
  • mto: (3311.1.1 ianc-integration)
  • mto: This revision was merged to the branch mainline in revision 3312.
  • Revision ID: ian.clatworthy@canonical.com-20080327075110-afgd7x03ybju06ez
Reduce evangelism in the User Guide

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