Implementing type cast with itables

[oovm]

I want to do something similar to the following Java code in wasm.

abstract class Animal {}
interface Say {
    void say();
}
interface Swim {
    boolean swim();
}
class Cat extends Animal implements Say {
    @Override
    public void say() {
        System.out.println("Meow!");
    }
}
class Dog extends Animal implements Say, Swim {
    @Override
    public void say() {
        System.out.println("Woof!");
    }
    @Override
    public boolean swim() {
        return true;
    }
}
class Fish extends Animal implements Swim {
    @Override
    public boolean swim() {
        return true;
    }
}
public class Main {
    public static void listen(Animal animal) {
        if (animal instanceof Say) {
            ((Say) animal).say();
        }
    }
    public static void main(String[] args) {
        Animal cat = new Cat();
        Animal dog = new Dog();
        Animal fish = new Fish();

        listen(cat);
        listen(dog);
        listen(fish);
    }
}

I referred to the virtual table definition here and added the interface table: objects-and-method-tables

The base class and interface are defined as follows:

;; class Animal
(type $Animal (struct (ref $AnimalVTable) (ref $AnimalITables)))
(type $AnimalVTable (struct))
(type $AnimalITables (struct))

;; interface Say
(type $Say (struct (ref null) (ref $SayITables)))
(type $SayITables (struct (ref $SayVTable)))
(type $SayVTable (struct (ref $say_func)))
(type $say_func (func (param (ref $Say))))

;; interface Swim
(type $Swim (struct (ref null) (ref $SwimITables)))
(type $SwimITables (struct (ref $SwimVTable)))
(type $SwimVTable (struct (ref $swim_func)))
(type $swim_func (func (param (ref $Swim))))

Then I defined the subclass:

;; Cat
(type $Cat (struct (ref $CatVTable) (ref $CatITables)))
(type $CatVTable (struct))
(type $CatITables (struct (ref $SayVTable)))

;; Dog
(type $Dog (struct (ref $DogVTable) (ref $DogITables)))
(type $DogVTable (struct))
(type $DogITables (struct (ref $SayVTable) (ref $SwimVTable)))

But I found that I couldn't simply promote the subclass object to the interface object.

Each interface object is required to put its own virtual table object in the itable first.

In this struct layout, Dog can be transformed into Say, but cannot be transformed into Swim.

Animal dog = new Dog(); // ok
((Say) dog).say() // Invoke 1, 0
((Swim) dog).swim() // Invoke index not right

This means that the type conversion chain of Dog -> Animal -> Swim cannot be implemented.

How should I improve my compiler(or struct layout) to solve this problem?

[sjrd]

I suggest you look at the technical documentation of the Scala.js Wasm emitter here:
https://github.com/scala-js/scala-js/blob/main/linker/shared/src/main/scala/org/scalajs/linker/backend/wasmemitter/README.md#basic-structure
and here:
https://github.com/scala-js/scala-js/blob/main/linker/shared/src/main/scala/org/scalajs/linker/backend/wasmemitter/README.md#itables-and-interface-method-calls
as well as the method that generates code for interface type tests here:
https://github.com/scala-js/scala-js/blob/d3a5b0aed7434c6e9ac4e71ab01b8ea56e2a55a3/linker/shared/src/main/scala/org/scalajs/linker/backend/wasmemitter/ClassEmitter.scala#L488
in particular this section:
https://github.com/scala-js/scala-js/blob/d3a5b0aed7434c6e9ac4e71ab01b8ea56e2a55a3/linker/shared/src/main/scala/org/scalajs/linker/backend/wasmemitter/ClassEmitter.scala#L515-L534

Good luck.

[oovm]

I'm trying to understand this part.

The first part is a regular type check: anyref -?> Object -?> ClassX

(func $is_instance_of_X (param $expr (ref $Object)) (result i32)
  (block $test_fail (result i32)
    ;; If expr is not an instance of Object, return false
    (local.get $expr)
    (br_on_cast_fail $test_fail (ref null $Object))
    
    ;; Test whether the itable at the target interface's slot is an instance of the interface's itable struct type
    (local.get $expr)
    (struct.get $Object $itables)
    (struct.get $Object.Itables ${X.classInfo.itableIdx})
    (ref.test ${genTypeID.forITable(X.className)})
    (return)
    ;; Test fail, return false
    (block.return (i32.const 0)) 
  )
)

So the key lies in the structure of genTypeID.forITable

This is done by genGlobalClassItable

The generated instructions are roughly as follows

;; Initialize the interface table (itables) for this classX
(global $classXITable (mut (ref $Itables)) 
  (struct.new $X.Itables
    ;; order of mro
    (ref.func $resolvedMethodInfos.method1_1)
    (ref.func $resolvedMethodInfos.method1_2)
    (ref.func $resolvedMethodInfos.method2_1)
    (ref.func $resolvedMethodInfos.method2_2)
    ...
    ;; order of mro
    (struct.new ${genTypeID.forITable(ancestor1)})
    (struct.new ${genTypeID.forITable(ancestor2)})
    ...
  )
)

which means that itables are actually a complex tree structure

[sjrd]

It's not a tree with arbitrary nesting. There are always exactly 3 levels.

In vtables, there are always exactly 2 levels: instance -> vtable -> method pointer.
In itables, there are always exactly 3 levels: instance -> itables -> intf slot -> method pointer.

[oovm]

I misjudged that struct.new which emits by empty class, itables are indeed flat.

[oovm]

I am thinking whether we can use a global downcast table structure.

For example, for code like this

sealed trait Animal
case class Dog(name: String) extends Animal
case class Cat(name: String) extends Animal
case class Fish() extends Animal

def sound(animal: Animal): String = {
  var name = ""
  animal match {
    case dog: Dog =>
      println("Woof!")
      name = dog.name
    case cat: Cat =>
      println("Meow!")
      name = cat.name
    case _: Fish =>
      println("What?")
  }
  name
}

When compiling, istanceof is not available, but a secondary dispatch table is used

The following relationship is defined:

trait AnyObject {
  def downcast(visitor: GlobalDowncast): Unit
}
trait GlobalDowncast {
  def downcastDog(dog: Dog): Unit = {
    downcastElse()
  }

  def downcastCat(cat: Cat): Unit = {
    downcastElse()
  }

  def downcastFish(fish: Fish): Unit = {
    downcastElse()
  }

  def downcastElse(): Unit = {}
}

Make all classes support secondary dispatch

trait Animal extends AnyObject {}

case class Dog(name: String) extends Animal {
  override def downcast(visitor: GlobalDowncast): Unit = {
    visitor.downcastDog(this)
  }
}

case class Cat(name: String) extends Animal {
  override def downcast(visitor: GlobalDowncast): Unit = {
    visitor.downcastCat(this)
  }
}

case class Fish(name: String) extends Animal {
  override def downcast(visitor: GlobalDowncast): Unit = {
    visitor.downcastFish(this)
  }
}

Finally, a local stack is generated at the call point and secondary dispatch is performed.

case class SoundContext(name: String) extends GlobalDowncast {
  override def downcastDog(dog: Dog): Unit = {
    name = dog.name
    println("Woof!")
  }

  override def downcastCat(cat: Cat): Unit = {
    name = cat.name
    println("Meow!")
  }

  override def downcastElse(): Unit = {
    println("What?")
  }
}

def sound(animal: Animal): String= {
  val ctx = SoundContext("")
  animal.downcast(ctx)
  ctx.name
}

@main
def main(): Unit = {
  val dog = Dog("nana")
  val cat = Cat("nvnv")
  val fish = Fish("fish")

  sound(dog)
  sound(cat)
  sound(fish)
}

In the actual program, GlobalDowncast is a very large global array/table, and each local context will instantiate and replace the part of it equal to the number of branches.

The actual query time is constant.

I am not sure how runtime will execute ref.test and ref.cast for deeply nested structures.

I want to know whether the execution time of ref.test is constant, regardless of the complexity of the structure.

[tlively]

ref.test and ref.cast should be constant time operations. Engines track a vector of supertypes for each type, then when casting a value of type t1 to t2, they can use the difference in number of supertypes to get a relative depth, then use that relative depth as an index into t1's vector of supertypes to check in constant time whether t2 is a supertype of t1.

[sjrd]

The solution you're proposing here is basically to hide itables interface slots behind virtual method calls. That is strictly worse than the 3 indirections of itables, since now you have an additional indirect function call.