]> git.proxmox.com Git - rustc.git/blob - src/librustc/ty/trait_def.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / 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 }