rustc_trait_selection/traits/query/dropck_outlives.rs
1use rustc_data_structures::fx::FxHashSet;
2use rustc_infer::traits::query::type_op::DropckOutlives;
3use rustc_middle::traits::query::{DropckConstraint, DropckOutlivesResult};
4use rustc_middle::ty::{self, EarlyBinder, ParamEnvAnd, Ty, TyCtxt};
5use rustc_span::{DUMMY_SP, Span};
6use tracing::{debug, instrument};
7
8use crate::traits::query::NoSolution;
9use crate::traits::query::normalize::QueryNormalizeExt;
10use crate::traits::{Normalized, ObligationCause, ObligationCtxt};
11
12/// This returns true if the type `ty` is "trivial" for
13/// dropck-outlives -- that is, if it doesn't require any types to
14/// outlive. This is similar but not *quite* the same as the
15/// `needs_drop` test in the compiler already -- that is, for every
16/// type T for which this function return true, needs-drop would
17/// return `false`. But the reverse does not hold: in particular,
18/// `needs_drop` returns false for `PhantomData`, but it is not
19/// trivial for dropck-outlives.
20///
21/// Note also that `needs_drop` requires a "global" type (i.e., one
22/// with erased regions), but this function does not.
23///
24// FIXME(@lcnr): remove this module and move this function somewhere else.
25pub fn trivial_dropck_outlives<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool {
26 match ty.kind() {
27 // None of these types have a destructor and hence they do not
28 // require anything in particular to outlive the dtor's
29 // execution.
30 ty::Infer(ty::FreshIntTy(_))
31 | ty::Infer(ty::FreshFloatTy(_))
32 | ty::Bool
33 | ty::Int(_)
34 | ty::Uint(_)
35 | ty::Float(_)
36 | ty::Never
37 | ty::FnDef(..)
38 | ty::FnPtr(..)
39 | ty::Char
40 | ty::CoroutineWitness(..)
41 | ty::RawPtr(_, _)
42 | ty::Ref(..)
43 | ty::Str
44 | ty::Foreign(..)
45 | ty::Error(_) => true,
46
47 // `T is PAT` and `[T]` have same properties as T.
48 ty::Pat(ty, _) | ty::Slice(ty) => trivial_dropck_outlives(tcx, *ty),
49 ty::Array(ty, size) => {
50 // Empty array never has a dtor. See issue #110288.
51 match size.try_to_target_usize(tcx) {
52 Some(0) => true,
53 _ => trivial_dropck_outlives(tcx, *ty),
54 }
55 }
56
57 // (T1..Tn) and closures have same properties as T1..Tn --
58 // check if *all* of them are trivial.
59 ty::Tuple(tys) => tys.iter().all(|t| trivial_dropck_outlives(tcx, t)),
60
61 ty::Closure(_, args) => trivial_dropck_outlives(tcx, args.as_closure().tupled_upvars_ty()),
62 ty::CoroutineClosure(_, args) => {
63 trivial_dropck_outlives(tcx, args.as_coroutine_closure().tupled_upvars_ty())
64 }
65
66 ty::Adt(def, _) => {
67 if def.is_manually_drop() {
68 // `ManuallyDrop` never has a dtor.
69 true
70 } else {
71 // Other types might. Moreover, PhantomData doesn't
72 // have a dtor, but it is considered to own its
73 // content, so it is non-trivial. Unions can have `impl Drop`,
74 // and hence are non-trivial as well.
75 false
76 }
77 }
78
79 // The following *might* require a destructor: needs deeper inspection.
80 ty::Dynamic(..)
81 | ty::Alias(..)
82 | ty::Param(_)
83 | ty::Placeholder(..)
84 | ty::Infer(_)
85 | ty::Bound(..)
86 | ty::Coroutine(..)
87 | ty::UnsafeBinder(_) => false,
88 }
89}
90
91pub fn compute_dropck_outlives_inner<'tcx>(
92 ocx: &ObligationCtxt<'_, 'tcx>,
93 goal: ParamEnvAnd<'tcx, DropckOutlives<'tcx>>,
94 span: Span,
95) -> Result<DropckOutlivesResult<'tcx>, NoSolution> {
96 let tcx = ocx.infcx.tcx;
97 let ParamEnvAnd { param_env, value: DropckOutlives { dropped_ty } } = goal;
98
99 let mut result = DropckOutlivesResult { kinds: vec![], overflows: vec![] };
100
101 // A stack of types left to process. Each round, we pop
102 // something from the stack and invoke
103 // `dtorck_constraint_for_ty_inner`. This may produce new types that
104 // have to be pushed on the stack. This continues until we have explored
105 // all the reachable types from the type `dropped_ty`.
106 //
107 // Example: Imagine that we have the following code:
108 //
109 // ```rust
110 // struct A {
111 // value: B,
112 // children: Vec<A>,
113 // }
114 //
115 // struct B {
116 // value: u32
117 // }
118 //
119 // fn f() {
120 // let a: A = ...;
121 // ..
122 // } // here, `a` is dropped
123 // ```
124 //
125 // at the point where `a` is dropped, we need to figure out
126 // which types inside of `a` contain region data that may be
127 // accessed by any destructors in `a`. We begin by pushing `A`
128 // onto the stack, as that is the type of `a`. We will then
129 // invoke `dtorck_constraint_for_ty_inner` which will expand `A`
130 // into the types of its fields `(B, Vec<A>)`. These will get
131 // pushed onto the stack. Eventually, expanding `Vec<A>` will
132 // lead to us trying to push `A` a second time -- to prevent
133 // infinite recursion, we notice that `A` was already pushed
134 // once and stop.
135 let mut ty_stack = vec![(dropped_ty, 0)];
136
137 // Set used to detect infinite recursion.
138 let mut ty_set = FxHashSet::default();
139
140 let cause = ObligationCause::dummy_with_span(span);
141 let mut constraints = DropckConstraint::empty();
142 while let Some((ty, depth)) = ty_stack.pop() {
143 debug!(
144 "{} kinds, {} overflows, {} ty_stack",
145 result.kinds.len(),
146 result.overflows.len(),
147 ty_stack.len()
148 );
149 dtorck_constraint_for_ty_inner(
150 tcx,
151 ocx.infcx.typing_env(param_env),
152 DUMMY_SP,
153 depth,
154 ty,
155 &mut constraints,
156 )?;
157
158 // "outlives" represent types/regions that may be touched
159 // by a destructor.
160 result.kinds.append(&mut constraints.outlives);
161 result.overflows.append(&mut constraints.overflows);
162
163 // If we have even one overflow, we should stop trying to evaluate further --
164 // chances are, the subsequent overflows for this evaluation won't provide useful
165 // information and will just decrease the speed at which we can emit these errors
166 // (since we'll be printing for just that much longer for the often enormous types
167 // that result here).
168 if !result.overflows.is_empty() {
169 break;
170 }
171
172 // dtorck types are "types that will get dropped but which
173 // do not themselves define a destructor", more or less. We have
174 // to push them onto the stack to be expanded.
175 for ty in constraints.dtorck_types.drain(..) {
176 let Normalized { value: ty, obligations } =
177 ocx.infcx.at(&cause, param_env).query_normalize(ty)?;
178 ocx.register_obligations(obligations);
179
180 debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
181
182 match ty.kind() {
183 // All parameters live for the duration of the
184 // function.
185 ty::Param(..) => {}
186
187 // A projection that we couldn't resolve - it
188 // might have a destructor.
189 ty::Alias(..) => {
190 result.kinds.push(ty.into());
191 }
192
193 _ => {
194 if ty_set.insert(ty) {
195 ty_stack.push((ty, depth + 1));
196 }
197 }
198 }
199 }
200 }
201
202 debug!("dropck_outlives: result = {:#?}", result);
203 Ok(result)
204}
205
206/// Returns a set of constraints that needs to be satisfied in
207/// order for `ty` to be valid for destruction.
208#[instrument(level = "debug", skip(tcx, typing_env, span, constraints))]
209pub fn dtorck_constraint_for_ty_inner<'tcx>(
210 tcx: TyCtxt<'tcx>,
211 typing_env: ty::TypingEnv<'tcx>,
212 span: Span,
213 depth: usize,
214 ty: Ty<'tcx>,
215 constraints: &mut DropckConstraint<'tcx>,
216) -> Result<(), NoSolution> {
217 if !tcx.recursion_limit().value_within_limit(depth) {
218 constraints.overflows.push(ty);
219 return Ok(());
220 }
221
222 if trivial_dropck_outlives(tcx, ty) {
223 return Ok(());
224 }
225
226 match ty.kind() {
227 ty::Bool
228 | ty::Char
229 | ty::Int(_)
230 | ty::Uint(_)
231 | ty::Float(_)
232 | ty::Str
233 | ty::Never
234 | ty::Foreign(..)
235 | ty::RawPtr(..)
236 | ty::Ref(..)
237 | ty::FnDef(..)
238 | ty::FnPtr(..)
239 | ty::CoroutineWitness(..) => {
240 // these types never have a destructor
241 }
242
243 ty::Pat(ety, _) | ty::Array(ety, _) | ty::Slice(ety) => {
244 // single-element containers, behave like their element
245 rustc_data_structures::stack::ensure_sufficient_stack(|| {
246 dtorck_constraint_for_ty_inner(tcx, typing_env, span, depth + 1, *ety, constraints)
247 })?;
248 }
249
250 ty::Tuple(tys) => rustc_data_structures::stack::ensure_sufficient_stack(|| {
251 for ty in tys.iter() {
252 dtorck_constraint_for_ty_inner(tcx, typing_env, span, depth + 1, ty, constraints)?;
253 }
254 Ok::<_, NoSolution>(())
255 })?,
256
257 ty::Closure(_, args) => rustc_data_structures::stack::ensure_sufficient_stack(|| {
258 for ty in args.as_closure().upvar_tys() {
259 dtorck_constraint_for_ty_inner(tcx, typing_env, span, depth + 1, ty, constraints)?;
260 }
261 Ok::<_, NoSolution>(())
262 })?,
263
264 ty::CoroutineClosure(_, args) => {
265 rustc_data_structures::stack::ensure_sufficient_stack(|| {
266 for ty in args.as_coroutine_closure().upvar_tys() {
267 dtorck_constraint_for_ty_inner(
268 tcx,
269 typing_env,
270 span,
271 depth + 1,
272 ty,
273 constraints,
274 )?;
275 }
276 Ok::<_, NoSolution>(())
277 })?
278 }
279
280 ty::Coroutine(_, args) => {
281 // rust-lang/rust#49918: types can be constructed, stored
282 // in the interior, and sit idle when coroutine yields
283 // (and is subsequently dropped).
284 //
285 // It would be nice to descend into interior of a
286 // coroutine to determine what effects dropping it might
287 // have (by looking at any drop effects associated with
288 // its interior).
289 //
290 // However, the interior's representation uses things like
291 // CoroutineWitness that explicitly assume they are not
292 // traversed in such a manner. So instead, we will
293 // simplify things for now by treating all coroutines as
294 // if they were like trait objects, where its upvars must
295 // all be alive for the coroutine's (potential)
296 // destructor.
297 //
298 // In particular, skipping over `_interior` is safe
299 // because any side-effects from dropping `_interior` can
300 // only take place through references with lifetimes
301 // derived from lifetimes attached to the upvars and resume
302 // argument, and we *do* incorporate those here.
303 let args = args.as_coroutine();
304
305 // While we conservatively assume that all coroutines require drop
306 // to avoid query cycles during MIR building, we can check the actual
307 // witness during borrowck to avoid unnecessary liveness constraints.
308 if args.witness().needs_drop(tcx, tcx.erase_regions(typing_env)) {
309 constraints.outlives.extend(args.upvar_tys().iter().map(ty::GenericArg::from));
310 constraints.outlives.push(args.resume_ty().into());
311 }
312 }
313
314 ty::Adt(def, args) => {
315 let DropckConstraint { dtorck_types, outlives, overflows } =
316 tcx.at(span).adt_dtorck_constraint(def.did())?;
317 // FIXME: we can try to recursively `dtorck_constraint_on_ty`
318 // there, but that needs some way to handle cycles.
319 constraints
320 .dtorck_types
321 .extend(dtorck_types.iter().map(|t| EarlyBinder::bind(*t).instantiate(tcx, args)));
322 constraints
323 .outlives
324 .extend(outlives.iter().map(|t| EarlyBinder::bind(*t).instantiate(tcx, args)));
325 constraints
326 .overflows
327 .extend(overflows.iter().map(|t| EarlyBinder::bind(*t).instantiate(tcx, args)));
328 }
329
330 // Objects must be alive in order for their destructor
331 // to be called.
332 ty::Dynamic(..) => {
333 constraints.outlives.push(ty.into());
334 }
335
336 // Types that can't be resolved. Pass them forward.
337 ty::Alias(..) | ty::Param(..) => {
338 constraints.dtorck_types.push(ty);
339 }
340
341 // Can't instantiate binder here.
342 ty::UnsafeBinder(_) => {
343 constraints.dtorck_types.push(ty);
344 }
345
346 ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error(_) => {
347 // By the time this code runs, all type variables ought to
348 // be fully resolved.
349 return Err(NoSolution);
350 }
351 }
352
353 Ok(())
354}