|
28
|
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
|
