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,
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};
18 pub(crate) fn provide(p: &mut Providers) {
19 *p = Providers { dropck_outlives, adt_dtorck_constraint, ..*p };
22 fn dropck_outlives<'tcx>(
24 canonical_goal: CanonicalTyGoal<'tcx>,
25 ) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>, NoSolution> {
26 debug!("dropck_outlives(goal={:#?})", canonical_goal);
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;
32 let mut result = DropckOutlivesResult { kinds: vec![], overflows: vec![] };
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`.
40 // Example: Imagine that we have the following code:
55 // } // here, `a` is dropped
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
68 let mut ty_stack = vec![(for_ty, 0)];
70 // Set used to detect infinite recursion.
71 let mut ty_set = FxHashSet::default();
73 let cause = ObligationCause::dummy();
74 let mut constraints = DropckConstraint::empty();
75 while let Some((ty, depth)) = ty_stack.pop() {
77 "{} kinds, {} overflows, {} ty_stack",
79 result.overflows.len(),
82 dtorck_constraint_for_ty(tcx, DUMMY_SP, for_ty, depth, ty, &mut constraints)?;
84 // "outlives" represent types/regions that may be touched
86 result.kinds.append(&mut constraints.outlives);
87 result.overflows.append(&mut constraints.overflows);
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
94 if !result.overflows.is_empty() {
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);
106 debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
109 // All parameters live for the duration of the
113 // A projection that we couldn't resolve - it
114 // might have a destructor.
115 ty::Alias(ty::Projection, ..) | ty::Alias(ty::Opaque, ..) => {
116 result.kinds.push(ty.into());
120 if ty_set.insert(ty) {
121 ty_stack.push((ty, depth + 1));
128 debug!("dropck_outlives: result = {:#?}", result);
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>(
141 constraints: &mut DropckConstraint<'tcx>,
142 ) -> Result<(), NoSolution> {
143 debug!("dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})", span, for_ty, depth, ty);
145 if !tcx.recursion_limit().value_within_limit(depth) {
146 constraints.overflows.push(ty);
150 if trivial_dropck_outlives(tcx, ty) {
167 | ty::GeneratorWitness(..) => {
168 // these types never have a destructor
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)
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)?;
182 Ok::<_, NoSolution>(())
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.
190 tcx.sess.delay_span_bug(
192 &format!("upvar_tys for closure not found. Expected capture information for closure {}", ty,),
194 return Err(NoSolution);
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)?;
201 Ok::<_, NoSolution>(())
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).
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
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)
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.
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(
234 &format!("upvar_tys for generator not found. Expected capture information for generator {}", ty,),
236 return Err(NoSolution);
239 constraints.outlives.extend(
243 .map(|t| -> ty::subst::GenericArg<'tcx> { t.into() }),
245 constraints.outlives.push(substs.as_generator().resume_ty().into());
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.
255 .extend(dtorck_types.iter().map(|t| EarlyBinder(*t).subst(tcx, substs)));
258 .extend(outlives.iter().map(|t| EarlyBinder(*t).subst(tcx, substs)));
261 .extend(overflows.iter().map(|t| EarlyBinder(*t).subst(tcx, substs)));
264 // Objects must be alive in order for their destructor
267 constraints.outlives.push(ty.into());
270 // Types that can't be resolved. Pass them forward.
271 ty::Alias(ty::Projection, ..) | ty::Alias(ty::Opaque, ..) | ty::Param(..) => {
272 constraints.dtorck_types.push(ty);
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);
285 /// Calculates the dtorck constraint for a type.
286 pub(crate) fn adt_dtorck_constraint(
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);
294 if def.is_phantom_data() {
295 // The first generic parameter here is guaranteed to be a type because it's
297 let substs = InternalSubsts::identity_for_item(tcx, def_id);
298 assert_eq!(substs.len(), 1);
299 let result = DropckConstraint {
301 dtorck_types: vec![substs.type_at(0)],
304 debug!("dtorck_constraint: {:?} => {:?}", def, result);
305 return Ok(tcx.arena.alloc(result));
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)?;
313 result.outlives.extend(tcx.destructor_constraints(def));
314 dedup_dtorck_constraint(&mut result);
316 debug!("dtorck_constraint: {:?} => {:?}", def, result);
318 Ok(tcx.arena.alloc(result))
321 fn dedup_dtorck_constraint(c: &mut DropckConstraint<'_>) {
322 let mut outlives = FxHashSet::default();
323 let mut dtorck_types = FxHashSet::default();
325 c.outlives.retain(|&val| outlives.replace(val).is_none());
326 c.dtorck_types.retain(|&val| dtorck_types.replace(val).is_none());