13 — Level 3, stage 3: access paths, reaching definitions & the DDG

[rahlk]

Part of #9. Phase 3 — native dataflow.

Learning goals

Dataflow analysis proper: forward may-analysis with a worklist, kill/gen sets, k-limited access
paths. Plus the payoff insight of doing this in RUST: ownership sharpens your analysis —
&mut is exclusive, so a write through a &mut borrow cannot alias any other live path; moves
END a path's liveness. Your language's semantics are doing points-to work for free.

Task

• Access-path model first (the vocabulary every DDG edge is labeled with): base(.field | [*])*,
  bases = locals / params / self / statics / captured vars (tagged which), all indices collapse
  to [*], depth k-limited (default 3, --graph-field-depth arrives with emission): x.f.g.h
  at k=3 → x.f.g.* which conservatively aliases everything deeper.
• Reaching definitions over the CFG (classic worklist). DDG edge = def-node → use-node,
  labeled with the path. Pattern-matching bindings (let Some(x) = ..., match arms,
  destructuring) are defs; expression-oriented arms (issue 11) mean arm results def the
  binding target.
• Writes through aliases are stage-5's refinement — until then a write to p.f where p may
  alias q does NOT kill/reach q.f. Document the &mut-exclusivity shortcut you CAN take now.

Gate (DFG gate)

• Every DDG edge connects a syntactic write of the path to a syntactic read of it.
• The loop-carried dependency fixture (x = x + 1 in a loop) produces the loop-carried edge.
• Shadowed variables (let x = ...; let x = ...; — idiomatic Rust!) do NOT leak edges across
  shadows; nested-scope shadowing asserted too.