llvm-native-core 0.1.16

//! BitVector — compact bit vector for liveness analysis, register
//! allocation, and dataflow sets.
//!
//! Provides space-efficient bit storage with set operations (union,
//! intersection, difference) and iteration over set bits.
//!
//! Clean-room behavioral reconstruction. No LLVM source is consulted.

use std::fmt;
use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};

// ═══════════════════════════════════════════════════════════════════════════
// BitVector
// ═══════════════════════════════════════════════════════════════════════════

/// A compact, growable bit vector.
///
/// Stored as a vector of u64 words. Bits are indexed from 0.
#[derive(Debug, Clone)]
pub struct BitVector {
    /// The underlying word storage. Each u64 holds 64 bits.
    words: Vec<u64>,
    /// Number of bits in the vector (may be less than capacity * 64).
    size: usize,
}

impl BitVector {
    /// Create an empty bit vector.
    pub fn new() -> Self {
        Self {
            words: Vec::new(),
            size: 0,
        }
    }

    /// Create a bit vector with `n` bits, all set to `value`.
    pub fn with_capacity(n: usize, value: bool) -> Self {
        let num_words = (n + 63) / 64;
        let fill = if value { !0u64 } else { 0u64 };
        Self {
            words: vec![fill; num_words],
            size: n,
        }
    }

    /// Number of bits in the vector.
    pub fn size(&self) -> usize {
        self.size
    }

    /// Number of set bits (population count).
    pub fn count(&self) -> usize {
        self.words.iter().map(|w| w.count_ones() as usize).sum()
    }

    /// Test if any bit is set.
    pub fn any(&self) -> bool {
        self.words.iter().any(|&w| w != 0)
    }

    /// Test if no bits are set.
    pub fn none(&self) -> bool {
        self.words.iter().all(|&w| w == 0)
    }

    /// Test if all bits are set.
    pub fn all(&self) -> bool {
        if self.size == 0 {
            return true;
        }
        let full_words = self.size / 64;
        for i in 0..full_words {
            if self.words[i] != !0u64 {
                return false;
            }
        }
        let remaining = self.size % 64;
        if remaining > 0 {
            let mask = (1u64 << remaining) - 1;
            if self.words[full_words] != mask {
                return false;
            }
        }
        true
    }

    /// Get the value of a specific bit.
    pub fn get(&self, index: usize) -> bool {
        if index >= self.size {
            return false;
        }
        let word = index / 64;
        let bit = index % 64;
        if word >= self.words.len() {
            return false;
        }
        (self.words[word] >> bit) & 1 == 1
    }

    /// Set a specific bit to `value`.
    pub fn set(&mut self, index: usize, value: bool) {
        self.grow_to(index + 1);
        let word = index / 64;
        let bit = index % 64;
        if value {
            self.words[word] |= 1 << bit;
        } else {
            self.words[word] &= !(1 << bit);
        }
    }

    /// Set all bits to 0.
    pub fn reset(&mut self) {
        for word in &mut self.words {
            *word = 0;
        }
    }

    /// Set all bits to 1.
    pub fn set_all(&mut self) {
        for word in &mut self.words {
            *word = !0u64;
        }
        // Clear bits beyond size
        let remaining = self.size % 64;
        if remaining > 0 && !self.words.is_empty() {
            let mask = (1u64 << remaining) - 1;
            let last = self.words.len() - 1;
            self.words[last] &= mask;
        }
    }

    /// Flip all bits.
    pub fn flip(&mut self) {
        for word in &mut self.words {
            *word = !*word;
        }
        let remaining = self.size % 64;
        if remaining > 0 && !self.words.is_empty() {
            let mask = (1u64 << remaining) - 1;
            let last = self.words.len() - 1;
            self.words[last] &= mask;
        }
    }

    /// Find the first set bit, if any.
    pub fn find_first(&self) -> Option<usize> {
        for (i, &word) in self.words.iter().enumerate() {
            if word != 0 {
                return Some(i * 64 + word.trailing_zeros() as usize);
            }
        }
        None
    }

    /// Find the next set bit after `prev`.
    pub fn find_next(&self, prev: usize) -> Option<usize> {
        if prev + 1 >= self.size {
            return None;
        }
        let start_word = (prev + 1) / 64;
        let start_bit = (prev + 1) % 64;

        // Check the starting word from start_bit onward
        if start_word < self.words.len() {
            let word = self.words[start_word] >> start_bit;
            if word != 0 {
                return Some(start_word * 64 + start_bit + word.trailing_zeros() as usize);
            }
        }

        // Check subsequent words
        for i in (start_word + 1)..self.words.len() {
            if self.words[i] != 0 {
                return Some(i * 64 + self.words[i].trailing_zeros() as usize);
            }
        }
        None
    }

    /// Iterate over all set bit indices.
    pub fn iter_set_bits(&self) -> SetBitsIter {
        SetBitsIter {
            bv: self,
            current: self.find_first(),
        }
    }

    /// Resize to a new number of bits.
    pub fn resize(&mut self, new_size: usize) {
        let new_words = (new_size + 63) / 64;
        self.words.resize(new_words, 0);
        self.size = new_size;

        // Clear bits beyond new size
        let remaining = new_size % 64;
        if remaining > 0 && !self.words.is_empty() {
            let mask = (1u64 << remaining) - 1;
            let last = self.words.len() - 1;
            self.words[last] &= mask;
        }
    }

    /// Grow to at least `min_size` bits.
    fn grow_to(&mut self, min_size: usize) {
        if min_size > self.size {
            self.resize(min_size);
        }
    }

    fn apply_mask_last_word(&mut self) {
        let remaining = self.size % 64;
        if remaining > 0 && !self.words.is_empty() {
            let mask = (1u64 << remaining) - 1;
            let last = self.words.len() - 1;
            self.words[last] &= mask;
        }
    }
}

// ═══════════════════════════════════════════════════════════════════════════
// Set Operations
// ═══════════════════════════════════════════════════════════════════════════

impl BitOr for &BitVector {
    type Output = BitVector;

    fn bitor(self, rhs: Self) -> BitVector {
        let max_size = self.size.max(rhs.size);
        let mut result = BitVector::with_capacity(max_size, false);
        for i in 0..result.words.len() {
            let a = if i < self.words.len() {
                self.words[i]
            } else {
                0
            };
            let b = if i < rhs.words.len() { rhs.words[i] } else { 0 };
            result.words[i] = a | b;
        }
        result.apply_mask_last_word();
        result
    }
}

impl BitOrAssign for BitVector {
    fn bitor_assign(&mut self, rhs: Self) {
        self.grow_to(rhs.size);
        for i in 0..rhs.words.len() {
            self.words[i] |= rhs.words[i];
        }
        self.apply_mask_last_word();
    }
}

impl BitAnd for &BitVector {
    type Output = BitVector;

    fn bitand(self, rhs: Self) -> BitVector {
        let min_size = self.size.min(rhs.size);
        let mut result = BitVector::with_capacity(min_size, false);
        for i in 0..result.words.len() {
            result.words[i] = self.words[i] & rhs.words[i];
        }
        result.apply_mask_last_word();
        result
    }
}

impl BitAndAssign for BitVector {
    fn bitand_assign(&mut self, rhs: Self) {
        let min_words = self.words.len().min(rhs.words.len());
        for i in 0..min_words {
            self.words[i] &= rhs.words[i];
        }
    }
}

impl BitXor for &BitVector {
    type Output = BitVector;

    fn bitxor(self, rhs: Self) -> BitVector {
        let max_size = self.size.max(rhs.size);
        let mut result = BitVector::with_capacity(max_size, false);
        for i in 0..result.words.len() {
            let a = if i < self.words.len() {
                self.words[i]
            } else {
                0
            };
            let b = if i < rhs.words.len() { rhs.words[i] } else { 0 };
            result.words[i] = a ^ b;
        }
        result.apply_mask_last_word();
        result
    }
}

impl BitXorAssign for BitVector {
    fn bitxor_assign(&mut self, rhs: Self) {
        self.grow_to(rhs.size);
        for i in 0..rhs.words.len() {
            self.words[i] ^= rhs.words[i];
        }
        self.apply_mask_last_word();
    }
}

impl Not for &BitVector {
    type Output = BitVector;

    fn not(self) -> BitVector {
        let mut result = self.clone();
        result.flip();
        result
    }
}

impl PartialEq for BitVector {
    fn eq(&self, other: &Self) -> bool {
        let max_words = self.words.len().max(other.words.len());
        for i in 0..max_words {
            let a = if i < self.words.len() {
                self.words[i]
            } else {
                0
            };
            let b = if i < other.words.len() {
                other.words[i]
            } else {
                0
            };
            if a != b {
                return false;
            }
        }
        true
    }
}

impl Eq for BitVector {}

impl fmt::Display for BitVector {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "[")?;
        for i in self.iter_set_bits() {
            write!(f, "{}", i)?;
        }
        write!(f, "]")
    }
}

// ═══════════════════════════════════════════════════════════════════════════
// Iterator over set bits
// ═══════════════════════════════════════════════════════════════════════════

/// Iterator over set bits in a BitVector.
pub struct SetBitsIter<'a> {
    bv: &'a BitVector,
    current: Option<usize>,
}

impl<'a> Iterator for SetBitsIter<'a> {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        let result = self.current?;
        self.current = self.bv.find_next(result);
        Some(result)
    }
}

// ═══════════════════════════════════════════════════════════════════════════
// SmallBitVector — inline bit vector for small sizes (≤ 64 bits)
// ═══════════════════════════════════════════════════════════════════════════

/// A bit vector that stores up to 64 bits inline (no heap allocation).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SmallBitVector {
    bits: u64,
}

impl SmallBitVector {
    pub fn new() -> Self {
        Self { bits: 0 }
    }

    pub fn get(&self, index: usize) -> bool {
        if index >= 64 {
            return false;
        }
        (self.bits >> index) & 1 == 1
    }

    pub fn set(&mut self, index: usize, value: bool) {
        if index >= 64 {
            return;
        }
        if value {
            self.bits |= 1 << index;
        } else {
            self.bits &= !(1 << index);
        }
    }

    pub fn count(&self) -> usize {
        self.bits.count_ones() as usize
    }

    pub fn any(&self) -> bool {
        self.bits != 0
    }
    pub fn none(&self) -> bool {
        self.bits == 0
    }
    pub fn reset(&mut self) {
        self.bits = 0;
    }
}

// ═══════════════════════════════════════════════════════════════════════════
// Tests
// ═══════════════════════════════════════════════════════════════════════════

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

    #[test]
    fn test_bit_vector_basic() {
        let mut bv = BitVector::with_capacity(128, false);
        assert_eq!(bv.size(), 128);
        assert!(bv.none());
        bv.set(5, true);
        assert!(bv.get(5));
        assert_eq!(bv.count(), 1);
    }

    #[test]
    fn test_bit_vector_iter() {
        let mut bv = BitVector::with_capacity(64, false);
        bv.set(0, true);
        bv.set(10, true);
        bv.set(63, true);
        let bits: Vec<usize> = bv.iter_set_bits().collect();
        assert_eq!(bits, vec![0, 10, 63]);
    }

    #[test]
    fn test_bit_vector_or() {
        let mut a = BitVector::with_capacity(64, false);
        a.set(0, true);
        let mut b = BitVector::with_capacity(64, false);
        b.set(1, true);
        let c = &a | &b;
        assert!(c.get(0));
        assert!(c.get(1));
    }

    #[test]
    fn test_bit_vector_and() {
        let mut a = BitVector::with_capacity(64, false);
        a.set(0, true);
        a.set(1, true);
        let mut b = BitVector::with_capacity(64, false);
        b.set(0, true);
        let c = &a & &b;
        assert!(c.get(0));
        assert!(!c.get(1));
    }

    #[test]
    fn test_bit_vector_not() {
        let mut a = BitVector::with_capacity(8, false);
        a.set(0, true);
        let b = !&a;
        assert!(!b.get(0));
        assert!(b.get(1));
        assert!(b.get(7));
    }

    #[test]
    fn test_bit_vector_resize() {
        let mut bv = BitVector::with_capacity(32, false);
        bv.set(31, true);
        bv.resize(64);
        assert_eq!(bv.size(), 64);
        assert!(bv.get(31));
        bv.set(63, true);
        assert!(bv.get(63));
    }

    #[test]
    fn test_small_bit_vector() {
        let mut sbv = SmallBitVector::new();
        assert!(sbv.none());
        sbv.set(3, true);
        assert!(sbv.get(3));
        assert_eq!(sbv.count(), 1);
        sbv.reset();
        assert!(sbv.none());
    }

    #[test]
    fn test_bit_vector_find_first() {
        let mut bv = BitVector::with_capacity(128, false);
        assert_eq!(bv.find_first(), None);
        bv.set(42, true);
        assert_eq!(bv.find_first(), Some(42));
    }

    #[test]
    fn test_bit_vector_find_next() {
        let mut bv = BitVector::with_capacity(128, false);
        bv.set(10, true);
        bv.set(20, true);
        bv.set(30, true);
        assert_eq!(bv.find_first(), Some(10));
        assert_eq!(bv.find_next(10), Some(20));
        assert_eq!(bv.find_next(20), Some(30));
        assert_eq!(bv.find_next(30), None);
    }
}