| 68 | } |
| 69 | |
| 70 | fn find_block(&self, pos: Position<NodeId>) -> PristineResult<GraphNode<NodeId>> { |
| 71 | // Handle ROOT position specially - ROOT is a virtual span that doesn't |
| 72 | // exist in the database. It represents the repository root and is the |
| 73 | // parent of all top-level files and directories. |
| 74 | if pos.change.is_root() { |
| 75 | return Ok(GraphNode::ROOT); |
| 76 | } |
| 77 | |
| 78 | let table = self.txn.open_multimap_table(GRAPH)?; |
| 79 | |
| 80 | let change_id = pos.change.get(); |
| 81 | let target_pos = pos.pos.get(); |
| 82 | |
| 83 | // Binary-search candidates instead of scanning every vertex of the |
| 84 | // change (the historical full-range scan made each call |
| 85 | // O(change vertices) and every multi-file import quadratic — review |
| 86 | // ::15, 2026-09-16). Within one change the non-empty hunks are |
| 87 | // DISJOINT ranges of that change's contents buffer, so at most one |
| 88 | // non-empty vertex contains a position, and it is the LAST vertex key |
| 89 | // ≤ (pos, u64::MAX). The empty-vertex fallback (the shared |
| 90 | // inode/content start ambiguity, AGENTS.md "Position Ambiguity") is |
| 91 | // an exact-key lookup. Empty vertices coincide with content-span |
| 92 | // starts, so they never hide a containing span from the candidate. |
| 93 | let upper = encode_vertex(change_id, target_pos, u64::MAX); |
| 94 | if let Some((v_change, v_start, v_end)) = table |
| 95 | .range::<&[u8; 24]>(&encode_vertex(change_id, 0, 0)..=&upper)? |
| 96 | .next_back() |
| 97 | .transpose()? |
| 98 | .map(|(key, _values)| decode_vertex(key.value())) |
| 99 | { |
| 100 | if v_change == change_id |
| 101 | && v_start != v_end |
| 102 | && v_start <= target_pos |
| 103 | && target_pos < v_end |
| 104 | { |
| 105 | return Ok(GraphNode { |
| 106 | change: NodeId::new(change_id), |
| 107 | start: ChangePosition::new(v_start), |
| 108 | end: ChangePosition::new(v_end), |
| 109 | }); |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | // Empty-vertex fallback: the exact key (change, pos, pos). |
| 114 | let empty_key = encode_vertex(change_id, target_pos, target_pos); |
| 115 | if try_is_present(table.get(&empty_key)?)? { |
| 116 | return Ok(GraphNode { |
| 117 | change: NodeId::new(change_id), |
| 118 | start: ChangePosition::new(target_pos), |
| 119 | end: ChangePosition::new(target_pos), |
| 120 | }); |
| 121 | } |
| 122 | |
| 123 | Err(PristineError::BlockNotFound { |
| 124 | change: change_id, |
| 125 | pos: target_pos, |
| 126 | }) |
| 127 | } |