duplicated user destructor for lookahead

[Joel E. Denny]

In the case of an error during a split GLR parse, a bison-2.0b-generated
parser sometimes invokes the user destructor for the lookahead token
twice.  This can lead to seg faults. It invokes it once on the token
because it's a lookahead.  It invokes it a second time because it's
already shifted onto one of the stacks.  The reason the parser still sees
the token as a lookahead after shifting it onto a stack is that it has not
yet shifted it onto all the stacks.

The test case at the end of this email demonstrates the problem by (1)
#define YYSTACKEXPANDABLE 0, (2) overflowing the initial stack size with
an infinite input and an ambiguous right recursion, and (3) detecting a
duplicate destructor call on any token by keeping a count of the
destructor calls as the token's semantic value.  If bison passes the test
case, the parser writes only `memory exhausted' to stderr.  If not, it
also writes `Destructor called on same value X times.' to stderr, where X
is 2 for bison-2.0b (or the latest CVS sources).  Exit status should be 0.

Below the test case is a patch.  The idea is straight-forward, but the
implementation could possibly be improved by some function encapsulation.
I added a bool yytoken_shifted alongside yytoken.  It tracks whether the
parser has shifted yytoken onto any stack yet.  Like yytoken, it is a
local variable in yyparse().  There's also a yytoken_shiftedp like
yytokenp in yyGLRStack.  The parser does not call the user destructor for
the lookahead if yytoken_shifted.

Joel

-----------------------------------------------
%{
  #include <stdio.h>
  #include <stdlib.h>
  static void yyerror (char const *);
  static int yylex (void);
  #define YYSTACKEXPANDABLE 0
%}

%glr-parser
%union { int *count; }
%type <count> 'a'

%destructor {
  if ((*$$)++)
    fprintf (stderr, "Destructor called on same value %d times.\n", *$$);
} 'a'

%%

start:
  stack1 start
  | stack2 start
  |
  ;
stack1: 'a' ;
stack2: 'a' ;

%%

static int
yylex (void)
{
  yylval.count = malloc(sizeof(int));
  if (!yylval.count)
    {
      fprintf (stderr, "Test inconclusive.\n");
      exit( EXIT_FAILURE );
    }
  *yylval.count = 0;
  return 'a';
}

static void
yyerror (char const *msg)
{
  fprintf (stderr, "%s\n", msg);
}

int
main (void)
{
  return !yyparse ();
}
-----------------------------------------------

Index: data/glr.c
===================================================================
RCS file: /cvsroot/bison/bison/data/glr.c,v
retrieving revision 1.117
diff -p -u -r1.117 glr.c
--- data/glr.c  26 Aug 2005 20:16:16 -0000      1.117
+++ data/glr.c  30 Aug 2005 15:47:20 -0000
@@ -728,6 +728,7 @@ struct yyGLRStack {
   int yyrawchar;
 ])[
   yySymbol* yytokenp;
+  yybool* yytoken_shiftedp;
   jmp_buf yyexception_buffer;
   yyGLRStackItem* yyitems;
   yyGLRStackItem* yynextFree;
@@ -1751,6 +1752,7 @@ yyprocessOneStack (yyGLRStack* yystack,
   const short int* yyconflicts;
   yyRuleNum yyrule;
   yySymbol* const yytokenp = yystack->yytokenp;
+  yybool* const yytoken_shiftedp = yystack->yytoken_shiftedp;

   while (yystack->yytops.yystates[yyk] != NULL)
     {
@@ -1779,6 +1781,7 @@ yyprocessOneStack (yyGLRStack* yystack,
              YYDPRINTF ((stderr, "Reading a token: "));
              yychar = YYLEX;
              *yytokenp = YYTRANSLATE (yychar);
+             *yytoken_shiftedp = yyfalse;
              YY_SYMBOL_PRINT ("Next token is", *yytokenp, yylvalp, yyllocp);
            }
          yygetLRActions (yystate, *yytokenp, &yyaction, &yyconflicts);
@@ -1800,6 +1803,7 @@ yyprocessOneStack (yyGLRStack* yystack,
            {
              YYDPRINTF ((stderr, "On stack %lu, ", (unsigned long int) yyk));
              YY_SYMBOL_PRINT ("shifting", *yytokenp, yylvalp, yyllocp);
+             *yystack->yytoken_shiftedp = yytrue;
              yyglrShift (yystack, yyk, yyaction, yyposn+1,
                          *yylvalp, yyllocp);
              YYDPRINTF ((stderr, "Stack %lu now in state #%d\n",
@@ -1937,6 +1941,7 @@ yyrecoverSyntaxError (yyGLRStack* yystac
                      ]b4_user_formals[)
 {
   yySymbol* const yytokenp = yystack->yytokenp;
+  yybool* const yytoken_shiftedp = yystack->yytoken_shiftedp;
   size_t yyk;
   int yyj;

@@ -1962,6 +1967,7 @@ yyrecoverSyntaxError (yyGLRStack* yystac
        YYDPRINTF ((stderr, "Reading a token: "));
        yychar = YYLEX;
        *yytokenp = YYTRANSLATE (yychar);
+       *yytoken_shiftedp = yyfalse;
        YY_SYMBOL_PRINT ("Next token is", *yytokenp, yylvalp, yyllocp);
        yyj = yypact[yystack->yytops.yystates[0]->yylrState];
        if (yyis_pact_ninf (yyj))
@@ -2044,6 +2050,7 @@ yyrecoverSyntaxError (yyGLRStack* yystac
 {
   int yyresult;
   yySymbol yytoken;
+  yybool yytoken_shifted;
   yyGLRStack yystack;
   size_t yyposn;
 ]b4_pure_if(
@@ -2085,6 +2092,7 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
     case 2: goto yyexhaustedlab;
     }
   yystack.yytokenp = &yytoken;
+  yystack.yytoken_shiftedp = &yytoken_shifted;
   yyglrShift (&yystack, 0, 0, 0, yylval, &yylloc);
   yyposn = 0;

@@ -2122,6 +2130,7 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
                  YYDPRINTF ((stderr, "Reading a token: "));
                  yychar = YYLEX;
                  yytoken = YYTRANSLATE (yychar);
+                 yytoken_shifted = yyfalse;
                   YY_SYMBOL_PRINT ("Next token is", yytoken, yylvalp, yyllocp);
                }
              yygetLRActions (yystate, yytoken, &yyaction, &yyconflicts);
@@ -2197,7 +2206,7 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
   /* Fall through.  */

  yyreturn:
-  if (yytoken != YYEOF && yytoken != YYEMPTY)
+  if (yytoken != YYEOF && yytoken != YYEMPTY && !yytoken_shifted)
     yydestruct ("Cleanup: discarding lookahead",
                 yytoken, yylvalp]b4_location_if([, yyllocp])[);