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, specializes};
  12
  13 use hir::def_id::DefId;
  14 use traits::{self, Reveal};
  15 use ty::{self, TyCtxt, TraitDef, TypeFoldable};
  16 use ty::fast_reject::{self, SimplifiedType};
  17 use syntax::ast::Name;
  18 use util::nodemap::{DefIdMap, FxHashMap};
  19
  20 /// A per-trait graph of impls in specialization order. At the moment, this
  21 /// graph forms a tree rooted with the trait itself, with all other nodes
  22 /// representing impls, and parent-child relationships representing
  23 /// specializations.
  24 ///
  25 /// The graph provides two key services:
  26 ///
  27 /// - Construction, which implicitly checks for overlapping impls (i.e., impls
  28 ///   that overlap but where neither specializes the other -- an artifact of the
  29 ///   simple "chain" rule.
  30 ///
  31 /// - Parent extraction. In particular, the graph can give you the *immediate*
  32 ///   parents of a given specializing impl, which is needed for extracting
  33 ///   default items amongst other thigns. In the simple "chain" rule, every impl
  34 ///   has at most one parent.
  35 pub struct Graph {
  36     // all impls have a parent; the "root" impls have as their parent the def_id
  37     // of the trait
  38     parent: DefIdMap<DefId>,
  39
  40     // the "root" impls are found by looking up the trait's def_id.
  41     children: DefIdMap<Children>,
  42 }
  43
  44 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  45 /// done in `TraitDef`.
  46 struct Children {
  47     // Impls of a trait (or specializations of a given impl). To allow for
  48     // quicker lookup, the impls are indexed by a simplified version of their
  49     // `Self` type: impls with a simplifiable `Self` are stored in
  50     // `nonblanket_impls` keyed by it, while all other impls are stored in
  51     // `blanket_impls`.
  52     //
  53     // A similar division is used within `TraitDef`, but the lists there collect
  54     // together *all* the impls for a trait, and are populated prior to building
  55     // the specialization graph.
  56
  57     /// Impls of the trait.
  58     nonblanket_impls: FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>,
  59
  60     /// Blanket impls associated with the trait.
  61     blanket_impls: Vec<DefId>,
  62 }
  63
  64 /// The result of attempting to insert an impl into a group of children.
  65 enum Inserted {
  66     /// The impl was inserted as a new child in this group of children.
  67     BecameNewSibling,
  68
  69     /// The impl replaced an existing impl that specializes it.
  70     Replaced(DefId),
  71
  72     /// The impl is a specialization of an existing child.
  73     ShouldRecurseOn(DefId),
  74 }
  75
  76 impl<'a, 'gcx, 'tcx> Children {
  77     fn new() -> Children {
  78         Children {
  79             nonblanket_impls: FxHashMap(),
  80             blanket_impls: vec![],
  81         }
  82     }
  83
  84     /// Insert an impl into this set of children without comparing to any existing impls
  85     fn insert_blindly(&mut self,
  86                       tcx: TyCtxt<'a, 'gcx, 'tcx>,
  87                       impl_def_id: DefId) {
  88         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
  89         if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) {
  90             self.nonblanket_impls.entry(sty).or_insert(vec![]).push(impl_def_id)
  91         } else {
  92             self.blanket_impls.push(impl_def_id)
  93         }
  94     }
  95
  96     /// Attempt to insert an impl into this set of children, while comparing for
  97     /// specialiation relationships.
  98     fn insert(&mut self,
  99               tcx: TyCtxt<'a, 'gcx, 'tcx>,
 100               impl_def_id: DefId,
 101               simplified_self: Option<SimplifiedType>)
 102               -> Result<Inserted, OverlapError>
 103     {
 104         for slot in match simplified_self {
 105             Some(sty) => self.filtered_mut(sty),
 106             None => self.iter_mut(),
 107         } {
 108             let possible_sibling = *slot;
 109
 110             let tcx = tcx.global_tcx();
 111             let (le, ge) = tcx.infer_ctxt((), Reveal::ExactMatch).enter(|infcx| {
 112                 let overlap = traits::overlapping_impls(&infcx,
 113                                                         possible_sibling,
 114                                                         impl_def_id);
 115                 if let Some(impl_header) = overlap {
 116                     let le = specializes(tcx, impl_def_id, possible_sibling);
 117                     let ge = specializes(tcx, possible_sibling, impl_def_id);
 118
 119                     if le == ge {
 120                         // overlap, but no specialization; error out
 121                         let trait_ref = impl_header.trait_ref.unwrap();
 122                         let self_ty = trait_ref.self_ty();
 123                         Err(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                         })
 135                     } else {
 136                         Ok((le, ge))
 137                     }
 138                 } else {
 139                     Ok((false, false))
 140                 }
 141             })?;
 142
 143             if le && !ge {
 144                 debug!("descending as child of TraitRef {:?}",
 145                        tcx.impl_trait_ref(possible_sibling).unwrap());
 146
 147                 // the impl specializes possible_sibling
 148                 return Ok(Inserted::ShouldRecurseOn(possible_sibling));
 149             } else if ge && !le {
 150                 debug!("placing as parent of TraitRef {:?}",
 151                        tcx.impl_trait_ref(possible_sibling).unwrap());
 152
 153                     // possible_sibling specializes the impl
 154                     *slot = impl_def_id;
 155                 return Ok(Inserted::Replaced(possible_sibling));
 156             } else {
 157                 // no overlap (error bailed already via ?)
 158             }
 159         }
 160
 161         // no overlap with any potential siblings, so add as a new sibling
 162         debug!("placing as new sibling");
 163         self.insert_blindly(tcx, impl_def_id);
 164         Ok(Inserted::BecameNewSibling)
 165     }
 166
 167     fn iter_mut(&'a mut self) -> Box<Iterator<Item = &'a mut DefId> + 'a> {
 168         let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter_mut());
 169         Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
 170     }
 171
 172     fn filtered_mut(&'a mut self, sty: SimplifiedType)
 173                     -> Box<Iterator<Item = &'a mut DefId> + 'a> {
 174         let nonblanket = self.nonblanket_impls.entry(sty).or_insert(vec![]).iter_mut();
 175         Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
 176     }
 177 }
 178
 179 impl<'a, 'gcx, 'tcx> Graph {
 180     pub fn new() -> Graph {
 181         Graph {
 182             parent: Default::default(),
 183             children: Default::default(),
 184         }
 185     }
 186
 187     /// Insert a local impl into the specialization graph. If an existing impl
 188     /// conflicts with it (has overlap, but neither specializes the other),
 189     /// information about the area of overlap is returned in the `Err`.
 190     pub fn insert(&mut self,
 191                   tcx: TyCtxt<'a, 'gcx, 'tcx>,
 192                   impl_def_id: DefId)
 193                   -> Result<(), OverlapError> {
 194         assert!(impl_def_id.is_local());
 195
 196         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
 197         let trait_def_id = trait_ref.def_id;
 198
 199         debug!("insert({:?}): inserting TraitRef {:?} into specialization graph",
 200                impl_def_id, trait_ref);
 201
 202         // if the reference itself contains an earlier error (e.g., due to a
 203         // resolution failure), then we just insert the impl at the top level of
 204         // the graph and claim that there's no overlap (in order to supress
 205         // bogus errors).
 206         if trait_ref.references_error() {
 207             debug!("insert: inserting dummy node for erroneous TraitRef {:?}, \
 208                     impl_def_id={:?}, trait_def_id={:?}",
 209                    trait_ref, impl_def_id, trait_def_id);
 210
 211             self.parent.insert(impl_def_id, trait_def_id);
 212             self.children.entry(trait_def_id).or_insert(Children::new())
 213                 .insert_blindly(tcx, impl_def_id);
 214             return Ok(());
 215         }
 216
 217         let mut parent = trait_def_id;
 218         let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
 219
 220         // Descend the specialization tree, where `parent` is the current parent node
 221         loop {
 222             use self::Inserted::*;
 223
 224             let insert_result = self.children.entry(parent).or_insert(Children::new())
 225                 .insert(tcx, impl_def_id, simplified)?;
 226
 227             match insert_result {
 228                 BecameNewSibling => {
 229                     break;
 230                 }
 231                 Replaced(new_child) => {
 232                     self.parent.insert(new_child, impl_def_id);
 233                     let mut new_children = Children::new();
 234                     new_children.insert_blindly(tcx, new_child);
 235                     self.children.insert(impl_def_id, new_children);
 236                     break;
 237                 }
 238                 ShouldRecurseOn(new_parent) => {
 239                     parent = new_parent;
 240                 }
 241             }
 242         }
 243
 244         self.parent.insert(impl_def_id, parent);
 245         Ok(())
 246     }
 247
 248     /// Insert cached metadata mapping from a child impl back to its parent.
 249     pub fn record_impl_from_cstore(&mut self,
 250                                    tcx: TyCtxt<'a, 'gcx, 'tcx>,
 251                                    parent: DefId,
 252                                    child: DefId) {
 253         if self.parent.insert(child, parent).is_some() {
 254             bug!("When recording an impl from the crate store, information about its parent \
 255                   was already present.");
 256         }
 257
 258         self.children.entry(parent).or_insert(Children::new()).insert_blindly(tcx, child);
 259     }
 260
 261     /// The parent of a given impl, which is the def id of the trait when the
 262     /// impl is a "specialization root".
 263     pub fn parent(&self, child: DefId) -> DefId {
 264         *self.parent.get(&child).unwrap()
 265     }
 266 }
 267
 268 /// A node in the specialization graph is either an impl or a trait
 269 /// definition; either can serve as a source of item definitions.
 270 /// There is always exactly one trait definition node: the root.
 271 #[derive(Debug, Copy, Clone)]
 272 pub enum Node {
 273     Impl(DefId),
 274     Trait(DefId),
 275 }
 276
 277 impl<'a, 'gcx, 'tcx> Node {
 278     pub fn is_from_trait(&self) -> bool {
 279         match *self {
 280             Node::Trait(..) => true,
 281             _ => false,
 282         }
 283     }
 284
 285     /// Iterate over the items defined directly by the given (impl or trait) node.
 286     #[inline] // FIXME(#35870) Avoid closures being unexported due to impl Trait.
 287     pub fn items(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>)
 288                  -> impl Iterator<Item = ty::AssociatedItem> + 'a {
 289         tcx.associated_items(self.def_id())
 290     }
 291
 292     pub fn def_id(&self) -> DefId {
 293         match *self {
 294             Node::Impl(did) => did,
 295             Node::Trait(did) => did,
 296         }
 297     }
 298 }
 299
 300 pub struct Ancestors<'a> {
 301     trait_def: &'a TraitDef,
 302     current_source: Option<Node>,
 303 }
 304
 305 impl<'a> Iterator for Ancestors<'a> {
 306     type Item = Node;
 307     fn next(&mut self) -> Option<Node> {
 308         let cur = self.current_source.take();
 309         if let Some(Node::Impl(cur_impl)) = cur {
 310             let parent = self.trait_def.specialization_graph.borrow().parent(cur_impl);
 311             if parent == self.trait_def.def_id {
 312                 self.current_source = Some(Node::Trait(parent));
 313             } else {
 314                 self.current_source = Some(Node::Impl(parent));
 315             }
 316         }
 317         cur
 318     }
 319 }
 320
 321 pub struct NodeItem<T> {
 322     pub node: Node,
 323     pub item: T,
 324 }
 325
 326 impl<T> NodeItem<T> {
 327     pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
 328         NodeItem {
 329             node: self.node,
 330             item: f(self.item),
 331         }
 332     }
 333 }
 334
 335 impl<'a, 'gcx, 'tcx> Ancestors<'a> {
 336     /// Search the items from the given ancestors, returning each definition
 337     /// with the given name and the given kind.
 338     #[inline] // FIXME(#35870) Avoid closures being unexported due to impl Trait.
 339     pub fn defs(self, tcx: TyCtxt<'a, 'gcx, 'tcx>, name: Name, kind: ty::AssociatedKind)
 340                 -> impl Iterator<Item = NodeItem<ty::AssociatedItem>> + 'a {
 341         self.flat_map(move |node| {
 342             node.items(tcx).filter(move |item| item.kind == kind && item.name == name)
 343                            .map(move |item| NodeItem { node: node, item: item })
 344         })
 345     }
 346 }
 347
 348 /// Walk up the specialization ancestors of a given impl, starting with that
 349 /// impl itself.
 350 pub fn ancestors<'a>(trait_def: &'a TraitDef, start_from_impl: DefId) -> Ancestors<'a> {
 351     Ancestors {
 352         trait_def: trait_def,
 353         current_source: Some(Node::Impl(start_from_impl)),
 354     }
 355 }