src/graphviz.c

   1 /* Output Graphviz specification of a state machine generated by Bison.
   2
   3    Copyright (C) 2006-2007, 2009-2015, 2018-2021 Free Software
   4    Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  20
  21 /* Written by Paul Eggert and Satya Kiran Popuri.  */
  22
  23 #include <config.h>
  24 #include "system.h"
  25
  26 #include <quotearg.h>
  27
  28 #include "files.h"
  29 #include "gram.h"
  30 #include "graphviz.h"
  31 #include "tables.h"
  32
  33 /* Return an unambiguous printable representation for NAME, suitable
  34    for C strings.  Use slot 2 since the user may use slots 0 and 1.  */
  35
  36 static char *
  37 quote (char const *name)
  38 {
  39   return quotearg_n_style (2, c_quoting_style, name);
  40 }
  41
  42 void
  43 start_graph (FILE *fout)
  44 {
  45   fprintf (fout,
  46            _("// Generated by %s.\n"
  47              "// Report bugs to <%s>.\n"
  48              "// Home page: <%s>.\n"
  49              "\n"),
  50            PACKAGE_STRING,
  51            PACKAGE_BUGREPORT,
  52            PACKAGE_URL);
  53   fprintf (fout,
  54            "digraph %s\n"
  55            "{\n",
  56            quote (grammar_file));
  57   fprintf (fout,
  58            "  node [fontname = courier, shape = box, colorscheme = paired6]\n"
  59            "  edge [fontname = courier]\n"
  60            "\n");
  61 }
  62
  63 void
  64 output_node (int id, char const *label, FILE *fout)
  65 {
  66   fprintf (fout, "  %d [label=\"%s\"]\n", id, label);
  67 }
  68
  69 void
  70 output_edge (int source, int destination, char const *label,
  71              char const *style, FILE *fout)
  72 {
  73   fprintf (fout, "  %d -> %d [style=%s", source, destination, style);
  74   if (label)
  75     {
  76       fputs (" label=\"", fout);
  77       for (const char *cp = label; *cp; ++cp)
  78         switch (*cp)
  79         {
  80         case '"':  fputs ("\\\"", fout); break;
  81         case '\\': fputs ("\\\\", fout); break;
  82         default:   fputc (*cp,    fout); break;
  83         }
  84       fputc ('"', fout);
  85     }
  86   fputs ("]\n", fout);
  87 }
  88
  89 static void
  90 no_reduce_bitset_init (state const *s, bitset *no_reduce_set)
  91 {
  92   *no_reduce_set = bitset_create (ntokens, BITSET_FIXED);
  93   bitset_zero (*no_reduce_set);
  94   {
  95     int n;
  96     FOR_EACH_SHIFT (s->transitions, n)
  97       bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n));
  98   }
  99   for (int n = 0; n < s->errs->num; ++n)
 100     if (s->errs->symbols[n])
 101       bitset_set (*no_reduce_set, s->errs->symbols[n]->content->number);
 102 }
 103
 104 /* Show the reductions from state SOURCE on rule RULENO. */
 105 static void
 106 conclude_red (struct obstack *out, int source, rule_number ruleno,
 107               bool enabled, bool first, FILE *fout)
 108 {
 109   /* If no lookahead tokens were valid transitions, this reduction is
 110      actually hidden, so cancel everything. */
 111   if (first)
 112     (void) obstack_finish0 (out);
 113   else
 114     {
 115       char const *ed = enabled ? "" : "d";
 116       /* First, build the edge's head. The name of reduction nodes is "nRm",
 117          with n the source state and m the rule number. This is because we
 118          don't want all the reductions bearing a same rule number to point to
 119          the same state, since that is not the desired format. */
 120       fprintf (fout, "  %d -> \"%dR%d%s\" [",
 121                source, source, ruleno, ed);
 122
 123       /* (The lookahead tokens have been added to the beginning of the
 124          obstack, in the caller function.) */
 125       if (! obstack_empty_p (out))
 126         {
 127           char *label = obstack_finish0 (out);
 128           fprintf (fout, "label=\"[%s]\", ", label);
 129           obstack_free (out, label);
 130         }
 131
 132       /* Then, the edge's tail. */
 133       fprintf (fout, "style=solid]\n");
 134
 135       /* Build the associated diamond representation of the target rule. */
 136       fprintf (fout, " \"%dR%d%s\" [label=\"",
 137                source, ruleno, ed);
 138       bool const final = rule_is_initial (&rules[ruleno]);
 139       if (final)
 140         fprintf (fout, "Acc");
 141       else
 142         fprintf (fout, "R%d", ruleno);
 143
 144       char const *color
 145         = !enabled ? "5"
 146         : final    ? "1"
 147         :            "3";
 148       fprintf (fout, "\", fillcolor=%s, shape=diamond, style=filled]\n",
 149                color);
 150     }
 151 }
 152
 153 static bool
 154 print_token (struct obstack *out, bool first, char const *tok)
 155 {
 156   if (! first)
 157     obstack_sgrow (out, ", ");
 158   obstack_backslash (out, tok);
 159   return false;
 160 }
 161
 162 void
 163 output_red (state const *s, reductions const *reds, FILE *fout)
 164 {
 165   bitset no_reduce_set;
 166   no_reduce_bitset_init (s, &no_reduce_set);
 167
 168   rule *default_reduction
 169     = yydefact[s->number] ? &rules[yydefact[s->number] - 1] : NULL;
 170
 171   /* Two obstacks are needed: one for the enabled reductions, and one
 172      for the disabled reductions, because in the end we want two
 173      separate edges, even though in most cases only one will actually
 174      be printed. */
 175   struct obstack dout;
 176   struct obstack eout;
 177   obstack_init (&dout);
 178   obstack_init (&eout);
 179
 180   const int source = s->number;
 181   for (int j = 0; j < reds->num; ++j)
 182     {
 183       bool defaulted = default_reduction && default_reduction == reds->rules[j];
 184
 185       /* Build the lookahead tokens lists, one for enabled transitions
 186          and one for disabled transitions. */
 187       bool firstd = true;
 188       bool firste = true;
 189       rule_number ruleno = reds->rules[j]->number;
 190
 191       if (reds->lookaheads)
 192         for (int i = 0; i < ntokens; i++)
 193           if (bitset_test (reds->lookaheads[j], i))
 194             {
 195               if (bitset_test (no_reduce_set, i))
 196                 firstd = print_token (&dout, firstd, symbols[i]->tag);
 197               else
 198                 {
 199                   if (! defaulted)
 200                     firste = print_token (&eout, firste, symbols[i]->tag);
 201                   bitset_set (no_reduce_set, i);
 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 }