src/state.c

   1 /* Type definitions for nondeterministic finite state machine for Bison.
   2
   3    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 Free
   4    Software 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 #include "print-xml.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++)
  62     {
  63       aver (j < shifts->num);
  64       if (TRANSITION_SYMBOL (shifts, j) == sym)
  65         return shifts->states[j];
  66     }
  67 }
  68
  69
  70                         /*--------------------.
  71                         | Error transitions.  |
  72                         `--------------------*/
  73
  74
  75 /*---------------------------------.
  76 | Create a new array of NUM errs.  |
  77 `---------------------------------*/
  78
  79 errs *
  80 errs_new (int num, symbol **tokens)
  81 {
  82   size_t symbols_size = num * sizeof *tokens;
  83   errs *res = xmalloc (offsetof (errs, symbols) + symbols_size);
  84   res->num = num;
  85   memcpy (res->symbols, tokens, symbols_size);
  86   return res;
  87 }
  88
  89
  90
  91
  92                         /*-------------.
  93                         | Reductions.  |
  94                         `-------------*/
  95
  96
  97 /*---------------------------------------.
  98 | Create a new array of NUM reductions.  |
  99 `---------------------------------------*/
 100
 101 static reductions *
 102 reductions_new (int num, rule **reds)
 103 {
 104   size_t rules_size = num * sizeof *reds;
 105   reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);
 106   res->num = num;
 107   res->lookahead_tokens = NULL;
 108   memcpy (res->rules, reds, rules_size);
 109   return res;
 110 }
 111
 112
 113
 114                         /*---------.
 115                         | States.  |
 116                         `---------*/
 117
 118
 119 state_number nstates = 0;
 120 /* FINAL_STATE is properly set by new_state when it recognizes its
 121    accessing symbol: $end.  */
 122 state *final_state = NULL;
 123
 124
 125 /*------------------------------------------------------------------.
 126 | Create a new state with ACCESSING_SYMBOL, for those items.  Store |
 127 | it in the state hash table.                                       |
 128 `------------------------------------------------------------------*/
 129
 130 state *
 131 state_new (symbol_number accessing_symbol,
 132            size_t nitems, item_number *core)
 133 {
 134   state *res;
 135   size_t items_size = nitems * sizeof *core;
 136
 137   aver (nstates < STATE_NUMBER_MAXIMUM);
 138
 139   res = xmalloc (offsetof (state, items) + items_size);
 140   res->number = nstates++;
 141   res->accessing_symbol = accessing_symbol;
 142   res->transitions = NULL;
 143   res->reductions = NULL;
 144   res->errs = 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
 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 void
 250 state_rule_lookahead_tokens_print_xml (state *s, rule *r,
 251                                        FILE *out, int level)
 252 {
 253   /* Find the reduction we are handling.  */
 254   reductions *reds = s->reductions;
 255   int red = state_reduction_find (s, r);
 256
 257   /* Print them if there are.  */
 258   if (reds->lookahead_tokens && red != -1)
 259     {
 260       bitset_iterator biter;
 261       int k;
 262       xml_puts (out, level, "<lookaheads>");
 263       BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
 264         {
 265           xml_printf (out, level + 1, "<symbol>%s</symbol>",
 266                       xml_escape (symbols[k]->tag));
 267         }
 268       xml_puts (out, level, "</lookaheads>");
 269     }
 270 }
 271
 272
 273 /*---------------------.
 274 | A state hash table.  |
 275 `---------------------*/
 276
 277 /* Initial capacity of states hash table.  */
 278 #define HT_INITIAL_CAPACITY 257
 279
 280 static struct hash_table *state_table = NULL;
 281
 282 /* Two states are equal if they have the same core items.  */
 283 static inline bool
 284 state_compare (state const *s1, state const *s2)
 285 {
 286   size_t i;
 287
 288   if (s1->nitems != s2->nitems)
 289     return false;
 290
 291   for (i = 0; i < s1->nitems; ++i)
 292     if (s1->items[i] != s2->items[i])
 293       return false;
 294
 295   return true;
 296 }
 297
 298 static bool
 299 state_comparator (void const *s1, void const *s2)
 300 {
 301   return state_compare (s1, s2);
 302 }
 303
 304 static inline size_t
 305 state_hash (state const *s, size_t tablesize)
 306 {
 307   /* Add up the state's item numbers to get a hash key.  */
 308   size_t key = 0;
 309   size_t i;
 310   for (i = 0; i < s->nitems; ++i)
 311     key += s->items[i];
 312   return key % tablesize;
 313 }
 314
 315 static size_t
 316 state_hasher (void const *s, size_t tablesize)
 317 {
 318   return state_hash (s, tablesize);
 319 }
 320
 321
 322 /*-------------------------------.
 323 | Create the states hash table.  |
 324 `-------------------------------*/
 325
 326 void
 327 state_hash_new (void)
 328 {
 329   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 330                                  NULL,
 331                                  state_hasher,
 332                                  state_comparator,
 333                                  NULL);
 334 }
 335
 336
 337 /*---------------------------------------------.
 338 | Free the states hash table, not the states.  |
 339 `---------------------------------------------*/
 340
 341 void
 342 state_hash_free (void)
 343 {
 344   hash_free (state_table);
 345 }
 346
 347
 348 /*-----------------------------------.
 349 | Insert S in the state hash table.  |
 350 `-----------------------------------*/
 351
 352 void
 353 state_hash_insert (state *s)
 354 {
 355   if (!hash_insert (state_table, s))
 356     xalloc_die ();
 357 }
 358
 359
 360 /*------------------------------------------------------------------.
 361 | Find the state associated to the CORE, and return it.  If it does |
 362 | not exist yet, return NULL.                                       |
 363 `------------------------------------------------------------------*/
 364
 365 state *
 366 state_hash_lookup (size_t nitems, item_number *core)
 367 {
 368   size_t items_size = nitems * sizeof *core;
 369   state *probe = xmalloc (offsetof (state, items) + items_size);
 370   state *entry;
 371
 372   probe->nitems = nitems;
 373   memcpy (probe->items, core, items_size);
 374   entry = hash_lookup (state_table, probe);
 375   free (probe);
 376   return entry;
 377 }
 378
 379
 380 /*--------------------------------------------------------.
 381 | Record S and all states reachable from S in REACHABLE.  |
 382 `--------------------------------------------------------*/
 383
 384 static void
 385 state_record_reachable_states (state *s, bitset reachable)
 386 {
 387   if (bitset_test (reachable, s->number))
 388     return;
 389   bitset_set (reachable, s->number);
 390   {
 391     int i;
 392     for (i = 0; i < s->transitions->num; ++i)
 393       if (!TRANSITION_IS_DISABLED (s->transitions, i))
 394         state_record_reachable_states (s->transitions->states[i], reachable);
 395   }
 396 }
 397
 398 void
 399 state_remove_unreachable_states (state_number old_to_new[])
 400 {
 401   state_number nstates_reachable = 0;
 402   bitset reachable = bitset_create (nstates, BITSET_FIXED);
 403   state_record_reachable_states (states[0], reachable);
 404   {
 405     state_number i;
 406     for (i = 0; i < nstates; ++i)
 407       {
 408         if (bitset_test (reachable, states[i]->number))
 409           {
 410             states[nstates_reachable] = states[i];
 411             states[nstates_reachable]->number = nstates_reachable;
 412             old_to_new[i] = nstates_reachable++;
 413           }
 414         else
 415           {
 416             state_free (states[i]);
 417             old_to_new[i] = nstates;
 418           }
 419       }
 420   }
 421   nstates = nstates_reachable;
 422   bitset_free (reachable);
 423 }
 424
 425 /* All the decorated states, indexed by the state number.  */
 426 state **states = NULL;
 427
 428
 429 /*----------------------.
 430 | Free all the states.  |
 431 `----------------------*/
 432
 433 void
 434 states_free (void)
 435 {
 436   state_number i;
 437   for (i = 0; i < nstates; ++i)
 438     state_free (states[i]);
 439   free (states);
 440 }