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 *
quote(char const * name)37 quote (char const *name)
38 {
39 return quotearg_n_style (2, c_quoting_style, name);
40 }
41
42 void
start_graph(FILE * fout)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
output_node(int id,char const * label,FILE * fout)64 output_node (int id, char const *label, FILE *fout)
65 {
66 fprintf (fout, " %d [label=\"%s\"]\n", id, label);
67 }
68
69 void
output_edge(int source,int destination,char const * label,char const * style,FILE * fout)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
no_reduce_bitset_init(state const * s,bitset * no_reduce_set)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
conclude_red(struct obstack * out,int source,rule_number ruleno,bool enabled,bool first,FILE * fout)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
print_token(struct obstack * out,bool first,char const * tok)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
output_red(state const * s,reductions const * reds,FILE * fout)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
finish_graph(FILE * fout)211 finish_graph (FILE *fout)
212 {
213 fputs ("}\n", fout);
214 }
215