Retrieve the alive graph for a file starting from a position. This function traverses the graph from the given starting position, collecting all alive vertices and their edges into an `AliveGraph`. # Arguments `txn` - The transaction providing graph access `start_pos` - Starting position (typically the file's inode position) `options` - Retrieval options # Returns A `RetrieveResult` containin
(
txn: &T,
start_pos: Position<NodeId>,
options: RetrieveOptions,
)
| 106 | /// println!("Retrieved {} vertices", result.graph.len_vertices()); |
| 107 | /// ``` |
| 108 | pub fn retrieve_graph<T: GraphTxnT>( |
| 109 | txn: &T, |
| 110 | start_pos: Position<NodeId>, |
| 111 | options: RetrieveOptions, |
| 112 | ) -> Result<RetrieveResult, PristineError> { |
| 113 | let mut result = RetrieveResult::new(AliveGraph::new()); |
| 114 | |
| 115 | // Span cache to avoid revisiting - keyed by the actual span, not position. |
| 116 | // This is important because a single position (e.g., position 9) might refer to |
| 117 | // different vertices: an empty inode span V[9:9] or a content span V[9:23]. |
| 118 | // Using the resolved span as the key ensures we visit each unique span once. |
| 119 | let mut cache: HashMap<GraphNode<NodeId>, VertexId> = HashMap::new(); |
| 120 | // Per-retrieval aliveness memo. `is_vertex_alive` iterates the vertex's |
| 121 | // parent edges and resolves causal dominance between them; on a heavily |
| 122 | // edited file the same vertices are re-checked across the main traversal |
| 123 | // and every `walk_through_dead` walk, which is the dominant repeated work. |
| 124 | // Aliveness is a pure function of (txn, options, vertex), so one memo per |
| 125 | // retrieval removes the repetition without changing any verdict. |
| 126 | let mut alive_memo: HashMap<GraphNode<NodeId>, bool> = HashMap::new(); |
| 127 | // Per-retrieval reachability memo for the dead-walk's chain comparisons. |
| 128 | let mut chain_memo: HashMap<(GraphNode<NodeId>, GraphNode<NodeId>), bool> = HashMap::new(); |
| 129 | // Shared causal-dominance memo across every aliveness check in this walk. |
| 130 | let mut dep_memo: HashMap<(NodeId, NodeId), bool> = HashMap::new(); |
| 131 | let mut dead_contexts = std::collections::HashSet::new(); |
| 132 | // A liveness query needs only reachability to any live bytes, independent |
| 133 | // of the owner-specific ordering of bypass edges. Share dead visits across |
| 134 | // root edges so overlapping deleted histories are scanned once. |
| 135 | let mut liveness_dead_seen = std::collections::HashSet::new(); |
| 136 | // Negative reachability proofs are independent of the bypass owner. |
| 137 | // Reuse only fully explored subgraphs with no live successor at all; |
| 138 | // positive walks retain their owner-specific ordering and attachment. |
| 139 | let mut empty_dead_subgraphs = std::collections::HashSet::new(); |
| 140 | // Bypass attachments declined inline because an alternate alive parent |
| 141 | // did not reach the owner in the alive graph built SO FAR; re-checked |
| 142 | // against the complete graph after the traversal (see `DeferredBypass`). |
| 143 | let mut deferred_bypasses: Vec<DeferredBypass> = Vec::new(); |
| 144 | |
| 145 | // Add dummy span at index 0 |
| 146 | result.graph.push_vertex(AliveVertex::DUMMY); |
| 147 | cache.insert(GraphNode::BOTTOM, VertexId::DUMMY); |
| 148 | |
| 149 | // Add the root span (inode span) at index 1 |
| 150 | // But only if it passes the change filter |
| 151 | let root_vertex = start_pos.inode_node(); |
| 152 | |
| 153 | // Check if root span passes the change filter |
| 154 | if !options.passes_filter(start_pos.change) { |
| 155 | // Root span is filtered out - return empty graph |
| 156 | result.was_filtered = options.has_filter(); |
| 157 | return Ok(result); |
| 158 | } |
| 159 | |
| 160 | // Track whether a change filter is active so callers can distinguish |
| 161 | // "genuinely empty file" from "file belongs to a different view". |
| 162 | result.was_filtered = options.has_filter(); |
| 163 | |
| 164 | let root_alive = AliveVertex::new(root_vertex); |
| 165 | result.graph.push_vertex(root_alive); |