Use bitset operations when possible, not loops over bits.

[bison.git] / src / conflicts.c

diff --git a/src/conflicts.c b/src/conflicts.c
index 01fff4f12cc0632b67d6c1255a59e0a8919d4f9f..e08256a161b8b9e8ec6eab7a67afebe3e0660da6 100644 (file)
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -1,5 +1,5 @@
 /* Find and resolve or report look-ahead conflicts for bison,
 /* 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.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 


@@ -19,8 +19,10 @@
    02111-1307, USA.  */
 
 #include "system.h"
    02111-1307, USA.  */
 
 #include "system.h"

+#include "bitset.h"

 #include "complain.h"
 #include "getargs.h"
 #include "complain.h"
 #include "getargs.h"

+#include "symtab.h"

 #include "files.h"
 #include "gram.h"
 #include "state.h"
 #include "files.h"
 #include "gram.h"
 #include "state.h"


@@ -33,8 +35,8 @@
 int expected_conflicts = -1;
 static char *conflicts = NULL;
 
 int expected_conflicts = -1;
 static char *conflicts = NULL;
 

-static unsigned *shiftset = NULL;
-static unsigned *lookaheadset = NULL;
+static bitset shiftset;
+static bitset lookaheadset;

 \f
 
 static inline void
 \f
 
 static inline void


@@ -44,7 +46,8 @@ log_resolution (state_t *state, int LAno, int token, char *resolution)
     obstack_fgrow4 (&output_obstack,
                    _("\
 Conflict in state %d between rule %d and token %s resolved as %s.\n"),
     obstack_fgrow4 (&output_obstack,
                    _("\
 Conflict in state %d between rule %d and token %s resolved as %s.\n"),

-                   state->number, LAruleno[LAno], tags[token], resolution);
+                   state->number, LAruleno[LAno], symbols[token]->tag,
+                   resolution);

 }
 
 
 }
 
 


@@ -60,7 +63,7 @@ flush_shift (state_t *state, int token)
   shifts *shiftp = state->shifts;
   int i;
 
   shifts *shiftp = state->shifts;
   int i;
 

-  RESETBIT (lookaheadset, token);
+  bitset_reset (lookaheadset, token);

   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);


@@ -76,7 +79,7 @@ flush_shift (state_t *state, int token)
 static void
 flush_reduce (int lookahead, int token)
 {
 static void
 flush_reduce (int lookahead, int token)
 {

-  RESETBIT (LA (lookahead), token);
+  bitset_reset (LA[lookahead], token);

 }
 
 
 }
 
 


@@ -92,24 +95,24 @@ resolve_sr_conflict (state_t *state, int lookahead)
 {
   int i;
   /* find the rule to reduce by to get precedence of reduction  */
 {
   int i;
   /* find the rule to reduce by to get precedence of reduction  */

-  int redprec = rule_table[LAruleno[lookahead]].prec;
-  errs *errp = ERRS_ALLOC (ntokens + 1);
-  short *errtokens = errp->errs;
+  int redprec = rules[LAruleno[lookahead]].prec;
+  errs *errp = errs_new (ntokens + 1);
+  errp->nerrs = 0;

 
   for (i = 0; i < ntokens; i++)
 
   for (i = 0; i < ntokens; i++)

-    if (BITISSET (LA (lookahead), i)
-       && BITISSET (lookaheadset, i)
-       && sprec[i])
+    if (bitset_test (LA[lookahead], i)
+       && bitset_test (lookaheadset, i)
+       && symbols[i]->prec)

       {
        /* Shift-reduce conflict occurs for token number i
           and it has a precedence.
           The precedence of shifting is that of token i.  */
       {
        /* Shift-reduce conflict occurs for token number i
           and it has a precedence.
           The precedence of shifting is that of token i.  */

-       if (sprec[i] < redprec)
+       if (symbols[i]->prec < redprec)

          {
            log_resolution (state, lookahead, i, _("reduce"));
            flush_shift (state, i);
          }
          {
            log_resolution (state, lookahead, i, _("reduce"));
            flush_shift (state, i);
          }

-       else if (sprec[i] > redprec)
+       else if (symbols[i]->prec > redprec)

          {
            log_resolution (state, lookahead, i, _("shift"));
            flush_reduce (lookahead, i);
          {
            log_resolution (state, lookahead, i, _("shift"));
            flush_reduce (lookahead, i);


@@ -120,7 +123,7 @@ resolve_sr_conflict (state_t *state, int lookahead)
             For right association, keep only the shift.
             For nonassociation, keep neither.  */
 
             For right association, keep only the shift.
             For nonassociation, keep neither.  */
 

-         switch (sassoc[i])
+         switch (symbols[i]->assoc)

            {
            case right_assoc:
              log_resolution (state, lookahead, i, _("shift"));
            {
            case right_assoc:
              log_resolution (state, lookahead, i, _("shift"));


@@ -137,17 +140,14 @@ resolve_sr_conflict (state_t *state, int lookahead)
              flush_shift (state, i);
              flush_reduce (lookahead, i);
              /* Record an explicit error for this token.  */
              flush_shift (state, i);
              flush_reduce (lookahead, i);
              /* Record an explicit error for this token.  */

-             *errtokens++ = i;
+             errp->errs[errp->nerrs++] = i;

              break;
            }
       }
 
              break;
            }
       }
 

-  errp->nerrs = errtokens - errp->errs;

   /* Some tokens have been explicitly made errors.  Allocate a
      permanent errs structure for this state, to record them.  */
   /* Some tokens have been explicitly made errors.  Allocate a
      permanent errs structure for this state, to record them.  */

-  i = (char *) errtokens - (char *) errp;
-  state->errs = ERRS_ALLOC (i + 1);
-  memcpy (state->errs, errp, i);
+  state->errs = errs_dup (errp);

   free (errp);
 }
 
   free (errp);
 }
 


@@ -161,21 +161,21 @@ set_conflicts (state_t *state)
   if (state->consistent)
     return;
 
   if (state->consistent)
     return;
 

-  for (i = 0; i < tokensetsize; i++)
-    lookaheadset[i] = 0;
+  bitset_zero (lookaheadset);

 
   shiftp = state->shifts;
   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
     if (!SHIFT_IS_DISABLED (shiftp, i))
 
   shiftp = state->shifts;
   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
     if (!SHIFT_IS_DISABLED (shiftp, i))

-      SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i));
+      bitset_set (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
      precedence */
   for (i = 0; i < state->nlookaheads; ++i)
 
   /* Loop over all rules which require lookahead in this state.  First
      check for shift-reduce conflict, and try to resolve using
      precedence */
   for (i = 0; i < state->nlookaheads; ++i)

-    if (rule_table[LAruleno[state->lookaheadsp + i]].prec)
-      for (j = 0; j < tokensetsize; ++j)
-       if (LA (state->lookaheadsp + i)[j] & lookaheadset[j])
+    if (rules[LAruleno[state->lookaheadsp + i]].prec)
+      for (j = 0; j < ntokens; ++j)
+       if (bitset_test (LA[state->lookaheadsp + i], j)
+           && bitset_test (lookaheadset, j))

          {
            resolve_sr_conflict (state, state->lookaheadsp + i);
            break;
          {
            resolve_sr_conflict (state, state->lookaheadsp + i);
            break;


@@ -186,26 +186,29 @@ set_conflicts (state_t *state)
      for conflicts not resolved above.  */
   for (i = 0; i < state->nlookaheads; ++i)
     {
      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])
+      /* FIXME: Here, I need something like `bitset_disjoint_p'. */
+      for (j = 0; j < ntokens; ++j)
+       if (bitset_test (LA[state->lookaheadsp + i], j)
+           && bitset_test (lookaheadset, j))

          conflicts[state->number] = 1;
 
          conflicts[state->number] = 1;
 

-      for (j = 0; j < tokensetsize; ++j)
-       lookaheadset[j] |= LA (state->lookaheadsp + i)[j];
+      bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);

     }
 }
 
 void
 solve_conflicts (void)
 {
     }
 }
 
 void
 solve_conflicts (void)
 {

-  int i;
+  size_t i;

 
   conflicts = XCALLOC (char, nstates);
 
   conflicts = XCALLOC (char, nstates);

-  shiftset = XCALLOC (unsigned, tokensetsize);
-  lookaheadset = XCALLOC (unsigned, tokensetsize);
+  shiftset = bitset_create (ntokens, BITSET_FIXED);
+  bitset_zero (shiftset);
+  lookaheadset = bitset_create (ntokens, BITSET_FIXED);
+  bitset_zero (lookaheadset);

 
   for (i = 0; i < nstates; i++)
 
   for (i = 0; i < nstates; i++)

-    set_conflicts (state_table[i]);
+    set_conflicts (states[i]);

 }
 
 
 }
 
 


@@ -216,32 +219,27 @@ solve_conflicts (void)
 static int
 count_sr_conflicts (state_t *state)
 {
 static int
 count_sr_conflicts (state_t *state)
 {

-  int i, k;
+  int i;

   int src_count = 0;
   shifts *shiftp = state->shifts;
 
   if (!shiftp)
     return 0;
 
   int src_count = 0;
   shifts *shiftp = state->shifts;
 
   if (!shiftp)
     return 0;
 

-  for (i = 0; i < tokensetsize; i++)
-    {
-      shiftset[i] = 0;
-      lookaheadset[i] = 0;
-    }
+  bitset_zero (lookaheadset);
+  bitset_zero (shiftset);

 
   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
     if (!SHIFT_IS_DISABLED (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));
+      bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));

 
   for (i = 0; i < state->nlookaheads; ++i)
 
   for (i = 0; i < state->nlookaheads; ++i)

-    for (k = 0; k < tokensetsize; ++k)
-      lookaheadset[k] |= LA (state->lookaheadsp + i)[k];
+    bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);

 
 

-  for (k = 0; k < tokensetsize; ++k)
-    lookaheadset[k] &= shiftset[k];
+  bitset_and (lookaheadset, lookaheadset, shiftset);

 
   for (i = 0; i < ntokens; i++)
 
   for (i = 0; i < ntokens; i++)

-    if (BITISSET (lookaheadset, i))
+    if (bitset_test (lookaheadset, i))

       src_count++;
 
   return src_count;
       src_count++;
 
   return src_count;


@@ -266,7 +264,7 @@ count_rr_conflicts (state_t *state)
       int count = 0;
       int j;
       for (j = 0; j < state->nlookaheads; ++j)
       int count = 0;
       int j;
       for (j = 0; j < state->nlookaheads; ++j)

-       if (BITISSET (LA (state->lookaheadsp), state->lookaheadsp + j))
+       if (bitset_test (LA[state->lookaheadsp + j], i))

          count++;
 
       if (count >= 2)
          count++;
 
       if (count >= 2)


@@ -323,13 +321,13 @@ void
 conflicts_output (FILE *out)
 {
   bool printed_sth = FALSE;
 conflicts_output (FILE *out)
 {
   bool printed_sth = FALSE;

-  int i;
+  size_t i;

   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
        fprintf (out, _("State %d contains "), i);
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
        fprintf (out, _("State %d contains "), i);

-       fputs (conflict_report (count_sr_conflicts (state_table[i]),
-                               count_rr_conflicts (state_table[i])), out);
+       fputs (conflict_report (count_sr_conflicts (states[i]),
+                               count_rr_conflicts (states[i])), out);

        printed_sth = TRUE;
       }
   if (printed_sth)
        printed_sth = TRUE;
       }
   if (printed_sth)


@@ -344,7 +342,7 @@ conflicts_output (FILE *out)
 void
 conflicts_print (void)
 {
 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
 
   /* 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


@@ -358,8 +356,8 @@ conflicts_print (void)
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {

-       src_total += count_sr_conflicts (state_table[i]);
-       rrc_total += count_rr_conflicts (state_table[i]);
+       src_total += count_sr_conflicts (states[i]);
+       rrc_total += count_rr_conflicts (states[i]);

       }
 
   src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);
       }
 
   src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);


@@ -404,6 +402,6 @@ void
 free_conflicts (void)
 {
   XFREE (conflicts);
 free_conflicts (void)
 {
   XFREE (conflicts);

-  XFREE (shiftset);
-  XFREE (lookaheadset);
+  bitset_free (shiftset);
+  bitset_free (lookaheadset);

 }
 }