Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / unicode / char_range.lucb

#==============================================================================================
#
#   char_range - Character ranges: storage, set operations and regexp canonicalization
#
#   DESCRIPTION:
#       Port of QuickJS libunicode.c lines 379-759: cr_init, cr_free, cr_realloc, cr_copy,
#       cr_compress, cr_op, cr_op1, cr_invert, unicode_case1, cr_regexp_canonicalize, and
#       the ID_Start / ID_Continue predicates that open the CONFIG_ALL_UNICODE section.
#
#==============================================================================================

# mark: Storage ================================================================================

# character range

import memory

func cr_default_realloc(opaque: void*?, ptr: void*?, size: usize) -> void*?:
    return c_realloc(ptr, size)

## Initialise `cr` empty, growing with `realloc_func(mem_opaque, ...)`, or C `realloc` when
## none.
pub func cr_init(cr: CharRange*, mem_opaque: void*?, realloc_func: ReallocFunc?):
    cr.len = 0
    cr.size = 0
    cr.points = none
    cr.mem_opaque = mem_opaque
    cr.realloc_func = realloc_func else cr_default_realloc

## Release the storage of `cr`.
pub func cr_free(cr: CharRange*):
    let realloc_func = cr.realloc_func else trap("cr_free: cr_init was not called")
    _ = realloc_func(cr.mem_opaque, cr.points, 0)

## Make room for `size` points (growing by at least half); 0, or -1 when it cannot grow.
pub func cr_realloc(cr: CharRange*, size: i32) -> i32:
    if size > cr.size:
        let new_size = max_int(size, cr.size * 3 // 2)
        let realloc_func = cr.realloc_func else trap("cr_realloc: cr_init was not called")
        let new_buf = realloc_func(cr.mem_opaque, cr.points,
                                   (usize)new_size * memory.size_of(u32)) else return -1
        cr.points = (u32*)new_buf
        cr.size = new_size
    return 0

## Replace the contents of `cr` with those of `cr1`; 0, or -1 when it cannot grow.
pub func cr_copy(cr: CharRange*, cr1: const CharRange*) -> i32:
    if cr_realloc(cr, cr1.len) != 0:
        return -1
    _ = memcpy(cr.points, cr1.points,
               memory.size_of(u32) * (usize)cr1.len)
    cr.len = cr1.len
    return 0

# merge consecutive intervals and remove empty intervals
func cr_compress(cr: CharRange*):
    let pt = cr_points(cr)
    let len = pt.length
    var i: usize = 0
    var j: usize = 0
    var k: usize = 0
    while (i + 1) < len:
        if pt[i] == pt[i + 1]:
            # empty interval
            i += 2
        else:
            j = i
            while (j + 3) < len and pt[j + 1] == pt[j + 2]:
                j += 2
            # just copy
            pt[k] = pt[i]
            pt[k + 1] = pt[j + 1]
            k += 2
            i = j + 2
    cr.len = (i32)k

# mark: Set operations =========================================================================

# union or intersection
## Append to `cr` (initialised, normally empty) the result of `op` on the ranges `a_pt` and
## `b_pt`, then merge adjacent intervals; 0, or -1 when it cannot grow. Neither span may
## point into `cr`'s own storage.
pub func cr_op(cr: CharRange*, a_pt: const u32[], b_pt: const u32[], op: CharRangeOpEnum) -> i32:
    let a_len = a_pt.length
    let b_len = b_pt.length
    var a_idx: usize = 0
    var b_idx: usize = 0
    while true:
        # get one more point from a or b in increasing order
        var v: u32 = 0
        if a_idx < a_len and b_idx < b_len:
            if a_pt[a_idx] < b_pt[b_idx]:
                v = a_pt[a_idx]
                a_idx += 1
            elif a_pt[a_idx] == b_pt[b_idx]:
                v = a_pt[a_idx]
                a_idx += 1
                b_idx += 1
            else:
                v = b_pt[b_idx]
                b_idx += 1
        elif a_idx < a_len:
            v = a_pt[a_idx]
            a_idx += 1
        elif b_idx < b_len:
            v = b_pt[b_idx]
            b_idx += 1
        else:
            break
        # add the point if the in/out status changes
        let a_in = (i32)(a_idx & 1)
        let b_in = (i32)(b_idx & 1)
        var is_in: i32 = 0
        if op == cr_op_union:
            is_in = a_in | b_in
        elif op == cr_op_inter:
            is_in = a_in & b_in
        elif op == cr_op_xor:
            is_in = a_in ^ b_in
        elif op == cr_op_sub:
            is_in = a_in & (b_in ^ 1)
        else:
            trap("cr_op: invalid operation")
        if is_in != (cr.len & 1):
            if cr_add_point(cr, v) != 0:
                return -1
    cr_compress(cr)
    return 0

## Replace `cr` with the result of `op` on `cr` and `b_pt`; 0, or -1 when it cannot grow.
pub func cr_op1(cr: CharRange*, b_pt: const u32[], op: CharRangeOpEnum) -> i32:
    var a = *cr
    cr.len = 0
    cr.size = 0
    cr.points = none
    let ret = cr_op(cr, cr_points(&a), b_pt, op)
    cr_free(&a)
    return ret

## Replace `cr` with its complement over [0, UINT32_MAX); 0, or -1 when it cannot grow.
pub func cr_invert(cr: CharRange*) -> i32:
    let len = cr.len
    if cr_realloc(cr, len + 2) != 0:
        return -1
    let points = cr.points else trap("cr_invert: no storage")
    _ = memmove(points + 1, points, (usize)len * memory.size_of(u32))
    points[0] = 0
    points[(usize)len + 1] = 0xffffffff
    cr.len = len + 2
    cr_compress(cr)
    return 0

# mark: Case ranges ============================================================================

let case_u: i32 = 1 << 0
let case_l: i32 = 1 << 1
let case_f: i32 = 1 << 2

func mr(run_type: RunType) -> u32:
    return 1u32 << (u32)run_type

# use the case conversion table to generate range of characters.
#    CASE_U: set char if modified by uppercasing,
#    CASE_L: set char if modified by lowercasing,
#    CASE_F: set char if modified by case folding,
func unicode_case1(cr: CharRange*, case_mask: i32) -> i32:
    let tab_run_mask: u32[3] = [
        mr(.u) | mr(.uf) | mr(.ul) | mr(.lsu) | mr(.u2l_399_ext2) | mr(.uf_d20) | mr(.uf_d1_ext) | mr(.u_ext) | mr(.uf_ext2) | mr(.uf_ext3),
        mr(.l) | mr(.lf) | mr(.ul) | mr(.lsu) | mr(.u2l_399_ext2) | mr(.lf_ext) | mr(.lf_ext2),
        mr(.uf) | mr(.lf) | mr(.ul) | mr(.lsu) | mr(.u2l_399_ext2) | mr(.lf_ext) | mr(.lf_ext2) | mr(.uf_d20) | mr(.uf_d1_ext) | mr(.lf_ext) | mr(.uf_ext2) | mr(.uf_ext3),
    ]
    if case_mask == 0:
        return 0
    var mask: u32 = 0
    for i: i32 in 0..<3:
        if ((case_mask >> i) & 1) != 0:
            mask |= tab_run_mask[(usize)i]
    for idx in 0..<case_conv_table1.length:
        let v = case_conv_table1[idx]
        let run_type = (v >> (32 - 17 - 7 - 4)) & 0xf
        var code = v >> (32 - 17)
        let len = (v >> (32 - 17 - 7)) & 0x7f
        if ((mask >> run_type) & 1) != 0:
            # the C `goto def_case` from the UL and LSU cases
            var def_case = false
            match (RunType)run_type:
                .ul:
                    if (case_mask & case_u) != 0 and (case_mask & (case_l | case_f)) != 0:
                        def_case = true
                    else:
                        code += (u32)((case_mask & case_u) != 0)
                        var i: u32 = 0
                        while i < len:
                            if cr_add_interval(cr, code + i, code + i + 1) != 0:
                                return -1
                            i += 2
                .lsu:
                    if (case_mask & case_u) != 0 and (case_mask & (case_l | case_f)) != 0:
                        def_case = true
                    else:
                        if (case_mask & case_u) == 0:
                            if cr_add_interval(cr, code, code + 1) != 0:
                                return -1
                        if cr_add_interval(cr, code + 1, code + 2) != 0:
                            return -1
                        if (case_mask & case_u) != 0:
                            if cr_add_interval(cr, code + 2, code + 3) != 0:
                                return -1
                _:
                    def_case = true
            if def_case:
                if cr_add_interval(cr, code, code + len) != 0:
                    return -1
    return 0

func cr_sort_and_remove_overlap(cr: CharRange*):
    # the resulting ranges are not necessarily sorted and may overlap
    if let points = cr.points:
        sort_point_pairs(points, (usize)(cr.len // 2))
    let pt = cr_points(cr)
    var j: usize = 0
    var i: usize = 0
    while i < pt.length:
        let start = pt[i]
        var end = pt[i + 1]
        i += 2
        while i < pt.length:
            let start1 = pt[i]
            let end1 = pt[i + 1]
            if start1 > end:
                # |------|
                #           |-------|
                break
            elif end1 <= end:
                # |------|
                #    |--|
                i += 2
            else:
                # |------|
                #     |-------|
                end = end1
                i += 2
        pt[j] = start
        pt[j + 1] = end
        j += 2
    cr.len = (i32)j

# mark: Regexp canonicalization ================================================================

# Release the four temporary ranges of cr_regexp_canonicalize (its C `fail:` and exit code).
func cr_free4(cr1: CharRange*, cr2: CharRange*, cr3: CharRange*, cr4: CharRange*):
    cr_free(cr1)
    cr_free(cr2)
    cr_free(cr3)
    cr_free(cr4)

# canonicalize a character set using the JS regex case folding rules
# (see lre_canonicalize())
## Replace `cr` with the set of its code points canonicalized by `lre_canonicalize(c,
## is_unicode)`; 0, or -1 when it cannot grow.
pub func cr_regexp_canonicalize(cr: CharRange*, is_unicode: bool) -> i32:
    var cr_inter: CharRange
    var cr_mask: CharRange
    var cr_result: CharRange
    var cr_sub: CharRange

    cr_init(&cr_mask, cr.mem_opaque, cr.realloc_func)
    cr_init(&cr_inter, cr.mem_opaque, cr.realloc_func)
    cr_init(&cr_result, cr.mem_opaque, cr.realloc_func)
    cr_init(&cr_sub, cr.mem_opaque, cr.realloc_func)
    defer cr_free4(&cr_inter, &cr_mask, &cr_result, &cr_sub)

    if unicode_case1(&cr_mask, case_f if is_unicode else case_u) != 0:
        return -1
    if cr_op(&cr_inter, cr_points(&cr_mask), cr_points(cr), cr_op_inter) != 0:
        return -1

    if cr_invert(&cr_mask) != 0:
        return -1
    if cr_op(&cr_sub, cr_points(&cr_mask), cr_points(cr), cr_op_inter) != 0:
        return -1

    # cr_inter = cr & cr_mask
    # cr_sub = cr & ~cr_mask

    # use the case conversion table to compute the result
    let no_interval: u32 = 0xffffffff  # the C `-1` of d_start and d_end
    var d_start = no_interval
    var d_end = no_interval
    var idx: u32 = 0
    var v = case_conv_table1[idx]
    var code = v >> (32 - 17)
    var len = (v >> (32 - 17 - 7)) & 0x7f
    let inter = cr_points(&cr_inter)
    var i: usize = 0
    while i < inter.length:
        let start = inter[i]
        let end = inter[i + 1]

        var c = start
        while c < end:
            while true:
                if c >= code and c < code + len:
                    break
                idx += 1
                assert(idx < case_conv_table1.length)
                v = case_conv_table1[idx]
                code = v >> (32 - 17)
                len = (v >> (32 - 17 - 7)) & 0x7f
            let d = lre_case_folding_entry(c, idx, v, is_unicode)
            # try to merge with the current interval
            if d_start == no_interval:
                d_start = d
                d_end = d + 1
            elif d_end == d:
                d_end += 1
            else:
                _ = cr_add_interval(&cr_result, d_start, d_end)
                d_start = d
                d_end = d + 1
            c += 1
        i += 2
    if d_start != no_interval:
        if cr_add_interval(&cr_result, d_start, d_end) != 0:
            return -1

    # the resulting ranges are not necessarily sorted and may overlap
    cr_sort_and_remove_overlap(&cr_result)

    # or with the character not affected by the case folding
    cr.len = 0
    if cr_op(cr, cr_points(&cr_result), cr_points(&cr_sub), cr_op_union) != 0:
        return -1
    return 0

# mark: Identifiers ============================================================================

## True if `c` has the ID_Start property.
pub func lre_is_id_start(c: u32) -> bool:
    return lre_is_in_table(c, unicode_prop_ID_Start_table, unicode_prop_ID_Start_index)

## True if `c` has the ID_Continue property.
pub func lre_is_id_continue(c: u32) -> bool:
    return (lre_is_id_start(c) or lre_is_in_table(c, unicode_prop_ID_Continue1_table, unicode_prop_ID_Continue1_index))