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 std::cell;
  12 use std::rc::Rc;
  13
  14 use super::{Overlap, specializes};
  15
  16 use middle::cstore::CrateStore;
  17 use hir::def_id::DefId;
  18 use infer;
  19 use traits::{self, ProjectionMode};
  20 use ty::{self, TyCtxt, ImplOrTraitItem, TraitDef, TypeFoldable};
  21 use ty::fast_reject::{self, SimplifiedType};
  22 use syntax::ast::Name;
  23 use util::nodemap::{DefIdMap, FnvHashMap};
  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 thigns. In the simple "chain" rule, every impl
  39 ///   has at most one parent.
  40 pub struct Graph {
  41     // all impls have a parent; the "root" impls have as their parent the def_id
  42     // of the trait
  43     parent: DefIdMap<DefId>,
  44
  45     // the "root" impls are found by looking up the trait's def_id.
  46     children: DefIdMap<Children>,
  47 }
  48
  49 /// Children of a given impl, grouped into blanket/non-blanket varieties as is
  50 /// done in `TraitDef`.
  51 struct Children {
  52     // Impls of a trait (or specializations of a given impl). To allow for
  53     // quicker lookup, the impls are indexed by a simplified version of their
  54     // `Self` type: impls with a simplifiable `Self` are stored in
  55     // `nonblanket_impls` keyed by it, while all other impls are stored in
  56     // `blanket_impls`.
  57     //
  58     // A similar division is used within `TraitDef`, but the lists there collect
  59     // together *all* the impls for a trait, and are populated prior to building
  60     // the specialization graph.
  61
  62     /// Impls of the trait.
  63     nonblanket_impls: FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>,
  64
  65     /// Blanket impls associated with the trait.
  66     blanket_impls: Vec<DefId>,
  67 }
  68
  69 /// The result of attempting to insert an impl into a group of children.
  70 enum InsertResult<'a, 'tcx: 'a> {
  71     /// The impl was inserted as a new child in this group of children.
  72     BecameNewSibling,
  73
  74     /// The impl replaced an existing impl that specializes it.
  75     Replaced(DefId),
  76
  77     /// The impl is a specialization of an existing child.
  78     ShouldRecurseOn(DefId),
  79
  80     /// The impl has an unresolvable overlap with an existing child (neither
  81     /// specializes the other).
  82     Overlapped(Overlap<'a, 'tcx>),
  83 }
  84
  85 impl Children {
  86     fn new() -> Children {
  87         Children {
  88             nonblanket_impls: FnvHashMap(),
  89             blanket_impls: vec![],
  90         }
  91     }
  92
  93     /// Insert an impl into this set of children without comparing to any existing impls
  94     fn insert_blindly(&mut self, tcx: &TyCtxt, 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     /// specialiation relationships.
 105     fn insert<'a, 'tcx>(&mut self,
 106                         tcx: &'a TyCtxt<'tcx>,
 107                         impl_def_id: DefId,
 108                         simplified_self: Option<SimplifiedType>)
 109                         -> InsertResult<'a, 'tcx>
 110     {
 111         for slot in match simplified_self {
 112             Some(sty) => self.filtered_mut(sty),
 113             None => self.iter_mut(),
 114         } {
 115             let possible_sibling = *slot;
 116
 117             let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, ProjectionMode::Topmost);
 118             let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id);
 119
 120             if let Some(impl_header) = overlap {
 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                     debug!("descending as child of TraitRef {:?}",
 126                            tcx.impl_trait_ref(possible_sibling).unwrap());
 127
 128                     // the impl specializes possible_sibling
 129                     return InsertResult::ShouldRecurseOn(possible_sibling);
 130                 } else if ge && !le {
 131                     debug!("placing as parent of TraitRef {:?}",
 132                            tcx.impl_trait_ref(possible_sibling).unwrap());
 133
 134                     // possible_sibling specializes the impl
 135                     *slot = impl_def_id;
 136                     return InsertResult::Replaced(possible_sibling);
 137                 } else {
 138                     // overlap, but no specialization; error out
 139                     return InsertResult::Overlapped(Overlap {
 140                         with_impl: possible_sibling,
 141                         on_trait_ref: impl_header.trait_ref.unwrap(),
 142                         in_context: infcx,
 143                     });
 144                 }
 145             }
 146         }
 147
 148         // no overlap with any potential siblings, so add as a new sibling
 149         debug!("placing as new sibling");
 150         self.insert_blindly(tcx, impl_def_id);
 151         InsertResult::BecameNewSibling
 152     }
 153
 154     fn iter_mut<'a>(&'a mut self) -> Box<Iterator<Item = &'a mut DefId> + 'a> {
 155         let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter_mut());
 156         Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
 157     }
 158
 159     fn filtered_mut<'a>(&'a mut self, sty: SimplifiedType)
 160                         -> Box<Iterator<Item = &'a mut DefId> + 'a> {
 161         let nonblanket = self.nonblanket_impls.entry(sty).or_insert(vec![]).iter_mut();
 162         Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
 163     }
 164 }
 165
 166 impl Graph {
 167     pub fn new() -> Graph {
 168         Graph {
 169             parent: Default::default(),
 170             children: Default::default(),
 171         }
 172     }
 173
 174     /// Insert a local impl into the specialization graph. If an existing impl
 175     /// conflicts with it (has overlap, but neither specializes the other),
 176     /// information about the area of overlap is returned in the `Err`.
 177     pub fn insert<'a, 'tcx>(&mut self,
 178                             tcx: &'a TyCtxt<'tcx>,
 179                             impl_def_id: DefId)
 180                             -> Result<(), Overlap<'a, 'tcx>> {
 181         assert!(impl_def_id.is_local());
 182
 183         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
 184         let trait_def_id = trait_ref.def_id;
 185
 186         debug!("insert({:?}): inserting TraitRef {:?} into specialization graph",
 187                impl_def_id, trait_ref);
 188
 189         // if the reference itself contains an earlier error (e.g., due to a
 190         // resolution failure), then we just insert the impl at the top level of
 191         // the graph and claim that there's no overlap (in order to supress
 192         // bogus errors).
 193         if trait_ref.references_error() {
 194             debug!("insert: inserting dummy node for erroneous TraitRef {:?}, \
 195                     impl_def_id={:?}, trait_def_id={:?}",
 196                    trait_ref, impl_def_id, trait_def_id);
 197
 198             self.parent.insert(impl_def_id, trait_def_id);
 199             self.children.entry(trait_def_id).or_insert(Children::new())
 200                 .insert_blindly(tcx, impl_def_id);
 201             return Ok(());
 202         }
 203
 204         let mut parent = trait_def_id;
 205         let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
 206
 207         // Descend the specialization tree, where `parent` is the current parent node
 208         loop {
 209             use self::InsertResult::*;
 210
 211             let insert_result = self.children.entry(parent).or_insert(Children::new())
 212                 .insert(tcx, impl_def_id, simplified);
 213
 214             match insert_result {
 215                 BecameNewSibling => {
 216                     break;
 217                 }
 218                 Replaced(new_child) => {
 219                     self.parent.insert(new_child, impl_def_id);
 220                     let mut new_children = Children::new();
 221                     new_children.insert_blindly(tcx, new_child);
 222                     self.children.insert(impl_def_id, new_children);
 223                     break;
 224                 }
 225                 ShouldRecurseOn(new_parent) => {
 226                     parent = new_parent;
 227                 }
 228                 Overlapped(error) => {
 229                     return Err(error);
 230                 }
 231             }
 232         }
 233
 234         self.parent.insert(impl_def_id, parent);
 235         Ok(())
 236     }
 237
 238     /// Insert cached metadata mapping from a child impl back to its parent.
 239     pub fn record_impl_from_cstore(&mut self, tcx: &TyCtxt, parent: DefId, child: DefId) {
 240         if self.parent.insert(child, parent).is_some() {
 241             bug!("When recording an impl from the crate store, information about its parent \
 242                   was already present.");
 243         }
 244
 245         self.children.entry(parent).or_insert(Children::new()).insert_blindly(tcx, child);
 246     }
 247
 248     /// The parent of a given impl, which is the def id of the trait when the
 249     /// impl is a "specialization root".
 250     pub fn parent(&self, child: DefId) -> DefId {
 251         *self.parent.get(&child).unwrap()
 252     }
 253 }
 254
 255 /// A node in the specialization graph is either an impl or a trait
 256 /// definition; either can serve as a source of item definitions.
 257 /// There is always exactly one trait definition node: the root.
 258 #[derive(Debug, Copy, Clone)]
 259 pub enum Node {
 260     Impl(DefId),
 261     Trait(DefId),
 262 }
 263
 264 impl Node {
 265     pub fn is_from_trait(&self) -> bool {
 266         match *self {
 267             Node::Trait(..) => true,
 268             _ => false,
 269         }
 270     }
 271
 272     /// Iterate over the items defined directly by the given (impl or trait) node.
 273     pub fn items<'a, 'tcx>(&self, tcx: &'a TyCtxt<'tcx>) -> NodeItems<'a, 'tcx> {
 274         match *self {
 275             Node::Impl(impl_def_id) => {
 276                 NodeItems::Impl {
 277                     tcx: tcx,
 278                     items: cell::Ref::map(tcx.impl_items.borrow(),
 279                                           |impl_items| &impl_items[&impl_def_id]),
 280                     idx: 0,
 281                 }
 282             }
 283             Node::Trait(trait_def_id) => {
 284                 NodeItems::Trait {
 285                     items: tcx.trait_items(trait_def_id).clone(),
 286                     idx: 0,
 287                 }
 288             }
 289         }
 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 /// An iterator over the items defined within a trait or impl.
 301 pub enum NodeItems<'a, 'tcx: 'a> {
 302     Impl {
 303         tcx: &'a TyCtxt<'tcx>,
 304         items: cell::Ref<'a, Vec<ty::ImplOrTraitItemId>>,
 305         idx: usize,
 306     },
 307     Trait {
 308         items: Rc<Vec<ImplOrTraitItem<'tcx>>>,
 309         idx: usize,
 310     },
 311 }
 312
 313 impl<'a, 'tcx> Iterator for NodeItems<'a, 'tcx> {
 314     type Item = ImplOrTraitItem<'tcx>;
 315     fn next(&mut self) -> Option<ImplOrTraitItem<'tcx>> {
 316         match *self {
 317             NodeItems::Impl { tcx, ref items, ref mut idx } => {
 318                 let items_table = tcx.impl_or_trait_items.borrow();
 319                 if *idx < items.len() {
 320                     let item_def_id = items[*idx].def_id();
 321                     let item = items_table[&item_def_id].clone();
 322                     *idx += 1;
 323                     Some(item)
 324                 } else {
 325                     None
 326                 }
 327             }
 328             NodeItems::Trait { ref items, ref mut idx } => {
 329                 if *idx < items.len() {
 330                     let item = items[*idx].clone();
 331                     *idx += 1;
 332                     Some(item)
 333                 } else {
 334                     None
 335                 }
 336             }
 337         }
 338     }
 339 }
 340
 341 pub struct Ancestors<'a, 'tcx: 'a> {
 342     trait_def: &'a TraitDef<'tcx>,
 343     current_source: Option<Node>,
 344 }
 345
 346 impl<'a, 'tcx> Iterator for Ancestors<'a, 'tcx> {
 347     type Item = Node;
 348     fn next(&mut self) -> Option<Node> {
 349         let cur = self.current_source.take();
 350         if let Some(Node::Impl(cur_impl)) = cur {
 351             let parent = self.trait_def.specialization_graph.borrow().parent(cur_impl);
 352             if parent == self.trait_def.def_id() {
 353                 self.current_source = Some(Node::Trait(parent));
 354             } else {
 355                 self.current_source = Some(Node::Impl(parent));
 356             }
 357         }
 358         cur
 359     }
 360 }
 361
 362 pub struct NodeItem<T> {
 363     pub node: Node,
 364     pub item: T,
 365 }
 366
 367 impl<T> NodeItem<T> {
 368     pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
 369         NodeItem {
 370             node: self.node,
 371             item: f(self.item),
 372         }
 373     }
 374 }
 375
 376 pub struct TypeDefs<'a, 'tcx: 'a> {
 377     // generally only invoked once or twice, so the box doesn't hurt
 378     iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>> + 'a>,
 379 }
 380
 381 impl<'a, 'tcx> Iterator for TypeDefs<'a, 'tcx> {
 382     type Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>;
 383     fn next(&mut self) -> Option<Self::Item> {
 384         self.iter.next()
 385     }
 386 }
 387
 388 pub struct FnDefs<'a, 'tcx: 'a> {
 389     // generally only invoked once or twice, so the box doesn't hurt
 390     iter: Box<Iterator<Item = NodeItem<Rc<ty::Method<'tcx>>>> + 'a>,
 391 }
 392
 393 impl<'a, 'tcx> Iterator for FnDefs<'a, 'tcx> {
 394     type Item = NodeItem<Rc<ty::Method<'tcx>>>;
 395     fn next(&mut self) -> Option<Self::Item> {
 396         self.iter.next()
 397     }
 398 }
 399
 400 pub struct ConstDefs<'a, 'tcx: 'a> {
 401     // generally only invoked once or twice, so the box doesn't hurt
 402     iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>> + 'a>,
 403 }
 404
 405 impl<'a, 'tcx> Iterator for ConstDefs<'a, 'tcx> {
 406     type Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>;
 407     fn next(&mut self) -> Option<Self::Item> {
 408         self.iter.next()
 409     }
 410 }
 411
 412 impl<'a, 'tcx> Ancestors<'a, 'tcx> {
 413     /// Search the items from the given ancestors, returning each type definition
 414     /// with the given name.
 415     pub fn type_defs(self, tcx: &'a TyCtxt<'tcx>, name: Name) -> TypeDefs<'a, 'tcx> {
 416         let iter = self.flat_map(move |node| {
 417             node.items(tcx)
 418                 .filter_map(move |item| {
 419                     if let ty::TypeTraitItem(assoc_ty) = item {
 420                         if assoc_ty.name == name {
 421                             return Some(NodeItem {
 422                                 node: node,
 423                                 item: assoc_ty,
 424                             });
 425                         }
 426                     }
 427                     None
 428                 })
 429
 430         });
 431         TypeDefs { iter: Box::new(iter) }
 432     }
 433
 434     /// Search the items from the given ancestors, returning each fn definition
 435     /// with the given name.
 436     pub fn fn_defs(self, tcx: &'a TyCtxt<'tcx>, name: Name) -> FnDefs<'a, 'tcx> {
 437         let iter = self.flat_map(move |node| {
 438             node.items(tcx)
 439                 .filter_map(move |item| {
 440                     if let ty::MethodTraitItem(method) = item {
 441                         if method.name == name {
 442                             return Some(NodeItem {
 443                                 node: node,
 444                                 item: method,
 445                             });
 446                         }
 447                     }
 448                     None
 449                 })
 450
 451         });
 452         FnDefs { iter: Box::new(iter) }
 453     }
 454
 455     /// Search the items from the given ancestors, returning each const
 456     /// definition with the given name.
 457     pub fn const_defs(self, tcx: &'a TyCtxt<'tcx>, name: Name) -> ConstDefs<'a, 'tcx> {
 458         let iter = self.flat_map(move |node| {
 459             node.items(tcx)
 460                 .filter_map(move |item| {
 461                     if let ty::ConstTraitItem(konst) = item {
 462                         if konst.name == name {
 463                             return Some(NodeItem {
 464                                 node: node,
 465                                 item: konst,
 466                             });
 467                         }
 468                     }
 469                     None
 470                 })
 471
 472         });
 473         ConstDefs { iter: Box::new(iter) }
 474     }
 475 }
 476
 477 /// Walk up the specialization ancestors of a given impl, starting with that
 478 /// impl itself.
 479 pub fn ancestors<'a, 'tcx>(trait_def: &'a TraitDef<'tcx>,
 480                            start_from_impl: DefId)
 481                            -> Ancestors<'a, 'tcx> {
 482     Ancestors {
 483         trait_def: trait_def,
 484         current_source: Some(Node::Impl(start_from_impl)),
 485     }
 486 }