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