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 74664042 : 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 445023432 : class RegionParamList
106 : {
107 : std::vector<Region> regions;
108 :
109 : public:
110 74192714 : 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 3079 : WARN_UNUSED_RESULT const Region *begin () const { return regions.data (); }
117 3079 : WARN_UNUSED_RESULT const Region *end () const
118 : {
119 3112 : return regions.data () + regions.size ();
120 : }
121 17130 : 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 9250 : static RegionParamList from_subst (size_t num_regions,
128 : std::vector<Region> subst)
129 : {
130 9250 : RegionParamList list (num_regions);
131 9276 : for (size_t i = 0; i < MIN (num_regions, subst.size ()); i++)
132 52 : list.regions.at (i) = subst.at (i);
133 9253 : for (size_t i = subst.size (); i < num_regions; i++)
134 : {
135 3 : list.regions.at (i) = Region::make_anonymous ();
136 : }
137 9250 : 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 163440 : SubstitutionArgumentMappings (SubstitutionArgumentMappings &&other) = default;
190 74026830 : 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 5195 : regions_from_nullable_args (SubstitutionArgumentMappings *args)
200 : {
201 5195 : if (args == nullptr)
202 4300 : return RegionParamList (0);
203 :
204 895 : 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 : // this is overridden in TypeBoundPredicate
278 : virtual TypeBoundPredicateItem
279 : lookup_associated_type (const std::string &search);
280 :
281 : size_t get_num_substitutions () const;
282 :
283 : size_t get_num_lifetime_params () const;
284 :
285 : size_t get_num_type_params () const;
286 :
287 : std::vector<SubstitutionParamMapping> &get_substs ();
288 :
289 : const std::vector<SubstitutionParamMapping> &get_substs () const;
290 :
291 : std::vector<SubstitutionParamMapping> clone_substs () const;
292 :
293 : void override_context ();
294 :
295 : bool needs_substitution () const;
296 :
297 : bool was_substituted () const;
298 :
299 : SubstitutionArgumentMappings &get_substitution_arguments ();
300 : const SubstitutionArgumentMappings &get_substitution_arguments () const;
301 :
302 : // this is the count of type params that are not substituted fuly
303 : size_t num_required_substitutions () const;
304 :
305 : // this is the count of type params that need substituted taking into account
306 : // possible defaults
307 : size_t min_required_substitutions () const;
308 :
309 : // We are trying to subst <i32, f32> into Struct Foo<X,Y> {}
310 : // in the case of Foo<i32,f32>{...}
311 : //
312 : // the substitions we have here define X,Y but the arguments have no bindings
313 : // so its a matter of ordering
314 : SubstitutionArgumentMappings
315 : get_mappings_from_generic_args (HIR::GenericArgs &args,
316 : const std::vector<Region> ®ions);
317 :
318 : // Recursive substitutions
319 : // Foo <A,B> { a:A, b: B}; Bar <X,Y,Z>{a:X, b: Foo<Y,Z>}
320 : //
321 : // we have bindings for X Y Z and need to propagate the binding Y,Z into Foo
322 : // Which binds to A,B
323 : SubstitutionArgumentMappings
324 : adjust_mappings_for_this (SubstitutionArgumentMappings &mappings,
325 : bool trait_mode = false);
326 :
327 : // Are the mappings here actually bound to this type. For example imagine the
328 : // case:
329 : //
330 : // struct Foo<T>(T);
331 : // impl<T> Foo<T> {
332 : // fn test(self) { ... }
333 : // }
334 : //
335 : // In this case we have a generic ADT of Foo and an impl block of a generic T
336 : // on Foo for the Self type. When we it comes to path resolution we can have:
337 : //
338 : // Foo::<i32>::test()
339 : //
340 : // This means the first segment of Foo::<i32> returns the ADT Foo<i32> not the
341 : // Self ADT bound to the T from the impl block. This means when it comes to
342 : // the next segment of test which resolves to the function we need to check
343 : // wether the arguments in the struct definition of foo can be bound here
344 : // before substituting the previous segments type here. This functions acts as
345 : // a guard for the solve_mappings_from_receiver_for_self to handle the case
346 : // where arguments are not bound. This is important for this next case:
347 : //
348 : // struct Baz<A, B>(A, B);
349 : // impl Baz<i32, f32> {
350 : // fn test<X>(a: X) -> X {
351 : // a
352 : // }
353 : // }
354 : //
355 : // In this case Baz has been already substituted for the impl's Self to become
356 : // ADT<i32, f32> so that the function test only has 1 generic argument of X.
357 : // The path for this will be:
358 : //
359 : // Baz::test::<_>(123)
360 : //
361 : // So the first segment here will be Baz<_, _> to try and infer the arguments
362 : // which will be taken from the impl's Self type in this case since it is
363 : // already substituted and like the previous case the check to see if we need
364 : // to inherit the previous segments generic arguments takes place but the
365 : // generic arguments are not bound to this type as they have already been
366 : // substituted.
367 : //
368 : // Its important to remember from the first example the FnType actually looks
369 : // like:
370 : //
371 : // fn <T>test(self :Foo<T>(T))
372 : //
373 : // As the generic parameters are "bound" to each of the items in the impl
374 : // block. So this check is about wether the arguments we have here can
375 : // actually be bound to this type.
376 : bool are_mappings_bound (SubstitutionArgumentMappings &mappings);
377 :
378 : // struct Foo<A, B>(A, B);
379 : //
380 : // impl<T> Foo<T, f32>;
381 : // -> fn test<X>(self, a: X) -> X
382 : //
383 : // We might invoke this via:
384 : //
385 : // a = Foo(123, 456f32);
386 : // b = a.test::<bool>(false);
387 : //
388 : // we need to figure out relevant generic arguemts for self to apply to the
389 : // fntype
390 : SubstitutionArgumentMappings solve_mappings_from_receiver_for_self (
391 : SubstitutionArgumentMappings &mappings) const;
392 :
393 : // Given a type such as:
394 : //
395 : // fn<X,Y>(a:&X, b:Y) -> (...)
396 : //
397 : // This function will inject implicit inference variables for the type
398 : // parameters X and Y
399 : BaseType *infer_substitions (location_t locus);
400 :
401 : // this clears any possible projections from higher ranked trait bounds which
402 : // could be hanging around from a previous resolution
403 : void prepare_higher_ranked_bounds ();
404 :
405 : // FIXME
406 : // this is bad name for this, i think it should be something like
407 : // compute-higher-ranked-bounds
408 : bool monomorphize ();
409 :
410 : // TODO comment
411 : virtual BaseType *handle_substitions (SubstitutionArgumentMappings &mappings)
412 : = 0;
413 :
414 : WARN_UNUSED_RESULT const SubstitutionArgumentMappings &
415 : get_used_arguments () const;
416 :
417 : WARN_UNUSED_RESULT tl::optional<SubstitutionArg> get_arg_at (size_t i) const;
418 :
419 : const RegionConstraints &get_region_constraints () const;
420 :
421 : protected:
422 : std::vector<SubstitutionParamMapping> substitutions;
423 : SubstitutionArgumentMappings used_arguments;
424 : RegionConstraints region_constraints;
425 : };
426 :
427 : } // namespace TyTy
428 : } // namespace Rust
429 : #endif // RUST_TYTY_SUBST_H
|
