Substituting non-owning type to reference of owning type

help
1

Hello,
I have two types representing the same kind of data, but one of them does not own it:

#[derive(Debug)]
pub struct NonOwning<'a> {
    first: usize,
    others: &'a [usize],
}

#[derive(Debug, Clone)]
pub struct Owning {
    first: usize,
    others: Vec<usize>,
}

What I want to know is if it's possible to implement some trait so that when a function wants a &'a Owning, I can instead give it a NonOwning<'a>, without having to clone anything. Typically, I have a HashSet<Owning>, and I want to check if it contains a NonOwning.

Thanks

2

You can’t solve this with the approach you’ve presented here, because you need to actually have an Owning stored somewhere for the reference to point to.

There are, however , some tricks you can pull with Borrow<dyn …> to deal with the hash set. When I get to a real computer, I’ll try to give an example.

3

Here are a couple options if you're willing to change your structure.

  1. You can combine owning and borrowing into one:

    #[derive(Debug)]
pub struct Data<'a> {
    first: usize,
    others: std::borrow::Cow<'a, [usize]>,
}

    This has the costs that you have to write Data<'static> for owning instances, and each usage of others will result in some run-time checking for which kind it is.

  2. You can make first be the first element of others instead of a separate field, so that this is itself an ordinary case of owning or borrowing a slice. If you do this, you can still provide your desired structure by making an unsized wrapper on the slice itself:

    #[repr(transparent)]
struct Data([usize]);

impl Data {
    fn first(&self) -> usize {
        self.0[0]
    }

    fn others(&self) -> &[usize] {
        self.0[1..]
    } 
}

    Then you can store Box<Data> in your HashSet and use &Data in contains, I think. You may need an additional std::borrow::Borrow implementation.

    The catch is that it's difficult to construct this type. You need a bit of unsafe code, or bytemuck can help.

2 Likes
4

The fundamental idea here is that Borrow represents cross-type comparisons. Your two types have different data layouts, but that's exactly what trait objects are designed to abstract over. Implementing this is pretty straightforward, but a bit longwinded:

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct NonOwning<'a> {
    first: usize,
    others: &'a [usize],
}

#[derive(Debug, Clone)]
pub struct Owning {
    first: usize,
    others: Vec<usize>,
}

// Trait to define the comparison
pub trait NonOwningView {
    fn non_owning(&self)->NonOwning<'_>;
}

impl NonOwningView for NonOwning<'_> {
    fn non_owning(&self)->NonOwning<'_> { *self }
}

impl NonOwningView for Owning {
    fn non_owning(&self)->NonOwning<'_> {
        NonOwning { first: self.first, others: &self.others[..] }
    }
}

// How to compare trait objects
impl std::cmp::PartialEq for dyn NonOwningView + '_ {
    fn eq(&self, other: &Self)->bool {
        self.non_owning() == other.non_owning()
    }
}

impl std::cmp::Eq for dyn NonOwningView + '_ {}

impl std::hash::Hash for dyn NonOwningView + '_ {
    fn hash<H: std::hash::Hasher>(&self, hasher:&mut H) {
        self.non_owning().hash(hasher)
    }
}

// Make sure Owned compares the same as the trait objects do
impl std::cmp::PartialEq for Owning {
    fn eq(&self, other: &Self)->bool {
        (self as &dyn NonOwningView) == (other as &dyn NonOwningView)
    }
}

impl std::cmp::Eq for Owning {}

impl std::hash::Hash for Owning {
    fn hash<H: std::hash::Hasher>(&self, hasher:&mut H) {
        (self as &dyn NonOwningView).hash(hasher)
    }
}

// Tell HashSet, etc. that it can use trait object for comparison
use std::borrow::Borrow;

impl<'a> Borrow<dyn NonOwningView + 'a> for Owning {
    fn borrow(&self)->&(dyn NonOwningView + 'a) { self }
}

impl<'a, 'b:'a> Borrow<dyn NonOwningView + 'a> for NonOwning<'b> {
    fn borrow(&self)->&(dyn NonOwningView + 'a) { self }
}

// Example use
#[test]
fn test_borrow() {
    use std::collections::HashSet;
    let set = [
        Owning { first: 3, others: vec![5,7]},
    ].into_iter().collect::<HashSet<_>>();
    
    assert!(set.contains::<dyn NonOwningView>(&NonOwning { first: 3, others: &[5,7]}))
}
5 Likes
5

Hey, thank you both for your replies.
I'll investigate further to see which one I'm going to use, but honestly, given the potential size of my data, I don't think the neatness of your solutions is going to be worth the added complexity, compared to just discarding NonOwning and just cloning Owning when necessary.
In any case, it was very instructive. Thank you very much.