Line data Source code
1 : /* Creating GraphViz .dot files from diagnostic state graphs.
2 : Copyright (C) 2025-2026 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 : {
328 1 : label_text function
329 1 : = m_logical_loc_mgr.get_short_name (logical_loc);
330 1 : if (function.get ())
331 1 : add_title_tr (id_of_dot_node, xp, num_columns, state_node,
332 3 : std::string ("Frame: ") + function.get (),
333 : style::h2,
334 : state_node_properties::dynalloc_state_t::unknown);
335 1 : }
336 : break;
337 0 : case state_node_properties::kind_t::dynalloc_buffer:
338 0 : {
339 0 : enum state_node_properties::dynalloc_state_t dynalloc_st
340 : = state_node.get_property
341 0 : (state_node_properties::dynalloc_state_prop);
342 0 : const char *extents
343 0 : = state_node.get_property (state_node_properties::dynamic_extents);
344 0 : const char *type = state_node.get_property (state_node_properties::type);
345 0 : pretty_printer pp;
346 0 : switch (dynalloc_st)
347 : {
348 0 : default:
349 0 : gcc_unreachable ();
350 :
351 0 : case state_node_properties::dynalloc_state_t::unknown:
352 0 : case state_node_properties::dynalloc_state_t::nonnull:
353 0 : if (type)
354 : {
355 0 : if (extents)
356 0 : pp_printf (&pp, "%s (%s byte allocation)",
357 : type, extents);
358 : else
359 0 : pp_printf (&pp, "%s", type);
360 : }
361 : else
362 : {
363 0 : if (extents)
364 0 : pp_printf (&pp, "%s byte allocation",
365 : extents);
366 : }
367 : break;
368 :
369 0 : case state_node_properties::dynalloc_state_t::unchecked:
370 0 : if (type)
371 : {
372 0 : if (extents)
373 0 : pp_printf (&pp, "%s (unchecked %s byte allocation)",
374 : type, extents);
375 : }
376 : else
377 : {
378 0 : if (extents)
379 0 : pp_printf (&pp, "Unchecked %s byte allocation",
380 : extents);
381 : }
382 : break;
383 :
384 0 : case state_node_properties::dynalloc_state_t::freed:
385 : // TODO: show deallocator
386 : // TODO: show deallocation event
387 0 : pp_printf (&pp, "Freed buffer");
388 0 : break;
389 : }
390 0 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
391 0 : add_title_tr (id_of_dot_node, xp, num_columns, state_node,
392 0 : pp_formatted_text (&pp),
393 : style::h2,
394 : dynalloc_st);
395 0 : }
396 0 : break;
397 :
398 8 : default:
399 8 : {
400 8 : xp.push_tag ("tr", true);
401 :
402 8 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
403 :
404 8 : if (depth > 0)
405 : {
406 : /* Indent, by create a <td> spanning "depth" columns. */
407 8 : xp.push_tag ("td", false);
408 8 : xp.set_attr ("colspan", std::to_string (depth));
409 8 : xp.add_text (" "); // graphviz doesn't like <td/>
410 8 : xp.pop_tag ("td");
411 : }
412 :
413 8 : switch (input_node_kind)
414 : {
415 : default:
416 : break;
417 1 : case state_node_properties::kind_t::variable:
418 1 : {
419 1 : const char *name
420 1 : = state_node.get_property (state_node_properties::name);
421 1 : gcc_assert (name);
422 1 : xp.push_tag ("td", false);
423 1 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
424 1 : push_src_text (xp);
425 1 : xp.add_text (name);
426 2 : pop_src_text (xp);
427 1 : xp.pop_tag ("td");
428 : }
429 1 : break;
430 4 : case state_node_properties::kind_t::element:
431 4 : {
432 4 : const char *index
433 4 : = state_node.get_property (state_node_properties::index);
434 4 : gcc_assert (index);
435 4 : xp.push_tag ("td", false);
436 4 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
437 4 : push_src_text (xp);
438 4 : xp.add_text ("[");
439 4 : xp.add_text (index);
440 4 : xp.add_text ("]");
441 8 : pop_src_text (xp);
442 4 : xp.pop_tag ("td");
443 : }
444 4 : break;
445 3 : case state_node_properties::kind_t::field:
446 3 : {
447 3 : const char *name
448 3 : = state_node.get_property (state_node_properties::name);
449 3 : gcc_assert (name);
450 3 : xp.push_tag ("td", false);
451 3 : maybe_add_dst_port (id_of_dot_node, xp, state_node);
452 3 : push_src_text (xp);
453 3 : xp.add_text (".");
454 3 : xp.add_text (name);
455 6 : pop_src_text (xp);
456 3 : xp.pop_tag ("td");
457 : }
458 3 : break;
459 : }
460 :
461 16 : if (const char *type
462 8 : = state_node.get_property (state_node_properties::type))
463 : {
464 8 : xp.push_tag ("td", false);
465 8 : xp.set_attr ("align", "right");
466 8 : push_src_text (xp);
467 8 : xp.add_text (type);
468 16 : pop_src_text (xp);
469 8 : xp.pop_tag ("td");
470 : }
471 :
472 16 : if (const char *value
473 8 : = state_node.get_property (state_node_properties::value_str))
474 : {
475 1 : xp.push_tag ("td", false);
476 1 : xp.set_attr ("align", "left");
477 1 : maybe_add_src_port (id_of_dot_node, xp, state_node);
478 1 : push_src_text (xp);
479 1 : xp.add_text (value);
480 2 : pop_src_text (xp);
481 1 : xp.pop_tag ("td");
482 1 : recurse = false;
483 : }
484 :
485 8 : xp.pop_tag ("tr");
486 : }
487 8 : break;
488 : }
489 :
490 10 : if (recurse)
491 19 : for (size_t i = 0; i < state_node.get_num_children (); ++i)
492 10 : on_node_in_table (id_of_dot_node, xp,
493 10 : state_node.get_child (i),
494 : max_depth, depth + 1, num_columns);
495 : }
496 :
497 : void
498 17 : push_src_text (xml::printer &xp)
499 : {
500 17 : xp.push_tag ("font");
501 17 : xp.set_attr ("color", "blue");
502 17 : }
503 :
504 : void
505 17 : pop_src_text (xml::printer &xp)
506 : {
507 17 : xp.pop_tag ("font");
508 : }
509 :
510 : /* If STATE_NODE is in m_src_nodes, add a port to XP for possible
511 : incoming edges to use. */
512 :
513 : void
514 1 : maybe_add_src_port (const dot::id &id_of_dot_node,
515 : xml::printer &xp,
516 : const diagnostics::digraphs::node &state_node)
517 : {
518 1 : auto iter = m_src_nodes.find (&state_node);
519 1 : if (iter == m_src_nodes.end ())
520 1 : return;
521 :
522 0 : dot::id src_id = make_id (state_node, false);
523 0 : dot::node_id node_id (id_of_dot_node,
524 0 : dot::port (src_id,
525 0 : dot::compass_pt::e));
526 0 : m_src_node_to_port_id.insert ({&state_node, node_id});
527 0 : xp.set_attr ("port", src_id.m_str);
528 0 : }
529 :
530 : /* If STATE_NODE is in m_dst_nodes, add a port to XP for possible
531 : incoming edges to use. */
532 :
533 : void
534 18 : maybe_add_dst_port (const dot::id &id_of_dot_node,
535 : xml::printer &xp,
536 : const diagnostics::digraphs::node &state_node)
537 : {
538 18 : auto iter = m_dst_nodes.find (&state_node);
539 18 : if (iter == m_dst_nodes.end ())
540 18 : return;
541 :
542 0 : dot::id dst_id = make_id (state_node, false);
543 0 : dot::node_id node_id (id_of_dot_node,
544 0 : dot::port (dst_id/*,
545 0 : dot::compass_pt::w*/));
546 0 : m_dst_node_to_port_id.insert ({&state_node, node_id});
547 0 : xp.set_attr ("port", dst_id.m_str);
548 0 : }
549 :
550 : private:
551 : const logical_locations::manager &m_logical_loc_mgr;
552 :
553 : /* All nodes involved in edges (and thus will need a port). */
554 : std::set<const digraphs::node *> m_src_nodes;
555 : std::set<const digraphs::node *> m_dst_nodes;
556 :
557 : std::map<const digraphs::node *, dot::node_id> m_src_node_to_port_id;
558 : std::map<const digraphs::node *, dot::node_id> m_dst_node_to_port_id;
559 : };
560 :
561 : std::unique_ptr<dot::graph>
562 1 : state_graphs::
563 : make_dot_graph (const digraphs::digraph &state_graph,
564 : const logical_locations::manager &logical_loc_mgr)
565 : {
566 1 : return std::make_unique<state_diagram> (state_graph, logical_loc_mgr);
567 : }
|
