src/conflicts.c

   1 /* Find and resolve or report lookahead conflicts for bison,
   2
   3    Copyright (C) 1984, 1989, 1992, 2000-2007, 2009-2012 Free Software
   4    Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21 #include <config.h>
  22 #include "system.h"
  23
  24 #include <bitset.h>
  25
  26 #include "LR0.h"
  27 #include "complain.h"
  28 #include "conflicts.h"
  29 #include "files.h"
  30 #include "getargs.h"
  31 #include "gram.h"
  32 #include "lalr.h"
  33 #include "print-xml.h"
  34 #include "reader.h"
  35 #include "state.h"
  36 #include "symtab.h"
  37
  38 /* -1 stands for not specified. */
  39 int expected_sr_conflicts = -1;
  40 int expected_rr_conflicts = -1;
  41 static char *conflicts;
  42 static struct obstack solved_conflicts_obstack;
  43 static struct obstack solved_conflicts_xml_obstack;
  44
  45 static bitset shift_set;
  46 static bitset lookahead_set;
  47
  48 \f
  49
  50 enum conflict_resolution
  51   {
  52     shift_resolution,
  53     reduce_resolution,
  54     left_resolution,
  55     right_resolution,
  56     nonassoc_resolution
  57   };
  58
  59
  60 /*----------------------------------------------------------------.
  61 | Explain how an SR conflict between TOKEN and RULE was resolved: |
  62 | RESOLUTION.                                                     |
  63 `----------------------------------------------------------------*/
  64
  65 static inline void
  66 log_resolution (rule *r, symbol_number token,
  67                 enum conflict_resolution resolution)
  68 {
  69   if (report_flag & report_solved_conflicts)
  70     {
  71       /* The description of the resolution. */
  72       switch (resolution)
  73         {
  74         case shift_resolution:
  75         case right_resolution:
  76           obstack_fgrow2 (&solved_conflicts_obstack,
  77                           _("    Conflict between rule %d and token %s"
  78                             " resolved as shift"),
  79                           r->number,
  80                           symbols[token]->tag);
  81           break;
  82
  83         case reduce_resolution:
  84         case left_resolution:
  85           obstack_fgrow2 (&solved_conflicts_obstack,
  86                           _("    Conflict between rule %d and token %s"
  87                             " resolved as reduce"),
  88                           r->number,
  89                           symbols[token]->tag);
  90           break;
  91
  92         case nonassoc_resolution:
  93           obstack_fgrow2 (&solved_conflicts_obstack,
  94                           _("    Conflict between rule %d and token %s"
  95                             " resolved as an error"),
  96                           r->number,
  97                           symbols[token]->tag);
  98           break;
  99         }
 100
 101       /* The reason. */
 102       switch (resolution)
 103         {
 104         case shift_resolution:
 105           obstack_fgrow2 (&solved_conflicts_obstack,
 106                           " (%s < %s)",
 107                           r->prec->tag,
 108                           symbols[token]->tag);
 109           break;
 110
 111         case reduce_resolution:
 112           obstack_fgrow2 (&solved_conflicts_obstack,
 113                           " (%s < %s)",
 114                           symbols[token]->tag,
 115                           r->prec->tag);
 116           break;
 117
 118         case left_resolution:
 119           obstack_fgrow1 (&solved_conflicts_obstack,
 120                           " (%%left %s)",
 121                           symbols[token]->tag);
 122           break;
 123
 124         case right_resolution:
 125           obstack_fgrow1 (&solved_conflicts_obstack,
 126                           " (%%right %s)",
 127                           symbols[token]->tag);
 128           break;
 129
 130         case nonassoc_resolution:
 131           obstack_fgrow1 (&solved_conflicts_obstack,
 132                           " (%%nonassoc %s)",
 133                           symbols[token]->tag);
 134           break;
 135         }
 136
 137       obstack_sgrow (&solved_conflicts_obstack, ".\n");
 138     }
 139
 140   /* XML report */
 141   if (xml_flag)
 142     {
 143       /* The description of the resolution. */
 144       switch (resolution)
 145         {
 146         case shift_resolution:
 147         case right_resolution:
 148           obstack_fgrow2 (&solved_conflicts_xml_obstack,
 149                           "        <resolution rule=\"%d\" symbol=\"%s\""
 150                           " type=\"shift\">",
 151                           r->number,
 152                           xml_escape (symbols[token]->tag));
 153           break;
 154
 155         case reduce_resolution:
 156         case left_resolution:
 157           obstack_fgrow2 (&solved_conflicts_xml_obstack,
 158                           "        <resolution rule=\"%d\" symbol=\"%s\""
 159                           " type=\"reduce\">",
 160                           r->number,
 161                           xml_escape (symbols[token]->tag));
 162           break;
 163
 164         case nonassoc_resolution:
 165           obstack_fgrow2 (&solved_conflicts_xml_obstack,
 166                           "        <resolution rule=\"%d\" symbol=\"%s\""
 167                           " type=\"error\">",
 168                           r->number,
 169                           xml_escape (symbols[token]->tag));
 170           break;
 171         }
 172
 173       /* The reason. */
 174       switch (resolution)
 175         {
 176         case shift_resolution:
 177           obstack_fgrow2 (&solved_conflicts_xml_obstack,
 178                           "%s &lt; %s",
 179                           xml_escape_n (0, r->prec->tag),
 180                           xml_escape_n (1, symbols[token]->tag));
 181           break;
 182
 183         case reduce_resolution:
 184           obstack_fgrow2 (&solved_conflicts_xml_obstack,
 185                           "%s &lt; %s",
 186                           xml_escape_n (0, symbols[token]->tag),
 187                           xml_escape_n (1, r->prec->tag));
 188           break;
 189
 190         case left_resolution:
 191           obstack_fgrow1 (&solved_conflicts_xml_obstack,
 192                           "%%left %s",
 193                           xml_escape (symbols[token]->tag));
 194           break;
 195
 196         case right_resolution:
 197           obstack_fgrow1 (&solved_conflicts_xml_obstack,
 198                           "%%right %s",
 199                           xml_escape (symbols[token]->tag));
 200           break;
 201
 202         case nonassoc_resolution:
 203           obstack_fgrow1 (&solved_conflicts_xml_obstack,
 204                           "%%nonassoc %s",
 205                           xml_escape (symbols[token]->tag));
 206       break;
 207         }
 208
 209       obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\n");
 210     }
 211 }
 212
 213
 214 /*------------------------------------------------------------------.
 215 | Turn off the shift recorded for the specified token in the        |
 216 | specified state.  Used when we resolve a shift-reduce conflict in |
 217 | favor of the reduction or as an error (%nonassoc).                |
 218 `------------------------------------------------------------------*/
 219
 220 static void
 221 flush_shift (state *s, int token)
 222 {
 223   transitions *trans = s->transitions;
 224   int i;
 225
 226   bitset_reset (lookahead_set, token);
 227   for (i = 0; i < trans->num; i++)
 228     if (!TRANSITION_IS_DISABLED (trans, i)
 229         && TRANSITION_SYMBOL (trans, i) == token)
 230       TRANSITION_DISABLE (trans, i);
 231 }
 232
 233
 234 /*--------------------------------------------------------------------.
 235 | Turn off the reduce recorded for the specified token in the         |
 236 | specified lookahead set.  Used when we resolve a shift-reduce       |
 237 | conflict in favor of the shift or as an error (%nonassoc).          |
 238 `--------------------------------------------------------------------*/
 239
 240 static void
 241 flush_reduce (bitset lookahead_tokens, int token)
 242 {
 243   bitset_reset (lookahead_tokens, token);
 244 }
 245
 246
 247 /*------------------------------------------------------------------.
 248 | Attempt to resolve shift-reduce conflict for one rule by means of |
 249 | precedence declarations.  It has already been checked that the    |
 250 | rule has a precedence.  A conflict is resolved by modifying the   |
 251 | shift or reduce tables so that there is no longer a conflict.     |
 252 |                                                                   |
 253 | RULENO is the number of the lookahead bitset to consider.         |
 254 |                                                                   |
 255 | ERRORS and NERRS can be used to store discovered explicit         |
 256 | errors.                                                           |
 257 `------------------------------------------------------------------*/
 258
 259 static void
 260 resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
 261 {
 262   symbol_number i;
 263   reductions *reds = s->reductions;
 264   /* Find the rule to reduce by to get precedence of reduction.  */
 265   rule *redrule = reds->rules[ruleno];
 266   int redprec = redrule->prec->prec;
 267   bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
 268
 269   for (i = 0; i < ntokens; i++)
 270     if (bitset_test (lookahead_tokens, i)
 271         && bitset_test (lookahead_set, i)
 272         && symbols[i]->prec)
 273       {
 274         /* Shift-reduce conflict occurs for token number i
 275            and it has a precedence.
 276            The precedence of shifting is that of token i.  */
 277         if (symbols[i]->prec < redprec)
 278           {
 279             log_resolution (redrule, i, reduce_resolution);
 280             flush_shift (s, i);
 281           }
 282         else if (symbols[i]->prec > redprec)
 283           {
 284             log_resolution (redrule, i, shift_resolution);
 285             flush_reduce (lookahead_tokens, i);
 286           }
 287         else
 288           /* Matching precedence levels.
 289              For left association, keep only the reduction.
 290              For right association, keep only the shift.
 291              For nonassociation, keep neither.  */
 292
 293           switch (symbols[i]->assoc)
 294             {
 295             default:
 296               abort ();
 297
 298             case right_assoc:
 299               log_resolution (redrule, i, right_resolution);
 300               flush_reduce (lookahead_tokens, i);
 301               break;
 302
 303             case left_assoc:
 304               log_resolution (redrule, i, left_resolution);
 305               flush_shift (s, i);
 306               break;
 307
 308             case non_assoc:
 309               log_resolution (redrule, i, nonassoc_resolution);
 310               flush_shift (s, i);
 311               flush_reduce (lookahead_tokens, i);
 312               /* Record an explicit error for this token.  */
 313               errors[(*nerrs)++] = symbols[i];
 314               break;
 315             }
 316       }
 317 }
 318
 319
 320 /*-------------------------------------------------------------------.
 321 | Solve the S/R conflicts of state S using the                       |
 322 | precedence/associativity, and flag it inconsistent if it still has |
 323 | conflicts.  ERRORS can be used as storage to compute the list of   |
 324 | lookahead tokens on which S raises a syntax error (%nonassoc).     |
 325 `-------------------------------------------------------------------*/
 326
 327 static void
 328 set_conflicts (state *s, symbol **errors)
 329 {
 330   int i;
 331   transitions *trans = s->transitions;
 332   reductions *reds = s->reductions;
 333   int nerrs = 0;
 334
 335   if (s->consistent)
 336     return;
 337
 338   bitset_zero (lookahead_set);
 339
 340   FOR_EACH_SHIFT (trans, i)
 341     bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
 342
 343   /* Loop over all rules which require lookahead in this state.  First
 344      check for shift-reduce conflict, and try to resolve using
 345      precedence.  */
 346   for (i = 0; i < reds->num; ++i)
 347     if (reds->rules[i]->prec && reds->rules[i]->prec->prec
 348         && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
 349       resolve_sr_conflict (s, i, errors, &nerrs);
 350
 351   if (nerrs)
 352     {
 353       /* Some tokens have been explicitly made errors.  Allocate a
 354          permanent errs structure for this state, to record them.  */
 355       state_errs_set (s, nerrs, errors);
 356     }
 357   if (obstack_object_size (&solved_conflicts_obstack))
 358     {
 359       obstack_1grow (&solved_conflicts_obstack, '\0');
 360       s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
 361     }
 362   if (obstack_object_size (&solved_conflicts_xml_obstack))
 363     {
 364       obstack_1grow (&solved_conflicts_xml_obstack, '\0');
 365       s->solved_conflicts_xml = obstack_finish (&solved_conflicts_xml_obstack);
 366     }
 367
 368   /* Loop over all rules which require lookahead in this state.  Check
 369      for conflicts not resolved above.  */
 370   for (i = 0; i < reds->num; ++i)
 371     {
 372       if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
 373         conflicts[s->number] = 1;
 374       bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
 375     }
 376 }
 377
 378
 379 /*----------------------------------------------------------------.
 380 | Solve all the S/R conflicts using the precedence/associativity, |
 381 | and flag as inconsistent the states that still have conflicts.  |
 382 `----------------------------------------------------------------*/
 383
 384 void
 385 conflicts_solve (void)
 386 {
 387   state_number i;
 388   /* List of lookahead tokens on which we explicitly raise a syntax error.  */
 389   symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);
 390
 391   conflicts = xcalloc (nstates, sizeof *conflicts);
 392   shift_set = bitset_create (ntokens, BITSET_FIXED);
 393   lookahead_set = bitset_create (ntokens, BITSET_FIXED);
 394   obstack_init (&solved_conflicts_obstack);
 395   obstack_init (&solved_conflicts_xml_obstack);
 396
 397   for (i = 0; i < nstates; i++)
 398     {
 399       set_conflicts (states[i], errors);
 400
 401       /* For uniformity of the code, make sure all the states have a valid
 402          `errs' member.  */
 403       if (!states[i]->errs)
 404         states[i]->errs = errs_new (0, 0);
 405     }
 406
 407   free (errors);
 408 }
 409
 410
 411 void
 412 conflicts_update_state_numbers (state_number old_to_new[],
 413                                 state_number nstates_old)
 414 {
 415   state_number i;
 416   for (i = 0; i < nstates_old; ++i)
 417     if (old_to_new[i] != nstates_old)
 418       conflicts[old_to_new[i]] = conflicts[i];
 419 }
 420
 421
 422 /*---------------------------------------------.
 423 | Count the number of shift/reduce conflicts.  |
 424 `---------------------------------------------*/
 425
 426 static int
 427 count_sr_conflicts (state *s)
 428 {
 429   int i;
 430   int src_count = 0;
 431   transitions *trans = s->transitions;
 432   reductions *reds = s->reductions;
 433
 434   if (!trans)
 435     return 0;
 436
 437   bitset_zero (lookahead_set);
 438   bitset_zero (shift_set);
 439
 440   FOR_EACH_SHIFT (trans, i)
 441     bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
 442
 443   for (i = 0; i < reds->num; ++i)
 444     bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
 445
 446   bitset_and (lookahead_set, lookahead_set, shift_set);
 447
 448   src_count = bitset_count (lookahead_set);
 449
 450   return src_count;
 451 }
 452
 453
 454 /*----------------------------------------------------------------.
 455 | Count the number of reduce/reduce conflicts.  If ONE_PER_TOKEN, |
 456 | count one conflict for each token that has any reduce/reduce    |
 457 | conflicts.  Otherwise, count one conflict for each pair of      |
 458 | conflicting reductions.                                         |
 459 +`----------------------------------------------------------------*/
 460
 461 static int
 462 count_rr_conflicts (state *s, bool one_per_token)
 463 {
 464   int i;
 465   reductions *reds = s->reductions;
 466   int rrc_count = 0;
 467
 468   for (i = 0; i < ntokens; i++)
 469     {
 470       int count = 0;
 471       int j;
 472       for (j = 0; j < reds->num; ++j)
 473         if (bitset_test (reds->lookahead_tokens[j], i))
 474           count++;
 475
 476       if (count >= 2)
 477         rrc_count += one_per_token ? 1 : count-1;
 478     }
 479
 480   return rrc_count;
 481 }
 482
 483
 484 /*--------------------------------------------------------.
 485 | Report the number of conflicts, using the Yacc format.  |
 486 `--------------------------------------------------------*/
 487
 488 static void
 489 conflict_report (FILE *out, int src_num, int rrc_num)
 490 {
 491   if (src_num && rrc_num)
 492     fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
 493              src_num, rrc_num);
 494   else if (src_num)
 495     fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
 496   else if (rrc_num)
 497     fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
 498 }
 499
 500
 501 /*-----------------------------------------------------------.
 502 | Output the detailed description of states with conflicts.  |
 503 `-----------------------------------------------------------*/
 504
 505 void
 506 conflicts_output (FILE *out)
 507 {
 508   bool printed_sth = false;
 509   state_number i;
 510   for (i = 0; i < nstates; i++)
 511     {
 512       state *s = states[i];
 513       if (conflicts[i])
 514         {
 515           fprintf (out, _("State %d "), i);
 516           conflict_report (out, count_sr_conflicts (s),
 517                            count_rr_conflicts (s, true));
 518           printed_sth = true;
 519         }
 520     }
 521   if (printed_sth)
 522     fputs ("\n\n", out);
 523 }
 524
 525 /*--------------------------------------------------------.
 526 | Total the number of S/R and R/R conflicts.  Unlike the  |
 527 | code in conflicts_output, however, count EACH pair of   |
 528 | reductions for the same state and lookahead as one      |
 529 | conflict.                                               |
 530 `--------------------------------------------------------*/
 531
 532 int
 533 conflicts_total_count (void)
 534 {
 535   state_number i;
 536   int count;
 537
 538   /* Conflicts by state.  */
 539   count = 0;
 540   for (i = 0; i < nstates; i++)
 541     if (conflicts[i])
 542       {
 543         count += count_sr_conflicts (states[i]);
 544         count += count_rr_conflicts (states[i], false);
 545       }
 546   return count;
 547 }
 548
 549
 550 /*------------------------------------------.
 551 | Reporting the total number of conflicts.  |
 552 `------------------------------------------*/
 553
 554 void
 555 conflicts_print (void)
 556 {
 557   /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
 558      not set, and then we want 0 SR, or else it is specified, in which
 559      case we want equality.  */
 560   bool src_ok;
 561   bool rrc_ok;
 562
 563   int src_total = 0;
 564   int rrc_total = 0;
 565   int src_expected;
 566   int rrc_expected;
 567
 568   /* Conflicts by state.  */
 569   {
 570     state_number i;
 571
 572     for (i = 0; i < nstates; i++)
 573       if (conflicts[i])
 574         {
 575           src_total += count_sr_conflicts (states[i]);
 576           rrc_total += count_rr_conflicts (states[i], true);
 577         }
 578   }
 579
 580   if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
 581     {
 582       warn (_("%%expect-rr applies only to GLR parsers"));
 583       expected_rr_conflicts = -1;
 584     }
 585
 586   src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
 587   rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
 588   src_ok = src_total == src_expected;
 589   rrc_ok = rrc_total == rrc_expected;
 590
 591   /* If there are as many RR conflicts and SR conflicts as
 592      expected, then there is nothing to report.  */
 593   if (rrc_ok & src_ok)
 594     return;
 595
 596   /* Report the total number of conflicts on STDERR.  */
 597   if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
 598     {
 599       if (!(warnings_flag & warnings_conflicts_sr))
 600         src_total = 0;
 601       if (!(warnings_flag & warnings_conflicts_rr))
 602         rrc_total = 0;
 603     }
 604   if (src_total | rrc_total)
 605     {
 606       if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
 607         set_warning_issued ();
 608       if (! yacc_flag)
 609         fprintf (stderr, "%s: ", current_file);
 610       conflict_report (stderr, src_total, rrc_total);
 611     }
 612
 613   if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)
 614     {
 615       if (! src_ok)
 616         complain (ngettext ("expected %d shift/reduce conflict",
 617                             "expected %d shift/reduce conflicts",
 618                             src_expected),
 619                   src_expected);
 620       if (! rrc_ok)
 621         complain (ngettext ("expected %d reduce/reduce conflict",
 622                             "expected %d reduce/reduce conflicts",
 623                             rrc_expected),
 624                   rrc_expected);
 625     }
 626 }
 627
 628
 629 void
 630 conflicts_free (void)
 631 {
 632   free (conflicts);
 633   bitset_free (shift_set);
 634   bitset_free (lookahead_set);
 635   obstack_free (&solved_conflicts_obstack, NULL);
 636   obstack_free (&solved_conflicts_xml_obstack, NULL);
 637 }