gcc/rust/typecheck/rust-hir-path-probe.h

   1 // Copyright (C) 2020-2023 Free Software Foundation, Inc.
   2
   3 // This file is part of GCC.
   4
   5 // GCC is free software; you can redistribute it and/or modify it under
   6 // the terms of the GNU General Public License as published by the Free
   7 // Software Foundation; either version 3, or (at your option) any later
   8 // version.
   9
  10 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13 // for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with GCC; see the file COPYING3.  If not see
  17 // <http://www.gnu.org/licenses/>.
  18
  19 #ifndef RUST_HIR_PATH_PROBE_H
  20 #define RUST_HIR_PATH_PROBE_H
  21
  22 #include "rust-hir-type-check-base.h"
  23 #include "rust-hir-full.h"
  24 #include "rust-tyty.h"
  25 #include "rust-substitution-mapper.h"
  26 #include "rust-hir-type-bounds.h"
  27
  28 namespace Rust {
  29 namespace Resolver {
  30
  31 struct PathProbeCandidate
  32 {
  33   enum CandidateType
  34   {
  35     ERROR,
  36
  37     ENUM_VARIANT,
  38
  39     IMPL_CONST,
  40     IMPL_TYPE_ALIAS,
  41     IMPL_FUNC,
  42
  43     TRAIT_ITEM_CONST,
  44     TRAIT_TYPE_ALIAS,
  45     TRAIT_FUNC,
  46   };
  47
  48   struct EnumItemCandidate
  49   {
  50     const TyTy::ADTType *parent;
  51     const TyTy::VariantDef *variant;
  52   };
  53
  54   struct ImplItemCandidate
  55   {
  56     HIR::ImplItem *impl_item;
  57     HIR::ImplBlock *parent;
  58   };
  59
  60   struct TraitItemCandidate
  61   {
  62     const TraitReference *trait_ref;
  63     const TraitItemReference *item_ref;
  64     HIR::ImplBlock *impl;
  65   };
  66
  67   CandidateType type;
  68   TyTy::BaseType *ty;
  69   Location locus;
  70   union Candidate
  71   {
  72     EnumItemCandidate enum_field;
  73     ImplItemCandidate impl;
  74     TraitItemCandidate trait;
  75
  76     Candidate (EnumItemCandidate enum_field) : enum_field (enum_field) {}
  77     Candidate (ImplItemCandidate impl) : impl (impl) {}
  78     Candidate (TraitItemCandidate trait) : trait (trait) {}
  79   } item;
  80
  81   PathProbeCandidate (CandidateType type, TyTy::BaseType *ty, Location locus,
  82                       EnumItemCandidate enum_field)
  83     : type (type), ty (ty), item (enum_field)
  84   {}
  85
  86   PathProbeCandidate (CandidateType type, TyTy::BaseType *ty, Location locus,
  87                       ImplItemCandidate impl)
  88     : type (type), ty (ty), item (impl)
  89   {}
  90
  91   PathProbeCandidate (CandidateType type, TyTy::BaseType *ty, Location locus,
  92                       TraitItemCandidate trait)
  93     : type (type), ty (ty), item (trait)
  94   {}
  95
  96   std::string as_string () const
  97   {
  98     return "PathProbe candidate TODO - as_string";
  99   }
 100
 101   bool is_enum_candidate () const { return type == ENUM_VARIANT; }
 102
 103   bool is_impl_candidate () const
 104   {
 105     return type == IMPL_CONST || type == IMPL_TYPE_ALIAS || type == IMPL_FUNC;
 106   }
 107
 108   bool is_trait_candidate () const
 109   {
 110     return type == TRAIT_ITEM_CONST || type == TRAIT_TYPE_ALIAS
 111            || type == TRAIT_FUNC;
 112   }
 113
 114   bool is_full_trait_item_candidate () const
 115   {
 116     return is_trait_candidate () && item.trait.impl == nullptr;
 117   }
 118
 119   static PathProbeCandidate get_error ()
 120   {
 121     return PathProbeCandidate (ERROR, nullptr, Location (),
 122                                ImplItemCandidate{nullptr, nullptr});
 123   }
 124
 125   bool is_error () const { return type == ERROR; }
 126 };
 127
 128 class PathProbeType : public TypeCheckBase, public HIR::HIRImplVisitor
 129 {
 130 public:
 131   static std::vector<PathProbeCandidate>
 132   Probe (const TyTy::BaseType *receiver,
 133          const HIR::PathIdentSegment &segment_name, bool probe_impls,
 134          bool probe_bounds, bool ignore_mandatory_trait_items,
 135          DefId specific_trait_id = UNKNOWN_DEFID)
 136   {
 137     PathProbeType probe (receiver, segment_name, specific_trait_id);
 138     if (probe_impls)
 139       {
 140         if (receiver->get_kind () == TyTy::TypeKind::ADT)
 141           {
 142             const TyTy::ADTType *adt
 143               = static_cast<const TyTy::ADTType *> (receiver);
 144             if (adt->is_enum ())
 145               probe.process_enum_item_for_candiates (adt);
 146           }
 147
 148         probe.process_impl_items_for_candidates ();
 149       }
 150
 151     if (!probe_bounds)
 152       return probe.candidates;
 153
 154     if (!probe.is_reciever_generic ())
 155       {
 156         std::vector<std::pair<TraitReference *, HIR::ImplBlock *>> probed_bounds
 157           = TypeBoundsProbe::Probe (receiver);
 158         for (auto &candidate : probed_bounds)
 159           {
 160             const TraitReference *trait_ref = candidate.first;
 161             if (specific_trait_id != UNKNOWN_DEFID)
 162               {
 163                 if (trait_ref->get_mappings ().get_defid ()
 164                     != specific_trait_id)
 165                   continue;
 166               }
 167
 168             HIR::ImplBlock *impl = candidate.second;
 169             probe.process_associated_trait_for_candidates (
 170               trait_ref, impl, ignore_mandatory_trait_items);
 171           }
 172       }
 173
 174     for (const TyTy::TypeBoundPredicate &predicate :
 175          receiver->get_specified_bounds ())
 176       {
 177         const TraitReference *trait_ref = predicate.get ();
 178         if (specific_trait_id != UNKNOWN_DEFID)
 179           {
 180             if (trait_ref->get_mappings ().get_defid () != specific_trait_id)
 181               continue;
 182           }
 183
 184         probe.process_predicate_for_candidates (predicate,
 185                                                 ignore_mandatory_trait_items);
 186       }
 187
 188     return probe.candidates;
 189   }
 190
 191   void visit (HIR::TypeAlias &alias) override
 192   {
 193     Identifier name = alias.get_new_type_name ();
 194     if (search.as_string ().compare (name) == 0)
 195       {
 196         HirId tyid = alias.get_mappings ().get_hirid ();
 197         TyTy::BaseType *ty = nullptr;
 198         bool ok = context->lookup_type (tyid, &ty);
 199         rust_assert (ok);
 200
 201         PathProbeCandidate::ImplItemCandidate impl_item_candidate{&alias,
 202                                                                   current_impl};
 203         PathProbeCandidate candidate{
 204           PathProbeCandidate::CandidateType::IMPL_TYPE_ALIAS, ty,
 205           alias.get_locus (), impl_item_candidate};
 206         candidates.push_back (std::move (candidate));
 207       }
 208   }
 209
 210   void visit (HIR::ConstantItem &constant) override
 211   {
 212     Identifier name = constant.get_identifier ();
 213     if (search.as_string ().compare (name) == 0)
 214       {
 215         HirId tyid = constant.get_mappings ().get_hirid ();
 216         TyTy::BaseType *ty = nullptr;
 217         bool ok = context->lookup_type (tyid, &ty);
 218         rust_assert (ok);
 219
 220         PathProbeCandidate::ImplItemCandidate impl_item_candidate{&constant,
 221                                                                   current_impl};
 222         PathProbeCandidate candidate{
 223           PathProbeCandidate::CandidateType::IMPL_CONST, ty,
 224           constant.get_locus (), impl_item_candidate};
 225         candidates.push_back (std::move (candidate));
 226       }
 227   }
 228
 229   void visit (HIR::Function &function) override
 230   {
 231     Identifier name = function.get_function_name ();
 232     if (search.as_string ().compare (name) == 0)
 233       {
 234         HirId tyid = function.get_mappings ().get_hirid ();
 235         TyTy::BaseType *ty = nullptr;
 236         bool ok = context->lookup_type (tyid, &ty);
 237         rust_assert (ok);
 238
 239         PathProbeCandidate::ImplItemCandidate impl_item_candidate{&function,
 240                                                                   current_impl};
 241         PathProbeCandidate candidate{
 242           PathProbeCandidate::CandidateType::IMPL_FUNC, ty,
 243           function.get_locus (), impl_item_candidate};
 244         candidates.push_back (std::move (candidate));
 245       }
 246   }
 247
 248 protected:
 249   void process_enum_item_for_candiates (const TyTy::ADTType *adt)
 250   {
 251     if (specific_trait_id != UNKNOWN_DEFID)
 252       return;
 253
 254     TyTy::VariantDef *v;
 255     if (!adt->lookup_variant (search.as_string (), &v))
 256       return;
 257
 258     PathProbeCandidate::EnumItemCandidate enum_item_candidate{adt, v};
 259     PathProbeCandidate candidate{
 260       PathProbeCandidate::CandidateType::ENUM_VARIANT, receiver->clone (),
 261       mappings->lookup_location (adt->get_ty_ref ()), enum_item_candidate};
 262     candidates.push_back (std::move (candidate));
 263   }
 264
 265   void process_impl_items_for_candidates ()
 266   {
 267     mappings->iterate_impl_items ([&] (HirId id, HIR::ImplItem *item,
 268                                        HIR::ImplBlock *impl) mutable -> bool {
 269       process_impl_item_candidate (id, item, impl);
 270       return true;
 271     });
 272   }
 273
 274   void process_impl_item_candidate (HirId id, HIR::ImplItem *item,
 275                                     HIR::ImplBlock *impl)
 276   {
 277     current_impl = impl;
 278     HirId impl_ty_id = impl->get_type ()->get_mappings ().get_hirid ();
 279     TyTy::BaseType *impl_block_ty = nullptr;
 280     if (!context->lookup_type (impl_ty_id, &impl_block_ty))
 281       return;
 282
 283     if (!receiver->can_eq (impl_block_ty, false))
 284       {
 285         if (!impl_block_ty->can_eq (receiver, false))
 286           return;
 287       }
 288
 289     // lets visit the impl_item
 290     item->accept_vis (*this);
 291   }
 292
 293   void
 294   process_associated_trait_for_candidates (const TraitReference *trait_ref,
 295                                            HIR::ImplBlock *impl,
 296                                            bool ignore_mandatory_trait_items)
 297   {
 298     const TraitItemReference *trait_item_ref = nullptr;
 299     if (!trait_ref->lookup_trait_item (search.as_string (), &trait_item_ref))
 300       return;
 301
 302     bool trait_item_needs_implementation = !trait_item_ref->is_optional ();
 303     if (ignore_mandatory_trait_items && trait_item_needs_implementation)
 304       return;
 305
 306     PathProbeCandidate::CandidateType candidate_type;
 307     switch (trait_item_ref->get_trait_item_type ())
 308       {
 309       case TraitItemReference::TraitItemType::FN:
 310         candidate_type = PathProbeCandidate::CandidateType::TRAIT_FUNC;
 311         break;
 312       case TraitItemReference::TraitItemType::CONST:
 313         candidate_type = PathProbeCandidate::CandidateType::TRAIT_ITEM_CONST;
 314         break;
 315       case TraitItemReference::TraitItemType::TYPE:
 316         candidate_type = PathProbeCandidate::CandidateType::TRAIT_TYPE_ALIAS;
 317         break;
 318
 319       case TraitItemReference::TraitItemType::ERROR:
 320       default:
 321         gcc_unreachable ();
 322         break;
 323       }
 324
 325     TyTy::BaseType *trait_item_tyty = trait_item_ref->get_tyty ();
 326
 327     // we can substitute the Self with the receiver here
 328     if (trait_item_tyty->get_kind () == TyTy::TypeKind::FNDEF)
 329       {
 330         TyTy::FnType *fn = static_cast<TyTy::FnType *> (trait_item_tyty);
 331         TyTy::SubstitutionParamMapping *param = nullptr;
 332         for (auto &param_mapping : fn->get_substs ())
 333           {
 334             const HIR::TypeParam &type_param
 335               = param_mapping.get_generic_param ();
 336             if (type_param.get_type_representation ().compare ("Self") == 0)
 337               {
 338                 param = &param_mapping;
 339                 break;
 340               }
 341           }
 342         rust_assert (param != nullptr);
 343
 344         std::vector<TyTy::SubstitutionArg> mappings;
 345         mappings.push_back (TyTy::SubstitutionArg (param, receiver->clone ()));
 346
 347         Location locus; // FIXME
 348         TyTy::SubstitutionArgumentMappings args (std::move (mappings), locus);
 349         trait_item_tyty = SubstMapperInternal::Resolve (trait_item_tyty, args);
 350       }
 351
 352     PathProbeCandidate::TraitItemCandidate trait_item_candidate{trait_ref,
 353                                                                 trait_item_ref,
 354                                                                 impl};
 355
 356     PathProbeCandidate candidate{candidate_type, trait_item_tyty,
 357                                  trait_ref->get_locus (), trait_item_candidate};
 358     candidates.push_back (std::move (candidate));
 359   }
 360
 361   void
 362   process_predicate_for_candidates (const TyTy::TypeBoundPredicate &predicate,
 363                                     bool ignore_mandatory_trait_items)
 364   {
 365     const TraitReference *trait_ref = predicate.get ();
 366
 367     TyTy::TypeBoundPredicateItem item
 368       = predicate.lookup_associated_item (search.as_string ());
 369     if (item.is_error ())
 370       return;
 371
 372     if (ignore_mandatory_trait_items && item.needs_implementation ())
 373       return;
 374
 375     const TraitItemReference *trait_item_ref = item.get_raw_item ();
 376     PathProbeCandidate::CandidateType candidate_type;
 377     switch (trait_item_ref->get_trait_item_type ())
 378       {
 379       case TraitItemReference::TraitItemType::FN:
 380         candidate_type = PathProbeCandidate::CandidateType::TRAIT_FUNC;
 381         break;
 382       case TraitItemReference::TraitItemType::CONST:
 383         candidate_type = PathProbeCandidate::CandidateType::TRAIT_ITEM_CONST;
 384         break;
 385       case TraitItemReference::TraitItemType::TYPE:
 386         candidate_type = PathProbeCandidate::CandidateType::TRAIT_TYPE_ALIAS;
 387         break;
 388
 389       case TraitItemReference::TraitItemType::ERROR:
 390       default:
 391         gcc_unreachable ();
 392         break;
 393       }
 394
 395     TyTy::BaseType *trait_item_tyty = item.get_tyty_for_receiver (receiver);
 396     PathProbeCandidate::TraitItemCandidate trait_item_candidate{trait_ref,
 397                                                                 trait_item_ref,
 398                                                                 nullptr};
 399     PathProbeCandidate candidate{candidate_type, trait_item_tyty,
 400                                  trait_item_ref->get_locus (),
 401                                  trait_item_candidate};
 402     candidates.push_back (std::move (candidate));
 403   }
 404
 405 protected:
 406   PathProbeType (const TyTy::BaseType *receiver,
 407                  const HIR::PathIdentSegment &query, DefId specific_trait_id)
 408     : TypeCheckBase (), receiver (receiver), search (query),
 409       current_impl (nullptr), specific_trait_id (specific_trait_id)
 410   {}
 411
 412   std::vector<std::pair<const TraitReference *, HIR::ImplBlock *>>
 413   union_bounds (
 414     const std::vector<std::pair</*const*/ TraitReference *, HIR::ImplBlock *>>
 415       a,
 416     const std::vector<std::pair<const TraitReference *, HIR::ImplBlock *>> b)
 417     const
 418   {
 419     std::map<DefId, std::pair<const TraitReference *, HIR::ImplBlock *>> mapper;
 420     for (auto &ref : a)
 421       {
 422         mapper.insert ({ref.first->get_mappings ().get_defid (), ref});
 423       }
 424     for (auto &ref : b)
 425       {
 426         mapper.insert ({ref.first->get_mappings ().get_defid (), ref});
 427       }
 428
 429     std::vector<std::pair<const TraitReference *, HIR::ImplBlock *>> union_set;
 430     for (auto it = mapper.begin (); it != mapper.end (); it++)
 431       {
 432         union_set.push_back ({it->second.first, it->second.second});
 433       }
 434     return union_set;
 435   }
 436
 437   bool is_reciever_generic () const
 438   {
 439     const TyTy::BaseType *root = receiver->get_root ();
 440     bool receiver_is_type_param = root->get_kind () == TyTy::TypeKind::PARAM;
 441     bool receiver_is_dyn = root->get_kind () == TyTy::TypeKind::DYNAMIC;
 442     return receiver_is_type_param || receiver_is_dyn;
 443   }
 444
 445   const TyTy::BaseType *receiver;
 446   const HIR::PathIdentSegment &search;
 447   std::vector<PathProbeCandidate> candidates;
 448   HIR::ImplBlock *current_impl;
 449   DefId specific_trait_id;
 450 };
 451
 452 class ReportMultipleCandidateError : private TypeCheckBase,
 453                                      private HIR::HIRImplVisitor
 454 {
 455 public:
 456   static void Report (std::vector<PathProbeCandidate> &candidates,
 457                       const HIR::PathIdentSegment &query, Location query_locus)
 458   {
 459     RichLocation r (query_locus);
 460     ReportMultipleCandidateError visitor (r);
 461     for (auto &c : candidates)
 462       {
 463         switch (c.type)
 464           {
 465           case PathProbeCandidate::CandidateType::ERROR:
 466           case PathProbeCandidate::CandidateType::ENUM_VARIANT:
 467             gcc_unreachable ();
 468             break;
 469
 470           case PathProbeCandidate::CandidateType::IMPL_CONST:
 471           case PathProbeCandidate::CandidateType::IMPL_TYPE_ALIAS:
 472           case PathProbeCandidate::CandidateType::IMPL_FUNC:
 473             c.item.impl.impl_item->accept_vis (visitor);
 474             break;
 475
 476           case PathProbeCandidate::CandidateType::TRAIT_ITEM_CONST:
 477           case PathProbeCandidate::CandidateType::TRAIT_TYPE_ALIAS:
 478           case PathProbeCandidate::CandidateType::TRAIT_FUNC:
 479             r.add_range (c.item.trait.item_ref->get_locus ());
 480             break;
 481           }
 482       }
 483
 484     rust_error_at (r, "multiple applicable items in scope for: %s",
 485                    query.as_string ().c_str ());
 486   }
 487
 488   void visit (HIR::TypeAlias &alias) override
 489   {
 490     r.add_range (alias.get_locus ());
 491   }
 492
 493   void visit (HIR::ConstantItem &constant) override
 494   {
 495     r.add_range (constant.get_locus ());
 496   }
 497
 498   void visit (HIR::Function &function) override
 499   {
 500     r.add_range (function.get_locus ());
 501   }
 502
 503 private:
 504   ReportMultipleCandidateError (RichLocation &r) : TypeCheckBase (), r (r) {}
 505
 506   RichLocation &r;
 507 };
 508
 509 class PathProbeImplTrait : public PathProbeType
 510 {
 511 public:
 512   static std::vector<PathProbeCandidate>
 513   Probe (const TyTy::BaseType *receiver,
 514          const HIR::PathIdentSegment &segment_name,
 515          const TraitReference *trait_reference)
 516   {
 517     PathProbeImplTrait probe (receiver, segment_name, trait_reference);
 518     // iterate all impls for this trait and receiver
 519     // then search for possible candidates using base class behaviours
 520     probe.process_trait_impl_items_for_candidates ();
 521     return probe.candidates;
 522   }
 523
 524 private:
 525   void process_trait_impl_items_for_candidates ();
 526
 527   PathProbeImplTrait (const TyTy::BaseType *receiver,
 528                       const HIR::PathIdentSegment &query,
 529                       const TraitReference *trait_reference)
 530     : PathProbeType (receiver, query, UNKNOWN_DEFID),
 531       trait_reference (trait_reference)
 532   {}
 533
 534   const TraitReference *trait_reference;
 535 };
 536
 537 } // namespace Resolver
 538 } // namespace Rust
 539
 540 #endif // RUST_HIR_PATH_PROBE_H