За время прошлого семестра в универе я прошёл курс «Инструменты и компиляторы на основе синтаксиса». В рамках курса мы создавали сканер, парсер, компилятор и прочие инструменты для языка Plo. Писали мы их на Python, но тогда меня серьёзно заинтересовал Rust.
В итоге я решил заняться очередным хобби-проектом, и на сей раз создать парсер JSON на Rust. Мне хотелось проверить полученные на курсе навыки и, наконец-то, реализовать проект на этом языке, что я откладывал уже не один год.
План
На мой взгляд, лучший способ освоения программирования — это его практическое применение. Таков и был мой план. Я отыскал спецификацию JSON и начал читать. В ней есть интересные схемы, помогающие представить структуру документа JSON.
Создать «парсер» можно разными способами. Я мог проверить, просканировать, токенизировать и, наконец, спарсить JSON. Но мне хотелось всё упростить, поэтому я проигнорировал все этапы, сосредоточившись конкретно на «парсинге» содержимого JSON из сырого файла/строки в перечисление Rust, представляющее его структуру.
Есть инструменты, способные на основе заданной грамматики автоматически генерировать нисходящие или восходящие парсеры, но мою реализацию можно считать рукописным решением. Это гибкий метод, который не привязан к строгим правилам или деталям реализации, позволяя легко вносить изменения.
Реализация
▍ Как представить JSON в Rust?
Чтобы сохранить спарсенные данные JSON, мне нужно как-то представить их в Rust.
Я начал с создания обобщённого перечисления
JSONValue, которое будет выражать структуру документа JSON в виде «дерева». Каждый «узел» в этом дереве может представлять один из типов — строку, число, объект, массив, логическое значение или нуль. В корне при этом находится узел, являющийся самим объектом JSON.Вот это перечисление:
#[derive(Debug, Clone, PartialEq)]
enum JSONValue {
Null,
True,
False,
Number(f64),
String(String),
Array(Vec<JSONValue>),
Object(HashMap<String, JSONValue>),
}▍ Что насчёт ошибок?
Здесь важно учитывать, что парсинг — это процесс, который может провалиться, например, из-за ошибок в исходном тексте. Так что анализатор должен уметь их обработать. Для этого я решил возвращать из парсера тип
Result. В результате успешного парсинга будет возвращаться значение JSON, а при провале — ошибка. enum JSONParseError {
Error(usize),
NotFound,
UnexpectedChar(usize),
MissingClosing(usize),
}Это перечисление я использовал для выражения различных типов ошибок, которые могут случиться в процессе парсинга. Заметьте, что с некоторыми из них связано значение
usize. Оно представляет оставшуюся длину входящей строки на момент ошибки.Это позволяет понять, какую часть строки удалось считать, и вывести более точное сообщение об ошибке. Ошибка
NotFound, можно сказать, является внутренней. С её помощью я указываю, что парсер не смог найти во входящей строке ожидаемый элемент.▍ «Значение» JSON
Согласно спецификации JSON, всё начинается как элемент и представляет значение, окружённое пустым пространством. Это значение может быть одного из следующих типов:
- object,
- array,
- string,
- number,
- «true»,
- «false»,
- «null».
▍ Простые значения
Я решил начать с простых значений и затем уже переходить к более сложным. Первым в этом списке стало
null, и вот простая функция для его обработки:fn null(src: &str) -> Result<(&str, JSONValue), JSONParseError> {
match src.strip_prefix("null") {
Some(rest) => Ok((rest, JSONValue::Null)),
None => Err(JSONParseError::NotFound),
}
}В этом коде мы просто проверяем, начинается ли входящая строка с
“null”. Если да, возвращаем оставшуюся строку и JSONValue::Null. В противном случае возвращаем ошибку, сообщая, что значение не найдено.Аналогичным образом я поступил со значениями
true и false — поэтому достаточно просто заменить в коде "null" на "true" или "false".▍ Строки
Кажется, что парсить строки в формат JSON легко — нужно лишь найти открывающие/закрывающие кавычки и вернуть содержащуюся между ними строку. По факту же здесь есть сложности. Строки могут содержать экранирующие последовательности вроде
\", \\, \n и прочих. Так что для корректного парсинга строк необходима правильная обработка.Код для парсинга строки начинается с поиска открывающих кавычек
“. После их обнаружения он считывает последующие символы, пока не находит закрывающую часть. Но закрывающая кавычка может оказаться экранирована, и на этот случай я реализовал флаг, позволяющий проверить, являлся ли последний символ экранирующим \. Если да, то следующий символ обрабатывается иначе, чтобы парсинг не прекратился преждевременно.Вот часть кода, отвечающая за парсинг строк:
fn string(mut src: &str) -> Result<(&str, JSONValue), JSONParseError> {
// Следим, чтобы считывание начиналось с кавычек
match src.strip_prefix("\"") {
Some(rest) => src = rest,
None => return Err(JSONParseError::NotFound),
};
let mut result: String = "".to_string();
let mut escaping = false; // Флаг
let mut chars = src.chars(); // Итератор
loop {
let c = match chars.next() {
Some(c) => c,
None => return Err(
JSONParseError::MissingClosing(src.len())
),
};
// Если встречаем \, делаем экранирование
if c == '\\' && !escaping {
escaping = true;
}
// Закрывающая кавычка без экранирования
else if c == '"' && !escaping {
break;
} else if escaping {
// Специальные экранирующие последовательности
match c {
// Кавычки
'"' => result.push('"'),
... // Другие экранирующие последовательности
_ => {
// Невозможно экранировать
return Err(JSONParseError::UnexpectedChar(
chars.count()
));
}
}
escaping = false;
} else {
result.push(c);
}
}
Ok((chars.as_str(), JSONValue::String(result)))
}▍ Числа
В обычных языках программирования зачастую есть несколько типов данных для выражения чисел, такие как целые числа разного размера, числа с плавающей запятой и прочие. При этом в JSON всего один тип числа — произвольное значение, которое может быть целым числом, числом с плавающей запятой, либо числом в экспоненциальной записи.
В моём парсере все числа представляются как
f64 (с плавающей запятой). Это простой способ выражения чисел в Rust, но он не поддерживает ту степень произвольной точности, которую даёт нам JSON. С этим ограничением своего парсера я пока планирую смириться.
Число в JSON состоит из нескольких частей: целая часть, дробная и степень. Парсер считывает эти части и выстраивает для них соответствующее значение
f64. И здесь также нужно учесть ряд пограничных случаев, таких как ведущие нули, отрицательные числа и прочее.Не буду углубляться в реализацию, но я написал функции для парсинга каждой из этих трёх частей и совместил их для обработки числа целиком.
fn number(mut src: &str) -> Result<(&str, JSONValue), JSONParseError> {
let mut result;
let negative;
match integer(src) {
Ok((rest, num)) => {
result = num.abs() as f64;
negative = num.is_negative();
src = rest;
}
Err(e) => return Err(e),
};
match fraction(src) {
Ok((rest, frac)) => {
result += frac;
src = rest;
}
Err(JSONParseError::NotFound) => {}
Err(e) => return Err(e),
}
match exponent(src) {
Ok((rest, exponent)) => {
src = rest;
let multipier = 10_f64.powf(exponent as f64);
result *= multipier;
}
Err(JSONParseError::NotFound) => {}
Err(e) => return Err(e),
}
if negative {
result *= -1.0;
}
Ok((src, JSONValue::Number(result)))
}▍ Списки и объекты
Массивы и объекты — это коллекции значений. Первые — это упорядоченные списки значений, а вторые — неупорядоченные коллекции пар ключ-значение. Парсеру нужно обрабатывать оба этих типа.
С позиции синтаксиса массивы и списки являются коллекциями, в которых значения разделяются запятыми. И для каждой такой коллекции парсер должен уметь обработать 3 случая:
- элементы отсутствуют,
- есть один элемент,
- есть множество элементов.
Отсутствие элементов обрабатывать легко — просто находим пару скобок, между которыми пусто.
В двух других случаях можно запустить цикл, который будет поочерёдно считывать элементы, пока они сопровождаются запятыми. Это простой способ парсинга подобных коллекций. Причём нельзя пропускать элементы, не являющиеся валидными значениями JSON, что требует подобающей обработки ошибок.
Вот код для двух последних случаев:
fn elements(mut src: &str) -> Result<(&str, Vec<JSONValue>), JSONParseError> {
let mut values = vec![];
loop {
match element(src) {
Ok((rest, v)) => {
src = rest;
values.push(v);
}
Err(e) => return Err(e),
}
// Если далее идёт запятая, считываем очередной символ src, в противном случае завершаем цикл
if src.chars().next() == Some(',') {
src = &src[1..];
} else {
break;
}
}
Ok((src, values))
}Опять же, это не полная реализация, но она позволяет понять, как парсер обрабатывает такие коллекции.
▍ Объединение компонентов парсера
Закончив с написанием всех компонентов, мы подобрались к самой основе парсера. Если говорить о JSON в API, то он зачастую применяется для передачи объектов. Однако корневой объект JSON фактически может быть любого типа из перечисленных выше — строкой, числом, объектом, массивом, логикой или нулём.
Поэтому парсинг начинается с проверки, к какому из этих типов относится корень JSON, после чего вызывается подходящая функция. Всё это происходит в определённом порядке в соответствии со спецификацией JSON.
// Окружающие пробелы уже удалены
fn value(src: &str) -> Result<(&str, JSONValue), JSONParseError> {
match object(src) {
Ok(res) => return Ok(res),
Err(JSONParseError::NotFound) => {} // Если NotFound, возвращаем Ок
Err(e) => return Err(e),
}
match array(src) {
Ok(res) => return Ok(res),
Err(JSONParseError::NotFound) => {} // Если NotFound, возвращаем Ок
Err(e) => return Err(e), // Любую другую ошибку передаём выше
}
match string(src) {
Ok(res) => return Ok(res),
Err(JSONParseError::NotFound) => {} // Если NotFound, возвращаем Ок
Err(e) => return Err(e), // Любую другую ошибку передаём выше
}
match number(src) {
Ok(res) => return Ok(res),
Err(JSONParseError::NotFound) => {} // Если NotFound, возвращаем Ок
Err(e) => return Err(e), // Любую другую ошибку передаём выше
}
match bool(src) {
Ok(res) => return Ok(res),
Err(JSONParseError::NotFound) => {} // Если NotFound, возвращаем Ок
Err(e) => return Err(e), // Любую другую ошибку передаём выше
};
match null(src) {
Ok(res) => return Ok(res),
Err(JSONParseError::NotFound) => {} // Если NotFound, возвращаем Ок
Err(e) => return Err(e), // Любую другую ошибку передаём выше
};
Err(JSONParseError::NotFound)
}Здесь у меня элементарный поток выполнения — я просто поочерёдно пробую спарсить корневое значение JSON как имеющее тот или иной тип. В случае успеха возвращаю результат. Если же ни один из типов не приводит к успеху, возвращаю ошибку.
На этом мой анализатор синтаксиса готов. Он состоит из всего 500 строк кода и может парсить строки JSON в перечисление
JSONValue. Вот gist этой реализации.Тестирование и производительность
Чтобы убедиться в правильной работе парсера, я написал несколько модульных текстов. По этой ссылке есть популярный набор бенчмарков для парсеров JSON. В качестве файлов для тестов я использовал
canada.json и twitter.json. Их парсинг прошёл успешно, и результаты меня порадовали. Код тестов я в gist включать не стал, так как тогда программа выходит за 500 строк.Для проверки производительности я нашёл в репозитории yyjson хорошие отчёты с графиками, детально отражающие производительность считывания среди различных парсеров JSON. С
canada.json все парсеры справляются со скоростью в пределах 1 ГБ/с. Я свой анализатор не оптимизировал, поэтому без особых ожиданий просто для сравнения решил прогнать его через очень грубый бенчмарк.let big_file = std::fs::read_to_string("canada.json").expect("Could not read file");
// Сколько байтов данных?
let num_bytes = big_file.len();
let mul = 1000;
let bytes_to_parse = num_bytes * mul;
let start_time = std::time::Instant::now();
for _ in 0..mul {
let _ = parse(big_file.as_str());
}
let end_time = std::time::Instant::now();
let bps = bytes_to_parse as f64 / (end_time - start_time).as_secs_f64();
let mbs = (bytes_to_parse as f64) / (1_000_000.0);
let mbps = mbs / (end_time - start_time).as_secs_f64();
let gbs = (bytes_to_parse as f64) / (1_000_000_000.0);
let gbps = gbs / (end_time - start_time).as_secs_f64();
println!("Parsing speed: {:.2} Bytes/s", bps);
println!("Parsing speed: {:.2} MB/s", mbps);
println!("Parsing speed: {:.2} GB/s", gbps);Я скормил парсеру
canada.json и сравнил результат с другими парсерами. Что получилось:Parsing speed: 52014622.29 Bytes/s
Parsing speed: 52.01 MB/s
Parsing speed: 0.05 GB/Скорость несерьёзная. Но её всё же достаточно, чтобы спарсить большой файл JSON в пределах секунды. Если же учесть, что оптимизаций я никаких не делал, то такие результаты меня вполне устраивают. Возможно, в будущем я займусь доработкой парсера для его ускорения.
▍ Красивые ошибки
Наконец, я решил сделать сообщения об ошибках более читаемыми. На тот момент — это были простые
enum, с которыми связано число. Мне же хотелось, чтобы они были более удобными для восприятия, подобно ошибкам в Python. В частности, я хотел знать, где конкретно во входящей строке произошла ошибка, а также выводить окружающий контекст, чтобы упростить отладку.В итоге, проделав некоторые манипуляции, я смог использовать связанные с ошибками значения
usize, чтобы выводить сообщение с окружающим контекстом. Такой механизм сильно упростил исправление проблем парсера. Чтобы это реализовать, я использовал размер оставшейся части исходного файла на момент ошибки для вычисления номера строки и столбца, где эта ошибка произошла. Далее на основе полученной информации я выводил сообщение с окружающим контекстом. Плюсом я также добавил стрелку, указывающую на место ошибки.
Error: UnexpectedChar(76)
----------------------------------------------------------------
"age": 30,
"cars": ["Ford \e This has an invalid escape", "BMW", "Fiat"],
^
|
|
Error: Unexpected Character on Line 4 Char 19Получился красивый способ обозначения ошибки, и он помог мне с отладкой парсера в ходе тестирования.
Вопрос
Я понимаю основную часть процессов в парсере, но меня сильно озадачивает один момент. Когда я выполняю парсинг
twitter.json через cargo run --release, парсер работает со скоростью около 60 МБ/с.Если же я делаю это через
sudo cargo run --release, он достигает уже 100+МБ/с. Понятия не имею, в чём причина. Использование sudo значительно ускоряет скорость парсера. Если у вас есть тому объяснение, будьте добры, поделитесь в комментариях.▍ Итог
Это был интересный проект, в ходе которого я многое узнал о Rust, парсерах и JSON. Я также получил прекрасный опыт написания парсера с нуля. Причём результаты меня определённо порадовали, как и то, что я занялся-таки изучением Rust.
Итоговый размер кода составил около 800 строк — со всеми тестами, бенчмарком и форматированием сообщений об ошибках. Ознакомиться с ним можно на GitHub.
Что касается использованной спецификации JSON, то она доступна на официальном сайте.
Telegram-канал со скидками, розыгрышами призов и новостями IT 💻
