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