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 | |
| 121 | // Add dummy span at index 0 |
| 122 | result.graph.push_vertex(AliveVertex::DUMMY); |
| 123 | cache.insert(GraphNode::BOTTOM, VertexId::DUMMY); |
| 124 | |
| 125 | // Add the root span (inode span) at index 1 |
| 126 | // But only if it passes the change filter |
| 127 | let root_vertex = start_pos.inode_node(); |
| 128 | |
| 129 | // Check if root span passes the change filter |
| 130 | if !options.passes_filter(start_pos.change) { |
| 131 | // Root span is filtered out - return empty graph |
| 132 | result.was_filtered = options.has_filter(); |
| 133 | return Ok(result); |
| 134 | } |
| 135 | |
| 136 | // Track whether a change filter is active so callers can distinguish |
| 137 | // "genuinely empty file" from "file belongs to a different view". |
| 138 | result.was_filtered = options.has_filter(); |
| 139 | |
| 140 | let root_alive = AliveVertex::new(root_vertex); |
| 141 | result.graph.push_vertex(root_alive); |
| 142 | cache.insert(root_vertex, VertexId::new(1)); |
| 143 | |
| 144 | // DFS traversal stack |
| 145 | let mut stack = vec![VertexId::new(1)]; |
| 146 | |
| 147 | // Determine whether iter_forward should include deleted edges. |
| 148 | // When a change filter is active we need to see deleted edges so we can |
| 149 | // decide whether the deletion "has happened" from our view's perspective. |
| 150 | let include_deleted = options.include_deleted_edges(); |
| 151 | |
| 152 | // Deferred bypass attachments: when a vertex has both direct alive |
| 153 | // children AND bypass children (live successors discovered through a |
| 154 | // dead chain), we attach the bypass children to the LAST direct |
| 155 | // child rather than to this vertex. Since that direct child is |
| 156 | // still on the stack and hasn't been processed yet, we record the |
| 157 | // attachment here and apply it when the direct child pops. |
| 158 | let mut pending_bypass: HashMap<VertexId, Vec<VertexId>> = HashMap::new(); |
| 159 | |
| 160 | while let Some(vid) = stack.pop() { |
| 161 | // Check span limit |
| 162 | if let Some(max) = options.max_vertices { |
| 163 | if result.graph.len_vertices() >= max { |
| 164 | result.truncated = true; |
| 165 | break; |