From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x336.google.com (mail-wm1-x336.google.com [IPv6:2a00:1450:4864:20::336]) by sourceware.org (Postfix) with ESMTPS id 3C42B38582B8 for ; Wed, 7 Feb 2024 12:44:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3C42B38582B8 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 3C42B38582B8 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::336 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707309850; cv=none; b=aX8pIR79K8ISv9g2Hy/8hF+QrhNF4zAIejxHV5q7he9u7j2Rcct4ecIHZOpleNNM/eI4lZCsSyp3Vt6dOoB0iR3hN8Fnajvre494MC/2WjsrsP/6ASBJICd0mpVLLKGqok+e9LCCZq05ob9vA0hviF+aRlATBXbO8g77xaBvZiI= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707309850; c=relaxed/simple; bh=uHg4IP/dvxwMcUZUo9C7ifmZgCEXCtKnf8B0yDv6EUE=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=hROCqbsBGVVIDRwhejs0nk7LU+K27PZfS0gXkYYsz3nHtAUiSYAImyTXrhoaDmTasskJZGQ+cXLgWyzZKYnxgFpS/gguKd8I1VjJk/Xv7JlIYmOim3fWhYlodLzx4mwugkpKcDUs/Q8Gs2KhijQOW9Vav6Fp1z9fgP3mtvmGapE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x336.google.com with SMTP id 5b1f17b1804b1-40ffd94a707so5450885e9.1 for ; Wed, 07 Feb 2024 04:44:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=embecosm.com; s=google; t=1707309842; x=1707914642; 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=Pmbia0Ja5DofaWXsNu8NNxlCcgcjAjU2zGNjFNjhQ/A=; b=gUprqfDhgLlTbCTW2JyDuemKtjYz080WwXzzAPl55Ft7XhclfIKlggosOgiPKfFjDc L6sihNH7rU5y8G+C1/9n0WQQkuKJCbqyEc5PyNa540u1eFsDDLfcivHnSRfr+R6KeKnV wL/HXqtHlSnQwx9LN88IWIHfry3nxZD4fbX1/GY9ssca5wJyqhunhEyRdb89P8px6VF4 b0m+6qCjZusSFPVgvVFqtOZOblFQTQohwJP86DmpgmgfaCClx3lLkCubOjrxgSefDOJU lupwpHCdog9OpKtbsdetwwxO5gxhUq4Xgq9HqRB+mDerhSgt2DiwPO9uKwGJLd8mjXBL hqdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707309842; x=1707914642; 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=Pmbia0Ja5DofaWXsNu8NNxlCcgcjAjU2zGNjFNjhQ/A=; b=UmtD2kzKDS3e7y9kJe0atY8WbP6kN5l9z3pTwA4f5AWcjGompCfMb/hN7PCW1e43gL KU1vHAc1X+/fSYFkWTmwpwMIP6NqE35Kwt6FsvN9xsNX5ilBPA1Fh8uB/0ZWsnfFpt8y usj9bGmT2gnE2ZCc8VleemFEbPQYmUzEAFbCNtaFBLUCca28vyc1FRQHHBL2tPHIct3E P3vml5w9XaRJjnX+NaVNrloWPnUBtMYDW7pH7Eg/VWNX9ekEnoLdXFt0BokDaPm775gh Dce1g+3w/+jxUGo+pqL2C5TzUlB/p1xlUxQzLnCXMBuecqutStR0zPh/JTUn3GqSujf0 Sl7A== X-Gm-Message-State: AOJu0YyzREp26GpBULrpj9xbF7nFStFC4prl6NgD537d28+xAh8tVl96 U/wDOzXTwrhWTcT75ctcnKrSoIy50hRh/TRXzvWZ42bVnJPbfpwqpHAdMrjkCT8PNKRRfRn6qYb mhw== X-Google-Smtp-Source: AGHT+IHW2S+oOkrvEGN7wq7EWrn3hFFuQ5Fjl/hTZzRIXbpQ/w9FgnLYcYHfZ5lFTXKu7A2uyZdufg== X-Received: by 2002:a05:600c:1d89:b0:40f:ecd4:7ef0 with SMTP id p9-20020a05600c1d8900b0040fecd47ef0mr3452099wms.24.1707309841934; Wed, 07 Feb 2024 04:44:01 -0800 (PST) X-Forwarded-Encrypted: i=1; AJvYcCW9EcW5i8PKTF23gFoDq0P5DOP05bEG8i3O56rfHhH8YaByXdAp+jR3qsIlSomThfQxq45bk/0LYC4s2CavZSXugDw= Received: from platypus.sou.embecosm-corp.com ([212.69.42.53]) by smtp.gmail.com with ESMTPSA id x19-20020a05600c2a5300b0040fbdd6f69bsm5044188wme.33.2024.02.07.04.44.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Feb 2024 04:44:01 -0800 (PST) From: arthur.cohen@embecosm.com To: gcc-patches@gcc.gnu.org Cc: gcc-rust@gcc.gnu.org, Jakub Dupak Subject: [COMMITTED 03/25] gccrs: Typecheck: lifetime interning and resolution tool Date: Wed, 7 Feb 2024 12:43:49 +0100 Message-ID: <20240207114419.1100894-4-arthur.cohen@embecosm.com> X-Mailer: git-send-email 2.42.1 In-Reply-To: <20240207114419.1100894-2-arthur.cohen@embecosm.com> References: <20240207114419.1100894-2-arthur.cohen@embecosm.com> Reply-To: arthur.cohen@embecosm.com MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-13.3 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: Jakub Dupak gcc/rust/ChangeLog: * typecheck/rust-hir-type-check.h (class Lifetime): add interned lifetime class * typecheck/rust-typecheck-context.cc (TypeCheckContext::TypeCheckContext): add resolution tool (TypeCheckContext::intern_lifetime): add method to intern lifetime from tyctx (TypeCheckContext::lookup_lifetime): add method to lookup lifetime from tyctx (TypeCheckContext::intern_and_insert_lifetime): add a helper method Signed-off-by: Jakub Dupak --- gcc/rust/typecheck/rust-hir-type-check.h | 225 +++++++++++++++++++ gcc/rust/typecheck/rust-typecheck-context.cc | 55 ++++- 2 files changed, 279 insertions(+), 1 deletion(-) diff --git a/gcc/rust/typecheck/rust-hir-type-check.h b/gcc/rust/typecheck/rust-hir-type-check.h index 7dd4dda5b93..0d74ae11a2c 100644 --- a/gcc/rust/typecheck/rust-hir-type-check.h +++ b/gcc/rust/typecheck/rust-hir-type-check.h @@ -24,6 +24,8 @@ #include "rust-hir-trait-reference.h" #include "rust-autoderef.h" +#include + namespace Rust { namespace Resolver { @@ -79,6 +81,49 @@ private: Item item; }; +/** + * Interned lifetime representation in TyTy + * + * On the HIR->TyTy boundary HIR::Lifetime is interned into this struct. + */ +class Lifetime +{ + uint32_t interner_index; + +public: + explicit constexpr Lifetime (uint32_t interner_index) + : interner_index (interner_index) + {} + + Lifetime () = default; + + WARN_UNUSED_RESULT bool is_static () const { return interner_index == 0; } + + WARN_UNUSED_RESULT static constexpr Lifetime static_lifetime () + { + return Lifetime (0); + } + + WARN_UNUSED_RESULT static constexpr Lifetime anonymous_lifetime () + { + return Lifetime (1); + } + + static constexpr uint32_t FIRST_NAMED_LIFETIME = 2; + + friend bool operator== (const Lifetime &lhs, const Lifetime &rhs) + { + return lhs.interner_index == rhs.interner_index; + } + + friend bool operator!= (const Lifetime &lhs, const Lifetime &rhs) + { + return !(lhs == rhs); + } + + WARN_UNUSED_RESULT Lifetime next () { return Lifetime (interner_index++); } +}; + class TypeCheckContext { public: @@ -173,6 +218,12 @@ public: void trait_query_completed (DefId id); bool trait_query_in_progress (DefId id) const; + Lifetime intern_lifetime (const HIR::Lifetime &name); + WARN_UNUSED_RESULT tl::optional + lookup_lifetime (const HIR::Lifetime &lifetime) const; + + void intern_and_insert_lifetime (const HIR::Lifetime &lifetime); + private: TypeCheckContext (); @@ -211,6 +262,180 @@ private: // query context lookups std::set querys_in_progress; std::set trait_queries_in_progress; + + /** Used to resolve (interned) lifetime names to their bounding scope. */ + class LifetimeResolver + { + /** + * The level of nested scopes, where the lifetime was declared. + * + * Index 0 is used for `impl` blocks and is skipped if not explicitly + * requested. + * Index 1 for the top-level of declarations of items. + * Index >1 is used for late-bound lifetimes. + */ + using ScopeIndex = size_t; + + static constexpr ScopeIndex IMPL_SCOPE = 0; + static constexpr ScopeIndex ITEM_SCOPE = 1; + + /** + * A reference to a lifetime binder. + * + * This is used to resolve lifetimes to their scope. + */ + struct LifetimeBinderRef + { + uint32_t scope; //> Depth of the scope where the lifetime was declared. + uint32_t index; //> Index of the lifetime in the scope. + }; + + /** + * A stack of the number of lifetimes declared in each scope. + * + * Used to pop the correct number of lifetimes when leaving a scope. + */ + std::stack binder_size_stack; + + /** + * Merged stack of all lifetimes declared in all scopes. + * + * Use `binder_size_stack` to determine the number of lifetimes in each + * scope. + */ + std::vector> lifetime_lookup; + + /** + * Whether the current scope is a function body. + * + * In function header, lifetimes are resolved as early-bound, in the body as + * named. This is because the header can be also used in call position. + */ + bool is_body = false; + + /** Return the number of the current scope. */ + WARN_UNUSED_RESULT uint32_t get_current_scope () const + { + return binder_size_stack.size () - 1; + } + + public: + /** Add new declaration of a lifetime. */ + void insert_mapping (Lifetime placeholder) + { + lifetime_lookup.push_back ( + {placeholder, {get_current_scope (), binder_size_stack.top ()++}}); + } + + /** Only to be used by the guard. */ + void push_binder () { binder_size_stack.push (0); } + /** Only to be used by the guard. */ + void pop_binder () { binder_size_stack.pop (); } + + /** + * Switch from resolving a function header to a function body. + */ + void switch_to_fn_body () { this->is_body = true; } + + size_t get_num_bound_regions () const { return binder_size_stack.top (); } + }; + + // lifetime resolving + std::unordered_map lifetime_name_interner; + Lifetime next_lifetime_index = Lifetime (Lifetime::FIRST_NAMED_LIFETIME); + + /** + * Stack of lifetime resolvers. + * + * Due to the contruction of the type checker, it is possible to start + * resolution of a new type in the middle of resolving another type. This + * stack isolates the conexts in such cases. + */ + std::stack lifetime_resolver_stack; + +public: + WARN_UNUSED_RESULT LifetimeResolver &get_lifetime_resolver () + { + rust_assert (!lifetime_resolver_stack.empty ()); + return lifetime_resolver_stack.top (); + } + + WARN_UNUSED_RESULT const LifetimeResolver &get_lifetime_resolver () const + { + rust_assert (!lifetime_resolver_stack.empty ()); + return lifetime_resolver_stack.top (); + } + + /** + * A guard that pushes a new lifetime resolver on the stack and pops it + * when it goes out of scope. + */ + class LifetimeResolverGuard + { + public: + /** The kind of scope that is being pushed. */ + enum ScopeKind + { + IMPL_BLOCK_RESOLVER, //> A new `impl` block scope. + RESOLVER, //> A new scope for a function body. + BINDER, //> A new scope for late-bound lifetimes. + }; + + private: + TypeCheckContext &ctx; + ScopeKind kind; + + public: + LifetimeResolverGuard (TypeCheckContext &ctx, ScopeKind kind) + : ctx (ctx), kind (kind) + { + if (kind == IMPL_BLOCK_RESOLVER) + { + ctx.lifetime_resolver_stack.push (LifetimeResolver ()); + } + + if (kind == RESOLVER) + { + ctx.lifetime_resolver_stack.push (LifetimeResolver ()); + // Skip the `impl` block scope. + ctx.lifetime_resolver_stack.top ().push_binder (); + } + rust_assert (!ctx.lifetime_resolver_stack.empty ()); + ctx.lifetime_resolver_stack.top ().push_binder (); + } + + ~LifetimeResolverGuard () + { + rust_assert (!ctx.lifetime_resolver_stack.empty ()); + ctx.lifetime_resolver_stack.top ().pop_binder (); + if (kind == RESOLVER) + { + ctx.lifetime_resolver_stack.pop (); + } + } + }; + + /** Start new late bound lifetime scope. */ + WARN_UNUSED_RESULT LifetimeResolverGuard push_lifetime_binder () + { + return LifetimeResolverGuard (*this, LifetimeResolverGuard::BINDER); + } + + /** Start new function body scope. */ + WARN_UNUSED_RESULT LifetimeResolverGuard + push_clean_lifetime_resolver (bool is_impl_block = false) + { + return LifetimeResolverGuard (*this, + is_impl_block + ? LifetimeResolverGuard::IMPL_BLOCK_RESOLVER + : LifetimeResolverGuard::RESOLVER); + } + + /** Switch from resolving a function header to a function body. */ + void switch_to_fn_body () + { + this->lifetime_resolver_stack.top ().switch_to_fn_body (); + } }; class TypeResolution diff --git a/gcc/rust/typecheck/rust-typecheck-context.cc b/gcc/rust/typecheck/rust-typecheck-context.cc index 46954683875..c6840c8b1a9 100644 --- a/gcc/rust/typecheck/rust-typecheck-context.cc +++ b/gcc/rust/typecheck/rust-typecheck-context.cc @@ -31,7 +31,7 @@ TypeCheckContext::get () return instance; } -TypeCheckContext::TypeCheckContext () {} +TypeCheckContext::TypeCheckContext () { lifetime_resolver_stack.emplace (); } TypeCheckContext::~TypeCheckContext () {} @@ -496,6 +496,59 @@ TypeCheckContext::trait_query_in_progress (DefId id) const != trait_queries_in_progress.end (); } +Lifetime +TypeCheckContext::intern_lifetime (const HIR::Lifetime &lifetime) +{ + if (lifetime.get_lifetime_type () == AST::Lifetime::NAMED) + { + auto maybe_interned = lookup_lifetime (lifetime); + if (maybe_interned) + return *maybe_interned; + + auto interned = next_lifetime_index.next (); + lifetime_name_interner[lifetime.get_name ()] = interned; + return interned; + } + if (lifetime.get_lifetime_type () == AST::Lifetime::WILDCARD) + { + return next_lifetime_index.next (); + } + if (lifetime.get_lifetime_type () == AST::Lifetime::STATIC) + { + return Lifetime::static_lifetime (); + } + rust_unreachable (); +} + +tl::optional +TypeCheckContext::lookup_lifetime (const HIR::Lifetime &lifetime) const +{ + if (lifetime.get_lifetime_type () == AST::Lifetime::NAMED) + { + rust_assert (lifetime.get_name () != "static"); + const auto name = lifetime.get_name (); + auto it = lifetime_name_interner.find (name); + if (it == lifetime_name_interner.end ()) + return tl::nullopt; + return it->second; + } + if (lifetime.get_lifetime_type () == AST::Lifetime::WILDCARD) + { + return Lifetime::anonymous_lifetime (); + } + if (lifetime.get_lifetime_type () == AST::Lifetime::STATIC) + { + return Lifetime::static_lifetime (); + } + rust_unreachable (); +} + +void +TypeCheckContext::intern_and_insert_lifetime (const HIR::Lifetime &lifetime) +{ + get_lifetime_resolver ().insert_mapping (intern_lifetime (lifetime)); +} + // TypeCheckContextItem TypeCheckContextItem::Item::Item (HIR::Function *item) : item (item) {} -- 2.42.1