From patchwork Tue Jan 30 12:06:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Arthur Cohen X-Patchwork-Id: 194053 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2087:b0:106:209c:c626 with SMTP id gs7csp1178493dyb; Tue, 30 Jan 2024 04:19:35 -0800 (PST) X-Google-Smtp-Source: AGHT+IEIEcn/0VOrKuXvz1z75F5L/6C1wOekiltab1qiXmxztTNytKuaqXfk4NoAPRoQmnv87dvh X-Received: by 2002:a05:622a:156:b0:42a:a4d5:966f with SMTP id v22-20020a05622a015600b0042aa4d5966fmr4764437qtw.113.1706617175188; Tue, 30 Jan 2024 04:19:35 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1706617175; cv=pass; d=google.com; s=arc-20160816; b=OhQI0EF7rmSbqPuFb2TIlqD53DYzUaV2dMPyTZ9+tcVM401lXW94qBSFeWb1f3PPM+ 8gBhqhEe8SclvQ6WzZczKqr0AZgTmnW4gePDYu6bmm+WdOcn+km0O+bNqyzqwXh8x86e XQG9DuLbqyyDa+WPzBQcGTf4EUKEQInnSJwT2a0FLgs5aMK6lkJz9ghJWKThNEF2NuUS 7vDjYNV5rGQW/IiPzF8w+jmXrtrcPd6b171Q2a2P0+0v+5LGbRIOJFwhSKg/u0Klk7Qn OvCqQXvWBbvErJngB2q8N6U3CRHUzXepEwsaH5CHuSbN6EqKLa7xVw+EHByQKZGIZlBy i3Mg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:reply-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature:arc-filter:dmarc-filter:delivered-to; bh=zMaBmClI87H01KBkQpbYdoKmuuYOGOFP18Y59AXZt14=; fh=6KiXNvQww/MsyVplklPLl//mUuD+DtDm73nSHh4O4+g=; b=hbwV61b4k1JlekFZb6fFwWRg9SJpUak4v5aWD9TOcShmI4Lp8RsZQiBzw0KFACGjzQ P4vif2nkBwQqHWw8Xt7q7P/wjgM2PrnM/F1DJz9tfKg8w4NHHA1hio/uYgGGI5FYFgnx oX0Pi7o5V+Lz05tI63HdicnIdlJppE3CKj+V9UxgEcn9pIjB+BRaXRUzM0dy6jAR4tQv L4Pt3DRFMHjCAviQEK6DjrX2cYH9ylOUHOeYWti818SplQ4TA0dOihN/Mo1tGU1/KHef s6VD03P6sTgFhl8NOoZLzDNHSkkLQXLbPcjkNrmiQHH7wG3a5vGzeugypzZlTkb0tsYs Vumw== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@embecosm.com header.s=google header.b=JLqAxKbQ; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org" Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id c9-20020ac85a89000000b00429aeece0a5si9664014qtc.796.2024.01.30.04.19.35 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 30 Jan 2024 04:19:35 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@embecosm.com header.s=google header.b=JLqAxKbQ; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org" Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C2A5A3858024 for ; Tue, 30 Jan 2024 12:19:34 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x42d.google.com (mail-wr1-x42d.google.com [IPv6:2a00:1450:4864:20::42d]) by sourceware.org (Postfix) with ESMTPS id 5D12138582A3 for ; Tue, 30 Jan 2024 12:11:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5D12138582A3 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 5D12138582A3 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::42d ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1706616666; cv=none; b=v6wLaSkrX5sykNECFCojtfeByxed4iDRv2J7aInAijnczG6emEcazFfHzCUxDaTYmN2hC9X8fjj3Os3Wb7RsvXkN7RuEpfehyRKSDw+Ej8MOFy0mIvywun6wHFTAZoMvx0a5RhDYEhlpaxh6HkkqC5hEQFn4+C8tf66JJrc7Lhc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1706616666; c=relaxed/simple; bh=vVoXioeFEmJ9J7I3VRvk/12lq1KUVEzC++eRzh9faBI=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=XQFFXS40HMewjDC8ROUpCVoctZSpp3sW/CGfOsDMaUZAkjhPWS1hKwhLfOrOk7ayVK0yIgHADdWAHixKL+5H5F15KFKLkAUiL4EYbCOR4QYZs9fdX/WR5v9f4r3ycUlZwaz4P+owBvgAkLejiPaERw1tGs2mlakXi72BweXdubs= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wr1-x42d.google.com with SMTP id ffacd0b85a97d-33aef64f702so1046640f8f.3 for ; Tue, 30 Jan 2024 04:11:00 -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=oTjk1Icqcupra0MIcsRFA5orGC0fkC83/1uzhiYVUd+YSlSZEHmV8v9p2moDRjF7rv F6PwOUjIobHvHErbMj2adoOAeOw6ZLkeJ36A1qh6z7Ok2ckEhnRPuNFPSJxIr8NV2M0o hJS23X6UDzzIp/Ds7AXXUo41o2IxKSZ4ezjqi8HziXIdslzA7p9ynhR6n8P9J+T8HRZ8 QBqplKmDijzofkcp+Pe0006gFMDR0xBrFlx0XSucJ1fS1x9eNXrw7Zb6/euL8eb6vELY juG/yZqp6HjtHxpat5edMDjwnI936iZ53SJKlxwxqs8gBr8/ED8TUJ7Z2mh03SmW9hKE hSkA== X-Gm-Message-State: AOJu0YzBi3gD9wrkni+g/bYVVUshDTYeJ68/FkzSmqRlm9SBz1WRw++s U7o9/91k6PMkMndzVHtkL9I+tWUnzwiW+EEQpJUWFBSTMEikcgM8BT/NTs6Dtx9Ktosr4ApcM1s WqQ== 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> MIME-Version: 1.0 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=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: arthur.cohen@embecosm.com Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1789517811075043446 X-GMAIL-MSGID: 1789517811075043446 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,