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, VecPerParamSpace};
  12 use middle::infer::InferCtxt;
  13 use middle::ty::{mod, Ty, AsPredicate, ToPolyTraitRef};
  14 use std::collections::HashSet;
  15 use std::fmt;
  16 use std::rc::Rc;
  17 use syntax::ast;
  18 use syntax::codemap::Span;
  19 use util::common::ErrorReported;
  20 use util::ppaux::Repr;
  21
  22 use super::{Obligation, ObligationCause, PredicateObligation,
  23             VtableImpl, VtableParam, VtableImplData};
  24
  25 ///////////////////////////////////////////////////////////////////////////
  26 // `Elaboration` iterator
  27 ///////////////////////////////////////////////////////////////////////////
  28
  29 /// "Elaboration" is the process of identifying all the predicates that
  30 /// are implied by a source predicate. Currently this basically means
  31 /// walking the "supertraits" and other similar assumptions. For
  32 /// example, if we know that `T : Ord`, the elaborator would deduce
  33 /// that `T : PartialOrd` holds as well. Similarly, if we have `trait
  34 /// Foo : 'static`, and we know that `T : Foo`, then we know that `T :
  35 /// 'static`.
  36 pub struct Elaborator<'cx, 'tcx:'cx> {
  37     tcx: &'cx ty::ctxt<'tcx>,
  38     stack: Vec<StackEntry<'tcx>>,
  39     visited: HashSet<ty::Predicate<'tcx>>,
  40 }
  41
  42 struct StackEntry<'tcx> {
  43     position: uint,
  44     predicates: Vec<ty::Predicate<'tcx>>,
  45 }
  46
  47 pub fn elaborate_trait_ref<'cx, 'tcx>(
  48     tcx: &'cx ty::ctxt<'tcx>,
  49     trait_ref: ty::PolyTraitRef<'tcx>)
  50     -> Elaborator<'cx, 'tcx>
  51 {
  52     elaborate_predicates(tcx, vec![trait_ref.as_predicate()])
  53 }
  54
  55 pub fn elaborate_trait_refs<'cx, 'tcx>(
  56     tcx: &'cx ty::ctxt<'tcx>,
  57     trait_refs: &[ty::PolyTraitRef<'tcx>])
  58     -> Elaborator<'cx, 'tcx>
  59 {
  60     let predicates = trait_refs.iter()
  61                                .map(|trait_ref| trait_ref.as_predicate())
  62                                .collect();
  63     elaborate_predicates(tcx, predicates)
  64 }
  65
  66 pub fn elaborate_predicates<'cx, 'tcx>(
  67     tcx: &'cx ty::ctxt<'tcx>,
  68     predicates: Vec<ty::Predicate<'tcx>>)
  69     -> Elaborator<'cx, 'tcx>
  70 {
  71     let visited: HashSet<ty::Predicate<'tcx>> =
  72         predicates.iter()
  73                   .map(|b| (*b).clone())
  74                   .collect();
  75
  76     let entry = StackEntry { position: 0, predicates: predicates };
  77     Elaborator { tcx: tcx, stack: vec![entry], visited: visited }
  78 }
  79
  80 impl<'cx, 'tcx> Elaborator<'cx, 'tcx> {
  81     pub fn filter_to_traits(self) -> Supertraits<'cx, 'tcx> {
  82         Supertraits { elaborator: self }
  83     }
  84
  85     fn push(&mut self, predicate: &ty::Predicate<'tcx>) {
  86         match *predicate {
  87             ty::Predicate::Trait(ref data) => {
  88                 let mut predicates =
  89                     ty::predicates_for_trait_ref(self.tcx,
  90                                                  &data.to_poly_trait_ref());
  91
  92                 // Only keep those bounds that we haven't already
  93                 // seen.  This is necessary to prevent infinite
  94                 // recursion in some cases.  One common case is when
  95                 // people define `trait Sized { }` rather than `trait
  96                 // Sized for Sized? { }`.
  97                 predicates.retain(|r| self.visited.insert(r.clone()));
  98
  99                 self.stack.push(StackEntry { position: 0,
 100                                              predicates: predicates });
 101             }
 102             ty::Predicate::Equate(..) => {
 103                 // Currently, we do not "elaborate" predicates like
 104                 // `X == Y`, though conceivably we might. For example,
 105                 // `&X == &Y` implies that `X == Y`.
 106             }
 107             ty::Predicate::Projection(..) => {
 108                 // Nothing to elaborate in a projection predicate.
 109             }
 110             ty::Predicate::RegionOutlives(..) |
 111             ty::Predicate::TypeOutlives(..) => {
 112                 // Currently, we do not "elaborate" predicates like
 113                 // `'a : 'b` or `T : 'a`.  We could conceivably do
 114                 // more here.  For example,
 115                 //
 116                 //     &'a int : 'b
 117                 //
 118                 // implies that
 119                 //
 120                 //     'a : 'b
 121                 //
 122                 // and we could get even more if we took WF
 123                 // constraints into account. For example,
 124                 //
 125                 //     &'a &'b int : 'c
 126                 //
 127                 // implies that
 128                 //
 129                 //     'b : 'a
 130                 //     'a : 'c
 131             }
 132         }
 133     }
 134 }
 135
 136 impl<'cx, 'tcx> Iterator for Elaborator<'cx, 'tcx> {
 137     type Item = ty::Predicate<'tcx>;
 138
 139     fn next(&mut self) -> Option<ty::Predicate<'tcx>> {
 140         loop {
 141             // Extract next item from top-most stack frame, if any.
 142             let next_predicate = match self.stack.last_mut() {
 143                 None => {
 144                     // No more stack frames. Done.
 145                     return None;
 146                 }
 147                 Some(entry) => {
 148                     let p = entry.position;
 149                     if p < entry.predicates.len() {
 150                         // Still more predicates left in the top stack frame.
 151                         entry.position += 1;
 152
 153                         let next_predicate =
 154                             entry.predicates[p].clone();
 155
 156                         Some(next_predicate)
 157                     } else {
 158                         None
 159                     }
 160                 }
 161             };
 162
 163             match next_predicate {
 164                 Some(next_predicate) => {
 165                     self.push(&next_predicate);
 166                     return Some(next_predicate);
 167                 }
 168
 169                 None => {
 170                     // Top stack frame is exhausted, pop it.
 171                     self.stack.pop();
 172                 }
 173             }
 174         }
 175     }
 176 }
 177
 178 ///////////////////////////////////////////////////////////////////////////
 179 // Supertrait iterator
 180 ///////////////////////////////////////////////////////////////////////////
 181
 182 /// A filter around the `Elaborator` that just yields up supertrait references,
 183 /// not other kinds of predicates.
 184 pub struct Supertraits<'cx, 'tcx:'cx> {
 185     elaborator: Elaborator<'cx, 'tcx>,
 186 }
 187
 188 pub fn supertraits<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
 189                               trait_ref: ty::PolyTraitRef<'tcx>)
 190                               -> Supertraits<'cx, 'tcx>
 191 {
 192     elaborate_trait_ref(tcx, trait_ref).filter_to_traits()
 193 }
 194
 195 pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
 196                                     bounds: &[ty::PolyTraitRef<'tcx>])
 197                                     -> Supertraits<'cx, 'tcx>
 198 {
 199     elaborate_trait_refs(tcx, bounds).filter_to_traits()
 200 }
 201
 202 impl<'cx, 'tcx> Iterator for Supertraits<'cx, 'tcx> {
 203     type Item = ty::PolyTraitRef<'tcx>;
 204
 205     fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> {
 206         loop {
 207             match self.elaborator.next() {
 208                 None => {
 209                     return None;
 210                 }
 211                 Some(ty::Predicate::Trait(data)) => {
 212                     return Some(data.to_poly_trait_ref());
 213                 }
 214                 Some(_) => {
 215                 }
 216             }
 217         }
 218     }
 219 }
 220
 221 ///////////////////////////////////////////////////////////////////////////
 222 // Other
 223 ///////////////////////////////////////////////////////////////////////////
 224
 225 // determine the `self` type, using fresh variables for all variables
 226 // declared on the impl declaration e.g., `impl<A,B> for Box<[(A,B)]>`
 227 // would return ($0, $1) where $0 and $1 are freshly instantiated type
 228 // variables.
 229 pub fn fresh_substs_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
 230                                        span: Span,
 231                                        impl_def_id: ast::DefId)
 232                                        -> Substs<'tcx>
 233 {
 234     let tcx = infcx.tcx;
 235     let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics;
 236     infcx.fresh_substs_for_generics(span, &impl_generics)
 237 }
 238
 239 impl<'tcx, N> fmt::Show for VtableImplData<'tcx, N> {
 240     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 241         write!(f, "VtableImpl({})", self.impl_def_id)
 242     }
 243 }
 244
 245 impl<'tcx> fmt::Show for super::VtableObjectData<'tcx> {
 246     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 247         write!(f, "VtableObject(...)")
 248     }
 249 }
 250
 251 /// See `super::obligations_for_generics`
 252 pub fn predicates_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
 253                                      cause: ObligationCause<'tcx>,
 254                                      recursion_depth: uint,
 255                                      generic_bounds: &ty::GenericBounds<'tcx>)
 256                                      -> VecPerParamSpace<PredicateObligation<'tcx>>
 257 {
 258     debug!("predicates_for_generics(generic_bounds={})",
 259            generic_bounds.repr(tcx));
 260
 261     generic_bounds.predicates.map(|predicate| {
 262         Obligation { cause: cause.clone(),
 263                      recursion_depth: recursion_depth,
 264                      predicate: predicate.clone() }
 265     })
 266 }
 267
 268 pub fn trait_ref_for_builtin_bound<'tcx>(
 269     tcx: &ty::ctxt<'tcx>,
 270     builtin_bound: ty::BuiltinBound,
 271     param_ty: Ty<'tcx>)
 272     -> Result<Rc<ty::TraitRef<'tcx>>, ErrorReported>
 273 {
 274     match tcx.lang_items.from_builtin_kind(builtin_bound) {
 275         Ok(def_id) => {
 276             Ok(Rc::new(ty::TraitRef {
 277                 def_id: def_id,
 278                 substs: tcx.mk_substs(Substs::empty().with_self_ty(param_ty))
 279             }))
 280         }
 281         Err(e) => {
 282             tcx.sess.err(e.as_slice());
 283             Err(ErrorReported)
 284         }
 285     }
 286 }
 287
 288 pub fn predicate_for_builtin_bound<'tcx>(
 289     tcx: &ty::ctxt<'tcx>,
 290     cause: ObligationCause<'tcx>,
 291     builtin_bound: ty::BuiltinBound,
 292     recursion_depth: uint,
 293     param_ty: Ty<'tcx>)
 294     -> Result<PredicateObligation<'tcx>, ErrorReported>
 295 {
 296     let trait_ref = try!(trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty));
 297     Ok(Obligation {
 298         cause: cause,
 299         recursion_depth: recursion_depth,
 300         predicate: trait_ref.as_predicate(),
 301     })
 302 }
 303
 304 /// Cast a trait reference into a reference to one of its super
 305 /// traits; returns `None` if `target_trait_def_id` is not a
 306 /// supertrait.
 307 pub fn upcast<'tcx>(tcx: &ty::ctxt<'tcx>,
 308                     source_trait_ref: ty::PolyTraitRef<'tcx>,
 309                     target_trait_def_id: ast::DefId)
 310                     -> Option<ty::PolyTraitRef<'tcx>>
 311 {
 312     if source_trait_ref.def_id() == target_trait_def_id {
 313         return Some(source_trait_ref); // shorcut the most common case
 314     }
 315
 316     for super_trait_ref in supertraits(tcx, source_trait_ref) {
 317         if super_trait_ref.def_id() == target_trait_def_id {
 318             return Some(super_trait_ref);
 319         }
 320     }
 321
 322     None
 323 }
 324
 325 /// Given an object of type `object_trait_ref`, returns the index of
 326 /// the method `n_method` found in the trait `trait_def_id` (which
 327 /// should be a supertrait of `object_trait_ref`) within the vtable
 328 /// for `object_trait_ref`.
 329 pub fn get_vtable_index_of_object_method<'tcx>(tcx: &ty::ctxt<'tcx>,
 330                                                object_trait_ref: ty::PolyTraitRef<'tcx>,
 331                                                trait_def_id: ast::DefId,
 332                                                method_index_in_trait: uint) -> uint {
 333     // We need to figure the "real index" of the method in a
 334     // listing of all the methods of an object. We do this by
 335     // iterating down the supertraits of the object's trait until
 336     // we find the trait the method came from, counting up the
 337     // methods from them.
 338     let mut method_count = 0;
 339     ty::each_bound_trait_and_supertraits(tcx, &[object_trait_ref], |bound_ref| {
 340         if bound_ref.def_id() == trait_def_id {
 341             false
 342         } else {
 343             let trait_items = ty::trait_items(tcx, bound_ref.def_id());
 344             for trait_item in trait_items.iter() {
 345                 match *trait_item {
 346                     ty::MethodTraitItem(_) => method_count += 1,
 347                     ty::TypeTraitItem(_) => {}
 348                 }
 349             }
 350             true
 351         }
 352     });
 353     method_count + method_index_in_trait
 354 }
 355
 356 impl<'tcx,O:Repr<'tcx>> Repr<'tcx> for super::Obligation<'tcx, O> {
 357     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 358         format!("Obligation(predicate={},depth={})",
 359                 self.predicate.repr(tcx),
 360                 self.recursion_depth)
 361     }
 362 }
 363
 364 impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::Vtable<'tcx, N> {
 365     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 366         match *self {
 367             super::VtableImpl(ref v) =>
 368                 v.repr(tcx),
 369
 370             super::VtableUnboxedClosure(ref d, ref s) =>
 371                 format!("VtableUnboxedClosure({},{})",
 372                         d.repr(tcx),
 373                         s.repr(tcx)),
 374
 375             super::VtableFnPointer(ref d) =>
 376                 format!("VtableFnPointer({})",
 377                         d.repr(tcx)),
 378
 379             super::VtableObject(ref d) =>
 380                 format!("VtableObject({})",
 381                         d.repr(tcx)),
 382
 383             super::VtableParam =>
 384                 format!("VtableParam"),
 385
 386             super::VtableBuiltin(ref d) =>
 387                 d.repr(tcx)
 388         }
 389     }
 390 }
 391
 392 impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::VtableImplData<'tcx, N> {
 393     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 394         format!("VtableImpl(impl_def_id={}, substs={}, nested={})",
 395                 self.impl_def_id.repr(tcx),
 396                 self.substs.repr(tcx),
 397                 self.nested.repr(tcx))
 398     }
 399 }
 400
 401 impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::VtableBuiltinData<N> {
 402     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 403         format!("VtableBuiltin(nested={})",
 404                 self.nested.repr(tcx))
 405     }
 406 }
 407
 408 impl<'tcx> Repr<'tcx> for super::VtableObjectData<'tcx> {
 409     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 410         format!("VtableObject(object_ty={})",
 411                 self.object_ty.repr(tcx))
 412     }
 413 }
 414
 415 impl<'tcx> Repr<'tcx> for super::SelectionError<'tcx> {
 416     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 417         match *self {
 418             super::Overflow =>
 419                 format!("Overflow"),
 420
 421             super::Unimplemented =>
 422                 format!("Unimplemented"),
 423
 424             super::OutputTypeParameterMismatch(ref a, ref b, ref c) =>
 425                 format!("OutputTypeParameterMismatch({},{},{})",
 426                         a.repr(tcx),
 427                         b.repr(tcx),
 428                         c.repr(tcx)),
 429         }
 430     }
 431 }
 432
 433 impl<'tcx> Repr<'tcx> for super::FulfillmentError<'tcx> {
 434     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 435         format!("FulfillmentError({},{})",
 436                 self.obligation.repr(tcx),
 437                 self.code.repr(tcx))
 438     }
 439 }
 440
 441 impl<'tcx> Repr<'tcx> for super::FulfillmentErrorCode<'tcx> {
 442     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 443         match *self {
 444             super::CodeSelectionError(ref o) => o.repr(tcx),
 445             super::CodeProjectionError(ref o) => o.repr(tcx),
 446             super::CodeAmbiguity => format!("Ambiguity")
 447         }
 448     }
 449 }
 450
 451 impl<'tcx> fmt::Show for super::FulfillmentErrorCode<'tcx> {
 452     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 453         match *self {
 454             super::CodeSelectionError(ref e) => write!(f, "{}", e),
 455             super::CodeProjectionError(ref e) => write!(f, "{}", e),
 456             super::CodeAmbiguity => write!(f, "Ambiguity")
 457         }
 458     }
 459 }
 460
 461 impl<'tcx> Repr<'tcx> for super::MismatchedProjectionTypes<'tcx> {
 462     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 463         self.err.repr(tcx)
 464     }
 465 }
 466
 467 impl<'tcx> fmt::Show for super::MismatchedProjectionTypes<'tcx> {
 468     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 469         write!(f, "MismatchedProjectionTypes(..)")
 470     }
 471 }
 472
 473