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.
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.
11 use dep_graph::DepNode;
12 use hir::def_id::DefId;
13 use traits::{self, specialization_graph};
16 use ty::{Ty, TyCtxt, TraitRef};
17 use std::cell::{Cell, RefCell};
19 use util::nodemap::FxHashMap;
21 /// A trait's definition with type information.
25 pub unsafety: hir::Unsafety,
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,
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`.
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.
42 // FIXME: solve the reentrancy issues and remove these lists in favor of the
43 // ones in `specialization_graph`.
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.
49 /// Impls of the trait.
50 nonblanket_impls: RefCell<
51 FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>
54 /// Blanket impls associated with the trait.
55 blanket_impls: RefCell<Vec<DefId>>,
57 /// The specialization order for impls of this trait.
58 pub specialization_graph: RefCell<traits::specialization_graph::Graph>,
61 pub flags: Cell<TraitFlags>,
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,
68 impl<'a, 'gcx, 'tcx> TraitDef {
69 pub fn new(def_id: DefId,
70 unsafety: hir::Unsafety,
76 paren_sugar: paren_sugar,
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,
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))
95 pub fn set_object_safety(&self, is_safe: bool) {
96 assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true));
98 self.flags.get() | if is_safe {
99 TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE
101 TraitFlags::OBJECT_SAFETY_VALID
106 fn write_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) {
107 tcx.dep_graph.write(DepNode::TraitImpls(self.def_id));
110 fn read_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) {
111 tcx.dep_graph.read(DepNode::TraitImpls(self.def_id));
114 /// Records a basic trait-to-implementation mapping.
116 /// Returns `true` iff the impl has not previously been recorded.
117 fn record_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
119 impl_trait_ref: TraitRef<'tcx>)
121 debug!("TraitDef::record_impl for {:?}, from {:?}",
122 self, impl_trait_ref);
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);
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
140 self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id)
142 if self.blanket_impls.borrow().contains(&impl_def_id) {
143 return false; // duplicate - skip
145 self.blanket_impls.borrow_mut().push(impl_def_id)
151 /// Records a trait-to-implementation mapping for a crate-local impl.
152 pub fn record_local_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
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);
160 /// Records a trait-to-implementation mapping for a non-local impl.
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>,
167 impl_trait_ref: TraitRef<'tcx>,
168 parent_impl: DefId) {
169 assert!(!impl_def_id.is_local());
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)
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
183 pub fn add_impl_for_specialization(&self,
184 tcx: TyCtxt<'a, 'gcx, 'tcx>,
186 -> Result<(), traits::OverlapError> {
187 assert!(impl_def_id.is_local());
189 self.specialization_graph.borrow_mut()
190 .insert(tcx, impl_def_id)
193 pub fn ancestors(&'a self, of_impl: DefId) -> specialization_graph::Ancestors<'a> {
194 specialization_graph::ancestors(self, of_impl)
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);
201 for &impl_def_id in self.blanket_impls.borrow().iter() {
205 for v in self.nonblanket_impls.borrow().values() {
206 for &impl_def_id in v {
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>,
219 self.read_trait_impls(tcx);
221 tcx.populate_implementations_for_trait_if_necessary(self.def_id);
223 for &impl_def_id in self.blanket_impls.borrow().iter() {
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.
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 {
246 for v in self.nonblanket_impls.borrow().values() {
247 for &impl_def_id in v {
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,