/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

  • Committer: Jelmer Vernooij
  • Date: 2020-03-22 01:35:14 UTC
  • mfrom: (7490.7.6 work)
  • mto: This revision was merged to the branch mainline in revision 7499.
  • Revision ID: jelmer@jelmer.uk-20200322013514-7vw1ntwho04rcuj3
merge lp:brz/3.1.

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)