1 /* Find and resolve or report lookahead conflicts for bison,
2
3 Copyright (C) 1984, 1989, 1992, 2000-2015, 2018-2021 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 <https://www.gnu.org/licenses/>. */
20
21 #include <config.h>
22 #include "system.h"
23
24 #include <bitset.h>
25
26 #include "complain.h"
27 #include "conflicts.h"
28 #include "counterexample.h"
29 #include "files.h"
30 #include "getargs.h"
31 #include "gram.h"
32 #include "lalr.h"
33 #include "lr0.h"
34 #include "print-xml.h"
35 #include "reader.h"
36 #include "state.h"
37 #include "symtab.h"
38
39 /* -1 stands for not specified. */
40 int expected_sr_conflicts = -1;
41 int expected_rr_conflicts = -1;
42
43 /* CONFLICTS[STATE-NUM] -- Whether that state has unresolved conflicts. */
44 static bool *conflicts;
45
46 static struct obstack solved_conflicts_obstack;
47 static struct obstack solved_conflicts_xml_obstack;
48
49 static bitset shift_set;
50 static bitset lookahead_set;
51
52 bool
53 has_conflicts (const state *s)
54 {
55 return conflicts[s->number];
56 }
57
58
59
60 enum conflict_resolution
61 {
62 shift_resolution,
63 reduce_resolution,
64 left_resolution,
65 right_resolution,
66 nonassoc_resolution
67 };
68
69
70 /*----------------------------------------------------------------.
71 | Explain how an SR conflict between TOKEN and RULE was resolved: |
72 | RESOLUTION. |
73 `----------------------------------------------------------------*/
74
75 static inline void
76 log_resolution (rule *r, symbol_number token,
77 enum conflict_resolution resolution)
78 {
79 if (report_flag & report_solved_conflicts)
80 {
81 /* The description of the resolution. */
82 switch (resolution)
83 {
84 case shift_resolution:
85 case right_resolution:
86 obstack_sgrow (&solved_conflicts_obstack, " ");
87 obstack_printf (&solved_conflicts_obstack,
88 _("Conflict between rule %d and token %s"
89 " resolved as shift"),
90 r->number,
91 symbols[token]->tag);
92 break;
93
94 case reduce_resolution:
95 case left_resolution:
96 obstack_sgrow (&solved_conflicts_obstack, " ");
97 obstack_printf (&solved_conflicts_obstack,
98 _("Conflict between rule %d and token %s"
99 " resolved as reduce"),
100 r->number,
101 symbols[token]->tag);
102 break;
103
104 case nonassoc_resolution:
105 obstack_sgrow (&solved_conflicts_obstack, " ");
106 obstack_printf (&solved_conflicts_obstack,
107 _("Conflict between rule %d and token %s"
108 " resolved as an error"),
109 r->number,
110 symbols[token]->tag);
111 break;
112 }
113
114 /* The reason. */
115 switch (resolution)
116 {
117 case shift_resolution:
118 obstack_printf (&solved_conflicts_obstack,
119 " (%s < %s)",
120 r->prec->symbol->tag,
121 symbols[token]->tag);
122 break;
123
124 case reduce_resolution:
125 obstack_printf (&solved_conflicts_obstack,
126 " (%s < %s)",
127 symbols[token]->tag,
128 r->prec->symbol->tag);
129 break;
130
131 case left_resolution:
132 obstack_printf (&solved_conflicts_obstack,
133 " (%%left %s)",
134 symbols[token]->tag);
135 break;
136
137 case right_resolution:
138 obstack_printf (&solved_conflicts_obstack,
139 " (%%right %s)",
140 symbols[token]->tag);
141 break;
142
143 case nonassoc_resolution:
144 obstack_printf (&solved_conflicts_obstack,
145 " (%%nonassoc %s)",
146 symbols[token]->tag);
147 break;
148 }
149
150 obstack_sgrow (&solved_conflicts_obstack, ".\n");
151 }
152
153 /* XML report */
154 if (xml_flag)
155 {
156 /* The description of the resolution. */
157 switch (resolution)
158 {
159 case shift_resolution:
160 case right_resolution:
161 obstack_printf (&solved_conflicts_xml_obstack,
162 " <resolution rule=\"%d\" symbol=\"%s\""
163 " type=\"shift\">",
164 r->number,
165 xml_escape (symbols[token]->tag));
166 break;
167
168 case reduce_resolution:
169 case left_resolution:
170 obstack_printf (&solved_conflicts_xml_obstack,
171 " <resolution rule=\"%d\" symbol=\"%s\""
172 " type=\"reduce\">",
173 r->number,
174 xml_escape (symbols[token]->tag));
175 break;
176
177 case nonassoc_resolution:
178 obstack_printf (&solved_conflicts_xml_obstack,
179 " <resolution rule=\"%d\" symbol=\"%s\""
180 " type=\"error\">",
181 r->number,
182 xml_escape (symbols[token]->tag));
183 break;
184 }
185
186 /* The reason. */
187 switch (resolution)
188 {
189 case shift_resolution:
190 obstack_printf (&solved_conflicts_xml_obstack,
191 "%s < %s",
192 xml_escape_n (0, r->prec->symbol->tag),
193 xml_escape_n (1, symbols[token]->tag));
194 break;
195
196 case reduce_resolution:
197 obstack_printf (&solved_conflicts_xml_obstack,
198 "%s < %s",
199 xml_escape_n (0, symbols[token]->tag),
200 xml_escape_n (1, r->prec->symbol->tag));
201 break;
202
203 case left_resolution:
204 obstack_printf (&solved_conflicts_xml_obstack,
205 "%%left %s",
206 xml_escape (symbols[token]->tag));
207 break;
208
209 case right_resolution:
210 obstack_printf (&solved_conflicts_xml_obstack,
211 "%%right %s",
212 xml_escape (symbols[token]->tag));
213 break;
214
215 case nonassoc_resolution:
216 obstack_printf (&solved_conflicts_xml_obstack,
217 "%%nonassoc %s",
218 xml_escape (symbols[token]->tag));
219 break;
220 }
221
222 obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\n");
223 }
224 }
225
226
227 /*------------------------------------------------------------------.
228 | Turn off the shift recorded for the specified token in the |
229 | specified state. Used when we resolve a shift/reduce conflict in |
230 | favor of the reduction or as an error (%nonassoc). |
231 `------------------------------------------------------------------*/
232
233 static void
234 flush_shift (state *s, int token)
235 {
236 transitions *trans = s->transitions;
237
238 bitset_reset (lookahead_set, token);
239 for (int i = 0; i < trans->num; ++i)
240 if (!TRANSITION_IS_DISABLED (trans, i)
241 && TRANSITION_SYMBOL (trans, i) == token)
242 TRANSITION_DISABLE (trans, i);
243 }
244
245
246 /*--------------------------------------------------------------------.
247 | Turn off the reduce recorded for the specified token in the |
248 | specified lookahead set. Used when we resolve a shift/reduce |
249 | conflict in favor of the shift or as an error (%nonassoc). |
250 `--------------------------------------------------------------------*/
251
252 static void
253 flush_reduce (bitset lookaheads, int token)
254 {
255 bitset_reset (lookaheads, token);
256 }
257
258
259 /*------------------------------------------------------------------.
260 | Attempt to resolve shift/reduce conflict for one rule by means of |
261 | precedence declarations. It has already been checked that the |
262 | rule has a precedence. A conflict is resolved by modifying the |
263 | shift or reduce tables so that there is no longer a conflict. |
264 | |
265 | RULENO is the number of the lookahead bitset to consider. |
266 | |
267 | ERRORS and NERRS can be used to store discovered explicit |
268 | errors. |
269 `------------------------------------------------------------------*/
270
271 static void
272 resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
273 {
274 reductions *reds = s->reductions;
275 /* Find the rule to reduce by to get precedence of reduction. */
276 rule *redrule = reds->rules[ruleno];
277 int redprec = redrule->prec->prec;
278 bitset lookaheads = reds->lookaheads[ruleno];
279
280 for (symbol_number i = 0; i < ntokens; ++i)
281 if (bitset_test (lookaheads, i)
282 && bitset_test (lookahead_set, i)
283 && symbols[i]->content->prec)
284 {
285 /* Shift/reduce conflict occurs for token number i
286 and it has a precedence.
287 The precedence of shifting is that of token i. */
288 if (symbols[i]->content->prec < redprec)
289 {
290 register_precedence (redrule->prec->number, i);
291 log_resolution (redrule, i, reduce_resolution);
292 flush_shift (s, i);
293 }
294 else if (symbols[i]->content->prec > redprec)
295 {
296 register_precedence (i, redrule->prec->number);
297 log_resolution (redrule, i, shift_resolution);
298 flush_reduce (lookaheads, i);
299 }
300 else
301 /* Matching precedence levels.
302 For non-defined associativity, keep both: unexpected
303 associativity conflict.
304 For left associativity, keep only the reduction.
305 For right associativity, keep only the shift.
306 For nonassociativity, keep neither. */
307
308 switch (symbols[i]->content->assoc)
309 {
310 case undef_assoc:
311 abort ();
312
313 case precedence_assoc:
314 break;
315
316 case right_assoc:
317 register_assoc (i, redrule->prec->number);
318 log_resolution (redrule, i, right_resolution);
319 flush_reduce (lookaheads, i);
320 break;
321
322 case left_assoc:
323 register_assoc (i, redrule->prec->number);
324 log_resolution (redrule, i, left_resolution);
325 flush_shift (s, i);
326 break;
327
328 case non_assoc:
329 register_assoc (i, redrule->prec->number);
330 log_resolution (redrule, i, nonassoc_resolution);
331 flush_shift (s, i);
332 flush_reduce (lookaheads, i);
333 /* Record an explicit error for this token. */
334 errors[(*nerrs)++] = symbols[i];
335 break;
336 }
337 }
338 }
339
340
341 /*-------------------------------------------------------------------.
342 | Solve the S/R conflicts of state S using the |
343 | precedence/associativity, and flag it inconsistent if it still has |
344 | conflicts. ERRORS can be used as storage to compute the list of |
345 | lookahead tokens on which S raises a syntax error (%nonassoc). |
346 `-------------------------------------------------------------------*/
347
348 static void
349 set_conflicts (state *s, symbol **errors)
350 {
351 if (s->consistent)
352 return;
353
354 reductions *reds = s->reductions;
355 int nerrs = 0;
356
357 bitset_zero (lookahead_set);
358
359 {
360 transitions *trans = s->transitions;
361 int i;
362 FOR_EACH_SHIFT (trans, i)
363 bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
364 }
365
366 /* Loop over all rules which require lookahead in this state. First
367 check for shift/reduce conflict, and try to resolve using
368 precedence. */
369 for (int i = 0; i < reds->num; ++i)
370 if (reds->rules[i]->prec
371 && reds->rules[i]->prec->prec
372 && !bitset_disjoint_p (reds->lookaheads[i], lookahead_set))
373 resolve_sr_conflict (s, i, errors, &nerrs);
374
375 if (nerrs)
376 /* Some tokens have been explicitly made errors. Allocate a
377 permanent errs structure for this state, to record them. */
378 state_errs_set (s, nerrs, errors);
379
380 if (obstack_object_size (&solved_conflicts_obstack))
381 s->solved_conflicts = obstack_finish0 (&solved_conflicts_obstack);
382 if (obstack_object_size (&solved_conflicts_xml_obstack))
383 s->solved_conflicts_xml = obstack_finish0 (&solved_conflicts_xml_obstack);
384
385 /* Loop over all rules which require lookahead in this state. Check
386 for conflicts not resolved above.
387
388 reds->lookaheads can be NULL if the LR type is LR(0). */
389 if (reds->lookaheads)
390 for (int i = 0; i < reds->num; ++i)
391 {
392 if (!bitset_disjoint_p (reds->lookaheads[i], lookahead_set))
393 conflicts[s->number] = true;
394 bitset_or (lookahead_set, lookahead_set, reds->lookaheads[i]);
395 }
396 }
397
398
399 /*----------------------------------------------------------------.
400 | Solve all the S/R conflicts using the precedence/associativity, |
401 | and flag as inconsistent the states that still have conflicts. |
402 `----------------------------------------------------------------*/
403
404 void
405 conflicts_solve (void)
406 {
407 /* List of lookahead tokens on which we explicitly raise a syntax error. */
408 symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);
409
410 conflicts = xcalloc (nstates, sizeof *conflicts);
411 shift_set = bitset_create (ntokens, BITSET_FIXED);
412 lookahead_set = bitset_create (ntokens, BITSET_FIXED);
413 obstack_init (&solved_conflicts_obstack);
414 obstack_init (&solved_conflicts_xml_obstack);
415
416 for (state_number i = 0; i < nstates; ++i)
417 {
418 set_conflicts (states[i], errors);
419
420 /* For uniformity of the code, make sure all the states have a valid
421 'errs' member. */
422 if (!states[i]->errs)
423 states[i]->errs = errs_new (0, 0);
424 }
425
426 free (errors);
427 }
428
429
430 void
431 conflicts_update_state_numbers (state_number old_to_new[],
432 state_number nstates_old)
433 {
434 for (state_number i = 0; i < nstates_old; ++i)
435 if (old_to_new[i] != nstates_old)
436 conflicts[old_to_new[i]] = conflicts[i];
437 }
438
439
440 /*---------------------------------------------.
441 | Count the number of shift/reduce conflicts. |
442 `---------------------------------------------*/
443
444 static size_t
445 count_state_sr_conflicts (const state *s)
446 {
447 transitions *trans = s->transitions;
448 reductions *reds = s->reductions;
449
450 if (!trans)
451 return 0;
452
453 bitset_zero (lookahead_set);
454 bitset_zero (shift_set);
455
456 {
457 int i;
458 FOR_EACH_SHIFT (trans, i)
459 bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
460 }
461
462 for (int i = 0; i < reds->num; ++i)
463 bitset_or (lookahead_set, lookahead_set, reds->lookaheads[i]);
464
465 bitset_and (lookahead_set, lookahead_set, shift_set);
466
467 return bitset_count (lookahead_set);
468 }
469
470 /*---------------------------------------------.
471 | The total number of shift/reduce conflicts. |
472 `---------------------------------------------*/
473
474 static size_t
475 count_sr_conflicts (void)
476 {
477 size_t res = 0;
478 /* Conflicts by state. */
479 for (state_number i = 0; i < nstates; ++i)
480 if (conflicts[i])
481 res += count_state_sr_conflicts (states[i]);
482 return res;
483 }
484
485
486
487 /*-----------------------------------------------------------------.
488 | Count the number of reduce/reduce conflicts. Count one conflict |
489 | for each reduction after the first for a given token. |
490 `-----------------------------------------------------------------*/
491
492 static size_t
493 count_state_rr_conflicts (const state *s)
494 {
495 reductions *reds = s->reductions;
496 size_t res = 0;
497
498 for (symbol_number i = 0; i < ntokens; ++i)
499 {
500 int count = 0;
501 for (int j = 0; j < reds->num; ++j)
502 count += bitset_test (reds->lookaheads[j], i);
503 if (2 <= count)
504 res += count-1;
505 }
506
507 return res;
508 }
509
510 static size_t
511 count_rr_conflicts (void)
512 {
513 size_t res = 0;
514 /* Conflicts by state. */
515 for (state_number i = 0; i < nstates; ++i)
516 if (conflicts[i])
517 res += count_state_rr_conflicts (states[i]);
518 return res;
519 }
520
521
522 /*------------------------------------------------------------------.
523 | For a given rule, the number of shift/reduce conflicts in a given |
524 | state. |
525 `------------------------------------------------------------------*/
526
527 static size_t
528 count_rule_state_sr_conflicts (rule *r, state *s)
529 {
530 size_t res = 0;
531 transitions *trans = s->transitions;
532 reductions *reds = s->reductions;
533
534 for (int i = 0; i < reds->num; ++i)
535 if (reds->rules[i] == r)
536 {
537 bitset lookaheads = reds->lookaheads[i];
538 int j;
539 FOR_EACH_SHIFT (trans, j)
540 res += bitset_test (lookaheads, TRANSITION_SYMBOL (trans, j));
541 }
542
543 return res;
544 }
545
546 /*----------------------------------------------------------------------.
547 | For a given rule, count the number of states for which it is involved |
548 | in shift/reduce conflicts. |
549 `----------------------------------------------------------------------*/
550
551 static size_t
552 count_rule_sr_conflicts (rule *r)
553 {
554 size_t res = 0;
555 for (state_number i = 0; i < nstates; ++i)
556 if (conflicts[i])
557 res += count_rule_state_sr_conflicts (r, states[i]);
558 return res;
559 }
560
561 /*-----------------------------------------------------------------.
562 | For a given rule, count the number of states in which it is |
563 | involved in reduce/reduce conflicts. |
564 `-----------------------------------------------------------------*/
565
566 static size_t
567 count_rule_state_rr_conflicts (rule *r, state *s)
568 {
569 size_t res = 0;
570 const reductions *reds = s->reductions;
571 bitset lookaheads = bitset_create (ntokens, BITSET_FIXED);
572
573 for (int i = 0; i < reds->num; ++i)
574 if (reds->rules[i] == r)
575 for (int j = 0; j < reds->num; ++j)
576 if (reds->rules[j] != r)
577 {
578 bitset_and (lookaheads,
579 reds->lookaheads[i],
580 reds->lookaheads[j]);
581 res += bitset_count (lookaheads);
582 }
583 bitset_free (lookaheads);
584 return res;
585 }
586
587 static size_t
588 count_rule_rr_conflicts (rule *r)
589 {
590 size_t res = 0;
591 for (state_number i = 0; i < nstates; ++i)
592 res += count_rule_state_rr_conflicts (r, states[i]);
593 return res;
594 }
595
596 /*-----------------------------------------------------------.
597 | Output the detailed description of states with conflicts. |
598 `-----------------------------------------------------------*/
599
600 void
601 conflicts_output (FILE *out)
602 {
603 bool printed_sth = false;
604 for (state_number i = 0; i < nstates; ++i)
605 if (conflicts[i])
606 {
607 const state *s = states[i];
608 int src = count_state_sr_conflicts (s);
609 int rrc = count_state_rr_conflicts (s);
610 fprintf (out, _("State %d "), i);
611 if (src && rrc)
612 fprintf (out,
613 _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
614 src, rrc);
615 else if (src)
616 fprintf (out, _("conflicts: %d shift/reduce\n"), src);
617 else if (rrc)
618 fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc);
619 printed_sth = true;
620 }
621 if (printed_sth)
622 fputs ("\n\n", out);
623 }
624
625 /*--------------------------------------------.
626 | Total the number of S/R and R/R conflicts. |
627 `--------------------------------------------*/
628
629 int
630 conflicts_total_count (void)
631 {
632 return count_sr_conflicts () + count_rr_conflicts ();
633 }
634
635 static void
636 report_counterexamples (void)
637 {
638 for (state_number sn = 0; sn < nstates; ++sn)
639 if (conflicts[sn])
640 counterexample_report_state (states[sn], stderr, "");
641 }
642
643 /*------------------------------------------------.
644 | Report per-rule %expect/%expect-rr mismatches. |
645 `------------------------------------------------*/
646
647 static void
648 report_rule_expectation_mismatches (void)
649 {
650 for (rule_number i = 0; i < nrules; i += 1)
651 {
652 rule *r = &rules[i];
653 int expected_sr = r->expected_sr_conflicts;
654 int expected_rr = r->expected_rr_conflicts;
655
656 if (expected_sr != -1 || expected_rr != -1)
657 {
658 int sr = count_rule_sr_conflicts (r);
659 if (sr != expected_sr && (sr != 0 || expected_sr != -1))
660 complain (&r->location, complaint,
661 _("shift/reduce conflicts for rule %d:"
662 " %d found, %d expected"),
663 r->code, sr, expected_sr);
664 int rr = count_rule_rr_conflicts (r);
665 if (rr != expected_rr && (rr != 0 || expected_rr != -1))
666 complain (&r->location, complaint,
667 _("reduce/reduce conflicts for rule %d:"
668 " %d found, %d expected"),
669 r->code, rr, expected_rr);
670 }
671 }
672 }
673
674 /*---------------------------------.
675 | Reporting numbers of conflicts. |
676 `---------------------------------*/
677
678 void
679 conflicts_print (void)
680 {
681 report_rule_expectation_mismatches ();
682
683 if (! glr_parser && expected_rr_conflicts != -1)
684 {
685 complain (NULL, Wother, _("%%expect-rr applies only to GLR parsers"));
686 expected_rr_conflicts = -1;
687 }
688
689 // The warning flags used to emit a diagnostic, if we did.
690 warnings unexpected_conflicts_warning = Wnone;
691 /* The following two blocks scream for factoring, but i18n support
692 would make it ugly. */
693 {
694 int total = count_sr_conflicts ();
695 /* If %expect is not used, but %expect-rr is, then expect 0 sr. */
696 int expected =
697 (expected_sr_conflicts == -1 && expected_rr_conflicts != -1)
698 ? 0
699 : expected_sr_conflicts;
700 if (expected != -1)
701 {
702 if (expected != total)
703 {
704 complain (NULL, complaint,
705 _("shift/reduce conflicts: %d found, %d expected"),
706 total, expected);
707 if (total)
708 unexpected_conflicts_warning = complaint;
709 }
710 }
711 else if (total)
712 {
713 complain (NULL, Wconflicts_sr,
714 ngettext ("%d shift/reduce conflict",
715 "%d shift/reduce conflicts",
716 total),
717 total);
718 unexpected_conflicts_warning = Wconflicts_sr;
719 }
720 }
721
722 {
723 int total = count_rr_conflicts ();
724 /* If %expect-rr is not used, but %expect is, then expect 0 rr. */
725 int expected =
726 (expected_rr_conflicts == -1 && expected_sr_conflicts != -1)
727 ? 0
728 : expected_rr_conflicts;
729 if (expected != -1)
730 {
731 if (expected != total)
732 {
733 complain (NULL, complaint,
734 _("reduce/reduce conflicts: %d found, %d expected"),
735 total, expected);
736 if (total)
737 unexpected_conflicts_warning = complaint;
738 }
739 }
740 else if (total)
741 {
742 complain (NULL, Wconflicts_rr,
743 ngettext ("%d reduce/reduce conflict",
744 "%d reduce/reduce conflicts",
745 total),
746 total);
747 unexpected_conflicts_warning = Wconflicts_rr;
748 }
749 }
750
751 if (warning_is_enabled (Wcounterexamples))
752 report_counterexamples ();
753 else if (unexpected_conflicts_warning != Wnone)
754 subcomplain (NULL, unexpected_conflicts_warning,
755 _("rerun with option '-Wcounterexamples'"
756 " to generate conflict counterexamples"));
757 }
758
759 void
760 conflicts_free (void)
761 {
762 free (conflicts);
763 bitset_free (shift_set);
764 bitset_free (lookahead_set);
765 obstack_free (&solved_conflicts_obstack, NULL);
766 obstack_free (&solved_conflicts_xml_obstack, NULL);
767 }