src/librustc/middle/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 middle::def_id::DefId;
  18 use middle::infer;
  19 use middle::traits;
  20 use middle::ty::{self, ImplOrTraitItem, TraitDef, TypeFoldable};
  21 use syntax::ast::Name;
  22 use util::nodemap::DefIdMap;
  23
  24 /// A per-trait graph of impls in specialization order. At the moment, this
  25 /// graph forms a tree rooted with the trait itself, with all other nodes
  26 /// representing impls, and parent-child relationships representing
  27 /// specializations.
  28 ///
  29 /// The graph provides two key services:
  30 ///
  31 /// - Construction, which implicitly checks for overlapping impls (i.e., impls
  32 ///   that overlap but where neither specializes the other -- an artifact of the
  33 ///   simple "chain" rule.
  34 ///
  35 /// - Parent extraction. In particular, the graph can give you the *immediate*
  36 ///   parents of a given specializing impl, which is needed for extracting
  37 ///   default items amongst other thigns. In the simple "chain" rule, every impl
  38 ///   has at most one parent.
  39 pub struct Graph {
  40     // all impls have a parent; the "root" impls have as their parent the def_id
  41     // of the trait
  42     parent: DefIdMap<DefId>,
  43
  44     // the "root" impls are found by looking up the trait's def_id.
  45     children: DefIdMap<Vec<DefId>>,
  46 }
  47
  48 impl Graph {
  49     pub fn new() -> Graph {
  50         Graph {
  51             parent: Default::default(),
  52             children: Default::default(),
  53         }
  54     }
  55
  56     /// Insert a local impl into the specialization graph. If an existing impl
  57     /// conflicts with it (has overlap, but neither specializes the other),
  58     /// information about the area of overlap is returned in the `Err`.
  59     pub fn insert<'a, 'tcx>(&mut self,
  60                             tcx: &'a ty::ctxt<'tcx>,
  61                             impl_def_id: DefId)
  62                             -> Result<(), Overlap<'a, 'tcx>> {
  63         assert!(impl_def_id.is_local());
  64
  65         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
  66         let trait_def_id = trait_ref.def_id;
  67
  68         // if the reference itself contains an earlier error (e.g., due to a
  69         // resolution failure), then we just insert the impl at the top level of
  70         // the graph and claim that there's no overlap (in order to supress
  71         // bogus errors).
  72         if trait_ref.references_error() {
  73             debug!("Inserting dummy node for erroneous TraitRef {:?}, \
  74                     impl_def_id={:?}, trait_def_id={:?}",
  75                    trait_ref, impl_def_id, trait_def_id);
  76
  77             self.parent.insert(impl_def_id, trait_def_id);
  78             self.children.entry(trait_def_id).or_insert(vec![]).push(impl_def_id);
  79             return Ok(());
  80         }
  81
  82         let mut parent = trait_def_id;
  83
  84         // Ugly hack around borrowck limitations. Assigned only in the case
  85         // where we bump downward an existing node in the graph.
  86         let child_to_insert;
  87
  88         'descend: loop {
  89             let mut possible_siblings = self.children.entry(parent).or_insert(vec![]);
  90
  91             for slot in possible_siblings.iter_mut() {
  92                 let possible_sibling = *slot;
  93
  94                 let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None);
  95                 let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id);
  96
  97                 if let Some(trait_ref) = overlap {
  98                     let le = specializes(tcx, impl_def_id, possible_sibling);
  99                     let ge = specializes(tcx, possible_sibling, impl_def_id);
 100
 101                     if le && !ge {
 102                         // the impl specializes possible_sibling
 103                         parent = possible_sibling;
 104                         continue 'descend;
 105                     } else if ge && !le {
 106                         // possible_sibling specializes the impl
 107                         *slot = impl_def_id;
 108                         self.parent.insert(impl_def_id, parent);
 109                         self.parent.insert(possible_sibling, impl_def_id);
 110                         // we have to defer the insertion, because we can't
 111                         // relinquish the borrow of `self.children`
 112                         child_to_insert = possible_sibling;
 113                         break 'descend;
 114                     } else {
 115                         // overlap, but no specialization; error out
 116                         return Err(Overlap {
 117                             with_impl: possible_sibling,
 118                             on_trait_ref: trait_ref,
 119                             in_context: infcx,
 120                         });
 121                     }
 122                 }
 123             }
 124
 125             // no overlap with any potential siblings, so add as a new sibling
 126             self.parent.insert(impl_def_id, parent);
 127             possible_siblings.push(impl_def_id);
 128             return Ok(());
 129         }
 130
 131         self.children.insert(impl_def_id, vec![child_to_insert]);
 132         Ok(())
 133     }
 134
 135     /// Insert cached metadata mapping from a child impl back to its parent.
 136     pub fn record_impl_from_cstore(&mut self, parent: DefId, child: DefId) {
 137         if self.parent.insert(child, parent).is_some() {
 138             panic!("When recording an impl from the crate store, information about its parent \
 139                     was already present.");
 140         }
 141
 142         self.children.entry(parent).or_insert(vec![]).push(child);
 143     }
 144
 145     /// The parent of a given impl, which is the def id of the trait when the
 146     /// impl is a "specialization root".
 147     pub fn parent(&self, child: DefId) -> DefId {
 148         *self.parent.get(&child).unwrap()
 149     }
 150 }
 151
 152 #[derive(Debug, Copy, Clone)]
 153 /// A node in the specialization graph is either an impl or a trait
 154 /// definition; either can serve as a source of item definitions.
 155 /// There is always exactly one trait definition node: the root.
 156 pub enum Node {
 157     Impl(DefId),
 158     Trait(DefId),
 159 }
 160
 161 impl Node {
 162     pub fn is_from_trait(&self) -> bool {
 163         match *self {
 164             Node::Trait(..) => true,
 165             _ => false,
 166         }
 167     }
 168
 169     /// Iterate over the items defined directly by the given (impl or trait) node.
 170     pub fn items<'a, 'tcx>(&self, tcx: &'a ty::ctxt<'tcx>) -> NodeItems<'a, 'tcx> {
 171         match *self {
 172             Node::Impl(impl_def_id) => {
 173                 NodeItems::Impl {
 174                     tcx: tcx,
 175                     items: cell::Ref::map(tcx.impl_items.borrow(),
 176                                           |impl_items| &impl_items[&impl_def_id]),
 177                     idx: 0,
 178                 }
 179             }
 180             Node::Trait(trait_def_id) => {
 181                 NodeItems::Trait {
 182                     items: tcx.trait_items(trait_def_id).clone(),
 183                     idx: 0,
 184                 }
 185             }
 186         }
 187     }
 188
 189     pub fn def_id(&self) -> DefId {
 190         match *self {
 191             Node::Impl(did) => did,
 192             Node::Trait(did) => did,
 193         }
 194     }
 195 }
 196
 197 /// An iterator over the items defined within a trait or impl.
 198 pub enum NodeItems<'a, 'tcx: 'a> {
 199     Impl {
 200         tcx: &'a ty::ctxt<'tcx>,
 201         items: cell::Ref<'a, Vec<ty::ImplOrTraitItemId>>,
 202         idx: usize,
 203     },
 204     Trait {
 205         items: Rc<Vec<ImplOrTraitItem<'tcx>>>,
 206         idx: usize,
 207     },
 208 }
 209
 210 impl<'a, 'tcx> Iterator for NodeItems<'a, 'tcx> {
 211     type Item = ImplOrTraitItem<'tcx>;
 212     fn next(&mut self) -> Option<ImplOrTraitItem<'tcx>> {
 213         match *self {
 214             NodeItems::Impl { tcx, ref items, ref mut idx } => {
 215                 let items_table = tcx.impl_or_trait_items.borrow();
 216                 if *idx < items.len() {
 217                     let item_def_id = items[*idx].def_id();
 218                     let item = items_table[&item_def_id].clone();
 219                     *idx += 1;
 220                     Some(item)
 221                 } else {
 222                     None
 223                 }
 224             }
 225             NodeItems::Trait { ref items, ref mut idx } => {
 226                 if *idx < items.len() {
 227                     let item = items[*idx].clone();
 228                     *idx += 1;
 229                     Some(item)
 230                 } else {
 231                     None
 232                 }
 233             }
 234         }
 235     }
 236 }
 237
 238 pub struct Ancestors<'a, 'tcx: 'a> {
 239     trait_def: &'a TraitDef<'tcx>,
 240     current_source: Option<Node>,
 241 }
 242
 243 impl<'a, 'tcx> Iterator for Ancestors<'a, 'tcx> {
 244     type Item = Node;
 245     fn next(&mut self) -> Option<Node> {
 246         let cur = self.current_source.take();
 247         if let Some(Node::Impl(cur_impl)) = cur {
 248             let parent = self.trait_def.specialization_graph.borrow().parent(cur_impl);
 249             if parent == self.trait_def.def_id() {
 250                 self.current_source = Some(Node::Trait(parent));
 251             } else {
 252                 self.current_source = Some(Node::Impl(parent));
 253             }
 254         }
 255         cur
 256     }
 257 }
 258
 259 pub struct NodeItem<T> {
 260     pub node: Node,
 261     pub item: T,
 262 }
 263
 264 impl<T> NodeItem<T> {
 265     pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
 266         NodeItem {
 267             node: self.node,
 268             item: f(self.item),
 269         }
 270     }
 271 }
 272
 273 pub struct TypeDefs<'a, 'tcx: 'a> {
 274     // generally only invoked once or twice, so the box doesn't hurt
 275     iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>> + 'a>,
 276 }
 277
 278 impl<'a, 'tcx> Iterator for TypeDefs<'a, 'tcx> {
 279     type Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>;
 280     fn next(&mut self) -> Option<Self::Item> {
 281         self.iter.next()
 282     }
 283 }
 284
 285 pub struct FnDefs<'a, 'tcx: 'a> {
 286     // generally only invoked once or twice, so the box doesn't hurt
 287     iter: Box<Iterator<Item = NodeItem<Rc<ty::Method<'tcx>>>> + 'a>,
 288 }
 289
 290 impl<'a, 'tcx> Iterator for FnDefs<'a, 'tcx> {
 291     type Item = NodeItem<Rc<ty::Method<'tcx>>>;
 292     fn next(&mut self) -> Option<Self::Item> {
 293         self.iter.next()
 294     }
 295 }
 296
 297 pub struct ConstDefs<'a, 'tcx: 'a> {
 298     // generally only invoked once or twice, so the box doesn't hurt
 299     iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>> + 'a>,
 300 }
 301
 302 impl<'a, 'tcx> Iterator for ConstDefs<'a, 'tcx> {
 303     type Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>;
 304     fn next(&mut self) -> Option<Self::Item> {
 305         self.iter.next()
 306     }
 307 }
 308
 309 impl<'a, 'tcx> Ancestors<'a, 'tcx> {
 310     /// Seach the items from the given ancestors, returning each type definition
 311     /// with the given name.
 312     pub fn type_defs(self, tcx: &'a ty::ctxt<'tcx>, name: Name) -> TypeDefs<'a, 'tcx> {
 313         let iter = self.flat_map(move |node| {
 314             node.items(tcx)
 315                 .filter_map(move |item| {
 316                     if let ty::TypeTraitItem(assoc_ty) = item {
 317                         if assoc_ty.name == name {
 318                             return Some(NodeItem {
 319                                 node: node,
 320                                 item: assoc_ty,
 321                             });
 322                         }
 323                     }
 324                     None
 325                 })
 326
 327         });
 328         TypeDefs { iter: Box::new(iter) }
 329     }
 330
 331     /// Seach the items from the given ancestors, returning each fn definition
 332     /// with the given name.
 333     pub fn fn_defs(self, tcx: &'a ty::ctxt<'tcx>, name: Name) -> FnDefs<'a, 'tcx> {
 334         let iter = self.flat_map(move |node| {
 335             node.items(tcx)
 336                 .filter_map(move |item| {
 337                     if let ty::MethodTraitItem(method) = item {
 338                         if method.name == name {
 339                             return Some(NodeItem {
 340                                 node: node,
 341                                 item: method,
 342                             });
 343                         }
 344                     }
 345                     None
 346                 })
 347
 348         });
 349         FnDefs { iter: Box::new(iter) }
 350     }
 351
 352     /// Seach the items from the given ancestors, returning each const
 353     /// definition with the given name.
 354     pub fn const_defs(self, tcx: &'a ty::ctxt<'tcx>, name: Name) -> ConstDefs<'a, 'tcx> {
 355         let iter = self.flat_map(move |node| {
 356             node.items(tcx)
 357                 .filter_map(move |item| {
 358                     if let ty::ConstTraitItem(konst) = item {
 359                         if konst.name == name {
 360                             return Some(NodeItem {
 361                                 node: node,
 362                                 item: konst,
 363                             });
 364                         }
 365                     }
 366                     None
 367                 })
 368
 369         });
 370         ConstDefs { iter: Box::new(iter) }
 371     }
 372 }
 373
 374 /// Walk up the specialization ancestors of a given impl, starting with that
 375 /// impl itself.
 376 pub fn ancestors<'a, 'tcx>(trait_def: &'a TraitDef<'tcx>,
 377                            start_from_impl: DefId)
 378                            -> Ancestors<'a, 'tcx> {
 379     Ancestors {
 380         trait_def: trait_def,
 381         current_source: Some(Node::Impl(start_from_impl)),
 382     }
 383 }