src/librustc_middle/traits/specialization_graph.rs

   1 use crate::ich::{self, StableHashingContext};
   2 use crate::ty::fast_reject::SimplifiedType;
   3 use crate::ty::fold::TypeFoldable;
   4 use crate::ty::{self, TyCtxt};
   5 use rustc_data_structures::fx::FxHashMap;
   6 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
   7 use rustc_errors::ErrorReported;
   8 use rustc_hir::def_id::{DefId, DefIdMap};
   9 use rustc_span::symbol::Ident;
  10
  11 /// A per-trait graph of impls in specialization order. At the moment, this
  12 /// graph forms a tree rooted with the trait itself, with all other nodes
  13 /// representing impls, and parent-child relationships representing
  14 /// specializations.
  15 ///
  16 /// The graph provides two key services:
  17 ///
  18 /// - Construction. This implicitly checks for overlapping impls (i.e., impls
  19 ///   that overlap but where neither specializes the other -- an artifact of the
  20 ///   simple "chain" rule.
  21 ///
  22 /// - Parent extraction. In particular, the graph can give you the *immediate*
  23 ///   parents of a given specializing impl, which is needed for extracting
  24 ///   default items amongst other things. In the simple "chain" rule, every impl
  25 ///   has at most one parent.
  26 #[derive(RustcEncodable, RustcDecodable, HashStable)]
  27 pub struct Graph {
  28     /// All impls have a parent; the "root" impls have as their parent the `def_id`
  29     /// of the trait.
  30     pub parent: DefIdMap<DefId>,
  31
  32     /// The "root" impls are found by looking up the trait's def_id.
  33     pub children: DefIdMap<Children>,
  34
  35     /// Whether an error was emitted while constructing the graph.
  36     pub has_errored: bool,
  37 }
  38
  39 impl Graph {
  40     pub fn new() -> Graph {
  41         Graph { parent: Default::default(), children: Default::default(), has_errored: false }
  42     }
  43
  44     /// The parent of a given impl, which is the `DefId` of the trait when the
  45     /// impl is a "specialization root".
  46     pub fn parent(&self, child: DefId) -> DefId {
  47         *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {:?}", child))
  48     }
  49 }
  50
  51 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  52 /// done in `TraitDef`.
  53 #[derive(Default, RustcEncodable, RustcDecodable)]
  54 pub struct Children {
  55     // Impls of a trait (or specializations of a given impl). To allow for
  56     // quicker lookup, the impls are indexed by a simplified version of their
  57     // `Self` type: impls with a simplifiable `Self` are stored in
  58     // `nonblanket_impls` keyed by it, while all other impls are stored in
  59     // `blanket_impls`.
  60     //
  61     // A similar division is used within `TraitDef`, but the lists there collect
  62     // together *all* the impls for a trait, and are populated prior to building
  63     // the specialization graph.
  64     /// Impls of the trait.
  65     pub nonblanket_impls: FxHashMap<SimplifiedType, Vec<DefId>>,
  66
  67     /// Blanket impls associated with the trait.
  68     pub blanket_impls: Vec<DefId>,
  69 }
  70
  71 /// A node in the specialization graph is either an impl or a trait
  72 /// definition; either can serve as a source of item definitions.
  73 /// There is always exactly one trait definition node: the root.
  74 #[derive(Debug, Copy, Clone)]
  75 pub enum Node {
  76     Impl(DefId),
  77     Trait(DefId),
  78 }
  79
  80 impl<'tcx> Node {
  81     pub fn is_from_trait(&self) -> bool {
  82         match *self {
  83             Node::Trait(..) => true,
  84             _ => false,
  85         }
  86     }
  87
  88     /// Iterate over the items defined directly by the given (impl or trait) node.
  89     pub fn items(&self, tcx: TyCtxt<'tcx>) -> impl 'tcx + Iterator<Item = &'tcx ty::AssocItem> {
  90         tcx.associated_items(self.def_id()).in_definition_order()
  91     }
  92
  93     /// Finds an associated item defined in this node.
  94     ///
  95     /// If this returns `None`, the item can potentially still be found in
  96     /// parents of this node.
  97     pub fn item(
  98         &self,
  99         tcx: TyCtxt<'tcx>,
 100         trait_item_name: Ident,
 101         trait_item_kind: ty::AssocKind,
 102         trait_def_id: DefId,
 103     ) -> Option<ty::AssocItem> {
 104         tcx.associated_items(self.def_id())
 105             .filter_by_name_unhygienic(trait_item_name.name)
 106             .find(move |impl_item| {
 107                 trait_item_kind == impl_item.kind
 108                     && tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id)
 109             })
 110             .copied()
 111     }
 112
 113     pub fn def_id(&self) -> DefId {
 114         match *self {
 115             Node::Impl(did) => did,
 116             Node::Trait(did) => did,
 117         }
 118     }
 119 }
 120
 121 #[derive(Copy, Clone)]
 122 pub struct Ancestors<'tcx> {
 123     trait_def_id: DefId,
 124     specialization_graph: &'tcx Graph,
 125     current_source: Option<Node>,
 126 }
 127
 128 impl Iterator for Ancestors<'_> {
 129     type Item = Node;
 130     fn next(&mut self) -> Option<Node> {
 131         let cur = self.current_source.take();
 132         if let Some(Node::Impl(cur_impl)) = cur {
 133             let parent = self.specialization_graph.parent(cur_impl);
 134
 135             self.current_source = if parent == self.trait_def_id {
 136                 Some(Node::Trait(parent))
 137             } else {
 138                 Some(Node::Impl(parent))
 139             };
 140         }
 141         cur
 142     }
 143 }
 144
 145 /// Information about the most specialized definition of an associated item.
 146 pub struct LeafDef {
 147     /// The associated item described by this `LeafDef`.
 148     pub item: ty::AssocItem,
 149
 150     /// The node in the specialization graph containing the definition of `item`.
 151     pub defining_node: Node,
 152
 153     /// The "top-most" (ie. least specialized) specialization graph node that finalized the
 154     /// definition of `item`.
 155     ///
 156     /// Example:
 157     ///
 158     /// ```
 159     /// trait Tr {
 160     ///     fn assoc(&self);
 161     /// }
 162     ///
 163     /// impl<T> Tr for T {
 164     ///     default fn assoc(&self) {}
 165     /// }
 166     ///
 167     /// impl Tr for u8 {}
 168     /// ```
 169     ///
 170     /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the
 171     /// `finalizing_node`, while `defining_node` will be the generic impl.
 172     ///
 173     /// If the leaf definition search is started at the generic impl, `finalizing_node` will be
 174     /// `None`, since the most specialized impl we found still allows overriding the method
 175     /// (doesn't finalize it).
 176     pub finalizing_node: Option<Node>,
 177 }
 178
 179 impl LeafDef {
 180     /// Returns whether this definition is known to not be further specializable.
 181     pub fn is_final(&self) -> bool {
 182         self.finalizing_node.is_some()
 183     }
 184 }
 185
 186 impl<'tcx> Ancestors<'tcx> {
 187     /// Finds the bottom-most (ie. most specialized) definition of an associated
 188     /// item.
 189     pub fn leaf_def(
 190         mut self,
 191         tcx: TyCtxt<'tcx>,
 192         trait_item_name: Ident,
 193         trait_item_kind: ty::AssocKind,
 194     ) -> Option<LeafDef> {
 195         let trait_def_id = self.trait_def_id;
 196         let mut finalizing_node = None;
 197
 198         self.find_map(|node| {
 199             if let Some(item) = node.item(tcx, trait_item_name, trait_item_kind, trait_def_id) {
 200                 if finalizing_node.is_none() {
 201                     let is_specializable = item.defaultness.is_default()
 202                         || tcx.impl_defaultness(node.def_id()).is_default();
 203
 204                     if !is_specializable {
 205                         finalizing_node = Some(node);
 206                     }
 207                 }
 208
 209                 Some(LeafDef { item, defining_node: node, finalizing_node })
 210             } else {
 211                 // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
 212                 finalizing_node = Some(node);
 213                 None
 214             }
 215         })
 216     }
 217 }
 218
 219 /// Walk up the specialization ancestors of a given impl, starting with that
 220 /// impl itself.
 221 ///
 222 /// Returns `Err` if an error was reported while building the specialization
 223 /// graph.
 224 pub fn ancestors(
 225     tcx: TyCtxt<'tcx>,
 226     trait_def_id: DefId,
 227     start_from_impl: DefId,
 228 ) -> Result<Ancestors<'tcx>, ErrorReported> {
 229     let specialization_graph = tcx.specialization_graph_of(trait_def_id);
 230
 231     if specialization_graph.has_errored || tcx.type_of(start_from_impl).references_error() {
 232         Err(ErrorReported)
 233     } else {
 234         Ok(Ancestors {
 235             trait_def_id,
 236             specialization_graph,
 237             current_source: Some(Node::Impl(start_from_impl)),
 238         })
 239     }
 240 }
 241
 242 impl<'a> HashStable<StableHashingContext<'a>> for Children {
 243     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 244         let Children { ref nonblanket_impls, ref blanket_impls } = *self;
 245
 246         ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, nonblanket_impls);
 247     }
 248 }