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 rustc::ty::subst::{Substs, UnpackedKind};
  18 use rustc::ty::{self, Ty, TyCtxt};
  19 use syntax::ast;
  20 use rustc::hir;
  21 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  22
  23 use super::terms::*;
  24 use super::terms::VarianceTerm::*;
  25
  26 pub struct ConstraintContext<'a, 'tcx: 'a> {
  27     pub terms_cx: TermsContext<'a, 'tcx>,
  28
  29     // These are pointers to common `ConstantTerm` instances
  30     covariant: VarianceTermPtr<'a>,
  31     contravariant: VarianceTermPtr<'a>,
  32     invariant: VarianceTermPtr<'a>,
  33     bivariant: VarianceTermPtr<'a>,
  34
  35     pub constraints: Vec<Constraint<'a>>,
  36 }
  37
  38 /// Declares that the variable `decl_id` appears in a location with
  39 /// variance `variance`.
  40 #[derive(Copy, Clone)]
  41 pub struct Constraint<'a> {
  42     pub inferred: InferredIndex,
  43     pub variance: &'a VarianceTerm<'a>,
  44 }
  45
  46 /// To build constraints, we visit one item (type, trait) at a time
  47 /// and look at its contents. So e.g. if we have
  48 ///
  49 ///     struct Foo<T> {
  50 ///         b: Bar<T>
  51 ///     }
  52 ///
  53 /// then while we are visiting `Bar<T>`, the `CurrentItem` would have
  54 /// the def-id and the start of `Foo`'s inferreds.
  55 pub struct CurrentItem {
  56     inferred_start: InferredIndex,
  57 }
  58
  59 pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>)
  60                                             -> ConstraintContext<'a, 'tcx> {
  61     let tcx = terms_cx.tcx;
  62     let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant));
  63     let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant));
  64     let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant));
  65     let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant));
  66     let mut constraint_cx = ConstraintContext {
  67         terms_cx,
  68         covariant,
  69         contravariant,
  70         invariant,
  71         bivariant,
  72         constraints: Vec::new(),
  73     };
  74
  75     tcx.hir.krate().visit_all_item_likes(&mut constraint_cx);
  76
  77     constraint_cx
  78 }
  79
  80 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
  81     fn visit_item(&mut self, item: &hir::Item) {
  82         match item.node {
  83             hir::ItemKind::Struct(ref struct_def, _) |
  84             hir::ItemKind::Union(ref struct_def, _) => {
  85                 self.visit_node_helper(item.id);
  86
  87                 if let hir::VariantData::Tuple(..) = *struct_def {
  88                     self.visit_node_helper(struct_def.id());
  89                 }
  90             }
  91
  92             hir::ItemKind::Enum(ref enum_def, _) => {
  93                 self.visit_node_helper(item.id);
  94
  95                 for variant in &enum_def.variants {
  96                     if let hir::VariantData::Tuple(..) = variant.node.data {
  97                         self.visit_node_helper(variant.node.data.id());
  98                     }
  99                 }
 100             }
 101
 102             hir::ItemKind::Fn(..) => {
 103                 self.visit_node_helper(item.id);
 104             }
 105
 106             hir::ItemKind::ForeignMod(ref foreign_mod) => {
 107                 for foreign_item in &foreign_mod.items {
 108                     if let hir::ForeignItemKind::Fn(..) = foreign_item.node {
 109                         self.visit_node_helper(foreign_item.id);
 110                     }
 111                 }
 112             }
 113
 114             _ => {}
 115         }
 116     }
 117
 118     fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) {
 119         if let hir::TraitItemKind::Method(..) = trait_item.node {
 120             self.visit_node_helper(trait_item.id);
 121         }
 122     }
 123
 124     fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) {
 125         if let hir::ImplItemKind::Method(..) = impl_item.node {
 126             self.visit_node_helper(impl_item.id);
 127         }
 128     }
 129 }
 130
 131 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 132     fn visit_node_helper(&mut self, id: ast::NodeId) {
 133         let tcx = self.terms_cx.tcx;
 134         let def_id = tcx.hir.local_def_id(id);
 135         self.build_constraints_for_item(def_id);
 136     }
 137
 138     fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
 139         self.terms_cx.tcx
 140     }
 141
 142     fn build_constraints_for_item(&mut self, def_id: DefId) {
 143         let tcx = self.tcx();
 144         debug!("build_constraints_for_item({})", tcx.item_path_str(def_id));
 145
 146         // Skip items with no generics - there's nothing to infer in them.
 147         if tcx.generics_of(def_id).count() == 0 {
 148             return;
 149         }
 150
 151         let id = tcx.hir.as_local_node_id(def_id).unwrap();
 152         let inferred_start = self.terms_cx.inferred_starts[&id];
 153         let current_item = &CurrentItem { inferred_start };
 154         match tcx.type_of(def_id).sty {
 155             ty::Adt(def, _) => {
 156                 // Not entirely obvious: constraints on structs/enums do not
 157                 // affect the variance of their type parameters. See discussion
 158                 // in comment at top of module.
 159                 //
 160                 // self.add_constraints_from_generics(generics);
 161
 162                 for field in def.all_fields() {
 163                     self.add_constraints_from_ty(current_item,
 164                                                  tcx.type_of(field.did),
 165                                                  self.covariant);
 166                 }
 167             }
 168
 169             ty::FnDef(..) => {
 170                 self.add_constraints_from_sig(current_item,
 171                                               tcx.fn_sig(def_id),
 172                                               self.covariant);
 173             }
 174
 175             _ => {
 176                 span_bug!(tcx.def_span(def_id),
 177                           "`build_constraints_for_item` unsupported for this item");
 178             }
 179         }
 180     }
 181
 182     fn add_constraint(&mut self,
 183                       current: &CurrentItem,
 184                       index: u32,
 185                       variance: VarianceTermPtr<'a>) {
 186         debug!("add_constraint(index={}, variance={:?})", index, variance);
 187         self.constraints.push(Constraint {
 188             inferred: InferredIndex(current.inferred_start.0 + index as usize),
 189             variance,
 190         });
 191     }
 192
 193     fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 194         self.xform(variance, self.contravariant)
 195     }
 196
 197     fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 198         self.xform(variance, self.invariant)
 199     }
 200
 201     fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
 202         match v {
 203             ty::Covariant => self.covariant,
 204             ty::Invariant => self.invariant,
 205             ty::Contravariant => self.contravariant,
 206             ty::Bivariant => self.bivariant,
 207         }
 208     }
 209
 210     fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 211         match (*v1, *v2) {
 212             (_, ConstantTerm(ty::Covariant)) => {
 213                 // Applying a "covariant" transform is always a no-op
 214                 v1
 215             }
 216
 217             (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
 218
 219             _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
 220         }
 221     }
 222
 223     fn add_constraints_from_trait_ref(&mut self,
 224                                       current: &CurrentItem,
 225                                       trait_ref: ty::TraitRef<'tcx>,
 226                                       variance: VarianceTermPtr<'a>) {
 227         debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
 228                trait_ref,
 229                variance);
 230         self.add_constraints_from_invariant_substs(current, trait_ref.substs, variance);
 231     }
 232
 233     fn add_constraints_from_invariant_substs(&mut self,
 234                                              current: &CurrentItem,
 235                                              substs: &Substs<'tcx>,
 236                                              variance: VarianceTermPtr<'a>) {
 237         debug!("add_constraints_from_invariant_substs: substs={:?} variance={:?}",
 238                substs,
 239                variance);
 240
 241         // Trait are always invariant so we can take advantage of that.
 242         let variance_i = self.invariant(variance);
 243         for ty in substs.types() {
 244             self.add_constraints_from_ty(current, ty, variance_i);
 245         }
 246
 247         for region in substs.regions() {
 248             self.add_constraints_from_region(current, region, variance_i);
 249         }
 250     }
 251
 252     /// Adds constraints appropriate for an instance of `ty` appearing
 253     /// in a context with the generics defined in `generics` and
 254     /// ambient variance `variance`
 255     fn add_constraints_from_ty(&mut self,
 256                                current: &CurrentItem,
 257                                ty: Ty<'tcx>,
 258                                variance: VarianceTermPtr<'a>) {
 259         debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
 260                ty,
 261                variance);
 262
 263         match ty.sty {
 264             ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) |
 265             ty::Str | ty::Never | ty::Foreign(..) => {
 266                 // leaf type -- noop
 267             }
 268
 269             ty::FnDef(..) |
 270             ty::Generator(..) |
 271             ty::Closure(..) => {
 272                 bug!("Unexpected closure type in variance computation");
 273             }
 274
 275             ty::Ref(region, ty, mutbl) => {
 276                 let contra = self.contravariant(variance);
 277                 self.add_constraints_from_region(current, region, contra);
 278                 self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance);
 279             }
 280
 281             ty::Array(typ, _) |
 282             ty::Slice(typ) => {
 283                 self.add_constraints_from_ty(current, typ, variance);
 284             }
 285
 286             ty::RawPtr(ref mt) => {
 287                 self.add_constraints_from_mt(current, mt, variance);
 288             }
 289
 290             ty::Tuple(subtys) => {
 291                 for &subty in subtys {
 292                     self.add_constraints_from_ty(current, subty, variance);
 293                 }
 294             }
 295
 296             ty::Adt(def, substs) => {
 297                 self.add_constraints_from_substs(current, def.did, substs, variance);
 298             }
 299
 300             ty::Projection(ref data) => {
 301                 let tcx = self.tcx();
 302                 self.add_constraints_from_trait_ref(current, data.trait_ref(tcx), variance);
 303             }
 304
 305             ty::Opaque(_, substs) => {
 306                 self.add_constraints_from_invariant_substs(current, substs, variance);
 307             }
 308
 309             ty::Dynamic(ref data, r) => {
 310                 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
 311                 let contra = self.contravariant(variance);
 312                 self.add_constraints_from_region(current, r, contra);
 313
 314                 let poly_trait_ref = data
 315                     .principal()
 316                     .with_self_ty(self.tcx(), self.tcx().types.err);
 317                 self.add_constraints_from_trait_ref(
 318                     current, *poly_trait_ref.skip_binder(), variance);
 319
 320                 for projection in data.projection_bounds() {
 321                     self.add_constraints_from_ty(
 322                         current, projection.skip_binder().ty, self.invariant);
 323                 }
 324             }
 325
 326             ty::Param(ref data) => {
 327                 self.add_constraint(current, data.idx, variance);
 328             }
 329
 330             ty::FnPtr(sig) => {
 331                 self.add_constraints_from_sig(current, sig, variance);
 332             }
 333
 334             ty::Error => {
 335                 // we encounter this when walking the trait references for object
 336                 // types, where we use Error as the Self type
 337             }
 338
 339             ty::UnnormalizedProjection(..) |
 340             ty::GeneratorWitness(..) |
 341             ty::Bound(..) |
 342             ty::Infer(..) => {
 343                 bug!("unexpected type encountered in \
 344                       variance inference: {}",
 345                      ty);
 346             }
 347         }
 348     }
 349
 350     /// Adds constraints appropriate for a nominal type (enum, struct,
 351     /// object, etc) appearing in a context with ambient variance `variance`
 352     fn add_constraints_from_substs(&mut self,
 353                                    current: &CurrentItem,
 354                                    def_id: DefId,
 355                                    substs: &Substs<'tcx>,
 356                                    variance: VarianceTermPtr<'a>) {
 357         debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
 358                def_id,
 359                substs,
 360                variance);
 361
 362         // We don't record `inferred_starts` entries for empty generics.
 363         if substs.is_empty() {
 364             return;
 365         }
 366
 367         let (local, remote) = if let Some(id) = self.tcx().hir.as_local_node_id(def_id) {
 368             (Some(self.terms_cx.inferred_starts[&id]), None)
 369         } else {
 370             (None, Some(self.tcx().variances_of(def_id)))
 371         };
 372
 373         for (i, k) in substs.iter().enumerate() {
 374             let variance_decl = if let Some(InferredIndex(start)) = local {
 375                 // Parameter on an item defined within current crate:
 376                 // variance not yet inferred, so return a symbolic
 377                 // variance.
 378                 self.terms_cx.inferred_terms[start + i]
 379             } else {
 380                 // Parameter on an item defined within another crate:
 381                 // variance already inferred, just look it up.
 382                 self.constant_term(remote.as_ref().unwrap()[i])
 383             };
 384             let variance_i = self.xform(variance, variance_decl);
 385             debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
 386                    variance_decl,
 387                    variance_i);
 388             match k.unpack() {
 389                 UnpackedKind::Lifetime(lt) => {
 390                     self.add_constraints_from_region(current, lt, variance_i)
 391                 }
 392                 UnpackedKind::Type(ty) => {
 393                     self.add_constraints_from_ty(current, ty, variance_i)
 394                 }
 395             }
 396         }
 397     }
 398
 399     /// Adds constraints appropriate for a function with signature
 400     /// `sig` appearing in a context with ambient variance `variance`
 401     fn add_constraints_from_sig(&mut self,
 402                                 current: &CurrentItem,
 403                                 sig: ty::PolyFnSig<'tcx>,
 404                                 variance: VarianceTermPtr<'a>) {
 405         let contra = self.contravariant(variance);
 406         for &input in sig.skip_binder().inputs() {
 407             self.add_constraints_from_ty(current, input, contra);
 408         }
 409         self.add_constraints_from_ty(current, sig.skip_binder().output(), variance);
 410     }
 411
 412     /// Adds constraints appropriate for a region appearing in a
 413     /// context with ambient variance `variance`
 414     fn add_constraints_from_region(&mut self,
 415                                    current: &CurrentItem,
 416                                    region: ty::Region<'tcx>,
 417                                    variance: VarianceTermPtr<'a>) {
 418         match *region {
 419             ty::ReEarlyBound(ref data) => {
 420                 self.add_constraint(current, data.index, variance);
 421             }
 422
 423             ty::ReStatic => {}
 424
 425             ty::ReLateBound(..) => {
 426                 // Late-bound regions do not get substituted the same
 427                 // way early-bound regions do, so we skip them here.
 428             }
 429
 430             ty::ReFree(..) |
 431             ty::ReClosureBound(..) |
 432             ty::ReScope(..) |
 433             ty::ReVar(..) |
 434             ty::RePlaceholder(..) |
 435             ty::ReEmpty |
 436             ty::ReErased => {
 437                 // We don't expect to see anything but 'static or bound
 438                 // regions when visiting member types or method types.
 439                 bug!("unexpected region encountered in variance \
 440                       inference: {:?}",
 441                      region);
 442             }
 443         }
 444     }
 445
 446     /// Adds constraints appropriate for a mutability-type pair
 447     /// appearing in a context with ambient variance `variance`
 448     fn add_constraints_from_mt(&mut self,
 449                                current: &CurrentItem,
 450                                mt: &ty::TypeAndMut<'tcx>,
 451                                variance: VarianceTermPtr<'a>) {
 452         match mt.mutbl {
 453             hir::MutMutable => {
 454                 let invar = self.invariant(variance);
 455                 self.add_constraints_from_ty(current, mt.ty, invar);
 456             }
 457
 458             hir::MutImmutable => {
 459                 self.add_constraints_from_ty(current, mt.ty, variance);
 460             }
 461         }
 462     }
 463 }