An alternative approach is to just store whitespace and comments as explicit nodes in the syntax tree. This is what IntelliJ and rust-analyzer do.
The benefit of leading-trivia approach is that it gives you statically-shaped AST. A node like BinExpr always has exactly three children, with operator being the second child. With IntelliJ approach, every node can have arbitrary many children, as you can get a series of comments at any position. So, getting a child of a specific type generally requires a linear scan of the children. On the other hand, you don’t need to store null pointers for optional syntactic elements. Additional benefit is that the token struct becomes simpler and smaller, and there are more tokens than internal nodes.
I don’t know which representation is more convenient for the user of the API. IntelliJ model seems intuitive. I haven’t worked with Roslyn model. It does seem that transplanting the trivia together with the token it’s attached to can make some code transformations just work.
My gut tells me that the statically-shaped AST is probably nicer to work with, but if you’re applying visitor-pattern approaches anyways then the intelliJ tooling can just as well give you that same sort of usability.
I imagine that the IntelliJ stuff is heavily based around its IDE needs. But Roslyn has similar requirements to support language servers! I wonder how that plays out in practice. I guess syntax trees never get too deep to where span-scanning isn’t a major issue.
Not sure if they were the first, but Roslyn uses the same approach: https://github.com/dotnet/roslyn/blob/main/docs/wiki/Roslyn-Overview.md#syntax-trivia. Later, Swift did the same: https://github.com/apple/swift/tree/main/lib/Syntax#trivia. Note that Swift’s docs are the best source to learn about design of syntax trees for IDE-like tooling.
An alternative approach is to just store whitespace and comments as explicit nodes in the syntax tree. This is what IntelliJ and rust-analyzer do.
The benefit of leading-trivia approach is that it gives you statically-shaped AST. A node like BinExpr always has exactly three children, with operator being the second child. With IntelliJ approach, every node can have arbitrary many children, as you can get a series of comments at any position. So, getting a child of a specific type generally requires a linear scan of the children. On the other hand, you don’t need to store null pointers for optional syntactic elements. Additional benefit is that the token struct becomes simpler and smaller, and there are more tokens than internal nodes.
I don’t know which representation is more convenient for the user of the API. IntelliJ model seems intuitive. I haven’t worked with Roslyn model. It does seem that transplanting the trivia together with the token it’s attached to can make some code transformations just work.
My gut tells me that the statically-shaped AST is probably nicer to work with, but if you’re applying visitor-pattern approaches anyways then the intelliJ tooling can just as well give you that same sort of usability.
I imagine that the IntelliJ stuff is heavily based around its IDE needs. But Roslyn has similar requirements to support language servers! I wonder how that plays out in practice. I guess syntax trees never get too deep to where span-scanning isn’t a major issue.