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 f578ee09fe66be0346ce01998ba38edde1a54ef6..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 (C) 1984, 1986, 1989, 2000 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,8 +20,9 @@
 
 
 #include "system.h"
 
 
 #include "system.h"

-#include "xalloc.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,191 +31,331 @@
 #include "state.h"
 #include "reader.h"
 #include "print.h"
 #include "state.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
 print_token (int extnum, int token)
 {
 
 #if 0
 static void
 print_token (int extnum, int token)
 {

-  fprintf (foutput, _(" type %d is %s\n"), extnum, tags[token]);
+  fprintf (out, _(" type %d is %s\n"), extnum, tags[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
 \f

-/*================================\
+/*--------------------------------.

 | Report information on a state.  |
 | Report information on a state.  |

-\================================*/
+`--------------------------------*/

 
 static void
 
 static void

-print_core (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];
-  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 (foutput, "    %s  ->  ", tags[rlhs[rule]]);
+         while (*sp >= 0)
+           sp++;

 
 

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

 
 

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

 
 

-      while (*sp > 0)
-       {
-         fprintf (foutput, " %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 (foutput, _("   (rule %d)"), rule);
-      putc ('\n', foutput);
+      fputc ('\n', out);

     }
     }

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

 
 

-  putc ('\n', foutput);
+  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 (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 = shift_table[state];
-  redp = reduction_table[state];
-  errp = err_table[state];
-
-  if (!shiftp && !redp)
+
+  for (i = 0; i < errp->nerrs; ++i)
+    if (errp->errs[i])
+      fprintf (out, _("    %-4s\terror (nonassociative)\n"),
+              escape (symbols[errp->errs[i]]->tag));
+
+  if (i > 0)
+    fputc ('\n', out);
+}
+
+
+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)

     {
     {

-      if (final_state == state)
-       fprintf (foutput, _("    $default\taccept\n"));
-      else
-       fprintf (foutput, _("    NO ACTIONS\n"));
+      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);
+    }
+}
+
+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 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;
     }
 
       return;
     }
 

-  if (shiftp)
+  bitset_zero (shiftset);
+
+  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));
+      }
+
+  for (i = 0; i < errp->nerrs; i++)
+    if (errp->errs[i])
+      bitset_set (shiftset, errp->errs[i]);
+
+  if (state->nlookaheads == 1 && !nodefault)

     {
     {

-      k = shiftp->nshifts;
+      int default_rule = LAruleno[state->lookaheadsp];

 
 

-      for (i = 0; i < k; i++)
-       {
-         if (!shiftp->shifts[i])
-           continue;
-         state1 = shiftp->shifts[i];
-         symbol = accessing_symbol[state1];
-         /* The following line used to be turned off.  */
-         if (ISVAR (symbol))
-           break;
-         if (symbol == 0)      /* I.e. strcmp(tags[symbol],"$")==0 */
-           fprintf (foutput, _("    $   \tgo to state %d\n"), state1);
-         else
-           fprintf (foutput, _("    %-4s\tshift, and go to state %d\n"),
-                    tags[symbol], state1);
-       }
+      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));

 
 

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

     }
     }

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

     {
     {

-      i = 0;
-      k = 0;
-    }
+      int cmax = 0;
+      int default_LA = -1;
+      int default_rule = 0;

 
 

-  if (errp)
-    {
-      int j, nerrs;
+      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);
+         }

 
 

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

 
 

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

        }
 
        }
 

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

     }
     }

+}

 
 

-  if (consistent[state] && redp)
-    {
-      rule = redp->rules[0];
-      symbol = rlhs[rule];
-      fprintf (foutput, _("    $default\treduce using rule %d (%s)\n\n"),
-              rule, tags[symbol]);
-    }
-  else if (redp)
-    {
-      print_reductions (state);
-    }

 
 

-  if (i < k)
-    {
-      for (; i < k; i++)
-       {
-         if (!shiftp->shifts[i])
-           continue;
-         state1 = shiftp->shifts[i];
-         symbol = accessing_symbol[state1];
-         fprintf (foutput, _("    %-4s\tgo to state %d\n"), tags[symbol],
-                  state1);
-       }
+static void
+print_actions (FILE *out, state_t *state)
+{
+  reductions *redp = state->reductions;
+  shifts *shiftp = state->shifts;

 
 

-      putc ('\n', foutput);
+  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
 }
 
 static void

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

 {
 {

-  fprintf (foutput, _("\n\nstate %d\n\n"), state);
-  print_core (state);
-  print_actions (state);
+  fprintf (out, _("state %d"), state->number);
+  fputs ("\n\n", out);
+  print_core (out, state);
+  print_actions (out, state);
+  fputs ("\n\n", out);

 }
 \f
 /*-----------------------------------------.
 | Print information on the whole grammar.  |
 `-----------------------------------------*/
 
 }
 \f
 /*-----------------------------------------.
 | Print information on the whole grammar.  |
 `-----------------------------------------*/
 

-#define END_TEST(end)                          \
-  do {                                         \
-    if (column + strlen(buffer) > (end)) {     \
-      fprintf (foutput, "%s\n   ", buffer);    \
+#define END_TEST(End)                          \
+do {                                           \
+  if (column + strlen(buffer) > (End))         \
+    {                                          \
+      fprintf (out, "%s\n   ", buffer);                \

       column = 3;                              \
       buffer[0] = 0;                           \
     }                                          \
       column = 3;                              \
       buffer[0] = 0;                           \
     }                                          \

-  } while (0)
+} while (0)

 
 
 static void
 
 
 static void

-print_grammar (void)
+print_grammar (FILE *out)

 {
   int i, j;
   short *rule;
 {
   int i, j;
   short *rule;


@@ -222,80 +363,59 @@ print_grammar (void)
   int column = 0;
 
   /* rule # : LHS -> RHS */
   int column = 0;
 
   /* rule # : LHS -> RHS */

-  fputs (_("\nGrammar\n"), foutput);
+  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 (foutput, _("rule %-4d %s ->"), i, tags[rlhs[i]]);
-       rule = &ritem[rrhs[i]];
-       if (*rule > 0)
-         while (*rule > 0)
-           fprintf (foutput, " %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

-         fputs (_("            /* empty */"), foutput);
-       putc ('\n', foutput);
+         fprintf (out, " /* %s */", _("empty"));
+       fputc ('\n', out);

       }
       }

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

 
 

-  /* TERMINAL (type #) : rule #s terminal is on RHS */
-  fputs (_("\nTerminals, with rules where they appear\n\n"), foutput);
-  fprintf (foutput, "%s (-1)\n", tags[0]);
-  if (translations)
-    {
-      for (i = 0; i <= max_user_token_number; i++)
-       if (token_translations[i] != 2)
-         {
-           buffer[0] = 0;
-           column = strlen (tags[token_translations[i]]);
-           fprintf (foutput, "%s", tags[token_translations[i]]);
-           END_TEST (50);
-           sprintf (buffer, " (%d)", i);

 
 

-           for (j = 1; j <= nrules; j++)
-             {
-               for (rule = &ritem[rrhs[j]]; *rule > 0; rule++)
-                 if (*rule == token_translations[i])
-                   {
-                     END_TEST (65);
-                     sprintf (buffer + strlen (buffer), " %d", j);
-                     break;
-                   }
-             }
-           fprintf (foutput, "%s\n", buffer);
-         }
-    }
-  else
-    for (i = 1; i < ntokens; i++)
+  /* 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;
       {
        buffer[0] = 0;

-       column = strlen (tags[i]);
-       fprintf (foutput, "%s", tags[i]);
+       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++)
-             if (*rule == i)
-               {
-                 END_TEST (65);
-                 sprintf (buffer + strlen (buffer), " %d", j);
-                 break;
-               }
-         }
-       fprintf (foutput, "%s\n", buffer);
+         for (rule = &ritem[rules[j].rhs]; *rule >= 0; rule++)
+           if (*rule == token_translations[i])
+             {
+               END_TEST (65);
+               sprintf (buffer + strlen (buffer), " %d", j - 1);
+               break;
+             }
+       fprintf (out, "%s\n", buffer);

       }
       }

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

 
 

-  fputs (_("\nNonterminals, with rules where they appear\n\n"), foutput);
+  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++;


@@ -304,8 +424,8 @@ print_grammar (void)
        }
 
       buffer[0] = 0;
        }
 
       buffer[0] = 0;

-      fprintf (foutput, "%s", tags[i]);
-      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);
 


@@ -317,8 +437,8 @@ print_grammar (void)
          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);

            }
        }
 
            }
        }
 


@@ -330,31 +450,57 @@ print_grammar (void)
          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;
                  }
            }
        }
                    break;
                  }
            }
        }

-      fprintf (foutput, "%s\n", buffer);
+      fprintf (out, "%s\n", buffer);

     }
     }

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

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

-  int i;
-
-  if (any_conflicts)
-    print_conflicts ();
-
-  if (verboseflag)
-    print_grammar ();
-
-  if (verboseflag)
-    for (i = 0; i < nstates; i++)
-      print_state (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");
+
+  size_t size = obstack_object_size (&output_obstack);
+  fwrite (obstack_finish (&output_obstack), 1, size, out);
+  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);

 }
 }