1// Copyright (c) 2012-2016 The go-diff authors. All rights reserved.
2// https://github.com/sergi/go-diff
3// See the included LICENSE file for license details.
4//
5// go-diff is a Go implementation of Google's Diff, Match, and Patch library
6// Original library is Copyright (c) 2006 Google Inc.
7// http://code.google.com/p/google-diff-match-patch/
8
9package diffmatchpatch
10
11import (
12	"bytes"
13	"errors"
14	"math"
15	"net/url"
16	"regexp"
17	"strconv"
18	"strings"
19)
20
21// Patch represents one patch operation.
22type Patch struct {
23	diffs   []Diff
24	Start1  int
25	Start2  int
26	Length1 int
27	Length2 int
28}
29
30// String emulates GNU diff's format.
31// Header: @@ -382,8 +481,9 @@
32// Indices are printed as 1-based, not 0-based.
33func (p *Patch) String() string {
34	var coords1, coords2 string
35
36	if p.Length1 == 0 {
37		coords1 = strconv.Itoa(p.Start1) + ",0"
38	} else if p.Length1 == 1 {
39		coords1 = strconv.Itoa(p.Start1 + 1)
40	} else {
41		coords1 = strconv.Itoa(p.Start1+1) + "," + strconv.Itoa(p.Length1)
42	}
43
44	if p.Length2 == 0 {
45		coords2 = strconv.Itoa(p.Start2) + ",0"
46	} else if p.Length2 == 1 {
47		coords2 = strconv.Itoa(p.Start2 + 1)
48	} else {
49		coords2 = strconv.Itoa(p.Start2+1) + "," + strconv.Itoa(p.Length2)
50	}
51
52	var text bytes.Buffer
53	_, _ = text.WriteString("@@ -" + coords1 + " +" + coords2 + " @@\n")
54
55	// Escape the body of the patch with %xx notation.
56	for _, aDiff := range p.diffs {
57		switch aDiff.Type {
58		case DiffInsert:
59			_, _ = text.WriteString("+")
60		case DiffDelete:
61			_, _ = text.WriteString("-")
62		case DiffEqual:
63			_, _ = text.WriteString(" ")
64		}
65
66		_, _ = text.WriteString(strings.Replace(url.QueryEscape(aDiff.Text), "+", " ", -1))
67		_, _ = text.WriteString("\n")
68	}
69
70	return unescaper.Replace(text.String())
71}
72
73// PatchAddContext increases the context until it is unique, but doesn't let the pattern expand beyond MatchMaxBits.
74func (dmp *DiffMatchPatch) PatchAddContext(patch Patch, text string) Patch {
75	if len(text) == 0 {
76		return patch
77	}
78
79	pattern := text[patch.Start2 : patch.Start2+patch.Length1]
80	padding := 0
81
82	// Look for the first and last matches of pattern in text.  If two different matches are found, increase the pattern length.
83	for strings.Index(text, pattern) != strings.LastIndex(text, pattern) &&
84		len(pattern) < dmp.MatchMaxBits-2*dmp.PatchMargin {
85		padding += dmp.PatchMargin
86		maxStart := max(0, patch.Start2-padding)
87		minEnd := min(len(text), patch.Start2+patch.Length1+padding)
88		pattern = text[maxStart:minEnd]
89	}
90	// Add one chunk for good luck.
91	padding += dmp.PatchMargin
92
93	// Add the prefix.
94	prefix := text[max(0, patch.Start2-padding):patch.Start2]
95	if len(prefix) != 0 {
96		patch.diffs = append([]Diff{Diff{DiffEqual, prefix}}, patch.diffs...)
97	}
98	// Add the suffix.
99	suffix := text[patch.Start2+patch.Length1 : min(len(text), patch.Start2+patch.Length1+padding)]
100	if len(suffix) != 0 {
101		patch.diffs = append(patch.diffs, Diff{DiffEqual, suffix})
102	}
103
104	// Roll back the start points.
105	patch.Start1 -= len(prefix)
106	patch.Start2 -= len(prefix)
107	// Extend the lengths.
108	patch.Length1 += len(prefix) + len(suffix)
109	patch.Length2 += len(prefix) + len(suffix)
110
111	return patch
112}
113
114// PatchMake computes a list of patches.
115func (dmp *DiffMatchPatch) PatchMake(opt ...interface{}) []Patch {
116	if len(opt) == 1 {
117		diffs, _ := opt[0].([]Diff)
118		text1 := dmp.DiffText1(diffs)
119		return dmp.PatchMake(text1, diffs)
120	} else if len(opt) == 2 {
121		text1 := opt[0].(string)
122		switch t := opt[1].(type) {
123		case string:
124			diffs := dmp.DiffMain(text1, t, true)
125			if len(diffs) > 2 {
126				diffs = dmp.DiffCleanupSemantic(diffs)
127				diffs = dmp.DiffCleanupEfficiency(diffs)
128			}
129			return dmp.PatchMake(text1, diffs)
130		case []Diff:
131			return dmp.patchMake2(text1, t)
132		}
133	} else if len(opt) == 3 {
134		return dmp.PatchMake(opt[0], opt[2])
135	}
136	return []Patch{}
137}
138
139// patchMake2 computes a list of patches to turn text1 into text2.
140// text2 is not provided, diffs are the delta between text1 and text2.
141func (dmp *DiffMatchPatch) patchMake2(text1 string, diffs []Diff) []Patch {
142	// Check for null inputs not needed since null can't be passed in C#.
143	patches := []Patch{}
144	if len(diffs) == 0 {
145		return patches // Get rid of the null case.
146	}
147
148	patch := Patch{}
149	charCount1 := 0 // Number of characters into the text1 string.
150	charCount2 := 0 // Number of characters into the text2 string.
151	// Start with text1 (prepatchText) and apply the diffs until we arrive at text2 (postpatchText). We recreate the patches one by one to determine context info.
152	prepatchText := text1
153	postpatchText := text1
154
155	for i, aDiff := range diffs {
156		if len(patch.diffs) == 0 && aDiff.Type != DiffEqual {
157			// A new patch starts here.
158			patch.Start1 = charCount1
159			patch.Start2 = charCount2
160		}
161
162		switch aDiff.Type {
163		case DiffInsert:
164			patch.diffs = append(patch.diffs, aDiff)
165			patch.Length2 += len(aDiff.Text)
166			postpatchText = postpatchText[:charCount2] +
167				aDiff.Text + postpatchText[charCount2:]
168		case DiffDelete:
169			patch.Length1 += len(aDiff.Text)
170			patch.diffs = append(patch.diffs, aDiff)
171			postpatchText = postpatchText[:charCount2] + postpatchText[charCount2+len(aDiff.Text):]
172		case DiffEqual:
173			if len(aDiff.Text) <= 2*dmp.PatchMargin &&
174				len(patch.diffs) != 0 && i != len(diffs)-1 {
175				// Small equality inside a patch.
176				patch.diffs = append(patch.diffs, aDiff)
177				patch.Length1 += len(aDiff.Text)
178				patch.Length2 += len(aDiff.Text)
179			}
180			if len(aDiff.Text) >= 2*dmp.PatchMargin {
181				// Time for a new patch.
182				if len(patch.diffs) != 0 {
183					patch = dmp.PatchAddContext(patch, prepatchText)
184					patches = append(patches, patch)
185					patch = Patch{}
186					// Unlike Unidiff, our patch lists have a rolling context. http://code.google.com/p/google-diff-match-patch/wiki/Unidiff Update prepatch text & pos to reflect the application of the just completed patch.
187					prepatchText = postpatchText
188					charCount1 = charCount2
189				}
190			}
191		}
192
193		// Update the current character count.
194		if aDiff.Type != DiffInsert {
195			charCount1 += len(aDiff.Text)
196		}
197		if aDiff.Type != DiffDelete {
198			charCount2 += len(aDiff.Text)
199		}
200	}
201
202	// Pick up the leftover patch if not empty.
203	if len(patch.diffs) != 0 {
204		patch = dmp.PatchAddContext(patch, prepatchText)
205		patches = append(patches, patch)
206	}
207
208	return patches
209}
210
211// PatchDeepCopy returns an array that is identical to a given an array of patches.
212func (dmp *DiffMatchPatch) PatchDeepCopy(patches []Patch) []Patch {
213	patchesCopy := []Patch{}
214	for _, aPatch := range patches {
215		patchCopy := Patch{}
216		for _, aDiff := range aPatch.diffs {
217			patchCopy.diffs = append(patchCopy.diffs, Diff{
218				aDiff.Type,
219				aDiff.Text,
220			})
221		}
222		patchCopy.Start1 = aPatch.Start1
223		patchCopy.Start2 = aPatch.Start2
224		patchCopy.Length1 = aPatch.Length1
225		patchCopy.Length2 = aPatch.Length2
226		patchesCopy = append(patchesCopy, patchCopy)
227	}
228	return patchesCopy
229}
230
231// PatchApply merges a set of patches onto the text.  Returns a patched text, as well as an array of true/false values indicating which patches were applied.
232func (dmp *DiffMatchPatch) PatchApply(patches []Patch, text string) (string, []bool) {
233	if len(patches) == 0 {
234		return text, []bool{}
235	}
236
237	// Deep copy the patches so that no changes are made to originals.
238	patches = dmp.PatchDeepCopy(patches)
239
240	nullPadding := dmp.PatchAddPadding(patches)
241	text = nullPadding + text + nullPadding
242	patches = dmp.PatchSplitMax(patches)
243
244	x := 0
245	// delta keeps track of the offset between the expected and actual location of the previous patch.  If there are patches expected at positions 10 and 20, but the first patch was found at 12, delta is 2 and the second patch has an effective expected position of 22.
246	delta := 0
247	results := make([]bool, len(patches))
248	for _, aPatch := range patches {
249		expectedLoc := aPatch.Start2 + delta
250		text1 := dmp.DiffText1(aPatch.diffs)
251		var startLoc int
252		endLoc := -1
253		if len(text1) > dmp.MatchMaxBits {
254			// PatchSplitMax will only provide an oversized pattern in the case of a monster delete.
255			startLoc = dmp.MatchMain(text, text1[:dmp.MatchMaxBits], expectedLoc)
256			if startLoc != -1 {
257				endLoc = dmp.MatchMain(text,
258					text1[len(text1)-dmp.MatchMaxBits:], expectedLoc+len(text1)-dmp.MatchMaxBits)
259				if endLoc == -1 || startLoc >= endLoc {
260					// Can't find valid trailing context.  Drop this patch.
261					startLoc = -1
262				}
263			}
264		} else {
265			startLoc = dmp.MatchMain(text, text1, expectedLoc)
266		}
267		if startLoc == -1 {
268			// No match found.  :(
269			results[x] = false
270			// Subtract the delta for this failed patch from subsequent patches.
271			delta -= aPatch.Length2 - aPatch.Length1
272		} else {
273			// Found a match.  :)
274			results[x] = true
275			delta = startLoc - expectedLoc
276			var text2 string
277			if endLoc == -1 {
278				text2 = text[startLoc:int(math.Min(float64(startLoc+len(text1)), float64(len(text))))]
279			} else {
280				text2 = text[startLoc:int(math.Min(float64(endLoc+dmp.MatchMaxBits), float64(len(text))))]
281			}
282			if text1 == text2 {
283				// Perfect match, just shove the Replacement text in.
284				text = text[:startLoc] + dmp.DiffText2(aPatch.diffs) + text[startLoc+len(text1):]
285			} else {
286				// Imperfect match.  Run a diff to get a framework of equivalent indices.
287				diffs := dmp.DiffMain(text1, text2, false)
288				if len(text1) > dmp.MatchMaxBits && float64(dmp.DiffLevenshtein(diffs))/float64(len(text1)) > dmp.PatchDeleteThreshold {
289					// The end points match, but the content is unacceptably bad.
290					results[x] = false
291				} else {
292					diffs = dmp.DiffCleanupSemanticLossless(diffs)
293					index1 := 0
294					for _, aDiff := range aPatch.diffs {
295						if aDiff.Type != DiffEqual {
296							index2 := dmp.DiffXIndex(diffs, index1)
297							if aDiff.Type == DiffInsert {
298								// Insertion
299								text = text[:startLoc+index2] + aDiff.Text + text[startLoc+index2:]
300							} else if aDiff.Type == DiffDelete {
301								// Deletion
302								startIndex := startLoc + index2
303								text = text[:startIndex] +
304									text[startIndex+dmp.DiffXIndex(diffs, index1+len(aDiff.Text))-index2:]
305							}
306						}
307						if aDiff.Type != DiffDelete {
308							index1 += len(aDiff.Text)
309						}
310					}
311				}
312			}
313		}
314		x++
315	}
316	// Strip the padding off.
317	text = text[len(nullPadding) : len(nullPadding)+(len(text)-2*len(nullPadding))]
318	return text, results
319}
320
321// PatchAddPadding adds some padding on text start and end so that edges can match something.
322// Intended to be called only from within patchApply.
323func (dmp *DiffMatchPatch) PatchAddPadding(patches []Patch) string {
324	paddingLength := dmp.PatchMargin
325	nullPadding := ""
326	for x := 1; x <= paddingLength; x++ {
327		nullPadding += string(x)
328	}
329
330	// Bump all the patches forward.
331	for i := range patches {
332		patches[i].Start1 += paddingLength
333		patches[i].Start2 += paddingLength
334	}
335
336	// Add some padding on start of first diff.
337	if len(patches[0].diffs) == 0 || patches[0].diffs[0].Type != DiffEqual {
338		// Add nullPadding equality.
339		patches[0].diffs = append([]Diff{Diff{DiffEqual, nullPadding}}, patches[0].diffs...)
340		patches[0].Start1 -= paddingLength // Should be 0.
341		patches[0].Start2 -= paddingLength // Should be 0.
342		patches[0].Length1 += paddingLength
343		patches[0].Length2 += paddingLength
344	} else if paddingLength > len(patches[0].diffs[0].Text) {
345		// Grow first equality.
346		extraLength := paddingLength - len(patches[0].diffs[0].Text)
347		patches[0].diffs[0].Text = nullPadding[len(patches[0].diffs[0].Text):] + patches[0].diffs[0].Text
348		patches[0].Start1 -= extraLength
349		patches[0].Start2 -= extraLength
350		patches[0].Length1 += extraLength
351		patches[0].Length2 += extraLength
352	}
353
354	// Add some padding on end of last diff.
355	last := len(patches) - 1
356	if len(patches[last].diffs) == 0 || patches[last].diffs[len(patches[last].diffs)-1].Type != DiffEqual {
357		// Add nullPadding equality.
358		patches[last].diffs = append(patches[last].diffs, Diff{DiffEqual, nullPadding})
359		patches[last].Length1 += paddingLength
360		patches[last].Length2 += paddingLength
361	} else if paddingLength > len(patches[last].diffs[len(patches[last].diffs)-1].Text) {
362		// Grow last equality.
363		lastDiff := patches[last].diffs[len(patches[last].diffs)-1]
364		extraLength := paddingLength - len(lastDiff.Text)
365		patches[last].diffs[len(patches[last].diffs)-1].Text += nullPadding[:extraLength]
366		patches[last].Length1 += extraLength
367		patches[last].Length2 += extraLength
368	}
369
370	return nullPadding
371}
372
373// PatchSplitMax looks through the patches and breaks up any which are longer than the maximum limit of the match algorithm.
374// Intended to be called only from within patchApply.
375func (dmp *DiffMatchPatch) PatchSplitMax(patches []Patch) []Patch {
376	patchSize := dmp.MatchMaxBits
377	for x := 0; x < len(patches); x++ {
378		if patches[x].Length1 <= patchSize {
379			continue
380		}
381		bigpatch := patches[x]
382		// Remove the big old patch.
383		patches = append(patches[:x], patches[x+1:]...)
384		x--
385
386		Start1 := bigpatch.Start1
387		Start2 := bigpatch.Start2
388		precontext := ""
389		for len(bigpatch.diffs) != 0 {
390			// Create one of several smaller patches.
391			patch := Patch{}
392			empty := true
393			patch.Start1 = Start1 - len(precontext)
394			patch.Start2 = Start2 - len(precontext)
395			if len(precontext) != 0 {
396				patch.Length1 = len(precontext)
397				patch.Length2 = len(precontext)
398				patch.diffs = append(patch.diffs, Diff{DiffEqual, precontext})
399			}
400			for len(bigpatch.diffs) != 0 && patch.Length1 < patchSize-dmp.PatchMargin {
401				diffType := bigpatch.diffs[0].Type
402				diffText := bigpatch.diffs[0].Text
403				if diffType == DiffInsert {
404					// Insertions are harmless.
405					patch.Length2 += len(diffText)
406					Start2 += len(diffText)
407					patch.diffs = append(patch.diffs, bigpatch.diffs[0])
408					bigpatch.diffs = bigpatch.diffs[1:]
409					empty = false
410				} else if diffType == DiffDelete && len(patch.diffs) == 1 && patch.diffs[0].Type == DiffEqual && len(diffText) > 2*patchSize {
411					// This is a large deletion.  Let it pass in one chunk.
412					patch.Length1 += len(diffText)
413					Start1 += len(diffText)
414					empty = false
415					patch.diffs = append(patch.diffs, Diff{diffType, diffText})
416					bigpatch.diffs = bigpatch.diffs[1:]
417				} else {
418					// Deletion or equality.  Only take as much as we can stomach.
419					diffText = diffText[:min(len(diffText), patchSize-patch.Length1-dmp.PatchMargin)]
420
421					patch.Length1 += len(diffText)
422					Start1 += len(diffText)
423					if diffType == DiffEqual {
424						patch.Length2 += len(diffText)
425						Start2 += len(diffText)
426					} else {
427						empty = false
428					}
429					patch.diffs = append(patch.diffs, Diff{diffType, diffText})
430					if diffText == bigpatch.diffs[0].Text {
431						bigpatch.diffs = bigpatch.diffs[1:]
432					} else {
433						bigpatch.diffs[0].Text =
434							bigpatch.diffs[0].Text[len(diffText):]
435					}
436				}
437			}
438			// Compute the head context for the next patch.
439			precontext = dmp.DiffText2(patch.diffs)
440			precontext = precontext[max(0, len(precontext)-dmp.PatchMargin):]
441
442			postcontext := ""
443			// Append the end context for this patch.
444			if len(dmp.DiffText1(bigpatch.diffs)) > dmp.PatchMargin {
445				postcontext = dmp.DiffText1(bigpatch.diffs)[:dmp.PatchMargin]
446			} else {
447				postcontext = dmp.DiffText1(bigpatch.diffs)
448			}
449
450			if len(postcontext) != 0 {
451				patch.Length1 += len(postcontext)
452				patch.Length2 += len(postcontext)
453				if len(patch.diffs) != 0 && patch.diffs[len(patch.diffs)-1].Type == DiffEqual {
454					patch.diffs[len(patch.diffs)-1].Text += postcontext
455				} else {
456					patch.diffs = append(patch.diffs, Diff{DiffEqual, postcontext})
457				}
458			}
459			if !empty {
460				x++
461				patches = append(patches[:x], append([]Patch{patch}, patches[x:]...)...)
462			}
463		}
464	}
465	return patches
466}
467
468// PatchToText takes a list of patches and returns a textual representation.
469func (dmp *DiffMatchPatch) PatchToText(patches []Patch) string {
470	var text bytes.Buffer
471	for _, aPatch := range patches {
472		_, _ = text.WriteString(aPatch.String())
473	}
474	return text.String()
475}
476
477// PatchFromText parses a textual representation of patches and returns a List of Patch objects.
478func (dmp *DiffMatchPatch) PatchFromText(textline string) ([]Patch, error) {
479	patches := []Patch{}
480	if len(textline) == 0 {
481		return patches, nil
482	}
483	text := strings.Split(textline, "\n")
484	textPointer := 0
485	patchHeader := regexp.MustCompile("^@@ -(\\d+),?(\\d*) \\+(\\d+),?(\\d*) @@$")
486
487	var patch Patch
488	var sign uint8
489	var line string
490	for textPointer < len(text) {
491
492		if !patchHeader.MatchString(text[textPointer]) {
493			return patches, errors.New("Invalid patch string: " + text[textPointer])
494		}
495
496		patch = Patch{}
497		m := patchHeader.FindStringSubmatch(text[textPointer])
498
499		patch.Start1, _ = strconv.Atoi(m[1])
500		if len(m[2]) == 0 {
501			patch.Start1--
502			patch.Length1 = 1
503		} else if m[2] == "0" {
504			patch.Length1 = 0
505		} else {
506			patch.Start1--
507			patch.Length1, _ = strconv.Atoi(m[2])
508		}
509
510		patch.Start2, _ = strconv.Atoi(m[3])
511
512		if len(m[4]) == 0 {
513			patch.Start2--
514			patch.Length2 = 1
515		} else if m[4] == "0" {
516			patch.Length2 = 0
517		} else {
518			patch.Start2--
519			patch.Length2, _ = strconv.Atoi(m[4])
520		}
521		textPointer++
522
523		for textPointer < len(text) {
524			if len(text[textPointer]) > 0 {
525				sign = text[textPointer][0]
526			} else {
527				textPointer++
528				continue
529			}
530
531			line = text[textPointer][1:]
532			line = strings.Replace(line, "+", "%2b", -1)
533			line, _ = url.QueryUnescape(line)
534			if sign == '-' {
535				// Deletion.
536				patch.diffs = append(patch.diffs, Diff{DiffDelete, line})
537			} else if sign == '+' {
538				// Insertion.
539				patch.diffs = append(patch.diffs, Diff{DiffInsert, line})
540			} else if sign == ' ' {
541				// Minor equality.
542				patch.diffs = append(patch.diffs, Diff{DiffEqual, line})
543			} else if sign == '@' {
544				// Start of next patch.
545				break
546			} else {
547				// WTF?
548				return patches, errors.New("Invalid patch mode '" + string(sign) + "' in: " + string(line))
549			}
550			textPointer++
551		}
552
553		patches = append(patches, patch)
554	}
555	return patches, nil
556}
557