/* IELR's inadequacy annotation list.
Copyright (C) 2009-2015, 2018-2020 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see . */
#ifndef ANNOTATION_LIST_H_
# define ANNOTATION_LIST_H_
# include
# include "Sbitset.h"
# include "InadequacyList.h"
# include "state.h"
typedef int AnnotationIndex;
/**
* A node in a list of annotations on a particular LR(0) state. Each
* annotation records how isocores of that LR(0) state might contribute to an
* individual inadequacy, which might manifest in a different state. Don't
* break encapsulation by modifying the fields directly. Use the provided
* interface functions.
*/
typedef struct AnnotationList
{
/** The next node in the list or \c NULL if none. */
struct AnnotationList *next;
/** The \c InadequacyList node describing how this inadequacy manifests. */
InadequacyList *inadequacyNode;
/**
* List of how the "always", "never", and potential contributions of the
* inadequacy might be made by isocores of the annotated LR(0) state:
* - The number of rows is the number of contributions. That is,
* AnnotationList::inadequacyNode->contributionCount.
* - The token associated with contribution \c i is
* InadequacyList__getContributionToken (AnnotationList::inadequacyNode, i).
* - Iff AnnotationList::contributions[i] = NULL, contribution
* \c i is an "always" contribution. That is, for every isocore of the
* annotated LR(0) state, its core or the core of one its eventual
* successors will definitely make this contribution to the inadequacy.
* It may contribute by either:
* - Creating a shift of contribution i's token in the state
* that can manifest the inadequacy.
* - Propagating that token to the lookahead set of contribution
* i's reduction in the state that can manifest the
* inadequacy.
* - Otherwise:
* - The number of columns in AnnotationList::contributions[i]
* is the number of kernel items in any isocore of the annotated LR(0)
* state.
* - Iff AnnotationList::contributions[i] is empty, contribution
* \c i is a "never" contribution. That is, no isocore of the
* annotated LR(0) state can make this contribution to the inadequacy.
* - Otherwise, for each bit \c j that is set in
* AnnotationList::contributions[i], if the token associated
* with contribution \c i is present in the lookahead set of kernel
* item \c j of an isocore of the annotated LR(0) state, that isocore
* will make contribution \c i to the inadequacy by propagating the
* contribution's token to the lookahead set of the contribution's
* reduction in the state that can manifest the inadequacy.
*/
Sbitset contributions[1];
} AnnotationList;
/**
* \pre
* - s != NULL.
* - \c follow_kernel_items, \c always_follows, and \c predecessors were
* computed by \c ielr_compute_auxiliary_tables.
* - The size of each of \c annotation_lists and \c annotation_counts is
* \c ::nstates.
* - If no \c InadequacyList nodes are currently allocated for the
* parser tables to which \c s belongs, then it is best if
* *inadequacy_list_node_count is zero to avoid overflow.
* Otherwise, *inadequacy_list_node_count has not been
* modified by any function except
* \c AnnotationList__compute_from_inadequacies since the invocation
* of \c AnnotationList__compute_from_inadequacies that constructed
* the first of the \c InadequacyList nodes currently allocated for
* those parser tables.
* \post
* - inadequacy_lists[s->number] now describes all inadequacies that
* manifest in \c s.
* - For every state states[i], annotation_lists[i] now
* contains all annotations associated with all inadequacies that manifest
* in \c s.
* - annotation_counts[i] was incremented by the number of new
* annotations added to states[i].
* - *max_contributionsp is the higher of:
* - The maximum number of contributions computed per annotation.
* - *max_contributionsp \@pre.
* - All memory for all new annotations was allocated on
* \c annotations_obstackp.
*/
void
AnnotationList__compute_from_inadequacies (
state *s, bitsetv follow_kernel_items, bitsetv always_follows,
state ***predecessors, bitset **item_lookahead_sets,
InadequacyList **inadequacy_lists, AnnotationList **annotation_lists,
AnnotationIndex *annotation_counts,
ContributionIndex *max_contributionsp,
struct obstack *annotations_obstackp,
InadequacyListNodeCount *inadequacy_list_node_count);
/**
* \pre
* - self != NULL.
* - \c nitems is the number of kernel items in the LR(0) state that every
* node in the list \c self annotates.
* \post
* - A textual representation of all nodes in the list \c self was printed to
* stderr. \c spaces spaces were printed before each line of the text.
*/
void AnnotationList__debug (AnnotationList const *self, size_t nitems,
int spaces);
/**
* \pre
* - self != NULL.
* - \c nitems is the number of kernel items in the LR(0) state that \c self
* annotates.
* - The number of rows in \c lookahead_filter is at least \c nitems, and the
* number of columns is \c ::ntokens.
* \post
* - lookahead_filter[i][j] is set iff some annotation in the list
* \c self lists token \c j in kernel item \c i as a contributor.
*/
void AnnotationList__computeLookaheadFilter (AnnotationList const *self,
size_t nitems,
bitsetv lookahead_filter);
/**
* \pre
* - self != NULL.
* - \c nitems is the number of kernel items in the LR(0) state that \c self
* annotates.
* - \c lookaheads describes the lookahead sets on the kernel items of some
* isocore of the LR(0) state that \c self annotates. Either:
* - lookaheads = NULL only if the lookahead set on every kernel
* item is empty.
* - For any 0 <= i < nitems, lookaheads[i] is either:
* - \c NULL only if the lookahead set on kernel item \c i is empty.
* - The (possibly empty) lookahead set on kernel item \c i.
* \post
* - If require_split_stable = false, \c result = either:
* - \c ContributionIndex__none iff the state described by \c lookaheads
* makes none of the contributions in \c self.
* - The index of the dominating contribution in \c self that is made by
* that state.
* - \c ContributionIndex__error_action to indicate that the inadequacy
* manifests as a conflict and that a syntax error action (because of a
* %nonassoc) dominates instead.
* - Otherwise, \c result is the same as if require_split_stable =
* false except that it is also \c ContributionIndex__none if there
* are contributions made by the state but the dominating contribution is
* not split-stable. By split-stable, we mean that the dominating
* contribution cannot change due to loss of one or more potential
* contributions due to loss of lookaheads due to splitting of the state.
* - After determining which contributions are actually made by the state,
* the algorithm for determining which contribution dominates in the
* conflict is intended to choose exactly the same action as conflicts.c
* would choose... no matter how crazy conflicts.c's choice is.
*/
ContributionIndex
AnnotationList__computeDominantContribution (AnnotationList const *self,
size_t nitems, bitset *lookaheads,
bool require_split_stable);
#endif /* !ANNOTATION_LIST_H_ */