DSEL for incremental parsing, OOP style

[thedeemon]

В текущем проекте на haXe нужно читать из сети AVI файл и по мере его загрузки разбирать и декодировать. Для начала для простых тестовых файлов был сделан простой разбор в лоб, но быстро стало понятно, что такой подход не масштабируется - объем кода быстро растет, а логика по нему сильно размазывается. Захотелось декларативного описания разбираемого формата, вспомнил про парсер-канабинакомбинаторы. Но они работают там, где весь необходимый инпут уже есть, для загружаемого постепенно нужно их готовить по-другому. Посмотрел было на проект reactive parsing (RxParsers), но там под тоннами бойлерплейта найти здравую мысль оказалось очень сложно, а автор честно признался, что парсер-комбинаторы видел впервые и как работает его проект сам толком не понимает. В общем, сделал я свое решение, простое и удобное.

В haXe нельзя определять свои операторы, но хотя бы есть extension methods и ФВП. Поэтому синтаксического шума получилось чуть больше, чем хотелось бы, но вполне терпимо. Выглядит это сейчас так:

var frame_chunk = seq([Const("00dc").or(Const("00db")), Var("frame_size"), Blob("frame_size".pad(), add_frame)]);
var other_chunk = seq([SomeInt, Var("chunk_size"), Blob("chunk_size".pad())]);			
var list_rec = seq([Const("LIST"), Var("rec_size"), Const("rec "), frame_chunk.or(other_chunk).until("rec_size".minus(4))]);
var sub_chunk = frame_chunk.or(list_rec).or(other_chunk);
var list_movi = seq([Const("LIST"), Var("movi_size"), Const("movi"), sub_chunk.until("movi_size".minus(4))]);

(это добрая половина всего парсера)
В основе лежат все те же парсер-комбинаторы, но устроенные иначе. В классическом подходе парсер - это функция, принимающая поток неразобранных символов/лексем/других элементов и возвращающая один из двух вариантов: либо признак успешного разбора, вместе с разобранным значением и остатком входного потока, либо признак неудачи. Комбинаторы соединяют парсеры друг с другом, образуя новые парсеры. Основные комбинаторы запускают парсер-аргумент и в зависимости от возвращенного значения поступают тем или иным образом (например, запускают или не запускают другой парсер). Получается, что каждый раз, когда некий парсер работает, у него есть два продолжения - функции вида Success(result, rest_input) -> ⊥ и Fail -> ⊥. В зависимости от успехов текущего парсера управление будет передано одному из этих продолжений. А значит, мы можем представить каждый парсер в виде объекта, состоящего из вызываемой функции parse и двух полей - продолжений success и fail. Тогда работа комбинаторов состоит в том, чтобы связать парсеры-аргументы путем задания им правильных значений для этих двух продолжений. Например, комбинатор "последовательность" строит цепочку из парсеров-аргументов так:

class AndParser extends Parser
{
  var parsers : Array<Parser>;
	
  public function new(parsers_array : Array<Parser>)
  {
    super();
    parsers = parsers_array;
    for (p in parsers)
      p.fail = on_fail;
    for (i in 0...parsers.length - 1)
      parsers[i].success = parsers[i + 1].parse;
    parsers[parsers.length - 1].success = on_success;
  }	
	
  override public function parse(pos : Int) : Void
  {
    parsers[0].parse(pos);
  }
}

Где on_success и on_fail определены в Parser и просто вызывают продолжения success и fail, которые определены как

public var success : Int -> Void;
public var fail : Void -> Void;	

Непрямой вызов нужен в силу мутабельности этих полей: построение графа идет снизу-вверх, и значения success и fail парсера определяются сверху (внешним парсером) уже после вызова конструктора текущего. Инпут не передается явно, т.к. входной поток в данной задаче один, все парсеры знают откуда читать. Разобранное значение не возвращается наверх, вместо этого для интересующей нас части данных (в моем случае - содержимого чанков с кадрами видеопотока) вызываются колбэки (в приведенном примере это add_frame).

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

С учетом исходной задачи были сделаны три элементарных парсера: 32-битная константа, 32-битная переменная (значение, используемое в других парсерах) и блоб - последовательность байтов определенной длины, и три комбинатора: последовательность, альтернатива и ограниченное размером повторение. Последний комбинатор применяет парсер-аргумент в цикле до тех пор, пока тот не съест заданное число байт. В приведенном выше примере составного парсера Const("LIST") создает парсер, принимающий только заданную константу и отвергающий все остальное, Var("chunk_size") создает парсер, читающий 4 байта и запоминающий их в переменной с заданным именем, Blob создает парсер, читающий кусок данных заданного размера и передающий его в заданный обработчик, seq задает последовательность, метод-расширение .or задает альтернативу, а .until задает повтор, ограниченный размером.

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

function Blob(?size_thunk : Void->Int, ?data_handler : ByteArray -> Void, ?const_size : Int):Parser
{
  if (size_thunk == null) size_thunk = function():Int { return const_size; };
  if (data_handler == null) return new JunkBlobParser(size_thunk);
  return new BlobParser(size_thunk, data_handler);
}	

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

Соответственно, выражения вроде "frame_size".pad() и "rec_size".minus(4), реализованные через extension methods для строк, возвращают функции:

public static function pad(varname : String) : Void -> Int 
{
  return function():Int { return (Reflect.field(Parser.mem, varname) + 1) & (~1); };
}

public static function minus(varname : String, ?x : Int, ?expr : Void -> Int) : Void -> Int
{
  if (x != null)
    return function():Int { return Std.int(Reflect.field(Parser.mem, varname) - x); };
  if (expr != null)
    return function():Int { return Std.int(Reflect.field(Parser.mem, varname) - expr()); };
  return function():Int { trace("bad minus result"); return 0; };
}

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