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
8package diff
9
10import (
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
56const (
57 updateDelay = 100 * time.Millisecond
58 finishDelay = 500 * time.Millisecond
59 ansiTerminal = true // ANSI escape codes used to move terminal cursor
60)
61
62var debug debugger
63
64type debugger struct {
65 sync.Mutex
66 p1, p2 EditScript
67 fwdPath, revPath *EditScript
68 grid []byte
69 lines int
70}
71
72func (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
100func (dbg *debugger) Update() {
101 dbg.print(updateDelay)
102}
103
104func (dbg *debugger) Finish() {
105 dbg.print(finishDelay)
106 dbg.Unlock()
107}
108
109func (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
117func (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}