1 use super::OverlapError
;
4 use rustc_hir
::def_id
::DefId
;
5 use rustc_middle
::ty
::fast_reject
::{self, SimplifiedType}
;
6 use rustc_middle
::ty
::{self, TyCtxt, TypeFoldable}
;
8 pub use rustc_middle
::traits
::specialization_graph
::*;
10 #[derive(Copy, Clone, Debug)]
11 pub enum FutureCompatOverlapErrorKind
{
17 pub struct FutureCompatOverlapError
{
18 pub error
: OverlapError
,
19 pub kind
: FutureCompatOverlapErrorKind
,
22 /// The result of attempting to insert an impl into a group of children.
24 /// The impl was inserted as a new child in this group of children.
25 BecameNewSibling(Option
<FutureCompatOverlapError
>),
27 /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc.
28 ReplaceChildren(Vec
<DefId
>),
30 /// The impl is a specialization of an existing child.
31 ShouldRecurseOn(DefId
),
35 fn insert_blindly(&mut self, tcx
: TyCtxt
<'tcx
>, impl_def_id
: DefId
);
36 fn remove_existing(&mut self, tcx
: TyCtxt
<'tcx
>, impl_def_id
: DefId
);
42 simplified_self
: Option
<SimplifiedType
>,
43 ) -> Result
<Inserted
, OverlapError
>;
46 impl ChildrenExt
for Children
{
47 /// Insert an impl into this set of children without comparing to any existing impls.
48 fn insert_blindly(&mut self, tcx
: TyCtxt
<'tcx
>, impl_def_id
: DefId
) {
49 let trait_ref
= tcx
.impl_trait_ref(impl_def_id
).unwrap();
50 if let Some(st
) = fast_reject
::simplify_type(tcx
, trait_ref
.self_ty(), false) {
51 debug
!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id
, st
);
52 self.nonblanket_impls
.entry(st
).or_default().push(impl_def_id
)
54 debug
!("insert_blindly: impl_def_id={:?} st=None", impl_def_id
);
55 self.blanket_impls
.push(impl_def_id
)
59 /// Removes an impl from this set of children. Used when replacing
60 /// an impl with a parent. The impl must be present in the list of
62 fn remove_existing(&mut self, tcx
: TyCtxt
<'tcx
>, impl_def_id
: DefId
) {
63 let trait_ref
= tcx
.impl_trait_ref(impl_def_id
).unwrap();
64 let vec
: &mut Vec
<DefId
>;
65 if let Some(st
) = fast_reject
::simplify_type(tcx
, trait_ref
.self_ty(), false) {
66 debug
!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id
, st
);
67 vec
= self.nonblanket_impls
.get_mut(&st
).unwrap();
69 debug
!("remove_existing: impl_def_id={:?} st=None", impl_def_id
);
70 vec
= &mut self.blanket_impls
;
73 let index
= vec
.iter().position(|d
| *d
== impl_def_id
).unwrap();
77 /// Attempt to insert an impl into this set of children, while comparing for
78 /// specialization relationships.
83 simplified_self
: Option
<SimplifiedType
>,
84 ) -> Result
<Inserted
, OverlapError
> {
85 let mut last_lint
= None
;
86 let mut replace_children
= Vec
::new();
88 debug
!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id
, simplified_self
,);
90 let possible_siblings
= match simplified_self
{
91 Some(st
) => PotentialSiblings
::Filtered(filtered_children(self, st
)),
92 None
=> PotentialSiblings
::Unfiltered(iter_children(self)),
95 for possible_sibling
in possible_siblings
{
97 "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}",
98 impl_def_id
, simplified_self
, possible_sibling
,
101 let create_overlap_error
= |overlap
: traits
::coherence
::OverlapResult
<'_
>| {
102 let trait_ref
= overlap
.impl_header
.trait_ref
.unwrap();
103 let self_ty
= trait_ref
.self_ty();
106 with_impl
: possible_sibling
,
107 trait_desc
: trait_ref
.print_only_trait_path().to_string(),
108 // Only report the `Self` type if it has at least
109 // some outer concrete shell; otherwise, it's
110 // not adding much information.
111 self_desc
: if self_ty
.has_concrete_skeleton() {
112 Some(self_ty
.to_string())
116 intercrate_ambiguity_causes
: overlap
.intercrate_ambiguity_causes
,
117 involves_placeholder
: overlap
.involves_placeholder
,
121 let report_overlap_error
= |overlap
: traits
::coherence
::OverlapResult
<'_
>,
123 // Found overlap, but no specialization; error out or report future-compat warning.
125 // Do we *still* get overlap if we disable the future-incompatible modes?
126 let should_err
= traits
::overlapping_impls(
130 traits
::SkipLeakCheck
::default(),
135 let error
= create_overlap_error(overlap
);
140 *last_lint
= Some(FutureCompatOverlapError
{
142 kind
: FutureCompatOverlapErrorKind
::LeakCheck
,
149 let last_lint_mut
= &mut last_lint
;
150 let (le
, ge
) = traits
::overlapping_impls(
154 traits
::SkipLeakCheck
::Yes
,
156 if let Some(overlap_kind
) =
157 tcx
.impls_are_allowed_to_overlap(impl_def_id
, possible_sibling
)
160 ty
::ImplOverlapKind
::Permitted { marker: _ }
=> {}
161 ty
::ImplOverlapKind
::Issue33140
=> {
162 *last_lint_mut
= Some(FutureCompatOverlapError
{
163 error
: create_overlap_error(overlap
),
164 kind
: FutureCompatOverlapErrorKind
::Issue33140
,
169 return Ok((false, false));
172 let le
= tcx
.specializes((impl_def_id
, possible_sibling
));
173 let ge
= tcx
.specializes((possible_sibling
, impl_def_id
));
176 report_overlap_error(overlap
, last_lint_mut
)
181 || Ok((false, false)),
186 "descending as child of TraitRef {:?}",
187 tcx
.impl_trait_ref(possible_sibling
).unwrap()
190 // The impl specializes `possible_sibling`.
191 return Ok(Inserted
::ShouldRecurseOn(possible_sibling
));
192 } else if ge
&& !le
{
194 "placing as parent of TraitRef {:?}",
195 tcx
.impl_trait_ref(possible_sibling
).unwrap()
198 replace_children
.push(possible_sibling
);
200 // Either there's no overlap, or the overlap was already reported by
205 if !replace_children
.is_empty() {
206 return Ok(Inserted
::ReplaceChildren(replace_children
));
209 // No overlap with any potential siblings, so add as a new sibling.
210 debug
!("placing as new sibling");
211 self.insert_blindly(tcx
, impl_def_id
);
212 Ok(Inserted
::BecameNewSibling(last_lint
))
216 fn iter_children(children
: &mut Children
) -> impl Iterator
<Item
= DefId
> + '_
{
217 let nonblanket
= children
.nonblanket_impls
.iter_mut().flat_map(|(_
, v
)| v
.iter());
218 children
.blanket_impls
.iter().chain(nonblanket
).cloned()
221 fn filtered_children(
222 children
: &mut Children
,
224 ) -> impl Iterator
<Item
= DefId
> + '_
{
225 let nonblanket
= children
.nonblanket_impls
.entry(st
).or_default().iter();
226 children
.blanket_impls
.iter().chain(nonblanket
).cloned()
229 // A custom iterator used by Children::insert
230 enum PotentialSiblings
<I
, J
>
232 I
: Iterator
<Item
= DefId
>,
233 J
: Iterator
<Item
= DefId
>,
239 impl<I
, J
> Iterator
for PotentialSiblings
<I
, J
>
241 I
: Iterator
<Item
= DefId
>,
242 J
: Iterator
<Item
= DefId
>,
246 fn next(&mut self) -> Option
<Self::Item
> {
248 PotentialSiblings
::Unfiltered(ref mut iter
) => iter
.next(),
249 PotentialSiblings
::Filtered(ref mut iter
) => iter
.next(),
255 /// Insert a local impl into the specialization graph. If an existing impl
256 /// conflicts with it (has overlap, but neither specializes the other),
257 /// information about the area of overlap is returned in the `Err`.
262 ) -> Result
<Option
<FutureCompatOverlapError
>, OverlapError
>;
264 /// Insert cached metadata mapping from a child impl back to its parent.
265 fn record_impl_from_cstore(&mut self, tcx
: TyCtxt
<'tcx
>, parent
: DefId
, child
: DefId
);
268 impl GraphExt
for Graph
{
269 /// Insert a local impl into the specialization graph. If an existing impl
270 /// conflicts with it (has overlap, but neither specializes the other),
271 /// information about the area of overlap is returned in the `Err`.
276 ) -> Result
<Option
<FutureCompatOverlapError
>, OverlapError
> {
277 assert
!(impl_def_id
.is_local());
279 let trait_ref
= tcx
.impl_trait_ref(impl_def_id
).unwrap();
280 let trait_def_id
= trait_ref
.def_id
;
283 "insert({:?}): inserting TraitRef {:?} into specialization graph",
284 impl_def_id
, trait_ref
287 // If the reference itself contains an earlier error (e.g., due to a
288 // resolution failure), then we just insert the impl at the top level of
289 // the graph and claim that there's no overlap (in order to suppress
291 if trait_ref
.references_error() {
293 "insert: inserting dummy node for erroneous TraitRef {:?}, \
294 impl_def_id={:?}, trait_def_id={:?}",
295 trait_ref
, impl_def_id
, trait_def_id
298 self.parent
.insert(impl_def_id
, trait_def_id
);
299 self.children
.entry(trait_def_id
).or_default().insert_blindly(tcx
, impl_def_id
);
303 let mut parent
= trait_def_id
;
304 let mut last_lint
= None
;
305 let simplified
= fast_reject
::simplify_type(tcx
, trait_ref
.self_ty(), false);
307 // Descend the specialization tree, where `parent` is the current parent node.
309 use self::Inserted
::*;
312 self.children
.entry(parent
).or_default().insert(tcx
, impl_def_id
, simplified
)?
;
314 match insert_result
{
315 BecameNewSibling(opt_lint
) => {
316 last_lint
= opt_lint
;
319 ReplaceChildren(grand_children_to_be
) => {
326 // and we are inserting the impl N. We want to make it:
334 // Adjust P's list of children: remove G and then add N.
336 let siblings
= self.children
.get_mut(&parent
).unwrap();
337 for &grand_child_to_be
in &grand_children_to_be
{
338 siblings
.remove_existing(tcx
, grand_child_to_be
);
340 siblings
.insert_blindly(tcx
, impl_def_id
);
343 // Set G's parent to N and N's parent to P.
344 for &grand_child_to_be
in &grand_children_to_be
{
345 self.parent
.insert(grand_child_to_be
, impl_def_id
);
347 self.parent
.insert(impl_def_id
, parent
);
349 // Add G as N's child.
350 for &grand_child_to_be
in &grand_children_to_be
{
354 .insert_blindly(tcx
, grand_child_to_be
);
358 ShouldRecurseOn(new_parent
) => {
364 self.parent
.insert(impl_def_id
, parent
);
368 /// Insert cached metadata mapping from a child impl back to its parent.
369 fn record_impl_from_cstore(&mut self, tcx
: TyCtxt
<'tcx
>, parent
: DefId
, child
: DefId
) {
370 if self.parent
.insert(child
, parent
).is_some() {
372 "When recording an impl from the crate store, information about its parent \
373 was already present."
377 self.children
.entry(parent
).or_default().insert_blindly(tcx
, child
);