Branch data Line data Source code
1 : : #ifndef RUST_TYTY_VARIANCE_ANALYSIS_PRIVATE_H
2 : : #define RUST_TYTY_VARIANCE_ANALYSIS_PRIVATE_H
3 : :
4 : : #include "rust-tyty-variance-analysis.h"
5 : :
6 : : #include "rust-tyty-visitor.h"
7 : :
8 : : namespace Rust {
9 : : namespace TyTy {
10 : : namespace VarianceAnalysis {
11 : :
12 : : using SolutionIndex = uint32_t;
13 : :
14 : : /** Term descibing variance relations. */
15 : : struct Term
16 : : {
17 : : enum Kind : uint8_t
18 : : {
19 : : CONST,
20 : : REF,
21 : : TRANSFORM,
22 : : };
23 : :
24 : : Kind kind;
25 : : union
26 : : {
27 : : struct
28 : : {
29 : : Term *lhs;
30 : : Term *rhs;
31 : : } transform;
32 : : SolutionIndex ref;
33 : : Variance const_val;
34 : : };
35 : :
36 : 169 : Term () {}
37 : :
38 : 4283 : Term (Variance variance) : kind (CONST), const_val (variance) {}
39 : :
40 : 178 : WARN_UNUSED_RESULT bool is_const () const { return kind == CONST; }
41 : :
42 : : static Term make_ref (SolutionIndex index);
43 : :
44 : : static Term make_transform (Term lhs, Term rhs);
45 : : };
46 : :
47 : : /** Variance constraint of a type parameter. */
48 : : struct Constraint
49 : : {
50 : 139 : Constraint (SolutionIndex target_index, Term *term)
51 : 139 : : target_index (target_index), term (term)
52 : : {}
53 : :
54 : : SolutionIndex target_index;
55 : : Term *term;
56 : : };
57 : :
58 : : /** Abstract variance visitor context. */
59 : 3643 : template <typename VARIANCE> class VarianceVisitorCtx
60 : : {
61 : : public:
62 : 3046 : virtual ~VarianceVisitorCtx () = default;
63 : :
64 : : virtual void add_constraints_from_ty (BaseType *ty, VARIANCE variance) = 0;
65 : : virtual void add_constraints_from_region (const Region ®ion,
66 : : VARIANCE variance)
67 : : = 0;
68 : 472 : void add_constraints_from_mutability (BaseType *type, Mutability mutability,
69 : : VARIANCE variance)
70 : : {
71 : 472 : switch (mutability)
72 : : {
73 : 300 : case Mutability::Imm:
74 : 300 : return add_constraints_from_ty (type, variance);
75 : 172 : case Mutability::Mut:
76 : 172 : return add_constraints_from_ty (type, Variance::invariant ());
77 : : }
78 : : }
79 : : virtual void
80 : : add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
81 : : VARIANCE variance, bool invariant_args)
82 : : = 0;
83 : : virtual void add_constrints_from_param (ParamType ¶m, VARIANCE variance)
84 : : = 0;
85 : : virtual VARIANCE contra (VARIANCE variance) = 0;
86 : : };
87 : :
88 : : template <typename VARIANCE> class VisitorBase final : public TyVisitor
89 : : {
90 : : VarianceVisitorCtx<VARIANCE> &ctx;
91 : : VARIANCE variance;
92 : :
93 : : public:
94 : 6070 : VisitorBase (VarianceVisitorCtx<VARIANCE> &ctx, VARIANCE variance)
95 : 6070 : : ctx (ctx), variance (variance)
96 : : {}
97 : :
98 : 206 : void visit (BoolType &type) override {}
99 : 47 : void visit (CharType &type) override {}
100 : 1983 : void visit (IntType &type) override {}
101 : 592 : void visit (UintType &type) override {}
102 : 188 : void visit (FloatType &type) override {}
103 : 175 : void visit (USizeType &type) override {}
104 : 17 : void visit (ISizeType &type) override {}
105 : 8 : void visit (StrType &type) override {}
106 : 0 : void visit (NeverType &type) override {}
107 : :
108 : 0 : void visit (ClosureType &type) override {}
109 : 11 : void visit (FnType &type) override
110 : : {
111 : 23 : for (auto ®ion : type.get_used_arguments ().get_regions ())
112 : 12 : ctx.add_constraints_from_region (region, Variance::invariant ());
113 : 11 : }
114 : :
115 : 253 : void visit (ReferenceType &type) override
116 : : {
117 : 253 : ctx.add_constraints_from_region (type.get_region (), variance);
118 : 253 : ctx.add_constraints_from_mutability (type.get_base (), type.mutability (),
119 : : variance);
120 : 253 : }
121 : 50 : void visit (ArrayType &type) override
122 : : {
123 : 50 : ctx.add_constraints_from_ty (type.get_element_type (), variance);
124 : 50 : }
125 : 290 : void visit (SliceType &type) override
126 : : {
127 : 290 : ctx.add_constraints_from_ty (type.get_element_type (), variance);
128 : 290 : }
129 : 219 : void visit (PointerType &type) override
130 : : {
131 : 219 : ctx.add_constraints_from_ty (type.get_base (), variance);
132 : 219 : ctx.add_constraints_from_mutability (type.get_base (), type.mutability (),
133 : : variance);
134 : 219 : }
135 : 148 : void visit (TupleType &type) override
136 : : {
137 : 149 : for (auto &elem : type.get_fields ())
138 : 1 : ctx.add_constraints_from_ty (elem.get_tyty (), variance);
139 : 148 : }
140 : 429 : void visit (ADTType &type) override
141 : : {
142 : 429 : ctx.add_constraints_from_generic_args (type.get_orig_ref (), type, variance,
143 : : false);
144 : 429 : }
145 : 0 : void visit (ProjectionType &type) override
146 : : {
147 : 0 : ctx.add_constraints_from_generic_args (type.get_orig_ref (), type, variance,
148 : : true);
149 : 0 : }
150 : 1445 : void visit (ParamType &type) override
151 : : {
152 : 1445 : ctx.add_constrints_from_param (type, variance);
153 : 1445 : }
154 : 9 : void visit (FnPtr &type) override
155 : : {
156 : 9 : auto contra = ctx.contra (variance);
157 : :
158 : 16 : for (auto ¶m : type.get_params ())
159 : : {
160 : 7 : ctx.add_constraints_from_ty (param.get_tyty (), contra);
161 : : }
162 : :
163 : 9 : ctx.add_constraints_from_ty (type.get_return_type (), variance);
164 : 9 : }
165 : :
166 : 0 : void visit (ErrorType &type) override {}
167 : :
168 : 0 : void visit (PlaceholderType &type) override { rust_unreachable (); }
169 : 0 : void visit (InferType &type) override { rust_unreachable (); }
170 : :
171 : 0 : void visit (DynamicObjectType &type) override
172 : : {
173 : : // TODO
174 : 0 : }
175 : :
176 : 0 : void visit (OpaqueType &type) override {}
177 : :
178 : 0 : void visit (TyTy::ConstParamType &) override {}
179 : 0 : void visit (TyTy::ConstValueType &) override {}
180 : 0 : void visit (TyTy::ConstInferType &) override {}
181 : 0 : void visit (TyTy::ConstErrorType &) override {}
182 : : };
183 : :
184 : : /** Per crate context for generic type variance analysis. */
185 : 4449 : class GenericTyPerCrateCtx
186 : : {
187 : : public: // External API
188 : : /** Add a type to context and process its variance constraints. */
189 : : void process_type (ADTType &ty);
190 : :
191 : : /**
192 : : * Solve for all variance constraints and clear temporary data.
193 : : *
194 : : * Only keeps the results.
195 : : */
196 : : void solve ();
197 : :
198 : : /** Prints solution debug output. To be called after solve. */
199 : : void debug_print_solutions ();
200 : :
201 : : tl::optional<SolutionIndex> lookup_type_index (HirId orig_ref);
202 : :
203 : : public: // Module internal API
204 : : /** Format term tree to string. */
205 : : WARN_UNUSED_RESULT std::string to_string (const Term &term) const;
206 : :
207 : : /** Formats as <type ident>`[`<param index>``]` */
208 : : WARN_UNUSED_RESULT std::string to_string (SolutionIndex index) const;
209 : :
210 : : /** Evaluate a variance relation expression (term tree). */
211 : : Variance evaluate (Term *term);
212 : :
213 : : std::vector<Variance> query_generic_variance (const ADTType &type);
214 : :
215 : : FreeRegions query_field_regions (const ADTType *parent, size_t variant_index,
216 : : size_t field_index,
217 : : const FreeRegions &parent_regions);
218 : :
219 : : std::vector<Region> query_type_regions (BaseType *base);
220 : :
221 : : public: // Data used by visitors.
222 : : // This whole class is private, therfore members can be public.
223 : :
224 : : /** Current solutions. Initiated to bivariant. */
225 : : std::vector<Variance> solutions;
226 : :
227 : : /** Constrains on solutions. Iteratively applied until fixpoint. */
228 : : std::vector<Constraint> constraints;
229 : :
230 : : /** Maps TyTy::orig_ref to an index of first solution for this type. */
231 : : std::unordered_map<HirId, SolutionIndex> map_from_ty_orig_ref;
232 : : };
233 : :
234 : : /** Visitor context for generic type variance analysis used for processing of a
235 : : * single type. */
236 : 3046 : class GenericTyVisitorCtx : VarianceVisitorCtx<Term>
237 : : {
238 : : using Visitor = VisitorBase<Term>;
239 : :
240 : : public:
241 : 3046 : explicit GenericTyVisitorCtx (GenericTyPerCrateCtx &ctx) : ctx (ctx) {}
242 : : /** Entry point: Add a type to context and process its variance constraints.
243 : : */
244 : : void process_type (ADTType &ty);
245 : :
246 : : private:
247 : : /** Resolve a type from a TyTy::ref. */
248 : : SolutionIndex lookup_or_add_type (HirId hir_id);
249 : :
250 : : /** Visit an inner type and add its constraints. */
251 : : void add_constraints_from_ty (BaseType *ty, Term variance) override;
252 : :
253 : : void add_constraint (SolutionIndex index, Term term);
254 : :
255 : : void add_constraints_from_region (const Region ®ion, Term term) override;
256 : :
257 : : void add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
258 : : Term variance,
259 : : bool invariant_args) override;
260 : :
261 : : void add_constrints_from_param (ParamType &type, Term variance) override;
262 : :
263 : : /** Construct a term for type in contravaraint position. */
264 : : Term contra (Term variance) override;
265 : :
266 : : private:
267 : : GenericTyPerCrateCtx &ctx;
268 : :
269 : : private: // Per type processing context
270 : : /** Index of the solution first **lifetime param** for the current type. */
271 : : SolutionIndex first_lifetime = 0;
272 : :
273 : : /** Index of the solution first **type param** for the current type. */
274 : : SolutionIndex first_type = 0;
275 : :
276 : : /** Maps type param names to index among type params. */
277 : : std::vector<std::string> param_names;
278 : : };
279 : :
280 : : /** Visitor context for basic type variance analysis. */
281 : : class TyVisitorCtx : public VarianceVisitorCtx<Variance>
282 : : {
283 : : public:
284 : : using Visitor = VisitorBase<Variance>;
285 : :
286 : 592 : TyVisitorCtx (GenericTyPerCrateCtx &ctx) : ctx (ctx) {}
287 : :
288 : 516 : std::vector<Variance> collect_variances (BaseType &ty)
289 : : {
290 : 516 : add_constraints_from_ty (&ty, Variance::covariant ());
291 : 516 : return variances;
292 : : }
293 : :
294 : 76 : std::vector<Region> collect_regions (BaseType &ty)
295 : : {
296 : 76 : add_constraints_from_ty (&ty, Variance::covariant ());
297 : 76 : return regions;
298 : : }
299 : :
300 : : void add_constraints_from_ty (BaseType *ty, Variance variance) override;
301 : : void add_constraints_from_region (const Region ®ion,
302 : : Variance variance) override;
303 : : void add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
304 : : Variance variance,
305 : : bool invariant_args) override;
306 : 0 : void add_constrints_from_param (ParamType ¶m, Variance variance) override
307 : 0 : {}
308 : : Variance contra (Variance variance) override;
309 : :
310 : : private:
311 : : GenericTyPerCrateCtx &ctx;
312 : : std::vector<Variance> variances;
313 : : std::vector<Region> regions;
314 : : };
315 : :
316 : : /** Extracts regions of a field from regions of parent ADT. */
317 : : class FieldVisitorCtx : public VarianceVisitorCtx<Variance>
318 : : {
319 : : public:
320 : : using Visitor = VisitorBase<Variance>;
321 : :
322 : : FreeRegions collect_regions (BaseType &ty);
323 : :
324 : 5 : FieldVisitorCtx (GenericTyPerCrateCtx &ctx, const SubstitutionRef &subst,
325 : : const FreeRegions &parent_regions)
326 : 5 : : ctx (ctx), subst (subst), parent_regions (parent_regions)
327 : : {}
328 : :
329 : : void add_constraints_from_ty (BaseType *ty, Variance variance) override;
330 : : void add_constraints_from_region (const Region ®ion,
331 : : Variance variance) override;
332 : 2 : void add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
333 : : Variance variance,
334 : 2 : bool invariant_args) override{};
335 : : void add_constrints_from_param (ParamType ¶m, Variance variance) override;
336 : :
337 : 0 : Variance contra (Variance variance) override
338 : : {
339 : 0 : return Variance::transform (variance, Variance::contravariant ());
340 : : }
341 : :
342 : : private:
343 : : GenericTyPerCrateCtx &ctx;
344 : : const SubstitutionRef &subst;
345 : : FreeRegions regions;
346 : : FreeRegions parent_regions;
347 : : std::vector<size_t> type_param_ranges;
348 : : };
349 : :
350 : : } // namespace VarianceAnalysis
351 : :
352 : : } // namespace TyTy
353 : : } // namespace Rust
354 : :
355 : : #endif // RUST_TYTY_VARIANCE_ANALYSIS_PRIVATE_H
|
