Something went wrong. Try again.
fork of gitlab.com/devnw/zig/json for zig 0.17
Something went wrong. Try again.
23 kB · 559 lines
Zig
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560// SPDX-License-Identifier: Apache-2.0// Copyright (c) 2024-2025 CodePros
//! Normalized Base-10 Decimal Number Representation//!//! Provides exact decimal arithmetic without IEEE floating point rounding.//! Numbers are stored as: sign * digits * 10^exp10
const std = @import("std");const json = @import("json.zig");
const Number = json.Number;
/// Saturation bound for the decimal exponent.////// JSON numbers whose magnitude exceeds ~10^308 are not representable as an/// f64 anyway, so there is no information lost by clamping the accumulated/// exponent to this sentinel. Clamping (rather than overflowing an `i32`)/// guarantees `parseNumber` never panics on adversarial input such as/// `"1e99999999999"`. The original text is preserved verbatim in/// `Number.lexeme`, so float conversion and re-serialization are unaffected.////// The value is kept far below `std.math.maxInt(i32)` so downstream code that/// adds the exponent to a digit count (e.g. `compare`) cannot overflow.const EXP_SATURATE: i32 = 1_000_000_000;
/// Saturating helper: append a decimal digit to `acc`, clamping at/// `EXP_SATURATE` so the running exponent can never overflow `i32`.fn accumExp(acc: i32, digit: u8) i32 { if (acc >= EXP_SATURATE) return EXP_SATURATE; const scaled = acc *| 10; const next = scaled +| @as(i32, digit - '0'); return if (next >= EXP_SATURATE) EXP_SATURATE else next;}
/// Parse a number lexeme into normalized formpub fn parseNumber(lexeme: []const u8, a: std.mem.Allocator) !Number { var sign: i8 = 1; var pos: usize = 0;
// Handle sign if (lexeme.len > 0 and lexeme[0] == '-') { sign = -1; pos = 1; }
// Parse integer part const int_start = pos; var int_end = pos; while (int_end < lexeme.len and lexeme[int_end] >= '0' and lexeme[int_end] <= '9') { int_end += 1; }
// Parse fractional part var frac_digits: usize = 0; if (int_end < lexeme.len and lexeme[int_end] == '.') { pos = int_end + 1; while (pos < lexeme.len and lexeme[pos] >= '0' and lexeme[pos] <= '9') { pos += 1; frac_digits += 1; } } else { pos = int_end; }
// Parse exponent var exp10: i32 = 0; if (pos < lexeme.len and (lexeme[pos] == 'e' or lexeme[pos] == 'E')) { pos += 1; var exp_sign: i32 = 1; if (pos < lexeme.len and lexeme[pos] == '+') { pos += 1; } else if (pos < lexeme.len and lexeme[pos] == '-') { exp_sign = -1; pos += 1; }
var exp_val: i32 = 0; while (pos < lexeme.len and lexeme[pos] >= '0' and lexeme[pos] <= '9') { // Saturating accumulation: an overly long exponent (e.g. // "1e99999999999") clamps at EXP_SATURATE instead of overflowing // i32 and panicking. The number is far outside f64 range either // way, and the verbatim lexeme is retained for serialization. exp_val = accumExp(exp_val, lexeme[pos]); pos += 1; } exp10 = exp_sign * exp_val; }
// Adjust exponent for fractional digits (saturating: a pathologically long // fractional part cannot drive exp10 below i32's range). exp10 -|= std.math.lossyCast(i32, frac_digits);
// Build digit string (integer + fractional parts) var digits_buf: std.ArrayList(u8) = .empty; errdefer digits_buf.deinit(a);
for (lexeme[int_start..int_end]) |c| { try digits_buf.append(a, c); }
if (int_end < lexeme.len and lexeme[int_end] == '.') { for (lexeme[int_end + 1 ..][0..frac_digits]) |c| { try digits_buf.append(a, c); } }
// Normalize: strip leading zeros (keep at least one digit). // Note: leading zeros don't affect the exponent. // // Count the run once and drop it with a single shift, rather than calling // orderedRemove(0) per zero (which memmoves the whole buffer each time and // is O(n^2) for long leading-zero runs). if (digits_buf.items.len > 1) { var lead: usize = 0; const max_strip = digits_buf.items.len - 1; // keep at least one digit while (lead < max_strip and digits_buf.items[lead] == '0') { lead += 1; } if (lead > 0) { digits_buf.replaceRangeAssumeCapacity(0, lead, &[_]u8{}); } }
// Normalize: strip trailing zeros while (digits_buf.items.len > 1 and digits_buf.items[digits_buf.items.len - 1] == '0') { _ = digits_buf.pop(); exp10 += 1; }
// Special case: zero if (digits_buf.items.len == 1 and digits_buf.items[0] == '0') { sign = 1; exp10 = 0; }
return .{ .lexeme = lexeme, .sign = sign, .digits = try digits_buf.toOwnedSlice(a), .exp10 = exp10, };}
/// Check if a number represents an integer (no fractional part)pub fn isInteger(n: Number) bool { if (n.exp10 >= 0) return true;
const neg_exp: usize = @intCast(-n.exp10); if (neg_exp > n.digits.len) return false;
// Check that trailing digits (fractional part) are all zeros return allZeros(n.digits[n.digits.len - neg_exp ..]);}
fn allZeros(s: []const u8) bool { for (s) |c| { if (c != '0') return false; } return true;}
/// Compare two numbers: returns -1 if a < b, 0 if a == b, 1 if a > bpub fn compare(a: Number, b: Number) i32 { // Handle zeros const a_zero = a.digits.len == 1 and a.digits[0] == '0'; const b_zero = b.digits.len == 1 and b.digits[0] == '0';
if (a_zero and b_zero) return 0; if (a_zero) return if (b.sign == -1) 1 else -1; if (b_zero) return if (a.sign == -1) -1 else 1;
// Different signs if (a.sign != b.sign) { return if (a.sign > b.sign) 1 else -1; }
const sign_mult: i32 = a.sign;
// Compare magnitudes (number of digits before decimal point) const a_mag: i64 = @as(i64, @intCast(a.digits.len)) + a.exp10; const b_mag: i64 = @as(i64, @intCast(b.digits.len)) + b.exp10;
if (a_mag != b_mag) { return if (a_mag > b_mag) sign_mult else -sign_mult; }
// Compare digit by digit const min_len = @min(a.digits.len, b.digits.len); for (a.digits[0..min_len], b.digits[0..min_len]) |ad, bd| { if (ad != bd) { return if (ad > bd) sign_mult else -sign_mult; } }
// Longer number wins if (a.digits.len != b.digits.len) { return if (a.digits.len > b.digits.len) sign_mult else -sign_mult; }
return 0;}
/// Check if n is a multiple of div (n mod div == 0)pub fn isMultipleOf(n: Number, div: Number) bool { // Division by zero if (div.digits.len == 1 and div.digits[0] == '0') return false;
// Zero is multiple of everything if (n.digits.len == 1 and n.digits[0] == '0') return true;
const n_exp = n.exp10; const d_exp = div.exp10;
// If n has fewer fractional digits than div, it can't be a multiple if (n_exp < d_exp) return false;
// exp_diff is the number of trailing zeros we would need to append to // n.digits to scale it up to an integer in div's units. It can be enormous // (n_exp/d_exp are exponents up to EXP_SATURATE), so we MUST NOT // materialize that many digits -- doing so was a memory/CPU DoS (a JSON // Schema `multipleOf` with a large exponent could force ~10^9 appends on // std.heap.page_allocator, both an unbounded allocation and an unbounded // loop). Instead we fold the scaling into modular arithmetic: appending one // '0' multiplies the running remainder by 10 (mod div_val), so appending k // zeros multiplies by 10^k (mod div_val), which we evaluate in O(log k) via // binary exponentiation. The result is exact for every divisor that fits in // a u64 -- which covers every divisor that the rest of this module can // already mod against (bigIntMod historically used the same u64 path). const exp_diff: i64 = @as(i64, n_exp) - @as(i64, d_exp);
const div_val = stringToU64(div.digits) orelse { // Divisor does not fit in u64. The previous implementation also could // not handle this (stringToU64 silently overflowed), so this case never // produced a correct answer before. Bail to a safe definite `false` // rather than risk an unbounded computation; no existing caller hits // this path (schema multipleOf divisors are small). return false; }; if (div_val == 0) return false;
// remainder of n.digits (mod div_val), computed without overflow. var remainder: u64 = stringToU64Mod(n.digits, div_val);
if (exp_diff > 0) { // exp_diff is bounded by ~2 * EXP_SATURATE (it derives from clamped // exponents), so it fits in u64. modPow10 is logarithmic in exp_diff, // so even the maximum value costs only ~31 iterations -- no DoS. // u128 intermediate: remainder and modPow10 result are both < div_val // (which is u64), so their product can reach ~2^128 -- widen before the // `% div_val` so the multiply can't overflow. The reduced result is // < div_val <= u64-max, so the @intCast back to u64 is safe. const scaled = @as(u128, remainder) * modPow10(@intCast(exp_diff), div_val); remainder = @as(u64, @intCast(scaled % div_val)); }
return remainder == 0;}
/// Compute 10^exp (mod m) using binary exponentiation. O(log exp).fn modPow10(exp: u64, m: u64) u64 { if (m == 1) return 0; var result: u64 = 1 % m; var base: u64 = 10 % m; var e = exp; while (e > 0) { if (e & 1 == 1) { // u128 intermediate: result and base are both < m (which is u64), // so their product can approach 2^128. Widen before the `% m` so // the multiply can't overflow; the reduced value fits back in u64. result = @as(u64, @intCast(@as(u128, result) * base % m)); } e >>= 1; base = @as(u64, @intCast(@as(u128, base) * base % m)); } return result;}
/// Reduce the decimal string `s` modulo `m` without overflow.fn stringToU64Mod(s: []const u8, m: u64) u64 { if (m == 0) return 0; var remainder: u64 = 0; for (s) |c| { // u128 intermediate: remainder is < m (which is u64), so `remainder * 10` // can overflow u64. Widen before the `% m`; the reduced value fits in u64. const next = @as(u128, remainder) * 10 + (c - '0'); remainder = @as(u64, @intCast(next % m)); } return remainder;}
/// Parse a decimal string to u64, returning null on overflow.fn stringToU64(s: []const u8) ?u64 { var result: u64 = 0; for (s) |c| { const mul = std.math.mul(u64, result, 10) catch return null; result = std.math.add(u64, mul, c - '0') catch return null; } return result;}
test "parse number - integer" { const n = try parseNumber("123", std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqual(@as(i8, 1), n.sign); try std.testing.expectEqualStrings("123", n.digits); try std.testing.expectEqual(@as(i32, 0), n.exp10);}
test "parse number - negative" { const n = try parseNumber("-42", std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqual(@as(i8, -1), n.sign); try std.testing.expectEqualStrings("42", n.digits);}
test "parse number - decimal" { const n = try parseNumber("3.14", std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqualStrings("314", n.digits); try std.testing.expectEqual(@as(i32, -2), n.exp10);}
test "parse number - exponent" { const n = try parseNumber("1e10", std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqualStrings("1", n.digits); try std.testing.expectEqual(@as(i32, 10), n.exp10);}
test "parse number - zero" { const n = try parseNumber("0", std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqual(@as(i8, 1), n.sign); // Normalized to positive try std.testing.expectEqualStrings("0", n.digits); try std.testing.expectEqual(@as(i32, 0), n.exp10);}
test "isInteger" { const int_num = try parseNumber("42", std.testing.allocator); defer std.testing.allocator.free(int_num.digits); try std.testing.expect(isInteger(int_num));
const float_num = try parseNumber("3.14", std.testing.allocator); defer std.testing.allocator.free(float_num.digits); try std.testing.expect(!isInteger(float_num));
const whole_float = try parseNumber("3.0", std.testing.allocator); defer std.testing.allocator.free(whole_float.digits); try std.testing.expect(isInteger(whole_float));}
test "compare numbers" { const a = try parseNumber("100", std.testing.allocator); defer std.testing.allocator.free(a.digits); const b = try parseNumber("99", std.testing.allocator); defer std.testing.allocator.free(b.digits); try std.testing.expect(compare(a, b) > 0);
const c = try parseNumber("-5", std.testing.allocator); defer std.testing.allocator.free(c.digits); const d = try parseNumber("5", std.testing.allocator); defer std.testing.allocator.free(d.digits); try std.testing.expect(compare(c, d) < 0);}
test "isMultipleOf" { const n = try parseNumber("10", std.testing.allocator); defer std.testing.allocator.free(n.digits); const div = try parseNumber("5", std.testing.allocator); defer std.testing.allocator.free(div.digits); try std.testing.expect(isMultipleOf(n, div));
const n2 = try parseNumber("10", std.testing.allocator); defer std.testing.allocator.free(n2.digits); const div2 = try parseNumber("3", std.testing.allocator); defer std.testing.allocator.free(div2.digits); try std.testing.expect(!isMultipleOf(n2, div2));}
// ASR-001 (Critical): parsing a number with an enormous exponent must not panic// with "integer overflow". Previously `exp_val = exp_val * 10 + digit` overflowed// i32 in Debug/ReleaseSafe. The exponent now saturates and the original lexeme is// preserved verbatim, so parsing succeeds with a defined, round-trippable value.test "parse number - huge positive exponent does not overflow (ASR-001)" { const n = try parseNumber("1e99999999999", std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqual(@as(i8, 1), n.sign); try std.testing.expectEqualStrings("1", n.digits); // Exponent saturates instead of overflowing. try std.testing.expectEqual(EXP_SATURATE, n.exp10); // The verbatim lexeme is retained for serialization / float conversion. try std.testing.expectEqualStrings("1e99999999999", n.lexeme);}
test "parse number - huge negative exponent does not overflow (ASR-001)" { const n = try parseNumber("1e-99999999999", std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqualStrings("1", n.digits); // Negative saturation sentinel. try std.testing.expectEqual(-EXP_SATURATE, n.exp10); try std.testing.expectEqualStrings("1e-99999999999", n.lexeme);}
test "parse number - 400-digit exponent does not overflow (ASR-001)" { // Build "1e" followed by 400 '9' digits. var buf: [402]u8 = undefined; buf[0] = '1'; buf[1] = 'e'; @memset(buf[2..], '9'); const n = try parseNumber(&buf, std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqualStrings("1", n.digits); try std.testing.expectEqual(EXP_SATURATE, n.exp10);
// Also exercise the sign-bearing, fractional variant to cover the // frac-adjust saturation path. var buf2: [404]u8 = undefined; buf2[0] = '1'; buf2[1] = '.'; buf2[2] = '5'; buf2[3] = 'e'; @memset(buf2[4..], '9'); const n2 = try parseNumber(&buf2, std.testing.allocator); defer std.testing.allocator.free(n2.digits); try std.testing.expectEqualStrings("15", n2.digits); // exp from the huge exponent saturates, then the single frac digit nudges it // down by one (still effectively saturated, never overflowing). try std.testing.expectEqual(EXP_SATURATE - 1, n2.exp10);}
// ASR-001 end-to-end: the public `json.parse` entry point must not crash on a// huge exponent. Before the fix this panicked with "integer overflow"; now it// succeeds and yields a `.num` whose exponent is saturated and whose lexeme is// the original text (so it round-trips on re-serialization).test "parse public API - huge exponent does not crash (ASR-001 end-to-end)" { var err: json.ParseError = undefined; var doc = try json.parse(std.testing.allocator, "1e99999999999", .{}, &err); defer doc.deinit(); try std.testing.expect(doc.root == .num); try std.testing.expectEqual(EXP_SATURATE, doc.root.num.exp10); try std.testing.expectEqualStrings("1e99999999999", doc.root.num.lexeme);
var err2: json.ParseError = undefined; var doc2 = try json.parse(std.testing.allocator, "1e-99999999999", .{}, &err2); defer doc2.deinit(); try std.testing.expect(doc2.root == .num); try std.testing.expectEqual(-EXP_SATURATE, doc2.root.num.exp10);}
// PERF-008: a long run of leading zeros must be stripped in a single shift,// and behavior must be preserved exactly (a lone "0" is not stripped to empty).test "parse number - long leading-zero run (PERF-008)" { // "0000...0001" with 1000 leading zeros parses to digits "1", exp10 0. var buf: [1001]u8 = undefined; @memset(buf[0..1000], '0'); buf[1000] = '1'; const n = try parseNumber(&buf, std.testing.allocator); defer std.testing.allocator.free(n.digits); try std.testing.expectEqualStrings("1", n.digits); try std.testing.expectEqual(@as(i32, 0), n.exp10);
// A lone "0" stays "0" (not stripped to empty). const z = try parseNumber("0", std.testing.allocator); defer std.testing.allocator.free(z.digits); try std.testing.expectEqualStrings("0", z.digits);
// "000" normalizes to a single "0". const z3 = try parseNumber("000", std.testing.allocator); defer std.testing.allocator.free(z3.digits); try std.testing.expectEqualStrings("0", z3.digits);}
// ASR-008 / PERF-004: isMultipleOf on a value with a very large positive exp10// must return promptly and correctly WITHOUT materializing ~10^9 digits.// Previously this appended one '0' per unit of exp_diff on page_allocator.test "isMultipleOf - huge exponent returns promptly and correctly (ASR-008/PERF-004)" { // n = 1e1000000000 (huge positive exp10 after saturation), div = 2. // 10^k is divisible by 2 for any k >= 1, so this must be true -- and must // be answered via modular arithmetic, not a 10^9-element allocation. const big = try parseNumber("1e1000000000", std.testing.allocator); defer std.testing.allocator.free(big.digits); const two = try parseNumber("2", std.testing.allocator); defer std.testing.allocator.free(two.digits); try std.testing.expect(isMultipleOf(big, two));
// 10^k is NOT divisible by 3 for any k, so this must be false. const three = try parseNumber("3", std.testing.allocator); defer std.testing.allocator.free(three.digits); try std.testing.expect(!isMultipleOf(big, three));
// Sanity: 7 * 10^k mod 7 == 0. const big7 = try parseNumber("7e1000000000", std.testing.allocator); defer std.testing.allocator.free(big7.digits); const seven = try parseNumber("7", std.testing.allocator); defer std.testing.allocator.free(seven.digits); try std.testing.expect(isMultipleOf(big7, seven));}
// Regression: the modular scaling must agree with the naive definition for// ordinary magnitudes where the old code path was also correct.test "isMultipleOf - exact modular scaling for small exponents" { // 100 is a multiple of 25; 100 is not a multiple of 7. const hundred = try parseNumber("1e2", std.testing.allocator); defer std.testing.allocator.free(hundred.digits); const twentyfive = try parseNumber("25", std.testing.allocator); defer std.testing.allocator.free(twentyfive.digits); try std.testing.expect(isMultipleOf(hundred, twentyfive));
const seven = try parseNumber("7", std.testing.allocator); defer std.testing.allocator.free(seven.digits); try std.testing.expect(!isMultipleOf(hundred, seven));
// 1000 is a multiple of 8 (1000 / 8 = 125). const thousand = try parseNumber("1000", std.testing.allocator); defer std.testing.allocator.free(thousand.digits); const eight = try parseNumber("8", std.testing.allocator); defer std.testing.allocator.free(eight.digits); try std.testing.expect(isMultipleOf(thousand, eight));}
// NASR-003 / NQUAL-001 (Critical): isMultipleOf's modular helpers must not// overflow when the divisor exceeds ~2^32. Both operands are attacker-controlled// JSON, so a `u64 * u64` multiply in modPow10/stringToU64Mod was a process-abort// ("integer overflow" at number.zig:266) in Debug and ReleaseSafe -- and a silent// wrap to a wrong boolean in ReleaseFast. Every modular multiply now uses a u128// intermediate so the product can't overflow before the `% m` reduces it.test "isMultipleOf - large u64 divisor does not overflow (NASR-003/NQUAL-001)" { const a = std.testing.allocator;
// The confirmed crash case: 19-significant-digit divisor (< 2^64 but > 2^32). // 10^40 mod 9999999999999999999 == 100, so 10^40 is NOT a multiple of it. const big = try parseNumber("1e40", a); defer a.free(big.digits); const huge_div = try parseNumber("9999999999999999999", a); defer a.free(huge_div.digits); // Must not panic. Result is defined and deterministic across repeated calls. const r1 = isMultipleOf(big, huge_div); const r2 = isMultipleOf(big, huge_div); try std.testing.expectEqual(r1, r2); try std.testing.expect(!r1); // 10^40 mod 9999999999999999999 == 100 != 0
// A ~10-digit prime > 2^32 against 1e64. 10^64 mod 9999999967 == 4679732603, // so this is NOT a multiple either -- but it must be answered without overflow. const e64 = try parseNumber("1e64", a); defer a.free(e64.digits); const prime = try parseNumber("9999999967", a); defer a.free(prime.digits); try std.testing.expect(!isMultipleOf(e64, prime));
// Correctness preserved for a true-multiple case: 9e30 (= 9 * 10^30) is a // multiple of 3. This exercises stringToU64Mod on the significand and the // modular scaling fold together with a small divisor. const nine_e30 = try parseNumber("9e30", a); defer a.free(nine_e30.digits); const three = try parseNumber("3", a); defer a.free(three.digits); try std.testing.expect(isMultipleOf(nine_e30, three));}