Re: too many gotos

[Paul Eggert]

Akim Demaille <address@hidden> writes:

> Unless someone knows a means to generate a grammar with arbitrarily
> many gotos.  That would allow us to test the output.

Don't know offhand, but that patch seems quite reasonable as far as it
goes.  A couple of things, though.  It should use size_t rather than
unsigned int (since the quantities in question in general might
overrun 32-bit counters on a 64-bit host).  Also, GOTO_NUMBER_MAXIMUM
should be revamped and/or removed accordingly.

I installed the following.  Of course this is not at all a complete
fix for the "grammar is too large for 16 (or 32) bits" problem, but at
least it's a step in the right direction.

2004-10-22  Akim Demaille  <address@hidden>
       and  Paul Eggert  <address@hidden>

        Remove some arbitrary limits on goto numbers and relations.
        * src/lalr.c (goto_map, ngotos, from_state, to_state): Omit
        initial values, since they're never used.
        (set_goto_map): ngotos is now unsigned, so test for overflow
        by seeing whether it wraps around to zero.
        * src/lalr.h (goto_number): Now size_t, not short int.
        (GOTO_NUMBER_MAXIMUM): Remove.
        * src/relation.c (relation_print, traverse, relation_transpose):
        Check for END_NODE rather than looking at sign.
        * src/relation.h (END_NODE): New macro.
        (relation_node): Now size_t, not short int.

Index: src/lalr.h
===================================================================
RCS file: /cvsroot/bison/bison/src/lalr.h,v
retrieving revision 1.28
diff -p -u -r1.28 lalr.h
--- src/lalr.h  21 Jun 2004 20:20:31 -0000      1.28
+++ src/lalr.h  22 Oct 2004 23:12:32 -0000
@@ -56,8 +56,7 @@ void lalr_free (void);
    together and GOTO_MAP[I - NTOKENS] is the index in FROM_STATE and
    TO_STATE of the first of them.  */
 
-typedef short int goto_number;
-# define GOTO_NUMBER_MAXIMUM SHRT_MAX
+typedef size_t goto_number;
 
 extern goto_number *goto_map;
 extern state_number *from_state;
Index: src/lalr.c
===================================================================
RCS file: /cvsroot/bison/bison/src/lalr.c,v
retrieving revision 1.98
retrieving revision 1.99
diff -p -u -r1.98 -r1.99
--- src/lalr.c  21 Jun 2004 20:20:30 -0000      1.98
+++ src/lalr.c  22 Oct 2004 23:08:33 -0000      1.99
@@ -42,10 +42,10 @@
 #include "relation.h"
 #include "symtab.h"
 
-goto_number *goto_map = NULL;
-static goto_number ngotos = 0;
-state_number *from_state = NULL;
-state_number *to_state = NULL;
+goto_number *goto_map;
+static goto_number ngotos;
+state_number *from_state;
+state_number *to_state;
 
 /* Linked list of goto numbers.  */
 typedef struct goto_list
@@ -90,9 +90,9 @@ set_goto_map (void)
       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
        {
-         if (ngotos >= GOTO_NUMBER_MAXIMUM)
-           abort ();
          ngotos++;
+         if (! ngotos)
+           abort ();
          goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
        }
     }
Index: src/relation.h
===================================================================
RCS file: /cvsroot/bison/bison/src/relation.h,v
retrieving revision 1.4
diff -p -u -r1.4 relation.h
--- src/relation.h      31 Mar 2004 00:37:21 -0000      1.4
+++ src/relation.h      22 Oct 2004 23:12:32 -0000
@@ -25,9 +25,11 @@
 /* Performing operations on graphs coded as list of adjacency.
 
    If GRAPH is a relation, then GRAPH[Node] is a list of adjacent
-   nodes, ended with -1.  */
+   nodes, ended with END_NODE.  */
 
-typedef short int relation_node;
+#define END_NODE ((relation_node) -1)
+
+typedef size_t relation_node;
 typedef relation_node *relation_nodes;
 typedef relation_nodes *relation;
 
Index: src/relation.c
===================================================================
RCS file: /cvsroot/bison/bison/src/relation.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -p -u -r1.7 -r1.8
--- src/relation.c      31 Mar 2004 00:37:21 -0000      1.7
+++ src/relation.c      22 Oct 2004 23:10:07 -0000      1.8
@@ -35,7 +35,7 @@ relation_print (relation r, size_t size,
     {
       fprintf (out, "%3d: ", i);
       if (r[i])
-       for (j = 0; r[i][j] != -1; ++j)
+       for (j = 0; r[i][j] != END_NODE; ++j)
          fprintf (out, "%3d ", r[i][j]);
       fputc ('\n', out);
     }
@@ -67,7 +67,7 @@ traverse (int i)
   INDEX[i] = height = top;
 
   if (R[i])
-    for (j = 0; R[i][j] >= 0; ++j)
+    for (j = 0; R[i][j] != END_NODE; ++j)
       {
        if (INDEX[R[i][j]] == 0)
          traverse (R[i][j]);
@@ -143,7 +143,7 @@ relation_transpose (relation *R_arg, int
   /* Count. */
   for (i = 0; i < n; i++)
     if ((*R_arg)[i])
-      for (j = 0; (*R_arg)[i][j] >= 0; ++j)
+      for (j = 0; (*R_arg)[i][j] != END_NODE; ++j)
        ++nedges[(*R_arg)[i][j]];
 
   /* Allocate. */
@@ -151,7 +151,7 @@ relation_transpose (relation *R_arg, int
     if (nedges[i] > 0)
       {
        relation_node *sp = CALLOC (sp, nedges[i] + 1);
-       sp[nedges[i]] = -1;
+       sp[nedges[i]] = END_NODE;
        new_R[i] = sp;
        end_R[i] = sp;
       }
@@ -159,7 +159,7 @@ relation_transpose (relation *R_arg, int
   /* Store. */
   for (i = 0; i < n; i++)
     if ((*R_arg)[i])
-      for (j = 0; (*R_arg)[i][j] >= 0; ++j)
+      for (j = 0; (*R_arg)[i][j] != END_NODE; ++j)
        {
          *end_R[(*R_arg)[i][j]] = i;
          ++end_R[(*R_arg)[i][j]];