src/graphviz.c

   1 /* Output Graphviz specification of a state machine generated by Bison.
   2
   3    Copyright (C) 2006-2007, 2009-2012 Free Software Foundation, Inc.
   4
   5    This file is part of Bison, the GNU Compiler Compiler.
   6
   7    This program is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 /* Written by Paul Eggert and Satya Kiran Popuri.  */
  21
  22 #include <config.h>
  23 #include "system.h"
  24
  25 #include <quotearg.h>
  26
  27 #include "files.h"
  28 #include "gram.h"
  29 #include "graphviz.h"
  30 #include "tables.h"
  31
  32 /* Return an unambiguous printable representation for NAME, suitable
  33    for C strings.  Use slot 2 since the user may use slots 0 and 1.  */
  34
  35 static char *
  36 quote (char const *name)
  37 {
  38   return quotearg_n_style (2, c_quoting_style, name);
  39 }
  40
  41 void
  42 start_graph (FILE *fout)
  43 {
  44   fprintf (fout,
  45            _("// Generated by %s.\n"
  46              "// Report bugs to <%s>.\n"
  47              "// Home page: <%s>.\n"
  48              "\n"),
  49            PACKAGE_STRING,
  50            PACKAGE_BUGREPORT,
  51            PACKAGE_URL);
  52   fprintf (fout,
  53            "digraph %s\n"
  54            "{\n",
  55            quote (grammar_file));
  56   fprintf (fout, "node [shape=box]\n");
  57 }
  58
  59 void
  60 output_node (int id, char const *label, FILE *fout)
  61 {
  62   fprintf (fout, "  %d [label=\"%s\"]\n", id, label);
  63 }
  64
  65 void
  66 output_edge (int source, int destination, char const *label,
  67              char const *style, FILE *fout)
  68 {
  69   fprintf (fout, "  %d -> %d [style=%s", source, destination, style);
  70   if (label)
  71     fprintf (fout, " label=%s", quote (label));
  72   fputs ("]\n", fout);
  73 }
  74
  75 char const *
  76 escape (char const *name)
  77 {
  78   char *q = quote (name);
  79   q[strlen (q) - 1] = '\0';
  80   return q + 1;
  81 }
  82
  83 static void
  84 no_reduce_bitset_init (state const *s, bitset *no_reduce_set)
  85 {
  86   int n;
  87   *no_reduce_set = bitset_create (ntokens, BITSET_FIXED);
  88   bitset_zero (*no_reduce_set);
  89   FOR_EACH_SHIFT (s->transitions, n)
  90     bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n));
  91   for (n = 0; n < s->errs->num; ++n)
  92     if (s->errs->symbols[n])
  93       bitset_set (*no_reduce_set, s->errs->symbols[n]->number);
  94 }
  95
  96 static bool
  97 print_token (struct obstack *out, bool first, char const *tok)
  98 {
  99   char const *q = escape (tok);
 100
 101   if (! first)
 102     obstack_sgrow (out, ",");
 103   obstack_sgrow (out, q);
 104   return false;
 105 }
 106
 107 void
 108 output_red (state const *s, reductions const *reds, FILE *fout)
 109 {
 110   bitset no_reduce_set;
 111   int j;
 112   int source = s->number;
 113   struct obstack oout;
 114
 115   no_reduce_bitset_init (s, &no_reduce_set);
 116   obstack_init (&oout);
 117
 118   for (j = 0; j < reds->num; ++j)
 119     {
 120       bool disabled = false;
 121       bool first = true;
 122       int ruleno = reds->rules[j]->user_number;
 123       rule *default_reduction = NULL;
 124
 125       if (yydefact[s->number] != 0)
 126         default_reduction = &rules[yydefact[s->number] - 1];
 127
 128       /* First, print the edges that represent each possible reduction for
 129          the given state. */
 130       obstack_printf (&oout, "  %1$d -> \"%1$dR%2$d\" [label=\"",
 131                       source, ruleno);
 132       if (default_reduction && default_reduction == reds->rules[j])
 133         first = print_token (&oout, true, "$default");
 134       else
 135         {
 136           int i;
 137           for (i = 0; i < ntokens; i++)
 138             if (bitset_test (reds->lookahead_tokens[j], i))
 139               {
 140                 first = print_token (&oout, first, symbols[i]->tag);
 141                 if (bitset_test (no_reduce_set, i))
 142                   disabled = true;
 143               }
 144         }
 145       obstack_sgrow (&oout, "\" style=solid]\n");
 146
 147       /* Then, print the reduction's representation. Done later since
 148          we need to know whether this reduction is disabled. */
 149       obstack_printf (&oout,
 150                       " \"%dR%d\" "
 151                       "[style=filled shape=diamond fillcolor=%s "
 152                       "label=\"R%d\"]\n",
 153                       source, ruleno,
 154                       disabled ? "firebrick1" : "yellowgreen",
 155                       ruleno);
 156
 157       /* If no lookahead tokens were valid transitions, this reduction is
 158          actually disabled, so don't print it. */
 159       if (first)
 160         (void) obstack_finish0 (&oout);
 161       else
 162         fprintf (fout, obstack_finish0 (&oout));
 163     }
 164   obstack_free (&oout, 0);
 165 }
 166
 167 void
 168 finish_graph (FILE *fout)
 169 {
 170   fputs ("}\n", fout);
 171 }