littlegraph-core 0.2.1

Embedded openCypher graph database backed by Neo4j record storage
Documentation
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"));
    }
}