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;
  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     /// Various flags
  63     pub flags: Cell<TraitFlags>
  64 }
  65
  66 impl<'tcx> TraitDef<'tcx> {
  67     pub fn new(unsafety: hir::Unsafety,
  68                paren_sugar: bool,
  69                generics: ty::Generics<'tcx>,
  70                trait_ref: ty::TraitRef<'tcx>,
  71                associated_type_names: Vec<Name>)
  72                -> TraitDef<'tcx> {
  73         TraitDef {
  74             paren_sugar: paren_sugar,
  75             unsafety: unsafety,
  76             generics: generics,
  77             trait_ref: trait_ref,
  78             associated_type_names: associated_type_names,
  79             nonblanket_impls: RefCell::new(FnvHashMap()),
  80             blanket_impls: RefCell::new(vec![]),
  81             flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS)
  82         }
  83     }
  84
  85     pub fn def_id(&self) -> DefId {
  86         self.trait_ref.def_id
  87     }
  88
  89     // returns None if not yet calculated
  90     pub fn object_safety(&self) -> Option<bool> {
  91         if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) {
  92             Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE))
  93         } else {
  94             None
  95         }
  96     }
  97
  98     pub fn set_object_safety(&self, is_safe: bool) {
  99         assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true));
 100         self.flags.set(
 101             self.flags.get() | if is_safe {
 102                 TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE
 103             } else {
 104                 TraitFlags::OBJECT_SAFETY_VALID
 105             }
 106         );
 107     }
 108
 109     fn write_trait_impls(&self, tcx: &ty::ctxt<'tcx>) {
 110         tcx.dep_graph.write(DepNode::TraitImpls(self.trait_ref.def_id));
 111     }
 112
 113     fn read_trait_impls(&self, tcx: &ty::ctxt<'tcx>) {
 114         tcx.dep_graph.read(DepNode::TraitImpls(self.trait_ref.def_id));
 115     }
 116
 117     /// Records a trait-to-implementation mapping.
 118     pub fn record_impl(&self,
 119                        tcx: &ty::ctxt<'tcx>,
 120                        impl_def_id: DefId,
 121                        impl_trait_ref: ty::TraitRef<'tcx>) {
 122         debug!("TraitDef::record_impl for {:?}, from {:?}",
 123                self, impl_trait_ref);
 124
 125         // Record the write into the impl set, but only for local
 126         // impls: external impls are handled differently.
 127         if impl_def_id.is_local() {
 128             self.write_trait_impls(tcx);
 129         }
 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 // 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 // duplicate - skip
 145             }
 146             self.blanket_impls.borrow_mut().push(impl_def_id)
 147         }
 148     }
 149
 150     pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: &ty::ctxt<'tcx>, mut f: F)  {
 151         self.read_trait_impls(tcx);
 152
 153         tcx.populate_implementations_for_trait_if_necessary(self.trait_ref.def_id);
 154
 155         for &impl_def_id in self.blanket_impls.borrow().iter() {
 156             f(impl_def_id);
 157         }
 158
 159         for v in self.nonblanket_impls.borrow().values() {
 160             for &impl_def_id in v {
 161                 f(impl_def_id);
 162             }
 163         }
 164     }
 165
 166     /// Iterate over every impl that could possibly match the
 167     /// self-type `self_ty`.
 168     pub fn for_each_relevant_impl<F: FnMut(DefId)>(&self,
 169                                                    tcx: &ty::ctxt<'tcx>,
 170                                                    self_ty: Ty<'tcx>,
 171                                                    mut f: F)
 172     {
 173         self.read_trait_impls(tcx);
 174
 175         tcx.populate_implementations_for_trait_if_necessary(self.trait_ref.def_id);
 176
 177         for &impl_def_id in self.blanket_impls.borrow().iter() {
 178             f(impl_def_id);
 179         }
 180
 181         // simplify_type(.., false) basically replaces type parameters and
 182         // projections with infer-variables. This is, of course, done on
 183         // the impl trait-ref when it is instantiated, but not on the
 184         // predicate trait-ref which is passed here.
 185         //
 186         // for example, if we match `S: Copy` against an impl like
 187         // `impl<T:Copy> Copy for Option<T>`, we replace the type variable
 188         // in `Option<T>` with an infer variable, to `Option<_>` (this
 189         // doesn't actually change fast_reject output), but we don't
 190         // replace `S` with anything - this impl of course can't be
 191         // selected, and as there are hundreds of similar impls,
 192         // considering them would significantly harm performance.
 193         if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, true) {
 194             if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) {
 195                 for &impl_def_id in impls {
 196                     f(impl_def_id);
 197                 }
 198             }
 199         } else {
 200             for v in self.nonblanket_impls.borrow().values() {
 201                 for &impl_def_id in v {
 202                     f(impl_def_id);
 203                 }
 204             }
 205         }
 206     }
 207
 208     pub fn borrow_impl_lists<'s>(&'s self, tcx: &ty::ctxt<'tcx>)
 209                                  -> (Ref<'s, Vec<DefId>>,
 210                                      Ref<'s, FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>>) {
 211         self.read_trait_impls(tcx);
 212         (self.blanket_impls.borrow(), self.nonblanket_impls.borrow())
 213     }
 214
 215 }
 216
 217 bitflags! {
 218     flags TraitFlags: u32 {
 219         const NO_TRAIT_FLAGS        = 0,
 220         const HAS_DEFAULT_IMPL      = 1 << 0,
 221         const IS_OBJECT_SAFE        = 1 << 1,
 222         const OBJECT_SAFETY_VALID   = 1 << 2,
 223         const IMPLS_VALID           = 1 << 3,
 224     }
 225 }
 226