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