https://gcc.gnu.org/g:469d668f6fac45dcd72182d1075285c761acac94
commit r15-8609-g469d668f6fac45dcd72182d1075285c761acac94
Author: Owen Avery <powerboat9.ga...@gmail.com>
Date: Thu Nov 14 19:57:42 2024 -0500
gccrs: Add ForeverStackStore
ForeverStackStore is meant to partially unify the internal states of
per-namespace ForeverStack instances. This commit does not contain
modifications to ForeverStack which would allow it to rely on a
ForeverStackStore to store nodes, but a future commit should address
this.
gcc/rust/ChangeLog:
* Make-lang.in: Handle rust-forever-stack.cc.
* resolve/rust-forever-stack.h
(class ForeverStackStore): Add.
* resolve/rust-forever-stack.cc: New file, based on
rust-forever-stack.hxx.
Signed-off-by: Owen Avery <powerboat9.ga...@gmail.com>
Diff:
---
gcc/rust/Make-lang.in | 1 +
gcc/rust/resolve/rust-forever-stack.cc | 318 +++++++++++++++++++++++++++++++++
gcc/rust/resolve/rust-forever-stack.h | 151 ++++++++++++++++
3 files changed, 470 insertions(+)
diff --git a/gcc/rust/Make-lang.in b/gcc/rust/Make-lang.in
index 8771cdf91e1e..b6f3a35e4e6f 100644
--- a/gcc/rust/Make-lang.in
+++ b/gcc/rust/Make-lang.in
@@ -146,6 +146,7 @@ GRS_OBJS = \
rust/rust-ast-resolve-path.o \
rust/rust-ast-resolve-stmt.o \
rust/rust-ast-resolve-struct-expr-field.o \
+ rust/rust-forever-stack.o \
rust/rust-hir-type-check.o \
rust/rust-privacy-check.o \
rust/rust-privacy-ctx.o \
diff --git a/gcc/rust/resolve/rust-forever-stack.cc
b/gcc/rust/resolve/rust-forever-stack.cc
new file mode 100644
index 000000000000..725ae0ea0188
--- /dev/null
+++ b/gcc/rust/resolve/rust-forever-stack.cc
@@ -0,0 +1,318 @@
+// Copyright (C) 2024 Free Software Foundation, Inc.
+
+// 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 "expected.h"
+#include "rust-ast.h"
+#include "rust-diagnostics.h"
+#include "rust-forever-stack.h"
+#include "rust-rib.h"
+#include "optional.h"
+
+namespace Rust {
+namespace Resolver2_0 {
+
+bool
+ForeverStackStore::Node::is_root () const
+{
+ return !parent.has_value ();
+}
+
+bool
+ForeverStackStore::Node::is_leaf () const
+{
+ return children.empty ();
+}
+
+NodeId
+ForeverStackStore::Node::get_id () const
+{
+ return id;
+}
+
+ForeverStackStore::Node &
+ForeverStackStore::Node::insert_child (NodeId id, tl::optional<Identifier>
path,
+ Rib::Kind kind)
+{
+ auto res = children.insert ({Link (id, path), Node (kind, id, *this)});
+
+ rust_debug ("inserting link: Link(%d [%s]): existed? %s", id,
+ path.has_value () ? path.value ().as_string ().c_str ()
+ : "<anon>",
+ !res.second ? "yes" : "no");
+
+ // sanity check on rib kind
+ // pick the value rib, since all ribs should have the same kind anyways
+ rust_assert (res.second || res.first->second.value_rib.kind == kind);
+
+ // verify, if we're using an existing node, our paths don't contradict
+ if (!res.second && path.has_value ())
+ {
+ auto other_path = res.first->first.path;
+ rust_assert (!other_path.has_value ()
+ || other_path.value ().as_string ()
+ == path.value ().as_string ());
+ }
+
+ return res.first->second;
+}
+
+tl::optional<ForeverStackStore::Node &>
+ForeverStackStore::Node::get_child (const Identifier &path)
+{
+ for (auto &ent : children)
+ {
+ if (ent.first.path.has_value ()
+ && ent.first.path->as_string () == path.as_string ())
+ return ent.second;
+ }
+ return tl::nullopt;
+}
+
+tl::optional<const ForeverStackStore::Node &>
+ForeverStackStore::Node::get_child (const Identifier &path) const
+{
+ for (auto &ent : children)
+ {
+ if (ent.first.path.has_value ()
+ && ent.first.path->as_string () == path.as_string ())
+ return ent.second;
+ }
+ return tl::nullopt;
+}
+
+tl::optional<ForeverStackStore::Node &>
+ForeverStackStore::Node::get_parent ()
+{
+ return parent;
+}
+
+tl::optional<const ForeverStackStore::Node &>
+ForeverStackStore::Node::get_parent () const
+{
+ if (parent)
+ return *parent;
+ return tl::nullopt;
+}
+
+tl::optional<const Identifier &>
+ForeverStackStore::Node::get_parent_path () const
+{
+ if (parent.has_value ())
+ for (auto &ent : parent->children)
+ if (ent.first.id == id && ent.first.path.has_value ())
+ return ent.first.path.value ();
+ return tl::nullopt;
+}
+
+Rib &
+ForeverStackStore::Node::get_rib (Namespace ns)
+{
+ switch (ns)
+ {
+ case Namespace::Values:
+ return value_rib;
+ case Namespace::Types:
+ return type_rib;
+ case Namespace::Labels:
+ return label_rib;
+ case Namespace::Macros:
+ return macro_rib;
+ default:
+ rust_unreachable ();
+ }
+}
+
+const Rib &
+ForeverStackStore::Node::get_rib (Namespace ns) const
+{
+ switch (ns)
+ {
+ case Namespace::Values:
+ return value_rib;
+ case Namespace::Types:
+ return type_rib;
+ case Namespace::Labels:
+ return label_rib;
+ case Namespace::Macros:
+ return macro_rib;
+ default:
+ rust_unreachable ();
+ }
+}
+
+tl::expected<NodeId, DuplicateNameError>
+ForeverStackStore::Node::insert (const Identifier &name, NodeId node,
+ Namespace ns)
+{
+ // So what do we do here - if the Rib has already been pushed in an earlier
+ // pass, we might end up in a situation where it is okay to re-add new names.
+ // Do we just ignore that here? Do we keep track of if the Rib is new or not?
+ // should our cursor have info on the current node like "is it newly pushed"?
+ return get_rib (ns).insert (name.as_string (),
+ Rib::Definition::NonShadowable (node));
+}
+
+tl::expected<NodeId, DuplicateNameError>
+ForeverStackStore::Node::insert_shadowable (const Identifier &name, NodeId
node,
+ Namespace ns)
+{
+ return get_rib (ns).insert (name.as_string (),
+ Rib::Definition::Shadowable (node));
+}
+
+tl::expected<NodeId, DuplicateNameError>
+ForeverStackStore::Node::insert_globbed (const Identifier &name, NodeId node,
+ Namespace ns)
+{
+ return get_rib (ns).insert (name.as_string (),
+ Rib::Definition::Globbed (node));
+}
+
+void
+ForeverStackStore::Node::reverse_iter (std::function<KeepGoing (Node &)>
lambda)
+{
+ for (Node *tmp = this; lambda (*tmp) == KeepGoing::Yes && !tmp->is_root ();
+ tmp = &tmp->parent.value ())
+ ;
+}
+
+void
+ForeverStackStore::Node::reverse_iter (
+ std::function<KeepGoing (const Node &)> lambda) const
+{
+ for (const Node *tmp = this;
+ lambda (*tmp) == KeepGoing::Yes && !tmp->is_root ();
+ tmp = &tmp->parent.value ())
+ ;
+}
+
+void
+ForeverStackStore::Node::child_iter (
+ std::function<KeepGoing (NodeId, tl::optional<const Identifier &>, Node &)>
+ lambda)
+{
+ for (auto &ent : children)
+ {
+ tl::optional<const Identifier &> path;
+ if (ent.first.path.has_value ())
+ path = ent.first.path.value ();
+ auto keep_going = lambda (ent.first.id, path, ent.second);
+ if (keep_going == KeepGoing::No)
+ return;
+ }
+}
+
+void
+ForeverStackStore::Node::child_iter (
+ std::function<KeepGoing (NodeId, tl::optional<const Identifier &>,
+ const Node &)>
+ lambda) const
+{
+ for (auto &ent : children)
+ {
+ tl::optional<const Identifier &> path;
+ if (ent.first.path.has_value ())
+ path = ent.first.path.value ();
+ auto keep_going = lambda (ent.first.id, path, ent.second);
+ if (keep_going == KeepGoing::No)
+ return;
+ }
+}
+
+ForeverStackStore::Node &
+ForeverStackStore::Node::find_closest_module ()
+{
+ // get kind of value_rib
+ // but all ribs should share the same kind anyways
+ if (value_rib.kind == Rib::Kind::Module || !parent.has_value ())
+ return *this;
+ else
+ return parent->find_closest_module ();
+}
+
+const ForeverStackStore::Node &
+ForeverStackStore::Node::find_closest_module () const
+{
+ // get kind of value_rib
+ // but all ribs should share the same kind anyways
+ if (value_rib.kind != Rib::Kind::Module || !parent.has_value ())
+ return *this;
+ else
+ return parent->find_closest_module ();
+}
+
+tl::optional<ForeverStackStore::Node &>
+ForeverStackStore::Node::dfs_node (NodeId to_find)
+{
+ if (id == to_find)
+ return *this;
+
+ for (auto &child : children)
+ {
+ auto candidate = child.second.dfs_node (to_find);
+
+ if (candidate.has_value ())
+ return candidate;
+ }
+
+ return tl::nullopt;
+}
+
+tl::optional<const ForeverStackStore::Node &>
+ForeverStackStore::Node::dfs_node (NodeId to_find) const
+{
+ if (id == to_find)
+ return *this;
+
+ for (auto &child : children)
+ {
+ auto candidate = child.second.dfs_node (to_find);
+
+ if (candidate.has_value ())
+ return candidate;
+ }
+
+ return tl::nullopt;
+}
+
+ForeverStackStore::Node &
+ForeverStackStore::get_root ()
+{
+ return root;
+}
+
+const ForeverStackStore::Node &
+ForeverStackStore::get_root () const
+{
+ return root;
+}
+
+tl::optional<ForeverStackStore::Node &>
+ForeverStackStore::get_node (NodeId node_id)
+{
+ return root.dfs_node (node_id);
+}
+
+tl::optional<const ForeverStackStore::Node &>
+ForeverStackStore::get_node (NodeId node_id) const
+{
+ return root.dfs_node (node_id);
+}
+
+} // namespace Resolver2_0
+} // namespace Rust
diff --git a/gcc/rust/resolve/rust-forever-stack.h
b/gcc/rust/resolve/rust-forever-stack.h
index 064d1ab2bb3a..66e12668f71a 100644
--- a/gcc/rust/resolve/rust-forever-stack.h
+++ b/gcc/rust/resolve/rust-forever-stack.h
@@ -392,6 +392,157 @@ not contain any imports, macro definitions or macro
invocations. You can look at
this pass's documentation for more details on this resolution process.
**/
+
+/**
+ * Intended for use by ForeverStack to store Nodes
+ * Unlike ForeverStack, does not store a cursor reference
+ * Intended to make path resolution in multiple namespaces simpler
+ **/
+class ForeverStackStore
+{
+public:
+ ForeverStackStore (NodeId crate_id) : root (Rib::Kind::Normal, crate_id)
+ {
+ rust_assert (root.is_root ());
+ rust_assert (root.is_leaf ());
+ }
+
+private:
+ /**
+ * A link between two Nodes in our trie data structure. This class represents
+ * the edges of the graph
+ */
+ class Link
+ {
+ public:
+ Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
+
+ bool compare (const Link &other) const { return id < other.id; }
+
+ NodeId id;
+ tl::optional<Identifier> path;
+ };
+
+ /* Link comparison class, which we use in a Node's `children` map */
+ class LinkCmp
+ {
+ public:
+ bool operator() (const Link &lhs, const Link &rhs) const
+ {
+ return lhs.compare (rhs);
+ }
+ };
+
+public:
+ class Node;
+
+ struct DfsResult
+ {
+ Node &first;
+ std::string second;
+ };
+
+ struct ConstDfsResult
+ {
+ const Node &first;
+ std::string second;
+ };
+
+ /* Should we keep going upon seeing a Rib? */
+ enum class KeepGoing
+ {
+ Yes,
+ No,
+ };
+
+ class Node
+ {
+ private:
+ friend class ForeverStackStore::ForeverStackStore;
+
+ Node (Rib::Kind rib_kind, NodeId id, tl::optional<Node &> parent)
+ : value_rib (rib_kind), type_rib (rib_kind), label_rib (rib_kind),
+ macro_rib (rib_kind), id (id), parent (parent)
+ {}
+ Node (Rib::Kind rib_kind, NodeId id) : Node (rib_kind, id, tl::nullopt) {}
+ Node (Rib::Kind rib_kind, NodeId id, Node &parent)
+ : Node (rib_kind, id, tl::optional<Node &> (parent))
+ {}
+
+ public:
+ Node (const Node &) = default;
+ Node (Node &&) = default;
+ Node &operator= (const Node &) = delete;
+ Node &operator= (Node &&) = default;
+
+ bool is_root () const;
+ bool is_leaf () const;
+
+ NodeId get_id () const;
+
+ Node &insert_child (NodeId id, tl::optional<Identifier> path,
+ Rib::Kind kind);
+
+ tl::optional<Node &> get_child (const Identifier &path);
+ tl::optional<const Node &> get_child (const Identifier &path) const;
+
+ tl::optional<Node &> get_parent ();
+ tl::optional<const Node &> get_parent () const;
+
+ // finds the identifier, if any, used to link
+ // this node's parent to this node
+ tl::optional<const Identifier &> get_parent_path () const;
+
+ Rib &get_rib (Namespace ns);
+ const Rib &get_rib (Namespace ns) const;
+
+ tl::expected<NodeId, DuplicateNameError> insert (const Identifier &name,
+ NodeId node, Namespace ns);
+ tl::expected<NodeId, DuplicateNameError>
+ insert_shadowable (const Identifier &name, NodeId node, Namespace ns);
+ tl::expected<NodeId, DuplicateNameError>
+ insert_globbed (const Identifier &name, NodeId node, Namespace ns);
+
+ void reverse_iter (std::function<KeepGoing (Node &)> lambda);
+ void reverse_iter (std::function<KeepGoing (const Node &)> lambda) const;
+
+ void child_iter (std::function<KeepGoing (
+ NodeId, tl::optional<const Identifier &>, Node &)>
+ lambda);
+ void child_iter (std::function<KeepGoing (
+ NodeId, tl::optional<const Identifier &>, const Node &)>
+ lambda) const;
+
+ Node &find_closest_module ();
+ const Node &find_closest_module () const;
+
+ tl::optional<Node &> dfs_node (NodeId to_find);
+ tl::optional<const Node &> dfs_node (NodeId to_find) const;
+
+ private:
+ // per-namespace ribs
+ Rib value_rib;
+ Rib type_rib;
+ Rib label_rib;
+ Rib macro_rib;
+ // all linked nodes
+ std::map<Link, Node, LinkCmp> children;
+
+ NodeId id; // The node id of the Node's scope
+
+ tl::optional<Node &> parent; // `None` only if the node is a root
+ };
+
+ Node &get_root ();
+ const Node &get_root () const;
+
+ tl::optional<Node &> get_node (NodeId node_id);
+ tl::optional<const Node &> get_node (NodeId node_id) const;
+
+private:
+ Node root;
+};
+
template <Namespace N> class ForeverStack
{
public:
