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 #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       char const *sep = "";
 263       xml_puts (out, level, "<lookaheads>");
 264       BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
 265         {
 266           xml_printf (out, level + 1, "<symbol class=\"%s\">%s</symbol>",
 267                       symbol_class_get_string (symbols[k]),
 268                       xml_escape (symbols[k]->tag));
 269         }
 270       xml_puts (out, level, "</lookaheads>");
 271     }
 272 }
 273
 274
 275 /*---------------------.
 276 | A state hash table.  |
 277 `---------------------*/
 278
 279 /* Initial capacity of states hash table.  */
 280 #define HT_INITIAL_CAPACITY 257
 281
 282 static struct hash_table *state_table = NULL;
 283
 284 /* Two states are equal if they have the same core items.  */
 285 static inline bool
 286 state_compare (state const *s1, state const *s2)
 287 {
 288   size_t i;
 289
 290   if (s1->nitems != s2->nitems)
 291     return false;
 292
 293   for (i = 0; i < s1->nitems; ++i)
 294     if (s1->items[i] != s2->items[i])
 295       return false;
 296
 297   return true;
 298 }
 299
 300 static bool
 301 state_comparator (void const *s1, void const *s2)
 302 {
 303   return state_compare (s1, s2);
 304 }
 305
 306 static inline size_t
 307 state_hash (state const *s, size_t tablesize)
 308 {
 309   /* Add up the state's item numbers to get a hash key.  */
 310   size_t key = 0;
 311   size_t i;
 312   for (i = 0; i < s->nitems; ++i)
 313     key += s->items[i];
 314   return key % tablesize;
 315 }
 316
 317 static size_t
 318 state_hasher (void const *s, size_t tablesize)
 319 {
 320   return state_hash (s, tablesize);
 321 }
 322
 323
 324 /*-------------------------------.
 325 | Create the states hash table.  |
 326 `-------------------------------*/
 327
 328 void
 329 state_hash_new (void)
 330 {
 331   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 332                                  NULL,
 333                                  state_hasher,
 334                                  state_comparator,
 335                                  NULL);
 336 }
 337
 338
 339 /*---------------------------------------------.
 340 | Free the states hash table, not the states.  |
 341 `---------------------------------------------*/
 342
 343 void
 344 state_hash_free (void)
 345 {
 346   hash_free (state_table);
 347 }
 348
 349
 350 /*-----------------------------------.
 351 | Insert S in the state hash table.  |
 352 `-----------------------------------*/
 353
 354 void
 355 state_hash_insert (state *s)
 356 {
 357   hash_insert (state_table, s);
 358 }
 359
 360
 361 /*------------------------------------------------------------------.
 362 | Find the state associated to the CORE, and return it.  If it does |
 363 | not exist yet, return NULL.                                       |
 364 `------------------------------------------------------------------*/
 365
 366 state *
 367 state_hash_lookup (size_t nitems, item_number *core)
 368 {
 369   size_t items_size = nitems * sizeof *core;
 370   state *probe = xmalloc (offsetof (state, items) + items_size);
 371   state *entry;
 372
 373   probe->nitems = nitems;
 374   memcpy (probe->items, core, items_size);
 375   entry = hash_lookup (state_table, probe);
 376   free (probe);
 377   return entry;
 378 }
 379
 380
 381 /*--------------------------------------------------------.
 382 | Record S and all states reachable from S in REACHABLE.  |
 383 `--------------------------------------------------------*/
 384
 385 static void
 386 state_record_reachable_states (state *s, bitset reachable)
 387 {
 388   if (bitset_test (reachable, s->number))
 389     return;
 390   bitset_set (reachable, s->number);
 391   {
 392     int i;
 393     for (i = 0; i < s->transitions->num; ++i)
 394       if (!TRANSITION_IS_DISABLED (s->transitions, i))
 395         state_record_reachable_states (s->transitions->states[i], reachable);
 396   }
 397 }
 398
 399 void
 400 state_remove_unreachable_states (state_number old_to_new[])
 401 {
 402   state_number nstates_reachable = 0;
 403   bitset reachable = bitset_create (nstates, BITSET_FIXED);
 404   state_record_reachable_states (states[0], reachable);
 405   {
 406     state_number i;
 407     for (i = 0; i < nstates; ++i)
 408       {
 409         if (bitset_test (reachable, states[i]->number))
 410           {
 411             states[nstates_reachable] = states[i];
 412             states[nstates_reachable]->number = nstates_reachable;
 413             old_to_new[i] = nstates_reachable++;
 414           }
 415         else
 416           {
 417             state_free (states[i]);
 418             old_to_new[i] = nstates;
 419           }
 420       }
 421   }
 422   nstates = nstates_reachable;
 423   bitset_free (reachable);
 424 }
 425
 426 /* All the decorated states, indexed by the state number.  */
 427 state **states = NULL;
 428
 429
 430 /*----------------------.
 431 | Free all the states.  |
 432 `----------------------*/
 433
 434 void
 435 states_free (void)
 436 {
 437   state_number i;
 438   for (i = 0; i < nstates; ++i)
 439     state_free (states[i]);
 440   free (states);
 441 }