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