Auto merge of #64564 - jonas-schievink:cowardly-default, r=nikomatsakis

Deny specializing items not in the parent impl

Part of https://github.com/rust-lang/rust/issues/29661 (https://github.com/rust-lang/rfcs/pull/2532). At least sort of?

This was discussed in https://github.com/rust-lang/rust/pull/61812#discussion_r300504114 and is needed for that PR to make progress (fixing an unsoundness).

One annoyance with doing this is that it sometimes requires users to copy-paste a provided trait method into an impl just to mark it `default` (ie. there is no syntax to forward this impl method to the provided trait method).

cc @Centril and @arielb1

12 files changed, 268 insertions, 45 deletions

diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index b2789a535fe..9b5d9431ae2 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -871,11 +871,33 @@ impl<I: Iterator + ?Sized> Iterator for Box<I> {
     fn nth(&mut self, n: usize) -> Option<I::Item> {
         (**self).nth(n)
     }
+    fn last(self) -> Option<I::Item> {
+        BoxIter::last(self)
+    }
+}
+
+trait BoxIter {
+    type Item;
+    fn last(self) -> Option<Self::Item>;
+}
+
+impl<I: Iterator + ?Sized> BoxIter for Box<I> {
+    type Item = I::Item;
+    default fn last(self) -> Option<I::Item> {
+        #[inline]
+        fn some<T>(_: Option<T>, x: T) -> Option<T> {
+            Some(x)
+        }
+
+        self.fold(None, some)
+    }
 }
 
+/// Specialization for sized `I`s that uses `I`s implementation of `last()`
+/// instead of the default.
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator + Sized> Iterator for Box<I> {
-    fn last(self) -> Option<I::Item> where I: Sized {
+impl<I: Iterator> BoxIter for Box<I> {
+    fn last(self) -> Option<I::Item> {
         (*self).last()
     }
 }
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 5b4ec885d77..d88bbe145d1 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -1505,8 +1505,8 @@ fn assoc_ty_def(
 
     if let Some(assoc_item) = trait_def
         .ancestors(tcx, impl_def_id)
-        .defs(tcx, assoc_ty_name, ty::AssocKind::Type, trait_def_id)
-        .next() {
+        .leaf_def(tcx, assoc_ty_name, ty::AssocKind::Type) {
+
         assoc_item
     } else {
         // This is saying that neither the trait nor
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index f0389bb037a..9c80ef7d4a2 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -125,7 +125,7 @@ pub fn find_associated_item<'tcx>(
     let trait_def = tcx.trait_def(trait_def_id);
 
     let ancestors = trait_def.ancestors(tcx, impl_data.impl_def_id);
-    match ancestors.defs(tcx, item.ident, item.kind, trait_def_id).next() {
+    match ancestors.leaf_def(tcx, item.ident, item.kind) {
         Some(node_item) => {
             let substs = tcx.infer_ctxt().enter(|infcx| {
                 let param_env = param_env.with_reveal_all();
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index 43f558d6443..c64d6748ea9 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -7,7 +7,6 @@ use crate::traits;
 use crate::ty::{self, TyCtxt, TypeFoldable};
 use crate::ty::fast_reject::{self, SimplifiedType};
 use syntax::ast::Ident;
-use crate::util::captures::Captures;
 use crate::util::nodemap::{DefIdMap, FxHashMap};
 
 /// A per-trait graph of impls in specialization order. At the moment, this
@@ -419,6 +418,35 @@ impl<'tcx> Node {
         tcx.associated_items(self.def_id())
     }
 
+    /// Finds an associated item defined in this node.
+    ///
+    /// If this returns `None`, the item can potentially still be found in
+    /// parents of this node.
+    pub fn item(
+        &self,
+        tcx: TyCtxt<'tcx>,
+        trait_item_name: Ident,
+        trait_item_kind: ty::AssocKind,
+        trait_def_id: DefId,
+    ) -> Option<ty::AssocItem> {
+        use crate::ty::AssocKind::*;
+
+        tcx.associated_items(self.def_id())
+            .find(move |impl_item| match (trait_item_kind, impl_item.kind) {
+                | (Const, Const)
+                | (Method, Method)
+                | (Type, Type)
+                | (Type, OpaqueTy)  // assoc. types can be made opaque in impls
+                => tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id),
+
+                | (Const, _)
+                | (Method, _)
+                | (Type, _)
+                | (OpaqueTy, _)
+                => false,
+            })
+    }
+
     pub fn def_id(&self) -> DefId {
         match *self {
             Node::Impl(did) => did,
@@ -427,6 +455,7 @@ impl<'tcx> Node {
     }
 }
 
+#[derive(Copy, Clone)]
 pub struct Ancestors<'tcx> {
     trait_def_id: DefId,
     specialization_graph: &'tcx Graph,
@@ -465,32 +494,18 @@ impl<T> NodeItem<T> {
 }
 
 impl<'tcx> Ancestors<'tcx> {
-    /// Search the items from the given ancestors, returning each definition
-    /// with the given name and the given kind.
-    // FIXME(#35870): avoid closures being unexported due to `impl Trait`.
-    #[inline]
-    pub fn defs(
-        self,
+    /// Finds the bottom-most (ie. most specialized) definition of an associated
+    /// item.
+    pub fn leaf_def(
+        mut self,
         tcx: TyCtxt<'tcx>,
         trait_item_name: Ident,
         trait_item_kind: ty::AssocKind,
-        trait_def_id: DefId,
-    ) -> impl Iterator<Item = NodeItem<ty::AssocItem>> + Captures<'tcx> + 'tcx {
-        self.flat_map(move |node| {
-            use crate::ty::AssocKind::*;
-            node.items(tcx).filter(move |impl_item| match (trait_item_kind, impl_item.kind) {
-                | (Const, Const)
-                | (Method, Method)
-                | (Type, Type)
-                | (Type, OpaqueTy)
-                => tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id),
-
-                | (Const, _)
-                | (Method, _)
-                | (Type, _)
-                | (OpaqueTy, _)
-                => false,
-            }).map(move |item| NodeItem { node: node, item: item })
+    ) -> Option<NodeItem<ty::AssocItem>> {
+        let trait_def_id = self.trait_def_id;
+        self.find_map(|node| {
+            node.item(tcx, trait_item_name, trait_item_kind, trait_def_id)
+                .map(|item| NodeItem { node, item })
         })
     }
 }
diff --git a/src/librustc/traits/util.rs b/src/librustc/traits/util.rs
index 18ec2241b2d..d8b1effe09b 100644
--- a/src/librustc/traits/util.rs
+++ b/src/librustc/traits/util.rs
@@ -4,7 +4,6 @@ use syntax_pos::Span;
 
 use crate::hir;
 use crate::hir::def_id::DefId;
-use crate::traits::specialize::specialization_graph::NodeItem;
 use crate::ty::{self, Ty, TyCtxt, ToPredicate, ToPolyTraitRef};
 use crate::ty::outlives::Component;
 use crate::ty::subst::{GenericArg, Subst, SubstsRef};
@@ -667,8 +666,8 @@ impl<'tcx> TyCtxt<'tcx> {
         }
     }
 
-    pub fn impl_item_is_final(self, node_item: &NodeItem<hir::Defaultness>) -> bool {
-        node_item.item.is_final() && !self.impl_is_default(node_item.node.def_id())
+    pub fn impl_item_is_final(self, assoc_item: &ty::AssocItem) -> bool {
+        assoc_item.defaultness.is_final() && !self.impl_is_default(assoc_item.container.id())
     }
 }
 
diff --git a/src/librustc/ty/query/config.rs b/src/librustc/ty/query/config.rs
index 91082c59ba0..c1c6a655d96 100644
--- a/src/librustc/ty/query/config.rs
+++ b/src/librustc/ty/query/config.rs
@@ -73,6 +73,17 @@ impl<'tcx, M: QueryAccessors<'tcx, Key = DefId>> QueryDescription<'tcx> for M {
             format!("processing {:?} with query `{}`", def_id, name).into()
         }
     }
+
+    default fn cache_on_disk(_: TyCtxt<'tcx>, _: Self::Key, _: Option<&Self::Value>) -> bool {
+        false
+    }
+
+    default fn try_load_from_disk(
+        _: TyCtxt<'tcx>,
+        _: SerializedDepNodeIndex,
+    ) -> Option<Self::Value> {
+        bug!("QueryDescription::load_from_disk() called for an unsupported query.")
+    }
 }
 
 impl<'tcx> QueryDescription<'tcx> for queries::analysis<'tcx> {
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 7380bf7536d..f130ee821d1 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1713,8 +1713,6 @@ fn check_specialization_validity<'tcx>(
     impl_id: DefId,
     impl_item: &hir::ImplItem,
 ) {
-    let ancestors = trait_def.ancestors(tcx, impl_id);
-
     let kind = match impl_item.kind {
         hir::ImplItemKind::Const(..) => ty::AssocKind::Const,
         hir::ImplItemKind::Method(..) => ty::AssocKind::Method,
@@ -1722,15 +1720,53 @@ fn check_specialization_validity<'tcx>(
         hir::ImplItemKind::TyAlias(_) => ty::AssocKind::Type,
     };
 
-    let parent = ancestors.defs(tcx, trait_item.ident, kind, trait_def.def_id).nth(1)
-        .map(|node_item| node_item.map(|parent| parent.defaultness));
+    let mut ancestor_impls = trait_def.ancestors(tcx, impl_id)
+        .skip(1)
+        .filter_map(|parent| {
+            if parent.is_from_trait() {
+                None
+            } else {
+                Some((parent, parent.item(tcx, trait_item.ident, kind, trait_def.def_id)))
+            }
+        })
+        .peekable();
 
-    if let Some(parent) = parent {
-        if tcx.impl_item_is_final(&parent) {
-            report_forbidden_specialization(tcx, impl_item, parent.node.def_id());
-        }
+    if ancestor_impls.peek().is_none() {
+        // No parent, nothing to specialize.
+        return;
     }
 
+    let opt_result = ancestor_impls.find_map(|(parent_impl, parent_item)| {
+        match parent_item {
+            // Parent impl exists, and contains the parent item we're trying to specialize, but
+            // doesn't mark it `default`.
+            Some(parent_item) if tcx.impl_item_is_final(&parent_item) => {
+                Some(Err(parent_impl.def_id()))
+            }
+
+            // Parent impl contains item and makes it specializable.
+            Some(_) => {
+                Some(Ok(()))
+            }
+
+            // Parent impl doesn't mention the item. This means it's inherited from the
+            // grandparent. In that case, if parent is a `default impl`, inherited items use the
+            // "defaultness" from the grandparent, else they are final.
+            None => if tcx.impl_is_default(parent_impl.def_id()) {
+                None
+            } else {
+                Some(Err(parent_impl.def_id()))
+            }
+        }
+    });
+
+    // If `opt_result` is `None`, we have only encoutered `default impl`s that don't contain the
+    // item. This is allowed, the item isn't actually getting specialized here.
+    let result = opt_result.unwrap_or(Ok(()));
+
+    if let Err(parent_impl) = result {
+        report_forbidden_specialization(tcx, impl_item, parent_impl);
+    }
 }
 
 fn check_impl_items_against_trait<'tcx>(
@@ -1846,8 +1882,7 @@ fn check_impl_items_against_trait<'tcx>(
     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(tcx, impl_id)
-            .defs(tcx, trait_item.ident, trait_item.kind, impl_trait_ref.def_id)
-            .next()
+            .leaf_def(tcx, trait_item.ident, trait_item.kind)
             .map(|node_item| !node_item.node.is_from_trait())
             .unwrap_or(false);
 
diff --git a/src/test/ui/specialization/auxiliary/cross_crates_defaults.rs b/src/test/ui/specialization/auxiliary/cross_crates_defaults.rs
index 5cf975b5752..1e5555355c3 100644
--- a/src/test/ui/specialization/auxiliary/cross_crates_defaults.rs
+++ b/src/test/ui/specialization/auxiliary/cross_crates_defaults.rs
@@ -22,7 +22,9 @@ pub trait Bar {
     fn bar(&self) -> i32 { 0 }
 }
 
-impl<T> Bar for T {} // use the provided method
+impl<T> Bar for T {
+    default fn bar(&self) -> i32 { 0 }
+}
 
 impl Bar for i32 {
     fn bar(&self) -> i32 { 1 }
diff --git a/src/test/ui/specialization/issue-36804.rs b/src/test/ui/specialization/issue-36804.rs
index 36cb939bc48..9546a5dd5f5 100644
--- a/src/test/ui/specialization/issue-36804.rs
+++ b/src/test/ui/specialization/issue-36804.rs
@@ -13,6 +13,10 @@ where
     fn next(&mut self) -> Option<T> {
         unimplemented!()
     }
+
+    default fn count(self) -> usize where Self: Sized {
+        self.fold(0, |cnt, _| cnt + 1)
+    }
 }
 
 impl<'a, I, T: 'a> Iterator for Cloned<I>
diff --git a/src/test/ui/specialization/non-defaulted-item-fail.rs b/src/test/ui/specialization/non-defaulted-item-fail.rs
new file mode 100644
index 00000000000..403f718d7dd
--- /dev/null
+++ b/src/test/ui/specialization/non-defaulted-item-fail.rs
@@ -0,0 +1,53 @@
+#![feature(specialization, associated_type_defaults)]
+
+// Test that attempting to override a non-default method or one not in the
+// parent impl causes an error.
+
+trait Foo {
+    type Ty = ();
+    const CONST: u8 = 123;
+    fn foo(&self) -> bool { true }
+}
+
+// Specialization tree for Foo:
+//
+//       Box<T>              Vec<T>
+//        / \                 / \
+// Box<i32>  Box<i64>   Vec<()>  Vec<bool>
+
+impl<T> Foo for Box<T> {
+    type Ty = bool;
+    const CONST: u8 = 0;
+    fn foo(&self) -> bool { false }
+}
+
+// Allowed
+impl Foo for Box<i32> {}
+
+// Can't override a non-`default` fn
+impl Foo for Box<i64> {
+    type Ty = Vec<()>;
+//~^ error: `Ty` specializes an item from a parent `impl`, but that item is not marked `default`
+    const CONST: u8 = 42;
+//~^ error: `CONST` specializes an item from a parent `impl`, but that item is not marked `default`
+    fn foo(&self) -> bool { true }
+//~^ error: `foo` specializes an item from a parent `impl`, but that item is not marked `default`
+}
+
+
+// Doesn't mention the item = provided body/value is used and the method is final.
+impl<T> Foo for Vec<T> {}
+
+// Allowed
+impl Foo for Vec<()> {}
+
+impl Foo for Vec<bool> {
+    type Ty = Vec<()>;
+//~^ error: `Ty` specializes an item from a parent `impl`, but that item is not marked `default`
+    const CONST: u8 = 42;
+//~^ error: `CONST` specializes an item from a parent `impl`, but that item is not marked `default`
+    fn foo(&self) -> bool { true }
+//~^ error: `foo` specializes an item from a parent `impl`, but that item is not marked `default`
+}
+
+fn main() {}
diff --git a/src/test/ui/specialization/non-defaulted-item-fail.stderr b/src/test/ui/specialization/non-defaulted-item-fail.stderr
new file mode 100644
index 00000000000..e6c5fc1441b
--- /dev/null
+++ b/src/test/ui/specialization/non-defaulted-item-fail.stderr
@@ -0,0 +1,81 @@
+error[E0520]: `Ty` specializes an item from a parent `impl`, but that item is not marked `default`
+  --> $DIR/non-defaulted-item-fail.rs:29:5
+   |
+LL | / impl<T> Foo for Box<T> {
+LL | |     type Ty = bool;
+LL | |     const CONST: u8 = 0;
+LL | |     fn foo(&self) -> bool { false }
+LL | | }
+   | |_- parent `impl` is here
+...
+LL |       type Ty = Vec<()>;
+   |       ^^^^^^^^^^^^^^^^^^ cannot specialize default item `Ty`
+   |
+   = note: to specialize, `Ty` in the parent `impl` must be marked `default`
+
+error[E0520]: `CONST` specializes an item from a parent `impl`, but that item is not marked `default`
+  --> $DIR/non-defaulted-item-fail.rs:31:5
+   |
+LL | / impl<T> Foo for Box<T> {
+LL | |     type Ty = bool;
+LL | |     const CONST: u8 = 0;
+LL | |     fn foo(&self) -> bool { false }
+LL | | }
+   | |_- parent `impl` is here
+...
+LL |       const CONST: u8 = 42;
+   |       ^^^^^^^^^^^^^^^^^^^^^ cannot specialize default item `CONST`
+   |
+   = note: to specialize, `CONST` in the parent `impl` must be marked `default`
+
+error[E0520]: `foo` specializes an item from a parent `impl`, but that item is not marked `default`
+  --> $DIR/non-defaulted-item-fail.rs:33:5
+   |
+LL | / impl<T> Foo for Box<T> {
+LL | |     type Ty = bool;
+LL | |     const CONST: u8 = 0;
+LL | |     fn foo(&self) -> bool { false }
+LL | | }
+   | |_- parent `impl` is here
+...
+LL |       fn foo(&self) -> bool { true }
+   |       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot specialize default item `foo`
+   |
+   = note: to specialize, `foo` in the parent `impl` must be marked `default`
+
+error[E0520]: `Ty` specializes an item from a parent `impl`, but that item is not marked `default`
+  --> $DIR/non-defaulted-item-fail.rs:45:5
+   |
+LL | impl<T> Foo for Vec<T> {}
+   | ------------------------- parent `impl` is here
+...
+LL |     type Ty = Vec<()>;
+   |     ^^^^^^^^^^^^^^^^^^ cannot specialize default item `Ty`
+   |
+   = note: to specialize, `Ty` in the parent `impl` must be marked `default`
+
+error[E0520]: `CONST` specializes an item from a parent `impl`, but that item is not marked `default`
+  --> $DIR/non-defaulted-item-fail.rs:47:5
+   |
+LL | impl<T> Foo for Vec<T> {}
+   | ------------------------- parent `impl` is here
+...
+LL |     const CONST: u8 = 42;
+   |     ^^^^^^^^^^^^^^^^^^^^^ cannot specialize default item `CONST`
+   |
+   = note: to specialize, `CONST` in the parent `impl` must be marked `default`
+
+error[E0520]: `foo` specializes an item from a parent `impl`, but that item is not marked `default`
+  --> $DIR/non-defaulted-item-fail.rs:49:5
+   |
+LL | impl<T> Foo for Vec<T> {}
+   | ------------------------- parent `impl` is here
+...
+LL |     fn foo(&self) -> bool { true }
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot specialize default item `foo`
+   |
+   = note: to specialize, `foo` in the parent `impl` must be marked `default`
+
+error: aborting due to 6 previous errors
+
+For more information about this error, try `rustc --explain E0520`.
diff --git a/src/test/ui/specialization/specialization-default-methods.rs b/src/test/ui/specialization/specialization-default-methods.rs
index 5d65a0457e7..9ae3d1e9f39 100644
--- a/src/test/ui/specialization/specialization-default-methods.rs
+++ b/src/test/ui/specialization/specialization-default-methods.rs
@@ -55,8 +55,9 @@ trait Bar {
 //                   /  \
 //            Vec<i32>  $Vec<i64>
 
-// use the provided method
-impl<T> Bar for T {}
+impl<T> Bar for T {
+    default fn bar(&self) -> i32 { 0 }
+}
 
 impl Bar for i32 {
     fn bar(&self) -> i32 { 1 }