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