1use std::collections::BTreeMap;
7
8use crate::error::{DiagCode, Diagnostic};
9use crate::span::Span;
10use crate::value::Value;
11
12use super::extract_str;
13
14#[derive(Clone, Debug)]
15enum ClassAtom {
16 Single(char),
17 Range(char, char),
18 Digit,
19 Word,
20 Space,
21}
22
23impl ClassAtom {
24 fn matches(&self, c: char) -> bool {
25 match self {
26 ClassAtom::Single(target) => c == *target,
27 ClassAtom::Range(lo, hi) => c >= *lo && c <= *hi,
28 ClassAtom::Digit => c.is_ascii_digit(),
29 ClassAtom::Word => c.is_ascii_alphanumeric() || c == '_',
30 ClassAtom::Space => c.is_whitespace(),
31 }
32 }
33}
34
35#[derive(Clone, Debug)]
36enum CharMatcher {
37 Literal(char),
38 AnyNotNewline,
39 Digit(bool),
40 Word(bool),
41 Space(bool),
42 Class { negated: bool, atoms: Vec<ClassAtom> },
43}
44
45impl CharMatcher {
46 fn matches(&self, c: char) -> bool {
47 match self {
48 CharMatcher::Literal(target) => c == *target,
49 CharMatcher::AnyNotNewline => c != '\n',
50 CharMatcher::Digit(pos) => c.is_ascii_digit() == *pos,
51 CharMatcher::Word(pos) => (c.is_ascii_alphanumeric() || c == '_') == *pos,
52 CharMatcher::Space(pos) => c.is_whitespace() == *pos,
53 CharMatcher::Class { negated, atoms } => {
54 let hit = atoms.iter().any(|a| a.matches(c));
55 if *negated { !hit } else { hit }
56 }
57 }
58 }
59}
60
61#[derive(Clone, Debug)]
62enum RegexAst {
63 Empty,
64 Matcher(CharMatcher),
65 AnchorStart,
66 AnchorEnd,
67 Seq(Vec<RegexAst>),
68 Alt(Box<RegexAst>, Box<RegexAst>),
69 Repeat { inner: Box<RegexAst>, min_one: bool, max_one: bool },
70}
71
72#[derive(Clone, Debug)]
73enum NfaState {
74 Match(CharMatcher, usize),
75 Split(usize, usize),
76 AnchorStart(usize),
77 AnchorEnd(usize),
78 Accept,
79}
80
81#[derive(Clone, Debug)]
82struct CompiledNfa {
83 states: Vec<NfaState>,
84 start: usize,
85}
86
87pub(crate) fn call_linear_regex(
89 path: &str,
90 args: &[Value],
91 span: Span,
92) -> Result<Option<Value>, Diagnostic> {
93 match path {
94 "regex.compile" => {
95 let pattern = extract_str(args, 0, "regex.compile(pattern)", span)?;
96 let mut rec = BTreeMap::new();
97 rec.insert("pattern".to_string(), Value::String(pattern.clone()));
98 rec.insert("linear_time_guaranteed".to_string(), Value::Bool(true));
99 match compile_nfa(&pattern) {
100 Ok(nfa) => {
101 rec.insert("valid".to_string(), Value::Bool(true));
102 rec.insert("state_count".to_string(), Value::I64(nfa.states.len() as i64));
103 }
104 Err(err) => {
105 rec.insert("valid".to_string(), Value::Bool(false));
106 rec.insert("state_count".to_string(), Value::I64(0));
107 rec.insert("error".to_string(), Value::String(err));
108 }
109 }
110 Ok(Some(Value::Record(rec)))
111 }
112 "regex.is_match" => {
113 let pattern = extract_str(args, 0, "regex.is_match(pattern, text)", span)?;
114 let text = extract_str(args, 1, "regex.is_match(pattern, text)", span)?;
115 let nfa = compile_nfa(&pattern)
116 .map_err(|e| Diagnostic::new(DiagCode::E100, span, format!("regex.is_match: {e}")))?;
117 Ok(Some(Value::Bool(nfa_is_match(&nfa, &text))))
118 }
119 "regex.find" => {
120 let pattern = extract_str(args, 0, "regex.find(pattern, text)", span)?;
121 let text = extract_str(args, 1, "regex.find(pattern, text)", span)?;
122 let nfa = compile_nfa(&pattern)
123 .map_err(|e| Diagnostic::new(DiagCode::E100, span, format!("regex.find: {e}")))?;
124 let mut rec = BTreeMap::new();
125 if let Some((b_start, b_end)) = find_first_match(&nfa, &text) {
126 rec.insert("matched".to_string(), Value::Bool(true));
127 rec.insert("text".to_string(), Value::String(text[b_start..b_end].to_string()));
128 rec.insert("start".to_string(), Value::I64(b_start as i64));
129 rec.insert("end".to_string(), Value::I64(b_end as i64));
130 } else {
131 rec.insert("matched".to_string(), Value::Bool(false));
132 rec.insert("text".to_string(), Value::String(String::new()));
133 rec.insert("start".to_string(), Value::I64(-1));
134 rec.insert("end".to_string(), Value::I64(-1));
135 }
136 Ok(Some(Value::Record(rec)))
137 }
138 "regex.find_all" => {
139 let pattern = extract_str(args, 0, "regex.find_all(pattern, text)", span)?;
140 let text = extract_str(args, 1, "regex.find_all(pattern, text)", span)?;
141 let nfa = compile_nfa(&pattern)
142 .map_err(|e| Diagnostic::new(DiagCode::E100, span, format!("regex.find_all: {e}")))?;
143 let matches = find_all_matches(&nfa, &text)
144 .into_iter()
145 .map(|(b_start, b_end)| {
146 let mut m = BTreeMap::new();
147 m.insert("text".to_string(), Value::String(text[b_start..b_end].to_string()));
148 m.insert("start".to_string(), Value::I64(b_start as i64));
149 m.insert("end".to_string(), Value::I64(b_end as i64));
150 Value::Record(m)
151 })
152 .collect();
153 Ok(Some(Value::List(matches)))
154 }
155 "regex.replace_all" => {
156 let pattern = extract_str(args, 0, "regex.replace_all(pattern, text, replacement)", span)?;
157 let text = extract_str(args, 1, "regex.replace_all(pattern, text, replacement)", span)?;
158 let rep = extract_str(args, 2, "regex.replace_all(pattern, text, replacement)", span)?;
159 let nfa = compile_nfa(&pattern).map_err(|e| {
160 Diagnostic::new(DiagCode::E100, span, format!("regex.replace_all: {e}"))
161 })?;
162 let spans = find_all_matches(&nfa, &text);
163 if spans.is_empty() {
164 return Ok(Some(Value::String(text)));
165 }
166 let mut out = String::with_capacity(text.len());
167 let mut last = 0;
168 for (s, e) in spans {
169 out.push_str(&text[last..s]);
170 out.push_str(&rep);
171 last = e;
172 }
173 out.push_str(&text[last..]);
174 Ok(Some(Value::String(out)))
175 }
176 _ => Ok(None),
177 }
178}
179
180fn compile_nfa(pattern: &str) -> Result<CompiledNfa, String> {
181 let chars: Vec<char> = pattern.chars().collect();
182 let mut pos = 0;
183 let ast = parse_alt(&chars, &mut pos, false)?;
184 if pos < chars.len() {
185 return Err(format!("unexpected character '{}' at index {pos}", chars[pos]));
186 }
187 let mut states = vec![NfaState::Accept];
188 let start = build_nfa(&ast, 0, &mut states);
189 Ok(CompiledNfa { states, start })
190}
191
192fn parse_alt(chars: &[char], pos: &mut usize, in_group: bool) -> Result<RegexAst, String> {
193 let mut left = parse_seq(chars, pos, in_group)?;
194 while *pos < chars.len() && chars[*pos] == '|' {
195 *pos += 1;
196 let right = parse_seq(chars, pos, in_group)?;
197 left = RegexAst::Alt(Box::new(left), Box::new(right));
198 }
199 Ok(left)
200}
201
202fn parse_seq(chars: &[char], pos: &mut usize, in_group: bool) -> Result<RegexAst, String> {
203 let mut items = Vec::new();
204 while *pos < chars.len() {
205 let c = chars[*pos];
206 if c == '|' || (in_group && c == ')') {
207 break;
208 }
209 if c == ')' {
210 return Err(format!("unmatched ')' at index {}", *pos));
211 }
212 let mut atom = parse_atom(chars, pos)?;
213 while *pos < chars.len() {
214 let (min_one, max_one) = match chars[*pos] {
215 '*' => (false, false),
216 '+' => (true, false),
217 '?' => (false, true),
218 _ => break,
219 };
220 *pos += 1;
221 atom = RegexAst::Repeat { inner: Box::new(atom), min_one, max_one };
222 }
223 items.push(atom);
224 }
225 match items.len() {
226 0 => Ok(RegexAst::Empty),
227 1 => Ok(items.remove(0)),
228 _ => Ok(RegexAst::Seq(items)),
229 }
230}
231
232fn parse_atom(chars: &[char], pos: &mut usize) -> Result<RegexAst, String> {
233 let c = chars[*pos];
234 match c {
235 '*' | '+' | '?' => Err(format!("quantifier '{c}' nothing to repeat at index {}", *pos)),
236 '^' => { *pos += 1; Ok(RegexAst::AnchorStart) }
237 '$' => { *pos += 1; Ok(RegexAst::AnchorEnd) }
238 '.' => { *pos += 1; Ok(RegexAst::Matcher(CharMatcher::AnyNotNewline)) }
239 '(' => {
240 *pos += 1;
241 let inner = parse_alt(chars, pos, true)?;
242 if *pos >= chars.len() || chars[*pos] != ')' {
243 return Err("unclosed group '('".to_string());
244 }
245 *pos += 1;
246 Ok(inner)
247 }
248 '[' => parse_class(chars, pos),
249 '\\' => {
250 *pos += 1;
251 if *pos >= chars.len() {
252 return Err("trailing '\\' in regex pattern".to_string());
253 }
254 let esc = chars[*pos];
255 *pos += 1;
256 let matcher = match esc {
257 'd' => CharMatcher::Digit(true),
258 'D' => CharMatcher::Digit(false),
259 'w' => CharMatcher::Word(true),
260 'W' => CharMatcher::Word(false),
261 's' => CharMatcher::Space(true),
262 'S' => CharMatcher::Space(false),
263 'n' => CharMatcher::Literal('\n'),
264 'r' => CharMatcher::Literal('\r'),
265 't' => CharMatcher::Literal('\t'),
266 other => CharMatcher::Literal(other),
267 };
268 Ok(RegexAst::Matcher(matcher))
269 }
270 other => { *pos += 1; Ok(RegexAst::Matcher(CharMatcher::Literal(other))) }
271 }
272}
273
274fn parse_class(chars: &[char], pos: &mut usize) -> Result<RegexAst, String> {
275 *pos += 1;
276 let negated = if *pos < chars.len() && chars[*pos] == '^' { *pos += 1; true } else { false };
277 let mut atoms = Vec::new();
278 while *pos < chars.len() && chars[*pos] != ']' {
279 let ch = if chars[*pos] == '\\' {
280 *pos += 1;
281 if *pos >= chars.len() {
282 return Err("unclosed character class '['".to_string());
283 }
284 let esc = chars[*pos];
285 *pos += 1;
286 match esc {
287 'd' => { atoms.push(ClassAtom::Digit); continue; }
288 'w' => { atoms.push(ClassAtom::Word); continue; }
289 's' => { atoms.push(ClassAtom::Space); continue; }
290 'n' => '\n',
291 'r' => '\r',
292 't' => '\t',
293 other => other,
294 }
295 } else {
296 let c = chars[*pos];
297 *pos += 1;
298 c
299 };
300 if *pos + 1 < chars.len() && chars[*pos] == '-' && chars[*pos + 1] != ']' {
301 *pos += 1;
302 let hi = chars[*pos];
303 *pos += 1;
304 atoms.push(ClassAtom::Range(ch, hi));
305 } else {
306 atoms.push(ClassAtom::Single(ch));
307 }
308 }
309 if *pos >= chars.len() || chars[*pos] != ']' {
310 return Err("unclosed character class '['".to_string());
311 }
312 *pos += 1;
313 Ok(RegexAst::Matcher(CharMatcher::Class { negated, atoms }))
314}
315
316fn build_nfa(ast: &RegexAst, next: usize, states: &mut Vec<NfaState>) -> usize {
317 match ast {
318 RegexAst::Empty => next,
319 RegexAst::Matcher(m) => {
320 let id = states.len();
321 states.push(NfaState::Match(m.clone(), next));
322 id
323 }
324 RegexAst::AnchorStart => {
325 let id = states.len();
326 states.push(NfaState::AnchorStart(next));
327 id
328 }
329 RegexAst::AnchorEnd => {
330 let id = states.len();
331 states.push(NfaState::AnchorEnd(next));
332 id
333 }
334 RegexAst::Seq(items) => items.iter().rev().fold(next, |cur, item| build_nfa(item, cur, states)),
335 RegexAst::Alt(a, b) => {
336 let s_a = build_nfa(a, next, states);
337 let s_b = build_nfa(b, next, states);
338 let id = states.len();
339 states.push(NfaState::Split(s_a, s_b));
340 id
341 }
342 RegexAst::Repeat { inner, min_one: false, max_one: true } => {
343 let s_in = build_nfa(inner, next, states);
344 let id = states.len();
345 states.push(NfaState::Split(s_in, next));
346 id
347 }
348 RegexAst::Repeat { inner, min_one, max_one: false } => {
349 let split_id = states.len();
350 states.push(NfaState::Accept);
351 let s_in = build_nfa(inner, split_id, states);
352 states[split_id] = NfaState::Split(s_in, next);
353 if *min_one { s_in } else { split_id }
354 }
355 RegexAst::Repeat { inner, min_one: true, max_one: true } => build_nfa(inner, next, states),
356 }
357}
358
359fn add_epsilon_state(
360 nfa: &CompiledNfa,
361 state: usize,
362 pos: usize,
363 total_len: usize,
364 active: &mut Vec<usize>,
365 visited: &mut [bool],
366) {
367 if visited[state] {
368 return;
369 }
370 visited[state] = true;
371 match &nfa.states[state] {
372 NfaState::Split(a, b) => {
373 add_epsilon_state(nfa, *a, pos, total_len, active, visited);
374 add_epsilon_state(nfa, *b, pos, total_len, active, visited);
375 }
376 NfaState::AnchorStart(out) if pos == 0 => {
377 add_epsilon_state(nfa, *out, pos, total_len, active, visited);
378 }
379 NfaState::AnchorEnd(out) if pos == total_len => {
380 add_epsilon_state(nfa, *out, pos, total_len, active, visited);
381 }
382 NfaState::AnchorStart(_) | NfaState::AnchorEnd(_) => {}
383 _ => active.push(state),
384 }
385}
386
387fn nfa_is_match(nfa: &CompiledNfa, text: &str) -> bool {
388 let chars: Vec<(usize, char)> = text.char_indices().collect();
389 let total = chars.len();
390 let mut active = Vec::new();
391 let mut next_active = Vec::new();
392 let mut visited = vec![false; nfa.states.len()];
393
394 for i in 0..=total {
395 visited.fill(false);
396 for &s in &active {
397 add_epsilon_state(nfa, s, i, total, &mut next_active, &mut visited);
398 }
399 add_epsilon_state(nfa, nfa.start, i, total, &mut next_active, &mut visited);
400 std::mem::swap(&mut active, &mut next_active);
401 next_active.clear();
402
403 if active.iter().any(|&s| matches!(nfa.states[s], NfaState::Accept)) {
404 return true;
405 }
406 if i == total {
407 break;
408 }
409 let ch = chars[i].1;
410 for &s in &active {
411 if let NfaState::Match(ref m, out) = nfa.states[s] {
412 if m.matches(ch) {
413 next_active.push(out);
414 }
415 }
416 }
417 std::mem::swap(&mut active, &mut next_active);
418 next_active.clear();
419 }
420 false
421}
422
423fn find_first_match(nfa: &CompiledNfa, text: &str) -> Option<(usize, usize)> {
424 let chars: Vec<(usize, char)> = text.char_indices().collect();
425 for start_idx in 0..=chars.len() {
426 if let Some(end_idx) = match_from_index(nfa, &chars, start_idx) {
427 let b_start = chars.get(start_idx).map(|p| p.0).unwrap_or(text.len());
428 let b_end = chars.get(end_idx).map(|p| p.0).unwrap_or(text.len());
429 return Some((b_start, b_end));
430 }
431 }
432 None
433}
434
435fn find_all_matches(nfa: &CompiledNfa, text: &str) -> Vec<(usize, usize)> {
436 let chars: Vec<(usize, char)> = text.char_indices().collect();
437 let mut out = Vec::new();
438 let mut idx = 0;
439 while idx <= chars.len() {
440 if let Some(end_idx) = match_from_index(nfa, &chars, idx) {
441 let b_start = chars.get(idx).map(|p| p.0).unwrap_or(text.len());
442 let b_end = chars.get(end_idx).map(|p| p.0).unwrap_or(text.len());
443 out.push((b_start, b_end));
444 idx = if end_idx > idx { end_idx } else { idx + 1 };
445 } else {
446 idx += 1;
447 }
448 }
449 out
450}
451
452fn match_from_index(nfa: &CompiledNfa, chars: &[(usize, char)], start_idx: usize) -> Option<usize> {
453 let total = chars.len();
454 let mut active = Vec::new();
455 let mut next_active = Vec::new();
456 let mut visited = vec![false; nfa.states.len()];
457
458 add_epsilon_state(nfa, nfa.start, start_idx, total, &mut active, &mut visited);
459 let mut longest_end = active
460 .iter()
461 .any(|&s| matches!(nfa.states[s], NfaState::Accept))
462 .then_some(start_idx);
463
464 for i in start_idx..total {
465 if active.is_empty() {
466 break;
467 }
468 let ch = chars[i].1;
469 visited.fill(false);
470 for &s in &active {
471 if let NfaState::Match(ref m, out) = nfa.states[s] {
472 if m.matches(ch) {
473 add_epsilon_state(nfa, out, i + 1, total, &mut next_active, &mut visited);
474 }
475 }
476 }
477 std::mem::swap(&mut active, &mut next_active);
478 next_active.clear();
479 if active.iter().any(|&s| matches!(nfa.states[s], NfaState::Accept)) {
480 longest_end = Some(i + 1);
481 }
482 }
483 longest_end
484}