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(),
143 let error = create_overlap_error(overlap);
148 *last_lint = Some(FutureCompatOverlapError {
150 kind: FutureCompatOverlapErrorKind::LeakCheck,
157 let last_lint_mut = &mut last_lint;
158 let (le, ge) = traits::overlapping_impls(
162 traits::SkipLeakCheck::Yes,
165 .map_or(Ok((false, false)), |overlap| {
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));
185 if le == ge { report_overlap_error(overlap, last_lint_mut) } else { Ok((le, ge)) }
190 "descending as child of TraitRef {:?}",
191 tcx.impl_trait_ref(possible_sibling).unwrap()
194 // The impl specializes `possible_sibling`.
195 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
196 } else if ge && !le {
198 "placing as parent of TraitRef {:?}",
199 tcx.impl_trait_ref(possible_sibling).unwrap()
202 replace_children.push(possible_sibling);
204 // Either there's no overlap, or the overlap was already reported by
209 if !replace_children.is_empty() {
210 return Ok(Inserted::ReplaceChildren(replace_children));
213 // No overlap with any potential siblings, so add as a new sibling.
214 debug!("placing as new sibling");
215 self.insert_blindly(tcx, impl_def_id);
216 Ok(Inserted::BecameNewSibling(last_lint))
220 fn iter_children(children: &mut Children) -> impl Iterator<Item = DefId> + '_ {
221 let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter());
222 children.blanket_impls.iter().chain(nonblanket).cloned()
225 fn filtered_children(
226 children: &mut Children,
228 ) -> impl Iterator<Item = DefId> + '_ {
229 let nonblanket = children.non_blanket_impls.entry(st).or_default().iter();
230 children.blanket_impls.iter().chain(nonblanket).cloned()
233 // A custom iterator used by Children::insert
234 enum PotentialSiblings<I, J>
236 I: Iterator<Item = DefId>,
237 J: Iterator<Item = DefId>,
243 impl<I, J> Iterator for PotentialSiblings<I, J>
245 I: Iterator<Item = DefId>,
246 J: Iterator<Item = DefId>,
250 fn next(&mut self) -> Option<Self::Item> {
252 PotentialSiblings::Unfiltered(ref mut iter) => iter.next(),
253 PotentialSiblings::Filtered(ref mut iter) => iter.next(),
259 /// Insert a local impl into the specialization graph. If an existing impl
260 /// conflicts with it (has overlap, but neither specializes the other),
261 /// information about the area of overlap is returned in the `Err`.
266 overlap_mode: OverlapMode,
267 ) -> Result<Option<FutureCompatOverlapError>, OverlapError>;
269 /// Insert cached metadata mapping from a child impl back to its parent.
270 fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId);
273 impl GraphExt for Graph {
274 /// Insert a local impl into the specialization graph. If an existing impl
275 /// conflicts with it (has overlap, but neither specializes the other),
276 /// information about the area of overlap is returned in the `Err`.
281 overlap_mode: OverlapMode,
282 ) -> Result<Option<FutureCompatOverlapError>, OverlapError> {
283 assert!(impl_def_id.is_local());
285 let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
286 let trait_def_id = trait_ref.def_id;
289 "insert({:?}): inserting TraitRef {:?} into specialization graph",
290 impl_def_id, trait_ref
293 // If the reference itself contains an earlier error (e.g., due to a
294 // resolution failure), then we just insert the impl at the top level of
295 // the graph and claim that there's no overlap (in order to suppress
297 if trait_ref.references_error() {
299 "insert: inserting dummy node for erroneous TraitRef {:?}, \
300 impl_def_id={:?}, trait_def_id={:?}",
301 trait_ref, impl_def_id, trait_def_id
304 self.parent.insert(impl_def_id, trait_def_id);
305 self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id);
309 let mut parent = trait_def_id;
310 let mut last_lint = None;
311 let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer);
313 // Descend the specialization tree, where `parent` is the current parent node.
315 use self::Inserted::*;
317 let insert_result = self.children.entry(parent).or_default().insert(
324 match insert_result {
325 BecameNewSibling(opt_lint) => {
326 last_lint = opt_lint;
329 ReplaceChildren(grand_children_to_be) => {
336 // and we are inserting the impl N. We want to make it:
344 // Adjust P's list of children: remove G and then add N.
346 let siblings = self.children.get_mut(&parent).unwrap();
347 for &grand_child_to_be in &grand_children_to_be {
348 siblings.remove_existing(tcx, grand_child_to_be);
350 siblings.insert_blindly(tcx, impl_def_id);
353 // Set G's parent to N and N's parent to P.
354 for &grand_child_to_be in &grand_children_to_be {
355 self.parent.insert(grand_child_to_be, impl_def_id);
357 self.parent.insert(impl_def_id, parent);
359 // Add G as N's child.
360 for &grand_child_to_be in &grand_children_to_be {
364 .insert_blindly(tcx, grand_child_to_be);
368 ShouldRecurseOn(new_parent) => {
374 self.parent.insert(impl_def_id, parent);
378 /// Insert cached metadata mapping from a child impl back to its parent.
379 fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId) {
380 if self.parent.insert(child, parent).is_some() {
382 "When recording an impl from the crate store, information about its parent \
383 was already present."
387 self.children.entry(parent).or_default().insert_blindly(tcx, child);