src/AnnotationList.c

   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  */
  37 static AnnotationList*
  38 AnnotationList__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  */
  60 static bool
  61 AnnotationList__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  */
  97 static bool
  98 AnnotationList__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
 154 static bitset
 155 AnnotationList__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
 164 static bitset
 165 AnnotationList__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
 191 static bool
 192 AnnotationList__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
 217 static void
 218 AnnotationList__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
 409 void
 410 AnnotationList__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
 576 void
 577 AnnotationList__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
 631 void
 632 AnnotationList__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  */
 671 static bool
 672 AnnotationList__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
 692 ContributionIndex
 693 AnnotationList__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 }