// Matrix Construct

//

// Copyright (C) Matrix Construct Developers, Authors & Contributors

// Copyright (C) 2016-2018 Jason Volk <jason@zemos.net>

//

// Permission to use, copy, modify, and/or distribute this software for any

// purpose with or without fee is hereby granted, provided that the above

// copyright notice and this permission notice is present in all copies. The

// full license for this software is available in the LICENSE file.

#pragma GCC visibility push(internal)

namespace ircd::json

{

using namespace ircd::spirit;

// Instantiations of the grammars

struct parser extern const parser;

struct printer extern const printer;

}

#pragma GCC visibility pop

#pragma GCC visibility push(internal)

BOOST_FUSION_ADAPT_STRUCT

(

ircd::json::member,

( decltype(ircd::json::member::first), first )

( decltype(ircd::json::member::second), second )

)

#pragma GCC visibility pop

#pragma GCC visibility push(internal)

BOOST_FUSION_ADAPT_STRUCT

(

ircd::json::object::member,

( decltype(ircd::json::object::member::first), first )

( decltype(ircd::json::object::member::second), second )

)

#pragma GCC visibility pop

#pragma GCC diagnostic push

#pragma GCC diagnostic ignored "-Wuninitialized"

struct [[gnu::visibility("internal")]]

ircd::json::parser

:qi::grammar<const char *, unused_type>

{

using it = const char *;

template<class T = unused_type,

class... A>

using rule = qi::rule<it, T, A...>;

const rule<> NUL { lit('\0') ,"nul" };

// insignificant whitespaces

const rule<> SP { lit('\x20') ,"space" };

const rule<> HT { lit('\x09') ,"horizontal tab" };

const rule<> CR { lit('\x0D') ,"carriage return" };

const rule<> LF { lit('\x0A') ,"line feed" };

// whitespace skipping

const rule<> WS { SP | HT | CR | LF ,"whitespace" };

const rule<> ws { *(WS) ,"whitespace monoid" };

const rule<> wsp { +(WS) ,"whitespace semigroup" };

// structural

const rule<> object_begin { lit('{') ,"object begin" };

const rule<> object_end { lit('}') ,"object end" };

const rule<> array_begin { lit('[') ,"array begin" };

const rule<> array_end { lit(']') ,"array end" };

const rule<> name_sep { lit(':') ,"name sep" };

const rule<> value_sep { lit(',') ,"value sep" };

const rule<> escape { lit('\\') ,"escape" };

const rule<> quote { lit('"') ,"quote" };

// literal

const rule<> lit_false { lit("false") ,"literal false" };

const rule<> lit_true { lit("true") ,"literal true" };

const rule<> lit_null { lit("null") ,"null" };

const rule<> boolean { lit_true | lit_false ,"boolean" };

const rule<> literal { lit_true | lit_false | lit_null ,"literal" };

// numerical

const rule<> number_int

{

(char_("1-9") >> repeat(0, 18)[char_("0-9")]) | lit('0')

,"integer"

};

const rule<> number_frac

{

lit('.') >> repeat(1, 18)[char_("0-9")] >> -char_("1-9")

,"fraction"

};

const rule<> number_exp

{

char_("eE") >> -char_("+-") >> repeat(1, 4)[char_("0-9")]

,"exponent"

};

const rule<> number

{

-lit('-') >> number_int >> -number_frac >> -number_exp

,"number"

};

// string

const rule<> utf16_surrogate

{

qi::uint_parser

<

uint16_t, // 16 bit width

16U, // base-16 (hex)

4U, // minimum digits

4U // maximum digits

>{}

,"UTF-16 surrogate"

};

const rule<> unicode

{

lit('u') >> utf16_surrogate

,"escaped unicode"

};

const rule<> control

{

char_('\x00', '\x1F')

,"control character"

};

// characters that must be escaped

const rule<> escaped

{

quote | escape | control

,"escaped character"

};

// characters that should appear after an escaping solidus

const rule<> escaper

{

char_("btnfr0\"\\") | unicode

,"escaper"

};

// cscapers supersetting the rule above with addl non-canonical chars

const rule<> escaper_nc

{

escaper | lit('/')

,"escaper"

};

const rule<> escape_sequence

{

escape >> escaper_nc

,"escape sequence"

};

const rule<string_view> chars

{

//raw[*((char_ - escaped) | (escape >> escaper_nc))]

raw[*((~char_('\x00', '\x1F') - char_("\x22\x5C")) | (escape >> escaper_nc))]

,"characters"

};

template<class block_t> static u64x2 string_content_block(const block_t, const block_t) noexcept;

const custom_parser string_content{};

const rule<string_view> string

{

//quote >> chars >> (!escape >> quote)

string_content

,"string"

};

// container

const rule<string_view> name

{

string.alias()

,"name"

};

// recursion depth

_r1_type depth;

[[noreturn]] static void throws_exceeded();

rule<unused_type(uint)> member

{

name >> -ws >> name_sep >> -ws >> value(depth)

,"member"

};

rule<unused_type(uint)> object

{

(eps(depth < json::object::max_recursion_depth) | eps[throws_exceeded]) >>

object_begin >> -((-ws >> member(depth)) % (-ws >> value_sep)) >> -ws >> object_end

,"object"

};

rule<unused_type(uint)> array

{

(eps(depth < json::array::max_recursion_depth) | eps[throws_exceeded]) >>

array_begin >> -((-ws >> value(depth)) % (-ws >> value_sep)) >> -ws >> array_end

,"array"

};

// primary recursive rule

rule<unused_type(uint)> value

{

(&quote >> string)

| (&object_begin >> object(depth + 1))

| (&array_begin >> array(depth + 1))

| number

| lit_true

| lit_false

| lit_null

,"value"

};

template<class gen,

class... attr>

bool operator()(const char *&start, const char *const &stop, gen&&, attr&&...) const;

template<class gen,

class... attr>

bool operator()(const char *const &start, const char *const &stop, gen&&, attr&&...) const;

parser() noexcept

:parser::base_type{rule<>{}} // required by spirit

{

// synthesized repropagation of recursive rules

value %= (&quote >> string)

| (&object_begin >> object(depth + 1))

| (&array_begin >> array(depth + 1))

| number

| lit_true

| lit_false

| lit_null

;

}

}

const ircd::json::parser;

#pragma GCC diagnostic pop

struct [[gnu::visibility("internal")]]

ircd::json::printer

:karma::grammar<char *, unused_type>

{

using it = char *;

template<class T = unused_type,

class... A>

using rule = karma::rule<it, T, A...>;

const rule<> NUL { lit('\0') ,"nul" };

// insignificant whitespaces

const rule<> SP { lit('\x20') ,"space" };

const rule<> HT { lit('\x09') ,"horizontal tab" };

const rule<> CR { lit('\x0D') ,"carriage return" };

const rule<> LF { lit('\x0A') ,"line feed" };

// whitespace skipping

const rule<> WS { SP | HT | CR | LF ,"whitespace" };

const rule<> ws { *(WS) ,"whitespace monoid" };

const rule<> wsp { +(WS) ,"whitespace semigroup" };

// structural

const rule<> object_begin { lit('{') ,"object begin" };

const rule<> object_end { lit('}') ,"object end" };

const rule<> array_begin { lit('[') ,"array begin" };

const rule<> array_end { lit(']') ,"array end" };

const rule<> name_sep { lit(':') ,"name separator" };

const rule<> value_sep { lit(',') ,"value separator" };

const rule<> quote { lit('"') ,"quote" };

const rule<> escape { lit('\\') ,"escape" };

// literal

const rule<string_view> lit_true { karma::string("true") ,"literal true" };

const rule<string_view> lit_false { karma::string("false") ,"literal false" };

const rule<string_view> lit_null { karma::string("null") ,"literal null" };

const rule<string_view> boolean { lit_true | lit_false ,"boolean" };

const rule<string_view> literal { lit_true | lit_false | lit_null ,"literal" };

// number

const rule<string_view> number

{

double_

,"number"

};

// string

using string_context = boost::spirit::context<fusion::cons<const string_view &>, fusion::vector<>>;

static void string_generate(unused_type, string_context &, bool &) noexcept;

const rule<string_view()> string

{

quote << eps[std::bind(&printer::string_generate, ph::_1, ph::_2, ph::_3)] << quote

,"string"

};

const rule<string_view()> name

{

string.alias()

,"name"

};

// primary recursive rule

rule<string_view> value

{

rule<string_view>{}

,"value"

};

rule<json::object::member> member

{

rule<json::object::member>{}

,"member"

};

rule<json::object> object

{

rule<json::object>{}

,"object"

};

rule<json::array> array

{

rule<json::array>{}

,"array"

};

template<class it_a,

class it_b,

class closure>

static void list_protocol(mutable_buffer &, it_a begin, const it_b &end, closure&&);

template<class gen,

class... attr>

void operator()(mutable_buffer &out, gen&&, attr&&...) const;

printer() noexcept

:printer::base_type{rule<>{}}

{

// synthesized repropagation of recursive rules

member %= name << name_sep << value;

object %= object_begin << -(member % value_sep) << object_end;

array %= array_begin << -(value % value_sep) << array_end;

value %= (&object << object)

| (&array << array)

| (&literal << literal)

| (&number << number)

| string

;

}

}

const ircd::json::printer;

decltype(ircd::json::stats)

ircd::json::stats;

template<class gen,

class... attr>

[[gnu::always_inline]]

inline void

ircd::json::printer::operator()(mutable_buffer &out,

gen&& g,

attr&&... a)

const

{

#ifdef IRCD_JSON_PRINTER_STATS

++stats.print_calls;

const prof::scope_cycles timer{stats.print_cycles};

#endif

if(unlikely(!ircd::generate(out, std::forward<gen>(g), std::forward<attr>(a)...)))

throw print_error

{

"Failed to generate JSON"

};

}

template<class it_a,

class it_b,

class closure>

[[gnu::always_inline]]

inline void

ircd::json::printer::list_protocol(mutable_buffer &out,

it_a it,

const it_b &end,

closure&& lambda)

{

if(likely(it != end))

{

lambda(out, *it);

for(++it; it != end; ++it)

{

const auto &printer(json::printer);

printer(out, printer.value_sep);

lambda(out, *it);

}

}

}

inline void

ircd::json::printer::string_generate(unused_type,

string_context &g,

bool &ret)

noexcept

{

#if __has_builtin(__builtin_assume)

__builtin_assume(ret == true);

#endif

assert(generator_state);

auto &state

{

*generator_state

};

const string_view &input

{

attr_at<0>(g)

};

const size_t output_length

{

json::string::stringify(state.out, input)

};

const size_t consumed

{

std::min(output_length, size(state.out))

};

state.consumed += consume(state.out, consumed);

state.generated += output_length;

ret = state.generated == state.consumed;

}

template<class gen,

class... attr>

[[gnu::always_inline]]

inline bool

ircd::json::parser::operator()(const char *const &start_,

const char *const &stop,

gen&& g,

attr&&...a)

const

{

const char *start(start_);

return operator()(start, stop, std::forward<gen>(g), std::forward<attr>(a)...);

}

template<class gen,

class... attr>

[[gnu::always_inline]]

inline bool

ircd::json::parser::operator()(const char *&start,

const char *const &stop,

gen&& g,

attr&&...a)

const

{

#ifdef IRCD_JSON_PARSER_STATS

++stats.parse_calls;

const prof::scope_cycles timer{stats.parse_cycles};

#endif

return ircd::parse<parse_error>(start, stop, std::forward<gen>(g), std::forward<attr>(a)...);

}

/// The input covers everything from the alleged start of our alleged string

/// to the end of whatever the user provided. Returns true if successful and

/// the result string_view is set in the context attribute; the iterator is

/// advanced.

template<class iterator,

class context,

class skipper,

class attr>

inline bool

ircd::json::custom_parser::parse(iterator &__restrict__ start,

const iterator &__restrict__ stop,

context &g,

const skipper &,

attr &)

const

{

// Clang scales between 128bit and 256bit systems when we use the 256 bit

// type (note that performance even improves on some 128 bit systems). GCC

// falls back to scalar instead, so we have to case 128bit systems on GCC.

#if defined(__AVX__) || defined(__clang__)

using block_t = u8x32;

using block_t_u = u256x1_u;

#else

using block_t = u8x16;

using block_t_u = u128x1_u;

#endif

assert(start <= stop);

const size_t input_max

{

size_t(std::distance(start, stop))

};

// The input is a priori invalid if the length is not greater than "" or

// the first character is not quote.

const bool input_valid

{

input_max >= 2 && start[0] == '"'

};

// When the input is valid subtract one for the new max length. Otherwise

// we mask this length to zero to void the remainder of this frame.

const u64x2 max

{

0, (input_max - 1) & boolmask<u64>(input_valid)

};

static const auto each_block

{

json::parser::string_content_block<block_t>

};

const auto count

{

simd::stream<block_t_u, block_t>(start + 1, max, each_block)

};

const bool ok

{

count[0] == 1

};

// Set the result in the context attribute. This covers the string content

// without surrounding quotes.

attr_at<0>(g) = string_view

{

start + ok, count[1] & boolmask<u64>(ok)

};

// Advance the iterator the length of the full string including quotes

// iff this parser was successful.

start += (1 + count[1] + 1) & boolmask<u64>(ok);

return ok;

}

template<class block_t>

inline ircd::u64x2

ircd::json::parser::string_content_block(const block_t block,

const block_t block_mask)

noexcept

{

assert(block_mask[0] == 0xff);

const block_t is_esc

(

block == '\\'

);

const block_t is_quote

(

block == '"'

);

const block_t is_ctrl

(

block < 0x20

);

const block_t is_special

{

is_esc | is_quote | is_ctrl

};

const block_t is_regular

{

simd::lateral<std::bit_and>(~is_special)

};

if(likely(is_regular[0]))

return u64x2

{

0, sizeof(block)

};

const u64 regular_prefix_count

{

simd::lzcnt(is_special | ~block_mask) / 8

};

if(likely(regular_prefix_count))

return u64x2

{

0, regular_prefix_count

};

const u64 err

{

popmask<u64>(is_quote[0])

| boolmask<u64>(is_ctrl[0])

| boolmask<u64>(is_esc[0] & ~block_mask[1])

};

const u64 add

{

1UL + popmask<u64>(is_esc[0] & (is_quote[1] | is_esc[1]) & block_mask[1])

};

return u64x2

{

err, add & boolmask<u64>(err == 0)

};

}

[[gnu::noinline]]

void

ircd::json::parser::throws_exceeded()

{

throw recursion_limit

{

"Maximum recursion depth exceeded"

};

}

///////////////////////////////////////////////////////////////////////////////

//

// json/tool.h

//

ircd::json::strung

ircd::json::replace(const strung &s,

const json::members &r)

{

static const auto in

{

[](const json::members &r, const object::member &m)

{

return std::any_of(begin(r), end(r), [&m]

(const json::member &r)

{

return string_view{r.first} == m.first;

});

}

};

if(!empty(s) && type(s) != type::OBJECT)

throw type_error

{

"Cannot replace member into JSON of type %s",

reflect(type(s))

};

size_t mctr {0};

thread_local std::array<member, iov::max_size> mb;

for(const object::member &m : object{s})

if(!in(r, m))

mb.at(mctr++) = member{m};

for(const json::member &m : r)

mb.at(mctr++) = m;

return strung

{

mb.data(), mb.data() + mctr

};

}

ircd::json::strung

ircd::json::replace(const strung &s,

const json::member &m_)

{

if(!empty(s) && type(s) != type::OBJECT)

throw type_error

{

"Cannot replace member into JSON of type %s",

reflect(type(s))

};

size_t mctr {0};

thread_local std::array<member, iov::max_size> mb;

for(const object::member &m : object{s})

if(m.first != string_view{m_.first})

mb.at(mctr++) = member{m};

mb.at(mctr++) = m_;

return strung

{

mb.data(), mb.data() + mctr

};

}

ircd::json::strung

ircd::json::insert(const strung &s,

const json::member &m)

{

if(!empty(s) && type(s) != type::OBJECT)

throw type_error

{

"Cannot insert member into JSON of type %s",

reflect(type(s))

};

size_t mctr {0};

thread_local std::array<member, iov::max_size> mb;

for(const object::member &m : object{s})

mb.at(mctr++) = member{m};

mb.at(mctr++) = m;

return strung

{

mb.data(), mb.data() + mctr

};

}

ircd::json::strung

ircd::json::remove(const strung &s,

const string_view &key)

{

if(empty(s))

return s;

if(type(s) != type::OBJECT)

throw type_error

{

"Cannot remove object member '%s' from JSON of type %s",

key,

reflect(type(s))

};

size_t mctr {0};

thread_local std::array<object::member, iov::max_size> mb;

for(const object::member &m : object{s})

if(m.first != key)

mb.at(mctr++) = m;

return strung

{

mb.data(), mb.data() + mctr

};

}

ircd::json::strung

ircd::json::remove(const strung &s,

const size_t &idx)

{

if(empty(s))

return s;

if(type(s) != type::ARRAY)

throw type_error

{

"Cannot remove array element [%zu] from JSON of type %s",

idx,

reflect(type(s))

};

size_t mctr{0}, i{0};

thread_local std::array<string_view, iov::max_size> mb;

for(const string_view &m : array{s})

if(i++ != idx)

mb.at(mctr++) = m;

return strung

{

mb.data(), mb.data() + mctr

};

}

void

ircd::json::merge(stack::object &out,

const vector &v)

{

struct val

{

//TODO: optimize with std::pmr::monotonic_buffer_resource et al

std::map<string_view, val, std::less<>> o;

std::vector<string_view> a;

string_view v;

void _merge_object(const json::object &o)

{

for(const auto &m : o)

{

val &v(this->o[m.first]);

v.merge(m.second);

}

}

void _merge_array(const json::array &a)

{

for(const auto &v : a)

this->a.emplace_back(v);

}

void merge(const string_view &v)

{

switch(json::type(v))

{

case json::OBJECT: _merge_object(v); break;

case json::ARRAY: _merge_array(v); break;

default: this->v = v; break;

}

}

void _compose_object(json::stack &out, json::stack::object &object) const

{

for(const auto &m : o)

{

json::stack::member member{object, m.first};

m.second.compose(out);

}

}

void _compose_object(json::stack &out, json::stack::member &member) const

{

json::stack::object object{member};

_compose_object(out, object);

}

void _compose_object(json::stack &out) const

{

json::stack::chase c{out, true};

if(c.m)

_compose_object(out, *c.m);

else if(c.o)

_compose_object(out, *c.o);

}

void _compose_array(json::stack &out) const

{

json::stack::array array{out};

for(const auto &v : a)

array.append(v);

}

void _compose_value(json::stack &out) const

{

json::stack::chase c{out, true};

if(c.a)

c.a->append(v);

else if(c.m)

c.m->append(v);

else

assert(0);

}

void compose(json::stack &out) const

{

if(!o.empty())

_compose_object(out);

else if(!a.empty())

_compose_array(out);

else if(!v.empty())

_compose_value(out);

}

val() = default;

val(const string_view &v)

{

merge(v);

}

};

val top;

for(const auto &o : v)

top.merge(o);

assert(out.s);

top.compose(*out.s);

}

///////////////////////////////////////////////////////////////////////////////

//

// json/stack.h

//

ircd::json::stack::stack(const mutable_buffer &buf,

flush_callback flusher,

const size_t &hiwat,

const size_t &lowat)

:buf{buf}

,flusher{std::move(flusher)}

,hiwat{hiwat}

,lowat{lowat}

{

}

ircd::json::stack::stack(stack &&other)

noexcept

:buf{std::move(other.buf)}

,flusher{std::move(other.flusher)}

,eptr{std::move(other.eptr)}

,cp{std::move(other.cp)}

,appended{std::move(other.appended)}

,flushed{std::move(other.flushed)}

,level{std::move(other.level)}

,hiwat{std::move(other.hiwat)}

,lowat{std::move(other.lowat)}

,co{std::move(other.co)}

,ca{std::move(other.ca)}

{

other.cp = nullptr;

other.co = nullptr;

other.ca = nullptr;

if(cp)

{

assert(cp->s == &other);

cp->s = this;

}

if(co)

{

assert(co->s == &other);

co->s = this;

}

if(ca)

{

assert(ca->s == &other);

ca->s = this;

}

}

ircd::json::stack::~stack()

noexcept

{

assert(closed());

if(buf.consumed())

flush(true);

assert(clean() || done());

}

void

ircd::json::stack::append(const char &c)

noexcept

{

append(1, [&c]

(const mutable_buffer &buf)

noexcept

{

buf[0] = c;

return 1;

});

}

void

ircd::json::stack::append(const string_view &s)

noexcept

{

append(s.size(), [&s]

(const mutable_buffer &buf)

noexcept

{

assert(ircd::size(buf) >= s.size());

return ircd::copy(buf, s);

});

}

void

ircd::json::stack::append(const size_t &expect,

const window_buffer::closure &closure)

noexcept try

{

if(!expect || failed())

return;

// Minimum bytes we keep available all times to allow the JSON to close

// correctly without complication on the user's stack unwind; hinted by

// the recursion level.

const size_t buf_min

{

level + 8

};

// Calculated buffer bytes required.

const size_t buf_req

{

expect + buf_min

};

// Since all appends are atomic, we need to have buffer available to print

// the JSON without having to flush while doing so. If we're low on buffer,

// this branch triggers a flush. Afterward, if there is still not enough

// buffer that's an error so the user needs to flush enough when called.

if(buf_req > buf.remaining())

{

if(unlikely(!flusher))

throw print_panic

{

"Insufficient buffer. I need %zu more bytes; you only have %zu left (of %zu).",

buf_req,

buf.remaining(),

size(buf.base)

};

if(!flush(true))

return;