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