use std::collections::{BTreeMap, BTreeSet};
use std::path::Path;
use crate::error::{Neo4jStoreError, Result};
use crate::value::Properties;
use super::page::{PageLayout, RecordReader};
use super::Neo4jStoreFormat;
const RELATIONSHIP_RECORD_SIZE: usize = 34;
const MAX_NODE_REFERENCE: u64 = 0x07_ffff_ffff;
const MAX_RELATIONSHIP_REFERENCE: u64 = 0x07_ffff_ffff;
const MAX_PROPERTY_REFERENCE: u64 = 0x0f_ffff_ffff;
#[allow(dead_code)]
pub(super) struct RelationshipRecordFields {
pub(super) start: u64,
pub(super) end: u64,
pub(super) type_id: u32,
pub(super) next_property: Option<u64>,
pub(super) first_previous: Option<u64>,
pub(super) first_next: Option<u64>,
pub(super) second_previous: Option<u64>,
pub(super) second_next: Option<u64>,
pub(super) first_in_start_chain: bool,
pub(super) first_in_end_chain: bool,
pub(super) start_node_dense: bool,
pub(super) end_node_dense: bool,
}
#[derive(Clone, Debug, Default)]
pub(super) struct RelationshipCatalog {
pub(super) records: Vec<RelationshipRecord>,
pub(super) outgoing: BTreeMap<u64, Vec<u64>>,
pub(super) incoming: BTreeMap<u64, Vec<u64>>,
}
#[derive(Clone, Debug, PartialEq)]
pub(super) struct RelationshipRecord {
pub(super) neo4j_id: u64,
pub(super) start: u64,
pub(super) end: u64,
pub(super) type_id: u32,
pub(super) next_property: Option<u64>,
pub(super) first_previous: Option<u64>,
pub(super) first_next: Option<u64>,
pub(super) second_previous: Option<u64>,
pub(super) second_next: Option<u64>,
pub(super) first_in_start_chain: bool,
pub(super) first_in_end_chain: bool,
pub(super) start_node_dense: bool,
pub(super) end_node_dense: bool,
pub(super) properties: Properties,
}
pub(super) fn load(
database_directory: &Path,
format: Neo4jStoreFormat,
relationship_types: &BTreeMap<u32, String>,
nodes: &BTreeSet<u64>,
node_relationship_heads: impl IntoIterator<Item = (u64, Option<u64>, bool)>,
) -> Result<RelationshipCatalog> {
let path = database_directory.join("neostore.relationshipstore.db");
let layout = PageLayout::new(&path, format, RELATIONSHIP_RECORD_SIZE)?;
let mut reader = RecordReader::open(&path, "relationship", layout)?;
let mut records = Vec::new();
let mut outgoing: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
let mut incoming: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
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);
}
}
for (node_id, head, dense) in node_relationship_heads {
if dense {
continue;
}
if let Some(target) = head {
if target >= record_count || !in_use.contains(&target) {
return Err(invalid(
&reader,
target,
format!(
"node {node_id} next relationship reference {target} is not an in-use record"
),
));
}
}
}
for id in 0..record_count {
let bytes = reader.read(id)?;
if bytes[0] & 1 == 0 {
continue;
}
let decoded = decode_record(&bytes);
for (name, reference) in [
(
"first previous",
(!decoded.first_in_start_chain)
.then_some(decoded.first_previous)
.flatten(),
),
("first next", decoded.first_next),
(
"second previous",
(!decoded.first_in_end_chain)
.then_some(decoded.second_previous)
.flatten(),
),
("second next", decoded.second_next),
] {
if let Some(target) = reference {
if target >= record_count || !in_use.contains(&target) {
return Err(invalid(
&reader,
id,
format!("{name} relationship reference {target} is not an in-use record"),
));
}
}
}
if !nodes.contains(&decoded.start) || !nodes.contains(&decoded.end) {
return Err(invalid(
&reader,
id,
"relationship endpoint node is not in use",
));
}
if !relationship_types.contains_key(&decoded.type_id) {
return Err(invalid(
&reader,
id,
format!("unknown relationship type token ID {}", decoded.type_id),
));
}
records.push(RelationshipRecord {
neo4j_id: id,
start: decoded.start,
end: decoded.end,
type_id: decoded.type_id,
next_property: decoded.next_property,
first_previous: decoded.first_previous,
first_next: decoded.first_next,
second_previous: decoded.second_previous,
second_next: decoded.second_next,
first_in_start_chain: decoded.first_in_start_chain,
first_in_end_chain: decoded.first_in_end_chain,
start_node_dense: decoded.start_node_dense,
end_node_dense: decoded.end_node_dense,
properties: Properties::new(),
});
outgoing.entry(decoded.start).or_default().push(id);
incoming.entry(decoded.end).or_default().push(id);
}
Ok(RelationshipCatalog {
records,
outgoing,
incoming,
})
}
#[allow(dead_code)]
struct DecodedRelationship {
start: u64,
end: u64,
type_id: u32,
next_property: Option<u64>,
first_previous: Option<u64>,
first_next: Option<u64>,
second_previous: Option<u64>,
second_next: Option<u64>,
first_in_start_chain: bool,
first_in_end_chain: bool,
start_node_dense: bool,
end_node_dense: bool,
}
fn decode_record(bytes: &[u8]) -> DecodedRelationship {
let header = bytes[0];
let start_low = read_u32(&bytes[1..5]);
let end_low = read_u32(&bytes[5..9]);
let type_and_modifiers = read_u32(&bytes[9..13]);
let next_property_low = read_u32(&bytes[29..33]);
DecodedRelationship {
start: (((header & 0x0e) as u64) << 31) | start_low as u64,
end: (((type_and_modifiers & 0x7000_0000) as u64) << 4) | end_low as u64,
type_id: type_and_modifiers & 0xffff,
next_property: decode_reference(next_property_low, ((header & 0xf0) as u64) << 28),
first_previous: decode_reference(
read_u32(&bytes[13..17]),
((type_and_modifiers & 0x0e00_0000) as u64) << 7,
),
first_next: decode_reference(
read_u32(&bytes[17..21]),
((type_and_modifiers & 0x01c0_0000) as u64) << 10,
),
second_previous: decode_reference(
read_u32(&bytes[21..25]),
((type_and_modifiers & 0x0038_0000) as u64) << 13,
),
second_next: decode_reference(
read_u32(&bytes[25..29]),
((type_and_modifiers & 0x0007_0000) as u64) << 16,
),
first_in_start_chain: bytes[33] & 1 != 0,
first_in_end_chain: bytes[33] & 2 != 0,
start_node_dense: bytes[33] & 4 != 0,
end_node_dense: bytes[33] & 8 != 0,
}
}
#[allow(dead_code)]
pub(super) fn encode_record(
fields: &RelationshipRecordFields,
) -> std::result::Result<[u8; RELATIONSHIP_RECORD_SIZE], String> {
if fields.start > MAX_NODE_REFERENCE || fields.end > MAX_NODE_REFERENCE {
return Err("relationship endpoint exceeds the 35-bit record field".to_owned());
}
if fields.type_id > u16::MAX as u32 {
return Err(format!(
"relationship type token ID {} exceeds 16 bits",
fields.type_id
));
}
let next_property = encode_reference(
fields.next_property,
MAX_PROPERTY_REFERENCE,
"relationship next-property",
)?;
let first_previous = encode_reference(
fields.first_previous,
MAX_RELATIONSHIP_REFERENCE,
"relationship first-previous",
)?;
let first_next = encode_reference(
fields.first_next,
MAX_RELATIONSHIP_REFERENCE,
"relationship first-next",
)?;
let second_previous = encode_reference(
fields.second_previous,
MAX_RELATIONSHIP_REFERENCE,
"relationship second-previous",
)?;
let second_next = encode_reference(
fields.second_next,
MAX_RELATIONSHIP_REFERENCE,
"relationship second-next",
)?;
let mut bytes = [0_u8; RELATIONSHIP_RECORD_SIZE];
bytes[0] = 1 | ((fields.start >> 31) as u8 & 0x0e) | ((next_property >> 28) as u8 & 0xf0);
bytes[1..5].copy_from_slice(&(fields.start as u32).to_be_bytes());
bytes[5..9].copy_from_slice(&(fields.end as u32).to_be_bytes());
let type_and_modifiers = fields.type_id
| (((fields.end >> 32) as u32 & 0x7) << 28)
| (((first_previous >> 32) as u32 & 0x7) << 25)
| (((first_next >> 32) as u32 & 0x7) << 22)
| (((second_previous >> 32) as u32 & 0x7) << 19)
| (((second_next >> 32) as u32 & 0x7) << 16);
bytes[9..13].copy_from_slice(&type_and_modifiers.to_be_bytes());
for (offset, reference) in [
(13, first_previous),
(17, first_next),
(21, second_previous),
(25, second_next),
(29, next_property),
] {
bytes[offset..offset + 4].copy_from_slice(&(reference as u32).to_be_bytes());
}
bytes[33] = u8::from(fields.first_in_start_chain)
| (u8::from(fields.first_in_end_chain) << 1)
| (u8::from(fields.start_node_dense) << 2)
| (u8::from(fields.end_node_dense) << 3);
Ok(bytes)
}
pub(super) fn encode_catalog_record(
record: &RelationshipRecord,
) -> std::result::Result<[u8; RELATIONSHIP_RECORD_SIZE], String> {
encode_record(&RelationshipRecordFields {
start: record.start,
end: record.end,
type_id: record.type_id,
next_property: record.next_property,
first_previous: record.first_previous,
first_next: record.first_next,
second_previous: record.second_previous,
second_next: record.second_next,
first_in_start_chain: record.first_in_start_chain,
first_in_end_chain: record.first_in_end_chain,
start_node_dense: record.start_node_dense,
end_node_dense: record.end_node_dense,
})
}
fn encode_reference(
reference: Option<u64>,
maximum: u64,
field: &str,
) -> std::result::Result<u64, String> {
let Some(reference) = reference else {
return Ok(u32::MAX as u64);
};
if reference > maximum {
return Err(format!(
"{field} reference {reference} exceeds its record field"
));
}
if reference == u32::MAX as u64 {
return Err(format!(
"{field} reference {reference} conflicts with the no-reference sentinel"
));
}
Ok(reference)
}
fn read_u32(bytes: &[u8]) -> u32 {
u32::from_be_bytes(bytes.try_into().expect("fixed-size relationship field"))
}
fn decode_reference(low: u32, modifier: u64) -> Option<u64> {
if modifier == 0 && low == u32::MAX {
None
} else {
Some(modifier | low as u64)
}
}
pub(super) fn read_with_next_property(
database_directory: &Path,
format: Neo4jStoreFormat,
record_id: u64,
next_property: u64,
) -> Result<[u8; RELATIONSHIP_RECORD_SIZE]> {
let path = database_directory.join("neostore.relationshipstore.db");
let layout = PageLayout::new(&path, format, RELATIONSHIP_RECORD_SIZE)?;
let mut reader = RecordReader::open(&path, "relationship", layout)?;
let mut bytes: [u8; RELATIONSHIP_RECORD_SIZE] = reader
.read(record_id)?
.try_into()
.expect("record reader returns the configured size");
set_next_property(&mut bytes, next_property);
Ok(bytes)
}
pub(super) fn set_next_property(bytes: &mut [u8; RELATIONSHIP_RECORD_SIZE], next_property: u64) {
bytes[0] = (bytes[0] & 0x0f) | ((next_property >> 28) as u8 & 0xf0);
bytes[29..33].copy_from_slice(&(next_property as u32).to_be_bytes());
}
fn invalid(reader: &RecordReader, record_id: u64, message: impl Into<String>) -> crate::Error {
Neo4jStoreError::InvalidRecord {
path: reader.path().to_path_buf(),
record_type: "relationship".to_owned(),
record_id,
offset: reader.offset(record_id).unwrap_or(u64::MAX),
context: "relationship scan".to_owned(),
message: message.into(),
}
.into()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn decodes_relationship_endpoint_and_property_modifiers() {
let mut bytes = [0_u8; RELATIONSHIP_RECORD_SIZE];
let start = 0x05_1234_5678_u64;
let end = 0x07_2345_6789_u64;
let property = 0x0f_3456_789a_u64;
bytes[0] = 1 | ((start >> 31) as u8 & 0x0e) | ((property >> 28) as u8 & 0xf0);
bytes[1..5].copy_from_slice(&(start as u32).to_be_bytes());
bytes[5..9].copy_from_slice(&(end as u32).to_be_bytes());
let type_and_modifiers = 42_u32 | (((end >> 32) as u32 & 0x7) << 28);
bytes[9..13].copy_from_slice(&type_and_modifiers.to_be_bytes());
bytes[29..33].copy_from_slice(&(property as u32).to_be_bytes());
let decoded = decode_record(&bytes);
assert_eq!(decoded.start, start);
assert_eq!(decoded.end, end);
assert_eq!(decoded.type_id, 42);
assert_eq!(decoded.next_property, Some(property));
}
#[test]
fn decodes_unused_property_reference() {
let mut bytes = [0_u8; RELATIONSHIP_RECORD_SIZE];
bytes[0] = 1;
bytes[1..5].copy_from_slice(&1_u32.to_be_bytes());
bytes[5..9].copy_from_slice(&2_u32.to_be_bytes());
bytes[9..13].copy_from_slice(&7_u32.to_be_bytes());
bytes[29..33].copy_from_slice(&u32::MAX.to_be_bytes());
assert_eq!(decode_record(&bytes).next_property, None);
}
#[test]
fn setting_property_head_preserves_relationship_chain_fields() {
let mut bytes = [0x5a_u8; RELATIONSHIP_RECORD_SIZE];
bytes[0] = 0x0d;
let before = bytes;
set_next_property(&mut bytes, 0x0c_1234_5678);
assert_eq!(decode_record(&bytes).next_property, Some(0x0c_1234_5678));
assert_eq!(bytes[0] & 0x0f, before[0] & 0x0f);
assert_eq!(&bytes[1..29], &before[1..29]);
assert_eq!(bytes[33], before[33]);
}
#[test]
fn relationship_record_codec_preserves_chain_fields_and_flags() {
let fields = RelationshipRecordFields {
start: 0x05_1234_5678,
end: 0x07_2345_6789,
type_id: 42,
next_property: Some(0x0e_3456_789a),
first_previous: Some(0x01_4567_89ab),
first_next: Some(0x02_5678_9abc),
second_previous: Some(0x03_6789_abcd),
second_next: Some(0x04_789a_bcde),
first_in_start_chain: true,
first_in_end_chain: false,
start_node_dense: true,
end_node_dense: false,
};
let bytes = encode_record(&fields).unwrap();
let decoded = decode_record(&bytes);
assert_eq!(decoded.start, fields.start);
assert_eq!(decoded.end, fields.end);
assert_eq!(decoded.type_id, fields.type_id);
assert_eq!(decoded.next_property, fields.next_property);
assert_eq!(decoded.first_previous, fields.first_previous);
assert_eq!(decoded.first_next, fields.first_next);
assert_eq!(decoded.second_previous, fields.second_previous);
assert_eq!(decoded.second_next, fields.second_next);
assert!(decoded.first_in_start_chain);
assert!(!decoded.first_in_end_chain);
assert!(decoded.start_node_dense);
assert!(!decoded.end_node_dense);
}
#[test]
fn relationship_record_encoder_rejects_unrepresentable_fields() {
let mut fields = RelationshipRecordFields {
start: 1,
end: 2,
type_id: 7,
next_property: None,
first_previous: None,
first_next: None,
second_previous: None,
second_next: None,
first_in_start_chain: true,
first_in_end_chain: true,
start_node_dense: false,
end_node_dense: false,
};
fields.start = MAX_NODE_REFERENCE + 1;
assert!(encode_record(&fields).unwrap_err().contains("endpoint"));
fields.start = 1;
fields.type_id = u16::MAX as u32 + 1;
assert!(encode_record(&fields).unwrap_err().contains("16 bits"));
fields.type_id = 7;
fields.first_next = Some(u32::MAX as u64);
assert!(encode_record(&fields).unwrap_err().contains("sentinel"));
}
}