Validating AST Structural Equivalence After Automated Refactoring

The hidden cost of a silent AST shift

A repository audit flags a dead import, an unused variable, or a duplicated helper. The next step is an automated refactor that rewrites the file. In many teams the refactor lands as a PR, is merged, and the audit record is closed. The failure shows up later: a unit test that used to pass now fails, a runtime edge case behaves differently, or a type‑checker flags an unexpected error. The root cause is a subtle change in the abstract syntax tree (AST) that the audit never saw. The audit reported a problem, the repair happened, but the structural equivalence of the program was never verified.

Why structural equivalence matters

An AST is the compiler’s view of the source. Two programs that look different in text can have identical ASTs, and therefore identical behaviour. Conversely, a change that appears innocuous—renaming a variable, moving a statement, or inlining a helper—can alter node ordering, scope bindings, or implicit type coercions. Those changes are invisible to a line‑based diff but can break semantics.

When refactoring tools apply transformations automatically, they rely on heuristics. Heuristics work for the common case but they do not guarantee that the resulting AST is isomorphic to the original with respect to the language’s operational semantics. Without a check, the audit‑to‑repair loop becomes a source of technical debt rather than a cure.

A concrete guard: run a structural‑equivalence harness before proposing a patch

1. Capture the pre‑refactor AST – Use the language’s parser to produce a canonical AST representation. Serialize it in a deterministic format (e.g. JSON with sorted keys).

1. Apply the automated transformation – Let the refactoring engine rewrite the source file.

1. Capture the post‑refactor AST – Parse the new source with the same parser and serialize it the same way.

1. Compare the two serialisations – A strict equality check guarantees that the transformation did not alter the tree structure. If the check fails, the harness reports INCONCLUSIVE or FAILED and the change is rejected.

The SHPBL live‑run harness (see the /harness page) implements exactly this pattern for several languages. It records a verdict of CERTIFIED when the ASTs match and the code still passes its test suite, PROVISIONAL when the match is perfect but correctness has not been asserted, and FAILED when the trees diverge. The harness is model‑independent; it does not rely on any AI model to decide equivalence.

Worked example in JavaScript

## Step 1 – original AST
npx @shpbl/sdk ast src/util.js > before.json

## Step 2 – run the automated refactor
npx refactor-tool src/util.js --inline-helpers

## Step 3 – new AST
npx @shpbl/sdk ast src/util.js > after.json

## Step 4 – structural check
diff -u before.json after.json && echo "AST unchanged"

If the diff reports any difference, the refactor is aborted. In practice the diff is usually empty for safe transformations like whitespace normalisation, but it catches edge cases such as accidental hoisting of a let declaration into a different block scope.

Limits you have to accept

Structural equivalence does not guarantee behavioural equivalence in all languages. JavaScript’s runtime can be affected by subtle differences in evaluation order that the AST does not capture. Likewise, code that relies on side‑effects in import statements may pass the AST check but still change behaviour after a rewrite. The harness can only flag structural mismatches; it cannot prove that two structurally identical trees are semantically identical.

The practical compromise is to pair the AST check with a lightweight test run. Running the full test suite is expensive, but a smoke test that exercises the public API of the changed module often catches the remaining behavioural drift. If the smoke test fails, the harness verdict becomes INCONCLUSIVE and the change is held for manual review.

Turning the insight into a Monday action

1. Add a step to your CI pipeline that runs the AST‑capture‑compare routine for every automated refactor job.
2. Configure the step to fail the job if the serialisations differ.
3. Pair the step with a minimal smoke test that imports the changed module and invokes its exported functions.

Doing this turns a silent failure mode into an explicit gate. The audit no longer ends in a dead‑end PR; it ends in a verified repair that preserves code health. Start with one high‑impact repository, run the free repository evaluation at /evaluation to see the current audit‑to‑repair gap, and iterate from there.