cheatah
Source BigBrain
Source

stdlib/parsers/json/json.cpp

1// Copyright (c) 2026 BigBrain LLC. MIT-licensed (see LICENSE).
2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.
3// json.cpp — implementation of the cheatah::parsers::json parser/serializer. All multi-line
4// logic lives here (declared in json.hpp); only trivial getters live in the token headers.
5//
6// Node is a class wrapping a std::variant, so its alternatives are reached via node.variant().
7// Dispatch is std::visit over that variant — compile-time, no runtime polymorphism.
9#include "json.hpp"
11#include "cursor.hpp"
12#include "owning_builder.hpp" // OwningBuilder (the owning construction policy)
13#include "scan.hpp" // detail:: low-level scanners (shared with the struct reader)
14#include "simd.hpp"
16#include <charconv>
17#include <cstddef>
18#include <cstdint>
19#include <string>
20#include <string_view>
21#include <type_traits>
22#include <utility>
23#include <variant>
24#include <vector>
26namespace cheatah::parsers::json {
28namespace {
30// The low-level scanners live in scan.hpp (detail::), shared verbatim with the struct reader; pull
31// the ones the DOM grammar uses into this scope.
32/**
33 * Decode the raw (escaped) inner bytes of a JSON string (scan.hpp's detail::decode_escapes).
34 * @complexity O(|raw|). @alloc output growth (reserved once up front).
35 * @test CheatahParsersJson.ScanNumbersAndEscapes
36 */
37using detail::decode_escapes;
38/**
39 * Consume an exact literal like "true" if present, else leave the cursor put (detail::match).
40 * @complexity O(|literal|). @alloc none.
41 * @test CheatahParsersJson.ScanNumbersAndEscapes
42 */
43using detail::match;
44/**
45 * Scan a quoted string to its raw inner bytes + had-escapes flag (detail::scan_string).
46 * @complexity O(|string|) — SIMD, 32 bytes per step. @alloc none — the raw bytes are a view.
47 * @test CheatahParsersJson.ScanNumbersAndEscapes
48 */
49using detail::scan_string;
50/**
51 * Advance the cursor past JSON whitespace (detail::skip_ws over the SIMD skip).
52 * @complexity O(whitespace run). @alloc none.
53 * @test ParsersJsonDom.ParsesEveryScalarKind
54 */
55using detail::skip_ws;
57// Parse a JSON string straight into `out`. OwnsStrings is the builder's string policy: when false
58// (pooled/view path) an unescaped string is a zero-copy String<std::string_view> into the SOURCE
59// text; when true (owning path) it is COPIED into an owned String<std::string> so the Document is
60// self-contained and may outlive the source (e.g. the cache parses a temporary buffer). An ESCAPED
61// string is always decoded into owned storage regardless, since the decoded bytes have no source.
62// @complexity O(|string|) @alloc only for owned/escaped strings @test ParsersJsonDom.PooledParserYieldsViewsIntoSource
63template <bool OwnsStrings>
64bool parse_string(Cursor& c, Node& out) {
65 std::string_view raw;
66 bool esc = false;
67 if (!scan_string(c, raw, esc)) {
68 return false;
69 }
70 if (!esc) {
71 if constexpr (OwnsStrings) {
72 out.variant().emplace<String<std::string>>(std::string(raw)); // owned copy
73 } else {
74 out.variant().emplace<String<std::string_view>>(raw); // zero-copy view into source
75 }
76 return true;
77 }
78 std::string decoded;
79 if (!decode_escapes(raw, decoded)) {
80 return false;
81 }
82 out.variant().emplace<String<std::string>>(std::move(decoded)); // owned
83 return true;
86// Parse a JSON number into `out` (emplaced in place).
87// @complexity O(digits) @alloc none @test ParsersJsonDom.ParsesEveryScalarKind
88bool parse_number(Cursor& c, Node& out) {
89 double d = 0.0;
90 if (!detail::parse_arithmetic(c, d)) {
91 return false;
92 }
93 out.variant().emplace<Number>(d);
94 return true;
97// ---- serialization (re-escapes string contents) -----------------------------
99// Append `s` to `out` as a quoted JSON string, re-escaping specials and control bytes (\u00XX).
100// @complexity O(|s|) @alloc amortized `out` growth @test ParsersJsonDom.DumpReescapesStringsAndFormatsNumbers
101void dump_string(std::string_view s, std::string& out) {
102 static constexpr char kHex[] = "0123456789abcdef";
103 out.push_back('"');
104 for (const char ch : s) {
105 switch (ch) {
106 case '"': out.append("\\\""); break;
107 case '\\': out.append("\\\\"); break;
108 case '\b': out.append("\\b"); break;
109 case '\f': out.append("\\f"); break;
110 case '\n': out.append("\\n"); break;
111 case '\r': out.append("\\r"); break;
112 case '\t': out.append("\\t"); break;
113 default:
114 if (static_cast<unsigned char>(ch) < 0x20) {
115 out.append("\\u00");
116 out.push_back(kHex[(static_cast<unsigned char>(ch) >> 4) & 0xF]);
117 out.push_back(kHex[static_cast<unsigned char>(ch) & 0xF]);
118 } else {
119 out.push_back(ch);
120 }
121 }
122 }
123 out.push_back('"');
126// Serialize ITERATIVELY with an explicit stack of open containers — symmetric with the iterative
127// parser, so a document of any nesting depth dumps without exhausting the C++ call stack (the
128// parser accepts adversarially deep input; the serializer must survive it too).
129// @complexity O(nodes) @alloc the frame stack, O(depth) @test ParsersJsonDom.DepthCapAndDeepDumpRoundTrip
130void dump_to(const Node& root, std::string& out) {
131 // One open container being emitted: which kind, how many children are already written, and a
132 // span of its remaining children (exactly one of the spans is used, chosen by is_object).
133 struct Frame {
134 bool is_object;
135 std::size_t next;
136 std::span<const Node> elements;
137 std::span<const Member> members;
138 };
139 std::vector<Frame> stack;
140 const Node* value = &root;
142 for (;;) {
143 // (A) Emit one VALUE. Scalars are appended whole; a container appends its opener and pushes
144 // a frame, so its children are emitted by the loop below.
145 std::visit(
146 [&](const auto& tok) {
147 using T = std::decay_t<decltype(tok)>;
148 if constexpr (std::is_same_v<T, Null>) {
149 out.append("null");
150 } else if constexpr (std::is_same_v<T, Boolean>) {
151 out.append(tok.value() ? "true" : "false");
152 } else if constexpr (std::is_same_v<T, Number>) {
153 char buf[32];
154 const std::to_chars_result r = std::to_chars(buf, buf + sizeof buf, tok.value());
155 out.append(buf, r.ptr);
156 } else if constexpr (std::is_same_v<T, String<std::string_view>> ||
157 std::is_same_v<T, String<std::string>>) {
158 dump_string(tok.value(), out);
159 } else if constexpr (std::is_same_v<T, OwnedArray> || std::is_same_v<T, ArrayView>) {
160 out.push_back('[');
161 stack.push_back(Frame{.is_object = false,
162 .next = 0,
163 .elements = tok.value(),
164 .members = {}});
165 } else { // Object
166 out.push_back('{');
167 stack.push_back(Frame{.is_object = true,
168 .next = 0,
169 .elements = {},
170 .members = tok.value()});
171 }
172 },
173 value->variant());
175 // (B) Find the next value to emit: write separators/keys for the innermost open container,
176 // closing every container that has run out of children along the way.
177 value = nullptr;
178 while (!stack.empty() && value == nullptr) {
179 Frame& top = stack.back();
180 if (top.is_object) {
181 if (top.next == top.members.size()) {
182 out.push_back('}');
183 stack.pop_back();
184 continue; // this object is finished — keep ascending
185 }
186 if (top.next > 0) {
187 out.push_back(',');
188 }
189 const Member& m = top.members[top.next++];
190 dump_string(to_view(m.first), out); // the key (a string Node)
191 out.push_back(':');
192 value = &m.second;
193 } else {
194 if (top.next == top.elements.size()) {
195 out.push_back(']');
196 stack.pop_back();
197 continue; // this array is finished — keep ascending
198 }
199 if (top.next > 0) {
200 out.push_back(',');
201 }
202 value = &top.elements[top.next++];
203 }
204 }
205 if (value == nullptr) {
206 return; // stack empty: the whole document has been emitted
207 }
208 }
211} // namespace
213std::string_view to_view(const Node& value) noexcept {
214 const Node::variant_type& v = value.variant();
215 if (const String<std::string_view>* view = std::get_if<String<std::string_view>>(&v)) {
216 return view->value();
217 }
218 if (const String<std::string>* owned = std::get_if<String<std::string>>(&v)) {
219 return owned->value();
220 }
221 return {};
224template <bool Validate>
225Document parse(std::string_view text, bool* ok) {
226 // A fresh Parser yields a self-contained OWNING Document (no pool references), so it is safe to
227 // return even though the Parser is destroyed here. Reuse a Parser (Parser::parse for the pooled
228 // view form, or Parser::parse_owning) to amortize allocation across many parses. Validate
229 // forwards straight through to the grammar (default true; <false> compiles the checks out).
230 Parser p;
231 return p.parse_owning<Validate>(text, ok);
233template Document parse<true>(std::string_view, bool*);
234template Document parse<false>(std::string_view, bool*);
236void dump(const Document& value, std::string& out) {
237 dump_to(value, out); // appends into the caller's (preallocated/reused) buffer
240std::string dump(const Document& value) {
241 std::string out;
242 dump_to(value, out);
243 return out;
246// ---- reusable Parser: ONE iterative grammar, two Builders -------------------
247//
248// The recursion is unrolled into a loop over an explicit frame_stack_: each open container is a
249// Frame, the Builder (driven as a stack machine: begin/add/finish) holds the partial container, and
250// completed values "bubble up" to their parent. Nesting depth therefore costs heap, not C++ call
251// frames — no stack overflow on adversarially deep input. The grammar is parameterized on (1) a
252// compile-time `bool Validate` and (2) a Builder policy (PoolBuilder -> span VIEWS into a reused
253// pool, or OwningBuilder -> self-contained owned vectors). Every bounds/structure check sits inside
254// `if constexpr (Validate)`, so with Validate=false the standard DISCARDS those statements at
255// compile time (validation gone from the binary, not merely optimized away); trusted input is
256// assumed well-formed, so the elided checks never fire and the result is identical (malformed input
257// under Validate=false is UB). Instantiated for both modes and both builders below.
259// Maximum container-nesting depth accepted under validation. The PARSE is iterative (frame_stack_),
260// but the OWNING result is a recursively-nested vector<Node> tree whose compiler-generated destructor
261// recurses one C++ frame per level — so genuinely-deep (but syntactically valid) input like
262// `[[[…]]]` would overflow the stack on scope-exit. Capping nesting during the parse transitively
263// bounds the tree depth, and thus that destructor (and any recursive accessor). 1000 is far deeper
264// than any real document and far below where the destructor overflows. Trusted-input (Validate=false)
265// callers skip the check, matching the module's "no validation on the trusted fast path" contract.
266inline constexpr std::size_t kMaxParseDepth = 1000;
268template <bool Validate, class Builder>
269bool Parser::parse_value(Cursor& c, Node& out, Builder& b) {
270 frame_stack_.clear();
271 Node value; // the most-recently-completed value, bubbling up toward its parent / the root
273 for (;;) {
274 // (A) Inside an object, the next child is a member: read its "key" and the ':' first.
275 if (!frame_stack_.empty() && frame_stack_.back().is_object) {
276 skip_ws(c);
277 if constexpr (Validate) {
278 if (c.it == c.end || *c.it != '"') {
279 return false; // key must be a string
280 }
281 }
282 if (!parse_string<Builder::owns_strings>(c, frame_stack_.back().key)) {
283 return false;
284 }
285 skip_ws(c);
286 if constexpr (Validate) {
287 if (c.it == c.end || *c.it != ':') {
288 return false;
289 }
290 }
291 ++c.it; // skip ':'
292 }
294 // (B) Read one value. A scalar fills `value`; an opening '['/'{' begins a container and (if
295 // non-empty) pushes a frame and loops back to read its first child. An empty container
296 // is finished immediately and falls through to (C).
297 skip_ws(c);
298 if constexpr (Validate) {
299 if (c.it == c.end) {
300 return false;
301 }
302 }
303 bool opened = false;
304 switch (*c.it) {
305 case '[':
306 ++c.it;
307 b.begin_array();
308 skip_ws(c);
309 if constexpr (Validate) {
310 if (c.it == c.end) {
311 return false; // unterminated right after '['
312 }
313 }
314 if (*c.it == ']') {
315 ++c.it;
316 value = b.finish_array(); // empty array
317 } else {
318 if constexpr (Validate) {
319 if (frame_stack_.size() >= kMaxParseDepth) return false; // nesting too deep
320 }
321 frame_stack_.push_back(Frame{false, Node{}});
322 opened = true;
323 }
324 break;
325 case '{':
326 ++c.it;
327 b.begin_object();
328 skip_ws(c);
329 if constexpr (Validate) {
330 if (c.it == c.end) {
331 return false; // unterminated right after '{'
332 }
333 }
334 if (*c.it == '}') {
335 ++c.it;
336 value = b.finish_object(); // empty object
337 } else {
338 if constexpr (Validate) {
339 if (frame_stack_.size() >= kMaxParseDepth) return false; // nesting too deep
340 }
341 frame_stack_.push_back(Frame{true, Node{}});
342 opened = true;
343 }
344 break;
345 case '"':
346 if (!parse_string<Builder::owns_strings>(c, value)) {
347 return false;
348 }
349 break;
350 case 't':
351 if (!match(c, "true")) {
352 return false;
353 }
354 value.variant().emplace<Boolean>(true);
355 break;
356 case 'f':
357 if (!match(c, "false")) {
358 return false;
359 }
360 value.variant().emplace<Boolean>(false);
361 break;
362 case 'n':
363 if (!match(c, "null")) {
364 return false;
365 }
366 value.variant().emplace<Null>();
367 break;
368 default:
369 if (!parse_number(c, value)) { // digit or '-'
370 return false;
371 }
372 break;
373 }
374 if (opened) {
375 continue; // a non-empty container was opened: loop back to read its first child/key
376 }
378 // (C) `value` is complete. Attach it to the enclosing container, then ascend through every
379 // container that closes here (each closed container becomes the next `value`).
380 for (;;) {
381 if (frame_stack_.empty()) {
382 out = std::move(value); // `value` was the whole document
383 return true;
384 }
385 Frame& top = frame_stack_.back();
386 if (top.is_object) {
387 b.add_member(Member{std::move(top.key), std::move(value)});
388 } else {
389 b.add_element(std::move(value));
390 }
391 skip_ws(c);
392 if constexpr (Validate) {
393 if (c.it == c.end) {
394 return false;
395 }
396 }
397 const char sep = *c.it++;
398 const char closer = top.is_object ? '}' : ']';
399 if (sep == ',') {
400 break; // more children: loop back to (A)/(B)
401 }
402 if (sep == closer) {
403 value = top.is_object ? b.finish_object() : b.finish_array();
404 frame_stack_.pop_back();
405 continue; // ascend: the closed container is now `value` for ITS parent
406 }
407 return false; // expected ',' or the closing bracket/brace
408 }
409 }
412// In the Validate=false instantiations `ok` is never referenced (the whole else branch below omits
413// it), so it is [[maybe_unused]]; the unchecked binary contains no *ok store at all.
414template <bool Validate>
415Document Parser::parse(std::string_view text, [[maybe_unused]] bool* ok) {
416 pool_.reset(text.size()); // reuse capacity; reserve a safe upper bound so spans never dangle
418 Cursor c{text.data(), text.data() + text.size()};
419 Node root; // default-constructed to null
420 if constexpr (Validate) {
421 bool good = parse_value<true>(c, root, pool_); // ArrayView/ObjectView into the reused pool
422 if (good) {
423 skip_ws(c);
424 good = (c.it == c.end); // reject trailing junk
425 }
426 if (!good) {
427 root.variant().emplace<Null>();
428 }
429 if (ok != nullptr) {
430 *ok = good;
431 }
432 } else {
433 // Trusted input: parse with NO validation — no bounds/structure checks, no trailing-junk
434 // check, and `ok` is not touched (an unchecked parse has no validity to report; malformed
435 // input is undefined behavior, not a reported error).
436 parse_value<false>(c, root, pool_);
437 }
438 return root;
441template <bool Validate>
442Document Parser::parse_owning(std::string_view text, [[maybe_unused]] bool* ok) {
443 Cursor c{text.data(), text.data() + text.size()};
444 Node root; // default-constructed to null
445 OwningBuilder owning; // local vectors -> OwnedArray/OwnedObject (no references into this Parser)
446 if constexpr (Validate) {
447 bool good = parse_value<true>(c, root, owning);
448 if (good) {
449 skip_ws(c);
450 good = (c.it == c.end); // reject trailing junk
451 }
452 if (!good) {
453 root.variant().emplace<Null>();
454 }
455 if (ok != nullptr) {
456 *ok = good;
457 }
458 } else {
459 parse_value<false>(c, root, owning); // trusted input: no validation, `ok` left untouched
460 }
461 return root;
464// Instantiate both validation modes of each public entry point (the private grammar they call is
465// implicitly instantiated for both Builders along with them). parse<true>/parse_owning<true> are
466// the default; the <false> forms compile with all validation `if constexpr`-stripped.
467template Document Parser::parse<true>(std::string_view, bool*);
468template Document Parser::parse<false>(std::string_view, bool*);
469template Document Parser::parse_owning<true>(std::string_view, bool*);
470template Document Parser::parse_owning<false>(std::string_view, bool*);
472std::string_view Parser::dump(const Document& value) {
473 dump_buf_.clear(); // reuse the buffer's capacity across calls (no realloc once warm)
474 dump_to(value, dump_buf_);
475 return dump_buf_; // valid until the next dump() on this Parser
478} // namespace cheatah::parsers::json