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