915
933
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)
919
1030
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1070
1238
index = CombinedGraphIndex([])
1071
1239
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)
1074
1452
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):