362
388
size = trans.put_file('index', stream)
363
389
return GraphIndex(trans, 'index', size)
391
def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
393
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
394
for key, value, references in nodes:
395
builder.add_node(key, value, references)
396
content = builder.finish().read()
398
trans = self.get_transport()
399
trans.put_bytes('index', (' '*offset) + content)
400
return GraphIndex(trans, 'index', size, offset=offset)
402
def test_clear_cache(self):
403
index = self.make_index()
404
# For now, we just want to make sure the api is available. As this is
405
# old code, we don't really worry if it *does* anything.
365
408
def test_open_bad_index_no_error(self):
366
409
trans = self.get_transport()
367
410
trans.put_bytes('name', "not an index\n")
368
411
index = GraphIndex(trans, 'name', 13)
413
def test_with_offset(self):
414
nodes = self.make_nodes(200)
415
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
416
self.assertEqual(200, index.key_count())
418
def test_buffer_all_with_offset(self):
419
nodes = self.make_nodes(200)
420
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
422
self.assertEqual(200, index.key_count())
424
def test_side_effect_buffering_with_offset(self):
425
nodes = self.make_nodes(20)
426
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
427
index._transport.recommended_page_size = lambda:64*1024
428
subset_nodes = [nodes[0][0], nodes[10][0], nodes[19][0]]
429
entries = [n[1] for n in index.iter_entries(subset_nodes)]
430
self.assertEqual(sorted(subset_nodes), sorted(entries))
431
self.assertEqual(20, index.key_count())
370
433
def test_open_sets_parsed_map_empty(self):
371
434
index = self.make_index()
372
435
self.assertEqual([], index._parsed_byte_map)
373
436
self.assertEqual([], index._parsed_key_map)
438
def test_key_count_buffers(self):
439
index = self.make_index(nodes=self.make_nodes(2))
440
# reset the transport log
441
del index._transport._activity[:]
442
self.assertEqual(2, index.key_count())
443
# We should have requested reading the header bytes
445
('readv', 'index', [(0, 200)], True, index._size),
447
index._transport._activity)
448
# And that should have been enough to trigger reading the whole index
450
self.assertIsNot(None, index._nodes)
452
def test_lookup_key_via_location_buffers(self):
453
index = self.make_index()
454
# reset the transport log
455
del index._transport._activity[:]
456
# do a _lookup_keys_via_location call for the middle of the file, which
457
# is what bisection uses.
458
result = index._lookup_keys_via_location(
459
[(index._size // 2, ('missing', ))])
460
# this should have asked for a readv request, with adjust_for_latency,
461
# and two regions: the header, and half-way into the file.
463
('readv', 'index', [(30, 30), (0, 200)], True, 60),
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([((index._size // 2, ('missing', )), False)],
470
# And this should have caused the file to be fully buffered
471
self.assertIsNot(None, index._nodes)
472
self.assertEqual([], index._parsed_byte_map)
375
474
def test_first_lookup_key_via_location(self):
376
index = self.make_index()
475
# We need enough data so that the _HEADER_READV doesn't consume the
476
# whole file. We always read 800 bytes for every key, and the local
477
# transport natural expansion is 4096 bytes. So we have to have >8192
478
# bytes or we will trigger "buffer_all".
479
# We also want the 'missing' key to fall within the range that *did*
482
index = self.make_index(nodes=self.make_nodes(64))
377
483
# reset the transport log
378
484
del index._transport._activity[:]
379
485
# do a _lookup_keys_via_location call for the middle of the file, which
380
486
# is what bisection uses.
487
start_lookup = index._size // 2
381
488
result = index._lookup_keys_via_location(
382
[(index._size // 2, ('missing', ))])
489
[(start_lookup, ('40missing', ))])
383
490
# this should have asked for a readv request, with adjust_for_latency,
384
491
# and two regions: the header, and half-way into the file.
385
492
self.assertEqual([
386
('readv', 'index', [(30, 30), (0, 200)], True, 60),
494
[(start_lookup, 800), (0, 200)], True, index._size),
388
496
index._transport._activity)
389
497
# and the result should be that the key cannot be present, because this
390
498
# is a trivial index.
391
self.assertEqual([((index._size // 2, ('missing', )), False)],
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)
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.
411
('readv', 'index', [(36, 36), (0, 200)], True, 72),
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)],
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)
499
self.assertEqual([((start_lookup, ('40missing', )), False)],
501
# And this should not have caused the file to be fully buffered
502
self.assertIs(None, index._nodes)
503
# And the regions of the file that have been parsed should be in the
504
# parsed_byte_map and the parsed_key_map
505
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
506
self.assertEqual([(None, self.make_key(26)),
507
(self.make_key(31), self.make_key(48))],
508
index._parsed_key_map)
422
510
def test_parsing_non_adjacent_data_trims(self):
423
# generate a big enough index that we only read some of it on a typical
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)
511
index = self.make_index(nodes=self.make_nodes(64))
431
512
result = index._lookup_keys_via_location(
432
513
[(index._size // 2, ('40', ))])
433
514
# and the result should be that the key cannot be present, because key is
448
530
# which then trims the start and end so the parsed size is < readv
450
532
# 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
533
# abuts or overlaps the parsed region on both sides will need to
452
534
# discard the data in the middle, but parse the end as well.
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 -
536
# we test this by doing a single lookup to seed the data, then
537
# a lookup for two keys that are present, and adjacent -
456
538
# we except both to be found, and the parsed byte map to include the
457
539
# locations of both keys.
459
def make_key(number):
460
return (str(number) + 'X'*100,)
461
def make_value(number):
463
for counter in range(128):
464
nodes.append((make_key(counter), make_value(counter), ()))
465
index = self.make_index(nodes=nodes)
540
index = self.make_index(nodes=self.make_nodes(128))
466
541
result = index._lookup_keys_via_location(
467
542
[(index._size // 2, ('40', ))])
468
543
# and we should have a parse map that includes the header and the
469
544
# 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))],
545
self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
546
self.assertEqual([(None, self.make_key(116)),
547
(self.make_key(35), self.make_key(51))],
472
548
index._parsed_key_map)
473
549
# now ask for two keys, right before and after the parsed region
474
550
result = index._lookup_keys_via_location(
475
[(11450, make_key(34)), (15534, make_key(52))])
551
[(11450, self.make_key(34)), (15707, self.make_key(52))])
476
552
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))),
553
((11450, self.make_key(34)),
554
(index, self.make_key(34), self.make_value(34))),
555
((15707, self.make_key(52)),
556
(index, self.make_key(52), self.make_value(52))),
481
self.assertEqual([(0, 3991), (9975, 17799)], index._parsed_byte_map)
559
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
483
561
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
484
562
# generate a big enough index that we only read some of it on a typical
485
563
# bisection lookup.
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)
564
index = self.make_index(nodes=self.make_nodes(64))
492
565
# lookup the keys in the middle of the file
493
566
result =index._lookup_keys_via_location(
494
567
[(index._size // 2, ('40', ))])
495
568
# 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))],
569
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
570
self.assertEqual([(None, self.make_key(26)),
571
(self.make_key(31), self.make_key(48))],
498
572
index._parsed_key_map)
499
573
# reset the transport log
500
574
del index._transport._activity[:]
584
644
# generate a big enough index that we only read some of it on a typical
585
645
# bisection lookup.
587
def make_key(number):
588
return (str(number) + 'X'*100,)
589
def make_value(number):
590
return str(number) + 'Y'*100
647
for counter in range(99):
648
nodes.append((self.make_key(counter), self.make_value(counter),
649
((self.make_key(counter + 20),),) ))
650
index = self.make_index(ref_lists=1, nodes=nodes)
651
# lookup a key in the middle that does not exist, so that when we can
652
# check that the referred-to-keys are not accessed automatically.
653
index_size = index._size
654
index_center = index_size // 2
655
result = index._lookup_keys_via_location(
656
[(index_center, ('40', ))])
657
# check the parse map - only the start and middle should have been
659
self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
660
self.assertEqual([(None, self.make_key(17)),
661
(self.make_key(44), self.make_key(5))],
662
index._parsed_key_map)
663
# and check the transport activity likewise.
665
[('readv', 'index', [(index_center, 800), (0, 200)], True,
667
index._transport._activity)
668
# reset the transport log for testing the reference lookup
669
del index._transport._activity[:]
670
# now looking up a key in the portion of the file already parsed should
671
# only perform IO to resolve its key references.
672
result = index._lookup_keys_via_location([(11000, self.make_key(45))])
674
[((11000, self.make_key(45)),
675
(index, self.make_key(45), self.make_value(45),
676
((self.make_key(65),),)))],
678
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
679
index._transport._activity)
681
def test_lookup_key_can_buffer_all(self):
591
683
for counter in range(64):
592
nodes.append((make_key(counter), make_value(counter),
593
((make_key(counter + 20),),) ))
684
nodes.append((self.make_key(counter), self.make_value(counter),
685
((self.make_key(counter + 20),),) ))
594
686
index = self.make_index(ref_lists=1, nodes=nodes)
595
687
# lookup a key in the middle that does not exist, so that when we can
596
688
# check that the referred-to-keys are not accessed automatically.
597
result =index._lookup_keys_via_location(
598
[(index._size // 2, ('40', ))])
689
index_size = index._size
690
index_center = index_size // 2
691
result = index._lookup_keys_via_location([(index_center, ('40', ))])
599
692
# check the parse map - only the start and middle should have been
601
694
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
602
self.assertEqual([(None, make_key(25)), (make_key(37), make_key(52))],
695
self.assertEqual([(None, self.make_key(25)),
696
(self.make_key(37), self.make_key(52))],
603
697
index._parsed_key_map)
604
698
# and check the transport activity likewise.
605
699
self.assertEqual(
606
[('readv', 'index', [(7906, 800), (0, 200)], True, 15813)],
700
[('readv', 'index', [(index_center, 800), (0, 200)], True,
607
702
index._transport._activity)
608
703
# reset the transport log for testing the reference lookup
609
704
del index._transport._activity[:]
610
705
# now looking up a key in the portion of the file already parsed should
611
706
# only perform IO to resolve its key references.
612
result = index._lookup_keys_via_location([(4000, make_key(40))])
707
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
613
708
self.assertEqual(
614
[((4000, make_key(40)),
615
(index, make_key(40), make_value(40), ((make_key(60),),)))],
709
[((7000, self.make_key(40)),
710
(index, self.make_key(40), self.make_value(40),
711
((self.make_key(60),),)))],
617
self.assertEqual([('readv', 'index', [(11976, 800)], True, 15813)],
618
index._transport._activity)
713
# Resolving the references would have required more data read, and we
714
# are already above the 50% threshold, so it triggered a _buffer_all
715
self.assertEqual([('get', 'index')], index._transport._activity)
620
717
def test_iter_all_entries_empty(self):
621
718
index = self.make_index()
640
737
(index, ('ref', ), 'refdata', ((), ))]),
641
738
set(index.iter_all_entries()))
740
def test_iter_entries_buffers_once(self):
741
index = self.make_index(nodes=self.make_nodes(2))
742
# reset the transport log
743
del index._transport._activity[:]
744
self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
745
set(index.iter_entries([self.make_key(1)])))
746
# We should have requested reading the header bytes
747
# But not needed any more than that because it would have triggered a
750
('readv', 'index', [(0, 200)], True, index._size),
752
index._transport._activity)
753
# And that should have been enough to trigger reading the whole index
755
self.assertIsNot(None, index._nodes)
757
def test_iter_entries_buffers_by_bytes_read(self):
758
index = self.make_index(nodes=self.make_nodes(64))
759
list(index.iter_entries([self.make_key(10)]))
760
# The first time through isn't enough to trigger a buffer all
761
self.assertIs(None, index._nodes)
762
self.assertEqual(4096, index._bytes_read)
763
# Grabbing a key in that same page won't trigger a buffer all, as we
764
# still haven't read 50% of the file
765
list(index.iter_entries([self.make_key(11)]))
766
self.assertIs(None, index._nodes)
767
self.assertEqual(4096, index._bytes_read)
768
# We haven't read more data, so reading outside the range won't trigger
769
# a buffer all right away
770
list(index.iter_entries([self.make_key(40)]))
771
self.assertIs(None, index._nodes)
772
self.assertEqual(8192, index._bytes_read)
773
# On the next pass, we will not trigger buffer all if the key is
774
# available without reading more
775
list(index.iter_entries([self.make_key(32)]))
776
self.assertIs(None, index._nodes)
777
# But if we *would* need to read more to resolve it, then we will
779
list(index.iter_entries([self.make_key(60)]))
780
self.assertIsNot(None, index._nodes)
643
782
def test_iter_entries_references_resolved(self):
644
783
index = self.make_index(1, nodes=[
645
784
(('name', ), 'data', ([('ref', ), ('ref', )], )),
802
964
index = self.make_index(nodes=[(('key', ), 'value', ())])
967
# XXX: external_references tests are duplicated in test_btree_index. We
968
# probably should have per_graph_index tests...
969
def test_external_references_no_refs(self):
970
index = self.make_index(ref_lists=0, nodes=[])
971
self.assertRaises(ValueError, index.external_references, 0)
973
def test_external_references_no_results(self):
974
index = self.make_index(ref_lists=1, nodes=[
975
(('key',), 'value', ([],))])
976
self.assertEqual(set(), index.external_references(0))
978
def test_external_references_missing_ref(self):
979
missing_key = ('missing',)
980
index = self.make_index(ref_lists=1, nodes=[
981
(('key',), 'value', ([missing_key],))])
982
self.assertEqual(set([missing_key]), index.external_references(0))
984
def test_external_references_multiple_ref_lists(self):
985
missing_key = ('missing',)
986
index = self.make_index(ref_lists=2, nodes=[
987
(('key',), 'value', ([], [missing_key]))])
988
self.assertEqual(set([]), index.external_references(0))
989
self.assertEqual(set([missing_key]), index.external_references(1))
991
def test_external_references_two_records(self):
992
index = self.make_index(ref_lists=1, nodes=[
993
(('key-1',), 'value', ([('key-2',)],)),
994
(('key-2',), 'value', ([],)),
996
self.assertEqual(set([]), index.external_references(0))
998
def test__find_ancestors(self):
1001
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1002
(key1, 'value', ([key2],)),
1003
(key2, 'value', ([],)),
1006
missing_keys = set()
1007
search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1008
self.assertEqual({key1: (key2,)}, parent_map)
1009
self.assertEqual(set(), missing_keys)
1010
self.assertEqual(set([key2]), search_keys)
1011
search_keys = index._find_ancestors(search_keys, 0, parent_map,
1013
self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1014
self.assertEqual(set(), missing_keys)
1015
self.assertEqual(set(), search_keys)
1017
def test__find_ancestors_w_missing(self):
1021
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1022
(key1, 'value', ([key2],)),
1023
(key2, 'value', ([],)),
1026
missing_keys = set()
1027
search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1029
self.assertEqual({key2: ()}, parent_map)
1030
self.assertEqual(set([key3]), missing_keys)
1031
self.assertEqual(set(), search_keys)
1033
def test__find_ancestors_dont_search_known(self):
1037
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1038
(key1, 'value', ([key2],)),
1039
(key2, 'value', ([key3],)),
1040
(key3, 'value', ([],)),
1042
# We already know about key2, so we won't try to search for key3
1043
parent_map = {key2: (key3,)}
1044
missing_keys = set()
1045
search_keys = index._find_ancestors([key1], 0, parent_map,
1047
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1048
self.assertEqual(set(), missing_keys)
1049
self.assertEqual(set(), search_keys)
1051
def test_supports_unlimited_cache(self):
1052
builder = GraphIndexBuilder(0, key_elements=1)
1053
stream = builder.finish()
1054
trans = get_transport(self.get_url())
1055
size = trans.put_file('index', stream)
1056
# It doesn't matter what unlimited_cache does here, just that it can be
1058
index = GraphIndex(trans, 'index', size, unlimited_cache=True)
806
1061
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
957
1269
index = CombinedGraphIndex([])
958
1270
index.validate()
1272
def test_key_count_reloads(self):
1273
index, reload_counter = self.make_combined_index_with_missing()
1274
self.assertEqual(2, index.key_count())
1275
self.assertEqual([1, 1, 0], reload_counter)
1277
def test_key_count_no_reload(self):
1278
index, reload_counter = self.make_combined_index_with_missing()
1279
index._reload_func = None
1280
# Without a _reload_func we just raise the exception
1281
self.assertRaises(errors.NoSuchFile, index.key_count)
1283
def test_key_count_reloads_and_fails(self):
1284
# We have deleted all underlying indexes, so we will try to reload, but
1285
# still fail. This is mostly to test we don't get stuck in an infinite
1286
# loop trying to reload
1287
index, reload_counter = self.make_combined_index_with_missing(
1289
self.assertRaises(errors.NoSuchFile, index.key_count)
1290
self.assertEqual([2, 1, 1], reload_counter)
1292
def test_iter_entries_reloads(self):
1293
index, reload_counter = self.make_combined_index_with_missing()
1294
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1295
index3 = index._indices[0]
1296
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1298
self.assertEqual([1, 1, 0], reload_counter)
1300
def test_iter_entries_reloads_midway(self):
1301
# The first index still looks present, so we get interrupted mid-way
1303
index, reload_counter = self.make_combined_index_with_missing(['2'])
1304
index1, index2 = index._indices
1305
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1306
index3 = index._indices[0]
1307
# We had already yielded '1', so we just go on to the next, we should
1308
# not yield '1' twice.
1309
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1311
self.assertEqual([1, 1, 0], reload_counter)
1313
def test_iter_entries_no_reload(self):
1314
index, reload_counter = self.make_combined_index_with_missing()
1315
index._reload_func = None
1316
# Without a _reload_func we just raise the exception
1317
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1319
def test_iter_entries_reloads_and_fails(self):
1320
index, reload_counter = self.make_combined_index_with_missing(
1322
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1323
self.assertEqual([2, 1, 1], reload_counter)
1325
def test_iter_all_entries_reloads(self):
1326
index, reload_counter = self.make_combined_index_with_missing()
1327
result = list(index.iter_all_entries())
1328
index3 = index._indices[0]
1329
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1331
self.assertEqual([1, 1, 0], reload_counter)
1333
def test_iter_all_entries_reloads_midway(self):
1334
index, reload_counter = self.make_combined_index_with_missing(['2'])
1335
index1, index2 = index._indices
1336
result = list(index.iter_all_entries())
1337
index3 = index._indices[0]
1338
# We had already yielded '1', so we just go on to the next, we should
1339
# not yield '1' twice.
1340
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1342
self.assertEqual([1, 1, 0], reload_counter)
1344
def test_iter_all_entries_no_reload(self):
1345
index, reload_counter = self.make_combined_index_with_missing()
1346
index._reload_func = None
1347
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1349
def test_iter_all_entries_reloads_and_fails(self):
1350
index, reload_counter = self.make_combined_index_with_missing(
1352
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1354
def test_iter_entries_prefix_reloads(self):
1355
index, reload_counter = self.make_combined_index_with_missing()
1356
result = list(index.iter_entries_prefix([('1',)]))
1357
index3 = index._indices[0]
1358
self.assertEqual([(index3, ('1',), '')], result)
1359
self.assertEqual([1, 1, 0], reload_counter)
1361
def test_iter_entries_prefix_reloads_midway(self):
1362
index, reload_counter = self.make_combined_index_with_missing(['2'])
1363
index1, index2 = index._indices
1364
result = list(index.iter_entries_prefix([('1',)]))
1365
index3 = index._indices[0]
1366
# We had already yielded '1', so we just go on to the next, we should
1367
# not yield '1' twice.
1368
self.assertEqual([(index1, ('1',), '')], result)
1369
self.assertEqual([1, 1, 0], reload_counter)
1371
def test_iter_entries_prefix_no_reload(self):
1372
index, reload_counter = self.make_combined_index_with_missing()
1373
index._reload_func = None
1374
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1377
def test_iter_entries_prefix_reloads_and_fails(self):
1378
index, reload_counter = self.make_combined_index_with_missing(
1380
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1384
def make_index_with_simple_nodes(self, name, num_nodes=1):
1385
"""Make an index named after 'name', with keys named after 'name' too.
1387
Nodes will have a value of '' and no references.
1390
(('index-%s-key-%s' % (name, n),), '', ())
1391
for n in range(1, num_nodes+1)]
1392
return self.make_index('index-%s' % name, 0, nodes=nodes)
1394
def test_reorder_after_iter_entries(self):
1395
# Four indices: [key1] in index1, [key2,key3] in index2, [] in index3,
1397
index = CombinedGraphIndex([])
1398
index.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
1399
index.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
1400
index.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
1401
index.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
1402
index1, index2, index3, index4 = index._indices
1403
# Query a key from index4 and index2.
1404
self.assertLength(2, list(index.iter_entries(
1405
[('index-4-key-1',), ('index-2-key-1',)])))
1406
# Now index2 and index4 should be moved to the front (and index1 should
1407
# still be before index3).
1408
self.assertEqual([index2, index4, index1, index3], index._indices)
1409
self.assertEqual(['2', '4', '1', '3'], index._index_names)
1411
def test_reorder_propagates_to_siblings(self):
1412
# Two CombinedGraphIndex objects, with the same number of indicies with
1414
cgi1 = CombinedGraphIndex([])
1415
cgi2 = CombinedGraphIndex([])
1416
cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
1417
cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
1418
cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
1419
cgi2.insert_index(1, self.make_index_with_simple_nodes('2-2'), 'two')
1420
index2_1, index2_2 = cgi2._indices
1421
cgi1.set_sibling_indices([cgi2])
1422
# Trigger a reordering in cgi1. cgi2 will be reordered as well.
1423
list(cgi1.iter_entries([('index-1-2-key-1',)]))
1424
self.assertEqual([index2_2, index2_1], cgi2._indices)
1425
self.assertEqual(['two', 'one'], cgi2._index_names)
1427
def test_validate_reloads(self):
1428
index, reload_counter = self.make_combined_index_with_missing()
1430
self.assertEqual([1, 1, 0], reload_counter)
1432
def test_validate_reloads_midway(self):
1433
index, reload_counter = self.make_combined_index_with_missing(['2'])
1436
def test_validate_no_reload(self):
1437
index, reload_counter = self.make_combined_index_with_missing()
1438
index._reload_func = None
1439
self.assertRaises(errors.NoSuchFile, index.validate)
1441
def test_validate_reloads_and_fails(self):
1442
index, reload_counter = self.make_combined_index_with_missing(
1444
self.assertRaises(errors.NoSuchFile, index.validate)
1446
def test_find_ancestors_across_indexes(self):
1451
index1 = self.make_index('12', ref_lists=1, nodes=[
1452
(key1, 'value', ([],)),
1453
(key2, 'value', ([key1],)),
1455
index2 = self.make_index('34', ref_lists=1, nodes=[
1456
(key3, 'value', ([key2],)),
1457
(key4, 'value', ([key3],)),
1459
c_index = CombinedGraphIndex([index1, index2])
1460
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1461
self.assertEqual({key1: ()}, parent_map)
1462
self.assertEqual(set(), missing_keys)
1463
# Now look for a key from index2 which requires us to find the key in
1464
# the second index, and then continue searching for parents in the
1466
parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1467
self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1468
self.assertEqual(set(), missing_keys)
1470
def test_find_ancestors_missing_keys(self):
1475
index1 = self.make_index('12', ref_lists=1, nodes=[
1476
(key1, 'value', ([],)),
1477
(key2, 'value', ([key1],)),
1479
index2 = self.make_index('34', ref_lists=1, nodes=[
1480
(key3, 'value', ([key2],)),
1482
c_index = CombinedGraphIndex([index1, index2])
1483
# Searching for a key which is actually not present at all should
1484
# eventually converge
1485
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1486
self.assertEqual({}, parent_map)
1487
self.assertEqual(set([key4]), missing_keys)
1489
def test_find_ancestors_no_indexes(self):
1490
c_index = CombinedGraphIndex([])
1492
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1493
self.assertEqual({}, parent_map)
1494
self.assertEqual(set([key1]), missing_keys)
1496
def test_find_ancestors_ghost_parent(self):
1501
index1 = self.make_index('12', ref_lists=1, nodes=[
1502
(key1, 'value', ([],)),
1503
(key2, 'value', ([key1],)),
1505
index2 = self.make_index('34', ref_lists=1, nodes=[
1506
(key4, 'value', ([key2, key3],)),
1508
c_index = CombinedGraphIndex([index1, index2])
1509
# Searching for a key which is actually not present at all should
1510
# eventually converge
1511
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1512
self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1514
self.assertEqual(set([key3]), missing_keys)
1516
def test__find_ancestors_empty_index(self):
1517
index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1519
missing_keys = set()
1520
search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1522
self.assertEqual(set(), search_keys)
1523
self.assertEqual({}, parent_map)
1524
self.assertEqual(set([('one',), ('two',)]), missing_keys)
961
1527
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
added
removed
bzrlib/tests/test_index.py
