Alternatives for self-referential structs in Rust?

Question

There are tons of questions about self-referential structs in Rust here, and I think I've read them all, but I'm still having trouble wrapping my head around things. What kind of design patterns exist for dealing with self-referential structs in Rust? I'll lay out my thinking so that others can tell me where I'm going wrong (I have a feeling it's at the beginning).

When I'm learning a new language I try to implement the same game, and for Rust I'm running into this problem: we have resources, some of which can be made from other resources. (Let's say they form a DAG.)

My naive attempt to model it is this:

struct Resource {
  name: String,
  production_cost: HashMap<&Resource, i32>,
  // other data
}

We need a lifetime annotation for the reference, so it becomes Resource<'a> with a HashMap<&'a Resource, i32>.

A Vec<Resource> of this form is impractical (impossible?) to build, so another attempt would be to go up a level:

struct Resource {
  name: String,
  // other data
}

struct ResourceConfig {
  resources: Vec<Resource>,
  resource_costs: HashMap<&Resource, HashMap<&Resource, i32>>,
}

I can't figure out a way to construct one of these, either. The next two options I can come up with are:

1. Wrap everything in RefCell/Rc's (or Arc/Mutexes). This seems to require way too much typing, not to mention the reference counting performance overhead (which I'm sure is trivial in my case).
2. Pass around indices to a master vector.

So the end result (2) looks like:

type RIndex = usize;
type ResourceSet = HashMap<RIndex, i32>;

struct Resource {
  name: String,
  // other data
}

struct ResourceConfig {
  resources: Vec<Resource>,
  resource_costs: HashMap<RIndex, ResourceSet>,
}

And the rest of the code just passes around a bunch of RIndex'es (and holds on to a &ResourceConfig reference to do the conversion). I can upgrade RIndex from a type alias to a newtype for type safety at the cost of keystrokes (probably worth it?), but in the end I feel like I'm just doing my own pointer management--instead of worrying about invalid/null pointers I'm worrying about getting a RIndex out of range.

What am I missing here? (Unsafe code?)

In C++, I would do something like:

class Resource {
  std::string name;
  std::unordered_map<Resource*, int> production_cost;
  // Probably wrap the unordered_map in its own class, maybe with a Resource reference, etc.
}

(Sure, I'd lose the lifetime guarantees but the resources would all live in the same object somewhere so it wouldn't really be hard to make work.)

Answer 1

Pass around indices to a master vector.

You are describing an arena – a vector of structs that can link to each other via indices. There are some nice crates that let you do this, and provide some compile-time checks.

In your case, we can go one step further – since you don't need to destroy a resource type once it's been created, all of the resources can live for the same lifetime (once created). Therefore, you should in theory be able to have items in the arena reference each other. typed-arena lets you do just that!

use typed_arena::Arena;

fn main() {
    let resources = Arena::<Resource>::default();

    let iron = resources.alloc(Resource {
        name: "iron".to_string(),
        cost: vec![],
    });
    let water = resources.alloc(Resource {
        name: "water".to_string(),
        cost: vec![],
    });
    let rust = resources.alloc(Resource {
        name: "rust".to_string(),
        cost: vec![iron, water],
    });

    println!("{iron:?}");
    println!("{water:?}");
    println!("{rust:?}");
}

#[derive(Debug)]
struct Resource<'a> {
    name: String,
    cost: Vec<&'a Resource<'a>>,
}

Resource { name: "iron", cost: [] }
Resource { name: "water", cost: [] }
Resource { name: "rust", cost: [Resource { name: "iron", cost: [] }, Resource { name: "water", cost: [] }] }