1 | /* Type definitions for the finite state machine for Bison. |
2 | |
3 | Copyright (C) 2001-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 | #include <config.h> |
22 | #include "state.h" |
23 | |
24 | #include "system.h" |
25 | |
26 | #include <hash.h> |
27 | |
28 | #include "closure.h" |
29 | #include "complain.h" |
30 | #include "getargs.h" |
31 | #include "gram.h" |
32 | #include "print-xml.h" |
33 | |
34 | |
35 | /*-------------------. |
36 | | Shifts and Gotos. | |
37 | `-------------------*/ |
38 | |
39 | |
40 | /*-----------------------------------------. |
41 | | Create a new array of NUM shifts/gotos. | |
42 | `-----------------------------------------*/ |
43 | |
44 | static transitions * |
45 | transitions_new (int num, state **dst) |
46 | { |
47 | size_t states_size = num * sizeof *dst; |
48 | transitions *res = xmalloc (offsetof (transitions, states) + states_size); |
49 | res->num = num; |
50 | memcpy (res->states, dst, states_size); |
51 | return res; |
52 | } |
53 | |
54 | |
55 | state * |
56 | transitions_to (state *s, symbol_number sym) |
57 | { |
58 | transitions *trans = s->transitions; |
59 | for (int i = 0; i < trans->num; ++i) |
60 | if (TRANSITION_SYMBOL (trans, i) == sym) |
61 | return trans->states[i]; |
62 | abort (); |
63 | } |
64 | |
65 | |
66 | /*--------------------. |
67 | | Error transitions. | |
68 | `--------------------*/ |
69 | |
70 | |
71 | /*---------------------------------. |
72 | | Create a new array of NUM errs. | |
73 | `---------------------------------*/ |
74 | |
75 | errs * |
76 | errs_new (int num, symbol **tokens) |
77 | { |
78 | size_t symbols_size = num * sizeof *tokens; |
79 | errs *res = xmalloc (offsetof (errs, symbols) + symbols_size); |
80 | res->num = num; |
81 | if (tokens) |
82 | memcpy (res->symbols, tokens, symbols_size); |
83 | return res; |
84 | } |
85 | |
86 | |
87 | |
88 | |
89 | /*-------------. |
90 | | Reductions. | |
91 | `-------------*/ |
92 | |
93 | |
94 | /*---------------------------------------. |
95 | | Create a new array of NUM reductions. | |
96 | `---------------------------------------*/ |
97 | |
98 | static reductions * |
99 | reductions_new (int num, rule **reds) |
100 | { |
101 | size_t rules_size = num * sizeof *reds; |
102 | reductions *res = xmalloc (offsetof (reductions, rules) + rules_size); |
103 | res->num = num; |
104 | res->lookahead_tokens = NULL; |
105 | memcpy (res->rules, reds, rules_size); |
106 | return res; |
107 | } |
108 | |
109 | |
110 | |
111 | /*---------. |
112 | | States. | |
113 | `---------*/ |
114 | |
115 | |
116 | state_number nstates = 0; |
117 | /* FINAL_STATE is properly set by new_state when it recognizes its |
118 | accessing symbol: $end. */ |
119 | state *final_state = NULL; |
120 | |
121 | |
122 | /*------------------------------------------------------------------. |
123 | | Create a new state with ACCESSING_SYMBOL, for those items. Store | |
124 | | it in the state hash table. | |
125 | `------------------------------------------------------------------*/ |
126 | |
127 | state * |
128 | state_new (symbol_number accessing_symbol, |
129 | size_t nitems, item_number *core) |
130 | { |
131 | aver (nstates < STATE_NUMBER_MAXIMUM); |
132 | |
133 | size_t items_size = nitems * sizeof *core; |
134 | state *res = xmalloc (offsetof (state, items) + items_size); |
135 | res->number = nstates++; |
136 | res->accessing_symbol = accessing_symbol; |
137 | res->transitions = NULL; |
138 | res->reductions = NULL; |
139 | res->errs = NULL; |
140 | res->state_list = NULL; |
141 | res->consistent = false; |
142 | res->solved_conflicts = NULL; |
143 | res->solved_conflicts_xml = NULL; |
144 | |
145 | res->nitems = nitems; |
146 | memcpy (res->items, core, items_size); |
147 | |
148 | state_hash_insert (res); |
149 | |
150 | return res; |
151 | } |
152 | |
153 | state * |
154 | state_new_isocore (state const *s) |
155 | { |
156 | aver (nstates < STATE_NUMBER_MAXIMUM); |
157 | |
158 | size_t items_size = s->nitems * sizeof *s->items; |
159 | state *res = xmalloc (offsetof (state, items) + items_size); |
160 | res->number = nstates++; |
161 | res->accessing_symbol = s->accessing_symbol; |
162 | res->transitions = |
163 | transitions_new (s->transitions->num, s->transitions->states); |
164 | res->reductions = reductions_new (s->reductions->num, s->reductions->rules); |
165 | res->errs = NULL; |
166 | res->state_list = NULL; |
167 | res->consistent = s->consistent; |
168 | res->solved_conflicts = NULL; |
169 | res->solved_conflicts_xml = NULL; |
170 | |
171 | res->nitems = s->nitems; |
172 | memcpy (res->items, s->items, items_size); |
173 | |
174 | return res; |
175 | } |
176 | |
177 | |
178 | /*---------. |
179 | | Free S. | |
180 | `---------*/ |
181 | |
182 | static void |
183 | state_free (state *s) |
184 | { |
185 | free (s->transitions); |
186 | free (s->reductions); |
187 | free (s->errs); |
188 | free (s); |
189 | } |
190 | |
191 | |
192 | void |
193 | state_transitions_print (const state *s, FILE *out) |
194 | { |
195 | const transitions *trans = s->transitions; |
196 | fprintf (out, "transitions of %d (%d):\n" , |
197 | s->number, trans->num); |
198 | for (int i = 0; i < trans->num; ++i) |
199 | fprintf (out, " %d: (%d, %s, %d)\n" , |
200 | i, |
201 | s->number, |
202 | symbols[s->transitions->states[i]->accessing_symbol]->tag, |
203 | s->transitions->states[i]->number); |
204 | } |
205 | |
206 | |
207 | /*---------------------------. |
208 | | Set the transitions of S. | |
209 | `---------------------------*/ |
210 | |
211 | void |
212 | state_transitions_set (state *s, int num, state **dst) |
213 | { |
214 | aver (!s->transitions); |
215 | s->transitions = transitions_new (num, dst); |
216 | if (trace_flag & trace_automaton) |
217 | state_transitions_print (s, stderr); |
218 | } |
219 | |
220 | |
221 | /*--------------------------. |
222 | | Set the reductions of S. | |
223 | `--------------------------*/ |
224 | |
225 | void |
226 | state_reductions_set (state *s, int num, rule **reds) |
227 | { |
228 | aver (!s->reductions); |
229 | s->reductions = reductions_new (num, reds); |
230 | } |
231 | |
232 | |
233 | int |
234 | state_reduction_find (state *s, rule const *r) |
235 | { |
236 | reductions *reds = s->reductions; |
237 | for (int i = 0; i < reds->num; ++i) |
238 | if (reds->rules[i] == r) |
239 | return i; |
240 | abort (); |
241 | } |
242 | |
243 | |
244 | /*--------------------. |
245 | | Set the errs of S. | |
246 | `--------------------*/ |
247 | |
248 | void |
249 | state_errs_set (state *s, int num, symbol **tokens) |
250 | { |
251 | aver (!s->errs); |
252 | s->errs = errs_new (num, tokens); |
253 | } |
254 | |
255 | |
256 | |
257 | /*--------------------------------------------------. |
258 | | Print on OUT all the lookahead tokens such that S | |
259 | | wants to reduce R. | |
260 | `--------------------------------------------------*/ |
261 | |
262 | void |
263 | state_rule_lookahead_tokens_print (state *s, rule const *r, FILE *out) |
264 | { |
265 | /* Find the reduction we are handling. */ |
266 | reductions *reds = s->reductions; |
267 | int red = state_reduction_find (s, r); |
268 | |
269 | /* Print them if there are. */ |
270 | if (reds->lookahead_tokens && red != -1) |
271 | { |
272 | bitset_iterator biter; |
273 | int k; |
274 | char const *sep = "" ; |
275 | fprintf (out, " [" ); |
276 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) |
277 | { |
278 | fprintf (out, "%s%s" , sep, symbols[k]->tag); |
279 | sep = ", " ; |
280 | } |
281 | fprintf (out, "]" ); |
282 | } |
283 | } |
284 | |
285 | void |
286 | state_rule_lookahead_tokens_print_xml (state *s, rule const *r, |
287 | FILE *out, int level) |
288 | { |
289 | /* Find the reduction we are handling. */ |
290 | reductions *reds = s->reductions; |
291 | int red = state_reduction_find (s, r); |
292 | |
293 | /* Print them if there are. */ |
294 | if (reds->lookahead_tokens && red != -1) |
295 | { |
296 | bitset_iterator biter; |
297 | int k; |
298 | xml_puts (out, level, "<lookaheads>" ); |
299 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) |
300 | { |
301 | xml_printf (out, level + 1, "<symbol>%s</symbol>" , |
302 | xml_escape (symbols[k]->tag)); |
303 | } |
304 | xml_puts (out, level, "</lookaheads>" ); |
305 | } |
306 | } |
307 | |
308 | |
309 | /*---------------------. |
310 | | A state hash table. | |
311 | `---------------------*/ |
312 | |
313 | /* Initial capacity of states hash table. */ |
314 | #define HT_INITIAL_CAPACITY 257 |
315 | |
316 | static struct hash_table *state_table = NULL; |
317 | |
318 | /* Two states are equal if they have the same core items. */ |
319 | static inline bool |
320 | state_compare (state const *s1, state const *s2) |
321 | { |
322 | if (s1->nitems != s2->nitems) |
323 | return false; |
324 | |
325 | for (size_t i = 0; i < s1->nitems; ++i) |
326 | if (s1->items[i] != s2->items[i]) |
327 | return false; |
328 | |
329 | return true; |
330 | } |
331 | |
332 | static bool |
333 | state_comparator (void const *s1, void const *s2) |
334 | { |
335 | return state_compare (s1, s2); |
336 | } |
337 | |
338 | static inline size_t |
339 | state_hash (state const *s, size_t tablesize) |
340 | { |
341 | /* Add up the state's item numbers to get a hash key. */ |
342 | size_t key = 0; |
343 | for (size_t i = 0; i < s->nitems; ++i) |
344 | key += s->items[i]; |
345 | return key % tablesize; |
346 | } |
347 | |
348 | static size_t |
349 | state_hasher (void const *s, size_t tablesize) |
350 | { |
351 | return state_hash (s, tablesize); |
352 | } |
353 | |
354 | |
355 | /*-------------------------------. |
356 | | Create the states hash table. | |
357 | `-------------------------------*/ |
358 | |
359 | void |
360 | state_hash_new (void) |
361 | { |
362 | state_table = hash_xinitialize (HT_INITIAL_CAPACITY, |
363 | NULL, |
364 | state_hasher, |
365 | state_comparator, |
366 | NULL); |
367 | } |
368 | |
369 | |
370 | /*---------------------------------------------. |
371 | | Free the states hash table, not the states. | |
372 | `---------------------------------------------*/ |
373 | |
374 | void |
375 | state_hash_free (void) |
376 | { |
377 | hash_free (state_table); |
378 | } |
379 | |
380 | |
381 | /*-----------------------------------. |
382 | | Insert S in the state hash table. | |
383 | `-----------------------------------*/ |
384 | |
385 | void |
386 | state_hash_insert (state *s) |
387 | { |
388 | if (!hash_insert (state_table, s)) |
389 | xalloc_die (); |
390 | } |
391 | |
392 | |
393 | /*------------------------------------------------------------------. |
394 | | Find the state associated to the CORE, and return it. If it does | |
395 | | not exist yet, return NULL. | |
396 | `------------------------------------------------------------------*/ |
397 | |
398 | state * |
399 | state_hash_lookup (size_t nitems, item_number *core) |
400 | { |
401 | size_t items_size = nitems * sizeof *core; |
402 | state *probe = xmalloc (offsetof (state, items) + items_size); |
403 | probe->nitems = nitems; |
404 | memcpy (probe->items, core, items_size); |
405 | state *entry = hash_lookup (state_table, probe); |
406 | free (probe); |
407 | return entry; |
408 | } |
409 | |
410 | |
411 | /*--------------------------------------------------------. |
412 | | Record S and all states reachable from S in REACHABLE. | |
413 | `--------------------------------------------------------*/ |
414 | |
415 | static void |
416 | state_record_reachable_states (state *s, bitset reachable) |
417 | { |
418 | if (bitset_test (reachable, s->number)) |
419 | return; |
420 | bitset_set (reachable, s->number); |
421 | for (int i = 0; i < s->transitions->num; ++i) |
422 | if (!TRANSITION_IS_DISABLED (s->transitions, i)) |
423 | state_record_reachable_states (s->transitions->states[i], reachable); |
424 | } |
425 | |
426 | void |
427 | state_remove_unreachable_states (state_number old_to_new[]) |
428 | { |
429 | state_number nstates_reachable = 0; |
430 | bitset reachable = bitset_create (nstates, BITSET_FIXED); |
431 | state_record_reachable_states (states[0], reachable); |
432 | for (state_number i = 0; i < nstates; ++i) |
433 | { |
434 | if (bitset_test (reachable, states[i]->number)) |
435 | { |
436 | states[nstates_reachable] = states[i]; |
437 | states[nstates_reachable]->number = nstates_reachable; |
438 | old_to_new[i] = nstates_reachable++; |
439 | } |
440 | else |
441 | { |
442 | state_free (states[i]); |
443 | old_to_new[i] = nstates; |
444 | } |
445 | } |
446 | nstates = nstates_reachable; |
447 | bitset_free (reachable); |
448 | } |
449 | |
450 | /* All the decorated states, indexed by the state number. */ |
451 | state **states = NULL; |
452 | |
453 | |
454 | /*----------------------. |
455 | | Free all the states. | |
456 | `----------------------*/ |
457 | |
458 | void |
459 | states_free (void) |
460 | { |
461 | closure_free (); |
462 | for (state_number i = 0; i < nstates; ++i) |
463 | state_free (states[i]); |
464 | free (states); |
465 | } |
466 | |