# Struggling to write a `DeepBorrow` trait

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 `Share`s 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.

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.

3 Likes

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();
}
}
}
``````

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.

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?

1 Like

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.