gno.land/p/moul/x/daily/myersdiff/v0

The shortest edit script between two documents, Myers' algorithm: Lines, Slices, Budget, Hunks, Unified, UnifiedScript, and Script.Apply.

 1import "gno.land/p/moul/x/daily/myersdiff/v0"
 2
 3s := myersdiff.Lines("a\nb\nc", "a\nx\nc")
 4s.Edits        // [ a] [-b] [+x] [ c]
 5s.Added()      // 1
 6s.Minimal      // true
 7s.Apply([]string{"a", "b", "c"})     // ["a", "x", "c"], true
 8s.Apply([]string{"q", "b", "c"})     // ["a", "x", "c"], false: not this document
 9
10myersdiff.Unified(old, new, 2)       // @@ -1,4 +1,5 @@ and its lines

A realm that stores text and lets it be edited ends up holding two versions of it and no way to say what moved between them. Storing the diff instead of the second snapshot is the usual answer, and showing a reader what a proposal changes is the other. Both need the same thing first: which lines were added, which were removed, and in what order. Everything else is formatting.

The search is bounded by a budget, not by the input size, deliberately. Myers costs O((n+m)*d) where d is the number of differing lines, so two similar documents are cheap at any size and two unrelated ones are quadratic. On chain the caller picks both documents, so d is attacker-controlled and the input size alone bounds nothing useful. DefaultBudget caps the rounds at 256; past it the search gives up and returns a script that deletes everything and inserts everything, with Minimal set to false. MaxBudget (1,024) is the ceiling a caller cannot raise past, because the round count is what the search allocates against: one frontier snapshot is kept per round so the script can be walked back out of them.

The threshold is a line count, not a file size, and it is easy to read the wrong way. The default gives up past 256 changed lines at any file size: two 4,000-line documents differing in 10 lines are diffed minimally, two 300-line documents sharing nothing are not. The cost is gas, not only time, and a search that runs to the ceiling against two MaxLines documents was measured in the billions against a 3,000,000,000 block limit during this package's review. A caller diffing text that may be unrelated should pass a small budget and take the fallback, rather than pay for the full search in front of it.

Three behaviours worth knowing before you use it:

• A non-minimal script is still a correct script. The budget changes how short the answer is, never whether it is right: Apply replays the fallback into the same document it replays the minimal one into, and reports true for both. Check Minimal when you are about to store a diff as the canonical record of a change, and ignore it when you are rendering one for a human.
• Reads are total, construction panics. Lines, Unified and Budget panic above MaxLines (4,096 a side), and nothing else in the package panics at all: Hunks with a negative context, Apply against a document the script does not describe, a Hunk whose side is empty are all defined. Lines counts newlines before it splits, so the cap is enforced before the slice for an oversized document is allocated, not after. Construction is a transaction, where aborting is the useful answer. Rendering is a page, and a realm cannot be redeployed on the same path, so a Render that panics is broken permanently.
• Apply verifies, it does not merely replay. Every Equal and Delete edit has to match the line it consumes and the script has to consume the whole document, so a script built against a different document comes back with false. Without that check the round trip proves only that a script agrees with itself, which is a test that cannot fail.
• A moved line is a delete and an insert, not a move. Myers compares sequences and has no concept of identity, so reordering three lines costs the edits needed to explain the new order. A realm that wants move detection has to run it as a second pass over this script, pairing equal texts across the two sides.

Hunks(s, context) groups the script the way a review tool prints it, merging two changes into one hunk when their context would overlap. The @@ header follows diff(1) exactly, including the convention a pure insertion needs: a side contributing no lines reports the line before the hunk and a length of zero, so @@ -0,0 +1,2 @@ is what patch(1) expects to read back.

Unified emits the hunk bodies and nothing else. The --- and +++ file headers name files, which a realm does not have, so a caller that wants them adds them.

Line-oriented only. A word diff or a character diff is the same algorithm over a different sequence, and Slices is exported so a caller can supply one; the splitting and the rendering would be different and are not here.

Live demo: r/moul/x/daily/myersdiffdemo.

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.