1 use rustc::infer::canonical::{Canonical, QueryResponse};
2 use rustc::traits::query::dropck_outlives::trivial_dropck_outlives;
3 use rustc::traits::query::dropck_outlives::{DropckOutlivesResult, DtorckConstraint};
4 use rustc::traits::query::{CanonicalTyGoal, NoSolution};
5 use rustc::traits::{Normalized, ObligationCause, TraitEngine, TraitEngineExt};
6 use rustc::ty::query::Providers;
7 use rustc::ty::subst::{InternalSubsts, Subst};
8 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt};
9 use rustc_data_structures::fx::FxHashSet;
10 use rustc_hir::def_id::DefId;
11 use rustc_span::source_map::{Span, DUMMY_SP};
13 crate fn provide(p: &mut Providers<'_>) {
14 *p = Providers { dropck_outlives, adt_dtorck_constraint, ..*p };
17 fn dropck_outlives<'tcx>(
19 canonical_goal: CanonicalTyGoal<'tcx>,
20 ) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>, NoSolution> {
21 debug!("dropck_outlives(goal={:#?})", canonical_goal);
23 tcx.infer_ctxt().enter_with_canonical(
26 |ref infcx, goal, canonical_inference_vars| {
28 let ParamEnvAnd { param_env, value: for_ty } = goal;
30 let mut result = DropckOutlivesResult { kinds: vec![], overflows: vec![] };
32 // A stack of types left to process. Each round, we pop
33 // something from the stack and invoke
34 // `dtorck_constraint_for_ty`. This may produce new types that
35 // have to be pushed on the stack. This continues until we have explored
36 // all the reachable types from the type `for_ty`.
38 // Example: Imagine that we have the following code:
53 // } // here, `a` is dropped
56 // at the point where `a` is dropped, we need to figure out
57 // which types inside of `a` contain region data that may be
58 // accessed by any destructors in `a`. We begin by pushing `A`
59 // onto the stack, as that is the type of `a`. We will then
60 // invoke `dtorck_constraint_for_ty` which will expand `A`
61 // into the types of its fields `(B, Vec<A>)`. These will get
62 // pushed onto the stack. Eventually, expanding `Vec<A>` will
63 // lead to us trying to push `A` a second time -- to prevent
64 // infinite recursion, we notice that `A` was already pushed
66 let mut ty_stack = vec![(for_ty, 0)];
68 // Set used to detect infinite recursion.
69 let mut ty_set = FxHashSet::default();
71 let mut fulfill_cx = TraitEngine::new(infcx.tcx);
73 let cause = ObligationCause::dummy();
74 let mut constraints = DtorckConstraint::empty();
75 while let Some((ty, depth)) = ty_stack.pop() {
77 "{} kinds, {} overflows, {} ty_stack",
79 result.overflows.len(),
82 dtorck_constraint_for_ty(tcx, DUMMY_SP, for_ty, depth, ty, &mut constraints)?;
84 // "outlives" represent types/regions that may be touched
86 result.kinds.extend(constraints.outlives.drain(..));
87 result.overflows.extend(constraints.overflows.drain(..));
89 // If we have even one overflow, we should stop trying to evaluate further --
90 // chances are, the subsequent overflows for this evaluation won't provide useful
91 // information and will just decrease the speed at which we can emit these errors
92 // (since we'll be printing for just that much longer for the often enormous types
94 if result.overflows.len() >= 1 {
98 // dtorck types are "types that will get dropped but which
99 // do not themselves define a destructor", more or less. We have
100 // to push them onto the stack to be expanded.
101 for ty in constraints.dtorck_types.drain(..) {
102 match infcx.at(&cause, param_env).normalize(&ty) {
103 Ok(Normalized { value: ty, obligations }) => {
104 fulfill_cx.register_predicate_obligations(infcx, obligations);
106 debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
109 // All parameters live for the duration of the
113 // A projection that we couldn't resolve - it
114 // might have a destructor.
115 ty::Projection(..) | ty::Opaque(..) => {
116 result.kinds.push(ty.into());
120 if ty_set.insert(ty) {
121 ty_stack.push((ty, depth + 1));
127 // We don't actually expect to fail to normalize.
128 // That implies a WF error somewhere else.
130 return Err(NoSolution);
136 debug!("dropck_outlives: result = {:#?}", result);
138 infcx.make_canonicalized_query_response(
139 canonical_inference_vars,
147 /// Returns a set of constraints that needs to be satisfied in
148 /// order for `ty` to be valid for destruction.
149 fn dtorck_constraint_for_ty<'tcx>(
155 constraints: &mut DtorckConstraint<'tcx>,
156 ) -> Result<(), NoSolution> {
157 debug!("dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})", span, for_ty, depth, ty);
159 if depth >= *tcx.sess.recursion_limit.get() {
160 constraints.overflows.push(ty);
164 if trivial_dropck_outlives(tcx, ty) {
181 | ty::GeneratorWitness(..) => {
182 // these types never have a destructor
185 ty::Array(ety, _) | ty::Slice(ety) => {
186 // single-element containers, behave like their element
187 dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ety, constraints)?;
191 for ty in tys.iter() {
192 dtorck_constraint_for_ty(
203 ty::Closure(def_id, substs) => {
204 for ty in substs.as_closure().upvar_tys(def_id, tcx) {
205 dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty, constraints)?;
209 ty::Generator(def_id, substs, _movability) => {
210 // rust-lang/rust#49918: types can be constructed, stored
211 // in the interior, and sit idle when generator yields
212 // (and is subsequently dropped).
214 // It would be nice to descend into interior of a
215 // generator to determine what effects dropping it might
216 // have (by looking at any drop effects associated with
219 // However, the interior's representation uses things like
220 // GeneratorWitness that explicitly assume they are not
221 // traversed in such a manner. So instead, we will
222 // simplify things for now by treating all generators as
223 // if they were like trait objects, where its upvars must
224 // all be alive for the generator's (potential)
227 // In particular, skipping over `_interior` is safe
228 // because any side-effects from dropping `_interior` can
229 // only take place through references with lifetimes
230 // derived from lifetimes attached to the upvars, and we
231 // *do* incorporate the upvars here.
233 constraints.outlives.extend(
236 .upvar_tys(def_id, tcx)
237 .map(|t| -> ty::subst::GenericArg<'tcx> { t.into() }),
241 ty::Adt(def, substs) => {
242 let DtorckConstraint { dtorck_types, outlives, overflows } =
243 tcx.at(span).adt_dtorck_constraint(def.did)?;
244 // FIXME: we can try to recursively `dtorck_constraint_on_ty`
245 // there, but that needs some way to handle cycles.
246 constraints.dtorck_types.extend(dtorck_types.subst(tcx, substs));
247 constraints.outlives.extend(outlives.subst(tcx, substs));
248 constraints.overflows.extend(overflows.subst(tcx, substs));
251 // Objects must be alive in order for their destructor
254 constraints.outlives.push(ty.into());
257 // Types that can't be resolved. Pass them forward.
258 ty::Projection(..) | ty::Opaque(..) | ty::Param(..) => {
259 constraints.dtorck_types.push(ty);
262 ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
264 ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error => {
265 // By the time this code runs, all type variables ought to
266 // be fully resolved.
267 return Err(NoSolution);
274 /// Calculates the dtorck constraint for a type.
275 crate fn adt_dtorck_constraint(
278 ) -> Result<DtorckConstraint<'_>, NoSolution> {
279 let def = tcx.adt_def(def_id);
280 let span = tcx.def_span(def_id);
281 debug!("dtorck_constraint: {:?}", def);
283 if def.is_phantom_data() {
284 // The first generic parameter here is guaranteed to be a type because it's
286 let substs = InternalSubsts::identity_for_item(tcx, def_id);
287 assert_eq!(substs.len(), 1);
288 let result = DtorckConstraint {
290 dtorck_types: vec![substs.type_at(0)],
293 debug!("dtorck_constraint: {:?} => {:?}", def, result);
297 let mut result = DtorckConstraint::empty();
298 for field in def.all_fields() {
299 let fty = tcx.type_of(field.did);
300 dtorck_constraint_for_ty(tcx, span, fty, 0, fty, &mut result)?;
302 result.outlives.extend(tcx.destructor_constraints(def));
303 dedup_dtorck_constraint(&mut result);
305 debug!("dtorck_constraint: {:?} => {:?}", def, result);
310 fn dedup_dtorck_constraint(c: &mut DtorckConstraint<'_>) {
311 let mut outlives = FxHashSet::default();
312 let mut dtorck_types = FxHashSet::default();
314 c.outlives.retain(|&val| outlives.replace(val).is_none());
315 c.dtorck_types.retain(|&val| dtorck_types.replace(val).is_none());