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