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#include <config.h> 21#include "system.h" 22 23#include "AnnotationList.h" 24#include "lalr.h" 25#include "ielr.h" 26 27/** 28 * \pre 29 * - <tt>annotations_obstackp != NULL</tt>. 30 * \post 31 * - \c result is a new \c AnnotationList with one node whose: 32 * - \c inadequacyNode member is \c NULL. 33 * - \c contributions member is allocated with \c contribution_count 34 * uninitialized elements. 35 * - All memory was allocated on \c annotations_obstackp. 36 */ 37static AnnotationList* 38AnnotationList__alloc_on_obstack (ContributionIndex contribution_count, 39 struct obstack *annotations_obstackp) 40{ 41 AnnotationList *result; 42 size_t contributions_size = 43 contribution_count * sizeof result->contributions[0]; 44 result = obstack_alloc (annotations_obstackp, 45 offsetof (AnnotationList, contributions) 46 + contributions_size); 47 result->next = NULL; 48 result->inadequacyNode = NULL; 49 return result; 50} 51 52/** 53 * \pre 54 * - <tt>self != NULL</tt>. 55 * - <tt>0 <= ci < self->inadequacyNode->contributionCount</tt>. 56 * \post 57 * - \c result = true iff contribution \c ci in \c self represents an 58 * "always" contribution. 59 */ 60static bool 61AnnotationList__isContributionAlways (AnnotationList const *self, 62 ContributionIndex ci) 63{ 64 aver (0 <= ci && ci < self->inadequacyNode->contributionCount); 65 return self->contributions[ci] == NULL; 66} 67 68/** 69 * \pre 70 * - \c self is a single node. 71 * - \c self annotates the same state as every other node in \c list, and 72 * that state has \c nitems kernel items. 73 * \post 74 * - If the list \c list already contains an identical annotation to \c self, 75 * \c self was discarded, \c result is false, and the caller is responsible 76 * for the memory of \c self. 77 * - Otherwise, \c list now contains the node \c self, \c result is true, and 78 * \c list assumes responsibility for the memory of \c self. 79 * - The sort in \c list is: 80 * - Sort in reverse order on the unique ID of the associated 81 * inadequacy node. Because these IDs are assigned in ascending 82 * order, this should mean that the insertion position within an 83 * annotation list is usually near the beginning with other 84 * annotations associated with the same inadequacy. 85 * - Next, sort on the first contribution that is different as follows: 86 * - Sort an always-contribution before a never-contribution before a 87 * potential-contribution. 88 * - Two always-contributions are identical. 89 * - Two never-contributions are identical. 90 * - For two potential-contributions, sort on the contributions' kernel 91 * item bitsets interpreted as binary numbers. 92 * - The sorting has a few effects: 93 * - It accelerates elimination of identical annotations during insertion. 94 * - It determines how the output of \c AnnotationList__debug is sorted. 95 * - Other than that, it's probably not important. 96 */ 97static bool 98AnnotationList__insertInto (AnnotationList *self, AnnotationList **list, 99 size_t nitems) 100{ 101 AnnotationList **node; 102 for (node = list; *node; node = &(*node)->next) 103 { 104 int cmp = 0; 105 ContributionIndex ci; 106 if (self->inadequacyNode->id < (*node)->inadequacyNode->id) 107 cmp = 1; 108 else if ((*node)->inadequacyNode->id < self->inadequacyNode->id) 109 cmp = -1; 110 else 111 for (ci = 0; 112 cmp == 0 && ci < self->inadequacyNode->contributionCount; 113 ++ci) 114 { 115 if (AnnotationList__isContributionAlways (self, ci)) 116 { 117 if (!AnnotationList__isContributionAlways (*node, ci)) 118 cmp = -1; 119 } 120 else if (AnnotationList__isContributionAlways (*node, ci)) 121 cmp = 1; 122 else 123 { 124 size_t item; 125 for (item = 0; cmp == 0 && item < nitems; ++item) 126 { 127 if (!Sbitset__test (self->contributions[ci], item)) 128 { 129 if (Sbitset__test ((*node)->contributions[ci], item)) 130 cmp = -1; 131 } 132 else if (!Sbitset__test ((*node)->contributions[ci], item)) 133 cmp = 1; 134 } 135 } 136 } 137 if (cmp < 0) 138 { 139 self->next = *node; 140 *node = self; 141 break; 142 } 143 else if (cmp == 0) 144 { 145 self = NULL; 146 break; 147 } 148 } 149 if (!*node) 150 *node = self; 151 return self != NULL; 152} 153 154static bitset 155AnnotationList__compute_shift_tokens (transitions *trans) 156{ 157 bitset shift_tokens = bitset_create (ntokens, BITSET_FIXED); 158 int i; 159 FOR_EACH_SHIFT (trans, i) 160 bitset_set (shift_tokens, TRANSITION_SYMBOL (trans, i)); 161 return shift_tokens; 162} 163 164static bitset 165AnnotationList__compute_conflicted_tokens (bitset shift_tokens, 166 reductions *reds) 167{ 168 bitset conflicted_tokens = bitset_create (ntokens, BITSET_FIXED); 169 bitset conflicted_tokens_rule = bitset_create (ntokens, BITSET_FIXED); 170 bitset tokens = bitset_create (ntokens, BITSET_FIXED); 171 int i; 172 173 bitset_copy (tokens, shift_tokens); 174 for (i = 0; i < reds->num; ++i) 175 { 176 bitset_and (conflicted_tokens_rule, tokens, reds->lookahead_tokens[i]); 177 bitset_or (conflicted_tokens, 178 conflicted_tokens, conflicted_tokens_rule); 179 bitset_or (tokens, tokens, reds->lookahead_tokens[i]); 180 /* Check that rules are sorted on rule number or the next step in 181 AnnotationList__compute_from_inadequacies will misbehave. */ 182 aver (i == 0 || reds->rules[i-1] < reds->rules[i]); 183 } 184 185 bitset_free (tokens); 186 bitset_free (conflicted_tokens_rule); 187 188 return conflicted_tokens; 189} 190 191static bool 192AnnotationList__compute_lhs_contributions (state *s, rule *the_rule, 193 symbol_number conflicted_token, 194 bitsetv follow_kernel_items, 195 bitsetv always_follows, 196 state ***predecessors, 197 bitset **item_lookahead_sets, 198 Sbitset *items, 199 struct obstack 200 *annotations_obstackp) 201{ 202 goto_number lhs_goto = map_goto (s->number, the_rule->lhs->number); 203 if (bitset_test (always_follows[lhs_goto], conflicted_token)) 204 return true; 205 *items = Sbitset__new_on_obstack (s->nitems, annotations_obstackp); 206 { 207 bitset_iterator biter_item; 208 bitset_bindex item; 209 BITSET_FOR_EACH (biter_item, follow_kernel_items[lhs_goto], item, 0) 210 if (ielr_item_has_lookahead (s, 0, item, conflicted_token, 211 predecessors, item_lookahead_sets)) 212 Sbitset__set (*items, item); 213 } 214 return false; 215} 216 217static void 218AnnotationList__computePredecessorAnnotations (AnnotationList *self, state *s, 219 bitsetv follow_kernel_items, 220 bitsetv always_follows, 221 state ***predecessors, 222 bitset **item_lookahead_sets, 223 AnnotationList 224 **annotation_lists, 225 AnnotationIndex 226 *annotation_counts, 227 struct obstack 228 *annotations_obstackp) 229{ 230 state **predecessor; 231 for (predecessor = predecessors[s->number]; *predecessor; ++predecessor) 232 { 233 AnnotationList *annotation_node = 234 AnnotationList__alloc_on_obstack ( 235 self->inadequacyNode->contributionCount, annotations_obstackp); 236 annotation_node->inadequacyNode = self->inadequacyNode; 237 bool potential_contribution = false; 238 bitset *lookaheads = NULL; 239 { 240 ContributionIndex ci; 241 for (ci = 0; ci < self->inadequacyNode->contributionCount; ++ci) 242 { 243 symbol_number contribution_token = 244 InadequacyList__getContributionToken (self->inadequacyNode, ci) 245 ->number; 246 if (AnnotationList__isContributionAlways (self, ci)) 247 { 248 annotation_node->contributions[ci] = NULL; 249 continue; 250 } 251 annotation_node->contributions[ci] = 252 Sbitset__new_on_obstack ((*predecessor)->nitems, 253 annotations_obstackp); 254 { 255 size_t predecessor_item = 0; 256 Sbitset sbiter_item; 257 Sbitset__Index self_item; 258 SBITSET__FOR_EACH (self->contributions[ci], s->nitems, 259 sbiter_item, self_item) 260 { 261 /* If this kernel item is the beginning of a RHS, it must be 262 the kernel item in the start state, and so it has an empty 263 lookahead set. Thus, it can't contribute to inadequacies, 264 and so it should never have been identified as a 265 contribution. If, instead, this kernel item is the 266 successor of the start state's kernel item, the lookahead 267 set is still empty, and so it also should never have been 268 identified as a contribution. This situation is fortunate 269 because we want to avoid the - 2 below in both cases. */ 270 aver (s->items[self_item] > 1); 271 /* If this kernel item is next to the beginning of the RHS, 272 then check all of the predecessor's goto follows for the 273 LHS. */ 274 if (item_number_is_rule_number (ritem[s->items[self_item] 275 - 2])) 276 { 277 Sbitset items; 278 unsigned int rulei; 279 for (rulei = s->items[self_item]; 280 !item_number_is_rule_number (ritem[rulei]); 281 ++rulei) 282 ; 283 if (AnnotationList__compute_lhs_contributions ( 284 *predecessor, 285 &rules[item_number_as_rule_number (ritem[rulei])], 286 contribution_token, 287 follow_kernel_items, always_follows, predecessors, 288 item_lookahead_sets, &items, annotations_obstackp)) 289 { 290 obstack_free (annotations_obstackp, 291 annotation_node->contributions[ci]); 292 annotation_node->contributions[ci] = NULL; 293 break; 294 } 295 else 296 { 297 Sbitset__or (annotation_node->contributions[ci], 298 annotation_node->contributions[ci], 299 items, (*predecessor)->nitems); 300 obstack_free (annotations_obstackp, items); 301 } 302 } 303 /* If this kernel item is later in the RHS, then check the 304 predecessor item's lookahead set. */ 305 else 306 { 307 /* We don't have to start the predecessor item search at 308 the beginning every time because items from both 309 states are sorted by their indices in ritem. */ 310 for (; 311 predecessor_item < (*predecessor)->nitems; 312 ++predecessor_item) 313 if ((*predecessor)->items[predecessor_item] 314 == s->items[self_item] - 1) 315 break; 316 aver (predecessor_item != (*predecessor)->nitems); 317 if (ielr_item_has_lookahead (*predecessor, 0, 318 predecessor_item, 319 contribution_token, 320 predecessors, 321 item_lookahead_sets)) 322 Sbitset__set (annotation_node->contributions[ci], 323 predecessor_item); 324 } 325 } 326 } 327 if (annotation_node->contributions[ci]) 328 { 329 Sbitset biter; 330 Sbitset__Index i; 331 SBITSET__FOR_EACH (annotation_node->contributions[ci], 332 (*predecessor)->nitems, biter, i) 333 { 334 potential_contribution = true; 335 if (!lookaheads) 336 { 337 size_t j; 338 lookaheads = xnmalloc ((*predecessor)->nitems, 339 sizeof *lookaheads); 340 for (j = 0; j < (*predecessor)->nitems; ++j) 341 lookaheads[j] = NULL; 342 } 343 if (!lookaheads[i]) 344 lookaheads[i] = bitset_create (ntokens, BITSET_FIXED); 345 bitset_set (lookaheads[i], contribution_token); 346 } 347 } 348 } 349 } 350 351 /* If the predecessor has any contributions besides just "always" and 352 "never" contributions: 353 - If the dominant contribution is split-stable, the annotation could 354 not affect merging on this predecessor state or its eventual 355 predecessor states. Moreover, all contributions that affect 356 whether the dominant contribution remains dominant must be "always" 357 or "never" contributions in order for the dominant contribution to 358 be split-stable. Thus, the dominant contribution computation result 359 in eventual successor states will not be affected by lookaheads 360 tracked for this predecessor state. (Also, as in the isocore 361 compatibility test, we depend on the fact that isocores with equal 362 dominant contributions will have the same dominant contribution when 363 merged. Otherwise, we might have to worry that the presence of a 364 potential contribution might somehow be the culprit of that behavior 365 and thus need to be tracked regardless of the split stability of the 366 dominant contribution.) Thus, go ahead and discard the annotation 367 to save space now plus time during state splitting. 368 - Otherwise, record the annotation, and compute any resulting 369 annotations needed on predecessor states. */ 370 if (potential_contribution) 371 { 372 if (ContributionIndex__none 373 != AnnotationList__computeDominantContribution ( 374 annotation_node, (*predecessor)->nitems, lookaheads, true)) 375 { 376 obstack_free (annotations_obstackp, annotation_node); 377 annotation_node = NULL; 378 } 379 { 380 size_t i; 381 for (i = 0; i < (*predecessor)->nitems; ++i) 382 if (lookaheads[i]) 383 bitset_free (lookaheads[i]); 384 free (lookaheads); 385 } 386 if (annotation_node) 387 { 388 if (AnnotationList__insertInto (annotation_node, 389 &annotation_lists[(*predecessor) 390 ->number], 391 (*predecessor)->nitems)) 392 { 393 ++annotation_counts[(*predecessor)->number]; 394 AnnotationList__computePredecessorAnnotations ( 395 annotation_node, *predecessor, 396 follow_kernel_items, always_follows, predecessors, 397 item_lookahead_sets, annotation_lists, annotation_counts, 398 annotations_obstackp); 399 } 400 else 401 obstack_free (annotations_obstackp, annotation_node); 402 } 403 } 404 else 405 obstack_free (annotations_obstackp, annotation_node); 406 } 407} 408 409void 410AnnotationList__compute_from_inadequacies ( 411 state *s, bitsetv follow_kernel_items, bitsetv always_follows, 412 state ***predecessors, bitset **item_lookahead_sets, 413 InadequacyList **inadequacy_lists, AnnotationList **annotation_lists, 414 AnnotationIndex *annotation_counts, 415 ContributionIndex *max_contributionsp, 416 struct obstack *annotations_obstackp, 417 InadequacyListNodeCount *inadequacy_list_node_count) 418{ 419 bitsetv all_lookaheads; 420 bitset shift_tokens; 421 bitset conflicted_tokens; 422 bitset_iterator biter_conflict; 423 bitset_bindex conflicted_token; 424 425 /* Return an empty list if s->lookahead_tokens = NULL. */ 426 if (s->consistent) 427 return; 428 429 all_lookaheads = bitsetv_create (s->nitems, ntokens, BITSET_FIXED); 430 bitsetv_ones (all_lookaheads); 431 shift_tokens = AnnotationList__compute_shift_tokens (s->transitions); 432 conflicted_tokens = 433 AnnotationList__compute_conflicted_tokens (shift_tokens, s->reductions); 434 435 /* Add an inadequacy annotation for each conflicted_token. */ 436 BITSET_FOR_EACH (biter_conflict, conflicted_tokens, conflicted_token, 0) 437 { 438 AnnotationList *annotation_node; 439 /* FIXME: Would a BITSET_FRUGAL or BITEST_SPARSE be more efficient? Now 440 or convert it inside InadequacyList__new_conflict? */ 441 bitset actions = bitset_create (s->reductions->num + 1, BITSET_FIXED); 442 ContributionIndex contribution_count = 0; 443 bool potential_contribution = false; 444 445 /* Allocate the annotation node. */ 446 { 447 int rule_i; 448 for (rule_i = 0; rule_i < s->reductions->num; ++rule_i) 449 if (bitset_test (s->reductions->lookahead_tokens[rule_i], 450 conflicted_token)) 451 ++contribution_count; 452 if (bitset_test (shift_tokens, conflicted_token)) 453 ++contribution_count; 454 annotation_node = 455 AnnotationList__alloc_on_obstack (contribution_count, 456 annotations_obstackp); 457 } 458 459 /* Add a contribution for each reduction that has conflicted_token as a 460 lookahead. */ 461 { 462 ContributionIndex ci = 0; 463 int item_i = 0; 464 int rule_i; 465 for (rule_i = 0; rule_i < s->reductions->num; ++rule_i) 466 { 467 rule *the_rule = s->reductions->rules[rule_i]; 468 if (bitset_test (s->reductions->lookahead_tokens[rule_i], 469 conflicted_token)) 470 { 471 bitset_set (actions, rule_i); 472 /* If this reduction is on a kernel item, just add it. */ 473 if (!item_number_is_rule_number (the_rule->rhs[0])) 474 { 475 annotation_node->contributions[ci] = 476 Sbitset__new_on_obstack (s->nitems, 477 annotations_obstackp); 478 /* Catch item_i up to rule_i. This works because both are 479 sorted on rule number. */ 480 while (!item_number_is_rule_number ( 481 ritem[s->items[item_i]]) 482 || item_number_as_rule_number ( 483 ritem[s->items[item_i]]) 484 != the_rule->number) 485 { 486 ++item_i; 487 aver (item_i < s->nitems); 488 } 489 Sbitset__set (annotation_node->contributions[ci], item_i); 490 } 491 /* Otherwise, add the kernel items whose lookahead sets 492 contribute the conflicted token to this reduction's 493 lookahead set. */ 494 else if (AnnotationList__compute_lhs_contributions ( 495 s, the_rule, conflicted_token, follow_kernel_items, 496 always_follows, predecessors, item_lookahead_sets, 497 &annotation_node->contributions[ci], 498 annotations_obstackp)) 499 { 500 annotation_node->contributions[ci++] = NULL; 501 continue; 502 } 503 /* The lookahead token has to come from somewhere. */ 504 aver (!Sbitset__isEmpty (annotation_node->contributions[ci], 505 s->nitems)); 506 ++ci; 507 potential_contribution = true; 508 } 509 } 510 } 511 512 /* If there are any contributions besides just "always" contributions: 513 - If there's also a shift contribution, record it. 514 - If the dominant contribution is split-stable, then the annotation 515 could not affect merging, so go ahead and discard the annotation and 516 the inadequacy to save space now plus time during state splitting. 517 - Otherwise, record the annotation and the inadequacy, and compute any 518 resulting annotations needed on predecessor states. */ 519 if (potential_contribution) 520 { 521 if (bitset_test (shift_tokens, conflicted_token)) 522 { 523 bitset_set (actions, s->reductions->num); 524 annotation_node->contributions[contribution_count - 1] = NULL; 525 } 526 { 527 InadequacyList *conflict_node = 528 InadequacyList__new_conflict ( 529 s, symbols[conflicted_token], actions, 530 inadequacy_list_node_count); 531 actions = NULL; 532 annotation_node->inadequacyNode = conflict_node; 533 if (ContributionIndex__none 534 != AnnotationList__computeDominantContribution ( 535 annotation_node, s->nitems, all_lookaheads, true)) 536 { 537 obstack_free (annotations_obstackp, annotation_node); 538 InadequacyList__delete (conflict_node); 539 } 540 else 541 { 542 InadequacyList__prependTo (conflict_node, 543 &inadequacy_lists[s->number]); 544 aver (AnnotationList__insertInto ( 545 annotation_node, &annotation_lists[s->number], 546 s->nitems)); 547 /* This aver makes sure the 548 AnnotationList__computeDominantContribution check above 549 does discard annotations in the simplest case of a S/R 550 conflict with no token precedence. */ 551 aver (!bitset_test (shift_tokens, conflicted_token) 552 || symbols[conflicted_token]->prec); 553 ++annotation_counts[s->number]; 554 if (contribution_count > *max_contributionsp) 555 *max_contributionsp = contribution_count; 556 AnnotationList__computePredecessorAnnotations ( 557 annotation_node, s, 558 follow_kernel_items, always_follows, predecessors, 559 item_lookahead_sets, annotation_lists, annotation_counts, 560 annotations_obstackp); 561 } 562 } 563 } 564 else 565 { 566 bitset_free (actions); 567 obstack_free (annotations_obstackp, annotation_node); 568 } 569 } 570 571 bitsetv_free (all_lookaheads); 572 bitset_free (shift_tokens); 573 bitset_free (conflicted_tokens); 574} 575 576void 577AnnotationList__debug (AnnotationList const *self, size_t nitems, int spaces) 578{ 579 AnnotationList const *a; 580 AnnotationIndex ai; 581 for (a = self, ai = 0; a; a = a->next, ++ai) 582 { 583 { 584 int j; 585 for (j = 0; j < spaces; ++j) 586 putc (' ', stderr); 587 } 588 fprintf (stderr, "Annotation %d (manifesting state %d):\n", 589 ai, a->inadequacyNode->manifestingState->number); 590 { 591 ContributionIndex ci; 592 bitset_bindex rulei = 0; /* init suppresses compiler warning */ 593 rulei = bitset_first (a->inadequacyNode->inadequacy.conflict.actions); 594 for (ci = 0; ci < a->inadequacyNode->contributionCount; ++ci) 595 { 596 symbol_number token = 597 InadequacyList__getContributionToken (a->inadequacyNode, ci) 598 ->number; 599 { 600 int j; 601 for (j = 0; j < spaces+2; ++j) 602 putc (' ', stderr); 603 } 604 if (ci == InadequacyList__getShiftContributionIndex ( 605 a->inadequacyNode)) 606 fprintf (stderr, "Contributes shift of token %d.\n", token); 607 else 608 { 609 fprintf (stderr, "Contributes token %d", token); 610 aver (rulei != BITSET_BINDEX_MAX); 611 fprintf (stderr, " as lookahead, rule number %d", 612 a->inadequacyNode->manifestingState 613 ->reductions->rules[rulei]->number); 614 rulei = 615 bitset_next (a->inadequacyNode->inadequacy.conflict.actions, 616 rulei+1); 617 if (AnnotationList__isContributionAlways (a, ci)) 618 fprintf (stderr, " always."); 619 else 620 { 621 fprintf (stderr, ", items: "); 622 Sbitset__fprint (a->contributions[ci], nitems, stderr); 623 } 624 fprintf (stderr, "\n"); 625 } 626 } 627 } 628 } 629} 630 631void 632AnnotationList__computeLookaheadFilter (AnnotationList const *self, 633 size_t nitems, 634 bitsetv lookahead_filter) 635{ 636 bitsetv_zero (lookahead_filter); 637 for (; self; self = self->next) 638 { 639 ContributionIndex ci; 640 for (ci = 0; ci < self->inadequacyNode->contributionCount; ++ci) 641 if (!AnnotationList__isContributionAlways (self, ci)) 642 { 643 Sbitset__Index item; 644 Sbitset biter; 645 symbol_number token = 646 InadequacyList__getContributionToken (self->inadequacyNode, ci) 647 ->number; 648 SBITSET__FOR_EACH (self->contributions[ci], nitems, biter, item) 649 bitset_set (lookahead_filter[item], token); 650 } 651 } 652} 653 654/** 655 * \pre 656 * - <tt>self != NULL</tt>. 657 * - \c nitems is the number of kernel items in the LR(0) state that \c self 658 * annotates. 659 * - \c lookaheads describes the lookahead sets on the kernel items of some 660 * isocore of the LR(0) state that \c self annotates. Either: 661 * - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel 662 * item is empty. 663 * - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> is either: 664 * - \c NULL only if the lookahead set on kernel item \c i is empty. 665 * - The (possibly empty) lookahead set on kernel item \c i. 666 * - <tt>0 <= ci < self->inadequacyNode->contributionCount</tt>. 667 * \post 668 * - \c result = true iff contribution \c ci in \c self is made by the state 669 * described by \c lookaheads. 670 */ 671static bool 672AnnotationList__stateMakesContribution (AnnotationList const *self, 673 size_t nitems, ContributionIndex ci, 674 bitset *lookaheads) 675{ 676 if (AnnotationList__isContributionAlways (self, ci)) 677 return true; 678 if (!lookaheads) 679 return false; 680 { 681 symbol_number token = 682 InadequacyList__getContributionToken (self->inadequacyNode, ci)->number; 683 Sbitset__Index item; 684 Sbitset biter; 685 SBITSET__FOR_EACH (self->contributions[ci], nitems, biter, item) 686 if (lookaheads[item] && bitset_test (lookaheads[item], token)) 687 return true; 688 } 689 return false; 690} 691 692ContributionIndex 693AnnotationList__computeDominantContribution (AnnotationList const *self, 694 size_t nitems, bitset *lookaheads, 695 bool require_split_stable) 696{ 697 symbol *token; 698 ContributionIndex const ci_shift = 699 InadequacyList__getShiftContributionIndex (self->inadequacyNode); 700 701 token = self->inadequacyNode->inadequacy.conflict.token; 702 703 /* S/R conflict. */ 704 if (ci_shift != ContributionIndex__none) 705 { 706 bool find_stable_domination_over_shift = false; 707 bool find_stable_error_action_domination = false; 708 { 709 ContributionIndex ci; 710 int actioni; 711 ContributionIndex ci_rr_dominator = ContributionIndex__none; 712 int shift_precedence = token->prec; 713 714 /* If the token has no precedence set, shift is always chosen. */ 715 if (!shift_precedence) 716 return ci_shift; 717 718 /* Figure out which reductions contribute, which of those would 719 dominate in a R/R comparison, and whether any reduction dominates 720 the shift so that the R/R comparison is actually needed. */ 721 for (ci = 0, actioni = bitset_first (self->inadequacyNode->inadequacy 722 .conflict.actions); 723 ci < self->inadequacyNode->contributionCount; 724 ++ci, actioni = bitset_next (self->inadequacyNode->inadequacy 725 .conflict.actions, actioni+1)) 726 { 727 int reduce_precedence = 0; 728 if (ci == ci_shift) 729 continue; 730 { 731 rule *r = self->inadequacyNode->manifestingState 732 ->reductions->rules[actioni]; 733 if (r->prec) 734 reduce_precedence = r->prec->prec; 735 } 736 /* If there's no need to check whether this reduction actually 737 contributes because the shift eliminates it from the R/R 738 comparison anyway, continue to the next reduction. */ 739 if (reduce_precedence 740 && (reduce_precedence < shift_precedence 741 || (reduce_precedence == shift_precedence 742 && token->assoc == right_assoc))) 743 continue; 744 if (!AnnotationList__stateMakesContribution (self, nitems, ci, 745 lookaheads)) 746 continue; 747 /* This uneliminated reduction contributes, so see if it can cause 748 an error action. */ 749 if (reduce_precedence == shift_precedence 750 && token->assoc == non_assoc) 751 { 752 /* It's not possible to find split-stable domination over 753 shift after a potential %nonassoc. */ 754 if (find_stable_domination_over_shift) 755 return ContributionIndex__none; 756 if (!require_split_stable 757 || AnnotationList__isContributionAlways (self, ci)) 758 return ContributionIndex__error_action; 759 find_stable_error_action_domination = true; 760 } 761 /* Consider this uneliminated contributing reduction in the R/R 762 comparison. */ 763 if (ci_rr_dominator == ContributionIndex__none) 764 ci_rr_dominator = ci; 765 /* If precedence is set for this uneliminated contributing 766 reduction, it dominates the shift, so try to figure out which 767 reduction dominates the R/R comparison. */ 768 if (reduce_precedence) 769 { 770 /* It's not possible to find split-stable error action 771 domination after a potential reduction. */ 772 if (find_stable_error_action_domination) 773 return ContributionIndex__none; 774 if (!require_split_stable) 775 return ci_rr_dominator; 776 if (!AnnotationList__isContributionAlways (self, 777 ci_rr_dominator)) 778 return ContributionIndex__none; 779 if (AnnotationList__isContributionAlways (self, ci)) 780 return ci_rr_dominator; 781 find_stable_domination_over_shift = true; 782 } 783 } 784 } 785 if (find_stable_domination_over_shift 786 || find_stable_error_action_domination) 787 return ContributionIndex__none; 788 /* No reduce or error action domination found, so shift dominates. */ 789 return ci_shift; 790 } 791 792 /* R/R conflict, so the reduction with the lowest rule number dominates. 793 Fortunately, contributions are sorted by rule number. */ 794 { 795 ContributionIndex ci; 796 for (ci = 0; ci < self->inadequacyNode->contributionCount; ++ci) 797 if (AnnotationList__stateMakesContribution (self, nitems, ci, 798 lookaheads)) 799 { 800 if (require_split_stable 801 && !AnnotationList__isContributionAlways (self, ci)) 802 return ContributionIndex__none; 803 return ci; 804 } 805 } 806 return ContributionIndex__none; 807} 808