Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / types.lucb

#==============================================================================================
#
#   types - The compiled program, its AST nodes, and the public `Regex` type
#
#   DESCRIPTION:
#       `Regex` holds everything a compiled pattern owns: the AST while it is being
#       compiled, the instructions, the character classes, the group names and the match
#       state (captures, registers and the backtracking stacks, reused between matches).
#       Its methods are the Oniguruma dialect's API and the accessors both dialects share;
#       the work is done by the free functions of the other fragments.
#
#==============================================================================================

# mark: Structures =============================================================================

## One compiled instruction. Fields are reused across opcodes.
struct Inst:
    var op: u8 = 0
    var x: i32 = 0
    var y: i32 = 0
    var ch: u32 = 0
    var ahead: bool = true
    var negate: bool = false

## One AST node. `a` holds a group index, anchor kind, backref index, repeat minimum, or a class
## index; `b` a repeat maximum (-1 = unbounded; INT32_MAX in the ECMAScript dialect).
## Children are an index-linked list. ECMAScript nodes also carry `flags` (F_IC, F_DOTALL,
## F_MULTI), and `x`/`y`: a repeat's captures [x, y), or a backreference's group list.
struct Node:
    var kind: u8 = 0
    var ch: u32 = 0
    var a: i32 = 0
    var b: i32 = 0
    var greedy: bool = true
    var ahead: bool = true
    var negate: bool = false
    var flags: u8 = 0
    var x: i32 = 0
    var y: i32 = 0
    var first_child: i32 = -1
    var next_sibling: i32 = -1

## A compiled character class: builtin bits plus a run of inclusive (lo, hi) codepoint ranges in
## the pool. ECMAScript classes use no builtins and keep their ranges sorted and disjoint.
struct CharClass:
    var negate: bool = false
    var builtins: u32 = 0
    var range_start: usize = 0
    var range_count: usize = 0

## A lookaround subprogram (Oniguruma): its own flat instruction array ending in MATCH.
struct Program:
    var code: Inst[]
    var length: usize = 0

## A named capturing group.
struct NameEntry:
    var start: i32 = 0
    var len: i32 = 0
    var group: i32 = 0

## A slice into the codepoint name pool.
struct Span:
    var start: i32 = 0
    var len: i32 = 0

## The backtracking stacks: choice points (pc, position, save-log length) and the save log of
## overwritten capture and register slots, unwound on backtrack. A choice point whose pc is
## negative is a lookaround marker: -1 for a positive one, -2 - continuation for a negative.
struct Stacks:
    var bt_pc: Vec[i32]
    var bt_sp: Vec[i32]
    var bt_log: Vec[i32]
    var log_slot: Vec[i32]
    var log_val: Vec[i32]

    func free_all():
        self.bt_pc.free_all()
        self.bt_sp.free_all()
        self.bt_log.free_all()
        self.log_slot.free_all()
        self.log_val.free_all()

func stacks_on(heap: Heap) -> Stacks:
    return Stacks(bt_pc = Vec[i32](heap = heap), bt_sp = Vec[i32](heap = heap),
                  bt_log = Vec[i32](heap = heap), log_slot = Vec[i32](heap = heap),
                  log_val = Vec[i32](heap = heap))

# mark: The engine =============================================================================

## A compiled pattern with its last-match state. Compile once, then call `search`/`match_at`
## (native, over a codepoint subject) or `find` (over a `str`); read the result with the
## accessors. Distinct patterns use distinct `Regex` values, so their last-match state is
## independent. An ECMAScript program comes from `compile_ecmascript` instead and is matched
## with `exec8`/`exec16` (es_api.lucb).
pub struct Regex:
    # Parse/compile scratch (freed after `build`).
    var pat: Vec[u32]
    var pp: usize = 0
    var nodes: Vec[Node]
    # Flags.
    var ic: bool = false
    var ext: bool = false
    var dotall: bool = false
    var multi: bool = false
    # Groups and names.
    var ngroups: i32 = 0
    var name_cps: Vec[u32]
    var names: Vec[NameEntry]
    # Classes.
    var classes: Vec[CharClass]
    var ranges: Vec[u32]
    # Compiled program.
    var code: Vec[Inst]
    var subprogs: Vec[Program]
    var mark_count: i32 = 0
    var marks: i32[]
    var caps: i32[]
    var has_g: bool = false
    # First-character filter.
    var first_any: bool = false
    var first_chars: Vec[u32]
    var first_classes: Vec[i32]
    # Match state.
    var len: i32 = 0
    var anchor: i32 = 0
    var steps: i32 = 0
    var budget: i32 = 200000
    # Reusable stacks for the main run (an Oniguruma lookaround uses fresh local stacks).
    var stacks: Stacks
    # Buffer for the `str` convenience path.
    var text_subj: Vec[u32]
    # The ECMAScript dialect (es_api.lucb): the flags, the capture count including group 0,
    # the register count, the group names in QuickJS's layout, the backreference group
    # lists, the allocation hook and, during an exec, the interrupt callback.
    var es: bool = false
    var es_flags: i32 = 0
    var unicode: bool = false
    var ncap: i32 = 1
    var nregs: i32 = 0
    var reg_depth: i32 = 0
    var group_names: Vec[u8]
    var ref_lists: Vec[i32]
    var heap: Heap
    var check_timeout: (func(void*?) -> bool)? = none
    var host_opaque: void*? = none
    var first_chars_i: Vec[u32]

    ## Compile `pattern`. `ignore_case` starts the whole pattern case-insensitive; an inline
    ## `(?i)` has the same effect. A malformed pattern fails with `syntax_error`.
    pub func init(pattern: str, ignore_case: bool = false) -> !:
        self.pat = Vec[u32]()
        self.pp = 0
        self.nodes = Vec[Node]()
        self.ic = false
        self.ext = false
        self.dotall = false
        self.multi = false
        self.ngroups = 0
        self.name_cps = Vec[u32]()
        self.names = Vec[NameEntry]()
        self.classes = Vec[CharClass]()
        self.ranges = Vec[u32]()
        self.code = Vec[Inst]()
        self.subprogs = Vec[Program]()
        self.mark_count = 0
        var empty: i32[]
        self.marks = empty
        self.caps = empty
        self.has_g = false
        self.first_any = false
        self.first_chars = Vec[u32]()
        self.first_classes = Vec[i32]()
        self.len = 0
        self.anchor = 0
        self.steps = 0
        self.budget = 200000
        self.stacks = stacks_on(Heap())
        self.text_subj = Vec[u32]()
        self.es = false
        self.es_flags = 0
        self.unicode = false
        self.ncap = 1
        self.nregs = 0
        self.reg_depth = 0
        self.group_names = Vec[u8]()
        self.ref_lists = Vec[i32]()
        self.heap = Heap()
        self.check_timeout = none
        self.host_opaque = none
        self.first_chars_i = Vec[u32]()
        onig_build(&self, pattern, ignore_case) catch failure:
            regex_dispose(&self)
            error(failure.code, failure.message)

    ## Whether the pattern uses `\G`, whose match depends on the anchor. A caller caching a
    ## pattern's match across positions must re-run such a pattern rather than reuse the result.
    pub func uses_g() -> bool:
        return self.has_g

    ## The leftmost match at or after `offset` over `subject` (a codepoint array), or false.
    ## `anchor` is the position `\G` asserts. Sets the last-match state on success.
    pub func search(subject: const u32[], offset: i32, anchor: i32) -> bool:
        return onig_search(&self, subject, offset, anchor)

    ## A match anchored exactly at `pos` (no scanning), or false.
    pub func match_at(subject: const u32[], pos: i32, anchor: i32) -> bool:
        return onig_match_at(&self, subject, pos, anchor)

    ## The leftmost match at or after codepoint `offset` in `text`, or false. Convenience for
    ## `str` callers; decodes into a reused buffer.
    pub func find(text: str, offset: i32, anchor: i32) -> bool:
        self.text_subj.used = 0
        decode_subj(text, &self.text_subj) catch failure:
            return false
        return onig_search(&self, self.text_subj.data[..<self.text_subj.used], offset, anchor)

    # -- match accessors -----------------------------------------------------------------------

    ## The whole-match start offset (a codepoint index).
    pub func match_start() -> i32:
        return self.caps[0]

    ## The whole-match end offset (a codepoint index).
    pub func match_end() -> i32:
        return self.caps[1]

    ## The number of groups, including group 0 (the whole match).
    pub func group_count() -> i32:
        return self.ncap

    ## The start of capturing group `index`, or -1 when unset.
    pub func group_start(index: i32) -> i32:
        if index >= 0 and index < self.ncap:
            return self.caps[(usize)(2 * index)]
        return -1

    ## The end of capturing group `index`, or -1 when unset.
    pub func group_end(index: i32) -> i32:
        if index >= 0 and index < self.ncap:
            return self.caps[(usize)(2 * index + 1)]
        return -1

    ## The index of a named group, or -1 when the pattern has no such name. (For an
    ## ECMAScript program with a duplicated name, the first group of that name.)
    pub func group_of(name: str) -> i32:
        if self.es:
            return es_group_of(&self, name)
        var query = Vec[u32]()
        decode_subj(name, &query) catch failure:
            query.free_all()
            return -1
        var result: i32 = -1
        var i: usize = 0
        while i < self.names.used and result < 0:
            let entry = self.names.data[i]
            if (usize)entry.len == query.used and pool_eq(&self, entry.start, query):
                result = entry.group
            i += 1
        query.free_all()
        return result

    # -- teardown ------------------------------------------------------------------------------

    ## Release every allocation the pattern holds. (An ECMAScript program is released with
    ## `free_ecmascript`, which also frees the `Regex` itself.)
    pub func close():
        regex_dispose(&self)

    static func own(native: Regex*) -> interop.Reference[Regex]!:
        return try interop.Reference[Regex].adopt(native, regex_type)

## The interop type of a compiled `Regex`.
pub let regex_type: interop.Type[Regex] = interop.Type[Regex]("regex", Regex.close, closeable = true)

## Compile `pattern` into an owned reference. `ignore_case` starts it case-insensitive.
pub func compile(pattern: str, ignore_case: bool = false) -> interop.Reference[Regex]!:
    let native = try new Regex(pattern, ignore_case)
    return try Regex.own(native)

func pool_eq(re: const Regex*, start: i32, query: Vec[u32]) -> bool:
    var i: usize = 0
    while i < query.used:
        if re.name_cps.data[(usize)start + i] != query.data[i]:
            return false
        i += 1
    return true

func regex_dispose(re: Regex*):
    re.pat.free_all()
    re.nodes.free_all()
    re.name_cps.free_all()
    re.names.free_all()
    re.classes.free_all()
    re.ranges.free_all()
    re.code.free_all()
    var i: usize = 0
    while i < re.subprogs.used:
        let prog = re.subprogs.data[i]
        if prog.code.length > 0:
            free(prog.code) in memory.heap
        i += 1
    re.subprogs.free_all()
    re.first_chars.free_all()
    re.first_classes.free_all()
    re.first_chars_i.free_all()
    re.stacks.free_all()
    re.text_subj.free_all()
    re.group_names.free_all()
    re.ref_lists.free_all()
    heap_free[i32](&re.heap, re.marks)
    heap_free[i32](&re.heap, re.caps)
    var empty: i32[]
    re.marks = empty
    re.caps = empty

## Decode `text` into a codepoint array. Invalid bytes pass through as their own value.
pub func decode_subj(text: str, out: Vec[u32]*) -> !:
    let bytes = text.bytes
    var offset: usize = 0
    while offset < bytes.length:
        if let decoded = utf8.decode(bytes, offset):
            _ = try out.push((u32)decoded.scalar)
            offset += decoded.width
        else:
            _ = try out.push((u32)bytes[offset])
            offset += 1