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