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 : #ifndef RUST_HIR_TYPE_CHECK
20 : #define RUST_HIR_TYPE_CHECK
21 :
22 : #include "rust-hir-map.h"
23 : #include "rust-mapping-common.h"
24 : #include "rust-tyty.h"
25 : #include "rust-hir-impl-trait-context.h"
26 : #include "rust-hir-trait-reference.h"
27 : #include "rust-stacked-contexts.h"
28 : #include "rust-autoderef.h"
29 : #include "rust-tyty-region.h"
30 : #include "rust-tyty-variance-analysis.h"
31 : #include "rust-system.h"
32 :
33 : namespace Rust {
34 : namespace Resolver {
35 :
36 : class TypeCheckContextItem
37 : {
38 : public:
39 : enum ItemType
40 : {
41 : ITEM,
42 : IMPL_ITEM,
43 : TRAIT_ITEM,
44 : ERROR
45 : };
46 :
47 : TypeCheckContextItem (HIR::Function *item);
48 : TypeCheckContextItem (HIR::ImplBlock &impl_block, HIR::Function *item);
49 : TypeCheckContextItem (HIR::TraitItemFunc *trait_item);
50 : TypeCheckContextItem (const TypeCheckContextItem &other);
51 :
52 : TypeCheckContextItem &operator= (const TypeCheckContextItem &other);
53 :
54 : static TypeCheckContextItem get_error ();
55 :
56 : bool is_error () const;
57 :
58 : ItemType get_type () const;
59 :
60 : HIR::Function *get_item ();
61 :
62 : std::pair<HIR::ImplBlock *, HIR::Function *> &get_impl_item ();
63 :
64 : HIR::TraitItemFunc *get_trait_item ();
65 :
66 : TyTy::FnType *get_context_type ();
67 :
68 : DefId get_defid () const;
69 :
70 : private:
71 : TypeCheckContextItem ();
72 :
73 : union Item
74 : {
75 : HIR::Function *item;
76 : std::pair<HIR::ImplBlock *, HIR::Function *> impl_item;
77 : HIR::TraitItemFunc *trait_item;
78 :
79 : Item (HIR::Function *item);
80 : Item (HIR::ImplBlock *impl_block, HIR::Function *item);
81 : Item (HIR::TraitItemFunc *trait_item);
82 : };
83 :
84 : ItemType type;
85 : Item item;
86 : };
87 :
88 : class TypeCheckBlockContextItem
89 : {
90 : public:
91 : enum ItemType
92 : {
93 : IMPL_BLOCK,
94 : TRAIT
95 : };
96 :
97 : TypeCheckBlockContextItem (HIR::ImplBlock *block);
98 : TypeCheckBlockContextItem (HIR::Trait *trait);
99 :
100 : bool is_impl_block () const;
101 : bool is_trait_block () const;
102 :
103 : HIR::ImplBlock &get_impl_block ();
104 : HIR::Trait &get_trait ();
105 :
106 : private:
107 : union Item
108 : {
109 : HIR::ImplBlock *block;
110 : HIR::Trait *trait;
111 :
112 : Item (HIR::ImplBlock *block);
113 : Item (HIR::Trait *trait);
114 : };
115 : ItemType type;
116 : Item item;
117 : };
118 :
119 : /**
120 : * Interned lifetime representation in TyTy
121 : *
122 : * On the HIR->TyTy boundary HIR::Lifetime is interned into this struct.
123 : */
124 : class Lifetime
125 : {
126 : uint32_t interner_index;
127 :
128 : public:
129 101 : explicit constexpr Lifetime (uint32_t interner_index)
130 : : interner_index (interner_index)
131 : {}
132 :
133 : Lifetime () = default;
134 :
135 9802 : WARN_UNUSED_RESULT bool is_static () const { return interner_index == 0; }
136 :
137 : WARN_UNUSED_RESULT static constexpr Lifetime static_lifetime ()
138 : {
139 : return Lifetime (0);
140 : }
141 :
142 : WARN_UNUSED_RESULT static constexpr Lifetime anonymous_lifetime ()
143 : {
144 : return Lifetime (1);
145 : }
146 :
147 : static constexpr uint32_t FIRST_NAMED_LIFETIME = 2;
148 :
149 327 : friend bool operator== (const Lifetime &lhs, const Lifetime &rhs)
150 : {
151 327 : return lhs.interner_index == rhs.interner_index;
152 : }
153 :
154 : friend bool operator!= (const Lifetime &lhs, const Lifetime &rhs)
155 : {
156 : return !(lhs == rhs);
157 : }
158 :
159 101 : WARN_UNUSED_RESULT Lifetime next () { return Lifetime (interner_index++); }
160 : };
161 :
162 45 : struct DeferredOpOverload
163 : {
164 : HirId expr_id;
165 : LangItem::Kind lang_item_type;
166 : HIR::PathIdentSegment specified_segment;
167 : HIR::OperatorExprMeta op;
168 : TyTy::TyVar result_type;
169 :
170 15 : DeferredOpOverload (HirId expr_id, LangItem::Kind lang_item_type,
171 : HIR::PathIdentSegment specified_segment,
172 : HIR::OperatorExprMeta op, TyTy::TyVar result_type)
173 15 : : expr_id (expr_id), lang_item_type (lang_item_type),
174 15 : specified_segment (specified_segment), op (op), result_type (result_type)
175 15 : {}
176 :
177 45 : DeferredOpOverload (const struct DeferredOpOverload &other)
178 45 : : expr_id (other.expr_id), lang_item_type (other.lang_item_type),
179 45 : specified_segment (other.specified_segment), op (other.op),
180 45 : result_type (other.result_type)
181 45 : {}
182 :
183 0 : DeferredOpOverload &operator= (struct DeferredOpOverload const &other)
184 : {
185 0 : expr_id = other.expr_id;
186 0 : lang_item_type = other.lang_item_type;
187 0 : specified_segment = other.specified_segment;
188 0 : op = other.op;
189 0 : result_type = other.result_type;
190 :
191 0 : return *this;
192 : }
193 : };
194 :
195 : class TypeCheckContext
196 : {
197 : public:
198 : static TypeCheckContext *get ();
199 :
200 : ~TypeCheckContext ();
201 :
202 : bool lookup_builtin (NodeId id, TyTy::BaseType **type);
203 : bool lookup_builtin (std::string name, TyTy::BaseType **type);
204 : void insert_builtin (HirId id, NodeId ref, TyTy::BaseType *type);
205 : const std::vector<std::unique_ptr<TyTy::BaseType>> &get_builtins () const;
206 :
207 : void insert_type (const Analysis::NodeMapping &mappings,
208 : TyTy::BaseType *type);
209 : bool lookup_type (HirId id, TyTy::BaseType **type) const;
210 : void clear_type (TyTy::BaseType *ty);
211 :
212 : void mark_function_body_pending (DefId id);
213 : void clear_function_body_pending (DefId id);
214 : bool function_body_pending (DefId id) const;
215 :
216 : void insert_implicit_type (HirId id, TyTy::BaseType *type);
217 :
218 : void insert_type_by_node_id (NodeId ref, HirId id);
219 : bool lookup_type_by_node_id (NodeId ref, HirId *id);
220 :
221 : bool have_function_context () const;
222 : TyTy::BaseType *peek_return_type ();
223 : TypeCheckContextItem peek_context ();
224 : void push_return_type (TypeCheckContextItem item,
225 : TyTy::BaseType *return_type);
226 : void pop_return_type ();
227 :
228 : void push_expected_type (TyTy::BaseType *expected);
229 : void pop_expected_type ();
230 : TyTy::BaseType *peek_expected_type () const;
231 :
232 : StackedContexts<TypeCheckBlockContextItem> &block_context ();
233 :
234 : void iterate (std::function<bool (HirId, TyTy::BaseType *)> cb);
235 :
236 : bool have_loop_context () const;
237 : void push_new_loop_context (HirId id, location_t locus);
238 : void push_new_while_loop_context (HirId id);
239 : TyTy::BaseType *peek_loop_context ();
240 : TyTy::BaseType *pop_loop_context ();
241 :
242 : void swap_head_loop_context (TyTy::BaseType *val);
243 :
244 : bool
245 : find_matching_impl_trait_frame (const TraitReference &tref,
246 : TyTy::BaseType &self,
247 : struct ImplTraitContextFrame *find) const;
248 : bool have_impl_trait_context () const;
249 : void push_impl_trait_context (struct ImplTraitContextFrame frame);
250 : struct ImplTraitContextFrame pop_impl_trait_context ();
251 : struct ImplTraitContextFrame peek_impl_trait_context ();
252 :
253 : void insert_trait_reference (DefId id, TraitReference &&ref);
254 : bool lookup_trait_reference (DefId id, TraitReference **ref);
255 :
256 : bool insert_associated_trait_impl (HirId id,
257 : AssociatedImplTrait &&associated);
258 : bool lookup_associated_trait_impl (HirId id,
259 : AssociatedImplTrait **associated);
260 :
261 : void insert_associated_type_mapping (HirId id, HirId mapping);
262 : void clear_associated_type_mapping (HirId id);
263 :
264 : // lookup any associated type mappings, the out parameter of mapping is
265 : // allowed to be nullptr which allows this interface to do a simple does exist
266 : // check
267 : bool lookup_associated_type_mapping (HirId id, HirId *mapping);
268 :
269 : void insert_associated_impl_mapping (HirId trait_id,
270 : TyTy::BaseType *impl_type,
271 : HirId impl_id);
272 : bool lookup_associated_impl_mapping_for_self (HirId trait_id,
273 : TyTy::BaseType *self,
274 : HirId *mapping);
275 :
276 : void insert_autoderef_mappings (HirId id,
277 : std::vector<Adjustment> &&adjustments);
278 : bool lookup_autoderef_mappings (HirId id,
279 : std::vector<Adjustment> **adjustments);
280 :
281 : void insert_cast_autoderef_mappings (HirId id,
282 : std::vector<Adjustment> &&adjustments);
283 : bool lookup_cast_autoderef_mappings (HirId id,
284 : std::vector<Adjustment> **adjustments);
285 :
286 : void insert_variant_definition (HirId id, HirId variant);
287 : bool lookup_variant_definition (HirId id, HirId *variant);
288 :
289 : void insert_operator_overload (HirId id, TyTy::FnType *call_site);
290 : bool lookup_operator_overload (HirId id, TyTy::FnType **call);
291 :
292 : void insert_deferred_operator_overload (DeferredOpOverload deferred);
293 : bool lookup_deferred_operator_overload (HirId id,
294 : DeferredOpOverload *deferred);
295 :
296 : void iterate_deferred_operator_overloads (
297 : std::function<bool (HirId, DeferredOpOverload &)> cb);
298 :
299 : void insert_unconstrained_check_marker (HirId id, bool status);
300 : bool have_checked_for_unconstrained (HirId id, bool *result);
301 :
302 : void insert_resolved_predicate (HirId id,
303 : const TyTy::TypeBoundPredicate &predicate);
304 : bool lookup_predicate (HirId id, TyTy::TypeBoundPredicate *result);
305 :
306 : void insert_query (HirId id);
307 : void query_completed (HirId id);
308 : bool query_in_progress (HirId id) const;
309 :
310 : void insert_trait_query (DefId id);
311 : void trait_query_completed (DefId id);
312 : bool trait_query_in_progress (DefId id) const;
313 :
314 : Lifetime intern_lifetime (const HIR::Lifetime &name);
315 : WARN_UNUSED_RESULT tl::optional<Lifetime>
316 : lookup_lifetime (const HIR::Lifetime &lifetime) const;
317 :
318 : WARN_UNUSED_RESULT tl::optional<TyTy::Region>
319 : lookup_and_resolve_lifetime (const HIR::Lifetime &lifetime) const;
320 :
321 : void intern_and_insert_lifetime (const HIR::Lifetime &lifetime);
322 :
323 : WARN_UNUSED_RESULT std::vector<TyTy::Region>
324 : regions_from_generic_args (const HIR::GenericArgs &args) const;
325 :
326 : void compute_inference_variables (bool emit_error);
327 :
328 : TyTy::VarianceAnalysis::CrateCtx &get_variance_analysis_ctx ();
329 :
330 1750 : void push_const_context (void) { const_context++; }
331 1749 : void pop_const_context (void)
332 : {
333 1749 : if (const_context > 0)
334 1749 : const_context--;
335 : }
336 2647 : bool const_context_p (void) { return (const_context > 0); }
337 :
338 : private:
339 : TypeCheckContext ();
340 :
341 : bool compute_infer_var (HirId id, TyTy::BaseType *ty, bool emit_error);
342 : bool compute_ambigious_op_overload (HirId id, DeferredOpOverload &op);
343 :
344 : std::map<NodeId, HirId> node_id_refs;
345 : std::map<HirId, TyTy::BaseType *> resolved;
346 : std::set<DefId> function_bodies_pending;
347 : std::vector<std::unique_ptr<TyTy::BaseType>> builtins;
348 : std::vector<std::pair<TypeCheckContextItem, TyTy::BaseType *>>
349 : return_type_stack;
350 : std::vector<TyTy::BaseType *> expected_type_stack;
351 : std::vector<TyTy::BaseType *> loop_type_stack;
352 : StackedContexts<TypeCheckBlockContextItem> block_stack;
353 : std::map<DefId, TraitReference> trait_context;
354 : std::map<HirId, AssociatedImplTrait> associated_impl_traits;
355 : std::vector<ImplTraitContextFrame> impl_trait_frame_stack;
356 :
357 : // trait-id -> list of < self-tyty:impl-id>
358 : std::map<HirId, std::vector<std::pair<TyTy::BaseType *, HirId>>>
359 : associated_traits_to_impls;
360 :
361 : std::map<HirId, HirId> associated_type_mappings;
362 :
363 : // adjustment mappings
364 : std::map<HirId, std::vector<Adjustment>> autoderef_mappings;
365 : std::map<HirId, std::vector<Adjustment>> cast_autoderef_mappings;
366 :
367 : // operator overloads
368 : std::map<HirId, TyTy::FnType *> operator_overloads;
369 :
370 : // variants
371 : std::map<HirId, HirId> variants;
372 :
373 : // unconstrained type-params check
374 : std::map<HirId, bool> unconstrained;
375 :
376 : // predicates
377 : std::map<HirId, TyTy::TypeBoundPredicate> predicates;
378 :
379 : // query context lookups
380 : std::set<HirId> querys_in_progress;
381 : std::set<DefId> trait_queries_in_progress;
382 :
383 : // deferred operator overload
384 : std::map<HirId, DeferredOpOverload> deferred_operator_overloads;
385 :
386 : // variance analysis
387 : TyTy::VarianceAnalysis::CrateCtx variance_analysis_ctx;
388 :
389 : unsigned int const_context = 0;
390 :
391 : /** Used to resolve (interned) lifetime names to their bounding scope. */
392 136387 : class LifetimeResolver
393 : {
394 : /**
395 : * The level of nested scopes, where the lifetime was declared.
396 : *
397 : * Index 0 is used for `impl` blocks and is skipped if not explicitly
398 : * requested.
399 : * Index 1 for the top-level of declarations of items.
400 : * Index >1 is used for late-bound lifetimes.
401 : */
402 : using ScopeIndex = size_t;
403 :
404 : static constexpr ScopeIndex IMPL_SCOPE = 0;
405 : static constexpr ScopeIndex ITEM_SCOPE = 1;
406 :
407 : /**
408 : * A reference to a lifetime binder.
409 : *
410 : * This is used to resolve lifetimes to their scope.
411 : */
412 : struct LifetimeBinderRef
413 : {
414 : uint32_t scope; //> Depth of the scope where the lifetime was declared.
415 : uint32_t index; //> Index of the lifetime in the scope.
416 : };
417 :
418 : /**
419 : * A stack of the number of lifetimes declared in each scope.
420 : *
421 : * Used to pop the correct number of lifetimes when leaving a scope.
422 : */
423 : std::stack<uint32_t> binder_size_stack;
424 :
425 : /**
426 : * Merged stack of all lifetimes declared in all scopes.
427 : *
428 : * Use `binder_size_stack` to determine the number of lifetimes in each
429 : * scope.
430 : */
431 : std::vector<std::pair<Lifetime, LifetimeBinderRef>> lifetime_lookup;
432 :
433 : /**
434 : * Whether the current scope is a function body.
435 : *
436 : * In function header, lifetimes are resolved as early-bound, in the body as
437 : * named. This is because the header can be also used in call position.
438 : */
439 : bool is_body = false;
440 :
441 : /** Return the number of the current scope. */
442 931 : WARN_UNUSED_RESULT uint32_t get_current_scope () const
443 : {
444 1832 : return binder_size_stack.size () - 1;
445 : }
446 :
447 : public:
448 : /** Add new declaration of a lifetime. */
449 901 : void insert_mapping (Lifetime placeholder)
450 : {
451 901 : lifetime_lookup.push_back (
452 901 : {placeholder, {get_current_scope (), binder_size_stack.top ()++}});
453 901 : }
454 :
455 : WARN_UNUSED_RESULT tl::optional<TyTy::Region>
456 : resolve (const Lifetime &placeholder) const;
457 :
458 : /** Only to be used by the guard. */
459 91170 : void push_binder () { binder_size_stack.push (0); }
460 : /** Only to be used by the guard. */
461 64943 : void pop_binder () { binder_size_stack.pop (); }
462 :
463 70603 : bool binder_empty () { return binder_size_stack.empty (); }
464 :
465 : /**
466 : * Switch from resolving a function header to a function body.
467 : */
468 6939 : void switch_to_fn_body () { this->is_body = true; }
469 :
470 22992 : size_t get_num_bound_regions () const { return binder_size_stack.top (); }
471 : };
472 :
473 : // lifetime resolving
474 : std::unordered_map<std::string, Lifetime> lifetime_name_interner;
475 : Lifetime next_lifetime_index = Lifetime (Lifetime::FIRST_NAMED_LIFETIME);
476 :
477 : /**
478 : * Stack of lifetime resolvers.
479 : *
480 : * Due to the contruction of the type checker, it is possible to start
481 : * resolution of a new type in the middle of resolving another type. This
482 : * stack isolates the conexts in such cases.
483 : */
484 : std::stack<LifetimeResolver> lifetime_resolver_stack;
485 :
486 : public:
487 23893 : WARN_UNUSED_RESULT LifetimeResolver &get_lifetime_resolver ()
488 : {
489 23893 : rust_assert (!lifetime_resolver_stack.empty ());
490 23893 : return lifetime_resolver_stack.top ();
491 : }
492 :
493 9802 : WARN_UNUSED_RESULT const LifetimeResolver &get_lifetime_resolver () const
494 : {
495 9802 : rust_assert (!lifetime_resolver_stack.empty ());
496 9802 : return lifetime_resolver_stack.top ();
497 : }
498 :
499 : /**
500 : * A guard that pushes a new lifetime resolver on the stack and pops it
501 : * when it goes out of scope.
502 : */
503 : class LifetimeResolverGuard
504 : {
505 : public:
506 : /** The kind of scope that is being pushed. */
507 : enum ScopeKind
508 : {
509 : IMPL_BLOCK_RESOLVER, //> A new `impl` block scope.
510 : RESOLVER, //> A new scope for a function body.
511 : BINDER, //> A new scope for late-bound lifetimes.
512 : };
513 :
514 : private:
515 : TypeCheckContext &ctx;
516 : ScopeKind kind;
517 :
518 : public:
519 70604 : LifetimeResolverGuard (TypeCheckContext &ctx, ScopeKind kind)
520 70604 : : ctx (ctx), kind (kind)
521 : {
522 70604 : if (kind == IMPL_BLOCK_RESOLVER)
523 : {
524 69718 : ctx.lifetime_resolver_stack.push (LifetimeResolver ());
525 : }
526 :
527 70604 : if (kind == RESOLVER)
528 : {
529 20566 : ctx.lifetime_resolver_stack.push (LifetimeResolver ());
530 : // Skip the `impl` block scope.
531 20566 : ctx.lifetime_resolver_stack.top ().push_binder ();
532 : }
533 70604 : rust_assert (!ctx.lifetime_resolver_stack.empty ());
534 70604 : ctx.lifetime_resolver_stack.top ().push_binder ();
535 70604 : }
536 :
537 70603 : ~LifetimeResolverGuard ()
538 : {
539 70603 : rust_assert (!ctx.lifetime_resolver_stack.empty ());
540 70603 : if (!ctx.lifetime_resolver_stack.top ().binder_empty ())
541 64943 : ctx.lifetime_resolver_stack.top ().pop_binder ();
542 70603 : if (kind == RESOLVER)
543 : {
544 20566 : ctx.lifetime_resolver_stack.pop ();
545 : }
546 70603 : }
547 : };
548 :
549 : /** Start new late bound lifetime scope. */
550 15179 : WARN_UNUSED_RESULT LifetimeResolverGuard push_lifetime_binder ()
551 : {
552 15179 : return LifetimeResolverGuard (*this, LifetimeResolverGuard::BINDER);
553 : }
554 :
555 : /** Start new function body scope. */
556 : WARN_UNUSED_RESULT LifetimeResolverGuard
557 55425 : push_clean_lifetime_resolver (bool is_impl_block = false)
558 : {
559 55425 : return LifetimeResolverGuard (*this,
560 : is_impl_block
561 : ? LifetimeResolverGuard::IMPL_BLOCK_RESOLVER
562 55425 : : LifetimeResolverGuard::RESOLVER);
563 : }
564 :
565 : /** Switch from resolving a function header to a function body. */
566 6939 : void switch_to_fn_body ()
567 : {
568 6939 : this->lifetime_resolver_stack.top ().switch_to_fn_body ();
569 : }
570 : };
571 :
572 : class TypeResolution
573 : {
574 : public:
575 : static void Resolve (HIR::Crate &crate);
576 : };
577 :
578 : class TraitQueryGuard
579 : {
580 : public:
581 4182 : TraitQueryGuard (DefId id) : id (id), ctx (*TypeCheckContext::get ())
582 : {
583 4182 : ctx.insert_trait_query (id);
584 4182 : }
585 :
586 4182 : ~TraitQueryGuard () { ctx.trait_query_completed (id); }
587 :
588 : private:
589 : DefId id;
590 : TypeCheckContext &ctx;
591 : };
592 :
593 : template <typename T> class ScopedPush
594 : {
595 : public:
596 89734 : ScopedPush (std::vector<T> &stack, T value, bool enabled = true)
597 89734 : : stack (stack), enabled (enabled)
598 : {
599 51815 : if (enabled)
600 89734 : stack.push_back (value);
601 : }
602 :
603 89734 : ~ScopedPush ()
604 : {
605 51815 : if (enabled)
606 89734 : stack.pop_back ();
607 : }
608 :
609 89776 : static bool contains (const std::vector<T> &stack, const T &value)
610 : {
611 127695 : return std::find (stack.begin (), stack.end (), value) != stack.end ();
612 : }
613 :
614 : private:
615 : std::vector<T> &stack;
616 : bool enabled;
617 : };
618 :
619 : class ImplTraitFrameGuard
620 : {
621 : public:
622 13507 : ImplTraitFrameGuard (ImplTraitContextFrame frame)
623 13507 : : ctx (*TypeCheckContext::get ())
624 : {
625 13507 : ctx.push_impl_trait_context (frame);
626 13507 : }
627 :
628 13507 : ~ImplTraitFrameGuard () { ctx.pop_impl_trait_context (); }
629 :
630 : private:
631 : Resolver::TypeCheckContext &ctx;
632 : };
633 :
634 : } // namespace Resolver
635 : } // namespace Rust
636 :
637 : #endif // RUST_HIR_TYPE_CHECK
|
