libdictenstein 4.0.0-rc.3

//! Lock-free, TrieRef-based PathMap zipper.
//!
//! [`PathMapZipper`] (and its borrowed sibling [`PathMapZipperRef`]) navigate a
//! PathMap trie through a [`TrieRefLike`] focus handle. Each `descend` /
//! `children` is a constant-time, lock-free step from the focus — no
//! per-operation lock and no replay of the path from the root (the historical
//! lock-per-operation, root-replay zipper this supersedes). A `path` byte buffer
//! is retained solely so [`DictZipper::path`] can reconstruct the byte path.

use super::ascii::PathMapDictionary;
use super::core::{trie_ref_root, trie_ref_root_borrowed, TrieRefLike};
use crate::value::DictionaryValue;
use crate::zipper::{DictZipper, ValuedDictZipper};
use pathmap::zipper::{TrieRefBorrowed, TrieRefOwned};
use pathmap::PathMap;
use std::marker::PhantomData;
use std::sync::Arc;

/// Zipper for PathMap-backed dictionaries, generic over the [`TrieRefLike`]
/// focus handle `R`.
///
/// Stores the focus handle `r` (already descended to the current position) plus
/// a `path` byte buffer kept only so [`DictZipper::path`] can reconstruct the
/// path. Defaults to the owned [`TrieRefOwned`] handle ([`PathMapZipper`]); the
/// borrowed, zero-copy variant is [`PathMapZipperRef`].
///
/// # Snapshot isolation
///
/// An owned zipper binds to a consistent `𝒪(1)` copy-on-write snapshot taken at
/// construction; concurrent mutations of the source dictionary are not observed
/// mid-traversal.
///
/// # Examples
///
/// ```ignore
/// use libdictenstein::DictZipper;
/// use libdictenstein::pathmap::PathMapDictionary;
/// use libdictenstein::pathmap::zipper::PathMapZipper;
///
/// let dict = PathMapDictionary::<()>::new();
/// // ... insert terms ...
/// let zipper = PathMapZipper::new_from_dict(&dict);
/// if let Some(c) = zipper.descend(b'c') {
///     if let Some(a) = c.descend(b'a') {
///         if let Some(t) = a.descend(b't') {
///             if t.is_final() { println!("Found 'cat'"); }
///         }
///     }
/// }
/// ```
pub struct TrieRefZipper<V: DictionaryValue, R: TrieRefLike<V> = TrieRefOwned<V>> {
    r: R,
    /// Byte path from the root, retained only for [`DictZipper::path`].
    path: Arc<[u8]>,
    _v: PhantomData<fn() -> V>,
}

/// Owned, snapshot-backed PathMap zipper (the default).
pub type PathMapZipper<V> = TrieRefZipper<V, TrieRefOwned<V>>;

/// Borrowed, zero-copy PathMap zipper over a live map for lifetime `'a`.
pub type PathMapZipperRef<'a, V> = TrieRefZipper<V, TrieRefBorrowed<'a, V>>;

// Manual `Clone` (a `#[derive]` would spuriously require `V: Clone`; clone is
// just the handle + `Arc` refcount bumps).
impl<V: DictionaryValue, R: TrieRefLike<V>> Clone for TrieRefZipper<V, R> {
    #[inline]
    fn clone(&self) -> Self {
        Self {
            r: self.r.clone(),
            path: Arc::clone(&self.path),
            _v: PhantomData,
        }
    }
}

impl<V: DictionaryValue, R: TrieRefLike<V>> TrieRefZipper<V, R> {
    #[inline]
    fn from_parts(r: R, path: Arc<[u8]>) -> Self {
        Self {
            r,
            path,
            _v: PhantomData,
        }
    }

    /// Borrow the underlying focus handle.
    #[inline]
    pub fn trie_ref(&self) -> &R {
        &self.r
    }
}

impl<V: DictionaryValue> PathMapZipper<V> {
    /// Create a root zipper over an `𝒪(1)` copy-on-write snapshot of `dict`.
    pub fn new_from_dict(dict: &PathMapDictionary<V>) -> Self {
        let state = dict.load_state();
        Self::from_parts(trie_ref_root(state.map.clone()), Arc::from(Vec::new()))
    }

    /// Create a root zipper from an owned `PathMap` (consumes it).
    pub fn from_map(map: PathMap<V>) -> Self {
        Self::from_parts(trie_ref_root(map), Arc::from(Vec::new()))
    }

    /// Create a root zipper from an `𝒪(1)` CoW snapshot of a borrowed map.
    pub fn from_map_ref(map: &PathMap<V>) -> Self {
        Self::from_parts(trie_ref_root(map.clone()), Arc::from(Vec::new()))
    }

    /// Wrap an existing owned TrieRef root handle.
    pub fn from_trie_ref(root: TrieRefOwned<V>) -> Self {
        Self::from_parts(root, Arc::from(Vec::new()))
    }
}

impl<'a, V: DictionaryValue> PathMapZipperRef<'a, V> {
    /// Create a borrowed, zero-copy root zipper over a live map.
    pub fn from_map(map: &'a PathMap<V>) -> Self {
        Self::from_parts(trie_ref_root_borrowed(map), Arc::from(Vec::new()))
    }

    /// Wrap an existing borrowed TrieRef root handle.
    pub fn from_trie_ref(root: TrieRefBorrowed<'a, V>) -> Self {
        Self::from_parts(root, Arc::from(Vec::new()))
    }
}

impl<V: DictionaryValue, R: TrieRefLike<V>> DictZipper for TrieRefZipper<V, R> {
    type Unit = u8;

    #[inline]
    fn is_final(&self) -> bool {
        self.r.is_val()
    }

    #[inline]
    fn descend(&self, label: Self::Unit) -> Option<Self> {
        let focus = self.r.descend_bytes(&[label]);
        if focus.path_exists() {
            let mut new_path = Vec::with_capacity(self.path.len() + 1);
            new_path.extend_from_slice(&self.path);
            new_path.push(label);
            Some(Self::from_parts(focus, Arc::from(new_path)))
        } else {
            None
        }
    }

    fn children(&self) -> impl Iterator<Item = (Self::Unit, Self)> {
        // Lock-free: the child mask proves each byte lands on an existing path,
        // so we descend directly from the focus with no re-validation, no lock,
        // and no 256-way bit scan (`ByteMask::iter()` is word-skipping).
        let r = self.r.clone();
        let base = Arc::clone(&self.path);
        r.child_mask().iter().map(move |byte| {
            let focus = r.descend_bytes(&[byte]);
            let mut new_path = Vec::with_capacity(base.len() + 1);
            new_path.extend_from_slice(&base);
            new_path.push(byte);
            (byte, Self::from_parts(focus, Arc::from(new_path)))
        })
    }

    #[inline]
    fn path(&self) -> Vec<Self::Unit> {
        self.path.to_vec()
    }
}

impl<V: DictionaryValue, R: TrieRefLike<V>> ValuedDictZipper for TrieRefZipper<V, R> {
    type Value = V;

    #[inline]
    fn value(&self) -> Option<Self::Value> {
        self.r.val_cloned()
    }
}

#[cfg(test)]
mod tests {
    use super::super::ascii::PathMapDictionary;
    use super::*;
    use crate::zipper::{DictZipper, ValuedDictZipper};

    #[test]
    fn test_root_zipper_not_final() {
        let dict = PathMapDictionary::<()>::new();
        let zipper = PathMapZipper::new_from_dict(&dict);

        assert!(!zipper.is_final());
        assert_eq!(zipper.path(), Vec::<u8>::new());
    }

    #[test]
    fn test_descend_nonexistent() {
        let dict = PathMapDictionary::<()>::new();
        let zipper = PathMapZipper::new_from_dict(&dict);

        assert!(zipper.descend(b'a').is_none());
    }

    #[test]
    fn test_descend_and_finality() {
        let dict = PathMapDictionary::<()>::new();
        dict.insert("cat");
        dict.insert("catch");

        let zipper = PathMapZipper::new_from_dict(&dict);

        // Navigate to 'c'
        let c = zipper.descend(b'c').expect("'c' should exist");
        assert!(!c.is_final());
        assert_eq!(c.path(), vec![b'c']);

        // Navigate to 'ca'
        let a = c.descend(b'a').expect("'a' should exist");
        assert!(!a.is_final());
        assert_eq!(a.path(), vec![b'c', b'a']);

        // Navigate to 'cat'
        let t = a.descend(b't').expect("'t' should exist");
        assert!(t.is_final()); // "cat" is a complete term
        assert_eq!(t.path(), vec![b'c', b'a', b't']);

        // Navigate to 'catc'
        let c2 = t.descend(b'c').expect("'c' should exist");
        assert!(!c2.is_final());

        // Navigate to 'catch'
        let h = c2.descend(b'h').expect("'h' should exist");
        assert!(h.is_final()); // "catch" is a complete term
        assert_eq!(h.path(), vec![b'c', b'a', b't', b'c', b'h']);
    }

    #[test]
    fn test_children_iteration() {
        let dict = PathMapDictionary::<()>::new();
        dict.insert("a");
        dict.insert("b");
        dict.insert("c");

        let zipper = PathMapZipper::new_from_dict(&dict);

        let children: Vec<_> = zipper.children().collect();

        assert_eq!(children.len(), 3);

        let labels: Vec<u8> = children.iter().map(|(label, _)| *label).collect();
        assert!(labels.contains(&b'a'));
        assert!(labels.contains(&b'b'));
        assert!(labels.contains(&b'c'));

        // Verify each child is final (single-character terms)
        for (_, child) in children {
            assert!(child.is_final());
        }
    }

    #[test]
    fn test_children_with_prefix() {
        let dict = PathMapDictionary::<()>::new();
        dict.insert("cat");
        dict.insert("car");
        dict.insert("dog");

        let zipper = PathMapZipper::new_from_dict(&dict);

        // Navigate to 'c'
        let c = zipper.descend(b'c').expect("'c' should exist");

        // 'c' should have one child: 'a'
        let children: Vec<_> = c.children().collect();
        assert_eq!(children.len(), 1);
        assert_eq!(children[0].0, b'a');

        // Navigate to 'ca'
        let a = c.descend(b'a').expect("'a' should exist");

        // 'ca' should have two children: 't' and 'r'
        let children: Vec<_> = a.children().collect();
        assert_eq!(children.len(), 2);

        let labels: Vec<u8> = children.iter().map(|(label, _)| *label).collect();
        assert!(labels.contains(&b't'));
        assert!(labels.contains(&b'r'));
    }

    #[test]
    fn test_valued_zipper() {
        let dict = PathMapDictionary::<u32>::new();
        dict.insert_with_value("print", 42);
        dict.insert_with_value("parse", 100);

        let zipper = PathMapZipper::new_from_dict(&dict);

        // Navigate to "print"
        let p = zipper.descend(b'p').unwrap();
        let r = p.descend(b'r').unwrap();
        let i = r.descend(b'i').unwrap();
        let n = i.descend(b'n').unwrap();
        let t = n.descend(b't').unwrap();

        assert!(t.is_final());
        assert_eq!(t.value(), Some(42));

        // Navigate to "parse" - restart from 'p'
        let a = p.descend(b'a').unwrap();
        let r = a.descend(b'r').unwrap();
        let s = r.descend(b's').unwrap();
        let e = s.descend(b'e').unwrap();

        assert!(e.is_final());
        assert_eq!(e.value(), Some(100));
    }

    #[test]
    fn test_valued_zipper_with_vec() {
        let dict = PathMapDictionary::<Vec<u32>>::new();
        dict.insert_with_value("global", vec![0]);
        dict.insert_with_value("local", vec![1, 2, 3]);

        let zipper = PathMapZipper::new_from_dict(&dict);

        // Navigate to "global"
        let mut z = zipper.clone();
        for &byte in b"global" {
            z = z.descend(byte).unwrap();
        }

        assert!(z.is_final());
        assert_eq!(z.value(), Some(vec![0]));

        // Navigate to "local"
        let mut z = zipper;
        for &byte in b"local" {
            z = z.descend(byte).unwrap();
        }

        assert!(z.is_final());
        assert_eq!(z.value(), Some(vec![1, 2, 3]));
    }

    #[test]
    fn test_path_reconstruction() {
        let dict = PathMapDictionary::<()>::new();
        dict.insert("hello");

        let zipper = PathMapZipper::new_from_dict(&dict);

        let mut z = zipper;
        let mut expected_path = Vec::new();

        for &byte in b"hello" {
            z = z.descend(byte).unwrap();
            expected_path.push(byte);
            assert_eq!(z.path(), expected_path);
        }

        assert_eq!(z.path(), b"hello".to_vec());
        assert_eq!(String::from_utf8(z.path()).unwrap(), "hello");
    }

    #[test]
    fn test_clone_independence() {
        let dict = PathMapDictionary::<()>::new();
        dict.insert("abc");

        let zipper = PathMapZipper::new_from_dict(&dict);

        let z1 = zipper.clone();
        let z2 = zipper.clone();

        // Navigate z1
        let z1_a = z1.descend(b'a').unwrap();

        // z2 should still be at root
        assert_eq!(z2.path(), Vec::<u8>::new());

        // z1_a should be at 'a'
        assert_eq!(z1_a.path(), vec![b'a']);
    }

    #[test]
    fn test_empty_dictionary() {
        let dict = PathMapDictionary::<()>::new();
        let zipper = PathMapZipper::new_from_dict(&dict);

        assert!(!zipper.is_final());
        assert_eq!(zipper.path(), Vec::<u8>::new());

        // No children in empty dictionary
        let children: Vec<_> = zipper.children().collect();
        assert_eq!(children.len(), 0);

        // Can't descend anywhere
        assert!(zipper.descend(b'a').is_none());
    }
}