Function tarjan_visit

atomic-core/src/output/alive/order.rs:413–518

Iterative Tarjan visit function. Equivalent to the classic recursive Tarjan's SCC algorithm, but uses an explicit work stack instead of the call stack. This avoids stack overflow for files with tens of thousands of vertices.

(
    graph: &mut AliveGraph,
    start: VertexId,
    state: &mut TarjanState,
    result: &mut OrderResult,
)

/// an explicit work stack instead of the call stack.  This avoids stack
/// overflow for files with tens of thousands of vertices.
fn tarjan_visit(
    graph: &mut AliveGraph,
    start: VertexId,
    state: &mut TarjanState,
    result: &mut OrderResult,
) {
    let mut work: Vec<TarjanFrame> = Vec::new();

    // Initialize the start vertex
    {
        let vertex = graph.vertex_mut(start);
        vertex.index = state.index;
        vertex.lowlink = state.index;
        vertex.mark_visited();
        vertex.push_stack();
    }
    state.index += 1;
    state.stack.push(start);

    let children: Vec<VertexId> = graph
        .children(start)
        .map(|(_, child)| *child)
        .filter(|c| !c.is_dummy())
        .collect();
    work.push(TarjanFrame {
        v: start,
        children,
        child_idx: 0,
    });

    while let Some(frame) = work.last_mut() {
        if frame.child_idx < frame.children.len() {
            let w = frame.children[frame.child_idx];
            frame.child_idx += 1;

            let w_visited = graph.get_vertex(w).is_visited();
            let w_on_stack = graph.get_vertex(w).is_on_stack();

            if !w_visited {
                // Initialize w and push a new frame (replaces recursive call)
                {
                    let vertex = graph.vertex_mut(w);
                    vertex.index = state.index;
                    vertex.lowlink = state.index;
                    vertex.mark_visited();
                    vertex.push_stack();
                }
                state.index += 1;
                state.stack.push(w);

                let w_children: Vec<VertexId> = graph
                    .children(w)
                    .map(|(_, child)| *child)
                    .filter(|c| !c.is_dummy())
                    .collect();
                work.push(TarjanFrame {
                    v: w,
                    children: w_children,