1 use rustc::hir::def_id::DefId;
2 use rustc::infer::canonical::{Canonical, QueryResponse};
3 use rustc::traits::query::dropck_outlives::{DropckOutlivesResult, DtorckConstraint};
4 use rustc::traits::query::{CanonicalTyGoal, NoSolution};
5 use rustc::traits::{TraitEngine, Normalized, ObligationCause, TraitEngineExt};
6 use rustc::ty::query::Providers;
7 use rustc::ty::subst::{Subst, InternalSubsts};
8 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt};
9 use rustc::util::nodemap::FxHashSet;
10 use rustc_data_structures::sync::Lrc;
11 use syntax::source_map::{Span, DUMMY_SP};
13 crate fn provide(p: &mut Providers<'_>) {
16 adt_dtorck_constraint,
21 fn dropck_outlives<'tcx>(
22 tcx: TyCtxt<'_, 'tcx, 'tcx>,
23 canonical_goal: CanonicalTyGoal<'tcx>,
24 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>>, NoSolution> {
25 debug!("dropck_outlives(goal={:#?})", canonical_goal);
27 tcx.infer_ctxt().enter_with_canonical(
30 |ref infcx, goal, canonical_inference_vars| {
37 let mut result = DropckOutlivesResult {
42 // A stack of types left to process. Each round, we pop
43 // something from the stack and invoke
44 // `dtorck_constraint_for_ty`. This may produce new types that
45 // have to be pushed on the stack. This continues until we have explored
46 // all the reachable types from the type `for_ty`.
48 // Example: Imagine that we have the following code:
63 // } // here, `a` is dropped
66 // at the point where `a` is dropped, we need to figure out
67 // which types inside of `a` contain region data that may be
68 // accessed by any destructors in `a`. We begin by pushing `A`
69 // onto the stack, as that is the type of `a`. We will then
70 // invoke `dtorck_constraint_for_ty` which will expand `A`
71 // into the types of its fields `(B, Vec<A>)`. These will get
72 // pushed onto the stack. Eventually, expanding `Vec<A>` will
73 // lead to us trying to push `A` a second time -- to prevent
74 // infinite recursion, we notice that `A` was already pushed
76 let mut ty_stack = vec![(for_ty, 0)];
78 // Set used to detect infinite recursion.
79 let mut ty_set = FxHashSet::default();
81 let mut fulfill_cx = TraitEngine::new(infcx.tcx);
83 let cause = ObligationCause::dummy();
84 while let Some((ty, depth)) = ty_stack.pop() {
85 let DtorckConstraint {
89 } = dtorck_constraint_for_ty(tcx, DUMMY_SP, for_ty, depth, ty)?;
91 // "outlives" represent types/regions that may be touched
93 result.kinds.extend(outlives);
94 result.overflows.extend(overflows);
96 // dtorck types are "types that will get dropped but which
97 // do not themselves define a destructor", more or less. We have
98 // to push them onto the stack to be expanded.
99 for ty in dtorck_types {
100 match infcx.at(&cause, param_env).normalize(&ty) {
105 fulfill_cx.register_predicate_obligations(infcx, obligations);
107 debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
110 // All parameters live for the duration of the
114 // A projection that we couldn't resolve - it
115 // might have a destructor.
116 ty::Projection(..) | ty::Opaque(..) => {
117 result.kinds.push(ty.into());
121 if ty_set.insert(ty) {
122 ty_stack.push((ty, depth + 1));
128 // We don't actually expect to fail to normalize.
129 // That implies a WF error somewhere else.
131 return Err(NoSolution);
137 debug!("dropck_outlives: result = {:#?}", result);
139 infcx.make_canonicalized_query_response(
140 canonical_inference_vars,
148 /// Returns a set of constraints that needs to be satisfied in
149 /// order for `ty` to be valid for destruction.
150 fn dtorck_constraint_for_ty<'a, 'gcx, 'tcx>(
151 tcx: TyCtxt<'a, 'gcx, 'tcx>,
156 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
158 "dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})",
159 span, for_ty, depth, ty
162 if depth >= *tcx.sess.recursion_limit.get() {
163 return Ok(DtorckConstraint {
165 dtorck_types: vec![],
170 let result = match ty.sty {
183 | ty::GeneratorWitness(..) => {
184 // these types never have a destructor
185 Ok(DtorckConstraint::empty())
188 ty::Array(ety, _) | ty::Slice(ety) => {
189 // single-element containers, behave like their element
190 dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ety)
193 ty::Tuple(tys) => tys.iter()
194 .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
197 ty::Closure(def_id, substs) => substs
198 .upvar_tys(def_id, tcx)
199 .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
202 ty::Generator(def_id, substs, _movability) => {
203 // rust-lang/rust#49918: types can be constructed, stored
204 // in the interior, and sit idle when generator yields
205 // (and is subsequently dropped).
207 // It would be nice to descend into interior of a
208 // generator to determine what effects dropping it might
209 // have (by looking at any drop effects associated with
212 // However, the interior's representation uses things like
213 // GeneratorWitness that explicitly assume they are not
214 // traversed in such a manner. So instead, we will
215 // simplify things for now by treating all generators as
216 // if they were like trait objects, where its upvars must
217 // all be alive for the generator's (potential)
220 // In particular, skipping over `_interior` is safe
221 // because any side-effects from dropping `_interior` can
222 // only take place through references with lifetimes
223 // derived from lifetimes attached to the upvars, and we
224 // *do* incorporate the upvars here.
226 let constraint = DtorckConstraint {
227 outlives: substs.upvar_tys(def_id, tcx).map(|t| t.into()).collect(),
228 dtorck_types: vec![],
232 "dtorck_constraint: generator {:?} => {:?}",
239 ty::Adt(def, substs) => {
240 let DtorckConstraint {
244 } = tcx.at(span).adt_dtorck_constraint(def.did)?;
245 Ok(DtorckConstraint {
246 // FIXME: we can try to recursively `dtorck_constraint_on_ty`
247 // there, but that needs some way to handle cycles.
248 dtorck_types: dtorck_types.subst(tcx, substs),
249 outlives: outlives.subst(tcx, substs),
250 overflows: overflows.subst(tcx, substs),
254 // Objects must be alive in order for their destructor
256 ty::Dynamic(..) => Ok(DtorckConstraint {
257 outlives: vec![ty.into()],
258 dtorck_types: vec![],
262 // Types that can't be resolved. Pass them forward.
263 ty::Projection(..) | ty::Opaque(..) | ty::Param(..) => Ok(DtorckConstraint {
265 dtorck_types: vec![ty],
269 ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
271 ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error => {
272 // By the time this code runs, all type variables ought to
273 // be fully resolved.
278 debug!("dtorck_constraint_for_ty({:?}) = {:?}", ty, result);
282 /// Calculates the dtorck constraint for a type.
283 crate fn adt_dtorck_constraint<'a, 'tcx>(
284 tcx: TyCtxt<'a, 'tcx, 'tcx>,
286 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
287 let def = tcx.adt_def(def_id);
288 let span = tcx.def_span(def_id);
289 debug!("dtorck_constraint: {:?}", def);
291 if def.is_phantom_data() {
292 // The first generic parameter here is guaranteed to be a type because it's
294 let substs = InternalSubsts::identity_for_item(tcx, def_id);
295 assert_eq!(substs.len(), 1);
296 let result = DtorckConstraint {
298 dtorck_types: vec![substs.type_at(0)],
301 debug!("dtorck_constraint: {:?} => {:?}", def, result);
305 let mut result = def.all_fields()
306 .map(|field| tcx.type_of(field.did))
307 .map(|fty| dtorck_constraint_for_ty(tcx, span, fty, 0, fty))
308 .collect::<Result<DtorckConstraint<'_>, NoSolution>>()?;
309 result.outlives.extend(tcx.destructor_constraints(def));
310 dedup_dtorck_constraint(&mut result);
312 debug!("dtorck_constraint: {:?} => {:?}", def, result);
317 fn dedup_dtorck_constraint<'tcx>(c: &mut DtorckConstraint<'tcx>) {
318 let mut outlives = FxHashSet::default();
319 let mut dtorck_types = FxHashSet::default();
321 c.outlives.retain(|&val| outlives.replace(val).is_none());
323 .retain(|&val| dtorck_types.replace(val).is_none());