Struggling to write a `DeepBorrow` trait

[RobinH]

Hey all,

for a library I'm working on, I want to convert an owned value containing potentially multiple levels of other owned values into its "deep" borrowed representation.
For example:

// From -> Into

Vec<i32> -> &[i32]
Vec<Vec<i32>> -> &[&[i32]]

for<T: DeepBorrow> Vec<T> -> &[T::DeeplyBorrowed]

the first problem that I encountered, is that it seems fundamentally impossible to have the following:

let borrowed: &[&[i32]] = vec![vec![1,2,3]];

because, we need to perform an intermediate step of converting Vec<Vec<i32>> into Vec<&[i32]> and can't just return a reference to this intermediate value.

So what I have so far is DeepBorrow trait which allows me borrow the innermost owned value. What I tried to do, was to express the following code as a trait:

  let inp = vec![vec![vec![1, 2, 3], vec![4, 5, 6]]];

  let i3: Vec<Vec<&[i32]>> = inp
      .iter()
      .map(|v| v.iter().map(|v| &v[..]).collect())
      .collect();
  let i2: Vec<&[&[i32]]> = i3.iter().map(|v| &v[..]).collect();
  let i1: &[&[&[i32]]] = &i2[..];

My solution looks like this:

trait DeepBorrow
{
    type Borrowed<'b>
    where
        Self: 'b;

    fn deep_borrow(&self) -> Self::Borrowed<'_>;
}

impl<I: DeepBorrow> DeepBorrow for Vec<I> {
    type Borrowed<'b> = Vec<I::Borrowed<'b>> where Self: 'b;

    fn deep_borrow(&self) -> Self::Borrowed<'_> {
        self.iter().map(|i| i.deep_borrow()).collect()
    }
}

impl<T> DeepBorrow for Vec<&[T]>
{
    type Borrowed<'b> = &'b [&'b [T]] where Self: 'b;

    fn deep_borrow(&self) -> Self::Borrowed<'_> {
        &self[..]
    }
}

impl DeepBorrow for Vec<i32> {
    type Borrowed<'b> = &'b [i32] where Self: 'b;

    fn deep_borrow(&self) -> Self::Borrowed<'_> {
        &self[..]
    }
}

[Playground]
Calling deep_borrow recursively on the input from before gives the expected slice of slice of slices (see the playground). The idea of DeepBorrow is that the impls for Vec<i32> and Vec<&[T]> serve as the base case of the recursion.

This is cool, but not quite yet what I need. I feel like it should be possible to have a trait with a fn with_deep_borrow<F>(&self, f: F) where F: FnOnce(DeepBorrow) which encapsulates the recursive calling of deep_borrow and passes the deeply borrowed value to a closure. This should work, as all the intermediate values are on the stack.
My most promising attempt thus far looks like this:

/// Foo should really be WithDeepBorrow
trait Foo<B: ?Sized> {
    /// and this with_deep_borrow
    fn foo<F>(&self, f: F)
    where
        F: Fn(&B);
}

impl<'a, I> Foo<[&'a [i32]]> for Vec<I>
where
    Self: DeepBorrow,
    <Self  as DeepBorrow>::Borrowed<'a>: Foo<[&'a [i32]]>,
{
    fn foo<F>(&self, f: F)
    where
        F: Fn(&[&'a [i32]]),
    {
        let d = self.deep_borrow();
        d.foo(f);
    }
}

impl<'a> Foo<[&'a [i32]]> for Vec<&'a [i32]>
{
    fn foo<F>(&self, f: F)
    where
        F: FnOnce(&[&'a [i32]]),
    {
    
        f(&self[..])
    }
}

[Playground]
but I just can't it to work. I've tried many variations of the above, adding a lifetime parameter to Foo, using HRTB in some places and other stuff, but either I end up with conflicting implementations or or some other type errors.

I hope someone is able to help me with this. Using GATs is not a problem as they are soon to be stable, but I'd like to refrain from using other unstable features.

Context: Why do I think I need this?

In the library I'm currently writing, I have a proc macro which can be used to annotate functions and serves as kind of a cache plus extra stuff. For example

#[sub_circuit]
fn circ(input: &[Share]) { ... }

gets transformed into roughly

fn circ(input: &[Share]) {
    fn inner(input: &[Share]) { todo!("Original function body") }
    
    static CACHE: Cache = Cache // Caches the circuit computed by inner for a 
                                //specific input length 
                                
    // when the circuit computed by inner is not in the Cache
    // create Vec<Share> which represent the input shares to the circuit
    let circ_inputs: Vec<Share> = create_inputs(input);
    inner(&circ_inputs[..]);
    // store the circuit created by inner() into Cache
}

But I'd like to support different, potentially nested input types, e.g. &[&[Share]]. I think I'm able to do create_inputs but it needs to create new Shares and therefore an owned version of the original input. But then I need to call inner() with the borrowed version of the newly created nestes input shares. This is what I'm struggling with.

I feel like I might have fallen into the trap of trying to have a too generic API and will likely not use this approach even if I find a solution to WithDeepBorrow (which actually doesn't quite express what I want, since the user should be able to use both Vec<[Share; N]> or &[&[Share; N]] as input types, which whould not be possible with current design. But it still bugs me that I think the above outlined with_deep_borrow should be possible but I can't get it to work.

[kpreid]

The fundamental problem here is that in order to have an &T there must be a T somewhere in memory. A function with signature fn(&'b Foo) -> &'b Bar implies that, somewhere in the memory (transitively) pointed to by Foo (or 'static memory), can be found a Bar.

From an &Vec<Vec<i32>> you can get a &[Vec<i32>], a &[i32] (of one of the inner vectors), or an &i32. But nowhere in existing memory is there an [&[i32]], so you cannot produce a reference &[&[i32]].

You may be able to solve your problem by making your code generic over borrowed vs. owned data (with AsRef, Cow, and other such tools) but you cannot solve it by turning everything into nested references.

[RobinH]

Yes, I identified that problem. The current DeepBorrow trait solves it by only turning the innermost owned value into a borrowed value. Therefore the following

let inp = vec![vec![vec![1, 2, 3], vec![4, 5, 6]]];

{
    let d3: Vec<Vec<&[i32]>> = inp.deep_borrow();
    {
        let d2: Vec<&[&[i32]]> = d3.deep_borrow();
        {
            let d1: &[&[&[i32]]] = d2.deep_borrow();
        }
    }
}

[Playground]

works.

Exemplified by the nested scopes is the relationship between the lifetimes of the intermediate values. What I want is a method that recursively calls deep_borrow() until the input is completely borrowed (all the intermediate values are on the stack) and then calls a provided closure with the completely borrowed data. This is what I'm trying to solve with the Foo trait which I should have probably named something better, e.g. WithDeepBorrow.
I think from a memory safety standpoint, this should be fine, but I don't know if or how to express this as a trait.

[kpreid]

The work of performing all of those nested construction steps is equal in time and memory allocation to the work of cloning the entire nested structure (except for its leaves). Are you sure you want to do that? Maybe your use case would be better satisfied by using Arc instead of &, so that owning and borrowing can be combined into shared-ownership?

[RobinH]

No, I'm not sure that I want to do that The amount of work would probably not be a problem, but I've found a simpler solution.
I've given up on making my API as generic as possible and restrict the allowed types for which I needed this DeepBorrow abstraction. Arbitrary nesting is not really needed and for my use case it is probably sufficient to turn Vec<Vec<T>> into &[&[T]] which makes it much simpler.

Thanks for your help :)