src/librustc_typeck/variance/constraints.rs

   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.
   4 //
   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.
  10
  11 //! Constraint construction and representation
  12 //!
  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.
  15
  16 use hir::def_id::DefId;
  17 use middle::resolve_lifetime as rl;
  18 use rustc::ty::subst::Substs;
  19 use rustc::ty::{self, Ty, TyCtxt};
  20 use rustc::hir::map as hir_map;
  21 use syntax::ast;
  22 use rustc::hir;
  23 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  24
  25 use super::terms::*;
  26 use super::terms::VarianceTerm::*;
  27 use super::xform::*;
  28
  29 use dep_graph::DepNode::ItemSignature as VarianceDepNode;
  30
  31 pub struct ConstraintContext<'a, 'tcx: 'a> {
  32     pub terms_cx: TermsContext<'a, 'tcx>,
  33
  34     // These are pointers to common `ConstantTerm` instances
  35     covariant: VarianceTermPtr<'a>,
  36     contravariant: VarianceTermPtr<'a>,
  37     invariant: VarianceTermPtr<'a>,
  38     bivariant: VarianceTermPtr<'a>,
  39
  40     pub constraints: Vec<Constraint<'a>>,
  41 }
  42
  43 /// Declares that the variable `decl_id` appears in a location with
  44 /// variance `variance`.
  45 #[derive(Copy, Clone)]
  46 pub struct Constraint<'a> {
  47     pub inferred: InferredIndex,
  48     pub variance: &'a VarianceTerm<'a>,
  49 }
  50
  51 pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>)
  52                                             -> ConstraintContext<'a, 'tcx> {
  53     let tcx = terms_cx.tcx;
  54     let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant));
  55     let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant));
  56     let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant));
  57     let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant));
  58     let mut constraint_cx = ConstraintContext {
  59         terms_cx: terms_cx,
  60         covariant: covariant,
  61         contravariant: contravariant,
  62         invariant: invariant,
  63         bivariant: bivariant,
  64         constraints: Vec::new(),
  65     };
  66
  67     // See README.md for a discussion on dep-graph management.
  68     tcx.visit_all_item_likes_in_krate(VarianceDepNode, &mut constraint_cx);
  69
  70     constraint_cx
  71 }
  72
  73 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
  74     fn visit_item(&mut self, item: &hir::Item) {
  75         let tcx = self.terms_cx.tcx;
  76         let did = tcx.hir.local_def_id(item.id);
  77
  78         debug!("visit_item item={}", tcx.hir.node_to_string(item.id));
  79
  80         match item.node {
  81             hir::ItemEnum(..) |
  82             hir::ItemStruct(..) |
  83             hir::ItemUnion(..) => {
  84                 let generics = tcx.item_generics(did);
  85
  86                 // Not entirely obvious: constraints on structs/enums do not
  87                 // affect the variance of their type parameters. See discussion
  88                 // in comment at top of module.
  89                 //
  90                 // self.add_constraints_from_generics(generics);
  91
  92                 for field in tcx.lookup_adt_def(did).all_fields() {
  93                     self.add_constraints_from_ty(generics,
  94                                                  tcx.item_type(field.did),
  95                                                  self.covariant);
  96                 }
  97             }
  98             hir::ItemTrait(..) => {
  99                 let generics = tcx.item_generics(did);
 100                 let trait_ref = ty::TraitRef {
 101                     def_id: did,
 102                     substs: Substs::identity_for_item(tcx, did)
 103                 };
 104                 self.add_constraints_from_trait_ref(generics,
 105                                                     trait_ref,
 106                                                     self.invariant);
 107             }
 108
 109             hir::ItemExternCrate(_) |
 110             hir::ItemUse(..) |
 111             hir::ItemStatic(..) |
 112             hir::ItemConst(..) |
 113             hir::ItemFn(..) |
 114             hir::ItemMod(..) |
 115             hir::ItemForeignMod(..) |
 116             hir::ItemTy(..) |
 117             hir::ItemImpl(..) |
 118             hir::ItemDefaultImpl(..) => {}
 119         }
 120     }
 121
 122     fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) {
 123     }
 124
 125     fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) {
 126     }
 127 }
 128
 129 /// Is `param_id` a lifetime according to `map`?
 130 fn is_lifetime(map: &hir_map::Map, param_id: ast::NodeId) -> bool {
 131     match map.find(param_id) {
 132         Some(hir_map::NodeLifetime(..)) => true,
 133         _ => false,
 134     }
 135 }
 136
 137 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 138     fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
 139         self.terms_cx.tcx
 140     }
 141
 142     fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
 143         match self.terms_cx.inferred_map.get(&param_id) {
 144             Some(&index) => index,
 145             None => {
 146                 bug!("no inferred index entry for {}",
 147                      self.tcx().hir.node_to_string(param_id));
 148             }
 149         }
 150     }
 151
 152     fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
 153         let tcx = self.terms_cx.tcx;
 154         assert!(is_lifetime(&tcx.hir, param_id));
 155         match tcx.named_region_map.defs.get(&param_id) {
 156             Some(&rl::Region::EarlyBound(_, lifetime_decl_id)) => lifetime_decl_id,
 157             Some(_) => bug!("should not encounter non early-bound cases"),
 158
 159             // The lookup should only fail when `param_id` is
 160             // itself a lifetime binding: use it as the decl_id.
 161             None => param_id,
 162         }
 163
 164     }
 165
 166     /// Is `param_id` a type parameter for which we infer variance?
 167     fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
 168         let result = self.terms_cx.inferred_map.contains_key(&param_id);
 169
 170         // To safe-guard against invalid inferred_map constructions,
 171         // double-check if variance is inferred at some use of a type
 172         // parameter (by inspecting parent of its binding declaration
 173         // to see if it is introduced by a type or by a fn/impl).
 174
 175         let check_result = |this: &ConstraintContext| -> bool {
 176             let tcx = this.terms_cx.tcx;
 177             let decl_id = this.find_binding_for_lifetime(param_id);
 178             // Currently only called on lifetimes; double-checking that.
 179             assert!(is_lifetime(&tcx.hir, param_id));
 180             let parent_id = tcx.hir.get_parent(decl_id);
 181             let parent = tcx.hir
 182                 .find(parent_id)
 183                 .unwrap_or_else(|| bug!("tcx.hir missing entry for id: {}", parent_id));
 184
 185             let is_inferred;
 186             macro_rules! cannot_happen { () => { {
 187                 bug!("invalid parent: {} for {}",
 188                      tcx.hir.node_to_string(parent_id),
 189                      tcx.hir.node_to_string(param_id));
 190             } } }
 191
 192             match parent {
 193                 hir_map::NodeItem(p) => {
 194                     match p.node {
 195                         hir::ItemTy(..) |
 196                         hir::ItemEnum(..) |
 197                         hir::ItemStruct(..) |
 198                         hir::ItemUnion(..) |
 199                         hir::ItemTrait(..) => is_inferred = true,
 200                         hir::ItemFn(..) => is_inferred = false,
 201                         _ => cannot_happen!(),
 202                     }
 203                 }
 204                 hir_map::NodeTraitItem(..) => is_inferred = false,
 205                 hir_map::NodeImplItem(..) => is_inferred = false,
 206                 _ => cannot_happen!(),
 207             }
 208
 209             return is_inferred;
 210         };
 211
 212         assert_eq!(result, check_result(self));
 213
 214         return result;
 215     }
 216
 217     /// Returns a variance term representing the declared variance of the type/region parameter
 218     /// with the given id.
 219     fn declared_variance(&self,
 220                          param_def_id: DefId,
 221                          item_def_id: DefId,
 222                          index: usize)
 223                          -> VarianceTermPtr<'a> {
 224         assert_eq!(param_def_id.krate, item_def_id.krate);
 225
 226         if let Some(param_node_id) = self.tcx().hir.as_local_node_id(param_def_id) {
 227             // Parameter on an item defined within current crate:
 228             // variance not yet inferred, so return a symbolic
 229             // variance.
 230             let InferredIndex(index) = self.inferred_index(param_node_id);
 231             self.terms_cx.inferred_infos[index].term
 232         } else {
 233             // Parameter on an item defined within another crate:
 234             // variance already inferred, just look it up.
 235             let variances = self.tcx().item_variances(item_def_id);
 236             self.constant_term(variances[index])
 237         }
 238     }
 239
 240     fn add_constraint(&mut self,
 241                       InferredIndex(index): InferredIndex,
 242                       variance: VarianceTermPtr<'a>) {
 243         debug!("add_constraint(index={}, variance={:?})", index, variance);
 244         self.constraints.push(Constraint {
 245             inferred: InferredIndex(index),
 246             variance: variance,
 247         });
 248     }
 249
 250     fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 251         self.xform(variance, self.contravariant)
 252     }
 253
 254     fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 255         self.xform(variance, self.invariant)
 256     }
 257
 258     fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
 259         match v {
 260             ty::Covariant => self.covariant,
 261             ty::Invariant => self.invariant,
 262             ty::Contravariant => self.contravariant,
 263             ty::Bivariant => self.bivariant,
 264         }
 265     }
 266
 267     fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 268         match (*v1, *v2) {
 269             (_, ConstantTerm(ty::Covariant)) => {
 270                 // Applying a "covariant" transform is always a no-op
 271                 v1
 272             }
 273
 274             (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
 275
 276             _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
 277         }
 278     }
 279
 280     fn add_constraints_from_trait_ref(&mut self,
 281                                       generics: &ty::Generics,
 282                                       trait_ref: ty::TraitRef<'tcx>,
 283                                       variance: VarianceTermPtr<'a>) {
 284         debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
 285                trait_ref,
 286                variance);
 287
 288         let trait_generics = self.tcx().item_generics(trait_ref.def_id);
 289
 290         // This edge is actually implied by the call to
 291         // `lookup_trait_def`, but I'm trying to be future-proof. See
 292         // README.md for a discussion on dep-graph management.
 293         self.tcx().dep_graph.read(VarianceDepNode(trait_ref.def_id));
 294
 295         self.add_constraints_from_substs(generics,
 296                                          trait_ref.def_id,
 297                                          &trait_generics.types,
 298                                          &trait_generics.regions,
 299                                          trait_ref.substs,
 300                                          variance);
 301     }
 302
 303     /// Adds constraints appropriate for an instance of `ty` appearing
 304     /// in a context with the generics defined in `generics` and
 305     /// ambient variance `variance`
 306     fn add_constraints_from_ty(&mut self,
 307                                generics: &ty::Generics,
 308                                ty: Ty<'tcx>,
 309                                variance: VarianceTermPtr<'a>) {
 310         debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
 311                ty,
 312                variance);
 313
 314         match ty.sty {
 315             ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
 316             ty::TyStr | ty::TyNever => {
 317                 // leaf type -- noop
 318             }
 319
 320             ty::TyClosure(..) |
 321             ty::TyAnon(..) => {
 322                 bug!("Unexpected closure type in variance computation");
 323             }
 324
 325             ty::TyRef(region, ref mt) => {
 326                 let contra = self.contravariant(variance);
 327                 self.add_constraints_from_region(generics, region, contra);
 328                 self.add_constraints_from_mt(generics, mt, variance);
 329             }
 330
 331             ty::TyArray(typ, _) |
 332             ty::TySlice(typ) => {
 333                 self.add_constraints_from_ty(generics, typ, variance);
 334             }
 335
 336             ty::TyRawPtr(ref mt) => {
 337                 self.add_constraints_from_mt(generics, mt, variance);
 338             }
 339
 340             ty::TyTuple(subtys, _) => {
 341                 for &subty in subtys {
 342                     self.add_constraints_from_ty(generics, subty, variance);
 343                 }
 344             }
 345
 346             ty::TyAdt(def, substs) => {
 347                 let adt_generics = self.tcx().item_generics(def.did);
 348
 349                 // This edge is actually implied by the call to
 350                 // `lookup_trait_def`, but I'm trying to be future-proof. See
 351                 // README.md for a discussion on dep-graph management.
 352                 self.tcx().dep_graph.read(VarianceDepNode(def.did));
 353
 354                 self.add_constraints_from_substs(generics,
 355                                                  def.did,
 356                                                  &adt_generics.types,
 357                                                  &adt_generics.regions,
 358                                                  substs,
 359                                                  variance);
 360             }
 361
 362             ty::TyProjection(ref data) => {
 363                 let trait_ref = &data.trait_ref;
 364                 let trait_generics = self.tcx().item_generics(trait_ref.def_id);
 365
 366                 // This edge is actually implied by the call to
 367                 // `lookup_trait_def`, but I'm trying to be future-proof. See
 368                 // README.md for a discussion on dep-graph management.
 369                 self.tcx().dep_graph.read(VarianceDepNode(trait_ref.def_id));
 370
 371                 self.add_constraints_from_substs(generics,
 372                                                  trait_ref.def_id,
 373                                                  &trait_generics.types,
 374                                                  &trait_generics.regions,
 375                                                  trait_ref.substs,
 376                                                  variance);
 377             }
 378
 379             ty::TyDynamic(ref data, r) => {
 380                 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
 381                 let contra = self.contravariant(variance);
 382                 self.add_constraints_from_region(generics, r, contra);
 383
 384                 if let Some(p) = data.principal() {
 385                     let poly_trait_ref = p.with_self_ty(self.tcx(), self.tcx().types.err);
 386                     self.add_constraints_from_trait_ref(generics, poly_trait_ref.0, variance);
 387                 }
 388
 389                 for projection in data.projection_bounds() {
 390                     self.add_constraints_from_ty(generics, projection.0.ty, self.invariant);
 391                 }
 392             }
 393
 394             ty::TyParam(ref data) => {
 395                 assert_eq!(generics.parent, None);
 396                 let mut i = data.idx as usize;
 397                 if !generics.has_self || i > 0 {
 398                     i -= generics.regions.len();
 399                 }
 400                 let def_id = generics.types[i].def_id;
 401                 let node_id = self.tcx().hir.as_local_node_id(def_id).unwrap();
 402                 match self.terms_cx.inferred_map.get(&node_id) {
 403                     Some(&index) => {
 404                         self.add_constraint(index, variance);
 405                     }
 406                     None => {
 407                         // We do not infer variance for type parameters
 408                         // declared on methods. They will not be present
 409                         // in the inferred_map.
 410                     }
 411                 }
 412             }
 413
 414             ty::TyFnDef(.., sig) |
 415             ty::TyFnPtr(sig) => {
 416                 self.add_constraints_from_sig(generics, sig, variance);
 417             }
 418
 419             ty::TyError => {
 420                 // we encounter this when walking the trait references for object
 421                 // types, where we use TyError as the Self type
 422             }
 423
 424             ty::TyInfer(..) => {
 425                 bug!("unexpected type encountered in \
 426                       variance inference: {}",
 427                      ty);
 428             }
 429         }
 430     }
 431
 432     /// Adds constraints appropriate for a nominal type (enum, struct,
 433     /// object, etc) appearing in a context with ambient variance `variance`
 434     fn add_constraints_from_substs(&mut self,
 435                                    generics: &ty::Generics,
 436                                    def_id: DefId,
 437                                    type_param_defs: &[ty::TypeParameterDef],
 438                                    region_param_defs: &[ty::RegionParameterDef],
 439                                    substs: &Substs<'tcx>,
 440                                    variance: VarianceTermPtr<'a>) {
 441         debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
 442                def_id,
 443                substs,
 444                variance);
 445
 446         for p in type_param_defs {
 447             let variance_decl = self.declared_variance(p.def_id, def_id, p.index as usize);
 448             let variance_i = self.xform(variance, variance_decl);
 449             let substs_ty = substs.type_for_def(p);
 450             debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
 451                    variance_decl,
 452                    variance_i);
 453             self.add_constraints_from_ty(generics, substs_ty, variance_i);
 454         }
 455
 456         for p in region_param_defs {
 457             let variance_decl = self.declared_variance(p.def_id, def_id, p.index as usize);
 458             let variance_i = self.xform(variance, variance_decl);
 459             let substs_r = substs.region_for_def(p);
 460             self.add_constraints_from_region(generics, substs_r, variance_i);
 461         }
 462     }
 463
 464     /// Adds constraints appropriate for a function with signature
 465     /// `sig` appearing in a context with ambient variance `variance`
 466     fn add_constraints_from_sig(&mut self,
 467                                 generics: &ty::Generics,
 468                                 sig: ty::PolyFnSig<'tcx>,
 469                                 variance: VarianceTermPtr<'a>) {
 470         let contra = self.contravariant(variance);
 471         for &input in sig.0.inputs() {
 472             self.add_constraints_from_ty(generics, input, contra);
 473         }
 474         self.add_constraints_from_ty(generics, sig.0.output(), variance);
 475     }
 476
 477     /// Adds constraints appropriate for a region appearing in a
 478     /// context with ambient variance `variance`
 479     fn add_constraints_from_region(&mut self,
 480                                    generics: &ty::Generics,
 481                                    region: &'tcx ty::Region,
 482                                    variance: VarianceTermPtr<'a>) {
 483         match *region {
 484             ty::ReEarlyBound(ref data) => {
 485                 assert_eq!(generics.parent, None);
 486                 let i = data.index as usize - generics.has_self as usize;
 487                 let def_id = generics.regions[i].def_id;
 488                 let node_id = self.tcx().hir.as_local_node_id(def_id).unwrap();
 489                 if self.is_to_be_inferred(node_id) {
 490                     let index = self.inferred_index(node_id);
 491                     self.add_constraint(index, variance);
 492                 }
 493             }
 494
 495             ty::ReStatic => {}
 496
 497             ty::ReLateBound(..) => {
 498                 // We do not infer variance for region parameters on
 499                 // methods or in fn types.
 500             }
 501
 502             ty::ReFree(..) |
 503             ty::ReScope(..) |
 504             ty::ReVar(..) |
 505             ty::ReSkolemized(..) |
 506             ty::ReEmpty |
 507             ty::ReErased => {
 508                 // We don't expect to see anything but 'static or bound
 509                 // regions when visiting member types or method types.
 510                 bug!("unexpected region encountered in variance \
 511                       inference: {:?}",
 512                      region);
 513             }
 514         }
 515     }
 516
 517     /// Adds constraints appropriate for a mutability-type pair
 518     /// appearing in a context with ambient variance `variance`
 519     fn add_constraints_from_mt(&mut self,
 520                                generics: &ty::Generics,
 521                                mt: &ty::TypeAndMut<'tcx>,
 522                                variance: VarianceTermPtr<'a>) {
 523         match mt.mutbl {
 524             hir::MutMutable => {
 525                 let invar = self.invariant(variance);
 526                 self.add_constraints_from_ty(generics, mt.ty, invar);
 527             }
 528
 529             hir::MutImmutable => {
 530                 self.add_constraints_from_ty(generics, mt.ty, variance);
 531             }
 532         }
 533     }
 534 }