Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / es_tests.lucb

#==============================================================================================
#
#   es_tests - Conformance tests of the ECMAScript dialect against QuickJS's libregexp
#
#   DESCRIPTION:
#       Every expectation of the es_table_* fragments comes from upstream libregexp.c: the
#       outcome of compiling a pattern (its error message, or its capture count, flags and
#       group names), the result of an exec over an 8-bit or 16-bit subject from a start
#       index, and parse_escape. A row's host mode selects the callbacks: 0 normal, 1
#       check_timeout always true, 2 check_stack_overflow always true, 100 + N the allocator
#       fails after N allocations (for an exec row, N allocations after the compile).
#
#==============================================================================================

# mark: Table rows =============================================================================

struct CompileCase:
    let pattern: str
    let flags: i32
    let mode: i32
    let expect: str

struct ExecCase:
    let pattern: str
    let flags: i32
    let mode: i32
    # the code units; `%XXXX` is one unit in hex
    let subject: str
    let cbuf_type: i32
    let cindex: i32
    let expect: str

struct EscapeCase:
    let text: str
    let allow_utf16: i32
    let expect: str

# mark: Hosts ==================================================================================

var test_alloc_left: i32 = 0
# blocks allocated through test_limited_realloc and not yet freed: every test ends at zero
var test_live_blocks: i32 = 0

func test_limited_realloc(opaque: void*?, ptr: void*?, size: usize) -> void*?:
    if size == 0:
        if ptr != none:
            test_live_blocks -= 1
        unicode.c_free(ptr)
        return none
    if test_alloc_left <= 0:
        return none
    test_alloc_left -= 1
    let p = unicode.c_realloc(ptr, size)
    if ptr == none and p != none:
        test_live_blocks += 1
    return p

func test_yes(opaque: void*?, size: usize) -> bool:
    return true

func test_timeout(opaque: void*?) -> bool:
    return true

func test_host(mode: i32) -> Host:
    # every allocation is counted; only mode 100 + N limits them
    test_alloc_left = 1000000000
    var host = Host(realloc_func = test_limited_realloc)
    if mode == 1:
        host.check_timeout = test_timeout
    elif mode == 2:
        host.check_stack_overflow = test_yes
    elif mode >= 100:
        test_alloc_left = mode - 100
    return host

# mark: Descriptions ===========================================================================

# A growable text for the descriptions.
struct Text:
    var bytes: Vec[u8]

    func add(s: const u8[]):
        for b in s:
            _ = self.bytes.push(b) catch failure: trap("out of memory")

    func add_int(v: i32):
        var buf: u8[16]
        let t = strings.format(buf, f"{v}") catch failure:
            recover "?"
        self.add(t.bytes)

    func view() -> str:
        return (str)self.bytes.data[..<self.bytes.used]

func put_hex(t: Text*, v: u32):
    let chars = "0123456789abcdef".bytes
    var digits: i32 = 1
    while digits < 8 and (v >> (u32)(digits * 4)) != 0:
        digits += 1
    var i = digits - 1
    while i >= 0:
        let one = chars[(usize)((v >> (u32)(i * 4)) & 15)..<(usize)((v >> (u32)(i * 4)) & 15) + 1]
        t.add(one)
        i -= 1

# "err=MSG" or "ok cc=N flags=0xN[ names=<a>,<b>]", as the C driver prints (less the bytecode).
func describe_compile(t: Text*, re: Regex*?, message: const u8[]):
    if re == none:
        t.add("err=".bytes)
        var n: usize = 0
        while n < message.length and message[n] != 0:
            n += 1
        t.add(message[..<n])
        return
    let prog = re else trap("unreachable")
    let cc = capture_count(prog)
    t.add("ok cc=".bytes)
    t.add_int(cc)
    t.add(" flags=0x".bytes)
    put_hex(t, (u32)program_flags(prog))
    if let names = group_names(prog):
        t.add(" names=".bytes)
        var p: usize = 0
        var i: i32 = 1
        while i < cc:
            if i != 1:
                t.add(",".bytes)
            var n: usize = 0
            while names[p + n] != 0:
                n += 1
            t.add("<".bytes)
            t.add(names[p..<p + n])
            t.add(">".bytes)
            p += n + 2
            i += 1

func hex_value(c: u8) -> u32:
    if c >= '0' and c <= '9':
        return (u32)(c - '0')
    return (u32)(c - 'a') + 10

# Decode a row's subject into code units.
func decode_units(subject: str, out: Vec[u16]*):
    let b = subject.bytes
    var i: usize = 0
    while i < b.length:
        if b[i] == '%':
            var v: u32 = 0
            for k: usize in 1..=4:
                v = (v << 4) | hex_value(b[i + k])
            _ = out.push((u16)v) catch failure: trap("out of memory")
            i += 5
        else:
            _ = out.push((u16)b[i]) catch failure: trap("out of memory")
            i += 1

# mark: Known deviations =======================================================================

# A row where this engine follows ECMAScript and libregexp does not: libregexp emits a v-flag
# class string inside a lookbehind forward (PREV, the string's characters, PREV), so a string
# of more than one character cannot match there; this engine matches it backward, as the
# specification's backward matcher does (V8 answers the same).
func exec_deviation(c: const ExecCase*, got: str) -> bool:
    return c.pattern == "(?<=[\\q{ab}])c" and c.flags == es_unicode_sets and got == "1 2,3"

# mark: Checks =================================================================================

func check_compile(c: const CompileCase*) -> bool:
    let live0 = test_live_blocks
    defer if_leak(c, live0)
    let host = test_host(c.mode)
    var message: u8[64]
    let re = compile_ecmascript(c.pattern.bytes, c.flags, message, &host)
    var t = Text(bytes = Vec[u8]())
    defer t.bytes.free_all()
    describe_compile(&t, re, message)
    var ok = t.view() == c.expect
    # Known deviation: when building \d, \s or \w runs out of memory, libregexp fails
    # without setting a message (cr_init_char_range); this engine says "out of memory".
    if not ok and c.mode >= 100 and c.expect == "err=" and t.view() == "err=out of memory":
        ok = true
    if not ok:
        print(f"compile /{c.pattern}/ {c.flags} mode {c.mode}:\n  got    {t.view()}\n  expect {c.expect}")
    if let prog = re:
        free_ecmascript(prog)
    return ok

func if_leak(c: const CompileCase*, live0: i32):
    if test_live_blocks != live0:
        print(f"LEAK {test_live_blocks - live0} /{c.pattern}/ {c.flags} mode {c.mode}")

func check_exec(c: const ExecCase*) -> bool:
    # compile with an allocator that only starts counting for the exec
    test_alloc_left = 1000000000
    var compile_host = Host(realloc_func = test_limited_realloc)
    var message: u8[64]
    let re0 = compile_ecmascript(c.pattern.bytes, c.flags, message, &compile_host)
    var t = Text(bytes = Vec[u8]())
    defer t.bytes.free_all()
    if re0 == none:
        var n: usize = 0
        while message[n] != 0:
            n += 1
        t.add("compile error ".bytes)
        t.add(message[..<n])
        if t.view() != c.expect:
            print(f"exec /{c.pattern}/: got {t.view()}, expect {c.expect}")
            return false
        return true
    let re = re0 else trap("unreachable")
    defer free_ecmascript(re)
    var units = Vec[u16]()
    defer units.free_all()
    decode_units(c.subject, &units)
    var bytes = Vec[u8]()
    defer bytes.free_all()
    for u in units.data[..<units.used]:
        _ = bytes.push((u8)u) catch failure: trap("out of memory")
    let cc = capture_count(re)
    let captures = new i32[(usize)(2 * cc)] --- in memory.heap catch failure: trap("out of memory")
    defer free(captures) in memory.heap
    let host = test_host(c.mode)
    var ret: i32 = 0
    if c.cbuf_type == 0:
        ret = exec8(re, bytes.data[..<bytes.used], c.cindex, captures, &host)
    else:
        ret = exec16(re, units.data[..<units.used], c.cindex, captures, &host)
    t.add_int(ret)
    if ret == 1:
        for i: i32 in 0..<cc:
            let a = captures[(usize)(2 * i)]
            let z = captures[(usize)(2 * i + 1)]
            if a >= 0 and z >= 0:
                t.add(" ".bytes)
                t.add_int(a)
                t.add(",".bytes)
                t.add_int(z)
            else:
                t.add(" -".bytes)
    var ok = t.view() == c.expect
    if not ok and exec_deviation(c, t.view()):
        ok = true
    if not ok:
        print(f"exec /{c.pattern}/ {c.flags} mode {c.mode} on \"{c.subject}\" type {c.cbuf_type} at {c.cindex}:\n  got    {t.view()}\n  expect {c.expect}")
    return ok

# mark: Tests ==================================================================================

test "ECMAScript compile: capture counts, flags, group names and error messages":
    var failures: i32 = 0
    for c in &es_compile_cases:
        if not check_compile(c):
            failures += 1
    print(f"compile rows: {es_compile_cases.length - (usize)failures} of {es_compile_cases.length} pass")
    assert(failures == 0)
    assert(test_live_blocks == 0, "a compile leaked")

test "ECMAScript exec: captures over 8-bit and 16-bit subjects":
    var failures: i32 = 0
    for c in &es_exec_cases1:
        if not check_exec(c):
            failures += 1
    for c in &es_exec_cases2:
        if not check_exec(c):
            failures += 1
    let total = es_exec_cases1.length + es_exec_cases2.length
    print(f"exec rows: {total - (usize)failures} of {total} pass")
    assert(failures == 0)
    assert(test_live_blocks == 0, "an exec leaked")

test "parse_escape":
    var failures: i32 = 0
    for c in &es_escape_cases:
        var pos: usize = 0
        let ret = parse_escape(c.text.bytes, &pos, c.allow_utf16)
        var buf: u8[32]
        let got = strings.format(buf, f"{ret} {pos}") catch failure:
            recover "?"
        if got != c.expect:
            print(f"escape \"{c.text}\" {c.allow_utf16}: got {got}, expect {c.expect}")
            failures += 1
    assert(failures == 0)

test "ECMAScript extra rows: lookbehind, loops, names, modifiers, folding, surrogates, sets":
    var failures: i32 = 0
    for c in &es_extra_compile_cases:
        if not check_compile(c):
            failures += 1
    for c in &es_extra_exec_cases:
        if not check_exec(c):
            failures += 1
    let total = es_extra_compile_cases.length + es_extra_exec_cases.length
    print(f"extra rows: {total - (usize)failures} of {total} pass")
    assert(failures == 0)
    assert(test_live_blocks == 0, "a compile or exec leaked")

# mark: The API ================================================================================

func units16(text: str, out: Vec[u16]*):
    for ch in text:
        let c = (u32)ch
        if c > 0xFFFF:
            _ = out.push((u16)(0xD800 + ((c - 0x10000) >> 10))) catch failure: trap("oom")
            _ = out.push((u16)(0xDC00 + ((c - 0x10000) & 0x3FF))) catch failure: trap("oom")
        else:
            _ = out.push((u16)c) catch failure: trap("oom")

test "compile_ecmascript16 encodes UTF-16 patterns as QuickJS does":
    var message: u8[64]
    var pat = Vec[u16]()
    defer pat.free_all()
    units16("(?<x>\u{1F600})+", &pat)
    var subj = Vec[u16]()
    defer subj.free_all()
    units16("a\u{1F600}\u{1F600}b", &subj)
    var caps: i32[4]
    # with u: one code point, the pair
    let re_u = compile_ecmascript16(pat.data[..<pat.used], es_unicode, message, none) else trap("compile")
    assert(exec16(re_u, subj.data[..<subj.used], 0, caps, none) == exec_match)
    assert(caps[0] == 1 and caps[1] == 5 and caps[2] == 3 and caps[3] == 5)
    assert(re_u.group_of("x") == 1 and re_u.group_of("y") == -1)
    free_ecmascript(re_u)
    # without u: two code units, so a quantifier after the character repeats the low
    # surrogate alone
    var pat2 = Vec[u16]()
    defer pat2.free_all()
    units16("\u{1F600}+", &pat2)
    let re = compile_ecmascript16(pat2.data[..<pat2.used], 0, message, none) else trap("compile")
    assert(exec16(re, subj.data[..<subj.used], 0, caps, none) == exec_match)
    assert(caps[0] == 1 and caps[1] == 3)
    free_ecmascript(re)
    let re2 = compile_ecmascript16(pat2.data[..<pat2.used], es_unicode, message, none) else trap("compile")
    assert(exec16(re2, subj.data[..<subj.used], 0, caps, none) == exec_match)
    assert(caps[0] == 1 and caps[1] == 5)
    free_ecmascript(re2)

test "compile_ecmascript reports QuickJS's messages, truncated to the buffer":
    var message: u8[8]
    assert(compile_ecmascript("a)".bytes, 0, message, none) == none)
    assert((str)message[0..<7] == "extrane" and message[7] == 0)
    var full: u8[64]
    assert(compile_ecmascript("(?ii:a)".bytes, 0, full, none) == none)
    var n: usize = 0
    while full[n] != 0:
        n += 1
    assert((str)full[0..<n] == "duplicate modifier: 'i'")
    let re = compile_ecmascript("(?<first>a)(b)".bytes, es_global | es_indices, full, none) else trap("compile")
    assert(full[0] == 0)
    assert(capture_count(re) == 3)
    assert(program_flags(re) == (es_global | es_indices | es_named_groups))
    let names = group_names(re) else trap("no names")
    assert(names.length == 9 and (str)names[0..<5] == "first" and names[5] == 0 and names[7] == 0)
    free_ecmascript(re)

var interrupt_calls: i32 = 0

func count_and_stop(opaque: void*?) -> bool:
    interrupt_calls += 1
    return interrupt_calls >= 3

test "exec polls check_timeout and stops when asked":
    var message: u8[64]
    let re = compile_ecmascript("(a*)*b".bytes, 0, message, none) else trap("compile")
    defer free_ecmascript(re)
    var caps: i32[4]
    let host = Host(check_timeout = count_and_stop)
    assert(exec8(re, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".bytes, 0, caps, &host) == exec_interrupted)
    assert(interrupt_calls == 3)
    # the same program still matches afterwards
    assert(exec8(re, "aaab".bytes, 0, caps, none) == exec_match)
    assert(caps[0] == 0 and caps[1] == 4 and caps[2] == 0 and caps[3] == 3)

test "the README example":
    var message: u8[128]
    let re = compile_ecmascript("(?<year>\\d{4})-(?<month>\\d{2})".bytes, es_unicode, message, none) else trap("syntax error")
    defer free_ecmascript(re)
    var captures: i32[6]
    assert(exec8(re, "on 2024-05-01".bytes, 0, captures, none) == exec_match)
    assert(captures[0] == 3 and captures[1] == 10 and captures[2] == 3 and captures[3] == 7)
    assert(captures[4] == 8 and captures[5] == 10)
    assert(re.group_of("month") == 2)