Patch to fix problem with embedded rules in GLR parsers.

[Paul Hilfinger]

In response to the report by S. Eken, I have made the following
changes to GLR-related files.  The symptom was that embedded rules,
such as

     X: A { f ($1); } B

would get incorrect values for $n in GLR mode (that is, when
%glr-parser is specified AND the rules are reduced in a section of the 
derivation where the parser has split its stack).  The same problem
also causes non-positive indices (as in $-2) to fail.  The reason, to
be frank, was simply that I had overlooked these cases, and has not
provided enough of the semantic stack to the semantic actions.  The
patch below fixes that, and also supplies a new regression, based on
Eken's submission.  There is also a small correction to an existing
GLR test that I happened to discover while working on this.

2003-01-29  Paul Hilfinger  <address@hidden>

        * tests/cxx-type.at: Correct apparent typo in Bison input: $$ instead
        of $1.
        
        Changes in response to error report by S. Eken: GLR mode does not 
        handle negative $ indices or $ indices in embedded rules correctly.
        See <http://mail.gnu.org/archive/html/bug-bison/2003-01/msg00076.html>.
        
        * data/glr.c (b4_rhs_value): Change to use YYFILL macro.
        (b4_rhs_location): Ditto.
        (yyfill): New function to copy from stack tree into array 
        incrementally.
        (yyuserAction): Modify to allow incremental move of semantic values 
        to rhs array when in GLR mode.  
        Define YYFILL to use in user-defined actions to fill semantic array 
        as needed.
        Remove dummy use of yystack, as there is now a guaranteed use.
        (yydoAction): Modify to allow incremental move of semantic values
        to rhs array when in GLR mode.
        (yyresolveAction): Ditto.
        (yyglrShiftDefer): Update comment.
        (yyresolveStates): Use X == NULL for pointers, not !X. 
        (yyglrReduce): Ditto.
        (yydoAction): Ditto
        
        * tests/glr-regr1.at: Rename to ...
        * tests/glr-regression.at: Add new regression test for the problems
        described above (adapted from S. Eken).
        Update copyright notice.
        * tests/testsuite.at: Rename glr-regr1.at to glr-regression.at.
        * tests/Makefile.am: Ditto.

Index: bison-1_5.64/tests/testsuite.at
- --- bison-1_5.64/tests/testsuite.at Thu, 14 Nov 2002 11:10:40 -0800 hilfingr 
(g
lrbison/c/41_testsuite. 1.1.1.5 644)
+++ tmp.4(w)/tests/testsuite.at Wed, 29 Jan 2003 14:17:26 -0800 hilfingr (glrbi
son/c/41_testsuite. 1.1.1.7 644)
@@ -108,5 +108,5 @@ m4_include([regression.at])
 # GLR tests:
 # C++ types, simplified
 m4_include([cxx-type.at])
- -# Regression test for state-folding optimization
- -m4_include([glr-regr1.at])
+# Regression tests
+m4_include([glr-regression.at])
Index: bison-1_5.64/tests/Makefile.am
- --- bison-1_5.64/tests/Makefile.am Tue, 29 Oct 2002 17:58:38 -0800 hilfingr 
(gl
rbison/c/45_Makefile.a 1.1.1.4 644)
+++ tmp.4(w)/tests/Makefile.am Wed, 29 Jan 2003 14:16:47 -0800 hilfingr (glrbis
on/c/45_Makefile.a 1.1.1.6 644)
@@ -48,7 +48,7 @@ TESTSUITE_AT = \
        synclines.at headers.at actions.at conflicts.at \
        calc.at \
         torture.at existing.at regression.at \
- -     cxx-type.at glr-regr1.at
+       cxx-type.at glr-regression.at
 
 TESTSUITE = $(srcdir)/testsuite
 
Index: bison-1_5.64/tests/cxx-type.at
- --- bison-1_5.64/tests/cxx-type.at Thu, 19 Dec 2002 19:07:09 -0800 hilfingr 
(gl
rbison/g/23_cxx-type.a 1.9 644)
+++ tmp.4(w)/tests/cxx-type.at Tue, 28 Jan 2003 19:21:53 -0800 hilfingr (glrbis
on/g/23_cxx-type.a 1.10 644)
@@ -72,7 +72,7 @@ stmt : expr ';'  $2
      | '@'  { YYACCEPT; }
      ;
 
- -expr : ID            { printf ("%s ", $$); }
+expr : ID              { printf ("%s ", ]$[1); }
      | TYPENAME '(' expr ')'
                        { printf ("%s <cast> ", ]$[1); }
      | expr '+' expr   { printf ("+ "); }
Index: bison-1_5.64/data/glr.c
- --- bison-1_5.64/data/glr.c Fri, 03 Jan 2003 16:11:20 -0800 hilfingr 
(glrbison/
e/14_glr-parser 1.27.1.28 644)
+++ tmp.4(w)/data/glr.c Wed, 29 Jan 2003 11:56:35 -0800 hilfingr (glrbison/e/14
_glr-parser 1.27.1.30 644)
@@ -111,7 +111,7 @@ m4_define([b4_lhs_value],
 # Expansion of $<TYPE>NUM, where the current rule has RULE-LENGTH
 # symbols on RHS.
 m4_define([b4_rhs_value],
- address@hidden([$2 - $1])@}.yystate.yysemantics.yysval[]m4_ifval([$3], [.$3])
])
address@hidden (m4_eval([$2 - $1]))@}.yystate.yysemantics.yysval[]m4_ifval([$3
], [.$3])])
 
 
 
@@ -131,8 +131,7 @@ m4_define([b4_lhs_location],
 # Expansion of @NUM, where the current rule has RULE-LENGTH symbols
 # on RHS.
 m4_define([b4_rhs_location],
- address@hidden([$2 - $1])@}.yystate.yyloc])
- -
address@hidden (m4_eval([$2 - $1]))@}.yystate.yyloc])
 
 # We do want M4 expansion after # for CPP macros.
 m4_changecom()
@@ -614,6 +613,28 @@ yytokenName (yySymbol yytoken)
 }
 #endif
 
+/** Fill in YYVSP[YYLOW1 .. YYLOW0-1] from the chain of states starting
+ *  at YYVSP[YYLOW0].yystate.yypred.  Leaves YYVSP[YYLOW1].yystate.yypred
+ *  containing the pointer to the next state in the chain. Assumes 
+ *  YYLOW1 < YYLOW0.  For convenience, returns YYLOW1. */
+static int
+yyfill (yyGLRStackItem* yyvsp, int yylow0, int yylow1) 
+{
+  yyGLRState* s;
+  int i;
+  s = yyvsp[yylow0].yystate.yypred; 
+  for (i = yylow0-1; i >= yylow1; i -= 1)
+    {
+      if (! s->yyresolved)
+       abort ();
+      yyvsp[i].yystate.yyresolved = yytrue;
+      yyvsp[i].yystate.yysemantics.yysval = s->yysemantics.yysval;
+      yyvsp[i].yystate.yyloc = s->yyloc;
+      s = yyvsp[i].yystate.yypred = s->yypred;
+    }
+  return yylow1;
+}
+
 /** Perform user action for rule number YYN, with RHS length YYRHSLEN,
  *  and top stack item YYVSP.  YYLVALP points to place to put semantic
  *  value ($$), and yylocp points to place for location information
@@ -624,8 +645,8 @@ yyuserAction (yyRuleNum yyn, int yyrhsle
              YYSTYPE* yyvalp, YYLTYPE* yylocp, yyGLRStack* yystack
               ]b4_user_formals[)
 {
- -  /* Avoid `unused' warnings in there are no $n. */
- -  (void) yystack;
+  int yynormal = (yystack->yysplitPoint == NULL);
+  int yylow;
 
   if (yyrhslen == 0)
     {
@@ -649,6 +670,9 @@ yyuserAction (yyRuleNum yyn, int yyrhsle
 # define YYRECOVERING (yystack->yyerrState != 0)
 # undef yyclearin
 # define yyclearin (yychar = *(yystack->yytokenp) = YYEMPTY)
+# undef YYFILL
+# define YYFILL(N)                                                          \
+  ((yynormal || yylow <= (N)) ? (N) : (yylow = yyfill (yyvsp, yylow, N)))
 # undef YYBACKUP
 # define YYBACKUP(Token, Value)                                        
             \
   do {                                                                      \
@@ -657,6 +681,7 @@ yyuserAction (yyRuleNum yyn, int yyrhsle
   } while (0)
 
 ]
+   yylow = 1;
    switch (yyn)
      {
        b4_actions
@@ -998,9 +1023,9 @@ yyglrShift (yyGLRStack* yystack, int yyk
     yyexpandGLRStack (yystack]b4_pure_args[);
 }
 
- -/** Shift to a new state on stack #K of STACK, to a new state
- - *  corresponding to LR state LRSTATE, at input position POSN, with
- - * the (unresolved) semantic value of RHS under the action for RULE. */
+/** Shift stack #K of YYSTACK, to a new state corresponding to LR
+ *  state YYLRSTATE, at input position YYPOSN, with the (unresolved) 
+ *  semantic value of YYRHS under the action for YYRULE. */
 static inline void
 yyglrShiftDefer (yyGLRStack* yystack, int yyk, yyStateNum yylrState,
                 size_t yyposn, yyGLRState* rhs, yyRuleNum yyrule]b4_pure_forma
ls[)
@@ -1058,15 +1083,13 @@ yydoAction (yyGLRStack* yystack, int yyk
     {
       int yyi;
       yyGLRState* yys;
- -      yyGLRStackItem yyrhsVals[YYMAXRHS];
- -      for (yyi = yynrhs-1, yys = yystack->yytops.yystates[yyk]; 0 <= yyi;
- -        yyi -= 1, yys = yys->yypred)
+      yyGLRStackItem yyrhsVals[YYMAXRHS+1];
+      yys = yyrhsVals[YYMAXRHS].yystate.yypred = yystack->yytops.yystates[yyk]
;
+      for (yyi = 0; yyi < yynrhs; yyi += 1)
        {
- -       if (! yys->yypred)
+         yys = yys->yypred;
+         if (yys == NULL)
            abort ();
- -       yyrhsVals[yyi].yystate.yyresolved = yytrue;
- -       yyrhsVals[yyi].yystate.yysemantics.yysval = yys->yysemantics.yysval;
- -       yyrhsVals[yyi].yystate.yyloc = yys->yyloc;
        }
       yyupdateSplit (yystack, yys);
       yystack->yytops.yystates[yyk] = yys;
@@ -1077,10 +1100,10 @@ yydoAction (yyGLRStack* yystack, int yyk
        }
       else
        {
- -       *yyvalp = yyrhsVals[0].yystate.yysemantics.yysval;
- -       *yylocp = yyrhsVals[0].yystate.yyloc;
+         *yyvalp = yyrhsVals[1].yystate.yysemantics.yysval;
+         *yylocp = yyrhsVals[1].yystate.yyloc;
        }
- -      return yyuserAction (yyrule, yynrhs, yyrhsVals + (yynrhs-1),
+      return yyuserAction (yyrule, yynrhs, yyrhsVals + YYMAXRHS - 1,
                           yyvalp, yylocp, yystack]b4_user_args[);
     }
 }
@@ -1152,7 +1175,7 @@ yyglrReduce (yyGLRStack* yystack, size_t
           0 < yyn; yyn -= 1)
        {
          yys = yys->yypred;
- -       if (! yys)
+         if (yys == NULL)
            abort ();
        }
       yyupdateSplit (yystack, yys);
@@ -1289,7 +1312,7 @@ yyresolveStates (yyGLRState* yys, int yy
   YYRESULTTAG yyflag;
   if (0 < yyn)
     {
- -      if (! yys->yypred)
+      if (yys->yypred == NULL)
        abort ();
       yyflag = yyresolveStates (yys->yypred, yyn-1, yystack]b4_user_args[);
       if (yyflag != yyok)
@@ -1311,22 +1334,13 @@ static YYRESULTTAG
 yyresolveAction (yySemanticOption* yyopt, yyGLRStack* yystack,
                 YYSTYPE* yyvalp, YYLTYPE* yylocp]b4_user_formals[)
 {
- -  yyGLRStackItem yyrhsVals[YYMAXRHS];
- -  int yynrhs, yyi;
- -  yyGLRState* yys;
+  yyGLRStackItem yyrhsVals[YYMAXRHS+1];
+  int yynrhs;
 
   yynrhs = yyrhsLength (yyopt->yyrule);
   YYCHK (yyresolveStates (yyopt->yystate, yynrhs, yystack]b4_user_args[));
- -  for (yyi = yynrhs-1, yys = yyopt->yystate; 0 <= yyi;
- -       yyi -= 1, yys = yys->yypred)
- -    {
- -      if (! yys->yypred)
- -     abort ();
- -      yyrhsVals[yyi].yystate.yyresolved = yytrue;
- -      yyrhsVals[yyi].yystate.yysemantics.yysval = yys->yysemantics.yysval;
- -      yyrhsVals[yyi].yystate.yyloc = yys->yyloc;
- -    }
- -  return yyuserAction (yyopt->yyrule, yynrhs, yyrhsVals + (yynrhs-1),
+  yyrhsVals[YYMAXRHS].yystate.yypred = yyopt->yystate;
+  return yyuserAction (yyopt->yyrule, yynrhs, yyrhsVals + YYMAXRHS - 1,
                       yyvalp, yylocp, yystack]b4_user_args[);
 }
 
Index: bison-1_5.64/tests/glr-regression.at
- --- bison-1_5.64/tests/glr-regr1.at Fri, 03 Jan 2003 16:11:20 -0800 hilfingr 
(g
lrbison/h/9_glr-regr1. 1.6 644)
+++ tmp.4(w)/tests/glr-regression.at Wed, 29 Jan 2003 14:20:37 -0800 hilfingr (
glrbison/h/9_glr-regr1. 1.7 644)
@@ -1,5 +1,5 @@
- -# Checking GLR Parsing: Regression Test           -*- Autotest -*-
- -# Copyright (C) 2002 Free Software Foundation, Inc.
+# Checking GLR Parsing: Regression Tests           -*- Autotest -*-
+# Copyright (C) 2002, 2003 Free Software Foundation, Inc.
 
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -16,7 +16,11 @@
 # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 # 02111-1307, USA.
 
- -AT_BANNER([[GLR Regression Test #1.]])
+AT_BANNER([[GLR Regression Tests]])
+
+## --------------------------- ##
+## Badly Collapsed GLR States. ##
+## --------------------------- ##
 
 AT_SETUP([Badly Collapsed GLR States])
 
@@ -103,5 +107,115 @@ E -> E 'P' E
 E -> E 'P' E
 <OR>
 ]], [])
+
+AT_CLEANUP
+
+## ------------------------------------------------------------ ##
+## Improper handling of embedded actions and $-N in GLR parsers ##
+## ------------------------------------------------------------ ##
+
+AT_SETUP([Improper handling of embedded actions and $-N in GLR parsers])
+
+AT_DATA_GRAMMAR([glr-regr2a.y],
+[[/* Regression Test: Improper handling of embedded actions and $-N  */
+/* Reported by S. Eken */
+
+%{
+  #define YYSTYPE char const *
+  #define yyfalse 0
+  #define yytrue 1
+
+  #include <ctype.h>
+  #include <stdio.h>
+  #include <string.h>
+  int yylex (void);
+  void yyerror (char const *);
+%}
+
+%glr-parser
+
+%%
+
+command:
+    's' var 't'
+       { printf ("Variable: '%s'\n", $2); } 
+    'v' 'x' 'q'
+  | 's' var_list 't' 'e'
+       { printf ("Varlist: '%s'\n", $2); }
+  | 's' var 't' var_printer 'x'
+  ;
+
+var:
+  'V'
+     { $$ = $1; }
+  ;
+
+var_list:
+  var
+    { $$ = $1; }
+  | var ',' var_list
+    {
+      char buffer[50];
+      strcpy (buffer, $1); 
+      strcat (buffer, ",");
+      strcat (buffer, $3);
+      $$ = strdup (buffer);
+    }  
+  ;
+
+var_printer: 'v'
+   { printf ("Variable: '%s'\n", $-1); }
+
+%%
+
+FILE *yyin = NULL;
+
+int
+yylex (void)
+{ 
+  int c;
+  char buf[50];
+  switch (fscanf (yyin, " %1[a-z,]", buf)) {
+  case 1:
+    return buf[0];
+  case EOF:
+    return 0;
+  default:
+    break;
+  }
+  fscanf (yyin, "%s", buf);
+  yylval = strdup (buf);
+  return 'V';
+}
+
+void
+yyerror (char const *s)
+{ printf ("%s\n", s);
+}
+
+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-regr2a.c glr-regr2a.y]], 0, [],
+[glr-regr2a.y: conflicts: 2 shift/reduce
+])
+AT_COMPILE([glr-regr2a])
+
+AT_CHECK([[echo s VARIABLE_1 t v x q | ./glr-regr2a]], 0,
+[[Variable: 'VARIABLE_1'
+]], [])
+AT_CHECK([[echo s VARIABLE_1 , ANOTHER_VARIABLE_2 t e | ./glr-regr2a]], 0,
+[[Varlist: 'VARIABLE_1,ANOTHER_VARIABLE_2'
+]])
+AT_CHECK([[echo s VARIABLE_3 t v x | ./glr-regr2a]], 0,
+[[Variable: 'VARIABLE_3'
+]], [])
+
 
 AT_CLEANUP