src/state.c

   1 /* Type definitions for nondeterministic finite state machine for Bison.
   2
   3    Copyright (C) 2001-2007, 2009-2010 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
  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   res->solved_conflicts_xml = NULL;
 147
 148   res->nitems = nitems;
 149   memcpy (res->items, core, items_size);
 150
 151   state_hash_insert (res);
 152
 153   return res;
 154 }
 155
 156
 157 /*---------.
 158 | Free S.  |
 159 `---------*/
 160
 161 static void
 162 state_free (state *s)
 163 {
 164   free (s->transitions);
 165   free (s->reductions);
 166   free (s->errs);
 167   free (s);
 168 }
 169
 170
 171 /*---------------------------.
 172 | Set the transitions of S.  |
 173 `---------------------------*/
 174
 175 void
 176 state_transitions_set (state *s, int num, state **trans)
 177 {
 178   aver (!s->transitions);
 179   s->transitions = transitions_new (num, trans);
 180 }
 181
 182
 183 /*--------------------------.
 184 | Set the reductions of S.  |
 185 `--------------------------*/
 186
 187 void
 188 state_reductions_set (state *s, int num, rule **reds)
 189 {
 190   aver (!s->reductions);
 191   s->reductions = reductions_new (num, reds);
 192 }
 193
 194
 195 int
 196 state_reduction_find (state *s, rule *r)
 197 {
 198   int i;
 199   reductions *reds = s->reductions;
 200   for (i = 0; i < reds->num; ++i)
 201     if (reds->rules[i] == r)
 202       return i;
 203   return -1;
 204 }
 205
 206
 207 /*--------------------.
 208 | Set the errs of S.  |
 209 `--------------------*/
 210
 211 void
 212 state_errs_set (state *s, int num, symbol **tokens)
 213 {
 214   aver (!s->errs);
 215   s->errs = errs_new (num, tokens);
 216 }
 217
 218
 219
 220 /*--------------------------------------------------.
 221 | Print on OUT all the lookahead tokens such that S |
 222 | wants to reduce R.                                |
 223 `--------------------------------------------------*/
 224
 225 void
 226 state_rule_lookahead_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->lookahead_tokens && red != -1)
 234     {
 235       bitset_iterator biter;
 236       int k;
 237       char const *sep = "";
 238       fprintf (out, "  [");
 239       BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
 240         {
 241           fprintf (out, "%s%s", sep, symbols[k]->tag);
 242           sep = ", ";
 243         }
 244       fprintf (out, "]");
 245     }
 246 }
 247
 248 void
 249 state_rule_lookahead_tokens_print_xml (state *s, rule *r,
 250                                        FILE *out, int level)
 251 {
 252   /* Find the reduction we are handling.  */
 253   reductions *reds = s->reductions;
 254   int red = state_reduction_find (s, r);
 255
 256   /* Print them if there are.  */
 257   if (reds->lookahead_tokens && red != -1)
 258     {
 259       bitset_iterator biter;
 260       int k;
 261       xml_puts (out, level, "<lookaheads>");
 262       BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
 263         {
 264           xml_printf (out, level + 1, "<symbol>%s</symbol>",
 265                       xml_escape (symbols[k]->tag));
 266         }
 267       xml_puts (out, level, "</lookaheads>");
 268     }
 269 }
 270
 271
 272 /*---------------------.
 273 | A state hash table.  |
 274 `---------------------*/
 275
 276 /* Initial capacity of states hash table.  */
 277 #define HT_INITIAL_CAPACITY 257
 278
 279 static struct hash_table *state_table = NULL;
 280
 281 /* Two states are equal if they have the same core items.  */
 282 static inline bool
 283 state_compare (state const *s1, state const *s2)
 284 {
 285   size_t i;
 286
 287   if (s1->nitems != s2->nitems)
 288     return false;
 289
 290   for (i = 0; i < s1->nitems; ++i)
 291     if (s1->items[i] != s2->items[i])
 292       return false;
 293
 294   return true;
 295 }
 296
 297 static bool
 298 state_comparator (void const *s1, void const *s2)
 299 {
 300   return state_compare (s1, s2);
 301 }
 302
 303 static inline size_t
 304 state_hash (state const *s, size_t tablesize)
 305 {
 306   /* Add up the state's item numbers to get a hash key.  */
 307   size_t key = 0;
 308   size_t i;
 309   for (i = 0; i < s->nitems; ++i)
 310     key += s->items[i];
 311   return key % tablesize;
 312 }
 313
 314 static size_t
 315 state_hasher (void const *s, size_t tablesize)
 316 {
 317   return state_hash (s, tablesize);
 318 }
 319
 320
 321 /*-------------------------------.
 322 | Create the states hash table.  |
 323 `-------------------------------*/
 324
 325 void
 326 state_hash_new (void)
 327 {
 328   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 329                                  NULL,
 330                                  state_hasher,
 331                                  state_comparator,
 332                                  NULL);
 333 }
 334
 335
 336 /*---------------------------------------------.
 337 | Free the states hash table, not the states.  |
 338 `---------------------------------------------*/
 339
 340 void
 341 state_hash_free (void)
 342 {
 343   hash_free (state_table);
 344 }
 345
 346
 347 /*-----------------------------------.
 348 | Insert S in the state hash table.  |
 349 `-----------------------------------*/
 350
 351 void
 352 state_hash_insert (state *s)
 353 {
 354   if (!hash_insert (state_table, s))
 355     xalloc_die ();
 356 }
 357
 358
 359 /*------------------------------------------------------------------.
 360 | Find the state associated to the CORE, and return it.  If it does |
 361 | not exist yet, return NULL.                                       |
 362 `------------------------------------------------------------------*/
 363
 364 state *
 365 state_hash_lookup (size_t nitems, item_number *core)
 366 {
 367   size_t items_size = nitems * sizeof *core;
 368   state *probe = xmalloc (offsetof (state, items) + items_size);
 369   state *entry;
 370
 371   probe->nitems = nitems;
 372   memcpy (probe->items, core, items_size);
 373   entry = hash_lookup (state_table, probe);
 374   free (probe);
 375   return entry;
 376 }
 377
 378
 379 /*--------------------------------------------------------.
 380 | Record S and all states reachable from S in REACHABLE.  |
 381 `--------------------------------------------------------*/
 382
 383 static void
 384 state_record_reachable_states (state *s, bitset reachable)
 385 {
 386   if (bitset_test (reachable, s->number))
 387     return;
 388   bitset_set (reachable, s->number);
 389   {
 390     int i;
 391     for (i = 0; i < s->transitions->num; ++i)
 392       if (!TRANSITION_IS_DISABLED (s->transitions, i))
 393         state_record_reachable_states (s->transitions->states[i], reachable);
 394   }
 395 }
 396
 397 void
 398 state_remove_unreachable_states (state_number old_to_new[])
 399 {
 400   state_number nstates_reachable = 0;
 401   bitset reachable = bitset_create (nstates, BITSET_FIXED);
 402   state_record_reachable_states (states[0], reachable);
 403   {
 404     state_number i;
 405     for (i = 0; i < nstates; ++i)
 406       {
 407         if (bitset_test (reachable, states[i]->number))
 408           {
 409             states[nstates_reachable] = states[i];
 410             states[nstates_reachable]->number = nstates_reachable;
 411             old_to_new[i] = nstates_reachable++;
 412           }
 413         else
 414           {
 415             state_free (states[i]);
 416             old_to_new[i] = nstates;
 417           }
 418       }
 419   }
 420   nstates = nstates_reachable;
 421   bitset_free (reachable);
 422 }
 423
 424 /* All the decorated states, indexed by the state number.  */
 425 state **states = NULL;
 426
 427
 428 /*----------------------.
 429 | Free all the states.  |
 430 `----------------------*/
 431
 432 void
 433 states_free (void)
 434 {
 435   state_number i;
 436   for (i = 0; i < nstates; ++i)
 437     state_free (states[i]);
 438   free (states);
 439 }