Nested ? matchers can cause the compiler to infinite loop/crash

The following code will cause the compiler to fail:

macro_rules! ex {
    ($($(i:ident)?)+) => { };
}

fn main() {
    ex!();
}

Playground link: https://play.rust-lang.org/?version=beta&mode=debug&edition=2018&gist=acce7614d74028b67c92a79b50b93522

It should error that the inner matcher can match an empty string and reject it, just as it does if * is used in place of ?.

The fix should be very easy, since this was already fixed for * repetitions in #36721 (original bug: #5067):

rust/src/libsyntax/ext/tt/macro_rules.rs

Lines 435 to 440 in 1a3a3df

    
           match *seq_tt { 
        
               TokenTree::MetaVarDecl(_, _, id) => id.name == "vis", 
        
               TokenTree::Sequence(_, ref sub_seq) => 
        
                   sub_seq.op == quoted::KleeneOp::ZeroOrMore, 
        
               _ => false, 
        
           }

Looks like sub_seq.op just needs to be checked against ?, too.

@mark-i-m

cc @mark-i-m

Note that with ? on the outside, this errors properly, although with inconsistent error messages: if the inner repetition uses * only, the error is "repetition matches empty token tree", but it seems that if any of the repetitions are ?, then the error is "multiple successful parses".

The behaviour in my previous comment is because the check for "repetition matches empty token tree" is done at definition time, but does not catch $($($i:ident)*)?; this is caught at expansion time however. Ideally all of this will be moved to definition time and the expansion-time check should probably be a) corrected to address the first comment and b) possibly become an ICE, since it should never be encountered since the RFC 550 rules should eliminate all ambiguity at definition time?

Hmm... I don't really remember how most of this code works...

Just grepping, but it looks like there are a couple of other places we might want to look at:

rust/src/libsyntax/ext/tt/macro_rules.rs

Lines 545 to 554 in 03acbd7

    
           // Reverse scan: Sequence comes before `first`. 
        
           if subfirst.maybe_empty || seq_rep.op == quoted::KleeneOp::ZeroOrMore { 
        
               // If sequence is potentially empty, then 
        
               // union them (preserving first emptiness). 
        
               first.add_all(&TokenSet { maybe_empty: true, ..subfirst }); 
        
           } else { 
        
               // Otherwise, sequence guaranteed 
        
               // non-empty; replace first. 
        
               first = subfirst; 
        
           }

rust/src/libsyntax/ext/tt/macro_rules.rs

Lines 594 to 604 in 03acbd7

    
               if subfirst.maybe_empty || 
        
                  seq_rep.op == quoted::KleeneOp::ZeroOrMore { 
        
                   // continue scanning for more first 
        
                   // tokens, but also make sure we 
        
                   // restore empty-tracking state 
        
                   first.maybe_empty = true; 
        
                   continue; 
        
               } else { 
        
                   return first; 
        
               } 
        
           }

I've opened #57610

Rollup merge of rust-lang#57610 - mark-i-m:nested-matchers, r=petroch…

Navigation Menu

Repository navigation

Nested `?` matchers can cause the compiler to infinite loop/crash #57597

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	match *seq_tt {
	TokenTree::MetaVarDecl(_, _, id) => id.name == "vis",
	TokenTree::Sequence(_, ref sub_seq) =>
	sub_seq.op == quoted::KleeneOp::ZeroOrMore,
	_ => false,
	}

	// Reverse scan: Sequence comes before `first`.
	if subfirst.maybe_empty \|\| seq_rep.op == quoted::KleeneOp::ZeroOrMore {
	// If sequence is potentially empty, then
	// union them (preserving first emptiness).
	first.add_all(&TokenSet { maybe_empty: true, ..subfirst });
	} else {
	// Otherwise, sequence guaranteed
	// non-empty; replace first.
	first = subfirst;
	}

	if subfirst.maybe_empty \|\|
	seq_rep.op == quoted::KleeneOp::ZeroOrMore {
	// continue scanning for more first
	// tokens, but also make sure we
	// restore empty-tracking state
	first.maybe_empty = true;
	continue;
	} else {
	return first;
	}
	}

Nested ? matchers can cause the compiler to infinite loop/crash #57597

Description

Activity

jonas-schievink commented on Jan 14, 2019

Centril commented on Jan 14, 2019

alercah commented on Jan 14, 2019

alercah commented on Jan 14, 2019

mark-i-m commented on Jan 14, 2019

mark-i-m commented on Jan 14, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Nested `?` matchers can cause the compiler to infinite loop/crash #57597