Refactored tokentrees into their own files in preparation for tokenstreams. Modified tests to point to the new file now.

34 files changed, 342 insertions, 287 deletions

diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index 8faa1cc1174..2ce01a0b255 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -38,11 +38,12 @@ use util::nodemap::{NodeMap, FnvHashSet};
 
 use syntax::codemap::{self, mk_sp, respan, Span, Spanned, ExpnId};
 use syntax::abi::Abi;
-use syntax::ast::{Name, NodeId, DUMMY_NODE_ID, TokenTree, AsmDialect};
+use syntax::ast::{Name, NodeId, DUMMY_NODE_ID, AsmDialect};
 use syntax::ast::{Attribute, Lit, StrStyle, FloatTy, IntTy, UintTy, MetaItem};
 use syntax::attr::{ThinAttributes, ThinAttributesExt};
 use syntax::parse::token::{keywords, InternedString};
 use syntax::ptr::P;
+use syntax::tokenstream::TokenTree;
 
 use std::collections::BTreeMap;
 use std::fmt;
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 8537fcc221c..2ad33a4d98e 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -19,13 +19,10 @@ use attr::{ThinAttributes, HasAttrs};
 use codemap::{mk_sp, respan, Span, Spanned, DUMMY_SP, ExpnId};
 use abi::Abi;
 use errors;
-use ext::base;
-use ext::tt::macro_parser;
 use parse::token::{self, keywords, InternedString};
-use parse::lexer;
-use parse::lexer::comments::{doc_comment_style, strip_doc_comment_decoration};
 use print::pprust;
 use ptr::P;
+use tokenstream::{TokenTree};
 
 use std::fmt;
 use std::rc::Rc;
@@ -1097,193 +1094,6 @@ pub enum CaptureBy {
     Ref,
 }
 
-/// A delimited sequence of token trees
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
-pub struct Delimited {
-    /// The type of delimiter
-    pub delim: token::DelimToken,
-    /// The span covering the opening delimiter
-    pub open_span: Span,
-    /// The delimited sequence of token trees
-    pub tts: Vec<TokenTree>,
-    /// The span covering the closing delimiter
-    pub close_span: Span,
-}
-
-impl Delimited {
-    /// Returns the opening delimiter as a token.
-    pub fn open_token(&self) -> token::Token {
-        token::OpenDelim(self.delim)
-    }
-
-    /// Returns the closing delimiter as a token.
-    pub fn close_token(&self) -> token::Token {
-        token::CloseDelim(self.delim)
-    }
-
-    /// Returns the opening delimiter as a token tree.
-    pub fn open_tt(&self) -> TokenTree {
-        TokenTree::Token(self.open_span, self.open_token())
-    }
-
-    /// Returns the closing delimiter as a token tree.
-    pub fn close_tt(&self) -> TokenTree {
-        TokenTree::Token(self.close_span, self.close_token())
-    }
-}
-
-/// A sequence of token trees
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
-pub struct SequenceRepetition {
-    /// The sequence of token trees
-    pub tts: Vec<TokenTree>,
-    /// The optional separator
-    pub separator: Option<token::Token>,
-    /// Whether the sequence can be repeated zero (*), or one or more times (+)
-    pub op: KleeneOp,
-    /// The number of `MatchNt`s that appear in the sequence (and subsequences)
-    pub num_captures: usize,
-}
-
-/// A Kleene-style [repetition operator](http://en.wikipedia.org/wiki/Kleene_star)
-/// for token sequences.
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
-pub enum KleeneOp {
-    ZeroOrMore,
-    OneOrMore,
-}
-
-/// When the main rust parser encounters a syntax-extension invocation, it
-/// parses the arguments to the invocation as a token-tree. This is a very
-/// loose structure, such that all sorts of different AST-fragments can
-/// be passed to syntax extensions using a uniform type.
-///
-/// If the syntax extension is an MBE macro, it will attempt to match its
-/// LHS token tree against the provided token tree, and if it finds a
-/// match, will transcribe the RHS token tree, splicing in any captured
-/// macro_parser::matched_nonterminals into the `SubstNt`s it finds.
-///
-/// The RHS of an MBE macro is the only place `SubstNt`s are substituted.
-/// Nothing special happens to misnamed or misplaced `SubstNt`s.
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
-pub enum TokenTree {
-    /// A single token
-    Token(Span, token::Token),
-    /// A delimited sequence of token trees
-    Delimited(Span, Rc<Delimited>),
-
-    // This only makes sense in MBE macros.
-
-    /// A kleene-style repetition sequence with a span
-    // FIXME(eddyb) #12938 Use DST.
-    Sequence(Span, Rc<SequenceRepetition>),
-}
-
-impl TokenTree {
-    pub fn len(&self) -> usize {
-        match *self {
-            TokenTree::Token(_, token::DocComment(name)) => {
-                match doc_comment_style(&name.as_str()) {
-                    AttrStyle::Outer => 2,
-                    AttrStyle::Inner => 3
-                }
-            }
-            TokenTree::Token(_, token::SpecialVarNt(..)) => 2,
-            TokenTree::Token(_, token::MatchNt(..)) => 3,
-            TokenTree::Delimited(_, ref delimed) => {
-                delimed.tts.len() + 2
-            }
-            TokenTree::Sequence(_, ref seq) => {
-                seq.tts.len()
-            }
-            TokenTree::Token(..) => 0
-        }
-    }
-
-    pub fn get_tt(&self, index: usize) -> TokenTree {
-        match (self, index) {
-            (&TokenTree::Token(sp, token::DocComment(_)), 0) => {
-                TokenTree::Token(sp, token::Pound)
-            }
-            (&TokenTree::Token(sp, token::DocComment(name)), 1)
-            if doc_comment_style(&name.as_str()) == AttrStyle::Inner => {
-                TokenTree::Token(sp, token::Not)
-            }
-            (&TokenTree::Token(sp, token::DocComment(name)), _) => {
-                let stripped = strip_doc_comment_decoration(&name.as_str());
-
-                // Searches for the occurrences of `"#*` and returns the minimum number of `#`s
-                // required to wrap the text.
-                let num_of_hashes = stripped.chars().scan(0, |cnt, x| {
-                    *cnt = if x == '"' {
-                        1
-                    } else if *cnt != 0 && x == '#' {
-                        *cnt + 1
-                    } else {
-                        0
-                    };
-                    Some(*cnt)
-                }).max().unwrap_or(0);
-
-                TokenTree::Delimited(sp, Rc::new(Delimited {
-                    delim: token::Bracket,
-                    open_span: sp,
-                    tts: vec![TokenTree::Token(sp, token::Ident(token::str_to_ident("doc"))),
-                              TokenTree::Token(sp, token::Eq),
-                              TokenTree::Token(sp, token::Literal(
-                                  token::StrRaw(token::intern(&stripped), num_of_hashes), None))],
-                    close_span: sp,
-                }))
-            }
-            (&TokenTree::Delimited(_, ref delimed), _) => {
-                if index == 0 {
-                    return delimed.open_tt();
-                }
-                if index == delimed.tts.len() + 1 {
-                    return delimed.close_tt();
-                }
-                delimed.tts[index - 1].clone()
-            }
-            (&TokenTree::Token(sp, token::SpecialVarNt(var)), _) => {
-                let v = [TokenTree::Token(sp, token::Dollar),
-                         TokenTree::Token(sp, token::Ident(token::str_to_ident(var.as_str())))];
-                v[index].clone()
-            }
-            (&TokenTree::Token(sp, token::MatchNt(name, kind)), _) => {
-                let v = [TokenTree::Token(sp, token::SubstNt(name)),
-                         TokenTree::Token(sp, token::Colon),
-                         TokenTree::Token(sp, token::Ident(kind))];
-                v[index].clone()
-            }
-            (&TokenTree::Sequence(_, ref seq), _) => {
-                seq.tts[index].clone()
-            }
-            _ => panic!("Cannot expand a token tree")
-        }
-    }
-
-    /// Returns the `Span` corresponding to this token tree.
-    pub fn get_span(&self) -> Span {
-        match *self {
-            TokenTree::Token(span, _)     => span,
-            TokenTree::Delimited(span, _) => span,
-            TokenTree::Sequence(span, _)  => span,
-        }
-    }
-
-    /// Use this token tree as a matcher to parse given tts.
-    pub fn parse(cx: &base::ExtCtxt, mtch: &[TokenTree], tts: &[TokenTree])
-                 -> macro_parser::NamedParseResult {
-        // `None` is because we're not interpolating
-        let arg_rdr = lexer::new_tt_reader_with_doc_flag(&cx.parse_sess().span_diagnostic,
-                                                         None,
-                                                         None,
-                                                         tts.iter().cloned().collect(),
-                                                         true);
-        macro_parser::parse(cx.parse_sess(), cx.cfg(), arg_rdr, mtch)
-    }
-}
-
 pub type Mac = Spanned<Mac_>;
 
 /// Represents a macro invocation. The Path indicates which macro
diff --git a/src/libsyntax/diagnostics/plugin.rs b/src/libsyntax/diagnostics/plugin.rs
index 26088b1242e..4831d40df06 100644
--- a/src/libsyntax/diagnostics/plugin.rs
+++ b/src/libsyntax/diagnostics/plugin.rs
@@ -13,12 +13,13 @@ use std::collections::BTreeMap;
 use std::env;
 
 use ast;
-use ast::{Ident, Name, TokenTree};
+use ast::{Ident, Name};
 use codemap::Span;
 use ext::base::{ExtCtxt, MacEager, MacResult};
 use ext::build::AstBuilder;
 use parse::token;
 use ptr::P;
+use tokenstream::{TokenTree};
 use util::small_vector::SmallVector;
 
 use diagnostics::metadata::output_metadata;
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 5da81a269ab..98b6e0762c5 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -31,6 +31,7 @@ use fold::Folder;
 use std::collections::{HashMap, HashSet};
 use std::rc::Rc;
 use std::default::Default;
+use tokenstream;
 
 
 #[derive(Debug,Clone)]
@@ -163,20 +164,22 @@ pub trait TTMacroExpander {
     fn expand<'cx>(&self,
                    ecx: &'cx mut ExtCtxt,
                    span: Span,
-                   token_tree: &[ast::TokenTree])
+                   token_tree: &[tokenstream::TokenTree])
                    -> Box<MacResult+'cx>;
 }
 
 pub type MacroExpanderFn =
-    for<'cx> fn(&'cx mut ExtCtxt, Span, &[ast::TokenTree]) -> Box<MacResult+'cx>;
+    for<'cx> fn(&'cx mut ExtCtxt, Span, &[tokenstream::TokenTree])
+                -> Box<MacResult+'cx>;
 
 impl<F> TTMacroExpander for F
-    where F : for<'cx> Fn(&'cx mut ExtCtxt, Span, &[ast::TokenTree]) -> Box<MacResult+'cx>
+    where F : for<'cx> Fn(&'cx mut ExtCtxt, Span, &[tokenstream::TokenTree])
+                          -> Box<MacResult+'cx>
 {
     fn expand<'cx>(&self,
                    ecx: &'cx mut ExtCtxt,
                    span: Span,
-                   token_tree: &[ast::TokenTree])
+                   token_tree: &[tokenstream::TokenTree])
                    -> Box<MacResult+'cx> {
         (*self)(ecx, span, token_tree)
     }
@@ -187,22 +190,23 @@ pub trait IdentMacroExpander {
                    cx: &'cx mut ExtCtxt,
                    sp: Span,
                    ident: ast::Ident,
-                   token_tree: Vec<ast::TokenTree> )
+                   token_tree: Vec<tokenstream::TokenTree> )
                    -> Box<MacResult+'cx>;
 }
 
 pub type IdentMacroExpanderFn =
-    for<'cx> fn(&'cx mut ExtCtxt, Span, ast::Ident, Vec<ast::TokenTree>) -> Box<MacResult+'cx>;
+    for<'cx> fn(&'cx mut ExtCtxt, Span, ast::Ident, Vec<tokenstream::TokenTree>)
+                -> Box<MacResult+'cx>;
 
 impl<F> IdentMacroExpander for F
     where F : for<'cx> Fn(&'cx mut ExtCtxt, Span, ast::Ident,
-                          Vec<ast::TokenTree>) -> Box<MacResult+'cx>
+                          Vec<tokenstream::TokenTree>) -> Box<MacResult+'cx>
 {
     fn expand<'cx>(&self,
                    cx: &'cx mut ExtCtxt,
                    sp: Span,
                    ident: ast::Ident,
-                   token_tree: Vec<ast::TokenTree> )
+                   token_tree: Vec<tokenstream::TokenTree> )
                    -> Box<MacResult+'cx>
     {
         (*self)(cx, sp, ident, token_tree)
@@ -607,7 +611,7 @@ impl<'a> ExtCtxt<'a> {
         expand::MacroExpander::new(self)
     }
 
-    pub fn new_parser_from_tts(&self, tts: &[ast::TokenTree])
+    pub fn new_parser_from_tts(&self, tts: &[tokenstream::TokenTree])
         -> parser::Parser<'a> {
         parse::tts_to_parser(self.parse_sess, tts.to_vec(), self.cfg())
     }
@@ -806,7 +810,7 @@ pub fn expr_to_string(cx: &mut ExtCtxt, expr: P<ast::Expr>, err_msg: &str)
 /// done as rarely as possible).
 pub fn check_zero_tts(cx: &ExtCtxt,
                       sp: Span,
-                      tts: &[ast::TokenTree],
+                      tts: &[tokenstream::TokenTree],
                       name: &str) {
     if !tts.is_empty() {
         cx.span_err(sp, &format!("{} takes no arguments", name));
@@ -817,7 +821,7 @@ pub fn check_zero_tts(cx: &ExtCtxt,
 /// is not a string literal, emit an error and return None.
 pub fn get_single_str_from_tts(cx: &mut ExtCtxt,
                                sp: Span,
-                               tts: &[ast::TokenTree],
+                               tts: &[tokenstream::TokenTree],
                                name: &str)
                                -> Option<String> {
     let mut p = cx.new_parser_from_tts(tts);
@@ -838,7 +842,7 @@ pub fn get_single_str_from_tts(cx: &mut ExtCtxt,
 /// parsing error, emit a non-fatal error and return None.
 pub fn get_exprs_from_tts(cx: &mut ExtCtxt,
                           sp: Span,
-                          tts: &[ast::TokenTree]) -> Option<Vec<P<ast::Expr>>> {
+                          tts: &[tokenstream::TokenTree]) -> Option<Vec<P<ast::Expr>>> {
     let mut p = cx.new_parser_from_tts(tts);
     let mut es = Vec::new();
     while p.token != token::Eof {
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index d63411568dc..0ac72b90c42 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -11,7 +11,6 @@
 use ast::{Block, Crate, DeclKind, PatKind};
 use ast::{Local, Ident, Mac_, Name, SpannedIdent};
 use ast::{MacStmtStyle, Mrk, Stmt, StmtKind, ItemKind};
-use ast::TokenTree;
 use ast;
 use ext::mtwt;
 use ext::build::AstBuilder;
@@ -27,6 +26,7 @@ use fold::*;
 use util::move_map::MoveMap;
 use parse::token::{fresh_mark, fresh_name, intern, keywords};
 use ptr::P;
+use tokenstream::TokenTree;
 use util::small_vector::SmallVector;
 use visit;
 use visit::Visitor;
diff --git a/src/libsyntax/ext/quote.rs b/src/libsyntax/ext/quote.rs
index 871b0d4b1c0..85527963b64 100644
--- a/src/libsyntax/ext/quote.rs
+++ b/src/libsyntax/ext/quote.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use ast::{self, Arg, Arm, Block, Expr, Item, Pat, Stmt, TokenTree, Ty};
+use ast::{self, Arg, Arm, Block, Expr, Item, Pat, Stmt, Ty};
 use codemap::Span;
 use ext::base::ExtCtxt;
 use ext::base;
@@ -17,6 +17,7 @@ use parse::parser::{Parser, PathStyle};
 use parse::token::*;
 use parse::token;
 use ptr::P;
+use tokenstream::{self, TokenTree};
 
 /// Quasiquoting works via token trees.
 ///
@@ -33,7 +34,7 @@ pub mod rt {
     use ptr::P;
     use std::rc::Rc;
 
-    use ast::TokenTree;
+    use tokenstream::{self, TokenTree};
 
     pub use parse::new_parser_from_tts;
     pub use codemap::{BytePos, Span, dummy_spanned, DUMMY_SP};
@@ -214,7 +215,7 @@ pub mod rt {
             if self.node.style == ast::AttrStyle::Inner {
                 r.push(TokenTree::Token(self.span, token::Not));
             }
-            r.push(TokenTree::Delimited(self.span, Rc::new(ast::Delimited {
+            r.push(TokenTree::Delimited(self.span, Rc::new(tokenstream::Delimited {
                 delim: token::Bracket,
                 open_span: self.span,
                 tts: self.node.value.to_tokens(cx),
@@ -234,7 +235,7 @@ pub mod rt {
 
     impl ToTokens for () {
         fn to_tokens(&self, _cx: &ExtCtxt) -> Vec<TokenTree> {
-            vec![TokenTree::Delimited(DUMMY_SP, Rc::new(ast::Delimited {
+            vec![TokenTree::Delimited(DUMMY_SP, Rc::new(tokenstream::Delimited {
                 delim: token::Paren,
                 open_span: DUMMY_SP,
                 tts: vec![],
@@ -548,7 +549,7 @@ fn mk_name(cx: &ExtCtxt, sp: Span, ident: ast::Ident) -> P<ast::Expr> {
 }
 
 fn mk_tt_path(cx: &ExtCtxt, sp: Span, name: &str) -> P<ast::Expr> {
-    let idents = vec!(id_ext("syntax"), id_ext("ast"), id_ext("TokenTree"), id_ext(name));
+    let idents = vec!(id_ext("syntax"), id_ext("tokenstream"), id_ext("TokenTree"), id_ext(name));
     cx.expr_path(cx.path_global(sp, idents))
 }
 
@@ -772,12 +773,12 @@ fn statements_mk_tt(cx: &ExtCtxt, tt: &TokenTree, matcher: bool) -> Vec<ast::Stm
                 None => cx.expr_none(sp),
             };
             let e_op = match seq.op {
-                ast::KleeneOp::ZeroOrMore => "ZeroOrMore",
-                ast::KleeneOp::OneOrMore => "OneOrMore",
+                tokenstream::KleeneOp::ZeroOrMore => "ZeroOrMore",
+                tokenstream::KleeneOp::OneOrMore => "OneOrMore",
             };
             let e_op_idents = vec![
                 id_ext("syntax"),
-                id_ext("ast"),
+                id_ext("tokenstream"),
                 id_ext("KleeneOp"),
                 id_ext(e_op),
             ];
@@ -787,7 +788,9 @@ fn statements_mk_tt(cx: &ExtCtxt, tt: &TokenTree, matcher: bool) -> Vec<ast::Stm
                               cx.field_imm(sp, id_ext("op"), e_op),
                               cx.field_imm(sp, id_ext("num_captures"),
                                                cx.expr_usize(sp, seq.num_captures))];
-            let seq_path = vec![id_ext("syntax"), id_ext("ast"), id_ext("SequenceRepetition")];
+            let seq_path = vec![id_ext("syntax"),
+                                id_ext("tokenstream"),
+                                id_ext("SequenceRepetition")];
             let e_seq_struct = cx.expr_struct(sp, cx.path_global(sp, seq_path), fields);
             let e_rc_new = cx.expr_call_global(sp, vec![id_ext("std"),
                                                         id_ext("rc"),
diff --git a/src/libsyntax/ext/source_util.rs b/src/libsyntax/ext/source_util.rs
index fd229d77966..b97e15e9260 100644
--- a/src/libsyntax/ext/source_util.rs
+++ b/src/libsyntax/ext/source_util.rs
@@ -18,6 +18,7 @@ use parse::token;
 use parse;
 use print::pprust;
 use ptr::P;
+use tokenstream;
 use util::small_vector::SmallVector;
 
 use std::fs::File;
@@ -30,7 +31,7 @@ use std::rc::Rc;
 // a given file into the current one.
 
 /// line!(): expands to the current line number
-pub fn expand_line(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_line(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                    -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "line!");
 
@@ -41,7 +42,7 @@ pub fn expand_line(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
 }
 
 /* column!(): expands to the current column number */
-pub fn expand_column(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_column(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                   -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "column!");
 
@@ -54,7 +55,7 @@ pub fn expand_column(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
 /// file!(): expands to the current filename */
 /// The filemap (`loc.file`) contains a bunch more information we could spit
 /// out if we wanted.
-pub fn expand_file(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_file(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                    -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "file!");
 
@@ -64,14 +65,14 @@ pub fn expand_file(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
     base::MacEager::expr(cx.expr_str(topmost, filename))
 }
 
-pub fn expand_stringify(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_stringify(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                         -> Box<base::MacResult+'static> {
     let s = pprust::tts_to_string(tts);
     base::MacEager::expr(cx.expr_str(sp,
                                    token::intern_and_get_ident(&s[..])))
 }
 
-pub fn expand_mod(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_mod(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                   -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "module_path!");
     let string = cx.mod_path()
@@ -87,7 +88,7 @@ pub fn expand_mod(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
 /// include! : parse the given file as an expr
 /// This is generally a bad idea because it's going to behave
 /// unhygienically.
-pub fn expand_include<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_include<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                            -> Box<base::MacResult+'cx> {
     let file = match get_single_str_from_tts(cx, sp, tts, "include!") {
         Some(f) => f,
@@ -130,7 +131,7 @@ pub fn expand_include<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[ast::TokenTree
 }
 
 // include_str! : read the given file, insert it as a literal string expr
-pub fn expand_include_str(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_include_str(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                           -> Box<base::MacResult+'static> {
     let file = match get_single_str_from_tts(cx, sp, tts, "include_str!") {
         Some(f) => f,
@@ -167,7 +168,7 @@ pub fn expand_include_str(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
     }
 }
 
-pub fn expand_include_bytes(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_include_bytes(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                             -> Box<base::MacResult+'static> {
     let file = match get_single_str_from_tts(cx, sp, tts, "include_bytes!") {
         Some(f) => f,
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index ca5eb8f8003..5f4bf8042f9 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -79,7 +79,7 @@ pub use self::ParseResult::*;
 use self::TokenTreeOrTokenTreeVec::*;
 
 use ast;
-use ast::{TokenTree, Name, Ident};
+use ast::{Name, Ident};
 use codemap::{BytePos, mk_sp, Span, Spanned};
 use codemap;
 use errors::FatalError;
@@ -91,6 +91,7 @@ use parse::token::{Token, Nonterminal};
 use parse::token;
 use print::pprust;
 use ptr::P;
+use tokenstream::{self, TokenTree};
 
 use std::mem;
 use std::rc::Rc;
@@ -102,8 +103,8 @@ use std::collections::hash_map::Entry::{Vacant, Occupied};
 
 #[derive(Clone)]
 enum TokenTreeOrTokenTreeVec {
-    Tt(ast::TokenTree),
-    TtSeq(Rc<Vec<ast::TokenTree>>),
+    Tt(tokenstream::TokenTree),
+    TtSeq(Rc<Vec<tokenstream::TokenTree>>),
 }
 
 impl TokenTreeOrTokenTreeVec {
@@ -374,7 +375,7 @@ pub fn parse(sess: &ParseSess,
                 match ei.top_elts.get_tt(idx) {
                     /* need to descend into sequence */
                     TokenTree::Sequence(sp, seq) => {
-                        if seq.op == ast::KleeneOp::ZeroOrMore {
+                        if seq.op == tokenstream::KleeneOp::ZeroOrMore {
                             let mut new_ei = ei.clone();
                             new_ei.match_cur += seq.num_captures;
                             new_ei.idx += 1;
diff --git a/src/libsyntax/ext/tt/macro_rules.rs b/src/libsyntax/ext/tt/macro_rules.rs
index bbe989b0f40..eb354392e7d 100644
--- a/src/libsyntax/ext/tt/macro_rules.rs
+++ b/src/libsyntax/ext/tt/macro_rules.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use ast::{self, TokenTree};
+use ast;
 use codemap::{Span, DUMMY_SP};
 use ext::base::{DummyResult, ExtCtxt, MacResult, SyntaxExtension};
 use ext::base::{NormalTT, TTMacroExpander};
@@ -21,6 +21,7 @@ use parse::token::{self, gensym_ident, NtTT, Token};
 use parse::token::Token::*;
 use print;
 use ptr::P;
+use tokenstream::{self, TokenTree};
 
 use util::small_vector::SmallVector;
 
@@ -248,22 +249,22 @@ pub fn compile<'cx>(cx: &'cx mut ExtCtxt,
     let match_rhs_tok = MatchNt(rhs_nm, token::str_to_ident("tt"));
     let argument_gram = vec!(
         TokenTree::Sequence(DUMMY_SP,
-                   Rc::new(ast::SequenceRepetition {
+                   Rc::new(tokenstream::SequenceRepetition {
                        tts: vec![
                            TokenTree::Token(DUMMY_SP, match_lhs_tok),
                            TokenTree::Token(DUMMY_SP, token::FatArrow),
                            TokenTree::Token(DUMMY_SP, match_rhs_tok)],
                        separator: Some(token::Semi),
-                       op: ast::KleeneOp::OneOrMore,
+                       op: tokenstream::KleeneOp::OneOrMore,
                        num_captures: 2
                    })),
         //to phase into semicolon-termination instead of
         //semicolon-separation
         TokenTree::Sequence(DUMMY_SP,
-                   Rc::new(ast::SequenceRepetition {
+                   Rc::new(tokenstream::SequenceRepetition {
                        tts: vec![TokenTree::Token(DUMMY_SP, token::Semi)],
                        separator: None,
-                       op: ast::KleeneOp::ZeroOrMore,
+                       op: tokenstream::KleeneOp::ZeroOrMore,
                        num_captures: 0
                    })));
 
@@ -427,7 +428,7 @@ impl FirstSets {
                         }
 
                         // Reverse scan: Sequence comes before `first`.
-                        if subfirst.maybe_empty || seq_rep.op == ast::KleeneOp::ZeroOrMore {
+                        if subfirst.maybe_empty || seq_rep.op == tokenstream::KleeneOp::ZeroOrMore {
                             // If sequence is potentially empty, then
                             // union them (preserving first emptiness).
                             first.add_all(&TokenSet { maybe_empty: true, ..subfirst });
@@ -474,7 +475,8 @@ impl FirstSets {
 
                             assert!(first.maybe_empty);
                             first.add_all(subfirst);
-                            if subfirst.maybe_empty || seq_rep.op == ast::KleeneOp::ZeroOrMore {
+                            if subfirst.maybe_empty ||
+                               seq_rep.op == tokenstream::KleeneOp::ZeroOrMore {
                                 // continue scanning for more first
                                 // tokens, but also make sure we
                                 // restore empty-tracking state
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index 6b3b5ce9de9..dbe6ca8c683 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -9,8 +9,7 @@
 // except according to those terms.
 use self::LockstepIterSize::*;
 
-use ast;
-use ast::{TokenTree, Ident, Name};
+use ast::{Ident, Name};
 use codemap::{Span, DUMMY_SP};
 use errors::{Handler, DiagnosticBuilder};
 use ext::tt::macro_parser::{NamedMatch, MatchedSeq, MatchedNonterminal};
@@ -18,6 +17,7 @@ use parse::token::{DocComment, MatchNt, SubstNt};
 use parse::token::{Token, NtIdent, SpecialMacroVar};
 use parse::token;
 use parse::lexer::TokenAndSpan;
+use tokenstream::{self, TokenTree};
 
 use std::rc::Rc;
 use std::ops::Add;
@@ -59,7 +59,7 @@ pub struct TtReader<'a> {
 pub fn new_tt_reader(sp_diag: &Handler,
                      interp: Option<HashMap<Name, Rc<NamedMatch>>>,
                      imported_from: Option<Ident>,
-                     src: Vec<ast::TokenTree>)
+                     src: Vec<tokenstream::TokenTree>)
                      -> TtReader {
     new_tt_reader_with_doc_flag(sp_diag, interp, imported_from, src, false)
 }
@@ -73,16 +73,16 @@ pub fn new_tt_reader(sp_diag: &Handler,
 pub fn new_tt_reader_with_doc_flag(sp_diag: &Handler,
                                    interp: Option<HashMap<Name, Rc<NamedMatch>>>,
                                    imported_from: Option<Ident>,
-                                   src: Vec<ast::TokenTree>,
+                                   src: Vec<tokenstream::TokenTree>,
                                    desugar_doc_comments: bool)
                                    -> TtReader {
     let mut r = TtReader {
         sp_diag: sp_diag,
         stack: vec!(TtFrame {
-            forest: TokenTree::Sequence(DUMMY_SP, Rc::new(ast::SequenceRepetition {
+            forest: TokenTree::Sequence(DUMMY_SP, Rc::new(tokenstream::SequenceRepetition {
                 tts: src,
                 // doesn't matter. This merely holds the root unzipping.
-                separator: None, op: ast::KleeneOp::ZeroOrMore, num_captures: 0
+                separator: None, op: tokenstream::KleeneOp::ZeroOrMore, num_captures: 0
             })),
             idx: 0,
             dotdotdoted: false,
@@ -259,7 +259,7 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
                     }
                     LisConstraint(len, _) => {
                         if len == 0 {
-                            if seq.op == ast::KleeneOp::OneOrMore {
+                            if seq.op == tokenstream::KleeneOp::OneOrMore {
                                 // FIXME #2887 blame invoker
                                 panic!(r.sp_diag.span_fatal(sp.clone(),
                                                      "this must repeat at least once"));
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index edf418e3332..0eb18287bea 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -24,6 +24,7 @@ use attr::{ThinAttributes, ThinAttributesExt};
 use codemap::{respan, Span, Spanned};
 use parse::token::{self, keywords};
 use ptr::P;
+use tokenstream::*;
 use util::small_vector::SmallVector;
 use util::move_map::MoveMap;
 
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index 420a41e03b9..999afdc1e01 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -104,6 +104,7 @@ pub mod show_span;
 pub mod std_inject;
 pub mod str;
 pub mod test;
+pub mod tokenstream;
 pub mod visit;
 
 pub mod print {
diff --git a/src/libsyntax/parse/mod.rs b/src/libsyntax/parse/mod.rs
index 2e4d46bc983..06ca135927e 100644
--- a/src/libsyntax/parse/mod.rs
+++ b/src/libsyntax/parse/mod.rs
@@ -17,6 +17,7 @@ use parse::parser::Parser;
 use parse::token::InternedString;
 use ptr::P;
 use str::char_at;
+use tokenstream;
 
 use std::cell::RefCell;
 use std::iter;
@@ -160,7 +161,7 @@ pub fn parse_tts_from_source_str<'a>(name: String,
                                      source: String,
                                      cfg: ast::CrateConfig,
                                      sess: &'a ParseSess)
-                                     -> PResult<'a, Vec<ast::TokenTree>> {
+                                     -> PResult<'a, Vec<tokenstream::TokenTree>> {
     let mut p = new_parser_from_source_str(
         sess,
         cfg,
@@ -222,7 +223,7 @@ pub fn filemap_to_parser<'a>(sess: &'a ParseSess,
 // compiler expands into it
 pub fn new_parser_from_tts<'a>(sess: &'a ParseSess,
                                cfg: ast::CrateConfig,
-                               tts: Vec<ast::TokenTree>) -> Parser<'a> {
+                               tts: Vec<tokenstream::TokenTree>) -> Parser<'a> {
     tts_to_parser(sess, tts, cfg)
 }
 
@@ -247,7 +248,7 @@ fn file_to_filemap(sess: &ParseSess, path: &Path, spanopt: Option<Span>)
 
 /// Given a filemap, produce a sequence of token-trees
 pub fn filemap_to_tts(sess: &ParseSess, filemap: Rc<FileMap>)
-    -> Vec<ast::TokenTree> {
+    -> Vec<tokenstream::TokenTree> {
     // it appears to me that the cfg doesn't matter here... indeed,
     // parsing tt's probably shouldn't require a parser at all.
     let cfg = Vec::new();
@@ -258,7 +259,7 @@ pub fn filemap_to_tts(sess: &ParseSess, filemap: Rc<FileMap>)
 
 /// Given tts and cfg, produce a parser
 pub fn tts_to_parser<'a>(sess: &'a ParseSess,
-                         tts: Vec<ast::TokenTree>,
+                         tts: Vec<tokenstream::TokenTree>,
                          cfg: ast::CrateConfig) -> Parser<'a> {
     let trdr = lexer::new_tt_reader(&sess.span_diagnostic, None, None, tts);
     let mut p = Parser::new(sess, cfg, Box::new(trdr));
@@ -662,7 +663,7 @@ mod tests {
     use super::*;
     use std::rc::Rc;
     use codemap::{Span, BytePos, Pos, Spanned, NO_EXPANSION};
-    use ast::{self, TokenTree, PatKind};
+    use ast::{self, PatKind};
     use abi::Abi;
     use attr::{first_attr_value_str_by_name, AttrMetaMethods};
     use parse;
@@ -670,6 +671,7 @@ mod tests {
     use parse::token::{str_to_ident};
     use print::pprust::item_to_string;
     use ptr::P;
+    use tokenstream::{self, TokenTree};
     use util::parser_testing::{string_to_tts, string_to_parser};
     use util::parser_testing::{string_to_expr, string_to_item, string_to_stmt};
 
@@ -729,7 +731,7 @@ mod tests {
     #[test]
     fn string_to_tts_macro () {
         let tts = string_to_tts("macro_rules! zip (($a)=>($a))".to_string());
-        let tts: &[ast::TokenTree] = &tts[..];
+        let tts: &[tokenstream::TokenTree] = &tts[..];
 
         match (tts.len(), tts.get(0), tts.get(1), tts.get(2), tts.get(3)) {
             (
@@ -789,7 +791,7 @@ mod tests {
             TokenTree::Token(sp(3, 4), token::Ident(str_to_ident("a"))),
             TokenTree::Delimited(
                 sp(5, 14),
-                Rc::new(ast::Delimited {
+                Rc::new(tokenstream::Delimited {
                     delim: token::DelimToken::Paren,
                     open_span: sp(5, 6),
                     tts: vec![
@@ -801,7 +803,7 @@ mod tests {
                 })),
             TokenTree::Delimited(
                 sp(15, 21),
-                Rc::new(ast::Delimited {
+                Rc::new(tokenstream::Delimited {
                     delim: token::DelimToken::Brace,
                     open_span: sp(15, 16),
                     tts: vec![
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 341b076e7cf..a597419d96d 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -33,7 +33,7 @@ use ast::{Stmt, StmtKind};
 use ast::{VariantData, StructField};
 use ast::StrStyle;
 use ast::SelfKind;
-use ast::{Delimited, SequenceRepetition, TokenTree, TraitItem, TraitRef};
+use ast::{TraitItem, TraitRef};
 use ast::{Ty, TyKind, TypeBinding, TyParam, TyParamBounds};
 use ast::{ViewPath, ViewPathGlob, ViewPathList, ViewPathSimple};
 use ast::{Visibility, WhereClause};
@@ -55,6 +55,7 @@ use util::parser::{AssocOp, Fixity};
 use print::pprust;
 use ptr::P;
 use parse::PResult;
+use tokenstream::{self, Delimited, SequenceRepetition, TokenTree};
 
 use std::collections::HashSet;
 use std::mem;
@@ -2720,16 +2721,17 @@ impl<'a> Parser<'a> {
     /// Parse an optional separator followed by a Kleene-style
     /// repetition token (+ or *).
     pub fn parse_sep_and_kleene_op(&mut self)
-                                   -> PResult<'a, (Option<token::Token>, ast::KleeneOp)> {
-        fn parse_kleene_op<'a>(parser: &mut Parser<'a>) -> PResult<'a,  Option<ast::KleeneOp>> {
+                                   -> PResult<'a, (Option<token::Token>, tokenstream::KleeneOp)> {
+        fn parse_kleene_op<'a>(parser: &mut Parser<'a>) ->
+          PResult<'a,  Option<tokenstream::KleeneOp>> {
             match parser.token {
                 token::BinOp(token::Star) => {
                     parser.bump();
-                    Ok(Some(ast::KleeneOp::ZeroOrMore))
+                    Ok(Some(tokenstream::KleeneOp::ZeroOrMore))
                 },
                 token::BinOp(token::Plus) => {
                     parser.bump();
-                    Ok(Some(ast::KleeneOp::OneOrMore))
+                    Ok(Some(tokenstream::KleeneOp::OneOrMore))
                 },
                 _ => Ok(None)
             }
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index 47de32ed7d0..8376d28164d 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -19,6 +19,7 @@ use ext::mtwt;
 use ptr::P;
 use util::interner::{RcStr, StrInterner};
 use util::interner;
+use tokenstream;
 
 use serialize::{Decodable, Decoder, Encodable, Encoder};
 use std::fmt;
@@ -338,7 +339,7 @@ pub enum Nonterminal {
     /// Stuff inside brackets for attributes
     NtMeta(P<ast::MetaItem>),
     NtPath(Box<ast::Path>),
-    NtTT(P<ast::TokenTree>), // needs P'ed to break a circularity
+    NtTT(P<tokenstream::TokenTree>), // needs P'ed to break a circularity
     // These are not exposed to macros, but are used by quasiquote.
     NtArm(ast::Arm),
     NtImplItem(P<ast::ImplItem>),
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index a2ee5bf6090..0b5ced0757a 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -11,7 +11,7 @@
 pub use self::AnnNode::*;
 
 use abi::{self, Abi};
-use ast::{self, TokenTree, BlockCheckMode, PatKind};
+use ast::{self, BlockCheckMode, PatKind};
 use ast::{SelfKind, RegionTyParamBound, TraitTyParamBound, TraitBoundModifier};
 use ast::Attribute;
 use attr::ThinAttributesExt;
@@ -28,6 +28,7 @@ use print::pp::{Breaks, eof};
 use print::pp::Breaks::{Consistent, Inconsistent};
 use ptr::P;
 use std_inject;
+use tokenstream::{self, TokenTree};
 
 use std::ascii;
 use std::io::{self, Write, Read};
@@ -330,11 +331,11 @@ pub fn lifetime_to_string(e: &ast::Lifetime) -> String {
     to_string(|s| s.print_lifetime(e))
 }
 
-pub fn tt_to_string(tt: &ast::TokenTree) -> String {
+pub fn tt_to_string(tt: &tokenstream::TokenTree) -> String {
     to_string(|s| s.print_tt(tt))
 }
 
-pub fn tts_to_string(tts: &[ast::TokenTree]) -> String {
+pub fn tts_to_string(tts: &[tokenstream::TokenTree]) -> String {
     to_string(|s| s.print_tts(tts))
 }
 
@@ -1445,7 +1446,7 @@ impl<'a> State<'a> {
     /// appropriate macro, transcribe back into the grammar we just parsed from,
     /// and then pretty-print the resulting AST nodes (so, e.g., we print
     /// expression arguments as expressions). It can be done! I think.
-    pub fn print_tt(&mut self, tt: &ast::TokenTree) -> io::Result<()> {
+    pub fn print_tt(&mut self, tt: &tokenstream::TokenTree) -> io::Result<()> {
         match *tt {
             TokenTree::Token(_, ref tk) => {
                 try!(word(&mut self.s, &token_to_string(tk)));
@@ -1476,14 +1477,14 @@ impl<'a> State<'a> {
                     None => {},
                 }
                 match seq.op {
-                    ast::KleeneOp::ZeroOrMore => word(&mut self.s, "*"),
-                    ast::KleeneOp::OneOrMore => word(&mut self.s, "+"),
+                    tokenstream::KleeneOp::ZeroOrMore => word(&mut self.s, "*"),
+                    tokenstream::KleeneOp::OneOrMore => word(&mut self.s, "+"),
                 }
             }
         }
     }
 
-    pub fn print_tts(&mut self, tts: &[ast::TokenTree]) -> io::Result<()> {
+    pub fn print_tts(&mut self, tts: &[tokenstream::TokenTree]) -> io::Result<()> {
         try!(self.ibox(0));
         for (i, tt) in tts.iter().enumerate() {
             if i != 0 {
diff --git a/src/libsyntax/tokenstream.rs b/src/libsyntax/tokenstream.rs
new file mode 100644
index 00000000000..b903537a7b7
--- /dev/null
+++ b/src/libsyntax/tokenstream.rs
@@ -0,0 +1,211 @@
+// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! # Token Trees
+//! TokenTrees are syntactic forms for dealing with tokens. The description below is
+//! more complete; in short a TokenTree is a single token, a delimited sequence of token
+//! trees, or a sequence with repetition for list splicing as part of macro expansion.
+
+use ast::{AttrStyle};
+use codemap::{Span};
+use ext::base;
+use ext::tt::macro_parser;
+use parse::lexer::comments::{doc_comment_style, strip_doc_comment_decoration};
+use parse::lexer;
+use parse::token;
+use std::rc::Rc;
+
+/// A delimited sequence of token trees
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
+pub struct Delimited {
+    /// The type of delimiter
+    pub delim: token::DelimToken,
+    /// The span covering the opening delimiter
+    pub open_span: Span,
+    /// The delimited sequence of token trees
+    pub tts: Vec<TokenTree>,
+    /// The span covering the closing delimiter
+    pub close_span: Span,
+}
+
+impl Delimited {
+    /// Returns the opening delimiter as a token.
+    pub fn open_token(&self) -> token::Token {
+        token::OpenDelim(self.delim)
+    }
+
+    /// Returns the closing delimiter as a token.
+    pub fn close_token(&self) -> token::Token {
+        token::CloseDelim(self.delim)
+    }
+
+    /// Returns the opening delimiter as a token tree.
+    pub fn open_tt(&self) -> TokenTree {
+        TokenTree::Token(self.open_span, self.open_token())
+    }
+
+    /// Returns the closing delimiter as a token tree.
+    pub fn close_tt(&self) -> TokenTree {
+        TokenTree::Token(self.close_span, self.close_token())
+    }
+}
+
+/// A sequence of token trees
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
+pub struct SequenceRepetition {
+    /// The sequence of token trees
+    pub tts: Vec<TokenTree>,
+    /// The optional separator
+    pub separator: Option<token::Token>,
+    /// Whether the sequence can be repeated zero (*), or one or more times (+)
+    pub op: KleeneOp,
+    /// The number of `MatchNt`s that appear in the sequence (and subsequences)
+    pub num_captures: usize,
+}
+
+/// A Kleene-style [repetition operator](http://en.wikipedia.org/wiki/Kleene_star)
+/// for token sequences.
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
+pub enum KleeneOp {
+    ZeroOrMore,
+    OneOrMore,
+}
+
+/// When the main rust parser encounters a syntax-extension invocation, it
+/// parses the arguments to the invocation as a token-tree. This is a very
+/// loose structure, such that all sorts of different AST-fragments can
+/// be passed to syntax extensions using a uniform type.
+///
+/// If the syntax extension is an MBE macro, it will attempt to match its
+/// LHS token tree against the provided token tree, and if it finds a
+/// match, will transcribe the RHS token tree, splicing in any captured
+/// macro_parser::matched_nonterminals into the `SubstNt`s it finds.
+///
+/// The RHS of an MBE macro is the only place `SubstNt`s are substituted.
+/// Nothing special happens to misnamed or misplaced `SubstNt`s.
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
+pub enum TokenTree {
+    /// A single token
+    Token(Span, token::Token),
+    /// A delimited sequence of token trees
+    Delimited(Span, Rc<Delimited>),
+
+    // This only makes sense in MBE macros.
+
+    /// A kleene-style repetition sequence with a span
+    // FIXME(eddyb) #12938 Use DST.
+    Sequence(Span, Rc<SequenceRepetition>),
+}
+
+impl TokenTree {
+    pub fn len(&self) -> usize {
+        match *self {
+            TokenTree::Token(_, token::DocComment(name)) => {
+                match doc_comment_style(&name.as_str()) {
+                    AttrStyle::Outer => 2,
+                    AttrStyle::Inner => 3
+                }
+            }
+            TokenTree::Token(_, token::SpecialVarNt(..)) => 2,
+            TokenTree::Token(_, token::MatchNt(..)) => 3,
+            TokenTree::Delimited(_, ref delimed) => {
+                delimed.tts.len() + 2
+            }
+            TokenTree::Sequence(_, ref seq) => {
+                seq.tts.len()
+            }
+            TokenTree::Token(..) => 0
+        }
+    }
+
+    pub fn get_tt(&self, index: usize) -> TokenTree {
+        match (self, index) {
+            (&TokenTree::Token(sp, token::DocComment(_)), 0) => {
+                TokenTree::Token(sp, token::Pound)
+            }
+            (&TokenTree::Token(sp, token::DocComment(name)), 1)
+            if doc_comment_style(&name.as_str()) == AttrStyle::Inner => {
+                TokenTree::Token(sp, token::Not)
+            }
+            (&TokenTree::Token(sp, token::DocComment(name)), _) => {
+                let stripped = strip_doc_comment_decoration(&name.as_str());
+
+                // Searches for the occurrences of `"#*` and returns the minimum number of `#`s
+                // required to wrap the text.
+                let num_of_hashes = stripped.chars().scan(0, |cnt, x| {
+                    *cnt = if x == '"' {
+                        1
+                    } else if *cnt != 0 && x == '#' {
+                        *cnt + 1
+                    } else {
+                        0
+                    };
+                    Some(*cnt)
+                }).max().unwrap_or(0);
+
+                TokenTree::Delimited(sp, Rc::new(Delimited {
+                    delim: token::Bracket,
+                    open_span: sp,
+                    tts: vec![TokenTree::Token(sp, token::Ident(token::str_to_ident("doc"))),
+                              TokenTree::Token(sp, token::Eq),
+                              TokenTree::Token(sp, token::Literal(
+                                  token::StrRaw(token::intern(&stripped), num_of_hashes), None))],
+                    close_span: sp,
+                }))
+            }
+            (&TokenTree::Delimited(_, ref delimed), _) => {
+                if index == 0 {
+                    return delimed.open_tt();
+                }
+                if index == delimed.tts.len() + 1 {
+                    return delimed.close_tt();
+                }
+                delimed.tts[index - 1].clone()
+            }
+            (&TokenTree::Token(sp, token::SpecialVarNt(var)), _) => {
+                let v = [TokenTree::Token(sp, token::Dollar),
+                         TokenTree::Token(sp, token::Ident(token::str_to_ident(var.as_str())))];
+                v[index].clone()
+            }
+            (&TokenTree::Token(sp, token::MatchNt(name, kind)), _) => {
+                let v = [TokenTree::Token(sp, token::SubstNt(name)),
+                         TokenTree::Token(sp, token::Colon),
+                         TokenTree::Token(sp, token::Ident(kind))];
+                v[index].clone()
+            }
+            (&TokenTree::Sequence(_, ref seq), _) => {
+                seq.tts[index].clone()
+            }
+            _ => panic!("Cannot expand a token tree")
+        }
+    }
+
+    /// Returns the `Span` corresponding to this token tree.
+    pub fn get_span(&self) -> Span {
+        match *self {
+            TokenTree::Token(span, _)     => span,
+            TokenTree::Delimited(span, _) => span,
+            TokenTree::Sequence(span, _)  => span,
+        }
+    }
+
+    /// Use this token tree as a matcher to parse given tts.
+    pub fn parse(cx: &base::ExtCtxt, mtch: &[TokenTree], tts: &[TokenTree])
+                 -> macro_parser::NamedParseResult {
+        // `None` is because we're not interpolating
+        let arg_rdr = lexer::new_tt_reader_with_doc_flag(&cx.parse_sess().span_diagnostic,
+                                                         None,
+                                                         None,
+                                                         tts.iter().cloned().collect(),
+                                                         true);
+        macro_parser::parse(cx.parse_sess(), cx.cfg(), arg_rdr, mtch)
+    }
+}
+
diff --git a/src/libsyntax/util/parser_testing.rs b/src/libsyntax/util/parser_testing.rs
index 06264196d9e..f59428bf536 100644
--- a/src/libsyntax/util/parser_testing.rs
+++ b/src/libsyntax/util/parser_testing.rs
@@ -14,10 +14,11 @@ use parse::{lexer, new_parser_from_source_str};
 use parse::parser::Parser;
 use parse::token;
 use ptr::P;
+use tokenstream;
 use std::iter::Peekable;
 
 /// Map a string to tts, using a made-up filename:
-pub fn string_to_tts(source_str: String) -> Vec<ast::TokenTree> {
+pub fn string_to_tts(source_str: String) -> Vec<tokenstream::TokenTree> {
     let ps = ParseSess::new();
     filemap_to_tts(&ps, ps.codemap().new_filemap("bogofile".to_string(), None, source_str))
 }
diff --git a/src/libsyntax_ext/asm.rs b/src/libsyntax_ext/asm.rs
index 50d2b9d31fe..b8a46fddf3a 100644
--- a/src/libsyntax_ext/asm.rs
+++ b/src/libsyntax_ext/asm.rs
@@ -23,6 +23,7 @@ use syntax::parse::token::intern;
 use syntax::parse::{self, token};
 use syntax::ptr::P;
 use syntax::ast::AsmDialect;
+use syntax::tokenstream;
 
 enum State {
     Asm,
@@ -48,7 +49,7 @@ impl State {
 
 const OPTIONS: &'static [&'static str] = &["volatile", "alignstack", "intel"];
 
-pub fn expand_asm<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_asm<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                        -> Box<base::MacResult+'cx> {
     if !cx.ecfg.enable_asm() {
         feature_gate::emit_feature_err(
@@ -62,8 +63,8 @@ pub fn expand_asm<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
     // parsed as `asm!(z)` with `z = "x": y` which is type ascription.
     let first_colon = tts.iter().position(|tt| {
         match *tt {
-            ast::TokenTree::Token(_, token::Colon) |
-            ast::TokenTree::Token(_, token::ModSep) => true,
+            tokenstream::TokenTree::Token(_, token::Colon) |
+            tokenstream::TokenTree::Token(_, token::ModSep) => true,
             _ => false
         }
     }).unwrap_or(tts.len());
diff --git a/src/libsyntax_ext/cfg.rs b/src/libsyntax_ext/cfg.rs
index 593bf14a018..5af1ae877ed 100644
--- a/src/libsyntax_ext/cfg.rs
+++ b/src/libsyntax_ext/cfg.rs
@@ -12,17 +12,17 @@
 /// a literal `true` or `false` based on whether the given cfg matches the
 /// current compilation environment.
 
-use syntax::ast;
 use syntax::codemap::Span;
 use syntax::ext::base::*;
 use syntax::ext::base;
 use syntax::ext::build::AstBuilder;
 use syntax::attr;
+use syntax::tokenstream;
 use syntax::parse::token;
 
 pub fn expand_cfg<'cx>(cx: &mut ExtCtxt,
                        sp: Span,
-                       tts: &[ast::TokenTree])
+                       tts: &[tokenstream::TokenTree])
                        -> Box<base::MacResult+'static> {
     let mut p = cx.new_parser_from_tts(tts);
     let cfg = panictry!(p.parse_meta_item());
diff --git a/src/libsyntax_ext/concat.rs b/src/libsyntax_ext/concat.rs
index db731adf794..f2ea27f6ebe 100644
--- a/src/libsyntax_ext/concat.rs
+++ b/src/libsyntax_ext/concat.rs
@@ -13,12 +13,13 @@ use syntax::codemap;
 use syntax::ext::base;
 use syntax::ext::build::AstBuilder;
 use syntax::parse::token;
+use syntax::tokenstream;
 
 use std::string::String;
 
 pub fn expand_syntax_ext(cx: &mut base::ExtCtxt,
                          sp: codemap::Span,
-                         tts: &[ast::TokenTree])
+                         tts: &[tokenstream::TokenTree])
                          -> Box<base::MacResult+'static> {
     let es = match base::get_exprs_from_tts(cx, sp, tts) {
         Some(e) => e,
diff --git a/src/libsyntax_ext/concat_idents.rs b/src/libsyntax_ext/concat_idents.rs
index 09c23682cd7..fe820983257 100644
--- a/src/libsyntax_ext/concat_idents.rs
+++ b/src/libsyntax_ext/concat_idents.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use syntax::ast::{self, TokenTree};
+use syntax::ast::{self};
 use syntax::codemap::Span;
 use syntax::ext::base::*;
 use syntax::ext::base;
@@ -16,6 +16,7 @@ use syntax::feature_gate;
 use syntax::parse::token;
 use syntax::parse::token::str_to_ident;
 use syntax::ptr::P;
+use syntax::tokenstream::TokenTree;
 
 pub fn expand_syntax_ext<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[TokenTree])
                               -> Box<base::MacResult+'cx> {
diff --git a/src/libsyntax_ext/env.rs b/src/libsyntax_ext/env.rs
index 63ec9cac073..1d7b8406fa2 100644
--- a/src/libsyntax_ext/env.rs
+++ b/src/libsyntax_ext/env.rs
@@ -20,10 +20,11 @@ use syntax::ext::base::*;
 use syntax::ext::base;
 use syntax::ext::build::AstBuilder;
 use syntax::parse::token;
+use syntax::tokenstream;
 
 use std::env;
 
-pub fn expand_option_env<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_option_env<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                               -> Box<base::MacResult+'cx> {
     let var = match get_single_str_from_tts(cx, sp, tts, "option_env!") {
         None => return DummyResult::expr(sp),
@@ -56,7 +57,7 @@ pub fn expand_option_env<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[ast::TokenT
     MacEager::expr(e)
 }
 
-pub fn expand_env<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+pub fn expand_env<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                        -> Box<base::MacResult+'cx> {
     let mut exprs = match get_exprs_from_tts(cx, sp, tts) {
         Some(ref exprs) if exprs.is_empty() => {
diff --git a/src/libsyntax_ext/format.rs b/src/libsyntax_ext/format.rs
index abfa6558064..276e2c68191 100644
--- a/src/libsyntax_ext/format.rs
+++ b/src/libsyntax_ext/format.rs
@@ -21,6 +21,7 @@ use syntax::ext::build::AstBuilder;
 use syntax::fold::Folder;
 use syntax::parse::token::{self, keywords};
 use syntax::ptr::P;
+use syntax::tokenstream;
 
 use std::collections::HashMap;
 
@@ -80,7 +81,7 @@ struct Context<'a, 'b:'a> {
 /// Some((fmtstr, unnamed arguments, ordering of named arguments,
 ///       named arguments))
 /// ```
-fn parse_args(ecx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
+fn parse_args(ecx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
               -> Option<(P<ast::Expr>, Vec<P<ast::Expr>>, Vec<String>,
                          HashMap<String, P<ast::Expr>>)> {
     let mut args = Vec::new();
@@ -606,7 +607,7 @@ impl<'a, 'b> Context<'a, 'b> {
 }
 
 pub fn expand_format_args<'cx>(ecx: &'cx mut ExtCtxt, sp: Span,
-                               tts: &[ast::TokenTree])
+                               tts: &[tokenstream::TokenTree])
                                -> Box<base::MacResult+'cx> {
 
     match parse_args(ecx, sp, tts) {
diff --git a/src/libsyntax_ext/log_syntax.rs b/src/libsyntax_ext/log_syntax.rs
index ee944abb645..73dcb3e933e 100644
--- a/src/libsyntax_ext/log_syntax.rs
+++ b/src/libsyntax_ext/log_syntax.rs
@@ -8,15 +8,15 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use syntax::ast;
 use syntax::codemap;
 use syntax::ext::base;
 use syntax::feature_gate;
 use syntax::print;
+use syntax::tokenstream;
 
 pub fn expand_syntax_ext<'cx>(cx: &'cx mut base::ExtCtxt,
                               sp: codemap::Span,
-                              tts: &[ast::TokenTree])
+                              tts: &[tokenstream::TokenTree])
                               -> Box<base::MacResult+'cx> {
     if !cx.ecfg.enable_log_syntax() {
         feature_gate::emit_feature_err(&cx.parse_sess.span_diagnostic,
diff --git a/src/libsyntax_ext/trace_macros.rs b/src/libsyntax_ext/trace_macros.rs
index 7b1e985442a..8a9207acd47 100644
--- a/src/libsyntax_ext/trace_macros.rs
+++ b/src/libsyntax_ext/trace_macros.rs
@@ -8,12 +8,12 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use syntax::ast::TokenTree;
 use syntax::codemap::Span;
 use syntax::ext::base::ExtCtxt;
 use syntax::ext::base;
 use syntax::feature_gate;
 use syntax::parse::token::keywords;
+use syntax::tokenstream::TokenTree;
 
 
 pub fn expand_trace_macros(cx: &mut ExtCtxt,
diff --git a/src/test/compile-fail-fulldeps/auxiliary/macro_crate_test.rs b/src/test/compile-fail-fulldeps/auxiliary/macro_crate_test.rs
index 3516f566e8a..460cad69e81 100644
--- a/src/test/compile-fail-fulldeps/auxiliary/macro_crate_test.rs
+++ b/src/test/compile-fail-fulldeps/auxiliary/macro_crate_test.rs
@@ -16,11 +16,12 @@ extern crate syntax;
 extern crate rustc;
 extern crate rustc_plugin;
 
-use syntax::ast::{self, TokenTree, Item, MetaItem, ImplItem, TraitItem, ItemKind};
+use syntax::ast::{self, Item, MetaItem, ImplItem, TraitItem, ItemKind};
 use syntax::codemap::Span;
 use syntax::ext::base::*;
 use syntax::parse::{self, token};
 use syntax::ptr::P;
+use syntax::tokenstream::{TokenTree};
 use rustc_plugin::Registry;
 
 #[macro_export]
diff --git a/src/test/run-pass-fulldeps/auxiliary/issue_16723_multiple_items_syntax_ext.rs b/src/test/run-pass-fulldeps/auxiliary/issue_16723_multiple_items_syntax_ext.rs
index 25a75c2d295..6c861883b4c 100644
--- a/src/test/run-pass-fulldeps/auxiliary/issue_16723_multiple_items_syntax_ext.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/issue_16723_multiple_items_syntax_ext.rs
@@ -21,6 +21,7 @@ use syntax::ast;
 use syntax::codemap;
 use syntax::ext::base::{ExtCtxt, MacResult, MacEager};
 use syntax::util::small_vector::SmallVector;
+use syntax::tokenstream;
 use rustc_plugin::Registry;
 
 #[plugin_registrar]
@@ -28,7 +29,8 @@ pub fn plugin_registrar(reg: &mut Registry) {
     reg.register_macro("multiple_items", expand)
 }
 
-fn expand(cx: &mut ExtCtxt, _: codemap::Span, _: &[ast::TokenTree]) -> Box<MacResult+'static> {
+fn expand(cx: &mut ExtCtxt, _: codemap::Span, _: &[tokenstream::TokenTree])
+          -> Box<MacResult+'static> {
     MacEager::items(SmallVector::many(vec![
         quote_item!(cx, struct Struct1;).unwrap(),
         quote_item!(cx, struct Struct2;).unwrap()
diff --git a/src/test/run-pass-fulldeps/auxiliary/macro_crate_test.rs b/src/test/run-pass-fulldeps/auxiliary/macro_crate_test.rs
index 3516f566e8a..460cad69e81 100644
--- a/src/test/run-pass-fulldeps/auxiliary/macro_crate_test.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/macro_crate_test.rs
@@ -16,11 +16,12 @@ extern crate syntax;
 extern crate rustc;
 extern crate rustc_plugin;
 
-use syntax::ast::{self, TokenTree, Item, MetaItem, ImplItem, TraitItem, ItemKind};
+use syntax::ast::{self, Item, MetaItem, ImplItem, TraitItem, ItemKind};
 use syntax::codemap::Span;
 use syntax::ext::base::*;
 use syntax::parse::{self, token};
 use syntax::ptr::P;
+use syntax::tokenstream::{TokenTree};
 use rustc_plugin::Registry;
 
 #[macro_export]
diff --git a/src/test/run-pass-fulldeps/auxiliary/plugin_args.rs b/src/test/run-pass-fulldeps/auxiliary/plugin_args.rs
index 99321ad4241..0abe041149c 100644
--- a/src/test/run-pass-fulldeps/auxiliary/plugin_args.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/plugin_args.rs
@@ -25,6 +25,7 @@ use syntax::ext::base::{TTMacroExpander, ExtCtxt, MacResult, MacEager, NormalTT}
 use syntax::parse::token;
 use syntax::print::pprust;
 use syntax::ptr::P;
+use syntax::tokenstream;
 use rustc_plugin::Registry;
 
 struct Expander {
@@ -35,7 +36,7 @@ impl TTMacroExpander for Expander {
     fn expand<'cx>(&self,
                    ecx: &'cx mut ExtCtxt,
                    sp: Span,
-                   _: &[ast::TokenTree]) -> Box<MacResult+'cx> {
+                   _: &[tokenstream::TokenTree]) -> Box<MacResult+'cx> {
         let args = self.args.iter().map(|i| pprust::meta_item_to_string(&*i))
             .collect::<Vec<_>>().join(", ");
         let interned = token::intern_and_get_ident(&args[..]);
diff --git a/src/test/run-pass-fulldeps/auxiliary/procedural_mbe_matching.rs b/src/test/run-pass-fulldeps/auxiliary/procedural_mbe_matching.rs
index 713a7d1e811..4a4c873564e 100644
--- a/src/test/run-pass-fulldeps/auxiliary/procedural_mbe_matching.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/procedural_mbe_matching.rs
@@ -19,7 +19,8 @@ extern crate rustc_plugin;
 
 use syntax::codemap::Span;
 use syntax::parse::token::{self, str_to_ident, NtExpr, NtPat};
-use syntax::ast::{TokenTree, Pat};
+use syntax::ast::{Pat};
+use syntax::tokenstream::{TokenTree};
 use syntax::ext::base::{ExtCtxt, MacResult, DummyResult, MacEager};
 use syntax::ext::build::AstBuilder;
 use syntax::ext::tt::macro_parser::{MatchedSeq, MatchedNonterminal};
diff --git a/src/test/run-pass-fulldeps/auxiliary/roman_numerals.rs b/src/test/run-pass-fulldeps/auxiliary/roman_numerals.rs
index 839ece49c3e..4414cc4ca30 100644
--- a/src/test/run-pass-fulldeps/auxiliary/roman_numerals.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/roman_numerals.rs
@@ -19,8 +19,8 @@ extern crate rustc;
 extern crate rustc_plugin;
 
 use syntax::codemap::Span;
-use syntax::ast::TokenTree;
 use syntax::parse::token;
+use syntax::tokenstream::TokenTree;
 use syntax::ext::base::{ExtCtxt, MacResult, DummyResult, MacEager};
 use syntax::ext::build::AstBuilder;  // trait for expr_usize
 use rustc_plugin::Registry;
diff --git a/src/test/run-pass-fulldeps/auxiliary/syntax_extension_with_dll_deps_2.rs b/src/test/run-pass-fulldeps/auxiliary/syntax_extension_with_dll_deps_2.rs
index 7281698a7fb..0812fcfc642 100644
--- a/src/test/run-pass-fulldeps/auxiliary/syntax_extension_with_dll_deps_2.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/syntax_extension_with_dll_deps_2.rs
@@ -18,8 +18,9 @@ extern crate syntax;
 extern crate rustc;
 extern crate rustc_plugin;
 
-use syntax::ast::{TokenTree, Item, MetaItem};
+use syntax::ast::{Item, MetaItem};
 use syntax::codemap::Span;
+use syntax::tokenstream::{TokenTree};
 use syntax::ext::base::*;
 use rustc_plugin::Registry;
 
diff --git a/src/test/run-pass-fulldeps/quote-tokens.rs b/src/test/run-pass-fulldeps/quote-tokens.rs
index 4397da35d7a..710e2fd1d07 100644
--- a/src/test/run-pass-fulldeps/quote-tokens.rs
+++ b/src/test/run-pass-fulldeps/quote-tokens.rs
@@ -20,8 +20,8 @@ use syntax::ptr::P;
 use syntax::parse::PResult;
 
 fn syntax_extension(cx: &ExtCtxt) {
-    let e_toks : Vec<syntax::ast::TokenTree> = quote_tokens!(cx, 1 + 2);
-    let p_toks : Vec<syntax::ast::TokenTree> = quote_tokens!(cx, (x, 1 .. 4, *));
+    let e_toks : Vec<syntax::tokenstream::TokenTree> = quote_tokens!(cx, 1 + 2);
+    let p_toks : Vec<syntax::tokenstream::TokenTree> = quote_tokens!(cx, (x, 1 .. 4, *));
 
     let a: P<syntax::ast::Expr> = quote_expr!(cx, 1 + 2);
     let _b: Option<P<syntax::ast::Item>> = quote_item!(cx, static foo : isize = $e_toks; );
@@ -39,7 +39,7 @@ fn syntax_extension(cx: &ExtCtxt) {
 
     let _l: P<syntax::ast::Ty> = quote_ty!(cx, &isize);
 
-    let _m: Vec<syntax::ast::TokenTree> = quote_matcher!(cx, $($foo:tt,)* bar);
+    let _m: Vec<syntax::tokenstream::TokenTree> = quote_matcher!(cx, $($foo:tt,)* bar);
     let _n: syntax::ast::Attribute = quote_attr!(cx, #![cfg(foo, bar = "baz")]);
 
     let _o: Option<P<syntax::ast::Item>> = quote_item!(cx, fn foo<T: ?Sized>() {});