1 use smallvec
::smallvec
;
3 use crate::traits
::{Obligation, ObligationCause, PredicateObligation}
;
4 use rustc_data_structures
::fx
::FxHashSet
;
5 use rustc_middle
::ty
::outlives
::Component
;
6 use rustc_middle
::ty
::{self, ToPolyTraitRef, ToPredicate, TyCtxt, WithConstness}
;
9 pub fn anonymize_predicate
<'tcx
>(
11 pred
: &ty
::Predicate
<'tcx
>,
12 ) -> ty
::Predicate
<'tcx
> {
14 ty
::Predicate
::Trait(ref data
, constness
) => {
15 ty
::Predicate
::Trait(tcx
.anonymize_late_bound_regions(data
), constness
)
18 ty
::Predicate
::RegionOutlives(ref data
) => {
19 ty
::Predicate
::RegionOutlives(tcx
.anonymize_late_bound_regions(data
))
22 ty
::Predicate
::TypeOutlives(ref data
) => {
23 ty
::Predicate
::TypeOutlives(tcx
.anonymize_late_bound_regions(data
))
26 ty
::Predicate
::Projection(ref data
) => {
27 ty
::Predicate
::Projection(tcx
.anonymize_late_bound_regions(data
))
30 ty
::Predicate
::WellFormed(data
) => ty
::Predicate
::WellFormed(data
),
32 ty
::Predicate
::ObjectSafe(data
) => ty
::Predicate
::ObjectSafe(data
),
34 ty
::Predicate
::ClosureKind(closure_def_id
, closure_substs
, kind
) => {
35 ty
::Predicate
::ClosureKind(closure_def_id
, closure_substs
, kind
)
38 ty
::Predicate
::Subtype(ref data
) => {
39 ty
::Predicate
::Subtype(tcx
.anonymize_late_bound_regions(data
))
42 ty
::Predicate
::ConstEvaluatable(def_id
, substs
) => {
43 ty
::Predicate
::ConstEvaluatable(def_id
, substs
)
48 struct PredicateSet
<'tcx
> {
50 set
: FxHashSet
<ty
::Predicate
<'tcx
>>,
53 impl PredicateSet
<'tcx
> {
54 fn new(tcx
: TyCtxt
<'tcx
>) -> Self {
55 Self { tcx, set: Default::default() }
58 fn insert(&mut self, pred
: &ty
::Predicate
<'tcx
>) -> bool
{
59 // We have to be careful here because we want
61 // for<'a> Foo<&'a int>
65 // for<'b> Foo<&'b int>
67 // to be considered equivalent. So normalize all late-bound
68 // regions before we throw things into the underlying set.
69 self.set
.insert(anonymize_predicate(self.tcx
, pred
))
73 impl<T
: AsRef
<ty
::Predicate
<'tcx
>>> Extend
<T
> for PredicateSet
<'tcx
> {
74 fn extend
<I
: IntoIterator
<Item
= T
>>(&mut self, iter
: I
) {
76 self.insert(pred
.as_ref());
81 ///////////////////////////////////////////////////////////////////////////
82 // `Elaboration` iterator
83 ///////////////////////////////////////////////////////////////////////////
85 /// "Elaboration" is the process of identifying all the predicates that
86 /// are implied by a source predicate. Currently, this basically means
87 /// walking the "supertraits" and other similar assumptions. For example,
88 /// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd`
89 /// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that
90 /// `T: Foo`, then we know that `T: 'static`.
91 pub struct Elaborator
<'tcx
> {
92 stack
: Vec
<PredicateObligation
<'tcx
>>,
93 visited
: PredicateSet
<'tcx
>,
96 pub fn elaborate_trait_ref
<'tcx
>(
98 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
99 ) -> Elaborator
<'tcx
> {
100 elaborate_predicates(tcx
, std
::iter
::once(trait_ref
.without_const().to_predicate()))
103 pub fn elaborate_trait_refs
<'tcx
>(
105 trait_refs
: impl Iterator
<Item
= ty
::PolyTraitRef
<'tcx
>>,
106 ) -> Elaborator
<'tcx
> {
107 let predicates
= trait_refs
.map(|trait_ref
| trait_ref
.without_const().to_predicate());
108 elaborate_predicates(tcx
, predicates
)
111 pub fn elaborate_predicates
<'tcx
>(
113 predicates
: impl IntoIterator
<Item
= ty
::Predicate
<'tcx
>>,
114 ) -> Elaborator
<'tcx
> {
116 predicates
.into_iter().map(|predicate
| predicate_obligation(predicate
, None
)).collect();
117 elaborate_obligations(tcx
, obligations
)
120 pub fn elaborate_obligations
<'tcx
>(
122 mut obligations
: Vec
<PredicateObligation
<'tcx
>>,
123 ) -> Elaborator
<'tcx
> {
124 let mut visited
= PredicateSet
::new(tcx
);
125 obligations
.retain(|obligation
| visited
.insert(&obligation
.predicate
));
126 Elaborator { stack: obligations, visited }
129 fn predicate_obligation
<'tcx
>(
130 predicate
: ty
::Predicate
<'tcx
>,
132 ) -> PredicateObligation
<'tcx
> {
133 let mut cause
= ObligationCause
::dummy();
134 if let Some(span
) = span
{
137 Obligation { cause, param_env: ty::ParamEnv::empty(), recursion_depth: 0, predicate }
140 impl Elaborator
<'tcx
> {
141 pub fn filter_to_traits(self) -> FilterToTraits
<Self> {
142 FilterToTraits
::new(self)
145 fn elaborate(&mut self, obligation
: &PredicateObligation
<'tcx
>) {
146 let tcx
= self.visited
.tcx
;
147 match obligation
.predicate
{
148 ty
::Predicate
::Trait(ref data
, _
) => {
149 // Get predicates declared on the trait.
150 let predicates
= tcx
.super_predicates_of(data
.def_id());
152 let obligations
= predicates
.predicates
.into_iter().map(|(pred
, span
)| {
153 predicate_obligation(
154 pred
.subst_supertrait(tcx
, &data
.to_poly_trait_ref()),
158 debug
!("super_predicates: data={:?}", data
);
160 // Only keep those bounds that we haven't already seen.
161 // This is necessary to prevent infinite recursion in some
162 // cases. One common case is when people define
163 // `trait Sized: Sized { }` rather than `trait Sized { }`.
164 let visited
= &mut self.visited
;
165 let obligations
= obligations
.filter(|o
| visited
.insert(&o
.predicate
));
167 self.stack
.extend(obligations
);
169 ty
::Predicate
::WellFormed(..) => {
170 // Currently, we do not elaborate WF predicates,
171 // although we easily could.
173 ty
::Predicate
::ObjectSafe(..) => {
174 // Currently, we do not elaborate object-safe
177 ty
::Predicate
::Subtype(..) => {
178 // Currently, we do not "elaborate" predicates like `X <: Y`,
179 // though conceivably we might.
181 ty
::Predicate
::Projection(..) => {
182 // Nothing to elaborate in a projection predicate.
184 ty
::Predicate
::ClosureKind(..) => {
185 // Nothing to elaborate when waiting for a closure's kind to be inferred.
187 ty
::Predicate
::ConstEvaluatable(..) => {
188 // Currently, we do not elaborate const-evaluatable
191 ty
::Predicate
::RegionOutlives(..) => {
192 // Nothing to elaborate from `'a: 'b`.
194 ty
::Predicate
::TypeOutlives(ref data
) => {
195 // We know that `T: 'a` for some type `T`. We can
196 // often elaborate this. For example, if we know that
197 // `[U]: 'a`, that implies that `U: 'a`. Similarly, if
198 // we know `&'a U: 'b`, then we know that `'a: 'b` and
201 // We can basically ignore bound regions here. So for
202 // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to
205 // Ignore `for<'a> T: 'a` -- we might in the future
206 // consider this as evidence that `T: 'static`, but
207 // I'm a bit wary of such constructions and so for now
208 // I want to be conservative. --nmatsakis
209 let ty_max
= data
.skip_binder().0;
210 let r_min
= data
.skip_binder().1;
211 if r_min
.is_late_bound() {
215 let visited
= &mut self.visited
;
216 let mut components
= smallvec
![];
217 tcx
.push_outlives_components(ty_max
, &mut components
);
221 .filter_map(|component
| match component
{
222 Component
::Region(r
) => {
223 if r
.is_late_bound() {
226 Some(ty
::Predicate
::RegionOutlives(ty
::Binder
::dummy(
227 ty
::OutlivesPredicate(r
, r_min
),
232 Component
::Param(p
) => {
233 let ty
= tcx
.mk_ty_param(p
.index
, p
.name
);
234 Some(ty
::Predicate
::TypeOutlives(ty
::Binder
::dummy(
235 ty
::OutlivesPredicate(ty
, r_min
),
239 Component
::UnresolvedInferenceVariable(_
) => None
,
241 Component
::Projection(_
) | Component
::EscapingProjection(_
) => {
242 // We can probably do more here. This
243 // corresponds to a case like `<T as
248 .filter(|p
| visited
.insert(p
))
249 .map(|p
| predicate_obligation(p
, None
)),
256 impl Iterator
for Elaborator
<'tcx
> {
257 type Item
= PredicateObligation
<'tcx
>;
259 fn size_hint(&self) -> (usize, Option
<usize>) {
260 (self.stack
.len(), None
)
263 fn next(&mut self) -> Option
<Self::Item
> {
264 // Extract next item from top-most stack frame, if any.
265 if let Some(obligation
) = self.stack
.pop() {
266 self.elaborate(&obligation
);
274 ///////////////////////////////////////////////////////////////////////////
275 // Supertrait iterator
276 ///////////////////////////////////////////////////////////////////////////
278 pub type Supertraits
<'tcx
> = FilterToTraits
<Elaborator
<'tcx
>>;
280 pub fn supertraits
<'tcx
>(
282 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
283 ) -> Supertraits
<'tcx
> {
284 elaborate_trait_ref(tcx
, trait_ref
).filter_to_traits()
287 pub fn transitive_bounds
<'tcx
>(
289 bounds
: impl Iterator
<Item
= ty
::PolyTraitRef
<'tcx
>>,
290 ) -> Supertraits
<'tcx
> {
291 elaborate_trait_refs(tcx
, bounds
).filter_to_traits()
294 ///////////////////////////////////////////////////////////////////////////
296 ///////////////////////////////////////////////////////////////////////////
298 /// A filter around an iterator of predicates that makes it yield up
299 /// just trait references.
300 pub struct FilterToTraits
<I
> {
304 impl<I
> FilterToTraits
<I
> {
305 fn new(base
: I
) -> FilterToTraits
<I
> {
306 FilterToTraits { base_iterator: base }
310 impl<'tcx
, I
: Iterator
<Item
= PredicateObligation
<'tcx
>>> Iterator
for FilterToTraits
<I
> {
311 type Item
= ty
::PolyTraitRef
<'tcx
>;
313 fn next(&mut self) -> Option
<ty
::PolyTraitRef
<'tcx
>> {
314 while let Some(obligation
) = self.base_iterator
.next() {
315 if let ty
::Predicate
::Trait(data
, _
) = obligation
.predicate
{
316 return Some(data
.to_poly_trait_ref());
322 fn size_hint(&self) -> (usize, Option
<usize>) {
323 let (_
, upper
) = self.base_iterator
.size_hint();