src/derivation.c

   1 /* Counterexample derivation trees
   2
   3    Copyright (C) 2020-2021 Free Software Foundation, Inc.
   4
   5    This file is part of Bison, the GNU Compiler Compiler.
   6
   7    This program is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  19
  20 #include <config.h>
  21
  22 #include "derivation.h"
  23 #include "glyphs.h"
  24
  25 #include <c-ctype.h>
  26 #include <gl_linked_list.h>
  27 #include <mbswidth.h>
  28 #include <vasnprintf.h>
  29
  30 #include "system.h"
  31 #include "complain.h"
  32
  33 struct derivation
  34 {
  35   symbol_number sym;
  36   derivation_list children;
  37   int reference_count;
  38   // The rule SYM -> CHILDREN.
  39   const rule *rule;
  40   // Color assigned for styling.  Guarantees that the derivation is
  41   // always displayed with the same color, independently of the order
  42   // in which the derivations are traversed.
  43   int color;
  44 };
  45
  46 static derivation d_dot = { -1, NULL, -1, NULL, -1 };
  47
  48 derivation *
  49 derivation_dot (void)
  50 {
  51   return &d_dot;
  52 }
  53
  54 void
  55 derivation_list_append (derivation_list dl, derivation *d)
  56 {
  57   derivation_retain (d);
  58   gl_list_add_last (dl, d);
  59 }
  60
  61 void
  62 derivation_list_prepend (derivation_list dl, derivation *d)
  63 {
  64   derivation_retain (d);
  65   gl_list_add_first (dl, d);
  66 }
  67
  68 void derivation_list_free (derivation_list dl)
  69 {
  70   derivation *d = NULL;
  71   for (gl_list_iterator_t it = gl_list_iterator (dl);
  72        derivation_list_next (&it, &d);
  73        )
  74     if (d != &d_dot)
  75       derivation_free (d);
  76   gl_list_free (dl);
  77 }
  78
  79 derivation *
  80 derivation_new (symbol_number sym, derivation_list children,
  81                 const rule *r)
  82 {
  83   derivation *res = xmalloc (sizeof *res);
  84   res->sym = sym;
  85   res->children = children;
  86   res->reference_count = 0;
  87   res->rule = r;
  88   res->color = -1;
  89   return res;
  90 }
  91
  92 void
  93 derivation_retain (derivation *d)
  94 {
  95   ++d->reference_count;
  96 }
  97
  98 void
  99 derivation_free (derivation *d)
 100 {
 101   if (!d)
 102     return;
 103   derivation_list free_queue =
 104     gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true,
 105                     1, (const void **)&d);
 106   while (gl_list_size (free_queue) > 0)
 107     {
 108       derivation *deriv = (derivation *) gl_list_get_at (free_queue, 0);
 109       if (--deriv->reference_count == 0)
 110         {
 111           if (deriv->children)
 112             {
 113               derivation *child = NULL;
 114               for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
 115                    derivation_list_next (&it, &child);
 116                    )
 117                 if (child != &d_dot)
 118                   gl_list_add_last (free_queue, child);
 119               gl_list_free (deriv->children);
 120             }
 121           free (deriv);
 122         }
 123       gl_list_remove_at (free_queue, 0);
 124     }
 125   gl_list_free (free_queue);
 126 }
 127
 128 size_t
 129 derivation_size (const derivation *deriv)
 130 {
 131   if (!deriv->children)
 132     return 1;
 133   int size = 1;
 134   derivation *child = NULL;
 135   for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
 136        derivation_list_next (&it, &child);
 137        )
 138     size += derivation_size (child);
 139   return size;
 140 }
 141
 142
 143 // Longest distance from root to leaf.
 144 static int
 145 derivation_depth (const derivation *deriv)
 146 {
 147   if (deriv->children)
 148     {
 149       // Children's depth cannot be 0, even if there are no children
 150       // (the case of a derivation with an empty RHS).
 151       int res = 1;
 152       derivation *child;
 153       for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
 154            derivation_list_next (&it, &child);
 155            )
 156         res = max_int (res, derivation_depth (child));
 157       return res + 1;
 158     }
 159   else
 160     return 1;
 161 }
 162
 163 static bool
 164 all_spaces (const char *s)
 165 {
 166   while (c_isspace (*s))
 167     s++;
 168   return *s == '\0';
 169 }
 170
 171 // Printing the derivation as trees without trailing spaces is
 172 // painful: we cannot simply pad one "column" before moving to the
 173 // next:
 174 //
 175 // exp
 176 // ↳ x1          e1  foo1                      x1
 177 //   ↳ x2        ↳ ε ↳ foo2                    ↳ x2
 178 //     ↳ x3            ↳ foo3                    ↳ x3
 179 //       ↳ "X" •         ↳ x1        foo4          ↳ "X"
 180 //                         ↳ x2      ↳ "quuux"
 181 //                           ↳ x3
 182 //                             ↳ "X"
 183 //
 184 // It's hard for a column to know that it's "last" to decide whether
 185 // to output the right-padding or not.  So when we need to pad on the
 186 // right to complete a column, we don't output the spaces, we
 187 // accumulate the width of padding in *PADDING.
 188 //
 189 // Each time we actually print something (non space), we flush that
 190 // padding.  When we _don't_ print something, its width is added to
 191 // the current padding.
 192 //
 193 // This function implements this.
 194 //
 195 // When COND is true, put S on OUT, preceded by *PADDING white spaces.
 196 // Otherwise add the width to *PADDING.  Return the width of S.
 197 static int
 198 fputs_if (bool cond, FILE *out, int *padding, const char *s)
 199 {
 200   int res = mbswidth (s, 0);
 201   if (cond && !all_spaces (s))
 202     {
 203       fprintf (out, "%*s%s", *padding, "", s);
 204       *padding = 0;
 205     }
 206   else
 207     {
 208       *padding += res;
 209     }
 210   return res;
 211 }
 212
 213 static int
 214 fprintf_if (bool cond, FILE *out, int *padding, const char *fmt, ...)
 215 {
 216   char buf[256];
 217   size_t len = sizeof (buf);
 218   va_list args;
 219   va_start (args, fmt);
 220   char *cp = vasnprintf (buf, &len, fmt, args);
 221   va_end (args);
 222   if (!cp)
 223     xalloc_die ();
 224   int res = fputs_if (cond, out, padding, cp);
 225   if (cp != buf)
 226     free (cp);
 227   return res;
 228 }
 229
 230 // The width taken to report this derivation recursively down to its
 231 // leaves.
 232 static int
 233 derivation_width (const derivation *deriv)
 234 {
 235   if (deriv->children)
 236     {
 237       const symbol *sym = symbols[deriv->sym];
 238       int self_width = mbswidth (sym->tag, 0);
 239
 240       // Arrow and space.
 241       int children_width = down_arrow_width;
 242       children_width += snprintf (NULL, 0, "%d: ", deriv->rule->number);
 243       if (gl_list_size (deriv->children) == 0)
 244         // Empty rhs.
 245         children_width += empty_width;
 246       else
 247         {
 248           if (gl_list_size (deriv->children) == 1
 249               && gl_list_get_first (deriv->children) == &d_dot)
 250             {
 251               children_width += empty_width;
 252               children_width += derivation_separator_width;
 253             }
 254
 255           derivation *child;
 256           for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
 257                derivation_list_next (&it, &child);
 258                )
 259             children_width
 260               += derivation_separator_width + derivation_width (child);
 261           // No separator at the beginning.
 262           children_width -= derivation_separator_width;
 263         }
 264       return max_int (self_width, children_width);
 265     }
 266   else if (deriv == &d_dot)
 267     {
 268       return dot_width;
 269     }
 270   else // leaf.
 271     {
 272       const symbol *sym = symbols[deriv->sym];
 273       return mbswidth (sym->tag, 0);
 274     }
 275 }
 276
 277
 278 // Print DERIV for DEPTH.
 279 //
 280 // The tree is printed from top to bottom with DEPTH ranging from 0 to
 281 // the total depth of the tree.  DERIV should only printed when we
 282 // reach its depth, i.e., then DEPTH is 0.
 283 //
 284 // When DEPTH is 1 and we're on a subderivation, then we print the RHS
 285 // of the derivation (in DEPTH 0 we printed its LHS).
 286 //
 287 // Return the "logical printed" width.  We might have not have reached
 288 // that width, in which case the missing spaces are in *PADDING.
 289 static int
 290 derivation_print_tree_impl (const derivation *deriv, FILE *out,
 291                             int depth, int *padding)
 292 {
 293   const int width = derivation_width (deriv);
 294
 295   int res = 0;
 296   if (deriv->children)
 297     {
 298       const symbol *sym = symbols[deriv->sym];
 299       char style[20];
 300       snprintf (style, 20, "cex-%d", deriv->color);
 301
 302       if (depth == 0 || depth == 1)
 303         {
 304           begin_use_class (style, out);
 305           begin_use_class ("cex-step", out);
 306         }
 307       if (depth == 0)
 308         {
 309           res += fputs_if (true, out, padding, sym->tag);
 310         }
 311       else
 312         {
 313           res += fputs_if (depth == 1, out, padding, down_arrow);
 314           res += fprintf_if (depth == 1, out, padding, "%d: ", deriv->rule->number);
 315           if (gl_list_size (deriv->children) == 0)
 316             // Empty rhs.
 317             res += fputs_if (depth == 1, out, padding, empty);
 318           else
 319             {
 320               if (gl_list_size (deriv->children) == 1
 321                   && gl_list_get_first (deriv->children) == &d_dot)
 322                 {
 323                   res += fputs_if (depth == 1, out, padding, empty);
 324                   res += fputs_if (depth == 1, out, padding, derivation_separator);
 325                 }
 326
 327               bool first = true;
 328               derivation *child;
 329               for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
 330                    derivation_list_next (&it, &child);
 331                    )
 332                 {
 333                   if (!first)
 334                     res += fputs_if (depth == 1, out, padding, derivation_separator);
 335                   res += derivation_print_tree_impl (child, out, depth - 1, padding);
 336                   first = false;
 337                 }
 338             }
 339         }
 340       if (depth == 0 || depth == 1)
 341         {
 342           end_use_class ("cex-step", out);
 343           end_use_class (style, out);
 344         }
 345       *padding += width - res;
 346       res = width;
 347     }
 348   else if (deriv == &d_dot)
 349     {
 350       if (depth == 0)
 351         begin_use_class ("cex-dot", out);
 352       res += fputs_if (depth == 0, out, padding, dot);
 353       if (depth == 0)
 354         end_use_class ("cex-dot", out);
 355     }
 356   else // leaf.
 357     {
 358       const symbol *sym = symbols[deriv->sym];
 359       if (depth == 0)
 360         begin_use_class ("cex-leaf", out);
 361       res += fputs_if (depth == 0, out, padding, sym->tag);
 362       if (depth == 0)
 363         end_use_class ("cex-leaf", out);
 364     }
 365   return res;
 366 }
 367
 368 static void
 369 derivation_print_tree (const derivation *deriv, FILE *out, const char *prefix)
 370 {
 371   fputc ('\n', out);
 372   for (int depth = 0, max_depth = derivation_depth (deriv);
 373        depth < max_depth; ++depth)
 374     {
 375       int padding = 0;
 376       fprintf (out, "    %s", prefix);
 377       derivation_print_tree_impl (deriv, out, depth, &padding);
 378       fputc ('\n', out);
 379     }
 380 }
 381
 382
 383 /* Print DERIV, colored according to COUNTER.
 384    Return false if nothing is printed.  */
 385 static bool
 386 derivation_print_flat_impl (derivation *deriv, FILE *out,
 387                             bool leaves_only,
 388                             int *counter, const char *prefix)
 389 {
 390   if (deriv->children)
 391     {
 392       const symbol *sym = symbols[deriv->sym];
 393       deriv->color = *counter;
 394       ++*counter;
 395       char style[20];
 396       snprintf (style, 20, "cex-%d", deriv->color);
 397       begin_use_class (style, out);
 398
 399       if (!leaves_only)
 400         {
 401           fputs (prefix, out);
 402           begin_use_class ("cex-step", out);
 403           fprintf (out, "%s %s [ ", sym->tag, arrow);
 404           end_use_class ("cex-step", out);
 405           prefix = "";
 406         }
 407       bool res = false;
 408       derivation *child;
 409       for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
 410            derivation_list_next (&it, &child);
 411            )
 412         {
 413           if (derivation_print_flat_impl (child, out,
 414                                           leaves_only, counter, prefix))
 415             {
 416               prefix = " ";
 417               res = true;
 418             }
 419           else if (!leaves_only)
 420             prefix = " ";
 421         }
 422       if (!leaves_only)
 423         {
 424           begin_use_class ("cex-step", out);
 425           if (res)
 426             fputs (" ]", out);
 427           else
 428             fputs ("]", out);
 429           end_use_class ("cex-step", out);
 430         }
 431       end_use_class (style, out);
 432       return res;
 433     }
 434   else if (deriv == &d_dot)
 435     {
 436       fputs (prefix, out);
 437       begin_use_class ("cex-dot", out);
 438       fputs (dot, out);
 439       end_use_class ("cex-dot", out);
 440     }
 441   else // leaf.
 442     {
 443       fputs (prefix, out);
 444       const symbol *sym = symbols[deriv->sym];
 445       begin_use_class ("cex-leaf", out);
 446       fprintf (out, "%s", sym->tag);
 447       end_use_class ("cex-leaf", out);
 448     }
 449   return true;
 450 }
 451
 452 static void
 453 derivation_print_flat (const derivation *deriv, FILE *out, const char *prefix)
 454 {
 455   int counter = 0;
 456   fputs (prefix, out);
 457   derivation_print_flat_impl ((derivation *)deriv, out, false, &counter, "");
 458   fputc ('\n', out);
 459 }
 460
 461 void
 462 derivation_print_leaves (const derivation *deriv, FILE *out)
 463 {
 464   int counter = 0;
 465   derivation_print_flat_impl ((derivation *)deriv, out, true, &counter, "");
 466   fputc ('\n', out);
 467 }
 468
 469 void
 470 derivation_print (const derivation *deriv, FILE *out, const char *prefix)
 471 {
 472   if (getenv ("YYFLAT"))
 473     derivation_print_flat (deriv, out, prefix);
 474   else
 475     derivation_print_tree (deriv, out, prefix);
 476 }