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