Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / es_vm.lucb

#==============================================================================================
#
#   es_vm - The backtracking VM of the ECMAScript dialect
#
#   DESCRIPTION:
#       The loop of vm.lucb over the ECMAScript instructions, on the same stacks and save
#       log, following libregexp.c's lre_exec_backtrack. Counted loops keep their counter
#       and the position an iteration started at in registers (slots of `caps` after the
#       capture pairs), so backtracking restores them like captures.
#
#       A lookaround runs inline, as QuickJS's does: LOOK_START pushes a marker choice
#       point; when the body matches, LOOK_MATCH drops every choice point above the marker
#       (the lookaround is atomic) but keeps the save log, so the captures it set stay set
#       until an outer backtrack undoes them; NLOOK_MATCH instead unwinds to the marker and
#       fails. Backtracking into a negative marker means the body failed: the negative
#       lookaround succeeds and execution resumes after it.
#
#       Every `budget` steps (10000) the loop polls the host's interrupt callback.
#
#==============================================================================================

# Whether the host asks the running match to stop.
func timed_out(re: const Regex*) -> bool:
    if let f = re.check_timeout:
        return f(re.host_opaque)
    return false

## Run the ECMAScript program from `sp0`: the end position of a match, or a RUN_* code.
func es_run[S: Units](re: Regex*, src: const S*, code: const Inst[], sp0: i32, st: Stacks*) -> i32:
    var bt: usize = 0
    var log: usize = 0
    var pc: i32 = 0
    var sp: i32 = sp0
    let len = re.len
    while true:
        re.steps += 1
        if re.steps > re.budget:
            re.steps = 0
            if timed_out(re):
                return RUN_INTERRUPTED
        let inst = code[(usize)pc]
        let op = inst.op
        if op == OP_CHAR:
            if sp < len:
                let c = src.next(sp)
                if c == inst.ch:
                    sp += src.width(c)
                    pc += 1
                    continue
        elif op == OP_ASSERT:
            if es_anchor_ok(re, src, (u8)inst.x, sp):
                pc += 1
                continue
        elif op == OP_SAVE:
            if not log_set(re, st, log, inst.x, sp):
                return RUN_NO_MEMORY
            log += 1
            pc += 1
            continue
        elif op == OP_JMP:
            pc = inst.x
            continue
        elif op == OP_SPLIT:
            if not st.bt_pc.put(bt, inst.y) or not st.bt_sp.put(bt, sp) or not st.bt_log.put(bt, (i32)log):
                return RUN_NO_MEMORY
            bt += 1
            pc = inst.x
            continue
        elif op == OP_MATCH:
            return sp
        # -- ECMAScript instructions ----------------------------------------------------------
        elif op == OP_CHAR_I:
            if sp < len:
                let c = src.next(sp)
                if canon(re, c) == inst.ch:
                    sp += src.width(c)
                    pc += 1
                    continue
        elif op == OP_RANGE or op == OP_RANGE_I:
            if sp < len:
                let c = src.next(sp)
                let key = canon(re, c) if op == OP_RANGE_I else c
                if es_class_has(re, (usize)inst.x, key):
                    sp += src.width(c)
                    pc += 1
                    continue
        elif op == OP_DOT:
            if sp < len:
                let c = src.next(sp)
                if not is_line_terminator(c):
                    sp += src.width(c)
                    pc += 1
                    continue
        elif op == OP_ANY_ALL:
            if sp < len:
                sp += src.width(src.next(sp))
                pc += 1
                continue
        elif op == OP_PREV:
            if sp > 0:
                sp -= src.width(src.prev(sp))
                pc += 1
                continue
        elif op == OP_SAVE_RESET:
            var g = inst.x
            while g <= inst.y:
                if not log_set(re, st, log, 2 * g, -1) or not log_set(re, st, log + 1, 2 * g + 1, -1):
                    return RUN_NO_MEMORY
                log += 2
                g += 1
            pc += 1
            continue
        elif op == OP_SET_REG:
            if not log_set(re, st, log, inst.x, inst.y):
                return RUN_NO_MEMORY
            log += 1
            pc += 1
            continue
        elif op == OP_SET_POS:
            if not log_set(re, st, log, inst.x, sp):
                return RUN_NO_MEMORY
            log += 1
            pc += 1
            continue
        elif op == OP_CHECK_ADV:
            if re.caps[(usize)inst.x] != sp:
                pc += 1
                continue
        elif op == OP_LOOP:
            let v = re.caps[(usize)inst.x] - 1
            if not log_set(re, st, log, inst.x, v):
                return RUN_NO_MEMORY
            log += 1
            pc = inst.y if v != 0 else pc + 1
            continue
        elif op == OP_LOOP_SPLIT:
            let v = re.caps[(usize)inst.x] - 1
            if not log_set(re, st, log, inst.x, v):
                return RUN_NO_MEMORY
            log += 1
            let limit = (i32)inst.ch
            if v > limit:
                # still in the mandatory iterations
                pc = inst.y
                continue
            # an optional iteration that matched nothing fails (the minimum-th may)
            if not (inst.negate and re.caps[(usize)inst.x + 1] == sp and v != limit):
                if v == 0:
                    pc += 1
                    continue
                let alt = pc + 1 if inst.ahead else inst.y
                if not st.bt_pc.put(bt, alt) or not st.bt_sp.put(bt, sp) or not st.bt_log.put(bt, (i32)log):
                    return RUN_NO_MEMORY
                bt += 1
                pc = inst.y if inst.ahead else pc + 1
                continue
        elif op == OP_LOOK_START:
            let marker = -2 - inst.x if inst.negate else -1
            if not st.bt_pc.put(bt, marker) or not st.bt_sp.put(bt, sp) or not st.bt_log.put(bt, (i32)log):
                return RUN_NO_MEMORY
            bt += 1
            pc += 1
            continue
        elif op == OP_LOOK_MATCH:
            # drop the body's choice points and the marker; keep the captures it set
            bt -= 1
            while st.bt_pc.data[bt] >= 0:
                bt -= 1
            sp = st.bt_sp.data[bt]
            pc += 1
            continue
        elif op == OP_NLOOK_MATCH:
            # the body matched: undo it and fail
            bt -= 1
            while st.bt_pc.data[bt] >= 0:
                bt -= 1
            let ll = (usize)st.bt_log.data[bt]
            while log > ll:
                log -= 1
                re.caps[(usize)st.log_slot.data[log]] = st.log_val.data[log]
        elif op == OP_BACKREF_ES:
            let ne = es_backref_end(re, src, inst, sp)
            if ne >= 0:
                sp = ne
                pc += 1
                continue
        # Failure: resume at the newest choice point.
        while true:
            if bt == 0:
                return RUN_FAIL
            bt -= 1
            pc = st.bt_pc.data[bt]
            sp = st.bt_sp.data[bt]
            let ll = (usize)st.bt_log.data[bt]
            while log > ll:
                log -= 1
                re.caps[(usize)st.log_slot.data[log]] = st.log_val.data[log]
            if pc >= 0:
                break
            if pc <= -2:
                # a negative lookaround whose body failed: it succeeds
                pc = -2 - pc
                break
# the body of a positive lookaround failed: so does the lookaround