Maybe a Dumb Borrow Question

[Yiab]

Given a trait WeirdTrait which includes the function fn get_thing(&self) -> Option<&Self::AssocType> where I get to write all of the code for the implementation of MyStruct, is there any way I can get the following type of implementation of get_thing to work?

impl WeirdTrait for Something {
    type AssocType = MyStruct;
    fn get_thing(&self) -> Option<&MyStruct> {
        let answer = MyStruct::new();
        Some(&answer)
    }
}

In other words, is there any way to return an owned object in place of a borrow of the same type?
I'm hoping for some kind of trait which means "when you borrow an object of this type, clone it instead" or something similar.

[OptimisticPeach]

Not really, unless it's a 'static reference, which applies to unit Structs and &'static strs and some other edge cases.

These edge cases include but are not limited to the following:

• Numbers that are hard-coded
  • f32, f64, usize, isize, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128
• Strings that are hard-coded
  • "Some text"
  • b"Some text"
  • include_str!
  • include_bytes!
• chars that are hard-coded
  • 'x'
  • b'x'
• bools that are hard-coded
  • true, false
• unit
  • ()
• Unit struct
  • std::marker::PhantomPinned
  • std::marker::PhantomData<T> unless the lifetimes conflict
  • struct S
• Never type
  • &loop{}
  • &panic!
  • &unreachable!
• Pre-defined structs, enums and unions (Edge cases)
  • struct Foo(usize) and Foo(30)
  • struct Foo{x: usize} and &Foo {x: 30}
  • Etc.

[RustyYato]

Fundamentally a borrow is temporary, and it must come from somewhere. When you return a borrow, you are asserting that it came from one of the inputs, or if there are no such inputs, that it came from global state (which is what @OptimisticPeach showed with 'static). In the case of WeirdTrait, by saying fn get_thing(&self) -> Option<&MyStruct>, you are asserting that the output comes from self. So you can't return something that comes from the local stack of the function (i.e. answer).

What are you trying to do? (This looks like a toy example, what is your actual problem) We can help you fix that, because what you are asking for is impossible to do soundly.

[Yiab]

Okay, here's the situation: I'm taking a course that involves abstract data types, and I'm trying to learn more about them and get better at Rust by implementing these abstract data types in Rust. There are three of these data types based on binary trees: Binary Search Trees, AVL Trees, and Heaps (binary heaps, specifically). I've made a pair of traits to represent recursively defined binary trees with the following relevant parts of their signatures:

trait BinTreeNode {
    type ObjectType: Eq;
    fn get_left_chid(&self) -> Option<&Self>;
    fn get_right_child(&self) -> Option<&Self>;
    fn get_data(&self) -> Option<&Self::ObjectType>;
}

trait BinTree {
    type ObjectType: Eq;
    type NodeType: BinTreeNode<ObjectType=Self::ObjectType>;
    fn get_root(&self) -> Option<&Self::NodeType>;
}

I've already implemented Binary Search Trees and AVL Trees with these traits (with the added restriction that ObjectType: Ord), and I wrote a display function to print a tree to the command line in a human-readable format (so long as ObjectType: Debug as well) which uses these traits. Now I'd like to implement Binary Heaps.

My first thought for implementing a Binary Heap is to store the data in a Vec<Self::ObjectType>, but I still need something to implement BinTreeNode if I want to use these traits and display function, so I tried writing something along the following lines:

struct Heap<T: Ord> {
    data: Vec<T>,
}
...
struct HeapNode<'a,T: Ord> {
    heap: &'a Heap<T>,
    index: usize,
}
impl<'a,T: Ord> BinTreeNode for HeapNode<'a,T> {
    type ObjectType = T;
    fn get_data(&self) -> Option<&T> {
        self.heap.data.get(self.index)
    }
    fn get_left_child(&self) -> Option<&HeapNode<'a,T>> {
        &HeapNode { heap: self.heap, index: 2*self.index }
    }
}

But of course that wouldn't work because I'm returning a borrow of an object which will get dropped at the end of the function call.
I could try to implement a Heap recursively instead, which would solve this particular problem, but that would make it significantly more complicated to insert a new piece of data into a heap, unless I'm missing something.
Is there some reasonable way to accomplish what I'm trying to do here?

[RustyYato]

It looks like the only way to conform to your traits is by defining the heap recursively. You could change you traits to take another associated type like so

trait BinTreeNode<'a> {
    type ObjectType: Eq;
    type ChildNode: 'a;
    
    fn get_left_chid(&'a self) -> Option<Self::ChildNode>;
    fn get_right_child(&'a self) -> Option<Self::ChildNode>;
    fn get_data(&self) -> Option<&Self::ObjectType>;
}

But there are probably more changes than just this.

You can then implement it for Heap like so

impl<'a, T: Eq> BinTreeNode<'a> for Heap<T> {
    type ObjectType = T;
    type ChildNode = usize;
    
    fn get_left_chid(&'a self) -> Option<usize> { ... }
    fn get_right_child(&'a self) -> Option<usize> { ... }
    fn get_data(&self) -> Option<&T> { ... }
}

impl<'a, T: Eq> BinTreeNode<'a> for BST<T> { // binary search tree
    type ObjectType = T;
    type ChildNode = &'a Self;
    
    fn get_left_chid(&'a self) -> Option<&'a Self> { ... }
    fn get_right_child(&'a self) -> Option<&'a Self> { ... }
    fn get_data(&self) -> Option<&T> { ... }
}

Do note that this may be more complex than converting your heap to a recursive definition.