Move diff functionality into diff*.go
diff --git a/diffmatchpatch/diff.go b/diffmatchpatch/diff.go new file mode 100644 index 0000000..a3c672a --- /dev/null +++ b/diffmatchpatch/diff.go
@@ -0,0 +1,1362 @@ +// Copyright (c) 2012-2016 The go-diff authors. All rights reserved. +// https://github.com/sergi/go-diff +// See the included LICENSE file for license details. +// +// go-diff is a Go implementation of Google's Diff, Match, and Patch library +// Original library is Copyright (c) 2006 Google Inc. +// http://code.google.com/p/google-diff-match-patch/ + +package diffmatchpatch + +import ( + "bytes" + "errors" + "fmt" + "html" + "math" + "net/url" + "strconv" + "strings" + "time" + "unicode/utf8" +) + +// DiffMain finds the differences between two texts. +func (dmp *DiffMatchPatch) DiffMain(text1, text2 string, checklines bool) []Diff { + return dmp.DiffMainRunes([]rune(text1), []rune(text2), checklines) +} + +// 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(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. + text1A := hm[0] + text1B := hm[1] + text2A := hm[2] + text2B := hm[3] + midCommon := hm[4] + // Send both pairs off for separate processing. + diffsA := dmp.diffMainRunes(text1A, text2A, checklines, deadline) + diffsB := dmp.diffMainRunes(text1B, text2B, checklines, deadline) + // Merge the results. + return append(diffsA, append([]Diff{Diff{DiffEqual, string(midCommon)}}, diffsB...)...) + } 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 + countDelete := 0 + countInsert := 0 + + // NOTE: Rune slices are slower than using strings in this case. + textDelete := "" + textInsert := "" + + for pointer < len(diffs) { + switch diffs[pointer].Type { + case DiffInsert: + countInsert++ + textInsert += diffs[pointer].Text + case DiffDelete: + countDelete++ + textDelete += diffs[pointer].Text + case DiffEqual: + // Upon reaching an equality, check for prior redundancies. + if countDelete >= 1 && countInsert >= 1 { + // Delete the offending records and add the merged ones. + diffs = splice(diffs, pointer-countDelete-countInsert, + countDelete+countInsert) + + pointer = pointer - countDelete - countInsert + a := dmp.diffMainRunes([]rune(textDelete), []rune(textInsert), false, deadline) + for j := len(a) - 1; j >= 0; j-- { + diffs = splice(diffs, pointer, 0, a[j]) + } + pointer = pointer + len(a) + } + + countInsert = 0 + countDelete = 0 + textDelete = "" + textInsert = "" + } + 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. + runes1Len, runes2Len := len(runes1), len(runes2) + + maxD := (runes1Len + runes2Len + 1) / 2 + vOffset := maxD + vLength := 2 * maxD + + v1 := make([]int, vLength) + v2 := make([]int, vLength) + for i := range v1 { + v1[i] = -1 + v2[i] = -1 + } + v1[vOffset+1] = 0 + v2[vOffset+1] = 0 + + delta := runes1Len - runes2Len + // 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 < maxD; d++ { + // Bail out if deadline is reached. + if !deadline.IsZero() && time.Now().After(deadline) { + break + } + + // Walk the front path one step. + for k1 := -d + k1start; k1 <= d-k1end; k1 += 2 { + k1Offset := vOffset + k1 + var x1 int + + if k1 == -d || (k1 != d && v1[k1Offset-1] < v1[k1Offset+1]) { + x1 = v1[k1Offset+1] + } else { + x1 = v1[k1Offset-1] + 1 + } + + y1 := x1 - k1 + for x1 < runes1Len && y1 < runes2Len { + if runes1[x1] != runes2[y1] { + break + } + x1++ + y1++ + } + v1[k1Offset] = x1 + if x1 > runes1Len { + // Ran off the right of the graph. + k1end += 2 + } else if y1 > runes2Len { + // Ran off the bottom of the graph. + k1start += 2 + } else if front { + k2Offset := vOffset + delta - k1 + if k2Offset >= 0 && k2Offset < vLength && v2[k2Offset] != -1 { + // Mirror x2 onto top-left coordinate system. + x2 := runes1Len - v2[k2Offset] + 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 { + k2Offset := vOffset + k2 + var x2 int + if k2 == -d || (k2 != d && v2[k2Offset-1] < v2[k2Offset+1]) { + x2 = v2[k2Offset+1] + } else { + x2 = v2[k2Offset-1] + 1 + } + var y2 = x2 - k2 + for x2 < runes1Len && y2 < runes2Len { + if runes1[runes1Len-x2-1] != runes2[runes2Len-y2-1] { + break + } + x2++ + y2++ + } + v2[k2Offset] = x2 + if x2 > runes1Len { + // Ran off the left of the graph. + k2end += 2 + } else if y2 > runes2Len { + // Ran off the top of the graph. + k2start += 2 + } else if !front { + k1Offset := vOffset + delta - k2 + if k1Offset >= 0 && k1Offset < vLength && v1[k1Offset] != -1 { + x1 := v1[k1Offset] + y1 := vOffset + x1 - k1Offset + // Mirror x2 onto top-left coordinate system. + x2 = runes1Len - 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 splits 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. + text1Length := len(text1) + text2Length := len(text2) + // Eliminate the null case. + if text1Length == 0 || text2Length == 0 { + return 0 + } + // Truncate the longer string. + if text1Length > text2Length { + text1 = text1[text1Length-text2Length:] + } else if text1Length < text2Length { + text2 = text2[0:text1Length] + } + textLength := int(math.Min(float64(text1Length), float64(text2Length))) + // Quick check for the worst case. + if text1 == text2 { + return textLength + } + + // 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[textLength-length:] + found := strings.Index(text2, pattern) + if found == -1 { + break + } + length += found + if found == 0 || text1[textLength-length:] == text2[0:length] { + best = length + length++ + } + } + + return best +} + +// 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 + } + + return [][]rune{hm[2], hm[3], hm[0], hm[1], hm[4]} +} + +// diffHalfMatchI checks if 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.<string>} 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. +func (dmp *DiffMatchPatch) diffHalfMatchI(l, s []rune, i int) [][]rune { + var bestCommonA []rune + var bestCommonB []rune + var bestCommonLen int + var bestLongtextA []rune + var bestLongtextB []rune + var bestShorttextA []rune + var bestShorttextB []rune + + // Start with a 1/4 length substring at position i as a seed. + seed := l[i : i+len(l)/4] + + for j := runesIndexOf(s, seed, 0); j != -1; j = runesIndexOf(s, seed, j+1) { + prefixLength := commonPrefixLength(l[i:], s[j:]) + suffixLength := commonSuffixLength(l[:i], s[:j]) + + if bestCommonLen < suffixLength+prefixLength { + bestCommonA = s[j-suffixLength : j] + bestCommonB = s[j : j+prefixLength] + bestCommonLen = len(bestCommonA) + len(bestCommonB) + bestLongtextA = l[:i-suffixLength] + bestLongtextB = l[i+prefixLength:] + bestShorttextA = s[:j-suffixLength] + bestShorttextB = s[j+prefixLength:] + } + } + + if bestCommonLen*2 < len(l) { + return nil + } + + return [][]rune{ + bestLongtextA, + bestLongtextB, + bestShorttextA, + bestShorttextB, + append(bestCommonA, bestCommonB...), + } +} + +// DiffCleanupSemantic reduces the number of edits by eliminating +// semantically trivial equalities. +func (dmp *DiffMatchPatch) DiffCleanupSemantic(diffs []Diff) []Diff { + changes := false + // Stack of indices where equalities are found. + type equality struct { + data int + next *equality + } + var equalities *equality + + 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 lengthInsertions1, lengthDeletions1 int + // Number of characters that changed after the equality. + var lengthInsertions2, lengthDeletions2 int + + for pointer < len(diffs) { + if diffs[pointer].Type == DiffEqual { // Equality found. + equalities = &equality{ + data: pointer, + next: equalities, + } + lengthInsertions1 = lengthInsertions2 + lengthDeletions1 = lengthDeletions2 + lengthInsertions2 = 0 + lengthDeletions2 = 0 + lastequality = diffs[pointer].Text + } else { // An insertion or deletion. + if diffs[pointer].Type == DiffInsert { + lengthInsertions2 += len(diffs[pointer].Text) + } else { + lengthDeletions2 += 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(lengthInsertions1), float64(lengthDeletions1))) + difference2 := int(math.Max(float64(lengthInsertions2), float64(lengthDeletions2))) + if len(lastequality) > 0 && + (len(lastequality) <= difference1) && + (len(lastequality) <= difference2) { + // Duplicate record. + insPoint := equalities.data + 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 = equalities.next + + if equalities != nil { + equalities = equalities.next + } + if equalities != nil { + pointer = equalities.data + } else { + pointer = -1 + } + + lengthInsertions1 = 0 // Reset the counters. + lengthDeletions1 = 0 + lengthInsertions2 = 0 + lengthDeletions2 = 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: <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 + for pointer < len(diffs) { + if diffs[pointer-1].Type == DiffDelete && + diffs[pointer].Type == DiffInsert { + deletion := diffs[pointer-1].Text + insertion := diffs[pointer].Text + overlapLength1 := dmp.DiffCommonOverlap(deletion, insertion) + overlapLength2 := dmp.DiffCommonOverlap(insertion, deletion) + if overlapLength1 >= overlapLength2 { + if float64(overlapLength1) >= float64(len(deletion))/2 || + float64(overlapLength1) >= float64(len(insertion))/2 { + + // Overlap found. Insert an equality and trim the surrounding edits. + diffs = append( + diffs[:pointer], + append([]Diff{Diff{DiffEqual, insertion[:overlapLength1]}}, diffs[pointer:]...)...) + //diffs.splice(pointer, 0, + // [DiffEqual, insertion[0 : overlapLength1)]] + diffs[pointer-1].Text = + deletion[0 : len(deletion)-overlapLength1] + diffs[pointer+1].Text = insertion[overlapLength1:] + pointer++ + } + } else { + if float64(overlapLength2) >= float64(len(deletion))/2 || + float64(overlapLength2) >= float64(len(insertion))/2 { + // Reverse overlap found. + // Insert an equality and swap and trim the surrounding edits. + overlap := Diff{DiffEqual, deletion[:overlapLength2]} + diffs = append( + diffs[:pointer], + append([]Diff{overlap}, diffs[pointer:]...)...) + // diffs.splice(pointer, 0, + // [DiffEqual, deletion[0 : overlapLength2)]] + diffs[pointer-1].Type = DiffInsert + diffs[pointer-1].Text = insertion[0 : len(insertion)-overlapLength2] + diffs[pointer+1].Type = DiffDelete + diffs[pointer+1].Text = deletion[overlapLength2:] + pointer++ + } + } + pointer++ + } + pointer++ + } + + return diffs +} + +// DiffCleanupSemanticLossless 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 c<ins>at c</ins>ame. -> The <ins>cat </ins>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 +} + +// DiffCleanupEfficiency 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. + type equality struct { + data int + next *equality + } + var equalities *equality + // Always equal to equalities[equalitiesLength-1][1] + lastequality := "" + pointer := 0 // Index of current position. + // Is there an insertion operation before the last equality. + preIns := false + // Is there a deletion operation before the last equality. + preDel := false + // Is there an insertion operation after the last equality. + postIns := false + // Is there a deletion operation after the last equality. + postDel := false + for pointer < len(diffs) { + if diffs[pointer].Type == DiffEqual { // Equality found. + if len(diffs[pointer].Text) < dmp.DiffEditCost && + (postIns || postDel) { + // Candidate found. + equalities = &equality{ + data: pointer, + next: equalities, + } + preIns = postIns + preDel = postDel + lastequality = diffs[pointer].Text + } else { + // Not a candidate, and can never become one. + equalities = nil + lastequality = "" + } + postIns = false + postDel = false + } else { // An insertion or deletion. + if diffs[pointer].Type == DiffDelete { + postDel = true + } else { + postIns = 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> + */ + var sumPres int + if preIns { + sumPres++ + } + if preDel { + sumPres++ + } + if postIns { + sumPres++ + } + if postDel { + sumPres++ + } + if len(lastequality) > 0 && + ((preIns && preDel && postIns && postDel) || + ((len(lastequality) < dmp.DiffEditCost/2) && sumPres == 3)) { + + insPoint := equalities.data + + // Duplicate record. + 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 = equalities.next + lastequality = "" + + if preIns && preDel { + // No changes made which could affect previous entry, keep going. + postIns = true + postDel = true + equalities = nil + } else { + if equalities != nil { + equalities = equalities.next + } + if equalities != nil { + pointer = equalities.data + } else { + pointer = -1 + } + postIns = false + postDel = false + } + changes = true + } + } + pointer++ + } + + if changes { + diffs = dmp.DiffCleanupMerge(diffs) + } + + return diffs +} + +// DiffCleanupMerge 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 + countDelete := 0 + countInsert := 0 + commonlength := 0 + textDelete := []rune(nil) + textInsert := []rune(nil) + + for pointer < len(diffs) { + switch diffs[pointer].Type { + case DiffInsert: + countInsert++ + textInsert = append(textInsert, []rune(diffs[pointer].Text)...) + pointer++ + break + case DiffDelete: + countDelete++ + textDelete = append(textDelete, []rune(diffs[pointer].Text)...) + pointer++ + break + case DiffEqual: + // Upon reaching an equality, check for prior redundancies. + if countDelete+countInsert > 1 { + if countDelete != 0 && countInsert != 0 { + // Factor out any common prefixies. + commonlength = commonPrefixLength(textInsert, textDelete) + if commonlength != 0 { + x := pointer - countDelete - countInsert + if x > 0 && diffs[x-1].Type == DiffEqual { + diffs[x-1].Text += string(textInsert[:commonlength]) + } else { + diffs = append([]Diff{Diff{DiffEqual, string(textInsert[:commonlength])}}, diffs...) + pointer++ + } + textInsert = textInsert[commonlength:] + textDelete = textDelete[commonlength:] + } + // Factor out any common suffixies. + commonlength = commonSuffixLength(textInsert, textDelete) + if commonlength != 0 { + insertIndex := len(textInsert) - commonlength + deleteIndex := len(textDelete) - commonlength + diffs[pointer].Text = string(textInsert[insertIndex:]) + diffs[pointer].Text + textInsert = textInsert[:insertIndex] + textDelete = textDelete[:deleteIndex] + } + } + // Delete the offending records and add the merged ones. + if countDelete == 0 { + diffs = splice(diffs, pointer-countInsert, + countDelete+countInsert, + Diff{DiffInsert, string(textInsert)}) + } else if countInsert == 0 { + diffs = splice(diffs, pointer-countDelete, + countDelete+countInsert, + Diff{DiffDelete, string(textDelete)}) + } else { + diffs = splice(diffs, pointer-countDelete-countInsert, + countDelete+countInsert, + Diff{DiffDelete, string(textDelete)}, + Diff{DiffInsert, string(textInsert)}) + } + + pointer = pointer - countDelete - countInsert + 1 + if countDelete != 0 { + pointer++ + } + if countInsert != 0 { + pointer++ + } + } 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++ + } + countInsert = 0 + countDelete = 0 + textDelete = nil + textInsert = nil + 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: A<ins>BA</ins>C -> <ins>AB</ins>AC + 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 +} + +// DiffXIndex returns the equivalent location in s2. +// 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 + lastChars1 := 0 + lastChars2 := 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 + } + lastChars1 = chars1 + lastChars2 = chars2 + } + if lastDiff.Type == DiffDelete { + // The location was deleted. + return lastChars2 + } + // Add the remaining character length. + return lastChars2 + (loc - lastChars1) +} + +// 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", "¶<br>", -1) + switch diff.Type { + case DiffInsert: + _, _ = buff.WriteString("<ins style=\"background:#e6ffe6;\">") + _, _ = buff.WriteString(text) + _, _ = buff.WriteString("</ins>") + case DiffDelete: + _, _ = buff.WriteString("<del style=\"background:#ffe6e6;\">") + _, _ = buff.WriteString(text) + _, _ = buff.WriteString("</del>") + case DiffEqual: + _, _ = buff.WriteString("<span>") + _, _ = buff.WriteString(text) + _, _ = buff.WriteString("</span>") + } + } + return buff.String() +} + +// DiffPrettyText converts a []Diff into a colored text report. +func (dmp *DiffMatchPatch) DiffPrettyText(diffs []Diff) string { + var buff bytes.Buffer + for _, diff := range diffs { + text := diff.Text + + switch diff.Type { + case DiffInsert: + _, _ = buff.WriteString("\x1b[32m") + _, _ = buff.WriteString(text) + _, _ = buff.WriteString("\x1b[0m") + case DiffDelete: + _, _ = buff.WriteString("\x1b[31m") + _, _ = buff.WriteString(text) + _, _ = buff.WriteString("\x1b[0m") + case DiffEqual: + _, _ = buff.WriteString(text) + } + } + + return buff.String() +} + +// DiffText1 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() +} + +// DiffText2 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() +} + +// DiffLevenshtein 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 +} + +// DiffToDelta 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 +} + +// DiffFromDelta 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 +}
diff --git a/diffmatchpatch/diff_test.go b/diffmatchpatch/diff_test.go new file mode 100644 index 0000000..5b7de57 --- /dev/null +++ b/diffmatchpatch/diff_test.go
@@ -0,0 +1,1373 @@ +// Copyright (c) 2012-2016 The go-diff authors. All rights reserved. +// https://github.com/sergi/go-diff +// See the included LICENSE file for license details. +// +// go-diff is a Go implementation of Google's Diff, Match, and Patch library +// Original library is Copyright (c) 2006 Google Inc. +// http://code.google.com/p/google-diff-match-patch/ + +package diffmatchpatch + +import ( + "fmt" + "strconv" + "strings" + "testing" + "time" + "unicode/utf8" + + "github.com/stretchr/testify/assert" +) + +func TestDiffCommonPrefix(t *testing.T) { + type TestCase struct { + Name string + + Text1 string + Text2 string + + Expected int + } + + dmp := New() + + for i, tc := range []TestCase{ + {"Null", "abc", "xyz", 0}, + {"Non-null", "1234abcdef", "1234xyz", 4}, + {"Whole", "1234", "1234xyz", 4}, + } { + actual := dmp.DiffCommonPrefix(tc.Text1, tc.Text2) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func BenchmarkDiffCommonPrefix(b *testing.B) { + s := "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ" + + dmp := New() + + for i := 0; i < b.N; i++ { + dmp.DiffCommonPrefix(s, s) + } +} + +func TestCommonPrefixLength(t *testing.T) { + type TestCase struct { + Text1 string + Text2 string + + Expected int + } + + for i, tc := range []TestCase{ + {"abc", "xyz", 0}, + {"1234abcdef", "1234xyz", 4}, + {"1234", "1234xyz", 4}, + } { + actual := commonPrefixLength([]rune(tc.Text1), []rune(tc.Text2)) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func TestDiffCommonSuffix(t *testing.T) { + type TestCase struct { + Name string + + Text1 string + Text2 string + + Expected int + } + + dmp := New() + + for i, tc := range []TestCase{ + {"Null", "abc", "xyz", 0}, + {"Non-null", "abcdef1234", "xyz1234", 4}, + {"Whole", "1234", "xyz1234", 4}, + } { + actual := dmp.DiffCommonSuffix(tc.Text1, tc.Text2) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func BenchmarkDiffCommonSuffix(b *testing.B) { + s := "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ" + + dmp := New() + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + dmp.DiffCommonSuffix(s, s) + } +} + +func TestCommonSuffixLength(t *testing.T) { + type TestCase struct { + Text1 string + Text2 string + + Expected int + } + + for i, tc := range []TestCase{ + {"abc", "xyz", 0}, + {"abcdef1234", "xyz1234", 4}, + {"1234", "xyz1234", 4}, + {"123", "a3", 1}, + } { + actual := commonSuffixLength([]rune(tc.Text1), []rune(tc.Text2)) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func TestDiffCommonOverlap(t *testing.T) { + type TestCase struct { + Name string + + Text1 string + Text2 string + + Expected int + } + + dmp := New() + + for i, tc := range []TestCase{ + {"Null", "", "abcd", 0}, + {"Whole", "abc", "abcd", 3}, + {"Null", "123456", "abcd", 0}, + {"Null", "123456xxx", "xxxabcd", 3}, + // Some overly clever languages (C#) may treat ligatures as equal to their component letters, e.g. U+FB01 == 'fi' + {"Unicode", "fi", "\ufb01i", 0}, + } { + actual := dmp.DiffCommonOverlap(tc.Text1, tc.Text2) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func TestDiffHalfMatch(t *testing.T) { + type TestCase struct { + Text1 string + Text2 string + + Expected []string + } + + dmp := New() + dmp.DiffTimeout = 1 + + for i, tc := range []TestCase{ + // No match + {"1234567890", "abcdef", nil}, + {"12345", "23", nil}, + + // Single Match + {"1234567890", "a345678z", []string{"12", "90", "a", "z", "345678"}}, + {"a345678z", "1234567890", []string{"a", "z", "12", "90", "345678"}}, + {"abc56789z", "1234567890", []string{"abc", "z", "1234", "0", "56789"}}, + {"a23456xyz", "1234567890", []string{"a", "xyz", "1", "7890", "23456"}}, + + // Multiple Matches + {"121231234123451234123121", "a1234123451234z", []string{"12123", "123121", "a", "z", "1234123451234"}}, + {"x-=-=-=-=-=-=-=-=-=-=-=-=", "xx-=-=-=-=-=-=-=", []string{"", "-=-=-=-=-=", "x", "", "x-=-=-=-=-=-=-="}}, + {"-=-=-=-=-=-=-=-=-=-=-=-=y", "-=-=-=-=-=-=-=yy", []string{"-=-=-=-=-=", "", "", "y", "-=-=-=-=-=-=-=y"}}, + + // Non-optimal halfmatch, ptimal diff would be -q+x=H-i+e=lloHe+Hu=llo-Hew+y not -qHillo+x=HelloHe-w+Hulloy + {"qHilloHelloHew", "xHelloHeHulloy", []string{"qHillo", "w", "x", "Hulloy", "HelloHe"}}, + } { + actual := dmp.DiffHalfMatch(tc.Text1, tc.Text2) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } + + dmp.DiffTimeout = 0 + + for i, tc := range []TestCase{ + // Optimal no halfmatch + {"qHilloHelloHew", "xHelloHeHulloy", nil}, + } { + actual := dmp.DiffHalfMatch(tc.Text1, tc.Text2) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func BenchmarkDiffHalfMatch(b *testing.B) { + s1, s2 := speedtestTexts() + + dmp := New() + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + dmp.DiffHalfMatch(s1, s2) + } +} + +func TestDiffBisectSplit(t *testing.T) { + type TestCase struct { + Text1 string + Text2 string + } + + dmp := New() + + for _, tc := range []TestCase{ + {"STUV\x05WX\x05YZ\x05[", "WĺĻļ\x05YZ\x05ĽľĿŀZ"}, + } { + diffs := dmp.diffBisectSplit([]rune(tc.Text1), + []rune(tc.Text2), 7, 6, time.Now().Add(time.Hour)) + + for _, d := range diffs { + assert.True(t, utf8.ValidString(d.Text)) + } + + // TODO define the expected outcome + } +} + +func TestDiffLinesToChars(t *testing.T) { + type TestCase struct { + Text1 string + Text2 string + + ExpectedChars1 string + ExpectedChars2 string + ExpectedLines []string + } + + dmp := New() + + for i, tc := range []TestCase{ + {"", "alpha\r\nbeta\r\n\r\n\r\n", "", "\u0001\u0002\u0003\u0003", []string{"", "alpha\r\n", "beta\r\n", "\r\n"}}, + {"a", "b", "\u0001", "\u0002", []string{"", "a", "b"}}, + // Omit final newline. + {"alpha\nbeta\nalpha", "", "\u0001\u0002\u0003", "", []string{"", "alpha\n", "beta\n", "alpha"}}, + } { + actualChars1, actualChars2, actualLines := dmp.DiffLinesToChars(tc.Text1, tc.Text2) + assert.Equal(t, tc.ExpectedChars1, actualChars1, fmt.Sprintf("Test case #%d, %#v", i, tc)) + assert.Equal(t, tc.ExpectedChars2, actualChars2, fmt.Sprintf("Test case #%d, %#v", i, tc)) + assert.Equal(t, tc.ExpectedLines, actualLines, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } + + // More than 256 to reveal any 8-bit limitations. + n := 300 + lineList := []string{ + "", // Account for the initial empty element of the lines array. + } + var charList []rune + for x := 1; x < n+1; x++ { + lineList = append(lineList, strconv.Itoa(x)+"\n") + charList = append(charList, rune(x)) + } + lines := strings.Join(lineList, "") + chars := string(charList) + assert.Equal(t, n, utf8.RuneCountInString(chars)) + + actualChars1, actualChars2, actualLines := dmp.DiffLinesToChars(lines, "") + assert.Equal(t, chars, actualChars1) + assert.Equal(t, "", actualChars2) + assert.Equal(t, lineList, actualLines) +} + +func TestDiffCharsToLines(t *testing.T) { + type TestCase struct { + Diffs []Diff + Lines []string + + Expected []Diff + } + + dmp := New() + + for i, tc := range []TestCase{ + { + Diffs: []Diff{ + {DiffEqual, "\u0001\u0002\u0001"}, + {DiffInsert, "\u0002\u0001\u0002"}, + }, + Lines: []string{"", "alpha\n", "beta\n"}, + + Expected: []Diff{ + {DiffEqual, "alpha\nbeta\nalpha\n"}, + {DiffInsert, "beta\nalpha\nbeta\n"}, + }, + }, + } { + actual := dmp.DiffCharsToLines(tc.Diffs, tc.Lines) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } + + // More than 256 to reveal any 8-bit limitations. + n := 300 + lineList := []string{ + "", // Account for the initial empty element of the lines array. + } + charList := []rune{} + for x := 1; x <= n; x++ { + lineList = append(lineList, strconv.Itoa(x)+"\n") + charList = append(charList, rune(x)) + } + assert.Equal(t, n, len(charList)) + + actual := dmp.DiffCharsToLines([]Diff{Diff{DiffDelete, string(charList)}}, lineList) + assert.Equal(t, []Diff{Diff{DiffDelete, strings.Join(lineList, "")}}, actual) +} + +func TestDiffCleanupMerge(t *testing.T) { + type TestCase struct { + Name string + + Diffs []Diff + + Expected []Diff + } + + dmp := New() + + for i, tc := range []TestCase{ + { + "Null case", + []Diff{}, + []Diff{}, + }, + { + "No Diff case", + []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffInsert, "c"}}, + []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffInsert, "c"}}, + }, + { + "Merge equalities", + []Diff{Diff{DiffEqual, "a"}, Diff{DiffEqual, "b"}, Diff{DiffEqual, "c"}}, + []Diff{Diff{DiffEqual, "abc"}}, + }, + { + "Merge deletions", + []Diff{Diff{DiffDelete, "a"}, Diff{DiffDelete, "b"}, Diff{DiffDelete, "c"}}, + []Diff{Diff{DiffDelete, "abc"}}, + }, + { + "Merge insertions", + []Diff{Diff{DiffInsert, "a"}, Diff{DiffInsert, "b"}, Diff{DiffInsert, "c"}}, + []Diff{Diff{DiffInsert, "abc"}}, + }, + { + "Merge interweave", + []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "b"}, Diff{DiffDelete, "c"}, Diff{DiffInsert, "d"}, Diff{DiffEqual, "e"}, Diff{DiffEqual, "f"}}, + []Diff{Diff{DiffDelete, "ac"}, Diff{DiffInsert, "bd"}, Diff{DiffEqual, "ef"}}, + }, + { + "Prefix and suffix detection", + []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "abc"}, Diff{DiffDelete, "dc"}}, + []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "c"}}, + }, + { + "Prefix and suffix detection with equalities", + []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "a"}, Diff{DiffInsert, "abc"}, Diff{DiffDelete, "dc"}, Diff{DiffEqual, "y"}}, + []Diff{Diff{DiffEqual, "xa"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "cy"}}, + }, + { + "Same test as above but with unicode (\u0101 will appear in diffs with at least 257 unique lines)", + []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "\u0101"}, Diff{DiffInsert, "\u0101bc"}, Diff{DiffDelete, "dc"}, Diff{DiffEqual, "y"}}, + []Diff{Diff{DiffEqual, "x\u0101"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "cy"}}, + }, + { + "Slide edit left", + []Diff{Diff{DiffEqual, "a"}, Diff{DiffInsert, "ba"}, Diff{DiffEqual, "c"}}, + []Diff{Diff{DiffInsert, "ab"}, Diff{DiffEqual, "ac"}}, + }, + { + "Slide edit right", + []Diff{Diff{DiffEqual, "c"}, Diff{DiffInsert, "ab"}, Diff{DiffEqual, "a"}}, + []Diff{Diff{DiffEqual, "ca"}, Diff{DiffInsert, "ba"}}, + }, + { + "Slide edit left recursive", + []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffEqual, "c"}, Diff{DiffDelete, "ac"}, Diff{DiffEqual, "x"}}, + []Diff{Diff{DiffDelete, "abc"}, Diff{DiffEqual, "acx"}}, + }, + { + "Slide edit right recursive", + []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "ca"}, Diff{DiffEqual, "c"}, Diff{DiffDelete, "b"}, Diff{DiffEqual, "a"}}, + []Diff{Diff{DiffEqual, "xca"}, Diff{DiffDelete, "cba"}}, + }, + } { + actual := dmp.DiffCleanupMerge(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func TestDiffCleanupSemanticLossless(t *testing.T) { + type TestCase struct { + Name string + + Diffs []Diff + + Expected []Diff + } + + dmp := New() + + for i, tc := range []TestCase{ + { + "Null case", + []Diff{}, + []Diff{}, + }, + { + "Blank lines", + []Diff{ + Diff{DiffEqual, "AAA\r\n\r\nBBB"}, + Diff{DiffInsert, "\r\nDDD\r\n\r\nBBB"}, + Diff{DiffEqual, "\r\nEEE"}, + }, + []Diff{ + Diff{DiffEqual, "AAA\r\n\r\n"}, + Diff{DiffInsert, "BBB\r\nDDD\r\n\r\n"}, + Diff{DiffEqual, "BBB\r\nEEE"}, + }, + }, + { + "Line boundaries", + []Diff{ + Diff{DiffEqual, "AAA\r\nBBB"}, + Diff{DiffInsert, " DDD\r\nBBB"}, + Diff{DiffEqual, " EEE"}, + }, + []Diff{ + Diff{DiffEqual, "AAA\r\n"}, + Diff{DiffInsert, "BBB DDD\r\n"}, + Diff{DiffEqual, "BBB EEE"}, + }, + }, + { + "Word boundaries", + []Diff{ + Diff{DiffEqual, "The c"}, + Diff{DiffInsert, "ow and the c"}, + Diff{DiffEqual, "at."}, + }, + []Diff{ + Diff{DiffEqual, "The "}, + Diff{DiffInsert, "cow and the "}, + Diff{DiffEqual, "cat."}, + }, + }, + { + "Alphanumeric boundaries", + []Diff{ + Diff{DiffEqual, "The-c"}, + Diff{DiffInsert, "ow-and-the-c"}, + Diff{DiffEqual, "at."}, + }, + []Diff{ + Diff{DiffEqual, "The-"}, + Diff{DiffInsert, "cow-and-the-"}, + Diff{DiffEqual, "cat."}, + }, + }, + { + "Hitting the start", + []Diff{ + Diff{DiffEqual, "a"}, + Diff{DiffDelete, "a"}, + Diff{DiffEqual, "ax"}, + }, + []Diff{ + Diff{DiffDelete, "a"}, + Diff{DiffEqual, "aax"}, + }, + }, + { + "Hitting the end", + []Diff{ + Diff{DiffEqual, "xa"}, + Diff{DiffDelete, "a"}, + Diff{DiffEqual, "a"}, + }, + []Diff{ + Diff{DiffEqual, "xaa"}, + Diff{DiffDelete, "a"}, + }, + }, + { + "Sentence boundaries", + []Diff{ + Diff{DiffEqual, "The xxx. The "}, + Diff{DiffInsert, "zzz. The "}, + Diff{DiffEqual, "yyy."}, + }, + []Diff{ + Diff{DiffEqual, "The xxx."}, + Diff{DiffInsert, " The zzz."}, + Diff{DiffEqual, " The yyy."}, + }, + }, + { + "UTF-8 strings", + []Diff{ + Diff{DiffEqual, "The ♕. The "}, + Diff{DiffInsert, "♔. The "}, + Diff{DiffEqual, "♖."}, + }, + []Diff{ + Diff{DiffEqual, "The ♕."}, + Diff{DiffInsert, " The ♔."}, + Diff{DiffEqual, " The ♖."}, + }, + }, + { + "Rune boundaries", + []Diff{ + Diff{DiffEqual, "♕♕"}, + Diff{DiffInsert, "♔♔"}, + Diff{DiffEqual, "♖♖"}, + }, + []Diff{ + Diff{DiffEqual, "♕♕"}, + Diff{DiffInsert, "♔♔"}, + Diff{DiffEqual, "♖♖"}, + }, + }, + } { + actual := dmp.DiffCleanupSemanticLossless(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func TestDiffCleanupSemantic(t *testing.T) { + type TestCase struct { + Name string + + Diffs []Diff + + Expected []Diff + } + + dmp := New() + + for i, tc := range []TestCase{ + { + "Null case", + []Diff{}, + []Diff{}, + }, + { + "No elimination #1", + []Diff{ + {DiffDelete, "ab"}, + {DiffInsert, "cd"}, + {DiffEqual, "12"}, + {DiffDelete, "e"}, + }, + []Diff{ + {DiffDelete, "ab"}, + {DiffInsert, "cd"}, + {DiffEqual, "12"}, + {DiffDelete, "e"}, + }, + }, + { + "No elimination #2", + []Diff{ + {DiffDelete, "abc"}, + {DiffInsert, "ABC"}, + {DiffEqual, "1234"}, + {DiffDelete, "wxyz"}, + }, + []Diff{ + {DiffDelete, "abc"}, + {DiffInsert, "ABC"}, + {DiffEqual, "1234"}, + {DiffDelete, "wxyz"}, + }, + }, + { + "No elimination #3", + []Diff{ + {DiffEqual, "2016-09-01T03:07:1"}, + {DiffInsert, "5.15"}, + {DiffEqual, "4"}, + {DiffDelete, "."}, + {DiffEqual, "80"}, + {DiffInsert, "0"}, + {DiffEqual, "78"}, + {DiffDelete, "3074"}, + {DiffEqual, "1Z"}, + }, + []Diff{ + {DiffEqual, "2016-09-01T03:07:1"}, + {DiffInsert, "5.15"}, + {DiffEqual, "4"}, + {DiffDelete, "."}, + {DiffEqual, "80"}, + {DiffInsert, "0"}, + {DiffEqual, "78"}, + {DiffDelete, "3074"}, + {DiffEqual, "1Z"}, + }, + }, + { + "Simple elimination", + []Diff{ + {DiffDelete, "a"}, + {DiffEqual, "b"}, + {DiffDelete, "c"}, + }, + []Diff{ + {DiffDelete, "abc"}, + {DiffInsert, "b"}, + }, + }, + { + "Backpass elimination", + []Diff{ + {DiffDelete, "ab"}, + {DiffEqual, "cd"}, + {DiffDelete, "e"}, + {DiffEqual, "f"}, + {DiffInsert, "g"}, + }, + []Diff{ + {DiffDelete, "abcdef"}, + {DiffInsert, "cdfg"}, + }, + }, + { + "Multiple eliminations", + []Diff{ + {DiffInsert, "1"}, + {DiffEqual, "A"}, + {DiffDelete, "B"}, + {DiffInsert, "2"}, + {DiffEqual, "_"}, + {DiffInsert, "1"}, + {DiffEqual, "A"}, + {DiffDelete, "B"}, + {DiffInsert, "2"}, + }, + []Diff{ + {DiffDelete, "AB_AB"}, + {DiffInsert, "1A2_1A2"}, + }, + }, + { + "Word boundaries", + []Diff{ + {DiffEqual, "The c"}, + {DiffDelete, "ow and the c"}, + {DiffEqual, "at."}, + }, + []Diff{ + {DiffEqual, "The "}, + {DiffDelete, "cow and the "}, + {DiffEqual, "cat."}, + }, + }, + { + "No overlap elimination", + []Diff{ + {DiffDelete, "abcxx"}, + {DiffInsert, "xxdef"}, + }, + []Diff{ + {DiffDelete, "abcxx"}, + {DiffInsert, "xxdef"}, + }, + }, + { + "Overlap elimination", + []Diff{ + {DiffDelete, "abcxxx"}, + {DiffInsert, "xxxdef"}, + }, + []Diff{ + {DiffDelete, "abc"}, + {DiffEqual, "xxx"}, + {DiffInsert, "def"}, + }, + }, + { + "Reverse overlap elimination", + []Diff{ + {DiffDelete, "xxxabc"}, + {DiffInsert, "defxxx"}, + }, + []Diff{ + {DiffInsert, "def"}, + {DiffEqual, "xxx"}, + {DiffDelete, "abc"}, + }, + }, + { + "Two overlap eliminations", + []Diff{ + {DiffDelete, "abcd1212"}, + {DiffInsert, "1212efghi"}, + {DiffEqual, "----"}, + {DiffDelete, "A3"}, + {DiffInsert, "3BC"}, + }, + []Diff{ + {DiffDelete, "abcd"}, + {DiffEqual, "1212"}, + {DiffInsert, "efghi"}, + {DiffEqual, "----"}, + {DiffDelete, "A"}, + {DiffEqual, "3"}, + {DiffInsert, "BC"}, + }, + }, + { + "Test case for adapting DiffCleanupSemantic to be equal to the Python version #19", + []Diff{ + {DiffEqual, "James McCarthy "}, + {DiffDelete, "close to "}, + {DiffEqual, "sign"}, + {DiffDelete, "ing"}, + {DiffInsert, "s"}, + {DiffEqual, " new "}, + {DiffDelete, "E"}, + {DiffInsert, "fi"}, + {DiffEqual, "ve"}, + {DiffInsert, "-yea"}, + {DiffEqual, "r"}, + {DiffDelete, "ton"}, + {DiffEqual, " deal"}, + {DiffInsert, " at Everton"}, + }, + []Diff{ + {DiffEqual, "James McCarthy "}, + {DiffDelete, "close to "}, + {DiffEqual, "sign"}, + {DiffDelete, "ing"}, + {DiffInsert, "s"}, + {DiffEqual, " new "}, + {DiffInsert, "five-year deal at "}, + {DiffEqual, "Everton"}, + {DiffDelete, " deal"}, + }, + }, + } { + actual := dmp.DiffCleanupSemantic(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func BenchmarkDiffCleanupSemantic(b *testing.B) { + s1, s2 := speedtestTexts() + + dmp := New() + + diffs := dmp.DiffMain(s1, s2, false) + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + dmp.DiffCleanupSemantic(diffs) + } +} + +func TestDiffCleanupEfficiency(t *testing.T) { + type TestCase struct { + Name string + + Diffs []Diff + + Expected []Diff + } + + dmp := New() + dmp.DiffEditCost = 4 + + for i, tc := range []TestCase{ + { + "Null case", + []Diff{}, + []Diff{}, + }, + { + "No elimination", + []Diff{ + Diff{DiffDelete, "ab"}, + Diff{DiffInsert, "12"}, + Diff{DiffEqual, "wxyz"}, + Diff{DiffDelete, "cd"}, + Diff{DiffInsert, "34"}, + }, + []Diff{ + Diff{DiffDelete, "ab"}, + Diff{DiffInsert, "12"}, + Diff{DiffEqual, "wxyz"}, + Diff{DiffDelete, "cd"}, + Diff{DiffInsert, "34"}, + }, + }, + { + "Four-edit elimination", + []Diff{ + Diff{DiffDelete, "ab"}, + Diff{DiffInsert, "12"}, + Diff{DiffEqual, "xyz"}, + Diff{DiffDelete, "cd"}, + Diff{DiffInsert, "34"}, + }, + []Diff{ + Diff{DiffDelete, "abxyzcd"}, + Diff{DiffInsert, "12xyz34"}, + }, + }, + { + "Three-edit elimination", + []Diff{ + Diff{DiffInsert, "12"}, + Diff{DiffEqual, "x"}, + Diff{DiffDelete, "cd"}, + Diff{DiffInsert, "34"}, + }, + []Diff{ + Diff{DiffDelete, "xcd"}, + Diff{DiffInsert, "12x34"}, + }, + }, + { + "Backpass elimination", + []Diff{ + Diff{DiffDelete, "ab"}, + Diff{DiffInsert, "12"}, + Diff{DiffEqual, "xy"}, + Diff{DiffInsert, "34"}, + Diff{DiffEqual, "z"}, + Diff{DiffDelete, "cd"}, + Diff{DiffInsert, "56"}, + }, + []Diff{ + Diff{DiffDelete, "abxyzcd"}, + Diff{DiffInsert, "12xy34z56"}, + }, + }, + } { + actual := dmp.DiffCleanupEfficiency(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } + + dmp.DiffEditCost = 5 + + for i, tc := range []TestCase{ + { + "High cost elimination", + []Diff{ + Diff{DiffDelete, "ab"}, + Diff{DiffInsert, "12"}, + Diff{DiffEqual, "wxyz"}, + Diff{DiffDelete, "cd"}, + Diff{DiffInsert, "34"}, + }, + []Diff{ + Diff{DiffDelete, "abwxyzcd"}, + Diff{DiffInsert, "12wxyz34"}, + }, + }, + } { + actual := dmp.DiffCleanupEfficiency(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func TestDiffPrettyHtml(t *testing.T) { + type TestCase struct { + Diffs []Diff + + Expected string + } + + dmp := New() + + for i, tc := range []TestCase{ + { + Diffs: []Diff{ + {DiffEqual, "a\n"}, + {DiffDelete, "<B>b</B>"}, + {DiffInsert, "c&d"}, + }, + + Expected: "<span>a¶<br></span><del style=\"background:#ffe6e6;\"><B>b</B></del><ins style=\"background:#e6ffe6;\">c&d</ins>", + }, + } { + actual := dmp.DiffPrettyHtml(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func TestDiffPrettyText(t *testing.T) { + type TestCase struct { + Diffs []Diff + + Expected string + } + + dmp := New() + + for i, tc := range []TestCase{ + { + Diffs: []Diff{ + {DiffEqual, "a\n"}, + {DiffDelete, "<B>b</B>"}, + {DiffInsert, "c&d"}, + }, + + Expected: "a\n\x1b[31m<B>b</B>\x1b[0m\x1b[32mc&d\x1b[0m", + }, + } { + actual := dmp.DiffPrettyText(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func TestDiffText(t *testing.T) { + type TestCase struct { + Diffs []Diff + + ExpectedText1 string + ExpectedText2 string + } + + dmp := New() + + for i, tc := range []TestCase{ + { + Diffs: []Diff{ + {DiffEqual, "jump"}, + {DiffDelete, "s"}, + {DiffInsert, "ed"}, + {DiffEqual, " over "}, + {DiffDelete, "the"}, + {DiffInsert, "a"}, + {DiffEqual, " lazy"}, + }, + + ExpectedText1: "jumps over the lazy", + ExpectedText2: "jumped over a lazy", + }, + } { + actualText1 := dmp.DiffText1(tc.Diffs) + assert.Equal(t, tc.ExpectedText1, actualText1, fmt.Sprintf("Test case #%d, %#v", i, tc)) + + actualText2 := dmp.DiffText2(tc.Diffs) + assert.Equal(t, tc.ExpectedText2, actualText2, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func TestDiffDelta(t *testing.T) { + dmp := New() + + // Convert a diff into delta string. + diffs := []Diff{ + Diff{DiffEqual, "jump"}, + Diff{DiffDelete, "s"}, + Diff{DiffInsert, "ed"}, + Diff{DiffEqual, " over "}, + Diff{DiffDelete, "the"}, + Diff{DiffInsert, "a"}, + Diff{DiffEqual, " lazy"}, + Diff{DiffInsert, "old dog"}, + } + text1 := dmp.DiffText1(diffs) + assert.Equal(t, "jumps over the lazy", text1) + + delta := dmp.DiffToDelta(diffs) + assert.Equal(t, "=4\t-1\t+ed\t=6\t-3\t+a\t=5\t+old dog", delta) + + // Convert delta string into a diff. + deltaDiffs, err := dmp.DiffFromDelta(text1, delta) + assert.Equal(t, diffs, deltaDiffs) + + // Generates error (19 < 20). + _, err = dmp.DiffFromDelta(text1+"x", delta) + if err == nil { + t.Fatal("Too long.") + } + + // Generates error (19 > 18). + _, err = dmp.DiffFromDelta(text1[1:], delta) + if err == nil { + t.Fatal("Too short.") + } + + // Generates error (%xy invalid URL escape). + _, err = dmp.DiffFromDelta("", "+%c3%xy") + if err == nil { + assert.Fail(t, "expected Invalid URL escape.") + } + + // Generates error (invalid utf8). + _, err = dmp.DiffFromDelta("", "+%c3xy") + if err == nil { + assert.Fail(t, "expected Invalid utf8.") + } + + // Test deltas with special characters. + diffs = []Diff{ + Diff{DiffEqual, "\u0680 \x00 \t %"}, + Diff{DiffDelete, "\u0681 \x01 \n ^"}, + Diff{DiffInsert, "\u0682 \x02 \\ |"}, + } + text1 = dmp.DiffText1(diffs) + assert.Equal(t, "\u0680 \x00 \t %\u0681 \x01 \n ^", text1) + + // Lowercase, due to UrlEncode uses lower. + delta = dmp.DiffToDelta(diffs) + assert.Equal(t, "=7\t-7\t+%DA%82 %02 %5C %7C", delta) + + deltaDiffs, err = dmp.DiffFromDelta(text1, delta) + assert.Equal(t, diffs, deltaDiffs) + assert.Nil(t, err) + + // Verify pool of unchanged characters. + diffs = []Diff{ + Diff{DiffInsert, "A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # "}, + } + + delta = dmp.DiffToDelta(diffs) + assert.Equal(t, "+A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # ", delta, "Unchanged characters.") + + // Convert delta string into a diff. + deltaDiffs, err = dmp.DiffFromDelta("", delta) + assert.Equal(t, diffs, deltaDiffs) + assert.Nil(t, err) +} + +func TestDiffXIndex(t *testing.T) { + type TestCase struct { + Name string + + Diffs []Diff + Location int + + Expected int + } + + dmp := New() + + for i, tc := range []TestCase{ + {"Translation on equality", []Diff{{DiffDelete, "a"}, {DiffInsert, "1234"}, {DiffEqual, "xyz"}}, 2, 5}, + {"Translation on deletion", []Diff{{DiffEqual, "a"}, {DiffDelete, "1234"}, {DiffEqual, "xyz"}}, 3, 1}, + } { + actual := dmp.DiffXIndex(tc.Diffs, tc.Location) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func TestDiffLevenshtein(t *testing.T) { + type TestCase struct { + Name string + + Diffs []Diff + + Expected int + } + + dmp := New() + + for i, tc := range []TestCase{ + {"Levenshtein with trailing equality", []Diff{{DiffDelete, "abc"}, {DiffInsert, "1234"}, {DiffEqual, "xyz"}}, 4}, + {"Levenshtein with leading equality", []Diff{{DiffEqual, "xyz"}, {DiffDelete, "abc"}, {DiffInsert, "1234"}}, 4}, + {"Levenshtein with middle equality", []Diff{{DiffDelete, "abc"}, {DiffEqual, "xyz"}, {DiffInsert, "1234"}}, 7}, + } { + actual := dmp.DiffLevenshtein(tc.Diffs) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func TestDiffBisect(t *testing.T) { + type TestCase struct { + Name string + + Time time.Time + + Expected []Diff + } + + dmp := New() + + text1 := "cat" + text2 := "map" + + for i, tc := range []TestCase{ + { + Name: "normal", + Time: time.Date(9999, time.December, 31, 23, 59, 59, 59, time.UTC), + + Expected: []Diff{ + {DiffDelete, "c"}, + {DiffInsert, "m"}, + {DiffEqual, "a"}, + {DiffDelete, "t"}, + {DiffInsert, "p"}, + }, + }, + { + Name: "Negative deadlines count as having infinite time", + Time: time.Date(0001, time.January, 01, 00, 00, 00, 00, time.UTC), + + Expected: []Diff{ + {DiffDelete, "c"}, + {DiffInsert, "m"}, + {DiffEqual, "a"}, + {DiffDelete, "t"}, + {DiffInsert, "p"}, + }, + }, + { + Name: "Timeout", + Time: time.Now().Add(time.Nanosecond), + + Expected: []Diff{ + {DiffDelete, "cat"}, + {DiffInsert, "map"}, + }, + }, + } { + actual := dmp.DiffBisect(text1, text2, tc.Time) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) + } +} + +func TestDiffMain(t *testing.T) { + type TestCase struct { + Text1 string + Text2 string + + Expected []Diff + } + + dmp := New() + + // Perform a trivial diff. + for i, tc := range []TestCase{ + { + "", + "", + nil, + }, + { + "abc", + "abc", + []Diff{Diff{DiffEqual, "abc"}}, + }, + { + "abc", + "ab123c", + []Diff{Diff{DiffEqual, "ab"}, Diff{DiffInsert, "123"}, Diff{DiffEqual, "c"}}, + }, + { + "a123bc", + "abc", + []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "123"}, Diff{DiffEqual, "bc"}}, + }, + { + "abc", + "a123b456c", + []Diff{Diff{DiffEqual, "a"}, Diff{DiffInsert, "123"}, Diff{DiffEqual, "b"}, Diff{DiffInsert, "456"}, Diff{DiffEqual, "c"}}, + }, + { + "a123b456c", + "abc", + []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "123"}, Diff{DiffEqual, "b"}, Diff{DiffDelete, "456"}, Diff{DiffEqual, "c"}}, + }, + } { + actual := dmp.DiffMain(tc.Text1, tc.Text2, false) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } + + // Perform a real diff and switch off the timeout. + dmp.DiffTimeout = 0 + + for i, tc := range []TestCase{ + { + "a", + "b", + []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "b"}}, + }, + { + "Apples are a fruit.", + "Bananas are also fruit.", + []Diff{ + Diff{DiffDelete, "Apple"}, + Diff{DiffInsert, "Banana"}, + Diff{DiffEqual, "s are a"}, + Diff{DiffInsert, "lso"}, + Diff{DiffEqual, " fruit."}, + }, + }, + { + "ax\t", + "\u0680x\u0000", + []Diff{ + Diff{DiffDelete, "a"}, + Diff{DiffInsert, "\u0680"}, + Diff{DiffEqual, "x"}, + Diff{DiffDelete, "\t"}, + Diff{DiffInsert, "\u0000"}, + }, + }, + { + "1ayb2", + "abxab", + []Diff{ + Diff{DiffDelete, "1"}, + Diff{DiffEqual, "a"}, + Diff{DiffDelete, "y"}, + Diff{DiffEqual, "b"}, + Diff{DiffDelete, "2"}, + Diff{DiffInsert, "xab"}, + }, + }, + { + "abcy", + "xaxcxabc", + []Diff{ + Diff{DiffInsert, "xaxcx"}, + Diff{DiffEqual, "abc"}, Diff{DiffDelete, "y"}, + }, + }, + { + "ABCDa=bcd=efghijklmnopqrsEFGHIJKLMNOefg", + "a-bcd-efghijklmnopqrs", + []Diff{ + Diff{DiffDelete, "ABCD"}, + Diff{DiffEqual, "a"}, + Diff{DiffDelete, "="}, + Diff{DiffInsert, "-"}, + Diff{DiffEqual, "bcd"}, + Diff{DiffDelete, "="}, + Diff{DiffInsert, "-"}, + Diff{DiffEqual, "efghijklmnopqrs"}, + Diff{DiffDelete, "EFGHIJKLMNOefg"}, + }, + }, + { + "a [[Pennsylvania]] and [[New", + " and [[Pennsylvania]]", + []Diff{ + Diff{DiffInsert, " "}, + Diff{DiffEqual, "a"}, + Diff{DiffInsert, "nd"}, + Diff{DiffEqual, " [[Pennsylvania]]"}, + Diff{DiffDelete, " and [[New"}, + }, + }, + } { + actual := dmp.DiffMain(tc.Text1, tc.Text2, false) + assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func TestDiffMainWithTimeout(t *testing.T) { + dmp := New() + dmp.DiffTimeout = 200 * time.Millisecond + + a := "`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n" + b := "I am the very model of a modern major general,\nI've information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n" + // Increase the text lengths by 1024 times to ensure a timeout. + for x := 0; x < 13; x++ { + a = a + a + b = b + b + } + + startTime := time.Now() + dmp.DiffMain(a, b, true) + endTime := time.Now() + + delta := endTime.Sub(startTime) + + // Test that we took at least the timeout period. + assert.True(t, delta >= dmp.DiffTimeout, fmt.Sprintf("%v !>= %v", delta, dmp.DiffTimeout)) + + // Test that we didn't take forever (be very forgiving). + // Theoretically this test could fail very occasionally if the + // OS task swaps or locks up for a second at the wrong moment. + assert.True(t, delta < (dmp.DiffTimeout*100), fmt.Sprintf("%v !< %v", delta, dmp.DiffTimeout*100)) +} + +func TestDiffMainWithCheckLines(t *testing.T) { + type TestCase struct { + Text1 string + Text2 string + } + + dmp := New() + dmp.DiffTimeout = 0 + + // Test cases must be at least 100 chars long to pass the cutoff. + for i, tc := range []TestCase{ + { + "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n", + "abcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\n", + }, + { + "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", + "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij", + }, + { + "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n", + "abcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n", + }, + } { + resultWithoutCheckLines := dmp.DiffMain(tc.Text1, tc.Text2, false) + resultWithCheckLines := dmp.DiffMain(tc.Text1, tc.Text2, true) + + // TODO this fails for the third test case, why? + if i != 2 { + assert.Equal(t, resultWithoutCheckLines, resultWithCheckLines, fmt.Sprintf("Test case #%d, %#v", i, tc)) + } + assert.Equal(t, diffRebuildTexts(resultWithoutCheckLines), diffRebuildTexts(resultWithCheckLines), fmt.Sprintf("Test case #%d, %#v", i, tc)) + } +} + +func BenchmarkDiffMain(bench *testing.B) { + s1 := "`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n" + s2 := "I am the very model of a modern major general,\nI've information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n" + + // Increase the text lengths by 1024 times to ensure a timeout. + for x := 0; x < 10; x++ { + s1 = s1 + s1 + s2 = s2 + s2 + } + + dmp := New() + dmp.DiffTimeout = time.Second + + bench.ResetTimer() + + for i := 0; i < bench.N; i++ { + dmp.DiffMain(s1, s2, true) + } +} + +func BenchmarkDiffMainLarge(b *testing.B) { + s1, s2 := speedtestTexts() + + dmp := New() + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + dmp.DiffMain(s1, s2, true) + } +} + +func BenchmarkDiffMainRunesLargeLines(b *testing.B) { + s1, s2 := speedtestTexts() + + dmp := New() + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + text1, text2, linearray := dmp.DiffLinesToRunes(s1, s2) + + diffs := dmp.DiffMainRunes(text1, text2, false) + diffs = dmp.DiffCharsToLines(diffs, linearray) + } +}
diff --git a/diffmatchpatch/diffmatchpatch.go b/diffmatchpatch/diffmatchpatch.go index f2fb710..beb1339 100644 --- a/diffmatchpatch/diffmatchpatch.go +++ b/diffmatchpatch/diffmatchpatch.go
@@ -13,8 +13,6 @@ import ( "bytes" "errors" - "fmt" - "html" "math" "net/url" "regexp" @@ -242,1346 +240,6 @@ } } -// DiffMain finds the differences between two texts. -func (dmp *DiffMatchPatch) DiffMain(text1, text2 string, checklines bool) []Diff { - return dmp.DiffMainRunes([]rune(text1), []rune(text2), checklines) -} - -// 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(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. - text1A := hm[0] - text1B := hm[1] - text2A := hm[2] - text2B := hm[3] - midCommon := hm[4] - // Send both pairs off for separate processing. - diffsA := dmp.diffMainRunes(text1A, text2A, checklines, deadline) - diffsB := dmp.diffMainRunes(text1B, text2B, checklines, deadline) - // Merge the results. - return append(diffsA, append([]Diff{Diff{DiffEqual, string(midCommon)}}, diffsB...)...) - } 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 - countDelete := 0 - countInsert := 0 - - // NOTE: Rune slices are slower than using strings in this case. - textDelete := "" - textInsert := "" - - for pointer < len(diffs) { - switch diffs[pointer].Type { - case DiffInsert: - countInsert++ - textInsert += diffs[pointer].Text - case DiffDelete: - countDelete++ - textDelete += diffs[pointer].Text - case DiffEqual: - // Upon reaching an equality, check for prior redundancies. - if countDelete >= 1 && countInsert >= 1 { - // Delete the offending records and add the merged ones. - diffs = splice(diffs, pointer-countDelete-countInsert, - countDelete+countInsert) - - pointer = pointer - countDelete - countInsert - a := dmp.diffMainRunes([]rune(textDelete), []rune(textInsert), false, deadline) - for j := len(a) - 1; j >= 0; j-- { - diffs = splice(diffs, pointer, 0, a[j]) - } - pointer = pointer + len(a) - } - - countInsert = 0 - countDelete = 0 - textDelete = "" - textInsert = "" - } - 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. - runes1Len, runes2Len := len(runes1), len(runes2) - - maxD := (runes1Len + runes2Len + 1) / 2 - vOffset := maxD - vLength := 2 * maxD - - v1 := make([]int, vLength) - v2 := make([]int, vLength) - for i := range v1 { - v1[i] = -1 - v2[i] = -1 - } - v1[vOffset+1] = 0 - v2[vOffset+1] = 0 - - delta := runes1Len - runes2Len - // 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 < maxD; d++ { - // Bail out if deadline is reached. - if !deadline.IsZero() && time.Now().After(deadline) { - break - } - - // Walk the front path one step. - for k1 := -d + k1start; k1 <= d-k1end; k1 += 2 { - k1Offset := vOffset + k1 - var x1 int - - if k1 == -d || (k1 != d && v1[k1Offset-1] < v1[k1Offset+1]) { - x1 = v1[k1Offset+1] - } else { - x1 = v1[k1Offset-1] + 1 - } - - y1 := x1 - k1 - for x1 < runes1Len && y1 < runes2Len { - if runes1[x1] != runes2[y1] { - break - } - x1++ - y1++ - } - v1[k1Offset] = x1 - if x1 > runes1Len { - // Ran off the right of the graph. - k1end += 2 - } else if y1 > runes2Len { - // Ran off the bottom of the graph. - k1start += 2 - } else if front { - k2Offset := vOffset + delta - k1 - if k2Offset >= 0 && k2Offset < vLength && v2[k2Offset] != -1 { - // Mirror x2 onto top-left coordinate system. - x2 := runes1Len - v2[k2Offset] - 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 { - k2Offset := vOffset + k2 - var x2 int - if k2 == -d || (k2 != d && v2[k2Offset-1] < v2[k2Offset+1]) { - x2 = v2[k2Offset+1] - } else { - x2 = v2[k2Offset-1] + 1 - } - var y2 = x2 - k2 - for x2 < runes1Len && y2 < runes2Len { - if runes1[runes1Len-x2-1] != runes2[runes2Len-y2-1] { - break - } - x2++ - y2++ - } - v2[k2Offset] = x2 - if x2 > runes1Len { - // Ran off the left of the graph. - k2end += 2 - } else if y2 > runes2Len { - // Ran off the top of the graph. - k2start += 2 - } else if !front { - k1Offset := vOffset + delta - k2 - if k1Offset >= 0 && k1Offset < vLength && v1[k1Offset] != -1 { - x1 := v1[k1Offset] - y1 := vOffset + x1 - k1Offset - // Mirror x2 onto top-left coordinate system. - x2 = runes1Len - 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 splits 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. - text1Length := len(text1) - text2Length := len(text2) - // Eliminate the null case. - if text1Length == 0 || text2Length == 0 { - return 0 - } - // Truncate the longer string. - if text1Length > text2Length { - text1 = text1[text1Length-text2Length:] - } else if text1Length < text2Length { - text2 = text2[0:text1Length] - } - textLength := int(math.Min(float64(text1Length), float64(text2Length))) - // Quick check for the worst case. - if text1 == text2 { - return textLength - } - - // 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[textLength-length:] - found := strings.Index(text2, pattern) - if found == -1 { - break - } - length += found - if found == 0 || text1[textLength-length:] == text2[0:length] { - best = length - length++ - } - } - - return best -} - -// 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 - } - - return [][]rune{hm[2], hm[3], hm[0], hm[1], hm[4]} -} - -// diffHalfMatchI checks if 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.<string>} 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. -func (dmp *DiffMatchPatch) diffHalfMatchI(l, s []rune, i int) [][]rune { - var bestCommonA []rune - var bestCommonB []rune - var bestCommonLen int - var bestLongtextA []rune - var bestLongtextB []rune - var bestShorttextA []rune - var bestShorttextB []rune - - // Start with a 1/4 length substring at position i as a seed. - seed := l[i : i+len(l)/4] - - for j := runesIndexOf(s, seed, 0); j != -1; j = runesIndexOf(s, seed, j+1) { - prefixLength := commonPrefixLength(l[i:], s[j:]) - suffixLength := commonSuffixLength(l[:i], s[:j]) - - if bestCommonLen < suffixLength+prefixLength { - bestCommonA = s[j-suffixLength : j] - bestCommonB = s[j : j+prefixLength] - bestCommonLen = len(bestCommonA) + len(bestCommonB) - bestLongtextA = l[:i-suffixLength] - bestLongtextB = l[i+prefixLength:] - bestShorttextA = s[:j-suffixLength] - bestShorttextB = s[j+prefixLength:] - } - } - - if bestCommonLen*2 < len(l) { - return nil - } - - return [][]rune{ - bestLongtextA, - bestLongtextB, - bestShorttextA, - bestShorttextB, - append(bestCommonA, bestCommonB...), - } -} - -// DiffCleanupSemantic reduces the number of edits by eliminating -// semantically trivial equalities. -func (dmp *DiffMatchPatch) DiffCleanupSemantic(diffs []Diff) []Diff { - changes := false - // Stack of indices where equalities are found. - type equality struct { - data int - next *equality - } - var equalities *equality - - 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 lengthInsertions1, lengthDeletions1 int - // Number of characters that changed after the equality. - var lengthInsertions2, lengthDeletions2 int - - for pointer < len(diffs) { - if diffs[pointer].Type == DiffEqual { // Equality found. - equalities = &equality{ - data: pointer, - next: equalities, - } - lengthInsertions1 = lengthInsertions2 - lengthDeletions1 = lengthDeletions2 - lengthInsertions2 = 0 - lengthDeletions2 = 0 - lastequality = diffs[pointer].Text - } else { // An insertion or deletion. - if diffs[pointer].Type == DiffInsert { - lengthInsertions2 += len(diffs[pointer].Text) - } else { - lengthDeletions2 += 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(lengthInsertions1), float64(lengthDeletions1))) - difference2 := int(math.Max(float64(lengthInsertions2), float64(lengthDeletions2))) - if len(lastequality) > 0 && - (len(lastequality) <= difference1) && - (len(lastequality) <= difference2) { - // Duplicate record. - insPoint := equalities.data - 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 = equalities.next - - if equalities != nil { - equalities = equalities.next - } - if equalities != nil { - pointer = equalities.data - } else { - pointer = -1 - } - - lengthInsertions1 = 0 // Reset the counters. - lengthDeletions1 = 0 - lengthInsertions2 = 0 - lengthDeletions2 = 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: <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 - for pointer < len(diffs) { - if diffs[pointer-1].Type == DiffDelete && - diffs[pointer].Type == DiffInsert { - deletion := diffs[pointer-1].Text - insertion := diffs[pointer].Text - overlapLength1 := dmp.DiffCommonOverlap(deletion, insertion) - overlapLength2 := dmp.DiffCommonOverlap(insertion, deletion) - if overlapLength1 >= overlapLength2 { - if float64(overlapLength1) >= float64(len(deletion))/2 || - float64(overlapLength1) >= float64(len(insertion))/2 { - - // Overlap found. Insert an equality and trim the surrounding edits. - diffs = append( - diffs[:pointer], - append([]Diff{Diff{DiffEqual, insertion[:overlapLength1]}}, diffs[pointer:]...)...) - //diffs.splice(pointer, 0, - // [DiffEqual, insertion[0 : overlapLength1)]] - diffs[pointer-1].Text = - deletion[0 : len(deletion)-overlapLength1] - diffs[pointer+1].Text = insertion[overlapLength1:] - pointer++ - } - } else { - if float64(overlapLength2) >= float64(len(deletion))/2 || - float64(overlapLength2) >= float64(len(insertion))/2 { - // Reverse overlap found. - // Insert an equality and swap and trim the surrounding edits. - overlap := Diff{DiffEqual, deletion[:overlapLength2]} - diffs = append( - diffs[:pointer], - append([]Diff{overlap}, diffs[pointer:]...)...) - // diffs.splice(pointer, 0, - // [DiffEqual, deletion[0 : overlapLength2)]] - diffs[pointer-1].Type = DiffInsert - diffs[pointer-1].Text = insertion[0 : len(insertion)-overlapLength2] - diffs[pointer+1].Type = DiffDelete - diffs[pointer+1].Text = deletion[overlapLength2:] - pointer++ - } - } - pointer++ - } - pointer++ - } - - return diffs -} - -// DiffCleanupSemanticLossless 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 c<ins>at c</ins>ame. -> The <ins>cat </ins>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 -} - -// DiffCleanupEfficiency 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. - type equality struct { - data int - next *equality - } - var equalities *equality - // Always equal to equalities[equalitiesLength-1][1] - lastequality := "" - pointer := 0 // Index of current position. - // Is there an insertion operation before the last equality. - preIns := false - // Is there a deletion operation before the last equality. - preDel := false - // Is there an insertion operation after the last equality. - postIns := false - // Is there a deletion operation after the last equality. - postDel := false - for pointer < len(diffs) { - if diffs[pointer].Type == DiffEqual { // Equality found. - if len(diffs[pointer].Text) < dmp.DiffEditCost && - (postIns || postDel) { - // Candidate found. - equalities = &equality{ - data: pointer, - next: equalities, - } - preIns = postIns - preDel = postDel - lastequality = diffs[pointer].Text - } else { - // Not a candidate, and can never become one. - equalities = nil - lastequality = "" - } - postIns = false - postDel = false - } else { // An insertion or deletion. - if diffs[pointer].Type == DiffDelete { - postDel = true - } else { - postIns = 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> - */ - var sumPres int - if preIns { - sumPres++ - } - if preDel { - sumPres++ - } - if postIns { - sumPres++ - } - if postDel { - sumPres++ - } - if len(lastequality) > 0 && - ((preIns && preDel && postIns && postDel) || - ((len(lastequality) < dmp.DiffEditCost/2) && sumPres == 3)) { - - insPoint := equalities.data - - // Duplicate record. - 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 = equalities.next - lastequality = "" - - if preIns && preDel { - // No changes made which could affect previous entry, keep going. - postIns = true - postDel = true - equalities = nil - } else { - if equalities != nil { - equalities = equalities.next - } - if equalities != nil { - pointer = equalities.data - } else { - pointer = -1 - } - postIns = false - postDel = false - } - changes = true - } - } - pointer++ - } - - if changes { - diffs = dmp.DiffCleanupMerge(diffs) - } - - return diffs -} - -// DiffCleanupMerge 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 - countDelete := 0 - countInsert := 0 - commonlength := 0 - textDelete := []rune(nil) - textInsert := []rune(nil) - - for pointer < len(diffs) { - switch diffs[pointer].Type { - case DiffInsert: - countInsert++ - textInsert = append(textInsert, []rune(diffs[pointer].Text)...) - pointer++ - break - case DiffDelete: - countDelete++ - textDelete = append(textDelete, []rune(diffs[pointer].Text)...) - pointer++ - break - case DiffEqual: - // Upon reaching an equality, check for prior redundancies. - if countDelete+countInsert > 1 { - if countDelete != 0 && countInsert != 0 { - // Factor out any common prefixies. - commonlength = commonPrefixLength(textInsert, textDelete) - if commonlength != 0 { - x := pointer - countDelete - countInsert - if x > 0 && diffs[x-1].Type == DiffEqual { - diffs[x-1].Text += string(textInsert[:commonlength]) - } else { - diffs = append([]Diff{Diff{DiffEqual, string(textInsert[:commonlength])}}, diffs...) - pointer++ - } - textInsert = textInsert[commonlength:] - textDelete = textDelete[commonlength:] - } - // Factor out any common suffixies. - commonlength = commonSuffixLength(textInsert, textDelete) - if commonlength != 0 { - insertIndex := len(textInsert) - commonlength - deleteIndex := len(textDelete) - commonlength - diffs[pointer].Text = string(textInsert[insertIndex:]) + diffs[pointer].Text - textInsert = textInsert[:insertIndex] - textDelete = textDelete[:deleteIndex] - } - } - // Delete the offending records and add the merged ones. - if countDelete == 0 { - diffs = splice(diffs, pointer-countInsert, - countDelete+countInsert, - Diff{DiffInsert, string(textInsert)}) - } else if countInsert == 0 { - diffs = splice(diffs, pointer-countDelete, - countDelete+countInsert, - Diff{DiffDelete, string(textDelete)}) - } else { - diffs = splice(diffs, pointer-countDelete-countInsert, - countDelete+countInsert, - Diff{DiffDelete, string(textDelete)}, - Diff{DiffInsert, string(textInsert)}) - } - - pointer = pointer - countDelete - countInsert + 1 - if countDelete != 0 { - pointer++ - } - if countInsert != 0 { - pointer++ - } - } 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++ - } - countInsert = 0 - countDelete = 0 - textDelete = nil - textInsert = nil - 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: A<ins>BA</ins>C -> <ins>AB</ins>AC - 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 -} - -// DiffXIndex returns the equivalent location in s2. -// 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 - lastChars1 := 0 - lastChars2 := 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 - } - lastChars1 = chars1 - lastChars2 = chars2 - } - if lastDiff.Type == DiffDelete { - // The location was deleted. - return lastChars2 - } - // Add the remaining character length. - return lastChars2 + (loc - lastChars1) -} - -// 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", "¶<br>", -1) - switch diff.Type { - case DiffInsert: - _, _ = buff.WriteString("<ins style=\"background:#e6ffe6;\">") - _, _ = buff.WriteString(text) - _, _ = buff.WriteString("</ins>") - case DiffDelete: - _, _ = buff.WriteString("<del style=\"background:#ffe6e6;\">") - _, _ = buff.WriteString(text) - _, _ = buff.WriteString("</del>") - case DiffEqual: - _, _ = buff.WriteString("<span>") - _, _ = buff.WriteString(text) - _, _ = buff.WriteString("</span>") - } - } - return buff.String() -} - -// DiffPrettyText converts a []Diff into a colored text report. -func (dmp *DiffMatchPatch) DiffPrettyText(diffs []Diff) string { - var buff bytes.Buffer - for _, diff := range diffs { - text := diff.Text - - switch diff.Type { - case DiffInsert: - _, _ = buff.WriteString("\x1b[32m") - _, _ = buff.WriteString(text) - _, _ = buff.WriteString("\x1b[0m") - case DiffDelete: - _, _ = buff.WriteString("\x1b[31m") - _, _ = buff.WriteString(text) - _, _ = buff.WriteString("\x1b[0m") - case DiffEqual: - _, _ = buff.WriteString(text) - } - } - - return buff.String() -} - -// DiffText1 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() -} - -// DiffText2 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() -} - -// DiffLevenshtein 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 -} - -// DiffToDelta 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 -} - -// DiffFromDelta 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'.
diff --git a/diffmatchpatch/diffmatchpatch_test.go b/diffmatchpatch/diffmatchpatch_test.go index c4cc45a..518a040 100644 --- a/diffmatchpatch/diffmatchpatch_test.go +++ b/diffmatchpatch/diffmatchpatch_test.go
@@ -85,87 +85,6 @@ return s1, s2 } -func TestDiffCommonPrefix(t *testing.T) { - type TestCase struct { - Name string - - Text1 string - Text2 string - - Expected int - } - - dmp := New() - - for i, tc := range []TestCase{ - {"Null", "abc", "xyz", 0}, - {"Non-null", "1234abcdef", "1234xyz", 4}, - {"Whole", "1234", "1234xyz", 4}, - } { - actual := dmp.DiffCommonPrefix(tc.Text1, tc.Text2) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestCommonPrefixLength(t *testing.T) { - type TestCase struct { - Text1 string - Text2 string - - Expected int - } - - for i, tc := range []TestCase{ - {"abc", "xyz", 0}, - {"1234abcdef", "1234xyz", 4}, - {"1234", "1234xyz", 4}, - } { - actual := commonPrefixLength([]rune(tc.Text1), []rune(tc.Text2)) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - -func TestDiffCommonSuffix(t *testing.T) { - type TestCase struct { - Name string - - Text1 string - Text2 string - - Expected int - } - - dmp := New() - - for i, tc := range []TestCase{ - {"Null", "abc", "xyz", 0}, - {"Non-null", "abcdef1234", "xyz1234", 4}, - {"Whole", "1234", "xyz1234", 4}, - } { - actual := dmp.DiffCommonSuffix(tc.Text1, tc.Text2) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestCommonSuffixLength(t *testing.T) { - type TestCase struct { - Text1 string - Text2 string - - Expected int - } - - for i, tc := range []TestCase{ - {"abc", "xyz", 0}, - {"abcdef1234", "xyz1234", 4}, - {"1234", "xyz1234", 4}, - {"123", "a3", 1}, - } { - actual := commonSuffixLength([]rune(tc.Text1), []rune(tc.Text2)) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - func TestRunesIndexOf(t *testing.T) { type TestCase struct { Pattern string @@ -192,1183 +111,6 @@ } } -func TestDiffCommonOverlap(t *testing.T) { - type TestCase struct { - Name string - - Text1 string - Text2 string - - Expected int - } - - dmp := New() - - for i, tc := range []TestCase{ - {"Null", "", "abcd", 0}, - {"Whole", "abc", "abcd", 3}, - {"Null", "123456", "abcd", 0}, - {"Null", "123456xxx", "xxxabcd", 3}, - // Some overly clever languages (C#) may treat ligatures as equal to their component letters, e.g. U+FB01 == 'fi' - {"Unicode", "fi", "\ufb01i", 0}, - } { - actual := dmp.DiffCommonOverlap(tc.Text1, tc.Text2) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffHalfMatch(t *testing.T) { - type TestCase struct { - Text1 string - Text2 string - - Expected []string - } - - dmp := New() - dmp.DiffTimeout = 1 - - for i, tc := range []TestCase{ - // No match - {"1234567890", "abcdef", nil}, - {"12345", "23", nil}, - - // Single Match - {"1234567890", "a345678z", []string{"12", "90", "a", "z", "345678"}}, - {"a345678z", "1234567890", []string{"a", "z", "12", "90", "345678"}}, - {"abc56789z", "1234567890", []string{"abc", "z", "1234", "0", "56789"}}, - {"a23456xyz", "1234567890", []string{"a", "xyz", "1", "7890", "23456"}}, - - // Multiple Matches - {"121231234123451234123121", "a1234123451234z", []string{"12123", "123121", "a", "z", "1234123451234"}}, - {"x-=-=-=-=-=-=-=-=-=-=-=-=", "xx-=-=-=-=-=-=-=", []string{"", "-=-=-=-=-=", "x", "", "x-=-=-=-=-=-=-="}}, - {"-=-=-=-=-=-=-=-=-=-=-=-=y", "-=-=-=-=-=-=-=yy", []string{"-=-=-=-=-=", "", "", "y", "-=-=-=-=-=-=-=y"}}, - - // Non-optimal halfmatch, ptimal diff would be -q+x=H-i+e=lloHe+Hu=llo-Hew+y not -qHillo+x=HelloHe-w+Hulloy - {"qHilloHelloHew", "xHelloHeHulloy", []string{"qHillo", "w", "x", "Hulloy", "HelloHe"}}, - } { - actual := dmp.DiffHalfMatch(tc.Text1, tc.Text2) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } - - dmp.DiffTimeout = 0 - - for i, tc := range []TestCase{ - // Optimal no halfmatch - {"qHilloHelloHew", "xHelloHeHulloy", nil}, - } { - actual := dmp.DiffHalfMatch(tc.Text1, tc.Text2) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - -func TestDiffBisectSplit(t *testing.T) { - type TestCase struct { - Text1 string - Text2 string - } - - dmp := New() - - for _, tc := range []TestCase{ - {"STUV\x05WX\x05YZ\x05[", "WĺĻļ\x05YZ\x05ĽľĿŀZ"}, - } { - diffs := dmp.diffBisectSplit([]rune(tc.Text1), - []rune(tc.Text2), 7, 6, time.Now().Add(time.Hour)) - - for _, d := range diffs { - assert.True(t, utf8.ValidString(d.Text)) - } - - // TODO define the expected outcome - } -} - -func TestDiffLinesToChars(t *testing.T) { - type TestCase struct { - Text1 string - Text2 string - - ExpectedChars1 string - ExpectedChars2 string - ExpectedLines []string - } - - dmp := New() - - for i, tc := range []TestCase{ - {"", "alpha\r\nbeta\r\n\r\n\r\n", "", "\u0001\u0002\u0003\u0003", []string{"", "alpha\r\n", "beta\r\n", "\r\n"}}, - {"a", "b", "\u0001", "\u0002", []string{"", "a", "b"}}, - // Omit final newline. - {"alpha\nbeta\nalpha", "", "\u0001\u0002\u0003", "", []string{"", "alpha\n", "beta\n", "alpha"}}, - } { - actualChars1, actualChars2, actualLines := dmp.DiffLinesToChars(tc.Text1, tc.Text2) - assert.Equal(t, tc.ExpectedChars1, actualChars1, fmt.Sprintf("Test case #%d, %#v", i, tc)) - assert.Equal(t, tc.ExpectedChars2, actualChars2, fmt.Sprintf("Test case #%d, %#v", i, tc)) - assert.Equal(t, tc.ExpectedLines, actualLines, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } - - // More than 256 to reveal any 8-bit limitations. - n := 300 - lineList := []string{ - "", // Account for the initial empty element of the lines array. - } - var charList []rune - for x := 1; x < n+1; x++ { - lineList = append(lineList, strconv.Itoa(x)+"\n") - charList = append(charList, rune(x)) - } - lines := strings.Join(lineList, "") - chars := string(charList) - assert.Equal(t, n, utf8.RuneCountInString(chars)) - - actualChars1, actualChars2, actualLines := dmp.DiffLinesToChars(lines, "") - assert.Equal(t, chars, actualChars1) - assert.Equal(t, "", actualChars2) - assert.Equal(t, lineList, actualLines) -} - -func TestDiffCharsToLines(t *testing.T) { - type TestCase struct { - Diffs []Diff - Lines []string - - Expected []Diff - } - - dmp := New() - - for i, tc := range []TestCase{ - { - Diffs: []Diff{ - {DiffEqual, "\u0001\u0002\u0001"}, - {DiffInsert, "\u0002\u0001\u0002"}, - }, - Lines: []string{"", "alpha\n", "beta\n"}, - - Expected: []Diff{ - {DiffEqual, "alpha\nbeta\nalpha\n"}, - {DiffInsert, "beta\nalpha\nbeta\n"}, - }, - }, - } { - actual := dmp.DiffCharsToLines(tc.Diffs, tc.Lines) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } - - // More than 256 to reveal any 8-bit limitations. - n := 300 - lineList := []string{ - "", // Account for the initial empty element of the lines array. - } - charList := []rune{} - for x := 1; x <= n; x++ { - lineList = append(lineList, strconv.Itoa(x)+"\n") - charList = append(charList, rune(x)) - } - assert.Equal(t, n, len(charList)) - - actual := dmp.DiffCharsToLines([]Diff{Diff{DiffDelete, string(charList)}}, lineList) - assert.Equal(t, []Diff{Diff{DiffDelete, strings.Join(lineList, "")}}, actual) -} - -func TestDiffCleanupMerge(t *testing.T) { - type TestCase struct { - Name string - - Diffs []Diff - - Expected []Diff - } - - dmp := New() - - for i, tc := range []TestCase{ - { - "Null case", - []Diff{}, - []Diff{}, - }, - { - "No Diff case", - []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffInsert, "c"}}, - []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffInsert, "c"}}, - }, - { - "Merge equalities", - []Diff{Diff{DiffEqual, "a"}, Diff{DiffEqual, "b"}, Diff{DiffEqual, "c"}}, - []Diff{Diff{DiffEqual, "abc"}}, - }, - { - "Merge deletions", - []Diff{Diff{DiffDelete, "a"}, Diff{DiffDelete, "b"}, Diff{DiffDelete, "c"}}, - []Diff{Diff{DiffDelete, "abc"}}, - }, - { - "Merge insertions", - []Diff{Diff{DiffInsert, "a"}, Diff{DiffInsert, "b"}, Diff{DiffInsert, "c"}}, - []Diff{Diff{DiffInsert, "abc"}}, - }, - { - "Merge interweave", - []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "b"}, Diff{DiffDelete, "c"}, Diff{DiffInsert, "d"}, Diff{DiffEqual, "e"}, Diff{DiffEqual, "f"}}, - []Diff{Diff{DiffDelete, "ac"}, Diff{DiffInsert, "bd"}, Diff{DiffEqual, "ef"}}, - }, - { - "Prefix and suffix detection", - []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "abc"}, Diff{DiffDelete, "dc"}}, - []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "c"}}, - }, - { - "Prefix and suffix detection with equalities", - []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "a"}, Diff{DiffInsert, "abc"}, Diff{DiffDelete, "dc"}, Diff{DiffEqual, "y"}}, - []Diff{Diff{DiffEqual, "xa"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "cy"}}, - }, - { - "Same test as above but with unicode (\u0101 will appear in diffs with at least 257 unique lines)", - []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "\u0101"}, Diff{DiffInsert, "\u0101bc"}, Diff{DiffDelete, "dc"}, Diff{DiffEqual, "y"}}, - []Diff{Diff{DiffEqual, "x\u0101"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "cy"}}, - }, - { - "Slide edit left", - []Diff{Diff{DiffEqual, "a"}, Diff{DiffInsert, "ba"}, Diff{DiffEqual, "c"}}, - []Diff{Diff{DiffInsert, "ab"}, Diff{DiffEqual, "ac"}}, - }, - { - "Slide edit right", - []Diff{Diff{DiffEqual, "c"}, Diff{DiffInsert, "ab"}, Diff{DiffEqual, "a"}}, - []Diff{Diff{DiffEqual, "ca"}, Diff{DiffInsert, "ba"}}, - }, - { - "Slide edit left recursive", - []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffEqual, "c"}, Diff{DiffDelete, "ac"}, Diff{DiffEqual, "x"}}, - []Diff{Diff{DiffDelete, "abc"}, Diff{DiffEqual, "acx"}}, - }, - { - "Slide edit right recursive", - []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "ca"}, Diff{DiffEqual, "c"}, Diff{DiffDelete, "b"}, Diff{DiffEqual, "a"}}, - []Diff{Diff{DiffEqual, "xca"}, Diff{DiffDelete, "cba"}}, - }, - } { - actual := dmp.DiffCleanupMerge(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffCleanupSemanticLossless(t *testing.T) { - type TestCase struct { - Name string - - Diffs []Diff - - Expected []Diff - } - - dmp := New() - - for i, tc := range []TestCase{ - { - "Null case", - []Diff{}, - []Diff{}, - }, - { - "Blank lines", - []Diff{ - Diff{DiffEqual, "AAA\r\n\r\nBBB"}, - Diff{DiffInsert, "\r\nDDD\r\n\r\nBBB"}, - Diff{DiffEqual, "\r\nEEE"}, - }, - []Diff{ - Diff{DiffEqual, "AAA\r\n\r\n"}, - Diff{DiffInsert, "BBB\r\nDDD\r\n\r\n"}, - Diff{DiffEqual, "BBB\r\nEEE"}, - }, - }, - { - "Line boundaries", - []Diff{ - Diff{DiffEqual, "AAA\r\nBBB"}, - Diff{DiffInsert, " DDD\r\nBBB"}, - Diff{DiffEqual, " EEE"}, - }, - []Diff{ - Diff{DiffEqual, "AAA\r\n"}, - Diff{DiffInsert, "BBB DDD\r\n"}, - Diff{DiffEqual, "BBB EEE"}, - }, - }, - { - "Word boundaries", - []Diff{ - Diff{DiffEqual, "The c"}, - Diff{DiffInsert, "ow and the c"}, - Diff{DiffEqual, "at."}, - }, - []Diff{ - Diff{DiffEqual, "The "}, - Diff{DiffInsert, "cow and the "}, - Diff{DiffEqual, "cat."}, - }, - }, - { - "Alphanumeric boundaries", - []Diff{ - Diff{DiffEqual, "The-c"}, - Diff{DiffInsert, "ow-and-the-c"}, - Diff{DiffEqual, "at."}, - }, - []Diff{ - Diff{DiffEqual, "The-"}, - Diff{DiffInsert, "cow-and-the-"}, - Diff{DiffEqual, "cat."}, - }, - }, - { - "Hitting the start", - []Diff{ - Diff{DiffEqual, "a"}, - Diff{DiffDelete, "a"}, - Diff{DiffEqual, "ax"}, - }, - []Diff{ - Diff{DiffDelete, "a"}, - Diff{DiffEqual, "aax"}, - }, - }, - { - "Hitting the end", - []Diff{ - Diff{DiffEqual, "xa"}, - Diff{DiffDelete, "a"}, - Diff{DiffEqual, "a"}, - }, - []Diff{ - Diff{DiffEqual, "xaa"}, - Diff{DiffDelete, "a"}, - }, - }, - { - "Sentence boundaries", - []Diff{ - Diff{DiffEqual, "The xxx. The "}, - Diff{DiffInsert, "zzz. The "}, - Diff{DiffEqual, "yyy."}, - }, - []Diff{ - Diff{DiffEqual, "The xxx."}, - Diff{DiffInsert, " The zzz."}, - Diff{DiffEqual, " The yyy."}, - }, - }, - { - "UTF-8 strings", - []Diff{ - Diff{DiffEqual, "The ♕. The "}, - Diff{DiffInsert, "♔. The "}, - Diff{DiffEqual, "♖."}, - }, - []Diff{ - Diff{DiffEqual, "The ♕."}, - Diff{DiffInsert, " The ♔."}, - Diff{DiffEqual, " The ♖."}, - }, - }, - { - "Rune boundaries", - []Diff{ - Diff{DiffEqual, "♕♕"}, - Diff{DiffInsert, "♔♔"}, - Diff{DiffEqual, "♖♖"}, - }, - []Diff{ - Diff{DiffEqual, "♕♕"}, - Diff{DiffInsert, "♔♔"}, - Diff{DiffEqual, "♖♖"}, - }, - }, - } { - actual := dmp.DiffCleanupSemanticLossless(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffCleanupSemantic(t *testing.T) { - type TestCase struct { - Name string - - Diffs []Diff - - Expected []Diff - } - - dmp := New() - - for i, tc := range []TestCase{ - { - "Null case", - []Diff{}, - []Diff{}, - }, - { - "No elimination #1", - []Diff{ - {DiffDelete, "ab"}, - {DiffInsert, "cd"}, - {DiffEqual, "12"}, - {DiffDelete, "e"}, - }, - []Diff{ - {DiffDelete, "ab"}, - {DiffInsert, "cd"}, - {DiffEqual, "12"}, - {DiffDelete, "e"}, - }, - }, - { - "No elimination #2", - []Diff{ - {DiffDelete, "abc"}, - {DiffInsert, "ABC"}, - {DiffEqual, "1234"}, - {DiffDelete, "wxyz"}, - }, - []Diff{ - {DiffDelete, "abc"}, - {DiffInsert, "ABC"}, - {DiffEqual, "1234"}, - {DiffDelete, "wxyz"}, - }, - }, - { - "No elimination #3", - []Diff{ - {DiffEqual, "2016-09-01T03:07:1"}, - {DiffInsert, "5.15"}, - {DiffEqual, "4"}, - {DiffDelete, "."}, - {DiffEqual, "80"}, - {DiffInsert, "0"}, - {DiffEqual, "78"}, - {DiffDelete, "3074"}, - {DiffEqual, "1Z"}, - }, - []Diff{ - {DiffEqual, "2016-09-01T03:07:1"}, - {DiffInsert, "5.15"}, - {DiffEqual, "4"}, - {DiffDelete, "."}, - {DiffEqual, "80"}, - {DiffInsert, "0"}, - {DiffEqual, "78"}, - {DiffDelete, "3074"}, - {DiffEqual, "1Z"}, - }, - }, - { - "Simple elimination", - []Diff{ - {DiffDelete, "a"}, - {DiffEqual, "b"}, - {DiffDelete, "c"}, - }, - []Diff{ - {DiffDelete, "abc"}, - {DiffInsert, "b"}, - }, - }, - { - "Backpass elimination", - []Diff{ - {DiffDelete, "ab"}, - {DiffEqual, "cd"}, - {DiffDelete, "e"}, - {DiffEqual, "f"}, - {DiffInsert, "g"}, - }, - []Diff{ - {DiffDelete, "abcdef"}, - {DiffInsert, "cdfg"}, - }, - }, - { - "Multiple eliminations", - []Diff{ - {DiffInsert, "1"}, - {DiffEqual, "A"}, - {DiffDelete, "B"}, - {DiffInsert, "2"}, - {DiffEqual, "_"}, - {DiffInsert, "1"}, - {DiffEqual, "A"}, - {DiffDelete, "B"}, - {DiffInsert, "2"}, - }, - []Diff{ - {DiffDelete, "AB_AB"}, - {DiffInsert, "1A2_1A2"}, - }, - }, - { - "Word boundaries", - []Diff{ - {DiffEqual, "The c"}, - {DiffDelete, "ow and the c"}, - {DiffEqual, "at."}, - }, - []Diff{ - {DiffEqual, "The "}, - {DiffDelete, "cow and the "}, - {DiffEqual, "cat."}, - }, - }, - { - "No overlap elimination", - []Diff{ - {DiffDelete, "abcxx"}, - {DiffInsert, "xxdef"}, - }, - []Diff{ - {DiffDelete, "abcxx"}, - {DiffInsert, "xxdef"}, - }, - }, - { - "Overlap elimination", - []Diff{ - {DiffDelete, "abcxxx"}, - {DiffInsert, "xxxdef"}, - }, - []Diff{ - {DiffDelete, "abc"}, - {DiffEqual, "xxx"}, - {DiffInsert, "def"}, - }, - }, - { - "Reverse overlap elimination", - []Diff{ - {DiffDelete, "xxxabc"}, - {DiffInsert, "defxxx"}, - }, - []Diff{ - {DiffInsert, "def"}, - {DiffEqual, "xxx"}, - {DiffDelete, "abc"}, - }, - }, - { - "Two overlap eliminations", - []Diff{ - {DiffDelete, "abcd1212"}, - {DiffInsert, "1212efghi"}, - {DiffEqual, "----"}, - {DiffDelete, "A3"}, - {DiffInsert, "3BC"}, - }, - []Diff{ - {DiffDelete, "abcd"}, - {DiffEqual, "1212"}, - {DiffInsert, "efghi"}, - {DiffEqual, "----"}, - {DiffDelete, "A"}, - {DiffEqual, "3"}, - {DiffInsert, "BC"}, - }, - }, - { - "Test case for adapting DiffCleanupSemantic to be equal to the Python version #19", - []Diff{ - {DiffEqual, "James McCarthy "}, - {DiffDelete, "close to "}, - {DiffEqual, "sign"}, - {DiffDelete, "ing"}, - {DiffInsert, "s"}, - {DiffEqual, " new "}, - {DiffDelete, "E"}, - {DiffInsert, "fi"}, - {DiffEqual, "ve"}, - {DiffInsert, "-yea"}, - {DiffEqual, "r"}, - {DiffDelete, "ton"}, - {DiffEqual, " deal"}, - {DiffInsert, " at Everton"}, - }, - []Diff{ - {DiffEqual, "James McCarthy "}, - {DiffDelete, "close to "}, - {DiffEqual, "sign"}, - {DiffDelete, "ing"}, - {DiffInsert, "s"}, - {DiffEqual, " new "}, - {DiffInsert, "five-year deal at "}, - {DiffEqual, "Everton"}, - {DiffDelete, " deal"}, - }, - }, - } { - actual := dmp.DiffCleanupSemantic(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffCleanupEfficiency(t *testing.T) { - type TestCase struct { - Name string - - Diffs []Diff - - Expected []Diff - } - - dmp := New() - dmp.DiffEditCost = 4 - - for i, tc := range []TestCase{ - { - "Null case", - []Diff{}, - []Diff{}, - }, - { - "No elimination", - []Diff{ - Diff{DiffDelete, "ab"}, - Diff{DiffInsert, "12"}, - Diff{DiffEqual, "wxyz"}, - Diff{DiffDelete, "cd"}, - Diff{DiffInsert, "34"}, - }, - []Diff{ - Diff{DiffDelete, "ab"}, - Diff{DiffInsert, "12"}, - Diff{DiffEqual, "wxyz"}, - Diff{DiffDelete, "cd"}, - Diff{DiffInsert, "34"}, - }, - }, - { - "Four-edit elimination", - []Diff{ - Diff{DiffDelete, "ab"}, - Diff{DiffInsert, "12"}, - Diff{DiffEqual, "xyz"}, - Diff{DiffDelete, "cd"}, - Diff{DiffInsert, "34"}, - }, - []Diff{ - Diff{DiffDelete, "abxyzcd"}, - Diff{DiffInsert, "12xyz34"}, - }, - }, - { - "Three-edit elimination", - []Diff{ - Diff{DiffInsert, "12"}, - Diff{DiffEqual, "x"}, - Diff{DiffDelete, "cd"}, - Diff{DiffInsert, "34"}, - }, - []Diff{ - Diff{DiffDelete, "xcd"}, - Diff{DiffInsert, "12x34"}, - }, - }, - { - "Backpass elimination", - []Diff{ - Diff{DiffDelete, "ab"}, - Diff{DiffInsert, "12"}, - Diff{DiffEqual, "xy"}, - Diff{DiffInsert, "34"}, - Diff{DiffEqual, "z"}, - Diff{DiffDelete, "cd"}, - Diff{DiffInsert, "56"}, - }, - []Diff{ - Diff{DiffDelete, "abxyzcd"}, - Diff{DiffInsert, "12xy34z56"}, - }, - }, - } { - actual := dmp.DiffCleanupEfficiency(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } - - dmp.DiffEditCost = 5 - - for i, tc := range []TestCase{ - { - "High cost elimination", - []Diff{ - Diff{DiffDelete, "ab"}, - Diff{DiffInsert, "12"}, - Diff{DiffEqual, "wxyz"}, - Diff{DiffDelete, "cd"}, - Diff{DiffInsert, "34"}, - }, - []Diff{ - Diff{DiffDelete, "abwxyzcd"}, - Diff{DiffInsert, "12wxyz34"}, - }, - }, - } { - actual := dmp.DiffCleanupEfficiency(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffPrettyHtml(t *testing.T) { - type TestCase struct { - Diffs []Diff - - Expected string - } - - dmp := New() - - for i, tc := range []TestCase{ - { - Diffs: []Diff{ - {DiffEqual, "a\n"}, - {DiffDelete, "<B>b</B>"}, - {DiffInsert, "c&d"}, - }, - - Expected: "<span>a¶<br></span><del style=\"background:#ffe6e6;\"><B>b</B></del><ins style=\"background:#e6ffe6;\">c&d</ins>", - }, - } { - actual := dmp.DiffPrettyHtml(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - -func TestDiffPrettyText(t *testing.T) { - type TestCase struct { - Diffs []Diff - - Expected string - } - - dmp := New() - - for i, tc := range []TestCase{ - { - Diffs: []Diff{ - {DiffEqual, "a\n"}, - {DiffDelete, "<B>b</B>"}, - {DiffInsert, "c&d"}, - }, - - Expected: "a\n\x1b[31m<B>b</B>\x1b[0m\x1b[32mc&d\x1b[0m", - }, - } { - actual := dmp.DiffPrettyText(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - -func TestDiffText(t *testing.T) { - type TestCase struct { - Diffs []Diff - - ExpectedText1 string - ExpectedText2 string - } - - dmp := New() - - for i, tc := range []TestCase{ - { - Diffs: []Diff{ - {DiffEqual, "jump"}, - {DiffDelete, "s"}, - {DiffInsert, "ed"}, - {DiffEqual, " over "}, - {DiffDelete, "the"}, - {DiffInsert, "a"}, - {DiffEqual, " lazy"}, - }, - - ExpectedText1: "jumps over the lazy", - ExpectedText2: "jumped over a lazy", - }, - } { - actualText1 := dmp.DiffText1(tc.Diffs) - assert.Equal(t, tc.ExpectedText1, actualText1, fmt.Sprintf("Test case #%d, %#v", i, tc)) - - actualText2 := dmp.DiffText2(tc.Diffs) - assert.Equal(t, tc.ExpectedText2, actualText2, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - -func TestDiffDelta(t *testing.T) { - dmp := New() - - // Convert a diff into delta string. - diffs := []Diff{ - Diff{DiffEqual, "jump"}, - Diff{DiffDelete, "s"}, - Diff{DiffInsert, "ed"}, - Diff{DiffEqual, " over "}, - Diff{DiffDelete, "the"}, - Diff{DiffInsert, "a"}, - Diff{DiffEqual, " lazy"}, - Diff{DiffInsert, "old dog"}, - } - text1 := dmp.DiffText1(diffs) - assert.Equal(t, "jumps over the lazy", text1) - - delta := dmp.DiffToDelta(diffs) - assert.Equal(t, "=4\t-1\t+ed\t=6\t-3\t+a\t=5\t+old dog", delta) - - // Convert delta string into a diff. - deltaDiffs, err := dmp.DiffFromDelta(text1, delta) - assert.Equal(t, diffs, deltaDiffs) - - // Generates error (19 < 20). - _, err = dmp.DiffFromDelta(text1+"x", delta) - if err == nil { - t.Fatal("Too long.") - } - - // Generates error (19 > 18). - _, err = dmp.DiffFromDelta(text1[1:], delta) - if err == nil { - t.Fatal("Too short.") - } - - // Generates error (%xy invalid URL escape). - _, err = dmp.DiffFromDelta("", "+%c3%xy") - if err == nil { - assert.Fail(t, "expected Invalid URL escape.") - } - - // Generates error (invalid utf8). - _, err = dmp.DiffFromDelta("", "+%c3xy") - if err == nil { - assert.Fail(t, "expected Invalid utf8.") - } - - // Test deltas with special characters. - diffs = []Diff{ - Diff{DiffEqual, "\u0680 \x00 \t %"}, - Diff{DiffDelete, "\u0681 \x01 \n ^"}, - Diff{DiffInsert, "\u0682 \x02 \\ |"}, - } - text1 = dmp.DiffText1(diffs) - assert.Equal(t, "\u0680 \x00 \t %\u0681 \x01 \n ^", text1) - - // Lowercase, due to UrlEncode uses lower. - delta = dmp.DiffToDelta(diffs) - assert.Equal(t, "=7\t-7\t+%DA%82 %02 %5C %7C", delta) - - deltaDiffs, err = dmp.DiffFromDelta(text1, delta) - assert.Equal(t, diffs, deltaDiffs) - assert.Nil(t, err) - - // Verify pool of unchanged characters. - diffs = []Diff{ - Diff{DiffInsert, "A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # "}, - } - - delta = dmp.DiffToDelta(diffs) - assert.Equal(t, "+A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # ", delta, "Unchanged characters.") - - // Convert delta string into a diff. - deltaDiffs, err = dmp.DiffFromDelta("", delta) - assert.Equal(t, diffs, deltaDiffs) - assert.Nil(t, err) -} - -func TestDiffXIndex(t *testing.T) { - type TestCase struct { - Name string - - Diffs []Diff - Location int - - Expected int - } - - dmp := New() - - for i, tc := range []TestCase{ - {"Translation on equality", []Diff{{DiffDelete, "a"}, {DiffInsert, "1234"}, {DiffEqual, "xyz"}}, 2, 5}, - {"Translation on deletion", []Diff{{DiffEqual, "a"}, {DiffDelete, "1234"}, {DiffEqual, "xyz"}}, 3, 1}, - } { - actual := dmp.DiffXIndex(tc.Diffs, tc.Location) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffLevenshtein(t *testing.T) { - type TestCase struct { - Name string - - Diffs []Diff - - Expected int - } - - dmp := New() - - for i, tc := range []TestCase{ - {"Levenshtein with trailing equality", []Diff{{DiffDelete, "abc"}, {DiffInsert, "1234"}, {DiffEqual, "xyz"}}, 4}, - {"Levenshtein with leading equality", []Diff{{DiffEqual, "xyz"}, {DiffDelete, "abc"}, {DiffInsert, "1234"}}, 4}, - {"Levenshtein with middle equality", []Diff{{DiffDelete, "abc"}, {DiffEqual, "xyz"}, {DiffInsert, "1234"}}, 7}, - } { - actual := dmp.DiffLevenshtein(tc.Diffs) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffBisect(t *testing.T) { - type TestCase struct { - Name string - - Time time.Time - - Expected []Diff - } - - dmp := New() - - text1 := "cat" - text2 := "map" - - for i, tc := range []TestCase{ - { - Name: "normal", - Time: time.Date(9999, time.December, 31, 23, 59, 59, 59, time.UTC), - - Expected: []Diff{ - {DiffDelete, "c"}, - {DiffInsert, "m"}, - {DiffEqual, "a"}, - {DiffDelete, "t"}, - {DiffInsert, "p"}, - }, - }, - { - Name: "Negative deadlines count as having infinite time", - Time: time.Date(0001, time.January, 01, 00, 00, 00, 00, time.UTC), - - Expected: []Diff{ - {DiffDelete, "c"}, - {DiffInsert, "m"}, - {DiffEqual, "a"}, - {DiffDelete, "t"}, - {DiffInsert, "p"}, - }, - }, - { - Name: "Timeout", - Time: time.Now().Add(time.Nanosecond), - - Expected: []Diff{ - {DiffDelete, "cat"}, - {DiffInsert, "map"}, - }, - }, - } { - actual := dmp.DiffBisect(text1, text2, tc.Time) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) - } -} - -func TestDiffMain(t *testing.T) { - type TestCase struct { - Text1 string - Text2 string - - Expected []Diff - } - - dmp := New() - - // Perform a trivial diff. - for i, tc := range []TestCase{ - { - "", - "", - nil, - }, - { - "abc", - "abc", - []Diff{Diff{DiffEqual, "abc"}}, - }, - { - "abc", - "ab123c", - []Diff{Diff{DiffEqual, "ab"}, Diff{DiffInsert, "123"}, Diff{DiffEqual, "c"}}, - }, - { - "a123bc", - "abc", - []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "123"}, Diff{DiffEqual, "bc"}}, - }, - { - "abc", - "a123b456c", - []Diff{Diff{DiffEqual, "a"}, Diff{DiffInsert, "123"}, Diff{DiffEqual, "b"}, Diff{DiffInsert, "456"}, Diff{DiffEqual, "c"}}, - }, - { - "a123b456c", - "abc", - []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "123"}, Diff{DiffEqual, "b"}, Diff{DiffDelete, "456"}, Diff{DiffEqual, "c"}}, - }, - } { - actual := dmp.DiffMain(tc.Text1, tc.Text2, false) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } - - // Perform a real diff and switch off the timeout. - dmp.DiffTimeout = 0 - - for i, tc := range []TestCase{ - { - "a", - "b", - []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "b"}}, - }, - { - "Apples are a fruit.", - "Bananas are also fruit.", - []Diff{ - Diff{DiffDelete, "Apple"}, - Diff{DiffInsert, "Banana"}, - Diff{DiffEqual, "s are a"}, - Diff{DiffInsert, "lso"}, - Diff{DiffEqual, " fruit."}, - }, - }, - { - "ax\t", - "\u0680x\u0000", - []Diff{ - Diff{DiffDelete, "a"}, - Diff{DiffInsert, "\u0680"}, - Diff{DiffEqual, "x"}, - Diff{DiffDelete, "\t"}, - Diff{DiffInsert, "\u0000"}, - }, - }, - { - "1ayb2", - "abxab", - []Diff{ - Diff{DiffDelete, "1"}, - Diff{DiffEqual, "a"}, - Diff{DiffDelete, "y"}, - Diff{DiffEqual, "b"}, - Diff{DiffDelete, "2"}, - Diff{DiffInsert, "xab"}, - }, - }, - { - "abcy", - "xaxcxabc", - []Diff{ - Diff{DiffInsert, "xaxcx"}, - Diff{DiffEqual, "abc"}, Diff{DiffDelete, "y"}, - }, - }, - { - "ABCDa=bcd=efghijklmnopqrsEFGHIJKLMNOefg", - "a-bcd-efghijklmnopqrs", - []Diff{ - Diff{DiffDelete, "ABCD"}, - Diff{DiffEqual, "a"}, - Diff{DiffDelete, "="}, - Diff{DiffInsert, "-"}, - Diff{DiffEqual, "bcd"}, - Diff{DiffDelete, "="}, - Diff{DiffInsert, "-"}, - Diff{DiffEqual, "efghijklmnopqrs"}, - Diff{DiffDelete, "EFGHIJKLMNOefg"}, - }, - }, - { - "a [[Pennsylvania]] and [[New", - " and [[Pennsylvania]]", - []Diff{ - Diff{DiffInsert, " "}, - Diff{DiffEqual, "a"}, - Diff{DiffInsert, "nd"}, - Diff{DiffEqual, " [[Pennsylvania]]"}, - Diff{DiffDelete, " and [[New"}, - }, - }, - } { - actual := dmp.DiffMain(tc.Text1, tc.Text2, false) - assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - -func TestDiffMainWithTimeout(t *testing.T) { - dmp := New() - dmp.DiffTimeout = 200 * time.Millisecond - - a := "`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n" - b := "I am the very model of a modern major general,\nI've information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n" - // Increase the text lengths by 1024 times to ensure a timeout. - for x := 0; x < 13; x++ { - a = a + a - b = b + b - } - - startTime := time.Now() - dmp.DiffMain(a, b, true) - endTime := time.Now() - - delta := endTime.Sub(startTime) - - // Test that we took at least the timeout period. - assert.True(t, delta >= dmp.DiffTimeout, fmt.Sprintf("%v !>= %v", delta, dmp.DiffTimeout)) - - // Test that we didn't take forever (be very forgiving). - // Theoretically this test could fail very occasionally if the - // OS task swaps or locks up for a second at the wrong moment. - assert.True(t, delta < (dmp.DiffTimeout*100), fmt.Sprintf("%v !< %v", delta, dmp.DiffTimeout*100)) -} - -func TestDiffMainWithCheckLines(t *testing.T) { - type TestCase struct { - Text1 string - Text2 string - } - - dmp := New() - dmp.DiffTimeout = 0 - - // Test cases must be at least 100 chars long to pass the cutoff. - for i, tc := range []TestCase{ - { - "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n", - "abcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\n", - }, - { - "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", - "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij", - }, - { - "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n", - "abcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n", - }, - } { - resultWithoutCheckLines := dmp.DiffMain(tc.Text1, tc.Text2, false) - resultWithCheckLines := dmp.DiffMain(tc.Text1, tc.Text2, true) - - // TODO this fails for the third test case, why? - if i != 2 { - assert.Equal(t, resultWithoutCheckLines, resultWithCheckLines, fmt.Sprintf("Test case #%d, %#v", i, tc)) - } - assert.Equal(t, diffRebuildTexts(resultWithoutCheckLines), diffRebuildTexts(resultWithCheckLines), fmt.Sprintf("Test case #%d, %#v", i, tc)) - } -} - func TestMatchAlphabet(t *testing.T) { type TestCase struct { Pattern string @@ -1918,98 +660,3 @@ assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) } } - -func BenchmarkDiffMain(bench *testing.B) { - s1 := "`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n" - s2 := "I am the very model of a modern major general,\nI've information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n" - - // Increase the text lengths by 1024 times to ensure a timeout. - for x := 0; x < 10; x++ { - s1 = s1 + s1 - s2 = s2 + s2 - } - - dmp := New() - dmp.DiffTimeout = time.Second - - bench.ResetTimer() - - for i := 0; i < bench.N; i++ { - dmp.DiffMain(s1, s2, true) - } -} - -func BenchmarkDiffCommonPrefix(b *testing.B) { - s := "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ" - - dmp := New() - - for i := 0; i < b.N; i++ { - dmp.DiffCommonPrefix(s, s) - } -} - -func BenchmarkDiffCommonSuffix(b *testing.B) { - s := "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ" - - dmp := New() - - b.ResetTimer() - - for i := 0; i < b.N; i++ { - dmp.DiffCommonSuffix(s, s) - } -} - -func BenchmarkDiffMainLarge(b *testing.B) { - s1, s2 := speedtestTexts() - - dmp := New() - - b.ResetTimer() - - for i := 0; i < b.N; i++ { - dmp.DiffMain(s1, s2, true) - } -} - -func BenchmarkDiffMainRunesLargeLines(b *testing.B) { - s1, s2 := speedtestTexts() - - dmp := New() - - b.ResetTimer() - - for i := 0; i < b.N; i++ { - text1, text2, linearray := dmp.DiffLinesToRunes(s1, s2) - - diffs := dmp.DiffMainRunes(text1, text2, false) - diffs = dmp.DiffCharsToLines(diffs, linearray) - } -} - -func BenchmarkDiffHalfMatch(b *testing.B) { - s1, s2 := speedtestTexts() - - dmp := New() - - b.ResetTimer() - - for i := 0; i < b.N; i++ { - dmp.DiffHalfMatch(s1, s2) - } -} - -func BenchmarkDiffCleanupSemantic(b *testing.B) { - s1, s2 := speedtestTexts() - - dmp := New() - - diffs := dmp.DiffMain(s1, s2, false) - - b.ResetTimer() - - for i := 0; i < b.N; i++ { - dmp.DiffCleanupSemantic(diffs) - } -}