Auto merge of #114115 - nnethercote:less-token-tree-cloning, r=petrochenkov

Less `TokenTree` cloning

`TokenTreeCursor` has this comment on it:
```
// FIXME: Many uses of this can be replaced with by-reference iterator to avoid clones.
```
This PR completes that FIXME. It doesn't have much perf effect, but at least we now know that.

r? `@petrochenkov`

2 files changed, 33 insertions, 37 deletions

diff --git a/compiler/rustc_ast/src/attr/mod.rs b/compiler/rustc_ast/src/attr/mod.rs
index 15fe29580c2..8b9bb1df5dc 100644
--- a/compiler/rustc_ast/src/attr/mod.rs
+++ b/compiler/rustc_ast/src/attr/mod.rs
@@ -285,17 +285,17 @@ impl MetaItem {
         self.kind.value_str()
     }
 
-    fn from_tokens<I>(tokens: &mut iter::Peekable<I>) -> Option<MetaItem>
+    fn from_tokens<'a, I>(tokens: &mut iter::Peekable<I>) -> Option<MetaItem>
     where
-        I: Iterator<Item = TokenTree>,
+        I: Iterator<Item = &'a TokenTree>,
     {
         // FIXME: Share code with `parse_path`.
-        let path = match tokens.next().map(TokenTree::uninterpolate) {
-            Some(TokenTree::Token(
-                Token { kind: kind @ (token::Ident(..) | token::ModSep), span },
+        let path = match tokens.next().map(|tt| TokenTree::uninterpolate(tt)).as_deref() {
+            Some(&TokenTree::Token(
+                Token { kind: ref kind @ (token::Ident(..) | token::ModSep), span },
                 _,
             )) => 'arm: {
-                let mut segments = if let token::Ident(name, _) = kind {
+                let mut segments = if let &token::Ident(name, _) = kind {
                     if let Some(TokenTree::Token(Token { kind: token::ModSep, .. }, _)) =
                         tokens.peek()
                     {
@@ -308,8 +308,8 @@ impl MetaItem {
                     thin_vec![PathSegment::path_root(span)]
                 };
                 loop {
-                    if let Some(TokenTree::Token(Token { kind: token::Ident(name, _), span }, _)) =
-                        tokens.next().map(TokenTree::uninterpolate)
+                    if let Some(&TokenTree::Token(Token { kind: token::Ident(name, _), span }, _)) =
+                        tokens.next().map(|tt| TokenTree::uninterpolate(tt)).as_deref()
                     {
                         segments.push(PathSegment::from_ident(Ident::new(name, span)));
                     } else {
@@ -326,7 +326,7 @@ impl MetaItem {
                 let span = span.with_hi(segments.last().unwrap().ident.span.hi());
                 Path { span, segments, tokens: None }
             }
-            Some(TokenTree::Token(Token { kind: token::Interpolated(nt), .. }, _)) => match &*nt {
+            Some(TokenTree::Token(Token { kind: token::Interpolated(nt), .. }, _)) => match &**nt {
                 token::Nonterminal::NtMeta(item) => return item.meta(item.path.span),
                 token::Nonterminal::NtPath(path) => (**path).clone(),
                 _ => return None,
@@ -354,7 +354,7 @@ impl MetaItemKind {
     }
 
     fn list_from_tokens(tokens: TokenStream) -> Option<ThinVec<NestedMetaItem>> {
-        let mut tokens = tokens.into_trees().peekable();
+        let mut tokens = tokens.trees().peekable();
         let mut result = ThinVec::new();
         while tokens.peek().is_some() {
             let item = NestedMetaItem::from_tokens(&mut tokens)?;
@@ -367,12 +367,12 @@ impl MetaItemKind {
         Some(result)
     }
 
-    fn name_value_from_tokens(
-        tokens: &mut impl Iterator<Item = TokenTree>,
+    fn name_value_from_tokens<'a>(
+        tokens: &mut impl Iterator<Item = &'a TokenTree>,
     ) -> Option<MetaItemKind> {
         match tokens.next() {
             Some(TokenTree::Delimited(_, Delimiter::Invisible, inner_tokens)) => {
-                MetaItemKind::name_value_from_tokens(&mut inner_tokens.into_trees())
+                MetaItemKind::name_value_from_tokens(&mut inner_tokens.trees())
             }
             Some(TokenTree::Token(token, _)) => {
                 MetaItemLit::from_token(&token).map(MetaItemKind::NameValue)
@@ -381,8 +381,8 @@ impl MetaItemKind {
         }
     }
 
-    fn from_tokens(
-        tokens: &mut iter::Peekable<impl Iterator<Item = TokenTree>>,
+    fn from_tokens<'a>(
+        tokens: &mut iter::Peekable<impl Iterator<Item = &'a TokenTree>>,
     ) -> Option<MetaItemKind> {
         match tokens.peek() {
             Some(TokenTree::Delimited(_, Delimiter::Parenthesis, inner_tokens)) => {
@@ -501,9 +501,9 @@ impl NestedMetaItem {
         self.meta_item().is_some()
     }
 
-    fn from_tokens<I>(tokens: &mut iter::Peekable<I>) -> Option<NestedMetaItem>
+    fn from_tokens<'a, I>(tokens: &mut iter::Peekable<I>) -> Option<NestedMetaItem>
     where
-        I: Iterator<Item = TokenTree>,
+        I: Iterator<Item = &'a TokenTree>,
     {
         match tokens.peek() {
             Some(TokenTree::Token(token, _))
@@ -513,9 +513,8 @@ impl NestedMetaItem {
                 return Some(NestedMetaItem::Lit(lit));
             }
             Some(TokenTree::Delimited(_, Delimiter::Invisible, inner_tokens)) => {
-                let inner_tokens = inner_tokens.clone();
                 tokens.next();
-                return NestedMetaItem::from_tokens(&mut inner_tokens.into_trees().peekable());
+                return NestedMetaItem::from_tokens(&mut inner_tokens.trees().peekable());
             }
             _ => {}
         }
diff --git a/compiler/rustc_ast/src/tokenstream.rs b/compiler/rustc_ast/src/tokenstream.rs
index ca4a739abd7..348c37c480f 100644
--- a/compiler/rustc_ast/src/tokenstream.rs
+++ b/compiler/rustc_ast/src/tokenstream.rs
@@ -25,6 +25,7 @@ use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
 use rustc_span::{Span, DUMMY_SP};
 use smallvec::{smallvec, SmallVec};
 
+use std::borrow::Cow;
 use std::{fmt, iter, mem};
 
 /// When the main Rust parser encounters a syntax-extension invocation, it
@@ -98,12 +99,13 @@ impl TokenTree {
         TokenTree::Token(Token::new(kind, span), Spacing::Joint)
     }
 
-    pub fn uninterpolate(self) -> TokenTree {
+    pub fn uninterpolate(&self) -> Cow<'_, TokenTree> {
         match self {
-            TokenTree::Token(token, spacing) => {
-                TokenTree::Token(token.uninterpolate().into_owned(), spacing)
-            }
-            tt => tt,
+            TokenTree::Token(token, spacing) => match token.uninterpolate() {
+                Cow::Owned(token) => Cow::Owned(TokenTree::Token(token, *spacing)),
+                Cow::Borrowed(_) => Cow::Borrowed(self),
+            },
+            _ => Cow::Borrowed(self),
         }
     }
 }
@@ -595,26 +597,21 @@ impl<'t> Iterator for RefTokenTreeCursor<'t> {
     }
 }
 
-/// Owning by-value iterator over a [`TokenStream`], that produces `TokenTree`
+/// Owning by-value iterator over a [`TokenStream`], that produces `&TokenTree`
 /// items.
-// FIXME: Many uses of this can be replaced with by-reference iterator to avoid clones.
+///
+/// Doesn't impl `Iterator` because Rust doesn't permit an owning iterator to
+/// return `&T` from `next`; the need for an explicit lifetime in the `Item`
+/// associated type gets in the way. Instead, use `next_ref` (which doesn't
+/// involve associated types) for getting individual elements, or
+/// `RefTokenTreeCursor` if you really want an `Iterator`, e.g. in a `for`
+/// loop.
 #[derive(Clone)]
 pub struct TokenTreeCursor {
     pub stream: TokenStream,
     index: usize,
 }
 
-impl Iterator for TokenTreeCursor {
-    type Item = TokenTree;
-
-    fn next(&mut self) -> Option<TokenTree> {
-        self.stream.0.get(self.index).map(|tree| {
-            self.index += 1;
-            tree.clone()
-        })
-    }
-}
-
 impl TokenTreeCursor {
     fn new(stream: TokenStream) -> Self {
         TokenTreeCursor { stream, index: 0 }