/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to breezy/tests/test_index.py

  • Committer: Jelmer Vernooij
  • Date: 2017-06-10 21:59:15 UTC
  • mto: This revision was merged to the branch mainline in revision 6690.
  • Revision ID: jelmer@jelmer.uk-20170610215915-zcpu0in3r1irx3ml
Move serializer to bzr.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_index.py
16
16
 
17
17
"""Tests for indices."""
18
18
 
19
 
from bzrlib import errors
20
 
from bzrlib.index import *
21
 
from bzrlib.tests import TestCaseWithMemoryTransport
22
 
from bzrlib.transport import get_transport
23
 
 
24
 
 
25
 
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
 
19
from .. import (
 
20
    errors,
 
21
    tests,
 
22
    transport,
 
23
    )
 
24
from ..bzr import (
 
25
    index,
 
26
    )
 
27
 
 
28
 
 
29
class TestGraphIndexBuilder(tests.TestCaseWithMemoryTransport):
26
30
 
27
31
    def test_build_index_empty(self):
28
 
        builder = GraphIndexBuilder()
 
32
        builder = index.GraphIndexBuilder()
29
33
        stream = builder.finish()
30
34
        contents = stream.read()
31
35
        self.assertEqual(
33
37
            contents)
34
38
 
35
39
    def test_build_index_empty_two_element_keys(self):
36
 
        builder = GraphIndexBuilder(key_elements=2)
 
40
        builder = index.GraphIndexBuilder(key_elements=2)
37
41
        stream = builder.finish()
38
42
        contents = stream.read()
39
43
        self.assertEqual(
41
45
            contents)
42
46
 
43
47
    def test_build_index_one_reference_list_empty(self):
44
 
        builder = GraphIndexBuilder(reference_lists=1)
 
48
        builder = index.GraphIndexBuilder(reference_lists=1)
45
49
        stream = builder.finish()
46
50
        contents = stream.read()
47
51
        self.assertEqual(
49
53
            contents)
50
54
 
51
55
    def test_build_index_two_reference_list_empty(self):
52
 
        builder = GraphIndexBuilder(reference_lists=2)
 
56
        builder = index.GraphIndexBuilder(reference_lists=2)
53
57
        stream = builder.finish()
54
58
        contents = stream.read()
55
59
        self.assertEqual(
57
61
            contents)
58
62
 
59
63
    def test_build_index_one_node_no_refs(self):
60
 
        builder = GraphIndexBuilder()
 
64
        builder = index.GraphIndexBuilder()
61
65
        builder.add_node(('akey', ), 'data')
62
66
        stream = builder.finish()
63
67
        contents = stream.read()
66
70
            "akey\x00\x00\x00data\n\n", contents)
67
71
 
68
72
    def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
69
 
        builder = GraphIndexBuilder()
 
73
        builder = index.GraphIndexBuilder()
70
74
        builder.add_node(('akey', ), 'data', ())
71
75
        stream = builder.finish()
72
76
        contents = stream.read()
78
82
        # multipart keys are separated by \x00 - because they are fixed length,
79
83
        # not variable this does not cause any issues, and seems clearer to the
80
84
        # author.
81
 
        builder = GraphIndexBuilder(key_elements=2)
 
85
        builder = index.GraphIndexBuilder(key_elements=2)
82
86
        builder.add_node(('akey', 'secondpart'), 'data')
83
87
        stream = builder.finish()
84
88
        contents = stream.read()
87
91
            "akey\x00secondpart\x00\x00\x00data\n\n", contents)
88
92
 
89
93
    def test_add_node_empty_value(self):
90
 
        builder = GraphIndexBuilder()
 
94
        builder = index.GraphIndexBuilder()
91
95
        builder.add_node(('akey', ), '')
92
96
        stream = builder.finish()
93
97
        contents = stream.read()
97
101
 
98
102
    def test_build_index_nodes_sorted(self):
99
103
        # the highest sorted node comes first.
100
 
        builder = GraphIndexBuilder()
 
104
        builder = index.GraphIndexBuilder()
101
105
        # use three to have a good chance of glitching dictionary hash
102
106
        # lookups etc. Insert in randomish order that is not correct
103
107
        # and not the reverse of the correct order.
115
119
 
116
120
    def test_build_index_2_element_key_nodes_sorted(self):
117
121
        # multiple element keys are sorted first-key, second-key.
118
 
        builder = GraphIndexBuilder(key_elements=2)
 
122
        builder = index.GraphIndexBuilder(key_elements=2)
119
123
        # use three values of each key element, to have a good chance of
120
124
        # glitching dictionary hash lookups etc. Insert in randomish order that
121
125
        # is not correct and not the reverse of the correct order.
144
148
            "\n", contents)
145
149
 
146
150
    def test_build_index_reference_lists_are_included_one(self):
147
 
        builder = GraphIndexBuilder(reference_lists=1)
 
151
        builder = index.GraphIndexBuilder(reference_lists=1)
148
152
        builder.add_node(('key', ), 'data', ([], ))
149
153
        stream = builder.finish()
150
154
        contents = stream.read()
154
158
            "\n", contents)
155
159
 
156
160
    def test_build_index_reference_lists_with_2_element_keys(self):
157
 
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
 
161
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
158
162
        builder.add_node(('key', 'key2'), 'data', ([], ))
159
163
        stream = builder.finish()
160
164
        contents = stream.read()
164
168
            "\n", contents)
165
169
 
166
170
    def test_build_index_reference_lists_are_included_two(self):
167
 
        builder = GraphIndexBuilder(reference_lists=2)
 
171
        builder = index.GraphIndexBuilder(reference_lists=2)
168
172
        builder.add_node(('key', ), 'data', ([], []))
169
173
        stream = builder.finish()
170
174
        contents = stream.read()
174
178
            "\n", contents)
175
179
 
176
180
    def test_clear_cache(self):
177
 
        builder = GraphIndexBuilder(reference_lists=2)
 
181
        builder = index.GraphIndexBuilder(reference_lists=2)
178
182
        # This is a no-op, but the api should exist
179
183
        builder.clear_cache()
180
184
 
181
185
    def test_node_references_are_byte_offsets(self):
182
 
        builder = GraphIndexBuilder(reference_lists=1)
 
186
        builder = index.GraphIndexBuilder(reference_lists=1)
183
187
        builder.add_node(('reference', ), 'data', ([], ))
184
188
        builder.add_node(('key', ), 'data', ([('reference', )], ))
185
189
        stream = builder.finish()
191
195
            "\n", contents)
192
196
 
193
197
    def test_node_references_are_cr_delimited(self):
194
 
        builder = GraphIndexBuilder(reference_lists=1)
 
198
        builder = index.GraphIndexBuilder(reference_lists=1)
195
199
        builder.add_node(('reference', ), 'data', ([], ))
196
200
        builder.add_node(('reference2', ), 'data', ([], ))
197
 
        builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
 
201
        builder.add_node(('key', ), 'data',
 
202
                         ([('reference', ), ('reference2', )], ))
198
203
        stream = builder.finish()
199
204
        contents = stream.read()
200
205
        self.assertEqual(
205
210
            "\n", contents)
206
211
 
207
212
    def test_multiple_reference_lists_are_tab_delimited(self):
208
 
        builder = GraphIndexBuilder(reference_lists=2)
 
213
        builder = index.GraphIndexBuilder(reference_lists=2)
209
214
        builder.add_node(('keference', ), 'data', ([], []))
210
 
        builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
 
215
        builder.add_node(('rey', ), 'data',
 
216
                         ([('keference', )], [('keference', )]))
211
217
        stream = builder.finish()
212
218
        contents = stream.read()
213
219
        self.assertEqual(
217
223
            "\n", contents)
218
224
 
219
225
    def test_add_node_referencing_missing_key_makes_absent(self):
220
 
        builder = GraphIndexBuilder(reference_lists=1)
221
 
        builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
 
226
        builder = index.GraphIndexBuilder(reference_lists=1)
 
227
        builder.add_node(('rey', ), 'data',
 
228
                         ([('beference', ), ('aeference2', )], ))
222
229
        stream = builder.finish()
223
230
        contents = stream.read()
224
231
        self.assertEqual(
230
237
 
231
238
    def test_node_references_three_digits(self):
232
239
        # test the node digit expands as needed.
233
 
        builder = GraphIndexBuilder(reference_lists=1)
234
 
        references = [(str(val), ) for val in reversed(range(9))]
 
240
        builder = index.GraphIndexBuilder(reference_lists=1)
 
241
        references = [(str(val), ) for val in range(8, -1, -1)]
235
242
        builder.add_node(('2-key', ), '', (references, ))
236
243
        stream = builder.finish()
237
244
        contents = stream.read()
252
259
    def test_absent_has_no_reference_overhead(self):
253
260
        # the offsets after an absent record should be correct when there are
254
261
        # >1 reference lists.
255
 
        builder = GraphIndexBuilder(reference_lists=2)
 
262
        builder = index.GraphIndexBuilder(reference_lists=2)
256
263
        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
257
264
        stream = builder.finish()
258
265
        contents = stream.read()
264
271
            "\n", contents)
265
272
 
266
273
    def test_add_node_bad_key(self):
267
 
        builder = GraphIndexBuilder()
 
274
        builder = index.GraphIndexBuilder()
268
275
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
269
276
            self.assertRaises(errors.BadIndexKey, builder.add_node,
270
277
                ('a%skey' % bad_char, ), 'data')
279
286
        self.assertRaises(errors.BadIndexKey, builder.add_node,
280
287
                ('primary', 'secondary'), 'data')
281
288
        # secondary key elements get checked too:
282
 
        builder = GraphIndexBuilder(key_elements=2)
 
289
        builder = index.GraphIndexBuilder(key_elements=2)
283
290
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
284
291
            self.assertRaises(errors.BadIndexKey, builder.add_node,
285
292
                ('prefix', 'a%skey' % bad_char), 'data')
286
293
 
287
294
    def test_add_node_bad_data(self):
288
 
        builder = GraphIndexBuilder()
 
295
        builder = index.GraphIndexBuilder()
289
296
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
290
297
            'data\naa')
291
298
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
292
299
            'data\x00aa')
293
300
 
294
301
    def test_add_node_bad_mismatched_ref_lists_length(self):
295
 
        builder = GraphIndexBuilder()
 
302
        builder = index.GraphIndexBuilder()
296
303
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
297
304
            'data aa', ([], ))
298
 
        builder = GraphIndexBuilder(reference_lists=1)
 
305
        builder = index.GraphIndexBuilder(reference_lists=1)
299
306
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
300
307
            'data aa')
301
308
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
302
309
            'data aa', (), )
303
310
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
304
311
            'data aa', ([], []))
305
 
        builder = GraphIndexBuilder(reference_lists=2)
 
312
        builder = index.GraphIndexBuilder(reference_lists=2)
306
313
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
307
314
            'data aa')
308
315
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
312
319
 
313
320
    def test_add_node_bad_key_in_reference_lists(self):
314
321
        # first list, first key - trivial
315
 
        builder = GraphIndexBuilder(reference_lists=1)
 
322
        builder = index.GraphIndexBuilder(reference_lists=1)
316
323
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
317
324
            'data aa', ([('a key', )], ))
318
325
        # references keys must be tuples too
329
336
            'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
330
337
        # and if there is more than one list it should be getting checked
331
338
        # too
332
 
        builder = GraphIndexBuilder(reference_lists=2)
 
339
        builder = index.GraphIndexBuilder(reference_lists=2)
333
340
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
334
341
            'data aa', ([], ['a bad key']))
335
342
 
336
343
    def test_add_duplicate_key(self):
337
 
        builder = GraphIndexBuilder()
 
344
        builder = index.GraphIndexBuilder()
338
345
        builder.add_node(('key', ), 'data')
339
 
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
340
 
            'data')
 
346
        self.assertRaises(errors.BadIndexDuplicateKey,
 
347
                          builder.add_node, ('key', ), 'data')
341
348
 
342
349
    def test_add_duplicate_key_2_elements(self):
343
 
        builder = GraphIndexBuilder(key_elements=2)
 
350
        builder = index.GraphIndexBuilder(key_elements=2)
344
351
        builder.add_node(('key', 'key'), 'data')
345
352
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
346
353
            ('key', 'key'), 'data')
347
354
 
348
355
    def test_add_key_after_referencing_key(self):
349
 
        builder = GraphIndexBuilder(reference_lists=1)
 
356
        builder = index.GraphIndexBuilder(reference_lists=1)
350
357
        builder.add_node(('key', ), 'data', ([('reference', )], ))
351
358
        builder.add_node(('reference', ), 'data', ([],))
352
359
 
353
360
    def test_add_key_after_referencing_key_2_elements(self):
354
 
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
 
361
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
355
362
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
356
363
        builder.add_node(('reference', 'tokey'), 'data', ([],))
357
364
 
358
365
    def test_set_optimize(self):
359
 
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
 
366
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
360
367
        builder.set_optimize(for_size=True)
361
368
        self.assertTrue(builder._optimize_for_size)
362
369
        builder.set_optimize(for_size=False)
363
370
        self.assertFalse(builder._optimize_for_size)
364
371
 
365
372
 
366
 
class TestGraphIndex(TestCaseWithMemoryTransport):
 
373
class TestGraphIndex(tests.TestCaseWithMemoryTransport):
367
374
 
368
375
    def make_key(self, number):
369
376
        return (str(number) + 'X'*100,)
380
387
        return nodes
381
388
 
382
389
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
383
 
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
390
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
384
391
        for key, value, references in nodes:
385
392
            builder.add_node(key, value, references)
386
393
        stream = builder.finish()
387
 
        trans = get_transport('trace+' + self.get_url())
 
394
        trans = transport.get_transport_from_url('trace+' + self.get_url())
388
395
        size = trans.put_file('index', stream)
389
 
        return GraphIndex(trans, 'index', size)
 
396
        return index.GraphIndex(trans, 'index', size)
390
397
 
391
398
    def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
392
399
                               offset=0):
393
 
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
400
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
394
401
        for key, value, references in nodes:
395
402
            builder.add_node(key, value, references)
396
403
        content = builder.finish().read()
397
404
        size = len(content)
398
405
        trans = self.get_transport()
399
406
        trans.put_bytes('index', (' '*offset) + content)
400
 
        return GraphIndex(trans, 'index', size, offset=offset)
 
407
        return index.GraphIndex(trans, 'index', size, offset=offset)
401
408
 
402
409
    def test_clear_cache(self):
403
410
        index = self.make_index()
408
415
    def test_open_bad_index_no_error(self):
409
416
        trans = self.get_transport()
410
417
        trans.put_bytes('name', "not an index\n")
411
 
        index = GraphIndex(trans, 'name', 13)
 
418
        idx = index.GraphIndex(trans, 'name', 13)
412
419
 
413
420
    def test_with_offset(self):
414
421
        nodes = self.make_nodes(200)
415
 
        index = self.make_index_with_offset(offset=1234567, nodes=nodes)
416
 
        self.assertEqual(200, index.key_count())
 
422
        idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
 
423
        self.assertEqual(200, idx.key_count())
417
424
 
418
425
    def test_buffer_all_with_offset(self):
419
426
        nodes = self.make_nodes(200)
420
 
        index = self.make_index_with_offset(offset=1234567, nodes=nodes)
421
 
        index._buffer_all()
422
 
        self.assertEqual(200, index.key_count())
 
427
        idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
 
428
        idx._buffer_all()
 
429
        self.assertEqual(200, idx.key_count())
423
430
 
424
431
    def test_side_effect_buffering_with_offset(self):
425
432
        nodes = self.make_nodes(20)
733
740
        index = self.make_index(1, nodes=[
734
741
            (('name', ), 'data', ([('ref', )], )),
735
742
            (('ref', ), 'refdata', ([], ))])
736
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
737
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
743
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
744
            (index, ('ref', ), 'refdata', ((), ))},
738
745
            set(index.iter_all_entries()))
739
746
 
740
747
    def test_iter_entries_buffers_once(self):
741
748
        index = self.make_index(nodes=self.make_nodes(2))
742
749
        # reset the transport log
743
750
        del index._transport._activity[:]
744
 
        self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
 
751
        self.assertEqual({(index, self.make_key(1), self.make_value(1))},
745
752
                         set(index.iter_entries([self.make_key(1)])))
746
753
        # We should have requested reading the header bytes
747
754
        # But not needed any more than that because it would have triggered a
783
790
        index = self.make_index(1, nodes=[
784
791
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
785
792
            (('ref', ), 'refdata', ([], ))])
786
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
787
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
793
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),('ref',)),)),
 
794
            (index, ('ref', ), 'refdata', ((), ))},
788
795
            set(index.iter_entries([('name',), ('ref',)])))
789
796
 
790
797
    def test_iter_entries_references_2_refs_resolved(self):
791
798
        index = self.make_index(2, nodes=[
792
799
            (('name', ), 'data', ([('ref', )], [('ref', )])),
793
800
            (('ref', ), 'refdata', ([], []))])
794
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
795
 
            (index, ('ref', ), 'refdata', ((), ()))]),
 
801
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
 
802
            (index, ('ref', ), 'refdata', ((), ()))},
796
803
            set(index.iter_entries([('name',), ('ref',)])))
797
804
 
798
805
    def test_iteration_absent_skipped(self):
799
806
        index = self.make_index(1, nodes=[
800
807
            (('name', ), 'data', ([('ref', )], ))])
801
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
 
808
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
802
809
            set(index.iter_all_entries()))
803
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
 
810
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
804
811
            set(index.iter_entries([('name', )])))
805
812
        self.assertEqual([], list(index.iter_entries([('ref', )])))
806
813
 
807
814
    def test_iteration_absent_skipped_2_element_keys(self):
808
815
        index = self.make_index(1, key_elements=2, nodes=[
809
816
            (('name', 'fin'), 'data', ([('ref', 'erence')], ))])
810
 
        self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
 
817
        self.assertEqual({(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))},
811
818
            set(index.iter_all_entries()))
812
 
        self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
 
819
        self.assertEqual({(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))},
813
820
            set(index.iter_entries([('name', 'fin')])))
814
821
        self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
815
822
 
817
824
        index = self.make_index(1, nodes=[
818
825
            (('name', ), 'data', ([('ref', )], )),
819
826
            (('ref', ), 'refdata', ([], ))])
820
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
821
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
827
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
828
            (index, ('ref', ), 'refdata', ((), ))},
822
829
            set(index.iter_entries([('name', ), ('ref', )])))
823
830
 
824
831
    def test_iter_nothing_empty(self):
830
837
        self.assertEqual([], list(index.iter_entries([('a', )])))
831
838
 
832
839
    def test_iter_missing_entry_empty_no_size(self):
833
 
        index = self.make_index()
834
 
        index = GraphIndex(index._transport, 'index', None)
835
 
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
840
        idx = self.make_index()
 
841
        idx = index.GraphIndex(idx._transport, 'index', None)
 
842
        self.assertEqual([], list(idx.iter_entries([('a', )])))
836
843
 
837
844
    def test_iter_key_prefix_1_element_key_None(self):
838
845
        index = self.make_index()
853
860
        index = self.make_index( nodes=[
854
861
            (('name', ), 'data', ()),
855
862
            (('ref', ), 'refdata', ())])
856
 
        self.assertEqual(set([(index, ('name', ), 'data'),
857
 
            (index, ('ref', ), 'refdata')]),
 
863
        self.assertEqual({(index, ('name', ), 'data'),
 
864
            (index, ('ref', ), 'refdata')},
858
865
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
859
866
 
860
867
    def test_iter_key_prefix_1_key_element_refs(self):
861
868
        index = self.make_index(1, nodes=[
862
869
            (('name', ), 'data', ([('ref', )], )),
863
870
            (('ref', ), 'refdata', ([], ))])
864
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
865
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
871
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
872
            (index, ('ref', ), 'refdata', ((), ))},
866
873
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
867
874
 
868
875
    def test_iter_key_prefix_2_key_element_no_refs(self):
870
877
            (('name', 'fin1'), 'data', ()),
871
878
            (('name', 'fin2'), 'beta', ()),
872
879
            (('ref', 'erence'), 'refdata', ())])
873
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
874
 
            (index, ('ref', 'erence'), 'refdata')]),
 
880
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
881
            (index, ('ref', 'erence'), 'refdata')},
875
882
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
876
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
877
 
            (index, ('name', 'fin2'), 'beta')]),
 
883
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
884
            (index, ('name', 'fin2'), 'beta')},
878
885
            set(index.iter_entries_prefix([('name', None)])))
879
886
 
880
887
    def test_iter_key_prefix_2_key_element_refs(self):
882
889
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
883
890
            (('name', 'fin2'), 'beta', ([], )),
884
891
            (('ref', 'erence'), 'refdata', ([], ))])
885
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
886
 
            (index, ('ref', 'erence'), 'refdata', ((), ))]),
 
892
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
893
            (index, ('ref', 'erence'), 'refdata', ((), ))},
887
894
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
888
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
889
 
            (index, ('name', 'fin2'), 'beta', ((), ))]),
 
895
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
896
            (index, ('name', 'fin2'), 'beta', ((), ))},
890
897
            set(index.iter_entries_prefix([('name', None)])))
891
898
 
892
899
    def test_key_count_empty(self):
928
935
    def test_validate_bad_index_errors(self):
929
936
        trans = self.get_transport()
930
937
        trans.put_bytes('name', "not an index\n")
931
 
        index = GraphIndex(trans, 'name', 13)
932
 
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
 
938
        idx = index.GraphIndex(trans, 'name', 13)
 
939
        self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
933
940
 
934
941
    def test_validate_bad_node_refs(self):
935
 
        index = self.make_index(2)
 
942
        idx = self.make_index(2)
936
943
        trans = self.get_transport()
937
944
        content = trans.get_bytes('index')
938
945
        # change the options line to end with a rather than a parseable number
939
946
        new_content = content[:-2] + 'a\n\n'
940
947
        trans.put_bytes('index', new_content)
941
 
        self.assertRaises(errors.BadIndexOptions, index.validate)
 
948
        self.assertRaises(errors.BadIndexOptions, idx.validate)
942
949
 
943
950
    def test_validate_missing_end_line_empty(self):
944
951
        index = self.make_index(2)
979
986
        missing_key = ('missing',)
980
987
        index = self.make_index(ref_lists=1, nodes=[
981
988
            (('key',), 'value', ([missing_key],))])
982
 
        self.assertEqual(set([missing_key]), index.external_references(0))
 
989
        self.assertEqual({missing_key}, index.external_references(0))
983
990
 
984
991
    def test_external_references_multiple_ref_lists(self):
985
992
        missing_key = ('missing',)
986
993
        index = self.make_index(ref_lists=2, nodes=[
987
994
            (('key',), 'value', ([], [missing_key]))])
988
995
        self.assertEqual(set([]), index.external_references(0))
989
 
        self.assertEqual(set([missing_key]), index.external_references(1))
 
996
        self.assertEqual({missing_key}, index.external_references(1))
990
997
 
991
998
    def test_external_references_two_records(self):
992
999
        index = self.make_index(ref_lists=1, nodes=[
1007
1014
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1008
1015
        self.assertEqual({key1: (key2,)}, parent_map)
1009
1016
        self.assertEqual(set(), missing_keys)
1010
 
        self.assertEqual(set([key2]), search_keys)
 
1017
        self.assertEqual({key2}, search_keys)
1011
1018
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1012
1019
                                            missing_keys)
1013
1020
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1027
1034
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1028
1035
                                            missing_keys)
1029
1036
        self.assertEqual({key2: ()}, parent_map)
1030
 
        self.assertEqual(set([key3]), missing_keys)
 
1037
        self.assertEqual({key3}, missing_keys)
1031
1038
        self.assertEqual(set(), search_keys)
1032
1039
 
1033
1040
    def test__find_ancestors_dont_search_known(self):
1049
1056
        self.assertEqual(set(), search_keys)
1050
1057
 
1051
1058
    def test_supports_unlimited_cache(self):
1052
 
        builder = GraphIndexBuilder(0, key_elements=1)
 
1059
        builder = index.GraphIndexBuilder(0, key_elements=1)
1053
1060
        stream = builder.finish()
1054
 
        trans = get_transport(self.get_url())
 
1061
        trans = self.get_transport()
1055
1062
        size = trans.put_file('index', stream)
1056
1063
        # It doesn't matter what unlimited_cache does here, just that it can be
1057
1064
        # passed
1058
 
        index = GraphIndex(trans, 'index', size, unlimited_cache=True)
1059
 
 
1060
 
 
1061
 
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
 
1065
        idx = index.GraphIndex(trans, 'index', size, unlimited_cache=True)
 
1066
 
 
1067
 
 
1068
class TestCombinedGraphIndex(tests.TestCaseWithMemoryTransport):
1062
1069
 
1063
1070
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1064
 
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
1071
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
1065
1072
        for key, value, references in nodes:
1066
1073
            builder.add_node(key, value, references)
1067
1074
        stream = builder.finish()
1068
1075
        trans = self.get_transport()
1069
1076
        size = trans.put_file(name, stream)
1070
 
        return GraphIndex(trans, name, size)
 
1077
        return index.GraphIndex(trans, name, size)
1071
1078
 
1072
1079
    def make_combined_index_with_missing(self, missing=['1', '2']):
1073
1080
        """Create a CombinedGraphIndex which will have missing indexes.
1079
1086
        :param missing: The underlying indexes to delete
1080
1087
        :return: (CombinedGraphIndex, reload_counter)
1081
1088
        """
1082
 
        index1 = self.make_index('1', nodes=[(('1',), '', ())])
1083
 
        index2 = self.make_index('2', nodes=[(('2',), '', ())])
1084
 
        index3 = self.make_index('3', nodes=[
 
1089
        idx1 = self.make_index('1', nodes=[(('1',), '', ())])
 
1090
        idx2 = self.make_index('2', nodes=[(('2',), '', ())])
 
1091
        idx3 = self.make_index('3', nodes=[
1085
1092
            (('1',), '', ()),
1086
1093
            (('2',), '', ())])
1087
1094
 
1089
1096
        reload_counter = [0, 0, 0]
1090
1097
        def reload():
1091
1098
            reload_counter[0] += 1
1092
 
            new_indices = [index3]
1093
 
            if index._indices == new_indices:
 
1099
            new_indices = [idx3]
 
1100
            if idx._indices == new_indices:
1094
1101
                reload_counter[2] += 1
1095
1102
                return False
1096
1103
            reload_counter[1] += 1
1097
 
            index._indices[:] = new_indices
 
1104
            idx._indices[:] = new_indices
1098
1105
            return True
1099
 
        index = CombinedGraphIndex([index1, index2], reload_func=reload)
 
1106
        idx = index.CombinedGraphIndex([idx1, idx2], reload_func=reload)
1100
1107
        trans = self.get_transport()
1101
1108
        for fname in missing:
1102
1109
            trans.delete(fname)
1103
 
        return index, reload_counter
 
1110
        return idx, reload_counter
1104
1111
 
1105
1112
    def test_open_missing_index_no_error(self):
1106
1113
        trans = self.get_transport()
1107
 
        index1 = GraphIndex(trans, 'missing', 100)
1108
 
        index = CombinedGraphIndex([index1])
 
1114
        idx1 = index.GraphIndex(trans, 'missing', 100)
 
1115
        idx = index.CombinedGraphIndex([idx1])
1109
1116
 
1110
1117
    def test_add_index(self):
1111
 
        index = CombinedGraphIndex([])
1112
 
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1113
 
        index.insert_index(0, index1)
1114
 
        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
 
1118
        idx = index.CombinedGraphIndex([])
 
1119
        idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1120
        idx.insert_index(0, idx1)
 
1121
        self.assertEqual([(idx1, ('key', ), '')],
 
1122
                         list(idx.iter_all_entries()))
1115
1123
 
1116
1124
    def test_clear_cache(self):
1117
1125
        log = []
1128
1136
                log.append(self._index)
1129
1137
                return self._index.clear_cache()
1130
1138
 
1131
 
        index = CombinedGraphIndex([])
1132
 
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1133
 
        index.insert_index(0, ClearCacheProxy(index1))
1134
 
        index2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1135
 
        index.insert_index(1, ClearCacheProxy(index2))
 
1139
        idx = index.CombinedGraphIndex([])
 
1140
        idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1141
        idx.insert_index(0, ClearCacheProxy(idx1))
 
1142
        idx2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1143
        idx.insert_index(1, ClearCacheProxy(idx2))
1136
1144
        # CombinedGraphIndex should call 'clear_cache()' on all children
1137
 
        index.clear_cache()
1138
 
        self.assertEqual(sorted([index1, index2]), sorted(log))
 
1145
        idx.clear_cache()
 
1146
        self.assertEqual(sorted([idx1, idx2]), sorted(log))
1139
1147
 
1140
1148
    def test_iter_all_entries_empty(self):
1141
 
        index = CombinedGraphIndex([])
1142
 
        self.assertEqual([], list(index.iter_all_entries()))
 
1149
        idx = index.CombinedGraphIndex([])
 
1150
        self.assertEqual([], list(idx.iter_all_entries()))
1143
1151
 
1144
1152
    def test_iter_all_entries_children_empty(self):
1145
 
        index1 = self.make_index('name')
1146
 
        index = CombinedGraphIndex([index1])
1147
 
        self.assertEqual([], list(index.iter_all_entries()))
 
1153
        idx1 = self.make_index('name')
 
1154
        idx = index.CombinedGraphIndex([idx1])
 
1155
        self.assertEqual([], list(idx.iter_all_entries()))
1148
1156
 
1149
1157
    def test_iter_all_entries_simple(self):
1150
 
        index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
1151
 
        index = CombinedGraphIndex([index1])
1152
 
        self.assertEqual([(index1, ('name', ), 'data')],
1153
 
            list(index.iter_all_entries()))
 
1158
        idx1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
 
1159
        idx = index.CombinedGraphIndex([idx1])
 
1160
        self.assertEqual([(idx1, ('name', ), 'data')],
 
1161
            list(idx.iter_all_entries()))
1154
1162
 
1155
1163
    def test_iter_all_entries_two_indices(self):
1156
 
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1157
 
        index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
1158
 
        index = CombinedGraphIndex([index1, index2])
1159
 
        self.assertEqual([(index1, ('name', ), 'data'),
1160
 
            (index2, ('2', ), '')],
1161
 
            list(index.iter_all_entries()))
 
1164
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1165
        idx2 = self.make_index('name2', nodes=[(('2', ), '', ())])
 
1166
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1167
        self.assertEqual([(idx1, ('name', ), 'data'),
 
1168
                          (idx2, ('2', ), '')],
 
1169
                         list(idx.iter_all_entries()))
1162
1170
 
1163
1171
    def test_iter_entries_two_indices_dup_key(self):
1164
 
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1165
 
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1166
 
        index = CombinedGraphIndex([index1, index2])
1167
 
        self.assertEqual([(index1, ('name', ), 'data')],
1168
 
            list(index.iter_entries([('name', )])))
 
1172
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1173
        idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
 
1174
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1175
        self.assertEqual([(idx1, ('name', ), 'data')],
 
1176
                         list(idx.iter_entries([('name', )])))
1169
1177
 
1170
1178
    def test_iter_all_entries_two_indices_dup_key(self):
1171
 
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1172
 
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1173
 
        index = CombinedGraphIndex([index1, index2])
1174
 
        self.assertEqual([(index1, ('name', ), 'data')],
1175
 
            list(index.iter_all_entries()))
 
1179
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1180
        idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
 
1181
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1182
        self.assertEqual([(idx1, ('name', ), 'data')],
 
1183
                         list(idx.iter_all_entries()))
1176
1184
 
1177
1185
    def test_iter_key_prefix_2_key_element_refs(self):
1178
 
        index1 = self.make_index('1', 1, key_elements=2, nodes=[
1179
 
            (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
1180
 
        index2 = self.make_index('2', 1, key_elements=2, nodes=[
1181
 
            (('name', 'fin2'), 'beta', ([], )),
1182
 
            (('ref', 'erence'), 'refdata', ([], ))])
1183
 
        index = CombinedGraphIndex([index1, index2])
1184
 
        self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1185
 
            (index2, ('ref', 'erence'), 'refdata', ((), ))]),
1186
 
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1187
 
        self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1188
 
            (index2, ('name', 'fin2'), 'beta', ((), ))]),
1189
 
            set(index.iter_entries_prefix([('name', None)])))
 
1186
        idx1 = self.make_index('1', 1, key_elements=2, nodes=[
 
1187
                (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
 
1188
        idx2 = self.make_index('2', 1, key_elements=2, nodes=[
 
1189
                (('name', 'fin2'), 'beta', ([], )),
 
1190
                (('ref', 'erence'), 'refdata', ([], ))])
 
1191
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1192
        self.assertEqual({(idx1, ('name', 'fin1'), 'data',
 
1193
                               ((('ref', 'erence'),),)),
 
1194
                              (idx2, ('ref', 'erence'), 'refdata', ((), ))},
 
1195
                         set(idx.iter_entries_prefix([('name', 'fin1'),
 
1196
                                                        ('ref', 'erence')])))
 
1197
        self.assertEqual({(idx1, ('name', 'fin1'), 'data',
 
1198
                               ((('ref', 'erence'),),)),
 
1199
                              (idx2, ('name', 'fin2'), 'beta', ((), ))},
 
1200
                         set(idx.iter_entries_prefix([('name', None)])))
1190
1201
 
1191
1202
    def test_iter_nothing_empty(self):
1192
 
        index = CombinedGraphIndex([])
1193
 
        self.assertEqual([], list(index.iter_entries([])))
 
1203
        idx = index.CombinedGraphIndex([])
 
1204
        self.assertEqual([], list(idx.iter_entries([])))
1194
1205
 
1195
1206
    def test_iter_nothing_children_empty(self):
1196
 
        index1 = self.make_index('name')
1197
 
        index = CombinedGraphIndex([index1])
1198
 
        self.assertEqual([], list(index.iter_entries([])))
 
1207
        idx1 = self.make_index('name')
 
1208
        idx = index.CombinedGraphIndex([idx1])
 
1209
        self.assertEqual([], list(idx.iter_entries([])))
1199
1210
 
1200
1211
    def test_iter_all_keys(self):
1201
 
        index1 = self.make_index('1', 1, nodes=[
1202
 
            (('name', ), 'data', ([('ref', )], ))])
1203
 
        index2 = self.make_index('2', 1, nodes=[
1204
 
            (('ref', ), 'refdata', ((), ))])
1205
 
        index = CombinedGraphIndex([index1, index2])
1206
 
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1207
 
            (index2, ('ref', ), 'refdata', ((), ))]),
1208
 
            set(index.iter_entries([('name', ), ('ref', )])))
 
1212
        idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
 
1213
                                               ([('ref', )], ))])
 
1214
        idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ((), ))])
 
1215
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1216
        self.assertEqual({(idx1, ('name', ), 'data', ((('ref', ), ), )),
 
1217
                              (idx2, ('ref', ), 'refdata', ((), ))},
 
1218
                         set(idx.iter_entries([('name', ), ('ref', )])))
1209
1219
 
1210
1220
    def test_iter_all_keys_dup_entry(self):
1211
 
        index1 = self.make_index('1', 1, nodes=[
1212
 
            (('name', ), 'data', ([('ref', )], )),
1213
 
            (('ref', ), 'refdata', ([], ))])
1214
 
        index2 = self.make_index('2', 1, nodes=[
1215
 
            (('ref', ), 'refdata', ([], ))])
1216
 
        index = CombinedGraphIndex([index1, index2])
1217
 
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1218
 
            (index1, ('ref', ), 'refdata', ((), ))]),
1219
 
            set(index.iter_entries([('name', ), ('ref', )])))
 
1221
        idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
 
1222
                                                 ([('ref', )], )),
 
1223
                                                (('ref', ), 'refdata', ([], ))])
 
1224
        idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ([], ))])
 
1225
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1226
        self.assertEqual({(idx1, ('name', ), 'data', ((('ref',),),)),
 
1227
                              (idx1, ('ref', ), 'refdata', ((), ))},
 
1228
                         set(idx.iter_entries([('name', ), ('ref', )])))
1220
1229
 
1221
1230
    def test_iter_missing_entry_empty(self):
1222
 
        index = CombinedGraphIndex([])
1223
 
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
1231
        idx = index.CombinedGraphIndex([])
 
1232
        self.assertEqual([], list(idx.iter_entries([('a', )])))
1224
1233
 
1225
1234
    def test_iter_missing_entry_one_index(self):
1226
 
        index1 = self.make_index('1')
1227
 
        index = CombinedGraphIndex([index1])
1228
 
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
1235
        idx1 = self.make_index('1')
 
1236
        idx = index.CombinedGraphIndex([idx1])
 
1237
        self.assertEqual([], list(idx.iter_entries([('a', )])))
1229
1238
 
1230
1239
    def test_iter_missing_entry_two_index(self):
1231
 
        index1 = self.make_index('1')
1232
 
        index2 = self.make_index('2')
1233
 
        index = CombinedGraphIndex([index1, index2])
1234
 
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
1240
        idx1 = self.make_index('1')
 
1241
        idx2 = self.make_index('2')
 
1242
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1243
        self.assertEqual([], list(idx.iter_entries([('a', )])))
1235
1244
 
1236
1245
    def test_iter_entry_present_one_index_only(self):
1237
 
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1238
 
        index2 = self.make_index('2', nodes=[])
1239
 
        index = CombinedGraphIndex([index1, index2])
1240
 
        self.assertEqual([(index1, ('key', ), '')],
1241
 
            list(index.iter_entries([('key', )])))
 
1246
        idx1 = self.make_index('1', nodes=[(('key', ), '', ())])
 
1247
        idx2 = self.make_index('2', nodes=[])
 
1248
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1249
        self.assertEqual([(idx1, ('key', ), '')],
 
1250
                         list(idx.iter_entries([('key', )])))
1242
1251
        # and in the other direction
1243
 
        index = CombinedGraphIndex([index2, index1])
1244
 
        self.assertEqual([(index1, ('key', ), '')],
1245
 
            list(index.iter_entries([('key', )])))
 
1252
        idx = index.CombinedGraphIndex([idx2, idx1])
 
1253
        self.assertEqual([(idx1, ('key', ), '')],
 
1254
                         list(idx.iter_entries([('key', )])))
1246
1255
 
1247
1256
    def test_key_count_empty(self):
1248
 
        index1 = self.make_index('1', nodes=[])
1249
 
        index2 = self.make_index('2', nodes=[])
1250
 
        index = CombinedGraphIndex([index1, index2])
1251
 
        self.assertEqual(0, index.key_count())
 
1257
        idx1 = self.make_index('1', nodes=[])
 
1258
        idx2 = self.make_index('2', nodes=[])
 
1259
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1260
        self.assertEqual(0, idx.key_count())
1252
1261
 
1253
1262
    def test_key_count_sums_index_keys(self):
1254
 
        index1 = self.make_index('1', nodes=[
 
1263
        idx1 = self.make_index('1', nodes=[
1255
1264
            (('1',), '', ()),
1256
1265
            (('2',), '', ())])
1257
 
        index2 = self.make_index('2', nodes=[(('1',), '', ())])
1258
 
        index = CombinedGraphIndex([index1, index2])
1259
 
        self.assertEqual(3, index.key_count())
 
1266
        idx2 = self.make_index('2', nodes=[(('1',), '', ())])
 
1267
        idx = index.CombinedGraphIndex([idx1, idx2])
 
1268
        self.assertEqual(3, idx.key_count())
1260
1269
 
1261
1270
    def test_validate_bad_child_index_errors(self):
1262
1271
        trans = self.get_transport()
1263
1272
        trans.put_bytes('name', "not an index\n")
1264
 
        index1 = GraphIndex(trans, 'name', 13)
1265
 
        index = CombinedGraphIndex([index1])
1266
 
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
 
1273
        idx1 = index.GraphIndex(trans, 'name', 13)
 
1274
        idx = index.CombinedGraphIndex([idx1])
 
1275
        self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
1267
1276
 
1268
1277
    def test_validate_empty(self):
1269
 
        index = CombinedGraphIndex([])
1270
 
        index.validate()
 
1278
        idx = index.CombinedGraphIndex([])
 
1279
        idx.validate()
1271
1280
 
1272
1281
    def test_key_count_reloads(self):
1273
 
        index, reload_counter = self.make_combined_index_with_missing()
1274
 
        self.assertEqual(2, index.key_count())
 
1282
        idx, reload_counter = self.make_combined_index_with_missing()
 
1283
        self.assertEqual(2, idx.key_count())
1275
1284
        self.assertEqual([1, 1, 0], reload_counter)
1276
1285
 
1277
1286
    def test_key_count_no_reload(self):
1278
 
        index, reload_counter = self.make_combined_index_with_missing()
1279
 
        index._reload_func = None
 
1287
        idx, reload_counter = self.make_combined_index_with_missing()
 
1288
        idx._reload_func = None
1280
1289
        # Without a _reload_func we just raise the exception
1281
 
        self.assertRaises(errors.NoSuchFile, index.key_count)
 
1290
        self.assertRaises(errors.NoSuchFile, idx.key_count)
1282
1291
 
1283
1292
    def test_key_count_reloads_and_fails(self):
1284
1293
        # We have deleted all underlying indexes, so we will try to reload, but
1285
1294
        # still fail. This is mostly to test we don't get stuck in an infinite
1286
1295
        # loop trying to reload
1287
 
        index, reload_counter = self.make_combined_index_with_missing(
1288
 
                                    ['1', '2', '3'])
1289
 
        self.assertRaises(errors.NoSuchFile, index.key_count)
 
1296
        idx, reload_counter = self.make_combined_index_with_missing(
 
1297
            ['1', '2', '3'])
 
1298
        self.assertRaises(errors.NoSuchFile, idx.key_count)
1290
1299
        self.assertEqual([2, 1, 1], reload_counter)
1291
1300
 
1292
1301
    def test_iter_entries_reloads(self):
1392
1401
        return self.make_index('index-%s' % name, 0, nodes=nodes)
1393
1402
 
1394
1403
    def test_reorder_after_iter_entries(self):
1395
 
        # Four indices: [key1] in index1, [key2,key3] in index2, [] in index3,
1396
 
        # [key4] in index4.
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(
 
1404
        # Four indices: [key1] in idx1, [key2,key3] in idx2, [] in idx3,
 
1405
        # [key4] in idx4.
 
1406
        idx = index.CombinedGraphIndex([])
 
1407
        idx.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
 
1408
        idx.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
 
1409
        idx.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
 
1410
        idx.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
 
1411
        idx1, idx2, idx3, idx4 = idx._indices
 
1412
        # Query a key from idx4 and idx2.
 
1413
        self.assertLength(2, list(idx.iter_entries(
1405
1414
            [('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)
 
1415
        # Now idx2 and idx4 should be moved to the front (and idx1 should
 
1416
        # still be before idx3).
 
1417
        self.assertEqual([idx2, idx4, idx1, idx3], idx._indices)
 
1418
        self.assertEqual(['2', '4', '1', '3'], idx._index_names)
1410
1419
 
1411
1420
    def test_reorder_propagates_to_siblings(self):
1412
1421
        # Two CombinedGraphIndex objects, with the same number of indicies with
1413
1422
        # matching names.
1414
 
        cgi1 = CombinedGraphIndex([])
1415
 
        cgi2 = CombinedGraphIndex([])
 
1423
        cgi1 = index.CombinedGraphIndex([])
 
1424
        cgi2 = index.CombinedGraphIndex([])
1416
1425
        cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
1417
1426
        cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
1418
1427
        cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
1425
1434
        self.assertEqual(['two', 'one'], cgi2._index_names)
1426
1435
 
1427
1436
    def test_validate_reloads(self):
1428
 
        index, reload_counter = self.make_combined_index_with_missing()
1429
 
        index.validate()
 
1437
        idx, reload_counter = self.make_combined_index_with_missing()
 
1438
        idx.validate()
1430
1439
        self.assertEqual([1, 1, 0], reload_counter)
1431
1440
 
1432
1441
    def test_validate_reloads_midway(self):
1433
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1434
 
        index.validate()
 
1442
        idx, reload_counter = self.make_combined_index_with_missing(['2'])
 
1443
        idx.validate()
1435
1444
 
1436
1445
    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)
 
1446
        idx, reload_counter = self.make_combined_index_with_missing()
 
1447
        idx._reload_func = None
 
1448
        self.assertRaises(errors.NoSuchFile, idx.validate)
1440
1449
 
1441
1450
    def test_validate_reloads_and_fails(self):
1442
 
        index, reload_counter = self.make_combined_index_with_missing(
1443
 
                                    ['1', '2', '3'])
1444
 
        self.assertRaises(errors.NoSuchFile, index.validate)
 
1451
        idx, reload_counter = self.make_combined_index_with_missing(
 
1452
            ['1', '2', '3'])
 
1453
        self.assertRaises(errors.NoSuchFile, idx.validate)
1445
1454
 
1446
1455
    def test_find_ancestors_across_indexes(self):
1447
1456
        key1 = ('key-1',)
1456
1465
            (key3, 'value', ([key2],)),
1457
1466
            (key4, 'value', ([key3],)),
1458
1467
            ])
1459
 
        c_index = CombinedGraphIndex([index1, index2])
 
1468
        c_index = index.CombinedGraphIndex([index1, index2])
1460
1469
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1461
1470
        self.assertEqual({key1: ()}, parent_map)
1462
1471
        self.assertEqual(set(), missing_keys)
1479
1488
        index2 = self.make_index('34', ref_lists=1, nodes=[
1480
1489
            (key3, 'value', ([key2],)),
1481
1490
            ])
1482
 
        c_index = CombinedGraphIndex([index1, index2])
 
1491
        c_index = index.CombinedGraphIndex([index1, index2])
1483
1492
        # Searching for a key which is actually not present at all should
1484
1493
        # eventually converge
1485
1494
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1486
1495
        self.assertEqual({}, parent_map)
1487
 
        self.assertEqual(set([key4]), missing_keys)
 
1496
        self.assertEqual({key4}, missing_keys)
1488
1497
 
1489
1498
    def test_find_ancestors_no_indexes(self):
1490
 
        c_index = CombinedGraphIndex([])
 
1499
        c_index = index.CombinedGraphIndex([])
1491
1500
        key1 = ('key-1',)
1492
1501
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1493
1502
        self.assertEqual({}, parent_map)
1494
 
        self.assertEqual(set([key1]), missing_keys)
 
1503
        self.assertEqual({key1}, missing_keys)
1495
1504
 
1496
1505
    def test_find_ancestors_ghost_parent(self):
1497
1506
        key1 = ('key-1',)
1505
1514
        index2 = self.make_index('34', ref_lists=1, nodes=[
1506
1515
            (key4, 'value', ([key2, key3],)),
1507
1516
            ])
1508
 
        c_index = CombinedGraphIndex([index1, index2])
 
1517
        c_index = index.CombinedGraphIndex([index1, index2])
1509
1518
        # Searching for a key which is actually not present at all should
1510
1519
        # eventually converge
1511
1520
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1512
1521
        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1513
1522
                         parent_map)
1514
 
        self.assertEqual(set([key3]), missing_keys)
 
1523
        self.assertEqual({key3}, missing_keys)
1515
1524
 
1516
1525
    def test__find_ancestors_empty_index(self):
1517
 
        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
 
1526
        idx = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1518
1527
        parent_map = {}
1519
1528
        missing_keys = set()
1520
 
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1521
 
                                            missing_keys)
 
1529
        search_keys = idx._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1530
                                          missing_keys)
1522
1531
        self.assertEqual(set(), search_keys)
1523
1532
        self.assertEqual({}, parent_map)
1524
 
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1525
 
 
1526
 
 
1527
 
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
 
1533
        self.assertEqual({('one',), ('two',)}, missing_keys)
 
1534
 
 
1535
 
 
1536
class TestInMemoryGraphIndex(tests.TestCaseWithMemoryTransport):
1528
1537
 
1529
1538
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1530
 
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
 
1539
        result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1531
1540
        result.add_nodes(nodes)
1532
1541
        return result
1533
1542
 
1535
1544
        index = self.make_index(0)
1536
1545
        index.add_nodes([(('name', ), 'data')])
1537
1546
        index.add_nodes([(('name2', ), ''), (('name3', ), '')])
1538
 
        self.assertEqual(set([
 
1547
        self.assertEqual({
1539
1548
            (index, ('name', ), 'data'),
1540
1549
            (index, ('name2', ), ''),
1541
1550
            (index, ('name3', ), ''),
1542
 
            ]), set(index.iter_all_entries()))
 
1551
            }, set(index.iter_all_entries()))
1543
1552
 
1544
1553
    def test_add_nodes(self):
1545
1554
        index = self.make_index(1)
1546
1555
        index.add_nodes([(('name', ), 'data', ([],))])
1547
1556
        index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
1548
 
        self.assertEqual(set([
 
1557
        self.assertEqual({
1549
1558
            (index, ('name', ), 'data', ((),)),
1550
1559
            (index, ('name2', ), '', ((),)),
1551
1560
            (index, ('name3', ), '', ((('r', ), ), )),
1552
 
            ]), set(index.iter_all_entries()))
 
1561
            }, set(index.iter_all_entries()))
1553
1562
 
1554
1563
    def test_iter_all_entries_empty(self):
1555
1564
        index = self.make_index()
1564
1573
        index = self.make_index(1, nodes=[
1565
1574
            (('name', ), 'data', ([('ref', )], )),
1566
1575
            (('ref', ), 'refdata', ([], ))])
1567
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref', ),),)),
1568
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
1576
        self.assertEqual({(index, ('name', ), 'data', ((('ref', ),),)),
 
1577
            (index, ('ref', ), 'refdata', ((), ))},
1569
1578
            set(index.iter_all_entries()))
1570
1579
 
1571
1580
    def test_iteration_absent_skipped(self):
1572
1581
        index = self.make_index(1, nodes=[
1573
1582
            (('name', ), 'data', ([('ref', )], ))])
1574
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
 
1583
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
1575
1584
            set(index.iter_all_entries()))
1576
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
 
1585
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
1577
1586
            set(index.iter_entries([('name', )])))
1578
1587
        self.assertEqual([], list(index.iter_entries([('ref', )])))
1579
1588
 
1581
1590
        index = self.make_index(1, nodes=[
1582
1591
            (('name', ), 'data', ([('ref', )], )),
1583
1592
            (('ref', ), 'refdata', ([], ))])
1584
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1585
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
1593
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
1594
            (index, ('ref', ), 'refdata', ((), ))},
1586
1595
            set(index.iter_entries([('name', ), ('ref', )])))
1587
1596
 
1588
1597
    def test_iter_key_prefix_1_key_element_no_refs(self):
1589
1598
        index = self.make_index( nodes=[
1590
1599
            (('name', ), 'data'),
1591
1600
            (('ref', ), 'refdata')])
1592
 
        self.assertEqual(set([(index, ('name', ), 'data'),
1593
 
            (index, ('ref', ), 'refdata')]),
 
1601
        self.assertEqual({(index, ('name', ), 'data'),
 
1602
            (index, ('ref', ), 'refdata')},
1594
1603
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
1595
1604
 
1596
1605
    def test_iter_key_prefix_1_key_element_refs(self):
1597
1606
        index = self.make_index(1, nodes=[
1598
1607
            (('name', ), 'data', ([('ref', )], )),
1599
1608
            (('ref', ), 'refdata', ([], ))])
1600
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1601
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
1609
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
1610
            (index, ('ref', ), 'refdata', ((), ))},
1602
1611
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
1603
1612
 
1604
1613
    def test_iter_key_prefix_2_key_element_no_refs(self):
1606
1615
            (('name', 'fin1'), 'data'),
1607
1616
            (('name', 'fin2'), 'beta'),
1608
1617
            (('ref', 'erence'), 'refdata')])
1609
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1610
 
            (index, ('ref', 'erence'), 'refdata')]),
 
1618
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
1619
            (index, ('ref', 'erence'), 'refdata')},
1611
1620
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1612
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1613
 
            (index, ('name', 'fin2'), 'beta')]),
 
1621
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
1622
            (index, ('name', 'fin2'), 'beta')},
1614
1623
            set(index.iter_entries_prefix([('name', None)])))
1615
1624
 
1616
1625
    def test_iter_key_prefix_2_key_element_refs(self):
1618
1627
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
1619
1628
            (('name', 'fin2'), 'beta', ([], )),
1620
1629
            (('ref', 'erence'), 'refdata', ([], ))])
1621
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1622
 
            (index, ('ref', 'erence'), 'refdata', ((), ))]),
 
1630
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1631
            (index, ('ref', 'erence'), 'refdata', ((), ))},
1623
1632
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1624
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1625
 
            (index, ('name', 'fin2'), 'beta', ((), ))]),
 
1633
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1634
            (index, ('name', 'fin2'), 'beta', ((), ))},
1626
1635
            set(index.iter_entries_prefix([('name', None)])))
1627
1636
 
1628
1637
    def test_iter_nothing_empty(self):
1654
1663
        index.validate()
1655
1664
 
1656
1665
 
1657
 
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
 
1666
class TestGraphIndexPrefixAdapter(tests.TestCaseWithMemoryTransport):
1658
1667
 
1659
 
    def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
1660
 
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
 
1668
    def make_index(self, ref_lists=1, key_elements=2, nodes=[],
 
1669
                   add_callback=False):
 
1670
        result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1661
1671
        result.add_nodes(nodes)
1662
1672
        if add_callback:
1663
1673
            add_nodes_callback = result.add_nodes
1664
1674
        else:
1665
1675
            add_nodes_callback = None
1666
 
        adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
 
1676
        adapter = index.GraphIndexPrefixAdapter(
 
1677
            result, ('prefix', ), key_elements - 1,
1667
1678
            add_nodes_callback=add_nodes_callback)
1668
1679
        return result, adapter
1669
1680
 
1670
1681
    def test_add_node(self):
1671
1682
        index, adapter = self.make_index(add_callback=True)
1672
1683
        adapter.add_node(('key',), 'value', ((('ref',),),))
1673
 
        self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
 
1684
        self.assertEqual({(index, ('prefix', 'key'), 'value',
 
1685
                               ((('prefix', 'ref'),),))},
1674
1686
            set(index.iter_all_entries()))
1675
1687
 
1676
1688
    def test_add_nodes(self):
1679
1691
            (('key',), 'value', ((('ref',),),)),
1680
1692
            (('key2',), 'value2', ((),)),
1681
1693
            ))
1682
 
        self.assertEqual(set([
 
1694
        self.assertEqual({
1683
1695
            (index, ('prefix', 'key2'), 'value2', ((),)),
1684
1696
            (index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1685
 
            ]),
 
1697
            },
1686
1698
            set(index.iter_all_entries()))
1687
1699
 
1688
1700
    def test_construct(self):
1689
 
        index = InMemoryGraphIndex()
1690
 
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
 
1701
        idx = index.InMemoryGraphIndex()
 
1702
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1)
1691
1703
 
1692
1704
    def test_construct_with_callback(self):
1693
 
        index = InMemoryGraphIndex()
1694
 
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
 
1705
        idx = index.InMemoryGraphIndex()
 
1706
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1,
 
1707
                                                idx.add_nodes)
1695
1708
 
1696
1709
    def test_iter_all_entries_cross_prefix_map_errors(self):
1697
1710
        index, adapter = self.make_index(nodes=[
1703
1716
            (('notprefix', 'key1'), 'data', ((), )),
1704
1717
            (('prefix', 'key1'), 'data1', ((), )),
1705
1718
            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1706
 
        self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1707
 
            (index, ('key2', ), 'data2', ((('key1',),),))]),
 
1719
        self.assertEqual({(index, ('key1', ), 'data1', ((),)),
 
1720
            (index, ('key2', ), 'data2', ((('key1',),),))},
1708
1721
            set(adapter.iter_all_entries()))
1709
1722
 
1710
1723
    def test_iter_entries(self):
1713
1726
            (('prefix', 'key1'), 'data1', ((), )),
1714
1727
            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1715
1728
        # ask for many - get all
1716
 
        self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1717
 
            (index, ('key2', ), 'data2', ((('key1', ),),))]),
 
1729
        self.assertEqual({(index, ('key1', ), 'data1', ((),)),
 
1730
            (index, ('key2', ), 'data2', ((('key1', ),),))},
1718
1731
            set(adapter.iter_entries([('key1', ), ('key2', )])))
1719
1732
        # ask for one, get one
1720
 
        self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
 
1733
        self.assertEqual({(index, ('key1', ), 'data1', ((),))},
1721
1734
            set(adapter.iter_entries([('key1', )])))
1722
1735
        # ask for missing, get none
1723
1736
        self.assertEqual(set(),
1729
1742
            (('prefix', 'prefix2', 'key1'), 'data1', ((), )),
1730
1743
            (('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1731
1744
        # ask for a prefix, get the results for just that prefix, adjusted.
1732
 
        self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
1733
 
            (index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
 
1745
        self.assertEqual({(index, ('prefix2', 'key1', ), 'data1', ((),)),
 
1746
            (index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))},
1734
1747
            set(adapter.iter_entries_prefix([('prefix2', None)])))
1735
1748
 
1736
1749
    def test_key_count_no_matching_keys(self):