]>
Commit | Line | Data |
---|---|---|
3157f602 XL |
1 | // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
5bcae85e SL |
11 | //! # Token Streams |
12 | //! | |
7cac9316 | 13 | //! `TokenStream`s represent syntactic objects before they are converted into ASTs. |
5bcae85e | 14 | //! A `TokenStream` is, roughly speaking, a sequence (eg stream) of `TokenTree`s, |
8bb4bdeb | 15 | //! which are themselves a single `Token` or a `Delimited` subsequence of tokens. |
5bcae85e SL |
16 | //! |
17 | //! ## Ownership | |
7cac9316 XL |
18 | //! `TokenStreams` are persistent data structures constructed as ropes with reference |
19 | //! counted-children. In general, this means that calling an operation on a `TokenStream` | |
20 | //! (such as `slice`) produces an entirely new `TokenStream` from the borrowed reference to | |
21 | //! the original. This essentially coerces `TokenStream`s into 'views' of their subparts, | |
22 | //! and a borrowed `TokenStream` is sufficient to build an owned `TokenStream` without taking | |
5bcae85e | 23 | //! ownership of the original. |
3157f602 | 24 | |
32a655c1 | 25 | use syntax_pos::{BytePos, Span, DUMMY_SP}; |
3157f602 | 26 | use ext::base; |
8bb4bdeb XL |
27 | use ext::tt::{macro_parser, quoted}; |
28 | use parse::Directory; | |
29 | use parse::token::{self, Token}; | |
9e0c209e | 30 | use print::pprust; |
32a655c1 | 31 | use serialize::{Decoder, Decodable, Encoder, Encodable}; |
32a655c1 | 32 | use util::RcSlice; |
5bcae85e | 33 | |
94b46f34 | 34 | use std::borrow::Cow; |
8bb4bdeb XL |
35 | use std::{fmt, iter, mem}; |
36 | use std::hash::{self, Hash}; | |
3157f602 XL |
37 | |
38 | /// A delimited sequence of token trees | |
39 | #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)] | |
40 | pub struct Delimited { | |
41 | /// The type of delimiter | |
42 | pub delim: token::DelimToken, | |
3157f602 | 43 | /// The delimited sequence of token trees |
8bb4bdeb | 44 | pub tts: ThinTokenStream, |
3157f602 XL |
45 | } |
46 | ||
47 | impl Delimited { | |
48 | /// Returns the opening delimiter as a token. | |
49 | pub fn open_token(&self) -> token::Token { | |
50 | token::OpenDelim(self.delim) | |
51 | } | |
52 | ||
53 | /// Returns the closing delimiter as a token. | |
54 | pub fn close_token(&self) -> token::Token { | |
55 | token::CloseDelim(self.delim) | |
56 | } | |
57 | ||
58 | /// Returns the opening delimiter as a token tree. | |
32a655c1 | 59 | pub fn open_tt(&self, span: Span) -> TokenTree { |
cc61c64b XL |
60 | let open_span = if span == DUMMY_SP { |
61 | DUMMY_SP | |
62 | } else { | |
ea8adc8c | 63 | span.with_hi(span.lo() + BytePos(self.delim.len() as u32)) |
32a655c1 SL |
64 | }; |
65 | TokenTree::Token(open_span, self.open_token()) | |
3157f602 XL |
66 | } |
67 | ||
68 | /// Returns the closing delimiter as a token tree. | |
32a655c1 | 69 | pub fn close_tt(&self, span: Span) -> TokenTree { |
cc61c64b XL |
70 | let close_span = if span == DUMMY_SP { |
71 | DUMMY_SP | |
72 | } else { | |
ea8adc8c | 73 | span.with_lo(span.hi() - BytePos(self.delim.len() as u32)) |
32a655c1 SL |
74 | }; |
75 | TokenTree::Token(close_span, self.close_token()) | |
3157f602 | 76 | } |
5bcae85e SL |
77 | |
78 | /// Returns the token trees inside the delimiters. | |
8bb4bdeb XL |
79 | pub fn stream(&self) -> TokenStream { |
80 | self.tts.clone().into() | |
5bcae85e | 81 | } |
3157f602 XL |
82 | } |
83 | ||
3157f602 XL |
84 | /// When the main rust parser encounters a syntax-extension invocation, it |
85 | /// parses the arguments to the invocation as a token-tree. This is a very | |
86 | /// loose structure, such that all sorts of different AST-fragments can | |
87 | /// be passed to syntax extensions using a uniform type. | |
88 | /// | |
89 | /// If the syntax extension is an MBE macro, it will attempt to match its | |
90 | /// LHS token tree against the provided token tree, and if it finds a | |
91 | /// match, will transcribe the RHS token tree, splicing in any captured | |
7cac9316 | 92 | /// `macro_parser::matched_nonterminals` into the `SubstNt`s it finds. |
3157f602 XL |
93 | /// |
94 | /// The RHS of an MBE macro is the only place `SubstNt`s are substituted. | |
95 | /// Nothing special happens to misnamed or misplaced `SubstNt`s. | |
5bcae85e | 96 | #[derive(Debug, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)] |
3157f602 XL |
97 | pub enum TokenTree { |
98 | /// A single token | |
99 | Token(Span, token::Token), | |
100 | /// A delimited sequence of token trees | |
8bb4bdeb | 101 | Delimited(Span, Delimited), |
3157f602 XL |
102 | } |
103 | ||
104 | impl TokenTree { | |
3157f602 | 105 | /// Use this token tree as a matcher to parse given tts. |
8bb4bdeb | 106 | pub fn parse(cx: &base::ExtCtxt, mtch: &[quoted::TokenTree], tts: TokenStream) |
3157f602 XL |
107 | -> macro_parser::NamedParseResult { |
108 | // `None` is because we're not interpolating | |
476ff2be | 109 | let directory = Directory { |
94b46f34 | 110 | path: Cow::from(cx.current_expansion.module.directory.as_path()), |
476ff2be SL |
111 | ownership: cx.current_expansion.directory_ownership, |
112 | }; | |
7cac9316 | 113 | macro_parser::parse(cx.parse_sess(), tts, mtch, Some(directory), true) |
3157f602 | 114 | } |
5bcae85e SL |
115 | |
116 | /// Check if this TokenTree is equal to the other, regardless of span information. | |
117 | pub fn eq_unspanned(&self, other: &TokenTree) -> bool { | |
118 | match (self, other) { | |
119 | (&TokenTree::Token(_, ref tk), &TokenTree::Token(_, ref tk2)) => tk == tk2, | |
120 | (&TokenTree::Delimited(_, ref dl), &TokenTree::Delimited(_, ref dl2)) => { | |
8bb4bdeb | 121 | dl.delim == dl2.delim && |
83c7162d XL |
122 | dl.stream().eq_unspanned(&dl2.stream()) |
123 | } | |
124 | (_, _) => false, | |
125 | } | |
126 | } | |
127 | ||
128 | // See comments in `interpolated_to_tokenstream` for why we care about | |
129 | // *probably* equal here rather than actual equality | |
130 | // | |
131 | // This is otherwise the same as `eq_unspanned`, only recursing with a | |
132 | // different method. | |
133 | pub fn probably_equal_for_proc_macro(&self, other: &TokenTree) -> bool { | |
134 | match (self, other) { | |
135 | (&TokenTree::Token(_, ref tk), &TokenTree::Token(_, ref tk2)) => { | |
136 | tk.probably_equal_for_proc_macro(tk2) | |
137 | } | |
138 | (&TokenTree::Delimited(_, ref dl), &TokenTree::Delimited(_, ref dl2)) => { | |
139 | dl.delim == dl2.delim && | |
140 | dl.stream().probably_equal_for_proc_macro(&dl2.stream()) | |
5bcae85e SL |
141 | } |
142 | (_, _) => false, | |
143 | } | |
144 | } | |
145 | ||
146 | /// Retrieve the TokenTree's span. | |
147 | pub fn span(&self) -> Span { | |
148 | match *self { | |
8bb4bdeb | 149 | TokenTree::Token(sp, _) | TokenTree::Delimited(sp, _) => sp, |
5bcae85e SL |
150 | } |
151 | } | |
152 | ||
3b2f2976 XL |
153 | /// Modify the `TokenTree`'s span inplace. |
154 | pub fn set_span(&mut self, span: Span) { | |
155 | match *self { | |
156 | TokenTree::Token(ref mut sp, _) | TokenTree::Delimited(ref mut sp, _) => { | |
157 | *sp = span; | |
158 | } | |
159 | } | |
160 | } | |
161 | ||
5bcae85e SL |
162 | /// Indicates if the stream is a token that is equal to the provided token. |
163 | pub fn eq_token(&self, t: Token) -> bool { | |
164 | match *self { | |
165 | TokenTree::Token(_, ref tk) => *tk == t, | |
166 | _ => false, | |
167 | } | |
168 | } | |
041b39d2 XL |
169 | |
170 | pub fn joint(self) -> TokenStream { | |
171 | TokenStream { kind: TokenStreamKind::JointTree(self) } | |
172 | } | |
3157f602 XL |
173 | } |
174 | ||
32a655c1 | 175 | /// # Token Streams |
5bcae85e | 176 | /// |
32a655c1 SL |
177 | /// A `TokenStream` is an abstract sequence of tokens, organized into `TokenTree`s. |
178 | /// The goal is for procedural macros to work with `TokenStream`s and `TokenTree`s | |
179 | /// instead of a representation of the abstract syntax tree. | |
180 | /// Today's `TokenTree`s can still contain AST via `Token::Interpolated` for back-compat. | |
181 | #[derive(Clone, Debug)] | |
5bcae85e | 182 | pub struct TokenStream { |
32a655c1 | 183 | kind: TokenStreamKind, |
5bcae85e SL |
184 | } |
185 | ||
32a655c1 SL |
186 | #[derive(Clone, Debug)] |
187 | enum TokenStreamKind { | |
188 | Empty, | |
189 | Tree(TokenTree), | |
041b39d2 | 190 | JointTree(TokenTree), |
32a655c1 | 191 | Stream(RcSlice<TokenStream>), |
5bcae85e SL |
192 | } |
193 | ||
32a655c1 SL |
194 | impl From<TokenTree> for TokenStream { |
195 | fn from(tt: TokenTree) -> TokenStream { | |
196 | TokenStream { kind: TokenStreamKind::Tree(tt) } | |
5bcae85e SL |
197 | } |
198 | } | |
199 | ||
cc61c64b XL |
200 | impl From<Token> for TokenStream { |
201 | fn from(token: Token) -> TokenStream { | |
202 | TokenTree::Token(DUMMY_SP, token).into() | |
203 | } | |
204 | } | |
205 | ||
32a655c1 SL |
206 | impl<T: Into<TokenStream>> iter::FromIterator<T> for TokenStream { |
207 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { | |
8bb4bdeb | 208 | TokenStream::concat(iter.into_iter().map(Into::into).collect::<Vec<_>>()) |
5bcae85e SL |
209 | } |
210 | } | |
211 | ||
32a655c1 SL |
212 | impl Eq for TokenStream {} |
213 | ||
5bcae85e SL |
214 | impl PartialEq<TokenStream> for TokenStream { |
215 | fn eq(&self, other: &TokenStream) -> bool { | |
32a655c1 | 216 | self.trees().eq(other.trees()) |
5bcae85e SL |
217 | } |
218 | } | |
219 | ||
5bcae85e | 220 | impl TokenStream { |
3b2f2976 XL |
221 | pub fn len(&self) -> usize { |
222 | if let TokenStreamKind::Stream(ref slice) = self.kind { | |
223 | slice.len() | |
224 | } else { | |
225 | 0 | |
226 | } | |
227 | } | |
228 | ||
32a655c1 SL |
229 | pub fn empty() -> TokenStream { |
230 | TokenStream { kind: TokenStreamKind::Empty } | |
9e0c209e SL |
231 | } |
232 | ||
5bcae85e | 233 | pub fn is_empty(&self) -> bool { |
32a655c1 SL |
234 | match self.kind { |
235 | TokenStreamKind::Empty => true, | |
236 | _ => false, | |
5bcae85e SL |
237 | } |
238 | } | |
239 | ||
8bb4bdeb XL |
240 | pub fn concat(mut streams: Vec<TokenStream>) -> TokenStream { |
241 | match streams.len() { | |
242 | 0 => TokenStream::empty(), | |
041b39d2 | 243 | 1 => streams.pop().unwrap(), |
8bb4bdeb XL |
244 | _ => TokenStream::concat_rc_slice(RcSlice::new(streams)), |
245 | } | |
246 | } | |
247 | ||
248 | fn concat_rc_slice(streams: RcSlice<TokenStream>) -> TokenStream { | |
249 | TokenStream { kind: TokenStreamKind::Stream(streams) } | |
250 | } | |
251 | ||
252 | pub fn trees(&self) -> Cursor { | |
253 | self.clone().into_trees() | |
5bcae85e SL |
254 | } |
255 | ||
8bb4bdeb | 256 | pub fn into_trees(self) -> Cursor { |
32a655c1 | 257 | Cursor::new(self) |
5bcae85e SL |
258 | } |
259 | ||
260 | /// Compares two TokenStreams, checking equality without regarding span information. | |
261 | pub fn eq_unspanned(&self, other: &TokenStream) -> bool { | |
83c7162d XL |
262 | let mut t1 = self.trees(); |
263 | let mut t2 = other.trees(); | |
264 | for (t1, t2) in t1.by_ref().zip(t2.by_ref()) { | |
8bb4bdeb | 265 | if !t1.eq_unspanned(&t2) { |
5bcae85e SL |
266 | return false; |
267 | } | |
268 | } | |
83c7162d XL |
269 | t1.next().is_none() && t2.next().is_none() |
270 | } | |
271 | ||
272 | // See comments in `interpolated_to_tokenstream` for why we care about | |
273 | // *probably* equal here rather than actual equality | |
274 | // | |
275 | // This is otherwise the same as `eq_unspanned`, only recursing with a | |
276 | // different method. | |
277 | pub fn probably_equal_for_proc_macro(&self, other: &TokenStream) -> bool { | |
278 | let mut t1 = self.trees(); | |
279 | let mut t2 = other.trees(); | |
280 | for (t1, t2) in t1.by_ref().zip(t2.by_ref()) { | |
281 | if !t1.probably_equal_for_proc_macro(&t2) { | |
282 | return false; | |
283 | } | |
284 | } | |
285 | t1.next().is_none() && t2.next().is_none() | |
5bcae85e | 286 | } |
041b39d2 XL |
287 | |
288 | /// Precondition: `self` consists of a single token tree. | |
289 | /// Returns true if the token tree is a joint operation w.r.t. `proc_macro::TokenNode`. | |
290 | pub fn as_tree(self) -> (TokenTree, bool /* joint? */) { | |
291 | match self.kind { | |
292 | TokenStreamKind::Tree(tree) => (tree, false), | |
293 | TokenStreamKind::JointTree(tree) => (tree, true), | |
294 | _ => unreachable!(), | |
295 | } | |
296 | } | |
297 | ||
3b2f2976 XL |
298 | pub fn map_enumerated<F: FnMut(usize, TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream { |
299 | let mut trees = self.into_trees(); | |
300 | let mut result = Vec::new(); | |
301 | let mut i = 0; | |
302 | while let Some(stream) = trees.next_as_stream() { | |
303 | result.push(match stream.kind { | |
304 | TokenStreamKind::Tree(tree) => f(i, tree).into(), | |
305 | TokenStreamKind::JointTree(tree) => f(i, tree).joint(), | |
306 | _ => unreachable!() | |
307 | }); | |
308 | i += 1; | |
309 | } | |
310 | TokenStream::concat(result) | |
311 | } | |
312 | ||
041b39d2 XL |
313 | pub fn map<F: FnMut(TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream { |
314 | let mut trees = self.into_trees(); | |
315 | let mut result = Vec::new(); | |
316 | while let Some(stream) = trees.next_as_stream() { | |
317 | result.push(match stream.kind { | |
318 | TokenStreamKind::Tree(tree) => f(tree).into(), | |
319 | TokenStreamKind::JointTree(tree) => f(tree).joint(), | |
320 | _ => unreachable!() | |
321 | }); | |
322 | } | |
323 | TokenStream::concat(result) | |
324 | } | |
325 | ||
2c00a5a8 | 326 | fn first_tree_and_joint(&self) -> Option<(TokenTree, bool)> { |
041b39d2 XL |
327 | match self.kind { |
328 | TokenStreamKind::Empty => None, | |
2c00a5a8 XL |
329 | TokenStreamKind::Tree(ref tree) => Some((tree.clone(), false)), |
330 | TokenStreamKind::JointTree(ref tree) => Some((tree.clone(), true)), | |
331 | TokenStreamKind::Stream(ref stream) => stream.first().unwrap().first_tree_and_joint(), | |
041b39d2 XL |
332 | } |
333 | } | |
334 | ||
335 | fn last_tree_if_joint(&self) -> Option<TokenTree> { | |
336 | match self.kind { | |
337 | TokenStreamKind::Empty | TokenStreamKind::Tree(..) => None, | |
338 | TokenStreamKind::JointTree(ref tree) => Some(tree.clone()), | |
339 | TokenStreamKind::Stream(ref stream) => stream.last().unwrap().last_tree_if_joint(), | |
340 | } | |
341 | } | |
342 | } | |
343 | ||
344 | pub struct TokenStreamBuilder(Vec<TokenStream>); | |
345 | ||
346 | impl TokenStreamBuilder { | |
347 | pub fn new() -> TokenStreamBuilder { | |
348 | TokenStreamBuilder(Vec::new()) | |
349 | } | |
350 | ||
351 | pub fn push<T: Into<TokenStream>>(&mut self, stream: T) { | |
352 | let stream = stream.into(); | |
353 | let last_tree_if_joint = self.0.last().and_then(TokenStream::last_tree_if_joint); | |
354 | if let Some(TokenTree::Token(last_span, last_tok)) = last_tree_if_joint { | |
2c00a5a8 | 355 | if let Some((TokenTree::Token(span, tok), is_joint)) = stream.first_tree_and_joint() { |
041b39d2 XL |
356 | if let Some(glued_tok) = last_tok.glue(tok) { |
357 | let last_stream = self.0.pop().unwrap(); | |
358 | self.push_all_but_last_tree(&last_stream); | |
359 | let glued_span = last_span.to(span); | |
2c00a5a8 XL |
360 | let glued_tt = TokenTree::Token(glued_span, glued_tok); |
361 | let glued_tokenstream = if is_joint { | |
362 | glued_tt.joint() | |
363 | } else { | |
364 | glued_tt.into() | |
365 | }; | |
366 | self.0.push(glued_tokenstream); | |
041b39d2 XL |
367 | self.push_all_but_first_tree(&stream); |
368 | return | |
369 | } | |
370 | } | |
371 | } | |
372 | self.0.push(stream); | |
373 | } | |
374 | ||
375 | pub fn add<T: Into<TokenStream>>(mut self, stream: T) -> Self { | |
376 | self.push(stream); | |
377 | self | |
378 | } | |
379 | ||
380 | pub fn build(self) -> TokenStream { | |
381 | TokenStream::concat(self.0) | |
382 | } | |
383 | ||
384 | fn push_all_but_last_tree(&mut self, stream: &TokenStream) { | |
385 | if let TokenStreamKind::Stream(ref streams) = stream.kind { | |
386 | let len = streams.len(); | |
387 | match len { | |
388 | 1 => {} | |
389 | 2 => self.0.push(streams[0].clone().into()), | |
390 | _ => self.0.push(TokenStream::concat_rc_slice(streams.sub_slice(0 .. len - 1))), | |
391 | } | |
392 | self.push_all_but_last_tree(&streams[len - 1]) | |
393 | } | |
394 | } | |
395 | ||
396 | fn push_all_but_first_tree(&mut self, stream: &TokenStream) { | |
397 | if let TokenStreamKind::Stream(ref streams) = stream.kind { | |
398 | let len = streams.len(); | |
399 | match len { | |
400 | 1 => {} | |
401 | 2 => self.0.push(streams[1].clone().into()), | |
402 | _ => self.0.push(TokenStream::concat_rc_slice(streams.sub_slice(1 .. len))), | |
403 | } | |
404 | self.push_all_but_first_tree(&streams[0]) | |
405 | } | |
406 | } | |
5bcae85e SL |
407 | } |
408 | ||
041b39d2 | 409 | #[derive(Clone)] |
8bb4bdeb | 410 | pub struct Cursor(CursorKind); |
5bcae85e | 411 | |
041b39d2 | 412 | #[derive(Clone)] |
8bb4bdeb XL |
413 | enum CursorKind { |
414 | Empty, | |
415 | Tree(TokenTree, bool /* consumed? */), | |
041b39d2 | 416 | JointTree(TokenTree, bool /* consumed? */), |
8bb4bdeb | 417 | Stream(StreamCursor), |
5bcae85e SL |
418 | } |
419 | ||
041b39d2 | 420 | #[derive(Clone)] |
8bb4bdeb XL |
421 | struct StreamCursor { |
422 | stream: RcSlice<TokenStream>, | |
423 | index: usize, | |
424 | stack: Vec<(RcSlice<TokenStream>, usize)>, | |
5bcae85e SL |
425 | } |
426 | ||
041b39d2 XL |
427 | impl StreamCursor { |
428 | fn new(stream: RcSlice<TokenStream>) -> Self { | |
429 | StreamCursor { stream: stream, index: 0, stack: Vec::new() } | |
430 | } | |
8bb4bdeb | 431 | |
041b39d2 | 432 | fn next_as_stream(&mut self) -> Option<TokenStream> { |
8bb4bdeb | 433 | loop { |
041b39d2 XL |
434 | if self.index < self.stream.len() { |
435 | self.index += 1; | |
436 | let next = self.stream[self.index - 1].clone(); | |
437 | match next.kind { | |
438 | TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => return Some(next), | |
439 | TokenStreamKind::Stream(stream) => self.insert(stream), | |
440 | TokenStreamKind::Empty => {} | |
8bb4bdeb | 441 | } |
041b39d2 XL |
442 | } else if let Some((stream, index)) = self.stack.pop() { |
443 | self.stream = stream; | |
444 | self.index = index; | |
8bb4bdeb XL |
445 | } else { |
446 | return None; | |
447 | } | |
32a655c1 SL |
448 | } |
449 | } | |
041b39d2 XL |
450 | |
451 | fn insert(&mut self, stream: RcSlice<TokenStream>) { | |
452 | self.stack.push((mem::replace(&mut self.stream, stream), | |
453 | mem::replace(&mut self.index, 0))); | |
454 | } | |
455 | } | |
456 | ||
457 | impl Iterator for Cursor { | |
458 | type Item = TokenTree; | |
459 | ||
460 | fn next(&mut self) -> Option<TokenTree> { | |
461 | self.next_as_stream().map(|stream| match stream.kind { | |
462 | TokenStreamKind::Tree(tree) | TokenStreamKind::JointTree(tree) => tree, | |
463 | _ => unreachable!() | |
464 | }) | |
465 | } | |
32a655c1 | 466 | } |
5bcae85e | 467 | |
8bb4bdeb XL |
468 | impl Cursor { |
469 | fn new(stream: TokenStream) -> Self { | |
470 | Cursor(match stream.kind { | |
471 | TokenStreamKind::Empty => CursorKind::Empty, | |
472 | TokenStreamKind::Tree(tree) => CursorKind::Tree(tree, false), | |
041b39d2 XL |
473 | TokenStreamKind::JointTree(tree) => CursorKind::JointTree(tree, false), |
474 | TokenStreamKind::Stream(stream) => CursorKind::Stream(StreamCursor::new(stream)), | |
8bb4bdeb | 475 | }) |
32a655c1 SL |
476 | } |
477 | ||
041b39d2 XL |
478 | pub fn next_as_stream(&mut self) -> Option<TokenStream> { |
479 | let (stream, consumed) = match self.0 { | |
480 | CursorKind::Tree(ref tree, ref mut consumed @ false) => | |
481 | (tree.clone().into(), consumed), | |
482 | CursorKind::JointTree(ref tree, ref mut consumed @ false) => | |
483 | (tree.clone().joint(), consumed), | |
484 | CursorKind::Stream(ref mut cursor) => return cursor.next_as_stream(), | |
485 | _ => return None, | |
486 | }; | |
487 | ||
488 | *consumed = true; | |
489 | Some(stream) | |
490 | } | |
491 | ||
492 | pub fn insert(&mut self, stream: TokenStream) { | |
493 | match self.0 { | |
494 | _ if stream.is_empty() => return, | |
495 | CursorKind::Empty => *self = stream.trees(), | |
496 | CursorKind::Tree(_, consumed) | CursorKind::JointTree(_, consumed) => { | |
497 | *self = TokenStream::concat(vec![self.original_stream(), stream]).trees(); | |
498 | if consumed { | |
499 | self.next(); | |
500 | } | |
501 | } | |
502 | CursorKind::Stream(ref mut cursor) => { | |
503 | cursor.insert(ThinTokenStream::from(stream).0.unwrap()); | |
504 | } | |
505 | } | |
506 | } | |
507 | ||
508 | pub fn original_stream(&self) -> TokenStream { | |
8bb4bdeb XL |
509 | match self.0 { |
510 | CursorKind::Empty => TokenStream::empty(), | |
041b39d2 XL |
511 | CursorKind::Tree(ref tree, _) => tree.clone().into(), |
512 | CursorKind::JointTree(ref tree, _) => tree.clone().joint(), | |
513 | CursorKind::Stream(ref cursor) => TokenStream::concat_rc_slice({ | |
514 | cursor.stack.get(0).cloned().map(|(stream, _)| stream) | |
515 | .unwrap_or(cursor.stream.clone()) | |
8bb4bdeb | 516 | }), |
5bcae85e | 517 | } |
8bb4bdeb XL |
518 | } |
519 | ||
520 | pub fn look_ahead(&self, n: usize) -> Option<TokenTree> { | |
521 | fn look_ahead(streams: &[TokenStream], mut n: usize) -> Result<TokenTree, usize> { | |
522 | for stream in streams { | |
523 | n = match stream.kind { | |
041b39d2 XL |
524 | TokenStreamKind::Tree(ref tree) | TokenStreamKind::JointTree(ref tree) |
525 | if n == 0 => return Ok(tree.clone()), | |
526 | TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => n - 1, | |
8bb4bdeb XL |
527 | TokenStreamKind::Stream(ref stream) => match look_ahead(stream, n) { |
528 | Ok(tree) => return Ok(tree), | |
529 | Err(n) => n, | |
530 | }, | |
531 | _ => n, | |
532 | }; | |
533 | } | |
8bb4bdeb | 534 | Err(n) |
5bcae85e | 535 | } |
8bb4bdeb XL |
536 | |
537 | match self.0 { | |
041b39d2 XL |
538 | CursorKind::Empty | |
539 | CursorKind::Tree(_, true) | | |
540 | CursorKind::JointTree(_, true) => Err(n), | |
541 | CursorKind::Tree(ref tree, false) | | |
542 | CursorKind::JointTree(ref tree, false) => look_ahead(&[tree.clone().into()], n), | |
8bb4bdeb XL |
543 | CursorKind::Stream(ref cursor) => { |
544 | look_ahead(&cursor.stream[cursor.index ..], n).or_else(|mut n| { | |
545 | for &(ref stream, index) in cursor.stack.iter().rev() { | |
546 | n = match look_ahead(&stream[index..], n) { | |
547 | Ok(tree) => return Ok(tree), | |
548 | Err(n) => n, | |
549 | } | |
550 | } | |
551 | ||
552 | Err(n) | |
553 | }) | |
554 | } | |
555 | }.ok() | |
556 | } | |
557 | } | |
558 | ||
559 | /// The `TokenStream` type is large enough to represent a single `TokenTree` without allocation. | |
560 | /// `ThinTokenStream` is smaller, but needs to allocate to represent a single `TokenTree`. | |
561 | /// We must use `ThinTokenStream` in `TokenTree::Delimited` to avoid infinite size due to recursion. | |
562 | #[derive(Debug, Clone)] | |
563 | pub struct ThinTokenStream(Option<RcSlice<TokenStream>>); | |
564 | ||
565 | impl From<TokenStream> for ThinTokenStream { | |
566 | fn from(stream: TokenStream) -> ThinTokenStream { | |
567 | ThinTokenStream(match stream.kind { | |
568 | TokenStreamKind::Empty => None, | |
569 | TokenStreamKind::Tree(tree) => Some(RcSlice::new(vec![tree.into()])), | |
041b39d2 | 570 | TokenStreamKind::JointTree(tree) => Some(RcSlice::new(vec![tree.joint()])), |
8bb4bdeb XL |
571 | TokenStreamKind::Stream(stream) => Some(stream), |
572 | }) | |
573 | } | |
574 | } | |
575 | ||
576 | impl From<ThinTokenStream> for TokenStream { | |
577 | fn from(stream: ThinTokenStream) -> TokenStream { | |
578 | stream.0.map(TokenStream::concat_rc_slice).unwrap_or_else(TokenStream::empty) | |
579 | } | |
580 | } | |
581 | ||
582 | impl Eq for ThinTokenStream {} | |
583 | ||
584 | impl PartialEq<ThinTokenStream> for ThinTokenStream { | |
585 | fn eq(&self, other: &ThinTokenStream) -> bool { | |
586 | TokenStream::from(self.clone()) == TokenStream::from(other.clone()) | |
5bcae85e SL |
587 | } |
588 | } | |
589 | ||
32a655c1 SL |
590 | impl fmt::Display for TokenStream { |
591 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
cc61c64b | 592 | f.write_str(&pprust::tokens_to_string(self.clone())) |
5bcae85e SL |
593 | } |
594 | } | |
595 | ||
32a655c1 SL |
596 | impl Encodable for TokenStream { |
597 | fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> { | |
8bb4bdeb | 598 | self.trees().collect::<Vec<_>>().encode(encoder) |
32a655c1 SL |
599 | } |
600 | } | |
5bcae85e | 601 | |
32a655c1 SL |
602 | impl Decodable for TokenStream { |
603 | fn decode<D: Decoder>(decoder: &mut D) -> Result<TokenStream, D::Error> { | |
604 | Vec::<TokenTree>::decode(decoder).map(|vec| vec.into_iter().collect()) | |
5bcae85e SL |
605 | } |
606 | } | |
607 | ||
8bb4bdeb XL |
608 | impl Hash for TokenStream { |
609 | fn hash<H: hash::Hasher>(&self, state: &mut H) { | |
610 | for tree in self.trees() { | |
611 | tree.hash(state); | |
612 | } | |
613 | } | |
614 | } | |
615 | ||
616 | impl Encodable for ThinTokenStream { | |
617 | fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> { | |
618 | TokenStream::from(self.clone()).encode(encoder) | |
619 | } | |
620 | } | |
621 | ||
622 | impl Decodable for ThinTokenStream { | |
623 | fn decode<D: Decoder>(decoder: &mut D) -> Result<ThinTokenStream, D::Error> { | |
624 | TokenStream::decode(decoder).map(Into::into) | |
625 | } | |
626 | } | |
627 | ||
628 | impl Hash for ThinTokenStream { | |
629 | fn hash<H: hash::Hasher>(&self, state: &mut H) { | |
630 | TokenStream::from(self.clone()).hash(state); | |
631 | } | |
632 | } | |
633 | ||
5bcae85e SL |
634 | |
635 | #[cfg(test)] | |
636 | mod tests { | |
637 | use super::*; | |
476ff2be | 638 | use syntax::ast::Ident; |
0531ce1d | 639 | use with_globals; |
32a655c1 SL |
640 | use syntax_pos::{Span, BytePos, NO_EXPANSION}; |
641 | use parse::token::Token; | |
8bb4bdeb | 642 | use util::parser_testing::string_to_stream; |
32a655c1 SL |
643 | |
644 | fn string_to_ts(string: &str) -> TokenStream { | |
8bb4bdeb | 645 | string_to_stream(string.to_owned()) |
32a655c1 | 646 | } |
5bcae85e SL |
647 | |
648 | fn sp(a: u32, b: u32) -> Span { | |
ea8adc8c | 649 | Span::new(BytePos(a), BytePos(b), NO_EXPANSION) |
5bcae85e SL |
650 | } |
651 | ||
5bcae85e SL |
652 | #[test] |
653 | fn test_concat() { | |
0531ce1d XL |
654 | with_globals(|| { |
655 | let test_res = string_to_ts("foo::bar::baz"); | |
656 | let test_fst = string_to_ts("foo::bar"); | |
657 | let test_snd = string_to_ts("::baz"); | |
658 | let eq_res = TokenStream::concat(vec![test_fst, test_snd]); | |
659 | assert_eq!(test_res.trees().count(), 5); | |
660 | assert_eq!(eq_res.trees().count(), 5); | |
661 | assert_eq!(test_res.eq_unspanned(&eq_res), true); | |
662 | }) | |
5bcae85e SL |
663 | } |
664 | ||
5bcae85e SL |
665 | #[test] |
666 | fn test_to_from_bijection() { | |
0531ce1d XL |
667 | with_globals(|| { |
668 | let test_start = string_to_ts("foo::bar(baz)"); | |
669 | let test_end = test_start.trees().collect(); | |
670 | assert_eq!(test_start, test_end) | |
671 | }) | |
5bcae85e SL |
672 | } |
673 | ||
674 | #[test] | |
675 | fn test_eq_0() { | |
0531ce1d XL |
676 | with_globals(|| { |
677 | let test_res = string_to_ts("foo"); | |
678 | let test_eqs = string_to_ts("foo"); | |
679 | assert_eq!(test_res, test_eqs) | |
680 | }) | |
5bcae85e SL |
681 | } |
682 | ||
683 | #[test] | |
684 | fn test_eq_1() { | |
0531ce1d XL |
685 | with_globals(|| { |
686 | let test_res = string_to_ts("::bar::baz"); | |
687 | let test_eqs = string_to_ts("::bar::baz"); | |
688 | assert_eq!(test_res, test_eqs) | |
689 | }) | |
5bcae85e SL |
690 | } |
691 | ||
5bcae85e SL |
692 | #[test] |
693 | fn test_eq_3() { | |
0531ce1d XL |
694 | with_globals(|| { |
695 | let test_res = string_to_ts(""); | |
696 | let test_eqs = string_to_ts(""); | |
697 | assert_eq!(test_res, test_eqs) | |
698 | }) | |
5bcae85e SL |
699 | } |
700 | ||
701 | #[test] | |
702 | fn test_diseq_0() { | |
0531ce1d XL |
703 | with_globals(|| { |
704 | let test_res = string_to_ts("::bar::baz"); | |
705 | let test_eqs = string_to_ts("bar::baz"); | |
706 | assert_eq!(test_res == test_eqs, false) | |
707 | }) | |
5bcae85e SL |
708 | } |
709 | ||
710 | #[test] | |
711 | fn test_diseq_1() { | |
0531ce1d XL |
712 | with_globals(|| { |
713 | let test_res = string_to_ts("(bar,baz)"); | |
714 | let test_eqs = string_to_ts("bar,baz"); | |
715 | assert_eq!(test_res == test_eqs, false) | |
716 | }) | |
5bcae85e SL |
717 | } |
718 | ||
5bcae85e SL |
719 | #[test] |
720 | fn test_is_empty() { | |
0531ce1d XL |
721 | with_globals(|| { |
722 | let test0: TokenStream = Vec::<TokenTree>::new().into_iter().collect(); | |
723 | let test1: TokenStream = | |
724 | TokenTree::Token(sp(0, 1), Token::Ident(Ident::from_str("a"), false)).into(); | |
725 | let test2 = string_to_ts("foo(bar::baz)"); | |
726 | ||
727 | assert_eq!(test0.is_empty(), true); | |
728 | assert_eq!(test1.is_empty(), false); | |
729 | assert_eq!(test2.is_empty(), false); | |
730 | }) | |
5bcae85e | 731 | } |
2c00a5a8 XL |
732 | |
733 | #[test] | |
734 | fn test_dotdotdot() { | |
735 | let mut builder = TokenStreamBuilder::new(); | |
736 | builder.push(TokenTree::Token(sp(0, 1), Token::Dot).joint()); | |
737 | builder.push(TokenTree::Token(sp(1, 2), Token::Dot).joint()); | |
738 | builder.push(TokenTree::Token(sp(2, 3), Token::Dot)); | |
739 | let stream = builder.build(); | |
740 | assert!(stream.eq_unspanned(&string_to_ts("..."))); | |
741 | assert_eq!(stream.trees().count(), 1); | |
742 | } | |
743 | ||
5bcae85e | 744 | } |