gcc/rust/typecheck/rust-hir-type-check.h

   1 // Copyright (C) 2020-2024 Free Software Foundation, Inc.
   2
   3 // This file is part of GCC.
   4
   5 // GCC is free software; you can redistribute it and/or modify it under
   6 // the terms of the GNU General Public License as published by the Free
   7 // Software Foundation; either version 3, or (at your option) any later
   8 // version.
   9
  10 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13 // for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with GCC; see the file COPYING3.  If not see
  17 // <http://www.gnu.org/licenses/>.
  18
  19 #ifndef RUST_HIR_TYPE_CHECK
  20 #define RUST_HIR_TYPE_CHECK
  21
  22 #include "rust-hir-map.h"
  23 #include "rust-tyty.h"
  24 #include "rust-hir-trait-reference.h"
  25 #include "rust-autoderef.h"
  26 #include "rust-tyty-region.h"
  27 #include "rust-tyty-variance-analysis.h"
  28 #include "rust-system.h"
  29
  30 namespace Rust {
  31 namespace Resolver {
  32
  33 class TypeCheckContextItem
  34 {
  35 public:
  36   enum ItemType
  37   {
  38     ITEM,
  39     IMPL_ITEM,
  40     TRAIT_ITEM,
  41     ERROR
  42   };
  43
  44   TypeCheckContextItem (HIR::Function *item);
  45   TypeCheckContextItem (HIR::ImplBlock *impl_block, HIR::Function *item);
  46   TypeCheckContextItem (HIR::TraitItemFunc *trait_item);
  47   TypeCheckContextItem (const TypeCheckContextItem &other);
  48
  49   TypeCheckContextItem &operator= (const TypeCheckContextItem &other);
  50
  51   static TypeCheckContextItem get_error ();
  52
  53   bool is_error () const;
  54
  55   ItemType get_type () const;
  56
  57   HIR::Function *get_item ();
  58
  59   std::pair<HIR::ImplBlock *, HIR::Function *> &get_impl_item ();
  60
  61   HIR::TraitItemFunc *get_trait_item ();
  62
  63   TyTy::FnType *get_context_type ();
  64
  65   DefId get_defid () const;
  66
  67 private:
  68   TypeCheckContextItem ();
  69
  70   union Item
  71   {
  72     HIR::Function *item;
  73     std::pair<HIR::ImplBlock *, HIR::Function *> impl_item;
  74     HIR::TraitItemFunc *trait_item;
  75
  76     Item (HIR::Function *item);
  77     Item (HIR::ImplBlock *impl_block, HIR::Function *item);
  78     Item (HIR::TraitItemFunc *trait_item);
  79   };
  80
  81   ItemType type;
  82   Item item;
  83 };
  84
  85 /**
  86  * Interned lifetime representation in TyTy
  87  *
  88  * On the HIR->TyTy boundary HIR::Lifetime is interned into this struct.
  89  */
  90 class Lifetime
  91 {
  92   uint32_t interner_index;
  93
  94 public:
  95   explicit constexpr Lifetime (uint32_t interner_index)
  96     : interner_index (interner_index)
  97   {}
  98
  99   Lifetime () = default;
 100
 101   WARN_UNUSED_RESULT bool is_static () const { return interner_index == 0; }
 102
 103   WARN_UNUSED_RESULT static constexpr Lifetime static_lifetime ()
 104   {
 105     return Lifetime (0);
 106   }
 107
 108   WARN_UNUSED_RESULT static constexpr Lifetime anonymous_lifetime ()
 109   {
 110     return Lifetime (1);
 111   }
 112
 113   static constexpr uint32_t FIRST_NAMED_LIFETIME = 2;
 114
 115   friend bool operator== (const Lifetime &lhs, const Lifetime &rhs)
 116   {
 117     return lhs.interner_index == rhs.interner_index;
 118   }
 119
 120   friend bool operator!= (const Lifetime &lhs, const Lifetime &rhs)
 121   {
 122     return !(lhs == rhs);
 123   }
 124
 125   WARN_UNUSED_RESULT Lifetime next () { return Lifetime (interner_index++); }
 126 };
 127
 128 class TypeCheckContext
 129 {
 130 public:
 131   static TypeCheckContext *get ();
 132
 133   ~TypeCheckContext ();
 134
 135   bool lookup_builtin (NodeId id, TyTy::BaseType **type);
 136   bool lookup_builtin (std::string name, TyTy::BaseType **type);
 137   void insert_builtin (HirId id, NodeId ref, TyTy::BaseType *type);
 138
 139   void insert_type (const Analysis::NodeMapping &mappings,
 140                     TyTy::BaseType *type);
 141   void insert_implicit_type (TyTy::BaseType *type);
 142   bool lookup_type (HirId id, TyTy::BaseType **type) const;
 143   void clear_type (TyTy::BaseType *ty);
 144
 145   void insert_implicit_type (HirId id, TyTy::BaseType *type);
 146
 147   void insert_type_by_node_id (NodeId ref, HirId id);
 148   bool lookup_type_by_node_id (NodeId ref, HirId *id);
 149
 150   bool have_function_context () const;
 151   TyTy::BaseType *peek_return_type ();
 152   TypeCheckContextItem peek_context ();
 153   void push_return_type (TypeCheckContextItem item,
 154                          TyTy::BaseType *return_type);
 155   void pop_return_type ();
 156   void iterate (std::function<bool (HirId, TyTy::BaseType *)> cb);
 157
 158   bool have_loop_context () const;
 159   void push_new_loop_context (HirId id, location_t locus);
 160   void push_new_while_loop_context (HirId id);
 161   TyTy::BaseType *peek_loop_context ();
 162   TyTy::BaseType *pop_loop_context ();
 163
 164   void swap_head_loop_context (TyTy::BaseType *val);
 165
 166   void insert_trait_reference (DefId id, TraitReference &&ref);
 167   bool lookup_trait_reference (DefId id, TraitReference **ref);
 168
 169   void insert_receiver (HirId id, TyTy::BaseType *t);
 170   bool lookup_receiver (HirId id, TyTy::BaseType **ref);
 171
 172   void insert_associated_trait_impl (HirId id,
 173                                      AssociatedImplTrait &&associated);
 174   bool lookup_associated_trait_impl (HirId id,
 175                                      AssociatedImplTrait **associated);
 176
 177   void insert_associated_type_mapping (HirId id, HirId mapping);
 178   void clear_associated_type_mapping (HirId id);
 179
 180   // lookup any associated type mappings, the out parameter of mapping is
 181   // allowed to be nullptr which allows this interface to do a simple does exist
 182   // check
 183   bool lookup_associated_type_mapping (HirId id, HirId *mapping);
 184
 185   void insert_associated_impl_mapping (HirId trait_id,
 186                                        const TyTy::BaseType *impl_type,
 187                                        HirId impl_id);
 188   bool lookup_associated_impl_mapping_for_self (HirId trait_id,
 189                                                 const TyTy::BaseType *self,
 190                                                 HirId *mapping);
 191
 192   void insert_autoderef_mappings (HirId id,
 193                                   std::vector<Adjustment> &&adjustments);
 194   bool lookup_autoderef_mappings (HirId id,
 195                                   std::vector<Adjustment> **adjustments);
 196
 197   void insert_cast_autoderef_mappings (HirId id,
 198                                        std::vector<Adjustment> &&adjustments);
 199   bool lookup_cast_autoderef_mappings (HirId id,
 200                                        std::vector<Adjustment> **adjustments);
 201
 202   void insert_variant_definition (HirId id, HirId variant);
 203   bool lookup_variant_definition (HirId id, HirId *variant);
 204
 205   void insert_operator_overload (HirId id, TyTy::FnType *call_site);
 206   bool lookup_operator_overload (HirId id, TyTy::FnType **call);
 207
 208   void insert_unconstrained_check_marker (HirId id, bool status);
 209   bool have_checked_for_unconstrained (HirId id, bool *result);
 210
 211   void insert_resolved_predicate (HirId id, TyTy::TypeBoundPredicate predicate);
 212   bool lookup_predicate (HirId id, TyTy::TypeBoundPredicate *result);
 213
 214   void insert_query (HirId id);
 215   void query_completed (HirId id);
 216   bool query_in_progress (HirId id) const;
 217
 218   void insert_trait_query (DefId id);
 219   void trait_query_completed (DefId id);
 220   bool trait_query_in_progress (DefId id) const;
 221
 222   Lifetime intern_lifetime (const HIR::Lifetime &name);
 223   WARN_UNUSED_RESULT tl::optional<Lifetime>
 224   lookup_lifetime (const HIR::Lifetime &lifetime) const;
 225
 226   WARN_UNUSED_RESULT tl::optional<TyTy::Region>
 227   lookup_and_resolve_lifetime (const HIR::Lifetime &lifetime) const;
 228
 229   void intern_and_insert_lifetime (const HIR::Lifetime &lifetime);
 230
 231   WARN_UNUSED_RESULT std::vector<TyTy::Region>
 232   regions_from_generic_args (const HIR::GenericArgs &args) const;
 233
 234   void compute_inference_variables (bool error);
 235
 236   TyTy::VarianceAnalysis::CrateCtx &get_variance_analysis_ctx ();
 237
 238 private:
 239   TypeCheckContext ();
 240
 241   std::map<NodeId, HirId> node_id_refs;
 242   std::map<HirId, TyTy::BaseType *> resolved;
 243   std::vector<std::unique_ptr<TyTy::BaseType>> builtins;
 244   std::vector<std::pair<TypeCheckContextItem, TyTy::BaseType *>>
 245     return_type_stack;
 246   std::vector<TyTy::BaseType *> loop_type_stack;
 247   std::map<DefId, TraitReference> trait_context;
 248   std::map<HirId, TyTy::BaseType *> receiver_context;
 249   std::map<HirId, AssociatedImplTrait> associated_impl_traits;
 250
 251   // trait-id -> list of < self-tyty:impl-id>
 252   std::map<HirId, std::vector<std::pair<const TyTy::BaseType *, HirId>>>
 253     associated_traits_to_impls;
 254
 255   std::map<HirId, HirId> associated_type_mappings;
 256
 257   // adjustment mappings
 258   std::map<HirId, std::vector<Adjustment>> autoderef_mappings;
 259   std::map<HirId, std::vector<Adjustment>> cast_autoderef_mappings;
 260
 261   // operator overloads
 262   std::map<HirId, TyTy::FnType *> operator_overloads;
 263
 264   // variants
 265   std::map<HirId, HirId> variants;
 266
 267   // unconstrained type-params check
 268   std::map<HirId, bool> unconstrained;
 269
 270   // predicates
 271   std::map<HirId, TyTy::TypeBoundPredicate> predicates;
 272
 273   // query context lookups
 274   std::set<HirId> querys_in_progress;
 275   std::set<DefId> trait_queries_in_progress;
 276
 277   // variance analysis
 278   TyTy::VarianceAnalysis::CrateCtx variance_analysis_ctx;
 279
 280   /** Used to resolve (interned) lifetime names to their bounding scope. */
 281   class LifetimeResolver
 282   {
 283     /**
 284      * The level of nested scopes, where the lifetime was declared.
 285      *
 286      * Index 0 is used for `impl` blocks and is skipped if not explicitly
 287      * requested.
 288      * Index 1 for the top-level of declarations of items.
 289      * Index >1 is used for late-bound lifetimes.
 290      */
 291     using ScopeIndex = size_t;
 292
 293     static constexpr ScopeIndex IMPL_SCOPE = 0;
 294     static constexpr ScopeIndex ITEM_SCOPE = 1;
 295
 296     /**
 297      * A reference to a lifetime binder.
 298      *
 299      * This is used to resolve lifetimes to their scope.
 300      */
 301     struct LifetimeBinderRef
 302     {
 303       uint32_t scope; //> Depth of the scope where the lifetime was declared.
 304       uint32_t index; //> Index of the lifetime in the scope.
 305     };
 306
 307     /**
 308      * A stack of the number of lifetimes declared in each scope.
 309      *
 310      * Used to pop the correct number of lifetimes when leaving a scope.
 311      */
 312     std::stack<uint32_t> binder_size_stack;
 313
 314     /**
 315      * Merged stack of all lifetimes declared in all scopes.
 316      *
 317      * Use `binder_size_stack` to determine the number of lifetimes in each
 318      * scope.
 319      */
 320     std::vector<std::pair<Lifetime, LifetimeBinderRef>> lifetime_lookup;
 321
 322     /**
 323      * Whether the current scope is a function body.
 324      *
 325      * In function header, lifetimes are resolved as early-bound, in the body as
 326      * named. This is because the header can be also used in call position.
 327      */
 328     bool is_body = false;
 329
 330     /** Return the number of the current scope. */
 331     WARN_UNUSED_RESULT uint32_t get_current_scope () const
 332     {
 333       return binder_size_stack.size () - 1;
 334     }
 335
 336   public:
 337     /** Add new declaration of a lifetime. */
 338     void insert_mapping (Lifetime placeholder)
 339     {
 340       lifetime_lookup.push_back (
 341         {placeholder, {get_current_scope (), binder_size_stack.top ()++}});
 342     }
 343
 344     WARN_UNUSED_RESULT tl::optional<TyTy::Region>
 345     resolve (const Lifetime &placeholder) const;
 346
 347     /** Only to be used by the guard. */
 348     void push_binder () { binder_size_stack.push (0); }
 349     /** Only to be used by the guard. */
 350     void pop_binder () { binder_size_stack.pop (); }
 351
 352     /**
 353      * Switch from resolving a function header to a function body.
 354      */
 355     void switch_to_fn_body () { this->is_body = true; }
 356
 357     size_t get_num_bound_regions () const { return binder_size_stack.top (); }
 358   };
 359
 360   // lifetime resolving
 361   std::unordered_map<std::string, Lifetime> lifetime_name_interner;
 362   Lifetime next_lifetime_index = Lifetime (Lifetime::FIRST_NAMED_LIFETIME);
 363
 364   /**
 365    * Stack of lifetime resolvers.
 366    *
 367    * Due to the contruction of the type checker, it is possible to start
 368    * resolution of a new type in the middle of resolving another type. This
 369    * stack isolates the conexts in such cases.
 370    */
 371   std::stack<LifetimeResolver> lifetime_resolver_stack;
 372
 373 public:
 374   WARN_UNUSED_RESULT LifetimeResolver &get_lifetime_resolver ()
 375   {
 376     rust_assert (!lifetime_resolver_stack.empty ());
 377     return lifetime_resolver_stack.top ();
 378   }
 379
 380   WARN_UNUSED_RESULT const LifetimeResolver &get_lifetime_resolver () const
 381   {
 382     rust_assert (!lifetime_resolver_stack.empty ());
 383     return lifetime_resolver_stack.top ();
 384   }
 385
 386   /**
 387    * A guard that pushes a new lifetime resolver on the stack and pops it
 388    * when it goes out of scope.
 389    */
 390   class LifetimeResolverGuard
 391   {
 392   public:
 393     /** The kind of scope that is being pushed. */
 394     enum ScopeKind
 395     {
 396       IMPL_BLOCK_RESOLVER, //> A new `impl` block scope.
 397       RESOLVER,            //> A new scope for a function body.
 398       BINDER,              //> A new scope for late-bound lifetimes.
 399     };
 400
 401   private:
 402     TypeCheckContext &ctx;
 403     ScopeKind kind;
 404
 405   public:
 406     LifetimeResolverGuard (TypeCheckContext &ctx, ScopeKind kind)
 407       : ctx (ctx), kind (kind)
 408     {
 409       if (kind == IMPL_BLOCK_RESOLVER)
 410         {
 411           ctx.lifetime_resolver_stack.push (LifetimeResolver ());
 412         }
 413
 414       if (kind == RESOLVER)
 415         {
 416           ctx.lifetime_resolver_stack.push (LifetimeResolver ());
 417           // Skip the `impl` block scope.
 418           ctx.lifetime_resolver_stack.top ().push_binder ();
 419         }
 420       rust_assert (!ctx.lifetime_resolver_stack.empty ());
 421       ctx.lifetime_resolver_stack.top ().push_binder ();
 422     }
 423
 424     ~LifetimeResolverGuard ()
 425     {
 426       rust_assert (!ctx.lifetime_resolver_stack.empty ());
 427       ctx.lifetime_resolver_stack.top ().pop_binder ();
 428       if (kind == RESOLVER)
 429         {
 430           ctx.lifetime_resolver_stack.pop ();
 431         }
 432     }
 433   };
 434
 435   /** Start new late bound lifetime scope. */
 436   WARN_UNUSED_RESULT LifetimeResolverGuard push_lifetime_binder ()
 437   {
 438     return LifetimeResolverGuard (*this, LifetimeResolverGuard::BINDER);
 439   }
 440
 441   /** Start new function body scope. */
 442   WARN_UNUSED_RESULT LifetimeResolverGuard
 443   push_clean_lifetime_resolver (bool is_impl_block = false)
 444   {
 445     return LifetimeResolverGuard (*this,
 446                                   is_impl_block
 447                                     ? LifetimeResolverGuard::IMPL_BLOCK_RESOLVER
 448                                     : LifetimeResolverGuard::RESOLVER);
 449   }
 450
 451   /** Switch from resolving a function header to a function body. */
 452   void switch_to_fn_body ()
 453   {
 454     this->lifetime_resolver_stack.top ().switch_to_fn_body ();
 455   }
 456 };
 457
 458 class TypeResolution
 459 {
 460 public:
 461   static void Resolve (HIR::Crate &crate);
 462 };
 463
 464 class TraitQueryGuard
 465 {
 466 public:
 467   TraitQueryGuard (DefId id) : id (id), ctx (*TypeCheckContext::get ())
 468   {
 469     ctx.insert_trait_query (id);
 470   }
 471
 472   ~TraitQueryGuard () { ctx.trait_query_completed (id); }
 473
 474 private:
 475   DefId id;
 476   TypeCheckContext &ctx;
 477 };
 478
 479 } // namespace Resolver
 480 } // namespace Rust
 481
 482 #endif // RUST_HIR_TYPE_CHECK