Switch the API away from Borrow bounds

[kvark]

It is a very common pattern in gfx-hal API right now to have I: IntoIterator and I::Item: Borrow<Something>. Unfortunately, this falls apart if the user actually wants to have something like this:

struct Foo<B: Backend>(B::Something);
impl<B: Backend> Borrow<B::Something> for Foo<B> {...}

Compiler isn't happy, because T impls Borrow<T> and there is no way to convince the compiler that this implementation doesn't conflict with our new one...

I'm going to change everything to use AsRef therefore. Any thoughts? Objections?

[zakarumych]

There is a way to convince the compiler

struct Foo<B, S=B::Something>(S);
impl<B> Borrow<B::Something> for Foo<B> { ... }

AsRef doesn't tell you of intention to borrow data from argument. Borrow does.

[kvark]

Apparently, AsRef isn't a solution either, since it's not implemented for T or &T. Next alternative: Iterator<&'a T>

[zakarumych]

Iterator<Item = &'a T> isn't better than Iterator<Item = impl Borrow<T>>
because it accepts strictly less types.

[kvark]

@omni-viral it is better because Borrow<T> just isn't possible for structs that just depend on <B: Backend>, including our own CommandBuffer. The trade-off here is that for Borrow we'd require all the users to change their data types/structures, while for &'a T it's only a single iter() call (or similar) at the use site.

[kvark]

Interestingly, Iterator<Item = &'a T> isn't a solution either :( If the user has an iterator over actual items, I don't see how Rust would allow us to make an iterator over their references instead (sounds like a case for streaming iterators, which we don't have). See playground example.

TL;DR: no solution is good atm?

• Borrow is bad because we can't impl<B: Backend> Borrow<B::AssociatedType> for Something<B>, where Something<B: Backend>(B::AssociatedType) or similar
  • a workaround exist by adding an extra generic type, but it's a bit awkward
• AsRef is bad because it's not implemented for T or &T
• &'a T is bad because we can't get an iterator over references if we have one over owned items...

@gankro - maybe you can make a recommendation for us?

[Gankra]

This stuff is extremely out of cache for me, but yeah in general you can't "win" the generic borrow game. The ideal system has conflicting blanket impls, and is consequently inexpressible. I also don't know enough about your system to suggest a more subtle solution. The only advice I can give is "trying to give a million meta-conversions to smooth over APIs is something I dislike as it blows up compile times and makes it much harder to read signatures, so maybe don't do it?"

[zakarumych]

@kvark you missed my point. impl Borrow<T> matches both &T and T. So it is already better than just plain &T. Even though you not always can implement it for wrapper type (although you can)

[fu5ha]

"trying to give a million meta-conversions to smooth over APIs is something I dislike as it blows up compile times and makes it much harder to read signatures, so maybe don't do it?"

Agree

[kvark]

@gankro

This stuff is extremely out of cache for me, but yeah in general you can't "win" the generic borrow game.

This doesn't appear so hopeless to me. Basically, it's a matter of communicating to Rust that in our particular case in struct Foo<B>(B::Something) that B::Something is never the same as Foo itself. This appears rather obvious to humans, fwiw. it's hardly a "can't win" game.

I also don't know enough about your system to suggest a more subtle solution.

Basically, we have a bunch of API entry points that receive sequences of references to our types. These are associated types of trait Backend. The user would typically have their own wrappers like:

struct Foo<B: hal::Backend> {
  raw: B::Foo,
  _something_else: Bar,
}

So as it turns out, neither Borrow, AsRef, or Iterator<&'a T> in the API would allow the user to provide such a sequence (of &B::Foo) without run-time overhead, with an exception of a case where the user cripples the signature to be Foo<B: hal::Backend, F = <B as hal::Backend>::Foo> { raw: F, ...}

The only advice I can give is "trying to give a million meta-conversions to smooth over APIs is something I dislike as it blows up compile times and makes it much harder to read signatures, so maybe don't do it?"

I don't find this advice applicable. We aren't going for that type complexity because we feel like it, we see it as the only means of having zero run-time overhead. In this context, compile times are not nearly as important.

[zakarumych]

The other option is to not use B: Backend as type parameter for type wrappers.
So instead of

struct Foo<B: Backend> {
  raw: B::Foo,
}

you'd write

struct Foo<F> {
  raw: F,
}

impl<F> Borrow<F> for Foo<F> { ... }

Then function signature

trait Device<B: Backend> {
  fn takes_foos(_: impl IntoIterator<Item = impl Borrow<B::Foo>>);
}

// This should typecheck.
let foos: Vec<Foo<B::Foo>> = ...;
device.takes_foos(foos);
device.takes_foos(&foos);

[Gankra]

I wrote up a detailed explanation here of why you can logically reason about the non-existence of the overlapping implementation, but in fact it can exist, and Rust doesn't factor in this kind of "local non-existence": https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=b0e9517c0599b080f9eeae3bfe548aa2

[Gankra]

Oh also, although streaming iterators aren't compatible with iterators/for, you can make them, they work fine: https://docs.rs/streaming-iterator/0.1.4/streaming_iterator/

[kvark]

@gankro @omni-viral I'm really puzzled as to why this gets a pass:

trait Bar {
    type Something;
}
struct Foo<B: Bar, S=<B as Bar>::Something>(S, PhantomData<B>);
impl<B, S> Borrow<S> for Foo<B, S>
where
    B: Bar<Something = S>,
{
    fn borrow(&self) -> &B::Something {
        &self.0
    }
}

Isn't saying that B<Something = S> semantically equivalent to just using B::Something instead of S in the first place? :/

[Gankra]

So = is just the default for when someone omits the argument. I am surprised this compiles, but I can make at least one argument that it's different: by making the associated type explicit, you have made the problematic implementation completely inexpressable, as the type's description itself is now infinite:

struct Evil;
impl Backend for Evil {
  type Metadata = GenericBackend<Evil, GenericBackend<Evil, GenericBackend, Evil, ......................>>;
}

which you can write in finite characters, but:

impl Backend for Evil {
  type Metadata = GenericBackend<Evil>;
}

error[E0275]: overflow evaluating the requirement `<Evil as Backend>::Metadata`
  --> src/lib.rs:25:6
   |
25 | impl Backend for Evil {
   |      ^^^^^^^

[Gankra]

filed rust-lang/rust#56804 just to be sure this isn't "accidentally" working

[zakarumych]

@kvark
The sole fact that S is type parameter to Foo<B, S> convince rustc that Foo<B, S> != S.
Hence you can implement Borrow<S> for Foo<B, S>.
Demanding that B::Something = S in where clause allows you to actually implement it.

[madadam]

Could this be solved by a custom Borrow-like trait:

pub trait GfxBorrow<T> {
    fn borrow(&self) -> &T;
}

And manually implemented it for all the types for which it makes sense?

[kvark]

@madadam the point of Borrow bound here (or any alternative to it) is to support the user having their own structures as wrappers around gfx-rs's raw types. So if we introduce our own trait, we'd be forcing the users to implement it, which would be unfortunate.

[madadam]

Sure, but is that different from the situation now, where they have to implement Borrow?

[kvark]

@madadam yeah, I suppose that is mostly the case. Borrow is usefully implemented for a bunch of standard types, such as smart pointers, so I thought it could be handy.

[madadam]

The custom trait can be implemented for those types too. The idea is just to explicitly not implement it for T, to avoid the original issue here.

[kvark]

Funny thing is - we do need that blanket implementation for T (i.e. provide actual &B::CommandBuffer not a wrapper around it). So we end up with the same problem even having a custom trait :)

[madadam]

No :) What I'm trying to suggest is:

1. Implement the custom trait manually for each gfx type
2. Implement it additionally for some useful types like Arc, Rc, ...
3. Let the users implement it themselves for their own wrappers

Point 1 is tedious, but it could be handled by a macro or custom derive. We could even provide custom derive to handle point 3, but that is probably overkill.

[kvark]

We have a CommandBuffer type wrapper in gfx-hal (hello #2514) that wraps around B::CommandBuffer. Even if we introduce a new trait MyBorrow<T> (which I tried), it would have to be implemented for both CommandBuffer<B> and B::CommandBuffer. And it's impossible (unless adding the type to the generic list like @omni-viral suggested), it faces the same issue as with the original Borrow.

[madadam]

I see. Then I think I'm out of ideas 🙁

[kvark]

This would be deprecated by #2862