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,
  57            "  node [fontname = courier, shape = box, colorscheme = paired6]\n"
  58            "  edge [fontname = courier]\n"
  59            "\n");
  60 }
  61
  62 void
  63 output_node (int id, char const *label, FILE *fout)
  64 {
  65   fprintf (fout, "  %d [label=\"%s\"]\n", id, label);
  66 }
  67
  68 void
  69 output_edge (int source, int destination, char const *label,
  70              char const *style, FILE *fout)
  71 {
  72   fprintf (fout, "  %d -> %d [style=%s", source, destination, style);
  73   if (label)
  74     fprintf (fout, " label=%s", quote (label));
  75   fputs ("]\n", fout);
  76 }
  77
  78 char const *
  79 escape (char const *name)
  80 {
  81   char *q = quote (name);
  82   q[strlen (q) - 1] = '\0';
  83   return q + 1;
  84 }
  85
  86 static void
  87 no_reduce_bitset_init (state const *s, bitset *no_reduce_set)
  88 {
  89   int n;
  90   *no_reduce_set = bitset_create (ntokens, BITSET_FIXED);
  91   bitset_zero (*no_reduce_set);
  92   FOR_EACH_SHIFT (s->transitions, n)
  93     bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n));
  94   for (n = 0; n < s->errs->num; ++n)
  95     if (s->errs->symbols[n])
  96       bitset_set (*no_reduce_set, s->errs->symbols[n]->number);
  97 }
  98
  99 static void
 100 conclude_red (struct obstack *out, int source, rule_number ruleno,
 101               bool enabled, bool first, FILE *fout)
 102 {
 103   /* If no lookahead tokens were valid transitions, this reduction is
 104      actually hidden, so cancel everything. */
 105   if (first)
 106     return (void) obstack_finish0 (out);
 107   else
 108     {
 109       char const *ed = enabled ? "" : "d";
 110       char const *color = enabled ? ruleno ? "3" : "1" : "5";
 111
 112       /* First, build the edge's head. The name of reduction nodes is "nRm",
 113          with n the source state and m the rule number. This is because we
 114          don't want all the reductions bearing a same rule number to point to
 115          the same state, since that is not the desired format. */
 116       fprintf (fout, "  %1$d -> \"%1$dR%2$d%3$s\" [",
 117                source, ruleno, ed);
 118
 119       /* (The lookahead tokens have been added to the beginning of the
 120          obstack, in the caller function.) */
 121       if (! obstack_empty_p (out))
 122         {
 123           char *label = obstack_finish0 (out);
 124           fprintf (fout, "label=\"[%s]\", ", label);
 125           obstack_free (out, label);
 126         }
 127
 128       /* Then, the edge's tail. */
 129       fprintf (fout, "style=solid]\n");
 130
 131       /* Build the associated diamond representation of the target rule. */
 132       fprintf (fout, " \"%dR%d%s\" [label=\"",
 133                source, ruleno, ed);
 134       if (ruleno)
 135         fprintf (fout, "R%d", ruleno);
 136       else
 137         fprintf (fout, "Acc");
 138
 139       fprintf (fout, "\", fillcolor=%s, shape=diamond, style=filled]\n",
 140                color);
 141     }
 142 }
 143
 144 static bool
 145 print_token (struct obstack *out, bool first, char const *tok)
 146 {
 147   char const *q = escape (tok);
 148
 149   if (! first)
 150     obstack_sgrow (out, ", ");
 151   obstack_sgrow (out, q);
 152   return false;
 153 }
 154
 155 void
 156 output_red (state const *s, reductions const *reds, FILE *fout)
 157 {
 158   bitset no_reduce_set;
 159   int j;
 160   int source = s->number;
 161
 162   /* Two obstacks are needed: one for the enabled reductions, and one
 163      for the disabled reductions, because in the end we want two
 164      separate edges, even though in most cases only one will actually
 165      be printed. */
 166   struct obstack dout;
 167   struct obstack eout;
 168
 169   no_reduce_bitset_init (s, &no_reduce_set);
 170   obstack_init (&dout);
 171   obstack_init (&eout);
 172
 173   for (j = 0; j < reds->num; ++j)
 174     {
 175       bool defaulted = false;
 176       bool firstd = true;
 177       bool firste = true;
 178       rule_number ruleno = reds->rules[j]->number;
 179       rule *default_reduction = NULL;
 180
 181       if (yydefact[s->number] != 0)
 182         default_reduction = &rules[yydefact[s->number] - 1];
 183
 184       /* Build the lookahead tokens lists, one for enabled transitions and one
 185          for disabled transistions. */
 186       if (default_reduction && default_reduction == reds->rules[j])
 187         defaulted = true;
 188       if (reds->lookahead_tokens)
 189         {
 190           int i;
 191           for (i = 0; i < ntokens; i++)
 192             if (bitset_test (reds->lookahead_tokens[j], i))
 193               {
 194                 if (bitset_test (no_reduce_set, i))
 195                   firstd = print_token (&dout, firstd, symbols[i]->tag);
 196                 else
 197                   {
 198                     if (! defaulted)
 199                       firste = print_token (&eout, firste, symbols[i]->tag);
 200                     bitset_set (no_reduce_set, i);
 201                   }
 202               }
 203         }
 204
 205       /* Do the actual output. */
 206       conclude_red (&dout, source, ruleno, false, firstd, fout);
 207       conclude_red (&eout, source, ruleno, true, firste && !defaulted, fout);
 208     }
 209   obstack_free (&dout, 0);
 210   obstack_free (&eout, 0);
 211   bitset_free (no_reduce_set);
 212 }
 213
 214 void
 215 finish_graph (FILE *fout)
 216 {
 217   fputs ("}\n", fout);
 218 }