src/libsyntax/tokenstream.rs

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