littlegraph-core 0.2.1

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

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(super) enum FixedStore {
    Property,
    Node,
    NodeLabel,
    Relationship,
    RelationshipGroup,
    String,
    Array,
    PropertyKeyToken,
    PropertyKeyName,
    LabelToken,
    LabelName,
    RelationshipTypeToken,
    RelationshipTypeName,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(super) struct FixedRecordDependency {
    pub(super) store: FixedStore,
    pub(super) record_id: u64,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(super) enum SharedDependency {
    DynamicChains,
    IdAllocation,
    IdReuse,
    IdReclamation,
    Counts,
    RelationshipGroupDegrees,
    Tokens,
}

#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(super) struct WriteSet {
    fixed_records: BTreeMap<FixedRecordDependency, BeforeImage>,
    shared: BTreeSet<SharedDependency>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
enum BeforeImage {
    Pending,
    Captured(Vec<u8>),
}

impl WriteSet {
    pub(super) fn insert_fixed(&mut self, store: FixedStore, record_id: u64) {
        self.fixed_records
            .entry(FixedRecordDependency { store, record_id })
            .or_insert(BeforeImage::Pending);
    }

    pub(super) fn insert_shared(&mut self, dependency: SharedDependency) {
        self.shared.insert(dependency);
    }

    pub(super) fn shared_len(&self) -> usize {
        self.shared.len()
    }

    pub(super) fn requires_reused_id_validation(&self) -> bool {
        self.shared.iter().any(|dependency| match dependency {
            SharedDependency::IdReuse => true,
            SharedDependency::DynamicChains
            | SharedDependency::IdAllocation
            | SharedDependency::IdReclamation
            | SharedDependency::Counts
            | SharedDependency::RelationshipGroupDegrees
            | SharedDependency::Tokens => false,
        })
    }

    pub(super) fn fixed_heap_bytes(&self) -> Option<usize> {
        self.fixed_records
            .values()
            .try_fold(0_usize, |bytes, image| {
                bytes
                    .checked_add(std::mem::size_of::<FixedRecordDependency>())
                    .and_then(|bytes| bytes.checked_add(std::mem::size_of::<BeforeImage>()))
                    .and_then(|bytes| bytes.checked_add(3 * std::mem::size_of::<usize>()))
                    .and_then(|bytes| match image {
                        BeforeImage::Captured(image) => bytes.checked_add(image.len()),
                        BeforeImage::Pending => Some(bytes),
                    })
            })
    }

    pub(super) fn pending_fixed(&self) -> Vec<FixedRecordDependency> {
        self.fixed_records
            .iter()
            .filter_map(|(dependency, image)| {
                matches!(image, BeforeImage::Pending).then_some(*dependency)
            })
            .collect()
    }

    pub(super) fn capture_before_image(
        &mut self,
        dependency: FixedRecordDependency,
        image: Vec<u8>,
    ) {
        if let Some(before_image @ BeforeImage::Pending) = self.fixed_records.get_mut(&dependency) {
            *before_image = BeforeImage::Captured(image);
        }
    }

    pub(super) fn rebase_dependencies(&self) -> Option<Vec<(FixedRecordDependency, &[u8])>> {
        if self.fixed_records.is_empty() {
            return None;
        }
        self.fixed_records
            .iter()
            .map(|(dependency, image)| match image {
                BeforeImage::Captured(image) => Some((*dependency, image.as_slice())),
                BeforeImage::Pending => None,
            })
            .collect()
    }

    pub(super) fn captured_before_images(&self) -> Vec<(FixedRecordDependency, &[u8])> {
        self.fixed_records
            .iter()
            .filter_map(|(dependency, image)| match image {
                BeforeImage::Captured(image) => Some((*dependency, image.as_slice())),
                BeforeImage::Pending => None,
            })
            .collect()
    }

    #[cfg(test)]
    pub(super) fn contains_fixed(&self, store: FixedStore, record_id: u64) -> bool {
        self.fixed_records
            .contains_key(&FixedRecordDependency { store, record_id })
    }

    #[cfg(test)]
    pub(super) fn contains_shared(&self, dependency: SharedDependency) -> bool {
        self.shared.contains(&dependency)
    }

    #[cfg(test)]
    pub(super) fn before_image(&self, store: FixedStore, record_id: u64) -> Option<&[u8]> {
        match self
            .fixed_records
            .get(&FixedRecordDependency { store, record_id })?
        {
            BeforeImage::Captured(image) => Some(image),
            BeforeImage::Pending => None,
        }
    }
}

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

    #[test]
    fn tracks_fixed_and_shared_dependencies_independently() {
        let mut write_set = WriteSet::default();
        write_set.insert_fixed(FixedStore::Node, 7);
        write_set.insert_shared(SharedDependency::Counts);

        assert!(write_set.contains_fixed(FixedStore::Node, 7));
        assert!(!write_set.contains_fixed(FixedStore::Node, 8));
        assert!(write_set.contains_shared(SharedDependency::Counts));
        assert!(!write_set.contains_shared(SharedDependency::Tokens));
    }

    #[test]
    fn captures_each_before_image_only_once() {
        let mut write_set = WriteSet::default();
        write_set.insert_fixed(FixedStore::Node, 7);
        let dependency = write_set.pending_fixed()[0];

        write_set.capture_before_image(dependency, vec![1, 2, 3]);
        write_set.capture_before_image(dependency, vec![4, 5, 6]);

        assert_eq!(
            write_set.before_image(FixedStore::Node, 7),
            Some(&[1, 2, 3][..])
        );
        assert!(write_set.pending_fixed().is_empty());
    }

    #[test]
    fn rebase_requires_complete_images_and_accepts_validated_shared_dependencies() {
        let mut write_set = WriteSet::default();
        assert!(write_set.rebase_dependencies().is_none());
        write_set.insert_fixed(FixedStore::Node, 7);
        assert!(write_set.rebase_dependencies().is_none());

        let dependency = write_set.pending_fixed()[0];
        write_set.capture_before_image(dependency, vec![1, 2, 3]);
        assert_eq!(
            write_set.rebase_dependencies().unwrap(),
            vec![(dependency, &[1, 2, 3][..])]
        );

        write_set.insert_shared(SharedDependency::DynamicChains);
        assert!(write_set.rebase_dependencies().is_some());

        write_set.insert_shared(SharedDependency::IdAllocation);
        assert!(write_set.rebase_dependencies().is_some());

        write_set.insert_shared(SharedDependency::Counts);
        assert!(write_set.rebase_dependencies().is_some());

        write_set.insert_shared(SharedDependency::IdReclamation);
        assert!(write_set.rebase_dependencies().is_some());

        write_set.insert_shared(SharedDependency::RelationshipGroupDegrees);
        assert!(write_set.rebase_dependencies().is_some());

        write_set.insert_shared(SharedDependency::IdReuse);
        assert!(write_set.rebase_dependencies().is_some());
        assert!(write_set.requires_reused_id_validation());

        write_set.insert_shared(SharedDependency::Tokens);
        assert!(write_set.rebase_dependencies().is_some());
    }

    #[test]
    fn only_id_reuse_requires_free_list_reselection() {
        let mut write_set = WriteSet::default();
        for dependency in [
            SharedDependency::DynamicChains,
            SharedDependency::IdAllocation,
            SharedDependency::IdReclamation,
            SharedDependency::Counts,
            SharedDependency::RelationshipGroupDegrees,
            SharedDependency::Tokens,
        ] {
            write_set.insert_shared(dependency);
        }
        assert!(!write_set.requires_reused_id_validation());

        write_set.insert_shared(SharedDependency::IdReuse);
        assert!(write_set.requires_reused_id_validation());
    }
}