]>
Commit | Line | Data |
---|---|---|
107c1cdb ND |
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 | } |