1 /* Counterexample derivation trees
3 Copyright (C) 2020-2022 Free Software Foundation, Inc.
5 This file is part of Bison, the GNU Compiler Compiler.
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.
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.
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/>. */
22 #include "derivation.h"
26 #include <gl_linked_list.h>
28 #include <vasnprintf.h>
36 derivation_list children
;
38 // The rule SYM -> CHILDREN.
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.
46 static derivation d_dot
= { -1, NULL
, -1, NULL
, -1 };
55 derivation_list_append (derivation_list dl
, derivation
*d
)
57 derivation_retain (d
);
58 gl_list_add_last (dl
, d
);
62 derivation_list_prepend (derivation_list dl
, derivation
*d
)
64 derivation_retain (d
);
65 gl_list_add_first (dl
, d
);
68 void derivation_list_free (derivation_list dl
)
71 for (gl_list_iterator_t it
= gl_list_iterator (dl
);
72 derivation_list_next (&it
, &d
);
80 derivation_new (symbol_number sym
, derivation_list children
,
83 derivation
*res
= xmalloc (sizeof *res
);
85 res
->children
= children
;
86 res
->reference_count
= 0;
93 derivation_retain (derivation
*d
)
99 derivation_free (derivation
*d
)
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)
108 derivation
*deriv
= (derivation
*) gl_list_get_at (free_queue
, 0);
109 if (--deriv
->reference_count
== 0)
113 derivation
*child
= NULL
;
114 for (gl_list_iterator_t it
= gl_list_iterator (deriv
->children
);
115 derivation_list_next (&it
, &child
);
118 gl_list_add_last (free_queue
, child
);
119 gl_list_free (deriv
->children
);
123 gl_list_remove_at (free_queue
, 0);
125 gl_list_free (free_queue
);
129 derivation_size (const derivation
*deriv
)
131 if (!deriv
->children
)
134 derivation
*child
= NULL
;
135 for (gl_list_iterator_t it
= gl_list_iterator (deriv
->children
);
136 derivation_list_next (&it
, &child
);
138 size
+= derivation_size (child
);
143 // Longest distance from root to leaf.
145 derivation_depth (const derivation
*deriv
)
149 // Children's depth cannot be 0, even if there are no children
150 // (the case of a derivation with an empty RHS).
153 for (gl_list_iterator_t it
= gl_list_iterator (deriv
->children
);
154 derivation_list_next (&it
, &child
);
156 res
= max_int (res
, derivation_depth (child
));
164 all_spaces (const char *s
)
166 while (c_isspace (*s
))
171 // Printing the derivation as trees without trailing spaces is
172 // painful: we cannot simply pad one "column" before moving to the
177 // ↳ x2 ↳ ε ↳ foo2 ↳ x2
179 // ↳ "X" • ↳ x1 foo4 ↳ "X"
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.
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.
193 // This function implements this.
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.
198 fputs_if (bool cond
, FILE *out
, int *padding
, const char *s
)
200 int res
= mbswidth (s
, 0);
201 if (cond
&& !all_spaces (s
))
203 fprintf (out
, "%*s%s", *padding
, "", s
);
214 fprintf_if (bool cond
, FILE *out
, int *padding
, const char *fmt
, ...)
217 size_t len
= sizeof (buf
);
219 va_start (args
, fmt
);
220 char *cp
= vasnprintf (buf
, &len
, fmt
, args
);
224 int res
= fputs_if (cond
, out
, padding
, cp
);
230 // The width taken to report this derivation recursively down to its
233 derivation_width (const derivation
*deriv
)
237 const symbol
*sym
= symbols
[deriv
->sym
];
238 int self_width
= mbswidth (sym
->tag
, 0);
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)
245 children_width
+= empty_width
;
248 if (gl_list_size (deriv
->children
) == 1
249 && gl_list_get_first (deriv
->children
) == &d_dot
)
251 children_width
+= empty_width
;
252 children_width
+= derivation_separator_width
;
256 for (gl_list_iterator_t it
= gl_list_iterator (deriv
->children
);
257 derivation_list_next (&it
, &child
);
260 += derivation_separator_width
+ derivation_width (child
);
261 // No separator at the beginning.
262 children_width
-= derivation_separator_width
;
264 return max_int (self_width
, children_width
);
266 else if (deriv
== &d_dot
)
272 const symbol
*sym
= symbols
[deriv
->sym
];
273 return mbswidth (sym
->tag
, 0);
278 // Print DERIV for DEPTH.
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.
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).
287 // Return the "logical printed" width. We might have not have reached
288 // that width, in which case the missing spaces are in *PADDING.
290 derivation_print_tree_impl (const derivation
*deriv
, FILE *out
,
291 int depth
, int *padding
)
293 const int width
= derivation_width (deriv
);
298 const symbol
*sym
= symbols
[deriv
->sym
];
300 snprintf (style
, 20, "cex-%d", deriv
->color
);
302 if (depth
== 0 || depth
== 1)
304 begin_use_class (style
, out
);
305 begin_use_class ("cex-step", out
);
309 res
+= fputs_if (true, out
, padding
, sym
->tag
);
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)
317 res
+= fputs_if (depth
== 1, out
, padding
, empty
);
320 if (gl_list_size (deriv
->children
) == 1
321 && gl_list_get_first (deriv
->children
) == &d_dot
)
323 res
+= fputs_if (depth
== 1, out
, padding
, empty
);
324 res
+= fputs_if (depth
== 1, out
, padding
, derivation_separator
);
329 for (gl_list_iterator_t it
= gl_list_iterator (deriv
->children
);
330 derivation_list_next (&it
, &child
);
334 res
+= fputs_if (depth
== 1, out
, padding
, derivation_separator
);
335 res
+= derivation_print_tree_impl (child
, out
, depth
- 1, padding
);
340 if (depth
== 0 || depth
== 1)
342 end_use_class ("cex-step", out
);
343 end_use_class (style
, out
);
345 *padding
+= width
- res
;
348 else if (deriv
== &d_dot
)
351 begin_use_class ("cex-dot", out
);
352 res
+= fputs_if (depth
== 0, out
, padding
, dot
);
354 end_use_class ("cex-dot", out
);
358 const symbol
*sym
= symbols
[deriv
->sym
];
360 begin_use_class ("cex-leaf", out
);
361 res
+= fputs_if (depth
== 0, out
, padding
, sym
->tag
);
363 end_use_class ("cex-leaf", out
);
369 derivation_print_tree (const derivation
*deriv
, FILE *out
, const char *prefix
)
372 for (int depth
= 0, max_depth
= derivation_depth (deriv
);
373 depth
< max_depth
; ++depth
)
376 fprintf (out
, " %s", prefix
);
377 derivation_print_tree_impl (deriv
, out
, depth
, &padding
);
383 /* Print DERIV, colored according to COUNTER.
384 Return false if nothing is printed. */
386 derivation_print_flat_impl (derivation
*deriv
, FILE *out
,
388 int *counter
, const char *prefix
)
392 const symbol
*sym
= symbols
[deriv
->sym
];
393 deriv
->color
= *counter
;
396 snprintf (style
, 20, "cex-%d", deriv
->color
);
397 begin_use_class (style
, out
);
402 begin_use_class ("cex-step", out
);
403 fprintf (out
, "%s %s [ ", sym
->tag
, arrow
);
404 end_use_class ("cex-step", out
);
409 for (gl_list_iterator_t it
= gl_list_iterator (deriv
->children
);
410 derivation_list_next (&it
, &child
);
413 if (derivation_print_flat_impl (child
, out
,
414 leaves_only
, counter
, prefix
))
419 else if (!leaves_only
)
424 begin_use_class ("cex-step", out
);
429 end_use_class ("cex-step", out
);
431 end_use_class (style
, out
);
434 else if (deriv
== &d_dot
)
437 begin_use_class ("cex-dot", out
);
439 end_use_class ("cex-dot", 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
);
453 derivation_print_flat (const derivation
*deriv
, FILE *out
, const char *prefix
)
457 derivation_print_flat_impl ((derivation
*)deriv
, out
, false, &counter
, "");
462 derivation_print_leaves (const derivation
*deriv
, FILE *out
)
465 derivation_print_flat_impl ((derivation
*)deriv
, out
, true, &counter
, "");
470 derivation_print (const derivation
*deriv
, FILE *out
, const char *prefix
)
472 if (getenv ("YYFLAT"))
473 derivation_print_flat (deriv
, out
, prefix
);
475 derivation_print_tree (deriv
, out
, prefix
);