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.

Playground

gnomod.toml

module = "gno.land/r/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/myersdiffdemo/v0"
gno = "0.9"
private = true

[addpkg]
  creator = "g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv"
  height = 914308
  max_deposit = "7000000ugnot"

myersdiffdemo.gno

// Package myersdiffdemo is a small gnoweb demo of the
// [p/moul/x/daily/myersdiff](/p/moul/x/daily/myersdiff/v0) library: four fixed
// document pairs, each showing one behaviour worth knowing before using it in a
// realm.
//
// It contains no diff logic of its own. Every line of every diff below is
// computed by the library at render time, so a change in the algorithm shows up
// here as a diff rather than as prose.
//
// Stateless and fixed-input, so Render is deterministic and pinnable.
//
// untrusted-render: no caller string reaches the page. The path selects a
// scenario by exact match against the table below, and the only other segment
// is parsed as an integer and clamped, so an unknown path renders the index
// instead of echoing anything.
package myersdiffdemo

import (
	"strconv"
	"strings"

	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/myersdiff/v0"
)

// scenario is one fixed pair of documents, chosen to show one property.
type scenario struct {
	key    string
	title  string
	note   string
	a      string
	b      string
	budget int
}

// scenarios are deliberately fixed rather than caller-supplied: output that
// moves with the caller or the block height cannot be pinned by an example
// test, and this realm's whole job is to be comparable from one render to the
// next.
var scenarios = []scenario{
	{
		key:   "patch",
		title: "A small patch in a large file",
		note: "The ordinary case, and the one Myers is fast at: most of the file is " +
			"untouched. The search ends after as many rounds as there are edits, not as " +
			"there are lines, which is the whole reason to prefer it to an edit matrix.",
		a: "package main\n\nimport \"fmt\"\n\nfunc main() {\n\tfmt.Println(\"hello\")\n}\n\n// TODO: say who\n",
		b: "package main\n\nimport \"fmt\"\n\nfunc main() {\n\tname := \"world\"\n\tfmt.Println(\"hello\", name)\n}\n",
	},
	{
		key:   "insert",
		title: "Appending to an empty document",
		note: "Every line is new, and the header says so: the left side contributes no " +
			"lines, so its start is 0 and its length is 0.",
		a:    "",
		b:    "one\ntwo\nthree",
	},
	{
		key:   "move",
		title: "A moved line is a delete and an insert",
		note: "Myers compares sequences, not contents: moving a line is the cheapest pair " +
			"of edits that explains the new order, never a single move operation.",
		a:    "alpha\nbravo\ncharlie\ndelta",
		b:    "bravo\ncharlie\ndelta\nalpha",
	},
	{
		key:   "starved",
		title: "A budget too small for the answer",
		note: "Two unrelated documents cost O((n+m)*d) to compare, and on chain the caller " +
			"picks d. With the budget set to 2 the search gives up and returns a correct " +
			"non-minimal script instead of burning the gas or panicking.",
		a:      "red\norange\nyellow\ngreen\nblue",
		b:      "one\ntwo\nthree\nfour\nfive",
		budget: 2,
	},
}

const (
	defaultContext = 2
	maxContext     = 6
	realmPath      = "/r/moul/x/daily/myersdiffdemo/v0"
)

// Render implements the gnoweb view.
//
//   - "" or "/"              : the index, with every scenario summarized.
//   - "/<key>"               : one scenario at the default context width.
//   - "/<key>/<context>"     : the same, with 0 to 6 lines of context.
func Render(path string) string {
	key, context := parsePath(path)
	if key == "" {
		return renderIndex()
	}
	for _, sc := range scenarios {
		if sc.key == key {
			return renderScenario(sc, context)
		}
	}
	return renderIndex()
}

// parsePath returns the scenario key and the context width. It never returns
// anything it was handed: the key is matched against the table by the caller
// and the width is an integer, clamped.
func parsePath(path string) (string, int) {
	path = strings.TrimPrefix(path, "/")
	if path == "" {
		return "", defaultContext
	}
	parts := strings.SplitN(path, "/", 2)
	context := defaultContext
	if len(parts) == 2 {
		if n, err := strconv.Atoi(parts[1]); err == nil {
			context = n
		}
	}
	if context < 0 {
		context = 0
	}
	if context > maxContext {
		context = maxContext
	}
	return parts[0], context
}

func renderIndex() string {
	var sb strings.Builder
	sb.WriteString("# Myers diff\n\n")
	sb.WriteString("Demo of the [`p/moul/x/daily/myersdiff`](/p/moul/x/daily/myersdiff/v0) library: ")
	sb.WriteString("the shortest edit script between two documents, the algorithm behind `git diff`.\n\n")
	sb.WriteString("It walks a grid whose diagonals are matching lines, taking the furthest-reaching ")
	sb.WriteString("path at each round, and stops the first time a path reaches the far corner. ")
	sb.WriteString("That round number is the number of edits, and it is minimal because no shorter ")
	sb.WriteString("path was available at any earlier round.\n\n")

	sb.WriteString("## The scenarios\n\n")
	t := ui.NewTable("scenario", "edits", "minimal", "what it shows")
	for _, sc := range scenarios {
		s := diffOf(sc)
		t.Row(
			md.Link(sc.key, realmPath+":"+sc.key),
			strconv.Itoa(s.Added()+s.Deleted()),
			yesNo(s.Minimal),
			sc.title,
		)
	}
	sb.WriteString(t.String())

	sb.WriteString("\n## Context width\n\n")
	sb.WriteString("Append a number to widen or narrow the unchanged lines printed around each change: ")
	sb.WriteString("[`patch/0`](" + realmPath + ":patch/0) shows the changes alone, ")
	sb.WriteString("[`patch/6`](" + realmPath + ":patch/6) shows the whole file as one hunk. ")
	sb.WriteString("Anything out of range is clamped to 0..6.\n\n")

	sb.WriteString("## API\n\n")
	sb.WriteString("- `Lines(a, b string) Script` is the whole surface for text.\n")
	sb.WriteString("- `Script.Apply(a []string) ([]string, bool)` replays the script and says whether it describes that document.\n")
	sb.WriteString("- `Hunks(s Script, context int) []Hunk` groups the script the way a review tool prints it.\n")
	sb.WriteString("- `Unified(a, b string, context int) string` is the two above, as text.\n")
	return sb.String()
}

func renderScenario(sc scenario, context int) string {
	s := diffOf(sc)

	var sb strings.Builder
	sb.WriteString("# ")
	sb.WriteString(sc.title)
	sb.WriteString("\n\n")
	sb.WriteString(sc.note)
	sb.WriteString("\n\n")

	sb.WriteString("## The diff\n\n")
	sb.WriteString("Context: ")
	sb.WriteString(strconv.Itoa(context))
	sb.WriteString(" line(s).\n\n")
	body := myersdiff.UnifiedScript(s, context)
	if body == "" {
		body = "(the two documents are identical)\n"
	}
	sb.WriteString("```diff\n")
	sb.WriteString(body)
	sb.WriteString("```\n\n")

	sb.WriteString("## The script\n\n")
	t := ui.NewTable("property", "value")
	t.Row("inserted lines", strconv.Itoa(s.Added()))
	t.Row("deleted lines", strconv.Itoa(s.Deleted()))
	t.Row("unchanged lines", strconv.Itoa(s.Unchanged()))
	t.Row("minimal", yesNo(s.Minimal))
	sb.WriteString(t.String())
	sb.WriteString("\n")

	sb.WriteString("Replaying it on the left document reproduces the right one ")
	sb.WriteString("**")
	sb.WriteString(yesNo(applies(sc, s)))
	sb.WriteString("**, which is the property that holds even when the script is not minimal.\n\n")

	sb.WriteString("[back](")
	sb.WriteString(realmPath)
	sb.WriteString(")\n")
	return sb.String()
}

func diffOf(sc scenario) myersdiff.Script {
	return myersdiff.Budget(lines(sc.a), lines(sc.b), sc.budget)
}

// applies is the demo asserting the library's own claim rather than repeating
// it: the rendered answer comes from running Apply, not from a constant.
func applies(sc scenario, s myersdiff.Script) bool {
	got, ok := s.Apply(lines(sc.a))
	if !ok {
		return false
	}
	want := lines(sc.b)
	if len(got) != len(want) {
		return false
	}
	for i := range got {
		if got[i] != want[i] {
			return false
		}
	}
	return true
}

func lines(s string) []string {
	if s == "" {
		return []string{}
	}
	return strings.Split(s, "\n")
}

func yesNo(b bool) string {
	if b {
		return "yes"
	}
	return "no"
}

myersdiffdemo_test.gno

package myersdiffdemo

import (
	"strings"
	"testing"

	"gno.land/p/nt/uassert/v0"
)

func TestUnknownPathFallsBackToTheIndex(t *testing.T) {
	index := Render("")
	uassert.Equal(t, index, Render("/"))
	uassert.Equal(t, index, Render("/nope"))
	uassert.Equal(t, index, Render("/patch2"))
}

// TestNoCallerEchoOnThePage is the escaping question asked the only way that
// settles it: feed the path every construct the sanitizer exists to stop, then
// assert none of it reached the page. This realm answers by never rendering a
// caller string at all, so the assertion is that the output is byte-identical
// to the index.
func TestNoCallerEchoOnThePage(t *testing.T) {
	index := Render("")
	hostile := []string{
		"/[click](https://evil.example)",
		"/![x](https://evil.example/p.png)",
		"/<gno-columns>",
		"/a`b",
		"/x\ny",
		"/patch/[link](https://evil.example)",
	}
	for _, p := range hostile {
		got := Render(p)
		uassert.False(t, strings.Contains(got, "evil.example"), "a caller URL reached the page")
		uassert.False(t, strings.Contains(got, "<gno-"), "caller chrome reached the page")
		if !strings.HasPrefix(p, "/patch/") {
			uassert.Equal(t, index, got)
		}
	}
	// A hostile context segment is parsed as an integer, fails, and leaves the
	// default width, so the page is the ordinary one.
	uassert.Equal(t, Render("/patch"), Render("/patch/[link](https://evil.example)"))
}

func TestContextIsClamped(t *testing.T) {
	uassert.Equal(t, Render("/patch/0"), Render("/patch/-3"))
	uassert.Equal(t, Render("/patch/6"), Render("/patch/99"))
	uassert.Equal(t, Render("/patch/2"), Render("/patch"))

	// Context 0 prints changed lines only, so no unchanged line of the fixture
	// survives into the diff body.
	narrow := Render("/patch/0")
	uassert.False(t, strings.Contains(narrow, " package main"), "context 0 printed an unchanged line")
	wide := Render("/patch/6")
	uassert.True(t, strings.Contains(wide, " package main"), "context 6 dropped an unchanged line")
}

func TestStarvedScenarioSaysSo(t *testing.T) {
	page := Render("/starved")
	uassert.True(t, strings.Contains(page, "| minimal | no |"), "the starved page should report a non-minimal script")
	uassert.True(t, strings.Contains(page, "reproduces the right one **yes**"), "a non-minimal script still applies")

	ok := Render("/move")
	uassert.True(t, strings.Contains(ok, "| minimal | yes |"), "the move page should report a minimal script")
}

// TestEveryScenarioApplies walks the whole table rather than the one scenario a
// hand-written test would pick: a fixture added later is covered the day it is
// added, not the day someone remembers it.
func TestEveryScenarioApplies(t *testing.T) {
	for _, sc := range scenarios {
		s := diffOf(sc)
		uassert.True(t, applies(sc, s), "scenario "+sc.key+" does not replay into its right-hand document")
		page := Render("/" + sc.key)
		uassert.True(t, strings.Contains(page, "```diff"), "scenario "+sc.key+" rendered no diff block")
	}
}

render_example_test.gno

package myersdiffdemo

// ExampleRender pins the realm Render output as a testable example.
//
// The block below is copied verbatim from what gno printed, never hand typed:
// every diff line and every count in it is computed by the library under test,
// so a change in the algorithm shows up here as a diff.
func ExampleRender() {
	print(Render(""))
	// Output:
	// # Myers diff
	//
	// Demo of the [`p/moul/x/daily/myersdiff`](/p/moul/x/daily/myersdiff/v0) library: the shortest edit script between two documents, the algorithm behind `git diff`.
	//
	// It walks a grid whose diagonals are matching lines, taking the furthest-reaching path at each round, and stops the first time a path reaches the far corner. That round number is the number of edits, and it is minimal because no shorter path was available at any earlier round.
	//
	// ## The scenarios
	//
	// | scenario | edits | minimal | what it shows |
	// | --- | --- | --- | --- |
	// | [patch](/r/moul/x/daily/myersdiffdemo/v0:patch) | 5 | yes | A small patch in a large file |
	// | [insert](/r/moul/x/daily/myersdiffdemo/v0:insert) | 3 | yes | Appending to an empty document |
	// | [move](/r/moul/x/daily/myersdiffdemo/v0:move) | 2 | yes | A moved line is a delete and an insert |
	// | [starved](/r/moul/x/daily/myersdiffdemo/v0:starved) | 10 | no | A budget too small for the answer |
	//
	// ## Context width
	//
	// Append a number to widen or narrow the unchanged lines printed around each change: [`patch/0`](/r/moul/x/daily/myersdiffdemo/v0:patch/0) shows the changes alone, [`patch/6`](/r/moul/x/daily/myersdiffdemo/v0:patch/6) shows the whole file as one hunk. Anything out of range is clamped to 0..6.
	//
	// ## API
	//
	// - `Lines(a, b string) Script` is the whole surface for text.
	// - `Script.Apply(a []string) ([]string, bool)` replays the script and says whether it describes that document.
	// - `Hunks(s Script, context int) []Hunk` groups the script the way a review tool prints it.
	// - `Unified(a, b string, context int) string` is the two above, as text.
}