src/conflicts.c

/* Find and resolve or report lookahead conflicts for bison,

   Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005,
   2006, 2007, 2009 Free Software Foundation, Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include <config.h>
#include "system.h"

#include <bitset.h>

#include "LR0.h"
#include "complain.h"
#include "conflicts.h"
#include "files.h"
#include "getargs.h"
#include "gram.h"
#include "lalr.h"
#include "print-xml.h"
#include "reader.h"
#include "state.h"
#include "symtab.h"

/* -1 stands for not specified. */
int expected_sr_conflicts = -1;
int expected_rr_conflicts = -1;
static char *conflicts;
static struct obstack solved_conflicts_obstack;
static struct obstack solved_conflicts_xml_obstack;

static bitset shift_set;
static bitset lookahead_set;

\f

enum conflict_resolution
  {
    shift_resolution,
    reduce_resolution,
    left_resolution,
    right_resolution,
    nonassoc_resolution
  };


/*----------------------------------------------------------------.
| Explain how an SR conflict between TOKEN and RULE was resolved: |
| RESOLUTION.                                                     |
`----------------------------------------------------------------*/

static inline void
log_resolution (rule *r, symbol_number token,
		enum conflict_resolution resolution)
{
  if (report_flag & report_solved_conflicts)
    {
      /* The description of the resolution. */
      switch (resolution)
	{
	case shift_resolution:
	case right_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("    Conflict between rule %d and token %s"
			    " resolved as shift"),
			  r->number,
			  symbols[token]->tag);
	  break;

	case reduce_resolution:
	case left_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("    Conflict between rule %d and token %s"
			    " resolved as reduce"),
			  r->number,
			  symbols[token]->tag);
	  break;

	case nonassoc_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("    Conflict between rule %d and token %s"
			    " resolved as an error"),
			  r->number,
			  symbols[token]->tag);
	  break;
	}

      /* The reason. */
      switch (resolution)
	{
	case shift_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  " (%s < %s)",
			  r->prec->tag,
			  symbols[token]->tag);
	  break;

	case reduce_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  " (%s < %s)",
			  symbols[token]->tag,
			  r->prec->tag);
	  break;

	case left_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%left %s)",
			  symbols[token]->tag);
	  break;

	case right_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%right %s)",
			  symbols[token]->tag);
	  break;

	case nonassoc_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%nonassoc %s)",
			  symbols[token]->tag);
	  break;
	}

      obstack_sgrow (&solved_conflicts_obstack, ".\n");
    }

  /* XML report */
  if (xml_flag)
    {
      /* The description of the resolution. */
      switch (resolution)
        {
        case shift_resolution:
        case right_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "        <resolution rule=\"%d\" symbol=\"%s\""
                          " type=\"shift\">",
                          r->number,
                          xml_escape (symbols[token]->tag));
          break;

        case reduce_resolution:
        case left_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "        <resolution rule=\"%d\" symbol=\"%s\""
                          " type=\"reduce\">",
                          r->number,
                          xml_escape (symbols[token]->tag));
          break;

        case nonassoc_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "        <resolution rule=\"%d\" symbol=\"%s\""
                          " type=\"error\">",
                          r->number,
                          xml_escape (symbols[token]->tag));
          break;
        }

      /* The reason. */
      switch (resolution)
        {
        case shift_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "%s &lt; %s",
                          xml_escape_n (0, r->prec->tag),
                          xml_escape_n (1, symbols[token]->tag));
          break;

        case reduce_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "%s &lt; %s",
                          xml_escape_n (0, symbols[token]->tag),
                          xml_escape_n (1, r->prec->tag));
          break;

        case left_resolution:
          obstack_fgrow1 (&solved_conflicts_xml_obstack,
                          "%%left %s",
                          xml_escape (symbols[token]->tag));
          break;

        case right_resolution:
          obstack_fgrow1 (&solved_conflicts_xml_obstack,
                          "%%right %s",
                          xml_escape (symbols[token]->tag));
          break;

        case nonassoc_resolution:
          obstack_fgrow1 (&solved_conflicts_xml_obstack,
                          "%%nonassoc %s",
                          xml_escape (symbols[token]->tag));
      break;
        }

      obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\n");
    }
}


/*------------------------------------------------------------------.
| Turn off the shift recorded for the specified token in the        |
| specified state.  Used when we resolve a shift-reduce conflict in |
| favor of the reduction or as an error (%nonassoc).                |
`------------------------------------------------------------------*/

static void
flush_shift (state *s, int token)
{
  transitions *trans = s->transitions;
  int i;

  bitset_reset (lookahead_set, token);
  for (i = 0; i < trans->num; i++)
    if (!TRANSITION_IS_DISABLED (trans, i)
	&& TRANSITION_SYMBOL (trans, i) == token)
      TRANSITION_DISABLE (trans, i);
}


/*--------------------------------------------------------------------.
| Turn off the reduce recorded for the specified token in the         |
| specified lookahead set.  Used when we resolve a shift-reduce       |
| conflict in favor of the shift or as an error (%nonassoc).          |
`--------------------------------------------------------------------*/

static void
flush_reduce (bitset lookahead_tokens, int token)
{
  bitset_reset (lookahead_tokens, token);
}


/*------------------------------------------------------------------.
| Attempt to resolve shift-reduce conflict for one rule by means of |
| precedence declarations.  It has already been checked that the    |
| rule has a precedence.  A conflict is resolved by modifying the   |
| shift or reduce tables so that there is no longer a conflict.     |
|                                                                   |
| RULENO is the number of the lookahead bitset to consider.         |
|                                                                   |
| ERRORS and NERRS can be used to store discovered explicit         |
| errors.                                                           |
`------------------------------------------------------------------*/

static void
resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
{
  symbol_number i;
  reductions *reds = s->reductions;
  /* Find the rule to reduce by to get precedence of reduction.  */
  rule *redrule = reds->rules[ruleno];
  int redprec = redrule->prec->prec;
  bitset lookahead_tokens = reds->lookahead_tokens[ruleno];

  for (i = 0; i < ntokens; i++)
    if (bitset_test (lookahead_tokens, i)
	&& bitset_test (lookahead_set, i)
	&& symbols[i]->prec)
      {
	/* Shift-reduce conflict occurs for token number i
	   and it has a precedence.
	   The precedence of shifting is that of token i.  */
	if (symbols[i]->prec < redprec)
	  {
	    log_resolution (redrule, i, reduce_resolution);
	    flush_shift (s, i);
	  }
	else if (symbols[i]->prec > redprec)
	  {
	    log_resolution (redrule, i, shift_resolution);
	    flush_reduce (lookahead_tokens, i);
	  }
	else
	  /* Matching precedence levels.
	     For left association, keep only the reduction.
	     For right association, keep only the shift.
	     For nonassociation, keep neither.  */

	  switch (symbols[i]->assoc)
	    {
	    default:
	      abort ();

	    case right_assoc:
	      log_resolution (redrule, i, right_resolution);
	      flush_reduce (lookahead_tokens, i);
	      break;

	    case left_assoc:
	      log_resolution (redrule, i, left_resolution);
	      flush_shift (s, i);
	      break;

	    case non_assoc:
	      log_resolution (redrule, i, nonassoc_resolution);
	      flush_shift (s, i);
	      flush_reduce (lookahead_tokens, i);
	      /* Record an explicit error for this token.  */
	      errors[(*nerrs)++] = symbols[i];
	      break;
	    }
      }
}


/*-------------------------------------------------------------------.
| Solve the S/R conflicts of state S using the                       |
| precedence/associativity, and flag it inconsistent if it still has |
| conflicts.  ERRORS can be used as storage to compute the list of   |
| lookahead tokens on which S raises a syntax error (%nonassoc).     |
`-------------------------------------------------------------------*/

static void
set_conflicts (state *s, symbol **errors)
{
  int i;
  transitions *trans = s->transitions;
  reductions *reds = s->reductions;
  int nerrs = 0;

  if (s->consistent)
    return;

  bitset_zero (lookahead_set);

  FOR_EACH_SHIFT (trans, i)
    bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));

  /* Loop over all rules which require lookahead in this state.  First
     check for shift-reduce conflict, and try to resolve using
     precedence.  */
  for (i = 0; i < reds->num; ++i)
    if (reds->rules[i]->prec && reds->rules[i]->prec->prec
	&& !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
      resolve_sr_conflict (s, i, errors, &nerrs);

  if (nerrs)
    {
      /* Some tokens have been explicitly made errors.  Allocate a
         permanent errs structure for this state, to record them.  */
      state_errs_set (s, nerrs, errors);
    }
  if (obstack_object_size (&solved_conflicts_obstack))
    {
      obstack_1grow (&solved_conflicts_obstack, '\0');
      s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
    }
  if (obstack_object_size (&solved_conflicts_xml_obstack))
    {
      obstack_1grow (&solved_conflicts_xml_obstack, '\0');
      s->solved_conflicts_xml = obstack_finish (&solved_conflicts_xml_obstack);
    }

  /* Loop over all rules which require lookahead in this state.  Check
     for conflicts not resolved above.  */
  for (i = 0; i < reds->num; ++i)
    {
      if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
	conflicts[s->number] = 1;
      bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
    }
}


/*----------------------------------------------------------------.
| Solve all the S/R conflicts using the precedence/associativity, |
| and flag as inconsistent the states that still have conflicts.  |
`----------------------------------------------------------------*/

void
conflicts_solve (void)
{
  state_number i;
  /* List of lookahead tokens on which we explicitly raise a syntax error.  */
  symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);

  conflicts = xcalloc (nstates, sizeof *conflicts);
  shift_set = bitset_create (ntokens, BITSET_FIXED);
  lookahead_set = bitset_create (ntokens, BITSET_FIXED);
  obstack_init (&solved_conflicts_obstack);
  obstack_init (&solved_conflicts_xml_obstack);

  for (i = 0; i < nstates; i++)
    {
      set_conflicts (states[i], errors);

      /* For uniformity of the code, make sure all the states have a valid
	 `errs' member.  */
      if (!states[i]->errs)
	states[i]->errs = errs_new (0, 0);
    }

  free (errors);
}


void
conflicts_update_state_numbers (state_number old_to_new[],
                                state_number nstates_old)
{
  state_number i;
  for (i = 0; i < nstates_old; ++i)
    if (old_to_new[i] != nstates_old)
      conflicts[old_to_new[i]] = conflicts[i];
}


/*---------------------------------------------.
| Count the number of shift/reduce conflicts.  |
`---------------------------------------------*/

static int
count_sr_conflicts (state *s)
{
  int i;
  int src_count = 0;
  transitions *trans = s->transitions;
  reductions *reds = s->reductions;

  if (!trans)
    return 0;

  bitset_zero (lookahead_set);
  bitset_zero (shift_set);

  FOR_EACH_SHIFT (trans, i)
    bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));

  for (i = 0; i < reds->num; ++i)
    bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);

  bitset_and (lookahead_set, lookahead_set, shift_set);

  src_count = bitset_count (lookahead_set);

  return src_count;
}


/*----------------------------------------------------------------.
| Count the number of reduce/reduce conflicts.  If ONE_PER_TOKEN, |
| count one conflict for each token that has any reduce/reduce    |
| conflicts.  Otherwise, count one conflict for each pair of      |
| conflicting reductions.                                         |
+`----------------------------------------------------------------*/

static int
count_rr_conflicts (state *s, bool one_per_token)
{
  int i;
  reductions *reds = s->reductions;
  int rrc_count = 0;

  for (i = 0; i < ntokens; i++)
    {
      int count = 0;
      int j;
      for (j = 0; j < reds->num; ++j)
	if (bitset_test (reds->lookahead_tokens[j], i))
	  count++;

      if (count >= 2)
	rrc_count += one_per_token ? 1 : count-1;
    }

  return rrc_count;
}


/*--------------------------------------------------------.
| Report the number of conflicts, using the Yacc format.  |
`--------------------------------------------------------*/

static void
conflict_report (FILE *out, int src_num, int rrc_num)
{
  if (src_num && rrc_num)
    fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
	     src_num, rrc_num);
  else if (src_num)
    fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
  else if (rrc_num)
    fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
}


/*-----------------------------------------------------------.
| Output the detailed description of states with conflicts.  |
`-----------------------------------------------------------*/

void
conflicts_output (FILE *out)
{
  bool printed_sth = false;
  state_number i;
  for (i = 0; i < nstates; i++)
    {
      state *s = states[i];
      if (conflicts[i])
	{
	  fprintf (out, _("State %d "), i);
	  conflict_report (out, count_sr_conflicts (s),
			   count_rr_conflicts (s, true));
	  printed_sth = true;
	}
    }
  if (printed_sth)
    fputs ("\n\n", out);
}

/*--------------------------------------------------------.
| Total the number of S/R and R/R conflicts.  Unlike the  |
| code in conflicts_output, however, count EACH pair of   |
| reductions for the same state and lookahead as one      |
| conflict.						  |
`--------------------------------------------------------*/

int
conflicts_total_count (void)
{
  state_number i;
  int count;

  /* Conflicts by state.  */
  count = 0;
  for (i = 0; i < nstates; i++)
    if (conflicts[i])
      {
	count += count_sr_conflicts (states[i]);
	count += count_rr_conflicts (states[i], false);
      }
  return count;
}


/*------------------------------------------.
| Reporting the total number of conflicts.  |
`------------------------------------------*/

void
conflicts_print (void)
{
  /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
     not set, and then we want 0 SR, or else it is specified, in which
     case we want equality.  */
  bool src_ok;
  bool rrc_ok;

  int src_total = 0;
  int rrc_total = 0;
  int src_expected;
  int rrc_expected;

  /* Conflicts by state.  */
  {
    state_number i;

    for (i = 0; i < nstates; i++)
      if (conflicts[i])
	{
	  src_total += count_sr_conflicts (states[i]);
	  rrc_total += count_rr_conflicts (states[i], true);
	}
  }

  if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
    {
      warn (_("%%expect-rr applies only to GLR parsers"));
      expected_rr_conflicts = -1;
    }

  src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
  rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
  src_ok = src_total == src_expected;
  rrc_ok = rrc_total == rrc_expected;

  /* If there are as many RR conflicts and SR conflicts as
     expected, then there is nothing to report.  */
  if (rrc_ok & src_ok)
    return;

  /* Report the total number of conflicts on STDERR.  */
  if (src_total | rrc_total)
    {
      if (! yacc_flag)
	fprintf (stderr, "%s: ", current_file);
      conflict_report (stderr, src_total, rrc_total);
    }

  if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)
    {
      if (! src_ok)
	complain (ngettext ("expected %d shift/reduce conflict",
			    "expected %d shift/reduce conflicts",
			    src_expected),
		  src_expected);
      if (! rrc_ok)
	complain (ngettext ("expected %d reduce/reduce conflict",
			    "expected %d reduce/reduce conflicts",
			    rrc_expected),
		  rrc_expected);
    }
}


void
conflicts_free (void)
{
  free (conflicts);
  bitset_free (shift_set);
  bitset_free (lookahead_set);
  obstack_free (&solved_conflicts_obstack, NULL);
  obstack_free (&solved_conflicts_xml_obstack, NULL);
}
Commit	Line	Data
	1	/* Find and resolve or report lookahead conflicts for bison,
	2
	3	Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005,
	4	2006, 2007, 2009 Free Software 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 < %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 < %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 (src_total \| rrc_total)
	598	{
	599	if (! yacc_flag)
	600	fprintf (stderr, "%s: ", current_file);
	601	conflict_report (stderr, src_total, rrc_total);
	602	}
	603
	604	if (expected_sr_conflicts != -1 \|\| expected_rr_conflicts != -1)
	605	{
	606	if (! src_ok)
	607	complain (ngettext ("expected %d shift/reduce conflict",
	608	"expected %d shift/reduce conflicts",
	609	src_expected),
	610	src_expected);
	611	if (! rrc_ok)
	612	complain (ngettext ("expected %d reduce/reduce conflict",
	613	"expected %d reduce/reduce conflicts",
	614	rrc_expected),
	615	rrc_expected);
	616	}
	617	}
	618
	619
	620	void
	621	conflicts_free (void)
	622	{
	623	free (conflicts);
	624	bitset_free (shift_set);
	625	bitset_free (lookahead_set);
	626	obstack_free (&solved_conflicts_obstack, NULL);
	627	obstack_free (&solved_conflicts_xml_obstack, NULL);
	628	}