rustc_trait_selection/traits/specialize/
specialization_graph.rs1use rustc_errors::ErrorGuaranteed;
2use rustc_hir::def_id::DefId;
3use rustc_macros::extension;
4use rustc_middle::bug;
5pub use rustc_middle::traits::specialization_graph::*;
6use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams};
7use rustc_middle::ty::{self, TyCtxt, TypeVisitableExt};
8use tracing::{debug, instrument};
9
10use super::OverlapError;
11use crate::traits;
12
13#[derive(Copy, Clone, Debug)]
14pub enum FutureCompatOverlapErrorKind {
15 LeakCheck,
16}
17
18#[derive(Debug)]
19pub struct FutureCompatOverlapError<'tcx> {
20 pub error: OverlapError<'tcx>,
21 pub kind: FutureCompatOverlapErrorKind,
22}
23
24#[derive(Debug)]
26enum Inserted<'tcx> {
27 BecameNewSibling(Option<FutureCompatOverlapError<'tcx>>),
29
30 ReplaceChildren(Vec<DefId>),
32
33 ShouldRecurseOn(DefId),
35}
36
37#[extension(trait ChildrenExt<'tcx>)]
38impl<'tcx> Children {
39 fn insert_blindly(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId) {
41 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().skip_binder();
42 if let Some(st) =
43 fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::InstantiateWithInfer)
44 {
45 debug!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id, st);
46 self.non_blanket_impls.entry(st).or_default().push(impl_def_id)
47 } else {
48 debug!("insert_blindly: impl_def_id={:?} st=None", impl_def_id);
49 self.blanket_impls.push(impl_def_id)
50 }
51 }
52
53 fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId) {
57 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().skip_binder();
58 let vec: &mut Vec<DefId>;
59 if let Some(st) =
60 fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::InstantiateWithInfer)
61 {
62 debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st);
63 vec = self.non_blanket_impls.get_mut(&st).unwrap();
64 } else {
65 debug!("remove_existing: impl_def_id={:?} st=None", impl_def_id);
66 vec = &mut self.blanket_impls;
67 }
68
69 let index = vec.iter().position(|d| *d == impl_def_id).unwrap();
70 vec.remove(index);
71 }
72
73 #[instrument(level = "debug", skip(self, tcx), ret)]
76 fn insert(
77 &mut self,
78 tcx: TyCtxt<'tcx>,
79 impl_def_id: DefId,
80 simplified_self: Option<SimplifiedType>,
81 overlap_mode: OverlapMode,
82 ) -> Result<Inserted<'tcx>, OverlapError<'tcx>> {
83 let mut last_lint = None;
84 let mut replace_children = Vec::new();
85
86 let possible_siblings = match simplified_self {
87 Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)),
88 None => PotentialSiblings::Unfiltered(iter_children(self)),
89 };
90
91 for possible_sibling in possible_siblings {
92 debug!(?possible_sibling);
93
94 let create_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>| {
95 let trait_ref = overlap.impl_header.trait_ref.unwrap();
96 let self_ty = trait_ref.self_ty();
97
98 OverlapError {
99 with_impl: possible_sibling,
100 trait_ref,
101 self_ty: self_ty.has_concrete_skeleton().then_some(self_ty),
105 intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
106 involves_placeholder: overlap.involves_placeholder,
107 overflowing_predicates: overlap.overflowing_predicates,
108 }
109 };
110
111 let report_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>,
112 last_lint: &mut _| {
113 let should_err = traits::overlapping_impls(
117 tcx,
118 possible_sibling,
119 impl_def_id,
120 traits::SkipLeakCheck::default(),
121 overlap_mode,
122 )
123 .is_some();
124
125 let error = create_overlap_error(overlap);
126
127 if should_err {
128 Err(error)
129 } else {
130 *last_lint = Some(FutureCompatOverlapError {
131 error,
132 kind: FutureCompatOverlapErrorKind::LeakCheck,
133 });
134
135 Ok((false, false))
136 }
137 };
138
139 let last_lint_mut = &mut last_lint;
140 let (le, ge) = traits::overlapping_impls(
141 tcx,
142 possible_sibling,
143 impl_def_id,
144 traits::SkipLeakCheck::Yes,
145 overlap_mode,
146 )
147 .map_or(Ok((false, false)), |overlap| {
148 if let Some(overlap_kind) =
149 tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling)
150 {
151 match overlap_kind {
152 ty::ImplOverlapKind::Permitted { marker: _ } => {}
153 }
154
155 return Ok((false, false));
156 }
157
158 let le = tcx.specializes((impl_def_id, possible_sibling));
159 let ge = tcx.specializes((possible_sibling, impl_def_id));
160
161 if le == ge { report_overlap_error(overlap, last_lint_mut) } else { Ok((le, ge)) }
162 })?;
163
164 if le && !ge {
165 debug!(
166 "descending as child of TraitRef {:?}",
167 tcx.impl_trait_ref(possible_sibling).unwrap().instantiate_identity()
168 );
169
170 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
172 } else if ge && !le {
173 debug!(
174 "placing as parent of TraitRef {:?}",
175 tcx.impl_trait_ref(possible_sibling).unwrap().instantiate_identity()
176 );
177
178 replace_children.push(possible_sibling);
179 } else {
180 }
183 }
184
185 if !replace_children.is_empty() {
186 return Ok(Inserted::ReplaceChildren(replace_children));
187 }
188
189 debug!("placing as new sibling");
191 self.insert_blindly(tcx, impl_def_id);
192 Ok(Inserted::BecameNewSibling(last_lint))
193 }
194}
195
196fn iter_children(children: &Children) -> impl Iterator<Item = DefId> {
197 let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter());
198 children.blanket_impls.iter().chain(nonblanket).cloned()
199}
200
201fn filtered_children(children: &mut Children, st: SimplifiedType) -> impl Iterator<Item = DefId> {
202 let nonblanket = children.non_blanket_impls.entry(st).or_default().iter();
203 children.blanket_impls.iter().chain(nonblanket).cloned()
204}
205
206enum PotentialSiblings<I, J>
208where
209 I: Iterator<Item = DefId>,
210 J: Iterator<Item = DefId>,
211{
212 Unfiltered(I),
213 Filtered(J),
214}
215
216impl<I, J> Iterator for PotentialSiblings<I, J>
217where
218 I: Iterator<Item = DefId>,
219 J: Iterator<Item = DefId>,
220{
221 type Item = DefId;
222
223 fn next(&mut self) -> Option<Self::Item> {
224 match *self {
225 PotentialSiblings::Unfiltered(ref mut iter) => iter.next(),
226 PotentialSiblings::Filtered(ref mut iter) => iter.next(),
227 }
228 }
229}
230
231#[extension(pub trait GraphExt<'tcx>)]
232impl<'tcx> Graph {
233 fn insert(
237 &mut self,
238 tcx: TyCtxt<'tcx>,
239 impl_def_id: DefId,
240 overlap_mode: OverlapMode,
241 ) -> Result<Option<FutureCompatOverlapError<'tcx>>, OverlapError<'tcx>> {
242 assert!(impl_def_id.is_local());
243
244 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().skip_binder();
246 let trait_def_id = trait_ref.def_id;
247
248 debug!(
249 "insert({:?}): inserting TraitRef {:?} into specialization graph",
250 impl_def_id, trait_ref
251 );
252
253 if trait_ref.references_error() {
258 debug!(
259 "insert: inserting dummy node for erroneous TraitRef {:?}, \
260 impl_def_id={:?}, trait_def_id={:?}",
261 trait_ref, impl_def_id, trait_def_id
262 );
263
264 self.parent.insert(impl_def_id, trait_def_id);
265 self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id);
266 return Ok(None);
267 }
268
269 let mut parent = trait_def_id;
270 let mut last_lint = None;
271 let simplified =
272 fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::InstantiateWithInfer);
273
274 loop {
276 let insert_result = self.children.entry(parent).or_default().insert(
277 tcx,
278 impl_def_id,
279 simplified,
280 overlap_mode,
281 )?;
282
283 match insert_result {
284 Inserted::BecameNewSibling(opt_lint) => {
285 last_lint = opt_lint;
286 break;
287 }
288 Inserted::ReplaceChildren(grand_children_to_be) => {
289 {
305 let siblings = self.children.get_mut(&parent).unwrap();
306 for &grand_child_to_be in &grand_children_to_be {
307 siblings.remove_existing(tcx, grand_child_to_be);
308 }
309 siblings.insert_blindly(tcx, impl_def_id);
310 }
311
312 for &grand_child_to_be in &grand_children_to_be {
314 self.parent.insert(grand_child_to_be, impl_def_id);
315 }
316 self.parent.insert(impl_def_id, parent);
317
318 for &grand_child_to_be in &grand_children_to_be {
320 self.children
321 .entry(impl_def_id)
322 .or_default()
323 .insert_blindly(tcx, grand_child_to_be);
324 }
325 break;
326 }
327 Inserted::ShouldRecurseOn(new_parent) => {
328 parent = new_parent;
329 }
330 }
331 }
332
333 self.parent.insert(impl_def_id, parent);
334 Ok(last_lint)
335 }
336
337 fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'tcx>, parent: DefId, child: DefId) {
339 if self.parent.insert(child, parent).is_some() {
340 bug!(
341 "When recording an impl from the crate store, information about its parent \
342 was already present."
343 );
344 }
345
346 self.children.entry(parent).or_default().insert_blindly(tcx, child);
347 }
348}
349
350pub(crate) fn assoc_def(
353 tcx: TyCtxt<'_>,
354 impl_def_id: DefId,
355 assoc_def_id: DefId,
356) -> Result<LeafDef, ErrorGuaranteed> {
357 let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
358 let trait_def = tcx.trait_def(trait_def_id);
359
360 if let Some(&impl_item_id) = tcx.impl_item_implementor_ids(impl_def_id).get(&assoc_def_id) {
367 if let Some(impl_def_id) = impl_def_id.as_local() {
370 tcx.ensure_ok().enforce_impl_non_lifetime_params_are_constrained(impl_def_id)?;
371 }
372
373 let item = tcx.associated_item(impl_item_id);
374 let impl_node = Node::Impl(impl_def_id);
375 return Ok(LeafDef {
376 item,
377 defining_node: impl_node,
378 finalizing_node: if item.defaultness(tcx).is_default() {
379 None
380 } else {
381 Some(impl_node)
382 },
383 });
384 }
385
386 let ancestors = trait_def.ancestors(tcx, impl_def_id)?;
387 if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_def_id) {
388 if assoc_item.item.container == ty::AssocItemContainer::Impl
391 && let Some(impl_def_id) = assoc_item.item.container_id(tcx).as_local()
392 {
393 tcx.ensure_ok().enforce_impl_non_lifetime_params_are_constrained(impl_def_id)?;
394 }
395
396 Ok(assoc_item)
397 } else {
398 bug!(
405 "No associated type `{}` for {}",
406 tcx.item_name(assoc_def_id),
407 tcx.def_path_str(impl_def_id)
408 )
409 }
410}