Re: redundant merges for GLR

[Paul Eggert]

"Joel E. Denny" <address@hidden> writes:

>> I haven't seen any response to my posts last month on problems I'm having
>> with bison GLR:
>>
>>   http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html
>>   http://lists.gnu.org/archive/html/help-bison/2005-07/msg00040.html
>>   http://lists.gnu.org/archive/html/help-bison/2005-07/msg00017.html
>>
>> Were my explanations unclear?  Am I correct that this is unintended
>> behavior?  Should I post these to bug-bison instead?

bug-bison would have been better, but I think the main problem is that
Paul Hilfinger (the GLR go-to guy) is probably on vacation.

> resolveValue() invokes mergeOptionSets() but doesn't remove the merged
> SemanticOption's.  Thus, within `if (yymerge)', resolveAction() and
> userMerge() are invoked for each of several identical SemanticOption's.
> This produces the redundant trees.

I'm a bit worried about the storage management for the deleted nodes
(did you look into that?) but the basic idea seems sound, and we can
worry about any memory leaks later.

I installed this patch, which doesn't quite match yours exactly but
which uses the same idea.  I also added the test case as you suggested.

Thanks.

2005-08-21  Paul Eggert  <address@hidden>

        * data/glr.c (yyresolveValue): Fix redundant parse tree problem
        reported by Joel E. Denny in
        <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00004.html>
        (trivial change).
        * tests/glr-regression.at (Duplicate representation of merged trees):
        New test, from Joel E. Denny in:
        <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html>.
        * THANKS: Add Joel E. Denny.

Index: THANKS
===================================================================
RCS file: /cvsroot/bison/bison/THANKS,v
retrieving revision 1.60
diff -p -u -r1.60 THANKS
--- THANKS      22 Jul 2005 21:20:58 -0000      1.60
+++ THANKS      21 Aug 2005 23:42:26 -0000
@@ -34,6 +34,7 @@ Jan Nieuwenhuizen         address@hidden
 Jesse Thilo               address@hidden
 Jim Kent                  address@hidden
 Jim Meyering              address@hidden
+Joel E. Denny             address@hidden
 Juan Manuel Guerrero      address@hidden
 Kees Zeelenberg           address@hidden
 Keith Browne              address@hidden
Index: data/glr.c
===================================================================
RCS file: /cvsroot/bison/bison/data/glr.c,v
retrieving revision 1.111
diff -p -u -r1.111 glr.c
--- data/glr.c  25 Jul 2005 04:20:39 -0000      1.111
+++ data/glr.c  21 Aug 2005 23:42:26 -0000
@@ -1606,35 +1606,44 @@ yyresolveValue (yySemanticOption* yyopti
                YYSTYPE* yyvalp, YYLTYPE* yylocp]b4_user_formals[)
 {
   yySemanticOption* yybest;
-  yySemanticOption* yyp;
+  yySemanticOption** yypp;
   yybool yymerge;
 
   yybest = yyoptionList;
   yymerge = yyfalse;
-  for (yyp = yyoptionList->yynext; yyp != NULL; yyp = yyp->yynext)
+  for (yypp = &yyoptionList->yynext; *yypp != NULL; )
     {
+      yySemanticOption* yyp = *yypp;
+
       if (yyidenticalOptions (yybest, yyp))
-       yymergeOptionSets (yybest, yyp);
+       {
+         yymergeOptionSets (yybest, yyp);
+         *yypp = yyp->yynext;
+       }
       else
-       switch (yypreference (yybest, yyp))
-         {
-         case 0:
-           yyreportAmbiguity (yybest, yyp, yystack]b4_pure_args[);
-           break;
-         case 1:
-           yymerge = yytrue;
-           break;
-         case 2:
-           break;
-         case 3:
-           yybest = yyp;
-           yymerge = yyfalse;
-           break;
-         }
+       {
+         switch (yypreference (yybest, yyp))
+           {
+           case 0:
+             yyreportAmbiguity (yybest, yyp, yystack]b4_pure_args[);
+             break;
+           case 1:
+             yymerge = yytrue;
+             break;
+           case 2:
+             break;
+           case 3:
+             yybest = yyp;
+             yymerge = yyfalse;
+             break;
+           }
+         yypp = &yyp->yynext;
+       }
     }
 
   if (yymerge)
     {
+      yySemanticOption* yyp;
       int yyprec = yydprec[yybest->yyrule];
       YYCHK (yyresolveAction (yybest, yystack, yyvalp, yylocp]b4_user_args[));
       for (yyp = yybest->yynext; yyp != NULL; yyp = yyp->yynext)
Index: tests/glr-regression.at
===================================================================
RCS file: /cvsroot/bison/bison/tests/glr-regression.at,v
retrieving revision 1.12
diff -p -u -r1.12 glr-regression.at
--- tests/glr-regression.at     18 Jul 2005 18:39:01 -0000      1.12
+++ tests/glr-regression.at     21 Aug 2005 23:42:26 -0000
@@ -327,3 +327,96 @@ AT_CHECK([[echo p1 t4 o2 p1 p1 t1 o1 t2 
 ]], [])
 
 AT_CLEANUP
+
+
+## ---------------------------------------------------------------------- ##
+## Duplicate representation of merged trees                               ##
+## Thanks to Joel E. Denny for this test; see                             ##
+## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html>.  ##
+## ---------------------------------------------------------------------- ##
+
+AT_SETUP([Duplicate representation of merged trees])
+
+AT_DATA_GRAMMAR([glr-regr4.y],
+[[%union { char *ptr; }
+%type <ptr> S A A1 A2 B
+%glr-parser
+
+%{
+  #include <stdio.h>
+  #include <stdlib.h>
+  #include <string.h>
+  static char *merge (YYSTYPE, YYSTYPE);
+  static char *make_value (char *, char *);
+  static void yyerror (char const *);
+  static int yylex (void);
+%}
+
+%%
+
+tree: S { printf ("%s\n", $1); } ;
+
+S:
+  A   %merge<merge> { $$ = make_value ("S", $1); }
+  | B %merge<merge> { $$ = make_value ("S", $1); }
+  ;
+
+A:
+  A1   %merge<merge> { $$ = make_value ("A", $1); }
+  | A2 %merge<merge> { $$ = make_value ("A", $1); }
+  ;
+
+A1: 'a' { $$ = make_value ("A1", "'a'"); } ;
+A2: 'a' { $$ = make_value ("A2", "'a'"); } ;
+B:  'a' { $$ = make_value ("B", "'a'");  } ;
+
+%%
+
+static int
+yylex (void)
+{
+  static char const *input = "a";
+  return *input++;
+}
+
+int
+main (void)
+{
+  return yyparse ();
+}
+
+static char *
+make_value (char *parent, char *child)
+{
+  char const format[] = "%s <- %s";
+  char *value = malloc (strlen (parent) + strlen (child) + sizeof format);
+  sprintf (value, format, parent, child);
+  return value;
+}
+
+static char *
+merge (YYSTYPE s1, YYSTYPE s2)
+{
+  char const format[] = "merge{ %s and %s }";
+  char *value = malloc (strlen (s1.ptr) + strlen (s2.ptr) + sizeof format);
+  sprintf (value, format, s1.ptr, s2.ptr);
+  return value;
+}
+
+static void
+yyerror (char const *msg)
+{
+  printf ("%s\n", msg);
+}
+]])
+
+AT_CHECK([[bison -o glr-regr4.c glr-regr4.y]], 0, [],
+[glr-regr4.y: conflicts: 1 reduce/reduce
+])
+AT_COMPILE([glr-regr4])
+
+AT_CHECK([[./glr-regr4]], 0,
+[[merge{ S <- merge{ A <- A1 <- 'a' and A <- A2 <- 'a' } and S <- B <- 'a' }
+]], [])
+
+AT_CLEANUP