Merge branch 'master' into redox

13 files changed, 338 insertions, 497 deletions

diff --git a/src/libsyntax/Cargo.toml b/src/libsyntax/Cargo.toml
index 8b61e1b0d3a..0b38f5450b6 100644
--- a/src/libsyntax/Cargo.toml
+++ b/src/libsyntax/Cargo.toml
@@ -14,3 +14,4 @@ log = { path = "../liblog" }
 rustc_bitflags = { path = "../librustc_bitflags" }
 syntax_pos = { path = "../libsyntax_pos" }
 rustc_errors = { path = "../librustc_errors" }
+rustc_data_structures = { path = "../librustc_data_structures" }
diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index 57a936bf9b0..2977e340a3c 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -789,9 +789,6 @@ fn find_stability_generic<'a, I>(diagnostic: &Handler,
     // Merge the deprecation info into the stability info
     if let Some(rustc_depr) = rustc_depr {
         if let Some(ref mut stab) = stab {
-            if let Unstable {reason: ref mut reason @ None, ..} = stab.level {
-                *reason = Some(rustc_depr.reason.clone())
-            }
             stab.rustc_depr = Some(rustc_depr);
         } else {
             span_err!(diagnostic, item_sp, E0549,
diff --git a/src/libsyntax/config.rs b/src/libsyntax/config.rs
index 946257a16d5..02429f02738 100644
--- a/src/libsyntax/config.rs
+++ b/src/libsyntax/config.rs
@@ -277,7 +277,7 @@ impl<'a> fold::Folder for StripUnconfigured<'a> {
     fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
         match self.configure_stmt(stmt) {
             Some(stmt) => fold::noop_fold_stmt(stmt, self),
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         }
     }
 
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 63eee7df9e8..7f66b060052 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -440,7 +440,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
@@ -448,7 +448,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
@@ -456,7 +456,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
@@ -524,6 +524,7 @@ pub trait Resolver {
     fn add_ext(&mut self, ident: ast::Ident, ext: Rc<SyntaxExtension>);
     fn add_expansions_at_stmt(&mut self, id: ast::NodeId, macros: Vec<Mark>);
 
+    fn resolve_imports(&mut self);
     fn find_attr_invoc(&mut self, attrs: &mut Vec<Attribute>) -> Option<Attribute>;
     fn resolve_macro(&mut self, scope: Mark, path: &ast::Path, force: bool)
                      -> Result<Rc<SyntaxExtension>, Determinacy>;
@@ -547,6 +548,7 @@ impl Resolver for DummyResolver {
     fn add_ext(&mut self, _ident: ast::Ident, _ext: Rc<SyntaxExtension>) {}
     fn add_expansions_at_stmt(&mut self, _id: ast::NodeId, _macros: Vec<Mark>) {}
 
+    fn resolve_imports(&mut self) {}
     fn find_attr_invoc(&mut self, _attrs: &mut Vec<Attribute>) -> Option<Attribute> { None }
     fn resolve_macro(&mut self, _scope: Mark, _path: &ast::Path, _force: bool)
                      -> Result<Rc<SyntaxExtension>, Determinacy> {
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index e3b23e239f9..8e0c3ce8448 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -89,7 +89,7 @@ macro_rules! expansions {
                     Expansion::OptExpr(Some(ref expr)) => visitor.visit_expr(expr),
                     Expansion::OptExpr(None) => {}
                     $($( Expansion::$kind(ref ast) => visitor.$visit(ast), )*)*
-                    $($( Expansion::$kind(ref ast) => for ast in ast.as_slice() {
+                    $($( Expansion::$kind(ref ast) => for ast in &ast[..] {
                         visitor.$visit_elt(ast);
                     }, )*)*
                 }
@@ -222,6 +222,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
         self.cx.current_expansion.depth = 0;
 
         let (expansion, mut invocations) = self.collect_invocations(expansion);
+        self.resolve_imports();
         invocations.reverse();
 
         let mut expansions = Vec::new();
@@ -230,9 +231,9 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
         loop {
             let invoc = if let Some(invoc) = invocations.pop() {
                 invoc
-            } else if undetermined_invocations.is_empty() {
-                break
             } else {
+                self.resolve_imports();
+                if undetermined_invocations.is_empty() { break }
                 invocations = mem::replace(&mut undetermined_invocations, Vec::new());
                 force = !mem::replace(&mut progress, false);
                 continue
@@ -292,6 +293,14 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
         expansion.fold_with(&mut placeholder_expander)
     }
 
+    fn resolve_imports(&mut self) {
+        if self.monotonic {
+            let err_count = self.cx.parse_sess.span_diagnostic.err_count();
+            self.cx.resolver.resolve_imports();
+            self.cx.resolve_err_count += self.cx.parse_sess.span_diagnostic.err_count() - err_count;
+        }
+    }
+
     fn collect_invocations(&mut self, expansion: Expansion) -> (Expansion, Vec<Invocation>) {
         let result = {
             let mut collector = InvocationCollector {
@@ -511,29 +520,31 @@ impl<'a> Parser<'a> {
                            -> PResult<'a, Expansion> {
         Ok(match kind {
             ExpansionKind::Items => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while let Some(item) = self.parse_item()? {
                     items.push(item);
                 }
                 Expansion::Items(items)
             }
             ExpansionKind::TraitItems => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while self.token != token::Eof {
                     items.push(self.parse_trait_item()?);
                 }
                 Expansion::TraitItems(items)
             }
             ExpansionKind::ImplItems => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while self.token != token::Eof {
                     items.push(self.parse_impl_item()?);
                 }
                 Expansion::ImplItems(items)
             }
             ExpansionKind::Stmts => {
-                let mut stmts = SmallVector::zero();
-                while self.token != token::Eof {
+                let mut stmts = SmallVector::new();
+                while self.token != token::Eof &&
+                      // won't make progress on a `}`
+                      self.token != token::CloseDelim(token::Brace) {
                     if let Some(stmt) = self.parse_full_stmt(macro_legacy_warnings)? {
                         stmts.push(stmt);
                     }
@@ -571,7 +582,7 @@ macro_rules! fully_configure {
     ($this:ident, $node:ident, $noop_fold:ident) => {
         match $noop_fold($node, &mut $this.cfg).pop() {
             Some(node) => node,
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         }
     }
 }
@@ -687,7 +698,7 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
     fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
         let stmt = match self.cfg.configure_stmt(stmt) {
             Some(stmt) => stmt,
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         };
 
         let (mac, style, attrs) = if let StmtKind::Mac(mac) = stmt.node {
diff --git a/src/libsyntax/ext/source_util.rs b/src/libsyntax/ext/source_util.rs
index ec48cae3f76..bda84cdaf39 100644
--- a/src/libsyntax/ext/source_util.rs
+++ b/src/libsyntax/ext/source_util.rs
@@ -104,7 +104,7 @@ pub fn expand_include<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[tokenstream::T
         }
         fn make_items(mut self: Box<ExpandResult<'a>>)
                       -> Option<SmallVector<P<ast::Item>>> {
-            let mut ret = SmallVector::zero();
+            let mut ret = SmallVector::new();
             while self.p.token != token::Eof {
                 match panictry!(self.p.parse_item()) {
                     Some(item) => ret.push(item),
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index 1066646aa8e..39ffab4dc17 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -130,7 +130,7 @@ struct MatcherTtFrame {
 }
 
 #[derive(Clone)]
-pub struct MatcherPos {
+struct MatcherPos {
     stack: Vec<MatcherTtFrame>,
     top_elts: TokenTreeOrTokenTreeVec,
     sep: Option<Token>,
@@ -143,6 +143,8 @@ pub struct MatcherPos {
     sp_lo: BytePos,
 }
 
+pub type NamedParseResult = ParseResult<HashMap<Ident, Rc<NamedMatch>>>;
+
 pub fn count_names(ms: &[TokenTree]) -> usize {
     ms.iter().fold(0, |count, elt| {
         count + match *elt {
@@ -160,14 +162,13 @@ pub fn count_names(ms: &[TokenTree]) -> usize {
     })
 }
 
-pub fn initial_matcher_pos(ms: Vec<TokenTree>, sep: Option<Token>, lo: BytePos)
-                           -> Box<MatcherPos> {
+fn initial_matcher_pos(ms: Vec<TokenTree>, lo: BytePos) -> Box<MatcherPos> {
     let match_idx_hi = count_names(&ms[..]);
-    let matches: Vec<_> = (0..match_idx_hi).map(|_| Vec::new()).collect();
+    let matches = create_matches(match_idx_hi);
     Box::new(MatcherPos {
         stack: vec![],
         top_elts: TtSeq(ms),
-        sep: sep,
+        sep: None,
         idx: 0,
         up: None,
         matches: matches,
@@ -200,27 +201,25 @@ pub enum NamedMatch {
     MatchedNonterminal(Rc<Nonterminal>)
 }
 
-pub fn nameize(p_s: &ParseSess, ms: &[TokenTree], res: &[Rc<NamedMatch>])
-            -> ParseResult<HashMap<Ident, Rc<NamedMatch>>> {
-    fn n_rec(p_s: &ParseSess, m: &TokenTree, res: &[Rc<NamedMatch>],
-             ret_val: &mut HashMap<Ident, Rc<NamedMatch>>, idx: &mut usize)
+fn nameize<I: Iterator<Item=Rc<NamedMatch>>>(ms: &[TokenTree], mut res: I) -> NamedParseResult {
+    fn n_rec<I: Iterator<Item=Rc<NamedMatch>>>(m: &TokenTree, mut res: &mut I,
+             ret_val: &mut HashMap<Ident, Rc<NamedMatch>>)
              -> Result<(), (syntax_pos::Span, String)> {
         match *m {
             TokenTree::Sequence(_, ref seq) => {
                 for next_m in &seq.tts {
-                    n_rec(p_s, next_m, res, ret_val, idx)?
+                    n_rec(next_m, res.by_ref(), ret_val)?
                 }
             }
             TokenTree::Delimited(_, ref delim) => {
                 for next_m in &delim.tts {
-                    n_rec(p_s, next_m, res, ret_val, idx)?;
+                    n_rec(next_m, res.by_ref(), ret_val)?;
                 }
             }
             TokenTree::Token(sp, MatchNt(bind_name, _)) => {
                 match ret_val.entry(bind_name) {
                     Vacant(spot) => {
-                        spot.insert(res[*idx].clone());
-                        *idx += 1;
+                        spot.insert(res.next().unwrap());
                     }
                     Occupied(..) => {
                         return Err((sp, format!("duplicated bind name: {}", bind_name)))
@@ -237,9 +236,8 @@ pub fn nameize(p_s: &ParseSess, ms: &[TokenTree], res: &[Rc<NamedMatch>])
     }
 
     let mut ret_val = HashMap::new();
-    let mut idx = 0;
     for m in ms {
-        match n_rec(p_s, m, res, &mut ret_val, &mut idx) {
+        match n_rec(m, res.by_ref(), &mut ret_val) {
             Ok(_) => {},
             Err((sp, msg)) => return Error(sp, msg),
         }
@@ -265,11 +263,8 @@ pub fn parse_failure_msg(tok: Token) -> String {
     }
 }
 
-pub type NamedParseResult = ParseResult<HashMap<Ident, Rc<NamedMatch>>>;
-
-/// Perform a token equality check, ignoring syntax context (that is, an
-/// unhygienic comparison)
-pub fn token_name_eq(t1 : &Token, t2 : &Token) -> bool {
+/// Perform a token equality check, ignoring syntax context (that is, an unhygienic comparison)
+fn token_name_eq(t1 : &Token, t2 : &Token) -> bool {
     match (t1,t2) {
         (&token::Ident(id1),&token::Ident(id2))
         | (&token::Lifetime(id1),&token::Lifetime(id2)) =>
@@ -278,234 +273,228 @@ pub fn token_name_eq(t1 : &Token, t2 : &Token) -> bool {
     }
 }
 
-pub fn parse(sess: &ParseSess, rdr: TtReader, ms: &[TokenTree]) -> NamedParseResult {
-    let mut parser = Parser::new_with_doc_flag(sess, Box::new(rdr), true);
-    let mut cur_eis = SmallVector::one(initial_matcher_pos(ms.to_owned(), None, parser.span.lo));
+fn create_matches(len: usize) -> Vec<Vec<Rc<NamedMatch>>> {
+    (0..len).into_iter().map(|_| Vec::new()).collect()
+}
 
-    loop {
-        let mut bb_eis = Vec::new(); // black-box parsed by parser.rs
-        let mut next_eis = Vec::new(); // or proceed normally
-        let mut eof_eis = Vec::new();
-
-        let (sp, tok) = (parser.span, parser.token.clone());
-
-        /* we append new items to this while we go */
-        loop {
-            let mut ei = match cur_eis.pop() {
-                None => break, /* for each Earley Item */
-                Some(ei) => ei,
-            };
-
-            // When unzipped trees end, remove them
-            while ei.idx >= ei.top_elts.len() {
-                match ei.stack.pop() {
-                    Some(MatcherTtFrame { elts, idx }) => {
-                        ei.top_elts = elts;
-                        ei.idx = idx + 1;
-                    }
-                    None => break
+fn inner_parse_loop(cur_eis: &mut SmallVector<Box<MatcherPos>>,
+                    next_eis: &mut Vec<Box<MatcherPos>>,
+                    eof_eis: &mut SmallVector<Box<MatcherPos>>,
+                    bb_eis: &mut SmallVector<Box<MatcherPos>>,
+                    token: &Token, span: &syntax_pos::Span) -> ParseResult<()> {
+    while let Some(mut ei) = cur_eis.pop() {
+        // When unzipped trees end, remove them
+        while ei.idx >= ei.top_elts.len() {
+            match ei.stack.pop() {
+                Some(MatcherTtFrame { elts, idx }) => {
+                    ei.top_elts = elts;
+                    ei.idx = idx + 1;
                 }
+                None => break
             }
+        }
 
-            let idx = ei.idx;
-            let len = ei.top_elts.len();
-
-            /* at end of sequence */
-            if idx >= len {
-                // can't move out of `match`es, so:
-                if ei.up.is_some() {
-                    // hack: a matcher sequence is repeating iff it has a
-                    // parent (the top level is just a container)
-
-
-                    // disregard separator, try to go up
-                    // (remove this condition to make trailing seps ok)
-                    if idx == len {
-                        // pop from the matcher position
-
-                        let mut new_pos = ei.up.clone().unwrap();
-
-                        // update matches (the MBE "parse tree") by appending
-                        // each tree as a subtree.
-
-                        // I bet this is a perf problem: we're preemptively
-                        // doing a lot of array work that will get thrown away
-                        // most of the time.
-
-                        // Only touch the binders we have actually bound
-                        for idx in ei.match_lo..ei.match_hi {
-                            let sub = (ei.matches[idx]).clone();
-                            (&mut new_pos.matches[idx])
-                                   .push(Rc::new(MatchedSeq(sub, mk_sp(ei.sp_lo,
-                                                                       sp.hi))));
-                        }
-
-                        new_pos.match_cur = ei.match_hi;
-                        new_pos.idx += 1;
-                        cur_eis.push(new_pos);
+        let idx = ei.idx;
+        let len = ei.top_elts.len();
+
+        // at end of sequence
+        if idx >= len {
+            // We are repeating iff there is a parent
+            if ei.up.is_some() {
+                // Disregarding the separator, add the "up" case to the tokens that should be
+                // examined.
+                // (remove this condition to make trailing seps ok)
+                if idx == len {
+                    let mut new_pos = ei.up.clone().unwrap();
+
+                    // update matches (the MBE "parse tree") by appending
+                    // each tree as a subtree.
+
+                    // I bet this is a perf problem: we're preemptively
+                    // doing a lot of array work that will get thrown away
+                    // most of the time.
+
+                    // Only touch the binders we have actually bound
+                    for idx in ei.match_lo..ei.match_hi {
+                        let sub = ei.matches[idx].clone();
+                        new_pos.matches[idx]
+                            .push(Rc::new(MatchedSeq(sub, mk_sp(ei.sp_lo,
+                                                                span.hi))));
                     }
 
-                    // can we go around again?
-
-                    // the *_t vars are workarounds for the lack of unary move
-                    match ei.sep {
-                        Some(ref t) if idx == len => { // we need a separator
-                            // i'm conflicted about whether this should be hygienic....
-                            // though in this case, if the separators are never legal
-                            // idents, it shouldn't matter.
-                            if token_name_eq(&tok, t) { //pass the separator
-                                let mut ei_t = ei.clone();
-                                // ei_t.match_cur = ei_t.match_lo;
-                                ei_t.idx += 1;
-                                next_eis.push(ei_t);
-                            }
-                        }
-                        _ => { // we don't need a separator
-                            let mut ei_t = ei;
-                            ei_t.match_cur = ei_t.match_lo;
-                            ei_t.idx = 0;
-                            cur_eis.push(ei_t);
-                        }
-                    }
-                } else {
-                    eof_eis.push(ei);
+                    new_pos.match_cur = ei.match_hi;
+                    new_pos.idx += 1;
+                    cur_eis.push(new_pos);
                 }
-            } else {
-                match ei.top_elts.get_tt(idx) {
-                    /* need to descend into sequence */
-                    TokenTree::Sequence(sp, seq) => {
-                        if seq.op == tokenstream::KleeneOp::ZeroOrMore {
-                            let mut new_ei = ei.clone();
-                            new_ei.match_cur += seq.num_captures;
-                            new_ei.idx += 1;
-                            //we specifically matched zero repeats.
-                            for idx in ei.match_cur..ei.match_cur + seq.num_captures {
-                                (&mut new_ei.matches[idx]).push(Rc::new(MatchedSeq(vec![], sp)));
-                            }
-
-                            cur_eis.push(new_ei);
-                        }
 
-                        let matches: Vec<_> = (0..ei.matches.len())
-                            .map(|_| Vec::new()).collect();
-                        let ei_t = ei;
-                        cur_eis.push(Box::new(MatcherPos {
-                            stack: vec![],
-                            sep: seq.separator.clone(),
-                            idx: 0,
-                            matches: matches,
-                            match_lo: ei_t.match_cur,
-                            match_cur: ei_t.match_cur,
-                            match_hi: ei_t.match_cur + seq.num_captures,
-                            up: Some(ei_t),
-                            sp_lo: sp.lo,
-                            top_elts: Tt(TokenTree::Sequence(sp, seq)),
-                        }));
+                // Check if we need a separator
+                if idx == len && ei.sep.is_some() {
+                    // We have a separator, and it is the current token.
+                    if ei.sep.as_ref().map(|ref sep| token_name_eq(&token, sep)).unwrap_or(false) {
+                        ei.idx += 1;
+                        next_eis.push(ei);
                     }
-                    TokenTree::Token(_, MatchNt(..)) => {
-                        // Built-in nonterminals never start with these tokens,
-                        // so we can eliminate them from consideration.
-                        match tok {
-                            token::CloseDelim(_) => {},
-                            _ => bb_eis.push(ei),
+                } else { // we don't need a separator
+                    ei.match_cur = ei.match_lo;
+                    ei.idx = 0;
+                    cur_eis.push(ei);
+                }
+            } else {
+                // We aren't repeating, so we must be potentially at the end of the input.
+                eof_eis.push(ei);
+            }
+        } else {
+            match ei.top_elts.get_tt(idx) {
+                /* need to descend into sequence */
+                TokenTree::Sequence(sp, seq) => {
+                    if seq.op == tokenstream::KleeneOp::ZeroOrMore {
+                        // Examine the case where there are 0 matches of this sequence
+                        let mut new_ei = ei.clone();
+                        new_ei.match_cur += seq.num_captures;
+                        new_ei.idx += 1;
+                        for idx in ei.match_cur..ei.match_cur + seq.num_captures {
+                            new_ei.matches[idx].push(Rc::new(MatchedSeq(vec![], sp)));
                         }
+                        cur_eis.push(new_ei);
                     }
-                    TokenTree::Token(sp, SubstNt(..)) => {
-                        return Error(sp, "missing fragment specifier".to_string())
-                    }
-                    seq @ TokenTree::Delimited(..) | seq @ TokenTree::Token(_, DocComment(..)) => {
-                        let lower_elts = mem::replace(&mut ei.top_elts, Tt(seq));
-                        let idx = ei.idx;
-                        ei.stack.push(MatcherTtFrame {
-                            elts: lower_elts,
-                            idx: idx,
-                        });
-                        ei.idx = 0;
-                        cur_eis.push(ei);
+
+                    // Examine the case where there is at least one match of this sequence
+                    let matches = create_matches(ei.matches.len());
+                    cur_eis.push(Box::new(MatcherPos {
+                        stack: vec![],
+                        sep: seq.separator.clone(),
+                        idx: 0,
+                        matches: matches,
+                        match_lo: ei.match_cur,
+                        match_cur: ei.match_cur,
+                        match_hi: ei.match_cur + seq.num_captures,
+                        up: Some(ei),
+                        sp_lo: sp.lo,
+                        top_elts: Tt(TokenTree::Sequence(sp, seq)),
+                    }));
+                }
+                TokenTree::Token(_, MatchNt(..)) => {
+                    // Built-in nonterminals never start with these tokens,
+                    // so we can eliminate them from consideration.
+                    match *token {
+                        token::CloseDelim(_) => {},
+                        _ => bb_eis.push(ei),
                     }
-                    TokenTree::Token(_, ref t) => {
-                        if token_name_eq(t,&tok) {
-                            let mut ei_t = ei.clone();
-                            ei_t.idx += 1;
-                            next_eis.push(ei_t);
-                        }
+                }
+                TokenTree::Token(sp, SubstNt(..)) => {
+                    return Error(sp, "missing fragment specifier".to_string())
+                }
+                seq @ TokenTree::Delimited(..) | seq @ TokenTree::Token(_, DocComment(..)) => {
+                    let lower_elts = mem::replace(&mut ei.top_elts, Tt(seq));
+                    let idx = ei.idx;
+                    ei.stack.push(MatcherTtFrame {
+                        elts: lower_elts,
+                        idx: idx,
+                    });
+                    ei.idx = 0;
+                    cur_eis.push(ei);
+                }
+                TokenTree::Token(_, ref t) => {
+                    if token_name_eq(t, &token) {
+                        ei.idx += 1;
+                        next_eis.push(ei);
                     }
                 }
             }
         }
+    }
+
+    Success(())
+}
+
+pub fn parse(sess: &ParseSess, rdr: TtReader, ms: &[TokenTree]) -> NamedParseResult {
+    let mut parser = Parser::new_with_doc_flag(sess, Box::new(rdr), true);
+    let mut cur_eis = SmallVector::one(initial_matcher_pos(ms.to_owned(), parser.span.lo));
+    let mut next_eis = Vec::new(); // or proceed normally
+
+    loop {
+        let mut bb_eis = SmallVector::new(); // black-box parsed by parser.rs
+        let mut eof_eis = SmallVector::new();
+        assert!(next_eis.is_empty());
+
+        match inner_parse_loop(&mut cur_eis, &mut next_eis, &mut eof_eis, &mut bb_eis,
+                               &parser.token, &parser.span) {
+            Success(_) => {},
+            Failure(sp, tok) => return Failure(sp, tok),
+            Error(sp, msg) => return Error(sp, msg),
+        }
+
+        // inner parse loop handled all cur_eis, so it's empty
+        assert!(cur_eis.is_empty());
 
         /* error messages here could be improved with links to orig. rules */
-        if token_name_eq(&tok, &token::Eof) {
+        if token_name_eq(&parser.token, &token::Eof) {
             if eof_eis.len() == 1 {
-                let mut v = Vec::new();
-                for dv in &mut (&mut eof_eis[0]).matches {
-                    v.push(dv.pop().unwrap());
-                }
-                return nameize(sess, ms, &v[..]);
+                return nameize(ms, eof_eis[0].matches.iter_mut().map(|mut dv| dv.pop().unwrap()));
             } else if eof_eis.len() > 1 {
-                return Error(sp, "ambiguity: multiple successful parses".to_string());
+                return Error(parser.span, "ambiguity: multiple successful parses".to_string());
             } else {
-                return Failure(sp, token::Eof);
+                return Failure(parser.span, token::Eof);
             }
-        } else {
-            if (!bb_eis.is_empty() && !next_eis.is_empty())
-                || bb_eis.len() > 1 {
-                let nts = bb_eis.iter().map(|ei| match ei.top_elts.get_tt(ei.idx) {
-                    TokenTree::Token(_, MatchNt(bind, name)) => {
-                        format!("{} ('{}')", name, bind)
-                    }
-                    _ => panic!()
-                }).collect::<Vec<String>>().join(" or ");
-
-                return Error(sp, format!(
-                    "local ambiguity: multiple parsing options: {}",
-                    match next_eis.len() {
-                        0 => format!("built-in NTs {}.", nts),
-                        1 => format!("built-in NTs {} or 1 other option.", nts),
-                        n => format!("built-in NTs {} or {} other options.", nts, n),
-                    }
-                ))
-            } else if bb_eis.is_empty() && next_eis.is_empty() {
-                return Failure(sp, tok);
-            } else if !next_eis.is_empty() {
-                /* Now process the next token */
-                while !next_eis.is_empty() {
-                    cur_eis.push(next_eis.pop().unwrap());
+        } else if (!bb_eis.is_empty() && !next_eis.is_empty()) || bb_eis.len() > 1 {
+            let nts = bb_eis.iter().map(|ei| match ei.top_elts.get_tt(ei.idx) {
+                TokenTree::Token(_, MatchNt(bind, name)) => {
+                    format!("{} ('{}')", name, bind)
                 }
-                parser.bump();
-            } else /* bb_eis.len() == 1 */ {
-                let mut ei = bb_eis.pop().unwrap();
-                if let TokenTree::Token(span, MatchNt(_, ident)) = ei.top_elts.get_tt(ei.idx) {
-                    let match_cur = ei.match_cur;
-                    (&mut ei.matches[match_cur]).push(Rc::new(MatchedNonterminal(
-                        Rc::new(parse_nt(&mut parser, span, &ident.name.as_str())))));
-                    ei.idx += 1;
-                    ei.match_cur += 1;
-                } else {
-                    unreachable!()
+                _ => panic!()
+            }).collect::<Vec<String>>().join(" or ");
+
+            return Error(parser.span, format!(
+                "local ambiguity: multiple parsing options: {}",
+                match next_eis.len() {
+                    0 => format!("built-in NTs {}.", nts),
+                    1 => format!("built-in NTs {} or 1 other option.", nts),
+                    n => format!("built-in NTs {} or {} other options.", nts, n),
                 }
-                cur_eis.push(ei);
+            ));
+        } else if bb_eis.is_empty() && next_eis.is_empty() {
+            return Failure(parser.span, parser.token);
+        } else if !next_eis.is_empty() {
+            /* Now process the next token */
+            cur_eis.extend(next_eis.drain(..));
+            parser.bump();
+        } else /* bb_eis.len() == 1 */ {
+            let mut ei = bb_eis.pop().unwrap();
+            if let TokenTree::Token(span, MatchNt(_, ident)) = ei.top_elts.get_tt(ei.idx) {
+                let match_cur = ei.match_cur;
+                ei.matches[match_cur].push(Rc::new(MatchedNonterminal(
+                            Rc::new(parse_nt(&mut parser, span, &ident.name.as_str())))));
+                ei.idx += 1;
+                ei.match_cur += 1;
+            } else {
+                unreachable!()
             }
+            cur_eis.push(ei);
         }
 
         assert!(!cur_eis.is_empty());
     }
 }
 
-pub fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: &str) -> Nonterminal {
+fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: &str) -> Nonterminal {
     match name {
         "tt" => {
             p.quote_depth += 1; //but in theory, non-quoted tts might be useful
             let mut tt = panictry!(p.parse_token_tree());
             p.quote_depth -= 1;
-            loop {
-                let nt = match tt {
-                    TokenTree::Token(_, token::Interpolated(ref nt)) => nt.clone(),
-                    _ => break,
-                };
-                match *nt {
-                    token::NtTT(ref sub_tt) => tt = sub_tt.clone(),
-                    _ => break,
+            while let TokenTree::Token(sp, token::Interpolated(nt)) = tt {
+                if let token::NtTT(..) = *nt {
+                    match Rc::try_unwrap(nt) {
+                        Ok(token::NtTT(sub_tt)) => tt = sub_tt,
+                        Ok(_) => unreachable!(),
+                        Err(nt_rc) => match *nt_rc {
+                            token::NtTT(ref sub_tt) => tt = sub_tt.clone(),
+                            _ => unreachable!(),
+                        },
+                    }
+                } else {
+                    tt = TokenTree::Token(sp, token::Interpolated(nt.clone()));
+                    break
                 }
             }
             return token::NtTT(tt);
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 9116b392f17..ea66fdc31cf 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -311,6 +311,11 @@ declare_features! (
 
     // Allows using `Self` and associated types in struct expressions and patterns.
     (active, more_struct_aliases, "1.14.0", Some(37544)),
+
+    // Allows #[link(..., cfg(..))]
+    (active, link_cfg, "1.14.0", Some(37406)),
+
+    (active, use_extern_macros, "1.15.0", Some(35896)),
 );
 
 declare_features! (
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index feed400897c..34280812421 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -45,6 +45,7 @@ extern crate libc;
 extern crate rustc_unicode;
 pub extern crate rustc_errors as errors;
 extern crate syntax_pos;
+extern crate rustc_data_structures;
 
 extern crate serialize as rustc_serialize; // used by deriving
 
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 7d15334ff9f..2e38ca82d5d 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -1902,12 +1902,12 @@ impl<'a> Parser<'a> {
                     if let Some(recv) = followed_by_ty_params {
                         assert!(recv.is_empty());
                         *recv = attrs;
-                    } else {
+                        debug!("parse_lifetime_defs ret {:?}", res);
+                        return Ok(res);
+                    } else if !attrs.is_empty() {
                         let msg = "trailing attribute after lifetime parameters";
                         return Err(self.fatal(msg));
                     }
-                    debug!("parse_lifetime_defs ret {:?}", res);
-                    return Ok(res);
                 }
             }
 
@@ -4409,7 +4409,7 @@ impl<'a> Parser<'a> {
                     let bounded_lifetime =
                         self.parse_lifetime()?;
 
-                    self.eat(&token::Colon);
+                    self.expect(&token::Colon)?;
 
                     let bounds =
                         self.parse_lifetimes(token::BinOp(token::Plus))?;
diff --git a/src/libsyntax/test.rs b/src/libsyntax/test.rs
index 618878c1f79..59a7e75d125 100644
--- a/src/libsyntax/test.rs
+++ b/src/libsyntax/test.rs
@@ -132,7 +132,7 @@ impl<'a> fold::Folder for TestHarnessGenerator<'a> {
                         path: self.cx.path.clone(),
                         bench: is_bench_fn(&self.cx, &i),
                         ignore: is_ignored(&i),
-                        should_panic: should_panic(&i)
+                        should_panic: should_panic(&i, &self.cx)
                     };
                     self.cx.testfns.push(test);
                     self.tests.push(i.ident);
@@ -395,14 +395,44 @@ fn is_ignored(i: &ast::Item) -> bool {
     i.attrs.iter().any(|attr| attr.check_name("ignore"))
 }
 
-fn should_panic(i: &ast::Item) -> ShouldPanic {
+fn should_panic(i: &ast::Item, cx: &TestCtxt) -> ShouldPanic {
     match i.attrs.iter().find(|attr| attr.check_name("should_panic")) {
         Some(attr) => {
-            let msg = attr.meta_item_list()
-                .and_then(|list| list.iter().find(|mi| mi.check_name("expected")))
-                .and_then(|li| li.meta_item())
-                .and_then(|mi| mi.value_str());
-            ShouldPanic::Yes(msg)
+            let sd = cx.span_diagnostic;
+            if attr.is_value_str() {
+                sd.struct_span_warn(
+                    attr.span(),
+                    "attribute must be of the form: \
+                     `#[should_panic]` or \
+                     `#[should_panic(expected = \"error message\")]`"
+                ).note("Errors in this attribute were erroneously allowed \
+                        and will become a hard error in a future release.")
+                .emit();
+                return ShouldPanic::Yes(None);
+            }
+            match attr.meta_item_list() {
+                // Handle #[should_panic]
+                None => ShouldPanic::Yes(None),
+                // Handle #[should_panic(expected = "foo")]
+                Some(list) => {
+                    let msg = list.iter()
+                        .find(|mi| mi.check_name("expected"))
+                        .and_then(|mi| mi.meta_item())
+                        .and_then(|mi| mi.value_str());
+                    if list.len() != 1 || msg.is_none() {
+                        sd.struct_span_warn(
+                            attr.span(),
+                            "argument must be of the form: \
+                             `expected = \"error message\"`"
+                        ).note("Errors in this attribute were erroneously \
+                                allowed and will become a hard error in a \
+                                future release.").emit();
+                        ShouldPanic::Yes(None)
+                    } else {
+                        ShouldPanic::Yes(msg)
+                    }
+                },
+            }
         }
         None => ShouldPanic::No,
     }
diff --git a/src/libsyntax/util/move_map.rs b/src/libsyntax/util/move_map.rs
index e1078b719bf..fe05e2958b3 100644
--- a/src/libsyntax/util/move_map.rs
+++ b/src/libsyntax/util/move_map.rs
@@ -10,6 +10,8 @@
 
 use std::ptr;
 
+use util::small_vector::SmallVector;
+
 pub trait MoveMap<T>: Sized {
     fn move_map<F>(self, mut f: F) -> Self where F: FnMut(T) -> T {
         self.move_flat_map(|e| Some(f(e)))
@@ -75,3 +77,50 @@ impl<T> MoveMap<T> for ::ptr::P<[T]> {
         ::ptr::P::from_vec(self.into_vec().move_flat_map(f))
     }
 }
+
+impl<T> MoveMap<T> for SmallVector<T> {
+    fn move_flat_map<F, I>(mut self, mut f: F) -> Self
+        where F: FnMut(T) -> I,
+              I: IntoIterator<Item=T>
+    {
+        let mut read_i = 0;
+        let mut write_i = 0;
+        unsafe {
+            let mut old_len = self.len();
+            self.set_len(0); // make sure we just leak elements in case of panic
+
+            while read_i < old_len {
+                // move the read_i'th item out of the vector and map it
+                // to an iterator
+                let e = ptr::read(self.get_unchecked(read_i));
+                let mut iter = f(e).into_iter();
+                read_i += 1;
+
+                while let Some(e) = iter.next() {
+                    if write_i < read_i {
+                        ptr::write(self.get_unchecked_mut(write_i), e);
+                        write_i += 1;
+                    } else {
+                        // If this is reached we ran out of space
+                        // in the middle of the vector.
+                        // However, the vector is in a valid state here,
+                        // so we just do a somewhat inefficient insert.
+                        self.set_len(old_len);
+                        self.insert(write_i, e);
+
+                        old_len = self.len();
+                        self.set_len(0);
+
+                        read_i += 1;
+                        write_i += 1;
+                    }
+                }
+            }
+
+            // write_i tracks the number of actually written new items.
+            self.set_len(write_i);
+        }
+
+        self
+    }
+}
diff --git a/src/libsyntax/util/small_vector.rs b/src/libsyntax/util/small_vector.rs
index 9be7dbd6817..31e675836fc 100644
--- a/src/libsyntax/util/small_vector.rs
+++ b/src/libsyntax/util/small_vector.rs
@@ -8,253 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use self::SmallVectorRepr::*;
-use self::IntoIterRepr::*;
+use rustc_data_structures::small_vec::SmallVec;
 
-use core::ops;
-use std::iter::{IntoIterator, FromIterator};
-use std::mem;
-use std::slice;
-use std::vec;
-
-use util::move_map::MoveMap;
-
-/// A vector type optimized for cases where the size is almost always 0 or 1
-#[derive(Clone)]
-pub struct SmallVector<T> {
-    repr: SmallVectorRepr<T>,
-}
-
-#[derive(Clone)]
-enum SmallVectorRepr<T> {
-    Zero,
-    One(T),
-    Many(Vec<T>),
-}
-
-impl<T> Default for SmallVector<T> {
-    fn default() -> Self {
-        SmallVector { repr: Zero }
-    }
-}
-
-impl<T> Into<Vec<T>> for SmallVector<T> {
-    fn into(self) -> Vec<T> {
-        match self.repr {
-            Zero => Vec::new(),
-            One(t) => vec![t],
-            Many(vec) => vec,
-        }
-    }
-}
-
-impl<T> FromIterator<T> for SmallVector<T> {
-    fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> SmallVector<T> {
-        let mut v = SmallVector::zero();
-        v.extend(iter);
-        v
-    }
-}
-
-impl<T> Extend<T> for SmallVector<T> {
-    fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
-        for val in iter {
-            self.push(val);
-        }
-    }
-}
-
-impl<T> SmallVector<T> {
-    pub fn zero() -> SmallVector<T> {
-        SmallVector { repr: Zero }
-    }
-
-    pub fn one(v: T) -> SmallVector<T> {
-        SmallVector { repr: One(v) }
-    }
-
-    pub fn many(vs: Vec<T>) -> SmallVector<T> {
-        SmallVector { repr: Many(vs) }
-    }
-
-    pub fn as_slice(&self) -> &[T] {
-        self
-    }
-
-    pub fn as_mut_slice(&mut self) -> &mut [T] {
-        self
-    }
-
-    pub fn pop(&mut self) -> Option<T> {
-        match self.repr {
-            Zero => None,
-            One(..) => {
-                let one = mem::replace(&mut self.repr, Zero);
-                match one {
-                    One(v1) => Some(v1),
-                    _ => unreachable!()
-                }
-            }
-            Many(ref mut vs) => vs.pop(),
-        }
-    }
-
-    pub fn push(&mut self, v: T) {
-        match self.repr {
-            Zero => self.repr = One(v),
-            One(..) => {
-                let one = mem::replace(&mut self.repr, Zero);
-                match one {
-                    One(v1) => mem::replace(&mut self.repr, Many(vec![v1, v])),
-                    _ => unreachable!()
-                };
-            }
-            Many(ref mut vs) => vs.push(v)
-        }
-    }
-
-    pub fn push_all(&mut self, other: SmallVector<T>) {
-        for v in other.into_iter() {
-            self.push(v);
-        }
-    }
-
-    pub fn get(&self, idx: usize) -> &T {
-        match self.repr {
-            One(ref v) if idx == 0 => v,
-            Many(ref vs) => &vs[idx],
-            _ => panic!("out of bounds access")
-        }
-    }
-
-    pub fn expect_one(self, err: &'static str) -> T {
-        match self.repr {
-            One(v) => v,
-            Many(v) => {
-                if v.len() == 1 {
-                    v.into_iter().next().unwrap()
-                } else {
-                    panic!(err)
-                }
-            }
-            _ => panic!(err)
-        }
-    }
-
-    pub fn len(&self) -> usize {
-        match self.repr {
-            Zero => 0,
-            One(..) => 1,
-            Many(ref vals) => vals.len()
-        }
-    }
-
-    pub fn is_empty(&self) -> bool { self.len() == 0 }
-
-    pub fn map<U, F: FnMut(T) -> U>(self, mut f: F) -> SmallVector<U> {
-        let repr = match self.repr {
-            Zero => Zero,
-            One(t) => One(f(t)),
-            Many(vec) => Many(vec.into_iter().map(f).collect()),
-        };
-        SmallVector { repr: repr }
-    }
-}
-
-impl<T> ops::Deref for SmallVector<T> {
-    type Target = [T];
-
-    fn deref(&self) -> &[T] {
-        match self.repr {
-            Zero => {
-                let result: &[T] = &[];
-                result
-            }
-            One(ref v) => {
-                unsafe { slice::from_raw_parts(v, 1) }
-            }
-            Many(ref vs) => vs
-        }
-    }
-}
-
-impl<T> ops::DerefMut for SmallVector<T> {
-    fn deref_mut(&mut self) -> &mut [T] {
-        match self.repr {
-            Zero => {
-                let result: &mut [T] = &mut [];
-                result
-            }
-            One(ref mut v) => {
-                unsafe { slice::from_raw_parts_mut(v, 1) }
-            }
-            Many(ref mut vs) => vs
-        }
-    }
-}
-
-impl<T> IntoIterator for SmallVector<T> {
-    type Item = T;
-    type IntoIter = IntoIter<T>;
-    fn into_iter(self) -> Self::IntoIter {
-        let repr = match self.repr {
-            Zero => ZeroIterator,
-            One(v) => OneIterator(v),
-            Many(vs) => ManyIterator(vs.into_iter())
-        };
-        IntoIter { repr: repr }
-    }
-}
-
-pub struct IntoIter<T> {
-    repr: IntoIterRepr<T>,
-}
-
-enum IntoIterRepr<T> {
-    ZeroIterator,
-    OneIterator(T),
-    ManyIterator(vec::IntoIter<T>),
-}
-
-impl<T> Iterator for IntoIter<T> {
-    type Item = T;
-
-    fn next(&mut self) -> Option<T> {
-        match self.repr {
-            ZeroIterator => None,
-            OneIterator(..) => {
-                let mut replacement = ZeroIterator;
-                mem::swap(&mut self.repr, &mut replacement);
-                match replacement {
-                    OneIterator(v) => Some(v),
-                    _ => unreachable!()
-                }
-            }
-            ManyIterator(ref mut inner) => inner.next()
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        match self.repr {
-            ZeroIterator => (0, Some(0)),
-            OneIterator(..) => (1, Some(1)),
-            ManyIterator(ref inner) => inner.size_hint()
-        }
-    }
-}
-
-impl<T> MoveMap<T> for SmallVector<T> {
-    fn move_flat_map<F, I>(self, mut f: F) -> Self
-        where F: FnMut(T) -> I,
-              I: IntoIterator<Item=T>
-    {
-        match self.repr {
-            Zero => Self::zero(),
-            One(v) => f(v).into_iter().collect(),
-            Many(vs) => SmallVector { repr: Many(vs.move_flat_map(f)) },
-        }
-    }
-}
+pub type SmallVector<T> = SmallVec<[T; 1]>;
 
 #[cfg(test)]
 mod tests {
@@ -262,7 +18,7 @@ mod tests {
 
     #[test]
     fn test_len() {
-        let v: SmallVector<isize> = SmallVector::zero();
+        let v: SmallVector<isize> = SmallVector::new();
         assert_eq!(0, v.len());
 
         assert_eq!(1, SmallVector::one(1).len());
@@ -271,30 +27,30 @@ mod tests {
 
     #[test]
     fn test_push_get() {
-        let mut v = SmallVector::zero();
+        let mut v = SmallVector::new();
         v.push(1);
         assert_eq!(1, v.len());
-        assert_eq!(&1, v.get(0));
+        assert_eq!(1, v[0]);
         v.push(2);
         assert_eq!(2, v.len());
-        assert_eq!(&2, v.get(1));
+        assert_eq!(2, v[1]);
         v.push(3);
         assert_eq!(3, v.len());
-        assert_eq!(&3, v.get(2));
+        assert_eq!(3, v[2]);
     }
 
     #[test]
     fn test_from_iter() {
         let v: SmallVector<isize> = (vec![1, 2, 3]).into_iter().collect();
         assert_eq!(3, v.len());
-        assert_eq!(&1, v.get(0));
-        assert_eq!(&2, v.get(1));
-        assert_eq!(&3, v.get(2));
+        assert_eq!(1, v[0]);
+        assert_eq!(2, v[1]);
+        assert_eq!(3, v[2]);
     }
 
     #[test]
     fn test_move_iter() {
-        let v = SmallVector::zero();
+        let v = SmallVector::new();
         let v: Vec<isize> = v.into_iter().collect();
         assert_eq!(v, Vec::new());
 
@@ -308,7 +64,7 @@ mod tests {
     #[test]
     #[should_panic]
     fn test_expect_one_zero() {
-        let _: isize = SmallVector::zero().expect_one("");
+        let _: isize = SmallVector::new().expect_one("");
     }
 
     #[test]