use std::collections::BTreeSet;
use std::fs::File;
use std::io::Read;
use std::path::{Path, PathBuf};
use crate::error::{Neo4jStoreError, Result};
use super::page::{PageLayout, RecordReader, PAGE_SIZE};
use super::Neo4jStoreFormat;
pub(super) const HEADER_SIZE: usize = 8;
pub(super) const NO_NEXT_BLOCK: u32 = u32::MAX;
#[derive(Clone, Copy, Debug)]
pub(super) struct DynamicStoreLayout {
pub(super) record_size: usize,
pub(super) payload_size: usize,
pub(super) record_capacity: u64,
}
pub(super) fn store_layout(path: &Path, format: Neo4jStoreFormat) -> Result<DynamicStoreLayout> {
let record_size = read_record_size(path)?;
let layout = PageLayout::new(path, format, record_size)?;
let file_size = std::fs::metadata(path)
.map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?
.len();
Ok(DynamicStoreLayout {
record_size,
payload_size: record_size - HEADER_SIZE,
record_capacity: layout.record_count(file_size),
})
}
pub(super) fn encode_append_only_chain(
data: &[u8],
first_id: u64,
layout: DynamicStoreLayout,
) -> std::result::Result<Vec<(u64, Vec<u8>)>, String> {
if data.is_empty() {
return Err("dynamic record chain cannot be empty".to_owned());
}
let record_count = data.len().div_ceil(layout.payload_size);
let end_id = first_id
.checked_add(record_count as u64)
.ok_or_else(|| "dynamic record ID overflow".to_owned())?;
if end_id > layout.record_capacity {
return Err(format!(
"dynamic store needs record IDs {first_id}..{end_id}, beyond physical capacity {}",
layout.record_capacity
));
}
let ids = (first_id..end_id).collect::<Vec<_>>();
encode_chain_for_ids(data, &ids, layout)
}
pub(super) fn encode_chain_for_ids(
data: &[u8],
ids: &[u64],
layout: DynamicStoreLayout,
) -> std::result::Result<Vec<(u64, Vec<u8>)>, String> {
if data.is_empty() {
return Err("dynamic record chain cannot be empty".to_owned());
}
let required_records = data.len().div_ceil(layout.payload_size);
if required_records != ids.len() {
return Err(format!(
"dynamic value needs {required_records} records but the existing chain has {}",
ids.len()
));
}
if ids.iter().any(|id| *id >= layout.record_capacity) {
return Err("dynamic record chain exceeds physical store capacity".to_owned());
}
data.chunks(layout.payload_size)
.enumerate()
.map(|(index, chunk)| {
let id = ids[index];
let next = ids.get(index + 1).copied();
let next_value = next.unwrap_or(NO_NEXT_BLOCK as u64);
if next_value > 0x0f_ffff_ffff {
return Err(format!(
"dynamic record reference {next_value} exceeds 36 bits"
));
}
let mut bytes = vec![0_u8; layout.record_size];
bytes[0] = 0x10 | if index == 0 { 0 } else { 0x80 } | ((next_value >> 32) as u8 & 0x0f);
bytes[1] = ((chunk.len() >> 16) & 0xff) as u8;
bytes[2] = ((chunk.len() >> 8) & 0xff) as u8;
bytes[3] = (chunk.len() & 0xff) as u8;
bytes[4..8].copy_from_slice(&(next_value as u32).to_be_bytes());
bytes[HEADER_SIZE..HEADER_SIZE + chunk.len()].copy_from_slice(chunk);
Ok((id, bytes))
})
.collect()
}
pub(super) fn prepare_chain_deletion(
path: &Path,
format: Neo4jStoreFormat,
record_type: &str,
first_id: u64,
context: &str,
) -> Result<Vec<(u64, Vec<u8>)>> {
let mut store = DynamicStore::open(path, format, record_type)?;
let (_, record_ids) = store.read_chain_with_ids(first_id, context)?;
record_ids
.into_iter()
.map(|record_id| {
let mut bytes = store.reader.read(record_id)?.to_vec();
bytes[0] &= !0x10;
Ok((record_id, bytes))
})
.collect()
}
pub(super) fn prepare_record_deletions(
path: &Path,
format: Neo4jStoreFormat,
record_type: &str,
record_ids: &[u64],
context: &str,
) -> Result<Vec<(u64, Vec<u8>)>> {
let mut store = DynamicStore::open(path, format, record_type)?;
record_ids
.iter()
.map(|record_id| {
let mut bytes = store.reader.read(*record_id)?.to_vec();
if bytes[0] & 0x10 == 0 {
return Err(store.invalid(*record_id, context, "dynamic record is not in use"));
}
bytes[0] &= !0x10;
Ok((*record_id, bytes))
})
.collect()
}
pub(super) struct DynamicStore {
reader: RecordReader,
record_type: String,
payload_size: usize,
}
impl DynamicStore {
pub(super) fn open(
path: &Path,
format: Neo4jStoreFormat,
record_type: impl Into<String>,
) -> Result<Self> {
let record_size = read_record_size(path)?;
let layout = PageLayout::new(path, format, record_size)?;
let record_type = record_type.into();
Ok(Self {
reader: RecordReader::open(path, record_type.clone(), layout)?,
record_type,
payload_size: record_size - HEADER_SIZE,
})
}
pub(super) fn read_chain(&mut self, first_id: u64, context: &str) -> Result<Vec<u8>> {
self.read_chain_with_ids(first_id, context)
.map(|(value, _)| value)
}
pub(super) fn read_chain_with_ids(
&mut self,
first_id: u64,
context: &str,
) -> Result<(Vec<u8>, Vec<u64>)> {
let mut id = first_id;
let mut first = true;
let mut seen = BTreeSet::new();
let mut value = Vec::new();
let mut record_ids = Vec::new();
loop {
if !seen.insert(id) {
return Err(self.invalid(
id,
context,
format!("dynamic chain cycle at record {id}"),
));
}
record_ids.push(id);
if id >= self.reader.record_count() {
return Err(self.invalid(
id,
context,
format!(
"dynamic chain points outside store containing {} records",
self.reader.record_count()
),
));
}
let bytes = self.reader.read(id)?;
let header = bytes[0];
if header & 0x10 == 0 {
return Err(self.invalid(id, context, "dynamic record is not in use"));
}
let is_start = header & 0x80 == 0;
if is_start != first {
let expected = if first { "start" } else { "linked" };
return Err(self.invalid(
id,
context,
format!("expected a {expected} dynamic record"),
));
}
let length = read_u24(&bytes[1..4]) as usize;
if length > self.payload_size {
return Err(self.invalid(
id,
context,
format!(
"payload length {length} exceeds dynamic record capacity {}",
self.payload_size
),
));
}
let low_next = read_u32(&bytes[4..8]);
let high_next = (header & 0x0f) as u64;
let next = if high_next == 0 && low_next == NO_NEXT_BLOCK {
None
} else {
Some((high_next << 32) | low_next as u64)
};
if next.is_some() && length != self.payload_size {
return Err(self.invalid(
id,
context,
format!(
"non-terminal dynamic record uses {length} of {} payload bytes",
self.payload_size
),
));
}
value.extend_from_slice(&bytes[HEADER_SIZE..HEADER_SIZE + length]);
match next {
Some(next_id) => {
id = next_id;
first = false;
}
None => return Ok((value, record_ids)),
}
}
}
pub(super) fn invalid(
&self,
record_id: u64,
context: &str,
message: impl Into<String>,
) -> crate::Error {
let offset = self.reader.offset(record_id).unwrap_or(u64::MAX);
Neo4jStoreError::InvalidRecord {
path: PathBuf::from(self.reader.path()),
record_type: self.record_type.clone(),
record_id,
offset,
context: context.to_owned(),
message: message.into(),
}
.into()
}
}
fn read_record_size(path: &Path) -> Result<usize> {
let mut file = File::open(path).map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?;
let mut bytes = [0_u8; 4];
file.read_exact(&mut bytes)
.map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?;
let record_size = u32::from_be_bytes(bytes) as usize;
if !(HEADER_SIZE + 1..=PAGE_SIZE).contains(&record_size) {
return Err(Neo4jStoreError::InvalidPageLayout {
path: path.to_path_buf(),
message: format!(
"dynamic record size {record_size} must be between {} and {PAGE_SIZE}",
HEADER_SIZE + 1
),
}
.into());
}
Ok(record_size)
}
fn read_u24(bytes: &[u8]) -> u32 {
(bytes[0] as u32) << 16 | (bytes[1] as u32) << 8 | bytes[2] as u32
}
pub(super) fn read_u32(bytes: &[u8]) -> u32 {
u32::from_be_bytes(bytes.try_into().expect("caller provides four bytes"))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn encodes_and_reads_an_append_only_dynamic_chain() {
for format in [
Neo4jStoreFormat::StandardV5_0,
Neo4jStoreFormat::AlignedV5_0,
] {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("strings");
let record_size = 16_usize;
let page_layout = PageLayout::new(&path, format, record_size).unwrap();
let capacity = 8_u64;
let file_len = page_layout.offset(capacity - 1, &path).unwrap() as usize + record_size;
let mut file = vec![0_u8; file_len];
file[..4].copy_from_slice(&(record_size as u32).to_be_bytes());
std::fs::write(&path, file).unwrap();
let layout = store_layout(&path, format).unwrap();
let value = "dynamic UTF-8 value: 世界".as_bytes();
let records = encode_append_only_chain(value, 1, layout).unwrap();
let mut file = std::fs::read(&path).unwrap();
for (record_id, bytes) in records {
let offset = page_layout.offset(record_id, &path).unwrap() as usize;
file[offset..offset + record_size].copy_from_slice(&bytes);
}
std::fs::write(&path, file).unwrap();
let mut store = DynamicStore::open(&path, format, "test string").unwrap();
assert_eq!(store.read_chain(1, "test").unwrap(), value);
}
}
#[test]
fn prepares_every_record_in_a_dynamic_chain_for_deletion() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("dynamic.db");
let record_size = 16;
let layout = DynamicStoreLayout {
record_size,
payload_size: record_size - HEADER_SIZE,
record_capacity: 8,
};
let mut bytes = vec![0_u8; PAGE_SIZE];
bytes[..4].copy_from_slice(&(record_size as u32).to_be_bytes());
for (id, record) in encode_append_only_chain(b"delete-this-chain", 1, layout).unwrap() {
let offset = id as usize * record_size;
bytes[offset..offset + record_size].copy_from_slice(&record);
}
std::fs::write(&path, bytes).unwrap();
let records = prepare_chain_deletion(
&path,
Neo4jStoreFormat::StandardV5_0,
"dynamic test",
1,
"delete test",
)
.unwrap();
assert_eq!(records.len(), 3);
assert_eq!(
records.iter().map(|(id, _)| *id).collect::<Vec<_>>(),
[1, 2, 3]
);
assert!(records.iter().all(|(_, bytes)| bytes[0] & 0x10 == 0));
}
#[test]
fn rejects_a_chain_beyond_preallocated_capacity() {
let layout = DynamicStoreLayout {
record_size: 16,
payload_size: 8,
record_capacity: 3,
};
let error = encode_append_only_chain(&[1_u8; 17], 1, layout).unwrap_err();
assert!(error.contains("beyond physical capacity"));
}
#[test]
fn rewrites_an_existing_non_consecutive_chain() {
let layout = DynamicStoreLayout {
record_size: 16,
payload_size: 8,
record_capacity: 20,
};
let records = encode_chain_for_ids(&[b'x'; 17], &[3, 9, 14], layout).unwrap();
assert_eq!(
records.iter().map(|record| record.0).collect::<Vec<_>>(),
[3, 9, 14]
);
assert_eq!(read_u32(&records[0].1[4..8]), 9);
assert_eq!(read_u32(&records[1].1[4..8]), 14);
assert_eq!(read_u32(&records[2].1[4..8]), NO_NEXT_BLOCK);
let error = encode_chain_for_ids(&[b'x'; 9], &[3], layout).unwrap_err();
assert!(error.contains("needs 2 records"));
}
}