src/librustc/traits/specialize/specialization_graph.rs

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