/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-05-06 11:48:54 UTC
  • mto: This revision was merged to the branch mainline in revision 6960.
  • Revision ID: jelmer@jelmer.uk-20180506114854-h4qd9ojaqy8wxjsd
Move .mailmap to root.

Show diffs side-by-side

added added

removed removed

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