From: Jakub Dupak <d...@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 <d...@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