Fix push parsing memory leak reported by Brandon Lucia at

[bison.git] / src / state.h

diff --git a/src/state.h b/src/state.h
index 830d4578588a7bdfbdb85e8498d2737577d69aa3..390ab8af2f6f7849784165b7aeb94c717b47030b 100644 (file)
--- a/src/state.h
+++ b/src/state.h
@@ -1,5 +1,7 @@
-/* Type definitions for nondeterministic finite state machine for bison,
-   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
+/* Type definitions for nondeterministic finite state machine for Bison.
+
+   Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007 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,8 +17,8 @@
 
    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.  */

 
 
 /* These type definitions are used to represent a nondeterministic
 
 
 /* These type definitions are used to represent a nondeterministic


@@ -42,7 +44,7 @@
    ACCESSING_SYMBOL of the core.
 
    Each core contains a vector of NITEMS items which are the indices
    ACCESSING_SYMBOL of the core.
 
    Each core contains a vector of NITEMS items which are the indices

-   in the RITEMS vector of the items that are selected in this state.
+   in the RITEM vector of the items that are selected in this state.

 
    The two types of actions are shifts/gotos (push the lookahead token
    and read another/goto to the state designated by a nterm) and
 
    The two types of actions are shifts/gotos (push the lookahead token
    and read another/goto to the state designated by a nterm) and


@@ -51,7 +53,7 @@
    lookahead token alone).  When the states are generated, these
    actions are represented in two other lists.
 
    lookahead token alone).  When the states are generated, these
    actions are represented in two other lists.
 

-   Each transition_t structure describes the possible transitions out
+   Each transition structure describes the possible transitions out

    of one state, the state whose number is in the number field.  Each
    contains a vector of numbers of the states that transitions can go
    to.  The accessing_symbol fields of those states' cores say what
    of one state, the state whose number is in the number field.  Each
    contains a vector of numbers of the states that transitions can go
    to.  The accessing_symbol fields of those states' cores say what


@@ -61,9 +63,8 @@
    deletes transitions by having them point to zero.
 
    Each reductions structure describes the possible reductions at the
    deletes transitions by having them point to zero.
 
    Each reductions structure describes the possible reductions at the

-   state whose number is in the number field.  The data is a list of
-   nreds rules, represented by their rule numbers.  first_reduction
-   points to the list of these structures.
+   state whose number is in the number field.  rules is an array of
+   num rules.  lookahead_tokens is an array of bitsets, one per rule.

 
    Conflict resolution can decide that certain tokens in certain
    states should explicitly be errors (for implementing %nonassoc).
 
    Conflict resolution can decide that certain tokens in certain
    states should explicitly be errors (for implementing %nonassoc).


@@ -82,31 +83,38 @@
 #ifndef STATE_H_
 # define STATE_H_
 
 #ifndef STATE_H_
 # define STATE_H_
 

-# include "bitset.h"
+# include <bitset.h>
+
+# include "gram.h"
+# include "symtab.h"

 
 
 /*-------------------.
 | Numbering states.  |
 `-------------------*/
 
 
 
 /*-------------------.
 | Numbering states.  |
 `-------------------*/
 

-typedef short state_number_t;
-# define STATE_NUMBER_MAX ((state_number_t) SHRT_MAX)
+typedef int state_number;
+# define STATE_NUMBER_MAXIMUM INT_MAX

 
 

-/* Be ready to map a state_number_t to an int.  */
-# define state_number_as_int(Tok) ((int) (Tok))
+/* Be ready to map a state_number to an int.  */
+static inline int
+state_number_as_int (state_number s)
+{
+  return s;
+}

 
 
 
 

-typedef struct state_s state_t;
+typedef struct state state;

 
 /*--------------.
 | Transitions.  |
 `--------------*/
 
 
 /*--------------.
 | Transitions.  |
 `--------------*/
 

-typedef struct transtion_s
+typedef struct

 {
 {

-  short num;
-  state_t *states[1];
-} transitions_t;
+  int num;
+  state *states[1];
+} transitions;

 
 
 /* What is the symbol labelling the transition to
 
 
 /* What is the symbol labelling the transition to


@@ -151,84 +159,85 @@ typedef struct transtion_s
     if (!TRANSITION_IS_DISABLED (Transitions, Iter))
 
 
     if (!TRANSITION_IS_DISABLED (Transitions, Iter))
 
 

-/* Return the state such these TRANSITIONS contain a shift/goto to it on
-   SYMBOL.  Aborts if none found.  */
-struct state_s;
-struct state_s *transitions_to (transitions_t *state, symbol_number_t s);
+/* Return the state such SHIFTS contain a shift/goto to it on SYM.
+   Abort if none found.  */
+struct state *transitions_to (transitions *shifts, symbol_number sym);

 
 
 /*-------.
 | Errs.  |
 `-------*/
 
 
 
 /*-------.
 | Errs.  |
 `-------*/
 

-typedef struct errs_s
+typedef struct

 {
 {

-  short num;
-  symbol_t *symbols[1];
-} errs_t;
+  int num;
+  symbol *symbols[1];
+} errs;

 
 

-errs_t *errs_new (int num, symbol_t **tokens);
+errs *errs_new (int num, symbol **tokens);

 
 
 /*-------------.
 | Reductions.  |
 `-------------*/
 
 
 
 /*-------------.
 | Reductions.  |
 `-------------*/
 

-typedef struct reductions_s
+typedef struct

 {
 {

-  short num;
-  bitset *lookaheads;
-  rule_t *rules[1];
-} reductions_t;
+  int num;
+  bitset *lookahead_tokens;
+  /* Sorted ascendingly on rule number.  */
+  rule *rules[1];
+} reductions;

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

-| States.  |
+| states.  |

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

-struct state_s
+struct state

 {
 {

-  state_number_t number;
-  symbol_number_t accessing_symbol;
-  transitions_t     *transitions;
-  reductions_t *reductions;
-  errs_t       *errs;
-
-  /* Nonzero if no lookahead is needed to decide what to do in state S.  */
+  state_number number;
+  symbol_number accessing_symbol;
+  transitions *transitions;
+  reductions *reductions;
+  errs *errs;
+
+  /* If non-zero, then no lookahead sets on reduce actions are needed to
+     decide what to do in state S.  */

   char consistent;
 
   /* If some conflicts were solved thanks to precedence/associativity,
      a human readable description of the resolution.  */
   const char *solved_conflicts;
 
   char consistent;
 
   /* If some conflicts were solved thanks to precedence/associativity,
      a human readable description of the resolution.  */
   const char *solved_conflicts;
 

-  /* Its items.  Must be last, since ITEMS can be arbitrarily large.
-     */
-  unsigned short nitems;
-  item_number_t items[1];
+  /* Its items.  Must be last, since ITEMS can be arbitrarily large.  Sorted
+     ascendingly on item index in RITEM, which is sorted on rule number.  */
+  size_t nitems;
+  item_number items[1];

 };
 
 };
 

-extern state_number_t nstates;
-extern state_t *final_state;
+extern state_number nstates;
+extern state *final_state;

 
 /* Create a new state with ACCESSING_SYMBOL for those items.  */
 
 /* Create a new state with ACCESSING_SYMBOL for those items.  */

-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 core_size, item_number *core);

 
 /* Set the transitions of STATE.  */
 
 /* Set the transitions of STATE.  */

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

 
 /* Set the reductions of STATE.  */
 
 /* Set the reductions of STATE.  */

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

 
 

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

 
 /* Set the errs of STATE.  */
 
 /* Set the errs of STATE.  */

-void state_errs_set (state_t *state, int num, symbol_t **errs);
+void state_errs_set (state *s, int num, symbol **errors);

 
 

-/* Print on OUT all the lookaheads such that this STATE wants to
-   reduce this RULE.  */
-void state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out);
+/* Print on OUT all the lookahead tokens such that this STATE wants to
+   reduce R.  */
+void state_rule_lookahead_tokens_print (state *s, rule *r, FILE *out);

 
 /* Create/destroy the states hash table.  */
 void state_hash_new (void);
 
 /* Create/destroy the states hash table.  */
 void state_hash_new (void);


@@ -236,14 +245,21 @@ void state_hash_free (void);
 
 /* Find the state associated to the CORE, and return it.  If it does
    not exist yet, return NULL.  */
 
 /* Find the state associated to the CORE, and return it.  If it does
    not exist yet, return NULL.  */

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

 
 /* Insert STATE in the state hash table.  */
 
 /* Insert STATE in the state hash table.  */

-void state_hash_insert (state_t *state);
+void state_hash_insert (state *s);
+
+/* Remove unreachable states, renumber remaining states, update NSTATES, and
+   write to OLD_TO_NEW a mapping of old state numbers to new state numbers such
+   that the old value of NSTATES is written as the new state number for removed
+   states.  The size of OLD_TO_NEW must be the old value of NSTATES.  */
+void state_remove_unreachable_states (state_number old_to_new[]);

 
 /* All the states, indexed by the state number.  */
 
 /* All the states, indexed by the state number.  */

-extern state_t **states;
+extern state **states;

 
 /* Free all the states.  */
 void states_free (void);
 
 /* Free all the states.  */
 void states_free (void);

+

 #endif /* !STATE_H_ */
 #endif /* !STATE_H_ */