I wrote a finite automata implementation in C years ago. C's access to mutable, unsafe, raw pointers made it quite simple for me to link/relink the states of a finite automata.
I read the official Rust Book and wanted to rewrite it in Rust. I ran into problems with recursive references (individual state nodes acting as a linked list). The only thing I could think of is to use Rc<RefCell<State>>
- which, as I understand it, are essentially the "unsafe" raw pointers Rust aims to minimize. Am I overthinking it or is this OK Rust code?
use std::cell::RefCell;
use std::rc::Rc;
type RefState = Rc<RefCell<State>>;
#[derive(Clone)]
enum State {
Symbols(RefState, String),
Epsilon(RefState),
SplitEpsilon(RefState, RefState),
Accepting
}
pub struct Sequence {
start: RefState,
end: RefState
}
impl State {
fn wrap(self) -> RefState {
Rc::new(RefCell::new(self))
}
fn accepting() -> RefState {
Rc::new(RefCell::new(State::Accepting))
}
fn symbols(chars: &str, connect: RefState) -> RefState {
Rc::new(RefCell::new(
State::Symbols(connect, chars.to_string())
))
}
fn epsilon(connect: RefState) -> RefState {
Rc::new(RefCell::new(
State::Epsilon(connect)
))
}
fn split(connect1: RefState, connect2: RefState) -> RefState {
Rc::new(RefCell::new(
State::SplitEpsilon(connect1, connect2)
))
}
}
impl Sequence {
pub fn concat(mut self, other: Sequence) -> Sequence {
*(self.end.borrow_mut()) = State::Epsilon(other.start);
self.end = other.end;
self
}
pub fn union(mut self, other: Sequence) -> Sequence {
let end = State::accepting();
let start = State::split(self.start.clone(), other.start.clone());
*(self.end.borrow_mut()) = State::Epsilon(end.clone());
*(other.end.borrow_mut()) = State::Epsilon(end.clone());
self.start = start;
self.end = end;
self
}
pub fn star(mut self) -> Sequence {
let end = State::accepting();
let split = State::SplitEpsilon(self.start.clone(), end.clone());
let start = split.clone().wrap();
*(self.end.borrow_mut()) = split;
self.start = start;
self.end = end;
self
}
pub fn symbols(chars: &str) -> Sequence {
let end = State::accepting();
let start = State::symbols(chars, end.clone());
Sequence { start, end }
}
}
Box
to model this tree: play.rust-lang.org/… \$\endgroup\$ – Erich Gubler Jul 10 '18 at 4:14Rc::from_raw
bothRc
andRefCell
have a safe API. \$\endgroup\$ – ljedrz Jul 10 '18 at 8:09