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