yacc bug in reader.c:end_rule()

[Giorgos Keramidas]

On 2007-09-24 18:50, Ruslan Ermilov <ru at freebsd.org> wrote:
> On Sun, Sep 23, 2007 at 04:13:15AM -0700, Darren Reed wrote:
> > Darren Reed wrote:
> >> There's a fairly obvious bug in yacc's reader.c but I'm not sure
> >> what the right fix is.
> >>
> >> Witness:
> >> end_rule()
> >> {
> >>    int i;
> >>
> >>    if (!last_was_action && plhs[nrules]->tag)
> >>    {
> >>       for (i = nitems - 1; pitem[i]; --i) continue;
> >>       if (pitem[i + 1] == 0 || pitem[i+1]->tag != plhs[nrules]->tag)
> >> ...
> >> }
> >>
> >> ...clearly if pitem[nitems-1] == NULL (and nitems is the size of the
> >> array from [0,nitems-1]) then the if() will access beyond the bounds
> >> of the array.
> >>
> >> There's also the question of i being able to run below 0 too here.
>
> Not possible: first four pitem's are explicitly set to NULL in
> reader.c:initialize_grammar().
>
> >> I don't know if the bug is here or if the bug is elsewhere in yacc,
> >> but I doubt that the "fix" is s/i + 1/i/. *Maybe* "i = nitems - 2;"?
> >>
> >> The bug can be masked by using calloc instead of malloc and similar
> >> other tricks, but there is something more fundamentaly wrong here.
> >>
> >> Has anyone else run into this?
> >
> > The following sample grammar will exercise the bug:
> >
> > %{
> > %}
> >
> > %union {
> >        char            *ptr;
> > };
> >
> > %type   <ptr>   test
> > %%
> >
> > test:   | $$ = malloc(2);
>
> It crashes even when written "correctly" as:
>
> test:	| { $$ = malloc(2); }
>
> >        ;
> >
> > %%
> >
> > (The error here is that "test" has an undefined return.)
> >
> Try this patch.  It replaces a non-sense with a fix for the bug.
>
> %%%
> Index: reader.c
> ===================================================================
> RCS file: /home/ncvs/src/usr.bin/yacc/reader.c,v
> retrieving revision 1.19
> diff -u -p -r1.19 reader.c
> --- reader.c	25 Aug 2002 13:23:09 -0000	1.19
> +++ reader.c	24 Sep 2007 14:16:18 -0000
> @@ -1257,7 +1257,7 @@ end_rule()
>      if (!last_was_action && plhs[nrules]->tag)
>      {
>  	for (i = nitems - 1; pitem[i]; --i) continue;
> -	if (pitem[i+1] == 0 || pitem[i+1]->tag != plhs[nrules]->tag)
> +	if (i == nitems - 1 || pitem[i+1]->tag != plhs[nrules]->tag)
>  	    default_action_warning();
>      }
>
> %%%

FWIW, I just verified that the fix works fine, using the same test as
yesterday:

keramida at kobe:/home/keramida/tmp/yt$ make
Warning: Object directory not changed from original /home/keramida/tmp/yt
yacc -d -o foo.c foo.y
yacc: w - line 11 of "foo.y", the default action assigns an undefined value to $$
yacc: w - the symbol $$ is undefined
[...]