From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7905) id C37903858296; Tue, 30 Jan 2024 11:57:47 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C37903858296 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1706615867; bh=naqSWAeAL9e9FsVE83eMmbn6jk6JrKUzdsJWUzDgUwE=; h=From:To:Subject:Date:From; b=yMXrBQL6/feqbK07DMUlRCHn0g5fO5ACdP160uvImtvcWiWUc28wANaJmD8Pkx1+7 AG5opQGd3DQM2w3Kfd7MskyJ5M54ANhedaldWLwKAtYkHerWPRmya5A20QTuoJkcY0 WzI2QymyEYrWAxU+LMTnLZBUO0G9k6l14+qHgliM= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Arthur Cohen To: gcc-cvs@gcc.gnu.org Subject: [gcc r14-8536] gccrs: foreverstack: Add `to_canonical_path` method X-Act-Checkin: gcc X-Git-Author: Arthur Cohen X-Git-Refname: refs/heads/trunk X-Git-Oldrev: 66e8a1614e4cc9d3eb92f1288cf19a805b21ac1a X-Git-Newrev: 12b2dcb088104c0682f501d0c87ba0b640bbb86b Message-Id: <20240130115747.C37903858296@sourceware.org> Date: Tue, 30 Jan 2024 11:57:47 +0000 (GMT) List-Id: https://gcc.gnu.org/g:12b2dcb088104c0682f501d0c87ba0b640bbb86b commit r14-8536-g12b2dcb088104c0682f501d0c87ba0b640bbb86b Author: Arthur Cohen Date: Fri Aug 25 13:40:44 2023 +0200 gccrs: foreverstack: Add `to_canonical_path` method gcc/rust/ChangeLog: * resolve/rust-forever-stack.h: New method. * resolve/rust-forever-stack.hxx: Likewise. Diff: --- 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 ec469a9b3fa0..37277ddb3ada 100644 --- a/gcc/rust/resolve/rust-forever-stack.h +++ b/gcc/rust/resolve/rust-forever-stack.h @@ -396,7 +396,10 @@ template 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 tl::optional resolve_path (const std::vector &segments); + // FIXME: Documentation + tl::optional to_canonical_path (NodeId id); + + // FIXME: Documentation + tl::optional 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 children; // all the other nodes it links to + NodeId id; // The node id of the Node's scope + tl::optional parent; // `None` only if the node is a root }; @@ -566,6 +579,12 @@ private: tl::optional resolve_segments (Node &starting_point, const std::vector &segments, SegIterator iterator); + + /* Helper functions for forward resolution (to_canonical_path, to_rib...) */ + + // FIXME: Documentation + tl::optional> 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 642135cda854..4e06da235bfa 100644 --- a/gcc/rust/resolve/rust-forever-stack.hxx +++ b/gcc/rust/resolve/rust-forever-stack.hxx @@ -66,8 +66,8 @@ ForeverStack::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::resolve_path (const std::vector &segments) }); } +template +tl::optional::Node &, std::string>> +ForeverStack::dfs (ForeverStack::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 +tl::optional +ForeverStack::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 tuple) { + auto containing_node = tuple.first; + auto name = tuple.second; + + auto segments = std::vector (); + + reverse_iter (containing_node, [&segments] (Node ¤t) { + 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 +tl::optional +ForeverStack::to_rib (NodeId rib_id) +{ + return tl::nullopt; +} + template void ForeverStack::stream_rib (std::stringstream &stream, const Rib &rib,