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 910myersdiff.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.
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.
Overview
Package myersdiff computes the shortest edit script between two sequences of lines, using Myers' greedy algorithm: the same one git, diff and every review tool run to turn two documents into a list of additions and deletions.
A realm that stores text and lets it be edited has two versions of it and no way to show what moved between them. Storing a diff instead of a snapshot is the usual answer, and this is the half that produces it.
The cost of the search is bounded by a budget, not by the input size alone: see Budget for why a minimal diff is sometimes the wrong answer on chain.
DefaultBudget caps the number of rounds the search may run before it gives up and returns a non-minimal script. Myers' algorithm 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 the input, so the cost has to be bounded by something the caller does not control.
The threshold this sets is worth stating plainly, because it is not a size: 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. A caller whose documents are large and similar is well inside it; a caller diffing unrelated text is always outside it and should pass a small budget rather than pay for the search before the fallback.
The cost is in gas, not just in time: a search that runs to the default ceiling against two MaxLines documents was measured in the billions of gas against a 3,000,000,000 block limit during the review of this package, before the frontier was resized to the round ceiling. Treat a full-ceiling search as something to avoid rather than something to budget for.
MaxBudget is the hard ceiling on the rounds any caller can ask for, whatever budget it passes.
It exists because the round count, not the input size, is what the search allocates against: one snapshot of the frontier is kept per round so the script can be walked back out of them. Without the ceiling, two documents at MaxLines and a large budget would permit 8,192 snapshots, and the budget parameter would hand a caller the memory bill as a dial. The useful direction for a caller is downwards.
MaxLines caps each side of the comparison. The algorithm allocates two slices proportional to n+m before it compares anything, so the size is checked before the work starts rather than discovered during it.
1const(2// Delete marks a line present in a and absent from b.3DeleteOp=-14// Equal marks a line present in both, unchanged.5EqualOp=06// Insert marks a line absent from a and present in b.7InsertOp=18)
Unified renders the body of a unified diff: the @@ headers and their lines, and nothing else. The --- and +++ file headers name files, which a realm does not have, so they are the caller's to add.
Hunks groups a script into the runs a unified diff prints, with context unchanged lines around each change. A negative context is treated as zero; a script with no changes produces no hunks.
Budget diffs two line sequences, stopping the search after at most budget rounds. A budget of zero or less means DefaultBudget; a budget larger than len(a)+len(b) is capped at it, since no minimal script is longer than that.
It panics when either side exceeds MaxLines. Construction is a transaction, where aborting is the useful answer; reading is where totality matters, and every method on the resulting Script is total.
Hunk is a contiguous run of the script worth printing: every change, plus up to context unchanged lines on each side of it.
AStart and BStart are 1-based line numbers. When a side contributes no lines at all, its start is the number of the line before the hunk and its length is zero, which is what diff(1) prints for a pure insertion into an empty file.
Script is a complete edit script turning a into b.
Minimal is false when the search hit its budget and the script fell back to deleting everything and inserting everything. That script is still correct: applying it to a yields b. It is simply not the shortest one.
Apply replays the script against a and returns the lines it produces, which is b when the script came from Slices(a, b).
The second return reports whether a is the document the script describes: every Equal and Delete edit has to match the line it consumes, and the script has to consume all of a. It is false for a script built against a different document, which is the check that makes a stored diff verifiable rather than merely replayable. The lines are returned either way, because they are what the script says and a caller deciding what to do about a mismatch usually wants to see both.
