sys/lib/python/mercurial/simplemerge.py

   1 #!/usr/bin/env python
   2 # Copyright (C) 2004, 2005 Canonical Ltd
   3 #
   4 # This program is free software; you can redistribute it and/or modify
   5 # it under the terms of the GNU General Public License as published by
   6 # the Free Software Foundation; either version 2 of the License, or
   7 # (at your option) any later version.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program; if not, write to the Free Software
  16 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17
  18 # mbp: "you know that thing where cvs gives you conflict markers?"
  19 # s: "i hate that."
  20
  21 from i18n import _
  22 import util, mdiff
  23 import sys, os
  24
  25 class CantReprocessAndShowBase(Exception):
  26     pass
  27
  28 def intersect(ra, rb):
  29     """Given two ranges return the range where they intersect or None.
  30
  31     >>> intersect((0, 10), (0, 6))
  32     (0, 6)
  33     >>> intersect((0, 10), (5, 15))
  34     (5, 10)
  35     >>> intersect((0, 10), (10, 15))
  36     >>> intersect((0, 9), (10, 15))
  37     >>> intersect((0, 9), (7, 15))
  38     (7, 9)
  39     """
  40     assert ra[0] <= ra[1]
  41     assert rb[0] <= rb[1]
  42
  43     sa = max(ra[0], rb[0])
  44     sb = min(ra[1], rb[1])
  45     if sa < sb:
  46         return sa, sb
  47     else:
  48         return None
  49
  50 def compare_range(a, astart, aend, b, bstart, bend):
  51     """Compare a[astart:aend] == b[bstart:bend], without slicing.
  52     """
  53     if (aend-astart) != (bend-bstart):
  54         return False
  55     for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)):
  56         if a[ia] != b[ib]:
  57             return False
  58     else:
  59         return True
  60
  61 class Merge3Text(object):
  62     """3-way merge of texts.
  63
  64     Given strings BASE, OTHER, THIS, tries to produce a combined text
  65     incorporating the changes from both BASE->OTHER and BASE->THIS."""
  66     def __init__(self, basetext, atext, btext, base=None, a=None, b=None):
  67         self.basetext = basetext
  68         self.atext = atext
  69         self.btext = btext
  70         if base is None:
  71             base = mdiff.splitnewlines(basetext)
  72         if a is None:
  73             a = mdiff.splitnewlines(atext)
  74         if b is None:
  75             b = mdiff.splitnewlines(btext)
  76         self.base = base
  77         self.a = a
  78         self.b = b
  79
  80     def merge_lines(self,
  81                     name_a=None,
  82                     name_b=None,
  83                     name_base=None,
  84                     start_marker='<<<<<<<',
  85                     mid_marker='=======',
  86                     end_marker='>>>>>>>',
  87                     base_marker=None,
  88                     reprocess=False):
  89         """Return merge in cvs-like form.
  90         """
  91         self.conflicts = False
  92         newline = '\n'
  93         if len(self.a) > 0:
  94             if self.a[0].endswith('\r\n'):
  95                 newline = '\r\n'
  96             elif self.a[0].endswith('\r'):
  97                 newline = '\r'
  98         if base_marker and reprocess:
  99             raise CantReprocessAndShowBase()
 100         if name_a:
 101             start_marker = start_marker + ' ' + name_a
 102         if name_b:
 103             end_marker = end_marker + ' ' + name_b
 104         if name_base and base_marker:
 105             base_marker = base_marker + ' ' + name_base
 106         merge_regions = self.merge_regions()
 107         if reprocess is True:
 108             merge_regions = self.reprocess_merge_regions(merge_regions)
 109         for t in merge_regions:
 110             what = t[0]
 111             if what == 'unchanged':
 112                 for i in range(t[1], t[2]):
 113                     yield self.base[i]
 114             elif what == 'a' or what == 'same':
 115                 for i in range(t[1], t[2]):
 116                     yield self.a[i]
 117             elif what == 'b':
 118                 for i in range(t[1], t[2]):
 119                     yield self.b[i]
 120             elif what == 'conflict':
 121                 self.conflicts = True
 122                 yield start_marker + newline
 123                 for i in range(t[3], t[4]):
 124                     yield self.a[i]
 125                 if base_marker is not None:
 126                     yield base_marker + newline
 127                     for i in range(t[1], t[2]):
 128                         yield self.base[i]
 129                 yield mid_marker + newline
 130                 for i in range(t[5], t[6]):
 131                     yield self.b[i]
 132                 yield end_marker + newline
 133             else:
 134                 raise ValueError(what)
 135
 136     def merge_annotated(self):
 137         """Return merge with conflicts, showing origin of lines.
 138
 139         Most useful for debugging merge.
 140         """
 141         for t in self.merge_regions():
 142             what = t[0]
 143             if what == 'unchanged':
 144                 for i in range(t[1], t[2]):
 145                     yield 'u | ' + self.base[i]
 146             elif what == 'a' or what == 'same':
 147                 for i in range(t[1], t[2]):
 148                     yield what[0] + ' | ' + self.a[i]
 149             elif what == 'b':
 150                 for i in range(t[1], t[2]):
 151                     yield 'b | ' + self.b[i]
 152             elif what == 'conflict':
 153                 yield '<<<<\n'
 154                 for i in range(t[3], t[4]):
 155                     yield 'A | ' + self.a[i]
 156                 yield '----\n'
 157                 for i in range(t[5], t[6]):
 158                     yield 'B | ' + self.b[i]
 159                 yield '>>>>\n'
 160             else:
 161                 raise ValueError(what)
 162
 163     def merge_groups(self):
 164         """Yield sequence of line groups.  Each one is a tuple:
 165
 166         'unchanged', lines
 167              Lines unchanged from base
 168
 169         'a', lines
 170              Lines taken from a
 171
 172         'same', lines
 173              Lines taken from a (and equal to b)
 174
 175         'b', lines
 176              Lines taken from b
 177
 178         'conflict', base_lines, a_lines, b_lines
 179              Lines from base were changed to either a or b and conflict.
 180         """
 181         for t in self.merge_regions():
 182             what = t[0]
 183             if what == 'unchanged':
 184                 yield what, self.base[t[1]:t[2]]
 185             elif what == 'a' or what == 'same':
 186                 yield what, self.a[t[1]:t[2]]
 187             elif what == 'b':
 188                 yield what, self.b[t[1]:t[2]]
 189             elif what == 'conflict':
 190                 yield (what,
 191                        self.base[t[1]:t[2]],
 192                        self.a[t[3]:t[4]],
 193                        self.b[t[5]:t[6]])
 194             else:
 195                 raise ValueError(what)
 196
 197     def merge_regions(self):
 198         """Return sequences of matching and conflicting regions.
 199
 200         This returns tuples, where the first value says what kind we
 201         have:
 202
 203         'unchanged', start, end
 204              Take a region of base[start:end]
 205
 206         'same', astart, aend
 207              b and a are different from base but give the same result
 208
 209         'a', start, end
 210              Non-clashing insertion from a[start:end]
 211
 212         Method is as follows:
 213
 214         The two sequences align only on regions which match the base
 215         and both descendents.  These are found by doing a two-way diff
 216         of each one against the base, and then finding the
 217         intersections between those regions.  These "sync regions"
 218         are by definition unchanged in both and easily dealt with.
 219
 220         The regions in between can be in any of three cases:
 221         conflicted, or changed on only one side.
 222         """
 223
 224         # section a[0:ia] has been disposed of, etc
 225         iz = ia = ib = 0
 226
 227         for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 228             #print 'match base [%d:%d]' % (zmatch, zend)
 229
 230             matchlen = zend - zmatch
 231             assert matchlen >= 0
 232             assert matchlen == (aend - amatch)
 233             assert matchlen == (bend - bmatch)
 234
 235             len_a = amatch - ia
 236             len_b = bmatch - ib
 237             len_base = zmatch - iz
 238             assert len_a >= 0
 239             assert len_b >= 0
 240             assert len_base >= 0
 241
 242             #print 'unmatched a=%d, b=%d' % (len_a, len_b)
 243
 244             if len_a or len_b:
 245                 # try to avoid actually slicing the lists
 246                 equal_a = compare_range(self.a, ia, amatch,
 247                                         self.base, iz, zmatch)
 248                 equal_b = compare_range(self.b, ib, bmatch,
 249                                         self.base, iz, zmatch)
 250                 same = compare_range(self.a, ia, amatch,
 251                                      self.b, ib, bmatch)
 252
 253                 if same:
 254                     yield 'same', ia, amatch
 255                 elif equal_a and not equal_b:
 256                     yield 'b', ib, bmatch
 257                 elif equal_b and not equal_a:
 258                     yield 'a', ia, amatch
 259                 elif not equal_a and not equal_b:
 260                     yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
 261                 else:
 262                     raise AssertionError("can't handle a=b=base but unmatched")
 263
 264                 ia = amatch
 265                 ib = bmatch
 266             iz = zmatch
 267
 268             # if the same part of the base was deleted on both sides
 269             # that's OK, we can just skip it.
 270
 271
 272             if matchlen > 0:
 273                 assert ia == amatch
 274                 assert ib == bmatch
 275                 assert iz == zmatch
 276
 277                 yield 'unchanged', zmatch, zend
 278                 iz = zend
 279                 ia = aend
 280                 ib = bend
 281
 282     def reprocess_merge_regions(self, merge_regions):
 283         """Where there are conflict regions, remove the agreed lines.
 284
 285         Lines where both A and B have made the same changes are
 286         eliminated.
 287         """
 288         for region in merge_regions:
 289             if region[0] != "conflict":
 290                 yield region
 291                 continue
 292             type, iz, zmatch, ia, amatch, ib, bmatch = region
 293             a_region = self.a[ia:amatch]
 294             b_region = self.b[ib:bmatch]
 295             matches = mdiff.get_matching_blocks(''.join(a_region),
 296                                                 ''.join(b_region))
 297             next_a = ia
 298             next_b = ib
 299             for region_ia, region_ib, region_len in matches[:-1]:
 300                 region_ia += ia
 301                 region_ib += ib
 302                 reg = self.mismatch_region(next_a, region_ia, next_b,
 303                                            region_ib)
 304                 if reg is not None:
 305                     yield reg
 306                 yield 'same', region_ia, region_len+region_ia
 307                 next_a = region_ia + region_len
 308                 next_b = region_ib + region_len
 309             reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
 310             if reg is not None:
 311                 yield reg
 312
 313     def mismatch_region(next_a, region_ia,  next_b, region_ib):
 314         if next_a < region_ia or next_b < region_ib:
 315             return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 316     mismatch_region = staticmethod(mismatch_region)
 317
 318     def find_sync_regions(self):
 319         """Return a list of sync regions, where both descendents match the base.
 320
 321         Generates a list of (base1, base2, a1, a2, b1, b2).  There is
 322         always a zero-length sync region at the end of all the files.
 323         """
 324
 325         ia = ib = 0
 326         amatches = mdiff.get_matching_blocks(self.basetext, self.atext)
 327         bmatches = mdiff.get_matching_blocks(self.basetext, self.btext)
 328         len_a = len(amatches)
 329         len_b = len(bmatches)
 330
 331         sl = []
 332
 333         while ia < len_a and ib < len_b:
 334             abase, amatch, alen = amatches[ia]
 335             bbase, bmatch, blen = bmatches[ib]
 336
 337             # there is an unconflicted block at i; how long does it
 338             # extend?  until whichever one ends earlier.
 339             i = intersect((abase, abase+alen), (bbase, bbase+blen))
 340             if i:
 341                 intbase = i[0]
 342                 intend = i[1]
 343                 intlen = intend - intbase
 344
 345                 # found a match of base[i[0], i[1]]; this may be less than
 346                 # the region that matches in either one
 347                 assert intlen <= alen
 348                 assert intlen <= blen
 349                 assert abase <= intbase
 350                 assert bbase <= intbase
 351
 352                 asub = amatch + (intbase - abase)
 353                 bsub = bmatch + (intbase - bbase)
 354                 aend = asub + intlen
 355                 bend = bsub + intlen
 356
 357                 assert self.base[intbase:intend] == self.a[asub:aend], \
 358                        (self.base[intbase:intend], self.a[asub:aend])
 359
 360                 assert self.base[intbase:intend] == self.b[bsub:bend]
 361
 362                 sl.append((intbase, intend,
 363                            asub, aend,
 364                            bsub, bend))
 365
 366             # advance whichever one ends first in the base text
 367             if (abase + alen) < (bbase + blen):
 368                 ia += 1
 369             else:
 370                 ib += 1
 371
 372         intbase = len(self.base)
 373         abase = len(self.a)
 374         bbase = len(self.b)
 375         sl.append((intbase, intbase, abase, abase, bbase, bbase))
 376
 377         return sl
 378
 379     def find_unconflicted(self):
 380         """Return a list of ranges in base that are not conflicted."""
 381         am = mdiff.get_matching_blocks(self.basetext, self.atext)
 382         bm = mdiff.get_matching_blocks(self.basetext, self.btext)
 383
 384         unc = []
 385
 386         while am and bm:
 387             # there is an unconflicted block at i; how long does it
 388             # extend?  until whichever one ends earlier.
 389             a1 = am[0][0]
 390             a2 = a1 + am[0][2]
 391             b1 = bm[0][0]
 392             b2 = b1 + bm[0][2]
 393             i = intersect((a1, a2), (b1, b2))
 394             if i:
 395                 unc.append(i)
 396
 397             if a2 < b2:
 398                 del am[0]
 399             else:
 400                 del bm[0]
 401
 402         return unc
 403
 404 def simplemerge(ui, local, base, other, **opts):
 405     def readfile(filename):
 406         f = open(filename, "rb")
 407         text = f.read()
 408         f.close()
 409         if util.binary(text):
 410             msg = _("%s looks like a binary file.") % filename
 411             if not opts.get('text'):
 412                 raise util.Abort(msg)
 413             elif not opts.get('quiet'):
 414                 ui.warn(_('warning: %s\n') % msg)
 415         return text
 416
 417     name_a = local
 418     name_b = other
 419     labels = opts.get('label', [])
 420     if labels:
 421         name_a = labels.pop(0)
 422     if labels:
 423         name_b = labels.pop(0)
 424     if labels:
 425         raise util.Abort(_("can only specify two labels."))
 426
 427     localtext = readfile(local)
 428     basetext = readfile(base)
 429     othertext = readfile(other)
 430
 431     local = os.path.realpath(local)
 432     if not opts.get('print'):
 433         opener = util.opener(os.path.dirname(local))
 434         out = opener(os.path.basename(local), "w", atomictemp=True)
 435     else:
 436         out = sys.stdout
 437
 438     reprocess = not opts.get('no_minimal')
 439
 440     m3 = Merge3Text(basetext, localtext, othertext)
 441     for line in m3.merge_lines(name_a=name_a, name_b=name_b,
 442                                reprocess=reprocess):
 443         out.write(line)
 444
 445     if not opts.get('print'):
 446         out.rename()
 447
 448     if m3.conflicts:
 449         if not opts.get('quiet'):
 450             ui.warn(_("warning: conflicts during merge.\n"))
 451         return 1