src/librustc/ty/trait_def.rs

   1 // Copyright 2012-2015 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 use dep_graph::DepNode;
  12 use hir::def_id::DefId;
  13 use traits::{self, specialization_graph};
  14 use ty;
  15 use ty::fast_reject;
  16 use ty::{Ty, TyCtxt, TraitRef};
  17 use std::cell::{Cell, RefCell};
  18 use hir;
  19 use util::nodemap::FxHashMap;
  20
  21 /// A trait's definition with type information.
  22 pub struct TraitDef {
  23     pub def_id: DefId,
  24
  25     pub unsafety: hir::Unsafety,
  26
  27     /// If `true`, then this trait had the `#[rustc_paren_sugar]`
  28     /// attribute, indicating that it should be used with `Foo()`
  29     /// sugar. This is a temporary thing -- eventually any trait will
  30     /// be usable with the sugar (or without it).
  31     pub paren_sugar: bool,
  32
  33     // Impls of a trait. To allow for quicker lookup, the impls are indexed by a
  34     // simplified version of their `Self` type: impls with a simplifiable `Self`
  35     // are stored in `nonblanket_impls` keyed by it, while all other impls are
  36     // stored in `blanket_impls`.
  37     //
  38     // A similar division is used within `specialization_graph`, but the ones
  39     // here are (1) stored as a flat list for the trait and (2) populated prior
  40     // to -- and used while -- determining specialization order.
  41     //
  42     // FIXME: solve the reentrancy issues and remove these lists in favor of the
  43     // ones in `specialization_graph`.
  44     //
  45     // These lists are tracked by `DepNode::TraitImpls`; we don't use
  46     // a DepTrackingMap but instead have the `TraitDef` insert the
  47     // required reads/writes.
  48
  49     /// Impls of the trait.
  50     nonblanket_impls: RefCell<
  51         FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>
  52     >,
  53
  54     /// Blanket impls associated with the trait.
  55     blanket_impls: RefCell<Vec<DefId>>,
  56
  57     /// The specialization order for impls of this trait.
  58     pub specialization_graph: RefCell<traits::specialization_graph::Graph>,
  59
  60     /// Various flags
  61     pub flags: Cell<TraitFlags>,
  62
  63     /// The ICH of this trait's DefPath, cached here so it doesn't have to be
  64     /// recomputed all the time.
  65     pub def_path_hash: u64,
  66 }
  67
  68 impl<'a, 'gcx, 'tcx> TraitDef {
  69     pub fn new(def_id: DefId,
  70                unsafety: hir::Unsafety,
  71                paren_sugar: bool,
  72                def_path_hash: u64)
  73                -> TraitDef {
  74         TraitDef {
  75             def_id: def_id,
  76             paren_sugar: paren_sugar,
  77             unsafety: unsafety,
  78             nonblanket_impls: RefCell::new(FxHashMap()),
  79             blanket_impls: RefCell::new(vec![]),
  80             flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS),
  81             specialization_graph: RefCell::new(traits::specialization_graph::Graph::new()),
  82             def_path_hash: def_path_hash,
  83         }
  84     }
  85
  86     // returns None if not yet calculated
  87     pub fn object_safety(&self) -> Option<bool> {
  88         if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) {
  89             Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE))
  90         } else {
  91             None
  92         }
  93     }
  94
  95     pub fn set_object_safety(&self, is_safe: bool) {
  96         assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true));
  97         self.flags.set(
  98             self.flags.get() | if is_safe {
  99                 TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE
 100             } else {
 101                 TraitFlags::OBJECT_SAFETY_VALID
 102             }
 103         );
 104     }
 105
 106     fn write_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) {
 107         tcx.dep_graph.write(DepNode::TraitImpls(self.def_id));
 108     }
 109
 110     fn read_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) {
 111         tcx.dep_graph.read(DepNode::TraitImpls(self.def_id));
 112     }
 113
 114     /// Records a basic trait-to-implementation mapping.
 115     ///
 116     /// Returns `true` iff the impl has not previously been recorded.
 117     fn record_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 118                    impl_def_id: DefId,
 119                    impl_trait_ref: TraitRef<'tcx>)
 120                    -> bool {
 121         debug!("TraitDef::record_impl for {:?}, from {:?}",
 122                self, impl_trait_ref);
 123
 124         // Record the write into the impl set, but only for local
 125         // impls: external impls are handled differently.
 126         if impl_def_id.is_local() {
 127             self.write_trait_impls(tcx);
 128         }
 129
 130         // We don't want to borrow_mut after we already populated all impls,
 131         // so check if an impl is present with an immutable borrow first.
 132         if let Some(sty) = fast_reject::simplify_type(tcx,
 133                                                       impl_trait_ref.self_ty(), false) {
 134             if let Some(is) = self.nonblanket_impls.borrow().get(&sty) {
 135                 if is.contains(&impl_def_id) {
 136                     return false; // duplicate - skip
 137                 }
 138             }
 139
 140             self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id)
 141         } else {
 142             if self.blanket_impls.borrow().contains(&impl_def_id) {
 143                 return false; // duplicate - skip
 144             }
 145             self.blanket_impls.borrow_mut().push(impl_def_id)
 146         }
 147
 148         true
 149     }
 150
 151     /// Records a trait-to-implementation mapping for a crate-local impl.
 152     pub fn record_local_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 153                              impl_def_id: DefId,
 154                              impl_trait_ref: TraitRef<'tcx>) {
 155         assert!(impl_def_id.is_local());
 156         let was_new = self.record_impl(tcx, impl_def_id, impl_trait_ref);
 157         assert!(was_new);
 158     }
 159
 160     /// Records a trait-to-implementation mapping for a non-local impl.
 161     ///
 162     /// The `parent_impl` is the immediately-less-specialized impl, or the
 163     /// trait's def ID if the impl is not a specialization -- information that
 164     /// should be pulled from the metadata.
 165     pub fn record_remote_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 166                               impl_def_id: DefId,
 167                               impl_trait_ref: TraitRef<'tcx>,
 168                               parent_impl: DefId) {
 169         assert!(!impl_def_id.is_local());
 170
 171         // if the impl has not previously been recorded
 172         if self.record_impl(tcx, impl_def_id, impl_trait_ref) {
 173             // if the impl is non-local, it's placed directly into the
 174             // specialization graph using parent information drawn from metadata.
 175             self.specialization_graph.borrow_mut()
 176                 .record_impl_from_cstore(tcx, parent_impl, impl_def_id)
 177         }
 178     }
 179
 180     /// Adds a local impl into the specialization graph, returning an error with
 181     /// overlap information if the impl overlaps but does not specialize an
 182     /// existing impl.
 183     pub fn add_impl_for_specialization(&self,
 184                                        tcx: TyCtxt<'a, 'gcx, 'tcx>,
 185                                        impl_def_id: DefId)
 186                                        -> Result<(), traits::OverlapError> {
 187         assert!(impl_def_id.is_local());
 188
 189         self.specialization_graph.borrow_mut()
 190             .insert(tcx, impl_def_id)
 191     }
 192
 193     pub fn ancestors(&'a self, of_impl: DefId) -> specialization_graph::Ancestors<'a> {
 194         specialization_graph::ancestors(self, of_impl)
 195     }
 196
 197     pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, mut f: F) {
 198         self.read_trait_impls(tcx);
 199         tcx.populate_implementations_for_trait_if_necessary(self.def_id);
 200
 201         for &impl_def_id in self.blanket_impls.borrow().iter() {
 202             f(impl_def_id);
 203         }
 204
 205         for v in self.nonblanket_impls.borrow().values() {
 206             for &impl_def_id in v {
 207                 f(impl_def_id);
 208             }
 209         }
 210     }
 211
 212     /// Iterate over every impl that could possibly match the
 213     /// self-type `self_ty`.
 214     pub fn for_each_relevant_impl<F: FnMut(DefId)>(&self,
 215                                                    tcx: TyCtxt<'a, 'gcx, 'tcx>,
 216                                                    self_ty: Ty<'tcx>,
 217                                                    mut f: F)
 218     {
 219         self.read_trait_impls(tcx);
 220
 221         tcx.populate_implementations_for_trait_if_necessary(self.def_id);
 222
 223         for &impl_def_id in self.blanket_impls.borrow().iter() {
 224             f(impl_def_id);
 225         }
 226
 227         // simplify_type(.., false) basically replaces type parameters and
 228         // projections with infer-variables. This is, of course, done on
 229         // the impl trait-ref when it is instantiated, but not on the
 230         // predicate trait-ref which is passed here.
 231         //
 232         // for example, if we match `S: Copy` against an impl like
 233         // `impl<T:Copy> Copy for Option<T>`, we replace the type variable
 234         // in `Option<T>` with an infer variable, to `Option<_>` (this
 235         // doesn't actually change fast_reject output), but we don't
 236         // replace `S` with anything - this impl of course can't be
 237         // selected, and as there are hundreds of similar impls,
 238         // considering them would significantly harm performance.
 239         if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, true) {
 240             if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) {
 241                 for &impl_def_id in impls {
 242                     f(impl_def_id);
 243                 }
 244             }
 245         } else {
 246             for v in self.nonblanket_impls.borrow().values() {
 247                 for &impl_def_id in v {
 248                     f(impl_def_id);
 249                 }
 250             }
 251         }
 252     }
 253 }
 254
 255 bitflags! {
 256     flags TraitFlags: u32 {
 257         const NO_TRAIT_FLAGS        = 0,
 258         const HAS_DEFAULT_IMPL      = 1 << 0,
 259         const IS_OBJECT_SAFE        = 1 << 1,
 260         const OBJECT_SAFETY_VALID   = 1 << 2,
 261         const IMPLS_VALID           = 1 << 3,
 262     }
 263 }