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