]>
Commit | Line | Data |
---|---|---|
7453a54e SL |
1 | //! Constraint construction and representation |
2 | //! | |
3 | //! The second pass over the AST determines the set of constraints. | |
4 | //! We walk the set of items and, for each member, generate new constraints. | |
5 | ||
f9f354fc | 6 | use hir::def_id::{DefId, LocalDefId}; |
dfeec247 | 7 | use rustc_hir as hir; |
04454e1e | 8 | use rustc_hir::def::DefKind; |
ba9703b0 XL |
9 | use rustc_middle::ty::subst::{GenericArgKind, SubstsRef}; |
10 | use rustc_middle::ty::{self, Ty, TyCtxt}; | |
7453a54e | 11 | |
7453a54e | 12 | use super::terms::VarianceTerm::*; |
dfeec247 | 13 | use super::terms::*; |
7453a54e | 14 | |
dc9dc135 | 15 | pub struct ConstraintContext<'a, 'tcx> { |
7453a54e SL |
16 | pub terms_cx: TermsContext<'a, 'tcx>, |
17 | ||
18 | // These are pointers to common `ConstantTerm` instances | |
19 | covariant: VarianceTermPtr<'a>, | |
20 | contravariant: VarianceTermPtr<'a>, | |
21 | invariant: VarianceTermPtr<'a>, | |
22 | bivariant: VarianceTermPtr<'a>, | |
23 | ||
9e0c209e | 24 | pub constraints: Vec<Constraint<'a>>, |
7453a54e SL |
25 | } |
26 | ||
27 | /// Declares that the variable `decl_id` appears in a location with | |
28 | /// variance `variance`. | |
29 | #[derive(Copy, Clone)] | |
30 | pub struct Constraint<'a> { | |
31 | pub inferred: InferredIndex, | |
32 | pub variance: &'a VarianceTerm<'a>, | |
33 | } | |
34 | ||
3b2f2976 | 35 | /// To build constraints, we visit one item (type, trait) at a time |
0731742a | 36 | /// and look at its contents. So e.g., if we have |
04454e1e FG |
37 | /// ```ignore (illustrative) |
38 | /// struct Foo<T> { | |
39 | /// b: Bar<T> | |
40 | /// } | |
41 | /// ``` | |
7cac9316 | 42 | /// then while we are visiting `Bar<T>`, the `CurrentItem` would have |
9fa01778 | 43 | /// the `DefId` and the start of `Foo`'s inferreds. |
041b39d2 | 44 | pub struct CurrentItem { |
041b39d2 | 45 | inferred_start: InferredIndex, |
7cac9316 XL |
46 | } |
47 | ||
dfeec247 XL |
48 | pub fn add_constraints_from_crate<'a, 'tcx>( |
49 | terms_cx: TermsContext<'a, 'tcx>, | |
50 | ) -> ConstraintContext<'a, 'tcx> { | |
7453a54e SL |
51 | let tcx = terms_cx.tcx; |
52 | let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant)); | |
53 | let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant)); | |
54 | let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant)); | |
55 | let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant)); | |
56 | let mut constraint_cx = ConstraintContext { | |
3b2f2976 XL |
57 | terms_cx, |
58 | covariant, | |
59 | contravariant, | |
60 | invariant, | |
61 | bivariant, | |
7453a54e SL |
62 | constraints: Vec::new(), |
63 | }; | |
64 | ||
04454e1e FG |
65 | let crate_items = tcx.hir_crate_items(()); |
66 | ||
064997fb FG |
67 | for def_id in crate_items.definitions() { |
68 | let def_kind = tcx.def_kind(def_id); | |
04454e1e | 69 | match def_kind { |
064997fb FG |
70 | DefKind::Struct | DefKind::Union | DefKind::Enum => { |
71 | constraint_cx.build_constraints_for_item(def_id); | |
04454e1e | 72 | |
064997fb FG |
73 | let adt = tcx.adt_def(def_id); |
74 | for variant in adt.variants() { | |
487cf647 FG |
75 | if let Some(ctor_def_id) = variant.ctor_def_id() { |
76 | constraint_cx.build_constraints_for_item(ctor_def_id.expect_local()); | |
04454e1e | 77 | } |
041b39d2 XL |
78 | } |
79 | } | |
064997fb | 80 | DefKind::Fn | DefKind::AssocFn => constraint_cx.build_constraints_for_item(def_id), |
041b39d2 XL |
81 | _ => {} |
82 | } | |
83 | } | |
84 | ||
064997fb FG |
85 | constraint_cx |
86 | } | |
7cac9316 | 87 | |
064997fb | 88 | impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { |
dc9dc135 | 89 | fn tcx(&self) -> TyCtxt<'tcx> { |
7cac9316 XL |
90 | self.terms_cx.tcx |
91 | } | |
7453a54e | 92 | |
f9f354fc | 93 | fn build_constraints_for_item(&mut self, def_id: LocalDefId) { |
7cac9316 | 94 | let tcx = self.tcx(); |
49aad941 | 95 | debug!("build_constraints_for_item({})", tcx.def_path_str(def_id)); |
7453a54e | 96 | |
041b39d2 XL |
97 | // Skip items with no generics - there's nothing to infer in them. |
98 | if tcx.generics_of(def_id).count() == 0 { | |
99 | return; | |
100 | } | |
7453a54e | 101 | |
064997fb | 102 | let inferred_start = self.terms_cx.inferred_starts[&def_id]; |
abe05a73 | 103 | let current_item = &CurrentItem { inferred_start }; |
9ffffee4 | 104 | match tcx.type_of(def_id).subst_identity().kind() { |
b7449926 | 105 | ty::Adt(def, _) => { |
7453a54e SL |
106 | // Not entirely obvious: constraints on structs/enums do not |
107 | // affect the variance of their type parameters. See discussion | |
108 | // in comment at top of module. | |
109 | // | |
476ff2be | 110 | // self.add_constraints_from_generics(generics); |
7453a54e | 111 | |
041b39d2 | 112 | for field in def.all_fields() { |
dfeec247 XL |
113 | self.add_constraints_from_ty( |
114 | current_item, | |
9ffffee4 | 115 | tcx.type_of(field.did).subst_identity(), |
dfeec247 XL |
116 | self.covariant, |
117 | ); | |
7453a54e SL |
118 | } |
119 | } | |
7453a54e | 120 | |
b7449926 | 121 | ty::FnDef(..) => { |
9ffffee4 FG |
122 | self.add_constraints_from_sig( |
123 | current_item, | |
124 | tcx.fn_sig(def_id).subst_identity(), | |
125 | self.covariant, | |
126 | ); | |
7cac9316 | 127 | } |
7453a54e | 128 | |
3dfed10e | 129 | ty::Error(_) => {} |
041b39d2 | 130 | _ => { |
dfeec247 XL |
131 | span_bug!( |
132 | tcx.def_span(def_id), | |
133 | "`build_constraints_for_item` unsupported for this item" | |
134 | ); | |
7cac9316 | 135 | } |
7453a54e SL |
136 | } |
137 | } | |
138 | ||
dfeec247 | 139 | fn add_constraint(&mut self, current: &CurrentItem, index: u32, variance: VarianceTermPtr<'a>) { |
9e0c209e SL |
140 | debug!("add_constraint(index={}, variance={:?})", index, variance); |
141 | self.constraints.push(Constraint { | |
041b39d2 | 142 | inferred: InferredIndex(current.inferred_start.0 + index as usize), |
3b2f2976 | 143 | variance, |
9e0c209e | 144 | }); |
7453a54e SL |
145 | } |
146 | ||
9e0c209e | 147 | fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> { |
7453a54e SL |
148 | self.xform(variance, self.contravariant) |
149 | } | |
150 | ||
9e0c209e | 151 | fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> { |
7453a54e SL |
152 | self.xform(variance, self.invariant) |
153 | } | |
154 | ||
155 | fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> { | |
156 | match v { | |
157 | ty::Covariant => self.covariant, | |
158 | ty::Invariant => self.invariant, | |
159 | ty::Contravariant => self.contravariant, | |
160 | ty::Bivariant => self.bivariant, | |
161 | } | |
162 | } | |
163 | ||
9e0c209e | 164 | fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> { |
7453a54e SL |
165 | match (*v1, *v2) { |
166 | (_, ConstantTerm(ty::Covariant)) => { | |
167 | // Applying a "covariant" transform is always a no-op | |
168 | v1 | |
169 | } | |
170 | ||
9e0c209e | 171 | (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)), |
7453a54e | 172 | |
9e0c209e | 173 | _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)), |
7453a54e SL |
174 | } |
175 | } | |
176 | ||
6a06907d | 177 | #[instrument(level = "debug", skip(self, current))] |
dfeec247 XL |
178 | fn add_constraints_from_invariant_substs( |
179 | &mut self, | |
180 | current: &CurrentItem, | |
181 | substs: SubstsRef<'tcx>, | |
182 | variance: VarianceTermPtr<'a>, | |
183 | ) { | |
041b39d2 XL |
184 | // Trait are always invariant so we can take advantage of that. |
185 | let variance_i = self.invariant(variance); | |
041b39d2 | 186 | |
532ac7d7 XL |
187 | for k in substs { |
188 | match k.unpack() { | |
e74abb32 | 189 | GenericArgKind::Lifetime(lt) => { |
532ac7d7 XL |
190 | self.add_constraints_from_region(current, lt, variance_i) |
191 | } | |
dfeec247 | 192 | GenericArgKind::Type(ty) => self.add_constraints_from_ty(current, ty, variance_i), |
3c0e092e XL |
193 | GenericArgKind::Const(val) => { |
194 | self.add_constraints_from_const(current, val, variance_i) | |
532ac7d7 XL |
195 | } |
196 | } | |
041b39d2 | 197 | } |
7453a54e SL |
198 | } |
199 | ||
200 | /// Adds constraints appropriate for an instance of `ty` appearing | |
201 | /// in a context with the generics defined in `generics` and | |
202 | /// ambient variance `variance` | |
dfeec247 XL |
203 | fn add_constraints_from_ty( |
204 | &mut self, | |
205 | current: &CurrentItem, | |
206 | ty: Ty<'tcx>, | |
207 | variance: VarianceTermPtr<'a>, | |
208 | ) { | |
209 | debug!("add_constraints_from_ty(ty={:?}, variance={:?})", ty, variance); | |
7453a54e | 210 | |
1b1a35ee | 211 | match *ty.kind() { |
dfeec247 XL |
212 | ty::Bool |
213 | | ty::Char | |
214 | | ty::Int(_) | |
215 | | ty::Uint(_) | |
216 | | ty::Float(_) | |
217 | | ty::Str | |
218 | | ty::Never | |
219 | | ty::Foreign(..) => { | |
9e0c209e | 220 | // leaf type -- noop |
7453a54e SL |
221 | } |
222 | ||
dfeec247 | 223 | ty::FnDef(..) | ty::Generator(..) | ty::Closure(..) => { |
54a0048b | 224 | bug!("Unexpected closure type in variance computation"); |
7453a54e SL |
225 | } |
226 | ||
b7449926 | 227 | ty::Ref(region, ty, mutbl) => { |
9ffffee4 | 228 | self.add_constraints_from_region(current, region, variance); |
94b46f34 | 229 | self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance); |
7453a54e SL |
230 | } |
231 | ||
3c0e092e XL |
232 | ty::Array(typ, len) => { |
233 | self.add_constraints_from_const(current, len, variance); | |
532ac7d7 | 234 | self.add_constraints_from_ty(current, typ, variance); |
532ac7d7 XL |
235 | } |
236 | ||
b7449926 | 237 | ty::Slice(typ) => { |
7cac9316 | 238 | self.add_constraints_from_ty(current, typ, variance); |
7453a54e SL |
239 | } |
240 | ||
b7449926 | 241 | ty::RawPtr(ref mt) => { |
7cac9316 | 242 | self.add_constraints_from_mt(current, mt, variance); |
7453a54e SL |
243 | } |
244 | ||
b7449926 | 245 | ty::Tuple(subtys) => { |
f9f354fc | 246 | for subty in subtys { |
5e7ed085 | 247 | self.add_constraints_from_ty(current, subty, variance); |
7453a54e SL |
248 | } |
249 | } | |
250 | ||
b7449926 | 251 | ty::Adt(def, substs) => { |
5e7ed085 | 252 | self.add_constraints_from_substs(current, def.did(), substs, variance); |
7453a54e SL |
253 | } |
254 | ||
9c376795 | 255 | ty::Alias(_, ref data) => { |
5869c6ff | 256 | self.add_constraints_from_invariant_substs(current, data.substs, variance); |
041b39d2 XL |
257 | } |
258 | ||
f2b60f7d | 259 | ty::Dynamic(data, r, _) => { |
9ffffee4 FG |
260 | // The type `dyn Trait<T> +'a` is covariant w/r/t `'a`: |
261 | self.add_constraints_from_region(current, r, variance); | |
7453a54e | 262 | |
0731742a | 263 | if let Some(poly_trait_ref) = data.principal() { |
ba9703b0 | 264 | self.add_constraints_from_invariant_substs( |
dfeec247 | 265 | current, |
ba9703b0 | 266 | poly_trait_ref.skip_binder().substs, |
dfeec247 XL |
267 | variance, |
268 | ); | |
0731742a | 269 | } |
7453a54e | 270 | |
476ff2be | 271 | for projection in data.projection_bounds() { |
f2b60f7d FG |
272 | match projection.skip_binder().term.unpack() { |
273 | ty::TermKind::Ty(ty) => { | |
5099ac24 FG |
274 | self.add_constraints_from_ty(current, ty, self.invariant); |
275 | } | |
f2b60f7d | 276 | ty::TermKind::Const(c) => { |
5099ac24 FG |
277 | self.add_constraints_from_const(current, c, self.invariant) |
278 | } | |
279 | } | |
7453a54e SL |
280 | } |
281 | } | |
282 | ||
b7449926 | 283 | ty::Param(ref data) => { |
48663c56 | 284 | self.add_constraint(current, data.index, variance); |
7453a54e SL |
285 | } |
286 | ||
b7449926 | 287 | ty::FnPtr(sig) => { |
7cac9316 | 288 | self.add_constraints_from_sig(current, sig, variance); |
7453a54e SL |
289 | } |
290 | ||
f035d41b | 291 | ty::Error(_) => { |
7453a54e | 292 | // we encounter this when walking the trait references for object |
b7449926 | 293 | // types, where we use Error as the Self type |
7453a54e SL |
294 | } |
295 | ||
9ffffee4 FG |
296 | ty::Placeholder(..) |
297 | | ty::GeneratorWitness(..) | |
298 | | ty::GeneratorWitnessMIR(..) | |
299 | | ty::Bound(..) | |
300 | | ty::Infer(..) => { | |
301 | bug!("unexpected type encountered in variance inference: {}", ty); | |
7453a54e SL |
302 | } |
303 | } | |
304 | } | |
305 | ||
306 | /// Adds constraints appropriate for a nominal type (enum, struct, | |
307 | /// object, etc) appearing in a context with ambient variance `variance` | |
dfeec247 XL |
308 | fn add_constraints_from_substs( |
309 | &mut self, | |
310 | current: &CurrentItem, | |
311 | def_id: DefId, | |
312 | substs: SubstsRef<'tcx>, | |
313 | variance: VarianceTermPtr<'a>, | |
314 | ) { | |
315 | debug!( | |
316 | "add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})", | |
317 | def_id, substs, variance | |
318 | ); | |
7453a54e | 319 | |
041b39d2 XL |
320 | // We don't record `inferred_starts` entries for empty generics. |
321 | if substs.is_empty() { | |
322 | return; | |
323 | } | |
324 | ||
f9f354fc | 325 | let (local, remote) = if let Some(def_id) = def_id.as_local() { |
064997fb | 326 | (Some(self.terms_cx.inferred_starts[&def_id]), None) |
041b39d2 XL |
327 | } else { |
328 | (None, Some(self.tcx().variances_of(def_id))) | |
329 | }; | |
330 | ||
331 | for (i, k) in substs.iter().enumerate() { | |
332 | let variance_decl = if let Some(InferredIndex(start)) = local { | |
333 | // Parameter on an item defined within current crate: | |
334 | // variance not yet inferred, so return a symbolic | |
335 | // variance. | |
336 | self.terms_cx.inferred_terms[start + i] | |
337 | } else { | |
338 | // Parameter on an item defined within another crate: | |
339 | // variance already inferred, just look it up. | |
340 | self.constant_term(remote.as_ref().unwrap()[i]) | |
341 | }; | |
7453a54e | 342 | let variance_i = self.xform(variance, variance_decl); |
dfeec247 XL |
343 | debug!( |
344 | "add_constraints_from_substs: variance_decl={:?} variance_i={:?}", | |
345 | variance_decl, variance_i | |
346 | ); | |
0531ce1d | 347 | match k.unpack() { |
e74abb32 | 348 | GenericArgKind::Lifetime(lt) => { |
0531ce1d XL |
349 | self.add_constraints_from_region(current, lt, variance_i) |
350 | } | |
dfeec247 | 351 | GenericArgKind::Type(ty) => self.add_constraints_from_ty(current, ty, variance_i), |
3c0e092e XL |
352 | GenericArgKind::Const(val) => { |
353 | self.add_constraints_from_const(current, val, variance) | |
532ac7d7 | 354 | } |
041b39d2 | 355 | } |
7453a54e SL |
356 | } |
357 | } | |
358 | ||
3c0e092e XL |
359 | /// Adds constraints appropriate for a const expression `val` |
360 | /// in a context with ambient variance `variance` | |
361 | fn add_constraints_from_const( | |
362 | &mut self, | |
363 | current: &CurrentItem, | |
923072b8 | 364 | c: ty::Const<'tcx>, |
3c0e092e XL |
365 | variance: VarianceTermPtr<'a>, |
366 | ) { | |
923072b8 | 367 | debug!("add_constraints_from_const(c={:?}, variance={:?})", c, variance); |
3c0e092e | 368 | |
923072b8 | 369 | match &c.kind() { |
3c0e092e | 370 | ty::ConstKind::Unevaluated(uv) => { |
5099ac24 | 371 | self.add_constraints_from_invariant_substs(current, uv.substs, variance); |
3c0e092e XL |
372 | } |
373 | _ => {} | |
374 | } | |
375 | } | |
376 | ||
7453a54e SL |
377 | /// Adds constraints appropriate for a function with signature |
378 | /// `sig` appearing in a context with ambient variance `variance` | |
dfeec247 XL |
379 | fn add_constraints_from_sig( |
380 | &mut self, | |
381 | current: &CurrentItem, | |
382 | sig: ty::PolyFnSig<'tcx>, | |
383 | variance: VarianceTermPtr<'a>, | |
384 | ) { | |
7453a54e | 385 | let contra = self.contravariant(variance); |
83c7162d | 386 | for &input in sig.skip_binder().inputs() { |
7cac9316 | 387 | self.add_constraints_from_ty(current, input, contra); |
7453a54e | 388 | } |
83c7162d | 389 | self.add_constraints_from_ty(current, sig.skip_binder().output(), variance); |
7453a54e SL |
390 | } |
391 | ||
392 | /// Adds constraints appropriate for a region appearing in a | |
393 | /// context with ambient variance `variance` | |
dfeec247 XL |
394 | fn add_constraints_from_region( |
395 | &mut self, | |
396 | current: &CurrentItem, | |
397 | region: ty::Region<'tcx>, | |
398 | variance: VarianceTermPtr<'a>, | |
399 | ) { | |
9e0c209e | 400 | match *region { |
7453a54e | 401 | ty::ReEarlyBound(ref data) => { |
041b39d2 | 402 | self.add_constraint(current, data.index, variance); |
7453a54e SL |
403 | } |
404 | ||
9e0c209e | 405 | ty::ReStatic => {} |
7453a54e SL |
406 | |
407 | ty::ReLateBound(..) => { | |
041b39d2 XL |
408 | // Late-bound regions do not get substituted the same |
409 | // way early-bound regions do, so we skip them here. | |
7453a54e SL |
410 | } |
411 | ||
9ffffee4 FG |
412 | ty::ReError(_) => {} |
413 | ||
f2b60f7d | 414 | ty::ReFree(..) | ty::ReVar(..) | ty::RePlaceholder(..) | ty::ReErased => { |
7453a54e SL |
415 | // We don't expect to see anything but 'static or bound |
416 | // regions when visiting member types or method types. | |
dfeec247 XL |
417 | bug!( |
418 | "unexpected region encountered in variance \ | |
54a0048b | 419 | inference: {:?}", |
dfeec247 XL |
420 | region |
421 | ); | |
7453a54e SL |
422 | } |
423 | } | |
424 | } | |
425 | ||
426 | /// Adds constraints appropriate for a mutability-type pair | |
427 | /// appearing in a context with ambient variance `variance` | |
dfeec247 XL |
428 | fn add_constraints_from_mt( |
429 | &mut self, | |
430 | current: &CurrentItem, | |
431 | mt: &ty::TypeAndMut<'tcx>, | |
432 | variance: VarianceTermPtr<'a>, | |
433 | ) { | |
7453a54e | 434 | match mt.mutbl { |
dfeec247 | 435 | hir::Mutability::Mut => { |
7453a54e | 436 | let invar = self.invariant(variance); |
7cac9316 | 437 | self.add_constraints_from_ty(current, mt.ty, invar); |
7453a54e SL |
438 | } |
439 | ||
dfeec247 | 440 | hir::Mutability::Not => { |
7cac9316 | 441 | self.add_constraints_from_ty(current, mt.ty, variance); |
7453a54e SL |
442 | } |
443 | } | |
444 | } | |
445 | } |