Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / es_compile.lucb

#==============================================================================================
#
#   es_compile - The ECMAScript compiler: AST to instructions
#
#   DESCRIPTION:
#       Compiles the AST of es_parse.lucb the way libregexp.c emits bytecode as it parses.
#       Inside a lookbehind the body is compiled backward, as in QuickJS: the terms of a
#       concatenation are reversed, a character test is wrapped in PREV ... PREV (step back,
#       test forward, step back again), a group saves its end before its start and a
#       backreference compares backward.
#
#       A quantifier gets QuickJS's loop layout (re_parse_term's quantifier section): a
#       SPLIT loop for ?, * and +, or a counter register for counted repeats; the captures of
#       the atom are reset at each iteration (SAVE_RESET) unless the atom always sets them;
#       and an optional iteration must advance (the ES empty check) unless the atom always
#       consumes a character. Registers are allocated as a stack, one level per nested loop.
#
#==============================================================================================

# mark: Emission ===============================================================================

func emit(out: Vec[Inst]*, op: u8, x: i32, y: i32) -> usize!:
    var inst = Inst(op = op)
    inst.x = x
    inst.y = y
    return try out.push(inst)

func es_char_op(out: Vec[Inst]*, op: u8, x: i32, ch: u32, backward: bool) -> !:
    if backward:
        _ = try emit(out, OP_PREV, 0, 0)
    var inst = Inst(op = op)
    inst.x = x
    inst.ch = ch
    _ = try out.push(inst)
    if backward:
        _ = try emit(out, OP_PREV, 0, 0)

func es_compile(re: Regex*, ni: i32, out: Vec[Inst]*, backward: bool) -> !:
    let node = re.nodes.data[(usize)ni]
    let kind = node.kind
    let ic = (node.flags & F_IC) != 0
    if kind == K_CHAR:
        try es_char_op(out, OP_CHAR_I if ic else OP_CHAR, 0, node.ch, backward)
    elif kind == K_ANY:
        try es_char_op(out, OP_ANY_ALL if (node.flags & F_DOTALL) != 0 else OP_DOT, 0, 0, backward)
    elif kind == K_CLASS:
        try es_char_op(out, OP_RANGE_I if ic else OP_RANGE, node.a, 0, backward)
    elif kind == K_ANCHOR:
        _ = try emit(out, OP_ASSERT, node.a, 0)
    elif kind == K_CONCAT:
        if not backward:
            var child = node.first_child
            while child != -1:
                try es_compile(re, child, out, backward)
                child = re.nodes.data[(usize)child].next_sibling
        else:
            # the terms in reverse order
            var children = Vec[i32](heap = re.heap)
            defer children.free_all()
            var child = node.first_child
            while child != -1:
                _ = try children.push(child)
                child = re.nodes.data[(usize)child].next_sibling
            var k = children.used
            while k > 0:
                k -= 1
                try es_compile(re, children.data[k], out, backward)
    elif kind == K_ALT:
        try es_compile_alt(re, ni, out, backward)
    elif kind == K_GROUP:
        if node.a == 0:
            try es_compile(re, node.first_child, out, backward)
        else:
            let first = 2 * node.a + (1 if backward else 0)
            let second = 2 * node.a + (0 if backward else 1)
            _ = try emit(out, OP_SAVE, first, 0)
            try es_compile(re, node.first_child, out, backward)
            _ = try emit(out, OP_SAVE, second, 0)
    elif kind == K_REPEAT:
        try es_compile_repeat(re, ni, out, backward)
    elif kind == K_BACKREF:
        var inst = Inst(op = OP_BACKREF_ES)
        inst.x = node.x
        inst.y = node.y
        inst.ch = (1 if ic else 0) | (2 if backward else 0)
        _ = try out.push(inst)
    elif kind == K_LOOK:
        let start = try emit(out, OP_LOOK_START, 0, 0)
        out.data[start].negate = node.negate
        try es_compile(re, node.first_child, out, not node.ahead)
        _ = try emit(out, OP_NLOOK_MATCH if node.negate else OP_LOOK_MATCH, 0, 0)
        out.data[start].x = (i32)out.used

# K_EMPTY emits nothing.

func es_compile_alt(re: Regex*, ni: i32, out: Vec[Inst]*, backward: bool) -> !:
    let node = re.nodes.data[(usize)ni]
    var jumps = Vec[i32](heap = re.heap)
    defer jumps.free_all()
    var child = node.first_child
    while child != -1:
        let nxt = re.nodes.data[(usize)child].next_sibling
        if nxt != -1:
            let si = try emit(out, OP_SPLIT, 0, 0)
            out.data[si].x = (i32)out.used
            try es_compile(re, child, out, backward)
            let ji = try emit(out, OP_JMP, 0, 0)
            _ = try jumps.push((i32)ji)
            out.data[si].y = (i32)out.used
        else:
            try es_compile(re, child, out, backward)
        child = nxt
    let end = (i32)out.used
    var k: usize = 0
    while k < jumps.used:
        out.data[(usize)jumps.data[k]].x = end
        k += 1

# mark: Quantifiers ============================================================================

func is_reg_op(op: u8) -> bool:
    return op == OP_SET_REG or op == OP_SET_POS or op == OP_CHECK_ADV or op == OP_LOOP or op == OP_LOOP_SPLIT

# Append `body` to `out`, moving its jump targets by where it lands and its registers by
# `reg_delta`.
func append_code(out: Vec[Inst]*, body: const Vec[Inst]*, reg_delta: i32) -> !:
    let off = (i32)out.used
    var i: usize = 0
    while i < body.used:
        var inst = body.data[i]
        let op = inst.op
        if op == OP_JMP or op == OP_LOOK_START:
            inst.x += off
        elif op == OP_SPLIT:
            inst.x += off
            inst.y += off
        elif op == OP_LOOP or op == OP_LOOP_SPLIT:
            inst.y += off
        if is_reg_op(op):
            inst.x += reg_delta
        _ = try out.push(inst)
        i += 1

# re_need_check_adv_and_capture_init: whether an iteration of the atom may match nothing
# (false when a character test comes before any control flow), and whether its captures
# must be reset at each iteration (true unless the atom sets them all unconditionally).
func atom_analysis(body: const Vec[Inst]*) -> (bool, bool):
    var need_check_adv = true
    var need_capture_init = false
    var i: usize = 0
    while i < body.used:
        let op = body.data[i].op
        let consumes = op == OP_CHAR or op == OP_CHAR_I or op == OP_DOT or op == OP_ANY_ALL or op == OP_RANGE or op == OP_RANGE_I
        # instructions with no effect on either question
        let neutral = op == OP_ASSERT or op == OP_SET_REG or op == OP_SET_POS or op == OP_PREV or op == OP_SAVE or op == OP_SAVE_RESET
        if consumes:
            need_check_adv = false
        elif op == OP_BACKREF_ES:
            need_capture_init = true
        elif not neutral:
            # safe behavior: we cannot predict the outcome
            need_capture_init = true
            break
        i += 1
    return (need_check_adv, need_capture_init)

func es_compile_repeat(re: Regex*, ni: i32, out: Vec[Inst]*, backward: bool) -> !:
    let node = re.nodes.data[(usize)ni]
    let quant_min = node.a
    let quant_max = node.b
    let greedy = node.greedy
    let has_caps = node.y > node.x
    # the atom, compiled with room for this level's two registers below its own
    let base = re.reg_depth
    var body = Vec[Inst](heap = re.heap)
    defer body.free_all()
    re.reg_depth = base + 2
    try es_compile(re, node.first_child, &body, backward)
    re.reg_depth = base
    let analysis = atom_analysis(&body)
    var check = analysis.0
    let need_capture_init = analysis.1
    let reset_inside = need_capture_init and has_caps
    let reg0 = 2 * re.ncap + base

    if quant_min == 0:
        # reset the captures once in case the atom is not executed
        if not need_capture_init and has_caps:
            _ = try emit(out, OP_SAVE_RESET, node.x, node.y - 1)
        if quant_max == 0:
            return
        if quant_max == 1 or quant_max == INT32_MAX:
            let split_at = try emit(out, OP_SPLIT, 0, 0)
            let body_start = (i32)out.used
            if check:
                _ = try emit(out, OP_SET_POS, reg0, 0)
            if reset_inside:
                _ = try emit(out, OP_SAVE_RESET, node.x, node.y - 1)
            try append_code(out, &body, (1 if check else 0) - 2)
            if check:
                _ = try emit(out, OP_CHECK_ADV, reg0, 0)
            if quant_max == INT32_MAX:
                _ = try emit(out, OP_JMP, (i32)split_at, 0)
            try patch_split(out, split_at, body_start, (i32)out.used, greedy)
        else:
            let split_at = try emit(out, OP_SPLIT, 0, 0)
            let next = (i32)out.used
            _ = try emit(out, OP_SET_REG, reg0, quant_max)
            let loop_top = try emit_counted_body(out, &body, reg0, check, reset_inside, node)
            try emit_loop_split(out, reg0, loop_top, quant_max, greedy, check)
            try patch_split(out, split_at, next, (i32)out.used, greedy)
    elif quant_min == 1 and quant_max == INT32_MAX and not check:
        let top = (i32)out.used
        if reset_inside:
            _ = try emit(out, OP_SAVE_RESET, node.x, node.y - 1)
        try append_code(out, &body, -2)
        let split_at = try emit(out, OP_SPLIT, 0, 0)
        try patch_split(out, split_at, top, (i32)out.used, greedy)
    else:
        if quant_min == quant_max:
            check = false
        _ = try emit(out, OP_SET_REG, reg0, quant_max)
        let loop_top = try emit_counted_body(out, &body, reg0, check, reset_inside, node)
        if quant_min == quant_max:
            # a simple loop is enough
            _ = try emit(out, OP_LOOP, reg0, loop_top)
        else:
            try emit_loop_split(out, reg0, loop_top, quant_max - quant_min, greedy, check)

# The body of a counted loop (counter in `reg0`, start position in `reg0 + 1` when
# checking); answers the loop's top.
func emit_counted_body(out: Vec[Inst]*, body: const Vec[Inst]*, reg0: i32, check: bool,
                       reset_inside: bool, node: Node) -> i32!:
    let loop_top = (i32)out.used
    if check:
        _ = try emit(out, OP_SET_POS, reg0 + 1, 0)
    if reset_inside:
        _ = try emit(out, OP_SAVE_RESET, node.x, node.y - 1)
    try append_code(out, body, (2 if check else 1) - 2)
    return loop_top

# The LOOP_SPLIT closing a counted body.
func emit_loop_split(out: Vec[Inst]*, reg0: i32, loop_top: i32, limit: i32, greedy: bool, check: bool) -> !:
    let li = try emit(out, OP_LOOP_SPLIT, reg0, loop_top)
    out.data[li].ch = (u32)limit
    out.data[li].ahead = greedy
    out.data[li].negate = check

# A SPLIT preferring `body` when greedy, `exit` otherwise.
func patch_split(out: Vec[Inst]*, split_at: usize, body: i32, exit: i32, greedy: bool) -> !:
    if greedy:
        out.data[split_at].x = body
        out.data[split_at].y = exit
    else:
        out.data[split_at].x = exit
        out.data[split_at].y = body

# The number of registers the program uses (compute_register_count).
func es_register_count(re: const Regex*) -> i32:
    var top: i32 = 0
    let first = 2 * re.ncap
    var i: usize = 0
    while i < re.code.used:
        let inst = re.code.data[i]
        if is_reg_op(inst.op):
            var used = inst.x - first + 1
            if inst.op == OP_LOOP_SPLIT and inst.negate:
                used += 1
            if used > top:
                top = used
        i += 1
    return top