[Перевод] Пишем простую библиотеку JSON с нуля: экскурс в современный C++
Глазами начинающего С++ программиста оцениваем удобство современных возможностей языка на примере реализации программы для лексического разбора и парсинга данных JSON.
В современном С++ есть много крутых возможностей. К примеру, семантика перемещения подразумевает дешевую передачу структур в функциях, а std::shared_ptr избавляет от необходимости вручную управлять памятью, то есть никаких больше new/delete! (Но как бы я ни старался понять std::unique_ptr, до меня никак не доходит).
Синтаксис также был несколько улучшен за счет появления auto и деструктуризации кортежей.
С целью протестировать С++ в нынешнем обличии, я решил реализовать небольшой, но значительный проект, работающий с очень динамическими данными. На ум сразу приходят два варианта — парсеры JSON или интерпретаторы Lisp.
В этой статье разбирается написание простого модуля JSON с нуля при помощи одной только стандартной библиотеки. Исходный код готовой программы доступен на GitHub.
В качестве самого большого упрощения мы вместо всех чисел JSON допустим использование только целых.
Сразу оговорюсь — я далеко не эксперт в программировании на С++, поэтому прошу не судить строго.
API
Две большие части API будут отвечать за лексинг (преобразование строки в массив токенов) и парсинг (преобразование массива токенов в объектное дерево JSON). В более грамотной реализации лексер бы получал поток символов, а не строку. Тем не менее вариант со строкой проще, поэтому использовать мы будем его.
Обе эти функции могут провалиться, поэтому в обоих случаях мы будем возвращать кортеж со строкой, содержащей, возможно, пустое сообщение об ошибке.
Заголовок определим в ./include/json.hpp.
#ifndef JSON_H
#define JSON_H
#include
#include
#include
namespace json {
std::tuple, std::string> lex(std::string);
std::tuple parse(std::vector, int index = 0);
} // namespace json
#endif
Токен, возвращенный lex, должен будет содержать строковое значение, местоположение (смещение) в оригинальном источнике, указатель на весь источник (для отладки), а также тип. Сам тип токена будет представлен перечислением из String, Number, Syntax (двоеточие, скобки и т.д.), Boolean либо Null.
...
#include
#include
namespace json {
enum class JSONTokenType { String, Number, Syntax, Boolean, Null };
struct JSONToken {
std::string value;
JSONTokenType type;
int location;
std::shared_ptr full_source;
};
...
} // namespace json
...
Это единственное место во всем коде, где мы будем передавать указатель. Использование std::shared_ptr избавляет нас от ручного управления памятью. Никаких new или delete.
Идем далее. JSONValue представляет структуру, содержащую опциональные поля String, Number, Boolean, Array и Object, с указанием типа для их различения.
...
#include
Благодаря std::optional мы можем избежать использования указателей для описания этих полей. Я заглянул в std::variant, но его API показался мне слишком сложным.
В завершении добавляем еще две функции: высокоуровневую parse, которая объединяет работу лексера и парсера, и deparse для вывода JSONValue в виде строки JSON.
...
std::tuple parse(std::vector, int index = 0);
std::tuple parse(std::string);
std::string deparse(JSONValue, std::string whitespace = "");
} // namespace json
...
Теперь можно приступать к реализации.
Лексинг
Сначала займемся лексингом: преобразуем строку JSON в массив токенов: Number, String, ключевого слова Null, ключевого слова Boolean либо Syntax в виде запятой либо двоеточия.
Основной цикл лексера пропускает пустое пространство и вызывает вспомогательные функции для каждого вида токенов. При обнаружении токена мы его откладываем и переходим в конец этого токена (некоторые токены, например, : представляют один символ, а некоторые, например, "my great string” состоят из нескольких).
Каждый найденный токен получает указатель на исходник JSON для использования в сообщениях об ошибке на случай сбоя парсинга. Опять же, в данной реализации это будет единственный раз, когда мы явно передаем указатели. Никакого ручного управления мы здесь не осуществляем, потому что будем использовать std::shared_ptr.
#include "json.hpp"
namespace json {
std::tuple, std::string> lex(std::string raw_json) {
std::vector tokens;
// Все токены будут нести указатели на исходный JSON для дальнейшей отладки
auto original_copy = std::make_shared(raw_json);
auto generic_lexers = {lex_syntax, lex_string, lex_number, lex_null, lex_true, lex_false};
for (int i = 0; i < raw_json.length(); i++) {
// Пропускаем пробел
if (auto new_index = lex_whitespace(raw_json, i); i != new_index) {
i = new_index - 1;
continue;
}
auto found = false;
for (auto lexer : generic_lexers) {
if (auto [token, new_index, error] = lexer(raw_json, i); i != new_index) {
// В случае ошибки лексинга делаем преждевременный возврат
if (error.length()) {
return {{}, error};
}
// Сохраняем ссылку на источник
token.full_source = original_copy;
tokens.push_back(token);
i = new_index - 1;
found = true;
break;
}
}
if (found) {
continue;
}
return {{}, format_error("Unable to lex", raw_json, i)};
}
return {tokens, ""};
}
} // namespace json
Здесь вы заметите две интересные детали — это синтаксис литералов в кортеже и то, насколько просто типизировать значение, содержащее массив указателей функции, при помощи автоматических (generic_lexers).
format_error
Поскольку мы ссылаемся на format_error, ее нужно определить. Она должна получать префикс сообщения, полную строку JSON и смещение индекса, куда указывает ошибка.
Внутри этой функции мы будем перебирать строку, пока не найдем всю строчку, содержащую это смещение индекса. Найденную строчку мы будем выводить вместе с указателем на символ, вызывающий ошибку.
...
#include
namespace json {
std::string format_error(std::string base, std::string source, int index) {
std::ostringstream s;
int counter = 0;
int line = 1;
int column = 0;
std::string lastline = "";
std::string whitespace = "";
for (auto c : source) {
if (counter == index) {
break;
}
if (c == '\n') {
line++;
column = 0;
lastline = "";
whitespace = "";
} else if (c == '\t') {
column++;
lastline += " ";
whitespace += " ";
} else {
column++;
lastline += c;
whitespace += " ";
}
counter++;
}
// Продолжаем наращивать lastline для отладки
while (counter < source.size()) {
auto c = source[counter];
if (c == '\n') {
break;
}
lastline += c;
counter++;
}
s << base << " at line " << line << ", column " << column << std::endl;
s << lastline << std::endl;
s << whitespace << "^";
return s.str();
}
...
API printf несколько напрягает, а Clang 12 (последняя версия Clang в последнем дистрибутиве Fedora) не поддерживает std::format. Поэтому для форматирования строк мы просто используем std::sstream.
Ну да ладно. Вернемся в лексингу. На очереди: whitespace.
lex_whitespace
Задача этой функции — пропускать пустые пространства. Хорошо, что в помощь у нас есть std::isspace.
int lex_whitespace(std::string raw_json, int index) {
while (std::isspace(raw_json[index])) {
if (index == raw_json.length()) {
break;
}
index++;
}
return index;
}
Все очень просто!
lex_syntax
Все универсальные лексеры действуют по одному шаблону — возвращают либо валидный токен и индекс его окончания, либо строку ошибки.
Поскольку все синтаксические элементы в JSON (,, :, {, }, [ и ]) являются одиночными символами, нам не требуется писать вспомогательную функцию «длиннейшей подстроки». Мы просто проверяем, является ли текущий символ одним из этих символов и в утвердительном случае возвращаем синтаксический токен.
std::tuple lex_syntax(std::string raw_json, int index) {
JSONToken token{"", JSONTokenType::Syntax, index};
std::string value = "";
auto c = raw_json[index];
if (c == '[' || c == ']' || c == '{' || c == '}' || c == ':' || c == ',') {
token.value += c;
index++;
}
return {token, index, ""};
} lex_string
Эта функция управляет состоянием, поэтому реализуется уже несколько сложнее. Нам нужно проверить, является ли текущий символ двойной открывающей кавычкой, после чего перебрать все символы вплоть до закрывающей.
Здесь есть вероятность достичь EOF, так что этот случай нужно обработать. При этом обработка вложенных кавычек остается в качестве упражнения вам, дорогой читатель :)
std::tuple lex_string(std::string raw_json,
int original_index) {
int index = original_index;
JSONToken token{"", JSONTokenType::String, index};
std::string value = "";
auto c = raw_json[index];
if (c != '"') {
return {token, original_index, ""};
}
index++;
// TODO: обработать вложенные кавычки
while (c = raw_json[index], c != '"') {
if (index == raw_json.length()) {
return {token, index, format_error("Unexpected EOF while lexing string", raw_json, index)};
}
token.value += c;
index++;
}
index++;
return {token, index, ""};
}
Здесь ничего особенного, так что переходим к лексингу чисел.
lex_number
Поскольку мы поддерживаем только целые, внутреннего состояния эта функция иметь не будет. Мы проверяем символы, пока не прекращаются цифры.
std::tuple lex_number(std::string raw_json,
int original_index) {
int index = original_index;
JSONToken token = {"", JSONTokenType::Number, index};
std::string value = "";
// TODO: обработать не только целые числа
while (true) {
if (index == raw_json.length()) {
break;
}
auto c = raw_json[index];
if (!(c >= '0' && c <= '9')) {
break;
}
token.value += c;
index++;
}
return {token, index, ""};
}
Готово. Переходим к ключевым словам: null, false, true.
lex_keyword
Эта вспомогательная функция будет проверять наличие ключевых слов.
std::tuple lex_keyword(std::string raw_json,
std::string keyword,
JSONTokenType type,
int original_index) {
int index = original_index;
JSONToken token{"", type, index};
while (keyword[index - original_index] == raw_json[index]) {
if (index == raw_json.length()) {
break;
}
index++;
}
if (index - original_index == keyword.length()) {
token.value = keyword;
}
return {token, index, ""};
}
Далее реализуем lex_false, lex_true и lex_null.
std::tuple lex_null(std::string raw_json,
int index) {
return lex_keyword(raw_json, "null", JSONTokenType::Null, index);
}
std::tuple lex_true(std::string raw_json,
int index) {
return lex_keyword(raw_json, "true", JSONTokenType::Boolean, index);
}
std::tuple lex_false(std::string raw_json,
int index) {
return lex_keyword(raw_json, "false", JSONTokenType::Boolean, index);
}
И на этом с лексингом покончено! Несмотря на то, что мы определяли все эти компоненты сверху вниз, писать их лучше в обратном порядке или размещать в более ранних объявлениях.
При желании теперь можно написать простую main.cpp вроде:
#include "json.hpp"
#include
int main(int argc, char *argv[]) {
if (argc == 1) {
std::cerr << "Expected JSON input argument to parse" << std::endl;
return 1;
}
std::string in{argv[1]};
auto [tokens, error] = json::lex(in);
if (error.size()) {
std::cerr << error << std::endl;
return 1;
}
for (auto t : tokens) {
std::cout << t.value << std::endl;
}
}
Настраиваем Makefile:
main: *.cpp ./include/*.hpp
clang++ -g -Wall -std=c++2a -I./include *.cpp -o $@
Выполняем сборку с помощью make и запускаем ./main '{"a": 1}' для отображения списка полученных токенов.
Теперь перейдем к парсингу из массива токенов.
Парсинг
В ходе этого процесса мы будем получать токены и возвращать их в виде дерева. При обнаружении токена [ или { создается потомок дерева, после чего заполняется содержимым до встречи токена ] или }, который его завершает.
std::tuple parse(std::vector tokens,
int index) {
auto token = tokens[index];
switch (token.type) {
case JSONTokenType::Number: {
auto n = std::stod(token.value);
return {JSONValue{.number = n, .type = JSONValueType::Number}, index + 1, ""};
}
case JSONTokenType::Boolean:
return {JSONValue{.boolean = token.value == "true", .type = JSONValueType::Boolean}, index + 1, ""};
case JSONTokenType::Null:
return {JSONValue{.type = JSONValueType::Null}, index + 1, ""};
case JSONTokenType::String:
return {JSONValue{.string = token.value, .type = JSONValueType::String}, index + 1, ""};
case JSONTokenType::Syntax:
if (token.value == "[") {
auto [array, new_index, error] = parse_array(tokens, index + 1);
return {JSONValue{.array = array, .type = JSONValueType::Array}, new_index, error};
}
if (token.value == "{") {
auto [object, new_index, error] = parse_object(tokens, index + 1);
return {JSONValue{.object = std::optional(object), .type = JSONValueType::Object}, new_index, error};
}
}
return {{}, index, format_parse_error("Failed to parse", token)};
}
Здесь мы уже ссылаемся на format_parse_error, которая по аналогии с format_error создает строку ошибки. На деле она вызывает format_error, но с деталями относительно парсинга.
std::string JSONTokenType_to_string(JSONTokenType jtt) {
switch (jtt) {
case JSONTokenType::String:
return "String";
case JSONTokenType::Number:
return "Number";
case JSONTokenType::Syntax:
return "Syntax";
case JSONTokenType::Boolean:
return "Boolean";
case JSONTokenType::Null:
return "Null";
}
}
std::string format_parse_error(std::string base, JSONToken token) {
std::ostringstream s;
s << "Unexpected token '" << token.value << "', type '"
<< JSONTokenType_to_string(token.type) << "', index ";
s << std::endl << base;
return format_error(s.str(), *token.full_source, token.location);
}
При преобразовании перечисления JSONTokenType в строку эта функция опиралась на другую, вспомогательную. Для пользователя это очень неудобно, когда язык изначально не предоставляет методы перевода перечислений в строку для отладки. Я знаю, что в С++ есть способы реализации этого с помощью отражения, но для меня они показались сложноватыми, хотя я учусь.
parse_array
Эту функцию вызывала parse при обнаружении открывающейся скобки. Она должна рекурсивно вызывать parse, а затем проверять наличие запятой и повторять ее вызов… пока не встретит закрывающую скобку.
Выполнение этой функции провалится, если она встретит что-либо кроме запятой или закрывающей скобки, сопровождаемой успешным вызовом parse.
std::tuple, int, std::string>
parse_array(std::vector tokens, int index) {
std::vector children = {};
while (index < tokens.size()) {
auto t = tokens[index];
if (t.type == JSONTokenType::Syntax) {
if (t.value == "]") {
return {children, index + 1, ""};
}
if (t.value == ",") {
index++;
t = tokens[index];
} else if (children.size() > 0) {
return {{},
index,
format_parse_error("Expected comma after element in array", t)};
}
}
auto [child, new_index, error] = parse(tokens, index);
if (error.size()) {
return {{}, index, error};
}
children.push_back(child);
index = new_index;
}
return {
{},
index,
format_parse_error("Unexpected EOF while parsing array", tokens[index])};
}
Осталось реализовать parse_object.
parse_object
Эта функция похожа на parse_array, но ее задача в поиске пар по шаблону $string COLON $parse() COMMA.
std::tuple, int, std::string>
parse_object(std::vector tokens, int index) {
std::map values = {};
while (index < tokens.size()) {
auto t = tokens[index];
if (t.type == JSONTokenType::Syntax) {
if (t.value == "}") {
return {values, index + 1, ""};
}
if (t.value == ",") {
index++;
t = tokens[index];
} else if (values.size() > 0) {
return {
{},
index,
format_parse_error("Expected comma after element in object", t)};
} else {
return {{},
index,
format_parse_error(
"Expected key-value pair or closing brace in object", t)};
}
}
auto [key, new_index, error] = parse(tokens, index);
if (error.size()) {
return {{}, index, error};
}
if (key.type != JSONValueType::String) {
return {
{}, index, format_parse_error("Expected string key in object", t)};
}
index = new_index;
t = tokens[index];
if (!(t.type == JSONTokenType::Syntax && t.value == ":")) {
return {{},
index,
format_parse_error("Expected colon after key in object", t)};
}
index++;
t = tokens[index];
auto [value, new_index1, error1] = parse(tokens, index);
if (error1.size()) {
return {{}, index, error1};
}
values[key.string.value()] = value;
index = new_index1;
}
return {values, index + 1, ""};
}
Эти функции парсинга несколько монотонны, но при этом просты.
Теперь можно реализовать вариацию parse, связывающую лексинг и парсинг.
std::tuple parse(std::string source) {
auto [tokens, error] = json::lex(source);
if (error.size()) {
return {{}, error};
}
auto [ast, _, error1] = json::parse(tokens);
return {ast, error1};
}
При этом мы полностью завершили перевод строки в код JSONValue.
deparse
Заключительная часть реализации состоит в реверсировании последних операций: генерации строки из JSONValue.
Это рекурсивная функция, и ее единственная хитрость состоит в правильной обработке пустых пространств для получения более стройного вывода.
std::string deparse(JSONValue v, std::string whitespace) {
switch (v.type) {
case JSONValueType::String:
return "\"" + v.string.value() + "\"";
case JSONValueType::Boolean:
return (v.boolean.value() ? "true" : "false");
case JSONValueType::Number:
return std::to_string(v.number.value());
case JSONValueType::Null:
return "null";
case JSONValueType::Array: {
std::string s = "[\n";
auto a = v.array.value();
for (int i = 0; i < a.size(); i++) {
auto value = a[i];
s += whitespace + " " + deparse(value, whitespace + " ");
if (i < a.size() - 1) {
s += ",";
}
s += "\n";
}
return s + whitespace + "]";
}
case JSONValueType::Object: {
std::string s = "{\n";
auto values = v.object.value();
auto i = 0;
for (auto const &[key, value] : values) {
s += whitespace + " " + "\"" + key +
"\": " + deparse(value, whitespace + " ");
if (i < values.size() - 1) {
s += ",";
}
s += "\n";
i++;
}
return s + whitespace + "}";
}
}
}
Готово!
main.cpp
Эта программа будет просто получать на входе JSON, парсить его и выводить обратно. Нечто вроде упрощенной jq.
#include "json.hpp"
#include
int main(int argc, char *argv[]) {
if (argc == 1) {
std::cerr << "Expected JSON input argument to parse" << std::endl;
return 1;
}
std::string in{argv[1]};
auto [ast, error] = json::parse(in);
if (error.size()) {
std::cerr << error << std::endl;
return 1;
}
std::cout << json::deparse(ast);
}
Собираем ее с помощью ранее определенной make и тестируем на чем-нибудь крупном вроде этого.
$ cd cpp-json
$ make
$ ./main "$(cat ./test/glossary.json)"
{
"glossary": {
"GlossDiv": {
"GlossList": {
"GlossEntry": {
"Abbrev": "ISO 8879:1986",
"Acronym": "SGML",
"GlossDef": {
"GlossSeeAlso": [
"GML",
"XML"
],
"para": "A meta-markup language, used to create markup languages such as DocBook."
},
"GlossSee": "markup",
"GlossTerm": "Standard Generalized Markup Language",
"ID": "SGML",
"SortAs": "SGML"
}
},
"title": "S"
},
"title": "example glossary"
}
}
Или чем-то неверном вроде:
./main '{"foo": [{ 1: 2 }]}'
Unexpected token '1', type 'Number', index
Expected string key in object at line 1, column 11
{"foo": [{ 1: 2 }]}
^
И прогоняем через Valgrind:
valgrind ./main '{"a": [1, 2, null, { "c": 129 }]}'
==153027== Memcheck, a memory error detector
==153027== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==153027== Using Valgrind-3.17.0 and LibVEX; rerun with -h for copyright info
==153027== Command: ./main {"a":\ [1,\ 2,\ null,\ {\ "c":\ 129\ }]}
==153027==
{
"a": [
1.000000,
2.000000,
null,
{
"c": 129.000000
}
]
}==153027==
==153027== HEAP SUMMARY:
==153027== in use at exit: 0 bytes in 0 blocks
==153027== total heap usage: 128 allocs, 128 frees, 105,386 bytes allocated
==153027==
==153027== All heap blocks were freed -- no leaks are possible
==153027==
==153027== For lists of detected and suppressed errors, rerun with: -s
==153027== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Весьма неплохо. Мне нравится современный C++!
