Sitelet https://github.com/starkware-libs/cairo/commit/ae4c9df3def1c21cad9e09395c65be0ef97866b6
Skip to content

Commit ae4c9df

Browse files
eytan-starkwareeytan-starkware
committed
(opt): store syntax node offsets relative to parent so get_children ignores position
get_children read the node's absolute offset to seed its children's offsets, so any edit that shifted a subtree (without changing its structure) invalidated get_children for the entire tail of the file — O(tail) re-execution for any insert/delete. Now children store offsets RELATIVE to their parent (computed from the parent green alone, starting at 0), so get_children depends only on the green tree: a structure-preserving edit that merely shifts a subtree no longer re-executes it. The absolute offset is recovered by SyntaxNode::offset via absolute_offset — a tracked query summing the relative offsets up the parent chain, memoized per node (O(1) amortized instead of an O(depth) walk per call; an edit recomputes only the shifted nodes actually queried). It is a salsa query rather than a cache inside node data because get_children output is position-independent and backdatable — an absolute position cached in it would go stale; the query gets revision-aware invalidation and backdating for free. Measured on the ls_reexec structural-edit scenario (insert one const statement atop a 400-statement body): get_children re-executions drop from 1612 to 12 — identical to the end-insert control, i.e. fully position-independent. Total per-edit executions go 4139 -> 2943; of the remainder, 404 are the trivial absolute_offset re-sums for the shifted statements (the control re-executes 4), and the rest is a position-correlated semantic wave (impl/trait-signature queries) plus the per-edit file_content wave shared by every scenario — both outside this fix's scope. Requires the stable node ids from the child-index fix below it to be effective.
1 parent 8be9353 commit ae4c9df

1 file changed

Lines changed: 27 additions & 10 deletions

File tree

  • crates/cairo-lang-syntax/src/node

‎crates/cairo-lang-syntax/src/node/mod.rs‎

Lines changed: 27 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -58,10 +58,11 @@ pub enum SyntaxNodeId<'db> {
5858
struct SyntaxNodeData<'a> {
5959
#[tracked]
6060
green: GreenId<'a>,
61-
/// Number of characters from the beginning of the file to the start of the span of this
62-
/// syntax subtree.
61+
/// This node's span start relative to its parent's (for a root, to the file start). Keeping
62+
/// it parent-relative makes `get_children` a pure function of the green tree, independent of
63+
/// the node's absolute position. Recover the absolute offset via [`SyntaxNode::offset`].
6364
#[tracked]
64-
offset: TextOffset,
65+
offset_in_parent: TextOffset,
6566
/// Unique identifier for this node.
6667
#[returns(ref)]
6768
id: SyntaxNodeId<'a>,
@@ -77,12 +78,25 @@ impl<'db> SyntaxNodeData<'db> {
7778
}
7879
}
7980

81+
/// The absolute offset of the node from the beginning of the file: its offset within its parent
82+
/// plus the (recursively memoized) absolute offset of the parent. A tracked query rather than a
83+
/// cache inside the node data, as a cache would go stale when a shifted-but-unchanged subtree is
84+
/// backdated.
85+
#[salsa::tracked]
86+
fn absolute_offset<'db>(db: &'db dyn Database, data: SyntaxNodeData<'db>) -> TextOffset {
87+
match data.parent(db) {
88+
Some(parent) => absolute_offset(db, parent.data)
89+
.add_width(data.offset_in_parent(db) - TextOffset::START),
90+
None => data.offset_in_parent(db),
91+
}
92+
}
93+
8094
impl<'db> cairo_lang_debug::DebugWithDb<'db> for SyntaxNodeData<'db> {
8195
type Db = dyn Database;
8296
fn fmt(&self, f: &mut std::fmt::Formatter<'_>, db: &'db Self::Db) -> std::fmt::Result {
8397
f.debug_struct("SyntaxNode")
8498
.field("green", &self.green(db).debug(db))
85-
.field("offset", &self.offset(db))
99+
.field("offset_in_parent", &self.offset_in_parent(db))
86100
.field("id", &self.id(db).debug(db))
87101
.finish()
88102
}
@@ -119,9 +133,9 @@ impl<'db> cairo_lang_debug::DebugWithDb<'db> for SyntaxNode<'db> {
119133
}
120134

121135
impl<'db> SyntaxNode<'db> {
122-
/// Gets the offset of this syntax node from the beginning of the file.
136+
/// Gets the absolute offset of this syntax node from the beginning of the file.
123137
pub fn offset(self, db: &'db dyn Database) -> TextOffset {
124-
self.data.offset(db)
138+
absolute_offset(db, self.data)
125139
}
126140

127141
/// Gets the parent syntax node, if any.
@@ -206,19 +220,20 @@ impl<'db> SyntaxNode<'db> {
206220
}
207221
}
208222

209-
/// Creates a new syntax node.
223+
/// Creates a new syntax node. `offset_in_parent` must be relative to the parent (absolute for a
224+
/// root) — see `SyntaxNodeData::offset_in_parent`.
210225
pub fn new_syntax_node<'db>(
211226
db: &'db dyn Database,
212227
green: GreenId<'db>,
213-
offset: TextOffset,
228+
offset_in_parent: TextOffset,
214229
id: SyntaxNodeId<'db>,
215230
kind: SyntaxKind,
216231
) -> SyntaxNode<'db> {
217232
let (parent, parent_kind) = match &id {
218233
SyntaxNodeId::Child { parent, .. } => (Some(parent.data), Some(parent.kind)),
219234
SyntaxNodeId::Root(_) => (None, None),
220235
};
221-
let data = SyntaxNodeData::new(db, green, offset, id);
236+
let data = SyntaxNodeData::new(db, green, offset_in_parent, id);
222237
SyntaxNode { data, parent, kind, parent_kind }
223238
}
224239

@@ -338,7 +353,9 @@ impl<'a> SyntaxNode<'a> {
338353

339354
/// Implementation of [SyntaxNode::get_children].
340355
pub(crate) fn get_children_impl(&self, db: &'a dyn Database) -> Vec<SyntaxNode<'a>> {
341-
let mut offset = self.offset(db);
356+
// Children offsets are relative to this node, so seeding from `TextOffset::START` (rather
357+
// than `self.offset(db)`) keeps `get_children` a pure function of the green tree.
358+
let mut offset = TextOffset::START;
342359
let self_green = self.green_node(db);
343360
let children = self_green.children();
344361
let mut res: Vec<SyntaxNode<'_>> = Vec::with_capacity(children.len());

0 commit comments

Comments
 (0)