(opt): store syntax node offsets relative to parent so get_children ignores position - #10191
Conversation
This stack of pull requests is managed by Graphite. Learn more about stacking. |
|
This change is |
PR SummaryMedium Risk Overview
Reviewed by Cursor Bugbot for commit 57c5a51. Bugbot is set up for automated code reviews on this repo. Configure here. |
orizi
left a comment
There was a problem hiding this comment.
@orizi reviewed 1 file and all commit messages, and made 1 comment.
Reviewable status:complete! all files reviewed, all discussions resolved (waiting on TomerStarkware).
8be9353 to
711e476
Compare
ae4c9df to
57c5a51
Compare
orizi
left a comment
There was a problem hiding this comment.
@orizi made 1 comment.
Reviewable status: 0 of 2 files reviewed, 1 unresolved discussion (waiting on eytan-starkware and TomerStarkware).
-- commits line 3 at r2:
rebase
…gnores 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.
57c5a51 to
f1247b0
Compare
orizi
left a comment
There was a problem hiding this comment.
@orizi reviewed 2 files and all commit messages, and resolved 1 discussion.
Reviewable status:
Summary
Stores syntax node offsets relative to the parent (computed from the parent green alone, starting at 0) instead of as absolute file offsets. This makes
get_childrendepend only on the green tree, so a structure-preserving edit that merely shifts a subtree no longer re-executes it. The absolute offset is recovered on demand bySyntaxNode::offsetvia a newabsolute_offsettracked query.Type of change
Please check one:
Why is this change needed?
get_childrenread the node's absolute offset to seed its children's offsets, so any edit that shifted a subtree (without changing its structure) invalidatedget_childrenfor the entire tail of the file — O(tail) re-execution for any insert/delete.What was the behavior or documentation before?
Children stored absolute file offsets seeded from their parent's absolute offset. An insert/delete that shifted a subtree invalidated
get_childrenfor the whole tail of the file, even though the subtree's structure was unchanged.What is the behavior or documentation after?
Children store offsets relative to their parent, so
get_childrendepends only on the green tree and is position-independent. The absolute offset is recovered bySyntaxNode::offsetviaabsolute_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_childrenoutput is position-independent and backdatable — an absolute position cached in it would go stale — and as a query it gets revision-aware invalidation and backdating for free.Measured on the
ls_reexecstructural-edit scenario (insert oneconststatement atop a 400-statement body):get_childrenre-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 trivialabsolute_offsetre-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-editfile_contentwave shared by every scenario — both outside this fix's scope.Related issue or discussion (if any)
Part of a stack with #10189 (regression benchmark) and #10190 (child-index-by-kind fix). Requires the stable node ids from #10190 to be effective.
Additional context
The benchmark numbers above come from the scenario added in #10189.