src/librustc_traits/dropck_outlives.rs

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