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