Хабрахабр

Как не выстрелить себе в ногу из конечного автомата

Конечный автомат редко применяется мобильными разработчиками. Хотя большинство знает принципы работы и легко реализует его самостоятельно. В статье разберемся, какие задачи решаются конечным автоматом на примере iOS-приложений. Рассказ носит прикладной характер и посвящен практическим аспектам работы.

Под катом вы найдете дополненную расшифровку выступления Александра Сычева (Brain89) на AppsConf, в котором он поделился вариантами применения конечного автомата при разработке неигровых приложений.

О спикере: Александр Сычев занимается iOS-разработкой восемь лет, за это время участвовал в создании как простых приложений, так и сложных клиентов для социальных сетей и финансового сектора. В данный момент является техлидом в компании Сбербанк.
В программирование приходят из множества сфер, имея разное образование и опыт, поэтому сначала вспомним базовую теорию.

Постановка задачи

Конечный автомат — это математическая абстракция, которая состоит из трех основных элементов:

  • множества внутренних состояний,
  • множества входных сигналов, которые определяют переход из текущего состояния в следующее,
  • множества конечных состояний, при переходе в которые автомат завершает работу («допускает входное слово x»).

Состояние

Под состоянием будем понимать переменную или группу переменных, которые определяют поведение объекта. Например, в стандартном приложении iOS «Настройки » есть пункт «Жирный шрифт» («Основные → Универсальный доступ»). Значение этого пункта позволяет переключаться между двумя вариантами отображения текста на дисплее устройства.

Находясь в разных состояниях и получая один и тот же сигнал, объект по-разному реагирует на изменение состояния. Посылая один и тот же сигнал «Изменить значение тумблера», получаем разную реакцию системы: либо обычное начертание шрифта, либо полужирное — всё просто.

Традиционные задачи

В практике программисты часто сталкиваются с конечным автоматом.

Игровые приложения

Это первое, что приходит в голову — в рамках игрового процесса практически всё определяется текущим игровым состоянием. Так, компания Apple предполагает использование конечных автоматов прежде всего в игровых приложениях (позднее подробно разберем это).

Например: Поведение системы при обработке одинакового сигнала, но разном внутреннем состоянии можно проиллюстрировать следующими примерами.

В зависимости от этого состояния определяется поведение врагов: они либо нападают, либо убегают.   ● игровой персонаж может быть разной силы: один — в механической броне и с лазерной пушкой, а другой — слабо прокаченный.

  ● игра находится на паузе — не надо отрисовывать текущий кадр; игрок в режиме меню или в игровом процессе — отрисовка совсем другая.

Анализ текстов

Одна из популярных задач анализа текста, связанная с применением конечного автомата, — спам-фильтры. Пусть есть набор стоп-слов и входная последовательность. Нужно либо отфильтровать эту последовательность, либо вообще ее не выводить.

Для ее решения используется алгоритм Кнута-Морриса-Пратта, программная реализация которого представляет собой конечный автомат. Формально, это задача поиска подстроки в строке. В качестве состояния выступает смещение входной последовательности и количество найденных символов в паттерне — стоп-слове.

Также, при анализе регулярных выражений часто используются конечные автоматы.

Параллельная обработка запросов

Конечный автомат — один из вариантов реализации обработки запросов и выполнения строгого набора инструкций.

В зависимости от конкретного протокола выбирается определенная реализация state machine, и соответственно, выполняется известный набор инструкций. Например, в веб-сервере nginx обработка входных запросов различных протоколов осуществляется с помощью конечных автоматов.

В целом, получается два класса задач:

  • управление логикой сложного объекта с комплексным внутренним состоянием,
  • формирование потоков управления и данных (описание алгоритма).

Очевидно, что такие общие задачи встречаются в практике любого программиста. Поэтому использование конечного автомата возможно в том числе и в неигровых, контентных приложениях, которыми занимаются большинство мобильных разработчиков.

Далее разберем, где и когда конечный автомат может быть использован при создании типичных iOS-приложений.

Есть три базовых слоя. У большинства мобильных приложений слоистая архитектура.

  • Представление (Presentation layer).
  • Бизнес-логика (Business logic layer).
  • Набор хелперов, сетевых клиентов и так далее (Core layer).

Как указано выше, конечный автомат управляет объектами со сложным поведением, т.е. с комплексным состоянием. Такие объекты точно есть в слое представления, потому что он принимает решения, обрабатывая пользовательский ввод или сообщения от операционной системы. Посмотрим на различные подходы к его исполнению.

Логично, что один из вариантом реализации контроллера — конечный автомат. В классической архитектурной метафоре Model-View-Controller состояние будет в контроллере: он принимает решение, что отображается во View и как реагировать на входные сигналы: нажатие кнопки, изменение ползунка и так далее.

В VIPER состояние находится в presenter: именно он определяет конкретный навигационный переход из текущего экрана и отображение данных во View.

Независимо от того, реактивные у нас биндинги или нет, поведение модуля, определенного в метафоре MVVM, будет фиксироваться во ViewModel. В Model-View-ViewModel состояние находится во ViewModel. Очевидно, его реализация через конечный автомат — допустимый вариант.

Например, сетевой клиент, который в зависимости от того, установлено или нет соединение с сервером, отправляет или блокирует запросы. На слое бизнес-логики приложения также встречаются сложные объекты с нетривиальным набором состояний. Или объект по работе с базой данных, которому нужно транслировать функции языка в SQL-запрос, выполнить его, получить ответ, транслировать в объекты и т.д.

В более специфичных задачах, таких как платежный модуль, в котором шире набор состояний, сложная логика, также корректно применение конечного автомата.

Ими надо уметь управлять. В итоге получаем, что в мобильных приложениях присутствует множество объектов, состояние и логика поведения которых описываются сложнее, чем одним предложением.

Рассмотрим реальный пример и поймем, в какой момент действительно необходим конечный автомат, а где его применение не оправдано.

Этот контроллер отображает набор комментариев в табличном виде. Рассмотрим ViewController из iOS-приложения «Чемпионат» — популярного спортивного ресурса. Экран довольно простой: нижележащий слой отдает данные, они обрабатываются и выводятся на экран.
Пользователи заходят в описание матча, просматривают фотографии, читают новости и оставляют свои комментарии.

Так появляется первый условный оператор, первое ветвление, определяющее дальнейшее поведение приложения. На отображение могут быть переданы или реальные данные, или ошибка.

Является ли это состояние ошибкой? Далее возникает вопрос, что делать, если данных нет. Например, хоккей в Египте мало кому интересен, в такой статье обычно не бывает комментариев. Скорее всего, нет: не к каждой новости есть комментарии пользователей. Так появляется второй условный оператор. Это нормальное поведение и нормальное состояние экрана, которое нужно уметь отображать.

В этом случае корректно показать индикатор загрузки. Логично предположить, что также есть стартовое состояние, в котором пользователь ожидает данные (например, когда экран комментариев только отобразился на экране). Это уже третий условный оператор.

Так получается уже четыре состояния на один простой экран, логика отображения которых описана через конструкцию if-else-if-else.

Итеративное развитие экрана приводит к запутанному клубку из условных конструкций, кучи флагов или к громоздкому множественному switch-case. А что, если таких состояний больше? Представьте, что разработчик, который будет его поддерживать, знает, где вы живете и у него есть бензопила, которую он всегда носит с собой. Такой код пугает. А вы так хотите дожить до своей маленькой, но заслуженной пенсии.

Думаю, в этом случае стоит задуматься, стоит ли оставлять такую реализацию в приложении.

Недостатки

Давайте поймем, что нам не нравится в этом коде.

Прежде всего, его тяжело читать.

Соответственно, он потратит много времени на анализ логики поведения приложения — повышается стоимость поддержки и развития. Раз код плохо читается, значит, новому разработчику будет трудно разобраться, что именно реализовано в конкретном месте проекта.

Если нужно добавить новое состояние, которое не следует из текущей лесенки, возможно, это вообще не удастся! Этот код негибкий. Практически, никак. Если нужен сквозной переход — резко бросить прохождение проверок по этой лесенке — как это сделать?

Когда переходы описаны через switch case, скорее всего, реализовано поведение по умолчанию. Также при таком подходе нет защиты от фиктивных состояний. Это состояние логично с точки зрения поведения программы, но вряд ли логично с точки зрения человеческой или бизнес-логики приложения.

Конечно, это построение логики каждого модуля / контроллера / сложного объекта, не основываясь на интуиции, а используя хороший формализованный подход. Какое может быть решение обозначенных недостатков? Например, конечный автомат.

GameplayKit

В качестве примера для реализации возьмем то, что предлагает компания Apple. В рамках фреймворка GameplayKit есть два класса, которые помогают нам работать с конечным автоматом.

  • GKState.
  • GKStateMachine.

По названию фреймворка понятно, что Apple хотела, чтобы его применяли в играх. Но и в неигровых приложениях он будет полезен.

Для его описания нужно выполнить простые действия. Класс GKState определяет состояние. Наследуемся от этого класса, задаем имя состояния и определяем три метода.

  • isValidNextState — валидное ли текущее состояние, исходя из предыдущего.
  • didEnterFrom — действия при переходе в это состояние.
  • willExitTo — действия при выходе из этого состояния.

Тут еще проще. GKStateMachine — класс конечного автомата. Достаточно выполнить два действия.

  • Передаем набор входных состояний типизированным массивом через инициализатор.
  • Осуществляем переходы в зависимости от входных сигналов с помощью метода enter. Через него также задается начальное состояние.

Может смутить тот факт, что в качестве аргумента метода enter передается любой класс. Но надо обратить внимание, что объект любого класса не может быть задан в массиве состояний  это запрещает строгая типизация. Соответственно, если задать в качестве класса следующего состояния произвольный класс, просто ничего не произойдет, а метод enter вернет false.

Состояния и переходы между ними

Познакомившись с фреймворком от Apple, вернемся к примеру. Надо описать состояния и переходы между ними. Сделать это нужно в наиболее понятной форме. Есть два распространенных варианта: таблицей или в виде графа переходов. Граф переходов, на мой взгляд, более понятный вариант. Он есть в UML в стандартизованном варианте. Поэтому выберем его.

В примере есть начальное состояние  ожидаем данные  и есть три состояния, в которые можно попасть из начального: данные получены, данных нет и ошибка. В графе переходов есть состояния, которые описаны именами, и стрелочки, которыми соединены эти состояния для описания переходов.

В реализации получим четыре небольших класса.

При входе стоит отобразить индикатор загрузки. Разберем состояние «Ожидание данных». Для этого нужно иметь слабую ссылку на ViewController, которым управляет создаваемый конечный автомат. А при выходе из этого состояния  скрыть его.

Параметры автомата

Второй шаг, который нужно сделать  задать параметры конечного автомата. Для этого создаем состояния и передаем их в объект автомата.

Также обязательно задаем начальное состояние

Теперь необходимо обрабатывать реакции на внешние события, изменяя состояние автомата. В принципе, все, автомат готов.

У нас получилась лесенка из if-else, на основе которой принималось решение, какое действие нужно выполнить. Вспомним постановку задачи. В качестве управления простым автоматом такой вариант реализации может быть (собственно, простой switch  это и есть примитивная реализация конечного автомата), но так практически не избавляемся от ранее указанных недостатков.

Предложен он классиками программирования  так называемой «бандой четырех». Есть другой подход, который позволит уйти от подобных лесенок.

Есть специальный паттерн проектирования, который так и называется  «Состояние».

Он позволяет объекту менять свое поведение в зависимости от состояния. Это поведенческий шаблон, похожий на стратегию, который описывает абстракцию конечного автомата. Таким образом, конечный автомат, который изначально принимал решение, какое вызвать состояние, теперь будет передавать сигнал, транслировать его в состояние, а состояние будет принимать решение. Основная цель применения  инкапсулировать поведение и данные, связанные с конкретным состоянием, в отдельном классе. Так частично разгрузим лесенку, и код станет более приятным в использовании.

Он предполагает, что GKStateMachine будет принимать решение. Стандартный фреймворк так не умеет. Внутри этого метода можно делегировать выбор следующего состояния текущему Поэтому расширим конечный автомат новым методом, где в качестве конфигурации передадим описание всех условных переменных, однозначно определяющих следующее состояние.

Далее делегируем выбор следующего состояния в текущее. Хорошая практика — описать состояние одним объектом и всегда передавать его, а не писать много-много входных параметров. Вот и весь апгрейд.

Достоинства GameplayKit.

  • Стандартная библиотека. Не надо ничего загружать, использовать cocoapods или carthage.
  • Библиотека достаточно проста в изучении.
  • Есть сразу две реализации: на Objective-C и на Swift.

Недостатки:

  • Реализации состояний и переходов тесно связаны.
    Нарушается принцип единственной ответственности: состояние знает, куда оно переходит и как.
  • Дубликаты состояний никак не контролируются.
    В state machine передается массив, а не множество состояний. Если передать несколько одинаковых состояний — будет использовано последнее из списка.

Какие еще есть варианты реализации конечного автомата? Посмотрим на GitHub.

Реализации на Objective-C

TransitionKit

Это самая популярная, уже давно существующая библиотека на Objective-C, лишенная недостатков, выявленных у GamePlayKit. Она позволяет нам реализовать конечный автомат и все действия, связанные с ним, на блоках.

Состояние отделено от переходов.

В рамках TransitionKit есть 2 класса.

  1. TKState — для задания состояний и входных, выходных действий.
  2. TKEvent — класс для описания перехода.
    TKEvent связывает одни состоянии с другими. Само событие определяется просто строкой.

Кроме того, появляются дополнительные преимущества.

Это работает так же, как и при использовании NSNotificationCenter. Можно передавать полезные данные при переходе. Весь полезный payload приходит в виде словаря userInfo, а пользователь сам разбирает информацию.

При попытке выполнить несуществующий — невозможный переход — получим не только значение NO при возврате из метода перехода, но и подробное описание ошибки, что полезно при отладке конечного автомата. Ошибочный переход имеет описание.

Это довольно наглядный пример, как конечный автомат может применяться в ядре приложения при реализации сетевых операций. TransitionKit используется в популярном сетевом комбайне RestKit.

На вход он принимает обрабатываемую операцию и очередь для ее исполнения. В RestKit есть специальный класс — RKOperationStateMachine — для управления параллельными операциями.

После старта обработки (и при любых переходах) state machine запускает на управление заранее определенный пользователем блок кода в указанной при создании очереди. Внутренне state machine очень простая: три состояния (готова, выполняется, завершена) и два перехода: начать и завершить выполнение.

State machine заботится об Связанная со своим автоматом операция передает внешние события в автомат, а он выполняет переходы между состояниями и все связанные действия.

  • асинхронном выполнении кода,
  • атомарности выполнения кода при переходах,
  • контроле правильности переходов,
  • отмене операций,
  • правильности изменения переменных состояния операции: isReady, isExecuting, isFinished.

Shift

Помимо TransitionKit отдельно стоит упомянуть Shift — крохотную библиотеку, реализованную как категория над NSObject. Такой подход позволяет превратить любой объект в конечный автомат, описав его состояния в виде строковых констант и действия в блоках при переходах. Конечно, это больше учебный проект, но довольно интересный и позволяет с минимальными затратами попробовать, что такое конечный автомат.

Реализации на Swift

Выделю одну (замечание: к сожалению, последние два года после доклада проект не развивается, но заложенные в него идеи стоит рассказать в статье). На Swift существует множество реализаций конечного автомата.

SwiftyStateMachine

В SwiftyStateMachine конечный автомат представлен немутабельной структурой, через методы didSet у свойства можно легко ловить изменения состояния.

Эта схема описывается отдельно от объекта, которым будет управлять автомат. В этой библиотеке конечный автомат задается через таблицу соответствий состояний и переходов между ними. Реализуется это через вложенный switch-case.

Ключевые характеристиками, достоинствами этой библиотеки являются.

  • Необходимость полностью описать схему переходов между состояниями.
    Это позволяет получить ошибку на этапе компиляции, если не будет обработан переход для конкретного состояния.
  • Жесткий контроль входных сигналов.
    Нельзя передать в state machine сигнал, который не определен или который определен для другой state machine.
  • Разделение схемы и объекта, которым она управляет, позволяет экономить время на инициализации автомата.
  • Визуализация, используя язык описания графов DOT.
    Есть графический язык разметки для работы со state-диаграммами — DOT. Эта библиотека использует его, чтобы указать, как будет визуализирован конечный автомат.

Заключение

Давайте отметим основные достоинства применения конечного автомата в мобильных приложениях.

  • Формализация.
    При описании задачи через конечный автомат необходимо задумываться обо всех состояниях, в которых может оказаться объект. Так получаем и документацию, и можем выявить не рассмотренные в постановке задачи моменты. Соответственно, упрощается тестирование кода.
  • Контроль потоков данных.
    Явное управление последовательностью вызовов (потоком управления).
  • Контроль ошибок.
    Если конечный автомат попадает в ошибочное состояние, то это просто значит, что при проектировании забыли определить еще одно состояние.
  • Единая точка входа для логирования и сбора статистики. Например, SwiftyStateMachine позволяет явно указать конкретный блок, в котором можно залогировать, что происходит с нашими данными. Это существенно упрощает отладку приложений.
  • История операций.
    Используя конечный автомат, можно реализовать отмену операций. Или, наоборот, восстановить всю картину переходов между состояниями. Стек операций обычно хранится в самом состоянии.

Теперь разберем несколько реальных примеров применения конечного автомата.

Отличным примером может служить заказ такси, содержащий большое количество состояний. Конечный автомат часто применяется для контроля алгоритма. Если их делать грубо, интуитивно, то получится большой switch case: ждем машину, машина приехала, оплата — все не влезет на слайд.

Есть состояние размещения заказа. Давайте формализуем. Приезжает водитель, пользователь отправляется в путешествие, производит оплату, потом заказ перемещается в историю. Пользователь ждет его подтверждения, может отменить. После происходит оценка заказа.

Это параллелит и упрощает работу. Теперь опишем состояния в компактных классах, которые можно распределить между командой разработчиков, и каждый из них будет протестирован.

В приложении для магазина можно формализовать заказ: его путешествие от корзины до потребителя, — с помощью конечного автомата. Другая похожая задача — это оформление заказа.

В приложении «Афиша-Рестораны» конечный автомат применен для оплаты заказа.

Для формализации задач достаточно получить от дизайнера все экраны. Кстати, необязательно описывать диаграмму переходов.

Управление этой историей можно делегировать конкретному суперобъекту, который будет определять правила внутри этой истории. Еще одним вариантом применения конечного автомата являются app coordinators — это набор инструкций, набор последовательности жестко заданных действий, полностью описывающий пользовательскую историю: авторизацию, выполнение заказа и так далее.

У него есть набор сигналов и переходы между ними по заданным состояниям. Если приглядеться, app coordinator выглядит, как state machine. Введение дополнительной абстракции увеличивает количество кода, соответственно, увеличивает время разработки, но зато этот код будет полностью протестирован и формализован. Логично, что если реализовать app coordinators как state machine, можно свести все переходы приложения к иерархии конечных автоматов, и, тем самым, полностью формализовать задачу. Такие преимущества очень подкупают.

Итак, state machine стоит применять, когда действительно нужна формализация, высокая тестируемость кода и нужно распределить задачи между разработчикам.

Это плохая практика, и она никак не поможет с развитием вашего приложения. Не надо пытаться использовать state machine для объектов, в которых есть один if-else.

В этом году на Apps Conf 2018, которая пройдет 8 и 9 октября, Александр планирует обсудить пять основных принципов объектно-ориентированного программирования и границы их применимости.

А если хотите получать информацию о новых расшифровках и интересных докладах, подпишитесь на тематическую рассылку.
Другие доклады по мобильной разработке, смотрите на нашем YouTube-канале.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть