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::ErrorGuaranteed;
   6 use rustc_hir::def_id::{DefId, DefIdMap};
   7 use rustc_span::symbol::sym;
   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: Option<ErrorGuaranteed>,
  35 }
  36
  37 impl Graph {
  38     pub fn new() -> Graph {
  39         Graph { parent: Default::default(), children: Default::default(), has_errored: None }
  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 /// What kind of overlap check are we doing -- this exists just for testing and feature-gating
  50 /// purposes.
  51 #[derive(Copy, Clone, PartialEq, Eq, Hash, HashStable, Debug, TyEncodable, TyDecodable)]
  52 pub enum OverlapMode {
  53     /// The 1.0 rules (either types fail to unify, or where clauses are not implemented for crate-local types)
  54     Stable,
  55     /// Feature-gated test: Stable, *or* there is an explicit negative impl that rules out one of the where-clauses.
  56     WithNegative,
  57     /// Just check for negative impls, not for "where clause not implemented": used for testing.
  58     Strict,
  59 }
  60
  61 impl OverlapMode {
  62     pub fn get<'tcx>(tcx: TyCtxt<'tcx>, trait_id: DefId) -> OverlapMode {
  63         let with_negative_coherence = tcx.features().with_negative_coherence;
  64         let strict_coherence = tcx.has_attr(trait_id, sym::rustc_strict_coherence);
  65
  66         if with_negative_coherence {
  67             if strict_coherence { OverlapMode::Strict } else { OverlapMode::WithNegative }
  68         } else if strict_coherence {
  69             bug!("To use strict_coherence you need to set with_negative_coherence feature flag");
  70         } else {
  71             OverlapMode::Stable
  72         }
  73     }
  74
  75     pub fn use_negative_impl(&self) -> bool {
  76         *self == OverlapMode::Strict || *self == OverlapMode::WithNegative
  77     }
  78
  79     pub fn use_implicit_negative(&self) -> bool {
  80         *self == OverlapMode::Stable || *self == OverlapMode::WithNegative
  81     }
  82 }
  83
  84 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  85 /// done in `TraitDef`.
  86 #[derive(Default, TyEncodable, TyDecodable, Debug, HashStable)]
  87 pub struct Children {
  88     // Impls of a trait (or specializations of a given impl). To allow for
  89     // quicker lookup, the impls are indexed by a simplified version of their
  90     // `Self` type: impls with a simplifiable `Self` are stored in
  91     // `non_blanket_impls` keyed by it, while all other impls are stored in
  92     // `blanket_impls`.
  93     //
  94     // A similar division is used within `TraitDef`, but the lists there collect
  95     // together *all* the impls for a trait, and are populated prior to building
  96     // the specialization graph.
  97     /// Impls of the trait.
  98     pub non_blanket_impls: FxIndexMap<SimplifiedType, Vec<DefId>>,
  99
 100     /// Blanket impls associated with the trait.
 101     pub blanket_impls: Vec<DefId>,
 102 }
 103
 104 /// A node in the specialization graph is either an impl or a trait
 105 /// definition; either can serve as a source of item definitions.
 106 /// There is always exactly one trait definition node: the root.
 107 #[derive(Debug, Copy, Clone)]
 108 pub enum Node {
 109     Impl(DefId),
 110     Trait(DefId),
 111 }
 112
 113 impl Node {
 114     pub fn is_from_trait(&self) -> bool {
 115         matches!(self, Node::Trait(..))
 116     }
 117
 118     /// Trys to find the associated item that implements `trait_item_def_id`
 119     /// defined in this node.
 120     ///
 121     /// If this returns `None`, the item can potentially still be found in
 122     /// parents of this node.
 123     pub fn item<'tcx>(
 124         &self,
 125         tcx: TyCtxt<'tcx>,
 126         trait_item_def_id: DefId,
 127     ) -> Option<&'tcx ty::AssocItem> {
 128         match *self {
 129             Node::Trait(_) => Some(tcx.associated_item(trait_item_def_id)),
 130             Node::Impl(impl_def_id) => {
 131                 let id = tcx.impl_item_implementor_ids(impl_def_id).get(&trait_item_def_id)?;
 132                 Some(tcx.associated_item(*id))
 133             }
 134         }
 135     }
 136
 137     pub fn def_id(&self) -> DefId {
 138         match *self {
 139             Node::Impl(did) => did,
 140             Node::Trait(did) => did,
 141         }
 142     }
 143 }
 144
 145 #[derive(Copy, Clone)]
 146 pub struct Ancestors<'tcx> {
 147     trait_def_id: DefId,
 148     specialization_graph: &'tcx Graph,
 149     current_source: Option<Node>,
 150 }
 151
 152 impl Iterator for Ancestors<'_> {
 153     type Item = Node;
 154     fn next(&mut self) -> Option<Node> {
 155         let cur = self.current_source.take();
 156         if let Some(Node::Impl(cur_impl)) = cur {
 157             let parent = self.specialization_graph.parent(cur_impl);
 158
 159             self.current_source = if parent == self.trait_def_id {
 160                 Some(Node::Trait(parent))
 161             } else {
 162                 Some(Node::Impl(parent))
 163             };
 164         }
 165         cur
 166     }
 167 }
 168
 169 /// Information about the most specialized definition of an associated item.
 170 pub struct LeafDef {
 171     /// The associated item described by this `LeafDef`.
 172     pub item: ty::AssocItem,
 173
 174     /// The node in the specialization graph containing the definition of `item`.
 175     pub defining_node: Node,
 176
 177     /// The "top-most" (ie. least specialized) specialization graph node that finalized the
 178     /// definition of `item`.
 179     ///
 180     /// Example:
 181     ///
 182     /// ```
 183     /// #![feature(specialization)]
 184     /// trait Tr {
 185     ///     fn assoc(&self);
 186     /// }
 187     ///
 188     /// impl<T> Tr for T {
 189     ///     default fn assoc(&self) {}
 190     /// }
 191     ///
 192     /// impl Tr for u8 {}
 193     /// ```
 194     ///
 195     /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the
 196     /// `finalizing_node`, while `defining_node` will be the generic impl.
 197     ///
 198     /// If the leaf definition search is started at the generic impl, `finalizing_node` will be
 199     /// `None`, since the most specialized impl we found still allows overriding the method
 200     /// (doesn't finalize it).
 201     pub finalizing_node: Option<Node>,
 202 }
 203
 204 impl LeafDef {
 205     /// Returns whether this definition is known to not be further specializable.
 206     pub fn is_final(&self) -> bool {
 207         self.finalizing_node.is_some()
 208     }
 209 }
 210
 211 impl<'tcx> Ancestors<'tcx> {
 212     /// Finds the bottom-most (ie. most specialized) definition of an associated
 213     /// item.
 214     pub fn leaf_def(mut self, tcx: TyCtxt<'tcx>, trait_item_def_id: DefId) -> Option<LeafDef> {
 215         let mut finalizing_node = None;
 216
 217         self.find_map(|node| {
 218             if let Some(item) = node.item(tcx, trait_item_def_id) {
 219                 if finalizing_node.is_none() {
 220                     let is_specializable = item.defaultness.is_default()
 221                         || tcx.impl_defaultness(node.def_id()).is_default();
 222
 223                     if !is_specializable {
 224                         finalizing_node = Some(node);
 225                     }
 226                 }
 227
 228                 Some(LeafDef { item: *item, defining_node: node, finalizing_node })
 229             } else {
 230                 // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
 231                 finalizing_node = Some(node);
 232                 None
 233             }
 234         })
 235     }
 236 }
 237
 238 /// Walk up the specialization ancestors of a given impl, starting with that
 239 /// impl itself.
 240 ///
 241 /// Returns `Err` if an error was reported while building the specialization
 242 /// graph.
 243 pub fn ancestors<'tcx>(
 244     tcx: TyCtxt<'tcx>,
 245     trait_def_id: DefId,
 246     start_from_impl: DefId,
 247 ) -> Result<Ancestors<'tcx>, ErrorGuaranteed> {
 248     let specialization_graph = tcx.specialization_graph_of(trait_def_id);
 249
 250     if let Some(reported) = specialization_graph.has_errored {
 251         Err(reported)
 252     } else if let Some(reported) = tcx.type_of(start_from_impl).error_reported() {
 253         Err(reported)
 254     } else {
 255         Ok(Ancestors {
 256             trait_def_id,
 257             specialization_graph,
 258             current_source: Some(Node::Impl(start_from_impl)),
 259         })
 260     }
 261 }