Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / es_api.lucb

#==============================================================================================
#
#   es_api - The ECMAScript dialect's public interface
#
#   DESCRIPTION:
#       What a JavaScript engine needs for RegExp, shaped like QuickJS's lre_compile /
#       lre_exec so luce-js can call it where it called libregexp:
#
#       - `compile_ecmascript(pattern, flags, message, host)` compiles a pattern given as
#         UTF-8 bytes (with the u or v flag) or CESU-8 bytes (each UTF-16 code unit encoded
#         alone, as QuickJS's JS_ToCStringLen2 produces without them); lone surrogates are
#         three-byte sequences. `compile_ecmascript16` takes the pattern as UTF-16 code units
#         and encodes it that way. The program is answered, or none with QuickJS's syntax
#         error message (NUL-terminated, truncated) in `message`.
#       - `capture_count`, `program_flags` and `group_names` describe the program.
#       - `exec8` / `exec16` match a Latin-1 or UTF-16 subject from a start index (a code
#         unit index; with u or v, an index inside a surrogate pair starts at the pair).
#         Without y the leftmost match at or after it is found; with y only one at it. The
#         answer is 1 (match: `captures` holds each group's start and end code unit index,
#         or -1 for a group that did not participate), 0 (no match), -1 (out of memory) or
#         -2 (the host's check_timeout asked to stop).
#       - `free_ecmascript` releases a program.
#
#       The host's callbacks: check_stack_overflow(opaque, 0) is asked at each nested
#       disjunction and class while compiling (true fails the compile with "stack
#       overflow"; matching is iterative and needs no such check); check_timeout(opaque) is
#       polled every 10000 steps of a match; realloc_func(opaque, ptr, size), with C realloc
#       semantics, provides all the program's memory, including the backtracking stacks an
#       exec grows (C's realloc when none). The host given to compile_ecmascript supplies
#       the allocator for the program's whole life; exec takes a host for check_timeout.
#
#==============================================================================================

# mark: The host ===============================================================================

## The callbacks an ECMAScript program's compile and exec use; every one is optional.
## QuickJS passes its JSContext as `opaque`.
pub struct Host:
    ## Passed as the first argument of every callback.
    pub var opaque: void*? = none
    ## `(opaque, size)`: true if the native stack is about to overflow; the compiler then
    ## fails with "stack overflow".
    pub var check_stack_overflow: (func(void*?, usize) -> bool)? = none
    ## `(opaque)`: true if the match must stop; exec then answers -2.
    pub var check_timeout: (func(void*?) -> bool)? = none
    ## `(opaque, ptr, size)` with C `realloc` semantics: the program's allocator.
    pub var realloc_func: ReallocFunc? = none

## exec's answer: a match.
pub let exec_match: i32 = 1
## exec's answer: no match.
pub let exec_no_match: i32 = 0
## exec's answer: an allocation failed.
pub let exec_out_of_memory: i32 = -1
## exec's answer: the host's check_timeout asked to stop.
pub let exec_interrupted: i32 = -2

# mark: Compiling ==============================================================================

# Every field of a fresh ECMAScript program allocating through `heap`.
func es_reset(re: Regex*, heap: Heap):
    re.pat = Vec[u32](heap = heap)
    re.pp = 0
    re.nodes = Vec[Node](heap = heap)
    re.ic = false
    re.ext = false
    re.dotall = false
    re.multi = false
    re.ngroups = 0
    re.name_cps = Vec[u32](heap = heap)
    re.names = Vec[NameEntry](heap = heap)
    re.classes = Vec[CharClass](heap = heap)
    re.ranges = Vec[u32](heap = heap)
    re.code = Vec[Inst](heap = heap)
    re.subprogs = Vec[Program](heap = heap)
    re.mark_count = 0
    var empty: i32[]
    re.marks = empty
    re.caps = empty
    re.has_g = false
    re.first_any = false
    re.first_chars = Vec[u32](heap = heap)
    re.first_classes = Vec[i32](heap = heap)
    re.len = 0
    re.anchor = 0
    re.steps = 0
    re.budget = 10000
    re.stacks = stacks_on(heap)
    re.text_subj = Vec[u32](heap = heap)
    re.es = true
    re.es_flags = 0
    re.unicode = false
    re.ncap = 1
    re.nregs = 0
    re.reg_depth = 0
    re.group_names = Vec[u8](heap = heap)
    re.ref_lists = Vec[i32](heap = heap)
    re.heap = heap
    re.check_timeout = none
    re.host_opaque = none
    re.first_chars_i = Vec[u32](heap = heap)

# pstrcpy into the caller's buffer.
func copy_message(out: u8[], text: const u8[]):
    if out.length == 0:
        return
    var n = text.length
    if n > out.length - 1:
        n = out.length - 1
    var i: usize = 0
    while i < n:
        out[i] = text[i]
        i += 1
    out[n] = 0

## Compile the ECMAScript `pattern` (UTF-8 with the u or v flag, CESU-8 without; see the
## module notes) with `flags` (es_global, es_ignore_case, ...). Answers the program, or none
## with the syntax error in `message` (NUL-terminated, truncated to fit). Free the program
## with `free_ecmascript`.
pub func compile_ecmascript(pattern: const u8[], flags: i32, message: u8[], host: const Host*?) -> Regex*?:
    var heap = Heap(realloc_func = c_heap_realloc, opaque = none)
    var check_stack: (func(void*?, usize) -> bool)? = none
    if let h = host:
        heap.opaque = h.opaque
        if let rf = h.realloc_func:
            heap.realloc_func = rf
        check_stack = h.check_stack_overflow
    let rf = heap.realloc_func else trap("unreachable")
    let mem = rf(heap.opaque, none, memory.size_of(Regex))
    if mem == none:
        copy_message(message, "out of memory".bytes)
        return none
    let re = (Regex*)(mem else trap("unreachable"))
    es_reset(re, heap)
    var ps = EsParse(re = re, src = pattern, p = 0)
    ps.is_unicode = (flags & (es_unicode | es_unicode_sets)) != 0
    ps.unicode_sets = (flags & es_unicode_sets) != 0
    ps.ignore_case = (flags & es_ignore_case) != 0
    ps.multi_line = (flags & es_multiline) != 0
    ps.dotall = (flags & es_dotall) != 0
    ps.capture_count = 1
    ps.total_capture_count = -1
    ps.has_named_captures = -1
    ps.check_stack = check_stack
    ps.opaque = heap.opaque
    es_build(&ps, flags) catch failure:
        if failure.code == syntax_error:
            copy_message(message, ps.message[0..<ps.message_len])
        else:
            copy_message(message, "out of memory".bytes)
        free_ecmascript(re)
        return none
    copy_message(message, "".bytes)
    return re

## `compile_ecmascript` for a pattern given as UTF-16 code units (a JavaScript string):
## encoded as UTF-8 with the u or v flag (a surrogate pair as one code point) and as
## CESU-8 without, as QuickJS encodes it.
pub func compile_ecmascript16(pattern: const u16[], flags: i32, message: u8[], host: const Host*?) -> Regex*?:
    let pairs = (flags & (es_unicode | es_unicode_sets)) != 0
    let bytes = new u8[pattern.length * 3 + 1] --- in memory.heap catch failure:
        copy_message(message, "out of memory".bytes)
        return none
    defer free(bytes) in memory.heap
    var n: usize = 0
    var i: usize = 0
    while i < pattern.length:
        var c = (u32)pattern[i]
        i += 1
        if pairs and is_hi_surrogate(c) and i < pattern.length and is_lo_surrogate((u32)pattern[i]):
            c = from_surrogate(c, (u32)pattern[i])
            i += 1
        n += utf8_encode(bytes[n..], c)
    return compile_ecmascript(bytes[..<n], flags, message, host)

func es_build(ps: EsParse*, flags: i32) -> !:
    let re = ps.re
    re.es_flags = flags
    re.unicode = ps.is_unicode
    let root = try es_parse_disjunction(ps)
    if cur(ps) != 0:
        _ = try es_fail(ps, "extraneous characters at the end")
    re.ncap = ps.capture_count
    re.reg_depth = 0
    try es_compile(re, root, &re.code, false)
    _ = try re.code.push(Inst(op = OP_MATCH))
    re.nregs = es_register_count(re)
    if re.nregs > REGISTER_COUNT_MAX:
        _ = try es_fail(ps, "too many imbricated quantifiers")
    # named groups are present when some name is not empty
    if re.group_names.used > (usize)((re.ncap - 1) * 2):
        re.es_flags |= es_named_groups
    re.caps = try heap_alloc[i32](&re.heap, (usize)(2 * re.ncap + re.nregs))
    var i: usize = 0
    while i < re.caps.length:
        re.caps[i] = -1
        i += 1
    try es_compute_first(re)
    re.nodes.free_all()

## Release a program from `compile_ecmascript`.
pub func free_ecmascript(re: Regex*):
    regex_dispose(re)
    let heap = re.heap
    let rf = heap.realloc_func else trap("free_ecmascript: not an ECMAScript program")
    _ = rf(heap.opaque, re, 0)

# mark: Describing =============================================================================

## The number of capture groups, including group 0 (the whole match): `captures` of exec
## needs twice as many elements.
pub func capture_count(re: const Regex*) -> i32:
    return re.ncap

## The flags the program was compiled with, plus es_named_groups when it has named groups.
pub func program_flags(re: const Regex*) -> i32:
    return re.es_flags

## The group names, or none when the program has no named group: for each group after
## group 0, its UTF-8 name followed by a NUL and one more byte (QuickJS's layout; an unnamed
## group is two NULs).
pub func group_names(re: const Regex*) -> const u8[]?:
    if (re.es_flags & es_named_groups) == 0:
        return none
    return re.group_names.data[..<re.group_names.used]

func es_group_of(re: const Regex*, name: str) -> i32:
    let names = re.group_names.data[..<re.group_names.used]
    var p: usize = 0
    var index: i32 = 1
    while p < names.length:
        var len: usize = 0
        while names[p + len] != 0:
            len += 1
        if len > 0 and same_name(names[p..<p + len], name.bytes):
            return index
        p += len + 2
        index += 1
    return -1

# mark: Matching ===============================================================================

## Match `subject`, a Latin-1 string, from code unit `start`. See the module notes for the
## answer and `captures` (at least 2 * capture_count(re) elements).
pub func exec8(re: Regex*, subject: const u8[], start: i32, captures: i32[], host: const Host*?) -> i32:
    let src = Latin1(data = subject)
    return es_exec(re, &src, start, captures, host)

## Match `subject`, a UTF-16 string, from code unit `start`.
pub func exec16(re: Regex*, subject: const u16[], start: i32, captures: i32[], host: const Host*?) -> i32:
    if re.unicode:
        let pairs = Utf16Pairs(data = subject)
        return es_exec(re, &pairs, start, captures, host)
    let units = Utf16(data = subject)
    return es_exec(re, &units, start, captures, host)

func es_exec[S: Units](re: Regex*, src: const S*, start: i32, captures: i32[], host: const Host*?) -> i32:
    if not re.es:
        trap("exec: not an ECMAScript program")
    let ncap2 = (usize)(2 * re.ncap)
    if captures.length < ncap2:
        trap("exec: the captures array is too short")
    var k: usize = 0
    while k < ncap2:
        captures[k] = -1
        k += 1
    re.len = src.count()
    re.check_timeout = none
    re.host_opaque = none
    if let h = host:
        re.check_timeout = h.check_timeout
        re.host_opaque = h.opaque
    re.budget = 10000
    re.steps = 0
    var at = start
    if at < 0 or at > re.len:
        return exec_no_match
    # with u or v, a start inside a surrogate pair starts at the pair
    if at > 0 and at < re.len and src.next(at - 1) > 0xFFFF:
        at -= 1
    let sticky = (re.es_flags & es_sticky) != 0
    let code = re.code.data[..<re.code.used]
    while true:
        if not sticky and not re.first_any:
            while at < re.len and not es_first_ok(re, src.next(at)):
                at += src.width(src.next(at))
            if at >= re.len:
                return exec_no_match
        var i: usize = 0
        while i < ncap2:
            re.caps[i] = -1
            i += 1
        let end = es_run(re, src, code, at, &re.stacks)
        if end >= 0:
            re.caps[0] = at
            re.caps[1] = end
            var j: usize = 0
            while j < ncap2:
                captures[j] = re.caps[j]
                j += 1
            return exec_match
        if end == RUN_INTERRUPTED:
            return exec_interrupted
        if end == RUN_NO_MEMORY:
            return exec_out_of_memory
        if sticky or at >= re.len:
            return exec_no_match
        at += src.width(src.next(at))

# mark: First-character filter =================================================================

# The characters and classes a match must start with, when every path from the start reaches
# a character test before anything else that could match (first_any otherwise).
func es_compute_first(re: Regex*) -> !:
    let plen = re.code.used
    var seen = Vec[bool](heap = re.heap)
    defer seen.free_all()
    try seen.ensure(plen)
    seen.used = plen
    var i: usize = 0
    while i < plen:
        seen.data[i] = false
        i += 1
    var stack = Vec[i32](heap = re.heap)
    defer stack.free_all()
    _ = try stack.push(0)
    while stack.used > 0:
        let pc = stack.data[stack.used - 1]
        stack.used -= 1
        if seen.data[(usize)pc]:
            continue
        seen.data[(usize)pc] = true
        let inst = re.code.data[(usize)pc]
        let op = inst.op
        if op == OP_SAVE or op == OP_ASSERT or op == OP_SET_REG or op == OP_SET_POS or op == OP_SAVE_RESET:
            _ = try stack.push(pc + 1)
        elif op == OP_JMP:
            _ = try stack.push(inst.x)
        elif op == OP_SPLIT:
            _ = try stack.push(inst.x)
            _ = try stack.push(inst.y)
        elif op == OP_CHAR:
            _ = try re.first_chars.push(inst.ch)
        elif op == OP_CHAR_I:
            _ = try re.first_chars_i.push(inst.ch)
        elif op == OP_RANGE:
            _ = try re.first_classes.push(inst.x)
        elif op == OP_RANGE_I:
            _ = try re.first_classes.push(-1 - inst.x)
        else:
            re.first_any = true
            return

func es_first_ok(re: const Regex*, c: u32) -> bool:
    var i: usize = 0
    while i < re.first_chars.used:
        if re.first_chars.data[i] == c:
            return true
        i += 1
    if re.first_chars_i.used > 0 or re.first_classes.used > 0:
        let folded = canon(re, c)
        var j: usize = 0
        while j < re.first_chars_i.used:
            if re.first_chars_i.data[j] == folded:
                return true
            j += 1
        var k: usize = 0
        while k < re.first_classes.used:
            let ci = re.first_classes.data[k]
            if ci >= 0:
                if es_class_has(re, (usize)ci, c):
                    return true
            elif es_class_has(re, (usize)(-1 - ci), folded):
                return true
            k += 1
    return false