Generic types, ownership, and persistent data structures

Question

TL;DR How do I build data structures over generic types that reference shared underlying data?

This question is about both semantics and good data modeling in Rust. The code below is a (more) trivial distillation of my problem to highlight my specific question, not my actual code.

The goal is to make a function that builds several vectors that contain references to shared data of a generic type. In the nomenclature of the following example I want to be able to return a collection of vectors that can store both Struct1's and Struct2's (abstracted by the trait Trait), however since (in my real code) Struct1 and Struct2 are relatively large and will be stored in relatively many places relatively frequently, I'd rather store references to shared data, not copy them all over the place.

The current problem I'm facing (and there've been many intermediate revisions) is that:

1. Since the type of data I'm trying to store are Trait, which aren't Sized I need to store references in my vectors
2. Since each struct will be referenced from multiple vectors, an & reference is necessary
3. Philosophically, there is no singular "owner" of a given struct, therefore no "right" place to stick my structs so they don't go out of scope with the build_vectors function.
   1. I considered trying to resolve this via a global vector of Traits into which I could point references, unfortunately issue (1) above seems to preclude that strategy.

.

struct Struct1;
struct Struct2;

trait Trait { fn name(&self) -> &str; }
impl Trait for Struct1 { fn name(&self) -> &str { "Struct1" } }
impl Trait for Struct2 { fn name(&self) -> &str { "Struct2" } }

fn shallow_copy<'a>(v: &'a Vec<&'a Box<Trait>>) -> Vec<&'a Box<Trait>> {
   v.iter().map(|x|*x).collect()
}

fn build_vectors<'a>() -> (Vec<&'a Box<Trait>>, Vec<&'a Box<Trait>>) {
  let box_struct1: &Box<Trait> = &(Box::new(Struct1) as Box<Trait>);
  let box_struct2: &Box<Trait> = &(Box::new(Struct2) as Box<Trait>);

  let vec1: Vec<&Box<Trait>> = vec![box_struct1];
  let mut vec2: Vec<&Box<Trait>> = shallow_copy(&vec1);

  vec2.push(box_struct2);

  (vec1, vec2)
}

fn join_names(v: &Vec<&Box<Trait>>) -> String {
   v.iter().map(|s| s.name()).collect::<Vec<_>>().connect(" ")
}

fn main() {
  let (vec1, vec2) = build_vectors();

  println!("vec1: {}", join_names(&vec1));
  println!("vec2: {}", join_names(&vec2));
}

The desired output is:

vec1: Struct1
vec2: Struct1 Struct2

Answer 1

This sounds like a perfect use case for Rc. Rc is a reference-counted type that allows you to have multiple owners to the same value.

use std::rc::Rc;

struct Struct1;
struct Struct2;

trait Trait { fn name(&self) -> &str; }
impl Trait for Struct1 { fn name(&self) -> &str { "Struct1" } }
impl Trait for Struct2 { fn name(&self) -> &str { "Struct2" } }

fn shallow_copy<'a>(v: &[Rc<Trait + 'a>]) -> Vec<Rc<Trait + 'a>> {
   v.iter().map(|x| x.clone()).collect()
}

fn build_vectors() -> (Vec<Rc<Trait>>, Vec<Rc<Trait>>) {
  let vec1: Vec<Rc<Trait>> = vec![Rc::new(Struct1)];
  let mut vec2: Vec<Rc<Trait>> = shallow_copy(&vec1);

  vec2.push(Rc::new(Struct2));

  (vec1, vec2)
}

fn join_names<'a>(v: &[Rc<Trait + 'a>]) -> String {
   v.iter().map(|s| s.name()).collect::<Vec<_>>().connect(" ")
}

fn main() {
  let (vec1, vec2) = build_vectors();

  println!("vec1: {}", join_names(&vec1));
  println!("vec2: {}", join_names(&vec2));
}

Note that the closure in shallow_copy uses clone() to clone the Rc. Cloning an Rc creates a new Rc that points to the same value (the underlying value is not cloned), and the shared reference count is increased by 1. Dropping an Rc decrements the reference count, and when the reference count drops to zero, the underlying value is dropped.

By the way, I've changed some functions to take slice references instead of Vec references, because it makes the functions more general (you can get slices from arrays too, for example).

Also, I had to annotate trait objects with a lifetime, because without an annotation, the compiler assumes 'static (i.e. Trait + 'static), which means "an implementation of Trait that doesn't contain any borrowed pointers (that are shorter than 'static)", and that caused lifetime errors.