compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs

   1 use super::OverlapError;
   2
   3 use crate::traits;
   4 use rustc_errors::ErrorGuaranteed;
   5 use rustc_hir::def_id::DefId;
   6 use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams};
   7 use rustc_middle::ty::{self, TyCtxt, TypeVisitable};
   8
   9 pub use rustc_middle::traits::specialization_graph::*;
  10
  11 #[derive(Copy, Clone, Debug)]
  12 pub enum FutureCompatOverlapErrorKind {
  13     Issue33140,
  14     LeakCheck,
  15 }
  16
  17 #[derive(Debug)]
  18 pub struct FutureCompatOverlapError<'tcx> {
  19     pub error: OverlapError<'tcx>,
  20     pub kind: FutureCompatOverlapErrorKind,
  21 }
  22
  23 /// The result of attempting to insert an impl into a group of children.
  24 enum Inserted<'tcx> {
  25     /// The impl was inserted as a new child in this group of children.
  26     BecameNewSibling(Option<FutureCompatOverlapError<'tcx>>),
  27
  28     /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc.
  29     ReplaceChildren(Vec<DefId>),
  30
  31     /// The impl is a specialization of an existing child.
  32     ShouldRecurseOn(DefId),
  33 }
  34
  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);
  38
  39     fn insert(
  40         &mut self,
  41         tcx: TyCtxt<'tcx>,
  42         impl_def_id: DefId,
  43         simplified_self: Option<SimplifiedType>,
  44         overlap_mode: OverlapMode,
  45     ) -> Result<Inserted<'tcx>, OverlapError<'tcx>>;
  46 }
  47
  48 impl<'tcx> ChildrenExt<'tcx> 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<'tcx>, 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)
  53         {
  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)
  56         } else {
  57             debug!("insert_blindly: impl_def_id={:?} st=None", impl_def_id);
  58             self.blanket_impls.push(impl_def_id)
  59         }
  60     }
  61
  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
  64     /// children already.
  65     fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, 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)
  69         {
  70             debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st);
  71             vec = self.non_blanket_impls.get_mut(&st).unwrap();
  72         } else {
  73             debug!("remove_existing: impl_def_id={:?} st=None", impl_def_id);
  74             vec = &mut self.blanket_impls;
  75         }
  76
  77         let index = vec.iter().position(|d| *d == impl_def_id).unwrap();
  78         vec.remove(index);
  79     }
  80
  81     /// Attempt to insert an impl into this set of children, while comparing for
  82     /// specialization relationships.
  83     fn insert(
  84         &mut self,
  85         tcx: TyCtxt<'tcx>,
  86         impl_def_id: DefId,
  87         simplified_self: Option<SimplifiedType>,
  88         overlap_mode: OverlapMode,
  89     ) -> Result<Inserted<'tcx>, OverlapError<'tcx>> {
  90         let mut last_lint = None;
  91         let mut replace_children = Vec::new();
  92
  93         debug!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id, simplified_self,);
  94
  95         let possible_siblings = match simplified_self {
  96             Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)),
  97             None => PotentialSiblings::Unfiltered(iter_children(self)),
  98         };
  99
 100         for possible_sibling in possible_siblings {
 101             debug!(
 102                 "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}",
 103                 impl_def_id, simplified_self, possible_sibling,
 104             );
 105
 106             let create_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>| {
 107                 let trait_ref = overlap.impl_header.trait_ref.unwrap();
 108                 let self_ty = trait_ref.self_ty();
 109
 110                 OverlapError {
 111                     with_impl: possible_sibling,
 112                     trait_ref,
 113                     // Only report the `Self` type if it has at least
 114                     // some outer concrete shell; otherwise, it's
 115                     // not adding much information.
 116                     self_ty: if self_ty.has_concrete_skeleton() { Some(self_ty) } else { None },
 117                     intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
 118                     involves_placeholder: overlap.involves_placeholder,
 119                 }
 120             };
 121
 122             let report_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>,
 123                                         last_lint: &mut _| {
 124                 // Found overlap, but no specialization; error out or report future-compat warning.
 125
 126                 // Do we *still* get overlap if we disable the future-incompatible modes?
 127                 let should_err = traits::overlapping_impls(
 128                     tcx,
 129                     possible_sibling,
 130                     impl_def_id,
 131                     traits::SkipLeakCheck::default(),
 132                     overlap_mode,
 133                 )
 134                 .is_some();
 135
 136                 let error = create_overlap_error(overlap);
 137
 138                 if should_err {
 139                     Err(error)
 140                 } else {
 141                     *last_lint = Some(FutureCompatOverlapError {
 142                         error,
 143                         kind: FutureCompatOverlapErrorKind::LeakCheck,
 144                     });
 145
 146                     Ok((false, false))
 147                 }
 148             };
 149
 150             let last_lint_mut = &mut last_lint;
 151             let (le, ge) = traits::overlapping_impls(
 152                 tcx,
 153                 possible_sibling,
 154                 impl_def_id,
 155                 traits::SkipLeakCheck::Yes,
 156                 overlap_mode,
 157             )
 158             .map_or(Ok((false, false)), |overlap| {
 159                 if let Some(overlap_kind) =
 160                     tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling)
 161                 {
 162                     match overlap_kind {
 163                         ty::ImplOverlapKind::Permitted { marker: _ } => {}
 164                         ty::ImplOverlapKind::Issue33140 => {
 165                             *last_lint_mut = Some(FutureCompatOverlapError {
 166                                 error: create_overlap_error(overlap),
 167                                 kind: FutureCompatOverlapErrorKind::Issue33140,
 168                             });
 169                         }
 170                     }
 171
 172                     return Ok((false, false));
 173                 }
 174
 175                 let le = tcx.specializes((impl_def_id, possible_sibling));
 176                 let ge = tcx.specializes((possible_sibling, impl_def_id));
 177
 178                 if le == ge { report_overlap_error(overlap, last_lint_mut) } else { Ok((le, ge)) }
 179             })?;
 180
 181             if le && !ge {
 182                 debug!(
 183                     "descending as child of TraitRef {:?}",
 184                     tcx.impl_trait_ref(possible_sibling).unwrap()
 185                 );
 186
 187                 // The impl specializes `possible_sibling`.
 188                 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
 189             } else if ge && !le {
 190                 debug!(
 191                     "placing as parent of TraitRef {:?}",
 192                     tcx.impl_trait_ref(possible_sibling).unwrap()
 193                 );
 194
 195                 replace_children.push(possible_sibling);
 196             } else {
 197                 // Either there's no overlap, or the overlap was already reported by
 198                 // `overlap_error`.
 199             }
 200         }
 201
 202         if !replace_children.is_empty() {
 203             return Ok(Inserted::ReplaceChildren(replace_children));
 204         }
 205
 206         // No overlap with any potential siblings, so add as a new sibling.
 207         debug!("placing as new sibling");
 208         self.insert_blindly(tcx, impl_def_id);
 209         Ok(Inserted::BecameNewSibling(last_lint))
 210     }
 211 }
 212
 213 fn iter_children(children: &mut Children) -> impl Iterator<Item = DefId> + '_ {
 214     let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter());
 215     children.blanket_impls.iter().chain(nonblanket).cloned()
 216 }
 217
 218 fn filtered_children(
 219     children: &mut Children,
 220     st: SimplifiedType,
 221 ) -> impl Iterator<Item = DefId> + '_ {
 222     let nonblanket = children.non_blanket_impls.entry(st).or_default().iter();
 223     children.blanket_impls.iter().chain(nonblanket).cloned()
 224 }
 225
 226 // A custom iterator used by Children::insert
 227 enum PotentialSiblings<I, J>
 228 where
 229     I: Iterator<Item = DefId>,
 230     J: Iterator<Item = DefId>,
 231 {
 232     Unfiltered(I),
 233     Filtered(J),
 234 }
 235
 236 impl<I, J> Iterator for PotentialSiblings<I, J>
 237 where
 238     I: Iterator<Item = DefId>,
 239     J: Iterator<Item = DefId>,
 240 {
 241     type Item = DefId;
 242
 243     fn next(&mut self) -> Option<Self::Item> {
 244         match *self {
 245             PotentialSiblings::Unfiltered(ref mut iter) => iter.next(),
 246             PotentialSiblings::Filtered(ref mut iter) => iter.next(),
 247         }
 248     }
 249 }
 250
 251 pub trait GraphExt<'tcx> {
 252     /// Insert a local impl into the specialization graph. If an existing impl
 253     /// conflicts with it (has overlap, but neither specializes the other),
 254     /// information about the area of overlap is returned in the `Err`.
 255     fn insert(
 256         &mut self,
 257         tcx: TyCtxt<'tcx>,
 258         impl_def_id: DefId,
 259         overlap_mode: OverlapMode,
 260     ) -> Result<Option<FutureCompatOverlapError<'tcx>>, OverlapError<'tcx>>;
 261
 262     /// Insert cached metadata mapping from a child impl back to its parent.
 263     fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'tcx>, parent: DefId, child: DefId);
 264 }
 265
 266 impl<'tcx> GraphExt<'tcx> for Graph {
 267     /// Insert a local impl into the specialization graph. If an existing impl
 268     /// conflicts with it (has overlap, but neither specializes the other),
 269     /// information about the area of overlap is returned in the `Err`.
 270     fn insert(
 271         &mut self,
 272         tcx: TyCtxt<'tcx>,
 273         impl_def_id: DefId,
 274         overlap_mode: OverlapMode,
 275     ) -> Result<Option<FutureCompatOverlapError<'tcx>>, OverlapError<'tcx>> {
 276         assert!(impl_def_id.is_local());
 277
 278         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
 279         let trait_def_id = trait_ref.def_id;
 280
 281         debug!(
 282             "insert({:?}): inserting TraitRef {:?} into specialization graph",
 283             impl_def_id, trait_ref
 284         );
 285
 286         // If the reference itself contains an earlier error (e.g., due to a
 287         // resolution failure), then we just insert the impl at the top level of
 288         // the graph and claim that there's no overlap (in order to suppress
 289         // bogus errors).
 290         if trait_ref.references_error() {
 291             debug!(
 292                 "insert: inserting dummy node for erroneous TraitRef {:?}, \
 293                  impl_def_id={:?}, trait_def_id={:?}",
 294                 trait_ref, impl_def_id, trait_def_id
 295             );
 296
 297             self.parent.insert(impl_def_id, trait_def_id);
 298             self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id);
 299             return Ok(None);
 300         }
 301
 302         let mut parent = trait_def_id;
 303         let mut last_lint = None;
 304         let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer);
 305
 306         // Descend the specialization tree, where `parent` is the current parent node.
 307         loop {
 308             use self::Inserted::*;
 309
 310             let insert_result = self.children.entry(parent).or_default().insert(
 311                 tcx,
 312                 impl_def_id,
 313                 simplified,
 314                 overlap_mode,
 315             )?;
 316
 317             match insert_result {
 318                 BecameNewSibling(opt_lint) => {
 319                     last_lint = opt_lint;
 320                     break;
 321                 }
 322                 ReplaceChildren(grand_children_to_be) => {
 323                     // We currently have
 324                     //
 325                     //     P
 326                     //     |
 327                     //     G
 328                     //
 329                     // and we are inserting the impl N. We want to make it:
 330                     //
 331                     //     P
 332                     //     |
 333                     //     N
 334                     //     |
 335                     //     G
 336
 337                     // Adjust P's list of children: remove G and then add N.
 338                     {
 339                         let siblings = self.children.get_mut(&parent).unwrap();
 340                         for &grand_child_to_be in &grand_children_to_be {
 341                             siblings.remove_existing(tcx, grand_child_to_be);
 342                         }
 343                         siblings.insert_blindly(tcx, impl_def_id);
 344                     }
 345
 346                     // Set G's parent to N and N's parent to P.
 347                     for &grand_child_to_be in &grand_children_to_be {
 348                         self.parent.insert(grand_child_to_be, impl_def_id);
 349                     }
 350                     self.parent.insert(impl_def_id, parent);
 351
 352                     // Add G as N's child.
 353                     for &grand_child_to_be in &grand_children_to_be {
 354                         self.children
 355                             .entry(impl_def_id)
 356                             .or_default()
 357                             .insert_blindly(tcx, grand_child_to_be);
 358                     }
 359                     break;
 360                 }
 361                 ShouldRecurseOn(new_parent) => {
 362                     parent = new_parent;
 363                 }
 364             }
 365         }
 366
 367         self.parent.insert(impl_def_id, parent);
 368         Ok(last_lint)
 369     }
 370
 371     /// Insert cached metadata mapping from a child impl back to its parent.
 372     fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'tcx>, parent: DefId, child: DefId) {
 373         if self.parent.insert(child, parent).is_some() {
 374             bug!(
 375                 "When recording an impl from the crate store, information about its parent \
 376                  was already present."
 377             );
 378         }
 379
 380         self.children.entry(parent).or_default().insert_blindly(tcx, child);
 381     }
 382 }
 383
 384 /// Locate the definition of an associated type in the specialization hierarchy,
 385 /// starting from the given impl.
 386 pub(crate) fn assoc_def(
 387     tcx: TyCtxt<'_>,
 388     impl_def_id: DefId,
 389     assoc_def_id: DefId,
 390 ) -> Result<LeafDef, ErrorGuaranteed> {
 391     let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id;
 392     let trait_def = tcx.trait_def(trait_def_id);
 393
 394     // This function may be called while we are still building the
 395     // specialization graph that is queried below (via TraitDef::ancestors()),
 396     // so, in order to avoid unnecessary infinite recursion, we manually look
 397     // for the associated item at the given impl.
 398     // If there is no such item in that impl, this function will fail with a
 399     // cycle error if the specialization graph is currently being built.
 400     if let Some(&impl_item_id) = tcx.impl_item_implementor_ids(impl_def_id).get(&assoc_def_id) {
 401         let &item = tcx.associated_item(impl_item_id);
 402         let impl_node = Node::Impl(impl_def_id);
 403         return Ok(LeafDef {
 404             item,
 405             defining_node: impl_node,
 406             finalizing_node: if item.defaultness(tcx).is_default() {
 407                 None
 408             } else {
 409                 Some(impl_node)
 410             },
 411         });
 412     }
 413
 414     let ancestors = trait_def.ancestors(tcx, impl_def_id)?;
 415     if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_def_id) {
 416         Ok(assoc_item)
 417     } else {
 418         // This is saying that neither the trait nor
 419         // the impl contain a definition for this
 420         // associated type.  Normally this situation
 421         // could only arise through a compiler bug --
 422         // if the user wrote a bad item name, it
 423         // should have failed in astconv.
 424         bug!(
 425             "No associated type `{}` for {}",
 426             tcx.item_name(assoc_def_id),
 427             tcx.def_path_str(impl_def_id)
 428         )
 429     }
 430 }