Re: glr-parser: Infinite loop in yymergeOptionSets: yySemanticOption linked list doesn't terminate with NULL [patch]

[Paul Hilfinger]

M. Rosien,

I have found the problem you reported.  A patch is appended (which I
have also checked into the repository).  Looking into this reminded me 
that at some point, it would be nice to redo glr.c with an eye towards
getting closer to the theoretical space efficiency.  Currently, it
causes quite a bit of redundant computation.

Paul Hilfinger

ChangeLog:

2005-05-20  Paul Hilfinger  <address@hidden>

        * data/glr.c (YY_SYMBOL_PRINT): Don't print newline at end to
        fix a small glitch in debugging output.
        (yyprocessOneStack, yyrecoverSyntaxError, yyparse): Print newline
        after YY_SYMBOL_PRINT where needed.

        (struct yyGLRState): Add some comments.
        (struct yySemanticOption): Add some comments.
        (union yyGLRStackItem): Add comment.

        (yymergeOptionSets): Correct this to properly perform the union,
        avoiding infinite reported by Michael Rosien.
        Update comment.

        * tests/glr-regression.at: Add test for GLR merging error reported
        by M. Rosien.
        

Index: bison-1_5.96/data/glr.c
--- bison-1_5.96/data/glr.c Wed, 18 May 2005 21:15:55 -0700 hilfingr 
(glrbison/e/14_glr-parser 1.27.1.33.1.5.1.7 644)
+++ bison-1_5.97/data/glr.c Sat, 21 May 2005 01:32:28 -0700 hilfingr 
(glrbison/e/14_glr-parser 1.27.1.33.1.5.1.8 644)
@@ -509,7 +509,6 @@ do {                                                        
        \
       YYFPRINTF (stderr, "%s ", Title);                                \
       yysymprint (stderr,                                      \
                   Type, Value]b4_location_if([, Location])[);  \
-      YYFPRINTF (stderr, "\n");                                        \
     }                                                          \
 } while (0)
 
@@ -575,15 +574,26 @@ typedef struct yyGLRStack yyGLRStack;
 typedef struct yyGLRStateSet yyGLRStateSet;
 
 struct yyGLRState {
+  /** Type tag: always true. */
   yybool yyisState;
+  /** Type tag for yysemantics. If true, yysval applies, otherwise
+   *  yyfirstVal applies. */
   yybool yyresolved;
+  /** Number of corresponding LALR(1) machine state. */
   yyStateNum yylrState;
+  /** Preceding state in this stack */
   yyGLRState* yypred;
+  /** Source position of the first token produced by my symbol */
   size_t yyposn;
   union {
+    /** First in a chain of alternative reductions producing the
+     *  non-terminal corresponding to this state, threaded through 
+     *  yynext. */
     yySemanticOption* yyfirstVal;
+    /** Semantic value for this state. */
     YYSTYPE yysval;
   } yysemantics;
+  /** Source location for this state. */
   YYLTYPE yyloc;
 };
 
@@ -593,12 +603,19 @@ struct yyGLRStateSet {
 };
 
 struct yySemanticOption {
+  /** Type tag: always false. */
   yybool yyisState;
+  /** Rule number for this reduction */
   yyRuleNum yyrule;
+  /** The last RHS state in the list of states to be reduced. */
   yyGLRState* yystate;
+  /** Next sibling in chain of options. To facilitate merging,
+   *  options are chained in decreasing order by address. */
   yySemanticOption* yynext;
 };
 
+/** Type of the items in the GLR stack. The yyisState field 
+ *  indicates which item of the union is valid. */
 union yyGLRStackItem {
   yyGLRState yystate;
   yySemanticOption yyoption;
@@ -1282,9 +1299,8 @@ yyidenticalOptions (yySemanticOption* yy
     return yyfalse;
 }
 
-/** Assuming identicalOptions (Y0,Y1), (destructively) merge the
- *  alternative semantic values for the RHS-symbols of Y1 into the
- *  corresponding semantic value sets of the symbols of Y0. */
+/** Assuming identicalOptions (Y0,Y1), destructively merge the
+ *  alternative semantic values for the RHS-symbols of Y1 and Y0. */
 static void
 yymergeOptionSets (yySemanticOption* yyy0, yySemanticOption* yyy1)
 {
@@ -1294,16 +1310,46 @@ yymergeOptionSets (yySemanticOption* yyy
        yyn = yyrhsLength (yyy0->yyrule);
        yyn > 0;
        yys0 = yys0->yypred, yys1 = yys1->yypred, yyn -= 1)
-    if (yys0 == yys1)
-      break;
-    else if (! yys0->yyresolved && ! yys1->yyresolved)
-      {
-       yySemanticOption* yyz;
-       for (yyz = yys0->yysemantics.yyfirstVal; yyz->yynext != NULL;
-            yyz = yyz->yynext)
-         continue;
-       yyz->yynext = yys1->yysemantics.yyfirstVal;
-      }
+    {
+      if (yys0 == yys1)
+       break;
+      else if (yys0->yyresolved) 
+       {
+         yys1->yyresolved = yytrue;
+         yys1->yysemantics.yysval = yys0->yysemantics.yysval;
+       }
+      else if (yys1->yyresolved)
+       {
+         yys0->yyresolved = yytrue;
+         yys0->yysemantics.yysval = yys1->yysemantics.yysval;
+       }
+      else 
+       {
+         yySemanticOption** yyz0p;
+         yySemanticOption* yyz1;
+         yyz0p = &yys0->yysemantics.yyfirstVal;
+         yyz1 = yys1->yysemantics.yyfirstVal;
+         while (yytrue)
+           {
+             if (yyz1 == *yyz0p || yyz1 == NULL)
+               break;
+             else if (*yyz0p == NULL)
+               {
+                 *yyz0p = yyz1;
+                 break;
+               }
+             else if (*yyz0p < yyz1)
+               {
+                 yySemanticOption* yyz = *yyz0p;
+                 *yyz0p = yyz1;
+                 yyz1 = yyz1->yynext;
+                 (*yyz0p)->yynext = yyz;
+               }
+             yyz0p = &(*yyz0p)->yynext;
+           }
+         yys1->yysemantics.yyfirstVal = yys0->yysemantics.yyfirstVal;
+       }
+    }
 }
 
 /** Y0 and Y1 represent two possible actions to take in a given
@@ -1579,6 +1625,7 @@ yyprocessOneStack (yyGLRStack* yystack, 
              yychar = YYLEX;
              *yytokenp = YYTRANSLATE (yychar);
              YY_SYMBOL_PRINT ("Next token is", *yytokenp, yylvalp, yyllocp);
+             YYDPRINTF ((stderr, "\n"));
            }
          yygetLRActions (yystate, *yytokenp, &yyaction, &yyconflicts);
 
@@ -1744,6 +1791,7 @@ yyrecoverSyntaxError (yyGLRStack* yystac
        yychar = YYLEX;
        *yytokenp = YYTRANSLATE (yychar);
        YY_SYMBOL_PRINT ("Next token is", *yytokenp, yylvalp, yyllocp);
+       YYDPRINTF ((stderr, "\n"));
        yyj = yypact[yystack->yytops.yystates[0]->yylrState];
        if (yyis_pact_ninf (yyj))
          return;
@@ -1786,6 +1834,7 @@ yyrecoverSyntaxError (yyGLRStack* yystac
              YYLLOC_DEFAULT (yyerrloc, yystack->yyerror_range, 2);]])[
              YY_SYMBOL_PRINT ("Shifting", yystos[yytable[yyj]],
                               yylvalp, &yyerrloc);
+             YYDPRINTF ((stderr, "\n"));
              yyglrShift (yystack, 0, yytable[yyj],
                          yys->yyposn, *yylvalp, &yyerrloc]b4_user_args[);
              yys = yystack->yytops.yystates[0];
@@ -1905,6 +1954,7 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
                  yychar = YYLEX;
                  yytoken = YYTRANSLATE (yychar);
                   YY_SYMBOL_PRINT ("Next token is", yytoken, yylvalp, yyllocp);
+                  YYDPRINTF ((stderr, "\n"));
                }
              yygetLRActions (yystate, yytoken, &yyaction, &yyconflicts);
              if (*yyconflicts != 0)
@@ -1912,6 +1962,7 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
              if (yyisShiftAction (yyaction))
                {
                  YY_SYMBOL_PRINT ("Shifting", yytoken, yylvalp, yyllocp);
+                 YYDPRINTF ((stderr, "\n"));
                  if (yytoken != YYEOF)
                    yytoken = YYEMPTY;
                  yyposn += 1;
Index: bison-1_5.96/tests/glr-regression.at
--- bison-1_5.96/tests/glr-regression.at Wed, 18 May 2005 21:15:55 -0700 
hilfingr (glrbison/h/9_glr-regr1. 1.10 644)
+++ bison-1_5.97/tests/glr-regression.at Sat, 21 May 2005 01:32:28 -0700 
hilfingr (glrbison/h/9_glr-regr1. 1.11 644)
@@ -222,3 +222,105 @@ AT_CHECK([[echo s VARIABLE_3 t v x | ./g
 
 
 AT_CLEANUP
+
+## ------------------------------------------------------------ ##
+## Improper merging of GLR delayed action sets                  ##
+## ------------------------------------------------------------ ##
+
+AT_SETUP([Improper merging of GLR delayed action sets])
+
+AT_DATA_GRAMMAR([glr-regr3.y],
+[[/* Regression Test: Improper merging of GLR delayed action sets.  */
+/* Reported by M. Rosien */
+
+%{
+#include <stdio.h>
+#include <stdarg.h>
+
+static int MergeRule (int x0, int x1);
+static void yyerror(char const * s);
+
+#define RULE(x) (1 << (x))
+
+%}
+
+%glr-parser
+
+%token BAD_CHAR
+%token P1 P2 T1 T2 T3 T4 O1 O2
+
+%%
+
+S : P1 T4 O2 NT6 P2  { printf ("Result: %x\n", $4); }
+;
+
+NT1 : P1 T1 O1 T2 P2 { $$ = RULE(2); }  %merge<MergeRule>
+;
+
+NT2 : NT1             { $$ = RULE(3); } %merge<MergeRule>
+    | P1 NT1 O1 T3 P2 { $$ = RULE(4); } %merge<MergeRule>
+;
+
+NT3 : T3              { $$ = RULE(5); } %merge<MergeRule>
+    | P1 NT1 O1 T3 P2 { $$ = RULE(6); } %merge<MergeRule>
+;
+
+NT4 : NT3              { $$ = RULE(7); } %merge<MergeRule>
+    | NT2              { $$ = RULE(8); } %merge<MergeRule>
+    | P1 NT2 O1 NT3 P2 { $$ = RULE(9); } %merge<MergeRule>
+;
+
+NT5 : NT4              { $$ = RULE(10); } %merge<MergeRule>
+;
+
+NT6 : P1 NT1 O1 T3 P2  { $$ = RULE(11) | $2; } %merge<MergeRule>
+    | NT5              { $$ = RULE(12) | $1; } %merge<MergeRule>
+;
+
+%%
+
+static int MergeRule (int x0, int x1) {
+  return x0 | x1;
+}
+
+static void yyerror(char const * s) {
+  fprintf(stderr,"error: %s\n",s);
+}
+
+FILE *yyin = NULL;
+
+int P[] = { P1, P2 };
+int O[] = { O1, O2 };
+int T[] = { T1, T2, T3, T4 };
+
+int yylex (void)
+{
+  char inp[3];
+  if (fscanf (yyin, "%2s", inp) == EOF)
+    return 0;
+  switch (inp[0]) 
+    {
+    case 'p': return P[inp[1] - '1'];
+    case 't': return T[inp[1] - '1'];
+    case 'o': return O[inp[1] - '1'];
+    }
+  return BAD_CHAR;
+}
+
+int main(int argc, char* argv[]) {
+  yyin = stdin;
+  if (argc == 2 && !(yyin = fopen (argv[1], "r"))) return 1;
+  return yyparse ();
+}
+]])
+
+AT_CHECK([[bison -o glr-regr3.c glr-regr3.y]], 0, [],
+[glr-regr3.y: conflicts: 1 shift/reduce, 1 reduce/reduce
+])
+AT_COMPILE([glr-regr3])
+
+AT_CHECK([[echo p1 t4 o2 p1 p1 t1 o1 t2 p2 o1 t3 p2 p2 | ./glr-regr3]], 0,
+[[Result: 1c04
+]], [])
+
+AT_CLEANUP