analyzer: support reverse direction in shortest-paths.h

This patch generalizes shortest-path.h so that it can be used to
find the shortest path from each node to a given target node (on top
of the existing support for finding the shortest path from a given
origin node to each node).

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.

gcc/analyzer/ChangeLog:
	* diagnostic-manager.cc (epath_finder::epath_finder):
	Update shortest_paths init for new param.

gcc/ChangeLog:
	* digraph.cc (selftest::test_shortest_paths): Update
	shortest_paths init for new param.  Add test of
	SPS_TO_GIVEN_TARGET.
	* shortest-paths.h (enum shortest_path_sense): New.
	(shortest_paths::shortest_paths): Add "sense" param.
	Update for renamings.  Generalize to use "sense" param.
	(shortest_paths::get_shortest_path): Rename param.
	(shortest_paths::m_sense): New field.
	(shortest_paths::m_prev): Rename...
	(shortest_paths::m_best_edge): ...to this.
	(shortest_paths::get_shortest_path): Update for renamings.
	Conditionalize flipping of path on sense of traversal.

1 files changed, 36 insertions, 3 deletions

diff --git a/gcc/digraph.cc b/gcc/digraph.cc
index 3441a85..e6966b0 100644
--- a/gcc/digraph.cc
+++ b/gcc/digraph.cc
@@ -147,7 +147,8 @@ test_shortest_paths ()
 
   /* Use "A" as the origin; all nodes should be reachable.  */
   {
-    shortest_paths<test_graph_traits, test_path> sp (g, a);
+    shortest_paths<test_graph_traits, test_path> sp (g, a,
+						     SPS_FROM_GIVEN_ORIGIN);
 
     test_path path_to_a = sp.get_shortest_path (a);
     ASSERT_EQ (path_to_a.m_edges.length (), 0); /* Trivial path.  */
@@ -181,7 +182,8 @@ test_shortest_paths ()
 
   /* Use "B" as the origin, so only E and F are reachable.  */
   {
-    shortest_paths<test_graph_traits, test_path> sp (g, b);
+    shortest_paths<test_graph_traits, test_path> sp (g, b,
+						     SPS_FROM_GIVEN_ORIGIN);
 
     test_path path_to_a = sp.get_shortest_path (a);
     ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path.  */
@@ -207,7 +209,8 @@ test_shortest_paths ()
 
   /* Use "C" as the origin, so only D and F are reachable.  */
   {
-    shortest_paths<test_graph_traits, test_path> sp (g, c);
+    shortest_paths<test_graph_traits, test_path> sp (g, c,
+						     SPS_FROM_GIVEN_ORIGIN);
 
     test_path path_to_a = sp.get_shortest_path (a);
     ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path.  */
@@ -229,6 +232,36 @@ test_shortest_paths ()
     ASSERT_EQ (path_to_f.m_edges.length (), 1);
     ASSERT_EQ (path_to_f.m_edges[0], cf);
   }
+
+  /* Test of SPS_TO_GIVEN_TARGET.  Use "F" as the target.  */
+  {
+    shortest_paths<test_graph_traits, test_path> sp (g, f,
+						     SPS_TO_GIVEN_TARGET);
+
+    test_path path_to_a = sp.get_shortest_path (a);
+    ASSERT_EQ (path_to_a.m_edges.length (), 2);
+    ASSERT_EQ (path_to_a.m_edges[0], ac);
+    ASSERT_EQ (path_to_a.m_edges[1], cf);
+
+    test_path path_to_b = sp.get_shortest_path (b);
+    ASSERT_EQ (path_to_b.m_edges.length (), 2);
+    ASSERT_EQ (path_to_b.m_edges[0], be);
+    ASSERT_EQ (path_to_b.m_edges[1], ef);
+
+    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], cf);
+
+    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 (), 1);
+    ASSERT_EQ (path_to_e.m_edges[0], ef);
+
+    test_path path_to_f = sp.get_shortest_path (f);
+    ASSERT_EQ (path_to_f.m_edges.length (), 0);
+  }
 }
 
 /* Run all of the selftests within this file.  */