Branch data Line data Source code
1 : : // Copyright (C) 2020-2025 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 : 83 : explicit constexpr Lifetime (uint32_t interner_index)
129 : : : interner_index (interner_index)
130 : : {}
131 : :
132 : : Lifetime () = default;
133 : :
134 : 29235 : 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 : 302 : friend bool operator== (const Lifetime &lhs, const Lifetime &rhs)
149 : : {
150 : 302 : 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 : 83 : 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 : : void 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 : 122967 : 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 : 930 : WARN_UNUSED_RESULT uint32_t get_current_scope () const
411 : : {
412 : 1824 : return binder_size_stack.size () - 1;
413 : : }
414 : :
415 : : public:
416 : : /** Add new declaration of a lifetime. */
417 : 894 : void insert_mapping (Lifetime placeholder)
418 : : {
419 : 894 : lifetime_lookup.push_back (
420 : 894 : {placeholder, {get_current_scope (), binder_size_stack.top ()++}});
421 : 894 : }
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 : 86752 : void push_binder () { binder_size_stack.push (0); }
428 : : /** Only to be used by the guard. */
429 : 50875 : void pop_binder () { binder_size_stack.pop (); }
430 : :
431 : 50881 : bool binder_empty () { return binder_size_stack.empty (); }
432 : :
433 : : /**
434 : : * Switch from resolving a function header to a function body.
435 : : */
436 : 6117 : void switch_to_fn_body () { this->is_body = true; }
437 : :
438 : 42074 : 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 : 42968 : WARN_UNUSED_RESULT LifetimeResolver &get_lifetime_resolver ()
456 : : {
457 : 42968 : rust_assert (!lifetime_resolver_stack.empty ());
458 : 42968 : return lifetime_resolver_stack.top ();
459 : : }
460 : :
461 : 29235 : WARN_UNUSED_RESULT const LifetimeResolver &get_lifetime_resolver () const
462 : : {
463 : 29235 : rust_assert (!lifetime_resolver_stack.empty ());
464 : 29235 : 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 : 50882 : LifetimeResolverGuard (TypeCheckContext &ctx, ScopeKind kind)
488 : 50882 : : ctx (ctx), kind (kind)
489 : : {
490 : 50882 : if (kind == IMPL_BLOCK_RESOLVER)
491 : : {
492 : 11068 : ctx.lifetime_resolver_stack.push (LifetimeResolver ());
493 : : }
494 : :
495 : 50882 : if (kind == RESOLVER)
496 : : {
497 : 35870 : ctx.lifetime_resolver_stack.push (LifetimeResolver ());
498 : : // Skip the `impl` block scope.
499 : 35870 : ctx.lifetime_resolver_stack.top ().push_binder ();
500 : : }
501 : 50882 : rust_assert (!ctx.lifetime_resolver_stack.empty ());
502 : 50882 : ctx.lifetime_resolver_stack.top ().push_binder ();
503 : 50882 : }
504 : :
505 : 50881 : ~LifetimeResolverGuard ()
506 : : {
507 : 50881 : rust_assert (!ctx.lifetime_resolver_stack.empty ());
508 : 50881 : if (!ctx.lifetime_resolver_stack.top ().binder_empty ())
509 : 50875 : ctx.lifetime_resolver_stack.top ().pop_binder ();
510 : 50881 : if (kind == RESOLVER)
511 : : {
512 : 35869 : ctx.lifetime_resolver_stack.pop ();
513 : : }
514 : 50881 : }
515 : : };
516 : :
517 : : /** Start new late bound lifetime scope. */
518 : 9478 : WARN_UNUSED_RESULT LifetimeResolverGuard push_lifetime_binder ()
519 : : {
520 : 9478 : return LifetimeResolverGuard (*this, LifetimeResolverGuard::BINDER);
521 : : }
522 : :
523 : : /** Start new function body scope. */
524 : : WARN_UNUSED_RESULT LifetimeResolverGuard
525 : 41404 : push_clean_lifetime_resolver (bool is_impl_block = false)
526 : : {
527 : 41404 : return LifetimeResolverGuard (*this,
528 : : is_impl_block
529 : : ? LifetimeResolverGuard::IMPL_BLOCK_RESOLVER
530 : 41404 : : LifetimeResolverGuard::RESOLVER);
531 : : }
532 : :
533 : : /** Switch from resolving a function header to a function body. */
534 : 6117 : void switch_to_fn_body ()
535 : : {
536 : 6117 : 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 : 3600 : TraitQueryGuard (DefId id) : id (id), ctx (*TypeCheckContext::get ())
550 : : {
551 : 3600 : ctx.insert_trait_query (id);
552 : 3600 : }
553 : :
554 : 3600 : ~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
|
