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::{SubstsRef, GenericArgKind};
   8 use rustc::ty::{self, Ty, TyCtxt};
   9 use rustc::hir;
  10 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  11
  12 use super::terms::*;
  13 use super::terms::VarianceTerm::*;
  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>(terms_cx: TermsContext<'a, 'tcx>)
  49                                             -> ConstraintContext<'a, 'tcx> {
  50     let tcx = terms_cx.tcx;
  51     let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant));
  52     let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant));
  53     let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant));
  54     let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant));
  55     let mut constraint_cx = ConstraintContext {
  56         terms_cx,
  57         covariant,
  58         contravariant,
  59         invariant,
  60         bivariant,
  61         constraints: Vec::new(),
  62     };
  63
  64     tcx.hir().krate().visit_all_item_likes(&mut constraint_cx);
  65
  66     constraint_cx
  67 }
  68
  69 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
  70     fn visit_item(&mut self, item: &hir::Item) {
  71         match item.kind {
  72             hir::ItemKind::Struct(ref struct_def, _) |
  73             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(current_item,
 153                                                  tcx.type_of(field.did),
 154                                                  self.covariant);
 155                 }
 156             }
 157
 158             ty::FnDef(..) => {
 159                 self.add_constraints_from_sig(current_item,
 160                                               tcx.fn_sig(def_id),
 161                                               self.covariant);
 162             }
 163
 164             _ => {
 165                 span_bug!(tcx.def_span(def_id),
 166                           "`build_constraints_for_item` unsupported for this item");
 167             }
 168         }
 169     }
 170
 171     fn add_constraint(&mut self,
 172                       current: &CurrentItem,
 173                       index: u32,
 174                       variance: VarianceTermPtr<'a>) {
 175         debug!("add_constraint(index={}, variance={:?})", index, variance);
 176         self.constraints.push(Constraint {
 177             inferred: InferredIndex(current.inferred_start.0 + index as usize),
 178             variance,
 179         });
 180     }
 181
 182     fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 183         self.xform(variance, self.contravariant)
 184     }
 185
 186     fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 187         self.xform(variance, self.invariant)
 188     }
 189
 190     fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
 191         match v {
 192             ty::Covariant => self.covariant,
 193             ty::Invariant => self.invariant,
 194             ty::Contravariant => self.contravariant,
 195             ty::Bivariant => self.bivariant,
 196         }
 197     }
 198
 199     fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> {
 200         match (*v1, *v2) {
 201             (_, ConstantTerm(ty::Covariant)) => {
 202                 // Applying a "covariant" transform is always a no-op
 203                 v1
 204             }
 205
 206             (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)),
 207
 208             _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)),
 209         }
 210     }
 211
 212     fn add_constraints_from_trait_ref(&mut self,
 213                                       current: &CurrentItem,
 214                                       trait_ref: ty::TraitRef<'tcx>,
 215                                       variance: VarianceTermPtr<'a>) {
 216         debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
 217                trait_ref,
 218                variance);
 219         self.add_constraints_from_invariant_substs(current, trait_ref.substs, variance);
 220     }
 221
 222     fn add_constraints_from_invariant_substs(&mut self,
 223                                              current: &CurrentItem,
 224                                              substs: SubstsRef<'tcx>,
 225                                              variance: VarianceTermPtr<'a>) {
 226         debug!("add_constraints_from_invariant_substs: substs={:?} variance={:?}",
 227                substs,
 228                variance);
 229
 230         // Trait are always invariant so we can take advantage of that.
 231         let variance_i = self.invariant(variance);
 232
 233         for k in substs {
 234             match k.unpack() {
 235                 GenericArgKind::Lifetime(lt) => {
 236                     self.add_constraints_from_region(current, lt, variance_i)
 237                 }
 238                 GenericArgKind::Type(ty) => {
 239                     self.add_constraints_from_ty(current, ty, variance_i)
 240                 }
 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(&mut self,
 252                                current: &CurrentItem,
 253                                ty: Ty<'tcx>,
 254                                variance: VarianceTermPtr<'a>) {
 255         debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
 256                ty,
 257                variance);
 258
 259         match ty.kind {
 260             ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) |
 261             ty::Str | ty::Never | ty::Foreign(..) => {
 262                 // leaf type -- noop
 263             }
 264
 265             ty::FnDef(..) |
 266             ty::Generator(..) |
 267             ty::Closure(..) => {
 268                 bug!("Unexpected closure type in variance computation");
 269             }
 270
 271             ty::Ref(region, ty, mutbl) => {
 272                 let contra = self.contravariant(variance);
 273                 self.add_constraints_from_region(current, region, contra);
 274                 self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance);
 275             }
 276
 277             ty::Array(typ, _) => {
 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.expect_ty(), 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                 let tcx = self.tcx();
 301                 self.add_constraints_from_trait_ref(current, data.trait_ref(tcx), variance);
 302             }
 303
 304             ty::Opaque(_, substs) => {
 305                 self.add_constraints_from_invariant_substs(current, substs, variance);
 306             }
 307
 308             ty::Dynamic(ref data, r) => {
 309                 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
 310                 let contra = self.contravariant(variance);
 311                 self.add_constraints_from_region(current, r, contra);
 312
 313                 if let Some(poly_trait_ref) = data.principal() {
 314                     let poly_trait_ref =
 315                         poly_trait_ref.with_self_ty(self.tcx(), self.tcx().types.err);
 316                     self.add_constraints_from_trait_ref(
 317                         current, *poly_trait_ref.skip_binder(), variance);
 318                 }
 319
 320                 for projection in data.projection_bounds() {
 321                     self.add_constraints_from_ty(
 322                         current, projection.skip_binder().ty, self.invariant);
 323                 }
 324             }
 325
 326             ty::Param(ref data) => {
 327                 self.add_constraint(current, data.index, variance);
 328             }
 329
 330             ty::FnPtr(sig) => {
 331                 self.add_constraints_from_sig(current, sig, variance);
 332             }
 333
 334             ty::Error => {
 335                 // we encounter this when walking the trait references for object
 336                 // types, where we use Error as the Self type
 337             }
 338
 339             ty::Placeholder(..) |
 340             ty::UnnormalizedProjection(..) |
 341             ty::GeneratorWitness(..) |
 342             ty::Bound(..) |
 343             ty::Infer(..) => {
 344                 bug!("unexpected type encountered in \
 345                       variance inference: {}",
 346                      ty);
 347             }
 348         }
 349     }
 350
 351     /// Adds constraints appropriate for a nominal type (enum, struct,
 352     /// object, etc) appearing in a context with ambient variance `variance`
 353     fn add_constraints_from_substs(&mut self,
 354                                    current: &CurrentItem,
 355                                    def_id: DefId,
 356                                    substs: SubstsRef<'tcx>,
 357                                    variance: VarianceTermPtr<'a>) {
 358         debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
 359                def_id,
 360                substs,
 361                variance);
 362
 363         // We don't record `inferred_starts` entries for empty generics.
 364         if substs.is_empty() {
 365             return;
 366         }
 367
 368         let (local, remote) = if let Some(id) = self.tcx().hir().as_local_hir_id(def_id) {
 369             (Some(self.terms_cx.inferred_starts[&id]), None)
 370         } else {
 371             (None, Some(self.tcx().variances_of(def_id)))
 372         };
 373
 374         for (i, k) in substs.iter().enumerate() {
 375             let variance_decl = if let Some(InferredIndex(start)) = local {
 376                 // Parameter on an item defined within current crate:
 377                 // variance not yet inferred, so return a symbolic
 378                 // variance.
 379                 self.terms_cx.inferred_terms[start + i]
 380             } else {
 381                 // Parameter on an item defined within another crate:
 382                 // variance already inferred, just look it up.
 383                 self.constant_term(remote.as_ref().unwrap()[i])
 384             };
 385             let variance_i = self.xform(variance, variance_decl);
 386             debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
 387                    variance_decl,
 388                    variance_i);
 389             match k.unpack() {
 390                 GenericArgKind::Lifetime(lt) => {
 391                     self.add_constraints_from_region(current, lt, variance_i)
 392                 }
 393                 GenericArgKind::Type(ty) => {
 394                     self.add_constraints_from_ty(current, ty, variance_i)
 395                 }
 396                 GenericArgKind::Const(_) => {
 397                     // Consts impose no constraints.
 398                 }
 399             }
 400         }
 401     }
 402
 403     /// Adds constraints appropriate for a function with signature
 404     /// `sig` appearing in a context with ambient variance `variance`
 405     fn add_constraints_from_sig(&mut self,
 406                                 current: &CurrentItem,
 407                                 sig: ty::PolyFnSig<'tcx>,
 408                                 variance: VarianceTermPtr<'a>) {
 409         let contra = self.contravariant(variance);
 410         for &input in sig.skip_binder().inputs() {
 411             self.add_constraints_from_ty(current, input, contra);
 412         }
 413         self.add_constraints_from_ty(current, sig.skip_binder().output(), variance);
 414     }
 415
 416     /// Adds constraints appropriate for a region appearing in a
 417     /// context with ambient variance `variance`
 418     fn add_constraints_from_region(&mut self,
 419                                    current: &CurrentItem,
 420                                    region: ty::Region<'tcx>,
 421                                    variance: VarianceTermPtr<'a>) {
 422         match *region {
 423             ty::ReEarlyBound(ref data) => {
 424                 self.add_constraint(current, data.index, variance);
 425             }
 426
 427             ty::ReStatic => {}
 428
 429             ty::ReLateBound(..) => {
 430                 // Late-bound regions do not get substituted the same
 431                 // way early-bound regions do, so we skip them here.
 432             }
 433
 434             ty::ReFree(..) |
 435             ty::ReClosureBound(..) |
 436             ty::ReScope(..) |
 437             ty::ReVar(..) |
 438             ty::RePlaceholder(..) |
 439             ty::ReEmpty |
 440             ty::ReErased => {
 441                 // We don't expect to see anything but 'static or bound
 442                 // regions when visiting member types or method types.
 443                 bug!("unexpected region encountered in variance \
 444                       inference: {:?}",
 445                      region);
 446             }
 447         }
 448     }
 449
 450     /// Adds constraints appropriate for a mutability-type pair
 451     /// appearing in a context with ambient variance `variance`
 452     fn add_constraints_from_mt(&mut self,
 453                                current: &CurrentItem,
 454                                mt: &ty::TypeAndMut<'tcx>,
 455                                variance: VarianceTermPtr<'a>) {
 456         match mt.mutbl {
 457             hir::Mutability::Mutable => {
 458                 let invar = self.invariant(variance);
 459                 self.add_constraints_from_ty(current, mt.ty, invar);
 460             }
 461
 462             hir::Mutability::Immutable => {
 463                 self.add_constraints_from_ty(current, mt.ty, variance);
 464             }
 465         }
 466     }
 467 }