[COMMITTED 012/101] gccrs: foreverstack: Add `to_canonical_path` method

[arthur.cohen@embecosm.com]

From: Arthur Cohen <arthur.cohen@embecosm.com>

gcc/rust/ChangeLog:

	* resolve/rust-forever-stack.h: New method.
	* resolve/rust-forever-stack.hxx: Likewise.
---
 gcc/rust/resolve/rust-forever-stack.h   | 25 ++++++-
 gcc/rust/resolve/rust-forever-stack.hxx | 90 ++++++++++++++++++++++++-
 2 files changed, 110 insertions(+), 5 deletions(-)

diff --git a/gcc/rust/resolve/rust-forever-stack.h b/gcc/rust/resolve/rust-forever-stack.h
index ec469a9b3fa..37277ddb3ad 100644
--- a/gcc/rust/resolve/rust-forever-stack.h
+++ b/gcc/rust/resolve/rust-forever-stack.h
@@ -396,7 +396,10 @@ template <Namespace N> class ForeverStack
 {
 public:
   ForeverStack ()
-    : root (Node (Rib (Rib::Kind::Normal))), cursor_reference (root)
+    // FIXME: Is that valid? Do we use the root? If yes, we should give the
+    // crate's node id to ForeverStack's constructor
+    : root (Node (Rib (Rib::Kind::Normal), UNKNOWN_NODEID)),
+      cursor_reference (root)
   {
     rust_assert (root.is_root ());
     rust_assert (root.is_leaf ());
@@ -478,6 +481,12 @@ public:
   template <typename S>
   tl::optional<NodeId> resolve_path (const std::vector<S> &segments);
 
+  // FIXME: Documentation
+  tl::optional<Resolver::CanonicalPath> to_canonical_path (NodeId id);
+
+  // FIXME: Documentation
+  tl::optional<Rib &> to_rib (NodeId rib_id);
+
   std::string as_debug_string ();
 
 private:
@@ -509,8 +518,10 @@ private:
   class Node
   {
   public:
-    Node (Rib rib) : rib (rib) {}
-    Node (Rib rib, Node &parent) : rib (rib), parent (parent) {}
+    Node (Rib rib, NodeId id) : rib (rib), id (id) {}
+    Node (Rib rib, NodeId id, Node &parent)
+      : rib (rib), id (id), parent (parent)
+    {}
 
     bool is_root () const;
     bool is_leaf () const;
@@ -520,6 +531,8 @@ private:
     Rib rib; // this is the "value" of the node - the data it keeps.
     std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
 
+    NodeId id; // The node id of the Node's scope
+
     tl::optional<Node &> parent; // `None` only if the node is a root
   };
 
@@ -566,6 +579,12 @@ private:
   tl::optional<Node &> resolve_segments (Node &starting_point,
 					 const std::vector<S> &segments,
 					 SegIterator<S> iterator);
+
+  /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
+
+  // FIXME: Documentation
+  tl::optional<std::pair<Node &, std::string>> dfs (Node &starting_point,
+						    NodeId to_find);
 };
 
 } // namespace Resolver2_0
diff --git a/gcc/rust/resolve/rust-forever-stack.hxx b/gcc/rust/resolve/rust-forever-stack.hxx
index 642135cda85..4e06da235bf 100644
--- a/gcc/rust/resolve/rust-forever-stack.hxx
+++ b/gcc/rust/resolve/rust-forever-stack.hxx
@@ -66,8 +66,8 @@ ForeverStack<N>::push_inner (Rib rib, Link link)
   // the iterator and a boolean. If the value already exists, the iterator
   // points to it. Otherwise, it points to the newly emplaced value, so we can
   // just update our cursor().
-  auto emplace
-    = cursor ().children.emplace (std::make_pair (link, Node (rib, cursor ())));
+  auto emplace = cursor ().children.emplace (
+    std::make_pair (link, Node (rib, link.id, cursor ())));
 
   auto it = emplace.first;
   auto existed = !emplace.second;
@@ -451,6 +451,92 @@ ForeverStack<N>::resolve_path (const std::vector<S> &segments)
     });
 }
 
+template <Namespace N>
+tl::optional<std::pair<typename ForeverStack<N>::Node &, std::string>>
+ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
+{
+  auto &values = starting_point.rib.get_values ();
+
+  for (auto &kv : values)
+    if (kv.second == to_find)
+      return {{starting_point, kv.first}};
+
+  for (auto &child : starting_point.children)
+    {
+      auto candidate = dfs (child.second, to_find);
+
+      if (candidate.has_value ())
+	return candidate;
+    }
+
+  return tl::nullopt;
+}
+
+template <Namespace N>
+tl::optional<Resolver::CanonicalPath>
+ForeverStack<N>::to_canonical_path (NodeId id)
+{
+  // find the id in the current forever stack, starting from the root,
+  // performing either a BFS or DFS once the Node containing the ID is found, go
+  // back up to the root (parent().parent().parent()...) accumulate link
+  // segments reverse them that's your canonical path
+
+  return dfs (root, id).map ([this, id] (std::pair<Node &, std::string> tuple) {
+    auto containing_node = tuple.first;
+    auto name = tuple.second;
+
+    auto segments = std::vector<Resolver::CanonicalPath> ();
+
+    reverse_iter (containing_node, [&segments] (Node &current) {
+      if (current.is_root ())
+	return KeepGoing::No;
+
+      auto children = current.parent.value ().children;
+      const Link *outer_link = nullptr;
+
+      for (auto &kv : children)
+	{
+	  auto &link = kv.first;
+	  auto &child = kv.second;
+
+	  if (link.id == child.id)
+	    {
+	      outer_link = &link;
+	      break;
+	    }
+	}
+
+      rust_assert (outer_link);
+
+      outer_link->path.map ([&segments, outer_link] (Identifier path) {
+	segments.emplace (segments.begin (),
+			  Resolver::CanonicalPath::new_seg (outer_link->id,
+							    path.as_string ()));
+      });
+
+      return KeepGoing::Yes;
+    });
+
+    auto path = Resolver::CanonicalPath::create_empty ();
+    for (const auto &segment : segments)
+      path = path.append (segment);
+
+    // Finally, append the name
+    path = path.append (Resolver::CanonicalPath::new_seg (id, name));
+    rust_debug ("[ARTHUR] found path: %s. Size: %lu", path.get ().c_str (),
+		segments.size ());
+
+    return path;
+  });
+}
+
+template <Namespace N>
+tl::optional<Rib &>
+ForeverStack<N>::to_rib (NodeId rib_id)
+{
+  return tl::nullopt;
+}
+
 template <Namespace N>
 void
 ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
-- 
2.42.1