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