From 83bae26d3f9b374fb189703aa8795ecb3240bab2 Mon Sep 17 00:00:00 2001
From: Theophile Ranquet <ranquet@lrde.epita.fr>
Date: Mon, 8 Oct 2012 06:11:41 +0000
Subject: [PATCH] graphs: show reductions

* src/graphviz.c (output_red): New, show reductions on the graph.
(no_reduce_bitset_init): New, initialize a bitset.
(print_token): New, print a lookahead token.
(escape): New, print "foo" as \"foo\" because Dot doesn't like quotes within
a label.

* src/graphviz.h : Adjust.
* src/print_graph.c (print_actions): Call output_red here.

Signed-off-by: Akim Demaille <akim@lrde.epita.fr>
---
 src/graphviz.c    | 82 +++++++++++++++++++++++++++++++++++++++++++++++
 src/graphviz.h    | 10 +++++-
 src/print_graph.c |  3 ++
 3 files changed, 94 insertions(+), 1 deletion(-)

diff --git a/src/graphviz.c b/src/graphviz.c
index 6498884a..a2baa160 100644
--- a/src/graphviz.c
+++ b/src/graphviz.c
@@ -25,7 +25,9 @@
 #include <quotearg.h>
 
 #include "files.h"
+#include "gram.h"
 #include "graphviz.h"
+#include "tables.h"
 
 /* Return an unambiguous printable representation for NAME, suitable
    for C strings.  Use slot 2 since the user may use slots 0 and 1.  */
@@ -78,6 +80,86 @@ escape (char const *name)
   return q + 1;
 }
 
+static void
+no_reduce_bitset_init (state const *s, bitset *no_reduce_set)
+{
+  int n;
+  *no_reduce_set = bitset_create (ntokens, BITSET_FIXED);
+  bitset_zero (*no_reduce_set);
+  FOR_EACH_SHIFT (s->transitions, n)
+    bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n));
+  for (n = 0; n < s->errs->num; ++n)
+    if (s->errs->symbols[n])
+      bitset_set (*no_reduce_set, s->errs->symbols[n]->number);
+}
+
+static bool
+print_token (struct obstack *out, bool first, char const *tok)
+{
+  char const *q = escape (tok);
+
+  if (! first)
+    obstack_sgrow (out, ",");
+  obstack_sgrow (out, q);
+  return false;
+}
+
+void
+output_red (state const *s, reductions const *reds, FILE *fout)
+{
+  int source = s->number;
+  int i, j;
+  bitset no_reduce_set;
+  no_reduce_bitset_init (s, &no_reduce_set);
+
+  struct obstack oout;
+  obstack_init (&oout);
+
+  for (j = 0; j < reds->num; ++j)
+    {
+      bool first = true;
+      bool disabled = false;
+      int ruleno = reds->rules[j]->user_number;
+      rule *default_reduction = NULL;
+      if (yydefact[s->number] != 0)
+        default_reduction = &rules[yydefact[s->number] - 1];
+
+      /* First, print the edges that represent each possible reduction for
+         the given state. */
+      obstack_printf (&oout, "  %1$d -> \"%1$dR%2$d\" [label=\"",
+                      source, ruleno);
+      if (default_reduction && default_reduction == reds->rules[j])
+        first = print_token (&oout, true, "$default");
+      else
+        for (i = 0; i < ntokens; i++)
+            if (bitset_test (reds->lookahead_tokens[j], i))
+              {
+                first = print_token (&oout, first, symbols[i]->tag);
+                if (bitset_test (no_reduce_set, i))
+                  disabled = true;
+              }
+      obstack_sgrow (&oout, "\" style=solid]\n");
+
+      /* Then, print the reduction's representation. This most be done later
+         because the we need the previously determined boolean to know if this
+         reduction is disabled or not. */
+      obstack_printf (&oout, " \"%dR%d\" "
+                             "[style=filled shape=diamond fillcolor=%s "
+                             "label=\"R%d\"]\n",
+                      source, ruleno,
+                      disabled ? "firebrick1" : "yellowgreen",
+                      ruleno);
+
+      /* If no lookahead tokens were valid transitions, this reduction is
+         actually disabled, so don't print it. */
+      if (first)
+        (void) obstack_finish0 (&oout);
+      else
+        fprintf (fout, obstack_finish0 (&oout));
+    }
+  obstack_free (&oout, 0);
+}
+
 void
 finish_graph (FILE *fout)
 {
diff --git a/src/graphviz.h b/src/graphviz.h
index 62f26fb4..371b15c5 100644
--- a/src/graphviz.h
+++ b/src/graphviz.h
@@ -22,6 +22,8 @@
 #ifndef GRAPHVIZ_H_
 # define GRAPHVIZ_H_
 
+#include "state.h"
+
 /// Begin a Dot graph.
 /// \param fout   output stream.
 void start_graph (FILE *fout);
@@ -40,7 +42,13 @@ void output_node (int id, char const *label, FILE *fout);
 /// \param style        Dot style of the edge (e.g., "dotted" or "solid").
 /// \param fout         output stream.
 void output_edge (int source, int destination, char const *label,
-		  char const *style, FILE *fout);
+                  char const *style, FILE *fout);
+
+/// Output a reduction.
+/// \param s            current state
+/// \param reds         the set of reductions
+/// \param fout         output stream.
+void output_red (state const *s, reductions const *reds, FILE *fout);
 
 /// End a Dot graph.
 /// \param fout  output stream.
diff --git a/src/print_graph.c b/src/print_graph.c
index 2e3fd460..b9021014 100644
--- a/src/print_graph.c
+++ b/src/print_graph.c
@@ -120,6 +120,9 @@ print_actions (state const *s, FILE *fgraph)
 
   transitions const *trans = s->transitions;
 
+  /* Display reductions. */
+  output_red (s, s->reductions, fgraph);
+
   if (!trans->num && !s->reductions)
     return;
 
-- 
2.45.2