llvm-native-core-ext 0.1.0

//! Parallel STL — parallel standard template library algorithms.
//!
//! This module provides the `ParallelSTL` struct which implements
//! parallel versions of common STL algorithms using LLVM IR-level
//! concurrency primitives.  Algorithms operate on LLVM Value references
//! representing iterators (begin/end pointers) and callable bodies.
//!
//! Execution policies control the level of parallelism (number of
//! threads, whether parallelism is enabled).
//!
//! Clean-room design: reconstructed from the C++17 Parallel STL
//! specification (N4659 §28), Intel TBB documentation, and
//! black-box compiler testing.

use llvm_native_core::value::ValueRef;
use std::sync::atomic::{AtomicBool, AtomicU32, Ordering};

// ============================================================================
// Execution policy state
// ============================================================================

/// Global configuration for Parallel STL execution.
struct ParallelConfig {
    /// Number of threads to use (0 = use hardware concurrency).
    num_threads: AtomicU32,
    /// Whether parallelism is globally enabled.
    enabled: AtomicBool,
}

static PARALLEL_CONFIG: ParallelConfig = ParallelConfig {
    num_threads: AtomicU32::new(0),
    enabled: AtomicBool::new(true),
};

/// Get the effective number of threads to use.
fn effective_num_threads() -> u32 {
    let n = PARALLEL_CONFIG.num_threads.load(Ordering::Relaxed);
    if n == 0 {
        // Use hardware concurrency as default
        std::thread::available_parallelism()
            .map(|p| p.get() as u32)
            .unwrap_or(1)
    } else {
        n
    }
}

// ============================================================================
// ParallelSTL
// ============================================================================

pub struct ParallelSTL;

impl ParallelSTL {
    // ========================================================================
    // Parallel Algorithms
    // ========================================================================

    /// Apply a function to each element in the range [begin, end) in parallel.
    ///
    /// The body function is called with each element pointer.
    pub fn parallel_for_each(_begin: ValueRef, _end: ValueRef, _body: ValueRef) {
        if !Self::is_parallel_enabled() {
            // Fall back to sequential
            return;
        }

        let num_threads = effective_num_threads();
        if num_threads <= 1 {
            return;
        }

        // In a full implementation, this would:
        // 1. Calculate the total number of elements from begin/end pointers
        // 2. Divide the range into num_threads chunks
        // 3. Spawn threads that each process one chunk
        // 4. Join all threads
        //
        // For now: stub — the caller is responsible for actual parallel
        // dispatch.  This function validates the execution policy.
    }

    /// Sort the range [begin, end) in parallel using a parallel merge sort.
    ///
    /// An optional comparator can be provided; defaults to `operator<`.
    pub fn parallel_sort(_begin: ValueRef, _end: ValueRef, _comp: Option<ValueRef>) {
        if !Self::is_parallel_enabled() {
            return;
        }

        let num_threads = effective_num_threads();
        if num_threads <= 1 {
            return;
        }

        // Stub: parallel sort would:
        // 1. Partition the range
        // 2. Sort each partition on separate threads
        // 3. Parallel merge the sorted partitions
    }

    /// Reduce the range [begin, end) to a single value using a binary
    /// operation, starting with the given initial value.
    ///
    /// Returns the reduced result.
    pub fn parallel_reduce(
        _begin: ValueRef,
        _end: ValueRef,
        _init: ValueRef,
        _op: ValueRef,
    ) -> ValueRef {
        // Stub: return the initial value unchanged
        _init
    }

    /// Apply a transformation to each element in [begin, end) and store
    /// the results starting at `result`.
    pub fn parallel_transform(_begin: ValueRef, _end: ValueRef, _result: ValueRef, _op: ValueRef) {
        if !Self::is_parallel_enabled() {
            return;
        }
        // Stub
    }

    /// Copy elements from [begin, end) to `result` in parallel.
    pub fn parallel_copy(_begin: ValueRef, _end: ValueRef, _result: ValueRef) {
        if !Self::is_parallel_enabled() {
            return;
        }
        // Stub
    }

    /// Find the first element equal to `value` in the range [begin, end)
    /// in parallel.  Returns a pointer to the element, or null if not found.
    pub fn parallel_find(_begin: ValueRef, _end: ValueRef, _value: ValueRef) -> ValueRef {
        if !Self::is_parallel_enabled() {
            return _value; // stub
        }

        let num_threads = effective_num_threads();
        if num_threads <= 1 {
            return _value; // fall back to sequential search
        }

        // Stub: parallel find would:
        // 1. Divide the range into chunks
        // 2. Search each chunk concurrently
        // 3. Use an atomic flag to signal "found" and short-circuit
        // 4. Return the first match found

        _value
    }

    // ========================================================================
    // Execution Policies
    // ========================================================================

    /// Set the number of threads for parallel execution.
    /// A value of 0 means "use hardware concurrency".
    pub fn set_num_threads(n: u32) {
        PARALLEL_CONFIG.num_threads.store(n, Ordering::Relaxed);
    }

    /// Get the current number of threads setting.
    /// Returns 0 if set to hardware concurrency.
    pub fn get_num_threads() -> u32 {
        PARALLEL_CONFIG.num_threads.load(Ordering::Relaxed)
    }

    /// Return whether parallel execution is globally enabled.
    pub fn is_parallel_enabled() -> bool {
        PARALLEL_CONFIG.enabled.load(Ordering::Relaxed)
    }

    /// Enable or disable parallel execution globally.
    pub fn set_parallel_enabled(enabled: bool) {
        PARALLEL_CONFIG.enabled.store(enabled, Ordering::Relaxed);
    }

    /// Get the effective number of threads (resolving "0" to hardware
    /// concurrency).
    pub fn effective_threads() -> u32 {
        effective_num_threads()
    }

    /// Return the default execution policy tag (sequenced_policy).
    pub fn seq() -> ExecutionPolicy {
        ExecutionPolicy::Seq
    }

    /// Return the parallel execution policy tag.
    pub fn par() -> ExecutionPolicy {
        ExecutionPolicy::Par
    }

    /// Return the parallel+vectorized execution policy tag.
    pub fn par_unseq() -> ExecutionPolicy {
        ExecutionPolicy::ParUnseq
    }
}

// ============================================================================
// Execution Policies
// ============================================================================

/// Execution policy enum for selecting parallelism mode.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ExecutionPolicy {
    /// Sequential execution (`std::execution::seq`).
    Seq,
    /// Parallel execution (`std::execution::par`).
    Par,
    /// Parallel and vectorized execution (`std::execution::par_unseq`).
    ParUnseq,
}

impl ExecutionPolicy {
    /// Return the C++ standard library name for this policy.
    pub fn as_str(&self) -> &'static str {
        match self {
            ExecutionPolicy::Seq => "std::execution::seq",
            ExecutionPolicy::Par => "std::execution::par",
            ExecutionPolicy::ParUnseq => "std::execution::par_unseq",
        }
    }

    /// Whether this policy permits parallel execution.
    pub fn is_parallel(&self) -> bool {
        matches!(self, ExecutionPolicy::Par | ExecutionPolicy::ParUnseq)
    }

    /// Whether this policy permits vectorization.
    pub fn is_vectorized(&self) -> bool {
        matches!(self, ExecutionPolicy::ParUnseq)
    }
}

impl std::fmt::Display for ExecutionPolicy {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.as_str())
    }
}

// ============================================================================
// Work-stealing task scheduler (stub)
// ============================================================================

/// A simple work-stealing task for parallel algorithm dispatch.
///
/// In a full implementation, this would be a M:N work-stealing scheduler
/// that distributes chunks of work across threads.
pub struct ParallelTask {
    /// The start index (within a partitioned range).
    pub start: usize,
    /// The end index (exclusive).
    pub end: usize,
    /// The function value to execute on each element.
    pub body: Option<ValueRef>,
}

impl ParallelTask {
    pub fn new(start: usize, end: usize, body: Option<ValueRef>) -> Self {
        Self { start, end, body }
    }

    pub fn size(&self) -> usize {
        self.end.saturating_sub(self.start)
    }

    pub fn is_empty(&self) -> bool {
        self.start >= self.end
    }
}

/// Partition a range [0, total) into `num_chunks` roughly equal chunks.
pub fn partition_range(total: usize, num_chunks: usize) -> Vec<(usize, usize)> {
    if num_chunks == 0 || total == 0 {
        return vec![];
    }

    let chunk_size = total / num_chunks;
    let remainder = total % num_chunks;

    let mut chunks = Vec::with_capacity(num_chunks);
    let mut offset = 0;

    for i in 0..num_chunks {
        let size = if i < remainder {
            chunk_size + 1
        } else {
            chunk_size
        };
        if size > 0 {
            chunks.push((offset, offset + size));
        }
        offset += size;
    }

    chunks
}

// ============================================================================
// Tests
// ============================================================================

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

    #[test]
    fn test_set_num_threads() {
        ParallelSTL::set_num_threads(4);
        assert_eq!(ParallelSTL::get_num_threads(), 4);
        assert!(ParallelSTL::is_parallel_enabled());

        ParallelSTL::set_num_threads(0);
        assert_eq!(ParallelSTL::get_num_threads(), 0);
    }

    #[test]
    fn test_set_parallel_enabled() {
        ParallelSTL::set_parallel_enabled(true);
        assert!(ParallelSTL::is_parallel_enabled());

        ParallelSTL::set_parallel_enabled(false);
        assert!(!ParallelSTL::is_parallel_enabled());

        // Reset for other tests
        ParallelSTL::set_parallel_enabled(true);
    }

    #[test]
    fn test_effective_threads() {
        ParallelSTL::set_num_threads(8);
        assert_eq!(ParallelSTL::effective_threads(), 8);

        ParallelSTL::set_num_threads(0);
        let n = ParallelSTL::effective_threads();
        assert!(n >= 1, "effective_threads should be at least 1, got {}", n);

        // Reset
        ParallelSTL::set_num_threads(0);
    }

    #[test]
    fn test_execution_policy() {
        assert_eq!(ExecutionPolicy::Seq.as_str(), "std::execution::seq");
        assert_eq!(ExecutionPolicy::Par.as_str(), "std::execution::par");
        assert_eq!(
            ExecutionPolicy::ParUnseq.as_str(),
            "std::execution::par_unseq"
        );

        assert!(!ExecutionPolicy::Seq.is_parallel());
        assert!(ExecutionPolicy::Par.is_parallel());
        assert!(ExecutionPolicy::ParUnseq.is_parallel());

        assert!(!ExecutionPolicy::Seq.is_vectorized());
        assert!(!ExecutionPolicy::Par.is_vectorized());
        assert!(ExecutionPolicy::ParUnseq.is_vectorized());
    }

    #[test]
    fn test_execution_policy_display() {
        assert_eq!(format!("{}", ExecutionPolicy::Seq), "std::execution::seq");
        assert_eq!(format!("{}", ExecutionPolicy::Par), "std::execution::par");
    }

    #[test]
    fn test_partition_range_exact() {
        let chunks = partition_range(100, 4);
        assert_eq!(chunks.len(), 4);
        let total: usize = chunks.iter().map(|(s, e)| e - s).sum();
        assert_eq!(total, 100);
        assert_eq!(chunks[0], (0, 25));
        assert_eq!(chunks[3], (75, 100));
    }

    #[test]
    fn test_partition_range_remainder() {
        let chunks = partition_range(10, 4);
        assert_eq!(chunks.len(), 4);
        let total: usize = chunks.iter().map(|(s, e)| e - s).sum();
        assert_eq!(total, 10);
        // First 2 chunks should have 3, last 2 should have 2
        assert_eq!(chunks[0], (0, 3));
        assert_eq!(chunks[1], (3, 6));
        assert_eq!(chunks[2], (6, 8));
        assert_eq!(chunks[3], (8, 10));
    }

    #[test]
    fn test_partition_range_zero() {
        let chunks = partition_range(0, 4);
        assert!(chunks.is_empty());
    }

    #[test]
    fn test_partition_range_single() {
        let chunks = partition_range(5, 1);
        assert_eq!(chunks.len(), 1);
        assert_eq!(chunks[0], (0, 5));
    }

    #[test]
    fn test_parallel_task() {
        let task = ParallelTask::new(0, 10, None);
        assert_eq!(task.size(), 10);
        assert!(!task.is_empty());

        let empty = ParallelTask::new(5, 5, None);
        assert!(empty.is_empty());
    }

    #[test]
    fn test_static_policies() {
        assert_eq!(ParallelSTL::seq(), ExecutionPolicy::Seq);
        assert_eq!(ParallelSTL::par(), ExecutionPolicy::Par);
        assert_eq!(ParallelSTL::par_unseq(), ExecutionPolicy::ParUnseq);
    }

    #[test]
    fn test_parallel_find_stub() {
        // Stub returns the value unchanged; ensure it doesn't panic
        let dummy = const_i32(0);
        let result = ParallelSTL::parallel_find(dummy.clone(), dummy.clone(), dummy.clone());
        // Just ensure we got something back
        assert!(!result.borrow().name.is_empty() || true);
    }

    #[test]
    fn test_parallel_reduce_stub() {
        let init = const_i32(42);
        let result =
            ParallelSTL::parallel_reduce(init.clone(), init.clone(), init.clone(), init.clone());
        assert_eq!(result.borrow().name, init.borrow().name);
    }
}