src/librustc/middle/traits/mod.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 /*!
  12  * Trait Resolution. See doc.rs.
  13  */
  14
  15 pub use self::SelectionError::*;
  16 pub use self::FulfillmentErrorCode::*;
  17 pub use self::Vtable::*;
  18 pub use self::ObligationCauseCode::*;
  19
  20 use middle::mem_categorization::Typer;
  21 use middle::subst;
  22 use middle::ty::{mod, Ty};
  23 use middle::typeck::infer::InferCtxt;
  24 use std::rc::Rc;
  25 use std::slice::Items;
  26 use syntax::ast;
  27 use syntax::codemap::{Span, DUMMY_SP};
  28 use util::common::ErrorReported;
  29
  30 pub use self::fulfill::FulfillmentContext;
  31 pub use self::select::SelectionContext;
  32 pub use self::select::SelectionCache;
  33 pub use self::select::{MethodMatchResult, MethodMatched, MethodAmbiguous, MethodDidNotMatch};
  34 pub use self::select::{MethodMatchedData}; // intentionally don't export variants
  35 pub use self::util::supertraits;
  36 pub use self::util::transitive_bounds;
  37 pub use self::util::Supertraits;
  38 pub use self::util::search_trait_and_supertraits_from_bound;
  39
  40 mod coherence;
  41 mod fulfill;
  42 mod select;
  43 mod util;
  44
  45 /**
  46  * An `Obligation` represents some trait reference (e.g. `int:Eq`) for
  47  * which the vtable must be found.  The process of finding a vtable is
  48  * called "resolving" the `Obligation`. This process consists of
  49  * either identifying an `impl` (e.g., `impl Eq for int`) that
  50  * provides the required vtable, or else finding a bound that is in
  51  * scope. The eventual result is usually a `Selection` (defined below).
  52  */
  53 #[deriving(Clone)]
  54 pub struct Obligation<'tcx> {
  55     pub cause: ObligationCause<'tcx>,
  56     pub recursion_depth: uint,
  57     pub trait_ref: Rc<ty::TraitRef<'tcx>>,
  58 }
  59
  60 /**
  61  * Why did we incur this obligation? Used for error reporting.
  62  */
  63 #[deriving(Clone)]
  64 pub struct ObligationCause<'tcx> {
  65     pub span: Span,
  66     pub code: ObligationCauseCode<'tcx>
  67 }
  68
  69 #[deriving(Clone)]
  70 pub enum ObligationCauseCode<'tcx> {
  71     /// Not well classified or should be obvious from span.
  72     MiscObligation,
  73
  74     /// In an impl of trait X for type Y, type Y must
  75     /// also implement all supertraits of X.
  76     ItemObligation(ast::DefId),
  77
  78     /// Obligation incurred due to an object cast.
  79     ObjectCastObligation(/* Object type */ Ty<'tcx>),
  80
  81     /// To implement drop, type must be sendable.
  82     DropTrait,
  83
  84     /// Various cases where expressions must be sized/copy/etc:
  85     AssignmentLhsSized,        // L = X implies that L is Sized
  86     StructInitializerSized,    // S { ... } must be Sized
  87     VariableType(ast::NodeId), // Type of each variable must be Sized
  88     ReturnType,                // Return type must be Sized
  89     RepeatVec,                 // [T,..n] --> T must be Copy
  90
  91     // Captures of variable the given id by a closure (span is the
  92     // span of the closure)
  93     ClosureCapture(ast::NodeId, Span),
  94
  95     // Types of fields (other than the last) in a struct must be sized.
  96     FieldSized,
  97
  98     // Only Sized types can be made into objects
  99     ObjectSized,
 100 }
 101
 102 pub type Obligations<'tcx> = subst::VecPerParamSpace<Obligation<'tcx>>;
 103
 104 pub type Selection<'tcx> = Vtable<'tcx, Obligation<'tcx>>;
 105
 106 #[deriving(Clone,Show)]
 107 pub enum SelectionError<'tcx> {
 108     Unimplemented,
 109     Overflow,
 110     OutputTypeParameterMismatch(Rc<ty::TraitRef<'tcx>>, ty::type_err<'tcx>)
 111 }
 112
 113 pub struct FulfillmentError<'tcx> {
 114     pub obligation: Obligation<'tcx>,
 115     pub code: FulfillmentErrorCode<'tcx>
 116 }
 117
 118 #[deriving(Clone)]
 119 pub enum FulfillmentErrorCode<'tcx> {
 120     CodeSelectionError(SelectionError<'tcx>),
 121     CodeAmbiguity,
 122 }
 123
 124 /**
 125  * When performing resolution, it is typically the case that there
 126  * can be one of three outcomes:
 127  *
 128  * - `Ok(Some(r))`: success occurred with result `r`
 129  * - `Ok(None)`: could not definitely determine anything, usually due
 130  *   to inconclusive type inference.
 131  * - `Err(e)`: error `e` occurred
 132  */
 133 pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 134
 135 /**
 136  * Given the successful resolution of an obligation, the `Vtable`
 137  * indicates where the vtable comes from. Note that while we call this
 138  * a "vtable", it does not necessarily indicate dynamic dispatch at
 139  * runtime. `Vtable` instances just tell the compiler where to find
 140  * methods, but in generic code those methods are typically statically
 141  * dispatched -- only when an object is constructed is a `Vtable`
 142  * instance reified into an actual vtable.
 143  *
 144  * For example, the vtable may be tied to a specific impl (case A),
 145  * or it may be relative to some bound that is in scope (case B).
 146  *
 147  *
 148  * ```
 149  * impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
 150  * impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
 151  * impl Clone for int { ... }             // Impl_3
 152  *
 153  * fn foo<T:Clone>(concrete: Option<Box<int>>,
 154  *                 param: T,
 155  *                 mixed: Option<T>) {
 156  *
 157  *    // Case A: Vtable points at a specific impl. Only possible when
 158  *    // type is concretely known. If the impl itself has bounded
 159  *    // type parameters, Vtable will carry resolutions for those as well:
 160  *    concrete.clone(); // Vtable(Impl_1, [Vtable(Impl_2, [Vtable(Impl_3)])])
 161  *
 162  *    // Case B: Vtable must be provided by caller. This applies when
 163  *    // type is a type parameter.
 164  *    param.clone();    // VtableParam(Oblig_1)
 165  *
 166  *    // Case C: A mix of cases A and B.
 167  *    mixed.clone();    // Vtable(Impl_1, [VtableParam(Oblig_1)])
 168  * }
 169  * ```
 170  *
 171  * ### The type parameter `N`
 172  *
 173  * See explanation on `VtableImplData`.
 174  */
 175 #[deriving(Show,Clone)]
 176 pub enum Vtable<'tcx, N> {
 177     /// Vtable identifying a particular impl.
 178     VtableImpl(VtableImplData<'tcx, N>),
 179
 180     /// Vtable automatically generated for an unboxed closure. The def
 181     /// ID is the ID of the closure expression. This is a `VtableImpl`
 182     /// in spirit, but the impl is generated by the compiler and does
 183     /// not appear in the source.
 184     VtableUnboxedClosure(ast::DefId, subst::Substs<'tcx>),
 185
 186     /// Successful resolution to an obligation provided by the caller
 187     /// for some type parameter.
 188     VtableParam(VtableParamData<'tcx>),
 189
 190     /// Successful resolution for a builtin trait.
 191     VtableBuiltin(VtableBuiltinData<N>),
 192 }
 193
 194 /**
 195  * Identifies a particular impl in the source, along with a set of
 196  * substitutions from the impl's type/lifetime parameters. The
 197  * `nested` vector corresponds to the nested obligations attached to
 198  * the impl's type parameters.
 199  *
 200  * The type parameter `N` indicates the type used for "nested
 201  * obligations" that are required by the impl. During type check, this
 202  * is `Obligation`, as one might expect. During trans, however, this
 203  * is `()`, because trans only requires a shallow resolution of an
 204  * impl, and nested obligations are satisfied later.
 205  */
 206 #[deriving(Clone)]
 207 pub struct VtableImplData<'tcx, N> {
 208     pub impl_def_id: ast::DefId,
 209     pub substs: subst::Substs<'tcx>,
 210     pub nested: subst::VecPerParamSpace<N>
 211 }
 212
 213 #[deriving(Show,Clone)]
 214 pub struct VtableBuiltinData<N> {
 215     pub nested: subst::VecPerParamSpace<N>
 216 }
 217
 218 /**
 219  * A vtable provided as a parameter by the caller. For example, in a
 220  * function like `fn foo<T:Eq>(...)`, if the `eq()` method is invoked
 221  * on an instance of `T`, the vtable would be of type `VtableParam`.
 222  */
 223 #[deriving(PartialEq,Eq,Clone)]
 224 pub struct VtableParamData<'tcx> {
 225     // In the above example, this would `Eq`
 226     pub bound: Rc<ty::TraitRef<'tcx>>,
 227 }
 228
 229 pub fn select_inherent_impl<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
 230                                      param_env: &ty::ParameterEnvironment<'tcx>,
 231                                      typer: &Typer<'tcx>,
 232                                      cause: ObligationCause<'tcx>,
 233                                      impl_def_id: ast::DefId,
 234                                      self_ty: Ty<'tcx>)
 235                                      -> SelectionResult<'tcx,
 236                                             VtableImplData<'tcx, Obligation<'tcx>>>
 237 {
 238     /*!
 239      * Matches the self type of the inherent impl `impl_def_id`
 240      * against `self_ty` and returns the resulting resolution.  This
 241      * routine may modify the surrounding type context (for example,
 242      * it may unify variables).
 243      */
 244
 245     // This routine is only suitable for inherent impls. This is
 246     // because it does not attempt to unify the output type parameters
 247     // from the trait ref against the values from the obligation.
 248     // (These things do not apply to inherent impls, for which there
 249     // is no trait ref nor obligation.)
 250     //
 251     // Matching against non-inherent impls should be done with
 252     // `try_resolve_obligation()`.
 253     assert!(ty::impl_trait_ref(infcx.tcx, impl_def_id).is_none());
 254
 255     let mut selcx = select::SelectionContext::new(infcx, param_env, typer);
 256     selcx.select_inherent_impl(impl_def_id, cause, self_ty)
 257 }
 258
 259 pub fn is_orphan_impl(tcx: &ty::ctxt,
 260                       impl_def_id: ast::DefId)
 261                       -> bool
 262 {
 263     /*!
 264      * True if neither the trait nor self type is local. Note that
 265      * `impl_def_id` must refer to an impl of a trait, not an inherent
 266      * impl.
 267      */
 268
 269     !coherence::impl_is_local(tcx, impl_def_id)
 270 }
 271
 272 pub fn overlapping_impls(infcx: &InferCtxt,
 273                          impl1_def_id: ast::DefId,
 274                          impl2_def_id: ast::DefId)
 275                          -> bool
 276 {
 277     /*!
 278      * True if there exist types that satisfy both of the two given impls.
 279      */
 280
 281     coherence::impl_can_satisfy(infcx, impl1_def_id, impl2_def_id) &&
 282     coherence::impl_can_satisfy(infcx, impl2_def_id, impl1_def_id)
 283 }
 284
 285 pub fn obligations_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
 286                                       cause: ObligationCause<'tcx>,
 287                                       generic_bounds: &ty::GenericBounds<'tcx>,
 288                                       type_substs: &subst::VecPerParamSpace<Ty<'tcx>>)
 289                                       -> subst::VecPerParamSpace<Obligation<'tcx>>
 290 {
 291     /*!
 292      * Given generic bounds from an impl like:
 293      *
 294      *    impl<A:Foo, B:Bar+Qux> ...
 295      *
 296      * along with the bindings for the types `A` and `B` (e.g.,
 297      * `<A=A0, B=B0>`), yields a result like
 298      *
 299      *    [[Foo for A0, Bar for B0, Qux for B0], [], []]
 300      *
 301      * Expects that `generic_bounds` have already been fully
 302      * substituted, late-bound regions liberated and so forth,
 303      * so that they are in the same namespace as `type_substs`.
 304      */
 305
 306     util::obligations_for_generics(tcx, cause, 0, generic_bounds, type_substs)
 307 }
 308
 309 pub fn obligation_for_builtin_bound<'tcx>(tcx: &ty::ctxt<'tcx>,
 310                                           cause: ObligationCause<'tcx>,
 311                                           source_ty: Ty<'tcx>,
 312                                           builtin_bound: ty::BuiltinBound)
 313                                           -> Result<Obligation<'tcx>, ErrorReported>
 314 {
 315     util::obligation_for_builtin_bound(tcx, cause, builtin_bound, 0, source_ty)
 316 }
 317
 318 impl<'tcx> Obligation<'tcx> {
 319     pub fn new(cause: ObligationCause<'tcx>, trait_ref: Rc<ty::TraitRef<'tcx>>)
 320                -> Obligation<'tcx> {
 321         Obligation { cause: cause,
 322                      recursion_depth: 0,
 323                      trait_ref: trait_ref }
 324     }
 325
 326     pub fn misc(span: Span, trait_ref: Rc<ty::TraitRef<'tcx>>) -> Obligation<'tcx> {
 327         Obligation::new(ObligationCause::misc(span), trait_ref)
 328     }
 329
 330     pub fn self_ty(&self) -> Ty<'tcx> {
 331         self.trait_ref.self_ty()
 332     }
 333 }
 334
 335 impl<'tcx> ObligationCause<'tcx> {
 336     pub fn new(span: Span, code: ObligationCauseCode<'tcx>)
 337                -> ObligationCause<'tcx> {
 338         ObligationCause { span: span, code: code }
 339     }
 340
 341     pub fn misc(span: Span) -> ObligationCause<'tcx> {
 342         ObligationCause { span: span, code: MiscObligation }
 343     }
 344
 345     pub fn dummy() -> ObligationCause<'tcx> {
 346         ObligationCause { span: DUMMY_SP, code: MiscObligation }
 347     }
 348 }
 349
 350 impl<'tcx, N> Vtable<'tcx, N> {
 351     pub fn iter_nested(&self) -> Items<N> {
 352         match *self {
 353             VtableImpl(ref i) => i.iter_nested(),
 354             VtableUnboxedClosure(..) => (&[]).iter(),
 355             VtableParam(_) => (&[]).iter(),
 356             VtableBuiltin(ref i) => i.iter_nested(),
 357         }
 358     }
 359
 360     pub fn map_nested<M>(&self, op: |&N| -> M) -> Vtable<'tcx, M> {
 361         match *self {
 362             VtableImpl(ref i) => VtableImpl(i.map_nested(op)),
 363             VtableUnboxedClosure(d, ref s) => VtableUnboxedClosure(d, s.clone()),
 364             VtableParam(ref p) => VtableParam((*p).clone()),
 365             VtableBuiltin(ref i) => VtableBuiltin(i.map_nested(op)),
 366         }
 367     }
 368
 369     pub fn map_move_nested<M>(self, op: |N| -> M) -> Vtable<'tcx, M> {
 370         match self {
 371             VtableImpl(i) => VtableImpl(i.map_move_nested(op)),
 372             VtableUnboxedClosure(d, s) => VtableUnboxedClosure(d, s),
 373             VtableParam(p) => VtableParam(p),
 374             VtableBuiltin(i) => VtableBuiltin(i.map_move_nested(op)),
 375         }
 376     }
 377 }
 378
 379 impl<'tcx, N> VtableImplData<'tcx, N> {
 380     pub fn iter_nested(&self) -> Items<N> {
 381         self.nested.iter()
 382     }
 383
 384     pub fn map_nested<M>(&self,
 385                          op: |&N| -> M)
 386                          -> VtableImplData<'tcx, M>
 387     {
 388         VtableImplData {
 389             impl_def_id: self.impl_def_id,
 390             substs: self.substs.clone(),
 391             nested: self.nested.map(op)
 392         }
 393     }
 394
 395     pub fn map_move_nested<M>(self, op: |N| -> M)
 396                               -> VtableImplData<'tcx, M> {
 397         let VtableImplData { impl_def_id, substs, nested } = self;
 398         VtableImplData {
 399             impl_def_id: impl_def_id,
 400             substs: substs,
 401             nested: nested.map_move(op)
 402         }
 403     }
 404 }
 405
 406 impl<N> VtableBuiltinData<N> {
 407     pub fn iter_nested(&self) -> Items<N> {
 408         self.nested.iter()
 409     }
 410
 411     pub fn map_nested<M>(&self,
 412                          op: |&N| -> M)
 413                          -> VtableBuiltinData<M>
 414     {
 415         VtableBuiltinData {
 416             nested: self.nested.map(op)
 417         }
 418     }
 419
 420     pub fn map_move_nested<M>(self, op: |N| -> M) -> VtableBuiltinData<M> {
 421         VtableBuiltinData {
 422             nested: self.nested.map_move(op)
 423         }
 424     }
 425 }
 426
 427 impl<'tcx> FulfillmentError<'tcx> {
 428     fn new(obligation: Obligation<'tcx>, code: FulfillmentErrorCode<'tcx>)
 429            -> FulfillmentError<'tcx>
 430     {
 431         FulfillmentError { obligation: obligation, code: code }
 432     }
 433
 434     pub fn is_overflow(&self) -> bool {
 435         match self.code {
 436             CodeAmbiguity => false,
 437             CodeSelectionError(Overflow) => true,
 438             CodeSelectionError(_) => false,
 439         }
 440     }
 441 }