src/librustc/middle/implicator.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // #![warn(deprecated_mode)]
  12
  13 use middle::def_id::DefId;
  14 use middle::infer::{InferCtxt, GenericKind};
  15 use middle::subst::Substs;
  16 use middle::traits;
  17 use middle::ty::{self, ToPredicate, Ty};
  18 use middle::ty::fold::{TypeFoldable, TypeFolder};
  19
  20 use syntax::ast;
  21 use syntax::codemap::Span;
  22
  23 use util::common::ErrorReported;
  24 use util::nodemap::FnvHashSet;
  25
  26 // Helper functions related to manipulating region types.
  27
  28 #[derive(Debug)]
  29 pub enum Implication<'tcx> {
  30     RegionSubRegion(Option<Ty<'tcx>>, ty::Region, ty::Region),
  31     RegionSubGeneric(Option<Ty<'tcx>>, ty::Region, GenericKind<'tcx>),
  32     Predicate(DefId, ty::Predicate<'tcx>),
  33 }
  34
  35 struct Implicator<'a, 'tcx: 'a> {
  36     infcx: &'a InferCtxt<'a,'tcx>,
  37     body_id: ast::NodeId,
  38     stack: Vec<(ty::Region, Option<Ty<'tcx>>)>,
  39     span: Span,
  40     out: Vec<Implication<'tcx>>,
  41     visited: FnvHashSet<Ty<'tcx>>,
  42 }
  43
  44 /// This routine computes the well-formedness constraints that must hold for the type `ty` to
  45 /// appear in a context with lifetime `outer_region`
  46 pub fn implications<'a,'tcx>(
  47     infcx: &'a InferCtxt<'a,'tcx>,
  48     body_id: ast::NodeId,
  49     ty: Ty<'tcx>,
  50     outer_region: ty::Region,
  51     span: Span)
  52     -> Vec<Implication<'tcx>>
  53 {
  54     debug!("implications(body_id={}, ty={:?}, outer_region={:?})",
  55            body_id,
  56            ty,
  57            outer_region);
  58
  59     let mut stack = Vec::new();
  60     stack.push((outer_region, None));
  61     let mut wf = Implicator { infcx: infcx,
  62                               body_id: body_id,
  63                               span: span,
  64                               stack: stack,
  65                               out: Vec::new(),
  66                               visited: FnvHashSet() };
  67     wf.accumulate_from_ty(ty);
  68     debug!("implications: out={:?}", wf.out);
  69     wf.out
  70 }
  71
  72 impl<'a, 'tcx> Implicator<'a, 'tcx> {
  73     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
  74         self.infcx.tcx
  75     }
  76
  77     fn accumulate_from_ty(&mut self, ty: Ty<'tcx>) {
  78         debug!("accumulate_from_ty(ty={:?})",
  79                ty);
  80
  81         // When expanding out associated types, we can visit a cyclic
  82         // set of types. Issue #23003.
  83         if !self.visited.insert(ty) {
  84             return;
  85         }
  86
  87         match ty.sty {
  88             ty::TyBool |
  89             ty::TyChar |
  90             ty::TyInt(..) |
  91             ty::TyUint(..) |
  92             ty::TyFloat(..) |
  93             ty::TyBareFn(..) |
  94             ty::TyError |
  95             ty::TyStr => {
  96                 // No borrowed content reachable here.
  97             }
  98
  99             ty::TyClosure(_, ref substs) => {
 100                 // FIXME(#27086). We do not accumulate from substs, since they
 101                 // don't represent reachable data. This means that, in
 102                 // practice, some of the lifetime parameters might not
 103                 // be in scope when the body runs, so long as there is
 104                 // no reachable data with that lifetime. For better or
 105                 // worse, this is consistent with fn types, however,
 106                 // which can also encapsulate data in this fashion
 107                 // (though it's somewhat harder, and typically
 108                 // requires virtual dispatch).
 109                 //
 110                 // Note that changing this (in a naive way, at least)
 111                 // causes regressions for what appears to be perfectly
 112                 // reasonable code like this:
 113                 //
 114                 // ```
 115                 // fn foo<'a>(p: &Data<'a>) {
 116                 //    bar(|q: &mut Parser| q.read_addr())
 117                 // }
 118                 // fn bar(p: Box<FnMut(&mut Parser)+'static>) {
 119                 // }
 120                 // ```
 121                 //
 122                 // Note that `p` (and `'a`) are not used in the
 123                 // closure at all, but to meet the requirement that
 124                 // the closure type `C: 'static` (so it can be coerced
 125                 // to the object type), we get the requirement that
 126                 // `'a: 'static` since `'a` appears in the closure
 127                 // type `C`.
 128                 //
 129                 // A smarter fix might "prune" unused `func_substs` --
 130                 // this would avoid breaking simple examples like
 131                 // this, but would still break others (which might
 132                 // indeed be invalid, depending on your POV). Pruning
 133                 // would be a subtle process, since we have to see
 134                 // what func/type parameters are used and unused,
 135                 // taking into consideration UFCS and so forth.
 136
 137                 for &upvar_ty in &substs.upvar_tys {
 138                     self.accumulate_from_ty(upvar_ty);
 139                 }
 140             }
 141
 142             ty::TyTrait(ref t) => {
 143                 let required_region_bounds =
 144                     object_region_bounds(self.tcx(), &t.principal, t.bounds.builtin_bounds);
 145                 self.accumulate_from_object_ty(ty, t.bounds.region_bound, required_region_bounds)
 146             }
 147
 148             ty::TyEnum(def, substs) |
 149             ty::TyStruct(def, substs) => {
 150                 let item_scheme = def.type_scheme(self.tcx());
 151                 self.accumulate_from_adt(ty, def.did, &item_scheme.generics, substs)
 152             }
 153
 154             ty::TyArray(t, _) |
 155             ty::TySlice(t) |
 156             ty::TyRawPtr(ty::TypeAndMut { ty: t, .. }) |
 157             ty::TyBox(t) => {
 158                 self.accumulate_from_ty(t)
 159             }
 160
 161             ty::TyRef(r_b, mt) => {
 162                 self.accumulate_from_rptr(ty, *r_b, mt.ty);
 163             }
 164
 165             ty::TyParam(p) => {
 166                 self.push_param_constraint_from_top(p);
 167             }
 168
 169             ty::TyProjection(ref data) => {
 170                 // `<T as TraitRef<..>>::Name`
 171
 172                 self.push_projection_constraint_from_top(data);
 173             }
 174
 175             ty::TyTuple(ref tuptys) => {
 176                 for &tupty in tuptys {
 177                     self.accumulate_from_ty(tupty);
 178                 }
 179             }
 180
 181             ty::TyInfer(_) => {
 182                 // This should not happen, BUT:
 183                 //
 184                 //   Currently we uncover region relationships on
 185                 //   entering the fn check. We should do this after
 186                 //   the fn check, then we can call this case a bug().
 187             }
 188         }
 189     }
 190
 191     fn accumulate_from_rptr(&mut self,
 192                             ty: Ty<'tcx>,
 193                             r_b: ty::Region,
 194                             ty_b: Ty<'tcx>) {
 195         // We are walking down a type like this, and current
 196         // position is indicated by caret:
 197         //
 198         //     &'a &'b ty_b
 199         //         ^
 200         //
 201         // At this point, top of stack will be `'a`. We must
 202         // require that `'a <= 'b`.
 203
 204         self.push_region_constraint_from_top(r_b);
 205
 206         // Now we push `'b` onto the stack, because it must
 207         // constrain any borrowed content we find within `T`.
 208
 209         self.stack.push((r_b, Some(ty)));
 210         self.accumulate_from_ty(ty_b);
 211         self.stack.pop().unwrap();
 212     }
 213
 214     /// Pushes a constraint that `r_b` must outlive the top region on the stack.
 215     fn push_region_constraint_from_top(&mut self,
 216                                        r_b: ty::Region) {
 217
 218         // Indicates that we have found borrowed content with a lifetime
 219         // of at least `r_b`. This adds a constraint that `r_b` must
 220         // outlive the region `r_a` on top of the stack.
 221         //
 222         // As an example, imagine walking a type like:
 223         //
 224         //     &'a &'b T
 225         //         ^
 226         //
 227         // when we hit the inner pointer (indicated by caret), `'a` will
 228         // be on top of stack and `'b` will be the lifetime of the content
 229         // we just found. So we add constraint that `'a <= 'b`.
 230
 231         let &(r_a, opt_ty) = self.stack.last().unwrap();
 232         self.push_sub_region_constraint(opt_ty, r_a, r_b);
 233     }
 234
 235     /// Pushes a constraint that `r_a <= r_b`, due to `opt_ty`
 236     fn push_sub_region_constraint(&mut self,
 237                                   opt_ty: Option<Ty<'tcx>>,
 238                                   r_a: ty::Region,
 239                                   r_b: ty::Region) {
 240         self.out.push(Implication::RegionSubRegion(opt_ty, r_a, r_b));
 241     }
 242
 243     /// Pushes a constraint that `param_ty` must outlive the top region on the stack.
 244     fn push_param_constraint_from_top(&mut self,
 245                                       param_ty: ty::ParamTy) {
 246         let &(region, opt_ty) = self.stack.last().unwrap();
 247         self.push_param_constraint(region, opt_ty, param_ty);
 248     }
 249
 250     /// Pushes a constraint that `projection_ty` must outlive the top region on the stack.
 251     fn push_projection_constraint_from_top(&mut self,
 252                                            projection_ty: &ty::ProjectionTy<'tcx>) {
 253         let &(region, opt_ty) = self.stack.last().unwrap();
 254         self.out.push(Implication::RegionSubGeneric(
 255             opt_ty, region, GenericKind::Projection(projection_ty.clone())));
 256     }
 257
 258     /// Pushes a constraint that `region <= param_ty`, due to `opt_ty`
 259     fn push_param_constraint(&mut self,
 260                              region: ty::Region,
 261                              opt_ty: Option<Ty<'tcx>>,
 262                              param_ty: ty::ParamTy) {
 263         self.out.push(Implication::RegionSubGeneric(
 264             opt_ty, region, GenericKind::Param(param_ty)));
 265     }
 266
 267     fn accumulate_from_adt(&mut self,
 268                            ty: Ty<'tcx>,
 269                            def_id: DefId,
 270                            _generics: &ty::Generics<'tcx>,
 271                            substs: &Substs<'tcx>)
 272     {
 273         let predicates =
 274             self.tcx().lookup_predicates(def_id).instantiate(self.tcx(), substs);
 275         let predicates = match self.fully_normalize(&predicates) {
 276             Ok(predicates) => predicates,
 277             Err(ErrorReported) => { return; }
 278         };
 279
 280         for predicate in predicates.predicates.as_slice() {
 281             match *predicate {
 282                 ty::Predicate::Trait(..) => { }
 283                 ty::Predicate::Equate(..) => { }
 284                 ty::Predicate::Projection(..) => { }
 285                 ty::Predicate::RegionOutlives(ref data) => {
 286                     match self.tcx().no_late_bound_regions(data) {
 287                         None => { }
 288                         Some(ty::OutlivesPredicate(r_a, r_b)) => {
 289                             self.push_sub_region_constraint(Some(ty), r_b, r_a);
 290                         }
 291                     }
 292                 }
 293                 ty::Predicate::TypeOutlives(ref data) => {
 294                     match self.tcx().no_late_bound_regions(data) {
 295                         None => { }
 296                         Some(ty::OutlivesPredicate(ty_a, r_b)) => {
 297                             self.stack.push((r_b, Some(ty)));
 298                             self.accumulate_from_ty(ty_a);
 299                             self.stack.pop().unwrap();
 300                         }
 301                     }
 302                 }
 303                 ty::Predicate::ObjectSafe(_) |
 304                 ty::Predicate::WellFormed(_) => {
 305                 }
 306             }
 307         }
 308
 309         let obligations = predicates.predicates
 310                                     .into_iter()
 311                                     .map(|pred| Implication::Predicate(def_id, pred));
 312         self.out.extend(obligations);
 313
 314         let variances = self.tcx().item_variances(def_id);
 315         self.accumulate_from_substs(substs, Some(&variances));
 316     }
 317
 318     fn accumulate_from_substs(&mut self,
 319                               substs: &Substs<'tcx>,
 320                               variances: Option<&ty::ItemVariances>)
 321     {
 322         let mut tmp_variances = None;
 323         let variances = variances.unwrap_or_else(|| {
 324             tmp_variances = Some(ty::ItemVariances {
 325                 types: substs.types.map(|_| ty::Variance::Invariant),
 326                 regions: substs.regions().map(|_| ty::Variance::Invariant),
 327             });
 328             tmp_variances.as_ref().unwrap()
 329         });
 330
 331         for (&region, &variance) in substs.regions().iter().zip(&variances.regions) {
 332             match variance {
 333                 ty::Contravariant | ty::Invariant => {
 334                     // If any data with this lifetime is reachable
 335                     // within, it must be at least contravariant.
 336                     self.push_region_constraint_from_top(region)
 337                 }
 338                 ty::Covariant | ty::Bivariant => { }
 339             }
 340         }
 341
 342         for (&ty, &variance) in substs.types.iter().zip(&variances.types) {
 343             match variance {
 344                 ty::Covariant | ty::Invariant => {
 345                     // If any data of this type is reachable within,
 346                     // it must be at least covariant.
 347                     self.accumulate_from_ty(ty);
 348                 }
 349                 ty::Contravariant | ty::Bivariant => { }
 350             }
 351         }
 352     }
 353
 354     fn accumulate_from_object_ty(&mut self,
 355                                  ty: Ty<'tcx>,
 356                                  region_bound: ty::Region,
 357                                  required_region_bounds: Vec<ty::Region>)
 358     {
 359         // Imagine a type like this:
 360         //
 361         //     trait Foo { }
 362         //     trait Bar<'c> : 'c { }
 363         //
 364         //     &'b (Foo+'c+Bar<'d>)
 365         //         ^
 366         //
 367         // In this case, the following relationships must hold:
 368         //
 369         //     'b <= 'c
 370         //     'd <= 'c
 371         //
 372         // The first conditions is due to the normal region pointer
 373         // rules, which say that a reference cannot outlive its
 374         // referent.
 375         //
 376         // The final condition may be a bit surprising. In particular,
 377         // you may expect that it would have been `'c <= 'd`, since
 378         // usually lifetimes of outer things are conservative
 379         // approximations for inner things. However, it works somewhat
 380         // differently with trait objects: here the idea is that if the
 381         // user specifies a region bound (`'c`, in this case) it is the
 382         // "master bound" that *implies* that bounds from other traits are
 383         // all met. (Remember that *all bounds* in a type like
 384         // `Foo+Bar+Zed` must be met, not just one, hence if we write
 385         // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and
 386         // 'y.)
 387         //
 388         // Note: in fact we only permit builtin traits, not `Bar<'d>`, I
 389         // am looking forward to the future here.
 390
 391         // The content of this object type must outlive
 392         // `bounds.region_bound`:
 393         let r_c = region_bound;
 394         self.push_region_constraint_from_top(r_c);
 395
 396         // And then, in turn, to be well-formed, the
 397         // `region_bound` that user specified must imply the
 398         // region bounds required from all of the trait types:
 399         for &r_d in &required_region_bounds {
 400             // Each of these is an instance of the `'c <= 'b`
 401             // constraint above
 402             self.out.push(Implication::RegionSubRegion(Some(ty), r_d, r_c));
 403         }
 404     }
 405
 406     fn fully_normalize<T>(&self, value: &T) -> Result<T,ErrorReported>
 407         where T : TypeFoldable<'tcx>
 408     {
 409         let value =
 410             traits::fully_normalize(self.infcx,
 411                                     traits::ObligationCause::misc(self.span, self.body_id),
 412                                     value);
 413         match value {
 414             Ok(value) => Ok(value),
 415             Err(errors) => {
 416                 // I don't like reporting these errors here, but I
 417                 // don't know where else to report them just now. And
 418                 // I don't really expect errors to arise here
 419                 // frequently. I guess the best option would be to
 420                 // propagate them out.
 421                 traits::report_fulfillment_errors(self.infcx, &errors);
 422                 Err(ErrorReported)
 423             }
 424         }
 425     }
 426 }
 427
 428 /// Given an object type like `SomeTrait+Send`, computes the lifetime
 429 /// bounds that must hold on the elided self type. These are derived
 430 /// from the declarations of `SomeTrait`, `Send`, and friends -- if
 431 /// they declare `trait SomeTrait : 'static`, for example, then
 432 /// `'static` would appear in the list. The hard work is done by
 433 /// `ty::required_region_bounds`, see that for more information.
 434 pub fn object_region_bounds<'tcx>(
 435     tcx: &ty::ctxt<'tcx>,
 436     principal: &ty::PolyTraitRef<'tcx>,
 437     others: ty::BuiltinBounds)
 438     -> Vec<ty::Region>
 439 {
 440     // Since we don't actually *know* the self type for an object,
 441     // this "open(err)" serves as a kind of dummy standin -- basically
 442     // a skolemized type.
 443     let open_ty = tcx.mk_infer(ty::FreshTy(0));
 444
 445     // Note that we preserve the overall binding levels here.
 446     assert!(!open_ty.has_escaping_regions());
 447     let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty));
 448     let trait_refs = vec!(ty::Binder(ty::TraitRef::new(principal.0.def_id, substs)));
 449
 450     let mut predicates = others.to_predicates(tcx, open_ty);
 451     predicates.extend(trait_refs.iter().map(|t| t.to_predicate()));
 452
 453     tcx.required_region_bounds(open_ty, predicates)
 454 }