code review 6847078: cmd/gc: do not overflow parser stack on a long chain of...

cmd/gc: do not overflow parser stack on a long chain of else if.

Fixes issue 2615.

[remyoudompheng, 2012-11-21 07:28:00]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[dfc, 2012-11-21 07:32:13]

On 2012/11/21 07:28:00, remyoudompheng wrote:
> Hello mailto:golang-dev@googlegroups.com (cc:
mailto:golang-dev@googlegroups.com),
> 
> I'd like you to review this change to
> https://go.googlecode.com/hg/

NOT LGTM. 

Thank you for fixing this longstanding issue but I am concerned that some files
have switched to GPLv3

[minux1, 2012-11-21 07:35:40]

On 2012/11/21 07:32:13, dfc wrote:
> Thank you for fixing this longstanding issue but I am concerned that some
files
> have switched to GPLv3
it's ok because there is a exception clause in bison output files.

/* As a special exception, you may create a larger work that contains
   part or all of the Bison parser skeleton and distribute that work
   under terms of your choice, so long as that work isn't itself a
   parser generator using the skeleton or a modified version thereof
   as a parser skeleton.  Alternatively, if you modify or redistribute
   the parser skeleton itself, you may (at your option) remove this
   special exception, which will cause the skeleton and the resulting
   Bison output files to be licensed under the GNU General Public
   License without this special exception.

   This special exception was added by the Free Software Foundation in
   version 2.2 of Bison.  */

[iant, 2012-11-21 14:28:47]

I agree that this patch is OK with respect to licensing.  The file is already
GPLv2 + exception, this changes it to GPLv3 + exception.  That is OK.

[dfc, 2012-11-21 21:03:43]

Thank you Ian, I withdraw my previous objection.
On 22 Nov 2012 01:28, <iant@golang.org> wrote:

> I agree that this patch is OK with respect to licensing.  The file is
> already GPLv2 + exception, this changes it to GPLv3 + exception.  That
> is OK.
>
>
>
https://codereview.appspot.**com/6847078/<https://codereview.appspot.com/6847...
>

[remyoudompheng, 2012-11-21 21:05:58]

What about the patch contents?

[DMorsing, 2012-11-22 17:26:21]

https://codereview.appspot.com/6847078/diff/4006/src/cmd/gc/go.y
File src/cmd/gc/go.y (right):

https://codereview.appspot.com/6847078/diff/4006/src/cmd/gc/go.y#newcode680
src/cmd/gc/go.y:680: else:
Reorder the rules so that elseblock_list is first, then the rules for else. It's
quite confusing to read about the subelements of a rule before the rule has been
introduced.

https://codereview.appspot.com/6847078/diff/4006/src/cmd/gc/go.y#newcode681
src/cmd/gc/go.y:681: LELSE LIF
This grammar allows for code like:

if true {
} else {
} else {
}

There should be a check for this somewhere, but I'm not sure where it should be.

https://codereview.appspot.com/6847078/diff/4006/src/cmd/gc/go.y#newcode705
src/cmd/gc/go.y:705: node = mal(sizeof *node);
Use list() here

[remyoudompheng, 2012-11-23 20:44:04]

http://codereview.appspot.com/6847078/diff/4006/src/cmd/gc/go.y
File src/cmd/gc/go.y (right):

http://codereview.appspot.com/6847078/diff/4006/src/cmd/gc/go.y#newcode680
src/cmd/gc/go.y:680: else:
A few lines above we have caseblock and then caseblock_list, isn't it consistent
to do the same?

http://codereview.appspot.com/6847078/diff/4006/src/cmd/gc/go.y#newcode705
src/cmd/gc/go.y:705: node = mal(sizeof *node);
On 2012/11/22 17:26:21, DMorsing wrote:
> Use list() here

list flattens OBLOCK nodes, which is not correct here.

[remyoudompheng, 2012-11-23 21:08:52]

Hello golang-dev@googlegroups.com, dave@cheney.net, minux.ma@gmail.com,
iant@golang.org, daniel.morsing@gmail.com (cc: golang-dev@googlegroups.com),

Please take another look.

[DMorsing, 2012-11-23 22:27:40]

LGTM

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y
File src/cmd/gc/go.y (right):

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y#newcode693
src/cmd/gc/go.y:693: elseifblock_list:
Name is getting a bit verbose. Shorten to just elseif_list.

[rsc, 2012-11-26 16:44:22]

Thanks for working on this.

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y
File src/cmd/gc/go.y (right):

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y#newcode693
src/cmd/gc/go.y:693: elseifblock_list:
On 2012/11/23 22:27:40, DMorsing wrote:
> Name is getting a bit verbose. Shorten to just elseif_list.

Agreed.

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y#newcode708
src/cmd/gc/go.y:708: NodeList *node;
$$ = list1($2) no?

https://codereview.appspot.com/6847078/diff/8002/test/fixedbugs/issue2615.go
File test/fixedbugs/issue2615.go (right):

https://codereview.appspot.com/6847078/diff/8002/test/fixedbugs/issue2615.go#...
test/fixedbugs/issue2615.go:1: // compile
Make this a 'run' test and check that it actually compiles correctly.
To do that you will probably have to rewrite the conditions so that they overlap
more.

I suggest:

func test(x [4]uint64) int {
    if x[0]&(1<<0) != 0 {
        return 0
    } else if x[0]&(1<<1) != 0 {
        return 1
    } else ...
    } else if x[3]&(1<<7) != 0 {
        return 199
    } else {
        return 200
    }
    panic("unreachable")
}

This function is a terrible way to find the index of the least significant 1 bit
in the 256-bit input (you could extend it if you wanted).

If you test with ^0, ^(1<<0), ^(1<<1), ^(1<<2), and so on, getting the right
answer will confirm that the tests are executed in order.

Russ

[remyoudompheng, 2012-12-03 13:17:55]

Hello dave@cheney.net, minux.ma@gmail.com, iant@golang.org,
daniel.morsing@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[remyoudompheng, 2012-12-03 13:18:43]

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y
File src/cmd/gc/go.y (right):

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y#newcode693
src/cmd/gc/go.y:693: elseifblock_list:
On 2012/11/26 16:44:23, rsc wrote:
> On 2012/11/23 22:27:40, DMorsing wrote:
> > Name is getting a bit verbose. Shorten to just elseif_list.
> 
> Agreed.

Done.

https://codereview.appspot.com/6847078/diff/8002/src/cmd/gc/go.y#newcode708
src/cmd/gc/go.y:708: NodeList *node;
I cannot do list1 because it flattens OBLOCK nodes, and compound_stmt is
almost(?) always a OBLOCK. 

Do you think I should introduce a version of list1 that preserve the node's
content, or is it OK as is?

https://codereview.appspot.com/6847078/diff/8002/test/fixedbugs/issue2615.go
File test/fixedbugs/issue2615.go (right):

https://codereview.appspot.com/6847078/diff/8002/test/fixedbugs/issue2615.go#...
test/fixedbugs/issue2615.go:1: // compile
On 2012/11/26 16:44:23, rsc wrote:
> Make this a 'run' test and check that it actually compiles correctly.
> To do that you will probably have to rewrite the conditions so that they
overlap
> more.
> 
> I suggest:
> 
> func test(x [4]uint64) int {
>     if x[0]&(1<<0) != 0 {
>         return 0
>     } else if x[0]&(1<<1) != 0 {
>         return 1
>     } else ...
>     } else if x[3]&(1<<7) != 0 {
>         return 199
>     } else {
>         return 200
>     }
>     panic("unreachable")
> }
> 
> This function is a terrible way to find the index of the least significant 1
bit
> in the 256-bit input (you could extend it if you wanted).
> 
> If you test with ^0, ^(1<<0), ^(1<<1), ^(1<<2), and so on, getting the right
> answer will confirm that the tests are executed in order.
> 
> Russ

Done.

[rsc, 2012-12-06 04:50:18]

LGTM w/ the test change passing

https://codereview.appspot.com/6847078/diff/14001/test/fixedbugs/issue2615.go
File test/fixedbugs/issue2615.go (right):

https://codereview.appspot.com/6847078/diff/14001/test/fixedbugs/issue2615.go...
test/fixedbugs/issue2615.go:534: bits[i/64] &= ^(1 << (uint(i) & 63))
This is only testing the first two cases. The rest of the if sequence could be
lost and the test would still pass. Let's test all the branches:

// clear bottom i bits
bits[i/64] ^= 1<<(uint(i)&63 + 1) - 1
for j := i/64 - 1; j >= 0; j-- {
    bits[j] = 0
}

k := test(bits)
if k != i {
    print("test(bits)=", k, " want ", i, "\n")
    panic("failed")
}

[remyoudompheng, 2012-12-06 07:08:04]

Hello dave@cheney.net, minux.ma@gmail.com, iant@golang.org,
daniel.morsing@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[remyoudompheng, 2012-12-06 07:09:24]

*** Submitted as https://code.google.com/p/go/source/detail?r=52c9c412f1f2 ***

cmd/gc: do not overflow parser stack on a long chain of else if.

Fixes issue 2615.

R=dave, minux.ma, iant, daniel.morsing, rsc
CC=golang-dev
https://codereview.appspot.com/6847078