Re: FYI: fix bugs when user action cuts nondeterministic parse

[Joel E. Denny]

I didn't quite catch everything last time, and there's still more to 
come....

2006-03-02  Joel E. Denny  <address@hidden>

        Don't leak semantic values for parent RHS when a user action cuts the
        parser, and clean up related code a bit.
        * tests/glr-regression.at (Leaked merged semantic value if user action
        cuts parse) Rename to...
        (Leaked semantic values if user action cuts parse) ... this.  Add check
        for leaked parent RHS values.
        * data/glr.c (yydestroyGLRState): In debugging output, distinguish
        between an unresolved state (non-empty chain of semantic options) and
        an incomplete one (signaled by an empty chain).
        (yyresolveStates): Document the interface.  Move all manipulation of an
        successfully or unsuccessfully resolved yyGLRState to...
        (yyresolveValue): ... here so that yyresolveValue always leaves a
        yyGLRState with consistent data and thus is easier to understand.
        Remove the yyvalp and yylocp parameters since they are always just
        taken from the yys parameter.  When reporting a discarded merged value
        in debugging output, note that it is incompletely merged.  Document the
        interface.
        (yyresolveAction): If resolving any of the RHS states fails, destroy
        them all rather than leaking them.  Thus, as long as user actions are
        written to clean up the RHS correctly, yyresolveAction always cleans up
        the RHS of a semantic option.  Document the interface.

Index: data/glr.c
===================================================================
RCS file: /sources/bison/bison/data/glr.c,v
retrieving revision 1.164
diff -p -u -r1.164 glr.c
--- data/glr.c  27 Feb 2006 19:50:59 -0000      1.164
+++ data/glr.c  2 Mar 2006 01:26:23 -0000
@@ -979,7 +979,10 @@ yydestroyGLRState (char const *yymsg, yy
 #if YYDEBUG
       if (yydebug)
        {
-         YYFPRINTF (stderr, "%s unresolved ", yymsg);
+         if (yys->yysemantics.yyfirstVal)
+           YYFPRINTF (stderr, "%s unresolved ", yymsg);
+         else
+           YYFPRINTF (stderr, "%s incomplete ", yymsg);
          yy_symbol_print (stderr, yystos[yys->yylrState],
                           NULL]b4_location_if([, &yys->yyloc])[]b4_user_args[);
          YYFPRINTF (stderr, "\n");
@@ -1666,9 +1669,14 @@ yypreference (yySemanticOption* y0, yySe
 }
 
 static YYRESULTTAG yyresolveValue (yyGLRState* yys,
-                                  yyGLRStack* yystackp, YYSTYPE* yyvalp,
-                                  YYLTYPE* yylocp]b4_user_formals[);
+                                  yyGLRStack* yystackp]b4_user_formals[);
+
 
+/** Resolve the previous N states starting at and including state S.  If result
+ *  != yyok, some states may have been left unresolved possibly with empty
+ *  semantic option chains.  Regardless of whether result = yyok, each state
+ *  has been left with consistent data so that yydestroyGLRState can be invoked
+ *  if necessary.  */
 static YYRESULTTAG
 yyresolveStates (yyGLRState* yys, int yyn,
                 yyGLRStack* yystackp]b4_user_formals[)
@@ -1678,22 +1686,15 @@ yyresolveStates (yyGLRState* yys, int yy
       YYASSERT (yys->yypred);
       YYCHK (yyresolveStates (yys->yypred, yyn-1, yystackp]b4_user_args[));
       if (! yys->yyresolved)
-       {
-         YYSTYPE yysval;
-         YYRESULTTAG yyflag = yyresolveValue (yys, yystackp, &yysval,
-                                              &yys->yyloc]b4_user_args[);
-         if (yyflag != yyok)
-           {
-             yys->yysemantics.yyfirstVal = NULL;
-             return yyflag;
-           }
-         yys->yysemantics.yysval = yysval;
-         yys->yyresolved = yytrue;
-       }
+       YYCHK (yyresolveValue (yys, yystackp]b4_user_args[));
     }
   return yyok;
 }
 
+/** Resolve the states for the RHS of OPT, perform its user action, and return
+ *  the semantic value and location.  Regardless of whether result = yyok, all
+ *  RHS states have been destroyed (assuming the user action destroys all RHS
+ *  semantic values if invoked).  */
 static YYRESULTTAG
 yyresolveAction (yySemanticOption* yyopt, yyGLRStack* yystackp,
                 YYSTYPE* yyvalp, YYLTYPE* yylocp]b4_user_formals[)
@@ -1703,10 +1704,18 @@ yyresolveAction (yySemanticOption* yyopt
   int yychar_current;
   YYSTYPE yylval_current;
   YYLTYPE yylloc_current;
-  YYRESULTTAG yyresult;
+  YYRESULTTAG yyflag;
 
   yynrhs = yyrhsLength (yyopt->yyrule);
-  YYCHK (yyresolveStates (yyopt->yystate, yynrhs, yystackp]b4_user_args[));
+  yyflag = yyresolveStates (yyopt->yystate, yynrhs, yystackp]b4_user_args[);
+  if (yyflag != yyok)
+    {
+      yyGLRState *yys;
+      for (yys = yyopt->yystate; yynrhs > 0; yys = yys->yypred, yynrhs -= 1)
+       yydestroyGLRState ("Cleanup: popping", yys]b4_user_args[);
+      return yyflag;
+    }
+
   yyrhsVals[YYMAXRHS + YYMAXLEFT].yystate.yypred = 
yyopt->yystate;]b4_location_if([[
   if (yynrhs == 0)
     /* Set default location.  */
@@ -1717,13 +1726,13 @@ yyresolveAction (yySemanticOption* yyopt
   yychar = yyopt->yyrawchar;
   yylval = yyopt->yyval;
   yylloc = yyopt->yyloc;
-  yyresult = yyuserAction (yyopt->yyrule, yynrhs,
+  yyflag = yyuserAction (yyopt->yyrule, yynrhs,
                           yyrhsVals + YYMAXRHS + YYMAXLEFT - 1,
                           yyvalp, yylocp, yystackp]b4_user_args[);
   yychar = yychar_current;
   yylval = yylval_current;
   yylloc = yylloc_current;
-  return yyresult;
+  return yyflag;
 }
 
 #if YYDEBUG
@@ -1797,15 +1806,21 @@ yyreportAmbiguity (yySemanticOption* yyx
 
 
 /** Resolve the ambiguity represented in state S, perform the indicated
- *  actions, and return the result.  */
+ *  actions, and set the semantic value of S.  If result != yyok, the chain of
+ *  semantic options in S has been cleared instead or it has been left
+ *  unmodified except that redundant options may have been removed.  Regardless
+ *  of whether result = yyok, S has been left with consistent data so that
+ *  yydestroyGLRState can be invoked if necessary.  */
 static YYRESULTTAG
-yyresolveValue (yyGLRState* yys, yyGLRStack* yystackp, YYSTYPE* yyvalp,
-               YYLTYPE* yylocp]b4_user_formals[)
+yyresolveValue (yyGLRState* yys, yyGLRStack* yystackp]b4_user_formals[)
 {
   yySemanticOption* yyoptionList = yys->yysemantics.yyfirstVal;
   yySemanticOption* yybest;
   yySemanticOption** yypp;
   yybool yymerge;
+  YYSTYPE yysval;
+  YYRESULTTAG yyflag;
+  YYLTYPE *yylocp = &yys->yyloc;
 
   yybest = yyoptionList;
   yymerge = yyfalse;
@@ -1848,29 +1863,39 @@ yyresolveValue (yyGLRState* yys, yyGLRSt
     {
       yySemanticOption* yyp;
       int yyprec = yydprec[yybest->yyrule];
-      YYCHK (yyresolveAction (yybest, yystackp, yyvalp, yylocp]b4_user_args[));
-      for (yyp = yybest->yynext; yyp != NULL; yyp = yyp->yynext)
-       {
-         if (yyprec == yydprec[yyp->yyrule])
-           {
-             YYSTYPE yyval1;
-             YYLTYPE yydummy;
-             YYRESULTTAG yyflag = yyresolveAction (yyp, yystackp, &yyval1,
-                                                   &yydummy]b4_user_args[);
-             if (yyflag != yyok)
-               {
-                 yydestruct ("Cleanup: discarding merged value",
-                             yystos[yys->yylrState],
-                             yyvalp]b4_location_if([, yylocp])[]b4_user_args[);
-                 return yyflag;
-               }
-             yyuserMerge (yymerger[yyp->yyrule], yyvalp, &yyval1);
-           }
-       }
-      return yyok;
+      yyflag = yyresolveAction (yybest, yystackp, &yysval,
+                               yylocp]b4_user_args[);
+      if (yyflag == yyok)
+       for (yyp = yybest->yynext; yyp != NULL; yyp = yyp->yynext)
+         {
+           if (yyprec == yydprec[yyp->yyrule])
+             {
+               YYSTYPE yysval_other;
+               YYLTYPE yydummy;
+               yyflag = yyresolveAction (yyp, yystackp, &yysval_other,
+                                         &yydummy]b4_user_args[);
+               if (yyflag != yyok)
+                 {
+                   yydestruct ("Cleanup: discarding incompletely merged value 
for",
+                               yystos[yys->yylrState],
+                               &yysval]b4_location_if([, 
yylocp])[]b4_user_args[);
+                   break;
+                 }
+               yyuserMerge (yymerger[yyp->yyrule], &yysval, &yysval_other);
+             }
+         }
+    }
+  else
+    yyflag = yyresolveAction (yybest, yystackp, &yysval, yylocp]b4_user_args[);
+
+  if (yyflag == yyok)
+    {
+      yys->yyresolved = yytrue;
+      yys->yysemantics.yysval = yysval;
     }
   else
-    return yyresolveAction (yybest, yystackp, yyvalp, yylocp]b4_user_args[);
+    yys->yysemantics.yyfirstVal = NULL;
+  return yyflag;
 }
 
 static YYRESULTTAG
Index: tests/glr-regression.at
===================================================================
RCS file: /sources/bison/bison/tests/glr-regression.at,v
retrieving revision 1.29
diff -p -u -r1.29 glr-regression.at
--- tests/glr-regression.at     30 Jan 2006 11:15:15 -0000      1.29
+++ tests/glr-regression.at     2 Mar 2006 01:26:23 -0000
@@ -941,34 +941,75 @@ AT_CLEANUP
 
 
 ## ------------------------------------------------------------------------- ##
-## Leaked merged semantic value if user action cuts parse.                  ##
+## Leaked semantic values if user action cuts parse.                        ##
 ## ------------------------------------------------------------------------- ##
 
-AT_SETUP([Leaked merged semantic value if user action cuts parse])
+AT_SETUP([Leaked semantic values if user action cuts parse])
 
 AT_DATA_GRAMMAR([glr-regr12.y],
 [[
 %glr-parser
 %union { int dummy; }
-%type <dummy> start
-%destructor { has_value = 0; } start
+%token PARENT_RHS_AFTER
+%type <dummy> parent_rhs_before merged PARENT_RHS_AFTER
+%destructor { parent_rhs_before_value = 0; } parent_rhs_before
+%destructor { merged_value = 0; } merged
+%destructor { parent_rhs_after_value = 0; } PARENT_RHS_AFTER
 
 %{
 # include <stdlib.h>
   static int merge (YYSTYPE, YYSTYPE);
   static void yyerror (char const *);
   static int yylex (void);
-  static int has_value = 0;
+  static int parent_rhs_before_value = 0;
+  static int merged_value = 0;
+  static int parent_rhs_after_value = 0;
 # define USE(val)
 %}
 
 %%
 
 start:
-    %merge<merge> { has_value = 1; USE ($$); }
-  | %merge<merge> { USE ($$); YYACCEPT; }
+  alt1 %dprec 1
+  | alt2 %dprec 2
+  ; 
+
+alt1:
+  PARENT_RHS_AFTER {
+    USE ($1);
+    parent_rhs_after_value = 0;
+  }
   ;
 
+alt2:
+  parent_rhs_before merged PARENT_RHS_AFTER {
+    USE (($1, $2, $3));
+    parent_rhs_before_value = 0;
+    merged_value = 0;
+    parent_rhs_after_value = 0;
+  }
+  ;
+
+parent_rhs_before:
+  {
+    USE ($$);
+    parent_rhs_before_value = 1;
+  }
+  ;
+
+merged:
+  %merge<merge> {
+    USE ($$);
+    merged_value = 1;
+  }
+  | cut %merge<merge> {
+    USE ($$);
+    merged_value = 1;
+  }
+  ;
+
+cut: { YYACCEPT; } ;
+
 %%
 
 static int
@@ -988,24 +1029,38 @@ yyerror (char const *msg)
 static int
 yylex (void)
 {
-  return 0;
+  static int const input[] = { PARENT_RHS_AFTER, 0 };
+  static const int *inputp = input;
+  if (*inputp == PARENT_RHS_AFTER)
+    parent_rhs_after_value = 1;
+  return *inputp++;
 }
 
 int
 main (void)
 {
   int exit_status = yyparse ();
-  if (has_value)
+  if (parent_rhs_before_value)
+    {
+      fprintf (stderr, "`parent_rhs_before' destructor not called.\n");
+      exit_status = 1;
+    }
+  if (merged_value)
+    {
+      fprintf (stderr, "`merged' destructor not called.\n");
+      exit_status = 1;
+    }
+  if (parent_rhs_after_value)
     {
-      fprintf (stderr, "Destructor not called.\n");
-      return 1;
+      fprintf (stderr, "`PARENT_RHS_AFTER' destructor not called.\n");
+      exit_status = 1;
     }
   return exit_status;
 }
 ]])
 
 AT_CHECK([[bison -t -o glr-regr12.c glr-regr12.y]], 0, [],
-[glr-regr12.y: conflicts: 1 reduce/reduce
+[glr-regr12.y: conflicts: 1 shift/reduce, 1 reduce/reduce
 ])
 AT_COMPILE([glr-regr12])