Dynamic dispatch with supertraits

gcc/rust/ChangeLog:

	* backend/rust-compile.cc:
	Modify compute_address_for_trait_item to support supertraits
	* typecheck/rust-tyty.cc:
	Remove auto

gcc/testsuite/ChangeLog:

	* rust/compile/trait13.rs:
	Add test for supertraits of supertraits
	* rust/compile/trait14.rs:
	Diamond problem with supertraits test
	* rust/execute/torture/trait14.rs:
	Add test for dynamic dispatch with supertraits
	* rust/execute/torture/trait15.rs:
	Add test for dynamic dispatch with generics
	* rust/execute/torture/trait16.rs:
	Add test for dynamic dispatch with lifetime params 1
	* rust/execute/torture/trait17.rs:
	Add test for dynamic dispatch with lifetime params 2
	* rust/execute/torture/trait18.rs:
	Add test for default implementations with dynamic dispatch and
	supertraits

Signed-off-by: Liam Naddell <liam.naddell@mail.utoronto.ca>

9 files changed, 420 insertions, 73 deletions

diff --git a/gcc/rust/backend/rust-compile.cc b/gcc/rust/backend/rust-compile.cc
index 82313a5..c67f9d6 100644
--- a/gcc/rust/backend/rust-compile.cc
+++ b/gcc/rust/backend/rust-compile.cc
@@ -241,100 +241,84 @@ HIRCompileBase::compute_address_for_trait_item (
     &receiver_bounds,
   const TyTy::BaseType *receiver, const TyTy::BaseType *root, location_t locus)
 {
-  // There are two cases here one where its an item which has an implementation
-  // within a trait-impl-block. Then there is the case where there is a default
-  // implementation for this within the trait.
-  //
-  // The awkward part here is that this might be a generic trait and we need to
-  // figure out the correct monomorphized type for this so we can resolve the
-  // address of the function , this is stored as part of the
-  // type-bound-predicate
-  //
-  // Algo:
-  // check if there is an impl-item for this trait-item-ref first
-  // else assert that the trait-item-ref has an implementation
-  //
-  // FIXME this does not support super traits
-
   TyTy::TypeBoundPredicateItem predicate_item
     = predicate->lookup_associated_item (ref->get_identifier ());
   rust_assert (!predicate_item.is_error ());
 
-  // this is the expected end type
+  // This is the expected end type
   TyTy::BaseType *trait_item_type = predicate_item.get_tyty_for_receiver (root);
   rust_assert (trait_item_type->get_kind () == TyTy::TypeKind::FNDEF);
   TyTy::FnType *trait_item_fntype
     = static_cast<TyTy::FnType *> (trait_item_type);
 
-  // find impl-block for this trait-item-ref
-  HIR::ImplBlock *associated_impl_block = nullptr;
-  const Resolver::TraitReference *predicate_trait_ref = predicate->get ();
+  // Loop through the list of trait references and impls that we satisfy.
+  // We are looking for one that has an implementation for "ref", a trait
+  // item.
   for (auto &item : receiver_bounds)
     {
-      Resolver::TraitReference *trait_ref = item.first;
       HIR::ImplBlock *impl_block = item.second;
-      if (predicate_trait_ref->is_equal (*trait_ref))
+      rust_assert (impl_block != nullptr);
+
+      // Lookup type for potentially associated impl.
+      std::unique_ptr<HIR::Type> &self_type_path = impl_block->get_type ();
+
+      // Checks for empty impl blocks, triggered by Sized trait.
+      if (self_type_path == nullptr)
+	continue;
+
+      // Convert HIR::Type to TyTy::BaseType
+      TyTy::BaseType *self = nullptr;
+      bool ok = ctx->get_tyctx ()->lookup_type (
+	self_type_path->get_mappings ().get_hirid (), &self);
+
+      rust_assert (ok);
+
+      // Look through the relevant bounds on our type, and find which one our
+      // impl block satisfies
+      TyTy::TypeBoundPredicate *self_bound = nullptr;
+      for (auto &bound : self->get_specified_bounds ())
 	{
-	  associated_impl_block = impl_block;
-	  break;
+	  const Resolver::TraitReference *bound_ref = bound.get ();
+	  const Resolver::TraitReference *specified_ref = predicate->get ();
+	  // If this impl is for one of our types or supertypes
+	  if (specified_ref->satisfies_bound (*bound_ref))
+	    {
+	      self_bound = &bound;
+	      break;
+	    }
 	}
-    }
 
-  // FIXME this probably should just return error_mark_node but this helps
-  // debug for now since we are wrongly returning early on type-resolution
-  // failures, until we take advantage of more error types and error_mark_node
-  rust_assert (associated_impl_block != nullptr);
-
-  // lookup self for the associated impl
-  std::unique_ptr<HIR::Type> &self_type_path
-    = associated_impl_block->get_type ();
-  TyTy::BaseType *self = nullptr;
-  bool ok = ctx->get_tyctx ()->lookup_type (
-    self_type_path->get_mappings ().get_hirid (), &self);
-  rust_assert (ok);
-
-  // lookup the predicate item from the self
-  TyTy::TypeBoundPredicate *self_bound = nullptr;
-  for (auto &bound : self->get_specified_bounds ())
-    {
-      const Resolver::TraitReference *bound_ref = bound.get ();
-      const Resolver::TraitReference *specified_ref = predicate->get ();
-      if (bound_ref->is_equal (*specified_ref))
+      // This impl block doesn't help us
+      if (self_bound == nullptr)
+	continue;
+
+      // Find the specific function in the impl block that matches "ref".
+      // This is the one we want to compute the address for.
+      HIR::Function *associated_function = nullptr;
+      for (auto &impl_item : impl_block->get_impl_items ())
 	{
-	  self_bound = &bound;
-	  break;
+	  bool is_function = impl_item->get_impl_item_type ()
+			     == HIR::ImplItem::ImplItemType::FUNCTION;
+	  if (!is_function)
+	    continue;
+
+	  HIR::Function *fn = static_cast<HIR::Function *> (impl_item.get ());
+	  bool found_associated_item
+	    = fn->get_function_name ().as_string ().compare (
+		ref->get_identifier ())
+	      == 0;
+	  if (found_associated_item)
+	    associated_function = fn;
 	}
-    }
-  rust_assert (self_bound != nullptr);
-
-  // lookup the associated item from the associated impl block
-  TyTy::TypeBoundPredicateItem associated_self_item
-    = self_bound->lookup_associated_item (ref->get_identifier ());
-  rust_assert (!associated_self_item.is_error ());
 
-  // Lookup the impl-block for the associated impl_item if it exists
-  HIR::Function *associated_function = nullptr;
-  for (auto &impl_item : associated_impl_block->get_impl_items ())
-    {
-      bool is_function = impl_item->get_impl_item_type ()
-			 == HIR::ImplItem::ImplItemType::FUNCTION;
-      if (!is_function)
+      // This impl block satisfies the bound, but doesn't contain the relevant
+      // function. This could happen because of supertraits.
+      if (associated_function == nullptr)
 	continue;
 
-      HIR::Function *fn = static_cast<HIR::Function *> (impl_item.get ());
-      bool found_associated_item
-	= fn->get_function_name ().as_string ().compare (ref->get_identifier ())
-	  == 0;
-      if (found_associated_item)
-	associated_function = fn;
-    }
-
-  // we found an impl_item for this
-  if (associated_function != nullptr)
-    {
       // lookup the associated type for this item
       TyTy::BaseType *lookup = nullptr;
-      bool ok = ctx->get_tyctx ()->lookup_type (
+      ok = ctx->get_tyctx ()->lookup_type (
 	associated_function->get_mappings ().get_hirid (), &lookup);
       rust_assert (ok);
       rust_assert (lookup->get_kind () == TyTy::TypeKind::FNDEF);
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index 7b17231..a122230 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -3792,7 +3792,7 @@ DynamicObjectType::get_object_items () const
   std::vector<
     std::pair<const Resolver::TraitItemReference *, const TypeBoundPredicate *>>
     items;
-  for (auto &bound : get_specified_bounds ())
+  for (const TypeBoundPredicate &bound : get_specified_bounds ())
     {
       const Resolver::TraitReference *trait = bound.get ();
       std::vector<const Resolver::TraitItemReference *> trait_items;
diff --git a/gcc/testsuite/rust/compile/trait13.rs b/gcc/testsuite/rust/compile/trait13.rs
new file mode 100644
index 0000000..af5f5a6
--- /dev/null
+++ b/gcc/testsuite/rust/compile/trait13.rs
@@ -0,0 +1,47 @@
+// Testing multiple supertraits and calling supertrait methods
+
+struct Foo {
+    my_int: u32,
+}
+
+trait GrandParent {
+    fn grandparent(&self) -> u32;
+}
+
+trait Parent : GrandParent {
+    fn parent(&self) -> bool;
+}
+
+trait Child : Parent {
+    fn child(&self);
+}
+
+impl GrandParent for Foo {
+    fn grandparent(&self) -> u32 {
+        self.my_int
+    }
+}
+
+impl Parent for Foo {
+    fn parent(&self) -> bool {
+        // Call supertrait method
+        return self.grandparent() != 0;
+    }
+}
+
+impl Child for Foo {
+    fn child(&self) {
+        let _ = self;
+    }
+}
+
+pub fn main() {
+    let a = Foo{my_int: 0xfeedf00d};
+    let b: &dyn Child = &a;
+
+    b.parent();
+    b.child();
+
+    // Here to silence bogus compiler warning
+    let _ = a.my_int;
+}
diff --git a/gcc/testsuite/rust/compile/trait14.rs b/gcc/testsuite/rust/compile/trait14.rs
new file mode 100644
index 0000000..c1d42b5
--- /dev/null
+++ b/gcc/testsuite/rust/compile/trait14.rs
@@ -0,0 +1,51 @@
+// Testing diamond problem with supertraits
+
+ 
+struct Foo {
+    my_int: u32,
+}
+
+trait GrandParent {
+    fn grandparent(&self);
+}
+
+trait Parent1 : GrandParent {
+    fn parent1(&self);
+}
+
+trait Parent2 : GrandParent {
+    fn parent2(&self);
+}
+
+trait Child : Parent1+Parent2 {
+    fn child(&self);
+}
+
+impl GrandParent for Foo {
+    fn grandparent(&self) { let _ = self; }
+}
+
+impl Parent1 for Foo {
+    fn parent1(&self) { let _ = self; }
+}
+
+impl Parent2 for Foo {
+    fn parent2(&self) { let _ = self; }
+}
+
+impl Child for Foo {
+    fn child(&self) {
+        let _ = self;
+    }
+}
+
+pub fn main() {
+    let a = Foo{my_int: 0xf00dfeed};
+    let b: &dyn Child = &a;
+
+    b.parent1();
+    b.child();
+
+    // Suppress bogus compile warning
+    let _ = a.my_int;
+}
diff --git a/gcc/testsuite/rust/execute/torture/trait14.rs b/gcc/testsuite/rust/execute/torture/trait14.rs
new file mode 100644
index 0000000..759950e
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/trait14.rs
@@ -0,0 +1,47 @@
+/* { dg-output "parent123\r*\nchild\r*\n" } */
+
+extern "C" {
+    fn printf(s: *const i8, ...);
+}
+ 
+#[lang = "sized"]
+pub trait Sized {}
+
+struct Foo(i32);
+trait Parent {
+    fn parent(&self);
+}
+
+trait Child : Parent {
+    fn child(&self);
+}
+
+impl Parent for Foo {
+    fn parent(&self) {
+        unsafe {
+            let parent = "parent%i\n\0";
+            let msg = parent as *const str;
+            printf(msg as *const i8,self.0);
+        }
+    }
+}
+
+impl Child for Foo {
+    fn child(&self) {
+        let _ = self;
+        unsafe {
+            let child = "child\n\0";
+            let msg = child as *const str;
+            printf(msg as *const i8);
+        }
+    }
+}
+
+pub fn main() -> i32 {
+    let a = Foo(123);
+    let b: &dyn Child = &a;
+
+    b.parent();
+    b.child();
+    0
+}
diff --git a/gcc/testsuite/rust/execute/torture/trait15.rs b/gcc/testsuite/rust/execute/torture/trait15.rs
new file mode 100644
index 0000000..53469d7
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/trait15.rs
@@ -0,0 +1,56 @@
+/* { dg-output "parent123\r*\nchild\r*\n" } */
+// Testing generics passing with supertraits
+
+extern "C" {
+    fn printf(s: *const i8, ...);
+}
+ 
+#[lang = "sized"]
+pub trait Sized {}
+
+struct Foo {
+    my_int: u32,
+}
+
+trait Parent<T> {
+    fn parent(&self) -> T;
+}
+
+trait Child<T> : Parent<T> {
+    fn child(&self);
+}
+
+impl Parent<u32> for Foo {
+    fn parent(&self) -> u32 {
+        unsafe {
+            let parent = "parent%i\n\0";
+            let msg = parent as *const str;
+            printf(msg as *const i8,self.my_int);
+            return self.my_int;
+        }
+    }
+}
+
+impl Child<u32> for Foo {
+    fn child(&self) {
+        let _ = self;
+        unsafe {
+            let child = "child\n\0";
+            let msg = child as *const str;
+            printf(msg as *const i8);
+        }
+    }
+}
+
+pub fn main() -> i32 {
+    let a = Foo{my_int: 123};
+    let b: &dyn Child<u32> = &a;
+
+    b.parent();
+    b.child();
+
+    //Silence bogus warning
+    let _ = a.my_int;
+    
+    0
+}
diff --git a/gcc/testsuite/rust/execute/torture/trait16.rs b/gcc/testsuite/rust/execute/torture/trait16.rs
new file mode 100644
index 0000000..95f48a1
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/trait16.rs
@@ -0,0 +1,52 @@
+/* { dg-output "parent123\r*\nchild\r*\n" } */
+//Testing lifetimes with supertraits
+
+extern "C" {
+    fn printf(s: *const i8, ...);
+}
+ 
+struct Foo {
+    my_int: u32,
+}
+
+trait Parent {
+    fn parent(&self);
+}
+
+trait Child : Parent {
+    fn child(&self);
+}
+
+impl Parent for Foo {
+    fn parent(&self) {
+        unsafe {
+            let parent = "parent%i\n\0";
+            let msg = parent as *const str;
+            printf(msg as *const i8,self.my_int);
+            return;
+        }
+    }
+}
+
+impl Child for Foo {
+    fn child<'a>(&self) {
+        let _ = self;
+        unsafe {
+            let child = "child\n\0";
+            let msg = child as *const str;
+            printf(msg as *const i8);
+        }
+    }
+}
+
+pub fn main() -> i32 {
+    let a = Foo{ my_int: 123};
+    let b: &dyn Child = &a;
+
+    b.parent();
+    b.child();
+
+    let _ = a.my_int;
+
+    0
+}
diff --git a/gcc/testsuite/rust/execute/torture/trait17.rs b/gcc/testsuite/rust/execute/torture/trait17.rs
new file mode 100644
index 0000000..a619ef8
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/trait17.rs
@@ -0,0 +1,54 @@
+/* { dg-output "parent123\r*\nchild\r*\n" } */
+
+//Second test for lifetimes in supertraits
+
+extern "C" {
+    fn printf(s: *const i8, ...);
+}
+ 
+struct Foo {
+    my_int: u32,
+}
+
+trait Parent {
+    fn parent(&self);
+}
+
+trait Child : Parent {
+    fn child(&self);
+}
+
+impl Parent for Foo {
+    fn parent<'b>(&self) {
+        unsafe {
+            let parent = "parent%i\n\0";
+            let msg = parent as *const str;
+            printf(msg as *const i8,self.my_int);
+            return;
+        }
+    }
+}
+
+impl Child for Foo {
+    fn child(&self) {
+        let _ = self;
+        unsafe {
+            let child = "child\n\0";
+            let msg = child as *const str;
+            printf(msg as *const i8);
+        }
+    }
+}
+
+pub fn main() -> i32 {
+    let a = Foo{ my_int: 123};
+    let b: &dyn Child = &a;
+
+    b.parent();
+    b.child();
+
+    // Silence bogus warning
+    let _ = a.my_int;
+
+    0
+}
diff --git a/gcc/testsuite/rust/execute/torture/trait18.rs b/gcc/testsuite/rust/execute/torture/trait18.rs
new file mode 100644
index 0000000..46024d8
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/trait18.rs
@@ -0,0 +1,56 @@
+/* { dg-output "parent\r*\nchild\r*\n" } */
+//Testing default implementations with supertraits.
+
+extern "C" {
+    fn printf(s: *const i8, ...);
+}
+ 
+struct Foo {
+    my_int: u32,
+}
+
+trait Parent {
+    fn parent_str(&self) -> &'static str;
+    fn parent(&self) {
+        unsafe {
+            let parent: &'static str = self.parent_str();
+            let msg = parent as *const str;
+            printf(msg as *const i8);
+        }
+    }
+}
+
+trait Child : Parent {
+    fn child(&self);
+}
+
+impl Parent for Foo {
+    fn parent_str(&self) -> &'static str {
+        let _ = self;
+        return "parent\n\0";
+    }
+}
+
+impl Child for Foo {
+    fn child(&self) {
+        let _ = self;
+        unsafe {
+            let child = "child\n\0";
+            let msg = child as *const str;
+            printf(msg as *const i8);
+        }
+    }
+}
+
+pub fn main() -> i32 {
+    let a = Foo{ my_int: 0xfeedf00d};
+    let b: &dyn Child = &a;
+
+    b.parent();
+    b.child();
+
+    // Bogus warning silencer
+    let _ = a.my_int;
+
+    0
+}