8
$\begingroup$

Swift allows you to define extension methods on any type or protocol. While extension methods on protocols are frequently used to provide default implementations, only methods listed in the main protocol body can go in the vtable, since you can define an extension method from anywhere. Consider this code:

// module A
public protocol AProtocol {
  func getSomeNumber() -> Int
}

public struct ExampleImplementation: AProtocol {
  public func getSomeNumber() -> Int { 4 }
}

// module B
import A

extension AProtocol {
  public func getSomeText() -> String {
    getSomeNumber().description
  }
}

public func printThing(_ x: some AProtocol) {
  print(x.getSomeText())
}

// module C
import A
import B

struct ActualImplementation: AProtocol {
  func getSomeNumber() -> Int { 5 }
  func getSomeText() -> String { "five" }
}

let x = ActualImplementation()
print(x.getSomeText()) // static lookup finds ActualImplementation.getSomeText and prints "five"
printThing(x) // since getSomeText isn't defined in module A, it's not in the vtable
              // so this uses the implementation from the extension and prints "5"

C#'s extension methods are just syntax sugar for static method calls and are resolved at compile time, so the equivalent code would also demonstrate this behavior in C#. Both Swift and C# have a concept of ABI stability and allow libraries to be distributed in binary form, so compile-time templates are a non-starter for these languages.

How could extension methods be dynamically dispatched in a language that allows binary dependencies?

$\endgroup$
10
  • $\begingroup$ What do you mean by "binary dependencies"? Do you need a different solution than the one(s) that C# and Swift use? $\endgroup$
    – RubenVerg
    May 23, 2023 at 18:33
  • $\begingroup$ If a library is distributed in source, it may be possible to add these to the vtable at compile time, since the compiler will be able to see all extension methods at once. If module A is compiled as a binary dependency, however, it can’t know what extension methods its consumers may define. $\endgroup$
    – Bbrk24
    May 23, 2023 at 18:34
  • $\begingroup$ oh, right. somehow I interpreted "binary" as two-fold and not as compiled. I still can't tell if the C# and Swift solutions are fine and you are looking for alternatives, or if those are incompatible with your needs. $\endgroup$
    – RubenVerg
    May 23, 2023 at 18:40
  • $\begingroup$ I am specifically looking for something that allows dynamic dispatch of, in this case getSomeText(), even when module A and/or module B are binary dependencies — which is something Swift and C# can’t do. $\endgroup$
    – Bbrk24
    May 23, 2023 at 18:43
  • $\begingroup$ Is getSomeText() actually dispatched dynamically? It seems since it's implemented in terms of the underlying interface that it would be dispatched statically and only the call to getSomeNumber() would be dynamic. Or could it be overridden by other implementations of the protocol? $\endgroup$
    – chrysante
    May 23, 2023 at 18:53

2 Answers 2

6
$\begingroup$

Objective-C's solution

Objective-C is insane.

Background

You know, say, C# dynamic? How every method call needs to be dynamically dispatched because you have no idea what it is at compile time? Objective-C is like that. Due to things like method swizzling and runtime class registration, it's impossible to know what the implementation is at compile time even when you know the type and method name. All method calls compile down to a call to objc_msgSend(self, _cmd, ...) or one of its relatives.

Objective-C does dynamic dispatch of extension methods, just like we want! Apple's implementation is naturally closed-source, so let's look at GNUStep's implementation. methodForSelector: calls out to objc_msg_lookup. It has a lot of handling of various cases (e.g. the class object hasn't been initialized yet) but the core of it is just two lines:

    Class class = classForObject((*receiver));
    struct objc_slot2 * result = objc_dtable_lookup(class->dtable, selector->index);

What is a selector?

In Smalltalk and Objective-C, a selector is a representation of a method name. In Objective-C, the type of a selector is SEL, which is a pointer to an opaque struct. But we're looking at GNUStep -- we have an implementation of that struct! And what I found blew my mind:

struct objc_selector
{
    union
    {
        const char *name;
        uintptr_t index;
    };
    const char * types;
};

The first member of the struct is a C string containing the actual method name. I already knew that SEL stores the name somehow, so this much is not a surprise to me. But it's also an index into a sparse array! That objc_dtable_lookup is just a macro that expands to SparseArrayLookup. If I understand the comments correctly, the index being the actual pointer to the name is only for selectors created at runtime; selectors known to exist at compile/link time are packed into the dtable then.

So, how does it actually work?

Every selector is a unique number -- the hashing can be done at compile time rather than runtime, which means there's no need for the memory footprint and runtime slowdown of a hash table. If your language supports dynamic linking or creating methods at runtime, you may have to take care that new methods can be added without conflicts, such as by using a sparse array indexed on the method name.

$\endgroup$
0
2
$\begingroup$

I don't see much problem in adding extension methods to a vtable per se, it can work pretty much like usual inheritance. There's not so much difference between

public protocol AProtocol {
  func getSomeNumber() -> Int
}

extension AProtocol {
  public func getSomeText() -> String {
    getSomeNumber().description
  }
}

and

public interface A {
  public Int getSomeNumber();
}

public interface B extends A {
  public String getSomeText() {
    return this.getSomeNumber().toString();
  }
}

to me. In principle they can be compiled the same.

Funny things start happening when you have multiple inheritance, but both C++ and Java (with interfaces with default implementations) have solutions, albite different ones.

Alternatively you can pretty much side-step the problems altogether separating vtable from an object. That's the default implementation strategy for type classes (in Haskell and other languages) thus I heard it dubbed "type class pattern", but others call it "fat pointers". I think Laurence Tratt did a great job explaining how it works and how it compares to usual vtables using Rust for examples.

$\endgroup$
2
  • $\begingroup$ See, the thing that makes extensions different from subclasses is that it adds to existing objects. If I model extensions as subclasses, then factory methods in module A would create objects without the extension methods, which definitely isn’t what I want. $\endgroup$
    – Bbrk24
    May 25, 2023 at 11:18
  • $\begingroup$ @Bbrk24 it can work differently if you detach the vtable from an object as per the last paragraph. In that case your factory method will simply create the objects (without vtables at all) and the logic in other modules can use whatever else mechanism necessary to construct or find the right vtable for that object with all the right extension methods that are known at that point. $\endgroup$ May 26, 2023 at 15:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .