Пишем простую библиотеку 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 <tuple>
#include <vector>
#include <string>

namespace json {
std::tuple<std::vector<JSONToken>, std::string> lex(std::string);
std::tuple<JSONValue, int, std::string> parse(std::vector<JSONToken>, int index = 0);
} // namespace json

#endif

Токен, возвращенный lex, должен будет содержать строковое значение, местоположение (смещение) в оригинальном источнике, указатель на весь источник (для отладки), а также тип. Сам тип токена будет представлен перечислением из String, Number, Syntax (двоеточие, скобки и т.д.), Boolean либо Null.

...
#include <string>
#include <memory>

namespace json {

enum class JSONTokenType { String, Number, Syntax, Boolean, Null };
struct JSONToken {
  std::string value;
  JSONTokenType type;
  int location;
  std::shared_ptr<std::string> full_source;
};

...

} // namespace json

...

Это единственное место во всем коде, где мы будем передавать указатель. Использование std::shared_ptr избавляет нас от ручного управления памятью. Никаких new или delete.

Идем далее. JSONValue представляет структуру, содержащую опциональные поля String, Number, Boolean, Array и Object, с указанием типа для их различения.

...
#include <map>
#include <optional>

namespace json {

enum class JSONValueType { String, Number, Object, Array, Boolean, Null };
struct JSONValue {
  std::optional<std::string> string;
  std::optional<double> number;
  std::optional<bool> boolean;
  std::optional<std::vector<JSONValue>> array;
  std::optional<std::map<std::string, JSONValue>> object;
  JSONValueType type;
};

enum class JSONTokenType { String, Number, Syntax, Boolean, Null };

...

Благодаря std::optional мы можем избежать использования указателей для описания этих полей. Я заглянул в std::variant, но его API показался мне слишком сложным.

В завершении добавляем еще две функции: высокоуровневую parse, которая объединяет работу лексера и парсера, и deparse для вывода JSONValue в виде строки JSON.

...
std::tuple<JSONValue, int, std::string> parse(std::vector<JSONToken>, int index = 0);
std::tuple<JSONValue, std::string> 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::vector<JSONToken>, std::string> lex(std::string raw_json) {
  std::vector<JSONToken> tokens;
  // Все токены будут нести указатели на исходный JSON для дальнейшей отладки
  auto original_copy = std::make_shared<std::string>(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 <sstream>

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<JSONToken, int, std::string> 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<JSONToken, int, std::string> 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<JSONToken, int, std::string> 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<JSONToken, int, std::string> 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<JSONToken, int, std::string> lex_null(std::string raw_json,
                                                 int index) {
  return lex_keyword(raw_json, "null", JSONTokenType::Null, index);
}

std::tuple<JSONToken, int, std::string> lex_true(std::string raw_json,
                                                 int index) {
  return lex_keyword(raw_json, "true", JSONTokenType::Boolean, index);
}

std::tuple<JSONToken, int, std::string> lex_false(std::string raw_json,
                                                  int index) {
  return lex_keyword(raw_json, "false", JSONTokenType::Boolean, index);
}

И на этом с лексингом покончено! Несмотря на то, что мы определяли все эти компоненты сверху вниз, писать их лучше в обратном порядке или размещать в более ранних объявлениях.

При желании теперь можно написать простую main.cpp вроде:

#include "json.hpp"

#include <iostream>

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<JSONValue, int, std::string> parse(std::vector<JSONToken> 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<std::vector<JSONValue>, int, std::string>
parse_array(std::vector<JSONToken> tokens, int index) {
  std::vector<JSONValue> 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<std::map<std::string, JSONValue>, int, std::string>
parse_object(std::vector<JSONToken> tokens, int index) {
  std::map<std::string, JSONValue> 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<JSONValue, std::string> 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 <iostream>

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++!