Class LockPrecedenceGraph

java.lang.Object

org.ek9lang.compiler.phase5.lockanalysis.LockPrecedenceGraph

All Implemented Interfaces:

Serializable

public final class LockPrecedenceGraph
extends Object
implements Serializable

Workspace-wide lock-precedence graph used by Phase 5 cycle detection.

Nodes are lock-identity stableId strings (the same FK form used elsewhere in LockAnalysis). Edges record an observed "lockA held when lockB acquired" relationship — i.e. an enter() site on lockB nested inside a MutexKey body protecting lockA. Each edge carries the source location of the inner enter() so cycle diagnostics can point users at the contributing call sites.

Deadlock model: a single nested-different-lock pair (e.g. lockA → lockB with no opposing acquisition anywhere in the program) is safe — there's no acquisition order that another thread could violate. The deadlock condition requires a cycle: lockA → lockB from one call site PLUS lockB → lockA (directly or transitively) from another. The compiler fires E08252 on edges that participate in a strongly-connected component of size ≥ 2 (i.e. real cycles).

Self-loops (lockA → lockA) are not recorded: the same lock reentrant on the same thread is legal (Java's ReentrantLock semantics). The cross-thread variant (same lock across a thread boundary) is handled separately by the C.3 verdict via E08253.

Thread-safety: same model as LockAnalysis — concurrent collection during parallel listener walks, single-threaded consumption afterwards. Uses ConcurrentHashMap for the adjacency map.

See Also:

• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	LockPrecedenceGraph.Edge	One observed nested-enter relationship between two distinct lock identities.

Constructor Summary

Constructors

Constructor	Description
LockPrecedenceGraph()

Method Summary

Modifier and Type	Method	Description
int	edgeCount()
List<LockPrecedenceGraph.Edge>	edgesFrom(String lockId)	All edges leaving the given node (empty if none).
List<LockPrecedenceGraph.Edge>	edgesInCycle(Set<String> cycle)	Edges of the graph whose endpoints both lie in the given cycle — these are the edges that participate in the deadlock-capable acquisition pattern.
List<Set<String>>	findCycles()	Find all strongly-connected components of size ≥ 2 in the graph.
Set<String>	nodes()	All node FQNs appearing as either source or target of any edge.
void	recordEdge(String outerLockId, String innerLockId, IToken innerCallLocation, String outerSiteId)	Record an observed precedence "outer held → inner acquired." Self-loops (outer == inner) are silently ignored — reentrancy on the same thread is legal.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

LockPrecedenceGraph

public LockPrecedenceGraph()

Method Details

recordEdge

public void recordEdge(String outerLockId,
 String innerLockId,
 IToken innerCallLocation,
 String outerSiteId)

Record an observed precedence "outer held → inner acquired." Self-loops (outer == inner) are silently ignored — reentrancy on the same thread is legal.

edgesFrom

public List<LockPrecedenceGraph.Edge> edgesFrom(String lockId)

All edges leaving the given node (empty if none).

nodes

public Set<String> nodes()

All node FQNs appearing as either source or target of any edge.

edgeCount

public int edgeCount()

findCycles

public List<Set<String>> findCycles()

Find all strongly-connected components of size ≥ 2 in the graph. Each non-trivial SCC corresponds to a deadlock-capable cycle: within the SCC every node reaches every other, meaning the acquisition-order constraints conflict.

Uses Tarjan's SCC algorithm — O(V + E), single pass.

Returns:

list of SCCs as sets of lock identity stableIds. Only non-trivial SCCs (size ≥ 2) are returned; singleton SCCs are omitted (no cycle, no deadlock).

edgesInCycle

public List<LockPrecedenceGraph.Edge> edgesInCycle(Set<String> cycle)

Edges of the graph whose endpoints both lie in the given cycle — these are the edges that participate in the deadlock-capable acquisition pattern. Used by C.3 to fire E08252 at each participating inner enter() site with a message linking to the other edges.