cex: display derivations as trees

Sometimes, understanding the derivations is difficult, because they
are serialized to fit in one line.  For instance, the example taken
from the NEWS file:

    %token ID
    %%
    s: a ID
    a: expr
    expr: expr ID ',' | "expr"

gave

    First example        expr • ID ',' ID $end
    Shift derivation     $accept → [ s → [ a → [ expr → [ expr • ID ',' ] ] ID ] $end ]
    Second example       expr • ID $end
    Reduce derivation    $accept → [ s → [ a → [ expr • ] ID ] $end ]

Printing as trees, it gives:

    First example        expr • ID ',' ID $end
    Shift derivation
      $accept
      ↳ s                      $end
        ↳ a                 ID
          ↳ expr
            ↳ expr • ID ','
    Second example       expr • ID $end
    Reduce derivation
      $accept
      ↳ s             $end
        ↳ a        ID
          ↳ expr •

* src/glyphs.h, src/glyphs.c (down_arrow, empty, derivation_separator):
New.
* src/derivation.c (derivation_print, derivation_print_impl): Rename
as...
(derivation_print_flat, derivation_print_flat_impl): These.
(fputs_if, derivation_depth, derivation_width, derivation_print_tree)
(derivation_print_tree_impl, derivation_print): New.
* src/counterexample.c (print_counterexample): Adjust.
* tests/conflicts.at, tests/counterexample.at, tests/diagnostics.at,
* tests/report.at: Adjust.

1 files changed, 448 insertions, 4 deletions

diff --git a/tests/counterexample.at b/tests/counterexample.at
index 17006c31..2b85d061 100644
--- a/tests/counterexample.at
+++ b/tests/counterexample.at
@@ -17,14 +17,23 @@
 
 AT_BANNER([[Counterexamples.]])
 
-# AT_BISON_CHECK_CEX(EXPERR)
-# --------------------------
+# AT_BISON_CHECK_CEX(TREE, FLAT)
+# ------------------------------
 m4_define([AT_BISON_CHECK_CEX],
 [AT_KEYWORDS([cex])
-AT_DATA([expout], [$1])
+
+AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
+# FIXME: Avoid trailing white spaces.
+AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g;s/ *$//;' stderr]],
+         [], [$1])
+
+m4_pushdef([AT_SET_ENV_IF],
+           [[YYFLAT=1; export YYFLAT;]]m4_defn([AT_SET_ENV_IF]))
 AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
 AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g' stderr]],
-         [], [expout])
+         [], [$2])
+m4_popdef([AT_SET_ENV_IF])
+
 ])
 
 ## --------------------- ##
@@ -47,6 +56,20 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token B:
   Example              A . B C
+  Shift derivation
+    s
+    `-> y         c
+        `-> A . B `-> C
+  Reduce derivation
+    s
+    `-> a       x
+        `-> A . `-> B C
+
+input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+  Example              A . B C
   Shift derivation     s -> [ y -> [ A . B ] c -> [ C ] ]
   Reduce derivation    s -> [ a -> [ A . ] x -> [ B C ] ]
 
@@ -75,6 +98,38 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token B:
   Example              A . B C
+  Shift derivation
+    s
+    `-> ac
+        `-> A ac          C
+              `-> b
+                  `-> . B
+  Reduce derivation
+    s
+    `-> a       bc
+        `-> A . `-> B C
+
+Shift/reduce conflict on token B:
+  Example              A A . B B C C
+  Shift derivation
+    s
+    `-> ac
+        `-> A ac                        C
+              `-> A ac                C
+                    `-> b
+                        `-> . b
+                              `-> B B
+  Reduce derivation
+    s
+    `-> a             bc
+        `-> A a       `-> B bc      C
+              `-> A .       `-> B C
+
+input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+  Example              A . B C
   Shift derivation     s -> [ ac -> [ A ac -> [ b -> [ . B ] ] C ] ]
   Reduce derivation    s -> [ a -> [ A . ] bc -> [ B C ] ]
 
@@ -109,6 +164,38 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 Shift/reduce conflict on token B:
   Example              A . B
+  Shift derivation
+    s
+    `-> A xby
+          `-> . B
+  Reduce derivation
+    s
+    `-> ax          by
+        `-> A x     `-> B y
+              `-> .       `-> %empty
+
+Shift/reduce conflict on token B:
+  First example        A X . B Y $end
+  Shift derivation
+    $accept
+    `-> s                     $end
+        `-> A xby
+              `-> X xby     Y
+                    `-> . B
+  Second example       A X . B y $end
+  Reduce derivation
+    $accept
+    `-> s                             $end
+        `-> ax                by
+            `-> A x           `-> B y
+                  `-> X x
+                        `-> .
+
+input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+  Example              A . B
   Shift derivation     s -> [ A xby -> [ . B ] ]
   Reduce derivation    s -> [ ax -> [ A x -> [ . ] ] by -> [ B y -> [ ] ] ]
 
@@ -144,6 +231,25 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token C:
   First example        B . C $end
+  Shift derivation
+    $accept
+    `-> g                 $end
+        `-> x
+            `-> bc
+                `-> B . C
+  Second example       B . C D $end
+  Reduce derivation
+    $accept
+    `-> g                       $end
+        `-> x
+            `-> b       cd
+                `-> B . `-> C D
+
+input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token C:
+  First example        B . C $end
   Shift derivation     $accept -> [ g -> [ x -> [ bc -> [ B . C ] ] ] $end ]
   Second example       B . C D $end
   Reduce derivation    $accept -> [ g -> [ x -> [ b -> [ B . ] cd -> [ C D ] ] ] $end ]
@@ -172,6 +278,25 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token A:
   First example        A . A B $end
+  Shift derivation
+    $accept
+    `-> s                   $end
+        `-> t
+            `-> y
+                `-> A . A B
+  Second example       A . A $end
+  Reduce derivation
+    $accept
+    `-> s                             $end
+        `-> s               t
+            `-> t           `-> x
+                `-> x           `-> A
+                    `-> A .
+
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token A:
+  First example        A . A B $end
   Shift derivation     $accept -> [ s -> [ t -> [ y -> [ A . A B ] ] ] $end ]
   Second example       A . A $end
   Reduce derivation    $accept -> [ s -> [ s -> [ t -> [ x -> [ A . ] ] ] t -> [ x -> [ A ] ] ] $end ]
@@ -204,6 +329,36 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 Shift/reduce conflict on token A:
   Example              b . A X X Y
+  Shift derivation
+    a
+    `-> s
+        `-> b . xx        y
+                `-> A X X `-> Y
+  Reduce derivation
+    a
+    `-> r       t
+        `-> b . `-> A x     xy
+                      `-> X `-> X Y
+
+Shift/reduce conflict on token X:
+  First example        A X . X
+  Shift derivation
+    a
+    `-> t
+        `-> A xx
+              `-> X . X
+  Second example       X . X xy
+  Reduce derivation
+    a
+    `-> x       t
+        `-> X . `-> X xy
+
+input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
+input.y:8.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
+Shift/reduce conflict on token A:
+  Example              b . A X X Y
   Shift derivation     a -> [ s -> [ b . xx -> [ A X X ] y -> [ Y ] ] ]
   Reduce derivation    a -> [ r -> [ b . ] t -> [ A x -> [ X ] xy -> [ X Y ] ] ]
 
@@ -236,6 +391,19 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
 Reduce/reduce conflict on token $end:
   Example              A b .
+  First derivation
+    a
+    `-> A b .
+  Second derivation
+    a
+    `-> A b
+          `-> b .
+
+input.y:4.9: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
+Reduce/reduce conflict on token $end:
+  Example              A b .
   First derivation     a -> [ A b . ]
   Second derivation    a -> [ A b -> [ b . ] ]
 
@@ -262,6 +430,23 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
 Reduce/reduce conflict on tokens A, C:
   First example        D . A $end
+  First derivation
+    $accept
+    `-> s             $end
+        `-> a       A
+            `-> D .
+  Second example       B D . A $end
+  Second derivation
+    $accept
+    `-> s               $end
+        `-> B b       A
+              `-> D .
+
+input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
+Reduce/reduce conflict on tokens A, C:
+  First example        D . A $end
   First derivation     $accept -> [ s -> [ a -> [ D . ] A ] $end ]
   Second example       B D . A $end
   Second derivation    $accept -> [ s -> [ B b -> [ D . ] A ] $end ]
@@ -290,6 +475,24 @@ AT_BISON_CHECK_CEX(
 Shift/reduce conflict on token J:
 time limit exceeded: XXX
   First example        H i . J K $end
+  Shift derivation
+    $accept
+    `-> a                 $end
+        `-> H i
+              `-> i . J K
+  Second example       H i . J $end
+  Reduce derivation
+    $accept
+    `-> s               $end
+        `-> a         J
+            `-> H i .
+
+input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token J:
+time limit exceeded: XXX
+  First example        H i . J K $end
   Shift derivation     $accept -> [ a -> [ H i -> [ i . J K ] ] $end ]
   Second example       H i . J $end
   Reduce derivation    $accept -> [ s -> [ a -> [ H i . ] J ] $end ]
@@ -321,6 +524,37 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token B:
   Example              N A . B C
+  Shift derivation
+    s
+    `-> n
+        `-> N b
+              `-> A . B C
+  Reduce derivation
+    s
+    `-> n               C
+        `-> N a       B
+              `-> A .
+
+Shift/reduce conflict on token B:
+  Example              N N A . B D C
+  Shift derivation
+    s
+    `-> n
+        `-> N n                 C
+              `-> N b
+                    `-> A . B D
+  Reduce derivation
+    s
+    `-> n                       C
+        `-> N n               D
+              `-> N a       B
+                    `-> A .
+
+input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+  Example              N A . B C
   Shift derivation     s -> [ n -> [ N b -> [ A . B C ] ] ]
   Reduce derivation    s -> [ n -> [ N a -> [ A . ] B ] C ]
 
@@ -357,6 +591,38 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
 Reduce/reduce conflict on tokens b, c:
   Example              B . b c
+  First derivation
+    S
+    `-> B                        C
+        `-> A       b A          `-> A          c A
+            `-> B .   `-> %empty     `-> %empty   `-> %empty
+  Second derivation
+    S
+    `-> B C
+          `-> A                          c A
+              `-> B                        `-> %empty
+                  `-> A     b A
+                      `-> .   `-> %empty
+
+Reduce/reduce conflict on tokens b, c:
+  Example              C . c b
+  First derivation
+    S
+    `-> C                        B
+        `-> A       c A          `-> A          b A
+            `-> C .   `-> %empty     `-> %empty   `-> %empty
+  Second derivation
+    S
+    `-> C B
+          `-> A                          b A
+              `-> C                        `-> %empty
+                  `-> A     c A
+                      `-> .   `-> %empty
+
+]],
+[[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
+Reduce/reduce conflict on tokens b, c:
+  Example              B . b c
   First derivation     S -> [ B -> [ A -> [ B . ] b A -> [ ] ] C -> [ A -> [ ] c A -> [ ] ] ]
   Second derivation    S -> [ B C -> [ A -> [ B -> [ A -> [ . ] b A -> [ ] ] ] c A -> [ ] ] ]
 
@@ -389,6 +655,136 @@ AT_BISON_CHECK_CEX(
 input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
 Reduce/reduce conflict on token A:
   First example        . c A A $end
+  First derivation
+    $accept
+    `-> a                   $end
+        `-> b     d
+            `-> . `-> c A A
+  Second example       . c A A $end
+  Second derivation
+    $accept
+    `-> a                   $end
+        `-> c     d
+            `-> . `-> c A A
+
+Reduce/reduce conflict on token A:
+time limit exceeded: XXX
+  First example        b . c A A $end
+  First derivation
+    $accept
+    `-> a                             $end
+        `-> b d
+              `-> a
+                  `-> b     d
+                      `-> . `-> c A A
+  Second example       b . A $end
+  Second derivation
+    $accept
+    `-> a                 $end
+        `-> b d
+              `-> c     A
+                  `-> .
+
+Reduce/reduce conflict on token A:
+time limit exceeded: XXX
+  First example        c . c A A $end
+  First derivation
+    $accept
+    `-> a                             $end
+        `-> c d
+              `-> a
+                  `-> b     d
+                      `-> . `-> c A A
+  Second example       c . A $end
+  Second derivation
+    $accept
+    `-> a                 $end
+        `-> c d
+              `-> c     A
+                  `-> .
+
+Shift/reduce conflict on token A:
+time limit exceeded: XXX
+  First example        b c . A
+  Shift derivation
+    a
+    `-> b d
+          `-> c . A
+  Second example       b c . c A A $end
+  Reduce derivation
+    $accept
+    `-> a                                       $end
+        `-> b d
+              `-> a
+                  `-> c d
+                        `-> a
+                            `-> b     d
+                                `-> . `-> c A A
+
+Reduce/reduce conflict on token A:
+  First example        b c . c A A $end
+  First derivation
+    $accept
+    `-> a                                       $end
+        `-> b d
+              `-> a
+                  `-> c d
+                        `-> a
+                            `-> b     d
+                                `-> . `-> c A A
+  Second example       b c . A $end
+  Second derivation
+    $accept
+    `-> a                           $end
+        `-> b d
+              `-> a
+                  `-> c d
+                        `-> c     A
+                            `-> .
+
+Shift/reduce conflict on token A:
+  First example        b c . A
+  Shift derivation
+    a
+    `-> b d
+          `-> c . A
+  Second example       b c . A $end
+  Reduce derivation
+    $accept
+    `-> a                           $end
+        `-> b d
+              `-> a
+                  `-> c d
+                        `-> c     A
+                            `-> .
+
+Reduce/reduce conflict on token $end:
+  Example              b d .
+  First derivation
+    a
+    `-> b d .
+  Second derivation
+    a
+    `-> b d
+          `-> d .
+
+Reduce/reduce conflict on token $end:
+  Example              c d .
+  First derivation
+    a
+    `-> c d .
+  Second derivation
+    a
+    `-> c d
+          `-> d .
+
+input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
+input.y:6.15: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
+Reduce/reduce conflict on token A:
+  First example        . c A A $end
   First derivation     $accept -> [ a -> [ b -> [ . ] d -> [ c A A ] ] $end ]
   Second example       . c A A $end
   Second derivation    $accept -> [ a -> [ c -> [ . ] d -> [ c A A ] ] $end ]
@@ -463,6 +859,21 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token J:
   Example              H i J . J J
+  Shift derivation
+    s
+    `-> a             J
+        `-> H i J . J
+  Reduce derivation
+    s
+    `-> a
+        `-> H i         J J
+              `-> i J .
+
+input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token J:
+  Example              H i J . J J
   Shift derivation     s -> [ a -> [ H i J . J ] J ]
   Reduce derivation    s -> [ a -> [ H i -> [ i J . ] J J ] ]
 
@@ -494,6 +905,21 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token D:
   Example              A a . D
+  Shift derivation
+    s
+    `-> A a d
+            `-> . D
+  Reduce derivation
+    s
+    `-> A a a             d
+            `-> b         `-> D
+                `-> c
+                    `-> .
+
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token D:
+  Example              A a . D
   Shift derivation     s -> [ A a d -> [ . D ] ]
   Reduce derivation    s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] ]
 
@@ -523,6 +949,24 @@ AT_BISON_CHECK_CEX(
 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 Shift/reduce conflict on token D:
   First example        A a . D $end
+  Shift derivation
+    $accept
+    `-> s               $end
+        `-> A a d
+                `-> . D
+  Second example       A a . D E $end
+  Reduce derivation
+    $accept
+    `-> s                             $end
+        `-> A a a             d     E
+                `-> b         `-> D
+                    `-> c
+                        `-> .
+
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token D:
+  First example        A a . D $end
   Shift derivation     $accept -> [ s -> [ A a d -> [ . D ] ] $end ]
   Second example       A a . D E $end
   Reduce derivation    $accept -> [ s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] E ] $end ]