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}