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"));
}
}