Formal State Machines and Advanced Concepts

In this lesson, we'll explore formal state machine concepts, including guards, conditions, hierarchical states, and state history. We'll also compare the State pattern with the Strategy pattern.

Formal State Machine Concepts

A state machine (or finite state machine - FSM) is a mathematical model of computation that consists of:

• States: A finite set of conditions the system can be in
• Transitions: Rules for moving from one state to another
• Events: Triggers that cause transitions
• Actions: Operations performed during transitions or within states

State Machine Diagram

1                    cancel
2        ┌───────────────────────────────┐
3        │                               │
4        ▼                               │
5    ┌─────────┐  pay      ┌──────┐     │
6    │ Created │──────────►│ Paid │─────┘
7    └─────────┘           └───┬──┘
8                              │ process
9                              ▼
10                        ┌────────────┐
11                        │ Processing │
12                        └─────┬──────┘
13                              │ ship
14                              ▼
15                         ┌─────────┐
16                         │ Shipped │
17                         └────┬────┘
18                              │ deliver
19                              ▼
20                        ┌───────────┐
21                        │ Delivered │
22                        └───────────┘

State Machine Table

Guards and Conditions

Guards are boolean conditions that must be true for a transition to occur:

typescript
1interface OrderState {
2  pay(context: OrderContext): void;
3  process(context: OrderContext): void;
4  ship(context: OrderContext): void;
5  deliver(context: OrderContext): void;
6  cancel(context: OrderContext): void;
7
8  getStatusName(): string;
9}
10
11class PaidState extends AbstractOrderState {
12  getStatusName(): string {
13    return 'Paid';
14  }
15
16  process(context: OrderContext): void {
17    // Guard: Check if inventory is available
18    if (!this.checkInventoryAvailable(context)) {
19      console.log(`Cannot process order ${context.id} - insufficient inventory`);
20      return;
21    }
22
23    // Guard: Check if payment is verified
24    if (!this.verifyPayment(context)) {
25      console.log(`Cannot process order ${context.id} - payment verification failed`);
26      return;
27    }
28
29    // All guards passed - perform transition
30    console.log(`Starting processing for order ${context.id}`);
31    this.transitionTo(context, new ProcessingState(), 'Processing initiated for');
32  }
33
34  private checkInventoryAvailable(context: OrderContext): boolean {
35    // Simulate inventory check
36    return context.items.length > 0;
37  }
38
39  private verifyPayment(context: OrderContext): boolean {
40    // Simulate payment verification
41    return context.getTotalAmount() > 0;
42  }
43}

Complex Guards with Multiple Conditions

typescript
1class ProcessingState extends AbstractOrderState {
2  getStatusName(): string {
3    return 'Processing';
4  }
5
6  ship(context: OrderContext): void {
7    const checks = {
8      itemsPicked: this.areItemsPicked(context),
9      qualityChecked: this.isQualityChecked(context),
10      labelGenerated: this.isLabelGenerated(context),
11      carrierAvailable: this.isCarrierAvailable(context)
12    };
13
14    // Log failed checks
15    const failedChecks = Object.entries(checks)
16      .filter(([_, passed]) => !passed)
17      .map(([check]) => check);
18
19    if (failedChecks.length > 0) {
20      console.log(`Cannot ship order ${context.id}. Failed checks: ${failedChecks.join(', ')}`);
21      return;
22    }
23
24    // All checks passed
25    console.log(`All pre-shipment checks passed for order ${context.id}`);
26    this.transitionTo(context, new ShippedState(), 'Shipped');
27  }
28
29  private areItemsPicked(context: OrderContext): boolean {
30    return true; // Simulate check
31  }
32
33  private isQualityChecked(context: OrderContext): boolean {
34    return true; // Simulate check
35  }
36
37  private isLabelGenerated(context: OrderContext): boolean {
38    return true; // Simulate check
39  }
40
41  private isCarrierAvailable(context: OrderContext): boolean {
42    return true; // Simulate check
43  }
44}

State History and Memento

Track state changes over time using the Memento pattern:

typescript
1interface StateSnapshot {
2  stateName: string;
3  timestamp: Date;
4  metadata?: Record<string, any>;
5}
6
7class OrderContext {
8  private state: OrderState;
9  private stateHistory: StateSnapshot[] = [];
10  public readonly id: string;
11  public readonly items: string[];
12
13  constructor(id: string, items: string[]) {
14    this.id = id;
15    this.items = items;
16    this.state = new CreatedState();
17    this.saveSnapshot();
18  }
19
20  setState(state: OrderState): void {
21    this.state = state;
22    this.saveSnapshot();
23  }
24
25  private saveSnapshot(): void {
26    this.stateHistory.push({
27      stateName: this.state.getStatusName(),
28      timestamp: new Date(),
29      metadata: this.captureMetadata()
30    });
31  }
32
33  private captureMetadata(): Record<string, any> {
34    const metadata: Record<string, any> = {
35      itemCount: this.items.length
36    };
37
38    // Capture state-specific metadata
39    if (this.state instanceof ShippedState) {
40      metadata.trackingInfo = this.state.getTrackingInfo();
41    }
42
43    return metadata;
44  }
45
46  getHistory(): ReadonlyArray<StateSnapshot> {
47    return this.stateHistory;
48  }
49
50  getTimeInState(stateName: string): number {
51    const entries = this.stateHistory.filter(s => s.stateName === stateName);
52    if (entries.length === 0) return 0;
53
54    const enter = entries[0].timestamp.getTime();
55    const exit = entries.length > 1
56      ? entries[entries.length - 1].timestamp.getTime()
57      : Date.now();
58
59    return exit - enter;
60  }
61
62  printStateTimeline(): void {
63    console.log(`\nState Timeline for Order ${this.id}:`);
64    this.stateHistory.forEach((snapshot, index) => {
65      const duration = index < this.stateHistory.length - 1
66        ? this.stateHistory[index + 1].timestamp.getTime() - snapshot.timestamp.getTime()
67        : Date.now() - snapshot.timestamp.getTime();
68
69      console.log(
70        `  ${index + 1}. ${snapshot.stateName.padEnd(12)} - ` +
71        `${snapshot.timestamp.toISOString()} (${duration}ms)`
72      );
73    });
74  }
75
76  // Delegate to state
77  pay(): void { this.state.pay(this); }
78  process(): void { this.state.process(this); }
79  ship(): void { this.state.ship(this); }
80  deliver(): void { this.state.deliver(this); }
81  cancel(): void { this.state.cancel(this); }
82  getStatusName(): string { return this.state.getStatusName(); }
83}

Hierarchical States (Nested State Machines)

Some states can have sub-states, creating a hierarchy:

1Processing State
2├── Picking Items
3│   ├── Scanning
4│   └── Verifying
5├── Quality Check
6│   ├── Inspecting
7│   └── Photographing
8└── Packing
9    ├── Boxing
10    └── Labeling

typescript
1interface SubState {
2  getName(): string;
3  execute(context: OrderContext): void;
4  canTransition(): boolean;
5}
6
7class PickingSubState implements SubState {
8  private itemsScanned: number = 0;
9
10  getName(): string {
11    return 'Picking Items';
12  }
13
14  execute(context: OrderContext): void {
15    console.log(`Picking items for order ${context.id}`);
16    this.itemsScanned = context.items.length;
17  }
18
19  canTransition(): boolean {
20    return this.itemsScanned > 0;
21  }
22}
23
24class QualityCheckSubState implements SubState {
25  private inspected: boolean = false;
26
27  getName(): string {
28    return 'Quality Check';
29  }
30
31  execute(context: OrderContext): void {
32    console.log(`Performing quality check for order ${context.id}`);
33    this.inspected = true;
34  }
35
36  canTransition(): boolean {
37    return this.inspected;
38  }
39}
40
41class PackingSubState implements SubState {
42  private packed: boolean = false;
43
44  getName(): string {
45    return 'Packing';
46  }
47
48  execute(context: OrderContext): void {
49    console.log(`Packing order ${context.id}`);
50    this.packed = true;
51  }
52
53  canTransition(): boolean {
54    return this.packed;
55  }
56}
57
58class ProcessingState extends AbstractOrderState {
59  private subStates: SubState[];
60  private currentSubStateIndex: number = 0;
61
62  constructor() {
63    super();
64    this.allowedTransitions = ['Shipped'];
65    this.subStates = [
66      new PickingSubState(),
67      new QualityCheckSubState(),
68      new PackingSubState()
69    ];
70  }
71
72  getStatusName(): string {
73    return 'Processing';
74  }
75
76  onEnter(context: OrderContext): void {
77    console.log(`Order ${context.id} entering processing pipeline`);
78    this.executeSubStates(context);
79  }
80
81  private executeSubStates(context: OrderContext): void {
82    for (const subState of this.subStates) {
83      console.log(`  → ${subState.getName()}`);
84      subState.execute(context);
85
86      if (!subState.canTransition()) {
87        console.log(`    Failed at ${subState.getName()}`);
88        return;
89      }
90    }
91
92    console.log(`  ✓ All processing steps completed`);
93  }
94
95  ship(context: OrderContext): void {
96    // Verify all substates completed
97    const allCompleted = this.subStates.every(s => s.canTransition());
98
99    if (!allCompleted) {
100      console.log(`Cannot ship - processing not complete`);
101      return;
102    }
103
104    this.transitionTo(context, new ShippedState(), 'Ready to ship');
105  }
106}

State vs Strategy Pattern

While structurally similar, State and Strategy patterns serve different purposes:

Similarities

Both patterns:

• Use composition over inheritance
• Define a family of algorithms/behaviors
• Encapsulate behavior in separate classes
• Follow the Open/Closed Principle

Key Differences

typescript
1// STATE PATTERN: States know about each other and trigger transitions
2class PaidState implements OrderState {
3  process(context: OrderContext): void {
4    // State transitions to another state
5    context.setState(new ProcessingState());
6  }
7}
8
9// STRATEGY PATTERN: Strategies are independent, client changes them
10class GroundShipping implements ShippingStrategy {
11  calculate(weight: number): number {
12    // Just calculates cost, doesn't know about other strategies
13    return weight * 5;
14  }
15}
16
17class ShippingCalculator {
18  private strategy: ShippingStrategy;
19
20  setStrategy(strategy: ShippingStrategy): void {
21    // Client explicitly changes strategy
22    this.strategy = strategy;
23  }
24
25  calculate(weight: number): number {
26    return this.strategy.calculate(weight);
27  }
28}

Comparison Table

When to Use Each

Use State Pattern when:

• Object behavior changes based on internal state
• Multiple conditional statements based on state
• State transitions follow defined rules
• Example: Order processing, document workflow, game character

Use Strategy Pattern when:

• Multiple algorithms can solve the same problem
• Client needs to choose algorithm at runtime
• Algorithms are independent and interchangeable
• Example: Shipping cost calculation, payment methods, sorting

Combined Example

You can use both patterns together:

typescript
1// State pattern for order lifecycle
2class ShippedState extends AbstractOrderState {
3  // Strategy pattern for delivery method
4  private deliveryStrategy: DeliveryStrategy;
5
6  constructor(deliveryStrategy: DeliveryStrategy) {
7    super();
8    this.deliveryStrategy = deliveryStrategy;
9  }
10
11  deliver(context: OrderContext): void {
12    // Use strategy to calculate delivery details
13    const deliveryDate = this.deliveryStrategy.calculateDeliveryDate(context);
14    console.log(`Estimated delivery: ${deliveryDate}`);
15
16    // State transition
17    this.transitionTo(context, new DeliveredState(), 'Delivered');
18  }
19}
20
21interface DeliveryStrategy {
22  calculateDeliveryDate(context: OrderContext): Date;
23}
24
25class StandardDelivery implements DeliveryStrategy {
26  calculateDeliveryDate(context: OrderContext): Date {
27    const date = new Date();
28    date.setDate(date.getDate() + 5);
29    return date;
30  }
31}
32
33class ExpressDelivery implements DeliveryStrategy {
34  calculateDeliveryDate(context: OrderContext): Date {
35    const date = new Date();
36    date.setDate(date.getDate() + 2);
37    return date;
38  }
39}

State Machine Validation

Validate state machine configuration at startup:

typescript
1class StateMachineValidator {
2  static validate(states: OrderState[]): { valid: boolean; errors: string[] } {
3    const errors: string[] = [];
4
5    // Check for duplicate state names
6    const stateNames = states.map(s => s.getStatusName());
7    const duplicates = stateNames.filter((name, index) => stateNames.indexOf(name) !== index);
8    if (duplicates.length > 0) {
9      errors.push(`Duplicate states found: ${duplicates.join(', ')}`);
10    }
11
12    // Check for unreachable states
13    const reachableStates = new Set<string>();
14    states.forEach(state => {
15      // Simulate finding reachable states (simplified)
16      reachableStates.add(state.getStatusName());
17    });
18
19    // Check for invalid transitions
20    // (would need transition table for full validation)
21
22    return {
23      valid: errors.length === 0,
24      errors
25    };
26  }
27}

Key Takeaways

• Formal state machines define states, transitions, events, and actions
• Guards are conditions that must be true for transitions to occur
• State history tracks transitions and time spent in each state
• Hierarchical states allow states to have sub-states
• State pattern manages state transitions; Strategy pattern selects algorithms
• States can use strategies internally for specific behaviors
• Validate state machine configuration to catch errors early

In the next workshop, you'll implement a complete order lifecycle state machine with guards, state history, and comprehensive testing.