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