src/librustc/traits/util.rs

   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.
   4 //
   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.
  10
  11 use hir::def_id::DefId;
  12 use ty::subst::{Subst, Substs};
  13 use ty::{self, Ty, TyCtxt, ToPredicate, ToPolyTraitRef};
  14 use ty::outlives::Component;
  15 use util::nodemap::FxHashSet;
  16
  17 use super::{Obligation, ObligationCause, PredicateObligation, SelectionContext, Normalized};
  18
  19 fn anonymize_predicate<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
  20                                        pred: &ty::Predicate<'tcx>)
  21                                        -> ty::Predicate<'tcx> {
  22     match *pred {
  23         ty::Predicate::Trait(ref data) =>
  24             ty::Predicate::Trait(tcx.anonymize_late_bound_regions(data)),
  25
  26         ty::Predicate::Equate(ref data) =>
  27             ty::Predicate::Equate(tcx.anonymize_late_bound_regions(data)),
  28
  29         ty::Predicate::RegionOutlives(ref data) =>
  30             ty::Predicate::RegionOutlives(tcx.anonymize_late_bound_regions(data)),
  31
  32         ty::Predicate::TypeOutlives(ref data) =>
  33             ty::Predicate::TypeOutlives(tcx.anonymize_late_bound_regions(data)),
  34
  35         ty::Predicate::Projection(ref data) =>
  36             ty::Predicate::Projection(tcx.anonymize_late_bound_regions(data)),
  37
  38         ty::Predicate::WellFormed(data) =>
  39             ty::Predicate::WellFormed(data),
  40
  41         ty::Predicate::ObjectSafe(data) =>
  42             ty::Predicate::ObjectSafe(data),
  43
  44         ty::Predicate::ClosureKind(closure_def_id, kind) =>
  45             ty::Predicate::ClosureKind(closure_def_id, kind)
  46     }
  47 }
  48
  49
  50 struct PredicateSet<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  51     tcx: TyCtxt<'a, 'gcx, 'tcx>,
  52     set: FxHashSet<ty::Predicate<'tcx>>,
  53 }
  54
  55 impl<'a, 'gcx, 'tcx> PredicateSet<'a, 'gcx, 'tcx> {
  56     fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> PredicateSet<'a, 'gcx, 'tcx> {
  57         PredicateSet { tcx: tcx, set: FxHashSet() }
  58     }
  59
  60     fn insert(&mut self, pred: &ty::Predicate<'tcx>) -> bool {
  61         // We have to be careful here because we want
  62         //
  63         //    for<'a> Foo<&'a int>
  64         //
  65         // and
  66         //
  67         //    for<'b> Foo<&'b int>
  68         //
  69         // to be considered equivalent. So normalize all late-bound
  70         // regions before we throw things into the underlying set.
  71         self.set.insert(anonymize_predicate(self.tcx, pred))
  72     }
  73 }
  74
  75 ///////////////////////////////////////////////////////////////////////////
  76 // `Elaboration` iterator
  77 ///////////////////////////////////////////////////////////////////////////
  78
  79 /// "Elaboration" is the process of identifying all the predicates that
  80 /// are implied by a source predicate. Currently this basically means
  81 /// walking the "supertraits" and other similar assumptions. For
  82 /// example, if we know that `T : Ord`, the elaborator would deduce
  83 /// that `T : PartialOrd` holds as well. Similarly, if we have `trait
  84 /// Foo : 'static`, and we know that `T : Foo`, then we know that `T :
  85 /// 'static`.
  86 pub struct Elaborator<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  87     stack: Vec<ty::Predicate<'tcx>>,
  88     visited: PredicateSet<'a, 'gcx, 'tcx>,
  89 }
  90
  91 pub fn elaborate_trait_ref<'cx, 'gcx, 'tcx>(
  92     tcx: TyCtxt<'cx, 'gcx, 'tcx>,
  93     trait_ref: ty::PolyTraitRef<'tcx>)
  94     -> Elaborator<'cx, 'gcx, 'tcx>
  95 {
  96     elaborate_predicates(tcx, vec![trait_ref.to_predicate()])
  97 }
  98
  99 pub fn elaborate_trait_refs<'cx, 'gcx, 'tcx>(
 100     tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 101     trait_refs: &[ty::PolyTraitRef<'tcx>])
 102     -> Elaborator<'cx, 'gcx, 'tcx>
 103 {
 104     let predicates = trait_refs.iter()
 105                                .map(|trait_ref| trait_ref.to_predicate())
 106                                .collect();
 107     elaborate_predicates(tcx, predicates)
 108 }
 109
 110 pub fn elaborate_predicates<'cx, 'gcx, 'tcx>(
 111     tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 112     mut predicates: Vec<ty::Predicate<'tcx>>)
 113     -> Elaborator<'cx, 'gcx, 'tcx>
 114 {
 115     let mut visited = PredicateSet::new(tcx);
 116     predicates.retain(|pred| visited.insert(pred));
 117     Elaborator { stack: predicates, visited: visited }
 118 }
 119
 120 impl<'cx, 'gcx, 'tcx> Elaborator<'cx, 'gcx, 'tcx> {
 121     pub fn filter_to_traits(self) -> FilterToTraits<Self> {
 122         FilterToTraits::new(self)
 123     }
 124
 125     fn push(&mut self, predicate: &ty::Predicate<'tcx>) {
 126         let tcx = self.visited.tcx;
 127         match *predicate {
 128             ty::Predicate::Trait(ref data) => {
 129                 // Predicates declared on the trait.
 130                 let predicates = tcx.item_super_predicates(data.def_id());
 131
 132                 let mut predicates: Vec<_> =
 133                     predicates.predicates
 134                               .iter()
 135                               .map(|p| p.subst_supertrait(tcx, &data.to_poly_trait_ref()))
 136                               .collect();
 137
 138                 debug!("super_predicates: data={:?} predicates={:?}",
 139                        data, predicates);
 140
 141                 // Only keep those bounds that we haven't already
 142                 // seen.  This is necessary to prevent infinite
 143                 // recursion in some cases.  One common case is when
 144                 // people define `trait Sized: Sized { }` rather than `trait
 145                 // Sized { }`.
 146                 predicates.retain(|r| self.visited.insert(r));
 147
 148                 self.stack.extend(predicates);
 149             }
 150             ty::Predicate::WellFormed(..) => {
 151                 // Currently, we do not elaborate WF predicates,
 152                 // although we easily could.
 153             }
 154             ty::Predicate::ObjectSafe(..) => {
 155                 // Currently, we do not elaborate object-safe
 156                 // predicates.
 157             }
 158             ty::Predicate::Equate(..) => {
 159                 // Currently, we do not "elaborate" predicates like
 160                 // `X == Y`, though conceivably we might. For example,
 161                 // `&X == &Y` implies that `X == Y`.
 162             }
 163             ty::Predicate::Projection(..) => {
 164                 // Nothing to elaborate in a projection predicate.
 165             }
 166             ty::Predicate::ClosureKind(..) => {
 167                 // Nothing to elaborate when waiting for a closure's kind to be inferred.
 168             }
 169
 170             ty::Predicate::RegionOutlives(..) => {
 171                 // Nothing to elaborate from `'a: 'b`.
 172             }
 173
 174             ty::Predicate::TypeOutlives(ref data) => {
 175                 // We know that `T: 'a` for some type `T`. We can
 176                 // often elaborate this. For example, if we know that
 177                 // `[U]: 'a`, that implies that `U: 'a`. Similarly, if
 178                 // we know `&'a U: 'b`, then we know that `'a: 'b` and
 179                 // `U: 'b`.
 180                 //
 181                 // We can basically ignore bound regions here. So for
 182                 // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to
 183                 // `'a: 'b`.
 184
 185                 // Ignore `for<'a> T: 'a` -- we might in the future
 186                 // consider this as evidence that `T: 'static`, but
 187                 // I'm a bit wary of such constructions and so for now
 188                 // I want to be conservative. --nmatsakis
 189                 let ty_max = data.skip_binder().0;
 190                 let r_min = data.skip_binder().1;
 191                 if r_min.is_bound() {
 192                     return;
 193                 }
 194
 195                 let visited = &mut self.visited;
 196                 self.stack.extend(
 197                     tcx.outlives_components(ty_max)
 198                        .into_iter()
 199                        .filter_map(|component| match component {
 200                            Component::Region(r) => if r.is_bound() {
 201                                None
 202                            } else {
 203                                Some(ty::Predicate::RegionOutlives(
 204                                    ty::Binder(ty::OutlivesPredicate(r, r_min))))
 205                            },
 206
 207                            Component::Param(p) => {
 208                                let ty = tcx.mk_param(p.idx, p.name);
 209                                Some(ty::Predicate::TypeOutlives(
 210                                    ty::Binder(ty::OutlivesPredicate(ty, r_min))))
 211                            },
 212
 213                            Component::UnresolvedInferenceVariable(_) => {
 214                                None
 215                            },
 216
 217                            Component::Projection(_) |
 218                            Component::EscapingProjection(_) => {
 219                                // We can probably do more here. This
 220                                // corresponds to a case like `<T as
 221                                // Foo<'a>>::U: 'b`.
 222                                None
 223                            },
 224                        })
 225                        .filter(|p| visited.insert(p)));
 226             }
 227         }
 228     }
 229 }
 230
 231 impl<'cx, 'gcx, 'tcx> Iterator for Elaborator<'cx, 'gcx, 'tcx> {
 232     type Item = ty::Predicate<'tcx>;
 233
 234     fn next(&mut self) -> Option<ty::Predicate<'tcx>> {
 235         // Extract next item from top-most stack frame, if any.
 236         let next_predicate = match self.stack.pop() {
 237             Some(predicate) => predicate,
 238             None => {
 239                 // No more stack frames. Done.
 240                 return None;
 241             }
 242         };
 243         self.push(&next_predicate);
 244         return Some(next_predicate);
 245     }
 246 }
 247
 248 ///////////////////////////////////////////////////////////////////////////
 249 // Supertrait iterator
 250 ///////////////////////////////////////////////////////////////////////////
 251
 252 pub type Supertraits<'cx, 'gcx, 'tcx> = FilterToTraits<Elaborator<'cx, 'gcx, 'tcx>>;
 253
 254 pub fn supertraits<'cx, 'gcx, 'tcx>(tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 255                                     trait_ref: ty::PolyTraitRef<'tcx>)
 256                                     -> Supertraits<'cx, 'gcx, 'tcx>
 257 {
 258     elaborate_trait_ref(tcx, trait_ref).filter_to_traits()
 259 }
 260
 261 pub fn transitive_bounds<'cx, 'gcx, 'tcx>(tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 262                                           bounds: &[ty::PolyTraitRef<'tcx>])
 263                                           -> Supertraits<'cx, 'gcx, 'tcx>
 264 {
 265     elaborate_trait_refs(tcx, bounds).filter_to_traits()
 266 }
 267
 268 ///////////////////////////////////////////////////////////////////////////
 269 // Iterator over def-ids of supertraits
 270
 271 pub struct SupertraitDefIds<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 272     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 273     stack: Vec<DefId>,
 274     visited: FxHashSet<DefId>,
 275 }
 276
 277 pub fn supertrait_def_ids<'cx, 'gcx, 'tcx>(tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 278                                            trait_def_id: DefId)
 279                                            -> SupertraitDefIds<'cx, 'gcx, 'tcx>
 280 {
 281     SupertraitDefIds {
 282         tcx: tcx,
 283         stack: vec![trait_def_id],
 284         visited: Some(trait_def_id).into_iter().collect(),
 285     }
 286 }
 287
 288 impl<'cx, 'gcx, 'tcx> Iterator for SupertraitDefIds<'cx, 'gcx, 'tcx> {
 289     type Item = DefId;
 290
 291     fn next(&mut self) -> Option<DefId> {
 292         let def_id = match self.stack.pop() {
 293             Some(def_id) => def_id,
 294             None => { return None; }
 295         };
 296
 297         let predicates = self.tcx.item_super_predicates(def_id);
 298         let visited = &mut self.visited;
 299         self.stack.extend(
 300             predicates.predicates
 301                       .iter()
 302                       .filter_map(|p| p.to_opt_poly_trait_ref())
 303                       .map(|t| t.def_id())
 304                       .filter(|&super_def_id| visited.insert(super_def_id)));
 305         Some(def_id)
 306     }
 307 }
 308
 309 ///////////////////////////////////////////////////////////////////////////
 310 // Other
 311 ///////////////////////////////////////////////////////////////////////////
 312
 313 /// A filter around an iterator of predicates that makes it yield up
 314 /// just trait references.
 315 pub struct FilterToTraits<I> {
 316     base_iterator: I
 317 }
 318
 319 impl<I> FilterToTraits<I> {
 320     fn new(base: I) -> FilterToTraits<I> {
 321         FilterToTraits { base_iterator: base }
 322     }
 323 }
 324
 325 impl<'tcx,I:Iterator<Item=ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> {
 326     type Item = ty::PolyTraitRef<'tcx>;
 327
 328     fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> {
 329         loop {
 330             match self.base_iterator.next() {
 331                 None => {
 332                     return None;
 333                 }
 334                 Some(ty::Predicate::Trait(data)) => {
 335                     return Some(data.to_poly_trait_ref());
 336                 }
 337                 Some(_) => {
 338                 }
 339             }
 340         }
 341     }
 342 }
 343
 344 ///////////////////////////////////////////////////////////////////////////
 345 // Other
 346 ///////////////////////////////////////////////////////////////////////////
 347
 348 /// Instantiate all bound parameters of the impl with the given substs,
 349 /// returning the resulting trait ref and all obligations that arise.
 350 /// The obligations are closed under normalization.
 351 pub fn impl_trait_ref_and_oblig<'a, 'gcx, 'tcx>(selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
 352                                                 impl_def_id: DefId,
 353                                                 impl_substs: &Substs<'tcx>)
 354                                                 -> (ty::TraitRef<'tcx>,
 355                                                     Vec<PredicateObligation<'tcx>>)
 356 {
 357     let impl_trait_ref =
 358         selcx.tcx().impl_trait_ref(impl_def_id).unwrap();
 359     let impl_trait_ref =
 360         impl_trait_ref.subst(selcx.tcx(), impl_substs);
 361     let Normalized { value: impl_trait_ref, obligations: normalization_obligations1 } =
 362         super::normalize(selcx, ObligationCause::dummy(), &impl_trait_ref);
 363
 364     let predicates = selcx.tcx().item_predicates(impl_def_id);
 365     let predicates = predicates.instantiate(selcx.tcx(), impl_substs);
 366     let Normalized { value: predicates, obligations: normalization_obligations2 } =
 367         super::normalize(selcx, ObligationCause::dummy(), &predicates);
 368     let impl_obligations =
 369         predicates_for_generics(ObligationCause::dummy(), 0, &predicates);
 370
 371     let impl_obligations: Vec<_> =
 372         impl_obligations.into_iter()
 373         .chain(normalization_obligations1)
 374         .chain(normalization_obligations2)
 375         .collect();
 376
 377     (impl_trait_ref, impl_obligations)
 378 }
 379
 380 /// See `super::obligations_for_generics`
 381 pub fn predicates_for_generics<'tcx>(cause: ObligationCause<'tcx>,
 382                                      recursion_depth: usize,
 383                                      generic_bounds: &ty::InstantiatedPredicates<'tcx>)
 384                                      -> Vec<PredicateObligation<'tcx>>
 385 {
 386     debug!("predicates_for_generics(generic_bounds={:?})",
 387            generic_bounds);
 388
 389     generic_bounds.predicates.iter().map(|predicate| {
 390         Obligation { cause: cause.clone(),
 391                      recursion_depth: recursion_depth,
 392                      predicate: predicate.clone() }
 393     }).collect()
 394 }
 395
 396 pub fn predicate_for_trait_ref<'tcx>(
 397     cause: ObligationCause<'tcx>,
 398     trait_ref: ty::TraitRef<'tcx>,
 399     recursion_depth: usize)
 400     -> PredicateObligation<'tcx>
 401 {
 402     Obligation {
 403         cause: cause,
 404         recursion_depth: recursion_depth,
 405         predicate: trait_ref.to_predicate(),
 406     }
 407 }
 408
 409 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 410     pub fn predicate_for_trait_def(self,
 411         cause: ObligationCause<'tcx>,
 412         trait_def_id: DefId,
 413         recursion_depth: usize,
 414         param_ty: Ty<'tcx>,
 415         ty_params: &[Ty<'tcx>])
 416         -> PredicateObligation<'tcx>
 417     {
 418         let trait_ref = ty::TraitRef {
 419             def_id: trait_def_id,
 420             substs: self.mk_substs_trait(param_ty, ty_params)
 421         };
 422         predicate_for_trait_ref(cause, trait_ref, recursion_depth)
 423     }
 424
 425     /// Cast a trait reference into a reference to one of its super
 426     /// traits; returns `None` if `target_trait_def_id` is not a
 427     /// supertrait.
 428     pub fn upcast_choices(self,
 429                           source_trait_ref: ty::PolyTraitRef<'tcx>,
 430                           target_trait_def_id: DefId)
 431                           -> Vec<ty::PolyTraitRef<'tcx>>
 432     {
 433         if source_trait_ref.def_id() == target_trait_def_id {
 434             return vec![source_trait_ref]; // shorcut the most common case
 435         }
 436
 437         supertraits(self, source_trait_ref)
 438             .filter(|r| r.def_id() == target_trait_def_id)
 439             .collect()
 440     }
 441
 442     /// Given a trait `trait_ref`, returns the number of vtable entries
 443     /// that come from `trait_ref`, excluding its supertraits. Used in
 444     /// computing the vtable base for an upcast trait of a trait object.
 445     pub fn count_own_vtable_entries(self, trait_ref: ty::PolyTraitRef<'tcx>) -> usize {
 446         let mut entries = 0;
 447         // Count number of methods and add them to the total offset.
 448         // Skip over associated types and constants.
 449         for trait_item in self.associated_items(trait_ref.def_id()) {
 450             if trait_item.kind == ty::AssociatedKind::Method {
 451                 entries += 1;
 452             }
 453         }
 454         entries
 455     }
 456
 457     /// Given an upcast trait object described by `object`, returns the
 458     /// index of the method `method_def_id` (which should be part of
 459     /// `object.upcast_trait_ref`) within the vtable for `object`.
 460     pub fn get_vtable_index_of_object_method<N>(self,
 461                                                 object: &super::VtableObjectData<'tcx, N>,
 462                                                 method_def_id: DefId) -> usize {
 463         // Count number of methods preceding the one we are selecting and
 464         // add them to the total offset.
 465         // Skip over associated types and constants.
 466         let mut entries = object.vtable_base;
 467         for trait_item in self.associated_items(object.upcast_trait_ref.def_id()) {
 468             if trait_item.def_id == method_def_id {
 469                 // The item with the ID we were given really ought to be a method.
 470                 assert_eq!(trait_item.kind, ty::AssociatedKind::Method);
 471                 return entries;
 472             }
 473             if trait_item.kind == ty::AssociatedKind::Method {
 474                 entries += 1;
 475             }
 476         }
 477
 478         bug!("get_vtable_index_of_object_method: {:?} was not found",
 479              method_def_id);
 480     }
 481
 482     pub fn closure_trait_ref_and_return_type(self,
 483         fn_trait_def_id: DefId,
 484         self_ty: Ty<'tcx>,
 485         sig: ty::PolyFnSig<'tcx>,
 486         tuple_arguments: TupleArgumentsFlag)
 487         -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>)>
 488     {
 489         let arguments_tuple = match tuple_arguments {
 490             TupleArgumentsFlag::No => sig.skip_binder().inputs()[0],
 491             TupleArgumentsFlag::Yes =>
 492                 self.intern_tup(sig.skip_binder().inputs(), false),
 493         };
 494         let trait_ref = ty::TraitRef {
 495             def_id: fn_trait_def_id,
 496             substs: self.mk_substs_trait(self_ty, &[arguments_tuple]),
 497         };
 498         ty::Binder((trait_ref, sig.skip_binder().output()))
 499     }
 500 }
 501
 502 pub enum TupleArgumentsFlag { Yes, No }