1 # Copyright (C) 2004, 2005 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    16 

    17 # mbp: "you know that thing where cvs gives you conflict markers?"

    18 # s: "i hate that."

    19 

    20 from i18n import _

    21 import util, mdiff

    22 import sys, os

    23 

    24 class CantReprocessAndShowBase(Exception):

    25     pass

    26 

    27 def intersect(ra, rb):

    28     """Given two ranges return the range where they intersect or None.

    29 

    30     >>> intersect((0, 10), (0, 6))

    31     (0, 6)

    32     >>> intersect((0, 10), (5, 15))

    33     (5, 10)

    34     >>> intersect((0, 10), (10, 15))

    35     >>> intersect((0, 9), (10, 15))

    36     >>> intersect((0, 9), (7, 15))

    37     (7, 9)

    38     """

    39     assert ra[0] <= ra[1]

    40     assert rb[0] <= rb[1]

    41 

    42     sa = max(ra[0], rb[0])

    43     sb = min(ra[1], rb[1])

    44     if sa < sb:

    45         return sa, sb

    46     else:

    47         return None

    48 

    49 def compare_range(a, astart, aend, b, bstart, bend):

    50     """Compare a[astart:aend] == b[bstart:bend], without slicing.

    51     """

    52     if (aend - astart) != (bend - bstart):

    53         return False

    54     for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)):

    55         if a[ia] != b[ib]:

    56             return False

    57     else:

    58         return True

    59 

    60 class Merge3Text(object):

    61     """3-way merge of texts.

    62 

    63     Given strings BASE, OTHER, THIS, tries to produce a combined text

    64     incorporating the changes from both BASE->OTHER and BASE->THIS."""

    65     def __init__(self, basetext, atext, btext, base=None, a=None, b=None):

    66         self.basetext = basetext

    67         self.atext = atext

    68         self.btext = btext

    69         if base is None:

    70             base = mdiff.splitnewlines(basetext)

    71         if a is None:

    72             a = mdiff.splitnewlines(atext)

    73         if b is None:

    74             b = mdiff.splitnewlines(btext)

    75         self.base = base

    76         self.a = a

    77         self.b = b

    78 

    79     def merge_lines(self,

    80                     name_a=None,

    81                     name_b=None,

    82                     name_base=None,

    83                     start_marker='<<<<<<<',

    84                     mid_marker='=======',

    85                     end_marker='>>>>>>>',

    86                     base_marker=None,

    87                     reprocess=False):

    88         """Return merge in cvs-like form.

    89         """

    90         self.conflicts = False

    91         newline = '\n'

    92         if len(self.a) > 0:

    93             if self.a[0].endswith('\r\n'):

    94                 newline = '\r\n'

    95             elif self.a[0].endswith('\r'):

    96                 newline = '\r'

    97         if base_marker and reprocess:

    98             raise CantReprocessAndShowBase()

    99         if name_a:

   100             start_marker = start_marker + ' ' + name_a

   101         if name_b:

   102             end_marker = end_marker + ' ' + name_b

   103         if name_base and base_marker:

   104             base_marker = base_marker + ' ' + name_base

   105         merge_regions = self.merge_regions()

   106         if reprocess is True:

   107             merge_regions = self.reprocess_merge_regions(merge_regions)

   108         for t in merge_regions:

   109             what = t[0]

   110             if what == 'unchanged':

   111                 for i in range(t[1], t[2]):

   112                     yield self.base[i]

   113             elif what == 'a' or what == 'same':

   114                 for i in range(t[1], t[2]):

   115                     yield self.a[i]

   116             elif what == 'b':

   117                 for i in range(t[1], t[2]):

   118                     yield self.b[i]

   119             elif what == 'conflict':

   120                 self.conflicts = True

   121                 yield start_marker + newline

   122                 for i in range(t[3], t[4]):

   123                     yield self.a[i]

   124                 if base_marker is not None:

   125                     yield base_marker + newline

   126                     for i in range(t[1], t[2]):

   127                         yield self.base[i]

   128                 yield mid_marker + newline

   129                 for i in range(t[5], t[6]):

   130                     yield self.b[i]

   131                 yield end_marker + newline

   132             else:

   133                 raise ValueError(what)

   134 

   135     def merge_annotated(self):

   136         """Return merge with conflicts, showing origin of lines.

   137 

   138         Most useful for debugging merge.

   139         """

   140         for t in self.merge_regions():

   141             what = t[0]

   142             if what == 'unchanged':

   143                 for i in range(t[1], t[2]):

   144                     yield 'u | ' + self.base[i]

   145             elif what == 'a' or what == 'same':

   146                 for i in range(t[1], t[2]):

   147                     yield what[0] + ' | ' + self.a[i]

   148             elif what == 'b':

   149                 for i in range(t[1], t[2]):

   150                     yield 'b | ' + self.b[i]

   151             elif what == 'conflict':

   152                 yield '<<<<\n'

   153                 for i in range(t[3], t[4]):

   154                     yield 'A | ' + self.a[i]

   155                 yield '----\n'

   156                 for i in range(t[5], t[6]):

   157                     yield 'B | ' + self.b[i]

   158                 yield '>>>>\n'

   159             else:

   160                 raise ValueError(what)

   161 

   162     def merge_groups(self):

   163         """Yield sequence of line groups.  Each one is a tuple:

   164 

   165         'unchanged', lines

   166              Lines unchanged from base

   167 

   168         'a', lines

   169              Lines taken from a

   170 

   171         'same', lines

   172              Lines taken from a (and equal to b)

   173 

   174         'b', lines

   175              Lines taken from b

   176 

   177         'conflict', base_lines, a_lines, b_lines

   178              Lines from base were changed to either a or b and conflict.

   179         """

   180         for t in self.merge_regions():

   181             what = t[0]

   182             if what == 'unchanged':

   183                 yield what, self.base[t[1]:t[2]]

   184             elif what == 'a' or what == 'same':

   185                 yield what, self.a[t[1]:t[2]]

   186             elif what == 'b':

   187                 yield what, self.b[t[1]:t[2]]

   188             elif what == 'conflict':

   189                 yield (what,

   190                        self.base[t[1]:t[2]],

   191                        self.a[t[3]:t[4]],

   192                        self.b[t[5]:t[6]])

   193             else:

   194                 raise ValueError(what)

   195 

   196     def merge_regions(self):

   197         """Return sequences of matching and conflicting regions.

   198 

   199         This returns tuples, where the first value says what kind we

   200         have:

   201 

   202         'unchanged', start, end

   203              Take a region of base[start:end]

   204 

   205         'same', astart, aend

   206              b and a are different from base but give the same result

   207 

   208         'a', start, end

   209              Non-clashing insertion from a[start:end]

   210 

   211         Method is as follows:

   212 

   213         The two sequences align only on regions which match the base

   214         and both descendents.  These are found by doing a two-way diff

   215         of each one against the base, and then finding the

   216         intersections between those regions.  These "sync regions"

   217         are by definition unchanged in both and easily dealt with.

   218 

   219         The regions in between can be in any of three cases:

   220         conflicted, or changed on only one side.

   221         """

   222 

   223         # section a[0:ia] has been disposed of, etc

   224         iz = ia = ib = 0

   225 

   226         for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():

   227             #print 'match base [%d:%d]' % (zmatch, zend)

   228 

   229             matchlen = zend - zmatch

   230             assert matchlen >= 0

   231             assert matchlen == (aend - amatch)

   232             assert matchlen == (bend - bmatch)

   233 

   234             len_a = amatch - ia

   235             len_b = bmatch - ib

   236             len_base = zmatch - iz

   237             assert len_a >= 0

   238             assert len_b >= 0

   239             assert len_base >= 0

   240 

   241             #print 'unmatched a=%d, b=%d' % (len_a, len_b)

   242 

   243             if len_a or len_b:

   244                 # try to avoid actually slicing the lists

   245                 equal_a = compare_range(self.a, ia, amatch,

   246                                         self.base, iz, zmatch)

   247                 equal_b = compare_range(self.b, ib, bmatch,

   248                                         self.base, iz, zmatch)

   249                 same = compare_range(self.a, ia, amatch,

   250                                      self.b, ib, bmatch)

   251 

   252                 if same:

   253                     yield 'same', ia, amatch

   254                 elif equal_a and not equal_b:

   255                     yield 'b', ib, bmatch

   256                 elif equal_b and not equal_a:

   257                     yield 'a', ia, amatch

   258                 elif not equal_a and not equal_b:

   259                     yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch

   260                 else:

   261                     raise AssertionError("can't handle a=b=base but unmatched")

   262 

   263                 ia = amatch

   264                 ib = bmatch

   265             iz = zmatch

   266 

   267             # if the same part of the base was deleted on both sides

   268             # that's OK, we can just skip it.

   269 

   270 

   271             if matchlen > 0:

   272                 assert ia == amatch

   273                 assert ib == bmatch

   274                 assert iz == zmatch

   275 

   276                 yield 'unchanged', zmatch, zend

   277                 iz = zend

   278                 ia = aend

   279                 ib = bend

   280 

   281     def reprocess_merge_regions(self, merge_regions):

   282         """Where there are conflict regions, remove the agreed lines.

   283 

   284         Lines where both A and B have made the same changes are

   285         eliminated.

   286         """

   287         for region in merge_regions:

   288             if region[0] != "conflict":

   289                 yield region

   290                 continue

   291             type, iz, zmatch, ia, amatch, ib, bmatch = region

   292             a_region = self.a[ia:amatch]

   293             b_region = self.b[ib:bmatch]

   294             matches = mdiff.get_matching_blocks(''.join(a_region),

   295                                                 ''.join(b_region))

   296             next_a = ia

   297             next_b = ib

   298             for region_ia, region_ib, region_len in matches[:-1]:

   299                 region_ia += ia

   300                 region_ib += ib

   301                 reg = self.mismatch_region(next_a, region_ia, next_b,

   302                                            region_ib)

   303                 if reg is not None:

   304                     yield reg

   305                 yield 'same', region_ia, region_len + region_ia

   306                 next_a = region_ia + region_len

   307                 next_b = region_ib + region_len

   308             reg = self.mismatch_region(next_a, amatch, next_b, bmatch)

   309             if reg is not None:

   310                 yield reg

   311 

   312     def mismatch_region(next_a, region_ia,  next_b, region_ib):

   313         if next_a < region_ia or next_b < region_ib:

   314             return 'conflict', None, None, next_a, region_ia, next_b, region_ib

   315     mismatch_region = staticmethod(mismatch_region)

   316 

   317     def find_sync_regions(self):

   318         """Return a list of sync regions, where both descendents match the base.

   319 

   320         Generates a list of (base1, base2, a1, a2, b1, b2).  There is

   321         always a zero-length sync region at the end of all the files.

   322         """

   323 

   324         ia = ib = 0

   325         amatches = mdiff.get_matching_blocks(self.basetext, self.atext)

   326         bmatches = mdiff.get_matching_blocks(self.basetext, self.btext)

   327         len_a = len(amatches)

   328         len_b = len(bmatches)

   329 

   330         sl = []

   331 

   332         while ia < len_a and ib < len_b:

   333             abase, amatch, alen = amatches[ia]

   334             bbase, bmatch, blen = bmatches[ib]

   335 

   336             # there is an unconflicted block at i; how long does it

   337             # extend?  until whichever one ends earlier.

   338             i = intersect((abase, abase + alen), (bbase, bbase + blen))

   339             if i:

   340                 intbase = i[0]

   341                 intend = i[1]

   342                 intlen = intend - intbase

   343 

   344                 # found a match of base[i[0], i[1]]; this may be less than

   345                 # the region that matches in either one

   346                 assert intlen <= alen

   347                 assert intlen <= blen

   348                 assert abase <= intbase

   349                 assert bbase <= intbase

   350 

   351                 asub = amatch + (intbase - abase)

   352                 bsub = bmatch + (intbase - bbase)

   353                 aend = asub + intlen

   354                 bend = bsub + intlen

   355 

   356                 assert self.base[intbase:intend] == self.a[asub:aend], \

   357                        (self.base[intbase:intend], self.a[asub:aend])

   358 

   359                 assert self.base[intbase:intend] == self.b[bsub:bend]

   360 

   361                 sl.append((intbase, intend,

   362                            asub, aend,

   363                            bsub, bend))

   364 

   365             # advance whichever one ends first in the base text

   366             if (abase + alen) < (bbase + blen):

   367                 ia += 1

   368             else:

   369                 ib += 1

   370 

   371         intbase = len(self.base)

   372         abase = len(self.a)

   373         bbase = len(self.b)

   374         sl.append((intbase, intbase, abase, abase, bbase, bbase))

   375 

   376         return sl

   377 

   378     def find_unconflicted(self):

   379         """Return a list of ranges in base that are not conflicted."""

   380         am = mdiff.get_matching_blocks(self.basetext, self.atext)

   381         bm = mdiff.get_matching_blocks(self.basetext, self.btext)

   382 

   383         unc = []

   384 

   385         while am and bm:

   386             # there is an unconflicted block at i; how long does it

   387             # extend?  until whichever one ends earlier.

   388             a1 = am[0][0]

   389             a2 = a1 + am[0][2]

   390             b1 = bm[0][0]

   391             b2 = b1 + bm[0][2]

   392             i = intersect((a1, a2), (b1, b2))

   393             if i:

   394                 unc.append(i)

   395 

   396             if a2 < b2:

   397                 del am[0]

   398             else:

   399                 del bm[0]

   400 

   401         return unc

   402 

   403 def simplemerge(ui, local, base, other, **opts):

   404     def readfile(filename):

   405         f = open(filename, "rb")

   406         text = f.read()

   407         f.close()

   408         if util.binary(text):

   409             msg = _("%s looks like a binary file.") % filename

   410             if not opts.get('text'):

   411                 raise util.Abort(msg)

   412             elif not opts.get('quiet'):

   413                 ui.warn(_('warning: %s\n') % msg)

   414         return text

   415 

   416     name_a = local

   417     name_b = other

   418     labels = opts.get('label', [])

   419     if labels:

   420         name_a = labels.pop(0)

   421     if labels:

   422         name_b = labels.pop(0)

   423     if labels:

   424         raise util.Abort(_("can only specify two labels."))

   425 

   426     localtext = readfile(local)

   427     basetext = readfile(base)

   428     othertext = readfile(other)

   429 

   430     local = os.path.realpath(local)

   431     if not opts.get('print'):

   432         opener = util.opener(os.path.dirname(local))

   433         out = opener(os.path.basename(local), "w", atomictemp=True)

   434     else:

   435         out = sys.stdout

   436 

   437     reprocess = not opts.get('no_minimal')

   438 

   439     m3 = Merge3Text(basetext, localtext, othertext)

   440     for line in m3.merge_lines(name_a=name_a, name_b=name_b,

   441                                reprocess=reprocess):

   442         out.write(line)

   443 

   444     if not opts.get('print'):

   445         out.rename()

   446 

   447     if m3.conflicts:

   448         if not opts.get('quiet'):

   449             ui.warn(_("warning: conflicts during merge.\n"))

   450         return 1