src/InadequacyList.h

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