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

  • Committer: wang
  • Date: 2006-10-29 13:41:32 UTC
  • mto: (2104.4.1 wang_65714)
  • mto: This revision was merged to the branch mainline in revision 2109.
  • Revision ID: wang@ubuntu-20061029134132-3d7f4216f20c4aef
Replace python's difflib by patiencediff because the worst case 
performance is cubic for difflib and people commiting large data 
files are often hurt by this. The worst case performance of patience is 
quadratic. Fix bug 65714.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
1
 
# Copyright (C) 2004, 2005 by Canonical Ltd
2
 
 
 
1
# Copyright (C) 2004, 2005 Canonical Ltd
 
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
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
 
 
7
#
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
12
 
 
 
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19
19
# s: "i hate that."
20
20
 
21
21
 
 
22
from bzrlib.errors import CantReprocessAndShowBase
 
23
import bzrlib.patiencediff
 
24
from bzrlib.textfile import check_text_lines
 
25
 
22
26
 
23
27
def intersect(ra, rb):
24
28
    """Given two ranges return the range where they intersect or None.
64
68
    incorporating the changes from both BASE->OTHER and BASE->THIS.
65
69
    All three will typically be sequences of lines."""
66
70
    def __init__(self, base, a, b):
 
71
        check_text_lines(base)
 
72
        check_text_lines(a)
 
73
        check_text_lines(b)
67
74
        self.base = base
68
75
        self.a = a
69
76
        self.b = b
70
 
        from difflib import SequenceMatcher
71
 
        self.a_ops = SequenceMatcher(None, base, a).get_opcodes()
72
 
        self.b_ops = SequenceMatcher(None, base, b).get_opcodes()
73
77
 
74
78
 
75
79
 
76
80
    def merge_lines(self,
77
81
                    name_a=None,
78
82
                    name_b=None,
79
 
                    start_marker='<<<<<<<<',
80
 
                    mid_marker='========',
81
 
                    end_marker='>>>>>>>>',
82
 
                    show_base=False):
 
83
                    name_base=None,
 
84
                    start_marker='<<<<<<<',
 
85
                    mid_marker='=======',
 
86
                    end_marker='>>>>>>>',
 
87
                    base_marker=None,
 
88
                    reprocess=False):
83
89
        """Return merge in cvs-like form.
84
90
        """
 
91
        if base_marker and reprocess:
 
92
            raise CantReprocessAndShowBase()
85
93
        if name_a:
86
94
            start_marker = start_marker + ' ' + name_a
87
95
        if name_b:
88
96
            end_marker = end_marker + ' ' + name_b
89
 
            
90
 
        for t in self.merge_regions():
 
97
        if name_base and base_marker:
 
98
            base_marker = base_marker + ' ' + name_base
 
99
        merge_regions = self.merge_regions()
 
100
        if reprocess is True:
 
101
            merge_regions = self.reprocess_merge_regions(merge_regions)
 
102
        for t in merge_regions:
91
103
            what = t[0]
92
104
            if what == 'unchanged':
93
105
                for i in range(t[1], t[2]):
102
114
                yield start_marker + '\n'
103
115
                for i in range(t[3], t[4]):
104
116
                    yield self.a[i]
 
117
                if base_marker is not None:
 
118
                    yield base_marker + '\n'
 
119
                    for i in range(t[1], t[2]):
 
120
                        yield self.base[i]
105
121
                yield mid_marker + '\n'
106
122
                for i in range(t[5], t[6]):
107
123
                    yield self.b[i]
263
279
                iz = zend
264
280
                ia = aend
265
281
                ib = bend
266
 
        
267
 
 
268
 
        
 
282
    
 
283
 
 
284
    def reprocess_merge_regions(self, merge_regions):
 
285
        """Where there are conflict regions, remove the agreed lines.
 
286
 
 
287
        Lines where both A and B have made the same changes are 
 
288
        eliminated.
 
289
        """
 
290
        for region in merge_regions:
 
291
            if region[0] != "conflict":
 
292
                yield region
 
293
                continue
 
294
            type, iz, zmatch, ia, amatch, ib, bmatch = region
 
295
            a_region = self.a[ia:amatch]
 
296
            b_region = self.b[ib:bmatch]
 
297
            matches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
298
                    None, a_region, b_region).get_matching_blocks()
 
299
            next_a = ia
 
300
            next_b = ib
 
301
            for region_ia, region_ib, region_len in matches[:-1]:
 
302
                region_ia += ia
 
303
                region_ib += ib
 
304
                reg = self.mismatch_region(next_a, region_ia, next_b,
 
305
                                           region_ib)
 
306
                if reg is not None:
 
307
                    yield reg
 
308
                yield 'same', region_ia, region_len+region_ia
 
309
                next_a = region_ia + region_len
 
310
                next_b = region_ib + region_len
 
311
            reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
 
312
            if reg is not None:
 
313
                yield reg
 
314
 
 
315
 
 
316
    @staticmethod
 
317
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
 
318
        if next_a < region_ia or next_b < region_ib:
 
319
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
320
            
 
321
 
269
322
    def find_sync_regions(self):
270
323
        """Return a list of sync regions, where both descendents match the base.
271
324
 
272
325
        Generates a list of (base1, base2, a1, a2, b1, b2).  There is
273
326
        always a zero-length sync region at the end of all the files.
274
327
        """
275
 
        from difflib import SequenceMatcher
276
328
 
277
329
        ia = ib = 0
278
 
        amatches = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
279
 
        bmatches = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
 
330
        amatches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
331
                None, self.base, self.a).get_matching_blocks()
 
332
        bmatches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
333
                None, self.base, self.b).get_matching_blocks()
280
334
        len_a = len(amatches)
281
335
        len_b = len(bmatches)
282
336
 
332
386
 
333
387
    def find_unconflicted(self):
334
388
        """Return a list of ranges in base that are not conflicted."""
335
 
        from difflib import SequenceMatcher
336
 
 
337
 
        import re
338
 
 
339
 
        # don't sync-up on lines containing only blanks or pounds
340
 
        junk_re = re.compile(r'^[ \t#]*$')
341
 
        
342
 
        am = SequenceMatcher(junk_re.match, self.base, self.a).get_matching_blocks()
343
 
        bm = SequenceMatcher(junk_re.match, self.base, self.b).get_matching_blocks()
 
389
        am = bzrlib.patiencediff.PatienceSequenceMatcher(
 
390
                None, self.base, self.a).get_matching_blocks()
 
391
        bm = bzrlib.patiencediff.PatienceSequenceMatcher(
 
392
                None, self.base, self.b).get_matching_blocks()
344
393
 
345
394
        unc = []
346
395