330975 - Mishandling of assignment around the ternary operator

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P4)

Description

[Blake Kaplan (:mrbkap) (inactive)]

Dave Herman reported this to me.

Minimal testcase:

js> evaluate('1 ? a = "pass" : 0')
:1: Invalid label

Comment 1

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: Proposed fix

This seems to be the right thing -- assignment binds tighter than either of the conditionals.

Comment 2

[Brendan Eich [:brendan]]

Comment on attachment 215547 [details] [diff] [review]
Proposed fix

> var opPrecedence = {
>     SEMICOLON: 0,
>     COMMA: 1,
>-    ASSIGN: 2,
>     HOOK: 3, COLON: 3, CONDITIONAL: 3,
>-    OR: 4,
>+    ASSIGN: 4, OR: 4,
>     AND: 5,

ASSIGN and OR should not have the same precedence, so don't skip over 2 in the new order.

But I still have no cvs setup due to disk corruption, so no narcissus source.  I'd like to noodle on this further.

/be

Comment 3

[Brendan Eich [:brendan]]

In C-based operator grammars, = is looser than ?: -- x = a ? b : c is parsed as x = (a ? b : c), not as (x = a) ? b : c.  So it's not accurate to say that = binds tighter than ?:.  So something peculiar to the ternary operator is biting here.

/be

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

Except that this case shows that = binds tighter than :. Maybe = needs a precedence of 2.5 and : needs a precedence of 2?

Comment 5

[Brendan Eich [:brendan]]

Operator precedence grammars handle possibly-bracketed alternations of operands and binary operators (unary operators are easy to handle too).  Here is an informal description:

* At each operand, shift (push onto an operand stack).

* At each operator, compare its precedence to the top of operator stack's precedence.  While the top stacked operator has higher (use > for right associativity, >= for left) precedence, reduce (pop operator and two operands and combine into a tree node, or evaluate as you go).  Then shift the new operator.

Obviously ?: requires special handling.  Your fix makes sense in light of how the JS grammar allows assignment expressions as "then" and "else" parts (unlike C, which breaks symmetry here).  Did you try a patch?

/be

Comment 6

[Brendan Eich [:brendan]]

(In reply to comment #4)
> Except that this case shows that = binds tighter than :. Maybe = needs a
> precedence of 2.5 and : needs a precedence of 2?

You could just make COLON have precedence 1.5 and leave the rest alone.

/be

Comment 7

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: Patch for ridcule

I'm pretty sure this shot-in-the-dark patch is wrong in some major way, but it isn't obvious to me. With this patch, assignment doesn't have lower precedence than conditionals, but it is right-associative. This is necessary, since otherwise we'll reduce the hook for the assignment, which is not what we want (we don't want to reduce the hook until we're truly done parsing the conditional). What does this patch break?

Comment 8

[Brendan Eich [:brendan]]

Oh, of course -- ASSIGN, HOOK, and COLON must have the same precedence, since the grammar is

CondExpr:
    OrExpr
    OrExpr ? AssignExpr : AssignExpr

(see jsparse.c).

But you do not want to reduce on COLON till a HOOK node tops the stack.  You do not even want reduce called with HOOK on top of the operators stack -- note that it and COLON lack opArity entries!  This is just a bug in Narcissus, but you can't fix it by building on it.

Consider that (a ? b, c : d) is an error -- we never want to reduce COMMA on the stack when scanning COLON.

On the other hand, we want (a ? b : c = d) to parse (a ? b : c) and reduce upon scanning ASSIGN, so this argues that CONDITIONAL must have the same precedence as ASSIGN.

So I say make ASSIGN, HOOK, COLON, and CONDITIONAL all precedence 2, and insert a comment where precedence 3 would go 'splaining all this (in one line :-P).

/be

Comment 9

[Brendan Eich [:brendan]]

Comment on attachment 215616 [details] [diff] [review]
Patch for ridcule

Nothing ridiculous here, but see my previous comment.

> var opPrecedence = {
>     SEMICOLON: 0,
>     COMMA: 1,
>-    ASSIGN: 2,
>-    HOOK: 3, COLON: 3, CONDITIONAL: 3,
>+    ASSIGN: 3, HOOK: 3, COLON: 3, CONDITIONAL: 3,

Rather, let ASSIGN, HOO, COLON, and CONDITIONAL all be 2; and comment at the line where precedence 3 used to be that operator precedence parsing requires this equation.

>             // Use >, not >=, for right-associative ASSIGN and HOOK/COLON.
>-            while (opPrecedence[operators.top().type] > opPrecedence[tt])
>+            while (opPrecedence[operators.top().type] > opPrecedence[tt] ||
>+                   (tt == COLON && operators.length &&
>+                    operators.top().type != HOOK)) {
>                 reduce();
>+            }

Note that right associativity is guaranteed by > instead of >=, independent of precedence.  Note also that you don't need to check operators.length, since operators.top() on an empty stack is 0 and 0.type is undefined.  This is intentional, it simplifies code all around.

/be

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #9)
> Note also that you don't need to check operators.length, since
> operators.top() on an empty stack is 0 and 0.type is undefined.

I mean (0).type or 0..type, of course! ;-)

/be

Comment 11

[Blake Kaplan (:mrbkap) (inactive)]

(In reply to comment #9)
> Note also that you don't need to check operators.length, since
> operators.top() on an empty stack is 0 and 0.type is undefined.

Actually, this was a bug in my patch. Blindly reducing until we found HOOK was wrong (as your (a ? b, c : d) example showed). Instead, I propose making the loop condition be:
(opPrecedence[operators.top().type] > opPrecedence[tt] ||
 (tt == COLON && operators.top().type == ASSIGN))

I can't quite vocalize why ASSIGN is special, though this seems right according to the grammar.

Comment 12

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: Like this

Comment 13

[Brendan Eich [:brendan]]

(In reply to comment #11)
> (In reply to comment #9)
> > Note also that you don't need to check operators.length, since
> > operators.top() on an empty stack is 0 and 0.type is undefined.
> 
> Actually, this was a bug in my patch. Blindly reducing until we found HOOK was
> wrong (as your (a ? b, c : d) example showed). Instead, I propose making the
> loop condition be:
> (opPrecedence[operators.top().type] > opPrecedence[tt] ||
>  (tt == COLON && operators.top().type == ASSIGN))
> 
> I can't quite vocalize why ASSIGN is special, though this seems right according
> to the grammar.

Good point -- but we can avoid this extra test by making ASSIGN > COLON precedence (this does not break the required ASSIGN <= CONDITIONAL precedence relation to avoid reducing (a ? b : c = d) at (a ? b : c), note well).  Well- (i.e, not over-) commented patch?

/be

Comment 14

[Brendan Eich [:brendan]]

(In reply to comment #13)
> Good point -- but we can avoid this extra test by making ASSIGN > COLON
> precedence (this does not break the required ASSIGN <= CONDITIONAL precedence
> relation to avoid reducing (a ? b : c = d) at (a ? b : c), note well).  Well-
> (i.e, not over-) commented patch?

I.e., COLON = 2, ASSIGN = HOOK = CONDITIONAL = 3.

/be

Comment 15

[Brendan Eich [:brendan]]

We could try to rationalize ?: as an operator grammar, so (a @ b ? c @ d @ e : f) where @ is an arbitrary binary operator, can parse as

(((a @ b) ? (c @ d @ e)) : f)

only if @ > ? and @ > :.  Each of ? and : would be binary (so HOOK and COLON would need opArity entries).  Then the challenge would be checking that every HOOK was the left child of a COLON, after which we could combine the nodes into a ternary CONDITIONAL.  Care to try that?

/be

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #15)
> Then the challenge would be checking that every
> HOOK was the left child of a COLON,

and every COLON was the parent of a left-kid HOOK, natch.

/be

Comment 17

[Bob Clary [:bc] (inactive)]

marking in-testsuite- since I think ?: is adequately covered in other tests and |evaluate| is narcissus only.

Comment 18

[Blake Kaplan (:mrbkap) (inactive)]

(In reply to comment #13)
> Good point -- but we can avoid this extra test by making ASSIGN > COLON
> precedence (this does not break the required ASSIGN <= CONDITIONAL precedence

This can't work -- COLON needs to have higher or equal precedence to HOOK or we'll try reducing HOOK on seeing COLON which isn't at all what we want without an extra test to make sure that HOOK is never reduced by COLON, and we're right back where we started.

(In reply to comment #15)
> Care to try that?

I don't have time to try that today, but pushing the conditionals into the regular grammar sounds like a fine idea that's worth trying at some point.

Comment 19

[Brendan Eich [:brendan]]

(In reply to comment #18)
> This can't work -- COLON needs to have higher or equal precedence to HOOK

Duh, sorry -- came full circle there!  Ok, let's try plan B (operator grammar rationalization).

We could use testsuite coverage of narcissus.  Not sure how to rig it up.

/be

Comment 20

[Blake Kaplan (:mrbkap) (inactive)]

(In reply to comment #15)
> We could try to rationalize ?: as an operator grammar, so (a @ b ? c @ d @ e :
> f) where @ is an arbitrary binary operator, can parse as
> 
> (((a @ b) ? (c @ d @ e)) : f)
> 
> only if @ > ? and @ > :

Looking at this again, I don't see how this fixes the original problem here. As we've determined ASSIGN must have equal priority to HOOK (and transitively to COLON), so we still wouldn't reduce the "true" portion (c @ d @ e) of this example, with @ = ASSIGN. Therefore, we'd need a special check for the ASSIGN/COLON behavior anyway.

The real problem here is that ASSIGN is being schitzophrenic wrt its priority. COLON doesn't reduce HOOK, but it does reduce ASSIGN, but HOOK doesn't reduce ASSIGN. I think that my latest patch is the easiest way to contain the damage to this one case.

Comment 21

[Brendan Eich [:brendan]]

(In reply to comment #20)
> The real problem here is that ASSIGN is being schitzophrenic wrt its priority.
> COLON doesn't reduce HOOK, but it does reduce ASSIGN, but HOOK doesn't reduce
> ASSIGN. I think that my latest patch is the easiest way to contain the damage
> to this one case.

Could be.  You're right -- if @ is = and the condition is not parenthesized, then @ < ? but any @ in the "then" or "else" parts must be > :, yet not > ? if nested or chained (a = b ? c = d ? e : f).

Hmm, I wonder whether this is why old C's ternary grammar had different non-terminals in the two positions?  No, that can't be why.  From http://www.lysator.liu.se/c/ANSI-C-grammar-y.html:

conditional_expression
	: logical_or_expression
	| logical_or_expression '?' expression ':' conditional_expression
	;

This production allows , as well as = expressions in the "then" part, but neither without parenthesization in the "else" part.  I had misremembered it with the two parts transposed.

Reviewing now.

/be

Comment 22

[Brendan Eich [:brendan]]

Comment on attachment 215629 [details] [diff] [review]
Like this

Thanks!

/be

Comment 23

[Blake Kaplan (:mrbkap) (inactive)]

Fix checked in.