Is there a safe way to implement Graph/Finite Automata structures with references?

1

I'm looking to implement a finite automaton structure as a set of states, where each state has a HashMap to link it to the other states via reference, s.th. like:

pub struct State<T: Eq + Copy + Hash> {    
   // ...
   transitions: HashMap<T, &PfaState<T>>,
}

Also, each state has a label, so the overarching structure would be something like:

pub struct Automaton<T: Eq + Copy + Hash> {
    states: HashMap<Vec<T>, PfaState<T>>,
}

Is that even possible without unsafe Rust? I could only think of using unsafe features like this graph implementation: https://github.com/nrc/r4cppp/blob/master/graphs/src/ref_graph.rs, but obviously I'd like to evaluate the safe options first, and it seriously makes my head hurt ... double-borrowing the states map, lifetime issues, the whole protocol ...

Anybody got a hint how to do this safely ?

2

It is possible, but tricky, see: Borrow cycles in Rust: arenas v.s. drop-checking − Exyr.org.

The core idea is that you need mutation via interior mutability to complete reference cycles.

1 Like
3

I'd probably recommend having one big vector that stores a reference to every state using an Rc. Inside the states you can then use Weak to allow cycles between states without memory leaks. Ultimately you'll have just a single Rc to every state and a lot of Weaks.

If you combine this with RefCell, you can freely modify the state transitions.

1 Like
4

https://github.com/SimonSapin/rust-forest

there are some interesting examples of tree/graph data structures.

1 Like
5

Hmm some of those look promising, even though I must admit that trying to work around the borrow checking doesn't make the code any clearer ... looks cluttered and a bit ugly. Trade-off of some kind ... clear and unsafe or cluttered and safe ... I'll think about it.

1 Like
6

and very likely UB.

unsafe does not give you superpowers; it only lets you assume some of the correctness proof-checking responsibility from the compiler. If you read through the threads in this forum you'll see that, on most occasions, the borrow-checker is correct in detecting a problem and it is the programmer who unwittingly wrote code that is UB.

7

I know, and I'm aware of the advantages of the proof-checking, but also I've implemented similar data structures in many languages, and in Rust if feels surprisingly hard.

8

I mean, using a garbage collector makes it a lot easier to do.

9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.