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