src/state.c

   1 /* Type definitions for nondeterministic finite state machine for Bison.
   2
   3    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 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 "system.h"
  23
  24 #include <hash.h>
  25
  26 #include "complain.h"
  27 #include "gram.h"
  28 #include "state.h"
  29
  30
  31                         /*-------------------.
  32                         | Shifts and Gotos.  |
  33                         `-------------------*/
  34
  35
  36 /*-----------------------------------------.
  37 | Create a new array of NUM shifts/gotos.  |
  38 `-----------------------------------------*/
  39
  40 static transitions *
  41 transitions_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
  56 state *
  57 transitions_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
  78 errs *
  79 errs_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
 100 static reductions *
 101 reductions_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
 118 state_number nstates = 0;
 119 /* FINAL_STATE is properly set by new_state when it recognizes its
 120    accessing symbol: $end.  */
 121 state *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
 129 state *
 130 state_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->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   aver (!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   aver (!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   aver (!s->errs);
 214   s->errs = errs_new (num, tokens);
 215 }
 216
 217
 218
 219 /*--------------------------------------------------.
 220 | Print on OUT all the lookahead tokens such that S |
 221 | wants to reduce R.                                |
 222 `--------------------------------------------------*/
 223
 224 void
 225 state_rule_lookahead_tokens_print (state *s, rule *r, FILE *out)
 226 {
 227   /* Find the reduction we are handling.  */
 228   reductions *reds = s->reductions;
 229   int red = state_reduction_find (s, r);
 230
 231   /* Print them if there are.  */
 232   if (reds->lookahead_tokens && red != -1)
 233     {
 234       bitset_iterator biter;
 235       int k;
 236       char const *sep = "";
 237       fprintf (out, "  [");
 238       BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
 239         {
 240           fprintf (out, "%s%s", sep, symbols[k]->tag);
 241           sep = ", ";
 242         }
 243       fprintf (out, "]");
 244     }
 245 }
 246
 247
 248 /*---------------------.
 249 | A state hash table.  |
 250 `---------------------*/
 251
 252 /* Initial capacity of states hash table.  */
 253 #define HT_INITIAL_CAPACITY 257
 254
 255 static struct hash_table *state_table = NULL;
 256
 257 /* Two states are equal if they have the same core items.  */
 258 static inline bool
 259 state_compare (state const *s1, state const *s2)
 260 {
 261   size_t i;
 262
 263   if (s1->nitems != s2->nitems)
 264     return false;
 265
 266   for (i = 0; i < s1->nitems; ++i)
 267     if (s1->items[i] != s2->items[i])
 268       return false;
 269
 270   return true;
 271 }
 272
 273 static bool
 274 state_comparator (void const *s1, void const *s2)
 275 {
 276   return state_compare (s1, s2);
 277 }
 278
 279 static inline size_t
 280 state_hash (state const *s, size_t tablesize)
 281 {
 282   /* Add up the state's item numbers to get a hash key.  */
 283   size_t key = 0;
 284   size_t i;
 285   for (i = 0; i < s->nitems; ++i)
 286     key += s->items[i];
 287   return key % tablesize;
 288 }
 289
 290 static size_t
 291 state_hasher (void const *s, size_t tablesize)
 292 {
 293   return state_hash (s, tablesize);
 294 }
 295
 296
 297 /*-------------------------------.
 298 | Create the states hash table.  |
 299 `-------------------------------*/
 300
 301 void
 302 state_hash_new (void)
 303 {
 304   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 305                                  NULL,
 306                                  state_hasher,
 307                                  state_comparator,
 308                                  NULL);
 309 }
 310
 311
 312 /*---------------------------------------------.
 313 | Free the states hash table, not the states.  |
 314 `---------------------------------------------*/
 315
 316 void
 317 state_hash_free (void)
 318 {
 319   hash_free (state_table);
 320 }
 321
 322
 323 /*-----------------------------------.
 324 | Insert S in the state hash table.  |
 325 `-----------------------------------*/
 326
 327 void
 328 state_hash_insert (state *s)
 329 {
 330   hash_insert (state_table, s);
 331 }
 332
 333
 334 /*------------------------------------------------------------------.
 335 | Find the state associated to the CORE, and return it.  If it does |
 336 | not exist yet, return NULL.                                       |
 337 `------------------------------------------------------------------*/
 338
 339 state *
 340 state_hash_lookup (size_t nitems, item_number *core)
 341 {
 342   size_t items_size = nitems * sizeof *core;
 343   state *probe = xmalloc (offsetof (state, items) + items_size);
 344   state *entry;
 345
 346   probe->nitems = nitems;
 347   memcpy (probe->items, core, items_size);
 348   entry = hash_lookup (state_table, probe);
 349   free (probe);
 350   return entry;
 351 }
 352
 353
 354 /*--------------------------------------------------------.
 355 | Record S and all states reachable from S in REACHABLE.  |
 356 `--------------------------------------------------------*/
 357
 358 static void
 359 state_record_reachable_states (state *s, bitset reachable)
 360 {
 361   if (bitset_test (reachable, s->number))
 362     return;
 363   bitset_set (reachable, s->number);
 364   {
 365     int i;
 366     for (i = 0; i < s->transitions->num; ++i)
 367       if (!TRANSITION_IS_DISABLED (s->transitions, i))
 368         state_record_reachable_states (s->transitions->states[i], reachable);
 369   }
 370 }
 371
 372 void
 373 state_remove_unreachable_states (state_number old_to_new[])
 374 {
 375   state_number nstates_reachable = 0;
 376   bitset reachable = bitset_create (nstates, BITSET_FIXED);
 377   state_record_reachable_states (states[0], reachable);
 378   {
 379     state_number i;
 380     for (i = 0; i < nstates; ++i)
 381       {
 382         if (bitset_test (reachable, states[i]->number))
 383           {
 384             states[nstates_reachable] = states[i];
 385             states[nstates_reachable]->number = nstates_reachable;
 386             old_to_new[i] = nstates_reachable++;
 387           }
 388         else
 389           {
 390             state_free (states[i]);
 391             old_to_new[i] = nstates;
 392           }
 393       }
 394   }
 395   nstates = nstates_reachable;
 396   bitset_free (reachable);
 397 }
 398
 399 /* All the decorated states, indexed by the state number.  */
 400 state **states = NULL;
 401
 402
 403 /*----------------------.
 404 | Free all the states.  |
 405 `----------------------*/
 406
 407 void
 408 states_free (void)
 409 {
 410   state_number i;
 411   for (i = 0; i < nstates; ++i)
 412     state_free (states[i]);
 413   free (states);
 414 }