355
326
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
356
327
builder.add_node(('reference', 'tokey'), 'data', ([],))
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)
366
330
class TestGraphIndex(TestCaseWithMemoryTransport):
368
def make_key(self, number):
369
return (str(number) + 'X'*100,)
371
def make_value(self, number):
372
return str(number) + 'Y'*100
374
def make_nodes(self, count=64):
375
# generate a big enough index that we only read some of it on a typical
378
for counter in range(count):
379
nodes.append((self.make_key(counter), self.make_value(counter), ()))
382
332
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
383
333
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
384
for key, value, references in nodes:
385
builder.add_node(key, value, references)
334
for node, value, references in nodes:
335
builder.add_node(node, value, references)
386
336
stream = builder.finish()
387
trans = get_transport('trace+' + self.get_url())
388
size = trans.put_file('index', stream)
389
return GraphIndex(trans, 'index', size)
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.
337
trans = self.get_transport()
338
trans.put_file('index', stream)
339
return GraphIndex(trans, 'index')
397
341
def test_open_bad_index_no_error(self):
398
342
trans = self.get_transport()
399
343
trans.put_bytes('name', "not an index\n")
400
index = GraphIndex(trans, 'name', 13)
402
def test_open_sets_parsed_map_empty(self):
403
index = self.make_index()
404
self.assertEqual([], index._parsed_byte_map)
405
self.assertEqual([], index._parsed_key_map)
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
414
('readv', 'index', [(0, 200)], True, index._size),
416
index._transport._activity)
417
# And that should have been enough to trigger reading the whole index
419
self.assertIsNot(None, index._nodes)
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.
432
('readv', 'index', [(30, 30), (0, 200)], True, 60),
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)],
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)
443
def test_first_lookup_key_via_location(self):
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*
451
index = self.make_index(nodes=self.make_nodes(64))
452
# reset the transport log
453
del index._transport._activity[:]
454
# do a _lookup_keys_via_location call for the middle of the file, which
455
# is what bisection uses.
456
start_lookup = index._size // 2
457
result = index._lookup_keys_via_location(
458
[(start_lookup, ('40missing', ))])
459
# this should have asked for a readv request, with adjust_for_latency,
460
# and two regions: the header, and half-way into the file.
463
[(start_lookup, 800), (0, 200)], True, index._size),
465
index._transport._activity)
466
# and the result should be that the key cannot be present, because this
467
# is a trivial index.
468
self.assertEqual([((start_lookup, ('40missing', )), False)],
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)
479
def test_parsing_non_adjacent_data_trims(self):
480
index = self.make_index(nodes=self.make_nodes(64))
481
result = index._lookup_keys_via_location(
482
[(index._size // 2, ('40', ))])
483
# and the result should be that the key cannot be present, because key is
484
# in the middle of the observed data from a 4K read - the smallest transport
485
# will do today with this api.
486
self.assertEqual([((index._size // 2, ('40', )), False)],
488
# and we should have a parse map that includes the header and the
489
# region that was parsed after trimming.
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))],
493
index._parsed_key_map)
495
def test_parsing_data_handles_parsed_contained_regions(self):
496
# the following patten creates a parsed region that is wholly within a
497
# single result from the readv layer:
498
# .... single-read (readv-minimum-size) ...
499
# which then trims the start and end so the parsed size is < readv
501
# then a dual lookup (or a reference lookup for that matter) which
502
# abuts or overlaps the parsed region on both sides will need to
503
# discard the data in the middle, but parse the end as well.
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 -
507
# we except both to be found, and the parsed byte map to include the
508
# locations of both keys.
509
index = self.make_index(nodes=self.make_nodes(128))
510
result = index._lookup_keys_via_location(
511
[(index._size // 2, ('40', ))])
512
# and we should have a parse map that includes the header and the
513
# region that was parsed after trimming.
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))],
517
index._parsed_key_map)
518
# now ask for two keys, right before and after the parsed region
519
result = index._lookup_keys_via_location(
520
[(11450, self.make_key(34)), (15707, self.make_key(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))),
528
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
530
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
531
# generate a big enough index that we only read some of it on a typical
533
index = self.make_index(nodes=self.make_nodes(64))
534
# lookup the keys in the middle of the file
535
result =index._lookup_keys_via_location(
536
[(index._size // 2, ('40', ))])
537
# check the parse map, this determines the test validity
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))],
541
index._parsed_key_map)
542
# reset the transport log
543
del index._transport._activity[:]
544
# now looking up a key in the portion of the file already parsed should
545
# not create a new transport request, and should return False (cannot
546
# be in the index) - even when the byte location we ask for is outside
548
result = index._lookup_keys_via_location(
550
self.assertEqual([((4000, ('40', )), False)],
552
self.assertEqual([], index._transport._activity)
554
def test_lookup_present_key_answers_without_io_when_map_permits(self):
555
# generate a big enough index that we only read some of it on a typical
557
index = self.make_index(nodes=self.make_nodes(64))
558
# lookup the keys in the middle of the file
559
result =index._lookup_keys_via_location(
560
[(index._size // 2, ('40', ))])
561
# check the parse map, this determines the test validity
562
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
563
self.assertEqual([(None, self.make_key(26)),
564
(self.make_key(31), self.make_key(48))],
565
index._parsed_key_map)
566
# reset the transport log
567
del index._transport._activity[:]
568
# now looking up a key in the portion of the file already parsed should
569
# not create a new transport request, and should return False (cannot
570
# be in the index) - even when the byte location we ask for is outside
573
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
575
[((4000, self.make_key(40)),
576
(index, self.make_key(40), self.make_value(40)))],
578
self.assertEqual([], index._transport._activity)
580
def test_lookup_key_below_probed_area(self):
581
# generate a big enough index that we only read some of it on a typical
583
index = self.make_index(nodes=self.make_nodes(64))
584
# ask for the key in the middle, but a key that is located in the
585
# unparsed region before the middle.
586
result =index._lookup_keys_via_location(
587
[(index._size // 2, ('30', ))])
588
# check the parse map, this determines the test validity
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))],
592
index._parsed_key_map)
593
self.assertEqual([((index._size // 2, ('30', )), -1)],
596
def test_lookup_key_above_probed_area(self):
597
# generate a big enough index that we only read some of it on a typical
599
index = self.make_index(nodes=self.make_nodes(64))
600
# ask for the key in the middle, but a key that is located in the
601
# unparsed region after the middle.
602
result =index._lookup_keys_via_location(
603
[(index._size // 2, ('50', ))])
604
# check the parse map, this determines the test validity
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))],
608
index._parsed_key_map)
609
self.assertEqual([((index._size // 2, ('50', )), +1)],
612
def test_lookup_key_resolves_references(self):
613
# generate a big enough index that we only read some of it on a typical
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
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.
634
[('readv', 'index', [(index_center, 800), (0, 200)], True,
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))])
643
[((11000, self.make_key(45)),
644
(index, self.make_key(45), self.make_value(45),
645
((self.make_key(65),),)))],
647
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
648
index._transport._activity)
650
def test_lookup_key_can_buffer_all(self):
652
for counter in range(64):
653
nodes.append((self.make_key(counter), self.make_value(counter),
654
((self.make_key(counter + 20),),) ))
655
index = self.make_index(ref_lists=1, nodes=nodes)
656
# lookup a key in the middle that does not exist, so that when we can
657
# check that the referred-to-keys are not accessed automatically.
658
index_size = index._size
659
index_center = index_size // 2
660
result = index._lookup_keys_via_location([(index_center, ('40', ))])
661
# check the parse map - only the start and middle should have been
663
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
664
self.assertEqual([(None, self.make_key(25)),
665
(self.make_key(37), self.make_key(52))],
666
index._parsed_key_map)
667
# and check the transport activity likewise.
669
[('readv', 'index', [(index_center, 800), (0, 200)], True,
671
index._transport._activity)
672
# reset the transport log for testing the reference lookup
673
del index._transport._activity[:]
674
# now looking up a key in the portion of the file already parsed should
675
# only perform IO to resolve its key references.
676
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
678
[((7000, self.make_key(40)),
679
(index, self.make_key(40), self.make_value(40),
680
((self.make_key(60),),)))],
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)
344
index = GraphIndex(trans, 'name')
686
346
def test_iter_all_entries_empty(self):
687
347
index = self.make_index()
690
350
def test_iter_all_entries_simple(self):
691
351
index = self.make_index(nodes=[(('name', ), 'data', ())])
692
self.assertEqual([(index, ('name', ), 'data')],
352
self.assertEqual([(('name', ), 'data')],
693
353
list(index.iter_all_entries()))
695
355
def test_iter_all_entries_simple_2_elements(self):
696
356
index = self.make_index(key_elements=2,
697
357
nodes=[(('name', 'surname'), 'data', ())])
698
self.assertEqual([(index, ('name', 'surname'), 'data')],
358
self.assertEqual([(('name', 'surname'), 'data')],
699
359
list(index.iter_all_entries()))
701
361
def test_iter_all_entries_references_resolved(self):
702
362
index = self.make_index(1, nodes=[
703
363
(('name', ), 'data', ([('ref', )], )),
704
364
(('ref', ), 'refdata', ([], ))])
705
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
706
(index, ('ref', ), 'refdata', ((), ))]),
365
self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
366
(('ref', ), 'refdata', ((), ))]),
707
367
set(index.iter_all_entries()))
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
719
('readv', 'index', [(0, 200)], True, index._size),
721
index._transport._activity)
722
# And that should have been enough to trigger reading the whole index
724
self.assertIsNot(None, index._nodes)
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
748
list(index.iter_entries([self.make_key(60)]))
749
self.assertIsNot(None, index._nodes)
751
def test_iter_entries_references_resolved(self):
752
index = self.make_index(1, nodes=[
753
(('name', ), 'data', ([('ref', ), ('ref', )], )),
754
(('ref', ), 'refdata', ([], ))])
755
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
756
(index, ('ref', ), 'refdata', ((), ))]),
757
set(index.iter_entries([('name',), ('ref',)])))
759
def test_iter_entries_references_2_refs_resolved(self):
760
index = self.make_index(2, nodes=[
761
(('name', ), 'data', ([('ref', )], [('ref', )])),
762
(('ref', ), 'refdata', ([], []))])
763
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
764
(index, ('ref', ), 'refdata', ((), ()))]),
765
set(index.iter_entries([('name',), ('ref',)])))
767
369
def test_iteration_absent_skipped(self):
768
370
index = self.make_index(1, nodes=[
769
371
(('name', ), 'data', ([('ref', )], ))])
770
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
372
self.assertEqual(set([(('name', ), 'data', ((('ref',),),))]),
771
373
set(index.iter_all_entries()))
772
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
374
self.assertEqual(set([(('name', ), 'data', ((('ref',),),))]),
773
375
set(index.iter_entries([('name', )])))
774
376
self.assertEqual([], list(index.iter_entries([('ref', )])))
776
378
def test_iteration_absent_skipped_2_element_keys(self):
777
379
index = self.make_index(1, key_elements=2, nodes=[
778
380
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
779
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
381
self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
780
382
set(index.iter_all_entries()))
781
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
383
self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
782
384
set(index.iter_entries([('name', 'fin')])))
783
385
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
851
448
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
852
449
(('name', 'fin2'), 'beta', ([], )),
853
450
(('ref', 'erence'), 'refdata', ([], ))])
854
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
855
(index, ('ref', 'erence'), 'refdata', ((), ))]),
451
self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
452
(('ref', 'erence'), 'refdata', ((), ))]),
856
453
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
857
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
858
(index, ('name', 'fin2'), 'beta', ((), ))]),
454
self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
455
(('name', 'fin2'), 'beta', ((), ))]),
859
456
set(index.iter_entries_prefix([('name', None)])))
861
def test_key_count_empty(self):
862
index = self.make_index()
863
self.assertEqual(0, index.key_count())
865
def test_key_count_one(self):
866
index = self.make_index(nodes=[(('name', ), '', ())])
867
self.assertEqual(1, index.key_count())
869
def test_key_count_two(self):
870
index = self.make_index(nodes=[
871
(('name', ), '', ()), (('foo', ), '', ())])
872
self.assertEqual(2, index.key_count())
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)])
879
('readv', 'index', [(0, 200)], True, index._size),
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)
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)
897
458
def test_validate_bad_index_errors(self):
898
459
trans = self.get_transport()
899
460
trans.put_bytes('name', "not an index\n")
900
index = GraphIndex(trans, 'name', 13)
461
index = GraphIndex(trans, 'name')
901
462
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
903
464
def test_validate_bad_node_refs(self):
933
494
index = self.make_index(nodes=[(('key', ), 'value', ())])
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)
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))
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))
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))
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', ([],)),
965
self.assertEqual(set([]), index.external_references(0))
967
def test__find_ancestors(self):
970
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
971
(key1, 'value', ([key2],)),
972
(key2, 'value', ([],)),
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,
982
self.assertEqual({key1: (key2,), key2: ()}, parent_map)
983
self.assertEqual(set(), missing_keys)
984
self.assertEqual(set(), search_keys)
986
def test__find_ancestors_w_missing(self):
990
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
991
(key1, 'value', ([key2],)),
992
(key2, 'value', ([],)),
996
search_keys = index._find_ancestors([key2, key3], 0, parent_map,
998
self.assertEqual({key2: ()}, parent_map)
999
self.assertEqual(set([key3]), missing_keys)
1000
self.assertEqual(set(), search_keys)
1002
def test__find_ancestors_dont_search_known(self):
1006
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1007
(key1, 'value', ([key2],)),
1008
(key2, 'value', ([key3],)),
1009
(key3, 'value', ([],)),
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,
1016
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1017
self.assertEqual(set(), missing_keys)
1018
self.assertEqual(set(), search_keys)
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
1027
index = GraphIndex(trans, 'index', size, unlimited_cache=True)
1030
498
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1032
500
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1033
501
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
1034
for key, value, references in nodes:
1035
builder.add_node(key, value, references)
502
for node, value, references in nodes:
503
builder.add_node(node, value, references)
1036
504
stream = builder.finish()
1037
505
trans = self.get_transport()
1038
size = trans.put_file(name, stream)
1039
return GraphIndex(trans, name, size)
1041
def make_combined_index_with_missing(self, missing=['1', '2']):
1042
"""Create a CombinedGraphIndex which will have missing indexes.
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
1048
:param missing: The underlying indexes to delete
1049
:return: (CombinedGraphIndex, reload_counter)
1051
index1 = self.make_index('1', nodes=[(('1',), '', ())])
1052
index2 = self.make_index('2', nodes=[(('2',), '', ())])
1053
index3 = self.make_index('3', nodes=[
1057
# total_reloads, num_changed, num_unchanged
1058
reload_counter = [0, 0, 0]
1060
reload_counter[0] += 1
1061
new_indices = [index3]
1062
if index._indices == new_indices:
1063
reload_counter[2] += 1
1065
reload_counter[1] += 1
1066
index._indices[:] = new_indices
1068
index = CombinedGraphIndex([index1, index2], reload_func=reload)
1069
trans = self.get_transport()
1070
for fname in missing:
1072
return index, reload_counter
506
trans.put_file(name, stream)
507
return GraphIndex(trans, name)
1074
509
def test_open_missing_index_no_error(self):
1075
510
trans = self.get_transport()
1076
index1 = GraphIndex(trans, 'missing', 100)
511
index1 = GraphIndex(trans, 'missing')
1077
512
index = CombinedGraphIndex([index1])
1079
514
def test_add_index(self):
1080
515
index = CombinedGraphIndex([])
1081
516
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1082
517
index.insert_index(0, index1)
1083
self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1085
def test_clear_cache(self):
1088
class ClearCacheProxy(object):
1090
def __init__(self, index):
1093
def __getattr__(self, name):
1094
return getattr(self._index)
1096
def clear_cache(self):
1097
log.append(self._index)
1098
return self._index.clear_cache()
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
1107
self.assertEqual(sorted([index1, index2]), sorted(log))
518
self.assertEqual([(('key', ), '')], list(index.iter_all_entries()))
1109
520
def test_iter_all_entries_empty(self):
1110
521
index = CombinedGraphIndex([])
1238
635
index = CombinedGraphIndex([])
1239
636
index.validate()
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)
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)
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(
1258
self.assertRaises(errors.NoSuchFile, index.key_count)
1259
self.assertEqual([2, 1, 1], reload_counter)
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',), '')],
1267
self.assertEqual([1, 1, 0], reload_counter)
1269
def test_iter_entries_reloads_midway(self):
1270
# The first index still looks present, so we get interrupted mid-way
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',), '')],
1280
self.assertEqual([1, 1, 0], reload_counter)
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',)])
1288
def test_iter_entries_reloads_and_fails(self):
1289
index, reload_counter = self.make_combined_index_with_missing(
1291
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1292
self.assertEqual([2, 1, 1], reload_counter)
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',), '')],
1300
self.assertEqual([1, 1, 0], reload_counter)
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',), '')],
1311
self.assertEqual([1, 1, 0], reload_counter)
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)
1318
def test_iter_all_entries_reloads_and_fails(self):
1319
index, reload_counter = self.make_combined_index_with_missing(
1321
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
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)
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)
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,
1346
def test_iter_entries_prefix_reloads_and_fails(self):
1347
index, reload_counter = self.make_combined_index_with_missing(
1349
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1352
def test_validate_reloads(self):
1353
index, reload_counter = self.make_combined_index_with_missing()
1355
self.assertEqual([1, 1, 0], reload_counter)
1357
def test_validate_reloads_midway(self):
1358
index, reload_counter = self.make_combined_index_with_missing(['2'])
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)
1366
def test_validate_reloads_and_fails(self):
1367
index, reload_counter = self.make_combined_index_with_missing(
1369
self.assertRaises(errors.NoSuchFile, index.validate)
1371
def test_find_ancestors_across_indexes(self):
1376
index1 = self.make_index('12', ref_lists=1, nodes=[
1377
(key1, 'value', ([],)),
1378
(key2, 'value', ([key1],)),
1380
index2 = self.make_index('34', ref_lists=1, nodes=[
1381
(key3, 'value', ([key2],)),
1382
(key4, 'value', ([key3],)),
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
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)
1395
def test_find_ancestors_missing_keys(self):
1400
index1 = self.make_index('12', ref_lists=1, nodes=[
1401
(key1, 'value', ([],)),
1402
(key2, 'value', ([key1],)),
1404
index2 = self.make_index('34', ref_lists=1, nodes=[
1405
(key3, 'value', ([key2],)),
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)
1414
def test_find_ancestors_no_indexes(self):
1415
c_index = CombinedGraphIndex([])
1417
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1418
self.assertEqual({}, parent_map)
1419
self.assertEqual(set([key1]), missing_keys)
1421
def test_find_ancestors_ghost_parent(self):
1426
index1 = self.make_index('12', ref_lists=1, nodes=[
1427
(key1, 'value', ([],)),
1428
(key2, 'value', ([key1],)),
1430
index2 = self.make_index('34', ref_lists=1, nodes=[
1431
(key4, 'value', ([key2, key3],)),
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: ()},
1439
self.assertEqual(set([key3]), missing_keys)
1441
def test__find_ancestors_empty_index(self):
1442
index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1444
missing_keys = set()
1445
search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1447
self.assertEqual(set(), search_keys)
1448
self.assertEqual({}, parent_map)
1449
self.assertEqual(set([('one',), ('two',)]), missing_keys)
1452
639
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1579
754
index.validate()
1582
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
1584
def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
1585
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1586
result.add_nodes(nodes)
1588
add_nodes_callback = result.add_nodes
1590
add_nodes_callback = None
1591
adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1592
add_nodes_callback=add_nodes_callback)
1593
return result, adapter
1595
def test_add_node(self):
1596
index, adapter = self.make_index(add_callback=True)
1597
adapter.add_node(('key',), 'value', ((('ref',),),))
1598
self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
1599
set(index.iter_all_entries()))
1601
def test_add_nodes(self):
1602
index, adapter = self.make_index(add_callback=True)
1604
(('key',), 'value', ((('ref',),),)),
1605
(('key2',), 'value2', ((),)),
1607
self.assertEqual(set([
1608
(index, ('prefix', 'key2'), 'value2', ((),)),
1609
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1611
set(index.iter_all_entries()))
1613
def test_construct(self):
1614
index = InMemoryGraphIndex()
1615
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
1617
def test_construct_with_callback(self):
1618
index = InMemoryGraphIndex()
1619
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
1621
def test_iter_all_entries_cross_prefix_map_errors(self):
1622
index, adapter = self.make_index(nodes=[
1623
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
1624
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
1626
def test_iter_all_entries(self):
1627
index, adapter = self.make_index(nodes=[
1628
(('notprefix', 'key1'), 'data', ((), )),
1629
(('prefix', 'key1'), 'data1', ((), )),
1630
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1631
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1632
(index, ('key2', ), 'data2', ((('key1',),),))]),
1633
set(adapter.iter_all_entries()))
1635
def test_iter_entries(self):
1636
index, adapter = self.make_index(nodes=[
1637
(('notprefix', 'key1'), 'data', ((), )),
1638
(('prefix', 'key1'), 'data1', ((), )),
1639
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1640
# ask for many - get all
1641
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1642
(index, ('key2', ), 'data2', ((('key1', ),),))]),
1643
set(adapter.iter_entries([('key1', ), ('key2', )])))
1644
# ask for one, get one
1645
self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
1646
set(adapter.iter_entries([('key1', )])))
1647
# ask for missing, get none
1648
self.assertEqual(set(),
1649
set(adapter.iter_entries([('key3', )])))
1651
def test_iter_entries_prefix(self):
1652
index, adapter = self.make_index(key_elements=3, nodes=[
1653
(('notprefix', 'foo', 'key1'), 'data', ((), )),
1654
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
1655
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1656
# ask for a prefix, get the results for just that prefix, adjusted.
1657
self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
1658
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
1659
set(adapter.iter_entries_prefix([('prefix2', None)])))
1661
def test_key_count_no_matching_keys(self):
1662
index, adapter = self.make_index(nodes=[
1663
(('notprefix', 'key1'), 'data', ((), ))])
1664
self.assertEqual(0, adapter.key_count())
1666
def test_key_count_some_keys(self):
1667
index, adapter = self.make_index(nodes=[
1668
(('notprefix', 'key1'), 'data', ((), )),
1669
(('prefix', 'key1'), 'data1', ((), )),
1670
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1671
self.assertEqual(2, adapter.key_count())
1673
def test_validate(self):
1674
index, adapter = self.make_index()
1677
calls.append('called')
1678
index.validate = validate
1680
self.assertEqual(['called'], calls)
added
removed
bzrlib/tests/test_index.py
