/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: Gustav Hartvigsson
  • Date: 2021-01-09 21:36:27 UTC
  • Revision ID: gustav.hartvigsson@gmail.com-20210109213627-h1xwcutzy9m7a99b
Added 'Case Preserving Working Tree Use Cases' from Canonical Wiki

* Addod a page from the Canonical Bazaar wiki
  with information on the scmeatics of case
  perserving filesystems an a case insensitive
  filesystem works.
  
  * Needs re-work, but this will do as it is the
    same inforamoton as what was on the linked
    page in the currint documentation.

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
# mbp: "you know that thing where cvs gives you conflict markers?"
 
18
# s: "i hate that."
 
19
 
 
20
import patiencediff
 
21
 
 
22
 
 
23
from . import (
 
24
    errors,
 
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
            # invariants:
 
252
            # assert len_a >= 0
 
253
            # assert len_b >= 0
 
254
 
 
255
            # print 'unmatched a=%d, b=%d' % (len_a, len_b)
 
256
 
 
257
            if len_a or len_b:
 
258
                # try to avoid actually slicing the lists
 
259
                same = compare_range(self.a, ia, amatch,
 
260
                                     self.b, ib, bmatch)
 
261
 
 
262
                if same:
 
263
                    yield 'same', ia, amatch
 
264
                else:
 
265
                    equal_a = compare_range(self.a, ia, amatch,
 
266
                                            self.base, iz, zmatch)
 
267
                    equal_b = compare_range(self.b, ib, bmatch,
 
268
                                            self.base, iz, zmatch)
 
269
                    if equal_a and not equal_b:
 
270
                        yield 'b', ib, bmatch
 
271
                    elif equal_b and not equal_a:
 
272
                        yield 'a', ia, amatch
 
273
                    elif not equal_a and not equal_b:
 
274
                        if self.is_cherrypick:
 
275
                            for node in self._refine_cherrypick_conflict(
 
276
                                    iz, zmatch, ia, amatch,
 
277
                                    ib, bmatch):
 
278
                                yield node
 
279
                        else:
 
280
                            yield ('conflict', iz, zmatch, ia, amatch, ib,
 
281
                                   bmatch)
 
282
                    else:
 
283
                        raise AssertionError(
 
284
                            "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,
 
305
                                    bend):
 
306
        """When cherrypicking b => a, ignore matches with b and base."""
 
307
        # Do not emit regions which match, only regions which do not match
 
308
        matches = patiencediff.PatienceSequenceMatcher(
 
309
            None, self.base[zstart:zend], self.b[bstart:bend]
 
310
            ).get_matching_blocks()
 
311
        last_base_idx = 0
 
312
        last_b_idx = 0
 
313
        last_b_idx = 0
 
314
        yielded_a = False
 
315
        for base_idx, b_idx, match_len in matches:
 
316
            conflict_b_len = b_idx - last_b_idx
 
317
            if conflict_b_len == 0:
 
318
                # There are no lines in b which conflict, so skip it
 
319
                pass
 
320
            else:
 
321
                if yielded_a:
 
322
                    yield ('conflict',
 
323
                           zstart + last_base_idx, zstart + base_idx,
 
324
                           aend, aend, bstart + last_b_idx, bstart + b_idx)
 
325
                else:
 
326
                    # The first conflict gets the a-range
 
327
                    yielded_a = True
 
328
                    yield ('conflict', zstart + last_base_idx, zstart +
 
329
                           base_idx,
 
330
                           astart, aend, bstart + last_b_idx, bstart + b_idx)
 
331
            last_base_idx = base_idx + match_len
 
332
            last_b_idx = b_idx + match_len
 
333
        if last_base_idx != zend - zstart or last_b_idx != bend - bstart:
 
334
            if yielded_a:
 
335
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
 
336
                       aend, aend, bstart + last_b_idx, bstart + b_idx)
 
337
            else:
 
338
                # The first conflict gets the a-range
 
339
                yielded_a = True
 
340
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
 
341
                       astart, aend, bstart + last_b_idx, bstart + b_idx)
 
342
        if not yielded_a:
 
343
            yield ('conflict', zstart, zend, astart, aend, bstart, bend)
 
344
 
 
345
    def reprocess_merge_regions(self, merge_regions):
 
346
        """Where there are conflict regions, remove the agreed lines.
 
347
 
 
348
        Lines where both A and B have made the same changes are
 
349
        eliminated.
 
350
        """
 
351
        for region in merge_regions:
 
352
            if region[0] != "conflict":
 
353
                yield region
 
354
                continue
 
355
            type, iz, zmatch, ia, amatch, ib, bmatch = region
 
356
            a_region = self.a[ia:amatch]
 
357
            b_region = self.b[ib:bmatch]
 
358
            matches = patiencediff.PatienceSequenceMatcher(
 
359
                None, a_region, b_region).get_matching_blocks()
 
360
            next_a = ia
 
361
            next_b = ib
 
362
            for region_ia, region_ib, region_len in matches[:-1]:
 
363
                region_ia += ia
 
364
                region_ib += ib
 
365
                reg = self.mismatch_region(next_a, region_ia, next_b,
 
366
                                           region_ib)
 
367
                if reg is not None:
 
368
                    yield reg
 
369
                yield 'same', region_ia, region_len + region_ia
 
370
                next_a = region_ia + region_len
 
371
                next_b = region_ib + region_len
 
372
            reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
 
373
            if reg is not None:
 
374
                yield reg
 
375
 
 
376
    @staticmethod
 
377
    def mismatch_region(next_a, region_ia, next_b, region_ib):
 
378
        if next_a < region_ia or next_b < region_ib:
 
379
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
380
 
 
381
    def find_sync_regions(self):
 
382
        """Return a list of sync regions, where both descendents match the base.
 
383
 
 
384
        Generates a list of (base1, base2, a1, a2, b1, b2).  There is
 
385
        always a zero-length sync region at the end of all the files.
 
386
        """
 
387
 
 
388
        ia = ib = 0
 
389
        amatches = patiencediff.PatienceSequenceMatcher(
 
390
            None, self.base, self.a).get_matching_blocks()
 
391
        bmatches = patiencediff.PatienceSequenceMatcher(
 
392
            None, self.base, self.b).get_matching_blocks()
 
393
        len_a = len(amatches)
 
394
        len_b = len(bmatches)
 
395
 
 
396
        sl = []
 
397
 
 
398
        while ia < len_a and ib < len_b:
 
399
            abase, amatch, alen = amatches[ia]
 
400
            bbase, bmatch, blen = bmatches[ib]
 
401
 
 
402
            # there is an unconflicted block at i; how long does it
 
403
            # extend?  until whichever one ends earlier.
 
404
            i = intersect((abase, abase + alen), (bbase, bbase + blen))
 
405
            if i:
 
406
                intbase = i[0]
 
407
                intend = i[1]
 
408
                intlen = intend - intbase
 
409
 
 
410
                # found a match of base[i[0], i[1]]; this may be less than
 
411
                # the region that matches in either one
 
412
                # assert intlen <= alen
 
413
                # assert intlen <= blen
 
414
                # assert abase <= intbase
 
415
                # assert bbase <= intbase
 
416
 
 
417
                asub = amatch + (intbase - abase)
 
418
                bsub = bmatch + (intbase - bbase)
 
419
                aend = asub + intlen
 
420
                bend = bsub + intlen
 
421
 
 
422
                # assert self.base[intbase:intend] == self.a[asub:aend], \
 
423
                #       (self.base[intbase:intend], self.a[asub:aend])
 
424
                # assert self.base[intbase:intend] == self.b[bsub:bend]
 
425
 
 
426
                sl.append((intbase, intend,
 
427
                           asub, aend,
 
428
                           bsub, bend))
 
429
            # advance whichever one ends first in the base text
 
430
            if (abase + alen) < (bbase + blen):
 
431
                ia += 1
 
432
            else:
 
433
                ib += 1
 
434
 
 
435
        intbase = len(self.base)
 
436
        abase = len(self.a)
 
437
        bbase = len(self.b)
 
438
        sl.append((intbase, intbase, abase, abase, bbase, bbase))
 
439
 
 
440
        return sl
 
441
 
 
442
    def find_unconflicted(self):
 
443
        """Return a list of ranges in base that are not conflicted."""
 
444
        am = patiencediff.PatienceSequenceMatcher(
 
445
            None, self.base, self.a).get_matching_blocks()
 
446
        bm = patiencediff.PatienceSequenceMatcher(
 
447
            None, self.base, self.b).get_matching_blocks()
 
448
 
 
449
        unc = []
 
450
 
 
451
        while am and bm:
 
452
            # there is an unconflicted block at i; how long does it
 
453
            # extend?  until whichever one ends earlier.
 
454
            a1 = am[0][0]
 
455
            a2 = a1 + am[0][2]
 
456
            b1 = bm[0][0]
 
457
            b2 = b1 + bm[0][2]
 
458
            i = intersect((a1, a2), (b1, b2))
 
459
            if i:
 
460
                unc.append(i)
 
461
 
 
462
            if a2 < b2:
 
463
                del am[0]
 
464
            else:
 
465
                del bm[0]
 
466
 
 
467
        return unc
 
468
 
 
469
 
 
470
def main(argv):
 
471
    # as for diff3 and meld the syntax is "MINE BASE OTHER"
 
472
    with open(argv[1], 'rt') as f:
 
473
        a = f.readlines()
 
474
    with open(argv[2], 'rt') as f:
 
475
        base = f.readlines()
 
476
    with open(argv[3], 'rt') as f:
 
477
        b = f.readlines()
 
478
 
 
479
    m3 = Merge3(base, a, b)
 
480
 
 
481
    # for sr in m3.find_sync_regions():
 
482
    #    print sr
 
483
 
 
484
    # sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
 
485
    sys.stdout.writelines(m3.merge_annotated())
 
486
 
 
487
 
 
488
if __name__ == '__main__':
 
489
    import sys
 
490
    sys.exit(main(sys.argv))