Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / unicode / normalize.lucb

#==============================================================================================
#
#   normalize - Decomposition, composition and the NFC/NFD/NFKC/NFKD normalization
#
#   DESCRIPTION:
#       Port of QuickJS libunicode.c lines 761-1243: the decomposition table decoder, the
#       composition search, combining classes, canonical ordering and unicode_normalize.
#       Normalized text is a buffer of `u32` code points (C uses `int` for the working
#       buffer; the values are the same).
#
#==============================================================================================

# mark: Decomposition table ====================================================================

let unicode_decomp_len_max: i32 = 18

enum DecompTypeEnum as u32:
    c1 = 0  # 16 bit char
    l1 = 1  # 16 bit char table
    l2 = 2
    l3 = 3
    l4 = 4
    l5 = 5  # XXX: not used
    l6 = 6  # XXX: could remove
    l7 = 7  # XXX: could remove
    ll1 = 8  # 18 bit char table
    ll2 = 9
    s1 = 10  # 8 bit char table
    s2 = 11
    s3 = 12
    s4 = 13
    s5 = 14
    i1 = 15  # increment 16 bit char value
    i2_0 = 16
    i2_1 = 17
    i3_1 = 18
    i3_2 = 19
    i4_1 = 20
    i4_2 = 21
    b1 = 22  # 16 bit base + 8 bit offset
    b2 = 23
    b3 = 24
    b4 = 25
    b5 = 26
    b6 = 27
    b7 = 28
    b8 = 29
    b18 = 30
    ls2 = 31
    pat3 = 32
    s2_ul = 33
    ls2_ul = 34

let unicode_short_table: u16[2] = [0x2044, 0x2215]

func unicode_get_short_code(c: u32) -> u32:
    if c < 0x80:
        return c
    elif c < 0x80 + 0x50:
        return c - 0x80 + 0x300
    else:
        return unicode_short_table[c - 0x80 - 0x50]

func unicode_get_lower_simple(c: u32) -> u32:
    if c < 0x100 or (c >= 0x410 and c <= 0x42f):
        return c + 0x20
    else:
        return c + 1

func unicode_get16(p: const u8*) -> u16:
    let lo: u16 = p[0]
    let hi: u16 = p[1]
    return lo | (hi << 8)

func unicode_decomp_entry(res: u32[], c: u32, idx: i32, code: u32, len: u32,
                          decomp_type: u32) -> i32:
    if decomp_type == (u32)DecompTypeEnum.c1:
        res[0] = unicode_decomp_table2[(usize)idx]
        return 1
    var d: const u8* = &unicode_decomp_data[unicode_decomp_table2[(usize)idx]]
    match (DecompTypeEnum)decomp_type:
        .l1, .l2, .l3, .l4, .l5, .l6, .l7:
            let l = (i32)(decomp_type - (u32)DecompTypeEnum.l1) + 1
            d = d + (usize)((c - code) * (u32)l * 2)
            for i in 0..<(usize)l:
                res[i] = unicode_get16(d + 2 * i)
                if res[i] == 0:
                    return 0
            return l
        .ll1, .ll2:
            let l = (i32)(decomp_type - (u32)DecompTypeEnum.ll1) + 1
            var k: u32 = (c - code) * (u32)l
            let p: u32 = len * (u32)l * 2
            for i in 0..<(usize)l:
                let low: u32 = unicode_get16(d + (usize)(2 * k))
                let bits: u32 = d[(usize)(p + (k // 4))]
                let c1 = low | (((bits >> ((k % 4) * 2)) & 3) << 16)
                if c1 == 0:
                    return 0
                res[i] = c1
                k += 1
            return l
        .s1, .s2, .s3, .s4, .s5:
            let l = (i32)(decomp_type - (u32)DecompTypeEnum.s1) + 1
            d = d + (usize)((c - code) * (u32)l)
            for i in 0..<(usize)l:
                res[i] = unicode_get_short_code(d[i])
                if res[i] == 0:
                    return 0
            return l
        .i1, .i2_0, .i2_1, .i3_1, .i3_2, .i4_1, .i4_2:
            # the C `goto decomp_type_i` from DECOMP_TYPE_I1
            var l: i32 = 1
            var p: i32 = 0
            if decomp_type != (u32)DecompTypeEnum.i1:
                l = 2 + (i32)((decomp_type - (u32)DecompTypeEnum.i2_0) >> 1)
                p = (i32)((decomp_type - (u32)DecompTypeEnum.i2_0) & 1) + (i32)(l > 2)
            for i: i32 in 0..<l:
                var c1: u32 = unicode_get16(d + 2 * (usize)i)
                if i == p:
                    c1 += c - code
                res[(usize)i] = c1
            return l
        .b1, .b2, .b3, .b4, .b5, .b6, .b7, .b8, .b18:
            # the C `goto decomp_type_b` from DECOMP_TYPE_B18
            var l: i32 = 18
            if decomp_type != (u32)DecompTypeEnum.b18:
                l = (i32)(decomp_type - (u32)DecompTypeEnum.b1) + 1
            let c_min: u32 = unicode_get16(d)
            d = d + 2 + (usize)((c - code) * (u32)l)
            for i in 0..<(usize)l:
                var c1: u32 = d[i]
                if c1 == 0xff:
                    c1 = 0x20
                else:
                    c1 += c_min
                res[i] = c1
            return l
        .ls2:
            d = d + (usize)((c - code) * 3)
            res[0] = unicode_get16(d)
            if res[0] == 0:
                return 0
            res[1] = unicode_get_short_code(d[2])
            return 2
        .pat3:
            res[0] = unicode_get16(d)
            res[2] = unicode_get16(d + 2)
            d = d + 4 + (usize)((c - code) * 2)
            res[1] = unicode_get16(d)
            return 3
        .s2_ul, .ls2_ul:
            let c1 = c - code
            var c2: u32 = 0
            if decomp_type == (u32)DecompTypeEnum.s2_ul:
                d = d + (usize)(c1 & ~1u32)
                c2 = unicode_get_short_code(*d)
                d = d + 1
            else:
                d = d + (usize)((c1 >> 1) * 3)
                c2 = unicode_get16(d)
                d = d + 2
            if (c1 & 1) != 0:
                c2 = unicode_get_lower_simple(c2)
            res[0] = c2
            res[1] = unicode_get_short_code(*d)
            return 2
        _:
            return 0

# return the length of the decomposition (length <=
# UNICODE_DECOMP_LEN_MAX) or 0 if no decomposition
func unicode_decomp_char(res: u32[], c: u32, is_compat1: bool) -> i32:
    var idx_min: i32 = 0
    var idx_max: i32 = (i32)unicode_decomp_table1.length - 1
    while idx_min <= idx_max:
        let idx = (idx_max + idx_min) // 2
        let v = unicode_decomp_table1[(usize)idx]
        let code = v >> (32 - 18)
        let len = (v >> (32 - 18 - 7)) & 0x7f
        if c < code:
            idx_max = idx - 1
        elif c >= code + len:
            idx_min = idx + 1
        else:
            let is_compat = v & 1
            if (u32)is_compat1 < is_compat:
                break
            let decomp_type = (v >> (32 - 18 - 7 - 6)) & 0x3f
            return unicode_decomp_entry(res, c, idx, code, len, decomp_type)
    return 0

# mark: Composition ============================================================================

# return 0 if no pair found
func unicode_compose_pair(c0: u32, c1: u32) -> i32:
    var pair: u32[2]
    var idx_min: i32 = 0
    var idx_max: i32 = (i32)unicode_comp_table.length - 1
    while idx_min <= idx_max:
        let idx = (idx_max + idx_min) // 2
        let idx1: u32 = unicode_comp_table[(usize)idx]

        # idx1 represent an entry of the decomposition table
        let d_idx = idx1 >> 6
        let d_offset = idx1 & 0x3f
        let v = unicode_decomp_table1[d_idx]
        let code = v >> (32 - 18)
        let len = (v >> (32 - 18 - 7)) & 0x7f
        let decomp_type = (v >> (32 - 18 - 7 - 6)) & 0x3f
        let ch = code + d_offset
        _ = unicode_decomp_entry(pair, ch, (i32)d_idx, code, len, decomp_type)
        var d = (i32)(c0 -% pair[0])
        if d == 0:
            d = (i32)(c1 -% pair[1])
        if d < 0:
            idx_max = idx - 1
        elif d > 0:
            idx_min = idx + 1
        else:
            return (i32)ch
    return 0

# mark: Combining classes ======================================================================

# return the combining class of character c (between 0 and 255)
func unicode_get_cc(c: u32) -> i32:
    var code: u32 = 0
    let pos = get_index_pos(&code, c, unicode_cc_index)
    if pos < 0:
        return 0
    var p: const u8* = &unicode_cc_table[(usize)pos]
    # Compressed run length encoding:
    #    - 2 high order bits are combining class type
    #    -         0:0, 1:230, 2:extra byte linear progression, 3:extra byte
    #    - 00..2F: range length (add 1)
    #    - 30..37: 3-bit range-length + 1 extra byte
    #    - 38..3F: 3-bit range-length + 2 extra byte
    while true:
        let b: u32 = *p
        p = p + 1
        let cc_type = b >> 6
        var n = b & 0x3f
        # (00..2F: the length is n itself)
        if n >= 48 and n < 56:
            n = (n - 48) << 8
            let e0: u32 = *p
            p = p + 1
            n |= e0
            n += 48
        elif n >= 56:
            n = (n - 56) << 8
            let e0: u32 = *p
            p = p + 1
            n |= e0 << 8
            let e1: u32 = *p
            p = p + 1
            n |= e1
            n += 48 + (1 << 11)
        if cc_type <= 1:
            p = p + 1
        let c1 = code + n + 1
        if c < c1:
            let prev: u32 = *(p - 1)
            match cc_type:
                0:
                    return (i32)prev
                1:
                    return (i32)(prev + c - code)
                2:
                    return 0
                _:
                    return 230
        code = c1

func sort_cc(buf: u32[]):
    let len = (i32)buf.length
    var i: i32 = 0
    while i < len:
        let cc = unicode_get_cc(buf[(usize)i])
        if cc != 0:
            let start = i
            var j = i + 1
            while j < len:
                let ch1 = buf[(usize)j]
                let cc1 = unicode_get_cc(ch1)
                if cc1 == 0:
                    break
                var k = j - 1
                while k >= start:
                    if unicode_get_cc(buf[(usize)k]) <= cc1:
                        break
                    buf[(usize)(k + 1)] = buf[(usize)k]
                    k -= 1
                buf[(usize)(k + 1)] = ch1
                j += 1
            i = j
        i += 1

# mark: Normalization ==========================================================================

func to_nfd_rec(dbuf: DynBuf*, src: const u32[], is_compat: bool):
    var res: u32[18]
    for i in 0..<src.length:
        var c = src[i]
        if c >= 0xac00 and c < 0xd7a4:
            # Hangul decomposition
            c -= 0xac00
            _ = dbuf_put_u32(dbuf, 0x1100 + c // 588)
            _ = dbuf_put_u32(dbuf, 0x1161 + (c % 588) // 28)
            let v = c % 28
            if v != 0:
                _ = dbuf_put_u32(dbuf, 0x11a7 + v)
        else:
            let l = unicode_decomp_char(res, c, is_compat)
            if l != 0:
                to_nfd_rec(dbuf, res[0..<(usize)l], is_compat)
            else:
                _ = dbuf_put_u32(dbuf, c)

# return 0 if not found
func compose_pair(c0: u32, c1: u32) -> i32:
    # Hangul composition
    if (c0 >= 0x1100 and c0 < 0x1100 + 19 and c1 >= 0x1161 and c1 < 0x1161 + 21):
        return (i32)(0xac00 + (c0 - 0x1100) * 588 + (c1 - 0x1161) * 28)
    elif (c0 >= 0xac00 and c0 < 0xac00 + 11172 and (c0 - 0xac00) % 28 == 0 and c1 >= 0x11a7 and c1 < 0x11a7 + 28):
        return (i32)(c0 + c1 - 0x11a7)
    else:
        return unicode_compose_pair(c0, c1)

# The code points of a DynBuf as a span (empty when it has no storage).
func dbuf_u32(dbuf: const DynBuf*, count: usize) -> u32[]:
    if let b = dbuf.buf:
        return u32[]((u32*)b, count)
    var empty: u32[]
    return empty

# The DynBuf storage as the result pointer (none when it has no storage).
func dbuf_result(dbuf: const DynBuf*) -> u32*?:
    if let b = dbuf.buf:
        return (u32*)b
    return none

## Normalize the code points `src` to the form `n_type` into a buffer allocated with
## `realloc_func(opaque, ...)` (C `realloc` when none), stored in `*pdst`; answer its length
## in code points, or -1 (and `*pdst` none) when memory runs out. The caller frees `*pdst`.
pub func unicode_normalize(pdst: u32*?*, src: const u32[], n_type: UnicodeNormalizationEnum,
                           opaque: void*?, realloc_func: ReallocFunc?) -> i32:
    let src_len = src.length
    let is_compat = (n_type >> 1) != 0

    var dbuf_s: DynBuf
    let dbuf = &dbuf_s
    dbuf_init2(dbuf, opaque, realloc_func)
    if dbuf_claim(dbuf, memory.size_of(u32) * src_len) != 0:
        *pdst = none
        return -1

    # common case: latin1 is unaffected by NFC
    if n_type == unicode_nfc:
        var latin1 = true
        for i in 0..<src_len:
            if src[i] >= 0x100:
                latin1 = false
                break
        if latin1:
            if src_len != 0:
                let b = dbuf.buf else trap("unicode_normalize: no storage")
                _ = memcpy(b, src.data, src_len * memory.size_of(u32))
            *pdst = dbuf_result(dbuf)
            return (i32)src_len

    to_nfd_rec(dbuf, src, is_compat)
    if dbuf_error(dbuf):
        *pdst = none
        return -1
    let buf_len = dbuf.size // memory.size_of(u32)
    let buf = dbuf_u32(dbuf, buf_len)

    sort_cc(buf)

    if buf_len <= 1 or (n_type & 1) != 0:
        # NFD / NFKD
        *pdst = dbuf_result(dbuf)
        return (i32)buf_len

    var i: usize = 1
    var out_len: usize = 1
    while i < buf_len:
        # find the starter character and test if it is blocked from
        # the character at 'i'
        var last_cc = unicode_get_cc(buf[i])
        var starter_pos = (isize)out_len - 1
        var blocked = false  # the C `goto next`
        while starter_pos >= 0:
            let cc = unicode_get_cc(buf[(usize)starter_pos])
            if cc == 0:
                break
            if cc >= last_cc:
                blocked = true
                break
            last_cc = 256
            starter_pos -= 1
        var p: i32 = 0
        if not blocked and starter_pos >= 0:
            p = compose_pair(buf[(usize)starter_pos], buf[i])
        if p != 0:
            buf[(usize)starter_pos] = (u32)p
            i += 1
        else:
            buf[out_len] = buf[i]
            out_len += 1
            i += 1
    *pdst = dbuf_result(dbuf)
    return (i32)out_len