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