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

22 files changed, 512 insertions, 253 deletions

diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index ecab801d408..d00e29d954f 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -99,7 +99,7 @@ impl Path {
     pub fn default_to_global(mut self) -> Path {
         if !self.is_global() &&
            !::parse::token::Ident(self.segments[0].identifier).is_path_segment_keyword() {
-            self.segments.insert(0, PathSegment::crate_root());
+            self.segments.insert(0, PathSegment::crate_root(self.span));
         }
         self
     }
@@ -133,10 +133,10 @@ impl PathSegment {
     pub fn from_ident(ident: Ident, span: Span) -> Self {
         PathSegment { identifier: ident, span: span, parameters: None }
     }
-    pub fn crate_root() -> Self {
+    pub fn crate_root(span: Span) -> Self {
         PathSegment {
-            identifier: keywords::CrateRoot.ident(),
-            span: DUMMY_SP,
+            identifier: Ident { ctxt: span.ctxt, ..keywords::CrateRoot.ident() },
+            span: span,
             parameters: None,
         }
     }
diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index 8e63e219c42..f0fc849c0c5 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -1057,7 +1057,7 @@ impl MetaItem {
     {
         let (mut span, name) = match tokens.next() {
             Some(TokenTree::Token(span, Token::Ident(ident))) => (span, ident.name),
-            Some(TokenTree::Token(_, Token::Interpolated(ref nt))) => match **nt {
+            Some(TokenTree::Token(_, Token::Interpolated(ref nt))) => match nt.0 {
                 token::Nonterminal::NtIdent(ident) => (ident.span, ident.node.name),
                 token::Nonterminal::NtMeta(ref meta) => return Some(meta.clone()),
                 _ => return None,
@@ -1229,7 +1229,7 @@ impl LitKind {
         match token {
             Token::Ident(ident) if ident.name == "true" => Some(LitKind::Bool(true)),
             Token::Ident(ident) if ident.name == "false" => Some(LitKind::Bool(false)),
-            Token::Interpolated(ref nt) => match **nt {
+            Token::Interpolated(ref nt) => match nt.0 {
                 token::NtExpr(ref v) => match v.node {
                     ExprKind::Lit(ref lit) => Some(lit.node.clone()),
                     _ => None,
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 8089fad5f36..4881170c1d1 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -215,7 +215,7 @@ impl<F> TTMacroExpander for F
         impl Folder for AvoidInterpolatedIdents {
             fn fold_tt(&mut self, tt: tokenstream::TokenTree) -> tokenstream::TokenTree {
                 if let tokenstream::TokenTree::Token(_, token::Interpolated(ref nt)) = tt {
-                    if let token::NtIdent(ident) = **nt {
+                    if let token::NtIdent(ident) = nt.0 {
                         return tokenstream::TokenTree::Token(ident.span, token::Ident(ident.node));
                     }
                 }
@@ -578,7 +578,10 @@ impl SyntaxExtension {
 
     pub fn is_modern(&self) -> bool {
         match *self {
-            SyntaxExtension::DeclMacro(..) => true,
+            SyntaxExtension::DeclMacro(..) |
+            SyntaxExtension::ProcMacro(..) |
+            SyntaxExtension::AttrProcMacro(..) |
+            SyntaxExtension::ProcMacroDerive(..) => true,
             _ => false,
         }
     }
@@ -903,17 +906,3 @@ pub fn get_exprs_from_tts(cx: &mut ExtCtxt,
     }
     Some(es)
 }
-
-pub struct ChangeSpan {
-    pub span: Span
-}
-
-impl Folder for ChangeSpan {
-    fn new_span(&mut self, _sp: Span) -> Span {
-        self.span
-    }
-
-    fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
-        fold::noop_fold_mac(mac, self)
-    }
-}
diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 412a3493208..1eb749623d8 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -320,7 +320,7 @@ impl<'a> AstBuilder for ExtCtxt<'a> {
         let last_identifier = idents.pop().unwrap();
         let mut segments: Vec<ast::PathSegment> = Vec::new();
         if global {
-            segments.push(ast::PathSegment::crate_root());
+            segments.push(ast::PathSegment::crate_root(sp));
         }
 
         segments.extend(idents.into_iter().map(|i| ast::PathSegment::from_ident(i, sp)));
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index f8a26287bd4..d2e51c9cb48 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -16,20 +16,20 @@ use config::{is_test_or_bench, StripUnconfigured};
 use errors::FatalError;
 use ext::base::*;
 use ext::derive::{add_derived_markers, collect_derives};
-use ext::hygiene::Mark;
+use ext::hygiene::{Mark, SyntaxContext};
 use ext::placeholders::{placeholder, PlaceholderExpander};
 use feature_gate::{self, Features, is_builtin_attr};
 use fold;
 use fold::*;
-use parse::{filemap_to_stream, ParseSess, DirectoryOwnership, PResult, token};
+use parse::{DirectoryOwnership, PResult};
+use parse::token::{self, Token};
 use parse::parser::Parser;
-use print::pprust;
 use ptr::P;
 use std_inject;
 use symbol::Symbol;
 use symbol::keywords;
 use syntax_pos::{Span, DUMMY_SP};
-use tokenstream::TokenStream;
+use tokenstream::{TokenStream, TokenTree};
 use util::small_vector::SmallVector;
 use visit::Visitor;
 
@@ -427,11 +427,13 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                 kind.expect_from_annotatables(items)
             }
             SyntaxExtension::AttrProcMacro(ref mac) => {
-                let item_toks = stream_for_item(&item, self.cx.parse_sess);
-
-                let span = Span { ctxt: self.cx.backtrace(), ..attr.span };
-                let tok_result = mac.expand(self.cx, attr.span, attr.tokens, item_toks);
-                self.parse_expansion(tok_result, kind, &attr.path, span)
+                let item_tok = TokenTree::Token(DUMMY_SP, Token::interpolated(match item {
+                    Annotatable::Item(item) => token::NtItem(item),
+                    Annotatable::TraitItem(item) => token::NtTraitItem(item.unwrap()),
+                    Annotatable::ImplItem(item) => token::NtImplItem(item.unwrap()),
+                })).into();
+                let tok_result = mac.expand(self.cx, attr.span, attr.tokens, item_tok);
+                self.parse_expansion(tok_result, kind, &attr.path, attr.span)
             }
             SyntaxExtension::ProcMacroDerive(..) | SyntaxExtension::BuiltinDerive(..) => {
                 self.cx.span_err(attr.span, &format!("`{}` is a derive mode", attr.path));
@@ -470,7 +472,6 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
             Ok(())
         };
 
-        let marked_tts = noop_fold_tts(mac.node.stream(), &mut Marker(mark));
         let opt_expanded = match *ext {
             SyntaxExtension::DeclMacro(ref expand, def_span) => {
                 if let Err(msg) = validate_and_set_expn_info(def_span.map(|(_, s)| s),
@@ -478,7 +479,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                     self.cx.span_err(path.span, &msg);
                     return kind.dummy(span);
                 }
-                kind.make_from(expand.expand(self.cx, span, marked_tts))
+                kind.make_from(expand.expand(self.cx, span, mac.node.stream()))
             }
 
             NormalTT(ref expandfun, def_info, allow_internal_unstable) => {
@@ -487,7 +488,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                     self.cx.span_err(path.span, &msg);
                     return kind.dummy(span);
                 }
-                kind.make_from(expandfun.expand(self.cx, span, marked_tts))
+                kind.make_from(expandfun.expand(self.cx, span, mac.node.stream()))
             }
 
             IdentTT(ref expander, tt_span, allow_internal_unstable) => {
@@ -506,7 +507,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                     }
                 });
 
-                let input: Vec<_> = marked_tts.into_trees().collect();
+                let input: Vec<_> = mac.node.stream().into_trees().collect();
                 kind.make_from(expander.expand(self.cx, span, ident, input))
             }
 
@@ -541,21 +542,17 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                     },
                 });
 
-                let tok_result = expandfun.expand(self.cx, span, marked_tts);
+                let tok_result = expandfun.expand(self.cx, span, mac.node.stream());
                 Some(self.parse_expansion(tok_result, kind, path, span))
             }
         };
 
-        let expanded = if let Some(expanded) = opt_expanded {
-            expanded
-        } else {
+        unwrap_or!(opt_expanded, {
             let msg = format!("non-{kind} macro in {kind} position: {name}",
                               name = path.segments[0].identifier.name, kind = kind.name());
             self.cx.span_err(path.span, &msg);
-            return kind.dummy(span);
-        };
-
-        expanded.fold_with(&mut Marker(mark))
+            kind.dummy(span)
+        })
     }
 
     /// Expand a derive invocation. Returns the result of expansion.
@@ -621,8 +618,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
             }
         };
         parser.ensure_complete_parse(path, kind.name(), span);
-        // FIXME better span info
-        expansion.fold_with(&mut ChangeSpan { span: span })
+        expansion
     }
 }
 
@@ -673,7 +669,9 @@ impl<'a> Parser<'a> {
         if self.token != token::Eof {
             let msg = format!("macro expansion ignores token `{}` and any following",
                               self.this_token_to_string());
-            let mut err = self.diagnostic().struct_span_err(self.span, &msg);
+            let mut def_site_span = self.span;
+            def_site_span.ctxt = SyntaxContext::empty(); // Avoid emitting backtrace info twice.
+            let mut err = self.diagnostic().struct_span_err(def_site_span, &msg);
             let msg = format!("caused by the macro expansion here; the usage \
                                of `{}!` is likely invalid in {} context",
                                macro_path, kind_name);
@@ -773,28 +771,6 @@ pub fn find_attr_invoc(attrs: &mut Vec<ast::Attribute>) -> Option<ast::Attribute
          .map(|i| attrs.remove(i))
 }
 
-// These are pretty nasty. Ideally, we would keep the tokens around, linked from
-// the AST. However, we don't so we need to create new ones. Since the item might
-// have come from a macro expansion (possibly only in part), we can't use the
-// existing codemap.
-//
-// Therefore, we must use the pretty printer (yuck) to turn the AST node into a
-// string, which we then re-tokenise (double yuck), but first we have to patch
-// the pretty-printed string on to the end of the existing codemap (infinity-yuck).
-fn stream_for_item(item: &Annotatable, parse_sess: &ParseSess) -> TokenStream {
-    let text = match *item {
-        Annotatable::Item(ref i) => pprust::item_to_string(i),
-        Annotatable::TraitItem(ref ti) => pprust::trait_item_to_string(ti),
-        Annotatable::ImplItem(ref ii) => pprust::impl_item_to_string(ii),
-    };
-    string_to_stream(text, parse_sess)
-}
-
-fn string_to_stream(text: String, parse_sess: &ParseSess) -> TokenStream {
-    let filename = String::from("<macro expansion>");
-    filemap_to_stream(parse_sess, parse_sess.codemap().new_filemap(filename, text))
-}
-
 impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
     fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
         let mut expr = self.cfg.configure_expr(expr).unwrap();
@@ -1070,7 +1046,7 @@ impl<'feat> ExpansionConfig<'feat> {
 }
 
 // A Marker adds the given mark to the syntax context.
-struct Marker(Mark);
+pub struct Marker(pub Mark);
 
 impl Folder for Marker {
     fn fold_ident(&mut self, mut ident: Ident) -> Ident {
diff --git a/src/libsyntax/ext/quote.rs b/src/libsyntax/ext/quote.rs
index f8fac847a05..9907dfe341e 100644
--- a/src/libsyntax/ext/quote.rs
+++ b/src/libsyntax/ext/quote.rs
@@ -30,9 +30,9 @@ pub mod rt {
     use ast;
     use codemap::Spanned;
     use ext::base::ExtCtxt;
-    use parse::{self, token, classify};
+    use parse::{self, classify};
+    use parse::token::{self, Token};
     use ptr::P;
-    use std::rc::Rc;
     use symbol::Symbol;
 
     use tokenstream::{self, TokenTree, TokenStream};
@@ -82,70 +82,70 @@ pub mod rt {
     impl ToTokens for ast::Path {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtPath(self.clone());
-            vec![TokenTree::Token(DUMMY_SP, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(DUMMY_SP, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::Ty {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtTy(P(self.clone()));
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::Block {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtBlock(P(self.clone()));
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::Generics {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtGenerics(self.clone());
-            vec![TokenTree::Token(DUMMY_SP, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(DUMMY_SP, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::WhereClause {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtWhereClause(self.clone());
-            vec![TokenTree::Token(DUMMY_SP, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(DUMMY_SP, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for P<ast::Item> {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtItem(self.clone());
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::ImplItem {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtImplItem(self.clone());
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for P<ast::ImplItem> {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtImplItem((**self).clone());
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::TraitItem {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtTraitItem(self.clone());
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::Stmt {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtStmt(self.clone());
-            let mut tts = vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))];
+            let mut tts = vec![TokenTree::Token(self.span, Token::interpolated(nt))];
 
             // Some statements require a trailing semicolon.
             if classify::stmt_ends_with_semi(&self.node) {
@@ -159,35 +159,35 @@ pub mod rt {
     impl ToTokens for P<ast::Expr> {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtExpr(self.clone());
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for P<ast::Pat> {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtPat(self.clone());
-            vec![TokenTree::Token(self.span, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(self.span, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::Arm {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtArm(self.clone());
-            vec![TokenTree::Token(DUMMY_SP, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(DUMMY_SP, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for ast::Arg {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtArg(self.clone());
-            vec![TokenTree::Token(DUMMY_SP, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(DUMMY_SP, Token::interpolated(nt))]
         }
     }
 
     impl ToTokens for P<ast::Block> {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtBlock(self.clone());
-            vec![TokenTree::Token(DUMMY_SP, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(DUMMY_SP, Token::interpolated(nt))]
         }
     }
 
@@ -215,7 +215,7 @@ pub mod rt {
     impl ToTokens for ast::MetaItem {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
             let nt = token::NtMeta(self.clone());
-            vec![TokenTree::Token(DUMMY_SP, token::Interpolated(Rc::new(nt)))]
+            vec![TokenTree::Token(DUMMY_SP, Token::interpolated(nt))]
         }
     }
 
@@ -364,7 +364,7 @@ pub mod rt {
 
         fn parse_tts(&self, s: String) -> Vec<TokenTree> {
             let source_name = "<quote expansion>".to_owned();
-            parse::parse_stream_from_source_str(source_name, s, self.parse_sess())
+            parse::parse_stream_from_source_str(source_name, s, self.parse_sess(), None)
                 .into_trees().collect()
         }
     }
@@ -700,7 +700,7 @@ fn expr_mk_token(cx: &ExtCtxt, sp: Span, tok: &token::Token) -> P<ast::Expr> {
         token::Underscore   => "Underscore",
         token::Eof          => "Eof",
 
-        token::Whitespace | token::SubstNt(_) | token::Comment | token::Shebang(_) => {
+        token::Whitespace | token::Comment | token::Shebang(_) => {
             panic!("unhandled token in quote!");
         }
     };
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index 61d8fc2941a..e877f1fedd4 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -158,15 +158,10 @@ pub type NamedParseResult = ParseResult<HashMap<Ident, Rc<NamedMatch>>>;
 pub fn count_names(ms: &[TokenTree]) -> usize {
     ms.iter().fold(0, |count, elt| {
         count + match *elt {
-            TokenTree::Sequence(_, ref seq) => {
-                seq.num_captures
-            }
-            TokenTree::Delimited(_, ref delim) => {
-                count_names(&delim.tts)
-            }
-            TokenTree::MetaVarDecl(..) => {
-                1
-            }
+            TokenTree::Sequence(_, ref seq) => seq.num_captures,
+            TokenTree::Delimited(_, ref delim) => count_names(&delim.tts),
+            TokenTree::MetaVar(..) => 0,
+            TokenTree::MetaVarDecl(..) => 1,
             TokenTree::Token(..) => 0,
         }
     })
@@ -244,7 +239,7 @@ fn nameize<I: Iterator<Item=NamedMatch>>(sess: &ParseSess, ms: &[TokenTree], mut
                     }
                 }
             }
-            TokenTree::Token(..) => (),
+            TokenTree::MetaVar(..) | TokenTree::Token(..) => (),
         }
 
         Ok(())
@@ -409,12 +404,11 @@ fn inner_parse_loop(sess: &ParseSess,
                     ei.idx = 0;
                     cur_eis.push(ei);
                 }
-                TokenTree::Token(_, ref t) => {
-                    if token_name_eq(t, token) {
-                        ei.idx += 1;
-                        next_eis.push(ei);
-                    }
+                TokenTree::Token(_, ref t) if token_name_eq(t, token) => {
+                    ei.idx += 1;
+                    next_eis.push(ei);
                 }
+                TokenTree::Token(..) | TokenTree::MetaVar(..) => {}
             }
         }
     }
diff --git a/src/libsyntax/ext/tt/macro_rules.rs b/src/libsyntax/ext/tt/macro_rules.rs
index 9c728c9f2eb..b732f47ce6a 100644
--- a/src/libsyntax/ext/tt/macro_rules.rs
+++ b/src/libsyntax/ext/tt/macro_rules.rs
@@ -120,7 +120,7 @@ fn generic_extension<'cx>(cx: &'cx mut ExtCtxt,
                     _ => cx.span_bug(sp, "malformed macro rhs"),
                 };
                 // rhs has holes ( `$id` and `$(...)` that need filled)
-                let tts = transcribe(&cx.parse_sess.span_diagnostic, Some(named_matches), rhs);
+                let tts = transcribe(cx, Some(named_matches), rhs);
 
                 if cx.trace_macros() {
                     trace_macros_note(cx, sp, format!("to `{}`", tts));
@@ -292,7 +292,7 @@ fn check_lhs_no_empty_seq(sess: &ParseSess, tts: &[quoted::TokenTree]) -> bool {
     use self::quoted::TokenTree;
     for tt in tts {
         match *tt {
-            TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => (),
+            TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => (),
             TokenTree::Delimited(_, ref del) => if !check_lhs_no_empty_seq(sess, &del.tts) {
                 return false;
             },
@@ -372,7 +372,7 @@ impl FirstSets {
             let mut first = TokenSet::empty();
             for tt in tts.iter().rev() {
                 match *tt {
-                    TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => {
+                    TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => {
                         first.replace_with(tt.clone());
                     }
                     TokenTree::Delimited(span, ref delimited) => {
@@ -432,7 +432,7 @@ impl FirstSets {
         for tt in tts.iter() {
             assert!(first.maybe_empty);
             match *tt {
-                TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => {
+                TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => {
                     first.add_one(tt.clone());
                     return first;
                 }
@@ -602,7 +602,7 @@ fn check_matcher_core(sess: &ParseSess,
         // First, update `last` so that it corresponds to the set
         // of NT tokens that might end the sequence `... token`.
         match *token {
-            TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => {
+            TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => {
                 let can_be_followed_by_any;
                 if let Err(bad_frag) = has_legal_fragment_specifier(sess, features, token) {
                     let msg = format!("invalid fragment specifier `{}`", bad_frag);
@@ -872,6 +872,7 @@ fn is_legal_fragment_specifier(sess: &ParseSess,
 fn quoted_tt_to_string(tt: &quoted::TokenTree) -> String {
     match *tt {
         quoted::TokenTree::Token(_, ref tok) => ::print::pprust::token_to_string(tok),
+        quoted::TokenTree::MetaVar(_, name) => format!("${}", name),
         quoted::TokenTree::MetaVarDecl(_, name, kind) => format!("${}:{}", name, kind),
         _ => panic!("unexpected quoted::TokenTree::{{Sequence or Delimited}} \
                      in follow set checker"),
diff --git a/src/libsyntax/ext/tt/quoted.rs b/src/libsyntax/ext/tt/quoted.rs
index c094a23cefc..4e9e30857b1 100644
--- a/src/libsyntax/ext/tt/quoted.rs
+++ b/src/libsyntax/ext/tt/quoted.rs
@@ -78,9 +78,11 @@ pub enum KleeneOp {
 pub enum TokenTree {
     Token(Span, token::Token),
     Delimited(Span, Rc<Delimited>),
-    /// A kleene-style repetition sequence with a span
+    /// A kleene-style repetition sequence
     Sequence(Span, Rc<SequenceRepetition>),
-    /// Matches a nonterminal. This is only used in the left hand side of MBE macros.
+    /// E.g. `$var`
+    MetaVar(Span, ast::Ident),
+    /// E.g. `$var:expr`. This is only used in the left hand side of MBE macros.
     MetaVarDecl(Span, ast::Ident /* name to bind */, ast::Ident /* kind of nonterminal */),
 }
 
@@ -130,6 +132,7 @@ impl TokenTree {
     pub fn span(&self) -> Span {
         match *self {
             TokenTree::Token(sp, _) |
+            TokenTree::MetaVar(sp, _) |
             TokenTree::MetaVarDecl(sp, _, _) |
             TokenTree::Delimited(sp, _) |
             TokenTree::Sequence(sp, _) => sp,
@@ -144,7 +147,7 @@ pub fn parse(input: tokenstream::TokenStream, expect_matchers: bool, sess: &Pars
     while let Some(tree) = trees.next() {
         let tree = parse_tree(tree, &mut trees, expect_matchers, sess);
         match tree {
-            TokenTree::Token(start_sp, token::SubstNt(ident)) if expect_matchers => {
+            TokenTree::MetaVar(start_sp, ident) if expect_matchers => {
                 let span = match trees.next() {
                     Some(tokenstream::TokenTree::Token(span, token::Colon)) => match trees.next() {
                         Some(tokenstream::TokenTree::Token(end_sp, ref tok)) => match tok.ident() {
@@ -199,13 +202,13 @@ fn parse_tree<I>(tree: tokenstream::TokenTree,
                     let ident = ast::Ident { name: keywords::DollarCrate.name(), ..ident };
                     TokenTree::Token(span, token::Ident(ident))
                 } else {
-                    TokenTree::Token(span, token::SubstNt(ident))
+                    TokenTree::MetaVar(span, ident)
                 }
             }
             Some(tokenstream::TokenTree::Token(span, tok)) => {
                 let msg = format!("expected identifier, found `{}`", pprust::token_to_string(&tok));
                 sess.span_diagnostic.span_err(span, &msg);
-                TokenTree::Token(span, token::SubstNt(keywords::Invalid.ident()))
+                TokenTree::MetaVar(span, keywords::Invalid.ident())
             }
             None => TokenTree::Token(span, token::Dollar),
         },
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index 78e755e73fa..fe3dd83f9d5 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -9,10 +9,12 @@
 // except according to those terms.
 
 use ast::Ident;
-use errors::Handler;
+use ext::base::ExtCtxt;
+use ext::expand::Marker;
 use ext::tt::macro_parser::{NamedMatch, MatchedSeq, MatchedNonterminal};
 use ext::tt::quoted;
-use parse::token::{self, SubstNt, Token, NtTT};
+use fold::noop_fold_tt;
+use parse::token::{self, Token, NtTT};
 use syntax_pos::{Span, DUMMY_SP};
 use tokenstream::{TokenStream, TokenTree, Delimited};
 use util::small_vector::SmallVector;
@@ -61,9 +63,9 @@ impl Iterator for Frame {
 }
 
 /// This can do Macro-By-Example transcription. On the other hand, if
-/// `src` contains no `TokenTree::{Sequence, Match}`s, or `SubstNt`s, `interp` can
+/// `src` contains no `TokenTree::{Sequence, MetaVar, MetaVarDecl}`s, `interp` can
 /// (and should) be None.
-pub fn transcribe(sp_diag: &Handler,
+pub fn transcribe(cx: &ExtCtxt,
                   interp: Option<HashMap<Ident, Rc<NamedMatch>>>,
                   src: Vec<quoted::TokenTree>)
                   -> TokenStream {
@@ -120,22 +122,20 @@ pub fn transcribe(sp_diag: &Handler,
                                          &interpolations,
                                          &repeats) {
                     LockstepIterSize::Unconstrained => {
-                        panic!(sp_diag.span_fatal(
-                            sp, /* blame macro writer */
+                        cx.span_fatal(sp, /* blame macro writer */
                             "attempted to repeat an expression \
                              containing no syntax \
-                             variables matched as repeating at this depth"));
+                             variables matched as repeating at this depth");
                     }
                     LockstepIterSize::Contradiction(ref msg) => {
                         // FIXME #2887 blame macro invoker instead
-                        panic!(sp_diag.span_fatal(sp, &msg[..]));
+                        cx.span_fatal(sp, &msg[..]);
                     }
                     LockstepIterSize::Constraint(len, _) => {
                         if len == 0 {
                             if seq.op == quoted::KleeneOp::OneOrMore {
                                 // FIXME #2887 blame invoker
-                                panic!(sp_diag.span_fatal(sp,
-                                                          "this must repeat at least once"));
+                                cx.span_fatal(sp, "this must repeat at least once");
                             }
                         } else {
                             repeats.push((0, len));
@@ -149,29 +149,37 @@ pub fn transcribe(sp_diag: &Handler,
                 }
             }
             // FIXME #2887: think about span stuff here
-            quoted::TokenTree::Token(sp, SubstNt(ident)) => {
-                match lookup_cur_matched(ident, &interpolations, &repeats) {
-                    None => result.push(TokenTree::Token(sp, SubstNt(ident)).into()),
-                    Some(cur_matched) => if let MatchedNonterminal(ref nt) = *cur_matched {
-                        match **nt {
-                            NtTT(ref tt) => result.push(tt.clone().into()),
-                            _ => {
-                                let token = TokenTree::Token(sp, token::Interpolated(nt.clone()));
-                                result.push(token.into());
-                            }
+            quoted::TokenTree::MetaVar(mut sp, ident) => {
+                if let Some(cur_matched) = lookup_cur_matched(ident, &interpolations, &repeats) {
+                    if let MatchedNonterminal(ref nt) = *cur_matched {
+                        if let NtTT(ref tt) = **nt {
+                            result.push(tt.clone().into());
+                        } else {
+                            sp.ctxt = sp.ctxt.apply_mark(cx.current_expansion.mark);
+                            let token = TokenTree::Token(sp, Token::interpolated((**nt).clone()));
+                            result.push(token.into());
                         }
                     } else {
-                        panic!(sp_diag.span_fatal(
-                            sp, /* blame the macro writer */
-                            &format!("variable '{}' is still repeating at this depth", ident)));
+                        cx.span_fatal(sp, /* blame the macro writer */
+                            &format!("variable '{}' is still repeating at this depth", ident));
                     }
+                } else {
+                    let ident =
+                        Ident { ctxt: ident.ctxt.apply_mark(cx.current_expansion.mark), ..ident };
+                    sp.ctxt = sp.ctxt.apply_mark(cx.current_expansion.mark);
+                    result.push(TokenTree::Token(sp, token::Dollar).into());
+                    result.push(TokenTree::Token(sp, token::Ident(ident)).into());
                 }
             }
-            quoted::TokenTree::Delimited(span, delimited) => {
+            quoted::TokenTree::Delimited(mut span, delimited) => {
+                span.ctxt = span.ctxt.apply_mark(cx.current_expansion.mark);
                 stack.push(Frame::Delimited { forest: delimited, idx: 0, span: span });
                 result_stack.push(mem::replace(&mut result, Vec::new()));
             }
-            quoted::TokenTree::Token(span, tok) => result.push(TokenTree::Token(span, tok).into()),
+            quoted::TokenTree::Token(sp, tok) => {
+                let mut marker = Marker(cx.current_expansion.mark);
+                result.push(noop_fold_tt(TokenTree::Token(sp, tok), &mut marker).into())
+            }
             quoted::TokenTree::MetaVarDecl(..) => panic!("unexpected `TokenTree::MetaVarDecl"),
         }
     }
@@ -240,7 +248,7 @@ fn lockstep_iter_size(tree: &quoted::TokenTree,
                 size + lockstep_iter_size(tt, interpolations, repeats)
             })
         },
-        TokenTree::Token(_, SubstNt(name)) | TokenTree::MetaVarDecl(_, name, _) =>
+        TokenTree::MetaVar(_, name) | TokenTree::MetaVarDecl(_, name, _) =>
             match lookup_cur_matched(name, interpolations, repeats) {
                 Some(matched) => match *matched {
                     MatchedNonterminal(_) => LockstepIterSize::Unconstrained,
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index df8ee189d21..4b0ec1a20e3 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -38,12 +38,19 @@ use symbol::Symbol;
 use std::ascii::AsciiExt;
 use std::env;
 
-macro_rules! setter {
+macro_rules! set {
+    (proc_macro) => {{
+        fn f(features: &mut Features, span: Span) {
+            features.declared_lib_features.push((Symbol::intern("proc_macro"), span));
+            features.proc_macro = true;
+        }
+        f as fn(&mut Features, Span)
+    }};
     ($field: ident) => {{
-        fn f(features: &mut Features) -> &mut bool {
-            &mut features.$field
+        fn f(features: &mut Features, _: Span) {
+            features.$field = true;
         }
-        f as fn(&mut Features) -> &mut bool
+        f as fn(&mut Features, Span)
     }}
 }
 
@@ -51,10 +58,9 @@ macro_rules! declare_features {
     ($((active, $feature: ident, $ver: expr, $issue: expr),)+) => {
         /// Represents active features that are currently being implemented or
         /// currently being considered for addition/removal.
-        const ACTIVE_FEATURES: &'static [(&'static str, &'static str,
-                                          Option<u32>, fn(&mut Features) -> &mut bool)] = &[
-            $((stringify!($feature), $ver, $issue, setter!($feature))),+
-        ];
+        const ACTIVE_FEATURES:
+                &'static [(&'static str, &'static str, Option<u32>, fn(&mut Features, Span))] =
+            &[$((stringify!($feature), $ver, $issue, set!($feature))),+];
 
         /// A set of features to be used by later passes.
         pub struct Features {
@@ -1478,9 +1484,9 @@ pub fn get_features(span_handler: &Handler, krate_attrs: &[ast::Attribute]) -> F
                         continue
                     };
 
-                    if let Some(&(_, _, _, setter)) = ACTIVE_FEATURES.iter()
+                    if let Some(&(_, _, _, set)) = ACTIVE_FEATURES.iter()
                         .find(|& &(n, _, _, _)| name == n) {
-                        *(setter(&mut features)) = true;
+                        set(&mut features, mi.span);
                         feature_checker.collect(&features, mi.span);
                     }
                     else if let Some(&(_, _, _)) = REMOVED_FEATURES.iter()
@@ -1514,7 +1520,7 @@ struct MutexFeatureChecker {
 
 impl MutexFeatureChecker {
     // If this method turns out to be a hotspot due to branching,
-    // the branching can be eliminated by modifying `setter!()` to set these spans
+    // the branching can be eliminated by modifying `set!()` to set these spans
     // only for the features that need to be checked for mutual exclusion.
     fn collect(&mut self, features: &Features, span: Span) {
         if features.proc_macro {
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 4c6cf49a8db..1fc670ec9f7 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -22,7 +22,7 @@ use ast::*;
 use ast;
 use syntax_pos::Span;
 use codemap::{Spanned, respan};
-use parse::token;
+use parse::token::{self, Token};
 use ptr::P;
 use symbol::keywords;
 use tokenstream::*;
@@ -573,7 +573,7 @@ pub fn noop_fold_tt<T: Folder>(tt: TokenTree, fld: &mut T) -> TokenTree {
 }
 
 pub fn noop_fold_tts<T: Folder>(tts: TokenStream, fld: &mut T) -> TokenStream {
-    tts.trees().map(|tt| fld.fold_tt(tt)).collect()
+    tts.map(|tt| fld.fold_tt(tt))
 }
 
 // apply ident folder if it's an ident, apply other folds to interpolated nodes
@@ -586,9 +586,8 @@ pub fn noop_fold_token<T: Folder>(t: token::Token, fld: &mut T) -> token::Token
                 Ok(nt) => nt,
                 Err(nt) => (*nt).clone(),
             };
-            token::Interpolated(Rc::new(fld.fold_interpolated(nt)))
+            Token::interpolated(fld.fold_interpolated(nt.0))
         }
-        token::SubstNt(ident) => token::SubstNt(fld.fold_ident(ident)),
         _ => t
     }
 }
diff --git a/src/libsyntax/parse/attr.rs b/src/libsyntax/parse/attr.rs
index 082930777e5..c99a09ab24e 100644
--- a/src/libsyntax/parse/attr.rs
+++ b/src/libsyntax/parse/attr.rs
@@ -151,7 +151,7 @@ impl<'a> Parser<'a> {
 
     pub fn parse_path_and_tokens(&mut self) -> PResult<'a, (ast::Path, TokenStream)> {
         let meta = match self.token {
-            token::Interpolated(ref nt) => match **nt {
+            token::Interpolated(ref nt) => match nt.0 {
                 Nonterminal::NtMeta(ref meta) => Some(meta.clone()),
                 _ => None,
             },
@@ -223,7 +223,7 @@ impl<'a> Parser<'a> {
     /// meta_item_inner : (meta_item | UNSUFFIXED_LIT) (',' meta_item_inner)? ;
     pub fn parse_meta_item(&mut self) -> PResult<'a, ast::MetaItem> {
         let nt_meta = match self.token {
-            token::Interpolated(ref nt) => match **nt {
+            token::Interpolated(ref nt) => match nt.0 {
                 token::NtMeta(ref e) => Some(e.clone()),
                 _ => None,
             },
diff --git a/src/libsyntax/parse/lexer/mod.rs b/src/libsyntax/parse/lexer/mod.rs
index a35b278a4b0..09cdf26bf1f 100644
--- a/src/libsyntax/parse/lexer/mod.rs
+++ b/src/libsyntax/parse/lexer/mod.rs
@@ -66,14 +66,15 @@ pub struct StringReader<'a> {
     token: token::Token,
     span: Span,
     open_braces: Vec<(token::DelimToken, Span)>,
-}
-
-fn mk_sp(lo: BytePos, hi: BytePos) -> Span {
-    Span { lo: lo, hi: hi, ctxt: NO_EXPANSION }
+    pub override_span: Option<Span>,
 }
 
 impl<'a> StringReader<'a> {
-    fn next_token(&mut self) -> TokenAndSpan {
+    fn mk_sp(&self, lo: BytePos, hi: BytePos) -> Span {
+        unwrap_or!(self.override_span, Span { lo: lo, hi: hi, ctxt: NO_EXPANSION})
+    }
+
+    fn next_token(&mut self) -> TokenAndSpan where Self: Sized {
         let res = self.try_next_token();
         self.unwrap_or_abort(res)
     }
@@ -175,6 +176,7 @@ impl<'a> StringReader<'a> {
             token: token::Eof,
             span: syntax_pos::DUMMY_SP,
             open_braces: Vec::new(),
+            override_span: None,
         }
     }
 
@@ -229,12 +231,12 @@ impl<'a> StringReader<'a> {
 
     /// Report a fatal error spanning [`from_pos`, `to_pos`).
     fn fatal_span_(&self, from_pos: BytePos, to_pos: BytePos, m: &str) -> FatalError {
-        self.fatal_span(mk_sp(from_pos, to_pos), m)
+        self.fatal_span(self.mk_sp(from_pos, to_pos), m)
     }
 
     /// Report a lexical error spanning [`from_pos`, `to_pos`).
     fn err_span_(&self, from_pos: BytePos, to_pos: BytePos, m: &str) {
-        self.err_span(mk_sp(from_pos, to_pos), m)
+        self.err_span(self.mk_sp(from_pos, to_pos), m)
     }
 
     /// Report a lexical error spanning [`from_pos`, `to_pos`), appending an
@@ -258,7 +260,7 @@ impl<'a> StringReader<'a> {
         for c in c.escape_default() {
             m.push(c)
         }
-        self.sess.span_diagnostic.struct_span_fatal(mk_sp(from_pos, to_pos), &m[..])
+        self.sess.span_diagnostic.struct_span_fatal(self.mk_sp(from_pos, to_pos), &m[..])
     }
 
     /// Report a lexical error spanning [`from_pos`, `to_pos`), appending an
@@ -282,7 +284,7 @@ impl<'a> StringReader<'a> {
         for c in c.escape_default() {
             m.push(c)
         }
-        self.sess.span_diagnostic.struct_span_err(mk_sp(from_pos, to_pos), &m[..])
+        self.sess.span_diagnostic.struct_span_err(self.mk_sp(from_pos, to_pos), &m[..])
     }
 
     /// Report a lexical error spanning [`from_pos`, `to_pos`), appending the
@@ -306,11 +308,11 @@ impl<'a> StringReader<'a> {
             None => {
                 if self.is_eof() {
                     self.peek_tok = token::Eof;
-                    self.peek_span = mk_sp(self.filemap.end_pos, self.filemap.end_pos);
+                    self.peek_span = self.mk_sp(self.filemap.end_pos, self.filemap.end_pos);
                 } else {
                     let start_bytepos = self.pos;
                     self.peek_tok = self.next_token_inner()?;
-                    self.peek_span = mk_sp(start_bytepos, self.pos);
+                    self.peek_span = self.mk_sp(start_bytepos, self.pos);
                 };
             }
         }
@@ -481,7 +483,7 @@ impl<'a> StringReader<'a> {
         self.with_str_from(start, |string| {
             if string == "_" {
                 self.sess.span_diagnostic
-                    .struct_span_warn(mk_sp(start, self.pos),
+                    .struct_span_warn(self.mk_sp(start, self.pos),
                                       "underscore literal suffix is not allowed")
                     .warn("this was previously accepted by the compiler but is \
                           being phased out; it will become a hard error in \
@@ -502,7 +504,7 @@ impl<'a> StringReader<'a> {
         if let Some(c) = self.ch {
             if c.is_whitespace() {
                 let msg = "called consume_any_line_comment, but there was whitespace";
-                self.sess.span_diagnostic.span_err(mk_sp(self.pos, self.pos), msg);
+                self.sess.span_diagnostic.span_err(self.mk_sp(self.pos, self.pos), msg);
             }
         }
 
@@ -545,13 +547,13 @@ impl<'a> StringReader<'a> {
 
                             Some(TokenAndSpan {
                                 tok: tok,
-                                sp: mk_sp(start_bpos, self.pos),
+                                sp: self.mk_sp(start_bpos, self.pos),
                             })
                         })
                     } else {
                         Some(TokenAndSpan {
                             tok: token::Comment,
-                            sp: mk_sp(start_bpos, self.pos),
+                            sp: self.mk_sp(start_bpos, self.pos),
                         })
                     }
                 }
@@ -584,7 +586,7 @@ impl<'a> StringReader<'a> {
                     }
                     return Some(TokenAndSpan {
                         tok: token::Shebang(self.name_from(start)),
-                        sp: mk_sp(start, self.pos),
+                        sp: self.mk_sp(start, self.pos),
                     });
                 }
             }
@@ -612,7 +614,7 @@ impl<'a> StringReader<'a> {
                 }
                 let c = Some(TokenAndSpan {
                     tok: token::Whitespace,
-                    sp: mk_sp(start_bpos, self.pos),
+                    sp: self.mk_sp(start_bpos, self.pos),
                 });
                 debug!("scanning whitespace: {:?}", c);
                 c
@@ -674,7 +676,7 @@ impl<'a> StringReader<'a> {
 
             Some(TokenAndSpan {
                 tok: tok,
-                sp: mk_sp(start_bpos, self.pos),
+                sp: self.mk_sp(start_bpos, self.pos),
             })
         })
     }
@@ -869,7 +871,7 @@ impl<'a> StringReader<'a> {
                                 let valid = if self.ch_is('{') {
                                     self.scan_unicode_escape(delim) && !ascii_only
                                 } else {
-                                    let span = mk_sp(start, self.pos);
+                                    let span = self.mk_sp(start, self.pos);
                                     self.sess.span_diagnostic
                                         .struct_span_err(span, "incorrect unicode escape sequence")
                                         .span_help(span,
@@ -907,13 +909,13 @@ impl<'a> StringReader<'a> {
                                                                         },
                                                                         c);
                                 if e == '\r' {
-                                    err.span_help(mk_sp(escaped_pos, pos),
+                                    err.span_help(self.mk_sp(escaped_pos, pos),
                                                   "this is an isolated carriage return; consider \
                                                    checking your editor and version control \
                                                    settings");
                                 }
                                 if (e == '{' || e == '}') && !ascii_only {
-                                    err.span_help(mk_sp(escaped_pos, pos),
+                                    err.span_help(self.mk_sp(escaped_pos, pos),
                                                   "if used in a formatting string, curly braces \
                                                    are escaped with `{{` and `}}`");
                                 }
diff --git a/src/libsyntax/parse/lexer/tokentrees.rs b/src/libsyntax/parse/lexer/tokentrees.rs
index 554a1fcfc71..63a396c14db 100644
--- a/src/libsyntax/parse/lexer/tokentrees.rs
+++ b/src/libsyntax/parse/lexer/tokentrees.rs
@@ -19,7 +19,9 @@ impl<'a> StringReader<'a> {
     pub fn parse_all_token_trees(&mut self) -> PResult<'a, TokenStream> {
         let mut tts = Vec::new();
         while self.token != token::Eof {
-            tts.push(self.parse_token_tree()?.into());
+            let tree = self.parse_token_tree()?;
+            let is_joint = tree.span().hi == self.span.lo && token::is_op(&self.token);
+            tts.push(if is_joint { tree.joint() } else { tree.into() });
         }
         Ok(TokenStream::concat(tts))
     }
@@ -31,13 +33,15 @@ impl<'a> StringReader<'a> {
             if let token::CloseDelim(..) = self.token {
                 return TokenStream::concat(tts);
             }
-            match self.parse_token_tree() {
-                Ok(tt) => tts.push(tt.into()),
+            let tree = match self.parse_token_tree() {
+                Ok(tree) => tree,
                 Err(mut e) => {
                     e.emit();
                     return TokenStream::concat(tts);
                 }
-            }
+            };
+            let is_joint = tree.span().hi == self.span.lo && token::is_op(&self.token);
+            tts.push(if is_joint { tree.joint() } else { tree.into() });
         }
     }
 
diff --git a/src/libsyntax/parse/mod.rs b/src/libsyntax/parse/mod.rs
index 3a68a6ba764..bd9a621c00c 100644
--- a/src/libsyntax/parse/mod.rs
+++ b/src/libsyntax/parse/mod.rs
@@ -141,9 +141,10 @@ pub fn parse_stmt_from_source_str(name: String, source: String, sess: &ParseSess
     new_parser_from_source_str(sess, name, source).parse_stmt()
 }
 
-pub fn parse_stream_from_source_str(name: String, source: String, sess: &ParseSess)
-                                        -> TokenStream {
-    filemap_to_stream(sess, sess.codemap().new_filemap(name, source))
+pub fn parse_stream_from_source_str(name: String, source: String, sess: &ParseSess,
+                                    override_span: Option<Span>)
+                                    -> TokenStream {
+    filemap_to_stream(sess, sess.codemap().new_filemap(name, source), override_span)
 }
 
 // Create a new parser from a source string
@@ -177,7 +178,7 @@ pub fn new_sub_parser_from_file<'a>(sess: &'a ParseSess,
 /// Given a filemap and config, return a parser
 pub fn filemap_to_parser(sess: & ParseSess, filemap: Rc<FileMap>, ) -> Parser {
     let end_pos = filemap.end_pos;
-    let mut parser = stream_to_parser(sess, filemap_to_stream(sess, filemap));
+    let mut parser = stream_to_parser(sess, filemap_to_stream(sess, filemap, None));
 
     if parser.token == token::Eof && parser.span == syntax_pos::DUMMY_SP {
         parser.span = Span { lo: end_pos, hi: end_pos, ctxt: NO_EXPANSION };
@@ -212,8 +213,10 @@ fn file_to_filemap(sess: &ParseSess, path: &Path, spanopt: Option<Span>)
 }
 
 /// Given a filemap, produce a sequence of token-trees
-pub fn filemap_to_stream(sess: &ParseSess, filemap: Rc<FileMap>) -> TokenStream {
+pub fn filemap_to_stream(sess: &ParseSess, filemap: Rc<FileMap>, override_span: Option<Span>)
+                         -> TokenStream {
     let mut srdr = lexer::StringReader::new(sess, filemap);
+    srdr.override_span = override_span;
     srdr.real_token();
     panictry!(srdr.parse_all_token_trees())
 }
@@ -684,7 +687,7 @@ mod tests {
                     id: ast::DUMMY_NODE_ID,
                     node: ast::ExprKind::Path(None, ast::Path {
                         span: sp(0, 6),
-                        segments: vec![ast::PathSegment::crate_root(),
+                        segments: vec![ast::PathSegment::crate_root(sp(0, 2)),
                                        str2seg("a", 2, 3),
                                        str2seg("b", 5, 6)]
                     }),
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 64506c4af46..c248e20b608 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -107,7 +107,7 @@ pub enum BlockMode {
 macro_rules! maybe_whole_expr {
     ($p:expr) => {
         if let token::Interpolated(nt) = $p.token.clone() {
-            match *nt {
+            match nt.0 {
                 token::NtExpr(ref e) => {
                     $p.bump();
                     return Ok((*e).clone());
@@ -134,7 +134,7 @@ macro_rules! maybe_whole_expr {
 macro_rules! maybe_whole {
     ($p:expr, $constructor:ident, |$x:ident| $e:expr) => {
         if let token::Interpolated(nt) = $p.token.clone() {
-            if let token::$constructor($x) = (*nt).clone() {
+            if let token::$constructor($x) = nt.0.clone() {
                 $p.bump();
                 return Ok($e);
             }
@@ -1602,7 +1602,7 @@ impl<'a> Parser<'a> {
     /// Matches token_lit = LIT_INTEGER | ...
     pub fn parse_lit_token(&mut self) -> PResult<'a, LitKind> {
         let out = match self.token {
-            token::Interpolated(ref nt) => match **nt {
+            token::Interpolated(ref nt) => match nt.0 {
                 token::NtExpr(ref v) => match v.node {
                     ExprKind::Lit(ref lit) => { lit.node.clone() }
                     _ => { return self.unexpected_last(&self.token); }
@@ -1761,7 +1761,7 @@ impl<'a> Parser<'a> {
         };
 
         if is_global {
-            segments.insert(0, PathSegment::crate_root());
+            segments.insert(0, PathSegment::crate_root(lo));
         }
 
         // Assemble the result.
@@ -1775,7 +1775,7 @@ impl<'a> Parser<'a> {
     /// This is used when parsing derive macro paths in `#[derive]` attributes.
     pub fn parse_path_allowing_meta(&mut self, mode: PathStyle) -> PResult<'a, ast::Path> {
         let meta_ident = match self.token {
-            token::Interpolated(ref nt) => match **nt {
+            token::Interpolated(ref nt) => match nt.0 {
                 token::NtMeta(ref meta) => match meta.node {
                     ast::MetaItemKind::Word => Some(ast::Ident::with_empty_ctxt(meta.name)),
                     _ => None,
@@ -2610,13 +2610,16 @@ impl<'a> Parser<'a> {
 
     pub fn process_potential_macro_variable(&mut self) {
         let ident = match self.token {
-            token::SubstNt(name) => {
+            token::Dollar if self.span.ctxt != syntax_pos::hygiene::SyntaxContext::empty() &&
+                             self.look_ahead(1, |t| t.is_ident()) => {
+                self.bump();
+                let name = match self.token { token::Ident(ident) => ident, _ => unreachable!() };
                 self.fatal(&format!("unknown macro variable `{}`", name)).emit();
                 return
             }
             token::Interpolated(ref nt) => {
                 self.meta_var_span = Some(self.span);
-                match **nt {
+                match nt.0 {
                     token::NtIdent(ident) => ident,
                     _ => return,
                 }
@@ -6168,7 +6171,7 @@ impl<'a> Parser<'a> {
             // `{foo, bar}`, `::{foo, bar}`, `*`, or `::*`.
             self.eat(&token::ModSep);
             let prefix = ast::Path {
-                segments: vec![PathSegment::crate_root()],
+                segments: vec![PathSegment::crate_root(lo)],
                 span: lo.to(self.span),
             };
             let view_path_kind = if self.eat(&token::BinOp(token::Star)) {
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index 75969cf2eb8..834ac38af98 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -16,10 +16,12 @@ pub use self::Token::*;
 
 use ast::{self};
 use ptr::P;
+use serialize::{Decodable, Decoder, Encodable, Encoder};
 use symbol::keywords;
-use tokenstream::TokenTree;
+use tokenstream::{TokenStream, TokenTree};
 
-use std::fmt;
+use std::cell::Cell;
+use std::{cmp, fmt};
 use std::rc::Rc;
 
 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Debug, Copy)]
@@ -167,14 +169,12 @@ pub enum Token {
     Underscore,
     Lifetime(ast::Ident),
 
-    /* For interpolation */
-    Interpolated(Rc<Nonterminal>),
+    // The `LazyTokenStream` is a pure function of the `Nonterminal`,
+    // and so the `LazyTokenStream` can be ignored by Eq, Hash, etc.
+    Interpolated(Rc<(Nonterminal, LazyTokenStream)>),
     // Can be expanded into several tokens.
     /// Doc comment
     DocComment(ast::Name),
-    // In right-hand-sides of MBE macros:
-    /// A syntactic variable that will be filled in by macro expansion.
-    SubstNt(ast::Ident),
 
     // Junk. These carry no data because we don't really care about the data
     // they *would* carry, and don't really want to allocate a new ident for
@@ -190,6 +190,10 @@ pub enum Token {
 }
 
 impl Token {
+    pub fn interpolated(nt: Nonterminal) -> Token {
+        Token::Interpolated(Rc::new((nt, LazyTokenStream::new())))
+    }
+
     /// Returns `true` if the token starts with '>'.
     pub fn is_like_gt(&self) -> bool {
         match *self {
@@ -214,7 +218,7 @@ impl Token {
             Lt | BinOp(Shl)             | // associated path
             ModSep                      | // global path
             Pound                       => true, // expression attributes
-            Interpolated(ref nt) => match **nt {
+            Interpolated(ref nt) => match nt.0 {
                 NtIdent(..) | NtExpr(..) | NtBlock(..) | NtPath(..) => true,
                 _ => false,
             },
@@ -237,7 +241,7 @@ impl Token {
             Lifetime(..)                | // lifetime bound in trait object
             Lt | BinOp(Shl)             | // associated path
             ModSep                      => true, // global path
-            Interpolated(ref nt) => match **nt {
+            Interpolated(ref nt) => match nt.0 {
                 NtIdent(..) | NtTy(..) | NtPath(..) => true,
                 _ => false,
             },
@@ -256,7 +260,7 @@ impl Token {
     pub fn ident(&self) -> Option<ast::Ident> {
         match *self {
             Ident(ident) => Some(ident),
-            Interpolated(ref nt) => match **nt {
+            Interpolated(ref nt) => match nt.0 {
                 NtIdent(ident) => Some(ident.node),
                 _ => None,
             },
@@ -288,7 +292,7 @@ impl Token {
     /// Returns `true` if the token is an interpolated path.
     pub fn is_path(&self) -> bool {
         if let Interpolated(ref nt) = *self {
-            if let NtPath(..) = **nt {
+            if let NtPath(..) = nt.0 {
                 return true;
             }
         }
@@ -358,6 +362,60 @@ impl Token {
         }
     }
 
+    pub fn glue(self, joint: Token) -> Option<Token> {
+        Some(match self {
+            Eq => match joint {
+                Eq => EqEq,
+                Gt => FatArrow,
+                _ => return None,
+            },
+            Lt => match joint {
+                Eq => Le,
+                Lt => BinOp(Shl),
+                Le => BinOpEq(Shl),
+                BinOp(Minus) => LArrow,
+                _ => return None,
+            },
+            Gt => match joint {
+                Eq => Ge,
+                Gt => BinOp(Shr),
+                Ge => BinOpEq(Shr),
+                _ => return None,
+            },
+            Not => match joint {
+                Eq => Ne,
+                _ => return None,
+            },
+            BinOp(op) => match joint {
+                Eq => BinOpEq(op),
+                BinOp(And) if op == And => AndAnd,
+                BinOp(Or) if op == Or => OrOr,
+                Gt if op == Minus => RArrow,
+                _ => return None,
+            },
+            Dot => match joint {
+                Dot => DotDot,
+                DotDot => DotDotDot,
+                _ => return None,
+            },
+            DotDot => match joint {
+                Dot => DotDotDot,
+                _ => return None,
+            },
+            Colon => match joint {
+                Colon => ModSep,
+                _ => return None,
+            },
+
+            Le | EqEq | Ne | Ge | AndAnd | OrOr | Tilde | BinOpEq(..) | At | DotDotDot | Comma |
+            Semi | ModSep | RArrow | LArrow | FatArrow | Pound | Dollar | Question |
+            OpenDelim(..) | CloseDelim(..) | Underscore => return None,
+
+            Literal(..) | Ident(..) | Lifetime(..) | Interpolated(..) | DocComment(..) |
+            Whitespace | Comment | Shebang(..) | Eof => return None,
+        })
+    }
+
     /// Returns `true` if the token is either a special identifier or a keyword.
     pub fn is_reserved_ident(&self) -> bool {
         self.is_special_ident() || self.is_used_keyword() || self.is_unused_keyword()
@@ -411,3 +469,66 @@ impl fmt::Debug for Nonterminal {
         }
     }
 }
+
+pub fn is_op(tok: &Token) -> bool {
+    match *tok {
+        OpenDelim(..) | CloseDelim(..) | Literal(..) | DocComment(..) |
+        Ident(..) | Underscore | Lifetime(..) | Interpolated(..) |
+        Whitespace | Comment | Shebang(..) | Eof => false,
+        _ => true,
+    }
+}
+
+pub struct LazyTokenStream(Cell<Option<TokenStream>>);
+
+impl Clone for LazyTokenStream {
+    fn clone(&self) -> Self {
+        let opt_stream = self.0.take();
+        self.0.set(opt_stream.clone());
+        LazyTokenStream(Cell::new(opt_stream))
+    }
+}
+
+impl cmp::Eq for LazyTokenStream {}
+impl PartialEq for LazyTokenStream {
+    fn eq(&self, _other: &LazyTokenStream) -> bool {
+        true
+    }
+}
+
+impl fmt::Debug for LazyTokenStream {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Debug::fmt(&self.clone().0.into_inner(), f)
+    }
+}
+
+impl LazyTokenStream {
+    pub fn new() -> Self {
+        LazyTokenStream(Cell::new(None))
+    }
+
+    pub fn force<F: FnOnce() -> TokenStream>(&self, f: F) -> TokenStream {
+        let mut opt_stream = self.0.take();
+        if opt_stream.is_none() {
+            opt_stream = Some(f());
+        }
+        self.0.set(opt_stream.clone());
+        opt_stream.clone().unwrap()
+    }
+}
+
+impl Encodable for LazyTokenStream {
+    fn encode<S: Encoder>(&self, _: &mut S) -> Result<(), S::Error> {
+        Ok(())
+    }
+}
+
+impl Decodable for LazyTokenStream {
+    fn decode<D: Decoder>(_: &mut D) -> Result<LazyTokenStream, D::Error> {
+        Ok(LazyTokenStream::new())
+    }
+}
+
+impl ::std::hash::Hash for LazyTokenStream {
+    fn hash<H: ::std::hash::Hasher>(&self, _hasher: &mut H) {}
+}
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 6c00e0b9efd..d449e412d6c 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -270,13 +270,12 @@ pub fn token_to_string(tok: &Token) -> String {
 
         /* Other */
         token::DocComment(s)        => s.to_string(),
-        token::SubstNt(s)           => format!("${}", s),
         token::Eof                  => "<eof>".to_string(),
         token::Whitespace           => " ".to_string(),
         token::Comment              => "/* */".to_string(),
         token::Shebang(s)           => format!("/* shebang: {}*/", s),
 
-        token::Interpolated(ref nt) => match **nt {
+        token::Interpolated(ref nt) => match nt.0 {
             token::NtExpr(ref e)        => expr_to_string(e),
             token::NtMeta(ref e)        => meta_item_to_string(e),
             token::NtTy(ref e)          => ty_to_string(e),
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),
         })
     }
diff --git a/src/libsyntax/util/parser_testing.rs b/src/libsyntax/util/parser_testing.rs
index 2727ab79ebf..d993ba14a4a 100644
--- a/src/libsyntax/util/parser_testing.rs
+++ b/src/libsyntax/util/parser_testing.rs
@@ -20,7 +20,7 @@ use std::iter::Peekable;
 /// Map a string to tts, using a made-up filename:
 pub fn string_to_stream(source_str: String) -> TokenStream {
     let ps = ParseSess::new(FilePathMapping::empty());
-    filemap_to_stream(&ps, ps.codemap().new_filemap("bogofile".to_string(), source_str))
+    filemap_to_stream(&ps, ps.codemap().new_filemap("bogofile".to_string(), source_str), None)
 }
 
 /// Map string to parser (via tts)
diff --git a/src/libsyntax/util/rc_slice.rs b/src/libsyntax/util/rc_slice.rs
index 2d9fd7aa875..d6939d71129 100644
--- a/src/libsyntax/util/rc_slice.rs
+++ b/src/libsyntax/util/rc_slice.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use std::fmt;
-use std::ops::Deref;
+use std::ops::{Deref, Range};
 use std::rc::Rc;
 
 use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult,
@@ -30,6 +30,14 @@ impl<T> RcSlice<T> {
             data: Rc::new(vec.into_boxed_slice()),
         }
     }
+
+    pub fn sub_slice(&self, range: Range<usize>) -> Self {
+        RcSlice {
+            data: self.data.clone(),
+            offset: self.offset + range.start as u32,
+            len: (range.end - range.start) as u32,
+        }
+    }
 }
 
 impl<T> Deref for RcSlice<T> {