1
### Copyright (C) 2002-2006 Stephen Kennedy <stevek@gnome.org>
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.
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.
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
19
################################################################################
23
################################################################################
24
class IncrementalSequenceMatcher(difflib.SequenceMatcher):
25
def __init__(self, isjunk=None, a="", b=""):
26
difflib.SequenceMatcher.__init__(self, isjunk, a, b)
29
la, lb = len(self.a), len(self.b)
30
todo = [(0, la, 0, lb)]
33
alo, ahi, blo, bhi = todo.pop(0)
34
i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
38
if alo < i and blo < j:
39
todo.append( (alo, i, blo, j) )
40
if i+k < ahi and j+k < bhi:
41
todo.append( (i+k, ahi, j+k, bhi) )
42
done.append( (la, (la, lb, 0)) )
44
self.matching_blocks = [x[1] for x in done]
47
def get_difference_opcodes(self):
48
return filter(lambda x: x[0]!="equal", self.get_opcodes())
52
"replace" : "replace",
55
"conflict" : "conflict",
59
def reverse_chunk(chunk):
60
return opcode_reverse[chunk[0]], chunk[3], chunk[4], chunk[1], chunk[2]
62
################################################################################
66
################################################################################
68
"""Utility class to hold diff2 or diff3 chunks"""
70
_matcher = IncrementalSequenceMatcher
73
# Internally, diffs are stored from text1 -> text0 and text1 -> text2.
74
self.num_sequences = 0
75
self.seqlength = [0, 0, 0]
77
self._merge_cache = []
79
def _update_merge_cache(self, texts):
80
if self.num_sequences == 3:
81
self._merge_cache = [c for c in self._merge_diffs(self.diffs[0], self.diffs[1], texts)]
83
self._merge_cache = [(c, None) for c in self.diffs[0]]
85
def change_sequence(self, sequence, startidx, sizechange, texts):
86
assert sequence in (0, 1, 2)
87
if sequence == 0 or sequence == 1:
88
self._change_sequence(0, sequence, startidx, sizechange, texts)
89
if sequence == 2 or (sequence == 1 and self.num_sequences == 3):
90
self._change_sequence(1, sequence, startidx, sizechange, texts)
91
self.seqlength[sequence] += sizechange
92
self._update_merge_cache(texts)
94
def _locate_chunk(self, whichdiffs, sequence, line):
95
"""Find the index of the chunk which contains line."""
96
high_index = 2 + 2 * int(sequence != 1)
97
for i, c in enumerate(self.diffs[whichdiffs]):
98
if line < c[high_index]:
100
return len(self.diffs[whichdiffs])
102
def _change_sequence(self, which, sequence, startidx, sizechange, texts):
103
diffs = self.diffs[which]
104
lines_added = [0,0,0]
105
lines_added[sequence] = sizechange
106
loidx = self._locate_chunk(which, sequence, startidx)
108
hiidx = self._locate_chunk(which, sequence, startidx-sizechange)
113
lorange = diffs[loidx][3], diffs[loidx][1]
117
if hiidx < len(diffs):
119
hirange = diffs[hiidx-1][4], diffs[hiidx-1][2]
121
hirange = self.seqlength[x], self.seqlength[1]
122
#print "diffs", loidx, hiidx, len(diffs), lorange, hirange #diffs[loidx], diffs[hiidx-1]
123
rangex = lorange[0], hirange[0] + lines_added[x]
124
range1 = lorange[1], hirange[1] + lines_added[1]
125
#print "^^^^^", rangex, range1
126
assert rangex[0] <= rangex[1] and range1[0] <= range1[1]
127
linesx = texts[x][rangex[0]:rangex[1]]
128
lines1 = texts[1][range1[0]:range1[1]]
129
#print "<<<\n%s\n===\n%s\n>>>" % ("\n".join(linesx),"\n".join(lines1))
130
newdiffs = self._matcher(None, lines1, linesx).get_difference_opcodes()
131
newdiffs = [ (c[0], c[1]+range1[0],c[2]+range1[0], c[3]+rangex[0],c[4]+rangex[0]) for c in newdiffs]
132
if hiidx < len(self.diffs[which]):
133
self.diffs[which][hiidx:] = [ (c[0],
134
c[1] + lines_added[1], c[2] + lines_added[1],
135
c[3] + lines_added[x], c[4] + lines_added[x])
136
for c in self.diffs[which][hiidx:] ]
137
self.diffs[which][loidx:hiidx] = newdiffs
139
def all_changes(self):
140
return iter(self._merge_cache)
142
def pair_changes(self, fromindex, toindex):
143
"""Give all changes between file1 and either file0 or file2.
147
for c in self._merge_cache:
152
for c in self._merge_cache:
154
yield reverse_chunk(c[seq])
156
def single_changes(self, textindex):
157
"""Give changes for single file only. do not return 'equal' hunks.
159
if textindex in (0,2):
161
for cs in self._merge_cache:
163
yield reverse_chunk(cs[seq]) + (1,)
165
for cs in self._merge_cache:
171
def sequences_identical(self):
172
return self.diffs == [[], []]
174
def _merge_blocks(self, using):
176
lowc = min(using[0][ 0][LO], using[1][ 0][LO])
177
highc = max(using[0][-1][HI], using[1][-1][HI])
182
low.append(lowc - d[LO] + d[2+LO])
184
high.append(highc - d[HI] + d[2+HI])
185
return low[0], high[0], lowc, highc, low[1], high[1]
187
def _auto_merge(self, using, texts):
188
"""Automatically merge two sequences of change blocks"""
189
l0, h0, l1, h1, l2, h2 = self._merge_blocks(using)
190
if h0-l0 == h2-l2 and texts[0][l0:h0] == texts[2][l2:h2]:
191
if l1 != h1 and l0 == h0:
199
out0 = (tag, l1, h1, l0, h0)
200
out1 = (tag, l1, h1, l2, h2)
203
def _merge_diffs(self, seq0, seq1, texts):
204
seq0, seq1 = seq0[:], seq1[:]
207
while len(seq0) or len(seq1):
213
high_seq = int(seq0[0][LO] > seq1[0][LO])
214
if seq0[0][LO] == seq1[0][LO]:
215
if seq0[0][0] == "insert":
217
elif seq1[0][0] == "insert":
220
high_diff = seq[high_seq].pop(0)
221
high_mark = high_diff[HI]
222
other_seq = high_seq ^ 1
225
using[high_seq].append(high_diff)
227
while seq[other_seq]:
228
other_diff = seq[other_seq][0]
229
if high_mark < other_diff[LO]:
231
if high_mark == other_diff[LO] and not (high_diff[0] == other_diff[0] == "insert"):
234
using[other_seq].append(other_diff)
235
seq[other_seq].pop(0)
237
if high_mark < other_diff[HI]:
238
(high_seq, other_seq) = (other_seq, high_seq)
239
high_mark = other_diff[HI]
242
assert len(using[1])==1
243
yield None, using[1][0]
244
elif len(using[1])==0:
245
assert len(using[0])==1
246
yield using[0][0], None
248
for c in self._auto_merge(using, texts):
251
def set_sequences_iter(self, sequences):
252
assert 0 <= len(sequences) <= 3
253
self.diffs = [[], []]
254
self.num_sequences = len(sequences)
255
self.seqlength = [len(s) for s in sequences]
257
for i in range(self.num_sequences - 1):
258
matcher = self._matcher(None, sequences[1], sequences[i*2])
259
work = matcher.initialise()
260
while work.next() == None:
262
self.diffs[i] = matcher.get_difference_opcodes()
263
self._update_merge_cache(sequences)
added
removed
diffutil.py
