andri.dk
[READ-ONLY] Mirror of https://github.com/andrioid/statesman. xstate inspired schema compatible statechart library for Go
fsm
go
statecharts
1package statesman
2
3// microstep.go is the generic engine that drives docs/transition-algorithm.md
4// §4 (macrostep/microstep loop) and §8 (action accumulation, transactionality).
5// It is generic over TCtx/TEvt but never names a per-machine ActionResult: it
6// calls the opaque applier/guard closures the generated constructor injects
7// (decision 36). compute works entirely on clones of the engine's live state, so
8// an observer-aborted microstep needs no rollback — the live state was untouched
9// until commit.
10
11// EffectKind tags an AppliedEffect.
12type EffectKind uint8
13
14const (
15 EffectNoop EffectKind = iota
16 EffectAssign
17 EffectSend
18 EffectSpawn
19)
20
21// AppliedEffect is the closure's return: the engine's view of one action result.
22// Assign carries the new context (the closure preserves child refs, decision 32);
23// Send/Spawn are outbox intents fired by the actor loop after publish.
24type AppliedEffect[TCtx any] struct {
25 Kind EffectKind
26 Ctx TCtx // EffectAssign
27 Target ActorAddress // EffectSend / EffectSpawn
28 Event EventBase // EffectSend
29 Spawn any // EffectSpawn descriptor (wired in Phase 4)
30}
31
32type queuedEvent[TEvt EventBase] struct {
33 descriptor string
34 payload TEvt
35 hasPayload bool
36}
37
38// Microstep is one committed-or-stageable transition transaction. The actor loop
39// runs observers on (PrevActive/PrevContext → NextActive/NextContext), then
40// commits (publish + drain Effects) or aborts.
41type Microstep[TCtx any] struct {
42 Transitions []*Transition
43 Exited []*StateNode // reverse document order (exit order)
44 Entered []*StateNode // document order (entry order)
45 PrevActive []StateID
46 NextActive []StateID
47 PrevContext TCtx
48 NextContext TCtx
49 Effects []AppliedEffect[TCtx] // Send/Spawn outbox, in order
50 TriggeredByEvent bool
51 ReachedFinal bool
52
53 // staged engine state, swapped in by commit.
54 cfg *configuration
55 hist map[StateID][]*StateNode
56 internalEnqueue []string // done.state.* descriptors
57}
58
59// engine holds the live interpreter state. Unexported; the Machine wraps it.
60type engine[TCtx any, TEvt EventBase] struct {
61 def *Definition
62 cfg *configuration
63 ctx TCtx
64 hist map[StateID][]*StateNode
65
66 internalQueue []queuedEvent[TEvt]
67 pendingExternal *queuedEvent[TEvt]
68
69 applyAction func(callsite int, ctx TCtx, evt TEvt) AppliedEffect[TCtx]
70 evalGuard func(callsite int, ctx TCtx, evt TEvt) bool
71
72 alwaysLimit int
73 alwaysRun int
74 status ActorStatus
75 errReason error
76 lastEvt TEvt // triggering event of the most recently staged microstep
77}
78
79// triggerEvent returns the event that triggered the most recently staged
80// microstep (zero for the initial entry and eventless/internal microsteps). The
81// actor loop passes it to observers.
82func (e *engine[TCtx, TEvt]) triggerEvent() TEvt { return e.lastEvt }
83
84const defaultAlwaysLimit = 100
85
86func newEngine[TCtx any, TEvt EventBase](
87 def *Definition,
88 initCtx TCtx,
89 applyAction func(int, TCtx, TEvt) AppliedEffect[TCtx],
90 evalGuard func(int, TCtx, TEvt) bool,
91 alwaysLimit int,
92) *engine[TCtx, TEvt] {
93 if alwaysLimit <= 0 {
94 alwaysLimit = defaultAlwaysLimit
95 }
96 return &engine[TCtx, TEvt]{
97 def: def,
98 cfg: newConfiguration(),
99 ctx: initCtx,
100 hist: make(map[StateID][]*StateNode),
101 applyAction: applyAction,
102 evalGuard: evalGuard,
103 alwaysLimit: alwaysLimit,
104 status: StatusStarting,
105 }
106}
107
108// guardPass returns a predicate evaluating guards against the live context and
109// the supplied triggering event (zero for eventless/internal microsteps).
110func (e *engine[TCtx, TEvt]) guardPass(evt TEvt) guardPredicate {
111 return func(t *Transition) bool {
112 if t.Guard == nil {
113 return true
114 }
115 return e.evalGuard(t.Guard.Callsite, e.ctx, evt)
116 }
117}
118
119// start computes the initial-configuration entry as a microstep (entry actions
120// run; invokes are deferred to the actor loop). Not committed.
121func (e *engine[TCtx, TEvt]) start() *Microstep[TCtx] {
122 toEnter := make(map[*StateNode]struct{})
123 defEntry := make(map[*StateNode]struct{})
124 addDescendantStatesToEnter(e.def.Root, toEnter, defEntry, e.hist)
125 var zero TEvt
126 return e.apply(nil, nil, toEnter, zero, false)
127}
128
129// offer queues an external event (from the mailbox) for the next step.
130func (e *engine[TCtx, TEvt]) offer(evt TEvt) {
131 e.pendingExternal = &queuedEvent[TEvt]{descriptor: evt.EventType(), payload: evt, hasPayload: true}
132}
133
134// offerDescriptor queues a synthetic external event identified only by its
135// descriptor (an `after` fire or a child done/error notification with no
136// user-constructed payload). Action/guard callsites on such edges are
137// context-shape, so the zero TEvt they receive is never inspected.
138func (e *engine[TCtx, TEvt]) offerDescriptor(desc string) {
139 e.pendingExternal = &queuedEvent[TEvt]{descriptor: desc}
140}
141
142// step computes the next pending microstep without committing, or reports the
143// macrostep quiescent. Priority: eventless > internal event > external. §4.
144func (e *engine[TCtx, TEvt]) step() (ms *Microstep[TCtx], quiescent bool) {
145 var zero TEvt
146 if ts := selectEventlessTransitions(e.cfg, e.guardPass(zero)); len(ts) > 0 {
147 if e.alwaysRun >= e.alwaysLimit {
148 e.status = StatusError
149 e.errReason = ErrAlwaysLoopExceeded
150 return nil, true
151 }
152 e.alwaysRun++
153 return e.microstepFor(ts, zero, false), false
154 }
155 for len(e.internalQueue) > 0 {
156 qe := e.internalQueue[0]
157 e.internalQueue = e.internalQueue[1:]
158 if ts := selectTransitions(e.cfg, qe.descriptor, e.guardPass(qe.payload)); len(ts) > 0 {
159 return e.microstepFor(ts, qe.payload, true), false
160 }
161 // unmatched internal event is discarded; try the next one.
162 }
163 if e.pendingExternal != nil {
164 qe := *e.pendingExternal
165 e.pendingExternal = nil
166 if ts := selectTransitions(e.cfg, qe.descriptor, e.guardPass(qe.payload)); len(ts) > 0 {
167 return e.microstepFor(ts, qe.payload, true), false
168 }
169 // unhandled external event is dropped.
170 }
171 return nil, true
172}
173
174func (e *engine[TCtx, TEvt]) microstepFor(ts []*Transition, evt TEvt, triggered bool) *Microstep[TCtx] {
175 exitSet := computeExitSet(e.cfg, ts)
176 toEnter, _ := computeEntrySet(ts, e.hist)
177 return e.apply(exitSet, ts, toEnter, evt, triggered)
178}
179
180// apply builds the staged microstep on clones of the live state. §6/§7/§8.1.
181func (e *engine[TCtx, TEvt]) apply(exitSet []*StateNode, ts []*Transition, toEnter map[*StateNode]struct{}, evt TEvt, triggered bool) *Microstep[TCtx] {
182 e.lastEvt = evt
183 stageCfg := e.cfg.clone()
184 stageHist := cloneHistory(e.hist)
185 stageCtx := e.ctx
186 var effects []AppliedEffect[TCtx]
187
188 fold := func(callsite int) {
189 eff := e.applyAction(callsite, stageCtx, evt)
190 switch eff.Kind {
191 case EffectAssign:
192 stageCtx = eff.Ctx
193 case EffectSend, EffectSpawn:
194 effects = append(effects, eff)
195 }
196 }
197
198 for _, s := range exitSet { // reverse document order
199 recordHistoryInto(s, stageHist, e.cfg)
200 for _, a := range s.Exit {
201 fold(a.Callsite)
202 }
203 stageCfg.remove(s)
204 }
205 for _, t := range ts {
206 for _, a := range t.Actions {
207 fold(a.Callsite)
208 }
209 }
210
211 entered := orderedEntry(toEnter)
212 var doneStates []string
213 reachedFinal := false
214 for _, s := range entered {
215 stageCfg.add(s)
216 for _, a := range s.Entry {
217 fold(a.Callsite)
218 }
219 if s.Kind != StateFinal {
220 continue
221 }
222 if s.Parent == nil || s.Parent == e.def.Root {
223 reachedFinal = true
224 continue
225 }
226 doneStates = append(doneStates, "done.state."+string(s.Parent.ID))
227 if gp := s.Parent.Parent; gp != nil && gp.Kind == StateParallel && allRegionsFinal(gp, stageCfg) {
228 doneStates = append(doneStates, "done.state."+string(gp.ID))
229 }
230 }
231
232 return &Microstep[TCtx]{
233 Transitions: ts,
234 Exited: exitSet,
235 Entered: entered,
236 PrevActive: e.cfg.atomicIDs(),
237 NextActive: stageCfg.atomicIDs(),
238 PrevContext: e.ctx,
239 NextContext: stageCtx,
240 Effects: effects,
241 TriggeredByEvent: triggered,
242 ReachedFinal: reachedFinal,
243 cfg: stageCfg,
244 hist: stageHist,
245 internalEnqueue: doneStates,
246 }
247}
248
249// commit applies a staged microstep to the live engine state.
250func (e *engine[TCtx, TEvt]) commit(ms *Microstep[TCtx]) {
251 e.cfg = ms.cfg
252 e.hist = ms.hist
253 e.ctx = ms.NextContext
254 for _, d := range ms.internalEnqueue {
255 e.internalQueue = append(e.internalQueue, queuedEvent[TEvt]{descriptor: d})
256 }
257 switch {
258 case ms.ReachedFinal:
259 e.status = StatusDone
260 case e.status == StatusStarting:
261 e.status = StatusRunning
262 }
263 if ms.TriggeredByEvent {
264 e.alwaysRun = 0
265 }
266}
267
268func (c *configuration) clone() *configuration {
269 n := newConfiguration()
270 for k := range c.members {
271 n.members[k] = struct{}{}
272 }
273 return n
274}
275
276func (c *configuration) atomicIDs() []StateID {
277 at := c.atomic()
278 out := make([]StateID, len(at))
279 for i, n := range at {
280 out[i] = n.ID
281 }
282 return out
283}
284
285func cloneHistory(h map[StateID][]*StateNode) map[StateID][]*StateNode {
286 out := make(map[StateID][]*StateNode, len(h))
287 for k, v := range h {
288 out[k] = v
289 }
290 return out
291}
292
293// recordHistoryInto records the to-restore states for any history child of s,
294// reading the configuration before s is removed. §6.4.
295func recordHistoryInto(s *StateNode, hist map[StateID][]*StateNode, cfg *configuration) {
296 for _, h := range s.Children {
297 if h.Kind != StateHistory {
298 continue
299 }
300 var rec []*StateNode
301 if h.HistoryKind == HistoryDeep {
302 for _, n := range cfg.all() {
303 if n.IsAtomic() && n.IsDescendant(s) {
304 rec = append(rec, n)
305 }
306 }
307 } else {
308 for _, c := range s.Children {
309 if cfg.has(c) {
310 rec = append(rec, c)
311 }
312 }
313 }
314 hist[h.ID] = rec
315 }
316}
317
318// allRegionsFinal reports whether every region of a parallel state has an active
319// final descendant. §7.5.
320func allRegionsFinal(gp *StateNode, cfg *configuration) bool {
321 for _, r := range gp.Children {
322 final := false
323 for _, n := range cfg.all() {
324 if n.Kind == StateFinal && (n == r || n.IsDescendant(r)) {
325 final = true
326 break
327 }
328 }
329 if !final {
330 return false
331 }
332 }
333 return true
334}