Auto merge of #40939 - jseyfried:proc_macro_api, r=nrc

proc_macro: implement `TokenTree`, `TokenKind`, hygienic `quote!`, and other API

All new API is gated behind `#![feature(proc_macro)]` and may be used with `#[proc_macro]`, `#[proc_macro_attribute]`, and `#[proc_macro_derive]` procedural macros.

More specifically, this PR adds the following in `proc_macro`:
```rust
// `TokenStream` constructors:
impl TokenStream { fn empty() -> TokenStream { ... } }
impl From<TokenTree> for TokenStream { ... }
impl From<TokenKind> for TokenStream { ... }
impl<T: Into<TokenStream>> FromIterator<T> for TokenStream { ... }
macro quote($($t:tt)*) { ... } // A hygienic `TokenStream` quoter

// `TokenStream` destructuring:
impl TokenStream { fn is_empty(&self) -> bool { ... } }
impl IntoIterator for TokenStream { type Item = TokenTree; ... }

struct TokenTree { span: Span, kind: TokenKind }
impl From<TokenKind> for TokenTree { ... }
impl Display for TokenTree { ... }

struct Span { ... } // a region of source code along with expansion/hygiene information
impl Default for Span { ... } // a span from the current procedural macro definition
impl Span { fn call_site() -> Span { ... } } // the call site of the current expansion
fn quote_span(span: Span) -> TokenStream;

enum TokenKind {
    Group(Delimiter, TokenStream), // A delimited sequence, e.g. `( ... )`
    Term(Term), // a unicode identifier, lifetime ('a), or underscore
    Op(char, Spacing), // a punctuation character (`+`, `,`, `$`, etc.).
    Literal(Literal), // a literal character (`'a'`), string (`"hello"`), or number (`2.3`)
}

enum Delimiter {
    Parenthesis, // `( ... )`
    Brace, // `[ ... ]`
    Bracket, // `{ ... }`
    None, // an implicit delimiter, e.g. `$var`, where $var is  `...`.
}

struct Term { ... } // An interned string
impl Term {
    fn intern(string: &str) -> Symbol { ... }
    fn as_str(&self) -> &str { ... }
}

enum Spacing {
    Alone, // not immediately followed by another `Op`, e.g. `+` in `+ =`.
    Joint, // immediately followed by another `Op`, e.g. `+` in `+=`
}

struct Literal { ... }
impl Display for Literal { ... }
impl Literal {
    fn integer(n: i128) -> Literal { .. } // unsuffixed integer literal
    fn float(n: f64) -> Literal { .. } // unsuffixed floating point literal
    fn u8(n: u8) -> Literal { ... } // similarly: i8, u16, i16, u32, i32, u64, i64, f32, f64
    fn string(string: &str) -> Literal { ... }
    fn character(ch: char) -> Literal { ... }
    fn byte_string(bytes: &[u8]) -> Literal { ... }
}
```
For details on `quote!` hygiene, see [this example](https://github.com/rust-lang/rust/pull/40939/commits/20a90485c040df87a667e9b6ee38e4d8a7d7fc5d) and [declarative macros 2.0](https://github.com/rust-lang/rust/pull/40847).

r? @nrc

1 files changed, 184 insertions, 41 deletions

diff --git a/src/libsyntax/tokenstream.rs b/src/libsyntax/tokenstream.rs
index 963482fc223..8eee25405df 100644
--- a/src/libsyntax/tokenstream.rs
+++ b/src/libsyntax/tokenstream.rs
@@ -138,6 +138,10 @@ impl TokenTree {
             _ => false,
         }
     }
+
+    pub fn joint(self) -> TokenStream {
+        TokenStream { kind: TokenStreamKind::JointTree(self) }
+    }
 }
 
 /// # Token Streams
@@ -155,6 +159,7 @@ pub struct TokenStream {
 enum TokenStreamKind {
     Empty,
     Tree(TokenTree),
+    JointTree(TokenTree),
     Stream(RcSlice<TokenStream>),
 }
 
@@ -199,7 +204,7 @@ impl TokenStream {
     pub fn concat(mut streams: Vec<TokenStream>) -> TokenStream {
         match streams.len() {
             0 => TokenStream::empty(),
-            1 => TokenStream::from(streams.pop().unwrap()),
+            1 => streams.pop().unwrap(),
             _ => TokenStream::concat_rc_slice(RcSlice::new(streams)),
         }
     }
@@ -225,6 +230,105 @@ impl TokenStream {
         }
         true
     }
+
+    /// Precondition: `self` consists of a single token tree.
+    /// Returns true if the token tree is a joint operation w.r.t. `proc_macro::TokenNode`.
+    pub fn as_tree(self) -> (TokenTree, bool /* joint? */) {
+        match self.kind {
+            TokenStreamKind::Tree(tree) => (tree, false),
+            TokenStreamKind::JointTree(tree) => (tree, true),
+            _ => unreachable!(),
+        }
+    }
+
+    pub fn map<F: FnMut(TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream {
+        let mut trees = self.into_trees();
+        let mut result = Vec::new();
+        while let Some(stream) = trees.next_as_stream() {
+            result.push(match stream.kind {
+                TokenStreamKind::Tree(tree) => f(tree).into(),
+                TokenStreamKind::JointTree(tree) => f(tree).joint(),
+                _ => unreachable!()
+            });
+        }
+        TokenStream::concat(result)
+    }
+
+    fn first_tree(&self) -> Option<TokenTree> {
+        match self.kind {
+            TokenStreamKind::Empty => None,
+            TokenStreamKind::Tree(ref tree) |
+            TokenStreamKind::JointTree(ref tree) => Some(tree.clone()),
+            TokenStreamKind::Stream(ref stream) => stream.first().unwrap().first_tree(),
+        }
+    }
+
+    fn last_tree_if_joint(&self) -> Option<TokenTree> {
+        match self.kind {
+            TokenStreamKind::Empty | TokenStreamKind::Tree(..) => None,
+            TokenStreamKind::JointTree(ref tree) => Some(tree.clone()),
+            TokenStreamKind::Stream(ref stream) => stream.last().unwrap().last_tree_if_joint(),
+        }
+    }
+}
+
+pub struct TokenStreamBuilder(Vec<TokenStream>);
+
+impl TokenStreamBuilder {
+    pub fn new() -> TokenStreamBuilder {
+        TokenStreamBuilder(Vec::new())
+    }
+
+    pub fn push<T: Into<TokenStream>>(&mut self, stream: T) {
+        let stream = stream.into();
+        let last_tree_if_joint = self.0.last().and_then(TokenStream::last_tree_if_joint);
+        if let Some(TokenTree::Token(last_span, last_tok)) = last_tree_if_joint {
+            if let Some(TokenTree::Token(span, tok)) = stream.first_tree() {
+                if let Some(glued_tok) = last_tok.glue(tok) {
+                    let last_stream = self.0.pop().unwrap();
+                    self.push_all_but_last_tree(&last_stream);
+                    let glued_span = last_span.to(span);
+                    self.0.push(TokenTree::Token(glued_span, glued_tok).into());
+                    self.push_all_but_first_tree(&stream);
+                    return
+                }
+            }
+        }
+        self.0.push(stream);
+    }
+
+    pub fn add<T: Into<TokenStream>>(mut self, stream: T) -> Self {
+        self.push(stream);
+        self
+    }
+
+    pub fn build(self) -> TokenStream {
+        TokenStream::concat(self.0)
+    }
+
+    fn push_all_but_last_tree(&mut self, stream: &TokenStream) {
+        if let TokenStreamKind::Stream(ref streams) = stream.kind {
+            let len = streams.len();
+            match len {
+                1 => {}
+                2 => self.0.push(streams[0].clone().into()),
+                _ => self.0.push(TokenStream::concat_rc_slice(streams.sub_slice(0 .. len - 1))),
+            }
+            self.push_all_but_last_tree(&streams[len - 1])
+        }
+    }
+
+    fn push_all_but_first_tree(&mut self, stream: &TokenStream) {
+        if let TokenStreamKind::Stream(ref streams) = stream.kind {
+            let len = streams.len();
+            match len {
+                1 => {}
+                2 => self.0.push(streams[1].clone().into()),
+                _ => self.0.push(TokenStream::concat_rc_slice(streams.sub_slice(1 .. len))),
+            }
+            self.push_all_but_first_tree(&streams[0])
+        }
+    }
 }
 
 #[derive(Clone)]
@@ -234,6 +338,7 @@ pub struct Cursor(CursorKind);
 enum CursorKind {
     Empty,
     Tree(TokenTree, bool /* consumed? */),
+    JointTree(TokenTree, bool /* consumed? */),
     Stream(StreamCursor),
 }
 
@@ -244,42 +349,45 @@ struct StreamCursor {
     stack: Vec<(RcSlice<TokenStream>, usize)>,
 }
 
-impl Iterator for Cursor {
-    type Item = TokenTree;
-
-    fn next(&mut self) -> Option<TokenTree> {
-        let cursor = match self.0 {
-            CursorKind::Stream(ref mut cursor) => cursor,
-            CursorKind::Tree(ref tree, ref mut consumed @ false) => {
-                *consumed = true;
-                return Some(tree.clone());
-            }
-            _ => return None,
-        };
+impl StreamCursor {
+    fn new(stream: RcSlice<TokenStream>) -> Self {
+        StreamCursor { stream: stream, index: 0, stack: Vec::new() }
+    }
 
+    fn next_as_stream(&mut self) -> Option<TokenStream> {
         loop {
-            if cursor.index < cursor.stream.len() {
-                match cursor.stream[cursor.index].kind.clone() {
-                    TokenStreamKind::Tree(tree) => {
-                        cursor.index += 1;
-                        return Some(tree);
-                    }
-                    TokenStreamKind::Stream(stream) => {
-                        cursor.stack.push((mem::replace(&mut cursor.stream, stream),
-                                           mem::replace(&mut cursor.index, 0) + 1));
-                    }
-                    TokenStreamKind::Empty => {
-                        cursor.index += 1;
-                    }
+            if self.index < self.stream.len() {
+                self.index += 1;
+                let next = self.stream[self.index - 1].clone();
+                match next.kind {
+                    TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => return Some(next),
+                    TokenStreamKind::Stream(stream) => self.insert(stream),
+                    TokenStreamKind::Empty => {}
                 }
-            } else if let Some((stream, index)) = cursor.stack.pop() {
-                cursor.stream = stream;
-                cursor.index = index;
+            } else if let Some((stream, index)) = self.stack.pop() {
+                self.stream = stream;
+                self.index = index;
             } else {
                 return None;
             }
         }
     }
+
+    fn insert(&mut self, stream: RcSlice<TokenStream>) {
+        self.stack.push((mem::replace(&mut self.stream, stream),
+                         mem::replace(&mut self.index, 0)));
+    }
+}
+
+impl Iterator for Cursor {
+    type Item = TokenTree;
+
+    fn next(&mut self) -> Option<TokenTree> {
+        self.next_as_stream().map(|stream| match stream.kind {
+            TokenStreamKind::Tree(tree) | TokenStreamKind::JointTree(tree) => tree,
+            _ => unreachable!()
+        })
+    }
 }
 
 impl Cursor {
@@ -287,18 +395,49 @@ impl Cursor {
         Cursor(match stream.kind {
             TokenStreamKind::Empty => CursorKind::Empty,
             TokenStreamKind::Tree(tree) => CursorKind::Tree(tree, false),
-            TokenStreamKind::Stream(stream) => {
-                CursorKind::Stream(StreamCursor { stream: stream, index: 0, stack: Vec::new() })
-            }
+            TokenStreamKind::JointTree(tree) => CursorKind::JointTree(tree, false),
+            TokenStreamKind::Stream(stream) => CursorKind::Stream(StreamCursor::new(stream)),
         })
     }
 
-    pub fn original_stream(self) -> TokenStream {
+    pub fn next_as_stream(&mut self) -> Option<TokenStream> {
+        let (stream, consumed) = match self.0 {
+            CursorKind::Tree(ref tree, ref mut consumed @ false) =>
+                (tree.clone().into(), consumed),
+            CursorKind::JointTree(ref tree, ref mut consumed @ false) =>
+                (tree.clone().joint(), consumed),
+            CursorKind::Stream(ref mut cursor) => return cursor.next_as_stream(),
+            _ => return None,
+        };
+
+        *consumed = true;
+        Some(stream)
+    }
+
+    pub fn insert(&mut self, stream: TokenStream) {
+        match self.0 {
+            _ if stream.is_empty() => return,
+            CursorKind::Empty => *self = stream.trees(),
+            CursorKind::Tree(_, consumed) | CursorKind::JointTree(_, consumed) => {
+                *self = TokenStream::concat(vec![self.original_stream(), stream]).trees();
+                if consumed {
+                    self.next();
+                }
+            }
+            CursorKind::Stream(ref mut cursor) => {
+                cursor.insert(ThinTokenStream::from(stream).0.unwrap());
+            }
+        }
+    }
+
+    pub fn original_stream(&self) -> TokenStream {
         match self.0 {
             CursorKind::Empty => TokenStream::empty(),
-            CursorKind::Tree(tree, _) => tree.into(),
-            CursorKind::Stream(cursor) => TokenStream::concat_rc_slice({
-                cursor.stack.get(0).cloned().map(|(stream, _)| stream).unwrap_or(cursor.stream)
+            CursorKind::Tree(ref tree, _) => tree.clone().into(),
+            CursorKind::JointTree(ref tree, _) => tree.clone().joint(),
+            CursorKind::Stream(ref cursor) => TokenStream::concat_rc_slice({
+                cursor.stack.get(0).cloned().map(|(stream, _)| stream)
+                    .unwrap_or(cursor.stream.clone())
             }),
         }
     }
@@ -307,8 +446,9 @@ impl Cursor {
         fn look_ahead(streams: &[TokenStream], mut n: usize) -> Result<TokenTree, usize> {
             for stream in streams {
                 n = match stream.kind {
-                    TokenStreamKind::Tree(ref tree) if n == 0 => return Ok(tree.clone()),
-                    TokenStreamKind::Tree(..) => n - 1,
+                    TokenStreamKind::Tree(ref tree) | TokenStreamKind::JointTree(ref tree)
+                        if n == 0 => return Ok(tree.clone()),
+                    TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => n - 1,
                     TokenStreamKind::Stream(ref stream) => match look_ahead(stream, n) {
                         Ok(tree) => return Ok(tree),
                         Err(n) => n,
@@ -316,13 +456,15 @@ impl Cursor {
                     _ => n,
                 };
             }
-
             Err(n)
         }
 
         match self.0 {
-            CursorKind::Empty | CursorKind::Tree(_, true) => Err(n),
-            CursorKind::Tree(ref tree, false) => look_ahead(&[tree.clone().into()], n),
+            CursorKind::Empty |
+            CursorKind::Tree(_, true) |
+            CursorKind::JointTree(_, true) => Err(n),
+            CursorKind::Tree(ref tree, false) |
+            CursorKind::JointTree(ref tree, false) => look_ahead(&[tree.clone().into()], n),
             CursorKind::Stream(ref cursor) => {
                 look_ahead(&cursor.stream[cursor.index ..], n).or_else(|mut n| {
                     for &(ref stream, index) in cursor.stack.iter().rev() {
@@ -350,6 +492,7 @@ impl From<TokenStream> for ThinTokenStream {
         ThinTokenStream(match stream.kind {
             TokenStreamKind::Empty => None,
             TokenStreamKind::Tree(tree) => Some(RcSlice::new(vec![tree.into()])),
+            TokenStreamKind::JointTree(tree) => Some(RcSlice::new(vec![tree.joint()])),
             TokenStreamKind::Stream(stream) => Some(stream),
         })
     }