{"id":932,"date":"2015-08-24T13:49:57","date_gmt":"2015-08-24T12:49:57","guid":{"rendered":"http:\/\/benjiweber.co.uk\/blog\/?p=932"},"modified":"2018-08-11T17:54:33","modified_gmt":"2018-08-11T16:54:33","slug":"optionally-typechecked-statemachines","status":"publish","type":"post","link":"https:\/\/benjiweber.co.uk\/blog\/2015\/08\/24\/optionally-typechecked-statemachines\/","title":{"rendered":"Optionally typechecked StateMachines"},"content":{"rendered":"

Many things can be modelled as finite state machines<\/a>. Particularly things where you’d naturally use “state” in the name e.g. the current state of an order, or delivery status. We often model these as enums. <\/p>\n

\r\nenum OrderStatus {\r\n    Pending,\r\n    CheckingOut,\r\n    Purchased,\r\n    Shipped,\r\n    Cancelled,\r\n    Delivered,\r\n    Failed,\r\n    Refunded\r\n}\r\n<\/pre>\n
Enums are great for restricting our order status to only valid states. However, usually there are only certain transitions that are valid. We can’t go from Delivered to Failed. Nor would we go straight from Pending to Delivered. Maybe we can transition from Purchased to either Shipped or Cancelled.<\/p>\n
Using enum values we cannot restrict to the transitions to only those that we desire. It would be nice to also let the compiler help us out by not letting us choose invalid transitions in our code. <\/p>\n
We can, however, achieve this if we use a class hierarchy to represent our states instead, and it can still be fairly concise. There are other reasons for using regular classes, they allow us to store and even capture state from the surrounding context. <\/p>\n
Here’s a way we could model the above enum as a class heirarchy with the valid transitions.<\/p>\n
\r\ninterface OrderStatus extends State {}\r\nstatic class Pending     implements OrderStatus, BiTransitionTo {}\r\nstatic class CheckingOut implements OrderStatus, BiTransitionTo {}\r\nstatic class Purchased   implements OrderStatus, BiTransitionTo {}\r\nstatic class Shipped     implements OrderStatus, BiTransitionTo {}\r\nstatic class Delivered   implements OrderStatus, TransitionTo {}\r\nstatic class Cancelled   implements OrderStatus {}\r\nstatic class Failed      implements OrderStatus {}\r\nstatic class Refunded    implements OrderStatus {}\r\n<\/pre>\n
We’ve declared an OrderStatus interface and then created implementations of OrderStatus for each valid state. We’ve then encoded the valid transitions as other interface implementations. There’s a TransitionTo<State> and BiTransitionTo<State1,State2>, or TriTransitionTo<State1,State2,State3> depending on the number of valid transitions from that state. We need differently named interfaces for different numbers of transitions because Java doesn’t support variance on the number of generic type parameters.<\/p>\n
Compile-time checking valid transitions<\/h2>\n
Now we can create the TransitionTo\/BiTransitionTo interfaces, which can give us the functionality to transition to a new state (but only if it is valid)<\/p>\n
We might imagine an api like this where we can choose which state to transition to<\/p>\n
\r\nnew Pending()\r\n    .transitionTo(CheckingOut.class)\r\n    .transitionTo(Purchased.class)\r\n    .transitionTo(Refunded.class) \/\/ <-- can we make this line fail to compile?\r\n<\/pre>\n
This turns out to be a little tricky, but not impossible, due to type erasure.<\/p>\n
Let's try to implement BiTransitionTo interface with the two valid transition.<\/p>\n
\r\npublic interface BiTransitionTo {\r\n    default T transitionTo(Class type) { ... }\r\n    default U transitionTo(Class type) { ... }\r\n}\r\n<\/pre>\n
Both of these transitionTo methods have the same erasure<\/a>. So we can't do it quite like this. However, if we can encourage the consumer of our API to pass a lambda, there is a way to work around this same erasure problem.<\/a><\/p>\n
So how about this API, where instead of passing class literals we pass constructor references. It looks similarly clean, but constructor references are basically lambdas so we can avoid type erasure.<\/p>\n
\r\nnew Pending()\r\n    .transition(CheckingOut::new)\r\n    .transition(Purchased::new)\r\n    .transition(Refunded::new) \/\/ <-- Now we can make this fail to compile\r\n<\/pre>\n
<\/p>\n
In order to make this work the trick is to create a new interface type for each valid transition within our BiTransitionTo interface<\/p>\n
\r\npublic interface BiTransitionTo {\r\n    interface OneTransition extends Supplier { }\r\n    default T transition(OneTransition constructor) { ... }\r\n    interface TwoTransition extends Supplier { }\r\n    default U transition(TwoTransition constructor) { ... }\r\n}\r\n<\/pre>\n
Supplier<T> is a functional interface in the java.util.function that is equivalent to a no-args constructor reference. By creating two interfaces that extend this we can overload the transition() method twice, allowing both methods to be passed a constructor reference without the two methods having the same erasure.<\/p>\n
Runtime checking<\/h2>\n
Sometimes we might not be able to know at compile-time what state our statemachine is in. Perhaps a Customer has a field of type OrderStatus that we serialize to a database.  We would need to be able to try a transition at runtime, and fail in some manner if the transition is not valid.<\/p>\n
This is also possible using the TransitionTo<NewState> approach outlined above. Since supertype parameters are available at runtime<\/a>, we can implement a tryTransition() method that uses reflection to check which transitions are permitted.<\/p>\n
First we'll need a way of finding the valid transition types. We'll add it to our State base interface.<\/p>\n
\r\ndefault List> validTransitionTypes() {\r\n    return asList(getClass().getGenericInterfaces())\r\n        .stream()\r\n        .filter(type -> type instanceof ParameterizedType)\r\n        .map(type -> (ParameterizedType) type)\r\n        .filter(TransitionTo::isTransition) \r\n        .flatMap(type -> asList(type.getActualTypeArguments()).stream())\r\n        .map(type -> (Class) type)\r\n        .collect(toList());\r\n}\r\n<\/pre>\n
Note the isTransition filter. Since we have multiple transition interfaces - TransitionTo<T>, BiTransitionTo<T,U>, TriTransitionTo<T,U,V> etc, we need a way of marking them as all specifying transitions. I've used an annotation <\/p>\n
\r\n@Retention(RUNTIME)\r\n@Target(ElementType.TYPE)\r\npublic @interface Transition {\r\n\r\n}\r\nstatic boolean isTransition(ParameterizedType type) {\r\n     Class cls = (Class)type.getRawType();\r\n     return cls.getAnnotationsByType(Transition.class).length > 0;\r\n}\r\n\r\n@Transition\r\npublic interface TriTransitionTo...\r\n<\/pre>\n
Once we have validTransitionTypes() we can find which transitions are valid at runtime.<\/p>\n
\r\nstatic class Pending implements OrderStatus, BiTransitionTo {}\r\n@Test\r\npublic void finding_valid_transitions_at_runtime() {\r\n    Pending pending = new Pending();\r\n    assertEquals(\r\n        asList(CheckingOut.class, Cancelled.class),\r\n        pending.validTransitionTypes()\r\n    );\r\n}\r\n<\/pre>\n
Now that we have the valid types, tryTransition() needs to check whether the requested transition is to one of those types. <\/p>\n
This is a little tricky, but since we're passing a lambda we make it a lambda-type-token<\/a> and use reflection to find the type parameter of the lambda.<\/p>\n
Our implementation then looks something like <\/p>\n
\r\n\r\ninterface NextState extends Supplier, MethodFinder {\r\n    default Class type() {\r\n        return (Class) getContainingClass();\r\n    }\r\n}\r\ndefault  T tryTransition(NextState desired) {\r\n    if (validTransitionTypes.contains(desired.type())) {\r\n        return desired.get();\r\n    }\r\n\r\n    throw new IllegalStateTransitionException();\r\n}\r\n<\/pre>\n
We can make it a bit nicer by allowing the caller to specify the exception to throw on error, like an Optional's orElseThrow. We can also allow the caller to ignore failed transitions.<\/p>\n
\r\n@Test\r\npublic void runtime_checked_transition() {\r\n    OrderStatus state = new Pending();\r\n    assertTrue(state instanceof Pending);\r\n    state = state\r\n        .tryTransition(CheckingOut::new)\r\n        .unchecked();\r\n    assertTrue(state instanceof CheckingOut);\r\n}\r\n<\/pre>\n
Since we've transitioned into a known state (or thrown an exception) with tryTransition we could then chain compile-time checked transitions on the end.<\/p>\n
\r\n@Test\r\npublic void runtime_checked_transition() {\r\n    OrderStatus state = new Pending();\r\n    assertTrue(state instanceof Pending);\r\n    state = state\r\n        .tryTransition(CheckingOut::new)\r\n        .unchecked()\r\n        .transition(Purchased::new); \/\/ This will be permitted if the tryTransition succeeds.\r\n    assertTrue(state instanceof CheckingOut);\r\n}\r\n<\/pre>\n
We can even let people ignore transition failures if they wish, just by catching the exception and returning the original value.<\/p>\n
\r\n@Test\r\npublic void runtime_checked_transition_ignoring_failure() {\r\n    OrderStatus state = new Pending();\r\n    assertTrue(state instanceof Pending);\r\n    state = state\r\n        .tryTransition(Refunded::new)\r\n        .ignoreIfInvalid();\r\n    assertFalse(state instanceof Refunded);\r\n    assertTrue(state instanceof Pending);\r\n}\r\n<\/pre>\n
Adding Behaviour<\/h2>\n
Since our states are classes, we can add behaviour to them. <\/p>\n
For instance we could add a notifyProgress() method to our OrderStatus, with different implementations in each state.<\/p>\n
\r\ninterface OrderStatus extends State {\r\n    default void notifyProgress(Customer customer, EmailSender sender) {}\r\n}\r\nstatic class Purchased implements OrderStatus, BiTransitionTo {\r\n    public void notifyProgress(Customer customer, EmailSender emailSender) {\r\n        emailSender.sendEmail(\"fulfillment@mycompany.com\", \"Customer order pending\");\r\n        emailSender.sendEmail(customer.email(), \"Your order is on its way\");\r\n    }\r\n}\r\n...\r\nOrderStatus status = new Pending();\r\nstatus.notifyProgress(customer, sender); \/\/ Does nothing\r\nstatus = status\r\n    .tryTransition(CheckingOut::new)\r\n    .unchecked()\r\n    .transition(Purchased::new);\r\nstatus.notifyProgress(customer, sender) ; \/\/ sends emails\r\n<\/pre>\n
Then we can call notifyProgress on any OrderStatus instance and it will notify differently depending on which implementation is active.<\/p>\n
Internal Transitions<\/h2>\n
One of the ways to make most use of the typechecked transitions is to have the transitions internally within the state. e.g. in a state machine for the Regex \"A+B\" the A state can transition either <\/p>\n