hgvs/diff.go

   1 // Copyright (C) The Lightning Authors. All rights reserved.
   2 //
   3 // SPDX-License-Identifier: AGPL-3.0
   4
   5 package hgvs
   6
   7 import (
   8         "fmt"
   9         "strings"
  10         "time"
  11
  12         "github.com/sergi/go-diff/diffmatchpatch"
  13 )
  14
  15 type Variant struct {
  16         Position int
  17         Ref      string
  18         New      string
  19         Left     string // base preceding an indel, if Ref or New is empty
  20 }
  21
  22 func (v *Variant) String() string {
  23         switch {
  24         case len(v.New) == 0 && len(v.Ref) == 0:
  25                 return fmt.Sprintf("%d=", v.Position)
  26         case len(v.New) == 0 && len(v.Ref) == 1:
  27                 return fmt.Sprintf("%ddel", v.Position)
  28         case len(v.New) == 0:
  29                 return fmt.Sprintf("%d_%ddel", v.Position, v.Position+len(v.Ref)-1)
  30         case len(v.Ref) == 1 && len(v.New) == 1:
  31                 return fmt.Sprintf("%d%s>%s", v.Position, v.Ref, v.New)
  32         case len(v.Ref) == 0:
  33                 return fmt.Sprintf("%d_%dins%s", v.Position-1, v.Position, v.New)
  34         case len(v.Ref) == 1 && len(v.New) > 0:
  35                 return fmt.Sprintf("%ddelins%s", v.Position, v.New)
  36         default:
  37                 return fmt.Sprintf("%d_%ddelins%s", v.Position, v.Position+len(v.Ref)-1, v.New)
  38         }
  39 }
  40
  41 // PadLeft returns a Variant that is equivalent to v but (if possible)
  42 // uses the stashed preceding base (the Left field) to avoid having a
  43 // non-empty Ref or New part, even for an insertion or deletion.
  44 //
  45 // For example, if v is {Position: 45, Ref: "", New: "A"}, PadLeft
  46 // might return {Position: 44, Ref: "T", New: "TA"}.
  47 func (v *Variant) PadLeft() Variant {
  48         if len(v.Ref) == 0 || len(v.New) == 0 {
  49                 return Variant{
  50                         Position: v.Position - len(v.Left),
  51                         Ref:      v.Left + v.Ref,
  52                         New:      v.Left + v.New,
  53                 }
  54         } else {
  55                 return *v
  56         }
  57 }
  58
  59 func Diff(a, b string, timeout time.Duration) ([]Variant, bool) {
  60         dmp := diffmatchpatch.New()
  61         var deadline time.Time
  62         if timeout > 0 {
  63                 deadline = time.Now().Add(timeout)
  64         }
  65         diffs := dmp.DiffBisect(a, b, deadline)
  66         timedOut := false
  67         if timeout > 0 && time.Now().After(deadline) {
  68                 timedOut = true
  69         }
  70         diffs = cleanup(dmp.DiffCleanupEfficiency(diffs))
  71         pos := 1
  72         var variants []Variant
  73         for i := 0; i < len(diffs); {
  74                 left := "" // last char before an insertion or deletion
  75                 for ; i < len(diffs) && diffs[i].Type == diffmatchpatch.DiffEqual; i++ {
  76                         pos += len(diffs[i].Text)
  77                         if tlen := len(diffs[i].Text); tlen > 0 {
  78                                 left = diffs[i].Text[tlen-1:]
  79                         }
  80                 }
  81                 if i >= len(diffs) {
  82                         break
  83                 }
  84                 v := Variant{Position: pos, Left: left}
  85                 for ; i < len(diffs) && diffs[i].Type != diffmatchpatch.DiffEqual; i++ {
  86                         if diffs[i].Type == diffmatchpatch.DiffDelete {
  87                                 v.Ref += diffs[i].Text
  88                         } else {
  89                                 v.New += diffs[i].Text
  90                         }
  91                 }
  92                 pos += len(v.Ref)
  93                 variants = append(variants, v)
  94                 left = ""
  95         }
  96         return variants, timedOut
  97 }
  98
  99 func cleanup(in []diffmatchpatch.Diff) (out []diffmatchpatch.Diff) {
 100         out = make([]diffmatchpatch.Diff, 0, len(in))
 101         for i := 0; i < len(in); i++ {
 102                 d := in[i]
 103                 // Merge consecutive entries of same type (e.g.,
 104                 // "insert A; insert B")
 105                 for i < len(in)-1 && in[i].Type == in[i+1].Type {
 106                         d.Text += in[i+1].Text
 107                         i++
 108                 }
 109                 out = append(out, d)
 110         }
 111         in, out = out, make([]diffmatchpatch.Diff, 0, len(in))
 112         for i := 0; i < len(in); i++ {
 113                 d := in[i]
 114                 // diffmatchpatch solves diff("AAX","XTX") with
 115                 // [delAA,=X,insTX] but we prefer to spell it
 116                 // [delAA,insXT,=X].
 117                 //
 118                 // So, when we see a [del,=,ins] sequence where the
 119                 // "=" part is a suffix of the "ins" part -- e.g.,
 120                 // [delAAA,=CGG,insTTTCGG] -- we rearrange it to the
 121                 // equivalent spelling [delAAA,insCGGTTT,=CGG].
 122                 if i < len(in)-2 &&
 123                         d.Type == diffmatchpatch.DiffDelete &&
 124                         in[i+1].Type == diffmatchpatch.DiffEqual &&
 125                         in[i+2].Type == diffmatchpatch.DiffInsert &&
 126                         strings.HasSuffix(in[i+2].Text, in[i+1].Text) {
 127                         eq, ins := in[i+1], in[i+2]
 128                         ins.Text = eq.Text + ins.Text[:len(ins.Text)-len(eq.Text)]
 129                         in[i+1] = ins
 130                         in[i+2] = eq
 131                 }
 132                 // diffmatchpatch solves diff("AXX","XXX") with
 133                 // [delA,=XX,insX] but we prefer to spell it
 134                 // [delA,insX,=XX].
 135                 //
 136                 // So, when we see a [del,=,ins] sequence that has the
 137                 // same effect after swapping the "=" and "ins" parts,
 138                 // we swap them.
 139                 if i < len(in)-2 &&
 140                         d.Type == diffmatchpatch.DiffDelete &&
 141                         in[i+1].Type == diffmatchpatch.DiffEqual &&
 142                         in[i+2].Type == diffmatchpatch.DiffInsert &&
 143                         in[i+1].Text+in[i+2].Text == in[i+2].Text+in[i+1].Text {
 144                         in[i+2], in[i+1] = in[i+1], in[i+2]
 145                 }
 146                 // when diffmatchpatch says [delAAA, insXAY] and
 147                 // len(X)==1, we prefer to treat the A>X as a snp.
 148                 if i < len(in)-1 &&
 149                         d.Type == diffmatchpatch.DiffDelete &&
 150                         in[i+1].Type == diffmatchpatch.DiffInsert &&
 151                         len(d.Text) >= 2 &&
 152                         len(in[i+1].Text) >= 2 &&
 153                         d.Text[1] == in[i+1].Text[1] {
 154                         eqend := 2
 155                         for ; eqend < len(d.Text) && eqend < len(in[i+1].Text) && d.Text[eqend] == in[i+1].Text[eqend]; eqend++ {
 156                         }
 157                         out = append(out,
 158                                 diffmatchpatch.Diff{diffmatchpatch.DiffDelete, d.Text[:1]},
 159                                 diffmatchpatch.Diff{diffmatchpatch.DiffInsert, in[i+1].Text[:1]},
 160                                 diffmatchpatch.Diff{diffmatchpatch.DiffEqual, d.Text[1:eqend]})
 161                         in[i].Text, in[i+1].Text = in[i].Text[eqend:], in[i+1].Text[eqend:]
 162                         i--
 163                         continue
 164                 }
 165                 // when diffmatchpatch says [delAAA, insXaY] and
 166                 // len(Y)==1, we prefer to treat the A>Y as a snp.
 167                 if i < len(in)-1 &&
 168                         d.Type == diffmatchpatch.DiffDelete &&
 169                         in[i+1].Type == diffmatchpatch.DiffInsert &&
 170                         len(d.Text) >= 2 &&
 171                         len(in[i+1].Text) >= 2 &&
 172                         d.Text[len(d.Text)-2] == in[i+1].Text[len(in[i+1].Text)-2] {
 173                         // eqstart will be the number of equal chars
 174                         // before the terminal snp, plus 1 for the snp
 175                         // itself. Example, for [delAAAA, insTTAAG],
 176                         // eqstart will be 3.
 177                         eqstart := 2
 178                         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++ {
 179                         }
 180                         eqstart--
 181                         out = append(out,
 182                                 diffmatchpatch.Diff{diffmatchpatch.DiffDelete, d.Text[:len(d.Text)-eqstart]},
 183                                 diffmatchpatch.Diff{diffmatchpatch.DiffInsert, in[i+1].Text[:len(in[i+1].Text)-eqstart]},
 184                                 diffmatchpatch.Diff{diffmatchpatch.DiffEqual, d.Text[len(d.Text)-eqstart : len(d.Text)-1]},
 185                                 diffmatchpatch.Diff{diffmatchpatch.DiffDelete, d.Text[len(d.Text)-1:]},
 186                                 diffmatchpatch.Diff{diffmatchpatch.DiffInsert, in[i+1].Text[len(in[i+1].Text)-1:]})
 187                         i++
 188                         continue
 189                 }
 190                 out = append(out, d)
 191         }
 192         return
 193 }
 194
 195 func Less(a, b Variant) bool {
 196         if a.Position != b.Position {
 197                 return a.Position < b.Position
 198         } else if a.New != b.New {
 199                 return a.New < b.New
 200         } else {
 201                 return a.Ref < b.Ref
 202         }
 203 }