Help with lifetimes for iterating through object hierarchy

[adamritter]

Hi,

I'm able to create an iterator for iterating through an object hierarchy, but I need to defer some slow computation and be able to access data from higher levels of the tree if required.

It's quite easy to do with unsafe Rust, and I know that the code is memory safe, but I can't prove it to Rust with setting the right lifetimes.

Here's a code that I created for minimizing the problem:

struct S<'a,'p> {
    data: &'a mut Option<u32>,
    e: E<'a,'p>
}

enum E<'a,'p> {
    Root(),
    Parent(&'p mut S<'a,'p>)
}

fn get(s:&mut S)->u32 {
    match(s.data) {
        Some(r)=>*r,
        None=>{
            let E::Parent(p)=&mut s.e else {
                panic!("!!!");
            };
            let rr=get(p);
            *s.data=Some(rr);
            rr
        }
    }
}

struct Data {
    extract: bool,
    data: Option<u32>,
    sub: Option<Box<Data>>
}

fn walk<'a,'p>(d:&'a mut Data, mut s:S<'a,'p>) {
    if(d.extract) {
        get(&mut s);
    }
    if let Some(sub)=&mut d.sub {
        walk(sub.as_mut(), S {e: E::Parent(&mut s), data: &mut d.data})
    }
}

fn test() {
    let mut data=Data {extract: false, data: Some(5),
        sub: Some(Box::new(
            Data {extract: false, data: None, sub: Some(Box::new(
                Data {extract: false, data: None, sub: None}
            ))}

        ))};
    walk(&mut data.sub.unwrap(), S {data: &mut data.data, e: E::Root()});
}

PS: It seems my previous post was taken down by spam filter when I was trying to fix formatting, so I tried again.

[H2CO3]

The problem is the well-recognized anti-pattern of &'a mut T<'a>, which in your case manifests syntactically as the Parent(&'p mut S<'a, 'p>) variant. This means that the value typed S<'a, 'p> will be borrowed for the entirety of its lifetime (due to &'p mut S<'_, 'p>), so it will effectively be useless after you mutably borrow it once. This is because mutable borrows are invariant in their type argument, so a &mut T<'long> can't be "shrunk" and converted to a &mut T<'short>.

If you try to rewrite it by separating the two lifetimes, you run into another problem. The correct definition would look something like:

struct S<'a, 'p> {
    data: &'a mut Option<u32>,
    e: E<'a, 'p>,
}

enum E<'a, 'p> {
    Root,
    Parent(&'a mut S<'b, 'p>),
}

however, this would need another lifetime parameter 'b on E:

struct S<'a, 'p> {
    data: &'a mut Option<u32>,
    e: E<'a, ???, 'p>,
}

enum E<'a, 'b, 'p> {
    Root,
    Parent(&'a mut S<'b, 'p>),
}

But that would in turn require another type parameter on S, etc. so the number of required type parameters grows without bounds.

This is another typical problem/anti-pattern, and as far as I'm aware, it can't be fixed, so what you want can't be expressed. You should probably re-structure your code instead, so that this is not required.

[adamritter]

Thanks very much for the quick answer.

Reorganizing the code base is too hard, but maybe I can factor out this problematic part which is safe but can't be supported by the type system (by making this example generic), and make a minimal safe data structure that uses 1 line of unsafe Rust.

[H2CO3]

It depends. Since the safe version of your code doesn't typecheck for a good reason, I strongly doubt that working it around with unsafe would result in sound, correct code. If you do that, you will likely cause undefined behavior.

[adamritter]

Thanks,

I could solve the problem with passing FnMuts around:

struct DataHolder<Data> {
    extract: bool,
    data: Option<Data>,
    sub: Option<Box<DataHolder<Data>>>
}

fn walk<Data, F>(d:&mut DataHolder<Data>, mut f: F) where Data : Clone ,  F:FnMut()->Data {
    if d.extract {
        if d.data.is_none() {
            let dd=f();
            d.data=Some(dd);
        }
        if let Some(sub)=&mut d.sub {
            let dd=&mut d.data;
            walk(sub.as_mut(), || dd.clone().unwrap())
        }
    } else {
        let o=&mut d.sub;
        let dd=&mut d.data;
        if let Some(sub)=o {
            if let Some(ddd)=dd {
                walk(sub.as_mut(), || ddd.clone())
            } else {
                walk(sub.as_mut(), || { 
                    let r=f();
                    *dd=Some(r.clone()); 
                    r})
            }
        }
    }
}

fn test() {
    let mut data=DataHolder {extract: false, data: Some(5), sub: None};
    let mut data2=DataHolder {extract: false, data: None, sub: None};
    let mut data3=DataHolder {extract: true, data: None, sub: None};
    data2.sub=Some(Box::new(data3));
    data.sub=Some(Box::new(data2));
    walk(&mut data, ||5);
}