]> git.proxmox.com Git - rustc.git/blob - src/librustc/traits/specialize/specialization_graph.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / traits / specialize / specialization_graph.rs
1 // Copyright 2016 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 std::cell;
12 use std::rc::Rc;
13
14 use super::{Overlap, specializes};
15
16 use middle::cstore::CrateStore;
17 use hir::def_id::DefId;
18 use infer;
19 use traits::{self, ProjectionMode};
20 use ty::{self, TyCtxt, ImplOrTraitItem, TraitDef, TypeFoldable};
21 use ty::fast_reject::{self, SimplifiedType};
22 use syntax::ast::Name;
23 use util::nodemap::{DefIdMap, FnvHashMap};
24
25 /// A per-trait graph of impls in specialization order. At the moment, this
26 /// graph forms a tree rooted with the trait itself, with all other nodes
27 /// representing impls, and parent-child relationships representing
28 /// specializations.
29 ///
30 /// The graph provides two key services:
31 ///
32 /// - Construction, which implicitly checks for overlapping impls (i.e., impls
33 /// that overlap but where neither specializes the other -- an artifact of the
34 /// simple "chain" rule.
35 ///
36 /// - Parent extraction. In particular, the graph can give you the *immediate*
37 /// parents of a given specializing impl, which is needed for extracting
38 /// default items amongst other thigns. In the simple "chain" rule, every impl
39 /// has at most one parent.
40 pub struct Graph {
41 // all impls have a parent; the "root" impls have as their parent the def_id
42 // of the trait
43 parent: DefIdMap<DefId>,
44
45 // the "root" impls are found by looking up the trait's def_id.
46 children: DefIdMap<Children>,
47 }
48
49 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
50 /// done in `TraitDef`.
51 struct Children {
52 // Impls of a trait (or specializations of a given impl). To allow for
53 // quicker lookup, the impls are indexed by a simplified version of their
54 // `Self` type: impls with a simplifiable `Self` are stored in
55 // `nonblanket_impls` keyed by it, while all other impls are stored in
56 // `blanket_impls`.
57 //
58 // A similar division is used within `TraitDef`, but the lists there collect
59 // together *all* the impls for a trait, and are populated prior to building
60 // the specialization graph.
61
62 /// Impls of the trait.
63 nonblanket_impls: FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>,
64
65 /// Blanket impls associated with the trait.
66 blanket_impls: Vec<DefId>,
67 }
68
69 /// The result of attempting to insert an impl into a group of children.
70 enum InsertResult<'a, 'tcx: 'a> {
71 /// The impl was inserted as a new child in this group of children.
72 BecameNewSibling,
73
74 /// The impl replaced an existing impl that specializes it.
75 Replaced(DefId),
76
77 /// The impl is a specialization of an existing child.
78 ShouldRecurseOn(DefId),
79
80 /// The impl has an unresolvable overlap with an existing child (neither
81 /// specializes the other).
82 Overlapped(Overlap<'a, 'tcx>),
83 }
84
85 impl Children {
86 fn new() -> Children {
87 Children {
88 nonblanket_impls: FnvHashMap(),
89 blanket_impls: vec![],
90 }
91 }
92
93 /// Insert an impl into this set of children without comparing to any existing impls
94 fn insert_blindly(&mut self, tcx: &TyCtxt, impl_def_id: DefId) {
95 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
96 if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) {
97 self.nonblanket_impls.entry(sty).or_insert(vec![]).push(impl_def_id)
98 } else {
99 self.blanket_impls.push(impl_def_id)
100 }
101 }
102
103 /// Attempt to insert an impl into this set of children, while comparing for
104 /// specialiation relationships.
105 fn insert<'a, 'tcx>(&mut self,
106 tcx: &'a TyCtxt<'tcx>,
107 impl_def_id: DefId,
108 simplified_self: Option<SimplifiedType>)
109 -> InsertResult<'a, 'tcx>
110 {
111 for slot in match simplified_self {
112 Some(sty) => self.filtered_mut(sty),
113 None => self.iter_mut(),
114 } {
115 let possible_sibling = *slot;
116
117 let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, ProjectionMode::Topmost);
118 let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id);
119
120 if let Some(impl_header) = overlap {
121 let le = specializes(tcx, impl_def_id, possible_sibling);
122 let ge = specializes(tcx, possible_sibling, impl_def_id);
123
124 if le && !ge {
125 debug!("descending as child of TraitRef {:?}",
126 tcx.impl_trait_ref(possible_sibling).unwrap());
127
128 // the impl specializes possible_sibling
129 return InsertResult::ShouldRecurseOn(possible_sibling);
130 } else if ge && !le {
131 debug!("placing as parent of TraitRef {:?}",
132 tcx.impl_trait_ref(possible_sibling).unwrap());
133
134 // possible_sibling specializes the impl
135 *slot = impl_def_id;
136 return InsertResult::Replaced(possible_sibling);
137 } else {
138 // overlap, but no specialization; error out
139 return InsertResult::Overlapped(Overlap {
140 with_impl: possible_sibling,
141 on_trait_ref: impl_header.trait_ref.unwrap(),
142 in_context: infcx,
143 });
144 }
145 }
146 }
147
148 // no overlap with any potential siblings, so add as a new sibling
149 debug!("placing as new sibling");
150 self.insert_blindly(tcx, impl_def_id);
151 InsertResult::BecameNewSibling
152 }
153
154 fn iter_mut<'a>(&'a mut self) -> Box<Iterator<Item = &'a mut DefId> + 'a> {
155 let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter_mut());
156 Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
157 }
158
159 fn filtered_mut<'a>(&'a mut self, sty: SimplifiedType)
160 -> Box<Iterator<Item = &'a mut DefId> + 'a> {
161 let nonblanket = self.nonblanket_impls.entry(sty).or_insert(vec![]).iter_mut();
162 Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
163 }
164 }
165
166 impl Graph {
167 pub fn new() -> Graph {
168 Graph {
169 parent: Default::default(),
170 children: Default::default(),
171 }
172 }
173
174 /// Insert a local impl into the specialization graph. If an existing impl
175 /// conflicts with it (has overlap, but neither specializes the other),
176 /// information about the area of overlap is returned in the `Err`.
177 pub fn insert<'a, 'tcx>(&mut self,
178 tcx: &'a TyCtxt<'tcx>,
179 impl_def_id: DefId)
180 -> Result<(), Overlap<'a, 'tcx>> {
181 assert!(impl_def_id.is_local());
182
183 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
184 let trait_def_id = trait_ref.def_id;
185
186 debug!("insert({:?}): inserting TraitRef {:?} into specialization graph",
187 impl_def_id, trait_ref);
188
189 // if the reference itself contains an earlier error (e.g., due to a
190 // resolution failure), then we just insert the impl at the top level of
191 // the graph and claim that there's no overlap (in order to supress
192 // bogus errors).
193 if trait_ref.references_error() {
194 debug!("insert: inserting dummy node for erroneous TraitRef {:?}, \
195 impl_def_id={:?}, trait_def_id={:?}",
196 trait_ref, impl_def_id, trait_def_id);
197
198 self.parent.insert(impl_def_id, trait_def_id);
199 self.children.entry(trait_def_id).or_insert(Children::new())
200 .insert_blindly(tcx, impl_def_id);
201 return Ok(());
202 }
203
204 let mut parent = trait_def_id;
205 let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
206
207 // Descend the specialization tree, where `parent` is the current parent node
208 loop {
209 use self::InsertResult::*;
210
211 let insert_result = self.children.entry(parent).or_insert(Children::new())
212 .insert(tcx, impl_def_id, simplified);
213
214 match insert_result {
215 BecameNewSibling => {
216 break;
217 }
218 Replaced(new_child) => {
219 self.parent.insert(new_child, impl_def_id);
220 let mut new_children = Children::new();
221 new_children.insert_blindly(tcx, new_child);
222 self.children.insert(impl_def_id, new_children);
223 break;
224 }
225 ShouldRecurseOn(new_parent) => {
226 parent = new_parent;
227 }
228 Overlapped(error) => {
229 return Err(error);
230 }
231 }
232 }
233
234 self.parent.insert(impl_def_id, parent);
235 Ok(())
236 }
237
238 /// Insert cached metadata mapping from a child impl back to its parent.
239 pub fn record_impl_from_cstore(&mut self, tcx: &TyCtxt, parent: DefId, child: DefId) {
240 if self.parent.insert(child, parent).is_some() {
241 bug!("When recording an impl from the crate store, information about its parent \
242 was already present.");
243 }
244
245 self.children.entry(parent).or_insert(Children::new()).insert_blindly(tcx, child);
246 }
247
248 /// The parent of a given impl, which is the def id of the trait when the
249 /// impl is a "specialization root".
250 pub fn parent(&self, child: DefId) -> DefId {
251 *self.parent.get(&child).unwrap()
252 }
253 }
254
255 /// A node in the specialization graph is either an impl or a trait
256 /// definition; either can serve as a source of item definitions.
257 /// There is always exactly one trait definition node: the root.
258 #[derive(Debug, Copy, Clone)]
259 pub enum Node {
260 Impl(DefId),
261 Trait(DefId),
262 }
263
264 impl Node {
265 pub fn is_from_trait(&self) -> bool {
266 match *self {
267 Node::Trait(..) => true,
268 _ => false,
269 }
270 }
271
272 /// Iterate over the items defined directly by the given (impl or trait) node.
273 pub fn items<'a, 'tcx>(&self, tcx: &'a TyCtxt<'tcx>) -> NodeItems<'a, 'tcx> {
274 match *self {
275 Node::Impl(impl_def_id) => {
276 NodeItems::Impl {
277 tcx: tcx,
278 items: cell::Ref::map(tcx.impl_items.borrow(),
279 |impl_items| &impl_items[&impl_def_id]),
280 idx: 0,
281 }
282 }
283 Node::Trait(trait_def_id) => {
284 NodeItems::Trait {
285 items: tcx.trait_items(trait_def_id).clone(),
286 idx: 0,
287 }
288 }
289 }
290 }
291
292 pub fn def_id(&self) -> DefId {
293 match *self {
294 Node::Impl(did) => did,
295 Node::Trait(did) => did,
296 }
297 }
298 }
299
300 /// An iterator over the items defined within a trait or impl.
301 pub enum NodeItems<'a, 'tcx: 'a> {
302 Impl {
303 tcx: &'a TyCtxt<'tcx>,
304 items: cell::Ref<'a, Vec<ty::ImplOrTraitItemId>>,
305 idx: usize,
306 },
307 Trait {
308 items: Rc<Vec<ImplOrTraitItem<'tcx>>>,
309 idx: usize,
310 },
311 }
312
313 impl<'a, 'tcx> Iterator for NodeItems<'a, 'tcx> {
314 type Item = ImplOrTraitItem<'tcx>;
315 fn next(&mut self) -> Option<ImplOrTraitItem<'tcx>> {
316 match *self {
317 NodeItems::Impl { tcx, ref items, ref mut idx } => {
318 let items_table = tcx.impl_or_trait_items.borrow();
319 if *idx < items.len() {
320 let item_def_id = items[*idx].def_id();
321 let item = items_table[&item_def_id].clone();
322 *idx += 1;
323 Some(item)
324 } else {
325 None
326 }
327 }
328 NodeItems::Trait { ref items, ref mut idx } => {
329 if *idx < items.len() {
330 let item = items[*idx].clone();
331 *idx += 1;
332 Some(item)
333 } else {
334 None
335 }
336 }
337 }
338 }
339 }
340
341 pub struct Ancestors<'a, 'tcx: 'a> {
342 trait_def: &'a TraitDef<'tcx>,
343 current_source: Option<Node>,
344 }
345
346 impl<'a, 'tcx> Iterator for Ancestors<'a, 'tcx> {
347 type Item = Node;
348 fn next(&mut self) -> Option<Node> {
349 let cur = self.current_source.take();
350 if let Some(Node::Impl(cur_impl)) = cur {
351 let parent = self.trait_def.specialization_graph.borrow().parent(cur_impl);
352 if parent == self.trait_def.def_id() {
353 self.current_source = Some(Node::Trait(parent));
354 } else {
355 self.current_source = Some(Node::Impl(parent));
356 }
357 }
358 cur
359 }
360 }
361
362 pub struct NodeItem<T> {
363 pub node: Node,
364 pub item: T,
365 }
366
367 impl<T> NodeItem<T> {
368 pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
369 NodeItem {
370 node: self.node,
371 item: f(self.item),
372 }
373 }
374 }
375
376 pub struct TypeDefs<'a, 'tcx: 'a> {
377 // generally only invoked once or twice, so the box doesn't hurt
378 iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>> + 'a>,
379 }
380
381 impl<'a, 'tcx> Iterator for TypeDefs<'a, 'tcx> {
382 type Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>;
383 fn next(&mut self) -> Option<Self::Item> {
384 self.iter.next()
385 }
386 }
387
388 pub struct FnDefs<'a, 'tcx: 'a> {
389 // generally only invoked once or twice, so the box doesn't hurt
390 iter: Box<Iterator<Item = NodeItem<Rc<ty::Method<'tcx>>>> + 'a>,
391 }
392
393 impl<'a, 'tcx> Iterator for FnDefs<'a, 'tcx> {
394 type Item = NodeItem<Rc<ty::Method<'tcx>>>;
395 fn next(&mut self) -> Option<Self::Item> {
396 self.iter.next()
397 }
398 }
399
400 pub struct ConstDefs<'a, 'tcx: 'a> {
401 // generally only invoked once or twice, so the box doesn't hurt
402 iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>> + 'a>,
403 }
404
405 impl<'a, 'tcx> Iterator for ConstDefs<'a, 'tcx> {
406 type Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>;
407 fn next(&mut self) -> Option<Self::Item> {
408 self.iter.next()
409 }
410 }
411
412 impl<'a, 'tcx> Ancestors<'a, 'tcx> {
413 /// Search the items from the given ancestors, returning each type definition
414 /// with the given name.
415 pub fn type_defs(self, tcx: &'a TyCtxt<'tcx>, name: Name) -> TypeDefs<'a, 'tcx> {
416 let iter = self.flat_map(move |node| {
417 node.items(tcx)
418 .filter_map(move |item| {
419 if let ty::TypeTraitItem(assoc_ty) = item {
420 if assoc_ty.name == name {
421 return Some(NodeItem {
422 node: node,
423 item: assoc_ty,
424 });
425 }
426 }
427 None
428 })
429
430 });
431 TypeDefs { iter: Box::new(iter) }
432 }
433
434 /// Search the items from the given ancestors, returning each fn definition
435 /// with the given name.
436 pub fn fn_defs(self, tcx: &'a TyCtxt<'tcx>, name: Name) -> FnDefs<'a, 'tcx> {
437 let iter = self.flat_map(move |node| {
438 node.items(tcx)
439 .filter_map(move |item| {
440 if let ty::MethodTraitItem(method) = item {
441 if method.name == name {
442 return Some(NodeItem {
443 node: node,
444 item: method,
445 });
446 }
447 }
448 None
449 })
450
451 });
452 FnDefs { iter: Box::new(iter) }
453 }
454
455 /// Search the items from the given ancestors, returning each const
456 /// definition with the given name.
457 pub fn const_defs(self, tcx: &'a TyCtxt<'tcx>, name: Name) -> ConstDefs<'a, 'tcx> {
458 let iter = self.flat_map(move |node| {
459 node.items(tcx)
460 .filter_map(move |item| {
461 if let ty::ConstTraitItem(konst) = item {
462 if konst.name == name {
463 return Some(NodeItem {
464 node: node,
465 item: konst,
466 });
467 }
468 }
469 None
470 })
471
472 });
473 ConstDefs { iter: Box::new(iter) }
474 }
475 }
476
477 /// Walk up the specialization ancestors of a given impl, starting with that
478 /// impl itself.
479 pub fn ancestors<'a, 'tcx>(trait_def: &'a TraitDef<'tcx>,
480 start_from_impl: DefId)
481 -> Ancestors<'a, 'tcx> {
482 Ancestors {
483 trait_def: trait_def,
484 current_source: Some(Node::Impl(start_from_impl)),
485 }
486 }