1 use crate::ich
::{self, StableHashingContext}
;
2 use crate::ty
::fast_reject
::SimplifiedType
;
3 use crate::ty
::{self, TyCtxt}
;
4 use rustc_ast
::ast
::Ident
;
5 use rustc_data_structures
::fx
::FxHashMap
;
6 use rustc_data_structures
::stable_hasher
::{HashStable, StableHasher}
;
7 use rustc_hir
::def_id
::{DefId, DefIdMap}
;
9 /// A per-trait graph of impls in specialization order. At the moment, this
10 /// graph forms a tree rooted with the trait itself, with all other nodes
11 /// representing impls, and parent-child relationships representing
14 /// The graph provides two key services:
16 /// - Construction. This implicitly checks for overlapping impls (i.e., impls
17 /// that overlap but where neither specializes the other -- an artifact of the
18 /// simple "chain" rule.
20 /// - Parent extraction. In particular, the graph can give you the *immediate*
21 /// parents of a given specializing impl, which is needed for extracting
22 /// default items amongst other things. In the simple "chain" rule, every impl
23 /// has at most one parent.
24 #[derive(RustcEncodable, RustcDecodable, HashStable)]
26 // All impls have a parent; the "root" impls have as their parent the `def_id`
28 pub parent
: DefIdMap
<DefId
>,
30 // The "root" impls are found by looking up the trait's def_id.
31 pub children
: DefIdMap
<Children
>,
35 pub fn new() -> Graph
{
36 Graph { parent: Default::default(), children: Default::default() }
39 /// The parent of a given impl, which is the `DefId` of the trait when the
40 /// impl is a "specialization root".
41 pub fn parent(&self, child
: DefId
) -> DefId
{
42 *self.parent
.get(&child
).unwrap_or_else(|| panic
!("Failed to get parent for {:?}", child
))
46 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
47 /// done in `TraitDef`.
48 #[derive(Default, RustcEncodable, RustcDecodable)]
50 // Impls of a trait (or specializations of a given impl). To allow for
51 // quicker lookup, the impls are indexed by a simplified version of their
52 // `Self` type: impls with a simplifiable `Self` are stored in
53 // `nonblanket_impls` keyed by it, while all other impls are stored in
56 // A similar division is used within `TraitDef`, but the lists there collect
57 // together *all* the impls for a trait, and are populated prior to building
58 // the specialization graph.
59 /// Impls of the trait.
60 pub nonblanket_impls
: FxHashMap
<SimplifiedType
, Vec
<DefId
>>,
62 /// Blanket impls associated with the trait.
63 pub blanket_impls
: Vec
<DefId
>,
66 /// A node in the specialization graph is either an impl or a trait
67 /// definition; either can serve as a source of item definitions.
68 /// There is always exactly one trait definition node: the root.
69 #[derive(Debug, Copy, Clone)]
76 pub fn is_from_trait(&self) -> bool
{
78 Node
::Trait(..) => true,
83 /// Iterate over the items defined directly by the given (impl or trait) node.
84 pub fn items(&self, tcx
: TyCtxt
<'tcx
>) -> impl 'tcx
+ Iterator
<Item
= &'tcx ty
::AssocItem
> {
85 tcx
.associated_items(self.def_id()).in_definition_order()
88 /// Finds an associated item defined in this node.
90 /// If this returns `None`, the item can potentially still be found in
91 /// parents of this node.
95 trait_item_name
: Ident
,
96 trait_item_kind
: ty
::AssocKind
,
98 ) -> Option
<ty
::AssocItem
> {
99 use crate::ty
::AssocKind
::*;
101 tcx
.associated_items(self.def_id())
102 .filter_by_name_unhygienic(trait_item_name
.name
)
103 .find(move |impl_item
| {
104 match (trait_item_kind
, impl_item
.kind
) {
108 | (Type
, OpaqueTy
) // assoc. types can be made opaque in impls
109 => tcx
.hygienic_eq(impl_item
.ident
, trait_item_name
, trait_def_id
),
121 pub fn def_id(&self) -> DefId
{
123 Node
::Impl(did
) => did
,
124 Node
::Trait(did
) => did
,
129 #[derive(Copy, Clone)]
130 pub struct Ancestors
<'tcx
> {
132 specialization_graph
: &'tcx Graph
,
133 current_source
: Option
<Node
>,
136 impl Iterator
for Ancestors
<'_
> {
138 fn next(&mut self) -> Option
<Node
> {
139 let cur
= self.current_source
.take();
140 if let Some(Node
::Impl(cur_impl
)) = cur
{
141 let parent
= self.specialization_graph
.parent(cur_impl
);
143 self.current_source
= if parent
== self.trait_def_id
{
144 Some(Node
::Trait(parent
))
146 Some(Node
::Impl(parent
))
153 pub struct NodeItem
<T
> {
158 impl<T
> NodeItem
<T
> {
159 pub fn map
<U
, F
: FnOnce(T
) -> U
>(self, f
: F
) -> NodeItem
<U
> {
160 NodeItem { node: self.node, item: f(self.item) }
164 impl<'tcx
> Ancestors
<'tcx
> {
165 /// Finds the bottom-most (ie. most specialized) definition of an associated
170 trait_item_name
: Ident
,
171 trait_item_kind
: ty
::AssocKind
,
172 ) -> Option
<NodeItem
<ty
::AssocItem
>> {
173 let trait_def_id
= self.trait_def_id
;
174 self.find_map(|node
| {
175 node
.item(tcx
, trait_item_name
, trait_item_kind
, trait_def_id
)
176 .map(|item
| NodeItem { node, item }
)
181 /// Walk up the specialization ancestors of a given impl, starting with that
186 start_from_impl
: DefId
,
187 ) -> Ancestors
<'tcx
> {
188 let specialization_graph
= tcx
.specialization_graph_of(trait_def_id
);
191 specialization_graph
,
192 current_source
: Some(Node
::Impl(start_from_impl
)),
196 impl<'a
> HashStable
<StableHashingContext
<'a
>> for Children
{
197 fn hash_stable(&self, hcx
: &mut StableHashingContext
<'a
>, hasher
: &mut StableHasher
) {
198 let Children { ref nonblanket_impls, ref blanket_impls }
= *self;
200 ich
::hash_stable_trait_impls(hcx
, hasher
, blanket_impls
, nonblanket_impls
);