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.

Try LambdaTest Now !!

Get 100 minutes of automation test minutes FREE!!

Next-Gen App & Browser Testing Cloud

Was this article helpful?

Helpful

NotHelpful