src/AnnotationList.h

/* IELR's inadequacy annotation list.

   Copyright (C) 2009-2012 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 ANNOTATION_LIST_H_
# define ANNOTATION_LIST_H_

#include <bitsetv.h>
#include "Sbitset.h"
#include "InadequacyList.h"
#include "state.h"

typedef unsigned int AnnotationIndex;

/**
 * A node in a list of annotations on a particular LR(0) state.  Each
 * annotation records how isocores of that LR(0) state might contribute to an
 * individual inadequacy, which might manifest in a different state.  Don't
 * break encapsulation by modifying the fields directly.  Use the provided
 * interface functions.
 */
typedef struct AnnotationList
{
  /** The next node in the list or \c NULL if none.  */
  struct AnnotationList *next;
  /** The \c InadequacyList node describing how this inadequacy manifests.  */
  InadequacyList *inadequacyNode;
  /**
   * List of how the "always", "never", and potential contributions of the
   * inadequacy might be made by isocores of the annotated LR(0) state:
   *   - The number of rows is the number of contributions.  That is,
   *     <tt>AnnotationList::inadequacyNode->contributionCount</tt>.
   *   - The token associated with contribution \c i is
   *     <tt>InadequacyList__getContributionToken (AnnotationList::inadequacyNode, i)</tt>.
   *   - Iff <tt>AnnotationList::contributions[i] = NULL</tt>, contribution
   *     \c i is an "always" contribution.  That is, for every isocore of the
   *     annotated LR(0) state, its core or the core of one its eventual
   *     successors will definitely make this contribution to the inadequacy.
   *     It may contribute by either:
   *     - Creating a shift of contribution <tt>i</tt>'s token in the state
   *       that can manifest the inadequacy.
   *     - Propagating that token to the lookahead set of contribution
   *       <tt>i</tt>'s reduction in the state that can manifest the
   *       inadequacy.
   *   - Otherwise:
   *     - The number of columns in <tt>AnnotationList::contributions[i]</tt>
   *       is the number of kernel items in any isocore of the annotated LR(0)
   *       state.
   *     - Iff <tt>AnnotationList::contributions[i]</tt> is empty, contribution
   *       \c i is a "never" contribution.  That is, no isocore of the
   *       annotated LR(0) state can make this contribution to the inadequacy.
   *     - Otherwise, for each bit \c j that is set in
   *       <tt>AnnotationList::contributions[i]</tt>, if the token associated
   *       with contribution \c i is present in the lookahead set of kernel
   *       item \c j of an isocore of the annotated LR(0) state, that isocore
   *       will make contribution \c i to the inadequacy by propagating the
   *       contribution's token to the lookahead set of the contribution's
   *       reduction in the state that can manifest the inadequacy.
   */
  Sbitset contributions[1];
} AnnotationList;

/**
 * \pre
 *   - <tt>s != NULL</tt>.
 *   - \c follow_kernel_items, \c always_follows, and \c predecessors were
 *     computed by \c ielr_compute_auxiliary_tables.
 *   - The size of each of \c annotation_lists and \c annotation_counts is
 *     \c ::nstates.
 *   - If no \c InadequacyList nodes are currently allocated for the
 *     parser tables to which \c s belongs, then it is best if
 *     <tt>*inadequacy_list_node_count</tt> is zero to avoid overflow.
 *     Otherwise, <tt>*inadequacy_list_node_count</tt> has not been
 *     modified by any function except
 *     \c AnnotationList__compute_from_inadequacies since the invocation
 *     of \c AnnotationList__compute_from_inadequacies that constructed
 *     the first of the \c InadequacyList nodes currently allocated for
 *     those parser tables.
 * \post
 *   - <tt>inadequacy_lists[s->number]</tt> now describes all inadequacies that
 *     manifest in \c s.
 *   - For every state <tt>states[i]</tt>, <tt>annotation_lists[i]</tt> now
 *     contains all annotations associated with all inadequacies that manifest
 *     in \c s.
 *   - <tt>annotation_counts[i]</tt> was incremented by the number of new
 *     annotations added to <tt>states[i]</tt>.
 *   - <tt>*max_contributionsp</tt> is the higher of:
 *     - The maximum number of contributions computed per annotation.
 *     - <tt>*max_contributionsp \@pre</tt>.
 *   - All memory for all new annotations was allocated on
 *     \c annotations_obstackp.
 */
void
AnnotationList__compute_from_inadequacies (
  state *s, bitsetv follow_kernel_items, bitsetv always_follows,
  state ***predecessors, bitset **item_lookahead_sets,
  InadequacyList **inadequacy_lists, AnnotationList **annotation_lists,
  AnnotationIndex *annotation_counts,
  ContributionIndex *max_contributionsp,
  struct obstack *annotations_obstackp,
  InadequacyListNodeCount *inadequacy_list_node_count);

/**
 * \pre
 *   - <tt>self != NULL</tt>.
 *   - \c nitems is the number of kernel items in the LR(0) state that every
 *     node in the list \c self annotates.
 * \post
 *   - A textual representation of all nodes in the list \c self was printed to
 *     stderr.  \c spaces spaces were printed before each line of the text.
 */
void AnnotationList__debug (AnnotationList const *self, size_t nitems,
                            int spaces);

/**
 * \pre
 *   - <tt>self != NULL</tt>.
 *   - \c nitems is the number of kernel items in the LR(0) state that \c self
 *     annotates.
 *   - The number of rows in \c lookahead_filter is at least \c nitems, and the
 *     number of columns is \c ::ntokens.
 * \post
 *   - <tt>lookahead_filter[i][j]</tt> is set iff some annotation in the list
 *     \c self lists token \c j in kernel item \c i as a contributor.
 */
void AnnotationList__computeLookaheadFilter (AnnotationList const *self,
                                             size_t nitems,
                                             bitsetv lookahead_filter);

/**
 * \pre
 *   - <tt>self != NULL</tt>.
 *   - \c nitems is the number of kernel items in the LR(0) state that \c self
 *     annotates.
 *   - \c lookaheads describes the lookahead sets on the kernel items of some
 *     isocore of the LR(0) state that \c self annotates.  Either:
 *     - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel
 *       item is empty.
 *     - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> is either:
 *       - \c NULL only if the lookahead set on kernel item \c i is empty.
 *       - The (possibly empty) lookahead set on kernel item \c i.
 * \post
 *   - If <tt>require_split_stable = false</tt>, \c result = either:
 *     - \c ContributionIndex__none iff the state described by \c lookaheads
 *       makes none of the contributions in \c self.
 *     - The index of the dominating contribution in \c self that is made by
 *       that state.
 *     - \c ContributionIndex__error_action to indicate that the inadequacy
 *       manifests as a conflict and that a syntax error action (because of a
 *       %nonassoc) dominates instead.
 *   - Otherwise, \c result is the same as if <tt>require_split_stable =
 *     false</tt> except that it is also \c ContributionIndex__none if there
 *     are contributions made by the state but the dominating contribution is
 *     not split-stable.  By split-stable, we mean that the dominating
 *     contribution cannot change due to loss of one or more potential
 *     contributions due to loss of lookaheads due to splitting of the state.
 *   - After determining which contributions are actually made by the state,
 *     the algorithm for determining which contribution dominates in the
 *     conflict is intended to choose exactly the same action as conflicts.c
 *     would choose... no matter how crazy conflicts.c's choice is.
 */
ContributionIndex
AnnotationList__computeDominantContribution (AnnotationList const *self,
                                             size_t nitems, bitset *lookaheads,
                                             bool require_split_stable);

#endif /* !ANNOTATION_LIST_H_ */
Commit	Line	Data
	1	/* IELR's inadequacy annotation list.
	2
	3	Copyright (C) 2009-2012 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 ANNOTATION_LIST_H_
	21	# define ANNOTATION_LIST_H_
	22
	23	#include <bitsetv.h>
	24	#include "Sbitset.h"
	25	#include "InadequacyList.h"
	26	#include "state.h"
	27
	28	typedef unsigned int AnnotationIndex;
	29
	30	/**
	31	* A node in a list of annotations on a particular LR(0) state. Each
	32	* annotation records how isocores of that LR(0) state might contribute to an
	33	* individual inadequacy, which might manifest in a different state. Don't
	34	* break encapsulation by modifying the fields directly. Use the provided
	35	* interface functions.
	36	*/
	37	typedef struct AnnotationList
	38	{
	39	/** The next node in the list or \c NULL if none. */
	40	struct AnnotationList *next;
	41	/** The \c InadequacyList node describing how this inadequacy manifests. */
	42	InadequacyList *inadequacyNode;
	43	/**
	44	* List of how the "always", "never", and potential contributions of the
	45	* inadequacy might be made by isocores of the annotated LR(0) state:
	46	* - The number of rows is the number of contributions. That is,
	47	* <tt>AnnotationList::inadequacyNode->contributionCount</tt>.
	48	* - The token associated with contribution \c i is
	49	* <tt>InadequacyList__getContributionToken (AnnotationList::inadequacyNode, i)</tt>.
	50	* - Iff <tt>AnnotationList::contributions[i] = NULL</tt>, contribution
	51	* \c i is an "always" contribution. That is, for every isocore of the
	52	* annotated LR(0) state, its core or the core of one its eventual
	53	* successors will definitely make this contribution to the inadequacy.
	54	* It may contribute by either:
	55	* - Creating a shift of contribution <tt>i</tt>'s token in the state
	56	* that can manifest the inadequacy.
	57	* - Propagating that token to the lookahead set of contribution
	58	* <tt>i</tt>'s reduction in the state that can manifest the
	59	* inadequacy.
	60	* - Otherwise:
	61	* - The number of columns in <tt>AnnotationList::contributions[i]</tt>
	62	* is the number of kernel items in any isocore of the annotated LR(0)
	63	* state.
	64	* - Iff <tt>AnnotationList::contributions[i]</tt> is empty, contribution
	65	* \c i is a "never" contribution. That is, no isocore of the
	66	* annotated LR(0) state can make this contribution to the inadequacy.
	67	* - Otherwise, for each bit \c j that is set in
	68	* <tt>AnnotationList::contributions[i]</tt>, if the token associated
	69	* with contribution \c i is present in the lookahead set of kernel
	70	* item \c j of an isocore of the annotated LR(0) state, that isocore
	71	* will make contribution \c i to the inadequacy by propagating the
	72	* contribution's token to the lookahead set of the contribution's
	73	* reduction in the state that can manifest the inadequacy.
	74	*/
	75	Sbitset contributions[1];
	76	} AnnotationList;
	77
	78	/**
	79	* \pre
	80	* - <tt>s != NULL</tt>.
	81	* - \c follow_kernel_items, \c always_follows, and \c predecessors were
	82	* computed by \c ielr_compute_auxiliary_tables.
	83	* - The size of each of \c annotation_lists and \c annotation_counts is
	84	* \c ::nstates.
	85	* - If no \c InadequacyList nodes are currently allocated for the
	86	* parser tables to which \c s belongs, then it is best if
	87	* <tt>*inadequacy_list_node_count</tt> is zero to avoid overflow.
	88	* Otherwise, <tt>*inadequacy_list_node_count</tt> has not been
	89	* modified by any function except
	90	* \c AnnotationList__compute_from_inadequacies since the invocation
	91	* of \c AnnotationList__compute_from_inadequacies that constructed
	92	* the first of the \c InadequacyList nodes currently allocated for
	93	* those parser tables.
	94	* \post
	95	* - <tt>inadequacy_lists[s->number]</tt> now describes all inadequacies that
	96	* manifest in \c s.
	97	* - For every state <tt>states[i]</tt>, <tt>annotation_lists[i]</tt> now
	98	* contains all annotations associated with all inadequacies that manifest
	99	* in \c s.
	100	* - <tt>annotation_counts[i]</tt> was incremented by the number of new
	101	* annotations added to <tt>states[i]</tt>.
	102	* - <tt>*max_contributionsp</tt> is the higher of:
	103	* - The maximum number of contributions computed per annotation.
	104	* - <tt>*max_contributionsp \@pre</tt>.
	105	* - All memory for all new annotations was allocated on
	106	* \c annotations_obstackp.
	107	*/
	108	void
	109	AnnotationList__compute_from_inadequacies (
	110	state *s, bitsetv follow_kernel_items, bitsetv always_follows,
	111	state *predecessors, bitset item_lookahead_sets,
	112	InadequacyList inadequacy_lists, AnnotationList annotation_lists,
	113	AnnotationIndex *annotation_counts,
	114	ContributionIndex *max_contributionsp,
	115	struct obstack *annotations_obstackp,
	116	InadequacyListNodeCount *inadequacy_list_node_count);
	117
	118	/**
	119	* \pre
	120	* - <tt>self != NULL</tt>.
	121	* - \c nitems is the number of kernel items in the LR(0) state that every
	122	* node in the list \c self annotates.
	123	* \post
	124	* - A textual representation of all nodes in the list \c self was printed to
	125	* stderr. \c spaces spaces were printed before each line of the text.
	126	*/
	127	void AnnotationList__debug (AnnotationList const *self, size_t nitems,
	128	int spaces);
	129
	130	/**
	131	* \pre
	132	* - <tt>self != NULL</tt>.
	133	* - \c nitems is the number of kernel items in the LR(0) state that \c self
	134	* annotates.
	135	* - The number of rows in \c lookahead_filter is at least \c nitems, and the
	136	* number of columns is \c ::ntokens.
	137	* \post
	138	* - <tt>lookahead_filter[i][j]</tt> is set iff some annotation in the list
	139	* \c self lists token \c j in kernel item \c i as a contributor.
	140	*/
	141	void AnnotationList__computeLookaheadFilter (AnnotationList const *self,
	142	size_t nitems,
	143	bitsetv lookahead_filter);
	144
	145	/**
	146	* \pre
	147	* - <tt>self != NULL</tt>.
	148	* - \c nitems is the number of kernel items in the LR(0) state that \c self
	149	* annotates.
	150	* - \c lookaheads describes the lookahead sets on the kernel items of some
	151	* isocore of the LR(0) state that \c self annotates. Either:
	152	* - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel
	153	* item is empty.
	154	* - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> is either:
	155	* - \c NULL only if the lookahead set on kernel item \c i is empty.
	156	* - The (possibly empty) lookahead set on kernel item \c i.
	157	* \post
	158	* - If <tt>require_split_stable = false</tt>, \c result = either:
	159	* - \c ContributionIndex__none iff the state described by \c lookaheads
	160	* makes none of the contributions in \c self.
	161	* - The index of the dominating contribution in \c self that is made by
	162	* that state.
	163	* - \c ContributionIndex__error_action to indicate that the inadequacy
	164	* manifests as a conflict and that a syntax error action (because of a
	165	* %nonassoc) dominates instead.
	166	* - Otherwise, \c result is the same as if <tt>require_split_stable =
	167	* false</tt> except that it is also \c ContributionIndex__none if there
	168	* are contributions made by the state but the dominating contribution is
	169	* not split-stable. By split-stable, we mean that the dominating
	170	* contribution cannot change due to loss of one or more potential
	171	* contributions due to loss of lookaheads due to splitting of the state.
	172	* - After determining which contributions are actually made by the state,
	173	* the algorithm for determining which contribution dominates in the
	174	* conflict is intended to choose exactly the same action as conflicts.c
	175	* would choose... no matter how crazy conflicts.c's choice is.
	176	*/
	177	ContributionIndex
	178	AnnotationList__computeDominantContribution (AnnotationList const *self,
	179	size_t nitems, bitset *lookaheads,
	180	bool require_split_stable);
	181
	182	#endif /* !ANNOTATION_LIST_H_ */