diff options
| -rw-r--r-- | src/librustc/dep_graph/dep_node.rs | 4 | ||||
| -rw-r--r-- | src/librustc/diagnostics.rs | 61 | ||||
| -rw-r--r-- | src/librustc/traits/mod.rs | 18 | ||||
| -rw-r--r-- | src/librustc/traits/object_safety.rs | 25 | ||||
| -rw-r--r-- | src/librustc/traits/project.rs | 21 | ||||
| -rw-r--r-- | src/librustc/traits/specialize/mod.rs | 50 | ||||
| -rw-r--r-- | src/librustc/traits/specialize/specialization_graph.rs | 25 | ||||
| -rw-r--r-- | src/librustc/ty/maps.rs | 40 | ||||
| -rw-r--r-- | src/librustc/ty/mod.rs | 38 | ||||
| -rw-r--r-- | src/librustc/ty/trait_def.rs | 336 | ||||
| -rw-r--r-- | src/librustc_driver/driver.rs | 3 | ||||
| -rw-r--r-- | src/librustc_metadata/decoder.rs | 15 | ||||
| -rw-r--r-- | src/librustc_metadata/lib.rs | 1 | ||||
| -rw-r--r-- | src/librustc_typeck/check/mod.rs | 4 | ||||
| -rw-r--r-- | src/librustc_typeck/coherence/mod.rs | 4 | ||||
| -rw-r--r-- | src/librustc_typeck/coherence/overlap.rs | 35 | ||||
| -rw-r--r-- | src/librustc_typeck/collect.rs | 12 | ||||
| -rw-r--r-- | src/librustc_typeck/diagnostics.rs | 61 |
18 files changed, 300 insertions, 453 deletions
diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs index 93dd76a6984..15c4469b746 100644 --- a/src/librustc/dep_graph/dep_node.rs +++ b/src/librustc/dep_graph/dep_node.rs @@ -106,6 +106,8 @@ pub enum DepNode<D: Clone + Debug> { UsedTraitImports(D), ConstEval(D), SymbolName(D), + SpecializationGraph(D), + ObjectSafety(D), // The set of impls for a given trait. Ultimately, it would be // nice to get more fine-grained here (e.g., to include a @@ -264,6 +266,8 @@ impl<D: Clone + Debug> DepNode<D> { UsedTraitImports(ref d) => op(d).map(UsedTraitImports), ConstEval(ref d) => op(d).map(ConstEval), SymbolName(ref d) => op(d).map(SymbolName), + SpecializationGraph(ref d) => op(d).map(SpecializationGraph), + ObjectSafety(ref d) => op(d).map(ObjectSafety), TraitImpls(ref d) => op(d).map(TraitImpls), AllLocalTraitImpls => Some(AllLocalTraitImpls), TraitItems(ref d) => op(d).map(TraitItems), diff --git a/src/librustc/diagnostics.rs b/src/librustc/diagnostics.rs index 8ef42826fac..470dcb4bd61 100644 --- a/src/librustc/diagnostics.rs +++ b/src/librustc/diagnostics.rs @@ -409,6 +409,67 @@ RFC. It is, however, [currently unimplemented][iss15872]. [iss15872]: https://github.com/rust-lang/rust/issues/15872 "##, +E0119: r##" +There are conflicting trait implementations for the same type. +Example of erroneous code: + +```compile_fail,E0119 +trait MyTrait { + fn get(&self) -> usize; +} + +impl<T> MyTrait for T { + fn get(&self) -> usize { 0 } +} + +struct Foo { + value: usize +} + +impl MyTrait for Foo { // error: conflicting implementations of trait + // `MyTrait` for type `Foo` + fn get(&self) -> usize { self.value } +} +``` + +When looking for the implementation for the trait, the compiler finds +both the `impl<T> MyTrait for T` where T is all types and the `impl +MyTrait for Foo`. Since a trait cannot be implemented multiple times, +this is an error. So, when you write: + +``` +trait MyTrait { + fn get(&self) -> usize; +} + +impl<T> MyTrait for T { + fn get(&self) -> usize { 0 } +} +``` + +This makes the trait implemented on all types in the scope. So if you +try to implement it on another one after that, the implementations will +conflict. Example: + +``` +trait MyTrait { + fn get(&self) -> usize; +} + +impl<T> MyTrait for T { + fn get(&self) -> usize { 0 } +} + +struct Foo; + +fn main() { + let f = Foo; + + f.get(); // the trait is implemented so we can use it +} +``` +"##, + E0133: r##" Unsafe code was used outside of an unsafe function or block. diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs index 2f525e1b8b4..1823373348b 100644 --- a/src/librustc/traits/mod.rs +++ b/src/librustc/traits/mod.rs @@ -619,8 +619,6 @@ pub fn get_vtable_methods<'a, 'tcx>( debug!("get_vtable_methods({:?})", trait_ref); supertraits(tcx, trait_ref).flat_map(move |trait_ref| { - tcx.populate_implementations_for_trait_if_necessary(trait_ref.def_id()); - let trait_methods = tcx.associated_items(trait_ref.def_id()) .filter(|item| item.kind == ty::AssociatedKind::Method); @@ -782,3 +780,19 @@ impl<'tcx> TraitObligation<'tcx> { ty::Binder(self.predicate.skip_binder().self_ty()) } } + +pub fn provide(providers: &mut ty::maps::Providers) { + *providers = ty::maps::Providers { + is_object_safe: object_safety::is_object_safe_provider, + specialization_graph_of: specialize::specialization_graph_provider, + ..*providers + }; +} + +pub fn provide_extern(providers: &mut ty::maps::Providers) { + *providers = ty::maps::Providers { + is_object_safe: object_safety::is_object_safe_provider, + specialization_graph_of: specialize::specialization_graph_provider, + ..*providers + }; +} diff --git a/src/librustc/traits/object_safety.rs b/src/librustc/traits/object_safety.rs index 66e8e503be4..0e3a53129d1 100644 --- a/src/librustc/traits/object_safety.rs +++ b/src/librustc/traits/object_safety.rs @@ -77,25 +77,6 @@ pub enum MethodViolationCode { } impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { - pub fn is_object_safe(self, trait_def_id: DefId) -> bool { - // Because we query yes/no results frequently, we keep a cache: - let def = self.trait_def(trait_def_id); - - let result = def.object_safety().unwrap_or_else(|| { - let result = self.object_safety_violations(trait_def_id).is_empty(); - - // Record just a yes/no result in the cache; this is what is - // queried most frequently. Note that this may overwrite a - // previous result, but always with the same thing. - def.set_object_safety(result); - - result - }); - - debug!("is_object_safe({:?}) = {}", trait_def_id, result); - - result - } /// Returns the object safety violations that affect /// astconv - currently, Self in supertraits. This is needed @@ -391,3 +372,9 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { error } } + +pub(super) fn is_object_safe_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + trait_def_id: DefId) + -> bool { + tcx.object_safety_violations(trait_def_id).is_empty() +} diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs index e01f97eb1f3..d6f6350373a 100644 --- a/src/librustc/traits/project.rs +++ b/src/librustc/traits/project.rs @@ -1320,23 +1320,10 @@ fn assoc_ty_def<'cx, 'gcx, 'tcx>( let trait_def_id = selcx.tcx().impl_trait_ref(impl_def_id).unwrap().def_id; let trait_def = selcx.tcx().trait_def(trait_def_id); - if !trait_def.is_complete(selcx.tcx()) { - let impl_node = specialization_graph::Node::Impl(impl_def_id); - for item in impl_node.items(selcx.tcx()) { - if item.kind == ty::AssociatedKind::Type && item.name == assoc_ty_name { - return Some(specialization_graph::NodeItem { - node: specialization_graph::Node::Impl(impl_def_id), - item: item, - }); - } - } - None - } else { - trait_def - .ancestors(impl_def_id) - .defs(selcx.tcx(), assoc_ty_name, ty::AssociatedKind::Type) - .next() - } + trait_def + .ancestors(selcx.tcx(), impl_def_id) + .defs(selcx.tcx(), assoc_ty_name, ty::AssociatedKind::Type) + .next() } // # Cache diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs index 3882e218241..b3956e813c4 100644 --- a/src/librustc/traits/specialize/mod.rs +++ b/src/librustc/traits/specialize/mod.rs @@ -27,6 +27,7 @@ use ty::subst::{Subst, Substs}; use traits::{self, Reveal, ObligationCause}; use ty::{self, TyCtxt, TypeFoldable}; use syntax_pos::DUMMY_SP; +use std::rc::Rc; pub mod specialization_graph; @@ -118,7 +119,7 @@ pub fn find_associated_item<'a, 'tcx>( let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap(); let trait_def = tcx.trait_def(trait_def_id); - let ancestors = trait_def.ancestors(impl_data.impl_def_id); + let ancestors = trait_def.ancestors(tcx, impl_data.impl_def_id); match ancestors.defs(tcx, item.name, item.kind).next() { Some(node_item) => { let substs = tcx.infer_ctxt((), Reveal::All).enter(|infcx| { @@ -285,3 +286,50 @@ impl SpecializesCache { self.map.insert((a, b), result); } } + +// Query provider for `specialization_graph_of`. +pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + trait_id: DefId) + -> Rc<specialization_graph::Graph> { + let mut sg = specialization_graph::Graph::new(); + + for &impl_def_id in tcx.trait_impls_of(trait_id).iter() { + if impl_def_id.is_local() { + // This is where impl overlap checking happens: + let insert_result = sg.insert(tcx, impl_def_id); + // Report error if there was one. + if let Err(overlap) = insert_result { + let mut err = struct_span_err!(tcx.sess, + tcx.span_of_impl(impl_def_id).unwrap(), + E0119, + "conflicting implementations of trait `{}`{}:", + overlap.trait_desc, + overlap.self_desc.clone().map_or(String::new(), + |ty| { + format!(" for type `{}`", ty) + })); + + match tcx.span_of_impl(overlap.with_impl) { + Ok(span) => { + err.span_label(span, format!("first implementation here")); + err.span_label(tcx.span_of_impl(impl_def_id).unwrap(), + format!("conflicting implementation{}", + overlap.self_desc + .map_or(String::new(), + |ty| format!(" for `{}`", ty)))); + } + Err(cname) => { + err.note(&format!("conflicting implementation in crate `{}`", cname)); + } + } + + err.emit(); + } + } else { + let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id); + sg.record_impl_from_cstore(tcx, parent, impl_def_id) + } + } + + Rc::new(sg) +} diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs index 6e2c16c82ae..87c98a0ef0e 100644 --- a/src/librustc/traits/specialize/specialization_graph.rs +++ b/src/librustc/traits/specialize/specialization_graph.rs @@ -12,8 +12,9 @@ use super::{OverlapError, specializes}; use hir::def_id::DefId; use traits::{self, Reveal}; -use ty::{self, TyCtxt, TraitDef, TypeFoldable}; +use ty::{self, TyCtxt, TypeFoldable}; use ty::fast_reject::{self, SimplifiedType}; +use std::rc::Rc; use syntax::ast::Name; use util::nodemap::{DefIdMap, FxHashMap}; @@ -301,18 +302,19 @@ impl<'a, 'gcx, 'tcx> Node { } } -pub struct Ancestors<'a> { - trait_def: &'a TraitDef, +pub struct Ancestors { + trait_def_id: DefId, + specialization_graph: Rc<Graph>, current_source: Option<Node>, } -impl<'a> Iterator for Ancestors<'a> { +impl Iterator for Ancestors { type Item = Node; fn next(&mut self) -> Option<Node> { let cur = self.current_source.take(); if let Some(Node::Impl(cur_impl)) = cur { - let parent = self.trait_def.specialization_graph.borrow().parent(cur_impl); - if parent == self.trait_def.def_id { + let parent = self.specialization_graph.parent(cur_impl); + if parent == self.trait_def_id { self.current_source = Some(Node::Trait(parent)); } else { self.current_source = Some(Node::Impl(parent)); @@ -336,7 +338,7 @@ impl<T> NodeItem<T> { } } -impl<'a, 'gcx, 'tcx> Ancestors<'a> { +impl<'a, 'gcx, 'tcx> Ancestors { /// Search the items from the given ancestors, returning each definition /// with the given name and the given kind. #[inline] // FIXME(#35870) Avoid closures being unexported due to impl Trait. @@ -351,9 +353,14 @@ impl<'a, 'gcx, 'tcx> Ancestors<'a> { /// Walk up the specialization ancestors of a given impl, starting with that /// impl itself. -pub fn ancestors<'a>(trait_def: &'a TraitDef, start_from_impl: DefId) -> Ancestors<'a> { +pub fn ancestors(tcx: TyCtxt, + trait_def_id: DefId, + start_from_impl: DefId) + -> Ancestors { + let specialization_graph = tcx.specialization_graph_of(trait_def_id); Ancestors { - trait_def: trait_def, + trait_def_id, + specialization_graph, current_source: Some(Node::Impl(start_from_impl)), } } diff --git a/src/librustc/ty/maps.rs b/src/librustc/ty/maps.rs index 1fd9e8f7375..188ef289ba9 100644 --- a/src/librustc/ty/maps.rs +++ b/src/librustc/ty/maps.rs @@ -18,10 +18,12 @@ use middle::region::RegionMaps; use mir; use mir::transform::{MirSuite, MirPassIndex}; use session::CompileResult; +use traits::specialization_graph; use ty::{self, CrateInherentImpls, Ty, TyCtxt}; use ty::item_path; use ty::steal::Steal; use ty::subst::Substs; +use ty::fast_reject::SimplifiedType; use util::nodemap::{DefIdSet, NodeSet}; use rustc_data_structures::indexed_vec::IndexVec; @@ -98,6 +100,15 @@ impl Key for (CrateNum, DefId) { } } +impl Key for (DefId, SimplifiedType) { + fn map_crate(&self) -> CrateNum { + self.0.krate + } + fn default_span(&self, tcx: TyCtxt) -> Span { + self.0.default_span(tcx) + } +} + impl<'tcx> Key for (DefId, &'tcx Substs<'tcx>) { fn map_crate(&self) -> CrateNum { self.0.krate @@ -391,6 +402,24 @@ impl<'tcx> QueryDescription for queries::is_mir_available<'tcx> { } } +impl<'tcx> QueryDescription for queries::trait_impls_of<'tcx> { + fn describe(tcx: TyCtxt, def_id: DefId) -> String { + format!("trait impls of `{}`", tcx.item_path_str(def_id)) + } +} + +impl<'tcx> QueryDescription for queries::relevant_trait_impls_for<'tcx> { + fn describe(tcx: TyCtxt, (def_id, ty): (DefId, SimplifiedType)) -> String { + format!("relevant impls for: `({}, {:?})`", tcx.item_path_str(def_id), ty) + } +} + +impl<'tcx> QueryDescription for queries::is_object_safe<'tcx> { + fn describe(tcx: TyCtxt, def_id: DefId) -> String { + format!("determine object safety of trait `{}`", tcx.item_path_str(def_id)) + } +} + macro_rules! define_maps { (<$tcx:tt> $($(#[$attr:meta])* @@ -820,6 +849,13 @@ define_maps! { <'tcx> [] item_body_nested_bodies: ItemBodyNestedBodies(DefId) -> Rc<BTreeMap<hir::BodyId, hir::Body>>, [] const_is_rvalue_promotable_to_static: ConstIsRvaluePromotableToStatic(DefId) -> bool, [] is_mir_available: IsMirAvailable(DefId) -> bool, + + [] trait_impls_of: TraitImpls(DefId) -> Rc<Vec<DefId>>, + // 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>>, + [] specialization_graph_of: SpecializationGraph(DefId) -> Rc<specialization_graph::Graph>, + [] is_object_safe: ObjectSafety(DefId) -> bool, } fn coherent_trait_dep_node((_, def_id): (CrateNum, DefId)) -> DepNode<DefId> { @@ -859,3 +895,7 @@ fn mir_keys(_: CrateNum) -> DepNode<DefId> { fn crate_variances(_: CrateNum) -> DepNode<DefId> { DepNode::CrateVariances } + +fn relevant_trait_impls_for((def_id, _): (DefId, SimplifiedType)) -> DepNode<DefId> { + DepNode::TraitImpls(def_id) +} diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs index 6ca401d27ac..a86d7351ef4 100644 --- a/src/librustc/ty/mod.rs +++ b/src/librustc/ty/mod.rs @@ -80,7 +80,7 @@ pub use self::context::{Lift, TypeckTables}; pub use self::instance::{Instance, InstanceDef}; -pub use self::trait_def::{TraitDef, TraitFlags}; +pub use self::trait_def::TraitDef; pub use self::maps::queries; @@ -2324,37 +2324,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { } pub fn trait_has_default_impl(self, trait_def_id: DefId) -> bool { - let def = self.trait_def(trait_def_id); - def.flags.get().intersects(TraitFlags::HAS_DEFAULT_IMPL) - } - - /// Populates the type context with all the implementations for the given - /// trait if necessary. - pub fn populate_implementations_for_trait_if_necessary(self, trait_id: DefId) { - if trait_id.is_local() { - return - } - - // The type is not local, hence we are reading this out of - // metadata and don't need to track edges. - let _ignore = self.dep_graph.in_ignore(); - - let def = self.trait_def(trait_id); - if def.flags.get().intersects(TraitFlags::HAS_REMOTE_IMPLS) { - return; - } - - debug!("populate_implementations_for_trait_if_necessary: searching for {:?}", def); - - for impl_def_id in self.sess.cstore.implementations_of_trait(Some(trait_id)) { - let trait_ref = self.impl_trait_ref(impl_def_id).unwrap(); - - // Record the trait->implementation mapping. - let parent = self.impl_parent(impl_def_id).unwrap_or(trait_id); - def.record_remote_impl(self, impl_def_id, trait_ref, parent); - } - - def.flags.set(def.flags.get() | TraitFlags::HAS_REMOTE_IMPLS); + self.trait_def(trait_def_id).has_default_impl } /// Given the def_id of an impl, return the def_id of the trait it implements. @@ -2603,6 +2573,8 @@ pub fn provide(providers: &mut ty::maps::Providers) { adt_dtorck_constraint, def_span, trait_of_item, + trait_impls_of: trait_def::trait_impls_of_provider, + relevant_trait_impls_for: trait_def::relevant_trait_impls_provider, ..*providers }; } @@ -2611,6 +2583,8 @@ pub fn provide_extern(providers: &mut ty::maps::Providers) { *providers = ty::maps::Providers { adt_sized_constraint, adt_dtorck_constraint, + trait_impls_of: trait_def::trait_impls_of_provider, + relevant_trait_impls_for: trait_def::relevant_trait_impls_provider, ..*providers }; } diff --git a/src/librustc/ty/trait_def.rs b/src/librustc/ty/trait_def.rs index 097b596c5eb..b0357a35b83 100644 --- a/src/librustc/ty/trait_def.rs +++ b/src/librustc/ty/trait_def.rs @@ -8,18 +8,13 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use dep_graph::DepNode; -use hir::def_id::{DefId, LOCAL_CRATE}; -use traits::{self, specialization_graph}; -use ty; +use hir::def_id::DefId; +use traits::specialization_graph; use ty::fast_reject; -use ty::{Ty, TyCtxt, TraitRef}; -use std::cell::{Cell, RefCell}; +use ty::fold::TypeFoldable; +use ty::{Ty, TyCtxt}; +use std::rc::Rc; use hir; -use util::nodemap::FxHashMap; - -use syntax::ast; -use syntax_pos::DUMMY_SP; /// A trait's definition with type information. pub struct TraitDef { @@ -33,40 +28,7 @@ pub struct TraitDef { /// be usable with the sugar (or without it). pub paren_sugar: bool, - // Impls of a trait. To allow for quicker lookup, the impls are indexed by a - // simplified version of their `Self` type: impls with a simplifiable `Self` - // are stored in `nonblanket_impls` keyed by it, while all other impls are - // stored in `blanket_impls`. - // - // A similar division is used within `specialization_graph`, but the ones - // here are (1) stored as a flat list for the trait and (2) populated prior - // to -- and used while -- determining specialization order. - // - // FIXME: solve the reentrancy issues and remove these lists in favor of the - // ones in `specialization_graph`. - // - // These lists are tracked by `DepNode::TraitImpls`; we don't use - // a DepTrackingMap but instead have the `TraitDef` insert the - // required reads/writes. - - /// Impls of the trait. - nonblanket_impls: RefCell< - FxHashMap<fast_reject::SimplifiedType, Vec<DefId>> - >, - - /// Blanket impls associated with the trait. - blanket_impls: RefCell<Vec<DefId>>, - - /// The specialization order for impls of this trait. - pub specialization_graph: RefCell<traits::specialization_graph::Graph>, - - /// Various flags - pub flags: Cell<TraitFlags>, - - /// The number of impls we've added from the local crate. - /// When this number matches up the list in the HIR map, - /// we're done, and the specialization graph is correct. - local_impl_count: Cell<usize>, + pub has_default_impl: bool, /// The ICH of this trait's DefPath, cached here so it doesn't have to be /// recomputed all the time. @@ -77,193 +39,28 @@ impl<'a, 'gcx, 'tcx> TraitDef { pub fn new(def_id: DefId, unsafety: hir::Unsafety, paren_sugar: bool, + has_default_impl: bool, def_path_hash: u64) -> TraitDef { TraitDef { - def_id: def_id, - paren_sugar: paren_sugar, - unsafety: unsafety, - nonblanket_impls: RefCell::new(FxHashMap()), - blanket_impls: RefCell::new(vec![]), - flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS), - local_impl_count: Cell::new(0), - specialization_graph: RefCell::new(traits::specialization_graph::Graph::new()), - def_path_hash: def_path_hash, - } - } - - // returns None if not yet calculated - pub fn object_safety(&self) -> Option<bool> { - if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) { - Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE)) - } else { - None + def_id, + paren_sugar, + unsafety, + has_default_impl, + def_path_hash, } } - pub fn set_object_safety(&self, is_safe: bool) { - assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true)); - self.flags.set( - self.flags.get() | if is_safe { - TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE - } else { - TraitFlags::OBJECT_SAFETY_VALID - } - ); - } - - fn write_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) { - tcx.dep_graph.write(DepNode::TraitImpls(self.def_id)); - } - - fn read_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) { - tcx.dep_graph.read(DepNode::TraitImpls(self.def_id)); - } - - /// Records a basic trait-to-implementation mapping. - /// - /// Returns `true` iff the impl has not previously been recorded. - fn record_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, - impl_def_id: DefId, - impl_trait_ref: TraitRef<'tcx>) - -> bool { - debug!("TraitDef::record_impl for {:?}, from {:?}", - self, impl_trait_ref); - - // Record the write into the impl set, but only for local - // impls: external impls are handled differently. - if impl_def_id.is_local() { - self.write_trait_impls(tcx); - } - - // We don't want to borrow_mut after we already populated all impls, - // so check if an impl is present with an immutable borrow first. - if let Some(sty) = fast_reject::simplify_type(tcx, - impl_trait_ref.self_ty(), false) { - if let Some(is) = self.nonblanket_impls.borrow().get(&sty) { - if is.contains(&impl_def_id) { - return false; // duplicate - skip - } - } - - self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id) - } else { - if self.blanket_impls.borrow().contains(&impl_def_id) { - return false; // duplicate - skip - } - self.blanket_impls.borrow_mut().push(impl_def_id) - } - - true - } - - /// Records a trait-to-implementation mapping for a crate-local impl. - pub fn record_local_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, - impl_def_id: DefId, - impl_trait_ref: TraitRef<'tcx>) { - assert!(impl_def_id.is_local()); - let was_new = self.record_impl(tcx, impl_def_id, impl_trait_ref); - assert!(was_new); - - self.local_impl_count.set(self.local_impl_count.get() + 1); - } - - /// Records a trait-to-implementation mapping. - pub fn record_has_default_impl(&self) { - self.flags.set(self.flags.get() | TraitFlags::HAS_DEFAULT_IMPL); - } - - /// Records a trait-to-implementation mapping for a non-local impl. - /// - /// The `parent_impl` is the immediately-less-specialized impl, or the - /// trait's def ID if the impl is not a specialization -- information that - /// should be pulled from the metadata. - pub fn record_remote_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, - impl_def_id: DefId, - impl_trait_ref: TraitRef<'tcx>, - parent_impl: DefId) { - assert!(!impl_def_id.is_local()); - - // if the impl has not previously been recorded - if self.record_impl(tcx, impl_def_id, impl_trait_ref) { - // if the impl is non-local, it's placed directly into the - // specialization graph using parent information drawn from metadata. - self.specialization_graph.borrow_mut() - .record_impl_from_cstore(tcx, parent_impl, impl_def_id) - } - } - - /// Adds a local impl into the specialization graph, returning an error with - /// overlap information if the impl overlaps but does not specialize an - /// existing impl. - pub fn add_impl_for_specialization(&self, - tcx: TyCtxt<'a, 'gcx, 'tcx>, - impl_def_id: DefId) - -> Result<(), traits::OverlapError> { - assert!(impl_def_id.is_local()); - - self.specialization_graph.borrow_mut() - .insert(tcx, impl_def_id) - } - - pub fn ancestors(&'a self, of_impl: DefId) -> specialization_graph::Ancestors<'a> { - specialization_graph::ancestors(self, of_impl) - } - - /// Whether the impl set and specialization graphs are complete. - pub fn is_complete(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> bool { - tcx.populate_implementations_for_trait_if_necessary(self.def_id); - ty::queries::coherent_trait::try_get(tcx, DUMMY_SP, (LOCAL_CRATE, self.def_id)).is_ok() - } - - /// If any local impls haven't been added yet, returns - /// Some(list of local impls for this trait). - fn missing_local_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) - -> Option<&'gcx [ast::NodeId]> { - if self.flags.get().intersects(TraitFlags::HAS_LOCAL_IMPLS) { - return None; - } - - if self.is_complete(tcx) { - self.flags.set(self.flags.get() | TraitFlags::HAS_LOCAL_IMPLS); - return None; - } - - let impls = tcx.hir.trait_impls(self.def_id); - assert!(self.local_impl_count.get() <= impls.len()); - if self.local_impl_count.get() == impls.len() { - self.flags.set(self.flags.get() | TraitFlags::HAS_LOCAL_IMPLS); - return None; - } - - Some(impls) + pub fn ancestors(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, + of_impl: DefId) + -> specialization_graph::Ancestors { + specialization_graph::ancestors(tcx, self.def_id, of_impl) } pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, mut f: F) { - self.read_trait_impls(tcx); - tcx.populate_implementations_for_trait_if_necessary(self.def_id); - - let local_impls = self.missing_local_impls(tcx); - if let Some(impls) = local_impls { - for &id in impls { - f(tcx.hir.local_def_id(id)); - } - } - let mut f = |def_id: DefId| { - if !(local_impls.is_some() && def_id.is_local()) { - f(def_id); - } - }; - - for &impl_def_id in self.blanket_impls.borrow().iter() { + for &impl_def_id in tcx.trait_impls_of(self.def_id).iter() { f(impl_def_id); } - - for v in self.nonblanket_impls.borrow().values() { - for &impl_def_id in v { - f(impl_def_id); - } - } } /// Iterate over every impl that could possibly match the @@ -273,25 +70,6 @@ impl<'a, 'gcx, 'tcx> TraitDef { self_ty: Ty<'tcx>, mut f: F) { - self.read_trait_impls(tcx); - tcx.populate_implementations_for_trait_if_necessary(self.def_id); - - let local_impls = self.missing_local_impls(tcx); - if let Some(impls) = local_impls { - for &id in impls { - f(tcx.hir.local_def_id(id)); - } - } - let mut f = |def_id: DefId| { - if !(local_impls.is_some() && def_id.is_local()) { - f(def_id); - } - }; - - for &impl_def_id in self.blanket_impls.borrow().iter() { - f(impl_def_id); - } - // simplify_type(.., false) basically replaces type parameters and // projections with infer-variables. This is, of course, done on // the impl trait-ref when it is instantiated, but not on the @@ -304,29 +82,71 @@ impl<'a, 'gcx, 'tcx> TraitDef { // replace `S` with anything - this impl of course can't be // selected, and as there are hundreds of similar impls, // considering them would significantly harm performance. - if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, true) { - if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) { - for &impl_def_id in impls { - f(impl_def_id); - } - } + let relevant_impls = if let Some(simplified_self_ty) = + fast_reject::simplify_type(tcx, self_ty, true) { + tcx.relevant_trait_impls_for((self.def_id, simplified_self_ty)) } else { - for v in self.nonblanket_impls.borrow().values() { - for &impl_def_id in v { - f(impl_def_id); - } - } + tcx.trait_impls_of(self.def_id) + }; + + for &impl_def_id in relevant_impls.iter() { + f(impl_def_id); } } } -bitflags! { - flags TraitFlags: u32 { - const NO_TRAIT_FLAGS = 0, - const HAS_DEFAULT_IMPL = 1 << 0, - const IS_OBJECT_SAFE = 1 << 1, - const OBJECT_SAFETY_VALID = 1 << 2, - const HAS_REMOTE_IMPLS = 1 << 3, - const HAS_LOCAL_IMPLS = 1 << 4, +// 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() { + // Traits defined in the current crate can't have impls in upstream + // crates, so we don't bother querying the cstore. + Vec::new() + } else { + 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) +} + +// 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>> +{ + let all_trait_impls = tcx.trait_impls_of(trait_id); + + let relevant: Vec<DefId> = all_trait_impls + .iter() + .map(|&impl_def_id| impl_def_id) + .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 + } + }) + .collect(); + + if all_trait_impls.len() == relevant.len() { + // If we didn't filter anything out, re-use the existing vec. + all_trait_impls + } else { + Rc::new(relevant) } } diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs index 8fddbe110b0..c23563e13be 100644 --- a/src/librustc_driver/driver.rs +++ b/src/librustc_driver/driver.rs @@ -22,6 +22,7 @@ use rustc::middle::{self, dependency_format, stability, reachable}; use rustc::middle::privacy::AccessLevels; use rustc::mir::transform::{MIR_CONST, MIR_VALIDATED, MIR_OPTIMIZED, Passes}; use rustc::ty::{self, TyCtxt, Resolutions, GlobalArenas}; +use rustc::traits; use rustc::util::common::time; use rustc::util::nodemap::NodeSet; use rustc::util::fs::rename_or_copy_remove; @@ -892,6 +893,7 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session, trans::provide(&mut local_providers); typeck::provide(&mut local_providers); ty::provide(&mut local_providers); + traits::provide(&mut local_providers); reachable::provide(&mut local_providers); rustc_const_eval::provide(&mut local_providers); middle::region::provide(&mut local_providers); @@ -900,6 +902,7 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session, cstore::provide(&mut extern_providers); trans::provide(&mut extern_providers); ty::provide_extern(&mut extern_providers); + traits::provide_extern(&mut extern_providers); // FIXME(eddyb) get rid of this once we replace const_eval with miri. rustc_const_eval::provide(&mut extern_providers); diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs index 51822474254..941b965d9a4 100644 --- a/src/librustc_metadata/decoder.rs +++ b/src/librustc_metadata/decoder.rs @@ -505,16 +505,11 @@ impl<'a, 'tcx> CrateMetadata { _ => bug!(), }; - let def = ty::TraitDef::new(self.local_def_id(item_id), - data.unsafety, - data.paren_sugar, - self.def_path_table.def_path_hash(item_id)); - - if data.has_default_impl { - def.record_has_default_impl(); - } - - def + ty::TraitDef::new(self.local_def_id(item_id), + data.unsafety, + data.paren_sugar, + data.has_default_impl, + self.def_path_table.def_path_hash(item_id)) } fn get_variant(&self, item: &Entry, index: DefIndex) -> ty::VariantDef { diff --git a/src/librustc_metadata/lib.rs b/src/librustc_metadata/lib.rs index 27555f49e57..6a40174fa02 100644 --- a/src/librustc_metadata/lib.rs +++ b/src/librustc_metadata/lib.rs @@ -29,6 +29,7 @@ #![cfg_attr(stage0, unstable(feature = "rustc_private", issue = "27812"))] #![cfg_attr(stage0, feature(staged_api))] +#![feature(sort_unstable)] #[macro_use] extern crate log; diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs index 70d2867c08c..d304d79bc52 100644 --- a/src/librustc_typeck/check/mod.rs +++ b/src/librustc_typeck/check/mod.rs @@ -1200,7 +1200,7 @@ fn check_specialization_validity<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, impl_id: DefId, impl_item: &hir::ImplItem) { - let ancestors = trait_def.ancestors(impl_id); + let ancestors = trait_def.ancestors(tcx, impl_id); let kind = match impl_item.node { hir::ImplItemKind::Const(..) => ty::AssociatedKind::Const, @@ -1330,7 +1330,7 @@ fn check_impl_items_against_trait<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, let mut invalidated_items = Vec::new(); let associated_type_overridden = overridden_associated_type.is_some(); for trait_item in tcx.associated_items(impl_trait_ref.def_id) { - let is_implemented = trait_def.ancestors(impl_id) + let is_implemented = trait_def.ancestors(tcx, impl_id) .defs(tcx, trait_item.name, trait_item.kind) .next() .map(|node_item| !node_item.node.is_from_trait()) diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs index 8b9dc20315d..165be49f760 100644 --- a/src/librustc_typeck/coherence/mod.rs +++ b/src/librustc_typeck/coherence/mod.rs @@ -46,8 +46,6 @@ fn check_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, node_id: ast::NodeId) { } enforce_trait_manually_implementable(tcx, impl_def_id, trait_ref.def_id); - let trait_def = tcx.trait_def(trait_ref.def_id); - trait_def.record_local_impl(tcx, impl_def_id, trait_ref); } } @@ -117,8 +115,6 @@ pub fn provide(providers: &mut Providers) { fn coherent_trait<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, (_, def_id): (CrateNum, DefId)) { - tcx.populate_implementations_for_trait_if_necessary(def_id); - let impls = tcx.hir.trait_impls(def_id); for &impl_id in impls { check_impl(tcx, impl_id); diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs index f479dc2e6ab..ba1d7b18e8c 100644 --- a/src/librustc_typeck/coherence/overlap.rs +++ b/src/librustc_typeck/coherence/overlap.rs @@ -41,39 +41,10 @@ pub fn check_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, node_id: ast::NodeId) { let _task = tcx.dep_graph.in_task(DepNode::CoherenceOverlapCheck(trait_def_id)); - let def = tcx.trait_def(trait_def_id); - - // attempt to insert into the specialization graph - let insert_result = def.add_impl_for_specialization(tcx, impl_def_id); - - // insertion failed due to overlap - if let Err(overlap) = insert_result { - let mut err = struct_span_err!(tcx.sess, - tcx.span_of_impl(impl_def_id).unwrap(), - E0119, - "conflicting implementations of trait `{}`{}:", - overlap.trait_desc, - overlap.self_desc.clone().map_or(String::new(), - |ty| { - format!(" for type `{}`", ty) - })); - - match tcx.span_of_impl(overlap.with_impl) { - Ok(span) => { - err.span_label(span, "first implementation here"); - err.span_label(tcx.span_of_impl(impl_def_id).unwrap(), - format!("conflicting implementation{}", - overlap.self_desc - .map_or(String::new(), - |ty| format!(" for `{}`", ty)))); - } - Err(cname) => { - err.note(&format!("conflicting implementation in crate `{}`", cname)); - } - } + // Trigger building the specialization graph for the trait of this impl. + // This will detect any overlap errors. + tcx.specialization_graph_of(trait_def_id); - err.emit(); - } // check for overlap with the automatic `impl Trait for Trait` if let ty::TyDynamic(ref data, ..) = trait_ref.self_ty().sty { diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs index 7c6c70024ce..cb1bd3e099d 100644 --- a/src/librustc_typeck/collect.rs +++ b/src/librustc_typeck/collect.rs @@ -749,12 +749,12 @@ fn trait_def<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, } let def_path_hash = tcx.def_path_hash(def_id); - let def = ty::TraitDef::new(def_id, unsafety, paren_sugar, def_path_hash); - - if tcx.hir.trait_is_auto(def_id) { - def.record_has_default_impl(); - } - + let has_default_impl = tcx.hir.trait_is_auto(def_id); + let def = ty::TraitDef::new(def_id, + unsafety, + paren_sugar, + has_default_impl, + def_path_hash); tcx.alloc_trait_def(def) } diff --git a/src/librustc_typeck/diagnostics.rs b/src/librustc_typeck/diagnostics.rs index 0f42ee15ecf..f9ebe3fff5b 100644 --- a/src/librustc_typeck/diagnostics.rs +++ b/src/librustc_typeck/diagnostics.rs @@ -1524,67 +1524,6 @@ impl TypeWrapper { ``` "##, -E0119: r##" -There are conflicting trait implementations for the same type. -Example of erroneous code: - -```compile_fail,E0119 -trait MyTrait { - fn get(&self) -> usize; -} - -impl<T> MyTrait for T { - fn get(&self) -> usize { 0 } -} - -struct Foo { - value: usize -} - -impl MyTrait for Foo { // error: conflicting implementations of trait - // `MyTrait` for type `Foo` - fn get(&self) -> usize { self.value } -} -``` - -When looking for the implementation for the trait, the compiler finds -both the `impl<T> MyTrait for T` where T is all types and the `impl -MyTrait for Foo`. Since a trait cannot be implemented multiple times, -this is an error. So, when you write: - -``` -trait MyTrait { - fn get(&self) -> usize; -} - -impl<T> MyTrait for T { - fn get(&self) -> usize { 0 } -} -``` - -This makes the trait implemented on all types in the scope. So if you -try to implement it on another one after that, the implementations will -conflict. Example: - -``` -trait MyTrait { - fn get(&self) -> usize; -} - -impl<T> MyTrait for T { - fn get(&self) -> usize { 0 } -} - -struct Foo; - -fn main() { - let f = Foo; - - f.get(); // the trait is implemented so we can use it -} -``` -"##, - E0120: r##" An attempt was made to implement Drop on a trait, which is not allowed: only structs and enums can implement Drop. An example causing this error: |