Finite state machine abstraction

[Szilard Szaloki]

Hi all,

I was wondering if Chromium could make use of a FiniteStateMachine<> abstraction: https://godbolt.org/z/4E9P7nMo8
The syntax helps define clear transitions from one state to another, better invariants in states, and is quite expressive overall — could even easily be turned into a diagram, text definition, etc.

Curious about your thoughts!

Szilard

[Adam Rice]

There are a number of different state machine abstractions in use in Chromium. The one I'm most familiar with is the "DoLoop" pattern used in the network stack: https://source.chromium.org/chromium/chromium/src/+/main:net/docs/code-patterns.md;l=38?q=file:net%2Fdocs%2Fcode-patterns.md%20DoLoop

My concern with this FiniteStateMachine<> abstraction is that it generates a lot of code. We need to be careful with code size in Chromium as it runs on platforms with limited resources. It also appears to silently ignore unexpected messages, which could make debugging hard. From an efficiency standpoint, the fact that it allocates memory on every state transition makes it unsuitable in cases like parsers where state transitions need to be lightweight.

Personally, after a number of bad experiences with state machines, I prefer not to use them when conventional control flow is an option.

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/c3b3ead1-386d-499e-8097-b21623cf786bn%40chromium.org.

[Szilard Szaloki]

Hi there,

My concern with this FiniteStateMachine<> abstraction is that it generates a lot of code.

It does generate some code to properly formalize the abstraction and to achieve this DSL-like syntax, but it's exactly this "transitions chained one after the other" style that makes it appealing. It's easily readable, and it also makes tooling straightforward, as you can just use Clang's LibASTMatchers with LibTooling to match the transitions and transform them into, say, Mermaid text definitions, which you can render into diagrams in Markdown.

It also appears to silently ignore unexpected messages, which could make debugging hard.

That's by design, but can be improved if needed — e.g. by logging the type of the message in the kIsSink branch of Dispatcher<>::Dispatch(), or by adding the capability to pass a custom sink function to FiniteStateMachine<>::handle().

From an efficiency standpoint, the fact that it allocates memory on every state transition makes it unsuitable in cases like parsers where state transitions need to be lightweight.

Messages can be kept on the stack and we can use raw pointers, too — only need virtual functions to work.

See the updated implementation here: https://godbolt.org/z/z4hbjs9Gb

Szilard

[Ryan Hamilton]

I think this discussion is a bit abstract. You might consider porting an existing piece of Chromium code over to this in order to illustrate the benefits.

Cheers,

Ryan

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAEQ0102JUcvG2AOmVcvdfNLWJCHbE9tdCMvW%2BQvGHeqN1%2BOr5w%40mail.gmail.com.

[Szilard Szaloki]

Makes sense — just wanted to get some early feedback here before I dig in, as I'm limited in time. Will try and port some code over to the above.

Best,
Szilard

[Szilard Szaloki]

For tooling, see an example attached.

Szilard