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

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