src/librustc_infer/traits/specialize/specialization_graph.rs

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