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::mir::interpret::ConstValue;
8 use rustc::ty::subst::{SubstsRef, UnpackedKind};
9 use rustc::ty::{self, Ty, TyCtxt};
11 use rustc::hir::itemlikevisit::ItemLikeVisitor;
14 use super::terms::VarianceTerm::*;
16 pub struct ConstraintContext<'a, 'tcx: 'a> {
17 pub terms_cx: TermsContext<'a, 'tcx>,
19 // These are pointers to common `ConstantTerm` instances
20 covariant: VarianceTermPtr<'a>,
21 contravariant: VarianceTermPtr<'a>,
22 invariant: VarianceTermPtr<'a>,
23 bivariant: VarianceTermPtr<'a>,
25 pub constraints: Vec<Constraint<'a>>,
28 /// Declares that the variable `decl_id` appears in a location with
29 /// variance `variance`.
30 #[derive(Copy, Clone)]
31 pub struct Constraint<'a> {
32 pub inferred: InferredIndex,
33 pub variance: &'a VarianceTerm<'a>,
36 /// To build constraints, we visit one item (type, trait) at a time
37 /// and look at its contents. So e.g., if we have
43 /// then while we are visiting `Bar<T>`, the `CurrentItem` would have
44 /// the `DefId` and the start of `Foo`'s inferreds.
45 pub struct CurrentItem {
46 inferred_start: InferredIndex,
49 pub fn add_constraints_from_crate<'a, 'tcx>(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 tcx.hir().krate().visit_all_item_likes(&mut constraint_cx);
70 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
71 fn visit_item(&mut self, item: &hir::Item) {
73 hir::ItemKind::Struct(ref struct_def, _) |
74 hir::ItemKind::Union(ref struct_def, _) => {
75 self.visit_node_helper(item.hir_id);
77 if let hir::VariantData::Tuple(..) = *struct_def {
78 self.visit_node_helper(struct_def.hir_id());
82 hir::ItemKind::Enum(ref enum_def, _) => {
83 self.visit_node_helper(item.hir_id);
85 for variant in &enum_def.variants {
86 if let hir::VariantData::Tuple(..) = variant.node.data {
87 self.visit_node_helper(variant.node.data.hir_id());
92 hir::ItemKind::Fn(..) => {
93 self.visit_node_helper(item.hir_id);
96 hir::ItemKind::ForeignMod(ref foreign_mod) => {
97 for foreign_item in &foreign_mod.items {
98 if let hir::ForeignItemKind::Fn(..) = foreign_item.node {
99 self.visit_node_helper(foreign_item.hir_id);
108 fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) {
109 if let hir::TraitItemKind::Method(..) = trait_item.node {
110 self.visit_node_helper(trait_item.hir_id);
114 fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) {
115 if let hir::ImplItemKind::Method(..) = impl_item.node {
116 self.visit_node_helper(impl_item.hir_id);
121 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
122 fn visit_node_helper(&mut self, id: hir::HirId) {
123 let tcx = self.terms_cx.tcx;
124 let def_id = tcx.hir().local_def_id_from_hir_id(id);
125 self.build_constraints_for_item(def_id);
128 fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
132 fn build_constraints_for_item(&mut self, def_id: DefId) {
133 let tcx = self.tcx();
134 debug!("build_constraints_for_item({})", tcx.def_path_str(def_id));
136 // Skip items with no generics - there's nothing to infer in them.
137 if tcx.generics_of(def_id).count() == 0 {
141 let id = tcx.hir().as_local_hir_id(def_id).unwrap();
142 let inferred_start = self.terms_cx.inferred_starts[&id];
143 let current_item = &CurrentItem { inferred_start };
144 match tcx.type_of(def_id).sty {
146 // Not entirely obvious: constraints on structs/enums do not
147 // affect the variance of their type parameters. See discussion
148 // in comment at top of module.
150 // self.add_constraints_from_generics(generics);
152 for field in def.all_fields() {
153 self.add_constraints_from_ty(current_item,
154 tcx.type_of(field.did),
160 self.add_constraints_from_sig(current_item,
166 span_bug!(tcx.def_span(def_id),
167 "`build_constraints_for_item` unsupported for this item");
172 fn add_constraint(&mut self,
173 current: &CurrentItem,
175 variance: VarianceTermPtr<'a>) {
176 debug!("add_constraint(index={}, variance={:?})", index, variance);
177 self.constraints.push(Constraint {
178 inferred: InferredIndex(current.inferred_start.0 + index as usize),
183 fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
184 self.xform(variance, self.contravariant)
187 fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
188 self.xform(variance, self.invariant)
191 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
193 ty::Covariant => self.covariant,
194 ty::Invariant => self.invariant,
195 ty::Contravariant => self.contravariant,
196 ty::Bivariant => self.bivariant,
200 fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
202 (_, ConstantTerm(ty::Covariant)) => {
203 // Applying a "covariant" transform is always a no-op
207 (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
209 _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
213 fn add_constraints_from_trait_ref(&mut self,
214 current: &CurrentItem,
215 trait_ref: ty::TraitRef<'tcx>,
216 variance: VarianceTermPtr<'a>) {
217 debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
220 self.add_constraints_from_invariant_substs(current, trait_ref.substs, variance);
223 fn add_constraints_from_invariant_substs(&mut self,
224 current: &CurrentItem,
225 substs: SubstsRef<'tcx>,
226 variance: VarianceTermPtr<'a>) {
227 debug!("add_constraints_from_invariant_substs: substs={:?} variance={:?}",
231 // Trait are always invariant so we can take advantage of that.
232 let variance_i = self.invariant(variance);
236 UnpackedKind::Lifetime(lt) => {
237 self.add_constraints_from_region(current, lt, variance_i)
239 UnpackedKind::Type(ty) => {
240 self.add_constraints_from_ty(current, ty, variance_i)
242 UnpackedKind::Const(ct) => {
243 self.add_constraints_from_const(current, ct, variance_i)
249 /// Adds constraints appropriate for an instance of `ty` appearing
250 /// in a context with the generics defined in `generics` and
251 /// ambient variance `variance`
252 fn add_constraints_from_ty(&mut self,
253 current: &CurrentItem,
255 variance: VarianceTermPtr<'a>) {
256 debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
261 ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) |
262 ty::Str | ty::Never | ty::Foreign(..) => {
269 bug!("Unexpected closure type in variance computation");
272 ty::Ref(region, ty, mutbl) => {
273 let contra = self.contravariant(variance);
274 self.add_constraints_from_region(current, region, contra);
275 self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance);
278 ty::Array(typ, len) => {
279 self.add_constraints_from_ty(current, typ, variance);
280 self.add_constraints_from_const(current, len, variance);
284 self.add_constraints_from_ty(current, typ, variance);
287 ty::RawPtr(ref mt) => {
288 self.add_constraints_from_mt(current, mt, variance);
291 ty::Tuple(subtys) => {
292 for &subty in subtys {
293 self.add_constraints_from_ty(current, subty, variance);
297 ty::Adt(def, substs) => {
298 self.add_constraints_from_substs(current, def.did, substs, variance);
301 ty::Projection(ref data) => {
302 let tcx = self.tcx();
303 self.add_constraints_from_trait_ref(current, data.trait_ref(tcx), variance);
306 ty::Opaque(_, substs) => {
307 self.add_constraints_from_invariant_substs(current, substs, variance);
310 ty::Dynamic(ref data, r) => {
311 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
312 let contra = self.contravariant(variance);
313 self.add_constraints_from_region(current, r, contra);
315 if let Some(poly_trait_ref) = data.principal() {
317 poly_trait_ref.with_self_ty(self.tcx(), self.tcx().types.err);
318 self.add_constraints_from_trait_ref(
319 current, *poly_trait_ref.skip_binder(), variance);
322 for projection in data.projection_bounds() {
323 self.add_constraints_from_ty(
324 current, projection.skip_binder().ty, self.invariant);
328 ty::Param(ref data) => {
329 self.add_constraint(current, data.idx, variance);
333 self.add_constraints_from_sig(current, sig, variance);
337 // we encounter this when walking the trait references for object
338 // types, where we use Error as the Self type
341 ty::Placeholder(..) |
342 ty::UnnormalizedProjection(..) |
343 ty::GeneratorWitness(..) |
346 bug!("unexpected type encountered in \
347 variance inference: {}",
353 /// Adds constraints appropriate for a nominal type (enum, struct,
354 /// object, etc) appearing in a context with ambient variance `variance`
355 fn add_constraints_from_substs(&mut self,
356 current: &CurrentItem,
358 substs: SubstsRef<'tcx>,
359 variance: VarianceTermPtr<'a>) {
360 debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
365 // We don't record `inferred_starts` entries for empty generics.
366 if substs.is_empty() {
370 let (local, remote) = if let Some(id) = self.tcx().hir().as_local_hir_id(def_id) {
371 (Some(self.terms_cx.inferred_starts[&id]), None)
373 (None, Some(self.tcx().variances_of(def_id)))
376 for (i, k) in substs.iter().enumerate() {
377 let variance_decl = if let Some(InferredIndex(start)) = local {
378 // Parameter on an item defined within current crate:
379 // variance not yet inferred, so return a symbolic
381 self.terms_cx.inferred_terms[start + i]
383 // Parameter on an item defined within another crate:
384 // variance already inferred, just look it up.
385 self.constant_term(remote.as_ref().unwrap()[i])
387 let variance_i = self.xform(variance, variance_decl);
388 debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
392 UnpackedKind::Lifetime(lt) => {
393 self.add_constraints_from_region(current, lt, variance_i)
395 UnpackedKind::Type(ty) => {
396 self.add_constraints_from_ty(current, ty, variance_i)
398 UnpackedKind::Const(ct) => {
399 self.add_constraints_from_const(current, ct, variance_i)
405 /// Adds constraints appropriate for a function with signature
406 /// `sig` appearing in a context with ambient variance `variance`
407 fn add_constraints_from_sig(&mut self,
408 current: &CurrentItem,
409 sig: ty::PolyFnSig<'tcx>,
410 variance: VarianceTermPtr<'a>) {
411 let contra = self.contravariant(variance);
412 for &input in sig.skip_binder().inputs() {
413 self.add_constraints_from_ty(current, input, contra);
415 self.add_constraints_from_ty(current, sig.skip_binder().output(), variance);
418 /// Adds constraints appropriate for a region appearing in a
419 /// context with ambient variance `variance`
420 fn add_constraints_from_region(&mut self,
421 current: &CurrentItem,
422 region: ty::Region<'tcx>,
423 variance: VarianceTermPtr<'a>) {
425 ty::ReEarlyBound(ref data) => {
426 self.add_constraint(current, data.index, variance);
431 ty::ReLateBound(..) => {
432 // Late-bound regions do not get substituted the same
433 // way early-bound regions do, so we skip them here.
437 ty::ReClosureBound(..) |
440 ty::RePlaceholder(..) |
443 // We don't expect to see anything but 'static or bound
444 // regions when visiting member types or method types.
445 bug!("unexpected region encountered in variance \
452 fn add_constraints_from_const(
454 current: &CurrentItem,
455 ct: &ty::Const<'tcx>,
456 variance: VarianceTermPtr<'a>
459 "add_constraints_from_const(ct={:?}, variance={:?})",
464 self.add_constraints_from_ty(current, ct.ty, variance);
465 if let ConstValue::Param(ref data) = ct.val {
466 self.add_constraint(current, data.index, variance);
470 /// Adds constraints appropriate for a mutability-type pair
471 /// appearing in a context with ambient variance `variance`
472 fn add_constraints_from_mt(&mut self,
473 current: &CurrentItem,
474 mt: &ty::TypeAndMut<'tcx>,
475 variance: VarianceTermPtr<'a>) {
478 let invar = self.invariant(variance);
479 self.add_constraints_from_ty(current, mt.ty, invar);
482 hir::MutImmutable => {
483 self.add_constraints_from_ty(current, mt.ty, variance);