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

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


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

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

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

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

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

Состояние

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



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

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

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

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

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

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

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



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

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

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



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

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

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

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



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

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

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

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

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

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

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

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



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



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



В Model-View-ViewModel состояние находится во ViewModel. Независимо от того, реактивные у нас биндинги или нет, поведение модуля, определенного в метафоре MVVM, будет фиксироваться во 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-канале. А если хотите получать информацию о новых расшифровках и интересных докладах, подпишитесь на тематическую рассылку.