.config/coc/extensions/coc-go-data/tools/pkg/mod/github.com/sergi/go-diff@v1.1.0/diffmatchpatch/patch.go

   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
   9 package diffmatchpatch
  10
  11 import (
  12         "bytes"
  13         "errors"
  14         "math"
  15         "net/url"
  16         "regexp"
  17         "strconv"
  18         "strings"
  19 )
  20
  21 // Patch represents one patch operation.
  22 type 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.
  33 func (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.
  74 func (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.
 115 func (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.
 141 func (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.
 212 func (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.
 232 func (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.
 323 func (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.
 375 func (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.
 469 func (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.
 478 func (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 }