| /* IELR's inadequacy annotation list. |
| |
| Copyright (C) 2009-2015, 2018-2019 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 <http://www.gnu.org/licenses/>. */ |
| |
| #include <config.h> |
| #include "system.h" |
| |
| #include "AnnotationList.h" |
| #include "lalr.h" |
| #include "ielr.h" |
| |
| /** |
| * \pre |
| * - <tt>annotations_obstackp != NULL</tt>. |
| * \post |
| * - \c result is a new \c AnnotationList with one node whose: |
| * - \c inadequacyNode member is \c NULL. |
| * - \c contributions member is allocated with \c contribution_count |
| * uninitialized elements. |
| * - All memory was allocated on \c annotations_obstackp. |
| */ |
| static AnnotationList* |
| AnnotationList__alloc_on_obstack (ContributionIndex contribution_count, |
| struct obstack *annotations_obstackp) |
| { |
| AnnotationList *result; |
| size_t contributions_size = |
| contribution_count * sizeof result->contributions[0]; |
| result = obstack_alloc (annotations_obstackp, |
| offsetof (AnnotationList, contributions) |
| + contributions_size); |
| result->next = NULL; |
| result->inadequacyNode = NULL; |
| return result; |
| } |
| |
| /** |
| * \pre |
| * - <tt>self != NULL</tt>. |
| * - <tt>0 <= ci < self->inadequacyNode->contributionCount</tt>. |
| * \post |
| * - \c result = true iff contribution \c ci in \c self represents an |
| * "always" contribution. |
| */ |
| static bool |
| AnnotationList__isContributionAlways (AnnotationList const *self, |
| ContributionIndex ci) |
| { |
| aver (0 <= ci && ci < self->inadequacyNode->contributionCount); |
| return self->contributions[ci] == NULL; |
| } |
| |
| /** |
| * \pre |
| * - \c self is a single node. |
| * - \c self annotates the same state as every other node in \c list, and |
| * that state has \c nitems kernel items. |
| * \post |
| * - If the list \c list already contains an identical annotation to \c self, |
| * \c self was discarded, \c result is false, and the caller is responsible |
| * for the memory of \c self. |
| * - Otherwise, \c list now contains the node \c self, \c result is true, and |
| * \c list assumes responsibility for the memory of \c self. |
| * - The sort in \c list is: |
| * - Sort in reverse order on the unique ID of the associated |
| * inadequacy node. Because these IDs are assigned in ascending |
| * order, this should mean that the insertion position within an |
| * annotation list is usually near the beginning with other |
| * annotations associated with the same inadequacy. |
| * - Next, sort on the first contribution that is different as follows: |
| * - Sort an always-contribution before a never-contribution before a |
| * potential-contribution. |
| * - Two always-contributions are identical. |
| * - Two never-contributions are identical. |
| * - For two potential-contributions, sort on the contributions' kernel |
| * item bitsets interpreted as binary numbers. |
| * - The sorting has a few effects: |
| * - It accelerates elimination of identical annotations during insertion. |
| * - It determines how the output of \c AnnotationList__debug is sorted. |
| * - Other than that, it's probably not important. |
| */ |
| static bool |
| AnnotationList__insertInto (AnnotationList *self, AnnotationList **list, |
| size_t nitems) |
| { |
| AnnotationList **node; |
| for (node = list; *node; node = &(*node)->next) |
| { |
| int cmp = 0; |
| ContributionIndex ci; |
| if (self->inadequacyNode->id < (*node)->inadequacyNode->id) |
| cmp = 1; |
| else if ((*node)->inadequacyNode->id < self->inadequacyNode->id) |
| cmp = -1; |
| else |
| for (ci = 0; |
| cmp == 0 && ci < self->inadequacyNode->contributionCount; |
| ++ci) |
| { |
| if (AnnotationList__isContributionAlways (self, ci)) |
| { |
| if (!AnnotationList__isContributionAlways (*node, ci)) |
| cmp = -1; |
| } |
| else if (AnnotationList__isContributionAlways (*node, ci)) |
| cmp = 1; |
| else |
| { |
| size_t item; |
| for (item = 0; cmp == 0 && item < nitems; ++item) |
| { |
| if (!Sbitset__test (self->contributions[ci], item)) |
| { |
| if (Sbitset__test ((*node)->contributions[ci], item)) |
| cmp = -1; |
| } |
| else if (!Sbitset__test ((*node)->contributions[ci], item)) |
| cmp = 1; |
| } |
| } |
| } |
| if (cmp < 0) |
| { |
| self->next = *node; |
| *node = self; |
| break; |
| } |
| else if (cmp == 0) |
| { |
| self = NULL; |
| break; |
| } |
| } |
| if (!*node) |
| *node = self; |
| return self != NULL; |
| } |
| |
| static bitset |
| AnnotationList__compute_shift_tokens (transitions *trans) |
| { |
| bitset shift_tokens = bitset_create (ntokens, BITSET_FIXED); |
| int i; |
| FOR_EACH_SHIFT (trans, i) |
| bitset_set (shift_tokens, TRANSITION_SYMBOL (trans, i)); |
| return shift_tokens; |
| } |
| |
| static bitset |
| AnnotationList__compute_conflicted_tokens (bitset shift_tokens, |
| reductions *reds) |
| { |
| bitset conflicted_tokens = bitset_create (ntokens, BITSET_FIXED); |
| bitset conflicted_tokens_rule = bitset_create (ntokens, BITSET_FIXED); |
| bitset tokens = bitset_create (ntokens, BITSET_FIXED); |
| |
| bitset_copy (tokens, shift_tokens); |
| for (int i = 0; i < reds->num; ++i) |
| { |
| bitset_and (conflicted_tokens_rule, tokens, reds->lookahead_tokens[i]); |
| bitset_or (conflicted_tokens, |
| conflicted_tokens, conflicted_tokens_rule); |
| bitset_or (tokens, tokens, reds->lookahead_tokens[i]); |
| /* Check that rules are sorted on rule number or the next step in |
| AnnotationList__compute_from_inadequacies will misbehave. */ |
| aver (i == 0 || reds->rules[i-1] < reds->rules[i]); |
| } |
| |
| bitset_free (tokens); |
| bitset_free (conflicted_tokens_rule); |
| |
| return conflicted_tokens; |
| } |
| |
| static bool |
| AnnotationList__compute_lhs_contributions (state *s, rule *the_rule, |
| symbol_number conflicted_token, |
| bitsetv follow_kernel_items, |
| bitsetv always_follows, |
| state ***predecessors, |
| bitset **item_lookahead_sets, |
| Sbitset *items, |
| struct obstack |
| *annotations_obstackp) |
| { |
| goto_number lhs_goto = map_goto (s->number, the_rule->lhs->number); |
| if (bitset_test (always_follows[lhs_goto], conflicted_token)) |
| return true; |
| *items = Sbitset__new_on_obstack (s->nitems, annotations_obstackp); |
| { |
| bitset_iterator biter_item; |
| bitset_bindex item; |
| BITSET_FOR_EACH (biter_item, follow_kernel_items[lhs_goto], item, 0) |
| if (ielr_item_has_lookahead (s, 0, item, conflicted_token, |
| predecessors, item_lookahead_sets)) |
| Sbitset__set (*items, item); |
| } |
| return false; |
| } |
| |
| static void |
| AnnotationList__computePredecessorAnnotations ( |
| AnnotationList *self, state *s, |
| bitsetv follow_kernel_items, |
| bitsetv always_follows, |
| state ***predecessors, |
| bitset **item_lookahead_sets, |
| AnnotationList **annotation_lists, |
| AnnotationIndex *annotation_counts, |
| struct obstack *annotations_obstackp) |
| { |
| for (state **predecessor = predecessors[s->number]; *predecessor; ++predecessor) |
| { |
| AnnotationList *annotation_node = |
| AnnotationList__alloc_on_obstack ( |
| self->inadequacyNode->contributionCount, annotations_obstackp); |
| annotation_node->inadequacyNode = self->inadequacyNode; |
| bool potential_contribution = false; |
| bitset *lookaheads = NULL; |
| { |
| for (ContributionIndex ci = 0; ci < self->inadequacyNode->contributionCount; ++ci) |
| { |
| symbol_number contribution_token = |
| InadequacyList__getContributionToken (self->inadequacyNode, ci) |
| ->content->number; |
| if (AnnotationList__isContributionAlways (self, ci)) |
| { |
| annotation_node->contributions[ci] = NULL; |
| continue; |
| } |
| annotation_node->contributions[ci] = |
| Sbitset__new_on_obstack ((*predecessor)->nitems, |
| annotations_obstackp); |
| { |
| size_t predecessor_item = 0; |
| Sbitset sbiter_item; |
| Sbitset__Index self_item; |
| SBITSET__FOR_EACH (self->contributions[ci], s->nitems, |
| sbiter_item, self_item) |
| { |
| /* If this kernel item is the beginning of a RHS, it must be |
| the kernel item in the start state, and so it has an empty |
| lookahead set. Thus, it can't contribute to inadequacies, |
| and so it should never have been identified as a |
| contribution. If, instead, this kernel item is the |
| successor of the start state's kernel item, the lookahead |
| set is still empty, and so it also should never have been |
| identified as a contribution. This situation is fortunate |
| because we want to avoid the - 2 below in both cases. */ |
| aver (s->items[self_item] > 1); |
| /* If this kernel item is next to the beginning of the RHS, |
| then check all of the predecessor's goto follows for the |
| LHS. */ |
| if (item_number_is_rule_number (ritem[s->items[self_item] |
| - 2])) |
| { |
| int rulei; |
| for (rulei = s->items[self_item]; |
| !item_number_is_rule_number (ritem[rulei]); |
| ++rulei) |
| continue; |
| Sbitset items; |
| if (AnnotationList__compute_lhs_contributions ( |
| *predecessor, |
| &rules[item_number_as_rule_number (ritem[rulei])], |
| contribution_token, |
| follow_kernel_items, always_follows, predecessors, |
| item_lookahead_sets, &items, annotations_obstackp)) |
| { |
| obstack_free (annotations_obstackp, |
| annotation_node->contributions[ci]); |
| annotation_node->contributions[ci] = NULL; |
| break; |
| } |
| else |
| { |
| Sbitset__or (annotation_node->contributions[ci], |
| annotation_node->contributions[ci], |
| items, (*predecessor)->nitems); |
| obstack_free (annotations_obstackp, items); |
| } |
| } |
| /* If this kernel item is later in the RHS, then check the |
| predecessor item's lookahead set. */ |
| else |
| { |
| /* We don't have to start the predecessor item search at |
| the beginning every time because items from both |
| states are sorted by their indices in ritem. */ |
| for (; |
| predecessor_item < (*predecessor)->nitems; |
| ++predecessor_item) |
| if ((*predecessor)->items[predecessor_item] |
| == s->items[self_item] - 1) |
| break; |
| aver (predecessor_item != (*predecessor)->nitems); |
| if (ielr_item_has_lookahead (*predecessor, 0, |
| predecessor_item, |
| contribution_token, |
| predecessors, |
| item_lookahead_sets)) |
| Sbitset__set (annotation_node->contributions[ci], |
| predecessor_item); |
| } |
| } |
| } |
| if (annotation_node->contributions[ci]) |
| { |
| Sbitset biter; |
| Sbitset__Index i; |
| SBITSET__FOR_EACH (annotation_node->contributions[ci], |
| (*predecessor)->nitems, biter, i) |
| { |
| potential_contribution = true; |
| if (!lookaheads) |
| { |
| lookaheads = xnmalloc ((*predecessor)->nitems, |
| sizeof *lookaheads); |
| for (size_t j = 0; j < (*predecessor)->nitems; ++j) |
| lookaheads[j] = NULL; |
| } |
| if (!lookaheads[i]) |
| lookaheads[i] = bitset_create (ntokens, BITSET_FIXED); |
| bitset_set (lookaheads[i], contribution_token); |
| } |
| } |
| } |
| } |
| |
| /* If the predecessor has any contributions besides just "always" and |
| "never" contributions: |
| - If the dominant contribution is split-stable, the annotation could |
| not affect merging on this predecessor state or its eventual |
| predecessor states. Moreover, all contributions that affect |
| whether the dominant contribution remains dominant must be "always" |
| or "never" contributions in order for the dominant contribution to |
| be split-stable. Thus, the dominant contribution computation result |
| in eventual successor states will not be affected by lookaheads |
| tracked for this predecessor state. (Also, as in the isocore |
| compatibility test, we depend on the fact that isocores with equal |
| dominant contributions will have the same dominant contribution when |
| merged. Otherwise, we might have to worry that the presence of a |
| potential contribution might somehow be the culprit of that behavior |
| and thus need to be tracked regardless of the split stability of the |
| dominant contribution.) Thus, go ahead and discard the annotation |
| to save space now plus time during state splitting. |
| - Otherwise, record the annotation, and compute any resulting |
| annotations needed on predecessor states. */ |
| if (potential_contribution) |
| { |
| if (ContributionIndex__none |
| != AnnotationList__computeDominantContribution ( |
| annotation_node, (*predecessor)->nitems, lookaheads, true)) |
| { |
| obstack_free (annotations_obstackp, annotation_node); |
| annotation_node = NULL; |
| } |
| { |
| for (size_t i = 0; i < (*predecessor)->nitems; ++i) |
| if (lookaheads[i]) |
| bitset_free (lookaheads[i]); |
| free (lookaheads); |
| } |
| if (annotation_node) |
| { |
| if (AnnotationList__insertInto (annotation_node, |
| &annotation_lists[(*predecessor) |
| ->number], |
| (*predecessor)->nitems)) |
| { |
| ++annotation_counts[(*predecessor)->number]; |
| AnnotationList__computePredecessorAnnotations ( |
| annotation_node, *predecessor, |
| follow_kernel_items, always_follows, predecessors, |
| item_lookahead_sets, annotation_lists, annotation_counts, |
| annotations_obstackp); |
| } |
| else |
| obstack_free (annotations_obstackp, annotation_node); |
| } |
| } |
| else |
| obstack_free (annotations_obstackp, annotation_node); |
| } |
| } |
| |
| 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) |
| { |
| /* Return an empty list if s->lookahead_tokens = NULL. */ |
| if (s->consistent) |
| return; |
| |
| bitsetv all_lookaheads = bitsetv_create (s->nitems, ntokens, BITSET_FIXED); |
| bitsetv_ones (all_lookaheads); |
| bitset shift_tokens = AnnotationList__compute_shift_tokens (s->transitions); |
| bitset conflicted_tokens = |
| AnnotationList__compute_conflicted_tokens (shift_tokens, s->reductions); |
| |
| /* Add an inadequacy annotation for each conflicted_token. */ |
| bitset_iterator biter_conflict; |
| bitset_bindex conflicted_token; |
| BITSET_FOR_EACH (biter_conflict, conflicted_tokens, conflicted_token, 0) |
| { |
| AnnotationList *annotation_node; |
| /* FIXME: Would a BITSET_FRUGAL or BITEST_SPARSE be more efficient? Now |
| or convert it inside InadequacyList__new_conflict? */ |
| bitset actions = bitset_create (s->reductions->num + 1, BITSET_FIXED); |
| ContributionIndex contribution_count = 0; |
| bool potential_contribution = false; |
| |
| /* Allocate the annotation node. */ |
| { |
| for (int rule_i = 0; rule_i < s->reductions->num; ++rule_i) |
| if (bitset_test (s->reductions->lookahead_tokens[rule_i], |
| conflicted_token)) |
| ++contribution_count; |
| if (bitset_test (shift_tokens, conflicted_token)) |
| ++contribution_count; |
| annotation_node = |
| AnnotationList__alloc_on_obstack (contribution_count, |
| annotations_obstackp); |
| } |
| |
| /* Add a contribution for each reduction that has conflicted_token as a |
| lookahead. */ |
| { |
| ContributionIndex ci = 0; |
| int item_i = 0; |
| for (int rule_i = 0; rule_i < s->reductions->num; ++rule_i) |
| { |
| rule *the_rule = s->reductions->rules[rule_i]; |
| if (bitset_test (s->reductions->lookahead_tokens[rule_i], |
| conflicted_token)) |
| { |
| bitset_set (actions, rule_i); |
| /* If this reduction is on a kernel item, just add it. */ |
| if (!item_number_is_rule_number (the_rule->rhs[0])) |
| { |
| annotation_node->contributions[ci] = |
| Sbitset__new_on_obstack (s->nitems, |
| annotations_obstackp); |
| /* Catch item_i up to rule_i. This works because both are |
| sorted on rule number. */ |
| while (!item_number_is_rule_number ( |
| ritem[s->items[item_i]]) |
| || item_number_as_rule_number ( |
| ritem[s->items[item_i]]) |
| != the_rule->number) |
| { |
| ++item_i; |
| aver (item_i < s->nitems); |
| } |
| Sbitset__set (annotation_node->contributions[ci], item_i); |
| } |
| /* Otherwise, add the kernel items whose lookahead sets |
| contribute the conflicted token to this reduction's |
| lookahead set. */ |
| else if (AnnotationList__compute_lhs_contributions ( |
| s, the_rule, conflicted_token, follow_kernel_items, |
| always_follows, predecessors, item_lookahead_sets, |
| &annotation_node->contributions[ci], |
| annotations_obstackp)) |
| { |
| annotation_node->contributions[ci++] = NULL; |
| continue; |
| } |
| /* The lookahead token has to come from somewhere. */ |
| aver (!Sbitset__isEmpty (annotation_node->contributions[ci], |
| s->nitems)); |
| ++ci; |
| potential_contribution = true; |
| } |
| } |
| } |
| |
| /* If there are any contributions besides just "always" contributions: |
| - If there's also a shift contribution, record it. |
| - If the dominant contribution is split-stable, then the annotation |
| could not affect merging, so go ahead and discard the annotation and |
| the inadequacy to save space now plus time during state splitting. |
| - Otherwise, record the annotation and the inadequacy, and compute any |
| resulting annotations needed on predecessor states. */ |
| if (potential_contribution) |
| { |
| if (bitset_test (shift_tokens, conflicted_token)) |
| { |
| bitset_set (actions, s->reductions->num); |
| annotation_node->contributions[contribution_count - 1] = NULL; |
| } |
| { |
| InadequacyList *conflict_node = |
| InadequacyList__new_conflict ( |
| s, symbols[conflicted_token], actions, |
| inadequacy_list_node_count); |
| actions = NULL; |
| annotation_node->inadequacyNode = conflict_node; |
| if (ContributionIndex__none |
| != AnnotationList__computeDominantContribution ( |
| annotation_node, s->nitems, all_lookaheads, true)) |
| { |
| obstack_free (annotations_obstackp, annotation_node); |
| InadequacyList__delete (conflict_node); |
| } |
| else |
| { |
| InadequacyList__prependTo (conflict_node, |
| &inadequacy_lists[s->number]); |
| { |
| bool b = |
| AnnotationList__insertInto (annotation_node, |
| &annotation_lists[s->number], |
| s->nitems); |
| aver (b); (void) b; |
| } |
| /* This aver makes sure the |
| AnnotationList__computeDominantContribution check above |
| does discard annotations in the simplest case of a S/R |
| conflict with no token precedence. */ |
| aver (!bitset_test (shift_tokens, conflicted_token) |
| || symbols[conflicted_token]->content->prec); |
| ++annotation_counts[s->number]; |
| if (contribution_count > *max_contributionsp) |
| *max_contributionsp = contribution_count; |
| AnnotationList__computePredecessorAnnotations ( |
| annotation_node, s, |
| follow_kernel_items, always_follows, predecessors, |
| item_lookahead_sets, annotation_lists, annotation_counts, |
| annotations_obstackp); |
| } |
| } |
| } |
| else |
| { |
| bitset_free (actions); |
| obstack_free (annotations_obstackp, annotation_node); |
| } |
| } |
| |
| bitsetv_free (all_lookaheads); |
| bitset_free (shift_tokens); |
| bitset_free (conflicted_tokens); |
| } |
| |
| void |
| AnnotationList__debug (AnnotationList const *self, size_t nitems, int spaces) |
| { |
| AnnotationList const *a; |
| AnnotationIndex ai; |
| for (a = self, ai = 0; a; a = a->next, ++ai) |
| { |
| for (int j = 0; j < spaces; ++j) |
| putc (' ', stderr); |
| fprintf (stderr, "Annotation %d (manifesting state %d):\n", |
| ai, a->inadequacyNode->manifestingState->number); |
| { |
| bitset_bindex rulei |
| = bitset_first (a->inadequacyNode->inadequacy.conflict.actions); |
| for (ContributionIndex ci = 0; ci < a->inadequacyNode->contributionCount; ++ci) |
| { |
| symbol_number token = |
| InadequacyList__getContributionToken (a->inadequacyNode, ci) |
| ->content->number; |
| for (int j = 0; j < spaces+2; ++j) |
| putc (' ', stderr); |
| if (ci == InadequacyList__getShiftContributionIndex ( |
| a->inadequacyNode)) |
| fprintf (stderr, "Contributes shift of token %d.\n", token); |
| else |
| { |
| fprintf (stderr, "Contributes token %d", token); |
| aver (rulei != BITSET_BINDEX_MAX); |
| fprintf (stderr, " as lookahead, rule number %d", |
| a->inadequacyNode->manifestingState |
| ->reductions->rules[rulei]->number); |
| rulei = |
| bitset_next (a->inadequacyNode->inadequacy.conflict.actions, |
| rulei+1); |
| if (AnnotationList__isContributionAlways (a, ci)) |
| fprintf (stderr, " always."); |
| else |
| { |
| fprintf (stderr, ", items: "); |
| Sbitset__fprint (a->contributions[ci], nitems, stderr); |
| } |
| fprintf (stderr, "\n"); |
| } |
| } |
| } |
| } |
| } |
| |
| void |
| AnnotationList__computeLookaheadFilter (AnnotationList const *self, |
| size_t nitems, |
| bitsetv lookahead_filter) |
| { |
| bitsetv_zero (lookahead_filter); |
| for (; self; self = self->next) |
| for (ContributionIndex ci = 0; ci < self->inadequacyNode->contributionCount; ++ci) |
| if (!AnnotationList__isContributionAlways (self, ci)) |
| { |
| symbol_number token = |
| InadequacyList__getContributionToken (self->inadequacyNode, ci) |
| ->content->number; |
| Sbitset__Index item; |
| Sbitset biter; |
| SBITSET__FOR_EACH (self->contributions[ci], nitems, biter, item) |
| bitset_set (lookahead_filter[item], token); |
| } |
| } |
| |
| /** |
| * \pre |
| * - <tt>self != NULL</tt>. |
| * - \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: |
| * - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel |
| * item is empty. |
| * - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> 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. |
| * - <tt>0 <= ci < self->inadequacyNode->contributionCount</tt>. |
| * \post |
| * - \c result = true iff contribution \c ci in \c self is made by the state |
| * described by \c lookaheads. |
| */ |
| static bool |
| AnnotationList__stateMakesContribution (AnnotationList const *self, |
| size_t nitems, ContributionIndex ci, |
| bitset *lookaheads) |
| { |
| if (AnnotationList__isContributionAlways (self, ci)) |
| return true; |
| if (!lookaheads) |
| return false; |
| { |
| symbol_number token = |
| InadequacyList__getContributionToken (self->inadequacyNode, ci) |
| ->content->number; |
| Sbitset__Index item; |
| Sbitset biter; |
| SBITSET__FOR_EACH (self->contributions[ci], nitems, biter, item) |
| if (lookaheads[item] && bitset_test (lookaheads[item], token)) |
| return true; |
| } |
| return false; |
| } |
| |
| ContributionIndex |
| AnnotationList__computeDominantContribution (AnnotationList const *self, |
| size_t nitems, bitset *lookaheads, |
| bool require_split_stable) |
| { |
| ContributionIndex const ci_shift = |
| InadequacyList__getShiftContributionIndex (self->inadequacyNode); |
| |
| symbol *token = self->inadequacyNode->inadequacy.conflict.token; |
| |
| /* S/R conflict. */ |
| if (ci_shift != ContributionIndex__none) |
| { |
| bool find_stable_domination_over_shift = false; |
| bool find_stable_error_action_domination = false; |
| { |
| int shift_precedence = token->content->prec; |
| |
| /* If the token has no precedence set, shift is always chosen. */ |
| if (!shift_precedence) |
| return ci_shift; |
| |
| /* Figure out which reductions contribute, which of those would |
| dominate in a R/R comparison, and whether any reduction dominates |
| the shift so that the R/R comparison is actually needed. */ |
| ContributionIndex ci_rr_dominator = ContributionIndex__none; |
| int actioni; |
| ContributionIndex ci; |
| for (ci = 0, |
| actioni = bitset_first (self->inadequacyNode->inadequacy |
| .conflict.actions); |
| ci < self->inadequacyNode->contributionCount; |
| ++ci, |
| actioni = bitset_next (self->inadequacyNode->inadequacy |
| .conflict.actions, actioni+1)) |
| { |
| int reduce_precedence = 0; |
| if (ci == ci_shift) |
| continue; |
| { |
| rule *r = self->inadequacyNode->manifestingState |
| ->reductions->rules[actioni]; |
| if (r->prec) |
| reduce_precedence = r->prec->prec; |
| } |
| /* If there's no need to check whether this reduction actually |
| contributes because the shift eliminates it from the R/R |
| comparison anyway, continue to the next reduction. */ |
| if (reduce_precedence |
| && (reduce_precedence < shift_precedence |
| || (reduce_precedence == shift_precedence |
| && token->content->assoc == right_assoc))) |
| continue; |
| if (!AnnotationList__stateMakesContribution (self, nitems, ci, |
| lookaheads)) |
| continue; |
| /* This uneliminated reduction contributes, so see if it can cause |
| an error action. */ |
| if (reduce_precedence == shift_precedence |
| && token->content->assoc == non_assoc) |
| { |
| /* It's not possible to find split-stable domination over |
| shift after a potential %nonassoc. */ |
| if (find_stable_domination_over_shift) |
| return ContributionIndex__none; |
| if (!require_split_stable |
| || AnnotationList__isContributionAlways (self, ci)) |
| return ContributionIndex__error_action; |
| find_stable_error_action_domination = true; |
| } |
| /* Consider this uneliminated contributing reduction in the R/R |
| comparison. */ |
| if (ci_rr_dominator == ContributionIndex__none) |
| ci_rr_dominator = ci; |
| /* If precedence is set for this uneliminated contributing |
| reduction, it dominates the shift, so try to figure out which |
| reduction dominates the R/R comparison. */ |
| if (reduce_precedence) |
| { |
| /* It's not possible to find split-stable error action |
| domination after a potential reduction. */ |
| if (find_stable_error_action_domination) |
| return ContributionIndex__none; |
| if (!require_split_stable) |
| return ci_rr_dominator; |
| if (!AnnotationList__isContributionAlways (self, |
| ci_rr_dominator)) |
| return ContributionIndex__none; |
| if (AnnotationList__isContributionAlways (self, ci)) |
| return ci_rr_dominator; |
| find_stable_domination_over_shift = true; |
| } |
| } |
| } |
| if (find_stable_domination_over_shift |
| || find_stable_error_action_domination) |
| return ContributionIndex__none; |
| /* No reduce or error action domination found, so shift dominates. */ |
| return ci_shift; |
| } |
| |
| /* R/R conflict, so the reduction with the lowest rule number dominates. |
| Fortunately, contributions are sorted by rule number. */ |
| for (ContributionIndex ci = 0; ci < self->inadequacyNode->contributionCount; ++ci) |
| if (AnnotationList__stateMakesContribution (self, nitems, ci, |
| lookaheads)) |
| { |
| if (require_split_stable |
| && !AnnotationList__isContributionAlways (self, ci)) |
| return ContributionIndex__none; |
| return ci; |
| } |
| return ContributionIndex__none; |
| } |
