src/librustc_ty/needs_drop.rs

   1 //! Check whether a type has (potentially) non-trivial drop glue.
   2
   3 use rustc::ty::subst::Subst;
   4 use rustc::ty::util::{needs_drop_components, AlwaysRequiresDrop};
   5 use rustc::ty::{self, Ty, TyCtxt};
   6 use rustc_data_structures::fx::FxHashSet;
   7 use rustc_hir::def_id::DefId;
   8 use rustc_span::DUMMY_SP;
   9
  10 type NeedsDropResult<T> = Result<T, AlwaysRequiresDrop>;
  11
  12 fn needs_drop_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool {
  13     let adt_fields =
  14         move |adt_def: &ty::AdtDef| tcx.adt_drop_tys(adt_def.did).map(|tys| tys.iter().copied());
  15     // If we don't know a type doesn't need drop, say it's a type parameter
  16     // without a `Copy` bound, then we conservatively return that it needs
  17     // drop.
  18     let res = NeedsDropTypes::new(tcx, query.param_env, query.value, adt_fields).next().is_some();
  19     debug!("needs_drop_raw({:?}) = {:?}", query, res);
  20     res
  21 }
  22
  23 struct NeedsDropTypes<'tcx, F> {
  24     tcx: TyCtxt<'tcx>,
  25     param_env: ty::ParamEnv<'tcx>,
  26     query_ty: Ty<'tcx>,
  27     seen_tys: FxHashSet<Ty<'tcx>>,
  28     /// A stack of types left to process. Each round, we pop something from the
  29     /// stack and check if it needs drop. If the result depends on whether some
  30     /// other types need drop we push them onto the stack.
  31     unchecked_tys: Vec<(Ty<'tcx>, usize)>,
  32     recursion_limit: usize,
  33     adt_components: F,
  34 }
  35
  36 impl<'tcx, F> NeedsDropTypes<'tcx, F> {
  37     fn new(
  38         tcx: TyCtxt<'tcx>,
  39         param_env: ty::ParamEnv<'tcx>,
  40         ty: Ty<'tcx>,
  41         adt_components: F,
  42     ) -> Self {
  43         let mut seen_tys = FxHashSet::default();
  44         seen_tys.insert(ty);
  45         let recursion_limit = *tcx.sess.recursion_limit.get();
  46         Self {
  47             tcx,
  48             param_env,
  49             seen_tys,
  50             query_ty: ty,
  51             unchecked_tys: vec![(ty, 0)],
  52             recursion_limit,
  53             adt_components,
  54         }
  55     }
  56 }
  57
  58 impl<'tcx, F, I> Iterator for NeedsDropTypes<'tcx, F>
  59 where
  60     F: Fn(&ty::AdtDef) -> NeedsDropResult<I>,
  61     I: Iterator<Item = Ty<'tcx>>,
  62 {
  63     type Item = NeedsDropResult<Ty<'tcx>>;
  64
  65     fn next(&mut self) -> Option<NeedsDropResult<Ty<'tcx>>> {
  66         let tcx = self.tcx;
  67
  68         while let Some((ty, level)) = self.unchecked_tys.pop() {
  69             if level > self.recursion_limit {
  70                 // Not having a `Span` isn't great. But there's hopefully some other
  71                 // recursion limit error as well.
  72                 tcx.sess.span_err(
  73                     DUMMY_SP,
  74                     &format!("overflow while checking whether `{}` requires drop", self.query_ty),
  75                 );
  76                 return Some(Err(AlwaysRequiresDrop));
  77             }
  78
  79             let components = match needs_drop_components(ty) {
  80                 Err(e) => return Some(Err(e)),
  81                 Ok(components) => components,
  82             };
  83             debug!("needs_drop_components({:?}) = {:?}", ty, components);
  84
  85             for component in components {
  86                 match component.kind {
  87                     _ if component.is_copy_modulo_regions(tcx, self.param_env, DUMMY_SP) => (),
  88
  89                     ty::Array(elem_ty, len) => {
  90                         // Zero-length arrays never contain anything to drop.
  91                         if len.try_eval_usize(tcx, self.param_env) != Some(0) {
  92                             if self.seen_tys.insert(elem_ty) {
  93                                 self.unchecked_tys.push((elem_ty, level + 1));
  94                             }
  95                         }
  96                     }
  97
  98                     ty::Closure(def_id, substs) => {
  99                         for upvar_ty in substs.as_closure().upvar_tys(def_id, tcx) {
 100                             if self.seen_tys.insert(upvar_ty) {
 101                                 self.unchecked_tys.push((upvar_ty, level + 1));
 102                             }
 103                         }
 104                     }
 105
 106                     // Check for a `Drop` impl and whether this is a union or
 107                     // `ManuallyDrop`. If it's a struct or enum without a `Drop`
 108                     // impl then check whether the field types need `Drop`.
 109                     ty::Adt(adt_def, substs) => {
 110                         let tys = match (self.adt_components)(adt_def) {
 111                             Err(e) => return Some(Err(e)),
 112                             Ok(tys) => tys,
 113                         };
 114                         for required_ty in tys {
 115                             let subst_ty = tcx.normalize_erasing_regions(
 116                                 self.param_env,
 117                                 required_ty.subst(tcx, substs),
 118                             );
 119                             if self.seen_tys.insert(subst_ty) {
 120                                 self.unchecked_tys.push((subst_ty, level + 1));
 121                             }
 122                         }
 123                     }
 124                     ty::Opaque(..) | ty::Projection(..) | ty::Param(_) => {
 125                         if ty == component {
 126                             // Return the type to the caller so they can decide
 127                             // what to do with it.
 128                             return Some(Ok(component));
 129                         } else if self.seen_tys.insert(component) {
 130                             // Store the type for later. We can't return here
 131                             // because we would then lose any other components
 132                             // of the type.
 133                             self.unchecked_tys.push((component, level + 1));
 134                         }
 135                     }
 136                     _ => return Some(Err(AlwaysRequiresDrop)),
 137                 }
 138             }
 139         }
 140
 141         return None;
 142     }
 143 }
 144
 145 fn adt_drop_tys(tcx: TyCtxt<'_>, def_id: DefId) -> Result<&ty::List<Ty<'_>>, AlwaysRequiresDrop> {
 146     let adt_components = move |adt_def: &ty::AdtDef| {
 147         if adt_def.is_manually_drop() {
 148             debug!("adt_drop_tys: `{:?}` is manually drop", adt_def);
 149             return Ok(Vec::new().into_iter());
 150         } else if adt_def.destructor(tcx).is_some() {
 151             debug!("adt_drop_tys: `{:?}` implements `Drop`", adt_def);
 152             return Err(AlwaysRequiresDrop);
 153         } else if adt_def.is_union() {
 154             debug!("adt_drop_tys: `{:?}` is a union", adt_def);
 155             return Ok(Vec::new().into_iter());
 156         }
 157         Ok(adt_def.all_fields().map(|field| tcx.type_of(field.did)).collect::<Vec<_>>().into_iter())
 158     };
 159
 160     let adt_ty = tcx.type_of(def_id);
 161     let param_env = tcx.param_env(def_id);
 162     let res: Result<Vec<_>, _> =
 163         NeedsDropTypes::new(tcx, param_env, adt_ty, adt_components).collect();
 164
 165     debug!("adt_drop_tys(`{}`) = `{:?}`", tcx.def_path_str(def_id), res);
 166     res.map(|components| tcx.intern_type_list(&components))
 167 }
 168
 169 pub(crate) fn provide(providers: &mut ty::query::Providers<'_>) {
 170     *providers = ty::query::Providers { needs_drop_raw, adt_drop_tys, ..*providers };
 171 }