Change the data structures for tracking defaulted traits. In the tcx, we

now have a simple set of trait def-ids. During coherence, we use a
separate table to track the default impls for any given trait so that we
can report a nice error. This fixes various bugs in the metadata
encoding that led to `ty::trait_has_default_impl` yielding the wrong
values in the cross-crate case. (In particular, default impl def-ids
were not included in the list of all impl def-ids; I debated fixing just
that, but this approach seemed cleaner overall, since we usually treat
the "defaulted" bit on traits as being a property of the trait, and now
iterating over a list of impls doesn't intermingle default impls with
normal impls.)

7 files changed, 51 insertions, 63 deletions

diff --git a/src/librustc/metadata/common.rs b/src/librustc/metadata/common.rs
index b28106a72e0..081c64ecae8 100644
--- a/src/librustc/metadata/common.rs
+++ b/src/librustc/metadata/common.rs
@@ -254,3 +254,5 @@ pub const tag_codemap: uint = 0xa1;
 pub const tag_codemap_filemap: uint = 0xa2;
 
 pub const tag_item_super_predicates: uint = 0xa3;
+
+pub const tag_defaulted_trait: uint = 0xa4;
diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index c7785ff4c87..ed5783c8dba 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -407,7 +407,7 @@ pub fn is_associated_type(cstore: &cstore::CStore, def: ast::DefId) -> bool {
     decoder::is_associated_type(&*cdata, def.node)
 }
 
-pub fn is_default_trait(cstore: &cstore::CStore, def: ast::DefId) -> bool {
-    let cdata = cstore.get_crate_data(def.krate);
-    decoder::is_default_trait(&*cdata, def.node)
+pub fn is_defaulted_trait(cstore: &cstore::CStore, trait_def_id: ast::DefId) -> bool {
+    let cdata = cstore.get_crate_data(trait_def_id.krate);
+    decoder::is_defaulted_trait(&*cdata, trait_def_id.node)
 }
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index f5f9bd41c8b..dbbc17c018a 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -1537,12 +1537,11 @@ pub fn is_associated_type(cdata: Cmd, id: ast::NodeId) -> bool {
     }
 }
 
-pub fn is_default_trait<'tcx>(cdata: Cmd, id: ast::NodeId) -> bool {
-    let item_doc = lookup_item(id, cdata.data());
-    match item_family(item_doc) {
-        Family::DefaultImpl => true,
-        _ => false
-    }
+pub fn is_defaulted_trait<'tcx>(cdata: Cmd, trait_id: ast::NodeId) -> bool {
+    let trait_doc = lookup_item(trait_id, cdata.data());
+    assert!(item_family(trait_doc) == Family::Trait);
+    let defaulted_doc = reader::get_doc(trait_doc, tag_defaulted_trait);
+    reader::doc_as_u8(defaulted_doc) != 0
 }
 
 pub fn get_imported_filemaps(metadata: &[u8]) -> Vec<codemap::FileMap> {
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index c4ba2373b9f..08263eb8e6a 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -1288,6 +1288,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
         let trait_predicates = ty::lookup_predicates(tcx, def_id);
         encode_unsafety(rbml_w, trait_def.unsafety);
         encode_paren_sugar(rbml_w, trait_def.paren_sugar);
+        encode_defaulted(rbml_w, ty::trait_has_default_impl(tcx, def_id));
         encode_associated_type_names(rbml_w, &trait_def.associated_type_names);
         encode_generics(rbml_w, ecx, &trait_def.generics, &trait_predicates, tag_item_generics);
         encode_predicates(rbml_w, ecx, &ty::lookup_super_predicates(tcx, def_id),
@@ -1660,6 +1661,11 @@ fn encode_paren_sugar(rbml_w: &mut Encoder, paren_sugar: bool) {
     rbml_w.wr_tagged_u8(tag_paren_sugar, byte);
 }
 
+fn encode_defaulted(rbml_w: &mut Encoder, is_defaulted: bool) {
+    let byte: u8 = if is_defaulted {1} else {0};
+    rbml_w.wr_tagged_u8(tag_defaulted_trait, byte);
+}
+
 fn encode_associated_type_names(rbml_w: &mut Encoder, names: &[ast::Name]) {
     rbml_w.start_tag(tag_associated_type_names);
     for &name in names {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index add829074c4..60a04417e02 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -757,8 +757,8 @@ pub struct ctxt<'tcx> {
     /// Maps a trait onto a list of impls of that trait.
     pub trait_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
 
-    /// Maps a trait onto a list of *default* trait implementations
-    default_trait_impls: RefCell<DefIdMap<ast::DefId>>,
+    /// A set of traits that have a default impl
+    traits_with_default_impls: RefCell<DefIdMap<()>>,
 
     /// Maps a DefId of a type to a list of its inherent impls.
     /// Contains implementations of methods that are inherent to a type.
@@ -2591,7 +2591,7 @@ pub fn mk_ctxt<'tcx>(s: Session,
         destructor_for_type: RefCell::new(DefIdMap()),
         destructors: RefCell::new(DefIdSet()),
         trait_impls: RefCell::new(DefIdMap()),
-        default_trait_impls: RefCell::new(DefIdMap()),
+        traits_with_default_impls: RefCell::new(DefIdMap()),
         inherent_impls: RefCell::new(DefIdMap()),
         impl_items: RefCell::new(DefIdMap()),
         used_unsafe: RefCell::new(NodeSet()),
@@ -5975,32 +5975,22 @@ pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
         || Rc::new(csearch::get_item_variances(&tcx.sess.cstore, item_id)))
 }
 
-pub fn trait_default_impl(tcx: &ctxt, trait_def_id: DefId) -> Option<ast::DefId> {
-    match tcx.default_trait_impls.borrow().get(&trait_def_id) {
-        Some(id) => Some(*id),
-        None => None
-    }
-}
-
 pub fn trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) -> bool {
+    populate_implementations_for_trait_if_necessary(tcx, trait_def_id);
     match tcx.lang_items.to_builtin_kind(trait_def_id) {
         Some(BoundSend) | Some(BoundSync) => true,
-        _ => tcx.default_trait_impls.borrow().contains_key(&trait_def_id)
+        _ => tcx.traits_with_default_impls.borrow().contains_key(&trait_def_id),
     }
 }
 
 /// Records a trait-to-implementation mapping.
-pub fn record_default_trait_implementation(tcx: &ctxt,
-                                           trait_def_id: DefId,
-                                           impl_def_id: DefId) {
-
+pub fn record_trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) {
     // We're using the latest implementation found as the reference one.
     // Duplicated implementations are caught and reported in the coherence
     // step.
-    tcx.default_trait_impls.borrow_mut().insert(trait_def_id, impl_def_id);
+    tcx.traits_with_default_impls.borrow_mut().insert(trait_def_id, ());
 }
 
-
 /// Records a trait-to-implementation mapping.
 pub fn record_trait_implementation(tcx: &ctxt,
                                    trait_def_id: DefId,
@@ -6031,8 +6021,7 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
     debug!("populate_implementations_for_type_if_necessary: searching for {:?}", type_id);
 
     let mut inherent_impls = Vec::new();
-    csearch::each_implementation_for_type(&tcx.sess.cstore, type_id,
-            |impl_def_id| {
+    csearch::each_implementation_for_type(&tcx.sess.cstore, type_id, |impl_def_id| {
         let impl_items = csearch::get_impl_items(&tcx.sess.cstore, impl_def_id);
 
         // Record the trait->implementation mappings, if applicable.
@@ -6078,27 +6067,20 @@ pub fn populate_implementations_for_trait_if_necessary(
     if trait_id.krate == LOCAL_CRATE {
         return
     }
+
     if tcx.populated_external_traits.borrow().contains(&trait_id) {
         return
     }
 
-    csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id,
-            |implementation_def_id|{
-        let impl_items = csearch::get_impl_items(&tcx.sess.cstore, implementation_def_id);
+    if csearch::is_defaulted_trait(&tcx.sess.cstore, trait_id) {
+        record_trait_has_default_impl(tcx, trait_id);
+    }
 
-        if csearch::is_default_trait(&tcx.sess.cstore, implementation_def_id) {
-            record_default_trait_implementation(tcx, trait_id,
-                                                implementation_def_id);
-            tcx.populated_external_traits.borrow_mut().insert(trait_id);
+    csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id, |implementation_def_id| {
+        let impl_items = csearch::get_impl_items(&tcx.sess.cstore, implementation_def_id);
 
-            // Nothing else to do for default trait implementations since
-            // they are not allowed to have type parameters, methods, or any
-            // other item that could be associated to a trait implementation.
-            return;
-        } else {
-            // Record the trait->implementation mapping.
-            record_trait_implementation(tcx, trait_id, implementation_def_id);
-        }
+        // Record the trait->implementation mapping.
+        record_trait_implementation(tcx, trait_id, implementation_def_id);
 
         // For any methods that use a default implementation, add them to
         // the map. This is a bit unfortunate.
@@ -6108,8 +6090,8 @@ pub fn populate_implementations_for_trait_if_necessary(
                 MethodTraitItem(method) => {
                     if let Some(source) = method.provided_source {
                         tcx.provided_method_sources
-                           .borrow_mut()
-                           .insert(method_def_id, source);
+                            .borrow_mut()
+                            .insert(method_def_id, source);
                     }
                 }
                 TypeTraitItem(_) => {}
diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs
index a6ecafb6241..466d00b348b 100644
--- a/src/librustc_typeck/coherence/overlap.rs
+++ b/src/librustc_typeck/coherence/overlap.rs
@@ -20,10 +20,11 @@ use syntax::ast;
 use syntax::ast_util;
 use syntax::visit;
 use syntax::codemap::Span;
+use util::nodemap::DefIdMap;
 use util::ppaux::Repr;
 
 pub fn check(tcx: &ty::ctxt) {
-    let mut overlap = OverlapChecker { tcx: tcx };
+    let mut overlap = OverlapChecker { tcx: tcx, default_impls: DefIdMap() };
     overlap.check_for_overlapping_impls();
 
     // this secondary walk specifically checks for impls of defaulted
@@ -33,6 +34,9 @@ pub fn check(tcx: &ty::ctxt) {
 
 struct OverlapChecker<'cx, 'tcx:'cx> {
     tcx: &'cx ty::ctxt<'tcx>,
+
+    // maps from a trait def-id to an impl id
+    default_impls: DefIdMap<ast::NodeId>,
 }
 
 impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> {
@@ -134,24 +138,19 @@ impl<'cx, 'tcx,'v> visit::Visitor<'v> for OverlapChecker<'cx, 'tcx> {
     fn visit_item(&mut self, item: &'v ast::Item) {
         match item.node {
             ast::ItemDefaultImpl(_, _) => {
+                // look for another default impl; note that due to the
+                // general orphan/coherence rules, it must always be
+                // in this crate.
                 let impl_def_id = ast_util::local_def(item.id);
-                match ty::impl_trait_ref(self.tcx, impl_def_id) {
-                    Some(ref trait_ref) => {
-                        match ty::trait_default_impl(self.tcx, trait_ref.def_id) {
-                            Some(other_impl) if other_impl != impl_def_id => {
-                                self.report_overlap_error(trait_ref.def_id,
-                                                          other_impl,
-                                                          impl_def_id);
-                            }
-                            Some(_) => {}
-                            None => {
-                                self.tcx.sess.bug(
-                                          &format!("no default implementation recorded for `{:?}`",
-                                          item));
-                            }
-                        }
+                let trait_ref = ty::impl_trait_ref(self.tcx, impl_def_id).unwrap();
+                let prev_default_impl = self.default_impls.insert(trait_ref.def_id, item.id);
+                match prev_default_impl {
+                    Some(prev_id) => {
+                        self.report_overlap_error(trait_ref.def_id,
+                                                  impl_def_id,
+                                                  ast_util::local_def(prev_id));
                     }
-                    _ => {}
+                    None => { }
                 }
             }
             _ => {}
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 77e3b6ee64b..5591281263d 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -979,7 +979,7 @@ fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
                                                            None,
                                                            None);
 
-            ty::record_default_trait_implementation(tcx, trait_ref.def_id, local_def(it.id))
+            ty::record_trait_has_default_impl(tcx, trait_ref.def_id);
         }
         ast::ItemImpl(_, _,
                       ref generics,