]>
Commit | Line | Data |
---|---|---|
107c1cdb ND |
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 | // +build debug | |
6 | ||
7 | package diff | |
8 | ||
9 | import ( | |
10 | "fmt" | |
11 | "strings" | |
12 | "sync" | |
13 | "time" | |
14 | ) | |
15 | ||
16 | // The algorithm can be seen running in real-time by enabling debugging: | |
17 | // go test -tags=debug -v | |
18 | // | |
19 | // Example output: | |
20 | // === RUN TestDifference/#34 | |
21 | // ┌───────────────────────────────┐ | |
22 | // │ \ · · · · · · · · · · · · · · │ | |
23 | // │ · # · · · · · · · · · · · · · │ | |
24 | // │ · \ · · · · · · · · · · · · · │ | |
25 | // │ · · \ · · · · · · · · · · · · │ | |
26 | // │ · · · X # · · · · · · · · · · │ | |
27 | // │ · · · # \ · · · · · · · · · · │ | |
28 | // │ · · · · · # # · · · · · · · · │ | |
29 | // │ · · · · · # \ · · · · · · · · │ | |
30 | // │ · · · · · · · \ · · · · · · · │ | |
31 | // │ · · · · · · · · \ · · · · · · │ | |
32 | // │ · · · · · · · · · \ · · · · · │ | |
33 | // │ · · · · · · · · · · \ · · # · │ | |
34 | // │ · · · · · · · · · · · \ # # · │ | |
35 | // │ · · · · · · · · · · · # # # · │ | |
36 | // │ · · · · · · · · · · # # # # · │ | |
37 | // │ · · · · · · · · · # # # # # · │ | |
38 | // │ · · · · · · · · · · · · · · \ │ | |
39 | // └───────────────────────────────┘ | |
40 | // [.Y..M.XY......YXYXY.|] | |
41 | // | |
42 | // The grid represents the edit-graph where the horizontal axis represents | |
43 | // list X and the vertical axis represents list Y. The start of the two lists | |
44 | // is the top-left, while the ends are the bottom-right. The '·' represents | |
45 | // an unexplored node in the graph. The '\' indicates that the two symbols | |
46 | // from list X and Y are equal. The 'X' indicates that two symbols are similar | |
47 | // (but not exactly equal) to each other. The '#' indicates that the two symbols | |
48 | // are different (and not similar). The algorithm traverses this graph trying to | |
49 | // make the paths starting in the top-left and the bottom-right connect. | |
50 | // | |
51 | // The series of '.', 'X', 'Y', and 'M' characters at the bottom represents | |
52 | // the currently established path from the forward and reverse searches, | |
53 | // separated by a '|' character. | |
54 | ||
55 | const ( | |
56 | updateDelay = 100 * time.Millisecond | |
57 | finishDelay = 500 * time.Millisecond | |
58 | ansiTerminal = true // ANSI escape codes used to move terminal cursor | |
59 | ) | |
60 | ||
61 | var debug debugger | |
62 | ||
63 | type debugger struct { | |
64 | sync.Mutex | |
65 | p1, p2 EditScript | |
66 | fwdPath, revPath *EditScript | |
67 | grid []byte | |
68 | lines int | |
69 | } | |
70 | ||
71 | func (dbg *debugger) Begin(nx, ny int, f EqualFunc, p1, p2 *EditScript) EqualFunc { | |
72 | dbg.Lock() | |
73 | dbg.fwdPath, dbg.revPath = p1, p2 | |
74 | top := "┌─" + strings.Repeat("──", nx) + "┐\n" | |
75 | row := "│ " + strings.Repeat("· ", nx) + "│\n" | |
76 | btm := "└─" + strings.Repeat("──", nx) + "┘\n" | |
77 | dbg.grid = []byte(top + strings.Repeat(row, ny) + btm) | |
78 | dbg.lines = strings.Count(dbg.String(), "\n") | |
79 | fmt.Print(dbg) | |
80 | ||
81 | // Wrap the EqualFunc so that we can intercept each result. | |
82 | return func(ix, iy int) (r Result) { | |
83 | cell := dbg.grid[len(top)+iy*len(row):][len("│ ")+len("· ")*ix:][:len("·")] | |
84 | for i := range cell { | |
85 | cell[i] = 0 // Zero out the multiple bytes of UTF-8 middle-dot | |
86 | } | |
87 | switch r = f(ix, iy); { | |
88 | case r.Equal(): | |
89 | cell[0] = '\\' | |
90 | case r.Similar(): | |
91 | cell[0] = 'X' | |
92 | default: | |
93 | cell[0] = '#' | |
94 | } | |
95 | return | |
96 | } | |
97 | } | |
98 | ||
99 | func (dbg *debugger) Update() { | |
100 | dbg.print(updateDelay) | |
101 | } | |
102 | ||
103 | func (dbg *debugger) Finish() { | |
104 | dbg.print(finishDelay) | |
105 | dbg.Unlock() | |
106 | } | |
107 | ||
108 | func (dbg *debugger) String() string { | |
109 | dbg.p1, dbg.p2 = *dbg.fwdPath, dbg.p2[:0] | |
110 | for i := len(*dbg.revPath) - 1; i >= 0; i-- { | |
111 | dbg.p2 = append(dbg.p2, (*dbg.revPath)[i]) | |
112 | } | |
113 | return fmt.Sprintf("%s[%v|%v]\n\n", dbg.grid, dbg.p1, dbg.p2) | |
114 | } | |
115 | ||
116 | func (dbg *debugger) print(d time.Duration) { | |
117 | if ansiTerminal { | |
118 | fmt.Printf("\x1b[%dA", dbg.lines) // Reset terminal cursor | |
119 | } | |
120 | fmt.Print(dbg) | |
121 | time.Sleep(d) | |
122 | } |