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