Programmeringsbloggen
En generisk state machine
Skriv en kommentar
Finite state machines (FSM), tilstandsmaskiner på norsk, er blant de mest kraftige abstraksjonene vi programmerere har tilgjengelig, og har et stort og variert bruksområde. FSM gir oss en enkel og elegant måte å utforske og definere oppførselen til komplekse systemer, og implementasjonen er både enkel å fortså og enkel å modifisere. I boken sin Agile Principles, Patterns, and Practises in C# sier Robert C. Martin følgende om dette:
“Finite state machines are underutilized. In many scenarios their use would help to create cleaner, simpler, more flexible, and more accurate code.”
I den enkleste formen er en state machine gjerne implementert som en eller flere switch/case statements – i mer komplekse løsninger kan man bruke STATE pattern. I .NET 3.0 fikk vi også Windows Workflow Foundation, hvor vi kan designe State Machine Workflows.
Men alle disse alternativene er mere komplekse enn å lage en FSM basert på en overgangstabell. I denne artikkelen designer jeg en generisk FSM-motor som kan gjenbrukes i mange scenarier. For å illustrere hvordan den virker vil jeg implementere tilstandsmaskinen som finnes i en typisk passeringsautomat – slike som man finner på T-banestasjoner, flytoget osv.
I diagrammet under ser du tilstandene (states), overgangene (transitions), hendelsene som kan inntreffe (transition conditions) og det systemet skal utføre når det går fra en tilstand til en annen (actions) i en slik passeringsautomat.
Ta for eksempel en automat som i utgangspunktet er låst. Hvis noen putter en mynt på automaten, vil systemet kalle en rutine for å låse opp porten, og endre statusen til å være ulåst. Når den så registrerer at noen passerer porten, vil den kalle rutinen for å låse porten, og returnere til den låste tilstanden. Hvis noen passerer mens systemet er i låst tilstand, vil automaten kalle alarm-rutinen og forbli i låst tilstand.
Skulle noen finne på å putte på penger mens systemet er ulåst, vil automaten si “tusen takk”, og forbli i ulåst tilstand.
Det første jeg vil gjøre er å opprette et par enumerasjoner som beskriver systemets tilstander og hendelser:
9 public enum State { LOCKED, UNLOCKED }
10 public enum Event { COIN, PASS }
Jeg utviklet selvsagt automaten vha. TDD, og her følger oppsettet av testklassen, som viser hvordan en StateMashine opprettes og konfigureres:
9 using StateMachine = Marosoft.Generics.StateMachine<State, Event>;
10
11 [TestFixture]
12 public class TestGenericStateMachine
13 {
14 private StateMachine _stateMachine;
15
16 static bool _unlockCalled = false;
17 static bool _alarmCalled = false;
18 static bool _thankYouCalled = false;
19 static bool _lockActionCalled = false;
20
21 private Action unlock = () => _unlockCalled = true;
22 private Action alarm = () => _alarmCalled = true;
23 private Action thankYou = () => _thankYouCalled = true;
24 private Action lockAction = () => _lockActionCalled = true;
25
26 [SetUp]
27 public void SetUp()
28 {
29 _stateMachine = new StateMachine(State.LOCKED);
30 // Equivalent to generic specification due to using statement
31
32 _stateMachine.AddTransition(State.LOCKED, Event.COIN, State.UNLOCKED, unlock);
33 _stateMachine.AddTransition(State.LOCKED, Event.PASS, State.LOCKED, alarm);
34 _stateMachine.AddTransition(State.UNLOCKED, Event.COIN, State.UNLOCKED, thankYou);
35 _stateMachine.AddTransition(State.UNLOCKED, Event.PASS, State.LOCKED, lockAction);
36 }
Legg merke til det spesielle using direktivet på linje 9. Dette er ikke et krav, men lar meg definere en StateMachine-variabel på linje 14 og initiere den på linje 29 uten å spesifisere hvilke enumerasjoner som skal brukes. Dette er et generelt tips om hvordan man kan gjøre kode som bruker mye generics mer lesbar.
Linje 16 til 24 setter opp fire dummy-actions som skal brukes når jeg tester tilstandsmaskinen. Det mest interessante kommer først på linje 32, hvor jeg begynner å definere tilstandsovergangene.
Du kan lese linje 32 på følgende måte: Hvis nåværende tilstand er LOCKED, og noen putter på en COIN, så skal tilstanden endres til UNLOCKED, og “unlock” skal kjøres.
Den første testen jeg trenger sjekker bare den initielle tilstanden, som jeg satte i konstruktøren. Testen er ikke mer enn én linje:
40 [Test]
41 public void InitialConditions()
42 {
43 Assert.AreEqual(State.LOCKED, _stateMachine.State);
44 }
Deretter skriver jeg tester for hver av de fire mulige overgangene. I hver test setter jeg først gjeldende status, noe som bare er aktuelt i enhetstestene – i virkelig bruk vil man ikke overstyre status på den måten. Deretter sender jeg inn et event til tilstandsmaskinen, før jeg sjekker ny status og om riktig action har blitt kalt (ref oppsettet av test-klassen). Her er testene:
46 [Test]
47 public void CoinInLockedState()
48 {
49 _stateMachine.State = State.LOCKED;
50 _stateMachine.HandleEvent(Event.COIN);
51 Assert.AreEqual(State.UNLOCKED, _stateMachine.State);
52 Assert.IsTrue(_unlockCalled);
53 }
54 [Test]
55 public void CoinInUnlockedState()
56 {
57 _stateMachine.State = State.UNLOCKED;
58 _stateMachine.HandleEvent(Event.COIN);
59 Assert.AreEqual(State.UNLOCKED, _stateMachine.State);
60 Assert.IsTrue(_thankYouCalled);
61 }
62 [Test]
63 public void PassInLockedState()
64 {
65 _stateMachine.State = State.LOCKED;
66 _stateMachine.HandleEvent(Event.PASS);
67 Assert.AreEqual(State.LOCKED, _stateMachine.State);
68 Assert.IsTrue(_alarmCalled);
69 }
70 [Test]
71 public void PassInUnlockedState()
72 {
73 _stateMachine.State = State.UNLOCKED;
74 _stateMachine.HandleEvent(Event.PASS);
75 Assert.AreEqual(State.LOCKED, _stateMachine.State);
76 Assert.IsTrue(_lockActionCalled);
77 }
Nå bør du skjønne hvordan StateMachine skal brukes, og jeg er klar for å vise hvordan den er implementert. Her er første bit; StateMachine har en generisk definisjon som forventer to typer som skal representere henholdsvis statuser og eventer: Jeg har kalt dem TState og TEvent. Construktøren tar inn initiell status:
9 public class StateMachine<TState, TEvent>
10 {
11 ///
12 /// Setter is left internal for testing purposes
13 ///
14 public TState State { get; internal set; }
15
16 public StateMachine(TState initialState)
17 {
18 State = initialState;
19 }
Videre inneholder klassen en liste med overganger (linje 21). En overgang – Transition – er en intern klasse i StateMachine (linje 23). Det er ikke så ofte jeg bruker private klasser i andre klasser, men her passet det fint. AddTransition-metoden (linje 31) som jeg brukte i SetUp i testklassen oppretter en ny Transition og legger den til i listen.
21 private List<Transition> _transitions = new List<Transition>();
22
23 private class Transition
24 {
25 public TState StartState;
26 public TEvent Trigger;
27 public TState EndState;
28 public Action Action;
29 }
30
31 public void AddTransition( TState startState,
32 TEvent trigger,
33 TState endState,
34 Action action)
35 {
36 _transitions.Add(new Transition
37 {
38 StartState = startState,
39 Trigger = trigger,
40 EndState = endState,
41 Action = action,
42 });
43 }
Og da gjenstår bare HandleEvent-metoden, som er gjengitt nedenfor. Den finner riktig overgang basert på event-parameteren og gjenldende status. Til dette bruker jeg Find-metoden til List. Hvis en overgang finnes, brukes den til å sette ny status, og riktig action kalles (linje 55 og 56).
Hvis et ugyldig event sendes inn for gitt status (ikke mulig for denne passeringsautomaten, men kan tenkes for andre tilstandsmaskiner), så kaster jeg et ArgumentException.
45 public void HandleEvent(TEvent e)
46 {
47 var transitionToPerform
48 = _transitions.Find((transition)
49 => transition.StartState.Equals(State) && transition.Trigger.Equals(e));
50
51 if (transitionToPerform == null)
52 throw new ArgumentException(
53 string.Format(“Can not handle event {0} in state {1}.”, e, State));
54
55 State = transitionToPerform.EndState;
56 transitionToPerform.Action.Invoke();
57 }
Min StateMachine er en forbedring av Robert C. Martins Transition Tables-eksempel fra boken jeg refererte. Ved å bruke generics har jeg gjort den gjenbrukbar. Når du trenger en tilstandsmaskin behøver du bare definere tilstandene og eventene, og konfigurere StateMachine med de riktige overgangene.
Det er også verdt å merke seg at du ikke er begrenset til å bruke enumerasjoner til å definere tilstander og/eller eventer; du kan like gjenre bruke klasser, slik som jeg har gjort her:
12 public abstract class TurnstileState
13 {
14 public override bool Equals(object obj)
15 {
16 return base.GetType().Equals(obj.GetType());
17 }
18 public override int GetHashCode()
19 {
20 return base.GetType().GetHashCode();
21 }
22 }
23 public class LockedState : TurnstileState { }
24 public class UnlockedState : TurnstileState { }
Den abstrakte klassen TurnstileState (turnstile er engelsk for passeringsautomat) definerer et interface (et tomt et sådan) for en tilstand. LockedState og UnlockedState arver fra TurnstileState, og erstatter Event.LOCKED og Event.UNLOCKED. Jeg har overstyrt Equals fordi HandleEvent bruker Equals til å finne riktig overgang (merk at man også alltid skal overstyre GetHashCode når man overstyrer Equals).
Flytende konfigurering..
Til slutt gjorde jeg en liten forbedring i hvordan jeg oppretter overgangene. Flytende interfacer er veldig populært for tiden, og kan gjøre kode mer lesbar. Sammenlign SetUp-metoden nedenfor med den jeg presenterte tidligere, og se om du er enig i at dette er bedre.
24 [SetUp]
25 public void SetUp()
26 {
27 _stateMachine = new StateMachine<State, Event>(State.LOCKED);
28
29 _stateMachine.Configure()
30 .Given(State.LOCKED)
31 .When(Event.COIN)
32 .ThenSetState(State.UNLOCKED).AndRun(unlock)
33 .When(Event.PASS)
34 .ThenSetState(State.LOCKED).AndRun(alarm)
35 .Given(State.UNLOCKED)
36 .When(Event.COIN)
37 .ThenSetState(State.UNLOCKED).AndRun(thankYou)
38 .When(Event.PASS)
39 .ThenSetState(State.LOCKED).AndRun(lockAction);
40 }
Da jeg implementerte det som trengtes for å få denne setup-metoden til å kjøre oppdaget jeg noe ganske morsomt. Konfigurerings-objektet jeg opprettet er faktisk en tilstandmaskin – en Finite State Machine. Begynner du først å tenke på denne måten så oppdager du stadig nye tilfeller hvor FSM-teknikken kan benyttes.
Tilstandsmaskiner kan gjøre koden din enklere å forstå, vedlikeholde og endre, og bør ikke undervurderes. De fjerner “spagetti”, og lar dine øvrige klasser konsentrere seg om sine primære ansvar. Tenk gjennom hvilke tilstander koden din kan ha neste gang du programmerer, og vurder å bruk en tilstandsmaskin for å forenkle koden.
Knagger: Fluent, Patterns, Robert C. Martin
Kategorier: OO-design/clean code.
RSS feed for kommentarene.
Tilbaketråkk.
November 19th, 2010 at 10:17 am
[...] I juni 2009 blogget jeg hvordan man kan implementere en generisk tilstandsmaskin i C#, inspirert av Robert C. Martin’s overgangstabeller fra boken Agile Principles, Patterns, and Practises in C#. Jeg designet også et flytende interface for å konfigurere tilstandsmaskiner – her er et tilbakeblikk på hvordan det så ut: 10 _stateMachine = new StateMachine<State, Event>(State.LOCKED);11 12 _stateMachine.Configure()13 .Given(State.LOCKED)14 .When(Event.COIN)15 .ThenSetState(State.UNLOCKED).AndRun(unlock)16 .When(Event.PASS)17 .ThenSetState(State.LOCKED).AndRun(alarm)18 .Given(State.UNLOCKED)19 .When(Event.COIN)20 .ThenSetState(State.UNLOCKED).AndRun(thankYou)21 .When(Event.PASS)22 .ThenSetState(State.LOCKED).AndRun(lockAction);23 [...]