1 // Copyright 2015 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.
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.
11 use ast
::{self, TokenTree}
;
12 use codemap
::{Span, DUMMY_SP}
;
13 use ext
::base
::{DummyResult, ExtCtxt, MacResult, SyntaxExtension}
;
14 use ext
::base
::{NormalTT, TTMacroExpander}
;
15 use ext
::tt
::macro_parser
::{Success, Error, Failure}
;
16 use ext
::tt
::macro_parser
::{MatchedSeq, MatchedNonterminal}
;
17 use ext
::tt
::macro_parser
::parse
;
18 use parse
::lexer
::new_tt_reader
;
19 use parse
::parser
::{Parser, Restrictions}
;
20 use parse
::token
::{self, special_idents, gensym_ident, NtTT, Token}
;
21 use parse
::token
::Token
::*;
25 use util
::small_vector
::SmallVector
;
27 use std
::cell
::RefCell
;
28 use std
::collections
::{HashMap}
;
29 use std
::collections
::hash_map
::{Entry}
;
32 struct ParserAnyMacro
<'a
> {
33 parser
: RefCell
<Parser
<'a
>>,
35 /// Span of the expansion site of the macro this parser is for
37 /// The ident of the macro we're parsing
38 macro_ident
: ast
::Ident
41 impl<'a
> ParserAnyMacro
<'a
> {
42 /// Make sure we don't have any tokens left to parse, so we don't
43 /// silently drop anything. `allow_semi` is so that "optional"
44 /// semicolons at the end of normal expressions aren't complained
45 /// about e.g. the semicolon in `macro_rules! kapow { () => {
46 /// panic!(); } }` doesn't get picked up by .parse_expr(), but it's
47 /// allowed to be there.
48 fn ensure_complete_parse(&self, allow_semi
: bool
, context
: &str) {
49 let mut parser
= self.parser
.borrow_mut();
50 if allow_semi
&& parser
.token
== token
::Semi
{
53 if parser
.token
!= token
::Eof
{
54 let token_str
= parser
.this_token_to_string();
55 let msg
= format
!("macro expansion ignores token `{}` and any \
58 let span
= parser
.span
;
59 let mut err
= parser
.diagnostic().struct_span_err(span
, &msg
[..]);
60 let msg
= format
!("caused by the macro expansion here; the usage \
61 of `{}!` is likely invalid in {} context",
62 self.macro_ident
, context
);
63 err
.span_note(self.site_span
, &msg
[..])
69 impl<'a
> MacResult
for ParserAnyMacro
<'a
> {
70 fn make_expr(self: Box
<ParserAnyMacro
<'a
>>) -> Option
<P
<ast
::Expr
>> {
71 let ret
= panictry
!(self.parser
.borrow_mut().parse_expr());
72 self.ensure_complete_parse(true, "expression");
75 fn make_pat(self: Box
<ParserAnyMacro
<'a
>>) -> Option
<P
<ast
::Pat
>> {
76 let ret
= panictry
!(self.parser
.borrow_mut().parse_pat());
77 self.ensure_complete_parse(false, "pattern");
80 fn make_items(self: Box
<ParserAnyMacro
<'a
>>) -> Option
<SmallVector
<P
<ast
::Item
>>> {
81 let mut ret
= SmallVector
::zero();
82 while let Some(item
) = panictry
!(self.parser
.borrow_mut().parse_item()) {
85 self.ensure_complete_parse(false, "item");
89 fn make_impl_items(self: Box
<ParserAnyMacro
<'a
>>)
90 -> Option
<SmallVector
<ast
::ImplItem
>> {
91 let mut ret
= SmallVector
::zero();
93 let mut parser
= self.parser
.borrow_mut();
96 _
=> ret
.push(panictry
!(parser
.parse_impl_item()))
99 self.ensure_complete_parse(false, "item");
103 fn make_stmts(self: Box
<ParserAnyMacro
<'a
>>)
104 -> Option
<SmallVector
<ast
::Stmt
>> {
105 let mut ret
= SmallVector
::zero();
107 let mut parser
= self.parser
.borrow_mut();
110 _
=> match parser
.parse_stmt() {
111 Ok(maybe_stmt
) => match maybe_stmt
{
112 Some(stmt
) => ret
.push(stmt
),
122 self.ensure_complete_parse(false, "statement");
126 fn make_ty(self: Box
<ParserAnyMacro
<'a
>>) -> Option
<P
<ast
::Ty
>> {
127 let ret
= panictry
!(self.parser
.borrow_mut().parse_ty());
128 self.ensure_complete_parse(false, "type");
133 struct MacroRulesMacroExpander
{
135 imported_from
: Option
<ast
::Ident
>,
136 lhses
: Vec
<TokenTree
>,
137 rhses
: Vec
<TokenTree
>,
141 impl TTMacroExpander
for MacroRulesMacroExpander
{
142 fn expand
<'cx
>(&self,
143 cx
: &'cx
mut ExtCtxt
,
146 -> Box
<MacResult
+'cx
> {
148 return DummyResult
::any(sp
);
150 generic_extension(cx
,
160 /// Given `lhses` and `rhses`, this is the new macro we create
161 fn generic_extension
<'cx
>(cx
: &'cx ExtCtxt
,
164 imported_from
: Option
<ast
::Ident
>,
168 -> Box
<MacResult
+'cx
> {
169 if cx
.trace_macros() {
170 println
!("{}! {{ {} }}",
172 print
::pprust
::tts_to_string(arg
));
175 // Which arm's failure should we report? (the one furthest along)
176 let mut best_fail_spot
= DUMMY_SP
;
177 let mut best_fail_msg
= "internal error: ran no matchers".to_string();
179 for (i
, lhs
) in lhses
.iter().enumerate() { // try each arm's matchers
180 let lhs_tt
= match *lhs
{
181 TokenTree
::Delimited(_
, ref delim
) => &delim
.tts
[..],
182 _
=> cx
.span_fatal(sp
, "malformed macro lhs")
185 match TokenTree
::parse(cx
, lhs_tt
, arg
) {
186 Success(named_matches
) => {
187 let rhs
= match rhses
[i
] {
189 TokenTree
::Delimited(_
, ref delimed
) => delimed
.tts
.clone(),
190 _
=> cx
.span_fatal(sp
, "malformed macro rhs"),
192 // rhs has holes ( `$id` and `$(...)` that need filled)
193 let trncbr
= new_tt_reader(&cx
.parse_sess().span_diagnostic
,
197 let mut p
= Parser
::new(cx
.parse_sess(), cx
.cfg(), Box
::new(trncbr
));
198 p
.filename
= cx
.filename
.clone();
199 p
.mod_path_stack
= cx
.mod_path_stack
.clone();
200 p
.restrictions
= match cx
.in_block
{
201 true => Restrictions
::NO_NONINLINE_MOD
,
202 false => Restrictions
::empty(),
204 p
.check_unknown_macro_variable();
205 // Let the context choose how to interpret the result.
206 // Weird, but useful for X-macros.
207 return Box
::new(ParserAnyMacro
{
208 parser
: RefCell
::new(p
),
210 // Pass along the original expansion site and the name of the macro
211 // so we can print a useful error message if the parse of the expanded
212 // macro leaves unparsed tokens.
217 Failure(sp
, ref msg
) => if sp
.lo
>= best_fail_spot
.lo
{
219 best_fail_msg
= (*msg
).clone();
221 Error(err_sp
, ref msg
) => {
222 cx
.span_fatal(err_sp
.substitute_dummy(sp
), &msg
[..])
227 cx
.span_fatal(best_fail_spot
.substitute_dummy(sp
), &best_fail_msg
[..]);
230 // Note that macro-by-example's input is also matched against a token tree:
231 // $( $lhs:tt => $rhs:tt );+
233 // Holy self-referential!
235 /// Converts a `macro_rules!` invocation into a syntax extension.
236 pub fn compile
<'cx
>(cx
: &'cx
mut ExtCtxt
,
237 def
: &ast
::MacroDef
) -> SyntaxExtension
{
239 let lhs_nm
= gensym_ident("lhs");
240 let rhs_nm
= gensym_ident("rhs");
242 // The pattern that macro_rules matches.
243 // The grammar for macro_rules! is:
244 // $( $lhs:tt => $rhs:tt );+
245 // ...quasiquoting this would be nice.
246 // These spans won't matter, anyways
247 let match_lhs_tok
= MatchNt(lhs_nm
, special_idents
::tt
, token
::Plain
, token
::Plain
);
248 let match_rhs_tok
= MatchNt(rhs_nm
, special_idents
::tt
, token
::Plain
, token
::Plain
);
249 let argument_gram
= vec
!(
250 TokenTree
::Sequence(DUMMY_SP
,
251 Rc
::new(ast
::SequenceRepetition
{
253 TokenTree
::Token(DUMMY_SP
, match_lhs_tok
),
254 TokenTree
::Token(DUMMY_SP
, token
::FatArrow
),
255 TokenTree
::Token(DUMMY_SP
, match_rhs_tok
)],
256 separator
: Some(token
::Semi
),
257 op
: ast
::KleeneOp
::OneOrMore
,
260 //to phase into semicolon-termination instead of
261 //semicolon-separation
262 TokenTree
::Sequence(DUMMY_SP
,
263 Rc
::new(ast
::SequenceRepetition
{
264 tts
: vec
![TokenTree
::Token(DUMMY_SP
, token
::Semi
)],
266 op
: ast
::KleeneOp
::ZeroOrMore
,
271 // Parse the macro_rules! invocation (`none` is for no interpolations):
272 let arg_reader
= new_tt_reader(&cx
.parse_sess().span_diagnostic
,
277 let argument_map
= match parse(cx
.parse_sess(),
282 Failure(sp
, str) | Error(sp
, str) => {
283 panic
!(cx
.parse_sess().span_diagnostic
284 .span_fatal(sp
.substitute_dummy(def
.span
), &str[..]));
288 let mut valid
= true;
290 // Extract the arguments:
291 let lhses
= match **argument_map
.get(&lhs_nm
.name
).unwrap() {
292 MatchedSeq(ref s
, _
) => {
293 s
.iter().map(|m
| match **m
{
294 MatchedNonterminal(NtTT(ref tt
)) => (**tt
).clone(),
295 _
=> cx
.span_bug(def
.span
, "wrong-structured lhs")
298 _
=> cx
.span_bug(def
.span
, "wrong-structured lhs")
302 check_lhs_nt_follows(cx
, lhs
, def
.span
);
305 let rhses
= match **argument_map
.get(&rhs_nm
.name
).unwrap() {
306 MatchedSeq(ref s
, _
) => {
307 s
.iter().map(|m
| match **m
{
308 MatchedNonterminal(NtTT(ref tt
)) => (**tt
).clone(),
309 _
=> cx
.span_bug(def
.span
, "wrong-structured rhs")
312 _
=> cx
.span_bug(def
.span
, "wrong-structured rhs")
316 valid
&= check_rhs(cx
, rhs
);
319 let exp
: Box
<_
> = Box
::new(MacroRulesMacroExpander
{
321 imported_from
: def
.imported_from
,
327 NormalTT(exp
, Some(def
.span
), def
.allow_internal_unstable
)
330 // why is this here? because of https://github.com/rust-lang/rust/issues/27774
331 fn ref_slice
<A
>(s
: &A
) -> &[A
] { use std::slice::from_raw_parts; unsafe { from_raw_parts(s, 1) }
}
333 fn check_lhs_nt_follows(cx
: &mut ExtCtxt
, lhs
: &TokenTree
, sp
: Span
) {
334 // lhs is going to be like TokenTree::Delimited(...), where the
335 // entire lhs is those tts. Or, it can be a "bare sequence", not wrapped in parens.
337 &TokenTree
::Delimited(_
, ref tts
) => {
338 check_matcher(cx
, &tts
.tts
);
340 tt @
&TokenTree
::Sequence(..) => {
341 check_matcher(cx
, ref_slice(tt
));
343 _
=> cx
.span_err(sp
, "invalid macro matcher; matchers must be contained \
344 in balanced delimiters or a repetition indicator")
346 // we don't abort on errors on rejection, the driver will do that for us
347 // after parsing/expansion. we can report every error in every macro this way.
350 fn check_rhs(cx
: &mut ExtCtxt
, rhs
: &TokenTree
) -> bool
{
352 TokenTree
::Delimited(..) => return true,
353 _
=> cx
.span_err(rhs
.get_span(), "macro rhs must be delimited")
358 // Issue 30450: when we are through a warning cycle, we can just error
359 // on all failure conditions and remove this struct and enum.
364 action
: OnFailAction
,
367 #[derive(Copy, Clone, Debug)]
368 enum OnFailAction { Warn, Error, DoNothing }
371 fn warn() -> OnFail { OnFail { saw_failure: false, action: OnFailAction::Warn }
}
372 fn error() -> OnFail { OnFail { saw_failure: false, action: OnFailAction::Error }
}
373 fn do_nothing() -> OnFail { OnFail { saw_failure: false, action: OnFailAction::DoNothing }
}
374 fn react(&mut self, cx
: &mut ExtCtxt
, sp
: Span
, msg
: &str) {
376 OnFailAction
::DoNothing
=> {}
377 OnFailAction
::Error
=> cx
.span_err(sp
, msg
),
378 OnFailAction
::Warn
=> {
379 cx
.struct_span_warn(sp
, msg
)
380 .span_note(sp
, "The above warning will be a hard error in the next release.")
384 self.saw_failure
= true;
388 fn check_matcher(cx
: &mut ExtCtxt
, matcher
: &[TokenTree
]) {
389 // Issue 30450: when we are through a warning cycle, we can just
390 // error on all failure conditions (and remove check_matcher_old).
392 // First run the old-pass, but *only* to find out if it would have failed.
393 let mut on_fail
= OnFail
::do_nothing();
394 check_matcher_old(cx
, matcher
.iter(), &Eof
, &mut on_fail
);
395 // Then run the new pass, but merely warn if the old pass accepts and new pass rejects.
396 // (Note this silently accepts code if new pass accepts.)
397 let mut on_fail
= if on_fail
.saw_failure
{
402 check_matcher_new(cx
, matcher
, &mut on_fail
);
405 // returns the last token that was checked, for TokenTree::Sequence.
406 // return value is used by recursive calls.
407 fn check_matcher_old
<'a
, I
>(cx
: &mut ExtCtxt
, matcher
: I
, follow
: &Token
, on_fail
: &mut OnFail
)
408 -> Option
<(Span
, Token
)> where I
: Iterator
<Item
=&'a TokenTree
> {
409 use print
::pprust
::token_to_string
;
414 // 2. For each token T in M:
415 let mut tokens
= matcher
.peekable();
416 while let Some(token
) = tokens
.next() {
417 last
= match *token
{
418 TokenTree
::Token(sp
, MatchNt(ref name
, ref frag_spec
, _
, _
)) => {
419 // ii. If T is a simple NT, look ahead to the next token T' in
420 // M. If T' is in the set FOLLOW(NT), continue. Else; reject.
421 if can_be_followed_by_any(&frag_spec
.name
.as_str()) {
424 let next_token
= match tokens
.peek() {
425 // If T' closes a complex NT, replace T' with F
426 Some(&&TokenTree
::Token(_
, CloseDelim(_
))) => follow
.clone(),
427 Some(&&TokenTree
::Token(_
, ref tok
)) => tok
.clone(),
428 Some(&&TokenTree
::Sequence(sp
, _
)) => {
429 // Be conservative around sequences: to be
430 // more specific, we would need to
431 // consider FIRST sets, but also the
432 // possibility that the sequence occurred
433 // zero times (in which case we need to
434 // look at the token that follows the
435 // sequence, which may itself be a sequence,
437 on_fail
.react(cx
, sp
,
438 &format
!("`${0}:{1}` is followed by a \
439 sequence repetition, which is not \
440 allowed for `{1}` fragments",
445 // die next iteration
446 Some(&&TokenTree
::Delimited(_
, ref delim
)) => delim
.close_token(),
447 // else, we're at the end of the macro or sequence
448 None
=> follow
.clone()
451 let tok
= if let TokenTree
::Token(_
, ref tok
) = *token
{
457 // If T' is in the set FOLLOW(NT), continue. Else, reject.
458 match (&next_token
, is_in_follow(cx
, &next_token
, &frag_spec
.name
.as_str())) {
460 on_fail
.react(cx
, sp
, &msg
);
463 (&Eof
, _
) => return Some((sp
, tok
.clone())),
464 (_
, Ok(true)) => continue,
465 (next
, Ok(false)) => {
466 on_fail
.react(cx
, sp
, &format
!("`${0}:{1}` is followed by `{2}`, which \
467 is not allowed for `{1}` fragments",
469 token_to_string(next
)));
475 TokenTree
::Sequence(sp
, ref seq
) => {
476 // iii. Else, T is a complex NT.
477 match seq
.separator
{
478 // If T has the form $(...)U+ or $(...)U* for some token U,
479 // run the algorithm on the contents with F set to U. If it
480 // accepts, continue, else, reject.
482 let last
= check_matcher_old(cx
, seq
.tts
.iter(), u
, on_fail
);
484 // Since the delimiter isn't required after the last
485 // repetition, make sure that the *next* token is
486 // sane. This doesn't actually compute the FIRST of
487 // the rest of the matcher yet, it only considers
488 // single tokens and simple NTs. This is imprecise,
489 // but conservatively correct.
490 Some((span
, tok
)) => {
491 let fol
= match tokens
.peek() {
492 Some(&&TokenTree
::Token(_
, ref tok
)) => tok
.clone(),
493 Some(&&TokenTree
::Delimited(_
, ref delim
)) =>
496 on_fail
.react(cx
, sp
, "sequence repetition followed by \
497 another sequence repetition, which is not allowed");
502 check_matcher_old(cx
, once(&TokenTree
::Token(span
, tok
.clone())),
508 // If T has the form $(...)+ or $(...)*, run the algorithm
509 // on the contents with F set to the token following the
510 // sequence. If it accepts, continue, else, reject.
512 let fol
= match tokens
.peek() {
513 Some(&&TokenTree
::Token(_
, ref tok
)) => tok
.clone(),
514 Some(&&TokenTree
::Delimited(_
, ref delim
)) => delim
.close_token(),
516 on_fail
.react(cx
, sp
, "sequence repetition followed by another \
517 sequence repetition, which is not allowed");
522 check_matcher_old(cx
, seq
.tts
.iter(), &fol
, on_fail
)
526 TokenTree
::Token(..) => {
527 // i. If T is not an NT, continue.
530 TokenTree
::Delimited(_
, ref tts
) => {
531 // if we don't pass in that close delimiter, we'll incorrectly consider the matcher
532 // `{ $foo:ty }` as having a follow that isn't `RBrace`
533 check_matcher_old(cx
, tts
.tts
.iter(), &tts
.close_token(), on_fail
)
540 fn check_matcher_new(cx
: &mut ExtCtxt
, matcher
: &[TokenTree
], on_fail
: &mut OnFail
) {
541 let first_sets
= FirstSets
::new(matcher
);
542 let empty_suffix
= TokenSet
::empty();
543 check_matcher_core(cx
, &first_sets
, matcher
, &empty_suffix
, on_fail
);
546 // The FirstSets for a matcher is a mapping from subsequences in the
547 // matcher to the FIRST set for that subsequence.
549 // This mapping is partially precomputed via a backwards scan over the
550 // token trees of the matcher, which provides a mapping from each
551 // repetition sequence to its FIRST set.
553 // (Hypothetically sequences should be uniquely identifiable via their
554 // spans, though perhaps that is false e.g. for macro-generated macros
555 // that do not try to inject artificial span information. My plan is
556 // to try to catch such cases ahead of time and not include them in
557 // the precomputed mapping.)
559 // this maps each TokenTree::Sequence `$(tt ...) SEP OP` that is uniquely identified by its
560 // span in the original matcher to the First set for the inner sequence `tt ...`.
562 // If two sequences have the same span in a matcher, then map that
563 // span to None (invalidating the mapping here and forcing the code to
565 first
: HashMap
<Span
, Option
<TokenSet
>>,
569 fn new(tts
: &[TokenTree
]) -> FirstSets
{
570 let mut sets
= FirstSets { first: HashMap::new() }
;
571 build_recur(&mut sets
, tts
);
574 // walks backward over `tts`, returning the FIRST for `tts`
575 // and updating `sets` at the same time for all sequence
576 // substructure we find within `tts`.
577 fn build_recur(sets
: &mut FirstSets
, tts
: &[TokenTree
]) -> TokenSet
{
578 let mut first
= TokenSet
::empty();
579 for tt
in tts
.iter().rev() {
581 TokenTree
::Token(sp
, ref tok
) => {
582 first
.replace_with((sp
, tok
.clone()));
584 TokenTree
::Delimited(_
, ref delimited
) => {
585 build_recur(sets
, &delimited
.tts
[..]);
586 first
.replace_with((delimited
.open_span
,
587 Token
::OpenDelim(delimited
.delim
)));
589 TokenTree
::Sequence(sp
, ref seq_rep
) => {
590 let subfirst
= build_recur(sets
, &seq_rep
.tts
[..]);
592 match sets
.first
.entry(sp
) {
593 Entry
::Vacant(vac
) => {
594 vac
.insert(Some(subfirst
.clone()));
596 Entry
::Occupied(mut occ
) => {
597 // if there is already an entry, then a span must have collided.
598 // This should not happen with typical macro_rules macros,
599 // but syntax extensions need not maintain distinct spans,
600 // so distinct syntax trees can be assigned the same span.
601 // In such a case, the map cannot be trusted; so mark this
602 // entry as unusable.
607 // If the sequence contents can be empty, then the first
608 // token could be the separator token itself.
610 if let (Some(ref sep
), true) = (seq_rep
.separator
.clone(),
611 subfirst
.maybe_empty
) {
612 first
.add_one_maybe((sp
, sep
.clone()));
615 // Reverse scan: Sequence comes before `first`.
616 if subfirst
.maybe_empty
|| seq_rep
.op
== ast
::KleeneOp
::ZeroOrMore
{
617 // If sequence is potentially empty, then
618 // union them (preserving first emptiness).
619 first
.add_all(&TokenSet { maybe_empty: true, ..subfirst }
);
621 // Otherwise, sequence guaranteed
622 // non-empty; replace first.
633 // walks forward over `tts` until all potential FIRST tokens are
635 fn first(&self, tts
: &[TokenTree
]) -> TokenSet
{
636 let mut first
= TokenSet
::empty();
637 for tt
in tts
.iter() {
638 assert
!(first
.maybe_empty
);
640 TokenTree
::Token(sp
, ref tok
) => {
641 first
.add_one((sp
, tok
.clone()));
644 TokenTree
::Delimited(_
, ref delimited
) => {
645 first
.add_one((delimited
.open_span
,
646 Token
::OpenDelim(delimited
.delim
)));
649 TokenTree
::Sequence(sp
, ref seq_rep
) => {
650 match self.first
.get(&sp
) {
651 Some(&Some(ref subfirst
)) => {
653 // If the sequence contents can be empty, then the first
654 // token could be the separator token itself.
656 if let (Some(ref sep
), true) = (seq_rep
.separator
.clone(),
657 subfirst
.maybe_empty
) {
658 first
.add_one_maybe((sp
, sep
.clone()));
661 assert
!(first
.maybe_empty
);
662 first
.add_all(subfirst
);
663 if subfirst
.maybe_empty
|| seq_rep
.op
== ast
::KleeneOp
::ZeroOrMore
{
664 // continue scanning for more first
665 // tokens, but also make sure we
666 // restore empty-tracking state
667 first
.maybe_empty
= true;
675 panic
!("assume all sequences have (unique) spans for now");
679 panic
!("We missed a sequence during FirstSets construction");
686 // we only exit the loop if `tts` was empty or if every
687 // element of `tts` matches the empty sequence.
688 assert
!(first
.maybe_empty
);
693 // A set of Tokens, which may include MatchNt tokens (for
694 // macro-by-example syntactic variables). It also carries the
695 // `maybe_empty` flag; that is true if and only if the matcher can
696 // match an empty token sequence.
698 // The First set is computed on submatchers like `$($a:expr b),* $(c)* d`,
699 // which has corresponding FIRST = {$a:expr, c, d}.
700 // Likewise, `$($a:expr b),* $(c)+ d` has FIRST = {$a:expr, c}.
702 // (Notably, we must allow for *-op to occur zero times.)
703 #[derive(Clone, Debug)]
705 tokens
: Vec
<(Span
, Token
)>,
710 // Returns a set for the empty sequence.
711 fn empty() -> Self { TokenSet { tokens: Vec::new(), maybe_empty: true }
}
713 // Returns the set `{ tok }` for the single-token (and thus
714 // non-empty) sequence [tok].
715 fn singleton(tok
: (Span
, Token
)) -> Self {
716 TokenSet { tokens: vec![tok], maybe_empty: false }
719 // Changes self to be the set `{ tok }`.
720 // Since `tok` is always present, marks self as non-empty.
721 fn replace_with(&mut self, tok
: (Span
, Token
)) {
723 self.tokens
.push(tok
);
724 self.maybe_empty
= false;
727 // Changes self to be the empty set `{}`; meant for use when
728 // the particular token does not matter, but we want to
729 // record that it occurs.
730 fn replace_with_irrelevant(&mut self) {
732 self.maybe_empty
= false;
735 // Adds `tok` to the set for `self`, marking sequence as non-empy.
736 fn add_one(&mut self, tok
: (Span
, Token
)) {
737 if !self.tokens
.contains(&tok
) {
738 self.tokens
.push(tok
);
740 self.maybe_empty
= false;
743 // Adds `tok` to the set for `self`. (Leaves `maybe_empty` flag alone.)
744 fn add_one_maybe(&mut self, tok
: (Span
, Token
)) {
745 if !self.tokens
.contains(&tok
) {
746 self.tokens
.push(tok
);
750 // Adds all elements of `other` to this.
752 // (Since this is a set, we filter out duplicates.)
754 // If `other` is potentially empty, then preserves the previous
755 // setting of the empty flag of `self`. If `other` is guaranteed
756 // non-empty, then `self` is marked non-empty.
757 fn add_all(&mut self, other
: &Self) {
758 for tok
in &other
.tokens
{
759 if !self.tokens
.contains(tok
) {
760 self.tokens
.push(tok
.clone());
763 if !other
.maybe_empty
{
764 self.maybe_empty
= false;
769 // Checks that `matcher` is internally consistent and that it
770 // can legally by followed by a token N, for all N in `follow`.
771 // (If `follow` is empty, then it imposes no constraint on
774 // Returns the set of NT tokens that could possibly come last in
775 // `matcher`. (If `matcher` matches the empty sequence, then
776 // `maybe_empty` will be set to true.)
778 // Requires that `first_sets` is pre-computed for `matcher`;
779 // see `FirstSets::new`.
780 fn check_matcher_core(cx
: &mut ExtCtxt
,
781 first_sets
: &FirstSets
,
782 matcher
: &[TokenTree
],
784 on_fail
: &mut OnFail
) -> TokenSet
{
785 use print
::pprust
::token_to_string
;
787 let mut last
= TokenSet
::empty();
789 // 2. For each token and suffix [T, SUFFIX] in M:
790 // ensure that T can be followed by SUFFIX, and if SUFFIX may be empty,
791 // then ensure T can also be followed by any element of FOLLOW.
792 'each_token
: for i
in 0..matcher
.len() {
793 let token
= &matcher
[i
];
794 let suffix
= &matcher
[i
+1..];
796 let build_suffix_first
= || {
797 let mut s
= first_sets
.first(suffix
);
798 if s
.maybe_empty { s.add_all(follow); }
802 // (we build `suffix_first` on demand below; you can tell
803 // which cases are supposed to fall through by looking for the
804 // initialization of this variable.)
807 // First, update `last` so that it corresponds to the set
808 // of NT tokens that might end the sequence `... token`.
810 TokenTree
::Token(sp
, ref tok
) => {
811 let can_be_followed_by_any
;
812 if let Err(bad_frag
) = has_legal_fragment_specifier(tok
) {
813 on_fail
.react(cx
, sp
, &format
!("invalid fragment specifier `{}`", bad_frag
));
814 // (This eliminates false positives and duplicates
815 // from error messages.)
816 can_be_followed_by_any
= true;
818 can_be_followed_by_any
= token_can_be_followed_by_any(tok
);
821 if can_be_followed_by_any
{
822 // don't need to track tokens that work with any,
823 last
.replace_with_irrelevant();
824 // ... and don't need to check tokens that can be
825 // followed by anything against SUFFIX.
826 continue 'each_token
;
828 last
.replace_with((sp
, tok
.clone()));
829 suffix_first
= build_suffix_first();
832 TokenTree
::Delimited(_
, ref d
) => {
833 let my_suffix
= TokenSet
::singleton((d
.close_span
, Token
::CloseDelim(d
.delim
)));
834 check_matcher_core(cx
, first_sets
, &d
.tts
, &my_suffix
, on_fail
);
835 // don't track non NT tokens
836 last
.replace_with_irrelevant();
838 // also, we don't need to check delimited sequences
840 continue 'each_token
;
842 TokenTree
::Sequence(sp
, ref seq_rep
) => {
843 suffix_first
= build_suffix_first();
844 // The trick here: when we check the interior, we want
845 // to include the separator (if any) as a potential
846 // (but not guaranteed) element of FOLLOW. So in that
847 // case, we make a temp copy of suffix and stuff
848 // delimiter in there.
850 // FIXME: Should I first scan suffix_first to see if
851 // delimiter is already in it before I go through the
852 // work of cloning it? But then again, this way I may
853 // get a "tighter" span?
855 let my_suffix
= if let Some(ref u
) = seq_rep
.separator
{
856 new
= suffix_first
.clone();
857 new
.add_one_maybe((sp
, u
.clone()));
863 // At this point, `suffix_first` is built, and
864 // `my_suffix` is some TokenSet that we can use
865 // for checking the interior of `seq_rep`.
866 let next
= check_matcher_core(cx
, first_sets
, &seq_rep
.tts
, my_suffix
, on_fail
);
867 if next
.maybe_empty
{
873 // the recursive call to check_matcher_core already ran the 'each_last
874 // check below, so we can just keep going forward here.
875 continue 'each_token
;
879 // (`suffix_first` guaranteed initialized once reaching here.)
881 // Now `last` holds the complete set of NT tokens that could
882 // end the sequence before SUFFIX. Check that every one works with `suffix`.
883 'each_last
: for &(_sp
, ref t
) in &last
.tokens
{
884 if let MatchNt(ref name
, ref frag_spec
, _
, _
) = *t
{
885 for &(sp
, ref next_token
) in &suffix_first
.tokens
{
886 match is_in_follow(cx
, next_token
, &frag_spec
.name
.as_str()) {
888 on_fail
.react(cx
, sp
, &msg
);
889 // don't bother reporting every source of
890 // conflict for a particular element of `last`.
895 let may_be
= if last
.tokens
.len() == 1 &&
896 suffix_first
.tokens
.len() == 1
905 &format
!("`${name}:{frag}` {may_be} followed by `{next}`, which \
906 is not allowed for `{frag}` fragments",
909 next
=token_to_string(next_token
),
921 fn token_can_be_followed_by_any(tok
: &Token
) -> bool
{
922 if let &MatchNt(_
, ref frag_spec
, _
, _
) = tok
{
923 frag_can_be_followed_by_any(&frag_spec
.name
.as_str())
925 // (Non NT's can always be followed by anthing in matchers.)
930 /// True if a fragment of type `frag` can be followed by any sort of
931 /// token. We use this (among other things) as a useful approximation
932 /// for when `frag` can be followed by a repetition like `$(...)*` or
933 /// `$(...)+`. In general, these can be a bit tricky to reason about,
934 /// so we adopt a conservative position that says that any fragment
935 /// specifier which consumes at most one token tree can be followed by
936 /// a fragment specifier (indeed, these fragments can be followed by
937 /// ANYTHING without fear of future compatibility hazards).
938 fn frag_can_be_followed_by_any(frag
: &str) -> bool
{
940 "item" | // always terminated by `}` or `;`
941 "block" | // exactly one token tree
942 "ident" | // exactly one token tree
943 "meta" | // exactly one token tree
944 "tt" => // exactly one token tree
952 /// True if a fragment of type `frag` can be followed by any sort of
953 /// token. We use this (among other things) as a useful approximation
954 /// for when `frag` can be followed by a repetition like `$(...)*` or
955 /// `$(...)+`. In general, these can be a bit tricky to reason about,
956 /// so we adopt a conservative position that says that any fragment
957 /// specifier which consumes at most one token tree can be followed by
958 /// a fragment specifier (indeed, these fragments can be followed by
959 /// ANYTHING without fear of future compatibility hazards).
960 fn can_be_followed_by_any(frag
: &str) -> bool
{
962 "item" | // always terminated by `}` or `;`
963 "block" | // exactly one token tree
964 "ident" | // exactly one token tree
965 "meta" | // exactly one token tree
966 "tt" => // exactly one token tree
974 /// True if `frag` can legally be followed by the token `tok`. For
975 /// fragments that can consume an unbounded number of tokens, `tok`
976 /// must be within a well-defined follow set. This is intended to
977 /// guarantee future compatibility: for example, without this rule, if
978 /// we expanded `expr` to include a new binary operator, we might
979 /// break macros that were relying on that binary operator as a
981 // when changing this do not forget to update doc/book/macros.md!
982 fn is_in_follow(_
: &ExtCtxt
, tok
: &Token
, frag
: &str) -> Result
<bool
, String
> {
983 if let &CloseDelim(_
) = tok
{
984 // closing a token tree can never be matched by any fragment;
985 // iow, we always require that `(` and `)` match, etc.
990 // since items *must* be followed by either a `;` or a `}`, we can
991 // accept anything after them
995 // anything can follow block, the braces provide an easy boundary to
1001 FatArrow
| Comma
| Semi
=> Ok(true),
1007 FatArrow
| Comma
| Eq
| BinOp(token
::Or
) => Ok(true),
1008 Ident(i
, _
) if (i
.name
.as_str() == "if" ||
1009 i
.name
.as_str() == "in") => Ok(true),
1015 OpenDelim(token
::DelimToken
::Brace
) | OpenDelim(token
::DelimToken
::Bracket
) |
1016 Comma
| FatArrow
| Colon
| Eq
| Gt
| Semi
| BinOp(token
::Or
) => Ok(true),
1017 Ident(i
, _
) if (i
.name
.as_str() == "as" ||
1018 i
.name
.as_str() == "where") => Ok(true),
1023 // being a single token, idents are harmless
1027 // being either a single token or a delimited sequence, tt is
1031 _
=> Err(format
!("invalid fragment specifier `{}`", frag
))
1036 fn has_legal_fragment_specifier(tok
: &Token
) -> Result
<(), String
> {
1037 debug
!("has_legal_fragment_specifier({:?})", tok
);
1038 if let &MatchNt(_
, ref frag_spec
, _
, _
) = tok
{
1039 let s
= &frag_spec
.name
.as_str();
1040 if !is_legal_fragment_specifier(s
) {
1041 return Err(s
.to_string());
1047 fn is_legal_fragment_specifier(frag
: &str) -> bool
{
1049 "item" | "block" | "stmt" | "expr" | "pat" |
1050 "path" | "ty" | "ident" | "meta" | "tt" => true,