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