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