src/librustc/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_ast::ast::Ident;
   5 use rustc_data_structures::fx::FxHashMap;
   6 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
   7 use rustc_hir::def_id::{DefId, DefIdMap};
   8
   9 /// A per-trait graph of impls in specialization order. At the moment, this
  10 /// graph forms a tree rooted with the trait itself, with all other nodes
  11 /// representing impls, and parent-child relationships representing
  12 /// specializations.
  13 ///
  14 /// The graph provides two key services:
  15 ///
  16 /// - Construction. This implicitly checks for overlapping impls (i.e., impls
  17 ///   that overlap but where neither specializes the other -- an artifact of the
  18 ///   simple "chain" rule.
  19 ///
  20 /// - Parent extraction. In particular, the graph can give you the *immediate*
  21 ///   parents of a given specializing impl, which is needed for extracting
  22 ///   default items amongst other things. In the simple "chain" rule, every impl
  23 ///   has at most one parent.
  24 #[derive(RustcEncodable, RustcDecodable, HashStable)]
  25 pub struct Graph {
  26     // All impls have a parent; the "root" impls have as their parent the `def_id`
  27     // of the trait.
  28     pub parent: DefIdMap<DefId>,
  29
  30     // The "root" impls are found by looking up the trait's def_id.
  31     pub children: DefIdMap<Children>,
  32 }
  33
  34 impl Graph {
  35     pub fn new() -> Graph {
  36         Graph { parent: Default::default(), children: Default::default() }
  37     }
  38
  39     /// The parent of a given impl, which is the `DefId` of the trait when the
  40     /// impl is a "specialization root".
  41     pub fn parent(&self, child: DefId) -> DefId {
  42         *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {:?}", child))
  43     }
  44 }
  45
  46 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  47 /// done in `TraitDef`.
  48 #[derive(Default, RustcEncodable, RustcDecodable)]
  49 pub struct Children {
  50     // Impls of a trait (or specializations of a given impl). To allow for
  51     // quicker lookup, the impls are indexed by a simplified version of their
  52     // `Self` type: impls with a simplifiable `Self` are stored in
  53     // `nonblanket_impls` keyed by it, while all other impls are stored in
  54     // `blanket_impls`.
  55     //
  56     // A similar division is used within `TraitDef`, but the lists there collect
  57     // together *all* the impls for a trait, and are populated prior to building
  58     // the specialization graph.
  59     /// Impls of the trait.
  60     pub nonblanket_impls: FxHashMap<SimplifiedType, Vec<DefId>>,
  61
  62     /// Blanket impls associated with the trait.
  63     pub blanket_impls: Vec<DefId>,
  64 }
  65
  66 /// A node in the specialization graph is either an impl or a trait
  67 /// definition; either can serve as a source of item definitions.
  68 /// There is always exactly one trait definition node: the root.
  69 #[derive(Debug, Copy, Clone)]
  70 pub enum Node {
  71     Impl(DefId),
  72     Trait(DefId),
  73 }
  74
  75 impl<'tcx> Node {
  76     pub fn is_from_trait(&self) -> bool {
  77         match *self {
  78             Node::Trait(..) => true,
  79             _ => false,
  80         }
  81     }
  82
  83     /// Iterate over the items defined directly by the given (impl or trait) node.
  84     pub fn items(&self, tcx: TyCtxt<'tcx>) -> impl 'tcx + Iterator<Item = &'tcx ty::AssocItem> {
  85         tcx.associated_items(self.def_id()).in_definition_order()
  86     }
  87
  88     /// Finds an associated item defined in this node.
  89     ///
  90     /// If this returns `None`, the item can potentially still be found in
  91     /// parents of this node.
  92     pub fn item(
  93         &self,
  94         tcx: TyCtxt<'tcx>,
  95         trait_item_name: Ident,
  96         trait_item_kind: ty::AssocKind,
  97         trait_def_id: DefId,
  98     ) -> Option<ty::AssocItem> {
  99         use crate::ty::AssocKind::*;
 100
 101         tcx.associated_items(self.def_id())
 102             .filter_by_name_unhygienic(trait_item_name.name)
 103             .find(move |impl_item| {
 104                 match (trait_item_kind, impl_item.kind) {
 105                 | (Const, Const)
 106                 | (Method, Method)
 107                 | (Type, Type)
 108                 | (Type, OpaqueTy)  // assoc. types can be made opaque in impls
 109                 => tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id),
 110
 111                 | (Const, _)
 112                 | (Method, _)
 113                 | (Type, _)
 114                 | (OpaqueTy, _)
 115                 => false,
 116             }
 117             })
 118             .copied()
 119     }
 120
 121     pub fn def_id(&self) -> DefId {
 122         match *self {
 123             Node::Impl(did) => did,
 124             Node::Trait(did) => did,
 125         }
 126     }
 127 }
 128
 129 #[derive(Copy, Clone)]
 130 pub struct Ancestors<'tcx> {
 131     trait_def_id: DefId,
 132     specialization_graph: &'tcx Graph,
 133     current_source: Option<Node>,
 134 }
 135
 136 impl Iterator for Ancestors<'_> {
 137     type Item = Node;
 138     fn next(&mut self) -> Option<Node> {
 139         let cur = self.current_source.take();
 140         if let Some(Node::Impl(cur_impl)) = cur {
 141             let parent = self.specialization_graph.parent(cur_impl);
 142
 143             self.current_source = if parent == self.trait_def_id {
 144                 Some(Node::Trait(parent))
 145             } else {
 146                 Some(Node::Impl(parent))
 147             };
 148         }
 149         cur
 150     }
 151 }
 152
 153 pub struct NodeItem<T> {
 154     pub node: Node,
 155     pub item: T,
 156 }
 157
 158 impl<T> NodeItem<T> {
 159     pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
 160         NodeItem { node: self.node, item: f(self.item) }
 161     }
 162 }
 163
 164 impl<'tcx> Ancestors<'tcx> {
 165     /// Finds the bottom-most (ie. most specialized) definition of an associated
 166     /// item.
 167     pub fn leaf_def(
 168         mut self,
 169         tcx: TyCtxt<'tcx>,
 170         trait_item_name: Ident,
 171         trait_item_kind: ty::AssocKind,
 172     ) -> Option<NodeItem<ty::AssocItem>> {
 173         let trait_def_id = self.trait_def_id;
 174         self.find_map(|node| {
 175             node.item(tcx, trait_item_name, trait_item_kind, trait_def_id)
 176                 .map(|item| NodeItem { node, item })
 177         })
 178     }
 179 }
 180
 181 /// Walk up the specialization ancestors of a given impl, starting with that
 182 /// impl itself.
 183 pub fn ancestors(
 184     tcx: TyCtxt<'tcx>,
 185     trait_def_id: DefId,
 186     start_from_impl: DefId,
 187 ) -> Ancestors<'tcx> {
 188     let specialization_graph = tcx.specialization_graph_of(trait_def_id);
 189     Ancestors {
 190         trait_def_id,
 191         specialization_graph,
 192         current_source: Some(Node::Impl(start_from_impl)),
 193     }
 194 }
 195
 196 impl<'a> HashStable<StableHashingContext<'a>> for Children {
 197     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 198         let Children { ref nonblanket_impls, ref blanket_impls } = *self;
 199
 200         ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, nonblanket_impls);
 201     }
 202 }