1/* Output Graphviz specification of a state machine generated by Bison.
2
3 Copyright (C) 2006-2007, 2009-2015, 2018-2019 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 <http://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
36static char *
37quote (char const *name)
38{
39 return quotearg_n_style (2, c_quoting_style, name);
40}
41
42void
43start_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
63void
64output_node (int id, char const *label, FILE *fout)
65{
66 fprintf (fout, " %d [label=\"%s\"]\n", id, label);
67}
68
69void
70output_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 fprintf (fout, " label=%s", quote (label));
76 fputs ("]\n", fout);
77}
78
79char const *
80escape (char const *name)
81{
82 char *q = quote (name);
83 q[strlen (q) - 1] = '\0';
84 return q + 1;
85}
86
87static void
88no_reduce_bitset_init (state const *s, bitset *no_reduce_set)
89{
90 *no_reduce_set = bitset_create (ntokens, BITSET_FIXED);
91 bitset_zero (*no_reduce_set);
92 {
93 int n;
94 FOR_EACH_SHIFT (s->transitions, n)
95 bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n));
96 }
97 for (int n = 0; n < s->errs->num; ++n)
98 if (s->errs->symbols[n])
99 bitset_set (*no_reduce_set, s->errs->symbols[n]->content->number);
100}
101
102static void
103conclude_red (struct obstack *out, int source, rule_number ruleno,
104 bool enabled, bool first, FILE *fout)
105{
106 /* If no lookahead tokens were valid transitions, this reduction is
107 actually hidden, so cancel everything. */
108 if (first)
109 (void) obstack_finish0 (out);
110 else
111 {
112 char const *ed = enabled ? "" : "d";
113 char const *color = enabled ? ruleno ? "3" : "1" : "5";
114
115 /* First, build the edge's head. The name of reduction nodes is "nRm",
116 with n the source state and m the rule number. This is because we
117 don't want all the reductions bearing a same rule number to point to
118 the same state, since that is not the desired format. */
119 fprintf (fout, " %d -> \"%dR%d%s\" [",
120 source, source, ruleno, ed);
121
122 /* (The lookahead tokens have been added to the beginning of the
123 obstack, in the caller function.) */
124 if (! obstack_empty_p (out))
125 {
126 char *label = obstack_finish0 (out);
127 fprintf (fout, "label=\"[%s]\", ", label);
128 obstack_free (out, label);
129 }
130
131 /* Then, the edge's tail. */
132 fprintf (fout, "style=solid]\n");
133
134 /* Build the associated diamond representation of the target rule. */
135 fprintf (fout, " \"%dR%d%s\" [label=\"",
136 source, ruleno, ed);
137 if (ruleno)
138 fprintf (fout, "R%d", ruleno);
139 else
140 fprintf (fout, "Acc");
141
142 fprintf (fout, "\", fillcolor=%s, shape=diamond, style=filled]\n",
143 color);
144 }
145}
146
147static bool
148print_token (struct obstack *out, bool first, char const *tok)
149{
150 if (! first)
151 obstack_sgrow (out, ", ");
152 obstack_sgrow (out, escape (tok));
153 return false;
154}
155
156void
157output_red (state const *s, reductions const *reds, FILE *fout)
158{
159 bitset no_reduce_set;
160 no_reduce_bitset_init (s, &no_reduce_set);
161
162 rule *default_reduction
163 = yydefact[s->number] ? &rules[yydefact[s->number] - 1] : NULL;
164
165 /* Two obstacks are needed: one for the enabled reductions, and one
166 for the disabled reductions, because in the end we want two
167 separate edges, even though in most cases only one will actually
168 be printed. */
169 struct obstack dout;
170 struct obstack eout;
171 obstack_init (&dout);
172 obstack_init (&eout);
173
174 const int source = s->number;
175 for (int j = 0; j < reds->num; ++j)
176 {
177 bool defaulted = default_reduction && default_reduction == reds->rules[j];
178
179 /* Build the lookahead tokens lists, one for enabled transitions
180 and one for disabled transitions. */
181 bool firstd = true;
182 bool firste = true;
183 rule_number ruleno = reds->rules[j]->number;
184
185 if (reds->lookahead_tokens)
186 for (int i = 0; i < ntokens; i++)
187 if (bitset_test (reds->lookahead_tokens[j], i))
188 {
189 if (bitset_test (no_reduce_set, i))
190 firstd = print_token (&dout, firstd, symbols[i]->tag);
191 else
192 {
193 if (! defaulted)
194 firste = print_token (&eout, firste, symbols[i]->tag);
195 bitset_set (no_reduce_set, i);
196 }
197 }
198
199 /* Do the actual output. */
200 conclude_red (&dout, source, ruleno, false, firstd, fout);
201 conclude_red (&eout, source, ruleno, true, firste && !defaulted, fout);
202 }
203 obstack_free (&dout, 0);
204 obstack_free (&eout, 0);
205 bitset_free (no_reduce_set);
206}
207
208void
209finish_graph (FILE *fout)
210{
211 fputs ("}\n", fout);
212}
213