4
\$\begingroup\$

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 }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ There's no reason at all you can't use a Box to model this tree: play.rust-lang.org/… \$\endgroup\$ – Erich Gubler Jul 10 '18 at 4:14
  • \$\begingroup\$ As long as you don't use Rc::from_raw both Rc and RefCell have a safe API. \$\endgroup\$ – ljedrz Jul 10 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.