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::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;
  22 use syntax::ast;
  23 use rustc::hir;
  24 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  25
  26 use rustc_data_structures::transitive_relation::TransitiveRelation;
  27
  28 use super::terms::*;
  29 use super::terms::VarianceTerm::*;
  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     /// 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>,
  46 }
  47
  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>,
  54 }
  55
  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
  58 ///
  59 ///     struct Foo<T> {
  60 ///         b: Bar<T>
  61 ///     }
  62 ///
  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> {
  66     def_id: DefId,
  67     generics: &'a ty::Generics,
  68 }
  69
  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 {
  78         terms_cx: terms_cx,
  79         covariant: covariant,
  80         contravariant: contravariant,
  81         invariant: invariant,
  82         bivariant: bivariant,
  83         constraints: Vec::new(),
  84         dependencies: TransitiveRelation::new(),
  85     };
  86
  87     tcx.hir.krate().visit_all_item_likes(&mut constraint_cx);
  88
  89     constraint_cx
  90 }
  91
  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);
  96
  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.
 100         //
 101         // See README.md for a detailed discussion
 102         // on dep-graph management.
 103         match item.node {
 104             hir::ItemEnum(..) |
 105             hir::ItemStruct(..) |
 106             hir::ItemUnion(..) => {
 107                 tcx.dep_graph.with_task(DepNode::ItemVarianceConstraints(def_id),
 108                                         AssertDepGraphSafe(self),
 109                                         def_id,
 110                                         visit_item_task);
 111             }
 112             _ => {
 113                 // Nothing to do here, skip the task.
 114             }
 115         }
 116
 117         fn visit_item_task<'a, 'tcx>(ccx: AssertDepGraphSafe<&mut ConstraintContext<'a, 'tcx>>,
 118                                      def_id: DefId)
 119         {
 120             ccx.0.build_constraints_for_item(def_id);
 121         }
 122     }
 123
 124     fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) {
 125     }
 126
 127     fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) {
 128     }
 129 }
 130
 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,
 135         _ => false,
 136     }
 137 }
 138
 139 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 140     fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
 141         self.terms_cx.tcx
 142     }
 143
 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));
 149
 150         match item.node {
 151             hir::ItemEnum(..) |
 152             hir::ItemStruct(..) |
 153             hir::ItemUnion(..) => {
 154                 let generics = tcx.generics_of(def_id);
 155                 let current_item = &CurrentItem { def_id, generics };
 156
 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.
 160                 //
 161                 // self.add_constraints_from_generics(generics);
 162
 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),
 166                                                  self.covariant);
 167                 }
 168             }
 169
 170             hir::ItemTrait(..) |
 171             hir::ItemExternCrate(_) |
 172             hir::ItemUse(..) |
 173             hir::ItemStatic(..) |
 174             hir::ItemConst(..) |
 175             hir::ItemFn(..) |
 176             hir::ItemMod(..) |
 177             hir::ItemForeignMod(..) |
 178             hir::ItemGlobalAsm(..) |
 179             hir::ItemTy(..) |
 180             hir::ItemImpl(..) |
 181             hir::ItemDefaultImpl(..) => {
 182                 span_bug!(item.span, "`build_constraints_for_item` invoked for non-type-def");
 183             }
 184         }
 185     }
 186
 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);
 194         }
 195         generics
 196     }
 197
 198     fn opt_inferred_index(&self, param_id: ast::NodeId) -> Option<&InferredIndex> {
 199         self.terms_cx.inferred_map.get(&param_id)
 200     }
 201
 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(&param_id) {
 206             Some(&rl::Region::EarlyBound(_, lifetime_decl_id)) => lifetime_decl_id,
 207             Some(_) => bug!("should not encounter non early-bound cases"),
 208
 209             // The lookup should only fail when `param_id` is
 210             // itself a lifetime binding: use it as the decl_id.
 211             None => param_id,
 212         }
 213
 214     }
 215
 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(&param_id);
 219
 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).
 224
 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);
 231             let parent = tcx.hir
 232                 .find(parent_id)
 233                 .unwrap_or_else(|| bug!("tcx.hir missing entry for id: {}", parent_id));
 234
 235             let is_inferred;
 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));
 240             } } }
 241
 242             match parent {
 243                 hir_map::NodeItem(p) => {
 244                     match p.node {
 245                         hir::ItemTy(..) |
 246                         hir::ItemEnum(..) |
 247                         hir::ItemStruct(..) |
 248                         hir::ItemUnion(..) |
 249                         hir::ItemTrait(..) => is_inferred = true,
 250                         hir::ItemFn(..) => is_inferred = false,
 251                         _ => cannot_happen!(),
 252                     }
 253                 }
 254                 hir_map::NodeTraitItem(..) => is_inferred = false,
 255                 hir_map::NodeImplItem(..) => is_inferred = false,
 256                 _ => cannot_happen!(),
 257             }
 258
 259             return is_inferred;
 260         };
 261
 262         assert_eq!(result, check_result(self));
 263
 264         return result;
 265     }
 266
 267     /// Returns a variance term representing the declared variance of the type/region parameter
 268     /// with the given id.
 269     fn declared_variance(&self,
 270                          param_def_id: DefId,
 271                          item_def_id: DefId,
 272                          index: usize)
 273                          -> VarianceTermPtr<'a> {
 274         assert_eq!(param_def_id.krate, item_def_id.krate);
 275
 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
 279             // variance.
 280             if let Some(&InferredIndex(index)) = self.opt_inferred_index(param_node_id) {
 281                 self.terms_cx.inferred_infos[index].term
 282             } else {
 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,
 291                         _ => false,
 292                     };
 293                     if !success {
 294                         bug!("parameter {:?} has no inferred, but declared on non-trait: {:?}",
 295                              item_def_id,
 296                              item);
 297                     }
 298                 }
 299                 self.invariant
 300             }
 301         } else {
 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])
 306         }
 307     }
 308
 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),
 315             variance: variance,
 316         });
 317     }
 318
 319     fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 320         self.xform(variance, self.contravariant)
 321     }
 322
 323     fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 324         self.xform(variance, self.invariant)
 325     }
 326
 327     fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
 328         match v {
 329             ty::Covariant => self.covariant,
 330             ty::Invariant => self.invariant,
 331             ty::Contravariant => self.contravariant,
 332             ty::Bivariant => self.bivariant,
 333         }
 334     }
 335
 336     fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 337         match (*v1, *v2) {
 338             (_, ConstantTerm(ty::Covariant)) => {
 339                 // Applying a "covariant" transform is always a no-op
 340                 v1
 341             }
 342
 343             (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
 344
 345             _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
 346         }
 347     }
 348
 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={:?}",
 354                trait_ref,
 355                variance);
 356
 357         let trait_generics = self.tcx().generics_of(trait_ref.def_id);
 358
 359         self.add_constraints_from_substs(current,
 360                                          trait_ref.def_id,
 361                                          &trait_generics.types,
 362                                          &trait_generics.regions,
 363                                          trait_ref.substs,
 364                                          variance);
 365     }
 366
 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,
 372                                ty: Ty<'tcx>,
 373                                variance: VarianceTermPtr<'a>) {
 374         debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
 375                ty,
 376                variance);
 377
 378         match ty.sty {
 379             ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
 380             ty::TyStr | ty::TyNever => {
 381                 // leaf type -- noop
 382             }
 383
 384             ty::TyClosure(..) |
 385             ty::TyAnon(..) => {
 386                 bug!("Unexpected closure type in variance computation");
 387             }
 388
 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);
 393             }
 394
 395             ty::TyArray(typ, _) |
 396             ty::TySlice(typ) => {
 397                 self.add_constraints_from_ty(current, typ, variance);
 398             }
 399
 400             ty::TyRawPtr(ref mt) => {
 401                 self.add_constraints_from_mt(current, mt, variance);
 402             }
 403
 404             ty::TyTuple(subtys, _) => {
 405                 for &subty in subtys {
 406                     self.add_constraints_from_ty(current, subty, variance);
 407                 }
 408             }
 409
 410             ty::TyAdt(def, substs) => {
 411                 let adt_generics = self.read_generics(current, def.did);
 412
 413                 self.add_constraints_from_substs(current,
 414                                                  def.did,
 415                                                  &adt_generics.types,
 416                                                  &adt_generics.regions,
 417                                                  substs,
 418                                                  variance);
 419             }
 420
 421             ty::TyProjection(ref data) => {
 422                 let trait_ref = &data.trait_ref;
 423                 let trait_generics = self.tcx().generics_of(trait_ref.def_id);
 424
 425                 self.add_constraints_from_substs(current,
 426                                                  trait_ref.def_id,
 427                                                  &trait_generics.types,
 428                                                  &trait_generics.regions,
 429                                                  trait_ref.substs,
 430                                                  variance);
 431             }
 432
 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);
 437
 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);
 441                 }
 442
 443                 for projection in data.projection_bounds() {
 444                     self.add_constraints_from_ty(current, projection.0.ty, self.invariant);
 445                 }
 446             }
 447
 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();
 453                 }
 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) {
 457                     Some(&index) => {
 458                         self.add_constraint(index, variance);
 459                     }
 460                     None => {
 461                         // We do not infer variance for type parameters
 462                         // declared on methods. They will not be present
 463                         // in the inferred_map.
 464                     }
 465                 }
 466             }
 467
 468             ty::TyFnDef(.., sig) |
 469             ty::TyFnPtr(sig) => {
 470                 self.add_constraints_from_sig(current, sig, variance);
 471             }
 472
 473             ty::TyError => {
 474                 // we encounter this when walking the trait references for object
 475                 // types, where we use TyError as the Self type
 476             }
 477
 478             ty::TyInfer(..) => {
 479                 bug!("unexpected type encountered in \
 480                       variance inference: {}",
 481                      ty);
 482             }
 483         }
 484     }
 485
 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,
 490                                    def_id: DefId,
 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={:?})",
 496                def_id,
 497                substs,
 498                variance);
 499
 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={:?}",
 505                    variance_decl,
 506                    variance_i);
 507             self.add_constraints_from_ty(current, substs_ty, variance_i);
 508         }
 509
 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);
 515         }
 516     }
 517
 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);
 527         }
 528         self.add_constraints_from_ty(current, sig.0.output(), variance);
 529     }
 530
 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>) {
 537         match *region {
 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);
 546                 }
 547             }
 548
 549             ty::ReStatic => {}
 550
 551             ty::ReLateBound(..) => {
 552                 // We do not infer variance for region parameters on
 553                 // methods or in fn types.
 554             }
 555
 556             ty::ReFree(..) |
 557             ty::ReScope(..) |
 558             ty::ReVar(..) |
 559             ty::ReSkolemized(..) |
 560             ty::ReEmpty |
 561             ty::ReErased => {
 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 \
 565                       inference: {:?}",
 566                      region);
 567             }
 568         }
 569     }
 570
 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>) {
 577         match mt.mutbl {
 578             hir::MutMutable => {
 579                 let invar = self.invariant(variance);
 580                 self.add_constraints_from_ty(current, mt.ty, invar);
 581             }
 582
 583             hir::MutImmutable => {
 584                 self.add_constraints_from_ty(current, mt.ty, variance);
 585             }
 586         }
 587     }
 588 }