1 use super::OverlapError;
4 use rustc_hir::def_id::DefId;
5 use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams};
6 use rustc_middle::ty::print::with_no_trimmed_paths;
7 use rustc_middle::ty::{self, TyCtxt, TypeVisitable};
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(), TreatParams::AsInfer)
54 debug!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id, st);
55 self.non_blanket_impls.entry(st).or_default().push(impl_def_id)
57 debug!("insert_blindly: impl_def_id={:?} st=None", impl_def_id);
58 self.blanket_impls.push(impl_def_id)
62 /// Removes an impl from this set of children. Used when replacing
63 /// an impl with a parent. The impl must be present in the list of
65 fn remove_existing(&mut self, tcx: TyCtxt<'_>, impl_def_id: DefId) {
66 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
67 let vec: &mut Vec<DefId>;
68 if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer)
70 debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st);
71 vec = self.non_blanket_impls.get_mut(&st).unwrap();
73 debug!("remove_existing: impl_def_id={:?} st=None", impl_def_id);
74 vec = &mut self.blanket_impls;
77 let index = vec.iter().position(|d| *d == impl_def_id).unwrap();
81 /// Attempt to insert an impl into this set of children, while comparing for
82 /// specialization relationships.
87 simplified_self: Option<SimplifiedType>,
88 overlap_mode: OverlapMode,
89 ) -> Result<Inserted, OverlapError> {
90 let mut last_lint = None;
91 let mut replace_children = Vec::new();
93 debug!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id, simplified_self,);
95 let possible_siblings = match simplified_self {
96 Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)),
97 None => PotentialSiblings::Unfiltered(iter_children(self)),
100 for possible_sibling in possible_siblings {
102 "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}",
103 impl_def_id, simplified_self, possible_sibling,
106 let create_overlap_error = |overlap: traits::coherence::OverlapResult<'_>| {
107 let trait_ref = overlap.impl_header.trait_ref.unwrap();
108 let self_ty = trait_ref.self_ty();
110 // FIXME: should postpone string formatting until we decide to actually emit.
111 with_no_trimmed_paths!({
113 with_impl: possible_sibling,
114 trait_desc: trait_ref.print_only_trait_path().to_string(),
115 // Only report the `Self` type if it has at least
116 // some outer concrete shell; otherwise, it's
117 // not adding much information.
118 self_desc: if self_ty.has_concrete_skeleton() {
119 Some(self_ty.to_string())
123 intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
124 involves_placeholder: overlap.involves_placeholder,
129 let report_overlap_error = |overlap: traits::coherence::OverlapResult<'_>,
131 // Found overlap, but no specialization; error out or report future-compat warning.
133 // Do we *still* get overlap if we disable the future-incompatible modes?
134 let should_err = traits::overlapping_impls(
138 traits::SkipLeakCheck::default(),
144 let error = create_overlap_error(overlap);
149 *last_lint = Some(FutureCompatOverlapError {
151 kind: FutureCompatOverlapErrorKind::LeakCheck,
158 let last_lint_mut = &mut last_lint;
159 let (le, ge) = traits::overlapping_impls(
163 traits::SkipLeakCheck::Yes,
166 if let Some(overlap_kind) =
167 tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling)
170 ty::ImplOverlapKind::Permitted { marker: _ } => {}
171 ty::ImplOverlapKind::Issue33140 => {
172 *last_lint_mut = Some(FutureCompatOverlapError {
173 error: create_overlap_error(overlap),
174 kind: FutureCompatOverlapErrorKind::Issue33140,
179 return Ok((false, false));
182 let le = tcx.specializes((impl_def_id, possible_sibling));
183 let ge = tcx.specializes((possible_sibling, impl_def_id));
186 report_overlap_error(overlap, last_lint_mut)
191 || Ok((false, false)),
196 "descending as child of TraitRef {:?}",
197 tcx.impl_trait_ref(possible_sibling).unwrap()
200 // The impl specializes `possible_sibling`.
201 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
202 } else if ge && !le {
204 "placing as parent of TraitRef {:?}",
205 tcx.impl_trait_ref(possible_sibling).unwrap()
208 replace_children.push(possible_sibling);
210 // Either there's no overlap, or the overlap was already reported by
215 if !replace_children.is_empty() {
216 return Ok(Inserted::ReplaceChildren(replace_children));
219 // No overlap with any potential siblings, so add as a new sibling.
220 debug!("placing as new sibling");
221 self.insert_blindly(tcx, impl_def_id);
222 Ok(Inserted::BecameNewSibling(last_lint))
226 fn iter_children(children: &mut Children) -> impl Iterator<Item = DefId> + '_ {
227 let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter());
228 children.blanket_impls.iter().chain(nonblanket).cloned()
231 fn filtered_children(
232 children: &mut Children,
234 ) -> impl Iterator<Item = DefId> + '_ {
235 let nonblanket = children.non_blanket_impls.entry(st).or_default().iter();
236 children.blanket_impls.iter().chain(nonblanket).cloned()
239 // A custom iterator used by Children::insert
240 enum PotentialSiblings<I, J>
242 I: Iterator<Item = DefId>,
243 J: Iterator<Item = DefId>,
249 impl<I, J> Iterator for PotentialSiblings<I, J>
251 I: Iterator<Item = DefId>,
252 J: Iterator<Item = DefId>,
256 fn next(&mut self) -> Option<Self::Item> {
258 PotentialSiblings::Unfiltered(ref mut iter) => iter.next(),
259 PotentialSiblings::Filtered(ref mut iter) => iter.next(),
265 /// Insert a local impl into the specialization graph. If an existing impl
266 /// conflicts with it (has overlap, but neither specializes the other),
267 /// information about the area of overlap is returned in the `Err`.
272 overlap_mode: OverlapMode,
273 ) -> Result<Option<FutureCompatOverlapError>, OverlapError>;
275 /// Insert cached metadata mapping from a child impl back to its parent.
276 fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId);
279 impl GraphExt for Graph {
280 /// Insert a local impl into the specialization graph. If an existing impl
281 /// conflicts with it (has overlap, but neither specializes the other),
282 /// information about the area of overlap is returned in the `Err`.
287 overlap_mode: OverlapMode,
288 ) -> Result<Option<FutureCompatOverlapError>, OverlapError> {
289 assert!(impl_def_id.is_local());
291 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
292 let trait_def_id = trait_ref.def_id;
295 "insert({:?}): inserting TraitRef {:?} into specialization graph",
296 impl_def_id, trait_ref
299 // If the reference itself contains an earlier error (e.g., due to a
300 // resolution failure), then we just insert the impl at the top level of
301 // the graph and claim that there's no overlap (in order to suppress
303 if trait_ref.references_error() {
305 "insert: inserting dummy node for erroneous TraitRef {:?}, \
306 impl_def_id={:?}, trait_def_id={:?}",
307 trait_ref, impl_def_id, trait_def_id
310 self.parent.insert(impl_def_id, trait_def_id);
311 self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id);
315 let mut parent = trait_def_id;
316 let mut last_lint = None;
317 let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer);
319 // Descend the specialization tree, where `parent` is the current parent node.
321 use self::Inserted::*;
323 let insert_result = self.children.entry(parent).or_default().insert(
330 match insert_result {
331 BecameNewSibling(opt_lint) => {
332 last_lint = opt_lint;
335 ReplaceChildren(grand_children_to_be) => {
342 // and we are inserting the impl N. We want to make it:
350 // Adjust P's list of children: remove G and then add N.
352 let siblings = self.children.get_mut(&parent).unwrap();
353 for &grand_child_to_be in &grand_children_to_be {
354 siblings.remove_existing(tcx, grand_child_to_be);
356 siblings.insert_blindly(tcx, impl_def_id);
359 // Set G's parent to N and N's parent to P.
360 for &grand_child_to_be in &grand_children_to_be {
361 self.parent.insert(grand_child_to_be, impl_def_id);
363 self.parent.insert(impl_def_id, parent);
365 // Add G as N's child.
366 for &grand_child_to_be in &grand_children_to_be {
370 .insert_blindly(tcx, grand_child_to_be);
374 ShouldRecurseOn(new_parent) => {
380 self.parent.insert(impl_def_id, parent);
384 /// Insert cached metadata mapping from a child impl back to its parent.
385 fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId) {
386 if self.parent.insert(child, parent).is_some() {
388 "When recording an impl from the crate store, information about its parent \
389 was already present."
393 self.children.entry(parent).or_default().insert_blindly(tcx, child);