/** * dmp.go * * Go language implementation of Google Diff, Match, and Patch library * * Original library is Copyright (c) 2006 Google Inc. * http://code.google.com/p/google-diff-match-patch/ * * Copyright (c) 2012 Sergi Mansilla * https://github.com/sergi/go-diff * * See included LICENSE file for license details. */ // Package diffmatchpatch offers robust algorithms to perform the // operations required for synchronizing plain text. package diffmatchpatch import ( "bytes" "errors" "fmt" "html" "math" "net/url" "regexp" "strconv" "strings" "time" "unicode/utf8" ) // The data structure representing a diff is an array of tuples: // [[DiffDelete, 'Hello'], [DiffInsert, 'Goodbye'], [DiffEqual, ' world.']] // which means: delete 'Hello', add 'Goodbye' and keep ' world.' type Operation int8 const ( DiffDelete Operation = -1 DiffInsert Operation = 1 DiffEqual Operation = 0 ) // unescaper unescapes selected chars for compatibility with JavaScript's encodeURI. // In speed critical applications this could be dropped since the // receiving application will certainly decode these fine. // Note that this function is case-sensitive. Thus "%3F" would not be // unescaped. But this is ok because it is only called with the output of // HttpUtility.UrlEncode which returns lowercase hex. // // Example: "%3f" -> "?", "%24" -> "$", etc. var unescaper = strings.NewReplacer( "%21", "!", "%7E", "~", "%27", "'", "%28", "(", "%29", ")", "%3B", ";", "%2F", "/", "%3F", "?", "%3A", ":", "%40", "@", "%26", "&", "%3D", "=", "%2B", "+", "%24", "$", "%2C", ",", "%23", "#", "%2A", "*") // Define some regex patterns for matching boundaries. var ( nonAlphaNumericRegex_ = regexp.MustCompile(`[^a-zA-Z0-9]`) whitespaceRegex_ = regexp.MustCompile(`\s`) linebreakRegex_ = regexp.MustCompile(`[\r\n]`) blanklineEndRegex_ = regexp.MustCompile(`\n\r?\n$`) blanklineStartRegex_ = regexp.MustCompile(`^\r?\n\r?\n`) ) func splice(slice []Diff, index int, amount int, elements ...Diff) []Diff { return append(slice[:index], append(elements, slice[index+amount:]...)...) } // indexOf returns the first index of pattern in str, starting at str[i]. func indexOf(str string, pattern string, i int) int { if i > len(str)-1 { return -1 } if i <= 0 { return strings.Index(str, pattern) } ind := strings.Index(str[i:], pattern) if ind == -1 { return -1 } return ind + i } // lastIndexOf returns the last index of pattern in str, starting at str[i]. func lastIndexOf(str string, pattern string, i int) int { if i < 0 { return -1 } if i >= len(str) { return strings.LastIndex(str, pattern) } _, size := utf8.DecodeRuneInString(str[i:]) return strings.LastIndex(str[:i+size], pattern) } // Return the index of pattern in target, starting at target[i]. func runesIndexOf(target, pattern []rune, i int) int { if i > len(target)-1 { return -1 } if i <= 0 { return runesIndex(target, pattern) } ind := runesIndex(target[i:], pattern) if ind == -1 { return -1 } return ind + i } func min(x, y int) int { if x < y { return x } return y } func max(x, y int) int { if x > y { return x } return y } func runesEqual(r1, r2 []rune) bool { if len(r1) != len(r2) { return false } for i, c := range r1 { if c != r2[i] { return false } } return true } // The equivalent of strings.Index for rune slices. func runesIndex(r1, r2 []rune) int { last := len(r1) - len(r2) for i := 0; i <= last; i++ { if runesEqual(r1[i:i+len(r2)], r2) { return i } } return -1 } // Diff represents one diff operation type Diff struct { Type Operation Text string } // Patch represents one patch operation. type Patch struct { diffs []Diff start1 int start2 int length1 int length2 int } // String emulates GNU diff's format. // Header: @@ -382,8 +481,9 @@ // Indicies are printed as 1-based, not 0-based. func (p *Patch) String() string { var coords1, coords2 string if p.length1 == 0 { coords1 = strconv.Itoa(p.start1) + ",0" } else if p.length1 == 1 { coords1 = strconv.Itoa(p.start1 + 1) } else { coords1 = strconv.Itoa(p.start1+1) + "," + strconv.Itoa(p.length1) } if p.length2 == 0 { coords2 = strconv.Itoa(p.start2) + ",0" } else if p.length2 == 1 { coords2 = strconv.Itoa(p.start2 + 1) } else { coords2 = strconv.Itoa(p.start2+1) + "," + strconv.Itoa(p.length2) } var text bytes.Buffer text.WriteString("@@ -" + coords1 + " +" + coords2 + " @@\n") // Escape the body of the patch with %xx notation. for _, aDiff := range p.diffs { switch aDiff.Type { case DiffInsert: text.WriteString("+") case DiffDelete: text.WriteString("-") case DiffEqual: text.WriteString(" ") } text.WriteString(strings.Replace(url.QueryEscape(aDiff.Text), "+", " ", -1)) text.WriteString("\n") } return unescaper.Replace(text.String()) } type DiffMatchPatch struct { // Number of seconds to map a diff before giving up (0 for infinity). DiffTimeout time.Duration // Cost of an empty edit operation in terms of edit characters. DiffEditCost int // 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). MatchDistance int // 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. PatchDeleteThreshold float64 // Chunk size for context length. PatchMargin int // The number of bits in an int. MatchMaxBits int // At what point is no match declared (0.0 = perfection, 1.0 = very loose). MatchThreshold float64 } // New creates a new DiffMatchPatch object with default parameters. func New() *DiffMatchPatch { // Defaults. return &DiffMatchPatch{ DiffTimeout: time.Second, DiffEditCost: 4, MatchThreshold: 0.5, MatchDistance: 1000, PatchDeleteThreshold: 0.5, PatchMargin: 4, MatchMaxBits: 32, } } // DiffMain finds the differences between two texts. func (dmp *DiffMatchPatch) DiffMain(text1, text2 string, checklines bool) []Diff { var deadline time.Time if dmp.DiffTimeout <= 0 { deadline = time.Now().Add(24 * 365 * time.Hour) } else { deadline = time.Now().Add(dmp.DiffTimeout) } return dmp.diffMain(text1, text2, checklines, deadline) } func (dmp *DiffMatchPatch) diffMain(text1, text2 string, checklines bool, deadline time.Time) []Diff { return dmp.diffMainRunes([]rune(text1), []rune(text2), checklines, deadline) } // DiffMainRunes finds the differences between two rune sequences. func (dmp *DiffMatchPatch) DiffMainRunes(text1, text2 []rune, checklines bool) []Diff { var deadline time.Time if dmp.DiffTimeout <= 0 { deadline = time.Now().Add(24 * 365 * time.Hour) } else { deadline = time.Now().Add(dmp.DiffTimeout) } return dmp.diffMainRunes(text1, text2, checklines, deadline) } func (dmp *DiffMatchPatch) diffMainRunes(text1, text2 []rune, checklines bool, deadline time.Time) []Diff { if runesEqual(text1, text2) { var diffs []Diff if len(text1) > 0 { diffs = append(diffs, Diff{DiffEqual, string(text1)}) } return diffs } // Trim off common prefix (speedup). commonlength := commonPrefixLength(text1, text2) commonprefix := text1[:commonlength] text1 = text1[commonlength:] text2 = text2[commonlength:] // Trim off common suffix (speedup). commonlength = commonSuffixLength(text1, text2) commonsuffix := text1[len(text1)-commonlength:] text1 = text1[:len(text1)-commonlength] text2 = text2[:len(text2)-commonlength] // Compute the diff on the middle block. diffs := dmp.diffCompute(text1, text2, checklines, deadline) // Restore the prefix and suffix. if len(commonprefix) != 0 { diffs = append([]Diff{Diff{DiffEqual, string(commonprefix)}}, diffs...) } if len(commonsuffix) != 0 { diffs = append(diffs, Diff{DiffEqual, string(commonsuffix)}) } return dmp.DiffCleanupMerge(diffs) } // diffCompute finds the differences between two rune slices. Assumes that the texts do not // have any common prefix or suffix. func (dmp *DiffMatchPatch) diffCompute(text1, text2 []rune, checklines bool, deadline time.Time) []Diff { diffs := []Diff{} if len(text1) == 0 { // Just add some text (speedup). return append(diffs, Diff{DiffInsert, string(text2)}) } else if len(text2) == 0 { // Just delete some text (speedup). return append(diffs, Diff{DiffDelete, string(text1)}) } var longtext, shorttext []rune if len(text1) > len(text2) { longtext = text1 shorttext = text2 } else { longtext = text2 shorttext = text1 } if i := runesIndex(longtext, shorttext); i != -1 { op := DiffInsert // Swap insertions for deletions if diff is reversed. if len(text1) > len(text2) { op = DiffDelete } // Shorter text is inside the longer text (speedup). return []Diff{ Diff{op, string(longtext[:i])}, Diff{DiffEqual, string(shorttext)}, Diff{op, string(longtext[i+len(shorttext):])}, } } else if len(shorttext) == 1 { // Single character string. // After the previous speedup, the character can't be an equality. return []Diff{ Diff{DiffDelete, string(text1)}, Diff{DiffInsert, string(text2)}, } // Check to see if the problem can be split in two. } else if hm := dmp.diffHalfMatch(text1, text2); hm != nil { // A half-match was found, sort out the return data. text1_a := hm[0] text1_b := hm[1] text2_a := hm[2] text2_b := hm[3] mid_common := hm[4] // Send both pairs off for separate processing. diffs_a := dmp.diffMainRunes(text1_a, text2_a, checklines, deadline) diffs_b := dmp.diffMainRunes(text1_b, text2_b, checklines, deadline) // Merge the results. return append(diffs_a, append([]Diff{Diff{DiffEqual, string(mid_common)}}, diffs_b...)...) } else if checklines && len(text1) > 100 && len(text2) > 100 { return dmp.diffLineMode(text1, text2, deadline) } return dmp.diffBisect(text1, text2, deadline) } // diffLineMode does a quick line-level diff on both []runes, then rediff the parts for // greater accuracy. This speedup can produce non-minimal diffs. func (dmp *DiffMatchPatch) diffLineMode(text1, text2 []rune, deadline time.Time) []Diff { // Scan the text on a line-by-line basis first. text1, text2, linearray := dmp.diffLinesToRunes(text1, text2) diffs := dmp.diffMainRunes(text1, text2, false, deadline) // Convert the diff back to original text. diffs = dmp.DiffCharsToLines(diffs, linearray) // Eliminate freak matches (e.g. blank lines) diffs = dmp.DiffCleanupSemantic(diffs) // Rediff any replacement blocks, this time character-by-character. // Add a dummy entry at the end. diffs = append(diffs, Diff{DiffEqual, ""}) pointer := 0 count_delete := 0 count_insert := 0 text_delete := "" text_insert := "" for pointer < len(diffs) { switch diffs[pointer].Type { case DiffInsert: count_insert++ text_insert += diffs[pointer].Text case DiffDelete: count_delete++ text_delete += diffs[pointer].Text case DiffEqual: // Upon reaching an equality, check for prior redundancies. if count_delete >= 1 && count_insert >= 1 { // Delete the offending records and add the merged ones. diffs = splice(diffs, pointer-count_delete-count_insert, count_delete+count_insert) pointer = pointer - count_delete - count_insert a := dmp.diffMain(text_delete, text_insert, false, deadline) for j := len(a) - 1; j >= 0; j-- { diffs = splice(diffs, pointer, 0, a[j]) } pointer = pointer + len(a) } count_insert = 0 count_delete = 0 text_delete = "" text_insert = "" } pointer++ } return diffs[:len(diffs)-1] // Remove the dummy entry at the end. } // DiffBisect finds 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. func (dmp *DiffMatchPatch) DiffBisect(text1, text2 string, deadline time.Time) []Diff { // Unused in this code, but retained for interface compatibility. return dmp.diffBisect([]rune(text1), []rune(text2), deadline) } // diffBisect finds the 'middle snake' of a diff, splits the problem in two // and returns the recursively constructed diff. // See Myers's 1986 paper: An O(ND) Difference Algorithm and Its Variations. func (dmp *DiffMatchPatch) diffBisect(runes1, runes2 []rune, deadline time.Time) []Diff { // Cache the text lengths to prevent multiple calls. runes1_len, runes2_len := len(runes1), len(runes2) max_d := (runes1_len + runes2_len + 1) / 2 v_offset := max_d v_length := 2 * max_d v1 := make([]int, v_length) v2 := make([]int, v_length) for i := range v1 { v1[i] = -1 v2[i] = -1 } v1[v_offset+1] = 0 v2[v_offset+1] = 0 delta := runes1_len - runes2_len // 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 := 0; d < max_d; d++ { // Bail out if deadline is reached. if time.Now().After(deadline) { break } // Walk the front path one step. for k1 := -d + k1start; k1 <= d-k1end; k1 += 2 { k1_offset := v_offset + k1 var x1 int if k1 == -d || (k1 != d && v1[k1_offset-1] < v1[k1_offset+1]) { x1 = v1[k1_offset+1] } else { x1 = v1[k1_offset-1] + 1 } y1 := x1 - k1 for x1 < runes1_len && y1 < runes2_len { if runes1[x1] != runes2[y1] { break } x1++ y1++ } v1[k1_offset] = x1 if x1 > runes1_len { // Ran off the right of the graph. k1end += 2 } else if y1 > runes2_len { // Ran off the bottom of the graph. k1start += 2 } else if front { k2_offset := v_offset + delta - k1 if k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1 { // Mirror x2 onto top-left coordinate system. x2 := runes1_len - v2[k2_offset] if x1 >= x2 { // Overlap detected. return dmp.diffBisectSplit_(runes1, runes2, x1, y1, deadline) } } } } // Walk the reverse path one step. for k2 := -d + k2start; k2 <= d-k2end; k2 += 2 { k2_offset := v_offset + k2 var x2 int if k2 == -d || (k2 != d && v2[k2_offset-1] < v2[k2_offset+1]) { x2 = v2[k2_offset+1] } else { x2 = v2[k2_offset-1] + 1 } var y2 = x2 - k2 for x2 < runes1_len && y2 < runes2_len { if runes1[runes1_len-x2-1] != runes2[runes2_len-y2-1] { break } x2++ y2++ } v2[k2_offset] = x2 if x2 > runes1_len { // Ran off the left of the graph. k2end += 2 } else if y2 > runes2_len { // Ran off the top of the graph. k2start += 2 } else if !front { k1_offset := v_offset + delta - k2 if k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1 { x1 := v1[k1_offset] y1 := v_offset + x1 - k1_offset // Mirror x2 onto top-left coordinate system. x2 = runes1_len - x2 if x1 >= x2 { // Overlap detected. return dmp.diffBisectSplit_(runes1, runes2, x1, y1, deadline) } } } } } // Diff took too long and hit the deadline or // number of diffs equals number of characters, no commonality at all. return []Diff{ Diff{DiffDelete, string(runes1)}, Diff{DiffInsert, string(runes2)}, } } func (dmp *DiffMatchPatch) diffBisectSplit_(runes1, runes2 []rune, x, y int, deadline time.Time) []Diff { runes1a := runes1[:x] runes2a := runes2[:y] runes1b := runes1[x:] runes2b := runes2[y:] // Compute both diffs serially. diffs := dmp.diffMainRunes(runes1a, runes2a, false, deadline) diffsb := dmp.diffMainRunes(runes1b, runes2b, false, deadline) return append(diffs, diffsb...) } // DiffLinesToChars split two texts into a list of strings. Reduces the texts to a string of // hashes where each Unicode character represents one line. // It's slightly faster to call DiffLinesToRunes first, followed by DiffMainRunes. func (dmp *DiffMatchPatch) DiffLinesToChars(text1, text2 string) (string, string, []string) { chars1, chars2, lineArray := dmp.DiffLinesToRunes(text1, text2) return string(chars1), string(chars2), lineArray } // DiffLinesToRunes splits two texts into a list of runes. Each rune represents one line. func (dmp *DiffMatchPatch) DiffLinesToRunes(text1, text2 string) ([]rune, []rune, []string) { // '\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 := []string{""} // e.g. lineArray[4] == 'Hello\n' lineHash := map[string]int{} // e.g. lineHash['Hello\n'] == 4 chars1 := dmp.diffLinesToRunesMunge(text1, &lineArray, lineHash) chars2 := dmp.diffLinesToRunesMunge(text2, &lineArray, lineHash) return chars1, chars2, lineArray } func (dmp *DiffMatchPatch) diffLinesToRunes(text1, text2 []rune) ([]rune, []rune, []string) { return dmp.DiffLinesToRunes(string(text1), string(text2)) } // diffLinesToRunesMunge splits a text into an array of strings. Reduces the // texts to a []rune where each Unicode character represents one line. // We use strings instead of []runes as input mainly because you can't use []rune as a map key. func (dmp *DiffMatchPatch) diffLinesToRunesMunge(text string, lineArray *[]string, lineHash map[string]int) []rune { // 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 runes := []rune{} for lineEnd < len(text)-1 { lineEnd = indexOf(text, "\n", lineStart) if lineEnd == -1 { lineEnd = len(text) - 1 } line := text[lineStart : lineEnd+1] lineStart = lineEnd + 1 lineValue_, ok := lineHash[line] if ok { runes = append(runes, rune(lineValue_)) } else { *lineArray = append(*lineArray, line) lineHash[line] = len(*lineArray) - 1 runes = append(runes, rune(len(*lineArray)-1)) } } return runes } // DiffCharsToLines rehydrates the text in a diff from a string of line hashes to real lines of // text. func (dmp *DiffMatchPatch) DiffCharsToLines(diffs []Diff, lineArray []string) []Diff { hydrated := make([]Diff, 0, len(diffs)) for _, aDiff := range diffs { chars := aDiff.Text text := make([]string, len(chars)) for i, r := range chars { text[i] = lineArray[r] } aDiff.Text = strings.Join(text, "") hydrated = append(hydrated, aDiff) } return hydrated } // DiffCommonPrefix determines the common prefix length of two strings. func (dmp *DiffMatchPatch) DiffCommonPrefix(text1, text2 string) int { // Unused in this code, but retained for interface compatibility. return commonPrefixLength([]rune(text1), []rune(text2)) } // DiffCommonSuffix determines the common suffix length of two strings. func (dmp *DiffMatchPatch) DiffCommonSuffix(text1, text2 string) int { // Unused in this code, but retained for interface compatibility. return commonSuffixLength([]rune(text1), []rune(text2)) } // commonPrefixLength returns the length of the common prefix of two rune slices. func commonPrefixLength(text1, text2 []rune) int { short, long := text1, text2 if len(short) > len(long) { short, long = long, short } for i, r := range short { if r != long[i] { return i } } return len(short) } // commonSuffixLength returns the length of the common suffix of two rune slices. func commonSuffixLength(text1, text2 []rune) int { n := min(len(text1), len(text2)) for i := 0; i < n; i++ { if text1[len(text1)-i-1] != text2[len(text2)-i-1] { return i } } return n // Binary search. // Performance analysis: http://neil.fraser.name/news/2007/10/09/ /* pointermin := 0 pointermax := math.Min(len(text1), len(text2)) pointermid := pointermax pointerend := 0 for pointermin < pointermid { if text1[len(text1)-pointermid:len(text1)-pointerend] == text2[len(text2)-pointermid:len(text2)-pointerend] { pointermin = pointermid pointerend = pointermin } else { pointermax = pointermid } pointermid = math.Floor((pointermax-pointermin)/2 + pointermin) } return pointermid */ } // DiffCommonOverlap determines if the suffix of one string is the prefix of another. func (dmp *DiffMatchPatch) DiffCommonOverlap(text1 string, text2 string) int { // Cache the text lengths to prevent multiple calls. text1_length := len(text1) text2_length := len(text2) // Eliminate the null case. if text1_length == 0 || text2_length == 0 { return 0 } // Truncate the longer string. if text1_length > text2_length { text1 = text1[text1_length-text2_length:] } else if text1_length < text2_length { text2 = text2[0:text1_length] } text_length := int(math.Min(float64(text1_length), float64(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 for { pattern := text1[text_length-length:] found := strings.Index(text2, pattern) if found == -1 { return best } length += found if found == 0 || text1[text_length-length:] == text2[0:length] { best = length length++ } } return 0 } // DiffHalfMatch checks whether the two texts share a substring which is at // least half the length of the longer text. This speedup can produce non-minimal diffs. func (dmp *DiffMatchPatch) DiffHalfMatch(text1, text2 string) []string { // Unused in this code, but retained for interface compatibility. runeSlices := dmp.diffHalfMatch([]rune(text1), []rune(text2)) if runeSlices == nil { return nil } result := make([]string, len(runeSlices)) for i, r := range runeSlices { result[i] = string(r) } return result } func (dmp *DiffMatchPatch) diffHalfMatch(text1, text2 []rune) [][]rune { if dmp.DiffTimeout <= 0 { // Don't risk returning a non-optimal diff if we have unlimited time. return nil } var longtext, shorttext []rune if len(text1) > len(text2) { longtext = text1 shorttext = text2 } else { longtext = text2 shorttext = text1 } if len(longtext) < 4 || len(shorttext)*2 < len(longtext) { return nil // Pointless. } // First check if the second quarter is the seed for a half-match. hm1 := dmp.diffHalfMatchI(longtext, shorttext, int(float64(len(longtext)+3)/4)) // Check again based on the third quarter. hm2 := dmp.diffHalfMatchI(longtext, shorttext, int(float64(len(longtext)+1)/2)) hm := [][]rune{} if hm1 == nil && hm2 == nil { return nil } else if hm2 == nil { hm = hm1 } else if hm1 == nil { 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) { return hm } else { return [][]rune{hm[2], hm[3], hm[0], hm[1], hm[4]} } return nil } /** * Does a substring of shorttext exist within longtext such that the substring * is at least half the length of longtext? * @param {string} longtext Longer string. * @param {string} shorttext Shorter string. * @param {number} i Start index of quarter length substring within longtext. * @return {Array.} 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 null if there was no match. * @private */ func (dmp *DiffMatchPatch) diffHalfMatchI(l, s []rune, i int) [][]rune { // Start with a 1/4 length substring at position i as a seed. seed := l[i : i+len(l)/4] j := -1 best_common := []rune{} best_longtext_a := []rune{} best_longtext_b := []rune{} best_shorttext_a := []rune{} best_shorttext_b := []rune{} if j < len(s) { j = runesIndexOf(s, seed, j+1) for { if j == -1 { break } prefixLength := commonPrefixLength(l[i:], s[j:]) suffixLength := commonSuffixLength(l[:i], s[:j]) if len(best_common) < suffixLength+prefixLength { best_common = concat(s[j-suffixLength:j], s[j:j+prefixLength]) best_longtext_a = l[:i-suffixLength] best_longtext_b = l[i+prefixLength:] best_shorttext_a = s[:j-suffixLength] best_shorttext_b = s[j+prefixLength:] } j = runesIndexOf(s, seed, j+1) } } if len(best_common)*2 >= len(l) { return [][]rune{ best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common, } } return nil } func concat(r1, r2 []rune) []rune { result := make([]rune, len(r1)+len(r2)) copy(result, r1) copy(result[len(r1):], r2) return result } // Diff_cleanupSemantic reduces the number of edits by eliminating // semantically trivial equalities. func (dmp *DiffMatchPatch) DiffCleanupSemantic(diffs []Diff) []Diff { changes := false equalities := new(Stack) // Stack of indices where equalities are found. var lastequality string // Always equal to diffs[equalities[equalitiesLength - 1]][1] var pointer int // Index of current position. // Number of characters that changed prior to the equality. var length_insertions1, length_deletions1 int // Number of characters that changed after the equality. var length_insertions2, length_deletions2 int for pointer < len(diffs) { if diffs[pointer].Type == DiffEqual { // Equality found. equalities.Push(pointer) length_insertions1 = length_insertions2 length_deletions1 = length_deletions2 length_insertions2 = 0 length_deletions2 = 0 lastequality = diffs[pointer].Text } else { // An insertion or deletion. if diffs[pointer].Type == DiffInsert { length_insertions2 += len(diffs[pointer].Text) } else { length_deletions2 += len(diffs[pointer].Text) } // Eliminate an equality that is smaller or equal to the edits on both // sides of it. _difference1 := int(math.Max(float64(length_insertions1), float64(length_deletions1))) _difference2 := int(math.Max(float64(length_insertions2), float64(length_deletions2))) if len(lastequality) > 0 && (len(lastequality) <= _difference1) && (len(lastequality) <= _difference2) { // Duplicate record. insPoint := equalities.Peek().(int) diffs = append( diffs[:insPoint], append([]Diff{Diff{DiffDelete, lastequality}}, diffs[insPoint:]...)...) // Change second copy to insert. diffs[insPoint+1].Type = DiffInsert // Throw away the equality we just deleted. equalities.Pop() if equalities.Len() > 0 { equalities.Pop() pointer = equalities.Peek().(int) } else { pointer = -1 } length_insertions1 = 0 // Reset the counters. length_deletions1 = 0 length_insertions2 = 0 length_deletions2 = 0 lastequality = "" changes = true } } pointer++ } // Normalize the diff. if changes { diffs = dmp.DiffCleanupMerge(diffs) } diffs = dmp.DiffCleanupSemanticLossless(diffs) // Find any overlaps between deletions and insertions. // e.g: abcxxxxxxdef // -> abcxxxdef // e.g: xxxabcdefxxx // -> defxxxabc // Only extract an overlap if it is as big as the edit ahead or behind it. pointer = 1 for pointer < len(diffs) { if diffs[pointer-1].Type == DiffDelete && diffs[pointer].Type == DiffInsert { deletion := diffs[pointer-1].Text insertion := diffs[pointer].Text overlap_length1 := dmp.DiffCommonOverlap(deletion, insertion) overlap_length2 := dmp.DiffCommonOverlap(insertion, deletion) if overlap_length1 >= overlap_length2 { if float64(overlap_length1) >= float64(len(deletion))/2 || float64(overlap_length1) >= float64(len(insertion))/2 { // Overlap found. Insert an equality and trim the surrounding edits. diffs = append( diffs[:pointer], append([]Diff{Diff{DiffEqual, insertion[:overlap_length1]}}, diffs[pointer:]...)...) //diffs.splice(pointer, 0, // [DiffEqual, insertion[0 : overlap_length1)]] diffs[pointer-1].Text = deletion[0 : len(deletion)-overlap_length1] diffs[pointer+1].Text = insertion[overlap_length1:] pointer++ } } else { if float64(overlap_length2) >= float64(len(deletion))/2 || float64(overlap_length2) >= float64(len(insertion))/2 { // Reverse overlap found. // Insert an equality and swap and trim the surrounding edits. overlap := Diff{DiffEqual, insertion[overlap_length2:]} diffs = append( diffs[:pointer], append([]Diff{overlap}, diffs[pointer:]...)...) // diffs.splice(pointer, 0, // [DiffEqual, deletion[0 : overlap_length2)]] diffs[pointer-1].Type = DiffInsert diffs[pointer-1].Text = insertion[0 : len(insertion)-overlap_length2] diffs[pointer+1].Type = DiffDelete diffs[pointer+1].Text = deletion[overlap_length2:] pointer++ } } pointer++ } pointer++ } return diffs } // Diff_cleanupSemanticLossless looks 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 cat came. -> The cat came. func (dmp *DiffMatchPatch) DiffCleanupSemanticLossless(diffs []Diff) []Diff { /** * 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. * @param {string} one First string. * @param {string} two Second string. * @return {number} The score. * @private */ diffCleanupSemanticScore_ := func(one, two string) int { if len(one) == 0 || len(two) == 0 { // 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. rune1, _ := utf8.DecodeLastRuneInString(one) rune2, _ := utf8.DecodeRuneInString(two) char1 := string(rune1) char2 := string(rune2) nonAlphaNumeric1 := nonAlphaNumericRegex_.MatchString(char1) nonAlphaNumeric2 := nonAlphaNumericRegex_.MatchString(char2) whitespace1 := nonAlphaNumeric1 && whitespaceRegex_.MatchString(char1) whitespace2 := nonAlphaNumeric2 && whitespaceRegex_.MatchString(char2) lineBreak1 := whitespace1 && linebreakRegex_.MatchString(char1) lineBreak2 := whitespace2 && linebreakRegex_.MatchString(char2) blankLine1 := lineBreak1 && blanklineEndRegex_.MatchString(one) blankLine2 := lineBreak2 && blanklineEndRegex_.MatchString(two) if blankLine1 || blankLine2 { // Five points for blank lines. return 5 } else if lineBreak1 || lineBreak2 { // Four points for line breaks. return 4 } else if nonAlphaNumeric1 && !whitespace1 && whitespace2 { // Three points for end of sentences. return 3 } else if whitespace1 || whitespace2 { // Two points for whitespace. return 2 } else if nonAlphaNumeric1 || nonAlphaNumeric2 { // One point for non-alphanumeric. return 1 } return 0 } pointer := 1 // Intentionally ignore the first and last element (don't need checking). for pointer < len(diffs)-1 { if diffs[pointer-1].Type == DiffEqual && diffs[pointer+1].Type == DiffEqual { // This is a single edit surrounded by equalities. equality1 := diffs[pointer-1].Text edit := diffs[pointer].Text equality2 := diffs[pointer+1].Text // First, shift the edit as far left as possible. commonOffset := dmp.DiffCommonSuffix(equality1, edit) if commonOffset > 0 { commonString := edit[len(edit)-commonOffset:] equality1 = equality1[0 : len(equality1)-commonOffset] edit = commonString + edit[:len(edit)-commonOffset] equality2 = commonString + equality2 } // Second, step character by character right, looking for the best fit. bestEquality1 := equality1 bestEdit := edit bestEquality2 := equality2 bestScore := diffCleanupSemanticScore_(equality1, edit) + diffCleanupSemanticScore_(edit, equality2) for len(edit) != 0 && len(equality2) != 0 { _, sz := utf8.DecodeRuneInString(edit) if len(equality2) < sz || edit[:sz] != equality2[:sz] { break } equality1 += edit[:sz] edit = edit[sz:] + equality2[:sz] equality2 = equality2[sz:] score := diffCleanupSemanticScore_(equality1, edit) + diffCleanupSemanticScore_(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].Text != bestEquality1 { // We have an improvement, save it back to the diff. if len(bestEquality1) != 0 { diffs[pointer-1].Text = bestEquality1 } else { diffs = splice(diffs, pointer-1, 1) pointer-- } diffs[pointer].Text = bestEdit if len(bestEquality2) != 0 { diffs[pointer+1].Text = bestEquality2 } else { //splice(diffs, pointer+1, 1) diffs = append(diffs[:pointer+1], diffs[pointer+2:]...) pointer-- } } } pointer++ } return diffs } // Diff_cleanupEfficiency reduces the number of edits by eliminating // operationally trivial equalities. func (dmp *DiffMatchPatch) DiffCleanupEfficiency(diffs []Diff) []Diff { changes := false // Stack of indices where equalities are found. equalities := new(Stack) // Always equal to equalities[equalitiesLength-1][1] lastequality := "" pointer := 0 // Index of current position. // Is there an insertion operation before the last equality. pre_ins := false // Is there a deletion operation before the last equality. pre_del := false // Is there an insertion operation after the last equality. post_ins := false // Is there a deletion operation after the last equality. post_del := false for pointer < len(diffs) { if diffs[pointer].Type == DiffEqual { // Equality found. if len(diffs[pointer].Text) < dmp.DiffEditCost && (post_ins || post_del) { // Candidate found. equalities.Push(pointer) pre_ins = post_ins pre_del = post_del lastequality = diffs[pointer].Text } else { // Not a candidate, and can never become one. equalities.Clear() lastequality = "" } post_ins = false post_del = false } else { // An insertion or deletion. if diffs[pointer].Type == DiffDelete { post_del = true } else { post_ins = true } /* * Five types to be split: * ABXYCD * AXCD * ABXC * AXCD * ABXC */ var sum_pres int if pre_ins { sum_pres++ } if pre_del { sum_pres++ } if post_ins { sum_pres++ } if post_del { sum_pres++ } if len(lastequality) > 0 && ((pre_ins && pre_del && post_ins && post_del) || ((len(lastequality) < dmp.DiffEditCost/2) && sum_pres == 3)) { // Duplicate record. diffs = append(diffs[:equalities.Peek().(int)], append([]Diff{Diff{DiffDelete, lastequality}}, diffs[equalities.Peek().(int):]...)...) // Change second copy to insert. diffs[equalities.Peek().(int)+1].Type = DiffInsert equalities.Pop() // Throw away the equality we just deleted. lastequality = "" if pre_ins && pre_del { // No changes made which could affect previous entry, keep going. post_ins = true post_del = true equalities.Clear() } else { if equalities.Len() > 0 { equalities.Pop() pointer = equalities.Peek().(int) } else { pointer = -1 } post_ins = false post_del = false } changes = true } } pointer++ } if changes { diffs = dmp.DiffCleanupMerge(diffs) } return diffs } // Diff_cleanupMerge reorders and merges like edit sections. Merge equalities. // Any edit section can move as long as it doesn't cross an equality. func (dmp *DiffMatchPatch) DiffCleanupMerge(diffs []Diff) []Diff { // Add a dummy entry at the end. diffs = append(diffs, Diff{DiffEqual, ""}) pointer := 0 count_delete := 0 count_insert := 0 commonlength := 0 text_delete := "" text_insert := "" for pointer < len(diffs) { switch diffs[pointer].Type { case DiffInsert: count_insert += 1 text_insert += diffs[pointer].Text pointer += 1 break case DiffDelete: count_delete += 1 text_delete += diffs[pointer].Text pointer += 1 break case DiffEqual: // Upon reaching an equality, check for prior redundancies. if count_delete+count_insert > 1 { if count_delete != 0 && count_insert != 0 { // Factor out any common prefixies. commonlength = dmp.DiffCommonPrefix(text_insert, text_delete) if commonlength != 0 { x := pointer - count_delete - count_insert if x > 0 && diffs[x-1].Type == DiffEqual { diffs[x-1].Text += text_insert[:commonlength] } else { diffs = append([]Diff{Diff{DiffEqual, text_insert[:commonlength]}}, diffs...) pointer += 1 } text_insert = text_insert[commonlength:] text_delete = text_delete[commonlength:] } // Factor out any common suffixies. commonlength = dmp.DiffCommonSuffix(text_insert, text_delete) if commonlength != 0 { insert_index := len(text_insert) - commonlength delete_index := len(text_delete) - commonlength diffs[pointer].Text = text_insert[insert_index:] + diffs[pointer].Text text_insert = text_insert[:insert_index] text_delete = text_delete[:delete_index] } } // Delete the offending records and add the merged ones. if count_delete == 0 { diffs = splice(diffs, pointer-count_insert, count_delete+count_insert, Diff{DiffInsert, text_insert}) } else if count_insert == 0 { diffs = splice(diffs, pointer-count_delete, count_delete+count_insert, Diff{DiffDelete, text_delete}) } else { diffs = splice(diffs, pointer-count_delete-count_insert, count_delete+count_insert, Diff{DiffDelete, text_delete}, Diff{DiffInsert, text_insert}) } pointer = pointer - count_delete - count_insert + 1 if count_delete != 0 { pointer += 1 } if count_insert != 0 { pointer += 1 } } else if pointer != 0 && diffs[pointer-1].Type == DiffEqual { // Merge this equality with the previous one. diffs[pointer-1].Text += diffs[pointer].Text diffs = append(diffs[:pointer], diffs[pointer+1:]...) } else { pointer++ } count_insert = 0 count_delete = 0 text_delete = "" text_insert = "" break } } if len(diffs[len(diffs)-1].Text) == 0 { diffs = diffs[0 : len(diffs)-1] // 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: ABAC -> ABAC changes := false pointer = 1 // Intentionally ignore the first and last element (don't need checking). for pointer < (len(diffs) - 1) { if diffs[pointer-1].Type == DiffEqual && diffs[pointer+1].Type == DiffEqual { // This is a single edit surrounded by equalities. if strings.HasSuffix(diffs[pointer].Text, diffs[pointer-1].Text) { // Shift the edit over the previous equality. diffs[pointer].Text = diffs[pointer-1].Text + diffs[pointer].Text[:len(diffs[pointer].Text)-len(diffs[pointer-1].Text)] diffs[pointer+1].Text = diffs[pointer-1].Text + diffs[pointer+1].Text diffs = splice(diffs, pointer-1, 1) changes = true } else if strings.HasPrefix(diffs[pointer].Text, diffs[pointer+1].Text) { // Shift the edit over the next equality. diffs[pointer-1].Text += diffs[pointer+1].Text diffs[pointer].Text = diffs[pointer].Text[len(diffs[pointer+1].Text):] + diffs[pointer+1].Text diffs = splice(diffs, pointer+1, 1) changes = true } } pointer++ } // If shifts were made, the diff needs reordering and another shift sweep. if changes { diffs = dmp.DiffCleanupMerge(diffs) } return diffs } // Diff_xIndex. loc is a location in text1, comAdde and return the equivalent location in // text2. // e.g. "The cat" vs "The big cat", 1->1, 5->8 func (dmp *DiffMatchPatch) DiffXIndex(diffs []Diff, loc int) int { chars1 := 0 chars2 := 0 last_chars1 := 0 last_chars2 := 0 lastDiff := Diff{} for i := 0; i < len(diffs); i++ { aDiff := diffs[i] if aDiff.Type != DiffInsert { // Equality or deletion. chars1 += len(aDiff.Text) } if aDiff.Type != DiffDelete { // Equality or insertion. chars2 += len(aDiff.Text) } if chars1 > loc { // Overshot the location. lastDiff = aDiff break } last_chars1 = chars1 last_chars2 = chars2 } if lastDiff.Type == DiffDelete { // The location was deleted. return last_chars2 } // Add the remaining character length. return last_chars2 + (loc - last_chars1) } // DiffPrettyHtml converts a []Diff into a pretty HTML report. // It is intended as an example from which to write one's own // display functions. func (dmp *DiffMatchPatch) DiffPrettyHtml(diffs []Diff) string { var buff bytes.Buffer for _, diff := range diffs { text := strings.Replace(html.EscapeString(diff.Text), "\n", "¶
", -1) switch diff.Type { case DiffInsert: buff.WriteString("") buff.WriteString(text) buff.WriteString("") case DiffDelete: buff.WriteString("") buff.WriteString(text) buff.WriteString("") case DiffEqual: buff.WriteString("") buff.WriteString(text) buff.WriteString("") } } return buff.String() } // Diff_text1 computes and returns the source text (all equalities and deletions). func (dmp *DiffMatchPatch) DiffText1(diffs []Diff) string { //StringBuilder text = new StringBuilder() var text bytes.Buffer for _, aDiff := range diffs { if aDiff.Type != DiffInsert { text.WriteString(aDiff.Text) } } return text.String() } // Diff_text2 computes and returns the destination text (all equalities and insertions). func (dmp *DiffMatchPatch) DiffText2(diffs []Diff) string { var text bytes.Buffer for _, aDiff := range diffs { if aDiff.Type != DiffDelete { text.WriteString(aDiff.Text) } } return text.String() } // Diff_levenshtein computes the Levenshtein distance; the number of inserted, deleted or // substituted characters. func (dmp *DiffMatchPatch) DiffLevenshtein(diffs []Diff) int { levenshtein := 0 insertions := 0 deletions := 0 for _, aDiff := range diffs { switch aDiff.Type { case DiffInsert: insertions += len(aDiff.Text) case DiffDelete: deletions += len(aDiff.Text) case DiffEqual: // A deletion and an insertion is one substitution. levenshtein += max(insertions, deletions) insertions = 0 deletions = 0 } } levenshtein += max(insertions, deletions) return levenshtein } // Diff_toDelta crushes 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. func (dmp *DiffMatchPatch) DiffToDelta(diffs []Diff) string { var text bytes.Buffer for _, aDiff := range diffs { switch aDiff.Type { case DiffInsert: text.WriteString("+") text.WriteString(strings.Replace(url.QueryEscape(aDiff.Text), "+", " ", -1)) text.WriteString("\t") break case DiffDelete: text.WriteString("-") text.WriteString(strconv.Itoa(utf8.RuneCountInString(aDiff.Text))) text.WriteString("\t") break case DiffEqual: text.WriteString("=") text.WriteString(strconv.Itoa(utf8.RuneCountInString(aDiff.Text))) text.WriteString("\t") break } } delta := text.String() if len(delta) != 0 { // Strip off trailing tab character. delta = delta[0 : utf8.RuneCountInString(delta)-1] delta = unescaper.Replace(delta) } return delta } // Diff_fromDelta. Given the original text1, and an encoded string which describes the // operations required to transform text1 into text2, comAdde the full diff. func (dmp *DiffMatchPatch) DiffFromDelta(text1, delta string) (diffs []Diff, err error) { diffs = []Diff{} defer func() { if r := recover(); r != nil { err = r.(error) } }() pointer := 0 // Cursor in text1 tokens := strings.Split(delta, "\t") for _, token := range tokens { if len(token) == 0 { // 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:] switch op := token[0]; op { case '+': // decode would Diff all "+" to " " param = strings.Replace(param, "+", "%2b", -1) param, err = url.QueryUnescape(param) if err != nil { return nil, err } if !utf8.ValidString(param) { return nil, fmt.Errorf("invalid UTF-8 token: %q", param) } diffs = append(diffs, Diff{DiffInsert, param}) case '=', '-': n, err := strconv.ParseInt(param, 10, 0) if err != nil { return diffs, err } else if n < 0 { return diffs, errors.New("Negative number in DiffFromDelta: " + param) } // remember that string slicing is by byte - we want by rune here. text := string([]rune(text1)[pointer : pointer+int(n)]) pointer += int(n) if op == '=' { diffs = append(diffs, Diff{DiffEqual, text}) } else { diffs = append(diffs, Diff{DiffDelete, text}) } default: // Anything else is an error. return diffs, errors.New("Invalid diff operation in DiffFromDelta: " + string(token[0])) } } if pointer != len([]rune(text1)) { return diffs, fmt.Errorf("Delta length (%v) smaller than source text length (%v)", pointer, len(text1)) } return diffs, err } // MATCH FUNCTIONS // MatchMain locates the best instance of 'pattern' in 'text' near 'loc'. // Returns -1 if no match found. func (dmp *DiffMatchPatch) MatchMain(text, pattern string, loc int) int { // Check for null inputs not needed since null can't be passed in C#. loc = int(math.Max(0, math.Min(float64(loc), float64(len(text))))) if text == pattern { // Shortcut (potentially not guaranteed by the algorithm) return 0 } else if len(text) == 0 { // Nothing to match. return -1 } else if loc+len(pattern) <= len(text) && text[loc:loc+len(pattern)] == pattern { // Perfect match at the perfect spot! (Includes case of null pattern) return loc } // Do a fuzzy compare. return dmp.MatchBitap(text, pattern, loc) } // MatchBitap locates the best instance of 'pattern' in 'text' near 'loc' using the // Bitap algorithm. Returns -1 if no match found. func (dmp *DiffMatchPatch) MatchBitap(text, pattern string, loc int) int { // Initialise the alphabet. s := dmp.MatchAlphabet(pattern) // Highest score beyond which we give up. var score_threshold float64 = dmp.MatchThreshold // Is there a nearby exact match? (speedup) best_loc := indexOf(text, pattern, loc) if best_loc != -1 { score_threshold = math.Min(dmp.matchBitapScore(0, best_loc, loc, pattern), score_threshold) // What about in the other direction? (speedup) best_loc = lastIndexOf(text, pattern, loc+len(pattern)) if best_loc != -1 { score_threshold = math.Min(dmp.matchBitapScore(0, best_loc, loc, pattern), score_threshold) } } // Initialise the bit arrays. matchmask := 1 << uint((len(pattern) - 1)) best_loc = -1 var bin_min, bin_mid int bin_max := len(pattern) + len(text) last_rd := []int{} for d := 0; d < len(pattern); d++ { // 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 for bin_min < bin_mid { if dmp.matchBitapScore(d, loc+bin_mid, loc, pattern) <= 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 := int(math.Max(1, float64(loc-bin_mid+1))) finish := int(math.Min(float64(loc+bin_mid), float64(len(text))) + float64(len(pattern))) rd := make([]int, finish+2) rd[finish+1] = (1 << uint(d)) - 1 for j := finish; j >= start; j-- { var charMatch int if len(text) <= j-1 { // Out of range. charMatch = 0 } else if _, ok := s[text[j-1]]; !ok { charMatch = 0 } else { charMatch = s[text[j-1]] } 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) != 0 { score := dmp.matchBitapScore(d, j-1, loc, pattern) // 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 = int(math.Max(1, float64(2*loc-best_loc))) } else { // Already passed loc, downhill from here on in. break } } } } if dmp.matchBitapScore(d+1, loc, loc, pattern) > score_threshold { // No hope for a (better) match at greater error levels. break } last_rd = rd } return best_loc } // matchBitapScore computes and returns the score for a match with e errors and x location. func (dmp *DiffMatchPatch) matchBitapScore(e, x, loc int, pattern string) float64 { var accuracy float64 = float64(e) / float64(len(pattern)) proximity := math.Abs(float64(loc - x)) if dmp.MatchDistance == 0 { // Dodge divide by zero error. if proximity == 0 { return accuracy } else { return 1.0 } } return accuracy + (proximity / float64(dmp.MatchDistance)) } // MatchAlphabet initialises the alphabet for the Bitap algorithm. func (dmp *DiffMatchPatch) MatchAlphabet(pattern string) map[byte]int { s := map[byte]int{} char_pattern := []byte(pattern) for _, c := range char_pattern { _, ok := s[c] if !ok { s[c] = 0 } } i := 0 for _, c := range char_pattern { value := s[c] | int(uint(1)< 2 { diffs = dmp.DiffCleanupSemantic(diffs) diffs = dmp.DiffCleanupEfficiency(diffs) } return dmp.PatchMake(text1, diffs) case []Diff: return dmp.patchMake2(text1, t) } } else if len(opt) == 3 { return dmp.PatchMake(opt[0], opt[2]) } return []Patch{} } // Compute a list of patches to turn text1 into text2. // text2 is not provided, diffs are the delta between text1 and text2. func (dmp *DiffMatchPatch) patchMake2(text1 string, diffs []Diff) []Patch { // Check for null inputs not needed since null can't be passed in C#. patches := []Patch{} if len(diffs) == 0 { return patches // Get rid of the null case. } patch := Patch{} char_count1 := 0 // Number of characters into the text1 string. char_count2 := 0 // Number of characters into the text2 string. // Start with text1 (prepatch_text) and apply the diffs until we arrive at // text2 (postpatch_text). We recreate the patches one by one to determine // context info. prepatch_text := text1 postpatch_text := text1 for i, aDiff := range diffs { if len(patch.diffs) == 0 && aDiff.Type != DiffEqual { // A new patch starts here. patch.start1 = char_count1 patch.start2 = char_count2 } switch aDiff.Type { case DiffInsert: patch.diffs = append(patch.diffs, aDiff) patch.length2 += len(aDiff.Text) postpatch_text = postpatch_text[:char_count2] + aDiff.Text + postpatch_text[char_count2:] case DiffDelete: patch.length1 += len(aDiff.Text) patch.diffs = append(patch.diffs, aDiff) postpatch_text = postpatch_text[:char_count2] + postpatch_text[char_count2+len(aDiff.Text):] case DiffEqual: if len(aDiff.Text) <= 2*dmp.PatchMargin && len(patch.diffs) != 0 && i != len(diffs)-1 { // Small equality inside a patch. patch.diffs = append(patch.diffs, aDiff) patch.length1 += len(aDiff.Text) patch.length2 += len(aDiff.Text) } if len(aDiff.Text) >= 2*dmp.PatchMargin { // Time for a new patch. if len(patch.diffs) != 0 { patch = dmp.PatchAddContext(patch, prepatch_text) patches = append(patches, patch) patch = Patch{} // 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 aDiff.Type != DiffInsert { char_count1 += len(aDiff.Text) } if aDiff.Type != DiffDelete { char_count2 += len(aDiff.Text) } } // Pick up the leftover patch if not empty. if len(patch.diffs) != 0 { patch = dmp.PatchAddContext(patch, prepatch_text) patches = append(patches, patch) } return patches } // PatchDeepCopy returns an array that is identical to a // given an array of patches. func (dmp *DiffMatchPatch) PatchDeepCopy(patches []Patch) []Patch { patchesCopy := []Patch{} for _, aPatch := range patches { patchCopy := Patch{} for _, aDiff := range aPatch.diffs { patchCopy.diffs = append(patchCopy.diffs, Diff{ aDiff.Type, aDiff.Text, }) } patchCopy.start1 = aPatch.start1 patchCopy.start2 = aPatch.start2 patchCopy.length1 = aPatch.length1 patchCopy.length2 = aPatch.length2 patchesCopy = append(patchesCopy, patchCopy) } return patchesCopy } // PatchApply merges a set of patches onto the text. Returns a patched text, as well // as an array of true/false values indicating which patches were applied. func (dmp *DiffMatchPatch) PatchApply(patches []Patch, text string) (string, []bool) { if len(patches) == 0 { return text, []bool{} } // Deep copy the patches so that no changes are made to originals. patches = dmp.PatchDeepCopy(patches) nullPadding := dmp.PatchAddPadding(patches) text = nullPadding + text + nullPadding patches = dmp.PatchSplitMax(patches) x := 0 // 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 := make([]bool, len(patches)) for _, aPatch := range patches { expected_loc := aPatch.start2 + delta text1 := dmp.DiffText1(aPatch.diffs) var start_loc int end_loc := -1 if len(text1) > dmp.MatchMaxBits { // PatchSplitMax will only provide an oversized pattern // in the case of a monster delete. start_loc = dmp.MatchMain(text, text1[:dmp.MatchMaxBits], expected_loc) if start_loc != -1 { end_loc = dmp.MatchMain(text, text1[len(text1)-dmp.MatchMaxBits:], expected_loc+len(text1)-dmp.MatchMaxBits) if end_loc == -1 || start_loc >= end_loc { // Can't find valid trailing context. Drop this patch. start_loc = -1 } } } else { start_loc = dmp.MatchMain(text, text1, expected_loc) } if start_loc == -1 { // No match found. :( results[x] = false // Subtract the delta for this failed patch from subsequent patches. delta -= aPatch.length2 - aPatch.length1 } else { // Found a match. :) results[x] = true delta = start_loc - expected_loc var text2 string if end_loc == -1 { text2 = text[start_loc:int(math.Min(float64(start_loc+len(text1)), float64(len(text))))] } else { text2 = text[start_loc:int(math.Min(float64(end_loc+dmp.MatchMaxBits), float64(len(text))))] } if text1 == text2 { // Perfect match, just shove the Replacement text in. text = text[:start_loc] + dmp.DiffText2(aPatch.diffs) + text[start_loc+len(text1):] } else { // Imperfect match. Run a diff to get a framework of equivalent // indices. diffs := dmp.DiffMain(text1, text2, false) if len(text1) > dmp.MatchMaxBits && float64(dmp.DiffLevenshtein(diffs))/float64(len(text1)) > dmp.PatchDeleteThreshold { // The end points match, but the content is unacceptably bad. results[x] = false } else { diffs = dmp.DiffCleanupSemanticLossless(diffs) index1 := 0 for _, aDiff := range aPatch.diffs { if aDiff.Type != DiffEqual { index2 := dmp.DiffXIndex(diffs, index1) if aDiff.Type == DiffInsert { // Insertion text = text[:start_loc+index2] + aDiff.Text + text[start_loc+index2:] } else if aDiff.Type == DiffDelete { // Deletion start_index := start_loc + index2 text = text[:start_index] + text[start_index+dmp.DiffXIndex(diffs, index1+len(aDiff.Text))-index2:] } } if aDiff.Type != DiffDelete { index1 += len(aDiff.Text) } } } } } x++ } // Strip the padding off. text = text[len(nullPadding) : len(nullPadding)+(len(text)-2*len(nullPadding))] return text, results } // PatchAddPadding adds some padding on text start and end so that edges can match something. // Intended to be called only from within patch_apply. func (dmp *DiffMatchPatch) PatchAddPadding(patches []Patch) string { paddingLength := dmp.PatchMargin nullPadding := "" for x := 1; x <= paddingLength; x++ { nullPadding += string(x) } // Bump all the patches forward. for i, _ := range patches { patches[i].start1 += paddingLength patches[i].start2 += paddingLength } // Add some padding on start of first diff. if len(patches[0].diffs) == 0 || patches[0].diffs[0].Type != DiffEqual { // Add nullPadding equality. patches[0].diffs = append([]Diff{Diff{DiffEqual, nullPadding}}, patches[0].diffs...) patches[0].start1 -= paddingLength // Should be 0. patches[0].start2 -= paddingLength // Should be 0. patches[0].length1 += paddingLength patches[0].length2 += paddingLength } else if paddingLength > len(patches[0].diffs[0].Text) { // Grow first equality. extraLength := paddingLength - len(patches[0].diffs[0].Text) patches[0].diffs[0].Text = nullPadding[len(patches[0].diffs[0].Text):] + patches[0].diffs[0].Text patches[0].start1 -= extraLength patches[0].start2 -= extraLength patches[0].length1 += extraLength patches[0].length2 += extraLength } // Add some padding on end of last diff. last := len(patches) - 1 if len(patches[last].diffs) == 0 || patches[last].diffs[len(patches[last].diffs)-1].Type != DiffEqual { // Add nullPadding equality. patches[last].diffs = append(patches[last].diffs, Diff{DiffEqual, nullPadding}) patches[last].length1 += paddingLength patches[last].length2 += paddingLength } else if paddingLength > len(patches[last].diffs[len(patches[last].diffs)-1].Text) { // Grow last equality. lastDiff := patches[last].diffs[len(patches[last].diffs)-1] extraLength := paddingLength - len(lastDiff.Text) patches[last].diffs[len(patches[last].diffs)-1].Text += nullPadding[:extraLength] patches[last].length1 += extraLength patches[last].length2 += extraLength } return nullPadding } // PatchSplitMax looks through the patches and breaks up any which are longer than the // maximum limit of the match algorithm. // Intended to be called only from within patch_apply. func (dmp *DiffMatchPatch) PatchSplitMax(patches []Patch) []Patch { patch_size := dmp.MatchMaxBits for x := 0; x < len(patches); x++ { if patches[x].length1 <= patch_size { continue } bigpatch := patches[x] // Remove the big old patch. patches = append(patches[:x], patches[x+1:]...) x -= 1 start1 := bigpatch.start1 start2 := bigpatch.start2 precontext := "" for len(bigpatch.diffs) != 0 { // Create one of several smaller patches. patch := Patch{} empty := true patch.start1 = start1 - len(precontext) patch.start2 = start2 - len(precontext) if len(precontext) != 0 { patch.length1 = len(precontext) patch.length2 = len(precontext) patch.diffs = append(patch.diffs, Diff{DiffEqual, precontext}) } for len(bigpatch.diffs) != 0 && patch.length1 < patch_size-dmp.PatchMargin { diff_type := bigpatch.diffs[0].Type diff_text := bigpatch.diffs[0].Text if diff_type == DiffInsert { // Insertions are harmless. patch.length2 += len(diff_text) start2 += len(diff_text) patch.diffs = append(patch.diffs, bigpatch.diffs[0]) bigpatch.diffs = bigpatch.diffs[1:] empty = false } else if diff_type == DiffDelete && len(patch.diffs) == 1 && patch.diffs[0].Type == DiffEqual && 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(patch.diffs, Diff{diff_type, diff_text}) bigpatch.diffs = bigpatch.diffs[1:] } else { // Deletion or equality. Only take as much as we can stomach. diff_text = diff_text[:min(len(diff_text), patch_size-patch.length1-dmp.PatchMargin)] patch.length1 += len(diff_text) start1 += len(diff_text) if diff_type == DiffEqual { patch.length2 += len(diff_text) start2 += len(diff_text) } else { empty = false } patch.diffs = append(patch.diffs, Diff{diff_type, diff_text}) if diff_text == bigpatch.diffs[0].Text { bigpatch.diffs = bigpatch.diffs[1:] } else { bigpatch.diffs[0].Text = bigpatch.diffs[0].Text[len(diff_text):] } } } // Compute the head context for the next patch. precontext = dmp.DiffText2(patch.diffs) precontext = precontext[max(0, len(precontext)-dmp.PatchMargin):] postcontext := "" // Append the end context for this patch. if len(dmp.DiffText1(bigpatch.diffs)) > dmp.PatchMargin { postcontext = dmp.DiffText1(bigpatch.diffs)[:dmp.PatchMargin] } else { postcontext = dmp.DiffText1(bigpatch.diffs) } if len(postcontext) != 0 { patch.length1 += len(postcontext) patch.length2 += len(postcontext) if len(patch.diffs) != 0 && patch.diffs[len(patch.diffs)-1].Type == DiffEqual { patch.diffs[len(patch.diffs)-1].Text += postcontext } else { patch.diffs = append(patch.diffs, Diff{DiffEqual, postcontext}) } } if !empty { x += 1 patches = append(patches[:x], append([]Patch{patch}, patches[x:]...)...) } } } return patches } // PatchToText takes a list of patches and returns a textual representation. func (dmp *DiffMatchPatch) PatchToText(patches []Patch) string { var text bytes.Buffer for _, aPatch := range patches { text.WriteString(aPatch.String()) } return text.String() } // PatchFromText parses a textual representation of patches and returns a List of Patch // objects. func (dmp *DiffMatchPatch) PatchFromText(textline string) ([]Patch, error) { patches := []Patch{} if len(textline) == 0 { return patches, nil } text := strings.Split(textline, "\n") textPointer := 0 patchHeader := regexp.MustCompile("^@@ -(\\d+),?(\\d*) \\+(\\d+),?(\\d*) @@$") var patch Patch var sign uint8 var line string for textPointer < len(text) { if !patchHeader.MatchString(text[textPointer]) { return patches, errors.New("Invalid patch string: " + text[textPointer]) } patch = Patch{} m := patchHeader.FindStringSubmatch(text[textPointer]) patch.start1, _ = strconv.Atoi(m[1]) if len(m[2]) == 0 { patch.start1-- patch.length1 = 1 } else if m[2] == "0" { patch.length1 = 0 } else { patch.start1-- patch.length1, _ = strconv.Atoi(m[2]) } patch.start2, _ = strconv.Atoi(m[3]) if len(m[4]) == 0 { patch.start2-- patch.length2 = 1 } else if m[4] == "0" { patch.length2 = 0 } else { patch.start2-- patch.length2, _ = strconv.Atoi(m[4]) } textPointer++ for textPointer < len(text) { if len(text[textPointer]) > 0 { sign = text[textPointer][0] } else { textPointer++ continue } line = text[textPointer][1:] line = strings.Replace(line, "+", "%2b", -1) line, _ = url.QueryUnescape(line) if sign == '-' { // Deletion. patch.diffs = append(patch.diffs, Diff{DiffDelete, line}) } else if sign == '+' { // Insertion. patch.diffs = append(patch.diffs, Diff{DiffInsert, line}) } else if sign == ' ' { // Minor equality. patch.diffs = append(patch.diffs, Diff{DiffEqual, line}) } else if sign == '@' { // Start of next patch. break } else { // WTF? return patches, errors.New("Invalid patch mode '" + string(sign) + "' in: " + string(line)) } textPointer++ } patches = append(patches, patch) } return patches, nil }