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 | |
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 | fprintf (fout, " label=%s" , quote (label)); |
76 | fputs ("]\n" , fout); |
77 | } |
78 | |
79 | char const * |
80 | escape (char const *name) |
81 | { |
82 | char *q = quote (name); |
83 | q[strlen (q) - 1] = '\0'; |
84 | return q + 1; |
85 | } |
86 | |
87 | static void |
88 | no_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 | |
102 | static void |
103 | conclude_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 | |
147 | static bool |
148 | print_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 | |
156 | void |
157 | output_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 | |
208 | void |
209 | finish_graph (FILE *fout) |
210 | { |
211 | fputs ("}\n" , fout); |
212 | } |
213 | |