rustc_middle/traits/specialization_graph.rs
1use rustc_data_structures::fx::FxIndexMap;
2use rustc_errors::ErrorGuaranteed;
3use rustc_hir::def_id::{DefId, DefIdMap};
4use rustc_macros::{HashStable, TyDecodable, TyEncodable};
5use rustc_span::sym;
6
7use crate::error::StrictCoherenceNeedsNegativeCoherence;
8use crate::ty::fast_reject::SimplifiedType;
9use crate::ty::{self, TyCtxt, TypeVisitableExt};
10
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
14/// specializations.
15///
16/// The graph provides two key services:
17///
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.
21///
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(TyEncodable, TyDecodable, HashStable, Debug)]
27pub struct Graph {
28 /// All impls have a parent; the "root" impls have as their parent the `def_id`
29 /// of the trait.
30 pub parent: DefIdMap<DefId>,
31
32 /// The "root" impls are found by looking up the trait's def_id.
33 pub children: DefIdMap<Children>,
34}
35
36impl Graph {
37 pub fn new() -> Graph {
38 Graph { parent: Default::default(), children: Default::default() }
39 }
40
41 /// The parent of a given impl, which is the `DefId` of the trait when the
42 /// impl is a "specialization root".
43 #[track_caller]
44 pub fn parent(&self, child: DefId) -> DefId {
45 *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {child:?}"))
46 }
47}
48
49/// What kind of overlap check are we doing -- this exists just for testing and feature-gating
50/// purposes.
51#[derive(Copy, Clone, PartialEq, Eq, Hash, HashStable, Debug, TyEncodable, TyDecodable)]
52pub enum OverlapMode {
53 /// The 1.0 rules (either types fail to unify, or where clauses are not implemented for crate-local types)
54 Stable,
55 /// Feature-gated test: Stable, *or* there is an explicit negative impl that rules out one of the where-clauses.
56 WithNegative,
57 /// Just check for negative impls, not for "where clause not implemented": used for testing.
58 Strict,
59}
60
61impl OverlapMode {
62 pub fn get(tcx: TyCtxt<'_>, trait_id: DefId) -> OverlapMode {
63 let with_negative_coherence = tcx.features().with_negative_coherence();
64 let strict_coherence = tcx.has_attr(trait_id, sym::rustc_strict_coherence);
65
66 if with_negative_coherence {
67 if strict_coherence { OverlapMode::Strict } else { OverlapMode::WithNegative }
68 } else {
69 if strict_coherence {
70 let attr_span = trait_id
71 .as_local()
72 .into_iter()
73 .flat_map(|local_def_id| {
74 tcx.hir_attrs(tcx.local_def_id_to_hir_id(local_def_id))
75 })
76 .find(|attr| attr.has_name(sym::rustc_strict_coherence))
77 .map(|attr| attr.span());
78 tcx.dcx().emit_err(StrictCoherenceNeedsNegativeCoherence {
79 span: tcx.def_span(trait_id),
80 attr_span,
81 });
82 }
83 OverlapMode::Stable
84 }
85 }
86
87 pub fn use_negative_impl(&self) -> bool {
88 *self == OverlapMode::Strict || *self == OverlapMode::WithNegative
89 }
90
91 pub fn use_implicit_negative(&self) -> bool {
92 *self == OverlapMode::Stable || *self == OverlapMode::WithNegative
93 }
94}
95
96/// Children of a given impl, grouped into blanket/non-blanket varieties as is
97/// done in `TraitDef`.
98#[derive(Default, TyEncodable, TyDecodable, Debug, HashStable)]
99pub struct Children {
100 // Impls of a trait (or specializations of a given impl). To allow for
101 // quicker lookup, the impls are indexed by a simplified version of their
102 // `Self` type: impls with a simplifiable `Self` are stored in
103 // `non_blanket_impls` keyed by it, while all other impls are stored in
104 // `blanket_impls`.
105 //
106 // A similar division is used within `TraitDef`, but the lists there collect
107 // together *all* the impls for a trait, and are populated prior to building
108 // the specialization graph.
109 /// Impls of the trait.
110 pub non_blanket_impls: FxIndexMap<SimplifiedType, Vec<DefId>>,
111
112 /// Blanket impls associated with the trait.
113 pub blanket_impls: Vec<DefId>,
114}
115
116/// A node in the specialization graph is either an impl or a trait
117/// definition; either can serve as a source of item definitions.
118/// There is always exactly one trait definition node: the root.
119#[derive(Debug, Copy, Clone)]
120pub enum Node {
121 Impl(DefId),
122 Trait(DefId),
123}
124
125impl Node {
126 pub fn is_from_trait(&self) -> bool {
127 matches!(self, Node::Trait(..))
128 }
129
130 /// Tries to find the associated item that implements `trait_item_def_id`
131 /// defined in this node.
132 ///
133 /// If this returns `None`, the item can potentially still be found in
134 /// parents of this node.
135 pub fn item<'tcx>(&self, tcx: TyCtxt<'tcx>, trait_item_def_id: DefId) -> Option<ty::AssocItem> {
136 match *self {
137 Node::Trait(_) => Some(tcx.associated_item(trait_item_def_id)),
138 Node::Impl(impl_def_id) => {
139 let id = tcx.impl_item_implementor_ids(impl_def_id).get(&trait_item_def_id)?;
140 Some(tcx.associated_item(*id))
141 }
142 }
143 }
144
145 pub fn def_id(&self) -> DefId {
146 match *self {
147 Node::Impl(did) => did,
148 Node::Trait(did) => did,
149 }
150 }
151}
152
153#[derive(Copy, Clone)]
154pub struct Ancestors<'tcx> {
155 trait_def_id: DefId,
156 specialization_graph: &'tcx Graph,
157 current_source: Option<Node>,
158}
159
160impl Iterator for Ancestors<'_> {
161 type Item = Node;
162 fn next(&mut self) -> Option<Node> {
163 let cur = self.current_source.take();
164 if let Some(Node::Impl(cur_impl)) = cur {
165 let parent = self.specialization_graph.parent(cur_impl);
166
167 self.current_source = if parent == self.trait_def_id {
168 Some(Node::Trait(parent))
169 } else {
170 Some(Node::Impl(parent))
171 };
172 }
173 cur
174 }
175}
176
177/// Information about the most specialized definition of an associated item.
178#[derive(Debug)]
179pub struct LeafDef {
180 /// The associated item described by this `LeafDef`.
181 pub item: ty::AssocItem,
182
183 /// The node in the specialization graph containing the definition of `item`.
184 pub defining_node: Node,
185
186 /// The "top-most" (ie. least specialized) specialization graph node that finalized the
187 /// definition of `item`.
188 ///
189 /// Example:
190 ///
191 /// ```
192 /// #![feature(specialization)]
193 /// trait Tr {
194 /// fn assoc(&self);
195 /// }
196 ///
197 /// impl<T> Tr for T {
198 /// default fn assoc(&self) {}
199 /// }
200 ///
201 /// impl Tr for u8 {}
202 /// ```
203 ///
204 /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the
205 /// `finalizing_node`, while `defining_node` will be the generic impl.
206 ///
207 /// If the leaf definition search is started at the generic impl, `finalizing_node` will be
208 /// `None`, since the most specialized impl we found still allows overriding the method
209 /// (doesn't finalize it).
210 pub finalizing_node: Option<Node>,
211}
212
213impl LeafDef {
214 /// Returns whether this definition is known to not be further specializable.
215 pub fn is_final(&self) -> bool {
216 self.finalizing_node.is_some()
217 }
218}
219
220impl<'tcx> Ancestors<'tcx> {
221 /// Finds the bottom-most (ie. most specialized) definition of an associated
222 /// item.
223 pub fn leaf_def(mut self, tcx: TyCtxt<'tcx>, trait_item_def_id: DefId) -> Option<LeafDef> {
224 let mut finalizing_node = None;
225
226 self.find_map(|node| {
227 if let Some(item) = node.item(tcx, trait_item_def_id) {
228 if finalizing_node.is_none() {
229 let is_specializable = item.defaultness(tcx).is_default()
230 || tcx.defaultness(node.def_id()).is_default();
231
232 if !is_specializable {
233 finalizing_node = Some(node);
234 }
235 }
236
237 Some(LeafDef { item, defining_node: node, finalizing_node })
238 } else {
239 // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
240 finalizing_node = Some(node);
241 None
242 }
243 })
244 }
245}
246
247/// Walk up the specialization ancestors of a given impl, starting with that
248/// impl itself.
249///
250/// Returns `Err` if an error was reported while building the specialization
251/// graph.
252pub fn ancestors(
253 tcx: TyCtxt<'_>,
254 trait_def_id: DefId,
255 start_from_impl: DefId,
256) -> Result<Ancestors<'_>, ErrorGuaranteed> {
257 let specialization_graph = tcx.specialization_graph_of(trait_def_id)?;
258
259 if let Err(reported) = tcx.type_of(start_from_impl).instantiate_identity().error_reported() {
260 Err(reported)
261 } else {
262 Ok(Ancestors {
263 trait_def_id,
264 specialization_graph,
265 current_source: Some(Node::Impl(start_from_impl)),
266 })
267 }
268}