src/librustc/traits/specialize/specialization_graph.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use super::OverlapError;
  12
  13 use hir::def_id::DefId;
  14 use ich::{self, StableHashingContext};
  15 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
  16                                            StableHasherResult};
  17 use traits;
  18 use ty::{self, TyCtxt, TypeFoldable};
  19 use ty::fast_reject::{self, SimplifiedType};
  20 use rustc_data_structures::sync::Lrc;
  21 use syntax::ast::Name;
  22 use util::captures::Captures;
  23 use util::nodemap::{DefIdMap, FxHashMap};
  24
  25 /// A per-trait graph of impls in specialization order. At the moment, this
  26 /// graph forms a tree rooted with the trait itself, with all other nodes
  27 /// representing impls, and parent-child relationships representing
  28 /// specializations.
  29 ///
  30 /// The graph provides two key services:
  31 ///
  32 /// - Construction, which implicitly checks for overlapping impls (i.e., impls
  33 ///   that overlap but where neither specializes the other -- an artifact of the
  34 ///   simple "chain" rule.
  35 ///
  36 /// - Parent extraction. In particular, the graph can give you the *immediate*
  37 ///   parents of a given specializing impl, which is needed for extracting
  38 ///   default items amongst other things. In the simple "chain" rule, every impl
  39 ///   has at most one parent.
  40 #[derive(RustcEncodable, RustcDecodable)]
  41 pub struct Graph {
  42     // all impls have a parent; the "root" impls have as their parent the def_id
  43     // of the trait
  44     parent: DefIdMap<DefId>,
  45
  46     // the "root" impls are found by looking up the trait's def_id.
  47     children: DefIdMap<Children>,
  48 }
  49
  50 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  51 /// done in `TraitDef`.
  52 #[derive(RustcEncodable, RustcDecodable)]
  53 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
  64     /// Impls of the trait.
  65     nonblanket_impls: FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>,
  66
  67     /// Blanket impls associated with the trait.
  68     blanket_impls: Vec<DefId>,
  69 }
  70
  71 /// The result of attempting to insert an impl into a group of children.
  72 enum Inserted {
  73     /// The impl was inserted as a new child in this group of children.
  74     BecameNewSibling(Option<OverlapError>),
  75
  76     /// The impl replaced an existing impl that specializes it.
  77     Replaced(DefId),
  78
  79     /// The impl is a specialization of an existing child.
  80     ShouldRecurseOn(DefId),
  81 }
  82
  83 impl<'a, 'gcx, 'tcx> Children {
  84     fn new() -> Children {
  85         Children {
  86             nonblanket_impls: FxHashMap(),
  87             blanket_impls: vec![],
  88         }
  89     }
  90
  91     /// Insert an impl into this set of children without comparing to any existing impls
  92     fn insert_blindly(&mut self,
  93                       tcx: TyCtxt<'a, 'gcx, 'tcx>,
  94                       impl_def_id: DefId) {
  95         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
  96         if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) {
  97             self.nonblanket_impls.entry(sty).or_insert(vec![]).push(impl_def_id)
  98         } else {
  99             self.blanket_impls.push(impl_def_id)
 100         }
 101     }
 102
 103     /// Attempt to insert an impl into this set of children, while comparing for
 104     /// specialization relationships.
 105     fn insert(&mut self,
 106               tcx: TyCtxt<'a, 'gcx, 'tcx>,
 107               impl_def_id: DefId,
 108               simplified_self: Option<SimplifiedType>)
 109               -> Result<Inserted, OverlapError>
 110     {
 111         let mut last_lint = None;
 112
 113         for slot in match simplified_self {
 114             Some(sty) => self.filtered_mut(sty),
 115             None => self.iter_mut(),
 116         } {
 117             let possible_sibling = *slot;
 118
 119             let overlap_error = |overlap: traits::coherence::OverlapResult| {
 120                 // overlap, but no specialization; error out
 121                 let trait_ref = overlap.impl_header.trait_ref.unwrap();
 122                 let self_ty = trait_ref.self_ty();
 123                 OverlapError {
 124                     with_impl: possible_sibling,
 125                     trait_desc: trait_ref.to_string(),
 126                     // only report the Self type if it has at least
 127                     // some outer concrete shell; otherwise, it's
 128                     // not adding much information.
 129                     self_desc: if self_ty.has_concrete_skeleton() {
 130                         Some(self_ty.to_string())
 131                     } else {
 132                         None
 133                     },
 134                     intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
 135                 }
 136             };
 137
 138             let tcx = tcx.global_tcx();
 139             let (le, ge) = traits::overlapping_impls(
 140                 tcx,
 141                 possible_sibling,
 142                 impl_def_id,
 143                 traits::IntercrateMode::Issue43355,
 144                 |overlap| {
 145                     if tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
 146                         return Ok((false, false));
 147                     }
 148
 149                     let le = tcx.specializes((impl_def_id, possible_sibling));
 150                     let ge = tcx.specializes((possible_sibling, impl_def_id));
 151
 152                     if le == ge {
 153                         Err(overlap_error(overlap))
 154                     } else {
 155                         Ok((le, ge))
 156                     }
 157                 },
 158                 || Ok((false, false)),
 159             )?;
 160
 161             if le && !ge {
 162                 debug!("descending as child of TraitRef {:?}",
 163                        tcx.impl_trait_ref(possible_sibling).unwrap());
 164
 165                 // the impl specializes possible_sibling
 166                 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
 167             } else if ge && !le {
 168                 debug!("placing as parent of TraitRef {:?}",
 169                        tcx.impl_trait_ref(possible_sibling).unwrap());
 170
 171                     // possible_sibling specializes the impl
 172                     *slot = impl_def_id;
 173                 return Ok(Inserted::Replaced(possible_sibling));
 174             } else {
 175                 if !tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
 176                     traits::overlapping_impls(
 177                         tcx,
 178                         possible_sibling,
 179                         impl_def_id,
 180                         traits::IntercrateMode::Fixed,
 181                         |overlap| last_lint = Some(overlap_error(overlap)),
 182                         || (),
 183                     );
 184                 }
 185
 186                 // no overlap (error bailed already via ?)
 187             }
 188         }
 189
 190         // no overlap with any potential siblings, so add as a new sibling
 191         debug!("placing as new sibling");
 192         self.insert_blindly(tcx, impl_def_id);
 193         Ok(Inserted::BecameNewSibling(last_lint))
 194     }
 195
 196     fn iter_mut(&'a mut self) -> Box<dyn Iterator<Item = &'a mut DefId> + 'a> {
 197         let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter_mut());
 198         Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
 199     }
 200
 201     fn filtered_mut(&'a mut self, sty: SimplifiedType)
 202                     -> Box<dyn Iterator<Item = &'a mut DefId> + 'a> {
 203         let nonblanket = self.nonblanket_impls.entry(sty).or_insert(vec![]).iter_mut();
 204         Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
 205     }
 206 }
 207
 208 impl<'a, 'gcx, 'tcx> Graph {
 209     pub fn new() -> Graph {
 210         Graph {
 211             parent: Default::default(),
 212             children: Default::default(),
 213         }
 214     }
 215
 216     /// Insert a local impl into the specialization graph. If an existing impl
 217     /// conflicts with it (has overlap, but neither specializes the other),
 218     /// information about the area of overlap is returned in the `Err`.
 219     pub fn insert(&mut self,
 220                   tcx: TyCtxt<'a, 'gcx, 'tcx>,
 221                   impl_def_id: DefId)
 222                   -> Result<Option<OverlapError>, OverlapError> {
 223         assert!(impl_def_id.is_local());
 224
 225         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
 226         let trait_def_id = trait_ref.def_id;
 227
 228         debug!("insert({:?}): inserting TraitRef {:?} into specialization graph",
 229                impl_def_id, trait_ref);
 230
 231         // if the reference itself contains an earlier error (e.g., due to a
 232         // resolution failure), then we just insert the impl at the top level of
 233         // the graph and claim that there's no overlap (in order to suppress
 234         // bogus errors).
 235         if trait_ref.references_error() {
 236             debug!("insert: inserting dummy node for erroneous TraitRef {:?}, \
 237                     impl_def_id={:?}, trait_def_id={:?}",
 238                    trait_ref, impl_def_id, trait_def_id);
 239
 240             self.parent.insert(impl_def_id, trait_def_id);
 241             self.children.entry(trait_def_id).or_insert(Children::new())
 242                 .insert_blindly(tcx, impl_def_id);
 243             return Ok(None);
 244         }
 245
 246         let mut parent = trait_def_id;
 247         let mut last_lint = None;
 248         let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
 249
 250         // Descend the specialization tree, where `parent` is the current parent node
 251         loop {
 252             use self::Inserted::*;
 253
 254             let insert_result = self.children.entry(parent).or_insert(Children::new())
 255                 .insert(tcx, impl_def_id, simplified)?;
 256
 257             match insert_result {
 258                 BecameNewSibling(opt_lint) => {
 259                     last_lint = opt_lint;
 260                     break;
 261                 }
 262                 Replaced(new_child) => {
 263                     self.parent.insert(new_child, impl_def_id);
 264                     let mut new_children = Children::new();
 265                     new_children.insert_blindly(tcx, new_child);
 266                     self.children.insert(impl_def_id, new_children);
 267                     break;
 268                 }
 269                 ShouldRecurseOn(new_parent) => {
 270                     parent = new_parent;
 271                 }
 272             }
 273         }
 274
 275         self.parent.insert(impl_def_id, parent);
 276         Ok(last_lint)
 277     }
 278
 279     /// Insert cached metadata mapping from a child impl back to its parent.
 280     pub fn record_impl_from_cstore(&mut self,
 281                                    tcx: TyCtxt<'a, 'gcx, 'tcx>,
 282                                    parent: DefId,
 283                                    child: DefId) {
 284         if self.parent.insert(child, parent).is_some() {
 285             bug!("When recording an impl from the crate store, information about its parent \
 286                   was already present.");
 287         }
 288
 289         self.children.entry(parent).or_insert(Children::new()).insert_blindly(tcx, child);
 290     }
 291
 292     /// The parent of a given impl, which is the def id of the trait when the
 293     /// impl is a "specialization root".
 294     pub fn parent(&self, child: DefId) -> DefId {
 295         *self.parent.get(&child).unwrap()
 296     }
 297 }
 298
 299 /// A node in the specialization graph is either an impl or a trait
 300 /// definition; either can serve as a source of item definitions.
 301 /// There is always exactly one trait definition node: the root.
 302 #[derive(Debug, Copy, Clone)]
 303 pub enum Node {
 304     Impl(DefId),
 305     Trait(DefId),
 306 }
 307
 308 impl<'a, 'gcx, 'tcx> Node {
 309     pub fn is_from_trait(&self) -> bool {
 310         match *self {
 311             Node::Trait(..) => true,
 312             _ => false,
 313         }
 314     }
 315
 316     /// Iterate over the items defined directly by the given (impl or trait) node.
 317     pub fn items(
 318         &self,
 319         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 320     ) -> impl Iterator<Item = ty::AssociatedItem> + 'a {
 321         tcx.associated_items(self.def_id())
 322     }
 323
 324     pub fn def_id(&self) -> DefId {
 325         match *self {
 326             Node::Impl(did) => did,
 327             Node::Trait(did) => did,
 328         }
 329     }
 330 }
 331
 332 pub struct Ancestors {
 333     trait_def_id: DefId,
 334     specialization_graph: Lrc<Graph>,
 335     current_source: Option<Node>,
 336 }
 337
 338 impl Iterator for Ancestors {
 339     type Item = Node;
 340     fn next(&mut self) -> Option<Node> {
 341         let cur = self.current_source.take();
 342         if let Some(Node::Impl(cur_impl)) = cur {
 343             let parent = self.specialization_graph.parent(cur_impl);
 344             if parent == self.trait_def_id {
 345                 self.current_source = Some(Node::Trait(parent));
 346             } else {
 347                 self.current_source = Some(Node::Impl(parent));
 348             }
 349         }
 350         cur
 351     }
 352 }
 353
 354 pub struct NodeItem<T> {
 355     pub node: Node,
 356     pub item: T,
 357 }
 358
 359 impl<T> NodeItem<T> {
 360     pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
 361         NodeItem {
 362             node: self.node,
 363             item: f(self.item),
 364         }
 365     }
 366 }
 367
 368 impl<'a, 'gcx, 'tcx> Ancestors {
 369     /// Search the items from the given ancestors, returning each definition
 370     /// with the given name and the given kind.
 371     #[inline] // FIXME(#35870) Avoid closures being unexported due to impl Trait.
 372     pub fn defs(
 373         self,
 374         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 375         trait_item_name: Name,
 376         trait_item_kind: ty::AssociatedKind,
 377         trait_def_id: DefId,
 378     ) -> impl Iterator<Item = NodeItem<ty::AssociatedItem>> + Captures<'gcx> + Captures<'tcx> + 'a {
 379         self.flat_map(move |node| {
 380             node.items(tcx).filter(move |impl_item| {
 381                 impl_item.kind == trait_item_kind &&
 382                 tcx.hygienic_eq(impl_item.name, trait_item_name, trait_def_id)
 383             }).map(move |item| NodeItem { node: node, item: item })
 384         })
 385     }
 386 }
 387
 388 /// Walk up the specialization ancestors of a given impl, starting with that
 389 /// impl itself.
 390 pub fn ancestors(tcx: TyCtxt,
 391                  trait_def_id: DefId,
 392                  start_from_impl: DefId)
 393                  -> Ancestors {
 394     let specialization_graph = tcx.specialization_graph_of(trait_def_id);
 395     Ancestors {
 396         trait_def_id,
 397         specialization_graph,
 398         current_source: Some(Node::Impl(start_from_impl)),
 399     }
 400 }
 401
 402 impl<'a> HashStable<StableHashingContext<'a>> for Children {
 403     fn hash_stable<W: StableHasherResult>(&self,
 404                                           hcx: &mut StableHashingContext<'a>,
 405                                           hasher: &mut StableHasher<W>) {
 406         let Children {
 407             ref nonblanket_impls,
 408             ref blanket_impls,
 409         } = *self;
 410
 411         ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, nonblanket_impls);
 412     }
 413 }
 414
 415 impl_stable_hash_for!(struct self::Graph {
 416     parent,
 417     children
 418 });