+++ /dev/null
-#! /usr/bin/env python\r
-\r
-"""\r
-Module difflib -- helpers for computing deltas between objects.\r
-\r
-Function get_close_matches(word, possibilities, n=3, cutoff=0.6):\r
- Use SequenceMatcher to return list of the best "good enough" matches.\r
-\r
-Function context_diff(a, b):\r
- For two lists of strings, return a delta in context diff format.\r
-\r
-Function ndiff(a, b):\r
- Return a delta: the difference between `a` and `b` (lists of strings).\r
-\r
-Function restore(delta, which):\r
- Return one of the two sequences that generated an ndiff delta.\r
-\r
-Function unified_diff(a, b):\r
- For two lists of strings, return a delta in unified diff format.\r
-\r
-Class SequenceMatcher:\r
- A flexible class for comparing pairs of sequences of any type.\r
-\r
-Class Differ:\r
- For producing human-readable deltas from sequences of lines of text.\r
-\r
-Class HtmlDiff:\r
- For producing HTML side by side comparison with change highlights.\r
-"""\r
-\r
-__all__ = ['get_close_matches', 'ndiff', 'restore', 'SequenceMatcher',\r
- 'Differ','IS_CHARACTER_JUNK', 'IS_LINE_JUNK', 'context_diff',\r
- 'unified_diff', 'HtmlDiff', 'Match']\r
-\r
-import heapq\r
-from collections import namedtuple as _namedtuple\r
-from functools import reduce\r
-\r
-Match = _namedtuple('Match', 'a b size')\r
-\r
-def _calculate_ratio(matches, length):\r
- if length:\r
- return 2.0 * matches / length\r
- return 1.0\r
-\r
-class SequenceMatcher:\r
-\r
- """\r
- SequenceMatcher is a flexible class for comparing pairs of sequences of\r
- any type, so long as the sequence elements are hashable. The basic\r
- algorithm predates, and is a little fancier than, an algorithm\r
- published in the late 1980's by Ratcliff and Obershelp under the\r
- hyperbolic name "gestalt pattern matching". The basic idea is to find\r
- the longest contiguous matching subsequence that contains no "junk"\r
- elements (R-O doesn't address junk). The same idea is then applied\r
- recursively to the pieces of the sequences to the left and to the right\r
- of the matching subsequence. This does not yield minimal edit\r
- sequences, but does tend to yield matches that "look right" to people.\r
-\r
- SequenceMatcher tries to compute a "human-friendly diff" between two\r
- sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the\r
- longest *contiguous* & junk-free matching subsequence. That's what\r
- catches peoples' eyes. The Windows(tm) windiff has another interesting\r
- notion, pairing up elements that appear uniquely in each sequence.\r
- That, and the method here, appear to yield more intuitive difference\r
- reports than does diff. This method appears to be the least vulnerable\r
- to synching up on blocks of "junk lines", though (like blank lines in\r
- ordinary text files, or maybe "<P>" lines in HTML files). That may be\r
- because this is the only method of the 3 that has a *concept* of\r
- "junk" <wink>.\r
-\r
- Example, comparing two strings, and considering blanks to be "junk":\r
-\r
- >>> s = SequenceMatcher(lambda x: x == " ",\r
- ... "private Thread currentThread;",\r
- ... "private volatile Thread currentThread;")\r
- >>>\r
-\r
- .ratio() returns a float in [0, 1], measuring the "similarity" of the\r
- sequences. As a rule of thumb, a .ratio() value over 0.6 means the\r
- sequences are close matches:\r
-\r
- >>> print round(s.ratio(), 3)\r
- 0.866\r
- >>>\r
-\r
- If you're only interested in where the sequences match,\r
- .get_matching_blocks() is handy:\r
-\r
- >>> for block in s.get_matching_blocks():\r
- ... print "a[%d] and b[%d] match for %d elements" % block\r
- a[0] and b[0] match for 8 elements\r
- a[8] and b[17] match for 21 elements\r
- a[29] and b[38] match for 0 elements\r
-\r
- Note that the last tuple returned by .get_matching_blocks() is always a\r
- dummy, (len(a), len(b), 0), and this is the only case in which the last\r
- tuple element (number of elements matched) is 0.\r
-\r
- If you want to know how to change the first sequence into the second,\r
- use .get_opcodes():\r
-\r
- >>> for opcode in s.get_opcodes():\r
- ... print "%6s a[%d:%d] b[%d:%d]" % opcode\r
- equal a[0:8] b[0:8]\r
- insert a[8:8] b[8:17]\r
- equal a[8:29] b[17:38]\r
-\r
- See the Differ class for a fancy human-friendly file differencer, which\r
- uses SequenceMatcher both to compare sequences of lines, and to compare\r
- sequences of characters within similar (near-matching) lines.\r
-\r
- See also function get_close_matches() in this module, which shows how\r
- simple code building on SequenceMatcher can be used to do useful work.\r
-\r
- Timing: Basic R-O is cubic time worst case and quadratic time expected\r
- case. SequenceMatcher is quadratic time for the worst case and has\r
- expected-case behavior dependent in a complicated way on how many\r
- elements the sequences have in common; best case time is linear.\r
-\r
- Methods:\r
-\r
- __init__(isjunk=None, a='', b='')\r
- Construct a SequenceMatcher.\r
-\r
- set_seqs(a, b)\r
- Set the two sequences to be compared.\r
-\r
- set_seq1(a)\r
- Set the first sequence to be compared.\r
-\r
- set_seq2(b)\r
- Set the second sequence to be compared.\r
-\r
- find_longest_match(alo, ahi, blo, bhi)\r
- Find longest matching block in a[alo:ahi] and b[blo:bhi].\r
-\r
- get_matching_blocks()\r
- Return list of triples describing matching subsequences.\r
-\r
- get_opcodes()\r
- Return list of 5-tuples describing how to turn a into b.\r
-\r
- ratio()\r
- Return a measure of the sequences' similarity (float in [0,1]).\r
-\r
- quick_ratio()\r
- Return an upper bound on .ratio() relatively quickly.\r
-\r
- real_quick_ratio()\r
- Return an upper bound on ratio() very quickly.\r
- """\r
-\r
- def __init__(self, isjunk=None, a='', b='', autojunk=True):\r
- """Construct a SequenceMatcher.\r
-\r
- Optional arg isjunk is None (the default), or a one-argument\r
- function that takes a sequence element and returns true iff the\r
- element is junk. None is equivalent to passing "lambda x: 0", i.e.\r
- no elements are considered to be junk. For example, pass\r
- lambda x: x in " \\t"\r
- if you're comparing lines as sequences of characters, and don't\r
- want to synch up on blanks or hard tabs.\r
-\r
- Optional arg a is the first of two sequences to be compared. By\r
- default, an empty string. The elements of a must be hashable. See\r
- also .set_seqs() and .set_seq1().\r
-\r
- Optional arg b is the second of two sequences to be compared. By\r
- default, an empty string. The elements of b must be hashable. See\r
- also .set_seqs() and .set_seq2().\r
-\r
- Optional arg autojunk should be set to False to disable the\r
- "automatic junk heuristic" that treats popular elements as junk\r
- (see module documentation for more information).\r
- """\r
-\r
- # Members:\r
- # a\r
- # first sequence\r
- # b\r
- # second sequence; differences are computed as "what do\r
- # we need to do to 'a' to change it into 'b'?"\r
- # b2j\r
- # for x in b, b2j[x] is a list of the indices (into b)\r
- # at which x appears; junk elements do not appear\r
- # fullbcount\r
- # for x in b, fullbcount[x] == the number of times x\r
- # appears in b; only materialized if really needed (used\r
- # only for computing quick_ratio())\r
- # matching_blocks\r
- # a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];\r
- # ascending & non-overlapping in i and in j; terminated by\r
- # a dummy (len(a), len(b), 0) sentinel\r
- # opcodes\r
- # a list of (tag, i1, i2, j1, j2) tuples, where tag is\r
- # one of\r
- # 'replace' a[i1:i2] should be replaced by b[j1:j2]\r
- # 'delete' a[i1:i2] should be deleted\r
- # 'insert' b[j1:j2] should be inserted\r
- # 'equal' a[i1:i2] == b[j1:j2]\r
- # isjunk\r
- # a user-supplied function taking a sequence element and\r
- # returning true iff the element is "junk" -- this has\r
- # subtle but helpful effects on the algorithm, which I'll\r
- # get around to writing up someday <0.9 wink>.\r
- # DON'T USE! Only __chain_b uses this. Use isbjunk.\r
- # isbjunk\r
- # for x in b, isbjunk(x) == isjunk(x) but much faster;\r
- # it's really the __contains__ method of a hidden dict.\r
- # DOES NOT WORK for x in a!\r
- # isbpopular\r
- # for x in b, isbpopular(x) is true iff b is reasonably long\r
- # (at least 200 elements) and x accounts for more than 1 + 1% of\r
- # its elements (when autojunk is enabled).\r
- # DOES NOT WORK for x in a!\r
-\r
- self.isjunk = isjunk\r
- self.a = self.b = None\r
- self.autojunk = autojunk\r
- self.set_seqs(a, b)\r
-\r
- def set_seqs(self, a, b):\r
- """Set the two sequences to be compared.\r
-\r
- >>> s = SequenceMatcher()\r
- >>> s.set_seqs("abcd", "bcde")\r
- >>> s.ratio()\r
- 0.75\r
- """\r
-\r
- self.set_seq1(a)\r
- self.set_seq2(b)\r
-\r
- def set_seq1(self, a):\r
- """Set the first sequence to be compared.\r
-\r
- The second sequence to be compared is not changed.\r
-\r
- >>> s = SequenceMatcher(None, "abcd", "bcde")\r
- >>> s.ratio()\r
- 0.75\r
- >>> s.set_seq1("bcde")\r
- >>> s.ratio()\r
- 1.0\r
- >>>\r
-\r
- SequenceMatcher computes and caches detailed information about the\r
- second sequence, so if you want to compare one sequence S against\r
- many sequences, use .set_seq2(S) once and call .set_seq1(x)\r
- repeatedly for each of the other sequences.\r
-\r
- See also set_seqs() and set_seq2().\r
- """\r
-\r
- if a is self.a:\r
- return\r
- self.a = a\r
- self.matching_blocks = self.opcodes = None\r
-\r
- def set_seq2(self, b):\r
- """Set the second sequence to be compared.\r
-\r
- The first sequence to be compared is not changed.\r
-\r
- >>> s = SequenceMatcher(None, "abcd", "bcde")\r
- >>> s.ratio()\r
- 0.75\r
- >>> s.set_seq2("abcd")\r
- >>> s.ratio()\r
- 1.0\r
- >>>\r
-\r
- SequenceMatcher computes and caches detailed information about the\r
- second sequence, so if you want to compare one sequence S against\r
- many sequences, use .set_seq2(S) once and call .set_seq1(x)\r
- repeatedly for each of the other sequences.\r
-\r
- See also set_seqs() and set_seq1().\r
- """\r
-\r
- if b is self.b:\r
- return\r
- self.b = b\r
- self.matching_blocks = self.opcodes = None\r
- self.fullbcount = None\r
- self.__chain_b()\r
-\r
- # For each element x in b, set b2j[x] to a list of the indices in\r
- # b where x appears; the indices are in increasing order; note that\r
- # the number of times x appears in b is len(b2j[x]) ...\r
- # when self.isjunk is defined, junk elements don't show up in this\r
- # map at all, which stops the central find_longest_match method\r
- # from starting any matching block at a junk element ...\r
- # also creates the fast isbjunk function ...\r
- # b2j also does not contain entries for "popular" elements, meaning\r
- # elements that account for more than 1 + 1% of the total elements, and\r
- # when the sequence is reasonably large (>= 200 elements); this can\r
- # be viewed as an adaptive notion of semi-junk, and yields an enormous\r
- # speedup when, e.g., comparing program files with hundreds of\r
- # instances of "return NULL;" ...\r
- # note that this is only called when b changes; so for cross-product\r
- # kinds of matches, it's best to call set_seq2 once, then set_seq1\r
- # repeatedly\r
-\r
- def __chain_b(self):\r
- # Because isjunk is a user-defined (not C) function, and we test\r
- # for junk a LOT, it's important to minimize the number of calls.\r
- # Before the tricks described here, __chain_b was by far the most\r
- # time-consuming routine in the whole module! If anyone sees\r
- # Jim Roskind, thank him again for profile.py -- I never would\r
- # have guessed that.\r
- # The first trick is to build b2j ignoring the possibility\r
- # of junk. I.e., we don't call isjunk at all yet. Throwing\r
- # out the junk later is much cheaper than building b2j "right"\r
- # from the start.\r
- b = self.b\r
- self.b2j = b2j = {}\r
-\r
- for i, elt in enumerate(b):\r
- indices = b2j.setdefault(elt, [])\r
- indices.append(i)\r
-\r
- # Purge junk elements\r
- junk = set()\r
- isjunk = self.isjunk\r
- if isjunk:\r
- for elt in list(b2j.keys()): # using list() since b2j is modified\r
- if isjunk(elt):\r
- junk.add(elt)\r
- del b2j[elt]\r
-\r
- # Purge popular elements that are not junk\r
- popular = set()\r
- n = len(b)\r
- if self.autojunk and n >= 200:\r
- ntest = n // 100 + 1\r
- for elt, idxs in list(b2j.items()):\r
- if len(idxs) > ntest:\r
- popular.add(elt)\r
- del b2j[elt]\r
-\r
- # Now for x in b, isjunk(x) == x in junk, but the latter is much faster.\r
- # Sicne the number of *unique* junk elements is probably small, the\r
- # memory burden of keeping this set alive is likely trivial compared to\r
- # the size of b2j.\r
- self.isbjunk = junk.__contains__\r
- self.isbpopular = popular.__contains__\r
-\r
- def find_longest_match(self, alo, ahi, blo, bhi):\r
- """Find longest matching block in a[alo:ahi] and b[blo:bhi].\r
-\r
- If isjunk is not defined:\r
-\r
- Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where\r
- alo <= i <= i+k <= ahi\r
- blo <= j <= j+k <= bhi\r
- and for all (i',j',k') meeting those conditions,\r
- k >= k'\r
- i <= i'\r
- and if i == i', j <= j'\r
-\r
- In other words, of all maximal matching blocks, return one that\r
- starts earliest in a, and of all those maximal matching blocks that\r
- start earliest in a, return the one that starts earliest in b.\r
-\r
- >>> s = SequenceMatcher(None, " abcd", "abcd abcd")\r
- >>> s.find_longest_match(0, 5, 0, 9)\r
- Match(a=0, b=4, size=5)\r
-\r
- If isjunk is defined, first the longest matching block is\r
- determined as above, but with the additional restriction that no\r
- junk element appears in the block. Then that block is extended as\r
- far as possible by matching (only) junk elements on both sides. So\r
- the resulting block never matches on junk except as identical junk\r
- happens to be adjacent to an "interesting" match.\r
-\r
- Here's the same example as before, but considering blanks to be\r
- junk. That prevents " abcd" from matching the " abcd" at the tail\r
- end of the second sequence directly. Instead only the "abcd" can\r
- match, and matches the leftmost "abcd" in the second sequence:\r
-\r
- >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")\r
- >>> s.find_longest_match(0, 5, 0, 9)\r
- Match(a=1, b=0, size=4)\r
-\r
- If no blocks match, return (alo, blo, 0).\r
-\r
- >>> s = SequenceMatcher(None, "ab", "c")\r
- >>> s.find_longest_match(0, 2, 0, 1)\r
- Match(a=0, b=0, size=0)\r
- """\r
-\r
- # CAUTION: stripping common prefix or suffix would be incorrect.\r
- # E.g.,\r
- # ab\r
- # acab\r
- # Longest matching block is "ab", but if common prefix is\r
- # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so\r
- # strip, so ends up claiming that ab is changed to acab by\r
- # inserting "ca" in the middle. That's minimal but unintuitive:\r
- # "it's obvious" that someone inserted "ac" at the front.\r
- # Windiff ends up at the same place as diff, but by pairing up\r
- # the unique 'b's and then matching the first two 'a's.\r
-\r
- a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk\r
- besti, bestj, bestsize = alo, blo, 0\r
- # find longest junk-free match\r
- # during an iteration of the loop, j2len[j] = length of longest\r
- # junk-free match ending with a[i-1] and b[j]\r
- j2len = {}\r
- nothing = []\r
- for i in xrange(alo, ahi):\r
- # look at all instances of a[i] in b; note that because\r
- # b2j has no junk keys, the loop is skipped if a[i] is junk\r
- j2lenget = j2len.get\r
- newj2len = {}\r
- for j in b2j.get(a[i], nothing):\r
- # a[i] matches b[j]\r
- if j < blo:\r
- continue\r
- if j >= bhi:\r
- break\r
- k = newj2len[j] = j2lenget(j-1, 0) + 1\r
- if k > bestsize:\r
- besti, bestj, bestsize = i-k+1, j-k+1, k\r
- j2len = newj2len\r
-\r
- # Extend the best by non-junk elements on each end. In particular,\r
- # "popular" non-junk elements aren't in b2j, which greatly speeds\r
- # the inner loop above, but also means "the best" match so far\r
- # doesn't contain any junk *or* popular non-junk elements.\r
- while besti > alo and bestj > blo and \\r
- not isbjunk(b[bestj-1]) and \\r
- a[besti-1] == b[bestj-1]:\r
- besti, bestj, bestsize = besti-1, bestj-1, bestsize+1\r
- while besti+bestsize < ahi and bestj+bestsize < bhi and \\r
- not isbjunk(b[bestj+bestsize]) and \\r
- a[besti+bestsize] == b[bestj+bestsize]:\r
- bestsize += 1\r
-\r
- # Now that we have a wholly interesting match (albeit possibly\r
- # empty!), we may as well suck up the matching junk on each\r
- # side of it too. Can't think of a good reason not to, and it\r
- # saves post-processing the (possibly considerable) expense of\r
- # figuring out what to do with it. In the case of an empty\r
- # interesting match, this is clearly the right thing to do,\r
- # because no other kind of match is possible in the regions.\r
- while besti > alo and bestj > blo and \\r
- isbjunk(b[bestj-1]) and \\r
- a[besti-1] == b[bestj-1]:\r
- besti, bestj, bestsize = besti-1, bestj-1, bestsize+1\r
- while besti+bestsize < ahi and bestj+bestsize < bhi and \\r
- isbjunk(b[bestj+bestsize]) and \\r
- a[besti+bestsize] == b[bestj+bestsize]:\r
- bestsize = bestsize + 1\r
-\r
- return Match(besti, bestj, bestsize)\r
-\r
- def get_matching_blocks(self):\r
- """Return list of triples describing matching subsequences.\r
-\r
- Each triple is of the form (i, j, n), and means that\r
- a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in\r
- i and in j. New in Python 2.5, it's also guaranteed that if\r
- (i, j, n) and (i', j', n') are adjacent triples in the list, and\r
- the second is not the last triple in the list, then i+n != i' or\r
- j+n != j'. IOW, adjacent triples never describe adjacent equal\r
- blocks.\r
-\r
- The last triple is a dummy, (len(a), len(b), 0), and is the only\r
- triple with n==0.\r
-\r
- >>> s = SequenceMatcher(None, "abxcd", "abcd")\r
- >>> s.get_matching_blocks()\r
- [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]\r
- """\r
-\r
- if self.matching_blocks is not None:\r
- return self.matching_blocks\r
- la, lb = len(self.a), len(self.b)\r
-\r
- # This is most naturally expressed as a recursive algorithm, but\r
- # at least one user bumped into extreme use cases that exceeded\r
- # the recursion limit on their box. So, now we maintain a list\r
- # ('queue`) of blocks we still need to look at, and append partial\r
- # results to `matching_blocks` in a loop; the matches are sorted\r
- # at the end.\r
- queue = [(0, la, 0, lb)]\r
- matching_blocks = []\r
- while queue:\r
- alo, ahi, blo, bhi = queue.pop()\r
- i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)\r
- # a[alo:i] vs b[blo:j] unknown\r
- # a[i:i+k] same as b[j:j+k]\r
- # a[i+k:ahi] vs b[j+k:bhi] unknown\r
- if k: # if k is 0, there was no matching block\r
- matching_blocks.append(x)\r
- if alo < i and blo < j:\r
- queue.append((alo, i, blo, j))\r
- if i+k < ahi and j+k < bhi:\r
- queue.append((i+k, ahi, j+k, bhi))\r
- matching_blocks.sort()\r
-\r
- # It's possible that we have adjacent equal blocks in the\r
- # matching_blocks list now. Starting with 2.5, this code was added\r
- # to collapse them.\r
- i1 = j1 = k1 = 0\r
- non_adjacent = []\r
- for i2, j2, k2 in matching_blocks:\r
- # Is this block adjacent to i1, j1, k1?\r
- if i1 + k1 == i2 and j1 + k1 == j2:\r
- # Yes, so collapse them -- this just increases the length of\r
- # the first block by the length of the second, and the first\r
- # block so lengthened remains the block to compare against.\r
- k1 += k2\r
- else:\r
- # Not adjacent. Remember the first block (k1==0 means it's\r
- # the dummy we started with), and make the second block the\r
- # new block to compare against.\r
- if k1:\r
- non_adjacent.append((i1, j1, k1))\r
- i1, j1, k1 = i2, j2, k2\r
- if k1:\r
- non_adjacent.append((i1, j1, k1))\r
-\r
- non_adjacent.append( (la, lb, 0) )\r
- self.matching_blocks = non_adjacent\r
- return map(Match._make, self.matching_blocks)\r
-\r
- def get_opcodes(self):\r
- """Return list of 5-tuples describing how to turn a into b.\r
-\r
- Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple\r
- has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the\r
- tuple preceding it, and likewise for j1 == the previous j2.\r
-\r
- The tags are strings, with these meanings:\r
-\r
- 'replace': a[i1:i2] should be replaced by b[j1:j2]\r
- 'delete': a[i1:i2] should be deleted.\r
- Note that j1==j2 in this case.\r
- 'insert': b[j1:j2] should be inserted at a[i1:i1].\r
- Note that i1==i2 in this case.\r
- 'equal': a[i1:i2] == b[j1:j2]\r
-\r
- >>> a = "qabxcd"\r
- >>> b = "abycdf"\r
- >>> s = SequenceMatcher(None, a, b)\r
- >>> for tag, i1, i2, j1, j2 in s.get_opcodes():\r
- ... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %\r
- ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))\r
- delete a[0:1] (q) b[0:0] ()\r
- equal a[1:3] (ab) b[0:2] (ab)\r
- replace a[3:4] (x) b[2:3] (y)\r
- equal a[4:6] (cd) b[3:5] (cd)\r
- insert a[6:6] () b[5:6] (f)\r
- """\r
-\r
- if self.opcodes is not None:\r
- return self.opcodes\r
- i = j = 0\r
- self.opcodes = answer = []\r
- for ai, bj, size in self.get_matching_blocks():\r
- # invariant: we've pumped out correct diffs to change\r
- # a[:i] into b[:j], and the next matching block is\r
- # a[ai:ai+size] == b[bj:bj+size]. So we need to pump\r
- # out a diff to change a[i:ai] into b[j:bj], pump out\r
- # the matching block, and move (i,j) beyond the match\r
- tag = ''\r
- if i < ai and j < bj:\r
- tag = 'replace'\r
- elif i < ai:\r
- tag = 'delete'\r
- elif j < bj:\r
- tag = 'insert'\r
- if tag:\r
- answer.append( (tag, i, ai, j, bj) )\r
- i, j = ai+size, bj+size\r
- # the list of matching blocks is terminated by a\r
- # sentinel with size 0\r
- if size:\r
- answer.append( ('equal', ai, i, bj, j) )\r
- return answer\r
-\r
- def get_grouped_opcodes(self, n=3):\r
- """ Isolate change clusters by eliminating ranges with no changes.\r
-\r
- Return a generator of groups with upto n lines of context.\r
- Each group is in the same format as returned by get_opcodes().\r
-\r
- >>> from pprint import pprint\r
- >>> a = map(str, range(1,40))\r
- >>> b = a[:]\r
- >>> b[8:8] = ['i'] # Make an insertion\r
- >>> b[20] += 'x' # Make a replacement\r
- >>> b[23:28] = [] # Make a deletion\r
- >>> b[30] += 'y' # Make another replacement\r
- >>> pprint(list(SequenceMatcher(None,a,b).get_grouped_opcodes()))\r
- [[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],\r
- [('equal', 16, 19, 17, 20),\r
- ('replace', 19, 20, 20, 21),\r
- ('equal', 20, 22, 21, 23),\r
- ('delete', 22, 27, 23, 23),\r
- ('equal', 27, 30, 23, 26)],\r
- [('equal', 31, 34, 27, 30),\r
- ('replace', 34, 35, 30, 31),\r
- ('equal', 35, 38, 31, 34)]]\r
- """\r
-\r
- codes = self.get_opcodes()\r
- if not codes:\r
- codes = [("equal", 0, 1, 0, 1)]\r
- # Fixup leading and trailing groups if they show no changes.\r
- if codes[0][0] == 'equal':\r
- tag, i1, i2, j1, j2 = codes[0]\r
- codes[0] = tag, max(i1, i2-n), i2, max(j1, j2-n), j2\r
- if codes[-1][0] == 'equal':\r
- tag, i1, i2, j1, j2 = codes[-1]\r
- codes[-1] = tag, i1, min(i2, i1+n), j1, min(j2, j1+n)\r
-\r
- nn = n + n\r
- group = []\r
- for tag, i1, i2, j1, j2 in codes:\r
- # End the current group and start a new one whenever\r
- # there is a large range with no changes.\r
- if tag == 'equal' and i2-i1 > nn:\r
- group.append((tag, i1, min(i2, i1+n), j1, min(j2, j1+n)))\r
- yield group\r
- group = []\r
- i1, j1 = max(i1, i2-n), max(j1, j2-n)\r
- group.append((tag, i1, i2, j1 ,j2))\r
- if group and not (len(group)==1 and group[0][0] == 'equal'):\r
- yield group\r
-\r
- def ratio(self):\r
- """Return a measure of the sequences' similarity (float in [0,1]).\r
-\r
- Where T is the total number of elements in both sequences, and\r
- M is the number of matches, this is 2.0*M / T.\r
- Note that this is 1 if the sequences are identical, and 0 if\r
- they have nothing in common.\r
-\r
- .ratio() is expensive to compute if you haven't already computed\r
- .get_matching_blocks() or .get_opcodes(), in which case you may\r
- want to try .quick_ratio() or .real_quick_ratio() first to get an\r
- upper bound.\r
-\r
- >>> s = SequenceMatcher(None, "abcd", "bcde")\r
- >>> s.ratio()\r
- 0.75\r
- >>> s.quick_ratio()\r
- 0.75\r
- >>> s.real_quick_ratio()\r
- 1.0\r
- """\r
-\r
- matches = reduce(lambda sum, triple: sum + triple[-1],\r
- self.get_matching_blocks(), 0)\r
- return _calculate_ratio(matches, len(self.a) + len(self.b))\r
-\r
- def quick_ratio(self):\r
- """Return an upper bound on ratio() relatively quickly.\r
-\r
- This isn't defined beyond that it is an upper bound on .ratio(), and\r
- is faster to compute.\r
- """\r
-\r
- # viewing a and b as multisets, set matches to the cardinality\r
- # of their intersection; this counts the number of matches\r
- # without regard to order, so is clearly an upper bound\r
- if self.fullbcount is None:\r
- self.fullbcount = fullbcount = {}\r
- for elt in self.b:\r
- fullbcount[elt] = fullbcount.get(elt, 0) + 1\r
- fullbcount = self.fullbcount\r
- # avail[x] is the number of times x appears in 'b' less the\r
- # number of times we've seen it in 'a' so far ... kinda\r
- avail = {}\r
- availhas, matches = avail.__contains__, 0\r
- for elt in self.a:\r
- if availhas(elt):\r
- numb = avail[elt]\r
- else:\r
- numb = fullbcount.get(elt, 0)\r
- avail[elt] = numb - 1\r
- if numb > 0:\r
- matches = matches + 1\r
- return _calculate_ratio(matches, len(self.a) + len(self.b))\r
-\r
- def real_quick_ratio(self):\r
- """Return an upper bound on ratio() very quickly.\r
-\r
- This isn't defined beyond that it is an upper bound on .ratio(), and\r
- is faster to compute than either .ratio() or .quick_ratio().\r
- """\r
-\r
- la, lb = len(self.a), len(self.b)\r
- # can't have more matches than the number of elements in the\r
- # shorter sequence\r
- return _calculate_ratio(min(la, lb), la + lb)\r
-\r
-def get_close_matches(word, possibilities, n=3, cutoff=0.6):\r
- """Use SequenceMatcher to return list of the best "good enough" matches.\r
-\r
- word is a sequence for which close matches are desired (typically a\r
- string).\r
-\r
- possibilities is a list of sequences against which to match word\r
- (typically a list of strings).\r
-\r
- Optional arg n (default 3) is the maximum number of close matches to\r
- return. n must be > 0.\r
-\r
- Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities\r
- that don't score at least that similar to word are ignored.\r
-\r
- The best (no more than n) matches among the possibilities are returned\r
- in a list, sorted by similarity score, most similar first.\r
-\r
- >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])\r
- ['apple', 'ape']\r
- >>> import keyword as _keyword\r
- >>> get_close_matches("wheel", _keyword.kwlist)\r
- ['while']\r
- >>> get_close_matches("apple", _keyword.kwlist)\r
- []\r
- >>> get_close_matches("accept", _keyword.kwlist)\r
- ['except']\r
- """\r
-\r
- if not n > 0:\r
- raise ValueError("n must be > 0: %r" % (n,))\r
- if not 0.0 <= cutoff <= 1.0:\r
- raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff,))\r
- result = []\r
- s = SequenceMatcher()\r
- s.set_seq2(word)\r
- for x in possibilities:\r
- s.set_seq1(x)\r
- if s.real_quick_ratio() >= cutoff and \\r
- s.quick_ratio() >= cutoff and \\r
- s.ratio() >= cutoff:\r
- result.append((s.ratio(), x))\r
-\r
- # Move the best scorers to head of list\r
- result = heapq.nlargest(n, result)\r
- # Strip scores for the best n matches\r
- return [x for score, x in result]\r
-\r
-def _count_leading(line, ch):\r
- """\r
- Return number of `ch` characters at the start of `line`.\r
-\r
- Example:\r
-\r
- >>> _count_leading(' abc', ' ')\r
- 3\r
- """\r
-\r
- i, n = 0, len(line)\r
- while i < n and line[i] == ch:\r
- i += 1\r
- return i\r
-\r
-class Differ:\r
- r"""\r
- Differ is a class for comparing sequences of lines of text, and\r
- producing human-readable differences or deltas. Differ uses\r
- SequenceMatcher both to compare sequences of lines, and to compare\r
- sequences of characters within similar (near-matching) lines.\r
-\r
- Each line of a Differ delta begins with a two-letter code:\r
-\r
- '- ' line unique to sequence 1\r
- '+ ' line unique to sequence 2\r
- ' ' line common to both sequences\r
- '? ' line not present in either input sequence\r
-\r
- Lines beginning with '? ' attempt to guide the eye to intraline\r
- differences, and were not present in either input sequence. These lines\r
- can be confusing if the sequences contain tab characters.\r
-\r
- Note that Differ makes no claim to produce a *minimal* diff. To the\r
- contrary, minimal diffs are often counter-intuitive, because they synch\r
- up anywhere possible, sometimes accidental matches 100 pages apart.\r
- Restricting synch points to contiguous matches preserves some notion of\r
- locality, at the occasional cost of producing a longer diff.\r
-\r
- Example: Comparing two texts.\r
-\r
- First we set up the texts, sequences of individual single-line strings\r
- ending with newlines (such sequences can also be obtained from the\r
- `readlines()` method of file-like objects):\r
-\r
- >>> text1 = ''' 1. Beautiful is better than ugly.\r
- ... 2. Explicit is better than implicit.\r
- ... 3. Simple is better than complex.\r
- ... 4. Complex is better than complicated.\r
- ... '''.splitlines(1)\r
- >>> len(text1)\r
- 4\r
- >>> text1[0][-1]\r
- '\n'\r
- >>> text2 = ''' 1. Beautiful is better than ugly.\r
- ... 3. Simple is better than complex.\r
- ... 4. Complicated is better than complex.\r
- ... 5. Flat is better than nested.\r
- ... '''.splitlines(1)\r
-\r
- Next we instantiate a Differ object:\r
-\r
- >>> d = Differ()\r
-\r
- Note that when instantiating a Differ object we may pass functions to\r
- filter out line and character 'junk'. See Differ.__init__ for details.\r
-\r
- Finally, we compare the two:\r
-\r
- >>> result = list(d.compare(text1, text2))\r
-\r
- 'result' is a list of strings, so let's pretty-print it:\r
-\r
- >>> from pprint import pprint as _pprint\r
- >>> _pprint(result)\r
- [' 1. Beautiful is better than ugly.\n',\r
- '- 2. Explicit is better than implicit.\n',\r
- '- 3. Simple is better than complex.\n',\r
- '+ 3. Simple is better than complex.\n',\r
- '? ++\n',\r
- '- 4. Complex is better than complicated.\n',\r
- '? ^ ---- ^\n',\r
- '+ 4. Complicated is better than complex.\n',\r
- '? ++++ ^ ^\n',\r
- '+ 5. Flat is better than nested.\n']\r
-\r
- As a single multi-line string it looks like this:\r
-\r
- >>> print ''.join(result),\r
- 1. Beautiful is better than ugly.\r
- - 2. Explicit is better than implicit.\r
- - 3. Simple is better than complex.\r
- + 3. Simple is better than complex.\r
- ? ++\r
- - 4. Complex is better than complicated.\r
- ? ^ ---- ^\r
- + 4. Complicated is better than complex.\r
- ? ++++ ^ ^\r
- + 5. Flat is better than nested.\r
-\r
- Methods:\r
-\r
- __init__(linejunk=None, charjunk=None)\r
- Construct a text differencer, with optional filters.\r
-\r
- compare(a, b)\r
- Compare two sequences of lines; generate the resulting delta.\r
- """\r
-\r
- def __init__(self, linejunk=None, charjunk=None):\r
- """\r
- Construct a text differencer, with optional filters.\r
-\r
- The two optional keyword parameters are for filter functions:\r
-\r
- - `linejunk`: A function that should accept a single string argument,\r
- and return true iff the string is junk. The module-level function\r
- `IS_LINE_JUNK` may be used to filter out lines without visible\r
- characters, except for at most one splat ('#'). It is recommended\r
- to leave linejunk None; as of Python 2.3, the underlying\r
- SequenceMatcher class has grown an adaptive notion of "noise" lines\r
- that's better than any static definition the author has ever been\r
- able to craft.\r
-\r
- - `charjunk`: A function that should accept a string of length 1. The\r
- module-level function `IS_CHARACTER_JUNK` may be used to filter out\r
- whitespace characters (a blank or tab; **note**: bad idea to include\r
- newline in this!). Use of IS_CHARACTER_JUNK is recommended.\r
- """\r
-\r
- self.linejunk = linejunk\r
- self.charjunk = charjunk\r
-\r
- def compare(self, a, b):\r
- r"""\r
- Compare two sequences of lines; generate the resulting delta.\r
-\r
- Each sequence must contain individual single-line strings ending with\r
- newlines. Such sequences can be obtained from the `readlines()` method\r
- of file-like objects. The delta generated also consists of newline-\r
- terminated strings, ready to be printed as-is via the writeline()\r
- method of a file-like object.\r
-\r
- Example:\r
-\r
- >>> print ''.join(Differ().compare('one\ntwo\nthree\n'.splitlines(1),\r
- ... 'ore\ntree\nemu\n'.splitlines(1))),\r
- - one\r
- ? ^\r
- + ore\r
- ? ^\r
- - two\r
- - three\r
- ? -\r
- + tree\r
- + emu\r
- """\r
-\r
- cruncher = SequenceMatcher(self.linejunk, a, b)\r
- for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():\r
- if tag == 'replace':\r
- g = self._fancy_replace(a, alo, ahi, b, blo, bhi)\r
- elif tag == 'delete':\r
- g = self._dump('-', a, alo, ahi)\r
- elif tag == 'insert':\r
- g = self._dump('+', b, blo, bhi)\r
- elif tag == 'equal':\r
- g = self._dump(' ', a, alo, ahi)\r
- else:\r
- raise ValueError, 'unknown tag %r' % (tag,)\r
-\r
- for line in g:\r
- yield line\r
-\r
- def _dump(self, tag, x, lo, hi):\r
- """Generate comparison results for a same-tagged range."""\r
- for i in xrange(lo, hi):\r
- yield '%s %s' % (tag, x[i])\r
-\r
- def _plain_replace(self, a, alo, ahi, b, blo, bhi):\r
- assert alo < ahi and blo < bhi\r
- # dump the shorter block first -- reduces the burden on short-term\r
- # memory if the blocks are of very different sizes\r
- if bhi - blo < ahi - alo:\r
- first = self._dump('+', b, blo, bhi)\r
- second = self._dump('-', a, alo, ahi)\r
- else:\r
- first = self._dump('-', a, alo, ahi)\r
- second = self._dump('+', b, blo, bhi)\r
-\r
- for g in first, second:\r
- for line in g:\r
- yield line\r
-\r
- def _fancy_replace(self, a, alo, ahi, b, blo, bhi):\r
- r"""\r
- When replacing one block of lines with another, search the blocks\r
- for *similar* lines; the best-matching pair (if any) is used as a\r
- synch point, and intraline difference marking is done on the\r
- similar pair. Lots of work, but often worth it.\r
-\r
- Example:\r
-\r
- >>> d = Differ()\r
- >>> results = d._fancy_replace(['abcDefghiJkl\n'], 0, 1,\r
- ... ['abcdefGhijkl\n'], 0, 1)\r
- >>> print ''.join(results),\r
- - abcDefghiJkl\r
- ? ^ ^ ^\r
- + abcdefGhijkl\r
- ? ^ ^ ^\r
- """\r
-\r
- # don't synch up unless the lines have a similarity score of at\r
- # least cutoff; best_ratio tracks the best score seen so far\r
- best_ratio, cutoff = 0.74, 0.75\r
- cruncher = SequenceMatcher(self.charjunk)\r
- eqi, eqj = None, None # 1st indices of equal lines (if any)\r
-\r
- # search for the pair that matches best without being identical\r
- # (identical lines must be junk lines, & we don't want to synch up\r
- # on junk -- unless we have to)\r
- for j in xrange(blo, bhi):\r
- bj = b[j]\r
- cruncher.set_seq2(bj)\r
- for i in xrange(alo, ahi):\r
- ai = a[i]\r
- if ai == bj:\r
- if eqi is None:\r
- eqi, eqj = i, j\r
- continue\r
- cruncher.set_seq1(ai)\r
- # computing similarity is expensive, so use the quick\r
- # upper bounds first -- have seen this speed up messy\r
- # compares by a factor of 3.\r
- # note that ratio() is only expensive to compute the first\r
- # time it's called on a sequence pair; the expensive part\r
- # of the computation is cached by cruncher\r
- if cruncher.real_quick_ratio() > best_ratio and \\r
- cruncher.quick_ratio() > best_ratio and \\r
- cruncher.ratio() > best_ratio:\r
- best_ratio, best_i, best_j = cruncher.ratio(), i, j\r
- if best_ratio < cutoff:\r
- # no non-identical "pretty close" pair\r
- if eqi is None:\r
- # no identical pair either -- treat it as a straight replace\r
- for line in self._plain_replace(a, alo, ahi, b, blo, bhi):\r
- yield line\r
- return\r
- # no close pair, but an identical pair -- synch up on that\r
- best_i, best_j, best_ratio = eqi, eqj, 1.0\r
- else:\r
- # there's a close pair, so forget the identical pair (if any)\r
- eqi = None\r
-\r
- # a[best_i] very similar to b[best_j]; eqi is None iff they're not\r
- # identical\r
-\r
- # pump out diffs from before the synch point\r
- for line in self._fancy_helper(a, alo, best_i, b, blo, best_j):\r
- yield line\r
-\r
- # do intraline marking on the synch pair\r
- aelt, belt = a[best_i], b[best_j]\r
- if eqi is None:\r
- # pump out a '-', '?', '+', '?' quad for the synched lines\r
- atags = btags = ""\r
- cruncher.set_seqs(aelt, belt)\r
- for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():\r
- la, lb = ai2 - ai1, bj2 - bj1\r
- if tag == 'replace':\r
- atags += '^' * la\r
- btags += '^' * lb\r
- elif tag == 'delete':\r
- atags += '-' * la\r
- elif tag == 'insert':\r
- btags += '+' * lb\r
- elif tag == 'equal':\r
- atags += ' ' * la\r
- btags += ' ' * lb\r
- else:\r
- raise ValueError, 'unknown tag %r' % (tag,)\r
- for line in self._qformat(aelt, belt, atags, btags):\r
- yield line\r
- else:\r
- # the synch pair is identical\r
- yield ' ' + aelt\r
-\r
- # pump out diffs from after the synch point\r
- for line in self._fancy_helper(a, best_i+1, ahi, b, best_j+1, bhi):\r
- yield line\r
-\r
- def _fancy_helper(self, a, alo, ahi, b, blo, bhi):\r
- g = []\r
- if alo < ahi:\r
- if blo < bhi:\r
- g = self._fancy_replace(a, alo, ahi, b, blo, bhi)\r
- else:\r
- g = self._dump('-', a, alo, ahi)\r
- elif blo < bhi:\r
- g = self._dump('+', b, blo, bhi)\r
-\r
- for line in g:\r
- yield line\r
-\r
- def _qformat(self, aline, bline, atags, btags):\r
- r"""\r
- Format "?" output and deal with leading tabs.\r
-\r
- Example:\r
-\r
- >>> d = Differ()\r
- >>> results = d._qformat('\tabcDefghiJkl\n', '\tabcdefGhijkl\n',\r
- ... ' ^ ^ ^ ', ' ^ ^ ^ ')\r
- >>> for line in results: print repr(line)\r
- ...\r
- '- \tabcDefghiJkl\n'\r
- '? \t ^ ^ ^\n'\r
- '+ \tabcdefGhijkl\n'\r
- '? \t ^ ^ ^\n'\r
- """\r
-\r
- # Can hurt, but will probably help most of the time.\r
- common = min(_count_leading(aline, "\t"),\r
- _count_leading(bline, "\t"))\r
- common = min(common, _count_leading(atags[:common], " "))\r
- common = min(common, _count_leading(btags[:common], " "))\r
- atags = atags[common:].rstrip()\r
- btags = btags[common:].rstrip()\r
-\r
- yield "- " + aline\r
- if atags:\r
- yield "? %s%s\n" % ("\t" * common, atags)\r
-\r
- yield "+ " + bline\r
- if btags:\r
- yield "? %s%s\n" % ("\t" * common, btags)\r
-\r
-# With respect to junk, an earlier version of ndiff simply refused to\r
-# *start* a match with a junk element. The result was cases like this:\r
-# before: private Thread currentThread;\r
-# after: private volatile Thread currentThread;\r
-# If you consider whitespace to be junk, the longest contiguous match\r
-# not starting with junk is "e Thread currentThread". So ndiff reported\r
-# that "e volatil" was inserted between the 't' and the 'e' in "private".\r
-# While an accurate view, to people that's absurd. The current version\r
-# looks for matching blocks that are entirely junk-free, then extends the\r
-# longest one of those as far as possible but only with matching junk.\r
-# So now "currentThread" is matched, then extended to suck up the\r
-# preceding blank; then "private" is matched, and extended to suck up the\r
-# following blank; then "Thread" is matched; and finally ndiff reports\r
-# that "volatile " was inserted before "Thread". The only quibble\r
-# remaining is that perhaps it was really the case that " volatile"\r
-# was inserted after "private". I can live with that <wink>.\r
-\r
-import re\r
-\r
-def IS_LINE_JUNK(line, pat=re.compile(r"\s*#?\s*$").match):\r
- r"""\r
- Return 1 for ignorable line: iff `line` is blank or contains a single '#'.\r
-\r
- Examples:\r
-\r
- >>> IS_LINE_JUNK('\n')\r
- True\r
- >>> IS_LINE_JUNK(' # \n')\r
- True\r
- >>> IS_LINE_JUNK('hello\n')\r
- False\r
- """\r
-\r
- return pat(line) is not None\r
-\r
-def IS_CHARACTER_JUNK(ch, ws=" \t"):\r
- r"""\r
- Return 1 for ignorable character: iff `ch` is a space or tab.\r
-\r
- Examples:\r
-\r
- >>> IS_CHARACTER_JUNK(' ')\r
- True\r
- >>> IS_CHARACTER_JUNK('\t')\r
- True\r
- >>> IS_CHARACTER_JUNK('\n')\r
- False\r
- >>> IS_CHARACTER_JUNK('x')\r
- False\r
- """\r
-\r
- return ch in ws\r
-\r
-\r
-########################################################################\r
-### Unified Diff\r
-########################################################################\r
-\r
-def _format_range_unified(start, stop):\r
- 'Convert range to the "ed" format'\r
- # Per the diff spec at http://www.unix.org/single_unix_specification/\r
- beginning = start + 1 # lines start numbering with one\r
- length = stop - start\r
- if length == 1:\r
- return '{}'.format(beginning)\r
- if not length:\r
- beginning -= 1 # empty ranges begin at line just before the range\r
- return '{},{}'.format(beginning, length)\r
-\r
-def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',\r
- tofiledate='', n=3, lineterm='\n'):\r
- r"""\r
- Compare two sequences of lines; generate the delta as a unified diff.\r
-\r
- Unified diffs are a compact way of showing line changes and a few\r
- lines of context. The number of context lines is set by 'n' which\r
- defaults to three.\r
-\r
- By default, the diff control lines (those with ---, +++, or @@) are\r
- created with a trailing newline. This is helpful so that inputs\r
- created from file.readlines() result in diffs that are suitable for\r
- file.writelines() since both the inputs and outputs have trailing\r
- newlines.\r
-\r
- For inputs that do not have trailing newlines, set the lineterm\r
- argument to "" so that the output will be uniformly newline free.\r
-\r
- The unidiff format normally has a header for filenames and modification\r
- times. Any or all of these may be specified using strings for\r
- 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.\r
- The modification times are normally expressed in the ISO 8601 format.\r
-\r
- Example:\r
-\r
- >>> for line in unified_diff('one two three four'.split(),\r
- ... 'zero one tree four'.split(), 'Original', 'Current',\r
- ... '2005-01-26 23:30:50', '2010-04-02 10:20:52',\r
- ... lineterm=''):\r
- ... print line # doctest: +NORMALIZE_WHITESPACE\r
- --- Original 2005-01-26 23:30:50\r
- +++ Current 2010-04-02 10:20:52\r
- @@ -1,4 +1,4 @@\r
- +zero\r
- one\r
- -two\r
- -three\r
- +tree\r
- four\r
- """\r
-\r
- started = False\r
- for group in SequenceMatcher(None,a,b).get_grouped_opcodes(n):\r
- if not started:\r
- started = True\r
- fromdate = '\t{}'.format(fromfiledate) if fromfiledate else ''\r
- todate = '\t{}'.format(tofiledate) if tofiledate else ''\r
- yield '--- {}{}{}'.format(fromfile, fromdate, lineterm)\r
- yield '+++ {}{}{}'.format(tofile, todate, lineterm)\r
-\r
- first, last = group[0], group[-1]\r
- file1_range = _format_range_unified(first[1], last[2])\r
- file2_range = _format_range_unified(first[3], last[4])\r
- yield '@@ -{} +{} @@{}'.format(file1_range, file2_range, lineterm)\r
-\r
- for tag, i1, i2, j1, j2 in group:\r
- if tag == 'equal':\r
- for line in a[i1:i2]:\r
- yield ' ' + line\r
- continue\r
- if tag in ('replace', 'delete'):\r
- for line in a[i1:i2]:\r
- yield '-' + line\r
- if tag in ('replace', 'insert'):\r
- for line in b[j1:j2]:\r
- yield '+' + line\r
-\r
-\r
-########################################################################\r
-### Context Diff\r
-########################################################################\r
-\r
-def _format_range_context(start, stop):\r
- 'Convert range to the "ed" format'\r
- # Per the diff spec at http://www.unix.org/single_unix_specification/\r
- beginning = start + 1 # lines start numbering with one\r
- length = stop - start\r
- if not length:\r
- beginning -= 1 # empty ranges begin at line just before the range\r
- if length <= 1:\r
- return '{}'.format(beginning)\r
- return '{},{}'.format(beginning, beginning + length - 1)\r
-\r
-# See http://www.unix.org/single_unix_specification/\r
-def context_diff(a, b, fromfile='', tofile='',\r
- fromfiledate='', tofiledate='', n=3, lineterm='\n'):\r
- r"""\r
- Compare two sequences of lines; generate the delta as a context diff.\r
-\r
- Context diffs are a compact way of showing line changes and a few\r
- lines of context. The number of context lines is set by 'n' which\r
- defaults to three.\r
-\r
- By default, the diff control lines (those with *** or ---) are\r
- created with a trailing newline. This is helpful so that inputs\r
- created from file.readlines() result in diffs that are suitable for\r
- file.writelines() since both the inputs and outputs have trailing\r
- newlines.\r
-\r
- For inputs that do not have trailing newlines, set the lineterm\r
- argument to "" so that the output will be uniformly newline free.\r
-\r
- The context diff format normally has a header for filenames and\r
- modification times. Any or all of these may be specified using\r
- strings for 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.\r
- The modification times are normally expressed in the ISO 8601 format.\r
- If not specified, the strings default to blanks.\r
-\r
- Example:\r
-\r
- >>> print ''.join(context_diff('one\ntwo\nthree\nfour\n'.splitlines(1),\r
- ... 'zero\none\ntree\nfour\n'.splitlines(1), 'Original', 'Current')),\r
- *** Original\r
- --- Current\r
- ***************\r
- *** 1,4 ****\r
- one\r
- ! two\r
- ! three\r
- four\r
- --- 1,4 ----\r
- + zero\r
- one\r
- ! tree\r
- four\r
- """\r
-\r
- prefix = dict(insert='+ ', delete='- ', replace='! ', equal=' ')\r
- started = False\r
- for group in SequenceMatcher(None,a,b).get_grouped_opcodes(n):\r
- if not started:\r
- started = True\r
- fromdate = '\t{}'.format(fromfiledate) if fromfiledate else ''\r
- todate = '\t{}'.format(tofiledate) if tofiledate else ''\r
- yield '*** {}{}{}'.format(fromfile, fromdate, lineterm)\r
- yield '--- {}{}{}'.format(tofile, todate, lineterm)\r
-\r
- first, last = group[0], group[-1]\r
- yield '***************' + lineterm\r
-\r
- file1_range = _format_range_context(first[1], last[2])\r
- yield '*** {} ****{}'.format(file1_range, lineterm)\r
-\r
- if any(tag in ('replace', 'delete') for tag, _, _, _, _ in group):\r
- for tag, i1, i2, _, _ in group:\r
- if tag != 'insert':\r
- for line in a[i1:i2]:\r
- yield prefix[tag] + line\r
-\r
- file2_range = _format_range_context(first[3], last[4])\r
- yield '--- {} ----{}'.format(file2_range, lineterm)\r
-\r
- if any(tag in ('replace', 'insert') for tag, _, _, _, _ in group):\r
- for tag, _, _, j1, j2 in group:\r
- if tag != 'delete':\r
- for line in b[j1:j2]:\r
- yield prefix[tag] + line\r
-\r
-def ndiff(a, b, linejunk=None, charjunk=IS_CHARACTER_JUNK):\r
- r"""\r
- Compare `a` and `b` (lists of strings); return a `Differ`-style delta.\r
-\r
- Optional keyword parameters `linejunk` and `charjunk` are for filter\r
- functions (or None):\r
-\r
- - linejunk: A function that should accept a single string argument, and\r
- return true iff the string is junk. The default is None, and is\r
- recommended; as of Python 2.3, an adaptive notion of "noise" lines is\r
- used that does a good job on its own.\r
-\r
- - charjunk: A function that should accept a string of length 1. The\r
- default is module-level function IS_CHARACTER_JUNK, which filters out\r
- whitespace characters (a blank or tab; note: bad idea to include newline\r
- in this!).\r
-\r
- Tools/scripts/ndiff.py is a command-line front-end to this function.\r
-\r
- Example:\r
-\r
- >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),\r
- ... 'ore\ntree\nemu\n'.splitlines(1))\r
- >>> print ''.join(diff),\r
- - one\r
- ? ^\r
- + ore\r
- ? ^\r
- - two\r
- - three\r
- ? -\r
- + tree\r
- + emu\r
- """\r
- return Differ(linejunk, charjunk).compare(a, b)\r
-\r
-def _mdiff(fromlines, tolines, context=None, linejunk=None,\r
- charjunk=IS_CHARACTER_JUNK):\r
- r"""Returns generator yielding marked up from/to side by side differences.\r
-\r
- Arguments:\r
- fromlines -- list of text lines to compared to tolines\r
- tolines -- list of text lines to be compared to fromlines\r
- context -- number of context lines to display on each side of difference,\r
- if None, all from/to text lines will be generated.\r
- linejunk -- passed on to ndiff (see ndiff documentation)\r
- charjunk -- passed on to ndiff (see ndiff documentation)\r
-\r
- This function returns an interator which returns a tuple:\r
- (from line tuple, to line tuple, boolean flag)\r
-\r
- from/to line tuple -- (line num, line text)\r
- line num -- integer or None (to indicate a context separation)\r
- line text -- original line text with following markers inserted:\r
- '\0+' -- marks start of added text\r
- '\0-' -- marks start of deleted text\r
- '\0^' -- marks start of changed text\r
- '\1' -- marks end of added/deleted/changed text\r
-\r
- boolean flag -- None indicates context separation, True indicates\r
- either "from" or "to" line contains a change, otherwise False.\r
-\r
- This function/iterator was originally developed to generate side by side\r
- file difference for making HTML pages (see HtmlDiff class for example\r
- usage).\r
-\r
- Note, this function utilizes the ndiff function to generate the side by\r
- side difference markup. Optional ndiff arguments may be passed to this\r
- function and they in turn will be passed to ndiff.\r
- """\r
- import re\r
-\r
- # regular expression for finding intraline change indices\r
- change_re = re.compile('(\++|\-+|\^+)')\r
-\r
- # create the difference iterator to generate the differences\r
- diff_lines_iterator = ndiff(fromlines,tolines,linejunk,charjunk)\r
-\r
- def _make_line(lines, format_key, side, num_lines=[0,0]):\r
- """Returns line of text with user's change markup and line formatting.\r
-\r
- lines -- list of lines from the ndiff generator to produce a line of\r
- text from. When producing the line of text to return, the\r
- lines used are removed from this list.\r
- format_key -- '+' return first line in list with "add" markup around\r
- the entire line.\r
- '-' return first line in list with "delete" markup around\r
- the entire line.\r
- '?' return first line in list with add/delete/change\r
- intraline markup (indices obtained from second line)\r
- None return first line in list with no markup\r
- side -- indice into the num_lines list (0=from,1=to)\r
- num_lines -- from/to current line number. This is NOT intended to be a\r
- passed parameter. It is present as a keyword argument to\r
- maintain memory of the current line numbers between calls\r
- of this function.\r
-\r
- Note, this function is purposefully not defined at the module scope so\r
- that data it needs from its parent function (within whose context it\r
- is defined) does not need to be of module scope.\r
- """\r
- num_lines[side] += 1\r
- # Handle case where no user markup is to be added, just return line of\r
- # text with user's line format to allow for usage of the line number.\r
- if format_key is None:\r
- return (num_lines[side],lines.pop(0)[2:])\r
- # Handle case of intraline changes\r
- if format_key == '?':\r
- text, markers = lines.pop(0), lines.pop(0)\r
- # find intraline changes (store change type and indices in tuples)\r
- sub_info = []\r
- def record_sub_info(match_object,sub_info=sub_info):\r
- sub_info.append([match_object.group(1)[0],match_object.span()])\r
- return match_object.group(1)\r
- change_re.sub(record_sub_info,markers)\r
- # process each tuple inserting our special marks that won't be\r
- # noticed by an xml/html escaper.\r
- for key,(begin,end) in sub_info[::-1]:\r
- text = text[0:begin]+'\0'+key+text[begin:end]+'\1'+text[end:]\r
- text = text[2:]\r
- # Handle case of add/delete entire line\r
- else:\r
- text = lines.pop(0)[2:]\r
- # if line of text is just a newline, insert a space so there is\r
- # something for the user to highlight and see.\r
- if not text:\r
- text = ' '\r
- # insert marks that won't be noticed by an xml/html escaper.\r
- text = '\0' + format_key + text + '\1'\r
- # Return line of text, first allow user's line formatter to do its\r
- # thing (such as adding the line number) then replace the special\r
- # marks with what the user's change markup.\r
- return (num_lines[side],text)\r
-\r
- def _line_iterator():\r
- """Yields from/to lines of text with a change indication.\r
-\r
- This function is an iterator. It itself pulls lines from a\r
- differencing iterator, processes them and yields them. When it can\r
- it yields both a "from" and a "to" line, otherwise it will yield one\r
- or the other. In addition to yielding the lines of from/to text, a\r
- boolean flag is yielded to indicate if the text line(s) have\r
- differences in them.\r
-\r
- Note, this function is purposefully not defined at the module scope so\r
- that data it needs from its parent function (within whose context it\r
- is defined) does not need to be of module scope.\r
- """\r
- lines = []\r
- num_blanks_pending, num_blanks_to_yield = 0, 0\r
- while True:\r
- # Load up next 4 lines so we can look ahead, create strings which\r
- # are a concatenation of the first character of each of the 4 lines\r
- # so we can do some very readable comparisons.\r
- while len(lines) < 4:\r
- try:\r
- lines.append(diff_lines_iterator.next())\r
- except StopIteration:\r
- lines.append('X')\r
- s = ''.join([line[0] for line in lines])\r
- if s.startswith('X'):\r
- # When no more lines, pump out any remaining blank lines so the\r
- # corresponding add/delete lines get a matching blank line so\r
- # all line pairs get yielded at the next level.\r
- num_blanks_to_yield = num_blanks_pending\r
- elif s.startswith('-?+?'):\r
- # simple intraline change\r
- yield _make_line(lines,'?',0), _make_line(lines,'?',1), True\r
- continue\r
- elif s.startswith('--++'):\r
- # in delete block, add block coming: we do NOT want to get\r
- # caught up on blank lines yet, just process the delete line\r
- num_blanks_pending -= 1\r
- yield _make_line(lines,'-',0), None, True\r
- continue\r
- elif s.startswith(('--?+', '--+', '- ')):\r
- # in delete block and see a intraline change or unchanged line\r
- # coming: yield the delete line and then blanks\r
- from_line,to_line = _make_line(lines,'-',0), None\r
- num_blanks_to_yield,num_blanks_pending = num_blanks_pending-1,0\r
- elif s.startswith('-+?'):\r
- # intraline change\r
- yield _make_line(lines,None,0), _make_line(lines,'?',1), True\r
- continue\r
- elif s.startswith('-?+'):\r
- # intraline change\r
- yield _make_line(lines,'?',0), _make_line(lines,None,1), True\r
- continue\r
- elif s.startswith('-'):\r
- # delete FROM line\r
- num_blanks_pending -= 1\r
- yield _make_line(lines,'-',0), None, True\r
- continue\r
- elif s.startswith('+--'):\r
- # in add block, delete block coming: we do NOT want to get\r
- # caught up on blank lines yet, just process the add line\r
- num_blanks_pending += 1\r
- yield None, _make_line(lines,'+',1), True\r
- continue\r
- elif s.startswith(('+ ', '+-')):\r
- # will be leaving an add block: yield blanks then add line\r
- from_line, to_line = None, _make_line(lines,'+',1)\r
- num_blanks_to_yield,num_blanks_pending = num_blanks_pending+1,0\r
- elif s.startswith('+'):\r
- # inside an add block, yield the add line\r
- num_blanks_pending += 1\r
- yield None, _make_line(lines,'+',1), True\r
- continue\r
- elif s.startswith(' '):\r
- # unchanged text, yield it to both sides\r
- yield _make_line(lines[:],None,0),_make_line(lines,None,1),False\r
- continue\r
- # Catch up on the blank lines so when we yield the next from/to\r
- # pair, they are lined up.\r
- while(num_blanks_to_yield < 0):\r
- num_blanks_to_yield += 1\r
- yield None,('','\n'),True\r
- while(num_blanks_to_yield > 0):\r
- num_blanks_to_yield -= 1\r
- yield ('','\n'),None,True\r
- if s.startswith('X'):\r
- raise StopIteration\r
- else:\r
- yield from_line,to_line,True\r
-\r
- def _line_pair_iterator():\r
- """Yields from/to lines of text with a change indication.\r
-\r
- This function is an iterator. It itself pulls lines from the line\r
- iterator. Its difference from that iterator is that this function\r
- always yields a pair of from/to text lines (with the change\r
- indication). If necessary it will collect single from/to lines\r
- until it has a matching pair from/to pair to yield.\r
-\r
- Note, this function is purposefully not defined at the module scope so\r
- that data it needs from its parent function (within whose context it\r
- is defined) does not need to be of module scope.\r
- """\r
- line_iterator = _line_iterator()\r
- fromlines,tolines=[],[]\r
- while True:\r
- # Collecting lines of text until we have a from/to pair\r
- while (len(fromlines)==0 or len(tolines)==0):\r
- from_line, to_line, found_diff =line_iterator.next()\r
- if from_line is not None:\r
- fromlines.append((from_line,found_diff))\r
- if to_line is not None:\r
- tolines.append((to_line,found_diff))\r
- # Once we have a pair, remove them from the collection and yield it\r
- from_line, fromDiff = fromlines.pop(0)\r
- to_line, to_diff = tolines.pop(0)\r
- yield (from_line,to_line,fromDiff or to_diff)\r
-\r
- # Handle case where user does not want context differencing, just yield\r
- # them up without doing anything else with them.\r
- line_pair_iterator = _line_pair_iterator()\r
- if context is None:\r
- while True:\r
- yield line_pair_iterator.next()\r
- # Handle case where user wants context differencing. We must do some\r
- # storage of lines until we know for sure that they are to be yielded.\r
- else:\r
- context += 1\r
- lines_to_write = 0\r
- while True:\r
- # Store lines up until we find a difference, note use of a\r
- # circular queue because we only need to keep around what\r
- # we need for context.\r
- index, contextLines = 0, [None]*(context)\r
- found_diff = False\r
- while(found_diff is False):\r
- from_line, to_line, found_diff = line_pair_iterator.next()\r
- i = index % context\r
- contextLines[i] = (from_line, to_line, found_diff)\r
- index += 1\r
- # Yield lines that we have collected so far, but first yield\r
- # the user's separator.\r
- if index > context:\r
- yield None, None, None\r
- lines_to_write = context\r
- else:\r
- lines_to_write = index\r
- index = 0\r
- while(lines_to_write):\r
- i = index % context\r
- index += 1\r
- yield contextLines[i]\r
- lines_to_write -= 1\r
- # Now yield the context lines after the change\r
- lines_to_write = context-1\r
- while(lines_to_write):\r
- from_line, to_line, found_diff = line_pair_iterator.next()\r
- # If another change within the context, extend the context\r
- if found_diff:\r
- lines_to_write = context-1\r
- else:\r
- lines_to_write -= 1\r
- yield from_line, to_line, found_diff\r
-\r
-\r
-_file_template = """\r
-<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"\r
- "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">\r
-\r
-<html>\r
-\r
-<head>\r
- <meta http-equiv="Content-Type"\r
- content="text/html; charset=ISO-8859-1" />\r
- <title></title>\r
- <style type="text/css">%(styles)s\r
- </style>\r
-</head>\r
-\r
-<body>\r
- %(table)s%(legend)s\r
-</body>\r
-\r
-</html>"""\r
-\r
-_styles = """\r
- table.diff {font-family:Courier; border:medium;}\r
- .diff_header {background-color:#e0e0e0}\r
- td.diff_header {text-align:right}\r
- .diff_next {background-color:#c0c0c0}\r
- .diff_add {background-color:#aaffaa}\r
- .diff_chg {background-color:#ffff77}\r
- .diff_sub {background-color:#ffaaaa}"""\r
-\r
-_table_template = """\r
- <table class="diff" id="difflib_chg_%(prefix)s_top"\r
- cellspacing="0" cellpadding="0" rules="groups" >\r
- <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\r
- <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\r
- %(header_row)s\r
- <tbody>\r
-%(data_rows)s </tbody>\r
- </table>"""\r
-\r
-_legend = """\r
- <table class="diff" summary="Legends">\r
- <tr> <th colspan="2"> Legends </th> </tr>\r
- <tr> <td> <table border="" summary="Colors">\r
- <tr><th> Colors </th> </tr>\r
- <tr><td class="diff_add"> Added </td></tr>\r
- <tr><td class="diff_chg">Changed</td> </tr>\r
- <tr><td class="diff_sub">Deleted</td> </tr>\r
- </table></td>\r
- <td> <table border="" summary="Links">\r
- <tr><th colspan="2"> Links </th> </tr>\r
- <tr><td>(f)irst change</td> </tr>\r
- <tr><td>(n)ext change</td> </tr>\r
- <tr><td>(t)op</td> </tr>\r
- </table></td> </tr>\r
- </table>"""\r
-\r
-class HtmlDiff(object):\r
- """For producing HTML side by side comparison with change highlights.\r
-\r
- This class can be used to create an HTML table (or a complete HTML file\r
- containing the table) showing a side by side, line by line comparison\r
- of text with inter-line and intra-line change highlights. The table can\r
- be generated in either full or contextual difference mode.\r
-\r
- The following methods are provided for HTML generation:\r
-\r
- make_table -- generates HTML for a single side by side table\r
- make_file -- generates complete HTML file with a single side by side table\r
-\r
- See tools/scripts/diff.py for an example usage of this class.\r
- """\r
-\r
- _file_template = _file_template\r
- _styles = _styles\r
- _table_template = _table_template\r
- _legend = _legend\r
- _default_prefix = 0\r
-\r
- def __init__(self,tabsize=8,wrapcolumn=None,linejunk=None,\r
- charjunk=IS_CHARACTER_JUNK):\r
- """HtmlDiff instance initializer\r
-\r
- Arguments:\r
- tabsize -- tab stop spacing, defaults to 8.\r
- wrapcolumn -- column number where lines are broken and wrapped,\r
- defaults to None where lines are not wrapped.\r
- linejunk,charjunk -- keyword arguments passed into ndiff() (used to by\r
- HtmlDiff() to generate the side by side HTML differences). See\r
- ndiff() documentation for argument default values and descriptions.\r
- """\r
- self._tabsize = tabsize\r
- self._wrapcolumn = wrapcolumn\r
- self._linejunk = linejunk\r
- self._charjunk = charjunk\r
-\r
- def make_file(self,fromlines,tolines,fromdesc='',todesc='',context=False,\r
- numlines=5):\r
- """Returns HTML file of side by side comparison with change highlights\r
-\r
- Arguments:\r
- fromlines -- list of "from" lines\r
- tolines -- list of "to" lines\r
- fromdesc -- "from" file column header string\r
- todesc -- "to" file column header string\r
- context -- set to True for contextual differences (defaults to False\r
- which shows full differences).\r
- numlines -- number of context lines. When context is set True,\r
- controls number of lines displayed before and after the change.\r
- When context is False, controls the number of lines to place\r
- the "next" link anchors before the next change (so click of\r
- "next" link jumps to just before the change).\r
- """\r
-\r
- return self._file_template % dict(\r
- styles = self._styles,\r
- legend = self._legend,\r
- table = self.make_table(fromlines,tolines,fromdesc,todesc,\r
- context=context,numlines=numlines))\r
-\r
- def _tab_newline_replace(self,fromlines,tolines):\r
- """Returns from/to line lists with tabs expanded and newlines removed.\r
-\r
- Instead of tab characters being replaced by the number of spaces\r
- needed to fill in to the next tab stop, this function will fill\r
- the space with tab characters. This is done so that the difference\r
- algorithms can identify changes in a file when tabs are replaced by\r
- spaces and vice versa. At the end of the HTML generation, the tab\r
- characters will be replaced with a nonbreakable space.\r
- """\r
- def expand_tabs(line):\r
- # hide real spaces\r
- line = line.replace(' ','\0')\r
- # expand tabs into spaces\r
- line = line.expandtabs(self._tabsize)\r
- # replace spaces from expanded tabs back into tab characters\r
- # (we'll replace them with markup after we do differencing)\r
- line = line.replace(' ','\t')\r
- return line.replace('\0',' ').rstrip('\n')\r
- fromlines = [expand_tabs(line) for line in fromlines]\r
- tolines = [expand_tabs(line) for line in tolines]\r
- return fromlines,tolines\r
-\r
- def _split_line(self,data_list,line_num,text):\r
- """Builds list of text lines by splitting text lines at wrap point\r
-\r
- This function will determine if the input text line needs to be\r
- wrapped (split) into separate lines. If so, the first wrap point\r
- will be determined and the first line appended to the output\r
- text line list. This function is used recursively to handle\r
- the second part of the split line to further split it.\r
- """\r
- # if blank line or context separator, just add it to the output list\r
- if not line_num:\r
- data_list.append((line_num,text))\r
- return\r
-\r
- # if line text doesn't need wrapping, just add it to the output list\r
- size = len(text)\r
- max = self._wrapcolumn\r
- if (size <= max) or ((size -(text.count('\0')*3)) <= max):\r
- data_list.append((line_num,text))\r
- return\r
-\r
- # scan text looking for the wrap point, keeping track if the wrap\r
- # point is inside markers\r
- i = 0\r
- n = 0\r
- mark = ''\r
- while n < max and i < size:\r
- if text[i] == '\0':\r
- i += 1\r
- mark = text[i]\r
- i += 1\r
- elif text[i] == '\1':\r
- i += 1\r
- mark = ''\r
- else:\r
- i += 1\r
- n += 1\r
-\r
- # wrap point is inside text, break it up into separate lines\r
- line1 = text[:i]\r
- line2 = text[i:]\r
-\r
- # if wrap point is inside markers, place end marker at end of first\r
- # line and start marker at beginning of second line because each\r
- # line will have its own table tag markup around it.\r
- if mark:\r
- line1 = line1 + '\1'\r
- line2 = '\0' + mark + line2\r
-\r
- # tack on first line onto the output list\r
- data_list.append((line_num,line1))\r
-\r
- # use this routine again to wrap the remaining text\r
- self._split_line(data_list,'>',line2)\r
-\r
- def _line_wrapper(self,diffs):\r
- """Returns iterator that splits (wraps) mdiff text lines"""\r
-\r
- # pull from/to data and flags from mdiff iterator\r
- for fromdata,todata,flag in diffs:\r
- # check for context separators and pass them through\r
- if flag is None:\r
- yield fromdata,todata,flag\r
- continue\r
- (fromline,fromtext),(toline,totext) = fromdata,todata\r
- # for each from/to line split it at the wrap column to form\r
- # list of text lines.\r
- fromlist,tolist = [],[]\r
- self._split_line(fromlist,fromline,fromtext)\r
- self._split_line(tolist,toline,totext)\r
- # yield from/to line in pairs inserting blank lines as\r
- # necessary when one side has more wrapped lines\r
- while fromlist or tolist:\r
- if fromlist:\r
- fromdata = fromlist.pop(0)\r
- else:\r
- fromdata = ('',' ')\r
- if tolist:\r
- todata = tolist.pop(0)\r
- else:\r
- todata = ('',' ')\r
- yield fromdata,todata,flag\r
-\r
- def _collect_lines(self,diffs):\r
- """Collects mdiff output into separate lists\r
-\r
- Before storing the mdiff from/to data into a list, it is converted\r
- into a single line of text with HTML markup.\r
- """\r
-\r
- fromlist,tolist,flaglist = [],[],[]\r
- # pull from/to data and flags from mdiff style iterator\r
- for fromdata,todata,flag in diffs:\r
- try:\r
- # store HTML markup of the lines into the lists\r
- fromlist.append(self._format_line(0,flag,*fromdata))\r
- tolist.append(self._format_line(1,flag,*todata))\r
- except TypeError:\r
- # exceptions occur for lines where context separators go\r
- fromlist.append(None)\r
- tolist.append(None)\r
- flaglist.append(flag)\r
- return fromlist,tolist,flaglist\r
-\r
- def _format_line(self,side,flag,linenum,text):\r
- """Returns HTML markup of "from" / "to" text lines\r
-\r
- side -- 0 or 1 indicating "from" or "to" text\r
- flag -- indicates if difference on line\r
- linenum -- line number (used for line number column)\r
- text -- line text to be marked up\r
- """\r
- try:\r
- linenum = '%d' % linenum\r
- id = ' id="%s%s"' % (self._prefix[side],linenum)\r
- except TypeError:\r
- # handle blank lines where linenum is '>' or ''\r
- id = ''\r
- # replace those things that would get confused with HTML symbols\r
- text=text.replace("&","&").replace(">",">").replace("<","<")\r
-\r
- # make space non-breakable so they don't get compressed or line wrapped\r
- text = text.replace(' ',' ').rstrip()\r
-\r
- return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' \\r
- % (id,linenum,text)\r
-\r
- def _make_prefix(self):\r
- """Create unique anchor prefixes"""\r
-\r
- # Generate a unique anchor prefix so multiple tables\r
- # can exist on the same HTML page without conflicts.\r
- fromprefix = "from%d_" % HtmlDiff._default_prefix\r
- toprefix = "to%d_" % HtmlDiff._default_prefix\r
- HtmlDiff._default_prefix += 1\r
- # store prefixes so line format method has access\r
- self._prefix = [fromprefix,toprefix]\r
-\r
- def _convert_flags(self,fromlist,tolist,flaglist,context,numlines):\r
- """Makes list of "next" links"""\r
-\r
- # all anchor names will be generated using the unique "to" prefix\r
- toprefix = self._prefix[1]\r
-\r
- # process change flags, generating middle column of next anchors/links\r
- next_id = ['']*len(flaglist)\r
- next_href = ['']*len(flaglist)\r
- num_chg, in_change = 0, False\r
- last = 0\r
- for i,flag in enumerate(flaglist):\r
- if flag:\r
- if not in_change:\r
- in_change = True\r
- last = i\r
- # at the beginning of a change, drop an anchor a few lines\r
- # (the context lines) before the change for the previous\r
- # link\r
- i = max([0,i-numlines])\r
- next_id[i] = ' id="difflib_chg_%s_%d"' % (toprefix,num_chg)\r
- # at the beginning of a change, drop a link to the next\r
- # change\r
- num_chg += 1\r
- next_href[last] = '<a href="#difflib_chg_%s_%d">n</a>' % (\r
- toprefix,num_chg)\r
- else:\r
- in_change = False\r
- # check for cases where there is no content to avoid exceptions\r
- if not flaglist:\r
- flaglist = [False]\r
- next_id = ['']\r
- next_href = ['']\r
- last = 0\r
- if context:\r
- fromlist = ['<td></td><td> No Differences Found </td>']\r
- tolist = fromlist\r
- else:\r
- fromlist = tolist = ['<td></td><td> Empty File </td>']\r
- # if not a change on first line, drop a link\r
- if not flaglist[0]:\r
- next_href[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix\r
- # redo the last link to link to the top\r
- next_href[last] = '<a href="#difflib_chg_%s_top">t</a>' % (toprefix)\r
-\r
- return fromlist,tolist,flaglist,next_href,next_id\r
-\r
- def make_table(self,fromlines,tolines,fromdesc='',todesc='',context=False,\r
- numlines=5):\r
- """Returns HTML table of side by side comparison with change highlights\r
-\r
- Arguments:\r
- fromlines -- list of "from" lines\r
- tolines -- list of "to" lines\r
- fromdesc -- "from" file column header string\r
- todesc -- "to" file column header string\r
- context -- set to True for contextual differences (defaults to False\r
- which shows full differences).\r
- numlines -- number of context lines. When context is set True,\r
- controls number of lines displayed before and after the change.\r
- When context is False, controls the number of lines to place\r
- the "next" link anchors before the next change (so click of\r
- "next" link jumps to just before the change).\r
- """\r
-\r
- # make unique anchor prefixes so that multiple tables may exist\r
- # on the same page without conflict.\r
- self._make_prefix()\r
-\r
- # change tabs to spaces before it gets more difficult after we insert\r
- # markkup\r
- fromlines,tolines = self._tab_newline_replace(fromlines,tolines)\r
-\r
- # create diffs iterator which generates side by side from/to data\r
- if context:\r
- context_lines = numlines\r
- else:\r
- context_lines = None\r
- diffs = _mdiff(fromlines,tolines,context_lines,linejunk=self._linejunk,\r
- charjunk=self._charjunk)\r
-\r
- # set up iterator to wrap lines that exceed desired width\r
- if self._wrapcolumn:\r
- diffs = self._line_wrapper(diffs)\r
-\r
- # collect up from/to lines and flags into lists (also format the lines)\r
- fromlist,tolist,flaglist = self._collect_lines(diffs)\r
-\r
- # process change flags, generating middle column of next anchors/links\r
- fromlist,tolist,flaglist,next_href,next_id = self._convert_flags(\r
- fromlist,tolist,flaglist,context,numlines)\r
-\r
- s = []\r
- fmt = ' <tr><td class="diff_next"%s>%s</td>%s' + \\r
- '<td class="diff_next">%s</td>%s</tr>\n'\r
- for i in range(len(flaglist)):\r
- if flaglist[i] is None:\r
- # mdiff yields None on separator lines skip the bogus ones\r
- # generated for the first line\r
- if i > 0:\r
- s.append(' </tbody> \n <tbody>\n')\r
- else:\r
- s.append( fmt % (next_id[i],next_href[i],fromlist[i],\r
- next_href[i],tolist[i]))\r
- if fromdesc or todesc:\r
- header_row = '<thead><tr>%s%s%s%s</tr></thead>' % (\r
- '<th class="diff_next"><br /></th>',\r
- '<th colspan="2" class="diff_header">%s</th>' % fromdesc,\r
- '<th class="diff_next"><br /></th>',\r
- '<th colspan="2" class="diff_header">%s</th>' % todesc)\r
- else:\r
- header_row = ''\r
-\r
- table = self._table_template % dict(\r
- data_rows=''.join(s),\r
- header_row=header_row,\r
- prefix=self._prefix[1])\r
-\r
- return table.replace('\0+','<span class="diff_add">'). \\r
- replace('\0-','<span class="diff_sub">'). \\r
- replace('\0^','<span class="diff_chg">'). \\r
- replace('\1','</span>'). \\r
- replace('\t',' ')\r
-\r
-del re\r
-\r
-def restore(delta, which):\r
- r"""\r
- Generate one of the two sequences that generated a delta.\r
-\r
- Given a `delta` produced by `Differ.compare()` or `ndiff()`, extract\r
- lines originating from file 1 or 2 (parameter `which`), stripping off line\r
- prefixes.\r
-\r
- Examples:\r
-\r
- >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),\r
- ... 'ore\ntree\nemu\n'.splitlines(1))\r
- >>> diff = list(diff)\r
- >>> print ''.join(restore(diff, 1)),\r
- one\r
- two\r
- three\r
- >>> print ''.join(restore(diff, 2)),\r
- ore\r
- tree\r
- emu\r
- """\r
- try:\r
- tag = {1: "- ", 2: "+ "}[int(which)]\r
- except KeyError:\r
- raise ValueError, ('unknown delta choice (must be 1 or 2): %r'\r
- % which)\r
- prefixes = (" ", tag)\r
- for line in delta:\r
- if line[:2] in prefixes:\r
- yield line[2:]\r
-\r
-def _test():\r
- import doctest, difflib\r
- return doctest.testmod(difflib)\r
-\r
-if __name__ == "__main__":\r
- _test()\r
projects / mirror_edk2.git / blobdiff