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