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