use crate::{
error::{Error, Result},
format::{TermId, TextSpaceId, segment::SegmentRef, text::PostingList},
};
#[cfg(test)]
use crate::format::{CollectionId, FrameId, text::Posting};
const MAGIC: [u8; 4] = *b"VLTP";
const VERSION: u16 = 3;
const DIRECTORY_ENTRY_LEN: usize = 24;
pub(crate) const DENSE_THRESHOLD: u32 = u32::MAX;
pub(crate) const DENSE_FLAG: u32 = 1 << 31;
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct PostingsSegment {
pub(crate) text_space_id: TextSpaceId,
pub(crate) previous_root: Option<SegmentRef>,
pub(crate) posting_lists: Vec<PostingList>,
}
pub(crate) fn encode_postings_segment(seg: &PostingsSegment) -> Result<Vec<u8>> {
let mut buf = Vec::new();
buf.extend_from_slice(&MAGIC);
buf.extend_from_slice(&VERSION.to_le_bytes());
buf.extend_from_slice(&seg.text_space_id.0.to_le_bytes());
write_optional_segment_ref(&mut buf, seg.previous_root);
let mut blob: Vec<u8> = Vec::new();
let mut directory: Vec<u8> = Vec::with_capacity(seg.posting_lists.len() * DIRECTORY_ENTRY_LEN);
for list in &seg.posting_lists {
let blob_offset = u32::try_from(blob.len())
.map_err(|_| Error::Format("PostingsSegment: blob offset exceeds u32".into()))?;
let cf: u64 = list.postings.iter().map(|p| u64::from(p.term_freq)).sum();
#[allow(clippy::absurd_extreme_comparisons)]
let is_dense = list.df > DENSE_THRESHOLD;
if is_dense {
encode_posting_blob_dense(&mut blob, list)?;
} else {
encode_posting_blob(&mut blob, list)?;
}
let blob_byte_len = u32::try_from(blob.len() - blob_offset as usize)
.map_err(|_| Error::Format("PostingsSegment: term blob length exceeds u32".into()))?;
if blob_byte_len & DENSE_FLAG != 0 {
return Err(Error::Format(
"PostingsSegment: term blob length collides with dense flag bit".into(),
));
}
let blob_len_with_flag = if is_dense {
blob_byte_len | DENSE_FLAG
} else {
blob_byte_len
};
directory.extend_from_slice(&list.term_id.0.to_le_bytes());
directory.extend_from_slice(&list.df.to_le_bytes());
directory.extend_from_slice(&cf.to_le_bytes());
directory.extend_from_slice(&blob_offset.to_le_bytes());
directory.extend_from_slice(&blob_len_with_flag.to_le_bytes());
}
let blob_len = u32::try_from(blob.len())
.map_err(|_| Error::Format("PostingsSegment: blob exceeds u32".into()))?;
let dir_count = u32::try_from(seg.posting_lists.len())
.map_err(|_| Error::Format("PostingsSegment: dir count exceeds u32".into()))?;
buf.extend_from_slice(&blob_len.to_le_bytes());
buf.extend_from_slice(&blob);
buf.extend_from_slice(&dir_count.to_le_bytes());
buf.extend_from_slice(&directory);
Ok(buf)
}
fn encode_posting_blob_dense(buf: &mut Vec<u8>, list: &PostingList) -> Result<()> {
let max_frame = list
.postings
.last()
.map(|p| p.frame_id.0)
.ok_or_else(|| Error::Format("dense posting list cannot be empty".into()))?;
let num_words = (max_frame / 64 + 1) as usize;
let mut bitset: Vec<u64> = vec![0u64; num_words];
let mut prev = 0u64;
for (i, posting) in list.postings.iter().enumerate() {
if i > 0 && posting.frame_id.0 <= prev {
return Err(Error::Format(format!(
"PostingsSegment: dense list must be ascending by frame_id (term_id={}, ordinal={i}, frame_id={}, prev={prev})",
list.term_id.0, posting.frame_id.0
)));
}
let fid = posting.frame_id.0;
let word_idx = (fid / 64) as usize;
let bit = fid % 64;
bitset[word_idx] |= 1u64 << bit;
prev = fid;
}
buf.reserve(num_words * 8);
for word in &bitset {
buf.extend_from_slice(&word.to_le_bytes());
}
Ok(())
}
fn encode_posting_blob(buf: &mut Vec<u8>, list: &PostingList) -> Result<()> {
let posting_count = u32::try_from(list.postings.len())
.map_err(|_| Error::Format("PostingList posting count overflow".into()))?;
write_varint_u64(buf, posting_count as u64);
let mut prev = 0u64;
for (i, posting) in list.postings.iter().enumerate() {
if i > 0 && posting.frame_id.0 <= prev {
return Err(Error::Format(format!(
"PostingsSegment: postings within a list must be ascending by frame_id (term_id={}, ordinal={i}, frame_id={}, prev={prev})",
list.term_id.0, posting.frame_id.0
)));
}
let gap = posting.frame_id.0 - prev;
if gap >> 63 != 0 {
return Err(Error::Format(format!(
"PostingsSegment: gap {gap} exceeds 2^63 — cannot pack the tf-exception flag bit"
)));
}
let tf_flag: u64 = if posting.term_freq > 1 { 1 } else { 0 };
write_varint_u64(buf, (gap << 1) | tf_flag);
prev = posting.frame_id.0;
}
for posting in &list.postings {
if posting.term_freq > 1 {
write_varint_u64(buf, u64::from(posting.term_freq));
} else if posting.term_freq == 0 {
return Err(Error::Format(format!(
"PostingsSegment: term_freq 0 is invalid (term_id={}, frame_id={})",
list.term_id.0, posting.frame_id.0
)));
}
}
for posting in &list.postings {
write_varint_u64(buf, u64::from(posting.collection_id.0));
}
for posting in &list.postings {
write_varint_u64(buf, u64::from(posting.field_mask));
}
if list.postings.iter().any(|p| p.positions_ref.is_some()) {
return Err(Error::Unsupported(
"PostingsSegment: positions_ref is reserved for a future format version".into(),
));
}
buf.push(0u8);
Ok(())
}
#[cfg(test)]
pub(crate) fn decode_postings_segment(bytes: &[u8]) -> Result<PostingsSegment> {
let dir = decode_postings_segment_directory(bytes)?;
let mut posting_lists = Vec::with_capacity(dir.entries.len());
for entry in &dir.entries {
let blob_slice =
&dir.blob[entry.blob_offset as usize..(entry.blob_offset + entry.blob_len) as usize];
let decoded = decode_term_blob_into(entry.term_id, entry.df, blob_slice)?;
let postings: Vec<Posting> = (0..decoded.frame_ids.len())
.map(|i| Posting {
frame_id: FrameId(decoded.frame_ids[i]),
collection_id: CollectionId(decoded.collection_ids[i]),
field_mask: decoded.field_masks[i],
term_freq: decoded.term_freqs[i],
positions_ref: None,
})
.collect();
posting_lists.push(PostingList {
term_id: entry.term_id,
df: entry.df,
postings,
});
}
Ok(PostingsSegment {
text_space_id: dir.text_space_id,
previous_root: dir.previous_root,
posting_lists,
})
}
#[derive(Debug)]
pub(crate) struct PostingListSoaDecoded {
#[allow(dead_code)]
pub(crate) term_id: TermId,
pub(crate) df: u32,
pub(crate) frame_ids: Vec<u64>,
pub(crate) term_freqs: Vec<u32>,
pub(crate) collection_ids: Vec<u32>,
pub(crate) field_masks: Vec<u32>,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct PostingsDirectoryEntry {
pub(crate) term_id: TermId,
pub(crate) df: u32,
pub(crate) cf: u64,
pub(crate) blob_offset: u32,
pub(crate) blob_len: u32,
pub(crate) is_dense: bool,
}
#[derive(Clone, Debug)]
pub(crate) struct PostingsSegmentDirectory {
#[allow(dead_code)]
pub(crate) text_space_id: TextSpaceId,
pub(crate) previous_root: Option<SegmentRef>,
pub(crate) entries: Vec<PostingsDirectoryEntry>,
pub(crate) blob: Vec<u8>,
}
pub(crate) fn decode_postings_segment_directory(bytes: &[u8]) -> Result<PostingsSegmentDirectory> {
let mut cur = Cursor::new(bytes);
let magic = cur.read_array::<4>()?;
if magic != MAGIC {
return Err(Error::Format(format!(
"PostingsSegment magic mismatch: expected VLTP, got {magic:?}"
)));
}
let version = cur.read_u16()?;
if version != VERSION {
return Err(Error::Format(format!(
"PostingsSegment version mismatch: expected {VERSION}, got {version}"
)));
}
let text_space_id = TextSpaceId(cur.read_u32()?);
let previous_root = read_optional_segment_ref(&mut cur)?;
let blob_len = cur.read_u32()? as usize;
let blob_start = cur.pos();
let blob_end = blob_start
.checked_add(blob_len)
.ok_or_else(|| Error::Format("PostingsSegment: blob_len overflow".into()))?;
if blob_end > bytes.len() {
return Err(Error::Format("PostingsSegment: blob truncated".into()));
}
let blob = bytes[blob_start..blob_end].to_vec();
cur.advance(blob_len)?;
let dir_count = cur.read_u32()? as usize;
let mut entries = Vec::with_capacity(dir_count);
for _ in 0..dir_count {
let term_id = TermId(cur.read_u32()?);
let df = cur.read_u32()?;
let cf = cur.read_u64()?;
let blob_offset = cur.read_u32()?;
let blob_len_with_flag = cur.read_u32()?;
let is_dense = (blob_len_with_flag & DENSE_FLAG) != 0;
let blob_len_for_term = blob_len_with_flag & !DENSE_FLAG;
if (blob_offset as usize)
.checked_add(blob_len_for_term as usize)
.map(|end| end > blob.len())
.unwrap_or(true)
{
return Err(Error::Format(format!(
"PostingsSegment: directory entry term_id={} blob slice [{}, {}) out of bounds (blob_len={})",
term_id.0,
blob_offset,
blob_offset as u64 + blob_len_for_term as u64,
blob.len()
)));
}
entries.push(PostingsDirectoryEntry {
term_id,
df,
cf,
blob_offset,
blob_len: blob_len_for_term,
is_dense,
});
}
if !cur.is_empty() {
return Err(Error::Format(format!(
"PostingsSegment: {} trailing bytes",
cur.remaining()
)));
}
Ok(PostingsSegmentDirectory {
text_space_id,
previous_root,
entries,
blob,
})
}
pub(crate) fn decode_term_blob_into(
term_id: TermId,
df: u32,
blob_slice: &[u8],
) -> Result<PostingListSoaDecoded> {
let mut cur = Cursor::new(blob_slice);
let posting_count = read_varint_u64(&mut cur)? as usize;
let mut frame_ids = Vec::with_capacity(posting_count);
let mut term_freqs = Vec::with_capacity(posting_count);
let mut exception_rows: Vec<u32> = Vec::new();
let mut prev = 0u64;
for i in 0..posting_count {
let packed = read_varint_u64(&mut cur)?;
let gap = packed >> 1;
let tf_flag = (packed & 1) as u32;
let frame_id = prev
.checked_add(gap)
.ok_or_else(|| Error::Format("PostingsSegment: frame_id overflow".into()))?;
frame_ids.push(frame_id);
term_freqs.push(1u32);
if tf_flag != 0 {
exception_rows.push(u32::try_from(i).map_err(|_| {
Error::Format("PostingsSegment: too many tf-exception rows".into())
})?);
}
prev = frame_id;
}
for row in &exception_rows {
let v = read_varint_u64(&mut cur)?;
let tf = u32::try_from(v).map_err(|_| {
Error::Format(format!(
"PostingsSegment: term_freq exception {v} exceeds u32"
))
})?;
if tf <= 1 {
return Err(Error::Format(format!(
"PostingsSegment: tf-exception stream value {tf} must be >= 2 (term_id={}, ordinal={})",
term_id.0, row
)));
}
term_freqs[*row as usize] = tf;
}
let mut collection_ids = Vec::with_capacity(posting_count);
for _ in 0..posting_count {
let v = read_varint_u64(&mut cur)?;
collection_ids.push(u32::try_from(v).map_err(|_| {
Error::Format(format!("PostingsSegment: collection_id {v} exceeds u32"))
})?);
}
let mut field_masks = Vec::with_capacity(posting_count);
for _ in 0..posting_count {
let v = read_varint_u64(&mut cur)?;
field_masks.push(
u32::try_from(v).map_err(|_| {
Error::Format(format!("PostingsSegment: field_mask {v} exceeds u32"))
})?,
);
}
let positions_present = cur.read_u8()?;
if positions_present != 0 {
return Err(Error::Unsupported(format!(
"PostingsSegment: positions are reserved (positions_present byte = {positions_present})"
)));
}
if !cur.is_empty() {
return Err(Error::Format(format!(
"PostingsSegment: term blob has {} trailing bytes",
cur.remaining()
)));
}
Ok(PostingListSoaDecoded {
term_id,
df,
frame_ids,
term_freqs,
collection_ids,
field_masks,
})
}
fn write_varint_u64(buf: &mut Vec<u8>, mut value: u64) {
while value >= 0x80 {
buf.push((value as u8) | 0x80);
value >>= 7;
}
buf.push(value as u8);
}
fn read_varint_u64(cur: &mut Cursor<'_>) -> Result<u64> {
let mut value = 0u64;
let mut shift = 0;
loop {
if shift >= 64 {
return Err(Error::Format(
"PostingsSegment: varint u64 exceeds 64 bits".into(),
));
}
let byte = cur.read_u8()?;
value |= u64::from(byte & 0x7F) << shift;
if byte & 0x80 == 0 {
break;
}
shift += 7;
}
Ok(value)
}
fn write_optional_segment_ref(buf: &mut Vec<u8>, maybe_ref: Option<SegmentRef>) {
if let Some(r) = maybe_ref {
buf.push(1u8);
buf.extend_from_slice(&r.segment_id.0.to_le_bytes());
buf.extend_from_slice(&r.offset.to_le_bytes());
buf.extend_from_slice(&r.length.to_le_bytes());
buf.extend_from_slice(&r.checksum);
} else {
buf.push(0u8);
}
}
fn read_optional_segment_ref(cur: &mut Cursor<'_>) -> Result<Option<SegmentRef>> {
let flag = cur.read_u8()?;
match flag {
0 => Ok(None),
1 => {
let segment_id = crate::format::SegmentId(cur.read_u64()?);
let offset = cur.read_u64()?;
let length = cur.read_u64()?;
let checksum = cur.read_array::<32>()?;
Ok(Some(SegmentRef {
segment_id,
offset,
length,
checksum,
}))
}
other => Err(Error::Format(format!(
"PostingsSegment previous_root presence flag must be 0 or 1, got {other}"
))),
}
}
struct Cursor<'a> {
bytes: &'a [u8],
pos: usize,
}
impl<'a> Cursor<'a> {
fn new(bytes: &'a [u8]) -> Self {
Self { bytes, pos: 0 }
}
fn remaining(&self) -> usize {
self.bytes.len() - self.pos
}
fn is_empty(&self) -> bool {
self.pos == self.bytes.len()
}
fn read_array<const N: usize>(&mut self) -> Result<[u8; N]> {
if self.pos + N > self.bytes.len() {
return Err(Error::Format(format!(
"PostingsSegment truncated: need {N} bytes at offset {}",
self.pos
)));
}
let mut out = [0u8; N];
out.copy_from_slice(&self.bytes[self.pos..self.pos + N]);
self.pos += N;
Ok(out)
}
fn read_u8(&mut self) -> Result<u8> {
Ok(self.read_array::<1>()?[0])
}
fn read_u16(&mut self) -> Result<u16> {
Ok(u16::from_le_bytes(self.read_array::<2>()?))
}
fn read_u32(&mut self) -> Result<u32> {
Ok(u32::from_le_bytes(self.read_array::<4>()?))
}
fn read_u64(&mut self) -> Result<u64> {
Ok(u64::from_le_bytes(self.read_array::<8>()?))
}
fn pos(&self) -> usize {
self.pos
}
fn advance(&mut self, n: usize) -> Result<()> {
if self.pos + n > self.bytes.len() {
return Err(Error::Format(format!(
"PostingsSegment truncated: need to advance {n} from offset {}",
self.pos
)));
}
self.pos += n;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::format::SegmentId;
fn posting(frame_id: u64, collection_id: u32, field_mask: u32, tf: u32) -> Posting {
Posting {
frame_id: FrameId(frame_id),
collection_id: CollectionId(collection_id),
field_mask,
term_freq: tf,
positions_ref: None,
}
}
fn list(term_id: u32, df: u32, postings: Vec<Posting>) -> PostingList {
PostingList {
term_id: TermId(term_id),
df,
postings,
}
}
#[test]
fn roundtrip_empty_segment() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: Vec::new(),
};
let bytes = encode_postings_segment(&seg).unwrap();
let decoded = decode_postings_segment(&bytes).unwrap();
assert_eq!(decoded, seg);
}
#[test]
fn roundtrip_multi_list_with_previous_root() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(7),
previous_root: Some(SegmentRef {
segment_id: SegmentId(99),
offset: 1024,
length: 256,
checksum: [0xCD; 32],
}),
posting_lists: vec![
list(
1,
3,
vec![
posting(3, 1, 0b001, 5),
posting(5, 1, 0b001, 2),
posting(100, 2, 0b011, 10),
],
),
list(
2,
2,
vec![posting(7, 1, 0b001, 1), posting(7000, 2, 0b010, 4)],
),
list(3, 0, vec![]),
],
};
let bytes = encode_postings_segment(&seg).unwrap();
let decoded = decode_postings_segment(&bytes).unwrap();
assert_eq!(decoded, seg);
}
#[test]
fn roundtrip_large_frame_ids() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: vec![list(
1,
3,
vec![
posting(1, 1, 0, 1),
posting(1_000_000, 1, 0, 1),
posting(1_000_000_000_000, 1, 0, 1),
],
)],
};
let bytes = encode_postings_segment(&seg).unwrap();
let decoded = decode_postings_segment(&bytes).unwrap();
assert_eq!(decoded, seg);
}
#[test]
fn rejects_non_ascending_frame_ids() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: vec![list(1, 2, vec![posting(10, 1, 0, 1), posting(5, 1, 0, 1)])],
};
let err = encode_postings_segment(&seg).expect_err("non-ascending");
assert!(err.to_string().contains("ascending"));
}
#[test]
fn rejects_duplicate_frame_ids() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: vec![list(1, 2, vec![posting(7, 1, 0, 1), posting(7, 1, 0, 1)])],
};
let err = encode_postings_segment(&seg).expect_err("duplicate");
assert!(err.to_string().contains("ascending"));
}
#[test]
fn rejects_magic_mismatch() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: vec![list(1, 1, vec![posting(1, 1, 0, 1)])],
};
let mut bytes = encode_postings_segment(&seg).unwrap();
bytes[0] = b'X';
let err = decode_postings_segment(&bytes).expect_err("magic");
assert!(err.to_string().contains("magic"));
}
#[test]
fn rejects_version_mismatch() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: vec![list(1, 1, vec![posting(1, 1, 0, 1)])],
};
let mut bytes = encode_postings_segment(&seg).unwrap();
bytes[4..6].copy_from_slice(&99u16.to_le_bytes());
let err = decode_postings_segment(&bytes).expect_err("version");
assert!(err.to_string().contains("version"));
}
#[test]
fn rejects_trailing_bytes() {
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: vec![list(1, 1, vec![posting(1, 1, 0, 1)])],
};
let mut bytes = encode_postings_segment(&seg).unwrap();
bytes.push(0xAB);
let err = decode_postings_segment(&bytes).expect_err("trailing");
assert!(err.to_string().contains("trailing"));
}
#[test]
fn tf_exception_saves_one_byte_per_tf1_posting() {
let n: u64 = 1_000;
let mut postings: Vec<Posting> = Vec::with_capacity(n as usize);
let mut frame = 100u64;
for i in 0..n {
let tf = if i % 20 == 0 { 3 } else { 1 };
postings.push(posting(frame, 1, 0b1, tf));
frame += 500;
}
let seg = PostingsSegment {
text_space_id: TextSpaceId(1),
previous_root: None,
posting_lists: vec![list(1, n as u32, postings.clone())],
};
let bytes = encode_postings_segment(&seg).unwrap();
let decoded = decode_postings_segment(&bytes).unwrap();
assert_eq!(decoded.posting_lists[0].postings, postings);
let posting_count = n as usize;
let exceptions = postings.iter().filter(|p| p.term_freq > 1).count();
let tf1_savings = posting_count - exceptions; assert!(
bytes.len() + tf1_savings > bytes.len() + 900,
"tf1 savings should clear 900 B — got savings = {tf1_savings}"
);
let blob_start_signature = bytes.windows(4).position(|w| w == MAGIC).unwrap();
assert_eq!(blob_start_signature, 0);
}
#[test]
fn varint_round_trip_edge_cases() {
for value in [0u64, 1, 0x7F, 0x80, 0x3FFF, 0x4000, (1u64 << 40), u64::MAX] {
let mut buf = Vec::new();
write_varint_u64(&mut buf, value);
let mut cur = Cursor::new(&buf);
let decoded = read_varint_u64(&mut cur).unwrap();
assert_eq!(decoded, value);
assert!(cur.is_empty());
}
}
}