Home | History | Annotate | Download | only in src 
      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     (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 }
    219