1 use crate::ich::{self, StableHashingContext};
2 use crate::ty::fast_reject::SimplifiedType;
3 use crate::ty::fold::TypeFoldable;
4 use crate::ty::{self, TyCtxt};
5 use rustc_data_structures::fx::FxHashMap;
6 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
7 use rustc_errors::ErrorReported;
8 use rustc_hir::def_id::{DefId, DefIdMap};
9 use rustc_span::symbol::Ident;
11 /// A per-trait graph of impls in specialization order. At the moment, this
12 /// graph forms a tree rooted with the trait itself, with all other nodes
13 /// representing impls, and parent-child relationships representing
16 /// The graph provides two key services:
18 /// - Construction. This implicitly checks for overlapping impls (i.e., impls
19 /// that overlap but where neither specializes the other -- an artifact of the
20 /// simple "chain" rule.
22 /// - Parent extraction. In particular, the graph can give you the *immediate*
23 /// parents of a given specializing impl, which is needed for extracting
24 /// default items amongst other things. In the simple "chain" rule, every impl
25 /// has at most one parent.
26 #[derive(RustcEncodable, RustcDecodable, HashStable)]
28 /// All impls have a parent; the "root" impls have as their parent the `def_id`
30 pub parent: DefIdMap<DefId>,
32 /// The "root" impls are found by looking up the trait's def_id.
33 pub children: DefIdMap<Children>,
35 /// Whether an error was emitted while constructing the graph.
36 pub has_errored: bool,
40 pub fn new() -> Graph {
41 Graph { parent: Default::default(), children: Default::default(), has_errored: false }
44 /// The parent of a given impl, which is the `DefId` of the trait when the
45 /// impl is a "specialization root".
46 pub fn parent(&self, child: DefId) -> DefId {
47 *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {:?}", child))
51 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
52 /// done in `TraitDef`.
53 #[derive(Default, RustcEncodable, RustcDecodable)]
55 // Impls of a trait (or specializations of a given impl). To allow for
56 // quicker lookup, the impls are indexed by a simplified version of their
57 // `Self` type: impls with a simplifiable `Self` are stored in
58 // `nonblanket_impls` keyed by it, while all other impls are stored in
61 // A similar division is used within `TraitDef`, but the lists there collect
62 // together *all* the impls for a trait, and are populated prior to building
63 // the specialization graph.
64 /// Impls of the trait.
65 pub nonblanket_impls: FxHashMap<SimplifiedType, Vec<DefId>>,
67 /// Blanket impls associated with the trait.
68 pub blanket_impls: Vec<DefId>,
71 /// A node in the specialization graph is either an impl or a trait
72 /// definition; either can serve as a source of item definitions.
73 /// There is always exactly one trait definition node: the root.
74 #[derive(Debug, Copy, Clone)]
81 pub fn is_from_trait(&self) -> bool {
83 Node::Trait(..) => true,
88 /// Iterate over the items defined directly by the given (impl or trait) node.
89 pub fn items(&self, tcx: TyCtxt<'tcx>) -> impl 'tcx + Iterator<Item = &'tcx ty::AssocItem> {
90 tcx.associated_items(self.def_id()).in_definition_order()
93 /// Finds an associated item defined in this node.
95 /// If this returns `None`, the item can potentially still be found in
96 /// parents of this node.
100 trait_item_name: Ident,
101 trait_item_kind: ty::AssocKind,
103 ) -> Option<ty::AssocItem> {
104 tcx.associated_items(self.def_id())
105 .filter_by_name_unhygienic(trait_item_name.name)
106 .find(move |impl_item| {
107 trait_item_kind == impl_item.kind
108 && tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id)
113 pub fn def_id(&self) -> DefId {
115 Node::Impl(did) => did,
116 Node::Trait(did) => did,
121 #[derive(Copy, Clone)]
122 pub struct Ancestors<'tcx> {
124 specialization_graph: &'tcx Graph,
125 current_source: Option<Node>,
128 impl Iterator for Ancestors<'_> {
130 fn next(&mut self) -> Option<Node> {
131 let cur = self.current_source.take();
132 if let Some(Node::Impl(cur_impl)) = cur {
133 let parent = self.specialization_graph.parent(cur_impl);
135 self.current_source = if parent == self.trait_def_id {
136 Some(Node::Trait(parent))
138 Some(Node::Impl(parent))
145 /// Information about the most specialized definition of an associated item.
147 /// The associated item described by this `LeafDef`.
148 pub item: ty::AssocItem,
150 /// The node in the specialization graph containing the definition of `item`.
151 pub defining_node: Node,
153 /// The "top-most" (ie. least specialized) specialization graph node that finalized the
154 /// definition of `item`.
163 /// impl<T> Tr for T {
164 /// default fn assoc(&self) {}
167 /// impl Tr for u8 {}
170 /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the
171 /// `finalizing_node`, while `defining_node` will be the generic impl.
173 /// If the leaf definition search is started at the generic impl, `finalizing_node` will be
174 /// `None`, since the most specialized impl we found still allows overriding the method
175 /// (doesn't finalize it).
176 pub finalizing_node: Option<Node>,
180 /// Returns whether this definition is known to not be further specializable.
181 pub fn is_final(&self) -> bool {
182 self.finalizing_node.is_some()
186 impl<'tcx> Ancestors<'tcx> {
187 /// Finds the bottom-most (ie. most specialized) definition of an associated
192 trait_item_name: Ident,
193 trait_item_kind: ty::AssocKind,
194 ) -> Option<LeafDef> {
195 let trait_def_id = self.trait_def_id;
196 let mut finalizing_node = None;
198 self.find_map(|node| {
199 if let Some(item) = node.item(tcx, trait_item_name, trait_item_kind, trait_def_id) {
200 if finalizing_node.is_none() {
201 let is_specializable = item.defaultness.is_default()
202 || tcx.impl_defaultness(node.def_id()).is_default();
204 if !is_specializable {
205 finalizing_node = Some(node);
209 Some(LeafDef { item, defining_node: node, finalizing_node })
211 // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
212 finalizing_node = Some(node);
219 /// Walk up the specialization ancestors of a given impl, starting with that
222 /// Returns `Err` if an error was reported while building the specialization
227 start_from_impl: DefId,
228 ) -> Result<Ancestors<'tcx>, ErrorReported> {
229 let specialization_graph = tcx.specialization_graph_of(trait_def_id);
231 if specialization_graph.has_errored || tcx.type_of(start_from_impl).references_error() {
236 specialization_graph,
237 current_source: Some(Node::Impl(start_from_impl)),
242 impl<'a> HashStable<StableHashingContext<'a>> for Children {
243 fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
244 let Children { ref nonblanket_impls, ref blanket_impls } = *self;
246 ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, nonblanket_impls);