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