Function natural_loops 

pub fn natural_loops(
    graph: &SqliteGraph,
    dom_result: &DominatorResult,
) -> Result<NaturalLoopsResult, SqliteGraphError>

Computes natural loops by finding back-edges where header dominates tail.

A natural loop is identified by a back-edge (tail -> header) where the header dominates the tail. Multiple back-edges to the same header are grouped into a single loop.

Arguments

• graph - The control flow graph to analyze
• dom_result - Dominator computation result (must include dominates() method)

Returns

NaturalLoopsResult containing all detected natural loops.

Algorithm

1. Find back-edges: For each edge (tail, header) in the graph:

   • Check if dom_result.dominates(header, tail) is true
   • If yes, this is a back-edge

2. Group by header: All back-edges to the same header form one loop

3. Compute loop body: For each back-edge:

   • DFS from tail, add all reachable nodes except header
   • Union with existing body for that header

Complexity

• Time: O(E * N) for back-edge check, O(E) for loop body computation
• Space: O(E) for storing loop bodies

Where:

• E = number of edges
• N = number of vertices

Irreducible CFGs

Irreducible CFGs (cycles without dominance) return empty loops for those cycles. This method does NOT produce false positives.

Error Handling

• Returns empty result for empty graphs
• Handles unreachable nodes gracefully (skips edges from unreachable nodes)
• Handles single-node graphs (no loops possible)

Example

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

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

let dom_result = dominators(&graph, entry)?;
let loops = natural_loops(&graph, &dom_result)?;

println!("Found {} natural loops", loops.count());
for (header, loop_) in loops.iter() {
    println!("  Loop {}: {} nodes, {} back-edges",
             header, loop_.size(), loop_.back_edge_count());
}