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 middle::resolve_lifetime as rl;
18 use rustc::dep_graph::{AssertDepGraphSafe, DepNode};
19 use rustc::ty::subst::Substs;
20 use rustc::ty::{self, Ty, TyCtxt};
21 use rustc::hir::map as hir_map;
24 use rustc::hir::itemlikevisit::ItemLikeVisitor;
26 use rustc_data_structures::transitive_relation::TransitiveRelation;
29 use super::terms::VarianceTerm::*;
31 pub struct ConstraintContext<'a, 'tcx: 'a> {
32 pub terms_cx: TermsContext<'a, 'tcx>,
34 // These are pointers to common `ConstantTerm` instances
35 covariant: VarianceTermPtr<'a>,
36 contravariant: VarianceTermPtr<'a>,
37 invariant: VarianceTermPtr<'a>,
38 bivariant: VarianceTermPtr<'a>,
40 pub constraints: Vec<Constraint<'a>>,
42 /// This relation tracks the dependencies between the variance of
43 /// various items. In particular, if `a < b`, then the variance of
44 /// `a` depends on the sources of `b`.
45 pub dependencies: TransitiveRelation<DefId>,
48 /// Declares that the variable `decl_id` appears in a location with
49 /// variance `variance`.
50 #[derive(Copy, Clone)]
51 pub struct Constraint<'a> {
52 pub inferred: InferredIndex,
53 pub variance: &'a VarianceTerm<'a>,
56 /// To build constriants, we visit one item (type, trait) at a time
57 /// and look at its contents. So e.g. if we have
63 /// then while we are visiting `Bar<T>`, the `CurrentItem` would have
64 /// the def-id and generics of `Foo`.
65 pub struct CurrentItem<'a> {
67 generics: &'a ty::Generics,
70 pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>)
71 -> ConstraintContext<'a, 'tcx> {
72 let tcx = terms_cx.tcx;
73 let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant));
74 let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant));
75 let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant));
76 let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant));
77 let mut constraint_cx = ConstraintContext {
80 contravariant: contravariant,
83 constraints: Vec::new(),
84 dependencies: TransitiveRelation::new(),
87 tcx.hir.krate().visit_all_item_likes(&mut constraint_cx);
92 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
93 fn visit_item(&mut self, item: &hir::Item) {
94 let tcx = self.terms_cx.tcx;
95 let def_id = tcx.hir.local_def_id(item.id);
97 // Encapsulate constructing the constraints into a task we can
98 // reference later. This can go away once the red-green
99 // algorithm is in place.
101 // See README.md for a detailed discussion
102 // on dep-graph management.
105 hir::ItemStruct(..) |
106 hir::ItemUnion(..) => {
107 tcx.dep_graph.with_task(DepNode::ItemVarianceConstraints(def_id),
108 AssertDepGraphSafe(self),
113 // Nothing to do here, skip the task.
117 fn visit_item_task<'a, 'tcx>(ccx: AssertDepGraphSafe<&mut ConstraintContext<'a, 'tcx>>,
120 ccx.0.build_constraints_for_item(def_id);
124 fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) {
127 fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) {
131 /// Is `param_id` a lifetime according to `map`?
132 fn is_lifetime(map: &hir_map::Map, param_id: ast::NodeId) -> bool {
133 match map.find(param_id) {
134 Some(hir_map::NodeLifetime(..)) => true,
139 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
140 fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
144 fn build_constraints_for_item(&mut self, def_id: DefId) {
145 let tcx = self.tcx();
146 let id = self.tcx().hir.as_local_node_id(def_id).unwrap();
147 let item = tcx.hir.expect_item(id);
148 debug!("visit_item item={}", tcx.hir.node_to_string(item.id));
152 hir::ItemStruct(..) |
153 hir::ItemUnion(..) => {
154 let generics = tcx.generics_of(def_id);
155 let current_item = &CurrentItem { def_id, generics };
157 // Not entirely obvious: constraints on structs/enums do not
158 // affect the variance of their type parameters. See discussion
159 // in comment at top of module.
161 // self.add_constraints_from_generics(generics);
163 for field in tcx.adt_def(def_id).all_fields() {
164 self.add_constraints_from_ty(current_item,
165 tcx.type_of(field.did),
171 hir::ItemExternCrate(_) |
173 hir::ItemStatic(..) |
177 hir::ItemForeignMod(..) |
178 hir::ItemGlobalAsm(..) |
181 hir::ItemDefaultImpl(..) => {
182 span_bug!(item.span, "`build_constraints_for_item` invoked for non-type-def");
187 /// Load the generics for another item, adding a corresponding
188 /// relation into the dependencies to indicate that the variance
189 /// for `current` relies on `def_id`.
190 fn read_generics(&mut self, current: &CurrentItem, def_id: DefId) -> &'tcx ty::Generics {
191 let generics = self.tcx().generics_of(def_id);
192 if self.tcx().dep_graph.is_fully_enabled() {
193 self.dependencies.add(current.def_id, def_id);
198 fn opt_inferred_index(&self, param_id: ast::NodeId) -> Option<&InferredIndex> {
199 self.terms_cx.inferred_map.get(¶m_id)
202 fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
203 let tcx = self.terms_cx.tcx;
204 assert!(is_lifetime(&tcx.hir, param_id));
205 match tcx.named_region_map.defs.get(¶m_id) {
206 Some(&rl::Region::EarlyBound(_, lifetime_decl_id)) => lifetime_decl_id,
207 Some(_) => bug!("should not encounter non early-bound cases"),
209 // The lookup should only fail when `param_id` is
210 // itself a lifetime binding: use it as the decl_id.
216 /// Is `param_id` a type parameter for which we infer variance?
217 fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
218 let result = self.terms_cx.inferred_map.contains_key(¶m_id);
220 // To safe-guard against invalid inferred_map constructions,
221 // double-check if variance is inferred at some use of a type
222 // parameter (by inspecting parent of its binding declaration
223 // to see if it is introduced by a type or by a fn/impl).
225 let check_result = |this: &ConstraintContext| -> bool {
226 let tcx = this.terms_cx.tcx;
227 let decl_id = this.find_binding_for_lifetime(param_id);
228 // Currently only called on lifetimes; double-checking that.
229 assert!(is_lifetime(&tcx.hir, param_id));
230 let parent_id = tcx.hir.get_parent(decl_id);
233 .unwrap_or_else(|| bug!("tcx.hir missing entry for id: {}", parent_id));
236 macro_rules! cannot_happen { () => { {
237 bug!("invalid parent: {} for {}",
238 tcx.hir.node_to_string(parent_id),
239 tcx.hir.node_to_string(param_id));
243 hir_map::NodeItem(p) => {
247 hir::ItemStruct(..) |
249 hir::ItemTrait(..) => is_inferred = true,
250 hir::ItemFn(..) => is_inferred = false,
251 _ => cannot_happen!(),
254 hir_map::NodeTraitItem(..) => is_inferred = false,
255 hir_map::NodeImplItem(..) => is_inferred = false,
256 _ => cannot_happen!(),
262 assert_eq!(result, check_result(self));
267 /// Returns a variance term representing the declared variance of the type/region parameter
268 /// with the given id.
269 fn declared_variance(&self,
273 -> VarianceTermPtr<'a> {
274 assert_eq!(param_def_id.krate, item_def_id.krate);
276 if let Some(param_node_id) = self.tcx().hir.as_local_node_id(param_def_id) {
277 // Parameter on an item defined within current crate:
278 // variance not yet inferred, so return a symbolic
280 if let Some(&InferredIndex(index)) = self.opt_inferred_index(param_node_id) {
281 self.terms_cx.inferred_infos[index].term
283 // If there is no inferred entry for a type parameter,
284 // it must be declared on a (locally defiend) trait -- they don't
285 // get inferreds because they are always invariant.
286 if cfg!(debug_assertions) {
287 let item_node_id = self.tcx().hir.as_local_node_id(item_def_id).unwrap();
288 let item = self.tcx().hir.expect_item(item_node_id);
289 let success = match item.node {
290 hir::ItemTrait(..) => true,
294 bug!("parameter {:?} has no inferred, but declared on non-trait: {:?}",
302 // Parameter on an item defined within another crate:
303 // variance already inferred, just look it up.
304 let variances = self.tcx().variances_of(item_def_id);
305 self.constant_term(variances[index])
309 fn add_constraint(&mut self,
310 InferredIndex(index): InferredIndex,
311 variance: VarianceTermPtr<'a>) {
312 debug!("add_constraint(index={}, variance={:?})", index, variance);
313 self.constraints.push(Constraint {
314 inferred: InferredIndex(index),
319 fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
320 self.xform(variance, self.contravariant)
323 fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
324 self.xform(variance, self.invariant)
327 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
329 ty::Covariant => self.covariant,
330 ty::Invariant => self.invariant,
331 ty::Contravariant => self.contravariant,
332 ty::Bivariant => self.bivariant,
336 fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
338 (_, ConstantTerm(ty::Covariant)) => {
339 // Applying a "covariant" transform is always a no-op
343 (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
345 _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
349 fn add_constraints_from_trait_ref(&mut self,
350 current: &CurrentItem,
351 trait_ref: ty::TraitRef<'tcx>,
352 variance: VarianceTermPtr<'a>) {
353 debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
357 let trait_generics = self.tcx().generics_of(trait_ref.def_id);
359 self.add_constraints_from_substs(current,
361 &trait_generics.types,
362 &trait_generics.regions,
367 /// Adds constraints appropriate for an instance of `ty` appearing
368 /// in a context with the generics defined in `generics` and
369 /// ambient variance `variance`
370 fn add_constraints_from_ty(&mut self,
371 current: &CurrentItem,
373 variance: VarianceTermPtr<'a>) {
374 debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
379 ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
380 ty::TyStr | ty::TyNever => {
386 bug!("Unexpected closure type in variance computation");
389 ty::TyRef(region, ref mt) => {
390 let contra = self.contravariant(variance);
391 self.add_constraints_from_region(current, region, contra);
392 self.add_constraints_from_mt(current, mt, variance);
395 ty::TyArray(typ, _) |
396 ty::TySlice(typ) => {
397 self.add_constraints_from_ty(current, typ, variance);
400 ty::TyRawPtr(ref mt) => {
401 self.add_constraints_from_mt(current, mt, variance);
404 ty::TyTuple(subtys, _) => {
405 for &subty in subtys {
406 self.add_constraints_from_ty(current, subty, variance);
410 ty::TyAdt(def, substs) => {
411 let adt_generics = self.read_generics(current, def.did);
413 self.add_constraints_from_substs(current,
416 &adt_generics.regions,
421 ty::TyProjection(ref data) => {
422 let trait_ref = &data.trait_ref;
423 let trait_generics = self.tcx().generics_of(trait_ref.def_id);
425 self.add_constraints_from_substs(current,
427 &trait_generics.types,
428 &trait_generics.regions,
433 ty::TyDynamic(ref data, r) => {
434 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
435 let contra = self.contravariant(variance);
436 self.add_constraints_from_region(current, r, contra);
438 if let Some(p) = data.principal() {
439 let poly_trait_ref = p.with_self_ty(self.tcx(), self.tcx().types.err);
440 self.add_constraints_from_trait_ref(current, poly_trait_ref.0, variance);
443 for projection in data.projection_bounds() {
444 self.add_constraints_from_ty(current, projection.0.ty, self.invariant);
448 ty::TyParam(ref data) => {
449 assert_eq!(current.generics.parent, None);
450 let mut i = data.idx as usize;
451 if !current.generics.has_self || i > 0 {
452 i -= current.generics.regions.len();
454 let def_id = current.generics.types[i].def_id;
455 let node_id = self.tcx().hir.as_local_node_id(def_id).unwrap();
456 match self.terms_cx.inferred_map.get(&node_id) {
458 self.add_constraint(index, variance);
461 // We do not infer variance for type parameters
462 // declared on methods. They will not be present
463 // in the inferred_map.
468 ty::TyFnDef(.., sig) |
469 ty::TyFnPtr(sig) => {
470 self.add_constraints_from_sig(current, sig, variance);
474 // we encounter this when walking the trait references for object
475 // types, where we use TyError as the Self type
479 bug!("unexpected type encountered in \
480 variance inference: {}",
486 /// Adds constraints appropriate for a nominal type (enum, struct,
487 /// object, etc) appearing in a context with ambient variance `variance`
488 fn add_constraints_from_substs(&mut self,
489 current: &CurrentItem,
491 type_param_defs: &[ty::TypeParameterDef],
492 region_param_defs: &[ty::RegionParameterDef],
493 substs: &Substs<'tcx>,
494 variance: VarianceTermPtr<'a>) {
495 debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
500 for p in type_param_defs {
501 let variance_decl = self.declared_variance(p.def_id, def_id, p.index as usize);
502 let variance_i = self.xform(variance, variance_decl);
503 let substs_ty = substs.type_for_def(p);
504 debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
507 self.add_constraints_from_ty(current, substs_ty, variance_i);
510 for p in region_param_defs {
511 let variance_decl = self.declared_variance(p.def_id, def_id, p.index as usize);
512 let variance_i = self.xform(variance, variance_decl);
513 let substs_r = substs.region_for_def(p);
514 self.add_constraints_from_region(current, substs_r, variance_i);
518 /// Adds constraints appropriate for a function with signature
519 /// `sig` appearing in a context with ambient variance `variance`
520 fn add_constraints_from_sig(&mut self,
521 current: &CurrentItem,
522 sig: ty::PolyFnSig<'tcx>,
523 variance: VarianceTermPtr<'a>) {
524 let contra = self.contravariant(variance);
525 for &input in sig.0.inputs() {
526 self.add_constraints_from_ty(current, input, contra);
528 self.add_constraints_from_ty(current, sig.0.output(), variance);
531 /// Adds constraints appropriate for a region appearing in a
532 /// context with ambient variance `variance`
533 fn add_constraints_from_region(&mut self,
534 current: &CurrentItem,
535 region: ty::Region<'tcx>,
536 variance: VarianceTermPtr<'a>) {
538 ty::ReEarlyBound(ref data) => {
539 assert_eq!(current.generics.parent, None);
540 let i = data.index as usize - current.generics.has_self as usize;
541 let def_id = current.generics.regions[i].def_id;
542 let node_id = self.tcx().hir.as_local_node_id(def_id).unwrap();
543 if self.is_to_be_inferred(node_id) {
544 let &index = self.opt_inferred_index(node_id).unwrap();
545 self.add_constraint(index, variance);
551 ty::ReLateBound(..) => {
552 // We do not infer variance for region parameters on
553 // methods or in fn types.
559 ty::ReSkolemized(..) |
562 // We don't expect to see anything but 'static or bound
563 // regions when visiting member types or method types.
564 bug!("unexpected region encountered in variance \
571 /// Adds constraints appropriate for a mutability-type pair
572 /// appearing in a context with ambient variance `variance`
573 fn add_constraints_from_mt(&mut self,
574 current: &CurrentItem,
575 mt: &ty::TypeAndMut<'tcx>,
576 variance: VarianceTermPtr<'a>) {
579 let invar = self.invariant(variance);
580 self.add_constraints_from_ty(current, mt.ty, invar);
583 hir::MutImmutable => {
584 self.add_constraints_from_ty(current, mt.ty, variance);