1 use crate::ast::NodeId;
2 use crate::early_buffered_lints::BufferedEarlyLintId;
3 use crate::ext::tt::macro_parser;
4 use crate::feature_gate::Features;
5 use crate::parse::{token, ParseSess};
6 use crate::print::pprust;
7 use crate::tokenstream::{self, DelimSpan};
9 use crate::symbol::keywords;
11 use syntax_pos::{edition::Edition, BytePos, Span};
13 use rustc_data_structures::sync::Lrc;
14 use std::iter::Peekable;
16 /// Contains the sub-token-trees of a "delimited" token tree, such as the contents of `(`. Note
17 /// that the delimiter itself might be `NoDelim`.
18 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, Debug)]
19 pub struct Delimited {
20 pub delim: token::DelimToken,
21 pub tts: Vec<TokenTree>,
25 /// Returns the opening delimiter (possibly `NoDelim`).
26 pub fn open_token(&self) -> token::Token {
27 token::OpenDelim(self.delim)
30 /// Returns the closing delimiter (possibly `NoDelim`).
31 pub fn close_token(&self) -> token::Token {
32 token::CloseDelim(self.delim)
35 /// Returns a `self::TokenTree` with a `Span` corresponding to the opening delimiter.
36 pub fn open_tt(&self, span: Span) -> TokenTree {
37 let open_span = if span.is_dummy() {
40 span.with_lo(span.lo() + BytePos(self.delim.len() as u32))
42 TokenTree::Token(open_span, self.open_token())
45 /// Returns a `self::TokenTree` with a `Span` corresponding to the closing delimiter.
46 pub fn close_tt(&self, span: Span) -> TokenTree {
47 let close_span = if span.is_dummy() {
50 span.with_lo(span.hi() - BytePos(self.delim.len() as u32))
52 TokenTree::Token(close_span, self.close_token())
56 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, Debug)]
57 pub struct SequenceRepetition {
58 /// The sequence of token trees
59 pub tts: Vec<TokenTree>,
60 /// The optional separator
61 pub separator: Option<token::Token>,
62 /// Whether the sequence can be repeated zero (*), or one or more times (+)
64 /// The number of `Match`s that appear in the sequence (and subsequences)
65 pub num_captures: usize,
68 /// A Kleene-style [repetition operator](http://en.wikipedia.org/wiki/Kleene_star)
69 /// for token sequences.
70 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
72 /// Kleene star (`*`) for zero or more repetitions
74 /// Kleene plus (`+`) for one or more repetitions
79 /// Similar to `tokenstream::TokenTree`, except that `$i`, `$i:ident`, and `$(...)`
80 /// are "first-class" token trees. Useful for parsing macros.
81 #[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
83 Token(Span, token::Token),
84 Delimited(DelimSpan, Lrc<Delimited>),
85 /// A kleene-style repetition sequence
86 Sequence(DelimSpan, Lrc<SequenceRepetition>),
88 MetaVar(Span, ast::Ident),
89 /// e.g., `$var:expr`. This is only used in the left hand side of MBE macros.
92 ast::Ident, /* name to bind */
93 ast::Ident, /* kind of nonterminal */
98 /// Return the number of tokens in the tree.
99 pub fn len(&self) -> usize {
101 TokenTree::Delimited(_, ref delimed) => match delimed.delim {
102 token::NoDelim => delimed.tts.len(),
103 _ => delimed.tts.len() + 2,
105 TokenTree::Sequence(_, ref seq) => seq.tts.len(),
110 /// Returns `true` if the given token tree contains no other tokens. This is vacuously true for
111 /// single tokens or metavar/decls, but may be false for delimited trees or sequences.
112 pub fn is_empty(&self) -> bool {
114 TokenTree::Delimited(_, ref delimed) => match delimed.delim {
115 token::NoDelim => delimed.tts.is_empty(),
118 TokenTree::Sequence(_, ref seq) => seq.tts.is_empty(),
123 /// Gets the `index`-th sub-token-tree. This only makes sense for delimited trees and sequences.
124 pub fn get_tt(&self, index: usize) -> TokenTree {
125 match (self, index) {
126 (&TokenTree::Delimited(_, ref delimed), _) if delimed.delim == token::NoDelim => {
127 delimed.tts[index].clone()
129 (&TokenTree::Delimited(span, ref delimed), _) => {
131 return delimed.open_tt(span.open);
133 if index == delimed.tts.len() + 1 {
134 return delimed.close_tt(span.close);
136 delimed.tts[index - 1].clone()
138 (&TokenTree::Sequence(_, ref seq), _) => seq.tts[index].clone(),
139 _ => panic!("Cannot expand a token tree"),
143 /// Retrieves the `TokenTree`'s span.
144 pub fn span(&self) -> Span {
146 TokenTree::Token(sp, _)
147 | TokenTree::MetaVar(sp, _)
148 | TokenTree::MetaVarDecl(sp, _, _) => sp,
149 TokenTree::Delimited(sp, _)
150 | TokenTree::Sequence(sp, _) => sp.entire(),
155 /// Takes a `tokenstream::TokenStream` and returns a `Vec<self::TokenTree>`. Specifically, this
156 /// takes a generic `TokenStream`, such as is used in the rest of the compiler, and returns a
157 /// collection of `TokenTree` for use in parsing a macro.
161 /// - `input`: a token stream to read from, the contents of which we are parsing.
162 /// - `expect_matchers`: `parse` can be used to parse either the "patterns" or the "body" of a
163 /// macro. Both take roughly the same form _except_ that in a pattern, metavars are declared with
164 /// their "matcher" type. For example `$var:expr` or `$id:ident`. In this example, `expr` and
165 /// `ident` are "matchers". They are not present in the body of a macro rule -- just in the
166 /// pattern, so we pass a parameter to indicate whether to expect them or not.
167 /// - `sess`: the parsing session. Any errors will be emitted to this session.
168 /// - `features`, `attrs`: language feature flags and attributes so that we know whether to use
169 /// unstable features or not.
170 /// - `edition`: which edition are we in.
171 /// - `macro_node_id`: the NodeId of the macro we are parsing.
175 /// A collection of `self::TokenTree`. There may also be some errors emitted to `sess`.
177 input: tokenstream::TokenStream,
178 expect_matchers: bool,
181 attrs: &[ast::Attribute],
183 macro_node_id: NodeId,
184 ) -> Vec<TokenTree> {
185 // Will contain the final collection of `self::TokenTree`
186 let mut result = Vec::new();
188 // For each token tree in `input`, parse the token into a `self::TokenTree`, consuming
189 // additional trees if need be.
190 let mut trees = input.trees().peekable();
191 while let Some(tree) = trees.next() {
192 // Given the parsed tree, if there is a metavar and we are expecting matchers, actually
193 // parse out the matcher (i.e., in `$id:ident` this would parse the `:` and `ident`).
194 let tree = parse_tree(
205 TokenTree::MetaVar(start_sp, ident) if expect_matchers => {
206 let span = match trees.next() {
207 Some(tokenstream::TokenTree::Token(span, token::Colon)) => match trees.next() {
208 Some(tokenstream::TokenTree::Token(end_sp, ref tok)) => match tok.ident() {
210 let span = end_sp.with_lo(start_sp.lo());
211 result.push(TokenTree::MetaVarDecl(span, ident, kind));
218 .map(tokenstream::TokenTree::span)
223 .map(tokenstream::TokenTree::span)
224 .unwrap_or(start_sp),
226 sess.missing_fragment_specifiers.borrow_mut().insert(span);
227 result.push(TokenTree::MetaVarDecl(
230 keywords::Invalid.ident(),
234 // Not a metavar or no matchers allowed, so just return the tree
235 _ => result.push(tree),
241 /// Takes a `tokenstream::TokenTree` and returns a `self::TokenTree`. Specifically, this takes a
242 /// generic `TokenTree`, such as is used in the rest of the compiler, and returns a `TokenTree`
243 /// for use in parsing a macro.
245 /// Converting the given tree may involve reading more tokens.
249 /// - `tree`: the tree we wish to convert.
250 /// - `trees`: an iterator over trees. We may need to read more tokens from it in order to finish
251 /// converting `tree`
252 /// - `expect_matchers`: same as for `parse` (see above).
253 /// - `sess`: the parsing session. Any errors will be emitted to this session.
254 /// - `features`, `attrs`: language feature flags and attributes so that we know whether to use
255 /// unstable features or not.
257 tree: tokenstream::TokenTree,
258 trees: &mut Peekable<I>,
259 expect_matchers: bool,
262 attrs: &[ast::Attribute],
264 macro_node_id: NodeId,
267 I: Iterator<Item = tokenstream::TokenTree>,
269 // Depending on what `tree` is, we could be parsing different parts of a macro
271 // `tree` is a `$` token. Look at the next token in `trees`
272 tokenstream::TokenTree::Token(span, token::Dollar) => match trees.next() {
273 // `tree` is followed by a delimited set of token trees. This indicates the beginning
274 // of a repetition sequence in the macro (e.g. `$(pat)*`).
275 Some(tokenstream::TokenTree::Delimited(span, delim, tts)) => {
276 // Must have `(` not `{` or `[`
277 if delim != token::Paren {
278 let tok = pprust::token_to_string(&token::OpenDelim(delim));
279 let msg = format!("expected `(`, found `{}`", tok);
280 sess.span_diagnostic.span_err(span.entire(), &msg);
282 // Parse the contents of the sequence itself
283 let sequence = parse(
292 // Get the Kleene operator and optional separator
293 let (separator, op) =
294 parse_sep_and_kleene_op(
303 // Count the number of captured "names" (i.e., named metavars)
304 let name_captures = macro_parser::count_names(&sequence);
307 Lrc::new(SequenceRepetition {
311 num_captures: name_captures,
316 // `tree` is followed by an `ident`. This could be `$meta_var` or the `$crate` special
317 // metavariable that names the crate of the invocation.
318 Some(tokenstream::TokenTree::Token(ident_span, ref token)) if token.is_ident() => {
319 let (ident, is_raw) = token.ident().unwrap();
320 let span = ident_span.with_lo(span.lo());
321 if ident.name == keywords::Crate.name() && !is_raw {
322 let ident = ast::Ident::new(keywords::DollarCrate.name(), ident.span);
323 TokenTree::Token(span, token::Ident(ident, is_raw))
325 TokenTree::MetaVar(span, ident)
329 // `tree` is followed by a random token. This is an error.
330 Some(tokenstream::TokenTree::Token(span, tok)) => {
332 "expected identifier, found `{}`",
333 pprust::token_to_string(&tok)
335 sess.span_diagnostic.span_err(span, &msg);
336 TokenTree::MetaVar(span, keywords::Invalid.ident())
339 // There are no more tokens. Just return the `$` we already have.
340 None => TokenTree::Token(span, token::Dollar),
343 // `tree` is an arbitrary token. Keep it.
344 tokenstream::TokenTree::Token(span, tok) => TokenTree::Token(span, tok),
346 // `tree` is the beginning of a delimited set of tokens (e.g., `(` or `{`). We need to
347 // descend into the delimited set and further parse it.
348 tokenstream::TokenTree::Delimited(span, delim, tts) => TokenTree::Delimited(
366 /// Takes a token and returns `Some(KleeneOp)` if the token is `+` `*` or `?`. Otherwise, return
368 fn kleene_op(token: &token::Token) -> Option<KleeneOp> {
370 token::BinOp(token::Star) => Some(KleeneOp::ZeroOrMore),
371 token::BinOp(token::Plus) => Some(KleeneOp::OneOrMore),
372 token::Question => Some(KleeneOp::ZeroOrOne),
377 /// Parse the next token tree of the input looking for a KleeneOp. Returns
379 /// - Ok(Ok((op, span))) if the next token tree is a KleeneOp
380 /// - Ok(Err(tok, span)) if the next token tree is a token but not a KleeneOp
381 /// - Err(span) if the next token tree is not a token
382 fn parse_kleene_op<I>(
385 ) -> Result<Result<(KleeneOp, Span), (token::Token, Span)>, Span>
387 I: Iterator<Item = tokenstream::TokenTree>,
390 Some(tokenstream::TokenTree::Token(span, tok)) => match kleene_op(&tok) {
391 Some(op) => Ok(Ok((op, span))),
392 None => Ok(Err((tok, span))),
396 .map(tokenstream::TokenTree::span)
401 /// Attempt to parse a single Kleene star, possibly with a separator.
403 /// For example, in a pattern such as `$(a),*`, `a` is the pattern to be repeated, `,` is the
404 /// separator, and `*` is the Kleene operator. This function is specifically concerned with parsing
405 /// the last two tokens of such a pattern: namely, the optional separator and the Kleene operator
406 /// itself. Note that here we are parsing the _macro_ itself, rather than trying to match some
407 /// stream of tokens in an invocation of a macro.
409 /// This function will take some input iterator `input` corresponding to `span` and a parsing
410 /// session `sess`. If the next one (or possibly two) tokens in `input` correspond to a Kleene
411 /// operator and separator, then a tuple with `(separator, KleeneOp)` is returned. Otherwise, an
412 /// error with the appropriate span is emitted to `sess` and a dummy value is returned.
414 /// N.B., in the 2015 edition, `*` and `+` are the only Kleene operators, and `?` is a separator.
415 /// In the 2018 edition however, `?` is a Kleene operator, and not a separator.
416 fn parse_sep_and_kleene_op<I>(
417 input: &mut Peekable<I>,
421 attrs: &[ast::Attribute],
423 macro_node_id: NodeId,
424 ) -> (Option<token::Token>, KleeneOp)
426 I: Iterator<Item = tokenstream::TokenTree>,
429 Edition::Edition2015 => parse_sep_and_kleene_op_2015(
437 Edition::Edition2018 => parse_sep_and_kleene_op_2018(input, span, sess, features, attrs),
441 // `?` is a separator (with a migration warning) and never a KleeneOp.
442 fn parse_sep_and_kleene_op_2015<I>(
443 input: &mut Peekable<I>,
446 _features: &Features,
447 _attrs: &[ast::Attribute],
448 macro_node_id: NodeId,
449 ) -> (Option<token::Token>, KleeneOp)
451 I: Iterator<Item = tokenstream::TokenTree>,
453 // We basically look at two token trees here, denoted as #1 and #2 below
454 let span = match parse_kleene_op(input, span) {
455 // #1 is a `+` or `*` KleeneOp
457 // `?` is ambiguous: it could be a separator (warning) or a Kleene::ZeroOrOne (error), so
458 // we need to look ahead one more token to be sure.
459 Ok(Ok((op, _))) if op != KleeneOp::ZeroOrOne => return (None, op),
461 // #1 is `?` token, but it could be a Kleene::ZeroOrOne (error in 2015) without a separator
462 // or it could be a `?` separator followed by any Kleene operator. We need to look ahead 1
463 // token to find out which.
464 Ok(Ok((op, op1_span))) => {
465 assert_eq!(op, KleeneOp::ZeroOrOne);
467 // Lookahead at #2. If it is a KleenOp, then #1 is a separator.
468 let is_1_sep = if let Some(&tokenstream::TokenTree::Token(_, ref tok2)) = input.peek() {
469 kleene_op(tok2).is_some()
475 // #1 is a separator and #2 should be a KleepeOp.
476 // (N.B. We need to advance the input iterator.)
477 match parse_kleene_op(input, span) {
478 // #2 is `?`, which is not allowed as a Kleene op in 2015 edition,
479 // but is allowed in the 2018 edition.
480 Ok(Ok((op, op2_span))) if op == KleeneOp::ZeroOrOne => {
482 .struct_span_err(op2_span, "expected `*` or `+`")
483 .note("`?` is not a macro repetition operator in the 2015 edition, \
484 but is accepted in the 2018 edition")
488 return (None, KleeneOp::ZeroOrMore);
491 // #2 is a Kleene op, which is the only valid option
493 // Warn that `?` as a separator will be deprecated
495 BufferedEarlyLintId::QuestionMarkMacroSep,
498 "using `?` as a separator is deprecated and will be \
499 a hard error in an upcoming edition",
502 return (Some(token::Question), op);
505 // #2 is a random token (this is an error) :(
506 Ok(Err((_, _))) => op1_span,
508 // #2 is not even a token at all :(
512 // `?` is not allowed as a Kleene op in 2015,
513 // but is allowed in the 2018 edition
515 .struct_span_err(op1_span, "expected `*` or `+`")
516 .note("`?` is not a macro repetition operator in the 2015 edition, \
517 but is accepted in the 2018 edition")
521 return (None, KleeneOp::ZeroOrMore);
525 // #1 is a separator followed by #2, a KleeneOp
526 Ok(Err((tok, span))) => match parse_kleene_op(input, span) {
527 // #2 is a `?`, which is not allowed as a Kleene op in 2015 edition,
528 // but is allowed in the 2018 edition
529 Ok(Ok((op, op2_span))) if op == KleeneOp::ZeroOrOne => {
531 .struct_span_err(op2_span, "expected `*` or `+`")
532 .note("`?` is not a macro repetition operator in the 2015 edition, \
533 but is accepted in the 2018 edition")
537 return (None, KleeneOp::ZeroOrMore);
540 // #2 is a KleeneOp :D
541 Ok(Ok((op, _))) => return (Some(tok), op),
543 // #2 is a random token :(
544 Ok(Err((_, span))) => span,
546 // #2 is not a token at all :(
554 sess.span_diagnostic.span_err(span, "expected `*` or `+`");
557 (None, KleeneOp::ZeroOrMore)
560 // `?` is a Kleene op, not a separator
561 fn parse_sep_and_kleene_op_2018<I>(
562 input: &mut Peekable<I>,
565 _features: &Features,
566 _attrs: &[ast::Attribute],
567 ) -> (Option<token::Token>, KleeneOp)
569 I: Iterator<Item = tokenstream::TokenTree>,
571 // We basically look at two token trees here, denoted as #1 and #2 below
572 let span = match parse_kleene_op(input, span) {
573 // #1 is a `?` (needs feature gate)
574 Ok(Ok((op, _op1_span))) if op == KleeneOp::ZeroOrOne => {
578 // #1 is a `+` or `*` KleeneOp
579 Ok(Ok((op, _))) => return (None, op),
581 // #1 is a separator followed by #2, a KleeneOp
582 Ok(Err((tok, span))) => match parse_kleene_op(input, span) {
583 // #2 is the `?` Kleene op, which does not take a separator (error)
584 Ok(Ok((op, _op2_span))) if op == KleeneOp::ZeroOrOne => {
586 sess.span_diagnostic.span_err(
588 "the `?` macro repetition operator does not take a separator",
592 return (None, KleeneOp::ZeroOrMore);
595 // #2 is a KleeneOp :D
596 Ok(Ok((op, _))) => return (Some(tok), op),
598 // #2 is a random token :(
599 Ok(Err((_, span))) => span,
601 // #2 is not a token at all :(
609 // If we ever get to this point, we have experienced an "unexpected token" error
611 .span_err(span, "expected one of: `*`, `+`, or `?`");
614 (None, KleeneOp::ZeroOrMore)