1use std::sync::OnceLock;
2
3use regex_syntax::{
4 Parser,
5 hir::{Class, HirKind},
6};
7use serde::{Deserialize, Serialize};
8
9const MAX_SCALAR: u32 = 0x10_FFFF;
10const SURROGATE_START: u32 = 0xD800;
11const SURROGATE_END: u32 = 0xDFFF;
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
14pub struct ClassRange {
15 pub start: char,
16 pub end: char,
17}
18
19#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
20pub struct ClassSet {
21 ranges: Vec<ClassRange>,
22}
23
24impl ClassSet {
25 #[must_use]
26 pub const fn empty() -> Self {
27 Self { ranges: Vec::new() }
28 }
29
30 #[must_use]
31 pub fn singleton(c: char) -> Self {
32 Self::from_ranges([ClassRange { start: c, end: c }])
33 }
34
35 #[must_use]
36 pub fn from_ranges(ranges: impl IntoIterator<Item = ClassRange>) -> Self {
37 let mut raw: Vec<(u32, u32)> = ranges
38 .into_iter()
39 .map(|range| (range.start as u32, range.end as u32))
40 .collect();
41 raw.sort_unstable();
42
43 let mut merged: Vec<(u32, u32)> = Vec::new();
44 for (start, end) in raw {
45 if let Some(last) = merged.last_mut() {
46 if start <= last.1.saturating_add(1) {
47 last.1 = last.1.max(end);
48 continue;
49 }
50 }
51 merged.push((start, end));
52 }
53
54 Self {
55 ranges: merged
56 .into_iter()
57 .flat_map(split_surrogates)
58 .filter_map(|(start, end)| {
59 Some(ClassRange {
60 start: char::from_u32(start)?,
61 end: char::from_u32(end)?,
62 })
63 })
64 .collect(),
65 }
66 }
67
68 #[must_use]
69 pub fn ranges(&self) -> &[ClassRange] {
70 &self.ranges
71 }
72
73 #[must_use]
74 pub fn contains(&self, c: char) -> bool {
75 self.ranges
76 .binary_search_by(|range| {
77 if c < range.start {
78 std::cmp::Ordering::Greater
79 } else if c > range.end {
80 std::cmp::Ordering::Less
81 } else {
82 std::cmp::Ordering::Equal
83 }
84 })
85 .is_ok()
86 }
87
88 #[must_use]
89 pub fn union(&self, other: &Self) -> Self {
90 Self::from_ranges(self.ranges.iter().chain(&other.ranges).copied())
91 }
92
93 #[must_use]
94 pub fn intersect(&self, other: &Self) -> Self {
95 let mut result = Vec::new();
96 let (mut left, mut right) = (0, 0);
97 while left < self.ranges.len() && right < other.ranges.len() {
98 let a = self.ranges[left];
99 let b = other.ranges[right];
100 let start = a.start.max(b.start);
101 let end = a.end.min(b.end);
102 if start <= end {
103 result.push(ClassRange { start, end });
104 }
105 if a.end < b.end {
106 left += 1;
107 } else {
108 right += 1;
109 }
110 }
111 Self::from_ranges(result)
112 }
113
114 #[must_use]
115 pub fn negate(&self) -> Self {
116 let mut result = Vec::new();
117 let mut cursor = 0_u32;
118 for range in &self.ranges {
119 let start = range.start as u32;
120 if cursor < start {
121 result.extend(split_surrogates((cursor, start - 1)));
122 }
123 cursor = (range.end as u32).saturating_add(1);
124 }
125 if cursor <= MAX_SCALAR {
126 result.extend(split_surrogates((cursor, MAX_SCALAR)));
127 }
128 Self::from_ranges(result.into_iter().filter_map(|(start, end)| {
129 Some(ClassRange {
130 start: char::from_u32(start)?,
131 end: char::from_u32(end)?,
132 })
133 }))
134 }
135
136 #[must_use]
137 pub fn is_empty(&self) -> bool {
138 self.ranges.is_empty()
139 }
140
141 #[must_use]
142 pub fn all() -> Self {
143 Self::empty().negate()
144 }
145}
146
147fn split_surrogates((start, end): (u32, u32)) -> Vec<(u32, u32)> {
148 if end < SURROGATE_START || start > SURROGATE_END {
149 return vec![(start, end)];
150 }
151 let mut result = Vec::with_capacity(2);
152 if start < SURROGATE_START {
153 result.push((start, SURROGATE_START - 1));
154 }
155 if end > SURROGATE_END {
156 result.push((SURROGATE_END + 1, end));
157 }
158 result
159}
160
161#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
162#[serde(rename_all = "snake_case")]
163pub enum PerlClass {
164 Digit,
165 Word,
166 Space,
167}
168
169impl PerlClass {
170 #[must_use]
171 pub fn set(self) -> ClassSet {
172 static DIGIT: OnceLock<ClassSet> = OnceLock::new();
173 static WORD: OnceLock<ClassSet> = OnceLock::new();
174 static SPACE: OnceLock<ClassSet> = OnceLock::new();
175
176 let (cell, source) = match self {
177 Self::Digit => (&DIGIT, r"\d"),
178 Self::Word => (&WORD, r"\w"),
179 Self::Space => (&SPACE, r"\s"),
180 };
181 cell.get_or_init(|| unicode_perl_class(source)).clone()
182 }
183}
184
185fn unicode_perl_class(source: &str) -> ClassSet {
186 let hir = Parser::new()
187 .parse(source)
188 .expect("built-in Perl class syntax is valid");
189 let HirKind::Class(Class::Unicode(class)) = hir.kind() else {
190 unreachable!("built-in Perl class lowers to a Unicode class")
191 };
192 ClassSet::from_ranges(class.iter().map(|range| ClassRange {
193 start: range.start(),
194 end: range.end(),
195 }))
196}
197
198#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
199#[serde(tag = "kind", rename_all = "snake_case")]
200pub enum ClassItem {
201 Single { c: char, escaped: bool },
202 Range { lo: char, hi: char },
203 Perl { class: PerlClass, negated: bool },
204}
205
206#[cfg(test)]
207mod tests {
208 use super::*;
209
210 #[test]
211 fn class_set_algebra() {
212 let letters = ClassSet::from_ranges([ClassRange {
213 start: 'a',
214 end: 'z',
215 }]);
216 let middle = ClassSet::from_ranges([ClassRange {
217 start: 'm',
218 end: 'p',
219 }]);
220 assert_eq!(letters.intersect(&middle), middle);
221 assert!(letters.union(&middle).contains('z'));
222 assert!(!letters.negate().contains('a'));
223 assert!(letters.negate().contains('A'));
224 }
225
226 #[test]
227 fn perl_classes_use_unicode_semantics() {
228 assert!(PerlClass::Word.set().contains('é'));
229 assert!(PerlClass::Digit.set().contains('٣'));
230 assert!(PerlClass::Space.set().contains('\u{2003}'));
231 }
232}