« back to all changes in this revision
Viewing changes to bzrlib/merge3.py
- browse files at revision 942
- compare with another revision
- download diff
- download tarball
- view history from revision 942
- Committer: Martin Pool
- Date: 2005-07-18 13:12:43 UTC
- Revision ID: mbp@sourcefrog.net-20050718131243-44532527fd065b31
- update convertinv to work with current weave code
- files added:
- bzrlib/hashcache.py
- tools
- files removed:
- bzrlib/statcache.py
- plugins/rsync
- files modified:
- .bzrignore
added
removed
bzrlib/merge3.py
1
# Copyright (C) 2004, 2005 by 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
18
# mbp: "you know that thing where cvs gives you conflict markers?"
19
# s: "i hate that."
20
21
22
23
def intersect(ra, rb):
24
"""Given two ranges return the range where they intersect or None.
25
26
>>> intersect((0, 10), (0, 6))
27
(0, 6)
28
>>> intersect((0, 10), (5, 15))
29
(5, 10)
30
>>> intersect((0, 10), (10, 15))
31
>>> intersect((0, 9), (10, 15))
32
>>> intersect((0, 9), (7, 15))
33
(7, 9)
34
"""
35
assert ra[0] <= ra[1]
36
assert rb[0] <= rb[1]
37
38
sa = max(ra[0], rb[0])
39
sb = min(ra[1], rb[1])
40
if sa < sb:
41
return sa, sb
42
else:
43
return None
44
45
46
def compare_range(a, astart, aend, b, bstart, bend):
47
"""Compare a[astart:aend] == b[bstart:bend], without slicing.
48
"""
49
if (aend-astart) != (bend-bstart):
50
return False
51
for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)):
52
if a[ia] != b[ib]:
53
return False
54
else:
55
return True
56
57
58
59
60
class Merge3(object):
61
"""3-way merge of texts.
62
63
Given BASE, OTHER, THIS, tries to produce a combined text
64
incorporating the changes from both BASE->OTHER and BASE->THIS.
65
All three will typically be sequences of lines."""
66
def __init__(self, base, a, b):
67
self.base = base
68
self.a = a
69
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
74
75
76
def merge_lines(self,
77
name_a=None,
78
name_b=None,
79
start_marker='<<<<<<<<',
80
mid_marker='========',
81
end_marker='>>>>>>>>',
82
show_base=False):
83
"""Return merge in cvs-like form.
84
"""
85
if name_a:
86
start_marker = start_marker + ' ' + name_a
87
if name_b:
88
end_marker = end_marker + ' ' + name_b
89
90
for t in self.merge_regions():
91
what = t[0]
92
if what == 'unchanged':
93
for i in range(t[1], t[2]):
94
yield self.base[i]
95
elif what == 'a' or what == 'same':
96
for i in range(t[1], t[2]):
97
yield self.a[i]
98
elif what == 'b':
99
for i in range(t[1], t[2]):
100
yield self.b[i]
101
elif what == 'conflict':
102
yield start_marker + '\n'
103
for i in range(t[3], t[4]):
104
yield self.a[i]
105
yield mid_marker + '\n'
106
for i in range(t[5], t[6]):
107
yield self.b[i]
108
yield end_marker + '\n'
109
else:
110
raise ValueError(what)
111
112
113
114
115
116
def merge_annotated(self):
117
"""Return merge with conflicts, showing origin of lines.
118
119
Most useful for debugging merge.
120
"""
121
for t in self.merge_regions():
122
what = t[0]
123
if what == 'unchanged':
124
for i in range(t[1], t[2]):
125
yield 'u | ' + self.base[i]
126
elif what == 'a' or what == 'same':
127
for i in range(t[1], t[2]):
128
yield what[0] + ' | ' + self.a[i]
129
elif what == 'b':
130
for i in range(t[1], t[2]):
131
yield 'b | ' + self.b[i]
132
elif what == 'conflict':
133
yield '<<<<\n'
134
for i in range(t[3], t[4]):
135
yield 'A | ' + self.a[i]
136
yield '----\n'
137
for i in range(t[5], t[6]):
138
yield 'B | ' + self.b[i]
139
yield '>>>>\n'
140
else:
141
raise ValueError(what)
142
143
144
145
146
147
def merge_groups(self):
148
"""Yield sequence of line groups. Each one is a tuple:
149
150
'unchanged', lines
151
Lines unchanged from base
152
153
'a', lines
154
Lines taken from a
155
156
'same', lines
157
Lines taken from a (and equal to b)
158
159
'b', lines
160
Lines taken from b
161
162
'conflict', base_lines, a_lines, b_lines
163
Lines from base were changed to either a or b and conflict.
164
"""
165
for t in self.merge_regions():
166
what = t[0]
167
if what == 'unchanged':
168
yield what, self.base[t[1]:t[2]]
169
elif what == 'a' or what == 'same':
170
yield what, self.a[t[1]:t[2]]
171
elif what == 'b':
172
yield what, self.b[t[1]:t[2]]
173
elif what == 'conflict':
174
yield (what,
175
self.base[t[1]:t[2]],
176
self.a[t[3]:t[4]],
177
self.b[t[5]:t[6]])
178
else:
179
raise ValueError(what)
180
181
182
def merge_regions(self):
183
"""Return sequences of matching and conflicting regions.
184
185
This returns tuples, where the first value says what kind we
186
have:
187
188
'unchanged', start, end
189
Take a region of base[start:end]
190
191
'same', astart, aend
192
b and a are different from base but give the same result
193
194
'a', start, end
195
Non-clashing insertion from a[start:end]
196
197
Method is as follows:
198
199
The two sequences align only on regions which match the base
200
and both descendents. These are found by doing a two-way diff
201
of each one against the base, and then finding the
202
intersections between those regions. These "sync regions"
203
are by definition unchanged in both and easily dealt with.
204
205
The regions in between can be in any of three cases:
206
conflicted, or changed on only one side.
207
"""
208
209
# section a[0:ia] has been disposed of, etc
210
iz = ia = ib = 0
211
212
for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
213
#print 'match base [%d:%d]' % (zmatch, zend)
214
215
matchlen = zend - zmatch
216
assert matchlen >= 0
217
assert matchlen == (aend - amatch)
218
assert matchlen == (bend - bmatch)
219
220
len_a = amatch - ia
221
len_b = bmatch - ib
222
len_base = zmatch - iz
223
assert len_a >= 0
224
assert len_b >= 0
225
assert len_base >= 0
226
227
#print 'unmatched a=%d, b=%d' % (len_a, len_b)
228
229
if len_a or len_b:
230
# try to avoid actually slicing the lists
231
equal_a = compare_range(self.a, ia, amatch,
232
self.base, iz, zmatch)
233
equal_b = compare_range(self.b, ib, bmatch,
234
self.base, iz, zmatch)
235
same = compare_range(self.a, ia, amatch,
236
self.b, ib, bmatch)
237
238
if same:
239
yield 'same', ia, amatch
240
elif equal_a and not equal_b:
241
yield 'b', ib, bmatch
242
elif equal_b and not equal_a:
243
yield 'a', ia, amatch
244
elif not equal_a and not equal_b:
245
yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
246
else:
247
raise AssertionError("can't handle a=b=base but unmatched")
248
249
ia = amatch
250
ib = bmatch
251
iz = zmatch
252
253
# if the same part of the base was deleted on both sides
254
# that's OK, we can just skip it.
255
256
257
if matchlen > 0:
258
assert ia == amatch
259
assert ib == bmatch
260
assert iz == zmatch
261
262
yield 'unchanged', zmatch, zend
263
iz = zend
264
ia = aend
265
ib = bend
266
267
268
269
def find_sync_regions(self):
270
"""Return a list of sync regions, where both descendents match the base.
271
272
Generates a list of (base1, base2, a1, a2, b1, b2). There is
273
always a zero-length sync region at the end of all the files.
274
"""
275
from difflib import SequenceMatcher
276
277
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()
280
len_a = len(amatches)
281
len_b = len(bmatches)
282
283
sl = []
284
285
while ia < len_a and ib < len_b:
286
abase, amatch, alen = amatches[ia]
287
bbase, bmatch, blen = bmatches[ib]
288
289
# there is an unconflicted block at i; how long does it
290
# extend? until whichever one ends earlier.
291
i = intersect((abase, abase+alen), (bbase, bbase+blen))
292
if i:
293
intbase = i[0]
294
intend = i[1]
295
intlen = intend - intbase
296
297
# found a match of base[i[0], i[1]]; this may be less than
298
# the region that matches in either one
299
assert intlen <= alen
300
assert intlen <= blen
301
assert abase <= intbase
302
assert bbase <= intbase
303
304
asub = amatch + (intbase - abase)
305
bsub = bmatch + (intbase - bbase)
306
aend = asub + intlen
307
bend = bsub + intlen
308
309
assert self.base[intbase:intend] == self.a[asub:aend], \
310
(self.base[intbase:intend], self.a[asub:aend])
311
312
assert self.base[intbase:intend] == self.b[bsub:bend]
313
314
sl.append((intbase, intend,
315
asub, aend,
316
bsub, bend))
317
318
# advance whichever one ends first in the base text
319
if (abase + alen) < (bbase + blen):
320
ia += 1
321
else:
322
ib += 1
323
324
intbase = len(self.base)
325
abase = len(self.a)
326
bbase = len(self.b)
327
sl.append((intbase, intbase, abase, abase, bbase, bbase))
328
329
return sl
330
331
332
333
def find_unconflicted(self):
334
"""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()
344
345
unc = []
346
347
while am and bm:
348
# there is an unconflicted block at i; how long does it
349
# extend? until whichever one ends earlier.
350
a1 = am[0][0]
351
a2 = a1 + am[0][2]
352
b1 = bm[0][0]
353
b2 = b1 + bm[0][2]
354
i = intersect((a1, a2), (b1, b2))
355
if i:
356
unc.append(i)
357
358
if a2 < b2:
359
del am[0]
360
else:
361
del bm[0]
362
363
return unc
364
365
366
def main(argv):
367
# as for diff3 and meld the syntax is "MINE BASE OTHER"
368
a = file(argv[1], 'rt').readlines()
369
base = file(argv[2], 'rt').readlines()
370
b = file(argv[3], 'rt').readlines()
371
372
m3 = Merge3(base, a, b)
373
374
#for sr in m3.find_sync_regions():
375
# print sr
376
377
# sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
378
sys.stdout.writelines(m3.merge_annotated())
379
380
381
if __name__ == '__main__':
382
import sys
383
sys.exit(main(sys.argv))
Loggerhead is a web-based interface for Breezy
Version: 2.0.1