1 // Copyright (C) The Lightning Authors. All rights reserved.
3 // SPDX-License-Identifier: AGPL-3.0
12 "github.com/sergi/go-diff/diffmatchpatch"
19 Left string // base preceding an indel, if Ref or New is empty
22 func (v *Variant) String() string {
24 case len(v.New) == 0 && len(v.Ref) == 0:
25 return fmt.Sprintf("%d=", v.Position)
26 case len(v.New) == 1 && v.New == v.Ref:
27 return fmt.Sprintf("%d=", v.Position)
29 return fmt.Sprintf("%d_%d=", v.Position, v.Position+len(v.Ref)-1)
30 case len(v.New) == 0 && len(v.Ref) == 1:
31 return fmt.Sprintf("%ddel", v.Position)
33 return fmt.Sprintf("%d_%ddel", v.Position, v.Position+len(v.Ref)-1)
34 case len(v.Ref) == 1 && len(v.New) == 1:
35 return fmt.Sprintf("%d%s>%s", v.Position, v.Ref, v.New)
37 return fmt.Sprintf("%d_%dins%s", v.Position-1, v.Position, v.New)
38 case len(v.Ref) == 1 && len(v.New) > 0:
39 return fmt.Sprintf("%ddelins%s", v.Position, v.New)
41 return fmt.Sprintf("%d_%ddelins%s", v.Position, v.Position+len(v.Ref)-1, v.New)
45 // PadLeft returns a Variant that is equivalent to v but (if possible)
46 // uses the stashed preceding base (the Left field) to avoid having a
47 // non-empty Ref or New part, even for an insertion or deletion.
49 // For example, if v is {Position: 45, Ref: "", New: "A"}, PadLeft
50 // might return {Position: 44, Ref: "T", New: "TA"}.
51 func (v *Variant) PadLeft() Variant {
52 if len(v.Ref) == 0 || len(v.New) == 0 {
54 Position: v.Position - len(v.Left),
63 func Diff(a, b string, timeout time.Duration) ([]Variant, bool) {
64 dmp := diffmatchpatch.New()
65 var deadline time.Time
67 deadline = time.Now().Add(timeout)
69 diffs := dmp.DiffBisect(a, b, deadline)
71 if timeout > 0 && time.Now().After(deadline) {
74 diffs = cleanup(dmp.DiffCleanupEfficiency(diffs))
76 var variants []Variant
77 for i := 0; i < len(diffs); {
78 left := "" // last char before an insertion or deletion
79 for ; i < len(diffs) && diffs[i].Type == diffmatchpatch.DiffEqual; i++ {
80 pos += len(diffs[i].Text)
81 if tlen := len(diffs[i].Text); tlen > 0 {
82 left = diffs[i].Text[tlen-1:]
88 v := Variant{Position: pos, Left: left}
89 for ; i < len(diffs) && diffs[i].Type != diffmatchpatch.DiffEqual; i++ {
90 if diffs[i].Type == diffmatchpatch.DiffDelete {
91 v.Ref += diffs[i].Text
93 v.New += diffs[i].Text
96 if len(v.Ref) == 2 && len(v.New) == 2 {
105 variants = append(variants, v1)
108 variants = append(variants, v)
111 return variants, timedOut
114 func cleanup(in []diffmatchpatch.Diff) (out []diffmatchpatch.Diff) {
115 out = make([]diffmatchpatch.Diff, 0, len(in))
116 for i := 0; i < len(in); i++ {
118 // Merge consecutive entries of same type (e.g.,
119 // "insert A; insert B")
120 for i < len(in)-1 && in[i].Type == in[i+1].Type {
121 d.Text += in[i+1].Text
126 in, out = out, make([]diffmatchpatch.Diff, 0, len(in))
127 for i := 0; i < len(in); i++ {
129 // when diffmatchpatch says [=yyyyXXXX, delX, =zzz],
130 // we really want [=yyyy, delX, =XXXXzzz] (ditto for
131 // ins instead of del)
133 d.Type == diffmatchpatch.DiffEqual &&
134 in[i+1].Type != diffmatchpatch.DiffEqual &&
135 in[i+2].Type == diffmatchpatch.DiffEqual &&
136 len(in[i+1].Text) <= len(d.Text) {
137 for cut := 0; cut < len(d.Text)-len(in[i+1].Text); cut++ {
138 if d.Text[cut:] == d.Text[cut+len(in[i+1].Text):]+in[i+1].Text {
139 in[i+2].Text = d.Text[cut+len(in[i+1].Text):] + in[i+1].Text + in[i+2].Text
140 in[i+1].Text = d.Text[cut : cut+len(in[i+1].Text)]
141 d.Text = d.Text[:cut]
146 // diffmatchpatch solves diff("AAX","XTX") with
147 // [delAA,=X,insTX] but we prefer to spell it
150 // So, when we see a [del,=,ins] sequence where the
151 // "=" part is a suffix of the "ins" part -- e.g.,
152 // [delAAA,=CGG,insTTTCGG] -- we rearrange it to the
153 // equivalent spelling [delAAA,insCGGTTT,=CGG].
155 d.Type == diffmatchpatch.DiffDelete &&
156 in[i+1].Type == diffmatchpatch.DiffEqual &&
157 in[i+2].Type == diffmatchpatch.DiffInsert &&
158 strings.HasSuffix(in[i+2].Text, in[i+1].Text) {
159 eq, ins := in[i+1], in[i+2]
160 ins.Text = eq.Text + ins.Text[:len(ins.Text)-len(eq.Text)]
164 // diffmatchpatch solves diff("AXX","XXX") with
165 // [delA,=XX,insX] but we prefer to spell it
168 // So, when we see a [del,=,ins] sequence that has the
169 // same effect after swapping the "=" and "ins" parts,
172 d.Type == diffmatchpatch.DiffDelete &&
173 in[i+1].Type == diffmatchpatch.DiffEqual &&
174 in[i+2].Type == diffmatchpatch.DiffInsert &&
175 in[i+1].Text+in[i+2].Text == in[i+2].Text+in[i+1].Text {
176 in[i+2], in[i+1] = in[i+1], in[i+2]
178 // when diffmatchpatch says [delAAA, insXAY] and
179 // len(X)==1, we prefer to treat the A>X as a snp.
181 d.Type == diffmatchpatch.DiffDelete &&
182 in[i+1].Type == diffmatchpatch.DiffInsert &&
184 len(in[i+1].Text) >= 2 &&
185 d.Text[1] == in[i+1].Text[1] {
187 for ; eqend < len(d.Text) && eqend < len(in[i+1].Text) && d.Text[eqend] == in[i+1].Text[eqend]; eqend++ {
190 diffmatchpatch.Diff{diffmatchpatch.DiffDelete, d.Text[:1]},
191 diffmatchpatch.Diff{diffmatchpatch.DiffInsert, in[i+1].Text[:1]},
192 diffmatchpatch.Diff{diffmatchpatch.DiffEqual, d.Text[1:eqend]})
193 in[i].Text, in[i+1].Text = in[i].Text[eqend:], in[i+1].Text[eqend:]
197 // when diffmatchpatch says [delAAA, insXaY] and
198 // len(Y)==1, we prefer to treat the A>Y as a snp.
200 d.Type == diffmatchpatch.DiffDelete &&
201 in[i+1].Type == diffmatchpatch.DiffInsert &&
203 len(in[i+1].Text) >= 2 &&
204 d.Text[len(d.Text)-2] == in[i+1].Text[len(in[i+1].Text)-2] {
205 // eqstart will be the number of equal chars
206 // before the terminal snp, plus 1 for the snp
207 // itself. Example, for [delAAAA, insTTAAG],
208 // eqstart will be 3.
210 for ; eqstart < len(d.Text) && eqstart < len(in[i+1].Text) && d.Text[len(d.Text)-eqstart] == in[i+1].Text[len(in[i+1].Text)-eqstart]; eqstart++ {
214 diffmatchpatch.Diff{diffmatchpatch.DiffDelete, d.Text[:len(d.Text)-eqstart]},
215 diffmatchpatch.Diff{diffmatchpatch.DiffInsert, in[i+1].Text[:len(in[i+1].Text)-eqstart]},
216 diffmatchpatch.Diff{diffmatchpatch.DiffEqual, d.Text[len(d.Text)-eqstart : len(d.Text)-1]},
217 diffmatchpatch.Diff{diffmatchpatch.DiffDelete, d.Text[len(d.Text)-1:]},
218 diffmatchpatch.Diff{diffmatchpatch.DiffInsert, in[i+1].Text[len(in[i+1].Text)-1:]})
222 // when diffmatchpatch says [delA, =X, delBX], we
223 // prefer [delAB, =X].
225 d.Type == diffmatchpatch.DiffDelete &&
226 in[i+1].Type == diffmatchpatch.DiffEqual &&
227 in[i+2].Type == diffmatchpatch.DiffDelete &&
228 strings.HasSuffix(in[i+2].Text, in[i+1].Text) {
230 diffmatchpatch.Diff{diffmatchpatch.DiffDelete, d.Text + in[i+2].Text[:len(in[i+2].Text)-len(in[i+1].Text)]},
237 in, out = out, make([]diffmatchpatch.Diff, 0, len(in))
238 for _, d := range in {
243 // for i := 0; i < len(out)-1; i++ {
244 // if out[i].Type == diffmatchpatch.DiffDelete && len(out[i].Text) == 2 &&
245 // out[i+1].Type == diffmatchpatch.DiffInsert && len(out[i+1].Text) == 2 {
246 // out = append(out, diffmatchpatch.Diff{}, diffmatchpatch.Diff{})
247 // copy(out[i+4:], out[i+2:])
248 // out[i+2] = diffmatchpatch.Diff{diffmatchpatch.DiffDelete, out[i].Text[1:]}
249 // out[i+3] = diffmatchpatch.Diff{diffmatchpatch.DiffInsert, out[i+1].Text[1:]}
250 // out[i].Text = out[i].Text[:1]
251 // out[i+1].Text = out[i+1].Text[:1]
257 func Less(a, b Variant) bool {
258 if a.Position != b.Position {
259 return a.Position < b.Position
260 } else if a.New != b.New {