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, Span, DUMMY_SP};
  26 use ext::base;
  27 use ext::tt::{macro_parser, quoted};
  28 use parse::Directory;
  29 use parse::token::{self, 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: token::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(Span, 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, _) | TokenTree::Delimited(sp, _) => sp,
 149         }
 150     }
 151
 152     /// Modify the `TokenTree`'s span inplace.
 153     pub fn set_span(&mut self, span: Span) {
 154         match *self {
 155             TokenTree::Token(ref mut sp, _) | TokenTree::Delimited(ref mut sp, _) => {
 156                 *sp = span;
 157             }
 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                     match (ts, next) {
 196                         (TokenStream {
 197                             kind: TokenStreamKind::Tree(TokenTree::Token(_, token::Token::Comma))
 198                         }, _) |
 199                         (_, TokenStream {
 200                             kind: TokenStreamKind::Tree(TokenTree::Token(_, token::Token::Comma))
 201                         }) => {}
 202                         (TokenStream {
 203                             kind: TokenStreamKind::Tree(TokenTree::Token(sp, _))
 204                         }, _) |
 205                         (TokenStream {
 206                             kind: TokenStreamKind::Tree(TokenTree::Delimited(sp, _))
 207                         }, _) => {
 208                             let sp = sp.shrink_to_hi();
 209                             let comma = TokenStream {
 210                                 kind: TokenStreamKind::Tree(TokenTree::Token(sp, token::Comma)),
 211                             };
 212                             suggestion = Some((pos, comma, sp));
 213                         }
 214                         _ => {}
 215                     }
 216                 }
 217             }
 218             if let Some((pos, comma, sp)) = suggestion {
 219                 let mut new_slice = vec![];
 220                 let parts = slice.split_at(pos + 1);
 221                 new_slice.extend_from_slice(parts.0);
 222                 new_slice.push(comma);
 223                 new_slice.extend_from_slice(parts.1);
 224                 let slice = RcVec::new(new_slice);
 225                 return Some((TokenStream { kind: TokenStreamKind::Stream(slice) }, sp));
 226             }
 227         }
 228         None
 229     }
 230 }
 231
 232 #[derive(Clone, Debug)]
 233 enum TokenStreamKind {
 234     Empty,
 235     Tree(TokenTree),
 236     JointTree(TokenTree),
 237     Stream(RcVec<TokenStream>),
 238 }
 239
 240 impl From<TokenTree> for TokenStream {
 241     fn from(tt: TokenTree) -> TokenStream {
 242         TokenStream { kind: TokenStreamKind::Tree(tt) }
 243     }
 244 }
 245
 246 impl From<Token> for TokenStream {
 247     fn from(token: Token) -> TokenStream {
 248         TokenTree::Token(DUMMY_SP, token).into()
 249     }
 250 }
 251
 252 impl<T: Into<TokenStream>> iter::FromIterator<T> for TokenStream {
 253     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
 254         TokenStream::concat(iter.into_iter().map(Into::into).collect::<Vec<_>>())
 255     }
 256 }
 257
 258 impl Extend<TokenStream> for TokenStream {
 259     fn extend<I: IntoIterator<Item = TokenStream>>(&mut self, iter: I) {
 260         let iter = iter.into_iter();
 261         let kind = mem::replace(&mut self.kind, TokenStreamKind::Empty);
 262
 263         // Vector of token streams originally in self.
 264         let tts: Vec<TokenStream> = match kind {
 265             TokenStreamKind::Empty => {
 266                 let mut vec = Vec::new();
 267                 vec.reserve(iter.size_hint().0);
 268                 vec
 269             }
 270             TokenStreamKind::Tree(_) | TokenStreamKind::JointTree(_) => {
 271                 let mut vec = Vec::new();
 272                 vec.reserve(1 + iter.size_hint().0);
 273                 vec.push(TokenStream { kind });
 274                 vec
 275             }
 276             TokenStreamKind::Stream(rc_vec) => match RcVec::try_unwrap(rc_vec) {
 277                 Ok(mut vec) => {
 278                     // Extend in place using the existing capacity if possible.
 279                     // This is the fast path for libraries like `quote` that
 280                     // build a token stream.
 281                     vec.reserve(iter.size_hint().0);
 282                     vec
 283                 }
 284                 Err(rc_vec) => {
 285                     // Self is shared so we need to copy and extend that.
 286                     let mut vec = Vec::new();
 287                     vec.reserve(rc_vec.len() + iter.size_hint().0);
 288                     vec.extend_from_slice(&rc_vec);
 289                     vec
 290                 }
 291             }
 292         };
 293
 294         // Perform the extend, joining tokens as needed along the way.
 295         let mut builder = TokenStreamBuilder(tts);
 296         for stream in iter {
 297             builder.push(stream);
 298         }
 299
 300         // Build the resulting token stream. If it contains more than one token,
 301         // preserve capacity in the vector in anticipation of the caller
 302         // performing additional calls to extend.
 303         let mut tts = builder.0;
 304         *self = match tts.len() {
 305             0 => TokenStream::empty(),
 306             1 => tts.pop().unwrap(),
 307             _ => TokenStream::concat_rc_vec(RcVec::new_preserving_capacity(tts)),
 308         };
 309     }
 310 }
 311
 312 impl Eq for TokenStream {}
 313
 314 impl PartialEq<TokenStream> for TokenStream {
 315     fn eq(&self, other: &TokenStream) -> bool {
 316         self.trees().eq(other.trees())
 317     }
 318 }
 319
 320 impl TokenStream {
 321     pub fn len(&self) -> usize {
 322         if let TokenStreamKind::Stream(ref slice) = self.kind {
 323             slice.len()
 324         } else {
 325             0
 326         }
 327     }
 328
 329     pub fn empty() -> TokenStream {
 330         TokenStream { kind: TokenStreamKind::Empty }
 331     }
 332
 333     pub fn is_empty(&self) -> bool {
 334         match self.kind {
 335             TokenStreamKind::Empty => true,
 336             _ => false,
 337         }
 338     }
 339
 340     pub fn concat(mut streams: Vec<TokenStream>) -> TokenStream {
 341         match streams.len() {
 342             0 => TokenStream::empty(),
 343             1 => streams.pop().unwrap(),
 344             _ => TokenStream::concat_rc_vec(RcVec::new(streams)),
 345         }
 346     }
 347
 348     fn concat_rc_vec(streams: RcVec<TokenStream>) -> TokenStream {
 349         TokenStream { kind: TokenStreamKind::Stream(streams) }
 350     }
 351
 352     pub fn trees(&self) -> Cursor {
 353         self.clone().into_trees()
 354     }
 355
 356     pub fn into_trees(self) -> Cursor {
 357         Cursor::new(self)
 358     }
 359
 360     /// Compares two TokenStreams, checking equality without regarding span information.
 361     pub fn eq_unspanned(&self, other: &TokenStream) -> bool {
 362         let mut t1 = self.trees();
 363         let mut t2 = other.trees();
 364         for (t1, t2) in t1.by_ref().zip(t2.by_ref()) {
 365             if !t1.eq_unspanned(&t2) {
 366                 return false;
 367             }
 368         }
 369         t1.next().is_none() && t2.next().is_none()
 370     }
 371
 372     // See comments in `interpolated_to_tokenstream` for why we care about
 373     // *probably* equal here rather than actual equality
 374     //
 375     // This is otherwise the same as `eq_unspanned`, only recursing with a
 376     // different method.
 377     pub fn probably_equal_for_proc_macro(&self, other: &TokenStream) -> bool {
 378         let mut t1 = self.trees();
 379         let mut t2 = other.trees();
 380         for (t1, t2) in t1.by_ref().zip(t2.by_ref()) {
 381             if !t1.probably_equal_for_proc_macro(&t2) {
 382                 return false;
 383             }
 384         }
 385         t1.next().is_none() && t2.next().is_none()
 386     }
 387
 388     /// Precondition: `self` consists of a single token tree.
 389     /// Returns true if the token tree is a joint operation w.r.t. `proc_macro::TokenNode`.
 390     pub fn as_tree(self) -> (TokenTree, bool /* joint? */) {
 391         match self.kind {
 392             TokenStreamKind::Tree(tree) => (tree, false),
 393             TokenStreamKind::JointTree(tree) => (tree, true),
 394             _ => unreachable!(),
 395         }
 396     }
 397
 398     pub fn map_enumerated<F: FnMut(usize, TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream {
 399         let mut trees = self.into_trees();
 400         let mut result = Vec::new();
 401         let mut i = 0;
 402         while let Some(stream) = trees.next_as_stream() {
 403             result.push(match stream.kind {
 404                 TokenStreamKind::Tree(tree) => f(i, tree).into(),
 405                 TokenStreamKind::JointTree(tree) => f(i, tree).joint(),
 406                 _ => unreachable!()
 407             });
 408             i += 1;
 409         }
 410         TokenStream::concat(result)
 411     }
 412
 413     pub fn map<F: FnMut(TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream {
 414         let mut trees = self.into_trees();
 415         let mut result = Vec::new();
 416         while let Some(stream) = trees.next_as_stream() {
 417             result.push(match stream.kind {
 418                 TokenStreamKind::Tree(tree) => f(tree).into(),
 419                 TokenStreamKind::JointTree(tree) => f(tree).joint(),
 420                 _ => unreachable!()
 421             });
 422         }
 423         TokenStream::concat(result)
 424     }
 425
 426     fn first_tree_and_joint(&self) -> Option<(TokenTree, bool)> {
 427         match self.kind {
 428             TokenStreamKind::Empty => None,
 429             TokenStreamKind::Tree(ref tree) => Some((tree.clone(), false)),
 430             TokenStreamKind::JointTree(ref tree) => Some((tree.clone(), true)),
 431             TokenStreamKind::Stream(ref stream) => stream.first().unwrap().first_tree_and_joint(),
 432         }
 433     }
 434
 435     fn last_tree_if_joint(&self) -> Option<TokenTree> {
 436         match self.kind {
 437             TokenStreamKind::Empty | TokenStreamKind::Tree(..) => None,
 438             TokenStreamKind::JointTree(ref tree) => Some(tree.clone()),
 439             TokenStreamKind::Stream(ref stream) => stream.last().unwrap().last_tree_if_joint(),
 440         }
 441     }
 442 }
 443
 444 #[derive(Clone)]
 445 pub struct TokenStreamBuilder(Vec<TokenStream>);
 446
 447 impl TokenStreamBuilder {
 448     pub fn new() -> TokenStreamBuilder {
 449         TokenStreamBuilder(Vec::new())
 450     }
 451
 452     pub fn push<T: Into<TokenStream>>(&mut self, stream: T) {
 453         let stream = stream.into();
 454         let last_tree_if_joint = self.0.last().and_then(TokenStream::last_tree_if_joint);
 455         if let Some(TokenTree::Token(last_span, last_tok)) = last_tree_if_joint {
 456             if let Some((TokenTree::Token(span, tok), is_joint)) = stream.first_tree_and_joint() {
 457                 if let Some(glued_tok) = last_tok.glue(tok) {
 458                     let last_stream = self.0.pop().unwrap();
 459                     self.push_all_but_last_tree(&last_stream);
 460                     let glued_span = last_span.to(span);
 461                     let glued_tt = TokenTree::Token(glued_span, glued_tok);
 462                     let glued_tokenstream = if is_joint {
 463                         glued_tt.joint()
 464                     } else {
 465                         glued_tt.into()
 466                     };
 467                     self.0.push(glued_tokenstream);
 468                     self.push_all_but_first_tree(&stream);
 469                     return
 470                 }
 471             }
 472         }
 473         self.0.push(stream);
 474     }
 475
 476     pub fn add<T: Into<TokenStream>>(mut self, stream: T) -> Self {
 477         self.push(stream);
 478         self
 479     }
 480
 481     pub fn build(self) -> TokenStream {
 482         TokenStream::concat(self.0)
 483     }
 484
 485     fn push_all_but_last_tree(&mut self, stream: &TokenStream) {
 486         if let TokenStreamKind::Stream(ref streams) = stream.kind {
 487             let len = streams.len();
 488             match len {
 489                 1 => {}
 490                 2 => self.0.push(streams[0].clone().into()),
 491                 _ => self.0.push(TokenStream::concat_rc_vec(streams.sub_slice(0 .. len - 1))),
 492             }
 493             self.push_all_but_last_tree(&streams[len - 1])
 494         }
 495     }
 496
 497     fn push_all_but_first_tree(&mut self, stream: &TokenStream) {
 498         if let TokenStreamKind::Stream(ref streams) = stream.kind {
 499             let len = streams.len();
 500             match len {
 501                 1 => {}
 502                 2 => self.0.push(streams[1].clone().into()),
 503                 _ => self.0.push(TokenStream::concat_rc_vec(streams.sub_slice(1 .. len))),
 504             }
 505             self.push_all_but_first_tree(&streams[0])
 506         }
 507     }
 508 }
 509
 510 #[derive(Clone)]
 511 pub struct Cursor(CursorKind);
 512
 513 #[derive(Clone)]
 514 enum CursorKind {
 515     Empty,
 516     Tree(TokenTree, bool /* consumed? */),
 517     JointTree(TokenTree, bool /* consumed? */),
 518     Stream(StreamCursor),
 519 }
 520
 521 #[derive(Clone)]
 522 struct StreamCursor {
 523     stream: RcVec<TokenStream>,
 524     index: usize,
 525     stack: Vec<(RcVec<TokenStream>, usize)>,
 526 }
 527
 528 impl StreamCursor {
 529     fn new(stream: RcVec<TokenStream>) -> Self {
 530         StreamCursor { stream: stream, index: 0, stack: Vec::new() }
 531     }
 532
 533     fn next_as_stream(&mut self) -> Option<TokenStream> {
 534         loop {
 535             if self.index < self.stream.len() {
 536                 self.index += 1;
 537                 let next = self.stream[self.index - 1].clone();
 538                 match next.kind {
 539                     TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => return Some(next),
 540                     TokenStreamKind::Stream(stream) => self.insert(stream),
 541                     TokenStreamKind::Empty => {}
 542                 }
 543             } else if let Some((stream, index)) = self.stack.pop() {
 544                 self.stream = stream;
 545                 self.index = index;
 546             } else {
 547                 return None;
 548             }
 549         }
 550     }
 551
 552     fn insert(&mut self, stream: RcVec<TokenStream>) {
 553         self.stack.push((mem::replace(&mut self.stream, stream),
 554                          mem::replace(&mut self.index, 0)));
 555     }
 556 }
 557
 558 impl Iterator for Cursor {
 559     type Item = TokenTree;
 560
 561     fn next(&mut self) -> Option<TokenTree> {
 562         self.next_as_stream().map(|stream| match stream.kind {
 563             TokenStreamKind::Tree(tree) | TokenStreamKind::JointTree(tree) => tree,
 564             _ => unreachable!()
 565         })
 566     }
 567 }
 568
 569 impl Cursor {
 570     fn new(stream: TokenStream) -> Self {
 571         Cursor(match stream.kind {
 572             TokenStreamKind::Empty => CursorKind::Empty,
 573             TokenStreamKind::Tree(tree) => CursorKind::Tree(tree, false),
 574             TokenStreamKind::JointTree(tree) => CursorKind::JointTree(tree, false),
 575             TokenStreamKind::Stream(stream) => CursorKind::Stream(StreamCursor::new(stream)),
 576         })
 577     }
 578
 579     pub fn next_as_stream(&mut self) -> Option<TokenStream> {
 580         let (stream, consumed) = match self.0 {
 581             CursorKind::Tree(ref tree, ref mut consumed @ false) =>
 582                 (tree.clone().into(), consumed),
 583             CursorKind::JointTree(ref tree, ref mut consumed @ false) =>
 584                 (tree.clone().joint(), consumed),
 585             CursorKind::Stream(ref mut cursor) => return cursor.next_as_stream(),
 586             _ => return None,
 587         };
 588
 589         *consumed = true;
 590         Some(stream)
 591     }
 592
 593     pub fn insert(&mut self, stream: TokenStream) {
 594         match self.0 {
 595             _ if stream.is_empty() => return,
 596             CursorKind::Empty => *self = stream.trees(),
 597             CursorKind::Tree(_, consumed) | CursorKind::JointTree(_, consumed) => {
 598                 *self = TokenStream::concat(vec![self.original_stream(), stream]).trees();
 599                 if consumed {
 600                     self.next();
 601                 }
 602             }
 603             CursorKind::Stream(ref mut cursor) => {
 604                 cursor.insert(ThinTokenStream::from(stream).0.unwrap());
 605             }
 606         }
 607     }
 608
 609     pub fn original_stream(&self) -> TokenStream {
 610         match self.0 {
 611             CursorKind::Empty => TokenStream::empty(),
 612             CursorKind::Tree(ref tree, _) => tree.clone().into(),
 613             CursorKind::JointTree(ref tree, _) => tree.clone().joint(),
 614             CursorKind::Stream(ref cursor) => TokenStream::concat_rc_vec({
 615                 cursor.stack.get(0).cloned().map(|(stream, _)| stream)
 616                     .unwrap_or(cursor.stream.clone())
 617             }),
 618         }
 619     }
 620
 621     pub fn look_ahead(&self, n: usize) -> Option<TokenTree> {
 622         fn look_ahead(streams: &[TokenStream], mut n: usize) -> Result<TokenTree, usize> {
 623             for stream in streams {
 624                 n = match stream.kind {
 625                     TokenStreamKind::Tree(ref tree) | TokenStreamKind::JointTree(ref tree)
 626                         if n == 0 => return Ok(tree.clone()),
 627                     TokenStreamKind::Tree(..) | TokenStreamKind::JointTree(..) => n - 1,
 628                     TokenStreamKind::Stream(ref stream) => match look_ahead(stream, n) {
 629                         Ok(tree) => return Ok(tree),
 630                         Err(n) => n,
 631                     },
 632                     _ => n,
 633                 };
 634             }
 635             Err(n)
 636         }
 637
 638         match self.0 {
 639             CursorKind::Empty |
 640             CursorKind::Tree(_, true) |
 641             CursorKind::JointTree(_, true) => Err(n),
 642             CursorKind::Tree(ref tree, false) |
 643             CursorKind::JointTree(ref tree, false) => look_ahead(&[tree.clone().into()], n),
 644             CursorKind::Stream(ref cursor) => {
 645                 look_ahead(&cursor.stream[cursor.index ..], n).or_else(|mut n| {
 646                     for &(ref stream, index) in cursor.stack.iter().rev() {
 647                         n = match look_ahead(&stream[index..], n) {
 648                             Ok(tree) => return Ok(tree),
 649                             Err(n) => n,
 650                         }
 651                     }
 652
 653                     Err(n)
 654                 })
 655             }
 656         }.ok()
 657     }
 658 }
 659
 660 /// The `TokenStream` type is large enough to represent a single `TokenTree` without allocation.
 661 /// `ThinTokenStream` is smaller, but needs to allocate to represent a single `TokenTree`.
 662 /// We must use `ThinTokenStream` in `TokenTree::Delimited` to avoid infinite size due to recursion.
 663 #[derive(Debug, Clone)]
 664 pub struct ThinTokenStream(Option<RcVec<TokenStream>>);
 665
 666 impl From<TokenStream> for ThinTokenStream {
 667     fn from(stream: TokenStream) -> ThinTokenStream {
 668         ThinTokenStream(match stream.kind {
 669             TokenStreamKind::Empty => None,
 670             TokenStreamKind::Tree(tree) => Some(RcVec::new(vec![tree.into()])),
 671             TokenStreamKind::JointTree(tree) => Some(RcVec::new(vec![tree.joint()])),
 672             TokenStreamKind::Stream(stream) => Some(stream),
 673         })
 674     }
 675 }
 676
 677 impl From<ThinTokenStream> for TokenStream {
 678     fn from(stream: ThinTokenStream) -> TokenStream {
 679         stream.0.map(TokenStream::concat_rc_vec).unwrap_or_else(TokenStream::empty)
 680     }
 681 }
 682
 683 impl Eq for ThinTokenStream {}
 684
 685 impl PartialEq<ThinTokenStream> for ThinTokenStream {
 686     fn eq(&self, other: &ThinTokenStream) -> bool {
 687         TokenStream::from(self.clone()) == TokenStream::from(other.clone())
 688     }
 689 }
 690
 691 impl fmt::Display for TokenStream {
 692     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 693         f.write_str(&pprust::tokens_to_string(self.clone()))
 694     }
 695 }
 696
 697 impl Encodable for TokenStream {
 698     fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
 699         self.trees().collect::<Vec<_>>().encode(encoder)
 700     }
 701 }
 702
 703 impl Decodable for TokenStream {
 704     fn decode<D: Decoder>(decoder: &mut D) -> Result<TokenStream, D::Error> {
 705         Vec::<TokenTree>::decode(decoder).map(|vec| vec.into_iter().collect())
 706     }
 707 }
 708
 709 impl Encodable for ThinTokenStream {
 710     fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
 711         TokenStream::from(self.clone()).encode(encoder)
 712     }
 713 }
 714
 715 impl Decodable for ThinTokenStream {
 716     fn decode<D: Decoder>(decoder: &mut D) -> Result<ThinTokenStream, D::Error> {
 717         TokenStream::decode(decoder).map(Into::into)
 718     }
 719 }
 720
 721 #[cfg(test)]
 722 mod tests {
 723     use super::*;
 724     use syntax::ast::Ident;
 725     use with_globals;
 726     use syntax_pos::{Span, BytePos, NO_EXPANSION};
 727     use parse::token::Token;
 728     use util::parser_testing::string_to_stream;
 729
 730     fn string_to_ts(string: &str) -> TokenStream {
 731         string_to_stream(string.to_owned())
 732     }
 733
 734     fn sp(a: u32, b: u32) -> Span {
 735         Span::new(BytePos(a), BytePos(b), NO_EXPANSION)
 736     }
 737
 738     #[test]
 739     fn test_concat() {
 740         with_globals(|| {
 741             let test_res = string_to_ts("foo::bar::baz");
 742             let test_fst = string_to_ts("foo::bar");
 743             let test_snd = string_to_ts("::baz");
 744             let eq_res = TokenStream::concat(vec![test_fst, test_snd]);
 745             assert_eq!(test_res.trees().count(), 5);
 746             assert_eq!(eq_res.trees().count(), 5);
 747             assert_eq!(test_res.eq_unspanned(&eq_res), true);
 748         })
 749     }
 750
 751     #[test]
 752     fn test_to_from_bijection() {
 753         with_globals(|| {
 754             let test_start = string_to_ts("foo::bar(baz)");
 755             let test_end = test_start.trees().collect();
 756             assert_eq!(test_start, test_end)
 757         })
 758     }
 759
 760     #[test]
 761     fn test_eq_0() {
 762         with_globals(|| {
 763             let test_res = string_to_ts("foo");
 764             let test_eqs = string_to_ts("foo");
 765             assert_eq!(test_res, test_eqs)
 766         })
 767     }
 768
 769     #[test]
 770     fn test_eq_1() {
 771         with_globals(|| {
 772             let test_res = string_to_ts("::bar::baz");
 773             let test_eqs = string_to_ts("::bar::baz");
 774             assert_eq!(test_res, test_eqs)
 775         })
 776     }
 777
 778     #[test]
 779     fn test_eq_3() {
 780         with_globals(|| {
 781             let test_res = string_to_ts("");
 782             let test_eqs = string_to_ts("");
 783             assert_eq!(test_res, test_eqs)
 784         })
 785     }
 786
 787     #[test]
 788     fn test_diseq_0() {
 789         with_globals(|| {
 790             let test_res = string_to_ts("::bar::baz");
 791             let test_eqs = string_to_ts("bar::baz");
 792             assert_eq!(test_res == test_eqs, false)
 793         })
 794     }
 795
 796     #[test]
 797     fn test_diseq_1() {
 798         with_globals(|| {
 799             let test_res = string_to_ts("(bar,baz)");
 800             let test_eqs = string_to_ts("bar,baz");
 801             assert_eq!(test_res == test_eqs, false)
 802         })
 803     }
 804
 805     #[test]
 806     fn test_is_empty() {
 807         with_globals(|| {
 808             let test0: TokenStream = Vec::<TokenTree>::new().into_iter().collect();
 809             let test1: TokenStream =
 810                 TokenTree::Token(sp(0, 1), Token::Ident(Ident::from_str("a"), false)).into();
 811             let test2 = string_to_ts("foo(bar::baz)");
 812
 813             assert_eq!(test0.is_empty(), true);
 814             assert_eq!(test1.is_empty(), false);
 815             assert_eq!(test2.is_empty(), false);
 816         })
 817     }
 818
 819     #[test]
 820     fn test_dotdotdot() {
 821         let mut builder = TokenStreamBuilder::new();
 822         builder.push(TokenTree::Token(sp(0, 1), Token::Dot).joint());
 823         builder.push(TokenTree::Token(sp(1, 2), Token::Dot).joint());
 824         builder.push(TokenTree::Token(sp(2, 3), Token::Dot));
 825         let stream = builder.build();
 826         assert!(stream.eq_unspanned(&string_to_ts("...")));
 827         assert_eq!(stream.trees().count(), 1);
 828     }
 829
 830     #[test]
 831     fn test_extend_empty() {
 832         with_globals(|| {
 833             // Append a token onto an empty token stream.
 834             let mut stream = TokenStream::empty();
 835             stream.extend(vec![string_to_ts("t")]);
 836
 837             let expected = string_to_ts("t");
 838             assert!(stream.eq_unspanned(&expected));
 839         });
 840     }
 841
 842     #[test]
 843     fn test_extend_nothing() {
 844         with_globals(|| {
 845             // Append nothing onto a token stream containing one token.
 846             let mut stream = string_to_ts("t");
 847             stream.extend(vec![]);
 848
 849             let expected = string_to_ts("t");
 850             assert!(stream.eq_unspanned(&expected));
 851         });
 852     }
 853
 854     #[test]
 855     fn test_extend_single() {
 856         with_globals(|| {
 857             // Append a token onto token stream containing a single token.
 858             let mut stream = string_to_ts("t1");
 859             stream.extend(vec![string_to_ts("t2")]);
 860
 861             let expected = string_to_ts("t1 t2");
 862             assert!(stream.eq_unspanned(&expected));
 863         });
 864     }
 865
 866     #[test]
 867     fn test_extend_in_place() {
 868         with_globals(|| {
 869             // Append a token onto token stream containing a reference counted
 870             // vec of tokens. The token stream has a reference count of 1 so
 871             // this can happen in place.
 872             let mut stream = string_to_ts("t1 t2");
 873             stream.extend(vec![string_to_ts("t3")]);
 874
 875             let expected = string_to_ts("t1 t2 t3");
 876             assert!(stream.eq_unspanned(&expected));
 877         });
 878     }
 879
 880     #[test]
 881     fn test_extend_copy() {
 882         with_globals(|| {
 883             // Append a token onto token stream containing a reference counted
 884             // vec of tokens. The token stream is shared so the extend takes
 885             // place on a copy.
 886             let mut stream = string_to_ts("t1 t2");
 887             let _incref = stream.clone();
 888             stream.extend(vec![string_to_ts("t3")]);
 889
 890             let expected = string_to_ts("t1 t2 t3");
 891             assert!(stream.eq_unspanned(&expected));
 892         });
 893     }
 894
 895     #[test]
 896     fn test_extend_no_join() {
 897         with_globals(|| {
 898             let first = TokenTree::Token(DUMMY_SP, Token::Dot);
 899             let second = TokenTree::Token(DUMMY_SP, Token::Dot);
 900
 901             // Append a dot onto a token stream containing a dot, but do not
 902             // join them.
 903             let mut stream = TokenStream::from(first);
 904             stream.extend(vec![TokenStream::from(second)]);
 905
 906             let expected = string_to_ts(". .");
 907             assert!(stream.eq_unspanned(&expected));
 908
 909             let unexpected = string_to_ts("..");
 910             assert!(!stream.eq_unspanned(&unexpected));
 911         });
 912     }
 913
 914     #[test]
 915     fn test_extend_join() {
 916         with_globals(|| {
 917             let first = TokenTree::Token(DUMMY_SP, Token::Dot).joint();
 918             let second = TokenTree::Token(DUMMY_SP, Token::Dot);
 919
 920             // Append a dot onto a token stream containing a dot, forming a
 921             // dotdot.
 922             let mut stream = first;
 923             stream.extend(vec![TokenStream::from(second)]);
 924
 925             let expected = string_to_ts("..");
 926             assert!(stream.eq_unspanned(&expected));
 927
 928             let unexpected = string_to_ts(". .");
 929             assert!(!stream.eq_unspanned(&unexpected));
 930         });
 931     }
 932 }