/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

  • Committer: Martin Pool
  • Date: 2009-12-14 06:06:59 UTC
  • mfrom: (4889 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4891.
  • Revision ID: mbp@sourcefrog.net-20091214060659-1ucv8hpnky0cbnaj
merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007, 2009 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""Tests for indices."""
18
18
 
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
 
176
181
    def test_node_references_are_byte_offsets(self):
177
182
        builder = GraphIndexBuilder(reference_lists=1)
178
183
        builder.add_node(('reference', ), 'data', ([], ))
230
235
        builder.add_node(('2-key', ), '', (references, ))
231
236
        stream = builder.finish()
232
237
        contents = stream.read()
233
 
        self.assertEqual(
 
238
        self.assertEqualDiff(
234
239
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
235
240
            "0\x00a\x00\x00\n"
236
241
            "1\x00a\x00\x00\n"
350
355
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
351
356
        builder.add_node(('reference', 'tokey'), 'data', ([],))
352
357
 
 
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
 
353
365
 
354
366
class TestGraphIndex(TestCaseWithMemoryTransport):
355
367
 
 
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
 
356
382
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
357
383
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
358
384
        for key, value, references in nodes:
362
388
        size = trans.put_file('index', stream)
363
389
        return GraphIndex(trans, 'index', size)
364
390
 
 
391
    def test_clear_cache(self):
 
392
        index = self.make_index()
 
393
        # For now, we just want to make sure the api is available. As this is
 
394
        # old code, we don't really worry if it *does* anything.
 
395
        index.clear_cache()
 
396
 
365
397
    def test_open_bad_index_no_error(self):
366
398
        trans = self.get_transport()
367
399
        trans.put_bytes('name', "not an index\n")
372
404
        self.assertEqual([], index._parsed_byte_map)
373
405
        self.assertEqual([], index._parsed_key_map)
374
406
 
 
407
    def test_key_count_buffers(self):
 
408
        index = self.make_index(nodes=self.make_nodes(2))
 
409
        # reset the transport log
 
410
        del index._transport._activity[:]
 
411
        self.assertEqual(2, index.key_count())
 
412
        # We should have requested reading the header bytes
 
413
        self.assertEqual([
 
414
            ('readv', 'index', [(0, 200)], True, index._size),
 
415
            ],
 
416
            index._transport._activity)
 
417
        # And that should have been enough to trigger reading the whole index
 
418
        # with buffering
 
419
        self.assertIsNot(None, index._nodes)
 
420
 
 
421
    def test_lookup_key_via_location_buffers(self):
 
422
        index = self.make_index()
 
423
        # reset the transport log
 
424
        del index._transport._activity[:]
 
425
        # do a _lookup_keys_via_location call for the middle of the file, which
 
426
        # is what bisection uses.
 
427
        result = index._lookup_keys_via_location(
 
428
            [(index._size // 2, ('missing', ))])
 
429
        # this should have asked for a readv request, with adjust_for_latency,
 
430
        # and two regions: the header, and half-way into the file.
 
431
        self.assertEqual([
 
432
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
 
433
            ],
 
434
            index._transport._activity)
 
435
        # and the result should be that the key cannot be present, because this
 
436
        # is a trivial index.
 
437
        self.assertEqual([((index._size // 2, ('missing', )), False)],
 
438
            result)
 
439
        # And this should have caused the file to be fully buffered
 
440
        self.assertIsNot(None, index._nodes)
 
441
        self.assertEqual([], index._parsed_byte_map)
 
442
 
375
443
    def test_first_lookup_key_via_location(self):
376
 
        index = self.make_index()
 
444
        # We need enough data so that the _HEADER_READV doesn't consume the
 
445
        # whole file. We always read 800 bytes for every key, and the local
 
446
        # transport natural expansion is 4096 bytes. So we have to have >8192
 
447
        # bytes or we will trigger "buffer_all".
 
448
        # We also want the 'missing' key to fall within the range that *did*
 
449
        # read
 
450
        nodes = []
 
451
        index = self.make_index(nodes=self.make_nodes(64))
377
452
        # reset the transport log
378
453
        del index._transport._activity[:]
379
454
        # do a _lookup_keys_via_location call for the middle of the file, which
380
455
        # is what bisection uses.
 
456
        start_lookup = index._size // 2
381
457
        result = index._lookup_keys_via_location(
382
 
            [(index._size // 2, ('missing', ))])
 
458
            [(start_lookup, ('40missing', ))])
383
459
        # this should have asked for a readv request, with adjust_for_latency,
384
460
        # and two regions: the header, and half-way into the file.
385
461
        self.assertEqual([
386
 
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
 
462
            ('readv', 'index',
 
463
             [(start_lookup, 800), (0, 200)], True, index._size),
387
464
            ],
388
465
            index._transport._activity)
389
466
        # and the result should be that the key cannot be present, because this
390
467
        # is a trivial index.
391
 
        self.assertEqual([((index._size // 2, ('missing', )), False)],
392
 
            result)
393
 
        # And the regions of the file that have been parsed - in this case the
394
 
        # entire file - should be in the parsed region map.
395
 
        self.assertEqual([(0, 60)], index._parsed_byte_map)
396
 
        self.assertEqual([(None, None)], index._parsed_key_map)
397
 
 
398
 
    def test_parsing_parses_data_adjacent_to_parsed_regions(self):
399
 
        # we trim data we recieve to remove the first and trailing
400
 
        # partial lines, except when they start at the end/finish at the start
401
 
        # of a region we've alread parsed/ the end of the file. The trivial
402
 
        # test for this is an index with 1 key.
403
 
        index = self.make_index(nodes=[(('name', ), 'data', ())])
404
 
        # reset the transport log
405
 
        del index._transport._activity[:]
406
 
        result = index._lookup_keys_via_location(
407
 
            [(index._size // 2, ('missing', ))])
408
 
        # this should have asked for a readv request, with adjust_for_latency,
409
 
        # and two regions: the header, and half-way into the file.
410
 
        self.assertEqual([
411
 
            ('readv', 'index', [(36, 36), (0, 200)], True, 72),
412
 
            ],
413
 
            index._transport._activity)
414
 
        # and the result should be that the key cannot be present, because this
415
 
        # is a trivial index and we should not have to do more round trips.
416
 
        self.assertEqual([((index._size // 2, ('missing', )), False)],
417
 
            result)
418
 
        # The whole file should be parsed at this point.
419
 
        self.assertEqual([(0, 72)], index._parsed_byte_map)
420
 
        self.assertEqual([(None, ('name',))], index._parsed_key_map)
 
468
        self.assertEqual([((start_lookup, ('40missing', )), False)],
 
469
            result)
 
470
        # And this should not have caused the file to be fully buffered
 
471
        self.assertIs(None, index._nodes)
 
472
        # And the regions of the file that have been parsed should be in the
 
473
        # parsed_byte_map and the parsed_key_map
 
474
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
475
        self.assertEqual([(None, self.make_key(26)),
 
476
                          (self.make_key(31), self.make_key(48))],
 
477
                         index._parsed_key_map)
421
478
 
422
479
    def test_parsing_non_adjacent_data_trims(self):
423
 
        # generate a big enough index that we only read some of it on a typical
424
 
        # bisection lookup.
425
 
        nodes = []
426
 
        def make_key(number):
427
 
            return (str(number) + 'X'*100,)
428
 
        for counter in range(64):
429
 
            nodes.append((make_key(counter), 'Y'*100, ()))
430
 
        index = self.make_index(nodes=nodes)
 
480
        index = self.make_index(nodes=self.make_nodes(64))
431
481
        result = index._lookup_keys_via_location(
432
482
            [(index._size // 2, ('40', ))])
433
483
        # and the result should be that the key cannot be present, because key is
437
487
            result)
438
488
        # and we should have a parse map that includes the header and the
439
489
        # region that was parsed after trimming.
440
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
441
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
490
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
491
        self.assertEqual([(None, self.make_key(26)),
 
492
                          (self.make_key(31), self.make_key(48))],
442
493
            index._parsed_key_map)
443
494
 
444
495
    def test_parsing_data_handles_parsed_contained_regions(self):
448
499
        # which then trims the start and end so the parsed size is < readv
449
500
        # miniumum.
450
501
        # then a dual lookup (or a reference lookup for that matter) which
451
 
        # abuts or overlaps the parsed region on both sides will need to 
 
502
        # abuts or overlaps the parsed region on both sides will need to
452
503
        # discard the data in the middle, but parse the end as well.
453
504
        #
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 - 
 
505
        # we test this by doing a single lookup to seed the data, then
 
506
        # a lookup for two keys that are present, and adjacent -
456
507
        # we except both to be found, and the parsed byte map to include the
457
508
        # locations of both keys.
458
 
        nodes = []
459
 
        def make_key(number):
460
 
            return (str(number) + 'X'*100,)
461
 
        def make_value(number):
462
 
            return 'Y'*100
463
 
        for counter in range(128):
464
 
            nodes.append((make_key(counter), make_value(counter), ()))
465
 
        index = self.make_index(nodes=nodes)
 
509
        index = self.make_index(nodes=self.make_nodes(128))
466
510
        result = index._lookup_keys_via_location(
467
511
            [(index._size // 2, ('40', ))])
468
512
        # and we should have a parse map that includes the header and the
469
513
        # region that was parsed after trimming.
470
 
        self.assertEqual([(0, 3991), (11622, 15534)], index._parsed_byte_map)
471
 
        self.assertEqual([(None, make_key(116)), (make_key(35), make_key(51))],
 
514
        self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
 
515
        self.assertEqual([(None, self.make_key(116)),
 
516
                          (self.make_key(35), self.make_key(51))],
472
517
            index._parsed_key_map)
473
518
        # now ask for two keys, right before and after the parsed region
474
519
        result = index._lookup_keys_via_location(
475
 
            [(11450, make_key(34)), (15534, make_key(52))])
 
520
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
476
521
        self.assertEqual([
477
 
            ((11450, make_key(34)), (index, make_key(34), make_value(34))),
478
 
            ((15534, make_key(52)), (index, make_key(52), make_value(52))),
 
522
            ((11450, self.make_key(34)),
 
523
             (index, self.make_key(34), self.make_value(34))),
 
524
            ((15707, self.make_key(52)),
 
525
             (index, self.make_key(52), self.make_value(52))),
479
526
            ],
480
527
            result)
481
 
        self.assertEqual([(0, 3991), (9975, 17799)], index._parsed_byte_map)
 
528
        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
482
529
 
483
530
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
484
531
        # generate a big enough index that we only read some of it on a typical
485
532
        # bisection lookup.
486
 
        nodes = []
487
 
        def make_key(number):
488
 
            return (str(number) + 'X'*100,)
489
 
        for counter in range(64):
490
 
            nodes.append((make_key(counter), 'Y'*100, ()))
491
 
        index = self.make_index(nodes=nodes)
 
533
        index = self.make_index(nodes=self.make_nodes(64))
492
534
        # lookup the keys in the middle of the file
493
535
        result =index._lookup_keys_via_location(
494
536
            [(index._size // 2, ('40', ))])
495
537
        # check the parse map, this determines the test validity
496
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
497
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
538
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
539
        self.assertEqual([(None, self.make_key(26)),
 
540
                          (self.make_key(31), self.make_key(48))],
498
541
            index._parsed_key_map)
499
542
        # reset the transport log
500
543
        del index._transport._activity[:]
502
545
        # not create a new transport request, and should return False (cannot
503
546
        # be in the index) - even when the byte location we ask for is outside
504
547
        # the parsed region
505
 
        # 
506
548
        result = index._lookup_keys_via_location(
507
549
            [(4000, ('40', ))])
508
550
        self.assertEqual([((4000, ('40', )), False)],
512
554
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
513
555
        # generate a big enough index that we only read some of it on a typical
514
556
        # bisection lookup.
515
 
        nodes = []
516
 
        def make_key(number):
517
 
            return (str(number) + 'X'*100,)
518
 
        def make_value(number):
519
 
            return str(number) + 'Y'*100
520
 
        for counter in range(64):
521
 
            nodes.append((make_key(counter), make_value(counter), ()))
522
 
        index = self.make_index(nodes=nodes)
 
557
        index = self.make_index(nodes=self.make_nodes(64))
523
558
        # lookup the keys in the middle of the file
524
559
        result =index._lookup_keys_via_location(
525
560
            [(index._size // 2, ('40', ))])
526
561
        # check the parse map, this determines the test validity
527
562
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
528
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
563
        self.assertEqual([(None, self.make_key(26)),
 
564
                          (self.make_key(31), self.make_key(48))],
529
565
            index._parsed_key_map)
530
566
        # reset the transport log
531
567
        del index._transport._activity[:]
533
569
        # not create a new transport request, and should return False (cannot
534
570
        # be in the index) - even when the byte location we ask for is outside
535
571
        # the parsed region
536
 
        # 
537
 
        result = index._lookup_keys_via_location([(4000, make_key(40))])
 
572
        #
 
573
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
538
574
        self.assertEqual(
539
 
            [((4000, make_key(40)), (index, make_key(40), make_value(40)))],
 
575
            [((4000, self.make_key(40)),
 
576
              (index, self.make_key(40), self.make_value(40)))],
540
577
            result)
541
578
        self.assertEqual([], index._transport._activity)
542
579
 
543
580
    def test_lookup_key_below_probed_area(self):
544
581
        # generate a big enough index that we only read some of it on a typical
545
582
        # bisection lookup.
546
 
        nodes = []
547
 
        def make_key(number):
548
 
            return (str(number) + 'X'*100,)
549
 
        for counter in range(64):
550
 
            nodes.append((make_key(counter), 'Y'*100, ()))
551
 
        index = self.make_index(nodes=nodes)
 
583
        index = self.make_index(nodes=self.make_nodes(64))
552
584
        # ask for the key in the middle, but a key that is located in the
553
585
        # unparsed region before the middle.
554
586
        result =index._lookup_keys_via_location(
555
587
            [(index._size // 2, ('30', ))])
556
588
        # check the parse map, this determines the test validity
557
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
558
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
589
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
590
        self.assertEqual([(None, self.make_key(26)),
 
591
                          (self.make_key(31), self.make_key(48))],
559
592
            index._parsed_key_map)
560
593
        self.assertEqual([((index._size // 2, ('30', )), -1)],
561
594
            result)
563
596
    def test_lookup_key_above_probed_area(self):
564
597
        # generate a big enough index that we only read some of it on a typical
565
598
        # bisection lookup.
566
 
        nodes = []
567
 
        def make_key(number):
568
 
            return (str(number) + 'X'*100,)
569
 
        for counter in range(64):
570
 
            nodes.append((make_key(counter), 'Y'*100, ()))
571
 
        index = self.make_index(nodes=nodes)
 
599
        index = self.make_index(nodes=self.make_nodes(64))
572
600
        # ask for the key in the middle, but a key that is located in the
573
601
        # unparsed region after the middle.
574
602
        result =index._lookup_keys_via_location(
575
603
            [(index._size // 2, ('50', ))])
576
604
        # check the parse map, this determines the test validity
577
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
578
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
605
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
 
606
        self.assertEqual([(None, self.make_key(26)),
 
607
                          (self.make_key(31), self.make_key(48))],
579
608
            index._parsed_key_map)
580
609
        self.assertEqual([((index._size // 2, ('50', )), +1)],
581
610
            result)
584
613
        # generate a big enough index that we only read some of it on a typical
585
614
        # bisection lookup.
586
615
        nodes = []
587
 
        def make_key(number):
588
 
            return (str(number) + 'X'*100,)
589
 
        def make_value(number):
590
 
            return str(number) + 'Y'*100
 
616
        for counter in range(99):
 
617
            nodes.append((self.make_key(counter), self.make_value(counter),
 
618
                ((self.make_key(counter + 20),),)  ))
 
619
        index = self.make_index(ref_lists=1, nodes=nodes)
 
620
        # lookup a key in the middle that does not exist, so that when we can
 
621
        # check that the referred-to-keys are not accessed automatically.
 
622
        index_size = index._size
 
623
        index_center = index_size // 2
 
624
        result = index._lookup_keys_via_location(
 
625
            [(index_center, ('40', ))])
 
626
        # check the parse map - only the start and middle should have been
 
627
        # parsed.
 
628
        self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
 
629
        self.assertEqual([(None, self.make_key(17)),
 
630
                          (self.make_key(44), self.make_key(5))],
 
631
            index._parsed_key_map)
 
632
        # and check the transport activity likewise.
 
633
        self.assertEqual(
 
634
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
 
635
                                  index_size)],
 
636
            index._transport._activity)
 
637
        # reset the transport log for testing the reference lookup
 
638
        del index._transport._activity[:]
 
639
        # now looking up a key in the portion of the file already parsed should
 
640
        # only perform IO to resolve its key references.
 
641
        result = index._lookup_keys_via_location([(11000, self.make_key(45))])
 
642
        self.assertEqual(
 
643
            [((11000, self.make_key(45)),
 
644
              (index, self.make_key(45), self.make_value(45),
 
645
               ((self.make_key(65),),)))],
 
646
            result)
 
647
        self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
 
648
            index._transport._activity)
 
649
 
 
650
    def test_lookup_key_can_buffer_all(self):
 
651
        nodes = []
591
652
        for counter in range(64):
592
 
            nodes.append((make_key(counter), make_value(counter),
593
 
                ((make_key(counter + 20),),)  ))
 
653
            nodes.append((self.make_key(counter), self.make_value(counter),
 
654
                ((self.make_key(counter + 20),),)  ))
594
655
        index = self.make_index(ref_lists=1, nodes=nodes)
595
656
        # lookup a key in the middle that does not exist, so that when we can
596
657
        # check that the referred-to-keys are not accessed automatically.
597
 
        result =index._lookup_keys_via_location(
598
 
            [(index._size // 2, ('40', ))])
 
658
        index_size = index._size
 
659
        index_center = index_size // 2
 
660
        result = index._lookup_keys_via_location([(index_center, ('40', ))])
599
661
        # check the parse map - only the start and middle should have been
600
662
        # parsed.
601
663
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
602
 
        self.assertEqual([(None, make_key(25)), (make_key(37), make_key(52))],
 
664
        self.assertEqual([(None, self.make_key(25)),
 
665
                          (self.make_key(37), self.make_key(52))],
603
666
            index._parsed_key_map)
604
667
        # and check the transport activity likewise.
605
668
        self.assertEqual(
606
 
            [('readv', 'index', [(7906, 800), (0, 200)], True, 15813)],
 
669
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
 
670
                                  index_size)],
607
671
            index._transport._activity)
608
672
        # reset the transport log for testing the reference lookup
609
673
        del index._transport._activity[:]
610
674
        # now looking up a key in the portion of the file already parsed should
611
675
        # only perform IO to resolve its key references.
612
 
        result = index._lookup_keys_via_location([(4000, make_key(40))])
 
676
        result = index._lookup_keys_via_location([(7000, self.make_key(40))])
613
677
        self.assertEqual(
614
 
            [((4000, make_key(40)),
615
 
              (index, make_key(40), make_value(40), ((make_key(60),),)))],
 
678
            [((7000, self.make_key(40)),
 
679
              (index, self.make_key(40), self.make_value(40),
 
680
               ((self.make_key(60),),)))],
616
681
            result)
617
 
        self.assertEqual([('readv', 'index', [(11976, 800)], True, 15813)],
618
 
            index._transport._activity)
 
682
        # Resolving the references would have required more data read, and we
 
683
        # are already above the 50% threshold, so it triggered a _buffer_all
 
684
        self.assertEqual([('get', 'index')], index._transport._activity)
619
685
 
620
686
    def test_iter_all_entries_empty(self):
621
687
        index = self.make_index()
640
706
            (index, ('ref', ), 'refdata', ((), ))]),
641
707
            set(index.iter_all_entries()))
642
708
 
 
709
    def test_iter_entries_buffers_once(self):
 
710
        index = self.make_index(nodes=self.make_nodes(2))
 
711
        # reset the transport log
 
712
        del index._transport._activity[:]
 
713
        self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
 
714
                         set(index.iter_entries([self.make_key(1)])))
 
715
        # We should have requested reading the header bytes
 
716
        # But not needed any more than that because it would have triggered a
 
717
        # buffer all
 
718
        self.assertEqual([
 
719
            ('readv', 'index', [(0, 200)], True, index._size),
 
720
            ],
 
721
            index._transport._activity)
 
722
        # And that should have been enough to trigger reading the whole index
 
723
        # with buffering
 
724
        self.assertIsNot(None, index._nodes)
 
725
 
 
726
    def test_iter_entries_buffers_by_bytes_read(self):
 
727
        index = self.make_index(nodes=self.make_nodes(64))
 
728
        list(index.iter_entries([self.make_key(10)]))
 
729
        # The first time through isn't enough to trigger a buffer all
 
730
        self.assertIs(None, index._nodes)
 
731
        self.assertEqual(4096, index._bytes_read)
 
732
        # Grabbing a key in that same page won't trigger a buffer all, as we
 
733
        # still haven't read 50% of the file
 
734
        list(index.iter_entries([self.make_key(11)]))
 
735
        self.assertIs(None, index._nodes)
 
736
        self.assertEqual(4096, index._bytes_read)
 
737
        # We haven't read more data, so reading outside the range won't trigger
 
738
        # a buffer all right away
 
739
        list(index.iter_entries([self.make_key(40)]))
 
740
        self.assertIs(None, index._nodes)
 
741
        self.assertEqual(8192, index._bytes_read)
 
742
        # On the next pass, we will not trigger buffer all if the key is
 
743
        # available without reading more
 
744
        list(index.iter_entries([self.make_key(32)]))
 
745
        self.assertIs(None, index._nodes)
 
746
        # But if we *would* need to read more to resolve it, then we will
 
747
        # buffer all.
 
748
        list(index.iter_entries([self.make_key(60)]))
 
749
        self.assertIsNot(None, index._nodes)
 
750
 
643
751
    def test_iter_entries_references_resolved(self):
644
752
        index = self.make_index(1, nodes=[
645
753
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
763
871
            (('name', ), '', ()), (('foo', ), '', ())])
764
872
        self.assertEqual(2, index.key_count())
765
873
 
 
874
    def test_read_and_parse_tracks_real_read_value(self):
 
875
        index = self.make_index(nodes=self.make_nodes(10))
 
876
        del index._transport._activity[:]
 
877
        index._read_and_parse([(0, 200)])
 
878
        self.assertEqual([
 
879
            ('readv', 'index', [(0, 200)], True, index._size),
 
880
            ],
 
881
            index._transport._activity)
 
882
        # The readv expansion code will expand the initial request to 4096
 
883
        # bytes, which is more than enough to read the entire index, and we
 
884
        # will track the fact that we read that many bytes.
 
885
        self.assertEqual(index._size, index._bytes_read)
 
886
 
 
887
    def test_read_and_parse_triggers_buffer_all(self):
 
888
        index = self.make_index(key_elements=2, nodes=[
 
889
            (('name', 'fin1'), 'data', ()),
 
890
            (('name', 'fin2'), 'beta', ()),
 
891
            (('ref', 'erence'), 'refdata', ())])
 
892
        self.assertTrue(index._size > 0)
 
893
        self.assertIs(None, index._nodes)
 
894
        index._read_and_parse([(0, index._size)])
 
895
        self.assertIsNot(None, index._nodes)
 
896
 
766
897
    def test_validate_bad_index_errors(self):
767
898
        trans = self.get_transport()
768
899
        trans.put_bytes('name', "not an index\n")
802
933
        index = self.make_index(nodes=[(('key', ), 'value', ())])
803
934
        index.validate()
804
935
 
 
936
    # XXX: external_references tests are duplicated in test_btree_index.  We
 
937
    # probably should have per_graph_index tests...
 
938
    def test_external_references_no_refs(self):
 
939
        index = self.make_index(ref_lists=0, nodes=[])
 
940
        self.assertRaises(ValueError, index.external_references, 0)
 
941
 
 
942
    def test_external_references_no_results(self):
 
943
        index = self.make_index(ref_lists=1, nodes=[
 
944
            (('key',), 'value', ([],))])
 
945
        self.assertEqual(set(), index.external_references(0))
 
946
 
 
947
    def test_external_references_missing_ref(self):
 
948
        missing_key = ('missing',)
 
949
        index = self.make_index(ref_lists=1, nodes=[
 
950
            (('key',), 'value', ([missing_key],))])
 
951
        self.assertEqual(set([missing_key]), index.external_references(0))
 
952
 
 
953
    def test_external_references_multiple_ref_lists(self):
 
954
        missing_key = ('missing',)
 
955
        index = self.make_index(ref_lists=2, nodes=[
 
956
            (('key',), 'value', ([], [missing_key]))])
 
957
        self.assertEqual(set([]), index.external_references(0))
 
958
        self.assertEqual(set([missing_key]), index.external_references(1))
 
959
 
 
960
    def test_external_references_two_records(self):
 
961
        index = self.make_index(ref_lists=1, nodes=[
 
962
            (('key-1',), 'value', ([('key-2',)],)),
 
963
            (('key-2',), 'value', ([],)),
 
964
            ])
 
965
        self.assertEqual(set([]), index.external_references(0))
 
966
 
 
967
    def test__find_ancestors(self):
 
968
        key1 = ('key-1',)
 
969
        key2 = ('key-2',)
 
970
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
971
            (key1, 'value', ([key2],)),
 
972
            (key2, 'value', ([],)),
 
973
            ])
 
974
        parent_map = {}
 
975
        missing_keys = set()
 
976
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
977
        self.assertEqual({key1: (key2,)}, parent_map)
 
978
        self.assertEqual(set(), missing_keys)
 
979
        self.assertEqual(set([key2]), search_keys)
 
980
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
981
                                            missing_keys)
 
982
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
983
        self.assertEqual(set(), missing_keys)
 
984
        self.assertEqual(set(), search_keys)
 
985
 
 
986
    def test__find_ancestors_w_missing(self):
 
987
        key1 = ('key-1',)
 
988
        key2 = ('key-2',)
 
989
        key3 = ('key-3',)
 
990
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
991
            (key1, 'value', ([key2],)),
 
992
            (key2, 'value', ([],)),
 
993
            ])
 
994
        parent_map = {}
 
995
        missing_keys = set()
 
996
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
997
                                            missing_keys)
 
998
        self.assertEqual({key2: ()}, parent_map)
 
999
        self.assertEqual(set([key3]), missing_keys)
 
1000
        self.assertEqual(set(), search_keys)
 
1001
 
 
1002
    def test__find_ancestors_dont_search_known(self):
 
1003
        key1 = ('key-1',)
 
1004
        key2 = ('key-2',)
 
1005
        key3 = ('key-3',)
 
1006
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1007
            (key1, 'value', ([key2],)),
 
1008
            (key2, 'value', ([key3],)),
 
1009
            (key3, 'value', ([],)),
 
1010
            ])
 
1011
        # We already know about key2, so we won't try to search for key3
 
1012
        parent_map = {key2: (key3,)}
 
1013
        missing_keys = set()
 
1014
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1015
                                            missing_keys)
 
1016
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1017
        self.assertEqual(set(), missing_keys)
 
1018
        self.assertEqual(set(), search_keys)
 
1019
 
 
1020
    def test_supports_unlimited_cache(self):
 
1021
        builder = GraphIndexBuilder(0, key_elements=1)
 
1022
        stream = builder.finish()
 
1023
        trans = get_transport(self.get_url())
 
1024
        size = trans.put_file('index', stream)
 
1025
        # It doesn't matter what unlimited_cache does here, just that it can be
 
1026
        # passed
 
1027
        index = GraphIndex(trans, 'index', size, unlimited_cache=True)
 
1028
 
805
1029
 
806
1030
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
807
1031
 
814
1038
        size = trans.put_file(name, stream)
815
1039
        return GraphIndex(trans, name, size)
816
1040
 
 
1041
    def make_combined_index_with_missing(self, missing=['1', '2']):
 
1042
        """Create a CombinedGraphIndex which will have missing indexes.
 
1043
 
 
1044
        This creates a CGI which thinks it has 2 indexes, however they have
 
1045
        been deleted. If CGI._reload_func() is called, then it will repopulate
 
1046
        with a new index.
 
1047
 
 
1048
        :param missing: The underlying indexes to delete
 
1049
        :return: (CombinedGraphIndex, reload_counter)
 
1050
        """
 
1051
        index1 = self.make_index('1', nodes=[(('1',), '', ())])
 
1052
        index2 = self.make_index('2', nodes=[(('2',), '', ())])
 
1053
        index3 = self.make_index('3', nodes=[
 
1054
            (('1',), '', ()),
 
1055
            (('2',), '', ())])
 
1056
 
 
1057
        # total_reloads, num_changed, num_unchanged
 
1058
        reload_counter = [0, 0, 0]
 
1059
        def reload():
 
1060
            reload_counter[0] += 1
 
1061
            new_indices = [index3]
 
1062
            if index._indices == new_indices:
 
1063
                reload_counter[2] += 1
 
1064
                return False
 
1065
            reload_counter[1] += 1
 
1066
            index._indices[:] = new_indices
 
1067
            return True
 
1068
        index = CombinedGraphIndex([index1, index2], reload_func=reload)
 
1069
        trans = self.get_transport()
 
1070
        for fname in missing:
 
1071
            trans.delete(fname)
 
1072
        return index, reload_counter
 
1073
 
817
1074
    def test_open_missing_index_no_error(self):
818
1075
        trans = self.get_transport()
819
1076
        index1 = GraphIndex(trans, 'missing', 100)
825
1082
        index.insert_index(0, index1)
826
1083
        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
827
1084
 
 
1085
    def test_clear_cache(self):
 
1086
        log = []
 
1087
 
 
1088
        class ClearCacheProxy(object):
 
1089
 
 
1090
            def __init__(self, index):
 
1091
                self._index = index
 
1092
 
 
1093
            def __getattr__(self, name):
 
1094
                return getattr(self._index)
 
1095
 
 
1096
            def clear_cache(self):
 
1097
                log.append(self._index)
 
1098
                return self._index.clear_cache()
 
1099
 
 
1100
        index = CombinedGraphIndex([])
 
1101
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1102
        index.insert_index(0, ClearCacheProxy(index1))
 
1103
        index2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1104
        index.insert_index(1, ClearCacheProxy(index2))
 
1105
        # CombinedGraphIndex should call 'clear_cache()' on all children
 
1106
        index.clear_cache()
 
1107
        self.assertEqual(sorted([index1, index2]), sorted(log))
 
1108
 
828
1109
    def test_iter_all_entries_empty(self):
829
1110
        index = CombinedGraphIndex([])
830
1111
        self.assertEqual([], list(index.iter_all_entries()))
894
1175
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
895
1176
            (index2, ('ref', ), 'refdata', ((), ))]),
896
1177
            set(index.iter_entries([('name', ), ('ref', )])))
897
 
 
 
1178
 
898
1179
    def test_iter_all_keys_dup_entry(self):
899
1180
        index1 = self.make_index('1', 1, nodes=[
900
1181
            (('name', ), 'data', ([('ref', )], )),
905
1186
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
906
1187
            (index1, ('ref', ), 'refdata', ((), ))]),
907
1188
            set(index.iter_entries([('name', ), ('ref', )])))
908
 
 
 
1189
 
909
1190
    def test_iter_missing_entry_empty(self):
910
1191
        index = CombinedGraphIndex([])
911
1192
        self.assertEqual([], list(index.iter_entries([('a', )])))
920
1201
        index2 = self.make_index('2')
921
1202
        index = CombinedGraphIndex([index1, index2])
922
1203
        self.assertEqual([], list(index.iter_entries([('a', )])))
923
 
 
 
1204
 
924
1205
    def test_iter_entry_present_one_index_only(self):
925
1206
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
926
1207
        index2 = self.make_index('2', nodes=[])
957
1238
        index = CombinedGraphIndex([])
958
1239
        index.validate()
959
1240
 
 
1241
    def test_key_count_reloads(self):
 
1242
        index, reload_counter = self.make_combined_index_with_missing()
 
1243
        self.assertEqual(2, index.key_count())
 
1244
        self.assertEqual([1, 1, 0], reload_counter)
 
1245
 
 
1246
    def test_key_count_no_reload(self):
 
1247
        index, reload_counter = self.make_combined_index_with_missing()
 
1248
        index._reload_func = None
 
1249
        # Without a _reload_func we just raise the exception
 
1250
        self.assertRaises(errors.NoSuchFile, index.key_count)
 
1251
 
 
1252
    def test_key_count_reloads_and_fails(self):
 
1253
        # We have deleted all underlying indexes, so we will try to reload, but
 
1254
        # still fail. This is mostly to test we don't get stuck in an infinite
 
1255
        # loop trying to reload
 
1256
        index, reload_counter = self.make_combined_index_with_missing(
 
1257
                                    ['1', '2', '3'])
 
1258
        self.assertRaises(errors.NoSuchFile, index.key_count)
 
1259
        self.assertEqual([2, 1, 1], reload_counter)
 
1260
 
 
1261
    def test_iter_entries_reloads(self):
 
1262
        index, reload_counter = self.make_combined_index_with_missing()
 
1263
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
 
1264
        index3 = index._indices[0]
 
1265
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
 
1266
                         result)
 
1267
        self.assertEqual([1, 1, 0], reload_counter)
 
1268
 
 
1269
    def test_iter_entries_reloads_midway(self):
 
1270
        # The first index still looks present, so we get interrupted mid-way
 
1271
        # through
 
1272
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1273
        index1, index2 = index._indices
 
1274
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
 
1275
        index3 = index._indices[0]
 
1276
        # We had already yielded '1', so we just go on to the next, we should
 
1277
        # not yield '1' twice.
 
1278
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
 
1279
                         result)
 
1280
        self.assertEqual([1, 1, 0], reload_counter)
 
1281
 
 
1282
    def test_iter_entries_no_reload(self):
 
1283
        index, reload_counter = self.make_combined_index_with_missing()
 
1284
        index._reload_func = None
 
1285
        # Without a _reload_func we just raise the exception
 
1286
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
 
1287
 
 
1288
    def test_iter_entries_reloads_and_fails(self):
 
1289
        index, reload_counter = self.make_combined_index_with_missing(
 
1290
                                    ['1', '2', '3'])
 
1291
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
 
1292
        self.assertEqual([2, 1, 1], reload_counter)
 
1293
 
 
1294
    def test_iter_all_entries_reloads(self):
 
1295
        index, reload_counter = self.make_combined_index_with_missing()
 
1296
        result = list(index.iter_all_entries())
 
1297
        index3 = index._indices[0]
 
1298
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
 
1299
                         result)
 
1300
        self.assertEqual([1, 1, 0], reload_counter)
 
1301
 
 
1302
    def test_iter_all_entries_reloads_midway(self):
 
1303
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1304
        index1, index2 = index._indices
 
1305
        result = list(index.iter_all_entries())
 
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_all_entries_no_reload(self):
 
1314
        index, reload_counter = self.make_combined_index_with_missing()
 
1315
        index._reload_func = None
 
1316
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
 
1317
 
 
1318
    def test_iter_all_entries_reloads_and_fails(self):
 
1319
        index, reload_counter = self.make_combined_index_with_missing(
 
1320
                                    ['1', '2', '3'])
 
1321
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
 
1322
 
 
1323
    def test_iter_entries_prefix_reloads(self):
 
1324
        index, reload_counter = self.make_combined_index_with_missing()
 
1325
        result = list(index.iter_entries_prefix([('1',)]))
 
1326
        index3 = index._indices[0]
 
1327
        self.assertEqual([(index3, ('1',), '')], result)
 
1328
        self.assertEqual([1, 1, 0], reload_counter)
 
1329
 
 
1330
    def test_iter_entries_prefix_reloads_midway(self):
 
1331
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1332
        index1, index2 = index._indices
 
1333
        result = list(index.iter_entries_prefix([('1',)]))
 
1334
        index3 = index._indices[0]
 
1335
        # We had already yielded '1', so we just go on to the next, we should
 
1336
        # not yield '1' twice.
 
1337
        self.assertEqual([(index1, ('1',), '')], result)
 
1338
        self.assertEqual([1, 1, 0], reload_counter)
 
1339
 
 
1340
    def test_iter_entries_prefix_no_reload(self):
 
1341
        index, reload_counter = self.make_combined_index_with_missing()
 
1342
        index._reload_func = None
 
1343
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
 
1344
                                                 [('1',)])
 
1345
 
 
1346
    def test_iter_entries_prefix_reloads_and_fails(self):
 
1347
        index, reload_counter = self.make_combined_index_with_missing(
 
1348
                                    ['1', '2', '3'])
 
1349
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
 
1350
                                                 [('1',)])
 
1351
 
 
1352
    def test_validate_reloads(self):
 
1353
        index, reload_counter = self.make_combined_index_with_missing()
 
1354
        index.validate()
 
1355
        self.assertEqual([1, 1, 0], reload_counter)
 
1356
 
 
1357
    def test_validate_reloads_midway(self):
 
1358
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1359
        index.validate()
 
1360
 
 
1361
    def test_validate_no_reload(self):
 
1362
        index, reload_counter = self.make_combined_index_with_missing()
 
1363
        index._reload_func = None
 
1364
        self.assertRaises(errors.NoSuchFile, index.validate)
 
1365
 
 
1366
    def test_validate_reloads_and_fails(self):
 
1367
        index, reload_counter = self.make_combined_index_with_missing(
 
1368
                                    ['1', '2', '3'])
 
1369
        self.assertRaises(errors.NoSuchFile, index.validate)
 
1370
 
 
1371
    def test_find_ancestors_across_indexes(self):
 
1372
        key1 = ('key-1',)
 
1373
        key2 = ('key-2',)
 
1374
        key3 = ('key-3',)
 
1375
        key4 = ('key-4',)
 
1376
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1377
            (key1, 'value', ([],)),
 
1378
            (key2, 'value', ([key1],)),
 
1379
            ])
 
1380
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1381
            (key3, 'value', ([key2],)),
 
1382
            (key4, 'value', ([key3],)),
 
1383
            ])
 
1384
        c_index = CombinedGraphIndex([index1, index2])
 
1385
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1386
        self.assertEqual({key1: ()}, parent_map)
 
1387
        self.assertEqual(set(), missing_keys)
 
1388
        # Now look for a key from index2 which requires us to find the key in
 
1389
        # the second index, and then continue searching for parents in the
 
1390
        # first index
 
1391
        parent_map, missing_keys = c_index.find_ancestry([key3], 0)
 
1392
        self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
 
1393
        self.assertEqual(set(), missing_keys)
 
1394
 
 
1395
    def test_find_ancestors_missing_keys(self):
 
1396
        key1 = ('key-1',)
 
1397
        key2 = ('key-2',)
 
1398
        key3 = ('key-3',)
 
1399
        key4 = ('key-4',)
 
1400
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1401
            (key1, 'value', ([],)),
 
1402
            (key2, 'value', ([key1],)),
 
1403
            ])
 
1404
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1405
            (key3, 'value', ([key2],)),
 
1406
            ])
 
1407
        c_index = CombinedGraphIndex([index1, index2])
 
1408
        # Searching for a key which is actually not present at all should
 
1409
        # eventually converge
 
1410
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1411
        self.assertEqual({}, parent_map)
 
1412
        self.assertEqual(set([key4]), missing_keys)
 
1413
 
 
1414
    def test_find_ancestors_no_indexes(self):
 
1415
        c_index = CombinedGraphIndex([])
 
1416
        key1 = ('key-1',)
 
1417
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1418
        self.assertEqual({}, parent_map)
 
1419
        self.assertEqual(set([key1]), missing_keys)
 
1420
 
 
1421
    def test_find_ancestors_ghost_parent(self):
 
1422
        key1 = ('key-1',)
 
1423
        key2 = ('key-2',)
 
1424
        key3 = ('key-3',)
 
1425
        key4 = ('key-4',)
 
1426
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1427
            (key1, 'value', ([],)),
 
1428
            (key2, 'value', ([key1],)),
 
1429
            ])
 
1430
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1431
            (key4, 'value', ([key2, key3],)),
 
1432
            ])
 
1433
        c_index = CombinedGraphIndex([index1, index2])
 
1434
        # Searching for a key which is actually not present at all should
 
1435
        # eventually converge
 
1436
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1437
        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
 
1438
                         parent_map)
 
1439
        self.assertEqual(set([key3]), missing_keys)
 
1440
 
 
1441
    def test__find_ancestors_empty_index(self):
 
1442
        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
 
1443
        parent_map = {}
 
1444
        missing_keys = set()
 
1445
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1446
                                            missing_keys)
 
1447
        self.assertEqual(set(), search_keys)
 
1448
        self.assertEqual({}, parent_map)
 
1449
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1450
 
960
1451
 
961
1452
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
962
1453