Use bitset operations when possible, not loops over bits.

[bison.git] / src / print.c

diff --git a/src/print.c b/src/print.c
index d676f7f3b226722dda83f4d4a61ee547917861b6..6dd25096a0037978334ccdcb949f591cf5a88e9d 100644 (file)
--- a/src/print.c
+++ b/src/print.c
@@ -1,5 +1,5 @@
 /* Print information on generated parser, for bison,
 /* Print information on generated parser, 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.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 


@@ -20,7 +20,9 @@
 
 
 #include "system.h"
 
 
 #include "system.h"

+#include "quotearg.h"

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

+#include "symtab.h"

 #include "gram.h"
 #include "LR0.h"
 #include "lalr.h"
 #include "gram.h"
 #include "LR0.h"
 #include "lalr.h"


@@ -30,6 +32,11 @@
 #include "reader.h"
 #include "print.h"
 #include "reduce.h"
 #include "reader.h"
 #include "print.h"
 #include "reduce.h"

+#include "closure.h"
+#include "bitset.h"
+
+static bitset shiftset;
+static bitset lookaheadset;

 
 #if 0
 static void
 
 #if 0
 static void


@@ -39,168 +46,297 @@ print_token (int extnum, int token)
 }
 #endif
 
 }
 #endif
 

+static inline const char *
+escape (const char *s)
+{
+  return quotearg_n_style (1, escape_quoting_style, s);
+}
+
+/* Be cautious not to use twice the same slot in a single expression. */
+static inline const char *
+escape2 (const char *s)
+{
+  return quotearg_n_style (2, escape_quoting_style, s);
+}
+

 \f
 /*--------------------------------.
 | Report information on a state.  |
 `--------------------------------*/
 
 static void
 \f
 /*--------------------------------.
 | Report information on a state.  |
 `--------------------------------*/
 
 static void

-print_core (FILE *out, int state)
+print_core (FILE *out, state_t *state)

 {
   int i;
 {
   int i;

-  int k;
-  int rule;
-  core *statep;
-  short *sp;
-  short *sp1;
+  short *sitems = state->items;
+  int snitems   = state->nitems;

 
 

-  statep = state_table[state].state;
-  k = statep->nitems;
-
-  if (k == 0)
-    return;
+  /* New experimental feature: if TRACE_FLAGS output all the items of
+     a state, not only its kernel.  */
+  if (trace_flag)
+    {
+      closure (sitems, snitems);
+      sitems = itemset;
+      snitems = nitemset;
+    }

 
 

-  for (i = 0; i < k; i++)
+  if (snitems)

     {
     {

-      sp1 = sp = ritem + statep->items[i];
+      for (i = 0; i < snitems; i++)
+       {
+         short *sp;
+         short *sp1;
+         int rule;

 
 

-      while (*sp > 0)
-       sp++;
+         sp1 = sp = ritem + sitems[i];

 
 

-      rule = -(*sp);
-      fprintf (out, "    %s  ->  ", tags[rlhs[rule]]);
+         while (*sp >= 0)
+           sp++;

 
 

-      for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
-       {
-         fprintf (out, "%s ", tags[*sp]);
-       }
+         rule = -(*sp);
+         fprintf (out, "    %s  ->  ", escape (symbols[rules[rule].lhs]->tag));

 
 

-      fputc ('.', out);
+         for (sp = ritem + rules[rule].rhs; sp < sp1; sp++)
+           fprintf (out, "%s ", escape (symbols[*sp]->tag));

 
 

-      while (*sp > 0)
-       {
-         fprintf (out, " %s", tags[*sp]);
-         sp++;
+         fputc ('.', out);
+
+         for (/* Nothing */; *sp >= 0; ++sp)
+           fprintf (out, " %s", escape (symbols[*sp]->tag));
+
+         fprintf (out, _("   (rule %d)"), rule - 1);
+         fputc ('\n', out);

        }
 
        }
 

-      fprintf (out, _("   (rule %d)"), rule);

       fputc ('\n', out);
     }
       fputc ('\n', out);
     }

+}
+
+
+static void
+print_shifts (FILE *out, state_t *state)
+{
+  int i;
+  shifts *shiftp = state->shifts;

 
 

-  fputc ('\n', out);
+  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
+    if (!SHIFT_IS_DISABLED (shiftp, i))
+      {
+       int state1 = shiftp->shifts[i];
+       int symbol = states[state1]->accessing_symbol;
+       fprintf (out,
+                _("    %-4s\tshift, and go to state %d\n"),
+                escape (symbols[symbol]->tag), state1);
+      }
+
+  if (i > 0)
+    fputc ('\n', out);

 }
 
 }
 

+

 static void
 static void

-print_actions (FILE *out, int state)
+print_errs (FILE *out, state_t *state)

 {
 {

+  errs *errp = state->errs;

   int i;
   int i;

-  int k;
-  int state1;
-  int symbol;
-  shifts *shiftp;
-  errs *errp;
-  reductions *redp;
-  int rule;
-
-  shiftp = state_table[state].shift_table;
-  redp = state_table[state].reduction_table;
-  errp = err_table[state];
-
-  if (!shiftp && !redp)
-    {
-      if (final_state == state)
-       fprintf (out, _("    $default\taccept\n"));
-      else
-       fprintf (out, _("    NO ACTIONS\n"));
-      return;
-    }

 
 

-  if (shiftp)
-    {
-      k = shiftp->nshifts;
+  for (i = 0; i < errp->nerrs; ++i)
+    if (errp->errs[i])
+      fprintf (out, _("    %-4s\terror (nonassociative)\n"),
+              escape (symbols[errp->errs[i]]->tag));

 
 

-      for (i = 0; i < k; i++)
-       {
-         if (!shiftp->shifts[i])
-           continue;
-         state1 = shiftp->shifts[i];
-         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);
+}

 
 

-      if (i > 0)
-       fputc ('\n', out);
-    }
-  else
+
+static void
+print_gotos (FILE *out, state_t *state)
+{
+  int i;
+  shifts *shiftp = state->shifts;
+
+  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
+    /* Skip token shifts.  */;
+
+  if (i < shiftp->nshifts)

     {
     {

-      i = 0;
-      k = 0;
+      for (; i < shiftp->nshifts; i++)
+       if (!SHIFT_IS_DISABLED (shiftp, i))
+         {
+           int state1 = shiftp->shifts[i];
+           int symbol = states[state1]->accessing_symbol;
+           fprintf (out, _("    %-4s\tgo to state %d\n"),
+                    escape (symbols[symbol]->tag), state1);
+         }
+
+      fputc ('\n', out);

     }
     }

+}

 
 

-  if (errp)
+static void
+print_reductions (FILE *out, state_t *state)
+{
+  int i;
+  shifts *shiftp = state->shifts;
+  reductions *redp = state->reductions;
+  errs *errp = state->errs;
+  int nodefault = 0;
+
+  if (redp->nreds == 0)
+    return;
+
+  if (state->consistent)

     {
     {

-      int j, nerrs;
+      int rule = redp->rules[0];
+      int symbol = rules[rule].lhs;
+      fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
+              rule - 1, escape (symbols[symbol]->tag));
+      return;
+    }

 
 

-      nerrs = errp->nerrs;
+  bitset_zero (shiftset);

 
 

-      for (j = 0; j < nerrs; j++)
-       {
-         if (!errp->errs[j])
-           continue;
-         symbol = errp->errs[j];
-         fprintf (out, _("    %-4s\terror (nonassociative)\n"),
-                  tags[symbol]);
-       }
+  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;
+       bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
+      }

 
 

-      if (j > 0)
-       fputc ('\n', out);
-    }
+  for (i = 0; i < errp->nerrs; i++)
+    if (errp->errs[i])
+      bitset_set (shiftset, errp->errs[i]);

 
 

-  if (state_table[state].consistent && redp)
+  if (state->nlookaheads == 1 && !nodefault)

     {
     {

-      rule = redp->rules[0];
-      symbol = rlhs[rule];
+      int default_rule = LAruleno[state->lookaheadsp];
+
+      bitset_and (lookaheadset, LA[state->lookaheadsp], shiftset);
+
+      for (i = 0; i < ntokens; i++)
+       if (bitset_test (lookaheadset, i))
+         fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
+                  escape (symbols[i]->tag), default_rule - 1,
+                  escape2 (symbols[rules[default_rule].lhs]->tag));
+

       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),

-              rule, tags[symbol]);
+              default_rule - 1, escape (symbols[rules[default_rule].lhs]->tag));

     }
     }

-  else if (redp)
+  else if (state->nlookaheads >= 1)

     {
     {

-      print_reductions (out, state);
-    }
+      int cmax = 0;
+      int default_LA = -1;
+      int default_rule = 0;

 
 

-  if (i < k)
-    {
-      for (; i < k; i++)
+      if (!nodefault)
+       for (i = 0; i < state->nlookaheads; ++i)
+         {
+           int count = 0;
+           int j;
+
+           bitset_andn (lookaheadset, LA[state->lookaheadsp + i], shiftset);
+
+           for (j = 0; j < ntokens; j++)
+             if (bitset_test (lookaheadset, j))
+               count++;
+
+           if (count > cmax)
+             {
+               cmax = count;
+               default_LA = state->lookaheadsp + i;
+               default_rule = LAruleno[state->lookaheadsp + i];
+             }
+
+           bitset_or (shiftset, shiftset, 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 (i = 0; i < ntokens; i++)

        {
        {

-         if (!shiftp->shifts[i])
-           continue;
-         state1 = shiftp->shifts[i];
-         symbol = state_table[state1].accessing_symbol;
-         fprintf (out, _("    %-4s\tgo to state %d\n"),
-                  tags[symbol], state1);
+         int j;
+         int defaulted = 0;
+         int count = bitset_test (shiftset, i);
+
+         for (j = 0; j < state->nlookaheads; ++j)
+           if (bitset_test (LA[state->lookaheadsp + j], i))
+             {
+               if (count == 0)
+                 {
+                   if (state->lookaheadsp + j != default_LA)
+                     fprintf (out,
+                              _("    %-4s\treduce using rule %d (%s)\n"),
+                              escape (symbols[i]->tag),
+                              LAruleno[state->lookaheadsp + j] - 1,
+                              escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
+                   else
+                     defaulted = 1;
+
+                   count++;
+                 }
+               else
+                 {
+                   if (defaulted)
+                     fprintf (out,
+                              _("    %-4s\treduce using rule %d (%s)\n"),
+                              escape (symbols[i]->tag),
+                              LAruleno[default_LA] - 1,
+                              escape2 (symbols[rules[LAruleno[default_LA]].lhs]->tag));
+                   defaulted = 0;
+                   fprintf (out,
+                            _("    %-4s\t[reduce using rule %d (%s)]\n"),
+                            escape (symbols[i]->tag),
+                            LAruleno[state->lookaheadsp + j] - 1,
+                            escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
+                 }
+             }

        }
 
        }
 

-      fputc ('\n', out);
+      if (default_LA >= 0)
+       fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
+                default_rule - 1,
+                escape (symbols[rules[default_rule].lhs]->tag));

     }
 }
 
     }
 }
 

+

 static void
 static void

-print_state (FILE *out, int state)
+print_actions (FILE *out, state_t *state)

 {
 {

-  fputs ("\n\n", out);
-  fprintf (out, _("state %d"), state);
+  reductions *redp = state->reductions;
+  shifts *shiftp = state->shifts;
+
+  if (shiftp->nshifts == 0 && redp->nreds == 0)
+    {
+      if (final_state == state->number)
+       fprintf (out, _("    $default\taccept\n"));
+      else
+       fprintf (out, _("    NO ACTIONS\n"));
+      return;
+    }
+
+  print_shifts (out, state);
+  print_errs (out, state);
+  print_reductions (out, state);
+  print_gotos (out, state);
+}
+
+static void
+print_state (FILE *out, state_t *state)
+{
+  fprintf (out, _("state %d"), state->number);

   fputs ("\n\n", out);
   print_core (out, state);
   print_actions (out, state);
   fputs ("\n\n", out);
   print_core (out, state);
   print_actions (out, state);

+  fputs ("\n\n", out);

 }
 \f
 /*-----------------------------------------.
 }
 \f
 /*-----------------------------------------.


@@ -227,56 +363,59 @@ print_grammar (FILE *out)
   int column = 0;
 
   /* rule # : LHS -> RHS */
   int column = 0;
 
   /* rule # : LHS -> RHS */

-  fprintf (out, "\n%s\n\n", _("Grammar"));
+  fprintf (out, "%s\n\n", _("Grammar"));
+  fprintf (out, "  %s\n", _("Number, Line, Rule"));

   for (i = 1; i <= nrules; i++)
     /* Don't print rules disabled in reduce_grammar_tables.  */
   for (i = 1; i <= nrules; i++)
     /* Don't print rules disabled in reduce_grammar_tables.  */

-    if (rlhs[i] >= 0)
+    if (rules[i].useful)

       {
       {

-       fprintf (out, _("rule %-4d %s ->"), i, tags[rlhs[i]]);
-       rule = &ritem[rrhs[i]];
-       if (*rule > 0)
-         while (*rule > 0)
-           fprintf (out, " %s", tags[*rule++]);
+       fprintf (out, _("  %3d %3d %s ->"),
+                i - 1, rules[i].line, escape (symbols[rules[i].lhs]->tag));
+       rule = &ritem[rules[i].rhs];
+       if (*rule >= 0)
+         while (*rule >= 0)
+           fprintf (out, " %s", escape (symbols[*rule++]->tag));

        else
        else

-         fprintf (out, "               /* %s */", _("empty"));
+         fprintf (out, " /* %s */", _("empty"));

        fputc ('\n', out);
       }
        fputc ('\n', out);
       }

+  fputs ("\n\n", out);

 
 

-  /* TERMINAL (type #) : rule #s terminal is on RHS */
-  fprintf (out, "\n%s\n\n", _("Terminals, with rules where they appear"));
-  fprintf (out, "%s (-1)\n", tags[0]);

 
 

+  /* TERMINAL (type #) : rule #s terminal is on RHS */
+  fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));

   for (i = 0; i <= max_user_token_number; i++)
     if (token_translations[i] != 2)
       {
        buffer[0] = 0;
   for (i = 0; i <= max_user_token_number; i++)
     if (token_translations[i] != 2)
       {
        buffer[0] = 0;

-       column = strlen (tags[token_translations[i]]);
-       fputs (tags[token_translations[i]], out);
+       column = strlen (escape (symbols[token_translations[i]]->tag));
+       fputs (escape (symbols[token_translations[i]]->tag), out);

        END_TEST (50);
        sprintf (buffer, " (%d)", i);
 
        for (j = 1; j <= nrules; j++)
        END_TEST (50);
        sprintf (buffer, " (%d)", i);
 
        for (j = 1; j <= nrules; j++)

-         for (rule = &ritem[rrhs[j]]; *rule > 0; rule++)
+         for (rule = &ritem[rules[j].rhs]; *rule >= 0; rule++)

            if (*rule == token_translations[i])
              {
                END_TEST (65);
            if (*rule == token_translations[i])
              {
                END_TEST (65);

-               sprintf (buffer + strlen (buffer), " %d", j);
+               sprintf (buffer + strlen (buffer), " %d", j - 1);

                break;
              }
        fprintf (out, "%s\n", buffer);
       }
                break;
              }
        fprintf (out, "%s\n", buffer);
       }

+  fputs ("\n\n", out);

 
 

-  fprintf (out, "\n%s\n\n",
-          _("Nonterminals, with rules where they appear"));
+
+  fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));

   for (i = ntokens; i <= nsyms - 1; i++)
     {
       int left_count = 0, right_count = 0;
 
       for (j = 1; j <= nrules; j++)
        {
   for (i = ntokens; i <= nsyms - 1; i++)
     {
       int left_count = 0, right_count = 0;
 
       for (j = 1; j <= nrules; j++)
        {

-         if (rlhs[j] == i)
+         if (rules[j].lhs == i)

            left_count++;
            left_count++;

-         for (rule = &ritem[rrhs[j]]; *rule > 0; rule++)
+         for (rule = &ritem[rules[j].rhs]; *rule >= 0; rule++)

            if (*rule == i)
              {
                right_count++;
            if (*rule == i)
              {
                right_count++;


@@ -285,8 +424,8 @@ print_grammar (FILE *out)
        }
 
       buffer[0] = 0;
        }
 
       buffer[0] = 0;

-      fputs (tags[i], out);
-      column = strlen (tags[i]);
+      fputs (escape (symbols[i]->tag), out);
+      column = strlen (escape (symbols[i]->tag));

       sprintf (buffer, " (%d)", i);
       END_TEST (0);
 
       sprintf (buffer, " (%d)", i);
       END_TEST (0);
 


@@ -298,8 +437,8 @@ print_grammar (FILE *out)
          for (j = 1; j <= nrules; j++)
            {
              END_TEST (65);
          for (j = 1; j <= nrules; j++)
            {
              END_TEST (65);

-             if (rlhs[j] == i)
-               sprintf (buffer + strlen (buffer), " %d", j);
+             if (rules[j].lhs == i)
+               sprintf (buffer + strlen (buffer), " %d", j - 1);

            }
        }
 
            }
        }
 


@@ -311,42 +450,57 @@ print_grammar (FILE *out)
          sprintf (buffer + strlen (buffer), _(" on right:"));
          for (j = 1; j <= nrules; j++)
            {
          sprintf (buffer + strlen (buffer), _(" on right:"));
          for (j = 1; j <= nrules; j++)
            {

-             for (rule = &ritem[rrhs[j]]; *rule > 0; rule++)
+             for (rule = &ritem[rules[j].rhs]; *rule >= 0; rule++)

                if (*rule == i)
                  {
                    END_TEST (65);
                if (*rule == i)
                  {
                    END_TEST (65);

-                   sprintf (buffer + strlen (buffer), " %d", j);
+                   sprintf (buffer + strlen (buffer), " %d", j - 1);

                    break;
                  }
            }
        }
       fprintf (out, "%s\n", buffer);
     }
                    break;
                  }
            }
        }
       fprintf (out, "%s\n", buffer);
     }

+  fputs ("\n\n", out);

 }
 \f
 void
 print_results (void)
 {
 }
 \f
 void
 print_results (void)
 {

-  if (verbose_flag)
-    {
-      int i;
+  size_t i;

 
 

-      /* We used to use just .out if spec_name_prefix (-p) was used, but
-        that conflicts with Posix.  */
-      FILE *out = xfopen (spec_verbose_file, "w");
+  /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
+     that conflicts with Posix.  */
+  FILE *out = xfopen (spec_verbose_file, "w");

 
 

-      size_t size = obstack_object_size (&output_obstack);
-      fwrite (obstack_finish (&output_obstack), 1, size, out);
-
-      reduce_output (out);
-      conflicts_output (out);
-
-      print_grammar (out);
-
-      for (i = 0; i < nstates; i++)
-       print_state (out, i);
-
-      xfclose (out);
-    }
+  size_t size = obstack_object_size (&output_obstack);
+  fwrite (obstack_finish (&output_obstack), 1, size, out);

   obstack_free (&output_obstack, NULL);
   obstack_free (&output_obstack, NULL);

+
+  if (size)
+    fputs ("\n\n", out);
+
+  reduce_output (out);
+  conflicts_output (out);
+
+  print_grammar (out);
+
+  /* New experimental feature: output all the items of a state, not
+     only its kernel.  Requires to run closure, which need memory
+     allocation/deallocation.  */
+  if (trace_flag)
+    new_closure (nritems);
+  /* Storage for print_reductions.  */
+  shiftset =  bitset_create (ntokens, BITSET_FIXED);
+  bitset_zero (shiftset);
+  lookaheadset = bitset_create (ntokens, BITSET_FIXED);
+  bitset_zero (lookaheadset);
+  for (i = 0; i < nstates; i++)
+    print_state (out, states[i]);
+  bitset_free (shiftset);
+  bitset_free (lookaheadset);
+  if (trace_flag)
+    free_closure ();
+
+  xfclose (out);

 }
 }