Alternative CST implementations

[axelkar]

toml-rs/toml#163 (comment)

^^^ TL;DR: strongly-typed (literally modeled with structs and enums) CSTs and bump allocation

[ChayimFriedman2]

See #6584. TL;DR: We'd love to switch rowan (or improve it) to something more performant, but mutable trees are a roadblocker. We're in the process of getting rid of them.

[axelkar]

Mutable trees just make it very hard to support this trivia model or fixed nodes.

What are fixed nodes?

Assists are sometimes indeed easier to express with mutable trees (which was the original motivation AFAIK), but you can look at what our ongoing migration does (see #15710), which is basically what Roslyn does.

That's really interesting. Isn't that issue only about the red/syntax tree? Is mutability in green trees as bad? Could you just make a path (Vec<usize> for recursively indexing children, usize for index in depth-first traversal, etc.) in the red tree, and translate it into a mutable green tree?

How does this translate to bump/arena allocation or laying the tree flat? Has it been considered in r-a? Since all nodes are the same size, I'd think that it's perfect. But actually the references to children would have to be stored in dynamic heap allocations... Not sure.

[ChayimFriedman2]

What are fixed nodes?

What you called typed nodes, but they are still untyped behind the cover, just that you know that e.g. to get the opening brace you look at the second token, not loop over the children and find the token with token kind of opening brace (as we do currently).

Isn't that issue only about the red/syntax tree?

FWIW we also regret the green/red tree split 😃 the motivation for it is faster parsing, but it's just not a bottleneck for rust-analyzer.

How does this translate to bump/arena allocation or laying the tree flat? Has it been considered in r-a? Since all nodes are the same size, I'd think that it's perfect. But actually the references to children would have to be stored in dynamic heap allocations... Not sure.

I actually have a local branch implementing that (and even posted it in Zulip in the past) and it shows some nice benefits, however I wanted to wait for the mutable tree migration then we change rowan as much as we need.

[axelkar]

What are fixed nodes?

What you called typed nodes, but they are still untyped behind the cover, just that you know that e.g. to get the opening brace you look at the second token, not loop over the children and find the token with token kind of opening brace (as we do currently).

How would that work in an error recovery scenario? Would the parser insert e.g. a fake opening brace token?

FWIW we also regret the green/red tree split 😃 the motivation for it is faster parsing, but it's just not a bottleneck for rust-analyzer.

Is there an alternative to the green/red tree split? Doubly-linked trees?

I actually have a local branch implementing that (and even posted it in Zulip in the past) and it shows some nice benefits, however I wanted to wait for the mutable tree migration then we change rowan as much as we need.

Wow! Do you have a link to the Zulip thread?

[ChayimFriedman2]

How would that work in an error recovery scenario? Would the parser insert e.g. a fake opening brace token?

All nodes are still optional, just in fixed position.

Is there an alternative to the green/red tree split? Doubly-linked trees?

Just simple trees.

Wow! Do you have a link to the Zulip thread?

#t-compiler/rust-analyzer > Rowan and caching

Although I didn't seem to link to branch there, that's https://github.com/ChayimFriedman2/rowan/tree/no-cache.

[axelkar]

Just simple trees.

Oh right, accessing the stack to reference parent nodes, or having a pointer there as I tried to describe with the wrong terminology.

Thanks!