← 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

  • Committer: John Arbash Meinel
  • Author(s): Mark Hammond
  • Date: 2008-09-09 17:02:21 UTC
  • mto: This revision was merged to the branch mainline in revision 3697.
  • Revision ID: john@arbash-meinel.com-20080909170221-svim3jw2mrz0amp3
An updated transparent icon for bzr.

Show diffs side-by-side

added added

removed removed

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