* data/glr.c (yyexpandGLRStack): Declare only if defined.

[bison.git] / src / state.c

diff --git a/src/state.c b/src/state.c
index 846bdae503e835be780cbccee594a01bceb0487a..e78db69bd41545bed1b796d0b20076c48bfa9de6 100644 (file)
--- a/src/state.c
+++ b/src/state.c
@@ -1,5 +1,6 @@
-/* Type definitions for nondeterministic finite state machine for bison,
-   Copyright (C) 2001, 2002  Free Software Foundation, Inc.
+/* Type definitions for nondeterministic finite state machine for Bison.
+
+   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.

 
    This file is part of Bison, the GNU Compiler Compiler.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 


@@ -15,12 +16,14 @@
 
    You should have received a copy of the GNU General Public License
    along with Bison; see the file COPYING.  If not, write to
 
    You should have received a copy of the GNU General Public License
    along with Bison; see the file COPYING.  If not, write to

-   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-   Boston, MA 02111-1307, USA.  */
+   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+   Boston, MA 02110-1301, USA.  */

 
 
 #include "system.h"
 
 
 #include "system.h"

-#include "hash.h"
+
+#include <hash.h>
+

 #include "complain.h"
 #include "gram.h"
 #include "state.h"
 #include "complain.h"
 #include "gram.h"
 #include "state.h"


@@ -31,35 +34,32 @@
                        `-------------------*/
 
 
                        `-------------------*/
 
 

-/*---------------------------------------.
-| Create a new array of N shifts/gotos.  |
-`---------------------------------------*/
-
-#define TRANSITIONS_ALLOC(Num)                                         \
-  (transitions_t *) xcalloc ((sizeof (transitions_t)                   \
-                                  + (Num - 1) * sizeof (state_t *)), 1)
+/*-----------------------------------------.
+| Create a new array of NUM shifts/gotos.  |
+`-----------------------------------------*/

 
 

-static transitions_t *
-transitions_new (int num, state_t **the_states)
+static transitions *
+transitions_new (int num, state **the_states)

 {
 {

-  transitions_t *res = TRANSITIONS_ALLOC (num);
+  size_t states_size = num * sizeof *the_states;
+  transitions *res = xmalloc (offsetof (transitions, states) + states_size);

   res->num = num;
   res->num = num;

-  memcpy (res->states, the_states, num * sizeof (the_states[0]));
+  memcpy (res->states, the_states, states_size);

   return res;
 }
 
 
   return res;
 }
 
 

-/*-------------------------------------------------------------------.
-| Return the state such these TRANSITIONS contain a shift/goto to it |
-| on SYMBOL.  Aborts if none found.                                  |
-`-------------------------------------------------------------------*/
+/*-------------------------------------------------------.
+| Return the state such that SHIFTS contain a shift/goto |
+| to it on SYM.  Abort if none found.                    |
+`-------------------------------------------------------*/

 
 

-state_t *
-transitions_to (transitions_t *shifts, symbol_number_t s)
+state *
+transitions_to (transitions *shifts, symbol_number sym)

 {
   int j;
   for (j = 0; j < shifts->num; j++)
 {
   int j;
   for (j = 0; j < shifts->num; j++)

-    if (TRANSITION_SYMBOL (shifts, j) == s)
+    if (TRANSITION_SYMBOL (shifts, j) == sym)

       return shifts->states[j];
   abort ();
 }
       return shifts->states[j];
   abort ();
 }


@@ -70,21 +70,17 @@ transitions_to (transitions_t *shifts, symbol_number_t s)
                        `--------------------*/
 
 
                        `--------------------*/
 
 

-/*-------------------------------.
-| Create a new array of N errs.  |
-`-------------------------------*/
+/*---------------------------------.
+| Create a new array of NUM errs.  |
+`---------------------------------*/

 
 

-#define ERRS_ALLOC(Nerrs)                              \
-  (errs_t *) xcalloc ((sizeof (errs_t)                 \
-                      + (Nerrs - 1) * sizeof (symbol_t *)), 1)
-
-
-errs_t *
-errs_new (int num, symbol_t **tokens)
+errs *
+errs_new (int num, symbol **tokens)

 {
 {

-  errs_t *res = ERRS_ALLOC (num);
+  size_t symbols_size = num * sizeof *tokens;
+  errs *res = xmalloc (offsetof (errs, symbols) + symbols_size);

   res->num = num;
   res->num = num;

-  memcpy (res->symbols, tokens, num * sizeof (tokens[0]));
+  memcpy (res->symbols, tokens, symbols_size);

   return res;
 }
 
   return res;
 }
 


@@ -96,21 +92,18 @@ errs_new (int num, symbol_t **tokens)
                        `-------------*/
 
 
                        `-------------*/
 
 

-/*-------------------------------------.
-| Create a new array of N reductions.  |
-`-------------------------------------*/
-
-#define REDUCTIONS_ALLOC(Nreductions)                          \
-  (reductions_t *) xcalloc ((sizeof (reductions_t)             \
-                            + (Nreductions - 1) * sizeof (rule_t *)), 1)
+/*---------------------------------------.
+| Create a new array of NUM reductions.  |
+`---------------------------------------*/

 
 

-static reductions_t *
-reductions_new (int num, rule_t **reductions)
+static reductions *
+reductions_new (int num, rule **reds)

 {
 {

-  reductions_t *res = REDUCTIONS_ALLOC (num);
+  size_t rules_size = num * sizeof *reds;
+  reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);

   res->num = num;
   res->num = num;

-  memcpy (res->rules, reductions, num * sizeof (reductions[0]));
-  res->lookaheads = NULL;
+  res->look_ahead_tokens = NULL;
+  memcpy (res->rules, reds, rules_size);

   return res;
 }
 
   return res;
 }
 


@@ -121,36 +114,38 @@ reductions_new (int num, rule_t **reductions)
                        `---------*/
 
 
                        `---------*/
 
 

-state_number_t nstates = 0;
+state_number nstates = 0;

 /* FINAL_STATE is properly set by new_state when it recognizes its
    accessing symbol: $end.  */
 /* FINAL_STATE is properly set by new_state when it recognizes its
    accessing symbol: $end.  */

-state_t *final_state = NULL;
+state *final_state = NULL;

 
 

-#define STATE_ALLOC(Nitems)                                            \
-  (state_t *) xcalloc ((sizeof (state_t)                               \
-                       + (Nitems - 1) * sizeof (item_number_t)), 1)

 
 /*------------------------------------------------------------------.
 | Create a new state with ACCESSING_SYMBOL, for those items.  Store |
 | it in the state hash table.                                       |
 `------------------------------------------------------------------*/
 
 
 /*------------------------------------------------------------------.
 | Create a new state with ACCESSING_SYMBOL, for those items.  Store |
 | it in the state hash table.                                       |
 `------------------------------------------------------------------*/
 

-state_t *
-state_new (symbol_number_t accessing_symbol,
-          size_t core_size, item_number_t *core)
+state *
+state_new (symbol_number accessing_symbol,
+          size_t nitems, item_number *core)

 {
 {

-  state_t *res;
+  state *res;
+  size_t items_size = nitems * sizeof *core;

 
 

-  assert (nstates < STATE_NUMBER_MAX);
+  if (STATE_NUMBER_MAXIMUM <= nstates)
+    abort ();

 
 

-  res = STATE_ALLOC (core_size);
+  res = xmalloc (offsetof (state, items) + items_size);
+  res->number = nstates++;

   res->accessing_symbol = accessing_symbol;
   res->accessing_symbol = accessing_symbol;

-  res->number = nstates;
-  ++nstates;
+  res->transitions = NULL;
+  res->reductions = NULL;
+  res->errs = NULL;
+  res->consistent = 0;

   res->solved_conflicts = NULL;
 
   res->solved_conflicts = NULL;
 

-  res->nitems = core_size;
-  memcpy (res->items, core, core_size * sizeof (core[0]));
+  res->nitems = nitems;
+  memcpy (res->items, core, items_size);

 
   state_hash_insert (res);
 
 
   state_hash_insert (res);
 


@@ -158,100 +153,102 @@ state_new (symbol_number_t accessing_symbol,
 }
 
 
 }
 
 

-/*-------------.
-| Free STATE.  |
-`-------------*/
+/*---------.
+| Free S.  |
+`---------*/

 
 static void
 
 static void

-state_free (state_t *state)
+state_free (state *s)

 {
 {

-  free (state->transitions);
-  free (state->reductions);
-  free (state->errs);
-  free (state);
+  free (s->transitions);
+  free (s->reductions);
+  free (s->errs);
+  free (s);

 }
 
 
 }
 
 

-/*-------------------------------.
-| Set the transitions of STATE.  |
-`-------------------------------*/
+/*---------------------------.
+| Set the transitions of S.  |
+`---------------------------*/

 
 void
 
 void

-state_transitions_set (state_t *state, int num, state_t **transitions)
+state_transitions_set (state *s, int num, state **trans)

 {
 {

-  assert (!state->transitions);
-  state->transitions = transitions_new (num, transitions);
+  assert (!s->transitions);
+  s->transitions = transitions_new (num, trans);

 }
 
 
 }
 
 

-/*------------------------------.
-| Set the reductions of STATE.  |
-`------------------------------*/
+/*--------------------------.
+| Set the reductions of S.  |
+`--------------------------*/

 
 void
 
 void

-state_reductions_set (state_t *state, int num, rule_t **reductions)
+state_reductions_set (state *s, int num, rule **reds)

 {
 {

-  assert (!state->reductions);
-  state->reductions = reductions_new (num, reductions);
+  assert (!s->reductions);
+  s->reductions = reductions_new (num, reds);

 }
 
 
 int
 }
 
 
 int

-state_reduction_find (state_t *state, rule_t *rule)
+state_reduction_find (state *s, rule *r)

 {
   int i;
 {
   int i;

-  reductions_t *reds = state->reductions;
+  reductions *reds = s->reductions;

   for (i = 0; i < reds->num; ++i)
   for (i = 0; i < reds->num; ++i)

-    if (reds->rules[i] == rule)
+    if (reds->rules[i] == r)

       return i;
   return -1;
 }
 
 
       return i;
   return -1;
 }
 
 

-/*------------------------.
-| Set the errs of STATE.  |
-`------------------------*/
+/*--------------------.
+| Set the errs of S.  |
+`--------------------*/

 
 void
 
 void

-state_errs_set (state_t *state, int num, symbol_t **tokens)
+state_errs_set (state *s, int num, symbol **tokens)

 {
 {

-  assert (!state->errs);
-  state->errs = errs_new (num, tokens);
+  if (s->errs)
+    abort ();
+  s->errs = errs_new (num, tokens);

 }
 
 
 
 }
 
 
 

-/*--------------------------------------------------------------.
-| Print on OUT all the lookaheads such that this STATE wants to |
-| reduce this RULE.                                             |
-`--------------------------------------------------------------*/
+/*---------------------------------------------------.
+| Print on OUT all the look-ahead tokens such that S |
+| wants to reduce R.                                 |
+`---------------------------------------------------*/

 
 void
 
 void

-state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
+state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out)

 {
   /* Find the reduction we are handling.  */
 {
   /* Find the reduction we are handling.  */

-  reductions_t *reds = state->reductions;
-  int red = state_reduction_find (state, rule);
+  reductions *reds = s->reductions;
+  int red = state_reduction_find (s, r);

 
   /* Print them if there are.  */
 
   /* Print them if there are.  */

-  if (reds->lookaheads && red != -1)
+  if (reds->look_ahead_tokens && red != -1)

     {
       bitset_iterator biter;
       int k;
     {
       bitset_iterator biter;
       int k;

-      int not_first = 0;
+      char const *sep = "";

       fprintf (out, "  [");
       fprintf (out, "  [");

-      BITSET_FOR_EACH (biter, reds->lookaheads[red], k, 0)
-       fprintf (out, "%s%s",
-                not_first++ ? ", " : "",
-                symbols[k]->tag);
+      BITSET_FOR_EACH (biter, reds->look_ahead_tokens[red], k, 0)
+       {
+         fprintf (out, "%s%s", sep, symbols[k]->tag);
+         sep = ", ";
+       }

       fprintf (out, "]");
     }
 }
 
 
       fprintf (out, "]");
     }
 }
 
 

-/*----------------------.
+/*---------------------.

 | A state hash table.  |
 | A state hash table.  |

-`----------------------*/
+`---------------------*/

 
 /* Initial capacity of states hash table.  */
 #define HT_INITIAL_CAPACITY 257
 
 /* Initial capacity of states hash table.  */
 #define HT_INITIAL_CAPACITY 257


@@ -259,10 +256,10 @@ state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
 static struct hash_table *state_table = NULL;
 
 /* Two states are equal if they have the same core items.  */
 static struct hash_table *state_table = NULL;
 
 /* Two states are equal if they have the same core items.  */

-static bool
-state_compare (const state_t *s1, const state_t *s2)
+static inline bool
+state_compare (state const *s1, state const *s2)

 {
 {

-  int i;
+  size_t i;

 
   if (s1->nitems != s2->nitems)
     return false;
 
   if (s1->nitems != s2->nitems)
     return false;


@@ -274,17 +271,29 @@ state_compare (const state_t *s1, const state_t *s2)
   return true;
 }
 
   return true;
 }
 

-static unsigned int
-state_hash (const state_t *state, unsigned int tablesize)
+static bool
+state_comparator (void const *s1, void const *s2)
+{
+  return state_compare (s1, s2);
+}
+
+static inline size_t
+state_hash (state const *s, size_t tablesize)

 {
   /* Add up the state's item numbers to get a hash key.  */
 {
   /* Add up the state's item numbers to get a hash key.  */

-  int key = 0;
-  int i;
-  for (i = 0; i < state->nitems; ++i)
-    key += state->items[i];
+  size_t key = 0;
+  size_t i;
+  for (i = 0; i < s->nitems; ++i)
+    key += s->items[i];

   return key % tablesize;
 }
 
   return key % tablesize;
 }
 

+static size_t
+state_hasher (void const *s, size_t tablesize)
+{
+  return state_hash (s, tablesize);
+}
+

 
 /*-------------------------------.
 | Create the states hash table.  |
 
 /*-------------------------------.
 | Create the states hash table.  |


@@ -295,9 +304,9 @@ state_hash_new (void)
 {
   state_table = hash_initialize (HT_INITIAL_CAPACITY,
                                 NULL,
 {
   state_table = hash_initialize (HT_INITIAL_CAPACITY,
                                 NULL,

-                                (Hash_hasher) state_hash,
-                                (Hash_comparator) state_compare,
-                                (Hash_data_freer) NULL);
+                                state_hasher,
+                                state_comparator,
+                                NULL);

 }
 
 
 }
 
 


@@ -312,14 +321,14 @@ state_hash_free (void)
 }
 
 
 }
 
 

-/*---------------------------------------.
-| Insert STATE in the state hash table.  |
-`---------------------------------------*/
+/*-----------------------------------.
+| Insert S in the state hash table.  |
+`-----------------------------------*/

 
 void
 
 void

-state_hash_insert (state_t *state)
+state_hash_insert (state *s)

 {
 {

-  hash_insert (state_table, state);
+  hash_insert (state_table, s);

 }
 
 
 }
 
 


@@ -328,21 +337,22 @@ state_hash_insert (state_t *state)
 | not exist yet, return NULL.                                       |
 `------------------------------------------------------------------*/
 
 | not exist yet, return NULL.                                       |
 `------------------------------------------------------------------*/
 

-state_t *
-state_hash_lookup (size_t core_size, item_number_t *core)
+state *
+state_hash_lookup (size_t nitems, item_number *core)

 {
 {

-  state_t *probe = STATE_ALLOC (core_size);
-  state_t *entry;
+  size_t items_size = nitems * sizeof *core;
+  state *probe = xmalloc (offsetof (state, items) + items_size);
+  state *entry;

 
 

-  probe->nitems = core_size;
-  memcpy (probe->items, core, core_size * sizeof (core[0]));
+  probe->nitems = nitems;
+  memcpy (probe->items, core, items_size);

   entry = hash_lookup (state_table, probe);
   free (probe);
   return entry;
 }
 
 /* All the decorated states, indexed by the state number.  */
   entry = hash_lookup (state_table, probe);
   free (probe);
   return entry;
 }
 
 /* All the decorated states, indexed by the state number.  */

-state_t **states = NULL;
+state **states = NULL;

 
 
 /*----------------------.
 
 
 /*----------------------.


@@ -352,7 +362,7 @@ state_t **states = NULL;
 void
 states_free (void)
 {
 void
 states_free (void)
 {

-  state_number_t i;
+  state_number i;

   for (i = 0; i < nstates; ++i)
     state_free (states[i]);
   free (states);
   for (i = 0; i < nstates; ++i)
     state_free (states[i]);
   free (states);