On macros future-proofing, FOLLOW sets, and related stuff

[bluss]

What do you mean by ‶plain Rust code″?

I meant without using macros, just regular rust types & traits & functions.

[nrc]

One could think that it would not be a problem since the token has precedence …

I actually like the fact that these changes would make macro pattern matches more order-independent and more like match arms.

I think that relying on procedural macros to fill the gap in expressivity is fine. I intend to add quite a lot of pattern matching functionality to libmacro, so procedural macros ought to be able to customise pattern matching fairly easily and do their own thing.

[LeoTestard]

More order-independent and more like match arms? But match arms are very order-dependent. I’m not sure to understand.

[nikomatsakis]

@LeoTestard I think you are correct that “FOLLOW” sets aren’t really what we need; I think what I was thinking of using is more like “FIRST” sets – that is, if you can be parsing a $t:expr in one arm and token X in the other, then it would be an error unless X is not considered a legal “start” for an expression.

[nikomatsakis]

I actually like the fact that these changes would make macro pattern matches more order-independent and more like match arms.

This confuses me a bit. Maybe I’ve missed some context in the conversation. For one thing, match arms are order dependent, and it seems like order dependence in macros is pretty crucial to being able to write parsers etc (and pretty darn easy to implement). Maybe I am just confused by this phrase “more order independent” – do you just mean because it would forbid careful hacks around what is or is not going to parse as a expr or ty etc?

[LeoTestard]

Yes, that’s more or less the idea of the last algorithm I proposed but just considering it to be an error if X is a legal start for an expression is a very conservative approach. If we rely on order-dependence, we can make it much less conservative by accepting cases where the first arm is obviously more specific that the second, but in this case you have to ‶skip″ the non-terminal to continue the analysis further. The problem is that you don’t know how many tokens you have to skip in the first arm in that case, I don’t know if there is a solution to that problem, I haven’t thought much about it yet. But the conservative approach where you just reject the macro on the first errorneous non trivial case you encounter (i.e. the first case involving a non-terminal) would certainly work.

[nrc]

Sorry, being silly about match arms. I guess there is something about the implicit-ness of macro pattern matching which makes me more uneasy with order dependence than match arms.

[nikomatsakis]

If we rely on order-dependence, we can make it much less conservative by accepting cases where the first arm is obviously more specific that the second, but in this case you have to ‶skip″ the non-terminal to continue the analysis further.

Sorry, I was being a bit imprecise. I did indeed assume that we would take the order into account, so specifically the error would be if the earlier arm matches (e.g.) a nonterminal nt but the token from the latter arm is in FIRST(nt). Under this model, there is no need to “skip” tokens. The goal is basically too show that, if the latter arm is to match, then the former arm must not have matched (specifically, the nonterminals within).

However, I can easily believe that this algorithm is too strong. (Obviously it will depend quite a bit on the FIRST sets etc, but I think we can expect them to be too strong.) It’d be great to start getting more specific, and collecting a catalog of examples (forgive me if I missed some from your original post).

There are two ways I can see going forward. One would be to add a lint, but avoid a hard error: something like, “this macro is fragile and may stop working or work differently as the definition of $expr changes” perhaps with suggestions like “consider reordering these macro arms” when it makes sense.

Another is to strengthen the analysis. This would make sense if we can find enough ways to do it. For example, one scenario that comes to mind is “postfix” disambiguators like:

 $e:expr ";"
 $t:ty ";"

The algorithm I was vaguely sketching above would fail here because the former arm wants an expr but the latter arm wants a ty and FIRST(expr) overlaps with FIRST(ty). I could some form of reasoning based on skipping tokens and the follow sets here that would accept this example (perhaps this is what you were alluding to above).

Thoughts?

[nikomatsakis]

If ak is a token and bk is a non-terminal, accept the macro is the token is not in the FIRST set of this non-terminal. If it is, it’s a tricky case. One could think that it would not be a problem since the token has precedence for being in the first arm so we could just continue to look at ak+1 … an and bk+1 … bn but the problem is that a single non-terminal could match several tokens so I think we cannot tell how much tokens we would need to skip in the first arm.

Is this the case you were alluding to when you mentioned strengthening?

[nikomatsakis]

Also, this has the advantage of being extremely simple to implement, so we can implement it quickly and use crater to see how much code it breaks, and maybe gather statistics on the breakage

Strong +1 to this. It would be very helpful for gaining a good catalog of examples.

[LeoTestard]

Yes, but I don’t think it’s feasible. Consider the following case:

macro_rules! foo(
    ($e:expr) => ...;
    ($x:ident @ $e:expr) => ...
);

This macro needs to be rejected, or at least warned about, because as the definition of expr changes, matches from the second arm will start matching the first. So far, it’s simple. Let’s see what happens when swapping arms:

macro_rules! foo(
    ($x:ident @ $e:expr) => ...;
    ($e:expr) => ...
);

The reasoning is to accept this because the first arm is more specific so no input that matches the second arm should start matching the first if it doesn’t already do. In this specific case it looks easy. But in the general case we just can’t accept that macro, because there could be ambiguities in the rest of the matcher. Consider:

macro_rules! foo(
    ($x:ident @ $e:expr ; $e2:expr) => ...;
    ($e:expr ; $x:ident @ $e2:expr) => ...
);

The problem here is quite obvious. If we stop at the first ‶more specific token in the first arm versus more general NT in the second arm″ case, we can miss possible ambiguities later in the matcher. In this case it looks like the thing to do is to skip until the ‘;’ and then continue the analysis. But is this possible in the general case? There won’t always be a delimiter token to help us, and we can’t know how many tokens we need to skip in the first arm. Furthermore, there could be overlapping NTs, etc. The general case is just too hard for such a simple approach.

[LeoTestard]

Sorry, I was being a bit imprecise. I did indeed assume that we would take the order into account, so specifically the error would be if the earlier arm matches (e.g.) a nonterminal nt but the token from the latter arm is in FIRST(nt). Under this model, there is no need to “skip” tokens. The goal is basically too show that, if the latter arm is to match, then the former arm must not have matched (specifically, the nonterminals within).

In principle, macros where a latter arm can match inputs that are also matched by former arm can be ok. The problem is when input matched by the latter byt not matched by the former could start to match it if the syntax is expanded.

[nikomatsakis]

So let’s dig into this example a bit more. Maybe you need to spell things out a bit for me. As I look at this, I’m not 100% sure where the problem is arising:

macro_rules! foo(
    ($x:ident @ $e:expr ; $e2:expr) => ...;
    ($e:expr ; $x:ident @ $e2:expr) => ...
);

In particular, what is the input that will change and cause things to continue differently? Presumably the idea is that there is some input which today triggers the second arm, but when the definition of expr is expanded to include @ will trigger the first arm, right?

(I had a post with some other thoughts, but I realized I was having trouble making an actual example that caused a problem here, though I see the abstract problem you are concerned with.)

[LeoTestard]

Yeah, right. And that’s why the first example (without the semicolons, with the expr arm first) should be disallowed. In fact it was taken from the running example that triggered this whole issue that used type ascription. Now that type ascription is actually landing, it’s no longer future-proofing, so I changed the example to use a @ instead of a :, but the example remains the same.

macro_rules! foo(
    ($e:expr) => ...;
    ($x:ident @ $e:expr) => ...
);

Let’s invoke the macro with: foo!(x @ x). If expr ::= ident @ expr is ever added as a production to the language, we have a problem. Problem that can be solved by swapping arm, because errorneous input now match the first arm, both before and after extension of the language.

Now for the third example, the one you are talking about:

macro_rules! foo(
    ($x:ident @ $e:expr ; $e2:expr) => ...;
    ($e:expr ; $x:ident @ $e2:expr) => ...
);

Mhhhh I guess I got confused at some point because I can’t find anymore an example that triggers a problem, and thinking about it I believe there is none, I shouldn’t have used the same ‶hypothetical future syntax″ before and after the semicolon. But I think I can find an example of a macro such that, whatever is the order in which you put the arms, you have an error, because the ‶first half″ (before the semicolon) of the first arm is more specific than the ‶first half″ of the second arm, but it’s the opposite for the ‶second halfs″. For example:

macro_rules! foo(
    ($x:ident ; $e2:expr) => ...;
    ($e:expr ; $x:ident @ $e2:expr) => ...
);

Here foo!(x ; x @ x) can change arm if we add the same production as above to the grammar. Ok it’s not exactly the same example but from the point of vue of the algorithm it’s still a more specific token in the first arm versus more general NT in the second arm″ case. And to reject it we need to continue the analysis after the semicolons. Which I think is not possible in the general case, for the reasons I gave in my previous post.

[nikomatsakis]

Great! Yes, I suspected we could find a fix by slightly tweaking the example. So let’s look a this example a bit more:

macro_rules! foo(
    ($x:ident ; $e2:expr) => ...;
    ($e:expr ; $x:ident @ $e2:expr) => ...
);

For background, the original way I thought to do macro future proofing – which we moved away from – was to make it part of the parser semantics. Basically, to parse nonterminal like expr, we would first pull in all token trees up until we find something in the follow-set. So e.g. if we were applying the macro above to x ; x @ x, when we come to the expression, we would pull in the tokens x @ x. We would then parse those tokens as an expression and error out if any of them remain unconsumed (in this case, that’d be an error, because @ x is unconsumed). One problem with this strategy is that the errors occur on the macro use-sites, but in a way the flaw is with the definition of the macro. (I’m also wondering if it is somehow… “incomplete” in that there may still be inputs that would accepted but would change interpretation?)

Anyway, I was hoping to apply that intution I just described in the previous paragraph to the algorithm, but I admit I’m not 100% sure how to do that. I am doubly convinced we ought to measure the real-world impact of the more conservative strategy. =)

[dobenour]

Do we have any concrete examples of recursive macros that will not be possible with the proposed macro!, other than s![]?

Also, I don’t like the reduced expressiveness.

[LeoTestard]

I’m not sure what you mean by ‶find a fix″. What would you do to analyse and reject this example?

Also, pulling tokens until we find something in the FOLLOW set doesn’t sound enough: for expr for example, ; is in the FOLLOW set, but can also appear inside an expression. You could add a condition of balancing delimiters (that is, pulling token trees instead) but even this way, I’m not sure it’s enough. For example, for ty, [ is in the FOLLOW set, and some types can begin with [ so you couldn’t parse them at all with this approach. But maybe I’m missing something here.

[nikomatsakis]

I’m not sure what you mean by ‶find a fix″. What would you do to analyse and reject this example?

Sorry, I meant…find a problematic case

Also, pulling tokens until we find something in the FOLLOW set doesn’t sound enough: for expr for example, ; is in the FOLLOW set, but can also appear inside an expression.

I said pulling token trees, not tokens, for this reason.

[nikomatsakis]

(Still, I’m not yet sure how to turn that “greedy parse” behavior into some sort of algorithm, or if it would work well. I’m curious to know how far we could get with the simpler, conservative variant.)

[LeoTestard]

I’ll work on it. But maybe we should start by specifying the FIRST sets? That is, determine for each NT a set of tokens they’re guaranteed to never begin with. Or should we take the opposite approach? Take the existing set of tokens the NTs can right now begin with and extend it with the tokens we might want to reserve.