https://gcc.gnu.org/g:d42498b69e27d2c15bbdfadfacd650001a9e8545
commit d42498b69e27d2c15bbdfadfacd650001a9e8545
Author: Jakub Dupak <d...@jakubdupak.com>
Date: Wed Jan 10 13:12:48 2024 +0100
Typecheck: lifetime interning and resolution tool
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 <d...@jakubdupak.com>
Diff:
---
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 c18412818d4d..120def2574bf 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 d65a679d7162..26872567d255 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) {}
