littlegraph-core 0.2.1

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

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

use super::page::{PageLayout, RecordReader};
use super::Neo4jStoreFormat;

const STORE: &str = "neostore.relationshipgroupstore.db";
const RECORD_SIZE: usize = 25;
const MAX_REFERENCE: u64 = 0x07_ffff_ffff;
const NO_REFERENCE: u64 = u32::MAX as u64;

#[derive(Clone, Debug, PartialEq, Eq)]
pub(super) struct RelationshipGroupRecord {
    pub(super) type_id: u32,
    pub(super) next: Option<u64>,
    pub(super) first_out: Option<u64>,
    pub(super) first_in: Option<u64>,
    pub(super) first_loop: Option<u64>,
    pub(super) owning_node: u64,
    pub(super) external_degrees_out: bool,
    pub(super) external_degrees_in: bool,
    pub(super) external_degrees_loop: bool,
}

#[derive(Clone, Debug, Default)]
pub(super) struct RelationshipGroupCatalog {
    pub(super) records: Vec<(u64, RelationshipGroupRecord)>,
    pub(super) by_node: BTreeMap<u64, Vec<u64>>,
}

pub(super) fn load(
    database_directory: &Path,
    format: Neo4jStoreFormat,
    nodes: &BTreeSet<u64>,
    dense_node_heads: &BTreeMap<u64, Option<u64>>,
    relationships: &BTreeSet<u64>,
    relationship_types: &BTreeSet<u32>,
) -> Result<RelationshipGroupCatalog> {
    let path = database_directory.join(STORE);
    let layout = PageLayout::new(&path, format, RECORD_SIZE)?;
    let mut reader = RecordReader::open(&path, "relationship group", layout)?;
    let record_count = reader.record_count();
    let mut in_use = BTreeSet::new();
    for id in 0..record_count {
        if reader.read(id)?[0] & 1 != 0 {
            in_use.insert(id);
        }
    }
    let mut records = Vec::new();
    let mut by_node: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
    for id in 0..record_count {
        let bytes = reader.read(id)?;
        let Ok(bytes) = <[u8; RECORD_SIZE]>::try_from(bytes) else {
            return Err(invalid(
                &reader,
                id,
                "relationship group record has invalid size",
            ));
        };
        let Some(record) = decode_record(&bytes) else {
            continue;
        };
        if !nodes.contains(&record.owning_node) {
            return Err(invalid(
                &reader,
                id,
                format!("owning node {} is not in use", record.owning_node),
            ));
        }
        if !relationship_types.contains(&record.type_id) {
            return Err(invalid(
                &reader,
                id,
                format!("unknown relationship type token ID {}", record.type_id),
            ));
        }
        for (name, reference) in [
            ("next group", record.next),
            ("first outgoing", record.first_out),
            ("first incoming", record.first_in),
            ("first loop", record.first_loop),
        ] {
            let Some(target) = reference else { continue };
            let valid = if name == "next group" {
                target < record_count && in_use.contains(&target)
            } else {
                relationships.contains(&target)
            };
            if !valid {
                return Err(invalid(
                    &reader,
                    id,
                    format!("{name} reference {target} is not in use"),
                ));
            }
        }
        by_node.entry(record.owning_node).or_default().push(id);
        records.push((id, record));
    }
    let record_map = records
        .iter()
        .map(|(id, record)| (*id, record))
        .collect::<BTreeMap<_, _>>();
    let mut reachable = BTreeSet::new();
    for (node_id, head) in dense_node_heads {
        let Some(mut group_id) = *head else { continue };
        let mut previous_type = None;
        let mut seen = BTreeSet::new();
        loop {
            if !seen.insert(group_id) {
                return Err(invalid(
                    &reader,
                    group_id,
                    "relationship group chain contains a cycle",
                ));
            }
            reachable.insert(group_id);
            let Some(group) = record_map.get(&group_id) else {
                return Err(invalid(
                    &reader,
                    group_id,
                    "dense node head does not point to an in-use relationship group",
                ));
            };
            if group.owning_node != *node_id {
                return Err(invalid(
                    &reader,
                    group_id,
                    "relationship group owner does not match dense node",
                ));
            }
            if previous_type.is_some_and(|type_id| group.type_id <= type_id) {
                return Err(invalid(
                    &reader,
                    group_id,
                    "relationship group types are not strictly increasing",
                ));
            }
            previous_type = Some(group.type_id);
            let Some(next) = group.next else { break };
            group_id = next;
        }
    }
    for (id, group) in &records {
        if !dense_node_heads.contains_key(&group.owning_node) {
            return Err(invalid(
                &reader,
                *id,
                "relationship group owner is not a dense node",
            ));
        }
        if !reachable.contains(id) {
            return Err(invalid(
                &reader,
                *id,
                "relationship group is not reachable from its owning dense node",
            ));
        }
    }
    Ok(RelationshipGroupCatalog { records, by_node })
}

fn invalid(reader: &RecordReader, record_id: u64, message: impl Into<String>) -> crate::Error {
    Neo4jStoreError::InvalidRecord {
        path: reader.path().to_path_buf(),
        record_type: "relationship group".to_owned(),
        record_id,
        offset: reader.offset(record_id).unwrap_or(u64::MAX),
        context: "relationship group load".to_owned(),
        message: message.into(),
    }
    .into()
}

pub(super) fn decode_record(bytes: &[u8; RECORD_SIZE]) -> Option<RelationshipGroupRecord> {
    if bytes[0] & 1 == 0 {
        return None;
    }
    let header = bytes[0];
    let high = bytes[1];
    Some(RelationshipGroupRecord {
        type_id: u16::from_be_bytes([bytes[2], bytes[3]]) as u32,
        next: decode_reference(read_u32(&bytes[4..8]), ((header & 0x0e) as u64) << 31),
        first_out: decode_reference(read_u32(&bytes[8..12]), ((header & 0x70) as u64) << 28),
        first_in: decode_reference(read_u32(&bytes[12..16]), ((high & 0x0e) as u64) << 31),
        first_loop: decode_reference(read_u32(&bytes[16..20]), ((high & 0x70) as u64) << 28),
        owning_node: read_u32(&bytes[20..24]) as u64 | ((bytes[24] as u64) << 32),
        external_degrees_out: header & 0x80 != 0,
        external_degrees_in: high & 1 != 0,
        external_degrees_loop: high & 0x80 != 0,
    })
}

pub(super) fn encode_record(
    record: &RelationshipGroupRecord,
) -> std::result::Result<[u8; RECORD_SIZE], String> {
    if record.type_id > u16::MAX as u32 {
        return Err(format!(
            "relationship group type ID {} exceeds 16 bits",
            record.type_id
        ));
    }
    if record.owning_node > MAX_REFERENCE {
        return Err("relationship group owning node exceeds 35 bits".to_owned());
    }
    let next = encode_reference(record.next, "next group")?;
    let first_out = encode_reference(record.first_out, "first outgoing relationship")?;
    let first_in = encode_reference(record.first_in, "first incoming relationship")?;
    let first_loop = encode_reference(record.first_loop, "first loop relationship")?;

    let mut bytes = [0_u8; RECORD_SIZE];
    bytes[0] = 1
        | ((next >> 31) as u8 & 0x0e)
        | ((first_out >> 28) as u8 & 0x70)
        | (u8::from(record.external_degrees_out) << 7);
    bytes[1] = ((first_in >> 31) as u8 & 0x0e)
        | ((first_loop >> 28) as u8 & 0x70)
        | u8::from(record.external_degrees_in)
        | (u8::from(record.external_degrees_loop) << 7);
    bytes[2..4].copy_from_slice(&(record.type_id as u16).to_be_bytes());
    for (offset, reference) in [(4, next), (8, first_out), (12, first_in), (16, first_loop)] {
        bytes[offset..offset + 4].copy_from_slice(&(reference as u32).to_be_bytes());
    }
    bytes[20..24].copy_from_slice(&(record.owning_node as u32).to_be_bytes());
    bytes[24] = (record.owning_node >> 32) as u8;
    Ok(bytes)
}

fn decode_reference(low: u32, modifier: u64) -> Option<u64> {
    if low == u32::MAX && modifier == 0 {
        None
    } else {
        Some(modifier | low as u64)
    }
}

fn encode_reference(reference: Option<u64>, field: &str) -> std::result::Result<u64, String> {
    let Some(reference) = reference else {
        return Ok(NO_REFERENCE);
    };
    if reference > MAX_REFERENCE {
        return Err(format!("relationship group {field} exceeds 35 bits"));
    }
    if reference == NO_REFERENCE {
        return Err(format!("relationship group {field} uses the null sentinel"));
    }
    Ok(reference)
}

fn read_u32(bytes: &[u8]) -> u32 {
    u32::from_be_bytes(
        bytes
            .try_into()
            .expect("four-byte relationship group field"),
    )
}

#[cfg(test)]
mod tests {
    use super::*;

    fn record() -> RelationshipGroupRecord {
        RelationshipGroupRecord {
            type_id: 42,
            next: Some(0x01_1234_5678),
            first_out: Some(0x02_2345_6789),
            first_in: Some(0x03_3456_789a),
            first_loop: Some(0x04_4567_89ab),
            owning_node: 0x05_5678_9abc,
            external_degrees_out: true,
            external_degrees_in: false,
            external_degrees_loop: true,
        }
    }

    #[test]
    fn relationship_group_codec_preserves_references_owner_and_flags() {
        let record = record();
        let bytes = encode_record(&record).unwrap();
        assert_eq!(decode_record(&bytes), Some(record));
    }

    #[test]
    fn relationship_group_codec_preserves_null_references() {
        let mut record = record();
        record.next = None;
        record.first_out = None;
        record.first_in = None;
        record.first_loop = None;
        let bytes = encode_record(&record).unwrap();
        assert_eq!(decode_record(&bytes), Some(record));
    }

    #[test]
    fn relationship_group_decoder_skips_unused_records() {
        assert_eq!(decode_record(&[0_u8; RECORD_SIZE]), None);
    }

    #[test]
    fn relationship_group_encoder_rejects_unrepresentable_fields() {
        let mut record = record();
        record.type_id = u16::MAX as u32 + 1;
        assert!(encode_record(&record).unwrap_err().contains("16 bits"));
        record.type_id = 42;
        record.owning_node = MAX_REFERENCE + 1;
        assert!(encode_record(&record).unwrap_err().contains("owning node"));
        record.owning_node = 1;
        record.first_out = Some(NO_REFERENCE);
        assert!(encode_record(&record)
            .unwrap_err()
            .contains("null sentinel"));
        record.first_out = Some(MAX_REFERENCE + 1);
        assert!(encode_record(&record).unwrap_err().contains("35 bits"));
    }
}