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.
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.
13 //! `TokenStream`s represent syntactic objects before they are converted into ASTs.
14 //! A `TokenStream` is, roughly speaking, a sequence (eg stream) of `TokenTree`s,
15 //! which are themselves a single `Token` or a `Delimited` subsequence of tokens.
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
23 //! ownership of the original.
25 use syntax_pos
::{BytePos, Span, DUMMY_SP}
;
27 use ext
::tt
::{macro_parser, quoted}
;
29 use parse
::token
::{self, Token}
;
31 use serialize
::{Decoder, Decodable, Encoder, Encodable}
;
34 use std
::{fmt, iter, mem}
;
35 use std
::hash
::{self, Hash}
;
37 /// A delimited sequence of token trees
38 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
39 pub struct Delimited
{
40 /// The type of delimiter
41 pub delim
: token
::DelimToken
,
42 /// The delimited sequence of token trees
43 pub tts
: ThinTokenStream
,
47 /// Returns the opening delimiter as a token.
48 pub fn open_token(&self) -> token
::Token
{
49 token
::OpenDelim(self.delim
)
52 /// Returns the closing delimiter as a token.
53 pub fn close_token(&self) -> token
::Token
{
54 token
::CloseDelim(self.delim
)
57 /// Returns the opening delimiter as a token tree.
58 pub fn open_tt(&self, span
: Span
) -> TokenTree
{
59 let open_span
= if span
== DUMMY_SP
{
62 span
.with_hi(span
.lo() + BytePos(self.delim
.len() as u32))
64 TokenTree
::Token(open_span
, self.open_token())
67 /// Returns the closing delimiter as a token tree.
68 pub fn close_tt(&self, span
: Span
) -> TokenTree
{
69 let close_span
= if span
== DUMMY_SP
{
72 span
.with_lo(span
.hi() - BytePos(self.delim
.len() as u32))
74 TokenTree
::Token(close_span
, self.close_token())
77 /// Returns the token trees inside the delimiters.
78 pub fn stream(&self) -> TokenStream
{
79 self.tts
.clone().into()
83 /// When the main rust parser encounters a syntax-extension invocation, it
84 /// parses the arguments to the invocation as a token-tree. This is a very
85 /// loose structure, such that all sorts of different AST-fragments can
86 /// be passed to syntax extensions using a uniform type.
88 /// If the syntax extension is an MBE macro, it will attempt to match its
89 /// LHS token tree against the provided token tree, and if it finds a
90 /// match, will transcribe the RHS token tree, splicing in any captured
91 /// `macro_parser::matched_nonterminals` into the `SubstNt`s it finds.
93 /// The RHS of an MBE macro is the only place `SubstNt`s are substituted.
94 /// Nothing special happens to misnamed or misplaced `SubstNt`s.
95 #[derive(Debug, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
98 Token(Span
, token
::Token
),
99 /// A delimited sequence of token trees
100 Delimited(Span
, Delimited
),
104 /// Use this token tree as a matcher to parse given tts.
105 pub fn parse(cx
: &base
::ExtCtxt
, mtch
: &[quoted
::TokenTree
], tts
: TokenStream
)
106 -> macro_parser
::NamedParseResult
{
107 // `None` is because we're not interpolating
108 let directory
= Directory
{
109 path
: cx
.current_expansion
.module
.directory
.clone(),
110 ownership
: cx
.current_expansion
.directory_ownership
,
112 macro_parser
::parse(cx
.parse_sess(), tts
, mtch
, Some(directory
), true)
115 /// Check if this TokenTree is equal to the other, regardless of span information.
116 pub fn eq_unspanned(&self, other
: &TokenTree
) -> bool
{
117 match (self, other
) {
118 (&TokenTree
::Token(_
, ref tk
), &TokenTree
::Token(_
, ref tk2
)) => tk
== tk2
,
119 (&TokenTree
::Delimited(_
, ref dl
), &TokenTree
::Delimited(_
, ref dl2
)) => {
120 dl
.delim
== dl2
.delim
&&
121 dl
.stream().trees().zip(dl2
.stream().trees()).all(|(tt
, tt2
)| tt
.eq_unspanned(&tt2
))
127 /// Retrieve the TokenTree's span.
128 pub fn span(&self) -> Span
{
130 TokenTree
::Token(sp
, _
) | TokenTree
::Delimited(sp
, _
) => sp
,
134 /// Modify the `TokenTree`'s span inplace.
135 pub fn set_span(&mut self, span
: Span
) {
137 TokenTree
::Token(ref mut sp
, _
) | TokenTree
::Delimited(ref mut sp
, _
) => {
143 /// Indicates if the stream is a token that is equal to the provided token.
144 pub fn eq_token(&self, t
: Token
) -> bool
{
146 TokenTree
::Token(_
, ref tk
) => *tk
== t
,
151 pub fn joint(self) -> TokenStream
{
152 TokenStream { kind: TokenStreamKind::JointTree(self) }
158 /// A `TokenStream` is an abstract sequence of tokens, organized into `TokenTree`s.
159 /// The goal is for procedural macros to work with `TokenStream`s and `TokenTree`s
160 /// instead of a representation of the abstract syntax tree.
161 /// Today's `TokenTree`s can still contain AST via `Token::Interpolated` for back-compat.
162 #[derive(Clone, Debug)]
163 pub struct TokenStream
{
164 kind
: TokenStreamKind
,
167 #[derive(Clone, Debug)]
168 enum TokenStreamKind
{
171 JointTree(TokenTree
),
172 Stream(RcSlice
<TokenStream
>),
175 impl From
<TokenTree
> for TokenStream
{
176 fn from(tt
: TokenTree
) -> TokenStream
{
177 TokenStream { kind: TokenStreamKind::Tree(tt) }
181 impl From
<Token
> for TokenStream
{
182 fn from(token
: Token
) -> TokenStream
{
183 TokenTree
::Token(DUMMY_SP
, token
).into()
187 impl<T
: Into
<TokenStream
>> iter
::FromIterator
<T
> for TokenStream
{
188 fn from_iter
<I
: IntoIterator
<Item
= T
>>(iter
: I
) -> Self {
189 TokenStream
::concat(iter
.into_iter().map(Into
::into
).collect
::<Vec
<_
>>())
193 impl Eq
for TokenStream {}
195 impl PartialEq
<TokenStream
> for TokenStream
{
196 fn eq(&self, other
: &TokenStream
) -> bool
{
197 self.trees().eq(other
.trees())
202 pub fn len(&self) -> usize {
203 if let TokenStreamKind
::Stream(ref slice
) = self.kind
{
210 pub fn empty() -> TokenStream
{
211 TokenStream { kind: TokenStreamKind::Empty }
214 pub fn is_empty(&self) -> bool
{
216 TokenStreamKind
::Empty
=> true,
221 pub fn concat(mut streams
: Vec
<TokenStream
>) -> TokenStream
{
222 match streams
.len() {
223 0 => TokenStream
::empty(),
224 1 => streams
.pop().unwrap(),
225 _
=> TokenStream
::concat_rc_slice(RcSlice
::new(streams
)),
229 fn concat_rc_slice(streams
: RcSlice
<TokenStream
>) -> TokenStream
{
230 TokenStream { kind: TokenStreamKind::Stream(streams) }
233 pub fn trees(&self) -> Cursor
{
234 self.clone().into_trees()
237 pub fn into_trees(self) -> Cursor
{
241 /// Compares two TokenStreams, checking equality without regarding span information.
242 pub fn eq_unspanned(&self, other
: &TokenStream
) -> bool
{
243 for (t1
, t2
) in self.trees().zip(other
.trees()) {
244 if !t1
.eq_unspanned(&t2
) {
251 /// Precondition: `self` consists of a single token tree.
252 /// Returns true if the token tree is a joint operation w.r.t. `proc_macro::TokenNode`.
253 pub fn as_tree(self) -> (TokenTree
, bool
/* joint? */) {
255 TokenStreamKind
::Tree(tree
) => (tree
, false),
256 TokenStreamKind
::JointTree(tree
) => (tree
, true),
261 pub fn map_enumerated
<F
: FnMut(usize, TokenTree
) -> TokenTree
>(self, mut f
: F
) -> TokenStream
{
262 let mut trees
= self.into_trees();
263 let mut result
= Vec
::new();
265 while let Some(stream
) = trees
.next_as_stream() {
266 result
.push(match stream
.kind
{
267 TokenStreamKind
::Tree(tree
) => f(i
, tree
).into(),
268 TokenStreamKind
::JointTree(tree
) => f(i
, tree
).joint(),
273 TokenStream
::concat(result
)
276 pub fn map
<F
: FnMut(TokenTree
) -> TokenTree
>(self, mut f
: F
) -> TokenStream
{
277 let mut trees
= self.into_trees();
278 let mut result
= Vec
::new();
279 while let Some(stream
) = trees
.next_as_stream() {
280 result
.push(match stream
.kind
{
281 TokenStreamKind
::Tree(tree
) => f(tree
).into(),
282 TokenStreamKind
::JointTree(tree
) => f(tree
).joint(),
286 TokenStream
::concat(result
)
289 fn first_tree_and_joint(&self) -> Option
<(TokenTree
, bool
)> {
291 TokenStreamKind
::Empty
=> None
,
292 TokenStreamKind
::Tree(ref tree
) => Some((tree
.clone(), false)),
293 TokenStreamKind
::JointTree(ref tree
) => Some((tree
.clone(), true)),
294 TokenStreamKind
::Stream(ref stream
) => stream
.first().unwrap().first_tree_and_joint(),
298 fn last_tree_if_joint(&self) -> Option
<TokenTree
> {
300 TokenStreamKind
::Empty
| TokenStreamKind
::Tree(..) => None
,
301 TokenStreamKind
::JointTree(ref tree
) => Some(tree
.clone()),
302 TokenStreamKind
::Stream(ref stream
) => stream
.last().unwrap().last_tree_if_joint(),
307 pub struct TokenStreamBuilder(Vec
<TokenStream
>);
309 impl TokenStreamBuilder
{
310 pub fn new() -> TokenStreamBuilder
{
311 TokenStreamBuilder(Vec
::new())
314 pub fn push
<T
: Into
<TokenStream
>>(&mut self, stream
: T
) {
315 let stream
= stream
.into();
316 let last_tree_if_joint
= self.0.last().and_then(TokenStream
::last_tree_if_joint
);
317 if let Some(TokenTree
::Token(last_span
, last_tok
)) = last_tree_if_joint
{
318 if let Some((TokenTree
::Token(span
, tok
), is_joint
)) = stream
.first_tree_and_joint() {
319 if let Some(glued_tok
) = last_tok
.glue(tok
) {
320 let last_stream
= self.0.pop().unwrap();
321 self.push_all_but_last_tree(&last_stream
);
322 let glued_span
= last_span
.to(span
);
323 let glued_tt
= TokenTree
::Token(glued_span
, glued_tok
);
324 let glued_tokenstream
= if is_joint
{
329 self.0.push(glued_tokenstream
);
330 self.push_all_but_first_tree(&stream
);
338 pub fn add
<T
: Into
<TokenStream
>>(mut self, stream
: T
) -> Self {
343 pub fn build(self) -> TokenStream
{
344 TokenStream
::concat(self.0)
347 fn push_all_but_last_tree(&mut self, stream
: &TokenStream
) {
348 if let TokenStreamKind
::Stream(ref streams
) = stream
.kind
{
349 let len
= streams
.len();
352 2 => self.0.push(streams
[0].clone().into()),
353 _
=> self.0.push(TokenStream
::concat_rc_slice(streams
.sub_slice(0 .. len
- 1))),
355 self.push_all_but_last_tree(&streams
[len
- 1])
359 fn push_all_but_first_tree(&mut self, stream
: &TokenStream
) {
360 if let TokenStreamKind
::Stream(ref streams
) = stream
.kind
{
361 let len
= streams
.len();
364 2 => self.0.push(streams
[1].clone().into()),
365 _
=> self.0.push(TokenStream
::concat_rc_slice(streams
.sub_slice(1 .. len
))),
367 self.push_all_but_first_tree(&streams
[0])
373 pub struct Cursor(CursorKind
);
378 Tree(TokenTree
, bool
/* consumed? */),
379 JointTree(TokenTree
, bool
/* consumed? */),
380 Stream(StreamCursor
),
384 struct StreamCursor
{
385 stream
: RcSlice
<TokenStream
>,
387 stack
: Vec
<(RcSlice
<TokenStream
>, usize)>,
391 fn new(stream
: RcSlice
<TokenStream
>) -> Self {
392 StreamCursor { stream: stream, index: 0, stack: Vec::new() }
395 fn next_as_stream(&mut self) -> Option
<TokenStream
> {
397 if self.index
< self.stream
.len() {
399 let next
= self.stream
[self.index
- 1].clone();
401 TokenStreamKind
::Tree(..) | TokenStreamKind
::JointTree(..) => return Some(next
),
402 TokenStreamKind
::Stream(stream
) => self.insert(stream
),
403 TokenStreamKind
::Empty
=> {}
405 } else if let Some((stream
, index
)) = self.stack
.pop() {
406 self.stream
= stream
;
414 fn insert(&mut self, stream
: RcSlice
<TokenStream
>) {
415 self.stack
.push((mem
::replace(&mut self.stream
, stream
),
416 mem
::replace(&mut self.index
, 0)));
420 impl Iterator
for Cursor
{
421 type Item
= TokenTree
;
423 fn next(&mut self) -> Option
<TokenTree
> {
424 self.next_as_stream().map(|stream
| match stream
.kind
{
425 TokenStreamKind
::Tree(tree
) | TokenStreamKind
::JointTree(tree
) => tree
,
432 fn new(stream
: TokenStream
) -> Self {
433 Cursor(match stream
.kind
{
434 TokenStreamKind
::Empty
=> CursorKind
::Empty
,
435 TokenStreamKind
::Tree(tree
) => CursorKind
::Tree(tree
, false),
436 TokenStreamKind
::JointTree(tree
) => CursorKind
::JointTree(tree
, false),
437 TokenStreamKind
::Stream(stream
) => CursorKind
::Stream(StreamCursor
::new(stream
)),
441 pub fn next_as_stream(&mut self) -> Option
<TokenStream
> {
442 let (stream
, consumed
) = match self.0 {
443 CursorKind
::Tree(ref tree
, ref mut consumed @
false) =>
444 (tree
.clone().into(), consumed
),
445 CursorKind
::JointTree(ref tree
, ref mut consumed @
false) =>
446 (tree
.clone().joint(), consumed
),
447 CursorKind
::Stream(ref mut cursor
) => return cursor
.next_as_stream(),
455 pub fn insert(&mut self, stream
: TokenStream
) {
457 _
if stream
.is_empty() => return,
458 CursorKind
::Empty
=> *self = stream
.trees(),
459 CursorKind
::Tree(_
, consumed
) | CursorKind
::JointTree(_
, consumed
) => {
460 *self = TokenStream
::concat(vec
![self.original_stream(), stream
]).trees();
465 CursorKind
::Stream(ref mut cursor
) => {
466 cursor
.insert(ThinTokenStream
::from(stream
).0.unwrap
());
471 pub fn original_stream(&self) -> TokenStream
{
473 CursorKind
::Empty
=> TokenStream
::empty(),
474 CursorKind
::Tree(ref tree
, _
) => tree
.clone().into(),
475 CursorKind
::JointTree(ref tree
, _
) => tree
.clone().joint(),
476 CursorKind
::Stream(ref cursor
) => TokenStream
::concat_rc_slice({
477 cursor
.stack
.get(0).cloned().map(|(stream
, _
)| stream
)
478 .unwrap_or(cursor
.stream
.clone())
483 pub fn look_ahead(&self, n
: usize) -> Option
<TokenTree
> {
484 fn look_ahead(streams
: &[TokenStream
], mut n
: usize) -> Result
<TokenTree
, usize> {
485 for stream
in streams
{
486 n
= match stream
.kind
{
487 TokenStreamKind
::Tree(ref tree
) | TokenStreamKind
::JointTree(ref tree
)
488 if n
== 0 => return Ok(tree
.clone()),
489 TokenStreamKind
::Tree(..) | TokenStreamKind
::JointTree(..) => n
- 1,
490 TokenStreamKind
::Stream(ref stream
) => match look_ahead(stream
, n
) {
491 Ok(tree
) => return Ok(tree
),
502 CursorKind
::Tree(_
, true) |
503 CursorKind
::JointTree(_
, true) => Err(n
),
504 CursorKind
::Tree(ref tree
, false) |
505 CursorKind
::JointTree(ref tree
, false) => look_ahead(&[tree
.clone().into()], n
),
506 CursorKind
::Stream(ref cursor
) => {
507 look_ahead(&cursor
.stream
[cursor
.index
..], n
).or_else(|mut n
| {
508 for &(ref stream
, index
) in cursor
.stack
.iter().rev() {
509 n
= match look_ahead(&stream
[index
..], n
) {
510 Ok(tree
) => return Ok(tree
),
522 /// The `TokenStream` type is large enough to represent a single `TokenTree` without allocation.
523 /// `ThinTokenStream` is smaller, but needs to allocate to represent a single `TokenTree`.
524 /// We must use `ThinTokenStream` in `TokenTree::Delimited` to avoid infinite size due to recursion.
525 #[derive(Debug, Clone)]
526 pub struct ThinTokenStream(Option
<RcSlice
<TokenStream
>>);
528 impl From
<TokenStream
> for ThinTokenStream
{
529 fn from(stream
: TokenStream
) -> ThinTokenStream
{
530 ThinTokenStream(match stream
.kind
{
531 TokenStreamKind
::Empty
=> None
,
532 TokenStreamKind
::Tree(tree
) => Some(RcSlice
::new(vec
![tree
.into()])),
533 TokenStreamKind
::JointTree(tree
) => Some(RcSlice
::new(vec
![tree
.joint()])),
534 TokenStreamKind
::Stream(stream
) => Some(stream
),
539 impl From
<ThinTokenStream
> for TokenStream
{
540 fn from(stream
: ThinTokenStream
) -> TokenStream
{
541 stream
.0.map(TokenStream
::concat_rc_slice
).unwrap_or_else(TokenStream
::empty
)
545 impl Eq
for ThinTokenStream {}
547 impl PartialEq
<ThinTokenStream
> for ThinTokenStream
{
548 fn eq(&self, other
: &ThinTokenStream
) -> bool
{
549 TokenStream
::from(self.clone()) == TokenStream
::from(other
.clone())
553 impl fmt
::Display
for TokenStream
{
554 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
555 f
.write_str(&pprust
::tokens_to_string(self.clone()))
559 impl Encodable
for TokenStream
{
560 fn encode
<E
: Encoder
>(&self, encoder
: &mut E
) -> Result
<(), E
::Error
> {
561 self.trees().collect
::<Vec
<_
>>().encode(encoder
)
565 impl Decodable
for TokenStream
{
566 fn decode
<D
: Decoder
>(decoder
: &mut D
) -> Result
<TokenStream
, D
::Error
> {
567 Vec
::<TokenTree
>::decode(decoder
).map(|vec
| vec
.into_iter().collect())
571 impl Hash
for TokenStream
{
572 fn hash
<H
: hash
::Hasher
>(&self, state
: &mut H
) {
573 for tree
in self.trees() {
579 impl Encodable
for ThinTokenStream
{
580 fn encode
<E
: Encoder
>(&self, encoder
: &mut E
) -> Result
<(), E
::Error
> {
581 TokenStream
::from(self.clone()).encode(encoder
)
585 impl Decodable
for ThinTokenStream
{
586 fn decode
<D
: Decoder
>(decoder
: &mut D
) -> Result
<ThinTokenStream
, D
::Error
> {
587 TokenStream
::decode(decoder
).map(Into
::into
)
591 impl Hash
for ThinTokenStream
{
592 fn hash
<H
: hash
::Hasher
>(&self, state
: &mut H
) {
593 TokenStream
::from(self.clone()).hash(state
);
601 use syntax
::ast
::Ident
;
602 use syntax_pos
::{Span, BytePos, NO_EXPANSION}
;
603 use parse
::token
::Token
;
604 use util
::parser_testing
::string_to_stream
;
606 fn string_to_ts(string
: &str) -> TokenStream
{
607 string_to_stream(string
.to_owned())
610 fn sp(a
: u32, b
: u32) -> Span
{
611 Span
::new(BytePos(a
), BytePos(b
), NO_EXPANSION
)
616 let test_res
= string_to_ts("foo::bar::baz");
617 let test_fst
= string_to_ts("foo::bar");
618 let test_snd
= string_to_ts("::baz");
619 let eq_res
= TokenStream
::concat(vec
![test_fst
, test_snd
]);
620 assert_eq
!(test_res
.trees().count(), 5);
621 assert_eq
!(eq_res
.trees().count(), 5);
622 assert_eq
!(test_res
.eq_unspanned(&eq_res
), true);
626 fn test_to_from_bijection() {
627 let test_start
= string_to_ts("foo::bar(baz)");
628 let test_end
= test_start
.trees().collect();
629 assert_eq
!(test_start
, test_end
)
634 let test_res
= string_to_ts("foo");
635 let test_eqs
= string_to_ts("foo");
636 assert_eq
!(test_res
, test_eqs
)
641 let test_res
= string_to_ts("::bar::baz");
642 let test_eqs
= string_to_ts("::bar::baz");
643 assert_eq
!(test_res
, test_eqs
)
648 let test_res
= string_to_ts("");
649 let test_eqs
= string_to_ts("");
650 assert_eq
!(test_res
, test_eqs
)
655 let test_res
= string_to_ts("::bar::baz");
656 let test_eqs
= string_to_ts("bar::baz");
657 assert_eq
!(test_res
== test_eqs
, false)
662 let test_res
= string_to_ts("(bar,baz)");
663 let test_eqs
= string_to_ts("bar,baz");
664 assert_eq
!(test_res
== test_eqs
, false)
669 let test0
: TokenStream
= Vec
::<TokenTree
>::new().into_iter().collect();
670 let test1
: TokenStream
=
671 TokenTree
::Token(sp(0, 1), Token
::Ident(Ident
::from_str("a"))).into();
672 let test2
= string_to_ts("foo(bar::baz)");
674 assert_eq
!(test0
.is_empty(), true);
675 assert_eq
!(test1
.is_empty(), false);
676 assert_eq
!(test2
.is_empty(), false);
680 fn test_dotdotdot() {
681 let mut builder
= TokenStreamBuilder
::new();
682 builder
.push(TokenTree
::Token(sp(0, 1), Token
::Dot
).joint());
683 builder
.push(TokenTree
::Token(sp(1, 2), Token
::Dot
).joint());
684 builder
.push(TokenTree
::Token(sp(2, 3), Token
::Dot
));
685 let stream
= builder
.build();
686 assert
!(stream
.eq_unspanned(&string_to_ts("...")));
687 assert_eq
!(stream
.trees().count(), 1);