diff options
author | Nathan Dench <ndenc2@gmail.com> | 2019-05-24 15:16:44 +1000 |
---|---|---|
committer | Nathan Dench <ndenc2@gmail.com> | 2019-05-24 15:16:44 +1000 |
commit | 107c1cdb09c575aa2f61d97f48d8587eb6bada4c (patch) | |
tree | ca7d008643efc555c388baeaf1d986e0b6b3e28c /vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go | |
parent | 844b5a68d8af4791755b8f0ad293cc99f5959183 (diff) | |
download | terraform-provider-statuscake-107c1cdb09c575aa2f61d97f48d8587eb6bada4c.tar.gz terraform-provider-statuscake-107c1cdb09c575aa2f61d97f48d8587eb6bada4c.tar.zst terraform-provider-statuscake-107c1cdb09c575aa2f61d97f48d8587eb6bada4c.zip |
Upgrade to 0.12
Diffstat (limited to 'vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go')
-rw-r--r-- | vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go | 363 |
1 files changed, 363 insertions, 0 deletions
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go b/vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go new file mode 100644 index 0000000..260befe --- /dev/null +++ b/vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go | |||
@@ -0,0 +1,363 @@ | |||
1 | // Copyright 2017, The Go Authors. All rights reserved. | ||
2 | // Use of this source code is governed by a BSD-style | ||
3 | // license that can be found in the LICENSE.md file. | ||
4 | |||
5 | // Package diff implements an algorithm for producing edit-scripts. | ||
6 | // The edit-script is a sequence of operations needed to transform one list | ||
7 | // of symbols into another (or vice-versa). The edits allowed are insertions, | ||
8 | // deletions, and modifications. The summation of all edits is called the | ||
9 | // Levenshtein distance as this problem is well-known in computer science. | ||
10 | // | ||
11 | // This package prioritizes performance over accuracy. That is, the run time | ||
12 | // is more important than obtaining a minimal Levenshtein distance. | ||
13 | package diff | ||
14 | |||
15 | // EditType represents a single operation within an edit-script. | ||
16 | type EditType uint8 | ||
17 | |||
18 | const ( | ||
19 | // Identity indicates that a symbol pair is identical in both list X and Y. | ||
20 | Identity EditType = iota | ||
21 | // UniqueX indicates that a symbol only exists in X and not Y. | ||
22 | UniqueX | ||
23 | // UniqueY indicates that a symbol only exists in Y and not X. | ||
24 | UniqueY | ||
25 | // Modified indicates that a symbol pair is a modification of each other. | ||
26 | Modified | ||
27 | ) | ||
28 | |||
29 | // EditScript represents the series of differences between two lists. | ||
30 | type EditScript []EditType | ||
31 | |||
32 | // String returns a human-readable string representing the edit-script where | ||
33 | // Identity, UniqueX, UniqueY, and Modified are represented by the | ||
34 | // '.', 'X', 'Y', and 'M' characters, respectively. | ||
35 | func (es EditScript) String() string { | ||
36 | b := make([]byte, len(es)) | ||
37 | for i, e := range es { | ||
38 | switch e { | ||
39 | case Identity: | ||
40 | b[i] = '.' | ||
41 | case UniqueX: | ||
42 | b[i] = 'X' | ||
43 | case UniqueY: | ||
44 | b[i] = 'Y' | ||
45 | case Modified: | ||
46 | b[i] = 'M' | ||
47 | default: | ||
48 | panic("invalid edit-type") | ||
49 | } | ||
50 | } | ||
51 | return string(b) | ||
52 | } | ||
53 | |||
54 | // stats returns a histogram of the number of each type of edit operation. | ||
55 | func (es EditScript) stats() (s struct{ NI, NX, NY, NM int }) { | ||
56 | for _, e := range es { | ||
57 | switch e { | ||
58 | case Identity: | ||
59 | s.NI++ | ||
60 | case UniqueX: | ||
61 | s.NX++ | ||
62 | case UniqueY: | ||
63 | s.NY++ | ||
64 | case Modified: | ||
65 | s.NM++ | ||
66 | default: | ||
67 | panic("invalid edit-type") | ||
68 | } | ||
69 | } | ||
70 | return | ||
71 | } | ||
72 | |||
73 | // Dist is the Levenshtein distance and is guaranteed to be 0 if and only if | ||
74 | // lists X and Y are equal. | ||
75 | func (es EditScript) Dist() int { return len(es) - es.stats().NI } | ||
76 | |||
77 | // LenX is the length of the X list. | ||
78 | func (es EditScript) LenX() int { return len(es) - es.stats().NY } | ||
79 | |||
80 | // LenY is the length of the Y list. | ||
81 | func (es EditScript) LenY() int { return len(es) - es.stats().NX } | ||
82 | |||
83 | // EqualFunc reports whether the symbols at indexes ix and iy are equal. | ||
84 | // When called by Difference, the index is guaranteed to be within nx and ny. | ||
85 | type EqualFunc func(ix int, iy int) Result | ||
86 | |||
87 | // Result is the result of comparison. | ||
88 | // NSame is the number of sub-elements that are equal. | ||
89 | // NDiff is the number of sub-elements that are not equal. | ||
90 | type Result struct{ NSame, NDiff int } | ||
91 | |||
92 | // Equal indicates whether the symbols are equal. Two symbols are equal | ||
93 | // if and only if NDiff == 0. If Equal, then they are also Similar. | ||
94 | func (r Result) Equal() bool { return r.NDiff == 0 } | ||
95 | |||
96 | // Similar indicates whether two symbols are similar and may be represented | ||
97 | // by using the Modified type. As a special case, we consider binary comparisons | ||
98 | // (i.e., those that return Result{1, 0} or Result{0, 1}) to be similar. | ||
99 | // | ||
100 | // The exact ratio of NSame to NDiff to determine similarity may change. | ||
101 | func (r Result) Similar() bool { | ||
102 | // Use NSame+1 to offset NSame so that binary comparisons are similar. | ||
103 | return r.NSame+1 >= r.NDiff | ||
104 | } | ||
105 | |||
106 | // Difference reports whether two lists of lengths nx and ny are equal | ||
107 | // given the definition of equality provided as f. | ||
108 | // | ||
109 | // This function returns an edit-script, which is a sequence of operations | ||
110 | // needed to convert one list into the other. The following invariants for | ||
111 | // the edit-script are maintained: | ||
112 | // • eq == (es.Dist()==0) | ||
113 | // • nx == es.LenX() | ||
114 | // • ny == es.LenY() | ||
115 | // | ||
116 | // This algorithm is not guaranteed to be an optimal solution (i.e., one that | ||
117 | // produces an edit-script with a minimal Levenshtein distance). This algorithm | ||
118 | // favors performance over optimality. The exact output is not guaranteed to | ||
119 | // be stable and may change over time. | ||
120 | func Difference(nx, ny int, f EqualFunc) (es EditScript) { | ||
121 | // This algorithm is based on traversing what is known as an "edit-graph". | ||
122 | // See Figure 1 from "An O(ND) Difference Algorithm and Its Variations" | ||
123 | // by Eugene W. Myers. Since D can be as large as N itself, this is | ||
124 | // effectively O(N^2). Unlike the algorithm from that paper, we are not | ||
125 | // interested in the optimal path, but at least some "decent" path. | ||
126 | // | ||
127 | // For example, let X and Y be lists of symbols: | ||
128 | // X = [A B C A B B A] | ||
129 | // Y = [C B A B A C] | ||
130 | // | ||
131 | // The edit-graph can be drawn as the following: | ||
132 | // A B C A B B A | ||
133 | // ┌─────────────┐ | ||
134 | // C │_|_|\|_|_|_|_│ 0 | ||
135 | // B │_|\|_|_|\|\|_│ 1 | ||
136 | // A │\|_|_|\|_|_|\│ 2 | ||
137 | // B │_|\|_|_|\|\|_│ 3 | ||
138 | // A │\|_|_|\|_|_|\│ 4 | ||
139 | // C │ | |\| | | | │ 5 | ||
140 | // └─────────────┘ 6 | ||
141 | // 0 1 2 3 4 5 6 7 | ||
142 | // | ||
143 | // List X is written along the horizontal axis, while list Y is written | ||
144 | // along the vertical axis. At any point on this grid, if the symbol in | ||
145 | // list X matches the corresponding symbol in list Y, then a '\' is drawn. | ||
146 | // The goal of any minimal edit-script algorithm is to find a path from the | ||
147 | // top-left corner to the bottom-right corner, while traveling through the | ||
148 | // fewest horizontal or vertical edges. | ||
149 | // A horizontal edge is equivalent to inserting a symbol from list X. | ||
150 | // A vertical edge is equivalent to inserting a symbol from list Y. | ||
151 | // A diagonal edge is equivalent to a matching symbol between both X and Y. | ||
152 | |||
153 | // Invariants: | ||
154 | // • 0 ≤ fwdPath.X ≤ (fwdFrontier.X, revFrontier.X) ≤ revPath.X ≤ nx | ||
155 | // • 0 ≤ fwdPath.Y ≤ (fwdFrontier.Y, revFrontier.Y) ≤ revPath.Y ≤ ny | ||
156 | // | ||
157 | // In general: | ||
158 | // • fwdFrontier.X < revFrontier.X | ||
159 | // • fwdFrontier.Y < revFrontier.Y | ||
160 | // Unless, it is time for the algorithm to terminate. | ||
161 | fwdPath := path{+1, point{0, 0}, make(EditScript, 0, (nx+ny)/2)} | ||
162 | revPath := path{-1, point{nx, ny}, make(EditScript, 0)} | ||
163 | fwdFrontier := fwdPath.point // Forward search frontier | ||
164 | revFrontier := revPath.point // Reverse search frontier | ||
165 | |||
166 | // Search budget bounds the cost of searching for better paths. | ||
167 | // The longest sequence of non-matching symbols that can be tolerated is | ||
168 | // approximately the square-root of the search budget. | ||
169 | searchBudget := 4 * (nx + ny) // O(n) | ||
170 | |||
171 | // The algorithm below is a greedy, meet-in-the-middle algorithm for | ||
172 | // computing sub-optimal edit-scripts between two lists. | ||
173 | // | ||
174 | // The algorithm is approximately as follows: | ||
175 | // • Searching for differences switches back-and-forth between | ||
176 | // a search that starts at the beginning (the top-left corner), and | ||
177 | // a search that starts at the end (the bottom-right corner). The goal of | ||
178 | // the search is connect with the search from the opposite corner. | ||
179 | // • As we search, we build a path in a greedy manner, where the first | ||
180 | // match seen is added to the path (this is sub-optimal, but provides a | ||
181 | // decent result in practice). When matches are found, we try the next pair | ||
182 | // of symbols in the lists and follow all matches as far as possible. | ||
183 | // • When searching for matches, we search along a diagonal going through | ||
184 | // through the "frontier" point. If no matches are found, we advance the | ||
185 | // frontier towards the opposite corner. | ||
186 | // • This algorithm terminates when either the X coordinates or the | ||
187 | // Y coordinates of the forward and reverse frontier points ever intersect. | ||
188 | // | ||
189 | // This algorithm is correct even if searching only in the forward direction | ||
190 | // or in the reverse direction. We do both because it is commonly observed | ||
191 | // that two lists commonly differ because elements were added to the front | ||
192 | // or end of the other list. | ||
193 | // | ||
194 | // Running the tests with the "debug" build tag prints a visualization of | ||
195 | // the algorithm running in real-time. This is educational for understanding | ||
196 | // how the algorithm works. See debug_enable.go. | ||
197 | f = debug.Begin(nx, ny, f, &fwdPath.es, &revPath.es) | ||
198 | for { | ||
199 | // Forward search from the beginning. | ||
200 | if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 { | ||
201 | break | ||
202 | } | ||
203 | for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ { | ||
204 | // Search in a diagonal pattern for a match. | ||
205 | z := zigzag(i) | ||
206 | p := point{fwdFrontier.X + z, fwdFrontier.Y - z} | ||
207 | switch { | ||
208 | case p.X >= revPath.X || p.Y < fwdPath.Y: | ||
209 | stop1 = true // Hit top-right corner | ||
210 | case p.Y >= revPath.Y || p.X < fwdPath.X: | ||
211 | stop2 = true // Hit bottom-left corner | ||
212 | case f(p.X, p.Y).Equal(): | ||
213 | // Match found, so connect the path to this point. | ||
214 | fwdPath.connect(p, f) | ||
215 | fwdPath.append(Identity) | ||
216 | // Follow sequence of matches as far as possible. | ||
217 | for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y { | ||
218 | if !f(fwdPath.X, fwdPath.Y).Equal() { | ||
219 | break | ||
220 | } | ||
221 | fwdPath.append(Identity) | ||
222 | } | ||
223 | fwdFrontier = fwdPath.point | ||
224 | stop1, stop2 = true, true | ||
225 | default: | ||
226 | searchBudget-- // Match not found | ||
227 | } | ||
228 | debug.Update() | ||
229 | } | ||
230 | // Advance the frontier towards reverse point. | ||
231 | if revPath.X-fwdFrontier.X >= revPath.Y-fwdFrontier.Y { | ||
232 | fwdFrontier.X++ | ||
233 | } else { | ||
234 | fwdFrontier.Y++ | ||
235 | } | ||
236 | |||
237 | // Reverse search from the end. | ||
238 | if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 { | ||
239 | break | ||
240 | } | ||
241 | for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ { | ||
242 | // Search in a diagonal pattern for a match. | ||
243 | z := zigzag(i) | ||
244 | p := point{revFrontier.X - z, revFrontier.Y + z} | ||
245 | switch { | ||
246 | case fwdPath.X >= p.X || revPath.Y < p.Y: | ||
247 | stop1 = true // Hit bottom-left corner | ||
248 | case fwdPath.Y >= p.Y || revPath.X < p.X: | ||
249 | stop2 = true // Hit top-right corner | ||
250 | case f(p.X-1, p.Y-1).Equal(): | ||
251 | // Match found, so connect the path to this point. | ||
252 | revPath.connect(p, f) | ||
253 | revPath.append(Identity) | ||
254 | // Follow sequence of matches as far as possible. | ||
255 | for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y { | ||
256 | if !f(revPath.X-1, revPath.Y-1).Equal() { | ||
257 | break | ||
258 | } | ||
259 | revPath.append(Identity) | ||
260 | } | ||
261 | revFrontier = revPath.point | ||
262 | stop1, stop2 = true, true | ||
263 | default: | ||
264 | searchBudget-- // Match not found | ||
265 | } | ||
266 | debug.Update() | ||
267 | } | ||
268 | // Advance the frontier towards forward point. | ||
269 | if revFrontier.X-fwdPath.X >= revFrontier.Y-fwdPath.Y { | ||
270 | revFrontier.X-- | ||
271 | } else { | ||
272 | revFrontier.Y-- | ||
273 | } | ||
274 | } | ||
275 | |||
276 | // Join the forward and reverse paths and then append the reverse path. | ||
277 | fwdPath.connect(revPath.point, f) | ||
278 | for i := len(revPath.es) - 1; i >= 0; i-- { | ||
279 | t := revPath.es[i] | ||
280 | revPath.es = revPath.es[:i] | ||
281 | fwdPath.append(t) | ||
282 | } | ||
283 | debug.Finish() | ||
284 | return fwdPath.es | ||
285 | } | ||
286 | |||
287 | type path struct { | ||
288 | dir int // +1 if forward, -1 if reverse | ||
289 | point // Leading point of the EditScript path | ||
290 | es EditScript | ||
291 | } | ||
292 | |||
293 | // connect appends any necessary Identity, Modified, UniqueX, or UniqueY types | ||
294 | // to the edit-script to connect p.point to dst. | ||
295 | func (p *path) connect(dst point, f EqualFunc) { | ||
296 | if p.dir > 0 { | ||
297 | // Connect in forward direction. | ||
298 | for dst.X > p.X && dst.Y > p.Y { | ||
299 | switch r := f(p.X, p.Y); { | ||
300 | case r.Equal(): | ||
301 | p.append(Identity) | ||
302 | case r.Similar(): | ||
303 | p.append(Modified) | ||
304 | case dst.X-p.X >= dst.Y-p.Y: | ||
305 | p.append(UniqueX) | ||
306 | default: | ||
307 | p.append(UniqueY) | ||
308 | } | ||
309 | } | ||
310 | for dst.X > p.X { | ||
311 | p.append(UniqueX) | ||
312 | } | ||
313 | for dst.Y > p.Y { | ||
314 | p.append(UniqueY) | ||
315 | } | ||
316 | } else { | ||
317 | // Connect in reverse direction. | ||
318 | for p.X > dst.X && p.Y > dst.Y { | ||
319 | switch r := f(p.X-1, p.Y-1); { | ||
320 | case r.Equal(): | ||
321 | p.append(Identity) | ||
322 | case r.Similar(): | ||
323 | p.append(Modified) | ||
324 | case p.Y-dst.Y >= p.X-dst.X: | ||
325 | p.append(UniqueY) | ||
326 | default: | ||
327 | p.append(UniqueX) | ||
328 | } | ||
329 | } | ||
330 | for p.X > dst.X { | ||
331 | p.append(UniqueX) | ||
332 | } | ||
333 | for p.Y > dst.Y { | ||
334 | p.append(UniqueY) | ||
335 | } | ||
336 | } | ||
337 | } | ||
338 | |||
339 | func (p *path) append(t EditType) { | ||
340 | p.es = append(p.es, t) | ||
341 | switch t { | ||
342 | case Identity, Modified: | ||
343 | p.add(p.dir, p.dir) | ||
344 | case UniqueX: | ||
345 | p.add(p.dir, 0) | ||
346 | case UniqueY: | ||
347 | p.add(0, p.dir) | ||
348 | } | ||
349 | debug.Update() | ||
350 | } | ||
351 | |||
352 | type point struct{ X, Y int } | ||
353 | |||
354 | func (p *point) add(dx, dy int) { p.X += dx; p.Y += dy } | ||
355 | |||
356 | // zigzag maps a consecutive sequence of integers to a zig-zag sequence. | ||
357 | // [0 1 2 3 4 5 ...] => [0 -1 +1 -2 +2 ...] | ||
358 | func zigzag(x int) int { | ||
359 | if x&1 != 0 { | ||
360 | x = ^x | ||
361 | } | ||
362 | return x >> 1 | ||
363 | } | ||