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