c/
regex.rs

1// Copyright (c) 2026 Meng Zhuo
2// SPDX-License-Identifier: BSD-3-Clause
3
4// Minimal POSIX regex engine (bytecode VM).
5// Supports BRE and ERE: literals, bracket expressions, groups, *, +, ?, |.
6// REG_ICASE, REG_EXTENDED, REG_NOSUB, REG_NOTBOL, REG_NOTEOL.
7// Unknown backslash sequences are treated as literal next char.
8// Bytes >= 0x80 outside brackets return REG_BADPAT.
9
10const REG_EXTENDED: c_int = 1;
11const REG_ICASE: c_int = 2;
12const REG_NOSUB: c_int = 8;
13const REG_NOTBOL: c_int = 1;
14const REG_NOTEOL: c_int = 2;
15
16const REG_OK: c_int = 0;
17const REG_NOMATCH: c_int = 1;
18const REG_BADPAT: c_int = 2;
19const REG_ESPACE: c_int = 12;
20
21const OP_CHAR: u8 = 1;
22const OP_BRACKET: u8 = 2;
23const OP_MATCH: u8 = 3;
24const OP_JUMP: u8 = 4;
25const OP_SPLIT: u8 = 5;
26const OP_BOL: u8 = 6;
27const OP_EOL: u8 = 7;
28
29// regex_t layout: re_nsub(8) + __opaque(8) + __padding[4](32) + __nsub2(8) + __padding2(1) = 57 bytes
30// __opaque is at offset 8
31
32#[derive(Copy, Clone)]
33struct BracketRange {
34    min: u8,
35    max: u8,
36}
37
38struct BracketData {
39    negated: bool,
40    icase: bool,
41    nranges: usize,
42    ranges: *mut BracketRange,
43    ranges_cap: usize,
44}
45
46struct CompiledRegex {
47    ncode: usize,
48    code: *mut u8,
49    code_cap: usize,
50    icase: bool,
51    extended: bool,
52    n_brackets: usize,
53    brackets: *mut BracketData,
54    brackets_cap: usize,
55}
56
57struct RegexCContext {
58    code: *mut CompiledRegex,
59    pos: usize,
60    last_atom_start: usize,
61    err: c_int,
62    extended: bool,
63    icase: bool,
64}
65
66#[derive(Copy, Clone)]
67struct MatchFrame {
68    pc: usize,
69    sp: usize,
70    at_bol: bool,
71}
72
73#[inline]
74fn is_ascii_letter(b: u8) -> bool {
75    (b >= b'a' && b <= b'z') || (b >= b'A' && b <= b'Z')
76}
77
78fn bracket_contains(br: &BracketData, b: u8) -> bool {
79    let c = if br.icase { case_fold_byte(b) } else { b };
80    for i in 0..br.nranges {
81        let r = unsafe { &*br.ranges.add(i) };
82        if c >= r.min && c <= r.max {
83            return !br.negated;
84        }
85    }
86    br.negated
87}
88
89fn grow_code(ctx: &mut RegexCContext, need: usize) -> bool {
90    let code = unsafe { &mut *ctx.code };
91    if need <= code.code_cap {
92        return true;
93    }
94    let mut cap = if code.code_cap == 0 { 128 } else { code.code_cap };
95    while cap < need {
96        cap *= 2;
97    }
98    let p = unsafe { crate::realloc(code.code as *mut c_void, cap) } as *mut u8;
99    if p.is_null() {
100        ctx.err = REG_ESPACE;
101        return false;
102    }
103    code.code = p;
104    code.code_cap = cap;
105    true
106}
107
108fn emit(ctx: &mut RegexCContext, byte: u8) -> bool {
109    if !grow_code(ctx, ctx.pos + 1) {
110        return false;
111    }
112    unsafe { *(*ctx.code).code.add(ctx.pos) = byte; }
113    ctx.pos += 1;
114    true
115}
116
117fn emit32(ctx: &mut RegexCContext, val: u32) -> bool {
118    emit(ctx, (val & 0xff) as u8)
119        && emit(ctx, ((val >> 8) & 0xff) as u8)
120        && emit(ctx, ((val >> 16) & 0xff) as u8)
121        && emit(ctx, ((val >> 24) & 0xff) as u8)
122}
123
124unsafe fn patch32(code: *mut u8, at: usize, val: u32) {
125    *code.add(at) = (val & 0xff) as u8;
126    *code.add(at + 1) = ((val >> 8) & 0xff) as u8;
127    *code.add(at + 2) = ((val >> 16) & 0xff) as u8;
128    *code.add(at + 3) = ((val >> 24) & 0xff) as u8;
129}
130
131fn emit_char(ctx: &mut RegexCContext, b: u8) -> bool {
132    emit(ctx, OP_CHAR) && emit(ctx, b)
133}
134
135fn case_fold_byte(b: u8) -> u8 {
136    if b >= b'a' && b <= b'z' { b - 32 }
137    else if b >= b'A' && b <= b'Z' { b + 32 }
138    else { b }
139}
140
141
142
143fn compile_expr(
144    ctx: &mut RegexCContext,
145    pat: *const c_char,
146    plen: usize,
147    start: usize,
148    end: usize,
149    in_group: bool,
150) -> bool {
151    let mut i = start;
152    let mut alt_start = start;
153    let extended = ctx.extended;
154
155    while i < end {
156        let b = unsafe { *pat.add(i) as u8 };
157
158        if b == b'|' && extended {
159            if !compile_sequence(ctx, pat, plen, alt_start, i) { return false; }
160            let jump_pos = ctx.pos;
161            if !emit(ctx, OP_JUMP) || !emit32(ctx, 0) { return false; }
162            let cur = ctx.pos;
163            unsafe { patch32((*ctx.code).code, jump_pos + 1, cur as u32); }
164            alt_start = i + 1;
165            i += 1;
166            continue;
167        }
168
169        if b == b')' && extended && in_group {
170            if !compile_sequence(ctx, pat, plen, alt_start, i) { return false; }
171            return true;
172        }
173
174        i += 1;
175    }
176
177    compile_sequence(ctx, pat, plen, alt_start, end)
178}
179
180fn compile_sequence(
181    ctx: &mut RegexCContext,
182    pat: *const c_char,
183    plen: usize,
184    start: usize,
185    end: usize,
186) -> bool {
187    let mut i = start;
188    let extended = ctx.extended;
189
190    while i < end {
191        let b = unsafe { *pat.add(i) as u8 };
192
193        if b == b'|' && extended { return true; }
194        if b == b')' && in_group_check(start, end, extended) { return true; }
195
196        if b == b'\\' && i + 1 < end {
197            let next = unsafe { *pat.add(i + 1) as u8 };
198            if next >= 0x80 { return false; }
199            if !extended && next == b'(' {
200                i = i.wrapping_add(2);
201                if !compile_group(ctx, pat, plen, &mut i, end) { return false; }
202                continue;
203            }
204            if !extended && next == b')' { return true; }
205            let atom = ctx.pos;
206            if !emit_char(ctx, next) { return false; }
207            ctx.last_atom_start = atom;
208            i = i.wrapping_add(2);
209            continue;
210        }
211
212        if b == b'(' && extended {
213            i += 1;
214            if !compile_group(ctx, pat, plen, &mut i, end) { return false; }
215            continue;
216        }
217
218        if b == b'[' {
219            let atom = ctx.pos;
220            if !compile_bracket(ctx, pat, plen, &mut i, end) { return false; }
221            ctx.last_atom_start = atom;
222            continue;
223        }
224
225        if b == b'^' && i == start {
226            let atom = ctx.pos;
227            if !emit(ctx, OP_BOL) { return false; }
228            ctx.last_atom_start = atom;
229            i += 1;
230            continue;
231        }
232        if b == b'$' && i + 1 == end {
233            let atom = ctx.pos;
234            if !emit(ctx, OP_EOL) { return false; }
235            ctx.last_atom_start = atom;
236            i += 1;
237            continue;
238        }
239
240        if (b == b'*' || b == b'+' || b == b'?') && ctx.last_atom_start < ctx.pos {
241            let prev_start = ctx.last_atom_start;
242            let prev_end = ctx.pos;
243            let op = unsafe { *(*ctx.code).code.add(prev_start) };
244            if op == OP_CHAR || op == OP_BRACKET || op == OP_BOL || op == OP_EOL {
245                let prev_len = prev_end - prev_start;
246                let mut prev = [0u8; 32];
247                for k in 0..prev_len {
248                    prev[k] = unsafe { *(*ctx.code).code.add(prev_start + k) };
249                }
250                ctx.pos = prev_start;
251
252                if b == b'*' {
253                    let sp = ctx.pos;
254                    if !emit(ctx, OP_SPLIT) || !emit32(ctx, 0) { return false; }
255                    for k in 0..prev_len { if !emit(ctx, prev[k]) { return false; } }
256                    let jmp = ctx.pos;
257                    if !emit(ctx, OP_JUMP) || !emit32(ctx, 0) { return false; }
258                    let after = ctx.pos;
259                    unsafe {
260                        patch32((*ctx.code).code, sp + 1, after as u32);
261                        patch32((*ctx.code).code, jmp + 1, sp as u32);
262                    }
263                } else if b == b'+' {
264                    let jmp = ctx.pos;
265                    if !emit(ctx, OP_JUMP) || !emit32(ctx, 0) { return false; }
266                    let sp = ctx.pos;
267                    if !emit(ctx, OP_SPLIT) || !emit32(ctx, 0) { return false; }
268                    for k in 0..prev_len { if !emit(ctx, prev[k]) { return false; } }
269                    let after = ctx.pos;
270                    unsafe {
271                        patch32((*ctx.code).code, jmp + 1, sp as u32);
272                        patch32((*ctx.code).code, sp + 1, after as u32);
273                    }
274                } else {
275                    let sp = ctx.pos;
276                    if !emit(ctx, OP_SPLIT) || !emit32(ctx, 0) { return false; }
277                    for k in 0..prev_len { if !emit(ctx, prev[k]) { return false; } }
278                    let after = ctx.pos;
279                    unsafe { patch32((*ctx.code).code, sp + 1, after as u32); }
280                }
281                ctx.last_atom_start = prev_start;
282                i += 1;
283                continue;
284            }
285        }
286
287        if b >= 0x80 { return false; }
288        let atom = ctx.pos;
289        if !emit_char(ctx, b) { return false; }
290        ctx.last_atom_start = atom;
291        i += 1;
292    }
293    true
294}
295
296fn in_group_check(start: usize, end: usize, extended: bool) -> bool {
297    extended && end > start
298}
299
300fn compile_group(
301    ctx: &mut RegexCContext,
302    pat: *const c_char,
303    plen: usize,
304    i: &mut usize,
305    end: usize,
306) -> bool {
307    let start = *i;
308    let mut depth = 1;
309    let mut j = start;
310    while j < end && depth > 0 {
311        let b = unsafe { *pat.add(j) as u8 };
312        if b == b'(' { depth += 1; }
313        else if b == b')' { depth -= 1; }
314        if depth > 0 { j += 1; }
315    }
316    if depth != 0 { return false; }
317    if !compile_expr(ctx, pat, plen, start, j, true) { return false; }
318    *i = j + 1;
319    true
320}
321
322fn add_range(ctx: &mut RegexCContext, bi: usize, min: u8, max: u8) -> bool {
323    let bd = unsafe { &mut *(*ctx.code).brackets.add(bi) };
324    if bd.nranges == bd.ranges_cap {
325        let cap = if bd.ranges_cap == 0 { 16 } else { bd.ranges_cap * 2 };
326        let p = unsafe {
327            crate::realloc(
328                bd.ranges as *mut c_void,
329                cap * core::mem::size_of::<BracketRange>(),
330            )
331        } as *mut BracketRange;
332        if p.is_null() {
333            ctx.err = REG_ESPACE;
334            return false;
335        }
336        bd.ranges = p;
337        bd.ranges_cap = cap;
338    }
339    unsafe { *bd.ranges.add(bd.nranges) = BracketRange { min, max }; }
340    bd.nranges += 1;
341    true
342}
343
344fn compile_bracket(
345    ctx: &mut RegexCContext,
346    pat: *const c_char,
347    _plen: usize,
348    i: &mut usize,
349    end: usize,
350) -> bool {
351    let bi = unsafe { (*ctx.code).n_brackets };
352    unsafe {
353        let code = &mut *ctx.code;
354        if bi == code.brackets_cap {
355            let cap = if code.brackets_cap == 0 { 8 } else { code.brackets_cap * 2 };
356            let p = crate::realloc(
357                code.brackets as *mut c_void,
358                cap * core::mem::size_of::<BracketData>(),
359            ) as *mut BracketData;
360            if p.is_null() {
361                ctx.err = REG_ESPACE;
362                return false;
363            }
364            code.brackets = p;
365            code.brackets_cap = cap;
366        }
367        let bd = &mut *code.brackets.add(bi);
368        bd.negated = false;
369        bd.icase = ctx.icase;
370        bd.nranges = 0;
371        bd.ranges = core::ptr::null_mut();
372        bd.ranges_cap = 0;
373        code.n_brackets += 1;
374    }
375
376    let mut negated = false;
377    let mut j = *i + 1;
378    if j >= end { return false; }
379    let first = unsafe { *pat.add(j) as u8 };
380    if first == b'^' { negated = true; j += 1; }
381
382    while j < end {
383        let cb = unsafe { *pat.add(j) as u8 };
384        if cb == b']' && j > *i + 1 + (if negated { 1 } else { 0 }) { break; }
385        if cb >= 0x80 { return false; }
386        let lo = cb;
387        j += 1;
388
389        if j + 1 < end && unsafe { *pat.add(j) as u8 } == b'-' {
390            let dash_next = unsafe { *pat.add(j + 1) as u8 };
391            if dash_next == b']' {
392                if !add_range(ctx, bi, lo, lo) { return false; }
393                if ctx.icase && is_ascii_letter(lo) {
394                    let fc = case_fold_byte(lo);
395                    if !add_range(ctx, bi, fc, fc) { return false; }
396                }
397                continue;
398            }
399            if dash_next >= 0x80 { return false; }
400            let hi = dash_next;
401            if lo > hi { return false; }
402            j += 2;
403            if !add_range(ctx, bi, lo, hi) { return false; }
404            if ctx.icase {
405                let flo = case_fold_byte(lo);
406                let fhi = case_fold_byte(hi);
407                if flo != lo || fhi != hi {
408                    let (rmin, rmax) = if flo < fhi { (flo, fhi) } else { (fhi, flo) };
409                    if !add_range(ctx, bi, rmin, rmax) { return false; }
410                }
411            }
412        } else {
413            if !add_range(ctx, bi, lo, lo) { return false; }
414            if ctx.icase && is_ascii_letter(lo) {
415                let f = case_fold_byte(lo);
416                if !add_range(ctx, bi, f, f) { return false; }
417            }
418        }
419    }
420    if j >= end || unsafe { *pat.add(j) as u8 } != b']' { return false; }
421    *i = j + 1;
422
423    unsafe {
424        let bd = &mut *(*ctx.code).brackets.add(bi);
425        bd.negated = negated;
426        bd.icase = ctx.icase;
427    }
428
429    if !emit(ctx, OP_BRACKET) { return false; }
430    if !emit32(ctx, bi as u32) { return false; }
431    true
432}
433
434#[inline]
435unsafe fn read32(code: *const u8, at: usize) -> usize {
436    (*code.add(at) as usize)
437        | ((*code.add(at + 1) as usize) << 8)
438        | ((*code.add(at + 2) as usize) << 16)
439        | ((*code.add(at + 3) as usize) << 24)
440}
441
442fn match_regex_impl(
443    code: &CompiledRegex,
444    input: *const c_char,
445    nmatch: usize,
446    pmatch: *mut crate::regmatch_t,
447    eflags: c_int,
448) -> c_int {
449    let frames = match (code.ncode + 1).checked_mul(core::mem::size_of::<MatchFrame>()) {
450        Some(n) => n,
451        None => return REG_ESPACE,
452    };
453    let stack = unsafe { crate::malloc(frames) } as *mut MatchFrame;
454    if stack.is_null() {
455        return REG_ESPACE;
456    }
457    let r = match_regex_inner(code, input, nmatch, pmatch, eflags, stack);
458    unsafe { crate::free(stack as *mut c_void) };
459    r
460}
461
462fn match_regex_inner(
463    code: &CompiledRegex,
464    input: *const c_char,
465    nmatch: usize,
466    pmatch: *mut crate::regmatch_t,
467    eflags: c_int,
468    stack: *mut MatchFrame,
469) -> c_int {
470    let slen = unsafe { crate::strlen(input) };
471    let notbol = (eflags & REG_NOTBOL) != 0;
472    let noteol = (eflags & REG_NOTEOL) != 0;
473    let bytecode = code.code;
474    let ncode = code.ncode;
475    let stack_cap = ncode + 1;
476
477    for start in 0..=slen {
478        let mut top: usize = 0;
479        unsafe { *stack.add(top) = MatchFrame { pc: 0, sp: start, at_bol: start == 0 }; }
480        top += 1;
481        let mut found = false;
482        let mut match_end = 0usize;
483
484        while top > 0 {
485            top -= 1;
486            let frame = unsafe { *stack.add(top) };
487            let mut pc = frame.pc;
488            let mut sp = frame.sp;
489            let mut at_bol = frame.at_bol;
490
491            loop {
492                if pc >= ncode { break; }
493                let op = unsafe { *bytecode.add(pc) };
494                match op {
495                    OP_CHAR => {
496                        if sp >= slen { break; }
497                        let expected = unsafe { *bytecode.add(pc + 1) };
498                        let actual = unsafe { *input.add(sp) as u8 };
499                        let m = if code.icase && is_ascii_letter(expected) && is_ascii_letter(actual) {
500                            case_fold_byte(expected) == case_fold_byte(actual)
501                        } else {
502                            expected == actual
503                        };
504                        if !m { break; }
505                        sp += 1;
506                        at_bol = false;
507                        pc += 2;
508                    }
509                    OP_BRACKET => {
510                        if sp >= slen { break; }
511                        let bi = unsafe { read32(bytecode, pc + 1) };
512                        let actual = unsafe { *input.add(sp) as u8 };
513                        if bi >= code.n_brackets { break; }
514                        if !bracket_contains(unsafe { &*code.brackets.add(bi) }, actual) { break; }
515                        sp += 1;
516                        at_bol = false;
517                        pc += 5;
518                    }
519                    OP_MATCH => {
520                        if !noteol || sp == slen {
521                            found = true;
522                            match_end = sp;
523                        }
524                        break;
525                    }
526                    OP_JUMP => {
527                        pc = unsafe { read32(bytecode, pc + 1) };
528                    }
529                    OP_SPLIT => {
530                        let alt = unsafe { read32(bytecode, pc + 1) };
531                        let next = pc + 5;
532                        if top + 2 <= stack_cap {
533                            unsafe {
534                                *stack.add(top) = MatchFrame { pc: alt, sp, at_bol };
535                                top += 1;
536                                *stack.add(top) = MatchFrame { pc: next, sp, at_bol };
537                            }
538                            top += 1;
539                        }
540                        break;
541                    }
542                    OP_BOL => {
543                        if !at_bol && !(start == 0 && !notbol) { break; }
544                        pc += 1;
545                    }
546                    OP_EOL => {
547                        if sp != slen { break; }
548                        pc += 1;
549                    }
550                    _ => { break; }
551                }
552            }
553            if found { break; }
554        }
555
556        if found {
557            if !pmatch.is_null() && nmatch > 0 {
558                unsafe {
559                    (*pmatch).rm_so = start as crate::regoff_t;
560                    (*pmatch).rm_eo = match_end as crate::regoff_t;
561                }
562            }
563            return REG_OK;
564        }
565    }
566    REG_NOMATCH
567}
568
569unsafe fn free_compiled(code: *mut CompiledRegex) {
570    if code.is_null() { return; }
571    let c = &*code;
572    if !c.brackets.is_null() {
573        let mut i = 0usize;
574        while i < c.n_brackets {
575            let bd = &*c.brackets.add(i);
576            if !bd.ranges.is_null() {
577                crate::free(bd.ranges as *mut c_void);
578            }
579            i += 1;
580        }
581        crate::free(c.brackets as *mut c_void);
582    }
583    if !c.code.is_null() {
584        crate::free(c.code as *mut c_void);
585    }
586    crate::free(code as *mut c_void);
587}
588
589#[no_mangle]
590pub unsafe extern "C" fn regcomp(preg: *mut crate::regex_t, pattern: *const c_char, cflags: c_int) -> c_int {
591    if preg.is_null() || pattern.is_null() { return REG_BADPAT; }
592    let code = crate::malloc(core::mem::size_of::<CompiledRegex>()) as *mut CompiledRegex;
593    if code.is_null() { return REG_ESPACE; }
594    crate::memset(code as *mut c_void, 0, core::mem::size_of::<CompiledRegex>());
595    let rc = compile_regex_into(pattern, cflags, code);
596    if rc != REG_OK {
597        free_compiled(code);
598        return rc;
599    }
600    crate::memset(preg as *mut c_void, 0, core::mem::size_of::<crate::regex_t>());
601    (*preg).__opaque = code as *mut c_void;
602    REG_OK
603}
604
605fn compile_regex_into(pat: *const c_char, flags: c_int, code: *mut CompiledRegex) -> c_int {
606    unsafe {
607        let plen = crate::strlen(pat);
608        if plen == 0 { return REG_BADPAT; }
609
610        crate::memset(code as *mut c_void, 0, core::mem::size_of::<CompiledRegex>());
611        (*code).icase = (flags & REG_ICASE) != 0;
612        (*code).extended = (flags & REG_EXTENDED) != 0;
613
614        let mut ctx = RegexCContext {
615            code,
616            pos: 0,
617            last_atom_start: 0,
618            err: REG_OK,
619            extended: (*code).extended,
620            icase: (*code).icase,
621        };
622
623        if !compile_expr(&mut ctx, pat, plen, 0, plen, false) {
624            return if ctx.err != 0 { ctx.err } else { REG_BADPAT };
625        }
626
627        if !emit(&mut ctx, OP_MATCH) {
628            return ctx.err;
629        }
630
631        (*code).ncode = ctx.pos;
632        REG_OK
633    }
634}
635
636#[no_mangle]
637pub unsafe extern "C" fn regexec(
638    preg: *const crate::regex_t,
639    string: *const c_char,
640    nmatch: usize,
641    pmatch: *mut crate::regmatch_t,
642    eflags: c_int,
643) -> c_int {
644    if preg.is_null() || string.is_null() { return REG_BADPAT; }
645    let code = (*preg).__opaque as *const CompiledRegex;
646    if code.is_null() { return REG_BADPAT; }
647    match_regex_impl(&*code, string, nmatch, pmatch, eflags)
648}
649
650const ERR_MSG: &[u8] = b"unknown error\0";
651const PAT_MSG: &[u8] = b"invalid pattern\0";
652const OK_MSG: &[u8] = b"no error\0";
653
654#[no_mangle]
655pub unsafe extern "C" fn regerror(
656    errcode: c_int,
657    _preg: *const crate::regex_t,
658    errbuf: *mut c_char,
659    errbuf_size: usize,
660) -> usize {
661    let msg = match errcode {
662        0 => OK_MSG,
663        2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 13 => PAT_MSG,
664        12 => b"out of memory\0" as &[u8],
665        _ => ERR_MSG,
666    };
667    let len = crate::strlen(msg.as_ptr() as *const c_char);
668    if !errbuf.is_null() && errbuf_size > 0 {
669        let copy = if len < errbuf_size { len } else { errbuf_size - 1 };
670        crate::memcpy(errbuf as *mut c_void, msg.as_ptr() as *const c_void, copy);
671        *errbuf.add(copy) = 0;
672    }
673    len + 1
674}
675
676#[no_mangle]
677pub unsafe extern "C" fn regfree(preg: *mut crate::regex_t) {
678    if preg.is_null() { return; }
679    let code = (*preg).__opaque as *mut CompiledRegex;
680    if !code.is_null() {
681        free_compiled(code);
682        (*preg).__opaque = core::ptr::null_mut();
683    }
684}
c/regex.rs

c/
regex.rs
