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