Skip to content

design.md

Latest commit

 

History

History
124 lines (105 loc) · 8.89 KB

design.md

File metadata and controls

124 lines (105 loc) · 8.89 KB
Raw

design.md — how semantic-diff works

Companion to spec.md. The spec is the what/why; this is the how. Where they differ, the spec wins. Borrowed mechanisms below name the source project and file; the two projects are public and linked on first mention.

Vision

CI today reacts to text. A whitespace pass, a rename, a for→iterator rewrite, a rustfmt run — each reruns the full suite and pages a reviewer, even though the compiler would emit identical code. semantic-diff changes the unit of change from the source line to the function's compiled meaning. We compute a content-addressed identity for each monomorphized function from the representation rustc already trusts for codegen — MIR — erasing only what the compiler itself treats as behavior-irrelevant (regions, local names, spans), and hashing the rest to a 128-bit fingerprint. A push moves a fingerprint exactly when the compiler would emit different code for that function. That delta is a precise oracle for test selection, review scope, and re-audit scope.

The bet is deliberately deflated to what survives scrutiny: not an absolute behavioral oracle, but a sharp cosmetic-robust change detector whose discrimination is exactly rustc's pre-optimization MIR pipeline at a pinned configuration — and we measure that property rather than assert it.

Components and responsibilities

1. sdiff-driver (codegen backend shim). Enumerates the crate's monomorphized instances and emits fingerprints. The mechanism choice is load-bearing and was the spec's biggest underestimate: after_analysis runs before mono-item collection, so you cannot enumerate Instances there. We do what cuda-oxide does — register a CodegenBackend whose codegen_crate calls tcx.collect_and_partition_mono_items(()) then delegates real codegen to the LLVM backend so a binary is still produced (cuda-oxide's codegen backend in crates/rustc-codegen-cuda/src/lib.rs).

2. canon (region-eraser + span/local canonicalizer). Produces a canonical body. Region erasure is lifted from rustowl's RegionEraser (a TypeFolder whose fold_region returns re_static, in src/bin/core/compiler/transform.rs). Then we add what rustowl never needed: a structural pass over the body that normalizes every SourceInfo span to DUMMY_SP and scrubs LocalDecl/VarDebugInfo names. This touches every Statement/Terminator/LocalDecl/VarDebugInfo — it is real MIR rewriting, not a one-line fold. Carve-out: spans feeding location intrinsics (#[track_caller], line!(), Location::caller) are behaviorally load-bearing; we detect those uses and keep their spans rather than silently erase them.

3. hash (fingerprint engine). Deterministic 128-bit hash. rustowl's get_hash verbatim (in src/bin/core/compiler/hash.rs): build ich::StableHashingContext + StableHasher, body.hash_stable(...), fold the two SipHasher128 lanes into a u128 hex string. Fold in the region-erased signature's type_id_hash (cuda-oxide's collector.rs). The rustc_private import is gated with rustversion exactly as rustowl does (also in hash.rs).

4. store (fingerprint index, .sdiff/<commit>.idx). A portable key→fingerprint map committed per tree. Key = DefPathHash + the substs' type_id_hash; value = the MIR fingerprint. JSON or sqlite.

5. delta (changed-function classifier). A set diff over the keyspace → ADDED / REMOVED / CHANGED. A cosmetic-only commit yields CHANGED = {} by construction. Module moves change DefPath, so they surface as an ADD+REMOVE pair with identical fingerprints, collapsed to "moved, unchanged" (a heuristic, not an identity proof — red-team patch).

6. tia (test-impact driver). During the build, records per-#[test] the transitively reachable keyset via a BFS over the MIR call graph — the worklist pattern lifted from cuda-oxide's WorklistCollector (in crates/rustc-codegen-cuda/src/collector.rs). Selects a test iff its reachable-set intersects ADDED∪REMOVED∪CHANGED. Dynamic edges (dyn/fn-ptr/FFI) add a "dynamic-root" tag and widen selection — never silently skip (red-team patch).

7. validator + annotator. The differential validator runs the same-commit double-build (M0) and samples skipped tests to detect drift; the annotator emits per-PR change-set JSON.

Control / data flow

  1. CI checks out base A and head B, builds both with the same pinned toolchain, same features, --remap-path-prefix normalizing the workspace root, -Z mir-opt-level=0.
  2. For each commit, sdiff-driver runs as the codegen backend: rustc type/borrow-checks and monomorphizes; in codegen_crate we collect_and_partition_mono_items, then delegate to LLVM.
  3. For each Instance, fetch the pre-optimization monomorphized body (not instance_mir's optimized body — see Decisions).
  4. canon: fold through RegionEraser; normalize spans → DUMMY_SP; scrub local/debug names.
  5. hash: StableHashingContext + StableHasher over the canonical body + signature type_id_hash → 128-bit mir_fp.
  6. store: write (DefPathHash, substs_tid) → mir_fp into .sdiff/<commit>.idx; record per-test reachable keysets via the call-graph BFS, tagging dynamic roots.
  7. delta: diff A.idx vs B.idx → ADDED/REMOVED/CHANGED. Cosmetic commit ⇒ CHANGED = {}.
  8. tia: intersect each test's reachable-set (∪ its dynamic-root reach) with the delta → minimal test list, or "run nothing."
  9. Annotator emits the PR change-set JSON.

Key design decisions & tradeoffs

  • Hash pre-optimization monomorphized MIR, not optimized MIR. cuda-oxide documents that tcx.instance_mir returns optimized MIR "affected by -C opt-level, -Z mir-enable-passes" (noted in cuda-oxide's collector.rs and lib.rs). Hashing that couples the fingerprint to inlining thresholds: a caller edit can push a callee across an inline boundary and flip its inlined hash with no behavior change (false CHANGED), and two sources can optimize to identical MIR (false UNCHANGED). We hash the mir_drops_elaborated_and_const_checked-class body resolved through the mono instance — substitutions and trait resolution visible, heuristic MIR-opts not yet run. Trade: immune to inlining churn; blind to pure MIR-opt-level behavior differences (acceptable — those are build config, gated separately).
  • Reuse rustc's StableHasher verbatim. Trade: we inherit rustc's exact notion of "stable," and its nightly rustc_private churn. Mitigated by pinning a nightly and gating imports with rustversion (rustowl pattern). The driver is a versioned plugin; toolchain bump ⇒ full re-baseline.
  • State cross-build stability as a contract, then measure it. StableHasher folds in DefPathHash/StableCrateId (crate name, disambiguator, -Cmetadata, compiler version) and spans carry sysroot-relative StableSourceFileIds. Cross-build identity holds only under a frozen toolchain + feature graph + remapped paths. We normalize the path axis and prove the rest on stage (M0) rather than claim it.
  • Stay SOUND on reachability. Over-select rather than ever skip an affected visible test. Dynamic edges widen, never narrow.
  • A build-config fingerprint gates the whole run. rustc version, sysroot hash, target, panic strategy, features, cfgs, build-script env (red-team patch). Any config change ⇒ run everything; this is the safety net for the false-UNCHANGED class (const/static/cfg/target-feature).

How the borrowed techniques are adapted

Borrowed Source Adaptation
get_hash stable MIR hash rustowl — src/bin/core/compiler/hash.rs used verbatim as hash; output is our mir_fp
RegionEraser rustowl — src/bin/core/compiler/transform.rs reused as-is for regions; we add span/name canonicalization rustowl lacks
(file_hash, mir_hash) cache key rustowl — src/bin/core/analyze.rs correction: rustowl's cosmetic-robustness is the separate file_hash, not span-scrubbed MIR — so span robustness is our work
type_id_hash of region-erased type cuda-oxide — crates/cuda-host/src/type_id.rs, crates/rustc-codegen-cuda/src/collector.rs borrow the principle (identity over a region-erased canonical form); apply to whole bodies across time, not types within one invocation
codegen-backend seam cuda-oxide — crates/rustc-codegen-cuda/src/lib.rs sdiff-driver registers a backend, collects mono items, delegates to LLVM
call-graph BFS worklist cuda-oxide — crates/rustc-codegen-cuda/src/collector.rs per-test reachability collector for the tia selector

The unifying principle, straight from both repos: compute the fingerprint where the compiler already knows the answer, erase only what the compiler itself treats as irrelevant — and refuse to erase the one span class (location intrinsics) that is actually behavioral.