`&impl Borrow<U>` should implement `Borrow<U>`

Currently Borrow has the following impls, plus some others that aren't relevant to this:

impl<T: ?Sized> Borrow<T> for T {
    fn borrow(&self) -> &T {
        self
    }
}

impl<T: ?Sized> Borrow<T> for &T {
    fn borrow(&self) -> &T {
        &**self
    }
}

I would find it very useful to have impl<T: Borrow<U> + ?Sized, U> Borrow<U> for &T, presumably replacing impl<T: ?Sized> Borrow<T> for &T (which would still effectively exist due to the impl<T: ?Sized> Borrow<T> for T)

impl<T: Borrow<U> + ?Sized, U> Borrow<U> for &T {
    fn borrow(&self) -> &U {
        (*self).borrow()
    }
}

FWIW, my use case for this is something along the lines of:

struct MyDataStructure<T, F: Fn(&T) -> K> {
    data: Vec<T>,
    key_extractor: F,
}

impl MyDataStructure {
    fn get<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> &T where K: Borrow<Q> {
        (self.key_extractor)(self.data[...]).borrow() == key
    }
}

The reason I can't have F return &K is that I want to allow for computed properties (e.g. the length of the data) instead of just stuff that can be borrowed.

Is there any reason this doesn't or can't exist? Is there some sort of coherence issue or something? If this isn't possible, are there any other ways to do what I'm trying to do?

I guess one potential issue is conflicting with existing impls for references, but I'm not sure how much of an issue that is. (Although I can see them being created in response to a lack of a blanket impl...)

I'm on my phone here right now, so bear with me while I'm trying to avoid typing too much code. Basically, an impl like you suggested is not possible because of conflicting impls. We of course still have the T: Borrow<T> impl - and that one we want to keep. You now propose a &'a T: Borrow<U> where T: Borrow<U>.

Now assume we define a (recursive) type Struct<'a> containing a field of type &'a Struct<'a>. (I know, such types tend to be not too useful due to the heavy restrictions on their lifetime but it is possible. And the example becomes way more realistic if you start asking for an impl for Box<T> that's similar to your proposed impl for shared references. Anyways, let's continue...) Then you can define an impl that ensures Struct<'a>: Borrow<&'a Struct<'a>> by pointing to the field of the Struct type. Then your &' a T: Borrow<U> where T: Borrow<U> applies to the case T == Struct<'a> and U == &'a Struct<'a>, so that we get an impl for &' a T: Borrow<U> i. e. &'a Struct<'a>: Borrow<&'a Struct<'a>>. But that's in conflict with the already existing T: Borrow<T>.

How did we get here? Well we didn't, Rust would have already rejected the &'a T: Borrow<U> where T: Borrow<U> impl for being in conflict with T: Borrow<T> before we even started talking about our Struct type. That one is just an example for why Rust will reject such a trait implementation.

Feel free to try defining your own Borrow-like trait (you don't even need methods) and adding just those two blanket impls. Rust will probably tell you that there's a conflict and probably even mention that the problem occurs precisely when U == &T. (As I said, I'm on my phone so I haven't actually tested this, so correct me if you're getting different results :wink:)

4 Likes

Hmm, yeah... :pensive: I guess I'll just have multiple different get methods, one for values, one for references, or something like that.

Error message for reference:

error[E0119]: conflicting implementations of trait `MyBorrow<&_>` for type `&_`:
 --> src\lib.rs:5:1
  |
1 | impl<T: ?Sized> MyBorrow<T> for T {}
  | --------------------------------- first implementation here
2 | impl<T: MyBorrow<U> + ?Sized, U> MyBorrow<U> for &T {}
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `&_`

Is there a reason that returning a Cow isn't sufficient?

2 Likes

I realized that I'm not sure my original idea can work.

Yeah, I could consider using Cow. It does restrict it to ToOwned types (which includes Clone), which probably isn't always the case, but I'm having trouble coming up with a good exception. (FWIW, all I really need is Borrow::borrow, not ToOwned::to_owned.) This seems like a good option though. (F: Fn(&T) -> Cow<K> I think)

Another possibility I thought of is something like for<'a> F: Fn(&'a T, &'a mut MaybeUninit<K>) -> &'a K, which doesn't introduce extra bounds, but is slightly clunkier to use.

What if K has drop glue? In that signature it is leaked. You could, however, use:

and have

for<'a> Fn(&'a T, &'a mut Slot<K>) -> Either<&'a K, StackBox<'a, K>>
  • (I may try to add Cow-related impls to StackBox so that that Either may be replaced with it).

Or simply Fn(&'_ T) -> Either<&'_ K, K>


Note that an alternative for Cow-like patterns is to use continuation-passing style (which incidentally frees you of any Borrow issues whatsoever):

F : Fn(&'_ T, &'_ mut dyn FnMut(&'_ K))
// or:        Box<    dyn FnOnce(&'_ K)>
// or:   StackBox<'_, dyn FnOnce(&'_ K)>

and then:

let mut ret = false;
// or:                            stackbox!(|q| ret = {
// or:                             Box::new(|q| ret = {
self.with_key_extractor(&self.data[…], &mut |q| ret = {
    q.borrow() == key
});
ret
1 Like

Hmm... Good point about not calling Drop.

stackbox seems a bit overly complicated but should work.

The problem with CPS is that I need to do multiple comparisons, and don't want to recalculate the key each time.

Also, what about for<'a> F: Fn(&'a T, &'a mut Option<K>) -> &'a K? One question I can think of is whether or not the Option is guaranteed to start as None, but there might be other issues I haven't thought of.

That would be dropped on the caller's frame, so :ok_hand:

Yeah, users would be allowed to panic! if the received Option<_> is not None, by starting with an assert!(out_slot.is_none());, or silently dropping that value (drop(out_slot.take());).

1 Like

Makes sense. I guess the main advantage of StackBox is getting rid of those annoying corner cases involving the Option starting out Some, or being inspected once the borrow ends. I'm not sure if it's worth an extra, complicated, dependency, but I'll see how annoyed I get by the Option stuff.

1 Like

:100: