]>
Commit | Line | Data |
---|---|---|
5bcae85e SL |
1 | //! # Token Streams |
2 | //! | |
7cac9316 | 3 | //! `TokenStream`s represent syntactic objects before they are converted into ASTs. |
5bcae85e | 4 | //! A `TokenStream` is, roughly speaking, a sequence (eg stream) of `TokenTree`s, |
8bb4bdeb | 5 | //! which are themselves a single `Token` or a `Delimited` subsequence of tokens. |
5bcae85e SL |
6 | //! |
7 | //! ## Ownership | |
9fa01778 | 8 | //! |
e1599b0c | 9 | //! `TokenStream`s are persistent data structures constructed as ropes with reference |
7cac9316 XL |
10 | //! counted-children. In general, this means that calling an operation on a `TokenStream` |
11 | //! (such as `slice`) produces an entirely new `TokenStream` from the borrowed reference to | |
12 | //! the original. This essentially coerces `TokenStream`s into 'views' of their subparts, | |
13 | //! and a borrowed `TokenStream` is sufficient to build an owned `TokenStream` without taking | |
5bcae85e | 14 | //! ownership of the original. |
3157f602 | 15 | |
60c5eb7d | 16 | use crate::token::{self, DelimToken, Token, TokenKind}; |
9fa01778 | 17 | |
60c5eb7d | 18 | use rustc_data_structures::stable_hasher::{HashStable, StableHasher}; |
0731742a | 19 | use rustc_data_structures::sync::Lrc; |
dfeec247 XL |
20 | use rustc_macros::HashStable_Generic; |
21 | use rustc_span::{Span, DUMMY_SP}; | |
22 | use smallvec::{smallvec, SmallVec}; | |
5bcae85e | 23 | |
e74abb32 | 24 | use std::{iter, mem}; |
3157f602 | 25 | |
3157f602 XL |
26 | /// When the main rust parser encounters a syntax-extension invocation, it |
27 | /// parses the arguments to the invocation as a token-tree. This is a very | |
28 | /// loose structure, such that all sorts of different AST-fragments can | |
29 | /// be passed to syntax extensions using a uniform type. | |
30 | /// | |
31 | /// If the syntax extension is an MBE macro, it will attempt to match its | |
32 | /// LHS token tree against the provided token tree, and if it finds a | |
33 | /// match, will transcribe the RHS token tree, splicing in any captured | |
7cac9316 | 34 | /// `macro_parser::matched_nonterminals` into the `SubstNt`s it finds. |
3157f602 XL |
35 | /// |
36 | /// The RHS of an MBE macro is the only place `SubstNt`s are substituted. | |
37 | /// Nothing special happens to misnamed or misplaced `SubstNt`s. | |
3dfed10e | 38 | #[derive(Debug, Clone, PartialEq, Encodable, Decodable, HashStable_Generic)] |
3157f602 XL |
39 | pub enum TokenTree { |
40 | /// A single token | |
dc9dc135 | 41 | Token(Token), |
3157f602 | 42 | /// A delimited sequence of token trees |
9fa01778 | 43 | Delimited(DelimSpan, DelimToken, TokenStream), |
3157f602 XL |
44 | } |
45 | ||
dc9dc135 XL |
46 | // Ensure all fields of `TokenTree` is `Send` and `Sync`. |
47 | #[cfg(parallel_compiler)] | |
48 | fn _dummy() | |
49 | where | |
50 | Token: Send + Sync, | |
51 | DelimSpan: Send + Sync, | |
52 | DelimToken: Send + Sync, | |
53 | TokenStream: Send + Sync, | |
dfeec247 XL |
54 | { |
55 | } | |
dc9dc135 | 56 | |
3157f602 | 57 | impl TokenTree { |
9fa01778 | 58 | /// Checks if this TokenTree is equal to the other, regardless of span information. |
5bcae85e SL |
59 | pub fn eq_unspanned(&self, other: &TokenTree) -> bool { |
60 | match (self, other) { | |
dc9dc135 XL |
61 | (TokenTree::Token(token), TokenTree::Token(token2)) => token.kind == token2.kind, |
62 | (TokenTree::Delimited(_, delim, tts), TokenTree::Delimited(_, delim2, tts2)) => { | |
9fa01778 | 63 | delim == delim2 && tts.eq_unspanned(&tts2) |
83c7162d | 64 | } |
dc9dc135 | 65 | _ => false, |
83c7162d XL |
66 | } |
67 | } | |
68 | ||
9fa01778 | 69 | /// Retrieves the TokenTree's span. |
5bcae85e | 70 | pub fn span(&self) -> Span { |
dc9dc135 XL |
71 | match self { |
72 | TokenTree::Token(token) => token.span, | |
0731742a | 73 | TokenTree::Delimited(sp, ..) => sp.entire(), |
5bcae85e SL |
74 | } |
75 | } | |
76 | ||
a1dfa0c6 | 77 | /// Modify the `TokenTree`'s span in-place. |
3b2f2976 | 78 | pub fn set_span(&mut self, span: Span) { |
dc9dc135 XL |
79 | match self { |
80 | TokenTree::Token(token) => token.span = span, | |
81 | TokenTree::Delimited(dspan, ..) => *dspan = DelimSpan::from_single(span), | |
5bcae85e SL |
82 | } |
83 | } | |
041b39d2 XL |
84 | |
85 | pub fn joint(self) -> TokenStream { | |
9fa01778 | 86 | TokenStream::new(vec![(self, Joint)]) |
0731742a XL |
87 | } |
88 | ||
dc9dc135 XL |
89 | pub fn token(kind: TokenKind, span: Span) -> TokenTree { |
90 | TokenTree::Token(Token::new(kind, span)) | |
91 | } | |
92 | ||
0731742a | 93 | /// Returns the opening delimiter as a token tree. |
60c5eb7d XL |
94 | pub fn open_tt(span: DelimSpan, delim: DelimToken) -> TokenTree { |
95 | TokenTree::token(token::OpenDelim(delim), span.open) | |
0731742a XL |
96 | } |
97 | ||
98 | /// Returns the closing delimiter as a token tree. | |
60c5eb7d XL |
99 | pub fn close_tt(span: DelimSpan, delim: DelimToken) -> TokenTree { |
100 | TokenTree::token(token::CloseDelim(delim), span.close) | |
101 | } | |
74b04a01 XL |
102 | |
103 | pub fn uninterpolate(self) -> TokenTree { | |
104 | match self { | |
105 | TokenTree::Token(token) => TokenTree::Token(token.uninterpolate().into_owned()), | |
106 | tt => tt, | |
107 | } | |
108 | } | |
60c5eb7d XL |
109 | } |
110 | ||
111 | impl<CTX> HashStable<CTX> for TokenStream | |
dfeec247 XL |
112 | where |
113 | CTX: crate::HashStableContext, | |
60c5eb7d XL |
114 | { |
115 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { | |
116 | for sub_tt in self.trees() { | |
117 | sub_tt.hash_stable(hcx, hasher); | |
118 | } | |
041b39d2 | 119 | } |
3157f602 XL |
120 | } |
121 | ||
32a655c1 | 122 | /// A `TokenStream` is an abstract sequence of tokens, organized into `TokenTree`s. |
e1599b0c | 123 | /// |
32a655c1 SL |
124 | /// The goal is for procedural macros to work with `TokenStream`s and `TokenTree`s |
125 | /// instead of a representation of the abstract syntax tree. | |
dc9dc135 | 126 | /// Today's `TokenTree`s can still contain AST via `token::Interpolated` for back-compat. |
3dfed10e | 127 | #[derive(Clone, Debug, Default, Encodable, Decodable)] |
e74abb32 | 128 | pub struct TokenStream(pub Lrc<Vec<TreeAndJoint>>); |
5bcae85e | 129 | |
0731742a XL |
130 | pub type TreeAndJoint = (TokenTree, IsJoint); |
131 | ||
132 | // `TokenStream` is used a lot. Make sure it doesn't unintentionally get bigger. | |
133 | #[cfg(target_arch = "x86_64")] | |
60c5eb7d | 134 | rustc_data_structures::static_assert_size!(TokenStream, 8); |
0731742a | 135 | |
3dfed10e | 136 | #[derive(Clone, Copy, Debug, PartialEq, Encodable, Decodable)] |
0731742a XL |
137 | pub enum IsJoint { |
138 | Joint, | |
dfeec247 | 139 | NonJoint, |
0731742a XL |
140 | } |
141 | ||
9fa01778 | 142 | use IsJoint::*; |
0731742a | 143 | |
b7449926 XL |
144 | impl TokenStream { |
145 | /// Given a `TokenStream` with a `Stream` of only two arguments, return a new `TokenStream` | |
146 | /// separating the two arguments with a comma for diagnostic suggestions. | |
e74abb32 | 147 | pub fn add_comma(&self) -> Option<(TokenStream, Span)> { |
b7449926 | 148 | // Used to suggest if a user writes `foo!(a b);` |
e74abb32 XL |
149 | let mut suggestion = None; |
150 | let mut iter = self.0.iter().enumerate().peekable(); | |
151 | while let Some((pos, ts)) = iter.next() { | |
152 | if let Some((_, next)) = iter.peek() { | |
153 | let sp = match (&ts, &next) { | |
154 | (_, (TokenTree::Token(Token { kind: token::Comma, .. }), _)) => continue, | |
dfeec247 XL |
155 | ( |
156 | (TokenTree::Token(token_left), NonJoint), | |
157 | (TokenTree::Token(token_right), _), | |
158 | ) if ((token_left.is_ident() && !token_left.is_reserved_ident()) | |
159 | || token_left.is_lit()) | |
160 | && ((token_right.is_ident() && !token_right.is_reserved_ident()) | |
161 | || token_right.is_lit()) => | |
162 | { | |
163 | token_left.span | |
164 | } | |
e74abb32 XL |
165 | ((TokenTree::Delimited(sp, ..), NonJoint), _) => sp.entire(), |
166 | _ => continue, | |
167 | }; | |
168 | let sp = sp.shrink_to_hi(); | |
169 | let comma = (TokenTree::token(token::Comma, sp), NonJoint); | |
170 | suggestion = Some((pos, comma, sp)); | |
b7449926 XL |
171 | } |
172 | } | |
e74abb32 XL |
173 | if let Some((pos, comma, sp)) = suggestion { |
174 | let mut new_stream = vec![]; | |
175 | let parts = self.0.split_at(pos + 1); | |
176 | new_stream.extend_from_slice(parts.0); | |
177 | new_stream.push(comma); | |
178 | new_stream.extend_from_slice(parts.1); | |
179 | return Some((TokenStream::new(new_stream), sp)); | |
180 | } | |
b7449926 XL |
181 | None |
182 | } | |
183 | } | |
184 | ||
0731742a XL |
185 | impl From<TokenTree> for TokenStream { |
186 | fn from(tree: TokenTree) -> TokenStream { | |
9fa01778 | 187 | TokenStream::new(vec![(tree, NonJoint)]) |
0731742a | 188 | } |
5bcae85e SL |
189 | } |
190 | ||
0731742a XL |
191 | impl From<TokenTree> for TreeAndJoint { |
192 | fn from(tree: TokenTree) -> TreeAndJoint { | |
193 | (tree, NonJoint) | |
5bcae85e SL |
194 | } |
195 | } | |
196 | ||
e74abb32 XL |
197 | impl iter::FromIterator<TokenTree> for TokenStream { |
198 | fn from_iter<I: IntoIterator<Item = TokenTree>>(iter: I) -> Self { | |
199 | TokenStream::new(iter.into_iter().map(Into::into).collect::<Vec<TreeAndJoint>>()) | |
b7449926 XL |
200 | } |
201 | } | |
202 | ||
32a655c1 SL |
203 | impl Eq for TokenStream {} |
204 | ||
5bcae85e SL |
205 | impl PartialEq<TokenStream> for TokenStream { |
206 | fn eq(&self, other: &TokenStream) -> bool { | |
32a655c1 | 207 | self.trees().eq(other.trees()) |
5bcae85e SL |
208 | } |
209 | } | |
210 | ||
5bcae85e | 211 | impl TokenStream { |
e74abb32 XL |
212 | pub fn new(streams: Vec<TreeAndJoint>) -> TokenStream { |
213 | TokenStream(Lrc::new(streams)) | |
3b2f2976 XL |
214 | } |
215 | ||
e74abb32 XL |
216 | pub fn is_empty(&self) -> bool { |
217 | self.0.is_empty() | |
9e0c209e SL |
218 | } |
219 | ||
e74abb32 XL |
220 | pub fn len(&self) -> usize { |
221 | self.0.len() | |
5bcae85e SL |
222 | } |
223 | ||
60c5eb7d XL |
224 | pub fn span(&self) -> Option<Span> { |
225 | match &**self.0 { | |
226 | [] => None, | |
227 | [(tt, _)] => Some(tt.span()), | |
228 | [(tt_start, _), .., (tt_end, _)] => Some(tt_start.span().to(tt_end.span())), | |
229 | } | |
230 | } | |
231 | ||
232 | pub fn from_streams(mut streams: SmallVec<[TokenStream; 2]>) -> TokenStream { | |
8bb4bdeb | 233 | match streams.len() { |
e74abb32 | 234 | 0 => TokenStream::default(), |
041b39d2 | 235 | 1 => streams.pop().unwrap(), |
0731742a | 236 | _ => { |
e74abb32 XL |
237 | // We are going to extend the first stream in `streams` with |
238 | // the elements from the subsequent streams. This requires | |
239 | // using `make_mut()` on the first stream, and in practice this | |
240 | // doesn't cause cloning 99.9% of the time. | |
241 | // | |
242 | // One very common use case is when `streams` has two elements, | |
243 | // where the first stream has any number of elements within | |
244 | // (often 1, but sometimes many more) and the second stream has | |
245 | // a single element within. | |
246 | ||
247 | // Determine how much the first stream will be extended. | |
248 | // Needed to avoid quadratic blow up from on-the-fly | |
249 | // reallocations (#57735). | |
dfeec247 | 250 | let num_appends = streams.iter().skip(1).map(|ts| ts.len()).sum(); |
9fa01778 | 251 | |
e74abb32 XL |
252 | // Get the first stream. If it's `None`, create an empty |
253 | // stream. | |
60c5eb7d | 254 | let mut iter = streams.drain(..); |
e74abb32 XL |
255 | let mut first_stream_lrc = iter.next().unwrap().0; |
256 | ||
257 | // Append the elements to the first stream, after reserving | |
258 | // space for them. | |
259 | let first_vec_mut = Lrc::make_mut(&mut first_stream_lrc); | |
260 | first_vec_mut.reserve(num_appends); | |
261 | for stream in iter { | |
262 | first_vec_mut.extend(stream.0.iter().cloned()); | |
0731742a | 263 | } |
8bb4bdeb | 264 | |
e74abb32 XL |
265 | // Create the final `TokenStream`. |
266 | TokenStream(first_stream_lrc) | |
267 | } | |
0731742a | 268 | } |
8bb4bdeb XL |
269 | } |
270 | ||
271 | pub fn trees(&self) -> Cursor { | |
272 | self.clone().into_trees() | |
5bcae85e SL |
273 | } |
274 | ||
8bb4bdeb | 275 | pub fn into_trees(self) -> Cursor { |
32a655c1 | 276 | Cursor::new(self) |
5bcae85e SL |
277 | } |
278 | ||
e1599b0c | 279 | /// Compares two `TokenStream`s, checking equality without regarding span information. |
5bcae85e | 280 | pub fn eq_unspanned(&self, other: &TokenStream) -> bool { |
83c7162d XL |
281 | let mut t1 = self.trees(); |
282 | let mut t2 = other.trees(); | |
283 | for (t1, t2) in t1.by_ref().zip(t2.by_ref()) { | |
8bb4bdeb | 284 | if !t1.eq_unspanned(&t2) { |
5bcae85e SL |
285 | return false; |
286 | } | |
287 | } | |
83c7162d XL |
288 | t1.next().is_none() && t2.next().is_none() |
289 | } | |
290 | ||
3b2f2976 | 291 | pub fn map_enumerated<F: FnMut(usize, TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream { |
e74abb32 XL |
292 | TokenStream(Lrc::new( |
293 | self.0 | |
294 | .iter() | |
295 | .enumerate() | |
296 | .map(|(i, (tree, is_joint))| (f(i, tree.clone()), *is_joint)) | |
dfeec247 | 297 | .collect(), |
e74abb32 | 298 | )) |
3b2f2976 XL |
299 | } |
300 | ||
041b39d2 | 301 | pub fn map<F: FnMut(TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream { |
e74abb32 | 302 | TokenStream(Lrc::new( |
dfeec247 | 303 | self.0.iter().map(|(tree, is_joint)| (f(tree.clone()), *is_joint)).collect(), |
e74abb32 | 304 | )) |
041b39d2 XL |
305 | } |
306 | } | |
307 | ||
532ac7d7 | 308 | // 99.5%+ of the time we have 1 or 2 elements in this vector. |
8faf50e0 | 309 | #[derive(Clone)] |
532ac7d7 | 310 | pub struct TokenStreamBuilder(SmallVec<[TokenStream; 2]>); |
041b39d2 XL |
311 | |
312 | impl TokenStreamBuilder { | |
313 | pub fn new() -> TokenStreamBuilder { | |
532ac7d7 | 314 | TokenStreamBuilder(SmallVec::new()) |
041b39d2 XL |
315 | } |
316 | ||
317 | pub fn push<T: Into<TokenStream>>(&mut self, stream: T) { | |
e74abb32 XL |
318 | let mut stream = stream.into(); |
319 | ||
320 | // If `self` is not empty and the last tree within the last stream is a | |
321 | // token tree marked with `Joint`... | |
322 | if let Some(TokenStream(ref mut last_stream_lrc)) = self.0.last_mut() { | |
323 | if let Some((TokenTree::Token(last_token), Joint)) = last_stream_lrc.last() { | |
e74abb32 XL |
324 | // ...and `stream` is not empty and the first tree within it is |
325 | // a token tree... | |
326 | let TokenStream(ref mut stream_lrc) = stream; | |
327 | if let Some((TokenTree::Token(token), is_joint)) = stream_lrc.first() { | |
e74abb32 XL |
328 | // ...and the two tokens can be glued together... |
329 | if let Some(glued_tok) = last_token.glue(&token) { | |
e74abb32 XL |
330 | // ...then do so, by overwriting the last token |
331 | // tree in `self` and removing the first token tree | |
332 | // from `stream`. This requires using `make_mut()` | |
333 | // on the last stream in `self` and on `stream`, | |
334 | // and in practice this doesn't cause cloning 99.9% | |
335 | // of the time. | |
336 | ||
337 | // Overwrite the last token tree with the merged | |
338 | // token. | |
339 | let last_vec_mut = Lrc::make_mut(last_stream_lrc); | |
340 | *last_vec_mut.last_mut().unwrap() = | |
341 | (TokenTree::Token(glued_tok), *is_joint); | |
342 | ||
343 | // Remove the first token tree from `stream`. (This | |
344 | // is almost always the only tree in `stream`.) | |
345 | let stream_vec_mut = Lrc::make_mut(stream_lrc); | |
346 | stream_vec_mut.remove(0); | |
347 | ||
348 | // Don't push `stream` if it's empty -- that could | |
349 | // block subsequent token gluing, by getting | |
350 | // between two token trees that should be glued | |
351 | // together. | |
352 | if !stream.is_empty() { | |
353 | self.0.push(stream); | |
354 | } | |
355 | return; | |
356 | } | |
041b39d2 XL |
357 | } |
358 | } | |
359 | } | |
360 | self.0.push(stream); | |
361 | } | |
362 | ||
041b39d2 | 363 | pub fn build(self) -> TokenStream { |
0731742a | 364 | TokenStream::from_streams(self.0) |
041b39d2 | 365 | } |
5bcae85e SL |
366 | } |
367 | ||
041b39d2 | 368 | #[derive(Clone)] |
0731742a XL |
369 | pub struct Cursor { |
370 | pub stream: TokenStream, | |
8bb4bdeb | 371 | index: usize, |
041b39d2 XL |
372 | } |
373 | ||
374 | impl Iterator for Cursor { | |
375 | type Item = TokenTree; | |
376 | ||
377 | fn next(&mut self) -> Option<TokenTree> { | |
0731742a | 378 | self.next_with_joint().map(|(tree, _)| tree) |
041b39d2 | 379 | } |
32a655c1 | 380 | } |
5bcae85e | 381 | |
8bb4bdeb XL |
382 | impl Cursor { |
383 | fn new(stream: TokenStream) -> Self { | |
0731742a XL |
384 | Cursor { stream, index: 0 } |
385 | } | |
386 | ||
387 | pub fn next_with_joint(&mut self) -> Option<TreeAndJoint> { | |
e74abb32 XL |
388 | if self.index < self.stream.len() { |
389 | self.index += 1; | |
390 | Some(self.stream.0[self.index - 1].clone()) | |
391 | } else { | |
392 | None | |
041b39d2 XL |
393 | } |
394 | } | |
395 | ||
0731742a XL |
396 | pub fn append(&mut self, new_stream: TokenStream) { |
397 | if new_stream.is_empty() { | |
398 | return; | |
5bcae85e | 399 | } |
0731742a | 400 | let index = self.index; |
e74abb32 | 401 | let stream = mem::take(&mut self.stream); |
532ac7d7 | 402 | *self = TokenStream::from_streams(smallvec![stream, new_stream]).into_trees(); |
0731742a | 403 | self.index = index; |
8bb4bdeb XL |
404 | } |
405 | ||
406 | pub fn look_ahead(&self, n: usize) -> Option<TokenTree> { | |
dfeec247 | 407 | self.stream.0[self.index..].get(n).map(|(tree, _)| tree.clone()) |
5bcae85e SL |
408 | } |
409 | } | |
410 | ||
3dfed10e | 411 | #[derive(Debug, Copy, Clone, PartialEq, Encodable, Decodable, HashStable_Generic)] |
b7449926 XL |
412 | pub struct DelimSpan { |
413 | pub open: Span, | |
414 | pub close: Span, | |
415 | } | |
416 | ||
417 | impl DelimSpan { | |
418 | pub fn from_single(sp: Span) -> Self { | |
dfeec247 | 419 | DelimSpan { open: sp, close: sp } |
b7449926 XL |
420 | } |
421 | ||
422 | pub fn from_pair(open: Span, close: Span) -> Self { | |
423 | DelimSpan { open, close } | |
424 | } | |
425 | ||
426 | pub fn dummy() -> Self { | |
427 | Self::from_single(DUMMY_SP) | |
428 | } | |
429 | ||
430 | pub fn entire(self) -> Span { | |
431 | self.open.with_hi(self.close.hi()) | |
432 | } | |
b7449926 | 433 | } |