Class InterproceduralLockAnalyzer

java.lang.Object
org.ek9lang.compiler.phase5.lockanalysis.InterproceduralLockAnalyzer
public final class InterproceduralLockAnalyzer extends Object
Phase C.2 of slice-2 deadlock detection: compute per-function mayEnter summaries by composing direct enters with reachable enters via the call graph and CrossThreadEdge list.

Algorithm: monotone worklist iteration to fixpoint. For each function with an outgoing edge to g, add to mayEnter(f) every TransitiveEnterRecord in mayEnter(g), with the edge kind composed against the path kind (any cross-thread edge poisons the whole path). Sets only grow, so the iteration terminates even with cyclic call graphs.

Edge kind composition (per EK9_CONCURRENCY_MODEL.md §5.2): SAME ∘ SAME = SAME; any other combination is CROSS_THREAD. See EdgeKind.composeWith(EdgeKind).

Parameter substitution: lock identities expressed as parameter-rooted placeholder tokens (placeholder:<paramFqn>) in a callee are resolved at each call edge against the caller's actual argument identities — the Phase B.1 arg→param bindings looked up via LockAnalysis.lookupCallArgBindingsAggregated(String, String). See substitutePlaceholders(Set, Map). Multi-hop pass-through is handled by re-substituting on each propagation layer (a substituted identity that is itself a placeholder is resolved by the next caller). This is what lets the same caller-side lock passed into two distinct parameter slots collapse to one identity (reentrant, no false E08252), while a genuine parameter-rooted cross-function cycle still resolves to concrete identities and fires E08252. Field-/allocation-/capture-rooted identities are stable across call boundaries and pass through unchanged.

First-cut simplifications:

  • No explicit SCC condensation. Worklist iteration handles cycles by construction (monotone sets). Tarjan-based topological processing would reduce iteration count for deep linear chains; can be added later if profiling justifies it.
  • Call-arg bindings are aggregated across all sites of a given (caller, callee) pair rather than disambiguated per site. A callee invoked from one caller with different locks at different sites therefore sees the union of bound identities — an over-approximation (errs toward flagging, never toward missing), consistent with the strict stance. Per-site disambiguation is a precision refinement.

Outputs: every FunctionLockSummary in LockAnalysis.summariesByFqn() has its mayEnter field populated with the transitive closure. Summaries are auto-created for any function reached in the call graph that doesn't already have one.

  • Constructor Details

    • InterproceduralLockAnalyzer

      public InterproceduralLockAnalyzer(CallGraph callGraph, LockAnalysis lockAnalysis)

  • Method Details

    • analyse

      public void analyse()