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.
14 use super::{Overlap, specializes}
;
16 use middle
::cstore
::CrateStore
;
17 use hir
::def_id
::DefId
;
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}
;
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
30 /// The graph provides two key services:
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.
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.
41 // all impls have a parent; the "root" impls have as their parent the def_id
43 parent
: DefIdMap
<DefId
>,
45 // the "root" impls are found by looking up the trait's def_id.
46 children
: DefIdMap
<Children
>,
49 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
50 /// done in `TraitDef`.
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
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.
62 /// Impls of the trait.
63 nonblanket_impls
: FnvHashMap
<fast_reject
::SimplifiedType
, Vec
<DefId
>>,
65 /// Blanket impls associated with the trait.
66 blanket_impls
: Vec
<DefId
>,
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.
74 /// The impl replaced an existing impl that specializes it.
77 /// The impl is a specialization of an existing child.
78 ShouldRecurseOn(DefId
),
80 /// The impl has an unresolvable overlap with an existing child (neither
81 /// specializes the other).
82 Overlapped(Overlap
<'a
, 'tcx
>),
86 fn new() -> Children
{
88 nonblanket_impls
: FnvHashMap(),
89 blanket_impls
: vec
![],
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
)
99 self.blanket_impls
.push(impl_def_id
)
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
>,
108 simplified_self
: Option
<SimplifiedType
>)
109 -> InsertResult
<'a
, 'tcx
>
111 for slot
in match simplified_self
{
112 Some(sty
) => self.filtered_mut(sty
),
113 None
=> self.iter_mut(),
115 let possible_sibling
= *slot
;
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
);
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
);
125 debug
!("descending as child of TraitRef {:?}",
126 tcx
.impl_trait_ref(possible_sibling
).unwrap());
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());
134 // possible_sibling specializes the impl
136 return InsertResult
::Replaced(possible_sibling
);
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(),
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
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
))
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
))
167 pub fn new() -> Graph
{
169 parent
: Default
::default(),
170 children
: Default
::default(),
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
>,
180 -> Result
<(), Overlap
<'a
, 'tcx
>> {
181 assert
!(impl_def_id
.is_local());
183 let trait_ref
= tcx
.impl_trait_ref(impl_def_id
).unwrap();
184 let trait_def_id
= trait_ref
.def_id
;
186 debug
!("insert({:?}): inserting TraitRef {:?} into specialization graph",
187 impl_def_id
, trait_ref
);
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
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
);
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
);
204 let mut parent
= trait_def_id
;
205 let simplified
= fast_reject
::simplify_type(tcx
, trait_ref
.self_ty(), false);
207 // Descend the specialization tree, where `parent` is the current parent node
209 use self::InsertResult
::*;
211 let insert_result
= self.children
.entry(parent
).or_insert(Children
::new())
212 .insert(tcx
, impl_def_id
, simplified
);
214 match insert_result
{
215 BecameNewSibling
=> {
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
);
225 ShouldRecurseOn(new_parent
) => {
228 Overlapped(error
) => {
234 self.parent
.insert(impl_def_id
, parent
);
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.");
245 self.children
.entry(parent
).or_insert(Children
::new()).insert_blindly(tcx
, child
);
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()
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)]
265 pub fn is_from_trait(&self) -> bool
{
267 Node
::Trait(..) => true,
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
> {
275 Node
::Impl(impl_def_id
) => {
278 items
: cell
::Ref
::map(tcx
.impl_items
.borrow(),
279 |impl_items
| &impl_items
[&impl_def_id
]),
283 Node
::Trait(trait_def_id
) => {
285 items
: tcx
.trait_items(trait_def_id
).clone(),
292 pub fn def_id(&self) -> DefId
{
294 Node
::Impl(did
) => did
,
295 Node
::Trait(did
) => did
,
300 /// An iterator over the items defined within a trait or impl.
301 pub enum NodeItems
<'a
, 'tcx
: 'a
> {
303 tcx
: &'a TyCtxt
<'tcx
>,
304 items
: cell
::Ref
<'a
, Vec
<ty
::ImplOrTraitItemId
>>,
308 items
: Rc
<Vec
<ImplOrTraitItem
<'tcx
>>>,
313 impl<'a
, 'tcx
> Iterator
for NodeItems
<'a
, 'tcx
> {
314 type Item
= ImplOrTraitItem
<'tcx
>;
315 fn next(&mut self) -> Option
<ImplOrTraitItem
<'tcx
>> {
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();
328 NodeItems
::Trait { ref items, ref mut idx }
=> {
329 if *idx
< items
.len() {
330 let item
= items
[*idx
].clone();
341 pub struct Ancestors
<'a
, 'tcx
: 'a
> {
342 trait_def
: &'a TraitDef
<'tcx
>,
343 current_source
: Option
<Node
>,
346 impl<'a
, 'tcx
> Iterator
for Ancestors
<'a
, 'tcx
> {
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
));
355 self.current_source
= Some(Node
::Impl(parent
));
362 pub struct NodeItem
<T
> {
367 impl<T
> NodeItem
<T
> {
368 pub fn map
<U
, F
: FnOnce(T
) -> U
>(self, f
: F
) -> NodeItem
<U
> {
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
>,
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
> {
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
>,
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
> {
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
>,
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
> {
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
| {
418 .filter_map(move |item
| {
419 if let ty
::TypeTraitItem(assoc_ty
) = item
{
420 if assoc_ty
.name
== name
{
421 return Some(NodeItem
{
431 TypeDefs { iter: Box::new(iter) }
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
| {
439 .filter_map(move |item
| {
440 if let ty
::MethodTraitItem(method
) = item
{
441 if method
.name
== name
{
442 return Some(NodeItem
{
452 FnDefs { iter: Box::new(iter) }
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
| {
460 .filter_map(move |item
| {
461 if let ty
::ConstTraitItem(konst
) = item
{
462 if konst
.name
== name
{
463 return Some(NodeItem
{
473 ConstDefs { iter: Box::new(iter) }
477 /// Walk up the specialization ancestors of a given impl, starting with that
479 pub fn ancestors
<'a
, 'tcx
>(trait_def
: &'a TraitDef
<'tcx
>,
480 start_from_impl
: DefId
)
481 -> Ancestors
<'a
, 'tcx
> {
483 trait_def
: trait_def
,
484 current_source
: Some(Node
::Impl(start_from_impl
)),