diff options
Diffstat (limited to 'src/libsyntax/tokenstream.rs')
| -rw-r--r-- | src/libsyntax/tokenstream.rs | 298 |
1 files changed, 132 insertions, 166 deletions
diff --git a/src/libsyntax/tokenstream.rs b/src/libsyntax/tokenstream.rs index 26cae2a8e7c..ac155556cda 100644 --- a/src/libsyntax/tokenstream.rs +++ b/src/libsyntax/tokenstream.rs @@ -14,7 +14,6 @@ //! ownership of the original. use crate::parse::token::{self, DelimToken, Token, TokenKind}; -use crate::print::pprust; use syntax_pos::{BytePos, Span, DUMMY_SP}; #[cfg(target_arch = "x86_64")] @@ -23,7 +22,7 @@ use rustc_data_structures::sync::Lrc; use rustc_serialize::{Decoder, Decodable, Encoder, Encodable}; use smallvec::{SmallVec, smallvec}; -use std::{fmt, iter, mem}; +use std::{iter, mem}; #[cfg(test)] mod tests; @@ -137,13 +136,8 @@ impl TokenTree { /// The goal is for procedural macros to work with `TokenStream`s and `TokenTree`s /// instead of a representation of the abstract syntax tree. /// Today's `TokenTree`s can still contain AST via `token::Interpolated` for back-compat. -/// -/// The use of `Option` is an optimization that avoids the need for an -/// allocation when the stream is empty. However, it is not guaranteed that an -/// empty stream is represented with `None`; it may be represented as a `Some` -/// around an empty `Vec`. -#[derive(Clone, Debug)] -pub struct TokenStream(pub Option<Lrc<Vec<TreeAndJoint>>>); +#[derive(Clone, Debug, Default)] +pub struct TokenStream(pub Lrc<Vec<TreeAndJoint>>); pub type TreeAndJoint = (TokenTree, IsJoint); @@ -162,38 +156,36 @@ use IsJoint::*; impl TokenStream { /// Given a `TokenStream` with a `Stream` of only two arguments, return a new `TokenStream` /// separating the two arguments with a comma for diagnostic suggestions. - pub(crate) fn add_comma(&self) -> Option<(TokenStream, Span)> { + pub fn add_comma(&self) -> Option<(TokenStream, Span)> { // Used to suggest if a user writes `foo!(a b);` - if let Some(ref stream) = self.0 { - let mut suggestion = None; - let mut iter = stream.iter().enumerate().peekable(); - while let Some((pos, ts)) = iter.next() { - if let Some((_, next)) = iter.peek() { - let sp = match (&ts, &next) { - (_, (TokenTree::Token(Token { kind: token::Comma, .. }), _)) => continue, - ((TokenTree::Token(token_left), NonJoint), - (TokenTree::Token(token_right), _)) - if ((token_left.is_ident() && !token_left.is_reserved_ident()) - || token_left.is_lit()) && - ((token_right.is_ident() && !token_right.is_reserved_ident()) - || token_right.is_lit()) => token_left.span, - ((TokenTree::Delimited(sp, ..), NonJoint), _) => sp.entire(), - _ => continue, - }; - let sp = sp.shrink_to_hi(); - let comma = (TokenTree::token(token::Comma, sp), NonJoint); - suggestion = Some((pos, comma, sp)); - } - } - if let Some((pos, comma, sp)) = suggestion { - let mut new_stream = vec![]; - let parts = stream.split_at(pos + 1); - new_stream.extend_from_slice(parts.0); - new_stream.push(comma); - new_stream.extend_from_slice(parts.1); - return Some((TokenStream::new(new_stream), sp)); + let mut suggestion = None; + let mut iter = self.0.iter().enumerate().peekable(); + while let Some((pos, ts)) = iter.next() { + if let Some((_, next)) = iter.peek() { + let sp = match (&ts, &next) { + (_, (TokenTree::Token(Token { kind: token::Comma, .. }), _)) => continue, + ((TokenTree::Token(token_left), NonJoint), + (TokenTree::Token(token_right), _)) + if ((token_left.is_ident() && !token_left.is_reserved_ident()) + || token_left.is_lit()) && + ((token_right.is_ident() && !token_right.is_reserved_ident()) + || token_right.is_lit()) => token_left.span, + ((TokenTree::Delimited(sp, ..), NonJoint), _) => sp.entire(), + _ => continue, + }; + let sp = sp.shrink_to_hi(); + let comma = (TokenTree::token(token::Comma, sp), NonJoint); + suggestion = Some((pos, comma, sp)); } } + if let Some((pos, comma, sp)) = suggestion { + let mut new_stream = vec![]; + let parts = self.0.split_at(pos + 1); + new_stream.extend_from_slice(parts.0); + new_stream.push(comma); + new_stream.extend_from_slice(parts.1); + return Some((TokenStream::new(new_stream), sp)); + } None } } @@ -210,9 +202,9 @@ impl From<TokenTree> for TreeAndJoint { } } -impl<T: Into<TokenStream>> iter::FromIterator<T> for TokenStream { - fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { - TokenStream::from_streams(iter.into_iter().map(Into::into).collect::<SmallVec<_>>()) +impl iter::FromIterator<TokenTree> for TokenStream { + fn from_iter<I: IntoIterator<Item = TokenTree>>(iter: I) -> Self { + TokenStream::new(iter.into_iter().map(Into::into).collect::<Vec<TreeAndJoint>>()) } } @@ -225,58 +217,57 @@ impl PartialEq<TokenStream> for TokenStream { } impl TokenStream { - pub fn len(&self) -> usize { - if let Some(ref slice) = self.0 { - slice.len() - } else { - 0 - } + pub fn new(streams: Vec<TreeAndJoint>) -> TokenStream { + TokenStream(Lrc::new(streams)) } - pub fn empty() -> TokenStream { - TokenStream(None) + pub fn is_empty(&self) -> bool { + self.0.is_empty() } - pub fn is_empty(&self) -> bool { - match self.0 { - None => true, - Some(ref stream) => stream.is_empty(), - } + pub fn len(&self) -> usize { + self.0.len() } pub(crate) fn from_streams(mut streams: SmallVec<[TokenStream; 2]>) -> TokenStream { match streams.len() { - 0 => TokenStream::empty(), + 0 => TokenStream::default(), 1 => streams.pop().unwrap(), _ => { - // rust-lang/rust#57735: pre-allocate vector to avoid - // quadratic blow-up due to on-the-fly reallocations. - let tree_count = streams.iter() - .map(|ts| match &ts.0 { None => 0, Some(s) => s.len() }) + // We are going to extend the first stream in `streams` with + // the elements from the subsequent streams. This requires + // using `make_mut()` on the first stream, and in practice this + // doesn't cause cloning 99.9% of the time. + // + // One very common use case is when `streams` has two elements, + // where the first stream has any number of elements within + // (often 1, but sometimes many more) and the second stream has + // a single element within. + + // Determine how much the first stream will be extended. + // Needed to avoid quadratic blow up from on-the-fly + // reallocations (#57735). + let num_appends = streams.iter() + .skip(1) + .map(|ts| ts.len()) .sum(); - let mut vec = Vec::with_capacity(tree_count); - for stream in streams { - match stream.0 { - None => {}, - Some(stream2) => vec.extend(stream2.iter().cloned()), - } + // Get the first stream. If it's `None`, create an empty + // stream. + let mut iter = streams.drain(); + let mut first_stream_lrc = iter.next().unwrap().0; + + // Append the elements to the first stream, after reserving + // space for them. + let first_vec_mut = Lrc::make_mut(&mut first_stream_lrc); + first_vec_mut.reserve(num_appends); + for stream in iter { + first_vec_mut.extend(stream.0.iter().cloned()); } - TokenStream::new(vec) - } - } - } - - pub fn new(streams: Vec<TreeAndJoint>) -> TokenStream { - match streams.len() { - 0 => TokenStream(None), - _ => TokenStream(Some(Lrc::new(streams))), - } - } - pub fn append_to_tree_and_joint_vec(self, vec: &mut Vec<TreeAndJoint>) { - if let Some(stream) = self.0 { - vec.extend(stream.iter().cloned()); + // Create the final `TokenStream`. + TokenStream(first_stream_lrc) + } } } @@ -344,43 +335,22 @@ impl TokenStream { } pub fn map_enumerated<F: FnMut(usize, TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream { - TokenStream(self.0.map(|stream| { - Lrc::new( - stream - .iter() - .enumerate() - .map(|(i, (tree, is_joint))| (f(i, tree.clone()), *is_joint)) - .collect()) - })) + TokenStream(Lrc::new( + self.0 + .iter() + .enumerate() + .map(|(i, (tree, is_joint))| (f(i, tree.clone()), *is_joint)) + .collect() + )) } pub fn map<F: FnMut(TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream { - TokenStream(self.0.map(|stream| { - Lrc::new( - stream - .iter() - .map(|(tree, is_joint)| (f(tree.clone()), *is_joint)) - .collect()) - })) - } - - fn first_tree_and_joint(&self) -> Option<TreeAndJoint> { - self.0.as_ref().map(|stream| { - stream.first().unwrap().clone() - }) - } - - fn last_tree_if_joint(&self) -> Option<TokenTree> { - match self.0 { - None => None, - Some(ref stream) => { - if let (tree, Joint) = stream.last().unwrap() { - Some(tree.clone()) - } else { - None - } - } - } + TokenStream(Lrc::new( + self.0 + .iter() + .map(|(tree, is_joint)| (f(tree.clone()), *is_joint)) + .collect() + )) } } @@ -394,18 +364,48 @@ impl TokenStreamBuilder { } pub fn push<T: Into<TokenStream>>(&mut self, stream: T) { - let stream = stream.into(); - let last_tree_if_joint = self.0.last().and_then(TokenStream::last_tree_if_joint); - if let Some(TokenTree::Token(last_token)) = last_tree_if_joint { - if let Some((TokenTree::Token(token), is_joint)) = stream.first_tree_and_joint() { - if let Some(glued_tok) = last_token.glue(&token) { - let last_stream = self.0.pop().unwrap(); - self.push_all_but_last_tree(&last_stream); - let glued_tt = TokenTree::Token(glued_tok); - let glued_tokenstream = TokenStream::new(vec![(glued_tt, is_joint)]); - self.0.push(glued_tokenstream); - self.push_all_but_first_tree(&stream); - return + let mut stream = stream.into(); + + // If `self` is not empty and the last tree within the last stream is a + // token tree marked with `Joint`... + if let Some(TokenStream(ref mut last_stream_lrc)) = self.0.last_mut() { + if let Some((TokenTree::Token(last_token), Joint)) = last_stream_lrc.last() { + + // ...and `stream` is not empty and the first tree within it is + // a token tree... + let TokenStream(ref mut stream_lrc) = stream; + if let Some((TokenTree::Token(token), is_joint)) = stream_lrc.first() { + + // ...and the two tokens can be glued together... + if let Some(glued_tok) = last_token.glue(&token) { + + // ...then do so, by overwriting the last token + // tree in `self` and removing the first token tree + // from `stream`. This requires using `make_mut()` + // on the last stream in `self` and on `stream`, + // and in practice this doesn't cause cloning 99.9% + // of the time. + + // Overwrite the last token tree with the merged + // token. + let last_vec_mut = Lrc::make_mut(last_stream_lrc); + *last_vec_mut.last_mut().unwrap() = + (TokenTree::Token(glued_tok), *is_joint); + + // Remove the first token tree from `stream`. (This + // is almost always the only tree in `stream`.) + let stream_vec_mut = Lrc::make_mut(stream_lrc); + stream_vec_mut.remove(0); + + // Don't push `stream` if it's empty -- that could + // block subsequent token gluing, by getting + // between two token trees that should be glued + // together. + if !stream.is_empty() { + self.0.push(stream); + } + return; + } } } } @@ -415,26 +415,6 @@ impl TokenStreamBuilder { pub fn build(self) -> TokenStream { TokenStream::from_streams(self.0) } - - fn push_all_but_last_tree(&mut self, stream: &TokenStream) { - if let Some(ref streams) = stream.0 { - let len = streams.len(); - match len { - 1 => {} - _ => self.0.push(TokenStream(Some(Lrc::new(streams[0 .. len - 1].to_vec())))), - } - } - } - - fn push_all_but_first_tree(&mut self, stream: &TokenStream) { - if let Some(ref streams) = stream.0 { - let len = streams.len(); - match len { - 1 => {} - _ => self.0.push(TokenStream(Some(Lrc::new(streams[1 .. len].to_vec())))), - } - } - } } #[derive(Clone)] @@ -457,16 +437,11 @@ impl Cursor { } pub fn next_with_joint(&mut self) -> Option<TreeAndJoint> { - match self.stream.0 { - None => None, - Some(ref stream) => { - if self.index < stream.len() { - self.index += 1; - Some(stream[self.index - 1].clone()) - } else { - None - } - } + if self.index < self.stream.len() { + self.index += 1; + Some(self.stream.0[self.index - 1].clone()) + } else { + None } } @@ -475,22 +450,13 @@ impl Cursor { return; } let index = self.index; - let stream = mem::replace(&mut self.stream, TokenStream(None)); + let stream = mem::take(&mut self.stream); *self = TokenStream::from_streams(smallvec![stream, new_stream]).into_trees(); self.index = index; } pub fn look_ahead(&self, n: usize) -> Option<TokenTree> { - match self.stream.0 { - None => None, - Some(ref stream) => stream[self.index ..].get(n).map(|(tree, _)| tree.clone()), - } - } -} - -impl fmt::Display for TokenStream { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.write_str(&pprust::tts_to_string(self.clone())) + self.stream.0[self.index ..].get(n).map(|(tree, _)| tree.clone()) } } |