Why does the Rust compiler use TokenTree instead of flat token streams?
Hi! I'm writing a compiler and a recursive descent parser. For inspiration, I looked at what rustc does for parsing, and found out that the lexer produces not just a regular old stream of tokens, but a sequence of TokenTrees. Essentially, they are tokens, but with each group of braces (round, square, or curly) starting a subtree.
Initially it looked a great idea, and I implemented the same in my lexer, but later realized that it's not too convenient for actual parsing. With a plain token stream my recursive descent parsing functions would just advance the "next token" position and call each other recursively: e.g. parseFunctionDefinition consumes an IdentifierToken for a function name, an OpenBraceToken, and then delegates to parseArgumentList(...).
With TokenTrees (group tokens), it's slightly more complicated. In the example above, parseFunctionDefinition would have to accept a BraceTokenGroup TokenTree, extract its children, call the general parse(tokens) routine recursively, which would also initialize a new parser state, and only then get the argument list. It's not serious complexity, but it's a bit of performance overhead, and even makes the code slightly longer in my implementation.
Am I misusing TokenTrees somehow? What does the Rust compiler gain by using them?
Thanks!