[gcc r14-8844] gccrs: Typecheck: lifetime interning and resolution tool

[gcc r14-8844] gccrs: Typecheck: lifetime interning and resolution tool

[Arthur Cohen]

https://gcc.gnu.org/g:c49e45d7e849c016bd9513447ff7341a9bcb1a05

commit r14-8844-gc49e45d7e849c016bd9513447ff7341a9bcb1a05
Author: Jakub Dupak <dev@jakubdupak.com>
Date:   Wed Jan 10 13:12:48 2024 +0100

    gccrs: 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 <dev@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 7dd4dda5b93c..0d74ae11a2c3 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 46954683875b..c6840c8b1a9f 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) {}