1 /* IELR's inadequacy annotation 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 ANNOTATION_LIST_H_
21 # define ANNOTATION_LIST_H_
22
23 # include <bitsetv.h>
24
25 # include "Sbitset.h"
26 # include "InadequacyList.h"
27 # include "state.h"
28
29 typedef int AnnotationIndex;
30
31 /**
32 * A node in a list of annotations on a particular LR(0) state. Each
33 * annotation records how isocores of that LR(0) state might contribute to an
34 * individual inadequacy, which might manifest in a different state. Don't
35 * break encapsulation by modifying the fields directly. Use the provided
36 * interface functions.
37 */
38 typedef struct AnnotationList
39 {
40 /** The next node in the list or \c NULL if none. */
41 struct AnnotationList *next;
42 /** The \c InadequacyList node describing how this inadequacy manifests. */
43 InadequacyList *inadequacyNode;
44 /**
45 * List of how the "always", "never", and potential contributions of the
46 * inadequacy might be made by isocores of the annotated LR(0) state:
47 * - The number of rows is the number of contributions. That is,
48 * <tt>AnnotationList::inadequacyNode->contributionCount</tt>.
49 * - The token associated with contribution \c i is
50 * <tt>InadequacyList__getContributionToken (AnnotationList::inadequacyNode, i)</tt>.
51 * - Iff <tt>AnnotationList::contributions[i] = NULL</tt>, contribution
52 * \c i is an "always" contribution. That is, for every isocore of the
53 * annotated LR(0) state, its core or the core of one its eventual
54 * successors will definitely make this contribution to the inadequacy.
55 * It may contribute by either:
56 * - Creating a shift of contribution <tt>i</tt>'s token in the state
57 * that can manifest the inadequacy.
58 * - Propagating that token to the lookahead set of contribution
59 * <tt>i</tt>'s reduction in the state that can manifest the
60 * inadequacy.
61 * - Otherwise:
62 * - The number of columns in <tt>AnnotationList::contributions[i]</tt>
63 * is the number of kernel items in any isocore of the annotated LR(0)
64 * state.
65 * - Iff <tt>AnnotationList::contributions[i]</tt> is empty, contribution
66 * \c i is a "never" contribution. That is, no isocore of the
67 * annotated LR(0) state can make this contribution to the inadequacy.
68 * - Otherwise, for each bit \c j that is set in
69 * <tt>AnnotationList::contributions[i]</tt>, if the token associated
70 * with contribution \c i is present in the lookahead set of kernel
71 * item \c j of an isocore of the annotated LR(0) state, that isocore
72 * will make contribution \c i to the inadequacy by propagating the
73 * contribution's token to the lookahead set of the contribution's
74 * reduction in the state that can manifest the inadequacy.
75 */
76 Sbitset contributions[1];
77 } AnnotationList;
78
79 /**
80 * \pre
81 * - <tt>s != NULL</tt>.
82 * - \c follow_kernel_items, \c always_follows, and \c predecessors were
83 * computed by \c ielr_compute_auxiliary_tables.
84 * - The size of each of \c annotation_lists and \c annotation_counts is
85 * \c ::nstates.
86 * - If no \c InadequacyList nodes are currently allocated for the
87 * parser tables to which \c s belongs, then it is best if
88 * <tt>*inadequacy_list_node_count</tt> is zero to avoid overflow.
89 * Otherwise, <tt>*inadequacy_list_node_count</tt> has not been
90 * modified by any function except
91 * \c AnnotationList__compute_from_inadequacies since the invocation
92 * of \c AnnotationList__compute_from_inadequacies that constructed
93 * the first of the \c InadequacyList nodes currently allocated for
94 * those parser tables.
95 * \post
96 * - <tt>inadequacy_lists[s->number]</tt> now describes all inadequacies that
97 * manifest in \c s.
98 * - For every state <tt>states[i]</tt>, <tt>annotation_lists[i]</tt> now
99 * contains all annotations associated with all inadequacies that manifest
100 * in \c s.
101 * - <tt>annotation_counts[i]</tt> was incremented by the number of new
102 * annotations added to <tt>states[i]</tt>.
103 * - <tt>*max_contributionsp</tt> is the higher of:
104 * - The maximum number of contributions computed per annotation.
105 * - <tt>*max_contributionsp \@pre</tt>.
106 * - All memory for all new annotations was allocated on
107 * \c annotations_obstackp.
108 */
109 void
110 AnnotationList__compute_from_inadequacies (
111 state *s, bitsetv follow_kernel_items, bitsetv always_follows,
112 state ***predecessors, bitset **item_lookahead_sets,
113 InadequacyList **inadequacy_lists, AnnotationList **annotation_lists,
114 AnnotationIndex *annotation_counts,
115 ContributionIndex *max_contributionsp,
116 struct obstack *annotations_obstackp,
117 InadequacyListNodeCount *inadequacy_list_node_count);
118
119 /**
120 * \pre
121 * - <tt>self != NULL</tt>.
122 * - \c nitems is the number of kernel items in the LR(0) state that every
123 * node in the list \c self annotates.
124 * \post
125 * - A textual representation of all nodes in the list \c self was printed to
126 * stderr. \c spaces spaces were printed before each line of the text.
127 */
128 void AnnotationList__debug (AnnotationList const *self, size_t nitems,
129 int spaces);
130
131 /**
132 * \pre
133 * - <tt>self != NULL</tt>.
134 * - \c nitems is the number of kernel items in the LR(0) state that \c self
135 * annotates.
136 * - The number of rows in \c lookahead_filter is at least \c nitems, and the
137 * number of columns is \c ::ntokens.
138 * \post
139 * - <tt>lookahead_filter[i][j]</tt> is set iff some annotation in the list
140 * \c self lists token \c j in kernel item \c i as a contributor.
141 */
142 void AnnotationList__computeLookaheadFilter (AnnotationList const *self,
143 size_t nitems,
144 bitsetv lookahead_filter);
145
146 /**
147 * \pre
148 * - <tt>self != NULL</tt>.
149 * - \c nitems is the number of kernel items in the LR(0) state that \c self
150 * annotates.
151 * - \c lookaheads describes the lookahead sets on the kernel items of some
152 * isocore of the LR(0) state that \c self annotates. Either:
153 * - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel
154 * item is empty.
155 * - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> is either:
156 * - \c NULL only if the lookahead set on kernel item \c i is empty.
157 * - The (possibly empty) lookahead set on kernel item \c i.
158 * \post
159 * - If <tt>require_split_stable = false</tt>, \c result = either:
160 * - \c ContributionIndex__none iff the state described by \c lookaheads
161 * makes none of the contributions in \c self.
162 * - The index of the dominating contribution in \c self that is made by
163 * that state.
164 * - \c ContributionIndex__error_action to indicate that the inadequacy
165 * manifests as a conflict and that a syntax error action (because of a
166 * %nonassoc) dominates instead.
167 * - Otherwise, \c result is the same as if <tt>require_split_stable =
168 * false</tt> except that it is also \c ContributionIndex__none if there
169 * are contributions made by the state but the dominating contribution is
170 * not split-stable. By split-stable, we mean that the dominating
171 * contribution cannot change due to loss of one or more potential
172 * contributions due to loss of lookaheads due to splitting of the state.
173 * - After determining which contributions are actually made by the state,
174 * the algorithm for determining which contribution dominates in the
175 * conflict is intended to choose exactly the same action as conflicts.c
176 * would choose... no matter how crazy conflicts.c's choice is.
177 */
178 ContributionIndex
179 AnnotationList__computeDominantContribution (AnnotationList const *self,
180 size_t nitems, bitset *lookaheads,
181 bool require_split_stable);
182
183 #endif /* !ANNOTATION_LIST_H_ */