src/InadequacyList.h

/* IELR's inadequacy list.

   Copyright (C) 2009 Free Software Foundation, Inc.

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

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#ifndef INADEQUACY_LIST_H_
# define INADEQUACY_LIST_H_

#include <bitset.h>
#include "gram.h"
#include "state.h"
#include "symtab.h"

/**
 * For a conflict, each rule in the grammar can have at most one contributing
 * reduction except that rule 0 cannot have any because the reduction on rule 0
 * cannot have lookaheads.  For a conflict, exactly one shift can contribute.
 * Thus the number of rules in the grammar is an upper bound on the number of
 * possible contributions to any conflict.  The maximum number of possible
 * items in a state is also an upper bound, but the \c nitems member of \c
 * state is currently a \c size_t and thus, if changed, risks becoming out of
 * sync with this type.  Whatever the type, it must support negatives for sake
 * of the special values below.
 */
typedef rule_number ContributionIndex;

/* Special \c ContributionIndex used to indicate null result when looking for a
   contribution.  */
extern ContributionIndex const ContributionIndex__none;

/* Special \c ContributionIndex used by
   \c AnnotationList__computeDominantContribution to signal when the action
   chosen in a conflict is a syntax error because of a %nonassoc.  */
extern ContributionIndex const ContributionIndex__error_action;

/**
 * The description of a conflict.  Don't break encapsulation by modifying the
 * fields directly.  Use the provided interface functions for
 * \c InadequacyList.
 */
typedef struct {
  /** The \c token passed to \c InadequacyList__new_conflict.  */
  symbol *token;
  /** The \c actions passed to \c InadequacyList__new_conflict.  */
  bitset actions;
} Conflict;

/**
 * A node in a list that describes all the inadequacies that manifest in a
 * particular state.  Don't break encapsulation by modifying the fields
 * directly.  Use the provided interface functions.
 */
typedef struct InadequacyList {
  struct InadequacyList *next;
  state *manifestingState;
  ContributionIndex contributionCount;
  union {
    Conflict conflict;
  } inadequacy;
} InadequacyList;

/**
 * \pre
 *   - <tt>manifesting_state != NULL</tt>.
 *   - \c token is a token.
 *   - The size of \c actions is
 *     <tt>manifesting_state->reductions->num + 1</tt>.
 * \post
 *   - \c result is a new \c InadequacyList with one node indicating that, in
 *     \c manifesting_state, the following actions are in conflict on \c token:
 *     - Shift iff
 *       <tt>bitset_test (actions, manifesting_state->reductions->num)</tt>.
 *     - For any \c i such that
 *       <tt>0 <= i < manifesting_state->reductions->num</tt>, the reduction
 *       for the rule <tt>manifesting_state->reductions->rules[i]</tt> iff
 *       <tt>actions[i]</tt> is set.
 *   - \c result assumes responsibility for the memory of \c actions.
 */
InadequacyList *InadequacyList__new_conflict (state *manifesting_state,
                                              symbol *token, bitset actions);

/**
 * \post
 *   - All memory associated with all nodes in the list \c self was freed.
 */
void InadequacyList__delete (InadequacyList *self);

/**
 * \pre
 *   - <tt>self != NULL</tt>.
 * \post
 *   - \c result = either:
 *     - \c ContributionIndex__none iff there is no shift contribution in
 *       \c self (perhaps because \c self isn't a conflict).
 *     - The index of the shift contribution, otherwise.
 */
ContributionIndex
InadequacyList__getShiftContributionIndex (InadequacyList const *self);

/**
 * \pre
 *   - <tt>self != NULL</tt>.
 *   - <tt>0 <= i < self->contributionCount</tt>.
 * \post
 *   - \c result = the token associated with contribution \c i in the
 *     inadequacy described by the node \c self.
 */
symbol *InadequacyList__getContributionToken (InadequacyList const *self,
                                              ContributionIndex i);

/**
 * \pre
 *   - \c self is a single node.
 *   - <tt>list != NULL</tt>.
 * \post
 *   - \c list now contains \c self as its first node.
 *   - \c list assumes responsibility for the memory of \c self.
 */
void InadequacyList__prependTo (InadequacyList *self, InadequacyList **list);

#endif /* !INADEQUACY_LIST_H_ */
Commit	Line	Data
	1	/* IELR's inadequacy list.
	2
	3	Copyright (C) 2009 Free Software Foundation, Inc.
	4
	5	This file is part of Bison, the GNU Compiler Compiler.
	6
	7	This program is free software: you can redistribute it and/or modify
	8	it under the terms of the GNU General Public License as published by
	9	the Free Software Foundation, either version 3 of the License, or
	10	(at your option) any later version.
	11
	12	This program is distributed in the hope that it will be useful,
	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	GNU General Public License for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with this program. If not, see <http://www.gnu.org/licenses/>. */
	19
	20	#ifndef INADEQUACY_LIST_H_
	21	# define INADEQUACY_LIST_H_
	22
	23	#include <bitset.h>
	24	#include "gram.h"
	25	#include "state.h"
	26	#include "symtab.h"
	27
	28	/**
	29	* For a conflict, each rule in the grammar can have at most one contributing
	30	* reduction except that rule 0 cannot have any because the reduction on rule 0
	31	* cannot have lookaheads. For a conflict, exactly one shift can contribute.
	32	* Thus the number of rules in the grammar is an upper bound on the number of
	33	* possible contributions to any conflict. The maximum number of possible
	34	* items in a state is also an upper bound, but the \c nitems member of \c
	35	* state is currently a \c size_t and thus, if changed, risks becoming out of
	36	* sync with this type. Whatever the type, it must support negatives for sake
	37	* of the special values below.
	38	*/
	39	typedef rule_number ContributionIndex;
	40
	41	/* Special \c ContributionIndex used to indicate null result when looking for a
	42	contribution. */
	43	extern ContributionIndex const ContributionIndex__none;
	44
	45	/* Special \c ContributionIndex used by
	46	\c AnnotationList__computeDominantContribution to signal when the action
	47	chosen in a conflict is a syntax error because of a %nonassoc. */
	48	extern ContributionIndex const ContributionIndex__error_action;
	49
	50	/**
	51	* The description of a conflict. Don't break encapsulation by modifying the
	52	* fields directly. Use the provided interface functions for
	53	* \c InadequacyList.
	54	*/
	55	typedef struct {
	56	/** The \c token passed to \c InadequacyList__new_conflict. */
	57	symbol *token;
	58	/** The \c actions passed to \c InadequacyList__new_conflict. */
	59	bitset actions;
	60	} Conflict;
	61
	62	/**
	63	* A node in a list that describes all the inadequacies that manifest in a
	64	* particular state. Don't break encapsulation by modifying the fields
	65	* directly. Use the provided interface functions.
	66	*/
	67	typedef struct InadequacyList {
	68	struct InadequacyList *next;
	69	state *manifestingState;
	70	ContributionIndex contributionCount;
	71	union {
	72	Conflict conflict;
	73	} inadequacy;
	74	} InadequacyList;
	75
	76	/**
	77	* \pre
	78	* - <tt>manifesting_state != NULL</tt>.
	79	* - \c token is a token.
	80	* - The size of \c actions is
	81	* <tt>manifesting_state->reductions->num + 1</tt>.
	82	* \post
	83	* - \c result is a new \c InadequacyList with one node indicating that, in
	84	* \c manifesting_state, the following actions are in conflict on \c token:
	85	* - Shift iff
	86	* <tt>bitset_test (actions, manifesting_state->reductions->num)</tt>.
	87	* - For any \c i such that
	88	* <tt>0 <= i < manifesting_state->reductions->num</tt>, the reduction
	89	* for the rule <tt>manifesting_state->reductions->rules[i]</tt> iff
	90	* <tt>actions[i]</tt> is set.
	91	* - \c result assumes responsibility for the memory of \c actions.
	92	*/
	93	InadequacyList InadequacyList__new_conflict (state manifesting_state,
	94	symbol *token, bitset actions);
	95
	96	/**
	97	* \post
	98	* - All memory associated with all nodes in the list \c self was freed.
	99	*/
	100	void InadequacyList__delete (InadequacyList *self);
	101
	102	/**
	103	* \pre
	104	* - <tt>self != NULL</tt>.
	105	* \post
	106	* - \c result = either:
	107	* - \c ContributionIndex__none iff there is no shift contribution in
	108	* \c self (perhaps because \c self isn't a conflict).
	109	* - The index of the shift contribution, otherwise.
	110	*/
	111	ContributionIndex
	112	InadequacyList__getShiftContributionIndex (InadequacyList const *self);
	113
	114	/**
	115	* \pre
	116	* - <tt>self != NULL</tt>.
	117	* - <tt>0 <= i < self->contributionCount</tt>.
	118	* \post
	119	* - \c result = the token associated with contribution \c i in the
	120	* inadequacy described by the node \c self.
	121	*/
	122	symbol InadequacyList__getContributionToken (InadequacyList const self,
	123	ContributionIndex i);
	124
	125	/**
	126	* \pre
	127	* - \c self is a single node.
	128	* - <tt>list != NULL</tt>.
	129	* \post
	130	* - \c list now contains \c self as its first node.
	131	* - \c list assumes responsibility for the memory of \c self.
	132	*/
	133	void InadequacyList__prependTo (InadequacyList self, InadequacyList *list);
	134
	135	#endif /* !INADEQUACY_LIST_H_ */