/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-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_bisect_multi.py
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007, 2009, 2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
16
16
 
17
17
"""Tests for bisect_multi."""
18
18
 
19
 
from bzrlib import errors
20
 
from bzrlib.bisect_multi import bisect_multi_bytes
21
 
from bzrlib.tests import TestCase
 
19
from ..bisect_multi import bisect_multi_bytes
 
20
from . import TestCase
22
21
 
23
22
 
24
23
class TestBisectMultiBytes(TestCase):
25
24
 
26
25
    def test_lookup_no_keys_no_calls(self):
27
26
        calls = []
 
27
 
28
28
        def missing_content(location_keys):
29
29
            calls.append(location_keys)
30
30
            return ((location_key, False) for location_key in location_keys)
31
31
        self.assertEqual([],
32
 
            list(bisect_multi_bytes(missing_content, 100, [])))
 
32
                         list(bisect_multi_bytes(missing_content, 100, [])))
33
33
        self.assertEqual([], calls)
34
34
 
35
35
    def test_lookup_missing_key_no_content(self):
40
40
        for a given location, key pair.
41
41
        """
42
42
        calls = []
 
43
 
43
44
        def missing_content(location_keys):
44
45
            calls.append(location_keys)
45
46
            return ((location_key, False) for location_key in location_keys)
46
47
        self.assertEqual([],
47
 
            list(bisect_multi_bytes(missing_content, 0, ['foo', 'bar'])))
 
48
                         list(bisect_multi_bytes(missing_content, 0, ['foo', 'bar'])))
48
49
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
49
50
 
50
51
    def test_lookup_missing_key_before_all_others(self):
51
52
        calls = []
 
53
 
52
54
        def missing_first_content(location_keys):
53
55
            # returns -1 for all keys unless the byte offset is 0 when it
54
56
            # returns False
62
64
            return result
63
65
        # given a 0 length file, this should terminate with one call.
64
66
        self.assertEqual([],
65
 
            list(bisect_multi_bytes(missing_first_content, 0, ['foo', 'bar'])))
 
67
                         list(bisect_multi_bytes(missing_first_content, 0, ['foo', 'bar'])))
66
68
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
67
69
        del calls[:]
68
70
        # given a 2 length file, this should make two calls - 1, 0.
69
71
        self.assertEqual([],
70
 
            list(bisect_multi_bytes(missing_first_content, 2, ['foo', 'bar'])))
 
72
                         list(bisect_multi_bytes(missing_first_content, 2, ['foo', 'bar'])))
71
73
        self.assertEqual([
72
74
            [(1, 'foo'), (1, 'bar')],
73
75
            [(0, 'foo'), (0, 'bar')],
84
86
        # 800 thousand keys, and log2 of 800000 is 19 - so we're doing log2
85
87
        # steps in the worst case there.
86
88
        self.assertEqual([],
87
 
            list(bisect_multi_bytes(
88
 
                missing_first_content,268435456 - 1 , ['foo', 'bar'])))
 
89
                         list(bisect_multi_bytes(
 
90
                             missing_first_content, 268435456 - 1, ['foo', 'bar'])))
89
91
        self.assertEqual([
90
92
            [(134217727, 'foo'), (134217727, 'bar')],
91
93
            [(67108864, 'foo'), (67108864, 'bar')],
146
148
    def test_lookup_missing_key_after_all_others(self):
147
149
        calls = []
148
150
        end = None
 
151
 
149
152
        def missing_last_content(location_keys):
150
153
            # returns +1 for all keys unless the byte offset is 'end' when it
151
154
            # returns False
160
163
        # given a 0 length file, this should terminate with one call.
161
164
        end = 0
162
165
        self.assertEqual([],
163
 
            list(bisect_multi_bytes(missing_last_content, 0, ['foo', 'bar'])))
 
166
                         list(bisect_multi_bytes(missing_last_content, 0, ['foo', 'bar'])))
164
167
        self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
165
168
        del calls[:]
166
169
        end = 2
167
170
        # given a 3 length file, this should make two calls - 1, 2.
168
171
        self.assertEqual([],
169
 
            list(bisect_multi_bytes(missing_last_content, 3, ['foo', 'bar'])))
 
172
                         list(bisect_multi_bytes(missing_last_content, 3, ['foo', 'bar'])))
170
173
        self.assertEqual([
171
174
            [(1, 'foo'), (1, 'bar')],
172
175
            [(2, 'foo'), (2, 'bar')],
177
180
        # test_lookup_missing_key_before_all_others for details about this
178
181
        # assertion.
179
182
        self.assertEqual([],
180
 
            list(bisect_multi_bytes(
181
 
                missing_last_content,268435456 - 1 , ['foo', 'bar'])))
 
183
                         list(bisect_multi_bytes(
 
184
                             missing_last_content, 268435456 - 1, ['foo', 'bar'])))
182
185
        self.assertEqual([
183
186
            [(134217727, 'foo'), (134217727, 'bar')],
184
187
            [(201326590, 'foo'), (201326590, 'bar')],
238
241
 
239
242
    def test_lookup_when_a_key_is_missing_continues(self):
240
243
        calls = []
 
244
 
241
245
        def missing_foo_otherwise_missing_first_content(location_keys):
242
246
            # returns -1 for all keys unless the byte offset is 0 when it
243
247
            # returns False
252
256
        # given a 2 length file, this should terminate with two calls, one for
253
257
        # both keys, and one for bar only.
254
258
        self.assertEqual([],
255
 
            list(bisect_multi_bytes(
256
 
                missing_foo_otherwise_missing_first_content, 2,
257
 
                ['foo', 'bar'])))
 
259
                         list(bisect_multi_bytes(
 
260
                             missing_foo_otherwise_missing_first_content, 2,
 
261
                             ['foo', 'bar'])))
258
262
        self.assertEqual([
259
263
            [(1, 'foo'), (1, 'bar')],
260
264
            [(0, 'bar')],
262
266
 
263
267
    def test_found_keys_returned_other_searches_continue(self):
264
268
        calls = []
 
269
 
265
270
        def find_bar_at_1_foo_missing_at_0(location_keys):
266
271
            calls.append(location_keys)
267
272
            result = []
276
281
        # given a 4 length file, this should terminate with three calls, two for
277
282
        # both keys, and one for foo only.
278
283
        self.assertEqual([('bar', 'bar-result')],
279
 
            list(bisect_multi_bytes(
280
 
                find_bar_at_1_foo_missing_at_0, 4,
281
 
                ['foo', 'bar'])))
 
284
                         list(bisect_multi_bytes(
 
285
                             find_bar_at_1_foo_missing_at_0, 4,
 
286
                             ['foo', 'bar'])))
282
287
        self.assertEqual([
283
288
            [(2, 'foo'), (2, 'bar')],
284
289
            [(1, 'foo'), (1, 'bar')],
287
292
 
288
293
    def test_searches_different_keys_in_different_directions(self):
289
294
        calls = []
 
295
 
290
296
        def missing_bar_at_1_foo_at_3(location_keys):
291
297
            calls.append(location_keys)
292
298
            result = []
306
312
            return result
307
313
        # given a 4 length file, this should terminate with two calls.
308
314
        self.assertEqual([],
309
 
            list(bisect_multi_bytes(
310
 
                missing_bar_at_1_foo_at_3, 4,
311
 
                ['foo', 'bar'])))
 
315
                         list(bisect_multi_bytes(
 
316
                             missing_bar_at_1_foo_at_3, 4,
 
317
                             ['foo', 'bar'])))
312
318
        self.assertEqual([
313
319
            [(2, 'foo'), (2, 'bar')],
314
320
            [(3, 'foo'), (1, 'bar')],
318
324
        # check that we can search down, up, down again -
319
325
        # so length 8, goes 4, 6, 5
320
326
        calls = []
 
327
 
321
328
        def missing_at_5(location_keys):
322
329
            calls.append(location_keys)
323
330
            result = []
333
340
            return result
334
341
        # given a 8 length file, this should terminate with three calls.
335
342
        self.assertEqual([],
336
 
            list(bisect_multi_bytes(
337
 
                missing_at_5, 8,
338
 
                ['foo', 'bar'])))
 
343
                         list(bisect_multi_bytes(
 
344
                             missing_at_5, 8,
 
345
                             ['foo', 'bar'])))
339
346
        self.assertEqual([
340
347
            [(4, 'foo'), (4, 'bar')],
341
348
            [(6, 'foo'), (6, 'bar')],
342
349
            [(5, 'foo'), (5, 'bar')],
343
350
            ], calls)
344