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