Explicit lifetimes troubles


#1

Hello.Please help me with:
Where are the tree of objects, this tree have been created in advance. We go from object to object(fn f1) and store in Element & to previous Element, and & to object, somewhere we return vector of &Object(fn collect)-this is incorrect case so I return Err).

I’ve made this for ids of objects, but when I add &Objects instead index, I have a lot of problems.
trait LinkTrait: Clone {
fn new(id: i32) -> Self;
}

struct Object<'a> {
    id: i32,
    next: Option<&'a Object<'a>>,
}

#[derive(Clone)]
struct Link {
    id: i32, //should be & Object
}

impl LinkTrait for Link {
    fn new(id: i32) -> Link {
        //should be & Object
        Link { id: id }
    }
}

struct Element<'a, L: LinkTrait + 'a> {
    prev: Option<&'a Element<'a, L>>,
    d: L,
}

fn collect<'a, L: LinkTrait + 'a>(current: &Element<'a, L>) -> Vec<L> {
    let mut cur = current;

    let mut v = Vec::new();

    loop {
        v.push(cur.d.clone());

        match cur.prev {
            Some(prev) => cur = prev,
            None => break,
        }
    }

    v
}

fn f1<'a, L: LinkTrait + 'a>(current: &'a Object, prev: &'a Element<'a, L>) -> Result<(), Vec<L>> {
    let cur_Element = Element {
        prev: Some(prev),
        d: L::new(current.id),
    };

    match current.next {
        Some(next) => f1(next, &cur_Element)?,
        None => {
            return {
                return Err(collect(&cur_Element));
            }
        }
    }

    Ok(())
}

fn main() {
    let Object3 = Object {
        id: 97,
        next: None,
    };
    let Object2 = Object {
        id: 9,
        next: Some(&Object3),
    };
    let Object1 = Object {
        id: 7,
        next: Some(&Object2),
    };

    let start = Element {
        prev: None,
        d: Link { id: Object1.id },
    };
    f1(&Object1, &start);
}

Please do not offer Box,Rc,Cell. There all may be made by borrowing.

Second question. This will be cool, if references to objects may be mutable(with Cell?)


Lets remove explicit lifetimes
#2

What you are trying to do here is not strictly impossible; but I don’t think it is possible the way you have written it. Writing Element as a recursive type forces many lifetimes to be equal, while your recursive calls to f1 force those same lifetimes to get successively narrower (as cur_Element lives shorter at each level).

Your life is five times easier with Vec::reverse():

#[derive(Debug)]
struct Object<'a> {
    id: i32,
    next: Option<&'a Object<'a>>,
}

fn collect<'a>(mut cur: &'a Object<'a>) -> Vec<&'a Object<'a>> {
    let mut v = vec![];
    loop {
        v.push(cur);

        match cur.next {
            Some(prev) => cur = prev,
            None => break,
        }
    }
    v.reverse();
    v
}

fn main() {
    let object3 = Object {
        id: 97,
        next: None,
    };
    let object2 = Object {
        id: 9,
        next: Some(&object3),
    };
    let object1 = Object {
        id: 7,
        next: Some(&object2),
    };

    println!("{:?}", collect(&object1));
}

#3

First off: This is not the kind of Rust code you should ever feel the need to write. The solution shown by ExpHP using Vec::reverse() is vastly more sane.

However, to show that it is possible to express your approach in Rust, here is a version that compiles with Object references in the Links:

#![allow(non_snake_case)]

trait LinkTrait<'a>: Clone {
    fn new(id: &'a Object<'a>) -> Self;
}

#[derive(Debug)]
struct Object<'a> {
    id: i32,
    next: Option<&'a Object<'a>>,
}

#[derive(Clone, Debug)]
struct Link<'a> {
    obj: &'a Object<'a>, //should be & Object
}

impl<'a> LinkTrait<'a> for Link<'a> {
    fn new(obj: &'a Object<'a>) -> Link<'a> {
        //should be & Object
        Link { obj: obj }
    }
}

struct Element<'a, 'b: 'a, L: LinkTrait<'b> + 'b> {
    prev: Option<&'a Element<'a, 'b, L>>,
    d: L,
    marker: std::marker::PhantomData<&'b Object<'b>>,
}

fn collect<'a, 'b, L: LinkTrait<'b>>(current: &Element<'a, 'b, L>) -> Vec<L> {
    let mut cur = current;

    let mut v = Vec::new();

    loop {
        v.push(cur.d.clone());

        match cur.prev {
            Some(prev) => cur = prev,
            None => break,
        }
    }

    v
}

fn f1<'a, 'b: 'a, L: LinkTrait<'b>>(current: &'b Object, prev: &'a Element<'a, 'b, L>) -> Vec<L> {
    let cur_Element = Element {
        prev: Some(prev),
        d: L::new(current),
        marker: std::marker::PhantomData,
    };

    match current.next {
        Some(next) => f1(next, &cur_Element),
        None => collect(&cur_Element),
    }
}

fn main() {
    let Object3 = Object {
        id: 97,
        next: None,
    };
    let Object2 = Object {
        id: 9,
        next: Some(&Object3),
    };
    let Object1 = Object {
        id: 7,
        next: Some(&Object2),
    };

    let start = Element {
        prev: None,
        d: Link { obj: &Object1 },
        marker: std::marker::PhantomData,
    };
    println!("{:?}", f1(&Object1, &start));
}

Playground

The main point here is that you need two separate lifetimes on your Element struct: One for the elements themselves (which are temporary and only live as long as f1 is running, and a second one for the Object references that are returned from f1 (and therefore need to live longer than the Elements.

(This also kind of answers your question from the “Let’s remove explicit lifetimes” thread about where you would need to manually annotate a Struct with multiple lifetimes instead of using one lifetime for everything.)

The PhantomData is used to prevent the compiler from complaining about an unused lifetime 'b. There might be a better way to express that, but I didn’t feel the desire to dig deeper, getting the code to compile was good enough for the moment. :wink:

One more note on you original code: f1 returned the Vec<L> as an Err (and would never, ever return Ok) which feels very backwards. I guess you arrived at this code by stripping down some larger code of yours, so maybe it made sense there.