Конечный автомат на bash

    Думаю все из нас, кто учился на ИТ-специальностях, в университете изучали конечные автоматы. Для тех, кто не в курсе, это абстрактный автомат способный находиться в конечном количестве состояний, переход из одного состояния в другое происходит при выполнение некоторых условий. Штука интересная, но не совсем понятно когда и как это можно применить для решения реальных задач. О том, как я пришел к решению возникшей задачи на основе конечного автомата, а также о том, как реализовал его на bash, я бы и хотел рассказать. А в качестве бонуса опишу как сохранять его состояние для возможности восстановить работу с прерванной точки.

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

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

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

    if [[ $STEP == 'step3' || $STEP == 'step4'  || … || $STEP == 'step10' ]]
    


    на каждом шаге переменной $STEP присваивается значение следующего шага:

    if [[ $STEP == 'step3' ]]
    then
        # Полезные действия. Возможно выход.
        STEP='step4'
    fi
    if [[ $STEP == 'step4' ]]
    then
        # Полезные действия. Возможно выход.
        STEP='step5'
    fi
    


    Теперь если в самом начале присвоить переменной STEP значение шага, мы сразу перейдем к нему, а далее выполнение скрипта будет последовательным.

    Однако немного поразмыслив, я понял что ждать пока операторы выполнят свою часть работы не всегда нужно. Иногда можно отравить сообщение и продолжить работу пропустив один-два шага, а к ним вернуться позже. Скрипт начал приобретать вот такой вид:

    if [[ $STEP == 'step3' ]]
    then
        # Полезные действия
        if [[ условие ]]
        then
            STEP='step4'
        else
            STEP='step5'
    fi
    


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

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

    function step1 {
        # Действия выполняемые на шаге 1
    }
    
    function step2 {
        # Действия выполняемые на шаге 2
    }
    …
    
    while [[ -z $EXIT ]]
    do
        case $STEP in
        step1)
            step1
            if [[ условие ]]
            then
                STEP='step2'
            else
                EXIT=1
            fi
        ;;
        step2)
            step2
            if [[ условие ]]
            then
                STEP='step3'
            else
                STEP='step1'
            fi
        ;;
        ...
        step10)
            step10
            if [[ условие ]]
            then
                STEP='step6'
            else
                STEP='step9'
            fi
        esac        
    done
    


    В результате получили:
    • Полную изоляцию состояний. Каждое состояние — отдельная функция.
    • Свободу в переходах между состояниями независимо от последовательности их описания в коде.

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

    Бонус: Сохранение состояния между вызовами.

    Поскольку мне была нужна возможность остановить скрипт и продолжить его работу через некоторое время, я написал функцию сохранения состояния:

    function saveState {
        echo -e «STEP='$STEP'\n» > state
    }
    


    Вызов функции добавил в конец скрипта, а в начало загрузку состояния: source state.

    Простой скрипт для экспериментов:

    #!/bin/bash
    
    STEP='step2' # Начальное состояние
    
    function step1 {
        echo 'step 1'
    }
    
    function step2 {
        echo 'step 2'
    }
    
    # Сохранить состояние
    function saveState {
        # Таким образом можно сохранить значение любых переменных
        echo -e "STEP='$STEP'\n" > state;
    }
    
    # Главный цикл
    function main {
       # Сигналом к завершению служит наличие значения у переменной EXIT     
        while [[ -z $EXIT ]]
        do
            case "$STEP" in
            step1)
                step1
                EXIT=1
            ;;
           step2)
               step2
               STEP='step1'
           ;;
           esac
       done
    }
    
    # Если существует файл state прочитать сохраненные в нем значения (на самом деле выполнить)
    if [ -f state ]
    then
        source 'state'
    fi
    main # Главный цикл
    saveState # Перед завершением сохранить состояние.
    


    После первого вызова он выведет:
    step2
    step1

    После второго:
    step1


    Сбросить состояние можно удалив файл state в директории скрипта.

    Несколько советов

    Обратите внимание на то, что bash ОЧЕНЬ чувствителен к пробелам и их отсутствию. Также в нем необычное понимание числовых значений как истина и ложь, 0 — истина (связано с тем, что программы возвращают 0 в случае успешного завершения, и отличное от нуля значение в случае ошибки). Для отладки скрипта полезно запускать его командой bash -x <скрипт>.

    Обновление от 25 мая 2015


    Выйдя в понедельник на роботу и еще немного поразмыслив понял, что код можно еще немного улучшить избавившись от case. Также учтены советы kt97679 об использовании trap, и ZyXI о printf.

    #!/bin/bash
    
    STEP='step2' # Начальное состояние
    
    # Функция состояния 1
    function step1 {
        echo 'step 1'
    }
    
    # Переход из состояния 1
    function step1Next {
        exit
    }
    
    # Функция состояния 2
    function step2 {
        echo 'step 2'
    }
    
    # Переход из состояния 2
    function step2Next {
        STEP='step1'
    }
    
    # Сохранить состояние
    function saveState {
        # Таким образом можно сохранить значение любых переменных, но в последующих строках использовать >>
        printf "STEP=%q\n" "$STEP" > state
    }
    
    # Главный цикл
    function main {
        while true
        do
            $STEP
            $STEP'Next'
       done
    }
    
    function loadState {
        # Если существует файл state прочитать сохраненные в нем значения (на самом деле выполнить)
        if [ -f state ]
        then
            source 'state'
        fi
    }
    
    trap saveState EXIT # Перед завершением сохранять состояние
    loadState # Прочитать сохраненное состояние
    main # Главный цикл
    


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

    Подробнее
    Реклама

    Комментарии 19

      0
      первая ассоциация: троллейбус, но потом вспомнил свой велосипед для деплоя. В баше же есть массивы, в них нельзя хранить состояние автомата?
        +2
        В данном случае, состояние — это некий выполняемый процесс, а вовсе не значения переменных.
        0
        Сохранение состояния можно делать при помощи trap. Если каждый шаг сам определяет следующий шаг, то основной цикл сильно упрощается:
        trap 'echo STEP=$STEP > state' EXIT; while true; do ${STEP}; done
        Код выше оформлен тегами pre, но что-то они не работают.
          0
          Только в простейшем случае для сохранения состояния достаточно сохранить шаг. В реальной ситуации придется сохранять еще и часть других переменных.

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

            Вот пример как работает trap EXIT:

            $ cat 054-trap-test.sh
            #!/bin/bash

            trap 'echo done' EXIT
            [ -z "$1" ] && echo no arg && exit
            echo arg is $1
            $ ./054-trap-test.sh
            no arg
            done
            $ ./054-trap-test.sh 1
            arg is 1
            done
            $

            В случае нормального завершения скрипта можно сохранять первый шаг последовательности. Или пустое значение.
              0
              Попробовал. Да, действительно можно сделать выход в любой точке при помощи exit, а действие которое необходимо выполнить при завершении указать в trap.
          0
          Когда-то делал вот такой велосипед автомат:
          ru.vingrad.com/Konechny-avtomat-s-dmumya-sostoyaniyami-na-bash-id53c397b2ae20154a6f023c30
          С некоторой полезной нагрузкой.
            0
            Конечные автоматы, если мне не изменяет память, используются, например, в компиляторах для парсинга. Также, для разбора регулярных выражений.
              0
              Не изменяет, так и есть. А еще в играх. Но часто ли вам приходится писать синтаксические анализаторы? Я не утверждаю, что это бесполезная теория, как раз наоборот. Данный подход позволяет получить красивый структурированный код там, где при обычном были бы хитросплетения условий в которых даже их автор не смог бы разобраться уже на следующий день. Это одна из реализаций принципа «разделяй и властвуй» в программировании, в данном случае от помог разделить действия и условия переходов от одного к другому.
              0
              Я бы, наверное, сначала попробовал решить подобную задачу при помощи make. Конечных автоматов из коробки там нет, но не исключено, что процесс загрузки данных можно представить в виде DAG, и тогда make очень даже неплох.
                0
                Шаги можно только пропускать. Осознав проблему код был переписан
                if [[ условие ]]
                then
                    STEP='step2'
                else
                    STEP='step3'
                fi
                

                если я правильно понимаю, то если переходить можно только в два состояния, то можно и просто пропускать: при невыполнении условия переходить к следующему шагу, поскольку нумерация шагов условная
                  +1
                  В реальном скрипте шаги не нумерованные а именованные. В сколько состояний можно переходить заранее неизвестно. Пропустить шаг, конечно, можно по условию, но если так делать то по мере совершенствования скрипта и увеличению всевозможных условий переходов получиться паутина из IF-ов. Конечные автоматы как раз позволяют этого избежать. В своем скрипте, в результате такого подхода, я смог спокойно менять условия переходов не запутываясь в условиях, к тому же последовательность «шагов» также не фиксирована.
                  • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Выйдя в понедельник на роботу и еще немного поразмыслив я понял, что код можно еще немного улучшить избавившись от case. Код смотрите в конце статьи.
                    0
                    echo -e "STEP='$STEP'\n" > state;
                    А зачем нужен еще один перевод строки?
                      0
                      В данном случае в нем нет необходимости, но если захотите сохранить еще что-нибудь…
                      Для этого и показал как сделать перевод строки.
                        +1
                        Здесь лучше подойдёт не echo, а printf:

                        printf 'STEP=%q\nOTHER_VAR=%q\n' "$STEP" "$OTHER_VAR"


                        Вы же не хотите долго отлаживать скрипт, если вам внезапно придёт в голову сохранение значения вида "abc\\ndef"?
                          0
                          Спасибо, внес правку в последний вариант скрипта.
                      0
                      А кстати, главный процесс в linux — init — не является ли конечным автоматом?

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

                      Самое читаемое