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