Subject: bug#18707: [PATCH] dfa: print detail of DFA states in a debug mode

From: Jim Meyering <[email-masked]>
Date: Sun, 19 Jul 2015 14:59:41 -0700

On Mon, Nov 24, 2014 at 4:26 PM, Norihiro Tanaka <[email-masked]> wrote:
> On Mon, 13 Oct 2014 19:39:21 +0900
> Norihiro Tanaka <[email-masked]> wrote:
>> If compile grep with -DDEBUG option, it outputs tokens etc.  In addition
>> to them, DFA states and transitions are output by this patch.  Debugging
>> them, the patch will be very useful.
>>
>> BTW, the patch doesn't make any changes without -DDEBUG option.
>
> I fixed some warnings output in compilation, and rebased it.

Thank you for your patience.
I applied this, changed many %zd to %zu (to ensure compilation
succeeded with -DDEBUG also when configured with
--enable-gcc-warnings) and adjusted the commit log entry. Will push
once you've ACK'd the result.
From 8f675e7c026ce56a8ef0cc33dc5fcd37f49f38a2 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sat, 22 Mar 2014 17:00:36 +0900
Subject: [PATCH] dfa: DEBUG: print detail of DFA states

When compiled with -DDEBUG, grep outputs tokens etc.
With this change, also print DFA states and transitions.
This change is very useful when debugging those.

* src/dfa.c (prtok) [DEBUG]: Change `%c' to `%02x' in printf format.
(state_index) [DEBUG]: Print detail of new state.
(dfastate) [DEBUG]: Print detail of DFA states.
Reported as http://debbugs.gnu.org/18707
---
 src/dfa.c | 86 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 78 insertions(+), 8 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index f9b3da9..b5ca825 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -509,8 +509,8 @@ prtok (token t)
     fprintf (stderr, "END");
   else if (t < NOTCHAR)
     {
-      int ch = t;
-      fprintf (stderr, "%c", ch);
+      unsigned int ch = t;
+      fprintf (stderr, "0x%02x", ch);
     }
   else
     {
@@ -2139,6 +2139,28 @@ state_index (struct dfa *d, position_set const *s, int context)
         return i;
     }

+#ifdef DEBUG
+  fprintf (stderr, "new state %zd\n nextpos:", i);
+  for (j = 0; j < s->nelem; ++j)
+    {
+      fprintf (stderr, " %zu:", s->elems[j].index);
+      prtok (d->tokens[s->elems[j].index]);
+    }
+  fprintf (stderr, "\n context:");
+  if (context ^ CTX_ANY)
+    {
+      if (context & CTX_NONE)
+        fprintf (stderr, " CTX_NONE");
+      if (context & CTX_LETTER)
+        fprintf (stderr, " CTX_LETTER");
+      if (context & CTX_NEWLINE)
+        fprintf (stderr, " CTX_NEWLINE");
+    }
+  else
+    fprintf (stderr, " CTX_ANY");
+  fprintf (stderr, "\n");
+#endif
+
   /* We'll have to create a new state.  */
   d->states = maybe_realloc (d->states, d->sindex, &d->salloc,
                              sizeof *d->states);
@@ -2369,7 +2391,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   fprintf (stderr, "dfaanalyze:\n");
   for (i = 0; i < d->tindex; ++i)
     {
-      fprintf (stderr, " %zd:", i);
+      fprintf (stderr, " %zu:", i);
       prtok (d->tokens[i]);
     }
   putc ('\n', stderr);
@@ -2483,7 +2505,7 @@ dfaanalyze (struct dfa *d, int searchflag)
         }
 #ifdef DEBUG
       /* ... balance the above nonsyntactic #ifdef goo...  */
-      fprintf (stderr, "node %zd:", i);
+      fprintf (stderr, "node %zu:", i);
       prtok (d->tokens[i]);
       putc ('\n', stderr);
       fprintf (stderr,
@@ -2491,13 +2513,13 @@ dfaanalyze (struct dfa *d, int searchflag)
       fprintf (stderr, " firstpos:");
       for (j = stk[-1].nfirstpos; j-- > 0;)
         {
-          fprintf (stderr, " %zd:", firstpos[j].index);
+          fprintf (stderr, " %zu:", firstpos[j].index);
           prtok (d->tokens[firstpos[j].index]);
         }
       fprintf (stderr, "\n lastpos:");
       for (j = stk[-1].nlastpos; j-- > 0;)
         {
-          fprintf (stderr, " %zd:", lastpos[j].index);
+          fprintf (stderr, " %zu:", lastpos[j].index);
           prtok (d->tokens[lastpos[j].index]);
         }
       putc ('\n', stderr);
@@ -2512,12 +2534,12 @@ dfaanalyze (struct dfa *d, int searchflag)
         || d->tokens[i] >= CSET)
       {
 #ifdef DEBUG
-        fprintf (stderr, "follows(%zd:", i);
+        fprintf (stderr, "follows(%zu:", i);
         prtok (d->tokens[i]);
         fprintf (stderr, "):");
         for (j = d->follows[i].nelem; j-- > 0;)
           {
-            fprintf (stderr, " %zd:", d->follows[i].elems[j].index);
+            fprintf (stderr, " %zu:", d->follows[i].elems[j].index);
             prtok (d->tokens[d->follows[i].elems[j].index]);
           }
         putc ('\n', stderr);
@@ -2607,6 +2629,10 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
   bool next_isnt_1st_byte = false; /* We can't add state0.  */
   size_t i, j, k;

+#ifdef DEBUG
+  fprintf (stderr, "build state %td\n", s);
+#endif
+
   zeroset (matches);

   for (i = 0; i < d->states[s].elems.nelem; ++i)
@@ -2658,6 +2684,16 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
             continue;
         }

+#ifdef DEBUG
+      fprintf (stderr, " nextpos %zu:", pos.index);
+      prtok (d->tokens[pos.index]);
+      fprintf (stderr, " of");
+      for (j = 0; j < NOTCHAR; j++)
+      if (tstbit (j,  matches))
+        fprintf (stderr, " 0x%02zx", j);
+      fprintf (stderr, "\n");
+#endif
+
       for (j = 0; j < ngrps; ++j)
         {
           /* If matches contains a single character only, and the current
@@ -2818,6 +2854,29 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
       else
         state_letter = state;

+#ifdef DEBUG
+      fprintf (stderr, "group %zu\n nextpos:", i);
+      for (j = 0; j < grps[i].nelem; ++j)
+        {
+          fprintf (stderr, " %zu:", grps[i].elems[j]);
+          prtok (d->tokens[grps[i].elems[j]]);
+        }
+      fprintf (stderr, "\n follows:");
+      for (j = 0; j < follows.nelem; ++j)
+        {
+          fprintf (stderr, " %zu:", follows.elems[j].index);
+          prtok (d->tokens[follows.elems[j].index]);
+        }
+      fprintf (stderr, "\n states:");
+      if (possible_contexts & CTX_NEWLINE)
+        fprintf (stderr, " CTX_NEWLINE:%td", state_newline);
+      if (possible_contexts & CTX_LETTER)
+        fprintf (stderr, " CTX_LETTER:%td", state_letter);
+      if (possible_contexts & CTX_NONE)
+        fprintf (stderr, " CTX_NONE:%td", state);
+      fprintf (stderr, "\n");
+#endif
+
       /* Set the transitions for each character in the current label.  */
       for (j = 0; j < CHARCLASS_WORDS; ++j)
         for (k = 0; k < CHARCLASS_WORD_BITS; ++k)
@@ -2834,6 +2893,17 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
             }
     }

+#ifdef DEBUG
+  fprintf (stderr, "trans table %td", s);
+  for (i = 0; i < NOTCHAR; ++i)
+    {
+      if (!(i & 0xf))
+        fprintf (stderr, "\n");
+      fprintf (stderr, " %2td", trans[i]);
+    }
+  fprintf (stderr, "\n");
+#endif
+
   for (i = 0; i < ngrps; ++i)
     free (grps[i].elems);
   free (follows.elems);
-- 
2.3.7