2007-01-30 Paolo Bonzini <bonzini@gnu.org>

[bison.git] / src / conflicts.c

diff --git a/src/conflicts.c b/src/conflicts.c
index 21ea7ce548be5aea3bcd7dc04bef6a6971d79df0..7bb3e08ee585e74ec236ee381923372e1ea7f106 100644 (file)
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -1,6 +1,6 @@
-/* Find and resolve or report look-ahead conflicts for bison,
+/* Find and resolve or report lookahead conflicts for bison,

 
 

-   Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003
+   Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005, 2006

    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.


@@ -17,9 +17,10 @@
 
    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
 
    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.  */
+   Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA.  */

 
 

+#include <config.h>

 #include "system.h"
 
 #include <bitset.h>
 #include "system.h"
 
 #include <bitset.h>


@@ -36,12 +37,13 @@
 #include "symtab.h"
 
 /* -1 stands for not specified. */
 #include "symtab.h"
 
 /* -1 stands for not specified. */

-int expected_conflicts = -1;
-static char *conflicts = NULL;
-struct obstack solved_conflicts_obstack;
+int expected_sr_conflicts = -1;
+int expected_rr_conflicts = -1;
+static char *conflicts;
+static struct obstack solved_conflicts_obstack;

 
 

-static bitset shiftset;
-static bitset lookaheadset;
+static bitset shift_set;
+static bitset lookahead_set;

 
 \f
 
 
 \f
 


@@ -145,7 +147,7 @@ flush_shift (state *s, int token)
   transitions *trans = s->transitions;
   int i;
 
   transitions *trans = s->transitions;
   int i;
 

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

   for (i = 0; i < trans->num; i++)
     if (!TRANSITION_IS_DISABLED (trans, i)
        && TRANSITION_SYMBOL (trans, i) == token)
   for (i = 0; i < trans->num; i++)
     if (!TRANSITION_IS_DISABLED (trans, i)
        && TRANSITION_SYMBOL (trans, i) == token)


@@ -153,16 +155,16 @@ flush_shift (state *s, int token)
 }
 
 
 }
 
 

-/*-------------------------------------------------------------------.
-| Turn off the reduce recorded for the specified token for the       |
-| specified lookahead.  Used when we resolve a shift-reduce conflict |
-| in favor of the shift.                                             |
-`-------------------------------------------------------------------*/
+/*--------------------------------------------------------------------.
+| Turn off the reduce recorded for the specified token for the        |
+| specified lookahead.  Used when we resolve a shift-reduce conflict  |
+| in favor of the shift.                                              |
+`--------------------------------------------------------------------*/

 
 static void
 
 static void

-flush_reduce (bitset lookaheads, int token)
+flush_reduce (bitset lookahead_tokens, int token)

 {
 {

-  bitset_reset (lookaheads, token);
+  bitset_reset (lookahead_tokens, token);

 }
 
 
 }
 
 


@@ -172,7 +174,7 @@ flush_reduce (bitset lookaheads, int token)
 | rule has a precedence.  A conflict is resolved by modifying the   |
 | shift or reduce tables so that there is no longer a conflict.     |
 |                                                                   |
 | rule has a precedence.  A conflict is resolved by modifying the   |
 | shift or reduce tables so that there is no longer a conflict.     |
 |                                                                   |

-| LOOKAHEAD is the number of the lookahead bitset to consider.      |
+| RULENO is the number of the lookahead bitset to consider.         |

 |                                                                   |
 | ERRORS can be used to store discovered explicit errors.           |
 `------------------------------------------------------------------*/
 |                                                                   |
 | ERRORS can be used to store discovered explicit errors.           |
 `------------------------------------------------------------------*/


@@ -185,12 +187,12 @@ resolve_sr_conflict (state *s, int ruleno, symbol **errors)
   /* Find the rule to reduce by to get precedence of reduction.  */
   rule *redrule = reds->rules[ruleno];
   int redprec = redrule->prec->prec;
   /* Find the rule to reduce by to get precedence of reduction.  */
   rule *redrule = reds->rules[ruleno];
   int redprec = redrule->prec->prec;

-  bitset lookaheads = reds->lookaheads[ruleno];
+  bitset lookahead_tokens = reds->lookahead_tokens[ruleno];

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

-    if (bitset_test (lookaheads, i)
-       && bitset_test (lookaheadset, i)
+    if (bitset_test (lookahead_tokens, i)
+       && bitset_test (lookahead_set, i)

        && symbols[i]->prec)
       {
        /* Shift-reduce conflict occurs for token number i
        && symbols[i]->prec)
       {
        /* Shift-reduce conflict occurs for token number i


@@ -204,7 +206,7 @@ resolve_sr_conflict (state *s, int ruleno, symbol **errors)
        else if (symbols[i]->prec > redprec)
          {
            log_resolution (redrule, i, shift_resolution);
        else if (symbols[i]->prec > redprec)
          {
            log_resolution (redrule, i, shift_resolution);

-           flush_reduce (lookaheads, i);
+           flush_reduce (lookahead_tokens, i);

          }
        else
          /* Matching precedence levels.
          }
        else
          /* Matching precedence levels.


@@ -214,9 +216,12 @@ resolve_sr_conflict (state *s, int ruleno, symbol **errors)
 
          switch (symbols[i]->assoc)
            {
 
          switch (symbols[i]->assoc)
            {

+           default:
+             abort ();
+

            case right_assoc:
              log_resolution (redrule, i, right_resolution);
            case right_assoc:
              log_resolution (redrule, i, right_resolution);

-             flush_reduce (lookaheads, i);
+             flush_reduce (lookahead_tokens, i);

              break;
 
            case left_assoc:
              break;
 
            case left_assoc:


@@ -227,19 +232,19 @@ resolve_sr_conflict (state *s, int ruleno, symbol **errors)
            case non_assoc:
              log_resolution (redrule, i, nonassoc_resolution);
              flush_shift (s, i);
            case non_assoc:
              log_resolution (redrule, i, nonassoc_resolution);
              flush_shift (s, i);

-             flush_reduce (lookaheads, i);
+             flush_reduce (lookahead_tokens, i);

              /* Record an explicit error for this token.  */
              errors[nerrs++] = symbols[i];
              break;
              /* Record an explicit error for this token.  */
              errors[nerrs++] = symbols[i];
              break;

-
-           case undef_assoc:
-             abort ();

            }
       }
 
            }
       }
 

-  /* Some tokens have been explicitly made errors.  Allocate a
-     permanent errs structure for this state, to record them.  */
-  state_errs_set (s, nerrs, errors);
+  if (nerrs)
+    {
+      /* Some tokens have been explicitly made errors.  Allocate a
+        permanent errs structure for this state, to record them.  */
+      state_errs_set (s, nerrs, errors);
+    }

 
   if (obstack_object_size (&solved_conflicts_obstack))
     {
 
   if (obstack_object_size (&solved_conflicts_obstack))
     {


@@ -253,7 +258,7 @@ resolve_sr_conflict (state *s, int ruleno, symbol **errors)
 | Solve the S/R conflicts of state S using the                       |
 | precedence/associativity, and flag it inconsistent if it still has |
 | conflicts.  ERRORS can be used as storage to compute the list of   |
 | Solve the S/R conflicts of state S using the                       |
 | precedence/associativity, and flag it inconsistent if it still has |
 | conflicts.  ERRORS can be used as storage to compute the list of   |

-| lookaheads on which S raises a syntax error (%nonassoc).           |
+| lookahead tokens on which S raises a syntax error (%nonassoc).     |

 `-------------------------------------------------------------------*/
 
 static void
 `-------------------------------------------------------------------*/
 
 static void


@@ -266,30 +271,27 @@ set_conflicts (state *s, symbol **errors)
   if (s->consistent)
     return;
 
   if (s->consistent)
     return;
 

-  bitset_zero (lookaheadset);
+  bitset_zero (lookahead_set);

 
   FOR_EACH_SHIFT (trans, i)
 
   FOR_EACH_SHIFT (trans, i)

-    bitset_set (lookaheadset, TRANSITION_SYMBOL (trans, i));
+    bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, 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 < reds->num; ++i)
     if (reds->rules[i]->prec && reds->rules[i]->prec->prec
 
   /* 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 < reds->num; ++i)
     if (reds->rules[i]->prec && reds->rules[i]->prec->prec

-       && !bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
-      {
-       resolve_sr_conflict (s, i, errors);
-       break;
-      }
+       && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
+      resolve_sr_conflict (s, i, errors);

 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */
   for (i = 0; i < reds->num; ++i)
     {
 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */
   for (i = 0; i < reds->num; ++i)
     {

-      if (!bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
+      if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))

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

-      bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
+      bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);

     }
 }
 
     }
 }
 


@@ -303,12 +305,12 @@ void
 conflicts_solve (void)
 {
   state_number i;
 conflicts_solve (void)
 {
   state_number i;

-  /* List of lookaheads on which we explicitly raise a syntax error.  */
-  symbol **errors = MALLOC (errors, ntokens + 1);
+  /* List of lookahead tokens on which we explicitly raise a syntax error.  */
+  symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);

 
 

-  CALLOC (conflicts, nstates);
-  shiftset = bitset_create (ntokens, BITSET_FIXED);
-  lookaheadset = bitset_create (ntokens, BITSET_FIXED);
+  conflicts = xcalloc (nstates, sizeof *conflicts);
+  shift_set = bitset_create (ntokens, BITSET_FIXED);
+  lookahead_set = bitset_create (ntokens, BITSET_FIXED);

   obstack_init (&solved_conflicts_obstack);
 
   for (i = 0; i < nstates; i++)
   obstack_init (&solved_conflicts_obstack);
 
   for (i = 0; i < nstates; i++)


@@ -340,18 +342,18 @@ count_sr_conflicts (state *s)
   if (!trans)
     return 0;
 
   if (!trans)
     return 0;
 

-  bitset_zero (lookaheadset);
-  bitset_zero (shiftset);
+  bitset_zero (lookahead_set);
+  bitset_zero (shift_set);

 
   FOR_EACH_SHIFT (trans, i)
 
   FOR_EACH_SHIFT (trans, i)

-    bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));
+    bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));

 
   for (i = 0; i < reds->num; ++i)
 
   for (i = 0; i < reds->num; ++i)

-    bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
+    bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);

 
 

-  bitset_and (lookaheadset, lookaheadset, shiftset);
+  bitset_and (lookahead_set, lookahead_set, shift_set);

 
 

-  src_count = bitset_count (lookaheadset);
+  src_count = bitset_count (lookahead_set);

 
   return src_count;
 }
 
   return src_count;
 }


@@ -365,7 +367,7 @@ count_sr_conflicts (state *s)
 +`----------------------------------------------------------------*/
 
 static int
 +`----------------------------------------------------------------*/
 
 static int

-count_rr_conflicts (state *s, int one_per_token)
+count_rr_conflicts (state *s, bool one_per_token)

 {
   int i;
   reductions *reds = s->reductions;
 {
   int i;
   reductions *reds = s->reductions;


@@ -376,7 +378,7 @@ count_rr_conflicts (state *s, int one_per_token)
       int count = 0;
       int j;
       for (j = 0; j < reds->num; ++j)
       int count = 0;
       int j;
       for (j = 0; j < reds->num; ++j)

-       if (bitset_test (reds->lookaheads[j], i))
+       if (bitset_test (reds->lookahead_tokens[j], i))

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


@@ -463,10 +465,13 @@ conflicts_print (void)
   /* 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
      case we want equality.  */
   /* 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
      case we want equality.  */

-  int src_ok = 0;
+  bool src_ok;
+  bool rrc_ok;

 
   int src_total = 0;
   int rrc_total = 0;
 
   int src_total = 0;
   int rrc_total = 0;

+  int src_expected;
+  int rrc_expected;

 
   /* Conflicts by state.  */
   {
 
   /* Conflicts by state.  */
   {


@@ -480,27 +485,42 @@ conflicts_print (void)
        }
   }
 
        }
   }
 

-  src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);
+  if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
+    {
+      warn (_("%%expect-rr applies only to GLR parsers"));
+      expected_rr_conflicts = -1;
+    }

 
 

-  /* If there are no RR conflicts, and as many SR conflicts as
+  src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
+  rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
+  src_ok = src_total == src_expected;
+  rrc_ok = rrc_total == rrc_expected;
+
+  /* If there are as many RR conflicts and SR conflicts as

      expected, then there is nothing to report.  */
      expected, then there is nothing to report.  */

-  if (!rrc_total && src_ok)
+  if (rrc_ok & src_ok)

     return;
 
   /* Report the total number of conflicts on STDERR.  */
     return;
 
   /* Report the total number of conflicts on STDERR.  */

-  if (! yacc_flag)
-    fprintf (stderr, "%s: ", current_file);
-  conflict_report (stderr, src_total, rrc_total);
+  if (src_total | rrc_total)
+    {
+      if (! yacc_flag)
+       fprintf (stderr, "%s: ", current_file);
+      conflict_report (stderr, src_total, rrc_total);
+    }

 
 

-  if (expected_conflicts != -1)
+  if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)

     {
       if (! src_ok)
     {
       if (! src_ok)

-       warn (ngettext ("expected %d shift/reduce conflict",
-                       "expected %d shift/reduce conflicts",
-                       expected_conflicts),
-             expected_conflicts);
-      if (rrc_total)
-       warn (_("expected 0 reduce/reduce conflicts"));
+       complain (ngettext ("expected %d shift/reduce conflict",
+                           "expected %d shift/reduce conflicts",
+                           src_expected),
+                 src_expected);
+      if (! rrc_ok)
+       complain (ngettext ("expected %d reduce/reduce conflict",
+                           "expected %d reduce/reduce conflicts",
+                           rrc_expected),
+                 rrc_expected);

     }
 }
 
     }
 }
 


@@ -508,8 +528,8 @@ conflicts_print (void)
 void
 conflicts_free (void)
 {
 void
 conflicts_free (void)
 {

-  XFREE (conflicts);
-  bitset_free (shiftset);
-  bitset_free (lookaheadset);
+  free (conflicts);
+  bitset_free (shift_set);
+  bitset_free (lookahead_set);

   obstack_free (&solved_conflicts_obstack, NULL);
 }
   obstack_free (&solved_conflicts_obstack, NULL);
 }