| 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 | } |