jsonx-lib 0.5.2

Strict RFC 8259 JSON: a borrowing parser, a pull reader, and a deterministic writer, with budgets checked before allocation and no recursion. No dependencies, no_std.
Documentation
//! Finding repeated keys in one object, in `O(n log n)` at worst.
//!
//! Shared by the tree builder (which applies every [`DuplicateKeys`](crate::DuplicateKeys)
//! policy) and the readers' state machine (which refuses duplicates under
//! the default policy). Keys are compared as decoded text, so `"a"` and an
//! escaped spelling of it are the same key. Each function takes the
//! object's keys as `key(i)` for `i` in `0..n`.

use alloc::vec::Vec;

/// Objects up to this many keys are checked pairwise.
const PAIRWISE: usize = 16;

/// Whether any of the `n` keys repeats. Small objects are checked pairwise,
/// comparing one-word fingerprints and the strings only when those match;
/// larger ones by sorting indices, which also leaves `order` sorted by
/// (key, position) for [`first_repeat`] and [`for_each_run`]. After `true`,
/// `order` is always sorted.
pub(crate) fn has_duplicates<'k>(
    n: usize,
    key: &impl Fn(usize) -> &'k str,
    order: &mut Vec<usize>,
) -> bool {
    if n < 2 {
        return false;
    }
    if n <= PAIRWISE {
        // At most 120 one-word comparisons.
        let mut prints = [0u64; PAIRWISE];
        for (i, slot) in prints.iter_mut().take(n).enumerate() {
            *slot = fingerprint(key(i).as_bytes());
        }
        let prints = prints.get(..n).unwrap_or(&[]);
        let any = prints.iter().enumerate().skip(1).any(|(i, a)| {
            prints
                .iter()
                .take(i)
                .enumerate()
                .any(|(j, b)| a == b && key(i) == key(j))
        });
        if !any {
            return false;
        }
    }
    order.clear();
    order.extend(0..n);
    order.sort_unstable_by(|&a, &b| key(a).cmp(key(b)).then(a.cmp(&b)));
    order.windows(2).any(|w| match w {
        [a, b] => key(*a) == key(*b),
        _ => false,
    })
}

/// A cheap summary of a key: equal keys have equal fingerprints. The length
/// and the first and last eight bytes, which tell most distinct keys apart
/// (including the `item1`/`item2` kind that share a long prefix).
#[inline]
pub(crate) fn fingerprint(bytes: &[u8]) -> u64 {
    let (head, tail) = match (bytes.first_chunk::<8>(), bytes.last_chunk::<8>()) {
        (Some(head), Some(tail)) => (u64::from_le_bytes(*head), u64::from_le_bytes(*tail)),
        _ => {
            let mut short = [0u8; 8];
            if let Some(slot) = short.get_mut(..bytes.len()) {
                slot.copy_from_slice(bytes);
            }
            (u64::from_le_bytes(short), 0)
        }
    };
    head ^ tail.rotate_left(29) ^ (bytes.len() as u64).rotate_left(56)
}

/// [`fingerprint`] of `text[start..end]`, without copying a short key: when
/// eight bytes of `text` follow `start` (as they do for any key but one at
/// the very end of a partial text), the key's first word is one load, masked
/// to its length.
#[inline]
pub(crate) fn fingerprint_at(text: &[u8], start: usize, end: usize) -> u64 {
    let len = end.saturating_sub(start);
    let word = |at: usize| {
        text.get(at..)
            .and_then(<[u8]>::first_chunk::<8>)
            .map(|w| u64::from_le_bytes(*w))
    };
    let (head, tail) = if len >= 8 {
        match (word(start), word(end - 8)) {
            (Some(head), Some(tail)) => (head, tail),
            _ => return fingerprint(text.get(start..end).unwrap_or_default()),
        }
    } else {
        match word(start) {
            // `len < 8`: the bytes past the key are masked off.
            Some(w) => (w & ((1u64 << (8 * len)) - 1), 0),
            None => return fingerprint(text.get(start..end).unwrap_or_default()),
        }
    };
    head ^ tail.rotate_left(29) ^ (len as u64).rotate_left(56)
}

/// Calls `f(run)` for each run of equal keys in the sorted `order` (each run
/// sorted by position, the first being the first occurrence).
pub(crate) fn for_each_run<'k>(
    key: &impl Fn(usize) -> &'k str,
    order: &[usize],
    mut f: impl FnMut(&[usize]),
) {
    let mut start = 0;
    while start < order.len() {
        let first = key(order.get(start).copied().unwrap_or(0));
        let mut end = start + 1;
        while order.get(end).is_some_and(|&i| key(i) == first) {
            end += 1;
        }
        if end - start > 1 {
            f(order.get(start..end).unwrap_or(&[]));
        }
        start = end;
    }
}

/// The position of the earliest key that repeats an earlier one, given the
/// sorted `order`.
pub(crate) fn first_repeat<'k>(key: &impl Fn(usize) -> &'k str, order: &[usize]) -> usize {
    let mut earliest = usize::MAX;
    for_each_run(key, order, |run| {
        if let Some(&second) = run.get(1) {
            earliest = earliest.min(second);
        }
    });
    earliest
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fingerprint_at_matches_the_fingerprint_of_the_slice() {
        let text = b"0123456789abcdefghij";
        for start in 0..=text.len() {
            for end in start..=text.len() {
                assert_eq!(
                    fingerprint_at(text, start, end),
                    fingerprint(&text[start..end]),
                    "{start}..{end}"
                );
            }
        }
    }

    #[test]
    fn test_pairwise_and_sorted_paths_agree() {
        let keys = ["a", "abcdefgh1", "abcdefgh2", "b", "abcdefgh1"];
        let key = |i: usize| keys.get(i).copied().unwrap_or("");
        let mut order = Vec::new();
        assert!(has_duplicates(keys.len(), &key, &mut order));
        assert_eq!(first_repeat(&key, &order), 4);
        assert!(!has_duplicates(4, &key, &mut order));
        assert!(!has_duplicates(1, &key, &mut order));

        let many: Vec<alloc::string::String> = (0..40).map(|i| alloc::format!("k{i}")).collect();
        let key = |i: usize| many.get(i).map_or("", |s| s.as_str());
        assert!(!has_duplicates(many.len(), &key, &mut order));
        let mut repeated = many.clone();
        repeated.push("k7".into());
        repeated.push("k3".into());
        let key = |i: usize| repeated.get(i).map_or("", |s| s.as_str());
        assert!(has_duplicates(repeated.len(), &key, &mut order));
        assert_eq!(first_repeat(&key, &order), 40);
        let mut runs = 0;
        for_each_run(&key, &order, |run| {
            runs += 1;
            assert_eq!(run.len(), 2);
        });
        assert_eq!(runs, 2);
    }
}