Show More
diff_match_patch.py
1918 lines
| 66.3 KiB
| text/x-python
|
PythonLexer
r1030 | #!/usr/bin/python2.4 | ||
from __future__ import division | |||
"""Diff Match and Patch | |||
Copyright 2006 Google Inc. | |||
http://code.google.com/p/google-diff-match-patch/ | |||
Licensed under the Apache License, Version 2.0 (the "License"); | |||
you may not use this file except in compliance with the License. | |||
You may obtain a copy of the License at | |||
http://www.apache.org/licenses/LICENSE-2.0 | |||
Unless required by applicable law or agreed to in writing, software | |||
distributed under the License is distributed on an "AS IS" BASIS, | |||
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |||
See the License for the specific language governing permissions and | |||
limitations under the License. | |||
""" | |||
"""Functions for diff, match and patch. | |||
Computes the difference between two texts to create a patch. | |||
Applies the patch onto another text, allowing for errors. | |||
""" | |||
__author__ = 'fraser@google.com (Neil Fraser)' | |||
import math | |||
import re | |||
import sys | |||
import time | |||
import urllib | |||
class diff_match_patch: | |||
"""Class containing the diff, match and patch methods. | |||
Also contains the behaviour settings. | |||
""" | |||
def __init__(self): | |||
"""Inits a diff_match_patch object with default settings. | |||
Redefine these in your program to override the defaults. | |||
""" | |||
# Number of seconds to map a diff before giving up (0 for infinity). | |||
self.Diff_Timeout = 1.0 | |||
# Cost of an empty edit operation in terms of edit characters. | |||
self.Diff_EditCost = 4 | |||
# At what point is no match declared (0.0 = perfection, 1.0 = very loose). | |||
self.Match_Threshold = 0.5 | |||
# How far to search for a match (0 = exact location, 1000+ = broad match). | |||
# A match this many characters away from the expected location will add | |||
# 1.0 to the score (0.0 is a perfect match). | |||
self.Match_Distance = 1000 | |||
# When deleting a large block of text (over ~64 characters), how close do | |||
# the contents have to be to match the expected contents. (0.0 = perfection, | |||
# 1.0 = very loose). Note that Match_Threshold controls how closely the | |||
# end points of a delete need to match. | |||
self.Patch_DeleteThreshold = 0.5 | |||
# Chunk size for context length. | |||
self.Patch_Margin = 4 | |||
# The number of bits in an int. | |||
# Python has no maximum, thus to disable patch splitting set to 0. | |||
# However to avoid long patches in certain pathological cases, use 32. | |||
# Multiple short patches (using native ints) are much faster than long ones. | |||
self.Match_MaxBits = 32 | |||
# DIFF FUNCTIONS | |||
# The data structure representing a diff is an array of tuples: | |||
# [(DIFF_DELETE, "Hello"), (DIFF_INSERT, "Goodbye"), (DIFF_EQUAL, " world.")] | |||
# which means: delete "Hello", add "Goodbye" and keep " world." | |||
DIFF_DELETE = -1 | |||
DIFF_INSERT = 1 | |||
DIFF_EQUAL = 0 | |||
def diff_main(self, text1, text2, checklines=True, deadline=None): | |||
"""Find the differences between two texts. Simplifies the problem by | |||
stripping any common prefix or suffix off the texts before diffing. | |||
Args: | |||
text1: Old string to be diffed. | |||
text2: New string to be diffed. | |||
checklines: Optional speedup flag. If present and false, then don't run | |||
a line-level diff first to identify the changed areas. | |||
Defaults to true, which does a faster, slightly less optimal diff. | |||
deadline: Optional time when the diff should be complete by. Used | |||
internally for recursive calls. Users should set DiffTimeout instead. | |||
Returns: | |||
Array of changes. | |||
""" | |||
# Set a deadline by which time the diff must be complete. | |||
if deadline == None: | |||
# Unlike in most languages, Python counts time in seconds. | |||
if self.Diff_Timeout <= 0: | |||
deadline = sys.maxint | |||
else: | |||
deadline = time.time() + self.Diff_Timeout | |||
# Check for null inputs. | |||
if text1 == None or text2 == None: | |||
raise ValueError("Null inputs. (diff_main)") | |||
# Check for equality (speedup). | |||
if text1 == text2: | |||
if text1: | |||
return [(self.DIFF_EQUAL, text1)] | |||
return [] | |||
# Trim off common prefix (speedup). | |||
commonlength = self.diff_commonPrefix(text1, text2) | |||
commonprefix = text1[:commonlength] | |||
text1 = text1[commonlength:] | |||
text2 = text2[commonlength:] | |||
# Trim off common suffix (speedup). | |||
commonlength = self.diff_commonSuffix(text1, text2) | |||
if commonlength == 0: | |||
commonsuffix = '' | |||
else: | |||
commonsuffix = text1[-commonlength:] | |||
text1 = text1[:-commonlength] | |||
text2 = text2[:-commonlength] | |||
# Compute the diff on the middle block. | |||
diffs = self.diff_compute(text1, text2, checklines, deadline) | |||
# Restore the prefix and suffix. | |||
if commonprefix: | |||
diffs[:0] = [(self.DIFF_EQUAL, commonprefix)] | |||
if commonsuffix: | |||
diffs.append((self.DIFF_EQUAL, commonsuffix)) | |||
self.diff_cleanupMerge(diffs) | |||
return diffs | |||
def diff_compute(self, text1, text2, checklines, deadline): | |||
"""Find the differences between two texts. Assumes that the texts do not | |||
have any common prefix or suffix. | |||
Args: | |||
text1: Old string to be diffed. | |||
text2: New string to be diffed. | |||
checklines: Speedup flag. If false, then don't run a line-level diff | |||
first to identify the changed areas. | |||
If true, then run a faster, slightly less optimal diff. | |||
deadline: Time when the diff should be complete by. | |||
Returns: | |||
Array of changes. | |||
""" | |||
if not text1: | |||
# Just add some text (speedup). | |||
return [(self.DIFF_INSERT, text2)] | |||
if not text2: | |||
# Just delete some text (speedup). | |||
return [(self.DIFF_DELETE, text1)] | |||
if len(text1) > len(text2): | |||
(longtext, shorttext) = (text1, text2) | |||
else: | |||
(shorttext, longtext) = (text1, text2) | |||
i = longtext.find(shorttext) | |||
if i != -1: | |||
# Shorter text is inside the longer text (speedup). | |||
diffs = [(self.DIFF_INSERT, longtext[:i]), (self.DIFF_EQUAL, shorttext), | |||
(self.DIFF_INSERT, longtext[i + len(shorttext):])] | |||
# Swap insertions for deletions if diff is reversed. | |||
if len(text1) > len(text2): | |||
diffs[0] = (self.DIFF_DELETE, diffs[0][1]) | |||
diffs[2] = (self.DIFF_DELETE, diffs[2][1]) | |||
return diffs | |||
if len(shorttext) == 1: | |||
# Single character string. | |||
# After the previous speedup, the character can't be an equality. | |||
return [(self.DIFF_DELETE, text1), (self.DIFF_INSERT, text2)] | |||
# Check to see if the problem can be split in two. | |||
hm = self.diff_halfMatch(text1, text2) | |||
if hm: | |||
# A half-match was found, sort out the return data. | |||
(text1_a, text1_b, text2_a, text2_b, mid_common) = hm | |||
# Send both pairs off for separate processing. | |||
diffs_a = self.diff_main(text1_a, text2_a, checklines, deadline) | |||
diffs_b = self.diff_main(text1_b, text2_b, checklines, deadline) | |||
# Merge the results. | |||
return diffs_a + [(self.DIFF_EQUAL, mid_common)] + diffs_b | |||
if checklines and len(text1) > 100 and len(text2) > 100: | |||
return self.diff_lineMode(text1, text2, deadline) | |||
return self.diff_bisect(text1, text2, deadline) | |||
def diff_lineMode(self, text1, text2, deadline): | |||
"""Do a quick line-level diff on both strings, then rediff the parts for | |||
greater accuracy. | |||
This speedup can produce non-minimal diffs. | |||
Args: | |||
text1: Old string to be diffed. | |||
text2: New string to be diffed. | |||
deadline: Time when the diff should be complete by. | |||
Returns: | |||
Array of changes. | |||
""" | |||
# Scan the text on a line-by-line basis first. | |||
(text1, text2, linearray) = self.diff_linesToChars(text1, text2) | |||
diffs = self.diff_main(text1, text2, False, deadline) | |||
# Convert the diff back to original text. | |||
self.diff_charsToLines(diffs, linearray) | |||
# Eliminate freak matches (e.g. blank lines) | |||
self.diff_cleanupSemantic(diffs) | |||
# Rediff any replacement blocks, this time character-by-character. | |||
# Add a dummy entry at the end. | |||
diffs.append((self.DIFF_EQUAL, '')) | |||
pointer = 0 | |||
count_delete = 0 | |||
count_insert = 0 | |||
text_delete = '' | |||
text_insert = '' | |||
while pointer < len(diffs): | |||
if diffs[pointer][0] == self.DIFF_INSERT: | |||
count_insert += 1 | |||
text_insert += diffs[pointer][1] | |||
elif diffs[pointer][0] == self.DIFF_DELETE: | |||
count_delete += 1 | |||
text_delete += diffs[pointer][1] | |||
elif diffs[pointer][0] == self.DIFF_EQUAL: | |||
# Upon reaching an equality, check for prior redundancies. | |||
if count_delete >= 1 and count_insert >= 1: | |||
# Delete the offending records and add the merged ones. | |||
a = self.diff_main(text_delete, text_insert, False, deadline) | |||
diffs[pointer - count_delete - count_insert : pointer] = a | |||
pointer = pointer - count_delete - count_insert + len(a) | |||
count_insert = 0 | |||
count_delete = 0 | |||
text_delete = '' | |||
text_insert = '' | |||
pointer += 1 | |||
diffs.pop() # Remove the dummy entry at the end. | |||
return diffs | |||
def diff_bisect(self, text1, text2, deadline): | |||
"""Find the 'middle snake' of a diff, split the problem in two | |||
and return the recursively constructed diff. | |||
See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations. | |||
Args: | |||
text1: Old string to be diffed. | |||
text2: New string to be diffed. | |||
deadline: Time at which to bail if not yet complete. | |||
Returns: | |||
Array of diff tuples. | |||
""" | |||
# Cache the text lengths to prevent multiple calls. | |||
text1_length = len(text1) | |||
text2_length = len(text2) | |||
max_d = (text1_length + text2_length + 1) // 2 | |||
v_offset = max_d | |||
v_length = 2 * max_d | |||
v1 = [-1] * v_length | |||
v1[v_offset + 1] = 0 | |||
v2 = v1[:] | |||
delta = text1_length - text2_length | |||
# If the total number of characters is odd, then the front path will | |||
# collide with the reverse path. | |||
front = (delta % 2 != 0) | |||
# Offsets for start and end of k loop. | |||
# Prevents mapping of space beyond the grid. | |||
k1start = 0 | |||
k1end = 0 | |||
k2start = 0 | |||
k2end = 0 | |||
for d in xrange(max_d): | |||
# Bail out if deadline is reached. | |||
if time.time() > deadline: | |||
break | |||
# Walk the front path one step. | |||
for k1 in xrange(-d + k1start, d + 1 - k1end, 2): | |||
k1_offset = v_offset + k1 | |||
if k1 == -d or (k1 != d and | |||
v1[k1_offset - 1] < v1[k1_offset + 1]): | |||
x1 = v1[k1_offset + 1] | |||
else: | |||
x1 = v1[k1_offset - 1] + 1 | |||
y1 = x1 - k1 | |||
while (x1 < text1_length and y1 < text2_length and | |||
text1[x1] == text2[y1]): | |||
x1 += 1 | |||
y1 += 1 | |||
v1[k1_offset] = x1 | |||
if x1 > text1_length: | |||
# Ran off the right of the graph. | |||
k1end += 2 | |||
elif y1 > text2_length: | |||
# Ran off the bottom of the graph. | |||
k1start += 2 | |||
elif front: | |||
k2_offset = v_offset + delta - k1 | |||
if k2_offset >= 0 and k2_offset < v_length and v2[k2_offset] != -1: | |||
# Mirror x2 onto top-left coordinate system. | |||
x2 = text1_length - v2[k2_offset] | |||
if x1 >= x2: | |||
# Overlap detected. | |||
return self.diff_bisectSplit(text1, text2, x1, y1, deadline) | |||
# Walk the reverse path one step. | |||
for k2 in xrange(-d + k2start, d + 1 - k2end, 2): | |||
k2_offset = v_offset + k2 | |||
if k2 == -d or (k2 != d and | |||
v2[k2_offset - 1] < v2[k2_offset + 1]): | |||
x2 = v2[k2_offset + 1] | |||
else: | |||
x2 = v2[k2_offset - 1] + 1 | |||
y2 = x2 - k2 | |||
while (x2 < text1_length and y2 < text2_length and | |||
text1[-x2 - 1] == text2[-y2 - 1]): | |||
x2 += 1 | |||
y2 += 1 | |||
v2[k2_offset] = x2 | |||
if x2 > text1_length: | |||
# Ran off the left of the graph. | |||
k2end += 2 | |||
elif y2 > text2_length: | |||
# Ran off the top of the graph. | |||
k2start += 2 | |||
elif not front: | |||
k1_offset = v_offset + delta - k2 | |||
if k1_offset >= 0 and k1_offset < v_length and v1[k1_offset] != -1: | |||
x1 = v1[k1_offset] | |||
y1 = v_offset + x1 - k1_offset | |||
# Mirror x2 onto top-left coordinate system. | |||
x2 = text1_length - x2 | |||
if x1 >= x2: | |||
# Overlap detected. | |||
return self.diff_bisectSplit(text1, text2, x1, y1, deadline) | |||
# Diff took too long and hit the deadline or | |||
# number of diffs equals number of characters, no commonality at all. | |||
return [(self.DIFF_DELETE, text1), (self.DIFF_INSERT, text2)] | |||
def diff_bisectSplit(self, text1, text2, x, y, deadline): | |||
"""Given the location of the 'middle snake', split the diff in two parts | |||
and recurse. | |||
Args: | |||
text1: Old string to be diffed. | |||
text2: New string to be diffed. | |||
x: Index of split point in text1. | |||
y: Index of split point in text2. | |||
deadline: Time at which to bail if not yet complete. | |||
Returns: | |||
Array of diff tuples. | |||
""" | |||
text1a = text1[:x] | |||
text2a = text2[:y] | |||
text1b = text1[x:] | |||
text2b = text2[y:] | |||
# Compute both diffs serially. | |||
diffs = self.diff_main(text1a, text2a, False, deadline) | |||
diffsb = self.diff_main(text1b, text2b, False, deadline) | |||
return diffs + diffsb | |||
def diff_linesToChars(self, text1, text2): | |||
"""Split two texts into an array of strings. Reduce the texts to a string | |||
of hashes where each Unicode character represents one line. | |||
Args: | |||
text1: First string. | |||
text2: Second string. | |||
Returns: | |||
Three element tuple, containing the encoded text1, the encoded text2 and | |||
the array of unique strings. The zeroth element of the array of unique | |||
strings is intentionally blank. | |||
""" | |||
lineArray = [] # e.g. lineArray[4] == "Hello\n" | |||
lineHash = {} # e.g. lineHash["Hello\n"] == 4 | |||
# "\x00" is a valid character, but various debuggers don't like it. | |||
# So we'll insert a junk entry to avoid generating a null character. | |||
lineArray.append('') | |||
def diff_linesToCharsMunge(text): | |||
"""Split a text into an array of strings. Reduce the texts to a string | |||
of hashes where each Unicode character represents one line. | |||
Modifies linearray and linehash through being a closure. | |||
Args: | |||
text: String to encode. | |||
Returns: | |||
Encoded string. | |||
""" | |||
chars = [] | |||
# Walk the text, pulling out a substring for each line. | |||
# text.split('\n') would would temporarily double our memory footprint. | |||
# Modifying text would create many large strings to garbage collect. | |||
lineStart = 0 | |||
lineEnd = -1 | |||
while lineEnd < len(text) - 1: | |||
lineEnd = text.find('\n', lineStart) | |||
if lineEnd == -1: | |||
lineEnd = len(text) - 1 | |||
line = text[lineStart:lineEnd + 1] | |||
lineStart = lineEnd + 1 | |||
if line in lineHash: | |||
chars.append(unichr(lineHash[line])) | |||
else: | |||
lineArray.append(line) | |||
lineHash[line] = len(lineArray) - 1 | |||
chars.append(unichr(len(lineArray) - 1)) | |||
return "".join(chars) | |||
chars1 = diff_linesToCharsMunge(text1) | |||
chars2 = diff_linesToCharsMunge(text2) | |||
return (chars1, chars2, lineArray) | |||
def diff_charsToLines(self, diffs, lineArray): | |||
"""Rehydrate the text in a diff from a string of line hashes to real lines | |||
of text. | |||
Args: | |||
diffs: Array of diff tuples. | |||
lineArray: Array of unique strings. | |||
""" | |||
for x in xrange(len(diffs)): | |||
text = [] | |||
for char in diffs[x][1]: | |||
text.append(lineArray[ord(char)]) | |||
diffs[x] = (diffs[x][0], "".join(text)) | |||
def diff_commonPrefix(self, text1, text2): | |||
"""Determine the common prefix of two strings. | |||
Args: | |||
text1: First string. | |||
text2: Second string. | |||
Returns: | |||
The number of characters common to the start of each string. | |||
""" | |||
# Quick check for common null cases. | |||
if not text1 or not text2 or text1[0] != text2[0]: | |||
return 0 | |||
# Binary search. | |||
# Performance analysis: http://neil.fraser.name/news/2007/10/09/ | |||
pointermin = 0 | |||
pointermax = min(len(text1), len(text2)) | |||
pointermid = pointermax | |||
pointerstart = 0 | |||
while pointermin < pointermid: | |||
if text1[pointerstart:pointermid] == text2[pointerstart:pointermid]: | |||
pointermin = pointermid | |||
pointerstart = pointermin | |||
else: | |||
pointermax = pointermid | |||
pointermid = (pointermax - pointermin) // 2 + pointermin | |||
return pointermid | |||
def diff_commonSuffix(self, text1, text2): | |||
"""Determine the common suffix of two strings. | |||
Args: | |||
text1: First string. | |||
text2: Second string. | |||
Returns: | |||
The number of characters common to the end of each string. | |||
""" | |||
# Quick check for common null cases. | |||
if not text1 or not text2 or text1[-1] != text2[-1]: | |||
return 0 | |||
# Binary search. | |||
# Performance analysis: http://neil.fraser.name/news/2007/10/09/ | |||
pointermin = 0 | |||
pointermax = min(len(text1), len(text2)) | |||
pointermid = pointermax | |||
pointerend = 0 | |||
while pointermin < pointermid: | |||
if (text1[-pointermid:len(text1) - pointerend] == | |||
text2[-pointermid:len(text2) - pointerend]): | |||
pointermin = pointermid | |||
pointerend = pointermin | |||
else: | |||
pointermax = pointermid | |||
pointermid = (pointermax - pointermin) // 2 + pointermin | |||
return pointermid | |||
def diff_commonOverlap(self, text1, text2): | |||
"""Determine if the suffix of one string is the prefix of another. | |||
Args: | |||
text1 First string. | |||
text2 Second string. | |||
Returns: | |||
The number of characters common to the end of the first | |||
string and the start of the second string. | |||
""" | |||
# Cache the text lengths to prevent multiple calls. | |||
text1_length = len(text1) | |||
text2_length = len(text2) | |||
# Eliminate the null case. | |||
if text1_length == 0 or text2_length == 0: | |||
return 0 | |||
# Truncate the longer string. | |||
if text1_length > text2_length: | |||
text1 = text1[-text2_length:] | |||
elif text1_length < text2_length: | |||
text2 = text2[:text1_length] | |||
text_length = min(text1_length, text2_length) | |||
# Quick check for the worst case. | |||
if text1 == text2: | |||
return text_length | |||
# Start by looking for a single character match | |||
# and increase length until no match is found. | |||
# Performance analysis: http://neil.fraser.name/news/2010/11/04/ | |||
best = 0 | |||
length = 1 | |||
while True: | |||
pattern = text1[-length:] | |||
found = text2.find(pattern) | |||
if found == -1: | |||
return best | |||
length += found | |||
if found == 0 or text1[-length:] == text2[:length]: | |||
best = length | |||
length += 1 | |||
def diff_halfMatch(self, text1, text2): | |||
"""Do the two texts share a substring which is at least half the length of | |||
the longer text? | |||
This speedup can produce non-minimal diffs. | |||
Args: | |||
text1: First string. | |||
text2: Second string. | |||
Returns: | |||
Five element Array, containing the prefix of text1, the suffix of text1, | |||
the prefix of text2, the suffix of text2 and the common middle. Or None | |||
if there was no match. | |||
""" | |||
if self.Diff_Timeout <= 0: | |||
# Don't risk returning a non-optimal diff if we have unlimited time. | |||
return None | |||
if len(text1) > len(text2): | |||
(longtext, shorttext) = (text1, text2) | |||
else: | |||
(shorttext, longtext) = (text1, text2) | |||
if len(longtext) < 4 or len(shorttext) * 2 < len(longtext): | |||
return None # Pointless. | |||
def diff_halfMatchI(longtext, shorttext, i): | |||
"""Does a substring of shorttext exist within longtext such that the | |||
substring is at least half the length of longtext? | |||
Closure, but does not reference any external variables. | |||
Args: | |||
longtext: Longer string. | |||
shorttext: Shorter string. | |||
i: Start index of quarter length substring within longtext. | |||
Returns: | |||
Five element Array, containing the prefix of longtext, the suffix of | |||
longtext, the prefix of shorttext, the suffix of shorttext and the | |||
common middle. Or None if there was no match. | |||
""" | |||
seed = longtext[i:i + len(longtext) // 4] | |||
best_common = '' | |||
j = shorttext.find(seed) | |||
while j != -1: | |||
prefixLength = self.diff_commonPrefix(longtext[i:], shorttext[j:]) | |||
suffixLength = self.diff_commonSuffix(longtext[:i], shorttext[:j]) | |||
if len(best_common) < suffixLength + prefixLength: | |||
best_common = (shorttext[j - suffixLength:j] + | |||
shorttext[j:j + prefixLength]) | |||
best_longtext_a = longtext[:i - suffixLength] | |||
best_longtext_b = longtext[i + prefixLength:] | |||
best_shorttext_a = shorttext[:j - suffixLength] | |||
best_shorttext_b = shorttext[j + prefixLength:] | |||
j = shorttext.find(seed, j + 1) | |||
if len(best_common) * 2 >= len(longtext): | |||
return (best_longtext_a, best_longtext_b, | |||
best_shorttext_a, best_shorttext_b, best_common) | |||
else: | |||
return None | |||
# First check if the second quarter is the seed for a half-match. | |||
hm1 = diff_halfMatchI(longtext, shorttext, (len(longtext) + 3) // 4) | |||
# Check again based on the third quarter. | |||
hm2 = diff_halfMatchI(longtext, shorttext, (len(longtext) + 1) // 2) | |||
if not hm1 and not hm2: | |||
return None | |||
elif not hm2: | |||
hm = hm1 | |||
elif not hm1: | |||
hm = hm2 | |||
else: | |||
# Both matched. Select the longest. | |||
if len(hm1[4]) > len(hm2[4]): | |||
hm = hm1 | |||
else: | |||
hm = hm2 | |||
# A half-match was found, sort out the return data. | |||
if len(text1) > len(text2): | |||
(text1_a, text1_b, text2_a, text2_b, mid_common) = hm | |||
else: | |||
(text2_a, text2_b, text1_a, text1_b, mid_common) = hm | |||
return (text1_a, text1_b, text2_a, text2_b, mid_common) | |||
def diff_cleanupSemantic(self, diffs): | |||
"""Reduce the number of edits by eliminating semantically trivial | |||
equalities. | |||
Args: | |||
diffs: Array of diff tuples. | |||
""" | |||
changes = False | |||
equalities = [] # Stack of indices where equalities are found. | |||
lastequality = None # Always equal to diffs[equalities[-1]][1] | |||
pointer = 0 # Index of current position. | |||
# Number of chars that changed prior to the equality. | |||
length_insertions1, length_deletions1 = 0, 0 | |||
# Number of chars that changed after the equality. | |||
length_insertions2, length_deletions2 = 0, 0 | |||
while pointer < len(diffs): | |||
if diffs[pointer][0] == self.DIFF_EQUAL: # Equality found. | |||
equalities.append(pointer) | |||
length_insertions1, length_insertions2 = length_insertions2, 0 | |||
length_deletions1, length_deletions2 = length_deletions2, 0 | |||
lastequality = diffs[pointer][1] | |||
else: # An insertion or deletion. | |||
if diffs[pointer][0] == self.DIFF_INSERT: | |||
length_insertions2 += len(diffs[pointer][1]) | |||
else: | |||
length_deletions2 += len(diffs[pointer][1]) | |||
# Eliminate an equality that is smaller or equal to the edits on both | |||
# sides of it. | |||
if (lastequality and (len(lastequality) <= | |||
max(length_insertions1, length_deletions1)) and | |||
(len(lastequality) <= max(length_insertions2, length_deletions2))): | |||
# Duplicate record. | |||
diffs.insert(equalities[-1], (self.DIFF_DELETE, lastequality)) | |||
# Change second copy to insert. | |||
diffs[equalities[-1] + 1] = (self.DIFF_INSERT, | |||
diffs[equalities[-1] + 1][1]) | |||
# Throw away the equality we just deleted. | |||
equalities.pop() | |||
# Throw away the previous equality (it needs to be reevaluated). | |||
if len(equalities): | |||
equalities.pop() | |||
if len(equalities): | |||
pointer = equalities[-1] | |||
else: | |||
pointer = -1 | |||
# Reset the counters. | |||
length_insertions1, length_deletions1 = 0, 0 | |||
length_insertions2, length_deletions2 = 0, 0 | |||
lastequality = None | |||
changes = True | |||
pointer += 1 | |||
# Normalize the diff. | |||
if changes: | |||
self.diff_cleanupMerge(diffs) | |||
self.diff_cleanupSemanticLossless(diffs) | |||
# Find any overlaps between deletions and insertions. | |||
# e.g: <del>abcxxx</del><ins>xxxdef</ins> | |||
# -> <del>abc</del>xxx<ins>def</ins> | |||
# e.g: <del>xxxabc</del><ins>defxxx</ins> | |||
# -> <ins>def</ins>xxx<del>abc</del> | |||
# Only extract an overlap if it is as big as the edit ahead or behind it. | |||
pointer = 1 | |||
while pointer < len(diffs): | |||
if (diffs[pointer - 1][0] == self.DIFF_DELETE and | |||
diffs[pointer][0] == self.DIFF_INSERT): | |||
deletion = diffs[pointer - 1][1] | |||
insertion = diffs[pointer][1] | |||
overlap_length1 = self.diff_commonOverlap(deletion, insertion) | |||
overlap_length2 = self.diff_commonOverlap(insertion, deletion) | |||
if overlap_length1 >= overlap_length2: | |||
if (overlap_length1 >= len(deletion) / 2.0 or | |||
overlap_length1 >= len(insertion) / 2.0): | |||
# Overlap found. Insert an equality and trim the surrounding edits. | |||
diffs.insert(pointer, (self.DIFF_EQUAL, | |||
insertion[:overlap_length1])) | |||
diffs[pointer - 1] = (self.DIFF_DELETE, | |||
deletion[:len(deletion) - overlap_length1]) | |||
diffs[pointer + 1] = (self.DIFF_INSERT, | |||
insertion[overlap_length1:]) | |||
pointer += 1 | |||
else: | |||
if (overlap_length2 >= len(deletion) / 2.0 or | |||
overlap_length2 >= len(insertion) / 2.0): | |||
# Reverse overlap found. | |||
# Insert an equality and swap and trim the surrounding edits. | |||
diffs.insert(pointer, (self.DIFF_EQUAL, deletion[:overlap_length2])) | |||
diffs[pointer - 1] = (self.DIFF_INSERT, | |||
insertion[:len(insertion) - overlap_length2]) | |||
diffs[pointer + 1] = (self.DIFF_DELETE, deletion[overlap_length2:]) | |||
pointer += 1 | |||
pointer += 1 | |||
pointer += 1 | |||
def diff_cleanupSemanticLossless(self, diffs): | |||
"""Look for single edits surrounded on both sides by equalities | |||
which can be shifted sideways to align the edit to a word boundary. | |||
e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came. | |||
Args: | |||
diffs: Array of diff tuples. | |||
""" | |||
def diff_cleanupSemanticScore(one, two): | |||
"""Given two strings, compute a score representing whether the | |||
internal boundary falls on logical boundaries. | |||
Scores range from 6 (best) to 0 (worst). | |||
Closure, but does not reference any external variables. | |||
Args: | |||
one: First string. | |||
two: Second string. | |||
Returns: | |||
The score. | |||
""" | |||
if not one or not two: | |||
# Edges are the best. | |||
return 6 | |||
# Each port of this function behaves slightly differently due to | |||
# subtle differences in each language's definition of things like | |||
# 'whitespace'. Since this function's purpose is largely cosmetic, | |||
# the choice has been made to use each language's native features | |||
# rather than force total conformity. | |||
char1 = one[-1] | |||
char2 = two[0] | |||
nonAlphaNumeric1 = not char1.isalnum() | |||
nonAlphaNumeric2 = not char2.isalnum() | |||
whitespace1 = nonAlphaNumeric1 and char1.isspace() | |||
whitespace2 = nonAlphaNumeric2 and char2.isspace() | |||
lineBreak1 = whitespace1 and (char1 == "\r" or char1 == "\n") | |||
lineBreak2 = whitespace2 and (char2 == "\r" or char2 == "\n") | |||
blankLine1 = lineBreak1 and self.BLANKLINEEND.search(one) | |||
blankLine2 = lineBreak2 and self.BLANKLINESTART.match(two) | |||
if blankLine1 or blankLine2: | |||
# Five points for blank lines. | |||
return 5 | |||
elif lineBreak1 or lineBreak2: | |||
# Four points for line breaks. | |||
return 4 | |||
elif nonAlphaNumeric1 and not whitespace1 and whitespace2: | |||
# Three points for end of sentences. | |||
return 3 | |||
elif whitespace1 or whitespace2: | |||
# Two points for whitespace. | |||
return 2 | |||
elif nonAlphaNumeric1 or nonAlphaNumeric2: | |||
# One point for non-alphanumeric. | |||
return 1 | |||
return 0 | |||
pointer = 1 | |||
# Intentionally ignore the first and last element (don't need checking). | |||
while pointer < len(diffs) - 1: | |||
if (diffs[pointer - 1][0] == self.DIFF_EQUAL and | |||
diffs[pointer + 1][0] == self.DIFF_EQUAL): | |||
# This is a single edit surrounded by equalities. | |||
equality1 = diffs[pointer - 1][1] | |||
edit = diffs[pointer][1] | |||
equality2 = diffs[pointer + 1][1] | |||
# First, shift the edit as far left as possible. | |||
commonOffset = self.diff_commonSuffix(equality1, edit) | |||
if commonOffset: | |||
commonString = edit[-commonOffset:] | |||
equality1 = equality1[:-commonOffset] | |||
edit = commonString + edit[:-commonOffset] | |||
equality2 = commonString + equality2 | |||
# Second, step character by character right, looking for the best fit. | |||
bestEquality1 = equality1 | |||
bestEdit = edit | |||
bestEquality2 = equality2 | |||
bestScore = (diff_cleanupSemanticScore(equality1, edit) + | |||
diff_cleanupSemanticScore(edit, equality2)) | |||
while edit and equality2 and edit[0] == equality2[0]: | |||
equality1 += edit[0] | |||
edit = edit[1:] + equality2[0] | |||
equality2 = equality2[1:] | |||
score = (diff_cleanupSemanticScore(equality1, edit) + | |||
diff_cleanupSemanticScore(edit, equality2)) | |||
# The >= encourages trailing rather than leading whitespace on edits. | |||
if score >= bestScore: | |||
bestScore = score | |||
bestEquality1 = equality1 | |||
bestEdit = edit | |||
bestEquality2 = equality2 | |||
if diffs[pointer - 1][1] != bestEquality1: | |||
# We have an improvement, save it back to the diff. | |||
if bestEquality1: | |||
diffs[pointer - 1] = (diffs[pointer - 1][0], bestEquality1) | |||
else: | |||
del diffs[pointer - 1] | |||
pointer -= 1 | |||
diffs[pointer] = (diffs[pointer][0], bestEdit) | |||
if bestEquality2: | |||
diffs[pointer + 1] = (diffs[pointer + 1][0], bestEquality2) | |||
else: | |||
del diffs[pointer + 1] | |||
pointer -= 1 | |||
pointer += 1 | |||
# Define some regex patterns for matching boundaries. | |||
BLANKLINEEND = re.compile(r"\n\r?\n$"); | |||
BLANKLINESTART = re.compile(r"^\r?\n\r?\n"); | |||
def diff_cleanupEfficiency(self, diffs): | |||
"""Reduce the number of edits by eliminating operationally trivial | |||
equalities. | |||
Args: | |||
diffs: Array of diff tuples. | |||
""" | |||
changes = False | |||
equalities = [] # Stack of indices where equalities are found. | |||
lastequality = None # Always equal to diffs[equalities[-1]][1] | |||
pointer = 0 # Index of current position. | |||
pre_ins = False # Is there an insertion operation before the last equality. | |||
pre_del = False # Is there a deletion operation before the last equality. | |||
post_ins = False # Is there an insertion operation after the last equality. | |||
post_del = False # Is there a deletion operation after the last equality. | |||
while pointer < len(diffs): | |||
if diffs[pointer][0] == self.DIFF_EQUAL: # Equality found. | |||
if (len(diffs[pointer][1]) < self.Diff_EditCost and | |||
(post_ins or post_del)): | |||
# Candidate found. | |||
equalities.append(pointer) | |||
pre_ins = post_ins | |||
pre_del = post_del | |||
lastequality = diffs[pointer][1] | |||
else: | |||
# Not a candidate, and can never become one. | |||
equalities = [] | |||
lastequality = None | |||
post_ins = post_del = False | |||
else: # An insertion or deletion. | |||
if diffs[pointer][0] == self.DIFF_DELETE: | |||
post_del = True | |||
else: | |||
post_ins = True | |||
# Five types to be split: | |||
# <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del> | |||
# <ins>A</ins>X<ins>C</ins><del>D</del> | |||
# <ins>A</ins><del>B</del>X<ins>C</ins> | |||
# <ins>A</del>X<ins>C</ins><del>D</del> | |||
# <ins>A</ins><del>B</del>X<del>C</del> | |||
if lastequality and ((pre_ins and pre_del and post_ins and post_del) or | |||
((len(lastequality) < self.Diff_EditCost / 2) and | |||
(pre_ins + pre_del + post_ins + post_del) == 3)): | |||
# Duplicate record. | |||
diffs.insert(equalities[-1], (self.DIFF_DELETE, lastequality)) | |||
# Change second copy to insert. | |||
diffs[equalities[-1] + 1] = (self.DIFF_INSERT, | |||
diffs[equalities[-1] + 1][1]) | |||
equalities.pop() # Throw away the equality we just deleted. | |||
lastequality = None | |||
if pre_ins and pre_del: | |||
# No changes made which could affect previous entry, keep going. | |||
post_ins = post_del = True | |||
equalities = [] | |||
else: | |||
if len(equalities): | |||
equalities.pop() # Throw away the previous equality. | |||
if len(equalities): | |||
pointer = equalities[-1] | |||
else: | |||
pointer = -1 | |||
post_ins = post_del = False | |||
changes = True | |||
pointer += 1 | |||
if changes: | |||
self.diff_cleanupMerge(diffs) | |||
def diff_cleanupMerge(self, diffs): | |||
"""Reorder and merge like edit sections. Merge equalities. | |||
Any edit section can move as long as it doesn't cross an equality. | |||
Args: | |||
diffs: Array of diff tuples. | |||
""" | |||
diffs.append((self.DIFF_EQUAL, '')) # Add a dummy entry at the end. | |||
pointer = 0 | |||
count_delete = 0 | |||
count_insert = 0 | |||
text_delete = '' | |||
text_insert = '' | |||
while pointer < len(diffs): | |||
if diffs[pointer][0] == self.DIFF_INSERT: | |||
count_insert += 1 | |||
text_insert += diffs[pointer][1] | |||
pointer += 1 | |||
elif diffs[pointer][0] == self.DIFF_DELETE: | |||
count_delete += 1 | |||
text_delete += diffs[pointer][1] | |||
pointer += 1 | |||
elif diffs[pointer][0] == self.DIFF_EQUAL: | |||
# Upon reaching an equality, check for prior redundancies. | |||
if count_delete + count_insert > 1: | |||
if count_delete != 0 and count_insert != 0: | |||
# Factor out any common prefixies. | |||
commonlength = self.diff_commonPrefix(text_insert, text_delete) | |||
if commonlength != 0: | |||
x = pointer - count_delete - count_insert - 1 | |||
if x >= 0 and diffs[x][0] == self.DIFF_EQUAL: | |||
diffs[x] = (diffs[x][0], diffs[x][1] + | |||
text_insert[:commonlength]) | |||
else: | |||
diffs.insert(0, (self.DIFF_EQUAL, text_insert[:commonlength])) | |||
pointer += 1 | |||
text_insert = text_insert[commonlength:] | |||
text_delete = text_delete[commonlength:] | |||
# Factor out any common suffixies. | |||
commonlength = self.diff_commonSuffix(text_insert, text_delete) | |||
if commonlength != 0: | |||
diffs[pointer] = (diffs[pointer][0], text_insert[-commonlength:] + | |||
diffs[pointer][1]) | |||
text_insert = text_insert[:-commonlength] | |||
text_delete = text_delete[:-commonlength] | |||
# Delete the offending records and add the merged ones. | |||
if count_delete == 0: | |||
diffs[pointer - count_insert : pointer] = [ | |||
(self.DIFF_INSERT, text_insert)] | |||
elif count_insert == 0: | |||
diffs[pointer - count_delete : pointer] = [ | |||
(self.DIFF_DELETE, text_delete)] | |||
else: | |||
diffs[pointer - count_delete - count_insert : pointer] = [ | |||
(self.DIFF_DELETE, text_delete), | |||
(self.DIFF_INSERT, text_insert)] | |||
pointer = pointer - count_delete - count_insert + 1 | |||
if count_delete != 0: | |||
pointer += 1 | |||
if count_insert != 0: | |||
pointer += 1 | |||
elif pointer != 0 and diffs[pointer - 1][0] == self.DIFF_EQUAL: | |||
# Merge this equality with the previous one. | |||
diffs[pointer - 1] = (diffs[pointer - 1][0], | |||
diffs[pointer - 1][1] + diffs[pointer][1]) | |||
del diffs[pointer] | |||
else: | |||
pointer += 1 | |||
count_insert = 0 | |||
count_delete = 0 | |||
text_delete = '' | |||
text_insert = '' | |||
if diffs[-1][1] == '': | |||
diffs.pop() # Remove the dummy entry at the end. | |||
# Second pass: look for single edits surrounded on both sides by equalities | |||
# which can be shifted sideways to eliminate an equality. | |||
# e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC | |||
changes = False | |||
pointer = 1 | |||
# Intentionally ignore the first and last element (don't need checking). | |||
while pointer < len(diffs) - 1: | |||
if (diffs[pointer - 1][0] == self.DIFF_EQUAL and | |||
diffs[pointer + 1][0] == self.DIFF_EQUAL): | |||
# This is a single edit surrounded by equalities. | |||
if diffs[pointer][1].endswith(diffs[pointer - 1][1]): | |||
# Shift the edit over the previous equality. | |||
diffs[pointer] = (diffs[pointer][0], | |||
diffs[pointer - 1][1] + | |||
diffs[pointer][1][:-len(diffs[pointer - 1][1])]) | |||
diffs[pointer + 1] = (diffs[pointer + 1][0], | |||
diffs[pointer - 1][1] + diffs[pointer + 1][1]) | |||
del diffs[pointer - 1] | |||
changes = True | |||
elif diffs[pointer][1].startswith(diffs[pointer + 1][1]): | |||
# Shift the edit over the next equality. | |||
diffs[pointer - 1] = (diffs[pointer - 1][0], | |||
diffs[pointer - 1][1] + diffs[pointer + 1][1]) | |||
diffs[pointer] = (diffs[pointer][0], | |||
diffs[pointer][1][len(diffs[pointer + 1][1]):] + | |||
diffs[pointer + 1][1]) | |||
del diffs[pointer + 1] | |||
changes = True | |||
pointer += 1 | |||
# If shifts were made, the diff needs reordering and another shift sweep. | |||
if changes: | |||
self.diff_cleanupMerge(diffs) | |||
def diff_xIndex(self, diffs, loc): | |||
"""loc is a location in text1, compute and return the equivalent location | |||
in text2. e.g. "The cat" vs "The big cat", 1->1, 5->8 | |||
Args: | |||
diffs: Array of diff tuples. | |||
loc: Location within text1. | |||
Returns: | |||
Location within text2. | |||
""" | |||
chars1 = 0 | |||
chars2 = 0 | |||
last_chars1 = 0 | |||
last_chars2 = 0 | |||
for x in xrange(len(diffs)): | |||
(op, text) = diffs[x] | |||
if op != self.DIFF_INSERT: # Equality or deletion. | |||
chars1 += len(text) | |||
if op != self.DIFF_DELETE: # Equality or insertion. | |||
chars2 += len(text) | |||
if chars1 > loc: # Overshot the location. | |||
break | |||
last_chars1 = chars1 | |||
last_chars2 = chars2 | |||
if len(diffs) != x and diffs[x][0] == self.DIFF_DELETE: | |||
# The location was deleted. | |||
return last_chars2 | |||
# Add the remaining len(character). | |||
return last_chars2 + (loc - last_chars1) | |||
def diff_prettyHtml(self, diffs): | |||
"""Convert a diff array into a pretty HTML report. | |||
Args: | |||
diffs: Array of diff tuples. | |||
Returns: | |||
HTML representation. | |||
""" | |||
html = [] | |||
for (op, data) in diffs: | |||
text = (data.replace("&", "&").replace("<", "<") | |||
.replace(">", ">").replace("\n", "¶<br>")) | |||
if op == self.DIFF_INSERT: | |||
html.append("<ins style=\"background:#e6ffe6;\">%s</ins>" % text) | |||
elif op == self.DIFF_DELETE: | |||
html.append("<del style=\"background:#ffe6e6;\">%s</del>" % text) | |||
elif op == self.DIFF_EQUAL: | |||
html.append("<span>%s</span>" % text) | |||
return "".join(html) | |||
def diff_text1(self, diffs): | |||
"""Compute and return the source text (all equalities and deletions). | |||
Args: | |||
diffs: Array of diff tuples. | |||
Returns: | |||
Source text. | |||
""" | |||
text = [] | |||
for (op, data) in diffs: | |||
if op != self.DIFF_INSERT: | |||
text.append(data) | |||
return "".join(text) | |||
def diff_text2(self, diffs): | |||
"""Compute and return the destination text (all equalities and insertions). | |||
Args: | |||
diffs: Array of diff tuples. | |||
Returns: | |||
Destination text. | |||
""" | |||
text = [] | |||
for (op, data) in diffs: | |||
if op != self.DIFF_DELETE: | |||
text.append(data) | |||
return "".join(text) | |||
def diff_levenshtein(self, diffs): | |||
"""Compute the Levenshtein distance; the number of inserted, deleted or | |||
substituted characters. | |||
Args: | |||
diffs: Array of diff tuples. | |||
Returns: | |||
Number of changes. | |||
""" | |||
levenshtein = 0 | |||
insertions = 0 | |||
deletions = 0 | |||
for (op, data) in diffs: | |||
if op == self.DIFF_INSERT: | |||
insertions += len(data) | |||
elif op == self.DIFF_DELETE: | |||
deletions += len(data) | |||
elif op == self.DIFF_EQUAL: | |||
# A deletion and an insertion is one substitution. | |||
levenshtein += max(insertions, deletions) | |||
insertions = 0 | |||
deletions = 0 | |||
levenshtein += max(insertions, deletions) | |||
return levenshtein | |||
def diff_toDelta(self, diffs): | |||
"""Crush the diff into an encoded string which describes the operations | |||
required to transform text1 into text2. | |||
E.g. =3\t-2\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'. | |||
Operations are tab-separated. Inserted text is escaped using %xx notation. | |||
Args: | |||
diffs: Array of diff tuples. | |||
Returns: | |||
Delta text. | |||
""" | |||
text = [] | |||
for (op, data) in diffs: | |||
if op == self.DIFF_INSERT: | |||
# High ascii will raise UnicodeDecodeError. Use Unicode instead. | |||
data = data.encode("utf-8") | |||
text.append("+" + urllib.quote(data, "!~*'();/?:@&=+$,# ")) | |||
elif op == self.DIFF_DELETE: | |||
text.append("-%d" % len(data)) | |||
elif op == self.DIFF_EQUAL: | |||
text.append("=%d" % len(data)) | |||
return "\t".join(text) | |||
def diff_fromDelta(self, text1, delta): | |||
"""Given the original text1, and an encoded string which describes the | |||
operations required to transform text1 into text2, compute the full diff. | |||
Args: | |||
text1: Source string for the diff. | |||
delta: Delta text. | |||
Returns: | |||
Array of diff tuples. | |||
Raises: | |||
ValueError: If invalid input. | |||
""" | |||
if type(delta) == unicode: | |||
# Deltas should be composed of a subset of ascii chars, Unicode not | |||
# required. If this encode raises UnicodeEncodeError, delta is invalid. | |||
delta = delta.encode("ascii") | |||
diffs = [] | |||
pointer = 0 # Cursor in text1 | |||
tokens = delta.split("\t") | |||
for token in tokens: | |||
if token == "": | |||
# Blank tokens are ok (from a trailing \t). | |||
continue | |||
# Each token begins with a one character parameter which specifies the | |||
# operation of this token (delete, insert, equality). | |||
param = token[1:] | |||
if token[0] == "+": | |||
param = urllib.unquote(param).decode("utf-8") | |||
diffs.append((self.DIFF_INSERT, param)) | |||
elif token[0] == "-" or token[0] == "=": | |||
try: | |||
n = int(param) | |||
except ValueError: | |||
raise ValueError("Invalid number in diff_fromDelta: " + param) | |||
if n < 0: | |||
raise ValueError("Negative number in diff_fromDelta: " + param) | |||
text = text1[pointer : pointer + n] | |||
pointer += n | |||
if token[0] == "=": | |||
diffs.append((self.DIFF_EQUAL, text)) | |||
else: | |||
diffs.append((self.DIFF_DELETE, text)) | |||
else: | |||
# Anything else is an error. | |||
raise ValueError("Invalid diff operation in diff_fromDelta: " + | |||
token[0]) | |||
if pointer != len(text1): | |||
raise ValueError( | |||
"Delta length (%d) does not equal source text length (%d)." % | |||
(pointer, len(text1))) | |||
return diffs | |||
# MATCH FUNCTIONS | |||
def match_main(self, text, pattern, loc): | |||
"""Locate the best instance of 'pattern' in 'text' near 'loc'. | |||
Args: | |||
text: The text to search. | |||
pattern: The pattern to search for. | |||
loc: The location to search around. | |||
Returns: | |||
Best match index or -1. | |||
""" | |||
# Check for null inputs. | |||
if text == None or pattern == None: | |||
raise ValueError("Null inputs. (match_main)") | |||
loc = max(0, min(loc, len(text))) | |||
if text == pattern: | |||
# Shortcut (potentially not guaranteed by the algorithm) | |||
return 0 | |||
elif not text: | |||
# Nothing to match. | |||
return -1 | |||
elif text[loc:loc + len(pattern)] == pattern: | |||
# Perfect match at the perfect spot! (Includes case of null pattern) | |||
return loc | |||
else: | |||
# Do a fuzzy compare. | |||
match = self.match_bitap(text, pattern, loc) | |||
return match | |||
def match_bitap(self, text, pattern, loc): | |||
"""Locate the best instance of 'pattern' in 'text' near 'loc' using the | |||
Bitap algorithm. | |||
Args: | |||
text: The text to search. | |||
pattern: The pattern to search for. | |||
loc: The location to search around. | |||
Returns: | |||
Best match index or -1. | |||
""" | |||
# Python doesn't have a maxint limit, so ignore this check. | |||
#if self.Match_MaxBits != 0 and len(pattern) > self.Match_MaxBits: | |||
# raise ValueError("Pattern too long for this application.") | |||
# Initialise the alphabet. | |||
s = self.match_alphabet(pattern) | |||
def match_bitapScore(e, x): | |||
"""Compute and return the score for a match with e errors and x location. | |||
Accesses loc and pattern through being a closure. | |||
Args: | |||
e: Number of errors in match. | |||
x: Location of match. | |||
Returns: | |||
Overall score for match (0.0 = good, 1.0 = bad). | |||
""" | |||
accuracy = float(e) / len(pattern) | |||
proximity = abs(loc - x) | |||
if not self.Match_Distance: | |||
# Dodge divide by zero error. | |||
return proximity and 1.0 or accuracy | |||
return accuracy + (proximity / float(self.Match_Distance)) | |||
# Highest score beyond which we give up. | |||
score_threshold = self.Match_Threshold | |||
# Is there a nearby exact match? (speedup) | |||
best_loc = text.find(pattern, loc) | |||
if best_loc != -1: | |||
score_threshold = min(match_bitapScore(0, best_loc), score_threshold) | |||
# What about in the other direction? (speedup) | |||
best_loc = text.rfind(pattern, loc + len(pattern)) | |||
if best_loc != -1: | |||
score_threshold = min(match_bitapScore(0, best_loc), score_threshold) | |||
# Initialise the bit arrays. | |||
matchmask = 1 << (len(pattern) - 1) | |||
best_loc = -1 | |||
bin_max = len(pattern) + len(text) | |||
# Empty initialization added to appease pychecker. | |||
last_rd = None | |||
for d in xrange(len(pattern)): | |||
# Scan for the best match each iteration allows for one more error. | |||
# Run a binary search to determine how far from 'loc' we can stray at | |||
# this error level. | |||
bin_min = 0 | |||
bin_mid = bin_max | |||
while bin_min < bin_mid: | |||
if match_bitapScore(d, loc + bin_mid) <= score_threshold: | |||
bin_min = bin_mid | |||
else: | |||
bin_max = bin_mid | |||
bin_mid = (bin_max - bin_min) // 2 + bin_min | |||
# Use the result from this iteration as the maximum for the next. | |||
bin_max = bin_mid | |||
start = max(1, loc - bin_mid + 1) | |||
finish = min(loc + bin_mid, len(text)) + len(pattern) | |||
rd = [0] * (finish + 2) | |||
rd[finish + 1] = (1 << d) - 1 | |||
for j in xrange(finish, start - 1, -1): | |||
if len(text) <= j - 1: | |||
# Out of range. | |||
charMatch = 0 | |||
else: | |||
charMatch = s.get(text[j - 1], 0) | |||
if d == 0: # First pass: exact match. | |||
rd[j] = ((rd[j + 1] << 1) | 1) & charMatch | |||
else: # Subsequent passes: fuzzy match. | |||
rd[j] = (((rd[j + 1] << 1) | 1) & charMatch) | ( | |||
((last_rd[j + 1] | last_rd[j]) << 1) | 1) | last_rd[j + 1] | |||
if rd[j] & matchmask: | |||
score = match_bitapScore(d, j - 1) | |||
# This match will almost certainly be better than any existing match. | |||
# But check anyway. | |||
if score <= score_threshold: | |||
# Told you so. | |||
score_threshold = score | |||
best_loc = j - 1 | |||
if best_loc > loc: | |||
# When passing loc, don't exceed our current distance from loc. | |||
start = max(1, 2 * loc - best_loc) | |||
else: | |||
# Already passed loc, downhill from here on in. | |||
break | |||
# No hope for a (better) match at greater error levels. | |||
if match_bitapScore(d + 1, loc) > score_threshold: | |||
break | |||
last_rd = rd | |||
return best_loc | |||
def match_alphabet(self, pattern): | |||
"""Initialise the alphabet for the Bitap algorithm. | |||
Args: | |||
pattern: The text to encode. | |||
Returns: | |||
Hash of character locations. | |||
""" | |||
s = {} | |||
for char in pattern: | |||
s[char] = 0 | |||
for i in xrange(len(pattern)): | |||
s[pattern[i]] |= 1 << (len(pattern) - i - 1) | |||
return s | |||
# PATCH FUNCTIONS | |||
def patch_addContext(self, patch, text): | |||
"""Increase the context until it is unique, | |||
but don't let the pattern expand beyond Match_MaxBits. | |||
Args: | |||
patch: The patch to grow. | |||
text: Source text. | |||
""" | |||
if len(text) == 0: | |||
return | |||
pattern = text[patch.start2 : patch.start2 + patch.length1] | |||
padding = 0 | |||
# Look for the first and last matches of pattern in text. If two different | |||
# matches are found, increase the pattern length. | |||
while (text.find(pattern) != text.rfind(pattern) and (self.Match_MaxBits == | |||
0 or len(pattern) < self.Match_MaxBits - self.Patch_Margin - | |||
self.Patch_Margin)): | |||
padding += self.Patch_Margin | |||
pattern = text[max(0, patch.start2 - padding) : | |||
patch.start2 + patch.length1 + padding] | |||
# Add one chunk for good luck. | |||
padding += self.Patch_Margin | |||
# Add the prefix. | |||
prefix = text[max(0, patch.start2 - padding) : patch.start2] | |||
if prefix: | |||
patch.diffs[:0] = [(self.DIFF_EQUAL, prefix)] | |||
# Add the suffix. | |||
suffix = text[patch.start2 + patch.length1 : | |||
patch.start2 + patch.length1 + padding] | |||
if suffix: | |||
patch.diffs.append((self.DIFF_EQUAL, suffix)) | |||
# Roll back the start points. | |||
patch.start1 -= len(prefix) | |||
patch.start2 -= len(prefix) | |||
# Extend lengths. | |||
patch.length1 += len(prefix) + len(suffix) | |||
patch.length2 += len(prefix) + len(suffix) | |||
def patch_make(self, a, b=None, c=None): | |||
"""Compute a list of patches to turn text1 into text2. | |||
Use diffs if provided, otherwise compute it ourselves. | |||
There are four ways to call this function, depending on what data is | |||
available to the caller: | |||
Method 1: | |||
a = text1, b = text2 | |||
Method 2: | |||
a = diffs | |||
Method 3 (optimal): | |||
a = text1, b = diffs | |||
Method 4 (deprecated, use method 3): | |||
a = text1, b = text2, c = diffs | |||
Args: | |||
a: text1 (methods 1,3,4) or Array of diff tuples for text1 to | |||
text2 (method 2). | |||
b: text2 (methods 1,4) or Array of diff tuples for text1 to | |||
text2 (method 3) or undefined (method 2). | |||
c: Array of diff tuples for text1 to text2 (method 4) or | |||
undefined (methods 1,2,3). | |||
Returns: | |||
Array of Patch objects. | |||
""" | |||
text1 = None | |||
diffs = None | |||
# Note that texts may arrive as 'str' or 'unicode'. | |||
if isinstance(a, basestring) and isinstance(b, basestring) and c is None: | |||
# Method 1: text1, text2 | |||
# Compute diffs from text1 and text2. | |||
text1 = a | |||
diffs = self.diff_main(text1, b, True) | |||
if len(diffs) > 2: | |||
self.diff_cleanupSemantic(diffs) | |||
self.diff_cleanupEfficiency(diffs) | |||
elif isinstance(a, list) and b is None and c is None: | |||
# Method 2: diffs | |||
# Compute text1 from diffs. | |||
diffs = a | |||
text1 = self.diff_text1(diffs) | |||
elif isinstance(a, basestring) and isinstance(b, list) and c is None: | |||
# Method 3: text1, diffs | |||
text1 = a | |||
diffs = b | |||
elif (isinstance(a, basestring) and isinstance(b, basestring) and | |||
isinstance(c, list)): | |||
# Method 4: text1, text2, diffs | |||
# text2 is not used. | |||
text1 = a | |||
diffs = c | |||
else: | |||
raise ValueError("Unknown call format to patch_make.") | |||
if not diffs: | |||
return [] # Get rid of the None case. | |||
patches = [] | |||
patch = patch_obj() | |||
char_count1 = 0 # Number of characters into the text1 string. | |||
char_count2 = 0 # Number of characters into the text2 string. | |||
prepatch_text = text1 # Recreate the patches to determine context info. | |||
postpatch_text = text1 | |||
for x in xrange(len(diffs)): | |||
(diff_type, diff_text) = diffs[x] | |||
if len(patch.diffs) == 0 and diff_type != self.DIFF_EQUAL: | |||
# A new patch starts here. | |||
patch.start1 = char_count1 | |||
patch.start2 = char_count2 | |||
if diff_type == self.DIFF_INSERT: | |||
# Insertion | |||
patch.diffs.append(diffs[x]) | |||
patch.length2 += len(diff_text) | |||
postpatch_text = (postpatch_text[:char_count2] + diff_text + | |||
postpatch_text[char_count2:]) | |||
elif diff_type == self.DIFF_DELETE: | |||
# Deletion. | |||
patch.length1 += len(diff_text) | |||
patch.diffs.append(diffs[x]) | |||
postpatch_text = (postpatch_text[:char_count2] + | |||
postpatch_text[char_count2 + len(diff_text):]) | |||
elif (diff_type == self.DIFF_EQUAL and | |||
len(diff_text) <= 2 * self.Patch_Margin and | |||
len(patch.diffs) != 0 and len(diffs) != x + 1): | |||
# Small equality inside a patch. | |||
patch.diffs.append(diffs[x]) | |||
patch.length1 += len(diff_text) | |||
patch.length2 += len(diff_text) | |||
if (diff_type == self.DIFF_EQUAL and | |||
len(diff_text) >= 2 * self.Patch_Margin): | |||
# Time for a new patch. | |||
if len(patch.diffs) != 0: | |||
self.patch_addContext(patch, prepatch_text) | |||
patches.append(patch) | |||
patch = patch_obj() | |||
# Unlike Unidiff, our patch lists have a rolling context. | |||
# http://code.google.com/p/google-diff-match-patch/wiki/Unidiff | |||
# Update prepatch text & pos to reflect the application of the | |||
# just completed patch. | |||
prepatch_text = postpatch_text | |||
char_count1 = char_count2 | |||
# Update the current character count. | |||
if diff_type != self.DIFF_INSERT: | |||
char_count1 += len(diff_text) | |||
if diff_type != self.DIFF_DELETE: | |||
char_count2 += len(diff_text) | |||
# Pick up the leftover patch if not empty. | |||
if len(patch.diffs) != 0: | |||
self.patch_addContext(patch, prepatch_text) | |||
patches.append(patch) | |||
return patches | |||
def patch_deepCopy(self, patches): | |||
"""Given an array of patches, return another array that is identical. | |||
Args: | |||
patches: Array of Patch objects. | |||
Returns: | |||
Array of Patch objects. | |||
""" | |||
patchesCopy = [] | |||
for patch in patches: | |||
patchCopy = patch_obj() | |||
# No need to deep copy the tuples since they are immutable. | |||
patchCopy.diffs = patch.diffs[:] | |||
patchCopy.start1 = patch.start1 | |||
patchCopy.start2 = patch.start2 | |||
patchCopy.length1 = patch.length1 | |||
patchCopy.length2 = patch.length2 | |||
patchesCopy.append(patchCopy) | |||
return patchesCopy | |||
def patch_apply(self, patches, text): | |||
"""Merge a set of patches onto the text. Return a patched text, as well | |||
as a list of true/false values indicating which patches were applied. | |||
Args: | |||
patches: Array of Patch objects. | |||
text: Old text. | |||
Returns: | |||
Two element Array, containing the new text and an array of boolean values. | |||
""" | |||
if not patches: | |||
return (text, []) | |||
# Deep copy the patches so that no changes are made to originals. | |||
patches = self.patch_deepCopy(patches) | |||
nullPadding = self.patch_addPadding(patches) | |||
text = nullPadding + text + nullPadding | |||
self.patch_splitMax(patches) | |||
# delta keeps track of the offset between the expected and actual location | |||
# of the previous patch. If there are patches expected at positions 10 and | |||
# 20, but the first patch was found at 12, delta is 2 and the second patch | |||
# has an effective expected position of 22. | |||
delta = 0 | |||
results = [] | |||
for patch in patches: | |||
expected_loc = patch.start2 + delta | |||
text1 = self.diff_text1(patch.diffs) | |||
end_loc = -1 | |||
if len(text1) > self.Match_MaxBits: | |||
# patch_splitMax will only provide an oversized pattern in the case of | |||
# a monster delete. | |||
start_loc = self.match_main(text, text1[:self.Match_MaxBits], | |||
expected_loc) | |||
if start_loc != -1: | |||
end_loc = self.match_main(text, text1[-self.Match_MaxBits:], | |||
expected_loc + len(text1) - self.Match_MaxBits) | |||
if end_loc == -1 or start_loc >= end_loc: | |||
# Can't find valid trailing context. Drop this patch. | |||
start_loc = -1 | |||
else: | |||
start_loc = self.match_main(text, text1, expected_loc) | |||
if start_loc == -1: | |||
# No match found. :( | |||
results.append(False) | |||
# Subtract the delta for this failed patch from subsequent patches. | |||
delta -= patch.length2 - patch.length1 | |||
else: | |||
# Found a match. :) | |||
results.append(True) | |||
delta = start_loc - expected_loc | |||
if end_loc == -1: | |||
text2 = text[start_loc : start_loc + len(text1)] | |||
else: | |||
text2 = text[start_loc : end_loc + self.Match_MaxBits] | |||
if text1 == text2: | |||
# Perfect match, just shove the replacement text in. | |||
text = (text[:start_loc] + self.diff_text2(patch.diffs) + | |||
text[start_loc + len(text1):]) | |||
else: | |||
# Imperfect match. | |||
# Run a diff to get a framework of equivalent indices. | |||
diffs = self.diff_main(text1, text2, False) | |||
if (len(text1) > self.Match_MaxBits and | |||
self.diff_levenshtein(diffs) / float(len(text1)) > | |||
self.Patch_DeleteThreshold): | |||
# The end points match, but the content is unacceptably bad. | |||
results[-1] = False | |||
else: | |||
self.diff_cleanupSemanticLossless(diffs) | |||
index1 = 0 | |||
for (op, data) in patch.diffs: | |||
if op != self.DIFF_EQUAL: | |||
index2 = self.diff_xIndex(diffs, index1) | |||
if op == self.DIFF_INSERT: # Insertion | |||
text = text[:start_loc + index2] + data + text[start_loc + | |||
index2:] | |||
elif op == self.DIFF_DELETE: # Deletion | |||
text = text[:start_loc + index2] + text[start_loc + | |||
self.diff_xIndex(diffs, index1 + len(data)):] | |||
if op != self.DIFF_DELETE: | |||
index1 += len(data) | |||
# Strip the padding off. | |||
text = text[len(nullPadding):-len(nullPadding)] | |||
return (text, results) | |||
def patch_addPadding(self, patches): | |||
"""Add some padding on text start and end so that edges can match | |||
something. Intended to be called only from within patch_apply. | |||
Args: | |||
patches: Array of Patch objects. | |||
Returns: | |||
The padding string added to each side. | |||
""" | |||
paddingLength = self.Patch_Margin | |||
nullPadding = "" | |||
for x in xrange(1, paddingLength + 1): | |||
nullPadding += chr(x) | |||
# Bump all the patches forward. | |||
for patch in patches: | |||
patch.start1 += paddingLength | |||
patch.start2 += paddingLength | |||
# Add some padding on start of first diff. | |||
patch = patches[0] | |||
diffs = patch.diffs | |||
if not diffs or diffs[0][0] != self.DIFF_EQUAL: | |||
# Add nullPadding equality. | |||
diffs.insert(0, (self.DIFF_EQUAL, nullPadding)) | |||
patch.start1 -= paddingLength # Should be 0. | |||
patch.start2 -= paddingLength # Should be 0. | |||
patch.length1 += paddingLength | |||
patch.length2 += paddingLength | |||
elif paddingLength > len(diffs[0][1]): | |||
# Grow first equality. | |||
extraLength = paddingLength - len(diffs[0][1]) | |||
newText = nullPadding[len(diffs[0][1]):] + diffs[0][1] | |||
diffs[0] = (diffs[0][0], newText) | |||
patch.start1 -= extraLength | |||
patch.start2 -= extraLength | |||
patch.length1 += extraLength | |||
patch.length2 += extraLength | |||
# Add some padding on end of last diff. | |||
patch = patches[-1] | |||
diffs = patch.diffs | |||
if not diffs or diffs[-1][0] != self.DIFF_EQUAL: | |||
# Add nullPadding equality. | |||
diffs.append((self.DIFF_EQUAL, nullPadding)) | |||
patch.length1 += paddingLength | |||
patch.length2 += paddingLength | |||
elif paddingLength > len(diffs[-1][1]): | |||
# Grow last equality. | |||
extraLength = paddingLength - len(diffs[-1][1]) | |||
newText = diffs[-1][1] + nullPadding[:extraLength] | |||
diffs[-1] = (diffs[-1][0], newText) | |||
patch.length1 += extraLength | |||
patch.length2 += extraLength | |||
return nullPadding | |||
def patch_splitMax(self, patches): | |||
"""Look through the patches and break up any which are longer than the | |||
maximum limit of the match algorithm. | |||
Intended to be called only from within patch_apply. | |||
Args: | |||
patches: Array of Patch objects. | |||
""" | |||
patch_size = self.Match_MaxBits | |||
if patch_size == 0: | |||
# Python has the option of not splitting strings due to its ability | |||
# to handle integers of arbitrary precision. | |||
return | |||
for x in xrange(len(patches)): | |||
if patches[x].length1 <= patch_size: | |||
continue | |||
bigpatch = patches[x] | |||
# Remove the big old patch. | |||
del patches[x] | |||
x -= 1 | |||
start1 = bigpatch.start1 | |||
start2 = bigpatch.start2 | |||
precontext = '' | |||
while len(bigpatch.diffs) != 0: | |||
# Create one of several smaller patches. | |||
patch = patch_obj() | |||
empty = True | |||
patch.start1 = start1 - len(precontext) | |||
patch.start2 = start2 - len(precontext) | |||
if precontext: | |||
patch.length1 = patch.length2 = len(precontext) | |||
patch.diffs.append((self.DIFF_EQUAL, precontext)) | |||
while (len(bigpatch.diffs) != 0 and | |||
patch.length1 < patch_size - self.Patch_Margin): | |||
(diff_type, diff_text) = bigpatch.diffs[0] | |||
if diff_type == self.DIFF_INSERT: | |||
# Insertions are harmless. | |||
patch.length2 += len(diff_text) | |||
start2 += len(diff_text) | |||
patch.diffs.append(bigpatch.diffs.pop(0)) | |||
empty = False | |||
elif (diff_type == self.DIFF_DELETE and len(patch.diffs) == 1 and | |||
patch.diffs[0][0] == self.DIFF_EQUAL and | |||
len(diff_text) > 2 * patch_size): | |||
# This is a large deletion. Let it pass in one chunk. | |||
patch.length1 += len(diff_text) | |||
start1 += len(diff_text) | |||
empty = False | |||
patch.diffs.append((diff_type, diff_text)) | |||
del bigpatch.diffs[0] | |||
else: | |||
# Deletion or equality. Only take as much as we can stomach. | |||
diff_text = diff_text[:patch_size - patch.length1 - | |||
self.Patch_Margin] | |||
patch.length1 += len(diff_text) | |||
start1 += len(diff_text) | |||
if diff_type == self.DIFF_EQUAL: | |||
patch.length2 += len(diff_text) | |||
start2 += len(diff_text) | |||
else: | |||
empty = False | |||
patch.diffs.append((diff_type, diff_text)) | |||
if diff_text == bigpatch.diffs[0][1]: | |||
del bigpatch.diffs[0] | |||
else: | |||
bigpatch.diffs[0] = (bigpatch.diffs[0][0], | |||
bigpatch.diffs[0][1][len(diff_text):]) | |||
# Compute the head context for the next patch. | |||
precontext = self.diff_text2(patch.diffs) | |||
precontext = precontext[-self.Patch_Margin:] | |||
# Append the end context for this patch. | |||
postcontext = self.diff_text1(bigpatch.diffs)[:self.Patch_Margin] | |||
if postcontext: | |||
patch.length1 += len(postcontext) | |||
patch.length2 += len(postcontext) | |||
if len(patch.diffs) != 0 and patch.diffs[-1][0] == self.DIFF_EQUAL: | |||
patch.diffs[-1] = (self.DIFF_EQUAL, patch.diffs[-1][1] + | |||
postcontext) | |||
else: | |||
patch.diffs.append((self.DIFF_EQUAL, postcontext)) | |||
if not empty: | |||
x += 1 | |||
patches.insert(x, patch) | |||
def patch_toText(self, patches): | |||
"""Take a list of patches and return a textual representation. | |||
Args: | |||
patches: Array of Patch objects. | |||
Returns: | |||
Text representation of patches. | |||
""" | |||
text = [] | |||
for patch in patches: | |||
text.append(str(patch)) | |||
return "".join(text) | |||
def patch_fromText(self, textline): | |||
"""Parse a textual representation of patches and return a list of patch | |||
objects. | |||
Args: | |||
textline: Text representation of patches. | |||
Returns: | |||
Array of Patch objects. | |||
Raises: | |||
ValueError: If invalid input. | |||
""" | |||
if type(textline) == unicode: | |||
# Patches should be composed of a subset of ascii chars, Unicode not | |||
# required. If this encode raises UnicodeEncodeError, patch is invalid. | |||
textline = textline.encode("ascii") | |||
patches = [] | |||
if not textline: | |||
return patches | |||
text = textline.split('\n') | |||
while len(text) != 0: | |||
m = re.match("^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$", text[0]) | |||
if not m: | |||
raise ValueError("Invalid patch string: " + text[0]) | |||
patch = patch_obj() | |||
patches.append(patch) | |||
patch.start1 = int(m.group(1)) | |||
if m.group(2) == '': | |||
patch.start1 -= 1 | |||
patch.length1 = 1 | |||
elif m.group(2) == '0': | |||
patch.length1 = 0 | |||
else: | |||
patch.start1 -= 1 | |||
patch.length1 = int(m.group(2)) | |||
patch.start2 = int(m.group(3)) | |||
if m.group(4) == '': | |||
patch.start2 -= 1 | |||
patch.length2 = 1 | |||
elif m.group(4) == '0': | |||
patch.length2 = 0 | |||
else: | |||
patch.start2 -= 1 | |||
patch.length2 = int(m.group(4)) | |||
del text[0] | |||
while len(text) != 0: | |||
if text[0]: | |||
sign = text[0][0] | |||
else: | |||
sign = '' | |||
line = urllib.unquote(text[0][1:]) | |||
line = line.decode("utf-8") | |||
if sign == '+': | |||
# Insertion. | |||
patch.diffs.append((self.DIFF_INSERT, line)) | |||
elif sign == '-': | |||
# Deletion. | |||
patch.diffs.append((self.DIFF_DELETE, line)) | |||
elif sign == ' ': | |||
# Minor equality. | |||
patch.diffs.append((self.DIFF_EQUAL, line)) | |||
elif sign == '@': | |||
# Start of next patch. | |||
break | |||
elif sign == '': | |||
# Blank line? Whatever. | |||
pass | |||
else: | |||
# WTF? | |||
raise ValueError("Invalid patch mode: '%s'\n%s" % (sign, line)) | |||
del text[0] | |||
return patches | |||
class patch_obj: | |||
"""Class representing one patch operation. | |||
""" | |||
def __init__(self): | |||
"""Initializes with an empty list of diffs. | |||
""" | |||
self.diffs = [] | |||
self.start1 = None | |||
self.start2 = None | |||
self.length1 = 0 | |||
self.length2 = 0 | |||
def __str__(self): | |||
"""Emmulate GNU diff's format. | |||
Header: @@ -382,8 +481,9 @@ | |||
Indicies are printed as 1-based, not 0-based. | |||
Returns: | |||
The GNU diff string. | |||
""" | |||
if self.length1 == 0: | |||
coords1 = str(self.start1) + ",0" | |||
elif self.length1 == 1: | |||
coords1 = str(self.start1 + 1) | |||
else: | |||
coords1 = str(self.start1 + 1) + "," + str(self.length1) | |||
if self.length2 == 0: | |||
coords2 = str(self.start2) + ",0" | |||
elif self.length2 == 1: | |||
coords2 = str(self.start2 + 1) | |||
else: | |||
coords2 = str(self.start2 + 1) + "," + str(self.length2) | |||
text = ["@@ -", coords1, " +", coords2, " @@\n"] | |||
# Escape the body of the patch with %xx notation. | |||
for (op, data) in self.diffs: | |||
if op == diff_match_patch.DIFF_INSERT: | |||
text.append("+") | |||
elif op == diff_match_patch.DIFF_DELETE: | |||
text.append("-") | |||
elif op == diff_match_patch.DIFF_EQUAL: | |||
text.append(" ") | |||
# High ascii will raise UnicodeDecodeError. Use Unicode instead. | |||
data = data.encode("utf-8") | |||
text.append(urllib.quote(data, "!~*'();/?:@&=+$,# ") + "\n") | |||
return "".join(text) |