1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Constraint construction and representation
13 //! The second pass over the AST determines the set of constraints.
14 //! We walk the set of items and, for each member, generate new constraints.
16 use hir::def_id::DefId;
17 use rustc::ty::subst::{Substs, UnpackedKind};
18 use rustc::ty::{self, Ty, TyCtxt};
21 use rustc::hir::itemlikevisit::ItemLikeVisitor;
24 use super::terms::VarianceTerm::*;
26 pub struct ConstraintContext<'a, 'tcx: 'a> {
27 pub terms_cx: TermsContext<'a, 'tcx>,
29 // These are pointers to common `ConstantTerm` instances
30 covariant: VarianceTermPtr<'a>,
31 contravariant: VarianceTermPtr<'a>,
32 invariant: VarianceTermPtr<'a>,
33 bivariant: VarianceTermPtr<'a>,
35 pub constraints: Vec<Constraint<'a>>,
38 /// Declares that the variable `decl_id` appears in a location with
39 /// variance `variance`.
40 #[derive(Copy, Clone)]
41 pub struct Constraint<'a> {
42 pub inferred: InferredIndex,
43 pub variance: &'a VarianceTerm<'a>,
46 /// To build constraints, we visit one item (type, trait) at a time
47 /// and look at its contents. So e.g. if we have
53 /// then while we are visiting `Bar<T>`, the `CurrentItem` would have
54 /// the def-id and the start of `Foo`'s inferreds.
55 pub struct CurrentItem {
56 inferred_start: InferredIndex,
59 pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>)
60 -> ConstraintContext<'a, 'tcx> {
61 let tcx = terms_cx.tcx;
62 let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant));
63 let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant));
64 let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant));
65 let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant));
66 let mut constraint_cx = ConstraintContext {
72 constraints: Vec::new(),
75 tcx.hir.krate().visit_all_item_likes(&mut constraint_cx);
80 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
81 fn visit_item(&mut self, item: &hir::Item) {
83 hir::ItemKind::Struct(ref struct_def, _) |
84 hir::ItemKind::Union(ref struct_def, _) => {
85 self.visit_node_helper(item.id);
87 if let hir::VariantData::Tuple(..) = *struct_def {
88 self.visit_node_helper(struct_def.id());
92 hir::ItemKind::Enum(ref enum_def, _) => {
93 self.visit_node_helper(item.id);
95 for variant in &enum_def.variants {
96 if let hir::VariantData::Tuple(..) = variant.node.data {
97 self.visit_node_helper(variant.node.data.id());
102 hir::ItemKind::Fn(..) => {
103 self.visit_node_helper(item.id);
106 hir::ItemKind::ForeignMod(ref foreign_mod) => {
107 for foreign_item in &foreign_mod.items {
108 if let hir::ForeignItemKind::Fn(..) = foreign_item.node {
109 self.visit_node_helper(foreign_item.id);
118 fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) {
119 if let hir::TraitItemKind::Method(..) = trait_item.node {
120 self.visit_node_helper(trait_item.id);
124 fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) {
125 if let hir::ImplItemKind::Method(..) = impl_item.node {
126 self.visit_node_helper(impl_item.id);
131 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
132 fn visit_node_helper(&mut self, id: ast::NodeId) {
133 let tcx = self.terms_cx.tcx;
134 let def_id = tcx.hir.local_def_id(id);
135 self.build_constraints_for_item(def_id);
138 fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
142 fn build_constraints_for_item(&mut self, def_id: DefId) {
143 let tcx = self.tcx();
144 debug!("build_constraints_for_item({})", tcx.item_path_str(def_id));
146 // Skip items with no generics - there's nothing to infer in them.
147 if tcx.generics_of(def_id).count() == 0 {
151 let id = tcx.hir.as_local_node_id(def_id).unwrap();
152 let inferred_start = self.terms_cx.inferred_starts[&id];
153 let current_item = &CurrentItem { inferred_start };
154 match tcx.type_of(def_id).sty {
156 // Not entirely obvious: constraints on structs/enums do not
157 // affect the variance of their type parameters. See discussion
158 // in comment at top of module.
160 // self.add_constraints_from_generics(generics);
162 for field in def.all_fields() {
163 self.add_constraints_from_ty(current_item,
164 tcx.type_of(field.did),
170 self.add_constraints_from_sig(current_item,
176 span_bug!(tcx.def_span(def_id),
177 "`build_constraints_for_item` unsupported for this item");
182 fn add_constraint(&mut self,
183 current: &CurrentItem,
185 variance: VarianceTermPtr<'a>) {
186 debug!("add_constraint(index={}, variance={:?})", index, variance);
187 self.constraints.push(Constraint {
188 inferred: InferredIndex(current.inferred_start.0 + index as usize),
193 fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
194 self.xform(variance, self.contravariant)
197 fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
198 self.xform(variance, self.invariant)
201 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
203 ty::Covariant => self.covariant,
204 ty::Invariant => self.invariant,
205 ty::Contravariant => self.contravariant,
206 ty::Bivariant => self.bivariant,
210 fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
212 (_, ConstantTerm(ty::Covariant)) => {
213 // Applying a "covariant" transform is always a no-op
217 (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
219 _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
223 fn add_constraints_from_trait_ref(&mut self,
224 current: &CurrentItem,
225 trait_ref: ty::TraitRef<'tcx>,
226 variance: VarianceTermPtr<'a>) {
227 debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
230 self.add_constraints_from_invariant_substs(current, trait_ref.substs, variance);
233 fn add_constraints_from_invariant_substs(&mut self,
234 current: &CurrentItem,
235 substs: &Substs<'tcx>,
236 variance: VarianceTermPtr<'a>) {
237 debug!("add_constraints_from_invariant_substs: substs={:?} variance={:?}",
241 // Trait are always invariant so we can take advantage of that.
242 let variance_i = self.invariant(variance);
243 for ty in substs.types() {
244 self.add_constraints_from_ty(current, ty, variance_i);
247 for region in substs.regions() {
248 self.add_constraints_from_region(current, region, variance_i);
252 /// Adds constraints appropriate for an instance of `ty` appearing
253 /// in a context with the generics defined in `generics` and
254 /// ambient variance `variance`
255 fn add_constraints_from_ty(&mut self,
256 current: &CurrentItem,
258 variance: VarianceTermPtr<'a>) {
259 debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
264 ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) |
265 ty::Str | ty::Never | ty::Foreign(..) => {
272 bug!("Unexpected closure type in variance computation");
275 ty::Ref(region, ty, mutbl) => {
276 let contra = self.contravariant(variance);
277 self.add_constraints_from_region(current, region, contra);
278 self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance);
283 self.add_constraints_from_ty(current, typ, variance);
286 ty::RawPtr(ref mt) => {
287 self.add_constraints_from_mt(current, mt, variance);
290 ty::Tuple(subtys) => {
291 for &subty in subtys {
292 self.add_constraints_from_ty(current, subty, variance);
296 ty::Adt(def, substs) => {
297 self.add_constraints_from_substs(current, def.did, substs, variance);
300 ty::Projection(ref data) => {
301 let tcx = self.tcx();
302 self.add_constraints_from_trait_ref(current, data.trait_ref(tcx), variance);
305 ty::Opaque(_, substs) => {
306 self.add_constraints_from_invariant_substs(current, substs, variance);
309 ty::Dynamic(ref data, r) => {
310 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
311 let contra = self.contravariant(variance);
312 self.add_constraints_from_region(current, r, contra);
314 if let Some(p) = data.principal() {
315 let poly_trait_ref = p.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.idx, 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::UnnormalizedProjection(..) |
340 ty::GeneratorWitness(..) |
342 bug!("unexpected type encountered in \
343 variance inference: {}",
349 /// Adds constraints appropriate for a nominal type (enum, struct,
350 /// object, etc) appearing in a context with ambient variance `variance`
351 fn add_constraints_from_substs(&mut self,
352 current: &CurrentItem,
354 substs: &Substs<'tcx>,
355 variance: VarianceTermPtr<'a>) {
356 debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
361 // We don't record `inferred_starts` entries for empty generics.
362 if substs.is_empty() {
366 let (local, remote) = if let Some(id) = self.tcx().hir.as_local_node_id(def_id) {
367 (Some(self.terms_cx.inferred_starts[&id]), None)
369 (None, Some(self.tcx().variances_of(def_id)))
372 for (i, k) in substs.iter().enumerate() {
373 let variance_decl = if let Some(InferredIndex(start)) = local {
374 // Parameter on an item defined within current crate:
375 // variance not yet inferred, so return a symbolic
377 self.terms_cx.inferred_terms[start + i]
379 // Parameter on an item defined within another crate:
380 // variance already inferred, just look it up.
381 self.constant_term(remote.as_ref().unwrap()[i])
383 let variance_i = self.xform(variance, variance_decl);
384 debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
388 UnpackedKind::Lifetime(lt) => {
389 self.add_constraints_from_region(current, lt, variance_i)
391 UnpackedKind::Type(ty) => {
392 self.add_constraints_from_ty(current, ty, variance_i)
398 /// Adds constraints appropriate for a function with signature
399 /// `sig` appearing in a context with ambient variance `variance`
400 fn add_constraints_from_sig(&mut self,
401 current: &CurrentItem,
402 sig: ty::PolyFnSig<'tcx>,
403 variance: VarianceTermPtr<'a>) {
404 let contra = self.contravariant(variance);
405 for &input in sig.skip_binder().inputs() {
406 self.add_constraints_from_ty(current, input, contra);
408 self.add_constraints_from_ty(current, sig.skip_binder().output(), variance);
411 /// Adds constraints appropriate for a region appearing in a
412 /// context with ambient variance `variance`
413 fn add_constraints_from_region(&mut self,
414 current: &CurrentItem,
415 region: ty::Region<'tcx>,
416 variance: VarianceTermPtr<'a>) {
418 ty::ReEarlyBound(ref data) => {
419 self.add_constraint(current, data.index, variance);
424 ty::ReLateBound(..) => {
425 // Late-bound regions do not get substituted the same
426 // way early-bound regions do, so we skip them here.
431 ty::ReClosureBound(..) |
434 ty::ReSkolemized(..) |
437 // We don't expect to see anything but 'static or bound
438 // regions when visiting member types or method types.
439 bug!("unexpected region encountered in variance \
446 /// Adds constraints appropriate for a mutability-type pair
447 /// appearing in a context with ambient variance `variance`
448 fn add_constraints_from_mt(&mut self,
449 current: &CurrentItem,
450 mt: &ty::TypeAndMut<'tcx>,
451 variance: VarianceTermPtr<'a>) {
454 let invar = self.invariant(variance);
455 self.add_constraints_from_ty(current, mt.ty, invar);
458 hir::MutImmutable => {
459 self.add_constraints_from_ty(current, mt.ty, variance);