Reference count TokenStream in fallback mode

[dtolnay]

The data structure for TokenStream currently in proc-macro2 is a bad fit for the API we inherit from libproc_macro. Specifically this problematic part:

impl Group {
    pub fn stream(&self) -> TokenStream;
}

This function, along with the lack of by-reference iterator on TokenStream, means that the only possible way to parse tokens ends up performing quadratically many token clones. For example if you start with a TokenStream representing ( ( ( ( a ) ) ) ), parsing it involves:

• calling into_iter() to get an iterator of TokenTree;
• you'll find in there a Group, so call stream(); this clones the tree's entire contents ( ( ( a ) ) )
• call into_iter()
• call stream(), which clones ( ( a ) )
• call into_iter()
• call stream(), which clones ( a )
• call into_iter()
• call stream(), which clones a.

Changing to Rc<Vec<TokenTree>> makes a large difference in syn's benchmarks.

Before:

test baseline            ... bench:     611,395 ns/iter (+/- 11,493)
test create_token_buffer ... bench:   2,101,492 ns/iter (+/- 18,112)
test parse_file          ... bench:   5,598,063 ns/iter (+/- 283,333)

After:

test baseline            ... bench:           3 ns/iter (+/- 0)
test create_token_buffer ... bench:     955,353 ns/iter (+/- 6,600)
test parse_file          ... bench:   4,144,685 ns/iter (+/- 74,192)

Rustc also uses a similar Rc<Vec> data structure in its own TokenStream implementation:

https://github.com/rust-lang/rust/blob/1.62.1/compiler/rustc_ast/src/tokenstream.rs#L305-L306

pub struct TokenStream(pub(crate) Lrc<Vec<TreeAndSpacing>>);