1 | /* IELR's inadequacy list. |
2 | |
3 | Copyright (C) 2009-2015, 2018-2019 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 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</tt> 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 | |