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 util::common::ErrorReported;
  15 use util::nodemap::FnvHashSet;
  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: FnvHashSet<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: FnvHashSet() }
  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.lookup_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             ty::Predicate::RegionOutlives(..) |
 170             ty::Predicate::TypeOutlives(..) => {
 171                 // Currently, we do not "elaborate" predicates like
 172                 // `'a : 'b` or `T : 'a`.  We could conceivably do
 173                 // more here.  For example,
 174                 //
 175                 //     &'a int : 'b
 176                 //
 177                 // implies that
 178                 //
 179                 //     'a : 'b
 180                 //
 181                 // and we could get even more if we took WF
 182                 // constraints into account. For example,
 183                 //
 184                 //     &'a &'b int : 'c
 185                 //
 186                 // implies that
 187                 //
 188                 //     'b : 'a
 189                 //     'a : 'c
 190             }
 191         }
 192     }
 193 }
 194
 195 impl<'cx, 'gcx, 'tcx> Iterator for Elaborator<'cx, 'gcx, 'tcx> {
 196     type Item = ty::Predicate<'tcx>;
 197
 198     fn next(&mut self) -> Option<ty::Predicate<'tcx>> {
 199         // Extract next item from top-most stack frame, if any.
 200         let next_predicate = match self.stack.pop() {
 201             Some(predicate) => predicate,
 202             None => {
 203                 // No more stack frames. Done.
 204                 return None;
 205             }
 206         };
 207         self.push(&next_predicate);
 208         return Some(next_predicate);
 209     }
 210 }
 211
 212 ///////////////////////////////////////////////////////////////////////////
 213 // Supertrait iterator
 214 ///////////////////////////////////////////////////////////////////////////
 215
 216 pub type Supertraits<'cx, 'gcx, 'tcx> = FilterToTraits<Elaborator<'cx, 'gcx, 'tcx>>;
 217
 218 pub fn supertraits<'cx, 'gcx, 'tcx>(tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 219                                     trait_ref: ty::PolyTraitRef<'tcx>)
 220                                     -> Supertraits<'cx, 'gcx, 'tcx>
 221 {
 222     elaborate_trait_ref(tcx, trait_ref).filter_to_traits()
 223 }
 224
 225 pub fn transitive_bounds<'cx, 'gcx, 'tcx>(tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 226                                           bounds: &[ty::PolyTraitRef<'tcx>])
 227                                           -> Supertraits<'cx, 'gcx, 'tcx>
 228 {
 229     elaborate_trait_refs(tcx, bounds).filter_to_traits()
 230 }
 231
 232 ///////////////////////////////////////////////////////////////////////////
 233 // Iterator over def-ids of supertraits
 234
 235 pub struct SupertraitDefIds<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 236     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 237     stack: Vec<DefId>,
 238     visited: FnvHashSet<DefId>,
 239 }
 240
 241 pub fn supertrait_def_ids<'cx, 'gcx, 'tcx>(tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 242                                            trait_def_id: DefId)
 243                                            -> SupertraitDefIds<'cx, 'gcx, 'tcx>
 244 {
 245     SupertraitDefIds {
 246         tcx: tcx,
 247         stack: vec![trait_def_id],
 248         visited: Some(trait_def_id).into_iter().collect(),
 249     }
 250 }
 251
 252 impl<'cx, 'gcx, 'tcx> Iterator for SupertraitDefIds<'cx, 'gcx, 'tcx> {
 253     type Item = DefId;
 254
 255     fn next(&mut self) -> Option<DefId> {
 256         let def_id = match self.stack.pop() {
 257             Some(def_id) => def_id,
 258             None => { return None; }
 259         };
 260
 261         let predicates = self.tcx.lookup_super_predicates(def_id);
 262         let visited = &mut self.visited;
 263         self.stack.extend(
 264             predicates.predicates
 265                       .iter()
 266                       .filter_map(|p| p.to_opt_poly_trait_ref())
 267                       .map(|t| t.def_id())
 268                       .filter(|&super_def_id| visited.insert(super_def_id)));
 269         Some(def_id)
 270     }
 271 }
 272
 273 ///////////////////////////////////////////////////////////////////////////
 274 // Other
 275 ///////////////////////////////////////////////////////////////////////////
 276
 277 /// A filter around an iterator of predicates that makes it yield up
 278 /// just trait references.
 279 pub struct FilterToTraits<I> {
 280     base_iterator: I
 281 }
 282
 283 impl<I> FilterToTraits<I> {
 284     fn new(base: I) -> FilterToTraits<I> {
 285         FilterToTraits { base_iterator: base }
 286     }
 287 }
 288
 289 impl<'tcx,I:Iterator<Item=ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> {
 290     type Item = ty::PolyTraitRef<'tcx>;
 291
 292     fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> {
 293         loop {
 294             match self.base_iterator.next() {
 295                 None => {
 296                     return None;
 297                 }
 298                 Some(ty::Predicate::Trait(data)) => {
 299                     return Some(data.to_poly_trait_ref());
 300                 }
 301                 Some(_) => {
 302                 }
 303             }
 304         }
 305     }
 306 }
 307
 308 ///////////////////////////////////////////////////////////////////////////
 309 // Other
 310 ///////////////////////////////////////////////////////////////////////////
 311
 312 /// Instantiate all bound parameters of the impl with the given substs,
 313 /// returning the resulting trait ref and all obligations that arise.
 314 /// The obligations are closed under normalization.
 315 pub fn impl_trait_ref_and_oblig<'a, 'gcx, 'tcx>(selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
 316                                                 impl_def_id: DefId,
 317                                                 impl_substs: &Substs<'tcx>)
 318                                                 -> (ty::TraitRef<'tcx>,
 319                                                     Vec<PredicateObligation<'tcx>>)
 320 {
 321     let impl_trait_ref =
 322         selcx.tcx().impl_trait_ref(impl_def_id).unwrap();
 323     let impl_trait_ref =
 324         impl_trait_ref.subst(selcx.tcx(), impl_substs);
 325     let Normalized { value: impl_trait_ref, obligations: normalization_obligations1 } =
 326         super::normalize(selcx, ObligationCause::dummy(), &impl_trait_ref);
 327
 328     let predicates = selcx.tcx().lookup_predicates(impl_def_id);
 329     let predicates = predicates.instantiate(selcx.tcx(), impl_substs);
 330     let Normalized { value: predicates, obligations: normalization_obligations2 } =
 331         super::normalize(selcx, ObligationCause::dummy(), &predicates);
 332     let impl_obligations =
 333         predicates_for_generics(ObligationCause::dummy(), 0, &predicates);
 334
 335     let impl_obligations: Vec<_> =
 336         impl_obligations.into_iter()
 337         .chain(normalization_obligations1)
 338         .chain(normalization_obligations2)
 339         .collect();
 340
 341     (impl_trait_ref, impl_obligations)
 342 }
 343
 344 /// See `super::obligations_for_generics`
 345 pub fn predicates_for_generics<'tcx>(cause: ObligationCause<'tcx>,
 346                                      recursion_depth: usize,
 347                                      generic_bounds: &ty::InstantiatedPredicates<'tcx>)
 348                                      -> Vec<PredicateObligation<'tcx>>
 349 {
 350     debug!("predicates_for_generics(generic_bounds={:?})",
 351            generic_bounds);
 352
 353     generic_bounds.predicates.iter().map(|predicate| {
 354         Obligation { cause: cause.clone(),
 355                      recursion_depth: recursion_depth,
 356                      predicate: predicate.clone() }
 357     }).collect()
 358 }
 359
 360 pub fn predicate_for_trait_ref<'tcx>(
 361     cause: ObligationCause<'tcx>,
 362     trait_ref: ty::TraitRef<'tcx>,
 363     recursion_depth: usize)
 364     -> PredicateObligation<'tcx>
 365 {
 366     Obligation {
 367         cause: cause,
 368         recursion_depth: recursion_depth,
 369         predicate: trait_ref.to_predicate(),
 370     }
 371 }
 372
 373 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 374     pub fn trait_ref_for_builtin_bound(self,
 375         builtin_bound: ty::BuiltinBound,
 376         param_ty: Ty<'tcx>)
 377         -> Result<ty::TraitRef<'tcx>, ErrorReported>
 378     {
 379         match self.lang_items.from_builtin_kind(builtin_bound) {
 380             Ok(def_id) => {
 381                 Ok(ty::TraitRef {
 382                     def_id: def_id,
 383                     substs: Substs::new_trait(self, param_ty, &[])
 384                 })
 385             }
 386             Err(e) => {
 387                 self.sess.err(&e);
 388                 Err(ErrorReported)
 389             }
 390         }
 391     }
 392
 393     pub fn predicate_for_trait_def(self,
 394         cause: ObligationCause<'tcx>,
 395         trait_def_id: DefId,
 396         recursion_depth: usize,
 397         param_ty: Ty<'tcx>,
 398         ty_params: &[Ty<'tcx>])
 399         -> PredicateObligation<'tcx>
 400     {
 401         let trait_ref = ty::TraitRef {
 402             def_id: trait_def_id,
 403             substs: Substs::new_trait(self, param_ty, ty_params)
 404         };
 405         predicate_for_trait_ref(cause, trait_ref, recursion_depth)
 406     }
 407
 408     pub fn predicate_for_builtin_bound(self,
 409         cause: ObligationCause<'tcx>,
 410         builtin_bound: ty::BuiltinBound,
 411         recursion_depth: usize,
 412         param_ty: Ty<'tcx>)
 413         -> Result<PredicateObligation<'tcx>, ErrorReported>
 414     {
 415         let trait_ref = self.trait_ref_for_builtin_bound(builtin_bound, param_ty)?;
 416         Ok(predicate_for_trait_ref(cause, trait_ref, recursion_depth))
 417     }
 418
 419     /// Cast a trait reference into a reference to one of its super
 420     /// traits; returns `None` if `target_trait_def_id` is not a
 421     /// supertrait.
 422     pub fn upcast_choices(self,
 423                           source_trait_ref: ty::PolyTraitRef<'tcx>,
 424                           target_trait_def_id: DefId)
 425                           -> Vec<ty::PolyTraitRef<'tcx>>
 426     {
 427         if source_trait_ref.def_id() == target_trait_def_id {
 428             return vec![source_trait_ref]; // shorcut the most common case
 429         }
 430
 431         supertraits(self, source_trait_ref)
 432             .filter(|r| r.def_id() == target_trait_def_id)
 433             .collect()
 434     }
 435
 436     /// Given a trait `trait_ref`, returns the number of vtable entries
 437     /// that come from `trait_ref`, excluding its supertraits. Used in
 438     /// computing the vtable base for an upcast trait of a trait object.
 439     pub fn count_own_vtable_entries(self, trait_ref: ty::PolyTraitRef<'tcx>) -> usize {
 440         let mut entries = 0;
 441         // Count number of methods and add them to the total offset.
 442         // Skip over associated types and constants.
 443         for trait_item in &self.trait_items(trait_ref.def_id())[..] {
 444             if let ty::MethodTraitItem(_) = *trait_item {
 445                 entries += 1;
 446             }
 447         }
 448         entries
 449     }
 450
 451     /// Given an upcast trait object described by `object`, returns the
 452     /// index of the method `method_def_id` (which should be part of
 453     /// `object.upcast_trait_ref`) within the vtable for `object`.
 454     pub fn get_vtable_index_of_object_method<N>(self,
 455                                                 object: &super::VtableObjectData<'tcx, N>,
 456                                                 method_def_id: DefId) -> usize {
 457         // Count number of methods preceding the one we are selecting and
 458         // add them to the total offset.
 459         // Skip over associated types and constants.
 460         let mut entries = object.vtable_base;
 461         for trait_item in &self.trait_items(object.upcast_trait_ref.def_id())[..] {
 462             if trait_item.def_id() == method_def_id {
 463                 // The item with the ID we were given really ought to be a method.
 464                 assert!(match *trait_item {
 465                     ty::MethodTraitItem(_) => true,
 466                     _ => false
 467                 });
 468
 469                 return entries;
 470             }
 471             if let ty::MethodTraitItem(_) = *trait_item {
 472                 entries += 1;
 473             }
 474         }
 475
 476         bug!("get_vtable_index_of_object_method: {:?} was not found",
 477              method_def_id);
 478     }
 479
 480     pub fn closure_trait_ref_and_return_type(self,
 481         fn_trait_def_id: DefId,
 482         self_ty: Ty<'tcx>,
 483         sig: &ty::PolyFnSig<'tcx>,
 484         tuple_arguments: TupleArgumentsFlag)
 485         -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>)>
 486     {
 487         let arguments_tuple = match tuple_arguments {
 488             TupleArgumentsFlag::No => sig.0.inputs[0],
 489             TupleArgumentsFlag::Yes => self.mk_tup(sig.0.inputs.to_vec()),
 490         };
 491         let trait_ref = ty::TraitRef {
 492             def_id: fn_trait_def_id,
 493             substs: Substs::new_trait(self, self_ty, &[arguments_tuple]),
 494         };
 495         ty::Binder((trait_ref, sig.0.output))
 496     }
 497 }
 498
 499 pub enum TupleArgumentsFlag { Yes, No }