350
326
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
351
327
builder.add_node(('reference', 'tokey'), 'data', ([],))
353
def test_set_optimize(self):
354
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
355
builder.set_optimize(for_size=True)
356
self.assertTrue(builder._optimize_for_size)
357
builder.set_optimize(for_size=False)
358
self.assertFalse(builder._optimize_for_size)
361
330
class TestGraphIndex(TestCaseWithMemoryTransport):
363
def make_key(self, number):
364
return (str(number) + 'X'*100,)
366
def make_value(self, number):
367
return str(number) + 'Y'*100
369
def make_nodes(self, count=64):
370
# generate a big enough index that we only read some of it on a typical
373
for counter in range(count):
374
nodes.append((self.make_key(counter), self.make_value(counter), ()))
377
332
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
378
333
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
379
for key, value, references in nodes:
380
builder.add_node(key, value, references)
334
for node, value, references in nodes:
335
builder.add_node(node, value, references)
381
336
stream = builder.finish()
382
trans = get_transport('trace+' + self.get_url())
383
size = trans.put_file('index', stream)
384
return GraphIndex(trans, 'index', size)
337
trans = self.get_transport()
338
trans.put_file('index', stream)
339
return GraphIndex(trans, 'index')
386
341
def test_open_bad_index_no_error(self):
387
342
trans = self.get_transport()
388
343
trans.put_bytes('name', "not an index\n")
389
index = GraphIndex(trans, 'name', 13)
391
def test_open_sets_parsed_map_empty(self):
392
index = self.make_index()
393
self.assertEqual([], index._parsed_byte_map)
394
self.assertEqual([], index._parsed_key_map)
396
def test_key_count_buffers(self):
397
index = self.make_index(nodes=self.make_nodes(2))
398
# reset the transport log
399
del index._transport._activity[:]
400
self.assertEqual(2, index.key_count())
401
# We should have requested reading the header bytes
403
('readv', 'index', [(0, 200)], True, index._size),
405
index._transport._activity)
406
# And that should have been enough to trigger reading the whole index
408
self.assertIsNot(None, index._nodes)
410
def test_lookup_key_via_location_buffers(self):
411
index = self.make_index()
412
# reset the transport log
413
del index._transport._activity[:]
414
# do a _lookup_keys_via_location call for the middle of the file, which
415
# is what bisection uses.
416
result = index._lookup_keys_via_location(
417
[(index._size // 2, ('missing', ))])
418
# this should have asked for a readv request, with adjust_for_latency,
419
# and two regions: the header, and half-way into the file.
421
('readv', 'index', [(30, 30), (0, 200)], True, 60),
423
index._transport._activity)
424
# and the result should be that the key cannot be present, because this
425
# is a trivial index.
426
self.assertEqual([((index._size // 2, ('missing', )), False)],
428
# And this should have caused the file to be fully buffered
429
self.assertIsNot(None, index._nodes)
430
self.assertEqual([], index._parsed_byte_map)
432
def test_first_lookup_key_via_location(self):
433
# We need enough data so that the _HEADER_READV doesn't consume the
434
# whole file. We always read 800 bytes for every key, and the local
435
# transport natural expansion is 4096 bytes. So we have to have >8192
436
# bytes or we will trigger "buffer_all".
437
# We also want the 'missing' key to fall within the range that *did*
440
index = self.make_index(nodes=self.make_nodes(64))
441
# reset the transport log
442
del index._transport._activity[:]
443
# do a _lookup_keys_via_location call for the middle of the file, which
444
# is what bisection uses.
445
start_lookup = index._size // 2
446
result = index._lookup_keys_via_location(
447
[(start_lookup, ('40missing', ))])
448
# this should have asked for a readv request, with adjust_for_latency,
449
# and two regions: the header, and half-way into the file.
452
[(start_lookup, 800), (0, 200)], True, index._size),
454
index._transport._activity)
455
# and the result should be that the key cannot be present, because this
456
# is a trivial index.
457
self.assertEqual([((start_lookup, ('40missing', )), False)],
459
# And this should not have caused the file to be fully buffered
460
self.assertIs(None, index._nodes)
461
# And the regions of the file that have been parsed should be in the
462
# parsed_byte_map and the parsed_key_map
463
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
464
self.assertEqual([(None, self.make_key(26)),
465
(self.make_key(31), self.make_key(48))],
466
index._parsed_key_map)
468
def test_parsing_non_adjacent_data_trims(self):
469
index = self.make_index(nodes=self.make_nodes(64))
470
result = index._lookup_keys_via_location(
471
[(index._size // 2, ('40', ))])
472
# and the result should be that the key cannot be present, because key is
473
# in the middle of the observed data from a 4K read - the smallest transport
474
# will do today with this api.
475
self.assertEqual([((index._size // 2, ('40', )), False)],
477
# and we should have a parse map that includes the header and the
478
# region that was parsed after trimming.
479
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
480
self.assertEqual([(None, self.make_key(26)),
481
(self.make_key(31), self.make_key(48))],
482
index._parsed_key_map)
484
def test_parsing_data_handles_parsed_contained_regions(self):
485
# the following patten creates a parsed region that is wholly within a
486
# single result from the readv layer:
487
# .... single-read (readv-minimum-size) ...
488
# which then trims the start and end so the parsed size is < readv
490
# then a dual lookup (or a reference lookup for that matter) which
491
# abuts or overlaps the parsed region on both sides will need to
492
# discard the data in the middle, but parse the end as well.
494
# we test this by doing a single lookup to seed the data, then
495
# a lookup for two keys that are present, and adjacent -
496
# we except both to be found, and the parsed byte map to include the
497
# locations of both keys.
498
index = self.make_index(nodes=self.make_nodes(128))
499
result = index._lookup_keys_via_location(
500
[(index._size // 2, ('40', ))])
501
# and we should have a parse map that includes the header and the
502
# region that was parsed after trimming.
503
self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
504
self.assertEqual([(None, self.make_key(116)),
505
(self.make_key(35), self.make_key(51))],
506
index._parsed_key_map)
507
# now ask for two keys, right before and after the parsed region
508
result = index._lookup_keys_via_location(
509
[(11450, self.make_key(34)), (15707, self.make_key(52))])
511
((11450, self.make_key(34)),
512
(index, self.make_key(34), self.make_value(34))),
513
((15707, self.make_key(52)),
514
(index, self.make_key(52), self.make_value(52))),
517
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
519
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
520
# generate a big enough index that we only read some of it on a typical
522
index = self.make_index(nodes=self.make_nodes(64))
523
# lookup the keys in the middle of the file
524
result =index._lookup_keys_via_location(
525
[(index._size // 2, ('40', ))])
526
# check the parse map, this determines the test validity
527
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
528
self.assertEqual([(None, self.make_key(26)),
529
(self.make_key(31), self.make_key(48))],
530
index._parsed_key_map)
531
# reset the transport log
532
del index._transport._activity[:]
533
# now looking up a key in the portion of the file already parsed should
534
# not create a new transport request, and should return False (cannot
535
# be in the index) - even when the byte location we ask for is outside
537
result = index._lookup_keys_via_location(
539
self.assertEqual([((4000, ('40', )), False)],
541
self.assertEqual([], index._transport._activity)
543
def test_lookup_present_key_answers_without_io_when_map_permits(self):
544
# generate a big enough index that we only read some of it on a typical
546
index = self.make_index(nodes=self.make_nodes(64))
547
# lookup the keys in the middle of the file
548
result =index._lookup_keys_via_location(
549
[(index._size // 2, ('40', ))])
550
# check the parse map, this determines the test validity
551
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
552
self.assertEqual([(None, self.make_key(26)),
553
(self.make_key(31), self.make_key(48))],
554
index._parsed_key_map)
555
# reset the transport log
556
del index._transport._activity[:]
557
# now looking up a key in the portion of the file already parsed should
558
# not create a new transport request, and should return False (cannot
559
# be in the index) - even when the byte location we ask for is outside
562
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
564
[((4000, self.make_key(40)),
565
(index, self.make_key(40), self.make_value(40)))],
567
self.assertEqual([], index._transport._activity)
569
def test_lookup_key_below_probed_area(self):
570
# generate a big enough index that we only read some of it on a typical
572
index = self.make_index(nodes=self.make_nodes(64))
573
# ask for the key in the middle, but a key that is located in the
574
# unparsed region before the middle.
575
result =index._lookup_keys_via_location(
576
[(index._size // 2, ('30', ))])
577
# check the parse map, this determines the test validity
578
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
579
self.assertEqual([(None, self.make_key(26)),
580
(self.make_key(31), self.make_key(48))],
581
index._parsed_key_map)
582
self.assertEqual([((index._size // 2, ('30', )), -1)],
585
def test_lookup_key_above_probed_area(self):
586
# generate a big enough index that we only read some of it on a typical
588
index = self.make_index(nodes=self.make_nodes(64))
589
# ask for the key in the middle, but a key that is located in the
590
# unparsed region after the middle.
591
result =index._lookup_keys_via_location(
592
[(index._size // 2, ('50', ))])
593
# check the parse map, this determines the test validity
594
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
595
self.assertEqual([(None, self.make_key(26)),
596
(self.make_key(31), self.make_key(48))],
597
index._parsed_key_map)
598
self.assertEqual([((index._size // 2, ('50', )), +1)],
601
def test_lookup_key_resolves_references(self):
602
# generate a big enough index that we only read some of it on a typical
605
for counter in range(99):
606
nodes.append((self.make_key(counter), self.make_value(counter),
607
((self.make_key(counter + 20),),) ))
608
index = self.make_index(ref_lists=1, nodes=nodes)
609
# lookup a key in the middle that does not exist, so that when we can
610
# check that the referred-to-keys are not accessed automatically.
611
index_size = index._size
612
index_center = index_size // 2
613
result = index._lookup_keys_via_location(
614
[(index_center, ('40', ))])
615
# check the parse map - only the start and middle should have been
617
self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
618
self.assertEqual([(None, self.make_key(17)),
619
(self.make_key(44), self.make_key(5))],
620
index._parsed_key_map)
621
# and check the transport activity likewise.
623
[('readv', 'index', [(index_center, 800), (0, 200)], True,
625
index._transport._activity)
626
# reset the transport log for testing the reference lookup
627
del index._transport._activity[:]
628
# now looking up a key in the portion of the file already parsed should
629
# only perform IO to resolve its key references.
630
result = index._lookup_keys_via_location([(11000, self.make_key(45))])
632
[((11000, self.make_key(45)),
633
(index, self.make_key(45), self.make_value(45),
634
((self.make_key(65),),)))],
636
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
637
index._transport._activity)
639
def test_lookup_key_can_buffer_all(self):
641
for counter in range(64):
642
nodes.append((self.make_key(counter), self.make_value(counter),
643
((self.make_key(counter + 20),),) ))
644
index = self.make_index(ref_lists=1, nodes=nodes)
645
# lookup a key in the middle that does not exist, so that when we can
646
# check that the referred-to-keys are not accessed automatically.
647
index_size = index._size
648
index_center = index_size // 2
649
result = index._lookup_keys_via_location([(index_center, ('40', ))])
650
# check the parse map - only the start and middle should have been
652
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
653
self.assertEqual([(None, self.make_key(25)),
654
(self.make_key(37), self.make_key(52))],
655
index._parsed_key_map)
656
# and check the transport activity likewise.
658
[('readv', 'index', [(index_center, 800), (0, 200)], True,
660
index._transport._activity)
661
# reset the transport log for testing the reference lookup
662
del index._transport._activity[:]
663
# now looking up a key in the portion of the file already parsed should
664
# only perform IO to resolve its key references.
665
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
667
[((7000, self.make_key(40)),
668
(index, self.make_key(40), self.make_value(40),
669
((self.make_key(60),),)))],
671
# Resolving the references would have required more data read, and we
672
# are already above the 50% threshold, so it triggered a _buffer_all
673
self.assertEqual([('get', 'index')], index._transport._activity)
344
index = GraphIndex(trans, 'name')
675
346
def test_iter_all_entries_empty(self):
676
347
index = self.make_index()
695
366
(index, ('ref', ), 'refdata', ((), ))]),
696
367
set(index.iter_all_entries()))
698
def test_iter_entries_buffers_once(self):
699
index = self.make_index(nodes=self.make_nodes(2))
700
# reset the transport log
701
del index._transport._activity[:]
702
self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
703
set(index.iter_entries([self.make_key(1)])))
704
# We should have requested reading the header bytes
705
# But not needed any more than that because it would have triggered a
708
('readv', 'index', [(0, 200)], True, index._size),
710
index._transport._activity)
711
# And that should have been enough to trigger reading the whole index
713
self.assertIsNot(None, index._nodes)
715
def test_iter_entries_buffers_by_bytes_read(self):
716
index = self.make_index(nodes=self.make_nodes(64))
717
list(index.iter_entries([self.make_key(10)]))
718
# The first time through isn't enough to trigger a buffer all
719
self.assertIs(None, index._nodes)
720
self.assertEqual(4096, index._bytes_read)
721
# Grabbing a key in that same page won't trigger a buffer all, as we
722
# still haven't read 50% of the file
723
list(index.iter_entries([self.make_key(11)]))
724
self.assertIs(None, index._nodes)
725
self.assertEqual(4096, index._bytes_read)
726
# We haven't read more data, so reading outside the range won't trigger
727
# a buffer all right away
728
list(index.iter_entries([self.make_key(40)]))
729
self.assertIs(None, index._nodes)
730
self.assertEqual(8192, index._bytes_read)
731
# On the next pass, we will not trigger buffer all if the key is
732
# available without reading more
733
list(index.iter_entries([self.make_key(32)]))
734
self.assertIs(None, index._nodes)
735
# But if we *would* need to read more to resolve it, then we will
737
list(index.iter_entries([self.make_key(60)]))
738
self.assertIsNot(None, index._nodes)
740
def test_iter_entries_references_resolved(self):
741
index = self.make_index(1, nodes=[
742
(('name', ), 'data', ([('ref', ), ('ref', )], )),
743
(('ref', ), 'refdata', ([], ))])
744
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
745
(index, ('ref', ), 'refdata', ((), ))]),
746
set(index.iter_entries([('name',), ('ref',)])))
748
def test_iter_entries_references_2_refs_resolved(self):
749
index = self.make_index(2, nodes=[
750
(('name', ), 'data', ([('ref', )], [('ref', )])),
751
(('ref', ), 'refdata', ([], []))])
752
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
753
(index, ('ref', ), 'refdata', ((), ()))]),
754
set(index.iter_entries([('name',), ('ref',)])))
756
369
def test_iteration_absent_skipped(self):
757
370
index = self.make_index(1, nodes=[
758
371
(('name', ), 'data', ([('ref', )], ))])
922
494
index = self.make_index(nodes=[(('key', ), 'value', ())])
925
# XXX: external_references tests are duplicated in test_btree_index. We
926
# probably should have per_graph_index tests...
927
def test_external_references_no_refs(self):
928
index = self.make_index(ref_lists=0, nodes=[])
929
self.assertRaises(ValueError, index.external_references, 0)
931
def test_external_references_no_results(self):
932
index = self.make_index(ref_lists=1, nodes=[
933
(('key',), 'value', ([],))])
934
self.assertEqual(set(), index.external_references(0))
936
def test_external_references_missing_ref(self):
937
missing_key = ('missing',)
938
index = self.make_index(ref_lists=1, nodes=[
939
(('key',), 'value', ([missing_key],))])
940
self.assertEqual(set([missing_key]), index.external_references(0))
942
def test_external_references_multiple_ref_lists(self):
943
missing_key = ('missing',)
944
index = self.make_index(ref_lists=2, nodes=[
945
(('key',), 'value', ([], [missing_key]))])
946
self.assertEqual(set([]), index.external_references(0))
947
self.assertEqual(set([missing_key]), index.external_references(1))
949
def test_external_references_two_records(self):
950
index = self.make_index(ref_lists=1, nodes=[
951
(('key-1',), 'value', ([('key-2',)],)),
952
(('key-2',), 'value', ([],)),
954
self.assertEqual(set([]), index.external_references(0))
956
def test__find_ancestors(self):
959
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
960
(key1, 'value', ([key2],)),
961
(key2, 'value', ([],)),
965
search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
966
self.assertEqual({key1: (key2,)}, parent_map)
967
self.assertEqual(set(), missing_keys)
968
self.assertEqual(set([key2]), search_keys)
969
search_keys = index._find_ancestors(search_keys, 0, parent_map,
971
self.assertEqual({key1: (key2,), key2: ()}, parent_map)
972
self.assertEqual(set(), missing_keys)
973
self.assertEqual(set(), search_keys)
975
def test__find_ancestors_w_missing(self):
979
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
980
(key1, 'value', ([key2],)),
981
(key2, 'value', ([],)),
985
search_keys = index._find_ancestors([key2, key3], 0, parent_map,
987
self.assertEqual({key2: ()}, parent_map)
988
self.assertEqual(set([key3]), missing_keys)
989
self.assertEqual(set(), search_keys)
991
def test__find_ancestors_dont_search_known(self):
995
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
996
(key1, 'value', ([key2],)),
997
(key2, 'value', ([key3],)),
998
(key3, 'value', ([],)),
1000
# We already know about key2, so we won't try to search for key3
1001
parent_map = {key2: (key3,)}
1002
missing_keys = set()
1003
search_keys = index._find_ancestors([key1], 0, parent_map,
1005
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1006
self.assertEqual(set(), missing_keys)
1007
self.assertEqual(set(), search_keys)
1010
498
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1012
500
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1013
501
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
1014
for key, value, references in nodes:
1015
builder.add_node(key, value, references)
502
for node, value, references in nodes:
503
builder.add_node(node, value, references)
1016
504
stream = builder.finish()
1017
505
trans = self.get_transport()
1018
size = trans.put_file(name, stream)
1019
return GraphIndex(trans, name, size)
1021
def make_combined_index_with_missing(self, missing=['1', '2']):
1022
"""Create a CombinedGraphIndex which will have missing indexes.
1024
This creates a CGI which thinks it has 2 indexes, however they have
1025
been deleted. If CGI._reload_func() is called, then it will repopulate
1028
:param missing: The underlying indexes to delete
1029
:return: (CombinedGraphIndex, reload_counter)
1031
index1 = self.make_index('1', nodes=[(('1',), '', ())])
1032
index2 = self.make_index('2', nodes=[(('2',), '', ())])
1033
index3 = self.make_index('3', nodes=[
1037
# total_reloads, num_changed, num_unchanged
1038
reload_counter = [0, 0, 0]
1040
reload_counter[0] += 1
1041
new_indices = [index3]
1042
if index._indices == new_indices:
1043
reload_counter[2] += 1
1045
reload_counter[1] += 1
1046
index._indices[:] = new_indices
1048
index = CombinedGraphIndex([index1, index2], reload_func=reload)
1049
trans = self.get_transport()
1050
for fname in missing:
1052
return index, reload_counter
506
trans.put_file(name, stream)
507
return GraphIndex(trans, name)
1054
509
def test_open_missing_index_no_error(self):
1055
510
trans = self.get_transport()
1056
index1 = GraphIndex(trans, 'missing', 100)
511
index1 = GraphIndex(trans, 'missing')
1057
512
index = CombinedGraphIndex([index1])
1059
514
def test_add_index(self):
1194
635
index = CombinedGraphIndex([])
1195
636
index.validate()
1197
def test_key_count_reloads(self):
1198
index, reload_counter = self.make_combined_index_with_missing()
1199
self.assertEqual(2, index.key_count())
1200
self.assertEqual([1, 1, 0], reload_counter)
1202
def test_key_count_no_reload(self):
1203
index, reload_counter = self.make_combined_index_with_missing()
1204
index._reload_func = None
1205
# Without a _reload_func we just raise the exception
1206
self.assertRaises(errors.NoSuchFile, index.key_count)
1208
def test_key_count_reloads_and_fails(self):
1209
# We have deleted all underlying indexes, so we will try to reload, but
1210
# still fail. This is mostly to test we don't get stuck in an infinite
1211
# loop trying to reload
1212
index, reload_counter = self.make_combined_index_with_missing(
1214
self.assertRaises(errors.NoSuchFile, index.key_count)
1215
self.assertEqual([2, 1, 1], reload_counter)
1217
def test_iter_entries_reloads(self):
1218
index, reload_counter = self.make_combined_index_with_missing()
1219
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1220
index3 = index._indices[0]
1221
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1223
self.assertEqual([1, 1, 0], reload_counter)
1225
def test_iter_entries_reloads_midway(self):
1226
# The first index still looks present, so we get interrupted mid-way
1228
index, reload_counter = self.make_combined_index_with_missing(['2'])
1229
index1, index2 = index._indices
1230
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1231
index3 = index._indices[0]
1232
# We had already yielded '1', so we just go on to the next, we should
1233
# not yield '1' twice.
1234
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1236
self.assertEqual([1, 1, 0], reload_counter)
1238
def test_iter_entries_no_reload(self):
1239
index, reload_counter = self.make_combined_index_with_missing()
1240
index._reload_func = None
1241
# Without a _reload_func we just raise the exception
1242
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1244
def test_iter_entries_reloads_and_fails(self):
1245
index, reload_counter = self.make_combined_index_with_missing(
1247
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1248
self.assertEqual([2, 1, 1], reload_counter)
1250
def test_iter_all_entries_reloads(self):
1251
index, reload_counter = self.make_combined_index_with_missing()
1252
result = list(index.iter_all_entries())
1253
index3 = index._indices[0]
1254
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1256
self.assertEqual([1, 1, 0], reload_counter)
1258
def test_iter_all_entries_reloads_midway(self):
1259
index, reload_counter = self.make_combined_index_with_missing(['2'])
1260
index1, index2 = index._indices
1261
result = list(index.iter_all_entries())
1262
index3 = index._indices[0]
1263
# We had already yielded '1', so we just go on to the next, we should
1264
# not yield '1' twice.
1265
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1267
self.assertEqual([1, 1, 0], reload_counter)
1269
def test_iter_all_entries_no_reload(self):
1270
index, reload_counter = self.make_combined_index_with_missing()
1271
index._reload_func = None
1272
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1274
def test_iter_all_entries_reloads_and_fails(self):
1275
index, reload_counter = self.make_combined_index_with_missing(
1277
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1279
def test_iter_entries_prefix_reloads(self):
1280
index, reload_counter = self.make_combined_index_with_missing()
1281
result = list(index.iter_entries_prefix([('1',)]))
1282
index3 = index._indices[0]
1283
self.assertEqual([(index3, ('1',), '')], result)
1284
self.assertEqual([1, 1, 0], reload_counter)
1286
def test_iter_entries_prefix_reloads_midway(self):
1287
index, reload_counter = self.make_combined_index_with_missing(['2'])
1288
index1, index2 = index._indices
1289
result = list(index.iter_entries_prefix([('1',)]))
1290
index3 = index._indices[0]
1291
# We had already yielded '1', so we just go on to the next, we should
1292
# not yield '1' twice.
1293
self.assertEqual([(index1, ('1',), '')], result)
1294
self.assertEqual([1, 1, 0], reload_counter)
1296
def test_iter_entries_prefix_no_reload(self):
1297
index, reload_counter = self.make_combined_index_with_missing()
1298
index._reload_func = None
1299
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1302
def test_iter_entries_prefix_reloads_and_fails(self):
1303
index, reload_counter = self.make_combined_index_with_missing(
1305
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1308
def test_validate_reloads(self):
1309
index, reload_counter = self.make_combined_index_with_missing()
1311
self.assertEqual([1, 1, 0], reload_counter)
1313
def test_validate_reloads_midway(self):
1314
index, reload_counter = self.make_combined_index_with_missing(['2'])
1317
def test_validate_no_reload(self):
1318
index, reload_counter = self.make_combined_index_with_missing()
1319
index._reload_func = None
1320
self.assertRaises(errors.NoSuchFile, index.validate)
1322
def test_validate_reloads_and_fails(self):
1323
index, reload_counter = self.make_combined_index_with_missing(
1325
self.assertRaises(errors.NoSuchFile, index.validate)
1327
def test_find_ancestors_across_indexes(self):
1332
index1 = self.make_index('12', ref_lists=1, nodes=[
1333
(key1, 'value', ([],)),
1334
(key2, 'value', ([key1],)),
1336
index2 = self.make_index('34', ref_lists=1, nodes=[
1337
(key3, 'value', ([key2],)),
1338
(key4, 'value', ([key3],)),
1340
c_index = CombinedGraphIndex([index1, index2])
1341
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1342
self.assertEqual({key1: ()}, parent_map)
1343
self.assertEqual(set(), missing_keys)
1344
# Now look for a key from index2 which requires us to find the key in
1345
# the second index, and then continue searching for parents in the
1347
parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1348
self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1349
self.assertEqual(set(), missing_keys)
1351
def test_find_ancestors_missing_keys(self):
1356
index1 = self.make_index('12', ref_lists=1, nodes=[
1357
(key1, 'value', ([],)),
1358
(key2, 'value', ([key1],)),
1360
index2 = self.make_index('34', ref_lists=1, nodes=[
1361
(key3, 'value', ([key2],)),
1363
c_index = CombinedGraphIndex([index1, index2])
1364
# Searching for a key which is actually not present at all should
1365
# eventually converge
1366
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1367
self.assertEqual({}, parent_map)
1368
self.assertEqual(set([key4]), missing_keys)
1370
def test_find_ancestors_no_indexes(self):
1371
c_index = CombinedGraphIndex([])
1373
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1374
self.assertEqual({}, parent_map)
1375
self.assertEqual(set([key1]), missing_keys)
1377
def test_find_ancestors_ghost_parent(self):
1382
index1 = self.make_index('12', ref_lists=1, nodes=[
1383
(key1, 'value', ([],)),
1384
(key2, 'value', ([key1],)),
1386
index2 = self.make_index('34', ref_lists=1, nodes=[
1387
(key4, 'value', ([key2, key3],)),
1389
c_index = CombinedGraphIndex([index1, index2])
1390
# Searching for a key which is actually not present at all should
1391
# eventually converge
1392
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1393
self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1395
self.assertEqual(set([key3]), missing_keys)
1397
def test__find_ancestors_empty_index(self):
1398
index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1400
missing_keys = set()
1401
search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1403
self.assertEqual(set(), search_keys)
1404
self.assertEqual({}, parent_map)
1405
self.assertEqual(set([('one',), ('two',)]), missing_keys)
1408
639
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
added
removed
bzrlib/tests/test_index.py
