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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.