src/AnnotationList.h

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