22-fyi-state-c.patch

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>
        Pessimize the code to simplify it: from now on, all the states
        have a valid SHIFTS, which NSHIFTS is possibly 0.
        
        * src/LR0.c (shifts_new): Be global and move to..
        * src/state.c, src/state.h: here.
        * src/conflicts, src/lalr.c, src/output.c, src/print.c,
        * src/print_graph: Adjust.
        
        
Index: src/print_graph.c
--- src/print_graph.c Thu, 22 Nov 2001 21:48:44 +0100 akim
+++ src/print_graph.c Sat, 01 Dec 2001 19:48:49 +0100 akim
@@ -84,20 +84,17 @@
 print_actions (int state, const char *node_name)
 {
   int i;
-  int k;
-  int state1;
-  int symbol;
-  shifts *shiftp;
-  errs *errp;
-  reductions *redp;
+
+  shifts   *shiftp = state_table[state].shift_table;
+  reductions *redp = state_table[state].reduction_table;
+#if 0
+  errs       *errp = err_table[state];
+#endif
+
   static char buff[10];
   edge_t edge;
 
-  shiftp = state_table[state].shift_table;
-  redp = state_table[state].reduction_table;
-  errp = err_table[state];
-
-  if (!shiftp && !redp)
+  if (!shiftp->nshifts && !redp)
     {
 #if 0
       if (final_state == state)
@@ -108,42 +105,26 @@
       return;
     }
 
-  if (shiftp)
-    {
-      k = shiftp->nshifts;
-
-      for (i = 0; i < k; i++)
-       {
-         if (!shiftp->shifts[i])
-           continue;
-         state1 = shiftp->shifts[i];
-         symbol = state_table[state1].accessing_symbol;
-
-         if (ISVAR (symbol))
-           break;
-
-         {
-           new_edge (&edge);
-
-           if (state > state1)
-             edge.type = back_edge;
-           open_edge (&edge, fgraph);
-           /* The edge source is the current node.  */
-           edge.sourcename = node_name;
-           sprintf (buff, "%d", state1);
-           edge.targetname = buff;
-           edge.color = (symbol == 0) ? red : blue;
-           edge.label = tags[symbol];
-           output_edge (&edge, fgraph);
-           close_edge (fgraph);
-         }
-       }
-    }
-  else
-    {
-      i = 0;
-      k = 0;
-    }
+  for (i = 0; i < shiftp->nshifts; i++)
+    if (!SHIFT_IS_DISABLED (shiftp, i))
+      {
+       int state1 = shiftp->shifts[i];
+       int symbol = state_table[state1].accessing_symbol;
+
+       new_edge (&edge);
+
+       if (state > state1)
+         edge.type = back_edge;
+       open_edge (&edge, fgraph);
+       /* The edge source is the current node.  */
+       edge.sourcename = node_name;
+       sprintf (buff, "%d", state1);
+       edge.targetname = buff;
+       edge.color = (symbol == 0) ? red : blue;
+       edge.label = tags[symbol];
+       output_edge (&edge, fgraph);
+       close_edge (fgraph);
+      }
 
 #if 0
   if (errp)
@@ -182,14 +163,12 @@
     }
 #endif
 
-  if (i < k)
-    {
-      for (; i < k; i++)
+  if (i < shiftp->nshifts)
+    for (; i < shiftp->nshifts; i++)
+      if (!SHIFT_IS_DISABLED (shiftp, i))
        {
-         if (!shiftp->shifts[i])
-           continue;
-         state1 = shiftp->shifts[i];
-         symbol = state_table[state1].accessing_symbol;
+         int state1 = shiftp->shifts[i];
+         int symbol = state_table[state1].accessing_symbol;
 
          new_edge (&edge);
          open_edge (&edge, fgraph);
@@ -201,7 +180,6 @@
          output_edge (&edge, fgraph);
          close_edge (fgraph);
        }
-    }
 }
 
 
Index: src/LR0.c
--- src/LR0.c Sat, 01 Dec 2001 16:53:15 +0100 akim
+++ src/LR0.c Sat, 01 Dec 2001 20:12:18 +0100 akim
@@ -314,19 +314,6 @@
 }
 
 
-/*---------------------------------.
-| Create a new array of N shitfs.  |
-`---------------------------------*/
-
-static shifts *
-shifts_new (int n)
-{
-  shifts *res = SHIFTS_ALLOC (n);
-  res->nshifts = n;
-  return res;
-}
-
-
 /*------------------------------------------------------------.
 | Save the NSHIFTS of SHIFTSET into the current linked list.  |
 `------------------------------------------------------------*/
@@ -393,7 +380,7 @@
 
   sp = first_shift;
 
-  if (!sp)
+  if (!sp->nshifts)
     {
       /* There are no shifts for any state.  Make one shift, from the
         initial state to the next-to-final state.  */
@@ -610,8 +597,7 @@
 
       /* create the shifts structures for the shifts to those states,
          now that the state numbers transitioning to are known */
-      if (nshifts > 0)
-       save_shifts ();
+      save_shifts ();
 
       /* states are queued when they are created; process them all */
       this_state = this_state->next;
Index: src/Makefile.am
--- src/Makefile.am Sat, 01 Dec 2001 01:14:25 +0100 akim
+++ src/Makefile.am Sat, 01 Dec 2001 20:04:49 +0100 akim
@@ -38,7 +38,8 @@
 bison_SOURCES = LR0.c closure.c complain.c conflicts.c \
     derives.c  \
     files.c getargs.c gram.c lalr.c lex.c main.c nullable.c \
-    output.c   \
+    output.h output.c \
+    state.h state.c \
     print.c reader.c reduce.c symtab.c warshall.c vcg.c print_graph.c
 
 EXTRA_bison_SOURCES = vmsgetargs.c
@@ -46,7 +47,6 @@
 noinst_HEADERS = LR0.h closure.h complain.h conflicts.h \
  derives.h \
  files.h getargs.h gram.h lalr.h lex.h nullable.h \
- output.h state.h      \
  print.h reader.h reduce.h symtab.h warshall.h system.h types.h \
  vcg.h vcg_defaults.h print_graph.h
 
Index: src/conflicts.c
--- src/conflicts.c Sat, 01 Dec 2001 19:38:04 +0100 akim
+++ src/conflicts.c Sat, 01 Dec 2001 19:40:02 +0100 akim
@@ -60,10 +60,9 @@
   shifts *shiftp = state_table[state].shift_table;
   int i;
 
-  if (shiftp)
-    for (i = 0; i < shiftp->nshifts; i++)
-      if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token)
-       SHIFT_DISABLE (shiftp, i);
+  for (i = 0; i < shiftp->nshifts; i++)
+    if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token)
+      SHIFT_DISABLE (shiftp, i);
 }
 
 
@@ -174,10 +173,9 @@
     lookaheadset[i] = 0;
 
   shiftp = state_table[state].shift_table;
-  if (shiftp)
-    for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
-      if (!SHIFT_IS_DISABLED (shiftp, i))
-       SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i));
+  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
+    if (!SHIFT_IS_DISABLED (shiftp, i))
+      SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i));
 
   /* Loop over all rules which require lookahead in this state.  First
      check for shift-reduce conflict, and try to resolve using
@@ -436,16 +434,15 @@
     shiftset[i] = 0;
 
   shiftp = state_table[state].shift_table;
-  if (shiftp)
-    for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
-      if (!SHIFT_IS_DISABLED (shiftp, i))
-       {
-         /* if this state has a shift for the error token, don't use a
-            default rule.  */
-         if (SHIFT_IS_ERROR (shiftp, i))
-           nodefault = 1;
-         SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
-       }
+  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
+    if (!SHIFT_IS_DISABLED (shiftp, i))
+      {
+       /* if this state has a shift for the error token, don't use a
+          default rule.  */
+       if (SHIFT_IS_ERROR (shiftp, i))
+         nodefault = 1;
+       SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
+      }
 
   errp = err_table[state];
   if (errp)
@@ -507,10 +504,9 @@
       for (i = 0; i < tokensetsize; i++)
        shiftset[i] = 0;
 
-      if (shiftp)
-       for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
-         if (!SHIFT_IS_DISABLED (shiftp, i))
-           SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
+      for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
+       if (!SHIFT_IS_DISABLED (shiftp, i))
+         SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
 
       for (i = 0; i < ntokens; i++)
        {
Index: src/lalr.c
--- src/lalr.c Sat, 01 Dec 2001 17:50:24 +0100 akim
+++ src/lalr.c Sat, 01 Dec 2001 20:10:53 +0100 akim
@@ -165,6 +165,15 @@
       state_table[rp->number].reduction_table = rp;
   }
 
+  /* Pessimization, but simplification of the code: make sense all the
+     states have a shift_table, even if reduced to 0 shifts.  */
+  {
+    int i;
+    for (i = 0; i < nstates; i++)
+      if (!state_table[i].shift_table)
+       state_table[i].shift_table = shifts_new (0);
+  }
+
   /* Initializing the lookaheads members.  Please note that it must be
      performed after having set some of the other members which are
      used below.  Change with extreme caution.  */
@@ -180,18 +189,17 @@
        state_table[i].lookaheads = count;
 
        if (rp
-           && (rp->nreds > 1 || (sp && SHIFT_IS_SHIFT (sp, 0))))
+           && (rp->nreds > 1 || (sp->nshifts && SHIFT_IS_SHIFT (sp, 0))))
          count += rp->nreds;
        else
          state_table[i].consistent = 1;
 
-       if (sp)
-         for (k = 0; k < sp->nshifts; k++)
-           if (SHIFT_IS_ERROR (sp, k))
-             {
-               state_table[i].consistent = 0;
-               break;
-             }
+       for (k = 0; k < sp->nshifts; k++)
+         if (SHIFT_IS_ERROR (sp, k))
+           {
+             state_table[i].consistent = 0;
+             break;
+           }
       }
      state_table[nstates].lookaheads = count;
   }
@@ -239,18 +247,16 @@
 
   ngotos = 0;
   for (sp = first_shift; sp; sp = sp->next)
-    {
-      for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i)
-       {
-         symbol = state_table[sp->shifts[i]].accessing_symbol;
+    for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i)
+      {
+       symbol = state_table[sp->shifts[i]].accessing_symbol;
 
-         if (ngotos == MAXSHORT)
-           fatal (_("too many gotos (max %d)"), MAXSHORT);
+       if (ngotos == MAXSHORT)
+         fatal (_("too many gotos (max %d)"), MAXSHORT);
 
-         ngotos++;
-         goto_map[symbol]++;
-       }
-    }
+       ngotos++;
+       goto_map[symbol]++;
+      }
 
   k = 0;
   for (i = ntokens; i < nsyms; i++)
@@ -336,29 +342,26 @@
       int stateno = to_state[i];
       shifts *sp = state_table[stateno].shift_table;
 
-      if (sp)
+      int j;
+      for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++)
        {
-         int j;
-         for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++)
-           {
-             int symbol = state_table[sp->shifts[j]].accessing_symbol;
-             SETBIT (F + i * tokensetsize, symbol);
-           }
+         int symbol = state_table[sp->shifts[j]].accessing_symbol;
+         SETBIT (F + i * tokensetsize, symbol);
+       }
 
-         for (; j < sp->nshifts; j++)
-           {
-             int symbol = state_table[sp->shifts[j]].accessing_symbol;
-             if (nullable[symbol])
-               edge[nedges++] = map_goto (stateno, symbol);
-           }
+      for (; j < sp->nshifts; j++)
+       {
+         int symbol = state_table[sp->shifts[j]].accessing_symbol;
+         if (nullable[symbol])
+           edge[nedges++] = map_goto (stateno, symbol);
+       }
 
-         if (nedges)
-           {
-             reads[i] = XCALLOC (short, nedges + 1);
-             shortcpy (reads[i], edge, nedges);
-             reads[i][nedges] = -1;
-             nedges = 0;
-           }
+      if (nedges)
+       {
+         reads[i] = XCALLOC (short, nedges + 1);
+         shortcpy (reads[i], edge, nedges);
+         reads[i][nedges] = -1;
+         nedges = 0;
        }
     }
 
Index: src/output.c
--- src/output.c Sat, 17 Nov 2001 17:06:51 +0100 akim
+++ src/output.c Sat, 01 Dec 2001 19:42:06 +0100 akim
@@ -587,40 +587,33 @@
        }
     }
 
-  shiftp = state_table[state].shift_table;
-
   /* Now see which tokens are allowed for shifts in this state.  For
      them, record the shift as the thing to do.  So shift is preferred
      to reduce.  */
+  shiftp = state_table[state].shift_table;
 
-  if (shiftp)
+  for (i = 0; i < shiftp->nshifts; i++)
     {
-      k = shiftp->nshifts;
+      shift_state = shiftp->shifts[i];
+      if (!shift_state)
+       continue;
 
-      for (i = 0; i < k; i++)
-       {
-         shift_state = shiftp->shifts[i];
-         if (!shift_state)
-           continue;
-
-         symbol = state_table[shift_state].accessing_symbol;
-
-         if (ISVAR (symbol))
-           break;
-
-         actrow[symbol] = shift_state;
-
-         /* Do not use any default reduction if there is a shift for
-            error */
-         if (symbol == error_token_number)
-           nodefault = 1;
-       }
-    }
+      symbol = state_table[shift_state].accessing_symbol;
 
-  errp = err_table[state];
+      if (ISVAR (symbol))
+       break;
+
+      actrow[symbol] = shift_state;
+
+      /* Do not use any default reduction if there is a shift for
+        error */
+      if (symbol == error_token_number)
+       nodefault = 1;
+    }
 
   /* See which tokens are an explicit error in this state (due to
      %nonassoc).  For them, record MINSHORT as the action.  */
+  errp = err_table[state];
 
   if (errp)
     {
Index: src/print.c
--- src/print.c Fri, 30 Nov 2001 00:04:35 +0100 akim
+++ src/print.c Sat, 01 Dec 2001 19:48:15 +0100 akim
@@ -86,13 +86,12 @@
 print_actions (FILE *out, int state)
 {
   int i;
-  int k;
 
   shifts   *shiftp = state_table[state].shift_table;
   reductions *redp = state_table[state].reduction_table;
   errs       *errp = err_table[state];
 
-  if (!shiftp && !redp)
+  if (!shiftp->nshifts && !redp)
     {
       if (final_state == state)
        fprintf (out, _("    $default\taccept\n"));
@@ -101,37 +100,25 @@
       return;
     }
 
-  if (shiftp)
-    {
-      k = shiftp->nshifts;
-
-      for (i = 0; i < k; i++)
-       {
-         int symbol;
-         int state1 = shiftp->shifts[i];
-         if (!state1)
-           continue;
-         symbol = state_table[state1].accessing_symbol;
-         /* The following line used to be turned off.  */
-         if (ISVAR (symbol))
-           break;
-         if (symbol == 0)      /* I.e. strcmp(tags[symbol],"$")==0 */
-           fprintf (out,
-                    _("    $   \tgo to state %d\n"), state1);
-         else
-           fprintf (out,
-                    _("    %-4s\tshift, and go to state %d\n"),
-                    tags[symbol], state1);
-       }
+  for (i = 0; i < shiftp->nshifts; i++)
+    if (!SHIFT_IS_DISABLED (shiftp, i))
+      {
+       int state1 = shiftp->shifts[i];
+       int symbol = state_table[state1].accessing_symbol;
+       /* The following line used to be turned off.  */
+       if (ISVAR (symbol))
+         break;
+       if (symbol == 0)        /* I.e. strcmp(tags[symbol],"$")==0 */
+         fprintf (out,
+                  _("    $   \tgo to state %d\n"), state1);
+       else
+         fprintf (out,
+                  _("    %-4s\tshift, and go to state %d\n"),
+                  tags[symbol], state1);
+      }
 
-      if (i > 0)
-       fputc ('\n', out);
-    }
-  else
-    {
-      i = 0;
-      k = 0;
-    }
+  if (i > 0)
+    fputc ('\n', out);
 
   if (errp)
     {
@@ -161,18 +148,16 @@
       print_reductions (out, state);
     }
 
-  if (i < k)
+  if (i < shiftp->nshifts)
     {
-      for (; i < k; i++)
-       {
-         int symbol;
-         int state1 = shiftp->shifts[i];
-         if (!state1)
-           continue;
-         symbol = state_table[state1].accessing_symbol;
-         fprintf (out, _("    %-4s\tgo to state %d\n"),
-                  tags[symbol], state1);
-       }
+      for (; i < shiftp->nshifts; i++)
+       if (!SHIFT_IS_DISABLED (shiftp, i))
+         {
+           int state1 = shiftp->shifts[i];
+           int symbol = state_table[state1].accessing_symbol;
+           fprintf (out, _("    %-4s\tgo to state %d\n"),
+                    tags[symbol], state1);
+         }
 
       fputc ('\n', out);
     }
Index: src/state.h
--- src/state.h Sat, 01 Dec 2001 19:38:04 +0100 akim
+++ src/state.h Sat, 01 Dec 2001 20:03:10 +0100 akim
@@ -1,5 +1,5 @@
 /* Type definitions for nondeterministic finite state machine for bison,
-   Copyright 1984, 1989, 2000 Free Software Foundation, Inc.
+   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -123,6 +123,9 @@
 #define SHIFTS_ALLOC(Nshifts)                                          \
   (shifts *) xcalloc ((unsigned) (sizeof (shifts)                      \
                                   + (Nshifts - 1) * sizeof (short)), 1)
+
+shifts * shifts_new PARAMS ((int n));
+
 
 /* What is the symbol which is shifted by SHIFTS->shifts[Shift]?  Can
    be a token (amongst which the error token), or non terminals in
Index: src/state.c
--- src/state.c Sat, 01 Dec 2001 20:18:55 +0100 akim
+++ src/state.c Sat, 01 Dec 2001 20:04:20 +0100 akim
@@ -0,0 +1,35 @@
+/* Type definitions for nondeterministic finite state machine for bison,
+   Copyright 2001 Free Software Foundation, Inc.
+
+   This file is part of Bison, the GNU Compiler Compiler.
+
+   Bison is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   Bison is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with Bison; see the file COPYING.  If not, write to
+   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+
+#include "system.h"
+#include "state.h"
+
+/*---------------------------------.
+| Create a new array of N shitfs.  |
+`---------------------------------*/
+
+shifts *
+shifts_new (int n)
+{
+  shifts *res = SHIFTS_ALLOC (n);
+  res->nshifts = n;
+  return res;
+}