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

   1 // Copyright (C) 2021-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-hir-type-bounds.h"
  20 #include "rust-hir-trait-resolve.h"
  21 #include "rust-substitution-mapper.h"
  22 #include "rust-type-util.h"
  23
  24 namespace Rust {
  25 namespace Resolver {
  26
  27 TypeBoundsProbe::TypeBoundsProbe (const TyTy::BaseType *receiver)
  28   : TypeCheckBase (), receiver (receiver)
  29 {}
  30
  31 std::vector<std::pair<TraitReference *, HIR::ImplBlock *>>
  32 TypeBoundsProbe::Probe (const TyTy::BaseType *receiver)
  33 {
  34   TypeBoundsProbe probe (receiver);
  35   probe.scan ();
  36   return probe.trait_references;
  37 }
  38
  39 bool
  40 TypeBoundsProbe::is_bound_satisfied_for_type (TyTy::BaseType *receiver,
  41                                               TraitReference *ref)
  42 {
  43   for (auto &bound : receiver->get_specified_bounds ())
  44     {
  45       const TraitReference *b = bound.get ();
  46       if (b->is_equal (*ref))
  47         return true;
  48     }
  49
  50   std::vector<std::pair<TraitReference *, HIR::ImplBlock *>> bounds
  51     = Probe (receiver);
  52   for (auto &bound : bounds)
  53     {
  54       const TraitReference *b = bound.first;
  55       if (b->is_equal (*ref))
  56         return true;
  57     }
  58
  59   return false;
  60 }
  61
  62 void
  63 TypeBoundsProbe::scan ()
  64 {
  65   std::vector<std::pair<HIR::TypePath *, HIR::ImplBlock *>>
  66     possible_trait_paths;
  67   mappings->iterate_impl_blocks (
  68     [&] (HirId id, HIR::ImplBlock *impl) mutable -> bool {
  69       // we are filtering for trait-impl-blocks
  70       if (!impl->has_trait_ref ())
  71         return true;
  72
  73       HirId impl_ty_id = impl->get_type ()->get_mappings ().get_hirid ();
  74       TyTy::BaseType *impl_type = nullptr;
  75       if (!query_type (impl_ty_id, &impl_type))
  76         return true;
  77
  78       if (!receiver->can_eq (impl_type, false))
  79         {
  80           if (!impl_type->can_eq (receiver, false))
  81             return true;
  82         }
  83
  84       possible_trait_paths.push_back ({impl->get_trait_ref ().get (), impl});
  85       return true;
  86     });
  87
  88   for (auto &path : possible_trait_paths)
  89     {
  90       HIR::TypePath *trait_path = path.first;
  91       TraitReference *trait_ref = TraitResolver::Resolve (*trait_path);
  92
  93       if (!trait_ref->is_error ())
  94         trait_references.push_back ({trait_ref, path.second});
  95     }
  96
  97   // marker traits...
  98   assemble_sized_builtin ();
  99 }
 100
 101 void
 102 TypeBoundsProbe::assemble_sized_builtin ()
 103 {
 104   const TyTy::BaseType *raw = receiver->destructure ();
 105
 106   // https://runrust.miraheze.org/wiki/Dynamically_Sized_Type
 107   // everything is sized except for:
 108   //
 109   //   1. dyn traits
 110   //   2. slices
 111   //   3. str
 112   //   4. ADT's which contain any of the above
 113   //   t. tuples which contain any of the above
 114   switch (raw->get_kind ())
 115     {
 116     case TyTy::ARRAY:
 117     case TyTy::REF:
 118     case TyTy::POINTER:
 119     case TyTy::PARAM:
 120     case TyTy::FNDEF:
 121     case TyTy::FNPTR:
 122     case TyTy::BOOL:
 123     case TyTy::CHAR:
 124     case TyTy::INT:
 125     case TyTy::UINT:
 126     case TyTy::FLOAT:
 127     case TyTy::USIZE:
 128     case TyTy::ISIZE:
 129     case TyTy::CLOSURE:
 130     case TyTy::INFER:
 131     case TyTy::NEVER:
 132     case TyTy::PLACEHOLDER:
 133     case TyTy::PROJECTION:
 134       assemble_builtin_candidate (LangItem::Kind::SIZED);
 135       break;
 136
 137       // FIXME str and slice need to be moved and test cases updated
 138     case TyTy::SLICE:
 139     case TyTy::STR:
 140     case TyTy::ADT:
 141     case TyTy::TUPLE:
 142       // FIXME add extra checks
 143       assemble_builtin_candidate (LangItem::Kind::SIZED);
 144       break;
 145
 146     case TyTy::DYNAMIC:
 147     case TyTy::ERROR:
 148       break;
 149     }
 150 }
 151
 152 void
 153 TypeBoundsProbe::assemble_builtin_candidate (LangItem::Kind lang_item)
 154 {
 155   DefId id;
 156   bool found_lang_item = mappings->lookup_lang_item (lang_item, &id);
 157   if (!found_lang_item)
 158     return;
 159
 160   HIR::Item *item = mappings->lookup_defid (id);
 161   if (item == nullptr)
 162     return;
 163
 164   rust_assert (item->get_item_kind () == HIR::Item::ItemKind::Trait);
 165   HIR::Trait *trait = static_cast<HIR::Trait *> (item);
 166   const TyTy::BaseType *raw = receiver->destructure ();
 167
 168   // assemble the reference
 169   TraitReference *trait_ref = TraitResolver::Resolve (*trait);
 170   trait_references.push_back ({trait_ref, mappings->lookup_builtin_marker ()});
 171
 172   rust_debug ("Added builtin lang_item: %s for %s",
 173               LangItem::ToString (lang_item).c_str (),
 174               raw->get_name ().c_str ());
 175 }
 176
 177 TraitReference *
 178 TypeCheckBase::resolve_trait_path (HIR::TypePath &path)
 179 {
 180   return TraitResolver::Resolve (path);
 181 }
 182
 183 TyTy::TypeBoundPredicate
 184 TypeCheckBase::get_predicate_from_bound (HIR::TypePath &type_path,
 185                                          HIR::Type *associated_self,
 186                                          BoundPolarity polarity)
 187 {
 188   TyTy::TypeBoundPredicate lookup = TyTy::TypeBoundPredicate::error ();
 189   bool already_resolved
 190     = context->lookup_predicate (type_path.get_mappings ().get_hirid (),
 191                                  &lookup);
 192   if (already_resolved)
 193     return lookup;
 194
 195   TraitReference *trait = resolve_trait_path (type_path);
 196   if (trait->is_error ())
 197     return TyTy::TypeBoundPredicate::error ();
 198
 199   TyTy::TypeBoundPredicate predicate (*trait, polarity, type_path.get_locus ());
 200   HIR::GenericArgs args
 201     = HIR::GenericArgs::create_empty (type_path.get_locus ());
 202
 203   auto &final_seg = type_path.get_final_segment ();
 204   switch (final_seg->get_type ())
 205     {
 206       case HIR::TypePathSegment::SegmentType::GENERIC: {
 207         auto final_generic_seg
 208           = static_cast<HIR::TypePathSegmentGeneric *> (final_seg.get ());
 209         if (final_generic_seg->has_generic_args ())
 210           {
 211             args = final_generic_seg->get_generic_args ();
 212           }
 213       }
 214       break;
 215
 216       case HIR::TypePathSegment::SegmentType::FUNCTION: {
 217         auto final_function_seg
 218           = static_cast<HIR::TypePathSegmentFunction *> (final_seg.get ());
 219         auto &fn = final_function_seg->get_function_path ();
 220
 221         // we need to make implicit generic args which must be an implicit
 222         // Tuple
 223         auto crate_num = mappings->get_current_crate ();
 224         HirId implicit_args_id = mappings->get_next_hir_id ();
 225         Analysis::NodeMapping mapping (crate_num,
 226                                        final_seg->get_mappings ().get_nodeid (),
 227                                        implicit_args_id, UNKNOWN_LOCAL_DEFID);
 228
 229         std::vector<std::unique_ptr<HIR::Type>> params_copy;
 230         for (auto &p : fn.get_params ())
 231           {
 232             params_copy.push_back (p->clone_type ());
 233           }
 234
 235         HIR::TupleType *implicit_tuple
 236           = new HIR::TupleType (mapping, std::move (params_copy),
 237                                 final_seg->get_locus ());
 238
 239         std::vector<std::unique_ptr<HIR::Type>> inputs;
 240         inputs.push_back (std::unique_ptr<HIR::Type> (implicit_tuple));
 241
 242         // resolve the fn_once_output type which assumes there must be an output
 243         // set
 244         rust_assert (fn.has_return_type ());
 245         TypeCheckType::Resolve (fn.get_return_type ().get ());
 246
 247         HIR::TraitItem *trait_item = mappings->lookup_trait_item_lang_item (
 248           LangItem::Kind::FN_ONCE_OUTPUT, final_seg->get_locus ());
 249
 250         std::vector<HIR::GenericArgsBinding> bindings;
 251         location_t output_locus = fn.get_return_type ()->get_locus ();
 252         HIR::GenericArgsBinding binding (Identifier (
 253                                            trait_item->trait_identifier ()),
 254                                          fn.get_return_type ()->clone_type (),
 255                                          output_locus);
 256         bindings.push_back (std::move (binding));
 257
 258         args = HIR::GenericArgs ({} /* lifetimes */,
 259                                  std::move (inputs) /* type_args*/,
 260                                  std::move (bindings) /* binding_args*/,
 261                                  {} /* const_args */, final_seg->get_locus ());
 262       }
 263       break;
 264
 265     default:
 266       /* nothing to do */
 267       break;
 268     }
 269
 270   if (associated_self != nullptr)
 271     {
 272       std::vector<std::unique_ptr<HIR::Type>> type_args;
 273       type_args.push_back (
 274         std::unique_ptr<HIR::Type> (associated_self->clone_type ()));
 275       for (auto &arg : args.get_type_args ())
 276         {
 277           type_args.push_back (std::unique_ptr<HIR::Type> (arg->clone_type ()));
 278         }
 279
 280       args = HIR::GenericArgs (args.get_lifetime_args (), std::move (type_args),
 281                                args.get_binding_args (), args.get_const_args (),
 282                                args.get_locus ());
 283     }
 284
 285   // we try to apply generic arguments when they are non empty and or when the
 286   // predicate requires them so that we get the relevant Foo expects x number
 287   // arguments but got zero see test case rust/compile/traits12.rs
 288   if (!args.is_empty () || predicate.requires_generic_args ())
 289     {
 290       // this is applying generic arguments to a trait reference
 291       predicate.apply_generic_arguments (&args, associated_self != nullptr);
 292     }
 293
 294   context->insert_resolved_predicate (type_path.get_mappings ().get_hirid (),
 295                                       predicate);
 296
 297   return predicate;
 298 }
 299
 300 } // namespace Resolver
 301
 302 namespace TyTy {
 303
 304 TypeBoundPredicate::TypeBoundPredicate (
 305   const Resolver::TraitReference &trait_reference, BoundPolarity polarity,
 306   location_t locus)
 307   : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
 308     reference (trait_reference.get_mappings ().get_defid ()), locus (locus),
 309     error_flag (false), polarity (polarity)
 310 {
 311   rust_assert (!trait_reference.get_trait_substs ().empty ());
 312
 313   substitutions.clear ();
 314   for (const auto &p : trait_reference.get_trait_substs ())
 315     substitutions.push_back (p.clone ());
 316
 317   // we setup a dummy implict self argument
 318   SubstitutionArg placeholder_self (&get_substs ().front (), nullptr);
 319   used_arguments.get_mappings ().push_back (placeholder_self);
 320 }
 321
 322 TypeBoundPredicate::TypeBoundPredicate (
 323   DefId reference, std::vector<SubstitutionParamMapping> subst,
 324   BoundPolarity polarity, location_t locus)
 325   : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
 326     reference (reference), locus (locus), error_flag (false),
 327     polarity (polarity)
 328 {
 329   rust_assert (!subst.empty ());
 330
 331   substitutions.clear ();
 332   for (const auto &p : subst)
 333     substitutions.push_back (p.clone ());
 334
 335   // we setup a dummy implict self argument
 336   SubstitutionArg placeholder_self (&get_substs ().front (), nullptr);
 337   used_arguments.get_mappings ().push_back (placeholder_self);
 338 }
 339
 340 TypeBoundPredicate::TypeBoundPredicate (mark_is_error)
 341   : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
 342     reference (UNKNOWN_DEFID), locus (UNDEF_LOCATION), error_flag (true),
 343     polarity (BoundPolarity::RegularBound)
 344 {}
 345
 346 TypeBoundPredicate::TypeBoundPredicate (const TypeBoundPredicate &other)
 347   : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
 348     reference (other.reference), locus (other.locus),
 349     error_flag (other.error_flag), polarity (other.polarity)
 350 {
 351   substitutions.clear ();
 352   for (const auto &p : other.get_substs ())
 353     substitutions.push_back (p.clone ());
 354
 355   std::vector<SubstitutionArg> mappings;
 356   for (size_t i = 0; i < other.used_arguments.get_mappings ().size (); i++)
 357     {
 358       const SubstitutionArg &oa = other.used_arguments.get_mappings ().at (i);
 359       SubstitutionArg arg (oa);
 360       mappings.push_back (std::move (arg));
 361     }
 362
 363   // we need to remap the argument mappings based on this copied constructor
 364   std::vector<SubstitutionArg> copied_arg_mappings;
 365   size_t i = 0;
 366   for (const auto &m : other.used_arguments.get_mappings ())
 367     {
 368       TyTy::BaseType *argument
 369         = m.get_tyty () == nullptr ? nullptr : m.get_tyty ()->clone ();
 370       SubstitutionArg c (&substitutions.at (i++), argument);
 371       copied_arg_mappings.push_back (std::move (c));
 372     }
 373
 374   used_arguments
 375     = SubstitutionArgumentMappings (copied_arg_mappings, {},
 376                                     other.used_arguments.get_regions (),
 377                                     other.used_arguments.get_locus ());
 378 }
 379
 380 TypeBoundPredicate &
 381 TypeBoundPredicate::operator= (const TypeBoundPredicate &other)
 382 {
 383   reference = other.reference;
 384   locus = other.locus;
 385   error_flag = other.error_flag;
 386   polarity = other.polarity;
 387   used_arguments = SubstitutionArgumentMappings::empty ();
 388
 389   substitutions.clear ();
 390   for (const auto &p : other.get_substs ())
 391     substitutions.push_back (p.clone ());
 392
 393   if (other.is_error ())
 394     return *this;
 395
 396   std::vector<SubstitutionArg> mappings;
 397   for (size_t i = 0; i < other.used_arguments.get_mappings ().size (); i++)
 398     {
 399       const SubstitutionArg &oa = other.used_arguments.get_mappings ().at (i);
 400       SubstitutionArg arg (oa);
 401       mappings.push_back (std::move (arg));
 402     }
 403
 404   // we need to remap the argument mappings based on this copied constructor
 405   std::vector<SubstitutionArg> copied_arg_mappings;
 406   size_t i = 0;
 407   for (const auto &m : other.used_arguments.get_mappings ())
 408     {
 409       TyTy::BaseType *argument
 410         = m.get_tyty () == nullptr ? nullptr : m.get_tyty ()->clone ();
 411       SubstitutionArg c (&substitutions.at (i++), argument);
 412       copied_arg_mappings.push_back (std::move (c));
 413     }
 414
 415   used_arguments
 416     = SubstitutionArgumentMappings (copied_arg_mappings, {},
 417                                     other.used_arguments.get_regions (),
 418                                     other.used_arguments.get_locus ());
 419
 420   return *this;
 421 }
 422
 423 TypeBoundPredicate
 424 TypeBoundPredicate::error ()
 425 {
 426   return TypeBoundPredicate (mark_is_error ());
 427 }
 428
 429 std::string
 430 TypeBoundPredicate::as_string () const
 431 {
 432   return get ()->as_string () + subst_as_string ();
 433 }
 434
 435 std::string
 436 TypeBoundPredicate::as_name () const
 437 {
 438   return get ()->get_name () + subst_as_string ();
 439 }
 440
 441 const Resolver::TraitReference *
 442 TypeBoundPredicate::get () const
 443 {
 444   auto context = Resolver::TypeCheckContext::get ();
 445
 446   Resolver::TraitReference *ref = nullptr;
 447   bool ok = context->lookup_trait_reference (reference, &ref);
 448   rust_assert (ok);
 449
 450   return ref;
 451 }
 452
 453 std::string
 454 TypeBoundPredicate::get_name () const
 455 {
 456   return get ()->get_name ();
 457 }
 458
 459 bool
 460 TypeBoundPredicate::is_object_safe (bool emit_error, location_t locus) const
 461 {
 462   const Resolver::TraitReference *trait = get ();
 463   rust_assert (trait != nullptr);
 464   return trait->is_object_safe (emit_error, locus);
 465 }
 466
 467 void
 468 TypeBoundPredicate::apply_generic_arguments (HIR::GenericArgs *generic_args,
 469                                              bool has_associated_self)
 470 {
 471   rust_assert (!substitutions.empty ());
 472   if (has_associated_self)
 473     {
 474       used_arguments = SubstitutionArgumentMappings::empty ();
 475     }
 476   else
 477     {
 478       // we need to get the substitutions argument mappings but also remember
 479       // that we have an implicit Self argument which we must be careful to
 480       // respect
 481       rust_assert (!used_arguments.is_empty ());
 482     }
 483
 484   // now actually perform a substitution
 485   used_arguments = get_mappings_from_generic_args (
 486     *generic_args,
 487     Resolver::TypeCheckContext::get ()->regions_from_generic_args (
 488       *generic_args));
 489
 490   error_flag |= used_arguments.is_error ();
 491   auto &subst_mappings = used_arguments;
 492   for (auto &sub : get_substs ())
 493     {
 494       SubstitutionArg arg = SubstitutionArg::error ();
 495       bool ok
 496         = subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
 497       if (ok && arg.get_tyty () != nullptr)
 498         sub.fill_param_ty (subst_mappings, subst_mappings.get_locus ());
 499     }
 500
 501   // associated argument mappings
 502   for (auto &it : subst_mappings.get_binding_args ())
 503     {
 504       std::string identifier = it.first;
 505       TyTy::BaseType *type = it.second;
 506
 507       TypeBoundPredicateItem item = lookup_associated_item (identifier);
 508       rust_assert (!item.is_error ());
 509
 510       const auto item_ref = item.get_raw_item ();
 511       item_ref->associated_type_set (type);
 512     }
 513 }
 514
 515 bool
 516 TypeBoundPredicate::contains_item (const std::string &search) const
 517 {
 518   auto trait_ref = get ();
 519   const Resolver::TraitItemReference *trait_item_ref = nullptr;
 520   return trait_ref->lookup_trait_item (search, &trait_item_ref);
 521 }
 522
 523 TypeBoundPredicateItem
 524 TypeBoundPredicate::lookup_associated_item (const std::string &search) const
 525 {
 526   auto trait_ref = get ();
 527   const Resolver::TraitItemReference *trait_item_ref = nullptr;
 528   if (!trait_ref->lookup_trait_item (search, &trait_item_ref))
 529     return TypeBoundPredicateItem::error ();
 530
 531   return TypeBoundPredicateItem (this, trait_item_ref);
 532 }
 533
 534 TypeBoundPredicateItem::TypeBoundPredicateItem (
 535   const TypeBoundPredicate *parent,
 536   const Resolver::TraitItemReference *trait_item_ref)
 537   : parent (parent), trait_item_ref (trait_item_ref)
 538 {}
 539
 540 TypeBoundPredicateItem
 541 TypeBoundPredicateItem::error ()
 542 {
 543   return TypeBoundPredicateItem (nullptr, nullptr);
 544 }
 545
 546 bool
 547 TypeBoundPredicateItem::is_error () const
 548 {
 549   return parent == nullptr || trait_item_ref == nullptr;
 550 }
 551
 552 const TypeBoundPredicate *
 553 TypeBoundPredicateItem::get_parent () const
 554 {
 555   return parent;
 556 }
 557
 558 TypeBoundPredicateItem
 559 TypeBoundPredicate::lookup_associated_item (
 560   const Resolver::TraitItemReference *ref) const
 561 {
 562   return lookup_associated_item (ref->get_identifier ());
 563 }
 564
 565 BaseType *
 566 TypeBoundPredicateItem::get_tyty_for_receiver (const TyTy::BaseType *receiver)
 567 {
 568   TyTy::BaseType *trait_item_tyty = get_raw_item ()->get_tyty ();
 569   if (parent->get_substitution_arguments ().is_empty ())
 570     return trait_item_tyty;
 571
 572   const Resolver::TraitItemReference *tref = get_raw_item ();
 573   bool is_associated_type = tref->get_trait_item_type ();
 574   if (is_associated_type)
 575     return trait_item_tyty;
 576
 577   // set up the self mapping
 578   SubstitutionArgumentMappings gargs = parent->get_substitution_arguments ();
 579   rust_assert (!gargs.is_empty ());
 580
 581   // setup the adjusted mappings
 582   std::vector<SubstitutionArg> adjusted_mappings;
 583   for (size_t i = 0; i < gargs.get_mappings ().size (); i++)
 584     {
 585       auto &mapping = gargs.get_mappings ().at (i);
 586
 587       bool is_implicit_self = i == 0;
 588       TyTy::BaseType *argument
 589         = is_implicit_self ? receiver->clone () : mapping.get_tyty ();
 590
 591       SubstitutionArg arg (mapping.get_param_mapping (), argument);
 592       adjusted_mappings.push_back (std::move (arg));
 593     }
 594
 595   SubstitutionArgumentMappings adjusted (adjusted_mappings, {},
 596                                          gargs.get_regions (),
 597                                          gargs.get_locus (),
 598                                          gargs.get_subst_cb (),
 599                                          true /* trait-mode-flag */);
 600   return Resolver::SubstMapperInternal::Resolve (trait_item_tyty, adjusted);
 601 }
 602 bool
 603 TypeBoundPredicate::is_error () const
 604 {
 605   auto context = Resolver::TypeCheckContext::get ();
 606
 607   Resolver::TraitReference *ref = nullptr;
 608   bool ok = context->lookup_trait_reference (reference, &ref);
 609
 610   return !ok || error_flag;
 611 }
 612
 613 BaseType *
 614 TypeBoundPredicate::handle_substitions (
 615   SubstitutionArgumentMappings &subst_mappings)
 616 {
 617   for (auto &sub : get_substs ())
 618     {
 619       if (sub.get_param_ty () == nullptr)
 620         continue;
 621
 622       ParamType *p = sub.get_param_ty ();
 623       BaseType *r = p->resolve ();
 624       BaseType *s = Resolver::SubstMapperInternal::Resolve (r, subst_mappings);
 625
 626       p->set_ty_ref (s->get_ty_ref ());
 627     }
 628
 629   // associated argument mappings
 630   for (auto &it : subst_mappings.get_binding_args ())
 631     {
 632       std::string identifier = it.first;
 633       TyTy::BaseType *type = it.second;
 634
 635       TypeBoundPredicateItem item = lookup_associated_item (identifier);
 636       if (!item.is_error ())
 637         {
 638           const auto item_ref = item.get_raw_item ();
 639           item_ref->associated_type_set (type);
 640         }
 641     }
 642
 643   // FIXME more error handling at some point
 644   // used_arguments = subst_mappings;
 645   // error_flag |= used_arguments.is_error ();
 646
 647   return nullptr;
 648 }
 649
 650 bool
 651 TypeBoundPredicate::requires_generic_args () const
 652 {
 653   if (is_error ())
 654     return false;
 655
 656   return substitutions.size () > 1;
 657 }
 658
 659 bool
 660 TypeBoundPredicate::contains_associated_types () const
 661 {
 662   return get_num_associated_bindings () > 0;
 663 }
 664
 665 size_t
 666 TypeBoundPredicate::get_num_associated_bindings () const
 667 {
 668   size_t count = 0;
 669   auto trait_ref = get ();
 670   for (const auto &trait_item : trait_ref->get_trait_items ())
 671     {
 672       bool is_associated_type
 673         = trait_item.get_trait_item_type ()
 674           == Resolver::TraitItemReference::TraitItemType::TYPE;
 675       if (is_associated_type)
 676         count++;
 677     }
 678   return count;
 679 }
 680
 681 TypeBoundPredicateItem
 682 TypeBoundPredicate::lookup_associated_type (const std::string &search)
 683 {
 684   TypeBoundPredicateItem item = lookup_associated_item (search);
 685
 686   // only need to check that it is infact an associated type because other
 687   // wise if it was not found it will just be an error node anyway
 688   if (!item.is_error ())
 689     {
 690       const auto raw = item.get_raw_item ();
 691       if (raw->get_trait_item_type ()
 692           != Resolver::TraitItemReference::TraitItemType::TYPE)
 693         return TypeBoundPredicateItem::error ();
 694     }
 695   return item;
 696 }
 697
 698 std::vector<TypeBoundPredicateItem>
 699 TypeBoundPredicate::get_associated_type_items ()
 700 {
 701   std::vector<TypeBoundPredicateItem> items;
 702   auto trait_ref = get ();
 703   for (const auto &trait_item : trait_ref->get_trait_items ())
 704     {
 705       bool is_associated_type
 706         = trait_item.get_trait_item_type ()
 707           == Resolver::TraitItemReference::TraitItemType::TYPE;
 708       if (is_associated_type)
 709         {
 710           TypeBoundPredicateItem item (this, &trait_item);
 711           items.push_back (std::move (item));
 712         }
 713     }
 714   return items;
 715 }
 716
 717 bool
 718 TypeBoundPredicate::is_equal (const TypeBoundPredicate &other) const
 719 {
 720   // check they match the same trait reference
 721   if (reference != other.reference)
 722     return false;
 723
 724   // check that the generics match
 725   if (get_num_substitutions () != other.get_num_substitutions ())
 726     return false;
 727
 728   // then match the generics applied
 729   for (size_t i = 0; i < get_num_substitutions (); i++)
 730     {
 731       const SubstitutionParamMapping &a = substitutions.at (i);
 732       const SubstitutionParamMapping &b = other.substitutions.at (i);
 733
 734       const ParamType *ap = a.get_param_ty ();
 735       const ParamType *bp = b.get_param_ty ();
 736
 737       const BaseType *apd = ap->destructure ();
 738       const BaseType *bpd = bp->destructure ();
 739
 740       // FIXME use the unify_and infer inteface or try coerce
 741       if (!apd->can_eq (bpd, false /*emit_errors*/))
 742         {
 743           if (!bpd->can_eq (apd, false /*emit_errors*/))
 744             return false;
 745         }
 746     }
 747
 748   return true;
 749 }
 750
 751 // trait item reference
 752
 753 const Resolver::TraitItemReference *
 754 TypeBoundPredicateItem::get_raw_item () const
 755 {
 756   return trait_item_ref;
 757 }
 758
 759 bool
 760 TypeBoundPredicateItem::needs_implementation () const
 761 {
 762   return !get_raw_item ()->is_optional ();
 763 }
 764
 765 location_t
 766 TypeBoundPredicateItem::get_locus () const
 767 {
 768   return get_raw_item ()->get_locus ();
 769 }
 770
 771 // TypeBoundsMappings
 772
 773 TypeBoundsMappings::TypeBoundsMappings (
 774   std::vector<TypeBoundPredicate> specified_bounds)
 775   : specified_bounds (specified_bounds)
 776 {}
 777
 778 std::vector<TypeBoundPredicate> &
 779 TypeBoundsMappings::get_specified_bounds ()
 780 {
 781   return specified_bounds;
 782 }
 783
 784 const std::vector<TypeBoundPredicate> &
 785 TypeBoundsMappings::get_specified_bounds () const
 786 {
 787   return specified_bounds;
 788 }
 789
 790 TypeBoundPredicate
 791 TypeBoundsMappings::lookup_predicate (DefId id)
 792 {
 793   for (auto &b : specified_bounds)
 794     {
 795       if (b.get_id () == id)
 796         return b;
 797     }
 798   return TypeBoundPredicate::error ();
 799 }
 800
 801 size_t
 802 TypeBoundsMappings::num_specified_bounds () const
 803 {
 804   return specified_bounds.size ();
 805 }
 806
 807 std::string
 808 TypeBoundsMappings::raw_bounds_as_string () const
 809 {
 810   std::string buf;
 811   for (size_t i = 0; i < specified_bounds.size (); i++)
 812     {
 813       const TypeBoundPredicate &b = specified_bounds.at (i);
 814       bool has_next = (i + 1) < specified_bounds.size ();
 815       buf += b.as_string () + (has_next ? " + " : "");
 816     }
 817   return buf;
 818 }
 819
 820 std::string
 821 TypeBoundsMappings::bounds_as_string () const
 822 {
 823   return "bounds:[" + raw_bounds_as_string () + "]";
 824 }
 825
 826 std::string
 827 TypeBoundsMappings::raw_bounds_as_name () const
 828 {
 829   std::string buf;
 830   for (size_t i = 0; i < specified_bounds.size (); i++)
 831     {
 832       const TypeBoundPredicate &b = specified_bounds.at (i);
 833       bool has_next = (i + 1) < specified_bounds.size ();
 834       buf += b.as_name () + (has_next ? " + " : "");
 835     }
 836
 837   return buf;
 838 }
 839
 840 void
 841 TypeBoundsMappings::add_bound (TypeBoundPredicate predicate)
 842 {
 843   for (auto &bound : specified_bounds)
 844     {
 845       bool same_trait_ref_p = bound.get_id () == predicate.get_id ();
 846       if (same_trait_ref_p)
 847         return;
 848     }
 849
 850   specified_bounds.push_back (predicate);
 851 }
 852
 853 } // namespace TyTy
 854 } // namespace Rust