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