cheatah
Source BigBrain
Source

stdlib/parsers/json/scan.hpp

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#pragma once
5// cheatah::parsers::json::detail — the low-level JSON scanners, header-only so BOTH the dynamic DOM
6// parser (json.cpp) and the static struct reader (read.hpp) share exactly one implementation. These
7// operate on a Cursor and never allocate except where noted (decode_escapes / the caller's string).
8// SIMD whitespace/string scanning comes from simd.hpp.
10#include <charconv>
11#include <cstddef>
12#include <cstdint>
13#include <limits>
14#include <string>
15#include <string_view>
16#include <type_traits>
18#include "cursor.hpp"
19#include "simd.hpp"
21#if !defined(__cpp_lib_to_chars)
22# include <cstdlib> // strtod / strtof / strtold — see from_chars_fp
23#endif
25namespace cheatah::parsers::json::detail {
27// Advance the cursor past JSON whitespace (SIMD-accelerated; see simd.hpp).
28// @complexity O(whitespace run) @alloc none @test Json.ParseObject
29inline void skip_ws(Cursor& c) noexcept {
30 c.it = simd::skip_whitespace(c.it, c.end);
33// Consume the exact literal `lit` (e.g. "true") if present, else leave the cursor put.
34// @complexity O(|lit|) @alloc none @test Json.ParseObject
35inline bool match(Cursor& c, std::string_view lit) noexcept {
36 if (static_cast<std::size_t>(c.end - c.it) < lit.size()) {
37 return false;
38 }
39 if (std::string_view(c.it, lit.size()) != lit) {
40 return false;
41 }
42 c.it += lit.size();
43 return true;
46// ---- string scanning + escape decoding --------------------------------------
48// Append the UTF-8 encoding of code point `cp` (1..4 bytes) to `out`.
49// @complexity O(1) @alloc amortized growth of `out` @test JsonRead.Strings
50inline void append_utf8(std::uint32_t cp, std::string& out) {
51 if (cp <= 0x7F) {
52 out.push_back(static_cast<char>(cp));
53 } else if (cp <= 0x7FF) {
54 out.push_back(static_cast<char>(0xC0 | (cp >> 6)));
55 out.push_back(static_cast<char>(0x80 | (cp & 0x3F)));
56 } else if (cp <= 0xFFFF) {
57 out.push_back(static_cast<char>(0xE0 | (cp >> 12)));
58 out.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3F)));
59 out.push_back(static_cast<char>(0x80 | (cp & 0x3F)));
60 } else {
61 out.push_back(static_cast<char>(0xF0 | (cp >> 18)));
62 out.push_back(static_cast<char>(0x80 | ((cp >> 12) & 0x3F)));
63 out.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3F)));
64 out.push_back(static_cast<char>(0x80 | (cp & 0x3F)));
65 }
68// Read 4 hex digits at raw[i..i+4) into cp.
69// @complexity O(1) @alloc none @test JsonRead.Strings
70inline bool hex4(std::string_view raw, std::size_t i, std::uint32_t& cp) {
71 if (i + 4 > raw.size()) {
72 return false;
73 }
74 std::uint32_t v = 0;
75 for (std::size_t k = 0; k < 4; ++k) {
76 const char ch = raw[i + k];
77 v <<= 4;
78 if (ch >= '0' && ch <= '9') {
79 v |= static_cast<std::uint32_t>(ch - '0');
80 } else if (ch >= 'a' && ch <= 'f') {
81 v |= static_cast<std::uint32_t>(ch - 'a' + 10);
82 } else if (ch >= 'A' && ch <= 'F') {
83 v |= static_cast<std::uint32_t>(ch - 'A' + 10);
84 } else {
85 return false;
86 }
87 }
88 cp = v;
89 return true;
92// Decode the raw (escaped) inner bytes of a JSON string into `out`. Ordinary bytes between escapes
93// are copied in BULK (find the next backslash, append the whole run) rather than one at a time —
94// most of a string is non-escape, so this is a few memcpy-sized appends instead of N push_backs.
95// @complexity O(|raw|) @alloc `out` growth (reserved once up front) @test JsonRead.Strings
96inline bool decode_escapes(std::string_view raw, std::string& out) {
97 out.clear();
98 out.reserve(raw.size());
99 std::size_t i = 0;
100 while (i < raw.size()) {
101 const std::size_t bs = raw.find('\\', i); // next escape, or npos
102 const std::size_t run_end = (bs == std::string_view::npos) ? raw.size() : bs;
103 out.append(raw.data() + i, run_end - i); // bulk-copy the ordinary run
104 if (bs == std::string_view::npos) {
105 return true;
106 }
107 i = bs + 1; // step onto the escape selector
108 if (i >= raw.size()) {
109 return false;
110 }
111 switch (raw[i++]) { // consume the selector; i now points past it
112 case '"': out.push_back('"'); break;
113 case '\\': out.push_back('\\'); break;
114 case '/': out.push_back('/'); break;
115 case 'b': out.push_back('\b'); break;
116 case 'f': out.push_back('\f'); break;
117 case 'n': out.push_back('\n'); break;
118 case 'r': out.push_back('\r'); break;
119 case 't': out.push_back('\t'); break;
120 case 'u': {
121 std::uint32_t cp = 0;
122 if (!hex4(raw, i, cp)) { // the 4 hex digits at [i, i+4)
123 return false;
124 }
125 i += 4;
126 if (cp >= 0xD800 && cp <= 0xDBFF) { // high surrogate; expect a low surrogate \uXXXX
127 std::uint32_t lo = 0;
128 if (i + 1 >= raw.size() || raw[i] != '\\' || raw[i + 1] != 'u' ||
129 !hex4(raw, i + 2, lo) || lo < 0xDC00 || lo > 0xDFFF) {
130 return false;
131 }
132 i += 6;
133 cp = 0x10000 + ((cp - 0xD800) << 10) + (lo - 0xDC00);
134 }
135 append_utf8(cp, out);
136 break;
137 }
138 default:
139 return false;
140 }
141 }
142 return true;
145// Scan a "..." string: set `raw` to its inner bytes and `esc` to whether it had escapes;
146// on entry c.it is at the opening quote, on success c.it is past the closing quote.
147// @complexity O(|string|) (SIMD 32 bytes/step) @alloc none (raw is a view) @test Json.Strings
148inline bool scan_string(Cursor& c, std::string_view& raw, bool& esc) {
149 ++c.it; // skip opening quote
150 const char* const start = c.it;
151 esc = false;
152 while (c.it < c.end) {
153 // SIMD-jump over ordinary content straight to the next quote or backslash (see simd.hpp).
154 c.it = simd::find_quote_or_backslash(c.it, c.end);
155 if (c.it == c.end) {
156 break; // unterminated
157 }
158 if (*c.it == '"') {
159 raw = std::string_view(start, static_cast<std::size_t>(c.it - start));
160 ++c.it; // skip closing quote
161 return true;
162 }
163 esc = true; // a backslash: this string has escapes (decoded later)
164 if (c.end - c.it < 2) {
165 return false; // dangling escape at end of input (checked BEFORE advancing — a pointer
166 // more than one-past-the-end is undefined behavior, even unused)
167 }
168 c.it += 2; // skip escape + escaped char (so \" does not end the string)
169 }
170 return false; // unterminated
173// ---- scalars ----------------------------------------------------------------
175// Powers of ten 10^0 .. 10^22 — every one is EXACTLY representable as a double (5^22 < 2^53), which
176// is what makes the float fast path below correctly rounded.
177inline constexpr double kPow10[23] = {1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7,
178 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15,
179 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22};
181/**
182 * `std::from_chars` for a FLOATING-POINT type, on toolchains that have it — and an equivalent where
183 * they do not.
184 *
185 * The integral overloads are universal, but the floating-point ones are the last piece of
186 * `<charconv>` a standard library implements, and Apple's libc++ still ships them **deleted**: the
187 * call compiles to `error: call to deleted function 'from_chars'`, which is how the macOS build
188 * failed the first time CI ran it. `__cpp_lib_to_chars` is the feature-test macro that says both
189 * halves are present, so it is what selects the path — the same shape `ndarray.hpp` already uses
190 * for `__cpp_lib_execution`.
191 *
192 * The fallback is `strtod`, which needs a NUL-terminated string, so the numeric token is copied into
193 * a small stack buffer first. `strtod` is more permissive than `from_chars` (it accepts leading
194 * whitespace, a leading `+`, and hex floats), but that cannot matter here: every caller has already
195 * validated the token against the JSON grammar, so none of those forms can reach this function.
196 *
197 * @param first the first character of the number.
198 * @param last one past the last character the caller will allow it to consume.
199 * @param out receives the parsed value; untouched on failure.
200 * @param next receives one past the last character consumed.
201 * @return false when the text is not a number the type can hold.
202 * @complexity O(digits).
203 * @alloc none — the token is bounded and copied to the stack; an absurdly long literal is refused
204 * rather than allocated for.
205 * @test JsonRead.Scalars / JsonRead.BigAndSmallDoubles
206 */
207template <class T>
208inline bool from_chars_fp(const char* first, const char* last, T& out, const char*& next) {
209#if defined(__cpp_lib_to_chars)
210 const std::from_chars_result r = std::from_chars(first, last, out);
211 if (r.ec != std::errc()) {
212 return false;
213 }
214 next = r.ptr;
215 return true;
216#else
217 // The longest token worth honouring. A correctly-rounded double needs at most ~17 significant
218 // digits; 512 leaves room for absurd-but-legal padding and still fits comfortably on the stack.
219 char buf[512];
220 const char* p = first;
221 while (p != last && (static_cast<unsigned>(*p - '0') <= 9u || *p == '-' || *p == '+' ||
222 *p == '.' || *p == 'e' || *p == 'E')) {
223 ++p;
224 }
225 const std::size_t n = static_cast<std::size_t>(p - first);
226 if (n == 0 || n >= sizeof buf) {
227 return false;
228 }
229 for (std::size_t i = 0; i < n; ++i) {
230 buf[i] = first[i];
231 }
232 buf[n] = '\0';
234 char* stop = nullptr;
235 T value;
236 if constexpr (std::is_same_v<T, float>) {
237 value = std::strtof(buf, &stop);
238 } else if constexpr (std::is_same_v<T, long double>) {
239 value = std::strtold(buf, &stop);
240 } else {
241 value = static_cast<T>(std::strtod(buf, &stop));
242 }
243 if (stop == buf) {
244 return false; // consumed nothing: not a number
245 }
246 out = value;
247 next = first + static_cast<std::size_t>(stop - buf);
248 return true;
249#endif
252// Parse a JSON double the fast way (Clinger): accumulate the digits into an integer mantissa, then
253// scale by one power of ten. When the mantissa fits in 53 bits AND the scale is within ±22, both
254// are exact doubles, so the single multiply/divide rounds once — bit-identical to std::from_chars
255// but without its general-format machinery. Anything outside that window (20+ digits, huge
256// exponents) falls back to std::from_chars for full correctness. Typical JSON numbers — prices,
257// quantities, timestamps — live entirely in the fast window.
258// @complexity O(digits) @alloc none @test JsonRead.NumbersEdge
259inline bool parse_double_fast(Cursor& c, double& out) {
260 const char* p = c.it;
261 const char* const end = c.end;
262 const bool negative = (p != end && *p == '-');
263 if (negative) {
264 ++p;
265 }
267 // Integer digits, then optional ".fraction" — both accumulate into ONE integer mantissa;
268 // each fraction digit just shifts the decimal exponent down by one.
269 const char* const int_start = p;
270 std::uint64_t mantissa = 0;
271 while (p != end && static_cast<unsigned>(*p - '0') <= 9u) {
272 mantissa = mantissa * 10u + static_cast<unsigned>(*p - '0');
273 ++p;
274 }
275 if (p == int_start) {
276 return false; // JSON requires at least one integer digit
277 }
278 std::int64_t digit_count = p - int_start;
279 int exp10 = 0;
280 if (p != end && *p == '.') {
281 ++p;
282 const char* const frac_start = p;
283 while (p != end && static_cast<unsigned>(*p - '0') <= 9u) {
284 mantissa = mantissa * 10u + static_cast<unsigned>(*p - '0');
285 ++p;
286 }
287 if (p == frac_start) {
288 return false; // JSON requires a digit after the decimal point
289 }
290 exp10 -= static_cast<int>(p - frac_start);
291 digit_count += p - frac_start;
292 }
294 // Optional exponent ("e"/"E", optional sign, digits).
295 if (p != end && (*p == 'e' || *p == 'E')) {
296 ++p;
297 bool exp_negative = false;
298 if (p != end && (*p == '+' || *p == '-')) {
299 exp_negative = (*p == '-');
300 ++p;
301 }
302 const char* const exp_start = p;
303 int e = 0;
304 while (p != end && static_cast<unsigned>(*p - '0') <= 9u) {
305 if (e < 10000) { // clamp; anything this large leaves the fast window anyway
306 e = e * 10 + (*p - '0');
307 }
308 ++p;
309 }
310 if (p == exp_start) {
311 return false; // 'e' with no digits
312 }
313 exp10 += exp_negative ? -e : e;
314 }
316 // The exactness window: <=19 digits means the mantissa accumulated without u64 overflow, the
317 // 2^53 test means it is an exact double, and |exp10| <= 22 means the scale is an exact double.
318 if (digit_count <= 19 && mantissa < (1ull << 53) && -22 <= exp10 && exp10 <= 22) {
319 double value = static_cast<double>(mantissa);
320 value = (exp10 >= 0) ? value * kPow10[exp10] : value / kPow10[-exp10];
321 out = negative ? -value : value;
322 c.it = p;
323 return true;
324 }
326 // Outside the window: the general parser handles arbitrary precision/exponents correctly.
327 const char* next = nullptr;
328 if (!from_chars_fp(c.it, end, out, next)) {
329 return false;
330 }
331 c.it = next;
332 return true;
335// Parse a JSON number into an arithmetic `out`. INTEGRAL types use a tight base-10 loop; double
336// uses the Clinger fast path above; other floating types (float, long double) defer to
337// std::from_chars. The integral loop is overflow-safe: a literal with more digits than the type can
338// ever hold exactly is re-parsed by std::from_chars, which detects out-of-range exactly; a negative
339// literal is rejected for unsigned fields rather than wrapped.
340// @complexity O(digits) @alloc none @test JsonRead.Scalars
341template <class T>
342inline bool parse_arithmetic(Cursor& c, T& out) {
343 if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) {
344 const char* p = c.it;
345 const bool negative = (p != c.end && *p == '-');
346 if (negative) {
347 if constexpr (std::is_unsigned_v<T>) {
348 return false; // a negative literal cannot fit an unsigned field
349 }
350 ++p;
351 }
352 if (p == c.end || *p < '0' || *p > '9') {
353 return false; // a number must have at least one digit
354 }
355 const char* const digit_start = p;
356 std::make_unsigned_t<T> magnitude = 0;
357 do {
358 magnitude = magnitude * 10 + static_cast<unsigned>(*p - '0');
359 ++p;
360 } while (p != c.end && *p >= '0' && *p <= '9');
361 if (p - digit_start > std::numeric_limits<T>::digits10) {
362 // More digits than T holds exactly: the accumulation above may have wrapped. Rare —
363 // re-parse with std::from_chars, which detects overflow exactly (and rejects it).
364 const std::from_chars_result r = std::from_chars(c.it, c.end, out);
365 if (r.ec != std::errc()) {
366 return false;
367 }
368 c.it = r.ptr;
369 return true;
370 }
371 c.it = p;
372 out = negative ? static_cast<T>(0) - static_cast<T>(magnitude) : static_cast<T>(magnitude);
373 return true;
374 } else if constexpr (std::is_same_v<T, double>) {
375 return parse_double_fast(c, out);
376 } else {
377 const char* next = nullptr;
378 if (!from_chars_fp(c.it, c.end, out, next)) {
379 return false;
380 }
381 c.it = next;
382 return true;
383 }
386// ---- skip an unknown value (iterative; depth-counted, so it cannot be stack-overflowed) ---------
387//
388// Consume exactly one complete JSON value (any shape) without storing it — used by the struct
389// reader to discard keys not present in the schema. Strings are skipped whole (so braces inside
390// them never miscount); containers are balanced with a depth counter rather than recursion, so an
391// adversarially deep unknown value costs O(depth) iterations and O(1) stack.
392// @complexity O(skipped bytes) @alloc none @test JsonRead.UnknownKeys
393inline bool skip_value(Cursor& c) {
394 std::size_t depth = 0;
395 do {
396 skip_ws(c);
397 if (c.it == c.end) {
398 return false;
399 }
400 switch (*c.it) {
401 case '{':
402 case '[':
403 ++c.it;
404 ++depth;
405 break;
406 case '}':
407 case ']':
408 if (depth == 0) {
409 return false;
410 }
411 ++c.it;
412 --depth;
413 break;
414 case '"': {
415 std::string_view raw;
416 bool esc = false;
417 if (!scan_string(c, raw, esc)) {
418 return false;
419 }
420 break;
421 }
422 case ',':
423 case ':':
424 if (depth == 0) {
425 return false; // stray punctuation is not a value
426 }
427 ++c.it; // structural punctuation inside a container we're skipping
428 break;
429 case 't':
430 if (!match(c, "true")) return false;
431 break;
432 case 'f':
433 if (!match(c, "false")) return false;
434 break;
435 case 'n':
436 if (!match(c, "null")) return false;
437 break;
438 default: {
439 double scratch = 0.0; // value discarded; we only need to advance past the number
440 if (!parse_arithmetic(c, scratch)) {
441 return false;
442 }
443 break;
444 }
445 }
446 } while (depth > 0);
447 return true;
450} // namespace cheatah::parsers::json::detail