src/state.c

   1 /* Type definitions for nondeterministic finite state machine for Bison.
   2
   3    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4
   5    This file is part of Bison, the GNU Compiler Compiler.
   6
   7    Bison 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 2, or (at your option)
  10    any later version.
  11
  12    Bison 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 Bison; see the file COPYING.  If not, write to
  19    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20    Boston, MA 02110-1301, USA.  */
  21
  22 #include <config.h>
  23 #include "system.h"
  24
  25 #include <hash.h>
  26
  27 #include "complain.h"
  28 #include "gram.h"
  29 #include "state.h"
  30
  31
  32                         /*-------------------.
  33                         | Shifts and Gotos.  |
  34                         `-------------------*/
  35
  36
  37 /*-----------------------------------------.
  38 | Create a new array of NUM shifts/gotos.  |
  39 `-----------------------------------------*/
  40
  41 static transitions *
  42 transitions_new (int num, state **the_states)
  43 {
  44   size_t states_size = num * sizeof *the_states;
  45   transitions *res = xmalloc (offsetof (transitions, states) + states_size);
  46   res->num = num;
  47   memcpy (res->states, the_states, states_size);
  48   return res;
  49 }
  50
  51
  52 /*-------------------------------------------------------.
  53 | Return the state such that SHIFTS contain a shift/goto |
  54 | to it on SYM.  Abort if none found.                    |
  55 `-------------------------------------------------------*/
  56
  57 state *
  58 transitions_to (transitions *shifts, symbol_number sym)
  59 {
  60   int j;
  61   for (j = 0; j < shifts->num; j++)
  62     if (TRANSITION_SYMBOL (shifts, j) == sym)
  63       return shifts->states[j];
  64   abort ();
  65 }
  66
  67
  68                         /*--------------------.
  69                         | Error transitions.  |
  70                         `--------------------*/
  71
  72
  73 /*---------------------------------.
  74 | Create a new array of NUM errs.  |
  75 `---------------------------------*/
  76
  77 errs *
  78 errs_new (int num, symbol **tokens)
  79 {
  80   size_t symbols_size = num * sizeof *tokens;
  81   errs *res = xmalloc (offsetof (errs, symbols) + symbols_size);
  82   res->num = num;
  83   memcpy (res->symbols, tokens, symbols_size);
  84   return res;
  85 }
  86
  87
  88
  89
  90                         /*-------------.
  91                         | Reductions.  |
  92                         `-------------*/
  93
  94
  95 /*---------------------------------------.
  96 | Create a new array of NUM reductions.  |
  97 `---------------------------------------*/
  98
  99 static reductions *
 100 reductions_new (int num, rule **reds)
 101 {
 102   size_t rules_size = num * sizeof *reds;
 103   reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);
 104   res->num = num;
 105   res->look_ahead_tokens = NULL;
 106   memcpy (res->rules, reds, rules_size);
 107   return res;
 108 }
 109
 110
 111
 112                         /*---------.
 113                         | States.  |
 114                         `---------*/
 115
 116
 117 state_number nstates = 0;
 118 /* FINAL_STATE is properly set by new_state when it recognizes its
 119    accessing symbol: $end.  */
 120 state *final_state = NULL;
 121
 122
 123 /*------------------------------------------------------------------.
 124 | Create a new state with ACCESSING_SYMBOL, for those items.  Store |
 125 | it in the state hash table.                                       |
 126 `------------------------------------------------------------------*/
 127
 128 state *
 129 state_new (symbol_number accessing_symbol,
 130            size_t nitems, item_number *core)
 131 {
 132   state *res;
 133   size_t items_size = nitems * sizeof *core;
 134
 135   if (STATE_NUMBER_MAXIMUM <= nstates)
 136     abort ();
 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->consistent = 0;
 145   res->solved_conflicts = NULL;
 146
 147   res->nitems = nitems;
 148   memcpy (res->items, core, items_size);
 149
 150   state_hash_insert (res);
 151
 152   return res;
 153 }
 154
 155
 156 /*---------.
 157 | Free S.  |
 158 `---------*/
 159
 160 static void
 161 state_free (state *s)
 162 {
 163   free (s->transitions);
 164   free (s->reductions);
 165   free (s->errs);
 166   free (s);
 167 }
 168
 169
 170 /*---------------------------.
 171 | Set the transitions of S.  |
 172 `---------------------------*/
 173
 174 void
 175 state_transitions_set (state *s, int num, state **trans)
 176 {
 177   assert (!s->transitions);
 178   s->transitions = transitions_new (num, trans);
 179 }
 180
 181
 182 /*--------------------------.
 183 | Set the reductions of S.  |
 184 `--------------------------*/
 185
 186 void
 187 state_reductions_set (state *s, int num, rule **reds)
 188 {
 189   assert (!s->reductions);
 190   s->reductions = reductions_new (num, reds);
 191 }
 192
 193
 194 int
 195 state_reduction_find (state *s, rule *r)
 196 {
 197   int i;
 198   reductions *reds = s->reductions;
 199   for (i = 0; i < reds->num; ++i)
 200     if (reds->rules[i] == r)
 201       return i;
 202   return -1;
 203 }
 204
 205
 206 /*--------------------.
 207 | Set the errs of S.  |
 208 `--------------------*/
 209
 210 void
 211 state_errs_set (state *s, int num, symbol **tokens)
 212 {
 213   if (s->errs)
 214     abort ();
 215   s->errs = errs_new (num, tokens);
 216 }
 217
 218
 219
 220 /*---------------------------------------------------.
 221 | Print on OUT all the look-ahead tokens such that S |
 222 | wants to reduce R.                                 |
 223 `---------------------------------------------------*/
 224
 225 void
 226 state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out)
 227 {
 228   /* Find the reduction we are handling.  */
 229   reductions *reds = s->reductions;
 230   int red = state_reduction_find (s, r);
 231
 232   /* Print them if there are.  */
 233   if (reds->look_ahead_tokens && red != -1)
 234     {
 235       bitset_iterator biter;
 236       int k;
 237       char const *sep = "";
 238       fprintf (out, "  [");
 239       BITSET_FOR_EACH (biter, reds->look_ahead_tokens[red], k, 0)
 240         {
 241           fprintf (out, "%s%s", sep, symbols[k]->tag);
 242           sep = ", ";
 243         }
 244       fprintf (out, "]");
 245     }
 246 }
 247
 248
 249 /*---------------------.
 250 | A state hash table.  |
 251 `---------------------*/
 252
 253 /* Initial capacity of states hash table.  */
 254 #define HT_INITIAL_CAPACITY 257
 255
 256 static struct hash_table *state_table = NULL;
 257
 258 /* Two states are equal if they have the same core items.  */
 259 static inline bool
 260 state_compare (state const *s1, state const *s2)
 261 {
 262   size_t i;
 263
 264   if (s1->nitems != s2->nitems)
 265     return false;
 266
 267   for (i = 0; i < s1->nitems; ++i)
 268     if (s1->items[i] != s2->items[i])
 269       return false;
 270
 271   return true;
 272 }
 273
 274 static bool
 275 state_comparator (void const *s1, void const *s2)
 276 {
 277   return state_compare (s1, s2);
 278 }
 279
 280 static inline size_t
 281 state_hash (state const *s, size_t tablesize)
 282 {
 283   /* Add up the state's item numbers to get a hash key.  */
 284   size_t key = 0;
 285   size_t i;
 286   for (i = 0; i < s->nitems; ++i)
 287     key += s->items[i];
 288   return key % tablesize;
 289 }
 290
 291 static size_t
 292 state_hasher (void const *s, size_t tablesize)
 293 {
 294   return state_hash (s, tablesize);
 295 }
 296
 297
 298 /*-------------------------------.
 299 | Create the states hash table.  |
 300 `-------------------------------*/
 301
 302 void
 303 state_hash_new (void)
 304 {
 305   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 306                                  NULL,
 307                                  state_hasher,
 308                                  state_comparator,
 309                                  NULL);
 310 }
 311
 312
 313 /*---------------------------------------------.
 314 | Free the states hash table, not the states.  |
 315 `---------------------------------------------*/
 316
 317 void
 318 state_hash_free (void)
 319 {
 320   hash_free (state_table);
 321 }
 322
 323
 324 /*-----------------------------------.
 325 | Insert S in the state hash table.  |
 326 `-----------------------------------*/
 327
 328 void
 329 state_hash_insert (state *s)
 330 {
 331   hash_insert (state_table, s);
 332 }
 333
 334
 335 /*------------------------------------------------------------------.
 336 | Find the state associated to the CORE, and return it.  If it does |
 337 | not exist yet, return NULL.                                       |
 338 `------------------------------------------------------------------*/
 339
 340 state *
 341 state_hash_lookup (size_t nitems, item_number *core)
 342 {
 343   size_t items_size = nitems * sizeof *core;
 344   state *probe = xmalloc (offsetof (state, items) + items_size);
 345   state *entry;
 346
 347   probe->nitems = nitems;
 348   memcpy (probe->items, core, items_size);
 349   entry = hash_lookup (state_table, probe);
 350   free (probe);
 351   return entry;
 352 }
 353
 354 /* All the decorated states, indexed by the state number.  */
 355 state **states = NULL;
 356
 357
 358 /*----------------------.
 359 | Free all the states.  |
 360 `----------------------*/
 361
 362 void
 363 states_free (void)
 364 {
 365   state_number i;
 366   for (i = 0; i < nstates; ++i)
 367     state_free (states[i]);
 368   free (states);
 369 }