This bulletproofs the shortest_paths code against unreachable nodes,
gracefully handling them, rather than failing an assertion.
I've marked this as "analyzer" as this is the only code using
shortest-paths.h.
This patch is required by followup work to fix PR analyzer/96374.
Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Pushed to trunk as r11-7638-g3f958348e78f38d91f0611618bb909182170c0f3.
gcc/ChangeLog:
* digraph.cc (selftest::test_shortest_paths): Add test coverage
for paths from B and C.
* shortest-paths.h (shortest_paths::shortest_paths): Handle
unreachable nodes, rather than asserting.
---
gcc/digraph.cc | 101 +++++++++++++++++++++++++++++++++----------
gcc/shortest-paths.h | 6 ++-
2 files changed, 83 insertions(+), 24 deletions(-)
diff --git a/gcc/digraph.cc b/gcc/digraph.cc
index 163909bb3ea..3441a8586cb 100644
--- a/gcc/digraph.cc
+++ b/gcc/digraph.cc
@@ -142,36 +142,93 @@ test_shortest_paths ()
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 *ef = 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);
+ /* Use "A" as the origin; all nodes should be reachable. */
+ {
+ 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); /* Trivial path. */
+
+ 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);
+ }
+
+ /* Verify that we gracefully handle an origin from which some nodes
+ aren't reachable. */
+
+ /* Use "B" as the origin, so only E and F are reachable. */
+ {
+ shortest_paths<test_graph_traits, test_path> sp (g, b);
- test_path path_to_a = sp.get_shortest_path (a);
- ASSERT_EQ (path_to_a.m_edges.length (), 0);
+ test_path path_to_a = sp.get_shortest_path (a);
+ ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */
- 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_b = sp.get_shortest_path (b);
+ ASSERT_EQ (path_to_b.m_edges.length (), 0); /* Trivial path. */
- 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_c = sp.get_shortest_path (c);
+ ASSERT_EQ (path_to_c.m_edges.length (), 0); /* No path. */
- 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_d = sp.get_shortest_path (d);
+ ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */
- 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_e = sp.get_shortest_path (e);
+ ASSERT_EQ (path_to_e.m_edges.length (), 1);
+ ASSERT_EQ (path_to_e.m_edges[0], 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);
+ 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], be);
+ ASSERT_EQ (path_to_f.m_edges[1], ef);
+ }
+
+ /* Use "C" as the origin, so only D and F are reachable. */
+ {
+ shortest_paths<test_graph_traits, test_path> sp (g, c);
+
+ test_path path_to_a = sp.get_shortest_path (a);
+ ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */
+
+ test_path path_to_b = sp.get_shortest_path (b);
+ ASSERT_EQ (path_to_b.m_edges.length (), 0); /* No path. */
+
+ test_path path_to_c = sp.get_shortest_path (c);
+ ASSERT_EQ (path_to_c.m_edges.length (), 0); /* Trivial path. */
+
+ test_path path_to_d = sp.get_shortest_path (d);
+ ASSERT_EQ (path_to_d.m_edges.length (), 1);
+ ASSERT_EQ (path_to_d.m_edges[0], cd);
+
+ test_path path_to_e = sp.get_shortest_path (e);
+ ASSERT_EQ (path_to_e.m_edges.length (), 0); /* No path. */
+
+ test_path path_to_f = sp.get_shortest_path (f);
+ ASSERT_EQ (path_to_f.m_edges.length (), 1);
+ ASSERT_EQ (path_to_f.m_edges[0], cf);
+ }
}
/* Run all of the selftests within this file. */
diff --git a/gcc/shortest-paths.h b/gcc/shortest-paths.h
index ded62852ca3..5648a959895 100644
--- a/gcc/shortest-paths.h
+++ b/gcc/shortest-paths.h
@@ -96,7 +96,8 @@ shortest_paths<GraphTraits, Path_t>::shortest_paths (const
graph_t &graph,
idx_in_queue_with_min_dist = i;
}
}
- gcc_assert (idx_with_min_dist != -1);
+ if (idx_with_min_dist == -1)
+ break;
gcc_assert (idx_in_queue_with_min_dist != -1);
// FIXME: this is confusing: there are two indices here
@@ -123,7 +124,8 @@ shortest_paths<GraphTraits, Path_t>::shortest_paths (const
graph_t &graph,
}
/* Generate an Path_t instance giving the shortest path to the node
- TO from the origin node. */
+ TO from the origin node.
+ If no such path exists, return an empty path. */
template <typename GraphTraits, typename Path_t>
inline Path_t
--
2.26.2
