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
::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}
;
23 crate fn provide(p
: &mut Providers
) {
26 adt_dtorck_constraint
,
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
);
37 tcx
.infer_ctxt().enter_with_canonical(
40 |ref infcx
, goal
, canonical_inference_vars
| {
47 let mut result
= DropckOutlivesResult
{
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`.
58 // Example: Imagine that we have the following code:
73 // } // here, `a` is dropped
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
86 let mut ty_stack
= vec
![(for_ty
, 0)];
88 // Set used to detect infinite recursion.
89 let mut ty_set
= FxHashSet
::default();
91 let fulfill_cx
= &mut FulfillmentContext
::new();
93 let cause
= ObligationCause
::dummy();
94 while let Some((ty
, depth
)) = ty_stack
.pop() {
95 let DtorckConstraint
{
99 } = dtorck_constraint_for_ty(tcx
, DUMMY_SP
, for_ty
, depth
, ty
)?
;
101 // "outlives" represent types/regions that may be touched
103 result
.kinds
.extend(outlives
);
104 result
.overflows
.extend(overflows
);
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
) {
115 fulfill_cx
.register_predicate_obligations(infcx
, obligations
);
117 debug
!("dropck_outlives: ty from dtorck_types = {:?}", ty
);
120 // All parameters live for the duration of the
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());
131 if ty_set
.insert(ty
) {
132 ty_stack
.push((ty
, depth
+ 1));
138 // We don't actually expect to fail to normalize.
139 // That implies a WF error somewhere else.
141 return Err(NoSolution
);
147 debug
!("dropck_outlives: result = {:#?}", result
);
149 infcx
.make_canonicalized_query_response(canonical_inference_vars
, result
, fulfill_cx
)
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
>,
162 ) -> Result
<DtorckConstraint
<'tcx
>, NoSolution
> {
164 "dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})",
165 span
, for_ty
, depth
, ty
168 if depth
>= *tcx
.sess
.recursion_limit
.get() {
169 return Ok(DtorckConstraint
{
171 dtorck_types
: vec
![],
176 let result
= match ty
.sty
{
189 | ty
::GeneratorWitness(..) => {
190 // these types never have a destructor
191 Ok(DtorckConstraint
::empty())
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
)
199 ty
::Tuple(tys
) => tys
.iter()
200 .map(|ty
| dtorck_constraint_for_ty(tcx
, span
, for_ty
, depth
+ 1, ty
))
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
))
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).
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
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)
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.
232 let constraint
= DtorckConstraint
{
233 outlives
: substs
.upvar_tys(def_id
, tcx
).map(|t
| t
.into()).collect(),
234 dtorck_types
: vec
![],
238 "dtorck_constraint: generator {:?} => {:?}",
245 ty
::Adt(def
, substs
) => {
246 let DtorckConstraint
{
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
),
260 // Objects must be alive in order for their destructor
262 ty
::Dynamic(..) => Ok(DtorckConstraint
{
263 outlives
: vec
![ty
.into()],
264 dtorck_types
: vec
![],
268 // Types that can't be resolved. Pass them forward.
269 ty
::Projection(..) | ty
::Opaque(..) | ty
::Param(..) => Ok(DtorckConstraint
{
271 dtorck_types
: vec
![ty
],
275 ty
::UnnormalizedProjection(..) => bug
!("only used with chalk-engine"),
277 ty
::Infer(..) | ty
::Error
=> {
278 // By the time this code runs, all type variables ought to
279 // be fully resolved.
284 debug
!("dtorck_constraint_for_ty({:?}) = {:?}", ty
, result
);
288 /// Calculates the dtorck constraint for a type.
289 crate fn adt_dtorck_constraint
<'a
, 'tcx
>(
290 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
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
);
297 if def
.is_phantom_data() {
298 // The first generic parameter here is guaranteed to be a type because it's
300 let substs
= Substs
::identity_for_item(tcx
, def_id
);
301 assert_eq
!(substs
.len(), 1);
302 let result
= DtorckConstraint
{
304 dtorck_types
: vec
![substs
.type_at(0)],
307 debug
!("dtorck_constraint: {:?} => {:?}", def
, result
);
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
);
318 debug
!("dtorck_constraint: {:?} => {:?}", def
, result
);
323 fn dedup_dtorck_constraint
<'tcx
>(c
: &mut DtorckConstraint
<'tcx
>) {
324 let mut outlives
= FxHashSet
::default();
325 let mut dtorck_types
= FxHashSet
::default();
327 c
.outlives
.retain(|&val
| outlives
.replace(val
).is_none());
329 .retain(|&val
| dtorck_types
.replace(val
).is_none());