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 4306 : 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 3665 : template <typename VARIANCE> class VarianceVisitorCtx
60 : {
61 : public:
62 3068 : 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 6093 : VisitorBase (VarianceVisitorCtx<VARIANCE> &ctx, VARIANCE variance)
95 6093 : : ctx (ctx), variance (variance)
96 : {}
97 :
98 206 : void visit (BoolType &type) override {}
99 47 : void visit (CharType &type) override {}
100 2006 : 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 4510 : 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 3068 : class GenericTyVisitorCtx : VarianceVisitorCtx<Term>
237 : {
238 : using Visitor = VisitorBase<Term>;
239 :
240 : public:
241 3068 : 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
|
