c/
regex.rs

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

c/
regex.rs
