Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

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}