https://gcc.gnu.org/g:c32d2dada8425762e26f537dde21f531100bb910
commit r17-3081-gc32d2dada8425762e26f537dde21f531100bb910 Author: Owen Avery <[email protected]> Date: Sun Jun 28 16:45:36 2026 -0400 gccrs: Unify node trees Each ForeverStack builds a tree of nodes. Since we already assume that nodes in one ForeverStack map one-to-one with nodes in another ForeverStack, we can have multiple ForeverStack instances share the same set of nodes. gcc/rust/ChangeLog: * resolve/rust-forever-stack.h (ForeverStackBase::Node::Node): Initialize all namespace ribs with a Rib::Kind. (ForeverStackBase::Node::rib): Replace member variable with member function taking namespace. (ForeverStackBase::Node::rib_values): New member variable. (ForeverStackBase::Node::rib_types): New member variable. (ForeverStackBase::Node::rib_labels): New member variable. (ForeverStackBase::Node::rib_macros): New member variable. (ForeverStackBase::ForeverStackBase): New constructor taking references to top-level nodes. (ForeverStack::root): Move member variable to... (ForeverStackBase::root): ...here and make it a reference. (ForeverStack::lang_prelude): Move member variable to... (ForeverStackBase::lang_prelude): ...here and make it a reference. (ForeverStack::extern_prelude): Move member variable to... (ForeverStackBase::extern_prelude): ...here and make it a reference. (ForeverStack::ForeverStack): Initialize ForeverStackBase and take top-level nodes as by-reference arguments. (ForeverStack::push_inner): Take Rib::Kind instead of Rib. * resolve/rust-forever-stack.hxx (ForeverStackBase::is_prelude): Use value rib to get rib kind. (ForeverStack::push_inner): Take Rib::Kind instead of Rib. (ForeverStack::pop): Use namespace specific ribs. (ForeverStack::insert_at_root): Likewise. (ForeverStack::insert_lang_prelude): Likewise. (ForeverStack::peek): Likewise. (ForeverStack::get): Likewise. (ForeverStack::get_lang_prelude): Likewise. (ForeverStack::find_closest_module): Likewise. (ForeverStack::dfs): Likewise. (ForeverStack::dfs_rib): Likewise. (ForeverStack::stream_node): Likewise. * resolve/rust-name-resolution-context.cc (NameResolutionContext::merge): Likewise. (NameResolutionContext::NameResolutionContext): Initialize top-level nodes and construct ForeverStack instances with references. * resolve/rust-name-resolution-context.h (NameResolutionContext::Node): New type alias to ForeverStackBase::Node. (NameResolutionContext::root): New member variable. (NameResolutionContext::lang_prelude): New member variable. (NameResolutionContext::extern_prelude): New member variable. * resolve/rust-name-resolution-context.hxx (NameResolutionContext::should_search_prelude): Use namespace specific rib. (NameResolutionContext::resolve_path): Simplify mapping to and from type namespace nodes (now a no-op). Also, use namespace specific ribs for looking up final segments. (NameResolutionContext::resolve_segments): Use namespace specific ribs. (NameResolutionContext::resolve_final_segment): Likewise. Signed-off-by: Owen Avery <[email protected]> Diff: --- gcc/rust/resolve/rust-forever-stack.h | 80 ++++++++++++++++------- gcc/rust/resolve/rust-forever-stack.hxx | 46 ++++++------- gcc/rust/resolve/rust-name-resolution-context.cc | 27 +++++--- gcc/rust/resolve/rust-name-resolution-context.h | 6 ++ gcc/rust/resolve/rust-name-resolution-context.hxx | 35 ++++------ 5 files changed, 117 insertions(+), 77 deletions(-) diff --git a/gcc/rust/resolve/rust-forever-stack.h b/gcc/rust/resolve/rust-forever-stack.h index 823868218131..0f95d0d73233 100644 --- a/gcc/rust/resolve/rust-forever-stack.h +++ b/gcc/rust/resolve/rust-forever-stack.h @@ -515,10 +515,36 @@ public: class Node { public: - Node (Rib rib, NodeId id) : rib (rib), id (id) {} - Node (Rib rib, NodeId id, Node &parent) - : rib (rib), id (id), parent (parent) + Node (Rib::Kind rib_kind, NodeId id) + : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind), + rib_macros (rib_kind), id (id) {} + Node (Rib::Kind rib_kind, NodeId id, Node &parent) + : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind), + rib_macros (rib_kind), id (id), parent (parent) + {} + + const Rib &rib (Namespace n) const + { + switch (n) + { + case Namespace::Values: + return rib_values; + case Namespace::Types: + return rib_types; + case Namespace::Labels: + return rib_labels; + case Namespace::Macros: + return rib_macros; + default: + rust_unreachable (); + } + } + + Rib &rib (Namespace n) + { + return const_cast<Rib &> (const_cast<const Node *> (this)->rib (n)); + } inline bool is_root () const; inline bool is_prelude () const; @@ -526,22 +552,44 @@ public: inline void insert_child (Link link, Node child); - Rib rib; // this is the "value" of the node - the data it keeps. + // these are the "values" of the node - the data it keeps. + Rib rib_values; + Rib rib_types; + Rib rib_labels; + Rib rib_macros; + 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 }; + + ForeverStackBase (Node &root, Node &lang_prelude, Node &extern_prelude) + : root (root), lang_prelude (lang_prelude), extern_prelude (extern_prelude) + {} + + /* The forever stack's actual nodes */ + Node &root; + + /* + * A special prelude node used currently for resolving language builtins + * It has the root node as a parent, and acts as a "special case" for name + * resolution + */ + Node &lang_prelude; + + /* + * The extern prelude, used for resolving external crates + */ + Node &extern_prelude; }; template <Namespace N> class ForeverStack : public ForeverStackBase { public: - ForeverStack () - : root (Node (Rib (Rib::Kind::Normal), UNKNOWN_NODEID)), - lang_prelude (Node (Rib (Rib::Kind::Prelude), UNKNOWN_NODEID, root)), - extern_prelude (Node (Rib (Rib::Kind::Prelude), UNKNOWN_NODEID)), + ForeverStack (Node &root, Node &lang_prelude, Node &extern_prelude) + : ForeverStackBase (root, lang_prelude, extern_prelude), cursor_reference (root) { rust_assert (root.is_root ()); @@ -686,7 +734,7 @@ public: }; /* Add a new Rib to the stack. This is an internal method */ - void push_inner (Rib rib, Link link); + void push_inner (Rib::Kind rib, Link link); /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */ void reverse_iter (std::function<KeepGoing (Node &)> lambda); @@ -702,20 +750,6 @@ public: void update_cursor (Node &new_cursor); - /* The forever stack's actual nodes */ - Node root; - /* - * A special prelude node used currently for resolving language builtins - * It has the root node as a parent, and acts as a "special case" for name - * resolution - */ - Node lang_prelude; - - /* - * The extern prelude, used for resolving external crates - */ - Node extern_prelude; - std::reference_wrapper<Node> cursor_reference; void stream_rib (std::stringstream &stream, const Rib &rib, diff --git a/gcc/rust/resolve/rust-forever-stack.hxx b/gcc/rust/resolve/rust-forever-stack.hxx index 3ed6692ffb4d..1b654c952caf 100644 --- a/gcc/rust/resolve/rust-forever-stack.hxx +++ b/gcc/rust/resolve/rust-forever-stack.hxx @@ -37,7 +37,7 @@ ForeverStackBase::Node::is_root () const bool ForeverStackBase::Node::is_prelude () const { - return rib.kind == Rib::Kind::Prelude; + return rib_values.kind == Rib::Kind::Prelude; } bool @@ -65,9 +65,9 @@ ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id, template <Namespace N> void -ForeverStack<N>::push_inner (Rib rib, Link link) +ForeverStack<N>::push_inner (Rib::Kind rib_kind, Link link) { - if (rib.kind == Rib::Kind::Prelude) + if (rib_kind == Rib::Kind::Prelude) { // If you push_inner into the prelude from outside the root, you will pop // back into the root, which could screw up a traversal. @@ -83,7 +83,7 @@ ForeverStack<N>::push_inner (Rib rib, Link link) // 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, link.id, cursor ()))); + std::make_pair (link, Node (rib_kind, link.id, cursor ()))); auto it = emplace.first; auto existed = !emplace.second; @@ -105,12 +105,12 @@ ForeverStack<N>::pop () rust_debug ("popping link"); - for (const auto &kv : cursor ().rib.get_values ()) + for (const auto &kv : cursor ().rib (N).get_values ()) rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (), kv.second.to_string ().c_str ()); if (cursor ().parent.has_value ()) - for (const auto &kv : cursor ().parent.value ().rib.get_values ()) + for (const auto &kv : cursor ().parent.value ().rib (N).get_values ()) rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (), kv.second.to_string ().c_str ()); @@ -161,7 +161,7 @@ template <Namespace N> tl::expected<NodeId, DuplicateNameError> ForeverStack<N>::insert_at_root (Identifier name, NodeId node) { - auto &root_rib = root.rib; + auto &root_rib = root.rib (N); // inserting in the root of the crate is never a shadowing operation, even for // macros @@ -207,7 +207,7 @@ template <Namespace N> inline void ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id) { - insert_inner (lang_prelude.rib, name.as_string (), + insert_inner (lang_prelude.rib (N), name.as_string (), Rib::Definition::NonShadowable (id, false)); } @@ -215,14 +215,14 @@ template <Namespace N> Rib & ForeverStack<N>::peek () { - return cursor ().rib; + return cursor ().rib (N); } template <Namespace N> const Rib & ForeverStack<N>::peek () const { - return cursor ().rib; + return cursor ().rib (N); } template <Namespace N> @@ -310,10 +310,10 @@ ForeverStack<N>::get (Node &start, const Identifier &name) // TODO: Can we improve the API? have `reverse_iter` return an optional? reverse_iter (start, [&resolved_definition, &name] (Node ¤t) { // we can't reference associated types/functions like this - if (current.rib.kind == Rib::Kind::TraitOrImpl) + if (current.rib (N).kind == Rib::Kind::TraitOrImpl) return KeepGoing::Yes; - auto candidate = current.rib.get (name.as_string ()); + auto candidate = current.rib (N).get (name.as_string ()); if (candidate) { @@ -329,7 +329,7 @@ ForeverStack<N>::get (Node &start, const Identifier &name) } else { - if (current.rib.kind == Rib::Kind::Module) + if (current.rib (N).kind == Rib::Kind::Module) return KeepGoing::No; else return KeepGoing::Yes; @@ -350,14 +350,14 @@ template <Namespace N> tl::optional<Rib::Definition> ForeverStack<N>::get_lang_prelude (const Identifier &name) { - return lang_prelude.rib.get (name.as_string ()); + return lang_prelude.rib (N).get (name.as_string ()); } template <Namespace N> tl::optional<Rib::Definition> ForeverStack<N>::get_lang_prelude (const std::string &name) { - return lang_prelude.rib.get (name); + return lang_prelude.rib (N).get (name); } template <Namespace N> @@ -380,10 +380,10 @@ tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get ( reverse_iter ([&resolved_definition, &name] (Node ¤t) { // looking up for labels cannot go through function ribs // TODO: What other ribs? - if (current.rib.kind == Rib::Kind::Function) + if (current.rib_labels.kind == Rib::Kind::Function) return KeepGoing::No; - auto candidate = current.rib.get (name.as_string ()); + auto candidate = current.rib_labels.get (name.as_string ()); // FIXME: Factor this in a function with the generic `get` return candidate.map_or ( @@ -421,7 +421,7 @@ ForeverStack<N>::find_closest_module (Node &starting_point) auto *closest_module = &starting_point; reverse_iter (starting_point, [&closest_module] (Node ¤t) { - if (current.rib.kind == Rib::Kind::Module || current.is_root ()) + if (current.rib (N).kind == Rib::Kind::Module || current.is_root ()) { closest_module = ¤t; return KeepGoing::No; @@ -526,7 +526,7 @@ template <Namespace N> tl::optional<typename ForeverStack<N>::DfsResult> ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find) { - auto values = starting_point.rib.get_values (); + auto values = starting_point.rib (N).get_values (); for (auto &kv : values) { @@ -557,7 +557,7 @@ tl::optional<typename ForeverStack<N>::ConstDfsResult> ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point, NodeId to_find) const { - auto values = starting_point.rib.get_values (); + auto values = starting_point.rib (N).get_values (); for (auto &kv : values) { @@ -588,7 +588,7 @@ tl::optional<Rib &> ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find) { return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & { - return x.rib; + return x.rib (N); }); } @@ -598,7 +598,7 @@ ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point, NodeId to_find) const { return dfs_node (starting_point, to_find) - .map ([] (const Node &x) -> const Rib & { return x.rib; }); + .map ([] (const Node &x) -> const Rib & { return x.rib (N); }); } template <Namespace N> @@ -692,7 +692,7 @@ ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation, << next << "is_leaf: " << (node.is_leaf () ? "true" : "false") << ",\n"; - stream_rib (stream, node.rib, next, next_next); + stream_rib (stream, node.rib (N), next, next_next); stream << indent << "}\n"; diff --git a/gcc/rust/resolve/rust-name-resolution-context.cc b/gcc/rust/resolve/rust-name-resolution-context.cc index 9444dc3a3bbd..cff4c9ecc18f 100644 --- a/gcc/rust/resolve/rust-name-resolution-context.cc +++ b/gcc/rust/resolve/rust-name-resolution-context.cc @@ -199,7 +199,16 @@ CanonicalPathRecordTraitImpl::as_path (const NameResolutionContext &ctx, } NameResolutionContext::NameResolutionContext () - : mappings (Analysis::Mappings::get ()), canonical_ctx (*this) + : root (std::make_unique<Node> (Rib::Kind::Normal, UNKNOWN_NODEID)), + lang_prelude ( + std::make_unique<Node> (Rib::Kind::Prelude, UNKNOWN_NODEID, *root)), + extern_prelude ( + std::make_unique<Node> (Rib::Kind::Prelude, UNKNOWN_NODEID)), + values (*root, *lang_prelude, *extern_prelude), + types (*root, *lang_prelude, *extern_prelude), + macros (*root, *lang_prelude, *extern_prelude), + labels (*root, *lang_prelude, *extern_prelude), + mappings (Analysis::Mappings::get ()), canonical_ctx (*this) {} tl::expected<NodeId, DuplicateNameError> @@ -390,7 +399,9 @@ NameResolutionContext::scoped (Rib::Kind rib_kind, Namespace ns, void NameResolutionContext::merge (NameResolutionContext &other, NodeId at) { - auto merge_fstack = [&] (auto &stack, auto &other_stack) { + // TODO: merge once, for all namespaces at once + + auto merge_fstack = [&] (auto &stack, auto &other_stack, Namespace ns) { auto node = stack.dfs_node (stack.root, at); if (node) { @@ -402,21 +413,21 @@ NameResolutionContext::merge (NameResolutionContext &other, NodeId at) extern_crate_node.insert_child (link, child); child.parent = extern_crate_node; } - for (auto kv : other_stack.root.rib.get_values ()) + for (auto kv : other_stack.root.rib (ns).get_values ()) { auto name = kv.first; auto def = kv.second; - extern_crate_node.rib.insert (name, def); + extern_crate_node.rib (ns).insert (name, def); } } stack.resolved_nodes.insert (other_stack.resolved_nodes.begin (), other_stack.resolved_nodes.end ()); }; - merge_fstack (values, other.values); - merge_fstack (types, other.types); - merge_fstack (macros, other.macros); - merge_fstack (labels, other.labels); + merge_fstack (values, other.values, Namespace::Values); + merge_fstack (types, other.types, Namespace::Types); + merge_fstack (macros, other.macros, Namespace::Macros); + merge_fstack (labels, other.labels, Namespace::Labels); canonical_ctx.merge (std::move (other.canonical_ctx)); } diff --git a/gcc/rust/resolve/rust-name-resolution-context.h b/gcc/rust/resolve/rust-name-resolution-context.h index 5aaea963154f..e30c5b59e42a 100644 --- a/gcc/rust/resolve/rust-name-resolution-context.h +++ b/gcc/rust/resolve/rust-name-resolution-context.h @@ -524,6 +524,12 @@ public: std::function<void (void)> lambda, tl::optional<Identifier> path = {}); + using Node = ForeverStackBase::Node; + + std::unique_ptr<Node> root; + std::unique_ptr<Node> lang_prelude; + std::unique_ptr<Node> extern_prelude; + ForeverStack<Namespace::Values> values; ForeverStack<Namespace::Types> types; ForeverStack<Namespace::Macros> macros; diff --git a/gcc/rust/resolve/rust-name-resolution-context.hxx b/gcc/rust/resolve/rust-name-resolution-context.hxx index 7de8da097fef..3c9c6a3d9a76 100644 --- a/gcc/rust/resolve/rust-name-resolution-context.hxx +++ b/gcc/rust/resolve/rust-name-resolution-context.hxx @@ -42,7 +42,7 @@ NameResolutionContext::should_search_prelude ( // Check whether we're at the start of a module (we can't travel elsewhere // from the start of a module) if (is_start (iterator, segments) - && current_node->rib.kind == Rib::Kind::Module) + && current_node->rib (N).kind == Rib::Kind::Module) return true; return false; @@ -203,31 +203,20 @@ NameResolutionContext::resolve_path ( // We do the first part of path resolution exclusively in the types NS - this // gives us a node in which to resolve the last segment of the path. - // We take our starting point and then get the equivalent Node from the Types - // NS - since it existed in whatever namespace we are right now, we assume it - // exists in the types NS. - auto types_starting_point - = types.dfs_node (types.root, starting_point.get ().id); - - // TODO: Add a method for converting a node between namespaces? Make all of - // the starting point stuff return a NodeId rather than a Node&? And take a - // NodeId as a starting point rather than a Node? - + // nodes are shared between stacks auto node - = resolve_segments (types, types_starting_point.value (), segments, - iterator, insert_segment_resolution, collect_errors); + = resolve_segments (types, starting_point.get (), segments, iterator, + insert_segment_resolution, collect_errors); if (!node) return tl::nullopt; // This node now represents the Node which *should* contain the definition - // used by the last segment. We now get the equivalent Node from this - // namespace after finding it in the types NS. - auto final_node_id = node.value ().id; - auto final_node = stack.dfs_node (stack.root, final_node_id).value (); + // used by the last segment. + auto &final_node = node.value (); // leave resolution within impl blocks to type checker - if (final_node.rib.kind == Rib::Kind::TraitOrImpl) + if (final_node.rib (N).kind == Rib::Kind::TraitOrImpl) return tl::nullopt; auto &seg = segments.back (); @@ -294,7 +283,7 @@ NameResolutionContext::resolve_segments ( while (true) { if (is_start (iterator, segments) - && current_node->rib.kind == Rib::Kind::TraitOrImpl) + && current_node->rib (N).kind == Rib::Kind::TraitOrImpl) { // we can't reference associated types/functions like this current_node = ¤t_node->parent.value (); @@ -323,7 +312,7 @@ NameResolutionContext::resolve_segments ( break; } - auto rib_lookup = current_node->rib.get (seg.name); + auto rib_lookup = current_node->rib (N).get (seg.name); if (rib_lookup && !rib_lookup->is_ambiguous ()) { if (Analysis::Mappings::get () @@ -369,7 +358,7 @@ NameResolutionContext::resolve_segments ( } if (!is_start (iterator, segments) - || current_node->rib.kind == Rib::Kind::Module + || current_node->rib (N).kind == Rib::Kind::Module || current_node->is_prelude ()) { return tl::nullopt; @@ -398,7 +387,7 @@ NameResolutionContext::resolve_final_segment ( if (is_lower_self) return Rib::Definition::NonShadowable (final_node.id); else - return final_node.rib.get (seg_name); + return final_node.rib_types.get (seg_name); } template <Namespace N> @@ -407,7 +396,7 @@ NameResolutionContext::resolve_final_segment ( ForeverStack<N> &stack, typename ForeverStack<N>::Node &final_node, std::string &seg_name, bool is_lower_self) { - return final_node.rib.get (seg_name); + return final_node.rib (N).get (seg_name); } } // namespace Resolver2_0
