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

[alercah]

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 ?.

[jonas-schievink]

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.

[Centril]

cc @mark-i-m

[alercah]

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".

[alercah]

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?

[mark-i-m]

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;
	}
	}

[mark-i-m]

I've opened #57610