src/librustc/traits/specialize/specialization_graph.rs

   1 use super::OverlapError;
   2
   3 use crate::hir::def_id::DefId;
   4 use crate::ich::{self, StableHashingContext};
   5 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
   6                                            StableHasherResult};
   7 use crate::traits;
   8 use crate::ty::{self, TyCtxt, TypeFoldable};
   9 use crate::ty::fast_reject::{self, SimplifiedType};
  10 use syntax::ast::Ident;
  11 use crate::util::captures::Captures;
  12 use crate::util::nodemap::{DefIdMap, FxHashMap};
  13
  14 /// A per-trait graph of impls in specialization order. At the moment, this
  15 /// graph forms a tree rooted with the trait itself, with all other nodes
  16 /// representing impls, and parent-child relationships representing
  17 /// specializations.
  18 ///
  19 /// The graph provides two key services:
  20 ///
  21 /// - Construction. This implicitly checks for overlapping impls (i.e., impls
  22 ///   that overlap but where neither specializes the other -- an artifact of the
  23 ///   simple "chain" rule.
  24 ///
  25 /// - Parent extraction. In particular, the graph can give you the *immediate*
  26 ///   parents of a given specializing impl, which is needed for extracting
  27 ///   default items amongst other things. In the simple "chain" rule, every impl
  28 ///   has at most one parent.
  29 #[derive(RustcEncodable, RustcDecodable)]
  30 pub struct Graph {
  31     // All impls have a parent; the "root" impls have as their parent the `def_id`
  32     // of the trait.
  33     parent: DefIdMap<DefId>,
  34
  35     // The "root" impls are found by looking up the trait's def_id.
  36     children: DefIdMap<Children>,
  37 }
  38
  39 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  40 /// done in `TraitDef`.
  41 #[derive(Default, RustcEncodable, RustcDecodable)]
  42 struct Children {
  43     // Impls of a trait (or specializations of a given impl). To allow for
  44     // quicker lookup, the impls are indexed by a simplified version of their
  45     // `Self` type: impls with a simplifiable `Self` are stored in
  46     // `nonblanket_impls` keyed by it, while all other impls are stored in
  47     // `blanket_impls`.
  48     //
  49     // A similar division is used within `TraitDef`, but the lists there collect
  50     // together *all* the impls for a trait, and are populated prior to building
  51     // the specialization graph.
  52
  53     /// Impls of the trait.
  54     nonblanket_impls: FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>,
  55
  56     /// Blanket impls associated with the trait.
  57     blanket_impls: Vec<DefId>,
  58 }
  59
  60 #[derive(Copy, Clone, Debug)]
  61 pub enum FutureCompatOverlapErrorKind {
  62     Issue43355,
  63     Issue33140,
  64 }
  65
  66 #[derive(Debug)]
  67 pub struct FutureCompatOverlapError {
  68     pub error: OverlapError,
  69     pub kind: FutureCompatOverlapErrorKind
  70 }
  71
  72 /// The result of attempting to insert an impl into a group of children.
  73 enum Inserted {
  74     /// The impl was inserted as a new child in this group of children.
  75     BecameNewSibling(Option<FutureCompatOverlapError>),
  76
  77     /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc.
  78     ReplaceChildren(Vec<DefId>),
  79
  80     /// The impl is a specialization of an existing child.
  81     ShouldRecurseOn(DefId),
  82 }
  83
  84 impl<'gcx, 'tcx> Children {
  85     /// Insert an impl into this set of children without comparing to any existing impls.
  86     fn insert_blindly(&mut self, tcx: TyCtxt<'gcx, 'tcx>, impl_def_id: DefId) {
  87         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
  88         if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) {
  89             debug!("insert_blindly: impl_def_id={:?} sty={:?}", impl_def_id, sty);
  90             self.nonblanket_impls.entry(sty).or_default().push(impl_def_id)
  91         } else {
  92             debug!("insert_blindly: impl_def_id={:?} sty=None", impl_def_id);
  93             self.blanket_impls.push(impl_def_id)
  94         }
  95     }
  96
  97     /// Removes an impl from this set of children. Used when replacing
  98     /// an impl with a parent. The impl must be present in the list of
  99     /// children already.
 100     fn remove_existing(&mut self, tcx: TyCtxt<'gcx, 'tcx>, impl_def_id: DefId) {
 101         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
 102         let vec: &mut Vec<DefId>;
 103         if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) {
 104             debug!("remove_existing: impl_def_id={:?} sty={:?}", impl_def_id, sty);
 105             vec = self.nonblanket_impls.get_mut(&sty).unwrap();
 106         } else {
 107             debug!("remove_existing: impl_def_id={:?} sty=None", impl_def_id);
 108             vec = &mut self.blanket_impls;
 109         }
 110
 111         let index = vec.iter().position(|d| *d == impl_def_id).unwrap();
 112         vec.remove(index);
 113     }
 114
 115     /// Attempt to insert an impl into this set of children, while comparing for
 116     /// specialization relationships.
 117     fn insert(
 118         &mut self,
 119         tcx: TyCtxt<'gcx, 'tcx>,
 120         impl_def_id: DefId,
 121         simplified_self: Option<SimplifiedType>,
 122     ) -> Result<Inserted, OverlapError> {
 123         let mut last_lint = None;
 124         let mut replace_children = Vec::new();
 125
 126         debug!(
 127             "insert(impl_def_id={:?}, simplified_self={:?})",
 128             impl_def_id,
 129             simplified_self,
 130         );
 131
 132         let possible_siblings = match simplified_self {
 133             Some(sty) => PotentialSiblings::Filtered(self.filtered(sty)),
 134             None => PotentialSiblings::Unfiltered(self.iter()),
 135         };
 136
 137         for possible_sibling in possible_siblings {
 138             debug!(
 139                 "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}",
 140                 impl_def_id,
 141                 simplified_self,
 142                 possible_sibling,
 143             );
 144
 145             let overlap_error = |overlap: traits::coherence::OverlapResult<'_>| {
 146                 // Found overlap, but no specialization; error out.
 147                 let trait_ref = overlap.impl_header.trait_ref.unwrap();
 148                 let self_ty = trait_ref.self_ty();
 149                 OverlapError {
 150                     with_impl: possible_sibling,
 151                     trait_desc: trait_ref.to_string(),
 152                     // Only report the `Self` type if it has at least
 153                     // some outer concrete shell; otherwise, it's
 154                     // not adding much information.
 155                     self_desc: if self_ty.has_concrete_skeleton() {
 156                         Some(self_ty.to_string())
 157                     } else {
 158                         None
 159                     },
 160                     intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
 161                     involves_placeholder: overlap.involves_placeholder,
 162                 }
 163             };
 164
 165             let tcx = tcx.global_tcx();
 166             let (le, ge) = traits::overlapping_impls(
 167                 tcx,
 168                 possible_sibling,
 169                 impl_def_id,
 170                 traits::IntercrateMode::Issue43355,
 171                 |overlap| {
 172                     if let Some(overlap_kind) =
 173                         tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling)
 174                     {
 175                         match overlap_kind {
 176                             ty::ImplOverlapKind::Permitted => {}
 177                             ty::ImplOverlapKind::Issue33140 => {
 178                                 last_lint = Some(FutureCompatOverlapError {
 179                                     error: overlap_error(overlap),
 180                                     kind: FutureCompatOverlapErrorKind::Issue33140
 181                                 });
 182                             }
 183                         }
 184
 185                         return Ok((false, false));
 186                     }
 187
 188                     let le = tcx.specializes((impl_def_id, possible_sibling));
 189                     let ge = tcx.specializes((possible_sibling, impl_def_id));
 190
 191                     if le == ge {
 192                         Err(overlap_error(overlap))
 193                     } else {
 194                         Ok((le, ge))
 195                     }
 196                 },
 197                 || Ok((false, false)),
 198             )?;
 199
 200             if le && !ge {
 201                 debug!("descending as child of TraitRef {:?}",
 202                        tcx.impl_trait_ref(possible_sibling).unwrap());
 203
 204                 // The impl specializes `possible_sibling`.
 205                 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
 206             } else if ge && !le {
 207                 debug!("placing as parent of TraitRef {:?}",
 208                        tcx.impl_trait_ref(possible_sibling).unwrap());
 209
 210                 replace_children.push(possible_sibling);
 211             } else {
 212                 if let None = tcx.impls_are_allowed_to_overlap(
 213                     impl_def_id, possible_sibling)
 214                 {
 215                     // do future-compat checks for overlap. Have issue #33140
 216                     // errors overwrite issue #43355 errors when both are present.
 217
 218                     traits::overlapping_impls(
 219                         tcx,
 220                         possible_sibling,
 221                         impl_def_id,
 222                         traits::IntercrateMode::Fixed,
 223                         |overlap| {
 224                             last_lint = Some(FutureCompatOverlapError {
 225                                 error: overlap_error(overlap),
 226                                 kind: FutureCompatOverlapErrorKind::Issue43355
 227                             });
 228                         },
 229                         || (),
 230                     );
 231                 }
 232
 233                 // no overlap (error bailed already via ?)
 234             }
 235         }
 236
 237         if !replace_children.is_empty() {
 238             return Ok(Inserted::ReplaceChildren(replace_children));
 239         }
 240
 241         // No overlap with any potential siblings, so add as a new sibling.
 242         debug!("placing as new sibling");
 243         self.insert_blindly(tcx, impl_def_id);
 244         Ok(Inserted::BecameNewSibling(last_lint))
 245     }
 246
 247     fn iter(&mut self) -> impl Iterator<Item = DefId> + '_ {
 248         let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter());
 249         self.blanket_impls.iter().chain(nonblanket).cloned()
 250     }
 251
 252     fn filtered(&mut self, sty: SimplifiedType) -> impl Iterator<Item = DefId> + '_ {
 253         let nonblanket = self.nonblanket_impls.entry(sty).or_default().iter();
 254         self.blanket_impls.iter().chain(nonblanket).cloned()
 255     }
 256 }
 257
 258 // A custom iterator used by Children::insert
 259 enum PotentialSiblings<I, J>
 260     where I: Iterator<Item = DefId>,
 261           J: Iterator<Item = DefId>
 262 {
 263     Unfiltered(I),
 264     Filtered(J)
 265 }
 266
 267 impl<I, J> Iterator for PotentialSiblings<I, J>
 268     where I: Iterator<Item = DefId>,
 269           J: Iterator<Item = DefId>
 270 {
 271     type Item = DefId;
 272
 273     fn next(&mut self) -> Option<Self::Item> {
 274         match *self {
 275             PotentialSiblings::Unfiltered(ref mut iter) => iter.next(),
 276             PotentialSiblings::Filtered(ref mut iter) => iter.next()
 277         }
 278     }
 279 }
 280
 281 impl<'gcx, 'tcx> Graph {
 282     pub fn new() -> Graph {
 283         Graph {
 284             parent: Default::default(),
 285             children: Default::default(),
 286         }
 287     }
 288
 289     /// Insert a local impl into the specialization graph. If an existing impl
 290     /// conflicts with it (has overlap, but neither specializes the other),
 291     /// information about the area of overlap is returned in the `Err`.
 292     pub fn insert(
 293         &mut self,
 294         tcx: TyCtxt<'gcx, 'tcx>,
 295         impl_def_id: DefId,
 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!("insert({:?}): inserting TraitRef {:?} into specialization graph",
 303                impl_def_id, trait_ref);
 304
 305         // If the reference itself contains an earlier error (e.g., due to a
 306         // resolution failure), then we just insert the impl at the top level of
 307         // the graph and claim that there's no overlap (in order to suppress
 308         // bogus errors).
 309         if trait_ref.references_error() {
 310             debug!("insert: inserting dummy node for erroneous TraitRef {:?}, \
 311                     impl_def_id={:?}, trait_def_id={:?}",
 312                    trait_ref, impl_def_id, trait_def_id);
 313
 314             self.parent.insert(impl_def_id, trait_def_id);
 315             self.children.entry(trait_def_id).or_default()
 316                 .insert_blindly(tcx, impl_def_id);
 317             return Ok(None);
 318         }
 319
 320         let mut parent = trait_def_id;
 321         let mut last_lint = None;
 322         let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
 323
 324         // Descend the specialization tree, where `parent` is the current parent node.
 325         loop {
 326             use self::Inserted::*;
 327
 328             let insert_result = self.children.entry(parent).or_default()
 329                 .insert(tcx, impl_def_id, simplified)?;
 330
 331             match insert_result {
 332                 BecameNewSibling(opt_lint) => {
 333                     last_lint = opt_lint;
 334                     break;
 335                 }
 336                 ReplaceChildren(grand_children_to_be) => {
 337                     // We currently have
 338                     //
 339                     //     P
 340                     //     |
 341                     //     G
 342                     //
 343                     // and we are inserting the impl N. We want to make it:
 344                     //
 345                     //     P
 346                     //     |
 347                     //     N
 348                     //     |
 349                     //     G
 350
 351                     // Adjust P's list of children: remove G and then add N.
 352                     {
 353                         let siblings = self.children
 354                             .get_mut(&parent)
 355                             .unwrap();
 356                         for &grand_child_to_be in &grand_children_to_be {
 357                             siblings.remove_existing(tcx, grand_child_to_be);
 358                         }
 359                         siblings.insert_blindly(tcx, impl_def_id);
 360                     }
 361
 362                     // Set G's parent to N and N's parent to P.
 363                     for &grand_child_to_be in &grand_children_to_be {
 364                         self.parent.insert(grand_child_to_be, impl_def_id);
 365                     }
 366                     self.parent.insert(impl_def_id, parent);
 367
 368                     // Add G as N's child.
 369                     for &grand_child_to_be in &grand_children_to_be {
 370                         self.children.entry(impl_def_id).or_default()
 371                             .insert_blindly(tcx, grand_child_to_be);
 372                     }
 373                     break;
 374                 }
 375                 ShouldRecurseOn(new_parent) => {
 376                     parent = new_parent;
 377                 }
 378             }
 379         }
 380
 381         self.parent.insert(impl_def_id, parent);
 382         Ok(last_lint)
 383     }
 384
 385     /// Insert cached metadata mapping from a child impl back to its parent.
 386     pub fn record_impl_from_cstore(
 387         &mut self,
 388         tcx: TyCtxt<'gcx, 'tcx>,
 389         parent: DefId,
 390         child: DefId,
 391     ) {
 392         if self.parent.insert(child, parent).is_some() {
 393             bug!("When recording an impl from the crate store, information about its parent \
 394                   was already present.");
 395         }
 396
 397         self.children.entry(parent).or_default().insert_blindly(tcx, child);
 398     }
 399
 400     /// The parent of a given impl, which is the `DefId` of the trait when the
 401     /// impl is a "specialization root".
 402     pub fn parent(&self, child: DefId) -> DefId {
 403         *self.parent.get(&child).unwrap()
 404     }
 405 }
 406
 407 /// A node in the specialization graph is either an impl or a trait
 408 /// definition; either can serve as a source of item definitions.
 409 /// There is always exactly one trait definition node: the root.
 410 #[derive(Debug, Copy, Clone)]
 411 pub enum Node {
 412     Impl(DefId),
 413     Trait(DefId),
 414 }
 415
 416 impl<'gcx, 'tcx> Node {
 417     pub fn is_from_trait(&self) -> bool {
 418         match *self {
 419             Node::Trait(..) => true,
 420             _ => false,
 421         }
 422     }
 423
 424     /// Iterate over the items defined directly by the given (impl or trait) node.
 425     pub fn items(&self, tcx: TyCtxt<'gcx, 'tcx>) -> ty::AssocItemsIterator<'gcx, 'tcx> {
 426         tcx.associated_items(self.def_id())
 427     }
 428
 429     pub fn def_id(&self) -> DefId {
 430         match *self {
 431             Node::Impl(did) => did,
 432             Node::Trait(did) => did,
 433         }
 434     }
 435 }
 436
 437 pub struct Ancestors<'tcx> {
 438     trait_def_id: DefId,
 439     specialization_graph: &'tcx Graph,
 440     current_source: Option<Node>,
 441 }
 442
 443 impl Iterator for Ancestors<'_> {
 444     type Item = Node;
 445     fn next(&mut self) -> Option<Node> {
 446         let cur = self.current_source.take();
 447         if let Some(Node::Impl(cur_impl)) = cur {
 448             let parent = self.specialization_graph.parent(cur_impl);
 449
 450             self.current_source = if parent == self.trait_def_id {
 451                 Some(Node::Trait(parent))
 452             } else {
 453                 Some(Node::Impl(parent))
 454             };
 455         }
 456         cur
 457     }
 458 }
 459
 460 pub struct NodeItem<T> {
 461     pub node: Node,
 462     pub item: T,
 463 }
 464
 465 impl<T> NodeItem<T> {
 466     pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
 467         NodeItem {
 468             node: self.node,
 469             item: f(self.item),
 470         }
 471     }
 472 }
 473
 474 impl<'gcx, 'tcx> Ancestors<'gcx> {
 475     /// Search the items from the given ancestors, returning each definition
 476     /// with the given name and the given kind.
 477     // FIXME(#35870): avoid closures being unexported due to `impl Trait`.
 478     #[inline]
 479     pub fn defs(
 480         self,
 481         tcx: TyCtxt<'gcx, 'tcx>,
 482         trait_item_name: Ident,
 483         trait_item_kind: ty::AssocKind,
 484         trait_def_id: DefId,
 485     ) -> impl Iterator<Item = NodeItem<ty::AssocItem>> + Captures<'gcx> + 'tcx {
 486         self.flat_map(move |node| {
 487             use crate::ty::AssocKind::*;
 488             node.items(tcx).filter(move |impl_item| match (trait_item_kind, impl_item.kind) {
 489                 | (Const, Const)
 490                 | (Method, Method)
 491                 | (Type, Type)
 492                 | (Type, Existential)
 493                 => tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id),
 494
 495                 | (Const, _)
 496                 | (Method, _)
 497                 | (Type, _)
 498                 | (Existential, _)
 499                 => false,
 500             }).map(move |item| NodeItem { node: node, item: item })
 501         })
 502     }
 503 }
 504
 505 /// Walk up the specialization ancestors of a given impl, starting with that
 506 /// impl itself.
 507 pub fn ancestors(
 508     tcx: TyCtxt<'tcx, '_>,
 509     trait_def_id: DefId,
 510     start_from_impl: DefId,
 511 ) -> Ancestors<'tcx> {
 512     let specialization_graph = tcx.specialization_graph_of(trait_def_id);
 513     Ancestors {
 514         trait_def_id,
 515         specialization_graph,
 516         current_source: Some(Node::Impl(start_from_impl)),
 517     }
 518 }
 519
 520 impl<'a> HashStable<StableHashingContext<'a>> for Children {
 521     fn hash_stable<W: StableHasherResult>(&self,
 522                                           hcx: &mut StableHashingContext<'a>,
 523                                           hasher: &mut StableHasher<W>) {
 524         let Children {
 525             ref nonblanket_impls,
 526             ref blanket_impls,
 527         } = *self;
 528
 529         ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, nonblanket_impls);
 530     }
 531 }
 532
 533 impl_stable_hash_for!(struct self::Graph {
 534     parent,
 535     children
 536 });