avila_atom/

lib.rs

//! # avila-atom
//!
//! **Atomic Computational Structures - Fundamental Data Structures**
//!
//! This library implements core data structures built from first principles,
//! providing type-safe primitives for systems programming with zero-compromise
//! performance characteristics.
//!
//! ## Available Structures
//!
//! - `Option<T>` - Optional value (presence/absence) - zero-cost abstraction
//! - `Result<T, E>` - Result type (success/failure) - enum-based sum type
//! - `DynamicArray<T>` - Contiguous growable array with amortized O(1) push
//! - `AssociativeArray<K, V>` - Hash-based or tree-based key-value store
//! - `StringBuffer` - UTF-8 encoded string with growable capacity
//!
//! ## Philosophy
//!
//! These structures are atomic computational primitives - stable elements
//! that compose infinitely to build complex software systems.
//!
//! ### Performance Characteristics
//!
//! - **Zero-cost abstractions**: No runtime overhead vs manual implementation
//! - **Memory locality**: Contiguous allocation for cache efficiency
//! - **Compile-time optimization**: Monomorphization enables aggressive inlining
//! - **Stack-preferred**: Structures optimize for stack allocation when possible
//!
//! ### no_std Compatibility
//!
//! All structures work in `no_std` environments with `alloc` feature:
//! - `AssociativeArray` falls back to B-Tree (O(log n)) instead of HashMap (O(1))
//! - Memory allocation via global allocator trait
//! - Zero dependency on operating system primitives

#![cfg_attr(not(feature = "std"), no_std)]
#![warn(missing_docs)]

#[cfg(feature = "std")]
extern crate std;

#[cfg(not(feature = "std"))]
extern crate alloc;

#[cfg(not(feature = "std"))]
use alloc::{vec::Vec, string::String, collections::BTreeMap};

#[cfg(feature = "std")]
use std::{vec::Vec, string::String, collections::HashMap};

/// Optional value type - represents presence or absence of a value
/// 
/// **Memory layout**: Single byte discriminant + value (if Some)
/// **Size**: `size_of::<T>() + 1` (optimized to `size_of::<T>()` for nullable pointers)
/// **Performance**: Zero-cost - compiles to same code as manual null checks
pub use core::option::Option;

/// Result type - represents success (Ok) or failure (Err)
/// 
/// **Memory layout**: Tagged union (discriminant + larger of Ok/Err)
/// **Size**: `1 + max(size_of::<T>(), size_of::<E>())`
/// **Performance**: Zero-cost abstraction, optimal enum representation
pub use core::result::Result;

/// Dynamic array with contiguous memory layout
/// 
/// **Complexity**:
/// - Access: O(1) by index
/// - Push: O(1) amortized (doubles capacity on realloc)
/// - Insert/Remove: O(n) for arbitrary position
/// 
/// **Memory**: `ptr + len + capacity` (24 bytes on 64-bit)
/// **Growth strategy**: Geometric progression (2x) for amortized O(1)
#[cfg(feature = "std")]
pub type DynamicArray<T> = Vec<T>;

#[cfg(not(feature = "std"))]
pub type DynamicArray<T> = Vec<T>;

/// Hash map (std) or B-Tree map (no_std) for key-value storage
/// 
/// **std mode** (HashMap):
/// - Lookup: O(1) average, O(n) worst case
/// - Insert: O(1) amortized
/// - Hasher: SipHash 1-3 (cryptographic, DoS resistant)
/// - Load factor: Grows at 90% capacity
/// 
/// **no_std mode** (BTreeMap):
/// - Lookup: O(log n)
/// - Insert: O(log n)
/// - Node size: Optimized for cache lines
/// - Ordering: Requires `K: Ord`
#[cfg(feature = "std")]
pub type AssociativeArray<K, V> = HashMap<K, V>;

#[cfg(not(feature = "std"))]
pub type AssociativeArray<K, V> = BTreeMap<K, V>;

/// UTF-8 encoded string buffer
/// 
/// **Guarantees**:
/// - Valid UTF-8 at all times (invariant enforced by type system)
/// - Contiguous memory layout
/// - Growable capacity with geometric progression
/// 
/// **Memory**: `ptr + len + capacity` (24 bytes on 64-bit)
/// **Validation**: All mutations validate UTF-8 boundaries
pub type StringBuffer = String;

/// Library version constant
pub const VERSION: &str = env!("CARGO_PKG_VERSION");

/// Compile-time size constants for common types
pub mod sizes {
    use core::mem::size_of;

    /// Size of Option<T> for non-nullable T
    pub const OPTION_OVERHEAD: usize = 1;
    
    /// Pointer size (32-bit: 4 bytes, 64-bit: 8 bytes)
    pub const PTR_SIZE: usize = size_of::<usize>();
    
    /// Vec/String header size (ptr + len + cap)
    pub const VEC_HEADER_SIZE: usize = 3 * PTR_SIZE;
    
    /// Default Vec capacity on first allocation
    pub const VEC_DEFAULT_CAPACITY: usize = 4;
}

/// Specialized array types with compile-time known sizes
pub mod fixed {
    /// Fixed-size array wrapper for stack allocation
    /// 
    /// **Performance**: Zero heap allocation, inlined operations
    /// **Use case**: When maximum size known at compile-time
    #[repr(transparent)]
    pub struct FixedArray<T, const N: usize>([T; N]);
    
    impl<T, const N: usize> FixedArray<T, N> {
        /// Create from array (zero-cost)
        #[inline(always)]
        pub const fn new(array: [T; N]) -> Self {
            Self(array)
        }
        
        /// Get slice view
        #[inline(always)]
        pub const fn as_slice(&self) -> &[T] {
            &self.0
        }
        
        /// Get mutable slice view
        #[inline(always)]
        pub fn as_mut_slice(&mut self) -> &mut [T] {
            &mut self.0
        }
        
        /// Compile-time size
        #[inline(always)]
        pub const fn len(&self) -> usize {
            N
        }
        
        /// Unwrap into inner array
        #[inline(always)]
        pub fn into_inner(self) -> [T; N] {
            self.0
        }
    }
    
    /// Small string optimization - stores up to 23 bytes inline
    /// 
    /// **Memory**: 24 bytes total (same as String header)
    /// **Benefit**: No heap allocation for short strings
    #[repr(C)]
    pub union SmallString {
        /// Inline storage for strings <= 23 bytes
        inline: core::mem::ManuallyDrop<InlineString>,
        /// Heap pointer for strings > 23 bytes
        heap: core::mem::ManuallyDrop<HeapString>,
    }
    
    #[repr(C)]
    #[derive(Copy, Clone)]
    struct InlineString {
        data: [u8; 23],
        len: u8, // MSB = 0 for inline
    }
    
    #[repr(C)]
    #[derive(Copy, Clone)]
    struct HeapString {
        ptr: *mut u8,
        cap: usize,
        len: usize, // MSB = 1 for heap
    }
}

/// Iterator utilities and extensions
pub mod iter {
    use super::*;
    
    /// Trait for converting into iterator with size hint
    pub trait IntoIteratorWithHint: IntoIterator {
        /// Get size hint before consuming
        fn size_hint_before(&self) -> (usize, Option<usize>);
    }
    
    impl<T> IntoIteratorWithHint for DynamicArray<T> {
        #[inline]
        fn size_hint_before(&self) -> (usize, Option<usize>) {
            let len = self.len();
            (len, Some(len))
        }
    }
}

/// Macro for convenient map initialization with capacity hint
/// 
/// **Optimization**: Pre-allocates exact capacity to avoid rehashing
/// 
/// # Examples
/// ```
/// # use avila_atom::map;
/// let m = map! {
///     "key1" => "value1",
///     "key2" => "value2",
/// };
/// assert_eq!(m.get("key1"), Some(&"value1"));
/// ```
#[macro_export]
macro_rules! map {
    ($($key:expr => $value:expr),* $(,)?) => {{
        // Count entries at compile-time
        const COUNT: usize = {
            let mut count = 0;
            $( let _ = $key; count += 1; )*
            count
        };
        
        let mut m = $crate::AssociativeArray::with_capacity(COUNT);
        $(
            m.insert($key, $value);
        )*
        m
    }};
}

/// Macro for convenient vector initialization
/// 
/// **Note**: Delegates to stdlib `vec![]` which uses optimized inline assembly
/// 
/// # Examples
/// ```
/// # use avila_atom::list;
/// let v = list![1, 2, 3, 4, 5];
/// assert_eq!(v.len(), 5);
/// ```
#[macro_export]
macro_rules! list {
    ($($item:expr),* $(,)?) => {{
        vec![$($item),*]
    }};
}

/// Macro for creating fixed-size arrays with type inference
/// 
/// **Performance**: Stack-allocated, zero heap operations
/// 
/// # Examples
/// ```
/// # use avila_atom::array;
/// let arr = array![1, 2, 3, 4];
/// assert_eq!(arr.len(), 4);
/// ```
#[macro_export]
macro_rules! array {
    ($($item:expr),* $(,)?) => {{
        $crate::fixed::FixedArray::new([$($item),*])
    }};
}

/// Macro for compile-time size assertions
/// 
/// **Purpose**: Verify structure sizes match expectations for ABI compatibility
/// 
/// # Examples
/// ```
/// # use avila_atom::static_assert_size;
/// static_assert_size!(Option<&str>, 16); // Two pointers on 64-bit
/// ```
#[macro_export]
macro_rules! static_assert_size {
    ($type:ty, $expected:expr) => {
        const _: [(); $expected] = [(); ::core::mem::size_of::<$type>()];
    };
}

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

    #[test]
    fn test_option() {
        let some: Option<i32> = Option::Some(42);
        let none: Option<i32> = Option::None;

        assert!(some.is_some());
        assert!(none.is_none());
    }

    #[test]
    fn test_result() {
        let ok: Result<i32, &str> = Result::Ok(42);
        let err: Result<i32, &str> = Result::Err("error");

        assert!(ok.is_ok());
        assert!(err.is_err());
    }

    #[test]
    fn test_dynamic_array() {
        let mut v: DynamicArray<i32> = DynamicArray::new();
        assert_eq!(v.capacity(), 0); // Zero allocation initially
        
        v.push(1);
        v.push(2);
        v.push(3);

        assert_eq!(v.len(), 3);
        assert!(v.capacity() >= 3); // Capacity grows as needed
    }

    #[test]
    fn test_dynamic_array_with_capacity() {
        let v: DynamicArray<i32> = DynamicArray::with_capacity(100);
        assert_eq!(v.capacity(), 100);
        assert_eq!(v.len(), 0);
    }

    #[test]
    #[cfg(feature = "std")]
    fn test_associative_array() {
        let m = map! {
            "key1" => "value1",
            "key2" => "value2",
        };

        assert_eq!(m.get("key1"), Some(&"value1"));
        assert_eq!(m.get("key2"), Some(&"value2"));
        assert_eq!(m.len(), 2);
    }

    #[test]
    fn test_string_buffer() {
        let s: StringBuffer = StringBuffer::from("Hello, Avila!");
        assert_eq!(s.len(), 13);
        assert!(s.is_ascii()); // Performance hint: ASCII-only allows SIMD
    }
    
    #[test]
    fn test_string_buffer_utf8() {
        let s: StringBuffer = StringBuffer::from("Ávila 🚀");
        assert_eq!(s.chars().count(), 7); // Character count
        assert_eq!(s.len(), 11); // Byte count (UTF-8 encoded)
    }
    
    #[test]
    fn test_fixed_array() {
        use crate::fixed::FixedArray;
        
        let arr = FixedArray::new([1, 2, 3, 4, 5]);
        assert_eq!(arr.len(), 5);
        assert_eq!(arr.as_slice()[0], 1);
    }
    
    #[test]
    fn test_option_size_optimization() {
        use core::mem::size_of;
        
        // Null pointer optimization: Option<&T> same size as *const T
        assert_eq!(size_of::<Option<&i32>>(), size_of::<&i32>());
        assert_eq!(size_of::<Option<Box<i32>>>(), size_of::<Box<i32>>());
    }
    
    #[test]
    fn test_result_error_handling() {
        fn divide(a: i32, b: i32) -> Result<i32, &'static str> {
            if b == 0 {
                Err("Division by zero")
            } else {
                Ok(a / b)
            }
        }
        
        assert_eq!(divide(10, 2), Ok(5));
        assert_eq!(divide(10, 0), Err("Division by zero"));
    }
    
    #[test]
    fn test_iterator_performance() {
        use crate::iter::IntoIteratorWithHint;
        
        let v = list![1, 2, 3, 4, 5];
        let (lower, upper) = v.size_hint_before();
        
        assert_eq!(lower, 5);
        assert_eq!(upper, Some(5));
    }
    
    #[test]
    #[cfg(feature = "std")]
    fn test_map_macro_capacity() {
        let m = map! {
            1 => "one",
            2 => "two",
            3 => "three",
        };
        
        // Map should be pre-allocated with exact capacity
        assert!(m.capacity() >= 3);
    }
}