Skip to content

spec.md

Latest commit

 

History

History
92 lines (61 loc) · 19.1 KB

spec.md

File metadata and controls

92 lines (61 loc) · 19.1 KB
Raw

semantic-diff: A "did the meaning change?" CI oracle from region-erased MIR fingerprints

Hash each function's region-erased, monomorphized MIR to a fingerprint that — within a frozen toolchain and feature graph — is stable across cosmetic edits and sensitive to behavioral ones, so CI test selection scopes to the functions whose generated code actually changed; and we measure that stability on stage rather than assert it.

The Vision

Most bytes that move through CI on a push are noise: whitespace, comments, renames (even to different lengths), import reshuffles, lifetime-name churn, a rustfmt pass. Today every one of those reruns the full suite and pages a reviewer for a "diff" that compiles to identical behavior. We pay for the text diff, not the meaning diff. (A for→iterator rewrite is the one classic-cosmetic case we do not absorb — at pre-optimization MIR a loop and a .fold(...)-closure differ; we over-select rather than claim a robustness we measured to be false. See §"The headline overclaim" and docs/prior-art.md.)

semantic-diff inverts the unit of change: not the source line, but the function's compiled meaning. We take the compiler's own monomorphized MIR — the representation rustc already trusts for codegen — erase the parts provably irrelevant to behavior (regions, local names, spans), and hash to a 128-bit fingerprint per monomorphized function. A push changes a fingerprint when the compiler would emit different code for that function. That delta becomes a precise oracle for test selection and review attention. The bold bet: what changed should be answered in the IR, not the text — and once you have a cheap, content-addressed identity for compiled behavior, a whole class of CI waste disappears.

The honest version of the bet, which is the one that survives scrutiny: this is not an absolute oracle. It is a sharp, cosmetic-robust change detector whose discrimination is exactly that of rustc's MIR pipeline at a pinned configuration — and we say precisely where that boundary lies.

The Novel Idea

The mechanism is 100% borrowed and we keep that front and center. rustc already does per-query stable hashing internally (StableHasher/SipHasher128 driving the red/green dep-graph). cuda-oxide already content-addresses type identity. rustowl already region-erases a MIR body and hashes it as an in-process cache key. Nobody invented semantic hashing here.

The genuinely new work is two things rustowl and cuda-oxide never attempt, because they never had to:

  1. Cross-commit, cross-build stability engineering. rustowl's mir_hash is a single-process cache key; cuda-oxide's type_id_hash agreement holds within one rustc invocation (study.json how_it_works[8], verbatim). The hard, unglamorous contribution is making a function fingerprint comparable across two clean builds of two commits — defining the exact precondition (frozen toolchain + feature graph + normalized sysroot) under which that holds, and proving it on stage with a same-commit double-build that yields a byte-identical fingerprint set.
  2. The delta-set as a sound input to regression test selection (RTS). Classic RTS (Ekstazi, Google/Facebook TIA) selects at file/class granularity from coverage or build-graph heuristics. We select at monomorphized-function granularity from the IR, and we carry an explicit soundness argument for the over-approximation. The claim we will quantify, not assert: false-positive reduction vs class-level RTS on cosmetic churn.

That's the whole novelty surface. It is a granularity-plus-stability contribution on top of known TIA, not a new idea about hashing.

Prior Art & How We Differ

  • rustc incremental compilation (red/green dep-graph). Per-query Fingerprints over HIR/MIR already detect change to skip work. Differ: those hashes are query-keyed and salted with StableCrateId (crate name + disambiguator + version); they are not a portable, cross-commit, function-granular identity, and they are never exposed as a diffable artifact or wired to test selection. We re-target, not re-invent.
  • rustowl (hash.rs, transform.rs, analyze.rs under src/bin/core/compiler/). get_hash builds ich::StableHashingContext + StableHasher, hashes a Body via HashStable; RegionEraser is a TypeFolder whose fold_region returns re_static. Differ — and a correction to our own first draft: rustowl does NOT scrub spans. It hashes only the region-erased body; its cosmetic-robustness comes from a separate file_hash, and the cache key is (file_hash, mir_hash) (in analyze.rs). Span-robustness is therefore work we must add, not lift. Misattributing it to rustowl is a citation a reviewer opening transform.rs would catch in ten seconds; we name it correctly.
  • cuda-oxide (collector.rs, type_id.rs). tcx.type_id_hash(tuple_ty).as_u128() content-addresses a region-erased type for cross-boundary symbol agreement; the static_borrow_collides_with_free_borrow test proves free lifetimes hash identically. Differ: that is an in-process ABI handshake via core::intrinsics::type_id const-eval — the file's own doc comment frames it as inside one invocation. We borrow the principle (identity over a region-erased canonical form) and apply it to whole bodies across time.
  • Ekstazi / Google TIA / Facebook predictive selection. File/class-granular, coverage- or ML-driven, deliberately conservative. Differ: we select at monomorphized-function granularity from the IR, so cosmetic-only commits select zero tests by construction. We will quantify the FP reduction rather than claim it.
  • BinDiff / Diaphora / translation validation. Content-address compiled functions to detect behavioral change. Differ: they work post-link, losing DefPath, source granularity, and per-test reachability; we sit post-monomorphization where trait resolution is visible but source identity survives.
  • sccache / Nix / Cargo fingerprinting. Content-address build inputs to cache outputs. Differ: we content-address compiled meaning to answer a behavioral-change question; Cargo's fingerprint flips on a comment edit, ours does not.

Architecture

  • sdiff-driver (codegen backend, not after_analysis). Responsibility: enumerate codegen instances and emit fingerprints. Mechanism: the draft offered "after_analysis OR a thin codegen shim" as interchangeable — they are not, and this was our biggest underestimate. after_analysis runs before mono-item collection; you cannot enumerate Instances there. We do what cuda-oxide does: register a CodegenBackend whose codegen_crate(&self, tcx, _) (in cuda-oxide's lib.rs) calls tcx.collect_and_partition_mono_items(()), then delegates real codegen to the LLVM backend so the build still produces a binary. Budgeted as a backend shim, not a callback.
  • region-eraser + span/local canonicalizer. Responsibility: produce a canonical body. Mechanism: reuse rustowl's RegionEraser for regions, then add what rustowl never needed — a full structural pass over the body normalizing every SourceInfo span to DUMMY_SP and scrubbing LocalDecl/VarDebugInfo names. This touches every Statement/Terminator/LocalDecl/VarDebugInfo; it is real MIR-rewriting work, sized accordingly, not a one-line fold.
  • fingerprint engine. Responsibility: deterministic 128-bit hash. Mechanism: rustowl's get_hash verbatim — StableHashingContext + StableHasher, body.hash_stable(...), fold the two SipHasher128 lanes into a u128 hex string (in hash.rs). Fold in the region-erased signature's type_id_hash (from cuda-oxide's collector.rs).
  • fingerprint store (.sdiff/<commit>.idx). Responsibility: portable key→fingerprint map per commit. Mechanism: key = DefPathHash + substs type_id_hash; value = MIR fingerprint; sqlite/JSON, committed per tree.
  • delta engine. Responsibility: exact changed-function set. Mechanism: set diff over the keyspace → ADDED / REMOVED / CHANGED. Cosmetic-only commit ⇒ CHANGED empty by construction.
  • test-impact driver. Responsibility: minimal test set. Mechanism: during the build, record per-#[test] the transitively reachable keyset via a BFS over the MIR call graph (cuda-oxide collector.rs). Select a test iff its reachable-set intersects ADDED∪REMOVED∪CHANGED, with the dynamic-edge handling below.
  • review/audit annotator (stub in MVP). Responsibility: mark which functions semantically changed. Mechanism: per-PR JSON: changed fingerprints (old→new) vs cosmetic-only files; ADD+REMOVE pairs with identical fingerprints collapse to "moved, unchanged."

The Hard Problem & Our Approach

The fingerprint must be simultaneously stable (across cosmetic edits and separate builds) and discriminating (it flips when codegen would differ) — with no false "unchanged" verdict, the dangerous direction. Two real obstacles, both raised against the draft and both conceded:

1. Optimizer coupling. tcx.instance_mir returns optimized MIR — cuda-oxide documents this explicitly (in collector.rs; a note in lib.rs says it is "affected by -C opt-level, -Z mir-enable-passes," running Inlining and JumpThreading). Optimized-MIR hashing is therefore a function of the optimizer: a caller edit that pushes a callee across an inlining threshold flips the callee's inlined hash with no behavior change (false CHANGED), and two different sources can optimize to identical MIR (false UNCHANGED). Fix: hash the post-monomorphization, pre-optimization body — the mir_drops_elaborated_and_const_checked-class instance MIR, resolved through the mono instance so substitutions and trait resolution are visible, but before the heuristic MIR-opt passes. This decouples from inlining thresholds while keeping monomorphization sensitivity. Where we must touch optimized MIR, we run with a pinned, opt-disabled pass set (-Z mir-opt-level=0) so the body is deterministic for the corpus.

2. The headline overclaim. We retire "as correct as the compiler." The defensible claim: "as discriminating as rustc's pre-optimization monomorphized MIR at a pinned toolchain + feature graph." Cross-build stability holds only under that precondition because StableHasher folds in DefPathHash/StableCrateId (crate name, disambiguator, -Cmetadata, compiler version) and spans carry sysroot-relative StableSourceFileIds. We state the precondition as a contract, normalize the remaining axis (canonical workspace path / remapped sysroot via --remap-path-prefix), and verify stability empirically instead of by assertion.

The unifying principle, borrowed straight from cuda-oxide and rustowl: compute the fingerprint where the compiler already knows the answer, erase only what the compiler itself treats as irrelevant. Region erasure is proven codegen-irrelevant (the &'a i32 ≡ &'static i32 test in type_id.rs); spans and local names never reach codegen — except the location intrinsics, which we refuse to erase (below).

Control / Data Flow

  1. Developer pushes commit B; CI checks out base A and head B, both built with the same pinned toolchain, same feature set, remapped path prefix.
  2. For each commit, sdiff-driver runs as the codegen backend: rustc type/borrow-checks and monomorphizes; in codegen_crate we call collect_and_partition_mono_items, then delegate to LLVM so a binary is still produced.
  3. For each Instance, fetch the pre-optimization monomorphized body.
  4. Fold through RegionEraser; normalize all spans → DUMMY_SP; scrub local/debug names → canonical body.
  5. get_hash (StableHashingContext + StableHasher) over the canonical body, plus the signature's type_id_hash, → 128-bit mir_fp hex.
  6. Store under (DefPathHash, substs_tid) into .sdiff/<commit>.idx; record per-test reachable keysets via MIR call-graph BFS, with dyn/fn-ptr/FFI targets adding a "dynamic-root" tag.
  7. Delta engine diffs A.idx vs B.idx → ADDED/REMOVED/CHANGED. A rustfmt/comment/rename commit ⇒ CHANGED = {}.
  8. test-impact driver intersects each test's reachable-set (∪ its dynamic-root reach) with the delta and emits the minimal list, or "run nothing."
  9. Annotator emits the PR change-set JSON.

Key Design Decisions & Tradeoffs

  • Hash pre-optimization monomorphized MIR. Trade: immune to inlining-threshold churn, still sees trait resolution and substitution; blind to pure MIR-opt-level behavior differences (acceptable — those are config, not source). Cost is O(monomorphizations).
  • Reuse rustc's StableHasher verbatim. Trade: inherit rustc's notion of stable, plus its nightly rustc_private churn (rustowl gates on rustversion::since(1.89/1.95) in hash.rs). We pin a nightly and treat the driver as a versioned plugin requiring re-baseline on bump — a budgeted recurring full-build cost, not a hidden one.
  • State the stability precondition as a contract. Trade: no cross-toolchain magic, but the guarantee we keep is one we can demonstrate.
  • Stay SOUND on call-graph reachability. Trade: over-select rather than ever skip an affected visible test. Dynamic edges are a documented boundary (below).
  • Key by DefPathHash + substs type_id_hash. Trade: survives renames/recompiles; module moves change DefPath, surfacing as ADD+REMOVE with identical fingerprints, collapsed to "moved, unchanged."
  • Refuse to erase spans feeding location intrinsics. #[track_caller]/line!()/Location::caller make a span behaviorally load-bearing; we detect those uses and keep their spans, documented as a carve-out rather than silently erased.

MVP Scope

Delivers: a working sdiff-driver (nightly codegen-backend shim) over a real binary/integration-test workspace, emitting a (DefPathHash, substs_tid) → mir_fp store from region-erased + span/name-canonicalized pre-opt MIR using rustowl's hash pipeline; sdiff diff A B printing ADDED/REMOVED/CHANGED; the test-impact driver selecting the minimal #[test] set; and the falsification suite. Build sequence: (1) lift RegionEraser+get_hash into a standalone crate; (2) stand up the codegen-backend shim and enumerate instances; (3) add span/local canonicalization fold; (4) store + delta CLI; (5) per-test reachability BFS; (6) the differential validator + stability harness. Punts: cross-crate reachability beyond the local graph; ML refinement of dynamic edges; the audit-ledger UI (ship change-set JSON + stub annotation); incremental in-process caching (recompute per CI run); non-Rust languages. Demo repo must be a binary/integration-test workspace — for a pure library, the mono collector instantiates almost nothing; we name this explicitly and pick the repo accordingly.

The Demo

Live, three acts. Act 0 — the property nobody cited has shown: build the same commit twice, different working directory, fresh target dir, remapped paths; print that the full fingerprint set is byte-identical (CHANGED: 0). If this fails, the tool is a single-process curiosity, so we run it first. Act 1: a commit that runs rustfmt, renames three locals (to different lengths), and adds a doc comment → sdiff diff prints CHANGED: 0, the driver selects 0 tests, then we run the full suite green to prove we aren't broken. Act 2: flip one < to <= in one helper → CHANGED: 1: crate::geom::clamp with old/new fingerprints; exactly the tests reaching clamp run, the rest skip. Act 3 — the falsifications we went looking for, and what we measured: (a) a caller edit that would flip an inlined callee's hash under optimized MIR — our pre-opt hash does not flip (the hole we engineered out); (b) a for→iterator rewrite that we expected to be cosmetic but measured to flip the fingerprint at pre-opt MIR — a safe over-selection, shown honestly rather than hidden; (c) a #[track_caller] call-site line shift that a naive span-scrub would miss (a real false UNCHANGED) — we show the leak, then show our location-intrinsic carve-out catching it (CHANGED on the caller); and (d) a const N: 7→8 change our per-function body hash misses, which the build-config gate flags and conservatively widens. The mic-drop is not "we diff meaning"; it is "here is where our own tool is wrong, here is how we found it, and here is what we do about it."

Risks & Honest Limitations

  • Cross-build instability is the load-bearing risk. Toolchain bump, feature-flag change, or non-normalized sysroot path can shift fingerprints wholesale → a fully-red CHANGED on a no-op. Mitigation: contractually frozen toolchain+features, path remapping, mandatory same-commit double-build check, and a defined re-baseline protocol on any toolchain/feature change (recompute all fingerprints; never diff across a baseline boundary).
  • False UNCHANGED is the dangerous direction. Const/static value changes, cfg/#[inline]/target-feature/panic=abort build-config changes alter codegen without altering a function's body hash. Mitigation: the differential validator (build with/without opts, confirm equal-fingerprint ⇒ equal codegen on a corpus) is in MVP scope, not a promise; a build-config hash gates the whole run (config change ⇒ run everything); soft-mode runs a small random sample of skipped tests to detect drift.
  • Dynamic dispatch can swallow selection. Real tests cross dyn/fn-ptr boundaries everywhere (allocator, panic hook, formatters). If the dynamic-root set engulfs most tests, value collapses to "run everything." Mitigation: we measure the statically-selectable fraction on a real suite and report it honestly; if it is low, that is a finding, not a hidden failure.
  • Monomorphization blowup. O(instances) for generic-heavy crates (serde, nalgebra) can exceed the cost of just running the suite, recomputed per run since we punt caching. Mitigation: a generic-collapsed mode (hash un-substituted body + substs separately) and honest scoping to crates where it pays.
  • rustc_private churn: versioned plugin, pinned nightly, isolated behind rustowl's rustversion-gated module.

Why Linus Respects It

It refuses to hand-wave and it kills its own overclaims first. It drops "as correct as the compiler" for the precise, breakable-in-one-sentence-resistant "as discriminating as rustc's pre-optimization MIR at a pinned toolchain," and it fixes the optimizer-coupling hole (hash pre-opt MIR) instead of pretending it isn't there. It corrects its own citation — rustowl does not scrub spans, span-robustness is our work — because a planted misattribution poisons every other citation. It states the cross-build precondition as a contract and measures it on stage with a double-build rather than asserting the one property the cited code only guarantees within a single invocation. It puts the differential validator in MVP scope and goes hunting for its own false UNCHANGED (const/cfg) and false CHANGED (inlining) cases. The bad state — a silently-skipped affected test — is engineered toward impossible by construction (cosmetic ⇒ empty CHANGED), by sound over-approximation, and by a config-hash gate. The novelty claim is deflated to exactly what's defensible: cross-build stability engineering plus a sound RTS argument on borrowed mechanism. That is a person who found the holes before Linus did.