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