← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_bisect_multi.py

Exclude more files from dumb-rsync upload

Show diffs side-by-side

added added

removed removed

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