littlegraph-core 0.2.1

Embedded openCypher graph database backed by Neo4j record storage
Documentation
use std::collections::{BTreeMap, BTreeSet};
use std::path::{Path, PathBuf};

use crate::error::{Neo4jStoreError, Result};

use super::dynamic::{read_u32, DynamicStore, NO_NEXT_BLOCK};
use super::page::{PageLayout, RecordReader};
use super::Neo4jStoreFormat;

const TOKEN_RECORD_SIZE: usize = 5;
const PROPERTY_KEY_TOKEN_RECORD_SIZE: usize = 9;

pub(super) fn encode_label_token(name_id: u32) -> [u8; TOKEN_RECORD_SIZE] {
    let mut bytes = [0_u8; TOKEN_RECORD_SIZE];
    bytes[0] = 1;
    bytes[1..5].copy_from_slice(&name_id.to_be_bytes());
    bytes
}

pub(super) fn encode_property_key_token(name_id: u32) -> [u8; PROPERTY_KEY_TOKEN_RECORD_SIZE] {
    let mut bytes = [0_u8; PROPERTY_KEY_TOKEN_RECORD_SIZE];
    bytes[0] = 1;
    bytes[5..9].copy_from_slice(&name_id.to_be_bytes());
    bytes
}

#[derive(Clone, Debug, Default)]
pub(super) struct TokenCatalog {
    pub(super) labels: BTreeMap<u32, String>,
    pub(super) relationship_types: BTreeMap<u32, String>,
    pub(super) property_keys: BTreeMap<u32, String>,
    pub(super) internal_labels: BTreeSet<u32>,
    pub(super) internal_relationship_types: BTreeSet<u32>,
    pub(super) internal_property_keys: BTreeSet<u32>,
}

struct LoadedTokenStore {
    names: BTreeMap<u32, String>,
    internal: BTreeSet<u32>,
}

struct TokenStoreSpec<'a> {
    token_type: &'a str,
    token_file: &'a str,
    name_file: &'a str,
    record_size: usize,
    name_id_offset: usize,
}

pub(super) fn load(database_directory: &Path, format: Neo4jStoreFormat) -> Result<TokenCatalog> {
    let labels = load_token_store(
        database_directory,
        format,
        TokenStoreSpec {
            token_type: "label token",
            token_file: "neostore.labeltokenstore.db",
            name_file: "neostore.labeltokenstore.db.names",
            record_size: TOKEN_RECORD_SIZE,
            name_id_offset: 1,
        },
    )?;
    let relationship_types = load_token_store(
        database_directory,
        format,
        TokenStoreSpec {
            token_type: "relationship type token",
            token_file: "neostore.relationshiptypestore.db",
            name_file: "neostore.relationshiptypestore.db.names",
            record_size: TOKEN_RECORD_SIZE,
            name_id_offset: 1,
        },
    )?;
    let property_keys = load_token_store(
        database_directory,
        format,
        TokenStoreSpec {
            token_type: "property key token",
            token_file: "neostore.propertystore.db.index",
            name_file: "neostore.propertystore.db.index.keys",
            record_size: PROPERTY_KEY_TOKEN_RECORD_SIZE,
            name_id_offset: 5,
        },
    )?;
    Ok(TokenCatalog {
        labels: labels.names,
        relationship_types: relationship_types.names,
        property_keys: property_keys.names,
        internal_labels: labels.internal,
        internal_relationship_types: relationship_types.internal,
        internal_property_keys: property_keys.internal,
    })
}

fn load_token_store(
    database_directory: &Path,
    format: Neo4jStoreFormat,
    spec: TokenStoreSpec<'_>,
) -> Result<LoadedTokenStore> {
    let token_path = database_directory.join(spec.token_file);
    let token_layout = PageLayout::new(&token_path, format, spec.record_size)?;
    let mut token_reader = RecordReader::open(&token_path, spec.token_type, token_layout)?;
    let name_path = database_directory.join(spec.name_file);
    let mut names = DynamicStore::open(&name_path, format, "dynamic token name")?;
    let mut tokens = BTreeMap::new();
    let mut internal = BTreeSet::new();

    for record_id in 0..token_reader.record_count() {
        let bytes = token_reader.read(record_id)?;
        if bytes[0] & 1 == 0 {
            continue;
        }
        let token_id = u32::try_from(record_id).map_err(|_| {
            invalid_record(
                &token_reader,
                record_id,
                spec.token_type,
                "token scan",
                "token ID does not fit in u32",
            )
        })?;
        let name_id = read_u32(&bytes[spec.name_id_offset..spec.name_id_offset + 4]);
        // Neo4j uses RESERVED while a token record has no assigned name yet.
        if name_id == NO_NEXT_BLOCK {
            continue;
        }
        let context = format!(
            "{0} {token_id} name chain starting at record {name_id}",
            spec.token_type
        );
        let name_bytes = names.read_chain(name_id as u64, &context)?;
        let name = String::from_utf8(name_bytes).map_err(|error| {
            names.invalid(
                name_id as u64,
                &context,
                format!("token name is not valid UTF-8: {error}"),
            )
        })?;
        tokens.insert(token_id, name);
        if bytes[0] & 2 != 0 {
            internal.insert(token_id);
        }
    }
    Ok(LoadedTokenStore {
        names: tokens,
        internal,
    })
}

fn invalid_record(
    reader: &RecordReader,
    record_id: u64,
    record_type: &str,
    context: &str,
    message: impl Into<String>,
) -> crate::Error {
    let offset = reader.offset(record_id).unwrap_or(u64::MAX);
    Neo4jStoreError::InvalidRecord {
        path: PathBuf::from(reader.path()),
        record_type: record_type.to_owned(),
        record_id,
        offset,
        context: context.to_owned(),
        message: message.into(),
    }
    .into()
}

#[cfg(test)]
mod tests {
    use std::fs::File;
    use std::io::{Seek, SeekFrom, Write};

    use super::*;

    fn write_at(file: &mut File, offset: u64, bytes: &[u8]) {
        file.seek(SeekFrom::Start(offset)).unwrap();
        file.write_all(bytes).unwrap();
    }

    fn dynamic_record(data: &[u8], next: Option<u64>, start: bool) -> [u8; 38] {
        let mut record = [0_u8; 38];
        let next = next.unwrap_or(NO_NEXT_BLOCK as u64);
        record[0] = 0x10 | if start { 0 } else { 0x80 } | ((next >> 32) as u8 & 0x0f);
        record[1] = ((data.len() >> 16) & 0xff) as u8;
        record[2] = ((data.len() >> 8) & 0xff) as u8;
        record[3] = (data.len() & 0xff) as u8;
        record[4..8].copy_from_slice(&(next as u32).to_be_bytes());
        record[8..8 + data.len()].copy_from_slice(data);
        record
    }

    fn create_name_store(path: &Path, format: Neo4jStoreFormat, records: &[(u64, [u8; 38])]) {
        let layout = PageLayout::new(path, format, 38).unwrap();
        let mut file = File::create(path).unwrap();
        write_at(&mut file, 0, &38_u32.to_be_bytes());
        for (id, record) in records {
            write_at(&mut file, layout.offset(*id, path).unwrap(), record);
        }
    }

    fn create_token_store(
        path: &Path,
        record_size: usize,
        name_offset: usize,
        name_id: u32,
        internal: bool,
    ) {
        let mut record = vec![0_u8; record_size];
        record[0] = 1 | if internal { 2 } else { 0 };
        record[name_offset..name_offset + 4].copy_from_slice(&name_id.to_be_bytes());
        std::fs::write(path, record).unwrap();
    }

    #[test]
    fn reads_short_and_multibyte_names() {
        let directory = tempfile::tempdir().unwrap();
        let path = directory.path().join("names");
        create_name_store(
            &path,
            Neo4jStoreFormat::AlignedV5_0,
            &[(1, dynamic_record("用户".as_bytes(), None, true))],
        );
        let mut store =
            DynamicStore::open(&path, Neo4jStoreFormat::AlignedV5_0, "token name").unwrap();
        assert_eq!(
            store.read_chain(1, "test token").unwrap(),
            "用户".as_bytes()
        );
    }

    #[test]
    fn reads_cross_page_chains_in_both_formats() {
        for format in [
            Neo4jStoreFormat::StandardV5_0,
            Neo4jStoreFormat::AlignedV5_0,
        ] {
            let directory = tempfile::tempdir().unwrap();
            let path = directory.path().join("names");
            create_name_store(
                &path,
                format,
                &[
                    (214, dynamic_record(&[b'a'; 30], Some(215), true)),
                    (215, dynamic_record("界".as_bytes(), None, false)),
                ],
            );
            let mut store = DynamicStore::open(&path, format, "token name").unwrap();
            assert_eq!(
                store.read_chain(214, "long token").unwrap(),
                format!("{}界", "a".repeat(30)).as_bytes()
            );
        }
    }

    #[test]
    fn rejects_cycles_unused_records_bad_lengths_and_utf8() {
        let cases = [
            dynamic_record(&[b'a'; 30], Some(1), true),
            [0_u8; 38],
            {
                let mut record = dynamic_record(b"x", None, true);
                record[1..4].copy_from_slice(&[0, 0, 31]);
                record
            },
            dynamic_record(&[0xff], None, true),
        ];
        for record in cases {
            let directory = tempfile::tempdir().unwrap();
            let path = directory.path().join("names");
            create_name_store(&path, Neo4jStoreFormat::AlignedV5_0, &[(1, record)]);
            let mut store =
                DynamicStore::open(&path, Neo4jStoreFormat::AlignedV5_0, "token name").unwrap();
            let result = store.read_chain(1, "label token 7");
            if record[8] == 0xff {
                assert!(String::from_utf8(result.unwrap()).is_err());
            } else {
                assert!(result.is_err());
            }
        }
    }

    #[test]
    fn decodes_36_bit_next_record_modifier() {
        let record = dynamic_record(&[b'a'; 30], Some(0x0a_1234_5678), true);
        let high = (record[0] & 0x0f) as u64;
        let low = read_u32(&record[4..8]) as u64;
        assert_eq!((high << 32) | low, 0x0a_1234_5678);
    }

    #[test]
    fn loads_all_three_token_stores() {
        for format in [
            Neo4jStoreFormat::StandardV5_0,
            Neo4jStoreFormat::AlignedV5_0,
        ] {
            let directory = tempfile::tempdir().unwrap();
            let fixtures = [
                (
                    "neostore.labeltokenstore.db",
                    "neostore.labeltokenstore.db.names",
                    TOKEN_RECORD_SIZE,
                    1,
                    "Person",
                    false,
                ),
                (
                    "neostore.relationshiptypestore.db",
                    "neostore.relationshiptypestore.db.names",
                    TOKEN_RECORD_SIZE,
                    1,
                    "KNOWS",
                    false,
                ),
                (
                    "neostore.propertystore.db.index",
                    "neostore.propertystore.db.index.keys",
                    PROPERTY_KEY_TOKEN_RECORD_SIZE,
                    5,
                    "名字",
                    true,
                ),
            ];
            for (token_file, name_file, record_size, name_offset, name, internal) in fixtures {
                create_token_store(
                    &directory.path().join(token_file),
                    record_size,
                    name_offset,
                    1,
                    internal,
                );
                create_name_store(
                    &directory.path().join(name_file),
                    format,
                    &[(1, dynamic_record(name.as_bytes(), None, true))],
                );
            }

            let catalog = load(directory.path(), format).unwrap();
            assert_eq!(catalog.labels.get(&0).unwrap(), "Person");
            assert_eq!(catalog.relationship_types.get(&0).unwrap(), "KNOWS");
            assert_eq!(catalog.property_keys.get(&0).unwrap(), "名字");
            assert!(catalog.internal_labels.is_empty());
            assert!(catalog.internal_relationship_types.is_empty());
            assert_eq!(catalog.internal_property_keys, BTreeSet::from([0]));
        }
    }

    #[test]
    fn encodes_a_property_key_token_record() {
        let bytes = encode_property_key_token(0x1234_5678);
        assert_eq!(bytes[0], 1);
        assert_eq!(&bytes[1..5], &[0; 4]);
        assert_eq!(read_u32(&bytes[5..9]), 0x1234_5678);
    }

    #[test]
    fn encodes_a_label_token_record() {
        assert_eq!(encode_label_token(0x1234_5678), [1, 0x12, 0x34, 0x56, 0x78]);
    }

    #[test]
    fn out_of_bounds_chain_error_keeps_chain_context() {
        let directory = tempfile::tempdir().unwrap();
        let path = directory.path().join("names");
        create_name_store(
            &path,
            Neo4jStoreFormat::AlignedV5_0,
            &[(1, dynamic_record(&[b'a'; 30], Some(99), true))],
        );
        let mut store =
            DynamicStore::open(&path, Neo4jStoreFormat::AlignedV5_0, "token name").unwrap();
        let error = store.read_chain(1, "label token 4 name chain").unwrap_err();
        let message = error.to_string();
        assert!(message.contains("label token 4 name chain"));
        assert!(message.contains("record 99"));
    }
}