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
35static char *
36quote (char const *name)
37{
38  return quotearg_n_style (2, c_quoting_style, name);
39}
40
41void
42start_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
62void
63output_node (int id, char const *label, FILE *fout)
64{
65  fprintf (fout, "  %d [label=\"%s\"]\n", id, label);
66}
67
68void
69output_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
78char const *
79escape (char const *name)
80{
81  char *q = quote (name);
82  q[strlen (q) - 1] = '\0';
83  return q + 1;
84}
85
86static void
87no_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
99static void
100conclude_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
144static bool
145print_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
155void
156output_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
214void
215finish_graph (FILE *fout)
216{
217  fputs ("}\n", fout);
218}
219