Implementación de máquina de estados finita (FSM) con Java 8

Escrito por el 01/08/2015, actualizado el 25/02/2016.
java planeta-codigo programacion
Enlace permanente Comentarios

Es raro pero no he encontrado una librería adecuada en Java con una implementación de una máquina de estados. Stateless4j puede ser una candidata pero también tiene algunas deficiencias que pueden hacer que no nos sirva. Basándome en Stateless4j y usando Java 8 he creado una implementación de FSM con una funcionalidad similar y más ligera donde una única instancia de la máquina de estados es independiente del número de instancias de objetos en las que se use.

Nota: Cuando busqué no encontré pero resulta que entre uno de los numerosos subproyectos de Spring está uno que sirve como implementación de máquina de estados, Spring Statemachine. Por supuesto, Spring Statemachine es mucho más avanzado que este ejemplo que muestro en el artículo y lo recomiendo también por su mejor soporte en futuras actualizaciones. Finalmente, he escrito un artículo específico sobre Spring Statemachine.

Java

Hace un par de años escribía un artículo sobre cómo implementar una máquina de estados usando el patrón de diseño State. El patrón de diseño State y el ejemplo era válido sin embargo podía tener algunas deficiencias. Una de ellas es que necesitaba una clase por cada estado diferente, si los estados son una docena el número de archivos necesarios son altos. Por otro lado cada estado debe implementar todas las posibles transiciones o métodos de la interfaz del estado que también pueden ser altos dependiendo del numero de estados y transiciones que se haga en ellos, aunque con la clase abstracta AbstractCompraState del estado solo necesitamos implementar los métodos de transiciones propias del estado. Se podría añadir pero el ejemplo del patrón de diseño estado no tiene operaciones para saber si una determinada transición u operación puede realizarse y en el caso de añadir esa funcionalidad si tuviésemos varias máquinas de estados probablemente duplicaríamos parte del código en cada una de ellas. También viendo el código el flujo de estados no es muy obvio. Por todo ello en este artículo comentaré otra posibilidad, creo que mejor, que es implementando una máquina de estados finita (FSM, Finite State Machine) y usando Java 8 aprovechando sus nuevas características como los streams e interfaces funcionales.

Me ha parecido raro pero no he encontrado muchas librerías en Java que implementen una máquina de estados, la mejor que he visto ha sido Stateless4j. Es perfectamente usable, sin embargo, al hacer un ejemplo me he dado cuenta de que también tiene un defecto importante. Y es que si queremos aplicar una máquina de estados a una instancia de cierta clase, Stateless4j necesita una instancia de la máquina de estados por cada instancia de esa clase, puede ser usado para controlar, por ejemplo, el estado de unos cuantos personajes de un juego o del juego mismo pero si tenemos unos cuantas miles de instancias como puede ser en una aplicación de gestión el código será poco eficiente y el consumo de memoria mayor. Además usa Java 7 y con Java 8 algunas cosas son más fáciles y claras.

Basándome en Stateless4j he creado una nueva implementación y usando Java 8 la tarea ha sido más sencilla y potente. Las funcionalidades que posee la implementación de esta máquina de estados son:

Definir estados.
Definir transiciones, manejadores de transiciones y opcionalmente condiciones que se deben dar para realizar el cambio de estado.
Definir manejadores de entrada y salida por transición.
Conocer el estado actual y si se está en un determinado estado.
Conocer los eventos aceptados para cambiar de estado.
Provocar eventos en la máquina de estados proporcionando un objeto y unos datos con información adicional para procesar el evento.
Definir manejadores para excepciones al realizar alguna transición o intentos de transiciones cuando no hay manejador definido.

La API de la máquina de estados se compone de dos builders que proporcionan una API fluida, uno para crear los estados (StateBuilder) y otro para la máquina de estados (StateMachineBuilder). Además de la máquina de estados (StateMachine) y la clase que representa un estado (State).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


package io.github.picodotdev.machinarum;

import java.util.HashMap;
import java.util.Map;

public class StateMachineBuilder<S, T, O extends Subject<S>, M> {

    private Map<S, StateBuilder<S, T, O, M>> stateBuilders;
    private TriConsumer<O, T, M> unhandledTriggerHandler;
    private TriConsumer<O, T, M> exceptionHandler;

    public StateMachineBuilder() {
        stateBuilders = new HashMap<>();
    }

    public StateBuilder<S, T, O, M> state(S state) {
        StateBuilder<S, T, O, M> stateBuilder = new StateBuilder<>();
        stateBuilders.put(state, stateBuilder);
        return stateBuilder;
    }
    
    public StateMachineBuilder<S, T, O, M> unhandledTriggerHandler(TriConsumer<O, T, M> unhandledTriggerHandler) {
        this.unhandledTriggerHandler = unhandledTriggerHandler;
        return this;
    }
    
    public StateMachineBuilder<S, T, O, M> exceptionHandler(TriConsumer<O, T, M> exceptionHandler) {
        this.exceptionHandler = exceptionHandler;
        return this;
    }

    public StateMachine<S, T, O, M> build() {
        Map<S, State<S, T, O, M>> states = new HashMap<>();
        stateBuilders.forEach((S s, StateBuilder<S, T, O, M> b) -> { states.put(s, b.build()); });
        return new StateMachine<S, T, O, M>(states, unhandledTriggerHandler, exceptionHandler);
    }
}

StateMachineBuilder.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


package io.github.picodotdev.machinarum;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.BiPredicate;

public class StateBuilder<S, T, O, M> {

    private Map<T, TriggerBehaviour<S, T, O, M>> triggerBehaviours;
    private Map<T, List<BiConsumer<O, M>>> triggerEnters;
    private Map<T, List<BiConsumer<O, M>>> triggerExits;
    private List<BiConsumer<O, M>> enters;
    private List<BiConsumer<O, M>> exits;

    public StateBuilder() {
        this.triggerBehaviours = new HashMap<>();
        this.triggerEnters = new HashMap<>();
        this.triggerExits = new HashMap<>();
        this.enters = new ArrayList<>();
        this.exits = new ArrayList<>();
    }

    public StateBuilder<S, T, O, M> permit(T trigger, S destination) {
        return permit(trigger, destination, null);
    }

    public StateBuilder<S, T, O, M> permit(T trigger, S destination, BiPredicate<O, M> guard) {
        triggerBehaviours.put(trigger, TriggerBehaviour.of(destination));
        return this;
    }

    public StateBuilder<S, T, O, M> permit(T trigger, BiFunction<O, M, S> selector) {
        return permit(trigger, selector, null);
    }

    public StateBuilder<S, T, O, M> permit(T trigger, BiFunction<O, M, S> selector, BiPredicate<O, M> guard) {
        triggerBehaviours.put(trigger, new TriggerBehaviour<>(selector, guard));
        return this;
    }

    public StateBuilder<S, T, O, M> ignore(T trigger) {
        return ignore(trigger, null);
    }

    public StateBuilder<S, T, O, M> ignore(T trigger, BiPredicate<O, M> guard) {
        triggerBehaviours.put(trigger, TriggerBehaviour.identity(guard));
        return this;
    }

    public StateBuilder<S, T, O, M> enter(T trigger, BiConsumer<O, M> action) {
        triggerEnters.putIfAbsent(trigger, new ArrayList<>());
        triggerEnters.get(trigger).add(action);
        return this;
    }

    public StateBuilder<S, T, O, M> enter(BiConsumer<O, M> action) {
        enters.add(action);
        return this;
    }

    public StateBuilder<S, T, O, M> exit(T trigger, BiConsumer<O, M> action) {
        triggerExits.putIfAbsent(trigger, new ArrayList<>());
        triggerExits.get(trigger).add(action);
        return this;
    }

    public StateBuilder<S, T, O, M> exit(BiConsumer<O, M> action) {
        exits.add(action);
        return this;
    }

    public State<S, T, O, M> build() {
        return new State<>(triggerBehaviours, triggerEnters, triggerExits, enters, exits);
    }
}

StateBuilder.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83


package io.github.picodotdev.machinarum;

import java.util.Map;
import java.util.Optional;
import java.util.Set;

public class StateMachine<S, T, O extends Subject<S>, M> {

    private Map<S, State<S, T, O, M>> states;
    private TriConsumer<O, T, M> unhandledTriggerHandler;
    private TriConsumer<O, T, M> exceptionHandler;

    StateMachine(Map<S, State<S, T, O, M>> states, TriConsumer<O, T, M> unhandledTriggerHandler, TriConsumer<O, T, M> exceptionHandler) {
        this.states = states;
        this.unhandledTriggerHandler = unhandledTriggerHandler;
        this.exceptionHandler = exceptionHandler;
    }

    public S getState(O object) {
        return object.getState();
    }

    private void setState(O object, S state) {
        object.setState(state);
    }

    public boolean isState(O object, S state) {
        return getState(object) == state;
    }

    public Set<T> getTriggers(O object) {
        return states.get(getState(object)).getPermittedTriggers();
    }

    public boolean hasTrigger(O object, T trigger) {
        return getTriggers(object).contains(trigger);
    }

    public boolean canFire(O object, T trigger) {
        return canFire(object, trigger, null);
    }

    public boolean canFire(O object, T trigger, M data) {
        synchronized (object) {
            Optional<TriggerBehaviour<S, T, O, M>> triggerBehaviour = states.get(getState(object)).getHandler(trigger);
            if (!triggerBehaviour.isPresent()) {
                return false;
            }
            return triggerBehaviour.get().isMet(object, data);
        }
    }

    public void fire(O object, T trigger) {
        fire(object, trigger, null);
    }

    public void fire(O object, T trigger, M data) {
        synchronized (object) {
            Optional<TriggerBehaviour<S, T, O, M>> optTriggerBehaviour = states.get(getState(object)).getHandler(trigger);

            if (optTriggerBehaviour.isPresent()) {
                TriggerBehaviour<S, T, O, M> triggerBehaviour = optTriggerBehaviour.get();
                if (triggerBehaviour.isMet(object, data)) {
                    Optional<S> state = null;

                    try {
                        state = triggerBehaviour.select(object, data);
                    } catch (Exception e) {
                        exceptionHandler.accept(object, trigger, data);
                    }

                    if (state.isPresent()) {
                        states.get(state.get()).exit(object, trigger, data);
                        setState(object, state.get());
                        states.get(state.get()).enter(object, trigger, data);
                    }
                }
            } else {
                unhandledTriggerHandler.accept(object, trigger, data);
            }
        }
    }
}

StateMachine.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


package io.github.picodotdev.machinarum;

import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.function.BiConsumer;

public class State<S, T, O, M> {

    private Map<T, TriggerBehaviour<S, T, O, M>> triggerBehaviours;
    private Map<T, List<BiConsumer<O, M>>> triggerEnters;
    private Map<T, List<BiConsumer<O, M>>> triggerExits;
    private List<BiConsumer<O, M>> enters;
    private List<BiConsumer<O, M>> exits;

    public State(Map<T, TriggerBehaviour<S, T, O, M>> triggerBehaviours, Map<T, List<BiConsumer<O, M>>> triggerEnters, Map<T, List<BiConsumer<O, M>>> triggerExits, List<BiConsumer<O, M>> enters, List<BiConsumer<O, M>> exits) {
        this.triggerBehaviours = triggerBehaviours;
        this.triggerEnters = triggerEnters;
        this.triggerExits = triggerExits;
        this.enters = enters;
        this.exits = exits;        
    }
    
    public boolean canHandle(T trigger) {
        return getHandler(trigger).isPresent();
    }
    
    public Optional<TriggerBehaviour<S, T, O, M>> getHandler(T trigger) {
        return Optional.ofNullable(triggerBehaviours.get(trigger));
    }
    
    public Set<T> getPermittedTriggers() {
        return triggerBehaviours.keySet();
    }
    
    public void enter(O object, T trigger, M data) {
        enters.stream().forEach((c) -> { c.accept(object, data); });
        triggerEnters.getOrDefault(trigger, Collections.emptyList()).stream().forEach((c) -> { c.accept(object, data); });
    }
    
    public void exit(O object, T trigger, M data) {
        triggerExits.getOrDefault(trigger, Collections.emptyList()).stream().forEach((c) -> { c.accept(object, data); });
        exits.stream().forEach((c) -> { c.accept(object, data); });        
    }
}

State.java

Internamente se usa la clase TransitionBehiavour que define el comportamiento en una transición y ante un evento. Si posee una función de protección (guard) se comprueba antes de ejecutar la acción (selector) y que devolverá el nuevo estado.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


package io.github.picodotdev.machinarum;

import java.util.Optional;
import java.util.function.BiFunction;
import java.util.function.BiPredicate;

public class TriggerBehaviour<S, T, O, M> {

    private BiFunction<O, M, S> selector;
    private BiPredicate<O, M> guard;

    public TriggerBehaviour(BiFunction<O, M, S> selector, BiPredicate<O, M> guard) {
        this.selector = selector;
        this.guard = guard;
    }

    public boolean isMet(O object, M data) {
        if (guard == null) {
            return true;
        }
        return guard.test(object, data);
    }

    public Optional<S> select(O object, M data) {
        if (!isMet(object, data)) {
            throw new IllegalStateException();
        }
        return Optional.ofNullable(selector.apply(object, data));
    }
    
    public static <S, T, O, M> TriggerBehaviour<S, T, O, M> of(S state) {
        return new TriggerBehaviour<>((O o, M m) -> {
            return state;
        }, null);
    }
    
    public static <S, T, O, M> TriggerBehaviour<S, T, O, M> identity(BiPredicate<O, M> guard) {
        return new TriggerBehaviour<>((O o, M m) -> { 
            return null; 
        }, guard);
    }
}

TriggerBehaviour.java

El siguiente es un ejemplo de uso similar al del artículo del patrón de diseño State con un hipotético flujo de estados para una compra junto con el código de la máquina de estados necesario para implementarlo y con unas pruebas unitarias. El enumerado State define los posibles estados y el enumerado Trigger define los posibles eventos, en constructor static se define la única instancia de máquina de estados necesaria para manejar cualquier número de instancias de Purchase usando las clases builder.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121


package io.github.picodotdev.machinarum;

import java.math.BigDecimal;
import java.time.LocalDateTime;
import java.util.Map;
import java.util.Optional;
import java.util.Set;

public class Purchase implements Subject<Purchase.State> {

    enum State {
        CREATED, RESERVED, TRANSIT, DELIVERIED, CANCELED
    }

    enum Trigger {
        RESERVE, DELIVERY, DELIVERIED, CANCEL
    }

    static {
        StateMachineBuilder<State, Trigger, Purchase, Optional<Map<String, Object>>> smb = new StateMachineBuilder<>();

        smb.state(State.CREATED).permit(Trigger.RESERVE, Purchase::reserve).permit(Trigger.CANCEL, State.CANCELED);
        smb.state(State.RESERVED).permit(Trigger.DELIVERY, State.TRANSIT, Purchase::isDeliverable).permit(Trigger.CANCEL, State.CANCELED);
        smb.state(State.TRANSIT).permit(Trigger.DELIVERIED, State.DELIVERIED);
        smb.state(State.DELIVERIED).enter(Purchase::deliveried);
        smb.state(State.CANCELED);
        
        smb.unhandledTriggerHandler(Purchase::onUnhandledTrigger).exceptionHandler(Purchase::onException);
        
        stateMachine = smb.build();
    }

    private static StateMachine<State, Trigger, Purchase, Optional<Map<String, Object>>> stateMachine;
    private static BigDecimal PREMIUM_DELIVERY = new BigDecimal("100");

    private LocalDateTime date;
    private State state;
    private int items;
    private BigDecimal amount;

    public Purchase(int items, BigDecimal amount) {
        this.date = LocalDateTime.now();
        this.state = State.CREATED;
        this.items = items;
        this.amount = amount;
    }

    public StateMachine<State, Trigger, Purchase, Optional<Map<String, Object>>> getStateMachine() {
        return stateMachine;
    }

    public State getState() {
        return state;
    }
    
    public void setState(State state) {
        this.state = state;
    }
    
    public LocalDateTime getDate() {
        return date;
    }

    public void setDate(LocalDateTime date) {
        this.date = date;
    }
    
    // StateMachine methods
    public boolean isState(State state) {
        return getStateMachine().isState(this, state);        
    }
    
    public Set<Trigger> getTriggers() {
        return getStateMachine().getTriggers(this);        
    }
    
    public boolean hasTrigger(Trigger trigger) {
        return getStateMachine().hasTrigger(this, trigger);        
    }
    
    public boolean canFire(Trigger trigger) {
        return getStateMachine().canFire(this, trigger);
    }
    
    public boolean canFire(Trigger trigger, Optional<Map<String, Object>> data) {
        return getStateMachine().canFire(this, trigger, data);
    }
    
    public void fire(Trigger trigger) {
        getStateMachine().fire(this, trigger);
    }
    
    public void fire(Trigger trigger, Optional<Map<String, Object>> data) {
        getStateMachine().fire(this, trigger, data);
    }
    
    private void onUnhandledTrigger(Trigger trigger, Optional<Map<String, Object>> data) {
        System.out.printf("UnhandledTrigger %s\n", trigger);
    }
    
    private void onException(Trigger trigger, Optional<Map<String, Object>> data) {
        System.out.printf("Execption %s\n", trigger);
    }

    // Business StateMachine methods
    private boolean isDeliverable(Optional<Map<String, Object>> m) {
        return date.plusMinutes(60).isAfter(LocalDateTime.now());
    }    

    private boolean hasStock(Optional<Map<String, Object>> m) {
        return items <= 5;
    }

    private State reserve(Optional<Map<String, Object>> m) {
        return (hasStock(m))?State.RESERVED:State.CANCELED;
    }
    
    private void deliveried(Optional<Map<String, Object>> m) {
        System.out.println("Deliveried");
    }
}

Purchase.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


package io.github.picodotdev.machinarum;

import static org.junit.Assert.assertEquals;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Map;
import java.util.Optional;

import org.junit.Assert;
import org.junit.Test;

import io.github.picodotdev.machinarum.Purchase.State;
import io.github.picodotdev.machinarum.Purchase.Trigger;

public class PurchaseTest {

    @Test
    public void testNormal() throws Exception {
        Purchase purchase = new Purchase(5, new BigDecimal("150"));

        purchase.fire(Trigger.RESERVE);
        assertEquals(State.RESERVED, purchase.getState());

        purchase.fire(Trigger.DELIVERY);
        assertEquals(State.TRANSIT, purchase.getState());

        purchase.fire(Trigger.DELIVERIED);
        assertEquals(State.DELIVERIED, purchase.getState());
    }

    @Test
    public void testCancel() throws Exception {
        Purchase purchase = new Purchase(5, new BigDecimal("150"));

        purchase.fire(Trigger.RESERVE);
        assertEquals(State.RESERVED, purchase.getState());

        purchase.fire(Trigger.CANCEL);
        assertEquals(State.CANCELED, purchase.getState());
    }

    @Test
    public void testMethods() throws Exception {
        Purchase purchase = new Purchase(5, new BigDecimal("150"));
        Optional<Map<String,Object>> data = Optional.empty();
        
        Assert.assertTrue(purchase.isState(Purchase.State.CREATED));
        Assert.assertTrue(Arrays.asList(Trigger.RESERVE, Trigger.CANCEL).containsAll(purchase.getTriggers()));
        Assert.assertTrue(purchase.hasTrigger(Trigger.RESERVE));
        Assert.assertTrue(purchase.canFire(Trigger.RESERVE));
        Assert.assertTrue(purchase.canFire(Trigger.RESERVE, data));
        purchase.fire(Trigger.RESERVE);
        purchase.fire(Trigger.CANCEL, data);
        assertEquals(State.CANCELED, purchase.getState());
    }
    
    @Test
    public void testHandlers() throws Exception {
        Purchase purchase = new Purchase(5, new BigDecimal("150"));
        
        purchase.fire(Trigger.DELIVERIED);
    }
}

PurchaseTest.java

La interfaz Subject proporciona las operaciones para que la máquina de estados pueda obtener y modificar el estado del objeto manejado en una transición, en este caso de una instancia de Purchase.

1
2
3
4
5
6
7


package io.github.picodotdev.machinarum;

public interface Subject<S> {

    S getState();
    void setState(S status);
}

Subject.java

Otra posibilidad a las máquinas de estados son las herramientas de procesos de negocio o BPM (Business Process Management) pero salvo que tengamos algo muy complejo la máquina de estados de este ejemplo será más que suficiente para la mayoría de situaciones. Hace un tiempo escribir varios artículos sobre Activiti y Drools:

El código fuente completo está disponible en mi repositorio de ejemplos en GitHub.

Referencia:

Implementación de máquina de estados finita (FSM) con Java 8

Cómo trabajar con importes, ratios y divisas en Java

Hemeroteca #7

Servicio para obtener ratios de conversión entre divisas

Nueva visita a Herramientas para un proyecto Java

Patrón múltiples vistas de un mismo dato en Tapestry

Alternativa a Hibernate u ORM y ejemplo de jOOQ