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