Rust, graphs, raw memory, and arena allocators

Context

Rust is a very solid language to build safe programs, when one can abide by its memory model and contrainsts : an object must have a unique owner. This constraint enable rust compiler to statically check the program, and avoid numerous bugs which would lead to undefined behaviours, race conditions, and other nasty deadly memory overlap bugs.

Objective

However, when one wants to manage more complex structured data like graphs, where nodes can reference each others, it is very difficult to work within the "single ownership" model. This article will track my learnings and experiments around the darker, unsafe rituals needed to work as safely as possible whith graph structures.

Some leads to investigate

• Rust Petgraph crate,
• Rust unsafe keyword use and raw pointers.(see the rustonomicon),
• Manual Arena allocator (CAD97),
• Slice-dst crate

Graph model and foreseen implementation

I would like to base my graph model on the hypergraphdb approach, as found in the paper hypergraphDB A Genealized Graph Database.

The hypergraph is composed of :

• atoms : nodes, directed edges, and hyperedges (like ordered set of nodes, or n-ary relationships)...
• kinds : types (but type is a reserved rust keyword)
• values : primitive or complex types

An Atom is used to represent a structure element of the hypergraph. In rust, it is composed of :

• an Id,
• a Kind,
• a Value, of type Kind,
• a vector of targets ids

A Kind is also stored as an Atom.