1 | /* Template classes for directed graphs. |
2 | Copyright (C) 2019-2023 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 | #include "config.h" |
22 | #include "system.h" |
23 | #include "coretypes.h" |
24 | #include "diagnostic.h" |
25 | #include "graphviz.h" |
26 | #include "digraph.h" |
27 | #include "shortest-paths.h" |
28 | #include "selftest.h" |
29 | |
30 | #if CHECKING_P |
31 | |
32 | namespace selftest { |
33 | |
34 | /* A family of digraph classes for writing selftests. */ |
35 | |
36 | struct test_node; |
37 | struct test_edge; |
38 | struct test_graph; |
39 | struct test_dump_args_t {}; |
40 | struct test_cluster; |
41 | |
42 | struct test_graph_traits |
43 | { |
44 | typedef test_node node_t; |
45 | typedef test_edge edge_t; |
46 | typedef test_graph graph_t; |
47 | typedef test_dump_args_t dump_args_t; |
48 | typedef test_cluster cluster_t; |
49 | }; |
50 | |
51 | struct test_node : public dnode<test_graph_traits> |
52 | { |
53 | test_node (const char *name, int index) : m_name (name), m_index (index) {} |
54 | void dump_dot (graphviz_out *, const dump_args_t &) const override |
55 | { |
56 | } |
57 | |
58 | const char *m_name; |
59 | int m_index; |
60 | }; |
61 | |
62 | struct test_edge : public dedge<test_graph_traits> |
63 | { |
64 | test_edge (node_t *src, node_t *dest) |
65 | : dedge<test_graph_traits> (src, dest) |
66 | {} |
67 | |
68 | void dump_dot (graphviz_out *gv, const dump_args_t &) const override |
69 | { |
70 | gv->println (fmt: "%s %s %s%c" , m_src->m_name, "->" , m_dest->m_name, ';'); |
71 | } |
72 | }; |
73 | |
74 | struct test_graph : public digraph<test_graph_traits> |
75 | { |
76 | test_node *add_test_node (const char *name) |
77 | { |
78 | test_node *result = new test_node (name, m_nodes.length ()); |
79 | add_node (node: result); |
80 | return result; |
81 | } |
82 | |
83 | test_edge *add_test_edge (test_node *src, test_node *dst) |
84 | { |
85 | test_edge *result = new test_edge (src, dst); |
86 | add_edge (edge: result); |
87 | return result; |
88 | } |
89 | }; |
90 | |
91 | struct test_cluster : public cluster<test_graph_traits> |
92 | { |
93 | }; |
94 | |
95 | struct test_path |
96 | { |
97 | auto_vec<const test_edge *> m_edges; |
98 | }; |
99 | |
100 | /* Smoketest of digraph dumping. */ |
101 | |
102 | static void |
103 | test_dump_to_dot () |
104 | { |
105 | test_graph g; |
106 | test_node *a = g.add_test_node (name: "a" ); |
107 | test_node *b = g.add_test_node (name: "b" ); |
108 | g.add_test_edge (src: a, dst: b); |
109 | |
110 | pretty_printer pp; |
111 | pp.buffer->stream = NULL; |
112 | test_dump_args_t dump_args; |
113 | g.dump_dot_to_pp (pp: &pp, NULL, args: dump_args); |
114 | |
115 | ASSERT_STR_CONTAINS (pp_formatted_text (&pp), |
116 | "a -> b;\n" ); |
117 | } |
118 | |
119 | /* Test shortest paths from A in this digraph, |
120 | where edges run top-to-bottom if not otherwise labeled: |
121 | |
122 | A |
123 | / \ |
124 | B C-->D |
125 | | | |
126 | E | |
127 | \ / |
128 | F. */ |
129 | |
130 | static void |
131 | test_shortest_paths () |
132 | { |
133 | test_graph g; |
134 | test_node *a = g.add_test_node (name: "a" ); |
135 | test_node *b = g.add_test_node (name: "b" ); |
136 | test_node *c = g.add_test_node (name: "d" ); |
137 | test_node *d = g.add_test_node (name: "d" ); |
138 | test_node *e = g.add_test_node (name: "e" ); |
139 | test_node *f = g.add_test_node (name: "f" ); |
140 | |
141 | test_edge *ab = g.add_test_edge (src: a, dst: b); |
142 | test_edge *ac = g.add_test_edge (src: a, dst: c); |
143 | test_edge *cd = g.add_test_edge (src: c, dst: d); |
144 | test_edge *be = g.add_test_edge (src: b, dst: e); |
145 | test_edge *ef = g.add_test_edge (src: e, dst: f); |
146 | test_edge *cf = g.add_test_edge (src: c, dst: f); |
147 | |
148 | /* Use "A" as the origin; all nodes should be reachable. */ |
149 | { |
150 | shortest_paths<test_graph_traits, test_path> sp (g, a, |
151 | SPS_FROM_GIVEN_ORIGIN); |
152 | |
153 | test_path path_to_a = sp.get_shortest_path (other_node: a); |
154 | ASSERT_EQ (path_to_a.m_edges.length (), 0); /* Trivial path. */ |
155 | |
156 | test_path path_to_b = sp.get_shortest_path (other_node: b); |
157 | ASSERT_EQ (path_to_b.m_edges.length (), 1); |
158 | ASSERT_EQ (path_to_b.m_edges[0], ab); |
159 | |
160 | test_path path_to_c = sp.get_shortest_path (other_node: c); |
161 | ASSERT_EQ (path_to_c.m_edges.length (), 1); |
162 | ASSERT_EQ (path_to_c.m_edges[0], ac); |
163 | |
164 | test_path path_to_d = sp.get_shortest_path (other_node: d); |
165 | ASSERT_EQ (path_to_d.m_edges.length (), 2); |
166 | ASSERT_EQ (path_to_d.m_edges[0], ac); |
167 | ASSERT_EQ (path_to_d.m_edges[1], cd); |
168 | |
169 | test_path path_to_e = sp.get_shortest_path (other_node: e); |
170 | ASSERT_EQ (path_to_e.m_edges.length (), 2); |
171 | ASSERT_EQ (path_to_e.m_edges[0], ab); |
172 | ASSERT_EQ (path_to_e.m_edges[1], be); |
173 | |
174 | test_path path_to_f = sp.get_shortest_path (other_node: f); |
175 | ASSERT_EQ (path_to_f.m_edges.length (), 2); |
176 | ASSERT_EQ (path_to_f.m_edges[0], ac); |
177 | ASSERT_EQ (path_to_f.m_edges[1], cf); |
178 | } |
179 | |
180 | /* Verify that we gracefully handle an origin from which some nodes |
181 | aren't reachable. */ |
182 | |
183 | /* Use "B" as the origin, so only E and F are reachable. */ |
184 | { |
185 | shortest_paths<test_graph_traits, test_path> sp (g, b, |
186 | SPS_FROM_GIVEN_ORIGIN); |
187 | |
188 | test_path path_to_a = sp.get_shortest_path (other_node: a); |
189 | ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */ |
190 | |
191 | test_path path_to_b = sp.get_shortest_path (other_node: b); |
192 | ASSERT_EQ (path_to_b.m_edges.length (), 0); /* Trivial path. */ |
193 | |
194 | test_path path_to_c = sp.get_shortest_path (other_node: c); |
195 | ASSERT_EQ (path_to_c.m_edges.length (), 0); /* No path. */ |
196 | |
197 | test_path path_to_d = sp.get_shortest_path (other_node: d); |
198 | ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */ |
199 | |
200 | test_path path_to_e = sp.get_shortest_path (other_node: e); |
201 | ASSERT_EQ (path_to_e.m_edges.length (), 1); |
202 | ASSERT_EQ (path_to_e.m_edges[0], be); |
203 | |
204 | test_path path_to_f = sp.get_shortest_path (other_node: f); |
205 | ASSERT_EQ (path_to_f.m_edges.length (), 2); |
206 | ASSERT_EQ (path_to_f.m_edges[0], be); |
207 | ASSERT_EQ (path_to_f.m_edges[1], ef); |
208 | } |
209 | |
210 | /* Use "C" as the origin, so only D and F are reachable. */ |
211 | { |
212 | shortest_paths<test_graph_traits, test_path> sp (g, c, |
213 | SPS_FROM_GIVEN_ORIGIN); |
214 | |
215 | test_path path_to_a = sp.get_shortest_path (other_node: a); |
216 | ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */ |
217 | |
218 | test_path path_to_b = sp.get_shortest_path (other_node: b); |
219 | ASSERT_EQ (path_to_b.m_edges.length (), 0); /* No path. */ |
220 | |
221 | test_path path_to_c = sp.get_shortest_path (other_node: c); |
222 | ASSERT_EQ (path_to_c.m_edges.length (), 0); /* Trivial path. */ |
223 | |
224 | test_path path_to_d = sp.get_shortest_path (other_node: d); |
225 | ASSERT_EQ (path_to_d.m_edges.length (), 1); |
226 | ASSERT_EQ (path_to_d.m_edges[0], cd); |
227 | |
228 | test_path path_to_e = sp.get_shortest_path (other_node: e); |
229 | ASSERT_EQ (path_to_e.m_edges.length (), 0); /* No path. */ |
230 | |
231 | test_path path_to_f = sp.get_shortest_path (other_node: f); |
232 | ASSERT_EQ (path_to_f.m_edges.length (), 1); |
233 | ASSERT_EQ (path_to_f.m_edges[0], cf); |
234 | } |
235 | |
236 | /* Test of SPS_TO_GIVEN_TARGET. Use "F" as the target. */ |
237 | { |
238 | shortest_paths<test_graph_traits, test_path> sp (g, f, |
239 | SPS_TO_GIVEN_TARGET); |
240 | |
241 | test_path path_to_a = sp.get_shortest_path (other_node: a); |
242 | ASSERT_EQ (path_to_a.m_edges.length (), 2); |
243 | ASSERT_EQ (path_to_a.m_edges[0], ac); |
244 | ASSERT_EQ (path_to_a.m_edges[1], cf); |
245 | |
246 | test_path path_to_b = sp.get_shortest_path (other_node: b); |
247 | ASSERT_EQ (path_to_b.m_edges.length (), 2); |
248 | ASSERT_EQ (path_to_b.m_edges[0], be); |
249 | ASSERT_EQ (path_to_b.m_edges[1], ef); |
250 | |
251 | test_path path_to_c = sp.get_shortest_path (other_node: c); |
252 | ASSERT_EQ (path_to_c.m_edges.length (), 1); |
253 | ASSERT_EQ (path_to_c.m_edges[0], cf); |
254 | |
255 | test_path path_to_d = sp.get_shortest_path (other_node: d); |
256 | ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */ |
257 | |
258 | test_path path_to_e = sp.get_shortest_path (other_node: e); |
259 | ASSERT_EQ (path_to_e.m_edges.length (), 1); |
260 | ASSERT_EQ (path_to_e.m_edges[0], ef); |
261 | |
262 | test_path path_to_f = sp.get_shortest_path (other_node: f); |
263 | ASSERT_EQ (path_to_f.m_edges.length (), 0); |
264 | } |
265 | } |
266 | |
267 | /* Run all of the selftests within this file. */ |
268 | |
269 | void |
270 | digraph_cc_tests () |
271 | { |
272 | test_dump_to_dot (); |
273 | test_shortest_paths (); |
274 | } |
275 | |
276 | } // namespace selftest |
277 | |
278 | #endif /* #if CHECKING_P */ |
279 | |