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   int source = s->number;
 111   int i, j;
 112   bitset no_reduce_set;
 113   no_reduce_bitset_init (s, &no_reduce_set);
 114
 115   struct obstack oout;
 116   obstack_init (&oout);
 117
 118   for (j = 0; j < reds->num; ++j)
 119     {
 120       bool first = true;
 121       bool disabled = false;
 122       int ruleno = reds->rules[j]->user_number;
 123       rule *default_reduction = NULL;
 124       if (yydefact[s->number] != 0)
 125         default_reduction = &rules[yydefact[s->number] - 1];
 126
 127       /* First, print the edges that represent each possible reduction for
 128          the given state. */
 129       obstack_printf (&oout, "  %1$d -> \"%1$dR%2$d\" [label=\"",
 130                       source, ruleno);
 131       if (default_reduction && default_reduction == reds->rules[j])
 132         first = print_token (&oout, true, "$default");
 133       else
 134         for (i = 0; i < ntokens; i++)
 135             if (bitset_test (reds->lookahead_tokens[j], i))
 136               {
 137                 first = print_token (&oout, first, symbols[i]->tag);
 138                 if (bitset_test (no_reduce_set, i))
 139                   disabled = true;
 140               }
 141       obstack_sgrow (&oout, "\" style=solid]\n");
 142
 143       /* Then, print the reduction's representation. This most be done later
 144          because the we need the previously determined boolean to know if this
 145          reduction is disabled or not. */
 146       obstack_printf (&oout, " \"%dR%d\" "
 147                              "[style=filled shape=diamond fillcolor=%s "
 148                              "label=\"R%d\"]\n",
 149                       source, ruleno,
 150                       disabled ? "firebrick1" : "yellowgreen",
 151                       ruleno);
 152
 153       /* If no lookahead tokens were valid transitions, this reduction is
 154          actually disabled, so don't print it. */
 155       if (first)
 156         (void) obstack_finish0 (&oout);
 157       else
 158         fprintf (fout, obstack_finish0 (&oout));
 159     }
 160   obstack_free (&oout, 0);
 161 }
 162
 163 void
 164 finish_graph (FILE *fout)
 165 {
 166   fputs ("}\n", fout);
 167 }