compiler/rustc_ast/src/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 of [`TokenTree`]s,
   5 //! which are themselves a single [`Token`] or a `Delimited` subsequence of tokens.
   6 //!
   7 //! ## Ownership
   8 //!
   9 //! `TokenStream`s are persistent data structures constructed as ropes with reference
  10 //! counted-children. In general, this means that calling an operation on a `TokenStream`
  11 //! (such as `slice`) produces an entirely new `TokenStream` from the borrowed reference to
  12 //! the original. This essentially coerces `TokenStream`s into "views" of their subparts,
  13 //! and a borrowed `TokenStream` is sufficient to build an owned `TokenStream` without taking
  14 //! ownership of the original.
  15
  16 use crate::ast::StmtKind;
  17 use crate::ast_traits::{HasAttrs, HasSpan, HasTokens};
  18 use crate::token::{self, Delimiter, Nonterminal, Token, TokenKind};
  19 use crate::AttrVec;
  20
  21 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  22 use rustc_data_structures::sync::{self, Lrc};
  23 use rustc_macros::HashStable_Generic;
  24 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
  25 use rustc_span::{Span, DUMMY_SP};
  26 use smallvec::{smallvec, SmallVec};
  27
  28 use std::{fmt, iter};
  29
  30 /// When the main Rust parser encounters a syntax-extension invocation, it
  31 /// parses the arguments to the invocation as a token tree. This is a very
  32 /// loose structure, such that all sorts of different AST fragments can
  33 /// be passed to syntax extensions using a uniform type.
  34 ///
  35 /// If the syntax extension is an MBE macro, it will attempt to match its
  36 /// LHS token tree against the provided token tree, and if it finds a
  37 /// match, will transcribe the RHS token tree, splicing in any captured
  38 /// `macro_parser::matched_nonterminals` into the `SubstNt`s it finds.
  39 ///
  40 /// The RHS of an MBE macro is the only place `SubstNt`s are substituted.
  41 /// Nothing special happens to misnamed or misplaced `SubstNt`s.
  42 #[derive(Debug, Clone, PartialEq, Encodable, Decodable, HashStable_Generic)]
  43 pub enum TokenTree {
  44     /// A single token.
  45     Token(Token, Spacing),
  46     /// A delimited sequence of token trees.
  47     Delimited(DelimSpan, Delimiter, TokenStream),
  48 }
  49
  50 // This type is used a lot. Make sure it doesn't unintentionally get bigger.
  51 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
  52 rustc_data_structures::static_assert_size!(TokenTree, 32);
  53
  54 // Ensure all fields of `TokenTree` is `Send` and `Sync`.
  55 #[cfg(parallel_compiler)]
  56 fn _dummy()
  57 where
  58     Token: Send + Sync,
  59     DelimSpan: Send + Sync,
  60     Delimiter: Send + Sync,
  61     TokenStream: Send + Sync,
  62 {
  63 }
  64
  65 impl TokenTree {
  66     /// Checks if this `TokenTree` is equal to the other, regardless of span information.
  67     pub fn eq_unspanned(&self, other: &TokenTree) -> bool {
  68         match (self, other) {
  69             (TokenTree::Token(token, _), TokenTree::Token(token2, _)) => token.kind == token2.kind,
  70             (TokenTree::Delimited(_, delim, tts), TokenTree::Delimited(_, delim2, tts2)) => {
  71                 delim == delim2 && tts.eq_unspanned(&tts2)
  72             }
  73             _ => false,
  74         }
  75     }
  76
  77     /// Retrieves the `TokenTree`'s span.
  78     pub fn span(&self) -> Span {
  79         match self {
  80             TokenTree::Token(token, _) => token.span,
  81             TokenTree::Delimited(sp, ..) => sp.entire(),
  82         }
  83     }
  84
  85     /// Modify the `TokenTree`'s span in-place.
  86     pub fn set_span(&mut self, span: Span) {
  87         match self {
  88             TokenTree::Token(token, _) => token.span = span,
  89             TokenTree::Delimited(dspan, ..) => *dspan = DelimSpan::from_single(span),
  90         }
  91     }
  92
  93     // Create a `TokenTree::Token` with alone spacing.
  94     pub fn token_alone(kind: TokenKind, span: Span) -> TokenTree {
  95         TokenTree::Token(Token::new(kind, span), Spacing::Alone)
  96     }
  97
  98     // Create a `TokenTree::Token` with joint spacing.
  99     pub fn token_joint(kind: TokenKind, span: Span) -> TokenTree {
 100         TokenTree::Token(Token::new(kind, span), Spacing::Joint)
 101     }
 102
 103     pub fn uninterpolate(self) -> TokenTree {
 104         match self {
 105             TokenTree::Token(token, spacing) => {
 106                 TokenTree::Token(token.uninterpolate().into_owned(), spacing)
 107             }
 108             tt => tt,
 109         }
 110     }
 111 }
 112
 113 impl<CTX> HashStable<CTX> for TokenStream
 114 where
 115     CTX: crate::HashStableContext,
 116 {
 117     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 118         for sub_tt in self.trees() {
 119             sub_tt.hash_stable(hcx, hasher);
 120         }
 121     }
 122 }
 123
 124 pub trait CreateTokenStream: sync::Send + sync::Sync {
 125     fn create_token_stream(&self) -> AttrAnnotatedTokenStream;
 126 }
 127
 128 impl CreateTokenStream for AttrAnnotatedTokenStream {
 129     fn create_token_stream(&self) -> AttrAnnotatedTokenStream {
 130         self.clone()
 131     }
 132 }
 133
 134 /// A lazy version of [`TokenStream`], which defers creation
 135 /// of an actual `TokenStream` until it is needed.
 136 /// `Box` is here only to reduce the structure size.
 137 #[derive(Clone)]
 138 pub struct LazyTokenStream(Lrc<Box<dyn CreateTokenStream>>);
 139
 140 impl LazyTokenStream {
 141     pub fn new(inner: impl CreateTokenStream + 'static) -> LazyTokenStream {
 142         LazyTokenStream(Lrc::new(Box::new(inner)))
 143     }
 144
 145     pub fn create_token_stream(&self) -> AttrAnnotatedTokenStream {
 146         self.0.create_token_stream()
 147     }
 148 }
 149
 150 impl fmt::Debug for LazyTokenStream {
 151     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 152         write!(f, "LazyTokenStream({:?})", self.create_token_stream())
 153     }
 154 }
 155
 156 impl<S: Encoder> Encodable<S> for LazyTokenStream {
 157     fn encode(&self, s: &mut S) {
 158         // Used by AST json printing.
 159         Encodable::encode(&self.create_token_stream(), s);
 160     }
 161 }
 162
 163 impl<D: Decoder> Decodable<D> for LazyTokenStream {
 164     fn decode(_d: &mut D) -> Self {
 165         panic!("Attempted to decode LazyTokenStream");
 166     }
 167 }
 168
 169 impl<CTX> HashStable<CTX> for LazyTokenStream {
 170     fn hash_stable(&self, _hcx: &mut CTX, _hasher: &mut StableHasher) {
 171         panic!("Attempted to compute stable hash for LazyTokenStream");
 172     }
 173 }
 174
 175 /// A `AttrAnnotatedTokenStream` is similar to a `TokenStream`, but with extra
 176 /// information about the tokens for attribute targets. This is used
 177 /// during expansion to perform early cfg-expansion, and to process attributes
 178 /// during proc-macro invocations.
 179 #[derive(Clone, Debug, Default, Encodable, Decodable)]
 180 pub struct AttrAnnotatedTokenStream(pub Lrc<Vec<(AttrAnnotatedTokenTree, Spacing)>>);
 181
 182 /// Like `TokenTree`, but for `AttrAnnotatedTokenStream`
 183 #[derive(Clone, Debug, Encodable, Decodable)]
 184 pub enum AttrAnnotatedTokenTree {
 185     Token(Token),
 186     Delimited(DelimSpan, Delimiter, AttrAnnotatedTokenStream),
 187     /// Stores the attributes for an attribute target,
 188     /// along with the tokens for that attribute target.
 189     /// See `AttributesData` for more information
 190     Attributes(AttributesData),
 191 }
 192
 193 impl AttrAnnotatedTokenStream {
 194     pub fn new(tokens: Vec<(AttrAnnotatedTokenTree, Spacing)>) -> AttrAnnotatedTokenStream {
 195         AttrAnnotatedTokenStream(Lrc::new(tokens))
 196     }
 197
 198     /// Converts this `AttrAnnotatedTokenStream` to a plain `TokenStream
 199     /// During conversion, `AttrAnnotatedTokenTree::Attributes` get 'flattened'
 200     /// back to a `TokenStream` of the form `outer_attr attr_target`.
 201     /// If there are inner attributes, they are inserted into the proper
 202     /// place in the attribute target tokens.
 203     pub fn to_tokenstream(&self) -> TokenStream {
 204         let trees: Vec<_> = self
 205             .0
 206             .iter()
 207             .flat_map(|tree| match &tree.0 {
 208                 AttrAnnotatedTokenTree::Token(inner) => {
 209                     smallvec![TokenTree::Token(inner.clone(), tree.1)].into_iter()
 210                 }
 211                 AttrAnnotatedTokenTree::Delimited(span, delim, stream) => {
 212                     smallvec![TokenTree::Delimited(*span, *delim, stream.to_tokenstream()),]
 213                         .into_iter()
 214                 }
 215                 AttrAnnotatedTokenTree::Attributes(data) => {
 216                     let mut outer_attrs = Vec::new();
 217                     let mut inner_attrs = Vec::new();
 218                     for attr in &data.attrs {
 219                         match attr.style {
 220                             crate::AttrStyle::Outer => {
 221                                 outer_attrs.push(attr);
 222                             }
 223                             crate::AttrStyle::Inner => {
 224                                 inner_attrs.push(attr);
 225                             }
 226                         }
 227                     }
 228
 229                     let mut target_tokens: Vec<_> = data
 230                         .tokens
 231                         .create_token_stream()
 232                         .to_tokenstream()
 233                         .0
 234                         .iter()
 235                         .cloned()
 236                         .collect();
 237                     if !inner_attrs.is_empty() {
 238                         let mut found = false;
 239                         // Check the last two trees (to account for a trailing semi)
 240                         for tree in target_tokens.iter_mut().rev().take(2) {
 241                             if let TokenTree::Delimited(span, delim, delim_tokens) = tree {
 242                                 // Inner attributes are only supported on extern blocks, functions, impls,
 243                                 // and modules. All of these have their inner attributes placed at
 244                                 // the beginning of the rightmost outermost braced group:
 245                                 // e.g. fn foo() { #![my_attr} }
 246                                 //
 247                                 // Therefore, we can insert them back into the right location
 248                                 // without needing to do any extra position tracking.
 249                                 //
 250                                 // Note: Outline modules are an exception - they can
 251                                 // have attributes like `#![my_attr]` at the start of a file.
 252                                 // Support for custom attributes in this position is not
 253                                 // properly implemented - we always synthesize fake tokens,
 254                                 // so we never reach this code.
 255
 256                                 let mut builder = TokenStreamBuilder::new();
 257                                 for inner_attr in inner_attrs {
 258                                     builder.push(inner_attr.tokens().to_tokenstream());
 259                                 }
 260                                 builder.push(delim_tokens.clone());
 261                                 *tree = TokenTree::Delimited(*span, *delim, builder.build());
 262                                 found = true;
 263                                 break;
 264                             }
 265                         }
 266
 267                         assert!(
 268                             found,
 269                             "Failed to find trailing delimited group in: {:?}",
 270                             target_tokens
 271                         );
 272                     }
 273                     let mut flat: SmallVec<[_; 1]> = SmallVec::new();
 274                     for attr in outer_attrs {
 275                         // FIXME: Make this more efficient
 276                         flat.extend(attr.tokens().to_tokenstream().0.clone().iter().cloned());
 277                     }
 278                     flat.extend(target_tokens);
 279                     flat.into_iter()
 280                 }
 281             })
 282             .collect();
 283         TokenStream::new(trees)
 284     }
 285 }
 286
 287 /// Stores the tokens for an attribute target, along
 288 /// with its attributes.
 289 ///
 290 /// This is constructed during parsing when we need to capture
 291 /// tokens.
 292 ///
 293 /// For example, `#[cfg(FALSE)] struct Foo {}` would
 294 /// have an `attrs` field containing the `#[cfg(FALSE)]` attr,
 295 /// and a `tokens` field storing the (unparsed) tokens `struct Foo {}`
 296 #[derive(Clone, Debug, Encodable, Decodable)]
 297 pub struct AttributesData {
 298     /// Attributes, both outer and inner.
 299     /// These are stored in the original order that they were parsed in.
 300     pub attrs: AttrVec,
 301     /// The underlying tokens for the attribute target that `attrs`
 302     /// are applied to
 303     pub tokens: LazyTokenStream,
 304 }
 305
 306 /// A `TokenStream` is an abstract sequence of tokens, organized into [`TokenTree`]s.
 307 ///
 308 /// The goal is for procedural macros to work with `TokenStream`s and `TokenTree`s
 309 /// instead of a representation of the abstract syntax tree.
 310 /// Today's `TokenTree`s can still contain AST via `token::Interpolated` for
 311 /// backwards compatibility.
 312 #[derive(Clone, Debug, Default, Encodable, Decodable)]
 313 pub struct TokenStream(pub(crate) Lrc<Vec<TokenTree>>);
 314
 315 // `TokenStream` is used a lot. Make sure it doesn't unintentionally get bigger.
 316 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 317 rustc_data_structures::static_assert_size!(TokenStream, 8);
 318
 319 #[derive(Clone, Copy, Debug, PartialEq, Encodable, Decodable, HashStable_Generic)]
 320 pub enum Spacing {
 321     Alone,
 322     Joint,
 323 }
 324
 325 impl TokenStream {
 326     /// Given a `TokenStream` with a `Stream` of only two arguments, return a new `TokenStream`
 327     /// separating the two arguments with a comma for diagnostic suggestions.
 328     pub fn add_comma(&self) -> Option<(TokenStream, Span)> {
 329         // Used to suggest if a user writes `foo!(a b);`
 330         let mut suggestion = None;
 331         let mut iter = self.0.iter().enumerate().peekable();
 332         while let Some((pos, ts)) = iter.next() {
 333             if let Some((_, next)) = iter.peek() {
 334                 let sp = match (&ts, &next) {
 335                     (_, TokenTree::Token(Token { kind: token::Comma, .. }, _)) => continue,
 336                     (
 337                         TokenTree::Token(token_left, Spacing::Alone),
 338                         TokenTree::Token(token_right, _),
 339                     ) if ((token_left.is_ident() && !token_left.is_reserved_ident())
 340                         || token_left.is_lit())
 341                         && ((token_right.is_ident() && !token_right.is_reserved_ident())
 342                             || token_right.is_lit()) =>
 343                     {
 344                         token_left.span
 345                     }
 346                     (TokenTree::Delimited(sp, ..), _) => sp.entire(),
 347                     _ => continue,
 348                 };
 349                 let sp = sp.shrink_to_hi();
 350                 let comma = TokenTree::token_alone(token::Comma, sp);
 351                 suggestion = Some((pos, comma, sp));
 352             }
 353         }
 354         if let Some((pos, comma, sp)) = suggestion {
 355             let mut new_stream = Vec::with_capacity(self.0.len() + 1);
 356             let parts = self.0.split_at(pos + 1);
 357             new_stream.extend_from_slice(parts.0);
 358             new_stream.push(comma);
 359             new_stream.extend_from_slice(parts.1);
 360             return Some((TokenStream::new(new_stream), sp));
 361         }
 362         None
 363     }
 364 }
 365
 366 impl From<(AttrAnnotatedTokenTree, Spacing)> for AttrAnnotatedTokenStream {
 367     fn from((tree, spacing): (AttrAnnotatedTokenTree, Spacing)) -> AttrAnnotatedTokenStream {
 368         AttrAnnotatedTokenStream::new(vec![(tree, spacing)])
 369     }
 370 }
 371
 372 impl iter::FromIterator<TokenTree> for TokenStream {
 373     fn from_iter<I: IntoIterator<Item = TokenTree>>(iter: I) -> Self {
 374         TokenStream::new(iter.into_iter().collect::<Vec<TokenTree>>())
 375     }
 376 }
 377
 378 impl Eq for TokenStream {}
 379
 380 impl PartialEq<TokenStream> for TokenStream {
 381     fn eq(&self, other: &TokenStream) -> bool {
 382         self.trees().eq(other.trees())
 383     }
 384 }
 385
 386 impl TokenStream {
 387     pub fn new(streams: Vec<TokenTree>) -> TokenStream {
 388         TokenStream(Lrc::new(streams))
 389     }
 390
 391     pub fn is_empty(&self) -> bool {
 392         self.0.is_empty()
 393     }
 394
 395     pub fn len(&self) -> usize {
 396         self.0.len()
 397     }
 398
 399     pub fn trees(&self) -> CursorRef<'_> {
 400         CursorRef::new(self)
 401     }
 402
 403     pub fn into_trees(self) -> Cursor {
 404         Cursor::new(self)
 405     }
 406
 407     /// Compares two `TokenStream`s, checking equality without regarding span information.
 408     pub fn eq_unspanned(&self, other: &TokenStream) -> bool {
 409         let mut t1 = self.trees();
 410         let mut t2 = other.trees();
 411         for (t1, t2) in iter::zip(&mut t1, &mut t2) {
 412             if !t1.eq_unspanned(&t2) {
 413                 return false;
 414             }
 415         }
 416         t1.next().is_none() && t2.next().is_none()
 417     }
 418
 419     pub fn map_enumerated<F: FnMut(usize, &TokenTree) -> TokenTree>(self, mut f: F) -> TokenStream {
 420         TokenStream(Lrc::new(self.0.iter().enumerate().map(|(i, tree)| f(i, tree)).collect()))
 421     }
 422
 423     fn opt_from_ast(node: &(impl HasAttrs + HasTokens)) -> Option<TokenStream> {
 424         let tokens = node.tokens()?;
 425         let attrs = node.attrs();
 426         let attr_annotated = if attrs.is_empty() {
 427             tokens.create_token_stream()
 428         } else {
 429             let attr_data = AttributesData { attrs: attrs.to_vec().into(), tokens: tokens.clone() };
 430             AttrAnnotatedTokenStream::new(vec![(
 431                 AttrAnnotatedTokenTree::Attributes(attr_data),
 432                 Spacing::Alone,
 433             )])
 434         };
 435         Some(attr_annotated.to_tokenstream())
 436     }
 437
 438     // Create a token stream containing a single token with alone spacing.
 439     pub fn token_alone(kind: TokenKind, span: Span) -> TokenStream {
 440         TokenStream::new(vec![TokenTree::token_alone(kind, span)])
 441     }
 442
 443     // Create a token stream containing a single token with joint spacing.
 444     pub fn token_joint(kind: TokenKind, span: Span) -> TokenStream {
 445         TokenStream::new(vec![TokenTree::token_joint(kind, span)])
 446     }
 447
 448     // Create a token stream containing a single `Delimited`.
 449     pub fn delimited(span: DelimSpan, delim: Delimiter, tts: TokenStream) -> TokenStream {
 450         TokenStream::new(vec![TokenTree::Delimited(span, delim, tts)])
 451     }
 452
 453     pub fn from_ast(node: &(impl HasAttrs + HasSpan + HasTokens + fmt::Debug)) -> TokenStream {
 454         TokenStream::opt_from_ast(node)
 455             .unwrap_or_else(|| panic!("missing tokens for node at {:?}: {:?}", node.span(), node))
 456     }
 457
 458     pub fn from_nonterminal_ast(nt: &Nonterminal) -> TokenStream {
 459         match nt {
 460             Nonterminal::NtIdent(ident, is_raw) => {
 461                 TokenStream::token_alone(token::Ident(ident.name, *is_raw), ident.span)
 462             }
 463             Nonterminal::NtLifetime(ident) => {
 464                 TokenStream::token_alone(token::Lifetime(ident.name), ident.span)
 465             }
 466             Nonterminal::NtItem(item) => TokenStream::from_ast(item),
 467             Nonterminal::NtBlock(block) => TokenStream::from_ast(block),
 468             Nonterminal::NtStmt(stmt) if let StmtKind::Empty = stmt.kind => {
 469                 // FIXME: Properly collect tokens for empty statements.
 470                 TokenStream::token_alone(token::Semi, stmt.span)
 471             }
 472             Nonterminal::NtStmt(stmt) => TokenStream::from_ast(stmt),
 473             Nonterminal::NtPat(pat) => TokenStream::from_ast(pat),
 474             Nonterminal::NtTy(ty) => TokenStream::from_ast(ty),
 475             Nonterminal::NtMeta(attr) => TokenStream::from_ast(attr),
 476             Nonterminal::NtPath(path) => TokenStream::from_ast(path),
 477             Nonterminal::NtVis(vis) => TokenStream::from_ast(vis),
 478             Nonterminal::NtExpr(expr) | Nonterminal::NtLiteral(expr) => TokenStream::from_ast(expr),
 479         }
 480     }
 481
 482     fn flatten_token(token: &Token, spacing: Spacing) -> TokenTree {
 483         match &token.kind {
 484             token::Interpolated(nt) if let token::NtIdent(ident, is_raw) = **nt => {
 485                 TokenTree::Token(Token::new(token::Ident(ident.name, is_raw), ident.span), spacing)
 486             }
 487             token::Interpolated(nt) => TokenTree::Delimited(
 488                 DelimSpan::from_single(token.span),
 489                 Delimiter::Invisible,
 490                 TokenStream::from_nonterminal_ast(&nt).flattened(),
 491             ),
 492             _ => TokenTree::Token(token.clone(), spacing),
 493         }
 494     }
 495
 496     fn flatten_token_tree(tree: &TokenTree) -> TokenTree {
 497         match tree {
 498             TokenTree::Token(token, spacing) => TokenStream::flatten_token(token, *spacing),
 499             TokenTree::Delimited(span, delim, tts) => {
 500                 TokenTree::Delimited(*span, *delim, tts.flattened())
 501             }
 502         }
 503     }
 504
 505     #[must_use]
 506     pub fn flattened(&self) -> TokenStream {
 507         fn can_skip(stream: &TokenStream) -> bool {
 508             stream.trees().all(|tree| match tree {
 509                 TokenTree::Token(token, _) => !matches!(token.kind, token::Interpolated(_)),
 510                 TokenTree::Delimited(_, _, inner) => can_skip(inner),
 511             })
 512         }
 513
 514         if can_skip(self) {
 515             return self.clone();
 516         }
 517
 518         self.trees().map(|tree| TokenStream::flatten_token_tree(tree)).collect()
 519     }
 520 }
 521
 522 // 99.5%+ of the time we have 1 or 2 elements in this vector.
 523 #[derive(Clone)]
 524 pub struct TokenStreamBuilder(SmallVec<[TokenStream; 2]>);
 525
 526 impl TokenStreamBuilder {
 527     pub fn new() -> TokenStreamBuilder {
 528         TokenStreamBuilder(SmallVec::new())
 529     }
 530
 531     pub fn push(&mut self, stream: TokenStream) {
 532         self.0.push(stream);
 533     }
 534
 535     pub fn build(self) -> TokenStream {
 536         let mut streams = self.0;
 537         match streams.len() {
 538             0 => TokenStream::default(),
 539             1 => streams.pop().unwrap(),
 540             _ => {
 541                 // We will extend the first stream in `streams` with the
 542                 // elements from the subsequent streams. This requires using
 543                 // `make_mut()` on the first stream, and in practice this
 544                 // doesn't cause cloning 99.9% of the time.
 545                 //
 546                 // One very common use case is when `streams` has two elements,
 547                 // where the first stream has any number of elements within
 548                 // (often 1, but sometimes many more) and the second stream has
 549                 // a single element within.
 550
 551                 // Determine how much the first stream will be extended.
 552                 // Needed to avoid quadratic blow up from on-the-fly
 553                 // reallocations (#57735).
 554                 let num_appends = streams.iter().skip(1).map(|ts| ts.len()).sum();
 555
 556                 // Get the first stream, which will become the result stream.
 557                 // If it's `None`, create an empty stream.
 558                 let mut iter = streams.drain(..);
 559                 let mut res_stream_lrc = iter.next().unwrap().0;
 560
 561                 // Append the subsequent elements to the result stream, after
 562                 // reserving space for them.
 563                 let res_vec_mut = Lrc::make_mut(&mut res_stream_lrc);
 564                 res_vec_mut.reserve(num_appends);
 565                 for stream in iter {
 566                     let stream_iter = stream.0.iter().cloned();
 567
 568                     // If (a) `res_mut_vec` is not empty and the last tree
 569                     // within it is a token tree marked with `Joint`, and (b)
 570                     // `stream` is not empty and the first tree within it is a
 571                     // token tree, and (c) the two tokens can be glued
 572                     // together...
 573                     if let Some(TokenTree::Token(last_tok, Spacing::Joint)) = res_vec_mut.last()
 574                         && let Some(TokenTree::Token(tok, spacing)) = stream.0.first()
 575                         && let Some(glued_tok) = last_tok.glue(&tok)
 576                     {
 577                         // ...then overwrite the last token tree in
 578                         // `res_vec_mut` with the glued token, and skip the
 579                         // first token tree from `stream`.
 580                         *res_vec_mut.last_mut().unwrap() = TokenTree::Token(glued_tok, *spacing);
 581                         res_vec_mut.extend(stream_iter.skip(1));
 582                     } else {
 583                         // Append all of `stream`.
 584                         res_vec_mut.extend(stream_iter);
 585                     }
 586                 }
 587
 588                 TokenStream(res_stream_lrc)
 589             }
 590         }
 591     }
 592 }
 593
 594 /// By-reference iterator over a [`TokenStream`].
 595 #[derive(Clone)]
 596 pub struct CursorRef<'t> {
 597     stream: &'t TokenStream,
 598     index: usize,
 599 }
 600
 601 impl<'t> CursorRef<'t> {
 602     fn new(stream: &'t TokenStream) -> Self {
 603         CursorRef { stream, index: 0 }
 604     }
 605
 606     pub fn look_ahead(&self, n: usize) -> Option<&TokenTree> {
 607         self.stream.0.get(self.index + n)
 608     }
 609 }
 610
 611 impl<'t> Iterator for CursorRef<'t> {
 612     type Item = &'t TokenTree;
 613
 614     fn next(&mut self) -> Option<&'t TokenTree> {
 615         self.stream.0.get(self.index).map(|tree| {
 616             self.index += 1;
 617             tree
 618         })
 619     }
 620 }
 621
 622 /// Owning by-value iterator over a [`TokenStream`].
 623 // FIXME: Many uses of this can be replaced with by-reference iterator to avoid clones.
 624 #[derive(Clone)]
 625 pub struct Cursor {
 626     pub stream: TokenStream,
 627     index: usize,
 628 }
 629
 630 impl Iterator for Cursor {
 631     type Item = TokenTree;
 632
 633     fn next(&mut self) -> Option<TokenTree> {
 634         self.stream.0.get(self.index).map(|tree| {
 635             self.index += 1;
 636             tree.clone()
 637         })
 638     }
 639 }
 640
 641 impl Cursor {
 642     fn new(stream: TokenStream) -> Self {
 643         Cursor { stream, index: 0 }
 644     }
 645
 646     #[inline]
 647     pub fn next_ref(&mut self) -> Option<&TokenTree> {
 648         self.stream.0.get(self.index).map(|tree| {
 649             self.index += 1;
 650             tree
 651         })
 652     }
 653
 654     pub fn look_ahead(&self, n: usize) -> Option<&TokenTree> {
 655         self.stream.0.get(self.index + n)
 656     }
 657 }
 658
 659 #[derive(Debug, Copy, Clone, PartialEq, Encodable, Decodable, HashStable_Generic)]
 660 pub struct DelimSpan {
 661     pub open: Span,
 662     pub close: Span,
 663 }
 664
 665 impl DelimSpan {
 666     pub fn from_single(sp: Span) -> Self {
 667         DelimSpan { open: sp, close: sp }
 668     }
 669
 670     pub fn from_pair(open: Span, close: Span) -> Self {
 671         DelimSpan { open, close }
 672     }
 673
 674     pub fn dummy() -> Self {
 675         Self::from_single(DUMMY_SP)
 676     }
 677
 678     pub fn entire(self) -> Span {
 679         self.open.with_hi(self.close.hi())
 680     }
 681 }