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<ty::Predicate<'tcx>> for Elaborator<'cx, 'tcx> {
 137     fn next(&mut self) -> Option<ty::Predicate<'tcx>> {
 138         loop {
 139             // Extract next item from top-most stack frame, if any.
 140             let next_predicate = match self.stack.last_mut() {
 141                 None => {
 142                     // No more stack frames. Done.
 143                     return None;
 144                 }
 145                 Some(entry) => {
 146                     let p = entry.position;
 147                     if p < entry.predicates.len() {
 148                         // Still more predicates left in the top stack frame.
 149                         entry.position += 1;
 150
 151                         let next_predicate =
 152                             entry.predicates[p].clone();
 153
 154                         Some(next_predicate)
 155                     } else {
 156                         None
 157                     }
 158                 }
 159             };
 160
 161             match next_predicate {
 162                 Some(next_predicate) => {
 163                     self.push(&next_predicate);
 164                     return Some(next_predicate);
 165                 }
 166
 167                 None => {
 168                     // Top stack frame is exhausted, pop it.
 169                     self.stack.pop();
 170                 }
 171             }
 172         }
 173     }
 174 }
 175
 176 ///////////////////////////////////////////////////////////////////////////
 177 // Supertrait iterator
 178 ///////////////////////////////////////////////////////////////////////////
 179
 180 /// A filter around the `Elaborator` that just yields up supertrait references,
 181 /// not other kinds of predicates.
 182 pub struct Supertraits<'cx, 'tcx:'cx> {
 183     elaborator: Elaborator<'cx, 'tcx>,
 184 }
 185
 186 pub fn supertraits<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
 187                               trait_ref: ty::PolyTraitRef<'tcx>)
 188                               -> Supertraits<'cx, 'tcx>
 189 {
 190     elaborate_trait_ref(tcx, trait_ref).filter_to_traits()
 191 }
 192
 193 pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
 194                                     bounds: &[ty::PolyTraitRef<'tcx>])
 195                                     -> Supertraits<'cx, 'tcx>
 196 {
 197     elaborate_trait_refs(tcx, bounds).filter_to_traits()
 198 }
 199
 200 impl<'cx, 'tcx> Iterator<ty::PolyTraitRef<'tcx>> for Supertraits<'cx, 'tcx> {
 201     fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> {
 202         loop {
 203             match self.elaborator.next() {
 204                 None => {
 205                     return None;
 206                 }
 207                 Some(ty::Predicate::Trait(data)) => {
 208                     return Some(data.to_poly_trait_ref());
 209                 }
 210                 Some(_) => {
 211                 }
 212             }
 213         }
 214     }
 215 }
 216
 217 ///////////////////////////////////////////////////////////////////////////
 218 // Other
 219 ///////////////////////////////////////////////////////////////////////////
 220
 221 // determine the `self` type, using fresh variables for all variables
 222 // declared on the impl declaration e.g., `impl<A,B> for Box<[(A,B)]>`
 223 // would return ($0, $1) where $0 and $1 are freshly instantiated type
 224 // variables.
 225 pub fn fresh_substs_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
 226                                        span: Span,
 227                                        impl_def_id: ast::DefId)
 228                                        -> Substs<'tcx>
 229 {
 230     let tcx = infcx.tcx;
 231     let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics;
 232     infcx.fresh_substs_for_generics(span, &impl_generics)
 233 }
 234
 235 impl<'tcx, N> fmt::Show for VtableImplData<'tcx, N> {
 236     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 237         write!(f, "VtableImpl({})", self.impl_def_id)
 238     }
 239 }
 240
 241 impl<'tcx> fmt::Show for super::VtableObjectData<'tcx> {
 242     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 243         write!(f, "VtableObject(...)")
 244     }
 245 }
 246
 247 /// See `super::obligations_for_generics`
 248 pub fn predicates_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
 249                                      cause: ObligationCause<'tcx>,
 250                                      recursion_depth: uint,
 251                                      generic_bounds: &ty::GenericBounds<'tcx>)
 252                                      -> VecPerParamSpace<PredicateObligation<'tcx>>
 253 {
 254     debug!("predicates_for_generics(generic_bounds={})",
 255            generic_bounds.repr(tcx));
 256
 257     generic_bounds.predicates.map(|predicate| {
 258         Obligation { cause: cause.clone(),
 259                      recursion_depth: recursion_depth,
 260                      predicate: predicate.clone() }
 261     })
 262 }
 263
 264 pub fn trait_ref_for_builtin_bound<'tcx>(
 265     tcx: &ty::ctxt<'tcx>,
 266     builtin_bound: ty::BuiltinBound,
 267     param_ty: Ty<'tcx>)
 268     -> Result<Rc<ty::TraitRef<'tcx>>, ErrorReported>
 269 {
 270     match tcx.lang_items.from_builtin_kind(builtin_bound) {
 271         Ok(def_id) => {
 272             Ok(Rc::new(ty::TraitRef {
 273                 def_id: def_id,
 274                 substs: tcx.mk_substs(Substs::empty().with_self_ty(param_ty))
 275             }))
 276         }
 277         Err(e) => {
 278             tcx.sess.err(e.as_slice());
 279             Err(ErrorReported)
 280         }
 281     }
 282 }
 283
 284 pub fn predicate_for_builtin_bound<'tcx>(
 285     tcx: &ty::ctxt<'tcx>,
 286     cause: ObligationCause<'tcx>,
 287     builtin_bound: ty::BuiltinBound,
 288     recursion_depth: uint,
 289     param_ty: Ty<'tcx>)
 290     -> Result<PredicateObligation<'tcx>, ErrorReported>
 291 {
 292     let trait_ref = try!(trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty));
 293     Ok(Obligation {
 294         cause: cause,
 295         recursion_depth: recursion_depth,
 296         predicate: trait_ref.as_predicate(),
 297     })
 298 }
 299
 300 /// Cast a trait reference into a reference to one of its super
 301 /// traits; returns `None` if `target_trait_def_id` is not a
 302 /// supertrait.
 303 pub fn upcast<'tcx>(tcx: &ty::ctxt<'tcx>,
 304                     source_trait_ref: ty::PolyTraitRef<'tcx>,
 305                     target_trait_def_id: ast::DefId)
 306                     -> Option<ty::PolyTraitRef<'tcx>>
 307 {
 308     if source_trait_ref.def_id() == target_trait_def_id {
 309         return Some(source_trait_ref); // shorcut the most common case
 310     }
 311
 312     for super_trait_ref in supertraits(tcx, source_trait_ref) {
 313         if super_trait_ref.def_id() == target_trait_def_id {
 314             return Some(super_trait_ref);
 315         }
 316     }
 317
 318     None
 319 }
 320
 321 /// Given an object of type `object_trait_ref`, returns the index of
 322 /// the method `n_method` found in the trait `trait_def_id` (which
 323 /// should be a supertrait of `object_trait_ref`) within the vtable
 324 /// for `object_trait_ref`.
 325 pub fn get_vtable_index_of_object_method<'tcx>(tcx: &ty::ctxt<'tcx>,
 326                                                object_trait_ref: ty::PolyTraitRef<'tcx>,
 327                                                trait_def_id: ast::DefId,
 328                                                method_index_in_trait: uint) -> uint {
 329     // We need to figure the "real index" of the method in a
 330     // listing of all the methods of an object. We do this by
 331     // iterating down the supertraits of the object's trait until
 332     // we find the trait the method came from, counting up the
 333     // methods from them.
 334     let mut method_count = 0;
 335     ty::each_bound_trait_and_supertraits(tcx, &[object_trait_ref], |bound_ref| {
 336         if bound_ref.def_id() == trait_def_id {
 337             false
 338         } else {
 339             let trait_items = ty::trait_items(tcx, bound_ref.def_id());
 340             for trait_item in trait_items.iter() {
 341                 match *trait_item {
 342                     ty::MethodTraitItem(_) => method_count += 1,
 343                     ty::TypeTraitItem(_) => {}
 344                 }
 345             }
 346             true
 347         }
 348     });
 349     method_count + method_index_in_trait
 350 }
 351
 352 impl<'tcx,O:Repr<'tcx>> Repr<'tcx> for super::Obligation<'tcx, O> {
 353     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 354         format!("Obligation(predicate={},depth={})",
 355                 self.predicate.repr(tcx),
 356                 self.recursion_depth)
 357     }
 358 }
 359
 360 impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::Vtable<'tcx, N> {
 361     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 362         match *self {
 363             super::VtableImpl(ref v) =>
 364                 v.repr(tcx),
 365
 366             super::VtableUnboxedClosure(ref d, ref s) =>
 367                 format!("VtableUnboxedClosure({},{})",
 368                         d.repr(tcx),
 369                         s.repr(tcx)),
 370
 371             super::VtableFnPointer(ref d) =>
 372                 format!("VtableFnPointer({})",
 373                         d.repr(tcx)),
 374
 375             super::VtableObject(ref d) =>
 376                 format!("VtableObject({})",
 377                         d.repr(tcx)),
 378
 379             super::VtableParam =>
 380                 format!("VtableParam"),
 381
 382             super::VtableBuiltin(ref d) =>
 383                 d.repr(tcx)
 384         }
 385     }
 386 }
 387
 388 impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::VtableImplData<'tcx, N> {
 389     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 390         format!("VtableImpl(impl_def_id={}, substs={}, nested={})",
 391                 self.impl_def_id.repr(tcx),
 392                 self.substs.repr(tcx),
 393                 self.nested.repr(tcx))
 394     }
 395 }
 396
 397 impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::VtableBuiltinData<N> {
 398     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 399         format!("VtableBuiltin(nested={})",
 400                 self.nested.repr(tcx))
 401     }
 402 }
 403
 404 impl<'tcx> Repr<'tcx> for super::VtableObjectData<'tcx> {
 405     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 406         format!("VtableObject(object_ty={})",
 407                 self.object_ty.repr(tcx))
 408     }
 409 }
 410
 411 impl<'tcx> Repr<'tcx> for super::SelectionError<'tcx> {
 412     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 413         match *self {
 414             super::Overflow =>
 415                 format!("Overflow"),
 416
 417             super::Unimplemented =>
 418                 format!("Unimplemented"),
 419
 420             super::OutputTypeParameterMismatch(ref a, ref b, ref c) =>
 421                 format!("OutputTypeParameterMismatch({},{},{})",
 422                         a.repr(tcx),
 423                         b.repr(tcx),
 424                         c.repr(tcx)),
 425         }
 426     }
 427 }
 428
 429 impl<'tcx> Repr<'tcx> for super::FulfillmentError<'tcx> {
 430     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 431         format!("FulfillmentError({},{})",
 432                 self.obligation.repr(tcx),
 433                 self.code.repr(tcx))
 434     }
 435 }
 436
 437 impl<'tcx> Repr<'tcx> for super::FulfillmentErrorCode<'tcx> {
 438     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 439         match *self {
 440             super::CodeSelectionError(ref o) => o.repr(tcx),
 441             super::CodeProjectionError(ref o) => o.repr(tcx),
 442             super::CodeAmbiguity => format!("Ambiguity")
 443         }
 444     }
 445 }
 446
 447 impl<'tcx> fmt::Show for super::FulfillmentErrorCode<'tcx> {
 448     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 449         match *self {
 450             super::CodeSelectionError(ref e) => write!(f, "{}", e),
 451             super::CodeProjectionError(ref e) => write!(f, "{}", e),
 452             super::CodeAmbiguity => write!(f, "Ambiguity")
 453         }
 454     }
 455 }
 456
 457 impl<'tcx> Repr<'tcx> for super::MismatchedProjectionTypes<'tcx> {
 458     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 459         self.err.repr(tcx)
 460     }
 461 }
 462
 463 impl<'tcx> fmt::Show for super::MismatchedProjectionTypes<'tcx> {
 464     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 465         write!(f, "MismatchedProjectionTypes(..)")
 466     }
 467 }
 468
 469