third-party-mirror / terraform / 80d4fe1e39aa758c5488269a446e7147cc3ca50f / . / v1.4.7 / internal / plans / objchange / lcs.go

package objchange | |

import ( | |

"github.com/zclconf/go-cty/cty" | |

) | |

// ValueEqual provides an implementation of the equals function that can be | |

// passed into LongestCommonSubsequence when comparing cty.Value types. | |

func ValueEqual(x, y cty.Value) bool { | |

unmarkedX, xMarks := x.UnmarkDeep() | |

unmarkedY, yMarks := y.UnmarkDeep() | |

eqV := unmarkedX.Equals(unmarkedY) | |

if len(xMarks) != len(yMarks) { | |

eqV = cty.False | |

} | |

if eqV.IsKnown() && eqV.True() { | |

return true | |

} | |

return false | |

} | |

// LongestCommonSubsequence finds a sequence of values that are common to both | |

// x and y, with the same relative ordering as in both collections. This result | |

// is useful as a first step towards computing a diff showing added/removed | |

// elements in a sequence. | |

// | |

// The approached used here is a "naive" one, assuming that both xs and ys will | |

// generally be small in most reasonable Terraform configurations. For larger | |

// lists the time/space usage may be sub-optimal. | |

// | |

// A pair of lists may have multiple longest common subsequences. In that | |

// case, the one selected by this function is undefined. | |

func LongestCommonSubsequence[V any](xs, ys []V, equals func(x, y V) bool) []V { | |

if len(xs) == 0 || len(ys) == 0 { | |

return make([]V, 0) | |

} | |

c := make([]int, len(xs)*len(ys)) | |

eqs := make([]bool, len(xs)*len(ys)) | |

w := len(xs) | |

for y := 0; y < len(ys); y++ { | |

for x := 0; x < len(xs); x++ { | |

eq := false | |

if equals(xs[x], ys[y]) { | |

eq = true | |

eqs[(w*y)+x] = true // equality tests can be expensive, so cache it | |

} | |

if eq { | |

// Sequence gets one longer than for the cell at top left, | |

// since we'd append a new item to the sequence here. | |

if x == 0 || y == 0 { | |

c[(w*y)+x] = 1 | |

} else { | |

c[(w*y)+x] = c[(w*(y-1))+(x-1)] + 1 | |

} | |

} else { | |

// We follow the longest of the sequence above and the sequence | |

// to the left of us in the matrix. | |

l := 0 | |

u := 0 | |

if x > 0 { | |

l = c[(w*y)+(x-1)] | |

} | |

if y > 0 { | |

u = c[(w*(y-1))+x] | |

} | |

if l > u { | |

c[(w*y)+x] = l | |

} else { | |

c[(w*y)+x] = u | |

} | |

} | |

} | |

} | |

// The bottom right cell tells us how long our longest sequence will be | |

seq := make([]V, c[len(c)-1]) | |

// Now we will walk back from the bottom right cell, finding again all | |

// of the equal pairs to construct our sequence. | |

x := len(xs) - 1 | |

y := len(ys) - 1 | |

i := len(seq) - 1 | |

for x > -1 && y > -1 { | |

if eqs[(w*y)+x] { | |

// Add the value to our result list and then walk diagonally | |

// up and to the left. | |

seq[i] = xs[x] | |

x-- | |

y-- | |

i-- | |

} else { | |

// Take the path with the greatest sequence length in the matrix. | |

l := 0 | |

u := 0 | |

if x > 0 { | |

l = c[(w*y)+(x-1)] | |

} | |

if y > 0 { | |

u = c[(w*(y-1))+x] | |

} | |

if l > u { | |

x-- | |

} else { | |

y-- | |

} | |

} | |

} | |

if i > -1 { | |

// should never happen if the matrix was constructed properly | |

panic("not enough elements in sequence") | |

} | |

return seq | |

} |