Lexer-based diff for MoonBit code: weighted token alignment with HTML rendering

diff

lexer

html

Download zip

Author

bobzhang

Version

0.1.2

License

Apache-2.0

Repository

github.com/bobzhang/ldiff

Last updated

10 days ago

Downloads

Dependencies

moonbitlang/lexer0.3.16

#ldiff — lexer-based diff for MoonBit code

Line diffs whose changed regions are aligned by weighted token similarity and highlighted word-by-word, rendered to HTML. Tokens come from the real MoonBit lexer (moonbitlang/lexer), so strings, comments and identifiers are classified the way the language sees them; line structure comes from moonbitlang/core/diff (Myers / patience).

let html = @ldiff.html_page(
  title="my change",
  @ldiff.side_by_side_html(old=old_lines, new=new_lines),
)

unified_html renders the same alignment as a single-column view. See __snapshot__/demo.html for rendered output (open it in a browser).

Notes:

html_page inserts body verbatim (it is your rendered HTML); only pass it output from this library or HTML you trust.
Lines are lexed independently. This is safe for MoonBit (a line-oriented language with no block comments); multiline raw strings (#|) lex as one Str token per line.

#How it works

Line diff (@diff, Myers/patience) gives structure and hunks.
Each Delete+Insert replacement block is aligned: lines pair by a weighted token edit distance (Wagner–Fischer), maximizing the total positive margin sum(similarity − 0.4) under a monotone alignment.
Each aligned pair's highlights are the alignment's own traceback (equal / substitution / delete / insert), so the script scored is exactly the script rendered; substitutions show as positionally paired runs.

Weight classes (integer, ×20): identifiers/keywords/literals 20, punctuation 6, comment content 2, whitespace 1, comment boilerplate (//, comment spacing) 0. Comments therefore help pairing (identical comments win ties) but can never veto it, and unrelated comment-only lines do not pair. Same-kind substitution costs 1.5×weight — renames align cheaply, but two lines with nothing in common stay under the pairing threshold.

All scoring is integer (permille similarities, stored backpointers): results are bit-identical across wasm, wasm-gc, js and native.

Cost discipline: dimension guards, a per-line token cap, an early-exit DP cell budget (2M) and a per-pair traceback guard; over budget a block renders as plain unpaired rows (in the style of difflib's _plain_replace), never as misleadingly highlighted pairs.

The design and implementation were hardened through several rounds of adversarial review; the regression tests pin the semantics (comment tie-breaking, zero-mass lines, margin-vs-raw-similarity objective, budget fallbacks, delete-before-insert ordering, traceback reconstruction).

#Development

Until a toolchain release bundles moonbitlang/core/diff, build against a core checkout that has it:

MOON_CORE_OVERRIDE=~/git/core moon test

Tok

source

pub struct Tok {
  kind : TokKind
  text : String
}

One diffable token: its weight class and its exact source text. Concatenating the text of tokenize_line's result reproduces the line.

Tok::kind

source

fn Tok::kind(self : Tok) -> TokKind

Tok::text

source

fn Tok::text(self : Tok) -> String

TokKind

source

pub(all) enum TokKind {
  Word
  Str
  Punct
  Comment
  Filler
  Space
  Marker
} derive(Eq)

The weight class of a token. Weights encode semantic importance for the alignment scorer: identifiers and literals carry full signal, punctuation less, comment content little, and comment boilerplate / whitespace none to almost none.

TokKind::equal

source

fn TokKind::equal(TokKind, TokKind) -> Bool

Keep == / != available as dot-callable methods on TokKind now that implicit promotion of impl Eq methods is deprecated.

TokKind::not_equal

source

fn TokKind::not_equal(x : TokKind, y : TokKind) -> Bool

Keep == / != available as dot-callable methods on TokKind now that implicit promotion of impl Eq methods is deprecated.

html_page

source

fn html_page(title~ : String, body : String) -> String

Wrap rendered diff HTML in a complete standalone page with default styling (light red/green rows, deeper word-level highlights).

side_by_side_html

source

fn side_by_side_html(old~ : ArrayView[String], new~ : ArrayView[String], context? : Int) -> String

GitHub-style split (side-by-side) view of a diff, as an HTML <table>. Equal lines appear on both sides; replacement blocks are aligned by weighted similarity and their paired rows carry word-level highlights; unpaired lines leave the other cell empty. Style it with html_page or your own CSS (classes: split, hunk-header, ctx, del, add, empty, wd, wa).

similarity

source

fn similarity(a : String, b : String) -> Int

Line similarity in permille: 1000 * (mass - dist) / mass over both sides' weighted mass. Zero-mass lines (empty or filler-only) carry no evidence either way and pair only when textually identical.

tokenize_line

source

fn tokenize_line(line : String) -> Array[Tok]

Tokenize one line of MoonBit source with the real MoonBit lexer (moonbitlang/lexer), mapping language tokens to weight classes:

identifiers / keywords / numbers -> Word
string, char, bytes and regex literals -> Str (one token each)
operators and separators -> Punct
comments -> content-tokenized Comment words + weightless Filler
gaps between token spans (whitespace the lexer skipped) -> Space, reconstructed from positions so concatenation reproduces the line

Lexical errors are ignored (diffs are routinely taken of incomplete code); the lexer's best-effort token stream is used as is.

unified_html

source

fn unified_html(old~ : ArrayView[String], new~ : ArrayView[String], context? : Int) -> String

Unified (single-column) view of a diff: hunk headers followed by /-/+-prefixed lines, with the same weighted alignment and word-level highlights as the split view — deletions of a replacement block first, then its insertions. Wrap the result in <pre> or use html_page.