gcc/rust/typecheck/rust-tyty.cc

   1 // Copyright (C) 2020-2025 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 #include "rust-tyty.h"
  20
  21 #include "rust-tyty-visitor.h"
  22 #include "rust-hir-map.h"
  23 #include "rust-location.h"
  24 #include "rust-linemap.h"
  25
  26 #include "rust-substitution-mapper.h"
  27 #include "rust-hir-trait-reference.h"
  28 #include "rust-hir-trait-resolve.h"
  29 #include "rust-tyty-cmp.h"
  30 #include "rust-type-util.h"
  31 #include "rust-hir-type-bounds.h"
  32
  33 #include "options.h"
  34
  35 namespace Rust {
  36 namespace TyTy {
  37
  38 std::string
  39 TypeKindFormat::to_string (TypeKind kind)
  40 {
  41   switch (kind)
  42     {
  43     case TypeKind::INFER:
  44       return "Infer";
  45
  46     case TypeKind::ADT:
  47       return "ADT";
  48
  49     case TypeKind::STR:
  50       return "STR";
  51
  52     case TypeKind::REF:
  53       return "REF";
  54
  55     case TypeKind::POINTER:
  56       return "POINTER";
  57
  58     case TypeKind::PARAM:
  59       return "PARAM";
  60
  61     case TypeKind::ARRAY:
  62       return "ARRAY";
  63
  64     case TypeKind::SLICE:
  65       return "SLICE";
  66
  67     case TypeKind::FNDEF:
  68       return "FnDef";
  69
  70     case TypeKind::FNPTR:
  71       return "FnPtr";
  72
  73     case TypeKind::TUPLE:
  74       return "Tuple";
  75
  76     case TypeKind::BOOL:
  77       return "Bool";
  78
  79     case TypeKind::CHAR:
  80       return "Char";
  81
  82     case TypeKind::INT:
  83       return "Int";
  84
  85     case TypeKind::UINT:
  86       return "Uint";
  87
  88     case TypeKind::FLOAT:
  89       return "Float";
  90
  91     case TypeKind::USIZE:
  92       return "Usize";
  93
  94     case TypeKind::ISIZE:
  95       return "Isize";
  96
  97     case TypeKind::NEVER:
  98       return "Never";
  99
 100     case TypeKind::PLACEHOLDER:
 101       return "Placeholder";
 102
 103     case TypeKind::PROJECTION:
 104       return "Projection";
 105
 106     case TypeKind::DYNAMIC:
 107       return "Dynamic";
 108
 109     case TypeKind::CLOSURE:
 110       return "Closure";
 111
 112     case TypeKind::ERROR:
 113       return "ERROR";
 114     }
 115   rust_unreachable ();
 116 }
 117
 118 bool
 119 is_primitive_type_kind (TypeKind kind)
 120 {
 121   switch (kind)
 122     {
 123     case TypeKind::BOOL:
 124     case TypeKind::CHAR:
 125     case TypeKind::INT:
 126     case TypeKind::UINT:
 127     case TypeKind::ISIZE:
 128     case TypeKind::USIZE:
 129     case TypeKind::FLOAT:
 130     case TypeKind::NEVER:
 131     case TypeKind::STR:
 132       return true;
 133     default:
 134       return false;
 135     }
 136 }
 137
 138 // BASE TYPE
 139
 140 BaseType::BaseType (HirId ref, HirId ty_ref, TypeKind kind, RustIdent ident,
 141                     std::set<HirId> refs)
 142   : TypeBoundsMappings ({}), kind (kind), ref (ref), ty_ref (ty_ref),
 143     orig_ref (ref), combined (refs), ident (ident),
 144     mappings (Analysis::Mappings::get ())
 145 {}
 146
 147 BaseType::BaseType (HirId ref, HirId ty_ref, TypeKind kind, RustIdent ident,
 148                     std::vector<TypeBoundPredicate> specified_bounds,
 149                     std::set<HirId> refs)
 150   : TypeBoundsMappings (specified_bounds), kind (kind), ref (ref),
 151     ty_ref (ty_ref), orig_ref (ref), combined (refs), ident (ident),
 152     mappings (Analysis::Mappings::get ())
 153 {}
 154
 155 BaseType::~BaseType () {}
 156
 157 HirId
 158 BaseType::get_ref () const
 159 {
 160   return ref;
 161 }
 162
 163 void
 164 BaseType::set_ref (HirId id)
 165 {
 166   if (id != ref)
 167     append_reference (ref);
 168   ref = id;
 169 }
 170
 171 HirId
 172 BaseType::get_ty_ref () const
 173 {
 174   return ty_ref;
 175 }
 176
 177 void
 178 BaseType::set_ty_ref (HirId id)
 179 {
 180   ty_ref = id;
 181 }
 182 HirId
 183 BaseType::get_orig_ref () const
 184 {
 185   return orig_ref;
 186 }
 187
 188 bool
 189 BaseType::is_equal (const BaseType &other) const
 190 {
 191   return get_kind () == other.get_kind ();
 192 }
 193
 194 bool
 195 BaseType::is_unit () const
 196 {
 197   const TyTy::BaseType *x = destructure ();
 198   switch (x->get_kind ())
 199     {
 200     case PARAM:
 201     case PROJECTION:
 202     case PLACEHOLDER:
 203     case FNPTR:
 204     case FNDEF:
 205     case ARRAY:
 206     case SLICE:
 207     case POINTER:
 208     case REF:
 209     case CLOSURE:
 210     case INFER:
 211     case BOOL:
 212     case CHAR:
 213     case INT:
 214     case UINT:
 215     case FLOAT:
 216     case USIZE:
 217     case ISIZE:
 218
 219     case STR:
 220     case DYNAMIC:
 221     case ERROR:
 222       return false;
 223
 224       // FIXME ! is coerceable to () so we need to fix that
 225     case NEVER:
 226       return true;
 227
 228       case TUPLE: {
 229         return x->as<const TupleType> ()->num_fields () == 0;
 230       }
 231
 232       case ADT: {
 233         auto adt = x->as<const ADTType> ();
 234         if (adt->is_enum ())
 235           return false;
 236
 237         for (const auto &variant : adt->get_variants ())
 238           {
 239             if (variant->num_fields () > 0)
 240               return false;
 241           }
 242
 243         return true;
 244       }
 245     }
 246   return false;
 247 }
 248
 249 TypeKind
 250 BaseType::get_kind () const
 251 {
 252   return kind;
 253 }
 254
 255 std::set<HirId>
 256 BaseType::get_combined_refs () const
 257 {
 258   return combined;
 259 }
 260
 261 void
 262 BaseType::append_reference (HirId id)
 263 {
 264   combined.insert (id);
 265 }
 266
 267 const RustIdent &
 268 BaseType::get_ident () const
 269 {
 270   return ident;
 271 }
 272
 273 location_t
 274 BaseType::get_locus () const
 275 {
 276   return ident.locus;
 277 }
 278
 279 // FIXME this is missing locus
 280 bool
 281 BaseType::satisfies_bound (const TypeBoundPredicate &predicate,
 282                            bool emit_error) const
 283 {
 284   const Resolver::TraitReference *query = predicate.get ();
 285   for (const auto &bound : specified_bounds)
 286     {
 287       const Resolver::TraitReference *item = bound.get ();
 288       if (item->satisfies_bound (*query))
 289         return true;
 290     }
 291
 292   if (destructure ()->is<InferType> ())
 293     return true;
 294
 295   bool satisfied = false;
 296   auto probed = Resolver::TypeBoundsProbe::Probe (this);
 297   for (const auto &b : probed)
 298     {
 299       const Resolver::TraitReference *bound = b.first;
 300       if (bound->satisfies_bound (*query))
 301         {
 302           satisfied = true;
 303           break;
 304         }
 305     }
 306
 307   if (!satisfied)
 308     return false;
 309
 310   for (const auto &b : probed)
 311     {
 312       const Resolver::TraitReference *bound = b.first;
 313       if (!bound->is_equal (*query))
 314         continue;
 315
 316       // builtin ones have no impl-block this needs fixed and use a builtin node
 317       // of somekind
 318       if (b.second == nullptr)
 319         return true;
 320
 321       // need to check that associated types can match as well
 322       const HIR::ImplBlock &impl = *(b.second);
 323       for (const auto &item : impl.get_impl_items ())
 324         {
 325           bool is_associated_type = item->get_impl_item_type ()
 326                                     == HIR::ImplItem::ImplItemType::TYPE_ALIAS;
 327           if (!is_associated_type)
 328             continue;
 329
 330           TyTy::BaseType *impl_item_ty = nullptr;
 331           Analysis::NodeMapping i = item->get_impl_mappings ();
 332           bool query_ok = Resolver::query_type (i.get_hirid (), &impl_item_ty);
 333           if (!query_ok)
 334             return false;
 335
 336           std::string item_name = item->get_impl_item_name ();
 337           TypeBoundPredicateItem lookup
 338             = predicate.lookup_associated_item (item_name);
 339           if (lookup.is_error ())
 340             return false;
 341
 342           const auto *item_ref = lookup.get_raw_item ();
 343           TyTy::BaseType *bound_ty = item_ref->get_tyty ();
 344
 345           // compare the types
 346           if (!bound_ty->can_eq (impl_item_ty, false))
 347             {
 348               if (!impl_item_ty->can_eq (bound_ty, false))
 349                 {
 350                   if (emit_error)
 351                     {
 352                       rich_location r (line_table,
 353                                        mappings->lookup_location (get_ref ()));
 354                       r.add_range (predicate.get_locus ());
 355                       r.add_range (mappings->lookup_location (i.get_hirid ()));
 356
 357                       std::string rich_msg
 358                         = "expected " + bound_ty->destructure ()->get_name ()
 359                           + ", found "
 360                           + impl_item_ty->destructure ()->get_name ();
 361                       r.add_fixit_replace (rich_msg.c_str ());
 362
 363                       rust_error_at (
 364                         r, ErrorCode::E0271,
 365                         "type mismatch, expected %qs but got %qs",
 366                         bound_ty->destructure ()->get_name ().c_str (),
 367                         impl_item_ty->destructure ()->get_name ().c_str ());
 368                     }
 369                   return false;
 370                 }
 371             }
 372         }
 373
 374       return true;
 375     }
 376
 377   return false;
 378 }
 379
 380 bool
 381 BaseType::bounds_compatible (const BaseType &other, location_t locus,
 382                              bool emit_error) const
 383 {
 384   std::vector<std::reference_wrapper<const TypeBoundPredicate>>
 385     unsatisfied_bounds;
 386   for (auto &bound : get_specified_bounds ())
 387     {
 388       if (!other.satisfies_bound (bound, emit_error))
 389         unsatisfied_bounds.push_back (bound);
 390     }
 391
 392   // lets emit a single error for this
 393   if (unsatisfied_bounds.size () > 0)
 394     {
 395       rich_location r (line_table, locus);
 396       std::string missing_preds;
 397       for (size_t i = 0; i < unsatisfied_bounds.size (); i++)
 398         {
 399           const TypeBoundPredicate &pred = unsatisfied_bounds.at (i);
 400           r.add_range (pred.get_locus ());
 401           missing_preds += pred.get_name ();
 402
 403           bool have_next = (i + 1) < unsatisfied_bounds.size ();
 404           if (have_next)
 405             missing_preds += ", ";
 406         }
 407
 408       if (emit_error)
 409         {
 410           rust_error_at (r, ErrorCode::E0277,
 411                          "bounds not satisfied for %s %qs is not satisfied",
 412                          other.get_name ().c_str (), missing_preds.c_str ());
 413           // rust_assert (!emit_error);
 414         }
 415     }
 416
 417   return unsatisfied_bounds.size () == 0;
 418 }
 419
 420 void
 421 BaseType::inherit_bounds (const BaseType &other)
 422 {
 423   inherit_bounds (other.get_specified_bounds ());
 424 }
 425
 426 void
 427 BaseType::inherit_bounds (
 428   const std::vector<TyTy::TypeBoundPredicate> &specified_bounds)
 429 {
 430   for (auto &bound : specified_bounds)
 431     {
 432       add_bound (bound);
 433     }
 434 }
 435
 436 const BaseType *
 437 BaseType::get_root () const
 438 {
 439   // FIXME this needs to be it its own visitor class with a vector adjustments
 440   const TyTy::BaseType *root = this;
 441
 442   if (const auto r = root->try_as<const ReferenceType> ())
 443     {
 444       root = r->get_base ()->get_root ();
 445     }
 446   else if (const auto r = root->try_as<const PointerType> ())
 447     {
 448       root = r->get_base ()->get_root ();
 449     }
 450   // these are an unsize
 451   else if (const auto r = root->try_as<const SliceType> ())
 452     {
 453       root = r->get_element_type ()->get_root ();
 454     }
 455   //  else if (const auto r = root->try_as<const ArrayType> ())
 456   //    {
 457   //      root = r->get_element_type ()->get_root ();
 458   //    }
 459
 460   return root;
 461 }
 462
 463 BaseType *
 464 BaseType::destructure ()
 465 {
 466   int recurisve_ops = 0;
 467   BaseType *x = this;
 468   while (true)
 469     {
 470       if (recurisve_ops++ >= rust_max_recursion_depth)
 471         {
 472           rust_error_at (
 473             UNDEF_LOCATION,
 474             "%<recursion depth%> count exceeds limit of %i (use "
 475             "%<frust-max-recursion-depth=%> to increase the limit)",
 476             rust_max_recursion_depth);
 477           return new ErrorType (get_ref ());
 478         }
 479
 480       if (auto p = x->try_as<ParamType> ())
 481         {
 482           auto pr = p->resolve ();
 483           if (pr == x)
 484             return pr;
 485
 486           x = pr;
 487         }
 488       else if (auto p = x->try_as<PlaceholderType> ())
 489         {
 490           if (!p->can_resolve ())
 491             return p;
 492
 493           x = p->resolve ();
 494         }
 495       else if (auto p = x->try_as<ProjectionType> ())
 496         {
 497           x = p->get ();
 498         }
 499       else
 500         {
 501           return x;
 502         }
 503     }
 504
 505   return x;
 506 }
 507
 508 const BaseType *
 509 BaseType::destructure () const
 510 {
 511   int recurisve_ops = 0;
 512   const BaseType *x = this;
 513   while (true)
 514     {
 515       if (recurisve_ops++ >= rust_max_recursion_depth)
 516         {
 517           rust_error_at (
 518             UNDEF_LOCATION,
 519             "%<recursion depth%> count exceeds limit of %i (use "
 520             "%<frust-max-recursion-depth=%> to increase the limit)",
 521             rust_max_recursion_depth);
 522           return new ErrorType (get_ref ());
 523         }
 524
 525       if (auto p = x->try_as<const ParamType> ())
 526         {
 527           auto pr = p->resolve ();
 528           if (pr == x)
 529             return pr;
 530
 531           x = pr;
 532         }
 533       else if (auto p = x->try_as<const PlaceholderType> ())
 534         {
 535           if (!p->can_resolve ())
 536             return p;
 537
 538           x = p->resolve ();
 539         }
 540       else if (auto p = x->try_as<const ProjectionType> ())
 541         {
 542           x = p->get ();
 543         }
 544       else
 545         {
 546           return x;
 547         }
 548     }
 549
 550   return x;
 551 }
 552
 553 BaseType *
 554 BaseType::monomorphized_clone () const
 555 {
 556   const TyTy::BaseType *x = destructure ();
 557
 558   if (auto arr = x->try_as<const ArrayType> ())
 559     {
 560       TyVar elm = arr->get_var_element_type ().monomorphized_clone ();
 561       return new ArrayType (arr->get_ref (), arr->get_ty_ref (), ident.locus,
 562                             arr->get_capacity_expr (), elm,
 563                             arr->get_combined_refs ());
 564     }
 565   else if (auto slice = x->try_as<const SliceType> ())
 566     {
 567       TyVar elm = slice->get_var_element_type ().monomorphized_clone ();
 568       return new SliceType (slice->get_ref (), slice->get_ty_ref (),
 569                             ident.locus, elm, slice->get_combined_refs ());
 570     }
 571   else if (auto ptr = x->try_as<const PointerType> ())
 572     {
 573       TyVar elm = ptr->get_var_element_type ().monomorphized_clone ();
 574       return new PointerType (ptr->get_ref (), ptr->get_ty_ref (), elm,
 575                               ptr->mutability (), ptr->get_combined_refs ());
 576     }
 577   else if (auto ref = x->try_as<const ReferenceType> ())
 578     {
 579       TyVar elm = ref->get_var_element_type ().monomorphized_clone ();
 580       return new ReferenceType (ref->get_ref (), ref->get_ty_ref (), elm,
 581                                 ref->mutability (), ref->get_region (),
 582                                 ref->get_combined_refs ());
 583     }
 584   else if (auto tuple = x->try_as<const TupleType> ())
 585     {
 586       std::vector<TyVar> cloned_fields;
 587       for (const auto &f : tuple->get_fields ())
 588         cloned_fields.push_back (f.monomorphized_clone ());
 589
 590       return new TupleType (tuple->get_ref (), tuple->get_ty_ref (),
 591                             ident.locus, cloned_fields,
 592                             tuple->get_combined_refs ());
 593     }
 594   else if (auto fn = x->try_as<const FnType> ())
 595     {
 596       std::vector<std::pair<HIR::Pattern *, BaseType *>> cloned_params;
 597       for (auto &p : fn->get_params ())
 598         cloned_params.push_back ({p.first, p.second->monomorphized_clone ()});
 599
 600       BaseType *retty = fn->get_return_type ()->monomorphized_clone ();
 601       return new FnType (fn->get_ref (), fn->get_ty_ref (), fn->get_id (),
 602                          fn->get_identifier (), fn->ident, fn->get_flags (),
 603                          fn->get_abi (), std::move (cloned_params), retty,
 604                          fn->clone_substs (), fn->get_substitution_arguments (),
 605                          fn->get_region_constraints (),
 606                          fn->get_combined_refs ());
 607     }
 608   else if (auto fn = x->try_as<const FnPtr> ())
 609     {
 610       std::vector<TyVar> cloned_params;
 611       for (auto &p : fn->get_params ())
 612         cloned_params.push_back (p.monomorphized_clone ());
 613
 614       TyVar retty = fn->get_var_return_type ().monomorphized_clone ();
 615       return new FnPtr (fn->get_ref (), fn->get_ty_ref (), ident.locus,
 616                         std::move (cloned_params), retty,
 617                         fn->get_combined_refs ());
 618     }
 619   else if (auto adt = x->try_as<const ADTType> ())
 620     {
 621       std::vector<VariantDef *> cloned_variants;
 622       for (auto &variant : adt->get_variants ())
 623         cloned_variants.push_back (variant->monomorphized_clone ());
 624
 625       return new ADTType (adt->get_ref (), adt->get_ty_ref (),
 626                           adt->get_identifier (), adt->ident,
 627                           adt->get_adt_kind (), cloned_variants,
 628                           adt->clone_substs (), adt->get_repr_options (),
 629                           adt->get_used_arguments (),
 630                           adt->get_region_constraints (),
 631                           adt->get_combined_refs ());
 632     }
 633   else
 634     {
 635       return x->clone ();
 636     }
 637
 638   rust_unreachable ();
 639   return nullptr;
 640 }
 641
 642 std::string
 643 BaseType::mappings_str () const
 644 {
 645   std::string buffer = "Ref: " + std::to_string (get_ref ())
 646                        + " TyRef: " + std::to_string (get_ty_ref ());
 647   buffer += "[";
 648   for (auto &ref : combined)
 649     buffer += std::to_string (ref) + ",";
 650   buffer += "]";
 651   return "(" + buffer + ")";
 652 }
 653
 654 std::string
 655 BaseType::debug_str () const
 656 {
 657   // return TypeKindFormat::to_string (get_kind ()) + ":" + as_string () + ":"
 658   //        + mappings_str () + ":" + bounds_as_string ();
 659   return get_name ();
 660 }
 661
 662 void
 663 BaseType::debug () const
 664 {
 665   rust_debug ("[%p] %s", static_cast<const void *> (this),
 666               debug_str ().c_str ());
 667 }
 668
 669 bool
 670 BaseType::is_concrete () const
 671 {
 672   const TyTy::BaseType *x = destructure ();
 673
 674   if (x->is<ParamType> () || x->is<ProjectionType> ())
 675     {
 676       return false;
 677     }
 678   // placeholder is a special case for this case when it is not resolvable
 679   // it means we its just an empty placeholder associated type which is
 680   // concrete
 681   else if (x->is<PlaceholderType> ())
 682     {
 683       return true;
 684     }
 685   else if (auto fn = x->try_as<const FnType> ())
 686     {
 687       for (const auto &param : fn->get_params ())
 688         {
 689           if (!param.second->is_concrete ())
 690             return false;
 691         }
 692       return fn->get_return_type ()->is_concrete ();
 693     }
 694   else if (auto fn = x->try_as<const FnPtr> ())
 695     {
 696       for (const auto &param : fn->get_params ())
 697         {
 698           if (!param.get_tyty ()->is_concrete ())
 699             return false;
 700         }
 701       return fn->get_return_type ()->is_concrete ();
 702     }
 703   else if (auto adt = x->try_as<const ADTType> ())
 704     {
 705       if (adt->is_unit ())
 706         return !adt->needs_substitution ();
 707
 708       for (auto &variant : adt->get_variants ())
 709         {
 710           bool is_num_variant
 711             = variant->get_variant_type () == VariantDef::VariantType::NUM;
 712           if (is_num_variant)
 713             continue;
 714
 715           for (auto &field : variant->get_fields ())
 716             {
 717               const BaseType *field_type = field->get_field_type ();
 718               if (!field_type->is_concrete ())
 719                 return false;
 720             }
 721         }
 722       return true;
 723     }
 724   else if (auto arr = x->try_as<const ArrayType> ())
 725     {
 726       return arr->get_element_type ()->is_concrete ();
 727     }
 728   else if (auto slice = x->try_as<const SliceType> ())
 729     {
 730       return slice->get_element_type ()->is_concrete ();
 731     }
 732   else if (auto ptr = x->try_as<const PointerType> ())
 733     {
 734       return ptr->get_base ()->is_concrete ();
 735     }
 736   else if (auto ref = x->try_as<const ReferenceType> ())
 737     {
 738       return ref->get_base ()->is_concrete ();
 739     }
 740   else if (auto tuple = x->try_as<const TupleType> ())
 741     {
 742       for (size_t i = 0; i < tuple->num_fields (); i++)
 743         {
 744           if (!tuple->get_field (i)->is_concrete ())
 745             return false;
 746         }
 747       return true;
 748     }
 749   else if (auto closure = x->try_as<const ClosureType> ())
 750     {
 751       if (closure->get_parameters ().is_concrete ())
 752         return false;
 753       return closure->get_result_type ().is_concrete ();
 754     }
 755   else if (x->is<InferType> () || x->is<BoolType> () || x->is<CharType> ()
 756            || x->is<IntType> () || x->is<UintType> () || x->is<FloatType> ()
 757            || x->is<USizeType> () || x->is<ISizeType> () || x->is<NeverType> ()
 758            || x->is<StrType> () || x->is<DynamicObjectType> ()
 759            || x->is<ErrorType> ())
 760     {
 761       return true;
 762     }
 763
 764   return false;
 765 }
 766
 767 bool
 768 BaseType::has_substitutions_defined () const
 769 {
 770   const TyTy::BaseType *x = destructure ();
 771   switch (x->get_kind ())
 772     {
 773     case INFER:
 774     case BOOL:
 775     case CHAR:
 776     case INT:
 777     case UINT:
 778     case FLOAT:
 779     case USIZE:
 780     case ISIZE:
 781     case NEVER:
 782     case STR:
 783     case DYNAMIC:
 784     case ERROR:
 785     case FNPTR:
 786     case ARRAY:
 787     case SLICE:
 788     case POINTER:
 789     case REF:
 790     case TUPLE:
 791     case PARAM:
 792     case PLACEHOLDER:
 793       return false;
 794
 795       case PROJECTION: {
 796         const ProjectionType &p = *static_cast<const ProjectionType *> (x);
 797         const SubstitutionRef &ref = static_cast<const SubstitutionRef &> (p);
 798         return ref.has_substitutions ();
 799       }
 800       break;
 801
 802       case FNDEF: {
 803         const FnType &fn = *static_cast<const FnType *> (x);
 804         const SubstitutionRef &ref = static_cast<const SubstitutionRef &> (fn);
 805         return ref.has_substitutions ();
 806       }
 807       break;
 808
 809       case ADT: {
 810         const ADTType &adt = *static_cast<const ADTType *> (x);
 811         const SubstitutionRef &ref = static_cast<const SubstitutionRef &> (adt);
 812         return ref.has_substitutions ();
 813       }
 814       break;
 815
 816       case CLOSURE: {
 817         const ClosureType &closure = *static_cast<const ClosureType *> (x);
 818         const SubstitutionRef &ref
 819           = static_cast<const SubstitutionRef &> (closure);
 820         return ref.has_substitutions ();
 821       }
 822       break;
 823     }
 824
 825   return false;
 826 }
 827
 828 bool
 829 BaseType::needs_generic_substitutions () const
 830 {
 831   const TyTy::BaseType *x = destructure ();
 832   switch (x->get_kind ())
 833     {
 834     case INFER:
 835     case BOOL:
 836     case CHAR:
 837     case INT:
 838     case UINT:
 839     case FLOAT:
 840     case USIZE:
 841     case ISIZE:
 842     case NEVER:
 843     case STR:
 844     case DYNAMIC:
 845     case ERROR:
 846     case FNPTR:
 847     case ARRAY:
 848     case SLICE:
 849     case POINTER:
 850     case REF:
 851     case TUPLE:
 852     case PARAM:
 853     case PLACEHOLDER:
 854       return false;
 855
 856       case PROJECTION: {
 857         const ProjectionType &p = *static_cast<const ProjectionType *> (x);
 858         const SubstitutionRef &ref = static_cast<const SubstitutionRef &> (p);
 859         return ref.needs_substitution ();
 860       }
 861       break;
 862
 863       case FNDEF: {
 864         const FnType &fn = *static_cast<const FnType *> (x);
 865         const SubstitutionRef &ref = static_cast<const SubstitutionRef &> (fn);
 866         return ref.needs_substitution ();
 867       }
 868       break;
 869
 870       case ADT: {
 871         const ADTType &adt = *static_cast<const ADTType *> (x);
 872         const SubstitutionRef &ref = static_cast<const SubstitutionRef &> (adt);
 873         return ref.needs_substitution ();
 874       }
 875       break;
 876
 877       case CLOSURE: {
 878         const ClosureType &closure = *static_cast<const ClosureType *> (x);
 879         const SubstitutionRef &ref
 880           = static_cast<const SubstitutionRef &> (closure);
 881         return ref.needs_substitution ();
 882       }
 883       break;
 884     }
 885
 886   return false;
 887 }
 888
 889 // InferType
 890
 891 InferType::InferType (HirId ref, InferTypeKind infer_kind, TypeHint hint,
 892                       location_t locus, std::set<HirId> refs)
 893   : BaseType (ref, ref, KIND, {Resolver::CanonicalPath::create_empty (), locus},
 894               refs),
 895     infer_kind (infer_kind), default_hint (hint)
 896 {}
 897
 898 InferType::InferType (HirId ref, HirId ty_ref, InferTypeKind infer_kind,
 899                       TypeHint hint, location_t locus, std::set<HirId> refs)
 900   : BaseType (ref, ty_ref, KIND,
 901               {Resolver::CanonicalPath::create_empty (), locus}, refs),
 902     infer_kind (infer_kind), default_hint (hint)
 903 {}
 904
 905 InferType::InferTypeKind
 906 InferType::get_infer_kind () const
 907 {
 908   return infer_kind;
 909 }
 910
 911 std::string
 912 InferType::get_name () const
 913 {
 914   return as_string ();
 915 }
 916
 917 void
 918 InferType::accept_vis (TyVisitor &vis)
 919 {
 920   vis.visit (*this);
 921 }
 922
 923 void
 924 InferType::accept_vis (TyConstVisitor &vis) const
 925 {
 926   vis.visit (*this);
 927 }
 928
 929 std::string
 930 InferType::as_string () const
 931 {
 932   switch (infer_kind)
 933     {
 934     case GENERAL:
 935       return "T?";
 936     case INTEGRAL:
 937       return "<integer>";
 938     case FLOAT:
 939       return "<float>";
 940     }
 941   return "<infer::error>";
 942 }
 943
 944 bool
 945 InferType::can_eq (const BaseType *other, bool emit_errors) const
 946 {
 947   InferCmp r (this, emit_errors);
 948   return r.can_eq (other);
 949 }
 950
 951 BaseType *
 952 InferType::clone () const
 953 {
 954   // clones for inference variables are special in that they _must_ exist within
 955   // the type check context and we must ensure we don't loose the chain
 956   // otherwise we will end up in the missing type annotations case
 957   //
 958   // This means we cannot simply take over the same reference we must generate a
 959   // new ref just like the get_implicit_infer_var code then we can setup the
 960   // chain of references accordingly to ensure we don't loose the ability to
 961   // update the inference variables when we solve the type
 962
 963   auto mappings = Analysis::Mappings::get ();
 964   auto context = Resolver::TypeCheckContext::get ();
 965
 966   InferType *clone
 967     = new InferType (mappings->get_next_hir_id (), get_infer_kind (),
 968                      default_hint, get_ident ().locus, get_combined_refs ());
 969
 970   context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
 971                                                UNKNOWN_NODEID,
 972                                                clone->get_ref (),
 973                                                UNKNOWN_LOCAL_DEFID),
 974                         clone);
 975   mappings->insert_location (clone->get_ref (),
 976                              mappings->lookup_location (get_ref ()));
 977
 978   // setup the chain to reference this
 979   clone->append_reference (get_ref ());
 980
 981   return clone;
 982 }
 983
 984 bool
 985 InferType::default_type (BaseType **type) const
 986 {
 987   auto context = Resolver::TypeCheckContext::get ();
 988   bool ok = false;
 989
 990   // NOTE: Calling this error is misleading.
 991   if (default_hint.kind == TypeKind::ERROR)
 992     {
 993       switch (infer_kind)
 994         {
 995         case GENERAL:
 996           return false;
 997
 998           case INTEGRAL: {
 999             ok = context->lookup_builtin ("i32", type);
1000             rust_assert (ok);
1001             return ok;
1002           }
1003
1004           case FLOAT: {
1005             ok = context->lookup_builtin ("f64", type);
1006             rust_assert (ok);
1007             return ok;
1008           }
1009         }
1010       return false;
1011     }
1012
1013   switch (default_hint.kind)
1014     {
1015     case ISIZE:
1016       ok = context->lookup_builtin ("isize", type);
1017       rust_assert (ok);
1018       return ok;
1019
1020     case USIZE:
1021       ok = context->lookup_builtin ("usize", type);
1022       rust_assert (ok);
1023       return ok;
1024
1025     case INT:
1026       switch (default_hint.szhint)
1027         {
1028         case TypeHint::SizeHint::S8:
1029           ok = context->lookup_builtin ("i8", type);
1030           rust_assert (ok);
1031           return ok;
1032
1033         case TypeHint::SizeHint::S16:
1034           ok = context->lookup_builtin ("i16", type);
1035           rust_assert (ok);
1036           return ok;
1037
1038         case TypeHint::SizeHint::S32:
1039           ok = context->lookup_builtin ("i32", type);
1040           rust_assert (ok);
1041           return ok;
1042
1043         case TypeHint::SizeHint::S64:
1044           ok = context->lookup_builtin ("i64", type);
1045           rust_assert (ok);
1046           return ok;
1047
1048         case TypeHint::SizeHint::S128:
1049           ok = context->lookup_builtin ("i128", type);
1050           rust_assert (ok);
1051           return ok;
1052
1053         default:
1054           return false;
1055         }
1056       break;
1057
1058     case UINT:
1059       switch (default_hint.szhint)
1060         {
1061         case TypeHint::SizeHint::S8:
1062           ok = context->lookup_builtin ("u8", type);
1063           rust_assert (ok);
1064           return ok;
1065
1066         case TypeHint::SizeHint::S16:
1067           ok = context->lookup_builtin ("u16", type);
1068           rust_assert (ok);
1069           return ok;
1070
1071         case TypeHint::SizeHint::S32:
1072           ok = context->lookup_builtin ("u32", type);
1073           rust_assert (ok);
1074           return ok;
1075
1076         case TypeHint::SizeHint::S64:
1077           ok = context->lookup_builtin ("u64", type);
1078           rust_assert (ok);
1079           return ok;
1080
1081         case TypeHint::SizeHint::S128:
1082           ok = context->lookup_builtin ("u128", type);
1083           rust_assert (ok);
1084           return ok;
1085
1086         default:
1087           return false;
1088         }
1089       break;
1090
1091     case TypeKind::FLOAT:
1092       switch (default_hint.szhint)
1093         {
1094         case TypeHint::SizeHint::S32:
1095           ok = context->lookup_builtin ("f32", type);
1096           rust_assert (ok);
1097           return ok;
1098
1099         case TypeHint::SizeHint::S64:
1100           ok = context->lookup_builtin ("f64", type);
1101           rust_assert (ok);
1102           return ok;
1103
1104         default:
1105           return false;
1106         }
1107       break;
1108
1109     default:
1110       return false;
1111     }
1112
1113   return false;
1114 }
1115
1116 void
1117 InferType::apply_primitive_type_hint (const BaseType &hint)
1118 {
1119   switch (hint.get_kind ())
1120     {
1121     case ISIZE:
1122     case USIZE:
1123       infer_kind = INTEGRAL;
1124       default_hint.kind = hint.get_kind ();
1125       break;
1126
1127       case INT: {
1128         infer_kind = INTEGRAL;
1129         default_hint.kind = hint.get_kind ();
1130         default_hint.shint = TypeHint::SignedHint::SIGNED;
1131         switch (hint.as<const IntType> ()->get_int_kind ())
1132           {
1133           case IntType::I8:
1134             default_hint.szhint = TypeHint::SizeHint::S8;
1135             break;
1136           case IntType::I16:
1137             default_hint.szhint = TypeHint::SizeHint::S16;
1138             break;
1139           case IntType::I32:
1140             default_hint.szhint = TypeHint::SizeHint::S32;
1141             break;
1142           case IntType::I64:
1143             default_hint.szhint = TypeHint::SizeHint::S64;
1144             break;
1145           case IntType::I128:
1146             default_hint.szhint = TypeHint::SizeHint::S128;
1147             break;
1148           }
1149       }
1150       break;
1151
1152       case UINT: {
1153         infer_kind = INTEGRAL;
1154         default_hint.kind = hint.get_kind ();
1155         default_hint.shint = TypeHint::SignedHint::UNSIGNED;
1156         switch (hint.as<const UintType> ()->get_uint_kind ())
1157           {
1158           case UintType::U8:
1159             default_hint.szhint = TypeHint::SizeHint::S8;
1160             break;
1161           case UintType::U16:
1162             default_hint.szhint = TypeHint::SizeHint::S16;
1163             break;
1164           case UintType::U32:
1165             default_hint.szhint = TypeHint::SizeHint::S32;
1166             break;
1167           case UintType::U64:
1168             default_hint.szhint = TypeHint::SizeHint::S64;
1169             break;
1170           case UintType::U128:
1171             default_hint.szhint = TypeHint::SizeHint::S128;
1172             break;
1173           }
1174       }
1175       break;
1176
1177       case TypeKind::FLOAT: {
1178         infer_kind = FLOAT;
1179         default_hint.shint = TypeHint::SignedHint::SIGNED;
1180         default_hint.kind = hint.get_kind ();
1181         switch (hint.as<const FloatType> ()->get_float_kind ())
1182           {
1183           case FloatType::F32:
1184             default_hint.szhint = TypeHint::SizeHint::S32;
1185             break;
1186
1187           case FloatType::F64:
1188             default_hint.szhint = TypeHint::SizeHint::S64;
1189             break;
1190           }
1191       }
1192       break;
1193
1194     default:
1195       // TODO bool, char, never??
1196       break;
1197     }
1198 }
1199
1200 // ErrorType
1201
1202 ErrorType::ErrorType (HirId ref, std::set<HirId> refs)
1203   : BaseType (ref, ref, KIND,
1204               {Resolver::CanonicalPath::create_empty (), UNDEF_LOCATION}, refs)
1205 {}
1206
1207 ErrorType::ErrorType (HirId ref, HirId ty_ref, std::set<HirId> refs)
1208   : BaseType (ref, ty_ref, KIND,
1209               {Resolver::CanonicalPath::create_empty (), UNDEF_LOCATION}, refs)
1210 {}
1211
1212 std::string
1213 ErrorType::get_name () const
1214 {
1215   return as_string ();
1216 }
1217
1218 void
1219 ErrorType::accept_vis (TyVisitor &vis)
1220 {
1221   vis.visit (*this);
1222 }
1223
1224 void
1225 ErrorType::accept_vis (TyConstVisitor &vis) const
1226 {
1227   vis.visit (*this);
1228 }
1229
1230 std::string
1231 ErrorType::as_string () const
1232 {
1233   return "<tyty::error>";
1234 }
1235
1236 bool
1237 ErrorType::can_eq (const BaseType *other, bool emit_errors) const
1238 {
1239   return get_kind () == other->get_kind ();
1240 }
1241
1242 BaseType *
1243 ErrorType::clone () const
1244 {
1245   return new ErrorType (get_ref (), get_ty_ref (), get_combined_refs ());
1246 }
1247
1248 // Struct Field type
1249
1250 StructFieldType::StructFieldType (HirId ref, std::string name, BaseType *ty,
1251                                   location_t locus)
1252   : ref (ref), name (name), ty (ty), locus (locus)
1253 {}
1254
1255 HirId
1256 StructFieldType::get_ref () const
1257 {
1258   return ref;
1259 }
1260
1261 std::string
1262 StructFieldType::get_name () const
1263 {
1264   return name;
1265 }
1266
1267 BaseType *
1268 StructFieldType::get_field_type () const
1269 {
1270   return ty;
1271 }
1272
1273 void
1274 StructFieldType::set_field_type (BaseType *fty)
1275 {
1276   ty = fty;
1277 }
1278
1279 void
1280 StructFieldType::debug () const
1281 {
1282   rust_debug ("%s", as_string ().c_str ());
1283 }
1284
1285 location_t
1286 StructFieldType::get_locus () const
1287 {
1288   return locus;
1289 }
1290
1291 std::string
1292 StructFieldType::as_string () const
1293 {
1294   return name + ":" + get_field_type ()->debug_str ();
1295 }
1296
1297 bool
1298 StructFieldType::is_equal (const StructFieldType &other) const
1299 {
1300   bool names_eq = get_name () == other.get_name ();
1301
1302   TyTy::BaseType *o = other.get_field_type ();
1303   if (auto op = o->try_as<ParamType> ())
1304     o = op->resolve ();
1305
1306   bool types_eq = get_field_type ()->is_equal (*o);
1307
1308   return names_eq && types_eq;
1309 }
1310
1311 StructFieldType *
1312 StructFieldType::clone () const
1313 {
1314   return new StructFieldType (get_ref (), get_name (),
1315                               get_field_type ()->clone (), locus);
1316 }
1317
1318 StructFieldType *
1319 StructFieldType::monomorphized_clone () const
1320 {
1321   return new StructFieldType (get_ref (), get_name (),
1322                               get_field_type ()->monomorphized_clone (), locus);
1323 }
1324
1325 // VariantDef
1326
1327 std::string
1328 VariantDef::variant_type_string (VariantType type)
1329 {
1330   switch (type)
1331     {
1332     case NUM:
1333       return "enumeral";
1334     case TUPLE:
1335       return "tuple";
1336     case STRUCT:
1337       return "struct";
1338     }
1339   rust_unreachable ();
1340   return "";
1341 }
1342
1343 VariantDef::VariantDef (HirId id, DefId defid, std::string identifier,
1344                         RustIdent ident, HIR::Expr *discriminant)
1345   : id (id), defid (defid), identifier (identifier), ident (ident),
1346     discriminant (discriminant)
1347
1348 {
1349   type = VariantType::NUM;
1350   fields = {};
1351 }
1352
1353 VariantDef::VariantDef (HirId id, DefId defid, std::string identifier,
1354                         RustIdent ident, VariantType type,
1355                         HIR::Expr *discriminant,
1356                         std::vector<StructFieldType *> fields)
1357   : id (id), defid (defid), identifier (identifier), ident (ident), type (type),
1358     discriminant (discriminant), fields (fields)
1359 {
1360   rust_assert ((type == VariantType::NUM && fields.empty ())
1361                || (type == VariantType::TUPLE || type == VariantType::STRUCT));
1362 }
1363
1364 VariantDef::VariantDef (const VariantDef &other)
1365   : id (other.id), defid (other.defid), identifier (other.identifier),
1366     ident (other.ident), type (other.type), discriminant (other.discriminant),
1367     fields (other.fields)
1368 {}
1369
1370 VariantDef &
1371 VariantDef::operator= (const VariantDef &other)
1372 {
1373   id = other.id;
1374   identifier = other.identifier;
1375   type = other.type;
1376   discriminant = other.discriminant;
1377   fields = other.fields;
1378   ident = other.ident;
1379
1380   return *this;
1381 }
1382
1383 VariantDef &
1384 VariantDef::get_error_node ()
1385 {
1386   static VariantDef node
1387     = VariantDef (UNKNOWN_HIRID, UNKNOWN_DEFID, "",
1388                   {Resolver::CanonicalPath::create_empty (), UNKNOWN_LOCATION},
1389                   nullptr);
1390
1391   return node;
1392 }
1393
1394 bool
1395 VariantDef::is_error () const
1396 {
1397   return get_id () == UNKNOWN_HIRID;
1398 }
1399
1400 HirId
1401 VariantDef::get_id () const
1402 {
1403   return id;
1404 }
1405
1406 DefId
1407 VariantDef::get_defid () const
1408 {
1409   return defid;
1410 }
1411
1412 VariantDef::VariantType
1413 VariantDef::get_variant_type () const
1414 {
1415   return type;
1416 }
1417
1418 bool
1419 VariantDef::is_data_variant () const
1420 {
1421   return type != VariantType::NUM;
1422 }
1423
1424 bool
1425 VariantDef::is_dataless_variant () const
1426 {
1427   return type == VariantType::NUM;
1428 }
1429
1430 std::string
1431 VariantDef::get_identifier () const
1432 {
1433   return identifier;
1434 }
1435
1436 size_t
1437 VariantDef::num_fields () const
1438 {
1439   return fields.size ();
1440 }
1441
1442 StructFieldType *
1443 VariantDef::get_field_at_index (size_t index)
1444 {
1445   rust_assert (index < fields.size ());
1446   return fields.at (index);
1447 }
1448
1449 std::vector<StructFieldType *> &
1450 VariantDef::get_fields ()
1451 {
1452   rust_assert (type != NUM);
1453   return fields;
1454 }
1455
1456 bool
1457 VariantDef::lookup_field (const std::string &lookup,
1458                           StructFieldType **field_lookup, size_t *index) const
1459 {
1460   size_t i = 0;
1461   for (auto &field : fields)
1462     {
1463       if (field->get_name ().compare (lookup) == 0)
1464         {
1465           if (index != nullptr)
1466             *index = i;
1467
1468           if (field_lookup != nullptr)
1469             *field_lookup = field;
1470
1471           return true;
1472         }
1473       i++;
1474     }
1475   return false;
1476 }
1477
1478 HIR::Expr *
1479 VariantDef::get_discriminant () const
1480 {
1481   rust_assert (discriminant != nullptr);
1482   return discriminant;
1483 }
1484
1485 std::string
1486 VariantDef::as_string () const
1487 {
1488   if (type == VariantType::NUM)
1489     return identifier + " = " + discriminant->as_string ();
1490
1491   std::string buffer;
1492   for (size_t i = 0; i < fields.size (); ++i)
1493     {
1494       buffer += fields.at (i)->as_string ();
1495       if ((i + 1) < fields.size ())
1496         buffer += ", ";
1497     }
1498
1499   if (type == VariantType::TUPLE)
1500     return identifier + " (" + buffer + ")";
1501   else
1502     return identifier + " {" + buffer + "}";
1503 }
1504
1505 bool
1506 VariantDef::is_equal (const VariantDef &other) const
1507 {
1508   if (type != other.type)
1509     return false;
1510
1511   if (identifier.compare (other.identifier) != 0)
1512     return false;
1513
1514   if (discriminant != other.discriminant)
1515     return false;
1516
1517   if (fields.size () != other.fields.size ())
1518     return false;
1519
1520   for (size_t i = 0; i < fields.size (); i++)
1521     {
1522       if (!fields.at (i)->is_equal (*other.fields.at (i)))
1523         return false;
1524     }
1525
1526   return true;
1527 }
1528
1529 VariantDef *
1530 VariantDef::clone () const
1531 {
1532   std::vector<StructFieldType *> cloned_fields;
1533   for (auto &f : fields)
1534     cloned_fields.push_back ((StructFieldType *) f->clone ());
1535
1536   return new VariantDef (id, defid, identifier, ident, type, discriminant,
1537                          cloned_fields);
1538 }
1539
1540 VariantDef *
1541 VariantDef::monomorphized_clone () const
1542 {
1543   std::vector<StructFieldType *> cloned_fields;
1544   for (auto &f : fields)
1545     cloned_fields.push_back ((StructFieldType *) f->monomorphized_clone ());
1546
1547   return new VariantDef (id, defid, identifier, ident, type, discriminant,
1548                          cloned_fields);
1549 }
1550
1551 const RustIdent &
1552 VariantDef::get_ident () const
1553 {
1554   return ident;
1555 }
1556
1557 // ADTType
1558
1559 void
1560 ADTType::accept_vis (TyVisitor &vis)
1561 {
1562   vis.visit (*this);
1563 }
1564
1565 void
1566 ADTType::accept_vis (TyConstVisitor &vis) const
1567 {
1568   vis.visit (*this);
1569 }
1570
1571 std::string
1572 ADTType::as_string () const
1573 {
1574   std::string variants_buffer;
1575   for (size_t i = 0; i < number_of_variants (); ++i)
1576     {
1577       TyTy::VariantDef *variant = variants.at (i);
1578       variants_buffer += variant->as_string ();
1579       if ((i + 1) < number_of_variants ())
1580         variants_buffer += ", ";
1581     }
1582
1583   return identifier + subst_as_string () + "{" + variants_buffer + "}";
1584 }
1585
1586 bool
1587 ADTType::can_eq (const BaseType *other, bool emit_errors) const
1588 {
1589   ADTCmp r (this, emit_errors);
1590   return r.can_eq (other);
1591 }
1592
1593 bool
1594 ADTType::is_equal (const BaseType &other) const
1595 {
1596   if (get_kind () != other.get_kind ())
1597     return false;
1598
1599   auto other2 = other.as<const ADTType> ();
1600   if (get_adt_kind () != other2->get_adt_kind ())
1601     return false;
1602
1603   if (number_of_variants () != other2->number_of_variants ())
1604     return false;
1605
1606   if (has_substitutions_defined () != other2->has_substitutions_defined ())
1607     return false;
1608
1609   if (has_substitutions_defined ())
1610     {
1611       if (get_num_substitutions () != other2->get_num_substitutions ())
1612         return false;
1613
1614       for (size_t i = 0; i < get_num_substitutions (); i++)
1615         {
1616           const SubstitutionParamMapping &a = substitutions.at (i);
1617           const SubstitutionParamMapping &b = other2->substitutions.at (i);
1618
1619           const ParamType *aa = a.get_param_ty ();
1620           const ParamType *bb = b.get_param_ty ();
1621           BaseType *aaa = aa->resolve ();
1622           BaseType *bbb = bb->resolve ();
1623           if (!aaa->is_equal (*bbb))
1624             return false;
1625         }
1626     }
1627
1628   for (size_t i = 0; i < number_of_variants (); i++)
1629     {
1630       const TyTy::VariantDef *a = get_variants ().at (i);
1631       const TyTy::VariantDef *b = other2->get_variants ().at (i);
1632
1633       if (!a->is_equal (*b))
1634         return false;
1635     }
1636
1637   return true;
1638 }
1639
1640 BaseType *
1641 ADTType::clone () const
1642 {
1643   std::vector<VariantDef *> cloned_variants;
1644   for (auto &variant : variants)
1645     cloned_variants.push_back (variant->clone ());
1646
1647   return new ADTType (get_ref (), get_ty_ref (), identifier, ident,
1648                       get_adt_kind (), cloned_variants, clone_substs (),
1649                       get_repr_options (), used_arguments,
1650                       get_region_constraints (), get_combined_refs ());
1651 }
1652
1653 static bool
1654 handle_substitions (SubstitutionArgumentMappings &subst_mappings,
1655                     StructFieldType *field)
1656 {
1657   auto fty = field->get_field_type ();
1658   if (auto p = fty->try_as<ParamType> ())
1659     {
1660       SubstitutionArg arg = SubstitutionArg::error ();
1661       bool ok = subst_mappings.get_argument_for_symbol (p, &arg);
1662       if (ok)
1663         {
1664           auto argt = arg.get_tyty ();
1665           bool arg_is_param = argt->get_kind () == TyTy::TypeKind::PARAM;
1666           bool arg_is_concrete = argt->get_kind () != TyTy::TypeKind::INFER;
1667
1668           if (arg_is_param || arg_is_concrete)
1669             {
1670               auto new_field = argt->clone ();
1671               new_field->set_ref (fty->get_ref ());
1672               field->set_field_type (new_field);
1673             }
1674           else
1675             {
1676               field->get_field_type ()->set_ty_ref (argt->get_ref ());
1677             }
1678         }
1679     }
1680   else if (fty->has_substitutions_defined () || !fty->is_concrete ())
1681     {
1682       BaseType *concrete
1683         = Resolver::SubstMapperInternal::Resolve (fty, subst_mappings);
1684
1685       if (concrete->get_kind () == TyTy::TypeKind::ERROR)
1686         {
1687           rust_error_at (subst_mappings.get_locus (),
1688                          "Failed to resolve field substitution type: %s",
1689                          fty->as_string ().c_str ());
1690           return false;
1691         }
1692
1693       auto new_field = concrete->clone ();
1694       new_field->set_ref (fty->get_ref ());
1695       field->set_field_type (new_field);
1696     }
1697
1698   return true;
1699 }
1700
1701 ADTType *
1702 ADTType::handle_substitions (SubstitutionArgumentMappings &subst_mappings)
1703 {
1704   auto adt = clone ()->as<ADTType> ();
1705   adt->set_ty_ref (mappings->get_next_hir_id ());
1706   adt->used_arguments = subst_mappings;
1707
1708   for (auto &sub : adt->get_substs ())
1709     {
1710       SubstitutionArg arg = SubstitutionArg::error ();
1711       bool ok
1712         = subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
1713       if (ok)
1714         sub.fill_param_ty (subst_mappings, subst_mappings.get_locus ());
1715     }
1716
1717   for (auto &variant : adt->get_variants ())
1718     {
1719       if (variant->is_dataless_variant ())
1720         continue;
1721
1722       for (auto &field : variant->get_fields ())
1723         {
1724           bool ok = ::Rust::TyTy::handle_substitions (subst_mappings, field);
1725           if (!ok)
1726             return adt;
1727         }
1728     }
1729
1730   return adt;
1731 }
1732
1733 // TupleType
1734
1735 TupleType::TupleType (HirId ref, location_t locus, std::vector<TyVar> fields,
1736                       std::set<HirId> refs)
1737   : BaseType (ref, ref, KIND, {Resolver::CanonicalPath::create_empty (), locus},
1738               refs),
1739     fields (fields)
1740 {}
1741
1742 TupleType::TupleType (HirId ref, HirId ty_ref, location_t locus,
1743                       std::vector<TyVar> fields, std::set<HirId> refs)
1744   : BaseType (ref, ty_ref, KIND,
1745               {Resolver::CanonicalPath::create_empty (), locus}, refs),
1746     fields (fields)
1747 {}
1748
1749 TupleType *
1750 TupleType::get_unit_type (HirId ref)
1751 {
1752   return new TupleType (ref, BUILTINS_LOCATION);
1753 }
1754
1755 size_t
1756 TupleType::num_fields () const
1757 {
1758   return fields.size ();
1759 }
1760
1761 const std::vector<TyVar> &
1762 TupleType::get_fields () const
1763 {
1764   return fields;
1765 }
1766
1767 void
1768 TupleType::accept_vis (TyVisitor &vis)
1769 {
1770   vis.visit (*this);
1771 }
1772
1773 void
1774 TupleType::accept_vis (TyConstVisitor &vis) const
1775 {
1776   vis.visit (*this);
1777 }
1778
1779 std::string
1780 TupleType::as_string () const
1781 {
1782   size_t i = 0;
1783   std::string fields_buffer;
1784   for (const TyVar &field : get_fields ())
1785     {
1786       fields_buffer += field.get_tyty ()->as_string ();
1787       bool has_next = (i + 1) < get_fields ().size ();
1788       fields_buffer += has_next ? ", " : "";
1789       i++;
1790     }
1791   return "(" + fields_buffer + ")";
1792 }
1793
1794 std::string
1795 TupleType::get_name () const
1796 {
1797   size_t i = 0;
1798   std::string fields_buffer;
1799   for (const TyVar &field : get_fields ())
1800     {
1801       fields_buffer += field.get_tyty ()->as_string ();
1802       bool has_next = (i + 1) < get_fields ().size ();
1803       fields_buffer += has_next ? ", " : "";
1804       i++;
1805     }
1806   return "(" + fields_buffer + ")";
1807 }
1808
1809 BaseType *
1810 TupleType::get_field (size_t index) const
1811 {
1812   return fields.at (index).get_tyty ();
1813 }
1814
1815 bool
1816 TupleType::can_eq (const BaseType *other, bool emit_errors) const
1817 {
1818   TupleCmp r (this, emit_errors);
1819   return r.can_eq (other);
1820 }
1821
1822 bool
1823 TupleType::is_equal (const BaseType &other) const
1824 {
1825   if (get_kind () != other.get_kind ())
1826     return false;
1827
1828   auto other2 = other.as<const TupleType> ();
1829   if (num_fields () != other2->num_fields ())
1830     return false;
1831
1832   for (size_t i = 0; i < num_fields (); i++)
1833     {
1834       if (!get_field (i)->is_equal (*other2->get_field (i)))
1835         return false;
1836     }
1837   return true;
1838 }
1839
1840 BaseType *
1841 TupleType::clone () const
1842 {
1843   std::vector<TyVar> cloned_fields;
1844   for (const auto &f : fields)
1845     cloned_fields.push_back (f.clone ());
1846
1847   return new TupleType (get_ref (), get_ty_ref (), get_ident ().locus,
1848                         cloned_fields, get_combined_refs ());
1849 }
1850
1851 TupleType *
1852 TupleType::handle_substitions (SubstitutionArgumentMappings &mappings)
1853 {
1854   auto mappings_table = Analysis::Mappings::get ();
1855
1856   auto tuple = clone ()->as<TupleType> ();
1857   tuple->set_ref (mappings_table->get_next_hir_id ());
1858   tuple->set_ty_ref (mappings_table->get_next_hir_id ());
1859
1860   for (size_t i = 0; i < tuple->fields.size (); i++)
1861     {
1862       TyVar &field = fields.at (i);
1863       if (!field.get_tyty ()->is_concrete ())
1864         {
1865           BaseType *concrete
1866             = Resolver::SubstMapperInternal::Resolve (field.get_tyty (),
1867                                                       mappings);
1868           tuple->fields[i]
1869             = TyVar::subst_covariant_var (field.get_tyty (), concrete);
1870         }
1871     }
1872
1873   return tuple;
1874 }
1875
1876 void
1877 FnType::accept_vis (TyVisitor &vis)
1878 {
1879   vis.visit (*this);
1880 }
1881
1882 void
1883 FnType::accept_vis (TyConstVisitor &vis) const
1884 {
1885   vis.visit (*this);
1886 }
1887
1888 std::string
1889 FnType::as_string () const
1890 {
1891   std::string params_str = "";
1892   for (auto &param : params)
1893     {
1894       auto pattern = param.first;
1895       auto ty = param.second;
1896       params_str += pattern->as_string () + " " + ty->as_string ();
1897       params_str += ",";
1898     }
1899
1900   std::string ret_str = type->as_string ();
1901   return "fn" + subst_as_string () + " (" + params_str + ") -> " + ret_str;
1902 }
1903
1904 bool
1905 FnType::can_eq (const BaseType *other, bool emit_errors) const
1906 {
1907   FnCmp r (this, emit_errors);
1908   return r.can_eq (other);
1909 }
1910
1911 bool
1912 FnType::is_equal (const BaseType &other) const
1913 {
1914   if (get_kind () != other.get_kind ())
1915     return false;
1916
1917   auto other2 = static_cast<const FnType &> (other);
1918   if (get_identifier ().compare (other2.get_identifier ()) != 0)
1919     return false;
1920
1921   if (!get_return_type ()->is_equal (*other2.get_return_type ()))
1922     return false;
1923
1924   if (has_substitutions_defined () != other2.has_substitutions_defined ())
1925     return false;
1926
1927   if (has_substitutions_defined ())
1928     {
1929       if (get_num_substitutions () != other2.get_num_substitutions ())
1930         return false;
1931
1932       const FnType &ofn = static_cast<const FnType &> (other);
1933       for (size_t i = 0; i < get_num_substitutions (); i++)
1934         {
1935           const SubstitutionParamMapping &a = get_substs ().at (i);
1936           const SubstitutionParamMapping &b = ofn.get_substs ().at (i);
1937
1938           const ParamType *pa = a.get_param_ty ();
1939           const ParamType *pb = b.get_param_ty ();
1940
1941           if (!pa->is_equal (*pb))
1942             return false;
1943         }
1944     }
1945
1946   if (num_params () != other2.num_params ())
1947     return false;
1948
1949   for (size_t i = 0; i < num_params (); i++)
1950     {
1951       auto lhs = param_at (i).second;
1952       auto rhs = other2.param_at (i).second;
1953       if (!lhs->is_equal (*rhs))
1954         return false;
1955     }
1956   return true;
1957 }
1958
1959 BaseType *
1960 FnType::clone () const
1961 {
1962   std::vector<std::pair<HIR::Pattern *, BaseType *>> cloned_params;
1963   for (auto &p : params)
1964     cloned_params.push_back ({p.first, p.second->clone ()});
1965
1966   return new FnType (get_ref (), get_ty_ref (), get_id (), get_identifier (),
1967                      ident, flags, abi, std::move (cloned_params),
1968                      get_return_type ()->clone (), clone_substs (),
1969                      get_substitution_arguments (), get_region_constraints (),
1970                      get_combined_refs ());
1971 }
1972
1973 FnType *
1974 FnType::handle_substitions (SubstitutionArgumentMappings &subst_mappings)
1975 {
1976   FnType *fn = static_cast<FnType *> (clone ());
1977   fn->set_ty_ref (mappings->get_next_hir_id ());
1978   fn->used_arguments = subst_mappings;
1979
1980   for (auto &sub : fn->get_substs ())
1981     {
1982       SubstitutionArg arg = SubstitutionArg::error ();
1983
1984       bool ok
1985         = subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
1986       if (ok)
1987         {
1988           sub.fill_param_ty (subst_mappings, subst_mappings.get_locus ());
1989         }
1990     }
1991
1992   auto fty = fn->get_return_type ();
1993   bool is_param_ty = fty->get_kind () == TypeKind::PARAM;
1994   if (is_param_ty)
1995     {
1996       ParamType *p = static_cast<ParamType *> (fty);
1997
1998       SubstitutionArg arg = SubstitutionArg::error ();
1999       bool ok = subst_mappings.get_argument_for_symbol (p, &arg);
2000       if (ok)
2001         {
2002           auto argt = arg.get_tyty ();
2003           bool arg_is_param = argt->get_kind () == TyTy::TypeKind::PARAM;
2004           bool arg_is_concrete = argt->get_kind () != TyTy::TypeKind::INFER;
2005
2006           if (arg_is_param || arg_is_concrete)
2007             {
2008               auto new_field = argt->clone ();
2009               new_field->set_ref (fty->get_ref ());
2010               fn->type = new_field;
2011             }
2012           else
2013             {
2014               fty->set_ty_ref (argt->get_ref ());
2015             }
2016         }
2017     }
2018   else if (fty->needs_generic_substitutions () || !fty->is_concrete ())
2019     {
2020       BaseType *concrete
2021         = Resolver::SubstMapperInternal::Resolve (fty, subst_mappings);
2022
2023       if (concrete == nullptr || concrete->get_kind () == TyTy::TypeKind::ERROR)
2024         {
2025           rust_error_at (subst_mappings.get_locus (),
2026                          "Failed to resolve field substitution type: %s",
2027                          fty->as_string ().c_str ());
2028           return nullptr;
2029         }
2030
2031       auto new_field = concrete->clone ();
2032       new_field->set_ref (fty->get_ref ());
2033       fn->type = new_field;
2034     }
2035
2036   for (auto &param : fn->get_params ())
2037     {
2038       auto fty = param.second;
2039
2040       bool is_param_ty = fty->get_kind () == TypeKind::PARAM;
2041       if (is_param_ty)
2042         {
2043           ParamType *p = static_cast<ParamType *> (fty);
2044
2045           SubstitutionArg arg = SubstitutionArg::error ();
2046           bool ok = subst_mappings.get_argument_for_symbol (p, &arg);
2047           if (ok)
2048             {
2049               auto argt = arg.get_tyty ();
2050               bool arg_is_param = argt->get_kind () == TyTy::TypeKind::PARAM;
2051               bool arg_is_concrete = argt->get_kind () != TyTy::TypeKind::INFER;
2052
2053               if (arg_is_param || arg_is_concrete)
2054                 {
2055                   auto new_field = argt->clone ();
2056                   new_field->set_ref (fty->get_ref ());
2057                   param.second = new_field;
2058                 }
2059               else
2060                 {
2061                   fty->set_ty_ref (argt->get_ref ());
2062                 }
2063             }
2064         }
2065       else if (fty->has_substitutions_defined () || !fty->is_concrete ())
2066         {
2067           BaseType *concrete
2068             = Resolver::SubstMapperInternal::Resolve (fty, subst_mappings);
2069
2070           if (concrete == nullptr
2071               || concrete->get_kind () == TyTy::TypeKind::ERROR)
2072             {
2073               rust_error_at (subst_mappings.get_locus (),
2074                              "Failed to resolve field substitution type: %s",
2075                              fty->as_string ().c_str ());
2076               return nullptr;
2077             }
2078
2079           auto new_field = concrete->clone ();
2080           new_field->set_ref (fty->get_ref ());
2081           param.second = new_field;
2082         }
2083     }
2084
2085   return fn;
2086 }
2087
2088 void
2089 FnPtr::accept_vis (TyVisitor &vis)
2090 {
2091   vis.visit (*this);
2092 }
2093
2094 void
2095 FnPtr::accept_vis (TyConstVisitor &vis) const
2096 {
2097   vis.visit (*this);
2098 }
2099
2100 std::string
2101 FnPtr::as_string () const
2102 {
2103   std::string params_str;
2104
2105   auto &params = get_params ();
2106   for (auto &p : params)
2107     {
2108       params_str += p.get_tyty ()->as_string () + " ,";
2109     }
2110
2111   return "fnptr (" + params_str + ") -> " + get_return_type ()->as_string ();
2112 }
2113
2114 bool
2115 FnPtr::can_eq (const BaseType *other, bool emit_errors) const
2116 {
2117   FnptrCmp r (this, emit_errors);
2118   return r.can_eq (other);
2119 }
2120
2121 bool
2122 FnPtr::is_equal (const BaseType &other) const
2123 {
2124   if (get_kind () != other.get_kind ())
2125     return false;
2126
2127   auto other2 = static_cast<const FnPtr &> (other);
2128   auto this_ret_type = get_return_type ();
2129   auto other_ret_type = other2.get_return_type ();
2130   if (this_ret_type->is_equal (*other_ret_type))
2131     return false;
2132
2133   if (num_params () != other2.num_params ())
2134     return false;
2135
2136   for (size_t i = 0; i < num_params (); i++)
2137     {
2138       if (!get_param_type_at (i)->is_equal (*other2.get_param_type_at (i)))
2139         return false;
2140     }
2141   return true;
2142 }
2143
2144 BaseType *
2145 FnPtr::clone () const
2146 {
2147   std::vector<TyVar> cloned_params;
2148   for (auto &p : params)
2149     cloned_params.push_back (TyVar (p.get_ref ()));
2150
2151   return new FnPtr (get_ref (), get_ty_ref (), ident.locus,
2152                     std::move (cloned_params), result_type,
2153                     get_combined_refs ());
2154 }
2155
2156 void
2157 ClosureType::accept_vis (TyVisitor &vis)
2158 {
2159   vis.visit (*this);
2160 }
2161
2162 void
2163 ClosureType::accept_vis (TyConstVisitor &vis) const
2164 {
2165   vis.visit (*this);
2166 }
2167
2168 std::string
2169 ClosureType::as_string () const
2170 {
2171   std::string params_buf = parameters->as_string ();
2172   return "|" + params_buf + "| {" + result_type.get_tyty ()->as_string () + "}";
2173 }
2174
2175 bool
2176 ClosureType::can_eq (const BaseType *other, bool emit_errors) const
2177 {
2178   ClosureCmp r (this, emit_errors);
2179   return r.can_eq (other);
2180 }
2181
2182 bool
2183 ClosureType::is_equal (const BaseType &other) const
2184 {
2185   if (other.get_kind () != TypeKind::CLOSURE)
2186     return false;
2187
2188   const ClosureType &other2 = static_cast<const ClosureType &> (other);
2189   if (get_def_id () != other2.get_def_id ())
2190     return false;
2191
2192   if (!get_parameters ().is_equal (other2.get_parameters ()))
2193     return false;
2194
2195   return get_result_type ().is_equal (other2.get_result_type ());
2196 }
2197
2198 BaseType *
2199 ClosureType::clone () const
2200 {
2201   return new ClosureType (get_ref (), get_ty_ref (), ident, id,
2202                           (TyTy::TupleType *) parameters->clone (), result_type,
2203                           clone_substs (), captures, get_combined_refs (),
2204                           specified_bounds);
2205 }
2206
2207 ClosureType *
2208 ClosureType::handle_substitions (SubstitutionArgumentMappings &mappings)
2209 {
2210   rust_unreachable ();
2211   return nullptr;
2212 }
2213
2214 void
2215 ClosureType::setup_fn_once_output () const
2216 {
2217   // lookup the lang items
2218   auto fn_once_lang_item = LangItem::Kind::FN_ONCE;
2219   auto fn_once_output_lang_item = LangItem::Kind::FN_ONCE_OUTPUT;
2220
2221   DefId trait_id = UNKNOWN_DEFID;
2222   bool trait_lang_item_defined
2223     = mappings->lookup_lang_item (fn_once_lang_item, &trait_id);
2224   rust_assert (trait_lang_item_defined);
2225
2226   DefId trait_item_id = UNKNOWN_DEFID;
2227   bool trait_item_lang_item_defined
2228     = mappings->lookup_lang_item (fn_once_output_lang_item, &trait_item_id);
2229   rust_assert (trait_item_lang_item_defined);
2230
2231   // resolve to the trait
2232   HIR::Item *item = mappings->lookup_defid (trait_id);
2233   rust_assert (item->get_item_kind () == HIR::Item::ItemKind::Trait);
2234   HIR::Trait *trait = static_cast<HIR::Trait *> (item);
2235
2236   Resolver::TraitReference *trait_ref
2237     = Resolver::TraitResolver::Resolve (*trait);
2238   rust_assert (!trait_ref->is_error ());
2239
2240   // resolve to trait item
2241   HIR::TraitItem *trait_item
2242     = mappings->lookup_trait_item_defid (trait_item_id);
2243   rust_assert (trait_item != nullptr);
2244   rust_assert (trait_item->get_item_kind ()
2245                == HIR::TraitItem::TraitItemKind::TYPE);
2246   std::string item_identifier = trait_item->trait_identifier ();
2247
2248   // setup associated types  #[lang = "fn_once_output"]
2249   Resolver::TraitItemReference *item_reference = nullptr;
2250   bool found = trait_ref->lookup_trait_item_by_type (
2251     item_identifier, Resolver::TraitItemReference::TraitItemType::TYPE,
2252     &item_reference);
2253   rust_assert (found);
2254
2255   // setup
2256   item_reference->associated_type_set (&get_result_type ());
2257 }
2258
2259 void
2260 ArrayType::accept_vis (TyVisitor &vis)
2261 {
2262   vis.visit (*this);
2263 }
2264
2265 void
2266 ArrayType::accept_vis (TyConstVisitor &vis) const
2267 {
2268   vis.visit (*this);
2269 }
2270
2271 std::string
2272 ArrayType::as_string () const
2273 {
2274   return "[" + get_element_type ()->as_string () + ":" + "CAPACITY" + "]";
2275 }
2276
2277 bool
2278 ArrayType::can_eq (const BaseType *other, bool emit_errors) const
2279 {
2280   ArrayCmp r (this, emit_errors);
2281   return r.can_eq (other);
2282 }
2283
2284 bool
2285 ArrayType::is_equal (const BaseType &other) const
2286 {
2287   if (get_kind () != other.get_kind ())
2288     return false;
2289
2290   auto other2 = static_cast<const ArrayType &> (other);
2291
2292   auto this_element_type = get_element_type ();
2293   auto other_element_type = other2.get_element_type ();
2294
2295   return this_element_type->is_equal (*other_element_type);
2296 }
2297
2298 BaseType *
2299 ArrayType::get_element_type () const
2300 {
2301   return element_type.get_tyty ();
2302 }
2303
2304 const TyVar &
2305 ArrayType::get_var_element_type () const
2306 {
2307   return element_type;
2308 }
2309
2310 BaseType *
2311 ArrayType::clone () const
2312 {
2313   return new ArrayType (get_ref (), get_ty_ref (), ident.locus, capacity_expr,
2314                         element_type, get_combined_refs ());
2315 }
2316
2317 ArrayType *
2318 ArrayType::handle_substitions (SubstitutionArgumentMappings &mappings)
2319 {
2320   auto mappings_table = Analysis::Mappings::get ();
2321
2322   ArrayType *ref = static_cast<ArrayType *> (clone ());
2323   ref->set_ty_ref (mappings_table->get_next_hir_id ());
2324
2325   // might be &T or &ADT so this needs to be recursive
2326   auto base = ref->get_element_type ();
2327   BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
2328   ref->element_type = TyVar::subst_covariant_var (base, concrete);
2329
2330   return ref;
2331 }
2332
2333 void
2334 SliceType::accept_vis (TyVisitor &vis)
2335 {
2336   vis.visit (*this);
2337 }
2338
2339 void
2340 SliceType::accept_vis (TyConstVisitor &vis) const
2341 {
2342   vis.visit (*this);
2343 }
2344
2345 std::string
2346 SliceType::as_string () const
2347 {
2348   return "[" + get_element_type ()->as_string () + "]";
2349 }
2350
2351 bool
2352 SliceType::can_eq (const BaseType *other, bool emit_errors) const
2353 {
2354   SliceCmp r (this, emit_errors);
2355   return r.can_eq (other);
2356 }
2357
2358 bool
2359 SliceType::is_equal (const BaseType &other) const
2360 {
2361   if (get_kind () != other.get_kind ())
2362     return false;
2363
2364   auto other2 = static_cast<const SliceType &> (other);
2365
2366   auto this_element_type = get_element_type ();
2367   auto other_element_type = other2.get_element_type ();
2368
2369   return this_element_type->is_equal (*other_element_type);
2370 }
2371
2372 BaseType *
2373 SliceType::get_element_type () const
2374 {
2375   return element_type.get_tyty ();
2376 }
2377
2378 const TyVar &
2379 SliceType::get_var_element_type () const
2380 {
2381   return element_type;
2382 }
2383
2384 BaseType *
2385 SliceType::clone () const
2386 {
2387   return new SliceType (get_ref (), get_ty_ref (), ident.locus,
2388                         element_type.clone (), get_combined_refs ());
2389 }
2390
2391 SliceType *
2392 SliceType::handle_substitions (SubstitutionArgumentMappings &mappings)
2393 {
2394   auto mappings_table = Analysis::Mappings::get ();
2395
2396   SliceType *ref = static_cast<SliceType *> (clone ());
2397   ref->set_ty_ref (mappings_table->get_next_hir_id ());
2398
2399   // might be &T or &ADT so this needs to be recursive
2400   auto base = ref->get_element_type ();
2401   BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
2402   ref->element_type = TyVar::subst_covariant_var (base, concrete);
2403
2404   return ref;
2405 }
2406
2407 // BoolType
2408
2409 BoolType::BoolType (HirId ref, std::set<HirId> refs)
2410   : BaseType (ref, ref, KIND,
2411               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2412               refs)
2413 {}
2414
2415 BoolType::BoolType (HirId ref, HirId ty_ref, std::set<HirId> refs)
2416   : BaseType (ref, ty_ref, KIND,
2417               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2418               refs)
2419 {}
2420
2421 std::string
2422 BoolType::get_name () const
2423 {
2424   return as_string ();
2425 }
2426
2427 void
2428 BoolType::accept_vis (TyVisitor &vis)
2429 {
2430   vis.visit (*this);
2431 }
2432
2433 void
2434 BoolType::accept_vis (TyConstVisitor &vis) const
2435 {
2436   vis.visit (*this);
2437 }
2438
2439 std::string
2440 BoolType::as_string () const
2441 {
2442   return "bool";
2443 }
2444
2445 bool
2446 BoolType::can_eq (const BaseType *other, bool emit_errors) const
2447 {
2448   BoolCmp r (this, emit_errors);
2449   return r.can_eq (other);
2450 }
2451
2452 BaseType *
2453 BoolType::clone () const
2454 {
2455   return new BoolType (get_ref (), get_ty_ref (), get_combined_refs ());
2456 }
2457
2458 // IntType
2459
2460 IntType::IntType (HirId ref, IntKind kind, std::set<HirId> refs)
2461   : BaseType (ref, ref, KIND,
2462               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2463               refs),
2464     int_kind (kind)
2465 {}
2466
2467 IntType::IntType (HirId ref, HirId ty_ref, IntKind kind, std::set<HirId> refs)
2468   : BaseType (ref, ty_ref, KIND,
2469               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2470               refs),
2471     int_kind (kind)
2472 {}
2473
2474 std::string
2475 IntType::get_name () const
2476 {
2477   return as_string ();
2478 }
2479
2480 IntType::IntKind
2481 IntType::get_int_kind () const
2482 {
2483   return int_kind;
2484 }
2485
2486 void
2487 IntType::accept_vis (TyVisitor &vis)
2488 {
2489   vis.visit (*this);
2490 }
2491
2492 void
2493 IntType::accept_vis (TyConstVisitor &vis) const
2494 {
2495   vis.visit (*this);
2496 }
2497
2498 std::string
2499 IntType::as_string () const
2500 {
2501   switch (int_kind)
2502     {
2503     case I8:
2504       return "i8";
2505     case I16:
2506       return "i16";
2507     case I32:
2508       return "i32";
2509     case I64:
2510       return "i64";
2511     case I128:
2512       return "i128";
2513     }
2514   rust_unreachable ();
2515   return "__unknown_int_type";
2516 }
2517
2518 bool
2519 IntType::can_eq (const BaseType *other, bool emit_errors) const
2520 {
2521   IntCmp r (this, emit_errors);
2522   return r.can_eq (other);
2523 }
2524
2525 BaseType *
2526 IntType::clone () const
2527 {
2528   return new IntType (get_ref (), get_ty_ref (), get_int_kind (),
2529                       get_combined_refs ());
2530 }
2531
2532 bool
2533 IntType::is_equal (const BaseType &other) const
2534 {
2535   if (!BaseType::is_equal (other))
2536     return false;
2537
2538   const IntType &o = static_cast<const IntType &> (other);
2539   return get_int_kind () == o.get_int_kind ();
2540 }
2541
2542 // UintType
2543
2544 UintType::UintType (HirId ref, UintKind kind, std::set<HirId> refs)
2545   : BaseType (ref, ref, KIND,
2546               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2547               refs),
2548     uint_kind (kind)
2549 {}
2550
2551 UintType::UintType (HirId ref, HirId ty_ref, UintKind kind,
2552                     std::set<HirId> refs)
2553   : BaseType (ref, ty_ref, KIND,
2554               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2555               refs),
2556     uint_kind (kind)
2557 {}
2558
2559 std::string
2560 UintType::get_name () const
2561 {
2562   return as_string ();
2563 }
2564
2565 UintType::UintKind
2566 UintType::get_uint_kind () const
2567 {
2568   return uint_kind;
2569 }
2570
2571 void
2572 UintType::accept_vis (TyVisitor &vis)
2573 {
2574   vis.visit (*this);
2575 }
2576
2577 void
2578 UintType::accept_vis (TyConstVisitor &vis) const
2579 {
2580   vis.visit (*this);
2581 }
2582
2583 std::string
2584 UintType::as_string () const
2585 {
2586   switch (uint_kind)
2587     {
2588     case U8:
2589       return "u8";
2590     case U16:
2591       return "u16";
2592     case U32:
2593       return "u32";
2594     case U64:
2595       return "u64";
2596     case U128:
2597       return "u128";
2598     }
2599   rust_unreachable ();
2600   return "__unknown_uint_type";
2601 }
2602
2603 bool
2604 UintType::can_eq (const BaseType *other, bool emit_errors) const
2605 {
2606   UintCmp r (this, emit_errors);
2607   return r.can_eq (other);
2608 }
2609
2610 BaseType *
2611 UintType::clone () const
2612 {
2613   return new UintType (get_ref (), get_ty_ref (), get_uint_kind (),
2614                        get_combined_refs ());
2615 }
2616
2617 bool
2618 UintType::is_equal (const BaseType &other) const
2619 {
2620   if (!BaseType::is_equal (other))
2621     return false;
2622
2623   const UintType &o = static_cast<const UintType &> (other);
2624   return get_uint_kind () == o.get_uint_kind ();
2625 }
2626
2627 // FloatType
2628
2629 FloatType::FloatType (HirId ref, FloatKind kind, std::set<HirId> refs)
2630   : BaseType (ref, ref, KIND,
2631               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2632               refs),
2633     float_kind (kind)
2634 {}
2635
2636 FloatType::FloatType (HirId ref, HirId ty_ref, FloatKind kind,
2637                       std::set<HirId> refs)
2638   : BaseType (ref, ty_ref, KIND,
2639               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2640               refs),
2641     float_kind (kind)
2642 {}
2643
2644 std::string
2645 FloatType::get_name () const
2646 {
2647   return as_string ();
2648 }
2649
2650 FloatType::FloatKind
2651 FloatType::get_float_kind () const
2652 {
2653   return float_kind;
2654 }
2655
2656 void
2657 FloatType::accept_vis (TyVisitor &vis)
2658 {
2659   vis.visit (*this);
2660 }
2661
2662 void
2663 FloatType::accept_vis (TyConstVisitor &vis) const
2664 {
2665   vis.visit (*this);
2666 }
2667
2668 std::string
2669 FloatType::as_string () const
2670 {
2671   switch (float_kind)
2672     {
2673     case F32:
2674       return "f32";
2675     case F64:
2676       return "f64";
2677     }
2678   rust_unreachable ();
2679   return "__unknown_float_type";
2680 }
2681
2682 bool
2683 FloatType::can_eq (const BaseType *other, bool emit_errors) const
2684 {
2685   FloatCmp r (this, emit_errors);
2686   return r.can_eq (other);
2687 }
2688
2689 BaseType *
2690 FloatType::clone () const
2691 {
2692   return new FloatType (get_ref (), get_ty_ref (), get_float_kind (),
2693                         get_combined_refs ());
2694 }
2695
2696 bool
2697 FloatType::is_equal (const BaseType &other) const
2698 {
2699   if (!BaseType::is_equal (other))
2700     return false;
2701
2702   const FloatType &o = static_cast<const FloatType &> (other);
2703   return get_float_kind () == o.get_float_kind ();
2704 }
2705
2706 // UsizeType
2707
2708 USizeType::USizeType (HirId ref, std::set<HirId> refs)
2709   : BaseType (ref, ref, KIND,
2710               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2711               refs)
2712 {}
2713
2714 USizeType::USizeType (HirId ref, HirId ty_ref, std::set<HirId> refs)
2715   : BaseType (ref, ty_ref, KIND,
2716               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2717               refs)
2718 {}
2719
2720 std::string
2721 USizeType::get_name () const
2722 {
2723   return as_string ();
2724 }
2725
2726 void
2727 USizeType::accept_vis (TyVisitor &vis)
2728 {
2729   vis.visit (*this);
2730 }
2731
2732 void
2733 USizeType::accept_vis (TyConstVisitor &vis) const
2734 {
2735   vis.visit (*this);
2736 }
2737
2738 std::string
2739 USizeType::as_string () const
2740 {
2741   return "usize";
2742 }
2743
2744 bool
2745 USizeType::can_eq (const BaseType *other, bool emit_errors) const
2746 {
2747   USizeCmp r (this, emit_errors);
2748   return r.can_eq (other);
2749 }
2750
2751 BaseType *
2752 USizeType::clone () const
2753 {
2754   return new USizeType (get_ref (), get_ty_ref (), get_combined_refs ());
2755 }
2756
2757 // ISizeType
2758
2759 ISizeType::ISizeType (HirId ref, std::set<HirId> refs)
2760   : BaseType (ref, ref, KIND,
2761               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2762               refs)
2763 {}
2764
2765 ISizeType::ISizeType (HirId ref, HirId ty_ref, std::set<HirId> refs)
2766   : BaseType (ref, ty_ref, KIND,
2767               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2768               refs)
2769 {}
2770
2771 std::string
2772 ISizeType::get_name () const
2773 {
2774   return as_string ();
2775 }
2776
2777 void
2778 ISizeType::accept_vis (TyVisitor &vis)
2779 {
2780   vis.visit (*this);
2781 }
2782
2783 void
2784 ISizeType::accept_vis (TyConstVisitor &vis) const
2785 {
2786   vis.visit (*this);
2787 }
2788
2789 std::string
2790 ISizeType::as_string () const
2791 {
2792   return "isize";
2793 }
2794
2795 bool
2796 ISizeType::can_eq (const BaseType *other, bool emit_errors) const
2797 {
2798   ISizeCmp r (this, emit_errors);
2799   return r.can_eq (other);
2800 }
2801
2802 BaseType *
2803 ISizeType::clone () const
2804 {
2805   return new ISizeType (get_ref (), get_ty_ref (), get_combined_refs ());
2806 }
2807
2808 // Char Type
2809
2810 CharType::CharType (HirId ref, std::set<HirId> refs)
2811   : BaseType (ref, ref, KIND,
2812               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2813               refs)
2814 {}
2815
2816 CharType::CharType (HirId ref, HirId ty_ref, std::set<HirId> refs)
2817   : BaseType (ref, ty_ref, KIND,
2818               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2819               refs)
2820 {}
2821
2822 std::string
2823 CharType::get_name () const
2824 {
2825   return as_string ();
2826 }
2827
2828 void
2829 CharType::accept_vis (TyVisitor &vis)
2830 {
2831   vis.visit (*this);
2832 }
2833
2834 void
2835 CharType::accept_vis (TyConstVisitor &vis) const
2836 {
2837   vis.visit (*this);
2838 }
2839
2840 std::string
2841 CharType::as_string () const
2842 {
2843   return "char";
2844 }
2845
2846 bool
2847 CharType::can_eq (const BaseType *other, bool emit_errors) const
2848 {
2849   CharCmp r (this, emit_errors);
2850   return r.can_eq (other);
2851 }
2852
2853 BaseType *
2854 CharType::clone () const
2855 {
2856   return new CharType (get_ref (), get_ty_ref (), get_combined_refs ());
2857 }
2858
2859 // Reference Type
2860
2861 ReferenceType::ReferenceType (HirId ref, TyVar base, Mutability mut,
2862                               Region region, std::set<HirId> refs)
2863   : BaseType (ref, ref, KIND,
2864               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2865               std::move (refs)),
2866     base (base), mut (mut), region (region)
2867 {}
2868
2869 ReferenceType::ReferenceType (HirId ref, HirId ty_ref, TyVar base,
2870                               Mutability mut, Region region,
2871                               std::set<HirId> refs)
2872   : BaseType (ref, ty_ref, KIND,
2873               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
2874               std::move (refs)),
2875     base (base), mut (mut), region (region)
2876 {}
2877
2878 Mutability
2879 ReferenceType::mutability () const
2880 {
2881   return mut;
2882 }
2883
2884 bool
2885 ReferenceType::is_mutable () const
2886 {
2887   return mut == Mutability::Mut;
2888 }
2889 Region
2890 ReferenceType::get_region () const
2891 {
2892   return region;
2893 }
2894
2895 bool
2896 ReferenceType::is_dyn_object () const
2897 {
2898   return is_dyn_slice_type () || is_dyn_str_type () || is_dyn_obj_type ();
2899 }
2900
2901 bool
2902 ReferenceType::is_dyn_slice_type (const TyTy::SliceType **slice) const
2903 {
2904   const TyTy::BaseType *element = get_base ()->destructure ();
2905   if (element->get_kind () != TyTy::TypeKind::SLICE)
2906     return false;
2907   if (slice == nullptr)
2908     return true;
2909
2910   *slice = static_cast<const TyTy::SliceType *> (element);
2911   return true;
2912 }
2913
2914 bool
2915 ReferenceType::is_dyn_str_type (const TyTy::StrType **str) const
2916 {
2917   const TyTy::BaseType *element = get_base ()->destructure ();
2918   if (element->get_kind () != TyTy::TypeKind::STR)
2919     return false;
2920   if (str == nullptr)
2921     return true;
2922
2923   *str = static_cast<const TyTy::StrType *> (element);
2924   return true;
2925 }
2926
2927 bool
2928 ReferenceType::is_dyn_obj_type (const TyTy::DynamicObjectType **dyn) const
2929 {
2930   const TyTy::BaseType *element = get_base ()->destructure ();
2931   if (element->get_kind () != TyTy::TypeKind::DYNAMIC)
2932     return false;
2933   if (dyn == nullptr)
2934     return true;
2935
2936   *dyn = static_cast<const TyTy::DynamicObjectType *> (element);
2937   return true;
2938 }
2939
2940 void
2941 ReferenceType::accept_vis (TyVisitor &vis)
2942 {
2943   vis.visit (*this);
2944 }
2945
2946 void
2947 ReferenceType::accept_vis (TyConstVisitor &vis) const
2948 {
2949   vis.visit (*this);
2950 }
2951
2952 std::string
2953 ReferenceType::as_string () const
2954 {
2955   return std::string ("&") + (is_mutable () ? "mut" : "") + " "
2956          + get_base ()->as_string ();
2957 }
2958
2959 std::string
2960 ReferenceType::get_name () const
2961 {
2962   return std::string ("&") + (is_mutable () ? "mut" : "") + " "
2963          + get_base ()->get_name ();
2964 }
2965
2966 bool
2967 ReferenceType::can_eq (const BaseType *other, bool emit_errors) const
2968 {
2969   ReferenceCmp r (this, emit_errors);
2970   return r.can_eq (other);
2971 }
2972
2973 bool
2974 ReferenceType::is_equal (const BaseType &other) const
2975 {
2976   if (get_kind () != other.get_kind ())
2977     return false;
2978
2979   auto other2 = static_cast<const ReferenceType &> (other);
2980   if (mutability () != other2.mutability ())
2981     return false;
2982
2983   return get_base ()->is_equal (*other2.get_base ());
2984 }
2985
2986 BaseType *
2987 ReferenceType::get_base () const
2988 {
2989   return base.get_tyty ();
2990 }
2991
2992 const TyVar &
2993 ReferenceType::get_var_element_type () const
2994 {
2995   return base;
2996 }
2997
2998 BaseType *
2999 ReferenceType::clone () const
3000 {
3001   return new ReferenceType (get_ref (), get_ty_ref (), base, mutability (),
3002                             get_region (), get_combined_refs ());
3003 }
3004
3005 ReferenceType *
3006 ReferenceType::handle_substitions (SubstitutionArgumentMappings &mappings)
3007 {
3008   auto mappings_table = Analysis::Mappings::get ();
3009
3010   ReferenceType *ref = static_cast<ReferenceType *> (clone ());
3011   ref->set_ty_ref (mappings_table->get_next_hir_id ());
3012
3013   // might be &T or &ADT so this needs to be recursive
3014   auto base = ref->get_base ();
3015   BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
3016   ref->base = TyVar::subst_covariant_var (base, concrete);
3017
3018   return ref;
3019 }
3020
3021 // PointerType
3022
3023 PointerType::PointerType (HirId ref, TyVar base, Mutability mut,
3024                           std::set<HirId> refs)
3025   : BaseType (ref, ref, KIND,
3026               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3027               refs),
3028     base (base), mut (mut)
3029 {}
3030
3031 PointerType::PointerType (HirId ref, HirId ty_ref, TyVar base, Mutability mut,
3032                           std::set<HirId> refs)
3033   : BaseType (ref, ty_ref, KIND,
3034               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3035               refs),
3036     base (base), mut (mut)
3037 {}
3038
3039 Mutability
3040 PointerType::mutability () const
3041 {
3042   return mut;
3043 }
3044
3045 bool
3046 PointerType::is_mutable () const
3047 {
3048   return mut == Mutability::Mut;
3049 }
3050
3051 bool
3052 PointerType::is_const () const
3053 {
3054   return mut == Mutability::Imm;
3055 }
3056
3057 bool
3058 PointerType::is_dyn_object () const
3059 {
3060   return is_dyn_slice_type () || is_dyn_str_type () || is_dyn_obj_type ();
3061 }
3062
3063 bool
3064 PointerType::is_dyn_slice_type (const TyTy::SliceType **slice) const
3065 {
3066   const TyTy::BaseType *element = get_base ()->destructure ();
3067   if (element->get_kind () != TyTy::TypeKind::SLICE)
3068     return false;
3069   if (slice == nullptr)
3070     return true;
3071
3072   *slice = static_cast<const TyTy::SliceType *> (element);
3073   return true;
3074 }
3075
3076 bool
3077 PointerType::is_dyn_str_type (const TyTy::StrType **str) const
3078 {
3079   const TyTy::BaseType *element = get_base ()->destructure ();
3080   if (element->get_kind () != TyTy::TypeKind::STR)
3081     return false;
3082   if (str == nullptr)
3083     return true;
3084
3085   *str = static_cast<const TyTy::StrType *> (element);
3086   return true;
3087 }
3088
3089 bool
3090 PointerType::is_dyn_obj_type (const TyTy::DynamicObjectType **dyn) const
3091 {
3092   const TyTy::BaseType *element = get_base ()->destructure ();
3093   if (element->get_kind () != TyTy::TypeKind::DYNAMIC)
3094     return false;
3095   if (dyn == nullptr)
3096     return true;
3097
3098   *dyn = static_cast<const TyTy::DynamicObjectType *> (element);
3099   return true;
3100 }
3101
3102 void
3103 PointerType::accept_vis (TyVisitor &vis)
3104 {
3105   vis.visit (*this);
3106 }
3107
3108 void
3109 PointerType::accept_vis (TyConstVisitor &vis) const
3110 {
3111   vis.visit (*this);
3112 }
3113
3114 std::string
3115 PointerType::as_string () const
3116 {
3117   return std::string ("* ") + (is_mutable () ? "mut" : "const") + " "
3118          + get_base ()->as_string ();
3119 }
3120
3121 std::string
3122 PointerType::get_name () const
3123 {
3124   return std::string ("* ") + (is_mutable () ? "mut" : "const") + " "
3125          + get_base ()->get_name ();
3126 }
3127
3128 bool
3129 PointerType::can_eq (const BaseType *other, bool emit_errors) const
3130 {
3131   PointerCmp r (this, emit_errors);
3132   return r.can_eq (other);
3133 }
3134
3135 bool
3136 PointerType::is_equal (const BaseType &other) const
3137 {
3138   if (get_kind () != other.get_kind ())
3139     return false;
3140
3141   auto other2 = static_cast<const PointerType &> (other);
3142   if (mutability () != other2.mutability ())
3143     return false;
3144
3145   return get_base ()->is_equal (*other2.get_base ());
3146 }
3147
3148 BaseType *
3149 PointerType::get_base () const
3150 {
3151   return base.get_tyty ();
3152 }
3153
3154 const TyVar &
3155 PointerType::get_var_element_type () const
3156 {
3157   return base;
3158 }
3159
3160 BaseType *
3161 PointerType::clone () const
3162 {
3163   return new PointerType (get_ref (), get_ty_ref (), base, mutability (),
3164                           get_combined_refs ());
3165 }
3166
3167 PointerType *
3168 PointerType::handle_substitions (SubstitutionArgumentMappings &mappings)
3169 {
3170   auto mappings_table = Analysis::Mappings::get ();
3171
3172   PointerType *ref = static_cast<PointerType *> (clone ());
3173   ref->set_ty_ref (mappings_table->get_next_hir_id ());
3174
3175   // might be &T or &ADT so this needs to be recursive
3176   auto base = ref->get_base ();
3177   BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
3178   ref->base = TyVar::subst_covariant_var (base, concrete);
3179
3180   return ref;
3181 }
3182
3183 // PARAM Type
3184
3185 ParamType::ParamType (std::string symbol, location_t locus, HirId ref,
3186                       HIR::GenericParam &param,
3187                       std::vector<TypeBoundPredicate> specified_bounds,
3188                       std::set<HirId> refs)
3189   : BaseType (ref, ref, KIND,
3190               {Resolver::CanonicalPath::new_seg (UNKNOWN_NODEID, symbol),
3191                locus},
3192               specified_bounds, refs),
3193     is_trait_self (false), symbol (symbol), param (param)
3194 {}
3195
3196 ParamType::ParamType (bool is_trait_self, std::string symbol, location_t locus,
3197                       HirId ref, HirId ty_ref, HIR::GenericParam &param,
3198                       std::vector<TypeBoundPredicate> specified_bounds,
3199                       std::set<HirId> refs)
3200   : BaseType (ref, ty_ref, KIND,
3201               {Resolver::CanonicalPath::new_seg (UNKNOWN_NODEID, symbol),
3202                locus},
3203               specified_bounds, refs),
3204     is_trait_self (is_trait_self), symbol (symbol), param (param)
3205 {}
3206
3207 HIR::GenericParam &
3208 ParamType::get_generic_param ()
3209 {
3210   return param;
3211 }
3212
3213 bool
3214 ParamType::can_resolve () const
3215 {
3216   return get_ref () != get_ty_ref ();
3217 }
3218
3219 void
3220 ParamType::accept_vis (TyVisitor &vis)
3221 {
3222   vis.visit (*this);
3223 }
3224
3225 void
3226 ParamType::accept_vis (TyConstVisitor &vis) const
3227 {
3228   vis.visit (*this);
3229 }
3230
3231 std::string
3232 ParamType::as_string () const
3233 {
3234   if (!can_resolve ())
3235     {
3236       return get_symbol () + " REF: " + std::to_string (get_ref ());
3237     }
3238
3239   BaseType *lookup = resolve ();
3240   return get_symbol () + "=" + lookup->as_string ();
3241 }
3242
3243 std::string
3244 ParamType::get_name () const
3245 {
3246   if (!can_resolve ())
3247     return get_symbol ();
3248
3249   return destructure ()->get_name ();
3250 }
3251
3252 bool
3253 ParamType::can_eq (const BaseType *other, bool emit_errors) const
3254 {
3255   ParamCmp r (this, emit_errors);
3256   return r.can_eq (other);
3257 }
3258
3259 BaseType *
3260 ParamType::clone () const
3261 {
3262   return new ParamType (is_trait_self, get_symbol (), ident.locus, get_ref (),
3263                         get_ty_ref (), param, get_specified_bounds (),
3264                         get_combined_refs ());
3265 }
3266
3267 std::string
3268 ParamType::get_symbol () const
3269 {
3270   return symbol;
3271 }
3272
3273 BaseType *
3274 ParamType::resolve () const
3275 {
3276   TyVar var (get_ty_ref ());
3277   BaseType *r = var.get_tyty ();
3278
3279   while (r->get_kind () == TypeKind::PARAM)
3280     {
3281       ParamType *rr = static_cast<ParamType *> (r);
3282       if (!rr->can_resolve ())
3283         break;
3284
3285       TyVar v (rr->get_ty_ref ());
3286       BaseType *n = v.get_tyty ();
3287
3288       // fix infinite loop
3289       if (r == n)
3290         break;
3291
3292       r = n;
3293     }
3294
3295   if (r->get_kind () == TypeKind::PARAM && (r->get_ref () == r->get_ty_ref ()))
3296     return TyVar (r->get_ty_ref ()).get_tyty ();
3297
3298   return r;
3299 }
3300
3301 bool
3302 ParamType::is_equal (const BaseType &other) const
3303 {
3304   if (get_kind () != other.get_kind ())
3305     {
3306       if (!can_resolve ())
3307         return false;
3308
3309       return resolve ()->is_equal (other);
3310     }
3311
3312   auto other2 = static_cast<const ParamType &> (other);
3313   if (can_resolve () != other2.can_resolve ())
3314     return false;
3315
3316   if (can_resolve ())
3317     return resolve ()->can_eq (other2.resolve (), false);
3318
3319   return get_symbol ().compare (other2.get_symbol ()) == 0;
3320 }
3321
3322 ParamType *
3323 ParamType::handle_substitions (SubstitutionArgumentMappings &subst_mappings)
3324 {
3325   SubstitutionArg arg = SubstitutionArg::error ();
3326   bool ok = subst_mappings.get_argument_for_symbol (this, &arg);
3327   if (!ok || arg.is_error ())
3328     return this;
3329
3330   ParamType *p = static_cast<ParamType *> (clone ());
3331   subst_mappings.on_param_subst (*p, arg);
3332
3333   // there are two cases one where we substitute directly to a new PARAM and
3334   // otherwise
3335   if (arg.get_tyty ()->get_kind () == TyTy::TypeKind::PARAM)
3336     {
3337       p->set_ty_ref (arg.get_tyty ()->get_ref ());
3338       return p;
3339     }
3340
3341   // this is the new subst that this needs to pass
3342   p->set_ref (mappings->get_next_hir_id ());
3343   p->set_ty_ref (arg.get_tyty ()->get_ref ());
3344
3345   return p;
3346 }
3347
3348 void
3349 ParamType::set_implicit_self_trait ()
3350 {
3351   is_trait_self = true;
3352 }
3353
3354 bool
3355 ParamType::is_implicit_self_trait () const
3356 {
3357   return is_trait_self;
3358 }
3359
3360 // StrType
3361
3362 StrType::StrType (HirId ref, std::set<HirId> refs)
3363   : BaseType (ref, ref, KIND,
3364               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3365               refs)
3366 {}
3367
3368 StrType::StrType (HirId ref, HirId ty_ref, std::set<HirId> refs)
3369   : BaseType (ref, ty_ref, KIND,
3370               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3371               refs)
3372 {}
3373
3374 std::string
3375 StrType::get_name () const
3376 {
3377   return as_string ();
3378 }
3379
3380 BaseType *
3381 StrType::clone () const
3382 {
3383   return new StrType (get_ref (), get_ty_ref (), get_combined_refs ());
3384 }
3385
3386 void
3387 StrType::accept_vis (TyVisitor &vis)
3388 {
3389   vis.visit (*this);
3390 }
3391
3392 void
3393 StrType::accept_vis (TyConstVisitor &vis) const
3394 {
3395   vis.visit (*this);
3396 }
3397
3398 std::string
3399 StrType::as_string () const
3400 {
3401   return "str";
3402 }
3403
3404 bool
3405 StrType::can_eq (const BaseType *other, bool emit_errors) const
3406 {
3407   StrCmp r (this, emit_errors);
3408   return r.can_eq (other);
3409 }
3410
3411 bool
3412 StrType::is_equal (const BaseType &other) const
3413 {
3414   return get_kind () == other.get_kind ();
3415 }
3416
3417 // Never Type
3418
3419 NeverType::NeverType (HirId ref, std::set<HirId> refs)
3420   : BaseType (ref, ref, KIND,
3421               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3422               refs)
3423 {}
3424
3425 NeverType::NeverType (HirId ref, HirId ty_ref, std::set<HirId> refs)
3426   : BaseType (ref, ty_ref, KIND,
3427               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3428               refs)
3429 {}
3430
3431 std::string
3432 NeverType::get_name () const
3433 {
3434   return as_string ();
3435 }
3436
3437 void
3438 NeverType::accept_vis (TyVisitor &vis)
3439 {
3440   vis.visit (*this);
3441 }
3442
3443 void
3444 NeverType::accept_vis (TyConstVisitor &vis) const
3445 {
3446   vis.visit (*this);
3447 }
3448
3449 std::string
3450 NeverType::as_string () const
3451 {
3452   return "!";
3453 }
3454
3455 bool
3456 NeverType::can_eq (const BaseType *other, bool emit_errors) const
3457 {
3458   NeverCmp r (this, emit_errors);
3459   return r.can_eq (other);
3460 }
3461
3462 BaseType *
3463 NeverType::clone () const
3464 {
3465   return new NeverType (get_ref (), get_ty_ref (), get_combined_refs ());
3466 }
3467
3468 // placeholder type
3469
3470 PlaceholderType::PlaceholderType (std::string symbol, HirId ref,
3471                                   std::set<HirId> refs)
3472   : BaseType (ref, ref, KIND,
3473               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3474               refs),
3475     symbol (symbol)
3476 {}
3477
3478 PlaceholderType::PlaceholderType (std::string symbol, HirId ref, HirId ty_ref,
3479                                   std::set<HirId> refs)
3480   : BaseType (ref, ty_ref, KIND,
3481               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3482               refs),
3483     symbol (symbol)
3484 {}
3485
3486 std::string
3487 PlaceholderType::get_name () const
3488 {
3489   return as_string ();
3490 }
3491
3492 std::string
3493 PlaceholderType::get_symbol () const
3494 {
3495   return symbol;
3496 }
3497
3498 void
3499 PlaceholderType::accept_vis (TyVisitor &vis)
3500 {
3501   vis.visit (*this);
3502 }
3503
3504 void
3505 PlaceholderType::accept_vis (TyConstVisitor &vis) const
3506 {
3507   vis.visit (*this);
3508 }
3509
3510 std::string
3511 PlaceholderType::as_string () const
3512 {
3513   return "<placeholder:" + (can_resolve () ? resolve ()->as_string () : "")
3514          + ">";
3515 }
3516
3517 bool
3518 PlaceholderType::can_eq (const BaseType *other, bool emit_errors) const
3519 {
3520   PlaceholderCmp r (this, emit_errors);
3521   return r.can_eq (other);
3522 }
3523
3524 BaseType *
3525 PlaceholderType::clone () const
3526 {
3527   return new PlaceholderType (get_symbol (), get_ref (), get_ty_ref (),
3528                               get_combined_refs ());
3529 }
3530
3531 void
3532 PlaceholderType::set_associated_type (HirId ref)
3533 {
3534   auto context = Resolver::TypeCheckContext::get ();
3535   context->insert_associated_type_mapping (get_ty_ref (), ref);
3536 }
3537
3538 void
3539 PlaceholderType::clear_associated_type ()
3540 {
3541   auto context = Resolver::TypeCheckContext::get ();
3542   context->clear_associated_type_mapping (get_ty_ref ());
3543 }
3544
3545 bool
3546 PlaceholderType::can_resolve () const
3547 {
3548   auto context = Resolver::TypeCheckContext::get ();
3549   return context->lookup_associated_type_mapping (get_ty_ref (), nullptr);
3550 }
3551
3552 BaseType *
3553 PlaceholderType::resolve () const
3554 {
3555   auto context = Resolver::TypeCheckContext::get ();
3556
3557   HirId mapping;
3558   bool ok = context->lookup_associated_type_mapping (get_ty_ref (), &mapping);
3559   rust_assert (ok);
3560
3561   return TyVar (mapping).get_tyty ();
3562 }
3563
3564 bool
3565 PlaceholderType::is_equal (const BaseType &other) const
3566 {
3567   if (get_kind () != other.get_kind ())
3568     {
3569       if (!can_resolve ())
3570         return false;
3571
3572       return resolve ()->is_equal (other);
3573     }
3574
3575   auto other2 = static_cast<const PlaceholderType &> (other);
3576   return get_symbol ().compare (other2.get_symbol ()) == 0;
3577 }
3578
3579 // Projection type
3580
3581 ProjectionType::ProjectionType (
3582   HirId ref, BaseType *base, const Resolver::TraitReference *trait, DefId item,
3583   std::vector<SubstitutionParamMapping> subst_refs,
3584   SubstitutionArgumentMappings generic_arguments,
3585   RegionConstraints region_constraints, std::set<HirId> refs)
3586   : BaseType (ref, ref, KIND,
3587               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3588               std::move (refs)),
3589     SubstitutionRef (std::move (subst_refs), std::move (generic_arguments),
3590                      std::move (region_constraints)),
3591     base (base), trait (trait), item (item)
3592 {}
3593
3594 ProjectionType::ProjectionType (
3595   HirId ref, HirId ty_ref, BaseType *base,
3596   const Resolver::TraitReference *trait, DefId item,
3597   std::vector<SubstitutionParamMapping> subst_refs,
3598   SubstitutionArgumentMappings generic_arguments,
3599   RegionConstraints region_constraints, std::set<HirId> refs)
3600   : BaseType (ref, ty_ref, KIND,
3601               {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
3602               refs),
3603     SubstitutionRef (std::move (subst_refs), std::move (generic_arguments),
3604                      std::move (region_constraints)),
3605     base (base), trait (trait), item (item)
3606 {}
3607
3608 std::string
3609 ProjectionType::get_name () const
3610 {
3611   return as_string ();
3612 }
3613
3614 const BaseType *
3615 ProjectionType::get () const
3616 {
3617   return base;
3618 }
3619
3620 BaseType *
3621 ProjectionType::get ()
3622 {
3623   return base;
3624 }
3625
3626 void
3627 ProjectionType::accept_vis (TyVisitor &vis)
3628 {
3629   vis.visit (*this);
3630 }
3631
3632 void
3633 ProjectionType::accept_vis (TyConstVisitor &vis) const
3634 {
3635   vis.visit (*this);
3636 }
3637
3638 std::string
3639 ProjectionType::as_string () const
3640 {
3641   return "<Projection=" + subst_as_string () + "::" + base->as_string () + ">";
3642 }
3643
3644 bool
3645 ProjectionType::can_eq (const BaseType *other, bool emit_errors) const
3646 {
3647   return base->can_eq (other, emit_errors);
3648 }
3649
3650 BaseType *
3651 ProjectionType::clone () const
3652 {
3653   return new ProjectionType (get_ref (), get_ty_ref (), base->clone (), trait,
3654                              item, clone_substs (), used_arguments,
3655                              region_constraints, get_combined_refs ());
3656 }
3657
3658 ProjectionType *
3659 ProjectionType::handle_substitions (
3660   SubstitutionArgumentMappings &subst_mappings)
3661 {
3662   // // do we really need to substitute this?
3663   // if (base->needs_generic_substitutions () ||
3664   // base->contains_type_parameters
3665   // ())
3666   //   {
3667   //     return this;
3668   //   }
3669
3670   ProjectionType *projection = static_cast<ProjectionType *> (clone ());
3671   projection->set_ty_ref (mappings->get_next_hir_id ());
3672   projection->used_arguments = subst_mappings;
3673
3674   auto context = Resolver::TypeCheckContext::get ();
3675   context->insert_implicit_type (projection->get_ty_ref (), projection);
3676
3677   for (auto &sub : projection->get_substs ())
3678     {
3679       SubstitutionArg arg = SubstitutionArg::error ();
3680       bool ok
3681         = subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
3682       if (ok)
3683         sub.fill_param_ty (subst_mappings, subst_mappings.get_locus ());
3684     }
3685
3686   auto fty = projection->base;
3687   bool is_param_ty = fty->get_kind () == TypeKind::PARAM;
3688   if (is_param_ty)
3689     {
3690       ParamType *p = static_cast<ParamType *> (fty);
3691
3692       SubstitutionArg arg = SubstitutionArg::error ();
3693       bool ok = subst_mappings.get_argument_for_symbol (p, &arg);
3694       if (ok)
3695         {
3696           auto argt = arg.get_tyty ();
3697           bool arg_is_param = argt->get_kind () == TyTy::TypeKind::PARAM;
3698           bool arg_is_concrete = argt->get_kind () != TyTy::TypeKind::INFER;
3699
3700           if (arg_is_param || arg_is_concrete)
3701             {
3702               auto new_field = argt->clone ();
3703               new_field->set_ref (fty->get_ref ());
3704               projection->base = new_field;
3705             }
3706           else
3707             {
3708               fty->set_ty_ref (argt->get_ref ());
3709             }
3710         }
3711     }
3712   else if (fty->needs_generic_substitutions () || !fty->is_concrete ())
3713     {
3714       BaseType *concrete
3715         = Resolver::SubstMapperInternal::Resolve (fty, subst_mappings);
3716
3717       if (concrete == nullptr || concrete->get_kind () == TyTy::TypeKind::ERROR)
3718         {
3719           rust_error_at (subst_mappings.get_locus (),
3720                          "Failed to resolve field substitution type: %s",
3721                          fty->as_string ().c_str ());
3722           return nullptr;
3723         }
3724
3725       projection->base = concrete;
3726     }
3727
3728   return projection;
3729 }
3730
3731 // DynObjectType
3732
3733 DynamicObjectType::DynamicObjectType (
3734   HirId ref, RustIdent ident, std::vector<TypeBoundPredicate> specified_bounds,
3735   std::set<HirId> refs)
3736   : BaseType (ref, ref, KIND, ident, specified_bounds, refs)
3737 {}
3738
3739 DynamicObjectType::DynamicObjectType (
3740   HirId ref, HirId ty_ref, RustIdent ident,
3741   std::vector<TypeBoundPredicate> specified_bounds, std::set<HirId> refs)
3742   : BaseType (ref, ty_ref, KIND, ident, specified_bounds, refs)
3743 {}
3744
3745 void
3746 DynamicObjectType::accept_vis (TyVisitor &vis)
3747 {
3748   vis.visit (*this);
3749 }
3750
3751 void
3752 DynamicObjectType::accept_vis (TyConstVisitor &vis) const
3753 {
3754   vis.visit (*this);
3755 }
3756
3757 std::string
3758 DynamicObjectType::as_string () const
3759 {
3760   return "dyn [" + raw_bounds_as_string () + "]";
3761 }
3762
3763 bool
3764 DynamicObjectType::can_eq (const BaseType *other, bool emit_errors) const
3765 {
3766   DynamicCmp r (this, emit_errors);
3767   return r.can_eq (other);
3768 }
3769
3770 BaseType *
3771 DynamicObjectType::clone () const
3772 {
3773   return new DynamicObjectType (get_ref (), get_ty_ref (), ident,
3774                                 specified_bounds, get_combined_refs ());
3775 }
3776
3777 std::string
3778 DynamicObjectType::get_name () const
3779 {
3780   return "dyn [" + raw_bounds_as_name () + "]";
3781 }
3782
3783 bool
3784 DynamicObjectType::is_equal (const BaseType &other) const
3785 {
3786   if (get_kind () != other.get_kind ())
3787     return false;
3788
3789   if (num_specified_bounds () != other.num_specified_bounds ())
3790     return false;
3791
3792   return bounds_compatible (other, UNDEF_LOCATION, false);
3793 }
3794
3795 const std::vector<
3796   std::pair<const Resolver::TraitItemReference *, const TypeBoundPredicate *>>
3797 DynamicObjectType::get_object_items () const
3798 {
3799   std::vector<
3800     std::pair<const Resolver::TraitItemReference *, const TypeBoundPredicate *>>
3801     items;
3802   for (auto &bound : get_specified_bounds ())
3803     {
3804       const Resolver::TraitReference *trait = bound.get ();
3805       std::vector<const Resolver::TraitItemReference *> trait_items;
3806       trait->get_trait_items_and_supers (trait_items);
3807
3808       for (auto &item : trait_items)
3809         {
3810           if (item->get_trait_item_type ()
3811                 == Resolver::TraitItemReference::TraitItemType::FN
3812               && item->is_object_safe ())
3813             items.push_back ({item, &bound});
3814         }
3815     }
3816   return items;
3817 }
3818
3819 } // namespace TyTy
3820 } // namespace Rust