Function walk_through_dead

atomic-core/src/output/alive/retrieve/mod.rs:427–581

Walk through a dead vertex's forward edges to find live successors. In the additive edge model there are no PSEUDO reconnection edges, so the alive-graph traversal must dynamically skip over dead vertices to find live descendants. This walks the dead vertex's BLOCK edges (including deleted ones, since we may need to skip multiple dead vertices in a row) and pushes any live destinations onto the

(
    txn: &T,
    options: &RetrieveOptions,
    owner_parent: GraphNode<NodeId>,
    dead_vertex: GraphNode<NodeId>,
    stack: &mut Vec<VertexId>,
    cache: &mut std::collections::HashMap<GraphNod

/// list so they appear as proper graph children of the upstream alive
/// parent.
fn walk_through_dead<T: GraphTxnT>(
    txn: &T,
    options: &RetrieveOptions,
    owner_parent: GraphNode<NodeId>,
    dead_vertex: GraphNode<NodeId>,
    stack: &mut Vec<VertexId>,
    cache: &mut std::collections::HashMap<GraphNode<NodeId>, VertexId>,
    result: &mut RetrieveResult,
) -> Result<Vec<VertexId>, PristineError> {
    use std::collections::HashSet;
    let mut live_successors: Vec<VertexId> = Vec::new();

    // BFS through dead vertices, recording live ones we encounter.
    //
    // We track three sets separately:
    //   * `dead_visited` — dead vertices we have walked through.  This is
    //     the set that an "alive outsider" check should consult: a dead
    //     vertex `D` is claimed by some alive parent `P` only when `P` is
    //     NOT in this set (i.e. `P` is not part of the dead chain).
    //   * `alive_found`  — alive vertices reached during this walk.  We
    //     remember them only to avoid pushing the same one to the graph
    //     twice, but they must NOT mask the alive-outsider check.
    //   * `seen`         — union, used purely to skip re-visiting the
    //     same vertex during BFS.
    let mut dead_visited: HashSet<GraphNode<NodeId>> = HashSet::new();
    let mut seen: HashSet<GraphNode<NodeId>> = HashSet::new();
    let mut queue: Vec<GraphNode<NodeId>> = vec![dead_vertex];
    seen.insert(dead_vertex);
    dead_visited.insert(dead_vertex);

    while let Some(current) = queue.pop() {
        // Walk current's forward edges (include deleted so we can chain
        // through multiple dead vertices in a row).
        let edges = txn.iter_forward(current, true)?;

        for edge in edges {
            let next_pos = edge.dest;
            let next_vertex = match txn.find_block(next_pos) {
                Ok(v) => v,
                Err(_) => continue,
            };

            if seen.contains(&next_vertex) {
                continue;
            }
            seen.insert(next_vertex);

            // Check change filter
            if !options.passes_filter(next_vertex.change) {
                continue;
            }

            // Is this vertex alive in our view?
            let alive = if options.has_filter() {
                options.is_vertex_alive(txn, next_vertex)?
            } else {
                classify::is_vertex_alive(txn, &next_vertex)?
            };