CODEWITHSUNDEEP
rustownershipborrowing
JJW5432
JJW5432

Reputation: 707

Recursive data type that doesn't care about owning substructure

I often want to define recursive data type in Rust. We need some level of indirection to avoid having a type with unbounded size. The classic solution is to use Box (playground):

enum IntList {
    Empty,
    Cons(i32, Box<IntList>),
}

The problem I have with this it that it requires that the list own its own tail. This means you can't have space sharing between two lists that share a tail because both want to own it. You could use a borrowed reference (playground):

enum IntList<'a> {
    Empty,
    Cons(i32, &'a IntList<'a>),
}

But then it's hard to create a list because it's not allowed to own its own tail.

Is there a way to have the list not care whether or not it owns the tail? That way I could have one list own the tail and another list have a reference to that same list as its tail.

My Attempt

My first thought was to use Cow for this purpose, but I couldn't get it to work. This is what I tried (playground):

#[derive(Clone)]
enum IntList<'a> {
    Empty,
    Cons(i32, Cow<'a, IntList<'a>),
}

but it fails with error

error[E0275]: overflow evaluating the requirement `IntList<'a>: std::marker::Sized`
 --> src/main.rs:8:13
  |
8 |   Cons(i32, Cow<'a, IntList<'a>>),
  |             ^^^^^^^^^^^^^^^^^^^^
  |
  = note: required because of the requirements on the impl of `std::borrow::ToOwned` for `IntList<'a>`
  = note: required because it appears within the type `std::borrow::Cow<'a, IntList<'a>>`
  = note: no field of an enum variant may have a dynamically sized type

Upvotes: 2

Views: 541

Answers (2)

Tom&#225;s Vallotton
Tom&#225;s Vallotton

Reputation: 638

This may be too old but just for the record, if you want to make a linked list you can use std::rc::Rc. It's just like Box, but you can have more than one reference to a single object. The only caveat is that you can't mutate the list once it's enclosed in Rc. Here is an example from the rust book:

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
use std::rc::Rc;

fn main() {
    let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil))))); // [10, 5]
    let b = Cons(3, Rc::clone(&a)); // [10, 5, 3]
    let c = Cons(4, Rc::clone(&a)); // [10, 5, 4]
}

Upvotes: 0

JJW5432
JJW5432

Reputation: 707

I made a data type kind of like Cow that I called Cowish. If there is already something like this out there, please let me know!

pub enum Cowish<'a, T, O>
where
    T: 'a,
{
    Borrowed(&'a T),
    Owned(O),
}

impl<'a, T, O> Borrow<T> for Cowish<'a, T, O>
where
    T: 'a,
    O: Borrow<T>,
{
    fn borrow(&self) -> &T {
        match self {
            Borrowed(b) => b,
            Owned(o) => o.borrow(),
        }
    }
}

impl<'a, T, O> Cowish<'a, T, O>
where
    T: ToOwned<Owned=O> + 'a,
    O: Borrow<T>,
{
    pub fn into_owned(self) -> O {
        match self {
            Borrowed(b) => b.to_owned(),
            Owned(o) => o,
        }
    }
}

Using that, I can do what I wanted:

enum IntList<'a> {
    Empty,
    Cons(i32, Cowish<'a, IntList<'a>, Box<IntList<'a>>>),
}

A larger example can be found here.

Upvotes: 2

Related Questions