Can I do in Rust the same things that I do in C++?

I would like to implement in Rust an idea that I have already developed in C++ but I'm not very sure what the best way is.
I would like to make a transition diagram interpreter that models the behavior of a finite state automata.
fsa
The transition diagram is a constant data structure whcih consists of a set of states.
Each state is a collection of arrows (coming out from the state of which they are part) and each arrow is composed by 3 elements:

  1. the event that allows to cross the arrow
  2. the action to perform when the arrow is run through
  3. the pointer to the state reached by following the arrow.
    In this way each instance of an interpreter of a transition diagram is constructed by passing it the pointer to the starting state.
    Each instance of the interpreter of a transition diagram offers a method to process an incoming event: the input event is searched for by scrolling the list of arrows that constitute the current state and when correspondence is found between the input event and the which enables crossing an arrow, the action associated with the found arrow is performed and the current state is set to the one reached by traversing the found arrow.

Since the events only need to be distinguishable from each other, I tried to create a trait that does so.
However, I find it difficult to model a state because in Rust arrays have a fixed size while in C++ I could write something like:

#include <stdio.h>
#define elementOf(a) (sizeof(a)/sizeof(a[0]))

class FSA_Event {
public:
    virtual bool equal(FSA_Event *ev) = 0;
};

class MyEvent : public FSA_Event {
    int i;
public:
    MyEvent(int v) : i(v) {}

    virtual bool equal(FSA_Event *ev) {
        // 0 event is by definition equal to any other MyEvent 
        return ((0 == ((MyEvent*)ev)->i) || (i == ((MyEvent*)ev)->i));
    }
};

// Event Instances
MyEvent ev1 = {1}, ev2 = {2}, ev3 = {3}, star = {0};

// Forward Declarations
struct FSA_Arrow;
struct FSA_State;

typedef void (FSA_Action) (FSA_Event *ev, void *usrObj);

struct FSA_Arrow {
    FSA_Event *ev;
    FSA_Action *act;
    FSA_State *nextSt;
};

struct FSA_State {
    unsigned int elementOfArrowsArray;
    FSA_Arrow *arrowsArray;
};

// External State Declarations
extern FSA_State st1, st2, st3;

// Action Function Macros
#define ACT_PROT(num) void Act_##num (FSA_Event *ev, void *usrObj);
#define ACT_BODY(num) void Act_##num (FSA_Event *ev, void *usrObj) { \
    printf("ACT_%d\n", num); \
}
#define ACT(num) ACT_PROT(num) ACT_BODY(num)

// Define Actions
ACT(1)
ACT(2)
ACT(3)
ACT(4)
ACT(5)
ACT(6)
ACT(7)

// State Transitions for st1
FSA_Arrow arrows_st1[] = { 
    {&ev1, Act_3, &st3},
    {&star, Act_7, &st1}
};
FSA_State st1 = {elementOf(arrows_st1), arrows_st1};

// State Transitions for st2
FSA_Arrow arrows_st2[] = { 
    {&ev1, Act_1, &st1},
    {&ev2, Act_2, &st3},
    {&star, Act_7, &st1} 
};
FSA_State st2 = {elementOf(arrows_st2), arrows_st2};

// State Transitions for st3
FSA_Arrow arrows_st3[] = {  
    {&ev2, Act_4, &st1},
    {&ev1, Act_3, &st2},
    {&star, Act_7, &st1} 
};
FSA_State st3 = {elementOf(arrows_st3), arrows_st3};

class FSA {
    void *usrObj;
    FSA_State *st;
public:
    FSA(FSA_State *begin, void* userObject) : st(begin), usrObj(userObject) {}

    bool exe(FSA_Event *ev) {
        for (unsigned i = 0; i < st->elementOfArrowsArray; i++) {
            if (ev->equal(st->arrowsArray[i].ev)) {
                st->arrowsArray[i].act(ev, usrObj);
                st = st->arrowsArray[i].nextSt;
                return true;
            }
        }
        return false;
    }
};

int main() {
    printf("begin\n");
    FSA fsa(&st1, NULL);

    fsa.exe(&ev1);  // expected to print ACT_3
    fsa.exe(&ev2);  // expected to print ACT_4
    fsa.exe(&ev3);  // expected to print ACT_7 (managing unexpected events)

    printf("END\n");
    return 0;
}

My attempts to recode older code in Rust are below and they are really poor... :sneezing_face:

pub trait FsaEvent {
    fn equal(&self, other: &dyn FsaEvent) -> bool;
}

type FsaAction = fn(&dyn FsaEvent) -> bool;

struct Arrow<'a> {
    ev: &'a dyn FsaEvent,
    act: FsaAction,
}

fn main() {
    println!("Hello, world!");
}

Do you have any suggestions?
Thanks in advance!
Greetings

Are you planning to hard-code a particular state machine (or a few) into your program, or do you need to write code that handles arbitrary state machines at runtime? Both are possible in Rust, but the idiomatic solution is different between the two cases:

  • A hardcoded state machine will probably be implemented as an enum with one variant per state and appropriate methods to drive the machine (possibly implemented with the help of a macro)
  • A runtime interpreter will probably be a struct that contains the transition table as a vector or hashmap, and a separate cursor struct that represents the current state of a single machine instance.
5 Likes

Of course.

If you just want to implement some state machine in Rust can be as simple as creating a enum for the states and putting a match statement in a loop that receives the events the dispatches the right handler depending on the enum. Same like you might do in C.

Interpreting an arbitrary state machine or compiling some state machine definition into Rust code that runs it is a bit harder but I'm sure it can be done, after all the Rust compiler is written in Rust.

Have a google for "state machines in rust" for all kind of approaches to this.

first of all, I would suggest against "translating" existing code (e.g. from C++) to rust, as it's generally results sub-optimal and non-idiomatic code. that being said, it can be a start point for people from other languages to learn rust. just keep in mind it's might give you sub-optimal result.

as suggested by others, simple state machines are typically modeled using enums. but just to answer your specific questions:

your original C++ code is very OO heavy, and rust in general tends to encourage non-OO style programming. a simple enum would suffice for such use case:

#[derive(Clone, Copy, PartialEq, Eq)]
enum Event {
    Star,
    Ev1,
    Ev2,
    Ev2,
}

in fact, C++ arrays have fixed sizes too, it's just C++ have array to pointer decay, and the call site actually need a pointer so you can use pass arrays with different sizes. the same effect (at least same as your example code) can be emulated in rust using slices.

static ST1: State = State {
    arrows: &[
        Arrow::new(Event::Ev1, act3, &ST3),
        Arrow::new(Event::Star, act7, &ST1),
    ]
};

the type State, Arrow and such can be defined like:

type Action = &'static dyn FnMut(Event);
struct Arrow {
    trigger: Event,
    action: Action,
    next: &'static State,
}
struct State {
    arrows: &'static [Arrow],
}
fn act1(ev: Event) {
    println("act 1");
}

as I said, "translating" from C++ to rust is a bad idea, especially if the original C++ code is deep in OO paradigm. OO code tends to form interconnected messy data structure using pointers, which is not easy to do in rust (which is a good thing).

your original code can be translated to rust, because they are all defined statically, here's one naive translated version:

however, if the state machine is not statically defined, it's not as trivial as this one. on the other hand, I would probably write the same logic like this:

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Event {
	Start,
	E1,
	E2,
	E3,
}

type Action = fn(Event);

fn act<const NUM: usize>(_: Event) {
	println!("ACT_{NUM}");
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum State {
	St1,
	St2,
	St3,
}

fn step(current: State, event: Event) -> Option<(State, Action)> {
	match (current, event) {
		(_, Event::Start) => Some((State::St1, act::<7>)),
		(State::St1, Event::E1) => Some((State::St3, act::<3>)),
		(State::St2, Event::E1) => Some((State::St1, act::<1>)),
		(State::St2, Event::E2) => Some((State::St3, act::<2>)),
		(State::St3, Event::E1) => Some((State::St2, act::<3>)),
		(State::St3, Event::E2) => Some((State::St1, act::<4>)),
		_ => None,
	}
}
5 Likes

I’ve tried to make a close translation of the C++ code for the fun of it… don’t interpret this as idiomatic Rust in any way, please :wink:

// #include <stdio.h>
// #define elementOf(a) (sizeof(a)/sizeof(a[0]))

// class FSA_Event {
// public:
//     virtual bool equal(FSA_Event *ev) = 0;
// };
pub trait FsaEvent: 'static {
    fn equal(&self, ev: &Self) -> bool;
}

// class MyEvent : public FSA_Event {
//     int i;
// public:
//     MyEvent(int v) : i(v) {}

//     virtual bool equal(FSA_Event *ev) {
//         // 0 event is by definition equal to any other MyEvent
//         return ((0 == ((MyEvent*)ev)->i) || (i == ((MyEvent*)ev)->i));
//     }
// };
struct MyEvent {
    i: u16,
}
impl MyEvent {
    const fn new(v: u16) -> Self {
        Self { i: v }
    }
}

impl FsaEvent for MyEvent {
    fn equal(&self, ev: &Self) -> bool {
        // 0 event is by definition equal to any other MyEvent
        0 == ev.i || self.i == ev.i
    }
}

// // Event Instances
// MyEvent ev1 = {1}, ev2 = {2}, ev3 = {3}, star = {0};
static EV1: MyEvent = MyEvent::new(1);
static EV2: MyEvent = MyEvent::new(2);
static EV3: MyEvent = MyEvent::new(3);
static STAR: MyEvent = MyEvent::new(0);

// // Forward Declarations
// struct FSA_Arrow;
// struct FSA_State;

// typedef void (FSA_Action) (FSA_Event *ev, void *usrObj);
type FsaAction<E, O> = fn(&E, &mut O);

// struct FSA_Arrow {
//     FSA_Event *ev;
//     FSA_Action *act;
//     FSA_State *nextSt;
// };
struct FsaArrow<E: FsaEvent, O: 'static> {
    ev: &'static E,
    act: FsaAction<E, O>,
    next_st: &'static FsaState<E, O>,
}

impl<E: FsaEvent, O: 'static> FsaArrow<E, O> {
    const fn new(ev: &'static E, act: FsaAction<E, O>, next_st: &'static FsaState<E, O>) -> Self {
        Self { ev, act, next_st }
    }
}

// struct FSA_State {
//     unsigned int elementOfArrowsArray;
//     FSA_Arrow *arrowsArray;
// };
struct FsaState<E: FsaEvent, O: 'static> {
    arrows_array: &'static [FsaArrow<E, O>],
}

// // External State Declarations
// extern FSA_State st1, st2, st3;

// // Action Function Macros
// #define ACT_PROT(num) void Act_##num (FSA_Event *ev, void *usrObj);
// #define ACT_BODY(num) void Act_##num (FSA_Event *ev, void *usrObj) { \
//     printf("ACT_%d\n", num); \
// }
// #define ACT(num) ACT_PROT(num) ACT_BODY(num)
macro_rules! act {
    ($num:literal) => {
        paste::paste! {
            fn [<act_ $num>](_ev: &MyEvent, _usr_obj: &mut ()) {
                println!("ACT_{}", $num)
            }
        }
    };
}

// // Define Actions
// ACT(1)
// ACT(2)
// ACT(3)
// ACT(4)
// ACT(5)
// ACT(6)
// ACT(7)

act! {1}
act! {2}
act! {3}
act! {4}
act! {5}
act! {6}
act! {7}

// // State Transitions for st1
// FSA_Arrow arrows_st1[] = {
//     {&ev1, Act_3, &st3},
//     {&star, Act_7, &st1}
// };
// FSA_State st1 = {elementOf(arrows_st1), arrows_st1};

static ARROWS_ST1: &[FsaArrow<MyEvent, ()>] = &[
    FsaArrow::new(&EV1, act_3, &ST3),
    FsaArrow::new(&STAR, act_7, &ST1),
];
static ST1: FsaState<MyEvent, ()> = FsaState {
    arrows_array: ARROWS_ST1,
};

// // State Transitions for st2
// FSA_Arrow arrows_st2[] = {
//     {&ev1, Act_1, &st1},
//     {&ev2, Act_2, &st3},
//     {&star, Act_7, &st1}
// };
// FSA_State st2 = {elementOf(arrows_st2), arrows_st2};

static ARROWS_ST2: &[FsaArrow<MyEvent, ()>] = &[
    FsaArrow::new(&EV1, act_1, &ST1),
    FsaArrow::new(&EV2, act_2, &ST3),
    FsaArrow::new(&STAR, act_7, &ST1),
];
static ST2: FsaState<MyEvent, ()> = FsaState {
    arrows_array: ARROWS_ST2,
};

// // State Transitions for st3
// FSA_Arrow arrows_st3[] = {
//     {&ev2, Act_4, &st1},
//     {&ev1, Act_3, &st2},
//     {&star, Act_7, &st1}
// };
// FSA_State st3 = {elementOf(arrows_st3), arrows_st3};

static ARROWS_ST3: &[FsaArrow<MyEvent, ()>] = &[
    FsaArrow::new(&EV2, act_4, &ST1),
    FsaArrow::new(&EV1, act_3, &ST2),
    FsaArrow::new(&STAR, act_7, &ST1),
];
static ST3: FsaState<MyEvent, ()> = FsaState {
    arrows_array: ARROWS_ST3,
};

// class FSA {
//     void *usrObj;
//     FSA_State *st;
// public:
//     FSA(FSA_State *begin, void* userObject) : st(begin), usrObj(userObject) {}

//     bool exe(FSA_Event *ev) {
//         for (unsigned i = 0; i < st->elementOfArrowsArray; i++) {
//             if (ev->equal(st->arrowsArray[i].ev)) {
//                 st->arrowsArray[i].act(ev, usrObj);
//                 st = st->arrowsArray[i].nextSt;
//                 return true;
//             }
//         }
//         return false;
//     }
// };
struct Fsa<E: FsaEvent, O: 'static> {
    st: &'static FsaState<E, O>,
    usr_obj: O,
}

impl<E: FsaEvent, O: 'static> Fsa<E, O> {
    fn new(begin: &'static FsaState<E, O>, usr_object: O) -> Self {
        Self { st: begin, usr_obj: usr_object }
    }
    fn exe(&mut self, ev: &E) -> bool {
        for arrow in self.st.arrows_array {
            if ev.equal(arrow.ev) {
                (arrow.act)(ev, &mut self.usr_obj);
                self.st = arrow.next_st;
                return true;
            }
        }
        false
    }
}

// int main() {
//     printf("begin\n");
//     FSA fsa(&st1, NULL);

//     fsa.exe(&ev1);  // expected to print ACT_3
//     fsa.exe(&ev2);  // expected to print ACT_4
//     fsa.exe(&ev3);  // expected to print ACT_7 (managing unexpected events)

//     printf("END\n");
//     return 0;
// }

fn main() {
    println!("begin");
    let mut fsa = Fsa::new(&ST1, ());

    fsa.exe(&EV1);  // expected to print ACT_3
    fsa.exe(&EV2);  // expected to print ACT_4
    fsa.exe(&EV3);  // expected to print ACT_7 (managing unexpected events)

    println!("END");
}

Rust Playground

a few issues encountered that I had to address (in order to stay within safe Rust code):

  • the ownership situation if the C++ code is not entirely clear - the only use-case involves a lot of globally defined instances of all the structs, so I chose &'static … references in Rust. This does however seem unnecessarily unflexible - or put differently, if all state machines must be compile-time things anyways, then the whole dynamic structure of the code could be replaced by more hard-coded stuff, where we just have transition functions instead if a data structure with concrete lists of arrows. If dynamically generated state machines should be supported, too, then some illustrative such use-case would be helpful to find the right kind of representation of the code in Rust.

  • the array in C++ represented in FSA_State by a pair of pointer and length (and user-code that would trigger UB if the length information was somehow mixed up) got represented using a single (wide) slice pointer in Rust.

  • the abstraction around FSA_Event was weird. Well… as far as I could tell, in principle, with all the FSA_Event * pointers, a heterogeneous instantiation could have been possible where a single state machine contains different event types. On the other hand, the implementation of MyEvent::equal involves a type cast, signalling a homogeneous case is assumed, i.e. MyEvent assumes all other events it comes across to be MyEvent, too.
    I’ve gone with a generic approach in Rust, where Fsa has a type parameter speficying the homogeneous event type. Alternatives are possible, too, though; e.g. in Rust, the cast in question could be made using dynamic type-checking with dyn Any. The C++ code doesn’t sufficiently explain itself in this regard

  • the same goes for void *usrObj which seemed safer with a generic type parameter instead of a void pointer. The use case example didn’t really use this capability at all, anyways, though.

  • in line with this, the arr_n transition functions seem to be generated for the concrete use case at hand, so in my Rust version they needed to operate on the known concrete types MyEvent and () for the usr_obj, as that’s just a dummy object / not used.

  • macros that generate new names in Rust are not easily possible without some helper crate, in this case the paste crate. For local usage, add it to your current crate as dependency using cargo add paste, though this popular crate is even available in the playground.

While sharing this in a playground I noticed that stable Rust has this code run into a minor compiler limitation around &mut … reference types appearing too directly inside constants. This could probably easily be worked around, too, but starting from the upcoming Rust version (currently in beta) it seems fixed, anyways.

7 Likes

From the bottom of my heart, Thank you community for the help, even quick!
You will certainly have understood that I am studying Rust and for now I have read the first 5 chapters of The Book plus almost all of chapter 10. I thought I knew enough to start getting involved but...

Since the C++ code I wrote didn't seem so transparent I'll try to add some reasons why it's written like this.

  1. first of all the code I posted was very simplified and this explains why some things like usrObj are not used.
  2. the intention with which I wrote this code is to create a generic engine (the FSA class) that accepts as input the description of the desired behavior in response to a stimulus (which for me here are the transition diagrams, i.e. the set of the static FSA_State objects) and which, once thus instructed, processes the incoming events in a deterministic way. Providing this engine to my colleagues I've standardized the way finite state automata were designed (i.e. increased code readability) and also I've simplified the debugging because - in the example I posted it is not present - it is easy to add to the FSA class a command-printable history that produces the last N pairs (name of the current state, name of the incoming event). Wanting to write a generic engine, I couldn't make assumptions about the nature of the events (in some cases they can be protocol messages, in others user commands, ...) and so I limited myself to writing FSA_Event which models the only requirement imposed by FSA to events. In summary I provide my users with an abstract event model and the FSA engine and users write their concrete events and transition diagrams.
  3. in the code I posted it is not present, but the original FSA_Action actually returns either NULL or the address of an FSA_State: this is the way to handle exceptions that may arise during the execution of FSA_Action. It's a sort of goto to be used extremely sparingly.
  4. an FSA_Action receives two things in input: a) the pointer to the event that triggered the FSA_Action execution b) a pointer to the user's data: in fact in practice the functions are not limited to making printouts but do things that operate on the data that must therefore be passed to them. FSA must ignore the logic/user data and for this reason receives a void* as a pointer to the user data and passes it back every time a FSA_Action is called
  5. if a user provides me with a transition diagram that for example implements an HDLC protocol, the same transition diagram is capable of managing N channels as long as each channel is associated with an FSA instance.
  6. my original code also provides a way to process incoming events either in the caller context or in a separate thread

My wish would be to replicate this in RUST and make it available to everyone as a crate. I will succeed? With your help I hope so!

I would also appreciate comments if what I have described is just my vision or if it might be of general interest.

Thanks again to everyone!
... and merry Christmas!

2 Likes

in rust, usually you can implement callbacks using closures, which can capture arbitrary environments, so typically callbacks doesn't need a opaque "context" parameter (unless you are interop with FFI of course, but it's usually encapsulated in a "wrapper" layer and the rust code can still use closures)

in short, in C++, a callbakc with a function pointer plus a opaque data pointer is roughly equivalent to a "fat" pointer to a Fn trait object in rust. for totally static cases, you can use &'static dyn Fn(), but generally Box<dyn Fn()> is often used.

it's not necessary to resort to dynamic dispatch, you can implement it as generic types, unless your intended use cases want to support mixing different event types in a single state machine.

the rust equivalence should be something like Option<State>, though in rust you generally don't use pointers willy-nilly, and it's preferred to define your data types with what C++ calls "value semantics".

btw, if you ever heard of certain functional programming concepts, as they say it, "Maybe" monad (or the like) models control flows like exception try/throw/catch. Option is like Maybe in Haskell.

in rust a callback is just an Fn object, it's totally opaque, you cannot even inspect the parts of the "fat" pointer without experimental unstable APIs.

I don't know what you mean here, rust doesn't limit you to single state machine instance. you can create as many state machines as you like.

an idiomatic rust implementation don't use pointers as much as your C++ code, they are just simple values, it's usually easier (and more importantly, safer) to make rust code concurrent than typical OO style code


in general, there's not much value to create a "generic framework" for state machines, writing a concrete state machine with the language construct is just as simple as (or perhaps simpler than) writing with a "framework" library.

the core logic of a state machine is the transition table (or diagram, it's usually implemented as table-structured data, and it's not uncommon to generate the table from some external source), don't over think it, treat data like data, not like they are some metaphorical "objects", and you'll thank yourself.

you may choose to encode the transition table as code or as data, it's no real difference:

// as code
// you can call the action functions directly, instead of returning them
fn next(current: State, event: Event) -> Option<(State, Action)> {
    match (current, event) {
        (State::S1, Event:E_1_2) => Some((State::S2, action_1_2)),
        //...
        // if the cases are not exhaustive, compiler will tell you
        _ => None,
    }
}
// as data: columns = (current, next, event, action)
// this is bare minimal information needed for a transition table
// additional information can be added for specific domain problem
const TRANSITION: &'static [(State, State, Event, Action)] = &[
    (State::S1, State::S2, Event::E_1_2, action_1_2),
    //....
];
5 Likes

You could take inspiration from existing FSM crates:

You may also be interested in looking at a generic graph library like petgraph — data structures in Rust // Lib.rs which provides a bunch of types and algorithms most of which won't matter to you.

2 Likes

Thanks Steffahn for your code!
Running it in playground I see that it works but when I try to compile it on my PC I get the following error:

Checking fsa v0.1.0 (/home/maleuser/Projects/rust/fsa)
error[E0658]: mutable references are not allowed in constant functions
   --> src/main.rs:68:18
    |
68 | act: FsaAction<E, O>,
    | ^^^
    |
    = note: see issue #57349 <https://github.com/rust-lang/rust/issues/57349> for more information

For more information about this error, try `rustc --explain E0658`.
error: could not compile `fsa` (bin "fsa") due to previous error

and I don't understand why on my PC mutable references become invalid in constant functions while in playground they are legal.

Secondly I see that you have defined FsaEvent as 'static. If I understand correctly, this means that every FSA event must exist for the entire duration of the program and I really don't want this: for simplicity my "main()" forwards only events to fsa allocated globally but could read a number typed by the user and pass it to fsa as an event that must be processed: once this processing is finished, the event passed to fsa can easily disappear.

I also have a doubt about the fact that FsaArrow, if I understand correctly, requires O to be static: in reality to define an FsaArrow I shouldn't make assumptions about the fact that the object that will be passed to Fsa::new as a userObject has already been created. Despite this, all FsaArrow type objects are read only data structures that are always present for the entire program duration. Similarly, the FsaEvents referenced by an FsaArrow must have the same lifetime as the FsaArrow, but the FsaEvents passed as input to Fsa::exe may never be so.

The intent of this code is to implement once what may be common to any state machine and leave to the author of a particular transition diagram everything that is specific to its implementation.
For this reason I have to model:

  • the generic event (which is in input to a state machine but also referenced in any transition diagram)
  • the generic transition diagram which contains the initial state on which an fsa instance is activated (the modeling of the generic transition diagram implies that the action associated with an event must also be modelled).

I don't want to make any assumptions about the type of user object whose reference is passed as input to Fsa::new (in main this reference is NULL): indeed, if possible, Fsa should be unable to use it and, for this reason, I modeled this reference using void*: the only thing the Fsa instance has to do, is to pass the instance received in input at Fsa::new to each action the Fsa instance decides to perform in response to an event received in input.

I’d called that out above, too:

In the mean-time, the version where this is fixed has become the latest stable. Just update your toolchain (rustup update).

rustup update makes the behavior of my pc equal to the playground! Thanks steffahn!!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.