1 /* IELR's inadequacy 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 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_ */ 157