]> git.saurik.com Git - bison.git/blame - src/state.c
style changes.
[bison.git] / src / state.c
CommitLineData
ec14f0c8 1/* Type definitions for nondeterministic finite state machine for Bison.
03b9e273 2
f805dfcb
JD
3 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 Free
4 Software 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;
f805dfcb 145 res->state_list = NULL;
03b9e273 146 res->consistent = 0;
df0e7316 147 res->solved_conflicts = NULL;
41d7a5f2 148 res->solved_conflicts_xml = NULL;
df0e7316 149
03b9e273
PE
150 res->nitems = nitems;
151 memcpy (res->items, core, items_size);
df0e7316 152
8b752b00
AD
153 state_hash_insert (res);
154
df0e7316
AD
155 return res;
156}
157
f805dfcb
JD
158state *
159state_new_isocore (state const *s)
160{
161 state *res;
162 size_t items_size = s->nitems * sizeof *s->items;
163
164 aver (nstates < STATE_NUMBER_MAXIMUM);
165
166 res = xmalloc (offsetof (state, items) + items_size);
167 res->number = nstates++;
168 res->accessing_symbol = s->accessing_symbol;
169 res->transitions =
170 transitions_new (s->transitions->num, s->transitions->states);
171 res->reductions = reductions_new (s->reductions->num, s->reductions->rules);
172 res->errs = NULL;
173 res->state_list = NULL;
174 res->consistent = s->consistent;
175 res->solved_conflicts = NULL;
176 res->solved_conflicts_xml = NULL;
177
178 res->nitems = s->nitems;
179 memcpy (res->items, s->items, items_size);
180
181 return res;
182}
183
df0e7316 184
17ee7397
PE
185/*---------.
186| Free S. |
187`---------*/
8b752b00
AD
188
189static void
17ee7397 190state_free (state *s)
8b752b00 191{
17ee7397
PE
192 free (s->transitions);
193 free (s->reductions);
194 free (s->errs);
195 free (s);
8b752b00
AD
196}
197
198
17ee7397
PE
199/*---------------------------.
200| Set the transitions of S. |
201`---------------------------*/
32e1e0a4
AD
202
203void
17ee7397 204state_transitions_set (state *s, int num, state **trans)
32e1e0a4 205{
4f82b42a 206 aver (!s->transitions);
17ee7397 207 s->transitions = transitions_new (num, trans);
32e1e0a4
AD
208}
209
210
17ee7397
PE
211/*--------------------------.
212| Set the reductions of S. |
213`--------------------------*/
8a731ca8
AD
214
215void
17ee7397 216state_reductions_set (state *s, int num, rule **reds)
8a731ca8 217{
4f82b42a 218 aver (!s->reductions);
17ee7397 219 s->reductions = reductions_new (num, reds);
8b752b00
AD
220}
221
222
cd08e51e 223int
17ee7397 224state_reduction_find (state *s, rule *r)
cd08e51e
AD
225{
226 int i;
17ee7397 227 reductions *reds = s->reductions;
cd08e51e 228 for (i = 0; i < reds->num; ++i)
17ee7397 229 if (reds->rules[i] == r)
cd08e51e
AD
230 return i;
231 return -1;
232}
233
234
17ee7397
PE
235/*--------------------.
236| Set the errs of S. |
237`--------------------*/
8b752b00
AD
238
239void
17ee7397 240state_errs_set (state *s, int num, symbol **tokens)
8b752b00 241{
4f82b42a 242 aver (!s->errs);
17ee7397 243 s->errs = errs_new (num, tokens);
8a731ca8
AD
244}
245
246
32e1e0a4 247
742e4900
JD
248/*--------------------------------------------------.
249| Print on OUT all the lookahead tokens such that S |
250| wants to reduce R. |
251`--------------------------------------------------*/
10e5b8bd
AD
252
253void
742e4900 254state_rule_lookahead_tokens_print (state *s, rule *r, FILE *out)
10e5b8bd 255{
cd08e51e 256 /* Find the reduction we are handling. */
17ee7397
PE
257 reductions *reds = s->reductions;
258 int red = state_reduction_find (s, r);
10e5b8bd
AD
259
260 /* Print them if there are. */
742e4900 261 if (reds->lookahead_tokens && red != -1)
10e5b8bd 262 {
cd08e51e
AD
263 bitset_iterator biter;
264 int k;
d0829076 265 char const *sep = "";
2f4f028d 266 fprintf (out, " [");
742e4900 267 BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
d0829076
PE
268 {
269 fprintf (out, "%s%s", sep, symbols[k]->tag);
270 sep = ", ";
271 }
2f4f028d 272 fprintf (out, "]");
10e5b8bd
AD
273 }
274}
c7ca99d4 275
41d7a5f2
PE
276void
277state_rule_lookahead_tokens_print_xml (state *s, rule *r,
278 FILE *out, int level)
279{
280 /* Find the reduction we are handling. */
281 reductions *reds = s->reductions;
282 int red = state_reduction_find (s, r);
283
284 /* Print them if there are. */
285 if (reds->lookahead_tokens && red != -1)
286 {
287 bitset_iterator biter;
288 int k;
41d7a5f2
PE
289 xml_puts (out, level, "<lookaheads>");
290 BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
291 {
408476bc 292 xml_printf (out, level + 1, "<symbol>%s</symbol>",
41d7a5f2
PE
293 xml_escape (symbols[k]->tag));
294 }
295 xml_puts (out, level, "</lookaheads>");
296 }
297}
298
c7ca99d4 299
36b5e963 300/*---------------------.
c7ca99d4 301| A state hash table. |
36b5e963 302`---------------------*/
c7ca99d4
AD
303
304/* Initial capacity of states hash table. */
305#define HT_INITIAL_CAPACITY 257
306
307static struct hash_table *state_table = NULL;
308
309/* Two states are equal if they have the same core items. */
03b9e273 310static inline bool
17ee7397 311state_compare (state const *s1, state const *s2)
c7ca99d4 312{
f6fbd3da 313 size_t i;
c7ca99d4
AD
314
315 if (s1->nitems != s2->nitems)
8307162d 316 return false;
c7ca99d4
AD
317
318 for (i = 0; i < s1->nitems; ++i)
319 if (s1->items[i] != s2->items[i])
8307162d 320 return false;
c7ca99d4 321
8307162d 322 return true;
c7ca99d4
AD
323}
324
03b9e273
PE
325static bool
326state_comparator (void const *s1, void const *s2)
327{
328 return state_compare (s1, s2);
329}
330
233a88ad
PE
331static inline size_t
332state_hash (state const *s, size_t tablesize)
c7ca99d4
AD
333{
334 /* Add up the state's item numbers to get a hash key. */
233a88ad 335 size_t key = 0;
f6fbd3da 336 size_t i;
17ee7397
PE
337 for (i = 0; i < s->nitems; ++i)
338 key += s->items[i];
c7ca99d4
AD
339 return key % tablesize;
340}
341
233a88ad
PE
342static size_t
343state_hasher (void const *s, size_t tablesize)
03b9e273
PE
344{
345 return state_hash (s, tablesize);
346}
347
c7ca99d4
AD
348
349/*-------------------------------.
350| Create the states hash table. |
351`-------------------------------*/
352
353void
354state_hash_new (void)
355{
356 state_table = hash_initialize (HT_INITIAL_CAPACITY,
357 NULL,
03b9e273
PE
358 state_hasher,
359 state_comparator,
360 NULL);
c7ca99d4
AD
361}
362
363
364/*---------------------------------------------.
365| Free the states hash table, not the states. |
366`---------------------------------------------*/
367
368void
369state_hash_free (void)
370{
371 hash_free (state_table);
372}
373
374
17ee7397
PE
375/*-----------------------------------.
376| Insert S in the state hash table. |
377`-----------------------------------*/
c7ca99d4
AD
378
379void
17ee7397 380state_hash_insert (state *s)
c7ca99d4 381{
75c7a52a
AD
382 if (!hash_insert (state_table, s))
383 xalloc_die ();
c7ca99d4
AD
384}
385
386
387/*------------------------------------------------------------------.
388| Find the state associated to the CORE, and return it. If it does |
389| not exist yet, return NULL. |
390`------------------------------------------------------------------*/
391
17ee7397 392state *
03b9e273 393state_hash_lookup (size_t nitems, item_number *core)
c7ca99d4 394{
03b9e273
PE
395 size_t items_size = nitems * sizeof *core;
396 state *probe = xmalloc (offsetof (state, items) + items_size);
17ee7397 397 state *entry;
c7ca99d4 398
03b9e273
PE
399 probe->nitems = nitems;
400 memcpy (probe->items, core, items_size);
c7ca99d4
AD
401 entry = hash_lookup (state_table, probe);
402 free (probe);
403 return entry;
404}
405
5967f0cf 406
14462c2b
JD
407/*--------------------------------------------------------.
408| Record S and all states reachable from S in REACHABLE. |
409`--------------------------------------------------------*/
5967f0cf
JD
410
411static void
14462c2b 412state_record_reachable_states (state *s, bitset reachable)
5967f0cf 413{
14462c2b 414 if (bitset_test (reachable, s->number))
5967f0cf 415 return;
14462c2b
JD
416 bitset_set (reachable, s->number);
417 {
418 int i;
419 for (i = 0; i < s->transitions->num; ++i)
420 if (!TRANSITION_IS_DISABLED (s->transitions, i))
421 state_record_reachable_states (s->transitions->states[i], reachable);
422 }
5967f0cf
JD
423}
424
425void
426state_remove_unreachable_states (state_number old_to_new[])
427{
428 state_number nstates_reachable = 0;
14462c2b
JD
429 bitset reachable = bitset_create (nstates, BITSET_FIXED);
430 state_record_reachable_states (states[0], reachable);
431 {
432 state_number i;
433 for (i = 0; i < nstates; ++i)
434 {
435 if (bitset_test (reachable, states[i]->number))
436 {
437 states[nstates_reachable] = states[i];
438 states[nstates_reachable]->number = nstates_reachable;
439 old_to_new[i] = nstates_reachable++;
440 }
441 else
442 {
443 state_free (states[i]);
444 old_to_new[i] = nstates;
445 }
446 }
447 }
5967f0cf 448 nstates = nstates_reachable;
14462c2b 449 bitset_free (reachable);
5967f0cf
JD
450}
451
c7ca99d4 452/* All the decorated states, indexed by the state number. */
17ee7397 453state **states = NULL;
c7ca99d4
AD
454
455
456/*----------------------.
457| Free all the states. |
458`----------------------*/
459
460void
461states_free (void)
462{
17ee7397 463 state_number i;
c7ca99d4 464 for (i = 0; i < nstates; ++i)
8b752b00
AD
465 state_free (states[i]);
466 free (states);
c7ca99d4 467}