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