/* Counterexample derivation trees Copyright (C) 2020-2021 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include #include "derivation.h" #include "glyphs.h" #include #include #include #include #include "system.h" #include "complain.h" struct derivation { symbol_number sym; derivation_list children; int reference_count; // The rule SYM -> CHILDREN. const rule *rule; // Color assigned for styling. Guarantees that the derivation is // always displayed with the same color, independently of the order // in which the derivations are traversed. int color; }; static derivation d_dot = { -1, NULL, -1, NULL, -1 }; derivation * derivation_dot (void) { return &d_dot; } void derivation_list_append (derivation_list dl, derivation *d) { derivation_retain (d); gl_list_add_last (dl, d); } void derivation_list_prepend (derivation_list dl, derivation *d) { derivation_retain (d); gl_list_add_first (dl, d); } void derivation_list_free (derivation_list dl) { derivation *d = NULL; for (gl_list_iterator_t it = gl_list_iterator (dl); derivation_list_next (&it, &d); ) if (d != &d_dot) derivation_free (d); gl_list_free (dl); } derivation * derivation_new (symbol_number sym, derivation_list children, const rule *r) { derivation *res = xmalloc (sizeof *res); res->sym = sym; res->children = children; res->reference_count = 0; res->rule = r; res->color = -1; return res; } void derivation_retain (derivation *d) { ++d->reference_count; } void derivation_free (derivation *d) { if (!d) return; derivation_list free_queue = gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1, (const void **)&d); while (gl_list_size (free_queue) > 0) { derivation *deriv = (derivation *) gl_list_get_at (free_queue, 0); if (--deriv->reference_count == 0) { if (deriv->children) { derivation *child = NULL; for (gl_list_iterator_t it = gl_list_iterator (deriv->children); derivation_list_next (&it, &child); ) if (child != &d_dot) gl_list_add_last (free_queue, child); gl_list_free (deriv->children); } free (deriv); } gl_list_remove_at (free_queue, 0); } gl_list_free (free_queue); } size_t derivation_size (const derivation *deriv) { if (!deriv->children) return 1; int size = 1; derivation *child = NULL; for (gl_list_iterator_t it = gl_list_iterator (deriv->children); derivation_list_next (&it, &child); ) size += derivation_size (child); return size; } // Longest distance from root to leaf. static int derivation_depth (const derivation *deriv) { if (deriv->children) { // Children's depth cannot be 0, even if there are no children // (the case of a derivation with an empty RHS). int res = 1; derivation *child; for (gl_list_iterator_t it = gl_list_iterator (deriv->children); derivation_list_next (&it, &child); ) res = max_int (res, derivation_depth (child)); return res + 1; } else return 1; } static bool all_spaces (const char *s) { while (c_isspace (*s)) s++; return *s == '\0'; } // Printing the derivation as trees without trailing spaces is // painful: we cannot simply pad one "column" before moving to the // next: // // exp // ↳ x1 e1 foo1 x1 // ↳ x2 ↳ ε ↳ foo2 ↳ x2 // ↳ x3 ↳ foo3 ↳ x3 // ↳ "X" • ↳ x1 foo4 ↳ "X" // ↳ x2 ↳ "quuux" // ↳ x3 // ↳ "X" // // It's hard for a column to know that it's "last" to decide whether // to output the right-padding or not. So when we need to pad on the // right to complete a column, we don't output the spaces, we // accumulate the width of padding in *PADDING. // // Each time we actually print something (non space), we flush that // padding. When we _don't_ print something, its width is added to // the current padding. // // This function implements this. // // When COND is true, put S on OUT, preceded by *PADDING white spaces. // Otherwise add the width to *PADDING. Return the width of S. static int fputs_if (bool cond, FILE *out, int *padding, const char *s) { int res = mbswidth (s, 0); if (cond && !all_spaces (s)) { fprintf (out, "%*s%s", *padding, "", s); *padding = 0; } else { *padding += res; } return res; } static int fprintf_if (bool cond, FILE *out, int *padding, const char *fmt, ...) { char buf[256]; size_t len = sizeof (buf); va_list args; va_start (args, fmt); char *cp = vasnprintf (buf, &len, fmt, args); va_end (args); if (!cp) xalloc_die (); int res = fputs_if (cond, out, padding, cp); if (cp != buf) free (cp); return res; } // The width taken to report this derivation recursively down to its // leaves. static int derivation_width (const derivation *deriv) { if (deriv->children) { const symbol *sym = symbols[deriv->sym]; int self_width = mbswidth (sym->tag, 0); // Arrow and space. int children_width = down_arrow_width; children_width += snprintf (NULL, 0, "%d: ", deriv->rule->number); if (gl_list_size (deriv->children) == 0) // Empty rhs. children_width += empty_width; else { if (gl_list_size (deriv->children) == 1 && gl_list_get_first (deriv->children) == &d_dot) { children_width += empty_width; children_width += derivation_separator_width; } derivation *child; for (gl_list_iterator_t it = gl_list_iterator (deriv->children); derivation_list_next (&it, &child); ) children_width += derivation_separator_width + derivation_width (child); // No separator at the beginning. children_width -= derivation_separator_width; } return max_int (self_width, children_width); } else if (deriv == &d_dot) { return dot_width; } else // leaf. { const symbol *sym = symbols[deriv->sym]; return mbswidth (sym->tag, 0); } } // Print DERIV for DEPTH. // // The tree is printed from top to bottom with DEPTH ranging from 0 to // the total depth of the tree. DERIV should only printed when we // reach its depth, i.e., then DEPTH is 0. // // When DEPTH is 1 and we're on a subderivation, then we print the RHS // of the derivation (in DEPTH 0 we printed its LHS). // // Return the "logical printed" width. We might have not have reached // that width, in which case the missing spaces are in *PADDING. static int derivation_print_tree_impl (const derivation *deriv, FILE *out, int depth, int *padding) { const int width = derivation_width (deriv); int res = 0; if (deriv->children) { const symbol *sym = symbols[deriv->sym]; char style[20]; snprintf (style, 20, "cex-%d", deriv->color); if (depth == 0 || depth == 1) { begin_use_class (style, out); begin_use_class ("cex-step", out); } if (depth == 0) { res += fputs_if (true, out, padding, sym->tag); } else { res += fputs_if (depth == 1, out, padding, down_arrow); res += fprintf_if (depth == 1, out, padding, "%d: ", deriv->rule->number); if (gl_list_size (deriv->children) == 0) // Empty rhs. res += fputs_if (depth == 1, out, padding, empty); else { if (gl_list_size (deriv->children) == 1 && gl_list_get_first (deriv->children) == &d_dot) { res += fputs_if (depth == 1, out, padding, empty); res += fputs_if (depth == 1, out, padding, derivation_separator); } bool first = true; derivation *child; for (gl_list_iterator_t it = gl_list_iterator (deriv->children); derivation_list_next (&it, &child); ) { if (!first) res += fputs_if (depth == 1, out, padding, derivation_separator); res += derivation_print_tree_impl (child, out, depth - 1, padding); first = false; } } } if (depth == 0 || depth == 1) { end_use_class ("cex-step", out); end_use_class (style, out); } *padding += width - res; res = width; } else if (deriv == &d_dot) { if (depth == 0) begin_use_class ("cex-dot", out); res += fputs_if (depth == 0, out, padding, dot); if (depth == 0) end_use_class ("cex-dot", out); } else // leaf. { const symbol *sym = symbols[deriv->sym]; if (depth == 0) begin_use_class ("cex-leaf", out); res += fputs_if (depth == 0, out, padding, sym->tag); if (depth == 0) end_use_class ("cex-leaf", out); } return res; } static void derivation_print_tree (const derivation *deriv, FILE *out, const char *prefix) { fputc ('\n', out); for (int depth = 0, max_depth = derivation_depth (deriv); depth < max_depth; ++depth) { int padding = 0; fprintf (out, " %s", prefix); derivation_print_tree_impl (deriv, out, depth, &padding); fputc ('\n', out); } } /* Print DERIV, colored according to COUNTER. Return false if nothing is printed. */ static bool derivation_print_flat_impl (derivation *deriv, FILE *out, bool leaves_only, int *counter, const char *prefix) { if (deriv->children) { const symbol *sym = symbols[deriv->sym]; deriv->color = *counter; ++*counter; char style[20]; snprintf (style, 20, "cex-%d", deriv->color); begin_use_class (style, out); if (!leaves_only) { fputs (prefix, out); begin_use_class ("cex-step", out); fprintf (out, "%s %s [ ", sym->tag, arrow); end_use_class ("cex-step", out); prefix = ""; } bool res = false; derivation *child; for (gl_list_iterator_t it = gl_list_iterator (deriv->children); derivation_list_next (&it, &child); ) { if (derivation_print_flat_impl (child, out, leaves_only, counter, prefix)) { prefix = " "; res = true; } else if (!leaves_only) prefix = " "; } if (!leaves_only) { begin_use_class ("cex-step", out); if (res) fputs (" ]", out); else fputs ("]", out); end_use_class ("cex-step", out); } end_use_class (style, out); return res; } else if (deriv == &d_dot) { fputs (prefix, out); begin_use_class ("cex-dot", out); fputs (dot, out); end_use_class ("cex-dot", out); } else // leaf. { fputs (prefix, out); const symbol *sym = symbols[deriv->sym]; begin_use_class ("cex-leaf", out); fprintf (out, "%s", sym->tag); end_use_class ("cex-leaf", out); } return true; } static void derivation_print_flat (const derivation *deriv, FILE *out, const char *prefix) { int counter = 0; fputs (prefix, out); derivation_print_flat_impl ((derivation *)deriv, out, false, &counter, ""); fputc ('\n', out); } void derivation_print_leaves (const derivation *deriv, FILE *out) { int counter = 0; derivation_print_flat_impl ((derivation *)deriv, out, true, &counter, ""); fputc ('\n', out); } void derivation_print (const derivation *deriv, FILE *out, const char *prefix) { if (getenv ("YYFLAT")) derivation_print_flat (deriv, out, prefix); else derivation_print_tree (deriv, out, prefix); }