gcc/rust/typecheck/rust-tyty.h

   1 // Copyright (C) 2020-2023 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_TYTY
  20 #define RUST_TYTY
  21
  22 #include "rust-hir-map.h"
  23 #include "rust-hir-full.h"
  24 #include "rust-diagnostics.h"
  25 #include "rust-abi.h"
  26 #include "rust-common.h"
  27 #include "rust-identifier.h"
  28
  29 namespace Rust {
  30
  31 namespace Resolver {
  32 class TraitReference;
  33 class TraitItemReference;
  34 class AssociatedImplTrait;
  35 } // namespace Resolver
  36
  37 namespace TyTy {
  38
  39 // https://rustc-dev-guide.rust-lang.org/type-inference.html#inference-variables
  40 // https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.TyKind.html#variants
  41 enum TypeKind
  42 {
  43   INFER,
  44   ADT,
  45   STR,
  46   REF,
  47   POINTER,
  48   PARAM,
  49   ARRAY,
  50   SLICE,
  51   FNDEF,
  52   FNPTR,
  53   TUPLE,
  54   BOOL,
  55   CHAR,
  56   INT,
  57   UINT,
  58   FLOAT,
  59   USIZE,
  60   ISIZE,
  61   NEVER,
  62   PLACEHOLDER,
  63   PROJECTION,
  64   DYNAMIC,
  65   CLOSURE,
  66   // there are more to add...
  67   ERROR
  68 };
  69
  70 extern bool
  71 is_primitive_type_kind (TypeKind kind);
  72
  73 class TypeKindFormat
  74 {
  75 public:
  76   static std::string to_string (TypeKind kind);
  77 };
  78
  79 class BaseType;
  80 class TypeBoundPredicate;
  81 class TypeBoundPredicateItem
  82 {
  83 public:
  84   TypeBoundPredicateItem (const TypeBoundPredicate *parent,
  85                           const Resolver::TraitItemReference *trait_item_ref)
  86     : parent (parent), trait_item_ref (trait_item_ref)
  87   {}
  88
  89   static TypeBoundPredicateItem error ()
  90   {
  91     return TypeBoundPredicateItem (nullptr, nullptr);
  92   }
  93
  94   bool is_error () const
  95   {
  96     return parent == nullptr || trait_item_ref == nullptr;
  97   }
  98
  99   BaseType *get_tyty_for_receiver (const TyTy::BaseType *receiver);
 100
 101   const Resolver::TraitItemReference *get_raw_item () const;
 102
 103   bool needs_implementation () const;
 104
 105   const TypeBoundPredicate *get_parent () const { return parent; }
 106
 107   Location get_locus () const;
 108
 109 private:
 110   const TypeBoundPredicate *parent;
 111   const Resolver::TraitItemReference *trait_item_ref;
 112 };
 113
 114 class TypeBoundsMappings
 115 {
 116 protected:
 117   TypeBoundsMappings (std::vector<TypeBoundPredicate> specified_bounds);
 118
 119 public:
 120   std::vector<TypeBoundPredicate> &get_specified_bounds ();
 121
 122   const std::vector<TypeBoundPredicate> &get_specified_bounds () const;
 123
 124   size_t num_specified_bounds () const;
 125
 126   std::string raw_bounds_as_string () const;
 127
 128   std::string bounds_as_string () const;
 129
 130   std::string raw_bounds_as_name () const;
 131
 132 protected:
 133   void add_bound (TypeBoundPredicate predicate);
 134
 135   std::vector<TypeBoundPredicate> specified_bounds;
 136 };
 137
 138 class TyVisitor;
 139 class TyConstVisitor;
 140 class BaseType : public TypeBoundsMappings
 141 {
 142 public:
 143   virtual ~BaseType () {}
 144
 145   HirId get_ref () const { return ref; }
 146
 147   void set_ref (HirId id)
 148   {
 149     if (id != ref)
 150       append_reference (ref);
 151     ref = id;
 152   }
 153
 154   HirId get_ty_ref () const { return ty_ref; }
 155
 156   void set_ty_ref (HirId id) { ty_ref = id; }
 157
 158   virtual void accept_vis (TyVisitor &vis) = 0;
 159
 160   virtual void accept_vis (TyConstVisitor &vis) const = 0;
 161
 162   virtual std::string as_string () const = 0;
 163
 164   virtual std::string get_name () const = 0;
 165
 166   // Unify two types. Returns a pointer to the newly-created unified ty, or
 167   // nullptr if the two ty cannot be unified. The caller is responsible for
 168   // releasing the memory of the returned ty.
 169   virtual BaseType *unify (BaseType *other) = 0;
 170
 171   // similar to unify but does not actually perform type unification but
 172   // determines whether they are compatible. Consider the following
 173   //
 174   // fn foo<T>() -> T { ... }
 175   // fn foo() -> i32 { ... }
 176   //
 177   // when the function has been substituted they can be considered equal.
 178   //
 179   // It can also be used to optional emit errors for trait item compatibility
 180   // checks
 181   virtual bool can_eq (const BaseType *other, bool emit_errors) const = 0;
 182
 183   // Check value equality between two ty. Type inference rules are ignored. Two
 184   //   ty are considered equal if they're of the same kind, and
 185   //     1. (For ADTs, arrays, tuples, refs) have the same underlying ty
 186   //     2. (For functions) have the same signature
 187   virtual bool is_equal (const BaseType &other) const
 188   {
 189     return get_kind () == other.get_kind ();
 190   }
 191
 192   bool satisfies_bound (const TypeBoundPredicate &predicate) const;
 193
 194   bool bounds_compatible (const BaseType &other, Location locus,
 195                           bool emit_error) const;
 196
 197   void inherit_bounds (const BaseType &other);
 198
 199   void inherit_bounds (
 200     const std::vector<TyTy::TypeBoundPredicate> &specified_bounds);
 201
 202   virtual bool is_unit () const { return false; }
 203
 204   virtual bool is_concrete () const = 0;
 205
 206   TypeKind get_kind () const { return kind; }
 207
 208   /* Returns a pointer to a clone of this. The caller is responsible for
 209    * releasing the memory of the returned ty. */
 210   virtual BaseType *clone () const = 0;
 211
 212   // TODO
 213   virtual BaseType *monomorphized_clone () const = 0;
 214
 215   // get_combined_refs returns the chain of node refs involved in unification
 216   std::set<HirId> get_combined_refs () const { return combined; }
 217
 218   void append_reference (HirId id) { combined.insert (id); }
 219
 220   virtual bool supports_substitutions () const { return false; }
 221
 222   virtual bool has_subsititions_defined () const { return false; }
 223
 224   virtual bool can_substitute () const
 225   {
 226     return supports_substitutions () && has_subsititions_defined ();
 227   }
 228
 229   virtual bool needs_generic_substitutions () const { return false; }
 230
 231   bool contains_type_parameters () const { return !is_concrete (); }
 232
 233   std::string mappings_str () const
 234   {
 235     std::string buffer = "Ref: " + std::to_string (get_ref ())
 236                          + " TyRef: " + std::to_string (get_ty_ref ());
 237     buffer += "[";
 238     for (auto &ref : combined)
 239       buffer += std::to_string (ref) + ",";
 240     buffer += "]";
 241     return "(" + buffer + ")";
 242   }
 243
 244   std::string debug_str () const
 245   {
 246     return TypeKindFormat::to_string (get_kind ()) + ":" + as_string () + ":"
 247            + mappings_str () + ":" + bounds_as_string ();
 248   }
 249
 250   void debug () const
 251   {
 252     rust_debug ("[%p] %s", static_cast<const void *> (this),
 253                 debug_str ().c_str ());
 254   }
 255
 256   // FIXME this will eventually go away
 257   const BaseType *get_root () const;
 258
 259   // This will get the monomorphized type from Params, Placeholders or
 260   // Projections if available or error
 261   const BaseType *destructure () const;
 262
 263   const RustIdent &get_ident () const { return ident; }
 264
 265   Location get_locus () const { return ident.locus; }
 266
 267 protected:
 268   BaseType (HirId ref, HirId ty_ref, TypeKind kind, RustIdent ident,
 269             std::set<HirId> refs = std::set<HirId> ())
 270     : TypeBoundsMappings ({}), kind (kind), ref (ref), ty_ref (ty_ref),
 271       combined (refs), ident (ident), mappings (Analysis::Mappings::get ())
 272   {}
 273
 274   BaseType (HirId ref, HirId ty_ref, TypeKind kind, RustIdent ident,
 275             std::vector<TypeBoundPredicate> specified_bounds,
 276             std::set<HirId> refs = std::set<HirId> ())
 277     : TypeBoundsMappings (specified_bounds), kind (kind), ref (ref),
 278       ty_ref (ty_ref), combined (refs), ident (ident),
 279       mappings (Analysis::Mappings::get ())
 280   {}
 281
 282   TypeKind kind;
 283   HirId ref;
 284   HirId ty_ref;
 285   std::set<HirId> combined;
 286   RustIdent ident;
 287
 288   Analysis::Mappings *mappings;
 289 };
 290
 291 // this is a placeholder for types that can change like inference variables
 292 class TyVar
 293 {
 294 public:
 295   explicit TyVar (HirId ref);
 296
 297   HirId get_ref () const { return ref; }
 298
 299   BaseType *get_tyty () const;
 300
 301   TyVar clone () const;
 302
 303   TyVar monomorphized_clone () const;
 304
 305   static TyVar get_implicit_infer_var (Location locus);
 306
 307   static TyVar subst_covariant_var (TyTy::BaseType *orig,
 308                                     TyTy::BaseType *subst);
 309
 310 private:
 311   HirId ref;
 312 };
 313
 314 class TyWithLocation
 315 {
 316 public:
 317   TyWithLocation (BaseType *ty, Location locus);
 318   TyWithLocation (BaseType *ty);
 319
 320   BaseType *get_ty () const { return ty; }
 321   Location get_locus () const { return locus; }
 322
 323 private:
 324   BaseType *ty;
 325   Location locus;
 326 };
 327
 328 class InferType : public BaseType
 329 {
 330 public:
 331   enum InferTypeKind
 332   {
 333     GENERAL,
 334     INTEGRAL,
 335     FLOAT
 336   };
 337
 338   InferType (HirId ref, InferTypeKind infer_kind, Location locus,
 339              std::set<HirId> refs = std::set<HirId> ())
 340     : BaseType (ref, ref, TypeKind::INFER,
 341                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
 342       infer_kind (infer_kind)
 343   {}
 344
 345   InferType (HirId ref, HirId ty_ref, InferTypeKind infer_kind, Location locus,
 346              std::set<HirId> refs = std::set<HirId> ())
 347     : BaseType (ref, ty_ref, TypeKind::INFER,
 348                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
 349       infer_kind (infer_kind)
 350   {}
 351
 352   void accept_vis (TyVisitor &vis) override;
 353   void accept_vis (TyConstVisitor &vis) const override;
 354
 355   std::string as_string () const override;
 356
 357   BaseType *unify (BaseType *other) override;
 358
 359   bool can_eq (const BaseType *other, bool emit_errors) const override final;
 360
 361   BaseType *clone () const final override;
 362   BaseType *monomorphized_clone () const final override;
 363
 364   InferTypeKind get_infer_kind () const { return infer_kind; }
 365
 366   std::string get_name () const override final { return as_string (); }
 367
 368   bool default_type (BaseType **type) const;
 369
 370   bool is_concrete () const final override { return true; }
 371
 372 private:
 373   InferTypeKind infer_kind;
 374 };
 375
 376 class ErrorType : public BaseType
 377 {
 378 public:
 379   ErrorType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
 380     : BaseType (ref, ref, TypeKind::ERROR,
 381                 {Resolver::CanonicalPath::create_empty (), Location ()}, refs)
 382   {}
 383
 384   ErrorType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
 385     : BaseType (ref, ty_ref, TypeKind::ERROR,
 386                 {Resolver::CanonicalPath::create_empty (), Location ()}, refs)
 387   {}
 388
 389   void accept_vis (TyVisitor &vis) override;
 390   void accept_vis (TyConstVisitor &vis) const override;
 391
 392   bool is_unit () const override { return true; }
 393
 394   std::string as_string () const override;
 395
 396   BaseType *unify (BaseType *other) override;
 397   bool can_eq (const BaseType *other, bool emit_errors) const override final;
 398
 399   BaseType *clone () const final override;
 400   BaseType *monomorphized_clone () const final override;
 401
 402   std::string get_name () const override final { return as_string (); }
 403
 404   bool is_concrete () const final override { return false; }
 405 };
 406
 407 class SubstitutionArgumentMappings;
 408 class ParamType : public BaseType
 409 {
 410 public:
 411   ParamType (std::string symbol, Location locus, HirId ref,
 412              HIR::GenericParam &param,
 413              std::vector<TypeBoundPredicate> specified_bounds,
 414              std::set<HirId> refs = std::set<HirId> ())
 415     : BaseType (ref, ref, TypeKind::PARAM,
 416                 {Resolver::CanonicalPath::new_seg (UNKNOWN_NODEID, symbol),
 417                  locus},
 418                 specified_bounds, refs),
 419       symbol (symbol), param (param)
 420   {}
 421
 422   ParamType (std::string symbol, Location locus, HirId ref, HirId ty_ref,
 423              HIR::GenericParam &param,
 424              std::vector<TypeBoundPredicate> specified_bounds,
 425              std::set<HirId> refs = std::set<HirId> ())
 426     : BaseType (ref, ty_ref, TypeKind::PARAM,
 427                 {Resolver::CanonicalPath::new_seg (UNKNOWN_NODEID, symbol),
 428                  locus},
 429                 specified_bounds, refs),
 430       symbol (symbol), param (param)
 431   {}
 432
 433   void accept_vis (TyVisitor &vis) override;
 434   void accept_vis (TyConstVisitor &vis) const override;
 435
 436   std::string as_string () const override;
 437
 438   BaseType *unify (BaseType *other) override;
 439   bool can_eq (const BaseType *other, bool emit_errors) const override final;
 440
 441   BaseType *clone () const final override;
 442   BaseType *monomorphized_clone () const final override;
 443
 444   std::string get_symbol () const;
 445
 446   HIR::GenericParam &get_generic_param () { return param; }
 447
 448   bool can_resolve () const { return get_ref () != get_ty_ref (); }
 449
 450   BaseType *resolve () const;
 451
 452   std::string get_name () const override final;
 453
 454   bool is_equal (const BaseType &other) const override;
 455
 456   bool is_concrete () const override final
 457   {
 458     auto r = resolve ();
 459     if (r == this)
 460       return false;
 461
 462     return r->is_concrete ();
 463   }
 464
 465   ParamType *handle_substitions (SubstitutionArgumentMappings mappings);
 466
 467 private:
 468   std::string symbol;
 469   HIR::GenericParam &param;
 470 };
 471
 472 class StructFieldType
 473 {
 474 public:
 475   StructFieldType (HirId ref, std::string name, BaseType *ty)
 476     : ref (ref), name (name), ty (ty)
 477   {}
 478
 479   HirId get_ref () const { return ref; }
 480
 481   std::string as_string () const;
 482
 483   bool is_equal (const StructFieldType &other) const;
 484
 485   std::string get_name () const { return name; }
 486
 487   BaseType *get_field_type () const { return ty; }
 488
 489   void set_field_type (BaseType *fty) { ty = fty; }
 490
 491   StructFieldType *clone () const;
 492
 493   StructFieldType *monomorphized_clone () const;
 494
 495   bool is_concrete () const { return ty->is_concrete (); }
 496
 497   void debug () const { rust_debug ("%s", as_string ().c_str ()); }
 498
 499 private:
 500   HirId ref;
 501   std::string name;
 502   BaseType *ty;
 503 };
 504
 505 class TupleType : public BaseType
 506 {
 507 public:
 508   TupleType (HirId ref, Location locus,
 509              std::vector<TyVar> fields = std::vector<TyVar> (),
 510              std::set<HirId> refs = std::set<HirId> ())
 511     : BaseType (ref, ref, TypeKind::TUPLE,
 512                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
 513       fields (fields)
 514   {}
 515
 516   TupleType (HirId ref, HirId ty_ref, Location locus,
 517              std::vector<TyVar> fields = std::vector<TyVar> (),
 518              std::set<HirId> refs = std::set<HirId> ())
 519     : BaseType (ref, ty_ref, TypeKind::TUPLE,
 520                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
 521       fields (fields)
 522   {}
 523
 524   static TupleType *get_unit_type (HirId ref)
 525   {
 526     return new TupleType (ref, Linemap::predeclared_location ());
 527   }
 528
 529   void accept_vis (TyVisitor &vis) override;
 530   void accept_vis (TyConstVisitor &vis) const override;
 531
 532   bool is_unit () const override { return this->fields.empty (); }
 533
 534   std::string as_string () const override;
 535
 536   BaseType *unify (BaseType *other) override;
 537   bool can_eq (const BaseType *other, bool emit_errors) const override final;
 538
 539   bool is_equal (const BaseType &other) const override;
 540
 541   size_t num_fields () const { return fields.size (); }
 542
 543   BaseType *get_field (size_t index) const;
 544
 545   BaseType *clone () const final override;
 546   BaseType *monomorphized_clone () const final override;
 547
 548   bool is_concrete () const override final
 549   {
 550     for (size_t i = 0; i < num_fields (); i++)
 551       {
 552         if (!get_field (i)->is_concrete ())
 553           return false;
 554       }
 555     return true;
 556   }
 557
 558   const std::vector<TyVar> &get_fields () const { return fields; }
 559
 560   std::string get_name () const override final { return as_string (); }
 561
 562   TupleType *handle_substitions (SubstitutionArgumentMappings mappings);
 563
 564 private:
 565   std::vector<TyVar> fields;
 566 };
 567
 568 class SubstitutionParamMapping
 569 {
 570 public:
 571   SubstitutionParamMapping (const HIR::TypeParam &generic, ParamType *param)
 572     : generic (generic), param (param)
 573   {}
 574
 575   SubstitutionParamMapping (const SubstitutionParamMapping &other)
 576     : generic (other.generic), param (other.param)
 577   {}
 578
 579   std::string as_string () const
 580   {
 581     if (param == nullptr)
 582       return "nullptr";
 583
 584     return param->get_name ();
 585   }
 586
 587   bool fill_param_ty (SubstitutionArgumentMappings &subst_mappings,
 588                       Location locus);
 589
 590   SubstitutionParamMapping clone () const
 591   {
 592     return SubstitutionParamMapping (generic, static_cast<ParamType *> (
 593                                                 param->clone ()));
 594   }
 595
 596   ParamType *get_param_ty () { return param; }
 597
 598   const ParamType *get_param_ty () const { return param; }
 599
 600   const HIR::TypeParam &get_generic_param () { return generic; };
 601
 602   // this is used for the backend to override the HirId ref of the param to
 603   // what the concrete type is for the rest of the context
 604   void override_context ();
 605
 606   bool needs_substitution () const
 607   {
 608     return !(get_param_ty ()->is_concrete ());
 609   }
 610
 611   Location get_param_locus () const { return generic.get_locus (); }
 612
 613   bool param_has_default_ty () const { return generic.has_type (); }
 614
 615   BaseType *get_default_ty () const
 616   {
 617     TyVar var (generic.get_type_mappings ().get_hirid ());
 618     return var.get_tyty ();
 619   }
 620
 621   bool need_substitution () const;
 622
 623 private:
 624   const HIR::TypeParam &generic;
 625   ParamType *param;
 626 };
 627
 628 class SubstitutionArg
 629 {
 630 public:
 631   SubstitutionArg (const SubstitutionParamMapping *param, BaseType *argument)
 632     : param (param), argument (argument)
 633   {}
 634
 635   // FIXME
 636   // the copy constructors need removed - they are unsafe see
 637   // TypeBoundPredicate
 638   SubstitutionArg (const SubstitutionArg &other)
 639     : param (other.param), argument (other.argument)
 640   {}
 641
 642   SubstitutionArg &operator= (const SubstitutionArg &other)
 643   {
 644     param = other.param;
 645     argument = other.argument;
 646     return *this;
 647   }
 648
 649   BaseType *get_tyty () { return argument; }
 650
 651   const BaseType *get_tyty () const { return argument; }
 652
 653   const SubstitutionParamMapping *get_param_mapping () const { return param; }
 654
 655   static SubstitutionArg error () { return SubstitutionArg (nullptr, nullptr); }
 656
 657   bool is_error () const { return param == nullptr || argument == nullptr; }
 658
 659   bool is_conrete () const
 660   {
 661     if (argument != nullptr)
 662       return true;
 663
 664     if (argument->get_kind () == TyTy::TypeKind::PARAM)
 665       return false;
 666
 667     return argument->is_concrete ();
 668   }
 669
 670   std::string as_string () const
 671   {
 672     return param->as_string ()
 673            + (argument != nullptr ? ":" + argument->as_string () : "");
 674   }
 675
 676 private:
 677   const SubstitutionParamMapping *param;
 678   BaseType *argument;
 679 };
 680
 681 typedef std::function<void (const ParamType &, const SubstitutionArg &)>
 682   ParamSubstCb;
 683 class SubstitutionArgumentMappings
 684 {
 685 public:
 686   SubstitutionArgumentMappings (std::vector<SubstitutionArg> mappings,
 687                                 Location locus,
 688                                 ParamSubstCb param_subst_cb = nullptr,
 689                                 bool trait_item_flag = false)
 690     : mappings (mappings), locus (locus), param_subst_cb (param_subst_cb),
 691       trait_item_flag (trait_item_flag)
 692   {}
 693
 694   SubstitutionArgumentMappings (const SubstitutionArgumentMappings &other)
 695     : mappings (other.mappings), locus (other.locus),
 696       param_subst_cb (other.param_subst_cb),
 697       trait_item_flag (other.trait_item_flag)
 698   {}
 699
 700   SubstitutionArgumentMappings &
 701   operator= (const SubstitutionArgumentMappings &other)
 702   {
 703     mappings = other.mappings;
 704     locus = other.locus;
 705     param_subst_cb = other.param_subst_cb;
 706     trait_item_flag = other.trait_item_flag;
 707
 708     return *this;
 709   }
 710
 711   static SubstitutionArgumentMappings error ()
 712   {
 713     return SubstitutionArgumentMappings ({}, Location (), nullptr, false);
 714   }
 715
 716   bool is_error () const { return mappings.size () == 0; }
 717
 718   bool get_argument_for_symbol (const ParamType *param_to_find,
 719                                 SubstitutionArg *argument)
 720   {
 721     for (auto &mapping : mappings)
 722       {
 723         const SubstitutionParamMapping *param = mapping.get_param_mapping ();
 724         const ParamType *p = param->get_param_ty ();
 725
 726         if (p->get_symbol ().compare (param_to_find->get_symbol ()) == 0)
 727           {
 728             *argument = mapping;
 729             return true;
 730           }
 731       }
 732     return false;
 733   }
 734
 735   bool get_argument_at (size_t index, SubstitutionArg *argument)
 736   {
 737     if (index > mappings.size ())
 738       return false;
 739
 740     *argument = mappings.at (index);
 741     return true;
 742   }
 743
 744   // is_concrete means if the used args is non error, ie: non empty this will
 745   // verify if actual real types have been put in place of are they still
 746   // ParamTy
 747   bool is_concrete () const
 748   {
 749     for (auto &mapping : mappings)
 750       {
 751         if (!mapping.is_conrete ())
 752           return false;
 753       }
 754     return true;
 755   }
 756
 757   Location get_locus () const { return locus; }
 758
 759   size_t size () const { return mappings.size (); }
 760
 761   bool is_empty () const { return size () == 0; }
 762
 763   std::vector<SubstitutionArg> &get_mappings () { return mappings; }
 764
 765   const std::vector<SubstitutionArg> &get_mappings () const { return mappings; }
 766
 767   std::string as_string () const
 768   {
 769     std::string buffer;
 770     for (auto &mapping : mappings)
 771       {
 772         buffer += mapping.as_string () + ", ";
 773       }
 774     return "<" + buffer + ">";
 775   }
 776
 777   void on_param_subst (const ParamType &p, const SubstitutionArg &a) const
 778   {
 779     if (param_subst_cb == nullptr)
 780       return;
 781
 782     param_subst_cb (p, a);
 783   }
 784
 785   ParamSubstCb get_subst_cb () const { return param_subst_cb; }
 786
 787   bool trait_item_mode () const { return trait_item_flag; }
 788
 789 private:
 790   std::vector<SubstitutionArg> mappings;
 791   Location locus;
 792   ParamSubstCb param_subst_cb;
 793   bool trait_item_flag;
 794 };
 795
 796 class SubstitutionRef
 797 {
 798 public:
 799   SubstitutionRef (std::vector<SubstitutionParamMapping> substitutions,
 800                    SubstitutionArgumentMappings arguments)
 801     : substitutions (substitutions), used_arguments (arguments)
 802   {}
 803
 804   bool has_substitutions () const { return substitutions.size () > 0; }
 805
 806   std::string subst_as_string () const
 807   {
 808     std::string buffer;
 809     for (size_t i = 0; i < substitutions.size (); i++)
 810       {
 811         const SubstitutionParamMapping &sub = substitutions.at (i);
 812         buffer += sub.as_string ();
 813
 814         if ((i + 1) < substitutions.size ())
 815           buffer += ", ";
 816       }
 817
 818     return buffer.empty () ? "" : "<" + buffer + ">";
 819   }
 820
 821   size_t get_num_substitutions () const { return substitutions.size (); }
 822
 823   std::vector<SubstitutionParamMapping> &get_substs () { return substitutions; }
 824
 825   const std::vector<SubstitutionParamMapping> &get_substs () const
 826   {
 827     return substitutions;
 828   }
 829
 830   std::vector<SubstitutionParamMapping> clone_substs () const
 831   {
 832     std::vector<SubstitutionParamMapping> clone;
 833
 834     for (auto &sub : substitutions)
 835       clone.push_back (sub.clone ());
 836
 837     return clone;
 838   }
 839
 840   void override_context ()
 841   {
 842     for (auto &sub : substitutions)
 843       {
 844         sub.override_context ();
 845       }
 846   }
 847
 848   bool needs_substitution () const
 849   {
 850     for (auto &sub : substitutions)
 851       {
 852         if (sub.need_substitution ())
 853           return true;
 854       }
 855     return false;
 856   }
 857
 858   bool was_substituted () const { return !needs_substitution (); }
 859
 860   SubstitutionArgumentMappings get_substitution_arguments () const
 861   {
 862     return used_arguments;
 863   }
 864
 865   // this is the count of type params that are not substituted fuly
 866   size_t num_required_substitutions () const
 867   {
 868     size_t n = 0;
 869     for (auto &p : substitutions)
 870       {
 871         if (p.needs_substitution ())
 872           n++;
 873       }
 874     return n;
 875   }
 876
 877   // this is the count of type params that need substituted taking into account
 878   // possible defaults
 879   size_t min_required_substitutions () const
 880   {
 881     size_t n = 0;
 882     for (auto &p : substitutions)
 883       {
 884         if (p.needs_substitution () && !p.param_has_default_ty ())
 885           n++;
 886       }
 887     return n;
 888   }
 889
 890   // We are trying to subst <i32, f32> into Struct Foo<X,Y> {}
 891   // in the case of Foo<i32,f32>{...}
 892   //
 893   // the substitions we have here define X,Y but the arguments have no bindings
 894   // so its a matter of ordering
 895   SubstitutionArgumentMappings
 896   get_mappings_from_generic_args (HIR::GenericArgs &args);
 897
 898   // Recursive substitutions
 899   // Foo <A,B> { a:A, b: B}; Bar <X,Y,Z>{a:X, b: Foo<Y,Z>}
 900   //
 901   // we have bindings for X Y Z and need to propagate the binding Y,Z into Foo
 902   // Which binds to A,B
 903   SubstitutionArgumentMappings
 904   adjust_mappings_for_this (SubstitutionArgumentMappings &mappings);
 905
 906   // Are the mappings here actually bound to this type. For example imagine the
 907   // case:
 908   //
 909   // struct Foo<T>(T);
 910   // impl<T> Foo<T> {
 911   //   fn test(self) { ... }
 912   // }
 913   //
 914   // In this case we have a generic ADT of Foo and an impl block of a generic T
 915   // on Foo for the Self type. When we it comes to path resolution we can have:
 916   //
 917   // Foo::<i32>::test()
 918   //
 919   // This means the first segment of Foo::<i32> returns the ADT Foo<i32> not the
 920   // Self ADT bound to the T from the impl block. This means when it comes to
 921   // the next segment of test which resolves to the function we need to check
 922   // wether the arguments in the struct definition of foo can be bound here
 923   // before substituting the previous segments type here. This functions acts as
 924   // a guard for the solve_mappings_from_receiver_for_self to handle the case
 925   // where arguments are not bound. This is important for this next case:
 926   //
 927   // struct Baz<A, B>(A, B);
 928   // impl Baz<i32, f32> {
 929   //   fn test<X>(a: X) -> X {
 930   //       a
 931   //   }
 932   // }
 933   //
 934   // In this case Baz has been already substituted for the impl's Self to become
 935   // ADT<i32, f32> so that the function test only has 1 generic argument of X.
 936   // The path for this will be:
 937   //
 938   // Baz::test::<_>(123)
 939   //
 940   // So the first segment here will be Baz<_, _> to try and infer the arguments
 941   // which will be taken from the impl's Self type in this case since it is
 942   // already substituted and like the previous case the check to see if we need
 943   // to inherit the previous segments generic arguments takes place but the
 944   // generic arguments are not bound to this type as they have already been
 945   // substituted.
 946   //
 947   // Its important to remember from the first example the FnType actually looks
 948   // like:
 949   //
 950   // fn <T>test(self :Foo<T>(T))
 951   //
 952   // As the generic parameters are "bound" to each of the items in the impl
 953   // block. So this check is about wether the arguments we have here can
 954   // actually be bound to this type.
 955   bool are_mappings_bound (SubstitutionArgumentMappings &mappings);
 956
 957   // struct Foo<A, B>(A, B);
 958   //
 959   // impl<T> Foo<T, f32>;
 960   //     -> fn test<X>(self, a: X) -> X
 961   //
 962   // We might invoke this via:
 963   //
 964   // a = Foo(123, 456f32);
 965   // b = a.test::<bool>(false);
 966   //
 967   // we need to figure out relevant generic arguemts for self to apply to the
 968   // fntype
 969   SubstitutionArgumentMappings solve_mappings_from_receiver_for_self (
 970     SubstitutionArgumentMappings &mappings) const;
 971
 972   // TODO comment
 973   SubstitutionArgumentMappings
 974   solve_missing_mappings_from_this (SubstitutionRef &ref, SubstitutionRef &to);
 975
 976   // TODO comment
 977   BaseType *infer_substitions (Location locus)
 978   {
 979     std::vector<SubstitutionArg> args;
 980     std::map<std::string, BaseType *> argument_mappings;
 981     for (auto &p : get_substs ())
 982       {
 983         if (p.needs_substitution ())
 984           {
 985             const std::string &symbol = p.get_param_ty ()->get_symbol ();
 986             auto it = argument_mappings.find (symbol);
 987             if (it == argument_mappings.end ())
 988               {
 989                 TyVar infer_var = TyVar::get_implicit_infer_var (locus);
 990                 args.push_back (SubstitutionArg (&p, infer_var.get_tyty ()));
 991                 argument_mappings[symbol] = infer_var.get_tyty ();
 992               }
 993             else
 994               {
 995                 args.push_back (SubstitutionArg (&p, it->second));
 996               }
 997           }
 998         else
 999           {
1000             args.push_back (
1001               SubstitutionArg (&p, p.get_param_ty ()->resolve ()));
1002           }
1003       }
1004
1005     SubstitutionArgumentMappings infer_arguments (std::move (args), locus);
1006     return handle_substitions (std::move (infer_arguments));
1007   }
1008
1009   // TODO comment
1010   bool monomorphize ();
1011
1012   // TODO comment
1013   virtual BaseType *handle_substitions (SubstitutionArgumentMappings mappings)
1014     = 0;
1015
1016   SubstitutionArgumentMappings get_used_arguments () const
1017   {
1018     return used_arguments;
1019   }
1020
1021 protected:
1022   std::vector<SubstitutionParamMapping> substitutions;
1023   SubstitutionArgumentMappings used_arguments;
1024 };
1025
1026 class TypeBoundPredicate : public SubstitutionRef
1027 {
1028 public:
1029   TypeBoundPredicate (const Resolver::TraitReference &trait_reference,
1030                       Location locus);
1031
1032   TypeBoundPredicate (DefId reference,
1033                       std::vector<SubstitutionParamMapping> substitutions,
1034                       Location locus);
1035
1036   TypeBoundPredicate (const TypeBoundPredicate &other);
1037
1038   TypeBoundPredicate &operator= (const TypeBoundPredicate &other);
1039
1040   static TypeBoundPredicate error ();
1041
1042   std::string as_string () const;
1043
1044   std::string as_name () const;
1045
1046   const Resolver::TraitReference *get () const;
1047
1048   Location get_locus () const { return locus; }
1049
1050   std::string get_name () const;
1051
1052   // check that this predicate is object-safe see:
1053   // https://doc.rust-lang.org/reference/items/traits.html#object-safety
1054   bool is_object_safe (bool emit_error, Location locus) const;
1055
1056   void apply_generic_arguments (HIR::GenericArgs *generic_args);
1057
1058   bool contains_item (const std::string &search) const;
1059
1060   TypeBoundPredicateItem
1061   lookup_associated_item (const std::string &search) const;
1062
1063   TypeBoundPredicateItem
1064   lookup_associated_item (const Resolver::TraitItemReference *ref) const;
1065
1066   // WARNING THIS WILL ALWAYS RETURN NULLPTR
1067   BaseType *
1068   handle_substitions (SubstitutionArgumentMappings mappings) override final;
1069
1070   bool is_error () const;
1071
1072   bool requires_generic_args () const;
1073
1074 private:
1075   DefId reference;
1076   Location locus;
1077   bool error_flag;
1078 };
1079
1080 // https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.VariantDef.html
1081 class VariantDef
1082 {
1083 public:
1084   enum VariantType
1085   {
1086     NUM,
1087     TUPLE,
1088     STRUCT
1089   };
1090
1091   static std::string variant_type_string (VariantType type)
1092   {
1093     switch (type)
1094       {
1095       case NUM:
1096         return "enumeral";
1097       case TUPLE:
1098         return "tuple";
1099       case STRUCT:
1100         return "struct";
1101       }
1102     gcc_unreachable ();
1103     return "";
1104   }
1105
1106   VariantDef (HirId id, std::string identifier, RustIdent ident,
1107               HIR::Expr *discriminant)
1108     : id (id), identifier (identifier), ident (ident),
1109       discriminant (discriminant)
1110
1111   {
1112     type = VariantType::NUM;
1113     fields = {};
1114   }
1115
1116   VariantDef (HirId id, std::string identifier, RustIdent ident,
1117               VariantType type, HIR::Expr *discriminant,
1118               std::vector<StructFieldType *> fields)
1119     : id (id), identifier (identifier), ident (ident), type (type),
1120       discriminant (discriminant), fields (fields)
1121   {
1122     rust_assert (
1123       (type == VariantType::NUM && fields.empty ())
1124       || (type == VariantType::TUPLE || type == VariantType::STRUCT));
1125   }
1126
1127   VariantDef (const VariantDef &other)
1128     : id (other.id), identifier (other.identifier), ident (other.ident),
1129       type (other.type), discriminant (other.discriminant),
1130       fields (other.fields)
1131   {}
1132
1133   VariantDef &operator= (const VariantDef &other)
1134   {
1135     id = other.id;
1136     identifier = other.identifier;
1137     type = other.type;
1138     discriminant = other.discriminant;
1139     fields = other.fields;
1140     ident = other.ident;
1141
1142     return *this;
1143   }
1144
1145   static VariantDef &get_error_node ()
1146   {
1147     static VariantDef node
1148       = VariantDef (UNKNOWN_HIRID, "",
1149                     {Resolver::CanonicalPath::create_empty (),
1150                      Linemap::unknown_location ()},
1151                     nullptr);
1152
1153     return node;
1154   }
1155
1156   bool is_error () const { return get_id () == UNKNOWN_HIRID; }
1157
1158   HirId get_id () const { return id; }
1159
1160   VariantType get_variant_type () const { return type; }
1161   bool is_data_variant () const { return type != VariantType::NUM; }
1162   bool is_dataless_variant () const { return type == VariantType::NUM; }
1163
1164   std::string get_identifier () const { return identifier; }
1165
1166   size_t num_fields () const { return fields.size (); }
1167   StructFieldType *get_field_at_index (size_t index)
1168   {
1169     rust_assert (index < fields.size ());
1170     return fields.at (index);
1171   }
1172
1173   std::vector<StructFieldType *> &get_fields ()
1174   {
1175     rust_assert (type != NUM);
1176     return fields;
1177   }
1178
1179   bool lookup_field (const std::string &lookup, StructFieldType **field_lookup,
1180                      size_t *index) const
1181   {
1182     size_t i = 0;
1183     for (auto &field : fields)
1184       {
1185         if (field->get_name ().compare (lookup) == 0)
1186           {
1187             if (index != nullptr)
1188               *index = i;
1189
1190             if (field_lookup != nullptr)
1191               *field_lookup = field;
1192
1193             return true;
1194           }
1195         i++;
1196       }
1197     return false;
1198   }
1199
1200   HIR::Expr *get_discriminant () const
1201   {
1202     rust_assert (discriminant != nullptr);
1203     return discriminant;
1204   }
1205
1206   std::string as_string () const
1207   {
1208     if (type == VariantType::NUM)
1209       return identifier + " = " + discriminant->as_string ();
1210
1211     std::string buffer;
1212     for (size_t i = 0; i < fields.size (); ++i)
1213       {
1214         buffer += fields.at (i)->as_string ();
1215         if ((i + 1) < fields.size ())
1216           buffer += ", ";
1217       }
1218
1219     if (type == VariantType::TUPLE)
1220       return identifier + " (" + buffer + ")";
1221     else
1222       return identifier + " {" + buffer + "}";
1223   }
1224
1225   bool is_equal (const VariantDef &other) const
1226   {
1227     if (type != other.type)
1228       return false;
1229
1230     if (identifier.compare (other.identifier) != 0)
1231       return false;
1232
1233     if (discriminant != other.discriminant)
1234       return false;
1235
1236     if (fields.size () != other.fields.size ())
1237       return false;
1238
1239     for (size_t i = 0; i < fields.size (); i++)
1240       {
1241         if (!fields.at (i)->is_equal (*other.fields.at (i)))
1242           return false;
1243       }
1244
1245     return true;
1246   }
1247
1248   VariantDef *clone () const
1249   {
1250     std::vector<StructFieldType *> cloned_fields;
1251     for (auto &f : fields)
1252       cloned_fields.push_back ((StructFieldType *) f->clone ());
1253
1254     return new VariantDef (id, identifier, ident, type, discriminant,
1255                            cloned_fields);
1256   }
1257
1258   VariantDef *monomorphized_clone () const
1259   {
1260     std::vector<StructFieldType *> cloned_fields;
1261     for (auto &f : fields)
1262       cloned_fields.push_back ((StructFieldType *) f->monomorphized_clone ());
1263
1264     return new VariantDef (id, identifier, ident, type, discriminant,
1265                            cloned_fields);
1266   }
1267
1268   const RustIdent &get_ident () const { return ident; }
1269
1270 private:
1271   HirId id;
1272   std::string identifier;
1273   RustIdent ident;
1274   VariantType type;
1275   // can either be a structure or a discriminant value
1276   HIR::Expr *discriminant;
1277   std::vector<StructFieldType *> fields;
1278 };
1279
1280 class ADTType : public BaseType, public SubstitutionRef
1281 {
1282 public:
1283   enum ADTKind
1284   {
1285     STRUCT_STRUCT,
1286     TUPLE_STRUCT,
1287     UNION,
1288     ENUM
1289   };
1290
1291   // Representation options, specified via attributes e.g. #[repr(packed)]
1292   struct ReprOptions
1293   {
1294     // bool is_c;
1295     // bool is_transparent;
1296     //...
1297
1298     // For align and pack: 0 = unspecified. Nonzero = byte alignment.
1299     // It is an error for both to be nonzero, this should be caught when
1300     // parsing the #[repr] attribute.
1301     unsigned char align = 0;
1302     unsigned char pack = 0;
1303   };
1304
1305   ADTType (HirId ref, std::string identifier, RustIdent ident, ADTKind adt_kind,
1306            std::vector<VariantDef *> variants,
1307            std::vector<SubstitutionParamMapping> subst_refs,
1308            SubstitutionArgumentMappings generic_arguments
1309            = SubstitutionArgumentMappings::error (),
1310            std::set<HirId> refs = std::set<HirId> ())
1311     : BaseType (ref, ref, TypeKind::ADT, ident, refs),
1312       SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
1313       identifier (identifier), variants (variants), adt_kind (adt_kind)
1314   {}
1315
1316   ADTType (HirId ref, HirId ty_ref, std::string identifier, RustIdent ident,
1317            ADTKind adt_kind, std::vector<VariantDef *> variants,
1318            std::vector<SubstitutionParamMapping> subst_refs,
1319            SubstitutionArgumentMappings generic_arguments
1320            = SubstitutionArgumentMappings::error (),
1321            std::set<HirId> refs = std::set<HirId> ())
1322     : BaseType (ref, ty_ref, TypeKind::ADT, ident, refs),
1323       SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
1324       identifier (identifier), variants (variants), adt_kind (adt_kind)
1325   {}
1326
1327   ADTType (HirId ref, HirId ty_ref, std::string identifier, RustIdent ident,
1328            ADTKind adt_kind, std::vector<VariantDef *> variants,
1329            std::vector<SubstitutionParamMapping> subst_refs, ReprOptions repr,
1330            SubstitutionArgumentMappings generic_arguments
1331            = SubstitutionArgumentMappings::error (),
1332            std::set<HirId> refs = std::set<HirId> ())
1333     : BaseType (ref, ty_ref, TypeKind::ADT, ident, refs),
1334       SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
1335       identifier (identifier), variants (variants), adt_kind (adt_kind),
1336       repr (repr)
1337   {}
1338
1339   ADTKind get_adt_kind () const { return adt_kind; }
1340   ReprOptions get_repr_options () const { return repr; }
1341
1342   bool is_struct_struct () const { return adt_kind == STRUCT_STRUCT; }
1343   bool is_tuple_struct () const { return adt_kind == TUPLE_STRUCT; }
1344   bool is_union () const { return adt_kind == UNION; }
1345   bool is_enum () const { return adt_kind == ENUM; }
1346
1347   bool is_unit () const override
1348   {
1349     if (number_of_variants () == 0)
1350       return true;
1351
1352     if (number_of_variants () == 1)
1353       return variants.at (0)->num_fields () == 0;
1354
1355     return false;
1356   }
1357
1358   void accept_vis (TyVisitor &vis) override;
1359   void accept_vis (TyConstVisitor &vis) const override;
1360
1361   std::string as_string () const override;
1362
1363   BaseType *unify (BaseType *other) override;
1364   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1365
1366   bool is_equal (const BaseType &other) const override;
1367
1368   std::string get_identifier () const { return identifier; }
1369
1370   std::string get_name () const override final
1371   {
1372     return identifier + subst_as_string ();
1373   }
1374
1375   bool is_concrete () const override final
1376   {
1377     for (auto &variant : variants)
1378       {
1379         for (auto &field : variant->get_fields ())
1380           {
1381             if (!field->is_concrete ())
1382               return false;
1383           }
1384       }
1385     return true;
1386   }
1387
1388   BaseType *clone () const final override;
1389   BaseType *monomorphized_clone () const final override;
1390
1391   bool needs_generic_substitutions () const override final
1392   {
1393     return needs_substitution ();
1394   }
1395
1396   bool supports_substitutions () const override final { return true; }
1397
1398   bool has_subsititions_defined () const override final
1399   {
1400     return has_substitutions ();
1401   }
1402
1403   size_t number_of_variants () const { return variants.size (); }
1404
1405   std::vector<VariantDef *> &get_variants () { return variants; }
1406   const std::vector<VariantDef *> &get_variants () const { return variants; }
1407
1408   bool lookup_variant (const std::string &lookup,
1409                        VariantDef **found_variant) const
1410   {
1411     for (auto &variant : variants)
1412       {
1413         if (variant->get_identifier ().compare (lookup) == 0)
1414           {
1415             *found_variant = variant;
1416             return true;
1417           }
1418       }
1419     return false;
1420   }
1421
1422   bool lookup_variant_by_id (HirId id, VariantDef **found_variant,
1423                              int *index = nullptr) const
1424   {
1425     int i = 0;
1426     for (auto &variant : variants)
1427       {
1428         if (variant->get_id () == id)
1429           {
1430             if (index != nullptr)
1431               *index = i;
1432
1433             *found_variant = variant;
1434             return true;
1435           }
1436         i++;
1437       }
1438     return false;
1439   }
1440
1441   ADTType *
1442   handle_substitions (SubstitutionArgumentMappings mappings) override final;
1443
1444 private:
1445   std::string identifier;
1446   std::vector<VariantDef *> variants;
1447   ADTType::ADTKind adt_kind;
1448   ReprOptions repr;
1449 };
1450
1451 class FnType : public BaseType, public SubstitutionRef
1452 {
1453 public:
1454   static const uint8_t FNTYPE_DEFAULT_FLAGS = 0x00;
1455   static const uint8_t FNTYPE_IS_METHOD_FLAG = 0x01;
1456   static const uint8_t FNTYPE_IS_EXTERN_FLAG = 0x02;
1457   static const uint8_t FNTYPE_IS_VARADIC_FLAG = 0X04;
1458
1459   FnType (HirId ref, DefId id, std::string identifier, RustIdent ident,
1460           uint8_t flags, ABI abi,
1461           std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
1462           BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
1463           std::set<HirId> refs = std::set<HirId> ())
1464     : BaseType (ref, ref, TypeKind::FNDEF, ident, refs),
1465       SubstitutionRef (std::move (subst_refs),
1466                        SubstitutionArgumentMappings::error ()),
1467       params (std::move (params)), type (type), flags (flags),
1468       identifier (identifier), id (id), abi (abi)
1469   {
1470     LocalDefId local_def_id = id.localDefId;
1471     rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
1472   }
1473
1474   FnType (HirId ref, HirId ty_ref, DefId id, std::string identifier,
1475           RustIdent ident, uint8_t flags, ABI abi,
1476           std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
1477           BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
1478           std::set<HirId> refs = std::set<HirId> ())
1479     : BaseType (ref, ty_ref, TypeKind::FNDEF, ident, refs),
1480       SubstitutionRef (std::move (subst_refs),
1481                        SubstitutionArgumentMappings::error ()),
1482       params (params), type (type), flags (flags), identifier (identifier),
1483       id (id), abi (abi)
1484   {
1485     LocalDefId local_def_id = id.localDefId;
1486     rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
1487   }
1488
1489   void accept_vis (TyVisitor &vis) override;
1490   void accept_vis (TyConstVisitor &vis) const override;
1491
1492   std::string as_string () const override;
1493
1494   std::string get_name () const override final { return as_string (); }
1495
1496   std::string get_identifier () const { return identifier; }
1497
1498   BaseType *unify (BaseType *other) override;
1499   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1500
1501   bool is_equal (const BaseType &other) const override;
1502
1503   size_t num_params () const { return params.size (); }
1504
1505   bool is_method () const
1506   {
1507     if (num_params () == 0)
1508       return false;
1509
1510     return (flags & FNTYPE_IS_METHOD_FLAG) != 0;
1511   }
1512
1513   bool is_extern () const { return (flags & FNTYPE_IS_EXTERN_FLAG) != 0; }
1514
1515   bool is_varadic () const { return (flags & FNTYPE_IS_VARADIC_FLAG) != 0; }
1516
1517   DefId get_id () const { return id; }
1518
1519   // get the Self type for the method
1520   BaseType *get_self_type () const
1521   {
1522     rust_assert (is_method ());
1523     return param_at (0).second;
1524   }
1525
1526   bool is_concrete () const override final
1527   {
1528     for (const auto &param : params)
1529       {
1530         const BaseType *p = param.second;
1531         if (!p->is_concrete ())
1532           return false;
1533       }
1534     return get_return_type ()->is_concrete ();
1535   }
1536
1537   std::vector<std::pair<HIR::Pattern *, BaseType *>> &get_params ()
1538   {
1539     return params;
1540   }
1541
1542   const std::vector<std::pair<HIR::Pattern *, BaseType *>> &get_params () const
1543   {
1544     return params;
1545   }
1546
1547   std::pair<HIR::Pattern *, BaseType *> &param_at (size_t idx)
1548   {
1549     return params.at (idx);
1550   }
1551
1552   const std::pair<HIR::Pattern *, BaseType *> &param_at (size_t idx) const
1553   {
1554     return params.at (idx);
1555   }
1556
1557   BaseType *get_return_type () const { return type; }
1558
1559   BaseType *clone () const final override;
1560   BaseType *monomorphized_clone () const final override;
1561
1562   bool needs_generic_substitutions () const override final
1563   {
1564     return needs_substitution ();
1565   }
1566
1567   bool supports_substitutions () const override final { return true; }
1568
1569   bool has_subsititions_defined () const override final
1570   {
1571     return has_substitutions ();
1572   }
1573
1574   FnType *
1575   handle_substitions (SubstitutionArgumentMappings mappings) override final;
1576
1577   ABI get_abi () const { return abi; }
1578
1579 private:
1580   std::vector<std::pair<HIR::Pattern *, BaseType *>> params;
1581   BaseType *type;
1582   uint8_t flags;
1583   std::string identifier;
1584   DefId id;
1585   ABI abi;
1586 };
1587
1588 class FnPtr : public BaseType
1589 {
1590 public:
1591   FnPtr (HirId ref, Location locus, std::vector<TyVar> params,
1592          TyVar result_type, std::set<HirId> refs = std::set<HirId> ())
1593     : BaseType (ref, ref, TypeKind::FNPTR,
1594                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
1595       params (std::move (params)), result_type (result_type)
1596   {}
1597
1598   FnPtr (HirId ref, HirId ty_ref, Location locus, std::vector<TyVar> params,
1599          TyVar result_type, std::set<HirId> refs = std::set<HirId> ())
1600     : BaseType (ref, ty_ref, TypeKind::FNPTR,
1601                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
1602       params (params), result_type (result_type)
1603   {}
1604
1605   std::string get_name () const override final { return as_string (); }
1606
1607   BaseType *get_return_type () const { return result_type.get_tyty (); }
1608
1609   size_t num_params () const { return params.size (); }
1610
1611   BaseType *param_at (size_t idx) const { return params.at (idx).get_tyty (); }
1612
1613   void accept_vis (TyVisitor &vis) override;
1614   void accept_vis (TyConstVisitor &vis) const override;
1615
1616   std::string as_string () const override;
1617
1618   BaseType *unify (BaseType *other) override;
1619   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1620
1621   bool is_equal (const BaseType &other) const override;
1622
1623   BaseType *clone () const final override;
1624   BaseType *monomorphized_clone () const final override;
1625
1626   void iterate_params (std::function<bool (BaseType *)> cb) const
1627   {
1628     for (auto &p : params)
1629       {
1630         if (!cb (p.get_tyty ()))
1631           return;
1632       }
1633   }
1634
1635   std::vector<TyVar> &get_params () { return params; }
1636   const std::vector<TyVar> &get_params () const { return params; }
1637
1638   bool is_concrete () const override final
1639   {
1640     for (auto &p : params)
1641       {
1642         if (!p.get_tyty ()->is_concrete ())
1643           return false;
1644       }
1645     return result_type.get_tyty ()->is_concrete ();
1646   }
1647
1648 private:
1649   std::vector<TyVar> params;
1650   TyVar result_type;
1651 };
1652
1653 class ClosureType : public BaseType, public SubstitutionRef
1654 {
1655 public:
1656   ClosureType (HirId ref, DefId id, RustIdent ident,
1657                std::vector<TyVar> parameter_types, TyVar result_type,
1658                std::vector<SubstitutionParamMapping> subst_refs,
1659                std::set<HirId> refs = std::set<HirId> ())
1660     : BaseType (ref, ref, TypeKind::CLOSURE, ident, refs),
1661       SubstitutionRef (std::move (subst_refs),
1662                        SubstitutionArgumentMappings::error ()),
1663       parameter_types (std::move (parameter_types)),
1664       result_type (std::move (result_type)), id (id)
1665   {
1666     LocalDefId local_def_id = id.localDefId;
1667     rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
1668   }
1669
1670   ClosureType (HirId ref, HirId ty_ref, RustIdent ident, DefId id,
1671                std::vector<TyVar> parameter_types, TyVar result_type,
1672                std::vector<SubstitutionParamMapping> subst_refs,
1673                std::set<HirId> refs = std::set<HirId> ())
1674     : BaseType (ref, ty_ref, TypeKind::CLOSURE, ident, refs),
1675       SubstitutionRef (std::move (subst_refs),
1676                        SubstitutionArgumentMappings::error ()),
1677       parameter_types (std::move (parameter_types)),
1678       result_type (std::move (result_type)), id (id)
1679   {
1680     LocalDefId local_def_id = id.localDefId;
1681     rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
1682   }
1683
1684   void accept_vis (TyVisitor &vis) override;
1685   void accept_vis (TyConstVisitor &vis) const override;
1686
1687   std::string as_string () const override;
1688   std::string get_name () const override final { return as_string (); }
1689
1690   BaseType *unify (BaseType *other) override;
1691   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1692
1693   bool is_equal (const BaseType &other) const override;
1694
1695   BaseType *clone () const final override;
1696   BaseType *monomorphized_clone () const final override;
1697
1698   bool is_concrete () const override final
1699   {
1700     for (auto &param : parameter_types)
1701       {
1702         auto p = param.get_tyty ();
1703         if (!p->is_concrete ())
1704           return false;
1705       }
1706     return result_type.get_tyty ()->is_concrete ();
1707   }
1708
1709   bool needs_generic_substitutions () const override final
1710   {
1711     return needs_substitution ();
1712   }
1713
1714   bool supports_substitutions () const override final { return true; }
1715
1716   bool has_subsititions_defined () const override final
1717   {
1718     return has_substitutions ();
1719   }
1720
1721   ClosureType *
1722   handle_substitions (SubstitutionArgumentMappings mappings) override final;
1723
1724 private:
1725   std::vector<TyVar> parameter_types;
1726   TyVar result_type;
1727   DefId id;
1728 };
1729
1730 class ArrayType : public BaseType
1731 {
1732 public:
1733   ArrayType (HirId ref, Location locus, HIR::Expr &capacity_expr, TyVar base,
1734              std::set<HirId> refs = std::set<HirId> ())
1735     : BaseType (ref, ref, TypeKind::ARRAY,
1736                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
1737       element_type (base), capacity_expr (capacity_expr)
1738   {}
1739
1740   ArrayType (HirId ref, HirId ty_ref, Location locus, HIR::Expr &capacity_expr,
1741              TyVar base, std::set<HirId> refs = std::set<HirId> ())
1742     : BaseType (ref, ty_ref, TypeKind::ARRAY,
1743                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
1744       element_type (base), capacity_expr (capacity_expr)
1745   {}
1746
1747   void accept_vis (TyVisitor &vis) override;
1748   void accept_vis (TyConstVisitor &vis) const override;
1749
1750   std::string as_string () const override;
1751
1752   std::string get_name () const override final { return as_string (); }
1753
1754   BaseType *unify (BaseType *other) override;
1755   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1756
1757   bool is_equal (const BaseType &other) const override;
1758
1759   BaseType *get_element_type () const;
1760
1761   BaseType *clone () const final override;
1762   BaseType *monomorphized_clone () const final override;
1763
1764   bool is_concrete () const final override
1765   {
1766     return get_element_type ()->is_concrete ();
1767   }
1768
1769   HIR::Expr &get_capacity_expr () const { return capacity_expr; }
1770
1771   ArrayType *handle_substitions (SubstitutionArgumentMappings mappings);
1772
1773 private:
1774   TyVar element_type;
1775   HIR::Expr &capacity_expr;
1776 };
1777
1778 class SliceType : public BaseType
1779 {
1780 public:
1781   SliceType (HirId ref, Location locus, TyVar base,
1782              std::set<HirId> refs = std::set<HirId> ())
1783     : BaseType (ref, ref, TypeKind::SLICE,
1784                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
1785       element_type (base)
1786   {}
1787
1788   SliceType (HirId ref, HirId ty_ref, Location locus, TyVar base,
1789              std::set<HirId> refs = std::set<HirId> ())
1790     : BaseType (ref, ty_ref, TypeKind::SLICE,
1791                 {Resolver::CanonicalPath::create_empty (), locus}, refs),
1792       element_type (base)
1793   {}
1794
1795   void accept_vis (TyVisitor &vis) override;
1796   void accept_vis (TyConstVisitor &vis) const override;
1797
1798   std::string as_string () const override;
1799
1800   std::string get_name () const override final { return as_string (); }
1801
1802   BaseType *unify (BaseType *other) override;
1803   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1804
1805   bool is_equal (const BaseType &other) const override;
1806
1807   BaseType *get_element_type () const;
1808
1809   BaseType *clone () const final override;
1810   BaseType *monomorphized_clone () const final override;
1811
1812   bool is_concrete () const final override
1813   {
1814     return get_element_type ()->is_concrete ();
1815   }
1816
1817   SliceType *handle_substitions (SubstitutionArgumentMappings mappings);
1818
1819 private:
1820   TyVar element_type;
1821 };
1822
1823 class BoolType : public BaseType
1824 {
1825 public:
1826   BoolType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
1827     : BaseType (ref, ref, TypeKind::BOOL,
1828                 {Resolver::CanonicalPath::create_empty (),
1829                  Linemap::predeclared_location ()},
1830                 refs)
1831   {}
1832
1833   BoolType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
1834     : BaseType (ref, ty_ref, TypeKind::BOOL,
1835                 {Resolver::CanonicalPath::create_empty (),
1836                  Linemap::predeclared_location ()},
1837                 refs)
1838   {}
1839
1840   void accept_vis (TyVisitor &vis) override;
1841   void accept_vis (TyConstVisitor &vis) const override;
1842
1843   std::string as_string () const override;
1844
1845   std::string get_name () const override final { return as_string (); }
1846
1847   BaseType *unify (BaseType *other) override;
1848   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1849
1850   BaseType *clone () const final override;
1851   BaseType *monomorphized_clone () const final override;
1852   bool is_concrete () const override final { return true; }
1853 };
1854
1855 class IntType : public BaseType
1856 {
1857 public:
1858   enum IntKind
1859   {
1860     I8,
1861     I16,
1862     I32,
1863     I64,
1864     I128
1865   };
1866
1867   IntType (HirId ref, IntKind kind, std::set<HirId> refs = std::set<HirId> ())
1868     : BaseType (ref, ref, TypeKind::INT,
1869                 {Resolver::CanonicalPath::create_empty (),
1870                  Linemap::predeclared_location ()},
1871                 refs),
1872       int_kind (kind)
1873   {}
1874
1875   IntType (HirId ref, HirId ty_ref, IntKind kind,
1876            std::set<HirId> refs = std::set<HirId> ())
1877     : BaseType (ref, ty_ref, TypeKind::INT,
1878                 {Resolver::CanonicalPath::create_empty (),
1879                  Linemap::predeclared_location ()},
1880                 refs),
1881       int_kind (kind)
1882   {}
1883
1884   void accept_vis (TyVisitor &vis) override;
1885   void accept_vis (TyConstVisitor &vis) const override;
1886
1887   std::string as_string () const override;
1888
1889   std::string get_name () const override final { return as_string (); }
1890
1891   BaseType *unify (BaseType *other) override;
1892   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1893
1894   IntKind get_int_kind () const { return int_kind; }
1895
1896   BaseType *clone () const final override;
1897   BaseType *monomorphized_clone () const final override;
1898
1899   bool is_equal (const BaseType &other) const override;
1900   bool is_concrete () const override final { return true; }
1901
1902 private:
1903   IntKind int_kind;
1904 };
1905
1906 class UintType : public BaseType
1907 {
1908 public:
1909   enum UintKind
1910   {
1911     U8,
1912     U16,
1913     U32,
1914     U64,
1915     U128
1916   };
1917
1918   UintType (HirId ref, UintKind kind, std::set<HirId> refs = std::set<HirId> ())
1919     : BaseType (ref, ref, TypeKind::UINT,
1920                 {Resolver::CanonicalPath::create_empty (),
1921                  Linemap::predeclared_location ()},
1922                 refs),
1923       uint_kind (kind)
1924   {}
1925
1926   UintType (HirId ref, HirId ty_ref, UintKind kind,
1927             std::set<HirId> refs = std::set<HirId> ())
1928     : BaseType (ref, ty_ref, TypeKind::UINT,
1929                 {Resolver::CanonicalPath::create_empty (),
1930                  Linemap::predeclared_location ()},
1931                 refs),
1932       uint_kind (kind)
1933   {}
1934
1935   void accept_vis (TyVisitor &vis) override;
1936   void accept_vis (TyConstVisitor &vis) const override;
1937
1938   std::string as_string () const override;
1939
1940   std::string get_name () const override final { return as_string (); }
1941
1942   BaseType *unify (BaseType *other) override;
1943   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1944
1945   UintKind get_uint_kind () const { return uint_kind; }
1946
1947   BaseType *clone () const final override;
1948   BaseType *monomorphized_clone () const final override;
1949
1950   bool is_equal (const BaseType &other) const override;
1951   bool is_concrete () const override final { return true; }
1952
1953 private:
1954   UintKind uint_kind;
1955 };
1956
1957 class FloatType : public BaseType
1958 {
1959 public:
1960   enum FloatKind
1961   {
1962     F32,
1963     F64
1964   };
1965
1966   FloatType (HirId ref, FloatKind kind,
1967              std::set<HirId> refs = std::set<HirId> ())
1968     : BaseType (ref, ref, TypeKind::FLOAT,
1969                 {Resolver::CanonicalPath::create_empty (),
1970                  Linemap::predeclared_location ()},
1971                 refs),
1972       float_kind (kind)
1973   {}
1974
1975   FloatType (HirId ref, HirId ty_ref, FloatKind kind,
1976              std::set<HirId> refs = std::set<HirId> ())
1977     : BaseType (ref, ty_ref, TypeKind::FLOAT,
1978                 {Resolver::CanonicalPath::create_empty (),
1979                  Linemap::predeclared_location ()},
1980                 refs),
1981       float_kind (kind)
1982   {}
1983
1984   void accept_vis (TyVisitor &vis) override;
1985   void accept_vis (TyConstVisitor &vis) const override;
1986
1987   std::string as_string () const override;
1988
1989   std::string get_name () const override final { return as_string (); }
1990
1991   BaseType *unify (BaseType *other) override;
1992   bool can_eq (const BaseType *other, bool emit_errors) const override final;
1993
1994   FloatKind get_float_kind () const { return float_kind; }
1995
1996   BaseType *clone () const final override;
1997   BaseType *monomorphized_clone () const final override;
1998
1999   bool is_equal (const BaseType &other) const override;
2000   bool is_concrete () const override final { return true; }
2001
2002 private:
2003   FloatKind float_kind;
2004 };
2005
2006 class USizeType : public BaseType
2007 {
2008 public:
2009   USizeType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
2010     : BaseType (ref, ref, TypeKind::USIZE,
2011                 {Resolver::CanonicalPath::create_empty (),
2012                  Linemap::predeclared_location ()},
2013                 refs)
2014   {}
2015
2016   USizeType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
2017     : BaseType (ref, ty_ref, TypeKind::USIZE,
2018                 {Resolver::CanonicalPath::create_empty (),
2019                  Linemap::predeclared_location ()},
2020                 refs)
2021   {}
2022
2023   void accept_vis (TyVisitor &vis) override;
2024   void accept_vis (TyConstVisitor &vis) const override;
2025
2026   std::string as_string () const override;
2027
2028   std::string get_name () const override final { return as_string (); }
2029
2030   BaseType *unify (BaseType *other) override;
2031   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2032
2033   BaseType *clone () const final override;
2034   BaseType *monomorphized_clone () const final override;
2035   bool is_concrete () const override final { return true; }
2036 };
2037
2038 class ISizeType : public BaseType
2039 {
2040 public:
2041   ISizeType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
2042     : BaseType (ref, ref, TypeKind::ISIZE,
2043                 {Resolver::CanonicalPath::create_empty (),
2044                  Linemap::predeclared_location ()},
2045                 refs)
2046   {}
2047
2048   ISizeType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
2049     : BaseType (ref, ty_ref, TypeKind::ISIZE,
2050                 {Resolver::CanonicalPath::create_empty (),
2051                  Linemap::predeclared_location ()},
2052                 refs)
2053   {}
2054
2055   void accept_vis (TyVisitor &vis) override;
2056   void accept_vis (TyConstVisitor &vis) const override;
2057
2058   std::string as_string () const override;
2059
2060   std::string get_name () const override final { return as_string (); }
2061
2062   BaseType *unify (BaseType *other) override;
2063   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2064
2065   BaseType *clone () const final override;
2066   BaseType *monomorphized_clone () const final override;
2067   bool is_concrete () const override final { return true; }
2068 };
2069
2070 class CharType : public BaseType
2071 {
2072 public:
2073   CharType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
2074     : BaseType (ref, ref, TypeKind::CHAR,
2075                 {Resolver::CanonicalPath::create_empty (),
2076                  Linemap::predeclared_location ()},
2077                 refs)
2078   {}
2079
2080   CharType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
2081     : BaseType (ref, ty_ref, TypeKind::CHAR,
2082                 {Resolver::CanonicalPath::create_empty (),
2083                  Linemap::predeclared_location ()},
2084                 refs)
2085   {}
2086
2087   void accept_vis (TyVisitor &vis) override;
2088   void accept_vis (TyConstVisitor &vis) const override;
2089
2090   std::string as_string () const override;
2091
2092   std::string get_name () const override final { return as_string (); }
2093
2094   BaseType *unify (BaseType *other) override;
2095   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2096
2097   BaseType *clone () const final override;
2098   BaseType *monomorphized_clone () const final override;
2099   bool is_concrete () const override final { return true; }
2100 };
2101
2102 class StrType : public BaseType
2103 {
2104 public:
2105   StrType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
2106     : BaseType (ref, ref, TypeKind::STR,
2107                 {Resolver::CanonicalPath::create_empty (),
2108                  Linemap::predeclared_location ()},
2109                 refs)
2110   {}
2111
2112   StrType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
2113     : BaseType (ref, ty_ref, TypeKind::STR,
2114                 {Resolver::CanonicalPath::create_empty (),
2115                  Linemap::predeclared_location ()},
2116                 refs)
2117   {}
2118
2119   std::string get_name () const override final { return as_string (); }
2120
2121   void accept_vis (TyVisitor &vis) override;
2122   void accept_vis (TyConstVisitor &vis) const override;
2123
2124   std::string as_string () const override;
2125
2126   BaseType *unify (BaseType *other) override;
2127   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2128
2129   bool is_equal (const BaseType &other) const override;
2130
2131   BaseType *clone () const final override;
2132   BaseType *monomorphized_clone () const final override;
2133   bool is_concrete () const override final { return true; }
2134 };
2135
2136 class ReferenceType : public BaseType
2137 {
2138 public:
2139   ReferenceType (HirId ref, TyVar base, Mutability mut,
2140                  std::set<HirId> refs = std::set<HirId> ())
2141     : BaseType (ref, ref, TypeKind::REF,
2142                 {Resolver::CanonicalPath::create_empty (),
2143                  Linemap::predeclared_location ()},
2144                 refs),
2145       base (base), mut (mut)
2146   {}
2147
2148   ReferenceType (HirId ref, HirId ty_ref, TyVar base, Mutability mut,
2149                  std::set<HirId> refs = std::set<HirId> ())
2150     : BaseType (ref, ty_ref, TypeKind::REF,
2151                 {Resolver::CanonicalPath::create_empty (),
2152                  Linemap::predeclared_location ()},
2153                 refs),
2154       base (base), mut (mut)
2155   {}
2156
2157   BaseType *get_base () const;
2158
2159   void accept_vis (TyVisitor &vis) override;
2160   void accept_vis (TyConstVisitor &vis) const override;
2161
2162   std::string as_string () const override;
2163
2164   std::string get_name () const override final
2165   {
2166     return "&" + get_base ()->get_name ();
2167   }
2168
2169   BaseType *unify (BaseType *other) override;
2170   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2171
2172   bool is_equal (const BaseType &other) const override;
2173
2174   BaseType *clone () const final override;
2175   BaseType *monomorphized_clone () const final override;
2176
2177   bool is_concrete () const override final
2178   {
2179     return get_base ()->is_concrete ();
2180   }
2181
2182   ReferenceType *handle_substitions (SubstitutionArgumentMappings mappings);
2183
2184   Mutability mutability () const { return mut; }
2185
2186   bool is_mutable () const { return mut == Mutability::Mut; }
2187
2188   bool is_dyn_object () const
2189   {
2190     return is_dyn_slice_type () || is_dyn_str_type ();
2191   }
2192
2193   bool is_dyn_slice_type (const TyTy::SliceType **slice = nullptr) const
2194   {
2195     const TyTy::BaseType *element = get_base ()->destructure ();
2196     if (element->get_kind () != TyTy::TypeKind::SLICE)
2197       return false;
2198     if (slice == nullptr)
2199       return true;
2200
2201     *slice = static_cast<const TyTy::SliceType *> (element);
2202     return true;
2203   }
2204
2205   bool is_dyn_str_type (const TyTy::StrType **str = nullptr) const
2206   {
2207     const TyTy::BaseType *element = get_base ()->destructure ();
2208     if (element->get_kind () != TyTy::TypeKind::STR)
2209       return false;
2210     if (str == nullptr)
2211       return true;
2212
2213     *str = static_cast<const TyTy::StrType *> (element);
2214     return true;
2215   }
2216
2217 private:
2218   TyVar base;
2219   Mutability mut;
2220 };
2221
2222 class PointerType : public BaseType
2223 {
2224 public:
2225   PointerType (HirId ref, TyVar base, Mutability mut,
2226                std::set<HirId> refs = std::set<HirId> ())
2227     : BaseType (ref, ref, TypeKind::POINTER,
2228                 {Resolver::CanonicalPath::create_empty (),
2229                  Linemap::predeclared_location ()},
2230                 refs),
2231       base (base), mut (mut)
2232   {}
2233
2234   PointerType (HirId ref, HirId ty_ref, TyVar base, Mutability mut,
2235                std::set<HirId> refs = std::set<HirId> ())
2236     : BaseType (ref, ty_ref, TypeKind::POINTER,
2237                 {Resolver::CanonicalPath::create_empty (),
2238                  Linemap::predeclared_location ()},
2239                 refs),
2240       base (base), mut (mut)
2241   {}
2242
2243   BaseType *get_base () const;
2244
2245   void accept_vis (TyVisitor &vis) override;
2246   void accept_vis (TyConstVisitor &vis) const override;
2247
2248   std::string as_string () const override;
2249
2250   std::string get_name () const override final
2251   {
2252     return "*" + get_base ()->get_name ();
2253   }
2254
2255   BaseType *unify (BaseType *other) override;
2256   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2257
2258   bool is_equal (const BaseType &other) const override;
2259
2260   BaseType *clone () const final override;
2261   BaseType *monomorphized_clone () const final override;
2262
2263   bool is_concrete () const override final
2264   {
2265     return get_base ()->is_concrete ();
2266   }
2267
2268   PointerType *handle_substitions (SubstitutionArgumentMappings mappings);
2269
2270   Mutability mutability () const { return mut; }
2271
2272   bool is_mutable () const { return mut == Mutability::Mut; }
2273
2274   bool is_const () const { return mut == Mutability::Imm; }
2275
2276   bool is_dyn_object () const
2277   {
2278     return is_dyn_slice_type () || is_dyn_str_type ();
2279   }
2280
2281   bool is_dyn_slice_type (const TyTy::SliceType **slice = nullptr) const
2282   {
2283     const TyTy::BaseType *element = get_base ()->destructure ();
2284     if (element->get_kind () != TyTy::TypeKind::SLICE)
2285       return false;
2286     if (slice == nullptr)
2287       return true;
2288
2289     *slice = static_cast<const TyTy::SliceType *> (element);
2290     return true;
2291   }
2292
2293   bool is_dyn_str_type (const TyTy::StrType **str = nullptr) const
2294   {
2295     const TyTy::BaseType *element = get_base ()->destructure ();
2296     if (element->get_kind () != TyTy::TypeKind::STR)
2297       return false;
2298     if (str == nullptr)
2299       return true;
2300
2301     *str = static_cast<const TyTy::StrType *> (element);
2302     return true;
2303   }
2304
2305 private:
2306   TyVar base;
2307   Mutability mut;
2308 };
2309
2310 // https://doc.rust-lang.org/std/primitive.never.html
2311 //
2312 // Since the `!` type is really complicated and it is even still unstable
2313 // in rustc, only fairly limited support for this type is introduced here.
2314 // Unification between `!` and ANY other type (including `<T?>`) is simply
2315 // not allowed. If it is needed, it should be handled manually. For example,
2316 // unifying `!` with other types is very necessary when resolving types of
2317 // `if/else` expressions.
2318 //
2319 // See related discussion at https://github.com/Rust-GCC/gccrs/pull/364
2320 class NeverType : public BaseType
2321 {
2322 public:
2323   NeverType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
2324     : BaseType (ref, ref, TypeKind::NEVER,
2325                 {Resolver::CanonicalPath::create_empty (),
2326                  Linemap::predeclared_location ()},
2327                 refs)
2328   {}
2329
2330   NeverType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
2331     : BaseType (ref, ty_ref, TypeKind::NEVER,
2332                 {Resolver::CanonicalPath::create_empty (),
2333                  Linemap::predeclared_location ()},
2334                 refs)
2335   {}
2336
2337   void accept_vis (TyVisitor &vis) override;
2338   void accept_vis (TyConstVisitor &vis) const override;
2339
2340   std::string as_string () const override;
2341
2342   BaseType *unify (BaseType *other) override;
2343   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2344
2345   BaseType *clone () const final override;
2346   BaseType *monomorphized_clone () const final override;
2347
2348   std::string get_name () const override final { return as_string (); }
2349
2350   bool is_unit () const override { return true; }
2351   bool is_concrete () const override final { return true; }
2352 };
2353
2354 // used at the type in associated types in traits
2355 // see: https://doc.rust-lang.org/book/ch19-03-advanced-traits.html
2356 class PlaceholderType : public BaseType
2357 {
2358 public:
2359   PlaceholderType (std::string symbol, HirId ref,
2360                    std::set<HirId> refs = std::set<HirId> ())
2361     : BaseType (ref, ref, TypeKind::PLACEHOLDER,
2362                 {Resolver::CanonicalPath::create_empty (),
2363                  Linemap::predeclared_location ()},
2364                 refs),
2365       symbol (symbol)
2366   {}
2367
2368   PlaceholderType (std::string symbol, HirId ref, HirId ty_ref,
2369                    std::set<HirId> refs = std::set<HirId> ())
2370     : BaseType (ref, ty_ref, TypeKind::PLACEHOLDER,
2371                 {Resolver::CanonicalPath::create_empty (),
2372                  Linemap::predeclared_location ()},
2373                 refs),
2374       symbol (symbol)
2375   {}
2376
2377   void accept_vis (TyVisitor &vis) override;
2378   void accept_vis (TyConstVisitor &vis) const override;
2379
2380   std::string as_string () const override;
2381
2382   BaseType *unify (BaseType *other) override;
2383   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2384
2385   BaseType *clone () const final override;
2386   BaseType *monomorphized_clone () const final override;
2387
2388   std::string get_name () const override final { return as_string (); }
2389
2390   bool is_unit () const override
2391   {
2392     rust_assert (can_resolve ());
2393     return resolve ()->is_unit ();
2394   }
2395
2396   std::string get_symbol () const { return symbol; }
2397
2398   void set_associated_type (HirId ref);
2399
2400   void clear_associated_type ();
2401
2402   bool can_resolve () const;
2403
2404   BaseType *resolve () const;
2405
2406   bool is_equal (const BaseType &other) const override;
2407
2408   bool is_concrete () const override final
2409   {
2410     if (!can_resolve ())
2411       return true;
2412
2413     return resolve ()->is_concrete ();
2414   }
2415
2416 private:
2417   std::string symbol;
2418 };
2419
2420 class ProjectionType : public BaseType, public SubstitutionRef
2421 {
2422 public:
2423   ProjectionType (HirId ref, BaseType *base,
2424                   const Resolver::TraitReference *trait, DefId item,
2425                   std::vector<SubstitutionParamMapping> subst_refs,
2426                   SubstitutionArgumentMappings generic_arguments
2427                   = SubstitutionArgumentMappings::error (),
2428                   std::set<HirId> refs = std::set<HirId> ())
2429     : BaseType (ref, ref, TypeKind::PROJECTION,
2430                 {Resolver::CanonicalPath::create_empty (),
2431                  Linemap::predeclared_location ()},
2432                 refs),
2433       SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
2434       base (base), trait (trait), item (item)
2435   {}
2436
2437   ProjectionType (HirId ref, HirId ty_ref, BaseType *base,
2438                   const Resolver::TraitReference *trait, DefId item,
2439                   std::vector<SubstitutionParamMapping> subst_refs,
2440                   SubstitutionArgumentMappings generic_arguments
2441                   = SubstitutionArgumentMappings::error (),
2442                   std::set<HirId> refs = std::set<HirId> ())
2443     : BaseType (ref, ty_ref, TypeKind::PROJECTION,
2444                 {Resolver::CanonicalPath::create_empty (),
2445                  Linemap::predeclared_location ()},
2446                 refs),
2447       SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
2448       base (base), trait (trait), item (item)
2449   {}
2450
2451   void accept_vis (TyVisitor &vis) override;
2452   void accept_vis (TyConstVisitor &vis) const override;
2453
2454   std::string as_string () const override;
2455
2456   BaseType *unify (BaseType *other) override;
2457   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2458
2459   BaseType *clone () const final override;
2460   BaseType *monomorphized_clone () const final override;
2461
2462   std::string get_name () const override final { return as_string (); }
2463
2464   bool is_unit () const override { return false; }
2465
2466   bool needs_generic_substitutions () const override final
2467   {
2468     return needs_substitution ();
2469   }
2470
2471   bool supports_substitutions () const override final { return true; }
2472
2473   bool has_subsititions_defined () const override final
2474   {
2475     return has_substitutions ();
2476   }
2477
2478   const BaseType *get () const { return base; }
2479   BaseType *get () { return base; }
2480
2481   bool is_concrete () const override final { return base->is_concrete (); }
2482
2483   ProjectionType *
2484   handle_substitions (SubstitutionArgumentMappings mappings) override final;
2485
2486 private:
2487   BaseType *base;
2488   const Resolver::TraitReference *trait;
2489   DefId item;
2490 };
2491
2492 class DynamicObjectType : public BaseType
2493 {
2494 public:
2495   DynamicObjectType (HirId ref, RustIdent ident,
2496                      std::vector<TypeBoundPredicate> specified_bounds,
2497                      std::set<HirId> refs = std::set<HirId> ())
2498     : BaseType (ref, ref, TypeKind::DYNAMIC, ident, specified_bounds, refs)
2499   {}
2500
2501   DynamicObjectType (HirId ref, HirId ty_ref, RustIdent ident,
2502                      std::vector<TypeBoundPredicate> specified_bounds,
2503                      std::set<HirId> refs = std::set<HirId> ())
2504     : BaseType (ref, ty_ref, TypeKind::DYNAMIC, ident, specified_bounds, refs)
2505   {}
2506
2507   void accept_vis (TyVisitor &vis) override;
2508   void accept_vis (TyConstVisitor &vis) const override;
2509
2510   std::string as_string () const override;
2511
2512   BaseType *unify (BaseType *other) override;
2513   bool can_eq (const BaseType *other, bool emit_errors) const override final;
2514
2515   bool is_equal (const BaseType &other) const override;
2516
2517   BaseType *clone () const final override;
2518   BaseType *monomorphized_clone () const final override;
2519
2520   std::string get_name () const override final;
2521
2522   bool is_concrete () const override final { return true; }
2523
2524   // this returns a flat list of items including super trait bounds
2525   const std::vector<
2526     std::pair<const Resolver::TraitItemReference *, const TypeBoundPredicate *>>
2527   get_object_items () const;
2528 };
2529
2530 } // namespace TyTy
2531 } // namespace Rust
2532
2533 #endif // RUST_TYTY