no users destructors if stack 0 deleted (was: Re: duplicated user destructor for lookahead)

[Joel E. Denny]

On Tue, 20 Sep 2005, Joel E. Denny wrote:

> In the event of memory exhaustion, if stack 0 happens to be marked for 
> deletion (guaranteeing that in a test case is not something I want to 
> think about), no user destructors are called on any symbols.

I created a test case.  #define YYSTACKEXPANDABLE 0 and an ambiguous right 
recursion on infinite input guarantees the memory exhaustion.  The current 
GLR implementation chooses to reduce stack 0 with rule 1, which leads to a 
syntax error, so stack 0 is marked for deletion.  Before the patch, stderr 
contains:

  memory exhausted
  Tokens = x, Destructors = y

where x > y, and exit status is non-zero.  After the patch, x = y, so the 
second line isn't printed, and exit status is 0.

> At first glance, it appears that perhaps another stack could be iterated 
> in its place in order to call user destructors.

I created a patch using this approach.

I've only tested after applying my earlier `duplicated user destructor for 
lookahead' patch, which I cut from the diff for this patch.

Joel

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

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

%destructor {
  destructors += 1;
} 'a'

%%

start:
  ambig0 'a' { destructors += 2; }
  | ambig1 start { destructors += 1; }
  | ambig2 start { destructors += 1; }
  ;

ambig0: 'a' ;
ambig1: 'a' ;
ambig2: 'a' ;

%%

static int
yylex (void)
{
  tokens += 1;
  return 'a';
}

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

int
main (void)
{
  int exit_status;
  exit_status = yyparse ();
  if (tokens != destructors)
    {
      fprintf (stderr, "Tokens = %d, Destructors = %d\n", tokens, destructors);
      return 1;
    }
  return !exit_status;
}

Index: data/glr.c
===================================================================
RCS file: /cvsroot/bison/bison/data/glr.c,v
retrieving revision 1.125
diff -p -u -r1.125 glr.c
--- data/glr.c  20 Sep 2005 07:57:15 -0000      1.125
+++ data/glr.c  26 Sep 2005 23:31:39 -0000
@@ -2227,15 +2260,26 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
     {
       yyGLRState** yystates = yystack.yytops.yystates;
       if (yystates)
-       while (yystates[0])
-         {
-           yyGLRState *yys = yystates[0];
+        {
+         size_t yysize = yystack.yytops.yysize;
+         size_t yyk;
+         for (yyk = 0; yyk < yysize; yyk += 1)
+           {
+             if (yystates[yyk])
+               {
+                 while (yystates[yyk])
+                   {
+                     yyGLRState *yys = yystates[yyk];
 ]b4_location_if([[       yystack.yyerror_range[1].yystate.yyloc = yys->yyloc;]]
-)[         yydestroyGLRState ("Cleanup: popping", yys);
-           yystates[0] = yys->yypred;
-           yystack.yynextFree -= 1;
-           yystack.yyspaceLeft += 1;
-         }
+)[                   yydestroyGLRState ("Cleanup: popping", yys);
+                     yystates[yyk] = yys->yypred;
+                     yystack.yynextFree -= 1;
+                     yystack.yyspaceLeft += 1;
+                   }
+                  break;
+                }
+           }
+       }
       yyfreeGLRStack (&yystack);
     }