rust-analyzer / rust-analyzer Public

Of these, only GreenNodes store the actual data, the other two layers are (non-trivial) views into green tree. Red-green terminology comes from Roslyn (link) and gives the name to the rowan library. Green and syntax nodes are defined in rowan, ast is defined in rust-analyzer.

Syntax trees are a semi-transient data structure. In general, frontend does not keep syntax trees for all files in memory. Instead, it lowers syntax trees to more compact and rigid representation, which is not full-fidelity, but which can be mapped back to a syntax tree if so desired.

GreenNode is a purely-functional tree with arbitrary arity. Conceptually, it is equivalent to the following run of the mill struct:

To reduce the amount of allocations, the GreenNode is a DST, which uses a single allocation for header and children. Thus, it is only usable behind a pointer.

To more compactly store the children, we box both interior nodes and tokens, and represent Either<Arc<Node>, Arc<Token>> as a single pointer with a tag in the last bit.

Leave a Comment