src/librustc/middle/traits/util.rs

   1
   2 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   3 // file at the top-level directory of this distribution and at
   4 // http://rust-lang.org/COPYRIGHT.
   5 //
   6 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   7 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   8 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   9 // option. This file may not be copied, modified, or distributed
  10 // except according to those terms.
  11
  12 use middle::subst;
  13 use middle::subst::{ParamSpace, Subst, Substs, VecPerParamSpace};
  14 use middle::typeck::infer::InferCtxt;
  15 use middle::ty;
  16 use std::fmt;
  17 use std::rc::Rc;
  18 use syntax::ast;
  19 use syntax::codemap::Span;
  20 use util::ppaux::Repr;
  21
  22 use super::{Obligation, ObligationCause, VtableImpl, VtableParam, VtableParamData, VtableImplData};
  23
  24 ///////////////////////////////////////////////////////////////////////////
  25 // Supertrait iterator
  26
  27 pub struct Supertraits<'cx, 'tcx:'cx> {
  28     tcx: &'cx ty::ctxt<'tcx>,
  29     stack: Vec<SupertraitEntry>,
  30 }
  31
  32 struct SupertraitEntry {
  33     position: uint,
  34     supertraits: Vec<Rc<ty::TraitRef>>,
  35 }
  36
  37 pub fn supertraits<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
  38                               trait_ref: Rc<ty::TraitRef>)
  39                               -> Supertraits<'cx, 'tcx>
  40 {
  41     /*!
  42      * Returns an iterator over the trait reference `T` and all of its
  43      * supertrait references. May contain duplicates. In general
  44      * the ordering is not defined.
  45      *
  46      * Example:
  47      *
  48      * ```
  49      * trait Foo { ... }
  50      * trait Bar : Foo { ... }
  51      * trait Baz : Bar+Foo { ... }
  52      * ```
  53      *
  54      * `supertraits(Baz)` yields `[Baz, Bar, Foo, Foo]` in some order.
  55      */
  56
  57     transitive_bounds(tcx, [trait_ref])
  58 }
  59
  60 pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
  61                                     bounds: &[Rc<ty::TraitRef>])
  62                                     -> Supertraits<'cx, 'tcx>
  63 {
  64     let bounds = Vec::from_fn(bounds.len(), |i| bounds[i].clone());
  65     let entry = SupertraitEntry { position: 0, supertraits: bounds };
  66     Supertraits { tcx: tcx, stack: vec![entry] }
  67 }
  68
  69 impl<'cx, 'tcx> Supertraits<'cx, 'tcx> {
  70     fn push(&mut self, trait_ref: &ty::TraitRef) {
  71         let bounds = ty::bounds_for_trait_ref(self.tcx, trait_ref);
  72         let entry = SupertraitEntry { position: 0,
  73                                       supertraits: bounds.trait_bounds };
  74         self.stack.push(entry);
  75     }
  76
  77     pub fn indices(&self) -> Vec<uint> {
  78         /*!
  79          * Returns the path taken through the trait supertraits to
  80          * reach the current point.
  81          */
  82
  83         self.stack.iter().map(|e| e.position).collect()
  84     }
  85 }
  86
  87 impl<'cx, 'tcx> Iterator<Rc<ty::TraitRef>> for Supertraits<'cx, 'tcx> {
  88     fn next(&mut self) -> Option<Rc<ty::TraitRef>> {
  89         loop {
  90             // Extract next item from top-most stack frame, if any.
  91             let next_trait = match self.stack.mut_last() {
  92                 None => {
  93                     // No more stack frames. Done.
  94                     return None;
  95                 }
  96                 Some(entry) => {
  97                     let p = entry.position;
  98                     if p < entry.supertraits.len() {
  99                         // Still more supertraits left in the top stack frame.
 100                         entry.position += 1;
 101
 102                         let next_trait =
 103                             (*entry.supertraits.get(p)).clone();
 104                         Some(next_trait)
 105                     } else {
 106                         None
 107                     }
 108                 }
 109             };
 110
 111             match next_trait {
 112                 Some(next_trait) => {
 113                     self.push(&*next_trait);
 114                     return Some(next_trait);
 115                 }
 116
 117                 None => {
 118                     // Top stack frame is exhausted, pop it.
 119                     self.stack.pop();
 120                 }
 121             }
 122         }
 123     }
 124 }
 125
 126 // determine the `self` type, using fresh variables for all variables
 127 // declared on the impl declaration e.g., `impl<A,B> for ~[(A,B)]`
 128 // would return ($0, $1) where $0 and $1 are freshly instantiated type
 129 // variables.
 130 pub fn fresh_substs_for_impl(infcx: &InferCtxt,
 131                              span: Span,
 132                              impl_def_id: ast::DefId)
 133                              -> Substs
 134 {
 135     let tcx = infcx.tcx;
 136     let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics;
 137     infcx.fresh_substs_for_generics(span, &impl_generics)
 138 }
 139
 140 impl<N> fmt::Show for VtableImplData<N> {
 141     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 142         write!(f, "VtableImpl({})", self.impl_def_id)
 143     }
 144 }
 145
 146 impl fmt::Show for VtableParamData {
 147     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 148         write!(f, "VtableParam(...)")
 149     }
 150 }
 151
 152 pub fn obligations_for_generics(tcx: &ty::ctxt,
 153                                 cause: ObligationCause,
 154                                 recursion_depth: uint,
 155                                 generics: &ty::Generics,
 156                                 substs: &Substs)
 157                                 -> VecPerParamSpace<Obligation>
 158 {
 159     /*! See `super::obligations_for_generics` */
 160
 161     debug!("obligations_for_generics(generics={}, substs={})",
 162            generics.repr(tcx), substs.repr(tcx));
 163
 164     let mut obligations = VecPerParamSpace::empty();
 165
 166     for def in generics.types.iter() {
 167         push_obligations_for_param_bounds(tcx,
 168                                           cause,
 169                                           recursion_depth,
 170                                           def.space,
 171                                           def.index,
 172                                           &def.bounds,
 173                                           substs,
 174                                           &mut obligations);
 175     }
 176
 177     debug!("obligations() ==> {}", obligations.repr(tcx));
 178
 179     return obligations;
 180 }
 181
 182 fn push_obligations_for_param_bounds(
 183     tcx: &ty::ctxt,
 184     cause: ObligationCause,
 185     recursion_depth: uint,
 186     space: subst::ParamSpace,
 187     index: uint,
 188     param_bounds: &ty::ParamBounds,
 189     param_substs: &Substs,
 190     obligations: &mut VecPerParamSpace<Obligation>)
 191 {
 192     let param_ty = *param_substs.types.get(space, index);
 193
 194     for builtin_bound in param_bounds.builtin_bounds.iter() {
 195         obligations.push(
 196             space,
 197             obligation_for_builtin_bound(tcx,
 198                                          cause,
 199                                          builtin_bound,
 200                                          recursion_depth,
 201                                          param_ty));
 202     }
 203
 204     for bound_trait_ref in param_bounds.trait_bounds.iter() {
 205         let bound_trait_ref = bound_trait_ref.subst(tcx, param_substs);
 206         obligations.push(
 207             space,
 208             Obligation { cause: cause,
 209                          recursion_depth: recursion_depth,
 210                          trait_ref: bound_trait_ref });
 211     }
 212 }
 213
 214 pub fn obligation_for_builtin_bound(
 215     tcx: &ty::ctxt,
 216     cause: ObligationCause,
 217     builtin_bound: ty::BuiltinBound,
 218     recursion_depth: uint,
 219     param_ty: ty::t)
 220     -> Obligation
 221 {
 222     match tcx.lang_items.from_builtin_kind(builtin_bound) {
 223         Ok(def_id) => {
 224             Obligation {
 225                 cause: cause,
 226                 recursion_depth: recursion_depth,
 227                 trait_ref: Rc::new(ty::TraitRef {
 228                     def_id: def_id,
 229                     substs: Substs::empty().with_self_ty(param_ty),
 230                 }),
 231             }
 232         }
 233         Err(e) => {
 234             tcx.sess.span_bug(cause.span, e.as_slice());
 235         }
 236     }
 237 }
 238
 239 pub fn search_trait_and_supertraits_from_bound(tcx: &ty::ctxt,
 240                                                caller_bound: Rc<ty::TraitRef>,
 241                                                test: |ast::DefId| -> bool)
 242                                                -> Option<VtableParamData>
 243 {
 244     /*!
 245      * Starting from a caller obligation `caller_bound` (which has
 246      * coordinates `space`/`i` in the list of caller obligations),
 247      * search through the trait and supertraits to find one where
 248      * `test(d)` is true, where `d` is the def-id of the
 249      * trait/supertrait.  If any is found, return `Some(p)` where `p`
 250      * is the path to that trait/supertrait. Else `None`.
 251      */
 252
 253     for bound in transitive_bounds(tcx, &[caller_bound]) {
 254         if test(bound.def_id) {
 255             let vtable_param = VtableParamData { bound: bound };
 256             return Some(vtable_param);
 257         }
 258     }
 259
 260     return None;
 261 }
 262
 263 impl Repr for super::Obligation {
 264     fn repr(&self, tcx: &ty::ctxt) -> String {
 265         format!("Obligation(trait_ref={},depth={})",
 266                 self.trait_ref.repr(tcx),
 267                 self.recursion_depth)
 268     }
 269 }
 270
 271 impl<N:Repr> Repr for super::Vtable<N> {
 272     fn repr(&self, tcx: &ty::ctxt) -> String {
 273         match *self {
 274             super::VtableImpl(ref v) =>
 275                 v.repr(tcx),
 276
 277             super::VtableUnboxedClosure(ref d) =>
 278                 format!("VtableUnboxedClosure({})",
 279                         d.repr(tcx)),
 280
 281             super::VtableParam(ref v) =>
 282                 format!("VtableParam({})", v.repr(tcx)),
 283
 284             super::VtableBuiltin =>
 285                 format!("Builtin"),
 286         }
 287     }
 288 }
 289
 290 impl<N:Repr> Repr for super::VtableImplData<N> {
 291     fn repr(&self, tcx: &ty::ctxt) -> String {
 292         format!("VtableImpl(impl_def_id={}, substs={}, nested={})",
 293                 self.impl_def_id.repr(tcx),
 294                 self.substs.repr(tcx),
 295                 self.nested.repr(tcx))
 296     }
 297 }
 298
 299 impl Repr for super::VtableParamData {
 300     fn repr(&self, tcx: &ty::ctxt) -> String {
 301         format!("VtableParam(bound={})",
 302                 self.bound.repr(tcx))
 303     }
 304 }
 305
 306 impl Repr for super::SelectionError {
 307     fn repr(&self, tcx: &ty::ctxt) -> String {
 308         match *self {
 309             super::Unimplemented =>
 310                 format!("Unimplemented"),
 311
 312             super::Overflow =>
 313                 format!("Overflow"),
 314
 315             super::OutputTypeParameterMismatch(ref t, ref e) =>
 316                 format!("OutputTypeParameterMismatch({}, {})",
 317                         t.repr(tcx),
 318                         e.repr(tcx)),
 319         }
 320     }
 321 }
 322
 323 impl Repr for super::FulfillmentError {
 324     fn repr(&self, tcx: &ty::ctxt) -> String {
 325         format!("FulfillmentError({},{})",
 326                 self.obligation.repr(tcx),
 327                 self.code.repr(tcx))
 328     }
 329 }
 330
 331 impl Repr for super::FulfillmentErrorCode {
 332     fn repr(&self, tcx: &ty::ctxt) -> String {
 333         match *self {
 334             super::CodeSelectionError(ref o) => o.repr(tcx),
 335             super::CodeAmbiguity => format!("Ambiguity")
 336         }
 337     }
 338 }
 339
 340 impl fmt::Show for super::FulfillmentErrorCode {
 341     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 342         match *self {
 343             super::CodeSelectionError(ref e) => write!(f, "{}", e),
 344             super::CodeAmbiguity => write!(f, "Ambiguity")
 345         }
 346     }
 347 }
 348
 349 impl Repr for ty::type_err {
 350     fn repr(&self, tcx: &ty::ctxt) -> String {
 351         ty::type_err_to_str(tcx, self)
 352     }
 353 }
 354