comtains 0.1.1

#![cfg_attr(docsrs, feature(doc_cfg))]

//! Compile-time optimized membership checks for static byte sequences.
//!
//! `comtains` expands fixed sets of byte strings into zero-allocation,
//! branch-ordered decision trees. The resulting [`ByteSet`] can be embedded
//! directly into hot parsers, opcode dispatchers, or protocol classifiers
//! without any runtime preprocessing.
//!
//! # Example
//! ```rust
//! use comtains::{byte_set, ByteSet};
//!
//! const KEYWORDS: ByteSet = byte_set![
//!     b"GET",
//!     b"POST",
//!     b"PUT",
//!     b"PATCH",
//! ];
//!
//! assert!(KEYWORDS.contains(b"POST"));
//! assert!(!KEYWORDS.contains(b"DELETE"));
//! ```
//!
//! # Design
//! 1. The `byte_set!` macro parses string or byte-sequence literals at compile
//!    time and builds a trie that merges shared prefixes.
//! 2. Each branch records how many sequences pass through it; siblings are
//!    sorted by descending weight so the hottest paths are checked first.
//! 3. The macro emits a nested `match` ladder that compares each byte via
//!    `candidate.get(depth)`, returning early on the first mismatch.
//! 4. Optional debug metadata mirrors the trie structure so unit tests and
//!    benchmarks can assert branch ordering.

extern crate self as comtains;

pub use comtains_macros::byte_set;

/// A compile-time generated byte-set matcher.
///
/// Instances of `ByteSet` are produced by the [`byte_set!`] macro. Each matcher
/// expands to a fully inlined decision tree that short-circuits on the first
/// mismatching byte, avoiding any heap allocations or runtime preprocessing.
#[derive(Clone, Copy, Debug)]
pub struct ByteSet {
    pub(crate) contains: fn(&[u8]) -> bool,
    pub(crate) len: usize,
    #[allow(dead_code)]
    pub(crate) metadata: &'static debug::ByteSetMetadata,
}

impl ByteSet {
    #[doc(hidden)]
    pub const fn __from_parts(
        contains: fn(&[u8]) -> bool,
        len: usize,
        metadata: &'static debug::ByteSetMetadata,
    ) -> Self {
        Self {
            contains,
            len,
            metadata,
        }
    }

    /// Returns `true` when the provided sequence is a member of the set.
    ///
    /// The lookup short-circuits on the first mismatching byte and never
    /// allocates.
    ///
    /// ```
    /// use comtains::{byte_set, ByteSet};
    ///
    /// const HTTP_METHODS: ByteSet = byte_set![b"GET", b"POST", b"PUT"];
    /// assert!(HTTP_METHODS.contains(b"POST"));
    /// assert!(!HTTP_METHODS.contains(b"DELETE"));
    /// ```
    #[inline(always)]
    pub fn contains(&self, candidate: &[u8]) -> bool {
        (self.contains)(candidate)
    }

    /// Number of sequences stored in the set.
    ///
    /// ```
    /// use comtains::{byte_set, ByteSet};
    ///
    /// const PAIRS: ByteSet = byte_set![b"ab", b"cd", b"ef"];
    /// assert_eq!(PAIRS.len(), 3);
    /// ```
    #[inline(always)]
    pub const fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` when the set is empty.
    ///
    /// ```
    /// use comtains::{byte_set, ByteSet};
    ///
    /// const EMPTY: ByteSet = byte_set![];
    /// assert!(EMPTY.is_empty());
    /// ```
    #[inline(always)]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[allow(dead_code)]
    pub(crate) fn debug_nodes(&self) -> &'static [debug::DebugNode] {
        self.metadata.nodes
    }

    #[allow(dead_code)]
    pub(crate) fn debug_edges(&self) -> &'static [debug::DebugEdge] {
        self.metadata.edges
    }
}

/// Introspection helpers emitted alongside every matcher.
/// Structures describing the generated trie. Intended for tests and debugging.
#[allow(dead_code)]
pub mod debug {
    /// Minimal node description emitted for tests and debugging.
    #[derive(Clone, Copy, Debug)]
    pub struct DebugNode {
        /// `true` if the node corresponds to a complete sequence.
        pub terminal: bool,
        /// Starting index of this node's children in the edge table.
        pub child_start: usize,
        /// Number of outgoing edges from this node.
        pub child_len: usize,
    }

    /// Minimal edge description emitted for tests and debugging.
    #[derive(Clone, Copy, Debug)]
    pub struct DebugEdge {
        /// Byte label associated with the transition.
        pub byte: u8,
        /// Index of the target node within the node table.
        pub target: usize,
        /// Number of sequences that traversed this edge.
        pub weight: usize,
    }

    /// Metadata bundle exported from the macro for inspection.
    #[derive(Clone, Copy, Debug)]
    pub struct ByteSetMetadata {
        /// Table of trie nodes in breadth-first order.
        pub nodes: &'static [DebugNode],
        /// Table of edges grouped per node.
        pub edges: &'static [DebugEdge],
    }

    pub const EMPTY_NODES: [DebugNode; 0] = [];
    pub const EMPTY_EDGES: [DebugEdge; 0] = [];
}

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

    const EXAMPLE_SET: ByteSet =
        byte_set![b"\xA0\xB1", b"\xA1\xB2", b"\xA1\xB2\xC3", b"\xA1\xB2\xC4"];

    #[test]
    fn finds_present_sequences() {
        assert!(EXAMPLE_SET.contains(b"\xA0\xB1"));
        assert!(EXAMPLE_SET.contains(b"\xA1\xB2"));
        assert!(EXAMPLE_SET.contains(b"\xA1\xB2\xC3"));
        assert!(EXAMPLE_SET.contains(b"\xA1\xB2\xC4"));
    }

    #[test]
    fn rejects_missing_sequences() {
        assert!(!EXAMPLE_SET.contains(b""));
        assert!(!EXAMPLE_SET.contains(b"\xA1"));
        assert!(!EXAMPLE_SET.contains(b"\xA1\xB2\x00"));
        assert!(!EXAMPLE_SET.contains(b"\xA1\xB3"));
        assert!(!EXAMPLE_SET.contains(b"\xA1\xB2\xC5"));
    }

    #[test]
    fn exposes_weighted_trie_structure() {
        let nodes = EXAMPLE_SET.debug_nodes();
        let edges = EXAMPLE_SET.debug_edges();

        assert!(
            nodes.len() >= 3,
            "expected at least three nodes in the trie"
        );
        let root = &nodes[0];
        assert!(
            root.child_len >= 2,
            "root should branch to shared A0 and A1 prefixes"
        );

        let first_child = &edges[root.child_start];
        let second_child = &edges[root.child_start + 1];

        assert_eq!(first_child.byte, 0xA1, "most common prefix should be A1");
        assert_eq!(
            first_child.weight, 3,
            "A1 branch should cover three sequences"
        );
        assert_eq!(
            second_child.byte, 0xA0,
            "less common branch should come second"
        );
        assert_eq!(
            second_child.weight, 1,
            "A0 branch should cover one sequence"
        );

        let shared_node = &nodes[first_child.target];
        assert!(
            shared_node.child_len >= 1,
            "branch A1 should have further children"
        );

        let mut found_b2 = false;
        let mut idx = shared_node.child_start;
        while idx < shared_node.child_start + shared_node.child_len {
            if edges[idx].byte == 0xB2 {
                assert_eq!(
                    edges[idx].weight, 3,
                    "A1B2 should be shared by all remaining sequences"
                );
                found_b2 = true;
                break;
            }
            idx += 1;
        }
        assert!(found_b2, "expected a child edge for byte B2 after A1");
    }

    #[test]
    fn supports_string_literals() {
        const STRING_SET: ByteSet = byte_set!["AA", "AB", "ABC"];
        assert!(STRING_SET.contains(b"AA"));
        assert!(STRING_SET.contains(b"AB"));
        assert!(!STRING_SET.contains(b"A"));
        assert!(!STRING_SET.contains(b"AC"));
    }

    #[test]
    fn supports_array_literals() {
        const ARRAY_SET: ByteSet = byte_set![[0x10, 0x20], [0x10, 0x20, 0x30]];
        assert!(ARRAY_SET.contains(&[0x10, 0x20]));
        assert!(ARRAY_SET.contains(&[0x10, 0x20, 0x30]));
        assert!(!ARRAY_SET.contains(&[0x10]));
        assert!(!ARRAY_SET.contains(&[0x10, 0x30]));
    }
}