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 97 : explicit constexpr Lifetime (uint32_t interner_index)
130 : : interner_index (interner_index)
131 : {}
132 :
133 : Lifetime () = default;
134 :
135 29721 : 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 314 : friend bool operator== (const Lifetime &lhs, const Lifetime &rhs)
150 : {
151 314 : 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 97 : WARN_UNUSED_RESULT Lifetime next () { return Lifetime (interner_index++); }
160 : };
161 :
162 24 : struct DeferredOpOverload
163 : {
164 : HirId expr_id;
165 : LangItem::Kind lang_item_type;
166 : HIR::PathIdentSegment specified_segment;
167 : TyTy::TypeBoundPredicate predicate;
168 : HIR::OperatorExprMeta op;
169 :
170 8 : DeferredOpOverload (HirId expr_id, LangItem::Kind lang_item_type,
171 : HIR::PathIdentSegment specified_segment,
172 : TyTy::TypeBoundPredicate &predicate,
173 : HIR::OperatorExprMeta op)
174 8 : : expr_id (expr_id), lang_item_type (lang_item_type),
175 16 : specified_segment (specified_segment), predicate (predicate), op (op)
176 8 : {}
177 :
178 24 : DeferredOpOverload (const struct DeferredOpOverload &other)
179 24 : : expr_id (other.expr_id), lang_item_type (other.lang_item_type),
180 48 : specified_segment (other.specified_segment), predicate (other.predicate),
181 24 : op (other.op)
182 24 : {}
183 :
184 0 : DeferredOpOverload &operator= (struct DeferredOpOverload const &other)
185 : {
186 0 : expr_id = other.expr_id;
187 0 : lang_item_type = other.lang_item_type;
188 0 : specified_segment = other.specified_segment;
189 0 : op = other.op;
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 insert_implicit_type (HirId id, TyTy::BaseType *type);
213 :
214 : void insert_type_by_node_id (NodeId ref, HirId id);
215 : bool lookup_type_by_node_id (NodeId ref, HirId *id);
216 :
217 : bool have_function_context () const;
218 : TyTy::BaseType *peek_return_type ();
219 : TypeCheckContextItem peek_context ();
220 : void push_return_type (TypeCheckContextItem item,
221 : TyTy::BaseType *return_type);
222 : void pop_return_type ();
223 :
224 : void push_expected_type (TyTy::BaseType *expected);
225 : void pop_expected_type ();
226 : TyTy::BaseType *peek_expected_type () const;
227 :
228 : StackedContexts<TypeCheckBlockContextItem> &block_context ();
229 :
230 : void iterate (std::function<bool (HirId, TyTy::BaseType *)> cb);
231 :
232 : bool have_loop_context () const;
233 : void push_new_loop_context (HirId id, location_t locus);
234 : void push_new_while_loop_context (HirId id);
235 : TyTy::BaseType *peek_loop_context ();
236 : TyTy::BaseType *pop_loop_context ();
237 :
238 : void swap_head_loop_context (TyTy::BaseType *val);
239 :
240 : bool
241 : find_matching_impl_trait_frame (const TraitReference &tref,
242 : struct ImplTraitContextFrame *find) const;
243 : bool have_impl_trait_context () const;
244 : void push_impl_trait_context (struct ImplTraitContextFrame frame);
245 : struct ImplTraitContextFrame pop_impl_trait_context ();
246 : struct ImplTraitContextFrame peek_impl_trait_context ();
247 :
248 : void insert_trait_reference (DefId id, TraitReference &&ref);
249 : bool lookup_trait_reference (DefId id, TraitReference **ref);
250 :
251 : bool insert_associated_trait_impl (HirId id,
252 : AssociatedImplTrait &&associated);
253 : bool lookup_associated_trait_impl (HirId id,
254 : AssociatedImplTrait **associated);
255 :
256 : void insert_associated_type_mapping (HirId id, HirId mapping);
257 : void clear_associated_type_mapping (HirId id);
258 :
259 : // lookup any associated type mappings, the out parameter of mapping is
260 : // allowed to be nullptr which allows this interface to do a simple does exist
261 : // check
262 : bool lookup_associated_type_mapping (HirId id, HirId *mapping);
263 :
264 : void insert_associated_impl_mapping (HirId trait_id,
265 : TyTy::BaseType *impl_type,
266 : HirId impl_id);
267 : bool lookup_associated_impl_mapping_for_self (HirId trait_id,
268 : TyTy::BaseType *self,
269 : HirId *mapping);
270 :
271 : void insert_autoderef_mappings (HirId id,
272 : std::vector<Adjustment> &&adjustments);
273 : bool lookup_autoderef_mappings (HirId id,
274 : std::vector<Adjustment> **adjustments);
275 :
276 : void insert_cast_autoderef_mappings (HirId id,
277 : std::vector<Adjustment> &&adjustments);
278 : bool lookup_cast_autoderef_mappings (HirId id,
279 : std::vector<Adjustment> **adjustments);
280 :
281 : void insert_variant_definition (HirId id, HirId variant);
282 : bool lookup_variant_definition (HirId id, HirId *variant);
283 :
284 : void insert_operator_overload (HirId id, TyTy::FnType *call_site);
285 : bool lookup_operator_overload (HirId id, TyTy::FnType **call);
286 :
287 : void insert_deferred_operator_overload (DeferredOpOverload deferred);
288 : bool lookup_deferred_operator_overload (HirId id,
289 : DeferredOpOverload *deferred);
290 :
291 : void iterate_deferred_operator_overloads (
292 : std::function<bool (HirId, DeferredOpOverload &)> cb);
293 :
294 : void insert_unconstrained_check_marker (HirId id, bool status);
295 : bool have_checked_for_unconstrained (HirId id, bool *result);
296 :
297 : void insert_resolved_predicate (HirId id, TyTy::TypeBoundPredicate predicate);
298 : bool lookup_predicate (HirId id, TyTy::TypeBoundPredicate *result);
299 :
300 : void insert_query (HirId id);
301 : void query_completed (HirId id);
302 : bool query_in_progress (HirId id) const;
303 :
304 : void insert_trait_query (DefId id);
305 : void trait_query_completed (DefId id);
306 : bool trait_query_in_progress (DefId id) const;
307 :
308 : Lifetime intern_lifetime (const HIR::Lifetime &name);
309 : WARN_UNUSED_RESULT tl::optional<Lifetime>
310 : lookup_lifetime (const HIR::Lifetime &lifetime) const;
311 :
312 : WARN_UNUSED_RESULT tl::optional<TyTy::Region>
313 : lookup_and_resolve_lifetime (const HIR::Lifetime &lifetime) const;
314 :
315 : void intern_and_insert_lifetime (const HIR::Lifetime &lifetime);
316 :
317 : WARN_UNUSED_RESULT std::vector<TyTy::Region>
318 : regions_from_generic_args (const HIR::GenericArgs &args) const;
319 :
320 : void compute_inference_variables (bool emit_error);
321 :
322 : TyTy::VarianceAnalysis::CrateCtx &get_variance_analysis_ctx ();
323 :
324 : private:
325 : TypeCheckContext ();
326 :
327 : bool compute_infer_var (HirId id, TyTy::BaseType *ty, bool emit_error);
328 : bool compute_ambigious_op_overload (HirId id, DeferredOpOverload &op);
329 :
330 : std::map<NodeId, HirId> node_id_refs;
331 : std::map<HirId, TyTy::BaseType *> resolved;
332 : std::vector<std::unique_ptr<TyTy::BaseType>> builtins;
333 : std::vector<std::pair<TypeCheckContextItem, TyTy::BaseType *>>
334 : return_type_stack;
335 : std::vector<TyTy::BaseType *> expected_type_stack;
336 : std::vector<TyTy::BaseType *> loop_type_stack;
337 : StackedContexts<TypeCheckBlockContextItem> block_stack;
338 : std::map<DefId, TraitReference> trait_context;
339 : std::map<HirId, AssociatedImplTrait> associated_impl_traits;
340 : std::vector<ImplTraitContextFrame> impl_trait_frame_stack;
341 :
342 : // trait-id -> list of < self-tyty:impl-id>
343 : std::map<HirId, std::vector<std::pair<TyTy::BaseType *, HirId>>>
344 : associated_traits_to_impls;
345 :
346 : std::map<HirId, HirId> associated_type_mappings;
347 :
348 : // adjustment mappings
349 : std::map<HirId, std::vector<Adjustment>> autoderef_mappings;
350 : std::map<HirId, std::vector<Adjustment>> cast_autoderef_mappings;
351 :
352 : // operator overloads
353 : std::map<HirId, TyTy::FnType *> operator_overloads;
354 :
355 : // variants
356 : std::map<HirId, HirId> variants;
357 :
358 : // unconstrained type-params check
359 : std::map<HirId, bool> unconstrained;
360 :
361 : // predicates
362 : std::map<HirId, TyTy::TypeBoundPredicate> predicates;
363 :
364 : // query context lookups
365 : std::set<HirId> querys_in_progress;
366 : std::set<DefId> trait_queries_in_progress;
367 :
368 : // deferred operator overload
369 : std::map<HirId, DeferredOpOverload> deferred_operator_overloads;
370 :
371 : // variance analysis
372 : TyTy::VarianceAnalysis::CrateCtx variance_analysis_ctx;
373 :
374 : /** Used to resolve (interned) lifetime names to their bounding scope. */
375 140924 : class LifetimeResolver
376 : {
377 : /**
378 : * The level of nested scopes, where the lifetime was declared.
379 : *
380 : * Index 0 is used for `impl` blocks and is skipped if not explicitly
381 : * requested.
382 : * Index 1 for the top-level of declarations of items.
383 : * Index >1 is used for late-bound lifetimes.
384 : */
385 : using ScopeIndex = size_t;
386 :
387 : static constexpr ScopeIndex IMPL_SCOPE = 0;
388 : static constexpr ScopeIndex ITEM_SCOPE = 1;
389 :
390 : /**
391 : * A reference to a lifetime binder.
392 : *
393 : * This is used to resolve lifetimes to their scope.
394 : */
395 : struct LifetimeBinderRef
396 : {
397 : uint32_t scope; //> Depth of the scope where the lifetime was declared.
398 : uint32_t index; //> Index of the lifetime in the scope.
399 : };
400 :
401 : /**
402 : * A stack of the number of lifetimes declared in each scope.
403 : *
404 : * Used to pop the correct number of lifetimes when leaving a scope.
405 : */
406 : std::stack<uint32_t> binder_size_stack;
407 :
408 : /**
409 : * Merged stack of all lifetimes declared in all scopes.
410 : *
411 : * Use `binder_size_stack` to determine the number of lifetimes in each
412 : * scope.
413 : */
414 : std::vector<std::pair<Lifetime, LifetimeBinderRef>> lifetime_lookup;
415 :
416 : /**
417 : * Whether the current scope is a function body.
418 : *
419 : * In function header, lifetimes are resolved as early-bound, in the body as
420 : * named. This is because the header can be also used in call position.
421 : */
422 : bool is_body = false;
423 :
424 : /** Return the number of the current scope. */
425 1034 : WARN_UNUSED_RESULT uint32_t get_current_scope () const
426 : {
427 2001 : return binder_size_stack.size () - 1;
428 : }
429 :
430 : public:
431 : /** Add new declaration of a lifetime. */
432 967 : void insert_mapping (Lifetime placeholder)
433 : {
434 967 : lifetime_lookup.push_back (
435 967 : {placeholder, {get_current_scope (), binder_size_stack.top ()++}});
436 967 : }
437 :
438 : WARN_UNUSED_RESULT tl::optional<TyTy::Region>
439 : resolve (const Lifetime &placeholder) const;
440 :
441 : /** Only to be used by the guard. */
442 100316 : void push_binder () { binder_size_stack.push (0); }
443 : /** Only to be used by the guard. */
444 58717 : void pop_binder () { binder_size_stack.pop (); }
445 :
446 58725 : bool binder_empty () { return binder_size_stack.empty (); }
447 :
448 : /**
449 : * Switch from resolving a function header to a function body.
450 : */
451 6577 : void switch_to_fn_body () { this->is_body = true; }
452 :
453 43551 : size_t get_num_bound_regions () const { return binder_size_stack.top (); }
454 : };
455 :
456 : // lifetime resolving
457 : std::unordered_map<std::string, Lifetime> lifetime_name_interner;
458 : Lifetime next_lifetime_index = Lifetime (Lifetime::FIRST_NAMED_LIFETIME);
459 :
460 : /**
461 : * Stack of lifetime resolvers.
462 : *
463 : * Due to the contruction of the type checker, it is possible to start
464 : * resolution of a new type in the middle of resolving another type. This
465 : * stack isolates the conexts in such cases.
466 : */
467 : std::stack<LifetimeResolver> lifetime_resolver_stack;
468 :
469 : public:
470 44518 : WARN_UNUSED_RESULT LifetimeResolver &get_lifetime_resolver ()
471 : {
472 44518 : rust_assert (!lifetime_resolver_stack.empty ());
473 44518 : return lifetime_resolver_stack.top ();
474 : }
475 :
476 29721 : WARN_UNUSED_RESULT const LifetimeResolver &get_lifetime_resolver () const
477 : {
478 29721 : rust_assert (!lifetime_resolver_stack.empty ());
479 29721 : return lifetime_resolver_stack.top ();
480 : }
481 :
482 : /**
483 : * A guard that pushes a new lifetime resolver on the stack and pops it
484 : * when it goes out of scope.
485 : */
486 : class LifetimeResolverGuard
487 : {
488 : public:
489 : /** The kind of scope that is being pushed. */
490 : enum ScopeKind
491 : {
492 : IMPL_BLOCK_RESOLVER, //> A new `impl` block scope.
493 : RESOLVER, //> A new scope for a function body.
494 : BINDER, //> A new scope for late-bound lifetimes.
495 : };
496 :
497 : private:
498 : TypeCheckContext &ctx;
499 : ScopeKind kind;
500 :
501 : public:
502 58725 : LifetimeResolverGuard (TypeCheckContext &ctx, ScopeKind kind)
503 58725 : : ctx (ctx), kind (kind)
504 : {
505 58725 : if (kind == IMPL_BLOCK_RESOLVER)
506 : {
507 11384 : ctx.lifetime_resolver_stack.push (LifetimeResolver ());
508 : }
509 :
510 58725 : if (kind == RESOLVER)
511 : {
512 41591 : ctx.lifetime_resolver_stack.push (LifetimeResolver ());
513 : // Skip the `impl` block scope.
514 41591 : ctx.lifetime_resolver_stack.top ().push_binder ();
515 : }
516 58725 : rust_assert (!ctx.lifetime_resolver_stack.empty ());
517 58725 : ctx.lifetime_resolver_stack.top ().push_binder ();
518 58725 : }
519 :
520 58725 : ~LifetimeResolverGuard ()
521 : {
522 58725 : rust_assert (!ctx.lifetime_resolver_stack.empty ());
523 58725 : if (!ctx.lifetime_resolver_stack.top ().binder_empty ())
524 58717 : ctx.lifetime_resolver_stack.top ().pop_binder ();
525 58725 : if (kind == RESOLVER)
526 : {
527 41591 : ctx.lifetime_resolver_stack.pop ();
528 : }
529 58725 : }
530 : };
531 :
532 : /** Start new late bound lifetime scope. */
533 11442 : WARN_UNUSED_RESULT LifetimeResolverGuard push_lifetime_binder ()
534 : {
535 11442 : return LifetimeResolverGuard (*this, LifetimeResolverGuard::BINDER);
536 : }
537 :
538 : /** Start new function body scope. */
539 : WARN_UNUSED_RESULT LifetimeResolverGuard
540 47283 : push_clean_lifetime_resolver (bool is_impl_block = false)
541 : {
542 47283 : return LifetimeResolverGuard (*this,
543 : is_impl_block
544 : ? LifetimeResolverGuard::IMPL_BLOCK_RESOLVER
545 47283 : : LifetimeResolverGuard::RESOLVER);
546 : }
547 :
548 : /** Switch from resolving a function header to a function body. */
549 6577 : void switch_to_fn_body ()
550 : {
551 6577 : this->lifetime_resolver_stack.top ().switch_to_fn_body ();
552 : }
553 : };
554 :
555 : class TypeResolution
556 : {
557 : public:
558 : static void Resolve (HIR::Crate &crate);
559 : };
560 :
561 : class TraitQueryGuard
562 : {
563 : public:
564 3934 : TraitQueryGuard (DefId id) : id (id), ctx (*TypeCheckContext::get ())
565 : {
566 3934 : ctx.insert_trait_query (id);
567 3934 : }
568 :
569 3934 : ~TraitQueryGuard () { ctx.trait_query_completed (id); }
570 :
571 : private:
572 : DefId id;
573 : TypeCheckContext &ctx;
574 : };
575 :
576 : template <typename T> class ScopedPush
577 : {
578 : public:
579 1599067 : ScopedPush (std::vector<T> &stack, T value, bool enabled = true)
580 1599067 : : stack (stack), enabled (enabled)
581 : {
582 51002 : if (enabled)
583 1599037 : stack.push_back (value);
584 : }
585 :
586 1599067 : ~ScopedPush ()
587 : {
588 51002 : if (enabled)
589 1599037 : stack.pop_back ();
590 1599067 : }
591 :
592 1599137 : static bool contains (const std::vector<T> &stack, const T &value)
593 : {
594 3147230 : return std::find (stack.begin (), stack.end (), value) != stack.end ();
595 : }
596 :
597 : private:
598 : std::vector<T> &stack;
599 : bool enabled;
600 : };
601 :
602 : class ImplTraitFrameGuard
603 : {
604 : public:
605 13326 : ImplTraitFrameGuard (ImplTraitContextFrame frame)
606 13326 : : ctx (*TypeCheckContext::get ())
607 : {
608 13326 : ctx.push_impl_trait_context (frame);
609 13326 : }
610 :
611 13326 : ~ImplTraitFrameGuard () { ctx.pop_impl_trait_context (); }
612 :
613 : private:
614 : Resolver::TypeCheckContext &ctx;
615 : };
616 :
617 : } // namespace Resolver
618 : } // namespace Rust
619 :
620 : #endif // RUST_HIR_TYPE_CHECK
|
