rustc_ty_utils/
needs_drop.rs

1//! Check whether a type has (potentially) non-trivial drop glue.
2
3use rustc_data_structures::fx::FxHashSet;
4use rustc_hir::def_id::DefId;
5use rustc_middle::bug;
6use rustc_middle::query::Providers;
7use rustc_middle::ty::util::{AlwaysRequiresDrop, needs_drop_components};
8use rustc_middle::ty::{self, EarlyBinder, GenericArgsRef, Ty, TyCtxt};
9use rustc_session::Limit;
10use rustc_span::sym;
11use tracing::{debug, instrument};
12
13use crate::errors::NeedsDropOverflow;
14
15type NeedsDropResult<T> = Result<T, AlwaysRequiresDrop>;
16
17fn needs_drop_raw<'tcx>(
18    tcx: TyCtxt<'tcx>,
19    query: ty::PseudoCanonicalInput<'tcx, Ty<'tcx>>,
20) -> bool {
21    // If we don't know a type doesn't need drop, for example if it's a type
22    // parameter without a `Copy` bound, then we conservatively return that it
23    // needs drop.
24    let adt_has_dtor =
25        |adt_def: ty::AdtDef<'tcx>| adt_def.destructor(tcx).map(|_| DtorType::Significant);
26    let res = drop_tys_helper(tcx, query.value, query.typing_env, adt_has_dtor, false, false)
27        .filter(filter_array_elements(tcx, query.typing_env))
28        .next()
29        .is_some();
30
31    debug!("needs_drop_raw({:?}) = {:?}", query, res);
32    res
33}
34
35fn needs_async_drop_raw<'tcx>(
36    tcx: TyCtxt<'tcx>,
37    query: ty::PseudoCanonicalInput<'tcx, Ty<'tcx>>,
38) -> bool {
39    // If we don't know a type doesn't need async drop, for example if it's a
40    // type parameter without a `Copy` bound, then we conservatively return that
41    // it needs async drop.
42    let adt_has_async_dtor =
43        |adt_def: ty::AdtDef<'tcx>| adt_def.async_destructor(tcx).map(|_| DtorType::Significant);
44    let res = drop_tys_helper(tcx, query.value, query.typing_env, adt_has_async_dtor, false, false)
45        .filter(filter_array_elements_async(tcx, query.typing_env))
46        .next()
47        .is_some();
48
49    debug!("needs_async_drop_raw({:?}) = {:?}", query, res);
50    res
51}
52
53/// HACK: in order to not mistakenly assume that `[PhantomData<T>; N]` requires drop glue
54/// we check the element type for drop glue. The correct fix would be looking at the
55/// entirety of the code around `needs_drop_components` and this file and come up with
56/// logic that is easier to follow while not repeating any checks that may thus diverge.
57fn filter_array_elements<'tcx>(
58    tcx: TyCtxt<'tcx>,
59    typing_env: ty::TypingEnv<'tcx>,
60) -> impl Fn(&Result<Ty<'tcx>, AlwaysRequiresDrop>) -> bool {
61    move |ty| match ty {
62        Ok(ty) => match *ty.kind() {
63            ty::Array(elem, _) => tcx.needs_drop_raw(typing_env.as_query_input(elem)),
64            _ => true,
65        },
66        Err(AlwaysRequiresDrop) => true,
67    }
68}
69fn filter_array_elements_async<'tcx>(
70    tcx: TyCtxt<'tcx>,
71    typing_env: ty::TypingEnv<'tcx>,
72) -> impl Fn(&Result<Ty<'tcx>, AlwaysRequiresDrop>) -> bool {
73    move |ty| match ty {
74        Ok(ty) => match *ty.kind() {
75            ty::Array(elem, _) => tcx.needs_async_drop_raw(typing_env.as_query_input(elem)),
76            _ => true,
77        },
78        Err(AlwaysRequiresDrop) => true,
79    }
80}
81
82fn has_significant_drop_raw<'tcx>(
83    tcx: TyCtxt<'tcx>,
84    query: ty::PseudoCanonicalInput<'tcx, Ty<'tcx>>,
85) -> bool {
86    let res = drop_tys_helper(
87        tcx,
88        query.value,
89        query.typing_env,
90        adt_consider_insignificant_dtor(tcx),
91        true,
92        false,
93    )
94    .filter(filter_array_elements(tcx, query.typing_env))
95    .next()
96    .is_some();
97    debug!("has_significant_drop_raw({:?}) = {:?}", query, res);
98    res
99}
100
101struct NeedsDropTypes<'tcx, F> {
102    tcx: TyCtxt<'tcx>,
103    typing_env: ty::TypingEnv<'tcx>,
104    /// Whether to reveal coroutine witnesses, this is set
105    /// to `false` unless we compute `needs_drop` for a coroutine witness.
106    reveal_coroutine_witnesses: bool,
107    query_ty: Ty<'tcx>,
108    seen_tys: FxHashSet<Ty<'tcx>>,
109    /// A stack of types left to process, and the recursion depth when we
110    /// pushed that type. Each round, we pop something from the stack and check
111    /// if it needs drop. If the result depends on whether some other types
112    /// need drop we push them onto the stack.
113    unchecked_tys: Vec<(Ty<'tcx>, usize)>,
114    recursion_limit: Limit,
115    adt_components: F,
116    /// Set this to true if an exhaustive list of types involved in
117    /// drop obligation is requested.
118    exhaustive: bool,
119}
120
121impl<'tcx, F> NeedsDropTypes<'tcx, F> {
122    fn new(
123        tcx: TyCtxt<'tcx>,
124        typing_env: ty::TypingEnv<'tcx>,
125        ty: Ty<'tcx>,
126        exhaustive: bool,
127        adt_components: F,
128    ) -> Self {
129        let mut seen_tys = FxHashSet::default();
130        seen_tys.insert(ty);
131        Self {
132            tcx,
133            typing_env,
134            reveal_coroutine_witnesses: exhaustive,
135            seen_tys,
136            query_ty: ty,
137            unchecked_tys: vec![(ty, 0)],
138            recursion_limit: tcx.recursion_limit(),
139            adt_components,
140            exhaustive,
141        }
142    }
143
144    /// Called when `ty` is found to always require drop.
145    /// If the exhaustive flag is true, then `Ok(ty)` is returned like any other type.
146    /// Otherwise, `Err(AlwaysRequireDrop)` is returned, which will cause iteration to abort.
147    fn always_drop_component(&self, ty: Ty<'tcx>) -> NeedsDropResult<Ty<'tcx>> {
148        if self.exhaustive { Ok(ty) } else { Err(AlwaysRequiresDrop) }
149    }
150}
151
152impl<'tcx, F, I> Iterator for NeedsDropTypes<'tcx, F>
153where
154    F: Fn(ty::AdtDef<'tcx>, GenericArgsRef<'tcx>) -> NeedsDropResult<I>,
155    I: Iterator<Item = Ty<'tcx>>,
156{
157    type Item = NeedsDropResult<Ty<'tcx>>;
158
159    #[instrument(level = "debug", skip(self), ret)]
160    fn next(&mut self) -> Option<NeedsDropResult<Ty<'tcx>>> {
161        let tcx = self.tcx;
162
163        while let Some((ty, level)) = self.unchecked_tys.pop() {
164            debug!(?ty, "needs_drop_components: inspect");
165            if !self.recursion_limit.value_within_limit(level) {
166                // Not having a `Span` isn't great. But there's hopefully some other
167                // recursion limit error as well.
168                debug!("needs_drop_components: recursion limit exceeded");
169                tcx.dcx().emit_err(NeedsDropOverflow { query_ty: self.query_ty });
170                return Some(self.always_drop_component(ty));
171            }
172
173            let components = match needs_drop_components(tcx, ty) {
174                Err(AlwaysRequiresDrop) => return Some(self.always_drop_component(ty)),
175                Ok(components) => components,
176            };
177            debug!("needs_drop_components({:?}) = {:?}", ty, components);
178
179            let queue_type = move |this: &mut Self, component: Ty<'tcx>| {
180                if this.seen_tys.insert(component) {
181                    this.unchecked_tys.push((component, level + 1));
182                }
183            };
184
185            for component in components {
186                match *component.kind() {
187                    // The information required to determine whether a coroutine has drop is
188                    // computed on MIR, while this very method is used to build MIR.
189                    // To avoid cycles, we consider that coroutines always require drop.
190                    //
191                    // HACK: Because we erase regions contained in the coroutine witness, we
192                    // have to conservatively assume that every region captured by the
193                    // coroutine has to be live when dropped. This results in a lot of
194                    // undesirable borrowck errors. During borrowck, we call `needs_drop`
195                    // for the coroutine witness and check whether any of the contained types
196                    // need to be dropped, and only require the captured types to be live
197                    // if they do.
198                    ty::Coroutine(_, args) => {
199                        if self.reveal_coroutine_witnesses {
200                            queue_type(self, args.as_coroutine().witness());
201                        } else {
202                            return Some(self.always_drop_component(ty));
203                        }
204                    }
205                    ty::CoroutineWitness(def_id, args) => {
206                        if let Some(witness) = tcx.mir_coroutine_witnesses(def_id) {
207                            self.reveal_coroutine_witnesses = true;
208                            for field_ty in &witness.field_tys {
209                                queue_type(
210                                    self,
211                                    EarlyBinder::bind(field_ty.ty).instantiate(tcx, args),
212                                );
213                            }
214                        }
215                    }
216
217                    ty::UnsafeBinder(bound_ty) => {
218                        let ty = self.tcx.instantiate_bound_regions_with_erased(bound_ty.into());
219                        queue_type(self, ty);
220                    }
221
222                    _ if tcx.type_is_copy_modulo_regions(self.typing_env, component) => {}
223
224                    ty::Closure(_, args) => {
225                        for upvar in args.as_closure().upvar_tys() {
226                            queue_type(self, upvar);
227                        }
228                    }
229
230                    ty::CoroutineClosure(_, args) => {
231                        for upvar in args.as_coroutine_closure().upvar_tys() {
232                            queue_type(self, upvar);
233                        }
234                    }
235
236                    // Check for a `Drop` impl and whether this is a union or
237                    // `ManuallyDrop`. If it's a struct or enum without a `Drop`
238                    // impl then check whether the field types need `Drop`.
239                    ty::Adt(adt_def, args) => {
240                        let tys = match (self.adt_components)(adt_def, args) {
241                            Err(AlwaysRequiresDrop) => {
242                                return Some(self.always_drop_component(ty));
243                            }
244                            Ok(tys) => tys,
245                        };
246                        for required_ty in tys {
247                            let required = tcx
248                                .try_normalize_erasing_regions(self.typing_env, required_ty)
249                                .unwrap_or(required_ty);
250
251                            queue_type(self, required);
252                        }
253                    }
254                    ty::Alias(..) | ty::Array(..) | ty::Placeholder(_) | ty::Param(_) => {
255                        if ty == component {
256                            // Return the type to the caller: they may be able
257                            // to normalize further than we can.
258                            return Some(Ok(component));
259                        } else {
260                            // Store the type for later. We can't return here
261                            // because we would then lose any other components
262                            // of the type.
263                            queue_type(self, component);
264                        }
265                    }
266
267                    ty::Foreign(_) | ty::Dynamic(..) => {
268                        debug!("needs_drop_components: foreign or dynamic");
269                        return Some(self.always_drop_component(ty));
270                    }
271
272                    ty::Bool
273                    | ty::Char
274                    | ty::Int(_)
275                    | ty::Uint(_)
276                    | ty::Float(_)
277                    | ty::Str
278                    | ty::Slice(_)
279                    | ty::Ref(..)
280                    | ty::RawPtr(..)
281                    | ty::FnDef(..)
282                    | ty::Pat(..)
283                    | ty::FnPtr(..)
284                    | ty::Tuple(_)
285                    | ty::Bound(..)
286                    | ty::Never
287                    | ty::Infer(_)
288                    | ty::Error(_) => {
289                        bug!("unexpected type returned by `needs_drop_components`: {component}")
290                    }
291                }
292            }
293        }
294
295        None
296    }
297}
298
299enum DtorType {
300    /// Type has a `Drop` but it is considered insignificant.
301    /// Check the query `adt_significant_drop_tys` for understanding
302    /// "significant" / "insignificant".
303    Insignificant,
304
305    /// Type has a `Drop` implantation.
306    Significant,
307}
308
309// This is a helper function for `adt_drop_tys` and `adt_significant_drop_tys`.
310// Depending on the implantation of `adt_has_dtor`, it is used to check if the
311// ADT has a destructor or if the ADT only has a significant destructor. For
312// understanding significant destructor look at `adt_significant_drop_tys`.
313fn drop_tys_helper<'tcx>(
314    tcx: TyCtxt<'tcx>,
315    ty: Ty<'tcx>,
316    typing_env: ty::TypingEnv<'tcx>,
317    adt_has_dtor: impl Fn(ty::AdtDef<'tcx>) -> Option<DtorType>,
318    only_significant: bool,
319    exhaustive: bool,
320) -> impl Iterator<Item = NeedsDropResult<Ty<'tcx>>> {
321    fn with_query_cache<'tcx>(
322        tcx: TyCtxt<'tcx>,
323        iter: impl IntoIterator<Item = Ty<'tcx>>,
324    ) -> NeedsDropResult<Vec<Ty<'tcx>>> {
325        iter.into_iter().try_fold(Vec::new(), |mut vec, subty| {
326            match subty.kind() {
327                ty::Adt(adt_id, args) => {
328                    for subty in tcx.adt_drop_tys(adt_id.did())? {
329                        vec.push(EarlyBinder::bind(subty).instantiate(tcx, args));
330                    }
331                }
332                _ => vec.push(subty),
333            };
334            Ok(vec)
335        })
336    }
337
338    let adt_components = move |adt_def: ty::AdtDef<'tcx>, args: GenericArgsRef<'tcx>| {
339        if adt_def.is_manually_drop() {
340            debug!("drop_tys_helper: `{:?}` is manually drop", adt_def);
341            Ok(Vec::new())
342        } else if let Some(dtor_info) = adt_has_dtor(adt_def) {
343            match dtor_info {
344                DtorType::Significant => {
345                    debug!("drop_tys_helper: `{:?}` implements `Drop`", adt_def);
346                    Err(AlwaysRequiresDrop)
347                }
348                DtorType::Insignificant => {
349                    debug!("drop_tys_helper: `{:?}` drop is insignificant", adt_def);
350
351                    // Since the destructor is insignificant, we just want to make sure all of
352                    // the passed in type parameters are also insignificant.
353                    // Eg: Vec<T> dtor is insignificant when T=i32 but significant when T=Mutex.
354                    Ok(args.types().collect())
355                }
356            }
357        } else if adt_def.is_union() {
358            debug!("drop_tys_helper: `{:?}` is a union", adt_def);
359            Ok(Vec::new())
360        } else {
361            let field_tys = adt_def.all_fields().map(|field| {
362                let r = tcx.type_of(field.did).instantiate(tcx, args);
363                debug!(
364                    "drop_tys_helper: Instantiate into {:?} with {:?} getting {:?}",
365                    field, args, r
366                );
367                r
368            });
369            if only_significant {
370                // We can't recurse through the query system here because we might induce a cycle
371                Ok(field_tys.collect())
372            } else {
373                // We can use the query system if we consider all drops significant. In that case,
374                // ADTs are `needs_drop` exactly if they `impl Drop` or if any of their "transitive"
375                // fields do. There can be no cycles here, because ADTs cannot contain themselves as
376                // fields.
377                with_query_cache(tcx, field_tys)
378            }
379        }
380        .map(|v| v.into_iter())
381    };
382
383    NeedsDropTypes::new(tcx, typing_env, ty, exhaustive, adt_components)
384}
385
386fn adt_consider_insignificant_dtor<'tcx>(
387    tcx: TyCtxt<'tcx>,
388) -> impl Fn(ty::AdtDef<'tcx>) -> Option<DtorType> {
389    move |adt_def: ty::AdtDef<'tcx>| {
390        let is_marked_insig = tcx.has_attr(adt_def.did(), sym::rustc_insignificant_dtor);
391        if is_marked_insig {
392            // In some cases like `std::collections::HashMap` where the struct is a wrapper around
393            // a type that is a Drop type, and the wrapped type (eg: `hashbrown::HashMap`) lies
394            // outside stdlib, we might choose to still annotate the wrapper (std HashMap) with
395            // `rustc_insignificant_dtor`, even if the type itself doesn't have a `Drop` impl.
396            Some(DtorType::Insignificant)
397        } else if adt_def.destructor(tcx).is_some() {
398            // There is a Drop impl and the type isn't marked insignificant, therefore Drop must be
399            // significant.
400            Some(DtorType::Significant)
401        } else {
402            // No destructor found nor the type is annotated with `rustc_insignificant_dtor`, we
403            // treat this as the simple case of Drop impl for type.
404            None
405        }
406    }
407}
408
409fn adt_drop_tys<'tcx>(
410    tcx: TyCtxt<'tcx>,
411    def_id: DefId,
412) -> Result<&'tcx ty::List<Ty<'tcx>>, AlwaysRequiresDrop> {
413    // This is for the "adt_drop_tys" query, that considers all `Drop` impls, therefore all dtors are
414    // significant.
415    let adt_has_dtor =
416        |adt_def: ty::AdtDef<'tcx>| adt_def.destructor(tcx).map(|_| DtorType::Significant);
417    // `tcx.type_of(def_id)` identical to `tcx.make_adt(def, identity_args)`
418    drop_tys_helper(
419        tcx,
420        tcx.type_of(def_id).instantiate_identity(),
421        ty::TypingEnv::non_body_analysis(tcx, def_id),
422        adt_has_dtor,
423        false,
424        false,
425    )
426    .collect::<Result<Vec<_>, _>>()
427    .map(|components| tcx.mk_type_list(&components))
428}
429
430fn adt_async_drop_tys<'tcx>(
431    tcx: TyCtxt<'tcx>,
432    def_id: DefId,
433) -> Result<&'tcx ty::List<Ty<'tcx>>, AlwaysRequiresDrop> {
434    // This is for the "adt_async_drop_tys" query, that considers all `AsyncDrop` impls.
435    let adt_has_dtor =
436        |adt_def: ty::AdtDef<'tcx>| adt_def.async_destructor(tcx).map(|_| DtorType::Significant);
437    // `tcx.type_of(def_id)` identical to `tcx.make_adt(def, identity_args)`
438    drop_tys_helper(
439        tcx,
440        tcx.type_of(def_id).instantiate_identity(),
441        ty::TypingEnv::non_body_analysis(tcx, def_id),
442        adt_has_dtor,
443        false,
444        false,
445    )
446    .collect::<Result<Vec<_>, _>>()
447    .map(|components| tcx.mk_type_list(&components))
448}
449
450// If `def_id` refers to a generic ADT, the queries above and below act as if they had been handed
451// a `tcx.make_ty(def, identity_args)` and as such it is legal to instantiate the generic parameters
452// of the ADT into the outputted `ty`s.
453fn adt_significant_drop_tys(
454    tcx: TyCtxt<'_>,
455    def_id: DefId,
456) -> Result<&ty::List<Ty<'_>>, AlwaysRequiresDrop> {
457    drop_tys_helper(
458        tcx,
459        tcx.type_of(def_id).instantiate_identity(), // identical to `tcx.make_adt(def, identity_args)`
460        ty::TypingEnv::non_body_analysis(tcx, def_id),
461        adt_consider_insignificant_dtor(tcx),
462        true,
463        false,
464    )
465    .collect::<Result<Vec<_>, _>>()
466    .map(|components| tcx.mk_type_list(&components))
467}
468
469#[instrument(level = "debug", skip(tcx), ret)]
470fn list_significant_drop_tys<'tcx>(
471    tcx: TyCtxt<'tcx>,
472    key: ty::PseudoCanonicalInput<'tcx, Ty<'tcx>>,
473) -> &'tcx ty::List<Ty<'tcx>> {
474    tcx.mk_type_list(
475        &drop_tys_helper(
476            tcx,
477            key.value,
478            key.typing_env,
479            adt_consider_insignificant_dtor(tcx),
480            true,
481            true,
482        )
483        .filter_map(|res| res.ok())
484        .collect::<Vec<_>>(),
485    )
486}
487
488pub(crate) fn provide(providers: &mut Providers) {
489    *providers = Providers {
490        needs_drop_raw,
491        needs_async_drop_raw,
492        has_significant_drop_raw,
493        adt_drop_tys,
494        adt_async_drop_tys,
495        adt_significant_drop_tys,
496        list_significant_drop_tys,
497        ..*providers
498    };
499}