Автоматы в коде: state machines, statecharts

Heartbleed (2014): уязвимость OpenSSL, позволявшая читать память сервера. Причина - некорректная обработка TLS heartbeat сообщений без проверки состояния соединения. Если бы TLS был закодирован как строгая FSM (как в rustls), heartbeat в неправильном состоянии был бы отклонён на уровне типов. State machines - это не теория, это безопасность.

• **rustls TLS library:** написана на Rust, кодирует TLS 1.3 как типобезопасную FSM. Каждое состояние - отдельный тип. Невозможно вызвать метод неправильного состояния без compile error. Используется в Cloudflare, AWS, Firefox
• **XState и Stately:** библиотека statecharts для JavaScript. 10M+ downloads в неделю. Stately Studio - визуальный редактор state machines. Microsoft Teams, Framer, Atlassian используют XState для управления сложным UI
• **Erlang OTP gen_statem:** поведение в OTP для кодирования FSM. Каждый process = actor = state machine. WhatsApp (Erlang), RabbitMQ, CockroachDB используют gen_statem для кодирования протоколов
• **Unity Animator (mecanim):** визуальная state machine для анимации персонажей. Каждый переход - условие на основе параметров. Blend trees - иерархические statecharts для плавных анимационных переходов

State machines в коде

**Finite State Machine (FSM)** в коде - прямая реализация DFA: множество состояний, текущее состояние, таблица переходов, функция выхода. FSM используются везде: TCP стек, парсеры, UI-компоненты, игровые NPC, компиляторы. Главное преимущество: поведение явно, переходы предсказуемы, тестируемость высокая.

Альтернатива явному FSM - **if/else спагетти**: бесконечные условия, глобальные флаги, неочевидные переходы. Это анти-паттерн, называемый «имплицитный FSM». Явный FSM с таблицей переходов: добавление нового состояния = новая строка в таблице. Тестирование: каждый переход проверяется независимо.

Statecharts: иерархические автоматы

**Statecharts** (Харел, 1987) - расширение FSM: иерархические состояния (вложенные), параллельные состояния, история состояний. XState (JavaScript) - популярная реализация statecharts для UI. Проблема плоских FSM: state explosion - 10 параллельных функций = 2^10 состояний. Statecharts решают через иерархию и параллелизм.

**XState** используется в Stately Studio, Cloudflare Workers, Microsoft Teams. **Erlang/Elixir gen_statem** - FSM в actor model. **Redux** неявно реализует FSM: reducer = функция перехода, action = событие. Явный statechart в Redux-Toolkit + XState - популярная архитектура для сложных UI.

Автоматы для валидации протоколов

Сетевые протоколы (TCP, HTTP/2, TLS, WebSocket) определяются через state machines. **TLS handshake** - строго определённая последовательность состояний. Нарушение порядка = ошибка или уязвимость. Современные TLS стеки (rustls, BoringSSL) кодируют протокол как FSM и проверяют каждый переход.

**rustls** (Rust TLS library) кодирует TLS 1.3 handshake как строгую FSM. Невалидные переходы невозможны на уровне типов (state encoded in generics). Это называется **типобезопасный State Pattern** - компилятор гарантирует корректность протокола. Ошибки в реализации TLS (Heartbleed, BEAST) часто связаны с некорректными переходами состояний.

Автоматы в игровом AI и UI

**Behavior Trees** и **FSM** - два основных подхода к game AI. FSM: простые NPC с конечным числом состояний (patrol, alert, attack, flee). Behavior Trees: иерархическое принятие решений, широко используются в AAA-играх (Halo, GTA). Unity Animator и Unreal Blueprints реализуют визуальные statecharts для NPC.

**React компоненты** неявно реализуют FSM через useState. Явный statechart с XState делает переходы предсказуемыми: нет невалидных состояний вроде (loading=true, error=true). **The Actor Model** (Erlang, Akka, XState) - каждый актор = FSM, взаимодействие через сообщения. Это масштабируемая архитектура для распределённых систем.

Итоги

• **FSM в коде:** явная таблица переходов vs неявный if/else. FSM: добавление состояния = одна строка, тестируемость каждого перехода, невалидные состояния невозможны
• **Statecharts (Харел):** иерархия + параллелизм + история. Решают state explosion плоских FSM. XState - популярная реализация для UI
• **Протоколы как FSM:** TCP, TLS, HTTP парсеры. rustls кодирует TLS состояния в типы - compile-time корректность протокола
• **Game AI и UI:** NPC behavior через FSM/Behavior Trees. React компоненты неявно реализуют FSM - явный statechart предотвращает невалидные комбинации состояний

Связанные темы

Автоматы в коде - прямое применение теории конечных автоматов:

• Детерминированные конечные автоматы — FSM в коде - прямая реализация DFA: состояния, переходы, функция выхода
• Regex на практике — Regex движки - специализированные FSM для сопоставления с образцом
• Формальная верификация — Model checking верифицирует FSM-модели систем на соответствие темпоральным свойствам

Вопросы для размышления

• Redux reducer - это функция перехода FSM. Какие именно компоненты Redux соответствуют компонентам FSM: состояниям, событиям, функции перехода?
• Heartbleed был вызван отсутствием проверки состояния TLS. Как типобезопасная FSM в rustls предотвращает подобные уязвимости?
• Behavior Trees популярнее FSM для сложного игрового AI. В чём ограничения FSM при росте сложности и как Behavior Trees их решают?

Связанные уроки

• comp-07-regex-in-lexer