vendor/github.com/hashicorp/terraform/plans/objchange/lcs.go

   1 package objchange
   2
   3 import (
   4         "github.com/zclconf/go-cty/cty"
   5 )
   6
   7 // LongestCommonSubsequence finds a sequence of values that are common to both
   8 // x and y, with the same relative ordering as in both collections. This result
   9 // is useful as a first step towards computing a diff showing added/removed
  10 // elements in a sequence.
  11 //
  12 // The approached used here is a "naive" one, assuming that both xs and ys will
  13 // generally be small in most reasonable Terraform configurations. For larger
  14 // lists the time/space usage may be sub-optimal.
  15 //
  16 // A pair of lists may have multiple longest common subsequences. In that
  17 // case, the one selected by this function is undefined.
  18 func LongestCommonSubsequence(xs, ys []cty.Value) []cty.Value {
  19         if len(xs) == 0 || len(ys) == 0 {
  20                 return make([]cty.Value, 0)
  21         }
  22
  23         c := make([]int, len(xs)*len(ys))
  24         eqs := make([]bool, len(xs)*len(ys))
  25         w := len(xs)
  26
  27         for y := 0; y < len(ys); y++ {
  28                 for x := 0; x < len(xs); x++ {
  29                         eqV := xs[x].Equals(ys[y])
  30                         eq := false
  31                         if eqV.IsKnown() && eqV.True() {
  32                                 eq = true
  33                                 eqs[(w*y)+x] = true // equality tests can be expensive, so cache it
  34                         }
  35                         if eq {
  36                                 // Sequence gets one longer than for the cell at top left,
  37                                 // since we'd append a new item to the sequence here.
  38                                 if x == 0 || y == 0 {
  39                                         c[(w*y)+x] = 1
  40                                 } else {
  41                                         c[(w*y)+x] = c[(w*(y-1))+(x-1)] + 1
  42                                 }
  43                         } else {
  44                                 // We follow the longest of the sequence above and the sequence
  45                                 // to the left of us in the matrix.
  46                                 l := 0
  47                                 u := 0
  48                                 if x > 0 {
  49                                         l = c[(w*y)+(x-1)]
  50                                 }
  51                                 if y > 0 {
  52                                         u = c[(w*(y-1))+x]
  53                                 }
  54                                 if l > u {
  55                                         c[(w*y)+x] = l
  56                                 } else {
  57                                         c[(w*y)+x] = u
  58                                 }
  59                         }
  60                 }
  61         }
  62
  63         // The bottom right cell tells us how long our longest sequence will be
  64         seq := make([]cty.Value, c[len(c)-1])
  65
  66         // Now we will walk back from the bottom right cell, finding again all
  67         // of the equal pairs to construct our sequence.
  68         x := len(xs) - 1
  69         y := len(ys) - 1
  70         i := len(seq) - 1
  71
  72         for x > -1 && y > -1 {
  73                 if eqs[(w*y)+x] {
  74                         // Add the value to our result list and then walk diagonally
  75                         // up and to the left.
  76                         seq[i] = xs[x]
  77                         x--
  78                         y--
  79                         i--
  80                 } else {
  81                         // Take the path with the greatest sequence length in the matrix.
  82                         l := 0
  83                         u := 0
  84                         if x > 0 {
  85                                 l = c[(w*y)+(x-1)]
  86                         }
  87                         if y > 0 {
  88                                 u = c[(w*(y-1))+x]
  89                         }
  90                         if l > u {
  91                                 x--
  92                         } else {
  93                                 y--
  94                         }
  95                 }
  96         }
  97
  98         if i > -1 {
  99                 // should never happen if the matrix was constructed properly
 100                 panic("not enough elements in sequence")
 101         }
 102
 103         return seq
 104 }