libdictenstein 0.2.0

//! High-performance dictionary data structures — tries, DAWGs, double-array tries, suffix
//! automata, compact suffix graphs, and lock-free durable Adaptive Radix Tries —
//! unified behind one trait API.
//!
//! libdictenstein provides the *container* half of approximate string matching: efficient,
//! traversable collections of terms. The *query* half — a Levenshtein-automaton transducer —
//! lives in the companion crate [`liblevenshtein`](https://github.com/universal-automata/liblevenshtein-rust),
//! which walks any type implementing [`Dictionary`]. This crate contains no fuzzy-matching code itself.
//!
//! # Choosing a Dictionary Backend
//!
//! ## In-memory backends
//!
//! | Backend | Best For | Performance | Memory | Dynamic Updates | Unicode |
//! |---------|----------|-------------|--------|-----------------|---------|
//! | **[DoubleArrayTrie]** | General use (recommended) | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | ✅ Insert-only | Byte-level |
//! | **[DoubleArrayTrieChar]** | Unicode text | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | ✅ Insert-only | ✅ Character-level |
//! | **[DynamicDawg]** | Insert + Remove | ⭐⭐⭐ | ⭐⭐⭐ | ✅ Thread-safe | Byte-level |
//! | **[DynamicDawgChar]** | Unicode + Insert + Remove | ⭐⭐⭐ | ⭐⭐⭐ | ✅ Thread-safe | ✅ Character-level |
//! | **[DynamicDawgU64]** | Token sequences, time series | ⭐⭐⭐ | ⭐⭐ | ✅ Thread-safe | 64-bit labels |
//! | **[SuffixAutomaton]** | Substring search | ⭐⭐⭐ | ⭐⭐ | ✅ Insert + Remove | Byte-level |
//! | **[SuffixAutomatonChar]** | Unicode substring search | ⭐⭐⭐ | ⭐⭐ | ✅ Insert + Remove | ✅ Character-level |
//! | **[Scdawg]** | Substring search (static, compact) | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | ✅ Insert-only | Byte-level |
//! | **[ScdawgChar]** | Unicode substring search (static) | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | ✅ Insert-only | ✅ Character-level |
//! | **`PathMapDictionary`** (feature `pathmap-backend`) | Fast in-memory queries | ⭐⭐⭐⭐ | ⭐⭐⭐ | ✅ Thread-safe | Byte-level |
//! | **`PathMapDictionaryChar`** (feature `pathmap-backend`) | Fast in-memory queries (Unicode) | ⭐⭐⭐⭐ | ⭐⭐⭐ | ✅ Thread-safe | ✅ Character-level |
//!
//! ## Disk-backed backends (feature `persistent-artrie`)
//!
//! | Backend | Best For | Persistence | Concurrency | Unicode |
//! |---------|----------|-------------|-------------|---------|
//! | **[PersistentARTrie]** | Disk-backed key/value, byte keys | mmap + WAL | Lock-free CAS | Byte-level |
//! | **[PersistentARTrieChar]** | Disk-backed key/value, Unicode | mmap + WAL | Lock-free CAS | ✅ Character-level |
//! | **[PersistentARTrieU64]** / **[PersistentARTrieU64Compact]** | Disk-backed sequence key/value, native u64 labels | overlay CX snapshot + WAL | Lock-free CAS | 64-bit labels |
//! | **[PersistentARTrieU64Prefix3Compat]** | Prefix-3 u64 CX compatibility/baseline profile | overlay CX snapshot + WAL | Lock-free CAS | 64-bit labels |
//! | **[PersistentSuffixAutomaton]** | Disk-backed substring search, byte keys | native suffix snapshot + WAL | Snapshot reads, COW writes | Byte-level |
//! | **[PersistentSuffixAutomatonChar]** | Disk-backed Unicode substring search | native suffix snapshot + WAL | Snapshot reads, COW writes | ✅ Character-level |
//! | **[PersistentSuffixTree]** | Disk-backed suffix-tree-compatible substring API, byte keys | native compact suffix-tree snapshot + WAL | Snapshot reads, COW writes | Byte-level |
//! | **[PersistentSuffixTreeChar]** | Disk-backed suffix-tree-compatible Unicode substring API | native compact suffix-tree snapshot + WAL | Snapshot reads, COW writes | ✅ Character-level |
//! | **[PersistentScdawg]** | Disk-backed compact-suffix API, byte keys | native SCDAWG snapshot + WAL | Snapshot reads, COW writes | Byte-level |
//! | **[PersistentScdawgChar]** | Disk-backed compact-suffix API, Unicode | native SCDAWG snapshot + WAL | Snapshot reads, COW writes | ✅ Character-level |
//! | **[PersistentVocabARTrie]** | Vocabulary trie (term ↔ u64 index) | overlay checkpoint + WAL | Lock-free CAS | ✅ Character-level |
//!
//! Use the [`factory::DictionaryFactory`] for a unified construction API across
//! all in-memory backends. See [`bijective::BijectiveDictionary`] for the
//! bidirectional-lookup trait shared by `BijectiveMap` and the vocab tries.
//!
//! [DoubleArrayTrie]: double_array_trie::DoubleArrayTrie
//! [DoubleArrayTrieChar]: double_array_trie::DoubleArrayTrieChar
//! [DynamicDawg]: dynamic_dawg::DynamicDawg
//! [DynamicDawgChar]: dynamic_dawg::DynamicDawgChar
//! [DynamicDawgU64]: dynamic_dawg::DynamicDawgU64
//! [SuffixAutomaton]: suffix_automaton::SuffixAutomaton
//! [SuffixAutomatonChar]: suffix_automaton::SuffixAutomatonChar
//! [Scdawg]: scdawg::Scdawg
//! [ScdawgChar]: scdawg::ScdawgChar
//! [PersistentARTrie]: persistent_artrie::PersistentARTrie
//! [PersistentARTrieChar]: persistent_artrie::char::PersistentARTrieChar
//! [PersistentARTrieU64]: persistent_artrie::PersistentARTrieU64
//! [PersistentARTrieU64Compact]: persistent_artrie::PersistentARTrieU64Compact
//! [PersistentARTrieU64Prefix3Compat]: persistent_artrie::PersistentARTrieU64Prefix3Compat
//! [PersistentSuffixAutomaton]: persistent_artrie::PersistentSuffixAutomaton
//! [PersistentSuffixAutomatonChar]: persistent_artrie::PersistentSuffixAutomatonChar
//! [PersistentSuffixTree]: persistent_artrie::PersistentSuffixTree
//! [PersistentSuffixTreeChar]: persistent_artrie::PersistentSuffixTreeChar
//! [PersistentScdawg]: persistent_artrie::PersistentScdawg
//! [PersistentScdawgChar]: persistent_artrie::PersistentScdawgChar
//! [PersistentVocabARTrie]: persistent_artrie::vocab::PersistentVocabARTrie

// === Shared infrastructure ===
pub mod bijective;
pub mod bloom_filter;
pub mod char_unit;
pub mod factory;
pub mod iterator;
pub mod node_signature;
pub mod substring;
pub mod sync_compat;
pub mod value;
pub mod zipper;

// === Zipper combinators ===
pub mod difference_zipper;
pub mod excluding_prefix_zipper;
pub mod intersection_zipper;
pub mod prefix_zipper;
pub mod symmetric_difference_zipper;
pub mod union_zipper;
pub mod value_diff_zipper;

// === Dictionary families ===
// Each family is a directory submodule whose `mod.rs` re-exports the family's
// public types. Within a family: `ascii` = byte/`u8` base, `char` = Unicode
// (`char`), `u64` = `u64`-labeled (dynamic_dawg only), `core` = the unit-generic
// substrate shared by the variants, and `*zipper` = the navigators.
pub mod double_array_trie;
pub mod dynamic_dawg;
#[cfg(feature = "pathmap-backend")]
pub mod pathmap;
pub mod scdawg;
pub mod suffix_automaton;

// === Persistent ARTrie modules (feature-gated at module level) ===
// These modules are gated here; internal code does NOT need feature gates.
//
// Layering: `persistent_artrie::core` is the shared substrate; the three
// variants depend on core, never on each other. See
// `persistent_artrie/core/mod.rs` for the invariant.
#[cfg(feature = "persistent-artrie")]
pub mod artrie_trait;
#[cfg(feature = "persistent-artrie")]
pub mod persistent_artrie;

#[cfg(feature = "serialization")]
pub mod serialization;

// Re-export core types at crate root
pub use bijective::{BijectiveDictionary, BijectiveMap, InsertError};
pub use bloom_filter::BloomFilter;
pub use char_unit::CharUnit;
pub use dynamic_dawg::core::{DawgCore, DawgNode};
pub use iterator::{DictionaryIterator, DictionaryTermIterator};
pub use node_signature::NodeSignature;
pub use substring::{
    BidirectionalDictionaryNode, ExtensionResult, SubstringDictionary, SubstringMatch,
};
pub use value::DictionaryValue;
pub use zipper::{DictZipper, ValuedDictZipper};

// Re-export persistent ARTrie types (only available with feature)
#[cfg(feature = "persistent-artrie")]
pub use artrie_trait::{ARTrie, EvictableARTrie};
// `ARTrieAtomicOps` is #[deprecated]; re-exported behind an allow so the
// re-export site itself doesn't spam warnings. External callers that name
// the trait still get the deprecation message.
#[cfg(feature = "persistent-artrie")]
#[allow(deprecated)]
pub use artrie_trait::ARTrieAtomicOps;
#[cfg(feature = "persistent-artrie")]
pub use persistent_artrie::char::{
    PersistentARTrieChar, PersistentARTrieCharNode, PersistentARTrieCharZipper,
};
#[cfg(feature = "persistent-artrie")]
pub use persistent_artrie::vocab::{IndexedVocabularyPersistent, PersistentVocabARTrie};
#[cfg(feature = "persistent-artrie")]
pub use persistent_artrie::wal::Lsn;
#[cfg(feature = "persistent-artrie")]
pub use persistent_artrie::{
    PersistentARTrie, PersistentARTrieU64, PersistentARTrieU64Node, PersistentARTrieZipper,
    PersistentScdawg, PersistentScdawgChar, PersistentScdawgCharNode, PersistentScdawgNode,
    PersistentSuffixAutomaton, PersistentSuffixAutomatonChar, PersistentSuffixAutomatonCharNode,
    PersistentSuffixAutomatonNode, PersistentSuffixTree, PersistentSuffixTreeChar,
    PersistentSuffixTreeCharNode, PersistentSuffixTreeNode, RecoveryMode, RecoveryReport,
    WalConfig,
};

/// Synchronization strategy for dictionary operations.
///
/// Different dictionary backends may have different thread-safety guarantees.
/// This trait allows backends to specify their synchronization requirements.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SyncStrategy {
    /// Backend requires external synchronization (e.g., RwLock).
    ///
    /// Use this for backends that use interior mutability without
    /// internal synchronization.
    ExternalSync,

    /// Backend is internally synchronized and safe for concurrent access.
    ///
    /// Use this for backends that use atomic operations, locks, or
    /// lock-free data structures internally.
    InternalSync,

    /// Backend is a persistent/immutable data structure.
    ///
    /// Mutations create new versions with structural sharing.
    /// Reads require no synchronization. Writes can use atomic swaps.
    Persistent,
}

/// Core dictionary abstraction for approximate string matching.
///
/// A dictionary represents a collection of terms that can be efficiently
/// traversed character-by-character via graph-like nodes. This trait
/// allows different backend implementations (trie, DAWG, double-array trie,
/// etc.) to be used interchangeably.
pub trait Dictionary {
    /// The node type used for dictionary traversal
    type Node: DictionaryNode;

    /// Get the root node of the dictionary
    fn root(&self) -> Self::Node;

    /// Check if a term exists in the dictionary
    fn contains(&self, term: &str) -> bool {
        let mut node = self.root();
        for unit in <Self::Node as DictionaryNode>::Unit::iter_str(term) {
            match node.transition(unit) {
                Some(next) => node = next,
                None => return false,
            }
        }
        node.is_final()
    }

    /// Get the total number of terms (if available efficiently)
    fn len(&self) -> Option<usize>;

    /// Check if the dictionary is empty
    fn is_empty(&self) -> bool {
        self.len().map(|n| n == 0).unwrap_or(false)
    }

    /// Get the synchronization strategy for this dictionary backend.
    ///
    /// This allows wrappers to optimize synchronization based on
    /// the backend's thread-safety guarantees.
    ///
    /// Default: `ExternalSync` (conservative, always safe)
    fn sync_strategy(&self) -> SyncStrategy {
        SyncStrategy::ExternalSync
    }

    /// Check if this dictionary uses suffix-based matching (substring search).
    ///
    /// Suffix-based dictionaries (like SuffixAutomaton) match substrings anywhere
    /// in the indexed text, whereas prefix-based dictionaries match complete words
    /// from the beginning.
    ///
    /// This affects how the Levenshtein automaton computes match distances:
    /// - Prefix-based: penalizes unmatched query suffix
    /// - Suffix-based: allows partial query matches without penalty
    ///
    /// Default: `false` (prefix-based matching)
    fn is_suffix_based(&self) -> bool {
        false
    }
}

/// Traversable dictionary node.
///
/// Nodes form a graph structure representing the dictionary, where edges
/// are labeled with character units (bytes or Unicode characters) and final
/// nodes mark valid terms.
///
/// # Type Parameters
///
/// The node is generic over [`CharUnit`], which can be:
/// - [`u8`] for byte-level matching (faster, ASCII-optimized)
/// - [`char`] for character-level matching (correct Unicode semantics)
pub trait DictionaryNode: Clone + Send + Sync {
    /// The character unit type for edge labels.
    ///
    /// Use `u8` for byte-level (existing behavior, fastest).
    /// Use `char` for character-level (proper Unicode support).
    type Unit: CharUnit;

    /// Check if this node marks the end of a valid term
    fn is_final(&self) -> bool;

    /// Transition to a child node via the given character unit
    ///
    /// Returns `None` if no such transition exists
    fn transition(&self, label: Self::Unit) -> Option<Self>;

    /// Iterate over all outgoing edges as (unit, child_node) pairs
    fn edges(&self) -> Box<dyn Iterator<Item = (Self::Unit, Self)> + '_>;

    /// Check if a specific edge exists
    fn has_edge(&self, label: Self::Unit) -> bool {
        self.transition(label).is_some()
    }

    /// Get the number of outgoing edges (if efficiently available)
    fn edge_count(&self) -> Option<usize> {
        None
    }
}

/// Extension trait for dictionaries that map terms to values.
///
/// This trait enables "fuzzy maps" - dictionaries that associate arbitrary values
/// with terms, allowing efficient filtered queries based on those values. This is
/// particularly useful for contextual code completion where terms are mapped to
/// scope IDs, categories, or other metadata.
pub trait MappedDictionary: Dictionary {
    /// The type of values associated with dictionary terms
    type Value: DictionaryValue;

    /// Get the value associated with a term.
    ///
    /// Returns `None` if the term doesn't exist in the dictionary.
    ///
    /// This is a required method. The previous default returned `None` for
    /// every term while pretending to be a real implementation, which silently
    /// broke any user expecting `MappedDictionary` semantics. Every backend in
    /// this crate now provides an explicit override.
    fn get_value(&self, term: &str) -> Option<Self::Value>;

    /// Check if a term exists and its value matches a predicate
    ///
    /// This is more efficient than `get_value` + predicate test, as it can
    /// short-circuit early if the term doesn't exist.
    fn contains_with_value<F>(&self, term: &str, predicate: F) -> bool
    where
        F: Fn(&Self::Value) -> bool,
    {
        self.get_value(term).is_some_and(|v| predicate(&v))
    }
}

/// Extension trait for dictionary nodes that provide access to values.
///
/// This trait allows nodes to expose values during graph traversal, enabling
/// efficient filtering at query time without materializing all results first.
pub trait MappedDictionaryNode: DictionaryNode {
    /// The type of values associated with terms at this node
    type Value: DictionaryValue;

    /// Get the value at this node if it's a final node
    ///
    /// Returns `None` if this is not a final node, or if no value is associated.
    fn value(&self) -> Option<Self::Value>;
}

/// Trait for dictionaries supporting set-like term insertion and removal.
///
/// This trait extends [`Dictionary`] with mutation capabilities. It is the
/// set-like interface — `insert(&str)` adds a term, `remove(&str)` removes
/// one, no values involved. For dictionaries that carry values along with
/// terms, see [`MutableMappedDictionary`].
///
/// # Overlap with `MutableMappedDictionary`
///
/// `MutableMappedDictionary` covers most write-with-value operations
/// (`insert_with_value`, `update_or_insert`, `union_with`, …) but
/// **deliberately omits** `remove` and the value-free `insert`. The two
/// traits are complementary, not redundant:
///
/// - Dictionaries that are set-like only (or have `Value = ()`): impl
///   [`MutableDictionary`].
/// - Dictionaries that carry meaningful values: impl
///   [`MutableMappedDictionary`] for value-aware writes and (if removal is
///   supported) [`MutableDictionary`] for set-like removal.
///
/// Several backends in this crate (`DynamicDawg`, `DynamicDawgChar`,
/// `DynamicDawgU64`) implement both.
///
/// # Default Implementations
///
/// The trait provides default implementations for batch operations
/// (`extend`, `remove_many`) built on top of the required `insert` and
/// `remove` methods.
pub trait MutableDictionary: Dictionary {
    /// Insert a term into the dictionary.
    ///
    /// Returns `true` if the term was newly inserted, `false` if it already existed.
    fn insert(&self, term: &str) -> bool;

    /// Remove a term from the dictionary.
    ///
    /// Returns `true` if the term was present and removed, `false` otherwise.
    fn remove(&self, term: &str) -> bool;

    /// Batch insert multiple terms.
    ///
    /// Returns the number of new terms added (not counting duplicates).
    ///
    /// The default implementation calls `insert` for each term. Implementations
    /// may override this for better performance.
    fn extend<I, S>(&self, terms: I) -> usize
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        terms
            .into_iter()
            .filter(|term| self.insert(term.as_ref()))
            .count()
    }

    /// Batch remove multiple terms.
    ///
    /// Returns the number of terms removed.
    ///
    /// The default implementation calls `remove` for each term. Implementations
    /// may override this for better performance.
    fn remove_many<I, S>(&self, terms: I) -> usize
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        terms
            .into_iter()
            .filter(|term| self.remove(term.as_ref()))
            .count()
    }
}

/// Trait for dictionaries supporting compaction and minimization.
///
/// Dictionaries that support dynamic modifications (insertions and deletions)
/// may accumulate internal fragmentation or redundant structure over time.
/// This trait provides methods to restore optimal structure.
///
/// # Compaction vs Minimization
///
/// - **`compact()`**: Full rebuild - extracts all terms, sorts them, and reconstructs
///   the structure from scratch. Achieves perfect minimality but is O(n log n + m).
///
/// - **`minimize()`**: Incremental optimization - merges equivalent nodes without
///   full rebuild. Faster for localized changes but may not achieve perfect minimality.
pub trait CompactableDictionary: MutableDictionary {
    /// Check if compaction would be beneficial.
    ///
    /// Returns `true` if deletions have occurred or the structure has degraded
    /// significantly from optimal.
    fn needs_compaction(&self) -> bool;

    /// Compact the dictionary to restore optimal structure.
    ///
    /// This performs a full rebuild, extracting all terms, sorting them for
    /// optimal prefix sharing, and reconstructing the dictionary.
    ///
    /// Returns the number of nodes/elements removed or optimized away.
    fn compact(&self) -> usize;

    /// Minimize the dictionary using incremental optimization.
    ///
    /// Unlike `compact()`, this method:
    /// - Makes no assumptions about insertion order
    /// - Only examines affected nodes and their neighbors
    /// - Preserves existing structure where possible
    /// - Is faster than `compact()` for localized updates
    ///
    /// Returns the number of nodes merged.
    ///
    /// The default implementation delegates to `compact()`. Dictionaries
    /// with more efficient incremental algorithms should override this.
    fn minimize(&self) -> usize {
        self.compact()
    }
}

/// Extension trait for dictionaries that support inserting values.
///
/// This trait enables mutation of mapped dictionaries, allowing terms to be
/// added or updated with associated values.
pub trait MutableMappedDictionary: MappedDictionary {
    /// Insert or update a term with an associated value.
    ///
    /// # Arguments
    ///
    /// * `term` - The term to insert
    /// * `value` - The value to associate with the term
    ///
    /// # Returns
    ///
    /// `true` if this is a new term, `false` if updating an existing term's value.
    fn insert_with_value(&self, term: &str, value: Self::Value) -> bool;

    /// Union this dictionary with another, applying a merge function for conflicting values.
    ///
    /// Iterates through all terms in `other` and:
    /// - Inserts new terms directly
    /// - For existing terms, merges values using `merge_fn`
    ///
    /// # Arguments
    ///
    /// * `other` - The dictionary to union with
    /// * `merge_fn` - Function to merge values when term exists in both dictionaries.
    ///   Takes `(existing_value, other_value)` and returns the merged value.
    ///
    /// # Returns
    ///
    /// Number of terms processed from `other`
    fn union_with<F>(&self, other: &Self, merge_fn: F) -> usize
    where
        F: Fn(&Self::Value, &Self::Value) -> Self::Value,
        Self::Value: Clone;

    /// Union with another dictionary, keeping the right (other's) value on conflicts.
    ///
    /// Convenience method equivalent to `union_with(other, |_, right| right.clone())`.
    fn union_replace(&self, other: &Self) -> usize
    where
        Self::Value: Clone,
    {
        self.union_with(other, |_, right| right.clone())
    }

    /// Update an existing term's value in place, or insert a new term with a default value.
    ///
    /// This method is useful when you want to incrementally modify a value (e.g., adding
    /// elements to a `HashSet` or `Vec`) without replacing it entirely.
    ///
    /// # Arguments
    ///
    /// * `term` - The term to update or insert
    /// * `default_value` - The value to use if the term doesn't exist
    /// * `update_fn` - Retry-safe function to apply to the existing value if the
    ///   term exists. Implementations with lock-free publication may invoke this
    ///   function more than once after CAS conflicts.
    ///
    /// # Returns
    ///
    /// `true` if this was a new term (inserted with default), `false` if an existing term was updated.
    fn update_or_insert<F>(&self, term: &str, default_value: Self::Value, update_fn: F) -> bool
    where
        F: Fn(&mut Self::Value);
}

/// Prelude module for convenient imports.
pub mod prelude {
    pub use crate::{
        BijectiveDictionary, BijectiveMap, CharUnit, CompactableDictionary, DictZipper, Dictionary,
        DictionaryNode, DictionaryValue, InsertError, MappedDictionary, MappedDictionaryNode,
        MutableDictionary, MutableMappedDictionary, SyncStrategy, ValuedDictZipper,
    };

    // Re-export common dictionary types
    pub use crate::double_array_trie::{DoubleArrayTrie, DoubleArrayTrieChar};
    pub use crate::dynamic_dawg::{DynamicDawg, DynamicDawgChar, DynamicDawgU64};
    pub use crate::scdawg::{Scdawg, ScdawgChar};
    pub use crate::suffix_automaton::{SuffixAutomaton, SuffixAutomatonChar};

    #[cfg(feature = "persistent-artrie")]
    pub use crate::persistent_artrie::{
        PersistentARTrieU64, PersistentScdawg, PersistentScdawgChar, PersistentSuffixAutomaton,
        PersistentSuffixAutomatonChar, PersistentSuffixTree, PersistentSuffixTreeChar,
    };
}