src/librustc_traits/dropck_outlives.rs

   1 // Copyright 2014 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 use rustc::infer::canonical::{Canonical, QueryResult};
  12 use rustc::hir::def_id::DefId;
  13 use rustc::traits::{FulfillmentContext, Normalized, ObligationCause};
  14 use rustc::traits::query::{CanonicalTyGoal, NoSolution};
  15 use rustc::traits::query::dropck_outlives::{DtorckConstraint, DropckOutlivesResult};
  16 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt};
  17 use rustc::ty::subst::Subst;
  18 use rustc::util::nodemap::FxHashSet;
  19 use std::rc::Rc;
  20 use syntax::codemap::{Span, DUMMY_SP};
  21 use util;
  22
  23 crate fn dropck_outlives<'tcx>(
  24     tcx: TyCtxt<'_, 'tcx, 'tcx>,
  25     goal: CanonicalTyGoal<'tcx>,
  26 ) -> Result<Rc<Canonical<'tcx, QueryResult<'tcx, DropckOutlivesResult<'tcx>>>>, NoSolution> {
  27     debug!("dropck_outlives(goal={:#?})", goal);
  28
  29     tcx.infer_ctxt().enter(|ref infcx| {
  30         let tcx = infcx.tcx;
  31         let (
  32             ParamEnvAnd {
  33                 param_env,
  34                 value: for_ty,
  35             },
  36             canonical_inference_vars,
  37         ) = infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &goal);
  38
  39         let mut result = DropckOutlivesResult { kinds: vec![], overflows: vec![] };
  40
  41         // A stack of types left to process. Each round, we pop
  42         // something from the stack and invoke
  43         // `dtorck_constraint_for_ty`. This may produce new types that
  44         // have to be pushed on the stack. This continues until we have explored
  45         // all the reachable types from the type `for_ty`.
  46         //
  47         // Example: Imagine that we have the following code:
  48         //
  49         // ```rust
  50         // struct A {
  51         //     value: B,
  52         //     children: Vec<A>,
  53         // }
  54         //
  55         // struct B {
  56         //     value: u32
  57         // }
  58         //
  59         // fn f() {
  60         //   let a: A = ...;
  61         //   ..
  62         // } // here, `a` is dropped
  63         // ```
  64         //
  65         // at the point where `a` is dropped, we need to figure out
  66         // which types inside of `a` contain region data that may be
  67         // accessed by any destructors in `a`. We begin by pushing `A`
  68         // onto the stack, as that is the type of `a`. We will then
  69         // invoke `dtorck_constraint_for_ty` which will expand `A`
  70         // into the types of its fields `(B, Vec<A>)`. These will get
  71         // pushed onto the stack. Eventually, expanding `Vec<A>` will
  72         // lead to us trying to push `A` a second time -- to prevent
  73         // infinite recusion, we notice that `A` was already pushed
  74         // once and stop.
  75         let mut ty_stack = vec![(for_ty, 0)];
  76
  77         // Set used to detect infinite recursion.
  78         let mut ty_set = FxHashSet();
  79
  80         let fulfill_cx = &mut FulfillmentContext::new();
  81
  82         let cause = ObligationCause::dummy();
  83         while let Some((ty, depth)) = ty_stack.pop() {
  84             let DtorckConstraint {
  85                 dtorck_types,
  86                 outlives,
  87                 overflows,
  88             } = dtorck_constraint_for_ty(tcx, DUMMY_SP, for_ty, depth, ty)?;
  89
  90             // "outlives" represent types/regions that may be touched
  91             // by a destructor.
  92             result.kinds.extend(outlives);
  93             result.overflows.extend(overflows);
  94
  95             // dtorck types are "types that will get dropped but which
  96             // do not themselves define a destructor", more or less. We have
  97             // to push them onto the stack to be expanded.
  98             for ty in dtorck_types {
  99                 match infcx.at(&cause, param_env).normalize(&ty) {
 100                     Ok(Normalized {
 101                         value: ty,
 102                         obligations,
 103                     }) => {
 104                         fulfill_cx.register_predicate_obligations(infcx, obligations);
 105
 106                         debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
 107
 108                         match ty.sty {
 109                             // All parameters live for the duration of the
 110                             // function.
 111                             ty::TyParam(..) => {}
 112
 113                             // A projection that we couldn't resolve - it
 114                             // might have a destructor.
 115                             ty::TyProjection(..) | ty::TyAnon(..) => {
 116                                 result.kinds.push(ty.into());
 117                             }
 118
 119                             _ => {
 120                                 if ty_set.insert(ty) {
 121                                     ty_stack.push((ty, depth + 1));
 122                                 }
 123                             }
 124                         }
 125                     }
 126
 127                     // We don't actually expect to fail to normalize.
 128                     // That implies a WF error somewhere else.
 129                     Err(NoSolution) => {
 130                         return Err(NoSolution);
 131                     }
 132                 }
 133             }
 134         }
 135
 136         debug!("dropck_outlives: result = {:#?}", result);
 137
 138         util::make_query_response(infcx, canonical_inference_vars, result, fulfill_cx)
 139     })
 140 }
 141
 142 /// Return a set of constraints that needs to be satisfied in
 143 /// order for `ty` to be valid for destruction.
 144 fn dtorck_constraint_for_ty<'a, 'gcx, 'tcx>(
 145     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 146     span: Span,
 147     for_ty: Ty<'tcx>,
 148     depth: usize,
 149     ty: Ty<'tcx>,
 150 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
 151     debug!(
 152         "dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})",
 153         span, for_ty, depth, ty
 154     );
 155
 156     if depth >= tcx.sess.recursion_limit.get() {
 157         return Ok(DtorckConstraint {
 158             outlives: vec![],
 159             dtorck_types: vec![],
 160             overflows: vec![ty],
 161         });
 162     }
 163
 164     let result = match ty.sty {
 165         ty::TyBool
 166         | ty::TyChar
 167         | ty::TyInt(_)
 168         | ty::TyUint(_)
 169         | ty::TyFloat(_)
 170         | ty::TyStr
 171         | ty::TyNever
 172         | ty::TyForeign(..)
 173         | ty::TyRawPtr(..)
 174         | ty::TyRef(..)
 175         | ty::TyFnDef(..)
 176         | ty::TyFnPtr(_)
 177         | ty::TyGeneratorWitness(..) => {
 178             // these types never have a destructor
 179             Ok(DtorckConstraint::empty())
 180         }
 181
 182         ty::TyArray(ety, _) | ty::TySlice(ety) => {
 183             // single-element containers, behave like their element
 184             dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ety)
 185         }
 186
 187         ty::TyTuple(tys) => tys.iter()
 188             .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
 189             .collect(),
 190
 191         ty::TyClosure(def_id, substs) => substs
 192             .upvar_tys(def_id, tcx)
 193             .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
 194             .collect(),
 195
 196         ty::TyGenerator(def_id, substs, _) => {
 197             // Note that the interior types are ignored here.
 198             // Any type reachable inside the interior must also be reachable
 199             // through the upvars.
 200             substs
 201                 .upvar_tys(def_id, tcx)
 202                 .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
 203                 .collect()
 204         }
 205
 206         ty::TyAdt(def, substs) => {
 207             let DtorckConstraint {
 208                 dtorck_types,
 209                 outlives,
 210                 overflows,
 211             } = tcx.at(span).adt_dtorck_constraint(def.did)?;
 212             Ok(DtorckConstraint {
 213                 // FIXME: we can try to recursively `dtorck_constraint_on_ty`
 214                 // there, but that needs some way to handle cycles.
 215                 dtorck_types: dtorck_types.subst(tcx, substs),
 216                 outlives: outlives.subst(tcx, substs),
 217                 overflows: overflows.subst(tcx, substs),
 218             })
 219         }
 220
 221         // Objects must be alive in order for their destructor
 222         // to be called.
 223         ty::TyDynamic(..) => Ok(DtorckConstraint {
 224             outlives: vec![ty.into()],
 225             dtorck_types: vec![],
 226             overflows: vec![],
 227         }),
 228
 229         // Types that can't be resolved. Pass them forward.
 230         ty::TyProjection(..) | ty::TyAnon(..) | ty::TyParam(..) => Ok(DtorckConstraint {
 231             outlives: vec![],
 232             dtorck_types: vec![ty],
 233             overflows: vec![],
 234         }),
 235
 236         ty::TyInfer(..) | ty::TyError => {
 237             // By the time this code runs, all type variables ought to
 238             // be fully resolved.
 239             Err(NoSolution)
 240         }
 241     };
 242
 243     debug!("dtorck_constraint_for_ty({:?}) = {:?}", ty, result);
 244     result
 245 }
 246
 247 /// Calculates the dtorck constraint for a type.
 248 crate fn adt_dtorck_constraint<'a, 'tcx>(
 249     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 250     def_id: DefId,
 251 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
 252     let def = tcx.adt_def(def_id);
 253     let span = tcx.def_span(def_id);
 254     debug!("dtorck_constraint: {:?}", def);
 255
 256     if def.is_phantom_data() {
 257         let result = DtorckConstraint {
 258             outlives: vec![],
 259             dtorck_types: vec![tcx.mk_param_from_def(&tcx.generics_of(def_id).types[0])],
 260             overflows: vec![],
 261         };
 262         debug!("dtorck_constraint: {:?} => {:?}", def, result);
 263         return Ok(result);
 264     }
 265
 266     let mut result = def.all_fields()
 267         .map(|field| tcx.type_of(field.did))
 268         .map(|fty| dtorck_constraint_for_ty(tcx, span, fty, 0, fty))
 269         .collect::<Result<DtorckConstraint, NoSolution>>()?;
 270     result.outlives.extend(tcx.destructor_constraints(def));
 271     dedup_dtorck_constraint(&mut result);
 272
 273     debug!("dtorck_constraint: {:?} => {:?}", def, result);
 274
 275     Ok(result)
 276 }
 277
 278 fn dedup_dtorck_constraint<'tcx>(c: &mut DtorckConstraint<'tcx>) {
 279     let mut outlives = FxHashSet();
 280     let mut dtorck_types = FxHashSet();
 281
 282     c.outlives.retain(|&val| outlives.replace(val).is_none());
 283     c.dtorck_types
 284         .retain(|&val| dtorck_types.replace(val).is_none());
 285 }