proposal.bs

<pre class='metadata'>
Title: A Minimal JSON Support Library for C++
Abstract: This paper proposes a minimal JSON support library for C++, which provides a simple and efficient way to represent and manipulate JSON data. The library consists of four main components: a json class that represents a JSON value, a basic_json_node class that provide a type-erased json storage, and two json_slice class that provides access and modification operations to the json class. The library aims to be compatible with the existing C++ standard library, and provides strong extension support.
Editor: Yexuan Xiao, bizwen@nykz.org
Shortname: ????
Revision: 0
Status: D
Audience: LEWG
Group: WG21
Date: 2024-02-09
Markup Shorthands: markdown on
Markup Shorthands: biblio yes
ED: https://github.com/YexuanXiao/basic_json/blob/master/proposal.bs
</pre>

<style>
img {
	width: 100%
}
@media (prefers-color-scheme: dark) {
img {
	filter: invert(1) !important;
}
}
</style>

# Motivation

JSON is an internet standard, widely used for data transmission and storage, but the C++ standard library lacks support for JSON, which forces C++ users to choose among third-party libraries.

As the C++ standard evolves, C++ becomes more and more suitable for network programming, and C++'s high performance makes C++ equally suitable for processing large amounts of data stored by JSON, so adding JSON to the standard library is beneficial and harmless to C++.

There are many third-party libraries that provide JSON support for C++, but they have some drawbacks, such as:
- They may have external dependencies, which can increase the complexity and size of the project, and introduce potential errors and incompatibilities.
- They may have different interfaces, conventions, and styles, which can reduce the readability and consistency of the code, and increase the learning curve for new users.
- They may have different levels of features, performance, and compatibility, which can make it hard to choose the best one for a specific use case, and may require switching between different libraries for different scenarios.
- They may not follow the modern C++ standards and best practices, which can limit the usability and portability of the code, and prevent the use of new language features and idioms.

Therefore, this proposal aims to provide a minimal JSON support library for C++, which can address these issues, and offer the following benefits:

- It does not have any external dependencies, and can be easily integrated into any C++ project, without affecting the existing code or environment.
- It has a simple and consistent interface, which follows the existing C++ standard library conventions and styles, and can be easily learned and used by C++ programmers.
- It has a sufficient level of features, performance, and compatibility, which can cover most common use cases of JSON data, and can work with any conforming C++ compiler and platform.
- It is easy to implement, with only about 1500 lines of code, which avoids too much implementation details and problems.

# Proposal

I propose to add a json header file and five classes (templates): nulljson_t, basic_json_node, basic_json, basic_const_json_slice, basic_json_slice.

```cpp
struct nulljson_t;

inline constexpr nulljson_t nulljson{};

template <typename Number,
	typename Integer, typename UInteger, typename Allocator>
class basic_json_node;

template <typename Node, typename String,
	typename Array, typename Object,
	bool HasInteger, bool HasUInteger>
class basic_json;

template <typename Node, typename String,
	typename Array, typename Object,
	bool HasInteger, bool HasUInteger>
class basic_const_json_slice;

template <typename Node, typename String,
	typename Array, typename Object,
	bool HasInteger, bool HasUInteger>
class basic_json_slice;
```

# Design

Since JSON has a self-referential structure ([[RFC8259]]), type erasure must be used.

<img src="https://www.json.org/img/object.png" alt="json.org’s JSON structure diagram: object">
<img src="https://www.json.org/img/value.png" alt="json.org’s JSON structure diagram: value">

## nulljson/nulljson_t

nulljson is a type similar to nullopt, used to indicate that the value of JSON is null.

nulljson_t is the type of nulljson, it is a trivial type and can be default constructed.

## basic_json_node

basic_json_node has four template parameters, Number, Integer, UInteger, Allocator, users can use these template parameters to customize their preferred types and allocators.

For example, some users may prefer to use fixed-length integer types, some users may prefer to use integer types provided by C++ keywords, and the same for floating-point types.

basic_json_node usually holds an allocator, an enum that indicates the kind, and a union that stores boolean, number (floating point), integer, unsigned integer, string, array(vector), object(map).

basic_json_node is a substitute for basic_json, providing storage space for basic_json in any situation where circular dependencies may occur.

basic_json_node is conceptually similar to void*, it does not always own memory, but can transfer memory through it.

## basic_json

basica_json can be implemented as storing a basic_json_node as a non-static data member, and does not have any other non-static data members, which makes basic_json and basic_json_node have the same size.

The reason why the allocator is a template parameter of basic_json_node rather than basic_json is that basic_json must have the same size as basic_json_node, so char is usually used to instantiate the allocator (void type can be used after LWG issue [[3917]] is resolved),
and then rebind is used to allocate storage. Once a specialization of basic_json_node is available, basic_json can be instantiated.basic_json has six template parameters: Node, String, Array, Object, HasInteger, HasUInteger.

Node must be a specialization of basic_json_node, and since basic_json_node provides type aliases to obtain the template arguments, basic_json can extract these type aliases, rewrite the specialization of basic_json_node, and compare it with Node to ensure this.

For arithmetic and boolean types, they are directly stored in the union, and since map and array store basic_json_node, pointers are needed to break the circular dependency,
and since the two types are not determined when instantiating basic_json_node, they are actually void*. Conceptually, basic_json is a hybrid of container adapters and containers.

Although string type does not have circular dependency problem, void* is also used to save the space. The relationship between basic_json and basic_json_node is shown in the following figure:

<img src="https://raw.githubusercontent.com/YexuanXiao/basic_json/master/figure.png" alt="relationship diagram between node, json and slice">

Therefore, the Allocator template parameter of basic_json_node is not used directly, but is rebound to the allocators of string, array, and object.

The triviality of basic_json_node depends on Allocator, if Allocator is trivial, then basic_json arrays will get faster copy speed.

Most of the member functions of basic_json are constructors, which make C++ values easily convertible to json. The destructor is responsible for destructing the entire object, basic_json also has copy constructor and copy assignment, as well as swap implemented by hidden friend and member functions.

In addition, basic_json also json has a right-value-qualified to node_type conversion function, which can transfer memory from basic_json to basic_json_node, just like a pointer.

The most special point of my proposal is to expose basic_json_node, which allows users to implement their own serializer and deserializer in a non-intrusive way: if a basic_json object that stores a boolean or arithmetic type value is needed, then construct it directly through the constructor,
if a basic_json object that stores an array or object type is needed, then users can construct array and object themselves, such as `std::vector<basic_json_node<>> a` and `std::map<std::string, basic_json_node> m`, then construct basic_json objects through the constructors of boolean or arithmetic types,
and then insert them into the container, finally, move a or m to the constructor of basic_json, and get a basic_json object that represents an array or map.

## basic_json_slice/basic_const_json_slice

json_slice and const_json_slice are similar to iterator and const_iterator, const_json_slice is constructed from basic_json const& and holds a pointer to basic_json. All non-static functions of const_json_slice are const, and return a value or a reference to a const object.

json_slice has all the member functions that const_json_slice has, and can be converted to const_json_slice. In addition, json_slice also has modifiers (overload of assignment operators), which can modify the value without changing the type of the value stored by json.

json_slice is trivially copyable, so copying a json_slice has low overhead. Any operation on json_slice does not produce a copy of the basic_json object, and for subscript operations, json_slice always returns a new json_slice.

## Summary

This design makes the basic_json template independent of the specific vector type, map type, string type, and if the user likes, he can use std::map, std::flat_map, std::unordered_map,
and the string type as the Key of the Object and the String type as the Value can be different, which makes KeyString can be implemented with a dictionary that records all possible values.

This design does not care whether the string type has char_traits and allocator,
and in extreme cases, this design allows both strings to be std::string_view, such as mapping the json byte stream to memory, each std::string_view references a part of the memory.
This makes it possible to not copy any strings (but still need to use dynamic memory to store maps and arrays).

# Implementation experience

I have provided a simple implementation on [Github](https://github.com/YexuanXiao/basic_json/blob/master/basic_json.hpp), the source code of the document is available in the same repository.

I have not implemented any allocator-related functions, because I do not have much experience with allocators. I have not provided serialization and deserialization functions, because C++ currently does not have a good io api, and different users may have their own serialization and deserialization needs, so this is not part of the proposal.

The design is feasible and stable, but I need some feedback to appropriately increase the usability of the library.

# Use cases

```cpp
#include "basic_json.hpp"
#include <string_view>
int main()
{
	/*
		Note: This code is for demonstration purposes only and can be compiled only, not be run.
	*/
	// json
	using json = bizwen::json;
	using namespace std::literals;
	json j01{};
	json j02{ j01 };
	// j j03{ nullptr };  deleted
	json j04{ 1. };
	json j05{ true };
	json j06{ 1.f };
	json j07{ 1u };
	json j08{ 1l };
	json j09{ 1ll };
	json j10{ 1ull };
	json j11{ "aaa" };
	auto str = "bbb";
	json j12{ str, str + 3 };
	json j13{ str, 3 };
	json j14{ str };
	json j15{ "bbb"sv };
	// since initializer_list returns a reference to a const object, this method is inefficient
	// json j16{ json::array_type{ json{0}, json{1} } };
	// json j17{ json::object_type{ { "key0"s, json{ 0 } }, { "key1"s, json{ 1 } } } };
	json j16{ json::array{ 0, 1 } };
	json j17{ json::object{"key0"s, 0, "key1"s, 1} };
	json j18{ bizwen::basic_json_node<>{} };
	swap(j17, j18); // adl hidden friend
	j17.swap(j18);
	j17 = j18;
	std::swap(j17, j18);
	json::node_type n{ std::move(j18) };

	// const_slice
	using const_slice = bizwen::const_json_slice;
	const_slice c1;
	c1.empty();
	c1.array();
	c1.string();
	c1.null();
	c1.boolean();
	c1.number();
	c1.object();
	c1.array();
	c1.object();
	c1.integer();
	c1.uinteger();
	c1["key"];
	c1["key"s];
	// requires transparent comparable
	// c1["key"sv];
	c1[1];
	const_slice c2{ j17 };
	c2.swap(c1);
	std::swap(c1, c2);
	const_slice c3{ std::move(j17) };
	const_slice c4 = c3;
	const_slice c5 = std::move(c4);
	c4 = c5;
	c5 = std::move(c4);
	bool b{ c5 };
	bizwen::nulljson_t nj{ c5 };
	json::string_type const& s{ c5 };
	json::array_type const& a{ c5 };
	for (auto const& i : a)
	{
		const_slice item{ i };
	}
	json::object_type const& o{ c5 };
	for (auto const& [k, v] : o)
	{
		const_slice item{ v };
	}
	long long ll{ c5 };
	unsigned long long ull{ c5 };

	// slice
	using slice = bizwen::json_slice;
	slice s1{};
	slice s2{ j17 };
	const_slice c6 = s2;
	std::string str1;
	s2 = str1;
	s2 = std::string{};
	s2 = "aaa";
	s2 = std::string_view{};
	s2 = bizwen::nulljson;
	s2 = true;
	s2 = 1.;
	s2 = 1;
	s2 = 1u;
	s2 = 1ll;
	s2 = 1ull;
	s2 = n;
	s2["key"] = 1;
}
```

# Appendix

```cpp
struct nulljson_t
{
	explicit constexpr nulljson_t() noexcept = default;
};

inline constexpr nulljson_t nulljson;

template <typename Number = double,
	typename Integer = long long, typename UInteger = unsigned long long,
	typename Allocator = std::allocator<char>>
class basic_json_node
{
public:
	using number_type = Number;
	using integer_type = Integer;
	using uinteger_type = UInteger;
	using allocator_type = Allocator;

	constexpr basic_json_node() noexcept = default;
	constexpr basic_json_node(basic_json_node const&) = default;
	constexpr basic_json_node(basic_json_node&& rhs) noexcept = default;
	constexpr basic_json_node& operator=(basic_json_node&& rhs) noexcept = default;
}

template <typename Node = basic_json_node<>, typename String = std::string,
	typename Array = std::vector<Node>,
	typename Object = std::map<String, Node>,
	bool HasInteger = true, bool HasUInteger = true>
class basic_json
{
public:
	static inline constexpr bool has_integer = HasInteger;
	static inline constexpr bool has_uinteger = HasUInteger;

	using node_type = Node;
	using object_type = Object;
	using value_type = Node;
	using array_type = Array;
	using string_type = String;

	using slice_type = /* ... */;
	using const_slice_type = /* ... */;

	using number_type = node_type::number_type;
	using integer_type = node_type::integer_type;
	using uinteger_type = node_type::uinteger_type;

	using char_type = string_type::value_type;
	using map_node_type = object_type::value_type;
	using allocator_type = node_type::allocator_type;
	using key_string_type = object_type::key_type;
	using key_char_type = key_string_type::value_type;

	constexpr void swap(basic_json& rhs) noexcept;
	friend constexpr void swap(basic_json& lhs, basic_json& rhs) noexcept;
	constexpr basic_json() noexcept = default;
	constexpr basic_json(basic_json&& rhs) noexcept;
	constexpr basic_json(basic_json const& rhs);
	constexpr basic_json& operator=(basic_json&& rhs);
	constexpr basic_json& operator=(basic_json const& rhs);
	constexpr basic_json(decltype(nullptr)) noexcept = delete;
	template <typename T>
		requires std::is_arithmetic_v<T>
	constexpr basic_json(T n) noexcept
	constexpr explicit basic_json(string_type v);
	constexpr basic_json(char_t const* begin, char_t const* end);
	constexpr basic_json(char_t const* str, string_type::size_type count);
	constexpr explicit basic_json(char_t const* str);
	template <typename StrLike>
		requires std::constructible_from<string_type, StrLike>
		&& (std::is_convertible_v<StrLike const&, char_type const*> == false)
	constexpr basic_json(StrLike const& str);
	constexpr explicit basic_json(array_type arr);
	constexpr explicit basic_json(object_type obj);
	constexpr explicit basic_json(node_type&& n) noexcept;
	[[nodiscard("discard nodes will cause leaks")]] constexpr operator node_type() && noexcept;
	constexpr ~basic_json() noexcept;
	constexpr slice_type slice();
	constexpr const_slice_type slice() const;

	// Helper Classes
	template<typename... Ts>
	struct array{ /*implement defined */ };
	template <std::size_t N>
	struct object{ /*implement defined */ };
	template <typename... Ts>
	object(Ts&&...) -> object</* implement defined */>;
}

template <typename Node = basic_json_node<>, typename String = std::string,
	typename Array = std::vector<Node>,
	typename Object = std::map<String, Node>,
	bool HasInteger = true, bool HasUInteger = true>
class basic_json_slice
{
public:
	static inline constexpr bool has_integer = HasInteger;
	static inline constexpr bool has_uinteger = HasUInteger;

	using node_type = Node;
	using object_type = Object;
	using value_type = Node;
	using array_type = Array;
	using string_type = String;

	using slice_type = /* ... */;
	using const_slice_type = /* ... */;
	using json_type = /* ... */;
	
	using number_type = node_type::number_type;
	using integer_type = node_type::integer_type;
	using uinteger_type = node_type::uinteger_type;

	using char_type = string_type::value_type;
	using map_node_type = object_type::value_type;
	using allocator_type = node_type::allocator_type;
	using key_string_type = object_type::key_type;
	using key_char_type = key_string_type::value_type;

	[[nodiscard]] constexpr bool empty() const noexcept;
	[[nodiscard]] constexpr bool string() const noexcept;
	[[nodiscard]] constexpr bool null() const noexcept;
	[[nodiscard]] constexpr bool boolean() const noexcept;
	[[nodiscard]] constexpr bool number() const noexcept;
	[[nodiscard]] constexpr bool object() const noexcept;
	[[nodiscard]] constexpr bool array() const noexcept;
	[[nodiscard]] constexpr bool integer() const noexcept
		requires HasInteger;
	[[nodiscard]] constexpr bool uinteger() const noexcept
		requires HasUInteger;
	constexpr void swap(basic_json_slice& rhs) noexcept;
	friend constexpr void swap(basic_json_slice& lhs, basic_json_slice& rhs) noexcept;
	constexpr basic_json_slice() noexcept = default;
	constexpr basic_json_slice(basic_json_slice&& rhs) noexcept = default;
	constexpr basic_json_slice(basic_json_slice const& rhs) noexcept = default;
	constexpr basic_json_slice(json_t& j) noexcept;
	constexpr basic_json_slice(node_type& n) noexcept;
	constexpr basic_json_slice& operator=(basic_json_slice const& rhs) noexcept = default;
	constexpr basic_json_slice& operator=(basic_json_slice&& rhs) noexcept = default;
	constexpr explicit operator bool() const;
	constexpr explicit operator number_t() const;
	constexpr explicit operator nulljson_t() const;
	constexpr explicit operator string_type&() const&;
	constexpr explicit operator array_type&() const&;
	constexpr explicit operator object_type&() const&;
	constexpr explicit operator integer_t() const
		requires HasInteger;
	constexpr explicit operator uinteger_t() const
		requires HasUInteger;
	constexpr basic_json_slice operator[](key_string_t const& k);
	template <typename KeyStrLike>
		requires transparent_comparable<KeyStrLike, key_string_t>
		&& (std::is_convertible_v<KeyStrLike const&, key_char_type const*> == false)
	constexpr basic_json_slice operator[](KeyStrLike const& k);
	constexpr basic_json_slice operator[](key_char_t* k);
	constexpr basic_json_slice operator[](array_type::size_type pos);
	constexpr basic_json_slice& operator=(string_type const& str);
	constexpr basic_json_slice& operator=(string_type&& str);
	constexpr basic_json_slice& operator=(char_t* str);
	template <typename StrLike>
		requires std::constructible_from<string_type, StrLike>
		&& (std::is_convertible_v<KeyStrLike const&, key_char_type const*> == false)
	constexpr basic_json_slice& operator=(StrLike const& str);
	constexpr basic_json_slice& operator=(nulljson_t n);
	template <typename T>
		requires std::is_arithmetic_v<T>
	constexpr basic_json_slice& operator=(T n)
	constexpr basic_json_slice& operator=(json_t& j);
	constexpr basic_json_slice& operator=(node_type& n);
}

template <typename Node = basic_json_node<>, typename String = std::string,
	typename Array = std::vector<Node>,
	typename Object = std::map<String, Node>,
	bool HasInteger = true, bool HasUInteger = true>
class basic_const_json_slice
{
public:
	static inline constexpr bool has_integer = HasInteger;
	static inline constexpr bool has_uinteger = HasUInteger;

	using node_type = Node;
	using object_type = Object;
	using value_type = Node;
	using array_type = Array;
	using string_type = String;

	using slice_type = /* ... */;
	using const_slice_type = /* ... */;
	using json_type = /* ... */;
	
	using number_type = node_type::number_type;
	using integer_type = node_type::integer_type;
	using uinteger_type = node_type::uinteger_type;

	using char_type = string_type::value_type;
	using map_node_type = object_type::value_type;
	using allocator_type = node_type::allocator_type;
	using key_string_type = object_type::key_type;
	using key_char_type = key_string_type::value_type;

	[[nodiscard]] constexpr bool empty() const noexcept;
	[[nodiscard]] constexpr bool string() const noexcept;
	[[nodiscard]] constexpr bool null() const noexcept;
	[[nodiscard]] constexpr bool boolean() const noexcept;
	[[nodiscard]] constexpr bool number() const noexcept;
	[[nodiscard]] constexpr bool object() const noexcept;
	[[nodiscard]] constexpr bool array() const noexcept;
	[[nodiscard]] constexpr bool integer() const noexcept
		requires HasInteger;
	[[nodiscard]] constexpr bool uinteger() const noexcept
		requires HasUInteger;
	constexpr void swap(basic_const_json_slice& rhs) noexcept
	friend constexpr void swap(basic_const_json_slice& lhs, basic_const_json_slice& rhs) noexcept
	constexpr basic_const_json_slice() noexcept = default;
	constexpr basic_const_json_slice(basic_const_json_slice&& rhs) noexcept = default;
	constexpr basic_const_json_slice(basic_const_json_slice const& rhs) noexcept = default;
	constexpr basic_const_json_slice(json_t const& j) noexcept;
	constexpr basic_const_json_slice(node_type const& n) noexcept;
	constexpr basic_const_json_slice& operator=(basic_const_json_slice const& rhs) noexcept = default;
	constexpr basic_const_json_slice& operator=(basic_const_json_slice&& rhs) noexcept = default;
	constexpr explicit operator bool() const;
	constexpr explicit operator number_t() const;
	constexpr explicit operator nulljson_t() const;
	constexpr explicit operator const string_type&() const&;
	constexpr explicit operator const array_type&() const&;
	constexpr explicit operator const object_type&() const&;
	constexpr explicit operator integer_t() const
		requires HasInteger;
	constexpr explicit operator uinteger_t() const
		requires HasUInteger;
	constexpr basic_const_json_slice operator[](key_string_t const& k) const;
	template <typename KeyStrLike>
		requires transparent_comparable<KeyStrLike, key_string_t>
		&& (std::is_convertible_v<KeyStrLike const&, key_char_type const*> == false)
	constexpr basic_const_json_slice operator[](KeyStrLike const& k) const;
	constexpr basic_const_json_slice operator[](key_char_t* k) const;
	constexpr basic_const_json_slice operator[](array_type::size_type pos) const;
	constexpr basic_const_json_slice(slice_type const& s);
}
```

# Acknowledgements

Thanks to F.v.S for the information about the polymorphic allocator, and the suggestions for nulljson_t and constructor.

Thanks to ykiko for simplifying code using fold expressions.

Thanks to YanzuoLiu for patiently reviewing the code and providing a graceful implementation of constructing objects.

<pre class=biblio>
{
"RFC8259": {
	"title": "The JavaScript Object Notation (JSON) Data Interchange Format",
	"authors": [
		"IETF"
	],
	"href": "https://www.rfc-editor.org/rfc/rfc8259",
	"date": "December 2017"
	},
"3917": {
	"title": "Validity of allocator<void> and possibly polymorphic_allocator<void> should be clarified",
	"authors": [
		"Daniel Krügler"
	],
	"href": "https://cplusplus.github.io/LWG/issue3917",
	"date": "April 2023"
	}
}
</pre>