src/librustc_traits/dropck_outlives.rs

   1 use rustc::hir::def_id::DefId;
   2 use rustc::infer::canonical::{Canonical, QueryResponse};
   3 use rustc::traits::query::dropck_outlives::{DropckOutlivesResult, DtorckConstraint};
   4 use rustc::traits::query::{CanonicalTyGoal, NoSolution};
   5 use rustc::traits::{TraitEngine, Normalized, ObligationCause, TraitEngineExt};
   6 use rustc::ty::query::Providers;
   7 use rustc::ty::subst::{Subst, InternalSubsts};
   8 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt};
   9 use rustc::util::nodemap::FxHashSet;
  10 use syntax::source_map::{Span, DUMMY_SP};
  11
  12 crate fn provide(p: &mut Providers<'_>) {
  13     *p = Providers {
  14         dropck_outlives,
  15         adt_dtorck_constraint,
  16         ..*p
  17     };
  18 }
  19
  20 fn dropck_outlives<'tcx>(
  21     tcx: TyCtxt<'tcx>,
  22     canonical_goal: CanonicalTyGoal<'tcx>,
  23 ) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>, NoSolution> {
  24     debug!("dropck_outlives(goal={:#?})", canonical_goal);
  25
  26     tcx.infer_ctxt().enter_with_canonical(
  27         DUMMY_SP,
  28         &canonical_goal,
  29         |ref infcx, goal, canonical_inference_vars| {
  30             let tcx = infcx.tcx;
  31             let ParamEnvAnd {
  32                 param_env,
  33                 value: for_ty,
  34             } = goal;
  35
  36             let mut result = DropckOutlivesResult {
  37                 kinds: vec![],
  38                 overflows: vec![],
  39             };
  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 recursion, 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::default();
  79
  80             let mut fulfill_cx = TraitEngine::new(infcx.tcx);
  81
  82             let cause = ObligationCause::dummy();
  83             let mut constraints = DtorckConstraint::empty();
  84             while let Some((ty, depth)) = ty_stack.pop() {
  85                 info!("{} kinds, {} overflows, {} ty_stack",
  86                     result.kinds.len(), result.overflows.len(), ty_stack.len());
  87                 dtorck_constraint_for_ty(tcx, DUMMY_SP, for_ty, depth, ty, &mut constraints)?;
  88
  89                 // "outlives" represent types/regions that may be touched
  90                 // by a destructor.
  91                 result.kinds.extend(constraints.outlives.drain(..));
  92                 result.overflows.extend(constraints.overflows.drain(..));
  93
  94                 // If we have even one overflow, we should stop trying to evaluate further --
  95                 // chances are, the subsequent overflows for this evaluation won't provide useful
  96                 // information and will just decrease the speed at which we can emit these errors
  97                 // (since we'll be printing for just that much longer for the often enormous types
  98                 // that result here).
  99                 if result.overflows.len() >= 1 {
 100                     break;
 101                 }
 102
 103                 // dtorck types are "types that will get dropped but which
 104                 // do not themselves define a destructor", more or less. We have
 105                 // to push them onto the stack to be expanded.
 106                 for ty in constraints.dtorck_types.drain(..) {
 107                     match infcx.at(&cause, param_env).normalize(&ty) {
 108                         Ok(Normalized {
 109                             value: ty,
 110                             obligations,
 111                         }) => {
 112                             fulfill_cx.register_predicate_obligations(infcx, obligations);
 113
 114                             debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
 115
 116                             match ty.kind {
 117                                 // All parameters live for the duration of the
 118                                 // function.
 119                                 ty::Param(..) => {}
 120
 121                                 // A projection that we couldn't resolve - it
 122                                 // might have a destructor.
 123                                 ty::Projection(..) | ty::Opaque(..) => {
 124                                     result.kinds.push(ty.into());
 125                                 }
 126
 127                                 _ => {
 128                                     if ty_set.insert(ty) {
 129                                         ty_stack.push((ty, depth + 1));
 130                                     }
 131                                 }
 132                             }
 133                         }
 134
 135                         // We don't actually expect to fail to normalize.
 136                         // That implies a WF error somewhere else.
 137                         Err(NoSolution) => {
 138                             return Err(NoSolution);
 139                         }
 140                     }
 141                 }
 142             }
 143
 144             debug!("dropck_outlives: result = {:#?}", result);
 145
 146             infcx.make_canonicalized_query_response(
 147                 canonical_inference_vars,
 148                 result,
 149                 &mut *fulfill_cx
 150             )
 151         },
 152     )
 153 }
 154
 155 /// Returns a set of constraints that needs to be satisfied in
 156 /// order for `ty` to be valid for destruction.
 157 fn dtorck_constraint_for_ty<'tcx>(
 158     tcx: TyCtxt<'tcx>,
 159     span: Span,
 160     for_ty: Ty<'tcx>,
 161     depth: usize,
 162     ty: Ty<'tcx>,
 163     constraints: &mut DtorckConstraint<'tcx>,
 164 ) -> Result<(), NoSolution> {
 165     debug!(
 166         "dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})",
 167         span, for_ty, depth, ty
 168     );
 169
 170     if depth >= *tcx.sess.recursion_limit.get() {
 171         constraints.overflows.push(ty);
 172         return Ok(());
 173     }
 174
 175     if tcx.trivial_dropck_outlives(ty) {
 176         return Ok(());
 177     }
 178
 179     match ty.kind {
 180         ty::Bool
 181         | ty::Char
 182         | ty::Int(_)
 183         | ty::Uint(_)
 184         | ty::Float(_)
 185         | ty::Str
 186         | ty::Never
 187         | ty::Foreign(..)
 188         | ty::RawPtr(..)
 189         | ty::Ref(..)
 190         | ty::FnDef(..)
 191         | ty::FnPtr(_)
 192         | ty::GeneratorWitness(..) => {
 193             // these types never have a destructor
 194         }
 195
 196         ty::Array(ety, _) | ty::Slice(ety) => {
 197             // single-element containers, behave like their element
 198             dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ety, constraints)?;
 199         }
 200
 201         ty::Tuple(tys) => for ty in tys.iter() {
 202             dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty.expect_ty(), constraints)?;
 203         },
 204
 205         ty::Closure(def_id, substs) => for ty in substs.as_closure().upvar_tys(def_id, tcx) {
 206             dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty, constraints)?;
 207         }
 208
 209         ty::Generator(def_id, substs, _movability) => {
 210             // rust-lang/rust#49918: types can be constructed, stored
 211             // in the interior, and sit idle when generator yields
 212             // (and is subsequently dropped).
 213             //
 214             // It would be nice to descend into interior of a
 215             // generator to determine what effects dropping it might
 216             // have (by looking at any drop effects associated with
 217             // its interior).
 218             //
 219             // However, the interior's representation uses things like
 220             // GeneratorWitness that explicitly assume they are not
 221             // traversed in such a manner. So instead, we will
 222             // simplify things for now by treating all generators as
 223             // if they were like trait objects, where its upvars must
 224             // all be alive for the generator's (potential)
 225             // destructor.
 226             //
 227             // In particular, skipping over `_interior` is safe
 228             // because any side-effects from dropping `_interior` can
 229             // only take place through references with lifetimes
 230             // derived from lifetimes attached to the upvars, and we
 231             // *do* incorporate the upvars here.
 232
 233             constraints.outlives.extend(substs.as_generator().upvar_tys(def_id, tcx)
 234                 .map(|t| -> ty::subst::GenericArg<'tcx> { t.into() }));
 235         }
 236
 237         ty::Adt(def, substs) => {
 238             let DtorckConstraint {
 239                 dtorck_types,
 240                 outlives,
 241                 overflows,
 242             } = tcx.at(span).adt_dtorck_constraint(def.did)?;
 243             // FIXME: we can try to recursively `dtorck_constraint_on_ty`
 244             // there, but that needs some way to handle cycles.
 245             constraints.dtorck_types.extend(dtorck_types.subst(tcx, substs));
 246             constraints.outlives.extend(outlives.subst(tcx, substs));
 247             constraints.overflows.extend(overflows.subst(tcx, substs));
 248         }
 249
 250         // Objects must be alive in order for their destructor
 251         // to be called.
 252         ty::Dynamic(..) => {
 253             constraints.outlives.push(ty.into());
 254         },
 255
 256         // Types that can't be resolved. Pass them forward.
 257         ty::Projection(..) | ty::Opaque(..) | ty::Param(..) => {
 258             constraints.dtorck_types.push(ty);
 259         },
 260
 261         ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
 262
 263         ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error => {
 264             // By the time this code runs, all type variables ought to
 265             // be fully resolved.
 266             return Err(NoSolution)
 267         }
 268     }
 269
 270     Ok(())
 271 }
 272
 273 /// Calculates the dtorck constraint for a type.
 274 crate fn adt_dtorck_constraint(
 275     tcx: TyCtxt<'_>,
 276     def_id: DefId,
 277 ) -> Result<DtorckConstraint<'_>, NoSolution> {
 278     let def = tcx.adt_def(def_id);
 279     let span = tcx.def_span(def_id);
 280     debug!("dtorck_constraint: {:?}", def);
 281
 282     if def.is_phantom_data() {
 283         // The first generic parameter here is guaranteed to be a type because it's
 284         // `PhantomData`.
 285         let substs = InternalSubsts::identity_for_item(tcx, def_id);
 286         assert_eq!(substs.len(), 1);
 287         let result = DtorckConstraint {
 288             outlives: vec![],
 289             dtorck_types: vec![substs.type_at(0)],
 290             overflows: vec![],
 291         };
 292         debug!("dtorck_constraint: {:?} => {:?}", def, result);
 293         return Ok(result);
 294     }
 295
 296     let mut result = DtorckConstraint::empty();
 297     for field in def.all_fields() {
 298         let fty = tcx.type_of(field.did);
 299         dtorck_constraint_for_ty(tcx, span, fty, 0, fty, &mut result)?;
 300     }
 301     result.outlives.extend(tcx.destructor_constraints(def));
 302     dedup_dtorck_constraint(&mut result);
 303
 304     debug!("dtorck_constraint: {:?} => {:?}", def, result);
 305
 306     Ok(result)
 307 }
 308
 309 fn dedup_dtorck_constraint(c: &mut DtorckConstraint<'_>) {
 310     let mut outlives = FxHashSet::default();
 311     let mut dtorck_types = FxHashSet::default();
 312
 313     c.outlives.retain(|&val| outlives.replace(val).is_none());
 314     c.dtorck_types
 315         .retain(|&val| dtorck_types.replace(val).is_none());
 316 }