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 }