Regenerate.

[bison.git] / src / conflicts.c

diff --git a/src/conflicts.c b/src/conflicts.c
index e09b6d8772b6796b459417d57452d55d77973f57..44546e1ca5788adfea7ad25c2e98c52b6d8cf631 100644 (file)
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -1,5 +1,6 @@
 /* Find and resolve or report look-ahead conflicts for bison,
 /* Find and resolve or report look-ahead conflicts for bison,

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

    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.


@@ -20,17 +21,19 @@
    02111-1307, USA.  */
 
 #include "system.h"
    02111-1307, USA.  */
 
 #include "system.h"

-#include "bitset.h"
+
+#include <bitset.h>
+
+#include "LR0.h"

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

-#include "getargs.h"
-#include "symtab.h"
+#include "conflicts.h"

 #include "files.h"
 #include "files.h"

+#include "getargs.h"

 #include "gram.h"
 #include "gram.h"

-#include "state.h"

 #include "lalr.h"
 #include "lalr.h"

-#include "conflicts.h"

 #include "reader.h"
 #include "reader.h"

-#include "LR0.h"
+#include "state.h"
+#include "symtab.h"

 
 /* -1 stands for not specified. */
 int expected_conflicts = -1;
 
 /* -1 stands for not specified. */
 int expected_conflicts = -1;


@@ -42,7 +45,7 @@ static bitset lookaheadset;
 
 \f
 
 
 \f
 

-enum conflict_resolution_e
+enum conflict_resolution

   {
     shift_resolution,
     reduce_resolution,
   {
     shift_resolution,
     reduce_resolution,


@@ -58,8 +61,8 @@ enum conflict_resolution_e
 `----------------------------------------------------------------*/
 
 static inline void
 `----------------------------------------------------------------*/
 
 static inline void

-log_resolution (rule_t *rule, int token,
-               enum conflict_resolution_e resolution)
+log_resolution (rule *r, symbol_number token,
+               enum conflict_resolution resolution)

 {
   if (report_flag & report_solved_conflicts)
     {
 {
   if (report_flag & report_solved_conflicts)
     {


@@ -67,26 +70,26 @@ log_resolution (rule_t *rule, int token,
       switch (resolution)
        {
        case shift_resolution:
       switch (resolution)
        {
        case shift_resolution:

-       case left_resolution:
+       case right_resolution:

          obstack_fgrow2 (&solved_conflicts_obstack,
                          _("\
     Conflict between rule %d and token %s resolved as shift"),
          obstack_fgrow2 (&solved_conflicts_obstack,
                          _("\
     Conflict between rule %d and token %s resolved as shift"),

-                         rule->number,
+                         r->number,

                          symbols[token]->tag);
          break;
        case reduce_resolution:
                          symbols[token]->tag);
          break;
        case reduce_resolution:

-       case right_resolution:
+       case left_resolution:

          obstack_fgrow2 (&solved_conflicts_obstack,
                          _("\
     Conflict between rule %d and token %s resolved as reduce"),
          obstack_fgrow2 (&solved_conflicts_obstack,
                          _("\
     Conflict between rule %d and token %s resolved as reduce"),

-                         rule->number,
+                         r->number,

                          symbols[token]->tag);
          break;
        case nonassoc_resolution:
          obstack_fgrow2 (&solved_conflicts_obstack,
                          _("\
     Conflict between rule %d and token %s resolved as an error"),
                          symbols[token]->tag);
          break;
        case nonassoc_resolution:
          obstack_fgrow2 (&solved_conflicts_obstack,
                          _("\
     Conflict between rule %d and token %s resolved as an error"),

-                         rule->number,
+                         r->number,

                          symbols[token]->tag);
          break;
        }
                          symbols[token]->tag);
          break;
        }


@@ -97,7 +100,7 @@ log_resolution (rule_t *rule, int token,
        case shift_resolution:
          obstack_fgrow2 (&solved_conflicts_obstack,
                          " (%s < %s)",
        case shift_resolution:
          obstack_fgrow2 (&solved_conflicts_obstack,
                          " (%s < %s)",

-                         rule->prec->tag,
+                         r->prec->tag,

                          symbols[token]->tag);
          break;
 
                          symbols[token]->tag);
          break;
 


@@ -105,7 +108,7 @@ log_resolution (rule_t *rule, int token,
          obstack_fgrow2 (&solved_conflicts_obstack,
                          " (%s < %s)",
                          symbols[token]->tag,
          obstack_fgrow2 (&solved_conflicts_obstack,
                          " (%s < %s)",
                          symbols[token]->tag,

-                         rule->prec->tag);
+                         r->prec->tag);

          break;
 
        case left_resolution:
          break;
 
        case left_resolution:


@@ -137,15 +140,16 @@ log_resolution (rule_t *rule, int token,
 `------------------------------------------------------------------*/
 
 static void
 `------------------------------------------------------------------*/
 
 static void

-flush_shift (state_t *state, int token)
+flush_shift (state *s, int token)

 {
 {

-  shifts *shiftp = state->shifts;
+  transitions *trans = s->transitions;

   int i;
 
   bitset_reset (lookaheadset, token);
   int i;
 
   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 < trans->num; i++)
+    if (!TRANSITION_IS_DISABLED (trans, i)
+       && TRANSITION_SYMBOL (trans, i) == token)
+      TRANSITION_DISABLE (trans, i);

 }
 
 
 }
 
 


@@ -169,18 +173,20 @@ flush_reduce (bitset lookaheads, int token)
 | shift or reduce tables so that there is no longer a conflict.     |
 |                                                                   |
 | LOOKAHEAD is the number of the lookahead bitset to consider.      |
 | shift or reduce tables so that there is no longer a conflict.     |
 |                                                                   |
 | LOOKAHEAD is the number of the lookahead bitset to consider.      |

+|                                                                   |
+| ERRORS can be used to store discovered explicit errors.           |

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

-resolve_sr_conflict (state_t *state, int lookahead)
+resolve_sr_conflict (state *s, int ruleno, symbol **errors)

 {
 {

-  int i;
+  symbol_number i;
+  reductions *reds = s->reductions;

   /* Find the rule to reduce by to get precedence of reduction.  */
   /* Find the rule to reduce by to get precedence of reduction.  */

-  rule_t *redrule = state->lookaheads_rule[lookahead];
+  rule *redrule = reds->rules[ruleno];

   int redprec = redrule->prec->prec;
   int redprec = redrule->prec->prec;

-  bitset lookaheads = state->lookaheads[lookahead];
-  errs *errp = errs_new (ntokens + 1);
-  errp->nerrs = 0;
+  bitset lookaheads = reds->lookaheads[ruleno];
+  int nerrs = 0;

 
   for (i = 0; i < ntokens; i++)
     if (bitset_test (lookaheads, i)
 
   for (i = 0; i < ntokens; i++)
     if (bitset_test (lookaheads, i)


@@ -193,7 +199,7 @@ resolve_sr_conflict (state_t *state, int lookahead)
        if (symbols[i]->prec < redprec)
          {
            log_resolution (redrule, i, reduce_resolution);
        if (symbols[i]->prec < redprec)
          {
            log_resolution (redrule, i, reduce_resolution);

-           flush_shift (state, i);
+           flush_shift (s, i);

          }
        else if (symbols[i]->prec > redprec)
          {
          }
        else if (symbols[i]->prec > redprec)
          {


@@ -215,87 +221,107 @@ resolve_sr_conflict (state_t *state, int lookahead)
 
            case left_assoc:
              log_resolution (redrule, i, left_resolution);
 
            case left_assoc:
              log_resolution (redrule, i, left_resolution);

-             flush_shift (state, i);
+             flush_shift (s, i);

              break;
 
            case non_assoc:
              log_resolution (redrule, i, nonassoc_resolution);
              break;
 
            case non_assoc:
              log_resolution (redrule, i, nonassoc_resolution);

-             flush_shift (state, i);
+             flush_shift (s, i);

              flush_reduce (lookaheads, i);
              /* Record an explicit error for this token.  */
              flush_reduce (lookaheads, i);
              /* Record an explicit error for this token.  */

-             errp->errs[errp->nerrs++] = i;
+             errors[nerrs++] = symbols[i];

              break;
 
            case undef_assoc:
              break;
 
            case undef_assoc:

-             assert (symbols[i]->assoc != undef_assoc);
-             break;
+             abort ();

            }
       }
 
            }
       }
 

-  /* Some tokens have been explicitly made errors.  Allocate a
-     permanent errs structure for this state, to record them.  */
-  state->errs = errs_dup (errp);
-  free (errp);
+  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))
     {
       obstack_1grow (&solved_conflicts_obstack, '\0');
 
   if (obstack_object_size (&solved_conflicts_obstack))
     {
       obstack_1grow (&solved_conflicts_obstack, '\0');

-      state->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
+      s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);

     }
 }
 
 
     }
 }
 
 

+/*-------------------------------------------------------------------.
+| 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).           |
+`-------------------------------------------------------------------*/
+

 static void
 static void

-set_conflicts (state_t *state)
+set_conflicts (state *s, symbol **errors)

 {
   int i;
 {
   int i;

-  shifts *shiftp;
+  transitions *trans = s->transitions;
+  reductions *reds = s->reductions;

 
 

-  if (state->consistent)
+  if (s->consistent)

     return;
 
   bitset_zero (lookaheadset);
 
     return;
 
   bitset_zero (lookaheadset);
 

-  shiftp = state->shifts;
-  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
-    if (!SHIFT_IS_DISABLED (shiftp, i))
-      bitset_set (lookaheadset, SHIFT_SYMBOL (shiftp, i));
+  FOR_EACH_SHIFT (trans, i)
+    bitset_set (lookaheadset, 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.  */
 
   /* 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 (state->lookaheads_rule[i]->prec
-       && state->lookaheads_rule[i]->prec->prec
-       && !bitset_disjoint_p (state->lookaheads[i], lookaheadset))
-      {
-       resolve_sr_conflict (state, i);
-       break;
-      }
+  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);

 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */
 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */

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

     {
     {

-      if (!bitset_disjoint_p (state->lookaheads[i], lookaheadset))
-       conflicts[state->number] = 1;
+      if (!bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
+       conflicts[s->number] = 1;

 
 

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

     }
 }
 
     }
 }
 

+
+/*----------------------------------------------------------------.
+| Solve all the S/R conflicts using the precedence/associativity, |
+| and flag as inconsistent the states that still have conflicts.  |
+`----------------------------------------------------------------*/
+

 void
 conflicts_solve (void)
 {
 void
 conflicts_solve (void)
 {

-  size_t i;
+  state_number i;
+  /* List of lookaheads on which we explicitly raise a syntax error.  */
+  symbol **errors = MALLOC (errors, ntokens + 1);

 
 

-  conflicts = XCALLOC (char, nstates);
+  CALLOC (conflicts, nstates);

   shiftset = bitset_create (ntokens, BITSET_FIXED);
   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
   obstack_init (&solved_conflicts_obstack);
 
   for (i = 0; i < nstates; i++)
   shiftset = bitset_create (ntokens, BITSET_FIXED);
   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
   obstack_init (&solved_conflicts_obstack);
 
   for (i = 0; i < nstates; i++)

-    set_conflicts (states[i]);
+    {
+      set_conflicts (states[i], errors);
+
+      /* For uniformity of the code, make sure all the states have a valid
+        `errs' member.  */
+      if (!states[i]->errs)
+       states[i]->errs = errs_new (0, 0);
+    }
+
+  free (errors);

 }
 
 
 }
 
 


@@ -304,24 +330,24 @@ conflicts_solve (void)
 `---------------------------------------------*/
 
 static int
 `---------------------------------------------*/
 
 static int

-count_sr_conflicts (state_t *state)
+count_sr_conflicts (state *s)

 {
   int i;
   int src_count = 0;
 {
   int i;
   int src_count = 0;

-  shifts *shiftp = state->shifts;
+  transitions *trans = s->transitions;
+  reductions *reds = s->reductions;

 
 

-  if (!shiftp)
+  if (!trans)

     return 0;
 
   bitset_zero (lookaheadset);
   bitset_zero (shiftset);
 
     return 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))
-      bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
+  FOR_EACH_SHIFT (trans, i)
+    bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));

 
 

-  for (i = 0; i < state->nlookaheads; ++i)
-    bitset_or (lookaheadset, lookaheadset, state->lookaheads[i]);
+  for (i = 0; i < reds->num; ++i)
+    bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);

 
   bitset_and (lookaheadset, lookaheadset, shiftset);
 
 
   bitset_and (lookaheadset, lookaheadset, shiftset);
 


@@ -331,70 +357,50 @@ count_sr_conflicts (state_t *state)
 }
 
 
 }
 
 

-/*----------------------------------------------.
-| Count the number of reduce/reduce conflicts.  |
-`----------------------------------------------*/
+/*----------------------------------------------------------------.
+| Count the number of reduce/reduce conflicts.  If ONE_PER_TOKEN, |
+| count one conflict for each token that has any reduce/reduce    |
+| conflicts.  Otherwise, count one conflict for each pair of      |
+| conflicting reductions.                                         |
++`----------------------------------------------------------------*/

 
 static int
 
 static int

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

 {
   int i;
 {
   int i;

+  reductions *reds = s->reductions;

   int rrc_count = 0;
 
   int rrc_count = 0;
 

-  if (state->nlookaheads < 2)
-    return 0;
-

   for (i = 0; i < ntokens; i++)
     {
       int count = 0;
       int j;
   for (i = 0; i < ntokens; i++)
     {
       int count = 0;
       int j;

-      for (j = 0; j < state->nlookaheads; ++j)
-       if (bitset_test (state->lookaheads[j], i))
+      for (j = 0; j < reds->num; ++j)
+       if (bitset_test (reds->lookaheads[j], i))

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

-       rrc_count++;
+       rrc_count += one_per_token ? 1 : count-1;

     }
 
   return rrc_count;
 }
 
     }
 
   return rrc_count;
 }
 

-/*--------------------------------------------------------------.
-| Return a human readable string which reports shift/reduce and |
-| reduce/reduce conflict numbers (SRC_NUM, RRC_NUM).            |
-`--------------------------------------------------------------*/

 
 

-static const char *
-conflict_report (int src_num, int rrc_num)
-{
-  static char res[4096];
-  char *cp = res;
+/*--------------------------------------------------------.
+| Report the number of conflicts, using the Yacc format.  |
+`--------------------------------------------------------*/

 
 

-  if (src_num >= 1)
-    {
-      sprintf (cp, ngettext ("%d shift/reduce conflict",
-                            "%d shift/reduce conflicts", src_num), src_num);
-      cp += strlen (cp);
-    }
-
-  if (src_num > 0 && rrc_num > 0)
-    {
-      sprintf (cp, " %s ", _("and"));
-      cp += strlen (cp);
-    }
-
-  if (rrc_num >= 1)
-    {
-      sprintf (cp, ngettext ("%d reduce/reduce conflict",
-                            "%d reduce/reduce conflicts", rrc_num), rrc_num);
-      cp += strlen (cp);
-    }
-
-  *cp++ = '.';
-  *cp++ = '\n';
-  *cp++ = '\0';
-
-  return res;
+static void
+conflict_report (FILE *out, int src_num, int rrc_num)
+{
+  if (src_num && rrc_num)
+    fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
+            src_num, rrc_num);
+  else if (src_num)
+    fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
+  else if (rrc_num)
+    fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);

 }
 
 
 }
 
 


@@ -405,18 +411,45 @@ conflict_report (int src_num, int rrc_num)
 void
 conflicts_output (FILE *out)
 {
 void
 conflicts_output (FILE *out)
 {

-  bool printed_sth = FALSE;
-  size_t i;
+  bool printed_sth = false;
+  state_number i;
+  for (i = 0; i < nstates; i++)
+    {
+      state *s = states[i];
+      if (conflicts[i])
+       {
+         fprintf (out, _("State %d "), i);
+         conflict_report (out, count_sr_conflicts (s),
+                          count_rr_conflicts (s, true));
+         printed_sth = true;
+       }
+    }
+  if (printed_sth)
+    fputs ("\n\n", out);
+}
+
+/*--------------------------------------------------------.
+| Total the number of S/R and R/R conflicts.  Unlike the  |
+| code in conflicts_output, however, count EACH pair of   |
+| reductions for the same state and lookahead as one      |
+| conflict.                                              |
+`--------------------------------------------------------*/
+
+int
+conflicts_total_count (void)
+{
+  state_number i;
+  int count;
+
+  /* Conflicts by state.  */
+  count = 0;

   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {

-       fprintf (out, _("State %d contains "), i);
-       fputs (conflict_report (count_sr_conflicts (states[i]),
-                               count_rr_conflicts (states[i])), out);
-       printed_sth = TRUE;
+       count += count_sr_conflicts (states[i]);
+       count += count_rr_conflicts (states[i], false);

       }
       }

-  if (printed_sth)
-    fputs ("\n\n", out);
+  return count;

 }
 
 
 }
 
 


@@ -427,23 +460,25 @@ conflicts_output (FILE *out)
 void
 conflicts_print (void)
 {
 void
 conflicts_print (void)
 {

-  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
      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 = false;

 
   int src_total = 0;
   int rrc_total = 0;
 
   /* Conflicts by state.  */
 
   int src_total = 0;
   int rrc_total = 0;
 
   /* Conflicts by state.  */

-  for (i = 0; i < nstates; i++)
-    if (conflicts[i])
-      {
-       src_total += count_sr_conflicts (states[i]);
-       rrc_total += count_rr_conflicts (states[i]);
-      }
+  {
+    state_number i;
+
+    for (i = 0; i < nstates; i++)
+      if (conflicts[i])
+       {
+         src_total += count_sr_conflicts (states[i]);
+         rrc_total += count_rr_conflicts (states[i], true);
+       }
+  }

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


@@ -453,32 +488,19 @@ conflicts_print (void)
     return;
 
   /* Report the total number of conflicts on STDERR.  */
     return;
 
   /* Report the total number of conflicts on STDERR.  */

-  if (yacc_flag)
-    {
-      /* If invoked with `--yacc', use the output format specified by
-        POSIX.  */
-      fprintf (stderr, _("conflicts: "));
-      if (src_total > 0)
-       fprintf (stderr, _(" %d shift/reduce"), src_total);
-      if (src_total > 0 && rrc_total > 0)
-       fprintf (stderr, ",");
-      if (rrc_total > 0)
-       fprintf (stderr, _(" %d reduce/reduce"), rrc_total);
-      putc ('\n', stderr);
-    }
-  else
-    {
-      fprintf (stderr, _("%s contains "), infile);
-      fputs (conflict_report (src_total, rrc_total), stderr);
-    }
+  if (! yacc_flag)
+    fprintf (stderr, "%s: ", current_file);
+  conflict_report (stderr, src_total, rrc_total);

 
 

-  if (expected_conflicts != -1 && !src_ok)
+  if (expected_conflicts != -1)

     {
     {

-      complain_message_count++;
-      fprintf (stderr, ngettext ("expected %d shift/reduce conflict\n",
-                                "expected %d shift/reduce conflicts\n",
-                                expected_conflicts),
-              expected_conflicts);
+      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"));

     }
 }
 
     }
 }