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 : :
34 : : #include "selftest.h"
35 : :
36 : : using digraph = diagnostics::digraphs::digraph;
37 : : using digraph_node = diagnostics::digraphs::node;
38 : : using digraph_edge = diagnostics::digraphs::edge;
39 : :
40 : : namespace {
41 : :
42 : 11 : class conversion_to_dot
43 : : {
44 : : public:
45 : : std::unique_ptr<dot::graph>
46 : : make_dot_graph_from_diagnostic_graph (const digraph &);
47 : :
48 : : std::unique_ptr<dot::stmt>
49 : : make_dot_node_from_digraph_node (const digraph_node &);
50 : :
51 : : std::unique_ptr<dot::edge_stmt>
52 : : make_dot_edge_from_digraph_edge (const digraph_edge &);
53 : :
54 : : dot::id
55 : : get_dot_id_for_node (const digraph_node &);
56 : :
57 : : bool
58 : : has_edges_p (const digraph_node &);
59 : :
60 : : private:
61 : : std::set<const digraph_node *> m_nodes_with_edges;
62 : : std::map<const digraph_node *, dot::stmt *> m_node_map;
63 : : };
64 : :
65 : : } // anonymous namespace
66 : :
67 : : // class conversion_to_dot
68 : :
69 : : std::unique_ptr<dot::graph>
70 : 11 : conversion_to_dot::
71 : : make_dot_graph_from_diagnostic_graph (const diagnostics::digraphs::digraph &input_graph)
72 : : {
73 : 11 : auto output_graph = std::make_unique<dot::graph> ();
74 : :
75 : 11 : if (const char *description = input_graph.get_description ())
76 : 14 : output_graph->m_stmt_list.add_attr (dot::id ("label"),
77 : 14 : dot::id (description));
78 : :
79 : 11 : const int num_nodes = input_graph.get_num_nodes ();
80 : 11 : const int num_edges = input_graph.get_num_edges ();
81 : :
82 : : /* Determine which nodes have in-edges and out-edges. */
83 : 406 : for (int i = 0; i < num_edges; ++i)
84 : : {
85 : 395 : const digraph_edge &input_edge = input_graph.get_edge (i);
86 : 395 : m_nodes_with_edges.insert (&input_edge.get_src_node ());
87 : 395 : m_nodes_with_edges.insert (&input_edge.get_dst_node ());
88 : : }
89 : :
90 : 28 : for (int i = 0; i < num_nodes; ++i)
91 : : {
92 : 17 : const digraph_node &input_node = input_graph.get_node (i);
93 : 17 : auto dot_node_stmt = make_dot_node_from_digraph_node (input_node);
94 : 17 : output_graph->m_stmt_list.add_stmt (std::move (dot_node_stmt));
95 : 17 : }
96 : :
97 : 406 : for (int i = 0; i < num_edges; ++i)
98 : : {
99 : 395 : const digraph_edge &input_edge = input_graph.get_edge (i);
100 : 395 : auto dot_edge_stmt = make_dot_edge_from_digraph_edge (input_edge);
101 : 395 : output_graph->m_stmt_list.add_stmt (std::move (dot_edge_stmt));
102 : 395 : }
103 : :
104 : 11 : return output_graph;
105 : : }
106 : :
107 : : std::unique_ptr<dot::stmt>
108 : 417 : conversion_to_dot::
109 : : make_dot_node_from_digraph_node (const diagnostics::digraphs::node &input_node)
110 : : {
111 : 417 : dot::id dot_id (get_dot_id_for_node (input_node));
112 : :
113 : : /* For now, we can only do either edges or children, not both
114 : : ...but see https://graphviz.org/docs/attrs/compound/ */
115 : :
116 : 417 : if (has_edges_p (input_node))
117 : : {
118 : 406 : auto output_node
119 : 406 : = std::make_unique<dot::node_stmt> (std::move (dot_id));
120 : 406 : m_node_map[&input_node] = output_node.get ();
121 : 406 : if (const char *label = input_node.get_label ())
122 : 400 : output_node->set_label (dot::id (label));
123 : 406 : return output_node;
124 : 406 : }
125 : : else
126 : : {
127 : 11 : auto output_node = std::make_unique<dot::subgraph> (std::move (dot_id));
128 : 11 : m_node_map[&input_node] = output_node.get ();
129 : 11 : if (const char *label = input_node.get_label ())
130 : 5 : output_node->add_attr (dot::id ("label"), dot::id (label));
131 : 11 : const int num_children = input_node.get_num_children ();
132 : 411 : for (int i = 0; i < num_children; ++i)
133 : : {
134 : 400 : const digraph_node &input_child = input_node.get_child (i);
135 : 400 : auto dot_child_stmt = make_dot_node_from_digraph_node (input_child);
136 : 400 : output_node->m_stmt_list.add_stmt (std::move (dot_child_stmt));
137 : 400 : }
138 : 11 : return output_node;
139 : 11 : }
140 : 417 : }
141 : :
142 : : std::unique_ptr<dot::edge_stmt>
143 : 395 : conversion_to_dot::
144 : : make_dot_edge_from_digraph_edge (const digraph_edge &input_edge)
145 : : {
146 : 395 : const digraph_node &src_dnode = input_edge.get_src_node ();
147 : 395 : const digraph_node &dst_dnode = input_edge.get_dst_node ();
148 : 395 : auto output_edge
149 : : = std::make_unique<dot::edge_stmt>
150 : 790 : (get_dot_id_for_node (src_dnode),
151 : 790 : get_dot_id_for_node (dst_dnode));
152 : 395 : if (const char *label = input_edge.get_label ())
153 : 395 : output_edge->set_label (dot::id (label));
154 : 395 : return output_edge;
155 : : }
156 : :
157 : : dot::id
158 : 1207 : conversion_to_dot::get_dot_id_for_node (const digraph_node &input_node)
159 : : {
160 : 1207 : if (has_edges_p (input_node))
161 : 2392 : return input_node.get_id ();
162 : : else
163 : 22 : return std::string ("cluster_") + input_node.get_id ();
164 : : }
165 : :
166 : : bool
167 : 1624 : conversion_to_dot::has_edges_p (const digraph_node &input_node)
168 : : {
169 : 1624 : return m_nodes_with_edges.find (&input_node) != m_nodes_with_edges.end ();
170 : : }
171 : :
172 : : // class object
173 : :
174 : : const char *
175 : 60 : diagnostics::digraphs::object::
176 : : get_attr (const char *key_prefix, const char *key) const
177 : : {
178 : 60 : if (!m_property_bag)
179 : : return nullptr;
180 : 112 : std::string prefixed_key = std::string (key_prefix) + key;
181 : 56 : if (json::value *jv = m_property_bag->get (prefixed_key.c_str ()))
182 : 41 : if (json::string *jstr = jv->dyn_cast_string ())
183 : 41 : return jstr->get_string ();
184 : : return nullptr;
185 : 56 : }
186 : :
187 : : void
188 : 1636 : diagnostics::digraphs::object::
189 : : set_attr (const char *key_prefix, const char *key, const char *value)
190 : : {
191 : 1636 : set_json_attr (key_prefix, key, std::make_unique<json::string> (value));
192 : 1636 : }
193 : :
194 : : void
195 : 1761 : diagnostics::digraphs::object::
196 : : set_json_attr (const char *key_prefix, const char *key, std::unique_ptr<json::value> value)
197 : : {
198 : 3522 : std::string prefixed_key = std::string (key_prefix) + key;
199 : 1761 : if (!m_property_bag)
200 : 589 : m_property_bag = std::make_unique<json::object> ();
201 : 1761 : m_property_bag->set (prefixed_key.c_str (), std::move (value));
202 : 1761 : }
203 : :
204 : : // class digraph
205 : :
206 : : DEBUG_FUNCTION void
207 : 0 : diagnostics::digraphs::digraph::dump () const
208 : : {
209 : 0 : make_json_sarif_graph ()->dump ();
210 : 0 : }
211 : :
212 : : std::unique_ptr<json::object>
213 : 8 : diagnostics::digraphs::digraph::make_json_sarif_graph () const
214 : : {
215 : 8 : return make_sarif_graph (*this, nullptr, nullptr);
216 : : }
217 : :
218 : : std::unique_ptr<dot::graph>
219 : 11 : diagnostics::digraphs::digraph::make_dot_graph () const
220 : : {
221 : 11 : conversion_to_dot to_dot;
222 : 11 : return to_dot.make_dot_graph_from_diagnostic_graph (*this);
223 : 11 : }
224 : :
225 : : std::unique_ptr<diagnostics::digraphs::digraph>
226 : 0 : diagnostics::digraphs::digraph::clone () const
227 : : {
228 : 0 : auto result = std::make_unique<diagnostics::digraphs::digraph> ();
229 : :
230 : 0 : if (get_property_bag ())
231 : 0 : result->set_property_bag (get_property_bag ()->clone_as_object ());
232 : :
233 : 0 : std::map<diagnostics::digraphs::node *, diagnostics::digraphs::node *> node_mapping;
234 : :
235 : 0 : for (auto &iter : m_nodes)
236 : 0 : result->add_node (iter->clone (*result, node_mapping));
237 : 0 : for (auto &iter : m_edges)
238 : 0 : result->add_edge (iter->clone (*result, node_mapping));
239 : :
240 : 0 : return result;
241 : 0 : }
242 : :
243 : : void
244 : 825 : diagnostics::digraphs::digraph::add_edge (const char *id,
245 : : node &src_node,
246 : : node &dst_node,
247 : : const char *label)
248 : : {
249 : 825 : auto e = std::make_unique<digraph_edge> (*this,
250 : : id,
251 : : src_node,
252 : 825 : dst_node);
253 : 825 : if (label)
254 : 778 : e->set_label (label);
255 : 825 : add_edge (std::move (e));
256 : 825 : }
257 : :
258 : : /* Utility function for edge ids: either use EDGE_ID, or
259 : : generate a unique one for when we don't care about the name.
260 : :
261 : : Edges in SARIF "SHALL" have an id that's unique within the graph
262 : : (SARIF 2.1.0 §3.41.2). This is so that graph traversals can refer
263 : : to edges by id (SARIF 2.1.0's §3.43.2 edgeId property). */
264 : :
265 : : std::string
266 : 833 : diagnostics::digraphs::digraph::make_edge_id (const char *edge_id)
267 : : {
268 : : /* If we have an id, use it. */
269 : 833 : if (edge_id)
270 : 4 : return edge_id;
271 : :
272 : : /* Otherwise, generate a unique one of the form "edgeN". */
273 : 829 : while (true)
274 : : {
275 : 1658 : auto candidate (std::string ("edge")
276 : 829 : + std::to_string (m_next_edge_id_index++));
277 : 829 : auto iter = m_id_to_edge_map.find (candidate);
278 : 829 : if (iter != m_id_to_edge_map.end ())
279 : : {
280 : : // Try again with the next index...
281 : 0 : continue;
282 : : }
283 : 829 : return candidate;
284 : 829 : }
285 : : }
286 : :
287 : : // class node
288 : :
289 : : DEBUG_FUNCTION void
290 : 0 : diagnostics::digraphs::node::dump () const
291 : : {
292 : 0 : to_json_sarif_node ()->dump ();
293 : 0 : }
294 : :
295 : : std::unique_ptr<json::object>
296 : 0 : diagnostics::digraphs::node::to_json_sarif_node () const
297 : : {
298 : 0 : return make_sarif_node (*this, nullptr, nullptr);
299 : : }
300 : :
301 : : std::unique_ptr<diagnostics::digraphs::node>
302 : 0 : diagnostics::digraphs::node::clone (digraph &new_graph,
303 : : std::map<node *, node *> &node_mapping) const
304 : : {
305 : 0 : auto result
306 : : = std::make_unique<diagnostics::digraphs::node> (new_graph,
307 : 0 : get_id ());
308 : 0 : node_mapping.insert ({const_cast <node *> (this), result.get ()});
309 : :
310 : 0 : result->set_logical_loc (m_logical_loc);
311 : :
312 : 0 : if (get_property_bag ())
313 : 0 : result->set_property_bag (get_property_bag ()->clone_as_object ());
314 : :
315 : 0 : for (auto &iter : m_children)
316 : 0 : result->add_child (iter->clone (new_graph, node_mapping));
317 : :
318 : 0 : return result;
319 : : }
320 : :
321 : : // class edge
322 : :
323 : : std::unique_ptr<digraph_edge>
324 : 0 : digraph_edge::clone (digraph &new_graph,
325 : : const std::map<node *, node *> &node_mapping) const
326 : : {
327 : 0 : auto iter_new_src = node_mapping.find (&m_src_node);
328 : 0 : gcc_assert (iter_new_src != node_mapping.end ());
329 : 0 : auto iter_new_dst = node_mapping.find (&m_dst_node);
330 : 0 : gcc_assert (iter_new_dst != node_mapping.end ());
331 : 0 : auto result
332 : : = std::make_unique<digraph_edge> (new_graph,
333 : 0 : m_id.c_str (),
334 : 0 : *iter_new_src->second,
335 : 0 : *iter_new_dst->second);
336 : 0 : if (get_property_bag ())
337 : 0 : result->set_property_bag (get_property_bag ()->clone_as_object ());
338 : :
339 : 0 : return result;
340 : : }
341 : :
342 : : DEBUG_FUNCTION void
343 : 0 : diagnostics::digraphs::edge::dump () const
344 : : {
345 : 0 : to_json_sarif_edge ()->dump ();
346 : 0 : }
347 : :
348 : : std::unique_ptr<json::object>
349 : 0 : diagnostics::digraphs::edge::to_json_sarif_edge () const
350 : : {
351 : 0 : return make_sarif_edge (*this, nullptr);
352 : : }
353 : :
354 : : #if CHECKING_P
355 : :
356 : : namespace diagnostics {
357 : : namespace selftest {
358 : :
359 : : static void
360 : 4 : test_empty_graph ()
361 : : {
362 : 4 : digraph g;
363 : :
364 : 4 : {
365 : 4 : auto sarif = g.make_json_sarif_graph ();
366 : :
367 : 4 : pretty_printer pp;
368 : 4 : sarif->print (&pp, true);
369 : 4 : ASSERT_STREQ
370 : : (pp_formatted_text (&pp),
371 : : ("{\"nodes\": [],\n"
372 : : " \"edges\": []}"));
373 : 4 : }
374 : :
375 : 4 : {
376 : 4 : auto dg = g.make_dot_graph ();
377 : :
378 : 4 : pretty_printer pp;
379 : 4 : dot::writer w (pp);
380 : 4 : dg->print (w);
381 : 4 : ASSERT_STREQ
382 : : (pp_formatted_text (&pp),
383 : : ("digraph {\n"
384 : : "}\n"));
385 : 4 : }
386 : 4 : }
387 : :
388 : : static void
389 : 4 : test_simple_graph ()
390 : : {
391 : : #define KEY_PREFIX "/placeholder/"
392 : 4 : auto g = std::make_unique<digraph> ();
393 : 4 : g->set_description ("test graph");
394 : 4 : g->set_attr (KEY_PREFIX, "date", "1066");
395 : :
396 : 4 : auto a = std::make_unique<digraph_node> (*g, "a");
397 : 4 : auto b = std::make_unique<digraph_node> (*g, "b");
398 : 4 : b->set_attr (KEY_PREFIX, "color", "red");
399 : 4 : auto c = std::make_unique<digraph_node> (*g, "c");
400 : 4 : c->set_label ("I am a node label");
401 : :
402 : 4 : auto e = std::make_unique<digraph_edge> (*g, nullptr, *a, *c);
403 : 4 : e->set_attr (KEY_PREFIX, "status", "copacetic");
404 : 4 : e->set_label ("I am an edge label");
405 : 4 : g->add_edge (std::move (e));
406 : :
407 : 4 : g->add_node (std::move (a));
408 : :
409 : 4 : b->add_child (std::move (c));
410 : 4 : g->add_node (std::move (b));
411 : : #undef KEY_PREFIX
412 : :
413 : 4 : {
414 : 4 : auto sarif = g->make_json_sarif_graph ();
415 : :
416 : 4 : pretty_printer pp;
417 : 4 : sarif->print (&pp, true);
418 : 4 : ASSERT_STREQ
419 : : (pp_formatted_text (&pp),
420 : : ("{\"properties\": {\"/placeholder/date\": \"1066\"},\n"
421 : : " \"nodes\": [{\"id\": \"a\"},\n"
422 : : " {\"id\": \"b\",\n"
423 : : " \"properties\": {\"/placeholder/color\": \"red\"},\n"
424 : : " \"children\": [{\"id\": \"c\"}]}],\n"
425 : : " \"edges\": [{\"id\": \"edge0\",\n"
426 : : " \"properties\": {\"/placeholder/status\": \"copacetic\"},\n"
427 : : " \"sourceNodeId\": \"a\",\n"
428 : : " \"targetNodeId\": \"c\"}]}"));
429 : 4 : }
430 : :
431 : 4 : {
432 : 4 : auto dg = g->make_dot_graph ();
433 : :
434 : 4 : pretty_printer pp;
435 : 4 : dot::writer w (pp);
436 : 4 : dg->print (w);
437 : 4 : ASSERT_STREQ
438 : : (pp_formatted_text (&pp),
439 : : ("digraph {\n"
440 : : " label=\"test graph\";\n"
441 : : " a;\n"
442 : : " \n"
443 : : " subgraph cluster_b {\n"
444 : : " c [label=\"I am a node label\"];\n"
445 : : "\n"
446 : : " };\n"
447 : : " a -> c [label=\"I am an edge label\"];\n"
448 : : "}\n"));
449 : 4 : }
450 : 4 : }
451 : :
452 : : /* Run all of the selftests within this file. */
453 : :
454 : : void
455 : 4 : digraphs_cc_tests ()
456 : : {
457 : 4 : test_empty_graph ();
458 : 4 : test_simple_graph ();
459 : 4 : }
460 : :
461 : : } // namespace diagnostics::selftest
462 : : } // namespace diagnostics
463 : :
464 : : #endif /* CHECKING_P */
|
