1 /* Type definitions for the finite state machine for Bison.
2
3 Copyright (C) 2001-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 #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->lookaheads = 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_index *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 const *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_lookaheads_print (state const *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->lookaheads && red != -1)
271 {
272 bitset_iterator biter;
273 int k;
274 char const *sep = "";
275 fprintf (out, " [");
276 BITSET_FOR_EACH (biter, reds->lookaheads[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_lookaheads_print_xml (state const *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->lookaheads && red != -1)
295 {
296 bitset_iterator biter;
297 int k;
298 xml_puts (out, level, "<lookaheads>");
299 BITSET_FOR_EACH (biter, reds->lookaheads[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 hash_xinsert (state_table, s);
389 }
390
391
392 /*------------------------------------------------------------------.
393 | Find the state associated to the CORE, and return it. If it does |
394 | not exist yet, return NULL. |
395 `------------------------------------------------------------------*/
396
397 state *
398 state_hash_lookup (size_t nitems, const item_index *core)
399 {
400 size_t items_size = nitems * sizeof *core;
401 state *probe = xmalloc (offsetof (state, items) + items_size);
402 probe->nitems = nitems;
403 memcpy (probe->items, core, items_size);
404 state *entry = hash_lookup (state_table, probe);
405 free (probe);
406 return entry;
407 }
408
409
410 /*--------------------------------------------------------.
411 | Record S and all states reachable from S in REACHABLE. |
412 `--------------------------------------------------------*/
413
414 static void
415 state_record_reachable_states (state *s, bitset reachable)
416 {
417 if (bitset_test (reachable, s->number))
418 return;
419 bitset_set (reachable, s->number);
420 for (int i = 0; i < s->transitions->num; ++i)
421 if (!TRANSITION_IS_DISABLED (s->transitions, i))
422 state_record_reachable_states (s->transitions->states[i], reachable);
423 }
424
425 void
426 state_remove_unreachable_states (state_number old_to_new[])
427 {
428 state_number nstates_reachable = 0;
429 bitset reachable = bitset_create (nstates, BITSET_FIXED);
430 state_record_reachable_states (states[0], reachable);
431 for (state_number i = 0; i < nstates; ++i)
432 {
433 if (bitset_test (reachable, states[i]->number))
434 {
435 states[nstates_reachable] = states[i];
436 states[nstates_reachable]->number = nstates_reachable;
437 old_to_new[i] = nstates_reachable++;
438 }
439 else
440 {
441 state_free (states[i]);
442 old_to_new[i] = nstates;
443 }
444 }
445 nstates = nstates_reachable;
446 bitset_free (reachable);
447 }
448
449 /* All the decorated states, indexed by the state number. */
450 state **states = NULL;
451
452
453 /*----------------------.
454 | Free all the states. |
455 `----------------------*/
456
457 void
458 states_free (void)
459 {
460 closure_free ();
461 for (state_number i = 0; i < nstates; ++i)
462 state_free (states[i]);
463 free (states);
464 }