use crate::store::Span;
use std::ops::Range;
use std::sync::OnceLock;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Carve {
Messages { intra: Option<usize> },
Cdc { target: usize },
Whole,
Inline,
}
impl Default for Carve {
fn default() -> Carve {
Carve::Messages { intra: None }
}
}
impl Carve {
pub fn carve<'a>(&self, body: &'a [u8]) -> Vec<Span<'a>> {
let ranges = self.ranges(body);
ranges
.into_iter()
.map(|(foldable, r)| if foldable { Span::Piece(&body[r]) } else { Span::Lit(&body[r]) })
.collect()
}
pub fn ranges(&self, body: &[u8]) -> Vec<(bool, Range<usize>)> {
if body.is_empty() {
return Vec::new();
}
match *self {
Carve::Inline => vec![(false, 0..body.len())],
Carve::Whole => vec![(true, 0..body.len())],
Carve::Cdc { target } => gear_ranges(body, target.max(64)),
Carve::Messages { intra } => match split_json_array(body) {
Some(elems) if !elems.is_empty() => {
let mut out = Vec::with_capacity(elems.len() * 2 + 1);
let mut cur = 0usize;
for (a, b) in elems {
if a > cur {
out.push((false, cur..a));
}
match intra {
Some(big) if b - a > big => {
for (_, sub) in gear_ranges(&body[a..b], big.max(64)) {
out.push((true, a + sub.start..a + sub.end));
}
}
_ => out.push((true, a..b)),
}
cur = b;
}
if cur < body.len() {
out.push((false, cur..body.len()));
}
out
}
_ => gear_ranges(body, 4096),
},
}
}
}
fn split_json_array(s: &[u8]) -> Option<Vec<(usize, usize)>> {
let mut i = 0;
while i < s.len() && s[i].is_ascii_whitespace() {
i += 1;
}
if i >= s.len() || s[i] != b'[' {
return None;
}
i += 1;
let mut out = Vec::new();
let (mut depth, mut in_str, mut esc) = (0i32, false, false);
let mut start: Option<usize> = None;
while i < s.len() {
let c = s[i];
if in_str {
if esc {
esc = false;
} else if c == b'\\' {
esc = true;
} else if c == b'"' {
in_str = false;
}
} else {
match c {
b'"' => {
in_str = true;
if start.is_none() {
start = Some(i);
}
}
b'[' | b'{' => {
if start.is_none() {
start = Some(i);
}
depth += 1;
}
b']' | b'}' => {
if depth == 0 && c == b']' {
if let Some(st) = start.take() {
out.push((st, i));
}
return Some(out);
}
depth -= 1;
}
b',' if depth == 0 => {
if let Some(st) = start.take() {
out.push((st, i));
}
}
w if w.is_ascii_whitespace() => {}
_ => {
if start.is_none() {
start = Some(i);
}
}
}
}
i += 1;
}
None
}
fn sm64(x: &mut u64) -> u64 {
*x = x.wrapping_add(0x9e3779b97f4a7c15);
let mut z = *x;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
z ^ (z >> 31)
}
fn gear_table() -> &'static [u64; 256] {
static TBL: OnceLock<[u64; 256]> = OnceLock::new();
TBL.get_or_init(|| {
let mut s = 0x7475726e_64620001u64; let mut t = [0u64; 256];
for e in t.iter_mut() {
*e = sm64(&mut s);
}
t
})
}
fn gear_ranges(body: &[u8], avg: usize) -> Vec<(bool, Range<usize>)> {
let tbl = gear_table();
let min = avg / 4;
let max = avg * 4;
let bits = (avg as f64).log2().round() as u32;
let ns = (bits + 2).min(63); let nl = bits.saturating_sub(2).max(1); let mut out = Vec::new();
let mut start = 0usize;
while start < body.len() {
let rem = body.len() - start;
if rem <= min {
out.push((true, start..body.len()));
break;
}
let hard = (start + max).min(body.len());
let mut h: u64 = 0;
let mut i = start + min;
for &b in &body[start..start + min] {
h = (h << 1).wrapping_add(tbl[b as usize]);
}
let normal = (start + avg).min(hard);
let mut cut = hard;
while i < hard {
h = (h << 1).wrapping_add(tbl[body[i] as usize]);
let n = if i < normal { ns } else { nl };
if h >> (64 - n) == 0 {
cut = i + 1;
break;
}
i += 1;
}
out.push((true, start..cut));
start = cut;
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn reassemble(body: &[u8], ranges: &[(bool, Range<usize>)]) -> Vec<u8> {
let mut out = Vec::new();
for (_, r) in ranges {
out.extend_from_slice(&body[r.clone()]);
}
out
}
#[test]
fn every_strategy_reassembles_exactly() {
let bodies: Vec<Vec<u8>> = vec![
br#"[{"role":"user","content":"hi"},{"role":"assistant","content":"hello"}]"#.to_vec(),
br#"[{"a":"br,ack]ets \" in [strings"},{"b":[1,2,{"c":"}]"}]}, "bare string" ]"#
.to_vec(),
br#"{"not":"an array"}"#.to_vec(),
(0u8..=255).cycle().take(40_000).collect(),
b"tiny".to_vec(),
Vec::new(),
];
let strategies = [
Carve::Messages { intra: None },
Carve::Messages { intra: Some(1024) },
Carve::Cdc { target: 2048 },
Carve::Whole,
Carve::Inline,
];
for body in &bodies {
for s in &strategies {
let ranges = s.ranges(body);
assert_eq!(&reassemble(body, &ranges), body, "{s:?} broke byte-exactness");
let mut at = 0usize;
for (_, r) in &ranges {
assert_eq!(r.start, at, "{s:?} left a gap");
at = r.end;
}
assert_eq!(at, body.len(), "{s:?} fell short");
}
}
}
#[test]
fn appending_a_turn_preserves_every_earlier_piece() {
let turn = |i: usize| {
format!(
r#"{{"role":"user","content":"turn {i} with some padding {}"}}"#,
"x".repeat(i * 13)
)
};
let conv =
|n: usize| format!("[{}]", (0..n).map(turn).collect::<Vec<_>>().join(",")).into_bytes();
let carve = Carve::default();
let pieces = |b: &[u8]| -> Vec<Vec<u8>> {
carve.ranges(b).into_iter().filter(|(f, _)| *f).map(|(_, r)| b[r].to_vec()).collect()
};
let five = conv(5);
let six = conv(6);
let p5 = pieces(&five);
let p6 = pieces(&six);
assert_eq!(p5.len(), 5);
assert_eq!(p6.len(), 6);
assert_eq!(&p6[..5], &p5[..], "the resent prefix must carve to IDENTICAL pieces");
}
#[test]
fn non_array_bodies_fall_back_to_cdc() {
let body: Vec<u8> = (0..30_000u32).flat_map(|i| i.to_le_bytes()).collect();
let msg = Carve::Messages { intra: None }.ranges(&body);
let cdc = Carve::Cdc { target: 4096 }.ranges(&body);
assert_eq!(msg, cdc, "unknown structure must carve exactly as the fallback does");
assert!(msg.len() > 1, "a large opaque body must actually chunk");
}
#[test]
fn cdc_chunks_respect_their_bounds_and_determinism() {
let body: Vec<u8> = {
let mut s = 42u64;
(0..200_000).map(|_| (sm64(&mut s) & 0xFF) as u8).collect()
};
let avg = 4096;
let ranges = Carve::Cdc { target: avg }.ranges(&body);
for (i, (_, r)) in ranges.iter().enumerate() {
let last = i + 1 == ranges.len();
assert!(r.len() <= avg * 4, "chunk {i} exceeds max");
if !last {
assert!(r.len() >= avg / 4, "chunk {i} under min");
}
}
assert_eq!(ranges, Carve::Cdc { target: avg }.ranges(&body), "CDC must be deterministic");
}
#[test]
fn cdc_resynchronises_after_a_prefix_shift() {
let body: Vec<u8> = {
let mut s = 7u64;
(0..300_000).map(|_| (sm64(&mut s) & 0xFF) as u8).collect()
};
let mut shifted = b"PREFIX-INSERTED-".to_vec();
shifted.extend_from_slice(&body);
let a: std::collections::HashSet<Vec<u8>> = Carve::Cdc { target: 4096 }
.ranges(&body)
.into_iter()
.map(|(_, r)| body[r].to_vec())
.collect();
let b: std::collections::HashSet<Vec<u8>> = Carve::Cdc { target: 4096 }
.ranges(&shifted)
.into_iter()
.map(|(_, r)| shifted[r].to_vec())
.collect();
let common = a.intersection(&b).count();
assert!(
common * 10 >= a.len() * 8,
"at least 80% of chunks must survive a prefix shift; got {common}/{}",
a.len()
);
}
#[test]
fn intra_chunking_splits_only_oversized_elements() {
let small = r#"{"role":"user","content":"short"}"#;
let big = format!(r#"{{"role":"tool","content":"{}"}}"#, "y".repeat(20_000));
let body = format!("[{small},{big}]").into_bytes();
let plain = Carve::Messages { intra: None }.ranges(&body);
let hybrid = Carve::Messages { intra: Some(4096) }.ranges(&body);
let fold_count = |v: &[(bool, Range<usize>)]| v.iter().filter(|(f, _)| *f).count();
assert_eq!(fold_count(&plain), 2);
assert!(fold_count(&hybrid) > 2, "the oversized element must chunk");
let first_piece = |v: &[(bool, Range<usize>)]| {
v.iter().find(|(f, _)| *f).map(|(_, r)| r.clone()).unwrap()
};
assert_eq!(first_piece(&plain), first_piece(&hybrid));
}
}