use crate::validate::{
Validity, at, skip_any_scalar, skip_collection, skip_digits_value, skip_space,
skip_space_and_comma, skip_string,
};
pub const QUERY_KEY_SEPARATOR: u8 = b'.';
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Kind {
String,
Number,
True,
False,
Null,
Object,
Array,
}
const fn kind_of(c: u8) -> Kind {
match c {
b'"' => Kind::String,
b'{' => Kind::Object,
b'[' => Kind::Array,
b't' => Kind::True,
b'f' => Kind::False,
b'n' => Kind::Null,
_ => Kind::Number,
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NotFound {
Missing,
BadQuery,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Stopped {
Exhausted,
NotACollection,
BadCursor,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Match<'a> {
pub offset: usize,
pub value: &'a [u8],
pub kind: Kind,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Pair<'a> {
pub key: Option<&'a [u8]>,
pub key_offset: usize,
pub offset: usize,
pub value: &'a [u8],
pub kind: Kind,
}
fn next_value(buf: &[u8], start: &mut usize, max: usize) -> Option<(usize, usize)> {
let mut i = *start;
let value_start = i;
let found = if skip_any_scalar(buf, &mut i, max) {
true
} else {
skip_collection(buf, &mut i, max) == Validity::Valid
};
if !found {
return None;
}
*start = i;
Some((value_start, i.saturating_sub(value_start)))
}
fn next_key_value_pair(
buf: &[u8],
start: &mut usize,
max: usize,
) -> Option<(usize, usize, usize, usize)> {
let mut i = *start;
let key_start = i;
if !skip_string(buf, &mut i, max) {
return None;
}
let key = key_start.saturating_add(1);
let key_length = i.saturating_sub(key_start).saturating_sub(2);
skip_space(buf, &mut i, max);
if !(i < max && at(buf, i) == Some(b':')) {
return None;
}
i = i.saturating_add(1);
skip_space(buf, &mut i, max);
let (value, value_length) = next_value(buf, &mut i, max)?;
*start = i;
Some((key, key_length, value, value_length))
}
fn object_search(buf: &[u8], max: usize, query: &[u8]) -> Option<(usize, usize)> {
let mut i = 0usize;
skip_space(buf, &mut i, max);
if !(i < max && at(buf, i) == Some(b'{')) {
return None;
}
i = i.saturating_add(1);
skip_space(buf, &mut i, max);
while i < max {
let Some((key, key_length, value, value_length)) = next_key_value_pair(buf, &mut i, max)
else {
break;
};
if query.len() == key_length && buf.get(key..key.saturating_add(key_length)) == Some(query)
{
return Some((value, value_length));
}
if !skip_space_and_comma(buf, &mut i, max) {
break;
}
}
None
}
fn array_search(buf: &[u8], max: usize, query_index: u32) -> Option<(usize, usize)> {
let mut i = 0usize;
skip_space(buf, &mut i, max);
if !(i < max && at(buf, i) == Some(b'[')) {
return None;
}
i = i.saturating_add(1);
skip_space(buf, &mut i, max);
let mut current: u32 = 0;
while i < max {
let Some((value, value_length)) = next_value(buf, &mut i, max) else {
break;
};
if current == query_index {
return Some((value, value_length));
}
if !skip_space_and_comma(buf, &mut i, max) || current == u32::MAX {
break;
}
current = current.saturating_add(1);
}
None
}
fn skip_query_part(query: &[u8], start: &mut usize, max: usize) -> Option<usize> {
let from = *start;
let mut i = from;
while i < max {
match at(query, i) {
Some(c) if c != QUERY_KEY_SEPARATOR && c != b'[' => i = i.saturating_add(1),
_ => break,
}
}
if i > from {
*start = i;
return Some(i.saturating_sub(from));
}
None
}
fn multi_search(buf: &[u8], query: &[u8]) -> Result<(usize, usize), NotFound> {
let query_length = query.len();
let mut i = 0usize;
let mut start = 0usize;
let mut length = buf.len();
while i < query_length {
let Some(sub) = buf.get(start..).and_then(|rest| rest.get(..length)) else {
return Err(NotFound::Missing);
};
let found = if at(query, i) == Some(b'[') {
i = i.saturating_add(1);
let query_index = skip_digits_value(query, &mut i, query_length).unwrap_or(-1);
if query_index < 0 || i >= query_length || at(query, i) != Some(b']') {
return Err(NotFound::BadQuery);
}
i = i.saturating_add(1);
array_search(sub, length, query_index.unsigned_abs())
} else {
let query_start = i;
let Some(key_length) = skip_query_part(query, &mut i, query_length) else {
return Err(NotFound::BadQuery);
};
if i == query_length.saturating_sub(1) {
return Err(NotFound::BadQuery);
}
let Some(key) = query.get(query_start..query_start.saturating_add(key_length)) else {
return Err(NotFound::BadQuery);
};
object_search(sub, length, key)
};
let Some((value, value_length)) = found else {
return Err(NotFound::Missing);
};
start = start.saturating_add(value);
length = value_length;
if i < query_length && at(query, i) == Some(QUERY_KEY_SEPARATOR) {
i = i.saturating_add(1);
}
}
Ok((start, length))
}
pub fn search<'a>(buf: &'a [u8], query: &[u8]) -> Result<Match<'a>, NotFound> {
if buf.is_empty() || query.is_empty() {
return Err(NotFound::BadQuery);
}
let (value, length) = multi_search(buf, query)?;
let Some(first) = at(buf, value) else {
return Err(NotFound::Missing);
};
let kind = kind_of(first);
let (offset, length) = if kind == Kind::String {
(value.saturating_add(1), length.saturating_sub(2))
} else {
(value, length)
};
let Some(slice) = buf.get(offset..).and_then(|rest| rest.get(..length)) else {
return Err(NotFound::Missing);
};
Ok(Match {
offset,
value: slice,
kind,
})
}
pub fn iterate<'a>(
buf: &'a [u8],
start: &mut usize,
next: &mut usize,
) -> Result<Pair<'a>, Stopped> {
let max = buf.len();
if max == 0 || *start >= max || *next > max {
return Err(Stopped::BadCursor);
}
skip_space(buf, start, max);
if *next <= *start {
*next = start.saturating_add(1);
skip_space(buf, next, max);
}
let Some(opener) = at(buf, *start) else {
return Err(Stopped::Exhausted);
};
let (key, key_length, value, value_length) = match opener {
b'[' => {
let Some((value, value_length)) = next_value(buf, next, max) else {
return Err(Stopped::Exhausted);
};
(0usize, 0usize, value, value_length)
}
b'{' => {
let Some(found) = next_key_value_pair(buf, next, max) else {
return Err(Stopped::Exhausted);
};
found
}
_ => return Err(Stopped::NotACollection),
};
let _ = skip_space_and_comma(buf, next, max);
let Some(first) = at(buf, value) else {
return Err(Stopped::Exhausted);
};
let kind = kind_of(first);
let (offset, value_length) = if kind == Kind::String {
(value.saturating_add(1), value_length.saturating_sub(2))
} else {
(value, value_length)
};
let Some(value_slice) = buf.get(offset..).and_then(|rest| rest.get(..value_length)) else {
return Err(Stopped::Exhausted);
};
let key_slice = if key == 0 {
None
} else {
buf.get(key..).and_then(|rest| rest.get(..key_length))
};
Ok(Pair {
key: key_slice,
key_offset: if key_slice.is_some() { key } else { 0 },
offset,
value: value_slice,
kind,
})
}
#[derive(Debug, Clone)]
pub struct Pairs<'a> {
buf: &'a [u8],
start: usize,
next: usize,
done: bool,
}
#[must_use]
pub const fn pairs(buf: &[u8]) -> Pairs<'_> {
Pairs {
buf,
start: 0,
next: 0,
done: false,
}
}
impl<'a> Iterator for Pairs<'a> {
type Item = Pair<'a>;
fn next(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
match iterate(self.buf, &mut self.start, &mut self.next) {
Ok(pair) => Some(pair),
Err(_) => {
self.done = true;
None
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_two_scanners_are_disjoint_and_do_not_move_on_failure() {
const INPUTS: [&[u8]; 18] = [
b"",
b" ",
b"[",
b"]",
b"{",
b"}",
b"[]",
b"{}",
b"[1,2]",
b"{\"a\":1}",
b"42",
b"-0.5e3",
b"\"s\"",
b"true",
b"false",
b"null",
b"[1,2",
b"{\"a\":",
];
for input in INPUTS {
let max = input.len();
let mut scalar_at = 0usize;
let scalar = skip_any_scalar(input, &mut scalar_at, max);
let mut collection_at = 0usize;
let collection = skip_collection(input, &mut collection_at, max) == Validity::Valid;
assert!(
!(scalar && collection),
"both scanners claimed {input:?}, so the order WOULD matter"
);
if !scalar {
assert_eq!(
scalar_at, 0,
"a failed scalar scan moved the cursor on {input:?}"
);
}
if !collection {
assert_eq!(
collection_at, 0,
"a failed collection scan moved the cursor on {input:?}"
);
}
}
}
}