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