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 "xalloc.h"
  23 #include "files.h"
  24 #include "gram.h"
  25 #include "LR0.h"
  26 #include "lalr.h"
  27 #include "conflicts.h"
  28 #include "complain.h"
  29 #include "getargs.h"
  30 #include "state.h"
  31 #include "reader.h"
  32 #include "obstack.h"
  33 #include "print_graph.h"
  34 #include "vcg.h"
  35 #include "quotearg.h"
  36
  37 static graph_t graph;
  38
  39 static unsigned 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, &graph_obstack);
 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, &graph_obstack);
 149             close_edge (&graph_obstack);
 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, &graph_obstack);
 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, &graph_obstack);
 208           close_edge (&graph_obstack);
 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   open_node (&node_obstack);
 227   /* Output a VCG formatted attributs list.  */
 228   output_node (&node, &node_obstack);
 229
 230   {
 231     /* Here we begin to compute the node label. */
 232     obstack_sgrow (&node_obstack, "\t\tlabel:\t\"");    /* Open Label  */
 233
 234     /* Keep the size of NODE_OBSTACK before computing the label. It is
 235        useful to format the label.  */
 236     node_output_size = obstack_object_size (&node_obstack);
 237
 238     /* Compute the labels of nodes on the fly.  */
 239     print_core (state, &node_obstack);
 240     /* Compute edges and additionnal parts of node label.  */
 241     print_actions (state, node.title, &node_obstack);
 242
 243     obstack_sgrow (&node_obstack, "\"\n");              /* Close Label.  */
 244
 245     close_node (&node_obstack);
 246   }
 247
 248   /* `obstack_cat' NODE_OBSTACK to GRAPH_OBSTACK.  */
 249   obstack_grow (&graph_obstack,
 250                 obstack_base (&node_obstack),
 251                 obstack_object_size (&node_obstack));
 252   obstack_finish (&node_obstack);
 253 }
 254 \f
 255
 256 void
 257 print_graph (void)
 258 {
 259   int i;
 260
 261   if (!graph_flag)
 262     return;
 263   new_graph (&graph);
 264
 265 #if 0
 266   graph.smanhattan_edges = yes;
 267   graph.manhattan_edges = yes;
 268 #endif
 269
 270   graph.display_edge_labels = yes;
 271   graph.layoutalgorithm = 0;
 272
 273   graph.port_sharing = no;
 274   graph.finetuning = yes;
 275   graph.straight_phase = yes;
 276   graph.priority_phase = yes;
 277   graph.splines = yes;
 278
 279   graph.crossing_weight = median;
 280
 281   /* Output graph options. */
 282   open_graph (&graph_obstack);
 283   output_graph (&graph, &graph_obstack);
 284
 285   for (i = 0; i < nstates; i++)
 286     /* Output nodes & edges. */
 287     print_state (i);
 288
 289   /* Close graph. */
 290   close_graph (&graph, &graph_obstack);
 291 }