oxc-project / oxc-project/backlog
Store `Span`s outside AST in a side table?
Nobody has claimed this yet.
- Dominant language
- No language data
- Stars
- 7
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
Making AstKind consistent (https://github.com/oxc-project/oxc/issues/11490) is close to reaching completion, which will open the door to adding NodeId to all AST nodes (https://github.com/oxc-project/oxc/discussions/5689).
Once we have NodeIds stored in AST, we could consider:
- Remove
span: Spanfields from all AST types. - Instead store
Spans in a side table -IndexVec<NodeId, Span>.
The rationale for this change, as I see it, are:
Spanadds 8 bytes to every single AST node type. At a guess they account for 10%-15% of total memory footprint of the AST.Spans are created in the parser, but then barely used until codegen.- By moving
Spans out of AST types, the rest of the AST is more compact in memory. - All the intermediate stages in pipeline (semantic, transform, minify) which don't care about
Spans will benefit from higher CPU cache hit rate while traversing the AST. - Linter also will benefit for same reason. It (mostly) doesn't use
Spans either. - Codegen with source maps, which does use
Spans, uses all of them. It will read them mostly in the same order as they were created in parser, so its pattern of reads from theIndexVec<NodeId, Span>will be largely linear, working from start to end - very efficient cache utilization.
So, in short, I think this change would follow the principle of data-oriented design - store data together which is accessed together.
There are some exceptions, but they all have good alternatives:
- All parts of pipeline use spans for diagnostics. But errors are rare, so these are cold paths - not important.
- Comment attachment in codegen and formatter uses spans. However, once we have
NodeIds in AST, we may well change comment attachment logic to useNodeIds instead. - Various other logic uses spans to compare nodes (e.g. "is this node the left or right side of its parent
BinaryExpression?"). But we will useNodeIds for this instead once we have them. We also haveAddressas an alternative solution, or the possibility of augmentingAstNodesto help with this. We shouldn't be using spans for this.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading the linked AstKind issue and NodeId discussion, then examine how spans are used across parsing, diagnostics, codegen, comment attachment, and formatting. Done would require an agreed design for storing spans outside AST nodes and resolving the listed exceptions.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100