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