MCPcopy Create free account
hub / github.com/atomicdotdev/atomic / retrieve_graph

Function retrieve_graph

atomic-core/src/output/alive/retrieve/mod.rs:108–486  ·  view source on GitHub ↗

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,
)

Source from the content-addressed store, hash-verified

106/// println!("Retrieved {} vertices", result.graph.len_vertices());
107/// ```
108pub 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);

Calls 15

memo_vertex_aliveFunction · 0.85
walk_through_deadFunction · 0.85
create_alive_vertexFunction · 0.85
attach_deferred_bypassesFunction · 0.85
replacement_rootsFunction · 0.85
push_vertexMethod · 0.80
inode_nodeMethod · 0.80
passes_filterMethod · 0.80
has_filterMethod · 0.80
include_deleted_edgesMethod · 0.80
len_verticesMethod · 0.80