warnings: organize variadic complaints call
[bison.git] / src / conflicts.c
CommitLineData
742e4900 1/* Find and resolve or report lookahead conflicts for bison,
f041e30b 2
34136e65 3 Copyright (C) 1984, 1989, 1992, 2000-2012 Free Software Foundation,
575619af 4 Inc.
08089d5d 5
ceed8467 6 This file is part of Bison, the GNU Compiler Compiler.
08089d5d 7
f16b0819
PE
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.
08089d5d 12
f16b0819
PE
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.
08089d5d 17
ceed8467 18 You should have received a copy of the GNU General Public License
f16b0819 19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
08089d5d 20
2cec9080 21#include <config.h>
08089d5d 22#include "system.h"
f041e30b
PE
23
24#include <bitset.h>
25
26#include "LR0.h"
7da99ede 27#include "complain.h"
f041e30b 28#include "conflicts.h"
08089d5d 29#include "files.h"
f041e30b 30#include "getargs.h"
08089d5d 31#include "gram.h"
720d742f 32#include "lalr.h"
41d7a5f2 33#include "print-xml.h"
b2ca4022 34#include "reader.h"
f041e30b
PE
35#include "state.h"
36#include "symtab.h"
d2729d44 37
7da99ede 38/* -1 stands for not specified. */
d6328241
PH
39int expected_sr_conflicts = -1;
40int expected_rr_conflicts = -1;
da2a7671 41static char *conflicts;
d6b771c3 42static struct obstack solved_conflicts_obstack;
41d7a5f2 43static struct obstack solved_conflicts_xml_obstack;
08089d5d 44
8dd162d3 45static bitset shift_set;
742e4900 46static bitset lookahead_set;
b408954b 47
c29240e7 48\f
08089d5d 49
f041e30b 50enum conflict_resolution
b408954b
AD
51 {
52 shift_resolution,
53 reduce_resolution,
54 left_resolution,
55 right_resolution,
86eff183 56 nonassoc_resolution
b408954b
AD
57 };
58
59
9801d40c
AD
60/*----------------------------------------------------------------.
61| Explain how an SR conflict between TOKEN and RULE was resolved: |
62| RESOLUTION. |
63`----------------------------------------------------------------*/
64
c29240e7 65static inline void
f041e30b 66log_resolution (rule *r, symbol_number token,
e9690142 67 enum conflict_resolution resolution)
08089d5d 68{
b408954b
AD
69 if (report_flag & report_solved_conflicts)
70 {
71 /* The description of the resolution. */
72 switch (resolution)
e9690142
JD
73 {
74 case shift_resolution:
75 case right_resolution:
cb9ec4fa 76 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
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:
cb9ec4fa 85 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
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:
cb9ec4fa 93 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
94 _(" Conflict between rule %d and token %s"
95 " resolved as an error"),
96 r->number,
97 symbols[token]->tag);
98 break;
99 }
b408954b
AD
100
101 /* The reason. */
102 switch (resolution)
e9690142
JD
103 {
104 case shift_resolution:
cb9ec4fa 105 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
106 " (%s < %s)",
107 r->prec->tag,
108 symbols[token]->tag);
109 break;
110
111 case reduce_resolution:
cb9ec4fa 112 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
113 " (%s < %s)",
114 symbols[token]->tag,
115 r->prec->tag);
116 break;
117
118 case left_resolution:
cb9ec4fa 119 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
120 " (%%left %s)",
121 symbols[token]->tag);
122 break;
123
124 case right_resolution:
cb9ec4fa 125 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
126 " (%%right %s)",
127 symbols[token]->tag);
128 break;
129
130 case nonassoc_resolution:
cb9ec4fa 131 obstack_printf (&solved_conflicts_obstack,
e9690142
JD
132 " (%%nonassoc %s)",
133 symbols[token]->tag);
134 break;
135 }
41d7a5f2 136
b408954b 137 obstack_sgrow (&solved_conflicts_obstack, ".\n");
ef1b4273 138 }
41d7a5f2 139
ef1b4273
JD
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:
aaf63e45 148 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
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:
aaf63e45 157 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
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:
aaf63e45 165 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
166 " <resolution rule=\"%d\" symbol=\"%s\""
167 " type=\"error\">",
168 r->number,
169 xml_escape (symbols[token]->tag));
170 break;
171 }
41d7a5f2 172
ef1b4273
JD
173 /* The reason. */
174 switch (resolution)
175 {
176 case shift_resolution:
aaf63e45 177 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
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:
aaf63e45 184 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
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:
aaf63e45 191 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
192 "%%left %s",
193 xml_escape (symbols[token]->tag));
194 break;
195
196 case right_resolution:
aaf63e45 197 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
198 "%%right %s",
199 xml_escape (symbols[token]->tag));
200 break;
201
202 case nonassoc_resolution:
aaf63e45 203 obstack_printf (&solved_conflicts_xml_obstack,
ef1b4273
JD
204 "%%nonassoc %s",
205 xml_escape (symbols[token]->tag));
206 break;
207 }
208
209 obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\n");
b408954b 210 }
08089d5d
DM
211}
212
213
c29240e7
AD
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 |
9d774aff 217| favor of the reduction or as an error (%nonassoc). |
c29240e7
AD
218`------------------------------------------------------------------*/
219
4a120d45 220static void
f041e30b 221flush_shift (state *s, int token)
08089d5d 222{
f041e30b 223 transitions *trans = s->transitions;
9f136c07 224 int i;
c29240e7 225
742e4900 226 bitset_reset (lookahead_set, token);
f041e30b
PE
227 for (i = 0; i < trans->num; i++)
228 if (!TRANSITION_IS_DISABLED (trans, i)
e9690142 229 && TRANSITION_SYMBOL (trans, i) == token)
f041e30b 230 TRANSITION_DISABLE (trans, i);
08089d5d
DM
231}
232
233
8dd162d3 234/*--------------------------------------------------------------------.
9d774aff
JD
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). |
8dd162d3 238`--------------------------------------------------------------------*/
709ae8c6
AD
239
240static void
742e4900 241flush_reduce (bitset lookahead_tokens, int token)
709ae8c6 242{
742e4900 243 bitset_reset (lookahead_tokens, token);
709ae8c6
AD
244}
245
246
c29240e7
AD
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. |
9801d40c 252| |
742e4900 253| RULENO is the number of the lookahead bitset to consider. |
8b752b00 254| |
9d774aff
JD
255| ERRORS and NERRS can be used to store discovered explicit |
256| errors. |
c29240e7 257`------------------------------------------------------------------*/
08089d5d 258
4a120d45 259static void
9d774aff 260resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
08089d5d 261{
f041e30b
PE
262 symbol_number i;
263 reductions *reds = s->reductions;
9801d40c 264 /* Find the rule to reduce by to get precedence of reduction. */
f041e30b 265 rule *redrule = reds->rules[ruleno];
9801d40c 266 int redprec = redrule->prec->prec;
742e4900 267 bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
08089d5d 268
08089d5d 269 for (i = 0; i < ntokens; i++)
742e4900 270 if (bitset_test (lookahead_tokens, i)
e9690142
JD
271 && bitset_test (lookahead_set, i)
272 && symbols[i]->prec)
92b16366 273 {
e9690142
JD
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
d78f0ac9
AD
288 /* Matching precedence levels.
289 For non-defined associativity, keep both: unexpected
290 associativity conflict.
291 For left associativity, keep only the reduction.
292 For right associativity, keep only the shift.
293 For nonassociativity, keep neither. */
709ae8c6 294
e9690142
JD
295 switch (symbols[i]->assoc)
296 {
d78f0ac9 297 case undef_assoc:
e9690142 298 abort ();
68cae94e 299
d78f0ac9
AD
300 case precedence_assoc:
301 break;
302
e9690142
JD
303 case right_assoc:
304 log_resolution (redrule, i, right_resolution);
305 flush_reduce (lookahead_tokens, i);
306 break;
307
308 case left_assoc:
309 log_resolution (redrule, i, left_resolution);
310 flush_shift (s, i);
311 break;
312
313 case non_assoc:
314 log_resolution (redrule, i, nonassoc_resolution);
315 flush_shift (s, i);
316 flush_reduce (lookahead_tokens, i);
317 /* Record an explicit error for this token. */
318 errors[(*nerrs)++] = symbols[i];
319 break;
320 }
92b16366 321 }
08089d5d
DM
322}
323
324
8b752b00 325/*-------------------------------------------------------------------.
f041e30b 326| Solve the S/R conflicts of state S using the |
8b752b00 327| precedence/associativity, and flag it inconsistent if it still has |
f041e30b 328| conflicts. ERRORS can be used as storage to compute the list of |
742e4900 329| lookahead tokens on which S raises a syntax error (%nonassoc). |
8b752b00
AD
330`-------------------------------------------------------------------*/
331
4a120d45 332static void
f041e30b 333set_conflicts (state *s, symbol **errors)
08089d5d 334{
914feea9 335 int i;
f041e30b
PE
336 transitions *trans = s->transitions;
337 reductions *reds = s->reductions;
9d774aff 338 int nerrs = 0;
c29240e7 339
f041e30b 340 if (s->consistent)
c29240e7 341 return;
08089d5d 342
742e4900 343 bitset_zero (lookahead_set);
08089d5d 344
f041e30b 345 FOR_EACH_SHIFT (trans, i)
742e4900 346 bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
08089d5d 347
742e4900 348 /* Loop over all rules which require lookahead in this state. First
c29240e7 349 check for shift-reduce conflict, and try to resolve using
9801d40c 350 precedence. */
cd08e51e
AD
351 for (i = 0; i < reds->num; ++i)
352 if (reds->rules[i]->prec && reds->rules[i]->prec->prec
e9690142 353 && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
9d774aff
JD
354 resolve_sr_conflict (s, i, errors, &nerrs);
355
356 if (nerrs)
357 {
358 /* Some tokens have been explicitly made errors. Allocate a
359 permanent errs structure for this state, to record them. */
360 state_errs_set (s, nerrs, errors);
361 }
362 if (obstack_object_size (&solved_conflicts_obstack))
6fbe73b6 363 s->solved_conflicts = obstack_finish0 (&solved_conflicts_obstack);
41d7a5f2 364 if (obstack_object_size (&solved_conflicts_xml_obstack))
6fbe73b6 365 s->solved_conflicts_xml = obstack_finish0 (&solved_conflicts_xml_obstack);
08089d5d 366
742e4900 367 /* Loop over all rules which require lookahead in this state. Check
c29240e7 368 for conflicts not resolved above. */
cd08e51e 369 for (i = 0; i < reds->num; ++i)
08089d5d 370 {
742e4900 371 if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
e9690142 372 conflicts[s->number] = 1;
742e4900 373 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
c29240e7
AD
374 }
375}
08089d5d 376
8b752b00
AD
377
378/*----------------------------------------------------------------.
379| Solve all the S/R conflicts using the precedence/associativity, |
380| and flag as inconsistent the states that still have conflicts. |
381`----------------------------------------------------------------*/
382
08089d5d 383void
b408954b 384conflicts_solve (void)
08089d5d 385{
f041e30b 386 state_number i;
742e4900 387 /* List of lookahead tokens on which we explicitly raise a syntax error. */
da2a7671 388 symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);
08089d5d 389
da2a7671 390 conflicts = xcalloc (nstates, sizeof *conflicts);
8dd162d3 391 shift_set = bitset_create (ntokens, BITSET_FIXED);
742e4900 392 lookahead_set = bitset_create (ntokens, BITSET_FIXED);
b408954b 393 obstack_init (&solved_conflicts_obstack);
41d7a5f2 394 obstack_init (&solved_conflicts_xml_obstack);
08089d5d 395
c29240e7 396 for (i = 0; i < nstates; i++)
8b752b00 397 {
f041e30b 398 set_conflicts (states[i], errors);
8b752b00
AD
399
400 /* For uniformity of the code, make sure all the states have a valid
e9690142 401 `errs' member. */
8b752b00 402 if (!states[i]->errs)
e9690142 403 states[i]->errs = errs_new (0, 0);
8b752b00
AD
404 }
405
f041e30b 406 free (errors);
08089d5d
DM
407}
408
409
5967f0cf
JD
410void
411conflicts_update_state_numbers (state_number old_to_new[],
412 state_number nstates_old)
413{
14462c2b
JD
414 state_number i;
415 for (i = 0; i < nstates_old; ++i)
5967f0cf
JD
416 if (old_to_new[i] != nstates_old)
417 conflicts[old_to_new[i]] = conflicts[i];
418}
419
420
c29240e7
AD
421/*---------------------------------------------.
422| Count the number of shift/reduce conflicts. |
423`---------------------------------------------*/
424
6c094ad0
AD
425static size_t
426count_state_sr_conflicts (state *s)
08089d5d 427{
f9abaa2c 428 int i;
f041e30b
PE
429 transitions *trans = s->transitions;
430 reductions *reds = s->reductions;
08089d5d 431
f041e30b 432 if (!trans)
0df87bb6 433 return 0;
08089d5d 434
742e4900 435 bitset_zero (lookahead_set);
8dd162d3 436 bitset_zero (shift_set);
08089d5d 437
f041e30b 438 FOR_EACH_SHIFT (trans, i)
8dd162d3 439 bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
08089d5d 440
cd08e51e 441 for (i = 0; i < reds->num; ++i)
742e4900 442 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
08089d5d 443
742e4900 444 bitset_and (lookahead_set, lookahead_set, shift_set);
08089d5d 445
6c094ad0
AD
446 return bitset_count (lookahead_set);
447}
0df87bb6 448
6c094ad0
AD
449/*---------------------------------------------.
450| The total number of shift/reduce conflicts. |
451`---------------------------------------------*/
452
453static size_t
454count_sr_conflicts (void)
455{
456 size_t res = 0;
457 state_number i;
458
459 /* Conflicts by state. */
460 for (i = 0; i < nstates; i++)
461 if (conflicts[i])
462 res += count_state_sr_conflicts (states[i]);
463 return res;
08089d5d
DM
464}
465
466
6c094ad0 467
676385e2
PH
468/*----------------------------------------------------------------.
469| Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, |
470| count one conflict for each token that has any reduce/reduce |
471| conflicts. Otherwise, count one conflict for each pair of |
472| conflicting reductions. |
6c094ad0 473`----------------------------------------------------------------*/
c29240e7 474
6c094ad0
AD
475static size_t
476count_state_rr_conflicts (state *s, bool one_per_token)
08089d5d 477{
c29240e7 478 int i;
f041e30b 479 reductions *reds = s->reductions;
6c094ad0 480 size_t res = 0;
08089d5d 481
08089d5d
DM
482 for (i = 0; i < ntokens; i++)
483 {
0df87bb6
AD
484 int count = 0;
485 int j;
cd08e51e 486 for (j = 0; j < reds->num; ++j)
6c094ad0 487 count += bitset_test (reds->lookahead_tokens[j], i);
c29240e7 488 if (count >= 2)
6c094ad0 489 res += one_per_token ? 1 : count-1;
08089d5d 490 }
0df87bb6 491
6c094ad0 492 return res;
08089d5d
DM
493}
494
6c094ad0
AD
495static size_t
496count_rr_conflicts (bool one_per_token)
497{
498 size_t res = 0;
499 state_number i;
500
501 /* Conflicts by state. */
502 for (i = 0; i < nstates; i++)
503 if (conflicts[i])
504 res += count_state_rr_conflicts (states[i], one_per_token);
505 return res;
506}
52489d44 507
52489d44 508
0df87bb6
AD
509/*-----------------------------------------------------------.
510| Output the detailed description of states with conflicts. |
511`-----------------------------------------------------------*/
c29240e7
AD
512
513void
0df87bb6 514conflicts_output (FILE *out)
c29240e7 515{
8307162d 516 bool printed_sth = false;
f041e30b 517 state_number i;
0df87bb6 518 for (i = 0; i < nstates; i++)
640748ee 519 {
f041e30b 520 state *s = states[i];
640748ee 521 if (conflicts[i])
e9690142 522 {
d87ea54c
AD
523 int src = count_state_sr_conflicts (s);
524 int rrc = count_state_rr_conflicts (s, true);
e9690142 525 fprintf (out, _("State %d "), i);
d87ea54c
AD
526 if (src && rrc)
527 fprintf (out,
528 _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
529 src, rrc);
530 else if (src)
531 fprintf (out, _("conflicts: %d shift/reduce\n"), src);
532 else if (rrc)
533 fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc);
e9690142
JD
534 printed_sth = true;
535 }
640748ee 536 }
d2d1b42b
AD
537 if (printed_sth)
538 fputs ("\n\n", out);
0df87bb6 539}
c29240e7 540
676385e2
PH
541/*--------------------------------------------------------.
542| Total the number of S/R and R/R conflicts. Unlike the |
543| code in conflicts_output, however, count EACH pair of |
742e4900 544| reductions for the same state and lookahead as one |
e9690142 545| conflict. |
676385e2
PH
546`--------------------------------------------------------*/
547
548int
549conflicts_total_count (void)
550{
6c094ad0 551 return count_sr_conflicts () + count_rr_conflicts (false);
676385e2 552}
e0e5bf84 553
c29240e7 554
0df87bb6
AD
555/*------------------------------------------.
556| Reporting the total number of conflicts. |
557`------------------------------------------*/
0619caf0 558
0df87bb6
AD
559void
560conflicts_print (void)
561{
d1400569 562 if (! glr_parser && expected_rr_conflicts != -1)
d6328241 563 {
bb8e56ff 564 complain (NULL, Wother, _("%%expect-rr applies only to GLR parsers"));
d6328241
PH
565 expected_rr_conflicts = -1;
566 }
567
d87ea54c
AD
568 /* Screams for factoring, but almost useless because of the
569 different strings to translate. */
570 {
571 int total = count_sr_conflicts ();
572 // If %expect is not used, but %expect-rr is, then expect 0 sr.
573 int expected =
574 (expected_sr_conflicts == -1 && expected_rr_conflicts != -1)
575 ? 0
576 : expected_sr_conflicts;
577 if (expected != -1)
578 {
579 if (expected != total)
bb8e56ff 580 complain (NULL, complaint,
d87ea54c
AD
581 _("shift/reduce conflicts: %d found, %d expected"),
582 total, expected);
583 }
584 else if (total)
bb8e56ff 585 complain (NULL, Wconflicts_sr,
d87ea54c
AD
586 ngettext ("%d shift/reduce conflict",
587 "%d shift/reduce conflicts",
588 total),
589 total);
590 }
7da99ede 591
d87ea54c
AD
592 {
593 int total = count_rr_conflicts (true);
594 // If %expect-rr is not used, but %expect is, then expect 0 rr.
595 int expected =
596 (expected_rr_conflicts == -1 && expected_sr_conflicts != -1)
597 ? 0
598 : expected_rr_conflicts;
599 if (expected != -1)
600 {
601 if (expected != total)
bb8e56ff 602 complain (NULL, complaint,
d87ea54c
AD
603 _("reduce/reduce conflicts: %d found, %d expected"),
604 total, expected);
605 }
606 else if (total)
bb8e56ff 607 complain (NULL, Wconflicts_rr,
d87ea54c
AD
608 ngettext ("%d reduce/reduce conflict",
609 "%d reduce/reduce conflicts",
610 total),
611 total);
612 }
c29240e7
AD
613}
614
615
08089d5d 616void
b408954b 617conflicts_free (void)
08089d5d 618{
afbb696d 619 free (conflicts);
8dd162d3 620 bitset_free (shift_set);
742e4900 621 bitset_free (lookahead_set);
b408954b 622 obstack_free (&solved_conflicts_obstack, NULL);
41d7a5f2 623 obstack_free (&solved_conflicts_xml_obstack, NULL);
08089d5d 624}