/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/merge3.py

  • Committer: Breezy landing bot
  • Author(s): Jelmer Vernooij
  • Date: 2018-11-16 18:26:22 UTC
  • mfrom: (7167.1.4 run-flake8)
  • Revision ID: breezy.the.bot@gmail.com-20181116182622-qw3gan3hz78a2imw
Add a flake8 test.

Merged from https://code.launchpad.net/~jelmer/brz/run-flake8/+merge/358902

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/merge3.py
 
1
# Copyright (C) 2005-2010 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
from __future__ import absolute_import
 
18
 
 
19
# mbp: "you know that thing where cvs gives you conflict markers?"
 
20
# s: "i hate that."
 
21
 
 
22
from . import (
 
23
    errors,
 
24
    patiencediff,
 
25
    textfile,
 
26
    )
 
27
 
 
28
 
 
29
class CantReprocessAndShowBase(errors.BzrError):
 
30
 
 
31
    _fmt = ("Can't reprocess and show base, because reprocessing obscures "
 
32
           "the relationship of conflicting lines to the base")
 
33
 
 
34
 
 
35
def intersect(ra, rb):
 
36
    """Given two ranges return the range where they intersect or None.
 
37
 
 
38
    >>> intersect((0, 10), (0, 6))
 
39
    (0, 6)
 
40
    >>> intersect((0, 10), (5, 15))
 
41
    (5, 10)
 
42
    >>> intersect((0, 10), (10, 15))
 
43
    >>> intersect((0, 9), (10, 15))
 
44
    >>> intersect((0, 9), (7, 15))
 
45
    (7, 9)
 
46
    """
 
47
    # preconditions: (ra[0] <= ra[1]) and (rb[0] <= rb[1])
 
48
 
 
49
    sa = max(ra[0], rb[0])
 
50
    sb = min(ra[1], rb[1])
 
51
    if sa < sb:
 
52
        return sa, sb
 
53
    else:
 
54
        return None
 
55
 
 
56
 
 
57
def compare_range(a, astart, aend, b, bstart, bend):
 
58
    """Compare a[astart:aend] == b[bstart:bend], without slicing.
 
59
    """
 
60
    if (aend-astart) != (bend-bstart):
 
61
        return False
 
62
    for ia, ib in zip(range(astart, aend), range(bstart, bend)):
 
63
        if a[ia] != b[ib]:
 
64
            return False
 
65
    else:
 
66
        return True
 
67
 
 
68
 
 
69
class Merge3(object):
 
70
    """3-way merge of texts.
 
71
 
 
72
    Given BASE, OTHER, THIS, tries to produce a combined text
 
73
    incorporating the changes from both BASE->OTHER and BASE->THIS.
 
74
    All three will typically be sequences of lines."""
 
75
 
 
76
    def __init__(self, base, a, b, is_cherrypick=False, allow_objects=False):
 
77
        """Constructor.
 
78
 
 
79
        :param base: lines in BASE
 
80
        :param a: lines in A
 
81
        :param b: lines in B
 
82
        :param is_cherrypick: flag indicating if this merge is a cherrypick.
 
83
            When cherrypicking b => a, matches with b and base do not conflict.
 
84
        :param allow_objects: if True, do not require that base, a and b are
 
85
            plain Python strs.  Also prevents BinaryFile from being raised.
 
86
            Lines can be any sequence of comparable and hashable Python
 
87
            objects.
 
88
        """
 
89
        if not allow_objects:
 
90
            textfile.check_text_lines(base)
 
91
            textfile.check_text_lines(a)
 
92
            textfile.check_text_lines(b)
 
93
        self.base = base
 
94
        self.a = a
 
95
        self.b = b
 
96
        self.is_cherrypick = is_cherrypick
 
97
 
 
98
    def merge_lines(self,
 
99
                    name_a=None,
 
100
                    name_b=None,
 
101
                    name_base=None,
 
102
                    start_marker=b'<<<<<<<',
 
103
                    mid_marker=b'=======',
 
104
                    end_marker=b'>>>>>>>',
 
105
                    base_marker=None,
 
106
                    reprocess=False):
 
107
        """Return merge in cvs-like form.
 
108
        """
 
109
        newline = b'\n'
 
110
        if len(self.a) > 0:
 
111
            if self.a[0].endswith(b'\r\n'):
 
112
                newline = b'\r\n'
 
113
            elif self.a[0].endswith(b'\r'):
 
114
                newline = b'\r'
 
115
        if base_marker and reprocess:
 
116
            raise CantReprocessAndShowBase()
 
117
        if name_a:
 
118
            start_marker = start_marker + b' ' + name_a
 
119
        if name_b:
 
120
            end_marker = end_marker + b' ' + name_b
 
121
        if name_base and base_marker:
 
122
            base_marker = base_marker + b' ' + name_base
 
123
        merge_regions = self.merge_regions()
 
124
        if reprocess is True:
 
125
            merge_regions = self.reprocess_merge_regions(merge_regions)
 
126
        for t in merge_regions:
 
127
            what = t[0]
 
128
            if what == 'unchanged':
 
129
                for i in range(t[1], t[2]):
 
130
                    yield self.base[i]
 
131
            elif what == 'a' or what == 'same':
 
132
                for i in range(t[1], t[2]):
 
133
                    yield self.a[i]
 
134
            elif what == 'b':
 
135
                for i in range(t[1], t[2]):
 
136
                    yield self.b[i]
 
137
            elif what == 'conflict':
 
138
                yield start_marker + newline
 
139
                for i in range(t[3], t[4]):
 
140
                    yield self.a[i]
 
141
                if base_marker is not None:
 
142
                    yield base_marker + newline
 
143
                    for i in range(t[1], t[2]):
 
144
                        yield self.base[i]
 
145
                yield mid_marker + newline
 
146
                for i in range(t[5], t[6]):
 
147
                    yield self.b[i]
 
148
                yield end_marker + newline
 
149
            else:
 
150
                raise ValueError(what)
 
151
 
 
152
    def merge_annotated(self):
 
153
        """Return merge with conflicts, showing origin of lines.
 
154
 
 
155
        Most useful for debugging merge.
 
156
        """
 
157
        for t in self.merge_regions():
 
158
            what = t[0]
 
159
            if what == 'unchanged':
 
160
                for i in range(t[1], t[2]):
 
161
                    yield 'u | ' + self.base[i]
 
162
            elif what == 'a' or what == 'same':
 
163
                for i in range(t[1], t[2]):
 
164
                    yield what[0] + ' | ' + self.a[i]
 
165
            elif what == 'b':
 
166
                for i in range(t[1], t[2]):
 
167
                    yield 'b | ' + self.b[i]
 
168
            elif what == 'conflict':
 
169
                yield '<<<<\n'
 
170
                for i in range(t[3], t[4]):
 
171
                    yield 'A | ' + self.a[i]
 
172
                yield '----\n'
 
173
                for i in range(t[5], t[6]):
 
174
                    yield 'B | ' + self.b[i]
 
175
                yield '>>>>\n'
 
176
            else:
 
177
                raise ValueError(what)
 
178
 
 
179
    def merge_groups(self):
 
180
        """Yield sequence of line groups.  Each one is a tuple:
 
181
 
 
182
        'unchanged', lines
 
183
             Lines unchanged from base
 
184
 
 
185
        'a', lines
 
186
             Lines taken from a
 
187
 
 
188
        'same', lines
 
189
             Lines taken from a (and equal to b)
 
190
 
 
191
        'b', lines
 
192
             Lines taken from b
 
193
 
 
194
        'conflict', base_lines, a_lines, b_lines
 
195
             Lines from base were changed to either a or b and conflict.
 
196
        """
 
197
        for t in self.merge_regions():
 
198
            what = t[0]
 
199
            if what == 'unchanged':
 
200
                yield what, self.base[t[1]:t[2]]
 
201
            elif what == 'a' or what == 'same':
 
202
                yield what, self.a[t[1]:t[2]]
 
203
            elif what == 'b':
 
204
                yield what, self.b[t[1]:t[2]]
 
205
            elif what == 'conflict':
 
206
                yield (what,
 
207
                       self.base[t[1]:t[2]],
 
208
                       self.a[t[3]:t[4]],
 
209
                       self.b[t[5]:t[6]])
 
210
            else:
 
211
                raise ValueError(what)
 
212
 
 
213
    def merge_regions(self):
 
214
        """Return sequences of matching and conflicting regions.
 
215
 
 
216
        This returns tuples, where the first value says what kind we
 
217
        have:
 
218
 
 
219
        'unchanged', start, end
 
220
             Take a region of base[start:end]
 
221
 
 
222
        'same', astart, aend
 
223
             b and a are different from base but give the same result
 
224
 
 
225
        'a', start, end
 
226
             Non-clashing insertion from a[start:end]
 
227
 
 
228
        Method is as follows:
 
229
 
 
230
        The two sequences align only on regions which match the base
 
231
        and both descendents.  These are found by doing a two-way diff
 
232
        of each one against the base, and then finding the
 
233
        intersections between those regions.  These "sync regions"
 
234
        are by definition unchanged in both and easily dealt with.
 
235
 
 
236
        The regions in between can be in any of three cases:
 
237
        conflicted, or changed on only one side.
 
238
        """
 
239
 
 
240
        # section a[0:ia] has been disposed of, etc
 
241
        iz = ia = ib = 0
 
242
 
 
243
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 
244
            matchlen = zend - zmatch
 
245
            # invariants:
 
246
            #   matchlen >= 0
 
247
            #   matchlen == (aend - amatch)
 
248
            #   matchlen == (bend - bmatch)
 
249
            len_a = amatch - ia
 
250
            len_b = bmatch - ib
 
251
            len_base = zmatch - iz
 
252
            # invariants:
 
253
            # assert len_a >= 0
 
254
            # assert len_b >= 0
 
255
            # assert len_base >= 0
 
256
 
 
257
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
 
258
 
 
259
            if len_a or len_b:
 
260
                # try to avoid actually slicing the lists
 
261
                same = compare_range(self.a, ia, amatch,
 
262
                                     self.b, ib, bmatch)
 
263
 
 
264
                if same:
 
265
                    yield 'same', ia, amatch
 
266
                else:
 
267
                    equal_a = compare_range(self.a, ia, amatch,
 
268
                                            self.base, iz, zmatch)
 
269
                    equal_b = compare_range(self.b, ib, bmatch,
 
270
                                            self.base, iz, zmatch)
 
271
                    if equal_a and not equal_b:
 
272
                        yield 'b', ib, bmatch
 
273
                    elif equal_b and not equal_a:
 
274
                        yield 'a', ia, amatch
 
275
                    elif not equal_a and not equal_b:
 
276
                        if self.is_cherrypick:
 
277
                            for node in self._refine_cherrypick_conflict(
 
278
                                                    iz, zmatch, ia, amatch,
 
279
                                                    ib, bmatch):
 
280
                                yield node
 
281
                        else:
 
282
                            yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
 
283
                    else:
 
284
                        raise AssertionError("can't handle a=b=base but unmatched")
 
285
 
 
286
                ia = amatch
 
287
                ib = bmatch
 
288
            iz = zmatch
 
289
 
 
290
            # if the same part of the base was deleted on both sides
 
291
            # that's OK, we can just skip it.
 
292
 
 
293
            if matchlen > 0:
 
294
                # invariants:
 
295
                # assert ia == amatch
 
296
                # assert ib == bmatch
 
297
                # assert iz == zmatch
 
298
 
 
299
                yield 'unchanged', zmatch, zend
 
300
                iz = zend
 
301
                ia = aend
 
302
                ib = bend
 
303
 
 
304
    def _refine_cherrypick_conflict(self, zstart, zend, astart, aend, bstart, bend):
 
305
        """When cherrypicking b => a, ignore matches with b and base."""
 
306
        # Do not emit regions which match, only regions which do not match
 
307
        matches = patiencediff.PatienceSequenceMatcher(None,
 
308
            self.base[zstart:zend], self.b[bstart:bend]).get_matching_blocks()
 
309
        last_base_idx = 0
 
310
        last_b_idx = 0
 
311
        last_b_idx = 0
 
312
        yielded_a = False
 
313
        for base_idx, b_idx, match_len in matches:
 
314
            conflict_z_len = base_idx - last_base_idx
 
315
            conflict_b_len = b_idx - last_b_idx
 
316
            if conflict_b_len == 0: # There are no lines in b which conflict,
 
317
                                    # so skip it
 
318
                pass
 
319
            else:
 
320
                if yielded_a:
 
321
                    yield ('conflict',
 
322
                           zstart + last_base_idx, zstart + base_idx,
 
323
                           aend, aend, bstart + last_b_idx, bstart + b_idx)
 
324
                else:
 
325
                    # The first conflict gets the a-range
 
326
                    yielded_a = True
 
327
                    yield ('conflict', zstart + last_base_idx, zstart +
 
328
                    base_idx,
 
329
                           astart, aend, bstart + last_b_idx, bstart + b_idx)
 
330
            last_base_idx = base_idx + match_len
 
331
            last_b_idx = b_idx + match_len
 
332
        if last_base_idx != zend - zstart or last_b_idx != bend - bstart:
 
333
            if yielded_a:
 
334
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
 
335
                       aend, aend, bstart + last_b_idx, bstart + b_idx)
 
336
            else:
 
337
                # The first conflict gets the a-range
 
338
                yielded_a = True
 
339
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
 
340
                       astart, aend, bstart + last_b_idx, bstart + b_idx)
 
341
        if not yielded_a:
 
342
            yield ('conflict', zstart, zend, astart, aend, bstart, bend)
 
343
 
 
344
    def reprocess_merge_regions(self, merge_regions):
 
345
        """Where there are conflict regions, remove the agreed lines.
 
346
 
 
347
        Lines where both A and B have made the same changes are
 
348
        eliminated.
 
349
        """
 
350
        for region in merge_regions:
 
351
            if region[0] != "conflict":
 
352
                yield region
 
353
                continue
 
354
            type, iz, zmatch, ia, amatch, ib, bmatch = region
 
355
            a_region = self.a[ia:amatch]
 
356
            b_region = self.b[ib:bmatch]
 
357
            matches = patiencediff.PatienceSequenceMatcher(
 
358
                    None, a_region, b_region).get_matching_blocks()
 
359
            next_a = ia
 
360
            next_b = ib
 
361
            for region_ia, region_ib, region_len in matches[:-1]:
 
362
                region_ia += ia
 
363
                region_ib += ib
 
364
                reg = self.mismatch_region(next_a, region_ia, next_b,
 
365
                                           region_ib)
 
366
                if reg is not None:
 
367
                    yield reg
 
368
                yield 'same', region_ia, region_len+region_ia
 
369
                next_a = region_ia + region_len
 
370
                next_b = region_ib + region_len
 
371
            reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
 
372
            if reg is not None:
 
373
                yield reg
 
374
 
 
375
    @staticmethod
 
376
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
 
377
        if next_a < region_ia or next_b < region_ib:
 
378
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
379
 
 
380
    def find_sync_regions(self):
 
381
        """Return a list of sync regions, where both descendents match the base.
 
382
 
 
383
        Generates a list of (base1, base2, a1, a2, b1, b2).  There is
 
384
        always a zero-length sync region at the end of all the files.
 
385
        """
 
386
 
 
387
        ia = ib = 0
 
388
        amatches = patiencediff.PatienceSequenceMatcher(
 
389
                None, self.base, self.a).get_matching_blocks()
 
390
        bmatches = patiencediff.PatienceSequenceMatcher(
 
391
                None, self.base, self.b).get_matching_blocks()
 
392
        len_a = len(amatches)
 
393
        len_b = len(bmatches)
 
394
 
 
395
        sl = []
 
396
 
 
397
        while ia < len_a and ib < len_b:
 
398
            abase, amatch, alen = amatches[ia]
 
399
            bbase, bmatch, blen = bmatches[ib]
 
400
 
 
401
            # there is an unconflicted block at i; how long does it
 
402
            # extend?  until whichever one ends earlier.
 
403
            i = intersect((abase, abase+alen), (bbase, bbase+blen))
 
404
            if i:
 
405
                intbase = i[0]
 
406
                intend = i[1]
 
407
                intlen = intend - intbase
 
408
 
 
409
                # found a match of base[i[0], i[1]]; this may be less than
 
410
                # the region that matches in either one
 
411
                # assert intlen <= alen
 
412
                # assert intlen <= blen
 
413
                # assert abase <= intbase
 
414
                # assert bbase <= intbase
 
415
 
 
416
                asub = amatch + (intbase - abase)
 
417
                bsub = bmatch + (intbase - bbase)
 
418
                aend = asub + intlen
 
419
                bend = bsub + intlen
 
420
 
 
421
                # assert self.base[intbase:intend] == self.a[asub:aend], \
 
422
                #       (self.base[intbase:intend], self.a[asub:aend])
 
423
                # assert self.base[intbase:intend] == self.b[bsub:bend]
 
424
 
 
425
                sl.append((intbase, intend,
 
426
                           asub, aend,
 
427
                           bsub, bend))
 
428
            # advance whichever one ends first in the base text
 
429
            if (abase + alen) < (bbase + blen):
 
430
                ia += 1
 
431
            else:
 
432
                ib += 1
 
433
 
 
434
        intbase = len(self.base)
 
435
        abase = len(self.a)
 
436
        bbase = len(self.b)
 
437
        sl.append((intbase, intbase, abase, abase, bbase, bbase))
 
438
 
 
439
        return sl
 
440
 
 
441
    def find_unconflicted(self):
 
442
        """Return a list of ranges in base that are not conflicted."""
 
443
        am = patiencediff.PatienceSequenceMatcher(
 
444
                None, self.base, self.a).get_matching_blocks()
 
445
        bm = patiencediff.PatienceSequenceMatcher(
 
446
                None, self.base, self.b).get_matching_blocks()
 
447
 
 
448
        unc = []
 
449
 
 
450
        while am and bm:
 
451
            # there is an unconflicted block at i; how long does it
 
452
            # extend?  until whichever one ends earlier.
 
453
            a1 = am[0][0]
 
454
            a2 = a1 + am[0][2]
 
455
            b1 = bm[0][0]
 
456
            b2 = b1 + bm[0][2]
 
457
            i = intersect((a1, a2), (b1, b2))
 
458
            if i:
 
459
                unc.append(i)
 
460
 
 
461
            if a2 < b2:
 
462
                del am[0]
 
463
            else:
 
464
                del bm[0]
 
465
 
 
466
        return unc
 
467
 
 
468
 
 
469
def main(argv):
 
470
    # as for diff3 and meld the syntax is "MINE BASE OTHER"
 
471
    with open(argv[1], 'rt') as f:
 
472
        a = f.readlines()
 
473
    with open(argv[2], 'rt') as f:
 
474
        base = f.readlines()
 
475
    with open(argv[3], 'rt') as f:
 
476
        b = f.readlines()
 
477
 
 
478
    m3 = Merge3(base, a, b)
 
479
 
 
480
    #for sr in m3.find_sync_regions():
 
481
    #    print sr
 
482
 
 
483
    # sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
 
484
    sys.stdout.writelines(m3.merge_annotated())
 
485
 
 
486
 
 
487
if __name__ == '__main__':
 
488
    import sys
 
489
    sys.exit(main(sys.argv))