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