gcc/rust/typecheck/rust-tyty-subst.cc

   1 // Copyright (C) 2020-2022 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-subst.h"
  20 #include "rust-hir-full.h"
  21 #include "rust-tyty.h"
  22 #include "rust-hir-type-check.h"
  23 #include "rust-substitution-mapper.h"
  24 #include "rust-hir-type-check-type.h"
  25
  26 namespace Rust {
  27 namespace TyTy {
  28
  29 SubstitutionParamMapping::SubstitutionParamMapping (
  30   const HIR::TypeParam &generic, ParamType *param)
  31   : generic (generic), param (param)
  32 {}
  33
  34 SubstitutionParamMapping::SubstitutionParamMapping (
  35   const SubstitutionParamMapping &other)
  36   : generic (other.generic), param (other.param)
  37 {}
  38
  39 std::string
  40 SubstitutionParamMapping::as_string () const
  41 {
  42   if (param == nullptr)
  43     return "nullptr";
  44
  45   return param->get_name ();
  46 }
  47
  48 SubstitutionParamMapping
  49 SubstitutionParamMapping::clone () const
  50 {
  51   return SubstitutionParamMapping (generic,
  52                                    static_cast<ParamType *> (param->clone ()));
  53 }
  54
  55 ParamType *
  56 SubstitutionParamMapping::get_param_ty ()
  57 {
  58   return param;
  59 }
  60
  61 const ParamType *
  62 SubstitutionParamMapping::get_param_ty () const
  63 {
  64   return param;
  65 }
  66
  67 const HIR::TypeParam &
  68 SubstitutionParamMapping::get_generic_param ()
  69 {
  70   return generic;
  71 }
  72
  73 bool
  74 SubstitutionParamMapping::needs_substitution () const
  75 {
  76   return !(get_param_ty ()->is_concrete ());
  77 }
  78
  79 Location
  80 SubstitutionParamMapping::get_param_locus () const
  81 {
  82   return generic.get_locus ();
  83 }
  84
  85 bool
  86 SubstitutionParamMapping::param_has_default_ty () const
  87 {
  88   return generic.has_type ();
  89 }
  90
  91 BaseType *
  92 SubstitutionParamMapping::get_default_ty () const
  93 {
  94   TyVar var (generic.get_type_mappings ().get_hirid ());
  95   return var.get_tyty ();
  96 }
  97
  98 bool
  99 SubstitutionParamMapping::need_substitution () const
 100 {
 101   if (!param->can_resolve ())
 102     return true;
 103
 104   auto resolved = param->resolve ();
 105   return !resolved->is_concrete ();
 106 }
 107
 108 bool
 109 SubstitutionParamMapping::fill_param_ty (
 110   SubstitutionArgumentMappings &subst_mappings, Location locus)
 111 {
 112   SubstitutionArg arg = SubstitutionArg::error ();
 113   bool ok = subst_mappings.get_argument_for_symbol (get_param_ty (), &arg);
 114   if (!ok)
 115     return true;
 116
 117   TyTy::BaseType &type = *arg.get_tyty ();
 118   if (type.get_kind () == TyTy::TypeKind::INFER)
 119     {
 120       type.inherit_bounds (*param);
 121     }
 122   else
 123     {
 124       if (!param->bounds_compatible (type, locus, true))
 125         return false;
 126     }
 127
 128   if (type.get_kind () == TypeKind::PARAM)
 129     {
 130       // delete param;
 131       param = static_cast<ParamType *> (type.clone ());
 132     }
 133   else
 134     {
 135       // check the substitution is compatible with bounds
 136       if (!param->bounds_compatible (type, locus, true))
 137         return false;
 138
 139       // recursively pass this down to all HRTB's
 140       for (auto &bound : param->get_specified_bounds ())
 141         bound.handle_substitions (subst_mappings);
 142
 143       param->set_ty_ref (type.get_ref ());
 144     }
 145
 146   return true;
 147 }
 148
 149 void
 150 SubstitutionParamMapping::override_context ()
 151 {
 152   if (!param->can_resolve ())
 153     return;
 154
 155   auto mappings = Analysis::Mappings::get ();
 156   auto context = Resolver::TypeCheckContext::get ();
 157
 158   context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
 159                                                UNKNOWN_NODEID,
 160                                                param->get_ref (),
 161                                                UNKNOWN_LOCAL_DEFID),
 162                         param->resolve ());
 163 }
 164
 165 SubstitutionArg::SubstitutionArg (const SubstitutionParamMapping *param,
 166                                   BaseType *argument)
 167   : param (param), argument (argument)
 168 {}
 169
 170 SubstitutionArg::SubstitutionArg (const SubstitutionArg &other)
 171   : param (other.param), argument (other.argument)
 172 {}
 173
 174 SubstitutionArg &
 175 SubstitutionArg::operator= (const SubstitutionArg &other)
 176 {
 177   param = other.param;
 178   argument = other.argument;
 179   return *this;
 180 }
 181
 182 BaseType *
 183 SubstitutionArg::get_tyty ()
 184 {
 185   return argument;
 186 }
 187
 188 const BaseType *
 189 SubstitutionArg::get_tyty () const
 190 {
 191   return argument;
 192 }
 193
 194 const SubstitutionParamMapping *
 195 SubstitutionArg::get_param_mapping () const
 196 {
 197   return param;
 198 }
 199
 200 SubstitutionArg
 201 SubstitutionArg::error ()
 202 {
 203   return SubstitutionArg (nullptr, nullptr);
 204 }
 205
 206 bool
 207 SubstitutionArg::is_error () const
 208 {
 209   return param == nullptr || argument == nullptr;
 210 }
 211
 212 bool
 213 SubstitutionArg::is_conrete () const
 214 {
 215   if (argument != nullptr)
 216     return true;
 217
 218   if (argument->get_kind () == TyTy::TypeKind::PARAM)
 219     return false;
 220
 221   return argument->is_concrete ();
 222 }
 223
 224 std::string
 225 SubstitutionArg::as_string () const
 226 {
 227   return param->as_string ()
 228          + (argument != nullptr ? ":" + argument->as_string () : "");
 229 }
 230
 231 // SubstitutionArgumentMappings
 232
 233 SubstitutionArgumentMappings::SubstitutionArgumentMappings (
 234   std::vector<SubstitutionArg> mappings,
 235   std::map<std::string, BaseType *> binding_args, Location locus,
 236   ParamSubstCb param_subst_cb, bool trait_item_flag)
 237   : mappings (mappings), binding_args (binding_args), locus (locus),
 238     param_subst_cb (param_subst_cb), trait_item_flag (trait_item_flag)
 239 {}
 240
 241 SubstitutionArgumentMappings::SubstitutionArgumentMappings (
 242   const SubstitutionArgumentMappings &other)
 243   : mappings (other.mappings), binding_args (other.binding_args),
 244     locus (other.locus), param_subst_cb (nullptr),
 245     trait_item_flag (other.trait_item_flag)
 246 {}
 247
 248 SubstitutionArgumentMappings &
 249 SubstitutionArgumentMappings::operator= (
 250   const SubstitutionArgumentMappings &other)
 251 {
 252   mappings = other.mappings;
 253   binding_args = other.binding_args;
 254   locus = other.locus;
 255   param_subst_cb = nullptr;
 256   trait_item_flag = other.trait_item_flag;
 257
 258   return *this;
 259 }
 260
 261 SubstitutionArgumentMappings
 262 SubstitutionArgumentMappings::error ()
 263 {
 264   return SubstitutionArgumentMappings ({}, {}, Location (), nullptr, false);
 265 }
 266
 267 bool
 268 SubstitutionArgumentMappings::is_error () const
 269 {
 270   return mappings.size () == 0;
 271 }
 272
 273 bool
 274 SubstitutionArgumentMappings::get_argument_for_symbol (
 275   const ParamType *param_to_find, SubstitutionArg *argument)
 276 {
 277   for (auto &mapping : mappings)
 278     {
 279       const SubstitutionParamMapping *param = mapping.get_param_mapping ();
 280       const ParamType *p = param->get_param_ty ();
 281
 282       if (p->get_symbol ().compare (param_to_find->get_symbol ()) == 0)
 283         {
 284           *argument = mapping;
 285           return true;
 286         }
 287     }
 288   return false;
 289 }
 290
 291 bool
 292 SubstitutionArgumentMappings::get_argument_at (size_t index,
 293                                                SubstitutionArg *argument)
 294 {
 295   if (index > mappings.size ())
 296     return false;
 297
 298   *argument = mappings.at (index);
 299   return true;
 300 }
 301
 302 bool
 303 SubstitutionArgumentMappings::is_concrete () const
 304 {
 305   for (auto &mapping : mappings)
 306     {
 307       if (!mapping.is_conrete ())
 308         return false;
 309     }
 310   return true;
 311 }
 312
 313 Location
 314 SubstitutionArgumentMappings::get_locus () const
 315 {
 316   return locus;
 317 }
 318
 319 size_t
 320 SubstitutionArgumentMappings::size () const
 321 {
 322   return mappings.size ();
 323 }
 324
 325 bool
 326 SubstitutionArgumentMappings::is_empty () const
 327 {
 328   return size () == 0;
 329 }
 330
 331 std::vector<SubstitutionArg> &
 332 SubstitutionArgumentMappings::get_mappings ()
 333 {
 334   return mappings;
 335 }
 336
 337 const std::vector<SubstitutionArg> &
 338 SubstitutionArgumentMappings::get_mappings () const
 339 {
 340   return mappings;
 341 }
 342
 343 std::map<std::string, BaseType *> &
 344 SubstitutionArgumentMappings::get_binding_args ()
 345 {
 346   return binding_args;
 347 }
 348
 349 const std::map<std::string, BaseType *> &
 350 SubstitutionArgumentMappings::get_binding_args () const
 351 {
 352   return binding_args;
 353 }
 354
 355 std::string
 356 SubstitutionArgumentMappings::as_string () const
 357 {
 358   std::string buffer;
 359   for (auto &mapping : mappings)
 360     {
 361       buffer += mapping.as_string () + ", ";
 362     }
 363   return "<" + buffer + ">";
 364 }
 365
 366 void
 367 SubstitutionArgumentMappings::on_param_subst (const ParamType &p,
 368                                               const SubstitutionArg &a) const
 369 {
 370   if (param_subst_cb == nullptr)
 371     return;
 372
 373   param_subst_cb (p, a);
 374 }
 375
 376 ParamSubstCb
 377 SubstitutionArgumentMappings::get_subst_cb () const
 378 {
 379   return param_subst_cb;
 380 }
 381
 382 bool
 383 SubstitutionArgumentMappings::trait_item_mode () const
 384 {
 385   return trait_item_flag;
 386 }
 387
 388 // SubstitutionRef
 389
 390 SubstitutionRef::SubstitutionRef (
 391   std::vector<SubstitutionParamMapping> substitutions,
 392   SubstitutionArgumentMappings arguments)
 393   : substitutions (substitutions), used_arguments (arguments)
 394 {}
 395
 396 bool
 397 SubstitutionRef::has_substitutions () const
 398 {
 399   return substitutions.size () > 0;
 400 }
 401
 402 std::string
 403 SubstitutionRef::subst_as_string () const
 404 {
 405   std::string buffer;
 406   for (size_t i = 0; i < substitutions.size (); i++)
 407     {
 408       const SubstitutionParamMapping &sub = substitutions.at (i);
 409       buffer += sub.as_string ();
 410
 411       if ((i + 1) < substitutions.size ())
 412         buffer += ", ";
 413     }
 414
 415   return buffer.empty () ? "" : "<" + buffer + ">";
 416 }
 417
 418 bool
 419 SubstitutionRef::supports_associated_bindings () const
 420 {
 421   return get_num_associated_bindings () > 0;
 422 }
 423
 424 size_t
 425 SubstitutionRef::get_num_associated_bindings () const
 426 {
 427   return 0;
 428 }
 429
 430 TypeBoundPredicateItem
 431 SubstitutionRef::lookup_associated_type (const std::string &search)
 432 {
 433   return TypeBoundPredicateItem::error ();
 434 }
 435
 436 size_t
 437 SubstitutionRef::get_num_substitutions () const
 438 {
 439   return substitutions.size ();
 440 }
 441
 442 std::vector<SubstitutionParamMapping> &
 443 SubstitutionRef::get_substs ()
 444 {
 445   return substitutions;
 446 }
 447
 448 const std::vector<SubstitutionParamMapping> &
 449 SubstitutionRef::get_substs () const
 450 {
 451   return substitutions;
 452 }
 453
 454 std::vector<SubstitutionParamMapping>
 455 SubstitutionRef::clone_substs () const
 456 {
 457   std::vector<SubstitutionParamMapping> clone;
 458
 459   for (auto &sub : substitutions)
 460     clone.push_back (sub.clone ());
 461
 462   return clone;
 463 }
 464
 465 void
 466 SubstitutionRef::override_context ()
 467 {
 468   for (auto &sub : substitutions)
 469     {
 470       sub.override_context ();
 471     }
 472 }
 473
 474 bool
 475 SubstitutionRef::needs_substitution () const
 476 {
 477   for (auto &sub : substitutions)
 478     {
 479       if (sub.need_substitution ())
 480         return true;
 481     }
 482   return false;
 483 }
 484
 485 bool
 486 SubstitutionRef::was_substituted () const
 487 {
 488   return !needs_substitution ();
 489 }
 490
 491 SubstitutionArgumentMappings &
 492 SubstitutionRef::get_substitution_arguments ()
 493 {
 494   return used_arguments;
 495 }
 496
 497 const SubstitutionArgumentMappings &
 498 SubstitutionRef::get_substitution_arguments () const
 499 {
 500   return used_arguments;
 501 }
 502
 503 size_t
 504 SubstitutionRef::num_required_substitutions () const
 505 {
 506   size_t n = 0;
 507   for (auto &p : substitutions)
 508     {
 509       if (p.needs_substitution ())
 510         n++;
 511     }
 512   return n;
 513 }
 514
 515 size_t
 516 SubstitutionRef::min_required_substitutions () const
 517 {
 518   size_t n = 0;
 519   for (auto &p : substitutions)
 520     {
 521       if (p.needs_substitution () && !p.param_has_default_ty ())
 522         n++;
 523     }
 524   return n;
 525 }
 526
 527 SubstitutionArgumentMappings
 528 SubstitutionRef::get_used_arguments () const
 529 {
 530   return used_arguments;
 531 }
 532
 533 SubstitutionArgumentMappings
 534 SubstitutionRef::get_mappings_from_generic_args (HIR::GenericArgs &args)
 535 {
 536   std::map<std::string, BaseType *> binding_arguments;
 537   if (args.get_binding_args ().size () > 0)
 538     {
 539       if (supports_associated_bindings ())
 540         {
 541           if (args.get_binding_args ().size () > get_num_associated_bindings ())
 542             {
 543               RichLocation r (args.get_locus ());
 544
 545               rust_error_at (r,
 546                              "generic item takes at most %lu type binding "
 547                              "arguments but %lu were supplied",
 548                              (unsigned long) get_num_associated_bindings (),
 549                              (unsigned long) args.get_binding_args ().size ());
 550               return SubstitutionArgumentMappings::error ();
 551             }
 552
 553           for (auto &binding : args.get_binding_args ())
 554             {
 555               BaseType *resolved
 556                 = Resolver::TypeCheckType::Resolve (binding.get_type ().get ());
 557               if (resolved == nullptr
 558                   || resolved->get_kind () == TyTy::TypeKind::ERROR)
 559                 {
 560                   rust_error_at (binding.get_locus (),
 561                                  "failed to resolve type arguments");
 562                   return SubstitutionArgumentMappings::error ();
 563                 }
 564
 565               // resolve to relevant binding
 566               auto binding_item
 567                 = lookup_associated_type (binding.get_identifier ());
 568               if (binding_item.is_error ())
 569                 {
 570                   rust_error_at (binding.get_locus (),
 571                                  "unknown associated type binding: %s",
 572                                  binding.get_identifier ().c_str ());
 573                   return SubstitutionArgumentMappings::error ();
 574                 }
 575
 576               binding_arguments[binding.get_identifier ()] = resolved;
 577             }
 578         }
 579       else
 580         {
 581           RichLocation r (args.get_locus ());
 582           for (auto &binding : args.get_binding_args ())
 583             r.add_range (binding.get_locus ());
 584
 585           rust_error_at (r, "associated type bindings are not allowed here");
 586           return SubstitutionArgumentMappings::error ();
 587         }
 588     }
 589
 590   // for inherited arguments
 591   size_t offs = used_arguments.size ();
 592   if (args.get_type_args ().size () + offs > substitutions.size ())
 593     {
 594       RichLocation r (args.get_locus ());
 595       r.add_range (substitutions.front ().get_param_locus ());
 596
 597       rust_error_at (
 598         r,
 599         "generic item takes at most %lu type arguments but %lu were supplied",
 600         (unsigned long) substitutions.size (),
 601         (unsigned long) args.get_type_args ().size ());
 602       return SubstitutionArgumentMappings::error ();
 603     }
 604
 605   if (args.get_type_args ().size () + offs < min_required_substitutions ())
 606     {
 607       RichLocation r (args.get_locus ());
 608       r.add_range (substitutions.front ().get_param_locus ());
 609
 610       rust_error_at (
 611         r,
 612         "generic item takes at least %lu type arguments but %lu were supplied",
 613         (unsigned long) (min_required_substitutions () - offs),
 614         (unsigned long) args.get_type_args ().size ());
 615       return SubstitutionArgumentMappings::error ();
 616     }
 617
 618   std::vector<SubstitutionArg> mappings = used_arguments.get_mappings ();
 619   for (auto &arg : args.get_type_args ())
 620     {
 621       BaseType *resolved = Resolver::TypeCheckType::Resolve (arg.get ());
 622       if (resolved == nullptr || resolved->get_kind () == TyTy::TypeKind::ERROR)
 623         {
 624           rust_error_at (args.get_locus (), "failed to resolve type arguments");
 625           return SubstitutionArgumentMappings::error ();
 626         }
 627
 628       SubstitutionArg subst_arg (&substitutions.at (offs), resolved);
 629       offs++;
 630       mappings.push_back (std::move (subst_arg));
 631     }
 632
 633   // we must need to fill out defaults
 634   size_t left_over
 635     = num_required_substitutions () - min_required_substitutions ();
 636   if (left_over > 0)
 637     {
 638       for (size_t offs = mappings.size (); offs < substitutions.size (); offs++)
 639         {
 640           SubstitutionParamMapping &param = substitutions.at (offs);
 641           rust_assert (param.param_has_default_ty ());
 642
 643           BaseType *resolved = param.get_default_ty ();
 644           if (resolved->get_kind () == TypeKind::ERROR)
 645             return SubstitutionArgumentMappings::error ();
 646
 647           // this resolved default might already contain default parameters
 648           if (resolved->contains_type_parameters ())
 649             {
 650               SubstitutionArgumentMappings intermediate (mappings,
 651                                                          binding_arguments,
 652                                                          args.get_locus ());
 653               resolved = Resolver::SubstMapperInternal::Resolve (resolved,
 654                                                                  intermediate);
 655
 656               if (resolved->get_kind () == TypeKind::ERROR)
 657                 return SubstitutionArgumentMappings::error ();
 658             }
 659
 660           SubstitutionArg subst_arg (&param, resolved);
 661           mappings.push_back (std::move (subst_arg));
 662         }
 663     }
 664
 665   return SubstitutionArgumentMappings (mappings, binding_arguments,
 666                                        args.get_locus ());
 667 }
 668
 669 BaseType *
 670 SubstitutionRef::infer_substitions (Location locus)
 671 {
 672   std::vector<SubstitutionArg> args;
 673   std::map<std::string, BaseType *> argument_mappings;
 674   for (auto &p : get_substs ())
 675     {
 676       if (p.needs_substitution ())
 677         {
 678           const std::string &symbol = p.get_param_ty ()->get_symbol ();
 679           auto it = argument_mappings.find (symbol);
 680           bool have_mapping = it != argument_mappings.end ();
 681
 682           if (have_mapping)
 683             {
 684               args.push_back (SubstitutionArg (&p, it->second));
 685             }
 686           else
 687             {
 688               TyVar infer_var = TyVar::get_implicit_infer_var (locus);
 689               args.push_back (SubstitutionArg (&p, infer_var.get_tyty ()));
 690               argument_mappings[symbol] = infer_var.get_tyty ();
 691             }
 692         }
 693       else
 694         {
 695           args.push_back (SubstitutionArg (&p, p.get_param_ty ()->resolve ()));
 696         }
 697     }
 698
 699   // FIXME do we need to add inference variables to all the possible bindings?
 700   // it might just lead to inference variable hell not 100% sure if rustc does
 701   // this i think the language might needs this to be explicitly set
 702
 703   SubstitutionArgumentMappings infer_arguments (std::move (args),
 704                                                 {} /* binding_arguments */,
 705                                                 locus);
 706   return handle_substitions (infer_arguments);
 707 }
 708
 709 SubstitutionArgumentMappings
 710 SubstitutionRef::adjust_mappings_for_this (
 711   SubstitutionArgumentMappings &mappings)
 712 {
 713   std::vector<SubstitutionArg> resolved_mappings;
 714   for (size_t i = 0; i < substitutions.size (); i++)
 715     {
 716       auto &subst = substitutions.at (i);
 717
 718       SubstitutionArg arg = SubstitutionArg::error ();
 719       if (mappings.size () == substitutions.size ())
 720         {
 721           mappings.get_argument_at (i, &arg);
 722         }
 723       else
 724         {
 725           if (subst.needs_substitution ())
 726             {
 727               // get from passed in mappings
 728               mappings.get_argument_for_symbol (subst.get_param_ty (), &arg);
 729             }
 730           else
 731             {
 732               // we should already have this somewhere
 733               used_arguments.get_argument_for_symbol (subst.get_param_ty (),
 734                                                       &arg);
 735             }
 736         }
 737
 738       bool ok = !arg.is_error ();
 739       if (ok)
 740         {
 741           SubstitutionArg adjusted (&subst, arg.get_tyty ());
 742           resolved_mappings.push_back (std::move (adjusted));
 743         }
 744     }
 745
 746   if (resolved_mappings.empty ())
 747     return SubstitutionArgumentMappings::error ();
 748
 749   return SubstitutionArgumentMappings (resolved_mappings,
 750                                        mappings.get_binding_args (),
 751                                        mappings.get_locus (),
 752                                        mappings.get_subst_cb (),
 753                                        mappings.trait_item_mode ());
 754 }
 755
 756 bool
 757 SubstitutionRef::are_mappings_bound (SubstitutionArgumentMappings &mappings)
 758 {
 759   std::vector<SubstitutionArg> resolved_mappings;
 760   for (size_t i = 0; i < substitutions.size (); i++)
 761     {
 762       auto &subst = substitutions.at (i);
 763
 764       SubstitutionArg arg = SubstitutionArg::error ();
 765       if (mappings.size () == substitutions.size ())
 766         {
 767           mappings.get_argument_at (i, &arg);
 768         }
 769       else
 770         {
 771           if (subst.needs_substitution ())
 772             {
 773               // get from passed in mappings
 774               mappings.get_argument_for_symbol (subst.get_param_ty (), &arg);
 775             }
 776           else
 777             {
 778               // we should already have this somewhere
 779               used_arguments.get_argument_for_symbol (subst.get_param_ty (),
 780                                                       &arg);
 781             }
 782         }
 783
 784       bool ok = !arg.is_error ();
 785       if (ok)
 786         {
 787           SubstitutionArg adjusted (&subst, arg.get_tyty ());
 788           resolved_mappings.push_back (std::move (adjusted));
 789         }
 790     }
 791
 792   return !resolved_mappings.empty ();
 793 }
 794
 795 // this function assumes that the mappings being passed are for the same type as
 796 // this new substitution reference so ordering matters here
 797 SubstitutionArgumentMappings
 798 SubstitutionRef::solve_mappings_from_receiver_for_self (
 799   SubstitutionArgumentMappings &mappings) const
 800 {
 801   std::vector<SubstitutionArg> resolved_mappings;
 802
 803   rust_assert (mappings.size () == get_num_substitutions ());
 804   for (size_t i = 0; i < get_num_substitutions (); i++)
 805     {
 806       const SubstitutionParamMapping &param_mapping = substitutions.at (i);
 807       SubstitutionArg &arg = mappings.get_mappings ().at (i);
 808
 809       if (param_mapping.needs_substitution ())
 810         {
 811           SubstitutionArg adjusted (&param_mapping, arg.get_tyty ());
 812           resolved_mappings.push_back (std::move (adjusted));
 813         }
 814     }
 815
 816   return SubstitutionArgumentMappings (resolved_mappings,
 817                                        mappings.get_binding_args (),
 818                                        mappings.get_locus ());
 819 }
 820
 821 SubstitutionArgumentMappings
 822 SubstitutionRef::solve_missing_mappings_from_this (SubstitutionRef &ref,
 823                                                    SubstitutionRef &to)
 824 {
 825   rust_assert (!ref.needs_substitution ());
 826   rust_assert (needs_substitution ());
 827   rust_assert (get_num_substitutions () == ref.get_num_substitutions ());
 828
 829   Location locus = used_arguments.get_locus ();
 830   std::vector<SubstitutionArg> resolved_mappings;
 831
 832   std::map<HirId, std::pair<ParamType *, BaseType *>> substs;
 833   for (size_t i = 0; i < get_num_substitutions (); i++)
 834     {
 835       SubstitutionParamMapping &a = substitutions.at (i);
 836       SubstitutionParamMapping &b = ref.substitutions.at (i);
 837
 838       if (a.need_substitution ())
 839         {
 840           const BaseType *root = a.get_param_ty ()->resolve ()->get_root ();
 841           rust_assert (root->get_kind () == TyTy::TypeKind::PARAM);
 842           const ParamType *p = static_cast<const TyTy::ParamType *> (root);
 843
 844           substs[p->get_ty_ref ()] = {static_cast<ParamType *> (p->clone ()),
 845                                       b.get_param_ty ()->resolve ()};
 846         }
 847     }
 848
 849   for (auto it = substs.begin (); it != substs.end (); it++)
 850     {
 851       HirId param_id = it->first;
 852       BaseType *arg = it->second.second;
 853
 854       const SubstitutionParamMapping *associate_param = nullptr;
 855       for (SubstitutionParamMapping &p : to.substitutions)
 856         {
 857           if (p.get_param_ty ()->get_ty_ref () == param_id)
 858             {
 859               associate_param = &p;
 860               break;
 861             }
 862         }
 863
 864       rust_assert (associate_param != nullptr);
 865       SubstitutionArg argument (associate_param, arg);
 866       resolved_mappings.push_back (std::move (argument));
 867     }
 868
 869   return SubstitutionArgumentMappings (resolved_mappings, {}, locus);
 870 }
 871
 872 bool
 873 SubstitutionRef::monomorphize ()
 874 {
 875   auto context = Resolver::TypeCheckContext::get ();
 876   for (const auto &subst : get_substs ())
 877     {
 878       const TyTy::ParamType *pty = subst.get_param_ty ();
 879
 880       if (!pty->can_resolve ())
 881         continue;
 882
 883       const TyTy::BaseType *binding = pty->resolve ();
 884       if (binding->get_kind () == TyTy::TypeKind::PARAM)
 885         continue;
 886
 887       for (const auto &bound : pty->get_specified_bounds ())
 888         {
 889           const Resolver::TraitReference *specified_bound_ref = bound.get ();
 890
 891           // setup any associated type mappings for the specified bonds and this
 892           // type
 893           auto candidates = Resolver::TypeBoundsProbe::Probe (binding);
 894
 895           Resolver::AssociatedImplTrait *associated_impl_trait = nullptr;
 896           for (auto &probed_bound : candidates)
 897             {
 898               const Resolver::TraitReference *bound_trait_ref
 899                 = probed_bound.first;
 900               const HIR::ImplBlock *associated_impl = probed_bound.second;
 901
 902               HirId impl_block_id
 903                 = associated_impl->get_mappings ().get_hirid ();
 904               Resolver::AssociatedImplTrait *associated = nullptr;
 905               bool found_impl_trait
 906                 = context->lookup_associated_trait_impl (impl_block_id,
 907                                                          &associated);
 908               if (found_impl_trait)
 909                 {
 910                   bool found_trait
 911                     = specified_bound_ref->is_equal (*bound_trait_ref);
 912                   bool found_self
 913                     = associated->get_self ()->can_eq (binding, false);
 914                   if (found_trait && found_self)
 915                     {
 916                       associated_impl_trait = associated;
 917                       break;
 918                     }
 919                 }
 920             }
 921
 922           if (associated_impl_trait != nullptr)
 923             {
 924               associated_impl_trait->setup_associated_types (binding, bound);
 925             }
 926         }
 927     }
 928
 929   return true;
 930 }
 931
 932 } // namespace TyTy
 933 } // namespace Rust