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_TYTY_SUBST_H
20 : #define RUST_TYTY_SUBST_H
21 :
22 : #include "rust-system.h"
23 : #include "rust-location.h"
24 : #include "rust-hir-full-decls.h"
25 : #include "rust-tyty-region.h"
26 : #include "rust-ast.h"
27 : #include "optional.h"
28 :
29 : namespace Rust {
30 : namespace TyTy {
31 :
32 : class ParamType;
33 : class BaseGeneric;
34 :
35 83461343 : struct RegionConstraints
36 : {
37 : /** 'a: 'b */
38 : std::vector<std::pair<Region, Region>> region_region;
39 : /** T: 'a */
40 : std::vector<std::pair<ParamType *, Region>> type_region;
41 : };
42 :
43 : class BaseType;
44 : class SubstitutionArgumentMappings;
45 : class SubstitutionParamMapping
46 : {
47 : public:
48 : SubstitutionParamMapping (HIR::GenericParam &generic, BaseGeneric *param);
49 :
50 : SubstitutionParamMapping (const SubstitutionParamMapping &other);
51 :
52 : std::string as_string () const;
53 :
54 : bool fill_param_ty (SubstitutionArgumentMappings &subst_mappings,
55 : location_t locus, bool needs_bounds_check = true);
56 :
57 : SubstitutionParamMapping clone () const;
58 :
59 : BaseGeneric *get_param_ty ();
60 : const BaseGeneric *get_param_ty () const;
61 :
62 : HIR::GenericParam &get_generic_param ();
63 : const HIR::GenericParam &get_generic_param () const;
64 :
65 : Identifier get_type_representation () const;
66 :
67 : // this is used for the backend to override the HirId ref of the param to
68 : // what the concrete type is for the rest of the context
69 : void override_context ();
70 :
71 : bool needs_substitution () const;
72 :
73 : location_t get_param_locus () const;
74 :
75 : bool param_has_default_ty () const;
76 :
77 : BaseType *get_default_ty () const;
78 :
79 : bool need_substitution () const;
80 :
81 : private:
82 : HIR::GenericParam &generic;
83 : BaseGeneric *param;
84 : };
85 :
86 : /**
87 : * Represents the part of the parameter list that contains lifetime
88 : * parameters.
89 : *
90 : * ```
91 : * Foo<'a, 'b, i32, 8>
92 : * ^^^^^^
93 : * ```
94 : *
95 : * It has fixed size based on the number of lifetime parameters and they are
96 : * indexed based on their order.
97 : *
98 : * All regions are initially set to unresolved. When type instantiation is
99 : * encountered, all explicitly mentioned lifetimes are resolved to bound
100 : * lifetimes. The remaining unresolved lifetimes are set to anonymous. During
101 : * BIR construction, all lifetimes are replaced with free region variables.
102 : * Inference of anonymous regions happens automatically using BIR subtyping
103 : * pass.
104 : */
105 497482367 : class RegionParamList
106 : {
107 : std::vector<Region> regions;
108 :
109 : public:
110 82931843 : RegionParamList (size_t num_regions) : regions (num_regions) {}
111 :
112 : Region *begin () { return regions.data (); }
113 : Region *end () { return regions.data () + regions.size (); }
114 1 : Region &operator[] (size_t index) { return regions.at (index); }
115 44 : const Region &operator[] (size_t index) const { return regions.at (index); }
116 3162 : WARN_UNUSED_RESULT const Region *begin () const { return regions.data (); }
117 3162 : WARN_UNUSED_RESULT const Region *end () const
118 : {
119 3195 : return regions.data () + regions.size ();
120 : }
121 17459 : size_t size () const { return regions.size (); }
122 :
123 : /**
124 : * Takes regions from the `subst` parameter and fills the rest with anonymous
125 : * regions.
126 : */
127 9410 : static RegionParamList from_subst (size_t num_regions,
128 : std::vector<Region> subst)
129 : {
130 9410 : RegionParamList list (num_regions);
131 9436 : for (size_t i = 0; i < MIN (num_regions, subst.size ()); i++)
132 52 : list.regions.at (i) = subst.at (i);
133 9413 : for (size_t i = subst.size (); i < num_regions; i++)
134 : {
135 3 : list.regions.at (i) = Region::make_anonymous ();
136 : }
137 9410 : return list;
138 : }
139 : };
140 :
141 : class SubstitutionArg
142 : {
143 : public:
144 : SubstitutionArg (const SubstitutionParamMapping *param, BaseType *argument);
145 :
146 : // FIXME
147 : // the copy constructors need removed - they are unsafe see
148 : // TypeBoundPredicate
149 : SubstitutionArg (const SubstitutionArg &other);
150 :
151 : SubstitutionArg &operator= (const SubstitutionArg &other);
152 :
153 : BaseType *get_tyty () const;
154 :
155 : const SubstitutionParamMapping *get_param_mapping () const;
156 :
157 : const BaseGeneric *get_param_ty () const;
158 :
159 : static SubstitutionArg error ();
160 :
161 : bool is_error () const;
162 :
163 : bool is_conrete () const;
164 :
165 : std::string as_string () const;
166 :
167 : private:
168 : const SubstitutionParamMapping *param;
169 : const BaseGeneric *original_param;
170 : BaseType *argument;
171 : };
172 :
173 : typedef std::function<void (const ParamType &, const SubstitutionArg &)>
174 : ParamSubstCb;
175 : class SubstitutionArgumentMappings
176 : {
177 : public:
178 : SubstitutionArgumentMappings (std::vector<SubstitutionArg> mappings,
179 : std::map<std::string, BaseType *> binding_args,
180 : RegionParamList regions, location_t locus,
181 : ParamSubstCb param_subst_cb = nullptr,
182 : bool trait_item_flag = false,
183 : bool error_flag = false);
184 :
185 : SubstitutionArgumentMappings (const SubstitutionArgumentMappings &other);
186 : SubstitutionArgumentMappings &
187 : operator= (const SubstitutionArgumentMappings &other);
188 :
189 190849 : SubstitutionArgumentMappings (SubstitutionArgumentMappings &&other) = default;
190 82749035 : SubstitutionArgumentMappings &operator= (SubstitutionArgumentMappings &&other)
191 : = default;
192 :
193 : static SubstitutionArgumentMappings error ();
194 :
195 : /** Creates empty substitution argument mappings with unresolved regions */
196 : static SubstitutionArgumentMappings empty (size_t num_regions = 0);
197 :
198 : static RegionParamList
199 728 : regions_from_nullable_args (SubstitutionArgumentMappings *args)
200 : {
201 728 : if (args == nullptr)
202 0 : return RegionParamList (0);
203 :
204 728 : return args->get_regions ();
205 : }
206 :
207 : bool is_error () const;
208 :
209 : bool get_argument_for_symbol (const BaseGeneric *param_to_find,
210 : SubstitutionArg *argument) const;
211 :
212 : /** Return type parameter index for symbol */
213 : tl::optional<size_t> find_symbol (const ParamType ¶m_to_find) const;
214 :
215 : bool get_argument_at (size_t index, SubstitutionArg *argument);
216 :
217 : // is_concrete means if the used args is non error, ie: non empty this will
218 : // verify if actual real types have been put in place of are they still
219 : // ParamTy
220 : bool is_concrete () const;
221 :
222 : location_t get_locus () const;
223 :
224 : size_t size () const;
225 :
226 : bool is_empty () const;
227 :
228 : std::vector<SubstitutionArg> &get_mappings ();
229 :
230 : const std::vector<SubstitutionArg> &get_mappings () const;
231 :
232 : std::map<std::string, BaseType *> &get_binding_args ();
233 :
234 : const std::map<std::string, BaseType *> &get_binding_args () const;
235 :
236 : const RegionParamList &get_regions () const;
237 : RegionParamList &get_mut_regions ();
238 :
239 : std::string as_string () const;
240 :
241 : void on_param_subst (const ParamType &p, const SubstitutionArg &a) const;
242 :
243 : ParamSubstCb get_subst_cb () const;
244 :
245 : bool trait_item_mode () const;
246 :
247 : private:
248 : std::vector<SubstitutionArg> mappings;
249 : std::map<std::string, BaseType *> binding_args;
250 : RegionParamList regions;
251 : location_t locus;
252 : ParamSubstCb param_subst_cb;
253 : bool trait_item_flag;
254 : bool error_flag;
255 : };
256 :
257 : class TypeBoundPredicateItem;
258 : class SubstitutionRef
259 : {
260 : public:
261 : SubstitutionRef (std::vector<SubstitutionParamMapping> substitutions,
262 : SubstitutionArgumentMappings arguments,
263 : RegionConstraints region_constraints);
264 :
265 : bool has_substitutions () const;
266 :
267 : std::string subst_as_string () const;
268 :
269 : bool supports_associated_bindings () const;
270 :
271 : // this is overridden in TypeBoundPredicate
272 : // which support bindings we don't add them directly to the SubstitutionRef
273 : // base class because this class represents the fn<X: Foo, Y: Bar>. The only
274 : // construct which supports associated types
275 : virtual size_t get_num_associated_bindings () const;
276 :
277 : // Number of substitution params inherited from an outer scope (e.g. trait
278 : // params inherited by a GAT). These are not supplied by the user when writing
279 : // angle-bracket args and are skipped during arity checking.
280 1143 : virtual size_t get_outer_param_count () const { return 0; }
281 :
282 : // this is overridden in TypeBoundPredicate
283 : virtual TypeBoundPredicateItem
284 : lookup_associated_type (const std::string &search);
285 :
286 : size_t get_num_substitutions () const;
287 :
288 : size_t get_num_lifetime_params () const;
289 :
290 : size_t get_num_type_params () const;
291 :
292 : std::vector<SubstitutionParamMapping> &get_substs ();
293 :
294 : const std::vector<SubstitutionParamMapping> &get_substs () const;
295 :
296 : std::vector<SubstitutionParamMapping> clone_substs () const;
297 :
298 : void override_context ();
299 :
300 : bool needs_substitution () const;
301 :
302 : bool was_substituted () const;
303 :
304 : SubstitutionArgumentMappings &get_substitution_arguments ();
305 : const SubstitutionArgumentMappings &get_substitution_arguments () const;
306 :
307 : // this is the count of type params that are not substituted fuly
308 : size_t num_required_substitutions () const;
309 :
310 : // this is the count of type params that need substituted taking into account
311 : // possible defaults
312 : size_t min_required_substitutions () const;
313 :
314 : // We are trying to subst <i32, f32> into Struct Foo<X,Y> {}
315 : // in the case of Foo<i32,f32>{...}
316 : //
317 : // the substitions we have here define X,Y but the arguments have no bindings
318 : // so its a matter of ordering
319 : SubstitutionArgumentMappings
320 : get_mappings_from_generic_args (HIR::GenericArgs &args,
321 : const std::vector<Region> ®ions);
322 :
323 : // Recursive substitutions
324 : // Foo <A,B> { a:A, b: B}; Bar <X,Y,Z>{a:X, b: Foo<Y,Z>}
325 : //
326 : // we have bindings for X Y Z and need to propagate the binding Y,Z into Foo
327 : // Which binds to A,B
328 : SubstitutionArgumentMappings
329 : adjust_mappings_for_this (SubstitutionArgumentMappings &mappings,
330 : bool trait_mode = false);
331 :
332 : // Are the mappings here actually bound to this type. For example imagine the
333 : // case:
334 : //
335 : // struct Foo<T>(T);
336 : // impl<T> Foo<T> {
337 : // fn test(self) { ... }
338 : // }
339 : //
340 : // In this case we have a generic ADT of Foo and an impl block of a generic T
341 : // on Foo for the Self type. When we it comes to path resolution we can have:
342 : //
343 : // Foo::<i32>::test()
344 : //
345 : // This means the first segment of Foo::<i32> returns the ADT Foo<i32> not the
346 : // Self ADT bound to the T from the impl block. This means when it comes to
347 : // the next segment of test which resolves to the function we need to check
348 : // wether the arguments in the struct definition of foo can be bound here
349 : // before substituting the previous segments type here. This functions acts as
350 : // a guard for the solve_mappings_from_receiver_for_self to handle the case
351 : // where arguments are not bound. This is important for this next case:
352 : //
353 : // struct Baz<A, B>(A, B);
354 : // impl Baz<i32, f32> {
355 : // fn test<X>(a: X) -> X {
356 : // a
357 : // }
358 : // }
359 : //
360 : // In this case Baz has been already substituted for the impl's Self to become
361 : // ADT<i32, f32> so that the function test only has 1 generic argument of X.
362 : // The path for this will be:
363 : //
364 : // Baz::test::<_>(123)
365 : //
366 : // So the first segment here will be Baz<_, _> to try and infer the arguments
367 : // which will be taken from the impl's Self type in this case since it is
368 : // already substituted and like the previous case the check to see if we need
369 : // to inherit the previous segments generic arguments takes place but the
370 : // generic arguments are not bound to this type as they have already been
371 : // substituted.
372 : //
373 : // Its important to remember from the first example the FnType actually looks
374 : // like:
375 : //
376 : // fn <T>test(self :Foo<T>(T))
377 : //
378 : // As the generic parameters are "bound" to each of the items in the impl
379 : // block. So this check is about wether the arguments we have here can
380 : // actually be bound to this type.
381 : bool are_mappings_bound (SubstitutionArgumentMappings &mappings);
382 :
383 : // struct Foo<A, B>(A, B);
384 : //
385 : // impl<T> Foo<T, f32>;
386 : // -> fn test<X>(self, a: X) -> X
387 : //
388 : // We might invoke this via:
389 : //
390 : // a = Foo(123, 456f32);
391 : // b = a.test::<bool>(false);
392 : //
393 : // we need to figure out relevant generic arguemts for self to apply to the
394 : // fntype
395 : SubstitutionArgumentMappings solve_mappings_from_receiver_for_self (
396 : SubstitutionArgumentMappings &mappings) const;
397 :
398 : // Given a type such as:
399 : //
400 : // fn<X,Y>(a:&X, b:Y) -> (...)
401 : //
402 : // This function will inject implicit inference variables for the type
403 : // parameters X and Y
404 : BaseType *infer_substitions (location_t locus);
405 :
406 : // FIXME
407 : // this is bad name for this, i think it should be something like
408 : // compute-higher-ranked-bounds
409 : bool monomorphize ();
410 :
411 : // TODO comment
412 : virtual BaseType *handle_substitions (SubstitutionArgumentMappings &mappings)
413 : = 0;
414 :
415 : WARN_UNUSED_RESULT const SubstitutionArgumentMappings &
416 : get_used_arguments () const;
417 :
418 : WARN_UNUSED_RESULT tl::optional<SubstitutionArg> get_arg_at (size_t i) const;
419 :
420 : const RegionConstraints &get_region_constraints () const;
421 :
422 : protected:
423 : std::vector<SubstitutionParamMapping> substitutions;
424 : SubstitutionArgumentMappings used_arguments;
425 : RegionConstraints region_constraints;
426 : };
427 :
428 : } // namespace TyTy
429 : } // namespace Rust
430 : #endif // RUST_TYTY_SUBST_H
|
