use super::OverlapError;
use crate::traits;
use rustc_errors::ErrorGuaranteed;
use rustc_hir::def_id::DefId;
use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams};
use rustc_middle::ty::{self, TyCtxt, TypeVisitableExt};
pub use rustc_middle::traits::specialization_graph::*;
#[derive(Copy, Clone, Debug)]
pub enum FutureCompatOverlapErrorKind {
Issue33140,
LeakCheck,
}
#[derive(Debug)]
pub struct FutureCompatOverlapError<'tcx> {
pub error: OverlapError<'tcx>,
pub kind: FutureCompatOverlapErrorKind,
}
#[derive(Debug)]
enum Inserted<'tcx> {
BecameNewSibling(Option<FutureCompatOverlapError<'tcx>>),
ReplaceChildren(Vec<DefId>),
ShouldRecurseOn(DefId),
}
trait ChildrenExt<'tcx> {
fn insert_blindly(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId);
fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId);
fn insert(
&mut self,
tcx: TyCtxt<'tcx>,
impl_def_id: DefId,
simplified_self: Option<SimplifiedType>,
overlap_mode: OverlapMode,
) -> Result<Inserted<'tcx>, OverlapError<'tcx>>;
}
impl<'tcx> ChildrenExt<'tcx> for Children {
fn insert_blindly(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId) {
let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().skip_binder();
if let Some(st) =
fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsCandidateKey)
{
debug!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id, st);
self.non_blanket_impls.entry(st).or_default().push(impl_def_id)
} else {
debug!("insert_blindly: impl_def_id={:?} st=None", impl_def_id);
self.blanket_impls.push(impl_def_id)
}
}
fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId) {
let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().skip_binder();
let vec: &mut Vec<DefId>;
if let Some(st) =
fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsCandidateKey)
{
debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st);
vec = self.non_blanket_impls.get_mut(&st).unwrap();
} else {
debug!("remove_existing: impl_def_id={:?} st=None", impl_def_id);
vec = &mut self.blanket_impls;
}
let index = vec.iter().position(|d| *d == impl_def_id).unwrap();
vec.remove(index);
}
#[instrument(level = "debug", skip(self, tcx), ret)]
fn insert(
&mut self,
tcx: TyCtxt<'tcx>,
impl_def_id: DefId,
simplified_self: Option<SimplifiedType>,
overlap_mode: OverlapMode,
) -> Result<Inserted<'tcx>, OverlapError<'tcx>> {
let mut last_lint = None;
let mut replace_children = Vec::new();
let possible_siblings = match simplified_self {
Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)),
None => PotentialSiblings::Unfiltered(iter_children(self)),
};
for possible_sibling in possible_siblings {
debug!(?possible_sibling);
let create_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>| {
let trait_ref = overlap.impl_header.trait_ref.unwrap();
let self_ty = trait_ref.self_ty();
OverlapError {
with_impl: possible_sibling,
trait_ref,
self_ty: self_ty.has_concrete_skeleton().then_some(self_ty),
intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
involves_placeholder: overlap.involves_placeholder,
}
};
let report_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>,
last_lint: &mut _| {
let should_err = traits::overlapping_impls(
tcx,
possible_sibling,
impl_def_id,
traits::SkipLeakCheck::default(),
overlap_mode,
)
.is_some();
let error = create_overlap_error(overlap);
if should_err {
Err(error)
} else {
*last_lint = Some(FutureCompatOverlapError {
error,
kind: FutureCompatOverlapErrorKind::LeakCheck,
});
Ok((false, false))
}
};
let last_lint_mut = &mut last_lint;
let (le, ge) = traits::overlapping_impls(
tcx,
possible_sibling,
impl_def_id,
traits::SkipLeakCheck::Yes,
overlap_mode,
)
.map_or(Ok((false, false)), |overlap| {
if let Some(overlap_kind) =
tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling)
{
match overlap_kind {
ty::ImplOverlapKind::Permitted { marker: _ } => {}
ty::ImplOverlapKind::Issue33140 => {
*last_lint_mut = Some(FutureCompatOverlapError {
error: create_overlap_error(overlap),
kind: FutureCompatOverlapErrorKind::Issue33140,
});
}
}
return Ok((false, false));
}
let le = tcx.specializes((impl_def_id, possible_sibling));
let ge = tcx.specializes((possible_sibling, impl_def_id));
if le == ge { report_overlap_error(overlap, last_lint_mut) } else { Ok((le, ge)) }
})?;
if le && !ge {
debug!(
"descending as child of TraitRef {:?}",
tcx.impl_trait_ref(possible_sibling).unwrap().instantiate_identity()
);
return Ok(Inserted::ShouldRecurseOn(possible_sibling));
} else if ge && !le {
debug!(
"placing as parent of TraitRef {:?}",
tcx.impl_trait_ref(possible_sibling).unwrap().instantiate_identity()
);
replace_children.push(possible_sibling);
} else {
}
}
if !replace_children.is_empty() {
return Ok(Inserted::ReplaceChildren(replace_children));
}
debug!("placing as new sibling");
self.insert_blindly(tcx, impl_def_id);
Ok(Inserted::BecameNewSibling(last_lint))
}
}
fn iter_children(children: &mut Children) -> impl Iterator<Item = DefId> + '_ {
let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter());
children.blanket_impls.iter().chain(nonblanket).cloned()
}
fn filtered_children(
children: &mut Children,
st: SimplifiedType,
) -> impl Iterator<Item = DefId> + '_ {
let nonblanket = children.non_blanket_impls.entry(st).or_default().iter();
children.blanket_impls.iter().chain(nonblanket).cloned()
}
enum PotentialSiblings<I, J>
where
I: Iterator<Item = DefId>,
J: Iterator<Item = DefId>,
{
Unfiltered(I),
Filtered(J),
}
impl<I, J> Iterator for PotentialSiblings<I, J>
where
I: Iterator<Item = DefId>,
J: Iterator<Item = DefId>,
{
type Item = DefId;
fn next(&mut self) -> Option<Self::Item> {
match *self {
PotentialSiblings::Unfiltered(ref mut iter) => iter.next(),
PotentialSiblings::Filtered(ref mut iter) => iter.next(),
}
}
}
pub trait GraphExt<'tcx> {
fn insert(
&mut self,
tcx: TyCtxt<'tcx>,
impl_def_id: DefId,
overlap_mode: OverlapMode,
) -> Result<Option<FutureCompatOverlapError<'tcx>>, OverlapError<'tcx>>;
fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'tcx>, parent: DefId, child: DefId);
}
impl<'tcx> GraphExt<'tcx> for Graph {
fn insert(
&mut self,
tcx: TyCtxt<'tcx>,
impl_def_id: DefId,
overlap_mode: OverlapMode,
) -> Result<Option<FutureCompatOverlapError<'tcx>>, OverlapError<'tcx>> {
assert!(impl_def_id.is_local());
let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().skip_binder();
let trait_def_id = trait_ref.def_id;
debug!(
"insert({:?}): inserting TraitRef {:?} into specialization graph",
impl_def_id, trait_ref
);
if trait_ref.references_error() {
debug!(
"insert: inserting dummy node for erroneous TraitRef {:?}, \
impl_def_id={:?}, trait_def_id={:?}",
trait_ref, impl_def_id, trait_def_id
);
self.parent.insert(impl_def_id, trait_def_id);
self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id);
return Ok(None);
}
let mut parent = trait_def_id;
let mut last_lint = None;
let simplified =
fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsCandidateKey);
loop {
use self::Inserted::*;
let insert_result = self.children.entry(parent).or_default().insert(
tcx,
impl_def_id,
simplified,
overlap_mode,
)?;
match insert_result {
BecameNewSibling(opt_lint) => {
last_lint = opt_lint;
break;
}
ReplaceChildren(grand_children_to_be) => {
{
let siblings = self.children.get_mut(&parent).unwrap();
for &grand_child_to_be in &grand_children_to_be {
siblings.remove_existing(tcx, grand_child_to_be);
}
siblings.insert_blindly(tcx, impl_def_id);
}
for &grand_child_to_be in &grand_children_to_be {
self.parent.insert(grand_child_to_be, impl_def_id);
}
self.parent.insert(impl_def_id, parent);
for &grand_child_to_be in &grand_children_to_be {
self.children
.entry(impl_def_id)
.or_default()
.insert_blindly(tcx, grand_child_to_be);
}
break;
}
ShouldRecurseOn(new_parent) => {
parent = new_parent;
}
}
}
self.parent.insert(impl_def_id, parent);
Ok(last_lint)
}
fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'tcx>, parent: DefId, child: DefId) {
if self.parent.insert(child, parent).is_some() {
bug!(
"When recording an impl from the crate store, information about its parent \
was already present."
);
}
self.children.entry(parent).or_default().insert_blindly(tcx, child);
}
}
pub(crate) fn assoc_def(
tcx: TyCtxt<'_>,
impl_def_id: DefId,
assoc_def_id: DefId,
) -> Result<LeafDef, ErrorGuaranteed> {
let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
let trait_def = tcx.trait_def(trait_def_id);
if let Some(&impl_item_id) = tcx.impl_item_implementor_ids(impl_def_id).get(&assoc_def_id) {
let item = tcx.associated_item(impl_item_id);
let impl_node = Node::Impl(impl_def_id);
return Ok(LeafDef {
item,
defining_node: impl_node,
finalizing_node: if item.defaultness(tcx).is_default() {
None
} else {
Some(impl_node)
},
});
}
let ancestors = trait_def.ancestors(tcx, impl_def_id)?;
if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_def_id) {
Ok(assoc_item)
} else {
bug!(
"No associated type `{}` for {}",
tcx.item_name(assoc_def_id),
tcx.def_path_str(impl_def_id)
)
}
}