compiler/rustc_middle/src/traits/specialization_graph.rs

   1 use crate::ty::fast_reject::SimplifiedType;
   2 use crate::ty::fold::TypeFoldable;
   3 use crate::ty::{self, TyCtxt};
   4 use rustc_data_structures::fx::FxIndexMap;
   5 use rustc_errors::ErrorReported;
   6 use rustc_hir::def_id::{DefId, DefIdMap};
   7 use rustc_span::symbol::Ident;
   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(TyEncodable, TyDecodable, HashStable, Debug)]
  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     /// Whether an error was emitted while constructing the graph.
  34     pub has_errored: bool,
  35 }
  36
  37 impl Graph {
  38     pub fn new() -> Graph {
  39         Graph { parent: Default::default(), children: Default::default(), has_errored: false }
  40     }
  41
  42     /// The parent of a given impl, which is the `DefId` of the trait when the
  43     /// impl is a "specialization root".
  44     pub fn parent(&self, child: DefId) -> DefId {
  45         *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {:?}", child))
  46     }
  47 }
  48
  49 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  50 /// done in `TraitDef`.
  51 #[derive(Default, TyEncodable, TyDecodable, Debug, HashStable)]
  52 pub struct Children {
  53     // Impls of a trait (or specializations of a given impl). To allow for
  54     // quicker lookup, the impls are indexed by a simplified version of their
  55     // `Self` type: impls with a simplifiable `Self` are stored in
  56     // `non_blanket_impls` keyed by it, while all other impls are stored in
  57     // `blanket_impls`.
  58     //
  59     // A similar division is used within `TraitDef`, but the lists there collect
  60     // together *all* the impls for a trait, and are populated prior to building
  61     // the specialization graph.
  62     /// Impls of the trait.
  63     pub non_blanket_impls: FxIndexMap<SimplifiedType, Vec<DefId>>,
  64
  65     /// Blanket impls associated with the trait.
  66     pub blanket_impls: Vec<DefId>,
  67 }
  68
  69 /// A node in the specialization graph is either an impl or a trait
  70 /// definition; either can serve as a source of item definitions.
  71 /// There is always exactly one trait definition node: the root.
  72 #[derive(Debug, Copy, Clone)]
  73 pub enum Node {
  74     Impl(DefId),
  75     Trait(DefId),
  76 }
  77
  78 impl<'tcx> Node {
  79     pub fn is_from_trait(&self) -> bool {
  80         matches!(self, Node::Trait(..))
  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         tcx.associated_items(self.def_id())
 100             .filter_by_name_unhygienic(trait_item_name.name)
 101             .find(move |impl_item| {
 102                 trait_item_kind == impl_item.kind
 103                     && tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id)
 104             })
 105             .copied()
 106     }
 107
 108     pub fn def_id(&self) -> DefId {
 109         match *self {
 110             Node::Impl(did) => did,
 111             Node::Trait(did) => did,
 112         }
 113     }
 114 }
 115
 116 #[derive(Copy, Clone)]
 117 pub struct Ancestors<'tcx> {
 118     trait_def_id: DefId,
 119     specialization_graph: &'tcx Graph,
 120     current_source: Option<Node>,
 121 }
 122
 123 impl Iterator for Ancestors<'_> {
 124     type Item = Node;
 125     fn next(&mut self) -> Option<Node> {
 126         let cur = self.current_source.take();
 127         if let Some(Node::Impl(cur_impl)) = cur {
 128             let parent = self.specialization_graph.parent(cur_impl);
 129
 130             self.current_source = if parent == self.trait_def_id {
 131                 Some(Node::Trait(parent))
 132             } else {
 133                 Some(Node::Impl(parent))
 134             };
 135         }
 136         cur
 137     }
 138 }
 139
 140 /// Information about the most specialized definition of an associated item.
 141 pub struct LeafDef {
 142     /// The associated item described by this `LeafDef`.
 143     pub item: ty::AssocItem,
 144
 145     /// The node in the specialization graph containing the definition of `item`.
 146     pub defining_node: Node,
 147
 148     /// The "top-most" (ie. least specialized) specialization graph node that finalized the
 149     /// definition of `item`.
 150     ///
 151     /// Example:
 152     ///
 153     /// ```
 154     /// trait Tr {
 155     ///     fn assoc(&self);
 156     /// }
 157     ///
 158     /// impl<T> Tr for T {
 159     ///     default fn assoc(&self) {}
 160     /// }
 161     ///
 162     /// impl Tr for u8 {}
 163     /// ```
 164     ///
 165     /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the
 166     /// `finalizing_node`, while `defining_node` will be the generic impl.
 167     ///
 168     /// If the leaf definition search is started at the generic impl, `finalizing_node` will be
 169     /// `None`, since the most specialized impl we found still allows overriding the method
 170     /// (doesn't finalize it).
 171     pub finalizing_node: Option<Node>,
 172 }
 173
 174 impl LeafDef {
 175     /// Returns whether this definition is known to not be further specializable.
 176     pub fn is_final(&self) -> bool {
 177         self.finalizing_node.is_some()
 178     }
 179 }
 180
 181 impl<'tcx> Ancestors<'tcx> {
 182     /// Finds the bottom-most (ie. most specialized) definition of an associated
 183     /// item.
 184     pub fn leaf_def(
 185         mut self,
 186         tcx: TyCtxt<'tcx>,
 187         trait_item_name: Ident,
 188         trait_item_kind: ty::AssocKind,
 189     ) -> Option<LeafDef> {
 190         let trait_def_id = self.trait_def_id;
 191         let mut finalizing_node = None;
 192
 193         self.find_map(|node| {
 194             if let Some(item) = node.item(tcx, trait_item_name, trait_item_kind, trait_def_id) {
 195                 if finalizing_node.is_none() {
 196                     let is_specializable = item.defaultness.is_default()
 197                         || tcx.impl_defaultness(node.def_id()).is_default();
 198
 199                     if !is_specializable {
 200                         finalizing_node = Some(node);
 201                     }
 202                 }
 203
 204                 Some(LeafDef { item, defining_node: node, finalizing_node })
 205             } else {
 206                 // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
 207                 finalizing_node = Some(node);
 208                 None
 209             }
 210         })
 211     }
 212 }
 213
 214 /// Walk up the specialization ancestors of a given impl, starting with that
 215 /// impl itself.
 216 ///
 217 /// Returns `Err` if an error was reported while building the specialization
 218 /// graph.
 219 pub fn ancestors(
 220     tcx: TyCtxt<'tcx>,
 221     trait_def_id: DefId,
 222     start_from_impl: DefId,
 223 ) -> Result<Ancestors<'tcx>, ErrorReported> {
 224     let specialization_graph = tcx.specialization_graph_of(trait_def_id);
 225
 226     if specialization_graph.has_errored || tcx.type_of(start_from_impl).references_error() {
 227         Err(ErrorReported)
 228     } else {
 229         Ok(Ancestors {
 230             trait_def_id,
 231             specialization_graph,
 232             current_source: Some(Node::Impl(start_from_impl)),
 233         })
 234     }
 235 }