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