1/* IELR's inadequacy annotation 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 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
28typedef unsigned int 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 */
37typedef 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 */
108void
109AnnotationList__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 */
127void 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 */
141void 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 */
177ContributionIndex
178AnnotationList__computeDominantContribution (AnnotationList const *self,
179                                             size_t nitems, bitset *lookaheads,
180                                             bool require_split_stable);
181
182#endif /* !ANNOTATION_LIST_H_ */
183