llvm-native-core 0.1.16

//! IntervalMap — map of intervals for live range tracking and
//! register allocation.
//!
//! An IntervalMap maps non-overlapping intervals [start, end) to values.
//! Used for register allocation live ranges, liveness analysis, and
//! any situation where you need to map intervals to data.
//!
//! Clean-room behavioral reconstruction. No LLVM source is consulted.

use std::cmp::Ordering;
use std::fmt;

// ═══════════════════════════════════════════════════════════════════════════
// Interval
// ═══════════════════════════════════════════════════════════════════════════

/// A half-open interval [start, end).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Interval {
    pub start: u32,
    pub end: u32,
}

impl Interval {
    pub fn new(start: u32, end: u32) -> Self {
        assert!(start <= end, "invalid interval [{}, {})", start, end);
        Self { start, end }
    }

    /// Length of the interval.
    pub fn len(&self) -> u32 {
        self.end - self.start
    }

    /// Whether the interval is empty.
    pub fn is_empty(&self) -> bool {
        self.start == self.end
    }

    /// Whether this interval contains a point.
    pub fn contains(&self, point: u32) -> bool {
        point >= self.start && point < self.end
    }

    /// Whether this interval overlaps with another.
    pub fn overlaps(&self, other: &Interval) -> bool {
        self.start < other.end && other.start < self.end
    }

    /// Intersection of two intervals.
    pub fn intersect(&self, other: &Interval) -> Option<Interval> {
        let start = self.start.max(other.start);
        let end = self.end.min(other.end);
        if start < end {
            Some(Interval::new(start, end))
        } else {
            None
        }
    }

    /// Union of two overlapping intervals.
    pub fn union(&self, other: &Interval) -> Option<Interval> {
        if self.overlaps(other) || self.end == other.start || other.end == self.start {
            Some(Interval::new(
                self.start.min(other.start),
                self.end.max(other.end),
            ))
        } else {
            None
        }
    }
}

impl PartialOrd for Interval {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Interval {
    fn cmp(&self, other: &Self) -> Ordering {
        self.start
            .cmp(&other.start)
            .then_with(|| self.end.cmp(&other.end))
    }
}

impl fmt::Display for Interval {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "[{}, {})", self.start, self.end)
    }
}

// ═══════════════════════════════════════════════════════════════════════════
// IntervalMap
// ═══════════════════════════════════════════════════════════════════════════

/// A map from non-overlapping intervals to values.
///
/// Intervals are kept in sorted order by start point. Insertions
/// that overlap existing intervals will trigger coalescing or
/// overwriting depending on the mode.
#[derive(Debug, Clone)]
pub struct IntervalMap<V: Clone> {
    entries: Vec<(Interval, V)>,
}

impl<V: Clone> IntervalMap<V> {
    pub fn new() -> Self {
        Self {
            entries: Vec::new(),
        }
    }

    /// Number of intervals in the map.
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Whether the map is empty.
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    /// Insert a value for the given interval.
    /// Overlapping intervals are coalesced.
    pub fn insert(&mut self, interval: Interval, value: V) {
        if interval.is_empty() {
            return;
        }

        // Find insertion point
        let pos = self
            .entries
            .binary_search_by(|(iv, _)| iv.start.cmp(&interval.start))
            .unwrap_or_else(|e| e);

        // Check for overlap with previous entry
        if pos > 0 {
            let (prev_iv, _) = &self.entries[pos - 1];
            if prev_iv.overlaps(&interval) || prev_iv.end == interval.start {
                // Coalesce — extend previous
                self.entries[pos - 1].0.end = self.entries[pos - 1].0.end.max(interval.end);
                return;
            }
        }

        // Check for overlap with next entry
        if pos < self.entries.len() {
            let (next_iv, _) = &self.entries[pos];
            if next_iv.overlaps(&interval) || interval.end == next_iv.start {
                // Coalesce — extend next's start
                let new_start = interval.start.min(next_iv.start);
                let new_end = interval.end.max(next_iv.end);
                self.entries[pos] = (Interval::new(new_start, new_end), value);
                return;
            }
        }

        // No overlap — insert new entry
        self.entries.insert(pos, (interval, value));
    }

    /// Get the value at a specific point, if any interval contains it.
    pub fn get(&self, point: u32) -> Option<&V> {
        // Binary search for the interval containing point
        let pos = self
            .entries
            .binary_search_by(|(iv, _)| {
                if point < iv.start {
                    Ordering::Greater // search left
                } else if point >= iv.end {
                    Ordering::Less // search right
                } else {
                    Ordering::Equal
                }
            })
            .ok()?;
        Some(&self.entries[pos].1)
    }

    /// Get the interval and value at a specific point.
    pub fn get_interval(&self, point: u32) -> Option<(&Interval, &V)> {
        let pos = self
            .entries
            .binary_search_by(|(iv, _)| {
                if point < iv.start {
                    Ordering::Greater
                } else if point >= iv.end {
                    Ordering::Less
                } else {
                    Ordering::Equal
                }
            })
            .ok()?;
        Some((&self.entries[pos].0, &self.entries[pos].1))
    }

    /// Remove all intervals.
    pub fn clear(&mut self) {
        self.entries.clear();
    }

    /// Iterate over all (interval, value) pairs.
    pub fn iter(&self) -> impl Iterator<Item = &(Interval, V)> {
        self.entries.iter()
    }

    /// Get all intervals as a slice.
    pub fn intervals(&self) -> &[(Interval, V)] {
        &self.entries
    }

    /// Find intervals that overlap the given interval.
    pub fn find_overlapping(&self, query: &Interval) -> Vec<&(Interval, V)> {
        self.entries
            .iter()
            .filter(|(iv, _)| iv.overlaps(query))
            .collect()
    }

    /// Get the start of the first interval.
    pub fn begin_index(&self) -> Option<u32> {
        self.entries.first().map(|(iv, _)| iv.start)
    }

    /// Get the end of the last interval.
    pub fn end_index(&self) -> Option<u32> {
        self.entries.last().map(|(iv, _)| iv.end)
    }
}

impl<V: Clone> Default for IntervalMap<V> {
    fn default() -> Self {
        Self::new()
    }
}

impl<V: Clone + fmt::Display> fmt::Display for IntervalMap<V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{{")?;
        for (i, (iv, val)) in self.entries.iter().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{}:{}", iv, val)?;
        }
        write!(f, "}}")
    }
}

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

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

    #[test]
    fn test_interval_basic() {
        let iv = Interval::new(10, 20);
        assert_eq!(iv.len(), 10);
        assert!(iv.contains(15));
        assert!(!iv.contains(20));
        assert!(!iv.contains(9));
    }

    #[test]
    fn test_interval_overlaps() {
        let a = Interval::new(0, 10);
        let b = Interval::new(5, 15);
        let c = Interval::new(10, 20);
        assert!(a.overlaps(&b));
        assert!(!a.overlaps(&c));
    }

    #[test]
    fn test_interval_intersect() {
        let a = Interval::new(0, 10);
        let b = Interval::new(5, 15);
        let isect = a.intersect(&b).unwrap();
        assert_eq!(isect, Interval::new(5, 10));
    }

    #[test]
    fn test_interval_union() {
        let a = Interval::new(0, 10);
        let c = Interval::new(10, 20);
        let u = a.union(&c).unwrap();
        assert_eq!(u, Interval::new(0, 20));
    }

    #[test]
    fn test_interval_map_insert() {
        let mut map = IntervalMap::new();
        map.insert(Interval::new(0, 10), "A");
        map.insert(Interval::new(20, 30), "B");
        assert_eq!(map.len(), 2);
    }

    #[test]
    fn test_interval_map_coalesce() {
        let mut map = IntervalMap::new();
        map.insert(Interval::new(0, 10), "A");
        map.insert(Interval::new(5, 20), "A"); // Coalesces
        assert_eq!(map.len(), 1);
        let (iv, _) = &map.intervals()[0];
        assert_eq!(iv.start, 0);
        assert_eq!(iv.end, 20);
    }

    #[test]
    fn test_interval_map_get() {
        let mut map = IntervalMap::new();
        map.insert(Interval::new(10, 20), "hello");
        assert_eq!(map.get(15), Some(&"hello"));
        assert_eq!(map.get(5), None);
        assert_eq!(map.get(20), None);
    }

    #[test]
    fn test_interval_map_find_overlapping() {
        let mut map = IntervalMap::new();
        map.insert(Interval::new(0, 10), "A");
        map.insert(Interval::new(15, 25), "B");
        map.insert(Interval::new(30, 40), "C");

        let overlaps = map.find_overlapping(&Interval::new(5, 20));
        assert_eq!(overlaps.len(), 2); // A and B
    }

    #[test]
    fn test_interval_map_clear() {
        let mut map = IntervalMap::new();
        map.insert(Interval::new(0, 10), "X");
        map.clear();
        assert!(map.is_empty());
    }

    #[test]
    fn test_interval_map_begin_end() {
        let mut map = IntervalMap::new();
        map.insert(Interval::new(10, 20), "A");
        map.insert(Interval::new(30, 50), "B");
        assert_eq!(map.begin_index(), Some(10));
        assert_eq!(map.end_index(), Some(50));
    }
}