compiler/rustc_traits/src/dropck_outlives.rs

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