Merge branch 'master' into issue-30961

13 files changed, 552 insertions, 692 deletions

diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index 67f73d4dd4f..b622f6861b3 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -17,8 +17,8 @@ pub use self::IntType::*;
 use ast;
 use ast::{AttrId, Attribute, Attribute_, MetaItem, MetaItemKind};
 use ast::{Expr, Item, Local, Stmt, StmtKind};
-use codemap::{spanned, dummy_spanned, Spanned};
-use syntax_pos::{Span, BytePos};
+use codemap::{respan, spanned, dummy_spanned, Spanned};
+use syntax_pos::{Span, BytePos, DUMMY_SP};
 use errors::Handler;
 use feature_gate::{Features, GatedCfg};
 use parse::lexer::comments::{doc_comment_style, strip_doc_comment_decoration};
@@ -92,6 +92,19 @@ pub trait AttrMetaMethods {
     /// Gets a list of inner meta items from a list MetaItem type.
     fn meta_item_list(&self) -> Option<&[P<MetaItem>]>;
 
+    /// Indicates if the attribute is a Word.
+    fn is_word(&self) -> bool;
+
+    /// Indicates if the attribute is a Value String.
+    fn is_value_str(&self) -> bool {
+        self.value_str().is_some()
+    }
+
+    /// Indicates if the attribute is a Meta-Item List.
+    fn is_meta_item_list(&self) -> bool {
+        self.meta_item_list().is_some()
+    }
+
     fn span(&self) -> Span;
 }
 
@@ -108,8 +121,11 @@ impl AttrMetaMethods for Attribute {
         self.meta().value_str()
     }
     fn meta_item_list(&self) -> Option<&[P<MetaItem>]> {
-        self.node.value.meta_item_list()
+        self.meta().meta_item_list()
     }
+
+    fn is_word(&self) -> bool { self.meta().is_word() }
+
     fn span(&self) -> Span { self.meta().span }
 }
 
@@ -140,6 +156,14 @@ impl AttrMetaMethods for MetaItem {
             _ => None
         }
     }
+
+    fn is_word(&self) -> bool {
+        match self.node {
+            MetaItemKind::Word(_) => true,
+            _ => false,
+        }
+    }
+
     fn span(&self) -> Span { self.span }
 }
 
@@ -150,6 +174,9 @@ impl AttrMetaMethods for P<MetaItem> {
     fn meta_item_list(&self) -> Option<&[P<MetaItem>]> {
         (**self).meta_item_list()
     }
+    fn is_word(&self) -> bool { (**self).is_word() }
+    fn is_value_str(&self) -> bool { (**self).is_value_str() }
+    fn is_meta_item_list(&self) -> bool { (**self).is_meta_item_list() }
     fn span(&self) -> Span { (**self).span() }
 }
 
@@ -194,22 +221,38 @@ impl AttributeMethods for Attribute {
 pub fn mk_name_value_item_str(name: InternedString, value: InternedString)
                               -> P<MetaItem> {
     let value_lit = dummy_spanned(ast::LitKind::Str(value, ast::StrStyle::Cooked));
-    mk_name_value_item(name, value_lit)
+    mk_spanned_name_value_item(DUMMY_SP, name, value_lit)
 }
 
 pub fn mk_name_value_item(name: InternedString, value: ast::Lit)
                           -> P<MetaItem> {
-    P(dummy_spanned(MetaItemKind::NameValue(name, value)))
+    mk_spanned_name_value_item(DUMMY_SP, name, value)
 }
 
 pub fn mk_list_item(name: InternedString, items: Vec<P<MetaItem>>) -> P<MetaItem> {
-    P(dummy_spanned(MetaItemKind::List(name, items)))
+    mk_spanned_list_item(DUMMY_SP, name, items)
 }
 
 pub fn mk_word_item(name: InternedString) -> P<MetaItem> {
-    P(dummy_spanned(MetaItemKind::Word(name)))
+    mk_spanned_word_item(DUMMY_SP, name)
+}
+
+pub fn mk_spanned_name_value_item(sp: Span, name: InternedString, value: ast::Lit)
+                          -> P<MetaItem> {
+    P(respan(sp, MetaItemKind::NameValue(name, value)))
+}
+
+pub fn mk_spanned_list_item(sp: Span, name: InternedString, items: Vec<P<MetaItem>>)
+                            -> P<MetaItem> {
+    P(respan(sp, MetaItemKind::List(name, items)))
+}
+
+pub fn mk_spanned_word_item(sp: Span, name: InternedString) -> P<MetaItem> {
+    P(respan(sp, MetaItemKind::Word(name)))
 }
 
+
+
 thread_local! { static NEXT_ATTR_ID: Cell<usize> = Cell::new(0) }
 
 pub fn mk_attr_id() -> AttrId {
@@ -223,21 +266,43 @@ pub fn mk_attr_id() -> AttrId {
 
 /// Returns an inner attribute with the given value.
 pub fn mk_attr_inner(id: AttrId, item: P<MetaItem>) -> Attribute {
-    dummy_spanned(Attribute_ {
-        id: id,
-        style: ast::AttrStyle::Inner,
-        value: item,
-        is_sugared_doc: false,
-    })
+    mk_spanned_attr_inner(DUMMY_SP, id, item)
+}
+
+/// Returns an innter attribute with the given value and span.
+pub fn mk_spanned_attr_inner(sp: Span, id: AttrId, item: P<MetaItem>) -> Attribute {
+    respan(sp,
+           Attribute_ {
+            id: id,
+            style: ast::AttrStyle::Inner,
+            value: item,
+            is_sugared_doc: false,
+          })
 }
 
+
 /// Returns an outer attribute with the given value.
 pub fn mk_attr_outer(id: AttrId, item: P<MetaItem>) -> Attribute {
+    mk_spanned_attr_outer(DUMMY_SP, id, item)
+}
+
+/// Returns an outer attribute with the given value and span.
+pub fn mk_spanned_attr_outer(sp: Span, id: AttrId, item: P<MetaItem>) -> Attribute {
+    respan(sp,
+           Attribute_ {
+            id: id,
+            style: ast::AttrStyle::Outer,
+            value: item,
+            is_sugared_doc: false,
+          })
+}
+
+pub fn mk_doc_attr_outer(id: AttrId, item: P<MetaItem>, is_sugared_doc: bool) -> Attribute {
     dummy_spanned(Attribute_ {
         id: id,
         style: ast::AttrStyle::Outer,
         value: item,
-        is_sugared_doc: false,
+        is_sugared_doc: is_sugared_doc,
     })
 }
 
diff --git a/src/libsyntax/codemap.rs b/src/libsyntax/codemap.rs
index a8aca90e623..b176b8fefc6 100644
--- a/src/libsyntax/codemap.rs
+++ b/src/libsyntax/codemap.rs
@@ -71,6 +71,23 @@ pub fn dummy_spanned<T>(t: T) -> Spanned<T> {
     respan(DUMMY_SP, t)
 }
 
+/// Build a span that covers the two provided spans.
+pub fn combine_spans(sp1: Span, sp2: Span) -> Span {
+    if sp1 == DUMMY_SP && sp2 == DUMMY_SP {
+        DUMMY_SP
+    } else if sp1 == DUMMY_SP {
+        sp2
+    } else if sp2 == DUMMY_SP {
+        sp1
+    } else {
+        Span {
+            lo: if sp1.lo < sp2.lo { sp1.lo } else { sp2.lo },
+            hi: if sp1.hi > sp2.hi { sp1.hi } else { sp2.hi },
+            expn_id: if sp1.expn_id == sp2.expn_id { sp1.expn_id } else { NO_EXPANSION },
+        }
+    }
+}
+
 #[derive(Clone, Hash, Debug)]
 pub struct NameAndSpan {
     /// The format with which the macro was invoked.
diff --git a/src/libsyntax/config.rs b/src/libsyntax/config.rs
index ff75149f518..a825cf866a8 100644
--- a/src/libsyntax/config.rs
+++ b/src/libsyntax/config.rs
@@ -124,7 +124,7 @@ pub fn strip_unconfigured_items(mut krate: ast::Crate, sess: &ParseSess, should_
         };
 
         let err_count = sess.span_diagnostic.err_count();
-        let krate_attrs = strip_unconfigured.process_cfg_attrs(krate.attrs.clone());
+        let krate_attrs = strip_unconfigured.configure(krate.attrs.clone()).unwrap_or_default();
         features = get_features(&sess.span_diagnostic, &krate_attrs);
         if err_count < sess.span_diagnostic.err_count() {
             krate.attrs = krate_attrs.clone(); // Avoid reconfiguring malformed `cfg_attr`s
diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 435241f426e..5d6429f7bdf 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -1135,30 +1135,19 @@ impl<'a> AstBuilder for ExtCtxt<'a> {
     }
 
     fn attribute(&self, sp: Span, mi: P<ast::MetaItem>) -> ast::Attribute {
-        respan(sp, ast::Attribute_ {
-            id: attr::mk_attr_id(),
-            style: ast::AttrStyle::Outer,
-            value: mi,
-            is_sugared_doc: false,
-        })
+        attr::mk_spanned_attr_outer(sp, attr::mk_attr_id(), mi)
     }
 
     fn meta_word(&self, sp: Span, w: InternedString) -> P<ast::MetaItem> {
-        P(respan(sp, ast::MetaItemKind::Word(w)))
+        attr::mk_spanned_word_item(sp, w)
     }
-    fn meta_list(&self,
-                 sp: Span,
-                 name: InternedString,
-                 mis: Vec<P<ast::MetaItem>> )
+    fn meta_list(&self, sp: Span, name: InternedString, mis: Vec<P<ast::MetaItem>>)
                  -> P<ast::MetaItem> {
-        P(respan(sp, ast::MetaItemKind::List(name, mis)))
+        attr::mk_spanned_list_item(sp, name, mis)
     }
-    fn meta_name_value(&self,
-                       sp: Span,
-                       name: InternedString,
-                       value: ast::LitKind)
+    fn meta_name_value(&self, sp: Span, name: InternedString, value: ast::LitKind)
                        -> P<ast::MetaItem> {
-        P(respan(sp, ast::MetaItemKind::NameValue(name, respan(sp, value))))
+        attr::mk_spanned_name_value_item(sp, name, respan(sp, value))
     }
 
     fn item_use(&self, sp: Span,
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index 18342f2e38c..5293d2ab000 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -302,9 +302,8 @@ fn contains_macro_use(fld: &mut MacroExpander, attrs: &[ast::Attribute]) -> bool
         };
 
         if is_use {
-            match attr.node.value.node {
-                ast::MetaItemKind::Word(..) => (),
-                _ => fld.cx.span_err(attr.span, "arguments to macro_use are not allowed here"),
+            if !attr.is_word() {
+              fld.cx.span_err(attr.span, "arguments to macro_use are not allowed here");
             }
             return true;
         }
diff --git a/src/libsyntax/ext/quote.rs b/src/libsyntax/ext/quote.rs
index ffc950d76dd..b70e270df54 100644
--- a/src/libsyntax/ext/quote.rs
+++ b/src/libsyntax/ext/quote.rs
@@ -581,9 +581,10 @@ fn mk_binop(cx: &ExtCtxt, sp: Span, bop: token::BinOpToken) -> P<ast::Expr> {
 
 fn mk_delim(cx: &ExtCtxt, sp: Span, delim: token::DelimToken) -> P<ast::Expr> {
     let name = match delim {
-        token::Paren     => "Paren",
-        token::Bracket   => "Bracket",
-        token::Brace     => "Brace",
+        token::Paren   => "Paren",
+        token::Bracket => "Bracket",
+        token::Brace   => "Brace",
+        token::NoDelim => "NoDelim",
     };
     mk_token_path(cx, sp, name)
 }
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index 7c0d10669f3..29a300b172e 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -14,7 +14,7 @@ use syntax_pos::{Span, DUMMY_SP};
 use errors::{Handler, DiagnosticBuilder};
 use ext::tt::macro_parser::{NamedMatch, MatchedSeq, MatchedNonterminal};
 use parse::token::{DocComment, MatchNt, SubstNt};
-use parse::token::{Token, NtIdent, SpecialMacroVar};
+use parse::token::{Token, Interpolated, NtIdent, NtTT, SpecialMacroVar};
 use parse::token;
 use parse::lexer::TokenAndSpan;
 use tokenstream::{self, TokenTree};
@@ -278,9 +278,9 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
             }
             // FIXME #2887: think about span stuff here
             TokenTree::Token(sp, SubstNt(ident)) => {
-                r.stack.last_mut().unwrap().idx += 1;
                 match lookup_cur_matched(r, ident) {
                     None => {
+                        r.stack.last_mut().unwrap().idx += 1;
                         r.cur_span = sp;
                         r.cur_tok = SubstNt(ident);
                         return ret_val;
@@ -292,14 +292,24 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
                             // (a) idents can be in lots of places, so it'd be a pain
                             // (b) we actually can, since it's a token.
                             MatchedNonterminal(NtIdent(ref sn)) => {
+                                r.stack.last_mut().unwrap().idx += 1;
                                 r.cur_span = sn.span;
                                 r.cur_tok = token::Ident(sn.node);
                                 return ret_val;
                             }
+                            MatchedNonterminal(NtTT(ref tt)) => {
+                                r.stack.push(TtFrame {
+                                    forest: TokenTree::Token(sp, Interpolated(NtTT(tt.clone()))),
+                                    idx: 0,
+                                    dotdotdoted: false,
+                                    sep: None,
+                                });
+                            }
                             MatchedNonterminal(ref other_whole_nt) => {
+                                r.stack.last_mut().unwrap().idx += 1;
                                 // FIXME(pcwalton): Bad copy.
                                 r.cur_span = sp;
-                                r.cur_tok = token::Interpolated((*other_whole_nt).clone());
+                                r.cur_tok = Interpolated((*other_whole_nt).clone());
                                 return ret_val;
                             }
                             MatchedSeq(..) => {
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 27485ee65fc..29da0fb1a27 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -481,6 +481,16 @@ pub const KNOWN_ATTRIBUTES: &'static [(&'static str, AttributeType, AttributeGat
                                         is just used for rustc unit tests \
                                         and will never be stable",
                                        cfg_fn!(rustc_attrs))),
+    ("rustc_partition_reused", Whitelisted, Gated("rustc_attrs",
+                                                  "this attribute \
+                                                   is just used for rustc unit tests \
+                                                   and will never be stable",
+                                                  cfg_fn!(rustc_attrs))),
+    ("rustc_partition_translated", Whitelisted, Gated("rustc_attrs",
+                                                      "this attribute \
+                                                       is just used for rustc unit tests \
+                                                       and will never be stable",
+                                                      cfg_fn!(rustc_attrs))),
     ("rustc_symbol_name", Whitelisted, Gated("rustc_attrs",
                                              "internal rustc attributes will never be stable",
                                              cfg_fn!(rustc_attrs))),
@@ -800,6 +810,29 @@ macro_rules! gate_feature_post {
     }}
 }
 
+impl<'a> PostExpansionVisitor<'a> {
+    fn check_abi(&self, abi: Abi, span: Span) {
+        match abi {
+            Abi::RustIntrinsic =>
+                gate_feature_post!(&self, intrinsics, span,
+                                   "intrinsics are subject to change"),
+            Abi::PlatformIntrinsic => {
+                gate_feature_post!(&self, platform_intrinsics, span,
+                                   "platform intrinsics are experimental and possibly buggy")
+            },
+            Abi::Vectorcall => {
+                gate_feature_post!(&self, abi_vectorcall, span,
+                                   "vectorcall is experimental and subject to change")
+            }
+            Abi::RustCall => {
+                gate_feature_post!(&self, unboxed_closures, span,
+                                   "rust-call ABI is subject to change");
+            }
+            _ => {}
+        }
+    }
+}
+
 impl<'a> Visitor for PostExpansionVisitor<'a> {
     fn visit_attribute(&mut self, attr: &ast::Attribute) {
         if !self.context.cm.span_allows_unstable(attr.span) {
@@ -831,21 +864,7 @@ impl<'a> Visitor for PostExpansionVisitor<'a> {
                                        across platforms, it is recommended to \
                                        use `#[link(name = \"foo\")]` instead")
                 }
-                match foreign_module.abi {
-                    Abi::RustIntrinsic =>
-                        gate_feature_post!(&self, intrinsics, i.span,
-                                           "intrinsics are subject to change"),
-                    Abi::PlatformIntrinsic => {
-                        gate_feature_post!(&self, platform_intrinsics, i.span,
-                                           "platform intrinsics are experimental \
-                                            and possibly buggy")
-                    },
-                    Abi::Vectorcall => {
-                        gate_feature_post!(&self, abi_vectorcall, i.span,
-                                           "vectorcall is experimental and subject to change")
-                    }
-                    _ => ()
-                }
+                self.check_abi(foreign_module.abi, i.span);
             }
 
             ast::ItemKind::Fn(..) => {
@@ -928,6 +947,16 @@ impl<'a> Visitor for PostExpansionVisitor<'a> {
         visit::walk_foreign_item(self, i)
     }
 
+    fn visit_ty(&mut self, ty: &ast::Ty) {
+        match ty.node {
+            ast::TyKind::BareFn(ref bare_fn_ty) => {
+                self.check_abi(bare_fn_ty.abi, ty.span);
+            }
+            _ => {}
+        }
+        visit::walk_ty(self, ty)
+    }
+
     fn visit_expr(&mut self, e: &ast::Expr) {
         match e.node {
             ast::ExprKind::Box(_) => {
@@ -1015,23 +1044,10 @@ impl<'a> Visitor for PostExpansionVisitor<'a> {
         }
 
         match fn_kind {
-            FnKind::ItemFn(_, _, _, _, abi, _) if abi == Abi::RustIntrinsic => {
-                gate_feature_post!(&self, intrinsics,
-                                  span,
-                                  "intrinsics are subject to change")
-            }
             FnKind::ItemFn(_, _, _, _, abi, _) |
-            FnKind::Method(_, &ast::MethodSig { abi, .. }, _) => match abi {
-                Abi::RustCall => {
-                    gate_feature_post!(&self, unboxed_closures, span,
-                        "rust-call ABI is subject to change");
-                },
-                Abi::Vectorcall => {
-                    gate_feature_post!(&self, abi_vectorcall, span,
-                        "vectorcall is experimental and subject to change");
-                },
-                _ => {}
-            },
+            FnKind::Method(_, &ast::MethodSig { abi, .. }, _) => {
+                self.check_abi(abi, span);
+            }
             _ => {}
         }
         visit::walk_fn(self, fn_kind, fn_decl, block, span);
@@ -1044,7 +1060,10 @@ impl<'a> Visitor for PostExpansionVisitor<'a> {
                                   ti.span,
                                   "associated constants are experimental")
             }
-            ast::TraitItemKind::Method(ref sig, _) => {
+            ast::TraitItemKind::Method(ref sig, ref block) => {
+                if block.is_none() {
+                    self.check_abi(sig.abi, ti.span);
+                }
                 if sig.constness == ast::Constness::Const {
                     gate_feature_post!(&self, const_fn, ti.span, "const fn is unstable");
                 }
@@ -1108,14 +1127,13 @@ pub fn get_features(span_handler: &Handler, krate_attrs: &[ast::Attribute]) -> F
             }
             Some(list) => {
                 for mi in list {
-                    let name = match mi.node {
-                        ast::MetaItemKind::Word(ref word) => (*word).clone(),
-                        _ => {
-                            span_err!(span_handler, mi.span, E0556,
-                                      "malformed feature, expected just one word");
-                            continue
-                        }
-                    };
+                    let name = if mi.is_word() {
+                                   mi.name()
+                               } else {
+                                   span_err!(span_handler, mi.span, E0556,
+                                             "malformed feature, expected just one word");
+                                   continue
+                               };
                     if let Some(&(_, _, _, setter)) = ACTIVE_FEATURES.iter()
                         .find(|& &(n, _, _, _)| name == n) {
                         *(setter(&mut features)) = true;
diff --git a/src/libsyntax/parse/mod.rs b/src/libsyntax/parse/mod.rs
index 2147e8ec2eb..7b28952aff6 100644
--- a/src/libsyntax/parse/mod.rs
+++ b/src/libsyntax/parse/mod.rs
@@ -237,7 +237,7 @@ pub fn new_parser_from_ts<'a>(sess: &'a ParseSess,
                               cfg: ast::CrateConfig,
                               ts: tokenstream::TokenStream)
                               -> Parser<'a> {
-    tts_to_parser(sess, ts.tts, cfg)
+    tts_to_parser(sess, ts.to_tts(), cfg)
 }
 
 
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 125f1abb062..c143e190c6f 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -258,6 +258,7 @@ pub struct Parser<'a> {
     pub tokens_consumed: usize,
     pub restrictions: Restrictions,
     pub quote_depth: usize, // not (yet) related to the quasiquoter
+    parsing_token_tree: bool,
     pub reader: Box<Reader+'a>,
     /// The set of seen errors about obsolete syntax. Used to suppress
     /// extra detail when the same error is seen twice
@@ -374,6 +375,7 @@ impl<'a> Parser<'a> {
             tokens_consumed: 0,
             restrictions: Restrictions::empty(),
             quote_depth: 0,
+            parsing_token_tree: false,
             obsolete_set: HashSet::new(),
             mod_path_stack: Vec::new(),
             filename: filename,
@@ -2663,7 +2665,7 @@ impl<'a> Parser<'a> {
     }
 
     pub fn check_unknown_macro_variable(&mut self) {
-        if self.quote_depth == 0 {
+        if self.quote_depth == 0 && !self.parsing_token_tree {
             match self.token {
                 token::SubstNt(name) =>
                     self.fatal(&format!("unknown macro variable `{}`", name)).emit(),
@@ -2723,6 +2725,7 @@ impl<'a> Parser<'a> {
                 Err(err)
             },
             token::OpenDelim(delim) => {
+                let parsing_token_tree = ::std::mem::replace(&mut self.parsing_token_tree, true);
                 // The span for beginning of the delimited section
                 let pre_span = self.span;
 
@@ -2787,6 +2790,7 @@ impl<'a> Parser<'a> {
                     _ => {}
                 }
 
+                self.parsing_token_tree = parsing_token_tree;
                 Ok(TokenTree::Delimited(span, Rc::new(Delimited {
                     delim: delim,
                     open_span: open_span,
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index f0a6f8edeec..6fdc9b714d3 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -48,6 +48,8 @@ pub enum DelimToken {
     Bracket,
     /// A curly brace: `{` or `}`
     Brace,
+    /// An empty delimiter
+    NoDelim,
 }
 
 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Debug, Copy)]
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 8866ffc2575..a619da84b2d 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -242,6 +242,8 @@ pub fn token_to_string(tok: &Token) -> String {
         token::CloseDelim(token::Bracket) => "]".to_string(),
         token::OpenDelim(token::Brace) => "{".to_string(),
         token::CloseDelim(token::Brace) => "}".to_string(),
+        token::OpenDelim(token::NoDelim) => " ".to_string(),
+        token::CloseDelim(token::NoDelim) => " ".to_string(),
         token::Pound                => "#".to_string(),
         token::Dollar               => "$".to_string(),
         token::Question             => "?".to_string(),
@@ -1777,12 +1779,14 @@ impl<'a> State<'a> {
                 try!(self.head(""));
                 try!(self.bopen());
             }
+            token::NoDelim => {}
         }
         try!(self.print_tts(&m.node.tts));
         match delim {
             token::Paren => self.pclose(),
             token::Bracket => word(&mut self.s, "]"),
             token::Brace => self.bclose(m.span),
+            token::NoDelim => Ok(()),
         }
     }
 
diff --git a/src/libsyntax/tokenstream.rs b/src/libsyntax/tokenstream.rs
index 0ad09fd0f7d..89ead21cc10 100644
--- a/src/libsyntax/tokenstream.rs
+++ b/src/libsyntax/tokenstream.rs
@@ -16,27 +16,27 @@
 //! or a SequenceRepetition specifier (for the purpose of sequence generation during macro
 //! expansion).
 //!
-//! A TokenStream also has a slice view, `TokenSlice`, that is analogous to `str` for
-//! `String`: it allows the programmer to divvy up, explore, and otherwise partition a
-//! TokenStream as borrowed subsequences.
+//! ## Ownership
+//! TokenStreams are persistant data structures construced as ropes with reference
+//! counted-children. In general, this means that calling an operation on a TokenStream
+//! (such as `slice`) produces an entirely new TokenStream from the borrowed reference to
+//! the original. This essentially coerces TokenStreams into 'views' of their subparts,
+//! and a borrowed TokenStream is sufficient to build an owned TokenStream without taking
+//! ownership of the original.
 
 use ast::{self, AttrStyle, LitKind};
 use syntax_pos::{Span, DUMMY_SP, NO_EXPANSION};
-use codemap::Spanned;
+use codemap::{Spanned, combine_spans};
 use ext::base;
 use ext::tt::macro_parser;
 use parse::lexer::comments::{doc_comment_style, strip_doc_comment_decoration};
 use parse::lexer;
 use parse;
-use parse::token::{self, Token, Lit, InternedString, Nonterminal};
-use parse::token::Lit as TokLit;
+use parse::token::{self, Token, Lit, Nonterminal};
 
 use std::fmt;
-use std::mem;
-use std::ops::Index;
-use std::ops;
 use std::iter::*;
-
+use std::ops::{self, Index};
 use std::rc::Rc;
 
 /// A delimited sequence of token trees
@@ -135,6 +135,7 @@ impl TokenTree {
             }
             TokenTree::Token(_, token::SpecialVarNt(..)) => 2,
             TokenTree::Token(_, token::MatchNt(..)) => 3,
+            TokenTree::Token(_, token::Interpolated(Nonterminal::NtTT(..))) => 1,
             TokenTree::Delimited(_, ref delimed) => delimed.tts.len() + 2,
             TokenTree::Sequence(_, ref seq) => seq.tts.len(),
             TokenTree::Token(..) => 0,
@@ -197,6 +198,9 @@ impl TokenTree {
                          TokenTree::Token(sp, token::Ident(kind))];
                 v[index].clone()
             }
+            (&TokenTree::Token(_, token::Interpolated(Nonterminal::NtTT(ref tt))), _) => {
+                tt.clone().unwrap()
+            }
             (&TokenTree::Sequence(_, ref seq), _) => seq.tts[index].clone(),
             _ => panic!("Cannot expand a token tree"),
         }
@@ -331,27 +335,51 @@ impl TokenTree {
 /// struct itself shouldn't be directly manipulated; the internal structure is not stable,
 /// and may be changed at any time in the future. The operators will not, however (except
 /// for signatures, later on).
-#[derive(Eq,Clone,Hash,RustcEncodable,RustcDecodable)]
+#[derive(Clone, Eq, Hash, RustcEncodable, RustcDecodable)]
 pub struct TokenStream {
-    pub span: Span,
-    pub tts: Vec<TokenTree>,
+    ts: InternalTS,
+}
+
+// NB If Leaf access proves to be slow, inroducing a secondary Leaf without the bounds
+// for unsliced Leafs may lead to some performance improvemenet.
+#[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
+pub enum InternalTS {
+    Empty(Span),
+    Leaf {
+        tts: Rc<Vec<TokenTree>>,
+        offset: usize,
+        len: usize,
+        sp: Span,
+    },
+    Node {
+        left: Rc<InternalTS>,
+        right: Rc<InternalTS>,
+        len: usize,
+        sp: Span,
+    },
 }
 
 impl fmt::Debug for TokenStream {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        if self.tts.len() == 0 {
-            write!(f, "([empty")?;
-        } else {
-            write!(f, "([")?;
-            write!(f, "{:?}", self.tts[0])?;
-
-            for tt in self.tts.iter().skip(1) {
-                write!(f, ",{:?}", tt)?;
+        self.ts.fmt(f)
+    }
+}
+
+impl fmt::Debug for InternalTS {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match *self {
+            InternalTS::Empty(..) => Ok(()),
+            InternalTS::Leaf { ref tts, offset, len, .. } => {
+                for t in tts.iter().skip(offset).take(len) {
+                    try!(write!(f, "{:?}", t));
+                }
+                Ok(())
+            }
+            InternalTS::Node { ref left, ref right, .. } => {
+                try!(left.fmt(f));
+                right.fmt(f)
             }
         }
-        write!(f, "|")?;
-        self.span.fmt(f)?;
-        write!(f, "])")
     }
 }
 
@@ -359,7 +387,7 @@ impl fmt::Debug for TokenStream {
 /// equality, see `eq_unspanned`.
 impl PartialEq<TokenStream> for TokenStream {
     fn eq(&self, other: &TokenStream) -> bool {
-        self.tts == other.tts
+        self.iter().eq(other.iter())
     }
 }
 
@@ -404,6 +432,59 @@ fn covering_span(trees: &[TokenTree]) -> Span {
     }
 }
 
+impl InternalTS {
+    fn len(&self) -> usize {
+        match *self {
+            InternalTS::Empty(..) => 0,
+            InternalTS::Leaf { len, .. } => len,
+            InternalTS::Node { len, .. } => len,
+        }
+    }
+
+    fn span(&self) -> Span {
+        match *self {
+            InternalTS::Empty(sp) |
+            InternalTS::Leaf { sp, .. } |
+            InternalTS::Node { sp, .. } => sp,
+        }
+    }
+
+    fn slice(&self, range: ops::Range<usize>) -> TokenStream {
+        let from = range.start;
+        let to = range.end;
+        if from == to {
+            return TokenStream::mk_empty();
+        }
+        if from > to {
+            panic!("Invalid range: {} to {}", from, to);
+        }
+        if from == 0 && to == self.len() {
+            return TokenStream { ts: self.clone() }; /* should be cheap */
+        }
+        match *self {
+            InternalTS::Empty(..) => panic!("Invalid index"),
+            InternalTS::Leaf { ref tts, offset, .. } => {
+                let offset = offset + from;
+                let len = to - from;
+                TokenStream::mk_sub_leaf(tts.clone(),
+                                         offset,
+                                         len,
+                                         covering_span(&tts[offset..offset + len]))
+            }
+            InternalTS::Node { ref left, ref right, .. } => {
+                let left_len = left.len();
+                if to <= left_len {
+                    left.slice(range)
+                } else if from >= left_len {
+                    right.slice(from - left_len..to - left_len)
+                } else {
+                    TokenStream::concat(left.slice(from..left_len), right.slice(0..to - left_len))
+                }
+            }
+        }
+    }
+}
+
 /// TokenStream operators include basic destructuring, boolean operations, `maybe_...`
 /// operations, and `maybe_..._prefix` operations. Boolean operations are straightforward,
 /// indicating information about the structure of the stream. The `maybe_...` operations
@@ -415,129 +496,149 @@ fn covering_span(trees: &[TokenTree]) -> Span {
 ///
 ///    `maybe_path_prefix("a::b::c(a,b,c).foo()") -> (a::b::c, "(a,b,c).foo()")`
 impl TokenStream {
-    /// Convert a vector of `TokenTree`s into a `TokenStream`.
-    pub fn from_tts(trees: Vec<TokenTree>) -> TokenStream {
-        let span = covering_span(&trees);
-        TokenStream {
-            tts: trees,
-            span: span,
-        }
+    pub fn mk_empty() -> TokenStream {
+        TokenStream { ts: InternalTS::Empty(DUMMY_SP) }
     }
 
-    /// Copies all of the TokenTrees from the TokenSlice, appending them to the stream.
-    pub fn append_stream(mut self, ts2: &TokenSlice) {
-        for tt in ts2.iter() {
-            self.tts.push(tt.clone());
-        }
-        self.span = covering_span(&self.tts[..]);
+    fn mk_spanned_empty(sp: Span) -> TokenStream {
+        TokenStream { ts: InternalTS::Empty(sp) }
     }
 
-    /// Manually change a TokenStream's span.
-    pub fn respan(self, span: Span) -> TokenStream {
+    fn mk_leaf(tts: Rc<Vec<TokenTree>>, sp: Span) -> TokenStream {
+        let len = tts.len();
         TokenStream {
-            tts: self.tts,
-            span: span,
+            ts: InternalTS::Leaf {
+                tts: tts,
+                offset: 0,
+                len: len,
+                sp: sp,
+            },
         }
     }
 
-    /// Construct a TokenStream from an ast literal.
-    pub fn from_ast_lit_str(lit: ast::Lit) -> Option<TokenStream> {
-        match lit.node {
-            LitKind::Str(val, _) => {
-                let val = TokLit::Str_(token::intern(&val));
-                Some(TokenStream::from_tts(vec![TokenTree::Token(lit.span,
-                                                                 Token::Literal(val, None))]))
-            }
-            _ => None,
+    fn mk_sub_leaf(tts: Rc<Vec<TokenTree>>, offset: usize, len: usize, sp: Span) -> TokenStream {
+        TokenStream {
+            ts: InternalTS::Leaf {
+                tts: tts,
+                offset: offset,
+                len: len,
+                sp: sp,
+            },
         }
-
     }
 
-    /// Convert a vector of TokenTrees into a parentheses-delimited TokenStream.
-    pub fn as_paren_delimited_stream(tts: Vec<TokenTree>) -> TokenStream {
-        let new_sp = covering_span(&tts);
-
-        let new_delim = Rc::new(Delimited {
-            delim: token::DelimToken::Paren,
-            open_span: DUMMY_SP,
-            tts: tts,
-            close_span: DUMMY_SP,
-        });
-
-        TokenStream::from_tts(vec![TokenTree::Delimited(new_sp, new_delim)])
+    fn mk_int_node(left: Rc<InternalTS>,
+                   right: Rc<InternalTS>,
+                   len: usize,
+                   sp: Span)
+                   -> TokenStream {
+        TokenStream {
+            ts: InternalTS::Node {
+                left: left,
+                right: right,
+                len: len,
+                sp: sp,
+            },
+        }
     }
 
-    /// Convert an interned string into a one-element TokenStream.
-    pub fn from_interned_string_as_ident(s: InternedString) -> TokenStream {
-        TokenStream::from_tts(vec![TokenTree::Token(DUMMY_SP,
-                                                    Token::Ident(token::str_to_ident(&s[..])))])
+    /// Convert a vector of `TokenTree`s into a `TokenStream`.
+    pub fn from_tts(trees: Vec<TokenTree>) -> TokenStream {
+        let span = covering_span(&trees[..]);
+        TokenStream::mk_leaf(Rc::new(trees), span)
     }
-}
-
-/// TokenSlices are 'views' of `TokenStream's; they fit the same role as `str`s do for
-/// `String`s. In general, most TokenStream manipulations will be refocusing their internal
-/// contents by taking a TokenSlice and then using indexing and the provided operators.
-#[derive(PartialEq, Eq, Debug)]
-pub struct TokenSlice([TokenTree]);
 
-impl ops::Deref for TokenStream {
-    type Target = TokenSlice;
-
-    fn deref(&self) -> &TokenSlice {
-        let tts: &[TokenTree] = &*self.tts;
-        unsafe { mem::transmute(tts) }
+    /// Manually change a TokenStream's span.
+    pub fn respan(self, span: Span) -> TokenStream {
+        match self.ts {
+            InternalTS::Empty(..) => TokenStream::mk_spanned_empty(span),
+            InternalTS::Leaf { tts, offset, len, .. } => {
+                TokenStream::mk_sub_leaf(tts, offset, len, span)
+            }
+            InternalTS::Node { left, right, len, .. } => {
+                TokenStream::mk_int_node(left, right, len, span)
+            }
+        }
     }
-}
 
-impl TokenSlice {
-    /// Convert a borrowed TokenTree slice into a borrowed TokenSlice.
-    fn from_tts(tts: &[TokenTree]) -> &TokenSlice {
-        unsafe { mem::transmute(tts) }
+    /// Concatenates two TokenStreams into a new TokenStream
+    pub fn concat(left: TokenStream, right: TokenStream) -> TokenStream {
+        let new_len = left.len() + right.len();
+        let new_span = combine_spans(left.span(), right.span());
+        TokenStream::mk_int_node(Rc::new(left.ts), Rc::new(right.ts), new_len, new_span)
     }
 
-    /// Indicates whether the `TokenStream` is empty.
+    /// Indicate if the TokenStream is empty.
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
 
-    /// Return the `TokenSlice`'s length.
+    /// Return a TokenStream's length.
     pub fn len(&self) -> usize {
-        self.0.len()
+        self.ts.len()
     }
 
-    /// Check equality versus another TokenStream, ignoring span information.
-    pub fn eq_unspanned(&self, other: &TokenSlice) -> bool {
-        if self.len() != other.len() {
-            return false;
-        }
-        for (tt1, tt2) in self.iter().zip(other.iter()) {
-            if !tt1.eq_unspanned(tt2) {
-                return false;
+    /// Convert a TokenStream into a vector of borrowed TokenTrees.
+    pub fn to_vec(&self) -> Vec<&TokenTree> {
+        fn internal_to_vec(ts: &InternalTS) -> Vec<&TokenTree> {
+            match *ts {
+                InternalTS::Empty(..) => Vec::new(),
+                InternalTS::Leaf { ref tts, offset, len, .. } => {
+                    tts[offset..offset + len].iter().collect()
+                }
+                InternalTS::Node { ref left, ref right, .. } => {
+                    let mut v1 = internal_to_vec(left);
+                    let mut v2 = internal_to_vec(right);
+                    v1.append(&mut v2);
+                    v1
+                }
             }
         }
-        true
+        internal_to_vec(&self.ts)
     }
 
-    /// Compute a span that covers the entire TokenSlice (eg, one wide enough to include
-    /// the entire slice). If the inputs share expansion identification, it is preserved.
-    /// If they do not, it is discarded.
-    pub fn covering_span(&self) -> Span {
-        covering_span(&self.0)
+    /// Convert a TokenStream into a vector of TokenTrees (by cloning the TokenTrees).
+    /// (This operation is an O(n) deep copy of the underlying structure.)
+    pub fn to_tts(&self) -> Vec<TokenTree> {
+        self.to_vec().into_iter().cloned().collect::<Vec<TokenTree>>()
     }
 
-    /// Indicates where the stream is of the form `= <ts>`, where `<ts>` is a continued
-    /// `TokenStream`.
-    pub fn is_assignment(&self) -> bool {
-        self.maybe_assignment().is_some()
+    /// Return the TokenStream's span.
+    pub fn span(&self) -> Span {
+        self.ts.span()
     }
 
-    /// Returns the RHS of an assigment.
-    pub fn maybe_assignment(&self) -> Option<&TokenSlice> {
-        if !(self.len() > 1) {
-            return None;
+    /// Returns an iterator over a TokenStream (as a sequence of TokenTrees).
+    pub fn iter<'a>(&self) -> Iter {
+        Iter { vs: self, idx: 0 }
+    }
+
+    /// Splits a TokenStream based on the provided `&TokenTree -> bool` predicate.
+    pub fn split<P>(&self, pred: P) -> Split<P>
+        where P: FnMut(&TokenTree) -> bool
+    {
+        Split {
+            vs: self,
+            pred: pred,
+            finished: false,
+            idx: 0,
         }
+    }
 
-        Some(&self[1..])
+    /// Produce a slice of the input TokenStream from the `from` index, inclusive, to the
+    /// `to` index, non-inclusive.
+    pub fn slice(&self, range: ops::Range<usize>) -> TokenStream {
+        self.ts.slice(range)
+    }
+
+    /// Slice starting at the provided index, inclusive.
+    pub fn slice_from(&self, from: ops::RangeFrom<usize>) -> TokenStream {
+        self.slice(from.start..self.len())
+    }
+
+    /// Slice up to the provided index, non-inclusive.
+    pub fn slice_to(&self, to: ops::RangeTo<usize>) -> TokenStream {
+        self.slice(0..to.end)
     }
 
     /// Indicates where the stream is a single, delimited expression (e.g., `(a,b,c)` or
@@ -547,50 +648,15 @@ impl TokenSlice {
     }
 
     /// Returns the inside of the delimited term as a new TokenStream.
-    pub fn maybe_delimited(&self) -> Option<&TokenSlice> {
+    pub fn maybe_delimited(&self) -> Option<TokenStream> {
         if !(self.len() == 1) {
             return None;
         }
 
+        // FIXME It would be nice to change Delimited to move the Rc around the TokenTree
+        // vector directly in order to avoid the clone here.
         match self[0] {
-            TokenTree::Delimited(_, ref rc) => Some(TokenSlice::from_tts(&*rc.tts)),
-            _ => None,
-        }
-    }
-
-    /// Returns a list of `TokenSlice`s if the stream is a delimited list, breaking the
-    /// stream on commas.
-    pub fn maybe_comma_list(&self) -> Option<Vec<&TokenSlice>> {
-        let maybe_tts = self.maybe_delimited();
-
-        let ts: &TokenSlice;
-        match maybe_tts {
-            Some(t) => {
-                ts = t;
-            }
-            None => {
-                return None;
-            }
-        }
-
-        let splits: Vec<&TokenSlice> = ts.split(|x| match *x {
-                TokenTree::Token(_, Token::Comma) => true,
-                _ => false,
-            })
-            .filter(|x| x.len() > 0)
-            .collect();
-
-        Some(splits)
-    }
-
-    /// Returns a Nonterminal if it is Interpolated.
-    pub fn maybe_interpolated_nonterminal(&self) -> Option<Nonterminal> {
-        if !(self.len() == 1) {
-            return None;
-        }
-
-        match self[0] {
-            TokenTree::Token(_, Token::Interpolated(ref nt)) => Some(nt.clone()),
+            TokenTree::Delimited(_, ref rc) => Some(TokenStream::from_tts(rc.tts.clone())),
             _ => None,
         }
     }
@@ -606,180 +672,54 @@ impl TokenSlice {
             return None;
         }
 
-        let tok = if let Some(tts) = self.maybe_delimited() {
-            if tts.len() != 1 {
-                return None;
-            }
-            &tts[0]
-        } else {
-            &self[0]
-        };
-
-        match *tok {
+        match self[0] {
             TokenTree::Token(_, Token::Ident(t)) => Some(t),
             _ => None,
         }
     }
 
-    /// Indicates if the stream is exactly one literal
-    pub fn is_lit(&self) -> bool {
-        self.maybe_lit().is_some()
-    }
-
-    /// Returns a literal
-    pub fn maybe_lit(&self) -> Option<token::Lit> {
-        if !(self.len() == 1) {
-            return None;
-        }
-
-        let tok = if let Some(tts) = self.maybe_delimited() {
-            if tts.len() != 1 {
-                return None;
-            }
-            &tts[0]
-        } else {
-            &self[0]
-        };
-
-        match *tok {
-            TokenTree::Token(_, Token::Literal(l, _)) => Some(l),
-            _ => None,
-        }
-    }
-
-    /// Returns an AST string literal if the TokenStream is either a normal ('cooked') or
-    /// raw string literal.
-    pub fn maybe_str(&self) -> Option<ast::Lit> {
-        if !(self.len() == 1) {
-            return None;
-        }
-
-        match self[0] {
-            TokenTree::Token(sp, Token::Literal(Lit::Str_(s), _)) => {
-                let l = LitKind::Str(token::intern_and_get_ident(&parse::str_lit(&s.as_str())),
-                                     ast::StrStyle::Cooked);
-                Some(Spanned {
-                    node: l,
-                    span: sp,
-                })
-            }
-            TokenTree::Token(sp, Token::Literal(Lit::StrRaw(s, n), _)) => {
-                let l = LitKind::Str(token::intern_and_get_ident(&parse::raw_str_lit(&s.as_str())),
-                                     ast::StrStyle::Raw(n));
-                Some(Spanned {
-                    node: l,
-                    span: sp,
-                })
+    /// Compares two TokenStreams, checking equality without regarding span information.
+    pub fn eq_unspanned(&self, other: &TokenStream) -> bool {
+        for (t1, t2) in self.iter().zip(other.iter()) {
+            if !t1.eq_unspanned(t2) {
+                return false;
             }
-            _ => None,
         }
+        true
     }
 
-    /// This operation extracts the path prefix , returning an AST path struct and the remainder
-    /// of the stream (if it finds one). To be more specific, a tokenstream that has a valid,
-    /// non-global path as a prefix (eg `foo(bar, baz)`, `foo::bar(bar)`, but *not*
-    /// `::foo::bar(baz)`) will yield the path and the remaining tokens (as a slice). The previous
-    /// examples will yield
-    /// `Some((Path { segments = vec![foo], ... }, [(bar, baz)]))`,
-    /// `Some((Path { segments = vec![foo, bar] }, [(baz)]))`,
-    /// and `None`, respectively.
-    pub fn maybe_path_prefix(&self) -> Option<(ast::Path, &TokenSlice)> {
-        let mut segments: Vec<ast::PathSegment> = Vec::new();
-
-        let path: Vec<&TokenTree> = self.iter()
-            .take_while(|x| x.is_ident() || x.eq_token(Token::ModSep))
-            .collect::<Vec<&TokenTree>>();
-
-        let path_size = path.len();
-        if path_size == 0 {
-            return None;
-        }
-
-        let cov_span = self[..path_size].covering_span();
-        let rst = &self[path_size..];
-
-        let fst_id = path[0];
-
-        if let Some(id) = fst_id.maybe_ident() {
-            segments.push(ast::PathSegment {
-                identifier: id,
-                parameters: ast::PathParameters::none(),
-            });
-        } else {
-            return None;
-        }
-
-        // Let's use a state machine to parse out the rest.
-        enum State {
-            Mod, // Expect a `::`, or return None otherwise.
-            Ident, // Expect an ident, or return None otherwise.
-        }
-        let mut state = State::Mod;
-
-        for p in &path[1..] {
-            match state {
-                State::Mod => {
-                    // State 0: ['::' -> state 1, else return None]
-                    if p.eq_token(Token::ModSep) {
-                        state = State::Ident;
-                    } else {
-                        return None;
-                    }
-                }
-                State::Ident => {
-                    // State 1: [ident -> state 0, else return None]
-                    if let Some(id) = p.maybe_ident() {
-                        segments.push(ast::PathSegment {
-                            identifier: id,
-                            parameters: ast::PathParameters::none(),
-                        });
-                        state = State::Mod;
-                    } else {
-                        return None;
-                    }
-                }
-            }
-        }
-
-        let path = ast::Path {
-            span: cov_span,
-            global: false,
-            segments: segments,
-        };
-        Some((path, rst))
-    }
+    /// Convert a vector of TokenTrees into a parentheses-delimited TokenStream.
+    pub fn as_delimited_stream(tts: Vec<TokenTree>, delim: token::DelimToken) -> TokenStream {
+        let new_sp = covering_span(&tts);
 
-    /// Returns an iterator over a TokenSlice (as a sequence of TokenStreams).
-    fn iter(&self) -> Iter {
-        Iter { vs: self }
-    }
+        let new_delim = Rc::new(Delimited {
+            delim: delim,
+            open_span: DUMMY_SP,
+            tts: tts,
+            close_span: DUMMY_SP,
+        });
 
-    /// Splits a TokenSlice based on the provided `&TokenTree -> bool` predicate.
-    fn split<P>(&self, pred: P) -> Split<P>
-        where P: FnMut(&TokenTree) -> bool
-    {
-        Split {
-            vs: self,
-            pred: pred,
-            finished: false,
-        }
+        TokenStream::from_tts(vec![TokenTree::Delimited(new_sp, new_delim)])
     }
 }
 
+// FIXME Reimplement this iterator to hold onto a slice iterator for a leaf, getting the
+// next leaf's iterator when the current one is exhausted.
 pub struct Iter<'a> {
-    vs: &'a TokenSlice,
+    vs: &'a TokenStream,
+    idx: usize,
 }
 
 impl<'a> Iterator for Iter<'a> {
     type Item = &'a TokenTree;
 
     fn next(&mut self) -> Option<&'a TokenTree> {
-        if self.vs.is_empty() {
+        if self.vs.is_empty() || self.idx >= self.vs.len() {
             return None;
         }
 
-        let ret = Some(&self.vs[0]);
-        self.vs = &self.vs[1..];
+        let ret = Some(&self.vs[self.idx]);
+        self.idx = self.idx + 1;
         ret
     }
 }
@@ -787,29 +727,35 @@ impl<'a> Iterator for Iter<'a> {
 pub struct Split<'a, P>
     where P: FnMut(&TokenTree) -> bool
 {
-    vs: &'a TokenSlice,
+    vs: &'a TokenStream,
     pred: P,
     finished: bool,
+    idx: usize,
 }
 
 impl<'a, P> Iterator for Split<'a, P>
     where P: FnMut(&TokenTree) -> bool
 {
-    type Item = &'a TokenSlice;
+    type Item = TokenStream;
 
-    fn next(&mut self) -> Option<&'a TokenSlice> {
+    fn next(&mut self) -> Option<TokenStream> {
         if self.finished {
             return None;
         }
+        if self.idx >= self.vs.len() {
+            self.finished = true;
+            return None;
+        }
 
-        match self.vs.iter().position(|x| (self.pred)(x)) {
+        let mut lookup = self.vs.iter().skip(self.idx);
+        match lookup.position(|x| (self.pred)(&x)) {
             None => {
                 self.finished = true;
-                Some(&self.vs[..])
+                Some(self.vs.slice_from(self.idx..))
             }
-            Some(idx) => {
-                let ret = Some(&self.vs[..idx]);
-                self.vs = &self.vs[idx + 1..];
+            Some(edx) => {
+                let ret = Some(self.vs.slice(self.idx..self.idx + edx));
+                self.idx += edx + 1;
                 ret
             }
         }
@@ -820,98 +766,134 @@ impl Index<usize> for TokenStream {
     type Output = TokenTree;
 
     fn index(&self, index: usize) -> &TokenTree {
-        Index::index(&**self, index)
+        &self.ts[index]
     }
 }
 
-impl ops::Index<ops::Range<usize>> for TokenStream {
-    type Output = TokenSlice;
+impl Index<usize> for InternalTS {
+    type Output = TokenTree;
 
-    fn index(&self, index: ops::Range<usize>) -> &TokenSlice {
-        Index::index(&**self, index)
+    fn index(&self, index: usize) -> &TokenTree {
+        if self.len() <= index {
+            panic!("Index {} too large for {:?}", index, self);
+        }
+        match *self {
+            InternalTS::Empty(..) => panic!("Invalid index"),
+            InternalTS::Leaf { ref tts, offset, .. } => tts.get(index + offset).unwrap(),
+            InternalTS::Node { ref left, ref right, .. } => {
+                let left_len = left.len();
+                if index < left_len {
+                    Index::index(&**left, index)
+                } else {
+                    Index::index(&**right, index - left_len)
+                }
+            }
+        }
     }
 }
 
-impl ops::Index<ops::RangeTo<usize>> for TokenStream {
-    type Output = TokenSlice;
-
-    fn index(&self, index: ops::RangeTo<usize>) -> &TokenSlice {
-        Index::index(&**self, index)
-    }
-}
 
-impl ops::Index<ops::RangeFrom<usize>> for TokenStream {
-    type Output = TokenSlice;
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use syntax_pos::{Span, BytePos, NO_EXPANSION, DUMMY_SP};
+    use parse::token::{self, str_to_ident, Token};
+    use util::parser_testing::string_to_tts;
+    use std::rc::Rc;
 
-    fn index(&self, index: ops::RangeFrom<usize>) -> &TokenSlice {
-        Index::index(&**self, index)
+    fn sp(a: u32, b: u32) -> Span {
+        Span {
+            lo: BytePos(a),
+            hi: BytePos(b),
+            expn_id: NO_EXPANSION,
+        }
     }
-}
-
-impl ops::Index<ops::RangeFull> for TokenStream {
-    type Output = TokenSlice;
 
-    fn index(&self, _index: ops::RangeFull) -> &TokenSlice {
-        Index::index(&**self, _index)
+    fn as_paren_delimited_stream(tts: Vec<TokenTree>) -> TokenStream {
+        TokenStream::as_delimited_stream(tts, token::DelimToken::Paren)
     }
-}
-
-impl Index<usize> for TokenSlice {
-    type Output = TokenTree;
 
-    fn index(&self, index: usize) -> &TokenTree {
-        &self.0[index]
+    #[test]
+    fn test_concat() {
+        let test_res = TokenStream::from_tts(string_to_tts("foo::bar::baz".to_string()));
+        let test_fst = TokenStream::from_tts(string_to_tts("foo::bar".to_string()));
+        let test_snd = TokenStream::from_tts(string_to_tts("::baz".to_string()));
+        let eq_res = TokenStream::concat(test_fst, test_snd);
+        assert_eq!(test_res.len(), 5);
+        assert_eq!(eq_res.len(), 5);
+        assert_eq!(test_res.eq_unspanned(&eq_res), true);
     }
-}
-
-impl ops::Index<ops::Range<usize>> for TokenSlice {
-    type Output = TokenSlice;
 
-    fn index(&self, index: ops::Range<usize>) -> &TokenSlice {
-        TokenSlice::from_tts(&self.0[index])
+    #[test]
+    fn test_from_to_bijection() {
+        let test_start = string_to_tts("foo::bar(baz)".to_string());
+        let test_end = TokenStream::from_tts(string_to_tts("foo::bar(baz)".to_string())).to_tts();
+        assert_eq!(test_start, test_end)
     }
-}
 
-impl ops::Index<ops::RangeTo<usize>> for TokenSlice {
-    type Output = TokenSlice;
+    #[test]
+    fn test_to_from_bijection() {
+        let test_start = TokenStream::from_tts(string_to_tts("foo::bar(baz)".to_string()));
+        let test_end = TokenStream::from_tts(test_start.clone().to_tts());
+        assert_eq!(test_start, test_end)
+    }
 
-    fn index(&self, index: ops::RangeTo<usize>) -> &TokenSlice {
-        TokenSlice::from_tts(&self.0[index])
+    #[test]
+    fn test_eq_0() {
+        let test_res = TokenStream::from_tts(string_to_tts("foo".to_string()));
+        let test_eqs = TokenStream::from_tts(string_to_tts("foo".to_string()));
+        assert_eq!(test_res, test_eqs)
     }
-}
 
-impl ops::Index<ops::RangeFrom<usize>> for TokenSlice {
-    type Output = TokenSlice;
+    #[test]
+    fn test_eq_1() {
+        let test_res = TokenStream::from_tts(string_to_tts("::bar::baz".to_string()));
+        let test_eqs = TokenStream::from_tts(string_to_tts("::bar::baz".to_string()));
+        assert_eq!(test_res, test_eqs)
+    }
 
-    fn index(&self, index: ops::RangeFrom<usize>) -> &TokenSlice {
-        TokenSlice::from_tts(&self.0[index])
+    #[test]
+    fn test_eq_2() {
+        let test_res = TokenStream::from_tts(string_to_tts("foo::bar".to_string()));
+        let test_eqs = TokenStream::from_tts(string_to_tts("foo::bar::baz".to_string()));
+        assert_eq!(test_res, test_eqs.slice(0..3))
     }
-}
 
-impl ops::Index<ops::RangeFull> for TokenSlice {
-    type Output = TokenSlice;
+    #[test]
+    fn test_eq_3() {
+        let test_res = TokenStream::from_tts(string_to_tts("".to_string()));
+        let test_eqs = TokenStream::from_tts(string_to_tts("".to_string()));
+        assert_eq!(test_res, test_eqs)
+    }
 
-    fn index(&self, _index: ops::RangeFull) -> &TokenSlice {
-        TokenSlice::from_tts(&self.0[_index])
+    #[test]
+    fn test_diseq_0() {
+        let test_res = TokenStream::from_tts(string_to_tts("::bar::baz".to_string()));
+        let test_eqs = TokenStream::from_tts(string_to_tts("bar::baz".to_string()));
+        assert_eq!(test_res == test_eqs, false)
     }
-}
 
+    #[test]
+    fn test_diseq_1() {
+        let test_res = TokenStream::from_tts(string_to_tts("(bar,baz)".to_string()));
+        let test_eqs = TokenStream::from_tts(string_to_tts("bar,baz".to_string()));
+        assert_eq!(test_res == test_eqs, false)
+    }
 
-#[cfg(test)]
-mod tests {
-    use super::*;
-    use ast;
-    use syntax_pos::{Span, BytePos, NO_EXPANSION, DUMMY_SP};
-    use parse::token::{self, str_to_ident, Token, Lit};
-    use util::parser_testing::string_to_tts;
-    use std::rc::Rc;
+    #[test]
+    fn test_slice_0() {
+        let test_res = TokenStream::from_tts(string_to_tts("foo::bar".to_string()));
+        let test_eqs = TokenStream::from_tts(string_to_tts("foo::bar::baz".to_string()));
+        assert_eq!(test_res, test_eqs.slice(0..3))
+    }
 
-    fn sp(a: u32, b: u32) -> Span {
-        Span {
-            lo: BytePos(a),
-            hi: BytePos(b),
-            expn_id: NO_EXPANSION,
-        }
+    #[test]
+    fn test_slice_1() {
+        let test_res = TokenStream::from_tts(string_to_tts("foo::bar::baz".to_string()))
+            .slice(2..3);
+        let test_eqs = TokenStream::from_tts(vec![TokenTree::Token(sp(5,8),
+                                                    token::Ident(str_to_ident("bar")))]);
+        assert_eq!(test_res, test_eqs)
     }
 
     #[test]
@@ -944,38 +926,6 @@ mod tests {
     }
 
     #[test]
-    fn test_is_assign() {
-        let test0 = TokenStream::from_tts(string_to_tts("= bar::baz".to_string()));
-        let test1 = TokenStream::from_tts(string_to_tts("= \"5\"".to_string()));
-        let test2 = TokenStream::from_tts(string_to_tts("= 5".to_string()));
-        let test3 = TokenStream::from_tts(string_to_tts("(foo = 10)".to_string()));
-        let test4 = TokenStream::from_tts(string_to_tts("= (foo,bar,baz)".to_string()));
-        let test5 = TokenStream::from_tts(string_to_tts("".to_string()));
-
-        assert_eq!(test0.is_assignment(), true);
-        assert_eq!(test1.is_assignment(), true);
-        assert_eq!(test2.is_assignment(), true);
-        assert_eq!(test3.is_assignment(), false);
-        assert_eq!(test4.is_assignment(), true);
-        assert_eq!(test5.is_assignment(), false);
-    }
-
-    #[test]
-    fn test_is_lit() {
-        let test0 = TokenStream::from_tts(string_to_tts("\"foo\"".to_string()));
-        let test1 = TokenStream::from_tts(string_to_tts("5".to_string()));
-        let test2 = TokenStream::from_tts(string_to_tts("foo".to_string()));
-        let test3 = TokenStream::from_tts(string_to_tts("foo::bar".to_string()));
-        let test4 = TokenStream::from_tts(string_to_tts("foo(bar)".to_string()));
-
-        assert_eq!(test0.is_lit(), true);
-        assert_eq!(test1.is_lit(), true);
-        assert_eq!(test2.is_lit(), false);
-        assert_eq!(test3.is_lit(), false);
-        assert_eq!(test4.is_lit(), false);
-    }
-
-    #[test]
     fn test_is_ident() {
         let test0 = TokenStream::from_tts(string_to_tts("\"foo\"".to_string()));
         let test1 = TokenStream::from_tts(string_to_tts("5".to_string()));
@@ -991,62 +941,6 @@ mod tests {
     }
 
     #[test]
-    fn test_maybe_assignment() {
-        let test0_input = TokenStream::from_tts(string_to_tts("= bar::baz".to_string()));
-        let test1_input = TokenStream::from_tts(string_to_tts("= \"5\"".to_string()));
-        let test2_input = TokenStream::from_tts(string_to_tts("= 5".to_string()));
-        let test3_input = TokenStream::from_tts(string_to_tts("(foo = 10)".to_string()));
-        let test4_input = TokenStream::from_tts(string_to_tts("= (foo,bar,baz)".to_string()));
-        let test5_input = TokenStream::from_tts(string_to_tts("".to_string()));
-
-        let test0 = test0_input.maybe_assignment();
-        let test1 = test1_input.maybe_assignment();
-        let test2 = test2_input.maybe_assignment();
-        let test3 = test3_input.maybe_assignment();
-        let test4 = test4_input.maybe_assignment();
-        let test5 = test5_input.maybe_assignment();
-
-        let test0_expected = TokenStream::from_tts(vec![TokenTree::Token(sp(2, 5),
-                                                        token::Ident(str_to_ident("bar"))),
-                                       TokenTree::Token(sp(5, 7), token::ModSep),
-                                       TokenTree::Token(sp(7, 10),
-                                                        token::Ident(str_to_ident("baz")))]);
-        assert_eq!(test0, Some(&test0_expected[..]));
-
-        let test1_expected = TokenStream::from_tts(vec![TokenTree::Token(sp(2, 5),
-                                            token::Literal(Lit::Str_(token::intern("5")), None))]);
-        assert_eq!(test1, Some(&test1_expected[..]));
-
-        let test2_expected = TokenStream::from_tts(vec![TokenTree::Token( sp(2,3)
-                                       , token::Literal(
-                                           Lit::Integer(
-                                             token::intern(&(5.to_string()))),
-                                             None))]);
-        assert_eq!(test2, Some(&test2_expected[..]));
-
-        assert_eq!(test3, None);
-
-
-        let test4_tts = vec![TokenTree::Token(sp(3, 6), token::Ident(str_to_ident("foo"))),
-                             TokenTree::Token(sp(6, 7), token::Comma),
-                             TokenTree::Token(sp(7, 10), token::Ident(str_to_ident("bar"))),
-                             TokenTree::Token(sp(10, 11), token::Comma),
-                             TokenTree::Token(sp(11, 14), token::Ident(str_to_ident("baz")))];
-
-        let test4_expected = TokenStream::from_tts(vec![TokenTree::Delimited(sp(2, 15),
-                                                Rc::new(Delimited {
-                                                    delim: token::DelimToken::Paren,
-                                                    open_span: sp(2, 3),
-                                                    tts: test4_tts,
-                                                    close_span: sp(14, 15),
-                                                }))]);
-        assert_eq!(test4, Some(&test4_expected[..]));
-
-        assert_eq!(test5, None);
-
-    }
-
-    #[test]
     fn test_maybe_delimited() {
         let test0_input = TokenStream::from_tts(string_to_tts("foo(bar::baz)".to_string()));
         let test1_input = TokenStream::from_tts(string_to_tts("(bar::baz)".to_string()));
@@ -1070,7 +964,7 @@ mod tests {
                                        TokenTree::Token(sp(4, 6), token::ModSep),
                                        TokenTree::Token(sp(6, 9),
                                                         token::Ident(str_to_ident("baz")))]);
-        assert_eq!(test1, Some(&test1_expected[..]));
+        assert_eq!(test1, Some(test1_expected));
 
         let test2_expected = TokenStream::from_tts(vec![TokenTree::Token(sp(1, 4),
                                                         token::Ident(str_to_ident("foo"))),
@@ -1080,79 +974,13 @@ mod tests {
                                        TokenTree::Token(sp(8, 9), token::Comma),
                                        TokenTree::Token(sp(9, 12),
                                                         token::Ident(str_to_ident("baz")))]);
-        assert_eq!(test2, Some(&test2_expected[..]));
-
-        assert_eq!(test3, None);
-
-        assert_eq!(test4, None);
-
-        assert_eq!(test5, None);
-    }
-
-    #[test]
-    fn test_maybe_comma_list() {
-        let test0_input = TokenStream::from_tts(string_to_tts("foo(bar::baz)".to_string()));
-        let test1_input = TokenStream::from_tts(string_to_tts("(bar::baz)".to_string()));
-        let test2_input = TokenStream::from_tts(string_to_tts("(foo,bar,baz)".to_string()));
-        let test3_input = TokenStream::from_tts(string_to_tts("(foo::bar,bar,baz)".to_string()));
-        let test4_input = TokenStream::from_tts(string_to_tts("(foo,bar,baz)(zab,rab)"
-            .to_string()));
-        let test5_input = TokenStream::from_tts(string_to_tts("(foo,bar,baz)foo".to_string()));
-        let test6_input = TokenStream::from_tts(string_to_tts("".to_string()));
-        // The following is supported behavior!
-        let test7_input = TokenStream::from_tts(string_to_tts("(foo,bar,)".to_string()));
-
-        let test0 = test0_input.maybe_comma_list();
-        let test1 = test1_input.maybe_comma_list();
-        let test2 = test2_input.maybe_comma_list();
-        let test3 = test3_input.maybe_comma_list();
-        let test4 = test4_input.maybe_comma_list();
-        let test5 = test5_input.maybe_comma_list();
-        let test6 = test6_input.maybe_comma_list();
-        let test7 = test7_input.maybe_comma_list();
-
-        assert_eq!(test0, None);
-
-        let test1_stream = TokenStream::from_tts(vec![TokenTree::Token(sp(1, 4),
-                                                        token::Ident(str_to_ident("bar"))),
-                                       TokenTree::Token(sp(4, 6), token::ModSep),
-                                       TokenTree::Token(sp(6, 9),
-                                                        token::Ident(str_to_ident("baz")))]);
-
-        let test1_expected: Vec<&TokenSlice> = vec![&test1_stream[..]];
-        assert_eq!(test1, Some(test1_expected));
-
-        let test2_foo = TokenStream::from_tts(vec![TokenTree::Token(sp(1, 4),
-                                                        token::Ident(str_to_ident("foo")))]);
-        let test2_bar = TokenStream::from_tts(vec![TokenTree::Token(sp(5, 8),
-                                                        token::Ident(str_to_ident("bar")))]);
-        let test2_baz = TokenStream::from_tts(vec![TokenTree::Token(sp(9, 12),
-                                                        token::Ident(str_to_ident("baz")))]);
-        let test2_expected: Vec<&TokenSlice> = vec![&test2_foo[..], &test2_bar[..], &test2_baz[..]];
         assert_eq!(test2, Some(test2_expected));
 
-        let test3_path = TokenStream::from_tts(vec![TokenTree::Token(sp(1, 4),
-                                                        token::Ident(str_to_ident("foo"))),
-                                       TokenTree::Token(sp(4, 6), token::ModSep),
-                                       TokenTree::Token(sp(6, 9),
-                                                        token::Ident(str_to_ident("bar")))]);
-        let test3_bar = TokenStream::from_tts(vec![TokenTree::Token(sp(10, 13),
-                                                        token::Ident(str_to_ident("bar")))]);
-        let test3_baz = TokenStream::from_tts(vec![TokenTree::Token(sp(14, 17),
-                                                        token::Ident(str_to_ident("baz")))]);
-        let test3_expected: Vec<&TokenSlice> =
-            vec![&test3_path[..], &test3_bar[..], &test3_baz[..]];
-        assert_eq!(test3, Some(test3_expected));
+        assert_eq!(test3, None);
 
         assert_eq!(test4, None);
 
         assert_eq!(test5, None);
-
-        assert_eq!(test6, None);
-
-
-        let test7_expected: Vec<&TokenSlice> = vec![&test2_foo[..], &test2_bar[..]];
-        assert_eq!(test7, Some(test7_expected));
     }
 
     // pub fn maybe_ident(&self) -> Option<ast::Ident>
@@ -1171,86 +999,10 @@ mod tests {
         assert_eq!(test4, None);
     }
 
-    // pub fn maybe_lit(&self) -> Option<token::Lit>
     #[test]
-    fn test_maybe_lit() {
-        let test0 = TokenStream::from_tts(string_to_tts("\"foo\"".to_string())).maybe_lit();
-        let test1 = TokenStream::from_tts(string_to_tts("5".to_string())).maybe_lit();
-        let test2 = TokenStream::from_tts(string_to_tts("foo".to_string())).maybe_lit();
-        let test3 = TokenStream::from_tts(string_to_tts("foo::bar".to_string())).maybe_lit();
-        let test4 = TokenStream::from_tts(string_to_tts("foo(bar)".to_string())).maybe_lit();
-
-        assert_eq!(test0, Some(Lit::Str_(token::intern("foo"))));
-        assert_eq!(test1, Some(Lit::Integer(token::intern(&(5.to_string())))));
-        assert_eq!(test2, None);
-        assert_eq!(test3, None);
-        assert_eq!(test4, None);
-    }
-
-    #[test]
-    fn test_maybe_path_prefix() {
-        let test0_input = TokenStream::from_tts(string_to_tts("foo(bar::baz)".to_string()));
-        let test1_input = TokenStream::from_tts(string_to_tts("(bar::baz)".to_string()));
-        let test2_input = TokenStream::from_tts(string_to_tts("(foo,bar,baz)".to_string()));
-        let test3_input = TokenStream::from_tts(string_to_tts("foo::bar(bar,baz)".to_string()));
-
-        let test0 = test0_input.maybe_path_prefix();
-        let test1 = test1_input.maybe_path_prefix();
-        let test2 = test2_input.maybe_path_prefix();
-        let test3 = test3_input.maybe_path_prefix();
-
-        let test0_tts = vec![TokenTree::Token(sp(4, 7), token::Ident(str_to_ident("bar"))),
-                             TokenTree::Token(sp(7, 9), token::ModSep),
-                             TokenTree::Token(sp(9, 12), token::Ident(str_to_ident("baz")))];
-
-        let test0_stream = TokenStream::from_tts(vec![TokenTree::Delimited(sp(3, 13),
-                                                               Rc::new(Delimited {
-                                                                   delim: token::DelimToken::Paren,
-                                                                   open_span: sp(3, 4),
-                                                                   tts: test0_tts,
-                                                                   close_span: sp(12, 13),
-                                                               }))]);
-
-        let test0_expected = Some((ast::Path::from_ident(sp(0, 3), str_to_ident("foo")),
-                                   &test0_stream[..]));
-        assert_eq!(test0, test0_expected);
-
-        assert_eq!(test1, None);
-        assert_eq!(test2, None);
-
-        let test3_path = ast::Path {
-            span: sp(0, 8),
-            global: false,
-            segments: vec![ast::PathSegment {
-                               identifier: str_to_ident("foo"),
-                               parameters: ast::PathParameters::none(),
-                           },
-                           ast::PathSegment {
-                               identifier: str_to_ident("bar"),
-                               parameters: ast::PathParameters::none(),
-                           }],
-        };
-
-        let test3_tts = vec![TokenTree::Token(sp(9, 12), token::Ident(str_to_ident("bar"))),
-                             TokenTree::Token(sp(12, 13), token::Comma),
-                             TokenTree::Token(sp(13, 16), token::Ident(str_to_ident("baz")))];
-
-        let test3_stream = TokenStream::from_tts(vec![TokenTree::Delimited(sp(8, 17),
-                                                               Rc::new(Delimited {
-                                                                   delim: token::DelimToken::Paren,
-                                                                   open_span: sp(8, 9),
-                                                                   tts: test3_tts,
-                                                                   close_span: sp(16, 17),
-                                                               }))]);
-        let test3_expected = Some((test3_path, &test3_stream[..]));
-        assert_eq!(test3, test3_expected);
-    }
-
-    #[test]
-    fn test_as_paren_delimited_stream() {
-        let test0 = TokenStream::as_paren_delimited_stream(string_to_tts("foo,bar,".to_string()));
-        let test1 = TokenStream::as_paren_delimited_stream(string_to_tts("baz(foo,bar)"
-            .to_string()));
+    fn test_as_delimited_stream() {
+        let test0 = as_paren_delimited_stream(string_to_tts("foo,bar,".to_string()));
+        let test1 = as_paren_delimited_stream(string_to_tts("baz(foo,bar)".to_string()));
 
         let test0_tts = vec![TokenTree::Token(sp(0, 3), token::Ident(str_to_ident("foo"))),
                              TokenTree::Token(sp(3, 4), token::Comma),
@@ -1290,5 +1042,4 @@ mod tests {
 
         assert_eq!(test1, test1_stream);
     }
-
 }