Fix the previous test.
[bison.git] / src / conflicts.c
CommitLineData
08089d5d 1/* Find and resolve or report look-ahead conflicts for bison,
22c821f3 2 Copyright 1984, 1989, 1992, 2000, 2001 Free Software Foundation, Inc.
08089d5d 3
ceed8467 4 This file is part of Bison, the GNU Compiler Compiler.
08089d5d 5
ceed8467
AD
6 Bison is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
08089d5d 10
ceed8467
AD
11 Bison is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
08089d5d 15
ceed8467
AD
16 You should have received a copy of the GNU General Public License
17 along with Bison; see the file COPYING. If not, write to the Free
18 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA. */
08089d5d 20
08089d5d 21#include "system.h"
7da99ede 22#include "complain.h"
ceed8467 23#include "getargs.h"
0e78e603 24#include "symtab.h"
08089d5d
DM
25#include "files.h"
26#include "gram.h"
27#include "state.h"
720d742f 28#include "lalr.h"
0619caf0 29#include "conflicts.h"
b2ca4022
AD
30#include "reader.h"
31#include "LR0.h"
d2729d44 32
7da99ede
AD
33/* -1 stands for not specified. */
34int expected_conflicts = -1;
342b8b6e 35static char *conflicts = NULL;
08089d5d 36
342b8b6e
AD
37static unsigned *shiftset = NULL;
38static unsigned *lookaheadset = NULL;
c29240e7 39\f
08089d5d 40
c29240e7 41static inline void
065fbd27 42log_resolution (state_t *state, int LAno, int token, char *resolution)
08089d5d 43{
64d15509
AD
44 if (verbose_flag)
45 obstack_fgrow4 (&output_obstack,
46 _("\
c29240e7 47Conflict in state %d between rule %d and token %s resolved as %s.\n"),
ad949da9
AD
48 state->number, LAruleno[LAno], symbols[token]->tag,
49 resolution);
08089d5d
DM
50}
51
52
c29240e7
AD
53/*------------------------------------------------------------------.
54| Turn off the shift recorded for the specified token in the |
55| specified state. Used when we resolve a shift-reduce conflict in |
56| favor of the reduction. |
57`------------------------------------------------------------------*/
58
4a120d45 59static void
065fbd27 60flush_shift (state_t *state, int token)
08089d5d 61{
065fbd27 62 shifts *shiftp = state->shifts;
9f136c07 63 int i;
c29240e7 64
709ae8c6 65 RESETBIT (lookaheadset, token);
d954473d
AD
66 for (i = 0; i < shiftp->nshifts; i++)
67 if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token)
68 SHIFT_DISABLE (shiftp, i);
08089d5d
DM
69}
70
71
709ae8c6
AD
72/*-------------------------------------------------------------------.
73| Turn off the reduce recorded for the specified token for the |
74| specified lookahead. Used when we resolve a shift-reduce conflict |
75| in favor of the shift. |
76`-------------------------------------------------------------------*/
77
78static void
79flush_reduce (int lookahead, int token)
80{
81 RESETBIT (LA (lookahead), token);
82}
83
84
c29240e7
AD
85/*------------------------------------------------------------------.
86| Attempt to resolve shift-reduce conflict for one rule by means of |
87| precedence declarations. It has already been checked that the |
88| rule has a precedence. A conflict is resolved by modifying the |
89| shift or reduce tables so that there is no longer a conflict. |
90`------------------------------------------------------------------*/
08089d5d 91
4a120d45 92static void
065fbd27 93resolve_sr_conflict (state_t *state, int lookahead)
08089d5d 94{
c29240e7 95 int i;
9f136c07 96 /* find the rule to reduce by to get precedence of reduction */
1a2b5d37 97 int redprec = rules[LAruleno[lookahead]].prec;
2cec70b9
AD
98 errs *errp = errs_new (ntokens + 1);
99 errp->nerrs = 0;
08089d5d 100
08089d5d 101 for (i = 0; i < ntokens; i++)
709ae8c6 102 if (BITISSET (LA (lookahead), i)
92b16366 103 && BITISSET (lookaheadset, i)
0e78e603 104 && symbols[i]->prec)
92b16366 105 {
709ae8c6
AD
106 /* Shift-reduce conflict occurs for token number i
107 and it has a precedence.
108 The precedence of shifting is that of token i. */
0e78e603 109 if (symbols[i]->prec < redprec)
92b16366 110 {
709ae8c6 111 log_resolution (state, lookahead, i, _("reduce"));
92b16366
AD
112 flush_shift (state, i);
113 }
0e78e603 114 else if (symbols[i]->prec > redprec)
92b16366 115 {
709ae8c6
AD
116 log_resolution (state, lookahead, i, _("shift"));
117 flush_reduce (lookahead, i);
92b16366
AD
118 }
119 else
709ae8c6
AD
120 /* Matching precedence levels.
121 For left association, keep only the reduction.
122 For right association, keep only the shift.
123 For nonassociation, keep neither. */
124
5a670b1e 125 switch (symbols[i]->assoc)
709ae8c6
AD
126 {
127 case right_assoc:
128 log_resolution (state, lookahead, i, _("shift"));
129 flush_reduce (lookahead, i);
130 break;
131
132 case left_assoc:
133 log_resolution (state, lookahead, i, _("reduce"));
134 flush_shift (state, i);
135 break;
136
137 case non_assoc:
138 log_resolution (state, lookahead, i, _("an error"));
139 flush_shift (state, i);
140 flush_reduce (lookahead, i);
141 /* Record an explicit error for this token. */
2cec70b9 142 errp->errs[errp->nerrs++] = i;
709ae8c6
AD
143 break;
144 }
92b16366
AD
145 }
146
92b16366
AD
147 /* Some tokens have been explicitly made errors. Allocate a
148 permanent errs structure for this state, to record them. */
2cec70b9 149 state->errs = errs_dup (errp);
c29240e7 150 free (errp);
08089d5d
DM
151}
152
153
4a120d45 154static void
065fbd27 155set_conflicts (state_t *state)
08089d5d 156{
d8cf039f 157 int i, j;
c29240e7 158 shifts *shiftp;
c29240e7 159
065fbd27 160 if (state->consistent)
c29240e7 161 return;
08089d5d 162
c29240e7
AD
163 for (i = 0; i < tokensetsize; i++)
164 lookaheadset[i] = 0;
08089d5d 165
065fbd27 166 shiftp = state->shifts;
d954473d
AD
167 for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
168 if (!SHIFT_IS_DISABLED (shiftp, i))
169 SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i));
08089d5d 170
c29240e7
AD
171 /* Loop over all rules which require lookahead in this state. First
172 check for shift-reduce conflict, and try to resolve using
173 precedence */
065fbd27 174 for (i = 0; i < state->nlookaheads; ++i)
1a2b5d37 175 if (rules[LAruleno[state->lookaheadsp + i]].prec)
d8cf039f 176 for (j = 0; j < tokensetsize; ++j)
065fbd27 177 if (LA (state->lookaheadsp + i)[j] & lookaheadset[j])
c29240e7 178 {
065fbd27 179 resolve_sr_conflict (state, state->lookaheadsp + i);
d8cf039f 180 break;
c29240e7 181 }
08089d5d 182
08089d5d 183
c29240e7
AD
184 /* Loop over all rules which require lookahead in this state. Check
185 for conflicts not resolved above. */
065fbd27 186 for (i = 0; i < state->nlookaheads; ++i)
08089d5d 187 {
d8cf039f 188 for (j = 0; j < tokensetsize; ++j)
065fbd27
AD
189 if (LA (state->lookaheadsp + i)[j] & lookaheadset[j])
190 conflicts[state->number] = 1;
08089d5d 191
d8cf039f 192 for (j = 0; j < tokensetsize; ++j)
065fbd27 193 lookaheadset[j] |= LA (state->lookaheadsp + i)[j];
c29240e7
AD
194 }
195}
08089d5d
DM
196
197void
342b8b6e 198solve_conflicts (void)
08089d5d 199{
c29240e7 200 int i;
08089d5d 201
d7913476
AD
202 conflicts = XCALLOC (char, nstates);
203 shiftset = XCALLOC (unsigned, tokensetsize);
204 lookaheadset = XCALLOC (unsigned, tokensetsize);
08089d5d 205
c29240e7 206 for (i = 0; i < nstates; i++)
29e88316 207 set_conflicts (states[i]);
08089d5d
DM
208}
209
210
c29240e7
AD
211/*---------------------------------------------.
212| Count the number of shift/reduce conflicts. |
213`---------------------------------------------*/
214
0df87bb6 215static int
065fbd27 216count_sr_conflicts (state_t *state)
08089d5d 217{
52afa962 218 int i, k;
0df87bb6 219 int src_count = 0;
065fbd27 220 shifts *shiftp = state->shifts;
08089d5d 221
c29240e7 222 if (!shiftp)
0df87bb6 223 return 0;
08089d5d
DM
224
225 for (i = 0; i < tokensetsize; i++)
226 {
227 shiftset[i] = 0;
228 lookaheadset[i] = 0;
229 }
230
52afa962 231 for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
9839bbe5
AD
232 if (!SHIFT_IS_DISABLED (shiftp, i))
233 SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
08089d5d 234
065fbd27 235 for (i = 0; i < state->nlookaheads; ++i)
52afa962 236 for (k = 0; k < tokensetsize; ++k)
065fbd27 237 lookaheadset[k] |= LA (state->lookaheadsp + i)[k];
08089d5d 238
52afa962
AD
239 for (k = 0; k < tokensetsize; ++k)
240 lookaheadset[k] &= shiftset[k];
08089d5d 241
08089d5d 242 for (i = 0; i < ntokens; i++)
52afa962
AD
243 if (BITISSET (lookaheadset, i))
244 src_count++;
0df87bb6
AD
245
246 return src_count;
08089d5d
DM
247}
248
249
c29240e7
AD
250/*----------------------------------------------.
251| Count the number of reduce/reduce conflicts. |
252`----------------------------------------------*/
253
0df87bb6 254static int
065fbd27 255count_rr_conflicts (state_t *state)
08089d5d 256{
c29240e7 257 int i;
0df87bb6 258 int rrc_count = 0;
08089d5d 259
065fbd27 260 if (state->nlookaheads < 2)
0df87bb6 261 return 0;
08089d5d 262
08089d5d
DM
263 for (i = 0; i < ntokens; i++)
264 {
0df87bb6
AD
265 int count = 0;
266 int j;
065fbd27 267 for (j = 0; j < state->nlookaheads; ++j)
3460813b 268 if (BITISSET (LA (state->lookaheadsp + j), i))
52afa962 269 count++;
08089d5d 270
c29240e7
AD
271 if (count >= 2)
272 rrc_count++;
08089d5d 273 }
0df87bb6
AD
274
275 return rrc_count;
08089d5d
DM
276}
277
ff4423cc
AD
278/*--------------------------------------------------------------.
279| Return a human readable string which reports shift/reduce and |
280| reduce/reduce conflict numbers (SRC_NUM, RRC_NUM). |
281`--------------------------------------------------------------*/
c29240e7 282
ff4423cc
AD
283static const char *
284conflict_report (int src_num, int rrc_num)
c29240e7 285{
ff4423cc
AD
286 static char res[4096];
287 char *cp = res;
288
7da99ede 289 if (src_num >= 1)
22c821f3 290 {
7da99ede
AD
291 sprintf (cp, ngettext ("%d shift/reduce conflict",
292 "%d shift/reduce conflicts", src_num), src_num);
22c821f3
AD
293 cp += strlen (cp);
294 }
c29240e7 295
0619caf0 296 if (src_num > 0 && rrc_num > 0)
22c821f3 297 {
7da99ede 298 sprintf (cp, " %s ", _("and"));
22c821f3
AD
299 cp += strlen (cp);
300 }
c29240e7 301
7da99ede 302 if (rrc_num >= 1)
22c821f3 303 {
7da99ede
AD
304 sprintf (cp, ngettext ("%d reduce/reduce conflict",
305 "%d reduce/reduce conflicts", rrc_num), rrc_num);
22c821f3
AD
306 cp += strlen (cp);
307 }
ff4423cc
AD
308
309 *cp++ = '.';
310 *cp++ = '\n';
311 *cp++ = '\0';
c29240e7 312
ff4423cc 313 return res;
c29240e7
AD
314}
315
316
0df87bb6
AD
317/*-----------------------------------------------------------.
318| Output the detailed description of states with conflicts. |
319`-----------------------------------------------------------*/
c29240e7
AD
320
321void
0df87bb6 322conflicts_output (FILE *out)
c29240e7 323{
d2d1b42b 324 bool printed_sth = FALSE;
c29240e7 325 int i;
0df87bb6
AD
326 for (i = 0; i < nstates; i++)
327 if (conflicts[i])
328 {
7da99ede 329 fprintf (out, _("State %d contains "), i);
29e88316
AD
330 fputs (conflict_report (count_sr_conflicts (states[i]),
331 count_rr_conflicts (states[i])), out);
d2d1b42b 332 printed_sth = TRUE;
0df87bb6 333 }
d2d1b42b
AD
334 if (printed_sth)
335 fputs ("\n\n", out);
0df87bb6 336}
c29240e7 337
c29240e7 338
0df87bb6
AD
339/*------------------------------------------.
340| Reporting the total number of conflicts. |
341`------------------------------------------*/
0619caf0 342
0df87bb6
AD
343void
344conflicts_print (void)
345{
346 int i;
347
a034c8b8
AD
348 /* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is
349 not set, and then we want 0 SR, or else it is specified, in which
350 case we want equality. */
351 int src_ok = 0;
352
0df87bb6
AD
353 int src_total = 0;
354 int rrc_total = 0;
355
356 /* Conflicts by state. */
357 for (i = 0; i < nstates; i++)
358 if (conflicts[i])
359 {
29e88316
AD
360 src_total += count_sr_conflicts (states[i]);
361 rrc_total += count_rr_conflicts (states[i]);
0df87bb6 362 }
c29240e7 363
a034c8b8
AD
364 src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);
365
366 /* If there are no RR conflicts, and as many SR conflicts as
367 expected, then there is nothing to report. */
368 if (!rrc_total && src_ok)
369 return;
370
0619caf0 371 /* Report the total number of conflicts on STDERR. */
a034c8b8 372 if (yacc_flag)
09b503c8 373 {
a034c8b8
AD
374 /* If invoked with `--yacc', use the output format specified by
375 POSIX. */
376 fprintf (stderr, _("conflicts: "));
377 if (src_total > 0)
378 fprintf (stderr, _(" %d shift/reduce"), src_total);
379 if (src_total > 0 && rrc_total > 0)
380 fprintf (stderr, ",");
381 if (rrc_total > 0)
382 fprintf (stderr, _(" %d reduce/reduce"), rrc_total);
383 putc ('\n', stderr);
384 }
385 else
386 {
387 fprintf (stderr, _("%s contains "), infile);
388 fputs (conflict_report (src_total, rrc_total), stderr);
09b503c8 389 }
7da99ede 390
a034c8b8 391 if (expected_conflicts != -1 && !src_ok)
7da99ede
AD
392 {
393 complain_message_count++;
81e895c0
AD
394 fprintf (stderr, ngettext ("expected %d shift/reduce conflict\n",
395 "expected %d shift/reduce conflicts\n",
7da99ede
AD
396 expected_conflicts),
397 expected_conflicts);
398 }
c29240e7
AD
399}
400
401
08089d5d 402void
342b8b6e 403free_conflicts (void)
08089d5d 404{
d7913476
AD
405 XFREE (conflicts);
406 XFREE (shiftset);
407 XFREE (lookaheadset);
08089d5d 408}