main
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(rune(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}