use super::{
FormatFault,
block::BLOCK_HEADER_LEN,
sidecar::{BlockIndex, FILE_HEADER_LEN},
};
pub(crate) enum SegmentIndex {
Hash(BlockIndex),
Key(SeparatorIndex),
}
#[cfg(test)]
impl SegmentIndex {
pub(crate) fn hash_index(&self) -> &BlockIndex {
match self {
Self::Hash(index) => index,
Self::Key(_) => panic!("hash index requested for key segment"),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct KeyRange {
pub min: Vec<u8>,
pub max: Vec<u8>,
}
impl KeyRange {
pub(crate) fn encode(&self) -> Vec<u8> {
let mut out = self.min.clone();
out.extend_from_slice(&self.max);
out
}
pub(crate) fn decode(section: &[u8], key_len: usize) -> Result<Self, FormatFault> {
if key_len == 0 || key_len.checked_mul(2) != Some(section.len()) {
return Err(FormatFault::corrupt("key range has the wrong width"));
}
let (min, max) = section.split_at(key_len);
if min > max {
return Err(FormatFault::corrupt("key range is inverted"));
}
Ok(Self {
min: min.to_vec(),
max: max.to_vec(),
})
}
}
pub(crate) fn shortest_separator(last: &[u8], first: &[u8]) -> Vec<u8> {
debug_assert!(last < first);
if let Some(at) = last.iter().zip(first).position(|(a, b)| a != b) {
let mut separator = last[..at].to_vec();
separator.push(last[at] + 1);
separator
} else {
first[..last.len() + 1].to_vec()
}
}
fn u32_at(b: &[u8], at: usize) -> u32 {
u32::from_le_bytes(b[at..at + 4].try_into().expect("checked field bounds"))
}
fn u64_at(b: &[u8], at: usize) -> u64 {
u64::from_le_bytes(b[at..at + 8].try_into().expect("checked field bounds"))
}
pub(crate) struct SeparatorIndex {
offsets: Vec<u64>,
separator_offsets: Vec<u32>,
separators: Vec<u8>,
}
impl SeparatorIndex {
pub(crate) fn validate(
section: &[u8],
key_len: usize,
) -> Result<(usize, usize, usize), FormatFault> {
let bad = || FormatFault::corrupt("invalid separator index");
if section.len() < 8 || u32_at(section, 4) != 0 {
return Err(bad());
}
let n = usize::try_from(u32_at(section, 0)).map_err(|_| bad())?;
if n == 0 {
return Err(bad());
}
let endpoints = n.checked_add(1).ok_or_else(bad)?;
let counts_at = endpoints
.checked_mul(8)
.and_then(|v| v.checked_add(8))
.ok_or_else(bad)?;
let separators_at = n
.checked_mul(4)
.and_then(|v| v.checked_add(counts_at))
.ok_or_else(bad)?;
let bytes_at = endpoints
.checked_mul(4)
.and_then(|v| v.checked_add(separators_at))
.ok_or_else(bad)?;
if bytes_at > section.len() {
return Err(bad());
}
let bytes = §ion[bytes_at..];
if u64_at(section, 8) != FILE_HEADER_LEN as u64
|| u32_at(section, separators_at) != 0
|| usize::try_from(u32_at(section, separators_at + n * 4)).ok() != Some(bytes.len())
{
return Err(bad());
}
let mut previous: Option<&[u8]> = None;
for i in 0..n {
let start = u64_at(section, 8 + i * 8);
let end = u64_at(section, 8 + (i + 1) * 8);
let len = end.checked_sub(start).ok_or_else(bad)?;
if len <= BLOCK_HEADER_LEN as u64
|| u32::try_from(len).is_err()
|| u32_at(section, counts_at + i * 4) == 0
{
return Err(bad());
}
let start =
usize::try_from(u32_at(section, separators_at + i * 4)).map_err(|_| bad())?;
let end =
usize::try_from(u32_at(section, separators_at + (i + 1) * 4)).map_err(|_| bad())?;
let sep = bytes.get(start..end).ok_or_else(bad)?;
if sep.len() > key_len
|| (i == 0 && !sep.is_empty())
|| previous.is_some_and(|p| p >= sep)
{
return Err(bad());
}
previous = Some(sep);
}
Ok((n, separators_at, bytes_at))
}
pub(crate) fn parse(section: &[u8], key_len: usize) -> Result<Self, FormatFault> {
let (n, separators_at, bytes_at) = Self::validate(section, key_len)?;
let endpoints = n + 1;
let bytes = §ion[bytes_at..];
Ok(Self {
offsets: (0..endpoints).map(|i| u64_at(section, 8 + i * 8)).collect(),
separator_offsets: (0..endpoints)
.map(|i| u32_at(section, separators_at + i * 4))
.collect(),
separators: bytes.to_vec(),
})
}
pub(crate) fn entry_counts(section: &[u8], key_len: usize) -> Result<Vec<u32>, FormatFault> {
let (n, _, _) = Self::validate(section, key_len)?;
let counts_at = 8 + (n + 1) * 8;
Ok((0..n).map(|i| u32_at(section, counts_at + i * 4)).collect())
}
pub(crate) fn len(&self) -> usize {
self.offsets.len() - 1
}
pub(crate) fn separator(&self, block: usize) -> &[u8] {
&self.separators
[self.separator_offsets[block] as usize..self.separator_offsets[block + 1] as usize]
}
pub(crate) fn locate(&self, key: &[u8]) -> usize {
let mut lo = 0;
let mut hi = self.len();
while lo < hi {
let mid = lo + (hi - lo) / 2;
if self.separator(mid) <= key {
lo = mid + 1;
} else {
hi = mid;
}
}
lo.saturating_sub(1)
}
pub(crate) fn range(&self, block: usize) -> (u64, usize) {
let start = self.offsets[block];
(start, (self.offsets[block + 1] - start) as usize)
}
pub(crate) fn end_offset(&self) -> u64 {
self.offsets[self.len()]
}
pub(crate) fn resident_bytes(&self) -> usize {
self.offsets.capacity() * 8
+ self.separator_offsets.capacity() * 4
+ self.separators.capacity()
}
}
pub(crate) struct SeparatorIndexBuilder {
offsets: Vec<u64>,
counts: Vec<u32>,
separator_offsets: Vec<u32>,
separators: Vec<u8>,
}
impl SeparatorIndexBuilder {
pub(crate) fn new() -> Self {
Self {
offsets: vec![FILE_HEADER_LEN as u64],
counts: Vec::new(),
separator_offsets: vec![0],
separators: Vec::new(),
}
}
pub(crate) fn push(
&mut self,
separator: &[u8],
block_len: u32,
entries: u32,
) -> Result<(), FormatFault> {
let bad = || FormatFault::corrupt("invalid separator index block");
let n = self.counts.len();
if n >= u32::MAX as usize
|| block_len as usize <= BLOCK_HEADER_LEN
|| entries == 0
|| (n == 0 && !separator.is_empty())
|| (n > 0 && &self.separators[self.separator_offsets[n - 1] as usize..] >= separator)
{
return Err(bad());
}
let separator_end = self
.separators
.len()
.checked_add(separator.len())
.and_then(|v| u32::try_from(v).ok())
.ok_or_else(bad)?;
let end = self.offsets[n]
.checked_add(u64::from(block_len))
.ok_or_else(bad)?;
self.offsets.push(end);
self.counts.push(entries);
self.separator_offsets.push(separator_end);
self.separators.extend_from_slice(separator);
Ok(())
}
pub(crate) fn end_offset(&self) -> u64 {
self.offsets[self.counts.len()]
}
pub(crate) fn finish(self) -> Result<Vec<u8>, FormatFault> {
if self.counts.is_empty() {
return Err(FormatFault::corrupt("empty separator index"));
}
let n = u32::try_from(self.counts.len())
.map_err(|_| FormatFault::corrupt("too many blocks"))?;
let capacity = self
.offsets
.len()
.checked_mul(8)
.and_then(|v| {
self.counts
.len()
.checked_mul(4)
.and_then(|c| v.checked_add(c))
})
.and_then(|v| {
self.separator_offsets
.len()
.checked_mul(4)
.and_then(|c| v.checked_add(c))
})
.and_then(|v| v.checked_add(self.separators.len()))
.and_then(|v| v.checked_add(8))
.ok_or_else(|| FormatFault::corrupt("separator index length overflow"))?;
let mut out = Vec::with_capacity(capacity);
out.extend_from_slice(&n.to_le_bytes());
out.extend_from_slice(&0u32.to_le_bytes());
for offset in self.offsets {
out.extend_from_slice(&offset.to_le_bytes());
}
for count in self.counts {
out.extend_from_slice(&count.to_le_bytes());
}
for offset in self.separator_offsets {
out.extend_from_slice(&offset.to_le_bytes());
}
out.extend(self.separators);
Ok(out)
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
fn golden() -> Vec<u8> {
vec![
2, 0, 0, 0, 0, 0, 0, 0, 64, 0, 0, 0, 0, 0, 0, 0, 164, 0, 0, 0, 0, 0, 0, 0, 8, 1, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2,
]
}
#[test]
fn by_key_sections_have_stable_bytes() {
assert_eq!(shortest_separator(&[0, 255], &[1, 0]), vec![1]);
assert_eq!(shortest_separator(&[1, 4], &[1, 5]), vec![1, 5]);
let mut b = SeparatorIndexBuilder::new();
b.push(b"", 100, 1).unwrap();
b.push(&[2], 100, 2).unwrap();
assert_eq!(b.finish().unwrap(), golden());
let index = SeparatorIndex::parse(&golden(), 2).unwrap();
assert_eq!(index.separator(0), b"");
assert_eq!(index.locate(&[2, 0]), 1);
assert_eq!(index.locate(&[0, 0]), 0);
assert_eq!(index.range(1), (164, 100));
assert_eq!(index.end_offset(), 264);
assert_eq!(index.resident_bytes(), 3 * 8 + 3 * 4 + 1);
let range = KeyRange {
min: vec![0, 1],
max: vec![2, 3],
};
assert_eq!(range.encode(), vec![0, 1, 2, 3]);
assert_eq!(KeyRange::decode(&range.encode(), 2).unwrap(), range);
let empty = vec![0, 0, 0, 0, 0, 0, 0, 0, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
assert!(SeparatorIndex::parse(&empty, 2).is_err());
assert!(SeparatorIndexBuilder::new().finish().is_err());
}
#[test]
fn resident_separator_bytes_charge_allocated_capacity() {
let mut index = SeparatorIndex::parse(&golden(), 2).unwrap();
index.offsets.reserve(32);
index.separator_offsets.reserve(32);
index.separators.reserve(32);
let allocated = index.offsets.capacity() * 8
+ index.separator_offsets.capacity() * 4
+ index.separators.capacity();
assert!(allocated > 3 * 8 + 3 * 4 + 1);
assert_eq!(index.resident_bytes(), allocated);
assert_eq!(SeparatorIndex::entry_counts(&golden(), 2).unwrap(), [1, 2]);
}
#[test]
fn by_key_structural_corruption_is_rejected() {
let good = golden();
for cut in 0..good.len() {
assert!(SeparatorIndex::parse(&good[..cut], 2).is_err());
assert!(SeparatorIndex::entry_counts(&good[..cut], 2).is_err());
}
for (at, replacement) in [
(4, 1),
(8, 63),
(16, 64),
(25, 0),
(32, 0),
(40, 1),
(44, 1),
(48, 3),
] {
let mut bad = good.clone();
bad[at] = replacement;
assert!(SeparatorIndex::parse(&bad, 2).is_err(), "offset {at}");
}
let mut bad = good.clone();
bad[..4].copy_from_slice(&u32::MAX.to_le_bytes());
assert!(SeparatorIndex::parse(&bad, 2).is_err());
assert!(SeparatorIndex::parse(&good, 0).is_err());
let mut b = SeparatorIndexBuilder::new();
b.push(b"", 100, 1).unwrap();
b.push(&[2], 100, 1).unwrap();
b.push(&[3], 100, 1).unwrap();
let good = b.finish().unwrap();
for sep in [1, 2] {
let mut bad = good.clone();
*bad.last_mut().unwrap() = sep;
assert!(SeparatorIndex::parse(&bad, 2).is_err());
}
for bytes in [&[1, 2, 3][..], &[2, 3, 1, 2][..]] {
assert!(KeyRange::decode(bytes, 2).is_err());
}
assert!(KeyRange::decode(&[], usize::MAX).is_err());
let mut b = SeparatorIndexBuilder::new();
assert!(b.push(&[1], 100, 1).is_err());
assert!(b.push(b"", 1, 1).is_err());
assert!(b.push(b"", 100, 0).is_err());
}
proptest! {
#[test]
fn separator_locate_matches_linear_blocks(mut keys in prop::collection::vec(any::<u16>(), 1..100), query in any::<u16>()) {
keys.sort_unstable(); keys.dedup();
let mut b = SeparatorIndexBuilder::new();
b.push(b"",100,1).unwrap();
let mut seps=vec![vec![]];
for pair in keys.windows(2) {
let sep=shortest_separator(&pair[0].to_be_bytes(), &pair[1].to_be_bytes());
prop_assert!(pair[0].to_be_bytes().as_slice() < sep.as_slice());
prop_assert!(sep.as_slice() <= pair[1].to_be_bytes().as_slice());
b.push(&sep,100,1).unwrap(); seps.push(sep);
}
let index=SeparatorIndex::parse(&b.finish().unwrap(),2).unwrap();
let q=query.to_be_bytes();
let expected=seps.iter().rposition(|s| s.as_slice() <= q.as_slice()).unwrap();
prop_assert_eq!(index.locate(&q),expected);
for (block,key) in keys.iter().enumerate() { prop_assert_eq!(index.locate(&key.to_be_bytes()),block); }
}
}
}