src/librustc_middle/traits/specialization_graph.rs

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