src/librustc_infer/traits/util.rs

   1 use smallvec::smallvec;
   2
   3 use rustc::ty::outlives::Component;
   4 use rustc::ty::{self, ToPolyTraitRef, TyCtxt};
   5 use rustc_data_structures::fx::FxHashSet;
   6
   7 fn anonymize_predicate<'tcx>(tcx: TyCtxt<'tcx>, pred: &ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
   8     match *pred {
   9         ty::Predicate::Trait(ref data, constness) => {
  10             ty::Predicate::Trait(tcx.anonymize_late_bound_regions(data), constness)
  11         }
  12
  13         ty::Predicate::RegionOutlives(ref data) => {
  14             ty::Predicate::RegionOutlives(tcx.anonymize_late_bound_regions(data))
  15         }
  16
  17         ty::Predicate::TypeOutlives(ref data) => {
  18             ty::Predicate::TypeOutlives(tcx.anonymize_late_bound_regions(data))
  19         }
  20
  21         ty::Predicate::Projection(ref data) => {
  22             ty::Predicate::Projection(tcx.anonymize_late_bound_regions(data))
  23         }
  24
  25         ty::Predicate::WellFormed(data) => ty::Predicate::WellFormed(data),
  26
  27         ty::Predicate::ObjectSafe(data) => ty::Predicate::ObjectSafe(data),
  28
  29         ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => {
  30             ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind)
  31         }
  32
  33         ty::Predicate::Subtype(ref data) => {
  34             ty::Predicate::Subtype(tcx.anonymize_late_bound_regions(data))
  35         }
  36
  37         ty::Predicate::ConstEvaluatable(def_id, substs) => {
  38             ty::Predicate::ConstEvaluatable(def_id, substs)
  39         }
  40     }
  41 }
  42
  43 struct PredicateSet<'tcx> {
  44     tcx: TyCtxt<'tcx>,
  45     set: FxHashSet<ty::Predicate<'tcx>>,
  46 }
  47
  48 impl PredicateSet<'tcx> {
  49     fn new(tcx: TyCtxt<'tcx>) -> Self {
  50         Self { tcx: tcx, set: Default::default() }
  51     }
  52
  53     fn insert(&mut self, pred: &ty::Predicate<'tcx>) -> bool {
  54         // We have to be careful here because we want
  55         //
  56         //    for<'a> Foo<&'a int>
  57         //
  58         // and
  59         //
  60         //    for<'b> Foo<&'b int>
  61         //
  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))
  65     }
  66 }
  67
  68 impl<T: AsRef<ty::Predicate<'tcx>>> Extend<T> for PredicateSet<'tcx> {
  69     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
  70         for pred in iter {
  71             self.insert(pred.as_ref());
  72         }
  73     }
  74 }
  75
  76 ///////////////////////////////////////////////////////////////////////////
  77 // `Elaboration` iterator
  78 ///////////////////////////////////////////////////////////////////////////
  79
  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>,
  89 }
  90
  91 pub fn elaborate_predicates<'tcx>(
  92     tcx: TyCtxt<'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 }
  98 }
  99
 100 impl Elaborator<'tcx> {
 101     fn elaborate(&mut self, predicate: &ty::Predicate<'tcx>) {
 102         let tcx = self.visited.tcx;
 103         match *predicate {
 104             ty::Predicate::Trait(ref data, _) => {
 105                 // Get predicates declared on the trait.
 106                 let predicates = tcx.super_predicates_of(data.def_id());
 107
 108                 let predicates = predicates
 109                     .predicates
 110                     .iter()
 111                     .map(|(pred, _)| pred.subst_supertrait(tcx, &data.to_poly_trait_ref()));
 112                 debug!("super_predicates: data={:?} predicates={:?}", data, predicates.clone());
 113
 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));
 120
 121                 self.stack.extend(predicates);
 122             }
 123             ty::Predicate::WellFormed(..) => {
 124                 // Currently, we do not elaborate WF predicates,
 125                 // although we easily could.
 126             }
 127             ty::Predicate::ObjectSafe(..) => {
 128                 // Currently, we do not elaborate object-safe
 129                 // predicates.
 130             }
 131             ty::Predicate::Subtype(..) => {
 132                 // Currently, we do not "elaborate" predicates like `X <: Y`,
 133                 // though conceivably we might.
 134             }
 135             ty::Predicate::Projection(..) => {
 136                 // Nothing to elaborate in a projection predicate.
 137             }
 138             ty::Predicate::ClosureKind(..) => {
 139                 // Nothing to elaborate when waiting for a closure's kind to be inferred.
 140             }
 141             ty::Predicate::ConstEvaluatable(..) => {
 142                 // Currently, we do not elaborate const-evaluatable
 143                 // predicates.
 144             }
 145             ty::Predicate::RegionOutlives(..) => {
 146                 // Nothing to elaborate from `'a: 'b`.
 147             }
 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
 153                 // `U: 'b`.
 154                 //
 155                 // We can basically ignore bound regions here. So for
 156                 // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to
 157                 // `'a: 'b`.
 158
 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() {
 166                     return;
 167                 }
 168
 169                 let visited = &mut self.visited;
 170                 let mut components = smallvec![];
 171                 tcx.push_outlives_components(ty_max, &mut components);
 172                 self.stack.extend(
 173                     components
 174                         .into_iter()
 175                         .filter_map(|component| match component {
 176                             Component::Region(r) => {
 177                                 if r.is_late_bound() {
 178                                     None
 179                                 } else {
 180                                     Some(ty::Predicate::RegionOutlives(ty::Binder::dummy(
 181                                         ty::OutlivesPredicate(r, r_min),
 182                                     )))
 183                                 }
 184                             }
 185
 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),
 190                                 )))
 191                             }
 192
 193                             Component::UnresolvedInferenceVariable(_) => None,
 194
 195                             Component::Projection(_) | Component::EscapingProjection(_) => {
 196                                 // We can probably do more here. This
 197                                 // corresponds to a case like `<T as
 198                                 // Foo<'a>>::U: 'b`.
 199                                 None
 200                             }
 201                         })
 202                         .filter(|p| visited.insert(p)),
 203                 );
 204             }
 205         }
 206     }
 207 }
 208
 209 impl Iterator for Elaborator<'tcx> {
 210     type Item = ty::Predicate<'tcx>;
 211
 212     fn size_hint(&self) -> (usize, Option<usize>) {
 213         (self.stack.len(), None)
 214     }
 215
 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);
 220             Some(pred)
 221         } else {
 222             None
 223         }
 224     }
 225 }