Branch data Line data Source code
1 : : /* Directed graphs associated with a diagnostic.
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 "graphviz.h"
31 : : #include "diagnostics/digraphs.h"
32 : : #include "diagnostics/sarif-sink.h"
33 : : #include "custom-sarif-properties/digraphs.h"
34 : :
35 : : using digraph_object = diagnostics::digraphs::object;
36 : : using digraph = diagnostics::digraphs::digraph;
37 : : using digraph_node = diagnostics::digraphs::node;
38 : : using digraph_edge = diagnostics::digraphs::edge;
39 : :
40 : : namespace properties = custom_sarif_properties::digraphs;
41 : :
42 : : namespace {
43 : :
44 : 11 : class conversion_to_dot
45 : : {
46 : : public:
47 : : std::unique_ptr<dot::graph>
48 : : make_dot_graph_from_diagnostic_graph (const digraph &);
49 : :
50 : : std::unique_ptr<dot::stmt>
51 : : make_dot_node_from_digraph_node (const digraph_node &);
52 : :
53 : : std::unique_ptr<dot::edge_stmt>
54 : : make_dot_edge_from_digraph_edge (const digraph_edge &);
55 : :
56 : : dot::id
57 : : get_dot_id_for_node (const digraph_node &);
58 : :
59 : : bool
60 : : has_edges_p (const digraph_node &);
61 : :
62 : : private:
63 : : std::set<const digraph_node *> m_nodes_with_edges;
64 : : std::map<const digraph_node *, dot::stmt *> m_node_map;
65 : : };
66 : :
67 : : } // anonymous namespace
68 : :
69 : : // class conversion_to_dot
70 : :
71 : : std::unique_ptr<dot::graph>
72 : 11 : conversion_to_dot::
73 : : make_dot_graph_from_diagnostic_graph (const diagnostics::digraphs::digraph &input_graph)
74 : : {
75 : 11 : auto output_graph = std::make_unique<dot::graph> ();
76 : :
77 : 11 : if (const char *description = input_graph.get_description ())
78 : 14 : output_graph->m_stmt_list.add_attr (dot::id ("label"),
79 : 14 : dot::id (description));
80 : :
81 : 11 : const int num_nodes = input_graph.get_num_nodes ();
82 : 11 : const int num_edges = input_graph.get_num_edges ();
83 : :
84 : : /* Determine which nodes have in-edges and out-edges. */
85 : 405 : for (int i = 0; i < num_edges; ++i)
86 : : {
87 : 394 : const digraph_edge &input_edge = input_graph.get_edge (i);
88 : 394 : m_nodes_with_edges.insert (&input_edge.get_src_node ());
89 : 394 : m_nodes_with_edges.insert (&input_edge.get_dst_node ());
90 : : }
91 : :
92 : 28 : for (int i = 0; i < num_nodes; ++i)
93 : : {
94 : 17 : const digraph_node &input_node = input_graph.get_node (i);
95 : 17 : auto dot_node_stmt = make_dot_node_from_digraph_node (input_node);
96 : 17 : output_graph->m_stmt_list.add_stmt (std::move (dot_node_stmt));
97 : 17 : }
98 : :
99 : 405 : for (int i = 0; i < num_edges; ++i)
100 : : {
101 : 394 : const digraph_edge &input_edge = input_graph.get_edge (i);
102 : 394 : auto dot_edge_stmt = make_dot_edge_from_digraph_edge (input_edge);
103 : 394 : output_graph->m_stmt_list.add_stmt (std::move (dot_edge_stmt));
104 : 394 : }
105 : :
106 : 11 : return output_graph;
107 : : }
108 : :
109 : : std::unique_ptr<dot::stmt>
110 : 416 : conversion_to_dot::
111 : : make_dot_node_from_digraph_node (const diagnostics::digraphs::node &input_node)
112 : : {
113 : 416 : dot::id dot_id (get_dot_id_for_node (input_node));
114 : :
115 : : /* For now, we can only do either edges or children, not both
116 : : ...but see https://graphviz.org/docs/attrs/compound/ */
117 : :
118 : 416 : if (has_edges_p (input_node))
119 : : {
120 : 405 : auto output_node
121 : 405 : = std::make_unique<dot::node_stmt> (std::move (dot_id));
122 : 405 : m_node_map[&input_node] = output_node.get ();
123 : 405 : if (const char *label = input_node.get_label ())
124 : 399 : output_node->set_label (dot::id (label));
125 : 405 : return output_node;
126 : 405 : }
127 : : else
128 : : {
129 : 11 : auto output_node = std::make_unique<dot::subgraph> (std::move (dot_id));
130 : 11 : m_node_map[&input_node] = output_node.get ();
131 : 11 : if (const char *label = input_node.get_label ())
132 : 5 : output_node->add_attr (dot::id ("label"), dot::id (label));
133 : 11 : const int num_children = input_node.get_num_children ();
134 : 410 : for (int i = 0; i < num_children; ++i)
135 : : {
136 : 399 : const digraph_node &input_child = input_node.get_child (i);
137 : 399 : auto dot_child_stmt = make_dot_node_from_digraph_node (input_child);
138 : 399 : output_node->m_stmt_list.add_stmt (std::move (dot_child_stmt));
139 : 399 : }
140 : 11 : return output_node;
141 : 11 : }
142 : 416 : }
143 : :
144 : : std::unique_ptr<dot::edge_stmt>
145 : 394 : conversion_to_dot::
146 : : make_dot_edge_from_digraph_edge (const digraph_edge &input_edge)
147 : : {
148 : 394 : const digraph_node &src_dnode = input_edge.get_src_node ();
149 : 394 : const digraph_node &dst_dnode = input_edge.get_dst_node ();
150 : 394 : auto output_edge
151 : : = std::make_unique<dot::edge_stmt>
152 : 788 : (get_dot_id_for_node (src_dnode),
153 : 788 : get_dot_id_for_node (dst_dnode));
154 : 394 : if (const char *label = input_edge.get_label ())
155 : 394 : output_edge->set_label (dot::id (label));
156 : 394 : return output_edge;
157 : : }
158 : :
159 : : dot::id
160 : 1204 : conversion_to_dot::get_dot_id_for_node (const digraph_node &input_node)
161 : : {
162 : 1204 : if (has_edges_p (input_node))
163 : 2386 : return input_node.get_id ();
164 : : else
165 : 22 : return std::string ("cluster_") + input_node.get_id ();
166 : : }
167 : :
168 : : bool
169 : 1620 : conversion_to_dot::has_edges_p (const digraph_node &input_node)
170 : : {
171 : 1620 : return m_nodes_with_edges.find (&input_node) != m_nodes_with_edges.end ();
172 : : }
173 : :
174 : : // class object
175 : :
176 : : /* String properties. */
177 : :
178 : : const char *
179 : 32 : digraph_object::get_property (const json::string_property &property) const
180 : : {
181 : 32 : if (!m_property_bag)
182 : : return nullptr;
183 : 32 : if (json::value *jv = m_property_bag->get (property.m_key.get ()))
184 : 21 : if (json::string *jstr = jv->dyn_cast_string ())
185 : 21 : return jstr->get_string ();
186 : : return nullptr;
187 : : }
188 : :
189 : : void
190 : 1167 : digraph_object::set_property (const json::string_property &property,
191 : : const char *utf8_value)
192 : : {
193 : 1167 : auto &bag = ensure_property_bag ();
194 : 1167 : bag.set_string (property.m_key.get (), utf8_value);
195 : 1167 : }
196 : :
197 : : /* Integer properties. */
198 : :
199 : : bool
200 : 0 : digraph_object::maybe_get_property (const json::integer_property &property,
201 : : long &out_value) const
202 : : {
203 : 0 : if (!m_property_bag)
204 : : return false;
205 : 0 : if (json::value *jv = m_property_bag->get (property.m_key.get ()))
206 : 0 : if (json::integer_number *jnum = jv->dyn_cast_integer_number ())
207 : : {
208 : 0 : out_value = jnum->get ();
209 : 0 : return true;
210 : : }
211 : : return false;
212 : : }
213 : :
214 : : void
215 : 0 : digraph_object::set_property (const json::integer_property &property, long value)
216 : : {
217 : 0 : auto &bag = ensure_property_bag ();
218 : 0 : bag.set_integer (property.m_key.get (), value);
219 : 0 : }
220 : :
221 : : /* Bool properties. */
222 : : void
223 : 0 : digraph_object::set_property (const json::bool_property &property, bool value)
224 : : {
225 : 0 : auto &bag = ensure_property_bag ();
226 : 0 : bag.set_bool (property.m_key.get (), value);
227 : 0 : }
228 : :
229 : : tristate
230 : 0 : digraph_object::
231 : : get_property_as_tristate (const json::bool_property &property) const
232 : : {
233 : 0 : if (m_property_bag)
234 : : {
235 : 0 : if (json::value *jv = m_property_bag->get (property.m_key.get ()))
236 : 0 : switch (jv->get_kind ())
237 : : {
238 : : default:
239 : : break;
240 : 0 : case json::JSON_TRUE:
241 : 0 : return tristate (true);
242 : 0 : case json::JSON_FALSE:
243 : 0 : return tristate (false);
244 : : }
245 : : }
246 : 0 : return tristate::unknown ();
247 : : }
248 : :
249 : : /* Array-of-string properties. */
250 : : json::array *
251 : 0 : digraph_object::get_property (const json::array_of_string_property &property) const
252 : : {
253 : 0 : if (m_property_bag)
254 : 0 : if (json::value *jv = m_property_bag->get (property.m_key.get ()))
255 : 0 : if (json::array *arr = jv->dyn_cast_array ())
256 : : return arr;
257 : : return nullptr;
258 : : }
259 : :
260 : : /* json::value properties. */
261 : : const json::value *
262 : 0 : digraph_object::get_property (const json::json_property &property) const
263 : : {
264 : 0 : if (m_property_bag)
265 : 0 : return m_property_bag->get (property.m_key.get ());
266 : : return nullptr;
267 : : }
268 : :
269 : : void
270 : 250 : digraph_object::set_property (const json::json_property &property,
271 : : std::unique_ptr<json::value> value)
272 : : {
273 : 250 : auto &bag = ensure_property_bag ();
274 : 250 : bag.set (property.m_key.get (), std::move (value));
275 : 250 : }
276 : :
277 : : json::object &
278 : 2011 : digraph_object::ensure_property_bag ()
279 : : {
280 : 2011 : if (!m_property_bag)
281 : 589 : m_property_bag = std::make_unique<sarif_property_bag> ( );
282 : 2011 : return *m_property_bag;
283 : : }
284 : :
285 : : // class digraph
286 : :
287 : : DEBUG_FUNCTION void
288 : 0 : digraph::dump () const
289 : : {
290 : 0 : make_json_sarif_graph ()->dump ();
291 : 0 : }
292 : :
293 : : std::unique_ptr<json::object>
294 : 8 : digraph::make_json_sarif_graph () const
295 : : {
296 : 8 : return make_sarif_graph (*this, nullptr, nullptr);
297 : : }
298 : :
299 : : std::unique_ptr<dot::graph>
300 : 11 : digraph::make_dot_graph () const
301 : : {
302 : 11 : conversion_to_dot converter;
303 : 11 : return converter.make_dot_graph_from_diagnostic_graph (*this);
304 : 11 : }
305 : :
306 : : std::unique_ptr<digraph>
307 : 0 : digraph::clone () const
308 : : {
309 : 0 : auto result = std::make_unique<diagnostics::digraphs::digraph> ();
310 : :
311 : 0 : if (get_property_bag ())
312 : 0 : result->set_property_bag (get_property_bag ()->clone_as_object ());
313 : :
314 : 0 : std::map<digraph_node *, digraph_node *> node_mapping;
315 : :
316 : 0 : for (auto &iter : m_nodes)
317 : 0 : result->add_node (iter->clone (*result, node_mapping));
318 : 0 : for (auto &iter : m_edges)
319 : 0 : result->add_edge (iter->clone (*result, node_mapping));
320 : :
321 : 0 : return result;
322 : 0 : }
323 : :
324 : : void
325 : 823 : digraph::add_edge (const char *id,
326 : : node &src_node,
327 : : node &dst_node,
328 : : const char *label)
329 : : {
330 : 823 : auto e = std::make_unique<digraph_edge> (*this,
331 : : id,
332 : : src_node,
333 : 823 : dst_node);
334 : 823 : if (label)
335 : 776 : e->set_label (label);
336 : 823 : add_edge (std::move (e));
337 : 823 : }
338 : :
339 : : /* Utility function for edge ids: either use EDGE_ID, or
340 : : generate a unique one for when we don't care about the name.
341 : :
342 : : Edges in SARIF "SHALL" have an id that's unique within the graph
343 : : (SARIF 2.1.0 §3.41.2). This is so that graph traversals can refer
344 : : to edges by id (SARIF 2.1.0's §3.43.2 edgeId property). */
345 : :
346 : : std::string
347 : 831 : digraph::make_edge_id (const char *edge_id)
348 : : {
349 : : /* If we have an id, use it. */
350 : 831 : if (edge_id)
351 : 4 : return edge_id;
352 : :
353 : : /* Otherwise, generate a unique one of the form "edgeN". */
354 : 827 : while (true)
355 : : {
356 : 1654 : auto candidate (std::string ("edge")
357 : 827 : + std::to_string (m_next_edge_id_index++));
358 : 827 : auto iter = m_id_to_edge_map.find (candidate);
359 : 827 : if (iter != m_id_to_edge_map.end ())
360 : : {
361 : : // Try again with the next index...
362 : 0 : continue;
363 : : }
364 : 827 : return candidate;
365 : 827 : }
366 : : }
367 : :
368 : : const char *
369 : 0 : digraph::get_graph_kind () const
370 : : {
371 : 0 : return get_property (properties::digraph::kind);
372 : : }
373 : :
374 : : void
375 : 0 : digraph::set_graph_kind (const char *kind)
376 : : {
377 : 0 : set_property (properties::digraph::kind, kind);
378 : 0 : }
379 : :
380 : : // class node
381 : :
382 : : DEBUG_FUNCTION void
383 : 0 : digraph_node::dump () const
384 : : {
385 : 0 : to_json_sarif_node ()->dump ();
386 : 0 : }
387 : :
388 : : std::unique_ptr<json::object>
389 : 0 : digraph_node::to_json_sarif_node () const
390 : : {
391 : 0 : return make_sarif_node (*this, nullptr, nullptr);
392 : : }
393 : :
394 : : std::unique_ptr<digraph_node>
395 : 0 : digraph_node::clone (digraph &new_graph,
396 : : std::map<node *, node *> &node_mapping) const
397 : : {
398 : 0 : auto result
399 : 0 : = std::make_unique<digraph_node> (new_graph, get_id ());
400 : 0 : node_mapping.insert ({const_cast <node *> (this), result.get ()});
401 : :
402 : 0 : result->set_logical_loc (m_logical_loc);
403 : :
404 : 0 : if (get_property_bag ())
405 : 0 : result->set_property_bag (get_property_bag ()->clone_as_object ());
406 : :
407 : 0 : for (auto &iter : m_children)
408 : 0 : result->add_child (iter->clone (new_graph, node_mapping));
409 : :
410 : 0 : return result;
411 : : }
412 : :
413 : : // class edge
414 : :
415 : : std::unique_ptr<digraph_edge>
416 : 0 : digraph_edge::clone (digraph &new_graph,
417 : : const std::map<node *, node *> &node_mapping) const
418 : : {
419 : 0 : auto iter_new_src = node_mapping.find (&m_src_node);
420 : 0 : gcc_assert (iter_new_src != node_mapping.end ());
421 : 0 : auto iter_new_dst = node_mapping.find (&m_dst_node);
422 : 0 : gcc_assert (iter_new_dst != node_mapping.end ());
423 : 0 : auto result
424 : : = std::make_unique<digraph_edge> (new_graph,
425 : 0 : m_id.c_str (),
426 : 0 : *iter_new_src->second,
427 : 0 : *iter_new_dst->second);
428 : 0 : if (get_property_bag ())
429 : 0 : result->set_property_bag (get_property_bag ()->clone_as_object ());
430 : :
431 : 0 : return result;
432 : : }
433 : :
434 : : DEBUG_FUNCTION void
435 : 0 : diagnostics::digraphs::edge::dump () const
436 : : {
437 : 0 : to_json_sarif_edge ()->dump ();
438 : 0 : }
439 : :
440 : : std::unique_ptr<json::object>
441 : 0 : diagnostics::digraphs::edge::to_json_sarif_edge () const
442 : : {
443 : 0 : return make_sarif_edge (*this, nullptr);
444 : : }
445 : :
446 : : #if CHECKING_P
447 : :
448 : : #include "selftest.h"
449 : : #include "custom-sarif-properties/state-graphs.h"
450 : :
451 : : namespace diagnostics {
452 : : namespace selftest {
453 : :
454 : : static void
455 : 4 : test_empty_graph ()
456 : : {
457 : 4 : digraph g;
458 : :
459 : 4 : {
460 : 4 : auto sarif = g.make_json_sarif_graph ();
461 : :
462 : 4 : pretty_printer pp;
463 : 4 : sarif->print (&pp, true);
464 : 4 : ASSERT_STREQ
465 : : (pp_formatted_text (&pp),
466 : : ("{\"nodes\": [],\n"
467 : : " \"edges\": []}"));
468 : 4 : }
469 : :
470 : 4 : {
471 : 4 : auto dg = g.make_dot_graph ();
472 : :
473 : 4 : pretty_printer pp;
474 : 4 : dot::writer w (pp);
475 : 4 : dg->print (w);
476 : 4 : ASSERT_STREQ
477 : : (pp_formatted_text (&pp),
478 : : ("digraph {\n"
479 : : "}\n"));
480 : 4 : }
481 : 4 : }
482 : :
483 : : static void
484 : 4 : test_simple_graph ()
485 : : {
486 : : #define KEY_PREFIX "/placeholder/"
487 : 4 : auto g = std::make_unique<digraph> ();
488 : 4 : g->set_description ("test graph");
489 : 4 : g->set_property (json::string_property (KEY_PREFIX, "date"), "1066");
490 : :
491 : 4 : auto a = std::make_unique<digraph_node> (*g, "a");
492 : 4 : auto b = std::make_unique<digraph_node> (*g, "b");
493 : 4 : b->set_property (json::string_property (KEY_PREFIX, "color"), "red");
494 : 4 : auto c = std::make_unique<digraph_node> (*g, "c");
495 : 4 : c->set_label ("I am a node label");
496 : :
497 : 4 : auto e = std::make_unique<digraph_edge> (*g, nullptr, *a, *c);
498 : 4 : e->set_property (json::string_property (KEY_PREFIX, "status"),
499 : : "copacetic");
500 : 4 : e->set_label ("I am an edge label");
501 : 4 : g->add_edge (std::move (e));
502 : :
503 : 4 : g->add_node (std::move (a));
504 : :
505 : 4 : b->add_child (std::move (c));
506 : 4 : g->add_node (std::move (b));
507 : : #undef KEY_PREFIX
508 : :
509 : 4 : {
510 : 4 : auto sarif = g->make_json_sarif_graph ();
511 : :
512 : 4 : pretty_printer pp;
513 : 4 : sarif->print (&pp, true);
514 : 4 : ASSERT_STREQ
515 : : (pp_formatted_text (&pp),
516 : : ("{\"properties\": {\"/placeholder/date\": \"1066\"},\n"
517 : : " \"nodes\": [{\"id\": \"a\"},\n"
518 : : " {\"id\": \"b\",\n"
519 : : " \"properties\": {\"/placeholder/color\": \"red\"},\n"
520 : : " \"children\": [{\"id\": \"c\"}]}],\n"
521 : : " \"edges\": [{\"id\": \"edge0\",\n"
522 : : " \"properties\": {\"/placeholder/status\": \"copacetic\"},\n"
523 : : " \"sourceNodeId\": \"a\",\n"
524 : : " \"targetNodeId\": \"c\"}]}"));
525 : 4 : }
526 : :
527 : 4 : {
528 : 4 : auto dg = g->make_dot_graph ();
529 : :
530 : 4 : pretty_printer pp;
531 : 4 : dot::writer w (pp);
532 : 4 : dg->print (w);
533 : 4 : ASSERT_STREQ
534 : : (pp_formatted_text (&pp),
535 : : ("digraph {\n"
536 : : " label=\"test graph\";\n"
537 : : " a;\n"
538 : : " \n"
539 : : " subgraph cluster_b {\n"
540 : : " c [label=\"I am a node label\"];\n"
541 : : "\n"
542 : : " };\n"
543 : : " a -> c [label=\"I am an edge label\"];\n"
544 : : "}\n"));
545 : 4 : }
546 : 4 : }
547 : :
548 : : static void
549 : 4 : test_property_objects ()
550 : : {
551 : 4 : namespace state_node_properties = custom_sarif_properties::state_graphs::node;
552 : :
553 : 4 : digraph g;
554 : 4 : digraph_node node (g, "a");
555 : :
556 : 4 : ASSERT_EQ (node.get_property (state_node_properties::kind_prop),
557 : : state_node_properties::kind_t::other);
558 : 4 : node.set_property (state_node_properties::kind_prop,
559 : : state_node_properties::kind_t::stack);
560 : 4 : ASSERT_EQ (node.get_property (state_node_properties::kind_prop),
561 : : state_node_properties::kind_t::stack);
562 : :
563 : 4 : ASSERT_EQ (node.get_property (state_node_properties::dynalloc_state_prop),
564 : : state_node_properties::dynalloc_state_t::unknown);
565 : 4 : node.set_property (state_node_properties::dynalloc_state_prop,
566 : : state_node_properties::dynalloc_state_t::freed);
567 : 4 : ASSERT_EQ (node.get_property (state_node_properties::dynalloc_state_prop),
568 : : state_node_properties::dynalloc_state_t::freed);
569 : :
570 : 4 : ASSERT_EQ (node.get_property (state_node_properties::type), nullptr);
571 : 4 : node.set_property (state_node_properties::type, "const char *");
572 : 4 : ASSERT_STREQ (node.get_property (state_node_properties::type),
573 : : "const char *");
574 : 4 : }
575 : :
576 : : /* Run all of the selftests within this file. */
577 : :
578 : : void
579 : 4 : digraphs_cc_tests ()
580 : : {
581 : 4 : test_empty_graph ();
582 : 4 : test_simple_graph ();
583 : 4 : test_property_objects ();
584 : 4 : }
585 : :
586 : : } // namespace diagnostics::selftest
587 : : } // namespace diagnostics
588 : :
589 : : #endif /* CHECKING_P */
|
