1 use smallvec::smallvec;
3 use rustc::ty::outlives::Component;
4 use rustc::ty::{self, ToPolyTraitRef, TyCtxt};
5 use rustc_data_structures::fx::FxHashSet;
7 fn anonymize_predicate<'tcx>(tcx: TyCtxt<'tcx>, pred: &ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
9 ty::Predicate::Trait(ref data, constness) => {
10 ty::Predicate::Trait(tcx.anonymize_late_bound_regions(data), constness)
13 ty::Predicate::RegionOutlives(ref data) => {
14 ty::Predicate::RegionOutlives(tcx.anonymize_late_bound_regions(data))
17 ty::Predicate::TypeOutlives(ref data) => {
18 ty::Predicate::TypeOutlives(tcx.anonymize_late_bound_regions(data))
21 ty::Predicate::Projection(ref data) => {
22 ty::Predicate::Projection(tcx.anonymize_late_bound_regions(data))
25 ty::Predicate::WellFormed(data) => ty::Predicate::WellFormed(data),
27 ty::Predicate::ObjectSafe(data) => ty::Predicate::ObjectSafe(data),
29 ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => {
30 ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind)
33 ty::Predicate::Subtype(ref data) => {
34 ty::Predicate::Subtype(tcx.anonymize_late_bound_regions(data))
37 ty::Predicate::ConstEvaluatable(def_id, substs) => {
38 ty::Predicate::ConstEvaluatable(def_id, substs)
43 struct PredicateSet<'tcx> {
45 set: FxHashSet<ty::Predicate<'tcx>>,
48 impl PredicateSet<'tcx> {
49 fn new(tcx: TyCtxt<'tcx>) -> Self {
50 Self { tcx: tcx, set: Default::default() }
53 fn insert(&mut self, pred: &ty::Predicate<'tcx>) -> bool {
54 // We have to be careful here because we want
56 // for<'a> Foo<&'a int>
60 // for<'b> Foo<&'b int>
62 // to be considered equivalent. So normalize all late-bound
63 // regions before we throw things into the underlying set.
64 self.set.insert(anonymize_predicate(self.tcx, pred))
68 impl<T: AsRef<ty::Predicate<'tcx>>> Extend<T> for PredicateSet<'tcx> {
69 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
71 self.insert(pred.as_ref());
76 ///////////////////////////////////////////////////////////////////////////
77 // `Elaboration` iterator
78 ///////////////////////////////////////////////////////////////////////////
80 /// "Elaboration" is the process of identifying all the predicates that
81 /// are implied by a source predicate. Currently, this basically means
82 /// walking the "supertraits" and other similar assumptions. For example,
83 /// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd`
84 /// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that
85 /// `T: Foo`, then we know that `T: 'static`.
86 pub struct Elaborator<'tcx> {
87 stack: Vec<ty::Predicate<'tcx>>,
88 visited: PredicateSet<'tcx>,
91 pub fn elaborate_predicates<'tcx>(
93 mut predicates: Vec<ty::Predicate<'tcx>>,
94 ) -> Elaborator<'tcx> {
95 let mut visited = PredicateSet::new(tcx);
96 predicates.retain(|pred| visited.insert(pred));
97 Elaborator { stack: predicates, visited }
100 impl Elaborator<'tcx> {
101 fn elaborate(&mut self, predicate: &ty::Predicate<'tcx>) {
102 let tcx = self.visited.tcx;
104 ty::Predicate::Trait(ref data, _) => {
105 // Get predicates declared on the trait.
106 let predicates = tcx.super_predicates_of(data.def_id());
108 let predicates = predicates
111 .map(|(pred, _)| pred.subst_supertrait(tcx, &data.to_poly_trait_ref()));
112 debug!("super_predicates: data={:?} predicates={:?}", data, predicates.clone());
114 // Only keep those bounds that we haven't already seen.
115 // This is necessary to prevent infinite recursion in some
116 // cases. One common case is when people define
117 // `trait Sized: Sized { }` rather than `trait Sized { }`.
118 let visited = &mut self.visited;
119 let predicates = predicates.filter(|pred| visited.insert(pred));
121 self.stack.extend(predicates);
123 ty::Predicate::WellFormed(..) => {
124 // Currently, we do not elaborate WF predicates,
125 // although we easily could.
127 ty::Predicate::ObjectSafe(..) => {
128 // Currently, we do not elaborate object-safe
131 ty::Predicate::Subtype(..) => {
132 // Currently, we do not "elaborate" predicates like `X <: Y`,
133 // though conceivably we might.
135 ty::Predicate::Projection(..) => {
136 // Nothing to elaborate in a projection predicate.
138 ty::Predicate::ClosureKind(..) => {
139 // Nothing to elaborate when waiting for a closure's kind to be inferred.
141 ty::Predicate::ConstEvaluatable(..) => {
142 // Currently, we do not elaborate const-evaluatable
145 ty::Predicate::RegionOutlives(..) => {
146 // Nothing to elaborate from `'a: 'b`.
148 ty::Predicate::TypeOutlives(ref data) => {
149 // We know that `T: 'a` for some type `T`. We can
150 // often elaborate this. For example, if we know that
151 // `[U]: 'a`, that implies that `U: 'a`. Similarly, if
152 // we know `&'a U: 'b`, then we know that `'a: 'b` and
155 // We can basically ignore bound regions here. So for
156 // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to
159 // Ignore `for<'a> T: 'a` -- we might in the future
160 // consider this as evidence that `T: 'static`, but
161 // I'm a bit wary of such constructions and so for now
162 // I want to be conservative. --nmatsakis
163 let ty_max = data.skip_binder().0;
164 let r_min = data.skip_binder().1;
165 if r_min.is_late_bound() {
169 let visited = &mut self.visited;
170 let mut components = smallvec![];
171 tcx.push_outlives_components(ty_max, &mut components);
175 .filter_map(|component| match component {
176 Component::Region(r) => {
177 if r.is_late_bound() {
180 Some(ty::Predicate::RegionOutlives(ty::Binder::dummy(
181 ty::OutlivesPredicate(r, r_min),
186 Component::Param(p) => {
187 let ty = tcx.mk_ty_param(p.index, p.name);
188 Some(ty::Predicate::TypeOutlives(ty::Binder::dummy(
189 ty::OutlivesPredicate(ty, r_min),
193 Component::UnresolvedInferenceVariable(_) => None,
195 Component::Projection(_) | Component::EscapingProjection(_) => {
196 // We can probably do more here. This
197 // corresponds to a case like `<T as
202 .filter(|p| visited.insert(p)),
209 impl Iterator for Elaborator<'tcx> {
210 type Item = ty::Predicate<'tcx>;
212 fn size_hint(&self) -> (usize, Option<usize>) {
213 (self.stack.len(), None)
216 fn next(&mut self) -> Option<ty::Predicate<'tcx>> {
217 // Extract next item from top-most stack frame, if any.
218 if let Some(pred) = self.stack.pop() {
219 self.elaborate(&pred);