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