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 }