regast-syntax 0.1.0

use std::sync::OnceLock;

use regex_syntax::{
    Parser,
    hir::{Class, HirKind},
};
use serde::{Deserialize, Serialize};

const MAX_SCALAR: u32 = 0x10_FFFF;
const SURROGATE_START: u32 = 0xD800;
const SURROGATE_END: u32 = 0xDFFF;

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct ClassRange {
    pub start: char,
    pub end: char,
}

#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct ClassSet {
    ranges: Vec<ClassRange>,
}

impl ClassSet {
    #[must_use]
    pub const fn empty() -> Self {
        Self { ranges: Vec::new() }
    }

    #[must_use]
    pub fn singleton(c: char) -> Self {
        Self::from_ranges([ClassRange { start: c, end: c }])
    }

    #[must_use]
    pub fn from_ranges(ranges: impl IntoIterator<Item = ClassRange>) -> Self {
        let mut raw: Vec<(u32, u32)> = ranges
            .into_iter()
            .map(|range| (range.start as u32, range.end as u32))
            .collect();
        raw.sort_unstable();

        let mut merged: Vec<(u32, u32)> = Vec::new();
        for (start, end) in raw {
            if let Some(last) = merged.last_mut() {
                if start <= last.1.saturating_add(1) {
                    last.1 = last.1.max(end);
                    continue;
                }
            }
            merged.push((start, end));
        }

        Self {
            ranges: merged
                .into_iter()
                .flat_map(split_surrogates)
                .filter_map(|(start, end)| {
                    Some(ClassRange {
                        start: char::from_u32(start)?,
                        end: char::from_u32(end)?,
                    })
                })
                .collect(),
        }
    }

    #[must_use]
    pub fn ranges(&self) -> &[ClassRange] {
        &self.ranges
    }

    #[must_use]
    pub fn contains(&self, c: char) -> bool {
        self.ranges
            .binary_search_by(|range| {
                if c < range.start {
                    std::cmp::Ordering::Greater
                } else if c > range.end {
                    std::cmp::Ordering::Less
                } else {
                    std::cmp::Ordering::Equal
                }
            })
            .is_ok()
    }

    #[must_use]
    pub fn union(&self, other: &Self) -> Self {
        Self::from_ranges(self.ranges.iter().chain(&other.ranges).copied())
    }

    #[must_use]
    pub fn intersect(&self, other: &Self) -> Self {
        let mut result = Vec::new();
        let (mut left, mut right) = (0, 0);
        while left < self.ranges.len() && right < other.ranges.len() {
            let a = self.ranges[left];
            let b = other.ranges[right];
            let start = a.start.max(b.start);
            let end = a.end.min(b.end);
            if start <= end {
                result.push(ClassRange { start, end });
            }
            if a.end < b.end {
                left += 1;
            } else {
                right += 1;
            }
        }
        Self::from_ranges(result)
    }

    #[must_use]
    pub fn negate(&self) -> Self {
        let mut result = Vec::new();
        let mut cursor = 0_u32;
        for range in &self.ranges {
            let start = range.start as u32;
            if cursor < start {
                result.extend(split_surrogates((cursor, start - 1)));
            }
            cursor = (range.end as u32).saturating_add(1);
        }
        if cursor <= MAX_SCALAR {
            result.extend(split_surrogates((cursor, MAX_SCALAR)));
        }
        Self::from_ranges(result.into_iter().filter_map(|(start, end)| {
            Some(ClassRange {
                start: char::from_u32(start)?,
                end: char::from_u32(end)?,
            })
        }))
    }

    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.ranges.is_empty()
    }

    #[must_use]
    pub fn all() -> Self {
        Self::empty().negate()
    }
}

fn split_surrogates((start, end): (u32, u32)) -> Vec<(u32, u32)> {
    if end < SURROGATE_START || start > SURROGATE_END {
        return vec![(start, end)];
    }
    let mut result = Vec::with_capacity(2);
    if start < SURROGATE_START {
        result.push((start, SURROGATE_START - 1));
    }
    if end > SURROGATE_END {
        result.push((SURROGATE_END + 1, end));
    }
    result
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum PerlClass {
    Digit,
    Word,
    Space,
}

impl PerlClass {
    #[must_use]
    pub fn set(self) -> ClassSet {
        static DIGIT: OnceLock<ClassSet> = OnceLock::new();
        static WORD: OnceLock<ClassSet> = OnceLock::new();
        static SPACE: OnceLock<ClassSet> = OnceLock::new();

        let (cell, source) = match self {
            Self::Digit => (&DIGIT, r"\d"),
            Self::Word => (&WORD, r"\w"),
            Self::Space => (&SPACE, r"\s"),
        };
        cell.get_or_init(|| unicode_perl_class(source)).clone()
    }
}

fn unicode_perl_class(source: &str) -> ClassSet {
    let hir = Parser::new()
        .parse(source)
        .expect("built-in Perl class syntax is valid");
    let HirKind::Class(Class::Unicode(class)) = hir.kind() else {
        unreachable!("built-in Perl class lowers to a Unicode class")
    };
    ClassSet::from_ranges(class.iter().map(|range| ClassRange {
        start: range.start(),
        end: range.end(),
    }))
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum ClassItem {
    Single { c: char, escaped: bool },
    Range { lo: char, hi: char },
    Perl { class: PerlClass, negated: bool },
}

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

    #[test]
    fn class_set_algebra() {
        let letters = ClassSet::from_ranges([ClassRange {
            start: 'a',
            end: 'z',
        }]);
        let middle = ClassSet::from_ranges([ClassRange {
            start: 'm',
            end: 'p',
        }]);
        assert_eq!(letters.intersect(&middle), middle);
        assert!(letters.union(&middle).contains('z'));
        assert!(!letters.negate().contains('a'));
        assert!(letters.negate().contains('A'));
    }

    #[test]
    fn perl_classes_use_unicode_semantics() {
        assert!(PerlClass::Word.set().contains('é'));
        assert!(PerlClass::Digit.set().contains('٣'));
        assert!(PerlClass::Space.set().contains('\u{2003}'));
    }
}