diff mbox series

[committed] analyzer: gracefully handle impossible paths in shortest-paths.h

Message ID 20210311225512.3131325-1-dmalcolm@redhat.com
State New
Headers show
Series [committed] analyzer: gracefully handle impossible paths in shortest-paths.h | expand

Commit Message

David Malcolm March 11, 2021, 10:55 p.m. UTC 
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 mbox series

Patch

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