use std::collections::HashMap;
use crate::error::Error;
use crate::path::{try_parse_path, PathSegment};
use crate::scan::{find_string_end, find_value_offsets, skip_value, skip_whitespace};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
#[non_exhaustive]
pub enum DuplicateKeyPolicy {
#[default]
First,
Last,
Error,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ObjectKeyReport<'a> {
pub keys: Vec<ResolvedObjectKey<'a>>,
pub has_duplicates: bool,
}
impl<'a> ObjectKeyReport<'a> {
pub fn get(&self, key: &str) -> Option<&ResolvedObjectKey<'a>> {
let kb = key.as_bytes();
self.keys.iter().find(|k| k.key_raw == kb)
}
pub fn value_span(&self, json: &'a [u8], key: &str) -> Option<&'a [u8]> {
let r = self.get(key)?;
Some(r.value(json))
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolvedObjectKey<'a> {
pub key_raw: &'a [u8],
pub value_start: usize,
pub value_end: usize,
pub occurrences: u32,
pub first_key_pos: usize,
pub last_key_pos: usize,
}
impl<'a> ResolvedObjectKey<'a> {
#[inline]
pub fn value(&self, json: &'a [u8]) -> &'a [u8] {
&json[self.value_start..self.value_end]
}
#[inline]
pub fn key_str(&self) -> Option<&'a str> {
if self.key_raw.contains(&b'\\') {
return None;
}
std::str::from_utf8(self.key_raw).ok()
}
#[inline]
pub fn key_display(&self) -> std::borrow::Cow<'a, str> {
String::from_utf8_lossy(self.key_raw)
}
#[inline]
pub fn is_duplicate(&self) -> bool {
self.occurrences > 1
}
}
#[derive(Clone, Copy)]
struct KeyAcc {
first_key_pos: usize,
first_vs: usize,
first_ve: usize,
last_key_pos: usize,
last_vs: usize,
last_ve: usize,
occurrences: u32,
}
#[inline]
pub fn check_duplicate_keys<'a>(
json: &'a [u8],
policy: DuplicateKeyPolicy,
) -> Result<ObjectKeyReport<'a>, Error> {
check_duplicate_keys_at(json, &[], policy)
}
pub fn check_duplicate_keys_at<'a>(
json: &'a [u8],
path: &[PathSegment],
policy: DuplicateKeyPolicy,
) -> Result<ObjectKeyReport<'a>, Error> {
let (start, end) = object_range(json, path)?;
scan_object_report(json, start, end, policy)
}
pub fn check_duplicate_keys_path<'a>(
json: &'a [u8],
path: &str,
policy: DuplicateKeyPolicy,
) -> Result<ObjectKeyReport<'a>, Error> {
if path.is_empty() {
check_duplicate_keys(json, policy)
} else {
let segs = try_parse_path(path)?;
check_duplicate_keys_at(json, &segs, policy)
}
}
#[inline]
pub fn validate_unique_keys(json: &[u8]) -> Result<(), Error> {
let (start, end) = object_range(json, &[])?;
scan_object_unique_only(json, start, end)
}
#[inline]
pub fn validate_unique_keys_at(json: &[u8], path: &[PathSegment]) -> Result<(), Error> {
let (start, end) = object_range(json, path)?;
scan_object_unique_only(json, start, end)
}
#[inline]
pub fn validate_unique_keys_path(json: &[u8], path: &str) -> Result<(), Error> {
if path.is_empty() {
validate_unique_keys(json)
} else {
let segs = try_parse_path(path)?;
validate_unique_keys_at(json, &segs)
}
}
pub fn validate_unique_keys_deep(json: &[u8]) -> Result<(), Error> {
let start = skip_whitespace(json, 0);
if start >= json.len() {
return Err(Error::TypeMismatch {
expected: "value",
found: "eof",
});
}
scan_value_unique(json, start)
}
#[inline]
pub fn check_duplicate_keys_deep(json: &[u8], policy: DuplicateKeyPolicy) -> Result<(), Error> {
match policy {
DuplicateKeyPolicy::Error => validate_unique_keys_deep(json),
DuplicateKeyPolicy::First | DuplicateKeyPolicy::Last => Err(Error::InvalidPath {
msg: "check_duplicate_keys_deep only supports DuplicateKeyPolicy::Error; use check_duplicate_keys per object for First/Last reports",
}),
}
}
pub fn object_key_wins<'a>(
json: &'a [u8],
object_start: usize,
object_end: usize,
key_raw: &[u8],
policy: DuplicateKeyPolicy,
) -> Result<&'a [u8], Error> {
let mut first: Option<(usize, usize, usize)> = None; let mut last: Option<(usize, usize, usize)> = None;
let mut pos = skip_whitespace(json, object_start + 1);
while pos < object_end {
pos = skip_whitespace(json, pos);
if pos >= object_end || json[pos] == b'}' {
break;
}
if json[pos] != b'"' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected object key string",
});
}
let key_pos = pos;
let ks = pos + 1;
let ke = find_string_end(json, ks)?;
let this_key = &json[ks..ke];
pos = skip_whitespace(json, ke + 1);
if pos >= object_end || json[pos] != b':' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected colon after object key",
});
}
pos = skip_whitespace(json, pos + 1);
let vs = pos;
let ve = skip_value(json, vs)?;
if this_key == key_raw {
if let Some((first_kp, _, _)) = first {
if policy == DuplicateKeyPolicy::Error {
return Err(Error::DuplicateKey {
key: String::from_utf8_lossy(key_raw).into_owned(),
first_pos: first_kp,
pos: key_pos,
});
}
} else {
first = Some((key_pos, vs, ve));
}
last = Some((key_pos, vs, ve));
}
pos = skip_whitespace(json, ve);
if pos < object_end && json[pos] == b',' {
pos += 1;
}
}
let win = match policy {
DuplicateKeyPolicy::First | DuplicateKeyPolicy::Error => first,
DuplicateKeyPolicy::Last => last.or(first),
};
let (_kp, vs, ve) = win.ok_or(Error::PathNotFound)?;
Ok(&json[vs..ve])
}
fn object_range(json: &[u8], path: &[PathSegment]) -> Result<(usize, usize), Error> {
if path.is_empty() {
let s = skip_whitespace(json, 0);
if s >= json.len() || json[s] != b'{' {
return Err(Error::TypeMismatch {
expected: "object",
found: "non-object",
});
}
let e = skip_value(json, s)?;
Ok((s, e))
} else {
let (s, e) = find_value_offsets(json, path)?;
if s >= json.len() || json[s] != b'{' {
return Err(Error::TypeMismatch {
expected: "object",
found: "non-object",
});
}
Ok((s, e))
}
}
fn scan_object_report<'a>(
json: &'a [u8],
start: usize,
end: usize,
policy: DuplicateKeyPolicy,
) -> Result<ObjectKeyReport<'a>, Error> {
let mut order: Vec<&'a [u8]> = Vec::new();
let mut map: HashMap<&'a [u8], KeyAcc> = HashMap::new();
let mut pos = skip_whitespace(json, start + 1);
while pos < end {
pos = skip_whitespace(json, pos);
if pos >= end || json[pos] == b'}' {
break;
}
if json[pos] != b'"' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected object key string",
});
}
let key_pos = pos;
let ks = pos + 1;
let ke = find_string_end(json, ks)?;
let key_raw = &json[ks..ke];
pos = skip_whitespace(json, ke + 1);
if pos >= end || json[pos] != b':' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected colon after object key",
});
}
pos = skip_whitespace(json, pos + 1);
let vs = pos;
let ve = skip_value(json, vs)?;
match map.get_mut(key_raw) {
Some(acc) => {
if policy == DuplicateKeyPolicy::Error {
return Err(Error::DuplicateKey {
key: String::from_utf8_lossy(key_raw).into_owned(),
first_pos: acc.first_key_pos,
pos: key_pos,
});
}
acc.occurrences += 1;
acc.last_key_pos = key_pos;
acc.last_vs = vs;
acc.last_ve = ve;
}
None => {
order.push(key_raw);
map.insert(
key_raw,
KeyAcc {
first_key_pos: key_pos,
first_vs: vs,
first_ve: ve,
last_key_pos: key_pos,
last_vs: vs,
last_ve: ve,
occurrences: 1,
},
);
}
}
pos = skip_whitespace(json, ve);
if pos < end && json[pos] == b',' {
pos += 1;
}
}
let mut has_duplicates = false;
let mut keys = Vec::with_capacity(order.len());
for key_raw in order {
let acc = map.remove(key_raw).expect("key in order");
if acc.occurrences > 1 {
has_duplicates = true;
}
let (vs, ve) = match policy {
DuplicateKeyPolicy::First | DuplicateKeyPolicy::Error => (acc.first_vs, acc.first_ve),
DuplicateKeyPolicy::Last => (acc.last_vs, acc.last_ve),
};
keys.push(ResolvedObjectKey {
key_raw,
value_start: vs,
value_end: ve,
occurrences: acc.occurrences,
first_key_pos: acc.first_key_pos,
last_key_pos: acc.last_key_pos,
});
}
Ok(ObjectKeyReport {
keys,
has_duplicates,
})
}
fn scan_object_unique_only(json: &[u8], start: usize, end: usize) -> Result<(), Error> {
let mut seen: HashMap<&[u8], usize> = HashMap::new();
let mut pos = skip_whitespace(json, start + 1);
while pos < end {
pos = skip_whitespace(json, pos);
if pos >= end || json[pos] == b'}' {
break;
}
if json[pos] != b'"' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected object key string",
});
}
let key_pos = pos;
let ks = pos + 1;
let ke = find_string_end(json, ks)?;
let key_raw = &json[ks..ke];
pos = skip_whitespace(json, ke + 1);
if pos >= end || json[pos] != b':' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected colon after object key",
});
}
pos = skip_whitespace(json, pos + 1);
let vs = pos;
let ve = skip_value(json, vs)?;
if let Some(&first_pos) = seen.get(key_raw) {
return Err(Error::DuplicateKey {
key: String::from_utf8_lossy(key_raw).into_owned(),
first_pos,
pos: key_pos,
});
}
seen.insert(key_raw, key_pos);
pos = skip_whitespace(json, ve);
if pos < end && json[pos] == b',' {
pos += 1;
}
}
Ok(())
}
fn scan_value_unique(json: &[u8], start: usize) -> Result<(), Error> {
let start = skip_whitespace(json, start);
if start >= json.len() {
return Ok(());
}
match json[start] {
b'{' => {
let end = skip_value(json, start)?;
scan_object_unique_only(json, start, end)?;
let mut pos = skip_whitespace(json, start + 1);
while pos < end {
pos = skip_whitespace(json, pos);
if pos >= end || json[pos] == b'}' {
break;
}
if json[pos] != b'"' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected object key string",
});
}
let ks = pos + 1;
let ke = find_string_end(json, ks)?;
pos = skip_whitespace(json, ke + 1);
if pos >= end || json[pos] != b':' {
return Err(Error::InvalidJsonSyntax {
pos,
msg: "Expected colon after object key",
});
}
pos = skip_whitespace(json, pos + 1);
let vs = pos;
let ve = skip_value(json, vs)?;
scan_value_unique(json, vs)?;
pos = skip_whitespace(json, ve);
if pos < end && json[pos] == b',' {
pos += 1;
}
}
Ok(())
}
b'[' => {
let end = skip_value(json, start)?;
let mut pos = skip_whitespace(json, start + 1);
while pos < end {
pos = skip_whitespace(json, pos);
if pos >= end || json[pos] == b']' {
break;
}
let ve = skip_value(json, pos)?;
scan_value_unique(json, pos)?;
pos = skip_whitespace(json, ve);
if pos < end && json[pos] == b',' {
pos += 1;
}
}
Ok(())
}
_ => Ok(()),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn error_rejects_duplicate_key_quote_offsets() {
let j = br#"{"a":1,"b":2,"a":3}"#;
let e = check_duplicate_keys(j, DuplicateKeyPolicy::Error).unwrap_err();
match e {
Error::DuplicateKey {
first_pos,
pos,
key,
} => {
assert_eq!(key, "a");
assert_eq!(first_pos, 1);
assert_eq!(j[first_pos], b'"');
assert_eq!(pos, 13);
assert_eq!(j[pos], b'"');
}
other => panic!("unexpected {other:?}"),
}
validate_unique_keys(j).unwrap_err();
}
#[test]
fn first_and_last_report_wins_zero_key_alloc_path() {
let j = br#"{"a":1,"b":2,"a":3}"#;
let first = check_duplicate_keys(j, DuplicateKeyPolicy::First).unwrap();
assert!(first.has_duplicates);
assert_eq!(first.value_span(j, "a").unwrap(), b"1");
assert_eq!(first.get("a").unwrap().occurrences, 2);
assert_eq!(first.get("a").unwrap().first_key_pos, 1);
assert_eq!(first.get("a").unwrap().last_key_pos, 13);
let a = first.get("a").unwrap();
assert_eq!(a.key_raw.as_ptr(), j[2..3].as_ptr());
let last = check_duplicate_keys(j, DuplicateKeyPolicy::Last).unwrap();
assert_eq!(last.value_span(j, "a").unwrap(), b"3");
assert_eq!(last.get("b").unwrap().value(j), b"2");
}
#[test]
fn unique_error_ok_report() {
let j = br#"{"a":1,"b":2}"#;
let r = check_duplicate_keys(j, DuplicateKeyPolicy::Error).unwrap();
assert!(!r.has_duplicates);
assert_eq!(r.keys.len(), 2);
validate_unique_keys(j).unwrap();
}
#[test]
fn deep_unique() {
assert!(validate_unique_keys_deep(br#"{"ok":{"x":1},"bad":{"y":1,"y":2}}"#).is_err());
validate_unique_keys_deep(br#"{"ok":{"x":1},"good":{"y":1,"z":2}}"#).unwrap();
}
#[test]
fn deep_first_last_rejected() {
assert!(matches!(
check_duplicate_keys_deep(br#"{}"#, DuplicateKeyPolicy::First),
Err(Error::InvalidPath { .. })
));
}
#[test]
fn object_key_wins_single_pass() {
let j = br#"{"a":1,"a":2}"#;
assert_eq!(
object_key_wins(j, 0, j.len(), b"a", DuplicateKeyPolicy::First).unwrap(),
b"1"
);
assert_eq!(
object_key_wins(j, 0, j.len(), b"a", DuplicateKeyPolicy::Last).unwrap(),
b"2"
);
let e = object_key_wins(j, 0, j.len(), b"a", DuplicateKeyPolicy::Error).unwrap_err();
match e {
Error::DuplicateKey {
first_pos, pos, ..
} => {
assert_eq!(j[first_pos], b'"');
assert_eq!(j[pos], b'"');
assert!(pos > first_pos);
}
other => panic!("{other:?}"),
}
}
}