/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/bzr/_groupcompress_py.py

  • Committer: Jelmer Vernooij
  • Date: 2020-09-02 11:51:19 UTC
  • mto: (7490.40.109 work)
  • mto: This revision was merged to the branch mainline in revision 7526.
  • Revision ID: jelmer@jelmer.uk-20200902115119-otuspc349t9rmhua
add test for git file merge.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/bzr/_groupcompress_py.py
20
20
useless stuff.
21
21
"""
22
22
 
23
 
from bzrlib import osutils
 
23
from __future__ import absolute_import
 
24
 
 
25
from .. import osutils
 
26
from ..sixish import (
 
27
    indexbytes,
 
28
    int2byte,
 
29
    range,
 
30
    )
24
31
 
25
32
 
26
33
class _OutputHandler(object):
36
43
    def add_copy(self, start_byte, end_byte):
37
44
        # The data stream allows >64kB in a copy, but to match the compiled
38
45
        # code, we will also limit it to a 64kB copy
39
 
        for start_byte in xrange(start_byte, end_byte, 64*1024):
40
 
            num_bytes = min(64*1024, end_byte - start_byte)
 
46
        for start_byte in range(start_byte, end_byte, 64 * 1024):
 
47
            num_bytes = min(64 * 1024, end_byte - start_byte)
41
48
            copy_bytes = encode_copy_instruction(start_byte, num_bytes)
42
49
            self.out_lines.append(copy_bytes)
43
50
            self.index_lines.append(False)
48
55
        if self.cur_insert_len > 127:
49
56
            raise AssertionError('We cannot insert more than 127 bytes'
50
57
                                 ' at a time.')
51
 
        self.out_lines.append(chr(self.cur_insert_len))
 
58
        self.out_lines.append(int2byte(self.cur_insert_len))
52
59
        self.index_lines.append(False)
53
60
        self.out_lines.extend(self.cur_insert_lines)
54
61
        if self.cur_insert_len < self.min_len_to_index:
55
 
            self.index_lines.extend([False]*len(self.cur_insert_lines))
 
62
            self.index_lines.extend([False] * len(self.cur_insert_lines))
56
63
        else:
57
 
            self.index_lines.extend([True]*len(self.cur_insert_lines))
 
64
            self.index_lines.extend([True] * len(self.cur_insert_lines))
58
65
        self.cur_insert_lines = []
59
66
        self.cur_insert_len = 0
60
67
 
62
69
        # Flush out anything pending
63
70
        self._flush_insert()
64
71
        line_len = len(line)
65
 
        for start_index in xrange(0, line_len, 127):
 
72
        for start_index in range(0, line_len, 127):
66
73
            next_len = min(127, line_len - start_index)
67
 
            self.out_lines.append(chr(next_len))
 
74
            self.out_lines.append(int2byte(next_len))
68
75
            self.index_lines.append(False)
69
 
            self.out_lines.append(line[start_index:start_index+next_len])
 
76
            self.out_lines.append(line[start_index:start_index + next_len])
70
77
            # We don't index long lines, because we won't be able to match
71
78
            # a line split across multiple inserts anway
72
79
            self.index_lines.append(False)
109
116
        self.line_offsets = []
110
117
        self.endpoint = 0
111
118
        self._matching_lines = {}
112
 
        self.extend_lines(lines, [True]*len(lines))
 
119
        self.extend_lines(lines, [True] * len(lines))
113
120
 
114
121
    def _update_matching_lines(self, new_lines, index):
115
122
        matches = self._matching_lines
116
123
        start_idx = len(self.lines)
117
124
        if len(new_lines) != len(index):
118
125
            raise AssertionError('The number of lines to be indexed does'
119
 
                ' not match the index/don\'t index flags: %d != %d'
120
 
                % (len(new_lines), len(index)))
 
126
                                 ' not match the index/don\'t index flags: %d != %d'
 
127
                                 % (len(new_lines), len(index)))
121
128
        for idx, do_index in enumerate(index):
122
129
            if not do_index:
123
130
                continue
125
132
            try:
126
133
                matches[line].add(start_idx + idx)
127
134
            except KeyError:
128
 
                matches[line] = set([start_idx + idx])
 
135
                matches[line] = {start_idx + idx}
129
136
 
130
137
    def get_matches(self, line):
131
138
        """Return the lines which match the line in right."""
165
172
                # This is the first match in a range
166
173
                prev_locations = locations
167
174
                range_len = 1
168
 
                locations = None # Consumed
 
175
                locations = None  # Consumed
169
176
            else:
170
177
                # We have a match started, compare to see if any of the
171
178
                # current matches can be continued
175
182
                    # At least one of the regions continues to match
176
183
                    prev_locations = set(next_locations)
177
184
                    range_len += 1
178
 
                    locations = None # Consumed
 
185
                    locations = None  # Consumed
179
186
                else:
180
187
                    # All current regions no longer match.
181
188
                    # This line does still match something, just not at the
221
228
                if block[-1] < min_match_bytes:
222
229
                    # This block may be a 'short' block, check
223
230
                    old_start, new_start, range_len = block
224
 
                    matched_bytes = sum(map(len,
225
 
                        lines[new_start:new_start + range_len]))
 
231
                    matched_bytes = sum(map(len, lines[new_start:new_start + range_len]))
226
232
                    if matched_bytes < min_match_bytes:
227
233
                        block = None
228
234
            if block is not None:
245
251
            self.line_offsets.append(endpoint)
246
252
        if len(self.line_offsets) != len(self.lines):
247
253
            raise AssertionError('Somehow the line offset indicator'
248
 
                ' got out of sync with the line counter.')
 
254
                                 ' got out of sync with the line counter.')
249
255
        self.endpoint = endpoint
250
256
 
251
257
    def _flush_insert(self, start_linenum, end_linenum,
252
258
                      new_lines, out_lines, index_lines):
253
259
        """Add an 'insert' request to the data stream."""
254
 
        bytes_to_insert = ''.join(new_lines[start_linenum:end_linenum])
 
260
        bytes_to_insert = b''.join(new_lines[start_linenum:end_linenum])
255
261
        insert_length = len(bytes_to_insert)
256
262
        # Each insert instruction is at most 127 bytes long
257
 
        for start_byte in xrange(0, insert_length, 127):
 
263
        for start_byte in range(0, insert_length, 127):
258
264
            insert_count = min(insert_length - start_byte, 127)
259
 
            out_lines.append(chr(insert_count))
 
265
            out_lines.append(int2byte(insert_count))
260
266
            # Don't index the 'insert' instruction
261
267
            index_lines.append(False)
262
 
            insert = bytes_to_insert[start_byte:start_byte+insert_count]
 
268
            insert = bytes_to_insert[start_byte:start_byte + insert_count]
263
269
            as_lines = osutils.split_lines(insert)
264
270
            out_lines.extend(as_lines)
265
 
            index_lines.extend([True]*len(as_lines))
 
271
            index_lines.extend([True] * len(as_lines))
266
272
 
267
273
    def _flush_copy(self, old_start_linenum, num_lines,
268
274
                    out_lines, index_lines):
274
280
        num_bytes = stop_byte - first_byte
275
281
        # The data stream allows >64kB in a copy, but to match the compiled
276
282
        # code, we will also limit it to a 64kB copy
277
 
        for start_byte in xrange(first_byte, stop_byte, 64*1024):
278
 
            num_bytes = min(64*1024, stop_byte - start_byte)
 
283
        for start_byte in range(first_byte, stop_byte, 64 * 1024):
 
284
            num_bytes = min(64 * 1024, stop_byte - start_byte)
279
285
            copy_bytes = encode_copy_instruction(start_byte, num_bytes)
280
286
            out_lines.append(copy_bytes)
281
287
            index_lines.append(False)
282
288
 
283
 
    def make_delta(self, new_lines, bytes_length=None, soft=False):
 
289
    def make_delta(self, new_lines, bytes_length, soft=False):
284
290
        """Compute the delta for this content versus the original content."""
285
 
        if bytes_length is None:
286
 
            bytes_length = sum(map(len, new_lines))
287
291
        # reserved for content type, content length
288
 
        out_lines = ['', '', encode_base128_int(bytes_length)]
 
292
        out_lines = [b'', b'', encode_base128_int(bytes_length)]
289
293
        index_lines = [False, False, False]
290
294
        output_handler = _OutputHandler(out_lines, index_lines,
291
295
                                        self._MIN_MATCH_BYTES)
296
300
        for old_start, new_start, range_len in blocks:
297
301
            if new_start != current_line_num:
298
302
                # non-matching region, insert the content
299
 
                output_handler.add_insert(new_lines[current_line_num:new_start])
 
303
                output_handler.add_insert(
 
304
                    new_lines[current_line_num:new_start])
300
305
            current_line_num = new_start + range_len
301
306
            if range_len:
302
307
                # Convert the line based offsets into byte based offsets
311
316
 
312
317
def encode_base128_int(val):
313
318
    """Convert an integer into a 7-bit lsb encoding."""
314
 
    bytes = []
 
319
    data = bytearray()
315
320
    count = 0
316
321
    while val >= 0x80:
317
 
        bytes.append(chr((val | 0x80) & 0xFF))
 
322
        data.append((val | 0x80) & 0xFF)
318
323
        val >>= 7
319
 
    bytes.append(chr(val))
320
 
    return ''.join(bytes)
321
 
 
322
 
 
323
 
def decode_base128_int(bytes):
 
324
    data.append(val)
 
325
    return bytes(data)
 
326
 
 
327
 
 
328
def decode_base128_int(data):
324
329
    """Decode an integer from a 7-bit lsb encoding."""
325
330
    offset = 0
326
331
    val = 0
327
332
    shift = 0
328
 
    bval = ord(bytes[offset])
 
333
    bval = indexbytes(data, offset)
329
334
    while bval >= 0x80:
330
335
        val |= (bval & 0x7F) << shift
331
336
        shift += 7
332
337
        offset += 1
333
 
        bval = ord(bytes[offset])
 
338
        bval = indexbytes(data, offset)
334
339
    val |= bval << shift
335
340
    offset += 1
336
341
    return val, offset
345
350
        base_byte = offset & 0xff
346
351
        if base_byte:
347
352
            copy_command |= copy_bit
348
 
            copy_bytes.append(chr(base_byte))
 
353
            copy_bytes.append(int2byte(base_byte))
349
354
        offset >>= 8
350
355
    if length is None:
351
356
        raise ValueError("cannot supply a length of None")
360
365
            base_byte = length & 0xff
361
366
            if base_byte:
362
367
                copy_command |= copy_bit
363
 
                copy_bytes.append(chr(base_byte))
 
368
                copy_bytes.append(int2byte(base_byte))
364
369
            length >>= 8
365
 
    copy_bytes[0] = chr(copy_command)
366
 
    return ''.join(copy_bytes)
 
370
    copy_bytes[0] = int2byte(copy_command)
 
371
    return b''.join(copy_bytes)
367
372
 
368
373
 
369
374
def decode_copy_instruction(bytes, cmd, pos):
385
390
    offset = 0
386
391
    length = 0
387
392
    if (cmd & 0x01):
388
 
        offset = ord(bytes[pos])
 
393
        offset = indexbytes(bytes, pos)
389
394
        pos += 1
390
395
    if (cmd & 0x02):
391
 
        offset = offset | (ord(bytes[pos]) << 8)
 
396
        offset = offset | (indexbytes(bytes, pos) << 8)
392
397
        pos += 1
393
398
    if (cmd & 0x04):
394
 
        offset = offset | (ord(bytes[pos]) << 16)
 
399
        offset = offset | (indexbytes(bytes, pos) << 16)
395
400
        pos += 1
396
401
    if (cmd & 0x08):
397
 
        offset = offset | (ord(bytes[pos]) << 24)
 
402
        offset = offset | (indexbytes(bytes, pos) << 24)
398
403
        pos += 1
399
404
    if (cmd & 0x10):
400
 
        length = ord(bytes[pos])
 
405
        length = indexbytes(bytes, pos)
401
406
        pos += 1
402
407
    if (cmd & 0x20):
403
 
        length = length | (ord(bytes[pos]) << 8)
 
408
        length = length | (indexbytes(bytes, pos) << 8)
404
409
        pos += 1
405
410
    if (cmd & 0x40):
406
 
        length = length | (ord(bytes[pos]) << 16)
 
411
        length = length | (indexbytes(bytes, pos) << 16)
407
412
        pos += 1
408
413
    if length == 0:
409
414
        length = 65536
412
417
 
413
418
def make_delta(source_bytes, target_bytes):
414
419
    """Create a delta from source to target."""
415
 
    if type(source_bytes) is not str:
416
 
        raise TypeError('source is not a str')
417
 
    if type(target_bytes) is not str:
418
 
        raise TypeError('target is not a str')
 
420
    if not isinstance(source_bytes, bytes):
 
421
        raise TypeError('source is not bytes')
 
422
    if not isinstance(target_bytes, bytes):
 
423
        raise TypeError('target is not bytes')
419
424
    line_locations = LinesDeltaIndex(osutils.split_lines(source_bytes))
420
425
    delta, _ = line_locations.make_delta(osutils.split_lines(target_bytes),
421
426
                                         bytes_length=len(target_bytes))
422
 
    return ''.join(delta)
 
427
    return b''.join(delta)
423
428
 
424
429
 
425
430
def apply_delta(basis, delta):
426
431
    """Apply delta to this object to become new_version_id."""
427
 
    if type(basis) is not str:
428
 
        raise TypeError('basis is not a str')
429
 
    if type(delta) is not str:
430
 
        raise TypeError('delta is not a str')
 
432
    if not isinstance(basis, bytes):
 
433
        raise TypeError('basis is not bytes')
 
434
    if not isinstance(delta, bytes):
 
435
        raise TypeError('delta is not bytes')
431
436
    target_length, pos = decode_base128_int(delta)
432
437
    lines = []
433
438
    len_delta = len(delta)
434
439
    while pos < len_delta:
435
 
        cmd = ord(delta[pos])
 
440
        cmd = indexbytes(delta, pos)
436
441
        pos += 1
437
442
        if cmd & 0x80:
438
443
            offset, length, pos = decode_copy_instruction(delta, cmd, pos)
441
446
                raise ValueError('data would copy bytes past the'
442
447
                                 'end of source')
443
448
            lines.append(basis[offset:last])
444
 
        else: # Insert of 'cmd' bytes
 
449
        else:  # Insert of 'cmd' bytes
445
450
            if cmd == 0:
446
451
                raise ValueError('Command == 0 not supported yet')
447
 
            lines.append(delta[pos:pos+cmd])
 
452
            lines.append(delta[pos:pos + cmd])
448
453
            pos += cmd
449
 
    bytes = ''.join(lines)
450
 
    if len(bytes) != target_length:
 
454
    data = b''.join(lines)
 
455
    if len(data) != target_length:
451
456
        raise ValueError('Delta claimed to be %d long, but ended up'
452
457
                         ' %d long' % (target_length, len(bytes)))
453
 
    return bytes
 
458
    return data
454
459
 
455
460
 
456
461
def apply_delta_to_source(source, delta_start, delta_end):