Branch data Line data Source code
1 : : /* Creating GraphViz .dot files from diagnostic state graphs.
2 : : Copyright (C) 2025 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #define INCLUDE_ALGORITHM
22 : : #define INCLUDE_MAP
23 : : #define INCLUDE_SET
24 : : #define INCLUDE_STRING
25 : : #define INCLUDE_VECTOR
26 : : #include "config.h"
27 : : #include "system.h"
28 : : #include "coretypes.h"
29 : :
30 : : #include "custom-sarif-properties/state-graphs.h"
31 : : #include "diagnostics/state-graphs.h"
32 : : #include "graphviz.h"
33 : : #include "xml.h"
34 : : #include "xml-printer.h"
35 : : #include "intl.h"
36 : :
37 : : using namespace diagnostics;
38 : : using namespace diagnostics::state_graphs;
39 : :
40 : : namespace state_node_properties = custom_sarif_properties::state_graphs::node;
41 : :
42 : : static int
43 : 12 : get_depth (const digraphs::node &n)
44 : : {
45 : 12 : int deepest_child = 0;
46 : 23 : for (size_t i = 0; i < n.get_num_children (); ++i)
47 : 11 : deepest_child = std::max (deepest_child,
48 : 11 : get_depth (n.get_child (i)));
49 : 12 : return deepest_child + 1;
50 : : }
51 : :
52 : : static const char *
53 : 2 : get_color_for_dynalloc_state (enum state_node_properties::dynalloc_state_t dynalloc_st)
54 : : {
55 : 2 : switch (dynalloc_st)
56 : : {
57 : 0 : default:
58 : 0 : gcc_unreachable ();
59 : : break;
60 : : case state_node_properties::dynalloc_state_t::unknown:
61 : : case state_node_properties::dynalloc_state_t::nonnull:
62 : : return nullptr;
63 : :
64 : 0 : case state_node_properties::dynalloc_state_t::unchecked:
65 : 0 : return "#ec7a08"; // pf-orange-400
66 : :
67 : 0 : case state_node_properties::dynalloc_state_t::freed:
68 : 0 : return "#cc0000"; // pf-red-100
69 : : }
70 : : }
71 : :
72 : : static void
73 : 0 : set_color_for_dynalloc_state (dot::attr_list &attrs,
74 : : enum state_node_properties::dynalloc_state_t state)
75 : : {
76 : 0 : if (const char *color = get_color_for_dynalloc_state (state))
77 : 0 : attrs.add (dot::id ("color"), dot::id (color));
78 : 0 : }
79 : :
80 : : class state_diagram : public dot::graph
81 : : {
82 : : public:
83 : 1 : state_diagram (const diagnostics::digraphs::digraph &input_state_graph,
84 : : const logical_locations::manager &logical_loc_mgr)
85 : 1 : : m_logical_loc_mgr (logical_loc_mgr)
86 : : {
87 : : // "node [shape=plaintext]\n"
88 : 1 : {
89 : 1 : auto attr_stmt
90 : 1 : = std::make_unique<dot::attr_stmt> (dot::attr_stmt::kind::node);
91 : 1 : attr_stmt->m_attrs.add (dot::id ("shape"), dot::id ("plaintext"));
92 : 1 : add_stmt (std::move (attr_stmt));
93 : 1 : }
94 : :
95 : : /* Determine which nodes are involved in edges. */
96 : 1 : for (size_t i = 0; i < input_state_graph.get_num_edges (); ++i)
97 : : {
98 : 0 : auto &edge = input_state_graph.get_edge (i);
99 : 0 : m_src_nodes.insert (&edge.get_src_node ());
100 : 0 : m_dst_nodes.insert (&edge.get_dst_node ());
101 : : }
102 : :
103 : : /* Recurse down the nodes in the state graph, creating subgraphs
104 : : and then eventually creating nodes, and recursively
105 : : creating XML tables, and adding ports for the endpoints of edges
106 : : where needed. */
107 : :
108 : 1 : auto root_cluster
109 : 1 : = std::make_unique<dot::subgraph> (dot::id ("cluster_memory_regions"));
110 : 2 : for (size_t i = 0; i < input_state_graph.get_num_nodes (); ++i)
111 : 1 : on_input_state_node (*root_cluster,
112 : 1 : input_state_graph.get_node (i));
113 : 1 : add_stmt (std::move (root_cluster));
114 : :
115 : : /* Now create dot edges for edges in input_stage_graph. */
116 : 1 : for (size_t i = 0; i < input_state_graph.get_num_edges (); ++i)
117 : : {
118 : 0 : auto &edge = input_state_graph.get_edge (i);
119 : 0 : auto &src_node = edge.get_src_node ();
120 : 0 : auto &dst_node = edge.get_dst_node ();
121 : :
122 : 0 : auto src_port_id = m_src_node_to_port_id.find (&src_node);
123 : 0 : if (src_port_id == m_src_node_to_port_id.end ())
124 : 0 : continue;
125 : 0 : auto dst_port_id = m_dst_node_to_port_id.find (&dst_node);
126 : 0 : if (dst_port_id == m_dst_node_to_port_id.end ())
127 : 0 : continue;
128 : :
129 : 0 : auto e = std::make_unique<dot::edge_stmt> (src_port_id->second,
130 : 0 : dst_port_id->second);
131 : 0 : set_color_for_dynalloc_state
132 : 0 : (e->m_attrs,
133 : : dst_node.get_property (state_node_properties::dynalloc_state_prop));
134 : :
135 : 0 : add_stmt (std::move (e));
136 : 0 : }
137 : 1 : }
138 : :
139 : : private:
140 : : struct pending_edge
141 : : {
142 : : dot::node_id m_src_node_id;
143 : : std::string m_dst_region_id;
144 : : };
145 : :
146 : : dot::id
147 : : get_id_for_region (const char *region_id)
148 : : {
149 : : gcc_assert (region_id);
150 : : return std::string ("cluster_region_") + region_id;
151 : : }
152 : :
153 : : dot::id
154 : 2 : make_id (const diagnostics::digraphs::node &state_node, bool cluster)
155 : : {
156 : 2 : std::string input_node_id = state_node.get_id ();
157 : 2 : if (cluster)
158 : 1 : return std::string ("cluster_") + input_node_id;
159 : : else
160 : 1 : return input_node_id;
161 : 2 : }
162 : :
163 : : bool
164 : 1 : starts_node_p (const diagnostics::digraphs::node &state_node)
165 : : {
166 : 1 : switch (state_node.get_property (state_node_properties::kind_prop))
167 : : {
168 : : default:
169 : : return false;
170 : :
171 : 1 : case state_node_properties::kind_t::stack:
172 : : /* We want all frames in the stack in the same table,
173 : : so they are grouped. */
174 : 1 : case state_node_properties::kind_t::dynalloc_buffer:
175 : 1 : case state_node_properties::kind_t::variable:
176 : 1 : return true;
177 : : }
178 : : }
179 : :
180 : : const char *
181 : 0 : get_label_for_node (const diagnostics::digraphs::node &state_node)
182 : : {
183 : 0 : switch (state_node.get_property (state_node_properties::kind_prop))
184 : : {
185 : : default:
186 : : return nullptr;
187 : :
188 : 0 : case state_node_properties::kind_t::globals:
189 : 0 : return _("Globals");
190 : 0 : case state_node_properties::kind_t::code:
191 : 0 : return _("Code");
192 : 0 : case state_node_properties::kind_t::stack:
193 : 0 : return _("Stack");
194 : 0 : case state_node_properties::kind_t::heap_:
195 : 0 : return _("Heap");
196 : : }
197 : : }
198 : :
199 : : void
200 : 1 : on_input_state_node (dot::subgraph &parent_subgraph,
201 : : const diagnostics::digraphs::node &state_node)
202 : : {
203 : 1 : dot::id sg_id = make_id (state_node, true);
204 : :
205 : 1 : if (starts_node_p (state_node))
206 : : {
207 : : // Create node with table
208 : 1 : xml::element table ("table", false);
209 : 1 : xml::printer xp (table);
210 : 1 : xp.set_attr ("border", "0");
211 : 1 : xp.set_attr ("cellborder", "1");
212 : 1 : xp.set_attr ("cellspacing", "0");
213 : :
214 : 1 : const int max_depth = get_depth (state_node);
215 : 1 : const int num_columns = max_depth + 2;
216 : :
217 : 1 : dot::id id_of_dot_node = make_id (state_node, false);
218 : 1 : on_node_in_table (id_of_dot_node, xp, state_node,
219 : : max_depth, 0, num_columns);
220 : :
221 : 1 : auto node = std::make_unique<dot::node_stmt> (std::move (id_of_dot_node));
222 : 2 : node->m_attrs.add (dot::id ("shape"),
223 : 2 : dot::id ("plaintext"));
224 : :
225 : : // xml must be done by now
226 : :
227 : 1 : node->m_attrs.add (dot::id ("label"),
228 : 1 : dot::id (table));
229 : :
230 : 1 : parent_subgraph.m_stmt_list.add_stmt (std::move (node));
231 : 1 : }
232 : : else
233 : : {
234 : 0 : auto child_subgraph = std::make_unique<dot::subgraph> (std::move (sg_id));
235 : :
236 : 0 : if (const char *label = get_label_for_node (state_node))
237 : 0 : child_subgraph->add_attr (dot::id ("label"), dot::id (label));
238 : :
239 : : // recurse:
240 : 0 : for (size_t i = 0; i < state_node.get_num_children (); ++i)
241 : 0 : on_input_state_node (*child_subgraph,
242 : 0 : state_node.get_child (i));
243 : 0 : parent_subgraph.m_stmt_list.add_stmt (std::move (child_subgraph));
244 : 0 : }
245 : 1 : }
246 : :
247 : : enum class style { h1, h2 };
248 : :
249 : : void
250 : 2 : add_title_tr (const dot::id &id_of_dot_node,
251 : : xml::printer &xp,
252 : : int num_columns,
253 : : const diagnostics::digraphs::node &state_node,
254 : : std::string heading,
255 : : enum style styl,
256 : : enum state_node_properties::dynalloc_state_t dynalloc_state)
257 : : {
258 : 2 : xp.push_tag ("tr", true);
259 : 2 : xp.push_tag ("td", false);
260 : 2 : xp.set_attr ("colspan", std::to_string (num_columns));
261 : 2 : xp.set_attr ("cellpadding", "5");
262 : :
263 : 2 : const char *bgcolor;
264 : 2 : const char *color;
265 : 2 : if (const char *c = get_color_for_dynalloc_state (dynalloc_state))
266 : : {
267 : : bgcolor = c;
268 : : color = "white";
269 : : }
270 : : else
271 : 2 : switch (styl)
272 : : {
273 : 0 : default:
274 : 0 : gcc_unreachable ();
275 : : case style::h1:
276 : : // from diagnostics/html-sink.cc: HTML_STYLE .linenum
277 : : bgcolor = "#0088ce";
278 : : color = "white";
279 : : break;
280 : 1 : case style::h2:
281 : : // from diagnostics/html-sink.cc: HTML_STYLE .events-hdr
282 : 1 : bgcolor = "#393f44"; // pf-black-800
283 : 1 : color = "white";
284 : 1 : break;
285 : : }
286 : :
287 : 2 : xp.set_attr ("bgcolor", bgcolor);
288 : 2 : xp.push_tag ("font", false);
289 : 2 : xp.set_attr ("color", color);
290 : 2 : if (heading == "")
291 : 0 : heading = " ";
292 : 2 : xp.add_text (std::move (heading));
293 : 2 : xp.pop_tag ("font");
294 : :
295 : 2 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
296 : :
297 : 2 : xp.pop_tag ("td");
298 : 2 : xp.pop_tag ("tr");
299 : 2 : }
300 : :
301 : : /* Recursively add <TR> to XP for STATE_NODE and its descendents. */
302 : : void
303 : 11 : on_node_in_table (const dot::id &id_of_dot_node,
304 : : xml::printer &xp,
305 : : const diagnostics::digraphs::node &state_node,
306 : : int max_depth,
307 : : int depth,
308 : : int num_columns)
309 : : {
310 : 11 : bool recurse = true;
311 : 11 : auto input_node_kind
312 : 11 : = state_node.get_property (state_node_properties::kind_prop);
313 : :
314 : 11 : switch (input_node_kind)
315 : : {
316 : : case state_node_properties::kind_t::padding:
317 : : case state_node_properties::kind_t::other:
318 : : return;
319 : :
320 : 1 : case state_node_properties::kind_t::stack:
321 : 1 : add_title_tr (id_of_dot_node, xp, num_columns, state_node, "Stack",
322 : : style::h1,
323 : : state_node_properties::dynalloc_state_t::unknown);
324 : 1 : break;
325 : 1 : case state_node_properties::kind_t::stack_frame:
326 : 1 : if (auto logical_loc = state_node.get_logical_loc ())
327 : 2 : if (const char *function
328 : 1 : = m_logical_loc_mgr.get_short_name (logical_loc))
329 : 2 : add_title_tr (id_of_dot_node, xp, num_columns, state_node,
330 : 3 : std::string ("Frame: ") + function,
331 : : style::h2,
332 : : state_node_properties::dynalloc_state_t::unknown);
333 : : break;
334 : 0 : case state_node_properties::kind_t::dynalloc_buffer:
335 : 0 : {
336 : 0 : enum state_node_properties::dynalloc_state_t dynalloc_st
337 : : = state_node.get_property
338 : 0 : (state_node_properties::dynalloc_state_prop);
339 : 0 : const char *extents
340 : 0 : = state_node.get_property (state_node_properties::dynamic_extents);
341 : 0 : const char *type = state_node.get_property (state_node_properties::type);
342 : 0 : pretty_printer pp;
343 : 0 : switch (dynalloc_st)
344 : : {
345 : 0 : default:
346 : 0 : gcc_unreachable ();
347 : :
348 : 0 : case state_node_properties::dynalloc_state_t::unknown:
349 : 0 : case state_node_properties::dynalloc_state_t::nonnull:
350 : 0 : if (type)
351 : : {
352 : 0 : if (extents)
353 : 0 : pp_printf (&pp, "%s (%s byte allocation)",
354 : : type, extents);
355 : : else
356 : 0 : pp_printf (&pp, "%s", type);
357 : : }
358 : : else
359 : : {
360 : 0 : if (extents)
361 : 0 : pp_printf (&pp, "%s byte allocation",
362 : : extents);
363 : : }
364 : : break;
365 : :
366 : 0 : case state_node_properties::dynalloc_state_t::unchecked:
367 : 0 : if (type)
368 : : {
369 : 0 : if (extents)
370 : 0 : pp_printf (&pp, "%s (unchecked %s byte allocation)",
371 : : type, extents);
372 : : }
373 : : else
374 : : {
375 : 0 : if (extents)
376 : 0 : pp_printf (&pp, "Unchecked %s byte allocation",
377 : : extents);
378 : : }
379 : : break;
380 : :
381 : 0 : case state_node_properties::dynalloc_state_t::freed:
382 : : // TODO: show deallocator
383 : : // TODO: show deallocation event
384 : 0 : pp_printf (&pp, "Freed buffer");
385 : 0 : break;
386 : : }
387 : 0 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
388 : 0 : add_title_tr (id_of_dot_node, xp, num_columns, state_node,
389 : 0 : pp_formatted_text (&pp),
390 : : style::h2,
391 : : dynalloc_st);
392 : 0 : }
393 : 0 : break;
394 : :
395 : 8 : default:
396 : 8 : {
397 : 8 : xp.push_tag ("tr", true);
398 : :
399 : 8 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
400 : :
401 : 8 : if (depth > 0)
402 : : {
403 : : /* Indent, by create a <td> spanning "depth" columns. */
404 : 8 : xp.push_tag ("td", false);
405 : 8 : xp.set_attr ("colspan", std::to_string (depth));
406 : 8 : xp.add_text (" "); // graphviz doesn't like <td/>
407 : 8 : xp.pop_tag ("td");
408 : : }
409 : :
410 : 8 : switch (input_node_kind)
411 : : {
412 : : default:
413 : : break;
414 : 1 : case state_node_properties::kind_t::variable:
415 : 1 : {
416 : 1 : const char *name
417 : 1 : = state_node.get_property (state_node_properties::name);
418 : 1 : gcc_assert (name);
419 : 1 : xp.push_tag ("td", false);
420 : 1 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
421 : 1 : push_src_text (xp);
422 : 1 : xp.add_text (name);
423 : 2 : pop_src_text (xp);
424 : 1 : xp.pop_tag ("td");
425 : : }
426 : 1 : break;
427 : 4 : case state_node_properties::kind_t::element:
428 : 4 : {
429 : 4 : const char *index
430 : 4 : = state_node.get_property (state_node_properties::index);
431 : 4 : gcc_assert (index);
432 : 4 : xp.push_tag ("td", false);
433 : 4 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
434 : 4 : push_src_text (xp);
435 : 4 : xp.add_text ("[");
436 : 4 : xp.add_text (index);
437 : 4 : xp.add_text ("]");
438 : 8 : pop_src_text (xp);
439 : 4 : xp.pop_tag ("td");
440 : : }
441 : 4 : break;
442 : 3 : case state_node_properties::kind_t::field:
443 : 3 : {
444 : 3 : const char *name
445 : 3 : = state_node.get_property (state_node_properties::name);
446 : 3 : gcc_assert (name);
447 : 3 : xp.push_tag ("td", false);
448 : 3 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
449 : 3 : push_src_text (xp);
450 : 3 : xp.add_text (".");
451 : 3 : xp.add_text (name);
452 : 6 : pop_src_text (xp);
453 : 3 : xp.pop_tag ("td");
454 : : }
455 : 3 : break;
456 : : }
457 : :
458 : 16 : if (const char *type
459 : 8 : = state_node.get_property (state_node_properties::type))
460 : : {
461 : 8 : xp.push_tag ("td", false);
462 : 8 : xp.set_attr ("align", "right");
463 : 8 : push_src_text (xp);
464 : 8 : xp.add_text (type);
465 : 16 : pop_src_text (xp);
466 : 8 : xp.pop_tag ("td");
467 : : }
468 : :
469 : 16 : if (const char *value
470 : 8 : = state_node.get_property (state_node_properties::value_str))
471 : : {
472 : 1 : xp.push_tag ("td", false);
473 : 1 : xp.set_attr ("align", "left");
474 : 1 : maybe_add_src_port (id_of_dot_node, xp, state_node);
475 : 1 : push_src_text (xp);
476 : 1 : xp.add_text (value);
477 : 2 : pop_src_text (xp);
478 : 1 : xp.pop_tag ("td");
479 : 1 : recurse = false;
480 : : }
481 : :
482 : 8 : xp.pop_tag ("tr");
483 : : }
484 : 8 : break;
485 : : }
486 : :
487 : 10 : if (recurse)
488 : 19 : for (size_t i = 0; i < state_node.get_num_children (); ++i)
489 : 10 : on_node_in_table (id_of_dot_node, xp,
490 : 10 : state_node.get_child (i),
491 : : max_depth, depth + 1, num_columns);
492 : : }
493 : :
494 : : void
495 : 17 : push_src_text (xml::printer &xp)
496 : : {
497 : 17 : xp.push_tag ("font");
498 : 17 : xp.set_attr ("color", "blue");
499 : 17 : }
500 : :
501 : : void
502 : 17 : pop_src_text (xml::printer &xp)
503 : : {
504 : 17 : xp.pop_tag ("font");
505 : : }
506 : :
507 : : /* If STATE_NODE is in m_src_nodes, add a port to XP for possible
508 : : incoming edges to use. */
509 : :
510 : : void
511 : 1 : maybe_add_src_port (const dot::id &id_of_dot_node,
512 : : xml::printer &xp,
513 : : const diagnostics::digraphs::node &state_node)
514 : : {
515 : 1 : auto iter = m_src_nodes.find (&state_node);
516 : 1 : if (iter == m_src_nodes.end ())
517 : 1 : return;
518 : :
519 : 0 : dot::id src_id = make_id (state_node, false);
520 : 0 : dot::node_id node_id (id_of_dot_node,
521 : 0 : dot::port (src_id,
522 : 0 : dot::compass_pt::e));
523 : 0 : m_src_node_to_port_id.insert ({&state_node, node_id});
524 : 0 : xp.set_attr ("port", src_id.m_str);
525 : 0 : }
526 : :
527 : : /* If STATE_NODE is in m_dst_nodes, add a port to XP for possible
528 : : incoming edges to use. */
529 : :
530 : : void
531 : 18 : maybe_add_dst_port (const dot::id &id_of_dot_node,
532 : : xml::printer &xp,
533 : : const diagnostics::digraphs::node &state_node)
534 : : {
535 : 18 : auto iter = m_dst_nodes.find (&state_node);
536 : 18 : if (iter == m_dst_nodes.end ())
537 : 18 : return;
538 : :
539 : 0 : dot::id dst_id = make_id (state_node, false);
540 : 0 : dot::node_id node_id (id_of_dot_node,
541 : 0 : dot::port (dst_id/*,
542 : 0 : dot::compass_pt::w*/));
543 : 0 : m_dst_node_to_port_id.insert ({&state_node, node_id});
544 : 0 : xp.set_attr ("port", dst_id.m_str);
545 : 0 : }
546 : :
547 : : private:
548 : : const logical_locations::manager &m_logical_loc_mgr;
549 : :
550 : : /* All nodes involved in edges (and thus will need a port). */
551 : : std::set<const digraphs::node *> m_src_nodes;
552 : : std::set<const digraphs::node *> m_dst_nodes;
553 : :
554 : : std::map<const digraphs::node *, dot::node_id> m_src_node_to_port_id;
555 : : std::map<const digraphs::node *, dot::node_id> m_dst_node_to_port_id;
556 : : };
557 : :
558 : : std::unique_ptr<dot::graph>
559 : 1 : state_graphs::
560 : : make_dot_graph (const digraphs::digraph &state_graph,
561 : : const logical_locations::manager &logical_loc_mgr)
562 : : {
563 : 1 : return std::make_unique<state_diagram> (state_graph, logical_loc_mgr);
564 : : }
|
