Use fixed slots for the children

[MichaReiser]

Thread to discuss the change around using fixed slots to store the children.

RSLint and rust-analyzer only store nodes or tokens if they've been present in the source file. Let's take the following example of a for statement that only has a condition but misses the init and update nodes.

for (;i < 10;) {
}

RSLint generates the following CST (ignoring trivia):

script:
  - for-stmt:
    - for-keyword
    - l-paren    #// <-- No ForInit after the l-paren
    - semicolon  
    - for-test:
      - binary-expression:
        - name-ref:
          - ident(test)
        - l-angle 
        - literal
          - number(10)
    - semicolon 
    - r-paren
    - block

The downside of not storing missing (even optional) nodes is that accessing a particular field requires iterating over the children of a node to find its position. For example, the for-test is the 4th element if the for-loop has no for-init but is the 5th element otherwise.

The CST can guarantee fixed positions of its children if missing optional or mandatory children are marked as missing inside its children collection. There are multiple ways to do so, some options are:

• Storing None for missing children
• Using a fake missing node/token
• Creating the missing nodes and tokens and flag them as "missing"
• Use an additional bitmask to encode which nodes are present or missing

script:
  - for-stmt:
    - for-keyword
    - l-paren
    - None # <<<
    - semicolon
    - for-test:
      - binary-expression:
        - name-ref:
          - ident(test)
        - l-angle 
        - literal:
          - number(10)
    - semicolon 
    - None # <<<
    - r-paren
    - block

Storing missing elements increases memory consumption because the data structure must encode the information whatever an element is present or missing. We explored different solutions, including bitflags, to mark present and missing elements to keep the overhead to a minimum.

From #1718

[MichaReiser]

I think I finally got my head around how this could work:

• Introduce a new SyntaxKind::List
• The parser generates a list node whenever the grammar has a T* or (...)* rule (the latter is required for lists that are separated by a token). That's all the changes needed in the parser and sink
• Create an AstList<N> which is a lightweight view over a SyntaxNode that guarantees that the children are nodes of type N. It mainly exposes a different API (also limited) compared to the SyntaxNode. Possible operations are iter() -> Iterable<N>, len() , as well as mutation APIs.
• Create an AstSeparatedList<N> which is a special list representing nodes that are separated by a specific token. Array elements are one use case for a separated list. The separated list is also a thin wrapper around a syntax node and defines operations like iter() -> Iterable<Element<N>> nodes() -> Iterable<Option<N>>, separators() -> Iterable<SyntaxToken>, trailing_separator() -> Option<SyntaxToken>, etc. See SeparatedList for a prototyped solution.
• The source gen uses AstList if the grammar defines a T* child, and AstSeparatedList when the grammar has a (T (',' T)* ','?) child

One thing left to verify is if SyntaxNodes are aware of their absolute position. That would be problematic because it requires computing the full span of all preceding children... (which requires iterating over all children). I did a closer look at this and will post an update tomorrow.

[ematipico]

I really like the introduction of AstSeparatedList! It really makes sense and it's definitely portable in various languages.

[MichaReiser]

I'm glad you like it :)

I started working on the AstList but believe that AstNodeList is a better name to be explicit that it's a list of homogenous nodes whereas AstSepartedList is a list of nodes separated by tokens.

[MichaReiser]

I took a look at how and when rowan computes the offsets and how using fixed slots for children improves the runtime performance. It's not as bad as I thought :)

Let's have a look at how child SyntaxNodes are resolved in rowan today using the following if statement (I'm going to ignore trivia):

if (true) {
  console.log("Test");
}

This parses to (ignoring the if's body as we're only looking at the if statement)

if-stmt
  - if-token
  - (
  - bool-literal
    - true-kw
  - )
  - block
     - {
     - list 
         - stmt(...)
     - }

A consumer could use the if as follow

  let if_stmt = ...;
  
  match if_stmt.condition() {
    ...
  }
  
  match if_stmt.cons() {
    ..
  }

Current rowan uses iteration to find a child. That means that rowan iterates over the GreenElements to find the if's condition and its cons, skipping tokens but constructing SyntaxNodes for all nodes (iterating over token or elements creates SyntaxToken/Node for every visited element).

• condition: Iterates over the green elements, skipping tokens. In this case, only one SyntaxNode gets created because all preceding siblings are tokens.
• consequence: Re-creates the SyntaxNode for the condition to then creates the SyntaxNode for the consequence.

That means, that we create n SyntaxNodes n times if a custom passes visits all children of a node only containing node children (regardless if we visit from left to right or right to left). This isn't too bad because creating SyntaxNode's is relatively cheap, but it's not entirely free. Using fixed slots for the children will allow us to retrieve a child without having to construct Syntax* for the preceding children first.

Now, what about the offsets? My initial fear was that the rowan computes the offset of a SyntaxNode by iterating over all preceding siblings adding their width to the offset of the parent (which would be O(n) for the last child). However, this isn't the case. Rowan stores the relative offset in the GreenChild data structure. Meaning, they get computed once during construction (parsing).

tools/crates/rome_rowan/src/green/node.rs

Lines 225 to 232 in 6799f74

	let children = children.into_iter().map(|el| {
	let rel_offset = text_len;
	text_len += el.text_len();
	match el {
	NodeOrToken::Node(node) => GreenChild::Node { rel_offset, node },
	NodeOrToken::Token(token) => GreenChild::Token { rel_offset, token },
	}
	});

Does that mean it's a happy ending after all? Indeed, it is! Retrieving a slot at position n can be implemented with constant time because the parent offset and the child's relative offset are pre-computed and, therefore, can be retrieved in constant time (parent.offset() + green_child.rel_offset)

I would recommend that we rename GreenChild to GreenSlot that can either contain an Element or a Node (and, if we're lazy, be Empty but that's wasting 16 byte for each missing node).

Note: And how does it work in Roslyn?

Roslyn caches most SyntaxNodes which allows them to efficiently compute the offset (worst case still O(n) but they don't pay for the calculation during the construction of the syntax node).

https://github.com/dotnet/roslyn/blob/a883f5d9db3ba7cb80e43b4db6c90f77bf32fcca/src/Compilers/Core/Portable/Syntax/SyntaxNode.cs#L536-L564

Their algorithm computes the relative offset from the parent and starts from one slot before the queried slot:

• It first tests if it has a cached SyntaxNode for the current slot. If yes -> get the offset from the cached SyntaxNode
• Compute the "width" of the node and add it to the relative offset. Now recurse and compute the offset of the slot at position current - 1

This works relatively well if you look at the if stmt example from aboth because passes tend to visit the children in the execution order (from left to right, or from lowest to highest index).

• condition: None of the children is cached. The implementation adds the offsets of the '(' and then the 'if' and adds them to the cached offset of the if statement (O(2)).
• consequence: That's where the caching comes into play. The algorithm doesn't need to add the offsets all the way back to the if keyword because it can stop at the cached condition that knows its relative offset from the start.

Neat, isn't it. However, adopting this approach would require to cache our SyntaxNodes. Something that isn't on our roadmap right now.

[MichaReiser]

OK, implementing this change turned out to be a bit more complicated than I expected. Or more precisely, we have multiple options, all coming with different ups and downs.

Option A: Transparent List Node

This is what Roslyn's doing. It uses a special ListKind that marks GreenNodes as lists. It then has special SyntaxList, SyntaxList<T> types on top. What's special is that Roslyn' models the list as transparent:

• calling ancestors and parent() skips the list node. It instead goes from the list's element to the list's parent
• calling children, first_node etc. traverses into lists. So, calling array.children_and_tokens() returns the [ and ] token but also all children of the array element list.

Advantages

• Hides the fact that we use list nodes to achieve fixed slots from the API (expected result for tests won't change)
• Iterating over all elements in a tree skips Lists

Disadvantages

• Requires changes to the unsafe memory management of rowan and we need to do additional book-keeping to know which is the "owning" parent. I don't feel comfortable building this into rowan with its mutable API in place (would propose removing it for now)
• A single "index" is no longer sufficient to uniquely identify the position of a node. It must now be a combination of the "parent" and "list" slot, where the second is optional.
• Requires new GreenList type.

Option B: Non-transparent SyntaxList

Same as Option A but doesn't rewire the parent of list elements nor does it iterate into lists when iterating over children (or siblings etc).

Advantages

• API is explicit that a child can be a Node, Token or a `List.
• Option to implement a custom "debug" format for lists

Disadvantages

• The return type of parent, ancestors etc. must now be typed as Option<NodeOrList> .
• Still requires to extend rowans cursor::Syntax* memory management code
• Expected output of integration tests change

Option C: AST List

Introduces the concept of lists on the AST level as nice views over a SyntaxNode.

Advantages

• Straightforward to implement. Only requires changing the AST codegen to wrap SyntaxNodes as Lists if the child type is T*
• Matches other AST types with the exception that it is a polymorph AST node-type

Disadvantages

• List nodes get passed to visit_node functions or are returned when e.g. calling descendants on a node.
• AstList<N> can't implement can_cast nor cast because it's not possible to determine if the list contains N nodes if the list is empty (would be legit if lists are read-only).
• Weird that users must manually cast a SyntaxNode to a SyntaxList if they want to operate on a list.
• Expected output for all tests changes because the tree now contains intermediate List nodes.

I'm currently leaning towards AST Lists because it's the most straightforward to implement.

[yassere]

For Option C, is the list just a normal green node under the hood?

AstList can't implement can_cast nor cast because it's not possible to determine if the list contains N nodes if the list is empty (would be legit if lists are read-only).

If a list contains no elements, would it be valid to model that as a non-existent list node rather than an empty list node?

I'm not sure how relevant this is to us, but I noticed this comment in Roslyn about there being no such thing as an empty green list.

[MichaReiser]

For Option C, is the list just a normal green node under the hood?

Yes, the list is just a normal GreenNode, even a normal SyntaxNode, under the hood.

If a list contains no elements, would it be valid to model that as a non-existent list node rather than an empty list node?

Interesting finding and something I haven't thought about yet. We would need to have some special handling on the parser to emit a missing node instead of an empty list if no elements have been added.

But I'm not sure if it solves the casting problem. It's not possible to tell two lists apart that only contain a single element. Is it a list over nodes or an AstSeparatedList but without a trailing separator?

I currently lean towards Option C and maybe move toward Option A if we find it too restrictive or cumbersome to use.

[yassere]

Is it a list over nodes or an AstSeparatedList but without a trailing separator?

Would the parser always know that from context while constructing the node?

There's probably a better solution for this particular problem, but do we want to consider adding a u8 of bitflags to green nodes if we're finding that it would be useful to encode several extra bits of information?

I currently lean towards Option C and maybe move toward Option A if we find it too restrictive or cumbersome to use.

That sounds good to me.

[ematipico]

I am also leaning towards Option C for the simple fact that I would prefer to not use the unsafe memory management system used by rowan. I would remove it in the future if possible (the library cstree has done, we might want to borrow their ideas).

[MichaReiser]

Would the parser always know that from context while constructing the node?

There's probably a better solution for this particular problem, but do we want to consider adding a u8 of bitflags to green nodes if we're finding that it would be useful to encode several extra bits of information?

The parser knows and the AST nodes know as well. I guess we could just define another SyntaxKind to keep the two lists apart. It would then be possible to create a SeparatedSyntaxList from a SyntaxNode. Casting into T should then be possible. Casting an empty list to List<T> is safe as long as we don't allow in-place mutations.