Auto merge of #86461 - crlf0710:rich_vtable, r=nikomatsakis

Refactor vtable format for upcoming trait_upcasting feature.

This modifies vtable format:
1. reordering occurrence order of methods coming from different traits
2. include `VPtr`s for supertraits where this vtable cannot be directly reused during trait upcasting.
Also, during codegen, the vtables corresponding to these newly included `VPtr` will be requested and generated.

For the cases where this vtable can directly used, now the super trait vtable has exactly the same content to some prefix of this one.

r? `@bjorn3`
cc `@RalfJung`
cc `@rust-lang/wg-traits`

8 files changed, 522 insertions, 0 deletions

diff --git a/src/test/ui/traits/vtable/vtable-diamond.rs b/src/test/ui/traits/vtable/vtable-diamond.rs
new file mode 100644
index 00000000000..f64ae95f1d4
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-diamond.rs
@@ -0,0 +1,39 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait B: A {
+    fn foo_b(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait C: A {
+    //~^ error Vtable
+    fn foo_c(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait D: B + C {
+    //~^ error Vtable
+    fn foo_d(&self) {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+impl C for S {}
+impl D for S {}
+
+fn foo(d: &dyn D) {
+    d.foo_d();
+}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-diamond.stderr b/src/test/ui/traits/vtable/vtable-diamond.stderr
new file mode 100644
index 00000000000..92a7f29536e
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-diamond.stderr
@@ -0,0 +1,35 @@
+error: Vtable entries for `<S as D>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as B>::foo_b),
+    Method(<S as C>::foo_c),
+    TraitVPtr(<S as C>),
+    Method(<S as D>::foo_d),
+]
+  --> $DIR/vtable-diamond.rs:21:1
+   |
+LL | / trait D: B + C {
+LL | |
+LL | |     fn foo_d(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as C>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as C>::foo_c),
+]
+  --> $DIR/vtable-diamond.rs:15:1
+   |
+LL | / trait C: A {
+LL | |
+LL | |     fn foo_c(&self) {}
+LL | | }
+   | |_^
+
+error: aborting due to 2 previous errors
+
diff --git a/src/test/ui/traits/vtable/vtable-multi-level.rs b/src/test/ui/traits/vtable/vtable-multi-level.rs
new file mode 100644
index 00000000000..33112b4eaaa
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multi-level.rs
@@ -0,0 +1,122 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+//   O --> G --> C --> A
+//     \     \     \-> B
+//     |     |-> F --> D
+//     |           \-> E
+//     |-> N --> J --> H
+//           \     \-> I
+//           |-> M --> K
+//                 \-> L
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait B {
+    //~^ error Vtable
+    fn foo_b(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait C: A + B {
+    fn foo_c(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait D {
+    //~^ error Vtable
+    fn foo_d(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait E {
+    //~^ error Vtable
+    fn foo_e(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait F: D + E {
+    //~^ error Vtable
+    fn foo_f(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait G: C + F {
+    fn foo_g(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait H {
+    //~^ error Vtable
+    fn foo_h(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait I {
+    //~^ error Vtable
+    fn foo_i(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait J: H + I {
+    //~^ error Vtable
+    fn foo_j(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait K {
+    //~^ error Vtable
+    fn foo_k(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait L {
+    //~^ error Vtable
+    fn foo_l(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait M: K + L {
+    //~^ error Vtable
+    fn foo_m(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait N: J + M {
+    //~^ error Vtable
+    fn foo_n(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait O: G + N {
+    //~^ error Vtable
+    fn foo_o(&self) {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+impl C for S {}
+impl D for S {}
+impl E for S {}
+impl F for S {}
+impl G for S {}
+impl H for S {}
+impl I for S {}
+impl J for S {}
+impl K for S {}
+impl L for S {}
+impl M for S {}
+impl N for S {}
+impl O for S {}
+
+fn foo(_: &dyn O) {}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-multi-level.stderr b/src/test/ui/traits/vtable/vtable-multi-level.stderr
new file mode 100644
index 00000000000..7700db98e0b
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multi-level.stderr
@@ -0,0 +1,214 @@
+error: Vtable entries for `<S as O>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as B>::foo_b),
+    TraitVPtr(<S as B>),
+    Method(<S as C>::foo_c),
+    Method(<S as D>::foo_d),
+    TraitVPtr(<S as D>),
+    Method(<S as E>::foo_e),
+    TraitVPtr(<S as E>),
+    Method(<S as F>::foo_f),
+    TraitVPtr(<S as F>),
+    Method(<S as G>::foo_g),
+    Method(<S as H>::foo_h),
+    TraitVPtr(<S as H>),
+    Method(<S as I>::foo_i),
+    TraitVPtr(<S as I>),
+    Method(<S as J>::foo_j),
+    TraitVPtr(<S as J>),
+    Method(<S as K>::foo_k),
+    TraitVPtr(<S as K>),
+    Method(<S as L>::foo_l),
+    TraitVPtr(<S as L>),
+    Method(<S as M>::foo_m),
+    TraitVPtr(<S as M>),
+    Method(<S as N>::foo_n),
+    TraitVPtr(<S as N>),
+    Method(<S as O>::foo_o),
+]
+  --> $DIR/vtable-multi-level.rs:95:1
+   |
+LL | / trait O: G + N {
+LL | |
+LL | |     fn foo_o(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as B>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as B>::foo_b),
+]
+  --> $DIR/vtable-multi-level.rs:19:1
+   |
+LL | / trait B {
+LL | |
+LL | |     fn foo_b(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as D>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as D>::foo_d),
+]
+  --> $DIR/vtable-multi-level.rs:30:1
+   |
+LL | / trait D {
+LL | |
+LL | |     fn foo_d(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as E>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as E>::foo_e),
+]
+  --> $DIR/vtable-multi-level.rs:36:1
+   |
+LL | / trait E {
+LL | |
+LL | |     fn foo_e(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as F>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as D>::foo_d),
+    Method(<S as E>::foo_e),
+    TraitVPtr(<S as E>),
+    Method(<S as F>::foo_f),
+]
+  --> $DIR/vtable-multi-level.rs:42:1
+   |
+LL | / trait F: D + E {
+LL | |
+LL | |     fn foo_f(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as H>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as H>::foo_h),
+]
+  --> $DIR/vtable-multi-level.rs:53:1
+   |
+LL | / trait H {
+LL | |
+LL | |     fn foo_h(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as I>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as I>::foo_i),
+]
+  --> $DIR/vtable-multi-level.rs:59:1
+   |
+LL | / trait I {
+LL | |
+LL | |     fn foo_i(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as J>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as H>::foo_h),
+    Method(<S as I>::foo_i),
+    TraitVPtr(<S as I>),
+    Method(<S as J>::foo_j),
+]
+  --> $DIR/vtable-multi-level.rs:65:1
+   |
+LL | / trait J: H + I {
+LL | |
+LL | |     fn foo_j(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as K>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as K>::foo_k),
+]
+  --> $DIR/vtable-multi-level.rs:71:1
+   |
+LL | / trait K {
+LL | |
+LL | |     fn foo_k(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as L>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as L>::foo_l),
+]
+  --> $DIR/vtable-multi-level.rs:77:1
+   |
+LL | / trait L {
+LL | |
+LL | |     fn foo_l(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as M>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as K>::foo_k),
+    Method(<S as L>::foo_l),
+    TraitVPtr(<S as L>),
+    Method(<S as M>::foo_m),
+]
+  --> $DIR/vtable-multi-level.rs:83:1
+   |
+LL | / trait M: K + L {
+LL | |
+LL | |     fn foo_m(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as N>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as H>::foo_h),
+    Method(<S as I>::foo_i),
+    TraitVPtr(<S as I>),
+    Method(<S as J>::foo_j),
+    Method(<S as K>::foo_k),
+    TraitVPtr(<S as K>),
+    Method(<S as L>::foo_l),
+    TraitVPtr(<S as L>),
+    Method(<S as M>::foo_m),
+    TraitVPtr(<S as M>),
+    Method(<S as N>::foo_n),
+]
+  --> $DIR/vtable-multi-level.rs:89:1
+   |
+LL | / trait N: J + M {
+LL | |
+LL | |     fn foo_n(&self) {}
+LL | | }
+   | |_^
+
+error: aborting due to 12 previous errors
+
diff --git a/src/test/ui/traits/vtable/vtable-multiple.rs b/src/test/ui/traits/vtable/vtable-multiple.rs
new file mode 100644
index 00000000000..cb0d0b72481
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multiple.rs
@@ -0,0 +1,31 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait B {
+    //~^ error Vtable
+    fn foo_b(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait C: A + B {
+    //~^ error Vtable
+    fn foo_c(&self) {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+impl C for S {}
+
+fn foo(c: &dyn C) {}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-multiple.stderr b/src/test/ui/traits/vtable/vtable-multiple.stderr
new file mode 100644
index 00000000000..f51b083de25
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multiple.stderr
@@ -0,0 +1,33 @@
+error: Vtable entries for `<S as C>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as B>::foo_b),
+    TraitVPtr(<S as B>),
+    Method(<S as C>::foo_c),
+]
+  --> $DIR/vtable-multiple.rs:16:1
+   |
+LL | / trait C: A + B {
+LL | |
+LL | |     fn foo_c(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as B>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as B>::foo_b),
+]
+  --> $DIR/vtable-multiple.rs:10:1
+   |
+LL | / trait B {
+LL | |
+LL | |     fn foo_b(&self) {}
+LL | | }
+   | |_^
+
+error: aborting due to 2 previous errors
+
diff --git a/src/test/ui/traits/vtable/vtable-vacant.rs b/src/test/ui/traits/vtable/vtable-vacant.rs
new file mode 100644
index 00000000000..ebea94171f2
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-vacant.rs
@@ -0,0 +1,28 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+// B --> A
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a1(&self) {}
+    fn foo_a2(&self) where Self: Sized {}
+}
+
+#[rustc_dump_vtable]
+trait B: A {
+    //~^ error Vtable
+    fn foo_b1(&self) {}
+    fn foo_b2() where Self: Sized {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+
+fn foo(_: &dyn B) {}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-vacant.stderr b/src/test/ui/traits/vtable/vtable-vacant.stderr
new file mode 100644
index 00000000000..768cca52689
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-vacant.stderr
@@ -0,0 +1,20 @@
+error: Vtable entries for `<S as B>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a1),
+    Vacant,
+    Method(<S as B>::foo_b1),
+    Vacant,
+]
+  --> $DIR/vtable-vacant.rs:13:1
+   |
+LL | / trait B: A {
+LL | |
+LL | |     fn foo_b1(&self) {}
+LL | |     fn foo_b2() where Self: Sized {}
+LL | | }
+   | |_^
+
+error: aborting due to previous error
+