Crux: A Diff That Reads the Program

Let a formatter loose in the same commit as a real fix and the diff is hundreds of lines long, with the fix somewhere in it. Crux sits on top of git, compares the syntax trees of the two revisions instead of their lines, and tells the reviewer what happened to the program, not to its text. This page covers how it does that, what it refuses to do, and a working tree diff you can edit.

C# .NET Roslyn Tree Diffing TypeScript Git MCP

What it does

Git compares lines, and a line is a poor unit of meaning. A language gives its authors many spellings of the same program, so a commit that changes one operator and also lets the formatter loose reads, in a line diff, as a rewrite. Crux answers the question the reviewer actually has. Take a commit to a small shopping-cart class in which a documentation comment was reworded, a method was moved to the top, the braces came off a loop and an if, a callback became an expression, and one + became a -. A line diff marks twenty-three lines. This is the whole report:

cart.ts
  # class Cart                       comment only   L5-28
      update DocComment   'A cart.' -> 'A cart that holds items and prices them.'   L4
  >   method clear                   moved from L30-32   L8-10
  ~   method total                   behavioral   L20-27
        update Binary     '+' -> '-'   L26

1 behavioral, 0 cosmetic, 1 comment only, 1 moved   (git diff: 23 changed lines)

Every row is a declaration and every marker is a claim: ~ changed, + new, - gone, > relocated, # comments only, and = for text that differs while the program does not, with the rules that say why. Unmarked rows are there for orientation. That commit is the first example in the demo at the bottom of this page, and the block above is what the demo prints for it.

Nothing about the repository changes: Crux reads git and replaces none of it. Six languages have backends (C#, TypeScript, JSON, YAML, XML, Markdown), and four other commands are built on the same trees: merge advice, a rename, a structural query language, and verified structural edits.

One file, six steps

  1. Resolve. Get the list of changed files from git, and both versions of each.
  2. Lower. Parse each version and translate the parser's tree into a common form.
  3. Match. Work out which node of the old tree is which node of the new one.
  4. Script. Turn the pairing into a list of edits, each an insert, delete, update or move.
  5. Attribute. File every edit under the closest declaration around it.
  6. Render. Print the declarations that have something to report, with line numbers from the actual files.

When a step fails for a file, that file gets git's ordinary diff and a line saying so. No file is skipped quietly. The demo runs steps two to six in your browser.

Decisions worth explaining

Normalize while lowering, never by rewriting

The obvious way to ignore formatting is to rewrite both files into a canonical form and diff the results. It fails at the last step: the reported line numbers belong to the rewritten text, not the file the reviewer has open. So nothing is ever rewritten. Each backend lowers its parser's tree into an intermediate representation, a normalization rule decides the canonical shape while the node is being built, and every node keeps a span into the original, untouched source. int Get() => _x; and its block-bodied twin lower to the same shape, and both still know which characters they came from.

The tree also accounts for every character. Each node holds the runs of source that none of its children cover, so across the tree those runs partition the file, and walking the tree reproduces the file exactly. That equality is tested over every source file in the repository. A token no node owns, or one two nodes both claim, breaks it, which is how a careless rule gets caught before it reports a wrong line.

Three ways to pair two trees

Matching runs in three phases, and each phase only adds pairs. The first hashes every subtree by shape and, working from the largest down, pairs any shape that appears exactly once in each revision, together with everything inside it. That accounts for all the code nobody touched, which is most of any commit and most of the noise. The second looks at containers that are still unmatched and scores each candidate by how many of its descendants already correspond.

The third exists because similarity is the wrong question for something small. A method of twenty nodes with one changed operator scores under the threshold, and without help it would report as a deletion and an addition: as though the method had been thrown away and written again. So the last phase walks down the pairs already made and pairs the remaining children by position, first by kind and name, then by kind alone, and only where the choice is forced: one loose node of that description in each tree. If there are two, nothing distinguishes them, and a wrong guess would read exactly like a finding. They stay unpaired and are reported as an addition and a removal.

The one answer it may not give

A tool that prints less than git is asking to be trusted about everything it left out. So the design is organized around one failure: saying unchanged about a program that changed. Equal hashes are a hint, confirmed by comparing the two subtrees node by node before they are paired. Pairing more cannot hide anything, because two paired nodes that differ always yield an edit. A declaration whose trees differ with no edit to explain it is reported as changed, coarsely, instead of being called cosmetic. A difference outside every declaration lands on the file. And before a hunk is printed, every line of it is tested against the revision it names; a report that fails loses its place to git's diff.

The other half is making the suppression inspectable. crux why lists everything that was kept out of the behavioral count, each with the rule responsible, and any rule can be switched off when a suppression looks wrong.

Is a move a change?

When a paired node sits somewhere else in the new tree, that is a move, and moves are never dropped. Whether it counts as behavioral depends on two questions. Did it change parent? Then it answers to a different qualified name and its callers all have to change. Is order part of the program at this position? Two methods can swap freely. Two statements cannot. The interesting cases are the ones a kind does not settle:

What movedVerdict
A method, a type, an import in C#Free. Reported, not counted as behavioral.
A statement, an argument, a parameterBehavioral, always.
A field with an initializerBehavioral: initializers run in declaration order.
A field of a structBehavioral: layout follows declaration order and interop reads it.
An enum memberFree only when every member states its own value.
An import in TypeScriptBehavioral unless type-only: module evaluation follows import order.

A swap of two parameters gets special care. The alignment that finds moves reports the fewest that explain a permutation, which for a swap is one, and move Parameter 'discount' is true without being the change. Every caller still passes its arguments the old way round, and if the two share a type nothing fails to compile. So a reordered parameter list is reported as one edit, showing the list before and after.

Rules that are built and switched off

Five normalization rules are on by default for C#: whitespace, expression bodies, optional braces, the order of using directives, and #region markers. Four more are implemented, tested and off, and the reasons differ. Redundant parentheses are there because somebody wanted them there, usually to make a long condition readable, and that is worth a reviewer's glance. String against string and this.x against x are equivalences only while the file does not redefine the names involved, which a tool that reads syntax cannot rule out: a file may declare its own String, or a local that shadows the field. And modifier order is off because the difference it would suppress does not occur: across the two codebases I measured, one line in five thousand files writes its modifiers out of order, and no commit ever permuted them. Hiding something by default implies it was worth checking, and here there was nothing to check.

An addition that is mostly a copy

A second test is usually written by copying the first, and a line diff marks every line of it. Crux looks for where an addition's text already exists and, when it finds a source, shows the new code as a delta from it: eleven marked lines become the three that differ, under a header that says where the rest came from. All the changed files are searched together, so a block cut from one file and pasted into another is recognised in both reports. For text copied from a file the commit never touched, Crux has git grep for the most distinctive lines it could not place and parses only the files that turn up.

Syntax only, and honest about it

Resolving names needs a project that restores and builds, for the old revision as well as the new, and old commits frequently no longer build at all. So Crux works file by file, on syntax alone. That limit is stated everywhere it matters instead of being papered over. The rename command sorts every site into three tiers: proven by syntax alone, likely because no other scope it searched declares that name, and refused because a rival declaration or a shadowing local makes the argument unsafe. The merge command takes the base, ours and theirs versions of each conflicted file from the index, reports which conflicts disappear when the three are compared as trees, and calls its own verdict advice, not proof that the result compiles.

Edits an agent can be held to

The same trees answer queries that text search cannot: a call to a method is not its declaration, and invocation("OldApi") knows the difference. Edits are expressions that select whole code units and end in an action. The edited file is produced in memory first and diffed against the original by Crux itself. Unless the only differences are the ones the action called for, the write is abandoned. A plan can be frozen, read as a reverse patch, and applied later, at which point it is rechecked against the working tree and refused if a selected node has changed. That is the property a coding agent needs from a tool: an edit that either does exactly what was asked or does nothing.

What it is worth

Less than the opening example suggests, and that is worth saying plainly. On two production C# codebases, two hundred commits apiece, its reports marked 5.1 and 15.0 percent fewer lines than git diff did for the same files. It can only take out noise that is there, and a tidy history does not hold much. Most commits in a disciplined repository are already what they look like, and most of the lower figure's history is files that exist on one side only, and in a brand-new file there is no noise to find.

The value is concentrated in the commits that are hard to review: the formatter run with a fix buried in it, the extracted method, the rename that touches dozens of files, where the report collapses an edit that recurs at every call site into one line and points at the declarations that do not fit the pattern. Those are the ones where a reviewer skims, and skimming is where the two lines get lost.

Interactive Demo

Two revisions of one TypeScript file. Both are editable, and everything below them is recomputed as you type: parse, match, edit script, report. The grey bars are the lines a line diff marks. The coloured ones are the lines the tree diff holds an edit against. Grey without colour is a line that reads differently and runs the same.

One caution before you start editing. Crux was built for C# and refined against the history of two production C# codebases, and that is where its judgment is best. This demo reads TypeScript, because the TypeScript compiler runs in a browser and Roslyn does not, and it is a small re-creation written for this page. If you push it into a report that looks wrong, that is most likely the demo and not the method. The details are in the note at the bottom.

A doc comment was reworded, a method moved, braces came off a loop and an if, a callback became an expression, and one operator changed. A line diff marks all of it.

Before 34 lines
After 29 lines
a line diff marks this line the tree diff holds an edit against it

Loading the parser. The comparison runs in your browser once it arrives.

Things to try

  • Find the operator. The first example is the commit described above. Hover a row of the summary to see its lines in both panes, then open Unified: the hunk marks two lines and prints the reformatted loop as context.
  • Audit a suppression. Load A formatter run and open Why. Every difference that was not reported is printed with the rule that explains it. Now untick expression-body and watch one of them become a change.
  • Try to sneak one past it. In any example, change a number, a name or a comparison on the right-hand side. Then reindent the whole file. The first is always reported and the second never is.
  • Move things. In When order matters, drag a method somewhere else in the class by cut and paste, then do the same to a field with an initializer.
  • Break it. Delete a closing brace. The report declines the file and says why, instead of guessing at a tree.

The demo is a re-creation written for this page, not the tool itself. Crux is C# on .NET and reads C# through Roslyn; none of that runs in a browser, and none of its source is here. What runs here is the same pipeline rebuilt in TypeScript: the parser is the TypeScript compiler, loaded in a worker, and the matching, the edit script, the attribution and the three formats were written fresh from the behaviour described above. So it illustrates the method and will not match the command's output line for line. The differences I know of: the real TypeScript backend normalizes whitespace only, so optional-braces and expression-body here are the two C# rules that carry over to TypeScript unchanged; this trivia also looks past semicolons and trailing commas; a hunk here prints the code a new construct wrapped as context, where the real one marks the whole region; the origin search for copied code looks inside the one file, because there is no repository behind the page; and under a copied addition the summary here lists what was changed in the copy, where the real summary names the origin and leaves the rest to the unified view. The sample code is invented, and files are limited to 3,000 lines.