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 void
  97 conclude_red (struct obstack *out, int source, int ruleno, bool enabled,
  98               bool first, FILE *fout)
  99 {
 100   /* If no lookahead tokens were valid transitions, this reduction is
 101      actually hidden, so cancel everything. */
 102   if (first)
 103     return (void) obstack_finish0 (out);
 104   else
 105     {
 106       char const *ed = enabled ? "e" : "d";
 107
 108       /* First, build the edge's head. */
 109       if (! first)
 110         fprintf (fout, "  %1$d -> \"%1$dR%2$d%3$s\" [label = \"",
 111                  source, ruleno, ed);
 112
 113       /* (The lookahead tokens have been added to the beginning of the
 114          obstack, in the caller function.) */
 115
 116       /* Then, the edge's tail. */
 117       obstack_sgrow (out, "\" style = solid]\n");
 118
 119       /* Build the associated diamond representation or the target rule. */
 120       obstack_printf (out, " \"%dR%d%s\" "
 121                            "[style = filled shape = diamond fillcolor = %s "
 122                            "label = \"R%d\"]\n",
 123                       source, ruleno, ed,
 124                       enabled ? "yellowgreen" : "firebrick1",
 125                       ruleno);
 126       fprintf (fout, obstack_finish0 (out));
 127     }
 128 }
 129
 130 static bool
 131 print_token (struct obstack *out, bool first, char const *tok)
 132 {
 133   char const *q = escape (tok);
 134
 135   if (! first)
 136     obstack_sgrow (out, ",");
 137   obstack_sgrow (out, q);
 138   return false;
 139 }
 140
 141 void
 142 output_red (state const *s, reductions const *reds, FILE *fout)
 143 {
 144   bitset no_reduce_set;
 145   int j;
 146   int source = s->number;
 147   struct obstack dout, eout;
 148
 149   no_reduce_bitset_init (s, &no_reduce_set);
 150   obstack_init (&dout);
 151   obstack_init (&eout);
 152
 153   for (j = 0; j < reds->num; ++j)
 154     {
 155       bool defaulted = false;
 156       bool firstd = true, firste = true; // first{en,dis}abled
 157       int ruleno = reds->rules[j]->user_number;
 158       rule *default_reduction = NULL;
 159
 160       if (yydefact[s->number] != 0)
 161         default_reduction = &rules[yydefact[s->number] - 1];
 162
 163       /* Build the lookahead tokens lists, one for enabled transitions and one
 164          for disabled transistions. */
 165       if (default_reduction && default_reduction == reds->rules[j])
 166         {
 167           firste = print_token (&eout, true, "$default");
 168           defaulted = true;
 169         }
 170       if (reds->lookahead_tokens)
 171         {
 172           int i;
 173           for (i = 0; i < ntokens; i++)
 174             if (bitset_test (reds->lookahead_tokens[j], i))
 175               {
 176                 if (bitset_test (no_reduce_set, i))
 177                   firstd = print_token (&dout, firstd, symbols[i]->tag);
 178                 else
 179                   {
 180                     if (! defaulted)
 181                       firste = print_token (&eout, firste, symbols[i]->tag);
 182                     bitset_set (no_reduce_set, i);
 183                   }
 184               }
 185         }
 186
 187       /* Do the actual output. */
 188       conclude_red (&eout, source, ruleno, true, firste, fout);
 189       conclude_red (&dout, source, ruleno, false, firstd, fout);
 190     }
 191   obstack_free (&eout, 0);
 192   obstack_free (&dout, 0);
 193 }
 194
 195 void
 196 finish_graph (FILE *fout)
 197 {
 198   fputs ("}\n", fout);
 199 }