public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Arthur Cohen <cohenarthur@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc r14-7884] gccrs: forever stack: Add path resolution Date: Tue, 16 Jan 2024 18:04:19 +0000 (GMT) [thread overview] Message-ID: <20240116180419.78D5A3858029@sourceware.org> (raw) https://gcc.gnu.org/g:79d8fb09c626213cdbe020ab13dac70107a8fee1 commit r14-7884-g79d8fb09c626213cdbe020ab13dac70107a8fee1 Author: Arthur Cohen <arthur.cohen@embecosm.com> Date: Thu Jul 20 17:52:14 2023 +0200 gccrs: forever stack: Add path resolution gcc/rust/ChangeLog: * resolve/rust-forever-stack.h (insert_at_root): New method. (resolve_path): New method. (reverse_iter): Iterate on `Node`s instead of `Rib`s * resolve/rust-forever-stack.hxx: Add path resolution. Diff: --- gcc/rust/resolve/rust-forever-stack.h | 49 +++++- gcc/rust/resolve/rust-forever-stack.hxx | 273 ++++++++++++++++++++++++++++++-- 2 files changed, 302 insertions(+), 20 deletions(-) diff --git a/gcc/rust/resolve/rust-forever-stack.h b/gcc/rust/resolve/rust-forever-stack.h index ff4221bd2ba..7ee08491987 100644 --- a/gcc/rust/resolve/rust-forever-stack.h +++ b/gcc/rust/resolve/rust-forever-stack.h @@ -434,6 +434,21 @@ public: */ tl::expected<NodeId, DuplicateNameError> insert (Identifier name, NodeId id); + /** + * Insert a new definition at the root of this stack + * + * @param name The name of the definition + * @param id Its NodeId + * + * @return `DuplicateNameError` if that node was already present in the Rib, + * the node's `NodeId` otherwise. + * + * @aborts if there are no `Rib`s inserted in the current map, this function + * aborts the program. + */ + tl::expected<NodeId, DuplicateNameError> insert_at_root (Identifier name, + NodeId id); + /* Access the innermost `Rib` in this map */ Rib &peek (); const Rib &peek () const; @@ -450,10 +465,16 @@ public: * @return a valid option with the NodeId if the identifier is present in the * current map, an empty one otherwise. */ - inline tl::optional<NodeId> get (const Identifier &name); + tl::optional<NodeId> get (const Identifier &name); + + /** + * Resolve a path to its definition in the current `ForeverStack` + * + * @return a valid option with the NodeId if the path is present in the + * current map, an empty one otherwise. + */ + tl::optional<NodeId> resolve_path (const AST::SimplePath &path); - // TODO: Should we dump to a file instead, like the other dumps? Or just print - // the string to a file in the SessionManager? std::string as_debug_string (); private: @@ -509,8 +530,11 @@ private: /* Add a new Rib to the stack. This is an internal method */ void push_inner (Rib rib, Link link); - /* Reverse iterate on all Ribs from the current one, in an outwards fashion */ - void reverse_iter (std::function<KeepGoing (Rib &)> lambda); + /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */ + void reverse_iter (std::function<KeepGoing (Node &)> lambda); + + /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */ + void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda); Node &cursor (); const Node &cursor () const; @@ -523,6 +547,21 @@ private: const std::string &next, const std::string &next_next); void stream_node (std::stringstream &stream, unsigned indentation, const Node &node); + + /* Helper types and functions for `resolve_path` */ + + using SegIterator = std::vector<AST::SimplePathSegment>::const_iterator; + + Node &find_closest_module (Node &starting_point); + + tl::optional<SegIterator> + find_starting_point (const std::vector<AST::SimplePathSegment> &segments, + Node &starting_point); + + tl::optional<Node &> + resolve_segments (Node &starting_point, + const std::vector<AST::SimplePathSegment> &segments, + SegIterator iterator); }; } // namespace Resolver2_0 diff --git a/gcc/rust/resolve/rust-forever-stack.hxx b/gcc/rust/resolve/rust-forever-stack.hxx index c961e2b32ed..8bdda67782a 100644 --- a/gcc/rust/resolve/rust-forever-stack.hxx +++ b/gcc/rust/resolve/rust-forever-stack.hxx @@ -16,6 +16,9 @@ // 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" @@ -47,7 +50,6 @@ ForeverStack<N>::Node::insert_child (Link link, Node child) // That's kinda the point, isn't it. So this method always succeeds, right? } -// FIXME: Add correct implementation template <Namespace N> void ForeverStack<N>::push (Rib rib, NodeId id, tl::optional<Identifier> path) @@ -97,6 +99,12 @@ ForeverStack<N>::pop () update_cursor (cursor ().parent.value ()); } +static tl::expected<NodeId, DuplicateNameError> +insert_inner (Rib &rib, std::string name, NodeId node, bool can_shadow) +{ + return rib.insert (name, node, can_shadow); +} + template <Namespace N> tl::expected<NodeId, DuplicateNameError> ForeverStack<N>::insert (Identifier name, NodeId node) @@ -107,7 +115,34 @@ ForeverStack<N>::insert (Identifier name, NodeId node) // 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 innermost_rib.insert (name.as_string (), node); + return insert_inner (innermost_rib, name.as_string (), node, false); +} + +template <Namespace N> +tl::expected<NodeId, DuplicateNameError> +ForeverStack<N>::insert_at_root (Identifier name, NodeId node) +{ + auto &root_rib = root.rib; + + // inserting in the root of the crate is never a shadowing operation, even for + // macros + return insert_inner (root_rib, name.as_string (), node, false); +} + +// Specialization for Macros and Labels - where we are allowed to shadow +// existing definitions +template <> +inline tl::expected<NodeId, DuplicateNameError> +ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node) +{ + return insert_inner (peek (), name.as_string (), node, true); +} + +template <> +inline tl::expected<NodeId, DuplicateNameError> +ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node) +{ + return insert_inner (peek (), name.as_string (), node, true); } template <Namespace N> @@ -126,20 +161,28 @@ ForeverStack<N>::peek () const template <Namespace N> void -ForeverStack<N>::reverse_iter (std::function<KeepGoing (Rib &)> lambda) +ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda) { - auto &tmp = cursor (); + return reverse_iter (cursor (), lambda); +} + +template <Namespace N> +void +ForeverStack<N>::reverse_iter (Node &start, + std::function<KeepGoing (Node &)> lambda) +{ + auto *tmp = &start; while (true) { - auto keep_going = lambda (tmp); + auto keep_going = lambda (*tmp); if (keep_going == KeepGoing::No) return; - if (tmp.is_root ()) + if (tmp->is_root ()) return; - tmp = tmp.parent.value (); + tmp = &tmp->parent.value (); } } @@ -168,16 +211,216 @@ template <Namespace N> tl::optional<NodeId> ForeverStack<N>::get (const Identifier &name) { - return {}; + return tl::nullopt; } -// TODO: Are there different fetching behavior for different namespaces? -// inline template <> -// tl::optional<NodeId> -// ForeverStack<Namespace::Values>::get (const Identifier &name) -// { -// return {}; -// } +template <> +inline tl::optional<NodeId> +ForeverStack<Namespace::Macros>::get (const Identifier &name) +{ + tl::optional<NodeId> resolved_node = tl::nullopt; + + // TODO: Can we improve the API? have `reverse_iter` return an optional? + reverse_iter ([&resolved_node, &name] (Node ¤t) { + auto candidate = current.rib.get (name.as_string ()); + + return candidate.map_or ( + [&resolved_node] (NodeId found) { + // macro resolving does not need to care about various ribs - they are + // available from all contexts if defined in the current scope, or an + // outermore one. so if we do have a candidate, we can return it + // directly and stop iterating + resolved_node = found; + + return KeepGoing::No; + }, + // if there was no candidate, we keep iterating + KeepGoing::Yes); + }); + + return resolved_node; +} + +/* Check if an iterator points to the last element */ +template <typename I, typename C> +static bool +is_last (const I &iterator, const C &collection) +{ + return iterator + 1 == collection.end (); +} + +/* Check if an iterator points to the start of the collection */ +template <typename I, typename C> +static bool +is_start (const I &iterator, const C &collection) +{ + return iterator == collection.begin (); +} + +template <Namespace N> +typename ForeverStack<N>::Node & +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 ()) + { + closest_module = ¤t; + return KeepGoing::No; + } + + return KeepGoing::Yes; + }); + + return *closest_module; +} + +/* If a the given condition is met, emit an error about misused leading path + * segments */ +static inline bool +check_leading_kw_at_start (const AST::SimplePathSegment &segment, + bool condition) +{ + if (condition) + rust_error_at ( + segment.get_locus (), ErrorCode::E0433, + "leading path segment %qs can only be used at the beginning of a path", + segment.as_string ().c_str ()); + + return condition; +} + +// we first need to handle the "starting" segments - `super`, `self` or +// `crate`. we don't need to do anything for `self` and can just skip it. for +// `crate`, we need to go back to the root of the current stack. for each +// `super` segment, we go back to the cursor's parent until we reach the +// correct one or the root. +template <Namespace N> +tl::optional<std::vector<AST::SimplePathSegment>::const_iterator> +ForeverStack<N>::find_starting_point ( + const std::vector<AST::SimplePathSegment> &segments, Node &starting_point) +{ + auto iterator = segments.begin (); + + // If we need to do path segment resolution, then we start + // at the closest module. In order to resolve something like `foo::bar!()`, we + // need to get back to the surrounding module, and look for a child module + // named `foo`. + if (segments.size () > 1) + starting_point = find_closest_module (starting_point); + + for (; !is_last (iterator, segments); iterator++) + { + auto seg = *iterator; + auto is_self_or_crate = seg.is_crate_path_seg () || seg.is_lower_self (); + + // if we're after the first path segment and meet `self` or `crate`, it's + // an error - we should only be seeing `super` keywords at this point + if (check_leading_kw_at_start (seg, !is_start (iterator, segments) + && is_self_or_crate)) + return tl::nullopt; + + if (seg.is_crate_path_seg ()) + { + starting_point = root; + iterator++; + break; + } + if (seg.is_lower_self ()) + { + // do nothing and exit + iterator++; + break; + } + if (seg.is_super_path_seg ()) + { + if (starting_point.is_root ()) + { + rust_error_at (seg.get_locus (), ErrorCode::E0433, + "too many leading %<super%> keywords"); + return tl::nullopt; + } + + starting_point = find_closest_module (starting_point.parent.value ()); + continue; + } + + // now we've gone through the allowed `crate`, `self` or leading `super` + // segments. we can start resolving each segment itself. + // if we do see another leading segment, then we can error out. + break; + } + + return iterator; +} + +template <Namespace N> +tl::optional<typename ForeverStack<N>::Node &> +ForeverStack<N>::resolve_segments ( + Node &starting_point, const std::vector<AST::SimplePathSegment> &segments, + std::vector<AST::SimplePathSegment>::const_iterator iterator) +{ + auto *current_node = &starting_point; + for (; !is_last (iterator, segments); iterator++) + { + auto &seg = *iterator; + auto str = seg.as_string (); + rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ()); + + // check that we don't encounter *any* leading keywords afterwards + if (check_leading_kw_at_start (seg, seg.is_crate_path_seg () + || seg.is_super_path_seg () + || seg.is_lower_self ())) + return tl::nullopt; + + tl::optional<typename ForeverStack<N>::Node &> child = tl::nullopt; + + for (auto &kv : current_node->children) + { + auto &link = kv.first; + + if (link.path.map_or ( + [&str] (Identifier path) { + auto &path_str = path.as_string (); + return str == path_str; + }, + false)) + { + child = kv.second; + break; + } + } + + if (!child.has_value ()) + { + rust_error_at (seg.get_locus (), ErrorCode::E0433, + "failed to resolve path segment %qs", str.c_str ()); + return tl::nullopt; + } + + current_node = &child.value (); + } + + return *current_node; +} + +template <Namespace N> +tl::optional<NodeId> +ForeverStack<N>::resolve_path (const AST::SimplePath &path) +{ + auto starting_point = cursor (); + auto &segments = path.get_segments (); + + return find_starting_point (segments, starting_point) + .and_then ([this, &segments, &starting_point] ( + std::vector<AST::SimplePathSegment>::const_iterator iterator) { + return resolve_segments (starting_point, segments, iterator); + }) + .and_then ([&path] (Node final_node) { + return final_node.rib.get (path.get_final_segment ().as_string ()); + }); +} template <Namespace N> void
reply other threads:[~2024-01-16 18:04 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20240116180419.78D5A3858029@sourceware.org \ --to=cohenarthur@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).