src/InadequacyList.h

   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_ */