src/librustc_traits/dropck_outlives.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use rustc::hir::def_id::DefId;
  12 use rustc::infer::canonical::{Canonical, QueryResponse};
  13 use rustc::traits::query::dropck_outlives::{DropckOutlivesResult, DtorckConstraint};
  14 use rustc::traits::query::{CanonicalTyGoal, NoSolution};
  15 use rustc::traits::{FulfillmentContext, Normalized, ObligationCause, TraitEngineExt};
  16 use rustc::ty::query::Providers;
  17 use rustc::ty::subst::{Subst, Substs};
  18 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt};
  19 use rustc::util::nodemap::FxHashSet;
  20 use rustc_data_structures::sync::Lrc;
  21 use syntax::source_map::{Span, DUMMY_SP};
  22
  23 crate fn provide(p: &mut Providers) {
  24     *p = Providers {
  25         dropck_outlives,
  26         adt_dtorck_constraint,
  27         ..*p
  28     };
  29 }
  30
  31 fn dropck_outlives<'tcx>(
  32     tcx: TyCtxt<'_, 'tcx, 'tcx>,
  33     canonical_goal: CanonicalTyGoal<'tcx>,
  34 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>>, NoSolution> {
  35     debug!("dropck_outlives(goal={:#?})", canonical_goal);
  36
  37     tcx.infer_ctxt().enter_with_canonical(
  38         DUMMY_SP,
  39         &canonical_goal,
  40         |ref infcx, goal, canonical_inference_vars| {
  41             let tcx = infcx.tcx;
  42             let ParamEnvAnd {
  43                 param_env,
  44                 value: for_ty,
  45             } = goal;
  46
  47             let mut result = DropckOutlivesResult {
  48                 kinds: vec![],
  49                 overflows: vec![],
  50             };
  51
  52             // A stack of types left to process. Each round, we pop
  53             // something from the stack and invoke
  54             // `dtorck_constraint_for_ty`. This may produce new types that
  55             // have to be pushed on the stack. This continues until we have explored
  56             // all the reachable types from the type `for_ty`.
  57             //
  58             // Example: Imagine that we have the following code:
  59             //
  60             // ```rust
  61             // struct A {
  62             //     value: B,
  63             //     children: Vec<A>,
  64             // }
  65             //
  66             // struct B {
  67             //     value: u32
  68             // }
  69             //
  70             // fn f() {
  71             //   let a: A = ...;
  72             //   ..
  73             // } // here, `a` is dropped
  74             // ```
  75             //
  76             // at the point where `a` is dropped, we need to figure out
  77             // which types inside of `a` contain region data that may be
  78             // accessed by any destructors in `a`. We begin by pushing `A`
  79             // onto the stack, as that is the type of `a`. We will then
  80             // invoke `dtorck_constraint_for_ty` which will expand `A`
  81             // into the types of its fields `(B, Vec<A>)`. These will get
  82             // pushed onto the stack. Eventually, expanding `Vec<A>` will
  83             // lead to us trying to push `A` a second time -- to prevent
  84             // infinite recursion, we notice that `A` was already pushed
  85             // once and stop.
  86             let mut ty_stack = vec![(for_ty, 0)];
  87
  88             // Set used to detect infinite recursion.
  89             let mut ty_set = FxHashSet::default();
  90
  91             let fulfill_cx = &mut FulfillmentContext::new();
  92
  93             let cause = ObligationCause::dummy();
  94             while let Some((ty, depth)) = ty_stack.pop() {
  95                 let DtorckConstraint {
  96                     dtorck_types,
  97                     outlives,
  98                     overflows,
  99                 } = dtorck_constraint_for_ty(tcx, DUMMY_SP, for_ty, depth, ty)?;
 100
 101                 // "outlives" represent types/regions that may be touched
 102                 // by a destructor.
 103                 result.kinds.extend(outlives);
 104                 result.overflows.extend(overflows);
 105
 106                 // dtorck types are "types that will get dropped but which
 107                 // do not themselves define a destructor", more or less. We have
 108                 // to push them onto the stack to be expanded.
 109                 for ty in dtorck_types {
 110                     match infcx.at(&cause, param_env).normalize(&ty) {
 111                         Ok(Normalized {
 112                             value: ty,
 113                             obligations,
 114                         }) => {
 115                             fulfill_cx.register_predicate_obligations(infcx, obligations);
 116
 117                             debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
 118
 119                             match ty.sty {
 120                                 // All parameters live for the duration of the
 121                                 // function.
 122                                 ty::Param(..) => {}
 123
 124                                 // A projection that we couldn't resolve - it
 125                                 // might have a destructor.
 126                                 ty::Projection(..) | ty::Opaque(..) => {
 127                                     result.kinds.push(ty.into());
 128                                 }
 129
 130                                 _ => {
 131                                     if ty_set.insert(ty) {
 132                                         ty_stack.push((ty, depth + 1));
 133                                     }
 134                                 }
 135                             }
 136                         }
 137
 138                         // We don't actually expect to fail to normalize.
 139                         // That implies a WF error somewhere else.
 140                         Err(NoSolution) => {
 141                             return Err(NoSolution);
 142                         }
 143                     }
 144                 }
 145             }
 146
 147             debug!("dropck_outlives: result = {:#?}", result);
 148
 149             infcx.make_canonicalized_query_response(canonical_inference_vars, result, fulfill_cx)
 150         },
 151     )
 152 }
 153
 154 /// Return a set of constraints that needs to be satisfied in
 155 /// order for `ty` to be valid for destruction.
 156 fn dtorck_constraint_for_ty<'a, 'gcx, 'tcx>(
 157     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 158     span: Span,
 159     for_ty: Ty<'tcx>,
 160     depth: usize,
 161     ty: Ty<'tcx>,
 162 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
 163     debug!(
 164         "dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})",
 165         span, for_ty, depth, ty
 166     );
 167
 168     if depth >= *tcx.sess.recursion_limit.get() {
 169         return Ok(DtorckConstraint {
 170             outlives: vec![],
 171             dtorck_types: vec![],
 172             overflows: vec![ty],
 173         });
 174     }
 175
 176     let result = match ty.sty {
 177         ty::Bool
 178         | ty::Char
 179         | ty::Int(_)
 180         | ty::Uint(_)
 181         | ty::Float(_)
 182         | ty::Str
 183         | ty::Never
 184         | ty::Foreign(..)
 185         | ty::RawPtr(..)
 186         | ty::Ref(..)
 187         | ty::FnDef(..)
 188         | ty::FnPtr(_)
 189         | ty::GeneratorWitness(..) => {
 190             // these types never have a destructor
 191             Ok(DtorckConstraint::empty())
 192         }
 193
 194         ty::Array(ety, _) | ty::Slice(ety) => {
 195             // single-element containers, behave like their element
 196             dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ety)
 197         }
 198
 199         ty::Tuple(tys) => tys.iter()
 200             .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
 201             .collect(),
 202
 203         ty::Closure(def_id, substs) => substs
 204             .upvar_tys(def_id, tcx)
 205             .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
 206             .collect(),
 207
 208         ty::Generator(def_id, substs, _movability) => {
 209             // rust-lang/rust#49918: types can be constructed, stored
 210             // in the interior, and sit idle when generator yields
 211             // (and is subsequently dropped).
 212             //
 213             // It would be nice to descend into interior of a
 214             // generator to determine what effects dropping it might
 215             // have (by looking at any drop effects associated with
 216             // its interior).
 217             //
 218             // However, the interior's representation uses things like
 219             // GeneratorWitness that explicitly assume they are not
 220             // traversed in such a manner. So instead, we will
 221             // simplify things for now by treating all generators as
 222             // if they were like trait objects, where its upvars must
 223             // all be alive for the generator's (potential)
 224             // destructor.
 225             //
 226             // In particular, skipping over `_interior` is safe
 227             // because any side-effects from dropping `_interior` can
 228             // only take place through references with lifetimes
 229             // derived from lifetimes attached to the upvars, and we
 230             // *do* incorporate the upvars here.
 231
 232             let constraint = DtorckConstraint {
 233                 outlives: substs.upvar_tys(def_id, tcx).map(|t| t.into()).collect(),
 234                 dtorck_types: vec![],
 235                 overflows: vec![],
 236             };
 237             debug!(
 238                 "dtorck_constraint: generator {:?} => {:?}",
 239                 def_id, constraint
 240             );
 241
 242             Ok(constraint)
 243         }
 244
 245         ty::Adt(def, substs) => {
 246             let DtorckConstraint {
 247                 dtorck_types,
 248                 outlives,
 249                 overflows,
 250             } = tcx.at(span).adt_dtorck_constraint(def.did)?;
 251             Ok(DtorckConstraint {
 252                 // FIXME: we can try to recursively `dtorck_constraint_on_ty`
 253                 // there, but that needs some way to handle cycles.
 254                 dtorck_types: dtorck_types.subst(tcx, substs),
 255                 outlives: outlives.subst(tcx, substs),
 256                 overflows: overflows.subst(tcx, substs),
 257             })
 258         }
 259
 260         // Objects must be alive in order for their destructor
 261         // to be called.
 262         ty::Dynamic(..) => Ok(DtorckConstraint {
 263             outlives: vec![ty.into()],
 264             dtorck_types: vec![],
 265             overflows: vec![],
 266         }),
 267
 268         // Types that can't be resolved. Pass them forward.
 269         ty::Projection(..) | ty::Opaque(..) | ty::Param(..) => Ok(DtorckConstraint {
 270             outlives: vec![],
 271             dtorck_types: vec![ty],
 272             overflows: vec![],
 273         }),
 274
 275         ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
 276
 277         ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error => {
 278             // By the time this code runs, all type variables ought to
 279             // be fully resolved.
 280             Err(NoSolution)
 281         }
 282     };
 283
 284     debug!("dtorck_constraint_for_ty({:?}) = {:?}", ty, result);
 285     result
 286 }
 287
 288 /// Calculates the dtorck constraint for a type.
 289 crate fn adt_dtorck_constraint<'a, 'tcx>(
 290     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 291     def_id: DefId,
 292 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
 293     let def = tcx.adt_def(def_id);
 294     let span = tcx.def_span(def_id);
 295     debug!("dtorck_constraint: {:?}", def);
 296
 297     if def.is_phantom_data() {
 298         // The first generic parameter here is guaranteed to be a type because it's
 299         // `PhantomData`.
 300         let substs = Substs::identity_for_item(tcx, def_id);
 301         assert_eq!(substs.len(), 1);
 302         let result = DtorckConstraint {
 303             outlives: vec![],
 304             dtorck_types: vec![substs.type_at(0)],
 305             overflows: vec![],
 306         };
 307         debug!("dtorck_constraint: {:?} => {:?}", def, result);
 308         return Ok(result);
 309     }
 310
 311     let mut result = def.all_fields()
 312         .map(|field| tcx.type_of(field.did))
 313         .map(|fty| dtorck_constraint_for_ty(tcx, span, fty, 0, fty))
 314         .collect::<Result<DtorckConstraint, NoSolution>>()?;
 315     result.outlives.extend(tcx.destructor_constraints(def));
 316     dedup_dtorck_constraint(&mut result);
 317
 318     debug!("dtorck_constraint: {:?} => {:?}", def, result);
 319
 320     Ok(result)
 321 }
 322
 323 fn dedup_dtorck_constraint<'tcx>(c: &mut DtorckConstraint<'tcx>) {
 324     let mut outlives = FxHashSet::default();
 325     let mut dtorck_types = FxHashSet::default();
 326
 327     c.outlives.retain(|&val| outlives.replace(val).is_none());
 328     c.dtorck_types
 329         .retain(|&val| dtorck_types.replace(val).is_none());
 330 }