From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by sourceware.org (Postfix) with ESMTPS id B1E373858035 for ; Tue, 30 Jan 2024 12:10:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B1E373858035 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=embecosm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=embecosm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org B1E373858035 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::32d ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1706616663; cv=none; b=rdQoEcwbW8ZAoGkfO9vkftZdpOiT3bce7/Y0Hbi0XCirpdLoHjqgZlTDQxk4+eECVuGqrhmKmmYUvBc37XTkK8hk50Frt7VSDzvoYDcDIzGPNY0PpgdGNEnLL26ryO+LfvC32lSwg9nUd2SzCr+KeCBiyeI7KEv95Tgg6qsipr0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1706616663; c=relaxed/simple; bh=vVoXioeFEmJ9J7I3VRvk/12lq1KUVEzC++eRzh9faBI=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=DNZIIlDgTXlReNM5A/slytdePrSrmMwjw3mFqsUsp+EOc84A1PueqBJjjhedF+iAS/U6+s0WuT2ej6rQI6FIdYFsM25iZhktTxCuqLWyY2NG6B7j485G/fFvwEfrnRSio6HASvnTlvvYKxXTfUOSRP6JvUkR9sck+BIc0/pLFzo= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x32d.google.com with SMTP id 5b1f17b1804b1-40e7e2e04f0so44308415e9.1 for ; Tue, 30 Jan 2024 04:10:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=embecosm.com; s=google; t=1706616658; x=1707221458; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:reply-to:references :in-reply-to:message-id:date:subject:cc:to:from:from:to:cc:subject :date:message-id:reply-to; bh=zMaBmClI87H01KBkQpbYdoKmuuYOGOFP18Y59AXZt14=; b=JLqAxKbQWkWpZY7yhl3be09MGSwiNMANaIuAJefHj6V06ddd00lSTl9c8XaxzQpoNX UwJYgCbaDMr/nL94Gkcb3nn4CSwKyeWodd8jCO9i9o3rqXNqe4vpfMriD3BRqsR7wsm9 w27SIdIe9CshHbRlxay3Fs+Z/vlsUWXA93+gDNjRi4kjKCEIi0xM3EBWWKr7Zn24qVWz ePVi9cn6pOW5ZF2eif4XTFX5K1rShBlQi3zW9l3Lrb37yPQ7R8ZQ83Tsa4StEP+fB79T BIrSueF2nudtTJS6W2zEsWbS16OMlxfXpOZdheYz/RweiaznJ2BO7fw65E9MG9yhk3ev x+Vg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1706616658; x=1707221458; h=content-transfer-encoding:mime-version:reply-to:references :in-reply-to:message-id:date:subject:cc:to:from:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=zMaBmClI87H01KBkQpbYdoKmuuYOGOFP18Y59AXZt14=; b=G6NhjvPMRyRsd4ouwzOaka9LFaWI/6M+25YieMkJUH/xwpREmvcxAJCOxAk6fb23fm 3lQ3t5RWUfIbGrks0VuCHbIqI6n/Op+SEmBSWMUCOByYYPGXhl7zZu7gCNfrr+lOKt9A RF3q1u32wiSvRS4hBRGcbO9aJlFC3Olbu8+J6uJFzCYPuXu63/eN679EPjxzl/Ve4Lmn zUeWznhLnJNoDTwwCGpT+WXpu2xssfUZdL/AN4h77amsOZHqwLuolyPbPVevLzFqsPP8 kz6X/BLyNeO+ubm4sgoALhrFMYPIC5bLI9MVeOgYlGUyLcpd95+zt+oSti8cVLf1X100 eFZg== X-Gm-Message-State: AOJu0Yype02Hf4Hwdv8AbhVqQmpgw4JoFlLmaM/gDq0v8NFG+A/lP9mZ 5NNBvsqF0/AW0k4MoNnhfMCTp3HcIh3dNMeOZ7lhPCtJiTvspuwVXIjyOOFyJ70Y8NjggJMciYG QUA== X-Google-Smtp-Source: AGHT+IHzBslxj2tdVBdzpxNjBkBAwf2CFSo12EsVdXc3EfwuRKIlMAbxlRp906dDBB81TJkt1eWENg== X-Received: by 2002:adf:fecc:0:b0:33a:e89f:1dc6 with SMTP id q12-20020adffecc000000b0033ae89f1dc6mr4239751wrs.29.1706616658443; Tue, 30 Jan 2024 04:10:58 -0800 (PST) Received: from platypus.localdomain ([62.23.166.218]) by smtp.gmail.com with ESMTPSA id f9-20020a056000036900b00339307d9d31sm10569894wrf.112.2024.01.30.04.10.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 30 Jan 2024 04:10:58 -0800 (PST) From: arthur.cohen@embecosm.com To: gcc-patches@gcc.gnu.org Cc: gcc-rust@gcc.gnu.org, Arthur Cohen Subject: [COMMITTED 012/101] gccrs: foreverstack: Add `to_canonical_path` method Date: Tue, 30 Jan 2024 13:06:28 +0100 Message-ID: <20240130121026.807464-15-arthur.cohen@embecosm.com> X-Mailer: git-send-email 2.42.1 In-Reply-To: <20240130121026.807464-2-arthur.cohen@embecosm.com> References: <20240130121026.807464-2-arthur.cohen@embecosm.com> Reply-To: arthur.cohen@embecosm.com MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-14.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: From: Arthur Cohen 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 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 642135cda85..4e06da235bf 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, -- 2.42.1