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