Re: Bison bugs (memory leaks) found by valgrind in GLR-related tests

[Joel E. Denny]

On Sat, 10 Dec 2005, Joel E. Denny wrote:

> It's a bug in the test case.  Some token semantic values are shared 
> between the merged parse trees.  Each such value is freed by semantic 
> actions for both trees.
> 
> I suspect the original memory leak was intentional because this isn't 
> quick to resolve.  Normally I use GLR to construct packed shared parse 
> forests, and I maintain a reference count for shared nodes.  Thus, all 
> semantic values are freed at the end rather than at each reduction.

Here's an attempt to fix these test cases. Someone should run valgrind to 
be sure the problem is completely solved. (I still need to set up a linux 
box.)

Joel

2005-12-16  Joel E. Denny  <address@hidden>

        * tests/cxx-type.at: Construct a tree, count the parents of shared
        nodes, and free each node once and only once.  Previously, the memory
        for semantic values was leaked instead.

--- tests/cxx-type.at   24 Jul 2005 07:24:22 -0000      1.27
+++ tests/cxx-type.at   16 Dec 2005 07:45:40 -0000
@@ -34,12 +34,33 @@ $1
 
 %{
   #include <stdio.h>
-  #define YYSTYPE char *
+  union Node {
+    struct {
+      int type;
+      int parents;
+    } node_info;
+    struct {
+      int type; /* 1 */
+      int parents;
+      char const *form;
+      union Node *children[3];
+    } nterm;
+    struct {
+      int type; /* 0 */
+      int parents;
+      char *text;
+    } term;
+  };
+  typedef union Node Node;
+  static Node *new_nterm (char const *, Node *, Node *, Node *);
+  static Node *new_term (char *);
+  static void free_node (Node *);
+  static char *node_to_string (Node *);
+  #define YYSTYPE Node *
 ]m4_bmatch([$2], [stmtMerge],
 [ static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);])[
   #define YYINITDEPTH 10
   #define YYSTACKEXPANDABLE 1
-  static char *format (char const *, ...);
   struct YYLTYPE;
 #if YYPURE
 # if YYLSP_NEEDED
@@ -66,36 +87,41 @@ $1
 
 %glr-parser
 
-%destructor { free ($$); } TYPENAME ID
+%destructor { free_node ($$); } stmt expr decl declarator TYPENAME ID
 
 %%
 
 prog :
      | prog stmt   {
-]AT_LOCATION_IF([
+                       char *output;]AT_LOCATION_IF([
                        printf ("%d.%d-%d.%d: ",
                             @2.first_line, @2.first_column,
                             @2.last_line, @2.last_column);])[
-                       printf ("%s\n", ]$[2);
+                       output = node_to_string (]$[2);
+                       printf ("%s\n", output);
+                       free (output);
+                       free_node (]$[2);
                   }
      ;
 
 stmt : expr ';'  $2    { $$ = ]$[1; }
      | decl      $3
-     | error ';'       { static char error_msg[] = "<error>"; $$ = error_msg; }
+     | error ';'       { $$ = new_nterm ("<error>", 0, 0, 0); }
      | '@'             { YYACCEPT; }
      ;
 
 expr : ID
-     | TYPENAME '(' expr ')'  { $$ = format ("<cast>(%s,%s)", ]$[3, ]$[1); }
-     | expr '+' expr         { $$ = format ("+(%s,%s)", ]$[1, ]$[3); }
-     | expr '=' expr          { $$ = format ("=(%s,%s)", ]$[1, ]$[3); }
+     | TYPENAME '(' expr ')'
+                       { $$ = new_nterm ("<cast>(%s,%s)", ]$[3, ]$[1, 0); }
+     | expr '+' expr   { $$ = new_nterm ("+(%s,%s)", ]$[1, ]$[3, 0); }
+     | expr '=' expr    { $$ = new_nterm ("=(%s,%s)", ]$[1, ]$[3, 0); }
      ;
 
 decl : TYPENAME declarator ';'
-                       { $$ = format ("<declare>(%s,%s)", ]$[1, ]$[2); }
+                       { $$ = new_nterm ("<declare>(%s,%s)", ]$[1, ]$[2, 0); }
      | TYPENAME declarator '=' expr ';'
-                       { $$ = format ("<init-declare>(%s,%s,%s)", ]$[1, ]$[2, 
]$[4); }
+                       { $$ = new_nterm ("<init-declare>(%s,%s,%s)", ]$[1,
+                                         ]$[2, ]$[4); }
      ;
 
 declarator : ID
@@ -174,14 +200,13 @@ yylex (LEX_PARAMETERS)
                ungetc (c, stdin);
                buffer[i++] = 0;
                tok = isupper ((unsigned char) buffer[0]) ? TYPENAME : ID;
-               yylval = strcpy ((char *) malloc (i), buffer);
+               yylval = new_term (strcpy ((char *) malloc (i), buffer));
              }
            else
              {
-               static char empty_string[] = "";
                colNum += 1;
                tok = c;
-               yylval = empty_string;
+               yylval = 0;
              }
 #if YYLSP_NEEDED
            yylloc.last_column = colNum-1;
@@ -203,16 +228,82 @@ yyerror (ERROR_PARAMETERS)
   fprintf (stderr, "%s\n", s);
 }
 
+static Node *
+new_nterm (char const *form, Node *child0, Node *child1, Node *child2)
+{
+  Node *node = malloc (sizeof (Node));
+  node->nterm.type = 1;
+  node->nterm.parents = 0;
+  node->nterm.form = form;
+  node->nterm.children[0] = child0;
+  if (child0)
+    child0->node_info.parents += 1;
+  node->nterm.children[1] = child1;
+  if (child1)
+    child1->node_info.parents += 1;
+  node->nterm.children[2] = child2;
+  if (child2)
+    child2->node_info.parents += 1;
+  return node;
+}
+
+static Node *
+new_term (char *text)
+{
+  Node *node = malloc (sizeof (Node));
+  node->term.type = 0;
+  node->term.parents = 0;
+  node->term.text = text;
+  return node;
+}
+
+static void
+free_node (Node *node)
+{
+  if (!node)
+    return;
+  node->node_info.parents -= 1;
+  /* Free only if 0 (last parent) or -1 (no parents).  */
+  if (node->node_info.parents > 0)
+    return;
+  if (node->node_info.type == 1)
+    {
+      free_node (node->nterm.children[0]);
+      free_node (node->nterm.children[1]);
+      free_node (node->nterm.children[2]);
+    }
+  else
+    free (node->term.text);
+  free (node);
+}
 
 static char *
-format (char const *form, ...)
+node_to_string (Node *node)
 {
-   char buffer[1024];
-   va_list args;
-   va_start (args, form);
-   vsprintf (buffer, form, args);
-   va_end (args);
-   return strcpy ((char *) malloc (strlen (buffer) + 1), buffer);
+  char *child0;
+  char *child1;
+  char *child2;
+  char *buffer;
+  if (!node)
+    {
+      buffer = malloc (1);
+      buffer[0] = 0;
+    }
+  else if (node->node_info.type == 1)
+    {
+      child0 = node_to_string (node->nterm.children[0]);
+      child1 = node_to_string (node->nterm.children[1]);
+      child2 = node_to_string (node->nterm.children[2]);
+      buffer = malloc (strlen (node->nterm.form) + strlen (child0)
+                      + strlen (child1) + strlen (child2) + 1);
+      sprintf (buffer, node->nterm.form, child0, child1, child2);
+      free (child0);
+      free (child1);
+      free (child2);
+    }
+  else
+    buffer = strdup (node->term.text);
+  return buffer;
 }
 
 ]]
@@ -220,7 +311,7 @@ m4_bmatch([$2], [stmtMerge],
 [[static YYSTYPE
 stmtMerge (YYSTYPE x0, YYSTYPE x1)
 {
-  return format ("<OR>(%s,%s)", x0, x1);
+  return new_nterm ("<OR>(%s,%s)", x0, x1, 0);
 }
 ]])
 )