src/libsyntax/tokenstream.rs

   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
  11 //! # Token Streams
  12 //!
  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.
  16 //!
  17 //! ## Ownership
  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.
  24
  25 use syntax_pos::{BytePos, Mark, Span, DUMMY_SP};
  26 use ext::base;
  27 use ext::tt::{macro_parser, quoted};
  28 use parse::Directory;
  29 use parse::token::{self, DelimToken, Token};
  30 use print::pprust;
  31 use serialize::{Decoder, Decodable, Encoder, Encodable};
  32 use util::RcVec;
  33
  34 use std::borrow::Cow;
  35 use std::{fmt, iter, mem};
  36
  37 /// A delimited sequence of token trees
  38 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, Debug)]
  39 pub struct Delimited {
  40     /// The type of delimiter
  41     pub delim: DelimToken,
  42     /// The delimited sequence of token trees
  43     pub tts: ThinTokenStream,
  44 }
  45
  46 impl Delimited {
  47     /// Returns the opening delimiter as a token.
  48     pub fn open_token(&self) -> token::Token {
  49         token::OpenDelim(self.delim)
  50     }
  51
  52     /// Returns the closing delimiter as a token.
  53     pub fn close_token(&self) -> token::Token {
  54         token::CloseDelim(self.delim)
  55     }
  56
  57     /// Returns the opening delimiter as a token tree.
  58     pub fn open_tt(&self, span: Span) -> TokenTree {
  59         let open_span = if span.is_dummy() {
  60             span
  61         } else {
  62             span.with_hi(span.lo() + BytePos(self.delim.len() as u32))
  63         };
  64         TokenTree::Token(open_span, self.open_token())
  65     }
  66
  67     /// Returns the closing delimiter as a token tree.
  68     pub fn close_tt(&self, span: Span) -> TokenTree {
  69         let close_span = if span.is_dummy() {
  70             span
  71         } else {
  72             span.with_lo(span.hi() - BytePos(self.delim.len() as u32))
  73         };
  74         TokenTree::Token(close_span, self.close_token())
  75     }
  76
  77     /// Returns the token trees inside the delimiters.
  78     pub fn stream(&self) -> TokenStream {
  79         self.tts.clone().into()
  80     }
  81 }
  82
  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.
  87 ///
  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.
  92 ///
  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, RustcEncodable, RustcDecodable)]
  96 pub enum TokenTree {
  97     /// A single token
  98     Token(Span, token::Token),
  99     /// A delimited sequence of token trees
 100     Delimited(DelimSpan, Delimited),
 101 }
 102
 103 impl TokenTree {
 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: Cow::from(cx.current_expansion.module.directory.as_path()),
 110             ownership: cx.current_expansion.directory_ownership,
 111         };
 112         macro_parser::parse(cx.parse_sess(), tts, mtch, Some(directory), true)
 113     }
 114
 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().eq_unspanned(&dl2.stream())
 122             }
 123             (_, _) => false,
 124         }
 125     }
 126
 127     // See comments in `interpolated_to_tokenstream` for why we care about
 128     // *probably* equal here rather than actual equality
 129     //
 130     // This is otherwise the same as `eq_unspanned`, only recursing with a
 131     // different method.
 132     pub fn probably_equal_for_proc_macro(&self, other: &TokenTree) -> bool {
 133         match (self, other) {
 134             (&TokenTree::Token(_, ref tk), &TokenTree::Token(_, ref tk2)) => {
 135                 tk.probably_equal_for_proc_macro(tk2)
 136             }
 137             (&TokenTree::Delimited(_, ref dl), &TokenTree::Delimited(_, ref dl2)) => {
 138                 dl.delim == dl2.delim &&
 139                 dl.stream().probably_equal_for_proc_macro(&dl2.stream())
 140             }
 141             (_, _) => false,
 142         }
 143     }
 144
 145     /// Retrieve the TokenTree's span.
 146     pub fn span(&self) -> Span {
 147         match *self {
 148             TokenTree::Token(sp, _) => sp,
 149             TokenTree::Delimited(sp, _) => sp.entire(),
 150         }
 151     }
 152
 153     /// Modify the `TokenTree`'s span in-place.
 154     pub fn set_span(&mut self, span: Span) {
 155         match *self {
 156             TokenTree::Token(ref mut sp, _) => *sp = span,
 157             TokenTree::Delimited(ref mut sp, _) => *sp = DelimSpan::from_single(span),
 158         }
 159     }
 160
 161     /// Indicates if the stream is a token that is equal to the provided token.
 162     pub fn eq_token(&self, t: Token) -> bool {
 163         match *self {
 164             TokenTree::Token(_, ref tk) => *tk == t,
 165             _ => false,
 166         }
 167     }
 168
 169     pub fn joint(self) -> TokenStream {
 170         TokenStream { kind: TokenStreamKind::JointTree(self) }
 171     }
 172 }
 173
 174 /// # Token Streams
 175 ///
 176 /// A `TokenStream` is an abstract sequence of tokens, organized into `TokenTree`s.
 177 /// The goal is for procedural macros to work with `TokenStream`s and `TokenTree`s
 178 /// instead of a representation of the abstract syntax tree.
 179 /// Today's `TokenTree`s can still contain AST via `Token::Interpolated` for back-compat.
 180 #[derive(Clone, Debug)]
 181 pub struct TokenStream {
 182     kind: TokenStreamKind,
 183 }
 184
 185 impl TokenStream {
 186     /// Given a `TokenStream` with a `Stream` of only two arguments, return a new `TokenStream`
 187     /// separating the two arguments with a comma for diagnostic suggestions.
 188     pub(crate) fn add_comma(&self) -> Option<(TokenStream, Span)> {
 189         // Used to suggest if a user writes `foo!(a b);`
 190         if let TokenStreamKind::Stream(ref slice) = self.kind {
 191             let mut suggestion = None;
 192             let mut iter = slice.iter().enumerate().peekable();
 193             while let Some((pos, ts)) = iter.next() {
 194                 if let Some((_, next)) = iter.peek() {
 195                     let sp = match (&ts.kind, &next.kind) {
 196                         (TokenStreamKind::Tree(TokenTree::Token(_, token::Token::Comma)), _) |
 197                         (_, TokenStreamKind::Tree(TokenTree::Token(_, token::Token::Comma))) => {
 198                             continue;
 199                         }
 200                         (TokenStreamKind::Tree(TokenTree::Token(sp, _)), _) => *sp,
 201                         (TokenStreamKind::Tree(TokenTree::Delimited(sp, _)), _) => sp.entire(),
 202                         _ => continue,
 203                     };
 204                     let sp = sp.shrink_to_hi();
 205                     let comma = TokenStream {
 206                         kind: TokenStreamKind::Tree(TokenTree::Token(sp, token::Comma)),
 207                     };
 208                     suggestion = Some((pos, comma, sp));
 209                 }
 210             }
 211             if let Some((pos, comma, sp)) = suggestion {
 212                 let mut new_slice = vec![];
 213                 let parts = slice.split_at(pos + 1);
 214                 new_slice.extend_from_slice(parts.0);
 215                 new_slice.push(comma);
 216                 new_slice.extend_from_slice(parts.1);
 217                 let slice = RcVec::new(new_slice);
 218                 return Some((TokenStream { kind: TokenStreamKind::Stream(slice) }, sp));
 219             }
 220         }
 221         None
 222     }
 223 }
 224
 225 #[derive(Clone, Debug)]
 226 enum TokenStreamKind {
 227     Empty,
 228     Tree(TokenTree),
 229     JointTree(TokenTree),
 230     Stream(RcVec<TokenStream>),
 231 }
 232
 233 impl From<TokenTree> for TokenStream {
 234     fn from(tt: TokenTree) -> TokenStream {
 235         TokenStream { kind: TokenStreamKind::Tree(tt) }
 236     }
 237 }
 238
 239 impl From<Token> for TokenStream {
 240     fn from(token: Token) -> TokenStream {
 241         TokenTree::Token(DUMMY_SP, token).into()
 242     }
 243 }
 244
 245 impl<T: Into<TokenStream>> iter::FromIterator<T> for TokenStream {
 246     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
 247         TokenStream::concat(iter.into_iter().map(Into::into).collect::<Vec<_>>())
 248     }
 249 }
 250
 251 impl Extend<TokenStream> for TokenStream {
 252     fn extend<I: IntoIterator<Item = TokenStream>>(&mut self, iter: I) {
 253         let iter = iter.into_iter();
 254         let kind = mem::replace(&mut self.kind, TokenStreamKind::Empty);
 255
 256         // Vector of token streams originally in self.
 257         let tts: Vec<TokenStream> = match kind {
 258             TokenStreamKind::Empty => {
 259                 let mut vec = Vec::new();
 260                 vec.reserve(iter.size_hint().0);
 261                 vec
 262             }
 263             TokenStreamKind::Tree(_) | TokenStreamKind::JointTree(_) => {
 264                 let mut vec = Vec::new();
 265                 vec.reserve(1 + iter.size_hint().0);
 266                 vec.push(TokenStream { kind });
 267                 vec
 268             }
 269             TokenStreamKind::Stream(rc_vec) => match RcVec::try_unwrap(rc_vec) {
 270                 Ok(mut vec) => {
 271                     // Extend in place using the existing capacity if possible.
 272                     // This is the fast path for libraries like `quote` that
 273                     // build a token stream.
 274                     vec.reserve(iter.size_hint().0);
 275                     vec
 276                 }
 277                 Err(rc_vec) => {
 278                     // Self is shared so we need to copy and extend that.
 279                     let mut vec = Vec::new();
 280                     vec.reserve(rc_vec.len() + iter.size_hint().0);
 281                     vec.extend_from_slice(&rc_vec);
 282                     vec
 283                 }
 284             }
 285         };
 286
 287         // Perform the extend, joining tokens as needed along the way.
 288         let mut builder = TokenStreamBuilder(tts);
 289         for stream in iter {
 290             builder.push(stream);
 291         }
 292
 293         // Build the resulting token stream. If it contains more than one token,
 294         // preserve capacity in the vector in anticipation of the caller
 295         // performing additional calls to extend.
 296         let mut tts = builder.0;
 297         *self = match tts.len() {
 298             0 => TokenStream::empty(),
 299             1 => tts.pop().unwrap(),
 300             _ => TokenStream::concat_rc_vec(RcVec::new_preserving_capacity(tts)),
 301         };
 302     }
 303 }
 304
 305 impl Eq for TokenStream {}
 306
 307 impl PartialEq<TokenStream> for TokenStream {
 308     fn eq(&self, other: &TokenStream) -> bool {
 309         self.trees().eq(other.trees())
 310     }
 311 }
 312
 313 impl TokenStream {
 314     pub fn len(&self) -> usize {
 315         if let TokenStreamKind::Stream(ref slice) = self.kind {
 316             slice.len()
 317         } else {
 318             0
 319         }
 320     }
 321
 322     pub fn empty() -> TokenStream {
 323         TokenStream { kind: TokenStreamKind::Empty }
 324     }
 325
 326     pub fn is_empty(&self) -> bool {
 327         match self.kind {
 328             TokenStreamKind::Empty => true,
 329             _ => false,
 330         }
 331     }
 332
 333     pub fn concat(mut streams: Vec<TokenStream>) -> TokenStream {
 334         match streams.len() {
 335             0 => TokenStream::empty(),
 336             1 => streams.pop().unwrap(),
 337             _ => TokenStream::concat_rc_vec(RcVec::new(streams)),
 338         }
 339     }
 340
 341     fn concat_rc_vec(streams: RcVec<TokenStream>) -> TokenStream {
 342         TokenStream { kind: TokenStreamKind::Stream(streams) }
 343     }
 344
 345     pub fn trees(&self) -> Cursor {
 346         self.clone().into_trees()
 347     }
 348
 349     pub fn into_trees(self) -> Cursor {
 350         Cursor::new(self)
 351     }
 352
 353     /// Compares two TokenStreams, checking equality without regarding span information.
 354     pub fn eq_unspanned(&self, other: &TokenStream) -> bool {
 355         let mut t1 = self.trees();
 356         let mut t2 = other.trees();
 357         for (t1, t2) in t1.by_ref().zip(t2.by_ref()) {
 358             if !t1.eq_unspanned(&t2) {
 359                 return false;
 360             }
 361         }
 362         t1.next().is_none() && t2.next().is_none()
 363     }
 364
 365     // See comments in `interpolated_to_tokenstream` for why we care about
 366     // *probably* equal here rather than actual equality
 367     //
 368     // This is otherwise the same as `eq_unspanned`, only recursing with a
 369     // different method.
 370     pub fn probably_equal_for_proc_macro(&self, other: &TokenStream) -> bool {
 371         // When checking for `probably_eq`, we ignore certain tokens that aren't
 372         // preserved in the AST. Because they are not preserved, the pretty
 373         // printer arbitrarily adds or removes them when printing as token
 374         // streams, making a comparison between a token stream generated from an
 375         // AST and a token stream which was parsed into an AST more reliable.
 376         fn semantic_tree(tree: &TokenTree) -> bool {
 377             match tree {
 378                 // The pretty printer tends to add trailing commas to
 379                 // everything, and in particular, after struct fields.
 380                 | TokenTree::Token(_, Token::Comma)
 381                 // The pretty printer emits `NoDelim` as whitespace.
 382                 | TokenTree::Token(_, Token::OpenDelim(DelimToken::NoDelim))
 383                 | TokenTree::Token(_, Token::CloseDelim(DelimToken::NoDelim))
 384                 // The pretty printer collapses many semicolons into one.
 385                 | TokenTree::Token(_, Token::Semi)
 386                 // The pretty printer collapses whitespace arbitrarily and can
 387                 // introduce whitespace from `NoDelim`.
 388                 | TokenTree::Token(_, Token::Whitespace) => false,
 389                 _ => true
 390             }
 391         }
 392
 393         let mut t1 = self.trees().filter(semantic_tree);
 394         let mut t2 = other.trees().filter(semantic_tree);
 395         for (t1, t2) in t1.by_ref().zip(t2.by_ref()) {
 396             if !t1.probably_equal_for_proc_macro(&t2) {
 397                 return false;
 398             }
 399         }
 400         t1.next().is_none() && t2.next().is_none()
 401     }
 402
 403     /// Precondition: `self` consists of a single token tree.
 404     /// Returns true if the token tree is a joint operation w.r.t. `proc_macro::TokenNode`.
 405     pub fn as_tree(self) -> (TokenTree, bool /* joint? */) {
 406         match self.kind {
 407             TokenStreamKind::Tree(tree) => (tree, false),
 408             TokenStreamKind::JointTree(tree) => (tree, true),
 409             _ => unreachable!(),
 410         }
 411     }
 412
 413     pub fn map_enumerated<F: FnMut(usize, TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream {
 414         let mut trees = self.into_trees();
 415         let mut result = Vec::new();
 416         let mut i = 0;
 417         while let Some(stream) = trees.next_as_stream() {
 418             result.push(match stream.kind {
 419                 TokenStreamKind::Tree(tree) => f(i, tree).into(),
 420                 TokenStreamKind::JointTree(tree) => f(i, tree).joint(),
 421                 _ => unreachable!()
 422             });
 423             i += 1;
 424         }
 425         TokenStream::concat(result)
 426     }
 427
 428     pub fn map<F: FnMut(TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream {
 429         let mut trees = self.into_trees();
 430         let mut result = Vec::new();
 431         while let Some(stream) = trees.next_as_stream() {
 432             result.push(match stream.kind {
 433                 TokenStreamKind::Tree(tree) => f(tree).into(),
 434                 TokenStreamKind::JointTree(tree) => f(tree).joint(),
 435                 _ => unreachable!()
 436             });
 437         }
 438         TokenStream::concat(result)
 439     }
 440
 441     fn first_tree_and_joint(&self) -> Option<(TokenTree, bool)> {
 442         match self.kind {
 443             TokenStreamKind::Empty => None,
 444             TokenStreamKind::Tree(ref tree) => Some((tree.clone(), false)),
 445             TokenStreamKind::JointTree(ref tree) => Some((tree.clone(), true)),
 446             TokenStreamKind::Stream(ref stream) => stream.first().unwrap().first_tree_and_joint(),
 447         }
 448     }
 449
 450     fn last_tree_if_joint(&self) -> Option<TokenTree> {
 451         match self.kind {
 452             TokenStreamKind::Empty | TokenStreamKind::Tree(..) => None,
 453             TokenStreamKind::JointTree(ref tree) => Some(tree.clone()),
 454             TokenStreamKind::Stream(ref stream) => stream.last().unwrap().last_tree_if_joint(),
 455         }
 456     }
 457 }
 458
 459 #[derive(Clone)]
 460 pub struct TokenStreamBuilder(Vec<TokenStream>);
 461
 462 impl TokenStreamBuilder {
 463     pub fn new() -> TokenStreamBuilder {
 464         TokenStreamBuilder(Vec::new())
 465     }
 466
 467     pub fn push<T: Into<TokenStream>>(&mut self, stream: T) {
 468         let stream = stream.into();
 469         let last_tree_if_joint = self.0.last().and_then(TokenStream::last_tree_if_joint);
 470         if let Some(TokenTree::Token(last_span, last_tok)) = last_tree_if_joint {
 471             if let Some((TokenTree::Token(span, tok), is_joint)) = stream.first_tree_and_joint() {
 472                 if let Some(glued_tok) = last_tok.glue(tok) {
 473                     let last_stream = self.0.pop().unwrap();
 474                     self.push_all_but_last_tree(&last_stream);
 475                     let glued_span = last_span.to(span);
 476                     let glued_tt = TokenTree::Token(glued_span, glued_tok);
 477                     let glued_tokenstream = if is_joint {
 478                         glued_tt.joint()
 479                     } else {
 480                         glued_tt.into()
 481                     };
 482                     self.0.push(glued_tokenstream);
 483                     self.push_all_but_first_tree(&stream);
 484                     return
 485                 }
 486             }
 487         }
 488         self.0.push(stream);
 489     }
 490
 491     pub fn add<T: Into<TokenStream>>(mut self, stream: T) -> Self {
 492         self.push(stream);
 493         self
 494     }
 495
 496     pub fn build(self) -> TokenStream {
 497         TokenStream::concat(self.0)
 498     }
 499
 500     fn push_all_but_last_tree(&mut self, stream: &TokenStream) {
 501         if let TokenStreamKind::Stream(ref streams) = stream.kind {
 502             let len = streams.len();
 503             match len {
 504                 1 => {}
 505                 2 => self.0.push(streams[0].clone().into()),
 506                 _ => self.0.push(TokenStream::concat_rc_vec(streams.sub_slice(0 .. len - 1))),
 507             }
 508             self.push_all_but_last_tree(&streams[len - 1])
 509         }
 510     }
 511
 512     fn push_all_but_first_tree(&mut self, stream: &TokenStream) {
 513         if let TokenStreamKind::Stream(ref streams) = stream.kind {
 514             let len = streams.len();
 515             match len {
 516                 1 => {}
 517                 2 => self.0.push(streams[1].clone().into()),
 518                 _ => self.0.push(TokenStream::concat_rc_vec(streams.sub_slice(1 .. len))),
 519             }
 520             self.push_all_but_first_tree(&streams[0])
 521         }
 522     }
 523 }
 524
 525 #[derive(Clone)]
 526 pub struct Cursor(CursorKind);
 527
 528 #[derive(Clone)]
 529 enum CursorKind {
 530     Empty,
 531     Tree(TokenTree, bool /* consumed? */),
 532     JointTree(TokenTree, bool /* consumed? */),
 533     Stream(StreamCursor),
 534 }
 535
 536 #[derive(Clone)]
 537 struct StreamCursor {
 538     stream: RcVec<TokenStream>,
 539     index: usize,
 540     stack: Vec<(RcVec<TokenStream>, usize)>,
 541 }
 542
 543 impl StreamCursor {
 544     fn new(stream: RcVec<TokenStream>) -> Self {
 545         StreamCursor { stream: stream, index: 0, stack: Vec::new() }
 546     }
 547
 548     fn next_as_stream(&mut self) -> Option<TokenStream> {
 549         loop {
 550             if self.index < self.stream.len() {
 551                 self.index += 1;
 552                 let next = self.stream[self.index - 1].clone();
 553                 match next.kind {
 554                     TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => return Some(next),
 555                     TokenStreamKind::Stream(stream) => self.insert(stream),
 556                     TokenStreamKind::Empty => {}
 557                 }
 558             } else if let Some((stream, index)) = self.stack.pop() {
 559                 self.stream = stream;
 560                 self.index = index;
 561             } else {
 562                 return None;
 563             }
 564         }
 565     }
 566
 567     fn insert(&mut self, stream: RcVec<TokenStream>) {
 568         self.stack.push((mem::replace(&mut self.stream, stream),
 569                          mem::replace(&mut self.index, 0)));
 570     }
 571 }
 572
 573 impl Iterator for Cursor {
 574     type Item = TokenTree;
 575
 576     fn next(&mut self) -> Option<TokenTree> {
 577         self.next_as_stream().map(|stream| match stream.kind {
 578             TokenStreamKind::Tree(tree) | TokenStreamKind::JointTree(tree) => tree,
 579             _ => unreachable!()
 580         })
 581     }
 582 }
 583
 584 impl Cursor {
 585     fn new(stream: TokenStream) -> Self {
 586         Cursor(match stream.kind {
 587             TokenStreamKind::Empty => CursorKind::Empty,
 588             TokenStreamKind::Tree(tree) => CursorKind::Tree(tree, false),
 589             TokenStreamKind::JointTree(tree) => CursorKind::JointTree(tree, false),
 590             TokenStreamKind::Stream(stream) => CursorKind::Stream(StreamCursor::new(stream)),
 591         })
 592     }
 593
 594     pub fn next_as_stream(&mut self) -> Option<TokenStream> {
 595         let (stream, consumed) = match self.0 {
 596             CursorKind::Tree(ref tree, ref mut consumed @ false) =>
 597                 (tree.clone().into(), consumed),
 598             CursorKind::JointTree(ref tree, ref mut consumed @ false) =>
 599                 (tree.clone().joint(), consumed),
 600             CursorKind::Stream(ref mut cursor) => return cursor.next_as_stream(),
 601             _ => return None,
 602         };
 603
 604         *consumed = true;
 605         Some(stream)
 606     }
 607
 608     pub fn insert(&mut self, stream: TokenStream) {
 609         match self.0 {
 610             _ if stream.is_empty() => return,
 611             CursorKind::Empty => *self = stream.trees(),
 612             CursorKind::Tree(_, consumed) | CursorKind::JointTree(_, consumed) => {
 613                 *self = TokenStream::concat(vec![self.original_stream(), stream]).trees();
 614                 if consumed {
 615                     self.next();
 616                 }
 617             }
 618             CursorKind::Stream(ref mut cursor) => {
 619                 cursor.insert(ThinTokenStream::from(stream).0.unwrap());
 620             }
 621         }
 622     }
 623
 624     pub fn original_stream(&self) -> TokenStream {
 625         match self.0 {
 626             CursorKind::Empty => TokenStream::empty(),
 627             CursorKind::Tree(ref tree, _) => tree.clone().into(),
 628             CursorKind::JointTree(ref tree, _) => tree.clone().joint(),
 629             CursorKind::Stream(ref cursor) => TokenStream::concat_rc_vec({
 630                 cursor.stack.get(0).cloned().map(|(stream, _)| stream)
 631                     .unwrap_or_else(|| cursor.stream.clone())
 632             }),
 633         }
 634     }
 635
 636     pub fn look_ahead(&self, n: usize) -> Option<TokenTree> {
 637         fn look_ahead(streams: &[TokenStream], mut n: usize) -> Result<TokenTree, usize> {
 638             for stream in streams {
 639                 n = match stream.kind {
 640                     TokenStreamKind::Tree(ref tree) | TokenStreamKind::JointTree(ref tree)
 641                         if n == 0 => return Ok(tree.clone()),
 642                     TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => n - 1,
 643                     TokenStreamKind::Stream(ref stream) => match look_ahead(stream, n) {
 644                         Ok(tree) => return Ok(tree),
 645                         Err(n) => n,
 646                     },
 647                     _ => n,
 648                 };
 649             }
 650             Err(n)
 651         }
 652
 653         match self.0 {
 654             CursorKind::Empty |
 655             CursorKind::Tree(_, true) |
 656             CursorKind::JointTree(_, true) => Err(n),
 657             CursorKind::Tree(ref tree, false) |
 658             CursorKind::JointTree(ref tree, false) => look_ahead(&[tree.clone().into()], n),
 659             CursorKind::Stream(ref cursor) => {
 660                 look_ahead(&cursor.stream[cursor.index ..], n).or_else(|mut n| {
 661                     for &(ref stream, index) in cursor.stack.iter().rev() {
 662                         n = match look_ahead(&stream[index..], n) {
 663                             Ok(tree) => return Ok(tree),
 664                             Err(n) => n,
 665                         }
 666                     }
 667
 668                     Err(n)
 669                 })
 670             }
 671         }.ok()
 672     }
 673 }
 674
 675 /// The `TokenStream` type is large enough to represent a single `TokenTree` without allocation.
 676 /// `ThinTokenStream` is smaller, but needs to allocate to represent a single `TokenTree`.
 677 /// We must use `ThinTokenStream` in `TokenTree::Delimited` to avoid infinite size due to recursion.
 678 #[derive(Debug, Clone)]
 679 pub struct ThinTokenStream(Option<RcVec<TokenStream>>);
 680
 681 impl From<TokenStream> for ThinTokenStream {
 682     fn from(stream: TokenStream) -> ThinTokenStream {
 683         ThinTokenStream(match stream.kind {
 684             TokenStreamKind::Empty => None,
 685             TokenStreamKind::Tree(tree) => Some(RcVec::new(vec![tree.into()])),
 686             TokenStreamKind::JointTree(tree) => Some(RcVec::new(vec![tree.joint()])),
 687             TokenStreamKind::Stream(stream) => Some(stream),
 688         })
 689     }
 690 }
 691
 692 impl From<ThinTokenStream> for TokenStream {
 693     fn from(stream: ThinTokenStream) -> TokenStream {
 694         stream.0.map(TokenStream::concat_rc_vec).unwrap_or_else(TokenStream::empty)
 695     }
 696 }
 697
 698 impl Eq for ThinTokenStream {}
 699
 700 impl PartialEq<ThinTokenStream> for ThinTokenStream {
 701     fn eq(&self, other: &ThinTokenStream) -> bool {
 702         TokenStream::from(self.clone()) == TokenStream::from(other.clone())
 703     }
 704 }
 705
 706 impl fmt::Display for TokenStream {
 707     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 708         f.write_str(&pprust::tokens_to_string(self.clone()))
 709     }
 710 }
 711
 712 impl Encodable for TokenStream {
 713     fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
 714         self.trees().collect::<Vec<_>>().encode(encoder)
 715     }
 716 }
 717
 718 impl Decodable for TokenStream {
 719     fn decode<D: Decoder>(decoder: &mut D) -> Result<TokenStream, D::Error> {
 720         Vec::<TokenTree>::decode(decoder).map(|vec| vec.into_iter().collect())
 721     }
 722 }
 723
 724 impl Encodable for ThinTokenStream {
 725     fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
 726         TokenStream::from(self.clone()).encode(encoder)
 727     }
 728 }
 729
 730 impl Decodable for ThinTokenStream {
 731     fn decode<D: Decoder>(decoder: &mut D) -> Result<ThinTokenStream, D::Error> {
 732         TokenStream::decode(decoder).map(Into::into)
 733     }
 734 }
 735
 736 #[derive(Debug, Copy, Clone, PartialEq, RustcEncodable, RustcDecodable)]
 737 pub struct DelimSpan {
 738     pub open: Span,
 739     pub close: Span,
 740 }
 741
 742 impl DelimSpan {
 743     pub fn from_single(sp: Span) -> Self {
 744         DelimSpan {
 745             open: sp,
 746             close: sp,
 747         }
 748     }
 749
 750     pub fn from_pair(open: Span, close: Span) -> Self {
 751         DelimSpan { open, close }
 752     }
 753
 754     pub fn dummy() -> Self {
 755         Self::from_single(DUMMY_SP)
 756     }
 757
 758     pub fn entire(self) -> Span {
 759         self.open.with_hi(self.close.hi())
 760     }
 761
 762     pub fn apply_mark(self, mark: Mark) -> Self {
 763         DelimSpan {
 764             open: self.open.apply_mark(mark),
 765             close: self.close.apply_mark(mark),
 766         }
 767     }
 768 }
 769
 770 #[cfg(test)]
 771 mod tests {
 772     use super::*;
 773     use syntax::ast::Ident;
 774     use with_globals;
 775     use syntax_pos::{Span, BytePos, NO_EXPANSION};
 776     use parse::token::Token;
 777     use util::parser_testing::string_to_stream;
 778
 779     fn string_to_ts(string: &str) -> TokenStream {
 780         string_to_stream(string.to_owned())
 781     }
 782
 783     fn sp(a: u32, b: u32) -> Span {
 784         Span::new(BytePos(a), BytePos(b), NO_EXPANSION)
 785     }
 786
 787     #[test]
 788     fn test_concat() {
 789         with_globals(|| {
 790             let test_res = string_to_ts("foo::bar::baz");
 791             let test_fst = string_to_ts("foo::bar");
 792             let test_snd = string_to_ts("::baz");
 793             let eq_res = TokenStream::concat(vec![test_fst, test_snd]);
 794             assert_eq!(test_res.trees().count(), 5);
 795             assert_eq!(eq_res.trees().count(), 5);
 796             assert_eq!(test_res.eq_unspanned(&eq_res), true);
 797         })
 798     }
 799
 800     #[test]
 801     fn test_to_from_bijection() {
 802         with_globals(|| {
 803             let test_start = string_to_ts("foo::bar(baz)");
 804             let test_end = test_start.trees().collect();
 805             assert_eq!(test_start, test_end)
 806         })
 807     }
 808
 809     #[test]
 810     fn test_eq_0() {
 811         with_globals(|| {
 812             let test_res = string_to_ts("foo");
 813             let test_eqs = string_to_ts("foo");
 814             assert_eq!(test_res, test_eqs)
 815         })
 816     }
 817
 818     #[test]
 819     fn test_eq_1() {
 820         with_globals(|| {
 821             let test_res = string_to_ts("::bar::baz");
 822             let test_eqs = string_to_ts("::bar::baz");
 823             assert_eq!(test_res, test_eqs)
 824         })
 825     }
 826
 827     #[test]
 828     fn test_eq_3() {
 829         with_globals(|| {
 830             let test_res = string_to_ts("");
 831             let test_eqs = string_to_ts("");
 832             assert_eq!(test_res, test_eqs)
 833         })
 834     }
 835
 836     #[test]
 837     fn test_diseq_0() {
 838         with_globals(|| {
 839             let test_res = string_to_ts("::bar::baz");
 840             let test_eqs = string_to_ts("bar::baz");
 841             assert_eq!(test_res == test_eqs, false)
 842         })
 843     }
 844
 845     #[test]
 846     fn test_diseq_1() {
 847         with_globals(|| {
 848             let test_res = string_to_ts("(bar,baz)");
 849             let test_eqs = string_to_ts("bar,baz");
 850             assert_eq!(test_res == test_eqs, false)
 851         })
 852     }
 853
 854     #[test]
 855     fn test_is_empty() {
 856         with_globals(|| {
 857             let test0: TokenStream = Vec::<TokenTree>::new().into_iter().collect();
 858             let test1: TokenStream =
 859                 TokenTree::Token(sp(0, 1), Token::Ident(Ident::from_str("a"), false)).into();
 860             let test2 = string_to_ts("foo(bar::baz)");
 861
 862             assert_eq!(test0.is_empty(), true);
 863             assert_eq!(test1.is_empty(), false);
 864             assert_eq!(test2.is_empty(), false);
 865         })
 866     }
 867
 868     #[test]
 869     fn test_dotdotdot() {
 870         let mut builder = TokenStreamBuilder::new();
 871         builder.push(TokenTree::Token(sp(0, 1), Token::Dot).joint());
 872         builder.push(TokenTree::Token(sp(1, 2), Token::Dot).joint());
 873         builder.push(TokenTree::Token(sp(2, 3), Token::Dot));
 874         let stream = builder.build();
 875         assert!(stream.eq_unspanned(&string_to_ts("...")));
 876         assert_eq!(stream.trees().count(), 1);
 877     }
 878
 879     #[test]
 880     fn test_extend_empty() {
 881         with_globals(|| {
 882             // Append a token onto an empty token stream.
 883             let mut stream = TokenStream::empty();
 884             stream.extend(vec![string_to_ts("t")]);
 885
 886             let expected = string_to_ts("t");
 887             assert!(stream.eq_unspanned(&expected));
 888         });
 889     }
 890
 891     #[test]
 892     fn test_extend_nothing() {
 893         with_globals(|| {
 894             // Append nothing onto a token stream containing one token.
 895             let mut stream = string_to_ts("t");
 896             stream.extend(vec![]);
 897
 898             let expected = string_to_ts("t");
 899             assert!(stream.eq_unspanned(&expected));
 900         });
 901     }
 902
 903     #[test]
 904     fn test_extend_single() {
 905         with_globals(|| {
 906             // Append a token onto token stream containing a single token.
 907             let mut stream = string_to_ts("t1");
 908             stream.extend(vec![string_to_ts("t2")]);
 909
 910             let expected = string_to_ts("t1 t2");
 911             assert!(stream.eq_unspanned(&expected));
 912         });
 913     }
 914
 915     #[test]
 916     fn test_extend_in_place() {
 917         with_globals(|| {
 918             // Append a token onto token stream containing a reference counted
 919             // vec of tokens. The token stream has a reference count of 1 so
 920             // this can happen in place.
 921             let mut stream = string_to_ts("t1 t2");
 922             stream.extend(vec![string_to_ts("t3")]);
 923
 924             let expected = string_to_ts("t1 t2 t3");
 925             assert!(stream.eq_unspanned(&expected));
 926         });
 927     }
 928
 929     #[test]
 930     fn test_extend_copy() {
 931         with_globals(|| {
 932             // Append a token onto token stream containing a reference counted
 933             // vec of tokens. The token stream is shared so the extend takes
 934             // place on a copy.
 935             let mut stream = string_to_ts("t1 t2");
 936             let _incref = stream.clone();
 937             stream.extend(vec![string_to_ts("t3")]);
 938
 939             let expected = string_to_ts("t1 t2 t3");
 940             assert!(stream.eq_unspanned(&expected));
 941         });
 942     }
 943
 944     #[test]
 945     fn test_extend_no_join() {
 946         with_globals(|| {
 947             let first = TokenTree::Token(DUMMY_SP, Token::Dot);
 948             let second = TokenTree::Token(DUMMY_SP, Token::Dot);
 949
 950             // Append a dot onto a token stream containing a dot, but do not
 951             // join them.
 952             let mut stream = TokenStream::from(first);
 953             stream.extend(vec![TokenStream::from(second)]);
 954
 955             let expected = string_to_ts(". .");
 956             assert!(stream.eq_unspanned(&expected));
 957
 958             let unexpected = string_to_ts("..");
 959             assert!(!stream.eq_unspanned(&unexpected));
 960         });
 961     }
 962
 963     #[test]
 964     fn test_extend_join() {
 965         with_globals(|| {
 966             let first = TokenTree::Token(DUMMY_SP, Token::Dot).joint();
 967             let second = TokenTree::Token(DUMMY_SP, Token::Dot);
 968
 969             // Append a dot onto a token stream containing a dot, forming a
 970             // dotdot.
 971             let mut stream = first;
 972             stream.extend(vec![TokenStream::from(second)]);
 973
 974             let expected = string_to_ts("..");
 975             assert!(stream.eq_unspanned(&expected));
 976
 977             let unexpected = string_to_ts(". .");
 978             assert!(!stream.eq_unspanned(&unexpected));
 979         });
 980     }
 981 }