compiler/rustc_middle/src/traits/specialization_graph.rs

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