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