/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: 2018-02-18 21:42:57 UTC
  • mto: This revision was merged to the branch mainline in revision 6859.
  • Revision ID: jelmer@jelmer.uk-20180218214257-jpevutp1wa30tz3v
Update TODO to reference Breezy, not Bazaar.

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 ... import (
 
19
from .. import (
20
20
    errors,
21
21
    tests,
22
22
    transport,
23
23
    )
24
 
from .. import (
 
24
from ..bzr import (
25
25
    index as _mod_index,
26
26
    )
27
27
 
31
31
    def test_bad_index_format_signature(self):
32
32
        error = _mod_index.BadIndexFormatSignature("foo", "bar")
33
33
        self.assertEqual("foo is not an index of type bar.",
34
 
                         str(error))
 
34
            str(error))
35
35
 
36
36
    def test_bad_index_data(self):
37
37
        error = _mod_index.BadIndexData("foo")
38
38
        self.assertEqual("Error in data for index foo.",
39
 
                         str(error))
 
39
            str(error))
40
40
 
41
41
    def test_bad_index_duplicate_key(self):
42
42
        error = _mod_index.BadIndexDuplicateKey("foo", "bar")
43
43
        self.assertEqual("The key 'foo' is already in index 'bar'.",
44
 
                         str(error))
 
44
            str(error))
45
45
 
46
46
    def test_bad_index_key(self):
47
47
        error = _mod_index.BadIndexKey("foo")
48
48
        self.assertEqual("The key 'foo' is not a valid key.",
49
 
                         str(error))
 
49
            str(error))
50
50
 
51
51
    def test_bad_index_options(self):
52
52
        error = _mod_index.BadIndexOptions("foo")
53
53
        self.assertEqual("Could not parse options for index foo.",
54
 
                         str(error))
 
54
            str(error))
55
55
 
56
56
    def test_bad_index_value(self):
57
57
        error = _mod_index.BadIndexValue("foo")
58
58
        self.assertEqual("The value 'foo' is not a valid value.",
59
 
                         str(error))
 
59
            str(error))
60
60
 
61
61
 
62
62
class TestGraphIndexBuilder(tests.TestCaseWithMemoryTransport):
66
66
        stream = builder.finish()
67
67
        contents = stream.read()
68
68
        self.assertEqual(
69
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
 
69
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
70
70
            contents)
71
71
 
72
72
    def test_build_index_empty_two_element_keys(self):
74
74
        stream = builder.finish()
75
75
        contents = stream.read()
76
76
        self.assertEqual(
77
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
 
77
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
78
78
            contents)
79
79
 
80
80
    def test_build_index_one_reference_list_empty(self):
82
82
        stream = builder.finish()
83
83
        contents = stream.read()
84
84
        self.assertEqual(
85
 
            b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
 
85
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
86
86
            contents)
87
87
 
88
88
    def test_build_index_two_reference_list_empty(self):
90
90
        stream = builder.finish()
91
91
        contents = stream.read()
92
92
        self.assertEqual(
93
 
            b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
 
93
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
94
94
            contents)
95
95
 
96
96
    def test_build_index_one_node_no_refs(self):
97
97
        builder = _mod_index.GraphIndexBuilder()
98
 
        builder.add_node((b'akey', ), b'data')
 
98
        builder.add_node(('akey', ), 'data')
99
99
        stream = builder.finish()
100
100
        contents = stream.read()
101
101
        self.assertEqual(
102
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
103
 
            b"akey\x00\x00\x00data\n\n", contents)
 
102
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
 
103
            "akey\x00\x00\x00data\n\n", contents)
104
104
 
105
105
    def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
106
106
        builder = _mod_index.GraphIndexBuilder()
107
 
        builder.add_node((b'akey', ), b'data', ())
 
107
        builder.add_node(('akey', ), 'data', ())
108
108
        stream = builder.finish()
109
109
        contents = stream.read()
110
110
        self.assertEqual(
111
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
112
 
            b"akey\x00\x00\x00data\n\n", contents)
 
111
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
 
112
            "akey\x00\x00\x00data\n\n", contents)
113
113
 
114
114
    def test_build_index_one_node_2_element_keys(self):
115
115
        # multipart keys are separated by \x00 - because they are fixed length,
116
116
        # not variable this does not cause any issues, and seems clearer to the
117
117
        # author.
118
118
        builder = _mod_index.GraphIndexBuilder(key_elements=2)
119
 
        builder.add_node((b'akey', b'secondpart'), b'data')
 
119
        builder.add_node(('akey', 'secondpart'), 'data')
120
120
        stream = builder.finish()
121
121
        contents = stream.read()
122
122
        self.assertEqual(
123
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
124
 
            b"akey\x00secondpart\x00\x00\x00data\n\n", contents)
 
123
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
 
124
            "akey\x00secondpart\x00\x00\x00data\n\n", contents)
125
125
 
126
126
    def test_add_node_empty_value(self):
127
127
        builder = _mod_index.GraphIndexBuilder()
128
 
        builder.add_node((b'akey', ), b'')
 
128
        builder.add_node(('akey', ), '')
129
129
        stream = builder.finish()
130
130
        contents = stream.read()
131
131
        self.assertEqual(
132
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
133
 
            b"akey\x00\x00\x00\n\n", contents)
 
132
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
 
133
            "akey\x00\x00\x00\n\n", contents)
134
134
 
135
135
    def test_build_index_nodes_sorted(self):
136
136
        # the highest sorted node comes first.
138
138
        # use three to have a good chance of glitching dictionary hash
139
139
        # lookups etc. Insert in randomish order that is not correct
140
140
        # and not the reverse of the correct order.
141
 
        builder.add_node((b'2002', ), b'data')
142
 
        builder.add_node((b'2000', ), b'data')
143
 
        builder.add_node((b'2001', ), b'data')
 
141
        builder.add_node(('2002', ), 'data')
 
142
        builder.add_node(('2000', ), 'data')
 
143
        builder.add_node(('2001', ), 'data')
144
144
        stream = builder.finish()
145
145
        contents = stream.read()
146
146
        self.assertEqual(
147
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
148
 
            b"2000\x00\x00\x00data\n"
149
 
            b"2001\x00\x00\x00data\n"
150
 
            b"2002\x00\x00\x00data\n"
151
 
            b"\n", contents)
 
147
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
 
148
            "2000\x00\x00\x00data\n"
 
149
            "2001\x00\x00\x00data\n"
 
150
            "2002\x00\x00\x00data\n"
 
151
            "\n", contents)
152
152
 
153
153
    def test_build_index_2_element_key_nodes_sorted(self):
154
154
        # multiple element keys are sorted first-key, second-key.
156
156
        # use three values of each key element, to have a good chance of
157
157
        # glitching dictionary hash lookups etc. Insert in randomish order that
158
158
        # is not correct and not the reverse of the correct order.
159
 
        builder.add_node((b'2002', b'2002'), b'data')
160
 
        builder.add_node((b'2002', b'2000'), b'data')
161
 
        builder.add_node((b'2002', b'2001'), b'data')
162
 
        builder.add_node((b'2000', b'2002'), b'data')
163
 
        builder.add_node((b'2000', b'2000'), b'data')
164
 
        builder.add_node((b'2000', b'2001'), b'data')
165
 
        builder.add_node((b'2001', b'2002'), b'data')
166
 
        builder.add_node((b'2001', b'2000'), b'data')
167
 
        builder.add_node((b'2001', b'2001'), b'data')
 
159
        builder.add_node(('2002', '2002'), 'data')
 
160
        builder.add_node(('2002', '2000'), 'data')
 
161
        builder.add_node(('2002', '2001'), 'data')
 
162
        builder.add_node(('2000', '2002'), 'data')
 
163
        builder.add_node(('2000', '2000'), 'data')
 
164
        builder.add_node(('2000', '2001'), 'data')
 
165
        builder.add_node(('2001', '2002'), 'data')
 
166
        builder.add_node(('2001', '2000'), 'data')
 
167
        builder.add_node(('2001', '2001'), 'data')
168
168
        stream = builder.finish()
169
169
        contents = stream.read()
170
170
        self.assertEqual(
171
 
            b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
172
 
            b"2000\x002000\x00\x00\x00data\n"
173
 
            b"2000\x002001\x00\x00\x00data\n"
174
 
            b"2000\x002002\x00\x00\x00data\n"
175
 
            b"2001\x002000\x00\x00\x00data\n"
176
 
            b"2001\x002001\x00\x00\x00data\n"
177
 
            b"2001\x002002\x00\x00\x00data\n"
178
 
            b"2002\x002000\x00\x00\x00data\n"
179
 
            b"2002\x002001\x00\x00\x00data\n"
180
 
            b"2002\x002002\x00\x00\x00data\n"
181
 
            b"\n", contents)
 
171
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
 
172
            "2000\x002000\x00\x00\x00data\n"
 
173
            "2000\x002001\x00\x00\x00data\n"
 
174
            "2000\x002002\x00\x00\x00data\n"
 
175
            "2001\x002000\x00\x00\x00data\n"
 
176
            "2001\x002001\x00\x00\x00data\n"
 
177
            "2001\x002002\x00\x00\x00data\n"
 
178
            "2002\x002000\x00\x00\x00data\n"
 
179
            "2002\x002001\x00\x00\x00data\n"
 
180
            "2002\x002002\x00\x00\x00data\n"
 
181
            "\n", contents)
182
182
 
183
183
    def test_build_index_reference_lists_are_included_one(self):
184
184
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
185
 
        builder.add_node((b'key', ), b'data', ([], ))
 
185
        builder.add_node(('key', ), 'data', ([], ))
186
186
        stream = builder.finish()
187
187
        contents = stream.read()
188
188
        self.assertEqual(
189
 
            b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
190
 
            b"key\x00\x00\x00data\n"
191
 
            b"\n", contents)
 
189
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
 
190
            "key\x00\x00\x00data\n"
 
191
            "\n", contents)
192
192
 
193
193
    def test_build_index_reference_lists_with_2_element_keys(self):
194
 
        builder = _mod_index.GraphIndexBuilder(
195
 
            reference_lists=1, key_elements=2)
196
 
        builder.add_node((b'key', b'key2'), b'data', ([], ))
 
194
        builder = _mod_index.GraphIndexBuilder(reference_lists=1, key_elements=2)
 
195
        builder.add_node(('key', 'key2'), 'data', ([], ))
197
196
        stream = builder.finish()
198
197
        contents = stream.read()
199
198
        self.assertEqual(
200
 
            b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
201
 
            b"key\x00key2\x00\x00\x00data\n"
202
 
            b"\n", contents)
 
199
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
 
200
            "key\x00key2\x00\x00\x00data\n"
 
201
            "\n", contents)
203
202
 
204
203
    def test_build_index_reference_lists_are_included_two(self):
205
204
        builder = _mod_index.GraphIndexBuilder(reference_lists=2)
206
 
        builder.add_node((b'key', ), b'data', ([], []))
 
205
        builder.add_node(('key', ), 'data', ([], []))
207
206
        stream = builder.finish()
208
207
        contents = stream.read()
209
208
        self.assertEqual(
210
 
            b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
211
 
            b"key\x00\x00\t\x00data\n"
212
 
            b"\n", contents)
 
209
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
 
210
            "key\x00\x00\t\x00data\n"
 
211
            "\n", contents)
213
212
 
214
213
    def test_clear_cache(self):
215
214
        builder = _mod_index.GraphIndexBuilder(reference_lists=2)
218
217
 
219
218
    def test_node_references_are_byte_offsets(self):
220
219
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
221
 
        builder.add_node((b'reference', ), b'data', ([], ))
222
 
        builder.add_node((b'key', ), b'data', ([(b'reference', )], ))
 
220
        builder.add_node(('reference', ), 'data', ([], ))
 
221
        builder.add_node(('key', ), 'data', ([('reference', )], ))
223
222
        stream = builder.finish()
224
223
        contents = stream.read()
225
224
        self.assertEqual(
226
 
            b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
227
 
            b"key\x00\x0072\x00data\n"
228
 
            b"reference\x00\x00\x00data\n"
229
 
            b"\n", contents)
 
225
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
 
226
            "key\x00\x0072\x00data\n"
 
227
            "reference\x00\x00\x00data\n"
 
228
            "\n", contents)
230
229
 
231
230
    def test_node_references_are_cr_delimited(self):
232
231
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
233
 
        builder.add_node((b'reference', ), b'data', ([], ))
234
 
        builder.add_node((b'reference2', ), b'data', ([], ))
235
 
        builder.add_node((b'key', ), b'data',
236
 
                         ([(b'reference', ), (b'reference2', )], ))
 
232
        builder.add_node(('reference', ), 'data', ([], ))
 
233
        builder.add_node(('reference2', ), 'data', ([], ))
 
234
        builder.add_node(('key', ), 'data',
 
235
                         ([('reference', ), ('reference2', )], ))
237
236
        stream = builder.finish()
238
237
        contents = stream.read()
239
238
        self.assertEqual(
240
 
            b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
241
 
            b"key\x00\x00077\r094\x00data\n"
242
 
            b"reference\x00\x00\x00data\n"
243
 
            b"reference2\x00\x00\x00data\n"
244
 
            b"\n", contents)
 
239
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
 
240
            "key\x00\x00077\r094\x00data\n"
 
241
            "reference\x00\x00\x00data\n"
 
242
            "reference2\x00\x00\x00data\n"
 
243
            "\n", contents)
245
244
 
246
245
    def test_multiple_reference_lists_are_tab_delimited(self):
247
246
        builder = _mod_index.GraphIndexBuilder(reference_lists=2)
248
 
        builder.add_node((b'keference', ), b'data', ([], []))
249
 
        builder.add_node((b'rey', ), b'data',
250
 
                         ([(b'keference', )], [(b'keference', )]))
 
247
        builder.add_node(('keference', ), 'data', ([], []))
 
248
        builder.add_node(('rey', ), 'data',
 
249
                         ([('keference', )], [('keference', )]))
251
250
        stream = builder.finish()
252
251
        contents = stream.read()
253
252
        self.assertEqual(
254
 
            b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
255
 
            b"keference\x00\x00\t\x00data\n"
256
 
            b"rey\x00\x0059\t59\x00data\n"
257
 
            b"\n", contents)
 
253
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
 
254
            "keference\x00\x00\t\x00data\n"
 
255
            "rey\x00\x0059\t59\x00data\n"
 
256
            "\n", contents)
258
257
 
259
258
    def test_add_node_referencing_missing_key_makes_absent(self):
260
259
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
261
 
        builder.add_node((b'rey', ), b'data',
262
 
                         ([(b'beference', ), (b'aeference2', )], ))
 
260
        builder.add_node(('rey', ), 'data',
 
261
                         ([('beference', ), ('aeference2', )], ))
263
262
        stream = builder.finish()
264
263
        contents = stream.read()
265
264
        self.assertEqual(
266
 
            b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
267
 
            b"aeference2\x00a\x00\x00\n"
268
 
            b"beference\x00a\x00\x00\n"
269
 
            b"rey\x00\x00074\r059\x00data\n"
270
 
            b"\n", contents)
 
265
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
 
266
            "aeference2\x00a\x00\x00\n"
 
267
            "beference\x00a\x00\x00\n"
 
268
            "rey\x00\x00074\r059\x00data\n"
 
269
            "\n", contents)
271
270
 
272
271
    def test_node_references_three_digits(self):
273
272
        # test the node digit expands as needed.
274
273
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
275
 
        references = [((b"%d" % val), ) for val in range(8, -1, -1)]
276
 
        builder.add_node((b'2-key', ), b'', (references, ))
 
274
        references = [(str(val), ) for val in range(8, -1, -1)]
 
275
        builder.add_node(('2-key', ), '', (references, ))
277
276
        stream = builder.finish()
278
277
        contents = stream.read()
279
278
        self.assertEqualDiff(
280
 
            b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
281
 
            b"0\x00a\x00\x00\n"
282
 
            b"1\x00a\x00\x00\n"
283
 
            b"2\x00a\x00\x00\n"
284
 
            b"2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
285
 
            b"3\x00a\x00\x00\n"
286
 
            b"4\x00a\x00\x00\n"
287
 
            b"5\x00a\x00\x00\n"
288
 
            b"6\x00a\x00\x00\n"
289
 
            b"7\x00a\x00\x00\n"
290
 
            b"8\x00a\x00\x00\n"
291
 
            b"\n", contents)
 
279
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
 
280
            "0\x00a\x00\x00\n"
 
281
            "1\x00a\x00\x00\n"
 
282
            "2\x00a\x00\x00\n"
 
283
            "2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
 
284
            "3\x00a\x00\x00\n"
 
285
            "4\x00a\x00\x00\n"
 
286
            "5\x00a\x00\x00\n"
 
287
            "6\x00a\x00\x00\n"
 
288
            "7\x00a\x00\x00\n"
 
289
            "8\x00a\x00\x00\n"
 
290
            "\n", contents)
292
291
 
293
292
    def test_absent_has_no_reference_overhead(self):
294
293
        # the offsets after an absent record should be correct when there are
295
294
        # >1 reference lists.
296
295
        builder = _mod_index.GraphIndexBuilder(reference_lists=2)
297
 
        builder.add_node((b'parent', ), b'', ([(b'aail', ), (b'zther', )], []))
 
296
        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
298
297
        stream = builder.finish()
299
298
        contents = stream.read()
300
299
        self.assertEqual(
301
 
            b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
302
 
            b"aail\x00a\x00\x00\n"
303
 
            b"parent\x00\x0059\r84\t\x00\n"
304
 
            b"zther\x00a\x00\x00\n"
305
 
            b"\n", contents)
 
300
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
 
301
            "aail\x00a\x00\x00\n"
 
302
            "parent\x00\x0059\r84\t\x00\n"
 
303
            "zther\x00a\x00\x00\n"
 
304
            "\n", contents)
306
305
 
307
306
    def test_add_node_bad_key(self):
308
307
        builder = _mod_index.GraphIndexBuilder()
309
 
        for bad_char in bytearray(b'\t\n\x0b\x0c\r\x00 '):
 
308
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
310
309
            self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
311
 
                              (b'a%skey' % bytes([bad_char]), ), b'data')
312
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
313
 
                          (), b'data')
314
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
315
 
                          b'not-a-tuple', b'data')
 
310
                ('a%skey' % bad_char, ), 'data')
 
311
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
 
312
                ('', ), 'data')
 
313
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
 
314
                'not-a-tuple', 'data')
316
315
        # not enough length
317
316
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
318
 
                          (), b'data')
 
317
                (), 'data')
319
318
        # too long
320
319
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
321
 
                          (b'primary', b'secondary'), b'data')
 
320
                ('primary', 'secondary'), 'data')
322
321
        # secondary key elements get checked too:
323
322
        builder = _mod_index.GraphIndexBuilder(key_elements=2)
324
 
        for bad_char in bytearray(b'\t\n\x0b\x0c\r\x00 '):
 
323
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
325
324
            self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
326
 
                              (b'prefix', b'a%skey' % bytes([bad_char])), b'data')
 
325
                ('prefix', 'a%skey' % bad_char), 'data')
327
326
 
328
327
    def test_add_node_bad_data(self):
329
328
        builder = _mod_index.GraphIndexBuilder()
330
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
331
 
                          b'data\naa')
332
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
333
 
                          b'data\x00aa')
 
329
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
330
            'data\naa')
 
331
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
332
            'data\x00aa')
334
333
 
335
334
    def test_add_node_bad_mismatched_ref_lists_length(self):
336
335
        builder = _mod_index.GraphIndexBuilder()
337
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
338
 
                          b'data aa', ([], ))
 
336
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
337
            'data aa', ([], ))
339
338
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
340
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
341
 
                          b'data aa')
342
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
343
 
                          b'data aa', (), )
344
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
345
 
                          b'data aa', ([], []))
 
339
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
340
            'data aa')
 
341
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
342
            'data aa', (), )
 
343
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
344
            'data aa', ([], []))
346
345
        builder = _mod_index.GraphIndexBuilder(reference_lists=2)
347
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
348
 
                          b'data aa')
349
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
350
 
                          b'data aa', ([], ))
351
 
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
352
 
                          b'data aa', ([], [], []))
 
346
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
347
            'data aa')
 
348
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
349
            'data aa', ([], ))
 
350
        self.assertRaises(_mod_index.BadIndexValue, builder.add_node, ('akey', ),
 
351
            'data aa', ([], [], []))
353
352
 
354
353
    def test_add_node_bad_key_in_reference_lists(self):
355
354
        # first list, first key - trivial
356
355
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
357
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
358
 
                          b'data aa', ([(b'a key', )], ))
 
356
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, ('akey', ),
 
357
            'data aa', ([('a key', )], ))
359
358
        # references keys must be tuples too
360
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
361
 
                          b'data aa', (['not-a-tuple'], ))
 
359
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, ('akey', ),
 
360
            'data aa', (['not-a-tuple'], ))
362
361
        # not enough length
363
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
364
 
                          b'data aa', ([()], ))
 
362
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, ('akey', ),
 
363
            'data aa', ([()], ))
365
364
        # too long
366
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
367
 
                          b'data aa', ([(b'primary', b'secondary')], ))
 
365
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, ('akey', ),
 
366
            'data aa', ([('primary', 'secondary')], ))
368
367
        # need to check more than the first key in the list
369
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
370
 
                          b'data aa', ([(b'agoodkey', ), (b'that is a bad key', )], ))
 
368
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, ('akey', ),
 
369
            'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
371
370
        # and if there is more than one list it should be getting checked
372
371
        # too
373
372
        builder = _mod_index.GraphIndexBuilder(reference_lists=2)
374
 
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
375
 
                          b'data aa', ([], ['a bad key']))
 
373
        self.assertRaises(_mod_index.BadIndexKey, builder.add_node, ('akey', ),
 
374
            'data aa', ([], ['a bad key']))
376
375
 
377
376
    def test_add_duplicate_key(self):
378
377
        builder = _mod_index.GraphIndexBuilder()
379
 
        builder.add_node((b'key', ), b'data')
 
378
        builder.add_node(('key', ), 'data')
380
379
        self.assertRaises(_mod_index.BadIndexDuplicateKey,
381
 
                          builder.add_node, (b'key', ), b'data')
 
380
                          builder.add_node, ('key', ), 'data')
382
381
 
383
382
    def test_add_duplicate_key_2_elements(self):
384
383
        builder = _mod_index.GraphIndexBuilder(key_elements=2)
385
 
        builder.add_node((b'key', b'key'), b'data')
 
384
        builder.add_node(('key', 'key'), 'data')
386
385
        self.assertRaises(_mod_index.BadIndexDuplicateKey, builder.add_node,
387
 
                          (b'key', b'key'), b'data')
 
386
            ('key', 'key'), 'data')
388
387
 
389
388
    def test_add_key_after_referencing_key(self):
390
389
        builder = _mod_index.GraphIndexBuilder(reference_lists=1)
391
 
        builder.add_node((b'key', ), b'data', ([(b'reference', )], ))
392
 
        builder.add_node((b'reference', ), b'data', ([],))
 
390
        builder.add_node(('key', ), 'data', ([('reference', )], ))
 
391
        builder.add_node(('reference', ), 'data', ([],))
393
392
 
394
393
    def test_add_key_after_referencing_key_2_elements(self):
395
 
        builder = _mod_index.GraphIndexBuilder(
396
 
            reference_lists=1, key_elements=2)
397
 
        builder.add_node((b'k', b'ey'), b'data',
398
 
                         ([(b'reference', b'tokey')], ))
399
 
        builder.add_node((b'reference', b'tokey'), b'data', ([],))
 
394
        builder = _mod_index.GraphIndexBuilder(reference_lists=1, key_elements=2)
 
395
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
 
396
        builder.add_node(('reference', 'tokey'), 'data', ([],))
400
397
 
401
398
    def test_set_optimize(self):
402
 
        builder = _mod_index.GraphIndexBuilder(
403
 
            reference_lists=1, key_elements=2)
 
399
        builder = _mod_index.GraphIndexBuilder(reference_lists=1, key_elements=2)
404
400
        builder.set_optimize(for_size=True)
405
401
        self.assertTrue(builder._optimize_for_size)
406
402
        builder.set_optimize(for_size=False)
410
406
class TestGraphIndex(tests.TestCaseWithMemoryTransport):
411
407
 
412
408
    def make_key(self, number):
413
 
        return ((b'%d' % number) + b'X' * 100,)
 
409
        return (str(number) + 'X'*100,)
414
410
 
415
411
    def make_value(self, number):
416
 
        return (b'%d' % number) + b'Y' * 100
 
412
            return str(number) + 'Y'*100
417
413
 
418
414
    def make_nodes(self, count=64):
419
415
        # generate a big enough index that we only read some of it on a typical
420
416
        # bisection lookup.
421
417
        nodes = []
422
418
        for counter in range(count):
423
 
            nodes.append(
424
 
                (self.make_key(counter), self.make_value(counter), ()))
 
419
            nodes.append((self.make_key(counter), self.make_value(counter), ()))
425
420
        return nodes
426
421
 
427
422
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
428
 
        builder = _mod_index.GraphIndexBuilder(
429
 
            ref_lists, key_elements=key_elements)
 
423
        builder = _mod_index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
430
424
        for key, value, references in nodes:
431
425
            builder.add_node(key, value, references)
432
426
        stream = builder.finish()
436
430
 
437
431
    def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
438
432
                               offset=0):
439
 
        builder = _mod_index.GraphIndexBuilder(
440
 
            ref_lists, key_elements=key_elements)
 
433
        builder = _mod_index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
441
434
        for key, value, references in nodes:
442
435
            builder.add_node(key, value, references)
443
436
        content = builder.finish().read()
444
437
        size = len(content)
445
438
        trans = self.get_transport()
446
 
        trans.put_bytes('index', (b' ' * offset) + content)
 
439
        trans.put_bytes('index', (' '*offset) + content)
447
440
        return _mod_index.GraphIndex(trans, 'index', size, offset=offset)
448
441
 
449
442
    def test_clear_cache(self):
454
447
 
455
448
    def test_open_bad_index_no_error(self):
456
449
        trans = self.get_transport()
457
 
        trans.put_bytes('name', b"not an index\n")
 
450
        trans.put_bytes('name', "not an index\n")
458
451
        idx = _mod_index.GraphIndex(trans, 'name', 13)
459
452
 
460
453
    def test_with_offset(self):
471
464
    def test_side_effect_buffering_with_offset(self):
472
465
        nodes = self.make_nodes(20)
473
466
        index = self.make_index_with_offset(offset=1234567, nodes=nodes)
474
 
        index._transport.recommended_page_size = lambda: 64 * 1024
 
467
        index._transport.recommended_page_size = lambda:64*1024
475
468
        subset_nodes = [nodes[0][0], nodes[10][0], nodes[19][0]]
476
469
        entries = [n[1] for n in index.iter_entries(subset_nodes)]
477
470
        self.assertEqual(sorted(subset_nodes), sorted(entries))
503
496
        # do a _lookup_keys_via_location call for the middle of the file, which
504
497
        # is what bisection uses.
505
498
        result = index._lookup_keys_via_location(
506
 
            [(index._size // 2, (b'missing', ))])
 
499
            [(index._size // 2, ('missing', ))])
507
500
        # this should have asked for a readv request, with adjust_for_latency,
508
501
        # and two regions: the header, and half-way into the file.
509
502
        self.assertEqual([
512
505
            index._transport._activity)
513
506
        # and the result should be that the key cannot be present, because this
514
507
        # is a trivial index.
515
 
        self.assertEqual([((index._size // 2, (b'missing', )), False)],
516
 
                         result)
 
508
        self.assertEqual([((index._size // 2, ('missing', )), False)],
 
509
            result)
517
510
        # And this should have caused the file to be fully buffered
518
511
        self.assertIsNot(None, index._nodes)
519
512
        self.assertEqual([], index._parsed_byte_map)
533
526
        # is what bisection uses.
534
527
        start_lookup = index._size // 2
535
528
        result = index._lookup_keys_via_location(
536
 
            [(start_lookup, (b'40missing', ))])
 
529
            [(start_lookup, ('40missing', ))])
537
530
        # this should have asked for a readv request, with adjust_for_latency,
538
531
        # and two regions: the header, and half-way into the file.
539
532
        self.assertEqual([
543
536
            index._transport._activity)
544
537
        # and the result should be that the key cannot be present, because this
545
538
        # is a trivial index.
546
 
        self.assertEqual([((start_lookup, (b'40missing', )), False)],
547
 
                         result)
 
539
        self.assertEqual([((start_lookup, ('40missing', )), False)],
 
540
            result)
548
541
        # And this should not have caused the file to be fully buffered
549
542
        self.assertIs(None, index._nodes)
550
543
        # And the regions of the file that have been parsed should be in the
551
544
        # parsed_byte_map and the parsed_key_map
552
545
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
553
 
        self.assertEqual([((), self.make_key(26)),
 
546
        self.assertEqual([(None, self.make_key(26)),
554
547
                          (self.make_key(31), self.make_key(48))],
555
548
                         index._parsed_key_map)
556
549
 
557
550
    def test_parsing_non_adjacent_data_trims(self):
558
551
        index = self.make_index(nodes=self.make_nodes(64))
559
552
        result = index._lookup_keys_via_location(
560
 
            [(index._size // 2, (b'40', ))])
 
553
            [(index._size // 2, ('40', ))])
561
554
        # and the result should be that the key cannot be present, because key is
562
555
        # in the middle of the observed data from a 4K read - the smallest transport
563
556
        # will do today with this api.
564
 
        self.assertEqual([((index._size // 2, (b'40', )), False)],
565
 
                         result)
 
557
        self.assertEqual([((index._size // 2, ('40', )), False)],
 
558
            result)
566
559
        # and we should have a parse map that includes the header and the
567
560
        # region that was parsed after trimming.
568
561
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
569
 
        self.assertEqual([((), self.make_key(26)),
 
562
        self.assertEqual([(None, self.make_key(26)),
570
563
                          (self.make_key(31), self.make_key(48))],
571
 
                         index._parsed_key_map)
 
564
            index._parsed_key_map)
572
565
 
573
566
    def test_parsing_data_handles_parsed_contained_regions(self):
574
567
        # the following patten creates a parsed region that is wholly within a
586
579
        # locations of both keys.
587
580
        index = self.make_index(nodes=self.make_nodes(128))
588
581
        result = index._lookup_keys_via_location(
589
 
            [(index._size // 2, (b'40', ))])
 
582
            [(index._size // 2, ('40', ))])
590
583
        # and we should have a parse map that includes the header and the
591
584
        # region that was parsed after trimming.
592
585
        self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
593
 
        self.assertEqual([((), self.make_key(116)),
 
586
        self.assertEqual([(None, self.make_key(116)),
594
587
                          (self.make_key(35), self.make_key(51))],
595
 
                         index._parsed_key_map)
 
588
            index._parsed_key_map)
596
589
        # now ask for two keys, right before and after the parsed region
597
590
        result = index._lookup_keys_via_location(
598
591
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
610
603
        # bisection lookup.
611
604
        index = self.make_index(nodes=self.make_nodes(64))
612
605
        # lookup the keys in the middle of the file
613
 
        result = index._lookup_keys_via_location(
614
 
            [(index._size // 2, (b'40', ))])
 
606
        result =index._lookup_keys_via_location(
 
607
            [(index._size // 2, ('40', ))])
615
608
        # check the parse map, this determines the test validity
616
609
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
617
 
        self.assertEqual([((), self.make_key(26)),
 
610
        self.assertEqual([(None, self.make_key(26)),
618
611
                          (self.make_key(31), self.make_key(48))],
619
 
                         index._parsed_key_map)
 
612
            index._parsed_key_map)
620
613
        # reset the transport log
621
614
        del index._transport._activity[:]
622
615
        # now looking up a key in the portion of the file already parsed should
624
617
        # be in the index) - even when the byte location we ask for is outside
625
618
        # the parsed region
626
619
        result = index._lookup_keys_via_location(
627
 
            [(4000, (b'40', ))])
628
 
        self.assertEqual([((4000, (b'40', )), False)],
629
 
                         result)
 
620
            [(4000, ('40', ))])
 
621
        self.assertEqual([((4000, ('40', )), False)],
 
622
            result)
630
623
        self.assertEqual([], index._transport._activity)
631
624
 
632
625
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
634
627
        # bisection lookup.
635
628
        index = self.make_index(nodes=self.make_nodes(64))
636
629
        # lookup the keys in the middle of the file
637
 
        result = index._lookup_keys_via_location(
638
 
            [(index._size // 2, (b'40', ))])
 
630
        result =index._lookup_keys_via_location(
 
631
            [(index._size // 2, ('40', ))])
639
632
        # check the parse map, this determines the test validity
640
633
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
641
 
        self.assertEqual([((), self.make_key(26)),
 
634
        self.assertEqual([(None, self.make_key(26)),
642
635
                          (self.make_key(31), self.make_key(48))],
643
 
                         index._parsed_key_map)
 
636
            index._parsed_key_map)
644
637
        # reset the transport log
645
638
        del index._transport._activity[:]
646
639
        # now looking up a key in the portion of the file already parsed should
661
654
        index = self.make_index(nodes=self.make_nodes(64))
662
655
        # ask for the key in the middle, but a key that is located in the
663
656
        # unparsed region before the middle.
664
 
        result = index._lookup_keys_via_location(
665
 
            [(index._size // 2, (b'30', ))])
 
657
        result =index._lookup_keys_via_location(
 
658
            [(index._size // 2, ('30', ))])
666
659
        # check the parse map, this determines the test validity
667
660
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
668
 
        self.assertEqual([((), self.make_key(26)),
 
661
        self.assertEqual([(None, self.make_key(26)),
669
662
                          (self.make_key(31), self.make_key(48))],
670
 
                         index._parsed_key_map)
671
 
        self.assertEqual([((index._size // 2, (b'30', )), -1)],
672
 
                         result)
 
663
            index._parsed_key_map)
 
664
        self.assertEqual([((index._size // 2, ('30', )), -1)],
 
665
            result)
673
666
 
674
667
    def test_lookup_key_above_probed_area(self):
675
668
        # generate a big enough index that we only read some of it on a typical
677
670
        index = self.make_index(nodes=self.make_nodes(64))
678
671
        # ask for the key in the middle, but a key that is located in the
679
672
        # unparsed region after the middle.
680
 
        result = index._lookup_keys_via_location(
681
 
            [(index._size // 2, (b'50', ))])
 
673
        result =index._lookup_keys_via_location(
 
674
            [(index._size // 2, ('50', ))])
682
675
        # check the parse map, this determines the test validity
683
676
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
684
 
        self.assertEqual([((), self.make_key(26)),
 
677
        self.assertEqual([(None, self.make_key(26)),
685
678
                          (self.make_key(31), self.make_key(48))],
686
 
                         index._parsed_key_map)
687
 
        self.assertEqual([((index._size // 2, (b'50', )), +1)],
688
 
                         result)
 
679
            index._parsed_key_map)
 
680
        self.assertEqual([((index._size // 2, ('50', )), +1)],
 
681
            result)
689
682
 
690
683
    def test_lookup_key_resolves_references(self):
691
684
        # generate a big enough index that we only read some of it on a typical
693
686
        nodes = []
694
687
        for counter in range(99):
695
688
            nodes.append((self.make_key(counter), self.make_value(counter),
696
 
                          ((self.make_key(counter + 20),),)))
 
689
                ((self.make_key(counter + 20),),)  ))
697
690
        index = self.make_index(ref_lists=1, nodes=nodes)
698
691
        # lookup a key in the middle that does not exist, so that when we can
699
692
        # check that the referred-to-keys are not accessed automatically.
700
693
        index_size = index._size
701
694
        index_center = index_size // 2
702
695
        result = index._lookup_keys_via_location(
703
 
            [(index_center, (b'40', ))])
 
696
            [(index_center, ('40', ))])
704
697
        # check the parse map - only the start and middle should have been
705
698
        # parsed.
706
699
        self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
707
 
        self.assertEqual([((), self.make_key(17)),
 
700
        self.assertEqual([(None, self.make_key(17)),
708
701
                          (self.make_key(44), self.make_key(5))],
709
 
                         index._parsed_key_map)
 
702
            index._parsed_key_map)
710
703
        # and check the transport activity likewise.
711
704
        self.assertEqual(
712
705
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
713
 
              index_size)],
 
706
                                  index_size)],
714
707
            index._transport._activity)
715
708
        # reset the transport log for testing the reference lookup
716
709
        del index._transport._activity[:]
723
716
               ((self.make_key(65),),)))],
724
717
            result)
725
718
        self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
726
 
                         index._transport._activity)
 
719
            index._transport._activity)
727
720
 
728
721
    def test_lookup_key_can_buffer_all(self):
729
722
        nodes = []
730
723
        for counter in range(64):
731
724
            nodes.append((self.make_key(counter), self.make_value(counter),
732
 
                          ((self.make_key(counter + 20),),)))
 
725
                ((self.make_key(counter + 20),),)  ))
733
726
        index = self.make_index(ref_lists=1, nodes=nodes)
734
727
        # lookup a key in the middle that does not exist, so that when we can
735
728
        # check that the referred-to-keys are not accessed automatically.
736
729
        index_size = index._size
737
730
        index_center = index_size // 2
738
 
        result = index._lookup_keys_via_location([(index_center, (b'40', ))])
 
731
        result = index._lookup_keys_via_location([(index_center, ('40', ))])
739
732
        # check the parse map - only the start and middle should have been
740
733
        # parsed.
741
734
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
742
 
        self.assertEqual([((), self.make_key(25)),
 
735
        self.assertEqual([(None, self.make_key(25)),
743
736
                          (self.make_key(37), self.make_key(52))],
744
 
                         index._parsed_key_map)
 
737
            index._parsed_key_map)
745
738
        # and check the transport activity likewise.
746
739
        self.assertEqual(
747
740
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
748
 
              index_size)],
 
741
                                  index_size)],
749
742
            index._transport._activity)
750
743
        # reset the transport log for testing the reference lookup
751
744
        del index._transport._activity[:]
766
759
        self.assertEqual([], list(index.iter_all_entries()))
767
760
 
768
761
    def test_iter_all_entries_simple(self):
769
 
        index = self.make_index(nodes=[((b'name', ), b'data', ())])
770
 
        self.assertEqual([(index, (b'name', ), b'data')],
771
 
                         list(index.iter_all_entries()))
 
762
        index = self.make_index(nodes=[(('name', ), 'data', ())])
 
763
        self.assertEqual([(index, ('name', ), 'data')],
 
764
            list(index.iter_all_entries()))
772
765
 
773
766
    def test_iter_all_entries_simple_2_elements(self):
774
767
        index = self.make_index(key_elements=2,
775
 
                                nodes=[((b'name', b'surname'), b'data', ())])
776
 
        self.assertEqual([(index, (b'name', b'surname'), b'data')],
777
 
                         list(index.iter_all_entries()))
 
768
            nodes=[(('name', 'surname'), 'data', ())])
 
769
        self.assertEqual([(index, ('name', 'surname'), 'data')],
 
770
            list(index.iter_all_entries()))
778
771
 
779
772
    def test_iter_all_entries_references_resolved(self):
780
773
        index = self.make_index(1, nodes=[
781
 
            ((b'name', ), b'data', ([(b'ref', )], )),
782
 
            ((b'ref', ), b'refdata', ([], ))])
783
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
784
 
                          (index, (b'ref', ), b'refdata', ((), ))},
785
 
                         set(index.iter_all_entries()))
 
774
            (('name', ), 'data', ([('ref', )], )),
 
775
            (('ref', ), 'refdata', ([], ))])
 
776
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
777
            (index, ('ref', ), 'refdata', ((), ))},
 
778
            set(index.iter_all_entries()))
786
779
 
787
780
    def test_iter_entries_buffers_once(self):
788
781
        index = self.make_index(nodes=self.make_nodes(2))
828
821
 
829
822
    def test_iter_entries_references_resolved(self):
830
823
        index = self.make_index(1, nodes=[
831
 
            ((b'name', ), b'data', ([(b'ref', ), (b'ref', )], )),
832
 
            ((b'ref', ), b'refdata', ([], ))])
833
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',), (b'ref',)),)),
834
 
                          (index, (b'ref', ), b'refdata', ((), ))},
835
 
                         set(index.iter_entries([(b'name',), (b'ref',)])))
 
824
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
 
825
            (('ref', ), 'refdata', ([], ))])
 
826
        self.assertEqual({(index, ('name', ), 'data', ((('ref',), ('ref',)),)),
 
827
            (index, ('ref', ), 'refdata', ((), ))},
 
828
            set(index.iter_entries([('name',), ('ref',)])))
836
829
 
837
830
    def test_iter_entries_references_2_refs_resolved(self):
838
831
        index = self.make_index(2, nodes=[
839
 
            ((b'name', ), b'data', ([(b'ref', )], [(b'ref', )])),
840
 
            ((b'ref', ), b'refdata', ([], []))])
841
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),), ((b'ref',),))),
842
 
                          (index, (b'ref', ), b'refdata', ((), ()))},
843
 
                         set(index.iter_entries([(b'name',), (b'ref',)])))
 
832
            (('name', ), 'data', ([('ref', )], [('ref', )])),
 
833
            (('ref', ), 'refdata', ([], []))])
 
834
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
 
835
            (index, ('ref', ), 'refdata', ((), ()))},
 
836
            set(index.iter_entries([('name',), ('ref',)])))
844
837
 
845
838
    def test_iteration_absent_skipped(self):
846
839
        index = self.make_index(1, nodes=[
847
 
            ((b'name', ), b'data', ([(b'ref', )], ))])
848
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
849
 
                         set(index.iter_all_entries()))
850
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
851
 
                         set(index.iter_entries([(b'name', )])))
852
 
        self.assertEqual([], list(index.iter_entries([(b'ref', )])))
 
840
            (('name', ), 'data', ([('ref', )], ))])
 
841
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
 
842
            set(index.iter_all_entries()))
 
843
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
 
844
            set(index.iter_entries([('name', )])))
 
845
        self.assertEqual([], list(index.iter_entries([('ref', )])))
853
846
 
854
847
    def test_iteration_absent_skipped_2_element_keys(self):
855
848
        index = self.make_index(1, key_elements=2, nodes=[
856
 
            ((b'name', b'fin'), b'data', ([(b'ref', b'erence')], ))])
857
 
        self.assertEqual([(index, (b'name', b'fin'), b'data', (((b'ref', b'erence'),),))],
858
 
                         list(index.iter_all_entries()))
859
 
        self.assertEqual([(index, (b'name', b'fin'), b'data', (((b'ref', b'erence'),),))],
860
 
                         list(index.iter_entries([(b'name', b'fin')])))
861
 
        self.assertEqual([], list(index.iter_entries([(b'ref', b'erence')])))
 
849
            (('name', 'fin'), 'data', ([('ref', 'erence')], ))])
 
850
        self.assertEqual({(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))},
 
851
            set(index.iter_all_entries()))
 
852
        self.assertEqual({(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))},
 
853
            set(index.iter_entries([('name', 'fin')])))
 
854
        self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
862
855
 
863
856
    def test_iter_all_keys(self):
864
857
        index = self.make_index(1, nodes=[
865
 
            ((b'name', ), b'data', ([(b'ref', )], )),
866
 
            ((b'ref', ), b'refdata', ([], ))])
867
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
868
 
                          (index, (b'ref', ), b'refdata', ((), ))},
869
 
                         set(index.iter_entries([(b'name', ), (b'ref', )])))
 
858
            (('name', ), 'data', ([('ref', )], )),
 
859
            (('ref', ), 'refdata', ([], ))])
 
860
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
861
            (index, ('ref', ), 'refdata', ((), ))},
 
862
            set(index.iter_entries([('name', ), ('ref', )])))
870
863
 
871
864
    def test_iter_nothing_empty(self):
872
865
        index = self.make_index()
874
867
 
875
868
    def test_iter_missing_entry_empty(self):
876
869
        index = self.make_index()
877
 
        self.assertEqual([], list(index.iter_entries([(b'a', )])))
 
870
        self.assertEqual([], list(index.iter_entries([('a', )])))
878
871
 
879
872
    def test_iter_missing_entry_empty_no_size(self):
880
873
        idx = self.make_index()
881
874
        idx = _mod_index.GraphIndex(idx._transport, 'index', None)
882
 
        self.assertEqual([], list(idx.iter_entries([(b'a', )])))
 
875
        self.assertEqual([], list(idx.iter_entries([('a', )])))
883
876
 
884
877
    def test_iter_key_prefix_1_element_key_None(self):
885
878
        index = self.make_index()
886
879
        self.assertRaises(_mod_index.BadIndexKey, list,
887
 
                          index.iter_entries_prefix([(None, )]))
 
880
            index.iter_entries_prefix([(None, )]))
888
881
 
889
882
    def test_iter_key_prefix_wrong_length(self):
890
883
        index = self.make_index()
891
884
        self.assertRaises(_mod_index.BadIndexKey, list,
892
 
                          index.iter_entries_prefix([(b'foo', None)]))
 
885
            index.iter_entries_prefix([('foo', None)]))
893
886
        index = self.make_index(key_elements=2)
894
887
        self.assertRaises(_mod_index.BadIndexKey, list,
895
 
                          index.iter_entries_prefix([(b'foo', )]))
 
888
            index.iter_entries_prefix([('foo', )]))
896
889
        self.assertRaises(_mod_index.BadIndexKey, list,
897
 
                          index.iter_entries_prefix([(b'foo', None, None)]))
 
890
            index.iter_entries_prefix([('foo', None, None)]))
898
891
 
899
892
    def test_iter_key_prefix_1_key_element_no_refs(self):
900
 
        index = self.make_index(nodes=[
901
 
            ((b'name', ), b'data', ()),
902
 
            ((b'ref', ), b'refdata', ())])
903
 
        self.assertEqual({(index, (b'name', ), b'data'),
904
 
                          (index, (b'ref', ), b'refdata')},
905
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
893
        index = self.make_index( nodes=[
 
894
            (('name', ), 'data', ()),
 
895
            (('ref', ), 'refdata', ())])
 
896
        self.assertEqual({(index, ('name', ), 'data'),
 
897
            (index, ('ref', ), 'refdata')},
 
898
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
906
899
 
907
900
    def test_iter_key_prefix_1_key_element_refs(self):
908
901
        index = self.make_index(1, nodes=[
909
 
            ((b'name', ), b'data', ([(b'ref', )], )),
910
 
            ((b'ref', ), b'refdata', ([], ))])
911
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
912
 
                          (index, (b'ref', ), b'refdata', ((), ))},
913
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
902
            (('name', ), 'data', ([('ref', )], )),
 
903
            (('ref', ), 'refdata', ([], ))])
 
904
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
905
            (index, ('ref', ), 'refdata', ((), ))},
 
906
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
914
907
 
915
908
    def test_iter_key_prefix_2_key_element_no_refs(self):
916
909
        index = self.make_index(key_elements=2, nodes=[
917
 
            ((b'name', b'fin1'), b'data', ()),
918
 
            ((b'name', b'fin2'), b'beta', ()),
919
 
            ((b'ref', b'erence'), b'refdata', ())])
920
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
921
 
                          (index, (b'ref', b'erence'), b'refdata')},
922
 
                         set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
923
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
924
 
                          (index, (b'name', b'fin2'), b'beta')},
925
 
                         set(index.iter_entries_prefix([(b'name', None)])))
 
910
            (('name', 'fin1'), 'data', ()),
 
911
            (('name', 'fin2'), 'beta', ()),
 
912
            (('ref', 'erence'), 'refdata', ())])
 
913
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
914
            (index, ('ref', 'erence'), 'refdata')},
 
915
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
916
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
917
            (index, ('name', 'fin2'), 'beta')},
 
918
            set(index.iter_entries_prefix([('name', None)])))
926
919
 
927
920
    def test_iter_key_prefix_2_key_element_refs(self):
928
921
        index = self.make_index(1, key_elements=2, nodes=[
929
 
            ((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
930
 
            ((b'name', b'fin2'), b'beta', ([], )),
931
 
            ((b'ref', b'erence'), b'refdata', ([], ))])
932
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
933
 
                          (index, (b'ref', b'erence'), b'refdata', ((), ))},
934
 
                         set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
935
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
936
 
                          (index, (b'name', b'fin2'), b'beta', ((), ))},
937
 
                         set(index.iter_entries_prefix([(b'name', None)])))
 
922
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
 
923
            (('name', 'fin2'), 'beta', ([], )),
 
924
            (('ref', 'erence'), 'refdata', ([], ))])
 
925
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
926
            (index, ('ref', 'erence'), 'refdata', ((), ))},
 
927
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
928
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
929
            (index, ('name', 'fin2'), 'beta', ((), ))},
 
930
            set(index.iter_entries_prefix([('name', None)])))
938
931
 
939
932
    def test_key_count_empty(self):
940
933
        index = self.make_index()
941
934
        self.assertEqual(0, index.key_count())
942
935
 
943
936
    def test_key_count_one(self):
944
 
        index = self.make_index(nodes=[((b'name', ), b'', ())])
 
937
        index = self.make_index(nodes=[(('name', ), '', ())])
945
938
        self.assertEqual(1, index.key_count())
946
939
 
947
940
    def test_key_count_two(self):
948
941
        index = self.make_index(nodes=[
949
 
            ((b'name', ), b'', ()), ((b'foo', ), b'', ())])
 
942
            (('name', ), '', ()), (('foo', ), '', ())])
950
943
        self.assertEqual(2, index.key_count())
951
944
 
952
945
    def test_read_and_parse_tracks_real_read_value(self):
964
957
 
965
958
    def test_read_and_parse_triggers_buffer_all(self):
966
959
        index = self.make_index(key_elements=2, nodes=[
967
 
            ((b'name', b'fin1'), b'data', ()),
968
 
            ((b'name', b'fin2'), b'beta', ()),
969
 
            ((b'ref', b'erence'), b'refdata', ())])
 
960
            (('name', 'fin1'), 'data', ()),
 
961
            (('name', 'fin2'), 'beta', ()),
 
962
            (('ref', 'erence'), 'refdata', ())])
970
963
        self.assertTrue(index._size > 0)
971
964
        self.assertIs(None, index._nodes)
972
965
        index._read_and_parse([(0, index._size)])
974
967
 
975
968
    def test_validate_bad_index_errors(self):
976
969
        trans = self.get_transport()
977
 
        trans.put_bytes('name', b"not an index\n")
 
970
        trans.put_bytes('name', "not an index\n")
978
971
        idx = _mod_index.GraphIndex(trans, 'name', 13)
979
972
        self.assertRaises(_mod_index.BadIndexFormatSignature, idx.validate)
980
973
 
983
976
        trans = self.get_transport()
984
977
        content = trans.get_bytes('index')
985
978
        # change the options line to end with a rather than a parseable number
986
 
        new_content = content[:-2] + b'a\n\n'
 
979
        new_content = content[:-2] + 'a\n\n'
987
980
        trans.put_bytes('index', new_content)
988
981
        self.assertRaises(_mod_index.BadIndexOptions, idx.validate)
989
982
 
996
989
        self.assertRaises(_mod_index.BadIndexData, index.validate)
997
990
 
998
991
    def test_validate_missing_end_line_nonempty(self):
999
 
        index = self.make_index(2, nodes=[((b'key', ), b'', ([], []))])
 
992
        index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
1000
993
        trans = self.get_transport()
1001
994
        content = trans.get_bytes('index')
1002
995
        # truncate the last byte
1008
1001
        index.validate()
1009
1002
 
1010
1003
    def test_validate_no_refs_content(self):
1011
 
        index = self.make_index(nodes=[((b'key', ), b'value', ())])
 
1004
        index = self.make_index(nodes=[(('key', ), 'value', ())])
1012
1005
        index.validate()
1013
1006
 
1014
1007
    # XXX: external_references tests are duplicated in test_btree_index.  We
1019
1012
 
1020
1013
    def test_external_references_no_results(self):
1021
1014
        index = self.make_index(ref_lists=1, nodes=[
1022
 
            ((b'key',), b'value', ([],))])
 
1015
            (('key',), 'value', ([],))])
1023
1016
        self.assertEqual(set(), index.external_references(0))
1024
1017
 
1025
1018
    def test_external_references_missing_ref(self):
1026
 
        missing_key = (b'missing',)
 
1019
        missing_key = ('missing',)
1027
1020
        index = self.make_index(ref_lists=1, nodes=[
1028
 
            ((b'key',), b'value', ([missing_key],))])
 
1021
            (('key',), 'value', ([missing_key],))])
1029
1022
        self.assertEqual({missing_key}, index.external_references(0))
1030
1023
 
1031
1024
    def test_external_references_multiple_ref_lists(self):
1032
 
        missing_key = (b'missing',)
 
1025
        missing_key = ('missing',)
1033
1026
        index = self.make_index(ref_lists=2, nodes=[
1034
 
            ((b'key',), b'value', ([], [missing_key]))])
 
1027
            (('key',), 'value', ([], [missing_key]))])
1035
1028
        self.assertEqual(set([]), index.external_references(0))
1036
1029
        self.assertEqual({missing_key}, index.external_references(1))
1037
1030
 
1038
1031
    def test_external_references_two_records(self):
1039
1032
        index = self.make_index(ref_lists=1, nodes=[
1040
 
            ((b'key-1',), b'value', ([(b'key-2',)],)),
1041
 
            ((b'key-2',), b'value', ([],)),
 
1033
            (('key-1',), 'value', ([('key-2',)],)),
 
1034
            (('key-2',), 'value', ([],)),
1042
1035
            ])
1043
1036
        self.assertEqual(set([]), index.external_references(0))
1044
1037
 
1045
1038
    def test__find_ancestors(self):
1046
 
        key1 = (b'key-1',)
1047
 
        key2 = (b'key-2',)
 
1039
        key1 = ('key-1',)
 
1040
        key2 = ('key-2',)
1048
1041
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1049
 
            (key1, b'value', ([key2],)),
1050
 
            (key2, b'value', ([],)),
 
1042
            (key1, 'value', ([key2],)),
 
1043
            (key2, 'value', ([],)),
1051
1044
            ])
1052
1045
        parent_map = {}
1053
1046
        missing_keys = set()
1054
 
        search_keys = index._find_ancestors(
1055
 
            [key1], 0, parent_map, missing_keys)
 
1047
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1056
1048
        self.assertEqual({key1: (key2,)}, parent_map)
1057
1049
        self.assertEqual(set(), missing_keys)
1058
1050
        self.assertEqual({key2}, search_keys)
1063
1055
        self.assertEqual(set(), search_keys)
1064
1056
 
1065
1057
    def test__find_ancestors_w_missing(self):
1066
 
        key1 = (b'key-1',)
1067
 
        key2 = (b'key-2',)
1068
 
        key3 = (b'key-3',)
 
1058
        key1 = ('key-1',)
 
1059
        key2 = ('key-2',)
 
1060
        key3 = ('key-3',)
1069
1061
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1070
 
            (key1, b'value', ([key2],)),
1071
 
            (key2, b'value', ([],)),
 
1062
            (key1, 'value', ([key2],)),
 
1063
            (key2, 'value', ([],)),
1072
1064
            ])
1073
1065
        parent_map = {}
1074
1066
        missing_keys = set()
1079
1071
        self.assertEqual(set(), search_keys)
1080
1072
 
1081
1073
    def test__find_ancestors_dont_search_known(self):
1082
 
        key1 = (b'key-1',)
1083
 
        key2 = (b'key-2',)
1084
 
        key3 = (b'key-3',)
 
1074
        key1 = ('key-1',)
 
1075
        key2 = ('key-2',)
 
1076
        key3 = ('key-3',)
1085
1077
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1086
 
            (key1, b'value', ([key2],)),
1087
 
            (key2, b'value', ([key3],)),
1088
 
            (key3, b'value', ([],)),
 
1078
            (key1, 'value', ([key2],)),
 
1079
            (key2, 'value', ([key3],)),
 
1080
            (key3, 'value', ([],)),
1089
1081
            ])
1090
1082
        # We already know about key2, so we won't try to search for key3
1091
1083
        parent_map = {key2: (key3,)}
1109
1101
class TestCombinedGraphIndex(tests.TestCaseWithMemoryTransport):
1110
1102
 
1111
1103
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1112
 
        builder = _mod_index.GraphIndexBuilder(
1113
 
            ref_lists, key_elements=key_elements)
 
1104
        builder = _mod_index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
1114
1105
        for key, value, references in nodes:
1115
1106
            builder.add_node(key, value, references)
1116
1107
        stream = builder.finish()
1128
1119
        :param missing: The underlying indexes to delete
1129
1120
        :return: (CombinedGraphIndex, reload_counter)
1130
1121
        """
1131
 
        idx1 = self.make_index('1', nodes=[((b'1',), b'', ())])
1132
 
        idx2 = self.make_index('2', nodes=[((b'2',), b'', ())])
 
1122
        idx1 = self.make_index('1', nodes=[(('1',), '', ())])
 
1123
        idx2 = self.make_index('2', nodes=[(('2',), '', ())])
1133
1124
        idx3 = self.make_index('3', nodes=[
1134
 
            ((b'1',), b'', ()),
1135
 
            ((b'2',), b'', ())])
 
1125
            (('1',), '', ()),
 
1126
            (('2',), '', ())])
1136
1127
 
1137
1128
        # total_reloads, num_changed, num_unchanged
1138
1129
        reload_counter = [0, 0, 0]
1139
 
 
1140
1130
        def reload():
1141
1131
            reload_counter[0] += 1
1142
1132
            new_indices = [idx3]
1159
1149
 
1160
1150
    def test_add_index(self):
1161
1151
        idx = _mod_index.CombinedGraphIndex([])
1162
 
        idx1 = self.make_index('name', 0, nodes=[((b'key', ), b'', ())])
 
1152
        idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1163
1153
        idx.insert_index(0, idx1)
1164
 
        self.assertEqual([(idx1, (b'key', ), b'')],
 
1154
        self.assertEqual([(idx1, ('key', ), '')],
1165
1155
                         list(idx.iter_all_entries()))
1166
1156
 
1167
1157
    def test_clear_cache(self):
1180
1170
                return self._index.clear_cache()
1181
1171
 
1182
1172
        idx = _mod_index.CombinedGraphIndex([])
1183
 
        idx1 = self.make_index('name', 0, nodes=[((b'key', ), b'', ())])
 
1173
        idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1184
1174
        idx.insert_index(0, ClearCacheProxy(idx1))
1185
 
        idx2 = self.make_index('name', 0, nodes=[((b'key', ), b'', ())])
 
1175
        idx2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1186
1176
        idx.insert_index(1, ClearCacheProxy(idx2))
1187
1177
        # CombinedGraphIndex should call 'clear_cache()' on all children
1188
1178
        idx.clear_cache()
1198
1188
        self.assertEqual([], list(idx.iter_all_entries()))
1199
1189
 
1200
1190
    def test_iter_all_entries_simple(self):
1201
 
        idx1 = self.make_index('name', nodes=[((b'name', ), b'data', ())])
 
1191
        idx1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
1202
1192
        idx = _mod_index.CombinedGraphIndex([idx1])
1203
 
        self.assertEqual([(idx1, (b'name', ), b'data')],
1204
 
                         list(idx.iter_all_entries()))
 
1193
        self.assertEqual([(idx1, ('name', ), 'data')],
 
1194
            list(idx.iter_all_entries()))
1205
1195
 
1206
1196
    def test_iter_all_entries_two_indices(self):
1207
 
        idx1 = self.make_index('name1', nodes=[((b'name', ), b'data', ())])
1208
 
        idx2 = self.make_index('name2', nodes=[((b'2', ), b'', ())])
 
1197
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1198
        idx2 = self.make_index('name2', nodes=[(('2', ), '', ())])
1209
1199
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1210
 
        self.assertEqual([(idx1, (b'name', ), b'data'),
1211
 
                          (idx2, (b'2', ), b'')],
 
1200
        self.assertEqual([(idx1, ('name', ), 'data'),
 
1201
                          (idx2, ('2', ), '')],
1212
1202
                         list(idx.iter_all_entries()))
1213
1203
 
1214
1204
    def test_iter_entries_two_indices_dup_key(self):
1215
 
        idx1 = self.make_index('name1', nodes=[((b'name', ), b'data', ())])
1216
 
        idx2 = self.make_index('name2', nodes=[((b'name', ), b'data', ())])
 
1205
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1206
        idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1217
1207
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1218
 
        self.assertEqual([(idx1, (b'name', ), b'data')],
1219
 
                         list(idx.iter_entries([(b'name', )])))
 
1208
        self.assertEqual([(idx1, ('name', ), 'data')],
 
1209
                         list(idx.iter_entries([('name', )])))
1220
1210
 
1221
1211
    def test_iter_all_entries_two_indices_dup_key(self):
1222
 
        idx1 = self.make_index('name1', nodes=[((b'name', ), b'data', ())])
1223
 
        idx2 = self.make_index('name2', nodes=[((b'name', ), b'data', ())])
 
1212
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1213
        idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1224
1214
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1225
 
        self.assertEqual([(idx1, (b'name', ), b'data')],
 
1215
        self.assertEqual([(idx1, ('name', ), 'data')],
1226
1216
                         list(idx.iter_all_entries()))
1227
1217
 
1228
1218
    def test_iter_key_prefix_2_key_element_refs(self):
1229
1219
        idx1 = self.make_index('1', 1, key_elements=2, nodes=[
1230
 
            ((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], ))])
 
1220
                (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
1231
1221
        idx2 = self.make_index('2', 1, key_elements=2, nodes=[
1232
 
            ((b'name', b'fin2'), b'beta', ([], )),
1233
 
            ((b'ref', b'erence'), b'refdata', ([], ))])
 
1222
                (('name', 'fin2'), 'beta', ([], )),
 
1223
                (('ref', 'erence'), 'refdata', ([], ))])
1234
1224
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1235
 
        self.assertEqual({(idx1, (b'name', b'fin1'), b'data',
1236
 
                           (((b'ref', b'erence'),),)),
1237
 
                          (idx2, (b'ref', b'erence'), b'refdata', ((), ))},
1238
 
                         set(idx.iter_entries_prefix([(b'name', b'fin1'),
1239
 
                                                      (b'ref', b'erence')])))
1240
 
        self.assertEqual({(idx1, (b'name', b'fin1'), b'data',
1241
 
                           (((b'ref', b'erence'),),)),
1242
 
                          (idx2, (b'name', b'fin2'), b'beta', ((), ))},
1243
 
                         set(idx.iter_entries_prefix([(b'name', None)])))
 
1225
        self.assertEqual({(idx1, ('name', 'fin1'), 'data',
 
1226
                               ((('ref', 'erence'),),)),
 
1227
                              (idx2, ('ref', 'erence'), 'refdata', ((), ))},
 
1228
                         set(idx.iter_entries_prefix([('name', 'fin1'),
 
1229
                                                        ('ref', 'erence')])))
 
1230
        self.assertEqual({(idx1, ('name', 'fin1'), 'data',
 
1231
                               ((('ref', 'erence'),),)),
 
1232
                              (idx2, ('name', 'fin2'), 'beta', ((), ))},
 
1233
                         set(idx.iter_entries_prefix([('name', None)])))
1244
1234
 
1245
1235
    def test_iter_nothing_empty(self):
1246
1236
        idx = _mod_index.CombinedGraphIndex([])
1252
1242
        self.assertEqual([], list(idx.iter_entries([])))
1253
1243
 
1254
1244
    def test_iter_all_keys(self):
1255
 
        idx1 = self.make_index('1', 1, nodes=[((b'name', ), b'data',
1256
 
                                               ([(b'ref', )], ))])
1257
 
        idx2 = self.make_index(
1258
 
            '2', 1, nodes=[((b'ref', ), b'refdata', ((), ))])
 
1245
        idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
 
1246
                                               ([('ref', )], ))])
 
1247
        idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ((), ))])
1259
1248
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1260
 
        self.assertEqual({(idx1, (b'name', ), b'data', (((b'ref', ), ), )),
1261
 
                          (idx2, (b'ref', ), b'refdata', ((), ))},
1262
 
                         set(idx.iter_entries([(b'name', ), (b'ref', )])))
 
1249
        self.assertEqual({(idx1, ('name', ), 'data', ((('ref', ), ), )),
 
1250
                              (idx2, ('ref', ), 'refdata', ((), ))},
 
1251
                         set(idx.iter_entries([('name', ), ('ref', )])))
1263
1252
 
1264
1253
    def test_iter_all_keys_dup_entry(self):
1265
 
        idx1 = self.make_index('1', 1, nodes=[((b'name', ), b'data',
1266
 
                                               ([(b'ref', )], )),
1267
 
                                              ((b'ref', ), b'refdata', ([], ))])
1268
 
        idx2 = self.make_index(
1269
 
            '2', 1, nodes=[((b'ref', ), b'refdata', ([], ))])
 
1254
        idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
 
1255
                                                 ([('ref', )], )),
 
1256
                                                (('ref', ), 'refdata', ([], ))])
 
1257
        idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ([], ))])
1270
1258
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1271
 
        self.assertEqual({(idx1, (b'name', ), b'data', (((b'ref',),),)),
1272
 
                          (idx1, (b'ref', ), b'refdata', ((), ))},
1273
 
                         set(idx.iter_entries([(b'name', ), (b'ref', )])))
 
1259
        self.assertEqual({(idx1, ('name', ), 'data', ((('ref',),),)),
 
1260
                              (idx1, ('ref', ), 'refdata', ((), ))},
 
1261
                         set(idx.iter_entries([('name', ), ('ref', )])))
1274
1262
 
1275
1263
    def test_iter_missing_entry_empty(self):
1276
1264
        idx = _mod_index.CombinedGraphIndex([])
1279
1267
    def test_iter_missing_entry_one_index(self):
1280
1268
        idx1 = self.make_index('1')
1281
1269
        idx = _mod_index.CombinedGraphIndex([idx1])
1282
 
        self.assertEqual([], list(idx.iter_entries([(b'a', )])))
 
1270
        self.assertEqual([], list(idx.iter_entries([('a', )])))
1283
1271
 
1284
1272
    def test_iter_missing_entry_two_index(self):
1285
1273
        idx1 = self.make_index('1')
1288
1276
        self.assertEqual([], list(idx.iter_entries([('a', )])))
1289
1277
 
1290
1278
    def test_iter_entry_present_one_index_only(self):
1291
 
        idx1 = self.make_index('1', nodes=[((b'key', ), b'', ())])
 
1279
        idx1 = self.make_index('1', nodes=[(('key', ), '', ())])
1292
1280
        idx2 = self.make_index('2', nodes=[])
1293
1281
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1294
 
        self.assertEqual([(idx1, (b'key', ), b'')],
1295
 
                         list(idx.iter_entries([(b'key', )])))
 
1282
        self.assertEqual([(idx1, ('key', ), '')],
 
1283
                         list(idx.iter_entries([('key', )])))
1296
1284
        # and in the other direction
1297
1285
        idx = _mod_index.CombinedGraphIndex([idx2, idx1])
1298
 
        self.assertEqual([(idx1, (b'key', ), b'')],
1299
 
                         list(idx.iter_entries([(b'key', )])))
 
1286
        self.assertEqual([(idx1, ('key', ), '')],
 
1287
                         list(idx.iter_entries([('key', )])))
1300
1288
 
1301
1289
    def test_key_count_empty(self):
1302
1290
        idx1 = self.make_index('1', nodes=[])
1306
1294
 
1307
1295
    def test_key_count_sums_index_keys(self):
1308
1296
        idx1 = self.make_index('1', nodes=[
1309
 
            ((b'1',), b'', ()),
1310
 
            ((b'2',), b'', ())])
1311
 
        idx2 = self.make_index('2', nodes=[((b'1',), b'', ())])
 
1297
            (('1',), '', ()),
 
1298
            (('2',), '', ())])
 
1299
        idx2 = self.make_index('2', nodes=[(('1',), '', ())])
1312
1300
        idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1313
1301
        self.assertEqual(3, idx.key_count())
1314
1302
 
1315
1303
    def test_validate_bad_child_index_errors(self):
1316
1304
        trans = self.get_transport()
1317
 
        trans.put_bytes('name', b"not an index\n")
 
1305
        trans.put_bytes('name', "not an index\n")
1318
1306
        idx1 = _mod_index.GraphIndex(trans, 'name', 13)
1319
1307
        idx = _mod_index.CombinedGraphIndex([idx1])
1320
1308
        self.assertRaises(_mod_index.BadIndexFormatSignature, idx.validate)
1345
1333
 
1346
1334
    def test_iter_entries_reloads(self):
1347
1335
        index, reload_counter = self.make_combined_index_with_missing()
1348
 
        result = list(index.iter_entries([(b'1',), (b'2',), (b'3',)]))
 
1336
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1349
1337
        index3 = index._indices[0]
1350
 
        self.assertEqual({(index3, (b'1',), b''), (index3, (b'2',), b'')},
1351
 
                         set(result))
 
1338
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
 
1339
                         result)
1352
1340
        self.assertEqual([1, 1, 0], reload_counter)
1353
1341
 
1354
1342
    def test_iter_entries_reloads_midway(self):
1356
1344
        # through
1357
1345
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1358
1346
        index1, index2 = index._indices
1359
 
        result = list(index.iter_entries([(b'1',), (b'2',), (b'3',)]))
 
1347
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1360
1348
        index3 = index._indices[0]
1361
 
        # We had already yielded b'1', so we just go on to the next, we should
1362
 
        # not yield b'1' twice.
1363
 
        self.assertEqual([(index1, (b'1',), b''), (index3, (b'2',), b'')],
 
1349
        # We had already yielded '1', so we just go on to the next, we should
 
1350
        # not yield '1' twice.
 
1351
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1364
1352
                         result)
1365
1353
        self.assertEqual([1, 1, 0], reload_counter)
1366
1354
 
1372
1360
 
1373
1361
    def test_iter_entries_reloads_and_fails(self):
1374
1362
        index, reload_counter = self.make_combined_index_with_missing(
1375
 
            ['1', '2', '3'])
 
1363
                                    ['1', '2', '3'])
1376
1364
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1377
1365
        self.assertEqual([2, 1, 1], reload_counter)
1378
1366
 
1380
1368
        index, reload_counter = self.make_combined_index_with_missing()
1381
1369
        result = list(index.iter_all_entries())
1382
1370
        index3 = index._indices[0]
1383
 
        self.assertEqual({(index3, (b'1',), b''), (index3, (b'2',), b'')},
1384
 
                         set(result))
 
1371
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
 
1372
                         result)
1385
1373
        self.assertEqual([1, 1, 0], reload_counter)
1386
1374
 
1387
1375
    def test_iter_all_entries_reloads_midway(self):
1391
1379
        index3 = index._indices[0]
1392
1380
        # We had already yielded '1', so we just go on to the next, we should
1393
1381
        # not yield '1' twice.
1394
 
        self.assertEqual([(index1, (b'1',), b''), (index3, (b'2',), b'')],
 
1382
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1395
1383
                         result)
1396
1384
        self.assertEqual([1, 1, 0], reload_counter)
1397
1385
 
1402
1390
 
1403
1391
    def test_iter_all_entries_reloads_and_fails(self):
1404
1392
        index, reload_counter = self.make_combined_index_with_missing(
1405
 
            ['1', '2', '3'])
 
1393
                                    ['1', '2', '3'])
1406
1394
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1407
1395
 
1408
1396
    def test_iter_entries_prefix_reloads(self):
1409
1397
        index, reload_counter = self.make_combined_index_with_missing()
1410
 
        result = list(index.iter_entries_prefix([(b'1',)]))
 
1398
        result = list(index.iter_entries_prefix([('1',)]))
1411
1399
        index3 = index._indices[0]
1412
 
        self.assertEqual([(index3, (b'1',), b'')], result)
 
1400
        self.assertEqual([(index3, ('1',), '')], result)
1413
1401
        self.assertEqual([1, 1, 0], reload_counter)
1414
1402
 
1415
1403
    def test_iter_entries_prefix_reloads_midway(self):
1416
1404
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1417
1405
        index1, index2 = index._indices
1418
 
        result = list(index.iter_entries_prefix([(b'1',)]))
 
1406
        result = list(index.iter_entries_prefix([('1',)]))
1419
1407
        index3 = index._indices[0]
1420
 
        # We had already yielded b'1', so we just go on to the next, we should
1421
 
        # not yield b'1' twice.
1422
 
        self.assertEqual([(index1, (b'1',), b'')], result)
 
1408
        # We had already yielded '1', so we just go on to the next, we should
 
1409
        # not yield '1' twice.
 
1410
        self.assertEqual([(index1, ('1',), '')], result)
1423
1411
        self.assertEqual([1, 1, 0], reload_counter)
1424
1412
 
1425
1413
    def test_iter_entries_prefix_no_reload(self):
1426
1414
        index, reload_counter = self.make_combined_index_with_missing()
1427
1415
        index._reload_func = None
1428
1416
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1429
 
                              [(b'1',)])
 
1417
                                                 [('1',)])
1430
1418
 
1431
1419
    def test_iter_entries_prefix_reloads_and_fails(self):
1432
1420
        index, reload_counter = self.make_combined_index_with_missing(
1433
 
            ['1', '2', '3'])
 
1421
                                    ['1', '2', '3'])
1434
1422
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1435
 
                              [(b'1',)])
 
1423
                                                 [('1',)])
 
1424
 
1436
1425
 
1437
1426
    def make_index_with_simple_nodes(self, name, num_nodes=1):
1438
1427
        """Make an index named after 'name', with keys named after 'name' too.
1440
1429
        Nodes will have a value of '' and no references.
1441
1430
        """
1442
1431
        nodes = [
1443
 
            ((('index-%s-key-%s' % (name, n)).encode('ascii'),), b'', ())
1444
 
            for n in range(1, num_nodes + 1)]
 
1432
            (('index-%s-key-%s' % (name, n),), '', ())
 
1433
            for n in range(1, num_nodes+1)]
1445
1434
        return self.make_index('index-%s' % name, 0, nodes=nodes)
1446
1435
 
1447
1436
    def test_reorder_after_iter_entries(self):
1448
1437
        # Four indices: [key1] in idx1, [key2,key3] in idx2, [] in idx3,
1449
1438
        # [key4] in idx4.
1450
1439
        idx = _mod_index.CombinedGraphIndex([])
1451
 
        idx.insert_index(0, self.make_index_with_simple_nodes('1'), b'1')
1452
 
        idx.insert_index(1, self.make_index_with_simple_nodes('2'), b'2')
1453
 
        idx.insert_index(2, self.make_index_with_simple_nodes('3'), b'3')
1454
 
        idx.insert_index(3, self.make_index_with_simple_nodes('4'), b'4')
 
1440
        idx.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
 
1441
        idx.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
 
1442
        idx.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
 
1443
        idx.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
1455
1444
        idx1, idx2, idx3, idx4 = idx._indices
1456
1445
        # Query a key from idx4 and idx2.
1457
1446
        self.assertLength(2, list(idx.iter_entries(
1458
 
            [(b'index-4-key-1',), (b'index-2-key-1',)])))
 
1447
            [('index-4-key-1',), ('index-2-key-1',)])))
1459
1448
        # Now idx2 and idx4 should be moved to the front (and idx1 should
1460
1449
        # still be before idx3).
1461
1450
        self.assertEqual([idx2, idx4, idx1, idx3], idx._indices)
1462
 
        self.assertEqual([b'2', b'4', b'1', b'3'], idx._index_names)
 
1451
        self.assertEqual(['2', '4', '1', '3'], idx._index_names)
1463
1452
 
1464
1453
    def test_reorder_propagates_to_siblings(self):
1465
1454
        # Two CombinedGraphIndex objects, with the same number of indicies with
1473
1462
        index2_1, index2_2 = cgi2._indices
1474
1463
        cgi1.set_sibling_indices([cgi2])
1475
1464
        # Trigger a reordering in cgi1.  cgi2 will be reordered as well.
1476
 
        list(cgi1.iter_entries([(b'index-1-2-key-1',)]))
 
1465
        list(cgi1.iter_entries([('index-1-2-key-1',)]))
1477
1466
        self.assertEqual([index2_2, index2_1], cgi2._indices)
1478
1467
        self.assertEqual(['two', 'one'], cgi2._index_names)
1479
1468
 
1497
1486
        self.assertRaises(errors.NoSuchFile, idx.validate)
1498
1487
 
1499
1488
    def test_find_ancestors_across_indexes(self):
1500
 
        key1 = (b'key-1',)
1501
 
        key2 = (b'key-2',)
1502
 
        key3 = (b'key-3',)
1503
 
        key4 = (b'key-4',)
 
1489
        key1 = ('key-1',)
 
1490
        key2 = ('key-2',)
 
1491
        key3 = ('key-3',)
 
1492
        key4 = ('key-4',)
1504
1493
        index1 = self.make_index('12', ref_lists=1, nodes=[
1505
 
            (key1, b'value', ([],)),
1506
 
            (key2, b'value', ([key1],)),
 
1494
            (key1, 'value', ([],)),
 
1495
            (key2, 'value', ([key1],)),
1507
1496
            ])
1508
1497
        index2 = self.make_index('34', ref_lists=1, nodes=[
1509
 
            (key3, b'value', ([key2],)),
1510
 
            (key4, b'value', ([key3],)),
 
1498
            (key3, 'value', ([key2],)),
 
1499
            (key4, 'value', ([key3],)),
1511
1500
            ])
1512
1501
        c_index = _mod_index.CombinedGraphIndex([index1, index2])
1513
1502
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1521
1510
        self.assertEqual(set(), missing_keys)
1522
1511
 
1523
1512
    def test_find_ancestors_missing_keys(self):
1524
 
        key1 = (b'key-1',)
1525
 
        key2 = (b'key-2',)
1526
 
        key3 = (b'key-3',)
1527
 
        key4 = (b'key-4',)
 
1513
        key1 = ('key-1',)
 
1514
        key2 = ('key-2',)
 
1515
        key3 = ('key-3',)
 
1516
        key4 = ('key-4',)
1528
1517
        index1 = self.make_index('12', ref_lists=1, nodes=[
1529
 
            (key1, b'value', ([],)),
1530
 
            (key2, b'value', ([key1],)),
 
1518
            (key1, 'value', ([],)),
 
1519
            (key2, 'value', ([key1],)),
1531
1520
            ])
1532
1521
        index2 = self.make_index('34', ref_lists=1, nodes=[
1533
 
            (key3, b'value', ([key2],)),
 
1522
            (key3, 'value', ([key2],)),
1534
1523
            ])
1535
1524
        c_index = _mod_index.CombinedGraphIndex([index1, index2])
1536
1525
        # Searching for a key which is actually not present at all should
1541
1530
 
1542
1531
    def test_find_ancestors_no_indexes(self):
1543
1532
        c_index = _mod_index.CombinedGraphIndex([])
1544
 
        key1 = (b'key-1',)
 
1533
        key1 = ('key-1',)
1545
1534
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1546
1535
        self.assertEqual({}, parent_map)
1547
1536
        self.assertEqual({key1}, missing_keys)
1548
1537
 
1549
1538
    def test_find_ancestors_ghost_parent(self):
1550
 
        key1 = (b'key-1',)
1551
 
        key2 = (b'key-2',)
1552
 
        key3 = (b'key-3',)
1553
 
        key4 = (b'key-4',)
 
1539
        key1 = ('key-1',)
 
1540
        key2 = ('key-2',)
 
1541
        key3 = ('key-3',)
 
1542
        key4 = ('key-4',)
1554
1543
        index1 = self.make_index('12', ref_lists=1, nodes=[
1555
 
            (key1, b'value', ([],)),
1556
 
            (key2, b'value', ([key1],)),
 
1544
            (key1, 'value', ([],)),
 
1545
            (key2, 'value', ([key1],)),
1557
1546
            ])
1558
1547
        index2 = self.make_index('34', ref_lists=1, nodes=[
1559
 
            (key4, b'value', ([key2, key3],)),
 
1548
            (key4, 'value', ([key2, key3],)),
1560
1549
            ])
1561
1550
        c_index = _mod_index.CombinedGraphIndex([index1, index2])
1562
1551
        # Searching for a key which is actually not present at all should
1570
1559
        idx = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1571
1560
        parent_map = {}
1572
1561
        missing_keys = set()
1573
 
        search_keys = idx._find_ancestors([(b'one',), (b'two',)], 0, parent_map,
 
1562
        search_keys = idx._find_ancestors([('one',), ('two',)], 0, parent_map,
1574
1563
                                          missing_keys)
1575
1564
        self.assertEqual(set(), search_keys)
1576
1565
        self.assertEqual({}, parent_map)
1577
 
        self.assertEqual({(b'one',), (b'two',)}, missing_keys)
 
1566
        self.assertEqual({('one',), ('two',)}, missing_keys)
1578
1567
 
1579
1568
 
1580
1569
class TestInMemoryGraphIndex(tests.TestCaseWithMemoryTransport):
1581
1570
 
1582
1571
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1583
 
        result = _mod_index.InMemoryGraphIndex(
1584
 
            ref_lists, key_elements=key_elements)
 
1572
        result = _mod_index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1585
1573
        result.add_nodes(nodes)
1586
1574
        return result
1587
1575
 
1588
1576
    def test_add_nodes_no_refs(self):
1589
1577
        index = self.make_index(0)
1590
 
        index.add_nodes([((b'name', ), b'data')])
1591
 
        index.add_nodes([((b'name2', ), b''), ((b'name3', ), b'')])
 
1578
        index.add_nodes([(('name', ), 'data')])
 
1579
        index.add_nodes([(('name2', ), ''), (('name3', ), '')])
1592
1580
        self.assertEqual({
1593
 
            (index, (b'name', ), b'data'),
1594
 
            (index, (b'name2', ), b''),
1595
 
            (index, (b'name3', ), b''),
 
1581
            (index, ('name', ), 'data'),
 
1582
            (index, ('name2', ), ''),
 
1583
            (index, ('name3', ), ''),
1596
1584
            }, set(index.iter_all_entries()))
1597
1585
 
1598
1586
    def test_add_nodes(self):
1599
1587
        index = self.make_index(1)
1600
 
        index.add_nodes([((b'name', ), b'data', ([],))])
1601
 
        index.add_nodes([((b'name2', ), b'', ([],)),
1602
 
                         ((b'name3', ), b'', ([(b'r', )],))])
 
1588
        index.add_nodes([(('name', ), 'data', ([],))])
 
1589
        index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
1603
1590
        self.assertEqual({
1604
 
            (index, (b'name', ), b'data', ((),)),
1605
 
            (index, (b'name2', ), b'', ((),)),
1606
 
            (index, (b'name3', ), b'', (((b'r', ), ), )),
 
1591
            (index, ('name', ), 'data', ((),)),
 
1592
            (index, ('name2', ), '', ((),)),
 
1593
            (index, ('name3', ), '', ((('r', ), ), )),
1607
1594
            }, set(index.iter_all_entries()))
1608
1595
 
1609
1596
    def test_iter_all_entries_empty(self):
1611
1598
        self.assertEqual([], list(index.iter_all_entries()))
1612
1599
 
1613
1600
    def test_iter_all_entries_simple(self):
1614
 
        index = self.make_index(nodes=[((b'name', ), b'data')])
1615
 
        self.assertEqual([(index, (b'name', ), b'data')],
1616
 
                         list(index.iter_all_entries()))
 
1601
        index = self.make_index(nodes=[(('name', ), 'data')])
 
1602
        self.assertEqual([(index, ('name', ), 'data')],
 
1603
            list(index.iter_all_entries()))
1617
1604
 
1618
1605
    def test_iter_all_entries_references(self):
1619
1606
        index = self.make_index(1, nodes=[
1620
 
            ((b'name', ), b'data', ([(b'ref', )], )),
1621
 
            ((b'ref', ), b'refdata', ([], ))])
1622
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref', ),),)),
1623
 
                          (index, (b'ref', ), b'refdata', ((), ))},
1624
 
                         set(index.iter_all_entries()))
 
1607
            (('name', ), 'data', ([('ref', )], )),
 
1608
            (('ref', ), 'refdata', ([], ))])
 
1609
        self.assertEqual({(index, ('name', ), 'data', ((('ref', ),),)),
 
1610
            (index, ('ref', ), 'refdata', ((), ))},
 
1611
            set(index.iter_all_entries()))
1625
1612
 
1626
1613
    def test_iteration_absent_skipped(self):
1627
1614
        index = self.make_index(1, nodes=[
1628
 
            ((b'name', ), b'data', ([(b'ref', )], ))])
1629
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
1630
 
                         set(index.iter_all_entries()))
1631
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
1632
 
                         set(index.iter_entries([(b'name', )])))
1633
 
        self.assertEqual([], list(index.iter_entries([(b'ref', )])))
 
1615
            (('name', ), 'data', ([('ref', )], ))])
 
1616
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
 
1617
            set(index.iter_all_entries()))
 
1618
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
 
1619
            set(index.iter_entries([('name', )])))
 
1620
        self.assertEqual([], list(index.iter_entries([('ref', )])))
1634
1621
 
1635
1622
    def test_iter_all_keys(self):
1636
1623
        index = self.make_index(1, nodes=[
1637
 
            ((b'name', ), b'data', ([(b'ref', )], )),
1638
 
            ((b'ref', ), b'refdata', ([], ))])
1639
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
1640
 
                          (index, (b'ref', ), b'refdata', ((), ))},
1641
 
                         set(index.iter_entries([(b'name', ), (b'ref', )])))
 
1624
            (('name', ), 'data', ([('ref', )], )),
 
1625
            (('ref', ), 'refdata', ([], ))])
 
1626
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
1627
            (index, ('ref', ), 'refdata', ((), ))},
 
1628
            set(index.iter_entries([('name', ), ('ref', )])))
1642
1629
 
1643
1630
    def test_iter_key_prefix_1_key_element_no_refs(self):
1644
 
        index = self.make_index(nodes=[
1645
 
            ((b'name', ), b'data'),
1646
 
            ((b'ref', ), b'refdata')])
1647
 
        self.assertEqual({(index, (b'name', ), b'data'),
1648
 
                          (index, (b'ref', ), b'refdata')},
1649
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
1631
        index = self.make_index( nodes=[
 
1632
            (('name', ), 'data'),
 
1633
            (('ref', ), 'refdata')])
 
1634
        self.assertEqual({(index, ('name', ), 'data'),
 
1635
            (index, ('ref', ), 'refdata')},
 
1636
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
1650
1637
 
1651
1638
    def test_iter_key_prefix_1_key_element_refs(self):
1652
1639
        index = self.make_index(1, nodes=[
1653
 
            ((b'name', ), b'data', ([(b'ref', )], )),
1654
 
            ((b'ref', ), b'refdata', ([], ))])
1655
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
1656
 
                          (index, (b'ref', ), b'refdata', ((), ))},
1657
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
1640
            (('name', ), 'data', ([('ref', )], )),
 
1641
            (('ref', ), 'refdata', ([], ))])
 
1642
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
1643
            (index, ('ref', ), 'refdata', ((), ))},
 
1644
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
1658
1645
 
1659
1646
    def test_iter_key_prefix_2_key_element_no_refs(self):
1660
1647
        index = self.make_index(key_elements=2, nodes=[
1661
 
            ((b'name', b'fin1'), b'data'),
1662
 
            ((b'name', b'fin2'), b'beta'),
1663
 
            ((b'ref', b'erence'), b'refdata')])
1664
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
1665
 
                          (index, (b'ref', b'erence'), b'refdata')},
1666
 
                         set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
1667
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
1668
 
                          (index, (b'name', b'fin2'), b'beta')},
1669
 
                         set(index.iter_entries_prefix([(b'name', None)])))
 
1648
            (('name', 'fin1'), 'data'),
 
1649
            (('name', 'fin2'), 'beta'),
 
1650
            (('ref', 'erence'), 'refdata')])
 
1651
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
1652
            (index, ('ref', 'erence'), 'refdata')},
 
1653
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
1654
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
1655
            (index, ('name', 'fin2'), 'beta')},
 
1656
            set(index.iter_entries_prefix([('name', None)])))
1670
1657
 
1671
1658
    def test_iter_key_prefix_2_key_element_refs(self):
1672
1659
        index = self.make_index(1, key_elements=2, nodes=[
1673
 
            ((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
1674
 
            ((b'name', b'fin2'), b'beta', ([], )),
1675
 
            ((b'ref', b'erence'), b'refdata', ([], ))])
1676
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
1677
 
                          (index, (b'ref', b'erence'), b'refdata', ((), ))},
1678
 
                         set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
1679
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
1680
 
                          (index, (b'name', b'fin2'), b'beta', ((), ))},
1681
 
                         set(index.iter_entries_prefix([(b'name', None)])))
 
1660
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
 
1661
            (('name', 'fin2'), 'beta', ([], )),
 
1662
            (('ref', 'erence'), 'refdata', ([], ))])
 
1663
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1664
            (index, ('ref', 'erence'), 'refdata', ((), ))},
 
1665
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
1666
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1667
            (index, ('name', 'fin2'), 'beta', ((), ))},
 
1668
            set(index.iter_entries_prefix([('name', None)])))
1682
1669
 
1683
1670
    def test_iter_nothing_empty(self):
1684
1671
        index = self.make_index()
1686
1673
 
1687
1674
    def test_iter_missing_entry_empty(self):
1688
1675
        index = self.make_index()
1689
 
        self.assertEqual([], list(index.iter_entries([b'a'])))
 
1676
        self.assertEqual([], list(index.iter_entries(['a'])))
1690
1677
 
1691
1678
    def test_key_count_empty(self):
1692
1679
        index = self.make_index()
1693
1680
        self.assertEqual(0, index.key_count())
1694
1681
 
1695
1682
    def test_key_count_one(self):
1696
 
        index = self.make_index(nodes=[((b'name', ), b'')])
 
1683
        index = self.make_index(nodes=[(('name', ), '')])
1697
1684
        self.assertEqual(1, index.key_count())
1698
1685
 
1699
1686
    def test_key_count_two(self):
1700
 
        index = self.make_index(nodes=[((b'name', ), b''), ((b'foo', ), b'')])
 
1687
        index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
1701
1688
        self.assertEqual(2, index.key_count())
1702
1689
 
1703
1690
    def test_validate_empty(self):
1705
1692
        index.validate()
1706
1693
 
1707
1694
    def test_validate_no_refs_content(self):
1708
 
        index = self.make_index(nodes=[((b'key', ), b'value')])
 
1695
        index = self.make_index(nodes=[(('key', ), 'value')])
1709
1696
        index.validate()
1710
1697
 
1711
1698
 
1713
1700
 
1714
1701
    def make_index(self, ref_lists=1, key_elements=2, nodes=[],
1715
1702
                   add_callback=False):
1716
 
        result = _mod_index.InMemoryGraphIndex(
1717
 
            ref_lists, key_elements=key_elements)
 
1703
        result = _mod_index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1718
1704
        result.add_nodes(nodes)
1719
1705
        if add_callback:
1720
1706
            add_nodes_callback = result.add_nodes
1721
1707
        else:
1722
1708
            add_nodes_callback = None
1723
1709
        adapter = _mod_index.GraphIndexPrefixAdapter(
1724
 
            result, (b'prefix', ), key_elements - 1,
 
1710
            result, ('prefix', ), key_elements - 1,
1725
1711
            add_nodes_callback=add_nodes_callback)
1726
1712
        return result, adapter
1727
1713
 
1728
1714
    def test_add_node(self):
1729
1715
        index, adapter = self.make_index(add_callback=True)
1730
 
        adapter.add_node((b'key',), b'value', (((b'ref',),),))
1731
 
        self.assertEqual({(index, (b'prefix', b'key'), b'value',
1732
 
                           (((b'prefix', b'ref'),),))},
1733
 
                         set(index.iter_all_entries()))
 
1716
        adapter.add_node(('key',), 'value', ((('ref',),),))
 
1717
        self.assertEqual({(index, ('prefix', 'key'), 'value',
 
1718
                               ((('prefix', 'ref'),),))},
 
1719
            set(index.iter_all_entries()))
1734
1720
 
1735
1721
    def test_add_nodes(self):
1736
1722
        index, adapter = self.make_index(add_callback=True)
1737
1723
        adapter.add_nodes((
1738
 
            ((b'key',), b'value', (((b'ref',),),)),
1739
 
            ((b'key2',), b'value2', ((),)),
 
1724
            (('key',), 'value', ((('ref',),),)),
 
1725
            (('key2',), 'value2', ((),)),
1740
1726
            ))
1741
1727
        self.assertEqual({
1742
 
            (index, (b'prefix', b'key2'), b'value2', ((),)),
1743
 
            (index, (b'prefix', b'key'), b'value', (((b'prefix', b'ref'),),))
 
1728
            (index, ('prefix', 'key2'), 'value2', ((),)),
 
1729
            (index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1744
1730
            },
1745
1731
            set(index.iter_all_entries()))
1746
1732
 
1747
1733
    def test_construct(self):
1748
1734
        idx = _mod_index.InMemoryGraphIndex()
1749
 
        adapter = _mod_index.GraphIndexPrefixAdapter(idx, (b'prefix', ), 1)
 
1735
        adapter = _mod_index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1)
1750
1736
 
1751
1737
    def test_construct_with_callback(self):
1752
1738
        idx = _mod_index.InMemoryGraphIndex()
1753
 
        adapter = _mod_index.GraphIndexPrefixAdapter(idx, (b'prefix', ), 1,
1754
 
                                                     idx.add_nodes)
 
1739
        adapter = _mod_index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1,
 
1740
                                                idx.add_nodes)
1755
1741
 
1756
1742
    def test_iter_all_entries_cross_prefix_map_errors(self):
1757
1743
        index, adapter = self.make_index(nodes=[
1758
 
            ((b'prefix', b'key1'), b'data1', (((b'prefixaltered', b'key2'),),))])
1759
 
        self.assertRaises(_mod_index.BadIndexData, list,
1760
 
                          adapter.iter_all_entries())
 
1744
            (('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
 
1745
        self.assertRaises(_mod_index.BadIndexData, list, adapter.iter_all_entries())
1761
1746
 
1762
1747
    def test_iter_all_entries(self):
1763
1748
        index, adapter = self.make_index(nodes=[
1764
 
            ((b'notprefix', b'key1'), b'data', ((), )),
1765
 
            ((b'prefix', b'key1'), b'data1', ((), )),
1766
 
            ((b'prefix', b'key2'), b'data2', (((b'prefix', b'key1'),),))])
1767
 
        self.assertEqual({(index, (b'key1', ), b'data1', ((),)),
1768
 
                          (index, (b'key2', ), b'data2', (((b'key1',),),))},
1769
 
                         set(adapter.iter_all_entries()))
 
1749
            (('notprefix', 'key1'), 'data', ((), )),
 
1750
            (('prefix', 'key1'), 'data1', ((), )),
 
1751
            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
 
1752
        self.assertEqual({(index, ('key1', ), 'data1', ((),)),
 
1753
            (index, ('key2', ), 'data2', ((('key1',),),))},
 
1754
            set(adapter.iter_all_entries()))
1770
1755
 
1771
1756
    def test_iter_entries(self):
1772
1757
        index, adapter = self.make_index(nodes=[
1773
 
            ((b'notprefix', b'key1'), b'data', ((), )),
1774
 
            ((b'prefix', b'key1'), b'data1', ((), )),
1775
 
            ((b'prefix', b'key2'), b'data2', (((b'prefix', b'key1'),),))])
 
1758
            (('notprefix', 'key1'), 'data', ((), )),
 
1759
            (('prefix', 'key1'), 'data1', ((), )),
 
1760
            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1776
1761
        # ask for many - get all
1777
 
        self.assertEqual({(index, (b'key1', ), b'data1', ((),)),
1778
 
                          (index, (b'key2', ), b'data2', (((b'key1', ),),))},
1779
 
                         set(adapter.iter_entries([(b'key1', ), (b'key2', )])))
 
1762
        self.assertEqual({(index, ('key1', ), 'data1', ((),)),
 
1763
            (index, ('key2', ), 'data2', ((('key1', ),),))},
 
1764
            set(adapter.iter_entries([('key1', ), ('key2', )])))
1780
1765
        # ask for one, get one
1781
 
        self.assertEqual({(index, (b'key1', ), b'data1', ((),))},
1782
 
                         set(adapter.iter_entries([(b'key1', )])))
 
1766
        self.assertEqual({(index, ('key1', ), 'data1', ((),))},
 
1767
            set(adapter.iter_entries([('key1', )])))
1783
1768
        # ask for missing, get none
1784
1769
        self.assertEqual(set(),
1785
 
                         set(adapter.iter_entries([(b'key3', )])))
 
1770
            set(adapter.iter_entries([('key3', )])))
1786
1771
 
1787
1772
    def test_iter_entries_prefix(self):
1788
1773
        index, adapter = self.make_index(key_elements=3, nodes=[
1789
 
            ((b'notprefix', b'foo', b'key1'), b'data', ((), )),
1790
 
            ((b'prefix', b'prefix2', b'key1'), b'data1', ((), )),
1791
 
            ((b'prefix', b'prefix2', b'key2'), b'data2', (((b'prefix', b'prefix2', b'key1'),),))])
 
1774
            (('notprefix', 'foo', 'key1'), 'data', ((), )),
 
1775
            (('prefix', 'prefix2', 'key1'), 'data1', ((), )),
 
1776
            (('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1792
1777
        # ask for a prefix, get the results for just that prefix, adjusted.
1793
 
        self.assertEqual({(index, (b'prefix2', b'key1', ), b'data1', ((),)),
1794
 
                          (index, (b'prefix2', b'key2', ), b'data2', (((b'prefix2', b'key1', ),),))},
1795
 
                         set(adapter.iter_entries_prefix([(b'prefix2', None)])))
 
1778
        self.assertEqual({(index, ('prefix2', 'key1', ), 'data1', ((),)),
 
1779
            (index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))},
 
1780
            set(adapter.iter_entries_prefix([('prefix2', None)])))
1796
1781
 
1797
1782
    def test_key_count_no_matching_keys(self):
1798
1783
        index, adapter = self.make_index(nodes=[
1799
 
            ((b'notprefix', b'key1'), b'data', ((), ))])
 
1784
            (('notprefix', 'key1'), 'data', ((), ))])
1800
1785
        self.assertEqual(0, adapter.key_count())
1801
1786
 
1802
1787
    def test_key_count_some_keys(self):
1803
1788
        index, adapter = self.make_index(nodes=[
1804
 
            ((b'notprefix', b'key1'), b'data', ((), )),
1805
 
            ((b'prefix', b'key1'), b'data1', ((), )),
1806
 
            ((b'prefix', b'key2'), b'data2', (((b'prefix', b'key1'),),))])
 
1789
            (('notprefix', 'key1'), 'data', ((), )),
 
1790
            (('prefix', 'key1'), 'data1', ((), )),
 
1791
            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1807
1792
        self.assertEqual(2, adapter.key_count())
1808
1793
 
1809
1794
    def test_validate(self):
1810
1795
        index, adapter = self.make_index()
1811
1796
        calls = []
1812
 
 
1813
1797
        def validate():
1814
1798
            calls.append('called')
1815
1799
        index.validate = validate