llvm-native-core 0.1.16

//! LLVM SmallVector<T, N> — stack-allocated vector with heap spillover.
//!
//! Clean-room behavioral reconstruction.
//! @llvm_behavior: SmallVector stores up to N elements inline on the stack.
//! When capacity exceeds N, it spills to heap allocation. Growth factor
//! is typically 2x (like std::vector). Ideal for small, bounded collections
//! that occasionally need more space.

use std::fmt;
use std::mem::MaybeUninit;

/// A vector-like container with inline storage for N elements.
/// Elements beyond N are allocated on the heap.
///
/// @llvm_behavior: SmallVector<T, N> memory layout:
///   - First N elements stored inline (stack)
///   - Exceeding elements stored on heap
///   - begin()/end() gives contiguous view of all elements
pub struct SmallVector<T, const N: usize> {
    /// Inline storage for the first N elements
    inline: [MaybeUninit<T>; N],
    /// Heap storage for overflow elements
    heap: Vec<T>,
    /// Total number of elements (inline + heap)
    len: usize,
}

impl<T, const N: usize> SmallVector<T, N> {
    /// Create an empty SmallVector.
    pub fn new() -> Self {
        Self {
            inline: unsafe { MaybeUninit::uninit().assume_init() },
            heap: Vec::new(),
            len: 0,
        }
    }

    /// Create a SmallVector with a single element.
    pub fn from_elem(elem: T) -> Self {
        let mut sv = Self::new();
        sv.push(elem);
        sv
    }

    /// Number of elements.
    #[inline]
    pub fn size(&self) -> usize {
        self.len
    }

    /// Number of elements (LLVM style alias).
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    /// True if empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// True if element count <= N (completely inline).
    #[inline]
    pub fn is_inline(&self) -> bool {
        self.len <= N
    }

    /// Get element at index.
    #[inline]
    pub fn get(&self, index: usize) -> Option<&T> {
        if index >= self.len {
            return None;
        }
        if index < N {
            // Safety: index < len <= N means inline[index] is initialized
            Some(unsafe { self.inline[index].assume_init_ref() })
        } else {
            self.heap.get(index - N)
        }
    }

    /// Get mutable element at index.
    #[inline]
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index >= self.len {
            return None;
        }
        if index < N {
            Some(unsafe { self.inline[index].assume_init_mut() })
        } else {
            self.heap.get_mut(index - N)
        }
    }

    /// Reference to first element.
    #[inline]
    pub fn front(&self) -> Option<&T> {
        self.get(0)
    }

    /// Reference to last element.
    #[inline]
    pub fn back(&self) -> Option<&T> {
        if self.len == 0 {
            None
        } else {
            self.get(self.len - 1)
        }
    }

    /// Push an element to the end.
    /// @llvm_behavior: push_back preserves existing iterators unless reallocation.
    pub fn push(&mut self, elem: T) {
        if self.len < N {
            // Store inline
            self.inline[self.len] = MaybeUninit::new(elem);
            self.len += 1;
        } else {
            // Spill to heap
            self.heap.push(elem);
            self.len += 1;
        }
    }

    /// Remove the last element and return it.
    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }
        self.len -= 1;
        if self.len < N {
            // Take from inline
            let slot = std::mem::replace(&mut self.inline[self.len], MaybeUninit::uninit());
            Some(unsafe { slot.assume_init() })
        } else {
            self.heap.pop()
        }
    }

    /// Remove all elements.
    pub fn clear(&mut self) {
        // Drop inline elements
        for i in 0..(self.len.min(N)) {
            unsafe { self.inline[i].assume_init_drop() };
        }
        self.heap.clear();
        self.len = 0;
    }

    /// Reserve capacity for at least `additional` more elements.
    /// @llvm_behavior: reserve ensures capacity >= size() + additional.
    pub fn reserve(&mut self, additional: usize) {
        let needed = self.len + additional;
        if needed > N {
            let heap_needed = needed - N;
            self.heap.reserve(heap_needed);
        }
    }

    /// Iterator over elements.
    pub fn iter(&self) -> SmallVectorIter<'_, T, N> {
        SmallVectorIter { sv: self, idx: 0 }
    }

    /// Mutable iterator over elements.
    pub fn iter_mut(&mut self) -> SmallVectorIterMut<'_, T, N> {
        SmallVectorIterMut { sv: self, idx: 0 }
    }

    /// Access the elements as a contiguous slice.
    /// Note: this only works when the data is purely inline (len <= N)
    /// or purely on heap. For mixed storage, this returns None.
    pub fn as_slice(&self) -> Option<&[T]> {
        if self.len <= N {
            // All inline: create slice from inline storage
            let ptr = self.inline.as_ptr() as *const T;
            Some(unsafe { std::slice::from_raw_parts(ptr, self.len) })
        } else if self.len > N && N == 0 {
            // N=0: all data on heap
            Some(self.heap.as_slice())
        } else {
            // Mixed: inline + heap — not contiguous
            None
        }
    }
}

// === Iterator ===

pub struct SmallVectorIter<'a, T, const N: usize> {
    sv: &'a SmallVector<T, N>,
    idx: usize,
}

impl<'a, T, const N: usize> Iterator for SmallVectorIter<'a, T, N> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        let item = self.sv.get(self.idx);
        if item.is_some() {
            self.idx += 1;
        }
        item
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.sv.len() - self.idx;
        (remaining, Some(remaining))
    }
}

pub struct SmallVectorIterMut<'a, T, const N: usize> {
    sv: &'a mut SmallVector<T, N>,
    idx: usize,
}

impl<'a, T, const N: usize> Iterator for SmallVectorIterMut<'a, T, N> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.idx >= self.sv.len() {
            return None;
        }
        let idx = self.idx;
        self.idx += 1;
        // Safety: we borrow the SmallVector mutably, returning mutable refs to elements
        // This is safe because we never return overlapping references
        unsafe {
            let ptr: *mut SmallVector<T, N> = self.sv;
            Some((*ptr).get_mut(idx).unwrap())
        }
    }
}

// === Trait Implementations ===

impl<T: Clone, const N: usize> Clone for SmallVector<T, N> {
    fn clone(&self) -> Self {
        let mut out = Self::new();
        for elem in self.iter() {
            out.push(elem.clone());
        }
        out
    }
}

impl<T: fmt::Debug, const N: usize> fmt::Debug for SmallVector<T, N> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

impl<T: PartialEq, const N: usize> PartialEq for SmallVector<T, N> {
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            return false;
        }
        for i in 0..self.len() {
            if self.get(i) != other.get(i) {
                return false;
            }
        }
        true
    }
}

impl<T: Eq, const N: usize> Eq for SmallVector<T, N> {}

impl<T, const N: usize> Drop for SmallVector<T, N> {
    fn drop(&mut self) {
        // Drop inline elements
        for i in 0..(self.len.min(N)) {
            unsafe { self.inline[i].assume_init_drop() };
        }
    }
}

impl<T, const N: usize> std::ops::Index<usize> for SmallVector<T, N> {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        self.get(index).expect("SmallVector index out of bounds")
    }
}

impl<T, const N: usize> std::ops::IndexMut<usize> for SmallVector<T, N> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        self.get_mut(index)
            .expect("SmallVector index out of bounds")
    }
}

impl<T, const N: usize> Default for SmallVector<T, N> {
    fn default() -> Self {
        Self::new()
    }
}