src/print_graph.c

/* Output a VCG description on generated parser, for Bison,
   Copyright 2001 Free Software Foundation, Inc.

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

   Bison 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 2, or (at your option)
   any later version.

   Bison 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 Bison; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */

#include "system.h"
#include "files.h"
#include "gram.h"
#include "LR0.h"
#include "lalr.h"
#include "conflicts.h"
#include "complain.h"
#include "getargs.h"
#include "state.h"
#include "reader.h"
#include "obstack.h"
#include "print_graph.h"
#include "vcg.h"
#include "quotearg.h"

static graph_t graph;
static FILE *fgraph = NULL;

static size_t node_output_size = 0;

/* Return an unambiguous printable representated, allocated in slot 0,
   for NAME, suitable for C strings.  */
static char const *
quote (char const *name)
{
  return quotearg_n_style (0, escape_quoting_style, name);
}

/* This part will construct the label of nodes. */
static void
print_core (int state, struct obstack *node_obstack)
{
  int i;
  int k;
  int rule;
  core *statep;
  short *sp;
  short *sp1;

  statep = state_table[state];
  k = statep->nitems;

  if (k == 0)
    return;

  for (i = 0; i < k; i++)
    {
      if (i)
	obstack_sgrow (node_obstack, "\\n");

      sp1 = sp = ritem + statep->items[i];

      while (*sp > 0)
	sp++;

      rule = -(*sp);

      obstack_fgrow1 (node_obstack, "%d: ", rule);
      obstack_fgrow1 (node_obstack, " %s  ->  ", quote (tags[rlhs[rule]]));

      for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
	obstack_fgrow1 (node_obstack, "%s ", quote (tags[*sp]));

      obstack_1grow (node_obstack, '.');

      while (*sp > 0)
	obstack_fgrow1 (node_obstack, " %s", quote (tags[*sp++]));
    }
}

/* Output in graph_obstack edges specifications in incidence with current
   node.  */
static void
print_actions (int state, const char *node_name, struct obstack *node_obstack)
{
  int i;
  int k;
  int state1;
  int symbol;
  shifts *shiftp;
  errs *errp;
  reductions *redp;
  int rule;
  static char buff[10];
  edge_t edge;

  shiftp = shift_table[state];
  redp = reduction_table[state];
  errp = err_table[state];

  if (!shiftp && !redp)
    {
      if (final_state == state)
	obstack_sgrow (node_obstack, "$default: accept");
      else
	obstack_sgrow (node_obstack, "NO ACTIONS");
      return;
    }

  if (shiftp)
    {
      k = shiftp->nshifts;

      for (i = 0; i < k; i++)
	{
	  if (!shiftp->shifts[i])
	    continue;
	  state1 = shiftp->shifts[i];
	  symbol = accessing_symbol[state1];

	  if (ISVAR (symbol))
	    break;

	  {
	    new_edge (&edge);

	    if (state > state1)
	      edge.type = back_edge;
	    open_edge (&edge, fgraph);
	    /* The edge source is the current node.  */
	    edge.sourcename = node_name;
	    sprintf (buff, "%d", state1);
	    edge.targetname = buff;
	    edge.color = (symbol == 0) ? red : blue;
	    /* FIXME: Be aware that quote uses static memory.  The string
	       must be output immediately (which is the case here). */
	    edge.label = tags[symbol] ? quote (tags[symbol]) : NULL;
	    output_edge (&edge, fgraph);
	    close_edge (fgraph);
	  }
	}
    }
  else
    {
      i = 0;
      k = 0;
    }

  if (errp)
    {
      int j, nerrs;

      nerrs = errp->nerrs;

      for (j = 0; j < nerrs; j++)
	{
	  if (!errp->errs[j])
	    continue;
	  symbol = errp->errs[j];
	  /* If something has been added in the NODE_OBSTACK after
	     the declaration of the label, then we need a `\n'.  */
	  if (obstack_object_size (node_obstack) > node_output_size)
	    obstack_sgrow (node_obstack, "\\n");
	  obstack_fgrow1 (node_obstack, _("%-4s\terror (nonassociative)"),
			  tags[symbol]);
	}
      if (j > 0)
	obstack_sgrow (node_obstack, "\\n");
    }

  if (consistent[state] && redp)
    {
      rule = redp->rules[0];
      symbol = rlhs[rule];
      if (obstack_object_size (node_obstack) > node_output_size)
	obstack_sgrow (node_obstack, "\\n");
      obstack_fgrow2 (node_obstack, _("$default\treduce using rule %d (%s)"),
		      rule, tags[symbol]);
    }

  if (i < k)
    {
      for (; i < k; i++)
	{
	  if (!shiftp->shifts[i])
	    continue;
	  state1 = shiftp->shifts[i];
	  symbol = accessing_symbol[state1];

	  new_edge (&edge);
	  open_edge (&edge, fgraph);
	  edge.sourcename = node_name;
	  sprintf (buff, "%d", state1);
	  edge.targetname = buff;
	  edge.color = red;
	  edge.label = tags[symbol] ? quote (tags[symbol]) : NULL;
	  output_edge (&edge, fgraph);
	  close_edge (fgraph);
	}
    }
}

/* Output in GRAPH_OBSTACK the current node specifications and edges
   which go out from that node.  */
static void
print_state (int state)
{
  static char name[10];
  struct obstack node_obstack;
  node_t node;

  obstack_init (&node_obstack);
  new_node (&node);	/* Set node attributs default value.  */
  sprintf (name, "%d", state);
  node.title = name;	/* Give a name to the node.  */

  {
    /* Here we begin to compute the node label. */
    obstack_sgrow (&node_obstack, "\t\tlabel:\t\"");	/* Open Label  */

    /* Keep the size of NODE_OBSTACK before computing the label. It is
       useful to format the label.  */
    node_output_size = obstack_object_size (&node_obstack);

    /* Compute the labels of nodes on the fly.  */
    print_core (state, &node_obstack);
    /* Compute edges and additionnal parts of node label.  */
    print_actions (state, node.title, &node_obstack);

    obstack_sgrow (&node_obstack, "\"\n");		/* Close Label.  */
  }

  open_node (fgraph);
  /* Output a VCG formatted attributs list.  */
  output_node (&node, fgraph);
  /* Save the node label.  */
  fwrite (obstack_base (&node_obstack),
	  obstack_object_size (&node_obstack), 1, fgraph);
  close_node (fgraph);

  obstack_free (&node_obstack, 0);
}
\f

void
print_graph (void)
{
  int i;

  if (!graph_flag)
    return;

  /* Output file.  */
  fgraph = xfopen (spec_graph_file, "w");

  new_graph (&graph);

#if 0
  graph.smanhattan_edges = yes;
  graph.manhattan_edges = yes;
#endif

  graph.display_edge_labels = yes;
  graph.layoutalgorithm = normal;

  graph.port_sharing = no;
  graph.finetuning = yes;
  graph.straight_phase = yes;
  graph.priority_phase = yes;
  graph.splines = yes;

  graph.crossing_weight = median;

  /* Output graph options. */
  open_graph (fgraph);
  output_graph (&graph, fgraph);

  for (i = 0; i < nstates; i++)
    /* Output nodes & edges. */
    print_state (i);

  /* Close graph. */
  close_graph (&graph, fgraph);
  xfclose (fgraph);
}
Commit	Line	Data
	1	/* Output a VCG description on generated parser, for Bison,
	2	Copyright 2001 Free Software Foundation, Inc.
	3
	4	This file is part of Bison, the GNU Compiler Compiler.
	5
	6	Bison is free software; you can redistribute it and/or modify
	7	it 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.
	10
	11	Bison is distributed in the hope that it will be useful,
	12	but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	GNU General Public License for more details.
	15
	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
	18	the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
	19	Boston, MA 02111-1307, USA. */
	20
	21	#include "system.h"
	22	#include "files.h"
	23	#include "gram.h"
	24	#include "LR0.h"
	25	#include "lalr.h"
	26	#include "conflicts.h"
	27	#include "complain.h"
	28	#include "getargs.h"
	29	#include "state.h"
	30	#include "reader.h"
	31	#include "obstack.h"
	32	#include "print_graph.h"
	33	#include "vcg.h"
	34	#include "quotearg.h"
	35
	36	static graph_t graph;
	37	static FILE *fgraph = NULL;
	38
	39	static size_t node_output_size = 0;
	40
	41	/* Return an unambiguous printable representated, allocated in slot 0,
	42	for NAME, suitable for C strings. */
	43	static char const *
	44	quote (char const *name)
	45	{
	46	return quotearg_n_style (0, escape_quoting_style, name);
	47	}
	48
	49	/* This part will construct the label of nodes. */
	50	static void
	51	print_core (int state, struct obstack *node_obstack)
	52	{
	53	int i;
	54	int k;
	55	int rule;
	56	core *statep;
	57	short *sp;
	58	short *sp1;
	59
	60	statep = state_table[state];
	61	k = statep->nitems;
	62
	63	if (k == 0)
	64	return;
	65
	66	for (i = 0; i < k; i++)
	67	{
	68	if (i)
	69	obstack_sgrow (node_obstack, "\\n");
	70
	71	sp1 = sp = ritem + statep->items[i];
	72
	73	while (*sp > 0)
	74	sp++;
	75
	76	rule = -(*sp);
	77
	78	obstack_fgrow1 (node_obstack, "%d: ", rule);
	79	obstack_fgrow1 (node_obstack, " %s -> ", quote (tags[rlhs[rule]]));
	80
	81	for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
	82	obstack_fgrow1 (node_obstack, "%s ", quote (tags[*sp]));
	83
	84	obstack_1grow (node_obstack, '.');
	85
	86	while (*sp > 0)
	87	obstack_fgrow1 (node_obstack, " %s", quote (tags[*sp++]));
	88	}
	89	}
	90
	91	/* Output in graph_obstack edges specifications in incidence with current
	92	node. */
	93	static void
	94	print_actions (int state, const char node_name, struct obstack node_obstack)
	95	{
	96	int i;
	97	int k;
	98	int state1;
	99	int symbol;
	100	shifts *shiftp;
	101	errs *errp;
	102	reductions *redp;
	103	int rule;
	104	static char buff[10];
	105	edge_t edge;
	106
	107	shiftp = shift_table[state];
	108	redp = reduction_table[state];
	109	errp = err_table[state];
	110
	111	if (!shiftp && !redp)
	112	{
	113	if (final_state == state)
	114	obstack_sgrow (node_obstack, "$default: accept");
	115	else
	116	obstack_sgrow (node_obstack, "NO ACTIONS");
	117	return;
	118	}
	119
	120	if (shiftp)
	121	{
	122	k = shiftp->nshifts;
	123
	124	for (i = 0; i < k; i++)
	125	{
	126	if (!shiftp->shifts[i])
	127	continue;
	128	state1 = shiftp->shifts[i];
	129	symbol = accessing_symbol[state1];
	130
	131	if (ISVAR (symbol))
	132	break;
	133
	134	{
	135	new_edge (&edge);
	136
	137	if (state > state1)
	138	edge.type = back_edge;
	139	open_edge (&edge, fgraph);
	140	/* The edge source is the current node. */
	141	edge.sourcename = node_name;
	142	sprintf (buff, "%d", state1);
	143	edge.targetname = buff;
	144	edge.color = (symbol == 0) ? red : blue;
	145	/* FIXME: Be aware that quote uses static memory. The string
	146	must be output immediately (which is the case here). */
	147	edge.label = tags[symbol] ? quote (tags[symbol]) : NULL;
	148	output_edge (&edge, fgraph);
	149	close_edge (fgraph);
	150	}
	151	}
	152	}
	153	else
	154	{
	155	i = 0;
	156	k = 0;
	157	}
	158
	159	if (errp)
	160	{
	161	int j, nerrs;
	162
	163	nerrs = errp->nerrs;
	164
	165	for (j = 0; j < nerrs; j++)
	166	{
	167	if (!errp->errs[j])
	168	continue;
	169	symbol = errp->errs[j];
	170	/* If something has been added in the NODE_OBSTACK after
	171	the declaration of the label, then we need a `\n'. */
	172	if (obstack_object_size (node_obstack) > node_output_size)
	173	obstack_sgrow (node_obstack, "\\n");
	174	obstack_fgrow1 (node_obstack, _("%-4s\terror (nonassociative)"),
	175	tags[symbol]);
	176	}
	177	if (j > 0)
	178	obstack_sgrow (node_obstack, "\\n");
	179	}
	180
	181	if (consistent[state] && redp)
	182	{
	183	rule = redp->rules[0];
	184	symbol = rlhs[rule];
	185	if (obstack_object_size (node_obstack) > node_output_size)
	186	obstack_sgrow (node_obstack, "\\n");
	187	obstack_fgrow2 (node_obstack, _("$default\treduce using rule %d (%s)"),
	188	rule, tags[symbol]);
	189	}
	190
	191	if (i < k)
	192	{
	193	for (; i < k; i++)
	194	{
	195	if (!shiftp->shifts[i])
	196	continue;
	197	state1 = shiftp->shifts[i];
	198	symbol = accessing_symbol[state1];
	199
	200	new_edge (&edge);
	201	open_edge (&edge, fgraph);
	202	edge.sourcename = node_name;
	203	sprintf (buff, "%d", state1);
	204	edge.targetname = buff;
	205	edge.color = red;
	206	edge.label = tags[symbol] ? quote (tags[symbol]) : NULL;
	207	output_edge (&edge, fgraph);
	208	close_edge (fgraph);
	209	}
	210	}
	211	}
	212
	213	/* Output in GRAPH_OBSTACK the current node specifications and edges
	214	which go out from that node. */
	215	static void
	216	print_state (int state)
	217	{
	218	static char name[10];
	219	struct obstack node_obstack;
	220	node_t node;
	221
	222	obstack_init (&node_obstack);
	223	new_node (&node); /* Set node attributs default value. */
	224	sprintf (name, "%d", state);
	225	node.title = name; /* Give a name to the node. */
	226
	227	{
	228	/* Here we begin to compute the node label. */
	229	obstack_sgrow (&node_obstack, "\t\tlabel:\t\""); /* Open Label */
	230
	231	/* Keep the size of NODE_OBSTACK before computing the label. It is
	232	useful to format the label. */
	233	node_output_size = obstack_object_size (&node_obstack);
	234
	235	/* Compute the labels of nodes on the fly. */
	236	print_core (state, &node_obstack);
	237	/* Compute edges and additionnal parts of node label. */
	238	print_actions (state, node.title, &node_obstack);
	239
	240	obstack_sgrow (&node_obstack, "\"\n"); /* Close Label. */
	241	}
	242
	243	open_node (fgraph);
	244	/* Output a VCG formatted attributs list. */
	245	output_node (&node, fgraph);
	246	/* Save the node label. */
	247	fwrite (obstack_base (&node_obstack),
	248	obstack_object_size (&node_obstack), 1, fgraph);
	249	close_node (fgraph);
	250
	251	obstack_free (&node_obstack, 0);
	252	}
	253	\f
	254
	255	void
	256	print_graph (void)
	257	{
	258	int i;
	259
	260	if (!graph_flag)
	261	return;
	262
	263	/* Output file. */
	264	fgraph = xfopen (spec_graph_file, "w");
	265
	266	new_graph (&graph);
	267
	268	#if 0
	269	graph.smanhattan_edges = yes;
	270	graph.manhattan_edges = yes;
	271	#endif
	272
	273	graph.display_edge_labels = yes;
	274	graph.layoutalgorithm = normal;
	275
	276	graph.port_sharing = no;
	277	graph.finetuning = yes;
	278	graph.straight_phase = yes;
	279	graph.priority_phase = yes;
	280	graph.splines = yes;
	281
	282	graph.crossing_weight = median;
	283
	284	/* Output graph options. */
	285	open_graph (fgraph);
	286	output_graph (&graph, fgraph);
	287
	288	for (i = 0; i < nstates; i++)
	289	/* Output nodes & edges. */
	290	print_state (i);
	291
	292	/* Close graph. */
	293	close_graph (&graph, fgraph);
	294	xfclose (fgraph);
	295	}