8 "github.com/sergi/go-diff/diffmatchpatch"
15 Left string // base preceding an indel, if Ref or New is empty
18 func (v *Variant) String() string {
20 case len(v.New) == 0 && len(v.Ref) == 0:
21 return fmt.Sprintf("%d=", v.Position)
22 case len(v.New) == 0 && len(v.Ref) == 1:
23 return fmt.Sprintf("%ddel", v.Position)
25 return fmt.Sprintf("%d_%ddel", v.Position, v.Position+len(v.Ref)-1)
26 case len(v.Ref) == 1 && len(v.New) == 1:
27 return fmt.Sprintf("%d%s>%s", v.Position, v.Ref, v.New)
29 return fmt.Sprintf("%d_%dins%s", v.Position-1, v.Position, v.New)
30 case len(v.Ref) == 1 && len(v.New) > 0:
31 return fmt.Sprintf("%ddelins%s", v.Position, v.New)
33 return fmt.Sprintf("%d_%ddelins%s", v.Position, v.Position+len(v.Ref)-1, v.New)
37 // PadLeft returns a Variant that is equivalent to v but (if possible)
38 // uses the stashed preceding base (the Left field) to avoid having a
39 // non-empty Ref or New part, even for an insertion or deletion.
41 // For example, if v is {Position: 45, Ref: "", New: "A"}, PadLeft
42 // might return {Position: 44, Ref: "T", New: "TA"}.
43 func (v *Variant) PadLeft() Variant {
44 if len(v.Ref) == 0 || len(v.New) == 0 {
46 Position: v.Position - len(v.Left),
55 func Diff(a, b string, timeout time.Duration) ([]Variant, bool) {
56 dmp := diffmatchpatch.New()
57 var deadline time.Time
59 deadline = time.Now().Add(timeout)
61 diffs := dmp.DiffBisect(a, b, deadline)
63 if timeout > 0 && time.Now().After(deadline) {
66 diffs = cleanup(dmp.DiffCleanupEfficiency(diffs))
68 var variants []Variant
69 for i := 0; i < len(diffs); {
70 left := "" // last char before an insertion or deletion
71 for ; i < len(diffs) && diffs[i].Type == diffmatchpatch.DiffEqual; i++ {
72 pos += len(diffs[i].Text)
73 if tlen := len(diffs[i].Text); tlen > 0 {
74 left = diffs[i].Text[tlen-1:]
80 v := Variant{Position: pos, Left: left}
81 for ; i < len(diffs) && diffs[i].Type != diffmatchpatch.DiffEqual; i++ {
82 if diffs[i].Type == diffmatchpatch.DiffDelete {
83 v.Ref += diffs[i].Text
85 v.New += diffs[i].Text
89 variants = append(variants, v)
92 return variants, timedOut
95 func cleanup(in []diffmatchpatch.Diff) (out []diffmatchpatch.Diff) {
96 out = make([]diffmatchpatch.Diff, 0, len(in))
97 for i := 0; i < len(in); i++ {
99 // Merge consecutive entries of same type (e.g.,
100 // "insert A; insert B")
101 for i < len(in)-1 && in[i].Type == in[i+1].Type {
102 d.Text += in[i+1].Text
107 in, out = out, make([]diffmatchpatch.Diff, 0, len(in))
108 for i := 0; i < len(in); i++ {
110 // diffmatchpatch solves diff("AAX","XTX") with
111 // [delAA,=X,insTX] but we prefer to spell it
114 // So, when we see a [del,=,ins] sequence where the
115 // "=" part is a suffix of the "ins" part -- e.g.,
116 // [delAAA,=CGG,insTTTCGG] -- we rearrange it to the
117 // equivalent spelling [delAAA,insCGGTTT,=CGG].
119 d.Type == diffmatchpatch.DiffDelete &&
120 in[i+1].Type == diffmatchpatch.DiffEqual &&
121 in[i+2].Type == diffmatchpatch.DiffInsert &&
122 strings.HasSuffix(in[i+2].Text, in[i+1].Text) {
123 eq, ins := in[i+1], in[i+2]
124 ins.Text = eq.Text + ins.Text[:len(ins.Text)-len(eq.Text)]
128 // diffmatchpatch solves diff("AXX","XXX") with
129 // [delA,=XX,insX] but we prefer to spell it
132 // So, when we see a [del,=,ins] sequence that has the
133 // same effect after swapping the "=" and "ins" parts,
136 d.Type == diffmatchpatch.DiffDelete &&
137 in[i+1].Type == diffmatchpatch.DiffEqual &&
138 in[i+2].Type == diffmatchpatch.DiffInsert &&
139 in[i+1].Text+in[i+2].Text == in[i+2].Text+in[i+1].Text {
140 in[i+2], in[i+1] = in[i+1], in[i+2]
147 func Less(a, b Variant) bool {
148 if a.Position != b.Position {
149 return a.Position < b.Position
150 } else if a.New != b.New {