Re: Re_ data_glr.c yyinitGLRStack() (fix)

[Paul Eggert]

Paul Hilfinger <address@hidden> writes:

>> By the way, it appears to me that there can be memory leaks in the GLR
>> parser if the stack overflows or the user invokes YYABORT....
>
> Yes, that does seem to be true (not entirely surprising, since the
> destructor code that's now there isn't mine, having been added later
> pretty much in parallel with yacc.c).

Thanks for checking that.  I installed the following patch, to fix
this bug and some others that I discovered in the neighborhood.  The
biggest user-visible change is that the start-symbol's value is now
consistently destroyed after a successful parse.  All 3 parser
skeletons got a little shorter as a result of this patch, which is a
good sign.

2005-07-18  Paul Eggert  <address@hidden>

        Destructor cleanups and regularization among the three skeletons.
        * NEWS: Document the behavior changes.
        * data/glr.c (yyrecoverSyntaxError): Don't bother to pop the
        stack before failing, as the cleanup code will do it for us now.
        * data/lalr1.cc (yyerrlab): Likewise.
        * data/glr.c (yyparse): Pop everything off the stack before
        freeing it, so that destructors get called properly.
        * data/lalr1.cc (yyreturn): Likewise.
        * data/yacc.c (yyreturn): Pop and destroy the start symbol, too.
        This is more consistent.
        * doc/bison.texinfo (Destructor Decl): Mention more reasons
        why destructors might be called.  1.875 -> 2.1.
        (Destructor Decl, Decl Summary, Table of Symbols):
        Some English-language cleanups for %destructor.
        * tests/actions.at (_AT_CHECK_PRINTER_AND_DESTRUCTOR):
        Add output line for destructor of start symbol.
        * tests/calc.at (AT_CHECK_CALC): Add one to line counts,
        because of that same extra output line.

Index: NEWS
===================================================================
RCS file: /cvsroot/bison/bison/NEWS,v
retrieving revision 1.119
diff -p -u -r1.119 NEWS
--- NEWS        19 Jul 2005 00:05:57 -0000      1.119
+++ NEWS        19 Jul 2005 06:55:02 -0000
@@ -15,6 +15,10 @@ Changes in the next version (not yet rel
   has replaced "parser stack overflow", as the old message was not
   always accurate for modern Bison-generated parsers.
 
+* Destructors are now called when the parser aborts, for all symbols left
+  behind on the stack.  Also, the start symbol is now destroyed after a
+  successful parse.  In both cases, the behavior was formerly inconsistent.
+
 The following change was also in version 2.0a, 2005-05-22:
 
 * When generating verbose diagnostics, Bison-generated parsers no longer
Index: data/glr.c
===================================================================
RCS file: /cvsroot/bison/bison/data/glr.c,v
retrieving revision 1.103
diff -p -u -r1.103 glr.c
--- data/glr.c  19 Jul 2005 00:05:57 -0000      1.103
+++ data/glr.c  19 Jul 2005 06:55:02 -0000
@@ -1846,21 +1846,7 @@ yyrecoverSyntaxError (yyGLRStack* yystac
     while (yytrue)
       {
        if (*yytokenp == YYEOF)
-         {
-           /* Now pop stack until empty and fail. */
-           while (yystack->yytops.yystates[0] != NULL)
-             {
-               yyGLRState *yys = yystack->yytops.yystates[0];
-]b4_location_if([[             yystack->yyerror_range[1].yystate.yyloc = 
yys->yyloc;]])[
-               yydestruct ("Error: popping",
-                            yystos[yys->yylrState],
-                           &yys->yysemantics.yysval]b4_location_if([, 
&yys->yyloc])[);
-               yystack->yytops.yystates[0] = yys->yypred;
-               yystack->yynextFree -= 1;
-               yystack->yyspaceLeft += 1;
-             }
-           yyFail (yystack][]b4_lpure_args[, NULL);
-         }
+         yyFail (yystack][]b4_lpure_args[, NULL);
        if (*yytokenp != YYEMPTY)
          {]b4_location_if([[
            /* We throw away the lookahead, but the error range
@@ -2121,6 +2107,19 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
   if (yytoken != YYEOF && yytoken != YYEMPTY)
     yydestruct ("Error: discarding lookahead",
                 yytoken, yylvalp]b4_location_if([, yyllocp])[);
+
+  /* Now pop stack until empty, destroying its entries as we go.  */
+  while (yystack.yytops.yystates[0] != NULL)
+    {
+      yyGLRState *yys = yystack.yytops.yystates[0];
+]b4_location_if([[      yystack.yyerror_range[1].yystate.yyloc = 
yys->yyloc;]])[
+      yydestruct ("Error: popping",
+                 yystos[yys->yylrState],
+                 &yys->yysemantics.yysval]b4_location_if([, &yys->yyloc])[);
+      yystack.yytops.yystates[0] = yys->yypred;
+      yystack.yynextFree -= 1;
+      yystack.yyspaceLeft += 1;
+    }
 
   yyfreeGLRStack (&yystack);
   return yyresult;
Index: data/lalr1.cc
===================================================================
RCS file: /cvsroot/bison/bison/data/lalr1.cc,v
retrieving revision 1.88
diff -p -u -r1.88 lalr1.cc
--- data/lalr1.cc       18 Jul 2005 22:10:15 -0000      1.88
+++ data/lalr1.cc       19 Jul 2005 06:55:02 -0000
@@ -729,23 +729,11 @@ yyerrlab:
       /* If just tried and failed to reuse look-ahead token after an
         error, discard it.  */
 
-      /* Return failure if at end of input.  */
       if (yylooka_ <= yyeof_)
         {
-          /* If at end of input, pop the error token,
-            then the rest of the stack, then return failure.  */
+         /* Return failure if at end of input.  */
          if (yylooka_ == yyeof_)
-            for (;;)
-              {
-                 yyerror_range_[0] = yylocation_stack_[0];
-                 yypop_ ();
-                if (yystate_stack_.height () == 1)
-                  YYABORT;
-                 yydestruct_ ("Error: popping",
-                              yystos_[yystate_stack_[0]],
-                              &yysemantic_stack_[0],
-                              &yylocation_stack_[0]);
-              }
+           YYABORT;
         }
       else
         {
@@ -768,7 +756,7 @@ yyerrorlab:
      YYERROR and the label yyerrorlab therefore never appears in user
      code.  */
   if (false)
-     goto yyerrorlab;
+    goto yyerrorlab;
 
   yyerror_range_[0] = yylocation_stack_[yylen_ - 1];
   yypop_ (yylen_);
@@ -838,6 +826,16 @@ yyabortlab:
 yyreturn:
   if (yylooka_ != yyeof_ && yylooka_ != yyempty_)
     yydestruct_ ("Error: discarding lookahead", yyilooka_, &yylval, &yylloc);
+
+  while (yystate_stack_.height () != 1)
+    {
+      yydestruct_ ("Error: popping",
+                  yystos_[yystate_stack_[0]],
+                  &yysemantic_stack_[0],
+                  &yylocation_stack_[0]);
+      yypop_ ();
+    }
+
   return yyresult_;
 }
 
Index: data/yacc.c
===================================================================
RCS file: /cvsroot/bison/bison/data/yacc.c,v
retrieving revision 1.97
diff -p -u -r1.97 yacc.c
--- data/yacc.c 19 Jul 2005 00:05:57 -0000      1.97
+++ data/yacc.c 19 Jul 2005 06:55:02 -0000
@@ -1220,8 +1220,7 @@ yyerrlab:
 
       if (yychar <= YYEOF)
         {
-          /* If at end of input, pop the error token,
-            then the rest of the stack, then return failure.  */
+         /* Return failure if at end of input.  */
          if (yychar == YYEOF)
            YYABORT;
         }
@@ -1333,16 +1332,12 @@ yyreturn:
   if (yychar != YYEOF && yychar != YYEMPTY)
      yydestruct ("Error: discarding lookahead",
                 yytoken, &yylval]b4_location_if([, &yylloc])[);
-  if (yyssp != yyss)
-    for (;;)
-      {
-]b4_location_if([[     yyerror_range[0] = *yylsp;]])[
-       YYPOPSTACK;
-       if (yyssp == yyss)
-         break;
-       yydestruct ("Error: popping",
-                   yystos[*yyssp], yyvsp]b4_location_if([, yylsp])[);
-      }
+  while (yyssp != yyss)
+    {
+      yydestruct ("Error: popping",
+                 yystos[*yyssp], yyvsp]b4_location_if([, yylsp])[);
+      YYPOPSTACK;
+    }
 #ifndef yyoverflow
   if (yyss != yyssa)
     YYSTACK_FREE (yyss);
Index: doc/bison.texinfo
===================================================================
RCS file: /cvsroot/bison/bison/doc/bison.texinfo,v
retrieving revision 1.152
diff -p -u -r1.152 bison.texinfo
--- doc/bison.texinfo   19 Jul 2005 00:05:57 -0000      1.152
+++ doc/bison.texinfo   19 Jul 2005 06:55:02 -0000
@@ -3792,28 +3792,31 @@ For instance, if your locations use a fi
 @cindex freeing discarded symbols
 @findex %destructor
 
-Some symbols can be discarded by the parser.  For instance, during error
-recovery (@pxref{Error Recovery}), embarrassing symbols already pushed
-on the stack, and embarrassing tokens coming from the rest of the file
-are thrown away until the parser falls on its feet.  If these symbols
-convey heap based information, this memory is lost.  While this behavior
-can be tolerable for batch parsers, such as in compilers, it is not for
-possibly ``never ending'' parsers such as shells, or implementations of
-communication protocols.
+Some symbols can be discarded by the parser.  During error
+recovery (@pxref{Error Recovery}), symbols already pushed
+on the stack and tokens coming from the rest of the file
+are discarded until the parser falls on its feet.  If the parser
+runs out of memory, all the symbols on the stack must be discarded.
+Even if the parser succeeds, it must discard the start symbol.
+
+When discarded symbols convey heap based information, this memory is
+lost.  While this behavior can be tolerable for batch parsers, such as
+in traditional compilers, it is unacceptable for programs like shells
+or protocol implementations that may parse and execute indefinitely.
 
-The @code{%destructor} directive allows for the definition of code that
-is called when a symbol is thrown away.
+The @code{%destructor} directive defines code that
+is called when a symbol is discarded.
 
 @deffn {Directive} %destructor @{ @var{code} @} @var{symbols}
 @findex %destructor
-Declare that the @var{code} must be invoked for each of the
address@hidden that will be discarded by the parser.  The @var{code}
-should use @code{$$} to designate the semantic value associated to the
address@hidden  The additional parser parameters are also available
+Invoke @var{code} whenever the parser discards one of the
address@hidden  Within @var{code}, @code{$$} designates the semantic
+value associated with the discarded symbol.  The additional
+parser parameters are also available
 (@pxref{Parser Function, , The Parser Function @code{yyparse}}).
 
address@hidden:} as of Bison 1.875, this feature is still considered as
-experimental, as there was not enough user feedback.  In particular,
address@hidden:} as of Bison 2.1, this feature is still
+experimental, as there has not been enough user feedback.  In particular,
 the syntax might still change.
 @end deffn
 
@@ -3830,7 +3833,7 @@ For instance:
 @end smallexample
 
 @noindent
-guarantees that when a @code{STRING} or a @code{string} will be discarded,
+guarantees that when a @code{STRING} or a @code{string} is discarded,
 its associated memory will be freed.
 
 Note that in the future, Bison might also consider that right hand side
@@ -3862,8 +3865,11 @@ stacked symbols popped during the first 
 @item
 incoming terminals during the second phase of error recovery,
 @item
-the current look-ahead when the parser aborts (either via an explicit
-call to @code{YYABORT}, or as a consequence of a failed error recovery).
+the current look-ahead and the entire stack when the parser aborts
+(either via an explicit call to @code{YYABORT}, or as a consequence of
+a failed error recovery or of memory exhaustion), and
address@hidden
+the start symbol, when the parser succeeds.
 @end itemize
 
 
@@ -4085,7 +4091,7 @@ above-mentioned declarations and to the 
 @end deffn
 
 @deffn {Directive} %destructor
-Specifying how the parser should reclaim the memory associated to
+Specify how the parser should reclaim the memory associated to
 discarded symbols.  @xref{Destructor Decl, , Freeing Discarded Symbols}.
 @end deffn
 
@@ -7821,7 +7827,7 @@ Bison declaration to create a header fil
 @end deffn
 
 @deffn {Directive} %destructor
-Specifying how the parser should reclaim the memory associated to
+Specify how the parser should reclaim the memory associated to
 discarded symbols.  @xref{Destructor Decl, , Freeing Discarded Symbols}.
 @end deffn
 
Index: tests/actions.at
===================================================================
RCS file: /cvsroot/bison/bison/tests/actions.at,v
retrieving revision 1.51
diff -p -u -r1.51 actions.at
--- tests/actions.at    19 Jul 2005 00:05:57 -0000      1.51
+++ tests/actions.at    19 Jul 2005 06:55:02 -0000
@@ -373,6 +373,7 @@ line (address@hidden): '(' (address@hidden) thing 
(address@hidden
 sending: EOF (address@hidden)
 input (address@hidden): /* Nothing */
 input (address@hidden): line (address@hidden) input (address@hidden)
+Freeing nterm input (address@hidden)
 Successful parse.
 ]])
 
@@ -391,6 +392,7 @@ line (address@hidden): '(' (address@hidden) error (@10-1
 sending: EOF (address@hidden)
 input (address@hidden): /* Nothing */
 input (address@hidden): line (address@hidden) input (address@hidden)
+Freeing nterm input (address@hidden)
 Successful parse.
 ]])
 
Index: tests/calc.at
===================================================================
RCS file: /cvsroot/bison/bison/tests/calc.at,v
retrieving revision 1.75
diff -p -u -r1.75 calc.at
--- tests/calc.at       18 Jul 2005 18:09:40 -0000      1.75
+++ tests/calc.at       19 Jul 2005 06:55:02 -0000
@@ -463,7 +463,7 @@ _AT_CHECK_CALC([$1],
 
 2^2^3 = 256
 (2^2)^3 = 64],
-               [570])
+               [571])
 
 # Some syntax errors.
 _AT_CHECK_CALC_ERROR([$1], [1], [0 0], [13],
@@ -501,7 +501,7 @@ _AT_CHECK_CALC_ERROR([$1], [1], [/dev/nu
 #
 _AT_CHECK_CALC_ERROR([$1], [0],
                      [() + (1 + 1 + 1 +) + (* * *) + (1 * 2 * *) = 1],
-                     [188],
+                     [189],
 [1.1: syntax error, unexpected ')', expecting number or '-' or '(' or '!'
 1.17: syntax error, unexpected ')', expecting number or '-' or '(' or '!'
 1.22: syntax error, unexpected '*', expecting number or '-' or '(' or '!'
@@ -510,10 +510,10 @@ calc: error: 4444 != 1])
 
 # The same, but this time exercising explicitly triggered syntax errors.
 # POSIX says the look-ahead causing the error should not be discarded.
-_AT_CHECK_CALC_ERROR([$1], [0], [(!) + (0 0) = 1], [75],
+_AT_CHECK_CALC_ERROR([$1], [0], [(!) + (0 0) = 1], [76],
 [1.9: syntax error, unexpected number
 calc: error: 2222 != 1])
-_AT_CHECK_CALC_ERROR([$1], [0], [(- *) + (0 0) = 1], [85],
+_AT_CHECK_CALC_ERROR([$1], [0], [(- *) + (0 0) = 1], [86],
 [1.3: syntax error, unexpected '*', expecting number or '-' or '(' or '!'
 1.11: syntax error, unexpected number
 calc: error: 2222 != 1])