В этом посте я постараюсь раскрыть тему написания несложного модульного приложения на языке C89 для обработки 24-битных BMP изображений, использующего в своей работе простой скриптовый язык.

Если вы заинтересованы в разработке языков или вам необходимо быстро разобраться как писать приложения, динамически загружающие исполняемый код, хранящийся в разделяемых библиотеках (dll, so), то возможно вам будет интересен данный материал.

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

Задача примерно следующая: разработать инструмент для обработки BMP (как самый простой формат) изображений с 24-битным кодированием цветов с возможностью расширения функционала без перекомпиляции и скриптовым языком для использования инструмента.

Разработка скриптового языка

Разработка любого языка, если конечно вы не совсем начинающий в этом деле, разумеется начинается с продумывания синтаксиса и абстрактного синтаксического дерева этого языка. Так как язык требуется максимально простой, и дерево его разбора будет проще некуда.

Язык должен позволять в заданном порядке вызывать трансформации для обработки изображения, при этом должна быть возможность передавать трансформации параметры при вызове. Например, для поворота картинки это должен быть угол поворота, и т.п. Намечается следующий синтаксис (РБНФ):

script = { transformation ";" } ;
transformation = [ T_IDENTIFIER "." ] T_IDENTIFIER "(" transformation_args ")" ;
transformation_args = [ literal { "," literal } ] ;
literal = T_INTEGER | T_FLOATING | T_STRING | T_IDENTIFIER ;

Здесь я определяю весь скрипт как последовательность трансформаций, каждая из которых должна оканчиваться точкой с запятой, трансформация в свою очередь состоит из опционального идентификатора с точкой, что значит "имя модуля" трансформации, идентификатора самой трансформации и списка аргументов, окружённого круглыми скобками. Список аргументов представляет собой список литералов, идущих через запятую, каждый из которых может быть либо целым числом, либо дробным, либо строкой, либо идентификатором.

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

По описанию синтаксиса сразу очевидно, какие типы узлов АСД нам необходимы: script, transformation, transformation_args и literal. Исходный код их определения ниже:

struct ast_position {
    uint32_t row;
    uint32_t col;
};

enum ast_literal_type {
    L_INTEGER,
    L_FLOATING,
    L_STRING,
    L_IDENTIFIER
};

struct ast_literal {
    enum ast_literal_type type;
    char * value;

    struct ast_position pos;
};

struct ast_transformation_args {
    struct ast_literal argument;
    struct ast_transformation_args * next;
};

struct ast_transformation {
    char * module;
    char * name;

    struct ast_transformation_args * args;

    struct ast_position pos;
};

struct ast_script {
    struct ast_transformation transformation;
    struct ast_script * next;
};

Написание парсера

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

Синтаксис файла грамматики для Bison можно легко найти в интернете и в руководстве, поэтому перейду сразу к описанию нашего языка. Синтаксис секции правил файла очень похож на РБНФ и в некотором роде даже более простой для понимания, поэтому привожу получившийся список правил:

file
    : script YYEOF  { *result = ast_script_reverse($1); }
    ;

script
    : /* empty */               { $$ = NULL; }
    | script transformation ';' { $$ = ast_script_new($2, $1); }
    ;

transformation
    : T_IDENTIFIER '(' transformation_args ')'                  {
        $$ = ast_transformation_create(NULL, $1, ast_transformation_args_reverse($3),
                ast_position_create(@$.first_line, @$.first_column));
    }
    | T_IDENTIFIER '.' T_IDENTIFIER '(' transformation_args ')' {
        $$ = ast_transformation_create($1, $3, ast_transformation_args_reverse($5),
                ast_position_create(@$.first_line, @$.first_column));
    }
    ;

transformation_args
    : /* empty */               { $$ = NULL; }
    | transformation_args_req   { $$ = $1; }
    ;

transformation_args_req
    : literal                               { $$ = ast_transformation_args_new($1, NULL); }
    | transformation_args_req ',' literal   { $$ = ast_transformation_args_new($3, $1); }
    ;

literal
    : T_INTEGER     { $$ = ast_literal_create(L_INTEGER, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_FLOATING    { $$ = ast_literal_create(L_FLOATING, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_STRING      { $$ = ast_literal_create(L_STRING, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_IDENTIFIER  { $$ = ast_literal_create(L_IDENTIFIER, $1, ast_position_create(@$.first_line, @$.first_column)); }
    ;

Здесь кроме определения правил синтаксиса можно видеть также код на Си, заключённый в фигурные скобки. Для тех, кто не знаком с синтаксисом файла грамматики Bison, поясняю: это действия, которые выполняет сгенерированный парсер, когда сворачивает правило. Свёрткой я здесь и далее называю reduce, операцию объединения нескольких определённых в ходе парсинга символов в один нетерминальный символ, при этом все "семантические значения" символов, которые были свёрнуты доступны по именам $n, где n - это номер символа в описании, начиная с 1. Так, в определении правила script, в его второй строке, под номером 1 будет нетерминал script, использованный при рекурсивной свёртке, а под номером 2, соответственно, трансформация. Здесь же стоит обратить внимание на переменную $$, в которую записывается значение, соответствующее текущему сворачиваемому символу. Из кода можно понять, что переменная @$ означает текущее положение в анализируемом тексте, но об этом позже.

Отдельно стоит отметить наличие здесь правила file, единственным назначением которого является запись в переменную и разворачивание списка script. К сожалению, по умолчанию генерируемый Bison парсер ни в каком виде не возвращает семантическое значение последнего свёрнутого правила, поэтому приходится явно записывать его в переменную. Для того, чтобы записывать в переменную что-либо, необходимо сначала эту переменную получить, поэтому здесь мы пользуемся возможностями Bison, и указываем в первой секции файла (предполагается, что читатель ознакомлен с общим синтаксисом файла) директиву %parse-param с указанием определения аргумента функции yyparse, генерируемой Bison. Цельный код получившегося парсера будет представлен ниже.

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

Последнее, на чём здесь хотелось бы заострить внимание, это дополнительное правило transformation_args_req, которое необходимо для корректного парсинга списка, разделённого запятыми. Если его не вводить, не будет возможности построить правило таким образом, чтобы нельзя было оставить "висячую" запятую в начале или в конце списка (или я не знаю как, если есть решение, добро пожаловать в комментарии).

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

%parse-param {struct ast_script ** result} {char ** error}

%{
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#include "ast.h"

int yylex(void);

void yyerror(struct ast_script ** result, char ** error, const char * str);
%}

%code requires {
#include "ast.h"
}

%union {
    struct ast_script * script;
    struct ast_transformation transformation;
    struct ast_transformation_args * transformation_args;
    struct ast_literal literal;
    char * token;
}

%token T_IDENTIFIER T_INTEGER T_FLOATING T_STRING

%type<script> script
%type<transformation> transformation
%type<transformation_args> transformation_args
%type<literal> literal
%type<token> T_IDENTIFIER T_INTEGER T_FLOATING T_STRING

%%

file
    : script YYEOF  { *result = ast_script_reverse($1); }
    ;

script
    : /* empty */               { $$ = NULL; }
    | script transformation ';' { $$ = ast_script_new($2, $1); }
    ;

transformation
    : T_IDENTIFIER '(' transformation_args ')'                  {
        $$ = ast_transformation_create(NULL, $1, ast_transformation_args_reverse($3),
                ast_position_create(@$.first_line, @$.first_column));
    }
    | T_IDENTIFIER '.' T_IDENTIFIER '(' transformation_args ')' {
        $$ = ast_transformation_create($1, $3, ast_transformation_args_reverse($5),
                ast_position_create(@$.first_line, @$.first_column));
    }
    ;

transformation_args
    : /* empty */               { $$ = NULL; }
    | transformation_args_req   { $$ = $1; }
    ;

transformation_args_req
    : literal                               { $$ = ast_transformation_args_new($1, NULL); }
    | transformation_args_req ',' literal   { $$ = ast_transformation_args_new($3, $1); }
    ;

literal
    : T_INTEGER     { $$ = ast_literal_create(L_INTEGER, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_FLOATING    { $$ = ast_literal_create(L_FLOATING, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_STRING      { $$ = ast_literal_create(L_STRING, $1, ast_position_create(@$.first_line, @$.first_column)); }
    | T_IDENTIFIER  { $$ = ast_literal_create(L_IDENTIFIER, $1, ast_position_create(@$.first_line, @$.first_column)); }
    ;

%%

void yyerror(struct ast_script ** result, char ** error, const char * str) {
    free(*error);

    *error = malloc(strlen(str) + 56);
    sprintf(*error, "at %d:%d: %s", yylloc.first_line, yylloc.first_column, str);
}

В секции объявлений (первой секции) можно заметить уже упомянутую ранее директиву %parse-param, в которой определены два аргумента для будущего парсера: указатель на переменную с результатом и указатель на переменную с ошибкой. Ниже идёт код вставляемый в результирующий файл с парсером до определения функции yyparse, в частности включение заголовка с описанием АСД и объявлений функций, необходимых для работы парсера (подробнее в руководстве пользователя). Ниже идёт снова включение заголовочника с АСД, но которое будет включено в сгенерированный Bison заголовочный файл (подробнее в указанном выше руководстве); директива %union, превращающая тип семантического значения правил в сишный union, определение которого следует за директивой; перечисление терминальных символов (токенов), которые могут быть получены парсером на вход и, в заключение, соответствие каждого из символов полю определённого выше юниона, необходимое для корректного сопоставления полей юниона при подстановке в действиях.

В конце файла, в эпилоге, определение функции yyerror, которая вызывается парсером в случае возникновения ошибки. Здесь данная функция форматирует и передаёт выше, в параметр парсера error, полученную ошибку (внимательный читатель может заметить, что для форматирования используется функция sprintf, а не snprintf, однако её использование невозможно за неимением оной в стандарте C89).

Создание лексера

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

%option noyywrap noinput nounput

%{
#include <string.h>

#include "parser.h"
#include "util.h"

extern YYLTYPE yylloc;

int fileno(FILE *stream);

void update_yylloc() {
    size_t i;

    yylloc.first_line = yylloc.last_line;
    yylloc.first_column = yylloc.last_column;

    for (i = 0; i < yyleng; ++i) {
        switch (yytext[i]) {
        case '\n':
            ++yylloc.last_line;
            yylloc.last_column = 1;
            break;

        default:
            ++yylloc.last_column;
        }
    }
}
%}

S [ \b\n\t\f\r]
W [a-zA-Z_]
D [0-9]

I {W}({W}|{D})*

%%

{S}         update_yylloc();
#.*$        update_yylloc();

{I}         update_yylloc(); yylval.token = strdup(yytext); return T_IDENTIFIER;

{D}+                update_yylloc(); yylval.token = strdup(yytext); return T_INTEGER;
{D}*\.{D}+          update_yylloc(); yylval.token = strdup(yytext); return T_FLOATING;
\"(\\.|[^"\\])*\"   update_yylloc(); yylval.token = strdup(yytext); return T_STRING;

.           update_yylloc(); return yytext[0];

Здесь мы видим указание некоторых опций, влияющих на то, как будет генерироваться лексер, подробнее о каждой из них можно узнать в руководстве. Ниже идёт код, необходимый для работы, в частности включение некоторых заголовочных файлов (в том числе файл, генерируемый парсером, для использования имён токенов, определённых в этом файле); объявление глобальной переменной парсера yylloc, использующейся для определения местоположения в файле; объявление функции fileno, потому что у меня не получилось подключить её с помощью заголовочного файла в C89. И определение вспомогательной функции, которая также используется для подсчёта местоположения в файле. Затем идут определения имён, которые могут быть использованы в правилах, в формате имя значение, где значение - это регулярное выражение Flex.

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

Единственное, что, возможно, заслуживает отдельного внимания, это наличие в коде переменной yylval. Эта глобальная переменная генерируется Bison и предназначена для хранения семантического значения текущего символа. В лексере мы задаём её значение, чтобы в парсере иметь возможность сохранить значение токена в АСД.

В качестве фичи, в списке правил можно увидеть синтаксис для комментариев, начинающихся с символа решётки и заканчивающихся переводом строки. Такое определение комментария позволит не только комментировать код, но и использовать shebang для удобного запуска скрипта.

Реализация интерпретатора

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

Я уже упоминал выше, что наше приложение должно иметь возможность работать с внешними библиотеками, поэтому будет удобным ввести для интерпретатора структуру и построить для неё некоторый жизненный цикл:

/* interpreter.h */

#include "ast.h"

struct interpreter_ids;

struct interpreter {
    const char * modules_prefix;

    const struct ast_script * script;
    struct interpreter_ids * identifiers;
};

struct interpreter interpreter_create(const struct ast_script * script);
void interpreter_discard(struct interpreter interpreter);

const char * interpreter_process_script(struct interpreter * interpreter);
const char * interpreter_run(const struct interpreter interpreter, struct image * image);

/* interpreter.c */

struct interpreter_ids {
    const char * module;
    const char * name;

    void * handle;
    void * symbol;

    struct interpreter_ids * next;
};

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

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

Динамическая загрузка символов

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

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

const char * interpreter_load_symbol(struct interpreter * interpreter, const char * module, const char * name) {
    static char * error = NULL;
    void * handle;
    void * symbol;

    if (interpreter_ids_lookup(interpreter->identifiers, module, name)) {
        return NULL;
    }

    if (strset(&error, interpreter_load_module(*interpreter, &handle, module))) {
        return error;
    }

    if (strset(&error, interpreter_do_load_symbol(&symbol, handle, name))) {
        dlclose(handle);
        return error;
    }

    interpreter->identifiers = interpreter_ids_new(module, name, handle, symbol, interpreter->identifiers);
    return NULL;
}

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

const char * interpreter_do_load_module(void ** handle, const char * filename) {
    if (!(*handle = dlopen(filename, RTLD_NOW | RTLD_LOCAL | RTLD_DEEPBIND))) {
        return dlerror();
    }

    return NULL;
}

const char * interpreter_load_module(const struct interpreter interpreter, void ** handle, const char * module) {
    size_t prefix_length, module_length;
    static char * error = NULL;
    char * filename;

    if (!module) {
        return strset(&error, interpreter_do_load_module(handle, NULL));
    }

    prefix_length = strlen(interpreter.modules_prefix);
    module_length = strlen(module);

    filename = malloc(sizeof(char) * (prefix_length + module_length + 4));

    sprintf(filename, "%s%s.so", interpreter.modules_prefix, module);
    if (!strset(&error, interpreter_do_load_module(handle, filename))) {
        free(filename);
        return NULL;
    }

    sprintf(filename, "%s%s", interpreter.modules_prefix, module);
    if (!interpreter_do_load_module(handle, filename)) {
        free(filename);
        return NULL;
    }

    free(filename);
    return error;
}

const char * interpreter_do_load_symbol(void ** symbol, void * handle, const char * name) {
    dlerror();

    *symbol = dlsym(handle, name);
    return dlerror();
}

В первой из приведённых функций используется вызов dlopen для открытия файла и получения хендлера, вторая используется для формирования имени файла модуля, а третья - для загрузки непосредственно символа из файла с помощью функции dlsym. На самом деле, об обеих из этих библиотечных функций достаточно обширно написано в man-страницах dlopen(3) и dlsym(3), что может быть особенно удобно если у вас установлена русская версия man. Однако, для полноты статьи я всё же разверну некоторые ньюансы работы.

Вызов dlopen принимает в качестве первого аргумента имя файла для загрузки и набор флагов во втором аргументе. Если имя файла содержит слеш (/), то файл ищется по абсолютному или относительному пути, относительно текущей директории запуска. Иначе используется следующий порядок разрешения имени:

1. (только в ELF) Если исполняемый файл вызывающей программы содержит метку DT_RPATH, и не содержит метки DT_RUNPATH, то производится поиск в каталогах, описанных в метке DT_RPATH;

2. Если при запуске программы была определена переменная окружения LD_LIBRARY_PATH, содержащая список каталогов через двоеточие, то производится поиск в этих каталогах (по соображениям безопасности эта переменная игнорируется для программ с установленными битами set-user-ID и set-group-ID);

3. (только в ELF) Если исполняемый файл вызывающей программы содержит метку DT_RUNPATH, то производится поиск по каталогам, перечисленным в этой метке;

4. Производится проверка в кэширующем файле /etc/ld.so.cache (обслуживается ldconfig(8)) на предмет наличия записи для filename;

5. Просматриваются каталоги /lib и /usr/lib (именно в таком порядке).

В качестве флагов необходимо передать один из двух следующих:

• RTLD_LAZY - выполнять позднее связывание (lazy binding). Выполняется поиск только тех символов, на которые есть ссылки из кода. Если на символ никогда не ссылаются, то он никогда не будет разрешён (позднее связывание выполняется только при ссылке на функции; ссылки на переменные всегда привязываются сразу при загрузке общего объекта). Начиная с libc 2.1.1, этот флаг заменяется на значение переменной окружения LD_BIND_NOW;

• RTLD_NOW - если указано данное значение или переменная окружения LD_BIND_NOW не пуста, то все неопределённые символы в общем объекте ищутся до возврата из dlopen(). Если этого сделать не удаётся, то возвращается ошибка.

Кроме того, вместе с одним из указанных выше флагов можно указать (используя побитовую операцию ИЛИ) один из следующих флагов:

• RTLD_LOCAL - противоположность RTLD_GLOBAL, используется по умолчанию, если не задано ни одного флага. Символы, определённые в этом общем объекте, не будут доступны при разрешении ссылок для общих объектов, загружаемых далее;

• RTLD_NODELETE (начиная с glibc 2.2) - не выгружать общий объект при dlclose(). В результате статические переменные объекта не инициализируются повторно, если объект загружается снова по dlopen();

• RTLD_NOLOAD (начиная с glibc 2.2) - не загружать общий объект. Это можно использовать для тестирования того, что объект уже загружен (dlopen() возвращает NULL, если нет, или описатель объекта в противном случае). Данный флаг также можно использовать для изменения флагов уже загруженного объекта. Например, общий объект, который был загружен ранее с RTLD_LOCAL, можно открыть повторно с RTLD_NOLOAD | RTLD_GLOBAL;

• RTLD_DEEPBIND (начиная с glibc 2.3.4) - поиск символов будет осуществляться перед поиском в области глобальных символов. Это означает, что самодостаточный объект будет использовать свои собственные символы вместо глобальных символов с тем же именем, содержащихся в объектах, которые уже были загружены.

Кроме того, если в качестве имени файла для dlopen передать NULL, будет получен хендлер для главной программы. При поиске символов с передачей данного хендлера будет производиться поиск сначала среди символов главной программы, затем во всех объектах, загруженных автоматически при запуске программы, затем в символах, загруженных с использованием флага RTLD_GLOBAL. Из ньюансов работы стоит выделить, что поиск производится только среди общих объектов, поэтому для поиска символов исполняемого файла следует скомпилировать его с указанием опции GNU gcc -rdynamic, что соответствует опции GNU ld --export-dynamic.

Здесь стоит оговориться, что всё выше описанное актуально в первую очередь для ОС GNU/Linux и может отличаться для других ОС, в частности использование опций компилятора и линкера.

Все операции по динамической загрузке в Linux предоставляются библиотеками ld.so (ld-linux.so), о подробностях работы которых можно также прочитать в man на странице ld.so(8). В частности, на указанной man-странице представлена информация о влиянии переменных окружения на процесс загрузки.

Запуск скрипта

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

typedef const char * (* transformation_function)(struct image * image, uint32_t argc, const struct value * argv);

Где структура value определена следующим образом:

struct value {
    enum {
        V_INTEGER,
        V_FLOATING,
        V_STRING,
        V_IDENTIFIER
    } type;

    union {
        int64_t integer;
        double floating;
        char * string;
        void * identifier;
    } value;
};

struct value value_from_integer(int64_t value);
struct value value_from_floating(double value);
struct value value_from_string(const char * value);
struct value value_from_identifier(void * value);
void value_discard(struct value value);

bool value_is_integer(struct value value);
bool value_is_floating(struct value value);
bool value_is_string(struct value value);
bool value_is_identifier(struct value value);

int64_t value_to_integer(struct value value);
double value_to_floating(struct value value);
const char * value_to_string(struct value value);
void * value_to_identifier(struct value value);

Кроме самой структуры я также привожу объявления функции API для работы со значениями, чтобы было понятно о чём шла речь выше. Благодаря такому набору функций программисту потребуется меньше времени на написание boilerplate-кода при работе с аргументами трансформаций.

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

И, наконец, код вызова функций, которые мы получили из внешних символов:

args = interpreter_collect_args(interpreter, &argc, transformation);
*((void **) (&transformation_function)) = interpreter_ids_lookup(
		interpreter.identifiers,
		transformation.module,
		transformation.name
)->symbol;

transformation_error = transformation_function(image, argc, args);
interpreter_delete_args(argc, args);

Присваивание на строке 2 можно записать проще в виде простого присваивания переменной значения, однако стандарт ISO C не позволяет прямо преобразовывать тип из указателя на данные, в указатель на функцию, поэтому gcc с флагом -pedantic будет выдавать предупреждение для этой операции. Поэтому, стандартом POSIX от 2003 и 2008 годов предлагается использовать приведённый выше способ вызова функций, полученных из сырых указателей, который не противоречит стандарту C.

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

uint32_t interpreter_count_args(const struct ast_transformation_args * transformation_args) {
    uint32_t count = 0;

    for (; transformation_args; transformation_args = transformation_args->next) {
        ++count;
    }

    return count;
}

struct value interpreter_parse_string_value(const char * value) {
    size_t value_length = strlen(value);
    size_t i, j;

    char * result = malloc(sizeof(char) * (value_length - 1));
    struct value result_value;

    for (i = 1, j = 0; i < value_length - 1; ++i, ++j) {
        if (value[i] == '\\') {
            ++i;
        }

        result[j] = value[i];
    }

    result[j++] = '\0';
    result_value = value_from_string(result);

    free(result);
    return result_value;
}

struct value *
interpreter_collect_args(const struct interpreter interpreter, uint32_t * argc, const struct ast_transformation transformation) {
    struct value * args = malloc(sizeof(struct value) * (*argc = interpreter_count_args(transformation.args)));
    const struct ast_transformation_args * next = transformation.args;
    uint32_t i;

    for (i = 0; next; next = next->next, ++i) {
        switch (next->argument.type) {
        case L_INTEGER:
            args[i].type = V_INTEGER;
            sscanf(next->argument.value, "%ld", &(args[i].value.integer));
            break;

        case L_FLOATING:
            args[i].type = V_FLOATING;
            sscanf(next->argument.value, "%lf", &(args[i].value.floating));
            break;

        case L_STRING:
            args[i] = interpreter_parse_string_value(next->argument.value);
            break;

        case L_IDENTIFIER:
            args[i] = value_from_identifier(interpreter_ids_lookup(
                interpreter.identifiers,
                transformation.module,
                next->argument.value
            )->symbol);
            break;

        default: /* fallback */
            args[i].type = V_IDENTIFIER;
            args[i].value.identifier = NULL;
        }
    }

    return args;
}

Работа с BMP изображениями

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

struct __attribute__((packed)) bmp_header {
    char     bfType[2];
    uint32_t bfSize;
    uint32_t bfReserved;
    uint32_t bfOffBits;

    uint32_t biSize;
    int32_t  biWidth;
    int32_t  biHeight;
    uint16_t biPlanes;
    uint16_t biBitCount;
    uint32_t biCompression;
    uint32_t biSizeImage;
    int32_t  biXPelsPerMeter;
    int32_t  biYPelsPerMeter;
    uint32_t biClrUsed;
    uint32_t biClrImportant;
};

struct bmp_pixel;

struct bmp_image {
    struct bmp_header header;
    struct bmp_pixel * bitmap;
};

Выше приведено определение структуры BMP изображения, использующееся в моей программе. Оно немного не соответствует спецификации, но его достаточно для работы с 24-битным форматом изображений. Первая структура представляет собой заголовок и предназначена для корректного считывания заголовка файла и валидации формата. Затем идёт неопредённая структура bmp_pixel, использующаяся для хранения цветов в формате BGR, использующемся в 24-битных BMP изображениях. Её определение не приведено в заголовочном файле с целью инкапсулировать работу с BMP внутри одного файла при этом оставив возможность передавать структуру bmp_image по значению. Последняя структура представляет собой всё изображение и хранит в себе заголовок и массив пикселей изображения.

Отдельное внимание стоит уделить атрибуту __attribute__((packed)), который заставляет компилятор упаковывать структуру без выравнивания. Иными словами, между полями структуры в памяти гарантировано не будет неиспользуемого пространства. Я намерено использую здесь слово "заставляет", потому что в случае, если аттрибут не поддерживается компилятором, то код не скомпилируется. В противовес аналогичному механизму #pragma pack, который также позволяет влиять на выравнивание структур данных, однако будет проигнорирован, если компилятор не знает что с ним делать. Здесь это играет важную роль, потому что если структура будет неупакована, программа не сможет работать правильно.

Если с чтением структуры из файлов никаких проблем нет, достаточно одного вызова fread, то с чтением содержимого изображения есть некоторые накладки. Кроме того, что изображение может начинаться не сразу после заголовка (из-за наличия палитры и даже при её отсутствии), сами значения цветов идут не друг за другом слева направо и сверху вниз, а слева направо и снизу вверх и с выравниванием строк изображения по четырём байтам, что означает, что в конце каждой строки необходимо разместить width % 4 байт для (Microsoft и тут палки в колёса ставит).

Код чтения и записи BMP я приведу под спойлером, а подробное описание полей структуры может быть получено в интернете, в частности на этом сайте: https://jenyay.net/Programming/Bmp.

const char * bmp_image_read(struct bmp_image * image, FILE * file) {
    int32_t row, rowOffset;

    size_t read_count = fread(&(image->header), sizeof(struct bmp_header), 1, file);
    if (read_count < 1) {
        return "cannot read BMP file";
    }

    /* Check file type signature */
    if (image->header.bfType[0] != 'B' || image->header.bfType[1] != 'M') {
        return "invalid BMP file";
    }

    if ((image->header.biSizeImage         /* Check size if biSizeImage != 0 */
     && (image->header.bfSize != image->header.bfOffBits + image->header.biSizeImage))
     || (image->header.biPlanes != 1)      /* Check biPlanes */
     || (image->header.biBitCount != 24)   /* Check pixel bits count, only 24 is supported */
     || (image->header.biCompression != 0) /* Check biCompression, only 0 is supported */
    ) {
        return "invalid BMP file";
    }

    /* Check file size */
    if (fseek(file, 0L, SEEK_END)) {
        return strerror(errno);
    }

    if (ftell(file) != image->header.bfSize) {
        return strerror(errno);
    }

    /* Go to bitmap */
    if (fseek(file, image->header.bfOffBits, SEEK_SET)) {
        return strerror(errno);
    }

    image->bitmap = malloc(sizeof(struct bmp_pixel) * image->header.biWidth * image->header.biHeight);

    rowOffset = image->header.biWidth % 4;
    for (row = image->header.biHeight - 1; row >= 0; --row) {
        read_count = fread(image->bitmap + row * image->header.biWidth, sizeof(struct bmp_pixel), image->header.biWidth, file);

        if (read_count < image->header.biWidth) {
            free(image->bitmap);
            return "cannot read BMP file";
        }

        if (fseek(file, rowOffset, SEEK_CUR)) {
            free(image->bitmap);
            return strerror(errno);
        }
    }

    return NULL;
}

const char * bmp_image_write(const struct bmp_image image, FILE * file) {
    static uint8_t offsetBuffer[] = { 0, 0, 0 };
    int32_t row, rowOffset;

    if (fwrite(&(image.header), sizeof(struct bmp_header), 1, file) < 1) {
        return "cannot write file";
    }

    rowOffset = image.header.biWidth % 4;
    for (row = image.header.biHeight - 1; row >= 0; --row) {
        if (fwrite(image.bitmap + row * image.header.biWidth,
            sizeof(struct bmp_pixel), image.header.biWidth, file) < image.header.biWidth) {
            return strerror(errno);
        }

        if (fwrite(offsetBuffer, 1, rowOffset, file) < rowOffset) {
            return strerror(errno);
        }
    }

    return NULL;
}

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

struct pixel {
    uint8_t red;
    uint8_t green;
    uint8_t blue;
};

struct image {
    uint32_t width;
    uint32_t height;

    struct pixel * pixels;
};

На этом я завершаю обзор работы с изображениями и подхожу к завершению.

Обработка ошибок

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

Определение местоположения синтаксических конструкций в файле

Другой аспект вывода сообщений об ошибках кроется в парсере. Для пользователя программы может быть очень удобно, если программа подскажет, где именно в файле произошла ошибка. Для этого необходимо на этапе лексического анализа отслеживать текущую позицию в файле, а на этапе синтаксического разбора - сохранять эту информацию в узлах дерева. В парсере, генерируемом Bison используется глобальная переменная yylloc, которая хранит в себе информацию о текущем положении парсера в файле и доступ к которой может быть получен внутри действий парсера с помощью переменных $@, для текущего правила, и @n - для сворачиваемых символов. Тип этой переменной определяется таким образом:

typedef struct YYLTYPE YYLTYPE;
struct YYLTYPE
{
  int first_line;
  int first_column;
  int last_line;
  int last_column;
};

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

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

struct ast_position {
    uint32_t row;
    uint32_t col;
};

struct ast_literal {
    enum ast_literal_type type;
    char * value;

    struct ast_position pos;
};

struct ast_transformation {
    char * module;
    char * name;

    struct ast_transformation_args * args;

    struct ast_position pos;
};

Для получения местоположения того или иного символа из действий парсера, используются переменные @$ и @n (по аналогии с $$ и $n для семантических значений). Для того, чтобы нам, как разработчикам парсера, было удобнее использовать эти значения, парсер, генерируемый Bison, автоматически подсчитывает позицию для всех нетерминальных символов, исходя из позиции символов, из которых они состоят (начало конструкции устанавливается равным началу первого символа, а конец - концу последнего). Сохраняя эту информацию, мы получаем возможность выводить ошибки в более приятном для пользователя формате, добавляя в сообщения об ошибках местоположение синтаксической конструкции, которая так или иначе была связана с возникшей ошибкой.

Бонус: пример функции модуля

В качестве дополнения, приведу код интересной функции модуля, которая принимает идентификатор в качестве аргумента:

typedef struct pixel (* blur_function)(uint32_t x, uint32_t y, const struct image image);

const char * do_(struct image * image, uint32_t argc, struct value * args) {
    blur_function map_function;

    if (argc < 1 || !value_is_identifier(args[0])) {
        return "blur type (blur, dilate or erode) is required as first argument";
    }

    *((void **) &map_function) = value_to_identifier(args[0]);

    if (map_function != blur && map_function != dilate && map_function != erode) {
        return "wrong blur type, only blur, dilate or erode are allowed";
    }

    do_blur(*image, map_function);
    return NULL;
}

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

Стоит отметить, что если попробовать слинковать функцию выше в составе разделяемой библиотеки, gcc может выкинуть ошибку и любезно попросить перекомпилировать объектный файл с флагом -fPIC, который заставляет gcc генерировать позиционно-независимый код (публикация на Хабре на тему).

Пример работы

Подадим на вход получившемуся приложению (ссылка на репозиторий ниже) следующий скрипт:

#!./image-transformer -p./modules/

# test script

print_ansi("\"\"");
echo();

rotate.rotate();
print_ansi();
echo();

rotate.rotate("-90");
print_ansi();
echo();

rotate.rotate(45);
print_ansi();
echo();

blur.do_(dilate);
print_ansi();

die();

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

#include <stdint.h>
#include <stdio.h>

#include "image.h"
#include "value.h"
#include "util.h"

const char * echo(const struct image * image, uint32_t argc, const struct value * args) {
    puts(argc > 0 && value_is_string(args[0]) ? value_to_string(args[0]) : "");
    return NULL;
}

const char * die(const struct image * image, uint32_t argc, const struct value * args) {
    static char * message;

    return argc > 0 && value_is_string(args[0])
        ? strset(&message, value_to_string(args[0]))
        : "suicide";
}

void do_print_ansi(const struct image image, const char * pixel_string) {
    uint32_t x, y, i;

    for (y = 0, i = 0; y < image.height; ++y) {
        for (x = 0; x < image.width; ++x, ++i) {
            printf("\x1B[48;2;%d;%d;%dm%s\x1B[0m",
                image.pixels[i].red,
                image.pixels[i].green,
                image.pixels[i].blue,
                pixel_string);
        }

        putchar('\n');
    }
}

const char * print_ansi(const struct image * image, uint32_t argc, const struct value * args) {
    do_print_ansi(*image, argc > 0 && value_is_string(args[0])
            ? value_to_string(args[0]) : "  ");

    return NULL;
}

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

В результате работы скрипта выше выводится следующее (в зависимости от исходной картинки):

Заключение

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

Полный исходный код рассмотренного приложения можно найти тут.

Ссылки

• Руководство по GNU Flex

• Руководство по GNU Bison

• Статья по формату BMP