compiler/rustc_ty_utils/src/needs_drop.rs

   1 //! Check whether a type has (potentially) non-trivial drop glue.
   2
   3 use rustc_data_structures::fx::FxHashSet;
   4 use rustc_hir::def_id::DefId;
   5 use rustc_middle::ty::subst::Subst;
   6 use rustc_middle::ty::subst::SubstsRef;
   7 use rustc_middle::ty::util::{needs_drop_components, AlwaysRequiresDrop};
   8 use rustc_middle::ty::{self, Ty, TyCtxt};
   9 use rustc_session::Limit;
  10 use rustc_span::{sym, DUMMY_SP};
  11
  12 type NeedsDropResult<T> = Result<T, AlwaysRequiresDrop>;
  13
  14 fn needs_drop_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool {
  15     // If we don't know a type doesn't need drop, for example if it's a type
  16     // parameter without a `Copy` bound, then we conservatively return that it
  17     // needs drop.
  18     let adt_has_dtor =
  19         |adt_def: &ty::AdtDef| adt_def.destructor(tcx).map(|_| DtorType::Significant);
  20     let res = drop_tys_helper(tcx, query.value, query.param_env, adt_has_dtor).next().is_some();
  21
  22     debug!("needs_drop_raw({:?}) = {:?}", query, res);
  23     res
  24 }
  25
  26 fn has_significant_drop_raw<'tcx>(
  27     tcx: TyCtxt<'tcx>,
  28     query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
  29 ) -> bool {
  30     let res =
  31         drop_tys_helper(tcx, query.value, query.param_env, adt_consider_insignificant_dtor(tcx))
  32             .next()
  33             .is_some();
  34     debug!("has_significant_drop_raw({:?}) = {:?}", query, res);
  35     res
  36 }
  37
  38 struct NeedsDropTypes<'tcx, F> {
  39     tcx: TyCtxt<'tcx>,
  40     param_env: ty::ParamEnv<'tcx>,
  41     query_ty: Ty<'tcx>,
  42     seen_tys: FxHashSet<Ty<'tcx>>,
  43     /// A stack of types left to process, and the recursion depth when we
  44     /// pushed that type. Each round, we pop something from the stack and check
  45     /// if it needs drop. If the result depends on whether some other types
  46     /// need drop we push them onto the stack.
  47     unchecked_tys: Vec<(Ty<'tcx>, usize)>,
  48     recursion_limit: Limit,
  49     adt_components: F,
  50 }
  51
  52 impl<'tcx, F> NeedsDropTypes<'tcx, F> {
  53     fn new(
  54         tcx: TyCtxt<'tcx>,
  55         param_env: ty::ParamEnv<'tcx>,
  56         ty: Ty<'tcx>,
  57         adt_components: F,
  58     ) -> Self {
  59         let mut seen_tys = FxHashSet::default();
  60         seen_tys.insert(ty);
  61         Self {
  62             tcx,
  63             param_env,
  64             seen_tys,
  65             query_ty: ty,
  66             unchecked_tys: vec![(ty, 0)],
  67             recursion_limit: tcx.recursion_limit(),
  68             adt_components,
  69         }
  70     }
  71 }
  72
  73 impl<'tcx, F, I> Iterator for NeedsDropTypes<'tcx, F>
  74 where
  75     F: Fn(&ty::AdtDef, SubstsRef<'tcx>) -> NeedsDropResult<I>,
  76     I: Iterator<Item = Ty<'tcx>>,
  77 {
  78     type Item = NeedsDropResult<Ty<'tcx>>;
  79
  80     fn next(&mut self) -> Option<NeedsDropResult<Ty<'tcx>>> {
  81         let tcx = self.tcx;
  82
  83         while let Some((ty, level)) = self.unchecked_tys.pop() {
  84             if !self.recursion_limit.value_within_limit(level) {
  85                 // Not having a `Span` isn't great. But there's hopefully some other
  86                 // recursion limit error as well.
  87                 tcx.sess.span_err(
  88                     DUMMY_SP,
  89                     &format!("overflow while checking whether `{}` requires drop", self.query_ty),
  90                 );
  91                 return Some(Err(AlwaysRequiresDrop));
  92             }
  93
  94             let components = match needs_drop_components(ty, &tcx.data_layout) {
  95                 Err(e) => return Some(Err(e)),
  96                 Ok(components) => components,
  97             };
  98             debug!("needs_drop_components({:?}) = {:?}", ty, components);
  99
 100             let queue_type = move |this: &mut Self, component: Ty<'tcx>| {
 101                 if this.seen_tys.insert(component) {
 102                     this.unchecked_tys.push((component, level + 1));
 103                 }
 104             };
 105
 106             for component in components {
 107                 match *component.kind() {
 108                     _ if component.is_copy_modulo_regions(tcx.at(DUMMY_SP), self.param_env) => (),
 109
 110                     ty::Closure(_, substs) => {
 111                         queue_type(self, substs.as_closure().tupled_upvars_ty());
 112                     }
 113
 114                     ty::Generator(def_id, substs, _) => {
 115                         let substs = substs.as_generator();
 116                         queue_type(self, substs.tupled_upvars_ty());
 117
 118                         let witness = substs.witness();
 119                         let interior_tys = match witness.kind() {
 120                             &ty::GeneratorWitness(tys) => tcx.erase_late_bound_regions(tys),
 121                             _ => {
 122                                 tcx.sess.delay_span_bug(
 123                                     tcx.hir().span_if_local(def_id).unwrap_or(DUMMY_SP),
 124                                     &format!("unexpected generator witness type {:?}", witness),
 125                                 );
 126                                 return Some(Err(AlwaysRequiresDrop));
 127                             }
 128                         };
 129
 130                         for interior_ty in interior_tys {
 131                             queue_type(self, interior_ty);
 132                         }
 133                     }
 134
 135                     // Check for a `Drop` impl and whether this is a union or
 136                     // `ManuallyDrop`. If it's a struct or enum without a `Drop`
 137                     // impl then check whether the field types need `Drop`.
 138                     ty::Adt(adt_def, substs) => {
 139                         let tys = match (self.adt_components)(adt_def, substs) {
 140                             Err(e) => return Some(Err(e)),
 141                             Ok(tys) => tys,
 142                         };
 143                         for required_ty in tys {
 144                             let subst_ty =
 145                                 tcx.normalize_erasing_regions(self.param_env, required_ty);
 146                             queue_type(self, subst_ty);
 147                         }
 148                     }
 149                     ty::Array(..) | ty::Opaque(..) | ty::Projection(..) | ty::Param(_) => {
 150                         if ty == component {
 151                             // Return the type to the caller: they may be able
 152                             // to normalize further than we can.
 153                             return Some(Ok(component));
 154                         } else {
 155                             // Store the type for later. We can't return here
 156                             // because we would then lose any other components
 157                             // of the type.
 158                             queue_type(self, component);
 159                         }
 160                     }
 161                     _ => return Some(Err(AlwaysRequiresDrop)),
 162                 }
 163             }
 164         }
 165
 166         None
 167     }
 168 }
 169
 170 enum DtorType {
 171     /// Type has a `Drop` but it is considered insignificant.
 172     /// Check the query `adt_significant_drop_tys` for understanding
 173     /// "significant" / "insignificant".
 174     Insignificant,
 175
 176     /// Type has a `Drop` implentation.
 177     Significant,
 178 }
 179
 180 // This is a helper function for `adt_drop_tys` and `adt_significant_drop_tys`.
 181 // Depending on the implentation of `adt_has_dtor`, it is used to check if the
 182 // ADT has a destructor or if the ADT only has a significant destructor. For
 183 // understanding significant destructor look at `adt_significant_drop_tys`.
 184 fn drop_tys_helper<'tcx>(
 185     tcx: TyCtxt<'tcx>,
 186     ty: Ty<'tcx>,
 187     param_env: rustc_middle::ty::ParamEnv<'tcx>,
 188     adt_has_dtor: impl Fn(&ty::AdtDef) -> Option<DtorType>,
 189 ) -> impl Iterator<Item = NeedsDropResult<Ty<'tcx>>> {
 190     let adt_components = move |adt_def: &ty::AdtDef, substs: SubstsRef<'tcx>| {
 191         if adt_def.is_manually_drop() {
 192             debug!("drop_tys_helper: `{:?}` is manually drop", adt_def);
 193             return Ok(Vec::new().into_iter());
 194         } else if let Some(dtor_info) = adt_has_dtor(adt_def) {
 195             match dtor_info {
 196                 DtorType::Significant => {
 197                     debug!("drop_tys_helper: `{:?}` implements `Drop`", adt_def);
 198                     return Err(AlwaysRequiresDrop);
 199                 }
 200                 DtorType::Insignificant => {
 201                     debug!("drop_tys_helper: `{:?}` drop is insignificant", adt_def);
 202
 203                     // Since the destructor is insignificant, we just want to make sure all of
 204                     // the passed in type parameters are also insignificant.
 205                     // Eg: Vec<T> dtor is insignificant when T=i32 but significant when T=Mutex.
 206                     return Ok(substs.types().collect::<Vec<Ty<'_>>>().into_iter());
 207                 }
 208             }
 209         } else if adt_def.is_union() {
 210             debug!("drop_tys_helper: `{:?}` is a union", adt_def);
 211             return Ok(Vec::new().into_iter());
 212         }
 213         Ok(adt_def
 214             .all_fields()
 215             .map(|field| {
 216                 let r = tcx.type_of(field.did).subst(tcx, substs);
 217                 debug!("drop_tys_helper: Subst into {:?} with {:?} gettng {:?}", field, substs, r);
 218                 r
 219             })
 220             .collect::<Vec<_>>()
 221             .into_iter())
 222     };
 223
 224     NeedsDropTypes::new(tcx, param_env, ty, adt_components)
 225 }
 226
 227 fn adt_consider_insignificant_dtor<'tcx>(
 228     tcx: TyCtxt<'tcx>,
 229 ) -> impl Fn(&ty::AdtDef) -> Option<DtorType> + 'tcx {
 230     move |adt_def: &ty::AdtDef| {
 231         let is_marked_insig = tcx.has_attr(adt_def.did, sym::rustc_insignificant_dtor);
 232         if is_marked_insig {
 233             // In some cases like `std::collections::HashMap` where the struct is a wrapper around
 234             // a type that is a Drop type, and the wrapped type (eg: `hashbrown::HashMap`) lies
 235             // outside stdlib, we might choose to still annotate the the wrapper (std HashMap) with
 236             // `rustc_insignificant_dtor`, even if the type itself doesn't have a `Drop` impl.
 237             Some(DtorType::Insignificant)
 238         } else if adt_def.destructor(tcx).is_some() {
 239             // There is a Drop impl and the type isn't marked insignificant, therefore Drop must be
 240             // significant.
 241             Some(DtorType::Significant)
 242         } else {
 243             // No destructor found nor the type is annotated with `rustc_insignificant_dtor`, we
 244             // treat this as the simple case of Drop impl for type.
 245             None
 246         }
 247     }
 248 }
 249
 250 fn adt_drop_tys(tcx: TyCtxt<'_>, def_id: DefId) -> Result<&ty::List<Ty<'_>>, AlwaysRequiresDrop> {
 251     // This is for the "adt_drop_tys" query, that considers all `Drop` impls, therefore all dtors are
 252     // significant.
 253     let adt_has_dtor =
 254         |adt_def: &ty::AdtDef| adt_def.destructor(tcx).map(|_| DtorType::Significant);
 255     drop_tys_helper(tcx, tcx.type_of(def_id), tcx.param_env(def_id), adt_has_dtor)
 256         .collect::<Result<Vec<_>, _>>()
 257         .map(|components| tcx.intern_type_list(&components))
 258 }
 259
 260 fn adt_significant_drop_tys(
 261     tcx: TyCtxt<'_>,
 262     def_id: DefId,
 263 ) -> Result<&ty::List<Ty<'_>>, AlwaysRequiresDrop> {
 264     drop_tys_helper(
 265         tcx,
 266         tcx.type_of(def_id),
 267         tcx.param_env(def_id),
 268         adt_consider_insignificant_dtor(tcx),
 269     )
 270     .collect::<Result<Vec<_>, _>>()
 271     .map(|components| tcx.intern_type_list(&components))
 272 }
 273
 274 pub(crate) fn provide(providers: &mut ty::query::Providers) {
 275     *providers = ty::query::Providers {
 276         needs_drop_raw,
 277         has_significant_drop_raw,
 278         adt_drop_tys,
 279         adt_significant_drop_tys,
 280         ..*providers
 281     };
 282 }