src/librustc_typeck/variance/constraints.rs

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