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