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