15-fyi-LA-bitset.patch

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>
        * src/L0.c, src/LR0.h (nstates): Be size_t.
        Adjust comparisons (signed vs unsigned).
        * src/conflics.c, src/lalr.c, src/lalr.h, src/output.c (LA): Now a
        bitset*.
        Adjust all dependencies.
        
        
Index: src/LR0.c
--- src/LR0.c Sat, 26 Jan 2002 17:16:02 +0100 akim
+++ src/LR0.c Fri, 01 Mar 2002 15:15:40 +0100 akim
@@ -1,5 +1,5 @@
 /* Generate the nondeterministic finite state machine for bison,
-   Copyright 1984, 1986, 1989, 2000, 2001  Free Software Foundation, Inc.
+   Copyright 1984, 1986, 1989, 2000, 2001, 2002  Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -23,6 +23,7 @@
    The entry point is generate_states.  */
 
 #include "system.h"
+#include "bitset.h"
 #include "symtab.h"
 #include "getargs.h"
 #include "reader.h"
@@ -34,7 +35,7 @@
 #include "lalr.h"
 #include "reduce.h"
 
-int nstates;
+unsigned int nstates;
 /* Initialize the final state to -1, otherwise, it might be set to 0
    by default, and since we don't compute the reductions of the final
    state, we end up not computing the reductions of the initial state,
Index: src/LR0.h
--- src/LR0.h Sat, 08 Dec 2001 20:47:14 +0100 akim
+++ src/LR0.h Fri, 01 Mar 2002 15:15:54 +0100 akim
@@ -1,5 +1,5 @@
 /* Generate the nondeterministic finite state machine for bison,
-   Copyright 1984, 1986, 1989, 2000, 2001  Free Software Foundation, Inc.
+   Copyright 1984, 1986, 1989, 2000, 2001, 2002  Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -25,7 +25,7 @@
 
 void generate_states PARAMS ((void));
 
-extern int nstates;
+extern unsigned int nstates;
 extern int final_state;
 
 #endif /* !LR0_H_ */
Index: src/conflicts.c
--- src/conflicts.c Sun, 06 Jan 2002 21:12:55 +0100 akim
+++ src/conflicts.c Fri, 01 Mar 2002 15:16:07 +0100 akim
@@ -1,5 +1,5 @@
 /* Find and resolve or report look-ahead conflicts for bison,
-   Copyright 1984, 1989, 1992, 2000, 2001 Free Software Foundation, Inc.
+   Copyright 1984, 1989, 1992, 2000, 2001, 2002 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -19,6 +19,7 @@
    02111-1307, USA.  */
 
 #include "system.h"
+#include "bitset.h"
 #include "complain.h"
 #include "getargs.h"
 #include "symtab.h"
@@ -78,7 +79,7 @@
 static void
 flush_reduce (int lookahead, int token)
 {
-  RESETBIT (LA (lookahead), token);
+  bitset_reset (LA[lookahead], token);
 }
 
 
@@ -99,7 +100,7 @@
   errp->nerrs = 0;
 
   for (i = 0; i < ntokens; i++)
-    if (BITISSET (LA (lookahead), i)
+    if (bitset_test (LA[lookahead], i)
        && BITISSET (lookaheadset, i)
        && symbols[i]->prec)
       {
@@ -173,8 +174,9 @@
      precedence */
   for (i = 0; i < state->nlookaheads; ++i)
     if (rules[LAruleno[state->lookaheadsp + i]].prec)
-      for (j = 0; j < tokensetsize; ++j)
-       if (LA (state->lookaheadsp + i)[j] & lookaheadset[j])
+      for (j = 0; j < ntokens; ++j)
+       if (bitset_test (LA[state->lookaheadsp + i], j)
+           && BITISSET (lookaheadset, j))
          {
            resolve_sr_conflict (state, state->lookaheadsp + i);
            break;
@@ -185,19 +187,21 @@
      for conflicts not resolved above.  */
   for (i = 0; i < state->nlookaheads; ++i)
     {
-      for (j = 0; j < tokensetsize; ++j)
-       if (LA (state->lookaheadsp + i)[j] & lookaheadset[j])
+      for (j = 0; j < ntokens; ++j)
+       if (bitset_test (LA[state->lookaheadsp + i], j)
+           && BITISSET (lookaheadset, j))
          conflicts[state->number] = 1;
 
-      for (j = 0; j < tokensetsize; ++j)
-       lookaheadset[j] |= LA (state->lookaheadsp + i)[j];
+      for (j = 0; j < ntokens; ++j)
+       if (bitset_test (LA[state->lookaheadsp + i], j))
+         SETBIT (lookaheadset, j);
     }
 }
 
 void
 solve_conflicts (void)
 {
-  int i;
+  size_t i;
 
   conflicts = XCALLOC (char, nstates);
   shiftset = XCALLOC (unsigned, tokensetsize);
@@ -233,8 +237,9 @@
       SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
 
   for (i = 0; i < state->nlookaheads; ++i)
-    for (k = 0; k < tokensetsize; ++k)
-      lookaheadset[k] |= LA (state->lookaheadsp + i)[k];
+    for (k = 0; k < ntokens; ++k)
+      if (bitset_test (LA[state->lookaheadsp + i], k))
+       SETBIT (lookaheadset, k);
 
   for (k = 0; k < tokensetsize; ++k)
     lookaheadset[k] &= shiftset[k];
@@ -265,7 +270,7 @@
       int count = 0;
       int j;
       for (j = 0; j < state->nlookaheads; ++j)
-       if (BITISSET (LA (state->lookaheadsp + j), i))
+       if (bitset_test (LA[state->lookaheadsp + j], i))
          count++;
 
       if (count >= 2)
@@ -322,7 +327,7 @@
 conflicts_output (FILE *out)
 {
   bool printed_sth = FALSE;
-  int i;
+  size_t i;
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
@@ -343,7 +348,7 @@
 void
 conflicts_print (void)
 {
-  int i;
+  size_t i;
 
   /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
      not set, and then we want 0 SR, or else it is specified, in which
Index: src/lalr.c
--- src/lalr.c Fri, 28 Dec 2001 16:47:09 +0100 akim
+++ src/lalr.c Fri, 01 Mar 2002 15:16:40 +0100 akim
@@ -24,6 +24,7 @@
    tokens they accept.  */
 
 #include "system.h"
+#include "bitset.h"
 #include "reader.h"
 #include "types.h"
 #include "LR0.h"
@@ -39,14 +40,14 @@
 state_t **states = NULL;
 
 int tokensetsize;
-short *LAruleno;
-unsigned *LA;
+short *LAruleno = NULL;
+bitset *LA = NULL;
 size_t nLA;
 
 static int ngotos;
-short *goto_map;
-short *from_state;
-short *to_state;
+short *goto_map = NULL;
+short *from_state = NULL;
+short *to_state = NULL;
 
 /* And for the famous F variable, which name is so descriptive that a
    comment is hardly needed.  <grin>.  */
@@ -136,7 +137,7 @@
 static void
 initialize_LA (void)
 {
-  int i;
+  size_t i;
   int j;
   short *np;
 
@@ -144,7 +145,12 @@
   if (!nLA)
     nLA = 1;
 
-  LA = XCALLOC (unsigned, nLA * tokensetsize);
+  LA = XCALLOC (bitset, nLA);
+  for (i = 0; i < nLA; ++i)
+    {
+      LA[i] = bitset_create (ntokens, BITSET_FIXED);
+      bitset_zero (LA[i]);
+    }
   LAruleno = XCALLOC (short, nLA);
   lookback = XCALLOC (shorts *, nLA);
 
@@ -159,7 +165,8 @@
 static void
 set_goto_map (void)
 {
-  int state, i;
+  size_t state;
+  int i;
   short *temp_map;
 
   goto_map = XCALLOC (short, nvars + 1) - ntokens;
@@ -494,10 +501,10 @@
   for (i = 0; i < nLA; i++)
     for (sp = lookback[i]; sp; sp = sp->next)
       {
-       int size = LA (i + 1) - LA (i);
        int j;
-       for (j = 0; j < size; ++j)
-         LA (i)[j] |= F (sp->value)[j];
+       for (j = 0; j < ntokens; ++j)
+         if (BITISSET (F (sp->value), j))
+           bitset_set (LA[i], j);
       }
 
   /* Free LOOKBACK. */
@@ -516,7 +523,7 @@
 static void
 initialize_lookaheads (void)
 {
-  int i;
+  size_t i;
   nLA = 0;
   for (i = 0; i < nstates; i++)
     {
@@ -556,7 +563,8 @@
 static void
 lookaheads_print (FILE *out)
 {
-  int i, j, k;
+  size_t i;
+  int j, k;
   fprintf (out, "Lookaheads: BEGIN\n");
   for (i = 0; i < nstates; ++i)
     {
@@ -565,7 +573,7 @@
 
       for (j = 0; j < states[i]->nlookaheads; ++j)
        for (k = 0; k < ntokens; ++k)
-         if (BITISSET (LA (states[i]->lookaheadsp + j), j))
+         if (bitset_test (LA[states[i]->lookaheadsp + j], j))
            fprintf (out, "   on %d (%s) -> rule %d\n",
                     k, symbols[k]->tag,
                     -LAruleno[states[i]->lookaheadsp + j] - 1);
Index: src/lalr.h
--- src/lalr.h Fri, 28 Dec 2001 16:47:09 +0100 akim
+++ src/lalr.h Fri, 01 Mar 2002 15:17:33 +0100 akim
@@ -1,5 +1,5 @@
 /* Compute look-ahead criteria for bison,
-   Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc.
+   Copyright 1984, 1986, 1989, 2000, 2002 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -21,6 +21,7 @@
 #ifndef LALR_H_
 # define LALR_H_
 
+#include "bitset.h"
 
 /* Import the definition of CORE, SHIFTS and REDUCTIONS. */
 # include "state.h"
@@ -65,8 +66,7 @@
    token is symbol i.  If LA[l, i] and LA[l, j] are both 1 for i != j,
    it is a conflict.  */
 
-extern unsigned *LA;
-#define LA(Rule) (LA + (Rule) * tokensetsize)
+extern bitset *LA;
 
 
 /* All the states, indexed by the state number.  */
Index: src/main.c
--- src/main.c Thu, 27 Dec 2001 14:58:13 +0100 akim
+++ src/main.c Fri, 01 Mar 2002 15:17:05 +0100 akim
@@ -1,5 +1,5 @@
 /* Top level entry point of bison,
-   Copyright 1984, 1986, 1989, 1992, 1995, 2000, 2001
+   Copyright 1984, 1986, 1989, 1992, 1995, 2000, 2001, 2002
    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
@@ -21,6 +21,7 @@
 
 
 #include "system.h"
+#include "bitset.h"
 #include "getargs.h"
 #include "files.h"
 #include "complain.h"
Index: src/output.c
--- src/output.c Mon, 04 Feb 2002 23:18:59 +0100 akim
+++ src/output.c Fri, 01 Mar 2002 15:19:48 +0100 akim
@@ -226,7 +226,7 @@
 static void
 output_stos (void)
 {
-  int i;
+  size_t i;
   short *values = (short *) alloca (sizeof (short) * nstates);
   for (i = 0; i < nstates; ++i)
     values[i] = states[i]->accessing_symbol;
@@ -355,7 +355,7 @@
        for (j = 0; j < ntokens; j++)
          /* and record this rule as the rule to use if that
             token follows.  */
-         if (BITISSET (LA (state->lookaheadsp + i), j))
+         if (bitset_test (LA[state->lookaheadsp + i], j))
            actrow[j] = -LAruleno[state->lookaheadsp + i];
     }
 
@@ -487,7 +487,7 @@
 static void
 token_actions (void)
 {
-  int i;
+  size_t i;
   short *yydefact = XCALLOC (short, nstates);
 
   actrow = XCALLOC (short, ntokens);
@@ -640,9 +640,9 @@
 static int
 default_goto (int symbol)
 {
-  int i;
-  int m = goto_map[symbol];
-  int n = goto_map[symbol + 1];
+  size_t i;
+  size_t m = goto_map[symbol];
+  size_t n = goto_map[symbol + 1];
   int default_state = -1;
   int max = 0;
 
@@ -740,7 +740,7 @@
   int w;
   int prev;
 
-  if (i >= nstates)
+  if (i >= (int) nstates)
     return -1;
 
   t = tally[i];
@@ -912,7 +912,7 @@
 static void
 output_actions (void)
 {
-  int i;
+  size_t i;
   nvectors = nstates + nvars;
 
   froms = XCALLOC (short *, nvectors);
Index: src/print.c
--- src/print.c Tue, 26 Feb 2002 23:24:19 +0100 akim
+++ src/print.c Fri, 01 Mar 2002 15:19:46 +0100 akim
@@ -216,7 +216,7 @@
       int default_rule = LAruleno[state->lookaheadsp];
 
       for (i = 0; i < ntokens; ++i)
-       if (BITISSET (LA (state->lookaheadsp), i)
+       if (bitset_test (LA[state->lookaheadsp], i)
            && bitset_test (shiftset, i))
          bitset_set (lookaheadset, i);
        else
@@ -244,7 +244,7 @@
            int j, k;
 
            for (k = 0; k < ntokens; ++k)
-             if (BITISSET (LA (state->lookaheadsp + i), k)
+             if (bitset_test (LA[state->lookaheadsp + i], k)
                  && ! bitset_test (shiftset, k))
                bitset_set (lookaheadset, k);
              else
@@ -278,7 +278,7 @@
 
          for (j = 0; j < state->nlookaheads; ++j)
            {
-             if (BITISSET (LA (state->lookaheadsp + j), i))
+             if (bitset_test (LA[state->lookaheadsp + j], i))
                {
                  if (count == 0)
                    {
@@ -479,7 +479,7 @@
 void
 print_results (void)
 {
-  int i;
+  size_t i;
 
   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
      that conflicts with Posix.  */
Index: src/print_graph.c
--- src/print_graph.c Fri, 28 Dec 2001 16:47:09 +0100 akim
+++ src/print_graph.c Fri, 01 Mar 2002 15:19:48 +0100 akim
@@ -172,7 +172,7 @@
 void
 print_graph (void)
 {
-  int i;
+  size_t i;
 
   /* Output file.  */
   fgraph = xfopen (spec_graph_file, "w");