From: arthur.cohen@embecosm.com
To: gcc-patches@gcc.gnu.org
Cc: gcc-rust@gcc.gnu.org, Jakub Dupak <dev@jakubdupak.com>
Subject: [COMMITTED 03/25] gccrs: Typecheck: lifetime interning and resolution tool
Date: Wed, 7 Feb 2024 12:43:49 +0100 [thread overview]
Message-ID: <20240207114419.1100894-4-arthur.cohen@embecosm.com> (raw)
In-Reply-To: <20240207114419.1100894-2-arthur.cohen@embecosm.com>
From: Jakub Dupak <dev@jakubdupak.com>
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 <dev@jakubdupak.com>
---
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 <stack>
+
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<Lifetime>
+ 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<HirId> querys_in_progress;
std::set<DefId> 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<uint32_t> 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<std::pair<Lifetime, LifetimeBinderRef>> 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<std::string, Lifetime> 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<LifetimeResolver> 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<Lifetime>
+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
next prev parent reply other threads:[~2024-02-07 12:44 UTC|newest]
Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-02-07 11:43 [COMMITTED 01/25] gccrs: Parse normal functions with `self` parameter correctly arthur.cohen
2024-02-07 11:43 ` [COMMITTED 02/25] gccrs: Implement quick-check for Unicode arthur.cohen
2024-02-07 11:43 ` arthur.cohen [this message]
2024-02-07 11:43 ` [COMMITTED 04/25] gccrs: TyTy: Region (lifetime) representation arthur.cohen
2024-02-07 11:43 ` [COMMITTED 05/25] gccrs: HIR: Add mising getter arthur.cohen
2024-02-07 11:43 ` [COMMITTED 06/25] gccrs: Typecheck: add regions (lifetimes) to TyTy arthur.cohen
2024-02-07 11:43 ` [COMMITTED 07/25] gccrs: TyTy: Store region constraints arthur.cohen
2024-02-07 15:26 ` Bernhard Reutner-Fischer
2024-02-07 14:46 ` Arthur Cohen
2024-02-07 11:43 ` [COMMITTED 08/25] gccrs: TyTy: Store reference to type before any substitutions arthur.cohen
2024-02-07 11:43 ` [COMMITTED 09/25] gccrs: Set the default ABI to C for extern blocks and extern functions arthur.cohen
2024-02-07 11:43 ` [COMMITTED 10/25] gccrs: add testcase to prove issue has already been fixed arthur.cohen
2024-02-07 11:43 ` [COMMITTED 11/25] gccrs: add test cases to prove type inference is working arthur.cohen
2024-02-07 11:43 ` [COMMITTED 12/25] gccrs: Fix ICE accessing empty vector without check arthur.cohen
2024-02-07 11:43 ` [COMMITTED 13/25] gccrs: remove old generics hack to reuse generic symbols from previous seg arthur.cohen
2024-02-09 10:03 ` Jakub Jelinek
2024-02-15 9:10 ` [PATCH] gccrs: Avoid *.bak suffixed tests - use dg-skip-if instead Jakub Jelinek
2024-02-15 13:12 ` Arthur Cohen
2024-02-07 11:44 ` [COMMITTED 14/25] gccrs: remove similar hack in type paths as we had in path expressions arthur.cohen
2024-02-07 11:44 ` [COMMITTED 15/25] gccrs: refactor inference variable computation into a seperate method arthur.cohen
2024-02-07 11:44 ` [COMMITTED 16/25] gccrs: Move the Implementation of implitem lowering into its own file arthur.cohen
2024-02-07 11:44 ` [COMMITTED 17/25] gccrs: Add testcase to show issue is already fixed arthur.cohen
2024-02-07 11:44 ` [COMMITTED 18/25] gccrs: fix bug in pattern check for tuples arthur.cohen
2024-02-07 11:44 ` [COMMITTED 19/25] gccrs: Use AssociatedItem in place of TraitItem arthur.cohen
2024-02-07 11:44 ` [COMMITTED 20/25] gccrs: Add checks for Trait functions arthur.cohen
2024-02-07 11:44 ` [COMMITTED 21/25] gccrs: Add missing visitors for AST::Function arthur.cohen
2024-02-07 11:44 ` [COMMITTED 22/25] gccrs: Fix inconsistent formatting arthur.cohen
2024-02-07 11:44 ` [COMMITTED 23/25] gccrs: Parse trait functions as `AST::Function` arthur.cohen
2024-02-07 11:44 ` [COMMITTED 24/25] gccrs: Remove obsolete classes and functions arthur.cohen
2024-02-07 11:44 ` [COMMITTED 25/25] gccrs: Fix macro parsing for trait items arthur.cohen
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=20240207114419.1100894-4-arthur.cohen@embecosm.com \
--to=arthur.cohen@embecosm.com \
--cc=dev@jakubdupak.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=gcc-rust@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: link
Be 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).