/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_bisect_multi.py

[merge] robertc's integration, updated tests to check for retcode=3

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_bisect_multi.py
1
 
# Copyright (C) 2007, 2009, 2011 Canonical Ltd
2
 
#
3
 
# This program is free software; you can redistribute it and/or modify
4
 
# it under the terms of the GNU General Public License as published by
5
 
# the Free Software Foundation; either version 2 of the License, or
6
 
# (at your option) any later version.
7
 
#
8
 
# This program is distributed in the hope that it will be useful,
9
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
# GNU General Public License for more details.
12
 
#
13
 
# You should have received a copy of the GNU General Public License
14
 
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
"""Tests for bisect_multi."""
18
 
 
19
 
from ..bisect_multi import bisect_multi_bytes
20
 
from . import TestCase
21
 
 
22
 
 
23
 
class TestBisectMultiBytes(TestCase):
24
 
 
25
 
    def test_lookup_no_keys_no_calls(self):
26
 
        calls = []
27
 
 
28
 
        def missing_content(location_keys):
29
 
            calls.append(location_keys)
30
 
            return ((location_key, False) for location_key in location_keys)
31
 
        self.assertEqual([],
32
 
                         list(bisect_multi_bytes(missing_content, 100, [])))
33
 
        self.assertEqual([], calls)
34
 
 
35
 
    def test_lookup_missing_key_no_content(self):
36
 
        """Doing a lookup in a zero-length file still does a single request.
37
 
 
38
 
        This makes sense because the bisector cannot tell how long content is
39
 
        and its more flexible to only stop when the content object says 'False'
40
 
        for a given location, key pair.
41
 
        """
42
 
        calls = []
43
 
 
44
 
        def missing_content(location_keys):
45
 
            calls.append(location_keys)
46
 
            return ((location_key, False) for location_key in location_keys)
47
 
        self.assertEqual([],
48
 
                         list(bisect_multi_bytes(missing_content, 0, ['foo', 'bar'])))
49
 
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
50
 
 
51
 
    def test_lookup_missing_key_before_all_others(self):
52
 
        calls = []
53
 
 
54
 
        def missing_first_content(location_keys):
55
 
            # returns -1 for all keys unless the byte offset is 0 when it
56
 
            # returns False
57
 
            calls.append(location_keys)
58
 
            result = []
59
 
            for location_key in location_keys:
60
 
                if location_key[0] == 0:
61
 
                    result.append((location_key, False))
62
 
                else:
63
 
                    result.append((location_key, -1))
64
 
            return result
65
 
        # given a 0 length file, this should terminate with one call.
66
 
        self.assertEqual([],
67
 
                         list(bisect_multi_bytes(missing_first_content, 0, ['foo', 'bar'])))
68
 
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
69
 
        del calls[:]
70
 
        # given a 2 length file, this should make two calls - 1, 0.
71
 
        self.assertEqual([],
72
 
                         list(bisect_multi_bytes(missing_first_content, 2, ['foo', 'bar'])))
73
 
        self.assertEqual([
74
 
            [(1, 'foo'), (1, 'bar')],
75
 
            [(0, 'foo'), (0, 'bar')],
76
 
            ], calls)
77
 
        del calls[:]
78
 
        # given a really long file - 200MB, this should make a series of calls with the
79
 
        # gap between adjactent calls dropping by 50% each time. We choose a
80
 
        # length which just under a power of two to generate a corner case in
81
 
        # bisection - naively using power of two reduction in size can lead to
82
 
        # a very long tail in the bisection process. The current users of
83
 
        # the bisect_multi_bytes api are not expected to be concerned by this,
84
 
        # as the delta gets down to 4K (the minimum we expect to read and
85
 
        # parse) within 16 steps even on a 200MB index (which at 4 keys/K is
86
 
        # 800 thousand keys, and log2 of 800000 is 19 - so we're doing log2
87
 
        # steps in the worst case there.
88
 
        self.assertEqual([],
89
 
                         list(bisect_multi_bytes(
90
 
                             missing_first_content, 268435456 - 1, ['foo', 'bar'])))
91
 
        self.assertEqual([
92
 
            [(134217727, 'foo'), (134217727, 'bar')],
93
 
            [(67108864, 'foo'), (67108864, 'bar')],
94
 
            [(33554433, 'foo'), (33554433, 'bar')],
95
 
            [(16777218, 'foo'), (16777218, 'bar')],
96
 
            [(8388611, 'foo'), (8388611, 'bar')],
97
 
            [(4194308, 'foo'), (4194308, 'bar')],
98
 
            [(2097157, 'foo'), (2097157, 'bar')],
99
 
            [(1048582, 'foo'), (1048582, 'bar')],
100
 
            [(524295, 'foo'), (524295, 'bar')],
101
 
            [(262152, 'foo'), (262152, 'bar')],
102
 
            [(131081, 'foo'), (131081, 'bar')],
103
 
            [(65546, 'foo'), (65546, 'bar')],
104
 
            [(32779, 'foo'), (32779, 'bar')],
105
 
            [(16396, 'foo'), (16396, 'bar')],
106
 
            [(8205, 'foo'), (8205, 'bar')],
107
 
            [(4110, 'foo'), (4110, 'bar')],
108
 
            [(2063, 'foo'), (2063, 'bar')],
109
 
            [(1040, 'foo'), (1040, 'bar')],
110
 
            [(529, 'foo'), (529, 'bar')],
111
 
            [(274, 'foo'), (274, 'bar')],
112
 
            [(147, 'foo'), (147, 'bar')],
113
 
            [(84, 'foo'), (84, 'bar')],
114
 
            [(53, 'foo'), (53, 'bar')],
115
 
            [(38, 'foo'), (38, 'bar')],
116
 
            [(31, 'foo'), (31, 'bar')],
117
 
            [(28, 'foo'), (28, 'bar')],
118
 
            [(27, 'foo'), (27, 'bar')],
119
 
            [(26, 'foo'), (26, 'bar')],
120
 
            [(25, 'foo'), (25, 'bar')],
121
 
            [(24, 'foo'), (24, 'bar')],
122
 
            [(23, 'foo'), (23, 'bar')],
123
 
            [(22, 'foo'), (22, 'bar')],
124
 
            [(21, 'foo'), (21, 'bar')],
125
 
            [(20, 'foo'), (20, 'bar')],
126
 
            [(19, 'foo'), (19, 'bar')],
127
 
            [(18, 'foo'), (18, 'bar')],
128
 
            [(17, 'foo'), (17, 'bar')],
129
 
            [(16, 'foo'), (16, 'bar')],
130
 
            [(15, 'foo'), (15, 'bar')],
131
 
            [(14, 'foo'), (14, 'bar')],
132
 
            [(13, 'foo'), (13, 'bar')],
133
 
            [(12, 'foo'), (12, 'bar')],
134
 
            [(11, 'foo'), (11, 'bar')],
135
 
            [(10, 'foo'), (10, 'bar')],
136
 
            [(9, 'foo'), (9, 'bar')],
137
 
            [(8, 'foo'), (8, 'bar')],
138
 
            [(7, 'foo'), (7, 'bar')],
139
 
            [(6, 'foo'), (6, 'bar')],
140
 
            [(5, 'foo'), (5, 'bar')],
141
 
            [(4, 'foo'), (4, 'bar')],
142
 
            [(3, 'foo'), (3, 'bar')],
143
 
            [(2, 'foo'), (2, 'bar')],
144
 
            [(1, 'foo'), (1, 'bar')],
145
 
            [(0, 'foo'), (0, 'bar')],
146
 
            ], calls)
147
 
 
148
 
    def test_lookup_missing_key_after_all_others(self):
149
 
        calls = []
150
 
        end = None
151
 
 
152
 
        def missing_last_content(location_keys):
153
 
            # returns +1 for all keys unless the byte offset is 'end' when it
154
 
            # returns False
155
 
            calls.append(location_keys)
156
 
            result = []
157
 
            for location_key in location_keys:
158
 
                if location_key[0] == end:
159
 
                    result.append((location_key, False))
160
 
                else:
161
 
                    result.append((location_key, +1))
162
 
            return result
163
 
        # given a 0 length file, this should terminate with one call.
164
 
        end = 0
165
 
        self.assertEqual([],
166
 
                         list(bisect_multi_bytes(missing_last_content, 0, ['foo', 'bar'])))
167
 
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
168
 
        del calls[:]
169
 
        end = 2
170
 
        # given a 3 length file, this should make two calls - 1, 2.
171
 
        self.assertEqual([],
172
 
                         list(bisect_multi_bytes(missing_last_content, 3, ['foo', 'bar'])))
173
 
        self.assertEqual([
174
 
            [(1, 'foo'), (1, 'bar')],
175
 
            [(2, 'foo'), (2, 'bar')],
176
 
            ], calls)
177
 
        del calls[:]
178
 
        end = 268435456 - 2
179
 
        # see the really-big lookup series in
180
 
        # test_lookup_missing_key_before_all_others for details about this
181
 
        # assertion.
182
 
        self.assertEqual([],
183
 
                         list(bisect_multi_bytes(
184
 
                             missing_last_content, 268435456 - 1, ['foo', 'bar'])))
185
 
        self.assertEqual([
186
 
            [(134217727, 'foo'), (134217727, 'bar')],
187
 
            [(201326590, 'foo'), (201326590, 'bar')],
188
 
            [(234881021, 'foo'), (234881021, 'bar')],
189
 
            [(251658236, 'foo'), (251658236, 'bar')],
190
 
            [(260046843, 'foo'), (260046843, 'bar')],
191
 
            [(264241146, 'foo'), (264241146, 'bar')],
192
 
            [(266338297, 'foo'), (266338297, 'bar')],
193
 
            [(267386872, 'foo'), (267386872, 'bar')],
194
 
            [(267911159, 'foo'), (267911159, 'bar')],
195
 
            [(268173302, 'foo'), (268173302, 'bar')],
196
 
            [(268304373, 'foo'), (268304373, 'bar')],
197
 
            [(268369908, 'foo'), (268369908, 'bar')],
198
 
            [(268402675, 'foo'), (268402675, 'bar')],
199
 
            [(268419058, 'foo'), (268419058, 'bar')],
200
 
            [(268427249, 'foo'), (268427249, 'bar')],
201
 
            [(268431344, 'foo'), (268431344, 'bar')],
202
 
            [(268433391, 'foo'), (268433391, 'bar')],
203
 
            [(268434414, 'foo'), (268434414, 'bar')],
204
 
            [(268434925, 'foo'), (268434925, 'bar')],
205
 
            [(268435180, 'foo'), (268435180, 'bar')],
206
 
            [(268435307, 'foo'), (268435307, 'bar')],
207
 
            [(268435370, 'foo'), (268435370, 'bar')],
208
 
            [(268435401, 'foo'), (268435401, 'bar')],
209
 
            [(268435416, 'foo'), (268435416, 'bar')],
210
 
            [(268435423, 'foo'), (268435423, 'bar')],
211
 
            [(268435426, 'foo'), (268435426, 'bar')],
212
 
            [(268435427, 'foo'), (268435427, 'bar')],
213
 
            [(268435428, 'foo'), (268435428, 'bar')],
214
 
            [(268435429, 'foo'), (268435429, 'bar')],
215
 
            [(268435430, 'foo'), (268435430, 'bar')],
216
 
            [(268435431, 'foo'), (268435431, 'bar')],
217
 
            [(268435432, 'foo'), (268435432, 'bar')],
218
 
            [(268435433, 'foo'), (268435433, 'bar')],
219
 
            [(268435434, 'foo'), (268435434, 'bar')],
220
 
            [(268435435, 'foo'), (268435435, 'bar')],
221
 
            [(268435436, 'foo'), (268435436, 'bar')],
222
 
            [(268435437, 'foo'), (268435437, 'bar')],
223
 
            [(268435438, 'foo'), (268435438, 'bar')],
224
 
            [(268435439, 'foo'), (268435439, 'bar')],
225
 
            [(268435440, 'foo'), (268435440, 'bar')],
226
 
            [(268435441, 'foo'), (268435441, 'bar')],
227
 
            [(268435442, 'foo'), (268435442, 'bar')],
228
 
            [(268435443, 'foo'), (268435443, 'bar')],
229
 
            [(268435444, 'foo'), (268435444, 'bar')],
230
 
            [(268435445, 'foo'), (268435445, 'bar')],
231
 
            [(268435446, 'foo'), (268435446, 'bar')],
232
 
            [(268435447, 'foo'), (268435447, 'bar')],
233
 
            [(268435448, 'foo'), (268435448, 'bar')],
234
 
            [(268435449, 'foo'), (268435449, 'bar')],
235
 
            [(268435450, 'foo'), (268435450, 'bar')],
236
 
            [(268435451, 'foo'), (268435451, 'bar')],
237
 
            [(268435452, 'foo'), (268435452, 'bar')],
238
 
            [(268435453, 'foo'), (268435453, 'bar')],
239
 
            [(268435454, 'foo'), (268435454, 'bar')]
240
 
            ], calls)
241
 
 
242
 
    def test_lookup_when_a_key_is_missing_continues(self):
243
 
        calls = []
244
 
 
245
 
        def missing_foo_otherwise_missing_first_content(location_keys):
246
 
            # returns -1 for all keys unless the byte offset is 0 when it
247
 
            # returns False
248
 
            calls.append(location_keys)
249
 
            result = []
250
 
            for location_key in location_keys:
251
 
                if location_key[1] == 'foo' or location_key[0] == 0:
252
 
                    result.append((location_key, False))
253
 
                else:
254
 
                    result.append((location_key, -1))
255
 
            return result
256
 
        # given a 2 length file, this should terminate with two calls, one for
257
 
        # both keys, and one for bar only.
258
 
        self.assertEqual([],
259
 
                         list(bisect_multi_bytes(
260
 
                             missing_foo_otherwise_missing_first_content, 2,
261
 
                             ['foo', 'bar'])))
262
 
        self.assertEqual([
263
 
            [(1, 'foo'), (1, 'bar')],
264
 
            [(0, 'bar')],
265
 
            ], calls)
266
 
 
267
 
    def test_found_keys_returned_other_searches_continue(self):
268
 
        calls = []
269
 
 
270
 
        def find_bar_at_1_foo_missing_at_0(location_keys):
271
 
            calls.append(location_keys)
272
 
            result = []
273
 
            for location_key in location_keys:
274
 
                if location_key == (1, 'bar'):
275
 
                    result.append((location_key, 'bar-result'))
276
 
                elif location_key[0] == 0:
277
 
                    result.append((location_key, False))
278
 
                else:
279
 
                    result.append((location_key, -1))
280
 
            return result
281
 
        # given a 4 length file, this should terminate with three calls, two for
282
 
        # both keys, and one for foo only.
283
 
        self.assertEqual([('bar', 'bar-result')],
284
 
                         list(bisect_multi_bytes(
285
 
                             find_bar_at_1_foo_missing_at_0, 4,
286
 
                             ['foo', 'bar'])))
287
 
        self.assertEqual([
288
 
            [(2, 'foo'), (2, 'bar')],
289
 
            [(1, 'foo'), (1, 'bar')],
290
 
            [(0, 'foo')],
291
 
            ], calls)
292
 
 
293
 
    def test_searches_different_keys_in_different_directions(self):
294
 
        calls = []
295
 
 
296
 
        def missing_bar_at_1_foo_at_3(location_keys):
297
 
            calls.append(location_keys)
298
 
            result = []
299
 
            for location_key in location_keys:
300
 
                if location_key[1] == 'bar':
301
 
                    if location_key[0] == 1:
302
 
                        result.append((location_key, False))
303
 
                    else:
304
 
                        # search down
305
 
                        result.append((location_key, -1))
306
 
                elif location_key[1] == 'foo':
307
 
                    if location_key[0] == 3:
308
 
                        result.append((location_key, False))
309
 
                    else:
310
 
                        # search up
311
 
                        result.append((location_key, +1))
312
 
            return result
313
 
        # given a 4 length file, this should terminate with two calls.
314
 
        self.assertEqual([],
315
 
                         list(bisect_multi_bytes(
316
 
                             missing_bar_at_1_foo_at_3, 4,
317
 
                             ['foo', 'bar'])))
318
 
        self.assertEqual([
319
 
            [(2, 'foo'), (2, 'bar')],
320
 
            [(3, 'foo'), (1, 'bar')],
321
 
            ], calls)
322
 
 
323
 
    def test_change_direction_in_single_key_search(self):
324
 
        # check that we can search down, up, down again -
325
 
        # so length 8, goes 4, 6, 5
326
 
        calls = []
327
 
 
328
 
        def missing_at_5(location_keys):
329
 
            calls.append(location_keys)
330
 
            result = []
331
 
            for location_key in location_keys:
332
 
                if location_key[0] == 5:
333
 
                    result.append((location_key, False))
334
 
                elif location_key[0] > 5:
335
 
                    # search down
336
 
                    result.append((location_key, -1))
337
 
                else:
338
 
                    # search up
339
 
                    result.append((location_key, +1))
340
 
            return result
341
 
        # given a 8 length file, this should terminate with three calls.
342
 
        self.assertEqual([],
343
 
                         list(bisect_multi_bytes(
344
 
                             missing_at_5, 8,
345
 
                             ['foo', 'bar'])))
346
 
        self.assertEqual([
347
 
            [(4, 'foo'), (4, 'bar')],
348
 
            [(6, 'foo'), (6, 'bar')],
349
 
            [(5, 'foo'), (5, 'bar')],
350
 
            ], calls)