diff options
| -rw-r--r-- | src/librustc/traits/specialize/mod.rs | 14 | ||||
| -rw-r--r-- | src/librustc/ty/maps.rs | 4 | ||||
| -rw-r--r-- | src/librustc/ty/trait_def.rs | 117 |
3 files changed, 108 insertions, 27 deletions
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs index b3956e813c4..0e5779f9d17 100644 --- a/src/librustc/traits/specialize/mod.rs +++ b/src/librustc/traits/specialize/mod.rs @@ -293,7 +293,19 @@ pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx -> Rc<specialization_graph::Graph> { let mut sg = specialization_graph::Graph::new(); - for &impl_def_id in tcx.trait_impls_of(trait_id).iter() { + let mut trait_impls: Vec<DefId> = tcx.trait_impls_of(trait_id).iter().collect(); + + // The coherence checking implementation seems to rely on impls being + // iterated over (roughly) in definition order, so we are sorting by + // negated CrateNum (so remote definitions are visited first) and then + // by a flattend version of the DefIndex. + trait_impls.sort_unstable_by_key(|def_id| { + (-(def_id.krate.as_u32() as i64), + def_id.index.address_space().index(), + def_id.index.as_array_index()) + }); + + for impl_def_id in trait_impls { if impl_def_id.is_local() { // This is where impl overlap checking happens: let insert_result = sg.insert(tcx, impl_def_id); diff --git a/src/librustc/ty/maps.rs b/src/librustc/ty/maps.rs index 188ef289ba9..0926da2005d 100644 --- a/src/librustc/ty/maps.rs +++ b/src/librustc/ty/maps.rs @@ -850,10 +850,10 @@ define_maps! { <'tcx> [] const_is_rvalue_promotable_to_static: ConstIsRvaluePromotableToStatic(DefId) -> bool, [] is_mir_available: IsMirAvailable(DefId) -> bool, - [] trait_impls_of: TraitImpls(DefId) -> Rc<Vec<DefId>>, + [] trait_impls_of: TraitImpls(DefId) -> ty::trait_def::TraitImpls, // Note that TraitDef::for_each_relevant_impl() will do type simplication for you. [] relevant_trait_impls_for: relevant_trait_impls_for((DefId, SimplifiedType)) - -> Rc<Vec<DefId>>, + -> ty::trait_def::TraitImpls, [] specialization_graph_of: SpecializationGraph(DefId) -> Rc<specialization_graph::Graph>, [] is_object_safe: ObjectSafety(DefId) -> bool, } diff --git a/src/librustc/ty/trait_def.rs b/src/librustc/ty/trait_def.rs index b0357a35b83..eb60f9d1010 100644 --- a/src/librustc/ty/trait_def.rs +++ b/src/librustc/ty/trait_def.rs @@ -35,6 +35,60 @@ pub struct TraitDef { pub def_path_hash: u64, } +// We don't store the list of impls in a flat list because each cached list of +// `relevant_impls_for` we would then duplicate all blanket impls. By keeping +// blanket and non-blanket impls separate, we can share the list of blanket +// impls. +#[derive(Clone)] +pub struct TraitImpls { + blanket_impls: Rc<Vec<DefId>>, + non_blanket_impls: Rc<Vec<DefId>>, +} + +impl TraitImpls { + pub fn iter(&self) -> TraitImplsIter { + TraitImplsIter { + blanket_impls: self.blanket_impls.clone(), + non_blanket_impls: self.non_blanket_impls.clone(), + index: 0 + } + } +} + +#[derive(Clone)] +pub struct TraitImplsIter { + blanket_impls: Rc<Vec<DefId>>, + non_blanket_impls: Rc<Vec<DefId>>, + index: usize, +} + +impl Iterator for TraitImplsIter { + type Item = DefId; + + fn next(&mut self) -> Option<DefId> { + if self.index < self.blanket_impls.len() { + let bi_index = self.index; + self.index += 1; + Some(self.blanket_impls[bi_index]) + } else { + let nbi_index = self.index - self.blanket_impls.len(); + if nbi_index < self.non_blanket_impls.len() { + self.index += 1; + Some(self.non_blanket_impls[nbi_index]) + } else { + None + } + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let items_left = (self.blanket_impls.len() + self.non_blanket_impls.len()) - self.index; + (items_left, Some(items_left)) + } +} + +impl ExactSizeIterator for TraitImplsIter {} + impl<'a, 'gcx, 'tcx> TraitDef { pub fn new(def_id: DefId, unsafety: hir::Unsafety, @@ -58,7 +112,7 @@ impl<'a, 'gcx, 'tcx> TraitDef { } pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, mut f: F) { - for &impl_def_id in tcx.trait_impls_of(self.def_id).iter() { + for impl_def_id in tcx.trait_impls_of(self.def_id).iter() { f(impl_def_id); } } @@ -89,7 +143,7 @@ impl<'a, 'gcx, 'tcx> TraitDef { tcx.trait_impls_of(self.def_id) }; - for &impl_def_id in relevant_impls.iter() { + for impl_def_id in relevant_impls.iter() { f(impl_def_id); } } @@ -98,8 +152,8 @@ impl<'a, 'gcx, 'tcx> TraitDef { // Query provider for `trait_impls_of`. pub(super) fn trait_impls_of_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, trait_id: DefId) - -> Rc<Vec<DefId>> { - let mut impls = if trait_id.is_local() { + -> TraitImpls { + let remote_impls = if trait_id.is_local() { // Traits defined in the current crate can't have impls in upstream // crates, so we don't bother querying the cstore. Vec::new() @@ -107,46 +161,61 @@ pub(super) fn trait_impls_of_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, tcx.sess.cstore.implementations_of_trait(Some(trait_id)) }; - impls.extend(tcx.hir - .trait_impls(trait_id) - .iter() - .map(|&node_id| tcx.hir.local_def_id(node_id)) - .filter(|&impl_def_id| { - let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); - !trait_ref.references_error() - })); - Rc::new(impls) + let mut blanket_impls = Vec::new(); + let mut non_blanket_impls = Vec::new(); + + let local_impls = tcx.hir + .trait_impls(trait_id) + .into_iter() + .map(|&node_id| tcx.hir.local_def_id(node_id)); + + for impl_def_id in local_impls.chain(remote_impls.into_iter()) { + let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + if impl_def_id.is_local() && impl_trait_ref.references_error() { + continue + } + + if fast_reject::simplify_type(tcx, impl_trait_ref.self_ty(), false).is_some() { + non_blanket_impls.push(impl_def_id); + } else { + blanket_impls.push(impl_def_id); + } + } + + TraitImpls { + blanket_impls: Rc::new(blanket_impls), + non_blanket_impls: Rc::new(non_blanket_impls), + } } // Query provider for `relevant_trait_impls_for`. pub(super) fn relevant_trait_impls_provider<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, (trait_id, self_ty): (DefId, fast_reject::SimplifiedType)) - -> Rc<Vec<DefId>> + -> TraitImpls { let all_trait_impls = tcx.trait_impls_of(trait_id); let relevant: Vec<DefId> = all_trait_impls + .non_blanket_impls .iter() - .map(|&impl_def_id| impl_def_id) + .cloned() .filter(|&impl_def_id| { let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); let impl_simple_self_ty = fast_reject::simplify_type(tcx, impl_trait_ref.self_ty(), - false); - if let Some(impl_simple_self_ty) = impl_simple_self_ty { - impl_simple_self_ty == self_ty - } else { - // blanket impl (?) - true - } + false).unwrap(); + impl_simple_self_ty == self_ty }) .collect(); - if all_trait_impls.len() == relevant.len() { + if all_trait_impls.non_blanket_impls.len() == relevant.len() { // If we didn't filter anything out, re-use the existing vec. all_trait_impls } else { - Rc::new(relevant) + TraitImpls { + blanket_impls: all_trait_impls.blanket_impls.clone(), + non_blanket_impls: Rc::new(relevant), + } } } |