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;
7 use rustc::ty::subst::{SubstsRef, GenericArgKind};
8 use rustc::ty::{self, Ty, TyCtxt};
10 use rustc::hir::itemlikevisit::ItemLikeVisitor;
13 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
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>(terms_cx: TermsContext<'a, 'tcx>)
49 -> ConstraintContext<'a, 'tcx> {
50 let tcx = terms_cx.tcx;
51 let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant));
52 let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant));
53 let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant));
54 let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant));
55 let mut constraint_cx = ConstraintContext {
61 constraints: Vec::new(),
64 tcx.hir().krate().visit_all_item_likes(&mut constraint_cx);
69 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
70 fn visit_item(&mut self, item: &hir::Item) {
72 hir::ItemKind::Struct(ref struct_def, _) |
73 hir::ItemKind::Union(ref struct_def, _) => {
74 self.visit_node_helper(item.hir_id);
76 if let hir::VariantData::Tuple(..) = *struct_def {
77 self.visit_node_helper(struct_def.ctor_hir_id().unwrap());
81 hir::ItemKind::Enum(ref enum_def, _) => {
82 self.visit_node_helper(item.hir_id);
84 for variant in &enum_def.variants {
85 if let hir::VariantData::Tuple(..) = variant.data {
86 self.visit_node_helper(variant.data.ctor_hir_id().unwrap());
91 hir::ItemKind::Fn(..) => {
92 self.visit_node_helper(item.hir_id);
95 hir::ItemKind::ForeignMod(ref foreign_mod) => {
96 for foreign_item in &foreign_mod.items {
97 if let hir::ForeignItemKind::Fn(..) = foreign_item.node {
98 self.visit_node_helper(foreign_item.hir_id);
107 fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) {
108 if let hir::TraitItemKind::Method(..) = trait_item.kind {
109 self.visit_node_helper(trait_item.hir_id);
113 fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) {
114 if let hir::ImplItemKind::Method(..) = impl_item.kind {
115 self.visit_node_helper(impl_item.hir_id);
120 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
121 fn visit_node_helper(&mut self, id: hir::HirId) {
122 let tcx = self.terms_cx.tcx;
123 let def_id = tcx.hir().local_def_id(id);
124 self.build_constraints_for_item(def_id);
127 fn tcx(&self) -> TyCtxt<'tcx> {
131 fn build_constraints_for_item(&mut self, def_id: DefId) {
132 let tcx = self.tcx();
133 debug!("build_constraints_for_item({})", tcx.def_path_str(def_id));
135 // Skip items with no generics - there's nothing to infer in them.
136 if tcx.generics_of(def_id).count() == 0 {
140 let id = tcx.hir().as_local_hir_id(def_id).unwrap();
141 let inferred_start = self.terms_cx.inferred_starts[&id];
142 let current_item = &CurrentItem { inferred_start };
143 match tcx.type_of(def_id).kind {
145 // Not entirely obvious: constraints on structs/enums do not
146 // affect the variance of their type parameters. See discussion
147 // in comment at top of module.
149 // self.add_constraints_from_generics(generics);
151 for field in def.all_fields() {
152 self.add_constraints_from_ty(current_item,
153 tcx.type_of(field.did),
159 self.add_constraints_from_sig(current_item,
165 span_bug!(tcx.def_span(def_id),
166 "`build_constraints_for_item` unsupported for this item");
171 fn add_constraint(&mut self,
172 current: &CurrentItem,
174 variance: VarianceTermPtr<'a>) {
175 debug!("add_constraint(index={}, variance={:?})", index, variance);
176 self.constraints.push(Constraint {
177 inferred: InferredIndex(current.inferred_start.0 + index as usize),
182 fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
183 self.xform(variance, self.contravariant)
186 fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
187 self.xform(variance, self.invariant)
190 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
192 ty::Covariant => self.covariant,
193 ty::Invariant => self.invariant,
194 ty::Contravariant => self.contravariant,
195 ty::Bivariant => self.bivariant,
199 fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
201 (_, ConstantTerm(ty::Covariant)) => {
202 // Applying a "covariant" transform is always a no-op
206 (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
208 _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
212 fn add_constraints_from_trait_ref(&mut self,
213 current: &CurrentItem,
214 trait_ref: ty::TraitRef<'tcx>,
215 variance: VarianceTermPtr<'a>) {
216 debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
219 self.add_constraints_from_invariant_substs(current, trait_ref.substs, variance);
222 fn add_constraints_from_invariant_substs(&mut self,
223 current: &CurrentItem,
224 substs: SubstsRef<'tcx>,
225 variance: VarianceTermPtr<'a>) {
226 debug!("add_constraints_from_invariant_substs: substs={:?} variance={:?}",
230 // Trait are always invariant so we can take advantage of that.
231 let variance_i = self.invariant(variance);
235 GenericArgKind::Lifetime(lt) => {
236 self.add_constraints_from_region(current, lt, variance_i)
238 GenericArgKind::Type(ty) => {
239 self.add_constraints_from_ty(current, ty, variance_i)
241 GenericArgKind::Const(_) => {
242 // Consts impose no constraints.
248 /// Adds constraints appropriate for an instance of `ty` appearing
249 /// in a context with the generics defined in `generics` and
250 /// ambient variance `variance`
251 fn add_constraints_from_ty(&mut self,
252 current: &CurrentItem,
254 variance: VarianceTermPtr<'a>) {
255 debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
260 ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) |
261 ty::Str | ty::Never | ty::Foreign(..) => {
268 bug!("Unexpected closure type in variance computation");
271 ty::Ref(region, ty, mutbl) => {
272 let contra = self.contravariant(variance);
273 self.add_constraints_from_region(current, region, contra);
274 self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance);
277 ty::Array(typ, _) => {
278 self.add_constraints_from_ty(current, typ, variance);
282 self.add_constraints_from_ty(current, typ, variance);
285 ty::RawPtr(ref mt) => {
286 self.add_constraints_from_mt(current, mt, variance);
289 ty::Tuple(subtys) => {
290 for &subty in subtys {
291 self.add_constraints_from_ty(current, subty.expect_ty(), variance);
295 ty::Adt(def, substs) => {
296 self.add_constraints_from_substs(current, def.did, substs, variance);
299 ty::Projection(ref data) => {
300 let tcx = self.tcx();
301 self.add_constraints_from_trait_ref(current, data.trait_ref(tcx), variance);
304 ty::Opaque(_, substs) => {
305 self.add_constraints_from_invariant_substs(current, substs, variance);
308 ty::Dynamic(ref data, r) => {
309 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
310 let contra = self.contravariant(variance);
311 self.add_constraints_from_region(current, r, contra);
313 if let Some(poly_trait_ref) = data.principal() {
315 poly_trait_ref.with_self_ty(self.tcx(), self.tcx().types.err);
316 self.add_constraints_from_trait_ref(
317 current, *poly_trait_ref.skip_binder(), variance);
320 for projection in data.projection_bounds() {
321 self.add_constraints_from_ty(
322 current, projection.skip_binder().ty, self.invariant);
326 ty::Param(ref data) => {
327 self.add_constraint(current, data.index, variance);
331 self.add_constraints_from_sig(current, sig, variance);
335 // we encounter this when walking the trait references for object
336 // types, where we use Error as the Self type
339 ty::Placeholder(..) |
340 ty::UnnormalizedProjection(..) |
341 ty::GeneratorWitness(..) |
344 bug!("unexpected type encountered in \
345 variance inference: {}",
351 /// Adds constraints appropriate for a nominal type (enum, struct,
352 /// object, etc) appearing in a context with ambient variance `variance`
353 fn add_constraints_from_substs(&mut self,
354 current: &CurrentItem,
356 substs: SubstsRef<'tcx>,
357 variance: VarianceTermPtr<'a>) {
358 debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
363 // We don't record `inferred_starts` entries for empty generics.
364 if substs.is_empty() {
368 let (local, remote) = if let Some(id) = self.tcx().hir().as_local_hir_id(def_id) {
369 (Some(self.terms_cx.inferred_starts[&id]), None)
371 (None, Some(self.tcx().variances_of(def_id)))
374 for (i, k) in substs.iter().enumerate() {
375 let variance_decl = if let Some(InferredIndex(start)) = local {
376 // Parameter on an item defined within current crate:
377 // variance not yet inferred, so return a symbolic
379 self.terms_cx.inferred_terms[start + i]
381 // Parameter on an item defined within another crate:
382 // variance already inferred, just look it up.
383 self.constant_term(remote.as_ref().unwrap()[i])
385 let variance_i = self.xform(variance, variance_decl);
386 debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
390 GenericArgKind::Lifetime(lt) => {
391 self.add_constraints_from_region(current, lt, variance_i)
393 GenericArgKind::Type(ty) => {
394 self.add_constraints_from_ty(current, ty, variance_i)
396 GenericArgKind::Const(_) => {
397 // Consts impose no constraints.
403 /// Adds constraints appropriate for a function with signature
404 /// `sig` appearing in a context with ambient variance `variance`
405 fn add_constraints_from_sig(&mut self,
406 current: &CurrentItem,
407 sig: ty::PolyFnSig<'tcx>,
408 variance: VarianceTermPtr<'a>) {
409 let contra = self.contravariant(variance);
410 for &input in sig.skip_binder().inputs() {
411 self.add_constraints_from_ty(current, input, contra);
413 self.add_constraints_from_ty(current, sig.skip_binder().output(), variance);
416 /// Adds constraints appropriate for a region appearing in a
417 /// context with ambient variance `variance`
418 fn add_constraints_from_region(&mut self,
419 current: &CurrentItem,
420 region: ty::Region<'tcx>,
421 variance: VarianceTermPtr<'a>) {
423 ty::ReEarlyBound(ref data) => {
424 self.add_constraint(current, data.index, variance);
429 ty::ReLateBound(..) => {
430 // Late-bound regions do not get substituted the same
431 // way early-bound regions do, so we skip them here.
435 ty::ReClosureBound(..) |
438 ty::RePlaceholder(..) |
441 // We don't expect to see anything but 'static or bound
442 // regions when visiting member types or method types.
443 bug!("unexpected region encountered in variance \
450 /// Adds constraints appropriate for a mutability-type pair
451 /// appearing in a context with ambient variance `variance`
452 fn add_constraints_from_mt(&mut self,
453 current: &CurrentItem,
454 mt: &ty::TypeAndMut<'tcx>,
455 variance: VarianceTermPtr<'a>) {
458 let invar = self.invariant(variance);
459 self.add_constraints_from_ty(current, mt.ty, invar);
462 hir::MutImmutable => {
463 self.add_constraints_from_ty(current, mt.ty, variance);