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.
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 super::{OverlapError, specializes};
13 use hir::def_id::DefId;
14 use traits::{self, Reveal};
15 use ty::{self, TyCtxt, TraitDef, TypeFoldable};
16 use ty::fast_reject::{self, SimplifiedType};
17 use syntax::ast::Name;
18 use util::nodemap::{DefIdMap, FxHashMap};
20 /// A per-trait graph of impls in specialization order. At the moment, this
21 /// graph forms a tree rooted with the trait itself, with all other nodes
22 /// representing impls, and parent-child relationships representing
25 /// The graph provides two key services:
27 /// - Construction, which implicitly checks for overlapping impls (i.e., impls
28 /// that overlap but where neither specializes the other -- an artifact of the
29 /// simple "chain" rule.
31 /// - Parent extraction. In particular, the graph can give you the *immediate*
32 /// parents of a given specializing impl, which is needed for extracting
33 /// default items amongst other thigns. In the simple "chain" rule, every impl
34 /// has at most one parent.
36 // all impls have a parent; the "root" impls have as their parent the def_id
38 parent: DefIdMap<DefId>,
40 // the "root" impls are found by looking up the trait's def_id.
41 children: DefIdMap<Children>,
44 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
45 /// done in `TraitDef`.
47 // Impls of a trait (or specializations of a given impl). To allow for
48 // quicker lookup, the impls are indexed by a simplified version of their
49 // `Self` type: impls with a simplifiable `Self` are stored in
50 // `nonblanket_impls` keyed by it, while all other impls are stored in
53 // A similar division is used within `TraitDef`, but the lists there collect
54 // together *all* the impls for a trait, and are populated prior to building
55 // the specialization graph.
57 /// Impls of the trait.
58 nonblanket_impls: FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>,
60 /// Blanket impls associated with the trait.
61 blanket_impls: Vec<DefId>,
64 /// The result of attempting to insert an impl into a group of children.
66 /// The impl was inserted as a new child in this group of children.
69 /// The impl replaced an existing impl that specializes it.
72 /// The impl is a specialization of an existing child.
73 ShouldRecurseOn(DefId),
76 impl<'a, 'gcx, 'tcx> Children {
77 fn new() -> Children {
79 nonblanket_impls: FxHashMap(),
80 blanket_impls: vec![],
84 /// Insert an impl into this set of children without comparing to any existing impls
85 fn insert_blindly(&mut self,
86 tcx: TyCtxt<'a, 'gcx, 'tcx>,
88 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
89 if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) {
90 self.nonblanket_impls.entry(sty).or_insert(vec![]).push(impl_def_id)
92 self.blanket_impls.push(impl_def_id)
96 /// Attempt to insert an impl into this set of children, while comparing for
97 /// specialiation relationships.
99 tcx: TyCtxt<'a, 'gcx, 'tcx>,
101 simplified_self: Option<SimplifiedType>)
102 -> Result<Inserted, OverlapError>
104 for slot in match simplified_self {
105 Some(sty) => self.filtered_mut(sty),
106 None => self.iter_mut(),
108 let possible_sibling = *slot;
110 let tcx = tcx.global_tcx();
111 let (le, ge) = tcx.infer_ctxt((), Reveal::UserFacing).enter(|infcx| {
112 let overlap = traits::overlapping_impls(&infcx,
115 if let Some(impl_header) = overlap {
116 if tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
117 return Ok((false, false));
120 let le = specializes(tcx, impl_def_id, possible_sibling);
121 let ge = specializes(tcx, possible_sibling, impl_def_id);
124 // overlap, but no specialization; error out
125 let trait_ref = impl_header.trait_ref.unwrap();
126 let self_ty = trait_ref.self_ty();
128 with_impl: possible_sibling,
129 trait_desc: trait_ref.to_string(),
130 // only report the Self type if it has at least
131 // some outer concrete shell; otherwise, it's
132 // not adding much information.
133 self_desc: if self_ty.has_concrete_skeleton() {
134 Some(self_ty.to_string())
148 debug!("descending as child of TraitRef {:?}",
149 tcx.impl_trait_ref(possible_sibling).unwrap());
151 // the impl specializes possible_sibling
152 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
153 } else if ge && !le {
154 debug!("placing as parent of TraitRef {:?}",
155 tcx.impl_trait_ref(possible_sibling).unwrap());
157 // possible_sibling specializes the impl
159 return Ok(Inserted::Replaced(possible_sibling));
161 // no overlap (error bailed already via ?)
165 // no overlap with any potential siblings, so add as a new sibling
166 debug!("placing as new sibling");
167 self.insert_blindly(tcx, impl_def_id);
168 Ok(Inserted::BecameNewSibling)
171 fn iter_mut(&'a mut self) -> Box<Iterator<Item = &'a mut DefId> + 'a> {
172 let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter_mut());
173 Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
176 fn filtered_mut(&'a mut self, sty: SimplifiedType)
177 -> Box<Iterator<Item = &'a mut DefId> + 'a> {
178 let nonblanket = self.nonblanket_impls.entry(sty).or_insert(vec![]).iter_mut();
179 Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
183 impl<'a, 'gcx, 'tcx> Graph {
184 pub fn new() -> Graph {
186 parent: Default::default(),
187 children: Default::default(),
191 /// Insert a local impl into the specialization graph. If an existing impl
192 /// conflicts with it (has overlap, but neither specializes the other),
193 /// information about the area of overlap is returned in the `Err`.
194 pub fn insert(&mut self,
195 tcx: TyCtxt<'a, 'gcx, 'tcx>,
197 -> Result<(), OverlapError> {
198 assert!(impl_def_id.is_local());
200 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
201 let trait_def_id = trait_ref.def_id;
203 debug!("insert({:?}): inserting TraitRef {:?} into specialization graph",
204 impl_def_id, trait_ref);
206 // if the reference itself contains an earlier error (e.g., due to a
207 // resolution failure), then we just insert the impl at the top level of
208 // the graph and claim that there's no overlap (in order to supress
210 if trait_ref.references_error() {
211 debug!("insert: inserting dummy node for erroneous TraitRef {:?}, \
212 impl_def_id={:?}, trait_def_id={:?}",
213 trait_ref, impl_def_id, trait_def_id);
215 self.parent.insert(impl_def_id, trait_def_id);
216 self.children.entry(trait_def_id).or_insert(Children::new())
217 .insert_blindly(tcx, impl_def_id);
221 let mut parent = trait_def_id;
222 let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
224 // Descend the specialization tree, where `parent` is the current parent node
226 use self::Inserted::*;
228 let insert_result = self.children.entry(parent).or_insert(Children::new())
229 .insert(tcx, impl_def_id, simplified)?;
231 match insert_result {
232 BecameNewSibling => {
235 Replaced(new_child) => {
236 self.parent.insert(new_child, impl_def_id);
237 let mut new_children = Children::new();
238 new_children.insert_blindly(tcx, new_child);
239 self.children.insert(impl_def_id, new_children);
242 ShouldRecurseOn(new_parent) => {
248 self.parent.insert(impl_def_id, parent);
252 /// Insert cached metadata mapping from a child impl back to its parent.
253 pub fn record_impl_from_cstore(&mut self,
254 tcx: TyCtxt<'a, 'gcx, 'tcx>,
257 if self.parent.insert(child, parent).is_some() {
258 bug!("When recording an impl from the crate store, information about its parent \
259 was already present.");
262 self.children.entry(parent).or_insert(Children::new()).insert_blindly(tcx, child);
265 /// The parent of a given impl, which is the def id of the trait when the
266 /// impl is a "specialization root".
267 pub fn parent(&self, child: DefId) -> DefId {
268 *self.parent.get(&child).unwrap()
272 /// A node in the specialization graph is either an impl or a trait
273 /// definition; either can serve as a source of item definitions.
274 /// There is always exactly one trait definition node: the root.
275 #[derive(Debug, Copy, Clone)]
281 impl<'a, 'gcx, 'tcx> Node {
282 pub fn is_from_trait(&self) -> bool {
284 Node::Trait(..) => true,
289 /// Iterate over the items defined directly by the given (impl or trait) node.
290 #[inline] // FIXME(#35870) Avoid closures being unexported due to impl Trait.
291 pub fn items(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>)
292 -> impl Iterator<Item = ty::AssociatedItem> + 'a {
293 tcx.associated_items(self.def_id())
296 pub fn def_id(&self) -> DefId {
298 Node::Impl(did) => did,
299 Node::Trait(did) => did,
304 pub struct Ancestors<'a> {
305 trait_def: &'a TraitDef,
306 current_source: Option<Node>,
309 impl<'a> Iterator for Ancestors<'a> {
311 fn next(&mut self) -> Option<Node> {
312 let cur = self.current_source.take();
313 if let Some(Node::Impl(cur_impl)) = cur {
314 let parent = self.trait_def.specialization_graph.borrow().parent(cur_impl);
315 if parent == self.trait_def.def_id {
316 self.current_source = Some(Node::Trait(parent));
318 self.current_source = Some(Node::Impl(parent));
325 pub struct NodeItem<T> {
330 impl<T> NodeItem<T> {
331 pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
339 impl<'a, 'gcx, 'tcx> Ancestors<'a> {
340 /// Search the items from the given ancestors, returning each definition
341 /// with the given name and the given kind.
342 #[inline] // FIXME(#35870) Avoid closures being unexported due to impl Trait.
343 pub fn defs(self, tcx: TyCtxt<'a, 'gcx, 'tcx>, name: Name, kind: ty::AssociatedKind)
344 -> impl Iterator<Item = NodeItem<ty::AssociatedItem>> + 'a {
345 self.flat_map(move |node| {
346 node.items(tcx).filter(move |item| item.kind == kind && item.name == name)
347 .map(move |item| NodeItem { node: node, item: item })
352 /// Walk up the specialization ancestors of a given impl, starting with that
354 pub fn ancestors<'a>(trait_def: &'a TraitDef, start_from_impl: DefId) -> Ancestors<'a> {
356 trait_def: trait_def,
357 current_source: Some(Node::Impl(start_from_impl)),