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