Downcasting covariantly associated types

1

Ok, this is a bit convoluted by you're familiar with the yoke crate it might be easier.

In this playground you can find a CovariantDowncast trait thats make it possible to downcast a 'static reference to a type that has a lifetime that is 'static to a reference with lifetime 'a to the same type with lifetime 'a. Downcasting covariantly references is trivial for owned types (hence the blanket implementation that followes immediately), but the situation is more complicated if you have internal lifetimes.

Specifically, this problem happens when you want to pair a zero-copy data structure referring to some memory and the memory it refers to. You put in the a structure Case (not shown here, it's Yoke in the yoke crate) both the zero-copy data structure with lifetime 'static (remember that it refers to some memory), and the associated memory. The important thing is then when you get the data structure from Case you need not only to get a &'a to the data structure for some 'a—also the lifetime of the data structure must be downcast from 'static to 'a, or you could throw away the Case, access the reference and crash. The purpose of CovariantDowncast is to code (unsafely) this constraint (it is a simplified version of the Yokeable trait, but the idea comes from there). Basically, it says "this lifetime is covariant and can be downcast from 'static".

Now, epserde is a kind-of zero-copy (de)serialization framework. Each type has an associated deserialization type: for example, Vec<usize> has deserialization type &[usize] (and so on recursively for more complex types). We need to implement CovariantDowncast for all associated deserialization types.

If there are no type parameters, everything is fine, as you can see in the second half of the code (the associated types are irrelevant for this example).

The problem is that as soon as there are type parameters, the compiler complains that they are not used. This is of course correct—different types might have the same deserialization type and that would create conflicting implementations. The problem is that we do not see how to get out of this except by adding a parameter T to CovariantDowncast the represent the original type, and which thus disambiguate the implementation. However, then T gets propagated everywhere, creating a really awkward and cumbersome environment.

T is not necessary: it is just there to tell the compiler "this implementation is unique". We were wondering whether there's any other way to convince the compiler of this fact.

Note that it is possible that in some basic cases associated deserialization types are the same: for example, both String and Box<std> have the same deserialization type—&str. In this specific case, we can just write a single implementation of CovariantDowncast that covers both cases.

In the derive code, we define deserialization types recursively: U<A> has deserialization type U<A::DeserType<'a>>. Even replacing U<A>::DeserType<a'> with U<A::DeserType<'a>> in the CovariantDowncast implementation we do not solve the problem, as, again, the compiler does not consider A as used when in appears in U<A::DeserType<'a>>.

In principle, if we could unroll the recursion at derive time and write the actual deserialization type, we would be fine, but there's no way to access this information at derive time. We might create a utility generating a CovariantDowncast implementation for the actual deserialization type, but it would be very unnatural and cumbersome.

Any suggestion would be welcome!

1 Like
2

Is your derive in a position to know at least one A for which U<A>: T?

3

No, unfortunately not. The implementation is entirely generic.

I didn't mention that if you accept that Case cannot hold standard owned data, there is a way out: having Case parameterized by S, but a field of type S::Assoc<'a>. At that point one can dispense with CovariantDowncast and apply directly transform in the getmethod (and of course the trait containing Assoc must be unsafe, as it assumes implicitly that covariant downcasting is fine).

We are trying to avoid this solution because, as I said, it prevents Case from containing owned data, making access transparency (to deserialized or owned data) impossible. The other reason is more philosophical: deserialization can happen independenly of the covariant downcast—it's a problem strictly connected with the "casing" idea.

4

Heads up: There's no actionable suggestions in this reply, I'm just exploring the problem space. If I think of something practical or more questions leading that direction I'll make another reply.

Here's a playground where I try to distill your question down a bit.[1] The problem is that you want to provide implementations for TargetTrait<'_> via the associated type of Intermediate implementators, for macro reasons. Given the specific example, you're looking for a way to name i32. With the example I added at the bottom, you're trying to name Option<A> (for any A).

I believe the compiler could actually handle the overlap checks here. To try to explain what I mean, consider what needs to be proved:

// The compiler can and does check this, letting it compile
for<'a>
    impl <S as Intermediate>::Assoc<'a> does not overlap with other impls
    => usize does not overlap with other impls

// E0207
for<'a, A>
    impl <U<A> as Intermediate>::Assoc<'a> does not overlap with other impls
    => i32 does not overlap with other impls

// E0207... but doesn't really need to be
for<'a, A>
    impl <V<A> as Intermediate>::Assoc<'a> does not overlap with other impls
    => Option<A> does not overlap with other impls

In none of the cases is there an actual conflict. The first one compiles because lifetimes don't need to be constrained like type parameters do. The compiler must have normalized the associated type projection for the overlap check, or it could not know that Assoc<'a> wasn't, say, &'a () (a conflict with the impl for &'static T).

The last one would be fine if associated type normalization happened before the unconstrained type parameter check (E0207) as well.[2] A is actually a parameter of the implementing type here!

The middle one is still problematic because you could make use of A in the implementation body, and the original concerns arise. If there was a way to introduce a generic type parameter for the header only, and normalization happened before E0207, this one could work too. But that seems further fetched.

That's all feature-request territory, not a solution to your problem today. But I do think this demonstrates that this is not a problem about convincing the compiler that there are no conflicts per se. For the playgrounds, the problems are

  • E0207 is eagerly enforced, without normalization (a problem for the Option<A> case)
  • There's no way to have a generic type parameter in the implementation header which isn't usable in the implementation body (a problem for the i32 case)

(That said, some of the workarounds I attempted involved legitimately conflicting implementations, so conflicts cannot be completely ignored.)

  1. I could have gotten rid of the lifetimes even, but didn't bother; maybe they're relevant to you sometimes. ↩︎

  2. n.b. I have no idea how practical it would be for the compiler to do that ↩︎

  3. i.e. a way to introduce a type parameter not usable in the implementation body ↩︎

5

Can you elaborate on what is cumbersome? At the sites where CovariantDowncast is utilized, do you not know any implementations, or it is dyn related, or is it just ergonomics -- having to name an implementor in situations where you shouldn't need to, like, there isn't one around?

6

It is just ergonomics. All structures containing a Case structure should have an additional parameter per Case to express the disambiguating type, and this propagates upwards. For example, the typestate used to load a BvGraph would become much more complex, as beside managing and storing the type of the offsets we should also manage and store the disambiguating type for the offsets, and propagate that type to anything storing the offsets (e.g., the reader factory). Not impossible, but a serious ergonomics blow.

1 Like
7

Yes, you're right—and I realize now the recursion problem is more relevant to the issue than I thought, so I tried to distill the problem here.

So, while I accept the compiler can't do the commented impl, I think it shold able to the other, as there's an outside Q type that makes the implementation unique.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.