1 //! Constraint construction and representation
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.
6 use hir::def_id::{DefId, LocalDefId};
8 use rustc_hir::def::DefKind;
9 use rustc_middle::ty::subst::{GenericArgKind, SubstsRef};
10 use rustc_middle::ty::{self, Ty, TyCtxt};
12 use super::terms::VarianceTerm::*;
15 pub struct ConstraintContext<'a, 'tcx> {
16 pub terms_cx: TermsContext<'a, 'tcx>,
18 // These are pointers to common `ConstantTerm` instances
19 covariant: VarianceTermPtr<'a>,
20 contravariant: VarianceTermPtr<'a>,
21 invariant: VarianceTermPtr<'a>,
22 bivariant: VarianceTermPtr<'a>,
24 pub constraints: Vec<Constraint<'a>>,
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>,
35 /// To build constraints, we visit one item (type, trait) at a time
36 /// and look at its contents. So e.g., if we have
37 /// ```ignore (illustrative)
42 /// then while we are visiting `Bar<T>`, the `CurrentItem` would have
43 /// the `DefId` and the start of `Foo`'s inferreds.
44 pub struct CurrentItem {
45 inferred_start: InferredIndex,
48 pub fn add_constraints_from_crate<'a, 'tcx>(
49 terms_cx: TermsContext<'a, 'tcx>,
50 ) -> ConstraintContext<'a, 'tcx> {
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 {
62 constraints: Vec::new(),
65 let crate_items = tcx.hir_crate_items(());
67 for def_id in crate_items.definitions() {
68 let def_kind = tcx.def_kind(def_id);
70 DefKind::Struct | DefKind::Union | DefKind::Enum => {
71 constraint_cx.build_constraints_for_item(def_id);
73 let adt = tcx.adt_def(def_id);
74 for variant in adt.variants() {
75 if let Some(ctor_def_id) = variant.ctor_def_id() {
76 constraint_cx.build_constraints_for_item(ctor_def_id.expect_local());
80 DefKind::Fn | DefKind::AssocFn => constraint_cx.build_constraints_for_item(def_id),
88 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
89 fn tcx(&self) -> TyCtxt<'tcx> {
93 fn build_constraints_for_item(&mut self, def_id: LocalDefId) {
95 debug!("build_constraints_for_item({})", tcx.def_path_str(def_id.to_def_id()));
97 // Skip items with no generics - there's nothing to infer in them.
98 if tcx.generics_of(def_id).count() == 0 {
102 let inferred_start = self.terms_cx.inferred_starts[&def_id];
103 let current_item = &CurrentItem { inferred_start };
104 match tcx.type_of(def_id).kind() {
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.
110 // self.add_constraints_from_generics(generics);
112 for field in def.all_fields() {
113 self.add_constraints_from_ty(
115 tcx.type_of(field.did),
122 self.add_constraints_from_sig(current_item, tcx.fn_sig(def_id), self.covariant);
128 tcx.def_span(def_id),
129 "`build_constraints_for_item` unsupported for this item"
135 fn add_constraint(&mut self, current: &CurrentItem, index: u32, variance: VarianceTermPtr<'a>) {
136 debug!("add_constraint(index={}, variance={:?})", index, variance);
137 self.constraints.push(Constraint {
138 inferred: InferredIndex(current.inferred_start.0 + index as usize),
143 fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
144 self.xform(variance, self.contravariant)
147 fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
148 self.xform(variance, self.invariant)
151 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
153 ty::Covariant => self.covariant,
154 ty::Invariant => self.invariant,
155 ty::Contravariant => self.contravariant,
156 ty::Bivariant => self.bivariant,
160 fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
162 (_, ConstantTerm(ty::Covariant)) => {
163 // Applying a "covariant" transform is always a no-op
167 (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
169 _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
173 #[instrument(level = "debug", skip(self, current))]
174 fn add_constraints_from_invariant_substs(
176 current: &CurrentItem,
177 substs: SubstsRef<'tcx>,
178 variance: VarianceTermPtr<'a>,
180 // Trait are always invariant so we can take advantage of that.
181 let variance_i = self.invariant(variance);
185 GenericArgKind::Lifetime(lt) => {
186 self.add_constraints_from_region(current, lt, variance_i)
188 GenericArgKind::Type(ty) => self.add_constraints_from_ty(current, ty, variance_i),
189 GenericArgKind::Const(val) => {
190 self.add_constraints_from_const(current, val, variance_i)
196 /// Adds constraints appropriate for an instance of `ty` appearing
197 /// in a context with the generics defined in `generics` and
198 /// ambient variance `variance`
199 fn add_constraints_from_ty(
201 current: &CurrentItem,
203 variance: VarianceTermPtr<'a>,
205 debug!("add_constraints_from_ty(ty={:?}, variance={:?})", ty, variance);
215 | ty::Foreign(..) => {
219 ty::FnDef(..) | ty::Generator(..) | ty::Closure(..) => {
220 bug!("Unexpected closure type in variance computation");
223 ty::Ref(region, ty, mutbl) => {
224 let contra = self.contravariant(variance);
225 self.add_constraints_from_region(current, region, contra);
226 self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance);
229 ty::Array(typ, len) => {
230 self.add_constraints_from_const(current, len, variance);
231 self.add_constraints_from_ty(current, typ, variance);
235 self.add_constraints_from_ty(current, typ, variance);
238 ty::RawPtr(ref mt) => {
239 self.add_constraints_from_mt(current, mt, variance);
242 ty::Tuple(subtys) => {
243 for subty in subtys {
244 self.add_constraints_from_ty(current, subty, variance);
248 ty::Adt(def, substs) => {
249 self.add_constraints_from_substs(current, def.did(), substs, variance);
252 ty::Alias(ty::Projection, ref data) => {
253 self.add_constraints_from_invariant_substs(current, data.substs, variance);
256 ty::Alias(ty::Opaque, ty::AliasTy { def_id: _, substs }) => {
257 self.add_constraints_from_invariant_substs(current, substs, variance);
260 ty::Dynamic(data, r, _) => {
261 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
262 let contra = self.contravariant(variance);
263 self.add_constraints_from_region(current, r, contra);
265 if let Some(poly_trait_ref) = data.principal() {
266 self.add_constraints_from_invariant_substs(
268 poly_trait_ref.skip_binder().substs,
273 for projection in data.projection_bounds() {
274 match projection.skip_binder().term.unpack() {
275 ty::TermKind::Ty(ty) => {
276 self.add_constraints_from_ty(current, ty, self.invariant);
278 ty::TermKind::Const(c) => {
279 self.add_constraints_from_const(current, c, self.invariant)
285 ty::Param(ref data) => {
286 self.add_constraint(current, data.index, variance);
290 self.add_constraints_from_sig(current, sig, variance);
294 // we encounter this when walking the trait references for object
295 // types, where we use Error as the Self type
298 ty::Placeholder(..) | ty::GeneratorWitness(..) | ty::Bound(..) | ty::Infer(..) => {
300 "unexpected type encountered in \
301 variance inference: {}",
308 /// Adds constraints appropriate for a nominal type (enum, struct,
309 /// object, etc) appearing in a context with ambient variance `variance`
310 fn add_constraints_from_substs(
312 current: &CurrentItem,
314 substs: SubstsRef<'tcx>,
315 variance: VarianceTermPtr<'a>,
318 "add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
319 def_id, substs, variance
322 // We don't record `inferred_starts` entries for empty generics.
323 if substs.is_empty() {
327 let (local, remote) = if let Some(def_id) = def_id.as_local() {
328 (Some(self.terms_cx.inferred_starts[&def_id]), None)
330 (None, Some(self.tcx().variances_of(def_id)))
333 for (i, k) in substs.iter().enumerate() {
334 let variance_decl = if let Some(InferredIndex(start)) = local {
335 // Parameter on an item defined within current crate:
336 // variance not yet inferred, so return a symbolic
338 self.terms_cx.inferred_terms[start + i]
340 // Parameter on an item defined within another crate:
341 // variance already inferred, just look it up.
342 self.constant_term(remote.as_ref().unwrap()[i])
344 let variance_i = self.xform(variance, variance_decl);
346 "add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
347 variance_decl, variance_i
350 GenericArgKind::Lifetime(lt) => {
351 self.add_constraints_from_region(current, lt, variance_i)
353 GenericArgKind::Type(ty) => self.add_constraints_from_ty(current, ty, variance_i),
354 GenericArgKind::Const(val) => {
355 self.add_constraints_from_const(current, val, variance)
361 /// Adds constraints appropriate for a const expression `val`
362 /// in a context with ambient variance `variance`
363 fn add_constraints_from_const(
365 current: &CurrentItem,
367 variance: VarianceTermPtr<'a>,
369 debug!("add_constraints_from_const(c={:?}, variance={:?})", c, variance);
372 ty::ConstKind::Unevaluated(uv) => {
373 self.add_constraints_from_invariant_substs(current, uv.substs, variance);
379 /// Adds constraints appropriate for a function with signature
380 /// `sig` appearing in a context with ambient variance `variance`
381 fn add_constraints_from_sig(
383 current: &CurrentItem,
384 sig: ty::PolyFnSig<'tcx>,
385 variance: VarianceTermPtr<'a>,
387 let contra = self.contravariant(variance);
388 for &input in sig.skip_binder().inputs() {
389 self.add_constraints_from_ty(current, input, contra);
391 self.add_constraints_from_ty(current, sig.skip_binder().output(), variance);
394 /// Adds constraints appropriate for a region appearing in a
395 /// context with ambient variance `variance`
396 fn add_constraints_from_region(
398 current: &CurrentItem,
399 region: ty::Region<'tcx>,
400 variance: VarianceTermPtr<'a>,
403 ty::ReEarlyBound(ref data) => {
404 self.add_constraint(current, data.index, variance);
409 ty::ReLateBound(..) => {
410 // Late-bound regions do not get substituted the same
411 // way early-bound regions do, so we skip them here.
414 ty::ReFree(..) | ty::ReVar(..) | ty::RePlaceholder(..) | ty::ReErased => {
415 // We don't expect to see anything but 'static or bound
416 // regions when visiting member types or method types.
418 "unexpected region encountered in variance \
426 /// Adds constraints appropriate for a mutability-type pair
427 /// appearing in a context with ambient variance `variance`
428 fn add_constraints_from_mt(
430 current: &CurrentItem,
431 mt: &ty::TypeAndMut<'tcx>,
432 variance: VarianceTermPtr<'a>,
435 hir::Mutability::Mut => {
436 let invar = self.invariant(variance);
437 self.add_constraints_from_ty(current, mt.ty, invar);
440 hir::Mutability::Not => {
441 self.add_constraints_from_ty(current, mt.ty, variance);