use alloc::vec::Vec;
const PAIRWISE: usize = 16;
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 {
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,
})
}
#[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)
}
#[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) {
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)
}
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;
}
}
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);
}
}