105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* IELR's inadequacy annotation list. 205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 2009-2012 Free Software Foundation, Inc. 405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 505436638acc7c010349a69c3395f1a57c642dc62Ying Wang This file is part of Bison, the GNU Compiler Compiler. 605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 705436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is free software: you can redistribute it and/or modify 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang it under the terms of the GNU General Public License as published by 905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation, either version 3 of the License, or 1005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 1105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1205436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is distributed in the hope that it will be useful, 1305436638acc7c010349a69c3395f1a57c642dc62Ying Wang but WITHOUT ANY WARRANTY; without even the implied warranty of 1405436638acc7c010349a69c3395f1a57c642dc62Ying Wang MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1505436638acc7c010349a69c3395f1a57c642dc62Ying Wang GNU General Public License for more details. 1605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1705436638acc7c010349a69c3395f1a57c642dc62Ying Wang You should have received a copy of the GNU General Public License 1805436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 1905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#ifndef ANNOTATION_LIST_H_ 2105436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define ANNOTATION_LIST_H_ 2205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2305436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <bitsetv.h> 2405436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "Sbitset.h" 2505436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "InadequacyList.h" 2605436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "state.h" 2705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2805436638acc7c010349a69c3395f1a57c642dc62Ying Wangtypedef unsigned int AnnotationIndex; 2905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3005436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 3105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * A node in a list of annotations on a particular LR(0) state. Each 3205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * annotation records how isocores of that LR(0) state might contribute to an 3305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * individual inadequacy, which might manifest in a different state. Don't 3405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * break encapsulation by modifying the fields directly. Use the provided 3505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * interface functions. 3605436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 3705436638acc7c010349a69c3395f1a57c642dc62Ying Wangtypedef struct AnnotationList 3805436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 3905436638acc7c010349a69c3395f1a57c642dc62Ying Wang /** The next node in the list or \c NULL if none. */ 4005436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct AnnotationList *next; 4105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /** The \c InadequacyList node describing how this inadequacy manifests. */ 4205436638acc7c010349a69c3395f1a57c642dc62Ying Wang InadequacyList *inadequacyNode; 4305436638acc7c010349a69c3395f1a57c642dc62Ying Wang /** 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * List of how the "always", "never", and potential contributions of the 4505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * inadequacy might be made by isocores of the annotated LR(0) state: 4605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The number of rows is the number of contributions. That is, 4705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>AnnotationList::inadequacyNode->contributionCount</tt>. 4805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The token associated with contribution \c i is 4905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>InadequacyList__getContributionToken (AnnotationList::inadequacyNode, i)</tt>. 5005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Iff <tt>AnnotationList::contributions[i] = NULL</tt>, contribution 5105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c i is an "always" contribution. That is, for every isocore of the 5205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * annotated LR(0) state, its core or the core of one its eventual 5305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * successors will definitely make this contribution to the inadequacy. 5405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * It may contribute by either: 5505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Creating a shift of contribution <tt>i</tt>'s token in the state 5605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * that can manifest the inadequacy. 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Propagating that token to the lookahead set of contribution 5805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>i</tt>'s reduction in the state that can manifest the 5905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * inadequacy. 6005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Otherwise: 6105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The number of columns in <tt>AnnotationList::contributions[i]</tt> 6205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * is the number of kernel items in any isocore of the annotated LR(0) 6305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * state. 6405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Iff <tt>AnnotationList::contributions[i]</tt> is empty, contribution 6505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c i is a "never" contribution. That is, no isocore of the 6605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * annotated LR(0) state can make this contribution to the inadequacy. 6705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Otherwise, for each bit \c j that is set in 6805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>AnnotationList::contributions[i]</tt>, if the token associated 6905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * with contribution \c i is present in the lookahead set of kernel 7005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * item \c j of an isocore of the annotated LR(0) state, that isocore 7105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * will make contribution \c i to the inadequacy by propagating the 7205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * contribution's token to the lookahead set of the contribution's 7305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * reduction in the state that can manifest the inadequacy. 7405436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 7505436638acc7c010349a69c3395f1a57c642dc62Ying Wang Sbitset contributions[1]; 7605436638acc7c010349a69c3395f1a57c642dc62Ying Wang} AnnotationList; 7705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 7805436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 7905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 8005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>s != NULL</tt>. 8105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c follow_kernel_items, \c always_follows, and \c predecessors were 8205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * computed by \c ielr_compute_auxiliary_tables. 8305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The size of each of \c annotation_lists and \c annotation_counts is 8405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ::nstates. 8505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - If no \c InadequacyList nodes are currently allocated for the 8605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * parser tables to which \c s belongs, then it is best if 8705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>*inadequacy_list_node_count</tt> is zero to avoid overflow. 8805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * Otherwise, <tt>*inadequacy_list_node_count</tt> has not been 8905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * modified by any function except 9005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c AnnotationList__compute_from_inadequacies since the invocation 9105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * of \c AnnotationList__compute_from_inadequacies that constructed 9205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * the first of the \c InadequacyList nodes currently allocated for 9305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * those parser tables. 9405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 9505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>inadequacy_lists[s->number]</tt> now describes all inadequacies that 9605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * manifest in \c s. 9705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - For every state <tt>states[i]</tt>, <tt>annotation_lists[i]</tt> now 9805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * contains all annotations associated with all inadequacies that manifest 9905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * in \c s. 10005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>annotation_counts[i]</tt> was incremented by the number of new 10105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * annotations added to <tt>states[i]</tt>. 10205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>*max_contributionsp</tt> is the higher of: 10305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The maximum number of contributions computed per annotation. 10405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>*max_contributionsp \@pre</tt>. 10505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - All memory for all new annotations was allocated on 10605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c annotations_obstackp. 10705436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 10805436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 10905436638acc7c010349a69c3395f1a57c642dc62Ying WangAnnotationList__compute_from_inadequacies ( 11005436638acc7c010349a69c3395f1a57c642dc62Ying Wang state *s, bitsetv follow_kernel_items, bitsetv always_follows, 11105436638acc7c010349a69c3395f1a57c642dc62Ying Wang state ***predecessors, bitset **item_lookahead_sets, 11205436638acc7c010349a69c3395f1a57c642dc62Ying Wang InadequacyList **inadequacy_lists, AnnotationList **annotation_lists, 11305436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationIndex *annotation_counts, 11405436638acc7c010349a69c3395f1a57c642dc62Ying Wang ContributionIndex *max_contributionsp, 11505436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct obstack *annotations_obstackp, 11605436638acc7c010349a69c3395f1a57c642dc62Ying Wang InadequacyListNodeCount *inadequacy_list_node_count); 11705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 11805436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 11905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 12005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>self != NULL</tt>. 12105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c nitems is the number of kernel items in the LR(0) state that every 12205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * node in the list \c self annotates. 12305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 12405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - A textual representation of all nodes in the list \c self was printed to 12505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * stderr. \c spaces spaces were printed before each line of the text. 12605436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 12705436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid AnnotationList__debug (AnnotationList const *self, size_t nitems, 12805436638acc7c010349a69c3395f1a57c642dc62Ying Wang int spaces); 12905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 13005436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 13105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 13205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>self != NULL</tt>. 13305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c nitems is the number of kernel items in the LR(0) state that \c self 13405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * annotates. 13505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The number of rows in \c lookahead_filter is at least \c nitems, and the 13605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * number of columns is \c ::ntokens. 13705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 13805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>lookahead_filter[i][j]</tt> is set iff some annotation in the list 13905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c self lists token \c j in kernel item \c i as a contributor. 14005436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 14105436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid AnnotationList__computeLookaheadFilter (AnnotationList const *self, 14205436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t nitems, 14305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv lookahead_filter); 14405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 14505436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 14605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 14705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>self != NULL</tt>. 14805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c nitems is the number of kernel items in the LR(0) state that \c self 14905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * annotates. 15005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c lookaheads describes the lookahead sets on the kernel items of some 15105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * isocore of the LR(0) state that \c self annotates. Either: 15205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel 15305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * item is empty. 15405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> is either: 15505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c NULL only if the lookahead set on kernel item \c i is empty. 15605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The (possibly empty) lookahead set on kernel item \c i. 15705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 15805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - If <tt>require_split_stable = false</tt>, \c result = either: 15905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c ContributionIndex__none iff the state described by \c lookaheads 16005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * makes none of the contributions in \c self. 16105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The index of the dominating contribution in \c self that is made by 16205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * that state. 16305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c ContributionIndex__error_action to indicate that the inadequacy 16405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * manifests as a conflict and that a syntax error action (because of a 16505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * %nonassoc) dominates instead. 16605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Otherwise, \c result is the same as if <tt>require_split_stable = 16705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * false</tt> except that it is also \c ContributionIndex__none if there 16805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * are contributions made by the state but the dominating contribution is 16905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * not split-stable. By split-stable, we mean that the dominating 17005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * contribution cannot change due to loss of one or more potential 17105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * contributions due to loss of lookaheads due to splitting of the state. 17205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - After determining which contributions are actually made by the state, 17305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * the algorithm for determining which contribution dominates in the 17405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * conflict is intended to choose exactly the same action as conflicts.c 17505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * would choose... no matter how crazy conflicts.c's choice is. 17605436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 17705436638acc7c010349a69c3395f1a57c642dc62Ying WangContributionIndex 17805436638acc7c010349a69c3395f1a57c642dc62Ying WangAnnotationList__computeDominantContribution (AnnotationList const *self, 17905436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t nitems, bitset *lookaheads, 18005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool require_split_stable); 18105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 18205436638acc7c010349a69c3395f1a57c642dc62Ying Wang#endif /* !ANNOTATION_LIST_H_ */ 183