Auto merge of #35666 - eddyb:rollup, r=eddyb

Rollup of 30 pull requests

- Successful merges: #34941, #35392, #35444, #35447, #35491, #35533, #35539, #35558, #35573, #35574, #35577, #35586, #35588, #35594, #35596, #35597, #35598, #35606, #35611, #35615, #35616, #35620, #35622, #35640, #35643, #35644, #35646, #35647, #35648, #35661
- Failed merges: #35395, #35415

3 files changed, 103 insertions, 30 deletions

diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index ad52184a6dc..afda59c61ff 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -314,7 +314,7 @@ declare_features! (
     (accepted, issue_5723_bootstrap, "1.0.0", None),
     (accepted, macro_rules, "1.0.0", None),
     // Allows using #![no_std]
-    (accepted, no_std, "1.0.0", None),
+    (accepted, no_std, "1.6.0", None),
     (accepted, slicing_syntax, "1.0.0", None),
     (accepted, struct_variant, "1.0.0", None),
     // These are used to test this portion of the compiler, they don't actually
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 4c279b2fe48..e174f3ad08d 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -3788,19 +3788,18 @@ impl<'a> Parser<'a> {
     }
 
     /// Parse a structure field
-    fn parse_name_and_ty(&mut self, pr: Visibility,
-                         attrs: Vec<Attribute> ) -> PResult<'a, StructField> {
-        let lo = match pr {
-            Visibility::Inherited => self.span.lo,
-            _ => self.last_span.lo,
-        };
+    fn parse_name_and_ty(&mut self,
+                         lo: BytePos,
+                         vis: Visibility,
+                         attrs: Vec<Attribute>)
+                         -> PResult<'a, StructField> {
         let name = self.parse_ident()?;
         self.expect(&token::Colon)?;
         let ty = self.parse_ty_sum()?;
         Ok(StructField {
             span: mk_sp(lo, self.last_span.hi),
             ident: Some(name),
-            vis: pr,
+            vis: vis,
             id: ast::DUMMY_NODE_ID,
             ty: ty,
             attrs: attrs,
@@ -5120,10 +5119,11 @@ impl<'a> Parser<'a> {
 
     /// Parse a structure field declaration
     pub fn parse_single_struct_field(&mut self,
+                                     lo: BytePos,
                                      vis: Visibility,
                                      attrs: Vec<Attribute> )
                                      -> PResult<'a, StructField> {
-        let a_var = self.parse_name_and_ty(vis, attrs)?;
+        let a_var = self.parse_name_and_ty(lo, vis, attrs)?;
         match self.token {
             token::Comma => {
                 self.bump();
@@ -5144,8 +5144,9 @@ impl<'a> Parser<'a> {
     /// Parse an element of a struct definition
     fn parse_struct_decl_field(&mut self) -> PResult<'a, StructField> {
         let attrs = self.parse_outer_attributes()?;
+        let lo = self.span.lo;
         let vis = self.parse_visibility(true)?;
-        self.parse_single_struct_field(vis, attrs)
+        self.parse_single_struct_field(lo, vis, attrs)
     }
 
     // If `allow_path` is false, just parse the `pub` in `pub(path)` (but still parse `pub(crate)`)
diff --git a/src/libsyntax/tokenstream.rs b/src/libsyntax/tokenstream.rs
index 89ead21cc10..0171f24101a 100644
--- a/src/libsyntax/tokenstream.rs
+++ b/src/libsyntax/tokenstream.rs
@@ -340,6 +340,11 @@ pub struct TokenStream {
     ts: InternalTS,
 }
 
+// This indicates the maximum size for a leaf in the concatenation algorithm.
+// If two leafs will be collectively smaller than this, they will be merged.
+// If a leaf is larger than this, it will be concatenated at the top.
+const LEAF_SIZE : usize = 32;
+
 // 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)]
@@ -483,6 +488,37 @@ impl InternalTS {
             }
         }
     }
+
+    fn to_vec(&self) -> Vec<&TokenTree> {
+        let mut res = Vec::with_capacity(self.len());
+        fn traverse_and_append<'a>(res: &mut Vec<&'a TokenTree>, ts: &'a InternalTS) {
+            match *ts {
+                InternalTS::Empty(..) => {},
+                InternalTS::Leaf { ref tts, offset, len, .. } => {
+                    let mut to_app = tts[offset..offset + len].iter().collect();
+                    res.append(&mut to_app);
+                }
+                InternalTS::Node { ref left, ref right, .. } => {
+                    traverse_and_append(res, left);
+                    traverse_and_append(res, right);
+                }
+            }
+        }
+        traverse_and_append(&mut res, self);
+        res
+    }
+
+    fn to_tts(&self) -> Vec<TokenTree> {
+        self.to_vec().into_iter().cloned().collect::<Vec<TokenTree>>()
+    }
+
+    // Returns an internal node's children.
+    fn children(&self) -> Option<(Rc<InternalTS>, Rc<InternalTS>)> {
+        match *self {
+            InternalTS::Node { ref left, ref right, .. } => Some((left.clone(), right.clone())),
+            _ => None,
+        }
+    }
 }
 
 /// TokenStream operators include basic destructuring, boolean operations, `maybe_...`
@@ -496,14 +532,17 @@ impl InternalTS {
 ///
 ///    `maybe_path_prefix("a::b::c(a,b,c).foo()") -> (a::b::c, "(a,b,c).foo()")`
 impl TokenStream {
+    // Construct an empty node with a dummy span.
     pub fn mk_empty() -> TokenStream {
         TokenStream { ts: InternalTS::Empty(DUMMY_SP) }
     }
 
+    // Construct an empty node with the provided span.
     fn mk_spanned_empty(sp: Span) -> TokenStream {
         TokenStream { ts: InternalTS::Empty(sp) }
     }
 
+    // Construct a leaf node with a 0 offset and length equivalent to the input.
     fn mk_leaf(tts: Rc<Vec<TokenTree>>, sp: Span) -> TokenStream {
         let len = tts.len();
         TokenStream {
@@ -516,6 +555,7 @@ impl TokenStream {
         }
     }
 
+    // Construct a leaf node with the provided values.
     fn mk_sub_leaf(tts: Rc<Vec<TokenTree>>, offset: usize, len: usize, sp: Span) -> TokenStream {
         TokenStream {
             ts: InternalTS::Leaf {
@@ -527,6 +567,7 @@ impl TokenStream {
         }
     }
 
+    // Construct an internal node with the provided values.
     fn mk_int_node(left: Rc<InternalTS>,
                    right: Rc<InternalTS>,
                    len: usize,
@@ -561,11 +602,56 @@ impl TokenStream {
         }
     }
 
-    /// Concatenates two TokenStreams into a new TokenStream
+    /// 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)
+        // This internal procedure performs 'aggressive compacting' during concatenation as
+        // follows:
+        // - If the nodes' combined total total length is less than 32, we copy both of
+        //   them into a new vector and build a new leaf node.
+        // - If one node is an internal node and the other is a 'small' leaf (length<32),
+        //   we recur down the internal node on the appropriate side.
+        // - Otherwise, we construct a new internal node that points to them as left and
+        // right.
+        fn concat_internal(left: Rc<InternalTS>, right: Rc<InternalTS>) -> TokenStream {
+            let llen = left.len();
+            let rlen = right.len();
+            let len = llen + rlen;
+            let span = combine_spans(left.span(), right.span());
+            if len <= LEAF_SIZE {
+                let mut new_vec = left.to_tts();
+                let mut rvec = right.to_tts();
+                new_vec.append(&mut rvec);
+                return TokenStream::mk_leaf(Rc::new(new_vec), span);
+            }
+
+            match (left.children(), right.children()) {
+                (Some((lleft, lright)), None) => {
+                    if rlen <= LEAF_SIZE  {
+                        let new_right = concat_internal(lright, right);
+                        TokenStream::mk_int_node(lleft, Rc::new(new_right.ts), len, span)
+                    } else {
+                       TokenStream::mk_int_node(left, right, len, span)
+                    }
+                }
+                (None, Some((rleft, rright))) => {
+                    if rlen <= LEAF_SIZE  {
+                        let new_left = concat_internal(left, rleft);
+                        TokenStream::mk_int_node(Rc::new(new_left.ts), rright, len, span)
+                    } else {
+                       TokenStream::mk_int_node(left, right, len, span)
+                    }
+                }
+                (_, _) => TokenStream::mk_int_node(left, right, len, span),
+            }
+        }
+
+        if left.is_empty() {
+            right
+        } else if right.is_empty() {
+            left
+        } else {
+            concat_internal(Rc::new(left.ts), Rc::new(right.ts))
+        }
     }
 
     /// Indicate if the TokenStream is empty.
@@ -580,27 +666,13 @@ impl TokenStream {
 
     /// 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
-                }
-            }
-        }
-        internal_to_vec(&self.ts)
+        self.ts.to_vec()
     }
 
     /// 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>>()
+        self.ts.to_tts()
     }
 
     /// Return the TokenStream's span.