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