diff options
Diffstat (limited to 'gcc/digraph.cc')
| -rw-r--r-- | gcc/digraph.cc | 188 |
1 files changed, 188 insertions, 0 deletions
diff --git a/gcc/digraph.cc b/gcc/digraph.cc new file mode 100644 index 0000000..02ff93d --- /dev/null +++ b/gcc/digraph.cc @@ -0,0 +1,188 @@ +/* Template classes for directed graphs. + Copyright (C) 2019-2020 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "diagnostic.h" +#include "graphviz.h" +#include "digraph.h" +#include "shortest-paths.h" +#include "selftest.h" + +#if CHECKING_P + +namespace selftest { + +/* A family of digraph classes for writing selftests. */ + +struct test_node; +struct test_edge; +struct test_graph; +struct test_dump_args_t {}; +struct test_cluster; + +struct test_graph_traits +{ + typedef test_node node_t; + typedef test_edge edge_t; + typedef test_graph graph_t; + typedef test_dump_args_t dump_args_t; + typedef test_cluster cluster_t; +}; + +struct test_node : public dnode<test_graph_traits> +{ + test_node (const char *name, int index) : m_name (name), m_index (index) {} + void dump_dot (graphviz_out *, const dump_args_t &) const OVERRIDE + { + } + + const char *m_name; + int m_index; +}; + +struct test_edge : public dedge<test_graph_traits> +{ + test_edge (node_t *src, node_t *dest) + : dedge (src, dest) + {} + + void dump_dot (graphviz_out *gv, const dump_args_t &) const OVERRIDE + { + gv->println ("%s -> %s;", m_src->m_name, m_dest->m_name); + } +}; + +struct test_graph : public digraph<test_graph_traits> +{ + test_node *add_test_node (const char *name) + { + test_node *result = new test_node (name, m_nodes.length ()); + add_node (result); + return result; + } + + test_edge *add_test_edge (test_node *src, test_node *dst) + { + test_edge *result = new test_edge (src, dst); + add_edge (result); + return result; + } +}; + +struct test_cluster : public cluster<test_graph_traits> +{ +}; + +struct test_path +{ + auto_vec<const test_edge *> m_edges; +}; + +/* Smoketest of digraph dumping. */ + +static void +test_dump_to_dot () +{ + test_graph g; + test_node *a = g.add_test_node ("a"); + test_node *b = g.add_test_node ("b"); + g.add_test_edge (a, b); + + pretty_printer pp; + pp.buffer->stream = NULL; + test_dump_args_t dump_args; + g.dump_dot_to_pp (&pp, NULL, dump_args); + + ASSERT_STR_CONTAINS (pp_formatted_text (&pp), + "a -> b;\n"); +} + +/* Test shortest paths from A in this digraph, + where edges run top-to-bottom if not otherwise labeled: + + A + / \ + B C-->D + | | + E | + \ / + F. */ + +static void +test_shortest_paths () +{ + test_graph g; + test_node *a = g.add_test_node ("a"); + test_node *b = g.add_test_node ("b"); + test_node *c = g.add_test_node ("d"); + test_node *d = g.add_test_node ("d"); + test_node *e = g.add_test_node ("e"); + test_node *f = g.add_test_node ("f"); + + test_edge *ab = g.add_test_edge (a, b); + test_edge *ac = g.add_test_edge (a, c); + test_edge *cd = g.add_test_edge (c, d); + test_edge *be = g.add_test_edge (b, e); + g.add_test_edge (e, f); + test_edge *cf = g.add_test_edge (c, f); + + shortest_paths<test_graph_traits, test_path> sp (g, a); + + test_path path_to_a = sp.get_shortest_path (a); + ASSERT_EQ (path_to_a.m_edges.length (), 0); + + test_path path_to_b = sp.get_shortest_path (b); + ASSERT_EQ (path_to_b.m_edges.length (), 1); + ASSERT_EQ (path_to_b.m_edges[0], ab); + + test_path path_to_c = sp.get_shortest_path (c); + ASSERT_EQ (path_to_c.m_edges.length (), 1); + ASSERT_EQ (path_to_c.m_edges[0], ac); + + test_path path_to_d = sp.get_shortest_path (d); + ASSERT_EQ (path_to_d.m_edges.length (), 2); + ASSERT_EQ (path_to_d.m_edges[0], ac); + ASSERT_EQ (path_to_d.m_edges[1], cd); + + test_path path_to_e = sp.get_shortest_path (e); + ASSERT_EQ (path_to_e.m_edges.length (), 2); + ASSERT_EQ (path_to_e.m_edges[0], ab); + ASSERT_EQ (path_to_e.m_edges[1], be); + + test_path path_to_f = sp.get_shortest_path (f); + ASSERT_EQ (path_to_f.m_edges.length (), 2); + ASSERT_EQ (path_to_f.m_edges[0], ac); + ASSERT_EQ (path_to_f.m_edges[1], cf); +} + +/* Run all of the selftests within this file. */ + +void +digraph_cc_tests () +{ + test_dump_to_dot (); + test_shortest_paths (); +} + +} // namespace selftest + +#endif /* #if CHECKING_P */ |