1 use super::OverlapError;
4 use rustc_hir::def_id::DefId;
5 use rustc_middle::ty::fast_reject::{self, SimplifiedType, SimplifyParams};
6 use rustc_middle::ty::print::with_no_trimmed_paths;
7 use rustc_middle::ty::{self, TyCtxt, TypeFoldable};
9 pub use rustc_middle::traits::specialization_graph::*;
11 #[derive(Copy, Clone, Debug)]
12 pub enum FutureCompatOverlapErrorKind {
18 pub struct FutureCompatOverlapError {
19 pub error: OverlapError,
20 pub kind: FutureCompatOverlapErrorKind,
23 /// The result of attempting to insert an impl into a group of children.
25 /// The impl was inserted as a new child in this group of children.
26 BecameNewSibling(Option<FutureCompatOverlapError>),
28 /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc.
29 ReplaceChildren(Vec<DefId>),
31 /// The impl is a specialization of an existing child.
32 ShouldRecurseOn(DefId),
35 trait ChildrenExt<'tcx> {
36 fn insert_blindly(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId);
37 fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId);
43 simplified_self: Option<SimplifiedType>,
44 overlap_mode: OverlapMode,
45 ) -> Result<Inserted, OverlapError>;
48 impl ChildrenExt<'_> for Children {
49 /// Insert an impl into this set of children without comparing to any existing impls.
50 fn insert_blindly(&mut self, tcx: TyCtxt<'_>, impl_def_id: DefId) {
51 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
52 if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), SimplifyParams::No) {
53 debug!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id, st);
54 self.non_blanket_impls.entry(st).or_default().push(impl_def_id)
56 debug!("insert_blindly: impl_def_id={:?} st=None", impl_def_id);
57 self.blanket_impls.push(impl_def_id)
61 /// Removes an impl from this set of children. Used when replacing
62 /// an impl with a parent. The impl must be present in the list of
64 fn remove_existing(&mut self, tcx: TyCtxt<'_>, impl_def_id: DefId) {
65 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
66 let vec: &mut Vec<DefId>;
67 if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), SimplifyParams::No) {
68 debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st);
69 vec = self.non_blanket_impls.get_mut(&st).unwrap();
71 debug!("remove_existing: impl_def_id={:?} st=None", impl_def_id);
72 vec = &mut self.blanket_impls;
75 let index = vec.iter().position(|d| *d == impl_def_id).unwrap();
79 /// Attempt to insert an impl into this set of children, while comparing for
80 /// specialization relationships.
85 simplified_self: Option<SimplifiedType>,
86 overlap_mode: OverlapMode,
87 ) -> Result<Inserted, OverlapError> {
88 let mut last_lint = None;
89 let mut replace_children = Vec::new();
91 debug!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id, simplified_self,);
93 let possible_siblings = match simplified_self {
94 Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)),
95 None => PotentialSiblings::Unfiltered(iter_children(self)),
98 for possible_sibling in possible_siblings {
100 "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}",
101 impl_def_id, simplified_self, possible_sibling,
104 let create_overlap_error = |overlap: traits::coherence::OverlapResult<'_>| {
105 let trait_ref = overlap.impl_header.trait_ref.unwrap();
106 let self_ty = trait_ref.self_ty();
108 // FIXME: should postpone string formatting until we decide to actually emit.
109 with_no_trimmed_paths!({
111 with_impl: possible_sibling,
112 trait_desc: trait_ref.print_only_trait_path().to_string(),
113 // Only report the `Self` type if it has at least
114 // some outer concrete shell; otherwise, it's
115 // not adding much information.
116 self_desc: if self_ty.has_concrete_skeleton() {
117 Some(self_ty.to_string())
121 intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
122 involves_placeholder: overlap.involves_placeholder,
127 let report_overlap_error = |overlap: traits::coherence::OverlapResult<'_>,
129 // Found overlap, but no specialization; error out or report future-compat warning.
131 // Do we *still* get overlap if we disable the future-incompatible modes?
132 let should_err = traits::overlapping_impls(
136 traits::SkipLeakCheck::default(),
142 let error = create_overlap_error(overlap);
147 *last_lint = Some(FutureCompatOverlapError {
149 kind: FutureCompatOverlapErrorKind::LeakCheck,
156 let last_lint_mut = &mut last_lint;
157 let (le, ge) = traits::overlapping_impls(
161 traits::SkipLeakCheck::Yes,
164 if let Some(overlap_kind) =
165 tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling)
168 ty::ImplOverlapKind::Permitted { marker: _ } => {}
169 ty::ImplOverlapKind::Issue33140 => {
170 *last_lint_mut = Some(FutureCompatOverlapError {
171 error: create_overlap_error(overlap),
172 kind: FutureCompatOverlapErrorKind::Issue33140,
177 return Ok((false, false));
180 let le = tcx.specializes((impl_def_id, possible_sibling));
181 let ge = tcx.specializes((possible_sibling, impl_def_id));
184 report_overlap_error(overlap, last_lint_mut)
189 || Ok((false, false)),
194 "descending as child of TraitRef {:?}",
195 tcx.impl_trait_ref(possible_sibling).unwrap()
198 // The impl specializes `possible_sibling`.
199 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
200 } else if ge && !le {
202 "placing as parent of TraitRef {:?}",
203 tcx.impl_trait_ref(possible_sibling).unwrap()
206 replace_children.push(possible_sibling);
208 // Either there's no overlap, or the overlap was already reported by
213 if !replace_children.is_empty() {
214 return Ok(Inserted::ReplaceChildren(replace_children));
217 // No overlap with any potential siblings, so add as a new sibling.
218 debug!("placing as new sibling");
219 self.insert_blindly(tcx, impl_def_id);
220 Ok(Inserted::BecameNewSibling(last_lint))
224 fn iter_children(children: &mut Children) -> impl Iterator<Item = DefId> + '_ {
225 let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter());
226 children.blanket_impls.iter().chain(nonblanket).cloned()
229 fn filtered_children(
230 children: &mut Children,
232 ) -> impl Iterator<Item = DefId> + '_ {
233 let nonblanket = children.non_blanket_impls.entry(st).or_default().iter();
234 children.blanket_impls.iter().chain(nonblanket).cloned()
237 // A custom iterator used by Children::insert
238 enum PotentialSiblings<I, J>
240 I: Iterator<Item = DefId>,
241 J: Iterator<Item = DefId>,
247 impl<I, J> Iterator for PotentialSiblings<I, J>
249 I: Iterator<Item = DefId>,
250 J: Iterator<Item = DefId>,
254 fn next(&mut self) -> Option<Self::Item> {
256 PotentialSiblings::Unfiltered(ref mut iter) => iter.next(),
257 PotentialSiblings::Filtered(ref mut iter) => iter.next(),
263 /// Insert a local impl into the specialization graph. If an existing impl
264 /// conflicts with it (has overlap, but neither specializes the other),
265 /// information about the area of overlap is returned in the `Err`.
270 overlap_mode: OverlapMode,
271 ) -> Result<Option<FutureCompatOverlapError>, OverlapError>;
273 /// Insert cached metadata mapping from a child impl back to its parent.
274 fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId);
277 impl GraphExt for Graph {
278 /// Insert a local impl into the specialization graph. If an existing impl
279 /// conflicts with it (has overlap, but neither specializes the other),
280 /// information about the area of overlap is returned in the `Err`.
285 overlap_mode: OverlapMode,
286 ) -> Result<Option<FutureCompatOverlapError>, OverlapError> {
287 assert!(impl_def_id.is_local());
289 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
290 let trait_def_id = trait_ref.def_id;
293 "insert({:?}): inserting TraitRef {:?} into specialization graph",
294 impl_def_id, trait_ref
297 // If the reference itself contains an earlier error (e.g., due to a
298 // resolution failure), then we just insert the impl at the top level of
299 // the graph and claim that there's no overlap (in order to suppress
301 if trait_ref.references_error() {
303 "insert: inserting dummy node for erroneous TraitRef {:?}, \
304 impl_def_id={:?}, trait_def_id={:?}",
305 trait_ref, impl_def_id, trait_def_id
308 self.parent.insert(impl_def_id, trait_def_id);
309 self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id);
313 let mut parent = trait_def_id;
314 let mut last_lint = None;
315 let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), SimplifyParams::No);
317 // Descend the specialization tree, where `parent` is the current parent node.
319 use self::Inserted::*;
321 let insert_result = self.children.entry(parent).or_default().insert(
328 match insert_result {
329 BecameNewSibling(opt_lint) => {
330 last_lint = opt_lint;
333 ReplaceChildren(grand_children_to_be) => {
340 // and we are inserting the impl N. We want to make it:
348 // Adjust P's list of children: remove G and then add N.
350 let siblings = self.children.get_mut(&parent).unwrap();
351 for &grand_child_to_be in &grand_children_to_be {
352 siblings.remove_existing(tcx, grand_child_to_be);
354 siblings.insert_blindly(tcx, impl_def_id);
357 // Set G's parent to N and N's parent to P.
358 for &grand_child_to_be in &grand_children_to_be {
359 self.parent.insert(grand_child_to_be, impl_def_id);
361 self.parent.insert(impl_def_id, parent);
363 // Add G as N's child.
364 for &grand_child_to_be in &grand_children_to_be {
368 .insert_blindly(tcx, grand_child_to_be);
372 ShouldRecurseOn(new_parent) => {
378 self.parent.insert(impl_def_id, parent);
382 /// Insert cached metadata mapping from a child impl back to its parent.
383 fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId) {
384 if self.parent.insert(child, parent).is_some() {
386 "When recording an impl from the crate store, information about its parent \
387 was already present."
391 self.children.entry(parent).or_default().insert_blindly(tcx, child);