pub const MAX_DEPTH: usize = 32;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Validity {
Valid,
Illegal,
MaxDepthExceeded,
Partial,
BadParameter,
}
const fn is_space(c: u8) -> bool {
c == b' ' || c == b'\t' || c == b'\n' || c == b'\r'
}
const fn is_ascii(c: u8) -> bool {
c <= 0x7F
}
const fn is_cntrl(c: u8) -> bool {
is_ascii(c) && c < b' '
}
const fn is_digit(c: u8) -> bool {
c.is_ascii_digit()
}
const fn is_open_bracket(c: u8) -> bool {
c == b'{' || c == b'['
}
const fn is_close_bracket(c: u8) -> bool {
c == b'}' || c == b']'
}
const fn is_matching_bracket(open: u8, close: u8) -> bool {
open.wrapping_add(2) == close && is_open_bracket(open)
}
pub(crate) fn at(buf: &[u8], i: usize) -> Option<u8> {
buf.get(i).copied()
}
pub(crate) fn skip_space(buf: &[u8], start: &mut usize, max: usize) {
let mut i = *start;
while i < max {
match at(buf, i) {
Some(c) if is_space(c) => i = i.saturating_add(1),
_ => break,
}
}
*start = i;
}
const fn count_high_bits(c: u8) -> usize {
let mut n = c;
let mut i = 0usize;
while (n & 0x80) != 0 {
i = i.saturating_add(1);
n = (n & 0x7F) << 1;
}
i
}
const fn shortest_utf8(length: usize, value: u32) -> bool {
let (min, max) = match length {
2 => (1u32 << 7, (1u32 << 11) - 1),
3 => (1u32 << 11, (1u32 << 16) - 1),
_ => (1u32 << 16, 0x10_FFFF),
};
value >= min && value <= max && (value < 0xD800 || value > 0xDFFF)
}
#[inline(never)]
fn skip_utf8_multibyte(buf: &[u8], start: &mut usize, max: usize) -> bool {
let mut i = *start;
let Some(first) = at(buf, i) else {
return false;
};
if !(first > 0xC1 && first < 0xF5) {
return false;
}
let bit_count = count_high_bits(first);
let shift = 7usize.saturating_sub(bit_count);
let mut value = u32::from(first) & ((1u32 << shift).saturating_sub(1));
let mut j = bit_count.saturating_sub(1);
while j > 0 {
i = i.saturating_add(1);
if i >= max {
break;
}
let Some(c) = at(buf, i) else { break };
if (c & 0xC0) != 0x80 {
break;
}
value = (value << 6) | u32::from(c & 0x3F);
j = j.saturating_sub(1);
}
if j == 0 && shortest_utf8(bit_count, value) {
*start = i.saturating_add(1);
return true;
}
false
}
fn skip_utf8(buf: &[u8], start: &mut usize, max: usize) -> bool {
if *start >= max {
return false;
}
match at(buf, *start) {
Some(c) if is_ascii(c) => {
*start = start.saturating_add(1);
true
}
Some(_) => skip_utf8_multibyte(buf, start, max),
None => false,
}
}
const NOT_A_HEX_CHAR: u8 = 0x10;
const fn hex_value(c: u8) -> u8 {
match c {
b'a'..=b'f' => c.saturating_sub(b'a').saturating_add(10),
b'A'..=b'F' => c.saturating_sub(b'A').saturating_add(10),
b'0'..=b'9' => c.saturating_sub(b'0'),
_ => NOT_A_HEX_CHAR,
}
}
const fn build_hex() -> [u8; 256] {
let mut table = [NOT_A_HEX_CHAR; 256];
let mut c = 0usize;
while c < 256 {
#[allow(clippy::indexing_slicing)]
{
table[c] = hex_value(c as u8);
}
c = c.saturating_add(1);
}
table
}
static HEX: [u8; 256] = build_hex();
#[inline]
fn hex_to_int(c: u8) -> u8 {
match HEX.get(c as usize) {
Some(value) => *value,
None => NOT_A_HEX_CHAR,
}
}
fn skip_one_hex_escape(buf: &[u8], start: &mut usize, max: usize, out: &mut u16) -> bool {
let mut i = *start;
let end = i.saturating_add(6);
let mut value = 0u16;
if end > i
&& end < max
&& at(buf, i) == Some(b'\\')
&& at(buf, i.saturating_add(1)) == Some(b'u')
{
i = i.saturating_add(2);
let n0 = hex_to_int(at(buf, i).unwrap_or(0));
let n1 = hex_to_int(at(buf, i.wrapping_add(1)).unwrap_or(0));
let n2 = hex_to_int(at(buf, i.wrapping_add(2)).unwrap_or(0));
let n3 = hex_to_int(at(buf, i.wrapping_add(3)).unwrap_or(0));
if (n0 | n1 | n2 | n3) & NOT_A_HEX_CHAR == 0 {
value = (u16::from(n0) << 12)
| (u16::from(n1) << 8)
| (u16::from(n2) << 4)
| u16::from(n3);
i = end;
}
}
if i == end {
*out = value;
*start = i;
return true;
}
false
}
const fn is_high_surrogate(x: u16) -> bool {
x >= 0xD800 && x <= 0xDBFF
}
const fn is_low_surrogate(x: u16) -> bool {
x >= 0xDC00 && x <= 0xDFFF
}
fn skip_hex_escape(buf: &[u8], start: &mut usize, max: usize) -> bool {
let mut i = *start;
let mut value = 0u16;
let mut ret = false;
if skip_one_hex_escape(buf, &mut i, max, &mut value) {
if is_high_surrogate(value) {
if skip_one_hex_escape(buf, &mut i, max, &mut value) && is_low_surrogate(value) {
ret = true;
}
} else if is_low_surrogate(value) {
} else {
ret = true;
}
}
if ret {
*start = i;
}
ret
}
#[inline(never)]
fn skip_escape(buf: &[u8], start: &mut usize, max: usize) -> bool {
let mut i = *start;
let mut ret = false;
if i < max.saturating_sub(1) && at(buf, i) == Some(b'\\') {
match at(buf, i.saturating_add(1)) {
Some(b'u') => ret = skip_hex_escape(buf, &mut i, max),
Some(b'"' | b'\\' | b'/' | b'b' | b'f' | b'n' | b'r' | b't') => {
i = i.saturating_add(2);
ret = true;
}
_ => {}
}
}
if ret {
*start = i;
}
ret
}
pub(crate) fn skip_string(buf: &[u8], start: &mut usize, max: usize) -> bool {
let mut i = *start;
let mut ret = false;
let max = max.min(buf.len());
if i < max && at(buf, i) == Some(b'"') {
i = i.saturating_add(1);
while i < max {
match at(buf, i) {
Some(b'"') => {
ret = true;
i = i.saturating_add(1);
break;
}
Some(b'\\') => {
if !skip_escape(buf, &mut i, max) {
break;
}
}
Some(c) if is_cntrl(c) => break,
Some(_) => {
if !skip_utf8(buf, &mut i, max) {
break;
}
}
None => break,
}
}
}
if ret {
*start = i;
}
ret
}
fn skip_literal(buf: &[u8], start: &mut usize, max: usize, literal: &[u8]) -> bool {
let from = *start;
if from >= max || literal.len() > max.saturating_sub(from) {
return false;
}
let end = from.saturating_add(literal.len());
let Some(slice) = buf.get(from..end) else {
return false;
};
if slice == literal {
*start = end;
return true;
}
false
}
pub(crate) const MAX_INDEX_VALUE: i32 = 0x7FFF_FFF7;
const MAX_FACTOR: i32 = MAX_INDEX_VALUE / 10;
pub(crate) fn skip_digits_value(buf: &[u8], start: &mut usize, max: usize) -> Option<i32> {
let from = *start;
let mut i = from;
let mut value: i32 = 0;
while i < max {
let Some(c) = at(buf, i) else { break };
if !is_digit(c) {
break;
}
if value > -1 {
let n = i32::from(hex_to_int(c));
value = if value <= MAX_FACTOR {
value.saturating_mul(10).saturating_add(n)
} else {
-1
};
}
i = i.saturating_add(1);
}
if i > from {
*start = i;
return Some(value);
}
None
}
fn skip_digits(buf: &[u8], start: &mut usize, max: usize) -> bool {
skip_digits_value(buf, start, max).is_some()
}
fn skip_decimals(buf: &[u8], start: &mut usize, max: usize) {
let mut i = *start;
if i < max && at(buf, i) == Some(b'.') {
i = i.saturating_add(1);
if skip_digits(buf, &mut i, max) {
*start = i;
}
}
}
fn skip_exponent(buf: &[u8], start: &mut usize, max: usize) {
let mut i = *start;
if i < max && matches!(at(buf, i), Some(b'e' | b'E')) {
i = i.saturating_add(1);
if i < max && matches!(at(buf, i), Some(b'-' | b'+')) {
i = i.saturating_add(1);
}
if skip_digits(buf, &mut i, max) {
*start = i;
}
}
}
#[inline(always)]
fn skip_number(buf: &[u8], start: &mut usize, max: usize) -> bool {
let max = max.min(buf.len());
let mut i = *start;
let mut ret = false;
if i < max && at(buf, i) == Some(b'-') {
i = i.saturating_add(1);
}
if i < max {
if at(buf, i) == Some(b'0') {
ret = true;
i = i.saturating_add(1);
} else {
ret = skip_digits(buf, &mut i, max);
}
}
if ret {
skip_decimals(buf, &mut i, max);
skip_exponent(buf, &mut i, max);
*start = i;
}
ret
}
pub(crate) fn skip_any_scalar(buf: &[u8], start: &mut usize, max: usize) -> bool {
any_scalar(buf, start, max)
}
#[inline(always)]
fn any_scalar(buf: &[u8], start: &mut usize, max: usize) -> bool {
match at(buf, *start) {
Some(b'"') => skip_string(buf, start, max),
Some(b't') => skip_literal(buf, start, max, b"true"),
Some(b'f') => skip_literal(buf, start, max, b"false"),
Some(b'n') => skip_literal(buf, start, max, b"null"),
Some(b'-' | b'0'..=b'9') => skip_number(buf, start, max),
_ => false,
}
}
pub(crate) fn skip_space_and_comma(buf: &[u8], start: &mut usize, max: usize) -> bool {
skip_space(buf, start, max);
let mut i = *start;
if i < max && at(buf, i) == Some(b',') {
i = i.saturating_add(1);
skip_space(buf, &mut i, max);
if i < max && !at(buf, i).is_some_and(is_close_bracket) {
*start = i;
return true;
}
}
false
}
#[inline(always)]
fn skip_array_scalars(buf: &[u8], start: &mut usize, max: usize) -> bool {
let max = max.min(buf.len());
let mut i = *start;
let mut ret = true;
while i < max {
if at(buf, i).is_some_and(is_open_bracket) {
break;
}
if !any_scalar(buf, &mut i, max) {
break;
}
if !skip_space_and_comma(buf, &mut i, max) {
if i >= max || at(buf, i) != Some(b']') {
ret = false;
}
break;
}
}
*start = i;
ret
}
#[inline(always)]
fn skip_object_scalars(buf: &[u8], start: &mut usize, max: usize) -> bool {
let max = max.min(buf.len());
let mut i = *start;
let mut ret = true;
while i < max {
if !skip_string(buf, &mut i, max) {
ret = false;
break;
}
skip_space(buf, &mut i, max);
if i < max && at(buf, i) != Some(b':') {
ret = false;
break;
}
i = i.saturating_add(1);
skip_space(buf, &mut i, max);
if i < max && at(buf, i).is_some_and(is_open_bracket) {
*start = i;
break;
}
if !any_scalar(buf, &mut i, max) {
ret = false;
break;
}
let comma = skip_space_and_comma(buf, &mut i, max);
*start = i;
if !comma {
break;
}
}
ret
}
#[inline(always)]
fn skip_scalars(buf: &[u8], start: &mut usize, max: usize, mode: u8) -> bool {
let max = max.min(buf.len());
skip_space(buf, start, max);
let i = *start;
if i >= max {
return true;
}
let Some(c) = at(buf, i) else { return true };
if mode == b'[' {
if c != b']' {
return skip_array_scalars(buf, start, max);
}
} else if c != b'}' {
return skip_object_scalars(buf, start, max);
}
true
}
pub(crate) fn skip_collection(buf: &[u8], start: &mut usize, max: usize) -> Validity {
let max = max.min(buf.len());
let mut ret = Validity::Partial;
let mut stack = [0u8; MAX_DEPTH];
let mut depth = 0usize;
let mut i = *start;
while i < max {
let Some(c) = at(buf, i) else { break };
i = i.saturating_add(1);
match c {
b'{' | b'[' => {
let next = depth;
if next >= MAX_DEPTH {
ret = Validity::MaxDepthExceeded;
} else {
depth = next.saturating_add(1);
if let Some(slot) = stack.get_mut(next) {
*slot = c;
}
if !skip_scalars(buf, &mut i, max, c) {
ret = Validity::Illegal;
}
}
}
b'}' | b']' => {
let d = depth.saturating_sub(1);
let open = stack.get(d).copied().unwrap_or(0);
if depth > 1 && d < MAX_DEPTH && is_matching_bracket(open, c) {
let outer = d.saturating_sub(1);
depth = outer.saturating_add(1);
let mode = stack.get(outer).copied().unwrap_or(0);
if skip_space_and_comma(buf, &mut i, max) {
if !skip_scalars(buf, &mut i, max, mode) {
ret = Validity::Illegal;
}
} else if i < max && !at(buf, i).is_some_and(|n| is_matching_bracket(mode, n)) {
ret = Validity::Illegal;
}
} else {
ret = if depth == 1 && is_matching_bracket(open, c) {
Validity::Valid
} else {
Validity::Illegal
};
}
}
_ => ret = Validity::Illegal,
}
if ret != Validity::Partial {
break;
}
}
if ret == Validity::Valid {
*start = i;
}
ret
}
#[must_use]
pub fn validate(buf: &[u8]) -> Validity {
let max = buf.len();
if max == 0 {
return Validity::BadParameter;
}
let mut i = 0usize;
skip_space(buf, &mut i, max);
let mut ret = if at(buf, i).is_some_and(is_open_bracket) {
skip_collection(buf, &mut i, max)
} else if skip_any_scalar(buf, &mut i, max) {
Validity::Valid
} else {
skip_collection(buf, &mut i, max)
};
if ret == Validity::Valid && i < max {
skip_space(buf, &mut i, max);
if i != max {
ret = Validity::Illegal;
}
}
ret
}
#[must_use]
pub fn is_valid(buf: &[u8]) -> bool {
validate(buf) == Validity::Valid
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_hex_table_is_the_rule_for_every_one_of_the_256_bytes() {
for c in 0..=u8::MAX {
assert_eq!(
hex_to_int(c),
hex_value(c),
"the table and the rule disagree about {c:#04x}"
);
}
}
#[test]
fn exactly_twenty_two_bytes_are_hex_digits() {
let hex = (0..=u8::MAX).filter(|c| hex_to_int(*c) != NOT_A_HEX_CHAR);
assert_eq!(hex.count(), 22, "10 digits plus a-f plus A-F");
}
#[test]
fn a_non_hex_byte_in_an_escape_is_refused() {
for bad in [
br#"{"a":"\ug000"}"#.as_slice(),
br#"{"a":"\u0g00"}"#.as_slice(),
br#"{"a":"\u00g0"}"#.as_slice(),
br#"{"a":"\u000g"}"#.as_slice(),
] {
assert!(
!is_valid(bad),
"a non-hex digit was accepted: {}",
core::str::from_utf8(bad).unwrap_or("<not utf8>")
);
}
assert!(is_valid(br#"{"a":"\u0041"}"#.as_slice()));
}
}