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

Method find_block_end

atomic-core/src/pristine/txn/write/graph.rs:148–223  ·  view source on GitHub ↗

Find a block that ends at or after the given position. This is used for predecessors resolution where we need to find the span that ENDS at a position, not one that contains it. This is important when creating edges from an existing span to a new one. # Arguments `pos` - The position to find (typically the end of a context span) # Returns The span that ends at or after the given position, or

(&self, pos: Position<NodeId>)

Source from the content-addressed store, hash-verified

146 /// - Empty vertices (start == end == pos) are matched exactly
147 /// - For non-empty vertices, finds one where start < pos <= end
148 fn find_block_end(&self, pos: Position<NodeId>) -> PristineResult<GraphNode<NodeId>> {
149 // Handle ROOT position specially
150 if pos.change.is_root() {
151 return Ok(GraphNode::ROOT);
152 }
153
154 let table = self.txn.open_multimap_table(GRAPH)?;
155
156 let change_id = pos.change.get();
157 let target_pos = pos.pos.get();
158
159 // FIRST: Check for empty span at exact position using direct lookup.
160 // This is important because empty vertices like inode markers (e.g., V[9:9])
161 // must be found when predecessors references position 9, even if there's
162 // another span like V[0:9] that also ends at position 9.
163 // Without this direct lookup, iteration would return V[0:9] first since
164 // it has a lower start position.
165 let empty_key = encode_vertex(change_id, target_pos, target_pos);
166 if try_is_present(table.get(&empty_key)?)? {
167 return Ok(GraphNode {
168 change: NodeId::new(change_id),
169 start: ChangePosition::new(target_pos),
170 end: ChangePosition::new(target_pos),
171 });
172 }
173
174 // SECOND: binary-search the vertices that end at or contain this
175 // position (the historical full-range scan made each call
176 // O(change vertices) and every multi-file import quadratic — review
177 // ::15, 2026-09-16). Under within-change hunk disjointness:
178 // - a span ENDING at pos (unique when it exists) is the span
179 // containing pos-1, so it is the last vertex key ≤ (pos-1, MAX);
180 // - a span CONTAINING pos (unique when it exists) is the last vertex
181 // key ≤ (pos, MAX).
182 // An ends-at-pos span starts strictly before any contains-pos span
183 // (which must start at pos exactly), so checking ends-at-pos first
184 // preserves the historical first-match-in-key-order semantics.
185 if target_pos > 0 {
186 let before_upper = encode_vertex(change_id, target_pos - 1, u64::MAX);
187 if let Some((v_change, v_start, v_end)) = table
188 .range::<&[u8; 24]>(&encode_vertex(change_id, 0, 0)..=&before_upper)?
189 .next_back()
190 .transpose()?
191 .map(|(key, _values)| decode_vertex(key.value()))
192 {
193 if v_change == change_id && v_end == target_pos && v_start < v_end {
194 return Ok(GraphNode {
195 change: NodeId::new(change_id),
196 start: ChangePosition::new(v_start),
197 end: ChangePosition::new(v_end),
198 });
199 }
200 }
201 }
202
203 let contains_upper = encode_vertex(change_id, target_pos, u64::MAX);
204 if let Some((v_change, v_start, v_end)) = table
205 .range::<&[u8; 24]>(&encode_vertex(change_id, 0, 0)..=&contains_upper)?

Calls 6

encode_vertexFunction · 0.85
try_is_presentFunction · 0.85
decode_vertexFunction · 0.85
valueMethod · 0.80
getMethod · 0.65
is_rootMethod · 0.45