12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216 |
- package diffmatchpatch
- import (
- "bytes"
- "errors"
- "fmt"
- "html"
- "math"
- "net/url"
- "regexp"
- "strconv"
- "strings"
- "time"
- "unicode/utf8"
- )
- type Operation int8
- const (
- DiffDelete Operation = -1
- DiffInsert Operation = 1
- DiffEqual Operation = 0
- )
- var unescaper = strings.NewReplacer(
- "%21", "!", "%7E", "~", "%27", "'",
- "%28", "(", "%29", ")", "%3B", ";",
- "%2F", "/", "%3F", "?", "%3A", ":",
- "%40", "@", "%26", "&", "%3D", "=",
- "%2B", "+", "%24", "$", "%2C", ",", "%23", "#", "%2A", "*")
- var (
- nonAlphaNumericRegex_ = regexp.MustCompile(`[^a-zA-Z0-9]`)
- whitespaceRegex_ = regexp.MustCompile(`\s`)
- linebreakRegex_ = regexp.MustCompile(`[\r\n]`)
- blanklineEndRegex_ = regexp.MustCompile(`\n\r?\n$`)
- blanklineStartRegex_ = regexp.MustCompile(`^\r?\n\r?\n`)
- )
- func splice(slice []Diff, index int, amount int, elements ...Diff) []Diff {
- return append(slice[:index], append(elements, slice[index+amount:]...)...)
- }
- func indexOf(str string, pattern string, i int) int {
- if i > len(str)-1 {
- return -1
- }
- if i <= 0 {
- return strings.Index(str, pattern)
- }
- ind := strings.Index(str[i:], pattern)
- if ind == -1 {
- return -1
- }
- return ind + i
- }
- func lastIndexOf(str string, pattern string, i int) int {
- if i < 0 {
- return -1
- }
- if i >= len(str) {
- return strings.LastIndex(str, pattern)
- }
- _, size := utf8.DecodeRuneInString(str[i:])
- return strings.LastIndex(str[:i+size], pattern)
- }
- func runesIndexOf(target, pattern []rune, i int) int {
- if i > len(target)-1 {
- return -1
- }
- if i <= 0 {
- return runesIndex(target, pattern)
- }
- ind := runesIndex(target[i:], pattern)
- if ind == -1 {
- return -1
- }
- return ind + i
- }
- func min(x, y int) int {
- if x < y {
- return x
- }
- return y
- }
- func max(x, y int) int {
- if x > y {
- return x
- }
- return y
- }
- func runesEqual(r1, r2 []rune) bool {
- if len(r1) != len(r2) {
- return false
- }
- for i, c := range r1 {
- if c != r2[i] {
- return false
- }
- }
- return true
- }
- func runesIndex(r1, r2 []rune) int {
- last := len(r1) - len(r2)
- for i := 0; i <= last; i++ {
- if runesEqual(r1[i:i+len(r2)], r2) {
- return i
- }
- }
- return -1
- }
- type Diff struct {
- Type Operation
- Text string
- }
- type Patch struct {
- diffs []Diff
- start1 int
- start2 int
- length1 int
- length2 int
- }
- func (p *Patch) String() string {
- var coords1, coords2 string
- if p.length1 == 0 {
- coords1 = strconv.Itoa(p.start1) + ",0"
- } else if p.length1 == 1 {
- coords1 = strconv.Itoa(p.start1 + 1)
- } else {
- coords1 = strconv.Itoa(p.start1+1) + "," + strconv.Itoa(p.length1)
- }
- if p.length2 == 0 {
- coords2 = strconv.Itoa(p.start2) + ",0"
- } else if p.length2 == 1 {
- coords2 = strconv.Itoa(p.start2 + 1)
- } else {
- coords2 = strconv.Itoa(p.start2+1) + "," + strconv.Itoa(p.length2)
- }
- var text bytes.Buffer
- text.WriteString("@@ -" + coords1 + " +" + coords2 + " @@\n")
-
- for _, aDiff := range p.diffs {
- switch aDiff.Type {
- case DiffInsert:
- text.WriteString("+")
- case DiffDelete:
- text.WriteString("-")
- case DiffEqual:
- text.WriteString(" ")
- }
- text.WriteString(strings.Replace(url.QueryEscape(aDiff.Text), "+", " ", -1))
- text.WriteString("\n")
- }
- return unescaper.Replace(text.String())
- }
- type DiffMatchPatch struct {
-
- DiffTimeout time.Duration
-
- DiffEditCost int
-
-
-
- MatchDistance int
-
-
-
-
- PatchDeleteThreshold float64
-
- PatchMargin int
-
- MatchMaxBits int
-
- MatchThreshold float64
- }
- func New() *DiffMatchPatch {
-
- return &DiffMatchPatch{
- DiffTimeout: time.Second,
- DiffEditCost: 4,
- MatchThreshold: 0.5,
- MatchDistance: 1000,
- PatchDeleteThreshold: 0.5,
- PatchMargin: 4,
- MatchMaxBits: 32,
- }
- }
- func (dmp *DiffMatchPatch) DiffMain(text1, text2 string, checklines bool) []Diff {
- var deadline time.Time
- if dmp.DiffTimeout <= 0 {
- deadline = time.Now().Add(24 * 365 * time.Hour)
- } else {
- deadline = time.Now().Add(dmp.DiffTimeout)
- }
- return dmp.diffMain(text1, text2, checklines, deadline)
- }
- func (dmp *DiffMatchPatch) diffMain(text1, text2 string, checklines bool, deadline time.Time) []Diff {
- return dmp.diffMainRunes([]rune(text1), []rune(text2), checklines, deadline)
- }
- func (dmp *DiffMatchPatch) DiffMainRunes(text1, text2 []rune, checklines bool) []Diff {
- var deadline time.Time
- if dmp.DiffTimeout <= 0 {
- deadline = time.Now().Add(24 * 365 * time.Hour)
- } else {
- deadline = time.Now().Add(dmp.DiffTimeout)
- }
- return dmp.diffMainRunes(text1, text2, checklines, deadline)
- }
- func (dmp *DiffMatchPatch) diffMainRunes(text1, text2 []rune, checklines bool, deadline time.Time) []Diff {
- if runesEqual(text1, text2) {
- var diffs []Diff
- if len(text1) > 0 {
- diffs = append(diffs, Diff{DiffEqual, string(text1)})
- }
- return diffs
- }
-
- commonlength := commonPrefixLength(text1, text2)
- commonprefix := text1[:commonlength]
- text1 = text1[commonlength:]
- text2 = text2[commonlength:]
-
- commonlength = commonSuffixLength(text1, text2)
- commonsuffix := text1[len(text1)-commonlength:]
- text1 = text1[:len(text1)-commonlength]
- text2 = text2[:len(text2)-commonlength]
-
- diffs := dmp.diffCompute(text1, text2, checklines, deadline)
-
- if len(commonprefix) != 0 {
- diffs = append([]Diff{Diff{DiffEqual, string(commonprefix)}}, diffs...)
- }
- if len(commonsuffix) != 0 {
- diffs = append(diffs, Diff{DiffEqual, string(commonsuffix)})
- }
- return dmp.DiffCleanupMerge(diffs)
- }
- func (dmp *DiffMatchPatch) diffCompute(text1, text2 []rune, checklines bool, deadline time.Time) []Diff {
- diffs := []Diff{}
- if len(text1) == 0 {
-
- return append(diffs, Diff{DiffInsert, string(text2)})
- } else if len(text2) == 0 {
-
- return append(diffs, Diff{DiffDelete, string(text1)})
- }
- var longtext, shorttext []rune
- if len(text1) > len(text2) {
- longtext = text1
- shorttext = text2
- } else {
- longtext = text2
- shorttext = text1
- }
- if i := runesIndex(longtext, shorttext); i != -1 {
- op := DiffInsert
-
- if len(text1) > len(text2) {
- op = DiffDelete
- }
-
- return []Diff{
- Diff{op, string(longtext[:i])},
- Diff{DiffEqual, string(shorttext)},
- Diff{op, string(longtext[i+len(shorttext):])},
- }
- } else if len(shorttext) == 1 {
-
-
- return []Diff{
- Diff{DiffDelete, string(text1)},
- Diff{DiffInsert, string(text2)},
- }
-
- } else if hm := dmp.diffHalfMatch(text1, text2); hm != nil {
-
- text1_a := hm[0]
- text1_b := hm[1]
- text2_a := hm[2]
- text2_b := hm[3]
- mid_common := hm[4]
-
- diffs_a := dmp.diffMainRunes(text1_a, text2_a, checklines, deadline)
- diffs_b := dmp.diffMainRunes(text1_b, text2_b, checklines, deadline)
-
- return append(diffs_a, append([]Diff{Diff{DiffEqual, string(mid_common)}}, diffs_b...)...)
- } else if checklines && len(text1) > 100 && len(text2) > 100 {
- return dmp.diffLineMode(text1, text2, deadline)
- }
- return dmp.diffBisect(text1, text2, deadline)
- }
- func (dmp *DiffMatchPatch) diffLineMode(text1, text2 []rune, deadline time.Time) []Diff {
-
- text1, text2, linearray := dmp.diffLinesToRunes(text1, text2)
- diffs := dmp.diffMainRunes(text1, text2, false, deadline)
-
- diffs = dmp.DiffCharsToLines(diffs, linearray)
-
- diffs = dmp.DiffCleanupSemantic(diffs)
-
-
- diffs = append(diffs, Diff{DiffEqual, ""})
- pointer := 0
- count_delete := 0
- count_insert := 0
- text_delete := ""
- text_insert := ""
- for pointer < len(diffs) {
- switch diffs[pointer].Type {
- case DiffInsert:
- count_insert++
- text_insert += diffs[pointer].Text
- case DiffDelete:
- count_delete++
- text_delete += diffs[pointer].Text
- case DiffEqual:
-
- if count_delete >= 1 && count_insert >= 1 {
-
- diffs = splice(diffs, pointer-count_delete-count_insert,
- count_delete+count_insert)
- pointer = pointer - count_delete - count_insert
- a := dmp.diffMain(text_delete, text_insert, false, deadline)
- for j := len(a) - 1; j >= 0; j-- {
- diffs = splice(diffs, pointer, 0, a[j])
- }
- pointer = pointer + len(a)
- }
- count_insert = 0
- count_delete = 0
- text_delete = ""
- text_insert = ""
- }
- pointer++
- }
- return diffs[:len(diffs)-1]
- }
- func (dmp *DiffMatchPatch) DiffBisect(text1, text2 string, deadline time.Time) []Diff {
-
- return dmp.diffBisect([]rune(text1), []rune(text2), deadline)
- }
- func (dmp *DiffMatchPatch) diffBisect(runes1, runes2 []rune, deadline time.Time) []Diff {
-
- runes1_len, runes2_len := len(runes1), len(runes2)
- max_d := (runes1_len + runes2_len + 1) / 2
- v_offset := max_d
- v_length := 2 * max_d
- v1 := make([]int, v_length)
- v2 := make([]int, v_length)
- for i := range v1 {
- v1[i] = -1
- v2[i] = -1
- }
- v1[v_offset+1] = 0
- v2[v_offset+1] = 0
- delta := runes1_len - runes2_len
-
-
- front := (delta%2 != 0)
-
-
- k1start := 0
- k1end := 0
- k2start := 0
- k2end := 0
- for d := 0; d < max_d; d++ {
-
- if time.Now().After(deadline) {
- break
- }
-
- for k1 := -d + k1start; k1 <= d-k1end; k1 += 2 {
- k1_offset := v_offset + k1
- var x1 int
- if k1 == -d || (k1 != d && v1[k1_offset-1] < v1[k1_offset+1]) {
- x1 = v1[k1_offset+1]
- } else {
- x1 = v1[k1_offset-1] + 1
- }
- y1 := x1 - k1
- for x1 < runes1_len && y1 < runes2_len {
- if runes1[x1] != runes2[y1] {
- break
- }
- x1++
- y1++
- }
- v1[k1_offset] = x1
- if x1 > runes1_len {
-
- k1end += 2
- } else if y1 > runes2_len {
-
- k1start += 2
- } else if front {
- k2_offset := v_offset + delta - k1
- if k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1 {
-
- x2 := runes1_len - v2[k2_offset]
- if x1 >= x2 {
-
- return dmp.diffBisectSplit_(runes1, runes2, x1, y1, deadline)
- }
- }
- }
- }
-
- for k2 := -d + k2start; k2 <= d-k2end; k2 += 2 {
- k2_offset := v_offset + k2
- var x2 int
- if k2 == -d || (k2 != d && v2[k2_offset-1] < v2[k2_offset+1]) {
- x2 = v2[k2_offset+1]
- } else {
- x2 = v2[k2_offset-1] + 1
- }
- var y2 = x2 - k2
- for x2 < runes1_len && y2 < runes2_len {
- if runes1[runes1_len-x2-1] != runes2[runes2_len-y2-1] {
- break
- }
- x2++
- y2++
- }
- v2[k2_offset] = x2
- if x2 > runes1_len {
-
- k2end += 2
- } else if y2 > runes2_len {
-
- k2start += 2
- } else if !front {
- k1_offset := v_offset + delta - k2
- if k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1 {
- x1 := v1[k1_offset]
- y1 := v_offset + x1 - k1_offset
-
- x2 = runes1_len - x2
- if x1 >= x2 {
-
- return dmp.diffBisectSplit_(runes1, runes2, x1, y1, deadline)
- }
- }
- }
- }
- }
-
-
- return []Diff{
- Diff{DiffDelete, string(runes1)},
- Diff{DiffInsert, string(runes2)},
- }
- }
- func (dmp *DiffMatchPatch) diffBisectSplit_(runes1, runes2 []rune, x, y int,
- deadline time.Time) []Diff {
- runes1a := runes1[:x]
- runes2a := runes2[:y]
- runes1b := runes1[x:]
- runes2b := runes2[y:]
-
- diffs := dmp.diffMainRunes(runes1a, runes2a, false, deadline)
- diffsb := dmp.diffMainRunes(runes1b, runes2b, false, deadline)
- return append(diffs, diffsb...)
- }
- func (dmp *DiffMatchPatch) DiffLinesToChars(text1, text2 string) (string, string, []string) {
- chars1, chars2, lineArray := dmp.DiffLinesToRunes(text1, text2)
- return string(chars1), string(chars2), lineArray
- }
- func (dmp *DiffMatchPatch) DiffLinesToRunes(text1, text2 string) ([]rune, []rune, []string) {
-
-
- lineArray := []string{""}
- lineHash := map[string]int{}
- chars1 := dmp.diffLinesToRunesMunge(text1, &lineArray, lineHash)
- chars2 := dmp.diffLinesToRunesMunge(text2, &lineArray, lineHash)
- return chars1, chars2, lineArray
- }
- func (dmp *DiffMatchPatch) diffLinesToRunes(text1, text2 []rune) ([]rune, []rune, []string) {
- return dmp.DiffLinesToRunes(string(text1), string(text2))
- }
- func (dmp *DiffMatchPatch) diffLinesToRunesMunge(text string, lineArray *[]string, lineHash map[string]int) []rune {
-
-
-
- lineStart := 0
- lineEnd := -1
- runes := []rune{}
- for lineEnd < len(text)-1 {
- lineEnd = indexOf(text, "\n", lineStart)
- if lineEnd == -1 {
- lineEnd = len(text) - 1
- }
- line := text[lineStart : lineEnd+1]
- lineStart = lineEnd + 1
- lineValue_, ok := lineHash[line]
- if ok {
- runes = append(runes, rune(lineValue_))
- } else {
- *lineArray = append(*lineArray, line)
- lineHash[line] = len(*lineArray) - 1
- runes = append(runes, rune(len(*lineArray)-1))
- }
- }
- return runes
- }
- func (dmp *DiffMatchPatch) DiffCharsToLines(diffs []Diff, lineArray []string) []Diff {
- hydrated := make([]Diff, 0, len(diffs))
- for _, aDiff := range diffs {
- chars := aDiff.Text
- text := make([]string, len(chars))
- for i, r := range chars {
- text[i] = lineArray[r]
- }
- aDiff.Text = strings.Join(text, "")
- hydrated = append(hydrated, aDiff)
- }
- return hydrated
- }
- func (dmp *DiffMatchPatch) DiffCommonPrefix(text1, text2 string) int {
-
- return commonPrefixLength([]rune(text1), []rune(text2))
- }
- func (dmp *DiffMatchPatch) DiffCommonSuffix(text1, text2 string) int {
-
- return commonSuffixLength([]rune(text1), []rune(text2))
- }
- func commonPrefixLength(text1, text2 []rune) int {
- short, long := text1, text2
- if len(short) > len(long) {
- short, long = long, short
- }
- for i, r := range short {
- if r != long[i] {
- return i
- }
- }
- return len(short)
- }
- func commonSuffixLength(text1, text2 []rune) int {
- n := min(len(text1), len(text2))
- for i := 0; i < n; i++ {
- if text1[len(text1)-i-1] != text2[len(text2)-i-1] {
- return i
- }
- }
- return n
-
-
-
- }
- func (dmp *DiffMatchPatch) DiffCommonOverlap(text1 string, text2 string) int {
-
- text1_length := len(text1)
- text2_length := len(text2)
-
- if text1_length == 0 || text2_length == 0 {
- return 0
- }
-
- if text1_length > text2_length {
- text1 = text1[text1_length-text2_length:]
- } else if text1_length < text2_length {
- text2 = text2[0:text1_length]
- }
- text_length := int(math.Min(float64(text1_length), float64(text2_length)))
-
- if text1 == text2 {
- return text_length
- }
-
-
-
- best := 0
- length := 1
- for {
- pattern := text1[text_length-length:]
- found := strings.Index(text2, pattern)
- if found == -1 {
- return best
- }
- length += found
- if found == 0 || text1[text_length-length:] == text2[0:length] {
- best = length
- length++
- }
- }
- return 0
- }
- func (dmp *DiffMatchPatch) DiffHalfMatch(text1, text2 string) []string {
-
- runeSlices := dmp.diffHalfMatch([]rune(text1), []rune(text2))
- if runeSlices == nil {
- return nil
- }
- result := make([]string, len(runeSlices))
- for i, r := range runeSlices {
- result[i] = string(r)
- }
- return result
- }
- func (dmp *DiffMatchPatch) diffHalfMatch(text1, text2 []rune) [][]rune {
- if dmp.DiffTimeout <= 0 {
-
- return nil
- }
- var longtext, shorttext []rune
- if len(text1) > len(text2) {
- longtext = text1
- shorttext = text2
- } else {
- longtext = text2
- shorttext = text1
- }
- if len(longtext) < 4 || len(shorttext)*2 < len(longtext) {
- return nil
- }
-
- hm1 := dmp.diffHalfMatchI(longtext, shorttext, int(float64(len(longtext)+3)/4))
-
- hm2 := dmp.diffHalfMatchI(longtext, shorttext, int(float64(len(longtext)+1)/2))
- hm := [][]rune{}
- if hm1 == nil && hm2 == nil {
- return nil
- } else if hm2 == nil {
- hm = hm1
- } else if hm1 == nil {
- hm = hm2
- } else {
-
- if len(hm1[4]) > len(hm2[4]) {
- hm = hm1
- } else {
- hm = hm2
- }
- }
-
- if len(text1) > len(text2) {
- return hm
- } else {
- return [][]rune{hm[2], hm[3], hm[0], hm[1], hm[4]}
- }
- return nil
- }
- func (dmp *DiffMatchPatch) diffHalfMatchI(l, s []rune, i int) [][]rune {
-
- seed := l[i : i+len(l)/4]
- j := -1
- best_common := []rune{}
- best_longtext_a := []rune{}
- best_longtext_b := []rune{}
- best_shorttext_a := []rune{}
- best_shorttext_b := []rune{}
- if j < len(s) {
- j = runesIndexOf(s, seed, j+1)
- for {
- if j == -1 {
- break
- }
- prefixLength := commonPrefixLength(l[i:], s[j:])
- suffixLength := commonSuffixLength(l[:i], s[:j])
- if len(best_common) < suffixLength+prefixLength {
- best_common = concat(s[j-suffixLength:j], s[j:j+prefixLength])
- best_longtext_a = l[:i-suffixLength]
- best_longtext_b = l[i+prefixLength:]
- best_shorttext_a = s[:j-suffixLength]
- best_shorttext_b = s[j+prefixLength:]
- }
- j = runesIndexOf(s, seed, j+1)
- }
- }
- if len(best_common)*2 >= len(l) {
- return [][]rune{
- best_longtext_a,
- best_longtext_b,
- best_shorttext_a,
- best_shorttext_b,
- best_common,
- }
- }
- return nil
- }
- func concat(r1, r2 []rune) []rune {
- result := make([]rune, len(r1)+len(r2))
- copy(result, r1)
- copy(result[len(r1):], r2)
- return result
- }
- func (dmp *DiffMatchPatch) DiffCleanupSemantic(diffs []Diff) []Diff {
- changes := false
- equalities := new(Stack)
- var lastequality string
-
- var pointer int
-
- var length_insertions1, length_deletions1 int
-
- var length_insertions2, length_deletions2 int
- for pointer < len(diffs) {
- if diffs[pointer].Type == DiffEqual {
- equalities.Push(pointer)
- length_insertions1 = length_insertions2
- length_deletions1 = length_deletions2
- length_insertions2 = 0
- length_deletions2 = 0
- lastequality = diffs[pointer].Text
- } else {
- if diffs[pointer].Type == DiffInsert {
- length_insertions2 += len(diffs[pointer].Text)
- } else {
- length_deletions2 += len(diffs[pointer].Text)
- }
-
-
- _difference1 := int(math.Max(float64(length_insertions1), float64(length_deletions1)))
- _difference2 := int(math.Max(float64(length_insertions2), float64(length_deletions2)))
- if len(lastequality) > 0 &&
- (len(lastequality) <= _difference1) &&
- (len(lastequality) <= _difference2) {
-
- insPoint := equalities.Peek().(int)
- diffs = append(
- diffs[:insPoint],
- append([]Diff{Diff{DiffDelete, lastequality}}, diffs[insPoint:]...)...)
-
- diffs[insPoint+1].Type = DiffInsert
-
- equalities.Pop()
- if equalities.Len() > 0 {
- equalities.Pop()
- pointer = equalities.Peek().(int)
- } else {
- pointer = -1
- }
- length_insertions1 = 0
- length_deletions1 = 0
- length_insertions2 = 0
- length_deletions2 = 0
- lastequality = ""
- changes = true
- }
- }
- pointer++
- }
-
- if changes {
- diffs = dmp.DiffCleanupMerge(diffs)
- }
- diffs = dmp.DiffCleanupSemanticLossless(diffs)
-
-
-
-
-
-
- pointer = 1
- for pointer < len(diffs) {
- if diffs[pointer-1].Type == DiffDelete &&
- diffs[pointer].Type == DiffInsert {
- deletion := diffs[pointer-1].Text
- insertion := diffs[pointer].Text
- overlap_length1 := dmp.DiffCommonOverlap(deletion, insertion)
- overlap_length2 := dmp.DiffCommonOverlap(insertion, deletion)
- if overlap_length1 >= overlap_length2 {
- if float64(overlap_length1) >= float64(len(deletion))/2 ||
- float64(overlap_length1) >= float64(len(insertion))/2 {
-
- diffs = append(
- diffs[:pointer],
- append([]Diff{Diff{DiffEqual, insertion[:overlap_length1]}}, diffs[pointer:]...)...)
-
-
- diffs[pointer-1].Text =
- deletion[0 : len(deletion)-overlap_length1]
- diffs[pointer+1].Text = insertion[overlap_length1:]
- pointer++
- }
- } else {
- if float64(overlap_length2) >= float64(len(deletion))/2 ||
- float64(overlap_length2) >= float64(len(insertion))/2 {
-
-
- overlap := Diff{DiffEqual, insertion[overlap_length2:]}
- diffs = append(
- diffs[:pointer],
- append([]Diff{overlap}, diffs[pointer:]...)...)
-
-
- diffs[pointer-1].Type = DiffInsert
- diffs[pointer-1].Text = insertion[0 : len(insertion)-overlap_length2]
- diffs[pointer+1].Type = DiffDelete
- diffs[pointer+1].Text = deletion[overlap_length2:]
- pointer++
- }
- }
- pointer++
- }
- pointer++
- }
- return diffs
- }
- func (dmp *DiffMatchPatch) DiffCleanupSemanticLossless(diffs []Diff) []Diff {
-
- diffCleanupSemanticScore_ := func(one, two string) int {
- if len(one) == 0 || len(two) == 0 {
-
- return 6
- }
-
-
-
-
-
- rune1, _ := utf8.DecodeLastRuneInString(one)
- rune2, _ := utf8.DecodeRuneInString(two)
- char1 := string(rune1)
- char2 := string(rune2)
- nonAlphaNumeric1 := nonAlphaNumericRegex_.MatchString(char1)
- nonAlphaNumeric2 := nonAlphaNumericRegex_.MatchString(char2)
- whitespace1 := nonAlphaNumeric1 && whitespaceRegex_.MatchString(char1)
- whitespace2 := nonAlphaNumeric2 && whitespaceRegex_.MatchString(char2)
- lineBreak1 := whitespace1 && linebreakRegex_.MatchString(char1)
- lineBreak2 := whitespace2 && linebreakRegex_.MatchString(char2)
- blankLine1 := lineBreak1 && blanklineEndRegex_.MatchString(one)
- blankLine2 := lineBreak2 && blanklineEndRegex_.MatchString(two)
- if blankLine1 || blankLine2 {
-
- return 5
- } else if lineBreak1 || lineBreak2 {
-
- return 4
- } else if nonAlphaNumeric1 && !whitespace1 && whitespace2 {
-
- return 3
- } else if whitespace1 || whitespace2 {
-
- return 2
- } else if nonAlphaNumeric1 || nonAlphaNumeric2 {
-
- return 1
- }
- return 0
- }
- pointer := 1
-
- for pointer < len(diffs)-1 {
- if diffs[pointer-1].Type == DiffEqual &&
- diffs[pointer+1].Type == DiffEqual {
-
- equality1 := diffs[pointer-1].Text
- edit := diffs[pointer].Text
- equality2 := diffs[pointer+1].Text
-
- commonOffset := dmp.DiffCommonSuffix(equality1, edit)
- if commonOffset > 0 {
- commonString := edit[len(edit)-commonOffset:]
- equality1 = equality1[0 : len(equality1)-commonOffset]
- edit = commonString + edit[:len(edit)-commonOffset]
- equality2 = commonString + equality2
- }
-
- bestEquality1 := equality1
- bestEdit := edit
- bestEquality2 := equality2
- bestScore := diffCleanupSemanticScore_(equality1, edit) +
- diffCleanupSemanticScore_(edit, equality2)
- for len(edit) != 0 && len(equality2) != 0 {
- _, sz := utf8.DecodeRuneInString(edit)
- if len(equality2) < sz || edit[:sz] != equality2[:sz] {
- break
- }
- equality1 += edit[:sz]
- edit = edit[sz:] + equality2[:sz]
- equality2 = equality2[sz:]
- score := diffCleanupSemanticScore_(equality1, edit) +
- diffCleanupSemanticScore_(edit, equality2)
-
-
- if score >= bestScore {
- bestScore = score
- bestEquality1 = equality1
- bestEdit = edit
- bestEquality2 = equality2
- }
- }
- if diffs[pointer-1].Text != bestEquality1 {
-
- if len(bestEquality1) != 0 {
- diffs[pointer-1].Text = bestEquality1
- } else {
- diffs = splice(diffs, pointer-1, 1)
- pointer--
- }
- diffs[pointer].Text = bestEdit
- if len(bestEquality2) != 0 {
- diffs[pointer+1].Text = bestEquality2
- } else {
-
- diffs = append(diffs[:pointer+1], diffs[pointer+2:]...)
- pointer--
- }
- }
- }
- pointer++
- }
- return diffs
- }
- func (dmp *DiffMatchPatch) DiffCleanupEfficiency(diffs []Diff) []Diff {
- changes := false
-
- equalities := new(Stack)
-
- lastequality := ""
- pointer := 0
-
- pre_ins := false
-
- pre_del := false
-
- post_ins := false
-
- post_del := false
- for pointer < len(diffs) {
- if diffs[pointer].Type == DiffEqual {
- if len(diffs[pointer].Text) < dmp.DiffEditCost &&
- (post_ins || post_del) {
-
- equalities.Push(pointer)
- pre_ins = post_ins
- pre_del = post_del
- lastequality = diffs[pointer].Text
- } else {
-
- equalities.Clear()
- lastequality = ""
- }
- post_ins = false
- post_del = false
- } else {
- if diffs[pointer].Type == DiffDelete {
- post_del = true
- } else {
- post_ins = true
- }
-
- var sum_pres int
- if pre_ins {
- sum_pres++
- }
- if pre_del {
- sum_pres++
- }
- if post_ins {
- sum_pres++
- }
- if post_del {
- sum_pres++
- }
- if len(lastequality) > 0 &&
- ((pre_ins && pre_del && post_ins && post_del) ||
- ((len(lastequality) < dmp.DiffEditCost/2) && sum_pres == 3)) {
-
- diffs = append(diffs[:equalities.Peek().(int)],
- append([]Diff{Diff{DiffDelete, lastequality}}, diffs[equalities.Peek().(int):]...)...)
-
- diffs[equalities.Peek().(int)+1].Type = DiffInsert
- equalities.Pop()
- lastequality = ""
- if pre_ins && pre_del {
-
- post_ins = true
- post_del = true
- equalities.Clear()
- } else {
- if equalities.Len() > 0 {
- equalities.Pop()
- pointer = equalities.Peek().(int)
- } else {
- pointer = -1
- }
- post_ins = false
- post_del = false
- }
- changes = true
- }
- }
- pointer++
- }
- if changes {
- diffs = dmp.DiffCleanupMerge(diffs)
- }
- return diffs
- }
- func (dmp *DiffMatchPatch) DiffCleanupMerge(diffs []Diff) []Diff {
-
- diffs = append(diffs, Diff{DiffEqual, ""})
- pointer := 0
- count_delete := 0
- count_insert := 0
- commonlength := 0
- text_delete := ""
- text_insert := ""
- for pointer < len(diffs) {
- switch diffs[pointer].Type {
- case DiffInsert:
- count_insert += 1
- text_insert += diffs[pointer].Text
- pointer += 1
- break
- case DiffDelete:
- count_delete += 1
- text_delete += diffs[pointer].Text
- pointer += 1
- break
- case DiffEqual:
-
- if count_delete+count_insert > 1 {
- if count_delete != 0 && count_insert != 0 {
-
- commonlength = dmp.DiffCommonPrefix(text_insert, text_delete)
- if commonlength != 0 {
- x := pointer - count_delete - count_insert
- if x > 0 && diffs[x-1].Type == DiffEqual {
- diffs[x-1].Text += text_insert[:commonlength]
- } else {
- diffs = append([]Diff{Diff{DiffEqual, text_insert[:commonlength]}}, diffs...)
- pointer += 1
- }
- text_insert = text_insert[commonlength:]
- text_delete = text_delete[commonlength:]
- }
-
- commonlength = dmp.DiffCommonSuffix(text_insert, text_delete)
- if commonlength != 0 {
- insert_index := len(text_insert) - commonlength
- delete_index := len(text_delete) - commonlength
- diffs[pointer].Text = text_insert[insert_index:] + diffs[pointer].Text
- text_insert = text_insert[:insert_index]
- text_delete = text_delete[:delete_index]
- }
- }
-
- if count_delete == 0 {
- diffs = splice(diffs, pointer-count_insert,
- count_delete+count_insert,
- Diff{DiffInsert, text_insert})
- } else if count_insert == 0 {
- diffs = splice(diffs, pointer-count_delete,
- count_delete+count_insert,
- Diff{DiffDelete, text_delete})
- } else {
- diffs = splice(diffs, pointer-count_delete-count_insert,
- count_delete+count_insert,
- Diff{DiffDelete, text_delete},
- Diff{DiffInsert, text_insert})
- }
- pointer = pointer - count_delete - count_insert + 1
- if count_delete != 0 {
- pointer += 1
- }
- if count_insert != 0 {
- pointer += 1
- }
- } else if pointer != 0 && diffs[pointer-1].Type == DiffEqual {
-
- diffs[pointer-1].Text += diffs[pointer].Text
- diffs = append(diffs[:pointer], diffs[pointer+1:]...)
- } else {
- pointer++
- }
- count_insert = 0
- count_delete = 0
- text_delete = ""
- text_insert = ""
- break
- }
- }
- if len(diffs[len(diffs)-1].Text) == 0 {
- diffs = diffs[0 : len(diffs)-1]
- }
-
-
-
- changes := false
- pointer = 1
-
- for pointer < (len(diffs) - 1) {
- if diffs[pointer-1].Type == DiffEqual &&
- diffs[pointer+1].Type == DiffEqual {
-
- if strings.HasSuffix(diffs[pointer].Text, diffs[pointer-1].Text) {
-
- diffs[pointer].Text = diffs[pointer-1].Text +
- diffs[pointer].Text[:len(diffs[pointer].Text)-len(diffs[pointer-1].Text)]
- diffs[pointer+1].Text = diffs[pointer-1].Text + diffs[pointer+1].Text
- diffs = splice(diffs, pointer-1, 1)
- changes = true
- } else if strings.HasPrefix(diffs[pointer].Text, diffs[pointer+1].Text) {
-
- diffs[pointer-1].Text += diffs[pointer+1].Text
- diffs[pointer].Text =
- diffs[pointer].Text[len(diffs[pointer+1].Text):] + diffs[pointer+1].Text
- diffs = splice(diffs, pointer+1, 1)
- changes = true
- }
- }
- pointer++
- }
-
- if changes {
- diffs = dmp.DiffCleanupMerge(diffs)
- }
- return diffs
- }
- func (dmp *DiffMatchPatch) DiffXIndex(diffs []Diff, loc int) int {
- chars1 := 0
- chars2 := 0
- last_chars1 := 0
- last_chars2 := 0
- lastDiff := Diff{}
- for i := 0; i < len(diffs); i++ {
- aDiff := diffs[i]
- if aDiff.Type != DiffInsert {
-
- chars1 += len(aDiff.Text)
- }
- if aDiff.Type != DiffDelete {
-
- chars2 += len(aDiff.Text)
- }
- if chars1 > loc {
-
- lastDiff = aDiff
- break
- }
- last_chars1 = chars1
- last_chars2 = chars2
- }
- if lastDiff.Type == DiffDelete {
-
- return last_chars2
- }
-
- return last_chars2 + (loc - last_chars1)
- }
- func (dmp *DiffMatchPatch) DiffPrettyHtml(diffs []Diff) string {
- var buff bytes.Buffer
- for _, diff := range diffs {
- text := strings.Replace(html.EscapeString(diff.Text), "\n", "¶<br>", -1)
- switch diff.Type {
- case DiffInsert:
- buff.WriteString("<ins style=\"background:#e6ffe6;\">")
- buff.WriteString(text)
- buff.WriteString("</ins>")
- case DiffDelete:
- buff.WriteString("<del style=\"background:#ffe6e6;\">")
- buff.WriteString(text)
- buff.WriteString("</del>")
- case DiffEqual:
- buff.WriteString("<span>")
- buff.WriteString(text)
- buff.WriteString("</span>")
- }
- }
- return buff.String()
- }
- func (dmp *DiffMatchPatch) DiffText1(diffs []Diff) string {
-
- var text bytes.Buffer
- for _, aDiff := range diffs {
- if aDiff.Type != DiffInsert {
- text.WriteString(aDiff.Text)
- }
- }
- return text.String()
- }
- func (dmp *DiffMatchPatch) DiffText2(diffs []Diff) string {
- var text bytes.Buffer
- for _, aDiff := range diffs {
- if aDiff.Type != DiffDelete {
- text.WriteString(aDiff.Text)
- }
- }
- return text.String()
- }
- func (dmp *DiffMatchPatch) DiffLevenshtein(diffs []Diff) int {
- levenshtein := 0
- insertions := 0
- deletions := 0
- for _, aDiff := range diffs {
- switch aDiff.Type {
- case DiffInsert:
- insertions += len(aDiff.Text)
- case DiffDelete:
- deletions += len(aDiff.Text)
- case DiffEqual:
-
- levenshtein += max(insertions, deletions)
- insertions = 0
- deletions = 0
- }
- }
- levenshtein += max(insertions, deletions)
- return levenshtein
- }
- func (dmp *DiffMatchPatch) DiffToDelta(diffs []Diff) string {
- var text bytes.Buffer
- for _, aDiff := range diffs {
- switch aDiff.Type {
- case DiffInsert:
- text.WriteString("+")
- text.WriteString(strings.Replace(url.QueryEscape(aDiff.Text), "+", " ", -1))
- text.WriteString("\t")
- break
- case DiffDelete:
- text.WriteString("-")
- text.WriteString(strconv.Itoa(utf8.RuneCountInString(aDiff.Text)))
- text.WriteString("\t")
- break
- case DiffEqual:
- text.WriteString("=")
- text.WriteString(strconv.Itoa(utf8.RuneCountInString(aDiff.Text)))
- text.WriteString("\t")
- break
- }
- }
- delta := text.String()
- if len(delta) != 0 {
-
- delta = delta[0 : utf8.RuneCountInString(delta)-1]
- delta = unescaper.Replace(delta)
- }
- return delta
- }
- func (dmp *DiffMatchPatch) DiffFromDelta(text1, delta string) (diffs []Diff, err error) {
- diffs = []Diff{}
- defer func() {
- if r := recover(); r != nil {
- err = r.(error)
- }
- }()
- pointer := 0
- tokens := strings.Split(delta, "\t")
- for _, token := range tokens {
- if len(token) == 0 {
-
- continue
- }
-
-
- param := token[1:]
- switch op := token[0]; op {
- case '+':
-
- param = strings.Replace(param, "+", "%2b", -1)
- param, err = url.QueryUnescape(param)
- if err != nil {
- return nil, err
- }
- if !utf8.ValidString(param) {
- return nil, fmt.Errorf("invalid UTF-8 token: %q", param)
- }
- diffs = append(diffs, Diff{DiffInsert, param})
- case '=', '-':
- n, err := strconv.ParseInt(param, 10, 0)
- if err != nil {
- return diffs, err
- } else if n < 0 {
- return diffs, errors.New("Negative number in DiffFromDelta: " + param)
- }
-
- text := string([]rune(text1)[pointer : pointer+int(n)])
- pointer += int(n)
- if op == '=' {
- diffs = append(diffs, Diff{DiffEqual, text})
- } else {
- diffs = append(diffs, Diff{DiffDelete, text})
- }
- default:
-
- return diffs, errors.New("Invalid diff operation in DiffFromDelta: " + string(token[0]))
- }
- }
- if pointer != len([]rune(text1)) {
- return diffs, fmt.Errorf("Delta length (%v) smaller than source text length (%v)", pointer, len(text1))
- }
- return diffs, err
- }
- func (dmp *DiffMatchPatch) MatchMain(text, pattern string, loc int) int {
-
- loc = int(math.Max(0, math.Min(float64(loc), float64(len(text)))))
- if text == pattern {
-
- return 0
- } else if len(text) == 0 {
-
- return -1
- } else if loc+len(pattern) <= len(text) && text[loc:loc+len(pattern)] == pattern {
-
- return loc
- }
-
- return dmp.MatchBitap(text, pattern, loc)
- }
- func (dmp *DiffMatchPatch) MatchBitap(text, pattern string, loc int) int {
-
- s := dmp.MatchAlphabet(pattern)
-
- var score_threshold float64 = dmp.MatchThreshold
-
- best_loc := indexOf(text, pattern, loc)
- if best_loc != -1 {
- score_threshold = math.Min(dmp.matchBitapScore(0, best_loc, loc,
- pattern), score_threshold)
-
- best_loc = lastIndexOf(text, pattern, loc+len(pattern))
- if best_loc != -1 {
- score_threshold = math.Min(dmp.matchBitapScore(0, best_loc, loc,
- pattern), score_threshold)
- }
- }
-
- matchmask := 1 << uint((len(pattern) - 1))
- best_loc = -1
- var bin_min, bin_mid int
- bin_max := len(pattern) + len(text)
- last_rd := []int{}
- for d := 0; d < len(pattern); d++ {
-
-
-
- bin_min = 0
- bin_mid = bin_max
- for bin_min < bin_mid {
- if dmp.matchBitapScore(d, loc+bin_mid, loc, pattern) <= score_threshold {
- bin_min = bin_mid
- } else {
- bin_max = bin_mid
- }
- bin_mid = (bin_max-bin_min)/2 + bin_min
- }
-
- bin_max = bin_mid
- start := int(math.Max(1, float64(loc-bin_mid+1)))
- finish := int(math.Min(float64(loc+bin_mid), float64(len(text))) + float64(len(pattern)))
- rd := make([]int, finish+2)
- rd[finish+1] = (1 << uint(d)) - 1
- for j := finish; j >= start; j-- {
- var charMatch int
- if len(text) <= j-1 {
-
- charMatch = 0
- } else if _, ok := s[text[j-1]]; !ok {
- charMatch = 0
- } else {
- charMatch = s[text[j-1]]
- }
- if d == 0 {
-
- rd[j] = ((rd[j+1] << 1) | 1) & charMatch
- } else {
-
- rd[j] = ((rd[j+1]<<1)|1)&charMatch | (((last_rd[j+1] | last_rd[j]) << 1) | 1) | last_rd[j+1]
- }
- if (rd[j] & matchmask) != 0 {
- score := dmp.matchBitapScore(d, j-1, loc, pattern)
-
-
- if score <= score_threshold {
-
- score_threshold = score
- best_loc = j - 1
- if best_loc > loc {
-
- start = int(math.Max(1, float64(2*loc-best_loc)))
- } else {
-
- break
- }
- }
- }
- }
- if dmp.matchBitapScore(d+1, loc, loc, pattern) > score_threshold {
-
- break
- }
- last_rd = rd
- }
- return best_loc
- }
- func (dmp *DiffMatchPatch) matchBitapScore(e, x, loc int, pattern string) float64 {
- var accuracy float64 = float64(e) / float64(len(pattern))
- proximity := math.Abs(float64(loc - x))
- if dmp.MatchDistance == 0 {
-
- if proximity == 0 {
- return accuracy
- } else {
- return 1.0
- }
- }
- return accuracy + (proximity / float64(dmp.MatchDistance))
- }
- func (dmp *DiffMatchPatch) MatchAlphabet(pattern string) map[byte]int {
- s := map[byte]int{}
- char_pattern := []byte(pattern)
- for _, c := range char_pattern {
- _, ok := s[c]
- if !ok {
- s[c] = 0
- }
- }
- i := 0
- for _, c := range char_pattern {
- value := s[c] | int(uint(1)<<uint((len(pattern)-i-1)))
- s[c] = value
- i++
- }
- return s
- }
- func (dmp *DiffMatchPatch) PatchAddContext(patch Patch, text string) Patch {
- if len(text) == 0 {
- return patch
- }
- pattern := text[patch.start2 : patch.start2+patch.length1]
- padding := 0
-
-
- for strings.Index(text, pattern) != strings.LastIndex(text, pattern) &&
- len(pattern) < dmp.MatchMaxBits-2*dmp.PatchMargin {
- padding += dmp.PatchMargin
- maxStart := max(0, patch.start2-padding)
- minEnd := min(len(text), patch.start2+patch.length1+padding)
- pattern = text[maxStart:minEnd]
- }
-
- padding += dmp.PatchMargin
-
- prefix := text[max(0, patch.start2-padding):patch.start2]
- if len(prefix) != 0 {
- patch.diffs = append([]Diff{Diff{DiffEqual, prefix}}, patch.diffs...)
- }
-
- suffix := text[patch.start2+patch.length1 : min(len(text), patch.start2+patch.length1+padding)]
- if len(suffix) != 0 {
- patch.diffs = append(patch.diffs, Diff{DiffEqual, suffix})
- }
-
- patch.start1 -= len(prefix)
- patch.start2 -= len(prefix)
-
- patch.length1 += len(prefix) + len(suffix)
- patch.length2 += len(prefix) + len(suffix)
- return patch
- }
- func (dmp *DiffMatchPatch) PatchMake(opt ...interface{}) []Patch {
- if len(opt) == 1 {
- diffs, _ := opt[0].([]Diff)
- text1 := dmp.DiffText1(diffs)
- return dmp.PatchMake(text1, diffs)
- } else if len(opt) == 2 {
- text1 := opt[0].(string)
- switch t := opt[1].(type) {
- case string:
- diffs := dmp.DiffMain(text1, t, true)
- if len(diffs) > 2 {
- diffs = dmp.DiffCleanupSemantic(diffs)
- diffs = dmp.DiffCleanupEfficiency(diffs)
- }
- return dmp.PatchMake(text1, diffs)
- case []Diff:
- return dmp.patchMake2(text1, t)
- }
- } else if len(opt) == 3 {
- return dmp.PatchMake(opt[0], opt[2])
- }
- return []Patch{}
- }
- func (dmp *DiffMatchPatch) patchMake2(text1 string, diffs []Diff) []Patch {
-
- patches := []Patch{}
- if len(diffs) == 0 {
- return patches
- }
- patch := Patch{}
- char_count1 := 0
- char_count2 := 0
-
-
-
- prepatch_text := text1
- postpatch_text := text1
- for i, aDiff := range diffs {
- if len(patch.diffs) == 0 && aDiff.Type != DiffEqual {
-
- patch.start1 = char_count1
- patch.start2 = char_count2
- }
- switch aDiff.Type {
- case DiffInsert:
- patch.diffs = append(patch.diffs, aDiff)
- patch.length2 += len(aDiff.Text)
- postpatch_text = postpatch_text[:char_count2] +
- aDiff.Text + postpatch_text[char_count2:]
- case DiffDelete:
- patch.length1 += len(aDiff.Text)
- patch.diffs = append(patch.diffs, aDiff)
- postpatch_text = postpatch_text[:char_count2] + postpatch_text[char_count2+len(aDiff.Text):]
- case DiffEqual:
- if len(aDiff.Text) <= 2*dmp.PatchMargin &&
- len(patch.diffs) != 0 && i != len(diffs)-1 {
-
- patch.diffs = append(patch.diffs, aDiff)
- patch.length1 += len(aDiff.Text)
- patch.length2 += len(aDiff.Text)
- }
- if len(aDiff.Text) >= 2*dmp.PatchMargin {
-
- if len(patch.diffs) != 0 {
- patch = dmp.PatchAddContext(patch, prepatch_text)
- patches = append(patches, patch)
- patch = Patch{}
-
-
-
-
- prepatch_text = postpatch_text
- char_count1 = char_count2
- }
- }
- }
-
- if aDiff.Type != DiffInsert {
- char_count1 += len(aDiff.Text)
- }
- if aDiff.Type != DiffDelete {
- char_count2 += len(aDiff.Text)
- }
- }
-
- if len(patch.diffs) != 0 {
- patch = dmp.PatchAddContext(patch, prepatch_text)
- patches = append(patches, patch)
- }
- return patches
- }
- func (dmp *DiffMatchPatch) PatchDeepCopy(patches []Patch) []Patch {
- patchesCopy := []Patch{}
- for _, aPatch := range patches {
- patchCopy := Patch{}
- for _, aDiff := range aPatch.diffs {
- patchCopy.diffs = append(patchCopy.diffs, Diff{
- aDiff.Type,
- aDiff.Text,
- })
- }
- patchCopy.start1 = aPatch.start1
- patchCopy.start2 = aPatch.start2
- patchCopy.length1 = aPatch.length1
- patchCopy.length2 = aPatch.length2
- patchesCopy = append(patchesCopy, patchCopy)
- }
- return patchesCopy
- }
- func (dmp *DiffMatchPatch) PatchApply(patches []Patch, text string) (string, []bool) {
- if len(patches) == 0 {
- return text, []bool{}
- }
-
- patches = dmp.PatchDeepCopy(patches)
- nullPadding := dmp.PatchAddPadding(patches)
- text = nullPadding + text + nullPadding
- patches = dmp.PatchSplitMax(patches)
- x := 0
-
-
-
-
- delta := 0
- results := make([]bool, len(patches))
- for _, aPatch := range patches {
- expected_loc := aPatch.start2 + delta
- text1 := dmp.DiffText1(aPatch.diffs)
- var start_loc int
- end_loc := -1
- if len(text1) > dmp.MatchMaxBits {
-
-
- start_loc = dmp.MatchMain(text, text1[:dmp.MatchMaxBits], expected_loc)
- if start_loc != -1 {
- end_loc = dmp.MatchMain(text,
- text1[len(text1)-dmp.MatchMaxBits:], expected_loc+len(text1)-dmp.MatchMaxBits)
- if end_loc == -1 || start_loc >= end_loc {
-
- start_loc = -1
- }
- }
- } else {
- start_loc = dmp.MatchMain(text, text1, expected_loc)
- }
- if start_loc == -1 {
-
- results[x] = false
-
- delta -= aPatch.length2 - aPatch.length1
- } else {
-
- results[x] = true
- delta = start_loc - expected_loc
- var text2 string
- if end_loc == -1 {
- text2 = text[start_loc:int(math.Min(float64(start_loc+len(text1)), float64(len(text))))]
- } else {
- text2 = text[start_loc:int(math.Min(float64(end_loc+dmp.MatchMaxBits), float64(len(text))))]
- }
- if text1 == text2 {
-
- text = text[:start_loc] + dmp.DiffText2(aPatch.diffs) + text[start_loc+len(text1):]
- } else {
-
-
- diffs := dmp.DiffMain(text1, text2, false)
- if len(text1) > dmp.MatchMaxBits && float64(dmp.DiffLevenshtein(diffs))/float64(len(text1)) > dmp.PatchDeleteThreshold {
-
- results[x] = false
- } else {
- diffs = dmp.DiffCleanupSemanticLossless(diffs)
- index1 := 0
- for _, aDiff := range aPatch.diffs {
- if aDiff.Type != DiffEqual {
- index2 := dmp.DiffXIndex(diffs, index1)
- if aDiff.Type == DiffInsert {
-
- text = text[:start_loc+index2] + aDiff.Text + text[start_loc+index2:]
- } else if aDiff.Type == DiffDelete {
-
- start_index := start_loc + index2
- text = text[:start_index] +
- text[start_index+dmp.DiffXIndex(diffs, index1+len(aDiff.Text))-index2:]
- }
- }
- if aDiff.Type != DiffDelete {
- index1 += len(aDiff.Text)
- }
- }
- }
- }
- }
- x++
- }
-
- text = text[len(nullPadding) : len(nullPadding)+(len(text)-2*len(nullPadding))]
- return text, results
- }
- func (dmp *DiffMatchPatch) PatchAddPadding(patches []Patch) string {
- paddingLength := dmp.PatchMargin
- nullPadding := ""
- for x := 1; x <= paddingLength; x++ {
- nullPadding += string(x)
- }
-
- for i, _ := range patches {
- patches[i].start1 += paddingLength
- patches[i].start2 += paddingLength
- }
-
- if len(patches[0].diffs) == 0 || patches[0].diffs[0].Type != DiffEqual {
-
- patches[0].diffs = append([]Diff{Diff{DiffEqual, nullPadding}}, patches[0].diffs...)
- patches[0].start1 -= paddingLength
- patches[0].start2 -= paddingLength
- patches[0].length1 += paddingLength
- patches[0].length2 += paddingLength
- } else if paddingLength > len(patches[0].diffs[0].Text) {
-
- extraLength := paddingLength - len(patches[0].diffs[0].Text)
- patches[0].diffs[0].Text = nullPadding[len(patches[0].diffs[0].Text):] + patches[0].diffs[0].Text
- patches[0].start1 -= extraLength
- patches[0].start2 -= extraLength
- patches[0].length1 += extraLength
- patches[0].length2 += extraLength
- }
-
- last := len(patches) - 1
- if len(patches[last].diffs) == 0 || patches[last].diffs[len(patches[last].diffs)-1].Type != DiffEqual {
-
- patches[last].diffs = append(patches[last].diffs, Diff{DiffEqual, nullPadding})
- patches[last].length1 += paddingLength
- patches[last].length2 += paddingLength
- } else if paddingLength > len(patches[last].diffs[len(patches[last].diffs)-1].Text) {
-
- lastDiff := patches[last].diffs[len(patches[last].diffs)-1]
- extraLength := paddingLength - len(lastDiff.Text)
- patches[last].diffs[len(patches[last].diffs)-1].Text += nullPadding[:extraLength]
- patches[last].length1 += extraLength
- patches[last].length2 += extraLength
- }
- return nullPadding
- }
- func (dmp *DiffMatchPatch) PatchSplitMax(patches []Patch) []Patch {
- patch_size := dmp.MatchMaxBits
- for x := 0; x < len(patches); x++ {
- if patches[x].length1 <= patch_size {
- continue
- }
- bigpatch := patches[x]
-
- patches = append(patches[:x], patches[x+1:]...)
- x -= 1
- start1 := bigpatch.start1
- start2 := bigpatch.start2
- precontext := ""
- for len(bigpatch.diffs) != 0 {
-
- patch := Patch{}
- empty := true
- patch.start1 = start1 - len(precontext)
- patch.start2 = start2 - len(precontext)
- if len(precontext) != 0 {
- patch.length1 = len(precontext)
- patch.length2 = len(precontext)
- patch.diffs = append(patch.diffs, Diff{DiffEqual, precontext})
- }
- for len(bigpatch.diffs) != 0 && patch.length1 < patch_size-dmp.PatchMargin {
- diff_type := bigpatch.diffs[0].Type
- diff_text := bigpatch.diffs[0].Text
- if diff_type == DiffInsert {
-
- patch.length2 += len(diff_text)
- start2 += len(diff_text)
- patch.diffs = append(patch.diffs, bigpatch.diffs[0])
- bigpatch.diffs = bigpatch.diffs[1:]
- empty = false
- } else if diff_type == DiffDelete && len(patch.diffs) == 1 && patch.diffs[0].Type == DiffEqual && len(diff_text) > 2*patch_size {
-
- patch.length1 += len(diff_text)
- start1 += len(diff_text)
- empty = false
- patch.diffs = append(patch.diffs, Diff{diff_type, diff_text})
- bigpatch.diffs = bigpatch.diffs[1:]
- } else {
-
- diff_text = diff_text[:min(len(diff_text), patch_size-patch.length1-dmp.PatchMargin)]
- patch.length1 += len(diff_text)
- start1 += len(diff_text)
- if diff_type == DiffEqual {
- patch.length2 += len(diff_text)
- start2 += len(diff_text)
- } else {
- empty = false
- }
- patch.diffs = append(patch.diffs, Diff{diff_type, diff_text})
- if diff_text == bigpatch.diffs[0].Text {
- bigpatch.diffs = bigpatch.diffs[1:]
- } else {
- bigpatch.diffs[0].Text =
- bigpatch.diffs[0].Text[len(diff_text):]
- }
- }
- }
-
- precontext = dmp.DiffText2(patch.diffs)
- precontext = precontext[max(0, len(precontext)-dmp.PatchMargin):]
- postcontext := ""
-
- if len(dmp.DiffText1(bigpatch.diffs)) > dmp.PatchMargin {
- postcontext = dmp.DiffText1(bigpatch.diffs)[:dmp.PatchMargin]
- } else {
- postcontext = dmp.DiffText1(bigpatch.diffs)
- }
- if len(postcontext) != 0 {
- patch.length1 += len(postcontext)
- patch.length2 += len(postcontext)
- if len(patch.diffs) != 0 && patch.diffs[len(patch.diffs)-1].Type == DiffEqual {
- patch.diffs[len(patch.diffs)-1].Text += postcontext
- } else {
- patch.diffs = append(patch.diffs, Diff{DiffEqual, postcontext})
- }
- }
- if !empty {
- x += 1
- patches = append(patches[:x], append([]Patch{patch}, patches[x:]...)...)
- }
- }
- }
- return patches
- }
- func (dmp *DiffMatchPatch) PatchToText(patches []Patch) string {
- var text bytes.Buffer
- for _, aPatch := range patches {
- text.WriteString(aPatch.String())
- }
- return text.String()
- }
- func (dmp *DiffMatchPatch) PatchFromText(textline string) ([]Patch, error) {
- patches := []Patch{}
- if len(textline) == 0 {
- return patches, nil
- }
- text := strings.Split(textline, "\n")
- textPointer := 0
- patchHeader := regexp.MustCompile("^@@ -(\\d+),?(\\d*) \\+(\\d+),?(\\d*) @@$")
- var patch Patch
- var sign uint8
- var line string
- for textPointer < len(text) {
- if !patchHeader.MatchString(text[textPointer]) {
- return patches, errors.New("Invalid patch string: " + text[textPointer])
- }
- patch = Patch{}
- m := patchHeader.FindStringSubmatch(text[textPointer])
- patch.start1, _ = strconv.Atoi(m[1])
- if len(m[2]) == 0 {
- patch.start1--
- patch.length1 = 1
- } else if m[2] == "0" {
- patch.length1 = 0
- } else {
- patch.start1--
- patch.length1, _ = strconv.Atoi(m[2])
- }
- patch.start2, _ = strconv.Atoi(m[3])
- if len(m[4]) == 0 {
- patch.start2--
- patch.length2 = 1
- } else if m[4] == "0" {
- patch.length2 = 0
- } else {
- patch.start2--
- patch.length2, _ = strconv.Atoi(m[4])
- }
- textPointer++
- for textPointer < len(text) {
- if len(text[textPointer]) > 0 {
- sign = text[textPointer][0]
- } else {
- textPointer++
- continue
- }
- line = text[textPointer][1:]
- line = strings.Replace(line, "+", "%2b", -1)
- line, _ = url.QueryUnescape(line)
- if sign == '-' {
-
- patch.diffs = append(patch.diffs, Diff{DiffDelete, line})
- } else if sign == '+' {
-
- patch.diffs = append(patch.diffs, Diff{DiffInsert, line})
- } else if sign == ' ' {
-
- patch.diffs = append(patch.diffs, Diff{DiffEqual, line})
- } else if sign == '@' {
-
- break
- } else {
-
- return patches, errors.New("Invalid patch mode '" + string(sign) + "' in: " + string(line))
- }
- textPointer++
- }
- patches = append(patches, patch)
- }
- return patches, nil
- }
|