blob: e6cc6ee44254c881a11f78f845180f5eeec44743 [file] [log] [blame]
Benjamin Peterson90f5ba52010-03-11 22:53:45 +00001#! /usr/bin/env python3
Tim Peters9ae21482001-02-10 08:00:53 +00002
3"""
4Module difflib -- helpers for computing deltas between objects.
5
6Function get_close_matches(word, possibilities, n=3, cutoff=0.6):
Tim Peters9ae21482001-02-10 08:00:53 +00007 Use SequenceMatcher to return list of the best "good enough" matches.
8
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00009Function context_diff(a, b):
10 For two lists of strings, return a delta in context diff format.
11
Tim Peters5e824c32001-08-12 22:25:01 +000012Function ndiff(a, b):
13 Return a delta: the difference between `a` and `b` (lists of strings).
Tim Peters9ae21482001-02-10 08:00:53 +000014
Tim Peters5e824c32001-08-12 22:25:01 +000015Function restore(delta, which):
16 Return one of the two sequences that generated an ndiff delta.
Tim Peters9ae21482001-02-10 08:00:53 +000017
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +000018Function unified_diff(a, b):
19 For two lists of strings, return a delta in unified diff format.
20
Tim Peters5e824c32001-08-12 22:25:01 +000021Class SequenceMatcher:
22 A flexible class for comparing pairs of sequences of any type.
Tim Peters9ae21482001-02-10 08:00:53 +000023
Tim Peters5e824c32001-08-12 22:25:01 +000024Class Differ:
25 For producing human-readable deltas from sequences of lines of text.
Martin v. Löwise064b412004-08-29 16:34:40 +000026
27Class HtmlDiff:
28 For producing HTML side by side comparison with change highlights.
Tim Peters9ae21482001-02-10 08:00:53 +000029"""
30
Tim Peters5e824c32001-08-12 22:25:01 +000031__all__ = ['get_close_matches', 'ndiff', 'restore', 'SequenceMatcher',
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +000032 'Differ','IS_CHARACTER_JUNK', 'IS_LINE_JUNK', 'context_diff',
Christian Heimes25bb7832008-01-11 16:17:00 +000033 'unified_diff', 'HtmlDiff', 'Match']
Tim Peters5e824c32001-08-12 22:25:01 +000034
Terry Reedybcd89882010-12-03 22:29:40 +000035import warnings
Raymond Hettingerbb6b7342004-06-13 09:57:33 +000036import heapq
Christian Heimes25bb7832008-01-11 16:17:00 +000037from collections import namedtuple as _namedtuple
38
39Match = _namedtuple('Match', 'a b size')
Raymond Hettingerbb6b7342004-06-13 09:57:33 +000040
Neal Norwitze7dfe212003-07-01 14:59:46 +000041def _calculate_ratio(matches, length):
42 if length:
43 return 2.0 * matches / length
44 return 1.0
45
Tim Peters9ae21482001-02-10 08:00:53 +000046class SequenceMatcher:
Tim Peters5e824c32001-08-12 22:25:01 +000047
48 """
49 SequenceMatcher is a flexible class for comparing pairs of sequences of
50 any type, so long as the sequence elements are hashable. The basic
51 algorithm predates, and is a little fancier than, an algorithm
52 published in the late 1980's by Ratcliff and Obershelp under the
53 hyperbolic name "gestalt pattern matching". The basic idea is to find
54 the longest contiguous matching subsequence that contains no "junk"
55 elements (R-O doesn't address junk). The same idea is then applied
56 recursively to the pieces of the sequences to the left and to the right
57 of the matching subsequence. This does not yield minimal edit
58 sequences, but does tend to yield matches that "look right" to people.
59
60 SequenceMatcher tries to compute a "human-friendly diff" between two
61 sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the
62 longest *contiguous* & junk-free matching subsequence. That's what
63 catches peoples' eyes. The Windows(tm) windiff has another interesting
64 notion, pairing up elements that appear uniquely in each sequence.
65 That, and the method here, appear to yield more intuitive difference
66 reports than does diff. This method appears to be the least vulnerable
67 to synching up on blocks of "junk lines", though (like blank lines in
68 ordinary text files, or maybe "<P>" lines in HTML files). That may be
69 because this is the only method of the 3 that has a *concept* of
70 "junk" <wink>.
71
72 Example, comparing two strings, and considering blanks to be "junk":
73
74 >>> s = SequenceMatcher(lambda x: x == " ",
75 ... "private Thread currentThread;",
76 ... "private volatile Thread currentThread;")
77 >>>
78
79 .ratio() returns a float in [0, 1], measuring the "similarity" of the
80 sequences. As a rule of thumb, a .ratio() value over 0.6 means the
81 sequences are close matches:
82
Guido van Rossumfff80df2007-02-09 20:33:44 +000083 >>> print(round(s.ratio(), 3))
Tim Peters5e824c32001-08-12 22:25:01 +000084 0.866
85 >>>
86
87 If you're only interested in where the sequences match,
88 .get_matching_blocks() is handy:
89
90 >>> for block in s.get_matching_blocks():
Guido van Rossumfff80df2007-02-09 20:33:44 +000091 ... print("a[%d] and b[%d] match for %d elements" % block)
Tim Peters5e824c32001-08-12 22:25:01 +000092 a[0] and b[0] match for 8 elements
Thomas Wouters0e3f5912006-08-11 14:57:12 +000093 a[8] and b[17] match for 21 elements
Tim Peters5e824c32001-08-12 22:25:01 +000094 a[29] and b[38] match for 0 elements
95
96 Note that the last tuple returned by .get_matching_blocks() is always a
97 dummy, (len(a), len(b), 0), and this is the only case in which the last
98 tuple element (number of elements matched) is 0.
99
100 If you want to know how to change the first sequence into the second,
101 use .get_opcodes():
102
103 >>> for opcode in s.get_opcodes():
Guido van Rossumfff80df2007-02-09 20:33:44 +0000104 ... print("%6s a[%d:%d] b[%d:%d]" % opcode)
Tim Peters5e824c32001-08-12 22:25:01 +0000105 equal a[0:8] b[0:8]
106 insert a[8:8] b[8:17]
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000107 equal a[8:29] b[17:38]
Tim Peters5e824c32001-08-12 22:25:01 +0000108
109 See the Differ class for a fancy human-friendly file differencer, which
110 uses SequenceMatcher both to compare sequences of lines, and to compare
111 sequences of characters within similar (near-matching) lines.
112
113 See also function get_close_matches() in this module, which shows how
114 simple code building on SequenceMatcher can be used to do useful work.
115
116 Timing: Basic R-O is cubic time worst case and quadratic time expected
117 case. SequenceMatcher is quadratic time for the worst case and has
118 expected-case behavior dependent in a complicated way on how many
119 elements the sequences have in common; best case time is linear.
120
121 Methods:
122
123 __init__(isjunk=None, a='', b='')
124 Construct a SequenceMatcher.
125
126 set_seqs(a, b)
127 Set the two sequences to be compared.
128
129 set_seq1(a)
130 Set the first sequence to be compared.
131
132 set_seq2(b)
133 Set the second sequence to be compared.
134
135 find_longest_match(alo, ahi, blo, bhi)
136 Find longest matching block in a[alo:ahi] and b[blo:bhi].
137
138 get_matching_blocks()
139 Return list of triples describing matching subsequences.
140
141 get_opcodes()
142 Return list of 5-tuples describing how to turn a into b.
143
144 ratio()
145 Return a measure of the sequences' similarity (float in [0,1]).
146
147 quick_ratio()
148 Return an upper bound on .ratio() relatively quickly.
149
150 real_quick_ratio()
151 Return an upper bound on ratio() very quickly.
152 """
153
Terry Reedy99f96372010-11-25 06:12:34 +0000154 def __init__(self, isjunk=None, a='', b='', autojunk=True):
Tim Peters9ae21482001-02-10 08:00:53 +0000155 """Construct a SequenceMatcher.
156
157 Optional arg isjunk is None (the default), or a one-argument
158 function that takes a sequence element and returns true iff the
Tim Peters5e824c32001-08-12 22:25:01 +0000159 element is junk. None is equivalent to passing "lambda x: 0", i.e.
Fred Drakef1da6282001-02-19 19:30:05 +0000160 no elements are considered to be junk. For example, pass
Tim Peters9ae21482001-02-10 08:00:53 +0000161 lambda x: x in " \\t"
162 if you're comparing lines as sequences of characters, and don't
163 want to synch up on blanks or hard tabs.
164
165 Optional arg a is the first of two sequences to be compared. By
166 default, an empty string. The elements of a must be hashable. See
167 also .set_seqs() and .set_seq1().
168
169 Optional arg b is the second of two sequences to be compared. By
Fred Drakef1da6282001-02-19 19:30:05 +0000170 default, an empty string. The elements of b must be hashable. See
Tim Peters9ae21482001-02-10 08:00:53 +0000171 also .set_seqs() and .set_seq2().
Terry Reedy99f96372010-11-25 06:12:34 +0000172
173 Optional arg autojunk should be set to False to disable the
174 "automatic junk heuristic" that treats popular elements as junk
175 (see module documentation for more information).
Tim Peters9ae21482001-02-10 08:00:53 +0000176 """
177
178 # Members:
179 # a
180 # first sequence
181 # b
182 # second sequence; differences are computed as "what do
183 # we need to do to 'a' to change it into 'b'?"
184 # b2j
185 # for x in b, b2j[x] is a list of the indices (into b)
Terry Reedybcd89882010-12-03 22:29:40 +0000186 # at which x appears; junk and popular elements do not appear
Tim Peters9ae21482001-02-10 08:00:53 +0000187 # fullbcount
188 # for x in b, fullbcount[x] == the number of times x
189 # appears in b; only materialized if really needed (used
190 # only for computing quick_ratio())
191 # matching_blocks
192 # a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];
193 # ascending & non-overlapping in i and in j; terminated by
194 # a dummy (len(a), len(b), 0) sentinel
195 # opcodes
196 # a list of (tag, i1, i2, j1, j2) tuples, where tag is
197 # one of
198 # 'replace' a[i1:i2] should be replaced by b[j1:j2]
199 # 'delete' a[i1:i2] should be deleted
200 # 'insert' b[j1:j2] should be inserted
201 # 'equal' a[i1:i2] == b[j1:j2]
202 # isjunk
203 # a user-supplied function taking a sequence element and
204 # returning true iff the element is "junk" -- this has
205 # subtle but helpful effects on the algorithm, which I'll
206 # get around to writing up someday <0.9 wink>.
207 # DON'T USE! Only __chain_b uses this. Use isbjunk.
Terry Reedy74a7c672010-12-03 18:57:42 +0000208 # bjunk
209 # the items in b for which isjunk is True.
210 # bpopular
211 # nonjunk items in b treated as junk by the heuristic (if used).
Tim Peters9ae21482001-02-10 08:00:53 +0000212
213 self.isjunk = isjunk
214 self.a = self.b = None
Terry Reedy99f96372010-11-25 06:12:34 +0000215 self.autojunk = autojunk
Tim Peters9ae21482001-02-10 08:00:53 +0000216 self.set_seqs(a, b)
217
218 def set_seqs(self, a, b):
219 """Set the two sequences to be compared.
220
221 >>> s = SequenceMatcher()
222 >>> s.set_seqs("abcd", "bcde")
223 >>> s.ratio()
224 0.75
225 """
226
227 self.set_seq1(a)
228 self.set_seq2(b)
229
230 def set_seq1(self, a):
231 """Set the first sequence to be compared.
232
233 The second sequence to be compared is not changed.
234
235 >>> s = SequenceMatcher(None, "abcd", "bcde")
236 >>> s.ratio()
237 0.75
238 >>> s.set_seq1("bcde")
239 >>> s.ratio()
240 1.0
241 >>>
242
243 SequenceMatcher computes and caches detailed information about the
244 second sequence, so if you want to compare one sequence S against
245 many sequences, use .set_seq2(S) once and call .set_seq1(x)
246 repeatedly for each of the other sequences.
247
248 See also set_seqs() and set_seq2().
249 """
250
251 if a is self.a:
252 return
253 self.a = a
254 self.matching_blocks = self.opcodes = None
255
256 def set_seq2(self, b):
257 """Set the second sequence to be compared.
258
259 The first sequence to be compared is not changed.
260
261 >>> s = SequenceMatcher(None, "abcd", "bcde")
262 >>> s.ratio()
263 0.75
264 >>> s.set_seq2("abcd")
265 >>> s.ratio()
266 1.0
267 >>>
268
269 SequenceMatcher computes and caches detailed information about the
270 second sequence, so if you want to compare one sequence S against
271 many sequences, use .set_seq2(S) once and call .set_seq1(x)
272 repeatedly for each of the other sequences.
273
274 See also set_seqs() and set_seq1().
275 """
276
277 if b is self.b:
278 return
279 self.b = b
280 self.matching_blocks = self.opcodes = None
281 self.fullbcount = None
282 self.__chain_b()
283
284 # For each element x in b, set b2j[x] to a list of the indices in
285 # b where x appears; the indices are in increasing order; note that
286 # the number of times x appears in b is len(b2j[x]) ...
287 # when self.isjunk is defined, junk elements don't show up in this
288 # map at all, which stops the central find_longest_match method
289 # from starting any matching block at a junk element ...
290 # also creates the fast isbjunk function ...
Tim Peters81b92512002-04-29 01:37:32 +0000291 # b2j also does not contain entries for "popular" elements, meaning
Terry Reedy99f96372010-11-25 06:12:34 +0000292 # elements that account for more than 1 + 1% of the total elements, and
Tim Peters81b92512002-04-29 01:37:32 +0000293 # when the sequence is reasonably large (>= 200 elements); this can
294 # be viewed as an adaptive notion of semi-junk, and yields an enormous
295 # speedup when, e.g., comparing program files with hundreds of
296 # instances of "return NULL;" ...
Tim Peters9ae21482001-02-10 08:00:53 +0000297 # note that this is only called when b changes; so for cross-product
298 # kinds of matches, it's best to call set_seq2 once, then set_seq1
299 # repeatedly
300
301 def __chain_b(self):
302 # Because isjunk is a user-defined (not C) function, and we test
303 # for junk a LOT, it's important to minimize the number of calls.
304 # Before the tricks described here, __chain_b was by far the most
305 # time-consuming routine in the whole module! If anyone sees
306 # Jim Roskind, thank him again for profile.py -- I never would
307 # have guessed that.
308 # The first trick is to build b2j ignoring the possibility
309 # of junk. I.e., we don't call isjunk at all yet. Throwing
310 # out the junk later is much cheaper than building b2j "right"
311 # from the start.
312 b = self.b
313 self.b2j = b2j = {}
Terry Reedy99f96372010-11-25 06:12:34 +0000314
Tim Peters81b92512002-04-29 01:37:32 +0000315 for i, elt in enumerate(b):
Terry Reedy99f96372010-11-25 06:12:34 +0000316 indices = b2j.setdefault(elt, [])
317 indices.append(i)
Tim Peters9ae21482001-02-10 08:00:53 +0000318
Terry Reedy99f96372010-11-25 06:12:34 +0000319 # Purge junk elements
Terry Reedy74a7c672010-12-03 18:57:42 +0000320 self.bjunk = junk = set()
Tim Peters81b92512002-04-29 01:37:32 +0000321 isjunk = self.isjunk
Tim Peters9ae21482001-02-10 08:00:53 +0000322 if isjunk:
Terry Reedy17a59252010-12-15 20:18:10 +0000323 for elt in b2j.keys():
Terry Reedy99f96372010-11-25 06:12:34 +0000324 if isjunk(elt):
325 junk.add(elt)
Terry Reedy17a59252010-12-15 20:18:10 +0000326 for elt in junk: # separate loop avoids separate list of keys
327 del b2j[elt]
Tim Peters9ae21482001-02-10 08:00:53 +0000328
Terry Reedy99f96372010-11-25 06:12:34 +0000329 # Purge popular elements that are not junk
Terry Reedy74a7c672010-12-03 18:57:42 +0000330 self.bpopular = popular = set()
Terry Reedy99f96372010-11-25 06:12:34 +0000331 n = len(b)
332 if self.autojunk and n >= 200:
333 ntest = n // 100 + 1
Terry Reedy17a59252010-12-15 20:18:10 +0000334 for elt, idxs in b2j.items():
Terry Reedy99f96372010-11-25 06:12:34 +0000335 if len(idxs) > ntest:
336 popular.add(elt)
Terry Reedy17a59252010-12-15 20:18:10 +0000337 for elt in popular: # ditto; as fast for 1% deletion
338 del b2j[elt]
Terry Reedy99f96372010-11-25 06:12:34 +0000339
Terry Reedybcd89882010-12-03 22:29:40 +0000340 def isbjunk(self, item):
341 "Deprecated; use 'item in SequenceMatcher().bjunk'."
342 warnings.warn("'SequenceMatcher().isbjunk(item)' is deprecated;\n"
343 "use 'item in SMinstance.bjunk' instead.",
344 DeprecationWarning, 2)
345 return item in self.bjunk
346
347 def isbpopular(self, item):
348 "Deprecated; use 'item in SequenceMatcher().bpopular'."
349 warnings.warn("'SequenceMatcher().isbpopular(item)' is deprecated;\n"
350 "use 'item in SMinstance.bpopular' instead.",
351 DeprecationWarning, 2)
352 return item in self.bpopular
Tim Peters9ae21482001-02-10 08:00:53 +0000353
354 def find_longest_match(self, alo, ahi, blo, bhi):
355 """Find longest matching block in a[alo:ahi] and b[blo:bhi].
356
357 If isjunk is not defined:
358
359 Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
360 alo <= i <= i+k <= ahi
361 blo <= j <= j+k <= bhi
362 and for all (i',j',k') meeting those conditions,
363 k >= k'
364 i <= i'
365 and if i == i', j <= j'
366
367 In other words, of all maximal matching blocks, return one that
368 starts earliest in a, and of all those maximal matching blocks that
369 start earliest in a, return the one that starts earliest in b.
370
371 >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
372 >>> s.find_longest_match(0, 5, 0, 9)
Christian Heimes25bb7832008-01-11 16:17:00 +0000373 Match(a=0, b=4, size=5)
Tim Peters9ae21482001-02-10 08:00:53 +0000374
375 If isjunk is defined, first the longest matching block is
376 determined as above, but with the additional restriction that no
377 junk element appears in the block. Then that block is extended as
378 far as possible by matching (only) junk elements on both sides. So
379 the resulting block never matches on junk except as identical junk
380 happens to be adjacent to an "interesting" match.
381
382 Here's the same example as before, but considering blanks to be
383 junk. That prevents " abcd" from matching the " abcd" at the tail
384 end of the second sequence directly. Instead only the "abcd" can
385 match, and matches the leftmost "abcd" in the second sequence:
386
387 >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
388 >>> s.find_longest_match(0, 5, 0, 9)
Christian Heimes25bb7832008-01-11 16:17:00 +0000389 Match(a=1, b=0, size=4)
Tim Peters9ae21482001-02-10 08:00:53 +0000390
391 If no blocks match, return (alo, blo, 0).
392
393 >>> s = SequenceMatcher(None, "ab", "c")
394 >>> s.find_longest_match(0, 2, 0, 1)
Christian Heimes25bb7832008-01-11 16:17:00 +0000395 Match(a=0, b=0, size=0)
Tim Peters9ae21482001-02-10 08:00:53 +0000396 """
397
398 # CAUTION: stripping common prefix or suffix would be incorrect.
399 # E.g.,
400 # ab
401 # acab
402 # Longest matching block is "ab", but if common prefix is
403 # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
404 # strip, so ends up claiming that ab is changed to acab by
405 # inserting "ca" in the middle. That's minimal but unintuitive:
406 # "it's obvious" that someone inserted "ac" at the front.
407 # Windiff ends up at the same place as diff, but by pairing up
408 # the unique 'b's and then matching the first two 'a's.
409
Terry Reedybcd89882010-12-03 22:29:40 +0000410 a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
Tim Peters9ae21482001-02-10 08:00:53 +0000411 besti, bestj, bestsize = alo, blo, 0
412 # find longest junk-free match
413 # during an iteration of the loop, j2len[j] = length of longest
414 # junk-free match ending with a[i-1] and b[j]
415 j2len = {}
416 nothing = []
Guido van Rossum805365e2007-05-07 22:24:25 +0000417 for i in range(alo, ahi):
Tim Peters9ae21482001-02-10 08:00:53 +0000418 # look at all instances of a[i] in b; note that because
419 # b2j has no junk keys, the loop is skipped if a[i] is junk
420 j2lenget = j2len.get
421 newj2len = {}
422 for j in b2j.get(a[i], nothing):
423 # a[i] matches b[j]
424 if j < blo:
425 continue
426 if j >= bhi:
427 break
428 k = newj2len[j] = j2lenget(j-1, 0) + 1
429 if k > bestsize:
430 besti, bestj, bestsize = i-k+1, j-k+1, k
431 j2len = newj2len
432
Tim Peters81b92512002-04-29 01:37:32 +0000433 # Extend the best by non-junk elements on each end. In particular,
434 # "popular" non-junk elements aren't in b2j, which greatly speeds
435 # the inner loop above, but also means "the best" match so far
436 # doesn't contain any junk *or* popular non-junk elements.
437 while besti > alo and bestj > blo and \
438 not isbjunk(b[bestj-1]) and \
439 a[besti-1] == b[bestj-1]:
440 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
441 while besti+bestsize < ahi and bestj+bestsize < bhi and \
442 not isbjunk(b[bestj+bestsize]) and \
443 a[besti+bestsize] == b[bestj+bestsize]:
444 bestsize += 1
445
Tim Peters9ae21482001-02-10 08:00:53 +0000446 # Now that we have a wholly interesting match (albeit possibly
447 # empty!), we may as well suck up the matching junk on each
448 # side of it too. Can't think of a good reason not to, and it
449 # saves post-processing the (possibly considerable) expense of
450 # figuring out what to do with it. In the case of an empty
451 # interesting match, this is clearly the right thing to do,
452 # because no other kind of match is possible in the regions.
453 while besti > alo and bestj > blo and \
454 isbjunk(b[bestj-1]) and \
455 a[besti-1] == b[bestj-1]:
456 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
457 while besti+bestsize < ahi and bestj+bestsize < bhi and \
458 isbjunk(b[bestj+bestsize]) and \
459 a[besti+bestsize] == b[bestj+bestsize]:
460 bestsize = bestsize + 1
461
Christian Heimes25bb7832008-01-11 16:17:00 +0000462 return Match(besti, bestj, bestsize)
Tim Peters9ae21482001-02-10 08:00:53 +0000463
464 def get_matching_blocks(self):
465 """Return list of triples describing matching subsequences.
466
467 Each triple is of the form (i, j, n), and means that
468 a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000469 i and in j. New in Python 2.5, it's also guaranteed that if
470 (i, j, n) and (i', j', n') are adjacent triples in the list, and
471 the second is not the last triple in the list, then i+n != i' or
472 j+n != j'. IOW, adjacent triples never describe adjacent equal
473 blocks.
Tim Peters9ae21482001-02-10 08:00:53 +0000474
475 The last triple is a dummy, (len(a), len(b), 0), and is the only
476 triple with n==0.
477
478 >>> s = SequenceMatcher(None, "abxcd", "abcd")
Christian Heimes25bb7832008-01-11 16:17:00 +0000479 >>> list(s.get_matching_blocks())
480 [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
Tim Peters9ae21482001-02-10 08:00:53 +0000481 """
482
483 if self.matching_blocks is not None:
484 return self.matching_blocks
Tim Peters9ae21482001-02-10 08:00:53 +0000485 la, lb = len(self.a), len(self.b)
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000486
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000487 # This is most naturally expressed as a recursive algorithm, but
488 # at least one user bumped into extreme use cases that exceeded
489 # the recursion limit on their box. So, now we maintain a list
490 # ('queue`) of blocks we still need to look at, and append partial
491 # results to `matching_blocks` in a loop; the matches are sorted
492 # at the end.
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000493 queue = [(0, la, 0, lb)]
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000494 matching_blocks = []
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000495 while queue:
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000496 alo, ahi, blo, bhi = queue.pop()
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000497 i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000498 # a[alo:i] vs b[blo:j] unknown
499 # a[i:i+k] same as b[j:j+k]
500 # a[i+k:ahi] vs b[j+k:bhi] unknown
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000501 if k: # if k is 0, there was no matching block
502 matching_blocks.append(x)
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000503 if alo < i and blo < j:
504 queue.append((alo, i, blo, j))
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000505 if i+k < ahi and j+k < bhi:
506 queue.append((i+k, ahi, j+k, bhi))
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000507 matching_blocks.sort()
Gustavo Niemeyer548148812006-01-31 18:34:13 +0000508
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000509 # It's possible that we have adjacent equal blocks in the
510 # matching_blocks list now. Starting with 2.5, this code was added
511 # to collapse them.
512 i1 = j1 = k1 = 0
513 non_adjacent = []
514 for i2, j2, k2 in matching_blocks:
515 # Is this block adjacent to i1, j1, k1?
516 if i1 + k1 == i2 and j1 + k1 == j2:
517 # Yes, so collapse them -- this just increases the length of
518 # the first block by the length of the second, and the first
519 # block so lengthened remains the block to compare against.
520 k1 += k2
521 else:
522 # Not adjacent. Remember the first block (k1==0 means it's
523 # the dummy we started with), and make the second block the
524 # new block to compare against.
525 if k1:
526 non_adjacent.append((i1, j1, k1))
527 i1, j1, k1 = i2, j2, k2
528 if k1:
529 non_adjacent.append((i1, j1, k1))
530
531 non_adjacent.append( (la, lb, 0) )
532 self.matching_blocks = non_adjacent
Christian Heimes25bb7832008-01-11 16:17:00 +0000533 return map(Match._make, self.matching_blocks)
Tim Peters9ae21482001-02-10 08:00:53 +0000534
Tim Peters9ae21482001-02-10 08:00:53 +0000535 def get_opcodes(self):
536 """Return list of 5-tuples describing how to turn a into b.
537
538 Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple
539 has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
540 tuple preceding it, and likewise for j1 == the previous j2.
541
542 The tags are strings, with these meanings:
543
544 'replace': a[i1:i2] should be replaced by b[j1:j2]
545 'delete': a[i1:i2] should be deleted.
546 Note that j1==j2 in this case.
547 'insert': b[j1:j2] should be inserted at a[i1:i1].
548 Note that i1==i2 in this case.
549 'equal': a[i1:i2] == b[j1:j2]
550
551 >>> a = "qabxcd"
552 >>> b = "abycdf"
553 >>> s = SequenceMatcher(None, a, b)
554 >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
Guido van Rossumfff80df2007-02-09 20:33:44 +0000555 ... print(("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
556 ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2])))
Tim Peters9ae21482001-02-10 08:00:53 +0000557 delete a[0:1] (q) b[0:0] ()
558 equal a[1:3] (ab) b[0:2] (ab)
559 replace a[3:4] (x) b[2:3] (y)
560 equal a[4:6] (cd) b[3:5] (cd)
561 insert a[6:6] () b[5:6] (f)
562 """
563
564 if self.opcodes is not None:
565 return self.opcodes
566 i = j = 0
567 self.opcodes = answer = []
568 for ai, bj, size in self.get_matching_blocks():
569 # invariant: we've pumped out correct diffs to change
570 # a[:i] into b[:j], and the next matching block is
571 # a[ai:ai+size] == b[bj:bj+size]. So we need to pump
572 # out a diff to change a[i:ai] into b[j:bj], pump out
573 # the matching block, and move (i,j) beyond the match
574 tag = ''
575 if i < ai and j < bj:
576 tag = 'replace'
577 elif i < ai:
578 tag = 'delete'
579 elif j < bj:
580 tag = 'insert'
581 if tag:
582 answer.append( (tag, i, ai, j, bj) )
583 i, j = ai+size, bj+size
584 # the list of matching blocks is terminated by a
585 # sentinel with size 0
586 if size:
587 answer.append( ('equal', ai, i, bj, j) )
588 return answer
589
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +0000590 def get_grouped_opcodes(self, n=3):
591 """ Isolate change clusters by eliminating ranges with no changes.
592
593 Return a generator of groups with upto n lines of context.
594 Each group is in the same format as returned by get_opcodes().
595
596 >>> from pprint import pprint
Guido van Rossumc1f779c2007-07-03 08:25:58 +0000597 >>> a = list(map(str, range(1,40)))
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +0000598 >>> b = a[:]
599 >>> b[8:8] = ['i'] # Make an insertion
600 >>> b[20] += 'x' # Make a replacement
601 >>> b[23:28] = [] # Make a deletion
602 >>> b[30] += 'y' # Make another replacement
603 >>> pprint(list(SequenceMatcher(None,a,b).get_grouped_opcodes()))
604 [[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],
605 [('equal', 16, 19, 17, 20),
606 ('replace', 19, 20, 20, 21),
607 ('equal', 20, 22, 21, 23),
608 ('delete', 22, 27, 23, 23),
609 ('equal', 27, 30, 23, 26)],
610 [('equal', 31, 34, 27, 30),
611 ('replace', 34, 35, 30, 31),
612 ('equal', 35, 38, 31, 34)]]
613 """
614
615 codes = self.get_opcodes()
Brett Cannond2c5b4b2004-07-10 23:54:07 +0000616 if not codes:
617 codes = [("equal", 0, 1, 0, 1)]
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +0000618 # Fixup leading and trailing groups if they show no changes.
619 if codes[0][0] == 'equal':
620 tag, i1, i2, j1, j2 = codes[0]
621 codes[0] = tag, max(i1, i2-n), i2, max(j1, j2-n), j2
622 if codes[-1][0] == 'equal':
623 tag, i1, i2, j1, j2 = codes[-1]
624 codes[-1] = tag, i1, min(i2, i1+n), j1, min(j2, j1+n)
625
626 nn = n + n
627 group = []
628 for tag, i1, i2, j1, j2 in codes:
629 # End the current group and start a new one whenever
630 # there is a large range with no changes.
631 if tag == 'equal' and i2-i1 > nn:
632 group.append((tag, i1, min(i2, i1+n), j1, min(j2, j1+n)))
633 yield group
634 group = []
635 i1, j1 = max(i1, i2-n), max(j1, j2-n)
636 group.append((tag, i1, i2, j1 ,j2))
637 if group and not (len(group)==1 and group[0][0] == 'equal'):
638 yield group
639
Tim Peters9ae21482001-02-10 08:00:53 +0000640 def ratio(self):
641 """Return a measure of the sequences' similarity (float in [0,1]).
642
643 Where T is the total number of elements in both sequences, and
Tim Petersbcc95cb2004-07-31 00:19:43 +0000644 M is the number of matches, this is 2.0*M / T.
Tim Peters9ae21482001-02-10 08:00:53 +0000645 Note that this is 1 if the sequences are identical, and 0 if
646 they have nothing in common.
647
648 .ratio() is expensive to compute if you haven't already computed
649 .get_matching_blocks() or .get_opcodes(), in which case you may
650 want to try .quick_ratio() or .real_quick_ratio() first to get an
651 upper bound.
652
653 >>> s = SequenceMatcher(None, "abcd", "bcde")
654 >>> s.ratio()
655 0.75
656 >>> s.quick_ratio()
657 0.75
658 >>> s.real_quick_ratio()
659 1.0
660 """
661
Guido van Rossum89da5d72006-08-22 00:21:25 +0000662 matches = sum(triple[-1] for triple in self.get_matching_blocks())
Neal Norwitze7dfe212003-07-01 14:59:46 +0000663 return _calculate_ratio(matches, len(self.a) + len(self.b))
Tim Peters9ae21482001-02-10 08:00:53 +0000664
665 def quick_ratio(self):
666 """Return an upper bound on ratio() relatively quickly.
667
668 This isn't defined beyond that it is an upper bound on .ratio(), and
669 is faster to compute.
670 """
671
672 # viewing a and b as multisets, set matches to the cardinality
673 # of their intersection; this counts the number of matches
674 # without regard to order, so is clearly an upper bound
675 if self.fullbcount is None:
676 self.fullbcount = fullbcount = {}
677 for elt in self.b:
678 fullbcount[elt] = fullbcount.get(elt, 0) + 1
679 fullbcount = self.fullbcount
680 # avail[x] is the number of times x appears in 'b' less the
681 # number of times we've seen it in 'a' so far ... kinda
682 avail = {}
Guido van Rossume2b70bc2006-08-18 22:13:04 +0000683 availhas, matches = avail.__contains__, 0
Tim Peters9ae21482001-02-10 08:00:53 +0000684 for elt in self.a:
685 if availhas(elt):
686 numb = avail[elt]
687 else:
688 numb = fullbcount.get(elt, 0)
689 avail[elt] = numb - 1
690 if numb > 0:
691 matches = matches + 1
Neal Norwitze7dfe212003-07-01 14:59:46 +0000692 return _calculate_ratio(matches, len(self.a) + len(self.b))
Tim Peters9ae21482001-02-10 08:00:53 +0000693
694 def real_quick_ratio(self):
695 """Return an upper bound on ratio() very quickly.
696
697 This isn't defined beyond that it is an upper bound on .ratio(), and
698 is faster to compute than either .ratio() or .quick_ratio().
699 """
700
701 la, lb = len(self.a), len(self.b)
702 # can't have more matches than the number of elements in the
703 # shorter sequence
Neal Norwitze7dfe212003-07-01 14:59:46 +0000704 return _calculate_ratio(min(la, lb), la + lb)
Tim Peters9ae21482001-02-10 08:00:53 +0000705
706def get_close_matches(word, possibilities, n=3, cutoff=0.6):
707 """Use SequenceMatcher to return list of the best "good enough" matches.
708
709 word is a sequence for which close matches are desired (typically a
710 string).
711
712 possibilities is a list of sequences against which to match word
713 (typically a list of strings).
714
715 Optional arg n (default 3) is the maximum number of close matches to
716 return. n must be > 0.
717
718 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities
719 that don't score at least that similar to word are ignored.
720
721 The best (no more than n) matches among the possibilities are returned
722 in a list, sorted by similarity score, most similar first.
723
724 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
725 ['apple', 'ape']
Tim Peters5e824c32001-08-12 22:25:01 +0000726 >>> import keyword as _keyword
727 >>> get_close_matches("wheel", _keyword.kwlist)
Tim Peters9ae21482001-02-10 08:00:53 +0000728 ['while']
Guido van Rossum486364b2007-06-30 05:01:58 +0000729 >>> get_close_matches("Apple", _keyword.kwlist)
Tim Peters9ae21482001-02-10 08:00:53 +0000730 []
Tim Peters5e824c32001-08-12 22:25:01 +0000731 >>> get_close_matches("accept", _keyword.kwlist)
Tim Peters9ae21482001-02-10 08:00:53 +0000732 ['except']
733 """
734
735 if not n > 0:
Walter Dörwald70a6b492004-02-12 17:35:32 +0000736 raise ValueError("n must be > 0: %r" % (n,))
Tim Peters9ae21482001-02-10 08:00:53 +0000737 if not 0.0 <= cutoff <= 1.0:
Walter Dörwald70a6b492004-02-12 17:35:32 +0000738 raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff,))
Tim Peters9ae21482001-02-10 08:00:53 +0000739 result = []
740 s = SequenceMatcher()
741 s.set_seq2(word)
742 for x in possibilities:
743 s.set_seq1(x)
744 if s.real_quick_ratio() >= cutoff and \
745 s.quick_ratio() >= cutoff and \
746 s.ratio() >= cutoff:
747 result.append((s.ratio(), x))
Tim Peters9ae21482001-02-10 08:00:53 +0000748
Raymond Hettinger6b59f5f2003-10-16 05:53:16 +0000749 # Move the best scorers to head of list
Raymond Hettingeraefde432004-06-15 23:53:35 +0000750 result = heapq.nlargest(n, result)
Raymond Hettinger6b59f5f2003-10-16 05:53:16 +0000751 # Strip scores for the best n matches
Raymond Hettingerbb6b7342004-06-13 09:57:33 +0000752 return [x for score, x in result]
Tim Peters5e824c32001-08-12 22:25:01 +0000753
754def _count_leading(line, ch):
755 """
756 Return number of `ch` characters at the start of `line`.
757
758 Example:
759
760 >>> _count_leading(' abc', ' ')
761 3
762 """
763
764 i, n = 0, len(line)
765 while i < n and line[i] == ch:
766 i += 1
767 return i
768
769class Differ:
770 r"""
771 Differ is a class for comparing sequences of lines of text, and
772 producing human-readable differences or deltas. Differ uses
773 SequenceMatcher both to compare sequences of lines, and to compare
774 sequences of characters within similar (near-matching) lines.
775
776 Each line of a Differ delta begins with a two-letter code:
777
778 '- ' line unique to sequence 1
779 '+ ' line unique to sequence 2
780 ' ' line common to both sequences
781 '? ' line not present in either input sequence
782
783 Lines beginning with '? ' attempt to guide the eye to intraline
784 differences, and were not present in either input sequence. These lines
785 can be confusing if the sequences contain tab characters.
786
787 Note that Differ makes no claim to produce a *minimal* diff. To the
788 contrary, minimal diffs are often counter-intuitive, because they synch
789 up anywhere possible, sometimes accidental matches 100 pages apart.
790 Restricting synch points to contiguous matches preserves some notion of
791 locality, at the occasional cost of producing a longer diff.
792
793 Example: Comparing two texts.
794
795 First we set up the texts, sequences of individual single-line strings
796 ending with newlines (such sequences can also be obtained from the
797 `readlines()` method of file-like objects):
798
799 >>> text1 = ''' 1. Beautiful is better than ugly.
800 ... 2. Explicit is better than implicit.
801 ... 3. Simple is better than complex.
802 ... 4. Complex is better than complicated.
803 ... '''.splitlines(1)
804 >>> len(text1)
805 4
806 >>> text1[0][-1]
807 '\n'
808 >>> text2 = ''' 1. Beautiful is better than ugly.
809 ... 3. Simple is better than complex.
810 ... 4. Complicated is better than complex.
811 ... 5. Flat is better than nested.
812 ... '''.splitlines(1)
813
814 Next we instantiate a Differ object:
815
816 >>> d = Differ()
817
818 Note that when instantiating a Differ object we may pass functions to
819 filter out line and character 'junk'. See Differ.__init__ for details.
820
821 Finally, we compare the two:
822
Tim Peters8a9c2842001-09-22 21:30:22 +0000823 >>> result = list(d.compare(text1, text2))
Tim Peters5e824c32001-08-12 22:25:01 +0000824
825 'result' is a list of strings, so let's pretty-print it:
826
827 >>> from pprint import pprint as _pprint
828 >>> _pprint(result)
829 [' 1. Beautiful is better than ugly.\n',
830 '- 2. Explicit is better than implicit.\n',
831 '- 3. Simple is better than complex.\n',
832 '+ 3. Simple is better than complex.\n',
833 '? ++\n',
834 '- 4. Complex is better than complicated.\n',
835 '? ^ ---- ^\n',
836 '+ 4. Complicated is better than complex.\n',
837 '? ++++ ^ ^\n',
838 '+ 5. Flat is better than nested.\n']
839
840 As a single multi-line string it looks like this:
841
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000842 >>> print(''.join(result), end="")
Tim Peters5e824c32001-08-12 22:25:01 +0000843 1. Beautiful is better than ugly.
844 - 2. Explicit is better than implicit.
845 - 3. Simple is better than complex.
846 + 3. Simple is better than complex.
847 ? ++
848 - 4. Complex is better than complicated.
849 ? ^ ---- ^
850 + 4. Complicated is better than complex.
851 ? ++++ ^ ^
852 + 5. Flat is better than nested.
853
854 Methods:
855
856 __init__(linejunk=None, charjunk=None)
857 Construct a text differencer, with optional filters.
858
859 compare(a, b)
Tim Peters8a9c2842001-09-22 21:30:22 +0000860 Compare two sequences of lines; generate the resulting delta.
Tim Peters5e824c32001-08-12 22:25:01 +0000861 """
862
863 def __init__(self, linejunk=None, charjunk=None):
864 """
865 Construct a text differencer, with optional filters.
866
867 The two optional keyword parameters are for filter functions:
868
869 - `linejunk`: A function that should accept a single string argument,
870 and return true iff the string is junk. The module-level function
871 `IS_LINE_JUNK` may be used to filter out lines without visible
Tim Peters81b92512002-04-29 01:37:32 +0000872 characters, except for at most one splat ('#'). It is recommended
873 to leave linejunk None; as of Python 2.3, the underlying
874 SequenceMatcher class has grown an adaptive notion of "noise" lines
875 that's better than any static definition the author has ever been
876 able to craft.
Tim Peters5e824c32001-08-12 22:25:01 +0000877
878 - `charjunk`: A function that should accept a string of length 1. The
879 module-level function `IS_CHARACTER_JUNK` may be used to filter out
880 whitespace characters (a blank or tab; **note**: bad idea to include
Tim Peters81b92512002-04-29 01:37:32 +0000881 newline in this!). Use of IS_CHARACTER_JUNK is recommended.
Tim Peters5e824c32001-08-12 22:25:01 +0000882 """
883
884 self.linejunk = linejunk
885 self.charjunk = charjunk
Tim Peters5e824c32001-08-12 22:25:01 +0000886
887 def compare(self, a, b):
888 r"""
Tim Peters8a9c2842001-09-22 21:30:22 +0000889 Compare two sequences of lines; generate the resulting delta.
Tim Peters5e824c32001-08-12 22:25:01 +0000890
891 Each sequence must contain individual single-line strings ending with
892 newlines. Such sequences can be obtained from the `readlines()` method
Tim Peters8a9c2842001-09-22 21:30:22 +0000893 of file-like objects. The delta generated also consists of newline-
894 terminated strings, ready to be printed as-is via the writeline()
Tim Peters5e824c32001-08-12 22:25:01 +0000895 method of a file-like object.
896
897 Example:
898
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000899 >>> print(''.join(Differ().compare('one\ntwo\nthree\n'.splitlines(1),
Tim Peters5e824c32001-08-12 22:25:01 +0000900 ... 'ore\ntree\nemu\n'.splitlines(1))),
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000901 ... end="")
Tim Peters5e824c32001-08-12 22:25:01 +0000902 - one
903 ? ^
904 + ore
905 ? ^
906 - two
907 - three
908 ? -
909 + tree
910 + emu
911 """
912
913 cruncher = SequenceMatcher(self.linejunk, a, b)
914 for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():
915 if tag == 'replace':
Tim Peters8a9c2842001-09-22 21:30:22 +0000916 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
Tim Peters5e824c32001-08-12 22:25:01 +0000917 elif tag == 'delete':
Tim Peters8a9c2842001-09-22 21:30:22 +0000918 g = self._dump('-', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +0000919 elif tag == 'insert':
Tim Peters8a9c2842001-09-22 21:30:22 +0000920 g = self._dump('+', b, blo, bhi)
Tim Peters5e824c32001-08-12 22:25:01 +0000921 elif tag == 'equal':
Tim Peters8a9c2842001-09-22 21:30:22 +0000922 g = self._dump(' ', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +0000923 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000924 raise ValueError('unknown tag %r' % (tag,))
Tim Peters8a9c2842001-09-22 21:30:22 +0000925
926 for line in g:
927 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000928
929 def _dump(self, tag, x, lo, hi):
Tim Peters8a9c2842001-09-22 21:30:22 +0000930 """Generate comparison results for a same-tagged range."""
Guido van Rossum805365e2007-05-07 22:24:25 +0000931 for i in range(lo, hi):
Tim Peters8a9c2842001-09-22 21:30:22 +0000932 yield '%s %s' % (tag, x[i])
Tim Peters5e824c32001-08-12 22:25:01 +0000933
934 def _plain_replace(self, a, alo, ahi, b, blo, bhi):
935 assert alo < ahi and blo < bhi
936 # dump the shorter block first -- reduces the burden on short-term
937 # memory if the blocks are of very different sizes
938 if bhi - blo < ahi - alo:
Tim Peters8a9c2842001-09-22 21:30:22 +0000939 first = self._dump('+', b, blo, bhi)
940 second = self._dump('-', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +0000941 else:
Tim Peters8a9c2842001-09-22 21:30:22 +0000942 first = self._dump('-', a, alo, ahi)
943 second = self._dump('+', b, blo, bhi)
944
945 for g in first, second:
946 for line in g:
947 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000948
949 def _fancy_replace(self, a, alo, ahi, b, blo, bhi):
950 r"""
951 When replacing one block of lines with another, search the blocks
952 for *similar* lines; the best-matching pair (if any) is used as a
953 synch point, and intraline difference marking is done on the
954 similar pair. Lots of work, but often worth it.
955
956 Example:
957
958 >>> d = Differ()
Raymond Hettinger83325e92003-07-16 04:32:32 +0000959 >>> results = d._fancy_replace(['abcDefghiJkl\n'], 0, 1,
960 ... ['abcdefGhijkl\n'], 0, 1)
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000961 >>> print(''.join(results), end="")
Tim Peters5e824c32001-08-12 22:25:01 +0000962 - abcDefghiJkl
963 ? ^ ^ ^
964 + abcdefGhijkl
965 ? ^ ^ ^
966 """
967
Tim Peters5e824c32001-08-12 22:25:01 +0000968 # don't synch up unless the lines have a similarity score of at
969 # least cutoff; best_ratio tracks the best score seen so far
970 best_ratio, cutoff = 0.74, 0.75
971 cruncher = SequenceMatcher(self.charjunk)
972 eqi, eqj = None, None # 1st indices of equal lines (if any)
973
974 # search for the pair that matches best without being identical
975 # (identical lines must be junk lines, & we don't want to synch up
976 # on junk -- unless we have to)
Guido van Rossum805365e2007-05-07 22:24:25 +0000977 for j in range(blo, bhi):
Tim Peters5e824c32001-08-12 22:25:01 +0000978 bj = b[j]
979 cruncher.set_seq2(bj)
Guido van Rossum805365e2007-05-07 22:24:25 +0000980 for i in range(alo, ahi):
Tim Peters5e824c32001-08-12 22:25:01 +0000981 ai = a[i]
982 if ai == bj:
983 if eqi is None:
984 eqi, eqj = i, j
985 continue
986 cruncher.set_seq1(ai)
987 # computing similarity is expensive, so use the quick
988 # upper bounds first -- have seen this speed up messy
989 # compares by a factor of 3.
990 # note that ratio() is only expensive to compute the first
991 # time it's called on a sequence pair; the expensive part
992 # of the computation is cached by cruncher
993 if cruncher.real_quick_ratio() > best_ratio and \
994 cruncher.quick_ratio() > best_ratio and \
995 cruncher.ratio() > best_ratio:
996 best_ratio, best_i, best_j = cruncher.ratio(), i, j
997 if best_ratio < cutoff:
998 # no non-identical "pretty close" pair
999 if eqi is None:
1000 # no identical pair either -- treat it as a straight replace
Tim Peters8a9c2842001-09-22 21:30:22 +00001001 for line in self._plain_replace(a, alo, ahi, b, blo, bhi):
1002 yield line
Tim Peters5e824c32001-08-12 22:25:01 +00001003 return
1004 # no close pair, but an identical pair -- synch up on that
1005 best_i, best_j, best_ratio = eqi, eqj, 1.0
1006 else:
1007 # there's a close pair, so forget the identical pair (if any)
1008 eqi = None
1009
1010 # a[best_i] very similar to b[best_j]; eqi is None iff they're not
1011 # identical
Tim Peters5e824c32001-08-12 22:25:01 +00001012
1013 # pump out diffs from before the synch point
Tim Peters8a9c2842001-09-22 21:30:22 +00001014 for line in self._fancy_helper(a, alo, best_i, b, blo, best_j):
1015 yield line
Tim Peters5e824c32001-08-12 22:25:01 +00001016
1017 # do intraline marking on the synch pair
1018 aelt, belt = a[best_i], b[best_j]
1019 if eqi is None:
1020 # pump out a '-', '?', '+', '?' quad for the synched lines
1021 atags = btags = ""
1022 cruncher.set_seqs(aelt, belt)
1023 for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():
1024 la, lb = ai2 - ai1, bj2 - bj1
1025 if tag == 'replace':
1026 atags += '^' * la
1027 btags += '^' * lb
1028 elif tag == 'delete':
1029 atags += '-' * la
1030 elif tag == 'insert':
1031 btags += '+' * lb
1032 elif tag == 'equal':
1033 atags += ' ' * la
1034 btags += ' ' * lb
1035 else:
Collin Winterce36ad82007-08-30 01:19:48 +00001036 raise ValueError('unknown tag %r' % (tag,))
Tim Peters8a9c2842001-09-22 21:30:22 +00001037 for line in self._qformat(aelt, belt, atags, btags):
1038 yield line
Tim Peters5e824c32001-08-12 22:25:01 +00001039 else:
1040 # the synch pair is identical
Tim Peters8a9c2842001-09-22 21:30:22 +00001041 yield ' ' + aelt
Tim Peters5e824c32001-08-12 22:25:01 +00001042
1043 # pump out diffs from after the synch point
Tim Peters8a9c2842001-09-22 21:30:22 +00001044 for line in self._fancy_helper(a, best_i+1, ahi, b, best_j+1, bhi):
1045 yield line
Tim Peters5e824c32001-08-12 22:25:01 +00001046
1047 def _fancy_helper(self, a, alo, ahi, b, blo, bhi):
Tim Peters8a9c2842001-09-22 21:30:22 +00001048 g = []
Tim Peters5e824c32001-08-12 22:25:01 +00001049 if alo < ahi:
1050 if blo < bhi:
Tim Peters8a9c2842001-09-22 21:30:22 +00001051 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
Tim Peters5e824c32001-08-12 22:25:01 +00001052 else:
Tim Peters8a9c2842001-09-22 21:30:22 +00001053 g = self._dump('-', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +00001054 elif blo < bhi:
Tim Peters8a9c2842001-09-22 21:30:22 +00001055 g = self._dump('+', b, blo, bhi)
1056
1057 for line in g:
1058 yield line
Tim Peters5e824c32001-08-12 22:25:01 +00001059
1060 def _qformat(self, aline, bline, atags, btags):
1061 r"""
1062 Format "?" output and deal with leading tabs.
1063
1064 Example:
1065
1066 >>> d = Differ()
Senthil Kumaran758025c2009-11-23 19:02:52 +00001067 >>> results = d._qformat('\tabcDefghiJkl\n', '\tabcdefGhijkl\n',
1068 ... ' ^ ^ ^ ', ' ^ ^ ^ ')
Guido van Rossumfff80df2007-02-09 20:33:44 +00001069 >>> for line in results: print(repr(line))
1070 ...
Tim Peters5e824c32001-08-12 22:25:01 +00001071 '- \tabcDefghiJkl\n'
1072 '? \t ^ ^ ^\n'
Senthil Kumaran758025c2009-11-23 19:02:52 +00001073 '+ \tabcdefGhijkl\n'
1074 '? \t ^ ^ ^\n'
Tim Peters5e824c32001-08-12 22:25:01 +00001075 """
1076
1077 # Can hurt, but will probably help most of the time.
1078 common = min(_count_leading(aline, "\t"),
1079 _count_leading(bline, "\t"))
1080 common = min(common, _count_leading(atags[:common], " "))
Senthil Kumaran758025c2009-11-23 19:02:52 +00001081 common = min(common, _count_leading(btags[:common], " "))
Tim Peters5e824c32001-08-12 22:25:01 +00001082 atags = atags[common:].rstrip()
1083 btags = btags[common:].rstrip()
1084
Tim Peters8a9c2842001-09-22 21:30:22 +00001085 yield "- " + aline
Tim Peters5e824c32001-08-12 22:25:01 +00001086 if atags:
Tim Peters527e64f2001-10-04 05:36:56 +00001087 yield "? %s%s\n" % ("\t" * common, atags)
Tim Peters5e824c32001-08-12 22:25:01 +00001088
Tim Peters8a9c2842001-09-22 21:30:22 +00001089 yield "+ " + bline
Tim Peters5e824c32001-08-12 22:25:01 +00001090 if btags:
Tim Peters8a9c2842001-09-22 21:30:22 +00001091 yield "? %s%s\n" % ("\t" * common, btags)
Tim Peters5e824c32001-08-12 22:25:01 +00001092
1093# With respect to junk, an earlier version of ndiff simply refused to
1094# *start* a match with a junk element. The result was cases like this:
1095# before: private Thread currentThread;
1096# after: private volatile Thread currentThread;
1097# If you consider whitespace to be junk, the longest contiguous match
1098# not starting with junk is "e Thread currentThread". So ndiff reported
1099# that "e volatil" was inserted between the 't' and the 'e' in "private".
1100# While an accurate view, to people that's absurd. The current version
1101# looks for matching blocks that are entirely junk-free, then extends the
1102# longest one of those as far as possible but only with matching junk.
1103# So now "currentThread" is matched, then extended to suck up the
1104# preceding blank; then "private" is matched, and extended to suck up the
1105# following blank; then "Thread" is matched; and finally ndiff reports
1106# that "volatile " was inserted before "Thread". The only quibble
1107# remaining is that perhaps it was really the case that " volatile"
1108# was inserted after "private". I can live with that <wink>.
1109
1110import re
1111
1112def IS_LINE_JUNK(line, pat=re.compile(r"\s*#?\s*$").match):
1113 r"""
1114 Return 1 for ignorable line: iff `line` is blank or contains a single '#'.
1115
1116 Examples:
1117
1118 >>> IS_LINE_JUNK('\n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001119 True
Tim Peters5e824c32001-08-12 22:25:01 +00001120 >>> IS_LINE_JUNK(' # \n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001121 True
Tim Peters5e824c32001-08-12 22:25:01 +00001122 >>> IS_LINE_JUNK('hello\n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001123 False
Tim Peters5e824c32001-08-12 22:25:01 +00001124 """
1125
1126 return pat(line) is not None
1127
1128def IS_CHARACTER_JUNK(ch, ws=" \t"):
1129 r"""
1130 Return 1 for ignorable character: iff `ch` is a space or tab.
1131
1132 Examples:
1133
1134 >>> IS_CHARACTER_JUNK(' ')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001135 True
Tim Peters5e824c32001-08-12 22:25:01 +00001136 >>> IS_CHARACTER_JUNK('\t')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001137 True
Tim Peters5e824c32001-08-12 22:25:01 +00001138 >>> IS_CHARACTER_JUNK('\n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001139 False
Tim Peters5e824c32001-08-12 22:25:01 +00001140 >>> IS_CHARACTER_JUNK('x')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001141 False
Tim Peters5e824c32001-08-12 22:25:01 +00001142 """
1143
1144 return ch in ws
1145
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001146
Raymond Hettingerf03d3022011-04-12 15:19:33 -07001147########################################################################
1148### Unified Diff
1149########################################################################
1150
1151def _format_range_unified(start, stop):
Raymond Hettinger49353d02011-04-11 12:40:58 -07001152 'Convert range to the "ed" format'
1153 # Per the diff spec at http://www.unix.org/single_unix_specification/
1154 beginning = start + 1 # lines start numbering with one
1155 length = stop - start
1156 if length == 1:
1157 return '{}'.format(beginning)
1158 if not length:
1159 beginning -= 1 # empty ranges begin at line just before the range
1160 return '{},{}'.format(beginning, length)
1161
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001162def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
1163 tofiledate='', n=3, lineterm='\n'):
1164 r"""
1165 Compare two sequences of lines; generate the delta as a unified diff.
1166
1167 Unified diffs are a compact way of showing line changes and a few
1168 lines of context. The number of context lines is set by 'n' which
1169 defaults to three.
1170
Raymond Hettinger0887c732003-06-17 16:53:25 +00001171 By default, the diff control lines (those with ---, +++, or @@) are
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001172 created with a trailing newline. This is helpful so that inputs
1173 created from file.readlines() result in diffs that are suitable for
1174 file.writelines() since both the inputs and outputs have trailing
1175 newlines.
1176
1177 For inputs that do not have trailing newlines, set the lineterm
1178 argument to "" so that the output will be uniformly newline free.
1179
1180 The unidiff format normally has a header for filenames and modification
1181 times. Any or all of these may be specified using strings for
R. David Murrayb2416e52010-04-12 16:58:02 +00001182 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
1183 The modification times are normally expressed in the ISO 8601 format.
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001184
1185 Example:
1186
1187 >>> for line in unified_diff('one two three four'.split(),
1188 ... 'zero one tree four'.split(), 'Original', 'Current',
R. David Murrayb2416e52010-04-12 16:58:02 +00001189 ... '2005-01-26 23:30:50', '2010-04-02 10:20:52',
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001190 ... lineterm=''):
R. David Murrayb2416e52010-04-12 16:58:02 +00001191 ... print(line) # doctest: +NORMALIZE_WHITESPACE
1192 --- Original 2005-01-26 23:30:50
1193 +++ Current 2010-04-02 10:20:52
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001194 @@ -1,4 +1,4 @@
1195 +zero
1196 one
1197 -two
1198 -three
1199 +tree
1200 four
1201 """
1202
1203 started = False
1204 for group in SequenceMatcher(None,a,b).get_grouped_opcodes(n):
1205 if not started:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001206 started = True
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001207 fromdate = '\t{}'.format(fromfiledate) if fromfiledate else ''
1208 todate = '\t{}'.format(tofiledate) if tofiledate else ''
1209 yield '--- {}{}{}'.format(fromfile, fromdate, lineterm)
1210 yield '+++ {}{}{}'.format(tofile, todate, lineterm)
Raymond Hettinger49353d02011-04-11 12:40:58 -07001211
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001212 first, last = group[0], group[-1]
Raymond Hettingerf03d3022011-04-12 15:19:33 -07001213 file1_range = _format_range_unified(first[1], last[2])
1214 file2_range = _format_range_unified(first[3], last[4])
Raymond Hettinger49353d02011-04-11 12:40:58 -07001215 yield '@@ -{} +{} @@{}'.format(file1_range, file2_range, lineterm)
1216
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001217 for tag, i1, i2, j1, j2 in group:
1218 if tag == 'equal':
1219 for line in a[i1:i2]:
1220 yield ' ' + line
1221 continue
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001222 if tag in {'replace', 'delete'}:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001223 for line in a[i1:i2]:
1224 yield '-' + line
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001225 if tag in {'replace', 'insert'}:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001226 for line in b[j1:j2]:
1227 yield '+' + line
1228
Raymond Hettingerf03d3022011-04-12 15:19:33 -07001229
1230########################################################################
1231### Context Diff
1232########################################################################
1233
1234def _format_range_context(start, stop):
1235 'Convert range to the "ed" format'
1236 # Per the diff spec at http://www.unix.org/single_unix_specification/
1237 beginning = start + 1 # lines start numbering with one
1238 length = stop - start
1239 if not length:
1240 beginning -= 1 # empty ranges begin at line just before the range
1241 if length <= 1:
1242 return '{}'.format(beginning)
1243 return '{},{}'.format(beginning, beginning + length - 1)
1244
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001245# See http://www.unix.org/single_unix_specification/
1246def context_diff(a, b, fromfile='', tofile='',
1247 fromfiledate='', tofiledate='', n=3, lineterm='\n'):
1248 r"""
1249 Compare two sequences of lines; generate the delta as a context diff.
1250
1251 Context diffs are a compact way of showing line changes and a few
1252 lines of context. The number of context lines is set by 'n' which
1253 defaults to three.
1254
1255 By default, the diff control lines (those with *** or ---) are
1256 created with a trailing newline. This is helpful so that inputs
1257 created from file.readlines() result in diffs that are suitable for
1258 file.writelines() since both the inputs and outputs have trailing
1259 newlines.
1260
1261 For inputs that do not have trailing newlines, set the lineterm
1262 argument to "" so that the output will be uniformly newline free.
1263
1264 The context diff format normally has a header for filenames and
1265 modification times. Any or all of these may be specified using
1266 strings for 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
R. David Murrayb2416e52010-04-12 16:58:02 +00001267 The modification times are normally expressed in the ISO 8601 format.
1268 If not specified, the strings default to blanks.
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001269
1270 Example:
1271
Guido van Rossumbe19ed72007-02-09 05:37:30 +00001272 >>> print(''.join(context_diff('one\ntwo\nthree\nfour\n'.splitlines(1),
R. David Murrayb2416e52010-04-12 16:58:02 +00001273 ... 'zero\none\ntree\nfour\n'.splitlines(1), 'Original', 'Current')),
Guido van Rossumbe19ed72007-02-09 05:37:30 +00001274 ... end="")
R. David Murrayb2416e52010-04-12 16:58:02 +00001275 *** Original
1276 --- Current
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001277 ***************
1278 *** 1,4 ****
1279 one
1280 ! two
1281 ! three
1282 four
1283 --- 1,4 ----
1284 + zero
1285 one
1286 ! tree
1287 four
1288 """
1289
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001290 prefix = dict(insert='+ ', delete='- ', replace='! ', equal=' ')
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001291 started = False
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001292 for group in SequenceMatcher(None,a,b).get_grouped_opcodes(n):
1293 if not started:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001294 started = True
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001295 fromdate = '\t{}'.format(fromfiledate) if fromfiledate else ''
1296 todate = '\t{}'.format(tofiledate) if tofiledate else ''
1297 yield '*** {}{}{}'.format(fromfile, fromdate, lineterm)
1298 yield '--- {}{}{}'.format(tofile, todate, lineterm)
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001299
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001300 first, last = group[0], group[-1]
Raymond Hettinger49353d02011-04-11 12:40:58 -07001301 yield '***************' + lineterm
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001302
Raymond Hettingerf03d3022011-04-12 15:19:33 -07001303 file1_range = _format_range_context(first[1], last[2])
Raymond Hettinger49353d02011-04-11 12:40:58 -07001304 yield '*** {} ****{}'.format(file1_range, lineterm)
1305
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001306 if any(tag in {'replace', 'delete'} for tag, _, _, _, _ in group):
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001307 for tag, i1, i2, _, _ in group:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001308 if tag != 'insert':
1309 for line in a[i1:i2]:
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001310 yield prefix[tag] + line
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001311
Raymond Hettingerf03d3022011-04-12 15:19:33 -07001312 file2_range = _format_range_context(first[3], last[4])
Raymond Hettinger49353d02011-04-11 12:40:58 -07001313 yield '--- {} ----{}'.format(file2_range, lineterm)
1314
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001315 if any(tag in {'replace', 'insert'} for tag, _, _, _, _ in group):
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001316 for tag, _, _, j1, j2 in group:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001317 if tag != 'delete':
1318 for line in b[j1:j2]:
Raymond Hettinger47e120e2011-04-10 17:14:56 -07001319 yield prefix[tag] + line
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001320
Tim Peters81b92512002-04-29 01:37:32 +00001321def ndiff(a, b, linejunk=None, charjunk=IS_CHARACTER_JUNK):
Tim Peters5e824c32001-08-12 22:25:01 +00001322 r"""
1323 Compare `a` and `b` (lists of strings); return a `Differ`-style delta.
1324
1325 Optional keyword parameters `linejunk` and `charjunk` are for filter
1326 functions (or None):
1327
1328 - linejunk: A function that should accept a single string argument, and
Tim Peters81b92512002-04-29 01:37:32 +00001329 return true iff the string is junk. The default is None, and is
1330 recommended; as of Python 2.3, an adaptive notion of "noise" lines is
1331 used that does a good job on its own.
Tim Peters5e824c32001-08-12 22:25:01 +00001332
1333 - charjunk: A function that should accept a string of length 1. The
1334 default is module-level function IS_CHARACTER_JUNK, which filters out
1335 whitespace characters (a blank or tab; note: bad idea to include newline
1336 in this!).
1337
1338 Tools/scripts/ndiff.py is a command-line front-end to this function.
1339
1340 Example:
1341
1342 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1343 ... 'ore\ntree\nemu\n'.splitlines(1))
Guido van Rossumbe19ed72007-02-09 05:37:30 +00001344 >>> print(''.join(diff), end="")
Tim Peters5e824c32001-08-12 22:25:01 +00001345 - one
1346 ? ^
1347 + ore
1348 ? ^
1349 - two
1350 - three
1351 ? -
1352 + tree
1353 + emu
1354 """
1355 return Differ(linejunk, charjunk).compare(a, b)
1356
Martin v. Löwise064b412004-08-29 16:34:40 +00001357def _mdiff(fromlines, tolines, context=None, linejunk=None,
1358 charjunk=IS_CHARACTER_JUNK):
Thomas Wouters902d6eb2007-01-09 23:18:33 +00001359 r"""Returns generator yielding marked up from/to side by side differences.
Martin v. Löwise064b412004-08-29 16:34:40 +00001360
1361 Arguments:
1362 fromlines -- list of text lines to compared to tolines
1363 tolines -- list of text lines to be compared to fromlines
1364 context -- number of context lines to display on each side of difference,
1365 if None, all from/to text lines will be generated.
1366 linejunk -- passed on to ndiff (see ndiff documentation)
1367 charjunk -- passed on to ndiff (see ndiff documentation)
Tim Peters48bd7f32004-08-29 22:38:38 +00001368
Martin v. Löwise064b412004-08-29 16:34:40 +00001369 This function returns an interator which returns a tuple:
1370 (from line tuple, to line tuple, boolean flag)
1371
1372 from/to line tuple -- (line num, line text)
Mark Dickinson934896d2009-02-21 20:59:32 +00001373 line num -- integer or None (to indicate a context separation)
Martin v. Löwise064b412004-08-29 16:34:40 +00001374 line text -- original line text with following markers inserted:
1375 '\0+' -- marks start of added text
1376 '\0-' -- marks start of deleted text
1377 '\0^' -- marks start of changed text
1378 '\1' -- marks end of added/deleted/changed text
Tim Peters48bd7f32004-08-29 22:38:38 +00001379
Martin v. Löwise064b412004-08-29 16:34:40 +00001380 boolean flag -- None indicates context separation, True indicates
1381 either "from" or "to" line contains a change, otherwise False.
1382
1383 This function/iterator was originally developed to generate side by side
1384 file difference for making HTML pages (see HtmlDiff class for example
1385 usage).
1386
1387 Note, this function utilizes the ndiff function to generate the side by
1388 side difference markup. Optional ndiff arguments may be passed to this
Tim Peters48bd7f32004-08-29 22:38:38 +00001389 function and they in turn will be passed to ndiff.
Martin v. Löwise064b412004-08-29 16:34:40 +00001390 """
Tim Peters48bd7f32004-08-29 22:38:38 +00001391 import re
Martin v. Löwise064b412004-08-29 16:34:40 +00001392
1393 # regular expression for finding intraline change indices
1394 change_re = re.compile('(\++|\-+|\^+)')
Tim Peters48bd7f32004-08-29 22:38:38 +00001395
Martin v. Löwise064b412004-08-29 16:34:40 +00001396 # create the difference iterator to generate the differences
1397 diff_lines_iterator = ndiff(fromlines,tolines,linejunk,charjunk)
1398
1399 def _make_line(lines, format_key, side, num_lines=[0,0]):
1400 """Returns line of text with user's change markup and line formatting.
1401
1402 lines -- list of lines from the ndiff generator to produce a line of
1403 text from. When producing the line of text to return, the
1404 lines used are removed from this list.
1405 format_key -- '+' return first line in list with "add" markup around
1406 the entire line.
1407 '-' return first line in list with "delete" markup around
1408 the entire line.
1409 '?' return first line in list with add/delete/change
1410 intraline markup (indices obtained from second line)
1411 None return first line in list with no markup
1412 side -- indice into the num_lines list (0=from,1=to)
1413 num_lines -- from/to current line number. This is NOT intended to be a
1414 passed parameter. It is present as a keyword argument to
1415 maintain memory of the current line numbers between calls
1416 of this function.
1417
1418 Note, this function is purposefully not defined at the module scope so
1419 that data it needs from its parent function (within whose context it
1420 is defined) does not need to be of module scope.
1421 """
1422 num_lines[side] += 1
1423 # Handle case where no user markup is to be added, just return line of
1424 # text with user's line format to allow for usage of the line number.
1425 if format_key is None:
1426 return (num_lines[side],lines.pop(0)[2:])
1427 # Handle case of intraline changes
1428 if format_key == '?':
1429 text, markers = lines.pop(0), lines.pop(0)
1430 # find intraline changes (store change type and indices in tuples)
1431 sub_info = []
1432 def record_sub_info(match_object,sub_info=sub_info):
1433 sub_info.append([match_object.group(1)[0],match_object.span()])
1434 return match_object.group(1)
1435 change_re.sub(record_sub_info,markers)
1436 # process each tuple inserting our special marks that won't be
1437 # noticed by an xml/html escaper.
1438 for key,(begin,end) in sub_info[::-1]:
1439 text = text[0:begin]+'\0'+key+text[begin:end]+'\1'+text[end:]
1440 text = text[2:]
1441 # Handle case of add/delete entire line
1442 else:
1443 text = lines.pop(0)[2:]
1444 # if line of text is just a newline, insert a space so there is
1445 # something for the user to highlight and see.
Tim Peters0ca0c642004-11-12 16:12:15 +00001446 if not text:
1447 text = ' '
Martin v. Löwise064b412004-08-29 16:34:40 +00001448 # insert marks that won't be noticed by an xml/html escaper.
1449 text = '\0' + format_key + text + '\1'
Georg Brandl7eb4b7d2005-07-22 21:49:32 +00001450 # Return line of text, first allow user's line formatter to do its
Martin v. Löwise064b412004-08-29 16:34:40 +00001451 # thing (such as adding the line number) then replace the special
1452 # marks with what the user's change markup.
1453 return (num_lines[side],text)
Tim Peters48bd7f32004-08-29 22:38:38 +00001454
Martin v. Löwise064b412004-08-29 16:34:40 +00001455 def _line_iterator():
1456 """Yields from/to lines of text with a change indication.
1457
1458 This function is an iterator. It itself pulls lines from a
1459 differencing iterator, processes them and yields them. When it can
1460 it yields both a "from" and a "to" line, otherwise it will yield one
1461 or the other. In addition to yielding the lines of from/to text, a
1462 boolean flag is yielded to indicate if the text line(s) have
1463 differences in them.
1464
1465 Note, this function is purposefully not defined at the module scope so
1466 that data it needs from its parent function (within whose context it
1467 is defined) does not need to be of module scope.
1468 """
1469 lines = []
1470 num_blanks_pending, num_blanks_to_yield = 0, 0
Tim Peters48bd7f32004-08-29 22:38:38 +00001471 while True:
Martin v. Löwise064b412004-08-29 16:34:40 +00001472 # Load up next 4 lines so we can look ahead, create strings which
1473 # are a concatenation of the first character of each of the 4 lines
1474 # so we can do some very readable comparisons.
1475 while len(lines) < 4:
1476 try:
Georg Brandla18af4e2007-04-21 15:47:16 +00001477 lines.append(next(diff_lines_iterator))
Martin v. Löwise064b412004-08-29 16:34:40 +00001478 except StopIteration:
1479 lines.append('X')
1480 s = ''.join([line[0] for line in lines])
1481 if s.startswith('X'):
1482 # When no more lines, pump out any remaining blank lines so the
1483 # corresponding add/delete lines get a matching blank line so
1484 # all line pairs get yielded at the next level.
1485 num_blanks_to_yield = num_blanks_pending
1486 elif s.startswith('-?+?'):
1487 # simple intraline change
1488 yield _make_line(lines,'?',0), _make_line(lines,'?',1), True
1489 continue
1490 elif s.startswith('--++'):
1491 # in delete block, add block coming: we do NOT want to get
1492 # caught up on blank lines yet, just process the delete line
1493 num_blanks_pending -= 1
1494 yield _make_line(lines,'-',0), None, True
1495 continue
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001496 elif s.startswith(('--?+', '--+', '- ')):
Martin v. Löwise064b412004-08-29 16:34:40 +00001497 # in delete block and see a intraline change or unchanged line
1498 # coming: yield the delete line and then blanks
1499 from_line,to_line = _make_line(lines,'-',0), None
1500 num_blanks_to_yield,num_blanks_pending = num_blanks_pending-1,0
1501 elif s.startswith('-+?'):
1502 # intraline change
1503 yield _make_line(lines,None,0), _make_line(lines,'?',1), True
1504 continue
1505 elif s.startswith('-?+'):
1506 # intraline change
1507 yield _make_line(lines,'?',0), _make_line(lines,None,1), True
1508 continue
1509 elif s.startswith('-'):
1510 # delete FROM line
1511 num_blanks_pending -= 1
1512 yield _make_line(lines,'-',0), None, True
1513 continue
1514 elif s.startswith('+--'):
1515 # in add block, delete block coming: we do NOT want to get
1516 # caught up on blank lines yet, just process the add line
1517 num_blanks_pending += 1
1518 yield None, _make_line(lines,'+',1), True
1519 continue
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001520 elif s.startswith(('+ ', '+-')):
Martin v. Löwise064b412004-08-29 16:34:40 +00001521 # will be leaving an add block: yield blanks then add line
1522 from_line, to_line = None, _make_line(lines,'+',1)
1523 num_blanks_to_yield,num_blanks_pending = num_blanks_pending+1,0
1524 elif s.startswith('+'):
1525 # inside an add block, yield the add line
1526 num_blanks_pending += 1
1527 yield None, _make_line(lines,'+',1), True
1528 continue
1529 elif s.startswith(' '):
1530 # unchanged text, yield it to both sides
1531 yield _make_line(lines[:],None,0),_make_line(lines,None,1),False
1532 continue
1533 # Catch up on the blank lines so when we yield the next from/to
1534 # pair, they are lined up.
1535 while(num_blanks_to_yield < 0):
1536 num_blanks_to_yield += 1
1537 yield None,('','\n'),True
1538 while(num_blanks_to_yield > 0):
1539 num_blanks_to_yield -= 1
1540 yield ('','\n'),None,True
1541 if s.startswith('X'):
1542 raise StopIteration
1543 else:
1544 yield from_line,to_line,True
1545
1546 def _line_pair_iterator():
1547 """Yields from/to lines of text with a change indication.
1548
1549 This function is an iterator. It itself pulls lines from the line
Georg Brandl7eb4b7d2005-07-22 21:49:32 +00001550 iterator. Its difference from that iterator is that this function
Martin v. Löwise064b412004-08-29 16:34:40 +00001551 always yields a pair of from/to text lines (with the change
1552 indication). If necessary it will collect single from/to lines
1553 until it has a matching pair from/to pair to yield.
1554
1555 Note, this function is purposefully not defined at the module scope so
1556 that data it needs from its parent function (within whose context it
1557 is defined) does not need to be of module scope.
1558 """
1559 line_iterator = _line_iterator()
1560 fromlines,tolines=[],[]
1561 while True:
1562 # Collecting lines of text until we have a from/to pair
1563 while (len(fromlines)==0 or len(tolines)==0):
Georg Brandla18af4e2007-04-21 15:47:16 +00001564 from_line, to_line, found_diff = next(line_iterator)
Martin v. Löwise064b412004-08-29 16:34:40 +00001565 if from_line is not None:
1566 fromlines.append((from_line,found_diff))
1567 if to_line is not None:
1568 tolines.append((to_line,found_diff))
1569 # Once we have a pair, remove them from the collection and yield it
1570 from_line, fromDiff = fromlines.pop(0)
1571 to_line, to_diff = tolines.pop(0)
1572 yield (from_line,to_line,fromDiff or to_diff)
1573
1574 # Handle case where user does not want context differencing, just yield
1575 # them up without doing anything else with them.
1576 line_pair_iterator = _line_pair_iterator()
1577 if context is None:
1578 while True:
Georg Brandla18af4e2007-04-21 15:47:16 +00001579 yield next(line_pair_iterator)
Martin v. Löwise064b412004-08-29 16:34:40 +00001580 # Handle case where user wants context differencing. We must do some
1581 # storage of lines until we know for sure that they are to be yielded.
1582 else:
1583 context += 1
1584 lines_to_write = 0
1585 while True:
1586 # Store lines up until we find a difference, note use of a
1587 # circular queue because we only need to keep around what
1588 # we need for context.
1589 index, contextLines = 0, [None]*(context)
1590 found_diff = False
1591 while(found_diff is False):
Georg Brandla18af4e2007-04-21 15:47:16 +00001592 from_line, to_line, found_diff = next(line_pair_iterator)
Martin v. Löwise064b412004-08-29 16:34:40 +00001593 i = index % context
1594 contextLines[i] = (from_line, to_line, found_diff)
1595 index += 1
1596 # Yield lines that we have collected so far, but first yield
1597 # the user's separator.
1598 if index > context:
1599 yield None, None, None
1600 lines_to_write = context
1601 else:
1602 lines_to_write = index
1603 index = 0
1604 while(lines_to_write):
1605 i = index % context
1606 index += 1
1607 yield contextLines[i]
1608 lines_to_write -= 1
1609 # Now yield the context lines after the change
1610 lines_to_write = context-1
1611 while(lines_to_write):
Georg Brandla18af4e2007-04-21 15:47:16 +00001612 from_line, to_line, found_diff = next(line_pair_iterator)
Martin v. Löwise064b412004-08-29 16:34:40 +00001613 # If another change within the context, extend the context
1614 if found_diff:
1615 lines_to_write = context-1
1616 else:
1617 lines_to_write -= 1
1618 yield from_line, to_line, found_diff
1619
1620
1621_file_template = """
1622<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
1623 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
1624
1625<html>
1626
1627<head>
Tim Peters48bd7f32004-08-29 22:38:38 +00001628 <meta http-equiv="Content-Type"
Martin v. Löwise064b412004-08-29 16:34:40 +00001629 content="text/html; charset=ISO-8859-1" />
1630 <title></title>
1631 <style type="text/css">%(styles)s
1632 </style>
1633</head>
1634
1635<body>
1636 %(table)s%(legend)s
1637</body>
1638
1639</html>"""
1640
1641_styles = """
1642 table.diff {font-family:Courier; border:medium;}
1643 .diff_header {background-color:#e0e0e0}
1644 td.diff_header {text-align:right}
1645 .diff_next {background-color:#c0c0c0}
1646 .diff_add {background-color:#aaffaa}
1647 .diff_chg {background-color:#ffff77}
1648 .diff_sub {background-color:#ffaaaa}"""
1649
1650_table_template = """
Tim Peters48bd7f32004-08-29 22:38:38 +00001651 <table class="diff" id="difflib_chg_%(prefix)s_top"
1652 cellspacing="0" cellpadding="0" rules="groups" >
1653 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
Martin v. Löwise064b412004-08-29 16:34:40 +00001654 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
1655 %(header_row)s
1656 <tbody>
1657%(data_rows)s </tbody>
1658 </table>"""
1659
1660_legend = """
1661 <table class="diff" summary="Legends">
1662 <tr> <th colspan="2"> Legends </th> </tr>
1663 <tr> <td> <table border="" summary="Colors">
1664 <tr><th> Colors </th> </tr>
1665 <tr><td class="diff_add">&nbsp;Added&nbsp;</td></tr>
1666 <tr><td class="diff_chg">Changed</td> </tr>
1667 <tr><td class="diff_sub">Deleted</td> </tr>
1668 </table></td>
1669 <td> <table border="" summary="Links">
1670 <tr><th colspan="2"> Links </th> </tr>
1671 <tr><td>(f)irst change</td> </tr>
1672 <tr><td>(n)ext change</td> </tr>
1673 <tr><td>(t)op</td> </tr>
1674 </table></td> </tr>
1675 </table>"""
1676
1677class HtmlDiff(object):
1678 """For producing HTML side by side comparison with change highlights.
1679
1680 This class can be used to create an HTML table (or a complete HTML file
Andrew M. Kuchling55be9ea2004-09-10 12:59:54 +00001681 containing the table) showing a side by side, line by line comparison
Tim Peters48bd7f32004-08-29 22:38:38 +00001682 of text with inter-line and intra-line change highlights. The table can
Martin v. Löwise064b412004-08-29 16:34:40 +00001683 be generated in either full or contextual difference mode.
Tim Peters48bd7f32004-08-29 22:38:38 +00001684
Martin v. Löwise064b412004-08-29 16:34:40 +00001685 The following methods are provided for HTML generation:
1686
1687 make_table -- generates HTML for a single side by side table
1688 make_file -- generates complete HTML file with a single side by side table
1689
Tim Peters48bd7f32004-08-29 22:38:38 +00001690 See tools/scripts/diff.py for an example usage of this class.
Martin v. Löwise064b412004-08-29 16:34:40 +00001691 """
1692
1693 _file_template = _file_template
1694 _styles = _styles
1695 _table_template = _table_template
1696 _legend = _legend
1697 _default_prefix = 0
Tim Peters48bd7f32004-08-29 22:38:38 +00001698
Martin v. Löwise064b412004-08-29 16:34:40 +00001699 def __init__(self,tabsize=8,wrapcolumn=None,linejunk=None,
1700 charjunk=IS_CHARACTER_JUNK):
1701 """HtmlDiff instance initializer
1702
1703 Arguments:
1704 tabsize -- tab stop spacing, defaults to 8.
1705 wrapcolumn -- column number where lines are broken and wrapped,
1706 defaults to None where lines are not wrapped.
1707 linejunk,charjunk -- keyword arguments passed into ndiff() (used to by
Tim Peters48bd7f32004-08-29 22:38:38 +00001708 HtmlDiff() to generate the side by side HTML differences). See
Martin v. Löwise064b412004-08-29 16:34:40 +00001709 ndiff() documentation for argument default values and descriptions.
1710 """
1711 self._tabsize = tabsize
1712 self._wrapcolumn = wrapcolumn
1713 self._linejunk = linejunk
1714 self._charjunk = charjunk
1715
1716 def make_file(self,fromlines,tolines,fromdesc='',todesc='',context=False,
1717 numlines=5):
1718 """Returns HTML file of side by side comparison with change highlights
1719
1720 Arguments:
1721 fromlines -- list of "from" lines
1722 tolines -- list of "to" lines
1723 fromdesc -- "from" file column header string
1724 todesc -- "to" file column header string
1725 context -- set to True for contextual differences (defaults to False
1726 which shows full differences).
1727 numlines -- number of context lines. When context is set True,
1728 controls number of lines displayed before and after the change.
1729 When context is False, controls the number of lines to place
1730 the "next" link anchors before the next change (so click of
1731 "next" link jumps to just before the change).
1732 """
Tim Peters48bd7f32004-08-29 22:38:38 +00001733
Martin v. Löwise064b412004-08-29 16:34:40 +00001734 return self._file_template % dict(
1735 styles = self._styles,
1736 legend = self._legend,
1737 table = self.make_table(fromlines,tolines,fromdesc,todesc,
1738 context=context,numlines=numlines))
Tim Peters48bd7f32004-08-29 22:38:38 +00001739
Martin v. Löwise064b412004-08-29 16:34:40 +00001740 def _tab_newline_replace(self,fromlines,tolines):
1741 """Returns from/to line lists with tabs expanded and newlines removed.
1742
1743 Instead of tab characters being replaced by the number of spaces
1744 needed to fill in to the next tab stop, this function will fill
1745 the space with tab characters. This is done so that the difference
1746 algorithms can identify changes in a file when tabs are replaced by
1747 spaces and vice versa. At the end of the HTML generation, the tab
1748 characters will be replaced with a nonbreakable space.
1749 """
1750 def expand_tabs(line):
1751 # hide real spaces
1752 line = line.replace(' ','\0')
1753 # expand tabs into spaces
1754 line = line.expandtabs(self._tabsize)
Ezio Melotti13925002011-03-16 11:05:33 +02001755 # replace spaces from expanded tabs back into tab characters
Martin v. Löwise064b412004-08-29 16:34:40 +00001756 # (we'll replace them with markup after we do differencing)
1757 line = line.replace(' ','\t')
1758 return line.replace('\0',' ').rstrip('\n')
1759 fromlines = [expand_tabs(line) for line in fromlines]
1760 tolines = [expand_tabs(line) for line in tolines]
1761 return fromlines,tolines
1762
1763 def _split_line(self,data_list,line_num,text):
1764 """Builds list of text lines by splitting text lines at wrap point
1765
1766 This function will determine if the input text line needs to be
1767 wrapped (split) into separate lines. If so, the first wrap point
1768 will be determined and the first line appended to the output
1769 text line list. This function is used recursively to handle
1770 the second part of the split line to further split it.
1771 """
1772 # if blank line or context separator, just add it to the output list
1773 if not line_num:
1774 data_list.append((line_num,text))
1775 return
1776
1777 # if line text doesn't need wrapping, just add it to the output list
1778 size = len(text)
1779 max = self._wrapcolumn
1780 if (size <= max) or ((size -(text.count('\0')*3)) <= max):
1781 data_list.append((line_num,text))
1782 return
1783
1784 # scan text looking for the wrap point, keeping track if the wrap
1785 # point is inside markers
1786 i = 0
1787 n = 0
1788 mark = ''
1789 while n < max and i < size:
1790 if text[i] == '\0':
1791 i += 1
1792 mark = text[i]
1793 i += 1
1794 elif text[i] == '\1':
1795 i += 1
1796 mark = ''
1797 else:
1798 i += 1
1799 n += 1
1800
1801 # wrap point is inside text, break it up into separate lines
1802 line1 = text[:i]
1803 line2 = text[i:]
1804
1805 # if wrap point is inside markers, place end marker at end of first
1806 # line and start marker at beginning of second line because each
1807 # line will have its own table tag markup around it.
1808 if mark:
1809 line1 = line1 + '\1'
1810 line2 = '\0' + mark + line2
1811
Tim Peters48bd7f32004-08-29 22:38:38 +00001812 # tack on first line onto the output list
Martin v. Löwise064b412004-08-29 16:34:40 +00001813 data_list.append((line_num,line1))
1814
Tim Peters48bd7f32004-08-29 22:38:38 +00001815 # use this routine again to wrap the remaining text
Martin v. Löwise064b412004-08-29 16:34:40 +00001816 self._split_line(data_list,'>',line2)
1817
1818 def _line_wrapper(self,diffs):
1819 """Returns iterator that splits (wraps) mdiff text lines"""
1820
1821 # pull from/to data and flags from mdiff iterator
1822 for fromdata,todata,flag in diffs:
1823 # check for context separators and pass them through
1824 if flag is None:
1825 yield fromdata,todata,flag
1826 continue
1827 (fromline,fromtext),(toline,totext) = fromdata,todata
1828 # for each from/to line split it at the wrap column to form
1829 # list of text lines.
1830 fromlist,tolist = [],[]
1831 self._split_line(fromlist,fromline,fromtext)
1832 self._split_line(tolist,toline,totext)
1833 # yield from/to line in pairs inserting blank lines as
1834 # necessary when one side has more wrapped lines
1835 while fromlist or tolist:
1836 if fromlist:
1837 fromdata = fromlist.pop(0)
1838 else:
1839 fromdata = ('',' ')
1840 if tolist:
1841 todata = tolist.pop(0)
1842 else:
1843 todata = ('',' ')
1844 yield fromdata,todata,flag
1845
1846 def _collect_lines(self,diffs):
1847 """Collects mdiff output into separate lists
1848
1849 Before storing the mdiff from/to data into a list, it is converted
1850 into a single line of text with HTML markup.
1851 """
1852
1853 fromlist,tolist,flaglist = [],[],[]
Tim Peters48bd7f32004-08-29 22:38:38 +00001854 # pull from/to data and flags from mdiff style iterator
Martin v. Löwise064b412004-08-29 16:34:40 +00001855 for fromdata,todata,flag in diffs:
1856 try:
1857 # store HTML markup of the lines into the lists
1858 fromlist.append(self._format_line(0,flag,*fromdata))
1859 tolist.append(self._format_line(1,flag,*todata))
1860 except TypeError:
1861 # exceptions occur for lines where context separators go
1862 fromlist.append(None)
1863 tolist.append(None)
1864 flaglist.append(flag)
1865 return fromlist,tolist,flaglist
Tim Peters48bd7f32004-08-29 22:38:38 +00001866
Martin v. Löwise064b412004-08-29 16:34:40 +00001867 def _format_line(self,side,flag,linenum,text):
1868 """Returns HTML markup of "from" / "to" text lines
1869
1870 side -- 0 or 1 indicating "from" or "to" text
1871 flag -- indicates if difference on line
1872 linenum -- line number (used for line number column)
1873 text -- line text to be marked up
1874 """
1875 try:
1876 linenum = '%d' % linenum
1877 id = ' id="%s%s"' % (self._prefix[side],linenum)
1878 except TypeError:
1879 # handle blank lines where linenum is '>' or ''
Tim Peters48bd7f32004-08-29 22:38:38 +00001880 id = ''
Martin v. Löwise064b412004-08-29 16:34:40 +00001881 # replace those things that would get confused with HTML symbols
1882 text=text.replace("&","&amp;").replace(">","&gt;").replace("<","&lt;")
1883
1884 # make space non-breakable so they don't get compressed or line wrapped
1885 text = text.replace(' ','&nbsp;').rstrip()
1886
1887 return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' \
1888 % (id,linenum,text)
1889
1890 def _make_prefix(self):
1891 """Create unique anchor prefixes"""
1892
1893 # Generate a unique anchor prefix so multiple tables
1894 # can exist on the same HTML page without conflicts.
1895 fromprefix = "from%d_" % HtmlDiff._default_prefix
1896 toprefix = "to%d_" % HtmlDiff._default_prefix
1897 HtmlDiff._default_prefix += 1
1898 # store prefixes so line format method has access
1899 self._prefix = [fromprefix,toprefix]
1900
1901 def _convert_flags(self,fromlist,tolist,flaglist,context,numlines):
1902 """Makes list of "next" links"""
Tim Peters48bd7f32004-08-29 22:38:38 +00001903
Martin v. Löwise064b412004-08-29 16:34:40 +00001904 # all anchor names will be generated using the unique "to" prefix
1905 toprefix = self._prefix[1]
Tim Peters48bd7f32004-08-29 22:38:38 +00001906
Martin v. Löwise064b412004-08-29 16:34:40 +00001907 # process change flags, generating middle column of next anchors/links
1908 next_id = ['']*len(flaglist)
1909 next_href = ['']*len(flaglist)
1910 num_chg, in_change = 0, False
1911 last = 0
1912 for i,flag in enumerate(flaglist):
1913 if flag:
1914 if not in_change:
1915 in_change = True
1916 last = i
1917 # at the beginning of a change, drop an anchor a few lines
Tim Peters48bd7f32004-08-29 22:38:38 +00001918 # (the context lines) before the change for the previous
Martin v. Löwise064b412004-08-29 16:34:40 +00001919 # link
1920 i = max([0,i-numlines])
1921 next_id[i] = ' id="difflib_chg_%s_%d"' % (toprefix,num_chg)
Tim Peters48bd7f32004-08-29 22:38:38 +00001922 # at the beginning of a change, drop a link to the next
Martin v. Löwise064b412004-08-29 16:34:40 +00001923 # change
1924 num_chg += 1
1925 next_href[last] = '<a href="#difflib_chg_%s_%d">n</a>' % (
1926 toprefix,num_chg)
1927 else:
1928 in_change = False
1929 # check for cases where there is no content to avoid exceptions
1930 if not flaglist:
1931 flaglist = [False]
1932 next_id = ['']
1933 next_href = ['']
1934 last = 0
1935 if context:
1936 fromlist = ['<td></td><td>&nbsp;No Differences Found&nbsp;</td>']
1937 tolist = fromlist
1938 else:
1939 fromlist = tolist = ['<td></td><td>&nbsp;Empty File&nbsp;</td>']
1940 # if not a change on first line, drop a link
1941 if not flaglist[0]:
1942 next_href[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix
1943 # redo the last link to link to the top
1944 next_href[last] = '<a href="#difflib_chg_%s_top">t</a>' % (toprefix)
1945
1946 return fromlist,tolist,flaglist,next_href,next_id
1947
1948 def make_table(self,fromlines,tolines,fromdesc='',todesc='',context=False,
1949 numlines=5):
1950 """Returns HTML table of side by side comparison with change highlights
1951
1952 Arguments:
1953 fromlines -- list of "from" lines
1954 tolines -- list of "to" lines
1955 fromdesc -- "from" file column header string
1956 todesc -- "to" file column header string
1957 context -- set to True for contextual differences (defaults to False
1958 which shows full differences).
1959 numlines -- number of context lines. When context is set True,
1960 controls number of lines displayed before and after the change.
1961 When context is False, controls the number of lines to place
1962 the "next" link anchors before the next change (so click of
1963 "next" link jumps to just before the change).
1964 """
1965
1966 # make unique anchor prefixes so that multiple tables may exist
1967 # on the same page without conflict.
1968 self._make_prefix()
Tim Peters48bd7f32004-08-29 22:38:38 +00001969
Martin v. Löwise064b412004-08-29 16:34:40 +00001970 # change tabs to spaces before it gets more difficult after we insert
1971 # markkup
1972 fromlines,tolines = self._tab_newline_replace(fromlines,tolines)
Tim Peters48bd7f32004-08-29 22:38:38 +00001973
Martin v. Löwise064b412004-08-29 16:34:40 +00001974 # create diffs iterator which generates side by side from/to data
1975 if context:
1976 context_lines = numlines
1977 else:
1978 context_lines = None
1979 diffs = _mdiff(fromlines,tolines,context_lines,linejunk=self._linejunk,
1980 charjunk=self._charjunk)
1981
1982 # set up iterator to wrap lines that exceed desired width
1983 if self._wrapcolumn:
1984 diffs = self._line_wrapper(diffs)
Tim Peters48bd7f32004-08-29 22:38:38 +00001985
Martin v. Löwise064b412004-08-29 16:34:40 +00001986 # collect up from/to lines and flags into lists (also format the lines)
1987 fromlist,tolist,flaglist = self._collect_lines(diffs)
1988
1989 # process change flags, generating middle column of next anchors/links
1990 fromlist,tolist,flaglist,next_href,next_id = self._convert_flags(
1991 fromlist,tolist,flaglist,context,numlines)
1992
Guido van Rossumd8faa362007-04-27 19:54:29 +00001993 s = []
Martin v. Löwise064b412004-08-29 16:34:40 +00001994 fmt = ' <tr><td class="diff_next"%s>%s</td>%s' + \
1995 '<td class="diff_next">%s</td>%s</tr>\n'
1996 for i in range(len(flaglist)):
1997 if flaglist[i] is None:
1998 # mdiff yields None on separator lines skip the bogus ones
1999 # generated for the first line
2000 if i > 0:
Guido van Rossumd8faa362007-04-27 19:54:29 +00002001 s.append(' </tbody> \n <tbody>\n')
Martin v. Löwise064b412004-08-29 16:34:40 +00002002 else:
Guido van Rossumd8faa362007-04-27 19:54:29 +00002003 s.append( fmt % (next_id[i],next_href[i],fromlist[i],
Martin v. Löwise064b412004-08-29 16:34:40 +00002004 next_href[i],tolist[i]))
2005 if fromdesc or todesc:
2006 header_row = '<thead><tr>%s%s%s%s</tr></thead>' % (
2007 '<th class="diff_next"><br /></th>',
2008 '<th colspan="2" class="diff_header">%s</th>' % fromdesc,
2009 '<th class="diff_next"><br /></th>',
2010 '<th colspan="2" class="diff_header">%s</th>' % todesc)
2011 else:
2012 header_row = ''
2013
2014 table = self._table_template % dict(
Guido van Rossumd8faa362007-04-27 19:54:29 +00002015 data_rows=''.join(s),
Martin v. Löwise064b412004-08-29 16:34:40 +00002016 header_row=header_row,
2017 prefix=self._prefix[1])
2018
2019 return table.replace('\0+','<span class="diff_add">'). \
2020 replace('\0-','<span class="diff_sub">'). \
2021 replace('\0^','<span class="diff_chg">'). \
2022 replace('\1','</span>'). \
2023 replace('\t','&nbsp;')
Tim Peters48bd7f32004-08-29 22:38:38 +00002024
Martin v. Löwise064b412004-08-29 16:34:40 +00002025del re
2026
Tim Peters5e824c32001-08-12 22:25:01 +00002027def restore(delta, which):
2028 r"""
Tim Peters8a9c2842001-09-22 21:30:22 +00002029 Generate one of the two sequences that generated a delta.
Tim Peters5e824c32001-08-12 22:25:01 +00002030
2031 Given a `delta` produced by `Differ.compare()` or `ndiff()`, extract
2032 lines originating from file 1 or 2 (parameter `which`), stripping off line
2033 prefixes.
2034
2035 Examples:
2036
2037 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
2038 ... 'ore\ntree\nemu\n'.splitlines(1))
Tim Peters8a9c2842001-09-22 21:30:22 +00002039 >>> diff = list(diff)
Guido van Rossumbe19ed72007-02-09 05:37:30 +00002040 >>> print(''.join(restore(diff, 1)), end="")
Tim Peters5e824c32001-08-12 22:25:01 +00002041 one
2042 two
2043 three
Guido van Rossumbe19ed72007-02-09 05:37:30 +00002044 >>> print(''.join(restore(diff, 2)), end="")
Tim Peters5e824c32001-08-12 22:25:01 +00002045 ore
2046 tree
2047 emu
2048 """
2049 try:
2050 tag = {1: "- ", 2: "+ "}[int(which)]
2051 except KeyError:
Collin Winterce36ad82007-08-30 01:19:48 +00002052 raise ValueError('unknown delta choice (must be 1 or 2): %r'
Tim Peters5e824c32001-08-12 22:25:01 +00002053 % which)
2054 prefixes = (" ", tag)
Tim Peters5e824c32001-08-12 22:25:01 +00002055 for line in delta:
2056 if line[:2] in prefixes:
Tim Peters8a9c2842001-09-22 21:30:22 +00002057 yield line[2:]
Tim Peters5e824c32001-08-12 22:25:01 +00002058
Tim Peters9ae21482001-02-10 08:00:53 +00002059def _test():
2060 import doctest, difflib
2061 return doctest.testmod(difflib)
2062
2063if __name__ == "__main__":
2064 _test()