src/print_graph.c

   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].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  ->  ",
  80                       quote (tags[rule_table[rule].lhs]));
  81
  82       for (sp = ritem + rule_table[rule].rhs; sp < sp1; sp++)
  83         obstack_fgrow1 (node_obstack, "%s ", quote (tags[*sp]));
  84
  85       obstack_1grow (node_obstack, '.');
  86
  87       while (*sp > 0)
  88         obstack_fgrow1 (node_obstack, " %s", quote (tags[*sp++]));
  89     }
  90 }
  91
  92 /* Output in graph_obstack edges specifications in incidence with current
  93    node.  */
  94 static void
  95 print_actions (int state, const char *node_name, struct obstack *node_obstack)
  96 {
  97   int i;
  98   int k;
  99   int state1;
 100   int symbol;
 101   shifts *shiftp;
 102   errs *errp;
 103   reductions *redp;
 104   int rule;
 105   static char buff[10];
 106   edge_t edge;
 107
 108   shiftp = state_table[state].shift_table;
 109   redp = state_table[state].reduction_table;
 110   errp = err_table[state];
 111
 112   if (!shiftp && !redp)
 113     {
 114       if (final_state == state)
 115         obstack_sgrow (node_obstack, "$default: accept");
 116       else
 117         obstack_sgrow (node_obstack, "NO ACTIONS");
 118       return;
 119     }
 120
 121   if (shiftp)
 122     {
 123       k = shiftp->nshifts;
 124
 125       for (i = 0; i < k; i++)
 126         {
 127           if (!shiftp->shifts[i])
 128             continue;
 129           state1 = shiftp->shifts[i];
 130           symbol = state_table[state1].accessing_symbol;
 131
 132           if (ISVAR (symbol))
 133             break;
 134
 135           {
 136             new_edge (&edge);
 137
 138             if (state > state1)
 139               edge.type = back_edge;
 140             open_edge (&edge, fgraph);
 141             /* The edge source is the current node.  */
 142             edge.sourcename = node_name;
 143             sprintf (buff, "%d", state1);
 144             edge.targetname = buff;
 145             edge.color = (symbol == 0) ? red : blue;
 146             /* FIXME: Be aware that quote uses static memory.  The string
 147                must be output immediately (which is the case here). */
 148             edge.label = tags[symbol] ? quote (tags[symbol]) : NULL;
 149             output_edge (&edge, fgraph);
 150             close_edge (fgraph);
 151           }
 152         }
 153     }
 154   else
 155     {
 156       i = 0;
 157       k = 0;
 158     }
 159
 160   if (errp)
 161     {
 162       int j, nerrs;
 163
 164       nerrs = errp->nerrs;
 165
 166       for (j = 0; j < nerrs; j++)
 167         {
 168           if (!errp->errs[j])
 169             continue;
 170           symbol = errp->errs[j];
 171           /* If something has been added in the NODE_OBSTACK after
 172              the declaration of the label, then we need a `\n'.  */
 173           if (obstack_object_size (node_obstack) > node_output_size)
 174             obstack_sgrow (node_obstack, "\\n");
 175           obstack_fgrow1 (node_obstack, _("%-4s\terror (nonassociative)"),
 176                           tags[symbol]);
 177         }
 178       if (j > 0)
 179         obstack_sgrow (node_obstack, "\\n");
 180     }
 181
 182   if (state_table[state].consistent && redp)
 183     {
 184       rule = redp->rules[0];
 185       symbol = rule_table[rule].lhs;
 186       if (obstack_object_size (node_obstack) > node_output_size)
 187         obstack_sgrow (node_obstack, "\\n");
 188       obstack_fgrow2 (node_obstack, _("$default\treduce using rule %d (%s)"),
 189                       rule, tags[symbol]);
 190     }
 191
 192   if (i < k)
 193     {
 194       for (; i < k; i++)
 195         {
 196           if (!shiftp->shifts[i])
 197             continue;
 198           state1 = shiftp->shifts[i];
 199           symbol = state_table[state1].accessing_symbol;
 200
 201           new_edge (&edge);
 202           open_edge (&edge, fgraph);
 203           edge.sourcename = node_name;
 204           sprintf (buff, "%d", state1);
 205           edge.targetname = buff;
 206           edge.color = red;
 207           edge.label = tags[symbol] ? quote (tags[symbol]) : NULL;
 208           output_edge (&edge, fgraph);
 209           close_edge (fgraph);
 210         }
 211     }
 212 }
 213
 214 /* Output in GRAPH_OBSTACK the current node specifications and edges
 215    which go out from that node.  */
 216 static void
 217 print_state (int state)
 218 {
 219   static char name[10];
 220   struct obstack node_obstack;
 221   node_t node;
 222
 223   obstack_init (&node_obstack);
 224   new_node (&node);     /* Set node attributs default value.  */
 225   sprintf (name, "%d", state);
 226   node.title = name;    /* Give a name to the node.  */
 227
 228   {
 229     /* Here we begin to compute the node label. */
 230     obstack_sgrow (&node_obstack, "\t\tlabel:\t\"");    /* Open Label  */
 231
 232     /* Keep the size of NODE_OBSTACK before computing the label. It is
 233        useful to format the label.  */
 234     node_output_size = obstack_object_size (&node_obstack);
 235
 236     /* Compute the labels of nodes on the fly.  */
 237     print_core (state, &node_obstack);
 238     /* Compute edges and additionnal parts of node label.  */
 239     print_actions (state, node.title, &node_obstack);
 240
 241     obstack_sgrow (&node_obstack, "\"\n");              /* Close Label.  */
 242   }
 243
 244   open_node (fgraph);
 245   /* Output a VCG formatted attributs list.  */
 246   output_node (&node, fgraph);
 247   /* Save the node label.  */
 248   fwrite (obstack_base (&node_obstack),
 249           obstack_object_size (&node_obstack), 1, fgraph);
 250   close_node (fgraph);
 251
 252   obstack_free (&node_obstack, 0);
 253 }
 254 \f
 255
 256 void
 257 print_graph (void)
 258 {
 259   int i;
 260
 261   if (!graph_flag)
 262     return;
 263
 264   /* Output file.  */
 265   fgraph = xfopen (spec_graph_file, "w");
 266
 267   new_graph (&graph);
 268
 269 #if 0
 270   graph.smanhattan_edges = yes;
 271   graph.manhattan_edges = yes;
 272 #endif
 273
 274   graph.display_edge_labels = yes;
 275   graph.layoutalgorithm = normal;
 276
 277   graph.port_sharing = no;
 278   graph.finetuning = yes;
 279   graph.straight_phase = yes;
 280   graph.priority_phase = yes;
 281   graph.splines = yes;
 282
 283   graph.crossing_weight = median;
 284
 285   /* Output graph options. */
 286   open_graph (fgraph);
 287   output_graph (&graph, fgraph);
 288
 289   for (i = 0; i < nstates; i++)
 290     /* Output nodes & edges. */
 291     print_state (i);
 292
 293   /* Close graph. */
 294   close_graph (&graph, fgraph);
 295   xfclose (fgraph);
 296 }