Line data Source code
1 : // Copyright (C) 2021-2026 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-full-decls.h"
20 : #include "rust-hir-type-bounds.h"
21 : #include "rust-hir-trait-resolve.h"
22 : #include "rust-substitution-mapper.h"
23 : #include "rust-hir-trait-resolve.h"
24 : #include "rust-type-util.h"
25 : #include "rust-tyty.h"
26 :
27 : namespace Rust {
28 : namespace Resolver {
29 :
30 69623 : TypeBoundsProbe::TypeBoundsProbe (TyTy::BaseType *receiver,
31 : const HIR::Trait *specified_trait)
32 69623 : : TypeCheckBase (), receiver (receiver), specified_trait (specified_trait)
33 69623 : {}
34 :
35 : std::vector<std::pair<TraitReference *, HIR::ImplBlock *>>
36 69623 : TypeBoundsProbe::Probe (TyTy::BaseType *receiver,
37 : const HIR::Trait *specified_trait)
38 : {
39 69623 : TypeBoundsProbe probe (receiver, specified_trait);
40 69623 : probe.scan ();
41 69623 : return probe.trait_references;
42 69623 : }
43 :
44 : bool
45 82 : TypeBoundsProbe::is_bound_satisfied_for_type (TyTy::BaseType *receiver,
46 : TraitReference *ref)
47 : {
48 82 : for (auto &bound : receiver->get_specified_bounds ())
49 : {
50 0 : const TraitReference *b = bound.get ();
51 0 : if (b->is_equal (*ref))
52 82 : return true;
53 : }
54 :
55 82 : std::vector<std::pair<TraitReference *, HIR::ImplBlock *>> bounds
56 82 : = Probe (receiver, ref->get_hir_trait_ref ());
57 82 : for (auto &bound : bounds)
58 : {
59 80 : const TraitReference *b = bound.first;
60 80 : if (b->is_equal (*ref))
61 82 : return true;
62 : }
63 :
64 : return false;
65 82 : }
66 :
67 : bool
68 278934 : TypeBoundsProbe::process_impl_block (
69 : HirId id, HIR::ImplBlock *impl,
70 : std::vector<std::pair<HIR::TypePath *, HIR::ImplBlock *>>
71 : &possible_trait_paths)
72 : {
73 : // we are filtering for trait-impl-blocks
74 278934 : if (!impl->has_trait_ref ())
75 : return true;
76 :
77 : // can be recursive trait resolution
78 278934 : HIR::Trait *t = TraitResolver::ResolveHirItem (impl->get_trait_ref ());
79 278934 : if (t == nullptr)
80 : return true;
81 :
82 278934 : HirId impl_ty_id = impl->get_type ().get_mappings ().get_hirid ();
83 278934 : TyTy::BaseType *impl_type = nullptr;
84 278934 : if (!query_type (impl_ty_id, &impl_type))
85 : return true;
86 :
87 278934 : if (!types_compatable (TyTy::TyWithLocation (receiver),
88 278934 : TyTy::TyWithLocation (impl_type), impl->get_locus (),
89 : false /*emit_errors*/, false /*check-bounds*/))
90 : return true;
91 :
92 25943 : possible_trait_paths.emplace_back (&impl->get_trait_ref (), impl);
93 25943 : return true;
94 : }
95 :
96 : void
97 69623 : TypeBoundsProbe::scan ()
98 : {
99 69623 : std::vector<std::pair<HIR::TypePath *, HIR::ImplBlock *>>
100 69623 : possible_trait_paths;
101 348557 : auto process_impl = [&] (HirId id, HIR::ImplBlock *impl) mutable -> bool {
102 278934 : return process_impl_block (id, impl, possible_trait_paths);
103 69623 : };
104 :
105 69623 : if (specified_trait == nullptr)
106 475 : mappings.iterate_trait_impl_blocks (process_impl);
107 : else
108 69148 : mappings.iterate_trait_impl_blocks (
109 138296 : specified_trait->get_mappings ().get_defid (), process_impl);
110 :
111 95566 : for (auto &path : possible_trait_paths)
112 : {
113 25943 : HIR::TypePath *trait_path = path.first;
114 25943 : TraitReference *trait_ref = TraitResolver::Resolve (*trait_path);
115 :
116 25943 : if (!trait_ref->is_error ())
117 25943 : trait_references.emplace_back (trait_ref, path.second);
118 : }
119 :
120 : // marker traits...
121 69623 : assemble_marker_builtins ();
122 :
123 : // add auto trait bounds
124 69673 : for (auto *auto_trait : mappings.get_auto_traits ())
125 50 : add_trait_bound (auto_trait);
126 69623 : }
127 :
128 : void
129 69623 : TypeBoundsProbe::assemble_marker_builtins ()
130 : {
131 69623 : const TyTy::BaseType *raw = receiver->destructure ();
132 :
133 : // https://runrust.miraheze.org/wiki/Dynamically_Sized_Type
134 : // everything is sized except for:
135 : //
136 : // 1. dyn traits
137 : // 2. slices
138 : // 3. str
139 : // 4. ADT's which contain any of the above
140 : // t. tuples which contain any of the above
141 69623 : switch (raw->get_kind ())
142 : {
143 53782 : case TyTy::ARRAY:
144 53782 : case TyTy::REF:
145 53782 : case TyTy::POINTER:
146 53782 : case TyTy::PARAM:
147 53782 : case TyTy::FNDEF:
148 53782 : case TyTy::BOOL:
149 53782 : case TyTy::CHAR:
150 53782 : case TyTy::INT:
151 53782 : case TyTy::UINT:
152 53782 : case TyTy::FLOAT:
153 53782 : case TyTy::USIZE:
154 53782 : case TyTy::ISIZE:
155 53782 : case TyTy::INFER:
156 53782 : case TyTy::NEVER:
157 53782 : case TyTy::PLACEHOLDER:
158 53782 : case TyTy::PROJECTION:
159 53782 : case TyTy::OPAQUE:
160 53782 : assemble_builtin_candidate (LangItem::Kind::SIZED);
161 53782 : break;
162 :
163 331 : case TyTy::FNPTR:
164 331 : case TyTy::CLOSURE:
165 331 : assemble_builtin_candidate (LangItem::Kind::SIZED);
166 331 : assemble_builtin_candidate (LangItem::Kind::FN_ONCE);
167 331 : assemble_builtin_candidate (LangItem::Kind::FN);
168 331 : assemble_builtin_candidate (LangItem::Kind::FN_MUT);
169 331 : break;
170 :
171 : // FIXME str and slice need to be moved and test cases updated
172 1628 : case TyTy::SLICE:
173 1628 : case TyTy::STR:
174 1628 : case TyTy::TUPLE:
175 : // FIXME add extra checks
176 1628 : assemble_builtin_candidate (LangItem::Kind::SIZED);
177 1628 : break;
178 :
179 13614 : case TyTy::ADT:
180 13614 : {
181 13614 : const auto &adt = *static_cast<const TyTy::ADTType *> (raw);
182 13614 : if (adt.get_adt_kind () != TyTy::ADTType::ADTKind::EXTERN)
183 13613 : assemble_builtin_candidate (LangItem::Kind::SIZED);
184 : }
185 : break;
186 :
187 : case TyTy::CONST:
188 : case TyTy::DYNAMIC:
189 : case TyTy::ERROR:
190 : break;
191 : }
192 69623 : }
193 :
194 : void
195 69453 : TypeBoundsProbe::add_trait_bound (HIR::Trait *trait)
196 : {
197 69453 : auto trait_ref = TraitResolver::Resolve (*trait);
198 :
199 95469 : for (const auto &existing : trait_references)
200 26020 : if (existing.first->is_equal (*trait_ref))
201 8 : return;
202 :
203 69449 : if (receiver->get_kind () == TyTy::TypeKind::ADT)
204 : {
205 13460 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (receiver);
206 30753 : for (auto &variant : adt->get_variants ())
207 : {
208 34542 : for (auto &field : variant->get_fields ())
209 : {
210 17249 : TyTy::BaseType *field_ty = field->get_field_type ();
211 :
212 : // TODO: A loop guard is needed here to prevent infinite
213 : // recursion, but self-referential types currently crash due to
214 : // issue Rust-GCC/gccrs#4709. Therefore, I avoided adding an
215 : // untested guard for now.
216 :
217 17249 : if (!field_ty->satisfies_bound (
218 17249 : TyTy::TypeBoundPredicate (*trait_ref,
219 : BoundPolarity::RegularBound,
220 17249 : UNDEF_LOCATION),
221 : false))
222 8 : return;
223 : }
224 : }
225 : }
226 :
227 69445 : trait_references.emplace_back (trait_ref, mappings.lookup_builtin_marker ());
228 : }
229 :
230 : void
231 70347 : TypeBoundsProbe::assemble_builtin_candidate (LangItem::Kind lang_item)
232 : {
233 70347 : auto lang_item_defined = mappings.lookup_lang_item (lang_item);
234 70347 : if (!lang_item_defined)
235 944 : return;
236 69403 : DefId &id = lang_item_defined.value ();
237 :
238 69403 : auto defid = mappings.lookup_defid (id);
239 69403 : if (!defid)
240 : return;
241 69403 : auto item = defid.value ();
242 :
243 69403 : rust_assert (item->get_item_kind () == HIR::Item::ItemKind::Trait);
244 69403 : HIR::Trait *trait = static_cast<HIR::Trait *> (item);
245 69403 : const TyTy::BaseType *raw = receiver->destructure ();
246 :
247 69403 : add_trait_bound (trait);
248 :
249 69403 : rust_debug ("Added builtin lang_item: %s for %s",
250 : LangItem::ToString (lang_item).c_str (),
251 : raw->get_name ().c_str ());
252 : }
253 :
254 : TraitReference *
255 8244 : TypeCheckBase::resolve_trait_path (HIR::TypePath &path)
256 : {
257 8244 : return TraitResolver::Resolve (path);
258 : }
259 :
260 : TyTy::TypeBoundPredicate
261 34087 : TypeCheckBase::get_predicate_from_bound (
262 : HIR::TypePath &type_path,
263 : tl::optional<std::reference_wrapper<HIR::Type>> associated_self,
264 : BoundPolarity polarity, bool is_qualified_type_path, bool is_super_trait,
265 : bool defer_bindings)
266 : {
267 34087 : TyTy::TypeBoundPredicate lookup = TyTy::TypeBoundPredicate::error ();
268 34087 : bool already_resolved
269 34087 : = context->lookup_predicate (type_path.get_mappings ().get_hirid (),
270 : &lookup);
271 34087 : if (already_resolved)
272 25843 : return lookup;
273 :
274 8244 : TraitReference *trait = resolve_trait_path (type_path);
275 8244 : if (trait->is_error ())
276 9 : return TyTy::TypeBoundPredicate::error ();
277 :
278 8235 : TyTy::TypeBoundPredicate predicate (*trait, polarity, type_path.get_locus ());
279 8235 : HIR::GenericArgs args
280 8235 : = HIR::GenericArgs::create_empty (type_path.get_locus ());
281 :
282 8235 : auto &final_seg = type_path.get_final_segment ();
283 8235 : switch (final_seg.get_type ())
284 : {
285 1055 : case HIR::TypePathSegment::SegmentType::GENERIC:
286 1055 : {
287 1055 : auto &final_generic_seg
288 : = static_cast<HIR::TypePathSegmentGeneric &> (final_seg);
289 1055 : if (final_generic_seg.has_generic_args ())
290 : {
291 1055 : args = final_generic_seg.get_generic_args ();
292 1055 : if (args.get_binding_args ().size () > 0
293 1055 : && associated_self.has_value () && is_qualified_type_path)
294 : {
295 1 : auto &binding_args = args.get_binding_args ();
296 :
297 1 : rich_location r (line_table, args.get_locus ());
298 2 : for (auto it = binding_args.begin (); it != binding_args.end ();
299 1 : it++)
300 : {
301 1 : auto &arg = *it;
302 1 : r.add_fixit_remove (arg.get_locus ());
303 : }
304 1 : rust_error_at (r, ErrorCode::E0229,
305 : "associated type bindings are not allowed here");
306 1 : }
307 : }
308 : }
309 : break;
310 :
311 29 : case HIR::TypePathSegment::SegmentType::FUNCTION:
312 29 : {
313 29 : auto &final_function_seg
314 : = static_cast<HIR::TypePathSegmentFunction &> (final_seg);
315 29 : auto &fn = final_function_seg.get_function_path ();
316 :
317 : // we need to make implicit generic args which must be an implicit
318 : // Tuple
319 29 : auto crate_num = mappings.get_current_crate ();
320 29 : HirId implicit_args_id = mappings.get_next_hir_id ();
321 29 : Analysis::NodeMapping mapping (crate_num,
322 29 : final_seg.get_mappings ().get_nodeid (),
323 29 : implicit_args_id, UNKNOWN_LOCAL_DEFID);
324 :
325 29 : std::vector<std::unique_ptr<HIR::Type>> params_copy;
326 59 : for (auto &p : fn.get_params ())
327 : {
328 30 : params_copy.push_back (p->clone_type ());
329 : }
330 :
331 29 : std::vector<std::unique_ptr<HIR::Type>> inputs;
332 29 : inputs.push_back (
333 29 : std::make_unique<HIR::TupleType> (mapping, std::move (params_copy),
334 29 : final_seg.get_locus ()));
335 :
336 29 : HIR::TraitItem *trait_item
337 29 : = mappings
338 29 : .lookup_trait_item_lang_item (LangItem::Kind::FN_ONCE_OUTPUT,
339 : final_seg.get_locus ())
340 29 : .value ();
341 :
342 29 : std::vector<HIR::GenericArgsBinding> bindings;
343 :
344 29 : if (fn.has_return_type () && !defer_bindings)
345 : {
346 28 : TypeCheckType::Resolve (fn.get_return_type ());
347 :
348 28 : location_t output_locus = fn.get_return_type ().get_locus ();
349 84 : bindings.emplace_back (Identifier (trait_item->trait_identifier ()),
350 56 : fn.get_return_type ().clone_type (),
351 : output_locus);
352 : }
353 :
354 58 : args = HIR::GenericArgs ({} /* lifetimes */,
355 : std::move (inputs) /* type_args*/,
356 : std::move (bindings) /* binding_args*/,
357 58 : {} /* const_args */, final_seg.get_locus ());
358 29 : }
359 29 : break;
360 :
361 : default:
362 : /* nothing to do */
363 : break;
364 : }
365 :
366 8235 : if (associated_self.has_value ())
367 : {
368 7277 : std::vector<std::unique_ptr<HIR::Type>> type_args;
369 7277 : type_args.push_back (std::unique_ptr<HIR::Type> (
370 7277 : associated_self.value ().get ().clone_type ()));
371 8016 : for (auto &arg : args.get_type_args ())
372 : {
373 739 : type_args.push_back (std::unique_ptr<HIR::Type> (arg->clone_type ()));
374 : }
375 :
376 21831 : args = HIR::GenericArgs (args.get_lifetime_args (), std::move (type_args),
377 7277 : args.get_binding_args (), args.get_const_args (),
378 14554 : args.get_locus ());
379 7277 : }
380 :
381 8235 : if (defer_bindings)
382 330 : args.get_binding_args ().clear ();
383 :
384 : // we try to apply generic arguments when they are non empty and or when the
385 : // predicate requires them so that we get the relevant Foo expects x number
386 : // arguments but got zero see test case rust/compile/traits12.rs
387 8235 : if (!args.is_empty () || predicate.requires_generic_args ())
388 : {
389 : // this is applying generic arguments to a trait reference
390 7592 : predicate.apply_generic_arguments (&args, associated_self.has_value (),
391 : is_super_trait);
392 : }
393 :
394 8234 : if (!defer_bindings)
395 7904 : context->insert_resolved_predicate (type_path.get_mappings ().get_hirid (),
396 : predicate);
397 :
398 8234 : return predicate;
399 34086 : }
400 :
401 : } // namespace Resolver
402 :
403 : namespace TyTy {
404 :
405 38860 : TypeBoundPredicate::TypeBoundPredicate (
406 : const Resolver::TraitReference &trait_reference, BoundPolarity polarity,
407 : location_t locus)
408 38860 : : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
409 38860 : reference (trait_reference.get_mappings ().get_defid ()), locus (locus),
410 38860 : error_flag (false), polarity (polarity),
411 116580 : super_traits (trait_reference.get_super_traits ())
412 : {
413 38860 : rust_assert (!trait_reference.get_trait_substs ().empty ());
414 :
415 38860 : substitutions.clear ();
416 81142 : for (const auto &p : trait_reference.get_trait_substs ())
417 42282 : substitutions.push_back (p.clone ());
418 :
419 : // we setup a dummy implict self argument
420 38860 : SubstitutionArg placeholder_self (&get_substs ().front (), nullptr);
421 38860 : used_arguments.get_mappings ().push_back (placeholder_self);
422 38860 : }
423 :
424 4182 : TypeBoundPredicate::TypeBoundPredicate (
425 : DefId reference, std::vector<SubstitutionParamMapping> subst,
426 : BoundPolarity polarity, location_t locus)
427 4182 : : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
428 4182 : reference (reference), locus (locus), error_flag (false),
429 8364 : polarity (polarity)
430 : {
431 4182 : rust_assert (!subst.empty ());
432 :
433 4182 : substitutions.clear ();
434 9077 : for (const auto &p : subst)
435 4895 : substitutions.push_back (p.clone ());
436 :
437 : // we setup a dummy implict self argument
438 4182 : SubstitutionArg placeholder_self (&get_substs ().front (), nullptr);
439 4182 : used_arguments.get_mappings ().push_back (placeholder_self);
440 4182 : }
441 :
442 104558 : TypeBoundPredicate::TypeBoundPredicate (mark_is_error)
443 104558 : : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
444 104558 : reference (UNKNOWN_DEFID), locus (UNDEF_LOCATION), error_flag (true),
445 104558 : polarity (BoundPolarity::RegularBound)
446 104558 : {}
447 :
448 3544167 : TypeBoundPredicate::TypeBoundPredicate (const TypeBoundPredicate &other)
449 3544167 : : SubstitutionRef ({}, SubstitutionArgumentMappings::empty (), {}),
450 3544167 : reference (other.reference), locus (other.locus),
451 3544167 : error_flag (other.error_flag), polarity (other.polarity),
452 7088334 : super_traits (other.super_traits)
453 : {
454 3544167 : substitutions.clear ();
455 8139118 : for (const auto &p : other.get_substs ())
456 4594951 : substitutions.push_back (p.clone ());
457 :
458 : // we need to remap the argument mappings based on this copied constructor
459 3544167 : std::vector<SubstitutionArg> copied_arg_mappings;
460 3544167 : size_t i = 0;
461 7606992 : for (const auto &m : other.used_arguments.get_mappings ())
462 : {
463 4062825 : TyTy::BaseType *argument
464 4062825 : = m.get_tyty () == nullptr ? nullptr : m.get_tyty ()->clone ();
465 4062825 : SubstitutionArg c (&substitutions.at (i++), argument);
466 4062825 : copied_arg_mappings.push_back (std::move (c));
467 : }
468 :
469 3544167 : used_arguments = SubstitutionArgumentMappings (
470 : copied_arg_mappings, other.used_arguments.get_binding_args (),
471 : other.used_arguments.get_regions (), other.used_arguments.get_locus (),
472 7088334 : false, false, other.used_arguments.get_constraint_args ());
473 3544167 : }
474 :
475 : TypeBoundPredicate &
476 73735 : TypeBoundPredicate::operator= (const TypeBoundPredicate &other)
477 : {
478 73735 : reference = other.reference;
479 73735 : locus = other.locus;
480 73735 : error_flag = other.error_flag;
481 73735 : polarity = other.polarity;
482 73735 : used_arguments = SubstitutionArgumentMappings::empty ();
483 :
484 73735 : substitutions.clear ();
485 179111 : for (const auto &p : other.get_substs ())
486 105376 : substitutions.push_back (p.clone ());
487 :
488 73735 : if (other.is_error ())
489 : return *this;
490 :
491 : // we need to remap the argument mappings based on this copied constructor
492 62116 : std::vector<SubstitutionArg> copied_arg_mappings;
493 62116 : size_t i = 0;
494 167475 : for (const auto &m : other.used_arguments.get_mappings ())
495 : {
496 105359 : TyTy::BaseType *argument
497 105359 : = m.get_tyty () == nullptr ? nullptr : m.get_tyty ()->clone ();
498 :
499 105359 : copied_arg_mappings.emplace_back (&substitutions.at (i++), argument);
500 : }
501 :
502 62116 : used_arguments = SubstitutionArgumentMappings (
503 : copied_arg_mappings, other.used_arguments.get_binding_args (),
504 : other.used_arguments.get_regions (), other.used_arguments.get_locus (),
505 124232 : false, false, other.used_arguments.get_constraint_args ());
506 62116 : super_traits = other.super_traits;
507 :
508 62116 : return *this;
509 62116 : }
510 :
511 : TypeBoundPredicate
512 104558 : TypeBoundPredicate::error ()
513 : {
514 104558 : return TypeBoundPredicate (mark_is_error ());
515 : }
516 :
517 : std::string
518 235 : TypeBoundPredicate::as_string () const
519 : {
520 235 : return get ()->as_string () + subst_as_string ();
521 : }
522 :
523 : std::string
524 907 : TypeBoundPredicate::as_name () const
525 : {
526 907 : return get ()->get_name () + subst_as_string ();
527 : }
528 :
529 : const Resolver::TraitReference *
530 241406 : TypeBoundPredicate::get () const
531 : {
532 241406 : auto context = Resolver::TypeCheckContext::get ();
533 :
534 241406 : Resolver::TraitReference *ref = nullptr;
535 241406 : bool ok = context->lookup_trait_reference (reference, &ref);
536 241406 : rust_assert (ok);
537 :
538 241406 : return ref;
539 : }
540 :
541 : std::string
542 7437 : TypeBoundPredicate::get_name () const
543 : {
544 7437 : return get ()->get_name ();
545 : }
546 :
547 : bool
548 271 : TypeBoundPredicate::is_object_safe (bool emit_error, location_t locus) const
549 : {
550 271 : const Resolver::TraitReference *trait = get ();
551 271 : rust_assert (trait != nullptr);
552 271 : return trait->is_object_safe (emit_error, locus);
553 : }
554 :
555 : void
556 7658 : TypeBoundPredicate::apply_generic_arguments (HIR::GenericArgs *generic_args,
557 : bool has_associated_self,
558 : bool is_super_trait)
559 : {
560 7658 : rust_assert (!substitutions.empty ());
561 7658 : if (has_associated_self)
562 : {
563 7277 : used_arguments = SubstitutionArgumentMappings::empty ();
564 : }
565 : else
566 : {
567 : // we need to get the substitutions argument mappings but also remember
568 : // that we have an implicit Self argument which we must be careful to
569 : // respect
570 381 : rust_assert (!used_arguments.is_empty ());
571 : }
572 :
573 : // now actually perform a substitution
574 7658 : auto args = get_mappings_from_generic_args (
575 : *generic_args,
576 7658 : Resolver::TypeCheckContext::get ()->regions_from_generic_args (
577 15316 : *generic_args));
578 :
579 7657 : apply_argument_mappings (args, is_super_trait);
580 7657 : }
581 :
582 : void
583 13042 : TypeBoundPredicate::apply_argument_mappings (
584 : SubstitutionArgumentMappings &arguments, bool is_super_trait)
585 : {
586 13042 : used_arguments = arguments;
587 13042 : error_flag |= used_arguments.is_error ();
588 13042 : auto &subst_mappings = used_arguments;
589 :
590 13042 : bool substs_need_bounds_check = !is_super_trait;
591 29513 : for (auto &sub : get_substs ())
592 : {
593 16471 : SubstitutionArg arg = SubstitutionArg::error ();
594 16471 : bool ok
595 16471 : = subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
596 16471 : if (ok && arg.get_tyty () != nullptr)
597 15220 : sub.fill_param_ty (subst_mappings, subst_mappings.get_locus (),
598 : substs_need_bounds_check);
599 : }
600 :
601 : // Associated type binding args (Iterator<Item = i32>) are consumed
602 : // by BaseType::satisfies_bound at check time
603 17476 : for (auto &super_trait : super_traits)
604 : {
605 4434 : auto adjusted
606 : = super_trait.adjust_mappings_for_this (used_arguments,
607 4434 : true /*trait mode*/);
608 4434 : super_trait.apply_argument_mappings (adjusted, is_super_trait);
609 4434 : }
610 13042 : }
611 :
612 : bool
613 0 : TypeBoundPredicate::contains_item (const std::string &search) const
614 : {
615 0 : auto trait_ref = get ();
616 0 : const Resolver::TraitItemReference *trait_item_ref = nullptr;
617 0 : return trait_ref->lookup_trait_item (search, &trait_item_ref);
618 : }
619 :
620 : tl::optional<TypeBoundPredicateItem>
621 16933 : TypeBoundPredicate::lookup_associated_item (const std::string &search) const
622 : {
623 16933 : auto trait_ref = get ();
624 16933 : const Resolver::TraitItemReference *trait_item_ref = nullptr;
625 16933 : if (trait_ref->lookup_trait_item (search, &trait_item_ref,
626 : false /*lookup supers*/))
627 15302 : return TypeBoundPredicateItem (*this, trait_item_ref);
628 :
629 1747 : for (auto &super_trait : super_traits)
630 : {
631 238 : auto lookup = super_trait.lookup_associated_item (search);
632 238 : if (lookup.has_value ())
633 122 : return lookup;
634 238 : }
635 :
636 1509 : return tl::nullopt;
637 : }
638 :
639 22357 : TypeBoundPredicateItem::TypeBoundPredicateItem (
640 : const TypeBoundPredicate parent,
641 : const Resolver::TraitItemReference *trait_item_ref)
642 22357 : : parent (parent), trait_item_ref (trait_item_ref)
643 22357 : {}
644 :
645 25140 : TypeBoundPredicateItem::TypeBoundPredicateItem (
646 : const TypeBoundPredicateItem &other)
647 25140 : : parent (other.parent), trait_item_ref (other.trait_item_ref)
648 25140 : {}
649 :
650 : TypeBoundPredicateItem &
651 6977 : TypeBoundPredicateItem::operator= (const TypeBoundPredicateItem &other)
652 : {
653 6977 : parent = other.parent;
654 6977 : trait_item_ref = other.trait_item_ref;
655 :
656 6977 : return *this;
657 : }
658 :
659 : TypeBoundPredicateItem
660 6982 : TypeBoundPredicateItem::error ()
661 : {
662 6982 : return TypeBoundPredicateItem (TypeBoundPredicate::error (), nullptr);
663 : }
664 :
665 : bool
666 7101 : TypeBoundPredicateItem::is_error () const
667 : {
668 7101 : return parent.is_error () || trait_item_ref == nullptr;
669 : }
670 :
671 : const TypeBoundPredicate *
672 1827 : TypeBoundPredicateItem::get_parent () const
673 : {
674 1827 : return &parent;
675 : }
676 :
677 : tl::optional<TypeBoundPredicateItem>
678 6916 : TypeBoundPredicate::lookup_associated_item (
679 : const Resolver::TraitItemReference *ref) const
680 : {
681 6916 : return lookup_associated_item (ref->get_identifier ());
682 : }
683 :
684 : BaseType *
685 9226 : TypeBoundPredicateItem::get_tyty_for_receiver (const TyTy::BaseType *receiver)
686 : {
687 9226 : auto ctx = Resolver::TypeCheckContext::get ();
688 :
689 9226 : TyTy::BaseType *trait_item_tyty = get_raw_item ()->get_tyty ();
690 9226 : if (parent.get_substitution_arguments ().is_empty ())
691 : return trait_item_tyty;
692 :
693 : // set up the self mapping
694 9226 : SubstitutionArgumentMappings gargs = parent.get_substitution_arguments ();
695 9226 : rust_assert (!gargs.is_empty ());
696 :
697 : // The associated-type projection we are rebasing is stored in trait
698 : // coordinates
699 : //
700 : // Self/X for trait SliceIndex<X>
701 : //
702 : // The predicate's own SubstitutionParamMappings may have already been
703 : // mutated by SubstitutionParamMapping::fill_param_ty when the bound is a
704 : // where-clause like I: SliceIndex<[T]>: substituting Self with the
705 : // ParamType I rebinds the predicate's first param from Self to I.
706 : // Building adjusted_mappings from those renamed mappings would make
707 : // name-based lookup (get_argument_for_symbol) miss the trait's Self/X
708 : // symbols inside the projection.
709 9226 : const auto &trait_substs = parent.get ()->get_trait_substs ();
710 9226 : rust_assert (gargs.get_mappings ().size () <= trait_substs.size ());
711 :
712 9226 : std::vector<SubstitutionArg> adjusted_mappings;
713 23066 : for (size_t i = 0; i < gargs.get_mappings ().size (); i++)
714 : {
715 13840 : auto &mapping = gargs.get_mappings ().at (i);
716 :
717 13840 : bool is_implicit_self = i == 0;
718 13840 : TyTy::BaseType *argument
719 13840 : = is_implicit_self ? receiver->clone () : mapping.get_tyty ();
720 :
721 13840 : adjusted_mappings.emplace_back (&trait_substs.at (i), argument);
722 : }
723 :
724 9226 : SubstitutionArgumentMappings adjusted (adjusted_mappings, {},
725 : gargs.get_regions (),
726 : gargs.get_locus (),
727 9226 : true /* trait-mode-flag */);
728 9226 : TyTy::BaseType *res
729 9226 : = Resolver::SubstMapperInternal::Resolve (trait_item_tyty, adjusted);
730 :
731 9226 : if (res != trait_item_tyty)
732 : {
733 9226 : auto &mappings = Analysis::Mappings::get ();
734 9226 : HirId fresh = mappings.get_next_hir_id ();
735 9226 : res->set_ref (fresh);
736 9226 : res->set_ty_ref (fresh);
737 9226 : ctx->insert_implicit_type (fresh, res);
738 : }
739 :
740 9226 : return res;
741 9226 : }
742 : bool
743 132694 : TypeBoundPredicate::is_error () const
744 : {
745 132694 : auto context = Resolver::TypeCheckContext::get ();
746 :
747 132694 : Resolver::TraitReference *ref = nullptr;
748 132694 : bool ok = context->lookup_trait_reference (reference, &ref);
749 :
750 132694 : return !ok || error_flag;
751 : }
752 :
753 : BaseType *
754 47468 : TypeBoundPredicate::handle_substitions (
755 : SubstitutionArgumentMappings &subst_mappings)
756 : {
757 106699 : for (auto &sub : get_substs ())
758 : {
759 59231 : if (sub.get_param_ty () == nullptr)
760 0 : continue;
761 :
762 59231 : auto p = sub.get_param_ty ();
763 59231 : BaseType *r = p->resolve ();
764 59231 : BaseType *s = Resolver::SubstMapperInternal::Resolve (r, subst_mappings);
765 :
766 59231 : p->set_ty_ref (s->get_ty_ref ());
767 : }
768 :
769 : // FIXME more error handling at some point
770 : // used_arguments = subst_mappings;
771 : // error_flag |= used_arguments.is_error ();
772 :
773 47468 : return nullptr;
774 : }
775 :
776 : bool
777 648 : TypeBoundPredicate::requires_generic_args () const
778 : {
779 648 : if (is_error ())
780 : return false;
781 :
782 648 : return substitutions.size () > 1;
783 : }
784 :
785 : bool
786 0 : TypeBoundPredicate::contains_associated_types () const
787 : {
788 0 : return get_num_associated_bindings () > 0;
789 : }
790 :
791 : size_t
792 236 : TypeBoundPredicate::get_num_associated_bindings () const
793 : {
794 236 : size_t count = 0;
795 :
796 236 : get_trait_hierachy ([&count] (const Resolver::TraitReference &ref) {
797 658 : for (const auto &trait_item : ref.get_trait_items ())
798 : {
799 422 : bool is_associated_type
800 422 : = trait_item.get_trait_item_type ()
801 422 : == Resolver::TraitItemReference::TraitItemType::TYPE;
802 422 : if (is_associated_type)
803 238 : count++;
804 : }
805 236 : });
806 :
807 236 : return count;
808 : }
809 :
810 : void
811 236 : TypeBoundPredicate::get_trait_hierachy (
812 : std::function<void (const Resolver::TraitReference &)> callback) const
813 : {
814 236 : auto trait_ref = get ();
815 236 : callback (*trait_ref);
816 :
817 236 : for (auto &super : super_traits)
818 : {
819 0 : const auto &super_trait_ref = *super.get ();
820 0 : callback (super_trait_ref);
821 0 : super.get_trait_hierachy (callback);
822 : }
823 236 : }
824 :
825 : TypeBoundPredicateItem
826 119 : TypeBoundPredicate::lookup_associated_type (const std::string &search)
827 : {
828 119 : tl::optional<TypeBoundPredicateItem> item = lookup_associated_item (search);
829 :
830 : // only need to check that it is infact an associated type because other
831 : // wise if it was not found it will just be an error node anyway
832 119 : if (item.has_value ())
833 : {
834 119 : const auto raw = item->get_raw_item ();
835 119 : if (raw->get_trait_item_type ()
836 : != Resolver::TraitItemReference::TraitItemType::TYPE)
837 0 : return TypeBoundPredicateItem::error ();
838 : }
839 119 : return item.value ();
840 119 : }
841 :
842 : std::vector<TypeBoundPredicateItem>
843 0 : TypeBoundPredicate::get_associated_type_items ()
844 : {
845 0 : std::vector<TypeBoundPredicateItem> items;
846 0 : auto trait_ref = get ();
847 0 : for (const auto &trait_item : trait_ref->get_trait_items ())
848 : {
849 0 : bool is_associated_type
850 0 : = trait_item.get_trait_item_type ()
851 0 : == Resolver::TraitItemReference::TraitItemType::TYPE;
852 0 : if (is_associated_type)
853 0 : items.emplace_back (*this, &trait_item);
854 : }
855 0 : return items;
856 : }
857 :
858 : bool
859 1620 : TypeBoundPredicate::is_equal (const TypeBoundPredicate &other) const
860 : {
861 : // check they match the same trait reference
862 1620 : if (reference != other.reference)
863 : return false;
864 :
865 : // check that the generics match
866 1602 : if (get_num_substitutions () != other.get_num_substitutions ())
867 : return false;
868 :
869 : // then match the generics applied
870 3358 : for (size_t i = 0; i < get_num_substitutions (); i++)
871 : {
872 1756 : SubstitutionParamMapping a = substitutions.at (i);
873 1756 : SubstitutionParamMapping b = other.substitutions.at (i);
874 :
875 1756 : auto ap = a.get_param_ty ();
876 1756 : auto bp = b.get_param_ty ();
877 :
878 1756 : BaseType *apd = ap->destructure ();
879 1756 : BaseType *bpd = bp->destructure ();
880 :
881 1756 : if (!Resolver::types_compatable (TyTy::TyWithLocation (apd),
882 1756 : TyTy::TyWithLocation (bpd),
883 : UNKNOWN_LOCATION, false))
884 0 : return false;
885 : }
886 :
887 : return true;
888 : }
889 :
890 : bool
891 9356 : TypeBoundPredicate::validate_type_implements_super_traits (
892 : TyTy::BaseType &self, HIR::Type &impl_type, HIR::Type &trait) const
893 : {
894 9356 : if (get_polarity () != BoundPolarity::RegularBound)
895 : return true;
896 :
897 9349 : auto &ptref = *get ();
898 13370 : for (auto &super : super_traits)
899 : {
900 4022 : if (super.get_polarity () != BoundPolarity::RegularBound)
901 0 : continue;
902 :
903 4022 : if (!super.validate_type_implements_this (self, impl_type, trait))
904 : {
905 1 : auto &sptref = *super.get ();
906 :
907 : // emit error
908 1 : std::string fixit1
909 1 : = "required by this bound in: " + ptref.get_name ();
910 2 : std::string fixit2 = "the trait " + sptref.get_name ()
911 2 : + " is not implemented for "
912 2 : + impl_type.to_string ();
913 :
914 1 : rich_location r (line_table, trait.get_locus ());
915 1 : r.add_fixit_insert_after (super.get_locus (), fixit1.c_str ());
916 1 : r.add_fixit_insert_after (trait.get_locus (), fixit2.c_str ());
917 1 : rust_error_at (r, ErrorCode::E0277,
918 : "the trait bound %<%s: %s%> is not satisfied",
919 3 : impl_type.to_string ().c_str (),
920 1 : sptref.get_name ().c_str ());
921 :
922 1 : return false;
923 1 : }
924 :
925 4021 : if (!super.validate_type_implements_super_traits (self, impl_type, trait))
926 : return false;
927 : }
928 :
929 : return true;
930 : }
931 :
932 : bool
933 4022 : TypeBoundPredicate::validate_type_implements_this (TyTy::BaseType &self,
934 : HIR::Type &impl_type,
935 : HIR::Type &trait) const
936 : {
937 4022 : const auto &ptref = *get ();
938 4022 : auto probed_bounds
939 4022 : = Resolver::TypeBoundsProbe::Probe (&self, ptref.get_hir_trait_ref ());
940 4022 : for (auto &elem : probed_bounds)
941 : {
942 4021 : auto &tref = *(elem.first);
943 4021 : if (ptref.is_equal (tref))
944 4022 : return true;
945 : }
946 :
947 : return false;
948 4022 : }
949 :
950 : // trait item reference
951 :
952 : const Resolver::TraitItemReference *
953 31667 : TypeBoundPredicateItem::get_raw_item () const
954 : {
955 31667 : return trait_item_ref;
956 : }
957 :
958 : bool
959 0 : TypeBoundPredicateItem::needs_implementation () const
960 : {
961 0 : return !get_raw_item ()->is_optional ();
962 : }
963 :
964 : location_t
965 5 : TypeBoundPredicateItem::get_locus () const
966 : {
967 5 : return get_raw_item ()->get_locus ();
968 : }
969 :
970 : // TypeBoundsMappings
971 :
972 6943694 : TypeBoundsMappings::TypeBoundsMappings (
973 : std::vector<TypeBoundPredicate> specified_bounds)
974 6943694 : : specified_bounds (std::move (specified_bounds))
975 6943694 : {}
976 :
977 : std::vector<TypeBoundPredicate> &
978 111182 : TypeBoundsMappings::get_specified_bounds ()
979 : {
980 111182 : return specified_bounds;
981 : }
982 :
983 : const std::vector<TypeBoundPredicate> &
984 5855977 : TypeBoundsMappings::get_specified_bounds () const
985 : {
986 5855977 : return specified_bounds;
987 : }
988 :
989 : TypeBoundPredicate
990 0 : TypeBoundsMappings::lookup_predicate (DefId id)
991 : {
992 0 : for (auto &b : specified_bounds)
993 : {
994 0 : if (b.get_id () == id)
995 0 : return b;
996 : }
997 0 : return TypeBoundPredicate::error ();
998 : }
999 :
1000 : size_t
1001 174227 : TypeBoundsMappings::num_specified_bounds () const
1002 : {
1003 174227 : return specified_bounds.size ();
1004 : }
1005 :
1006 : std::string
1007 35209 : TypeBoundsMappings::raw_bounds_as_string () const
1008 : {
1009 35209 : std::string buf;
1010 35444 : for (size_t i = 0; i < specified_bounds.size (); i++)
1011 : {
1012 235 : const TypeBoundPredicate &b = specified_bounds.at (i);
1013 235 : bool has_next = (i + 1) < specified_bounds.size ();
1014 936 : buf += b.as_string () + (has_next ? " + " : "");
1015 : }
1016 35209 : return buf;
1017 : }
1018 :
1019 : std::string
1020 35038 : TypeBoundsMappings::bounds_as_string () const
1021 : {
1022 70076 : return "bounds:[" + raw_bounds_as_string () + "]";
1023 : }
1024 :
1025 : std::string
1026 896 : TypeBoundsMappings::raw_bounds_as_name () const
1027 : {
1028 896 : std::string buf;
1029 1803 : for (size_t i = 0; i < specified_bounds.size (); i++)
1030 : {
1031 907 : const TypeBoundPredicate &b = specified_bounds.at (i);
1032 907 : bool has_next = (i + 1) < specified_bounds.size ();
1033 3617 : buf += b.as_name () + (has_next ? " + " : "");
1034 : }
1035 :
1036 896 : return buf;
1037 : }
1038 :
1039 : void
1040 55975 : TypeBoundsMappings::add_bound (const TypeBoundPredicate &predicate)
1041 : {
1042 62643 : for (auto &bound : specified_bounds)
1043 : {
1044 29356 : bool same_trait_ref_p = bound.get_id () == predicate.get_id ();
1045 6668 : if (same_trait_ref_p)
1046 55975 : return;
1047 : }
1048 :
1049 33287 : specified_bounds.push_back (predicate);
1050 : }
1051 :
1052 : } // namespace TyTy
1053 : } // namespace Rust
|
