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 ? "e" : "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       if (! obstack_empty_p (out))
 120         /* (The lookahead tokens have been added to the beginning of the
 121            obstack, in the caller function.) */
 122         fprintf (fout, "label = \"[%s]\" ", obstack_finish0 (out));
 123
 124       /* Then, the edge's tail. */
 125       fprintf (fout, "style = solid]\n");
 126
 127       /* Build the associated diamond representation of the target rule. */
 128       fprintf (fout, " \"%dR%d%s\" [style = filled, "
 129                     "shape = diamond, fillcolor = %s, ",
 130                source, ruleno, ed, color);
 131
 132      if (ruleno)
 133         fprintf (fout, "label = \"R%d\"]\n", ruleno);
 134       else
 135         fprintf (fout, "label = \"Acc\"]\n");
 136
 137     }
 138 }
 139
 140 static bool
 141 print_token (struct obstack *out, bool first, char const *tok)
 142 {
 143   char const *q = escape (tok);
 144
 145   if (! first)
 146     obstack_sgrow (out, ", ");
 147   obstack_sgrow (out, q);
 148   return false;
 149 }
 150
 151 void
 152 output_red (state const *s, reductions const *reds, FILE *fout)
 153 {
 154   bitset no_reduce_set;
 155   int j;
 156   int source = s->number;
 157
 158   /* Two obstacks are needed: one for the enabled reductions, and one
 159      for the disabled reductions, because in the end we want two
 160      separate edges, even though in most cases only one will actually
 161      be printed. */
 162   struct obstack dout;
 163   struct obstack eout;
 164
 165   no_reduce_bitset_init (s, &no_reduce_set);
 166   obstack_init (&dout);
 167   obstack_init (&eout);
 168
 169   for (j = 0; j < reds->num; ++j)
 170     {
 171       bool defaulted = false;
 172       bool firstd = true;
 173       bool firste = true;
 174       rule_number ruleno = reds->rules[j]->user_number;
 175       rule *default_reduction = NULL;
 176
 177       if (yydefact[s->number] != 0)
 178         default_reduction = &rules[yydefact[s->number] - 1];
 179
 180       /* Build the lookahead tokens lists, one for enabled transitions and one
 181          for disabled transistions. */
 182       if (default_reduction && default_reduction == reds->rules[j])
 183         defaulted = true;
 184       if (reds->lookahead_tokens)
 185         {
 186           int i;
 187           for (i = 0; i < ntokens; i++)
 188             if (bitset_test (reds->lookahead_tokens[j], i))
 189               {
 190                 if (bitset_test (no_reduce_set, i))
 191                   firstd = print_token (&dout, firstd, symbols[i]->tag);
 192                 else
 193                   {
 194                     if (! defaulted)
 195                       firste = print_token (&eout, firste, symbols[i]->tag);
 196                     bitset_set (no_reduce_set, i);
 197                   }
 198               }
 199         }
 200
 201       /* Do the actual output. */
 202       conclude_red (&eout, source, ruleno, true, firste && !defaulted, fout);
 203       conclude_red (&dout, source, ruleno, false, firstd, fout);
 204     }
 205   obstack_free (&eout, 0);
 206   obstack_free (&dout, 0);
 207 }
 208
 209 void
 210 finish_graph (FILE *fout)
 211 {
 212   fputs ("}\n", fout);
 213 }