Line data Source code
1 : // Copyright (C) 2020-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-item.h"
20 : #include "rust-system.h"
21 : #include "rust-type-util.h"
22 : #include "rust-diagnostics.h"
23 : #include "rust-hir-map.h"
24 : #include "rust-hir-type-check-implitem.h"
25 : #include "rust-hir-type-check-item.h"
26 : #include "rust-hir-type-check.h"
27 : #include "rust-casts.h"
28 : #include "rust-mapping-common.h"
29 : #include "rust-rib.h"
30 : #include "rust-unify.h"
31 : #include "rust-coercion.h"
32 : #include "rust-hir-type-bounds.h"
33 : #include "rust-hir-trait-resolve.h"
34 : #include "rust-substitution-mapper.h"
35 : #include "rust-finalized-name-resolution-context.h"
36 :
37 : namespace Rust {
38 : namespace Resolver {
39 :
40 : const size_t kNormalizeProjectionLimit = 10;
41 :
42 : bool
43 5896546 : query_type (HirId reference, TyTy::BaseType **result)
44 : {
45 5896546 : auto &mappings = Analysis::Mappings::get ();
46 5896546 : TypeCheckContext *context = TypeCheckContext::get ();
47 :
48 5896546 : if (context->lookup_type (reference, result))
49 : return true;
50 :
51 85669 : if (context->query_in_progress (reference))
52 : return false;
53 :
54 67253 : context->insert_query (reference);
55 :
56 67253 : std::pair<HIR::Enum *, HIR::EnumItem *> enum_candidiate
57 67253 : = mappings.lookup_hir_enumitem (reference);
58 134506 : bool enum_candidiate_ok
59 67253 : = enum_candidiate.first != nullptr && enum_candidiate.second != nullptr;
60 67253 : if (enum_candidiate_ok)
61 : {
62 4773 : HIR::Enum *parent = enum_candidiate.first;
63 4773 : HIR::EnumItem *enum_item = enum_candidiate.second;
64 4773 : rust_debug_loc (enum_item->get_locus (), "resolved item {%u} to",
65 : reference);
66 :
67 4773 : *result = TypeCheckItem::Resolve (*parent);
68 :
69 4773 : context->query_completed (reference);
70 4773 : return true;
71 : }
72 :
73 62480 : if (auto item = mappings.hir.items.lookup (reference))
74 : {
75 3121 : rust_debug_loc (item.value ()->get_locus (), "resolved item {%u} to",
76 : reference);
77 :
78 3121 : DefId item_defid = item.value ()->get_mappings ().get_defid ();
79 3121 : bool is_local
80 3121 : = item_defid.crateNum == mappings.crate.get_current_crate ();
81 3121 : bool is_fn
82 3121 : = item.value ()->get_item_kind () == HIR::Item::ItemKind::Function;
83 3121 : bool is_const_fn = false;
84 3121 : if (is_fn)
85 : {
86 210 : auto &fn = *static_cast<HIR::Function *> (item.value ());
87 210 : is_const_fn = fn.get_qualifiers ().is_const ();
88 : }
89 :
90 210 : bool needs_full_resolve_for_const
91 210 : = is_fn && context->const_context_p () && is_const_fn;
92 3121 : if (is_fn && is_local && !needs_full_resolve_for_const)
93 : {
94 189 : HIR::Function &fn = *static_cast<HIR::Function *> (item.value ());
95 189 : *result = TypeCheckItem::ResolveFunctionSignature (fn);
96 189 : }
97 2932 : else if (item.value ()->get_item_kind () == HIR::Item::ItemKind::Trait
98 2932 : && is_local && !context->const_context_p ())
99 : {
100 412 : HIR::Trait &trait = *static_cast<HIR::Trait *> (item.value ());
101 412 : *result = TypeCheckItem::ResolveTraitSignature (trait);
102 : }
103 : else
104 2520 : *result = TypeCheckItem::Resolve (*item.value ());
105 :
106 3100 : context->query_completed (reference);
107 3100 : return true;
108 : }
109 :
110 59359 : if (auto impl_item = mappings.lookup_hir_implitem (reference))
111 : {
112 15619 : auto impl_block
113 15619 : = mappings.lookup_hir_impl_block (impl_item->second).value ();
114 15619 : auto lifetime_pin = context->push_clean_lifetime_resolver (true);
115 :
116 15619 : bool failure_flag = false;
117 15619 : auto substitutions
118 : = TypeCheckItem::ResolveImplBlockSubstitutions (*impl_block,
119 15619 : failure_flag);
120 15619 : if (failure_flag)
121 : {
122 1 : *result
123 1 : = TypeCheckItem::ResolveImplItem (*impl_block, *impl_item->first);
124 1 : context->query_completed (reference);
125 1 : return true;
126 : }
127 :
128 15618 : TyTy::BaseType *self = nullptr;
129 15618 : bool ok
130 15618 : = query_type (impl_block->get_type ().get_mappings ().get_hirid (),
131 : &self);
132 15618 : if (!ok)
133 : {
134 0 : context->query_completed (reference);
135 0 : return false;
136 : }
137 :
138 15618 : tl::optional<ImplTraitFrameGuard> guard;
139 15618 : if (impl_block->has_trait_ref ())
140 : {
141 14624 : HIR::TypePath &ref = impl_block->get_trait_ref ();
142 14624 : auto trait_reference = TraitResolver::Resolve (ref);
143 14624 : if (trait_reference->is_error ())
144 : {
145 0 : context->query_completed (reference);
146 0 : return false;
147 : }
148 :
149 14624 : auto specified_bound = TypeCheckBase::ResolvePredicateFromBound (
150 14624 : ref, impl_block->get_type (), impl_block->get_polarity ());
151 :
152 14624 : std::map<DefId, AssocTypeEntry> assoc_types_by_trait_item;
153 14624 : std::vector<const TraitItemReference *> trait_item_refs;
154 14624 : TypeCheckItem::ResolveImplTraitAssociatedTypes (
155 : context, *impl_block, specified_bound, self, substitutions,
156 : assoc_types_by_trait_item, trait_item_refs);
157 :
158 14589 : ImplTraitContextFrame frame{trait_reference, self,
159 14589 : std::move (assoc_types_by_trait_item)};
160 14589 : guard.emplace (frame);
161 14589 : }
162 :
163 : // found an impl item
164 15583 : rust_debug_loc (impl_item->first->get_locus (),
165 : "resolved impl-item {%u} to", reference);
166 :
167 15583 : DefId item_defid = impl_item->first->get_impl_mappings ().get_defid ();
168 15583 : bool is_local
169 15583 : = item_defid.crateNum == mappings.crate.get_current_crate ();
170 15583 : bool is_fn
171 15583 : = impl_item->first->get_impl_item_type () == HIR::ImplItem::FUNCTION;
172 15583 : bool is_const_fn = false;
173 15583 : if (is_fn)
174 : {
175 15523 : auto &fn = *static_cast<HIR::Function *> (impl_item->first);
176 15523 : is_const_fn = fn.get_qualifiers ().is_const ();
177 : }
178 :
179 15523 : bool needs_full_resolve_for_const
180 15523 : = is_fn && context->const_context_p () && is_const_fn;
181 15583 : if (is_fn && is_local && !needs_full_resolve_for_const)
182 : {
183 15185 : HIR::Function &fn = *static_cast<HIR::Function *> (impl_item->first);
184 15185 : *result = TypeCheckImplItem::ResolveFunctionSignature (
185 : *impl_block, fn, self, std::move (substitutions));
186 15185 : }
187 : else
188 398 : *result = TypeCheckImplItem::Resolve (*impl_block, *impl_item->first,
189 : self, std::move (substitutions));
190 :
191 15513 : context->query_completed (reference);
192 15513 : return true;
193 15514 : }
194 :
195 : // is it an impl_type?
196 43740 : if (auto impl_block_by_type = mappings.lookup_impl_block_type (reference))
197 : {
198 : // found an impl item
199 43612 : HIR::ImplBlock *impl = impl_block_by_type.value ();
200 43612 : rust_debug_loc (impl->get_locus (), "resolved impl block type {%u} to",
201 : reference);
202 :
203 : // this could be recursive to the root type
204 43612 : if (impl->has_type ())
205 : {
206 43612 : HIR::Type &ty = impl->get_type ();
207 43612 : NodeId ref_node_id = UNKNOWN_NODEID;
208 43612 : NodeId ast_node_id = ty.get_mappings ().get_nodeid ();
209 :
210 43612 : auto &nr_ctx = Resolver2_0::FinalizedNameResolutionContext::get ();
211 :
212 : // assign the ref_node_id if we've found something
213 43612 : nr_ctx.lookup (ast_node_id, Resolver2_0::Namespace::Types)
214 74979 : .map ([&ref_node_id] (NodeId resolved) { ref_node_id = resolved; });
215 :
216 43612 : if (ref_node_id != UNKNOWN_NODEID)
217 : {
218 31367 : tl::optional<HirId> hid
219 31367 : = mappings.lookup_node_to_hir (ref_node_id);
220 31367 : if (hid.has_value () && context->query_in_progress (hid.value ()))
221 : {
222 91 : context->query_completed (reference);
223 91 : return false;
224 : }
225 : }
226 : }
227 :
228 43521 : *result = TypeCheckItem::ResolveImplBlockSelf (*impl);
229 43500 : context->query_completed (reference);
230 43500 : return true;
231 : }
232 :
233 : // is it an extern item?
234 128 : if (auto extern_item = mappings.lookup_hir_extern_item (reference))
235 : {
236 124 : auto block = mappings.hir.extern_blocks.lookup (extern_item->second);
237 124 : rust_assert (block.has_value ());
238 :
239 124 : *result
240 124 : = TypeCheckTopLevelExternItem::Resolve (*extern_item.value ().first,
241 124 : *block.value ());
242 124 : context->query_completed (reference);
243 124 : return true;
244 : }
245 :
246 : // more?
247 4 : location_t possible_locus = mappings.lookup_location (reference);
248 4 : rust_debug_loc (possible_locus, "query system failed to resolve: [%u]",
249 : reference);
250 4 : context->query_completed (reference);
251 :
252 4 : return false;
253 : }
254 :
255 : bool
256 4926865 : types_compatable (TyTy::TyWithLocation lhs, TyTy::TyWithLocation rhs,
257 : location_t unify_locus, bool emit_errors, bool check_bounds)
258 : {
259 4926865 : TyTy::BaseType *result
260 4926865 : = unify_site_and (UNKNOWN_HIRID, lhs, rhs, unify_locus, emit_errors,
261 : false /*commit*/, true /*infer*/, true /*cleanup*/,
262 : check_bounds);
263 4926858 : return result->get_kind () != TyTy::TypeKind::ERROR;
264 : }
265 :
266 : TyTy::BaseType *
267 39838 : unify_site (HirId id, TyTy::TyWithLocation lhs, TyTy::TyWithLocation rhs,
268 : location_t unify_locus)
269 : {
270 39838 : TyTy::BaseType *expected = lhs.get_ty ();
271 39838 : TyTy::BaseType *expr = rhs.get_ty ();
272 :
273 39838 : rust_debug ("unify_site id={%u} expected={%s} expr={%s}", id,
274 : expected->debug_str ().c_str (), expr->debug_str ().c_str ());
275 :
276 39838 : std::vector<UnifyRules::CommitSite> commits;
277 39838 : std::vector<UnifyRules::InferenceSite> infers;
278 39838 : return UnifyRules::Resolve (lhs, rhs, unify_locus, true /*commit*/,
279 : true /*emit_error*/, true /*check_bounds*/,
280 39838 : false /*infer*/, commits, infers);
281 39838 : }
282 :
283 : TyTy::BaseType *
284 6159888 : unify_site_and (HirId id, TyTy::TyWithLocation lhs, TyTy::TyWithLocation rhs,
285 : location_t unify_locus, bool emit_errors, bool commit_if_ok,
286 : bool implicit_infer_vars, bool cleanup, bool check_bounds,
287 : bool allow_never_coercion)
288 : {
289 6159888 : TypeCheckContext &context = *TypeCheckContext::get ();
290 :
291 6159888 : TyTy::BaseType *expected = lhs.get_ty ();
292 6159888 : TyTy::BaseType *expr = rhs.get_ty ();
293 :
294 6159889 : rust_debug_loc (unify_locus,
295 : "begin unify_site_and commit %s infer %s check_bounds %s "
296 : "id={%u} expected={%s} expr={%s}",
297 : commit_if_ok ? "true" : "false",
298 : implicit_infer_vars ? "true" : "false",
299 : check_bounds ? "true" : "false", id == UNKNOWN_HIRID ? 0 : id,
300 : expected->debug_str ().c_str (), expr->debug_str ().c_str ());
301 :
302 6159888 : std::vector<UnifyRules::CommitSite> commits;
303 6159888 : std::vector<UnifyRules::InferenceSite> infers;
304 6159888 : TyTy::BaseType *result
305 6159888 : = UnifyRules::Resolve (lhs, rhs, unify_locus, false /*commit inline*/,
306 : emit_errors, check_bounds, implicit_infer_vars,
307 : commits, infers, nullptr, allow_never_coercion);
308 6159874 : bool ok = result->get_kind () != TyTy::TypeKind::ERROR;
309 :
310 6159875 : rust_debug_loc (unify_locus,
311 : "unify_site_and done ok=%s commit %s infer %s id={%u} "
312 : "expected={%s} expr={%s}",
313 : ok ? "true" : "false", commit_if_ok ? "true" : "false",
314 : implicit_infer_vars ? "true" : "false",
315 : id == UNKNOWN_HIRID ? 0 : id, expected->debug_str ().c_str (),
316 : expr->debug_str ().c_str ());
317 :
318 6159874 : if (ok && commit_if_ok)
319 : {
320 291761 : for (auto &c : commits)
321 : {
322 176860 : UnifyRules::commit (c.lhs, c.rhs, c.resolved);
323 : }
324 : }
325 6044973 : else if (cleanup)
326 : {
327 6089006 : for (auto &i : infers)
328 : {
329 44386 : if (i.param != nullptr)
330 : {
331 44342 : i.param->set_ref (i.pref);
332 44342 : i.param->set_ty_ref (i.ptyref);
333 : }
334 :
335 : // remove the inference variable
336 44386 : context.clear_type (i.infer);
337 : // FIXME: Don't delete - result might point to this
338 : // delete i.infer;
339 : }
340 : }
341 6159874 : return result;
342 6159874 : }
343 :
344 : TyTy::BaseType *
345 51848 : coercion_site (HirId id, TyTy::TyWithLocation lhs, TyTy::TyWithLocation rhs,
346 : location_t locus)
347 : {
348 51848 : TyTy::BaseType *expected = lhs.get_ty ();
349 51848 : TyTy::BaseType *expr = rhs.get_ty ();
350 :
351 51848 : rust_debug ("coercion_site id={%u} expected={%s} expr={%s}", id,
352 : expected->debug_str ().c_str (), expr->debug_str ().c_str ());
353 :
354 51848 : auto context = TypeCheckContext::get ();
355 51848 : if (expected->get_kind () == TyTy::TypeKind::ERROR
356 51848 : || expr->get_kind () == TyTy::TypeKind::ERROR)
357 : return expr;
358 :
359 : // can we autoderef it?
360 51826 : auto result = TypeCoercionRules::Coerce (expr, expected, locus,
361 51826 : true /*allow-autodref*/);
362 :
363 : // the result needs to be unified
364 51819 : TyTy::BaseType *receiver = expr;
365 51819 : if (!result.is_error ())
366 : {
367 51756 : receiver = result.tyty;
368 : }
369 :
370 51819 : rust_debug ("coerce_default_unify(a={%s}, b={%s})",
371 : receiver->debug_str ().c_str (), expected->debug_str ().c_str ());
372 51819 : TyTy::BaseType *coerced
373 51819 : = unify_site_and (id, lhs,
374 51819 : TyTy::TyWithLocation (receiver, rhs.get_locus ()), locus,
375 : true /*emit_error*/, true /*commit*/, true /*infer*/,
376 : true /*cleanup*/);
377 51819 : context->insert_autoderef_mappings (id, std::move (result.adjustments));
378 51819 : return coerced;
379 51819 : }
380 :
381 : TyTy::BaseType *
382 391562 : try_coercion (HirId id, TyTy::TyWithLocation lhs, TyTy::TyWithLocation rhs,
383 : location_t locus)
384 : {
385 391562 : TyTy::BaseType *expected = lhs.get_ty ();
386 391562 : TyTy::BaseType *expr = rhs.get_ty ();
387 :
388 391562 : rust_debug ("try_coercion_site id={%u} expected={%s} expr={%s}", id,
389 : expected->debug_str ().c_str (), expr->debug_str ().c_str ());
390 :
391 391562 : auto result = TypeCoercionRules::TryCoerce (expr, expected, locus,
392 391562 : true /*allow-autodref*/);
393 391562 : if (result.is_error ())
394 295273 : return new TyTy::ErrorType (id);
395 :
396 96289 : return result.tyty;
397 391562 : }
398 :
399 : TyTy::BaseType *
400 6603 : cast_site (HirId id, TyTy::TyWithLocation from, TyTy::TyWithLocation to,
401 : location_t cast_locus)
402 : {
403 6603 : rust_debug ("cast_site id={%u} from={%s} to={%s}", id,
404 : from.get_ty ()->debug_str ().c_str (),
405 : to.get_ty ()->debug_str ().c_str ());
406 :
407 6603 : auto context = TypeCheckContext::get ();
408 6603 : if (from.get_ty ()->get_kind () == TyTy::TypeKind::ERROR
409 6603 : || to.get_ty ()->get_kind () == TyTy::TypeKind::ERROR)
410 : return to.get_ty ();
411 :
412 : // do the cast
413 6561 : auto result = TypeCastRules::resolve (cast_locus, from, to);
414 :
415 : // we assume error has already been emitted
416 6561 : if (result.is_error ())
417 : return to.get_ty ();
418 :
419 : // the result needs to be unified
420 6544 : TyTy::BaseType *casted_result = result.tyty;
421 6544 : rust_debug ("cast_default_unify(a={%s}, b={%s})",
422 : casted_result->debug_str ().c_str (),
423 : to.get_ty ()->debug_str ().c_str ());
424 :
425 6544 : TyTy::BaseType *casted
426 6544 : = unify_site (id, to,
427 6544 : TyTy::TyWithLocation (casted_result, from.get_locus ()),
428 : cast_locus);
429 6544 : context->insert_cast_autoderef_mappings (id, std::move (result.adjustments));
430 6544 : return casted;
431 6561 : }
432 :
433 : AssociatedImplTrait *
434 12819 : lookup_associated_impl_block (const TyTy::TypeBoundPredicate &bound,
435 : TyTy::BaseType *binding, bool *ambigious)
436 : {
437 12819 : auto context = TypeCheckContext::get ();
438 :
439 : // setup any associated type mappings for the specified bonds and this
440 : // type
441 12819 : auto candidates
442 12819 : = TypeBoundsProbe::Probe (binding, bound.get ()->get_hir_trait_ref ());
443 12819 : std::vector<AssociatedImplTrait *> associated_impl_traits;
444 28971 : for (auto &probed_bound : candidates)
445 : {
446 16152 : HIR::ImplBlock *associated_impl = probed_bound.second;
447 :
448 16152 : HirId impl_block_id = associated_impl->get_mappings ().get_hirid ();
449 16152 : AssociatedImplTrait *associated = nullptr;
450 16152 : bool found_impl_trait
451 16152 : = context->lookup_associated_trait_impl (impl_block_id, &associated);
452 16152 : if (found_impl_trait)
453 : {
454 : // compare the bounds from here i think is what we can do:
455 3100 : if (bound.get ()->is_equal (*associated->get_predicate ().get ()))
456 : {
457 3100 : associated_impl_traits.push_back (associated);
458 : }
459 : }
460 : }
461 :
462 12819 : if (associated_impl_traits.empty ())
463 : return nullptr;
464 :
465 : // This code is important when you look at slices for example when
466 : // you have a slice such as:
467 : //
468 : // let slice = &array[1..3]
469 : //
470 : // the higher ranked bounds will end up having an Index trait
471 : // implementation for Range<usize> so we need this code to resolve
472 : // that we have an integer inference variable that needs to become
473 : // a usize
474 : //
475 : // The other complicated issue is that we might have an intrinsic
476 : // which requires the :Clone or Copy bound but the libcore adds
477 : // implementations for all the integral types so when there are
478 : // multiple candidates we need to resolve to the default
479 : // implementation for that type otherwise its an error for
480 : // ambiguous type bounds
481 :
482 : // if we have a non-general inference variable we need to be
483 : // careful about the selection here
484 3061 : bool is_infer_var = binding->get_kind () == TyTy::TypeKind::INFER;
485 3061 : bool is_integer_infervar
486 : = is_infer_var
487 3061 : && static_cast<const TyTy::InferType *> (binding)->get_infer_kind ()
488 3111 : == TyTy::InferType::InferTypeKind::INTEGRAL;
489 50 : bool is_float_infervar
490 : = is_infer_var
491 50 : && static_cast<const TyTy::InferType *> (binding)->get_infer_kind ()
492 3061 : == TyTy::InferType::InferTypeKind::FLOAT;
493 :
494 3061 : AssociatedImplTrait *associate_impl_trait = nullptr;
495 3061 : if (associated_impl_traits.size () == 1)
496 : {
497 : // just go for it
498 3022 : associate_impl_trait = associated_impl_traits.at (0);
499 : }
500 39 : else if (is_integer_infervar)
501 : {
502 0 : TyTy::BaseType *type = nullptr;
503 0 : bool ok = context->lookup_builtin ("i32", &type);
504 0 : rust_assert (ok);
505 :
506 0 : for (auto &impl : associated_impl_traits)
507 : {
508 0 : bool found = impl->get_self ()->is_equal (*type);
509 0 : if (found)
510 : {
511 0 : associate_impl_trait = impl;
512 0 : break;
513 : }
514 : }
515 : }
516 39 : else if (is_float_infervar)
517 : {
518 0 : TyTy::BaseType *type = nullptr;
519 0 : bool ok = context->lookup_builtin ("f64", &type);
520 0 : rust_assert (ok);
521 :
522 0 : for (auto &impl : associated_impl_traits)
523 : {
524 0 : bool found = impl->get_self ()->is_equal (*type);
525 0 : if (found)
526 : {
527 0 : associate_impl_trait = impl;
528 0 : break;
529 : }
530 : }
531 : }
532 :
533 3061 : if (associate_impl_trait == nullptr && ambigious != nullptr)
534 : {
535 38 : *ambigious = true;
536 : }
537 :
538 : return associate_impl_trait;
539 12819 : }
540 :
541 : void
542 12825 : rebind_projection_self_from_fn (TyTy::FnType &fn, TyTy::BaseType *root)
543 : {
544 : // After substitution+monomorphize the fn's substitution clones carry the
545 : // call-site bindings. Inner projections in the return/params can still
546 : // reference the traits formal Self via TyVar(formal.ref) whose type table
547 : // entry resolves to the unbound formal
548 12825 : std::map<HirId, TyTy::BaseGeneric *> bound_by_formal;
549 19446 : for (auto &sub : fn.get_substs ())
550 : {
551 6621 : auto *pty = sub.get_param_ty ();
552 6621 : if (pty == nullptr || pty->get_kind () != TyTy::TypeKind::PARAM
553 13226 : || !pty->can_resolve ())
554 111 : continue;
555 6510 : bound_by_formal[pty->get_ref ()] = pty;
556 : }
557 :
558 12825 : std::function<void (TyTy::BaseType *)> rebind;
559 41110 : rebind = [&] (TyTy::BaseType *ty) {
560 15460 : if (ty == nullptr)
561 : return;
562 :
563 15460 : if (auto *proj = ty->try_as<TyTy::ProjectionType> ())
564 : {
565 203 : auto *self = proj->get_self ();
566 203 : if (self->get_kind () == TyTy::TypeKind::PARAM)
567 : {
568 172 : auto it = bound_by_formal.find (self->get_ref ());
569 172 : if (it != bound_by_formal.end ())
570 158 : proj->set_self (it->second);
571 : }
572 :
573 517 : for (auto &sub : proj->get_substs ())
574 : {
575 314 : auto *param = sub.get_param_ty ();
576 314 : if (param == nullptr || param->get_kind () != TyTy::TypeKind::PARAM
577 628 : || param->can_resolve ())
578 276 : continue;
579 :
580 38 : auto it = bound_by_formal.find (param->get_ref ());
581 38 : if (it == bound_by_formal.end ()
582 38 : || it->second->get_kind () != TyTy::TypeKind::PARAM)
583 0 : continue;
584 :
585 38 : auto *bound = static_cast<TyTy::ParamType *> (it->second);
586 38 : if (bound->can_resolve ())
587 38 : param->set_ty_ref (bound->get_ty_ref ());
588 : }
589 : return;
590 : }
591 :
592 15257 : if (auto *adt = ty->try_as<TyTy::ADTType> ())
593 : {
594 2811 : for (auto &variant : adt->get_variants ())
595 3330 : for (auto &field : variant->get_fields ())
596 1601 : rebind (field->get_field_type ());
597 : return;
598 : }
599 :
600 14175 : if (auto *ref = ty->try_as<TyTy::ReferenceType> ())
601 55 : rebind (ref->get_base ());
602 14120 : else if (auto *ptr = ty->try_as<TyTy::PointerType> ())
603 243 : rebind (ptr->get_base ());
604 13877 : else if (auto *tup = ty->try_as<TyTy::TupleType> ())
605 5532 : for (size_t i = 0; i < tup->num_fields (); i++)
606 736 : rebind (tup->get_field (i));
607 12825 : };
608 :
609 12825 : rebind (root);
610 12825 : }
611 :
612 : TyTy::BaseType *
613 23712 : normalize_projection (TyTy::ProjectionType *proj, location_t locus,
614 : bool emit_errors, bool unify_self)
615 : {
616 24299 : static std::vector<TyTy::ProjectionType *> active_projections;
617 47424 : if (ScopedPush<TyTy::ProjectionType *>::contains (active_projections, proj))
618 : return proj;
619 :
620 23712 : ScopedPush<TyTy::ProjectionType *> guard (active_projections, proj);
621 :
622 23712 : if (!proj->is_trait_position ())
623 : {
624 389 : TyTy::BaseType *base = proj->get ();
625 389 : if (auto *param = base->try_as<TyTy::ParamType> ())
626 : {
627 57 : if (param->can_resolve ())
628 : {
629 57 : TyTy::BaseType *resolved
630 57 : = TyTy::TyVar (param->get_ty_ref ()).get_tyty ();
631 57 : if (!resolved->is<TyTy::ParamType> ())
632 389 : base = resolved;
633 : }
634 : }
635 24059 : if (auto *base_proj = base->try_as<TyTy::ProjectionType> ())
636 0 : return normalize_projection (base_proj, locus, emit_errors, unify_self);
637 : return base;
638 : }
639 :
640 : // special case the discriminant_type lang item
641 23323 : auto &mappings = Analysis::Mappings::get ();
642 23323 : auto *ctx = TypeCheckContext::get ();
643 23323 : if (auto discriminant_type_id
644 23323 : = mappings.lookup_lang_item (LangItem::Kind::DISCRIMINANT_TYPE))
645 : {
646 39195 : if (proj->get_item_defid () == discriminant_type_id.value ())
647 : {
648 79 : TyTy::BaseType *isize_ty = nullptr;
649 79 : bool ok = ctx->lookup_builtin ("isize", &isize_ty);
650 79 : rust_assert (ok);
651 :
652 : // If the self type is a concrete ADT, use its repr.
653 79 : TyTy::BaseType *self = proj->get_self ()->destructure ();
654 79 : if (auto *adt = self->try_as<TyTy::ADTType> ())
655 : {
656 0 : auto *repr = adt->get_repr_options ().repr;
657 0 : if (repr != nullptr)
658 : return repr;
659 : }
660 79 : return isize_ty;
661 : }
662 : }
663 :
664 23244 : ImplTraitContextFrame frame;
665 23244 : if (!ctx->find_matching_impl_trait_frame (*proj->get_trait_ref (),
666 23244 : *proj->get_self (), &frame))
667 : {
668 : // No concrete impl frame check WHERE clause bindings on the self type
669 : //
670 : // fn foo<T: Trait<AssocType = X>>()
671 : //
672 : // normalizes
673 : //
674 : // <T as Trait>::AssocType -> X.
675 :
676 6792 : TyTy::BaseType *self = proj->get_self ()->destructure ();
677 6792 : const DefId item_defid = proj->get_item_defid ();
678 :
679 : // find the name of the associated type from the trait reference
680 6792 : std::string assoc_name;
681 7157 : for (const auto &ti : proj->get_trait_ref ()->get_trait_items ())
682 : {
683 7522 : if (ti.get_mappings ().get_defid () == item_defid)
684 : {
685 6792 : assoc_name = ti.get_identifier ();
686 6792 : break;
687 : }
688 : }
689 :
690 6792 : if (!assoc_name.empty ())
691 : {
692 11430 : for (auto &bound : self->get_specified_bounds ())
693 : {
694 : // The associated type can be declared on a supertrait of
695 : // a bound: see issue-4884
696 : //
697 : // I: SplitIter<Item = T> binds Iterator2::Item,
698 :
699 5077 : auto item = bound.lookup_associated_item (assoc_name);
700 5077 : if (!item.has_value ())
701 1874 : continue;
702 :
703 3210 : auto &item_val = item.value ();
704 3210 : const auto raw_item = item_val.get_raw_item ();
705 3210 : if (raw_item->get_mappings ().get_defid () != item_defid)
706 7 : continue;
707 :
708 3203 : const auto parent = item_val.get_parent ();
709 3203 : const auto &arguments = parent->get_substitution_arguments ();
710 3203 : const auto &binding = arguments.get_binding_args ();
711 3203 : auto it = binding.find (assoc_name);
712 3203 : if (it != binding.end ())
713 439 : return it->second;
714 :
715 2793 : const auto &constraints = arguments.get_constraint_args ();
716 2793 : auto constraint = constraints.find (assoc_name);
717 2793 : if (constraint != constraints.end ())
718 : {
719 29 : TyTy::BaseType *constrained = proj->clone ();
720 29 : constrained->inherit_bounds (*constraint->second);
721 :
722 : // Keep the constrained projection distinct from the canonical
723 : // associated-type declaration.
724 29 : auto &mappings = Analysis::Mappings::get ();
725 29 : HirId fresh = mappings.get_next_hir_id ();
726 29 : constrained->set_ref (fresh);
727 29 : constrained->set_ty_ref (fresh);
728 29 : ctx->insert_implicit_type (fresh, constrained);
729 29 : return constrained;
730 : }
731 : }
732 : }
733 :
734 : // If self is a trait-position projection recursively normalize it first
735 : // so the impl-block lookup below works on a concrete type.
736 6353 : if (auto *self_proj = self->try_as<TyTy::ProjectionType> ())
737 : {
738 12 : if (self_proj->is_trait_position ())
739 : {
740 12 : auto *norm = normalize_projection (self_proj, locus, emit_errors,
741 : unify_self);
742 12 : if (norm != self_proj
743 12 : && norm->get_kind () != TyTy::TypeKind::ERROR)
744 11 : self = norm->destructure ();
745 : }
746 : else
747 : {
748 0 : auto *base = self_proj->get ();
749 0 : if (base && base != self_proj)
750 0 : self = base->destructure ();
751 : }
752 : }
753 :
754 : // Direct impl-block lookup for concrete self types (no active frame).
755 6353 : if (!assoc_name.empty () && self->get_kind () != TyTy::TypeKind::PARAM
756 4079 : && self->get_kind () != TyTy::TypeKind::INFER
757 10432 : && self->get_kind () != TyTy::TypeKind::PROJECTION)
758 : {
759 4067 : auto candidates = TypeBoundsProbe::Probe (
760 4067 : self, proj->get_trait_ref ()->get_hir_trait_ref ());
761 4267 : for (auto &probed : candidates)
762 : {
763 4167 : HIR::ImplBlock *impl_block = probed.second;
764 4167 : if (!impl_block->has_trait_ref ())
765 200 : continue;
766 :
767 3967 : HIR::TypePath &ref = impl_block->get_trait_ref ();
768 3967 : auto *tref = TraitResolver::Resolve (ref);
769 3967 : if (tref->is_error ()
770 3967 : || !tref->is_equal (*proj->get_trait_ref ()))
771 0 : continue;
772 :
773 4136 : for (auto &impl_item : impl_block->get_impl_items ())
774 : {
775 8272 : if (impl_item->get_impl_item_name ().compare (assoc_name)
776 4136 : != 0)
777 169 : continue;
778 :
779 3967 : TyTy::BaseType *result = nullptr;
780 3967 : if (query_type (impl_item->get_impl_mappings ().get_hirid (),
781 : &result))
782 : {
783 : // the impl might not have been checked yet, e.g. when a
784 : // bounds probe resolves a struct field before it
785 3967 : HirId impl_id = impl_block->get_mappings ().get_hirid ();
786 3967 : AssociatedImplTrait *associated = nullptr;
787 3967 : if (!ctx->lookup_associated_trait_impl (impl_id,
788 : &associated))
789 1218 : TypeCheckItem::Resolve (*impl_block);
790 :
791 3925 : if (ctx->lookup_associated_trait_impl (impl_id,
792 : &associated)
793 3925 : && associated != nullptr)
794 : {
795 3925 : auto mapping
796 : = associated->bind_impl_for_projection (*proj,
797 3925 : locus);
798 3925 : if (!mapping.is_error ())
799 3918 : result
800 3918 : = SubstMapperInternal::Resolve (result, mapping);
801 3925 : }
802 :
803 : // impl type aliases are stored as non-trait-position
804 : // ProjectionType; unwrap to base only when there are no
805 : // substitution params (non-GAT)
806 3925 : if (auto *p = result->try_as<TyTy::ProjectionType> ())
807 : {
808 3925 : if (!p->is_trait_position ())
809 : {
810 3925 : bool all_substs_bound = true;
811 4307 : for (auto &s : p->get_substs ())
812 : {
813 550 : auto *sp = s.get_param_ty ();
814 550 : if (sp == nullptr || !sp->can_resolve ()
815 950 : || sp->resolve ()->get_kind ()
816 : == TyTy::TypeKind::PARAM)
817 : {
818 : all_substs_bound = false;
819 : break;
820 : }
821 : }
822 :
823 : // Also unwrap when the base is already concrete
824 3925 : bool base_is_concrete
825 3925 : = p->get () != nullptr
826 3925 : && p->get ()->is_concrete ();
827 3925 : if (!p->has_substitutions () || all_substs_bound
828 3925 : || base_is_concrete)
829 3900 : result = p->get ();
830 : }
831 : }
832 :
833 3925 : return result;
834 : }
835 0 : break;
836 : }
837 : }
838 4025 : }
839 :
840 : // special-case FnOnce::Output
841 2386 : if (proj->is_trait_position ())
842 : {
843 2386 : auto fn_once_lookup
844 2386 : = mappings.lookup_lang_item (LangItem::Kind::FN_ONCE);
845 2386 : auto fn_once_output_lookup
846 2386 : = mappings.lookup_lang_item (LangItem::Kind::FN_ONCE_OUTPUT);
847 2386 : if (!fn_once_lookup || !fn_once_output_lookup)
848 1173 : return proj;
849 :
850 1313 : DefId &fn_once_trait_id = fn_once_lookup.value ();
851 1313 : DefId &fn_once_output_id = fn_once_output_lookup.value ();
852 1313 : DefId proj_trait_id = proj->get_trait_ref ()->get_defid ();
853 1313 : DefId proj_trait_item_id = proj->get_item_defid ();
854 :
855 1503 : if (proj_trait_id == fn_once_trait_id
856 1403 : && proj_trait_item_id == fn_once_output_id)
857 : {
858 190 : auto pself = proj->get_self ();
859 1403 : if (auto closure = pself->try_as<TyTy::ClosureType> ())
860 100 : return &closure->get_result_type ();
861 : }
862 : }
863 :
864 : return proj;
865 6750 : }
866 :
867 16452 : if (unify_self)
868 : {
869 1 : TyTy::BaseType *proj_self = proj->get_self ();
870 1 : bool proj_self_is_unresolved_trait_self = false;
871 1 : if (auto *param = proj_self->try_as<TyTy::ParamType> ())
872 : {
873 1 : proj_self_is_unresolved_trait_self
874 1 : = !param->can_resolve () && param->is_implicit_self_trait ();
875 : }
876 :
877 : if (!proj_self_is_unresolved_trait_self)
878 : {
879 0 : TyTy::BaseType *impl_self = frame.self;
880 0 : TyTy::BaseType *self = unify_site_and (
881 0 : /*id*/ 0, TyTy::TyWithLocation (proj_self, locus),
882 0 : TyTy::TyWithLocation (impl_self, locus), locus,
883 : /*emit_errors*/ false,
884 : /*commit*/ false,
885 : /*infer*/ false,
886 : /*cleanup*/ true,
887 : /*check_bounds*/ false);
888 :
889 0 : if (self->get_kind () == TyTy::TypeKind::ERROR)
890 : return self;
891 : }
892 : }
893 :
894 : // Lookup the trait item -> impl type mapping (key = trait item DefId).
895 16452 : const DefId item = proj->get_item_defid ();
896 16452 : auto it = frame.assoc_types_by_trait_item.find (item);
897 16452 : if (it == frame.assoc_types_by_trait_item.end ())
898 : {
899 : return proj;
900 : }
901 :
902 16452 : auto &entry = it->second;
903 16452 : auto impl_value = entry.value;
904 :
905 : // chase the impl body through any further projections it contains
906 16452 : TyTy::BaseType *normalized = impl_value;
907 32904 : for (size_t i = 0; i < kNormalizeProjectionLimit; i++)
908 : {
909 32904 : if (!normalized->is<TyTy::ProjectionType> ())
910 : break;
911 :
912 16501 : auto p = normalized->as<TyTy::ProjectionType> ();
913 16501 : if (p->is_trait_position ())
914 : {
915 49 : auto *n = normalize_projection (p, locus, emit_errors, unify_self);
916 49 : if (n == p)
917 : break;
918 :
919 : normalized = n;
920 : }
921 : else
922 : {
923 16452 : auto *v = p->get ();
924 16452 : if (v == nullptr || v == p)
925 : break;
926 :
927 : normalized = v;
928 : }
929 : }
930 :
931 : return normalized;
932 23670 : }
933 :
934 : } // namespace Resolver
935 : } // namespace Rust
|