use std::fs::File;
use std::io::{Read, Seek, SeekFrom};
use std::path::Path;
use crate::error::{Neo4jStoreError, Result};
const PAGE_SIZE: usize = 8192;
const META_PAGE_ID: usize = 0;
const STATE_PAGE_IDS: [usize; 2] = [1, 2];
const STATE_FIELDS_SIZE: usize = 57;
const STATE_SIZE: usize = STATE_FIELDS_SIZE * 2;
const BASE_HEADER_SIZE: usize = 82;
const KEY_SIZE: usize = 13;
const VALUE_SIZE: usize = 8;
const MAX_KEY_COUNT: usize = (PAGE_SIZE - BASE_HEADER_SIZE) / (KEY_SIZE + VALUE_SIZE);
const COUNTS_LAYOUT_IDENTIFIER: [u8; 8] = [b'C', b'o', b'L', b'a', 0, 0, 3, 0xdb];
const TREE_NODE: u8 = 1;
const LEAF_NODE: u8 = 1;
const DATA_LAYER: u8 = 0;
const NODE_COUNT_KEY_TYPE: u8 = 1;
const RELATIONSHIP_COUNT_KEY_TYPE: u8 = 2;
const RELATIONSHIP_GROUP_DEGREE_KEY_TYPE: u8 = 3;
pub(super) fn empty_file(include_total_node_count: bool) -> Vec<u8> {
let mut bytes = vec![0_u8; PAGE_SIZE * 6];
bytes[4..8].copy_from_slice(&(PAGE_SIZE as u32).to_be_bytes());
bytes[8..16].copy_from_slice(&COUNTS_LAYOUT_IDENTIFIER);
write_empty_state(&mut bytes, 1, 5, true);
write_empty_state(&mut bytes, 2, 5, false);
let root = &mut bytes[5 * PAGE_SIZE..6 * PAGE_SIZE];
root[0] = TREE_NODE;
root[1] = LEAF_NODE;
root[2..6].copy_from_slice(&4_u32.to_be_bytes());
if include_total_node_count {
root[6..10].copy_from_slice(&1_u32.to_be_bytes());
root[BASE_HEADER_SIZE] = NODE_COUNT_KEY_TYPE;
root[BASE_HEADER_SIZE + 1..BASE_HEADER_SIZE + 9].copy_from_slice(&u64::MAX.to_be_bytes());
}
bytes
}
fn write_empty_state(bytes: &mut [u8], page_id: usize, unstable: u32, clean: bool) {
let offset = page_id * PAGE_SIZE;
let fields = &mut bytes[offset..offset + STATE_FIELDS_SIZE];
fields[0..4].copy_from_slice(&4_u32.to_be_bytes());
fields[4..8].copy_from_slice(&unstable.to_be_bytes());
fields[8..16].copy_from_slice(&5_u64.to_be_bytes());
fields[16..24].copy_from_slice(&4_u64.to_be_bytes());
fields[24..32].copy_from_slice(&5_u64.to_be_bytes());
fields[56] = u8::from(clean);
let fields = fields.to_vec();
bytes[offset + STATE_FIELDS_SIZE..offset + STATE_SIZE].copy_from_slice(&fields);
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(super) struct RelationshipCountKey {
pub(super) start_label_id: i32,
pub(super) type_id: i32,
pub(super) end_label_id: i32,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(super) struct RelationshipGroupDegreeKey {
pub(super) group_id: u64,
pub(super) direction: u8,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct CountEntry {
pub(super) value_offset: u64,
pub(super) count: u64,
}
#[derive(Debug, PartialEq, Eq)]
pub(super) struct CountsUpdate {
pub(super) root_page_offset: u64,
pub(super) root_page: Vec<u8>,
}
#[derive(Clone, Copy, Debug)]
struct TreeState {
page_id: usize,
stable_generation: u32,
unstable_generation: u32,
root_id: u64,
root_generation: u64,
last_id: u64,
clean: bool,
valid: bool,
}
pub(super) fn locate_node_count(path: &Path, label_id: i32) -> Result<CountEntry> {
let (_, state, root_offset, root) = read_tree(path)?;
validate_root(path, root_offset, &root, state.root_generation)?;
let key_count = read_u32(&root, 6) as usize;
let target_first = label_id as i64 as u64;
for position in 0..key_count {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let key = &root[key_offset..key_offset + KEY_SIZE];
if key[0] == NODE_COUNT_KEY_TYPE
&& read_u64(key, 1) == target_first
&& read_u32(key, 9) == 0
{
let value_in_page = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE + position * VALUE_SIZE;
let count = read_u64(&root, value_in_page);
return Ok(CountEntry {
value_offset: (root_offset + value_in_page) as u64,
count,
});
}
}
Err(invalid(
path,
root_offset,
format!("counts tree has no node-count entry for label ID {label_id}"),
))
}
pub(super) fn locate_relationship_count(
path: &Path,
target: RelationshipCountKey,
) -> Result<CountEntry> {
let (_, state, root_offset, root) = read_tree(path)?;
validate_root(path, root_offset, &root, state.root_generation)?;
let key_count = read_u32(&root, 6) as usize;
let target = relationship_key(target);
for position in 0..key_count {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
if root[key_offset..key_offset + KEY_SIZE] == target {
let value_in_page = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE + position * VALUE_SIZE;
return Ok(CountEntry {
value_offset: (root_offset + value_in_page) as u64,
count: read_u64(&root, value_in_page),
});
}
}
Err(invalid(
path,
root_offset,
"counts tree has no requested relationship-count entry",
))
}
pub(super) fn validate_relationship_group_degrees(path: &Path) -> Result<()> {
let (_, selected, root_offset, root) = read_tree(path)?;
validate_root(path, root_offset, &root, selected.root_generation)?;
let key_count = read_u32(&root, 6) as usize;
for position in 0..key_count {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let key = &root[key_offset..key_offset + KEY_SIZE];
if key[0] != RELATIONSHIP_GROUP_DEGREE_KEY_TYPE || read_u32(key, 9) != 0 {
return Err(invalid(
path,
root_offset + key_offset,
"relationship group degree tree contains an invalid key",
));
}
if read_u64(key, 1) & 3 > 2 {
return Err(invalid(
path,
root_offset + key_offset,
"relationship group degree key has an invalid direction",
));
}
}
Ok(())
}
pub(super) fn prepare_node_count_increment(
path: &Path,
label_id: i32,
increment: u64,
) -> Result<CountsUpdate> {
prepare_node_count_increments(path, &[(label_id, increment)])
}
pub(super) fn prepare_node_count_increments(
path: &Path,
increments: &[(i32, u64)],
) -> Result<CountsUpdate> {
if increments.is_empty() || increments.iter().any(|(_, increment)| *increment == 0) {
return Err(invalid(
path,
0,
"counts increment must be greater than zero",
));
}
let deltas = increments
.iter()
.map(|(label_id, increment)| {
i64::try_from(*increment)
.map(|increment| (*label_id, increment))
.map_err(|_| invalid(path, 0, "counts increment exceeds i64"))
})
.collect::<Result<Vec<_>>>()?;
prepare_node_count_deltas(path, &deltas)
}
pub(super) fn prepare_node_count_deltas(
path: &Path,
deltas: &[(i32, i64)],
) -> Result<CountsUpdate> {
prepare_node_count_changes(path, deltas, &[])
}
pub(super) fn prepare_node_count_changes(
path: &Path,
deltas: &[(i32, i64)],
insert_missing: &[i32],
) -> Result<CountsUpdate> {
prepare_counts_changes(path, deltas, insert_missing, &[], &[])
}
pub(super) fn prepare_relationship_group_degree_changes(
path: &Path,
deltas: &[(RelationshipGroupDegreeKey, i64)],
) -> Result<CountsUpdate> {
prepare_counts_changes(path, &[], &[], &[], deltas)
}
pub(super) fn prepare_counts_changes(
path: &Path,
node_deltas: &[(i32, i64)],
insert_missing_node_keys: &[i32],
relationship_deltas: &[(RelationshipCountKey, i64)],
relationship_group_degree_deltas: &[(RelationshipGroupDegreeKey, i64)],
) -> Result<CountsUpdate> {
let mut changes = node_deltas
.iter()
.map(|(label_id, delta)| (node_key(*label_id), *delta, false))
.chain(
relationship_deltas
.iter()
.map(|(key, delta)| (relationship_key(*key), *delta, true)),
)
.chain(
relationship_group_degree_deltas
.iter()
.map(|(key, delta)| {
relationship_group_degree_key(path, *key).map(|key| (key, *delta, true))
})
.collect::<Result<Vec<_>>>()?,
)
.collect::<Vec<_>>();
if changes.is_empty() || changes.iter().any(|(_, delta, _)| *delta == 0) {
return Err(invalid(path, 0, "counts delta must be non-zero"));
}
changes.sort_unstable_by(|(left, _, _), (right, _, _)| compare_keys(left, right));
if changes.windows(2).any(|pair| pair[0].0 == pair[1].0) {
return Err(invalid(
path,
0,
"counts increments contain a duplicate key",
));
}
let (file_len, selected, root_offset, mut new_root) = read_tree(path)?;
let expected_pages = selected
.last_id
.checked_add(1)
.ok_or_else(|| invalid(path, 0, "counts tree last page ID overflow"))?;
let expected_length = expected_pages
.checked_mul(PAGE_SIZE as u64)
.ok_or_else(|| invalid(path, 0, "counts tree file length overflow"))?;
if file_len != expected_length {
return Err(invalid(
path,
0,
"counts tree file length does not end at its last allocated page",
));
}
validate_root(path, root_offset, &new_root, selected.root_generation)?;
let key_count = read_u32(&new_root, 6) as usize;
let mut entries = (0..key_count)
.map(|position| {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let value_offset = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE + position * VALUE_SIZE;
let key: [u8; KEY_SIZE] = new_root[key_offset..key_offset + KEY_SIZE]
.try_into()
.expect("validated fixed-size counts key");
let value = read_u64(&new_root, value_offset);
(key, value)
})
.collect::<Vec<_>>();
for (key, delta, insert_missing_relationship_key) in changes {
let position = entries.iter().position(|(existing, _)| *existing == key);
let count = position.map(|position| entries[position].1).unwrap_or(0);
let insert_missing_node_key = key[0] == NODE_COUNT_KEY_TYPE
&& insert_missing_node_keys.contains(&(read_u64(&key, 1) as i64 as i32));
if position.is_none() && !insert_missing_node_key && !insert_missing_relationship_key {
let message = if key[0] == NODE_COUNT_KEY_TYPE {
format!(
"counts tree has no node-count entry for label ID {}",
read_u64(&key, 1) as i64
)
} else {
"counts tree has no entry for a requested count key".to_owned()
};
return Err(invalid(path, root_offset, message));
}
if position.is_none() && delta < 0 {
return Err(invalid(
path,
root_offset,
"cannot insert a counts key with a negative value",
));
}
let count =
i64::try_from(count).map_err(|_| invalid(path, root_offset, "count exceeds i64"))?;
let next_count = count
.checked_add(delta)
.filter(|count| *count >= 0)
.ok_or_else(|| invalid(path, root_offset, "count overflow or underflow"))?
as u64;
if let Some(position) = position {
entries[position].1 = next_count;
} else {
entries.push((key, next_count));
}
}
entries.sort_unstable_by(|(left, _), (right, _)| compare_keys(left, right));
if entries.len() > MAX_KEY_COUNT {
return Err(invalid(
path,
root_offset,
"counts leaf has no capacity for a new key",
));
}
new_root[6..10].copy_from_slice(&(entries.len() as u32).to_be_bytes());
let key_area_end = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE;
let value_area_end = key_area_end + MAX_KEY_COUNT * VALUE_SIZE;
new_root[BASE_HEADER_SIZE..key_area_end].fill(0);
new_root[key_area_end..value_area_end].fill(0);
for (position, (key, value)) in entries.into_iter().enumerate() {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
new_root[key_offset..key_offset + KEY_SIZE].copy_from_slice(&key);
let value_offset = key_area_end + position * VALUE_SIZE;
new_root[value_offset..value_offset + VALUE_SIZE].copy_from_slice(&value.to_be_bytes());
}
Ok(CountsUpdate {
root_page_offset: root_offset as u64,
root_page: new_root,
})
}
fn node_key(label_id: i32) -> [u8; KEY_SIZE] {
let mut key = [0_u8; KEY_SIZE];
key[0] = NODE_COUNT_KEY_TYPE;
key[1..9].copy_from_slice(&(label_id as i64).to_be_bytes());
key
}
fn relationship_key(value: RelationshipCountKey) -> [u8; KEY_SIZE] {
let mut key = [0_u8; KEY_SIZE];
key[0] = RELATIONSHIP_COUNT_KEY_TYPE;
let first = ((value.start_label_id as u32 as u64) << 32) | value.type_id as u32 as u64;
key[1..9].copy_from_slice(&first.to_be_bytes());
key[9..13].copy_from_slice(&value.end_label_id.to_be_bytes());
key
}
fn relationship_group_degree_key(
path: &Path,
value: RelationshipGroupDegreeKey,
) -> Result<[u8; KEY_SIZE]> {
if value.direction > 2 {
return Err(invalid(
path,
0,
"relationship group degree direction must be 0, 1, or 2",
));
}
let first = value
.group_id
.checked_shl(2)
.and_then(|group| group.checked_add(value.direction as u64))
.filter(|first| *first <= i64::MAX as u64)
.ok_or_else(|| {
invalid(
path,
0,
"relationship group ID exceeds the degree key range",
)
})?;
let mut key = [0_u8; KEY_SIZE];
key[0] = RELATIONSHIP_GROUP_DEGREE_KEY_TYPE;
key[1..9].copy_from_slice(&first.to_be_bytes());
Ok(key)
}
fn compare_keys(left: &[u8; KEY_SIZE], right: &[u8; KEY_SIZE]) -> std::cmp::Ordering {
(left[0] as i8)
.cmp(&(right[0] as i8))
.then_with(|| (read_u64(left, 1) as i64).cmp(&(read_u64(right, 1) as i64)))
.then_with(|| (read_u32(left, 9) as i32).cmp(&(read_u32(right, 9) as i32)))
}
fn read_tree(path: &Path) -> Result<(u64, TreeState, usize, Vec<u8>)> {
let mut file = File::open(path).map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?;
let file_len = file
.metadata()
.map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?
.len();
let metadata = read_region(
&mut file,
path,
0,
PAGE_SIZE,
0,
"counts tree metadata page is truncated",
)?;
validate_metadata(path, &metadata)?;
let mut states = Vec::with_capacity(STATE_PAGE_IDS.len());
for page_id in STATE_PAGE_IDS {
let offset = page_id
.checked_mul(PAGE_SIZE)
.ok_or_else(|| invalid(path, 0, "counts tree state page offset overflow"))?;
let page = read_region(
&mut file,
path,
offset as u64,
STATE_SIZE,
offset,
"counts tree state page is truncated",
)?;
states.push(read_state(&page, page_id));
}
let selected = select_state(path, states[0], states[1])?;
if selected.root_id > selected.last_id {
return Err(invalid(
path,
selected.page_id * PAGE_SIZE + 8,
"counts tree root page ID is beyond the last allocated page",
));
}
let root_offset = usize::try_from(selected.root_id)
.ok()
.and_then(|id| id.checked_mul(PAGE_SIZE))
.ok_or_else(|| invalid(path, 0, "counts tree root page offset overflow"))?;
let root = read_region(
&mut file,
path,
root_offset as u64,
PAGE_SIZE,
root_offset,
"counts tree root page is truncated",
)?;
Ok((file_len, selected, root_offset, root))
}
fn read_region(
file: &mut File,
path: &Path,
offset: u64,
len: usize,
invalid_offset: usize,
truncated_message: &str,
) -> Result<Vec<u8>> {
file.seek(SeekFrom::Start(offset))
.map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?;
let mut bytes = vec![0_u8; len];
let mut actual = 0;
while actual < len {
match file.read(&mut bytes[actual..]) {
Ok(0) => return Err(invalid(path, invalid_offset, truncated_message)),
Ok(count) => actual += count,
Err(source) if source.kind() == std::io::ErrorKind::Interrupted => {}
Err(source) => {
return Err(Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
}
.into());
}
}
}
Ok(bytes)
}
fn validate_root(path: &Path, root_offset: usize, root: &[u8], root_generation: u64) -> Result<()> {
if root[0] != TREE_NODE || root[1] & 0x0f != LEAF_NODE || (root[1] >> 4) & 0x0f != DATA_LAYER {
return Err(invalid(
path,
root_offset,
"counts tree root is not a single data leaf",
));
}
if read_u32(root, 2) as u64 != root_generation {
return Err(invalid(
path,
root_offset + 2,
"counts tree root generation does not match the selected state",
));
}
let key_count = read_u32(root, 6) as usize;
if key_count > MAX_KEY_COUNT {
return Err(invalid(
path,
root_offset + 6,
"counts leaf key count exceeds fixed-size page capacity",
));
}
let mut previous_key = None;
for position in 0..key_count {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let key: &[u8; KEY_SIZE] = root[key_offset..key_offset + KEY_SIZE]
.try_into()
.expect("validated fixed-size counts key");
if previous_key.is_some_and(|previous| compare_keys(&previous, key).is_ge()) {
return Err(invalid(
path,
root_offset + key_offset,
"counts leaf keys are not strictly increasing",
));
}
previous_key = Some(*key);
}
Ok(())
}
fn validate_metadata(path: &Path, bytes: &[u8]) -> Result<()> {
let metadata = bytes
.get(META_PAGE_ID * PAGE_SIZE..(META_PAGE_ID + 1) * PAGE_SIZE)
.ok_or_else(|| invalid(path, 0, "counts tree metadata page is truncated"))?;
if read_u32(metadata, 4) as usize != PAGE_SIZE {
return Err(invalid(path, 4, "counts tree does not use 8192-byte pages"));
}
if metadata[8..16] != COUNTS_LAYOUT_IDENTIFIER {
return Err(invalid(path, 8, "unexpected counts tree layout identifier"));
}
Ok(())
}
fn read_state(state: &[u8], page_id: usize) -> TreeState {
let fields = &state[..STATE_FIELDS_SIZE];
let checksum = &state[STATE_FIELDS_SIZE..];
TreeState {
page_id,
stable_generation: read_u32(fields, 0),
unstable_generation: read_u32(fields, 4),
root_id: read_u64(fields, 8),
root_generation: read_u64(fields, 16),
last_id: read_u64(fields, 24),
clean: fields[56] == 1,
valid: fields == checksum && fields[..56].iter().any(|byte| *byte != 0),
}
}
fn select_state(path: &Path, a: TreeState, b: TreeState) -> Result<TreeState> {
match (a.valid, b.valid) {
(true, false) => Ok(a),
(false, true) => Ok(b),
(false, false) => Err(invalid(
path,
PAGE_SIZE,
"both counts tree state pages are invalid",
)),
(true, true)
if a.stable_generation == b.stable_generation
&& a.unstable_generation == b.unstable_generation
&& a.clean != b.clean =>
{
Ok(if a.clean { a } else { b })
}
(true, true)
if a.stable_generation >= b.stable_generation
&& a.unstable_generation > b.unstable_generation =>
{
Ok(a)
}
(true, true)
if b.stable_generation >= a.stable_generation
&& b.unstable_generation > a.unstable_generation =>
{
Ok(b)
}
_ => Err(invalid(
path,
a.page_id * PAGE_SIZE,
"counts tree state generations do not identify a newest page",
)),
}
}
fn read_u32(bytes: &[u8], offset: usize) -> u32 {
u32::from_be_bytes(
bytes[offset..offset + 4]
.try_into()
.expect("validated page field"),
)
}
fn read_u64(bytes: &[u8], offset: usize) -> u64 {
u64::from_be_bytes(
bytes[offset..offset + 8]
.try_into()
.expect("validated page field"),
)
}
fn invalid(path: &Path, offset: usize, message: impl Into<String>) -> crate::Error {
Neo4jStoreError::InvalidMetadata {
path: path.to_path_buf(),
offset: offset as u64,
message: message.into(),
}
.into()
}
#[cfg(test)]
mod tests {
use std::fs;
use super::*;
fn write_state(bytes: &mut [u8], page_id: usize, unstable: u32, clean: bool) {
let offset = page_id * PAGE_SIZE;
let fields = &mut bytes[offset..offset + STATE_FIELDS_SIZE];
fields[0..4].copy_from_slice(&4_u32.to_be_bytes());
fields[4..8].copy_from_slice(&unstable.to_be_bytes());
fields[8..16].copy_from_slice(&5_u64.to_be_bytes());
fields[16..24].copy_from_slice(&4_u64.to_be_bytes());
fields[24..32].copy_from_slice(&5_u64.to_be_bytes());
fields[56] = u8::from(clean);
let fields = fields.to_vec();
bytes[offset + STATE_FIELDS_SIZE..offset + STATE_SIZE].copy_from_slice(&fields);
}
fn counts_file(entries: &[(i32, u64)]) -> Vec<u8> {
let mut bytes = vec![0_u8; PAGE_SIZE * 6];
bytes[4..8].copy_from_slice(&(PAGE_SIZE as u32).to_be_bytes());
bytes[8..16].copy_from_slice(&COUNTS_LAYOUT_IDENTIFIER);
write_state(&mut bytes, 1, 5, true);
write_state(&mut bytes, 2, 5, false);
let root = &mut bytes[5 * PAGE_SIZE..6 * PAGE_SIZE];
root[0] = TREE_NODE;
root[1] = LEAF_NODE;
root[2..6].copy_from_slice(&4_u32.to_be_bytes());
root[6..10].copy_from_slice(&(entries.len() as u32).to_be_bytes());
for (position, (label_id, count)) in entries.iter().enumerate() {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
root[key_offset] = NODE_COUNT_KEY_TYPE;
root[key_offset + 1..key_offset + 9]
.copy_from_slice(&(*label_id as i64 as u64).to_be_bytes());
let value_offset = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE + position * VALUE_SIZE;
root[value_offset..value_offset + VALUE_SIZE].copy_from_slice(&count.to_be_bytes());
}
bytes
}
#[test]
fn locates_fixed_size_node_count_values() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
fs::write(&path, counts_file(&[(-1, 62), (0, 1)])).unwrap();
let total = locate_node_count(&path, -1).unwrap();
assert_eq!(total.count, 62);
assert_eq!(total.value_offset, (5 * PAGE_SIZE + 5100) as u64);
assert_eq!(locate_node_count(&path, 0).unwrap().count, 1);
}
#[test]
fn reads_and_updates_a_sparse_counts_tree_without_loading_the_file() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
let sparse_len = 1_u64 << 40;
let last_id = sparse_len / PAGE_SIZE as u64 - 1;
let mut bytes = counts_file(&[(-1, 62)]);
for page_id in STATE_PAGE_IDS {
let state_offset = page_id * PAGE_SIZE;
for copy_offset in [0, STATE_FIELDS_SIZE] {
bytes[state_offset + copy_offset + 24..state_offset + copy_offset + 32]
.copy_from_slice(&last_id.to_be_bytes());
}
}
fs::write(&path, bytes).unwrap();
let file = fs::OpenOptions::new().write(true).open(&path).unwrap();
file.set_len(sparse_len).unwrap();
assert_eq!(locate_node_count(&path, -1).unwrap().count, 62);
let update = prepare_node_count_increment(&path, -1, 1).unwrap();
assert_eq!(read_u64(&update.root_page, 5100), 63);
}
#[test]
fn prepares_node_count_decrements_and_rejects_underflow() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
fs::write(&path, counts_file(&[(0, 2), (1, 0)])).unwrap();
let update = prepare_node_count_deltas(&path, &[(0, -1)]).unwrap();
assert_eq!(read_u64(&update.root_page, 5100), 1);
assert!(prepare_node_count_deltas(&path, &[(1, -1)])
.unwrap_err()
.to_string()
.contains("underflow"));
}
#[test]
fn inserts_a_new_node_count_key_in_comparator_order() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
fs::write(&path, counts_file(&[(-1, 62), (0, 1), (2, 4)])).unwrap();
let update = prepare_node_count_changes(&path, &[(1, 1), (2, 1)], &[1]).unwrap();
assert_eq!(read_u32(&update.root_page, 6), 4);
for (position, expected) in [-1_i64, 0, 1, 2].into_iter().enumerate() {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
assert_eq!(read_u64(&update.root_page, key_offset + 1) as i64, expected);
}
let values = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE;
assert_eq!(read_u64(&update.root_page, values + 2 * VALUE_SIZE), 1);
assert_eq!(read_u64(&update.root_page, values + 3 * VALUE_SIZE), 5);
assert!(prepare_node_count_changes(&path, &[(3, 1)], &[])
.unwrap_err()
.to_string()
.contains("no node-count entry"));
}
#[test]
fn inserts_and_updates_relationship_count_keys() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
fs::write(&path, counts_file(&[(-1, 2)])).unwrap();
let wildcard = RelationshipCountKey {
start_label_id: -1,
type_id: -1,
end_label_id: -1,
};
let typed = RelationshipCountKey {
start_label_id: 3,
type_id: 7,
end_label_id: -1,
};
let update =
prepare_counts_changes(&path, &[], &[], &[(wildcard, 1), (typed, 2)], &[]).unwrap();
assert_eq!(read_u32(&update.root_page, 6), 3);
let values = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE;
assert_eq!(read_u64(&update.root_page, values), 2);
assert_eq!(read_u64(&update.root_page, values + VALUE_SIZE), 1);
assert_eq!(read_u64(&update.root_page, values + 2 * VALUE_SIZE), 2);
let wildcard_offset = BASE_HEADER_SIZE + KEY_SIZE;
assert_eq!(
update.root_page[wildcard_offset],
RELATIONSHIP_COUNT_KEY_TYPE
);
assert_eq!(read_u64(&update.root_page, wildcard_offset + 1), u64::MAX);
assert_eq!(read_u32(&update.root_page, wildcard_offset + 9), u32::MAX);
}
#[test]
fn inserts_and_updates_relationship_group_degree_keys() {
let directory = tempfile::tempdir().unwrap();
let path = directory
.path()
.join("neostore.relationshipgroupstore.degrees.db");
fs::write(&path, counts_file(&[(-1, 2)])).unwrap();
let key = RelationshipGroupDegreeKey {
group_id: 7,
direction: 2,
};
let update = prepare_relationship_group_degree_changes(&path, &[(key, 3)]).unwrap();
let key_offset = BASE_HEADER_SIZE + KEY_SIZE;
assert_eq!(
update.root_page[key_offset],
RELATIONSHIP_GROUP_DEGREE_KEY_TYPE
);
assert_eq!(read_u64(&update.root_page, key_offset + 1), (7 << 2) | 2);
let value_offset = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE + VALUE_SIZE;
assert_eq!(read_u64(&update.root_page, value_offset), 3);
let mut bytes = fs::read(&path).unwrap();
let offset = update.root_page_offset as usize;
bytes[offset..offset + PAGE_SIZE].copy_from_slice(&update.root_page);
fs::write(&path, bytes).unwrap();
let update = prepare_relationship_group_degree_changes(&path, &[(key, -1)]).unwrap();
assert_eq!(read_u64(&update.root_page, value_offset), 2);
}
#[test]
fn applies_relationship_group_degree_deltas_to_the_latest_root() {
let directory = tempfile::tempdir().unwrap();
let path = directory
.path()
.join("neostore.relationshipgroupstore.degrees.db");
fs::write(&path, counts_file(&[(-1, 2)])).unwrap();
let key = RelationshipGroupDegreeKey {
group_id: 11,
direction: 0,
};
for delta in [4, -1, -1] {
let update = prepare_relationship_group_degree_changes(&path, &[(key, delta)]).unwrap();
let mut bytes = fs::read(&path).unwrap();
let offset = update.root_page_offset as usize;
bytes[offset..offset + PAGE_SIZE].copy_from_slice(&update.root_page);
fs::write(&path, bytes).unwrap();
}
let update = prepare_relationship_group_degree_changes(&path, &[(key, -1)]).unwrap();
let value_offset = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE + VALUE_SIZE;
assert_eq!(read_u64(&update.root_page, value_offset), 1);
}
#[test]
fn rejects_invalid_relationship_group_degree_direction() {
let directory = tempfile::tempdir().unwrap();
let path = directory
.path()
.join("neostore.relationshipgroupstore.degrees.db");
fs::write(&path, counts_file(&[(-1, 2)])).unwrap();
let error = prepare_relationship_group_degree_changes(
&path,
&[(
RelationshipGroupDegreeKey {
group_id: 7,
direction: 3,
},
1,
)],
)
.unwrap_err();
assert!(error.to_string().contains("direction"));
}
#[test]
fn rejects_decrementing_a_missing_relationship_group_degree() {
let directory = tempfile::tempdir().unwrap();
let path = directory
.path()
.join("neostore.relationshipgroupstore.degrees.db");
fs::write(&path, counts_file(&[(-1, 2)])).unwrap();
let error = prepare_relationship_group_degree_changes(
&path,
&[(
RelationshipGroupDegreeKey {
group_id: 7,
direction: 0,
},
-1,
)],
)
.unwrap_err();
assert!(error
.to_string()
.contains("cannot insert a counts key with a negative value"));
}
#[test]
fn rejects_non_leaf_roots_and_missing_keys() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
let mut bytes = counts_file(&[(-1, 62)]);
bytes[5 * PAGE_SIZE + 1] = 0;
fs::write(&path, bytes).unwrap();
assert!(locate_node_count(&path, -1)
.unwrap_err()
.to_string()
.contains("not a single data leaf"));
fs::write(&path, counts_file(&[(-1, 62)])).unwrap();
assert!(locate_node_count(&path, 7)
.unwrap_err()
.to_string()
.contains("no node-count entry"));
}
#[test]
fn rejects_duplicate_and_descending_persisted_count_keys() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
for entries in [vec![(-1, 1), (-1, 2)], vec![(1, 1), (0, 2)]] {
fs::write(&path, counts_file(&entries)).unwrap();
let error = locate_node_count(&path, -1).unwrap_err();
assert!(error.to_string().contains("not strictly increasing"));
}
}
#[test]
fn rejects_a_root_page_beyond_the_last_allocated_page() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
let mut bytes = counts_file(&[(-1, 1)]);
bytes.resize(PAGE_SIZE * 7, 0);
for page_id in STATE_PAGE_IDS {
let state_offset = page_id * PAGE_SIZE;
for copy_offset in [0, STATE_FIELDS_SIZE] {
bytes[state_offset + copy_offset + 8..state_offset + copy_offset + 16]
.copy_from_slice(&6_u64.to_be_bytes());
}
}
fs::write(&path, bytes).unwrap();
let error = locate_node_count(&path, -1).unwrap_err();
assert!(error.to_string().contains("last allocated page"));
}
#[test]
fn prepares_journaled_in_place_node_count_update() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
fs::write(&path, counts_file(&[(-1, 62), (0, 1)])).unwrap();
let update = prepare_node_count_increments(&path, &[(-1, 1), (0, 1)]).unwrap();
assert_eq!(update.root_page.len(), PAGE_SIZE);
assert_eq!(read_u32(&update.root_page, 2), 4);
assert_eq!(read_u64(&update.root_page, 5100), 63);
assert_eq!(update.root_page_offset, (5 * PAGE_SIZE) as u64);
let update = prepare_node_count_increments(&path, &[(-1, 2), (0, 2)]).unwrap();
assert_eq!(read_u64(&update.root_page, 5100), 64);
assert_eq!(read_u64(&update.root_page, 5108), 3);
}
#[test]
fn commits_repeated_journaled_counts_updates_without_growing_the_tree() {
let directory = tempfile::tempdir().unwrap();
fs::write(directory.path().join("neostore"), b"counts-test-store").unwrap();
let path = directory.path().join("neostore.counts.db");
fs::write(&path, counts_file(&[(-1, 62), (0, 1)])).unwrap();
for expected in [63, 64] {
let update = prepare_node_count_increment(&path, -1, 1).unwrap();
let mut change_set =
super::super::transaction::ChangeSet::new(directory.path()).unwrap();
change_set
.overwrite(
"neostore.counts.db",
update.root_page_offset,
update.root_page,
)
.unwrap();
super::super::transaction::commit(change_set).unwrap();
assert_eq!(locate_node_count(&path, -1).unwrap().count, expected);
}
assert_eq!(fs::metadata(path).unwrap().len(), (6 * PAGE_SIZE) as u64);
}
#[test]
fn rejects_counts_increment_overflow() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("neostore.counts.db");
fs::write(&path, counts_file(&[(-1, i64::MAX as u64)])).unwrap();
assert!(prepare_node_count_increment(&path, -1, 1)
.unwrap_err()
.to_string()
.contains("overflow"));
assert!(prepare_node_count_increments(&path, &[(-1, 1), (-1, 1)])
.unwrap_err()
.to_string()
.contains("duplicate"));
}
#[test]
#[ignore = "requires NEO4J_REAL_FIXTURE generated by tools/neo4j-fixture-generator"]
fn reads_total_nodes_from_a_real_counts_store() {
let database = std::env::var("NEO4J_REAL_FIXTURE").unwrap();
let source = Path::new(&database);
let entry = locate_node_count(&source.join("neostore.counts.db"), -1).unwrap();
assert_eq!(entry.count, 62);
let directory = tempfile::tempdir().unwrap();
fs::copy(source.join("neostore"), directory.path().join("neostore")).unwrap();
let path = directory.path().join("neostore.counts.db");
fs::copy(source.join("neostore.counts.db"), &path).unwrap();
let update = prepare_node_count_increments(&path, &[(-1, 1), (0, 1)]).unwrap();
let mut change_set = super::super::transaction::ChangeSet::new(directory.path()).unwrap();
change_set
.overwrite(
"neostore.counts.db",
update.root_page_offset,
update.root_page,
)
.unwrap();
super::super::transaction::commit(change_set).unwrap();
assert_eq!(locate_node_count(&path, -1).unwrap().count, 63);
assert_eq!(locate_node_count(&path, 0).unwrap().count, 2);
}
}