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