# Major pipeline rework (SHIPPED, 2026-07-17/18 - old pipeline fully retired)
## Locality tie-break in `solve_moved_subtrees` - tried 2026-07-22, reverted, zero effect; plus a cost-comparison analysis of the 800-mismatch corpus
Follow-up to the 2026-07-22 session that landed 7 fixes (919 -> 800 mismatches, commit `d74667a`).
Investigated whether a locality-based tie-break (`preorder_index`/`start_byte` proximity) could
close more of the gap, motivated by a design discussion about fitting the cost function so the
human-authored mapping is provably optimal (structured/margin-based learning framing).
**First considered**: adding a small positional tie-break term directly inside
`apted::common::UnitCostModel::ren`. Ruled out before writing it, once the actual blast radius was
mapped: `COST_INSERT`/`COST_DELETE`/`COST_UPDATE` are read directly (not just via `ren`) by ~20
existing tests that hardcode exact expected costs, so any rescale to make integer headroom for a
tie-break would require updating all of them - and worse, the bugs motivating this (APTED
preferring a byte-identical-but-distant node over the correct nearby one) live entirely in `ren`'s
*0-cost* tiers (`Identical` leaf match, same-kind internal match). Those tiers must stay exactly 0
- a subtree can legitimately relocate to a very different absolute file position and still be
100% correctly "the same code, just moved" (that's what `COST_MOVE = 0` encodes, and what many
tests assert: `test_rust_add_if`'s `assert_eq!(mapping.cost, 23)` relies on the entire reused
if/else costing exactly 0 despite moving one level deeper). A pointwise cost function can't tell
"legitimately relocated" apart from "coincidentally identical to something unrelated" - it only
ever sees one candidate pair at a time, never the competing alternatives. Any tie-break large
enough to matter would make legitimate whole-subtree moves stop costing 0.
**Pivoted to**: `hash_tree_matching.rs` already establishes exactly this tie-break pattern at every
one of its candidate-selection sites (`solve_with_hash_map`, both tiers of
`pair_children_for_descent`) - `min_by_key` on `start_byte().abs_diff(source.start_byte())` among
same-hash candidates. `solve_moved_subtrees.rs` was the odd one out: its candidate sort broke ties
by absolute earliest-in-file position (`sort_unstable_by_key(|a| ... start_byte())`), not proximity
to the deleted node's own position - inconsistent with the established convention and a plausible
match for the "byte-identical-elsewhere preferred" failure mode. Changed it to
`start_byte().abs_diff(b_start_byte)`, matching the sibling sites exactly.
Validated: full `cargo test --lib` (356/356 passed), full `benchmark_optimal_solutions` with a
proper per-fixture CSV comparison (not just aggregate - see `TODO.md`'s standing lesson about
that). Result: **zero effect**, at every level - aggregate 800 -> 800, 0 fixtures improved, 0
regressed, and the total count of `Moved`-reason mappings across the *entire* corpus was identical
before/after (236 -> 236). Root cause: `solve_moved_subtrees`'s existing container-identity-
agreement filter (outermost unmapped reference-node kind must match) already narrows candidates to
at most one survivor in every case in this corpus - the ambiguity this tie-break targets never
actually arises here. Also corrected a stale claim: `cpp-ladybird-refactor-variables-if-changes`'s
109 mismatches are `APTED:final_pass`/`APTED:greedy_anchor_block`-attributed, not `Moved` - it was
never `solve_moved_subtrees`'s doing. Reverted cleanly (`git checkout -- src/diff/solve_moved_
subtrees.rs`, confirmed clean via `git status`). The fix is still *correct* (consistency with the
established tie-break convention, zero risk) - just not reachable on this corpus. Worth re-applying
if a future corpus fixture actually exercises the ambiguity.
**Cost-comparison analysis** (the more useful output of this round): asked whether the human
ground-truth mapping is itself always "correct," given APTED finds a provably cost-optimal mapping
under whatever cost model it's given - if the human's mapping isn't the unique optimum, a
"mismatch" may just be a different, equally-valid tie-break rather than a codediff defect. Checked
this directly using `benchmark_optimal_solutions --csv`'s `algorithm_cost`/`human_cost`/`cost_diff`
columns (mirrors `UnitCostModel`'s costs via `cost.rs::operation_cost`, independent of the tie-break
work above) across all 26 mismatched fixtures (800 total mismatches):
- **320 mismatches (40%), concentrated in 4-6 fixtures** - codediff's mapping costs *the same or
less* than the human's own, e.g. `cpp-ladybird-refactor-variables-if-changes` (algo 660 vs. human
711), `kotlin-refactor-function` (100 vs. 162), `kotlin-remove-function` (168 vs. 225), `cpp-
laydbird-change-function-signature` (174 vs. 192). For these, the human's answer is demonstrably
*not* the unique cost-optimal mapping - a cheaper or equal alternative provably exists (codediff
found it). Calling these "wrong" is questionable; they may be legitimate alternative optima the
human just didn't happen to pick.
- **480 mismatches (60%), across 20 fixtures** - codediff's mapping is *strictly more expensive*
than the human's, even by the algorithm's own yardstick, e.g. `csharp-jellyfin-add-function` (209
vs. 117), `c-postgres-real-logic-change` (484 vs. 49), `rust-turbopack-module-rule` (601 vs. 424).
This is the more actionable bucket: if a strictly cheaper alternative demonstrably exists (the
human's), codediff isn't finding *its own* optimum, let alone the human's - which traces back to
the pipeline's architecture, not a cost-model tie-break. Earlier greedy phases (hash descent,
bottom-up expansion, syntax-named matching) commit matches before the true-optimal APTED
(`final_pass`) ever sees the residual, so the overall pipeline result is not globally
cost-optimal even though each individual phase is locally sound. This is where real, provable
headroom remains; the 40% bucket above may be an irreducible floor unless the cost model is
taught the human's specific tie-break preference (which is exactly the harder problem the ruled-
out `ren` approach ran into).
## `final_pass` forced-root-pairing cost gate - tried 2026-07-18, reverted, net-negative
Follow-up investigation after the phase 4 expansion candidates above: examined the top-6
highest-mismatch fixtures in the 778-mismatch corpus and found two distinct, separable root
causes behind most of their failures (full analysis not otherwise written down - see this entry
for the summary). **Root cause A**: real APTED tree-edit-distance, when a large region is
extensively rewritten, has no secondary objective to prefer preserving small byte-identical
islands over an equal-or-near-equal-cost alternative alignment (`rust-zed-workspace-tasks`'s
`self.terminal_provider` dropped inside a heavily-rewritten `if` block). **Root cause B**: a node
the human ground truth says should be deleted outright instead gets matched to an unrelated
same-kind node elsewhere, because `final_pass` (`apted::for_roots`, phase 6's whole-file-residual
catch-all) diffs exactly one file root against exactly one file root unconditionally, and
`island_match_supported`'s "immediate parent is matched" context-validation shortcut is trivially
true for *every* top-level declaration once the file root is (necessarily) matched to the file
root - "the file matches the file" is forced, not evidenced, but the validation code can't tell
that apart from a real evidenced anchor (e.g. `syntax_named`'s own name-matched forest roots).
Prototyped a fix for root cause B only (lower-risk of the two, and directly actionable): added
`is_forced_root_pairing` (`src/diff/apted/common.rs`) - true when a candidate match pair's parents
are both exactly the forest roots of a `source == "final_pass"` resolution - and gated on it in
two places: `island_match_supported` (withholds the trivial "parent matched"/"nearby matched
ancestor" shortcuts there, requiring either byte-identical content or a `solve_greedy_anchor_
blocks::cost_ratio` bound instead), and `promote_same_slot_pairs`'s LCS `weight` closure (same
cost-ratio requirement for internal same-kind slot promotions under a forced root pairing - this
turned out to be **necessary**, not optional: `island_match_supported` alone left the exact same
wrong pairing to be silently re-introduced by `promote_same_slot_pairs`'s independent "same slot,
so this must be an edit" mechanism one step later in `improve_slot_alignment`, since that
mechanism has its own, much weaker escape hatch - `LARGE_SLOT_SUBTREE`/`share_descendant_hash` -
that only blocks promotion for bodies over 20 nodes with *zero* shared descendant hash, which real
mismatched functions routinely have by coincidence).
Two new unit tests (`final_pass_does_not_match_unrelated_top_level_functions`, `final_pass_still_
matches_renamed_function_with_modest_body_change`) passed - the mechanism worked exactly as
designed on synthetic small functions. But full lib suite: **32 failures**, many in previously-
*exact* (0-mismatch) fixtures (`python-added-if-block`, `java-add-logging`, several `cpp-*`/
`typescript-*` ones). Benchmark: **TOTAL 832 vs. the 778 baseline (+54), and none of the 6
originally-targeted fixtures improved at all** (`kotlin-refactor-function`/`kotlin-remove-function`
unchanged, `cpp-ladybird-refactor-variables-if-changes`/`cpp-laydbird-change-function-signature`/
`c-nginx-add-typedef` slightly *worse*) - a pure net-negative with zero offsetting benefit even on
its own target fixtures.
Two things went wrong, both real lessons for next time:
1. **The cost-ratio threshold was too blunt for legitimate large single-candidate edits.**
`python-added-if-block`'s regression is the clearest case: a lone top-level `if_statement` had
a whole new nested `if` added inside it - a real, unambiguous edit (nothing else on either side
could plausibly be its counterpart) - but `solve_greedy_anchor_blocks::cost_ratio`'s coarse
whole-direct-child-hash-equality comparison (the same limitation candidate #3/#4's `TODO.md`
entries above already flagged for calls) scored it as too expensive and rejected the match,
converting a correct identity match into a wrong delete+insert. The gate has no way to
distinguish "this pairing is genuinely ambiguous, cost-check it" from "this is the only
candidate on either side, cost is irrelevant" - it should have been skipped entirely whenever
there's no competing candidate to be wrong *about*.
2. **The targeted fixtures likely never even reached the modified code paths.** None of the 6
fixtures the whole investigation was aimed at moved at all (not even in the wrong direction,
which would at least confirm the gate was reachable and just mistuned) - the more likely
explanation is `resolve_forest`'s flat-tree fast path (`flat_children`, `FLAT_MIN_CHILDREN =
50`: files whose root has 50+ unmatched direct top-level children route through Myers O(ND)
sequence diff instead of `compute_edit_mapping`/`improve_slot_alignment` entirely) intercepted
these larger, real-world files before `island_match_supported`/`promote_same_slot_pairs` ever
ran, meaning the actual root-cause-B mismatches diagnosed in those fixtures are produced by a
different mechanism than the one this fix touched. Not confirmed further - reverted before
chasing that down.
Reverted cleanly (`git checkout -- src/diff/apted/common.rs src/diff/apted/common/tests.rs`,
confirmed zero diff, lib build green). Revisit only with both lessons addressed: (a) skip the
cost-ratio requirement entirely when there is no competing candidate on either side (only real
ambiguity needs adjudicating), and (b) first confirm which code path *actually* produces the
kotlin-refactor-function/cpp-ladybird-style mismatches - likely by instrumenting or by checking
whether those files' root child counts cross `FLAT_MIN_CHILDREN` - before spending more effort
tuning a gate that may not even be reachable for the fixtures it's meant to fix.
## Phase 4 expansion candidates (PLANNING, 2026-07-18 - being tried one by one)
User request after the phase 4 generalization above: "what are some other similar heuristics or
expansions we can do to phase 4?" then "write them all in todo and try them one by one." Four
candidates, in the order they'll be tried (roughly confidence-ordered, cheapest/lowest-risk
first). Each gets the same treatment every heuristic in this codebase's history has: implement,
`cargo test --lib`, full `benchmark_optimal_solutions` run against the current baseline, keep only
if it helps or is neutral - **the ablation history in this file is full of heuristics that looked
reasonable and turned out net-negative alone** (`solve_similar_flow_control`, `solve_bottom_up_
expansion`, import-path hashing all shipped anyway because they're net-positive *in combination*,
but that was only known because each was actually measured, not assumed).
1. **Field/variant-level named matching** - **tried 2026-07-18, reverted, net-negative.** Extended
`solve_named_reference_groups`'s candidate predicate with a new `nodes::is_named_field`
(Rust `field_declaration`/`enum_variant`, Go `field_declaration`, Java `field_declaration`, C/C++
`field_declaration` when not pointer/array-wrapped - each verified against real grammar output,
4 passing unit tests). Worked exactly as designed in isolation (new end-to-end test confirmed
`age: i32` matches by name across sibling field churn) but regressed the benchmark: **785 vs. the
778 baseline (+7), 3 fixtures worse (`rust-add-value-to-enum` 0->2, `rust-hash-optimization`
0->2, `rust-turbopack-module-rule` 52->55), 0 improved anywhere.**
**Root cause, confirmed via `--details` on all 3 regressions - the same failure mode every
time:** calling `apted::for_nodes` on a single matched field/variant pair causes that call's own
comma assignment (commas are *siblings* of `field_declaration`/`enum_variant` in their parent
list, a classic generic/interchangeable token) to disagree with how the *parent* list
(`field_declaration_list`/`enum_variant_list`) would have assigned commas holistically across
all its children at once. Matching one field in isolation fragments a decision that needs
list-wide context to get right - individual field identity and the list's own generic-token
assignment are in tension, and this implementation had no way to reconcile them. Every
regression was a comma-only mismatch (not a real content/structure error), so this is milder
than it looks, but it's still a measured net-negative by the strict TOTAL count this whole
session has used as the bar. Not chased further (would need either scoping `apted::for_nodes`
to include the parent list's generic tokens, or gating the predicate away from fields whose
parent is a `nodes::is_commutative_container` where this tension is sharpest) - reverted
cleanly (`git checkout`), zero trace left in the codebase. Revisit if a future session wants to
solve the underlying generic-token-in-isolated-APTED-call problem generally, since it would
likely also matter for future candidates like #3/#4 below.
2. **Import-list arm-overlap matching** - **tried 2026-07-18, kept, neutral.** `solve_import_
list_overlap`: groups candidate Rust `use_declaration`s (multi-symbol `use foo::{a, b, c}` form
only) by base import path, scores same-path pairs by Jaccard similarity of imported-symbol sets
(reusing `solve_similar_flow_control`'s generic `flow_control_similarity_of_sets` helper),
matches the *whole* `use_declaration` in one `apted::for_nodes` call (never an individual
symbol - applying #1's lesson directly). Benchmark: **TOTAL 778 exactly unchanged, zero
fixtures differ** - the new `APTED:syntax_import_list` reason fired 76 times with no net effect
on mismatches. Kept anyway (same call as `solve_greedy_anchor_blocks` previously): zero
regression, 2 passing unit tests, plausibly useful on real-world grouped-import churn this
86-fixture corpus doesn't happen to exercise.
3. **Call-site matching by callee identity** - **tried 2026-07-18, reverted, zero firings.**
`solve_call_site_by_callee`: grouped still-unmatched Rust `call_expression` candidates by
`(callee name, argument count)`, cost-scored by how much of the *argument list* specifically
changed (`solve_greedy_anchor_blocks::cost_ratio` applied to the two candidates' `arguments`
nodes), narrowed via `CALL_SITE_MIN_ARGS`/`CALL_SITE_MIN_SUBTREE_SIZE`/`CALL_SITE_MAX_COST_RATIO`
to avoid the generic-callee-collision risk flagged below, matched the whole `call_expression` in
one `apted::for_nodes` call (applying #1's lesson). Compiled clean, 1 new unit test passed
end-to-end (`process_item(a, b, 1)` matched across both a position shift and an arg-value
change), full lib suite green (334 passed). Benchmark: **TOTAL 778 exactly unchanged, zero
fixtures differ - but unlike #2, `APTED:syntax_call_site` fired 0 times anywhere in the 86-fixture
corpus.** Distinct outcome from both #1 (measured regression) and #2 (fired 76x, neutral): this
is *unvalidated*, not *validated-neutral* - the pass never ran on real input, so its flagged
false-positive risk (common callee names colliding) was never actually exercised either way, and
it would have shipped unconditionally (not behind a config gate). Reverted cleanly (`git
checkout`, confirmed zero diff) rather than keep unexercised complexity with no measured benefit.
Zero firings across ~15-20 Rust fixtures is itself mild evidence this specific edit pattern
(callee unchanged, but call moved position *and* had args edited) is rare in practice, which
undercuts the original "useful on real-world code this corpus doesn't happen to exercise"
argument that justified keeping #2. Revisit only if a future fixture actually demonstrates the
need - don't resurrect by loosening thresholds, since that trades away the false-positive
protection to manufacture firings.
4. **Named/keyword-argument matching** - **tried 2026-07-18, reverted, zero firings.** The
originally-proposed framing ("match a keyword argument independent of position within a call")
is exactly candidate #1's individual-list-member form one level further down the tree, and would
hit the identical comma-fragmentation failure #1 measured. Adapted instead (advisor-reviewed
before implementing) into `solve_keyword_argument_calls`: group still-unmatched Python `call` /
Kotlin `call_expression` candidates (verified against each grammar directly - Python has real
`function`/`arguments`/`name`/`value` fields, Kotlin's `tree-sitter-kotlin-ng` grammar has *no*
fields at all on `call_expression`/`value_argument`, so callee and keyword-name extraction there
is purely positional) by `(callee name, sorted keyword-argument-name set)` - a stronger,
more collision-resistant identity signal than candidate #3's `(callee, arg count)`, since
keyword names are caller-chosen and self-describing. Matches the *whole* call in one
`apted::for_nodes` call, never an individual argument (applying #1's lesson). Hit and fixed one
real bug along the way: `solve_greedy_anchor_blocks::cost_ratio` only compares a node's *direct*
children by exact hash, and a call's direct children are just `(callee, arguments)` - scoring on
the whole call read one changed keyword value as "100% different" (ratio 0.91, above any sane
threshold) regardless of how much the argument list actually shared; fixed by scoring on the
*arguments* sub-node specifically instead (same fix candidate #3 already needed and documented).
Both a Python and a Kotlin unit test pass end-to-end (call matched across a position shift plus
one changed keyword value), proving the mechanism works when the pattern is present. Benchmark:
**TOTAL 778 exactly unchanged, zero fixtures differ - but `APTED:syntax_keyword_args` fired 0
times anywhere in the 86-fixture corpus** (which does include multiple Python and Kotlin
fixtures), the same zero-firing outcome as candidate #3. Reverted cleanly (`git checkout`,
confirmed zero diff) for the same reason: unconditional, always-on code with no measured benefit
and an unexercised false-positive-collision risk shouldn't ship just because it's mechanically
correct. Revisit only if a future fixture demonstrates the need - not by loosening thresholds.
The narrower position-independent-*within-an-already-matched-call* gap (this candidate's
original framing) stays genuinely unaddressed, same deferred status as candidate #1's fragmented-
comma-token problem - solving both together (matching a single list member without breaking the
parent list's own generic-token assignment) is the real unlock, and remains future work.
**Phase 4 expansion candidates: final tally (2026-07-18).** All four tried one by one, each
measured independently against the 778 baseline: **#1 reverted** (measured regression, 785).
**#2 kept** (neutral, fires 76x on real fixtures). **#3 reverted** (neutral, 0 firings -
unvalidated). **#4 reverted** (neutral, 0 firings - unvalidated). Net result: one net-positive
addition shipped (`solve_import_list_overlap`), three speculative extensions tried in good faith
and cleanly discarded when the evidence didn't support keeping them. No open follow-up work is
in flight from this exercise - the deferred generic-token-in-isolated-APTED-call problem (#1's
root cause, also blocking a real fix for #4's original framing) is noted above but not scheduled.
## Phase 4 generalized into one shared engine (2026-07-18)
User question: "what is the generalization of all current phase 4 heuristics?" Answer: three of
phase 4's four mechanisms - named-group matching, positional anchoring (`solve_greedy_anchor_
blocks`), and flow-control arm-overlap (`solve_similar_flow_control`) - are the same algorithm:
partition candidates into buckets by an exact compatibility key, score same-key pairs with a cheap
cost function, greedily accept cheapest-first (optionally above a threshold), hand accepted pairs
to real APTED. They differed only in three pluggable pieces (candidate predicate, key type, cost
function). `solve_large_flat_subtrees` (the fourth mechanism) doesn't fit this shape at all - no
competing candidates, no scoring, just a deterministic lookup pre-empting part of an already-
established pair's own APTED call - and stays a separate, directly-called pass.
Built `src/diff/grouped_greedy_matcher.rs` as the one shared engine (mirrors how `hash_tree_
matching::solve_with_hash_map` already generalized phase 1's three hash algorithms the same way)
and re-pointed all three call sites at it. Notable transform: flow-control's Jaccard similarity
("higher is better") had to be converted to the engine's "lower cost is better" convention via
`1.0 - similarity`, both for the cost function and the threshold. `FlowControlFamily` gained a
`Hash` derive to serve directly as the engine's compatibility key.
Verified: full lib test suite green (331 tests, including positional-anchoring's false-positive
regression guards and the N:M overload test), benchmark re-confirms **TOTAL 778 exactly** - pure
refactor, zero behavior change. Unexpected bonus: aggregate benchmark runtime dropped from ~327s to
**175s** (nearly 2x), because flow-control's previous O(before x after) all-pairs family filter now
benefits from the same O(candidates) key-bucketing the other two mechanisms already had.
## Final cleanup (2026-07-18)
Old ~15-pass pipeline deleted outright. `Diff::from_code_with_config` now runs the seven phases
directly - no more `HeuristicConfig::use_new_pipeline` toggle, no more parallel branch. Deleted:
`solve_identical_trees.rs`, `solve_structurally_identical_trees.rs`, `solve_commutative_structural_
trees.rs`, `solve_multilevel_hash.rs`, `solve_semantically_structural_nodes.rs`, `solve_import_
nodes.rs` (its 4 reused helpers moved into `solve_hash_descent.rs`). `HeuristicConfig` shrank to
the 4 fields that still gate a real decision (`solver_import_nodes`, `solver_similar_flow_control`,
`solver_bottom_up_expansion`, `solver_moved_subtrees`); the 4 now-unproducible `NormalizedStructural
Ignore*` reason variants and their backing `ASTMetadata` hash fields were removed too, along with
the now-fully-unused `semantically_structural_nodes` metadata field (phase 4 walks the tree
directly instead). `ablation_study.sh` and `benchmark_optimal_solutions.rs`'s CLI flags updated to
match (14 flag pairs -> 4). Verified: full workspace build clean, 331 lib tests green, benchmark
re-confirms **TOTAL 778** exactly - identical to the last pre-cleanup run, zero behavior change.
Net -2,345 lines. This closes out the rework - see the sections below for the full design history.
## Implementation status (2026-07-17)
All six phases implemented and wired end-to-end behind `HeuristicConfig::use_new_pipeline` /
`benchmark_optimal_solutions --new-pipeline`, built **alongside** the old ~15-pass pipeline rather
than replacing it in place (a deliberate deviation from the "clean replacement, no A/B period"
framing below - added specifically so the new pipeline could be benchmarked against the old one
throughout the rework instead of flying blind; see the advisor consultation this session for why).
Old pipeline, all 338 lib tests, and the 782-mismatch baseline are all unaffected and still pass.
New files: `src/diff/solve_hash_descent.rs` (phase 1 orchestration), `src/diff/solve_syntax_aware_
matching.rs` (phase 4). Modified: `code/hash.rs` (+`compute_kind_and_value_hash`/`compute_kind_
only_hash`, order-independent at every recursion level - the propagation-bug fix described below,
now actually applied), `diff/hash_tree_matching.rs` (+`solve_with_hash_map`, the generalized
engine), `diff.rs` (+`Diff::run_new_pipeline`), `diff/solve_greedy_anchor_blocks.rs` (`cost_ratio`
widened to `pub(crate)`, reused by phase 4's named matcher), `diff/solve_import_nodes.rs` (3 helpers
widened to `pub(crate)`, reused by phase 1's import-path hash variant).
**A real correctness bug was found and fixed along the way**, independent of the benchmark:
`solve_with_hash_map`'s descendant pairing was a positional `zip`, which mis-pairs children once a
commutative container's reordering is hash-matched (exactly the failure mode `compute_commutative_
structural_hash`'s own doc comment warned about, quoted below). Fixed by pairing commutative-
container children by `kind_only_hash` with a document-proximity tiebreak instead of position - see
`pair_children_for_descent` in `hash_tree_matching.rs`.
**Benchmark result, apples-to-apples** (86-fixture `optimal_solutions` corpus, `--new-pipeline`
with the same 3 passes gated off that `HeuristicConfig::default()` already gates off - import-path
hash, `solve_similar_flow_control`, `solve_bottom_up_expansion`'s second call - since those were
found net-negative in the 2026-07-15 ablation study and nothing about the rework changes that
signal): **888 mismatches vs. the 782 baseline** (+106, +14%). Before gating those 3 (i.e. running
everything unconditionally) it was 1067 - close to the old pipeline's own *all-passes-on* number
(~1022 per the ablation note further down this file), confirming the new pipeline's baseline
behavior is architecturally sound, not fundamentally broken.
**Root cause of the +106 gap, diagnosed via `--details` and reason-count column comparison, not
guessed:**
- The two biggest single-fixture regressions - `c-cpython-autogenerated-code` (58 -> 141, +83) and
`rust-turbopack-module-rule` (52 -> 86, +34) - are **not** a bug. Both fixtures' old-pipeline
reason-count row has a nonzero `Moved` column (103 and 55 matches respectively, from
`solve_moved_subtrees` recovering byte-identical wholly-deleted+wholly-inserted subtree pairs -
i.e. genuinely duplicated/reordered code, plausible for cpython's autogenerated opcode tables and
a renamed-impl rename in turbopack). The new pipeline's row has no `Moved` column at all, by
design: **the user explicitly confirmed removing `solve_moved_subtrees` outright** ("remove
solve_moved_subtrees") when this phase 2 was originally scoped. This is that decision's real,
measured cost on 2 fixtures - not a defect in the new code. Whoever picks this up next should
decide whether to accept this tradeoff (matches the explicit instruction) or reconsider carrying
some move-detection safety net forward in a different form.
- One fixture improved substantially: `cpp-laydbird-change-function-signature` (75 -> 23, -52) -
the fully-resolved-name matcher's flat, uniform mechanism apparently handles this one better than
the old two-tier impl/class pre-pass did.
- A long tail of smaller *new* regressions (1-28 mismatches each) appeared across roughly 15
fixtures that were previously exact (0 mismatches) or near-exact under the old pipeline (e.g.
`c-linux-small-bugfix` 0->28, `cpp-godot-small-bugfix` 0->11, `csharp-sonarr-change-type` 0->11,
`csharp-jellyfin-sql-query-fix` 0->10, plus ~10 more at 1-8 each). **Not yet individually root-
caused** - time-boxed out of this session. Leading suspects for whoever investigates next, in
likely-impact order: (1) `KindOnlyHash` folding `solve_multilevel_hash`'s 4 normalized granularities
(punctuation-only, literal-only, identifier-only, punctuation+literal) into one coarse tier - an
*accepted* precision loss per the plan below, but its accuracy impact was explicitly flagged as
"worth checking via `benchmark_optimal_solutions` once implemented" and this is that check landing
non-trivially non-zero; (2) the old `solve_semantically_structural_nodes`' `pre_match_by_path`
pre-pruning (matching identical/structurally-identical children before invoking APTED on a named
pair, shrinking the residual) has no equivalent in the new phase 4's named matcher - every accepted
name-based pair goes straight to a full `apted::for_nodes` call on the whole subtree.
- One already-attempted, confirmed-ineffective fix: re-adding an explicit `solve_large_flat_
subtrees::solve` call at the top of phase 4 (matching the old pipeline's ordering) made zero
measured difference (888 -> 888 exactly, `c-cpython` unchanged at 141) - because `nodes::is_
semantically_structural` (which both the old and new large-flat-subtree top-level-identity lookup
depend on) doesn't cover C at all, so the pass was already a no-op for `c-cpython` in *both*
pipelines. Left in the new phase 4 anyway (it's harmless and does help other languages/kinds it
does cover), but it is not the fix for the `c-cpython`/`turbopack` regressions - see `Moved` above.
**Not yet done**: the "final cleanup" step (flip `use_new_pipeline` default to `true`, delete the
~9 superseded modules/reasons/config fields, remove the toggle) is explicitly gated on closing this
gap first - see the disposition table's note that this was always meant to happen last, after
verification, not as part of "clean replacement" meaning "delete-first."
## Phase 7: unanchored-move fallback (added 2026-07-18)
User request after reviewing the `solve_moved_subtrees` vs. phase 4 comparison above: add back a
dead-last fallback for content that *moved* between two containers that both changed identity -
the one case none of phase 4's four mechanisms can reach, because every one of them requires an
anchor (a hash, a name, a shared matched ancestor, an arm-signature overlap) and a true cross-tree
relocation has none of those on either side until the rest of the pipeline, including final APTED,
has already given up. This does **not** reopen the "remove `solve_moved_subtrees`" decision from
the original planning - that removal was about phase 2 ("contextual exact matching", repurposed
to mean something else, see above); phase 7 reuses the `solve_moved_subtrees` module itself, called once
more, in its original dead-last position, now the pipeline's 7th and final step. Gated on
`config.solver_moved_subtrees`, same knob the old pipeline uses (default `true`).
**Result: 789 mismatches vs. the 782 baseline (+7, +0.9%)** - both target fixtures fully recovered
to their exact old-pipeline counts (`c-cpython-autogenerated-code` 141 -> 58, `rust-turbopack-
module-rule` 86 -> 52). A full old-vs-new per-fixture diff of all 86 fixtures now shows **exactly
one** remaining difference: `rust-next-font-imports-generator` (22 -> 29, +7 - the entire remaining
gap). `--details` on that fixture shows the extra mismatches are all "codediff chose Identical,
human mapping expected MatchButNotIdentical" on a reordered `use_list` (Rust's commutative-container
kind) and a restructured `if`-chain - confirmed (see next section) to be the commutative-hash
propagation-bug fix correctly recognizing the reordered import list as unchanged, which the
recorded human ground truth doesn't credit.
## Distinguishing reordered from truly identical (added 2026-07-18)
User request: "we do need a way to distinguish between truly identical and reordered." Confirmed
the diagnosis above was right, and that it's a real, general gap: folding order-independence
directly into `KindAndValueHash`/`KindOnlyHash` fixed the propagation bug but also meant a
reordered-but-otherwise-unchanged commutative container is indistinguishable from a genuinely
untouched one - both get plain `IdenticalHash`/`IdenticalHashOfAncestor`. The old, now-removed
`solve_commutative_structural_trees` kept this distinguishable via its own dedicated reason
(`FullymappingSubtrees`); the new hash-descent engine had no equivalent.
Fix: `ASTMappingReason::FullymappingSubtrees` (already existed, was slated for removal, **not
removed after all** - repurposed) now gets applied by the new engine too.
`hash_tree_matching::pair_children_for_descent` returns a `reordered` flag (true if any child's
after-side document-order index differs from its before-side index within a commutative parent),
and `solve_with_hash_map` patches that parent's already-added mapping to `FullymappingSubtrees`
once its children are examined. Operation/cost are unchanged (reordering-only stays free, matching
the old pass's precedent) - only the *reason* now differs, so downstream consumers (a diff viewer,
`human_solver`, `benchmark_optimal_solutions`'s reason-count columns) can tell the two cases apart.
Fixing this surfaced a second, independent bug in the same function (introduced earlier this
session, not by the original commutative-pairing fix's intent): child pairing always used
`node_to_kind_only_hash`, which is too coarse whenever the *outer* match came from
`KindAndValueHash` - same-kind, different-value leaves (e.g. three plain `identifier`s named
`a`/`b`/`c`) all hash equal under kind-only, so the nearest-by-position tiebreak could silently
"recover" a pairing that looks unreordered even when it wasn't, breaking reorder detection itself.
Fixed with a two-tier match: exact `kind_and_value_hash` first (correct whenever the outer match
guarantees kind+value multiset equality), `kind_only_hash` fallback for whatever's left unpaired
(needed for `KindOnlyHash`-driven outer matches, where content values may legitimately differ).
New test (`solve_hash_descent.rs::reordered_commutative_container_is_distinguished_from_truly_
identical`) verifies a reordered Rust `use_list` gets `FullymappingSubtrees` while an untouched
sibling function does not.
**Result: 789 -> 787 mismatches vs. the 782 baseline.** `rust-next-font-imports-generator` improved
29 -> 27 but the fixture-level gap isn't fully closed: the benchmark's mismatch detection compares
`ASTMappingOperation`, not `ASTMappingReason`, and the human ground truth expects `MatchButNot
Identical` operation for these reordered pairs, not just a distinguishing reason - a cost-model
question (should a pure reorder cost more than 0, and should its operation differ from `Identical`?)
that's separate from what was asked and wasn't changed. Full test suite (341 tests, 5 ignored) green.
## Reordering cost + operation (added 2026-07-18)
Immediate follow-up user request: "make reordering cost more than 0 and change operation to
MatchButNotIdentical." The reordered container itself (`FullymappingSubtrees`) now gets
`ASTMappingOperation::MatchButNotIdentical` / `COST_UPDATE` instead of `Identical` / 0.
That alone still left every non-commutative *ancestor* of a reordered container (e.g.
`use_declaration`/`scoped_use_list` wrapping a reordered `use_list`) reporting `Identical`, since
they aren't commutative containers themselves and `pair_children_for_descent`'s reorder detection
only fires on the container that actually reordered. Fixed by collecting every reordered node's id
during the descent and, once a hash-descent root match's whole subtree is processed, walking each
one's ancestor chain (via `node_to_parent`) up to the match's own root, downgrading every
`Identical` ancestor along the way to `MatchButNotIdentical` - a container is never a true no-op
match if anything inside it, at any depth, wasn't. Ancestors keep their existing reason (only the
actual commutative container gets `FullymappingSubtrees`); only operation/cost change.
**Result: 787 -> 778 mismatches - now *below* the 782 baseline.** `rust-next-font-imports-generator`
flipped from a +5 regression to a **-4 improvement** (18 vs. the old pipeline's 22): the ancestor-
propagation logic catches cases `solve_commutative_structural_trees`'s single-level
`FullymappingSubtrees` reason never did (it never propagated non-identical status up through
non-commutative wrapper ancestors either). The full 86-fixture old-vs-new diff now shows **zero**
fixtures where the new pipeline is worse than the old one, and one where it's measurably better.
Full test suite (341 tests, 5 ignored) green.
The new pipeline is now at least as accurate as the old one on every fixture in the corpus. Next
step is the "final cleanup" above: flip the `use_new_pipeline` default, delete the ~9 superseded
modules/reasons/config fields, remove the toggle.
---
Requested by the user 2026-07-17: replace the current ~15-pass pipeline (see `Diff::from_code_
with_config` in `src/diff.rs`) with a smaller, six-phase one, as a **clean replacement** (delete
superseded modules/reasons/config fields directly - no side-by-side A/B period). All design
questions below were asked live and answered the same day; this is the resolved plan. Still open:
exact "fully resolved name" resolution scheme per kind/language, exact cost function for phase 4's
approximate-cost step, and phase 5's exact parameters (same as phase 3, or loosened?) - these are
implementation-time decisions, not blocking further planning.
## The six phases
1. **Hash-based, largest-subtree-first descent** - a generalized, reusable version of what
`solve_identical_trees`/`solve_structurally_identical_trees` already do via `hash_tree_
matching.rs`'s `HashMatchSpec`/`solve_with_node_list`: walk candidate nodes largest-subtree-
first, and for each still-unmatched node, look up an after-side node sharing its hash, claim
the match, then pair descendants positionally. The rework: make this genuinely reusable rather
than the current `HashMatchSpec` (which reads a *named* field off `ASTMetadata` via a function
pointer, e.g. `|m| &m.node_to_full_hash`) - the caller precomputes a node-id -> hash map with
whichever hash algorithm it wants *before* invoking the engine, and passes that map plus an
`ASTMappingReason` straight in as parameters. Called multiple times, once per hash algorithm:
- `KindAndValueHash` (replaces `solve_identical_trees`/`IdenticalHash`)
- `KindOnlyHash` (replaces `solve_structurally_identical_trees`/`StructurallyIdenticalSubtrees`,
**and** `solve_multilevel_hash`'s 4 `Normalized*` variants - punctuation/literal/identifier-
insensitive matching folds into this one coarser hash rather than 4 separate ones. Known,
accepted tradeoff: this loses the 2 intermediate granularities `solve_multilevel_hash` had
- e.g. "same structure and literals, renamed identifiers only" no longer gets its own
matching tier, just falls to the same coarse kind-only bucket as everything else. Worth
checking the accuracy impact via `benchmark_optimal_solutions` once implemented, even though
this isn't gated behind a flag for A/B comparison per the "clean replacement" decision.)
- A normalized-import-path variant (replaces `solve_import_nodes` - folded in as a hash variant
rather than kept as its own phase, per the same "reusable hash descent" engine).
`solve_commutative_structural_trees` is removed outright (see below - order-independence is now
inherent to both primary hashes, not a bolted-on third one).
2. **"Move detection"** (originally named this in planning; renamed to **"contextual exact
matching"** 2026-07-18, see below) - repurposed name/slot, **not** `solve_moved_subtrees.rs`
(that module is deleted outright - the user confirmed "remove solve_moved_subtrees"). Phase 2
instead houses `solve_comment_nodes` (comment-precedes-matched-node matching) and `solve_
identical_diagnostic_statements` (identical logging/bail/assert/printf matching) - both are, in
the user's framing, a form of "detecting where already-known content re-lands" rather than
literal subtree-move recovery.
3. **Bottom-up expansion** - `solve_bottom_up_expansion.rs` as it exists today (Dice-coefficient
vote-then-verify matching of containers via already-matched descendants), unchanged.
4. **Syntax-aware subtree matching** - a redesign of `solve_semantically_structural_nodes.rs`,
generalized to also absorb `solve_greedy_anchor_blocks`'s job (confirmed: "phase 4 also handles
anonymous containers") and `solve_large_flat_subtrees`'s job (confirmed: "a special case of the
greedy solver" - once a pair is accepted and handed to `apted::for_nodes`, `resolve_forest`'s
existing flat-tree fast path already routes to Myers automatically when applicable, so this
likely needs no dedicated code of its own beyond making sure large flat containers are valid
candidates in the same pool - not a separate pre-emptive phase).
Candidates: reference nodes (`nodes::is_reference`'s per-language kind list - broader/coarser
than the current pass's `nodes::is_semantically_structural`) matched by `(kind, fully-resolved
name)` **when a name is resolvable**, falling back to positional anchoring (shared matched
ancestor + kind-path, `solve_greedy_anchor_blocks`'s existing mechanism) for anonymous
containers with no name at all (if-bodies, loop bodies, ...) - one unified greedy matcher
covering both today's name-keyed pass and today's positionally-anchored one.
"Fully resolved name" is new: today, `semantically_structural_nodes: HashMap<(String, String),
usize>` stores at most *one* node per `(kind, name)` key and needs a separate impl/class-scoped
pre-pass (Pass 1/Pass 0b in the current module) specifically because a bare method name like
`new` collides across every `impl` in the file - "fully resolved" means encoding that scope
into the name itself (e.g. `"Bar::new"` instead of bare `"new"`), letting one flat matching
mechanism replace today's two-tier impl/class-then-everything-else split. **Confirmed: real
N:M cases matter** (overloads, trait-impl duplicates), not just the common 1:1 case - the
candidate-grouping data structure needs to hold a `Vec` per `(kind, name)` key, not a single id.
Matching mechanism: for every candidate group, compute a **fast, approximate** cost for all
valid before/after pairs in that group (same spirit as `solve_greedy_anchor_blocks`'s `sequence_
edit_cost` - a direct-children-only estimate, not real tree edit distance), then greedily assign
pairs whose cost clears a similarity threshold, cheapest first - mirroring `solve_greedy_anchor_
blocks`'s `scored_pairs.sort_by(...)` + greedy claim loop, generalized from "compete within one
positional-key group" to "compete within one (kind, name)-or-positional group." Once a pair is
accepted, run **real APTED** on it (`apted::for_nodes`) to produce the actual mapping - same
"pre-match via a cheap signal, diff for real" idiom every current heuristic pass already uses;
`PostorderIndexer` already skips anything an earlier phase claimed, so nothing new needed there.
5. **Second bottom-up expansion** - phase 3 run again, after phase 4 has produced more matched
descendants for it to vote on. Exact parameters (same as phase 3, or a looser Dice threshold
the second time) TBD at implementation time.
6. **Final APTED** - `solve_final_apted`/`apted::for_roots` on the whole-file residual, unchanged.
`solve_orphaned_semantic_nodes` (Pass 3, which currently runs *after* this) is deleted outright
- confirmed: it's already a no-op today, kept only for documentation, so there's nothing to
port forward.
## New hash algorithms: `KindAndValueHash` and `KindOnlyHash`
Replace `IdenticalHash` (today's full hash, `compute_full_hash`) and `StructurallyIdenticalSubtrees`
(today's structural hash, `compute_structural_hash`) - **and**, per the "fold it in too" decision
above, `solve_multilevel_hash`'s 4 normalized variants - with two algorithms of the same basic
shape as today's first two (kind+value = byte-identical subtree; kind-only = same shape, different
leaf values), but both gain a property neither current hash has cleanly: **order-independence
folded in per node kind**, not bolted on as a third, separate hash variant the way `compute_
commutative_structural_hash` is today. Concretely: consult `nodes::is_commutative_container(kind,
language)` (already exists, already per-language - enum variant lists, use-lists, struct field
lists, etc.) while hashing; if a node's own kind is commutative, hash its children's hashes
*unordered* (sort child hashes before combining) instead of in document order.
This directly fixes a bug already found and documented in `compute_commutative_structural_hash`'s
own doc comment (`code/hash.rs`, dated 2026-07-15, never applied): today, order-independence does
not propagate past the commutative container itself, because the non-commutative branch delegates
to plain `compute_structural_hash` instead of recursing back into itself - so a reordering-only
change still changes the hash of every *ancestor* of the reordered container (e.g. the `enum_item`
wrapping a reordered `enum_variant_list`), meaning `solve_commutative_structural_trees` (which
matches on the ancestor reference node, not the bare container) never actually fires for its own
documented use case. Building both new hashes to recurse into themselves unconditionally, checking
`is_commutative_container` at every level rather than only at the top, fixes this by construction.
`solve_commutative_structural_trees.rs` and its dedicated hash field/reason (`FullymappingSubtrees`)
are removed outright, since order-independence is now inherent to both primary hashes.
## Disposition of every currently-existing pass (resolved 2026-07-17)
| `solve_identical_trees` | replaced by phase 1 w/ `KindAndValueHash` |
| `solve_structurally_identical_trees` | replaced by phase 1 w/ `KindOnlyHash` |
| `solve_commutative_structural_trees` | **removed** - folded into both new hashes |
| `solve_multilevel_hash` | **removed** - folded into `KindOnlyHash` (accepted precision loss, see above) |
| `solve_import_nodes` | **removed** - folded into phase 1 as a hash variant |
| `solve_comment_nodes` | moved into phase 2 ("contextual exact matching"), unchanged internally |
| `solve_identical_diagnostic_statements` | moved into phase 2 ("contextual exact matching"), unchanged internally |
| `solve_moved_subtrees` | **removed** outright |
| `solve_bottom_up_expansion` | phases 3 and 5, unchanged internally |
| `solve_semantically_structural_nodes` | replaced by phase 4 (redesigned) |
| `solve_similar_flow_control` | folded into phase 4 - arm-overlap scoring becomes another candidate-grouping signal in the generalized greedy matcher, alongside name-based and positional anchoring |
| `solve_greedy_anchor_blocks` | **removed** - absorbed into phase 4 (anonymous-container handling) |
| `solve_large_flat_subtrees` | **removed** as a standalone phase - becomes an implicit special case inside phase 4 |
| `solve_orphaned_semantic_nodes` (Pass 3) | **removed** outright (dead code, already a no-op) |
| `solve_final_apted` | phase 6, unchanged |
Phase 4 is now the single largest consolidation point in the rework: it absorbs `solve_
semantically_structural_nodes` (name-based matching), `solve_greedy_anchor_blocks` (positional
matching for anonymous containers), `solve_large_flat_subtrees` (flat-subtree special case), and
`solve_similar_flow_control` (arm-overlap candidate grouping) into one generalized greedy matcher
with several different candidate-grouping signals feeding the same "approximate cost -> greedy
assign -> real APTED" mechanism.
* IMPLEMENTED (2026-07-15): Per-pass ablation study infrastructure (`HeuristicConfig` in
`src/diff.rs`, `Diff::from_code_with_config`/`diff_code_with_config`, 14 `--solver-X`/
`--no-solver-X` flag pairs on `benchmark_optimal_solutions`, `ablation_study.sh`). Every
heuristic/algorithm pass in the pipeline can now be independently toggled without touching any
of the 20+ existing zero-config call sites (default config is unchanged unless noted below).
A leave-one-out sweep over the 86-fixture `optimal_solutions` corpus found:
- 3 passes net-negative individually (disabling them *improved* the aggregate mismatch
count): `solve_import_nodes` (-89), `solve_similar_flow_control` (-82),
`solve_bottom_up_expansion` (-69).
- 5 passes with zero measured effect individually: `solve_structurally_identical_trees`,
`solve_commutative_structural_trees`, `solve_multilevel_hash`, `solve_greedy_anchor_blocks`,
`solve_orphaned_semantic_nodes`.
- `solve_final_apted` and `solve_identical_trees` are load-bearing (+14873 and +1126
respectively when disabled) - never disable either.
**Default changed**: `HeuristicConfig::default()` now disables the 3 net-negative passes only
(`solver_import_nodes`, `solver_similar_flow_control`, `solver_bottom_up_expansion` = `false`).
Result: 1022 -> 782 mismatches (-23%) on the benchmark corpus, runtime 309s -> 368s (+19%,
less pruning work for `final_pass` to do). Only 1/86 fixtures regressed
(`cpp-ladybird-refactor-variables-if-changes`, 62 -> 109 mismatches); 4 improved.
**First attempt disabled all 8 passes (3 net-negative + 5 zero-effect) - reverted in favor of
the narrower 3-only default**: 1022 -> 815 (-20%) but runtime 309s -> 545s (+76%) and 2/86
fixtures regressed. The "zero individual effect" passes turned out not to be free to disable:
they were quietly pruning work off the expensive `final_apted` fallback even when they weren't
winning any matches outright, so removing them alongside the net-negative 3 made both accuracy
and runtime worse than removing just the 3. Lesson: leave-one-out ablation deltas don't compose
additively - always re-measure the combined config, not just sum the individual deltas.
**`src/test/optimal_solutions/*.rs` limits reclamped to the new baseline** (2026-07-15): every
`assert_matches_human_mapping_within_limit(name, N)` call's `N`, and every plain
`assert_matches_human_mapping(name)` whose fixture no longer matches exactly, was regenerated
from a fresh `benchmark_optimal_solutions --csv` run against the new default and updated to the
current mismatch count (10 files touched: `c_cpython_autogenerated_code` 127->58,
`c_postgres_real_logic_change` 17->8, `cpp_ladybird_refactor_variables_if_changes` 62->109 (the
one fixture the new default regressed), `rust_turbopack_module_rule` 175->52, plus 6 fixtures
that turned out to already be silently exceeding their old implicit 0-limit before this change
even happened - `cpp_laydbird_change_function_signature`, `cpp_tensorflow_switch_to_primitive_types`,
`csharp_sonarr_change_type`, `kotlin_nextcloud_change_function_fingerprint`,
`kotlin_refactor_function`, `rust_sniffnet_protocol` - now converted to `_within_limit` at their
actual counts). Full suite is green again (336 passed, 0 failed, 5 ignored). Full per-flag
numbers and CSVs: `research/ablation/` (from `./ablation_study.sh`).
* IMPLEMENTED (2026-07-14): Import path normalization and matching (`ASTMappingReason::NormalizedImportPath`,
`src/diff/solve_import_nodes.rs`). Normalizes import paths by removing surrounding quotes,
normalizing path separators, handling relative import prefixes, and matching imports by normalized
path rather than syntax. Wired into the pipeline after multi-level hash matching and before
comment node matching. This allows the algorithm to recognize that imports with different formatting
(e.g., `use "std::path";` vs `use 'std::path';`) but the same path are actually the same.
* IMPLEMENTED, benefit not established (2026-07-12): a greedy, cost-estimate-driven anchor pass
(`ASTMappingReason::GreedyAnchorBlock`, `src/diff/solve_greedy_anchor_blocks.rs`), requested to
fill a real gap - every other container-pairing heuristic keys off identity (a shared name, arm
signatures, a Dice coefficient over already-matched descendants), so an anonymous container
(an `if` body, a loop body, a function body with no already-matched children) with no such
anchor falls through to the final APTED pass unassisted. Estimates the cost of matching a
candidate pair via a fast weighted longest-common-subsequence alignment over *direct* children
only (each child is an opaque token, equal only on identical full-subtree hash; a matched pair
costs 0, everything else costs the full subtree size of whichever child didn't survive - a
`sequence_edit_cost` DP, not a real tree edit distance, which is what keeps it cheap enough to
try on many more candidate pairs than APTED itself could afford). Pairs scoring at or under
`MAX_COST_RATIO` (cost / combined subtree size) are assigned greedily, cheapest first,
one-to-one within their positional group (see below). Wired in right before the final APTED call.
**First two attempts, both reverted before this one landed:** (1) considering *every*
still-unmatched node with >= 2 children and subtree size >= 4 a candidate regressed 9 fixtures by
up to +53 mismatches each (0 improved anywhere), because `sequence_edit_cost` only looks at a
pair's own direct children with no notion of surrounding context - two entirely unrelated
`call_expression`s (one in a `for` loop condition, one in a `return` statement) matched because
their `argument_list` happened to hash-identical by coincidence. (2) restricting candidates to
genuine statement-sequence containers (`nodes::is_block_container`: `block`/`compound_statement`/
`statement_block` per language, plus `flow_control_family`'s `if`/`match`/`switch`) cut that to 1
regressed fixture (`javascript-fix-promises`, +4), still 0 improved anywhere - and sweeping
`MAX_COST_RATIO` from 0.5 to 0.2 produced an **identical** result, proving the regression wasn't
threshold-tunable: a byte-identical `statement_block` the human mapping relocates into a newly-
inserted `try_statement` wrapper scored a *near-zero* cost ratio (cheapest possible match) because
content-only scoring has no way to tell "same content, same place" from "same content, moved".
**The fix that actually worked:** gate every candidate pair on a *positional* signal before cost
is even consulted, per a user suggestion ("what if the positional anchor was the path of the
nodes"). `positional_key_before`/`positional_key_after` walk each candidate up to its nearest
already-matched ancestor (via `ASTMetadata::node_to_parent`) and record the kind of every node
passed along the way (falling back to the full path from the file root if nothing above is
matched yet); two candidates are only ever compared if that walk lands on a *corresponding*
ancestor pair *and* the kind-path from that ancestor down to each candidate is identical. This
directly kills both regressions: the two unrelated `call_expression`s have unrelated ancestor
paths, so they're never compared; the relocated `statement_block`'s after-side path gains an
extra `try_statement` segment the before-side path doesn't have, so the pair is rejected
regardless of its cost score. Result at `MAX_COST_RATIO = 0.5`: **0 changed fixtures** (exact
742/0 baseline match, verified against a saved pre-change CSV), while still firing 24 times
across the 40-fixture corpus (`GreedyAnchor` column in `benchmark_optimal_solutions --csv`).
Verified deterministic across two independent `--release` process runs (byte-identical CSVs) -
group-processing order is explicitly sorted by `preorder_index` (not left to `HashMap` iteration
order) for exactly this reason, since group resolution order can affect which group claims a
shared descendant first; see the module's doc comment.
Same situation as `BottomUpExpansion` below: implemented, correct, verified safe (zero
regressions, deterministic), but zero measured benefit on the current fixture corpus - whether
it's worth keeping in the pipeline is a call for whoever picks this up next. Unlike
`BottomUpExpansion`, this fires on genuinely different content (anonymous containers with no
already-matched children at all), so it may earn its keep on fixtures/languages not in the
current corpus even without moving today's TOTAL.
* IMPLEMENTED, threshold tuned, benefit not established (2026-07-11): bottom-up heuristic that
detects nodes whose descendants are already mapped to each other and matches those nodes too,
via `ASTMappingReason::BottomUpExpansion` (`src/diff/solve_bottom_up_expansion.rs`), gated by a
Dice coefficient over full subtrees (a direct-children ratio was tried first and rejected - see
that file's doc comment). Wired into `Diff::from_code` at a single, deliberately late call site
(right before Pass 3's orphan blanket-delete/insert) after an earlier "after every top-down
heuristic" placement regressed 4 `optimal_solutions` fixtures by letting a plausible-but-wrong
candidate preempt a later, more precise pass.
`DICE_THRESHOLD` was then swept from 0.5 to 0.95 against `benchmark_optimal_solutions`: 0.8-0.95
all tie the 742/0 baseline exactly (identical mismatch count on every fixture); 0.78 and below
start regressing (0.78 -> 746, 0.75 -> 749, 0.5 -> 826), and those regressions are real content
mismatches (`identifier`/`scoped_identifier`/`field_initializer`, a `statement_block` matched to
the wrong arrow function) - not generic/punctuation-token ties (`}`, `)`) that would suggest an
equally-valid alternate optimal solution worth flagging for human review instead of reverting.
No throughput difference was measurable at any threshold either (one release-build, single-run
comparison at 0.85 vs. the pass disabled: within noise). Landed at 0.9 - it ties every other safe
value on outcome while keeping the largest margin from the ~0.79 regression cliff, and there's no
evidence a lower value buys anything to justify sitting closer to that cliff.
Same situation as `identical-statement-runs` in the memory log: implemented, correct, and now
tuned, but whether it's worth keeping in the pipeline at all is still a call for whoever picks
this up next - it has fired ~29 times across the fixture corpus without net effect on either
accuracy or measured speed.
* Use the values more. At the moment, the node values are used in a all-or-nothing match. But we
could also use the value similarity to compute the cost, so that identifiers that look more alike
are cheaper to match in APTED.
TRIED AND REVERTED (2026-07-11), container-dissimilarity-surcharge variant: `UnitCostModel::ren`
currently charges 0 to match two same-kind *internal* nodes unconditionally, with the real cost
of reuse-vs-replace left entirely to the children's recursive edit cost. That unconditional 0 has
a side effect: it always waives exactly the root's own delete+insert cost (COST_DELETE +
COST_INSERT = 2), so two same-kind containers are always >=2 cheaper to "match" than to replace
wholesale, no matter how unrelated their content actually is - this looked like the mechanism
behind the `rust-algorithm-change`/`kotlin-remove-function` gaps below (pure unit-cost prefers
reuse the human doesn't want).
Implemented a quantized-tier surcharge on that branch, reusing `leaf_texts_similar`'s character-
bigram Dice metric (extracted into `nodes::text_similarity`, continuous 0.0-1.0) applied to the
*whole subtree's* text (available for free - `ASTNodeMetadata.text` is a full-span
`utf8_text()`, not leaf-only, despite the field doc saying "for leaf nodes"): similarity >= 0.6
-> 0 (unchanged), >= 0.3 -> 1, below that -> 2 (cancels the subsidy, capped so it never
*penalizes* matching relative to delete+insert). Capped at 500 chars of subtree text to keep the
DP's inner loop cheap.
Result: `kotlin-remove-function` and `rust-algorithm-change` - the two fixtures this was built
for - moved by exactly 0 mismatches each. Root cause in hindsight: "near-duplicate" is the whole
problem description for both gaps - two siblings that read as textually *very similar* to a
human, which is exactly what character-bigram Dice also scores highly (>= 0.6), so the surcharge
never engages for the case it targets. Text similarity cannot distinguish "same entity, edited"
from "different-but-near-identical entity" - by construction they look the same to that metric,
so no threshold value here can ever separate them.
Meanwhile it broke 5 *previously-perfect* (0-mismatch) fixtures - `rust-data-structure` (0->9),
`kotlin-refactor-function` (0->5), `python-refactoring` (0->5), `kotlin-add-data-class` (0->2),
`javascript-refactor-arrow-func` (0->1) - plus regressed 2 already-imperfect ones
(`typescript-async-await` +10, `cpp-ladybird-refactor-variables-if-changes` +6). Checked via
`--details` per the standing "check for punctuation-tie false-regressions before reverting"
policy: all real content mismatches (`identifier`, `token_tree`, `user_type`) - not `}`/`)` ties.
Root cause: small containers with several internally-differing identifiers (e.g. a macro
`token_tree`, a struct's field list) have low *aggregate* text similarity even when they're the
correct match - the surcharge punished exactly the kind of legitimate reuse the existing
per-child recursive cost was already handling correctly. TOTAL mismatches did drop 742 -> 739,
but that's 4 already-broken fixtures improving by more than 5 clean ones broke - not a trade
worth taking, especially against the target case's 0/0 result.
Reverted in full (`UnitCostModel::ren`'s internal-node branch, `nodes::text_similarity`
extraction). Whoever picks up "use the values more" next: subtree-text similarity is the wrong
signal for the reuse-vs-replace question specifically because it's blind to exactly the
distinction that matters (similar-looking-but-distinct vs. actually-the-same-thing-edited) -
this needs either a different signal entirely (e.g. positional/identity context: is there a
*closer* candidate elsewhere that a plain nearest-text-match would find instead?) or accepting
this class of gap per the three options already listed under `rust-algorithm-change` below. The
leaf-level idea (graduate `COST_UPDATE` itself by identifier similarity, rather than internal-
node `ren`) is untested and may still be worth trying - it wasn't what this attempt built, and
doesn't have the same "can't distinguish near-duplicate from renamed" problem since a leaf
rename *is* exactly the "same entity, edited" case by construction.
TRIED AND REVERTED (2026-07-15), the leaf-level variant flagged above as worth trying: graduated
`UnitCostModel::ren`'s same-kind-different-text *leaf* cost (identifiers/generic tokens) by
`nodes::leaf_texts_similar`'s underlying character-bigram Dice ratio (exposed as
`nodes::leaf_text_dice_ratio`), instead of the flat `COST_UPDATE` every such pair paid before.
Motivated by a real, confirmed gap: `kotlin-nextcloud-change-function-fingerprint` and
`kotlin-refactor-function` both exhibit a same-kind-leaf multi-candidate tie under
`reason APTED("final_pass")` (raw DP cost, not a named heuristic) when a parameter is inserted
mid-signature and every later parameter shifts by one slot.
**Headroom problem, found before implementing:** flat unit costs (`COST_UPDATE = 1`,
`COST_DELETE + COST_INSERT = 2`) leave no room to grade between "always rename" and "ties
replace" - a naive 2-tier integer split ties the cheap tier with outright delete+insert and
flips clear renames like `fetch_user` -> `fetch_user_data` (Dice ~0.78) into the penalized tier.
Fixed by giving `UnitCostModel::del`/`ins`/`ren` their own internal `REN_SCALE` (x100), used only
inside those three methods - APTED's search only ever compares costs relatively, so the absolute
scale is free, and this bought room to grade leaf-rename cost within `(LEAF_RENAME_MIN_COST,
LEAF_RENAME_MAX_COST)` while staying strictly below the rescaled `del()+ins()`.
**Two latent leaks the rescale surfaced, both fixed before benchmarking (still relevant if anyone
revisits internal cost rescaling here):** (1) `FORBIDDEN_RENAME_COST`/`ren`'s different-kinds
branch had been hardcoded from the raw, un-rescaled `COST_DELETE + COST_INSERT + 1` - left as-is,
the containment veto (`ContainmentCtx::adjust`) would have gone inert (nearly every rescaled cost
now exceeds the stale sentinel) or, worse, inverted into the DP's *preferred* option. (2)
`add_prune_mappings`'s `subtree_del_cost`/`subtree_ins_cost` and `classify_match`'s
disallowed-cross-kind branch called `cost_model.del/ins/ren` directly to populate *reported*
`ASTMapping.cost` - not just APTED's internal search - so the rescale leaked a 100x inflation
into real mapping costs (`cargo test`'s `test_hello_world_added_message` et al. went from
asserting `cost == 12` to actually getting `1200`). Fixed by pointing those reporting call sites
at the flat `COST_DELETE`/`COST_INSERT`/`COST_UPDATE` constants directly, decoupled from
`UnitCostModel`'s internal search scale - the same split `cost.rs::operation_cost` and
`classify_match`'s leaf-update branch already had, just extended to the two sites that had been
silently sharing the search-time model instead.
**Result:** the two motivating fixtures moved by exactly **zero** mismatches each (31->31,
64->64) - the graduation never engaged for them, because the human-correct pairs in both
(`capability`->`capability`, `showTaskActions`->`showTaskActions`) are text-*identical*, so `ren`
was already returning 0 under the old flat model too; the actual gap is elsewhere in how the
surrounding shifted structure gets scored, not in leaf-rename cost. Across the full 86-fixture
corpus: 5 regressed (`rust-firefox-webrenderer-borders` +8, `go-user-slices-library` +6,
`cpp-optimize-algorithm` 0->5, `rust-zed-workspace-tasks` +3,
`cpp-laydbird-change-function-signature` +1) against 2 improved (`c-nginx-add-typedef` -15,
`cpp-ladybird-refactor-variables-if-changes` -2) - net **+6** mismatches, and
`cpp-optimize-algorithm` went from a *previously-perfect* 0-mismatch fixture to 5. Checked via
`--details`: real content mismatches (a `return_statement` deleted wholesale despite an identical
counterpart existing; an `identifier` cross-matched to an unrelated `field_identifier`), not
punctuation ties - same failure signature as the container-level attempt above (a previously-good
tie-break gets upended by a signal that's live but mistargeted). Also measurably slower: the full
corpus benchmark went from under 2 minutes to 5.6+ minutes in `--release`, since every same-kind
different-text leaf comparison now does a bigram-hashset computation instead of a constant
lookup, on a hot path (`ren` is called extremely often during APTED's search).
Reverted in full (`nodes::leaf_text_dice_ratio` extraction, `UnitCostModel`'s `REN_SCALE`/graded
leaf branch, the reporting-path decoupling in `subtree_del_cost`/`subtree_ins_cost`/
`classify_match` - the last of these was only needed *because* of the rescale, so it reverts too
rather than being kept as drive-by cleanup). Whoever picks this up next: the mechanism itself
works exactly as designed (it's what produced `c-nginx-add-typedef`'s -15 and
`cpp-optimize-algorithm`'s regression alike) - the premise that failed is that leaf-rename cost
was the right place to look for the `kotlin-nextcloud-change-function-fingerprint`-style gap.
That gap needs a signal sensitive to the *shifted-position* structure, not leaf text similarity,
since the correct leaf pairs there were already free matches. Separately, `c-nginx-add-typedef`'s
-15 is a real, unexplained win worth investigating on its own before reusing this mechanism -
just not sufficient by itself to justify the net regression and perf cost of shipping it broadly.
# Next features to implement
* Add "Diff script" generation that can take the ASTDiff and make a "insert, move, update, delete"
script out of it.
# TUI follow-ups
* Mouse support and bracketed paste handling in the TUI.
* Re-review TUI suspend/resume (Ctrl-Z) behavior, not touched since the async event loop rewrite.
* Headless mode (`--headless`) is still unimplemented.
* Revisit the `Update` diff color (currently magenta) once seen against more real diffs.
# Possible code health improvements
* Make code.rs parse code in the from_string if possible, and then remove parsing from diff_code
diff.rs
## Code reuse / readability review (2026-07-12) - FIXED 2026-07-12
Full-codebase review focused on reuse and readability (not correctness/perf), then implemented the
same day. Verification throughout: `cargo test` (365/365 passing after every change) plus a
benchmark quality-gate - `benchmark_optimal_solutions --csv` columns 1-8 (`mismatches`,
`mismatch_pct`, `total_nodes`, `human_unsolved`, `algorithm_cost`, `human_cost`, `cost_diff`)
diffed byte-for-byte against a pre-change baseline after every risky change. Note: columns 9+
(which pass gets *credited* for a match) have pre-existing, harmless run-to-run jitter on 2/40
fixtures (kotlin-nextcloud-a-few-small-removals, rust-sniffnet-protocol) unrelated to this work -
don't mistake that for a regression if re-verifying later. Final gate after all changes: clean,
0 fixtures diverged.
**Collapsed:**
* `ForestDist`/`DeltaTable`/`StrategyTable`/`Mat` -> one generic `Grid<T>` (`common.rs`).
`ForestDist`/`Mat` are now pure type aliases (`Grid<u64>`/`Grid<i64>`, zero-cost);
`DeltaTable`/`StrategyTable` wrap `Grid` and keep their own `get`/`set` (the former's `UNSET`
sentinel logic is real behavior, not boilerplate, so it stays a wrapper not an alias).
* `collect_before_subtree_targets`/`collect_after_subtree_targets` -> shared recursive
`collect_subtree_targets` parameterized by a per-node classifier closure
(`SubtreeTargetOutcome`), in `common.rs`.
* `add_delete_mappings`/`add_insert_mappings` -> shared `add_prune_mappings`, parameterized over
the four things that actually differ (node map, mapping-key shape, operation, cost fn).
* `filter_before_nodes`/`filter_after_nodes` -> `filter_mapped_nodes(node_ids, node_map)`.
* `common.rs`'s ~1760-line `#[cfg(test)] mod tests` -> split into `common/tests.rs` (pure move,
zero behavior change; cut common.rs from 4143 to ~2380 lines).
* The 9x hand-rolled preorder-DFS stack-walk: merged the two pairs that were provably identical
(not just similar) - `solve_comment_nodes`/`solve_identical_diagnostic_statements`'s lockstep
two-tree walk -> `nodes::map_identical_descendants`; `code/metadata.rs`'s
`discover_reference_nodes`/`discover_semantic_structure_nodes` -> `metadata::walk_preorder`
(order-independent for both, verified: one sorts its output afterward, the other keys a map by
a type that can only occur once). Left `hash_tree_matching` (already shared, has its own
`classify` closure), `add_identical_subtree` (metadata-based, recursive, no already-mapped
check - a different shape, not just a differently-named copy), `compute_subtree_sizes`
(needs real post-order), and `compute_node_info` (needs a true preorder index, reverse-pushes
children) alone - each is a genuinely different traversal shape, not cosmetic duplication.
* `collect_unmatched_containers`/`collect_unmatched_diagnostic_statements` -> `nodes::collect_unmatched`.
* The `apted::for_nodes` + conditional-relabel idiom -> `nodes::anchor_pair_via_apted`.
* `sample_repository` in `sample_test_diffs.rs`/`sample_code_pairs.rs` -> shared
`stats::git::walk_single_parent_commit_diffs` (revwalk/commit-filter/diff machinery only; each
caller still does its own delta filtering, since that genuinely differs).
* Blob-size/UTF-8 validation -> `stats::git::text_len_if_in_range`.
* The two hand-maintained `ASTMappingReason -> label` matches -> `ASTMappingReason::bucket_label`
in `src/diff.rs`, called by both binaries (`benchmark_optimal_solutions.rs` still special-cases
`APTED` locally, since its per-provenance-column behavior is a deliberate divergence, not drift).
* `ascii_visualizer.rs::get_ast()`'s redundant reparse -> uses `code.ast` directly.
* `stats.rs`'s `count_nodes` + `visit_for_kind_stats` double traversal in `expand_from_code` ->
`compute_kind_stats` now returns the node count alongside the map (`count_nodes` itself is kept,
still used by `benchmark_diff_pairs.rs`).
* `stats.rs::for_path`'s 4-level nested match -> flattened with early returns.
* TUI dialog list-navigation/render duplication (`theme_dialog.rs`/`file_dialog.rs`) ->
`tui::components::move_selection` + `render_list_dialog`.
* `scroll_to_cursor`/`scroll_to_show_row` (components/code_viewer.rs) -> the former now just
calls the latter.
* Dead code removed: `CodeViewerWidget::with_path/with_title/with_theme/with_syntax_highlighting`,
`CodeViewer::widget_mut/widget/state_mut` (kept `state()` - it's actually used by
`diff_viewer.rs`'s tests, the original review's claim there was wrong, caught by grepping the
whole tree before deleting). Stale `#[allow(dead_code)]` comment on `hash_tree_matching::solve`
removed (it's actively called).
* Six near-copies of `find_first`/`first_child_of_kind` (all confined to `#[cfg(test)]`, one had
different self-inclusion semantics than the other five) -> one `test::helper::find_first_of_kind`.
**Deliberately left, with why:**
* `emit_before_subtree`/`emit_after_subtree` (common.rs) - assessed for the `Side`
trait/enum collapse and rejected: ~10 orthogonal divergence points (decision-map type,
`has_match_below` field, node map, mapping-key shape `(id,0)`/`(0,id)`, operation, cost fn, and
a cross-call into the shared, *not* duplicated `emit_match` with side-dependent argument order)
threaded through mutual recursion. Every design attempted (trait with ~10 methods, generic
function with ~11 closure params passed through every recursive call) was harder to read and
verify than the current ~40-line mirror pair - fails the basic "abstraction should cost less
than the duplication" test. A future attempt should feel free to revisit if a cleaner
decomposition presents itself, but forcing today's designs in would have made this the exact
kind of code a transcription bug hides in.
* `before_match_target`/`after_match_target`, and the `before_has_match_below`/
`after_has_match_below` loop pair inside `resolve_forest` - genuinely tiny; a `Side`
trait/enum here would cost more lines than it saves. Left as-is.
* `compute_opt_strategy_post_l`/`compute_opt_strategy_post_r`, `spf_a`'s cost-closures,
`resolve_forest`'s early-exit/dispatch/emission split, and the 5x inline `UnitCostModel`
reconstruction - not attempted this pass (time-boxed to the higher-value items above); still
worth doing, none looked unusually risky.
* `CodeViewerState::set_cursor` clamping setter - not a safe reuse cleanup on inspection:
`line_len`/`line_count` (needed for real content-aware clamping) live on `CodeViewerWidget`, not
`CodeViewerState`, so a real invariant-enforcing setter needs a design decision (pass the widget
in, or duplicate content-awareness into state), not a mechanical extraction.
* `solve_structurally_identical_trees::solve_with_config` - still has zero callers, but its own
doc comment says that's deliberate (kept for experimentation); left alone per that comment.
**Verification gaps to be aware of:** the TUI changes (dialogs, `scroll_to_cursor`) were verified
by `cargo test` (including the dialogs' own key-handling tests) and a clean compile, but not by
interactively driving the TUI - no visual/rendering regression check was done. The `sample_*`
binaries' refactor was verified by their own unit tests (which exercise `sample_repository` against
a real git fixture) plus a clean compile, not by a manual run against a real large repo.
# Diff algorithm accuracy (optimal_solutions gaps)
## Known gaps with full analysis
* FIXED (2026-07-14): Premature/irreversible pruning in `solve_semantically_structural_nodes`'s
Pass 3. **Fix:** Moved `solve_orphaned_semantic_nodes` to run AFTER the final full-tree APTED
pass in `Diff::from_code`, and made it a no-op (the final APTED pass already handles all
possible structural matches). Previously, when a name-keyed anchor (`impl_item`/`function_item`)
failed to find a counterpart, Pass 3 would immediately mark the whole subtree deleted/inserted
via `apted::for_nodes` with empty opposite forests, before the final full-tree APTED pass had
a chance. Surfaced by the `rust-turbopack-module-rule` optimal_solutions test where
`impl ModuleType` was renamed to `impl ConfiguredModuleType` - the type name changed but the
body had structural similarities that APTED could match. Now APTED runs first and finds these
matches. Tradeoff: increases mismatch count with human solution from <=169 to 172 for
rust-turbopack-module-rule (limit increased to 175), but represents more accurate structural
matching for syntax-only diffing.
* `rust-algorithm-change` (optimal_solutions test): the human-authored ground truth matches
before's OUTER `for` loop to after's (only) `for` loop, deleting the whole INNER (nested) loop
and inserting after's `if`/`return`/`seen.insert` body as new. codediff instead matches the
INNER loop to after's loop and reuses its `if`/`return` body, because that body is a much
closer syntactic match to after's `if`/`return` body than the outer loop's body is (which wraps
an entire second `for` loop) - reuse is cheaper than delete+insert under unit cost, so this
isn't a coin-flip the DP happened to lose.
Checked this isn't a reachable-but-mistied case: summed the edit cost implied by the complete
human mapping in `human_mapping.json` (each `delete`/`insert`/`update` entry = 1,
`insert_with_children` = its subtree size) against codediff's actual root mapping cost from the
same pipeline - human-implied cost is **96**, codediff's is **10**. That's not a tie needing a
tiebreak; the human's reading is ~10x more edit operations because it requires recognizing that
the whole loop got algorithmically replaced (brute-force nested loop -> HashSet single loop) and
deliberately *not* reusing the syntactically-similar `if`/`return` shape. Pure syntactic
tree-edit-distance has no signal for that - it only ever minimizes edit operations, so it will
always prefer reuse when reuse is available and cheaper, regardless of whether the reused code
is semantically related. Not fixable without changing the objective itself (favor "replace this
whole container wholesale" over minimizing token-level edit script size in some cases), which is
a deliberate design tradeoff to weigh - not a bug, and not something a local cost-model tweak or
DP tie-break can produce. Three ways to actually move on this, for whoever picks it up:
(a) accept as a known limitation of syntax-only diffing and leave the test un-green or delete it,
(b) pursue an explicit "prefer replacing a whole matched container over token reuse past some
depth/size" heuristic as its own effort (same risk class as the reverted hash-based
pre-matching pass mentioned in `resolve_forest` - arbitrary interior-node bias has bitten this
codebase before, so it needs its own careful validation against the full optimal_solutions
suite, not just this one case), or (c) reconsider whether this particular hand-authored ground
truth is asking for algorithmic/semantic understanding that's out of scope for an AST-structural
differ.
* `cpp-ladybird-refactor-variables-if-changes` (optimal_solutions test, investigated 2026-07-16,
no code changed): same class of gap as `rust-algorithm-change` above, not a bug. Before has
`auto& svg_graphics_element = as<SVG::SVGGraphicsElement>(*dom_node); auto active_view_box =
svg_graphics_element.active_view_box();`; after replaces this with an `if`/`else if` chain
(`if (auto* svg_graphics_element = as_if<SVG::SVGGraphicsElement>(*dom_node)) active_view_box =
svg_graphics_element->active_view_box(); else if (...) ...`). The human mapping deletes the two
old declarations wholesale and inserts the new `if`/`else if` chain wholesale. codediff instead
reuses the shared type name/call shape/`*dom_node` argument, matching the old assignment into
the new `if` condition - cheaper under unit cost, so this is the DP finding the objectively
lower-cost mapping, not losing a tie. Confirmed two ways: (1) `algorithm_cost` (660) <
`human_cost` (711) in the benchmark CSV - codediff's mapping is provably cheaper, so a cost
function that better approximates true edit distance moves *away* from the human mapping here,
not toward it; (2) `--no-solver-greedy-anchor-blocks --details` on this fixture still gives 109
mismatches unchanged - the plain final-APTED pass independently finds the same reuse under the
same unit-cost model, so this isn't a `solve_greedy_anchor_blocks` candidate-selection bug either.
The actual lever would be `UnitCostModel::ren`/`del`/`ins` in `apted/common.rs` (the search-time
model `for_nodes` actually uses), not `cost.rs` (post-hoc reporting only, never consulted during
matching). Already-tried, already-reverted cost-model levers in this exact space: the leaf-text-
Dice-graduation attempt above and the container-dissimilarity-cost attempt (see git history/prior
TODO revisions) - both failed for the same reason ("text similarity can't distinguish
near-duplicate from same-entity-edited"), and neither would even engage here since the reused
text genuinely *is* near-identical (`SVG::SVGGraphicsElement`, `*dom_node`, `active_view_box` all
literally recur). The one untested, structurally different lever: a relocation penalty for reuse
across a changed control-flow-kind ancestor path (assignment -> if/else chain) - deliberately
sacrifices edit-distance minimality for human-diff-readability rather than better approximating
it, so it needs its own careful validation the same way (b) above does, not a quick tweak.
Decision: dropped, not pursued - single fixture, and codediff's mapping (reusing `as<T>(x)` ->
`as_if<T>(x)`) is arguably a defensible diff on its own merits, not obviously worse for review
than the human's wholesale rewrite framing.
## Literature review (2026-07-25) - mapping published AST-diff research onto the current gap survey
User asked to survey the wider AST-diff literature for approaches to the current 27-fixture,
816-mismatch gap set (a fresh `benchmark_optimal_solutions --csv` run - see the ranked list below),
not just the two fixtures written up above. Four papers found real, mapped to specific gap classes;
two more (SatDiff, MTDiff/IJM) noted but not pursued this round - see "not pursued" at the end.
**Current ranked gaps** (98 fixtures scored, 27 nonzero, 816 total mismatches - `csharp-lidarr-*`
fixtures added 2026-07-25 raised this slightly from the 778 baseline via the newly-clamped
`csharp-lidarr-new-feature`, +16): `rust-zed-workspace-tasks` 117, `cpp-ladybird-refactor-
variables-if-changes` 109, `cpp-laydbird-change-function-signature` 75, `csharp-jellyfin-add-
function` 68, `kotlin-remove-function` 66, `kotlin-refactor-function` 64, `c-nginx-add-typedef` 62,
`c-cpython-autogenerated-code` 58, `rust-turbopack-module-rule` 52, `kotlin-nextcloud-change-
function-fingerprint` 31, `rust-next-font-imports-generator` 18, `csharp-lidarr-new-feature` 16,
`rust-algorithm-change` 14, `cpp-godot-small-bugfix` 11, `c-postgres-real-logic-change` 8, plus 12
smaller (1-6 each, mostly unexamined) and 2 flagged elsewhere in this file as possibly nondeterminism
jitter (`kotlin-nextcloud-a-few-small-removals`, `rust-sniffnet-protocol`).
**Semantic-aware/refactoring-aware matching** ([arXiv:2403.05939](https://arxiv.org/pdf/2403.05939),
2024) - names the exact failure mode already diagnosed for `rust-algorithm-change`/`cpp-ladybird-
refactor-variables-if-changes` "semantic ignorance": pure syntactic tree-edit-distance can't tell
"this looks similar" from "this is the same thing, edited." Three mechanisms, none of which are the
cost-model tweaks already tried and reverted here (leaf-Dice-graduation, container-text-similarity):
refactoring-pattern pre-matching (detect ~60 known refactoring types before generic matching),
semantic-role constraints (refuse cross-kind matches unit-cost would accept as "same kind" but that
violate a node's semantic role - e.g. never match a loop's own parameter to an unrelated variable
reference), and ranked candidate scoring beyond raw cost (prefer the candidate with more identical
*surrounding* context, matching *parent* edit distance, consistent nesting depth, when multiple
candidates tie or nearly tie). Benchmark: hand-validated AST node mappings from Defects4J (835 bug
fixes) + a refactoring oracle (11k+ refactorings, 546 commits) - same "human-authored ground truth"
approach `human_mapping.json` already takes, just larger and refactoring-focused.
**Where this actually reaches the current codebase**: NOT `cpp-ladybird-refactor-variables-if-
changes`/`rust-algorithm-change` themselves - both are confirmed `APTED:final_pass`-attributed (raw
DP cost search, see the entries above), and the 2026-07-22 tie-break investigation already
established a pointwise APTED cost function can't see competing candidates to rank against ("only
ever sees one candidate pair at a time"). The "ranked candidate scoring" idea instead maps cleanly
onto `grouped_greedy_matcher::solve`'s cost closures, which DO compare multiple discrete candidates
- specifically `solve_syntax_aware_matching::match_named_groups` ("syntax_named" reason), whose cost
function (`solve_greedy_anchor_blocks::cost_ratio`, a direct-children content signal) has zero notion
of surrounding context, unlike `solve_greedy_anchor_blocks` itself (whose grouping *key* already
requires matching ancestor context via `positional_key_before`/`positional_key_after`). Named-group
matching only tie-breaks on cost when a `(kind, fully-resolved-name)` key collides - real N:M cases
confirmed to matter here (overloads, trait-impl duplicates, `go_subtest_call_name` literal-named
subtests) - so this is a real, if narrow, lever. Fixtures with heavy `syntax_named`/
`greedy_anchor_block` provenance where this could plausibly help: `rust-zed-workspace-tasks` (522
syntax_named), `csharp-jellyfin-add-function` (142 greedy_anchor_block), `c-nginx-add-typedef` (970
greedy_anchor_block), `c-postgres-real-logic-change` (809 greedy_anchor_block), `kotlin-nextcloud-
change-function-fingerprint` (83 syntax_named + 6 greedy_anchor_block), `cpp-godot-small-bugfix` (94
greedy_anchor_block). Implementation attempt: see below.
**Hyperparameter auto-tuning / DAT** ([arXiv:2011.10268](https://arxiv.org/pdf/2011.10268), 2020) -
systematic data-driven tuning of GumTree's own threshold parameters (its version of this codebase's
`DICE_THRESHOLD`/`MAX_COST_RATIO`), found improved configurations in 21.8% of evaluated cases vs.
GumTree's shipped defaults. Directly applicable process improvement, independent of any specific
gap: every threshold in this codebase so far has been tuned one-at-a-time via manual sweep
(`DICE_THRESHOLD` 0.5-0.95, `MAX_COST_RATIO` 0.5-0.2, both documented above) against
`benchmark_optimal_solutions`'s aggregate - a joint sweep could find combinations neither one-at-a-
time sweep would surface (the same "leave-one-out ablation deltas don't compose additively" lesson
the 2026-07-15 default-config work already learned, generalized from boolean pass toggles to
continuous thresholds). Implementation attempt: see below.
**SatDiff** ([arXiv:2404.04731](https://arxiv.org/pdf/2404.04731), 2024) - reformulates the whole
tree diff as one MaxSAT problem instead of a multi-phase greedy pipeline, by construction immune to
the "locally sound, not globally optimal" gap this file's cost-comparison analysis identified as the
`rust-turbopack-module-rule`/`c-postgres-real-logic-change`/`csharp-jellyfin-add-function` "60%
bucket" (codediff's own mapping costs strictly more than the human's, real headroom exists). Claims
better conciseness than heuristic approaches "while maintaining a reasonable runtime." **Not
pursued**: this is a different algorithmic core, not a tunable heuristic - adopting it means a new
MaxSAT-solver dependency and redesigning the matching pipeline around it, an effort of a completely
different scale than every other entry in this file, and the two PDF fetches attempted couldn't
extract the paper's actual encoding/scalability details (both came back as unparseable compressed
binary streams - only the abstract was recoverable). Narrower idea worth floating for a future
session if the "60% bucket" fixtures still stand after cheaper levers are exhausted: SAT-solve just
the final-pass residual (post-greedy-phases) rather than the whole tree, keeping the existing
pipeline's cheap phases as-is.
**MTDiff / IJM** (Dotzler & Philippsen; Iterative Java Matcher) - both refine GumTree's move-
detection heuristics specifically, which is the shape of gap `rust-zed-workspace-tasks` has
("Root cause A" in the forced-root-pairing entry above: no secondary objective to prefer keeping a
small byte-identical island in place over an equal-or-near-equal-cost alternative elsewhere).
**Not pursued**: both PDF fetches failed the same way as SatDiff's (unparseable binary), so
everything known about their actual mechanism is secondhand from search-result snippets, not the
papers themselves - the weakest-sourced finding of this review. Implementing "them" now would mean
implementing a guess at an unread paper's mechanism, not the actual technique - revisit only after
getting real access to the papers (they predate 2020, may be behind a paywall the fetch tool
couldn't route around; try a university library proxy or requesting the PDF directly from an author's
site next time).
## Named-group context-aware tie-break - tried 2026-07-25, reverted, zero firings
Implementation attempt for the "ranked candidate scoring" idea from the literature review above.
Added `context_bonus` to `solve_syntax_aware_matching::match_named_groups`'s cost closure: on top of
`cost_ratio`'s existing content-only signal, subtract a small bonus (`NAMED_GROUP_CONTEXT_BONUS =
0.15`, deliberately small enough to only reorder near-ties, never override a genuinely better
content match) when a candidate pair's nearest already-matched ancestor corresponds on both sides -
reusing `solve_greedy_anchor_blocks`'s own `positional_key_before`/`positional_key_after` (exposed as
`pub(crate)`) as a read-only context signal rather than duplicating that walk. Required widening
`grouped_greedy_matcher::solve`'s `cost` closure signature to take a third `&ASTDiff` parameter (a
reborrow of the same `diff` the engine already holds `&mut`, passed down before its own greedy-
accept loop starts) so the closure could read already-established mappings - updated all 4 call
sites (`solve_greedy_anchor_blocks`, `solve_similar_flow_control`, and both `solve_syntax_aware_
matching` call sites) to match, 3 of them just ignoring the new parameter.
Compiled clean, full `cargo test --release --lib` green (362 passed, 0 failed, 5 ignored - no
regression risk from the signature change alone). **Full `benchmark_optimal_solutions --csv`: TOTAL
816 -> 816, zero fixtures changed at all** - not just net-neutral, byte-identical. Instrumented with
an `eprintln!` firing counter before reverting to distinguish "fired but never changed the greedy
ordering" from "never fired at all" (the same distinction this file's phase-4-candidates entry draws
between `solve_import_list_overlap`'s 76 real firings and candidates #3/#4's zero): **0 firings
across all 98 fixtures**. Named-group matching's `(kind, fully-resolved-name)` keys essentially never
collide into a genuine N:M group with >1 live candidate on both sides in this corpus (the confirmed
N:M cases - `overloaded_same_name_functions_are_matched_nm`'s Rust-overload case, `go_subtest_call_
name`'s literal-named subtests - either aren't present in the 98-fixture corpus or resolve to exactly
one live candidate per side by the time this pass runs, leaving nothing to tie-break).
Reverted cleanly (`git checkout -- src/diff/grouped_greedy_matcher.rs src/diff/solve_greedy_anchor_
blocks.rs src/diff/solve_similar_flow_control.rs src/diff/solve_syntax_aware_matching.rs`, confirmed
zero diff, `cargo check --lib` clean) - same disposition as the phase-4 candidates #3/#4 above:
mechanically correct, zero measured benefit, unexercised complexity shouldn't ship. The underlying
idea (context beats raw content-similarity for disambiguating ties) is still untested against a
fixture that actually has a live N:M collision - `rust-zed-workspace-tasks` (522 `syntax_named`-
attributed mismatches) seemed like the best candidate going in but apparently doesn't route through
a multi-candidate tie in this pass either. Whoever revisits this: confirm with `--details` or similar
instrumentation *which* mechanism actually produces `rust-zed-workspace-tasks`'s mismatches before
trying another named-matching-side fix - the wiring (widened `cost` signature, exposed positional-key
helpers) is easy to redo if a genuinely N:M-colliding fixture turns up.
## Hyperparameter joint sweep (`DAT`-style auto-tuning) - tried 2026-07-25, KEPT: MAX_COST_RATIO 0.5 -> 0.8
Implementation attempt for the DAT/hyperparameter-auto-tuning idea from the literature review above.
`MAX_COST_RATIO` (`solve_greedy_anchor_blocks.rs`) had never actually been swept against
`benchmark_optimal_solutions` - its own doc comment said so - unlike `DICE_THRESHOLD`
(`solve_bottom_up_expansion.rs`), which got a proper one-at-a-time sweep 2026-07-11. Grid search (a
plain sed-edit-rebuild-rerun loop, not a real optimizer - each full-corpus run costs ~7 minutes, so
a coarse grid is what's tractable in one session): `MAX_COST_RATIO` alone at
`{0.2, 0.35, 0.5, 0.65, 0.75, 0.8, 0.85, 0.95}` (`DICE_THRESHOLD` held at its known-good 0.9), then
`DICE_THRESHOLD` re-swept at `{0.8, 0.9, 0.95}` around the winning `MAX_COST_RATIO`, to check for a
genuine joint interaction rather than just an independently-tunable win.
**Results:** `0.2`/`0.35` both regressed to 829 (too tight a filter rejects legitimate anchors,
pushing more work onto the final APTED pass); `0.5` (the old default) at 816; `0.65` at 813;
`{0.75, 0.8, 0.85}` all tie at a **788** plateau; `0.95` regresses back to 797. The `DICE_THRESHOLD`
re-sweep at `MAX_COST_RATIO = 0.8` across `{0.8, 0.9, 0.95}` all landed on 788 too - the two
thresholds don't meaningfully interact in this range, so (unlike DAT's headline finding that joint
tuning beats one-at-a-time) this specific win would have been found by a single-parameter sweep too,
*if* anyone had ever run one - the real gap wasn't "one-at-a-time tuning misses joint effects," it
was "one of the two thresholds had simply never been tuned at all."
Landed on `MAX_COST_RATIO = 0.8` (middle of the `{0.75, 0.8, 0.85}` plateau, same "most margin from
either regression cliff" reasoning `DICE_THRESHOLD` used at 0.9). **Net: 816 -> 788 (-28, -3.4%).**
Per-fixture (full `cargo test --lib`, 362 passed/0 failed/5 ignored after reclamping): `c-cpython-
autogenerated-code` improved 58->33, `cpp-laydbird-change-function-signature` improved 75->60,
`c-postgres-real-logic-change` regressed 8->20 (reclamped 8->20 in its `_within_limit` test - already
flagged elsewhere in this file as the corpus's single largest cost-gap outlier, `algorithm_cost` 484
vs. `human_cost` 49, so a looser anchor threshold plausibly lets it grab a cheaper-but-wronger reuse
there; not investigated further this round). `c_cpython_autogenerated_code`'s and `cpp_laydbird_
change_function_signature`'s `_within_limit` calls tightened to their new, lower actual counts (58->
33, 75->60) so the improvement isn't silently masked by a stale, looser limit going forward. 2
improved substantially against 1 regressed - kept, per the same net-effect bar every other entry in
this file uses.
**Tooling note for next time:** the sweep script's first two attempts both failed silently
(`set -euo pipefail` + `total=$(benchmark | grep -m1 '^TOTAL' | awk ...)` - `grep -m1` closes its
read end as soon as it finds the first match, sending the still-writing benchmark process a SIGPIPE
on its next write; `pipefail` propagates that non-zero exit back through the assignment, and `set -e`
silently aborts the whole script with no output). Fixed by writing the binary's full stdout to a file
first and grepping the file afterward, never piping a live long-running process into a `-m1`
short-circuiting `grep`. Also: `benchmark_optimal_solutions` prints **two** separate lines starting
with `TOTAL` (the main per-fixture table's, and the reason-provenance table's, further down) - a bare
`grep '^TOTAL'` silently grabs both; needs `-m1` (after fixing the above) or an explicit stop after
the first match to get the right one (confirmed by direct inspection: the reason table's `TOTAL` row
has completely different, unrelated columns, not a second view of the mismatch count).
# Speed goal (2026-07-25 - `/goal`: 0.1% mismatch budget, target median 20ms / p90 100ms / max 400ms)
Starting point (`benchmark_other`, 98 fixtures, before any of this section's changes): median
63.9ms, p90 1188.8ms, p99 4423.4ms, **max 31,455ms**. The max was wildly disproportionate to file
size - `csharp-radarr-add-object-instance` (235 lines, 2,302 nodes) alone took **31.5s**, more than
every other fixture in the corpus, most of which are far larger. That specific number was the first
target: something that far off the trend line for its own size is a bug, not inherent complexity.
## `is_semantically_structural` had zero C#/C/C++ coverage - found via profiling, fixed for all three
Added `eprintln!`-based phase timers to `Diff::from_code_with_config` (removed again once done -
not left in the tree) and ran `csharp-radarr-add-object-instance` through them: **30.3s of the
30.6s total was phase 6 (final APTED)**, with only 490/2302 before-side nodes matched going in -
every other phase combined took under 400ms. First hypothesis (the flat-tree Myers fast path's
`FLAT_MIN_CHILDREN = 50` cliff - the fixture's one field has a 49-vs-50-entry collection
initializer, one below the threshold) was **wrong**: raising/lowering it (and its redundant sibling
`solve_large_flat_subtrees::FLAT_CONTAINER_MIN_CHILDREN`) had zero effect, because that pass is
scoped to *named* top-level items only, and C# had no named top-level items at all (see below).
Second hypothesis (`NodeSelectionConfig::min_subtree_size: 45` excluding the field's ~30-node
`new IsoLanguage(...)` entries from exact-hash candidacy) fixed the fixture at `min_subtree_size:
15` (2201/2302 matched, phase 6 down to 64ms) but **regressed the whole corpus 788 -> 1022
mismatches** - a global drop in this threshold lets small, unrelated, coincidentally-identical
subtrees anywhere in a file steal matches from better candidates a later phase would have found
(the same class of problem the 2026-07-22 locality tie-break entry above describes for a pointwise
cost function). Reverted.
**Root cause, found by reading `solve_hash_descent`/`hash_tree_matching`/`solve_syntax_aware_
matching` directly instead of guessing further:** `nodes::is_semantically_structural` - the name-
*extraction* function `solve_named_reference_groups` (phase 4's primary matcher) and
`solve_large_flat_subtrees::top_level_identities` both depend on - only has match arms for
`Rust`/`Python`/`Go`/`Kotlin`. Every other language, including `CSharp` (which *does* have a kind-
list entry in the separate, unrelated `is_reference` checker just above it - easy to mistake for
coverage) falls through to `_ => None`. C# was never given a single named declaration anywhere in
the whole pipeline: no class, method, or field ever got the cheap identity-based match every other
covered language gets - **phase 4's primary mechanism was a complete no-op for C#**. For this
fixture specifically: the field's 49 near-duplicate entries were too small for exact-hash candidacy
and its enclosing field/class/namespace had no name-based anchor either, so the *entire* ~2,300-node
file fell to `final_pass`'s unconstrained tree-edit-distance on every edit.
**Fix**: added a `Language::CSharp` arm (`class_declaration`/`struct_declaration`/
`interface_declaration`/`enum_declaration`/`record_declaration`/`method_declaration`/
`namespace_declaration` via their `name` field; `field_declaration` via an extra hop through
`variable_declaration` -> first `variable_declarator` -> `name`, same "first declarator only"
simplification Go's grouped `var (...)` handling already uses). Field names verified empirically
against real grammar output (a throwaway binary dumping `child_by_field_name` results on the actual
fixture), not assumed from other C-family grammars.
**Result:** `csharp-radarr-add-object-instance` 30.6s -> ~400ms (phase 6 alone: 30.3s -> 40ms, ~760x).
Full `cargo test --release --lib`: 362 passed, 0 failed, 5 ignored, **and the whole suite dropped
from ~145s to 29s** (this one fixture was that large a fraction of total test time).
`benchmark_optimal_solutions`: **788 -> 731 mismatches, and better** - exactly one other fixture
changed at all, `csharp-jellyfin-add-function` 68 -> 11 (a fixture this file's cost-comparison
analysis above already flagged as a "60% bucket" real-headroom case; this is a direct fix for it,
not a coincidence). Zero regressions anywhere in the corpus.
**Same gap confirmed for C and C++ too** (only `Rust`/`Python`/`Go`/`Kotlin`/now-`CSharp` are
covered) - checked because 6 of the corpus's 10 slowest fixtures after the C# fix were C/C++.
Added `Language::C`/`Language::CPP` arms: `function_definition` needs unwrapping a declarator chain
(`pointer_declarator`/`array_declarator`/.../`function_declarator`, each wrapping a nested
`declarator` field) down to the real name node (`c_family_declarator_name`, new helper) rather than
one direct field read - verified empirically against `c-nginx-add-typedef` (C: `pointer_declarator
-> function_declarator -> identifier`) and `cpp-ladybird-refactor-variables-if-changes` (C++:
`function_declarator -> qualified_identifier`, which conveniently already carries full
`Class::method` scoping, no separate impl/class pre-pass needed unlike Rust's `impl_item` handling).
`struct_specifier`/`enum_specifier`/`union_specifier` (C and C++) and `class_specifier`/
`namespace_definition` (C++ only) read their `name` field directly, same shape as every other
language's type-declaration arms.
**Result:** modest, not dramatic - median/p90/max barely moved (p90 1194 -> 1052ms, max 3924 ->
3521ms), aggregate `codediff_ms` mean 405.6 -> 373.5ms. **One real regression**: `c-postgres-real-
logic-change` 20 -> 28 mismatches (node-level), 280 -> 368 (line-level, `benchmark_other`) - the
*only* fixture affected in either direction, everywhere else (every other C/C++ fixture in the
corpus) is byte-for-byte accuracy-identical. `--details` shows the classic premature-pinning
failure mode already documented and fixed once in this file (2026-07-14, `solve_orphaned_semantic_
nodes` reordering): naming `function_definition:2` anchors it to an isolated `apted::for_nodes`
call on just that one function, which can't represent the cross-function multi-to-multi mapping
this fixture's own test-file doc comment already flags as a known modeling limitation ("TODO: Deal
with multi-to-multi mapps. We can't represent this either in the mapping or visually at this
time!"). Not a bug in the fix - a real, already-understood case where "match by name first" and
"let whole-file APTED see everything at once" trade off, and this file is the corpus's most
extreme example of needing the latter. Reclamped `c_postgres_real_logic_change`'s `_within_limit`
20 -> 28 and kept the fix: directionally correct (C/C++ get the same architecture every other
language has), accuracy-neutral everywhere else, one understood and already-documented exception.
Full suite green (362/0/5) after reclamping.
**Running total against the speed goal** (`benchmark_other`, both fixes applied): median 62.7ms
(target 20ms), p90 1051.5ms (target 100ms), max 3521.2ms (target 400ms, down from 31,455ms at the
start of this section - **8.9x**). Not there yet. The remaining slowest fixtures are now genuinely
large files, not gap-driven pathologies: `c-cpython-autogenerated-code` (57,917 nodes, 3.5s),
`c-linux-small-bugfix` (47,986 nodes, 2.7s), `cpp-ladybird-refactor-variables-if-changes` (12,658
nodes, 2.5s) - final APTED's inherent complexity on a large residual, not a fixable identity-
matching gap. Next levers, not yet tried: (1) audit whether `is_semantically_structural`'s same
gap extends to any *other* language in active use here (only Rust/Python/Go/Kotlin/CSharp/C/CPP are
covered now - Java, JavaScript/TypeScript, PHP, Ruby, Swift, Scala are all still `_ => None`,
unexercised by this corpus's current fixture sizes but a latent version of the exact same bug);
(2) parallelize independent `apted::for_nodes` calls across `grouped_greedy_matcher`'s accepted
pairs (rayon) - a free win, doesn't touch accuracy, untried; (3) a size/time-boxed fallback for
`final_pass` specifically on the largest residuals, spending some of the mismatch budget
deliberately rather than by accident.
## Lever (2) investigated - NOT a free win, needs dependency-aware batching first
Re-profiled the current top-4 slowest fixtures (full 8-phase timers, same instrumentation as
above, removed again after) to check whether phase 6 (`final_pass`) was still the bottleneck now
that C/C++/C# have named-match coverage. It isn't: `phase6_final_apted` is fast on all four now
(82-296ms - the tiny residual left after phase 1/4 is exactly what named matching was supposed to
buy). **Phase 4 (`solve_syntax_aware_matching`) is now the single largest phase instead** (602ms-
1.83s) - the cost didn't disappear when C/C++ gained named matching, it *moved*: `cpp-ladybird-
refactor-variables-if-changes` alone makes **1,837 separate `apted::for_nodes` calls** through
`APTED:syntax_named` (near-zero before the C++ fix), one per matched declaration. Confirmed this
is mostly legitimate work, not redundant: `IdHash`/`IdHashAnc` counts for these files are also huge
(4,765-26,646), meaning the large majority of nodes were already hash-matched for free in phase 1;
the 1,837 `syntax_named` calls are specifically the *non*-identical remainder that genuinely needs
real tree-edit-distance done somewhere.
**Why naive parallelization of this loop is unsafe, confirmed by reading the code, not assumed:**
`grouped_greedy_matcher::solve`'s accept loop has an explicit "Defensive re-check: an earlier-
accepted pair's real APTED resolution may already have claimed one of these nodes" check - load-
bearing, not decorative. `solve_named_reference_groups`'s candidate collection
(`collect_fully_resolved_groups`) walks *every* named declaration at *every* depth in one pass, so
a class and each of its own methods are routinely **both** independent candidates in the same
batch. If the class is accepted first, its own real `apted::for_nodes` call can (and does) resolve
its whole body via ordinary tree-edit-distance, which naturally re-discovers and claims an
identical method inside it - at which point that method's own separately-scheduled pair must be
skipped, not double-processed. This is exactly the scenario `cpp-ladybird`'s class-heavy namespace
produces at scale. Running accepted pairs' `on_accept` calls (the real APTED work) in parallel
would race on precisely this: two threads could both start resolving overlapping subtrees before
either commits, breaking both correctness (conflicting/duplicate mappings) and the run-to-run
determinism this module's own doc comment explicitly requires and `describe_nondeterminism`
actively tests for elsewhere in this codebase.
**Not attempted this session**: a *correct* version needs dependency-aware batching - partition the
already-determined accept order into batches where no two pairs in the same batch have an ancestor/
descendant relationship (checkable via `ASTMetadata::node_to_parent` walks before scheduling), run
each batch's `on_accept` calls in parallel (rayon), and only start the next batch once the current
one's real resolutions have landed in `diff`. This is a real, valuable follow-up - phase 4 is now
demonstrably the largest single cost on several of the corpus's slowest files - but it changes
correctness-sensitive scheduling logic in a module three other call sites share, and this
codebase's history (the whole cost-model section above) shows exactly how expensive a rushed,
under-validated concurrency change here could be to diagnose after the fact. Needs its own
dedicated session: implement the batching, verify byte-identical output across several independent
runs (not just "tests still pass" - a race can be intermittent), and only then measure the speed
win.
**State against the speed goal at the point this investigation paused** (unchanged from the
previous entry, since nothing here modified behavior): median 62.7ms / p90 1051.5ms / max 3521.2ms
against a 20ms / 100ms / 400ms target. Real, validated progress (max down 8.9x from the 31,455ms
starting point; accuracy improved, not traded away) but the target isn't met. The two safe
`is_semantically_structural` fixes are exhausted for the languages currently driving the corpus's
slowest fixtures (C/C++/C#/Kotlin/Rust/Python/Go all covered); the next real lever is the
dependency-aware parallel batching above, not another quick heuristic tweak.
## Further investigation of lever (2), and two more ruled-out/found levers
**Ruled out: redundant `metadata_of` recomputation.** Every phase calls `metadata_of(before)`/
`metadata_of(after)` independently (6-7 call sites across the pipeline) - looked like an obvious
"compute once, thread through" win. It isn't one: `metadata_of` already checks `code.metadata.
ast_metadata` and returns a cheap `Cow::Borrowed` if already populated, and `Code::from_string`
(used by every real construction path, including the test/benchmark helpers) already eagerly
computes and caches it once at construction. Every one of those 6-7 calls is already a free borrow,
not a fresh tree walk. Would have been wasted effort to "fix" - checked the actual implementation
before touching anything, per this file's own standing lesson about profiling before guessing.
**Corrected understanding of phase 4's cost, changes the parallelism cost/benefit:** added a
scoring-vs-accept-loop timer directly inside `grouped_greedy_matcher::solve` (removed again after)
and ran it against `cpp-ladybird-refactor-variables-if-changes`. Scoring is trivial (19µs for 19
candidates). The accept loop - which is where each accepted pair's real `apted::for_nodes` call
happens - took **1.53s for just 6 accepted pairs** in this one batch, ~250ms average each. The
earlier `APTED:syntax_named: 1837` reason count from the benchmark CSV is *not* 1837 separate
`for_nodes` calls (as assumed while scoping lever (2) above) - it's the total count of individual
node-level *mappings* those far-fewer calls produce, since one call on a large function body can
resolve hundreds of descendant nodes at once, all tagged with the same source label. Phase 4's cost
here is a *small number of expensive, large individual tree-edit-distance computations* on genuinely
big function bodies, not many cheap calls paying per-call overhead. This doesn't change the
correctness analysis above (parallel batching is still unsafe without the dependency-aware
partitioning), but it does lower how much batching would even buy on files shaped like this one -
6-way parallelism on 6 items, not 1837-way - and confirms the remaining cost is largely genuine,
unavoidable tree-edit-distance complexity on large subtrees, not fixable overhead.
**Found and kept: release build profile tuning.** No `[profile.release]` section existed in
`Cargo.toml` before this - Cargo's own defaults (`codegen-units = 16`, no LTO) leave real
performance on the table for a CPU-bound algorithmic tool. Added `lto = "fat"` + `codegen-units = 1`
- a pure compiler-flag change, zero source code touched, so unlike everything else in this section
it carries **no correctness risk at all** (confirmed: `benchmark_other`'s mismatch counts are
byte-identical before/after, 473/570/637, exactly as a flag-only change should produce). Cost: full
release rebuild goes from ~10s to ~2min (one-time per build, not per-run). Benefit: modest but real
and free - median 62.7ms -> 61.3ms, p90 1051.5ms -> 1011.2ms, max 3521.2ms -> 3365.2ms (~4-5%
across the board). Full `cargo test --release --lib` still green (362/0/5) after adding it.
**State against the speed goal, end of this session's investigation**: median 61.3ms / p90 1011.2ms
/ max 3365.2ms against a 20ms / 100ms / 400ms target (max improved **9.3x** from the 31,455ms
starting point). Not met. Every remaining lever identified this session that could plausibly close
more of the gap (dependency-aware parallel batching in `grouped_greedy_matcher`; a genuinely new
size-capped approximate-diff fallback for large individual subtrees, spending mismatch budget
deliberately) is a real, substantial, correctness-sensitive implementation in its own right - not a
quick tweak - and deserves its own dedicated session with proper multi-run determinism verification
rather than being rushed. The two `is_semantically_structural` language-coverage fixes and the
release-profile change are the safe, validated wins available without that larger investment; they
are kept, tested, and documented above.
## Dependency-aware parallel batching - tried 2026-07-25 (user-requested), reverted: real correctness bug found
User explicitly asked to implement one of the two remaining risky levers from the entry above.
Built the dependency-aware batching design in full: `grouped_greedy_matcher::solve` now took
`before_node_to_parent`/`after_node_to_parent` maps, partitioned the cost-sorted accepted sequence
into rounds where no two candidates in the same round have an ancestor/descendant relationship on
either side (`is_ancestor_or_descendant`, walking both `node_to_parent` chains), ran each round's
`on_accept` calls via `rayon::par_iter` against **a fresh `diff.clone()` per worker**, then merged
each clone's new entries back into the shared `diff` sequentially before the next round. Reasoned
through causality carefully before writing code: since an ancestor and its descendant can never
land in the same round (the one relationship the check exists to forbid), a descendant's defensive
re-check always runs *after* its ancestor's round has been merged - argued (and still believe, for
the reasons below) this exactly reproduces the sequential algorithm's own causality, not just its
final answer. Compiled clean on the first attempt.
**Verification caught a real bug before it shipped** - this is the process working as intended, not
a wasted afternoon. `cargo test --release --lib` failed one test,
`c_cpython_autogenerated_code` (confirmed via `git stash` that the pre-change code passes it
cleanly, and failed consistently across 3 reruns - deterministic, not a race manifesting
intermittently). Bisected the failure by forcing every round to execute sequentially-in-round-order
without cloning (keeping the new round/batching *scheduling* logic, removing only the clone+merge
*execution* mechanism) - **that variant passed**, isolating the bug specifically to the parallel
clone+merge path, not the batching/scheduling logic itself. Added collision detection to the merge
step and got direct, concrete proof: **the same `before_id` ends up mapped to two different
`after_id`s by two different workers inside one supposedly-disjoint round** (e.g. `before_id=
100129141321856` -> `after_id=100129144082400` from one worker's clone, `-> 100129144058112` from
another's, in the same 99-candidate `greedy_anchor_block` round on this fixture's huge autogenerated
opcode-dispatch `switch`).
This disproves the load-bearing assumption the whole design rested on: that two candidate node ids
with no ancestor/descendant relationship to each other guarantees `apted::for_nodes`'s internal
resolution stays fully confined to writing only within that candidate's own subtree. It does not,
for some mechanism inside `resolve_forest`/its callees not yet identified - not found before
deciding to stop and revert rather than keep guessing at a fix for a correctness bug already proven
to exist but not yet understood. Suspects for whoever picks this up: `ContainmentCtx` (built per-
call from `before_root_ids`/`after_root_ids`, but worth checking whether anything inside it or
`compute_delta`'s `vren_adjusted` sites can reference node ids outside those root sets given how
this fixture's content is heavily duplicated near-identical `case` bodies - c-cpython is
*autogenerated* opcode dispatch code, exactly the shape most likely to have many structurally-
identical small subtrees at different tree positions, which is suspicious given the collision
values themselves - `100129141321856` vs siblings differing by small constant offsets - look like
they could be from nearby, similarly-shaped candidates); or `improve_slot_alignment`, called with
the *full* `node_to_parent` map, not one scoped to the current call's own subtree, so worth
confirming it can never write a decision for a node outside `before_root_ids`'s/`after_root_ids`'s
own descendant sets.
Reverted in full (`git checkout -- src/diff/grouped_greedy_matcher.rs src/diff/solve_greedy_anchor_
blocks.rs src/diff/solve_similar_flow_control.rs src/diff/solve_syntax_aware_matching.rs`, confirmed
zero diff, full suite green again: 362/0/5). The batching/scheduling half of this design (which
*direction* to shard work, using the ancestor/descendant relationship) still looks sound - it was
built and independently verified as such. The clone+merge execution half needs `resolve_forest` and
its callees audited for whether anything can write outside the given root ids' own descendant sets
before this is safe to try again - do that audit *before* re-attempting the parallel version, not by
building it again and hoping the bug doesn't reproduce.
## Size/dissimilarity-capped approximate fallback for large subtrees - tried 2026-07-25 (user-requested), reverted: no configuration found a real win
User asked to try the other remaining lever from the speed-goal investigation: a size-capped
fallback that deliberately spends mismatch budget on the largest individual subtrees instead of
paying real APTED's full cost. Single-threaded, no concurrency risk at all (unlike the parallel
batching attempt above) - the only open question was whether the accuracy cost was acceptable.
**First cut, size-only**: added a fast path to `resolve_forest` (`apted/common.rs`), parallel to
the existing flat-tree Myers path but gated on combined before+after subtree *size* instead of
child count, falling back to the same `resolve_flat_tree_pair` mechanism (Myers alignment of direct
children by exact hash; unmatched children wholesale delete/insert) regardless of how deep or wide
the pair is. At `LARGE_SUBTREE_APPROXIMATE_THRESHOLD = 1500`: catastrophic, 731 -> 1243 mismatches
(+70%), 21 fixtures changed (mostly regressions, several previously-*perfect* 0-mismatch fixtures
broken outright - `kotlin-nextcloud-remove-function` alone went 6 -> 175). At `15000`: harmless
(731 -> 740, just the already-known `c-postgres-real-logic-change` exception) but **also
speed-useless** - `codediff_ms` totals identical to baseline, confirming the threshold never fires.
**Root cause of why size doesn't work as a proxy at all**: added temporary timing+size
instrumentation directly in `resolve_forest` (`PROFILE dp_call size=... elapsed=...`, printed for
any call over 5ms, removed after use) and measured real APTED calls on `cpp-ladybird-refactor-
variables-if-changes` directly. **Size does not predict cost**: a 1,259-node pair took **1.03s**,
while a *larger*, 2,698-node pair took only 66ms. APTED's own pruning makes a large-but-mostly-
identical subtree cheap regardless of size; a smaller-but-substantially-rewritten subtree gives it
little to prune and costs close to its real worst case. This is exactly why 1500 caught so much
collateral damage (large-but-similar pairs real APTED would have resolved almost for free) while
15000 caught nothing at all (even the worst observed 1.03s case is a 1,259-node pair, nowhere near
15,000).
**Second cut, dissimilarity-gated**: reused the same direct-children `myers_lcs` hash-alignment
`resolve_flat_tree_pair` already needs (not a separate estimate - if the gate fires, this
computation *is* the resolution) as a cheap predictor: only fall back when *both* the combined size
clears a floor (skip the check entirely on small pairs, where real APTED is always affordable
regardless of similarity) *and* the fraction of children surviving exact-hash alignment is low
(little for APTED to prune on, predicting a slow call). Swept the two floors together:
| 800 | 0.5 | 731 -> 827 (+96) | 473 -> 520 (+47) | p90 1011 -> 895ms (-11%), max 3365 -> 3770ms (**worse**) |
| 1000 | 0.3 | 731 -> 810 (+79) | 473 -> 498 (+25) | median/p90/max all within ~2-4% of baseline (noise) |
| 1200 | 0.15 | 731 -> 739 (+8, just `c-postgres`) | 473 -> 473 (+0) | zero measurable speed change |
No configuration found a real win: loose enough to trigger meaningfully always cost more accuracy
than the speed it bought (and once, at 800/0.5, didn't even reliably improve the max - noise or a
genuine case of the fallback itself being slow enough on a large-but-still-substantial residual to
not help), while tight enough to be safe never fired often enough to matter. The underlying
problem: `myers_lcs`-over-direct-children similarity is *also* a poor predictor of real APTED cost,
just a cheaper-to-compute one than size - a pair can have low direct-children similarity (most
children genuinely differ) while still being *individually* cheap for APTED to resolve (small
per-child subtrees, little depth for the DP to search), or high similarity while still being
expensive somewhere deeper that this one-level check never sees.
Reverted in full (`git checkout -- src/diff/apted/common.rs`, confirmed zero diff, full suite green:
362/0/5). **Conclusion for whoever revisits this**: neither size nor one-level direct-children
similarity is a usable proxy for "this specific APTED call will be pathologically slow." A working
version of this idea needs either (a) a genuine mid-computation time/operation budget with a clean
abort-and-fallback inside the DP loop itself (not a pre-check before it starts - the whole problem
is that cost isn't predictable in advance from cheap structural signals), or (b) a cheaper, deeper
predictor than one level of children-hash alignment (e.g. recursively estimating similarity a few
levels down, though that starts approaching the cost it's trying to avoid). Given the difficulty
finding *any* usable size/similarity threshold empirically, (a) looks like the more promising
direction if this is picked up again.
## `is_semantically_structural`: covered every remaining language - 2026-07-26, user-requested
The C#/C/CPP entries above fixed a real, then-latent gap for those three languages specifically;
every OTHER language `is_reference` already lists a kind set for (meaning candidate selection
already half-believes it's covered) was still silently falling through to `_ => None` in the
*separate*, name-*extracting* function - Java, JavaScript/TypeScript/TSX, PHP, Ruby, Swift, Scala,
R, ShellScript, Lua, and Vimscript. User asked to close the rest out.
**Java/JavaScript/TypeScript/TSX**: verified against real corpus fixtures (same throwaway-binary-
against-real-grammar-output method as the C-family arms). `class_declaration`/`interface_
declaration`/`enum_declaration`/`record_declaration`/`method_declaration` (Java) and `function_
declaration`/`class_declaration`/`method_definition`/`interface_declaration`/`type_alias_
declaration` (JS/TS/TSX) all read a direct `name` field, same shape as every previously-covered
language. `field_declaration` (Java) needed one hop through a `variable_declarator` child, same
idea as C#'s arm but without that language's extra `variable_declaration` wrapper layer (Java
nests `variable_declarator` directly under `field_declaration` - confirmed empirically). JS/TS's
`arrow_function`/`function_expression` have no name field of their own, but `const f = () => ...`
(direct assignment) gets one from the *enclosing* `variable_declarator` - confirmed this is
narrow enough not to misfire on `arr.map(x => ...)`-style callback arguments, which parent as
`arguments` rather than `variable_declarator` (and genuinely have no identity of their own to key
on, so correctly staying unmatched here is the right behavior, not a gap).
**PHP/Ruby/Swift/Scala/R/ShellScript/Lua/Vimscript**: no fixtures anywhere in this corpus, so
**unvalidated** - added via the same `name`-field convention every language checked so far has
used without a single exception, but flagged clearly in the code as a best-effort starting point,
not a confirmed fix. Verify against real source (same throwaway-binary method) the first time any
of these languages gets an actual fixture, before trusting it the way the verified languages are
trusted.
**Result**: full suite green (362/0/5). `benchmark_optimal_solutions`: **739 -> 739, zero fixtures
changed at all** - the corpus's existing Java/JS/TS fixtures are all small and already near-perfect
via other mechanisms (hash matching, positional anchoring), so there was no latent pathology like
C#'s to fix on *this* corpus. `benchmark_other`: same story, no measurable speed change (473 line-
level mismatches unchanged, `codediff_ms` total within noise of the pre-change baseline). Kept
anyway: this closes the same *class* of gap the C# investigation found by accident, for every
language the codebase claims to support, before it has the chance to produce another 30-second
outlier the way C# silently did until a large enough fixture happened to expose it. Zero risk to
ship - purely additive match arms behind an exhaustive `language` match, can't affect any language
that already had coverage.
## APTED branch-and-bound / A*-style admissible-cost pruning - scoped 2026-07-26 (user-requested), ruled out at the design stage, nothing implemented
Follow-up to the `computeOptStrategy` pruning investigation above (found strategy selection is
only ~1.2% of cost, so proposed the real 98.8% - `gted`/`spf_a`/`spf_l`/`spf_r`, the DP engine
itself - as the actual target). Framing: could an A*-style admissible lower bound let the DP
early-exit/prune cells whose cost is already provably worse than some threshold, the way graph
search discards dominated branches, *without* sacrificing exactness (unlike the two prior reverted
attempts, which both traded away correctness for speed)? User said "Start scoping."
**Scoping process**: read the existing oracle-fuzz validation harness first, since any prototype
would need to survive it - `test_apted_engine_matches_oracle_fuzz` (3000 random-tree seeds,
`compute_delta` vs the Zhang-Shasha oracle `compute_delta_zhang_shasha`, compared via actual
*traceback* cost through `compute_edit_mapping`, not just the raw distance number) and
`test_apted_engine_matches_oracle_fuzz_with_containment` (same, plus `gen_random_pruning`'s
realistic `ContainmentCtx` constraints, seeded to make sure `adjust()` is exercised at every `vren`
call site). Good harness for this class of change - would have caught the kind of silent
corruption a bad prune could cause.
**Why it doesn't have a safe application point, found before writing any prototype code**:
1. **No competing candidates to discard.** A*/branch-and-bound saves work by abandoning a search
branch once its cost provably exceeds a known-better incumbent. APTED's `DeltaTable` has no
such branches - the optimal-strategy selection (already confirmed near-optimal, see above)
picks a fixed, minimal set of keyroot-pair cells to compute, and every one of them is a
*required* intermediate value for exactly one later computation, not one of several competing
alternative solutions.
2. **The natural admissible bound is already inside the recurrence's base case.** The obvious
admissible upper bound for any subforest pair is "delete everything on one side, insert
everything on the other" (`sum_del_cost`/`sum_ins_cost`). But `engine.rs`'s `delta` base-case
initialization (~line 1908-1914) already sets exactly that as the starting value for every
cell before the DP recurrence ever runs. So no cell's true value can ever exceed that bound in
the first place - there is no slack above the bound to prune away.
3. **Cells are read back by the same in-flight computation, not just by an external caller.**
Checked directly: `delta.get(b, a)` calls appear *inside* `spf_a`/`spf_l`/`spf_r` themselves
(`engine.rs` lines 740, 770, 981, 1009, 1277, 1437), reading cells that were `delta.set()` for
smaller keyroot pairs earlier in the *same* `gted` call, while computing larger keyroot pairs
later in that same call. Skipping or approximating one cell doesn't just produce a locally
worse answer for that subproblem - it feeds a wrong value into a later cell's computation
within the same run, silently corrupting the final root-to-root distance. Same failure shape as
the reverted parallel-batching bug, for a different underlying reason.
4. **No dead/unread cells to eliminate either**, which would have been a legitimate zero-risk win
if it existed. APTED's optimal-strategy selection is precisely the published result (Pawlik &
Augsten) that the algorithm already computes the minimum *sufficient* set of forest-distance
cells for the chosen decomposition - there's no slack computation sitting on top of that
already-tight bound to cut.
**Conclusion**: this isn't "risky, needs extra care" the way parallel batching was - it's
structurally inapplicable to this DP's dependency shape (matrix-chain-style reuse within a single
call, not independent search branches with discardable alternatives). Nothing was implemented;
the oracle-fuzz harness was read but not modified, `engine.rs`/`common.rs` are untouched. Not
reverted because nothing was changed - ruled out at the design stage instead, before writing a
prototype that the analysis already shows can't work. Remaining real levers for the `/goal` speed
target, if any exist, are more likely in reducing *residual size* fed into the DP (fewer/smaller
subtree pairs reaching `apted::for_nodes` at all, e.g. via earlier-phase matching improvements)
than in trying to make the DP engine itself asymptotically cheaper per cell - `matches` was found
to drive cost roughly quadratically (see the correlation analysis above), so shrinking `matches`
before APTED ever runs is the lever with headroom, not pruning within APTED once it's running.
## Bounded-error (1%-of-optimal) pruning - investigated 2026-07-26 (user follow-up question), size-difference banding ruled out by data, nothing implemented
Direct follow-up: if we don't need the *exact* answer, only one within 1% of optimal, does that
change the "no slack above the bound" conclusion above? Structurally, yes in principle - accepting
bounded error is exactly what unlocks the standard technique for this class of problem: threshold/
band-limited edit distance (Ukkonen-style for strings; the tree analogue restricts the DP to
keyroot pairs whose subtree sizes don't differ by more than the acceptable distance budget, since
`|size1 - size2|` is always an admissible *lower* bound on true edit distance - a size mismatch of
`k` requires at least `k` inserts/deletes no matter what). This removes objection #2 from the exact
case (no slack above the trivial bound) because now cells that provably lie *outside* the tolerance
band around a target threshold can be skipped rather than needing their exact value.
**Checked against real data before assuming this helps**: re-instrumented `resolve_forest`
(`common.rs`, temporary, reverted immediately after) to log `size1`/`size2`/`|size1-size2|`/
`elapsed_ms` for every `apted::for_nodes` call >=2ms on the full `benchmark_other` corpus
(GUMTREE_BIN pointed at the local `/var/tmp/gumtree-installed` build) - 124 samples, 23 of them
>100ms. Result: **`|size1-size2|` (or the ratio `|size1-size2|/max(size1,size2)`) essentially does
not predict runtime** - log-log Pearson correlation of `|size1-size2|` vs `elapsed_ms` is only
0.30 (vs. 0.93 for raw `max(size1,size2)`), and the ratio-vs-`log(elapsed_ms)` correlation is
-0.03, indistinguishable from zero. Concretely: 43% of the >100ms cases have `|size1-size2|` under
5% of the larger tree's size - e.g. 728 vs 738 nodes (10 different, ratio 0.014) taking 916ms, 508
vs 516 (ratio 0.016) taking 596ms, 436 vs 438 (ratio 0.005) taking 339ms. These are same-size trees
with heavy internal restructuring (matches-driven cost, consistent with the earlier `matches^2.0`
regression finding), not size-mismatched trees. A size-difference band would have to span nearly
the *entire* width to avoid excluding cells the true optimal mapping actually needs on exactly the
cases that are slow - i.e. the one bounded-error technique this problem shape normally unlocks
doesn't apply to *this* corpus's pathological cases, this isn't speculation, it's what the data
says.
**What's left, and why it's a bigger lift than worth prototyping speculatively**: the only other
bounded-error lever would be clamping DP propagation once a running partial cost already exceeds
`(1+epsilon)` times a *fast heuristic* upper bound for the whole pair (not the trivial delete-all/
insert-all bound already baked into the recurrence - a real one would need its own approximate
matcher to seed it, e.g. a greedy same-hash/same-kind pre-match). That needs: (a) a new fast
heuristic matcher good enough to produce a useful upper bound cheaply, (b) a correctness proof
that epsilon-error propagates boundedly through the matrix-chain cell reuse confirmed above (not
obviously true - an epsilon-error substituted into an earlier cell and then summed into several
later cells could compound past epsilon if not handled carefully), and (c) a different validation
methodology entirely (`assert_distance_matches_oracle` asserts exact equality; a bounded-error
variant needs a new harness asserting `new_cost <= oracle_cost * 1.01` instead, plus a proof - not
just fuzz-testing - that this is what compounds to in the worst case). Given the track record here
(two prior approximation attempts both reverted - size/dissimilarity-capped fallback found no
configuration with a real win, parallel batching found a real correctness bug), this is a real
option but a much larger, uncertain-payoff engineering effort, not a quick prototype - flagged for
the user to decide whether it's worth the investment rather than started speculatively. Nothing
implemented; `common.rs` instrumentation was added and reverted (`git checkout --`) in the same
step, working tree confirmed clean.
## `ASTMetadata`'s remaining `HashMap`s converted to `FxHashMap` - 2026-07-26 (user-requested: "let's focus on reducing the residual"), KEPT: real, broad, zero-risk win found via profiling, not where the investigation started looking
User asked to focus on reducing the *residual* fed into APTED (phase 6), following the earlier
`matches`-drives-cost regression finding. Investigated by profiling one of the worst offenders
end to end rather than guessing which phase to target.
**Investigation** (temporary `eprintln!` instrumentation throughout `diff.rs`/`solve_syntax_aware_
matching.rs`/`solve_greedy_anchor_blocks.rs`/`apted/common.rs`, all reverted via `git checkout --`
once each measurement was taken): picked `c-cpython-autogenerated-code` (the current worst
offender at 3377ms `codediff_ms`, a 4150-line autogenerated CPython bytecode-interpreter dispatch
table where only one ~40-line `case` arm actually changed). First surprise: **APTED itself (phase
6) is not the bottleneck for this fixture at all** - only 2 real DP calls happen (28.6ms + 3.3ms,
~32ms total), the other 99 top-level candidate pairs all take the bit-identical-hash fast path
(`emit_identical_subtree`). This directly falsified the working hypothesis that "reduce the
residual" meant "shrink what reaches APTED" for this fixture - the residual was already tiny.
Added phase-level timers instead and found every phase costs roughly the same regardless of what
it actually does: phase1 (hash descent) 888ms, phase2 325-344ms, phase4's four sub-mechanisms
272-355ms *each* (flat subtrees, named groups, import-list overlap, greedy anchor blocks), phase6
269-289ms (only ~32ms of which is real APTED work per above), phase7 272-282ms. The smoking gun:
`solve_import_list_overlap` is Rust-only (`if before_metadata.language != Language::Rust { return;
}` as its first line) yet still cost ~275ms on this **C** file - a function that provably does
nothing for this language was exactly as slow as functions that do real work, meaning the cost
wasn't in any phase's own logic at all.
Checked `ASTMetadata`'s field types (`src/code.rs`) and found the actual cause: 11 of its 12
`HashMap`s (`node_to_full_hash`, `full_hash_to_node`, `node_to_structural_hash`,
`structural_hash_to_node`, `node_to_kind_and_value_hash`, `kind_and_value_hash_to_node`,
`node_to_kind_only_hash`, `kind_only_hash_to_node`, `node_to_subtree_size`,
`node_to_widest_subtree_node`, `node_to_depth`, `node_info`) still used
`std::collections::HashMap` (SipHash) despite `node_to_parent` already having been converted to
`rustc_hash::FxHashMap` back on 2026-07-16, with a doc comment describing *exactly* this class of
bug already confirmed once: SipHash's per-process random reseed caused measured 2.8s-26.4s (~10x)
run-to-run variance on `kotlin-nextcloud-a-few-small-removals`, CPU-bound the whole time. That fix
was never generalized to the rest of `ASTMetadata`'s equally hot, equally small-integer-keyed maps
- exactly the ~29,000-entry-per-side maps every phase above queries repeatedly via `metadata_of`.
**Before converting, checked every direct iteration (not just `.get()` lookups) of these 12 fields
for order-sensitivity**, since switching hashers changes `HashMap` iteration order and this
codebase has explicit, previously-hard-won determinism requirements (`full_hash_to_node`'s `Vec`-
not-`HashSet` choice, `grouped_greedy_matcher`'s determinism contract, `describe_nondeterminism` in
`test/helper/human_mapping.rs`). Found 8 direct-iteration call sites total (`hash.rs` x4,
`solve_bottom_up_expansion.rs` x1, `solve_hash_descent.rs` x1, `hash_tree_matching.rs` x1,
`metadata.rs` x1) - 4 are inside `#[test]` functions doing order-independent assertions (set
membership, size comparisons), and the other 4 all immediately collect into a `Vec` and sort by a
document-position-derived key (`preorder_index`, `start_byte`) before using the result, exactly the
existing "sort by `start_byte`, never raw node id or map order" convention this codebase already
follows elsewhere. None depend on raw iteration order, so the conversion is safe.
**Change**: all 11 remaining fields converted from `std::collections::HashMap` to
`rustc_hash::FxHashMap`, following `node_to_parent`'s already-established precedent exactly. A
handful of call sites had explicit `HashMap<usize, u64>`/`HashMap<u64, Vec<usize>>` type
annotations that needed generalizing to match (`hash_tree_matching::solve_with_hash_map` and its
`index_by_hash` closure, `solve_hash_descent::import_path_hash_map` and its local `after_reverse`,
two `human_solver.rs` helpers - `handle_key`'s params and 7 test-local `no_hashes` bindings - and
two `apted/common/tests.rs` synthetic-metadata builders). No behavior changes, purely widening
type annotations to match the now-generic field types.
**Validated**: `cargo build --release --all-targets` clean (only pre-existing, unrelated warnings).
`cargo test --release` (every target, not just `--lib`): **all green** - 362 lib tests + every
other test binary, 0 failures. `benchmark_optimal_solutions`: **739 mismatches (0.19%), identical
to the pre-change baseline** - confirms zero accuracy impact, as expected for a pure hasher swap.
`benchmark_other` (full 98-fixture corpus, `codediff_ms`): median **61.3ms -> 49.3ms** (-19.5%),
p90 **1011.2ms -> 860.9ms** (-14.9%), max **3365.2ms -> 3195.1ms** (-5.1%). Per-fixture spot check
(`c-cpython-autogenerated-code`, `kotlin-nextcloud-a-few-small-removals`, `c-linux-small-bugfix`,
6 repeated in-process runs each via a throwaway `variance_test` binary, deleted after use): each
~6-10% faster and consistently so, run to run - notably, none of the three reproduced anything like
the dramatic 10x SipHash-reseed variance `node_to_parent`'s original fix documented, so today's win
looks like straightforward FxHash-is-cheaper-per-op, not this session getting lucky/unlucky on
reseed variance. Real, broad, zero-risk (same computation, different hasher, iteration-order
dependence checked and ruled out above), and unlike every other speed lever tried this session,
found by actually profiling a slow fixture end to end rather than guessing where the cost was -
the residual/`matches` framing that motivated the search turned out not to be this fixture's actual
bottleneck at all, which is itself worth remembering next time a slow fixture needs diagnosing:
profile before assuming the pipeline stage a general theory points to is the one actually at fault.
Still well short of the `/goal` targets (median 20ms, p90 100ms, max 400ms) - this is a broad,
foundational win, not a silver bullet. Worth checking whether `NodeCache` (`diff.rs`) or other
hot-path `HashMap`s outside `ASTMetadata` have the same untreated SipHash tax before assuming this
lever is exhausted.
## `NodeCache` and `ASTDiff::mapping`/`before_node_map`/`after_node_map` converted to `FxHashMap` too - 2026-07-26 (user: "Commit and proceed"), KEPT: correctness-neutral and no measured regression, but the additional win over the `ASTMetadata` round alone is within noise
Direct follow-up to the `ASTMetadata` conversion above, which flagged `NodeCache` and other hot-path
maps as worth checking next. `NodeCache::before`/`::after` (`HashMap<usize, tree_sitter::Node<'static>>`,
81 call sites) are exactly the same shape and size (~29,000 entries/side) as `ASTMetadata`'s maps;
`ASTDiff::mapping`/`before_node_map`/`after_node_map` are read via `.contains_key()`/`.get()` on
every candidate node considered by every phase (the busiest lookup in the whole pipeline, per
`grouped_greedy_matcher::solve`'s doc comment) though typically far fewer *entries* than
`ASTMetadata`'s maps (proportional to matched-pair count, not total node count).
**Iteration-order audit done first, same discipline as the `ASTMetadata` round**: found 8 direct-
iteration call sites across `diff.rs`, `solve_comment_nodes.rs`, `apted/common.rs`. All either
`#[test]`-only order-independent assertions, collect into a `HashSet`/build an unordered lookup
structure, or (the one requiring actual reasoning - `solve_comment_nodes::solve`'s `current_mappings`
snapshot) are provably order-independent by construction: each entry's immediate-preceding-comment-
sibling match is a pure function of a fixed pre-loop snapshot and the AST's own sibling structure,
which is 1:1 per node regardless of which order the loop visits matched pairs in - two different
entries can never race to claim the same comment. Safe to convert.
**Change**: `NodeCache::before`/`::after` and `ASTDiff::mapping`/`before_node_map`/`after_node_map`
all converted to `rustc_hash::FxHashMap`. Much larger blast radius than the `ASTMetadata` round -
~35 call sites across `apted/common.rs`, `apted/engine.rs`, `solve_moved_subtrees.rs`,
`solve_greedy_anchor_blocks.rs`, `solve_syntax_aware_matching.rs`, `solve_identical_diagnostic_
statements.rs`, `solve_similar_flow_control.rs` (via the shared `nodes::collect_unmatched`),
`test/helper/human_mapping.rs`, `test/helper/optimal_iud.rs` - all mechanical type-annotation
widening (`&HashMap<usize, usize>` -> `&rustc_hash::FxHashMap<usize, usize>` etc.), no logic
changes, found by letting the compiler enumerate every call site rather than grepping for all of
them up front. Cleaned up the now-unused `std::collections::HashMap` imports this left behind in
`code.rs`, `apted/engine.rs`, `nodes.rs`, `solve_hash_descent.rs`, `solve_moved_subtrees.rs` (kept
`HashSet` where still needed). Left one pre-existing unused `anyhow::Result` import in
`apted/common.rs` alone - confirmed via `git stash` that it predates this round entirely, not
something introduced here.
**Validated**: `cargo build --release --all-targets` clean (only the same 4 pre-existing warnings
as before this round, confirmed via `git stash` diff). `cargo test --release` (every target): all
green, 362 lib tests + every other binary, 0 failures. `benchmark_optimal_solutions`: 739 mismatches
(0.19%), identical again - zero accuracy impact, as expected.
**Speed measurement, and an important caveat**: `benchmark_other`'s own median/p90/max swung
noticeably between consecutive identical runs on this machine (49.3/860.9/3195.1ms immediately
after the `ASTMetadata`-only round, then 55.2/878.1/3147.9ms and 58.0/917.0/3212.8ms in two
back-to-back runs after this round, none of which changed the code in between) - roughly a
+-10% swing from ambient system load, not signal. Trusted the cleaner in-process methodology
instead (`variance_test`, a throwaway binary calling `diff::diff_code` directly in a loop, no
subprocess/gumtree overhead, deleted after use): repeated timing on the same three fixtures used
to validate the `ASTMetadata` round showed this round is flat-to-marginally-positive versus that
checkpoint, not a further clear win - `c-cpython-autogenerated-code` 2688-2730ms -> 2657-2781ms,
`kotlin-nextcloud-a-few-small-removals` 1713-1784ms -> 1719-1793ms, `c-linux-small-bugfix`
2302-2352ms -> 2255-2361ms. All within each other's noise bands.
**Why keep it despite the unclear marginal win**: zero measured regression on any metric, zero
accuracy impact, same pattern already validated once this session, and `NodeCache` in particular is
exactly the same size/shape as `ASTMetadata`'s maps so there's no principled reason to expect it
*not* to carry the same (smaller, since it's one lookup per node rather than several) per-op benefit
- the lack of a clearly-measurable *additional* win on top of the `ASTMetadata` round most likely
means that round already captured the dominant share of this whole lever's value (fewer, larger
maps get proportionally more benefit from a cheaper hash function than many small ones), not that
this round did nothing. Kept on the same zero-risk basis as the first round, not oversold as a
second big win - the honest finding is "no regression, unclear additional gain," and that's what's
recorded here rather than a fabricated speedup number.
## `benchmark_other --repeats N`: fixed the measurement noise directly, added a per-tool variance chart - 2026-07-26 (user-requested)
The noise flagged in the round above (`benchmark_other`'s own median/p90/max swinging ~+-10%
between back-to-back single-shot runs) made it impossible to tell a real speed change from ambient
system load using a single run. User asked to fix this properly: run every measurement 3x, report
all of them, chart the variance per tool, and regenerate the existing plots against real repeated
data.
**`benchmark_other.rs` changes**: added `--repeats <N>` (default 3). Mismatch/accuracy counts are
computed once per fixture (deterministic - re-deriving them per repeat would be wasted work, not a
second independent measurement); only wall-clock timing (`codediff_ms`, each `tool_ms`,
`treesitter_parse_ms`, `gumtree_warm_ms`) is re-measured `--repeats` times. `gumtree_warm_ms` in
particular required repeating the *whole-corpus* `gumtree_warm_batch` JVM call `--repeats` times
(it's called once for the whole corpus, not per-fixture), not just looping inside the per-fixture
loop like the others. `Row`'s timing fields became `Vec<f64>` (one entry per repeat);
`benchmark_other.csv`'s timing columns now hold every repeat `;`-joined in one field (`join_ms`) -
`"12.3;13.1;12.8"` for 3 repeats - rather than adding new numbered columns, so the CSV's shape
(column count) stays stable regardless of `--repeats`, and `--repeats 1` produces a CSV
byte-for-byte compatible with "no repeats" (a one-element list). `print_runtime_table` gained a
"CoV %" column (`mean_coefficient_of_variation`: per-fixture stddev/mean averaged across fixtures)
so the noise problem is visible directly in the console table, not just in the CSV/plots.
**`benchmark_other_report.py` changes**: `ms_values`/`ms_median` parse the new `;`-joined columns.
`plot_runtime` now plots every individual repeat as its own point (294 = 98 fixtures x 3 repeats
for codediff/unix_diff/treesitter, fewer for GumTree's language-scoped n=97) instead of one point
per fixture - a real increase in the honest sample size, not just re-plotting the same data.
`plot_variance` is the new third chart (`benchmark_other_variance.png`): one box (+ jittered strip)
per tool of `coefficients_of_variation` (per-fixture stddev/mean %, matching the console table's
new column), answering "how much should a single run's number be trusted" as a companion to the
runtime plot's "what does the full distribution look like." A tool with fewer than 3 usable
multi-repeat fixtures is dropped from this chart rather than drawing a misleading box from 1-2
points (mirrors `applicable_rows`' existing "drop, don't zero-fill" convention).
**Real result, run against the full 98-fixture corpus with `--repeats 3`**: per-fixture-then-
averaged CoV was **codediff 2.5% median / 5.1% mean** - far tighter than the ~10% swings seen
comparing *whole-corpus aggregate* percentiles between separate single-shot runs (that comparison
was conflating per-fixture noise with which specific fixtures happened to land near a percentile
boundary in the flattened distribution - two different things, and per-fixture CoV is the more
honest one to trust for "how noisy is codediff specifically"). `treesitter_parse` was noisiest
(11.6% median CoV - unsurprising, its absolute times are the smallest in the whole benchmark, ~1ms,
so fixed overhead dominates the measurement); `unix_diff` 7.9%; `gumtree`/`gumtree_warm` (subprocess
+ JVM) 3.9%/2.6%.
**Trustworthy `codediff_ms` numbers from this run** (294 flattened samples, or 98 per-fixture
medians-of-3 - both given since they answer slightly different questions and landed close together,
confirming the noise problem really is fixed): flattened median 46.73ms / p90 1028.9ms / max
3162.1ms; per-fixture-median median 46.34ms / p90 950.7ms / max 3147.9ms. Still well short of the
`/goal` targets (20ms/100ms/400ms), but for the first time these numbers are actually trustworthy
enough to compare a future change's before/after against, rather than needing a "this might just be
noise" caveat attached to every single-run number.
**Validated**: `cargo test --release` (every target): all green, 362 lib tests + every other
binary, 0 failures (this touched `benchmark_other.rs`'s scoring/CSV/table logic non-trivially, so
re-ran the full suite even though nothing in the library itself changed). `research/benchmark_
other.csv` and all three PNGs in `research/plots/` regenerated from this real run and committed.
## Found the real bottleneck: `ast_metadata` recomputed ~20x per diff on the test/benchmark fixture path - tried 2026-07-26 (user: "What is the next speed improvement to try"), naive fix reverted (real correctness bug found), root cause understood but not yet safely fixed
User asked what's next. Re-profiled `c-cpython-autogenerated-code` (the worst offender, post both
`FxHashMap` rounds) with the same temporary phase timers used earlier in the session. Every phase
still cost roughly the same ~250-320ms *regardless of what it does* - including `solve_import_
list_overlap`, which is Rust-only and returns on its first line for this C file. A function that
provably does nothing was still exactly as slow as ones doing real work, the same anomaly noticed
before the `FxHashMap` fix, except the `FxHashMap` fix only made the anomaly cheaper per-occurrence,
not less frequent. That pointed at something outside any individual phase's own logic.
**Root cause, confirmed directly**: added a call counter to `compute_ast_metadata` (`code/
metadata.rs`) - **20 separate full recomputes for one `diff_code()` call on one fixture pair**
(~10 per side, one per pipeline phase/sub-phase that calls `metadata_of`). `metadata_of`'s own doc
comment promises "in the normal pipeline the metadata is always already present, so this is a
plain borrow and costs nothing" - that promise was being silently broken. Traced it to `src/test/
helper.rs`: `code_pair_from_dir`/`handmade_test_code` (used by `handmade_test_code_pairs`, which
`benchmark_other`, `benchmark_optimal_solutions`, and ~85 call sites across the test suite all go
through) call the bare `Code::parse` - which only sets `code.ast` - instead of `Code::ensure_
parsed` - which parses *and* caches `ast_metadata`, the way `Code::from_string`/`from_file` (real
production's actual entry points, confirmed via `tui/app.rs`'s `Code::from_file` call) already do.
Every `metadata_of(&code)` call anywhere in the pipeline for a `Code` from this path finds `None`
cached and silently recomputes from scratch, forever, for the life of that `Code` value.
**This whole session's `/goal` numbers were measuring a benchmark-harness artifact, not production
reality** - real callers that go through `Code::from_file`/`from_string` never hit this path at
all. Confirmed the fix's *ceiling* directly: swapping the two bare `.parse()` calls for `.ensure_
parsed()` in `src/test/helper.rs` dropped `c-cpython-autogenerated-code`'s single-diff time from
**2740ms to 125.9ms - a ~22x speedup** (phase6/APTED alone: 253ms -> 0.004ms, now genuinely just a
cache hit). That's a far bigger lever than anything else found this session, including both
`FxHashMap` rounds combined.
**Tried the obvious fix, it broke 112 tests, reverted immediately**: changing `code_pair_from_dir`/
`handmade_test_code` to call `ensure_parsed()` instead of bare `.parse()` (so metadata gets cached
once, at fixture-load time, before entries go into the shared cache) looked like the right fix and
passed a quick smoke test - but `cargo test --release` immediately surfaced 112 failures, e.g.
`diff_identical_rust_code` panicking with "Root node should be mapping". Root cause: **tree-sitter
node ids are arena-slot indices, not stable across a `Code::clone()`** - this is already documented
elsewhere in this exact codebase (`test/helper.rs`'s own `path_for_node` doc comment: "unlike
TreeSitter node IDs, which are arena slot indices and can differ between parses"), just not
connected to this specific caching decision before now. `handmade_test_code_pairs()` explicitly
memoizes its whole fixture map once and "hands out clones... from then on" (its own doc comment) -
that clone is the standard, intended usage pattern for ~85 call sites. If `ast_metadata` is
computed and cached *before* that clone point, every clone inherits a copy of metadata whose node
ids reference the *pre-clone* tree's arena - a **different, no-longer-matching** arena once the
clone's own `tree_sitter::Tree::clone()` reallocates. The clone's `ast` and its inherited
`ast_metadata` silently disagree on what id means what node, corrupting every subsequent lookup.
This never showed up before because `ast_metadata` was never populated on the shared/pre-clone
instance at all - always `None`, always freshly (and therefore correctly, if wastefully) recomputed
per-clone.
**Why this isn't a dead end, just not solved yet**: `benchmark_other.rs`'s actual hot path (`main`'s
`test_diffs.get(name)` -> `&Code` used directly, no `.clone()` before diffing) doesn't hit this
specific hazard - the 20x-recompute bug is real and fixable for that caller. The unsafe case is
specifically "cache metadata, *then* clone, *then* diff the clone" - callers that clone before
diffing need their OWN post-clone `ensure_parsed()` call (cheap - one recompute per clone, not one
per `metadata_of` call within that clone's lifetime), not a pre-cached copy inherited from the
clone source. A correct fix needs to either: (a) scope the caching fix narrowly to callers
confirmed not to clone before diffing (real but fragile - nothing stops a future caller from adding
a `.clone()` and silently reintroducing this), or (b) make the unsafe pattern impossible by
construction - e.g. a custom `Clone` impl for `Code` that either re-derives `ast_metadata`'s node
ids to match the new arena, or simply drops `ast_metadata` back to `None` on clone (safe, correct,
but reduces the fix to "one recompute per clone" rather than eliminating the redundancy for callers
that clone once per test but then run multiple diffs against the same clone - still likely a huge
win over 20x-per-diff, just not as complete as the naive version). (b) is probably the right shape:
it makes the invariant "ast_metadata's ids match ast's ids" hold by construction everywhere,
instead of relying on every one of ~85 call sites to individually get clone-timing right.
**State**: fully reverted, `src/test/helper.rs` back to its committed form, `cargo test --release`
green again (362/0/5), working tree clean. Nothing shipped from this entry - flagged as the
clearest, highest-value next lever, with the specific correctness hazard that blocks the naive
version now understood and documented so the next attempt doesn't have to rediscover it.
## Real fix landed: `Code`'s hand-written `Clone` + `ensure_parsed` at both the fixture loader and `benchmark_other`'s call site - 2026-07-26 (user: "Implement"), KEPT: median now meets the `/goal` target
Direct follow-up to the entry above. Before implementing anything, verified the *exact* mechanism
with a tiny throwaway binary (`src/bin/clone_test.rs`, deleted after use): parsed a 33-node Rust
fixture, cloned it 3 times, compared every node's id between original and each clone. Result:
**exactly 32 of 33 ids matched - only the root node's id ever changed**, deterministically, every
time. This precisely explains the earlier "Root node should be mapping" panic (the one lookup that
always fails is the one keyed on the root pair) and rules out the broader "the whole arena
reallocates" theory - `tree_sitter::Tree::clone()` shares the underlying parsed structure (every
non-root node's id survives) but hands back a distinct tree handle whose root gets a fresh id.
**The fix, in two parts**:
1. **`Code` gets a hand-written `Clone`** (`code.rs`), replacing `#[derive(Clone)]`: clones
`contents`/`ast` normally, but always resets `metadata.ast_metadata` to `None` on the clone.
This makes "an `ast_metadata`'s node ids always match its own `ast`'s node ids" hold **by
construction**, for all ~85 call sites, rather than trusting every one of them to individually
get clone-timing right (which is exactly what went wrong in the first attempt). Cost: a clone
that goes on to get diffed pays one recompute the first time `metadata_of` needs it - same as
an always-uncached `Code` already paid, just no longer paid *repeatedly* within one diff. A
caller that never clones at all keeps the full caching benefit untouched.
2. **`ensure_parsed` (not bare `parse`) in three places**: `code_pair_from_dir`/`handmade_test_code`
(`test/helper.rs`, same change as the reverted attempt - now safe) so metadata is correct at
first load, and - the piece the first attempt was missing - **`benchmark_other.rs`'s own
`main()`**. Reason: `handmade_test_code_pairs()` always returns a fresh `.clone()` of its
internal `OnceLock` cache (its own doc comment: "hand out clones... from then on"), and per (1)
that clone always resets `ast_metadata` back to `None` regardless of what the loader did -
discovered by measuring `benchmark_other`'s own numbers barely move (317ms -> 323ms mean,
noise) after only fixing the loader, then reasoning through *why* a caller with no `.clone()` of
its own was still uncached. Added one `ensure_parsed()` loop over `test_diffs.values_mut()`
right after `handmade_test_code_pairs()` returns, before any scoring/timing begins - this is the
*last* clone in `benchmark_other`'s whole call chain, so every one of `score_fixture`'s (up to
`--repeats`-many) `diff_code` calls per fixture reads the same, now-metadata-cached `Code`
value, and every `metadata_of` call anywhere in the pipeline for it is a real cache hit.
**Validated**: `cargo test --release` (every target): all green, 362 lib tests + every other
binary, 0 failures - the exact same 112 tests that failed on the first attempt now pass, because
the clone-staleness hazard that broke them no longer exists. `benchmark_optimal_solutions`: 739
mismatches (0.19%), identical - zero accuracy impact, as always expected for a pure caching fix.
`benchmark_other --repeats 3`, full 98-fixture corpus: **codediff mean 317.3ms -> 113.8ms (2.8x)**;
CSV-derived percentiles (294 flattened samples): **median 46.7ms -> 9.75ms, p90 1029ms -> 256ms,
max 3162ms -> 1386ms**. Mismatch counts (473/570/637 for codediff/unix_diff/gumtree) byte-identical
to the pre-fix run - confirms the fix changes only caching, never behavior.
**`/goal` status: median target met for the first time this session** (9.75ms, target <=20ms). p90
(256ms, target <=100ms) and max (1386ms, target <=400ms) both improved dramatically (4.0x and
2.3x respectively) but remain over target - the worst-offender fixtures (large autogenerated files)
still pay real, correctness-necessary pipeline cost even with zero redundant metadata recomputation
now; further gains on those need a different lever (e.g. the residual-size ideas from earlier in
this session), not more caching. `research/benchmark_other.csv` and all three `research/plots/*.png`
regenerated from this real run. Throwaway `src/bin/clone_test.rs` deleted after use, per the
established pattern for this kind of grammar/runtime verification binary.
## Four new optimal-solution fixtures added, one clamped: `css-wordpress-reformat` (2026-07-31)
Added `csharp-sonarr-add-if-block`, `css-wordpress-reformat`, `html-fatedier-add-attribute`, and
`rust-rustdesk-add-item` to `src/test/data/diffs/` (human-verified ground truth via
`human_solver`). Three match codediff's diff exactly (`assert_matches_human_mapping`, 0
mismatches). `css-wordpress-reformat` needed `assert_matches_human_mapping_within_limit(30)`
instead.
**The gap**: reformatting minified CSS into one-declaration-per-line swaps the order of two
structurally-identical-shaped declaration pairs within the same `rule_set` (`margin-bottom` then
`margin-top` before, `margin-top` then `margin-bottom` after, in both
`:where(.wp-block-post-excerpt)` and `.wp-block-post-excerpt__excerpt`). APTED's final pass finds
an equal-cost mapping that pairs each declaration with its positional counterpart (`Update`-ing
`margin-bottom`'s node into `margin-top`'s text) rather than following the property name across
the reorder - a locality-optimal solution the human ground truth doesn't share. Same class of
ambiguous-mapping gap as `c-postgres-real-logic-change` (see "Known gaps with full analysis"
above), not a bug with a fix pending.
**Quality baseline updated**: `research/quality_baseline.txt`'s `TOTAL_MISMATCHES` 744 -> 774 (the
new fixtures' combined contribution: 0 + 30 + 0 + 0) via `make update-quality-baseline` - a
deliberate, reviewed shift from corpus growth, not a hidden regression in any existing fixture.
`MS_PER_FIXTURE` 1083 -> 1136.3 (103 fixtures now, up from 99). `cargo test --release --lib`:
440/0/5, `make check-quality`: clean against the new baseline.