Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / onig_compile.lucb

#==============================================================================================
#
#   onig_compile - The Oniguruma compiler: AST to instructions, and the first-character filter
#
#   DESCRIPTION:
#       Counted repeats are unrolled; an unbounded repeat loops through a MARK/PROGRESS pair
#       that stops an iteration that matched nothing. A lookaround becomes a subprogram run
#       on its own stacks. The first-character filter lists the characters and classes a
#       match can start with, so the search skips positions that cannot start one.
#
#==============================================================================================

# mark: Compiler ===============================================================================

func compile_node(re: Regex*, ni: i32, out: Vec[Inst]*) -> !:
    let node = re.nodes.data[(usize)ni]
    let kind = node.kind
    if kind == K_CHAR:
        var inst = Inst(op = OP_CHAR)
        inst.ch = node.ch
        _ = try out.push(inst)
    elif kind == K_ANY:
        _ = try out.push(Inst(op = OP_ANY))
    elif kind == K_CLASS:
        var inst = Inst(op = OP_CLASS)
        inst.x = node.a
        _ = try out.push(inst)
    elif kind == K_ANCHOR:
        var inst = Inst(op = OP_ASSERT)
        inst.x = node.a
        _ = try out.push(inst)
    elif kind == K_CONCAT:
        var child = node.first_child
        while child != -1:
            try compile_node(re, child, out)
            child = re.nodes.data[(usize)child].next_sibling
    elif kind == K_ALT:
        try compile_alt(re, ni, out)
    elif kind == K_GROUP:
        if node.a == 0:
            try compile_node(re, node.first_child, out)
        else:
            var open = Inst(op = OP_SAVE)
            open.x = 2 * node.a
            _ = try out.push(open)
            try compile_node(re, node.first_child, out)
            var shut = Inst(op = OP_SAVE)
            shut.x = 2 * node.a + 1
            _ = try out.push(shut)
    elif kind == K_REPEAT:
        try compile_repeat(re, ni, out)
    elif kind == K_BACKREF:
        var inst = Inst(op = OP_BACKREF)
        inst.x = node.a
        _ = try out.push(inst)
    elif kind == K_LOOK:
        var sub = Vec[Inst]()
        try compile_node(re, node.first_child, &sub)
        _ = try sub.push(Inst(op = OP_MATCH))
        let plen = sub.used
        let arr = try new Inst[plen] --- in memory.heap
        var i: usize = 0
        while i < plen:
            arr[i] = sub.data[i]
            i += 1
        sub.free_all()
        var prog = Program()
        prog.code = arr
        prog.length = plen
        let sidx = try re.subprogs.push(prog)
        var inst = Inst(op = OP_LOOK)
        inst.x = (i32)sidx
        inst.ahead = node.ahead
        inst.negate = node.negate
        _ = try out.push(inst)

# K_EMPTY and anything else emit nothing.

func compile_alt(re: Regex*, ni: i32, out: Vec[Inst]*) -> !:
    let node = re.nodes.data[(usize)ni]
    var jumps = Vec[i32]()
    var child = node.first_child
    while child != -1:
        let nxt = re.nodes.data[(usize)child].next_sibling
        if nxt != -1:
            let si = try out.push(Inst(op = OP_SPLIT))
            out.data[si].x = (i32)out.used
            try compile_node(re, child, out)
            let ji = try out.push(Inst(op = OP_JMP))
            _ = try jumps.push((i32)ji)
            out.data[si].y = (i32)out.used
        else:
            try compile_node(re, child, out)
        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
    jumps.free_all()

func compile_repeat(re: Regex*, ni: i32, out: Vec[Inst]*) -> !:
    let node = re.nodes.data[(usize)ni]
    let child = node.first_child
    let lo = node.a
    let hi = node.b
    var i: i32 = 0
    while i < lo:
        try compile_node(re, child, out)
        i += 1
    if hi < 0:
        let mi = try out.push(Inst(op = OP_MARK))
        let slot = re.mark_count
        re.mark_count += 1
        out.data[mi].x = slot
        let loop_top = (i32)mi
        let si = try out.push(Inst(op = OP_SPLIT))
        if node.greedy:
            out.data[si].x = (i32)out.used
        else:
            out.data[si].y = (i32)out.used
        try compile_node(re, child, out)
        var guard = Inst(op = OP_PROGRESS)
        guard.x = slot
        _ = try out.push(guard)
        var jump = Inst(op = OP_JMP)
        jump.x = loop_top
        _ = try out.push(jump)
        if node.greedy:
            out.data[si].y = (i32)out.used
        else:
            out.data[si].x = (i32)out.used
    else:
        var splits = Vec[i32]()
        var k: i32 = 0
        while k < hi - lo:
            let si = try out.push(Inst(op = OP_SPLIT))
            _ = try splits.push((i32)si)
            if node.greedy:
                out.data[si].x = (i32)out.used
            else:
                out.data[si].y = (i32)out.used
            try compile_node(re, child, out)
            k += 1
        let end = (i32)out.used
        var j: usize = 0
        while j < splits.used:
            let si = (usize)splits.data[j]
            if node.greedy:
                out.data[si].y = end
            else:
                out.data[si].x = end
            j += 1
        splits.free_all()

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

func compute_first(re: Regex*) -> !:
    let plen = re.code.used
    let seen = try new bool[plen] --- in memory.heap
    var i: usize = 0
    while i < plen:
        seen[i] = false
        i += 1
    var stack = Vec[i32]()
    _ = try stack.push(0)
    var bail = false
    while stack.used > 0 and not bail:
        let pc = stack.data[stack.used - 1]
        stack.used -= 1
        if pc < 0 or (usize)pc >= plen or seen[(usize)pc]:
            continue
        seen[(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_MARK or op == OP_PROGRESS:
            _ = 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:
            if not first_has(re, inst.ch):
                _ = try re.first_chars.push(inst.ch)
        elif op == OP_CLASS:
            _ = try re.first_classes.push(inst.x)
        else:
            re.first_any = true
            bail = true
    free(seen) in memory.heap
    stack.free_all()

func first_has(re: const Regex*, cp: u32) -> bool:
    var i: usize = 0
    while i < re.first_chars.used:
        if re.first_chars.data[i] == cp:
            return true
        i += 1
    return false

func first_ok(re: const Regex*, ch: u32) -> bool:
    var i: usize = 0
    while i < re.first_chars.used:
        if eq(re, ch, re.first_chars.data[i]):
            return true
        i += 1
    var j: usize = 0
    while j < re.first_classes.used:
        if class_ok(re, (usize)re.first_classes.data[j], ch):
            return true
        j += 1
    return false