src/state.c

   1 /* Type definitions for nondeterministic finite state machine for Bison.
   2
   3    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 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       if (shifts->num <= j)
  65         abort ();
  66       if (TRANSITION_SYMBOL (shifts, j) == sym)
  67         return shifts->states[j];
  68     }
  69 }
  70
  71
  72                         /*--------------------.
  73                         | Error transitions.  |
  74                         `--------------------*/
  75
  76
  77 /*---------------------------------.
  78 | Create a new array of NUM errs.  |
  79 `---------------------------------*/
  80
  81 errs *
  82 errs_new (int num, symbol **tokens)
  83 {
  84   size_t symbols_size = num * sizeof *tokens;
  85   errs *res = xmalloc (offsetof (errs, symbols) + symbols_size);
  86   res->num = num;
  87   memcpy (res->symbols, tokens, symbols_size);
  88   return res;
  89 }
  90
  91
  92
  93
  94                         /*-------------.
  95                         | Reductions.  |
  96                         `-------------*/
  97
  98
  99 /*---------------------------------------.
 100 | Create a new array of NUM reductions.  |
 101 `---------------------------------------*/
 102
 103 static reductions *
 104 reductions_new (int num, rule **reds)
 105 {
 106   size_t rules_size = num * sizeof *reds;
 107   reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);
 108   res->num = num;
 109   res->look_ahead_tokens = NULL;
 110   memcpy (res->rules, reds, rules_size);
 111   return res;
 112 }
 113
 114
 115
 116                         /*---------.
 117                         | States.  |
 118                         `---------*/
 119
 120
 121 state_number nstates = 0;
 122 /* FINAL_STATE is properly set by new_state when it recognizes its
 123    accessing symbol: $end.  */
 124 state *final_state = NULL;
 125
 126
 127 /*------------------------------------------------------------------.
 128 | Create a new state with ACCESSING_SYMBOL, for those items.  Store |
 129 | it in the state hash table.                                       |
 130 `------------------------------------------------------------------*/
 131
 132 state *
 133 state_new (symbol_number accessing_symbol,
 134            size_t nitems, item_number *core)
 135 {
 136   state *res;
 137   size_t items_size = nitems * sizeof *core;
 138
 139   if (STATE_NUMBER_MAXIMUM <= nstates)
 140     abort ();
 141
 142   res = xmalloc (offsetof (state, items) + items_size);
 143   res->number = nstates++;
 144   res->accessing_symbol = accessing_symbol;
 145   res->transitions = NULL;
 146   res->reductions = NULL;
 147   res->errs = NULL;
 148   res->consistent = 0;
 149   res->solved_conflicts = NULL;
 150
 151   res->nitems = nitems;
 152   memcpy (res->items, core, items_size);
 153
 154   state_hash_insert (res);
 155
 156   return res;
 157 }
 158
 159
 160 /*---------.
 161 | Free S.  |
 162 `---------*/
 163
 164 static void
 165 state_free (state *s)
 166 {
 167   free (s->transitions);
 168   free (s->reductions);
 169   free (s->errs);
 170   free (s);
 171 }
 172
 173
 174 /*---------------------------.
 175 | Set the transitions of S.  |
 176 `---------------------------*/
 177
 178 void
 179 state_transitions_set (state *s, int num, state **trans)
 180 {
 181   assert (!s->transitions);
 182   s->transitions = transitions_new (num, trans);
 183 }
 184
 185
 186 /*--------------------------.
 187 | Set the reductions of S.  |
 188 `--------------------------*/
 189
 190 void
 191 state_reductions_set (state *s, int num, rule **reds)
 192 {
 193   assert (!s->reductions);
 194   s->reductions = reductions_new (num, reds);
 195 }
 196
 197
 198 int
 199 state_reduction_find (state *s, rule *r)
 200 {
 201   int i;
 202   reductions *reds = s->reductions;
 203   for (i = 0; i < reds->num; ++i)
 204     if (reds->rules[i] == r)
 205       return i;
 206   return -1;
 207 }
 208
 209
 210 /*--------------------.
 211 | Set the errs of S.  |
 212 `--------------------*/
 213
 214 void
 215 state_errs_set (state *s, int num, symbol **tokens)
 216 {
 217   if (s->errs)
 218     abort ();
 219   s->errs = errs_new (num, tokens);
 220 }
 221
 222
 223
 224 /*---------------------------------------------------.
 225 | Print on OUT all the look-ahead tokens such that S |
 226 | wants to reduce R.                                 |
 227 `---------------------------------------------------*/
 228
 229 void
 230 state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out)
 231 {
 232   /* Find the reduction we are handling.  */
 233   reductions *reds = s->reductions;
 234   int red = state_reduction_find (s, r);
 235
 236   /* Print them if there are.  */
 237   if (reds->look_ahead_tokens && red != -1)
 238     {
 239       bitset_iterator biter;
 240       int k;
 241       char const *sep = "";
 242       fprintf (out, "  [");
 243       BITSET_FOR_EACH (biter, reds->look_ahead_tokens[red], k, 0)
 244         {
 245           fprintf (out, "%s%s", sep, symbols[k]->tag);
 246           sep = ", ";
 247         }
 248       fprintf (out, "]");
 249     }
 250 }
 251
 252
 253 /*---------------------.
 254 | A state hash table.  |
 255 `---------------------*/
 256
 257 /* Initial capacity of states hash table.  */
 258 #define HT_INITIAL_CAPACITY 257
 259
 260 static struct hash_table *state_table = NULL;
 261
 262 /* Two states are equal if they have the same core items.  */
 263 static inline bool
 264 state_compare (state const *s1, state const *s2)
 265 {
 266   size_t i;
 267
 268   if (s1->nitems != s2->nitems)
 269     return false;
 270
 271   for (i = 0; i < s1->nitems; ++i)
 272     if (s1->items[i] != s2->items[i])
 273       return false;
 274
 275   return true;
 276 }
 277
 278 static bool
 279 state_comparator (void const *s1, void const *s2)
 280 {
 281   return state_compare (s1, s2);
 282 }
 283
 284 static inline size_t
 285 state_hash (state const *s, size_t tablesize)
 286 {
 287   /* Add up the state's item numbers to get a hash key.  */
 288   size_t key = 0;
 289   size_t i;
 290   for (i = 0; i < s->nitems; ++i)
 291     key += s->items[i];
 292   return key % tablesize;
 293 }
 294
 295 static size_t
 296 state_hasher (void const *s, size_t tablesize)
 297 {
 298   return state_hash (s, tablesize);
 299 }
 300
 301
 302 /*-------------------------------.
 303 | Create the states hash table.  |
 304 `-------------------------------*/
 305
 306 void
 307 state_hash_new (void)
 308 {
 309   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 310                                  NULL,
 311                                  state_hasher,
 312                                  state_comparator,
 313                                  NULL);
 314 }
 315
 316
 317 /*---------------------------------------------.
 318 | Free the states hash table, not the states.  |
 319 `---------------------------------------------*/
 320
 321 void
 322 state_hash_free (void)
 323 {
 324   hash_free (state_table);
 325 }
 326
 327
 328 /*-----------------------------------.
 329 | Insert S in the state hash table.  |
 330 `-----------------------------------*/
 331
 332 void
 333 state_hash_insert (state *s)
 334 {
 335   hash_insert (state_table, s);
 336 }
 337
 338
 339 /*------------------------------------------------------------------.
 340 | Find the state associated to the CORE, and return it.  If it does |
 341 | not exist yet, return NULL.                                       |
 342 `------------------------------------------------------------------*/
 343
 344 state *
 345 state_hash_lookup (size_t nitems, item_number *core)
 346 {
 347   size_t items_size = nitems * sizeof *core;
 348   state *probe = xmalloc (offsetof (state, items) + items_size);
 349   state *entry;
 350
 351   probe->nitems = nitems;
 352   memcpy (probe->items, core, items_size);
 353   entry = hash_lookup (state_table, probe);
 354   free (probe);
 355   return entry;
 356 }
 357
 358 /* All the decorated states, indexed by the state number.  */
 359 state **states = NULL;
 360
 361
 362 /*----------------------.
 363 | Free all the states.  |
 364 `----------------------*/
 365
 366 void
 367 states_free (void)
 368 {
 369   state_number i;
 370   for (i = 0; i < nstates; ++i)
 371     state_free (states[i]);
 372   free (states);
 373 }