Why need object safety?

If we use trait object only by generic function, it's always safe. For example, in below case, self_compare always compare two same type object.

trait Comparable {
    fn compare(&self, other: &Self) -> bool;
}

impl Comparable for i32 {
    fn compare(&self, other: &Self) -> bool {
        self == other
    }
}

fn self_compare<T: Comparable>(a: &T) -> bool {
    a.compare(a)
}

fn main() {
    let x = 42;

    println!("x == x: {}", self_compare(&x)); // true

    /* cannot compile, but it should be ok
    let a: &dyn Comparable = &x;
    self_compare(a);
    */
}

Also, we can compile it like below c code:

#include <stdio.h>
#include <stdbool.h>

typedef bool (*CompareFn)(const void* a, const void* b);

typedef struct {
    const void* obj;
    CompareFn compare;
} ComparableObject;

bool compare_i32(const void* a, const void* b) {
    return *(const int*)a == *(const int*)b;
}

bool self_compare(ComparableObject comp_obj) {
    return comp_obj.compare(comp_obj.obj, comp_obj.obj);
}

int main() {
    int x = 42;

    ComparableObject a = { &x, compare_i32 };
    printf("x == x: %s\n", self_compare(a) ? "true" : "false"); // true
    
    return 0;
}

What's more, for existential type ∃α.T(α)≡∀β.(∀α.T(α)→β)→β, that means, for a trait object, if we pass ∀β.(∀α.T(α)→β), we can get a β value. (∀α.T(α)→β) is just a generic function. Every such type generic function should be ok for trait object.
So, why Rust have object safety and forbidden such usage?

1 Like

Your c code has UB if the types are different. Rust would have to check that they are the same

You can create a new DynComp trait that uses a dyn & for the other parameter and the tries to downcast it to the self type. And blanket impl it for all Eq implementors.

1 Like

no, the C code is NOT equivalent to the rust trait.

the rust trait prevent you from doing this:

/// compile error: argument type mismatch
fn nonsense_compare<X: Comparable, Y: Comparable>(x: &X, y: &Y) -> bool {
    x.compare(y)
}

but your C code doesn't prevent this error:

bool nonsense_compare(ComparableObject x, ComparableObject y) {
    return x.compare(x.obj, y.obj)
}

instead, the following definition would ressemble the C version more closely, and is dyn-compatible, but you'll have a hard time implementing it:

// this resembles the C code, e.g. erase the type of the `other` argument
trait Comparable {
    fn compare(&self, other: &dyn Comparable) -> bool;
}
// but how to implement it?
impl Comparable for i32 {
    fn compare(&self, other: &dyn Comparable) -> bool {
        // what???
    }
}
4 Likes

it's impossible that types are different. I only pass one a.
As mentioned above, if the generic function type is (∀α.T(α)→β), then the function is always safe.

I don't write nonsense_compare. And of course c code never care too much about type safe. I just write the c code to show the code can compile with high performance.

But rust cannot statically verify this for every use of the trait. You have to think of dyn trait in rust as a really simple vtable

compiler can statically check whether the generic function type is (∀α.T(α)→β).

Yes, it can; that's why your original (non-dyn) version compiles successfully. By coercing to dyn Comparable, though, you're explicitly asking the compiler not to do that and instead use a vtable strategy that will support arbitrary types, even if you aren't using that capability in practice.

5 Likes

Your post would be much more understandable if:

  • you specified which type theory (and syntax for it) you're using
  • you did not shadow/reuse variable names (the α for example)
  • you explained what each variable is supposed to represent in the code example above

That said, the answer is most likely "Rust does not have dependent types".

I would also advise against using C for examples involving type checking since it's not really known for that capability.

13 Likes

Here's another way to look at this problem: even in a language with dependent types, dyn Comparable cannot meaningfully implement the Comparable trait.

In a dependently typed language, dyn Comparable would be an alias for ∃T: Type. (T, Comparable<Self = T>) - that is, it's a tuple containing an arbitrary type, an instance of that type, and an instance of Comparable for that type. A Comparable<Self = T> is essentially a struct with one field, a &T -> &T -> bool. (The actual Rust semantics are fairly close to this, modulo pointers - the vtable of a fat pointer is a pointer to the struct.)

The problem is, implementing Comparable for dyn Comparable requires providing an instance of Comparable<Self = dyn Comparable>, which requires an &dyn Comparable -> &dyn Comparable -> bool. Rewriting this to the above form gives &(∃T: Type. (T, Comparable<Self = T>)) -> &(∃U: Type. (U, Comparable<Self = U>)) -> bool. Clearly, this type has two different and unrelated type parameters; implementing it properly would require generalizing comparison from "I can compare T to itself and U to itself" to "I can compare T to some arbitrary type U", which is impossible.

So, back to the original problem. Calling self_compare(a); would not be sound, because a could not implement Comparable. In this very specific case, it "works" - you could compile it, if Rust made a very special exception that is only sound under specific circumstances. But it starts to break down very quickly:

fn duo_compare<T: Comparable>(a: &T, b: &T) -> bool {
    a.compare(b)
}

let a: &dyn Comparable = /* snip, T */;
let b: &dyn Comparable = /* snip, U */;
duo_compare(a, b); // Unsound! T compared with U

In practice the special exception here would be so limited (and easy to get wrong) that it isn't worth making; it's much safer to just declare that trait non-dyn-safe.

One other note, type theory isn't the only source of the dyn-safety limitation. For example, there's nothing type-theoretically wrong with having generics be dyn-safe, but Rust's desire/requirement to monomorphize prevents that.

8 Likes

"The problem is, implementing Comparable for dyn Comparable requires providing an instance of Comparable<Self = dyn Comparable> , which requires an &dyn Comparable -> &dyn Comparable -> bool ."
no, it's totally wrong. A dyn comparable never requires &dyn Comparable -> &dyn Comparable -> bool. A existential type never require such functions, it's just wrongly usage followed from originally ugly OOP programming. As mentioned above, an existential type is ∀β.(∀α.T(α)→β)→β, it only support user to provide a generic function with type ∀α.T(α)→β and return β. It has no relation with &dyn Comparable -> &dyn Comparable -> bool at all.

(post deleted by author)

rust explicitly define generic functions as "non-dispatchable":

Dispatchable functions must:

  • Not have any type parameters (although lifetime parameters are allowed).

rust trait objects automatically implement the base trait.

if this were not the case, you cannot substitute dyn Comparable for T instantiating generic function fn self_compare<T: Comparable>(a: &T) -> bool;

and when implementing Comparable for dyn Comparable, Self is dyn Comparable, per rust's type system.

that's right, rust trait objects are just for dynamic dispaching:

The purpose of trait objects is to permit “late binding” of methods. Calling a method on a trait object results in virtual dispatch at runtime: that is, a function pointer is loaded from the trait object vtable and invoked indirectly.

all in all, rust's dyn Trait may resemble some aspect of existantial types, but it is NOT existantial types, for these reasons. your whole premise that dyn-compatible equals existantial type is simply false.


I'm interested to learn the type theory you are using, specifically, how is rust's trait modeled in this type theory? also, does rust's requirement that dyn Trait: Trait hold true in the type theory? thank you in advance.

4 Likes

A trait object is not an existential type, much less in your obscure sense that you fail to describe, it is a "dynamically dispatched trait".

1 Like

(Mostly a side comment / maybe off-topic.)

It's not a requirement / doesn't hold in Rust. (They are of limited usefulness without, so maybe they could be / maybe the breaking change is nonetheless tenable. On the other hand, it seems cleaner to me to just saydyn _ types are always valid, in the type system if nothing else; they just might not implement said trait or might be non-constructable.)

right, I agree it's cleaner to separate the concern between dyn type and dyn compatibility. I think this idea is also discussed in one of niko's "dyn async trait series", although I don't remember the details.

there's also the possibility of removing the automatic impl Trait for dyn Trait shim generated by the compiler, but instead introducing new syntax to enable user code to implement the shim manually, as a way to "opt-in" dyn compatibility.

1 Like

hi, all. I found Swift can support such usage:
swift_self_comp

let comps : [any Comparable] = [1, 2.0, "hello"]

func selfCompare<T: Comparable>(_ a: T) -> Bool {
    return a < a
}

for c in comps {
    print(selfCompare(c))
}

The link editor here breaks full godbolt links (it adds a level of URL encoding) - use a short link or paste into the raw markdown view

1 Like

this is very interesting to know.

I don't know anything about swift, but just playing around with your code, it seems in swift type system, the erased type any Comparable (which I assume is analog to rust's dyn Comparable?) does not really "conform to" Comparable protocol (which I assume is the swift equivalent way to say the trait Comparable is not dyn-compatible?)

here's the compile error I got:

func binaryCompare<T: Comparable>(_ a: T, _ b: T) -> Bool {
    return a < b
}

print(binaryCompare(comps[0], comps[1]));
//         |- error: type 'any Comparable' cannot conform to 'Comparable'
//         `- note: only concrete types such as structs, enums and classes can conform to protocols

so I think the swift type checker is smarter for the special case of func selfCompare() to automatically generate an adapter when only a single value is given, where in rust you have to manually create the dyn-compatible adapter trait and blanket implement it for the non dyn-compatible one. however, the original problem remains: the trait Comparable as defined in OP cannot be dynamically dispatched using vtable, i.e. is non dyn-compatible in rust terminology.

I am not very familiar with Swift, too. But yes, it can only support single value input generic function in my understanding.
However, "binaryCompare(comps[0], comps[1])" not compile doesn't means it dynamically dispatched using vtable. We store different types into one container and call selfCompare for each of them, of course it's dynamically dispatched using vtable.
In fact, I think people made a mistake long term. Use dyn_object.virtual_function is not really dynamic dispatch, it's just a Syntactic sugar,the really dynamic dispatch is single value input generic function. Why I say it's Syntactic sugar? Because every time we use dyn_object.virtual_function, we can use single value input generic function to replace it. For example, https://godbolt.org/z/nEWq6qPjG , we can always use makeSpeakGeneric to replace makeSpeak.

protocol Speak {
    func speak()
}

struct Dog: Speak {
    func speak() {
        print("Woof!")
    }
}

struct Cat: Speak {
    func speak() {
        print("Meow!")
    }
}

func makeSpeak(_ animal: any Speak) {
    animal.speak()
}

let dog : any Speak = Dog()
let cat : any Speak = Cat()

makeSpeak(dog)
makeSpeak(cat)

func makeSpeakGeneric<T: Speak>(_ animal: T) {
    animal.speak()
}

makeSpeakGeneric(dog)
makeSpeakGeneric(cat)

Of course more powerful representation is better.