Implement converting an AST to a token tree

[alexcrichton]

Updated description

First implemented in #43230 the compiler can now tokenize a few AST nodes when necessary losslessly from the original token stream. Currently, however, this is somewhat buggy:

• It only happens for items in certain situations (aka no inner attributes). The consequence of this is that more and more attributed items will have invalid span information when sent to procedural macros.
• We don't invalidate the cache when later changing the item. The consequence of this is that procedural macros will receive a buggy view of what the AST node actually represents.

The "real bug" here is that we haven't actually implemented this ticket. The initial implementation in #43230 was effectively just a heuristic, and not even a great one! As a result we still need the ability basically to losslessly tokenize an AST node back to its original set of tokens.

Some bugs that arise from this are:

• Usage of #[cfg] modifies the AST but doesn't invalidate the cache -- #48644
• Modules with attributes disagree on what their internal tokens are -- #47627
• macro_rules! and procedural macros don't play well together -- #49846
• Invoking a macro with brackets loses span information -- #50840

Original Description

There's an associated FIXME in the code right now, and to fix this we'll need to implement tokenization of an AST node. Right now the thinking of how to implement this is to save all TokenStream instances adjacent to an AST node, and use that instead of converting back into a token stream

cc @dtolnay, @nrc, @jseyfried

[dtolnay]

Unfortunately no matter how we slice it this is a very difficult issue :(

@alexcrichton or @petrochenkov would it be possible to make an order of magnitude estimate of effort for a real fix? Multiple person-weeks, multiple months, most of a year?

Does most of the difficulty come from performance implications? I imagine the naive fix of making the AST look more like Syn's AST where every token is individually represented would be pretty bad for compiler performance.

I've been hitting this issue over and over and over since it was filed. It wasn't so bad with only derive macros where the symptom was usually just error messages being printed in the wrong place, but now with attribute macros and function-like macros I often find it totally impossible to build composable macros (as seen in #57207) and the consequence of losing spans is no longer cosmetic, it is that code that should compile doesn't compile.

[petrochenkov]

@dtolnay
I think we should start with attaching associated token streams to all AST fragments that can be used as interpolated tokens in macros (the list can be found in enum Nonterminal), like it's already done for ast::Item. This shouldn't require much time.
(Note, that significant part of enum Nonterminal is used only for legacy quasi-quoting, that's being removed right now.)

This may regress performance of expansion-heavy compilation by few percent, but correctness seems more important and this can be optimized later.
We need to start with attaching tokens to ast::Expr and running benchmarks.

---

Tokens attached to non-terminals will fix the decl macro issues, but not #[cfg] or inner attributes.
Longer term we need some dual AST/tokens representation with cfgs, built-in derives and other compiler transformations correctly transforming both parts.

Alternatively, AST as it exists now would only be created after expansion, and only tokens + things necessary for expansion, like attribute targets, would exist before that (unfortunately, too much is needed to resolve and expand an attribute).
Or some hybrid using AST only for expanded parts and being gradually folded from token-only to AST-only during expansion.
That's some design work that requires a focused person who knows things to sit and work through the design and proof-of-concept implementation.
I have no idea how much time it would take for me personally, I never did this kind of high-level work.

[dtolnay]

Thanks! That's very helpful.

That's some design work that requires a focused person who knows things to sit and work through the design and proof-of-concept implementation.
I have no idea how much time it would take for me personally, I never did this kind of high-level work.

Let's try to find the right person to at least be thinking passively about this problem, or else it will keep sitting here racking up mentions as every procedural macro library hits it. Would @eddyb be the most appropriate person?

[petrochenkov]

cc @matklad who was also interested in an alternative AST.

[matklad]

Thanks for the ping @petrochenkov! It's interesting that I am experimenting with macro expansion in rust-analyzer in this very moment :)

I don't have much expertise here: I don't really know how rust macros actually work, and have taken only a cursory look at the spans/syntax context infrastructure. Below are my random thoughts about ast/token tree conversion in the context of IDEs:

In rust-analyzer, the syntax trees are not based on token trees (in IDE context, braces are not always balanced, and you need to account for trivia, etc). My current plan is to make token-trees strictly a macro-specific interface and materialize them only when expanding macro invocations. And, because rust-analyzer syntax trees are pretty heavy weight, I also want (rust-analyzer/rust-analyzer#386) to introduce a "post-expansion" AST based on more traditional hierarchy-of-enums representation.

Longer term we need some dual AST/tokens representation with cfgs, built-in derives and other compiler transformations correctly transforming both parts.

One way to achieve that would be libsyntax2 style tree, whose "real" representation is a sequence of token trees, and where AST nodes don't store data themselves besides pointers into the token tree.

[alexcrichton]

I think we probably just haven't put enough weight on this issue yet because it wasn't really all the pressing earlier, but I definitely agree with @dtolnay that it's far more pressing now!

I've always thought that the hard part of this is that we'd basically have to make libsyntax's AST looks like syn's, which I figured was a monumental task given the size and usage of libsyntax. I never really considered the performance implications, but I wouldn't be surprised if it had more than a few regressions.

Thinking on this for a bit though, we may be able to get to a more short-term solution. Up to now #[cfg] is the only (AFAIK) extension which actually modifies the AST pre-expansion. If that's true, then I think we can take a hybrid libsyntax/syn-like approach. We could perhaps say that all composite structures, those which can be internally #[cfg]'d, have the ability to generate their token stream. They do this by iterating over their components and recursively generating token streams. All terminal nodes have cached token streams from the parser (like ast::Item does today).

A strategy like that, which is specific to #[cfg] and falls apart if something else modifies the AST, may be an order of magnitude less work than "make the entire AST syn-like". I haven't thought this through too much though, and the numerous locations we can place #[cfg] may effectively mean that we're just implementing a ToTokens trait for the whole AST anyway.

In any case the best way forward with this I think is to try to brainstorm a bit to figure out a few possibilities of what a "reasonable" solution might look like, and then bring this up with the broader compiler team because it has a lot of implications on the compiler!

[dtolnay]

How feasible is it to implement ToTokens for the existing AST without data structure changes? We care most about preserving spans of identifiers as those are what lead to compilation failures. As I understand it, for every identifier represented in the AST there should be a way to form a proc_macro::Span corresponding to its hygiene context. As a first pass, we care less about spans of other tokens like keywords and punctuation since those would typically only affect error message placement.

[alexcrichton]

I'm not sure I've actually got a great idea of how feasible that would be. I feel like it would be difficult because we don't track all spans everywhere, but that's based on a mental snapshot of the AST from like 3 years ago. Diagnostics have come a long way since then which often comes with annotating more parts of the AST with more spans.

I'm pretty sure, however, that most punctuation in the AST doesn't have span information. For example nothing in #[foo] or foo::bar or foo + bar has span information on just the punctuation itself. That may the hardest part because all identifiers may have spans at this point.

(oh right, also keywords aren't really tracked at all)

It may just not actually be that hard to implement a raw ToTokens for the AST. The pretty printing module is basically already that, and we'd just switch it all to pretty printing to a TokenStream and then pretty printing that later on

[dtolnay]

all identifiers may have spans at this point.

That's what I mean. We can implement conversions from AST to token stream (similar to ToTokens) in a way that preserves spans of all identifiers while inventing spans (as currently done) for keywords and punctuation.

It may just not actually be that hard to implement a raw ToTokens for the AST. The pretty printing module is basically already that, and we'd just switch it all to pretty printing to a TokenStream and then pretty printing that later on

@alexcrichton or @petrochenkov would one of you be able to give this a shot for one of the simplest AST types? Then we could see whether other people can fill in the work for the rest of the AST.

[alexcrichton]

Before we give this a stab I'd want to game out the viability of this strategy. I feel like the punctuation/keyword spans are basically unused for TokenStream but are critical for setting span information on all the rustc AST nodes (as the hi/lo is used all over the place in the parser). I'd be wary that if identifiers were correct and nothing else we'd still be in a pretty bad place

[dtolnay]

@eddyb had some ideas at the Rust All Hands for how to fix this. As I understand it, we want to treat cfg eliminations and other manipulations of the syntax tree as overlays, with each overlay also carrying a token range that identifies the contiguous group of source tokens involved. This overlay mechanism already exists to some extent but is collapsed at some point in a way that is not information-preserving. Based on the token range information captured in overlays it should be possible to reconstruct accurate spans for every token in the syntax tree. And the performance will possibly even be better than the current stringify-reparse workaround.

This will be impactful not just for procedural macros. We identified that IDEs also care about span information captured accurately in macro-expanded code.

Mentioning @alexreg who may be interested in tackling this issue.

[elichai]

Just so I understand. this issue is about the Span?
If so is it even close to solving? Because This gives me a lot of problems in my attribute macro, every error in the function is shown like it's on the macro.

i.e.

83 |     #[logfn(INFO)]                                      
   |     ^^^^^^^^^^^^^^ expected struct `std::string::String`, found array of 20 elements