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