ART: Add interface class join heuristic

Do not treat interfaces as regular classes. This will always
lead to a join of java.lang.Object, rejecting semantically
valid programs.

We want to retain IMT dispatch, forcing us to verify interface
assigment. In the absence of set types, the result is ambiguous
and not well defined. In a best effort, attempt to find a joint
interface by walking the interface tables of the join arguments
backwards.

In the case of two non-interface classes, we still prefer the
class hierarchy.

Bug: 69826014
Test: m test-art-host-gtest-reg_type_test
Change-Id: I7e0086f045e5bb2a7c3ee3464de45fc5b02f4d3f

4 files changed, 100 insertions, 0 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 5c7ec81ce1..6ec09fcd7b 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -243,6 +243,7 @@ ART_GTEST_verifier_deps_test_DEX_DEPS := VerifierDeps VerifierDepsMulti MultiDex
 ART_GTEST_dex_to_dex_decompiler_test_DEX_DEPS := VerifierDeps DexToDexDecompiler
 ART_GTEST_oatdump_app_test_DEX_DEPS := ProfileTestMultiDex
 ART_GTEST_oatdump_test_DEX_DEPS := ProfileTestMultiDex
+ART_GTEST_reg_type_test_DEX_DEPS := Interfaces
 
 # The elf writer test has dependencies on core.oat.
 ART_GTEST_elf_writer_test_HOST_DEPS := $(HOST_CORE_IMAGE_DEFAULT_64) $(HOST_CORE_IMAGE_DEFAULT_32)
diff --git a/runtime/verifier/reg_type.cc b/runtime/verifier/reg_type.cc
index b0ea514e2a..c8ef80f95d 100644
--- a/runtime/verifier/reg_type.cc
+++ b/runtime/verifier/reg_type.cc
@@ -608,6 +608,9 @@ namespace {
 ObjPtr<mirror::Class> ArrayClassJoin(ObjPtr<mirror::Class> s, ObjPtr<mirror::Class> t)
     REQUIRES_SHARED(Locks::mutator_lock_);
 
+ObjPtr<mirror::Class> InterfaceClassJoin(ObjPtr<mirror::Class> s, ObjPtr<mirror::Class> t)
+    REQUIRES_SHARED(Locks::mutator_lock_);
+
 /*
  * A basic Join operation on classes. For a pair of types S and T the Join, written S v T = J, is
  * S <: J, T <: J and for-all U such that S <: U, T <: U then J <: U. That is J is the parent of
@@ -640,6 +643,8 @@ ObjPtr<mirror::Class> ClassJoin(ObjPtr<mirror::Class> s, ObjPtr<mirror::Class> t
     return t;
   } else if (s->IsArrayClass() && t->IsArrayClass()) {
     return ArrayClassJoin(s, t);
+  } else if (s->IsInterface() || t->IsInterface()) {
+    return InterfaceClassJoin(s, t);
   } else {
     size_t s_depth = s->Depth();
     size_t t_depth = t->Depth();
@@ -690,6 +695,48 @@ ObjPtr<mirror::Class> ArrayClassJoin(ObjPtr<mirror::Class> s, ObjPtr<mirror::Cla
   return array_class;
 }
 
+ObjPtr<mirror::Class> InterfaceClassJoin(ObjPtr<mirror::Class> s, ObjPtr<mirror::Class> t) {
+  // This is expensive, as we do not have good data structures to do this even halfway
+  // efficiently.
+  //
+  // We're not following JVMS for interface verification (not everything is assignable to an
+  // interface, we trade this for IMT dispatch). We also don't have set types to make up for
+  // it. So we choose one arbitrary common ancestor interface by walking the interface tables
+  // backwards.
+  //
+  // For comparison, runtimes following the JVMS will punt all interface type checking to
+  // runtime.
+  ObjPtr<mirror::IfTable> s_if = s->GetIfTable();
+  int32_t s_if_count = s->GetIfTableCount();
+  ObjPtr<mirror::IfTable> t_if = t->GetIfTable();
+  int32_t t_if_count = t->GetIfTableCount();
+
+  // Note: we'll be using index == count to stand for the argument itself.
+  for (int32_t s_it = s_if_count; s_it >= 0; --s_it) {
+    ObjPtr<mirror::Class> s_cl = s_it == s_if_count ? s : s_if->GetInterface(s_it);
+    if (!s_cl->IsInterface()) {
+      continue;
+    }
+
+    for (int32_t t_it = t_if_count; t_it >= 0; --t_it) {
+      ObjPtr<mirror::Class> t_cl = t_it == t_if_count ? t : t_if->GetInterface(t_it);
+      if (!t_cl->IsInterface()) {
+        continue;
+      }
+
+      if (s_cl == t_cl) {
+        // Found something arbitrary in common.
+        return s_cl;
+      }
+    }
+  }
+
+  // Return java.lang.Object.
+  ObjPtr<mirror::Class> obj_class = s->IsInterface() ? s->GetSuperClass() : t->GetSuperClass();
+  DCHECK(obj_class->IsObjectClass());
+  return obj_class;
+}
+
 }  // namespace
 
 const RegType& RegType::Merge(const RegType& incoming_type,
diff --git a/runtime/verifier/reg_type_test.cc b/runtime/verifier/reg_type_test.cc
index 32243857f8..e8ee454af5 100644
--- a/runtime/verifier/reg_type_test.cc
+++ b/runtime/verifier/reg_type_test.cc
@@ -1094,5 +1094,55 @@ TEST_F(RegTypeOOMTest, ClassJoinOOM) {
   Runtime::Current()->GetHeap()->DecrementDisableMovingGC(soa.Self());
 }
 
+class RegTypeClassJoinTest : public RegTypeTest {
+ protected:
+  void TestClassJoin(const char* in1, const char* in2, const char* out) {
+    ArenaStack stack(Runtime::Current()->GetArenaPool());
+    ScopedArenaAllocator allocator(&stack);
+
+    ScopedObjectAccess soa(Thread::Current());
+    jobject jclass_loader = LoadDex("Interfaces");
+    StackHandleScope<4> hs(soa.Self());
+    Handle<mirror::ClassLoader> class_loader(
+        hs.NewHandle(soa.Decode<mirror::ClassLoader>(jclass_loader)));
+
+    Handle<mirror::Class> c1(hs.NewHandle(
+        class_linker_->FindClass(soa.Self(), in1, class_loader)));
+    Handle<mirror::Class> c2(hs.NewHandle(
+        class_linker_->FindClass(soa.Self(), in2, class_loader)));
+    ASSERT_TRUE(c1 != nullptr);
+    ASSERT_TRUE(c2 != nullptr);
+
+    // We cannot allow moving GC. Otherwise we'd have to ensure the reg types are updated (reference
+    // reg types store a class pointer in a GCRoot, which is normally updated through active
+    // verifiers being registered with their thread), which is unnecessarily complex.
+    Runtime::Current()->GetHeap()->IncrementDisableMovingGC(soa.Self());
+
+    RegTypeCache cache(true, allocator);
+    const RegType& c1_reg_type = *cache.InsertClass(in1, c1.Get(), false);
+    const RegType& c2_reg_type = *cache.InsertClass(in2, c2.Get(), false);
+
+    const RegType& join_type = c1_reg_type.Merge(c2_reg_type, &cache, nullptr);
+    EXPECT_TRUE(join_type.HasClass());
+    EXPECT_EQ(join_type.GetDescriptor(), std::string_view(out));
+
+    Runtime::Current()->GetHeap()->DecrementDisableMovingGC(soa.Self());
+  }
+};
+
+TEST_F(RegTypeClassJoinTest, ClassJoinInterfaces) {
+  TestClassJoin("LInterfaces$K;", "LInterfaces$L;", "LInterfaces$J;");
+}
+
+TEST_F(RegTypeClassJoinTest, ClassJoinInterfaceClass) {
+  TestClassJoin("LInterfaces$B;", "LInterfaces$L;", "LInterfaces$J;");
+}
+
+TEST_F(RegTypeClassJoinTest, ClassJoinClassClass) {
+  // This test codifies that we prefer the class hierarchy over interfaces. It's a mostly
+  // arbitrary choice, optimally we'd have set types and could handle multi-inheritance precisely.
+  TestClassJoin("LInterfaces$A;", "LInterfaces$B;", "Ljava/lang/Object;");
+}
+
 }  // namespace verifier
 }  // namespace art
diff --git a/test/Interfaces/Interfaces.java b/test/Interfaces/Interfaces.java
index db602534d8..6290e7c19f 100644
--- a/test/Interfaces/Interfaces.java
+++ b/test/Interfaces/Interfaces.java
@@ -26,6 +26,8 @@ class Interfaces {
     interface K extends J {
         public void k();
     }
+    interface L extends I, J {
+    }
     class A implements I, J {
         public void i() {};
         public void j1() {};