Function dominators 

pub fn dominators(
    graph: &SqliteGraph,
    entry: i64,
) -> Result<DominatorResult, SqliteGraphError>

Computes dominators and immediate dominators for a CFG entry node.

Uses Cooper et al.’s simple_fast iterative algorithm (2001) to compute:

• Full dominance sets: for each node, all nodes that dominate it
• Immediate dominator tree: each node’s closest strict dominator

Arguments

• graph - The control flow graph to analyze
• entry - The entry node ID (must exist in graph)

Returns

DominatorResult containing dominance sets and immediate dominator tree.

Algorithm Steps

1. Get all nodes: Fetch all entity IDs from the graph
2. Initialize: Each node dominates all nodes (optimistic), entry dominates only itself
3. Compute reverse postorder: DFS from entry, process nodes in postorder
4. Iterate to fixed point:
   • For each node in reverse postorder (except entry):
     • Intersect all predecessors’ dominator sets
     • Union with {node} (node dominates itself)
     • Update if changed
5. Extract immediate dominators: Find closest strict dominator for each node

Complexity

• Time: O(N²) worst case, O(E) to O(N log N) in practice
• Space: O(N²) for dominance sets

Error Handling

• Returns SqliteGraphError::NotFound if entry node doesn’t exist
• Handles unreachable nodes gracefully (they have empty/undefined dominators)
• Has iteration limit (1000) to prevent infinite loops

Example

use sqlitegraph::{SqliteGraph, algo::dominators};

let graph = SqliteGraph::open_in_memory()?;
// ... build CFG ...

let result = dominators(&graph, 0)?;

// Check entry dominates all reachable nodes
for &node in result.dom.keys() {
    assert!(result.dominates(0, node));
}

// Immediate dominator forms a tree
assert_eq!(result.immediate_dominator(0), None);