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.
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.
11 use rustc::infer::canonical::{Canonical, QueryResult};
12 use rustc::hir::def_id::DefId;
13 use rustc::traits::{FulfillmentContext, Normalized, ObligationCause};
14 use rustc::traits::query::{CanonicalTyGoal, NoSolution};
15 use rustc::traits::query::dropck_outlives::{DtorckConstraint, DropckOutlivesResult};
16 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt};
17 use rustc::ty::subst::Subst;
18 use rustc::util::nodemap::FxHashSet;
20 use syntax::codemap::{Span, DUMMY_SP};
23 crate fn dropck_outlives<'tcx>(
24 tcx: TyCtxt<'_, 'tcx, 'tcx>,
25 goal: CanonicalTyGoal<'tcx>,
26 ) -> Result<Rc<Canonical<'tcx, QueryResult<'tcx, DropckOutlivesResult<'tcx>>>>, NoSolution> {
27 debug!("dropck_outlives(goal={:#?})", goal);
29 tcx.infer_ctxt().enter(|ref infcx| {
36 canonical_inference_vars,
37 ) = infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &goal);
39 let mut result = DropckOutlivesResult { kinds: vec![], overflows: vec![] };
41 // A stack of types left to process. Each round, we pop
42 // something from the stack and invoke
43 // `dtorck_constraint_for_ty`. This may produce new types that
44 // have to be pushed on the stack. This continues until we have explored
45 // all the reachable types from the type `for_ty`.
47 // Example: Imagine that we have the following code:
62 // } // here, `a` is dropped
65 // at the point where `a` is dropped, we need to figure out
66 // which types inside of `a` contain region data that may be
67 // accessed by any destructors in `a`. We begin by pushing `A`
68 // onto the stack, as that is the type of `a`. We will then
69 // invoke `dtorck_constraint_for_ty` which will expand `A`
70 // into the types of its fields `(B, Vec<A>)`. These will get
71 // pushed onto the stack. Eventually, expanding `Vec<A>` will
72 // lead to us trying to push `A` a second time -- to prevent
73 // infinite recusion, we notice that `A` was already pushed
75 let mut ty_stack = vec![(for_ty, 0)];
77 // Set used to detect infinite recursion.
78 let mut ty_set = FxHashSet();
80 let fulfill_cx = &mut FulfillmentContext::new();
82 let cause = ObligationCause::dummy();
83 while let Some((ty, depth)) = ty_stack.pop() {
84 let DtorckConstraint {
88 } = dtorck_constraint_for_ty(tcx, DUMMY_SP, for_ty, depth, ty)?;
90 // "outlives" represent types/regions that may be touched
92 result.kinds.extend(outlives);
93 result.overflows.extend(overflows);
95 // dtorck types are "types that will get dropped but which
96 // do not themselves define a destructor", more or less. We have
97 // to push them onto the stack to be expanded.
98 for ty in dtorck_types {
99 match infcx.at(&cause, param_env).normalize(&ty) {
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
111 ty::TyParam(..) => {}
113 // A projection that we couldn't resolve - it
114 // might have a destructor.
115 ty::TyProjection(..) | ty::TyAnon(..) => {
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 util::make_query_response(infcx, canonical_inference_vars, result, fulfill_cx)
142 /// Return a set of constraints that needs to be satisfied in
143 /// order for `ty` to be valid for destruction.
144 fn dtorck_constraint_for_ty<'a, 'gcx, 'tcx>(
145 tcx: TyCtxt<'a, 'gcx, 'tcx>,
150 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
152 "dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})",
153 span, for_ty, depth, ty
156 if depth >= tcx.sess.recursion_limit.get() {
157 return Ok(DtorckConstraint {
159 dtorck_types: vec![],
164 let result = match ty.sty {
177 | ty::TyGeneratorWitness(..) => {
178 // these types never have a destructor
179 Ok(DtorckConstraint::empty())
182 ty::TyArray(ety, _) | ty::TySlice(ety) => {
183 // single-element containers, behave like their element
184 dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ety)
187 ty::TyTuple(tys, _) => tys.iter()
188 .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
191 ty::TyClosure(def_id, substs) => substs
192 .upvar_tys(def_id, tcx)
193 .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
196 ty::TyGenerator(def_id, substs, _) => {
197 // Note that the interior types are ignored here.
198 // Any type reachable inside the interior must also be reachable
199 // through the upvars.
201 .upvar_tys(def_id, tcx)
202 .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty))
206 ty::TyAdt(def, substs) => {
207 let DtorckConstraint {
211 } = tcx.at(span).adt_dtorck_constraint(def.did)?;
212 Ok(DtorckConstraint {
213 // FIXME: we can try to recursively `dtorck_constraint_on_ty`
214 // there, but that needs some way to handle cycles.
215 dtorck_types: dtorck_types.subst(tcx, substs),
216 outlives: outlives.subst(tcx, substs),
217 overflows: overflows.subst(tcx, substs),
221 // Objects must be alive in order for their destructor
223 ty::TyDynamic(..) => Ok(DtorckConstraint {
224 outlives: vec![ty.into()],
225 dtorck_types: vec![],
229 // Types that can't be resolved. Pass them forward.
230 ty::TyProjection(..) | ty::TyAnon(..) | ty::TyParam(..) => Ok(DtorckConstraint {
232 dtorck_types: vec![ty],
236 ty::TyInfer(..) | ty::TyError => {
237 // By the time this code runs, all type variables ought to
238 // be fully resolved.
243 debug!("dtorck_constraint_for_ty({:?}) = {:?}", ty, result);
247 /// Calculates the dtorck constraint for a type.
248 crate fn adt_dtorck_constraint<'a, 'tcx>(
249 tcx: TyCtxt<'a, 'tcx, 'tcx>,
251 ) -> Result<DtorckConstraint<'tcx>, NoSolution> {
252 let def = tcx.adt_def(def_id);
253 let span = tcx.def_span(def_id);
254 debug!("dtorck_constraint: {:?}", def);
256 if def.is_phantom_data() {
257 let result = DtorckConstraint {
259 dtorck_types: vec![tcx.mk_param_from_def(&tcx.generics_of(def_id).types[0])],
262 debug!("dtorck_constraint: {:?} => {:?}", def, result);
266 let mut result = def.all_fields()
267 .map(|field| tcx.type_of(field.did))
268 .map(|fty| dtorck_constraint_for_ty(tcx, span, fty, 0, fty))
269 .collect::<Result<DtorckConstraint, NoSolution>>()?;
270 result.outlives.extend(tcx.destructor_constraints(def));
271 dedup_dtorck_constraint(&mut result);
273 debug!("dtorck_constraint: {:?} => {:?}", def, result);
278 fn dedup_dtorck_constraint<'tcx>(c: &mut DtorckConstraint<'tcx>) {
279 let mut outlives = FxHashSet();
280 let mut dtorck_types = FxHashSet();
282 c.outlives.retain(|&val| outlives.replace(val).is_none());
284 .retain(|&val| dtorck_types.replace(val).is_none());