src/InadequacyList.h

   1 /* IELR's inadequacy list.
   2
   3    Copyright (C) 2009, 2010 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  * A unique ID assigned to every \c InadequacyList node.
  30  *
  31  * This must remain unsigned so that the overflow check in
  32  * \c InadequacyList__new_conflict works properly.
  33  */
  34 typedef unsigned long long int InadequacyListNodeCount;
  35
  36 /**
  37  * For a conflict, each rule in the grammar can have at most one contributing
  38  * reduction except that rule 0 cannot have any because the reduction on rule 0
  39  * cannot have lookaheads.  For a conflict, exactly one shift can contribute.
  40  * Thus the number of rules in the grammar is an upper bound on the number of
  41  * possible contributions to any conflict.  The maximum number of possible
  42  * items in a state is also an upper bound, but the \c nitems member of \c
  43  * state is currently a \c size_t and thus, if changed, risks becoming out of
  44  * sync with this type.  Whatever the type, it must support negatives for sake
  45  * of the special values below.
  46  */
  47 typedef rule_number ContributionIndex;
  48
  49 /* Special \c ContributionIndex used to indicate null result when looking for a
  50    contribution.  */
  51 extern ContributionIndex const ContributionIndex__none;
  52
  53 /* Special \c ContributionIndex used by
  54    \c AnnotationList__computeDominantContribution to signal when the action
  55    chosen in a conflict is a syntax error because of a %nonassoc.  */
  56 extern ContributionIndex const ContributionIndex__error_action;
  57
  58 /**
  59  * The description of a conflict.  Don't break encapsulation by modifying the
  60  * fields directly.  Use the provided interface functions for
  61  * \c InadequacyList.
  62  */
  63 typedef struct {
  64   /** The \c token passed to \c InadequacyList__new_conflict.  */
  65   symbol *token;
  66   /** The \c actions passed to \c InadequacyList__new_conflict.  */
  67   bitset actions;
  68 } Conflict;
  69
  70 /**
  71  * A node in a list that describes all the inadequacies that manifest in a
  72  * particular state.  Don't break encapsulation by modifying the fields
  73  * directly.  Use the provided interface functions.
  74  */
  75 typedef struct InadequacyList {
  76   struct InadequacyList *next;
  77   InadequacyListNodeCount id;
  78   state *manifestingState;
  79   ContributionIndex contributionCount;
  80   union {
  81     Conflict conflict;
  82   } inadequacy;
  83 } InadequacyList;
  84
  85 /**
  86  * \pre
  87  *   - <tt>manifesting_state != NULL</tt>.
  88  *   - \c token is a token.
  89  *   - The size of \c actions is
  90  *     <tt>manifesting_state->reductions->num + 1</tt>.
  91  *   - If the set of all \c InadequacyList nodes with which the new
  92  *     \c InadequacyList node might be compared is currently empty, then
  93  *     it is best if <tt>*node_count</t> is zero so that the node count
  94  *     does not eventually overflow.  However, if that set is not
  95  *     currently empty, then <tt>*node_count</tt> has not been modified
  96  *     by any function except \c InadequacyList__new_conflict since the
  97  *     invocation of \c InadequacyList__new_conflict that constructed
  98  *     the first existing member of that set.
  99  * \post
 100  *   - \c result is a new \c InadequacyList with one node indicating that, in
 101  *     \c manifesting_state, the following actions are in conflict on \c token:
 102  *     - Shift iff
 103  *       <tt>bitset_test (actions, manifesting_state->reductions->num)</tt>.
 104  *     - For any \c i such that
 105  *       <tt>0 <= i < manifesting_state->reductions->num</tt>, the reduction
 106  *       for the rule <tt>manifesting_state->reductions->rules[i]</tt> iff
 107  *       <tt>actions[i]</tt> is set.
 108  *   - Given any node \c n from the set of all existing
 109  *     \c InadequacyList nodes with which \c result might be compared
 110  *     such that <tt>n != result</tt>, then <tt>n->id < result->id</tt>.
 111  *   - \c result assumes responsibility for the memory of \c actions.
 112  */
 113 InadequacyList *InadequacyList__new_conflict (
 114   state *manifesting_state, symbol *token, bitset actions,
 115   InadequacyListNodeCount *node_count);
 116
 117 /**
 118  * \post
 119  *   - All memory associated with all nodes in the list \c self was freed.
 120  */
 121 void InadequacyList__delete (InadequacyList *self);
 122
 123 /**
 124  * \pre
 125  *   - <tt>self != NULL</tt>.
 126  * \post
 127  *   - \c result = either:
 128  *     - \c ContributionIndex__none iff there is no shift contribution in
 129  *       \c self (perhaps because \c self isn't a conflict).
 130  *     - The index of the shift contribution, otherwise.
 131  */
 132 ContributionIndex
 133 InadequacyList__getShiftContributionIndex (InadequacyList const *self);
 134
 135 /**
 136  * \pre
 137  *   - <tt>self != NULL</tt>.
 138  *   - <tt>0 <= i < self->contributionCount</tt>.
 139  * \post
 140  *   - \c result = the token associated with contribution \c i in the
 141  *     inadequacy described by the node \c self.
 142  */
 143 symbol *InadequacyList__getContributionToken (InadequacyList const *self,
 144                                               ContributionIndex i);
 145
 146 /**
 147  * \pre
 148  *   - \c self is a single node.
 149  *   - <tt>list != NULL</tt>.
 150  * \post
 151  *   - \c list now contains \c self as its first node.
 152  *   - \c list assumes responsibility for the memory of \c self.
 153  */
 154 void InadequacyList__prependTo (InadequacyList *self, InadequacyList **list);
 155
 156 #endif /* !INADEQUACY_LIST_H_ */