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
44static transitions *
45transitions_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
55state *
56transitions_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
75errs *
76errs_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
98static reductions *
99reductions_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
116state_number nstates = 0;
117/* FINAL_STATE is properly set by new_state when it recognizes its
118 accessing symbol: $end. */
119state *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
127state *
128state_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
153state *
154state_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
182static void
183state_free (state *s)
184{
185 free (s->transitions);
186 free (s->reductions);
187 free (s->errs);
188 free (s);
189}
190
191
192void
193state_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
211void
212state_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
225void
226state_reductions_set (state *s, int num, rule **reds)
227{
228 aver (!s->reductions);
229 s->reductions = reductions_new (num, reds);
230}
231
232
233int
234state_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
248void
249state_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
262void
263state_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
285void
286state_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
316static struct hash_table *state_table = NULL;
317
318/* Two states are equal if they have the same core items. */
319static inline bool
320state_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
332static bool
333state_comparator (void const *s1, void const *s2)
334{
335 return state_compare (s1, s2);
336}
337
338static inline size_t
339state_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
348static size_t
349state_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
359void
360state_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
374void
375state_hash_free (void)
376{
377 hash_free (state_table);
378}
379
380
381/*-----------------------------------.
382| Insert S in the state hash table. |
383`-----------------------------------*/
384
385void
386state_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
398state *
399state_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
415static void
416state_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
426void
427state_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. */
451state **states = NULL;
452
453
454/*----------------------.
455| Free all the states. |
456`----------------------*/
457
458void
459states_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