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