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
::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
),
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 ) -> Result
<Inserted
, OverlapError
>;
47 impl ChildrenExt
for Children
{
48 /// Insert an impl into this set of children without comparing to any existing impls.
49 fn insert_blindly(&mut self, tcx
: TyCtxt
<'tcx
>, impl_def_id
: DefId
) {
50 let trait_ref
= tcx
.impl_trait_ref(impl_def_id
).unwrap();
51 if let Some(st
) = fast_reject
::simplify_type(tcx
, trait_ref
.self_ty(), false) {
52 debug
!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id
, st
);
53 self.nonblanket_impls
.entry(st
).or_default().push(impl_def_id
)
55 debug
!("insert_blindly: impl_def_id={:?} st=None", impl_def_id
);
56 self.blanket_impls
.push(impl_def_id
)
60 /// Removes an impl from this set of children. Used when replacing
61 /// an impl with a parent. The impl must be present in the list of
63 fn remove_existing(&mut self, tcx
: TyCtxt
<'tcx
>, impl_def_id
: DefId
) {
64 let trait_ref
= tcx
.impl_trait_ref(impl_def_id
).unwrap();
65 let vec
: &mut Vec
<DefId
>;
66 if let Some(st
) = fast_reject
::simplify_type(tcx
, trait_ref
.self_ty(), false) {
67 debug
!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id
, st
);
68 vec
= self.nonblanket_impls
.get_mut(&st
).unwrap();
70 debug
!("remove_existing: impl_def_id={:?} st=None", impl_def_id
);
71 vec
= &mut self.blanket_impls
;
74 let index
= vec
.iter().position(|d
| *d
== impl_def_id
).unwrap();
78 /// Attempt to insert an impl into this set of children, while comparing for
79 /// specialization relationships.
84 simplified_self
: Option
<SimplifiedType
>,
85 ) -> Result
<Inserted
, OverlapError
> {
86 let mut last_lint
= None
;
87 let mut replace_children
= Vec
::new();
89 debug
!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id
, simplified_self
,);
91 let possible_siblings
= match simplified_self
{
92 Some(st
) => PotentialSiblings
::Filtered(filtered_children(self, st
)),
93 None
=> PotentialSiblings
::Unfiltered(iter_children(self)),
96 for possible_sibling
in possible_siblings
{
98 "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}",
99 impl_def_id
, simplified_self
, possible_sibling
,
102 let create_overlap_error
= |overlap
: traits
::coherence
::OverlapResult
<'_
>| {
103 let trait_ref
= overlap
.impl_header
.trait_ref
.unwrap();
104 let self_ty
= trait_ref
.self_ty();
106 // FIXME: should postpone string formatting until we decide to actually emit.
107 with_no_trimmed_paths(|| OverlapError
{
108 with_impl
: possible_sibling
,
109 trait_desc
: trait_ref
.print_only_trait_path().to_string(),
110 // Only report the `Self` type if it has at least
111 // some outer concrete shell; otherwise, it's
112 // not adding much information.
113 self_desc
: if self_ty
.has_concrete_skeleton() {
114 Some(self_ty
.to_string())
118 intercrate_ambiguity_causes
: overlap
.intercrate_ambiguity_causes
,
119 involves_placeholder
: overlap
.involves_placeholder
,
123 let report_overlap_error
= |overlap
: traits
::coherence
::OverlapResult
<'_
>,
125 // Found overlap, but no specialization; error out or report future-compat warning.
127 // Do we *still* get overlap if we disable the future-incompatible modes?
128 let should_err
= traits
::overlapping_impls(
132 traits
::SkipLeakCheck
::default(),
137 let error
= create_overlap_error(overlap
);
142 *last_lint
= Some(FutureCompatOverlapError
{
144 kind
: FutureCompatOverlapErrorKind
::LeakCheck
,
151 let last_lint_mut
= &mut last_lint
;
152 let (le
, ge
) = traits
::overlapping_impls(
156 traits
::SkipLeakCheck
::Yes
,
158 if let Some(overlap_kind
) =
159 tcx
.impls_are_allowed_to_overlap(impl_def_id
, possible_sibling
)
162 ty
::ImplOverlapKind
::Permitted { marker: _ }
=> {}
163 ty
::ImplOverlapKind
::Issue33140
=> {
164 *last_lint_mut
= Some(FutureCompatOverlapError
{
165 error
: create_overlap_error(overlap
),
166 kind
: FutureCompatOverlapErrorKind
::Issue33140
,
171 return Ok((false, false));
174 let le
= tcx
.specializes((impl_def_id
, possible_sibling
));
175 let ge
= tcx
.specializes((possible_sibling
, impl_def_id
));
178 report_overlap_error(overlap
, last_lint_mut
)
183 || Ok((false, false)),
188 "descending as child of TraitRef {:?}",
189 tcx
.impl_trait_ref(possible_sibling
).unwrap()
192 // The impl specializes `possible_sibling`.
193 return Ok(Inserted
::ShouldRecurseOn(possible_sibling
));
194 } else if ge
&& !le
{
196 "placing as parent of TraitRef {:?}",
197 tcx
.impl_trait_ref(possible_sibling
).unwrap()
200 replace_children
.push(possible_sibling
);
202 // Either there's no overlap, or the overlap was already reported by
207 if !replace_children
.is_empty() {
208 return Ok(Inserted
::ReplaceChildren(replace_children
));
211 // No overlap with any potential siblings, so add as a new sibling.
212 debug
!("placing as new sibling");
213 self.insert_blindly(tcx
, impl_def_id
);
214 Ok(Inserted
::BecameNewSibling(last_lint
))
218 fn iter_children(children
: &mut Children
) -> impl Iterator
<Item
= DefId
> + '_
{
219 let nonblanket
= children
.nonblanket_impls
.iter_mut().flat_map(|(_
, v
)| v
.iter());
220 children
.blanket_impls
.iter().chain(nonblanket
).cloned()
223 fn filtered_children(
224 children
: &mut Children
,
226 ) -> impl Iterator
<Item
= DefId
> + '_
{
227 let nonblanket
= children
.nonblanket_impls
.entry(st
).or_default().iter();
228 children
.blanket_impls
.iter().chain(nonblanket
).cloned()
231 // A custom iterator used by Children::insert
232 enum PotentialSiblings
<I
, J
>
234 I
: Iterator
<Item
= DefId
>,
235 J
: Iterator
<Item
= DefId
>,
241 impl<I
, J
> Iterator
for PotentialSiblings
<I
, J
>
243 I
: Iterator
<Item
= DefId
>,
244 J
: Iterator
<Item
= DefId
>,
248 fn next(&mut self) -> Option
<Self::Item
> {
250 PotentialSiblings
::Unfiltered(ref mut iter
) => iter
.next(),
251 PotentialSiblings
::Filtered(ref mut iter
) => iter
.next(),
257 /// Insert a local impl into the specialization graph. If an existing impl
258 /// conflicts with it (has overlap, but neither specializes the other),
259 /// information about the area of overlap is returned in the `Err`.
264 ) -> Result
<Option
<FutureCompatOverlapError
>, OverlapError
>;
266 /// Insert cached metadata mapping from a child impl back to its parent.
267 fn record_impl_from_cstore(&mut self, tcx
: TyCtxt
<'tcx
>, parent
: DefId
, child
: DefId
);
270 impl GraphExt
for Graph
{
271 /// Insert a local impl into the specialization graph. If an existing impl
272 /// conflicts with it (has overlap, but neither specializes the other),
273 /// information about the area of overlap is returned in the `Err`.
278 ) -> Result
<Option
<FutureCompatOverlapError
>, OverlapError
> {
279 assert
!(impl_def_id
.is_local());
281 let trait_ref
= tcx
.impl_trait_ref(impl_def_id
).unwrap();
282 let trait_def_id
= trait_ref
.def_id
;
285 "insert({:?}): inserting TraitRef {:?} into specialization graph",
286 impl_def_id
, trait_ref
289 // If the reference itself contains an earlier error (e.g., due to a
290 // resolution failure), then we just insert the impl at the top level of
291 // the graph and claim that there's no overlap (in order to suppress
293 if trait_ref
.references_error() {
295 "insert: inserting dummy node for erroneous TraitRef {:?}, \
296 impl_def_id={:?}, trait_def_id={:?}",
297 trait_ref
, impl_def_id
, trait_def_id
300 self.parent
.insert(impl_def_id
, trait_def_id
);
301 self.children
.entry(trait_def_id
).or_default().insert_blindly(tcx
, impl_def_id
);
305 let mut parent
= trait_def_id
;
306 let mut last_lint
= None
;
307 let simplified
= fast_reject
::simplify_type(tcx
, trait_ref
.self_ty(), false);
309 // Descend the specialization tree, where `parent` is the current parent node.
311 use self::Inserted
::*;
314 self.children
.entry(parent
).or_default().insert(tcx
, impl_def_id
, simplified
)?
;
316 match insert_result
{
317 BecameNewSibling(opt_lint
) => {
318 last_lint
= opt_lint
;
321 ReplaceChildren(grand_children_to_be
) => {
328 // and we are inserting the impl N. We want to make it:
336 // Adjust P's list of children: remove G and then add N.
338 let siblings
= self.children
.get_mut(&parent
).unwrap();
339 for &grand_child_to_be
in &grand_children_to_be
{
340 siblings
.remove_existing(tcx
, grand_child_to_be
);
342 siblings
.insert_blindly(tcx
, impl_def_id
);
345 // Set G's parent to N and N's parent to P.
346 for &grand_child_to_be
in &grand_children_to_be
{
347 self.parent
.insert(grand_child_to_be
, impl_def_id
);
349 self.parent
.insert(impl_def_id
, parent
);
351 // Add G as N's child.
352 for &grand_child_to_be
in &grand_children_to_be
{
356 .insert_blindly(tcx
, grand_child_to_be
);
360 ShouldRecurseOn(new_parent
) => {
366 self.parent
.insert(impl_def_id
, parent
);
370 /// Insert cached metadata mapping from a child impl back to its parent.
371 fn record_impl_from_cstore(&mut self, tcx
: TyCtxt
<'tcx
>, parent
: DefId
, child
: DefId
) {
372 if self.parent
.insert(child
, parent
).is_some() {
374 "When recording an impl from the crate store, information about its parent \
375 was already present."
379 self.children
.entry(parent
).or_default().insert_blindly(tcx
, child
);