myersdiffdemo.gno
7.75 Kb · 241 lines
1// Package myersdiffdemo is a small gnoweb demo of the
2// [p/moul/x/daily/myersdiff](/p/moul/x/daily/myersdiff/v0) library: four fixed
3// document pairs, each showing one behaviour worth knowing before using it in a
4// realm.
5//
6// It contains no diff logic of its own. Every line of every diff below is
7// computed by the library at render time, so a change in the algorithm shows up
8// here as a diff rather than as prose.
9//
10// Stateless and fixed-input, so Render is deterministic and pinnable.
11//
12// untrusted-render: no caller string reaches the page. The path selects a
13// scenario by exact match against the table below, and the only other segment
14// is parsed as an integer and clamped, so an unknown path renders the index
15// instead of echoing anything.
16package myersdiffdemo
17
18import (
19 "strconv"
20 "strings"
21
22 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
23 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
24 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/myersdiff/v0"
25)
26
27// scenario is one fixed pair of documents, chosen to show one property.
28type scenario struct {
29 key string
30 title string
31 note string
32 a string
33 b string
34 budget int
35}
36
37// scenarios are deliberately fixed rather than caller-supplied: output that
38// moves with the caller or the block height cannot be pinned by an example
39// test, and this realm's whole job is to be comparable from one render to the
40// next.
41var scenarios = []scenario{
42 {
43 key: "patch",
44 title: "A small patch in a large file",
45 note: "The ordinary case, and the one Myers is fast at: most of the file is " +
46 "untouched. The search ends after as many rounds as there are edits, not as " +
47 "there are lines, which is the whole reason to prefer it to an edit matrix.",
48 a: "package main\n\nimport \"fmt\"\n\nfunc main() {\n\tfmt.Println(\"hello\")\n}\n\n// TODO: say who\n",
49 b: "package main\n\nimport \"fmt\"\n\nfunc main() {\n\tname := \"world\"\n\tfmt.Println(\"hello\", name)\n}\n",
50 },
51 {
52 key: "insert",
53 title: "Appending to an empty document",
54 note: "Every line is new, and the header says so: the left side contributes no " +
55 "lines, so its start is 0 and its length is 0.",
56 a: "",
57 b: "one\ntwo\nthree",
58 },
59 {
60 key: "move",
61 title: "A moved line is a delete and an insert",
62 note: "Myers compares sequences, not contents: moving a line is the cheapest pair " +
63 "of edits that explains the new order, never a single move operation.",
64 a: "alpha\nbravo\ncharlie\ndelta",
65 b: "bravo\ncharlie\ndelta\nalpha",
66 },
67 {
68 key: "starved",
69 title: "A budget too small for the answer",
70 note: "Two unrelated documents cost O((n+m)*d) to compare, and on chain the caller " +
71 "picks d. With the budget set to 2 the search gives up and returns a correct " +
72 "non-minimal script instead of burning the gas or panicking.",
73 a: "red\norange\nyellow\ngreen\nblue",
74 b: "one\ntwo\nthree\nfour\nfive",
75 budget: 2,
76 },
77}
78
79const (
80 defaultContext = 2
81 maxContext = 6
82 realmPath = "/r/moul/x/daily/myersdiffdemo/v0"
83)
84
85// Render implements the gnoweb view.
86//
87// - "" or "/" : the index, with every scenario summarized.
88// - "/<key>" : one scenario at the default context width.
89// - "/<key>/<context>" : the same, with 0 to 6 lines of context.
90func Render(path string) string {
91 key, context := parsePath(path)
92 if key == "" {
93 return renderIndex()
94 }
95 for _, sc := range scenarios {
96 if sc.key == key {
97 return renderScenario(sc, context)
98 }
99 }
100 return renderIndex()
101}
102
103// parsePath returns the scenario key and the context width. It never returns
104// anything it was handed: the key is matched against the table by the caller
105// and the width is an integer, clamped.
106func parsePath(path string) (string, int) {
107 path = strings.TrimPrefix(path, "/")
108 if path == "" {
109 return "", defaultContext
110 }
111 parts := strings.SplitN(path, "/", 2)
112 context := defaultContext
113 if len(parts) == 2 {
114 if n, err := strconv.Atoi(parts[1]); err == nil {
115 context = n
116 }
117 }
118 if context < 0 {
119 context = 0
120 }
121 if context > maxContext {
122 context = maxContext
123 }
124 return parts[0], context
125}
126
127func renderIndex() string {
128 var sb strings.Builder
129 sb.WriteString("# Myers diff\n\n")
130 sb.WriteString("Demo of the [`p/moul/x/daily/myersdiff`](/p/moul/x/daily/myersdiff/v0) library: ")
131 sb.WriteString("the shortest edit script between two documents, the algorithm behind `git diff`.\n\n")
132 sb.WriteString("It walks a grid whose diagonals are matching lines, taking the furthest-reaching ")
133 sb.WriteString("path at each round, and stops the first time a path reaches the far corner. ")
134 sb.WriteString("That round number is the number of edits, and it is minimal because no shorter ")
135 sb.WriteString("path was available at any earlier round.\n\n")
136
137 sb.WriteString("## The scenarios\n\n")
138 t := ui.NewTable("scenario", "edits", "minimal", "what it shows")
139 for _, sc := range scenarios {
140 s := diffOf(sc)
141 t.Row(
142 md.Link(sc.key, realmPath+":"+sc.key),
143 strconv.Itoa(s.Added()+s.Deleted()),
144 yesNo(s.Minimal),
145 sc.title,
146 )
147 }
148 sb.WriteString(t.String())
149
150 sb.WriteString("\n## Context width\n\n")
151 sb.WriteString("Append a number to widen or narrow the unchanged lines printed around each change: ")
152 sb.WriteString("[`patch/0`](" + realmPath + ":patch/0) shows the changes alone, ")
153 sb.WriteString("[`patch/6`](" + realmPath + ":patch/6) shows the whole file as one hunk. ")
154 sb.WriteString("Anything out of range is clamped to 0..6.\n\n")
155
156 sb.WriteString("## API\n\n")
157 sb.WriteString("- `Lines(a, b string) Script` is the whole surface for text.\n")
158 sb.WriteString("- `Script.Apply(a []string) ([]string, bool)` replays the script and says whether it describes that document.\n")
159 sb.WriteString("- `Hunks(s Script, context int) []Hunk` groups the script the way a review tool prints it.\n")
160 sb.WriteString("- `Unified(a, b string, context int) string` is the two above, as text.\n")
161 return sb.String()
162}
163
164func renderScenario(sc scenario, context int) string {
165 s := diffOf(sc)
166
167 var sb strings.Builder
168 sb.WriteString("# ")
169 sb.WriteString(sc.title)
170 sb.WriteString("\n\n")
171 sb.WriteString(sc.note)
172 sb.WriteString("\n\n")
173
174 sb.WriteString("## The diff\n\n")
175 sb.WriteString("Context: ")
176 sb.WriteString(strconv.Itoa(context))
177 sb.WriteString(" line(s).\n\n")
178 body := myersdiff.UnifiedScript(s, context)
179 if body == "" {
180 body = "(the two documents are identical)\n"
181 }
182 sb.WriteString("```diff\n")
183 sb.WriteString(body)
184 sb.WriteString("```\n\n")
185
186 sb.WriteString("## The script\n\n")
187 t := ui.NewTable("property", "value")
188 t.Row("inserted lines", strconv.Itoa(s.Added()))
189 t.Row("deleted lines", strconv.Itoa(s.Deleted()))
190 t.Row("unchanged lines", strconv.Itoa(s.Unchanged()))
191 t.Row("minimal", yesNo(s.Minimal))
192 sb.WriteString(t.String())
193 sb.WriteString("\n")
194
195 sb.WriteString("Replaying it on the left document reproduces the right one ")
196 sb.WriteString("**")
197 sb.WriteString(yesNo(applies(sc, s)))
198 sb.WriteString("**, which is the property that holds even when the script is not minimal.\n\n")
199
200 sb.WriteString("[back](")
201 sb.WriteString(realmPath)
202 sb.WriteString(")\n")
203 return sb.String()
204}
205
206func diffOf(sc scenario) myersdiff.Script {
207 return myersdiff.Budget(lines(sc.a), lines(sc.b), sc.budget)
208}
209
210// applies is the demo asserting the library's own claim rather than repeating
211// it: the rendered answer comes from running Apply, not from a constant.
212func applies(sc scenario, s myersdiff.Script) bool {
213 got, ok := s.Apply(lines(sc.a))
214 if !ok {
215 return false
216 }
217 want := lines(sc.b)
218 if len(got) != len(want) {
219 return false
220 }
221 for i := range got {
222 if got[i] != want[i] {
223 return false
224 }
225 }
226 return true
227}
228
229func lines(s string) []string {
230 if s == "" {
231 return []string{}
232 }
233 return strings.Split(s, "\n")
234}
235
236func yesNo(b bool) string {
237 if b {
238 return "yes"
239 }
240 return "no"
241}