| 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 | |
| 28 | typedef 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 | */ |
| 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_ */ |