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
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 5c7ec81..6ec09fc 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -243,6 +243,7 @@
 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 b0ea514..c8ef80f 100644
--- a/runtime/verifier/reg_type.cc
+++ b/runtime/verifier/reg_type.cc
@@ -608,6 +608,9 @@
 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 @@
     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 @@
   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 3224385..e8ee454 100644
--- a/runtime/verifier/reg_type_test.cc
+++ b/runtime/verifier/reg_type_test.cc
@@ -1094,5 +1094,55 @@
   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 db60253..6290e7c 100644
--- a/test/Interfaces/Interfaces.java
+++ b/test/Interfaces/Interfaces.java
@@ -26,6 +26,8 @@
     interface K extends J {
         public void k();
     }
+    interface L extends I, J {
+    }
     class A implements I, J {
         public void i() {};
         public void j1() {};