How to use Common method of diff Package

Best Got code snippet using diff.Common

diff.go

Source:diff.go Github

copy

Full Screen

...157 text1A := hm[0]158 text1B := hm[1]159 text2A := hm[2]160 text2B := hm[3]161 midCommon := hm[4]162 // Send both pairs off for separate processing.163 diffsA := dmp.diffMainRunes(text1A, text2A, checklines, deadline)164 diffsB := dmp.diffMainRunes(text1B, text2B, checklines, deadline)165 // Merge the results.166 diffs := diffsA167 diffs = append(diffs, Diff{DiffEqual, string(midCommon)})168 diffs = append(diffs, diffsB...)169 return diffs170 } else if checklines && len(text1) > 100 && len(text2) > 100 {171 return dmp.diffLineMode(text1, text2, deadline)172 }173 return dmp.diffBisect(text1, text2, deadline)174}175// diffLineMode does a quick line-level diff on both []runes, then rediff the parts for greater accuracy. This speedup can produce non-minimal diffs.176func (dmp *DiffMatchPatch) diffLineMode(text1, text2 []rune, deadline time.Time) []Diff {177 // Scan the text on a line-by-line basis first.178 text1, text2, linearray := dmp.diffLinesToRunes(text1, text2)179 diffs := dmp.diffMainRunes(text1, text2, false, deadline)180 // Convert the diff back to original text.181 diffs = dmp.DiffCharsToLines(diffs, linearray)182 // Eliminate freak matches (e.g. blank lines)183 diffs = dmp.DiffCleanupSemantic(diffs)184 // Rediff any replacement blocks, this time character-by-character.185 // Add a dummy entry at the end.186 diffs = append(diffs, Diff{DiffEqual, ""})187 pointer := 0188 countDelete := 0189 countInsert := 0190 // NOTE: Rune slices are slower than using strings in this case.191 textDelete := ""192 textInsert := ""193 for pointer < len(diffs) {194 switch diffs[pointer].Type {195 case DiffInsert:196 countInsert++197 textInsert += diffs[pointer].Text198 case DiffDelete:199 countDelete++200 textDelete += diffs[pointer].Text201 case DiffEqual:202 // Upon reaching an equality, check for prior redundancies.203 if countDelete >= 1 && countInsert >= 1 {204 // Delete the offending records and add the merged ones.205 diffs = splice(diffs, pointer-countDelete-countInsert,206 countDelete+countInsert)207 pointer = pointer - countDelete - countInsert208 a := dmp.diffMainRunes([]rune(textDelete), []rune(textInsert), false, deadline)209 for j := len(a) - 1; j >= 0; j-- {210 diffs = splice(diffs, pointer, 0, a[j])211 }212 pointer = pointer + len(a)213 }214 countInsert = 0215 countDelete = 0216 textDelete = ""217 textInsert = ""218 }219 pointer++220 }221 return diffs[:len(diffs)-1] // Remove the dummy entry at the end.222}223// DiffBisect finds the 'middle snake' of a diff, split the problem in two and return the recursively constructed diff.224// If an invalid UTF-8 sequence is encountered, it will be replaced by the Unicode replacement character.225// See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.226func (dmp *DiffMatchPatch) DiffBisect(text1, text2 string, deadline time.Time) []Diff {227 // Unused in this code, but retained for interface compatibility.228 return dmp.diffBisect([]rune(text1), []rune(text2), deadline)229}230// diffBisect finds the 'middle snake' of a diff, splits the problem in two and returns the recursively constructed diff.231// See Myers's 1986 paper: An O(ND) Difference Algorithm and Its Variations.232func (dmp *DiffMatchPatch) diffBisect(runes1, runes2 []rune, deadline time.Time) []Diff {233 // Cache the text lengths to prevent multiple calls.234 runes1Len, runes2Len := len(runes1), len(runes2)235 maxD := (runes1Len + runes2Len + 1) / 2236 vOffset := maxD237 vLength := 2 * maxD238 v1 := make([]int, vLength)239 v2 := make([]int, vLength)240 for i := range v1 {241 v1[i] = -1242 v2[i] = -1243 }244 v1[vOffset+1] = 0245 v2[vOffset+1] = 0246 delta := runes1Len - runes2Len247 // If the total number of characters is odd, then the front path will collide with the reverse path.248 front := (delta%2 != 0)249 // Offsets for start and end of k loop. Prevents mapping of space beyond the grid.250 k1start := 0251 k1end := 0252 k2start := 0253 k2end := 0254 for d := 0; d < maxD; d++ {255 // Bail out if deadline is reached.256 if !deadline.IsZero() && d%16 == 0 && time.Now().After(deadline) {257 break258 }259 // Walk the front path one step.260 for k1 := -d + k1start; k1 <= d-k1end; k1 += 2 {261 k1Offset := vOffset + k1262 var x1 int263 if k1 == -d || (k1 != d && v1[k1Offset-1] < v1[k1Offset+1]) {264 x1 = v1[k1Offset+1]265 } else {266 x1 = v1[k1Offset-1] + 1267 }268 y1 := x1 - k1269 for x1 < runes1Len && y1 < runes2Len {270 if runes1[x1] != runes2[y1] {271 break272 }273 x1++274 y1++275 }276 v1[k1Offset] = x1277 if x1 > runes1Len {278 // Ran off the right of the graph.279 k1end += 2280 } else if y1 > runes2Len {281 // Ran off the bottom of the graph.282 k1start += 2283 } else if front {284 k2Offset := vOffset + delta - k1285 if k2Offset >= 0 && k2Offset < vLength && v2[k2Offset] != -1 {286 // Mirror x2 onto top-left coordinate system.287 x2 := runes1Len - v2[k2Offset]288 if x1 >= x2 {289 // Overlap detected.290 return dmp.diffBisectSplit(runes1, runes2, x1, y1, deadline)291 }292 }293 }294 }295 // Walk the reverse path one step.296 for k2 := -d + k2start; k2 <= d-k2end; k2 += 2 {297 k2Offset := vOffset + k2298 var x2 int299 if k2 == -d || (k2 != d && v2[k2Offset-1] < v2[k2Offset+1]) {300 x2 = v2[k2Offset+1]301 } else {302 x2 = v2[k2Offset-1] + 1303 }304 var y2 = x2 - k2305 for x2 < runes1Len && y2 < runes2Len {306 if runes1[runes1Len-x2-1] != runes2[runes2Len-y2-1] {307 break308 }309 x2++310 y2++311 }312 v2[k2Offset] = x2313 if x2 > runes1Len {314 // Ran off the left of the graph.315 k2end += 2316 } else if y2 > runes2Len {317 // Ran off the top of the graph.318 k2start += 2319 } else if !front {320 k1Offset := vOffset + delta - k2321 if k1Offset >= 0 && k1Offset < vLength && v1[k1Offset] != -1 {322 x1 := v1[k1Offset]323 y1 := vOffset + x1 - k1Offset324 // Mirror x2 onto top-left coordinate system.325 x2 = runes1Len - x2326 if x1 >= x2 {327 // Overlap detected.328 return dmp.diffBisectSplit(runes1, runes2, x1, y1, deadline)329 }330 }331 }332 }333 }334 // Diff took too long and hit the deadline or number of diffs equals number of characters, no commonality at all.335 return []Diff{336 Diff{DiffDelete, string(runes1)},337 Diff{DiffInsert, string(runes2)},338 }339}340func (dmp *DiffMatchPatch) diffBisectSplit(runes1, runes2 []rune, x, y int,341 deadline time.Time) []Diff {342 runes1a := runes1[:x]343 runes2a := runes2[:y]344 runes1b := runes1[x:]345 runes2b := runes2[y:]346 // Compute both diffs serially.347 diffs := dmp.diffMainRunes(runes1a, runes2a, false, deadline)348 diffsb := dmp.diffMainRunes(runes1b, runes2b, false, deadline)349 return append(diffs, diffsb...)350}351// DiffLinesToChars splits two texts into a list of strings, and educes the texts to a string of hashes where each Unicode character represents one line.352// It's slightly faster to call DiffLinesToRunes first, followed by DiffMainRunes.353func (dmp *DiffMatchPatch) DiffLinesToChars(text1, text2 string) (string, string, []string) {354 chars1, chars2, lineArray := dmp.DiffLinesToRunes(text1, text2)355 return string(chars1), string(chars2), lineArray356}357// DiffLinesToRunes splits two texts into a list of runes. Each rune represents one line.358func (dmp *DiffMatchPatch) DiffLinesToRunes(text1, text2 string) ([]rune, []rune, []string) {359 // '\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.360 lineArray := []string{""} // e.g. lineArray[4] == 'Hello\n'361 lineHash := map[string]int{} // e.g. lineHash['Hello\n'] == 4362 chars1 := dmp.diffLinesToRunesMunge(text1, &lineArray, lineHash)363 chars2 := dmp.diffLinesToRunesMunge(text2, &lineArray, lineHash)364 return chars1, chars2, lineArray365}366func (dmp *DiffMatchPatch) diffLinesToRunes(text1, text2 []rune) ([]rune, []rune, []string) {367 return dmp.DiffLinesToRunes(string(text1), string(text2))368}369// diffLinesToRunesMunge splits a text into an array of strings, and reduces the texts to a []rune where each Unicode character represents one line.370// We use strings instead of []runes as input mainly because you can't use []rune as a map key.371func (dmp *DiffMatchPatch) diffLinesToRunesMunge(text string, lineArray *[]string, lineHash map[string]int) []rune {372 // 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.373 lineStart := 0374 lineEnd := -1375 runes := []rune{}376 for lineEnd < len(text)-1 {377 lineEnd = indexOf(text, "\n", lineStart)378 if lineEnd == -1 {379 lineEnd = len(text) - 1380 }381 line := text[lineStart : lineEnd+1]382 lineStart = lineEnd + 1383 lineValue, ok := lineHash[line]384 if ok {385 runes = append(runes, rune(lineValue))386 } else {387 *lineArray = append(*lineArray, line)388 lineHash[line] = len(*lineArray) - 1389 runes = append(runes, rune(len(*lineArray)-1))390 }391 }392 return runes393}394// DiffCharsToLines rehydrates the text in a diff from a string of line hashes to real lines of text.395func (dmp *DiffMatchPatch) DiffCharsToLines(diffs []Diff, lineArray []string) []Diff {396 hydrated := make([]Diff, 0, len(diffs))397 for _, aDiff := range diffs {398 chars := aDiff.Text399 text := make([]string, len(chars))400 for i, r := range chars {401 text[i] = lineArray[r]402 }403 aDiff.Text = strings.Join(text, "")404 hydrated = append(hydrated, aDiff)405 }406 return hydrated407}408// DiffCommonPrefix determines the common prefix length of two strings.409func (dmp *DiffMatchPatch) DiffCommonPrefix(text1, text2 string) int {410 // Unused in this code, but retained for interface compatibility.411 return commonPrefixLength([]rune(text1), []rune(text2))412}413// DiffCommonSuffix determines the common suffix length of two strings.414func (dmp *DiffMatchPatch) DiffCommonSuffix(text1, text2 string) int {415 // Unused in this code, but retained for interface compatibility.416 return commonSuffixLength([]rune(text1), []rune(text2))417}418// commonPrefixLength returns the length of the common prefix of two rune slices.419func commonPrefixLength(text1, text2 []rune) int {420 // Linear search. See comment in commonSuffixLength.421 n := 0422 for ; n < len(text1) && n < len(text2); n++ {423 if text1[n] != text2[n] {424 return n425 }426 }427 return n428}429// commonSuffixLength returns the length of the common suffix of two rune slices.430func commonSuffixLength(text1, text2 []rune) int {431 // Use linear search rather than the binary search discussed at https://neil.fraser.name/news/2007/10/09/.432 // See discussion at https://github.com/sergi/go-diff/issues/54.433 i1 := len(text1)434 i2 := len(text2)435 for n := 0; ; n++ {436 i1--437 i2--438 if i1 < 0 || i2 < 0 || text1[i1] != text2[i2] {439 return n440 }441 }442}443// DiffCommonOverlap determines if the suffix of one string is the prefix of another.444func (dmp *DiffMatchPatch) DiffCommonOverlap(text1 string, text2 string) int {445 // Cache the text lengths to prevent multiple calls.446 text1Length := len(text1)447 text2Length := len(text2)448 // Eliminate the null case.449 if text1Length == 0 || text2Length == 0 {450 return 0451 }452 // Truncate the longer string.453 if text1Length > text2Length {454 text1 = text1[text1Length-text2Length:]455 } else if text1Length < text2Length {456 text2 = text2[0:text1Length]457 }458 textLength := int(math.Min(float64(text1Length), float64(text2Length)))459 // Quick check for the worst case.460 if text1 == text2 {461 return textLength462 }463 // 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/464 best := 0465 length := 1466 for {467 pattern := text1[textLength-length:]468 found := strings.Index(text2, pattern)469 if found == -1 {470 break471 }472 length += found473 if found == 0 || text1[textLength-length:] == text2[0:length] {474 best = length475 length++476 }477 }478 return best479}480// 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.481func (dmp *DiffMatchPatch) DiffHalfMatch(text1, text2 string) []string {482 // Unused in this code, but retained for interface compatibility.483 runeSlices := dmp.diffHalfMatch([]rune(text1), []rune(text2))484 if runeSlices == nil {485 return nil486 }487 result := make([]string, len(runeSlices))488 for i, r := range runeSlices {489 result[i] = string(r)490 }491 return result492}493func (dmp *DiffMatchPatch) diffHalfMatch(text1, text2 []rune) [][]rune {494 if dmp.DiffTimeout <= 0 {495 // Don't risk returning a non-optimal diff if we have unlimited time.496 return nil497 }498 var longtext, shorttext []rune499 if len(text1) > len(text2) {500 longtext = text1501 shorttext = text2502 } else {503 longtext = text2504 shorttext = text1505 }506 if len(longtext) < 4 || len(shorttext)*2 < len(longtext) {507 return nil // Pointless.508 }509 // First check if the second quarter is the seed for a half-match.510 hm1 := dmp.diffHalfMatchI(longtext, shorttext, int(float64(len(longtext)+3)/4))511 // Check again based on the third quarter.512 hm2 := dmp.diffHalfMatchI(longtext, shorttext, int(float64(len(longtext)+1)/2))513 hm := [][]rune{}514 if hm1 == nil && hm2 == nil {515 return nil516 } else if hm2 == nil {517 hm = hm1518 } else if hm1 == nil {519 hm = hm2520 } else {521 // Both matched. Select the longest.522 if len(hm1[4]) > len(hm2[4]) {523 hm = hm1524 } else {525 hm = hm2526 }527 }528 // A half-match was found, sort out the return data.529 if len(text1) > len(text2) {530 return hm531 }532 return [][]rune{hm[2], hm[3], hm[0], hm[1], hm[4]}533}534// diffHalfMatchI checks if a substring of shorttext exist within longtext such that the substring is at least half the length of longtext?535// Returns a slice 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.536func (dmp *DiffMatchPatch) diffHalfMatchI(l, s []rune, i int) [][]rune {537 var bestCommonA []rune538 var bestCommonB []rune539 var bestCommonLen int540 var bestLongtextA []rune541 var bestLongtextB []rune542 var bestShorttextA []rune543 var bestShorttextB []rune544 // Start with a 1/4 length substring at position i as a seed.545 seed := l[i : i+len(l)/4]546 for j := runesIndexOf(s, seed, 0); j != -1; j = runesIndexOf(s, seed, j+1) {547 prefixLength := commonPrefixLength(l[i:], s[j:])548 suffixLength := commonSuffixLength(l[:i], s[:j])549 if bestCommonLen < suffixLength+prefixLength {550 bestCommonA = s[j-suffixLength : j]551 bestCommonB = s[j : j+prefixLength]552 bestCommonLen = len(bestCommonA) + len(bestCommonB)553 bestLongtextA = l[:i-suffixLength]554 bestLongtextB = l[i+prefixLength:]555 bestShorttextA = s[:j-suffixLength]556 bestShorttextB = s[j+prefixLength:]557 }558 }559 if bestCommonLen*2 < len(l) {560 return nil561 }562 return [][]rune{563 bestLongtextA,564 bestLongtextB,565 bestShorttextA,566 bestShorttextB,567 append(bestCommonA, bestCommonB...),568 }569}570// DiffCleanupSemantic reduces the number of edits by eliminating semantically trivial equalities.571func (dmp *DiffMatchPatch) DiffCleanupSemantic(diffs []Diff) []Diff {572 changes := false573 // Stack of indices where equalities are found.574 equalities := make([]int, 0, len(diffs))575 var lastequality string576 // Always equal to diffs[equalities[equalitiesLength - 1]][1]577 var pointer int // Index of current position.578 // Number of characters that changed prior to the equality.579 var lengthInsertions1, lengthDeletions1 int580 // Number of characters that changed after the equality.581 var lengthInsertions2, lengthDeletions2 int582 for pointer < len(diffs) {583 if diffs[pointer].Type == DiffEqual {584 // Equality found.585 equalities = append(equalities, pointer)586 lengthInsertions1 = lengthInsertions2587 lengthDeletions1 = lengthDeletions2588 lengthInsertions2 = 0589 lengthDeletions2 = 0590 lastequality = diffs[pointer].Text591 } else {592 // An insertion or deletion.593 if diffs[pointer].Type == DiffInsert {594 lengthInsertions2 += len(diffs[pointer].Text)595 } else {596 lengthDeletions2 += len(diffs[pointer].Text)597 }598 // Eliminate an equality that is smaller or equal to the edits on both sides of it.599 difference1 := int(math.Max(float64(lengthInsertions1), float64(lengthDeletions1)))600 difference2 := int(math.Max(float64(lengthInsertions2), float64(lengthDeletions2)))601 if len(lastequality) > 0 &&602 (len(lastequality) <= difference1) &&603 (len(lastequality) <= difference2) {604 // Duplicate record.605 insPoint := equalities[len(equalities)-1]606 diffs = splice(diffs, insPoint, 0, Diff{DiffDelete, lastequality})607 // Change second copy to insert.608 diffs[insPoint+1].Type = DiffInsert609 // Throw away the equality we just deleted.610 equalities = equalities[:len(equalities)-1]611 if len(equalities) > 0 {612 equalities = equalities[:len(equalities)-1]613 }614 pointer = -1615 if len(equalities) > 0 {616 pointer = equalities[len(equalities)-1]617 }618 lengthInsertions1 = 0 // Reset the counters.619 lengthDeletions1 = 0620 lengthInsertions2 = 0621 lengthDeletions2 = 0622 lastequality = ""623 changes = true624 }625 }626 pointer++627 }628 // Normalize the diff.629 if changes {630 diffs = dmp.DiffCleanupMerge(diffs)631 }632 diffs = dmp.DiffCleanupSemanticLossless(diffs)633 // Find any overlaps between deletions and insertions.634 // e.g: <del>abcxxx</del><ins>xxxdef</ins>635 // -> <del>abc</del>xxx<ins>def</ins>636 // e.g: <del>xxxabc</del><ins>defxxx</ins>637 // -> <ins>def</ins>xxx<del>abc</del>638 // Only extract an overlap if it is as big as the edit ahead or behind it.639 pointer = 1640 for pointer < len(diffs) {641 if diffs[pointer-1].Type == DiffDelete &&642 diffs[pointer].Type == DiffInsert {643 deletion := diffs[pointer-1].Text644 insertion := diffs[pointer].Text645 overlapLength1 := dmp.DiffCommonOverlap(deletion, insertion)646 overlapLength2 := dmp.DiffCommonOverlap(insertion, deletion)647 if overlapLength1 >= overlapLength2 {648 if float64(overlapLength1) >= float64(len(deletion))/2 ||649 float64(overlapLength1) >= float64(len(insertion))/2 {650 // Overlap found. Insert an equality and trim the surrounding edits.651 diffs = splice(diffs, pointer, 0, Diff{DiffEqual, insertion[:overlapLength1]})652 diffs[pointer-1].Text =653 deletion[0 : len(deletion)-overlapLength1]654 diffs[pointer+1].Text = insertion[overlapLength1:]655 pointer++656 }657 } else {658 if float64(overlapLength2) >= float64(len(deletion))/2 ||659 float64(overlapLength2) >= float64(len(insertion))/2 {660 // Reverse overlap found. Insert an equality and swap and trim the surrounding edits.661 overlap := Diff{DiffEqual, deletion[:overlapLength2]}662 diffs = splice(diffs, pointer, 0, overlap)663 diffs[pointer-1].Type = DiffInsert664 diffs[pointer-1].Text = insertion[0 : len(insertion)-overlapLength2]665 diffs[pointer+1].Type = DiffDelete666 diffs[pointer+1].Text = deletion[overlapLength2:]667 pointer++668 }669 }670 pointer++671 }672 pointer++673 }674 return diffs675}676// Define some regex patterns for matching boundaries.677var (678 nonAlphaNumericRegex = regexp.MustCompile(`[^a-zA-Z0-9]`)679 whitespaceRegex = regexp.MustCompile(`\s`)680 linebreakRegex = regexp.MustCompile(`[\r\n]`)681 blanklineEndRegex = regexp.MustCompile(`\n\r?\n$`)682 blanklineStartRegex = regexp.MustCompile(`^\r?\n\r?\n`)683)684// diffCleanupSemanticScore computes a score representing whether the internal boundary falls on logical boundaries.685// Scores range from 6 (best) to 0 (worst). Closure, but does not reference any external variables.686func diffCleanupSemanticScore(one, two string) int {687 if len(one) == 0 || len(two) == 0 {688 // Edges are the best.689 return 6690 }691 // 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.692 rune1, _ := utf8.DecodeLastRuneInString(one)693 rune2, _ := utf8.DecodeRuneInString(two)694 char1 := string(rune1)695 char2 := string(rune2)696 nonAlphaNumeric1 := nonAlphaNumericRegex.MatchString(char1)697 nonAlphaNumeric2 := nonAlphaNumericRegex.MatchString(char2)698 whitespace1 := nonAlphaNumeric1 && whitespaceRegex.MatchString(char1)699 whitespace2 := nonAlphaNumeric2 && whitespaceRegex.MatchString(char2)700 lineBreak1 := whitespace1 && linebreakRegex.MatchString(char1)701 lineBreak2 := whitespace2 && linebreakRegex.MatchString(char2)702 blankLine1 := lineBreak1 && blanklineEndRegex.MatchString(one)703 blankLine2 := lineBreak2 && blanklineEndRegex.MatchString(two)704 if blankLine1 || blankLine2 {705 // Five points for blank lines.706 return 5707 } else if lineBreak1 || lineBreak2 {708 // Four points for line breaks.709 return 4710 } else if nonAlphaNumeric1 && !whitespace1 && whitespace2 {711 // Three points for end of sentences.712 return 3713 } else if whitespace1 || whitespace2 {714 // Two points for whitespace.715 return 2716 } else if nonAlphaNumeric1 || nonAlphaNumeric2 {717 // One point for non-alphanumeric.718 return 1719 }720 return 0721}722// DiffCleanupSemanticLossless looks for single edits surrounded on both sides by equalities which can be shifted sideways to align the edit to a word boundary.723// E.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.724func (dmp *DiffMatchPatch) DiffCleanupSemanticLossless(diffs []Diff) []Diff {725 pointer := 1726 // Intentionally ignore the first and last element (don't need checking).727 for pointer < len(diffs)-1 {728 if diffs[pointer-1].Type == DiffEqual &&729 diffs[pointer+1].Type == DiffEqual {730 // This is a single edit surrounded by equalities.731 equality1 := diffs[pointer-1].Text732 edit := diffs[pointer].Text733 equality2 := diffs[pointer+1].Text734 // First, shift the edit as far left as possible.735 commonOffset := dmp.DiffCommonSuffix(equality1, edit)736 if commonOffset > 0 {737 commonString := edit[len(edit)-commonOffset:]738 equality1 = equality1[0 : len(equality1)-commonOffset]739 edit = commonString + edit[:len(edit)-commonOffset]740 equality2 = commonString + equality2741 }742 // Second, step character by character right, looking for the best fit.743 bestEquality1 := equality1744 bestEdit := edit745 bestEquality2 := equality2746 bestScore := diffCleanupSemanticScore(equality1, edit) +747 diffCleanupSemanticScore(edit, equality2)748 for len(edit) != 0 && len(equality2) != 0 {749 _, sz := utf8.DecodeRuneInString(edit)...

Full Screen

Full Screen

difflayer_test.go

Source:difflayer_test.go Github

copy

Full Screen

1// Copyright 2019 The go-ethereum Authors2// This file is part of the go-ethereum library.3//4// The go-ethereum library is free software: you can redistribute it and/or modify5// it under the terms of the GNU Lesser General Public License as published by6// the Free Software Foundation, either version 3 of the License, or7// (at your option) any later version.8//9// The go-ethereum library is distributed in the hope that it will be useful,10// but WITHOUT ANY WARRANTY; without even the implied warranty of11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the12// GNU Lesser General Public License for more details.13//14// You should have received a copy of the GNU Lesser General Public License15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.16package snapshot17import (18 "bytes"19 "math/rand"20 "testing"21 "github.com/VictoriaMetrics/fastcache"22 "github.com/ethereum/go-ethereum/common"23 "github.com/ethereum/go-ethereum/crypto"24 "github.com/ethereum/go-ethereum/ethdb/memorydb"25)26func copyDestructs(destructs map[common.Hash]struct{}) map[common.Hash]struct{} {27 copy := make(map[common.Hash]struct{})28 for hash := range destructs {29 copy[hash] = struct{}{}30 }31 return copy32}33func copyAccounts(accounts map[common.Hash][]byte) map[common.Hash][]byte {34 copy := make(map[common.Hash][]byte)35 for hash, blob := range accounts {36 copy[hash] = blob37 }38 return copy39}40func copyStorage(storage map[common.Hash]map[common.Hash][]byte) map[common.Hash]map[common.Hash][]byte {41 copy := make(map[common.Hash]map[common.Hash][]byte)42 for accHash, slots := range storage {43 copy[accHash] = make(map[common.Hash][]byte)44 for slotHash, blob := range slots {45 copy[accHash][slotHash] = blob46 }47 }48 return copy49}50// TestMergeBasics tests some simple merges51func TestMergeBasics(t *testing.T) {52 var (53 destructs = make(map[common.Hash]struct{})54 accounts = make(map[common.Hash][]byte)55 storage = make(map[common.Hash]map[common.Hash][]byte)56 )57 // Fill up a parent58 for i := 0; i < 100; i++ {59 h := randomHash()60 data := randomAccount()61 accounts[h] = data62 if rand.Intn(4) == 0 {63 destructs[h] = struct{}{}64 }65 if rand.Intn(2) == 0 {66 accStorage := make(map[common.Hash][]byte)67 value := make([]byte, 32)68 rand.Read(value)69 accStorage[randomHash()] = value70 storage[h] = accStorage71 }72 }73 // Add some (identical) layers on top74 parent := newDiffLayer(emptyLayer(), common.Hash{}, copyDestructs(destructs), copyAccounts(accounts), copyStorage(storage))75 child := newDiffLayer(parent, common.Hash{}, copyDestructs(destructs), copyAccounts(accounts), copyStorage(storage))76 child = newDiffLayer(child, common.Hash{}, copyDestructs(destructs), copyAccounts(accounts), copyStorage(storage))77 child = newDiffLayer(child, common.Hash{}, copyDestructs(destructs), copyAccounts(accounts), copyStorage(storage))78 child = newDiffLayer(child, common.Hash{}, copyDestructs(destructs), copyAccounts(accounts), copyStorage(storage))79 // And flatten80 merged := (child.flatten()).(*diffLayer)81 { // Check account lists82 if have, want := len(merged.accountList), 0; have != want {83 t.Errorf("accountList wrong: have %v, want %v", have, want)84 }85 if have, want := len(merged.AccountList()), len(accounts); have != want {86 t.Errorf("AccountList() wrong: have %v, want %v", have, want)87 }88 if have, want := len(merged.accountList), len(accounts); have != want {89 t.Errorf("accountList [2] wrong: have %v, want %v", have, want)90 }91 }92 { // Check account drops93 if have, want := len(merged.destructSet), len(destructs); have != want {94 t.Errorf("accountDrop wrong: have %v, want %v", have, want)95 }96 }97 { // Check storage lists98 i := 099 for aHash, sMap := range storage {100 if have, want := len(merged.storageList), i; have != want {101 t.Errorf("[1] storageList wrong: have %v, want %v", have, want)102 }103 list, _ := merged.StorageList(aHash)104 if have, want := len(list), len(sMap); have != want {105 t.Errorf("[2] StorageList() wrong: have %v, want %v", have, want)106 }107 if have, want := len(merged.storageList[aHash]), len(sMap); have != want {108 t.Errorf("storageList wrong: have %v, want %v", have, want)109 }110 i++111 }112 }113}114// TestMergeDelete tests some deletion115func TestMergeDelete(t *testing.T) {116 var (117 storage = make(map[common.Hash]map[common.Hash][]byte)118 )119 // Fill up a parent120 h1 := common.HexToHash("0x01")121 h2 := common.HexToHash("0x02")122 flipDrops := func() map[common.Hash]struct{} {123 return map[common.Hash]struct{}{124 h2: {},125 }126 }127 flipAccs := func() map[common.Hash][]byte {128 return map[common.Hash][]byte{129 h1: randomAccount(),130 }131 }132 flopDrops := func() map[common.Hash]struct{} {133 return map[common.Hash]struct{}{134 h1: {},135 }136 }137 flopAccs := func() map[common.Hash][]byte {138 return map[common.Hash][]byte{139 h2: randomAccount(),140 }141 }142 // Add some flipAccs-flopping layers on top143 parent := newDiffLayer(emptyLayer(), common.Hash{}, flipDrops(), flipAccs(), storage)144 child := parent.Update(common.Hash{}, flopDrops(), flopAccs(), storage)145 child = child.Update(common.Hash{}, flipDrops(), flipAccs(), storage)146 child = child.Update(common.Hash{}, flopDrops(), flopAccs(), storage)147 child = child.Update(common.Hash{}, flipDrops(), flipAccs(), storage)148 child = child.Update(common.Hash{}, flopDrops(), flopAccs(), storage)149 child = child.Update(common.Hash{}, flipDrops(), flipAccs(), storage)150 if data, _ := child.Account(h1); data == nil {151 t.Errorf("last diff layer: expected %x account to be non-nil", h1)152 }153 if data, _ := child.Account(h2); data != nil {154 t.Errorf("last diff layer: expected %x account to be nil", h2)155 }156 if _, ok := child.destructSet[h1]; ok {157 t.Errorf("last diff layer: expected %x drop to be missing", h1)158 }159 if _, ok := child.destructSet[h2]; !ok {160 t.Errorf("last diff layer: expected %x drop to be present", h1)161 }162 // And flatten163 merged := (child.flatten()).(*diffLayer)164 if data, _ := merged.Account(h1); data == nil {165 t.Errorf("merged layer: expected %x account to be non-nil", h1)166 }167 if data, _ := merged.Account(h2); data != nil {168 t.Errorf("merged layer: expected %x account to be nil", h2)169 }170 if _, ok := merged.destructSet[h1]; !ok { // Note, drops stay alive until persisted to disk!171 t.Errorf("merged diff layer: expected %x drop to be present", h1)172 }173 if _, ok := merged.destructSet[h2]; !ok { // Note, drops stay alive until persisted to disk!174 t.Errorf("merged diff layer: expected %x drop to be present", h1)175 }176 // If we add more granular metering of memory, we can enable this again,177 // but it's not implemented for now178 //if have, want := merged.memory, child.memory; have != want {179 // t.Errorf("mem wrong: have %d, want %d", have, want)180 //}181}182// This tests that if we create a new account, and set a slot, and then merge183// it, the lists will be correct.184func TestInsertAndMerge(t *testing.T) {185 // Fill up a parent186 var (187 acc = common.HexToHash("0x01")188 slot = common.HexToHash("0x02")189 parent *diffLayer190 child *diffLayer191 )192 {193 var (194 destructs = make(map[common.Hash]struct{})195 accounts = make(map[common.Hash][]byte)196 storage = make(map[common.Hash]map[common.Hash][]byte)197 )198 parent = newDiffLayer(emptyLayer(), common.Hash{}, destructs, accounts, storage)199 }200 {201 var (202 destructs = make(map[common.Hash]struct{})203 accounts = make(map[common.Hash][]byte)204 storage = make(map[common.Hash]map[common.Hash][]byte)205 )206 accounts[acc] = randomAccount()207 storage[acc] = make(map[common.Hash][]byte)208 storage[acc][slot] = []byte{0x01}209 child = newDiffLayer(parent, common.Hash{}, destructs, accounts, storage)210 }211 // And flatten212 merged := (child.flatten()).(*diffLayer)213 { // Check that slot value is present214 have, _ := merged.Storage(acc, slot)215 if want := []byte{0x01}; !bytes.Equal(have, want) {216 t.Errorf("merged slot value wrong: have %x, want %x", have, want)217 }218 }219}220func emptyLayer() *diskLayer {221 return &diskLayer{222 diskdb: memorydb.New(),223 cache: fastcache.New(500 * 1024),224 }225}226// BenchmarkSearch checks how long it takes to find a non-existing key227// BenchmarkSearch-6 200000 10481 ns/op (1K per layer)228// BenchmarkSearch-6 200000 10760 ns/op (10K per layer)229// BenchmarkSearch-6 100000 17866 ns/op230//231// BenchmarkSearch-6 500000 3723 ns/op (10k per layer, only top-level RLock()232func BenchmarkSearch(b *testing.B) {233 // First, we set up 128 diff layers, with 1K items each234 fill := func(parent snapshot) *diffLayer {235 var (236 destructs = make(map[common.Hash]struct{})237 accounts = make(map[common.Hash][]byte)238 storage = make(map[common.Hash]map[common.Hash][]byte)239 )240 for i := 0; i < 10000; i++ {241 accounts[randomHash()] = randomAccount()242 }243 return newDiffLayer(parent, common.Hash{}, destructs, accounts, storage)244 }245 var layer snapshot246 layer = emptyLayer()247 for i := 0; i < 128; i++ {248 layer = fill(layer)249 }250 key := crypto.Keccak256Hash([]byte{0x13, 0x38})251 b.ResetTimer()252 for i := 0; i < b.N; i++ {253 layer.AccountRLP(key)254 }255}256// BenchmarkSearchSlot checks how long it takes to find a non-existing key257// - Number of layers: 128258// - Each layers contains the account, with a couple of storage slots259// BenchmarkSearchSlot-6 100000 14554 ns/op260// BenchmarkSearchSlot-6 100000 22254 ns/op (when checking parent root using mutex)261// BenchmarkSearchSlot-6 100000 14551 ns/op (when checking parent number using atomic)262// With bloom filter:263// BenchmarkSearchSlot-6 3467835 351 ns/op264func BenchmarkSearchSlot(b *testing.B) {265 // First, we set up 128 diff layers, with 1K items each266 accountKey := crypto.Keccak256Hash([]byte{0x13, 0x37})267 storageKey := crypto.Keccak256Hash([]byte{0x13, 0x37})268 accountRLP := randomAccount()269 fill := func(parent snapshot) *diffLayer {270 var (271 destructs = make(map[common.Hash]struct{})272 accounts = make(map[common.Hash][]byte)273 storage = make(map[common.Hash]map[common.Hash][]byte)274 )275 accounts[accountKey] = accountRLP276 accStorage := make(map[common.Hash][]byte)277 for i := 0; i < 5; i++ {278 value := make([]byte, 32)279 rand.Read(value)280 accStorage[randomHash()] = value281 storage[accountKey] = accStorage282 }283 return newDiffLayer(parent, common.Hash{}, destructs, accounts, storage)284 }285 var layer snapshot286 layer = emptyLayer()287 for i := 0; i < 128; i++ {288 layer = fill(layer)289 }290 b.ResetTimer()291 for i := 0; i < b.N; i++ {292 layer.Storage(accountKey, storageKey)293 }294}295// With accountList and sorting296// BenchmarkFlatten-6 50 29890856 ns/op297//298// Without sorting and tracking accountList299// BenchmarkFlatten-6 300 5511511 ns/op300func BenchmarkFlatten(b *testing.B) {301 fill := func(parent snapshot) *diffLayer {302 var (303 destructs = make(map[common.Hash]struct{})304 accounts = make(map[common.Hash][]byte)305 storage = make(map[common.Hash]map[common.Hash][]byte)306 )307 for i := 0; i < 100; i++ {308 accountKey := randomHash()309 accounts[accountKey] = randomAccount()310 accStorage := make(map[common.Hash][]byte)311 for i := 0; i < 20; i++ {312 value := make([]byte, 32)313 rand.Read(value)314 accStorage[randomHash()] = value315 }316 storage[accountKey] = accStorage317 }318 return newDiffLayer(parent, common.Hash{}, destructs, accounts, storage)319 }320 b.ResetTimer()321 for i := 0; i < b.N; i++ {322 b.StopTimer()323 var layer snapshot324 layer = emptyLayer()325 for i := 1; i < 128; i++ {326 layer = fill(layer)327 }328 b.StartTimer()329 for i := 1; i < 128; i++ {330 dl, ok := layer.(*diffLayer)331 if !ok {332 break333 }334 layer = dl.flatten()335 }336 b.StopTimer()337 }338}339// This test writes ~324M of diff layers to disk, spread over340// - 128 individual layers,341// - each with 200 accounts342// - containing 200 slots343//344// BenchmarkJournal-6 1 1471373923 ns/ops345// BenchmarkJournal-6 1 1208083335 ns/op // bufio writer346func BenchmarkJournal(b *testing.B) {347 fill := func(parent snapshot) *diffLayer {348 var (349 destructs = make(map[common.Hash]struct{})350 accounts = make(map[common.Hash][]byte)351 storage = make(map[common.Hash]map[common.Hash][]byte)352 )353 for i := 0; i < 200; i++ {354 accountKey := randomHash()355 accounts[accountKey] = randomAccount()356 accStorage := make(map[common.Hash][]byte)357 for i := 0; i < 200; i++ {358 value := make([]byte, 32)359 rand.Read(value)360 accStorage[randomHash()] = value361 }362 storage[accountKey] = accStorage363 }364 return newDiffLayer(parent, common.Hash{}, destructs, accounts, storage)365 }366 layer := snapshot(new(diskLayer))367 for i := 1; i < 128; i++ {368 layer = fill(layer)369 }370 b.ResetTimer()371 for i := 0; i < b.N; i++ {372 layer.Journal(new(bytes.Buffer))373 }374}...

Full Screen

Full Screen

Common

Using AI Code Generation

copy

Full Screen

1import "fmt"2func main() {3 d.Common()4}5import "fmt"6func main() {7 d.Common()8}9import "fmt"10func main() {11 d.Common()12}13import "fmt"14func main() {15 d.Common()16}17import "fmt"18func main() {19 d.Common()20}21import "fmt"22func main() {23 d.Common()24}25import "fmt"26func main() {27 d.Common()28}29import "fmt"30func main() {31 d.Common()32}33import "fmt"34func main() {35 d.Common()36}37import "fmt"38func main() {39 d.Common()40}41import "fmt"42func main() {43 d.Common()44}45import "fmt"46func main() {47 d.Common()48}49import "fmt"50func main() {51 d.Common()52}53import

Full Screen

Full Screen

Common

Using AI Code Generation

copy

Full Screen

1func main() {2 c.Method()3}4func main() {5 c.Method()6}7func main() {8 c.Method()9}10func main() {11 c.Method()12}13func main() {14 c.Method()15}16func main() {17 c.Method()18}19func main() {20 c.Method()21}22func main() {23 c.Method()24}25func main() {26 c.Method()27}28func main() {29 c.Method()30}31func main() {32 c.Method()33}34func main() {35 c.Method()36}37func main() {38 c.Method()39}40func main() {41 c.Method()42}43func main() {44 c.Method()45}46func main() {47 c.Method()48}

Full Screen

Full Screen

Common

Using AI Code Generation

copy

Full Screen

1import (2func main() {3 fmt.Println(diff.Common())4}5func Common() string {6}7func Diff2() string {8}

Full Screen

Full Screen

Common

Using AI Code Generation

copy

Full Screen

1import (2func main() {3 fmt.Println("Hello, World!")4 c := Common{}5 c.Method1()6 c.Method2()7 c.Method3()8}9import (10func main() {11 fmt.Println("Hello, World!")12 c := Common{}13 c.Method1()14 c.Method2()15 c.Method3()16}17import (18func main() {19 fmt.Println("Hello, World!")20 c := Common{}21 c.Method1()22 c.Method2()23 c.Method3()24}25import (26func main() {27 fmt.Println("Hello, World!")28 c := Common{}29 c.Method1()30 c.Method2()31 c.Method3()32}33import (34func main() {35 fmt.Println("Hello, World!")36 c := Common{}37 c.Method1()38 c.Method2()39 c.Method3()40}41import (42func main() {43 fmt.Println("Hello, World!")44 c := Common{}45 c.Method1()46 c.Method2()47 c.Method3()48}49import (50func main() {51 fmt.Println("Hello, World!")52 c := Common{}53 c.Method1()54 c.Method2()55 c.Method3()56}57import (58func main() {59 fmt.Println("Hello, World!")60 c := Common{}61 c.Method1()62 c.Method2()63 c.Method3()64}65import (66func main() {67 fmt.Println("Hello, World!")68 c := Common{}69 c.Method1()70 c.Method2()71 c.Method3()72}73import (74func main()

Full Screen

Full Screen

Common

Using AI Code Generation

copy

Full Screen

1import (2func main() {3 fmt.Println(diff.Common())4}5import (6func main() {7 fmt.Println(diff.Common())8}9import (10func main() {11 fmt.Println(diff.Common())12}13import (14func main() {15 fmt.Println(diff.Common())16}17import (18func main() {19 fmt.Println(diff.Common())20}21import (22func main() {23 fmt.Println(diff.Common())24}25import (26func main() {27 fmt.Println(diff.Common())28}29import (30func main() {31 fmt.Println(diff.Common())32}33import (34func main() {35 fmt.Println(diff.Common())36}37import (38func main() {39 fmt.Println(diff.Common())40}

Full Screen

Full Screen

Common

Using AI Code Generation

copy

Full Screen

1import (2func main() {3 fmt.Println("Hello, playground")4 obj := diff.Diff{}5 obj.Common()6}7import "fmt"8type Diff struct {9}10func (d *Diff) Common() {11 fmt.Println("Common method of diff class")12}

Full Screen

Full Screen

Common

Using AI Code Generation

copy

Full Screen

1import (2func main() {3 d1 := diff{10, 20}4 d1.Common()5 d2 := diff{100, 200}6 d2.Common()7}

Full Screen

Full Screen

Automation Testing Tutorials

Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.

LambdaTest Learning Hubs:

YouTube

You could also refer to video tutorials over LambdaTest YouTube channel to get step by step demonstration from industry experts.

Run Got automation tests on LambdaTest cloud grid

Perform automation testing on 3000+ real desktop and mobile devices online.

... View sample repo... View DocumentationSign up Free
›
_

Most used method in

Try LambdaTest Now !!

Get 100 minutes of automation test minutes FREE!!

...
Sign up with GoogleSign up with Email
Next-Gen App & Browser Testing Cloud

Was this article helpful?

Helpful

NotHelpful