Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / onig_match.lucb

#==============================================================================================
#
#   onig_match - Oniguruma matching: the search loop and the character tests
#
#   DESCRIPTION:
#       The search runs the program at each start position the first-character filter
#       admits. `^` and `$` are line anchors, as in Oniguruma / Ruby (the flavour TextMate
#       grammars target). Case-insensitive matching is ASCII case swapping. A lookaround runs
#       its subprogram on fresh stacks and discards the captures it set; a lookbehind tries
#       the start positions up to 256 back that end exactly at the current position.
#
#==============================================================================================

# mark: Search =================================================================================

func onig_search(re: Regex*, subject: const u32[], offset: i32, anchor: i32) -> bool:
    let src = CodePoints(data = subject)
    re.len = (i32)subject.length
    re.anchor = anchor
    var at = offset
    while at <= re.len:
        if not re.first_any:
            if at >= re.len or not first_ok(re, subject[(usize)at]):
                at += 1
                continue
        onig_reset(re)
        let end = run_prog(re, &src, re.code.data[..<re.code.used], at, -1, &re.stacks)
        if end >= 0:
            re.caps[0] = at
            re.caps[1] = end
            return true
        if end == RUN_NO_MEMORY:
            trap("out of memory in regex vm")
        at += 1
    return false

func onig_match_at(re: Regex*, subject: const u32[], pos: i32, anchor: i32) -> bool:
    let src = CodePoints(data = subject)
    re.len = (i32)subject.length
    re.anchor = anchor
    onig_reset(re)
    let end = run_prog(re, &src, re.code.data[..<re.code.used], pos, -1, &re.stacks)
    if end >= 0:
        re.caps[0] = pos
        re.caps[1] = end
        return true
    if end == RUN_NO_MEMORY:
        trap("out of memory in regex vm")
    return false

func onig_reset(re: Regex*):
    re.steps = 0
    var i: usize = 0
    while i < re.caps.length:
        re.caps[i] = -1
        i += 1

## A lookaround: run its subprogram (captures are discarded), possibly negated.
func onig_run_look[S: Units](re: Regex*, src: const S*, inst: Inst, sp: i32) -> bool:
    let prog = re.subprogs.data[(usize)inst.x]
    var snap = Vec[i32]()
    var s: usize = 0
    while s < re.caps.length:
        _ = snap.push(re.caps[s]) catch failure: trap("out of memory in regex vm")
        s += 1
    var st = stacks_on(Heap())
    var ok = false
    if inst.ahead:
        let r = run_prog(re, src, prog.code[..<prog.length], sp, -1, &st)
        if r == RUN_NO_MEMORY:
            trap("out of memory in regex vm")
        ok = r >= 0
    else:
        let limit: i32 = sp - 256 if sp > 256 else 0
        var pos = sp
        while pos >= limit:
            let r = run_prog(re, src, prog.code[..<prog.length], pos, sp, &st)
            if r == RUN_NO_MEMORY:
                trap("out of memory in regex vm")
            if r >= 0:
                ok = true
                break
            pos -= 1
    var r: usize = 0
    while r < re.caps.length:
        re.caps[r] = snap.data[r]
        r += 1
    snap.free_all()
    st.free_all()
    if inst.negate:
        return not ok
    return ok

## Match a backreference at `sp`: the new position on success, or -1. An unset group matches
## the empty string.
func backref_end[S: Units](re: const Regex*, src: const S*, idx: i32, sp: i32) -> i32:
    let ei = 2 * idx + 1
    if idx < 0 or ei >= 2 * re.ncap:
        return sp
    let cs = re.caps[(usize)(2 * idx)]
    let ce = re.caps[(usize)ei]
    if cs < 0 or ce < 0:
        return sp
    let n = ce - cs
    if sp + n > re.len:
        return -1
    var k: i32 = 0
    while k < n:
        if not eq(re, src.next(sp + k), src.next(cs + k)):
            return -1
        k += 1
    return sp + n

# mark: Character tests ========================================================================

func eq(re: const Regex*, a: u32, b: u32) -> bool:
    if a == b:
        return true
    if re.ic:
        return swapcase(a) == b
    return false

func class_ok(re: const Regex*, ci: usize, ch: u32) -> bool:
    let cls = re.classes.data[ci]
    return class_hit(re, cls, ch) != cls.negate

func class_hit(re: const Regex*, cls: CharClass, ch: u32) -> bool:
    let b = cls.builtins
    if (b & B_d) != 0 and is_digit(ch):
        return true
    if (b & B_D) != 0 and not is_digit(ch):
        return true
    if (b & B_w) != 0 and is_word(ch):
        return true
    if (b & B_W) != 0 and not is_word(ch):
        return true
    if (b & B_s) != 0 and is_space(ch):
        return true
    if (b & B_S) != 0 and not is_space(ch):
        return true
    if (b & B_h) != 0 and is_hex(ch):
        return true
    if (b & B_H) != 0 and not is_hex(ch):
        return true
    var j: usize = 0
    while j < cls.range_count:
        let lo = re.ranges.data[cls.range_start + 2 * j]
        let hi = re.ranges.data[cls.range_start + 2 * j + 1]
        if in_range(re, ch, lo, hi):
            return true
        j += 1
    return false

func in_range(re: const Regex*, ch: u32, lo: u32, hi: u32) -> bool:
    if lo <= ch and ch <= hi:
        return true
    if re.ic:
        let s = swapcase(ch)
        if s != ch and lo <= s and s <= hi:
            return true
    return false

func anchor_ok[S: Units](re: const Regex*, src: const S*, kind: u8, pos: i32) -> bool:
    # `^` and `$` are line anchors, as in Oniguruma / Ruby (the flavour TextMate grammars target):
    # they match at every line boundary, not only at the ends of the subject. The tokenizer feeds
    # one line at a time (with its trailing newline), so `$` also matches just before that newline.
    if kind == AN_BOL:
        return pos == 0 or (pos > 0 and src.prev(pos) == (u32)'\n')
    if kind == AN_EOL:
        return pos == re.len or (pos < re.len and src.next(pos) == (u32)'\n')
    if kind == AN_WORDB:
        return word_at(re, src, pos - 1) != word_at(re, src, pos)
    if kind == AN_NWORDB:
        return word_at(re, src, pos - 1) == word_at(re, src, pos)
    if kind == AN_BUFS:
        return pos == 0
    if kind == AN_G:
        return pos == re.anchor
    if kind == AN_BUFE:
        return pos == re.len
    return false

func word_at[S: Units](re: const Regex*, src: const S*, i: i32) -> bool:
    return i >= 0 and i < re.len and is_word(src.next(i))

func is_builtin(c: u32) -> bool:
    return c == (u32)'d' or c == (u32)'D' or c == (u32)'w' or c == (u32)'W' or c == (u32)'s' or c == (u32)'S' or c == (u32)'h' or c == (u32)'H'

func builtin_bit(c: u32) -> u32:
    if c == (u32)'d':
        return B_d
    if c == (u32)'D':
        return B_D
    if c == (u32)'w':
        return B_w
    if c == (u32)'W':
        return B_W
    if c == (u32)'s':
        return B_s
    if c == (u32)'S':
        return B_S
    if c == (u32)'h':
        return B_h
    return B_H

func is_digit(ch: u32) -> bool:
    return ch >= (u32)'0' and ch <= (u32)'9'

func is_word(ch: u32) -> bool:
    return is_digit(ch) or (ch >= (u32)'a' and ch <= (u32)'z') or (ch >= (u32)'A' and ch <= (u32)'Z') or ch == (u32)'_'

func is_space(ch: u32) -> bool:
    return ch == (u32)' ' or ch == (u32)'\t' or ch == (u32)'\n' or ch == (u32)'\r' or ch == 11 or ch == 12

func is_hex(ch: u32) -> bool:
    return is_digit(ch) or (ch >= (u32)'a' and ch <= (u32)'f') or (ch >= (u32)'A' and ch <= (u32)'F')

func hex_digit(cp: u32) -> i32:
    if cp >= (u32)'0' and cp <= (u32)'9':
        return (i32)(cp - (u32)'0')
    if cp >= (u32)'a' and cp <= (u32)'f':
        return (i32)(cp - (u32)'a') + 10
    if cp >= (u32)'A' and cp <= (u32)'F':
        return (i32)(cp - (u32)'A') + 10
    return 0

func swapcase(ch: u32) -> u32:
    if ch >= (u32)'A' and ch <= (u32)'Z':
        return ch + 32
    if ch >= (u32)'a' and ch <= (u32)'z':
        return ch - 32
    return ch