Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / es_sets.lucb

#==============================================================================================
#
#   es_sets - ECMAScript class sets: code points plus, with the v flag, strings
#
#   DESCRIPTION:
#       The counterpart of libregexp.c's REStringList (lines 132-460): a set is a
#       `unicode.CharRange` of code points plus a hash set of the strings whose length is
#       not one (the v flag's \q{...} and sequence properties such as \p{RGI_Emoji}), with
#       the union, intersection and difference of class set operations, and Canonicalize
#       for the i flag. The \d \s \w ranges live here too. A finished set becomes a class,
#       or, when it holds strings, an alternation that tries the longest strings first.
#
#==============================================================================================

# mark: The set ================================================================================

struct StrSet:
    var cr: unicode.CharRange
    # the strings: at offs[i] in `pool`, a length followed by that many code points
    var pool: Vec[u32]
    var offs: Vec[i32]
    # open-addressed hash buckets holding indexes into `offs`, -1 when empty
    var table: Vec[i32]

func set_init(ps: const EsParse*, s: StrSet*):
    let heap = ps.re.heap
    unicode.cr_init(&s.cr, heap.opaque, heap.realloc_func)
    s.pool = Vec[u32](heap = heap)
    s.offs = Vec[i32](heap = heap)
    s.table = Vec[i32](heap = heap)

func set_free(s: StrSet*):
    unicode.cr_free(&s.cr)
    s.pool.free_all()
    s.offs.free_all()
    s.table.free_all()

func cr_check(ret: i32) -> !:
    if ret != 0:
        error(memory.exhausted, "regex: out of memory")

func set_string_count(s: const StrSet*) -> usize:
    return s.offs.used

func str_hash(cps: const u32[]) -> u32:
    var h: u32 = 1
    for c in cps:
        h = h *% 263 +% c
    return h *% 0x61C88647

# The code points of string `i` of the set.
func set_string(s: const StrSet*, i: usize) -> const u32[]:
    let off = (usize)s.offs.data[i]
    let n = (usize)s.pool.data[off]
    return s.pool.data[off + 1..<off + 1 + n]

func same_cps(a: const u32[], b: const u32[]) -> bool:
    if a.length != b.length:
        return false
    var i: usize = 0
    while i < a.length:
        if a[i] != b[i]:
            return false
        i += 1
    return true

# The bucket of `cps`: where it is, or the empty bucket where it would go.
func set_bucket(s: const StrSet*, cps: const u32[]) -> usize:
    let mask = s.table.used - 1
    var h = (usize)(str_hash(cps)) & mask
    while true:
        let e = s.table.data[h]
        if e < 0 or same_cps(set_string(s, (usize)e), cps):
            return h
        h = (h + 1) & mask

func set_has_string(s: const StrSet*, cps: const u32[]) -> bool:
    if s.offs.used == 0:
        return false
    return s.table.data[set_bucket(s, cps)] >= 0

# Rebuild the hash buckets for the strings in `offs`, with room to grow.
func set_rehash(s: StrSet*, want: usize) -> !:
    var size: usize = 16
    while size < 2 * want:
        size *= 2
    s.table.used = 0
    try s.table.ensure(size)
    s.table.used = size
    var i: usize = 0
    while i < size:
        s.table.data[i] = -1
        i += 1
    var k: usize = 0
    while k < s.offs.used:
        s.table.data[set_bucket(s, set_string(s, k))] = (i32)k
        k += 1

func set_add_string(s: StrSet*, cps: const u32[]) -> !:
    if set_has_string(s, cps):
        return
    if 2 * (s.offs.used + 1) > s.table.used:
        try set_rehash(s, s.offs.used + 1)
    let off = try s.pool.push((u32)cps.length)
    for c in cps:
        _ = try s.pool.push(c)
    let index = try s.offs.push((i32)off)
    s.table.data[set_bucket(s, cps)] = (i32)index

# re_string_add: a one-character string joins the code points.
func set_add(s: StrSet*, cps: const u32[]) -> !:
    if cps.length == 1:
        try cr_check(unicode.cr_union_interval(&s.cr, cps[0], cps[0]))
        return
    try set_add_string(s, cps)

# a = a op b (unicode.cr_op_union, cr_op_inter or cr_op_sub)
func set_op(a: StrSet*, b: const StrSet*, op: i32) -> !:
    try cr_check(unicode.cr_op1(&a.cr, unicode.cr_points(&b.cr), op))
    if op == unicode.cr_op_union:
        var i: usize = 0
        while i < b.offs.used:
            try set_add_string(a, set_string(b, i))
            i += 1
        return
    # intersection or difference: keep the strings of `a` that are (not) in `b`
    var kept: usize = 0
    var i: usize = 0
    while i < a.offs.used:
        var keep = set_has_string(b, set_string(a, i))
        if op == unicode.cr_op_sub:
            keep = not keep
        if keep:
            a.offs.data[kept] = a.offs.data[i]
            kept += 1
        i += 1
    if kept != a.offs.used:
        a.offs.used = kept
        try set_rehash(a, kept)

# re_string_list_canonicalize
func set_canonicalize(ps: const EsParse*, s: StrSet*, is_unicode: bool) -> !:
    try cr_check(unicode.cr_regexp_canonicalize(&s.cr, is_unicode))
    if s.offs.used == 0:
        return
    var old: StrSet = ---
    set_init(ps, &old)
    defer set_free(&old)
    # move the strings aside, then add them back canonicalized
    let pool = old.pool
    old.pool = s.pool
    s.pool = pool
    let offs = old.offs
    old.offs = s.offs
    s.offs = offs
    s.table.used = 0
    var buf = Vec[u32](heap = ps.re.heap)
    defer buf.free_all()
    var i: usize = 0
    while i < old.offs.used:
        let cps = set_string(&old, i)
        buf.used = 0
        for c in cps:
            _ = try buf.push((u32)unicode.lre_canonicalize(c, is_unicode))
        try set_add(s, buf.data[..<buf.used])
        i += 1

# mark: Class escapes ==========================================================================

# \d, \s and \w as [low, high + 1) bounds.
let char_range_d: u32[2] = [0x0030, 0x0039 + 1]

# code point ranges for Zs,Zl or Zp property
let char_range_s: u32[20] = [
    0x0009, 0x000D + 1,
    0x0020, 0x0020 + 1,
    0x00A0, 0x00A0 + 1,
    0x1680, 0x1680 + 1,
    0x2000, 0x200A + 1,
    # 2028;LINE SEPARATOR;Zl;0;WS;;;;;N;;;;;
    # 2029;PARAGRAPH SEPARATOR;Zp;0;B;;;;;N;;;;;
    0x2028, 0x2029 + 1,
    0x202F, 0x202F + 1,
    0x205F, 0x205F + 1,
    0x3000, 0x3000 + 1,
    # FEFF;ZERO WIDTH NO-BREAK SPACE;Cf;0;BN;;;;;N;BYTE ORDER MARK;;;;
    0xFEFF, 0xFEFF + 1,
]

let char_range_w: u32[8] = [
    0x0030, 0x0039 + 1,
    0x0041, 0x005A + 1,
    0x005F, 0x005F + 1,
    0x0061, 0x007A + 1,
]

# CharRangeEnum: bit 0 is the inversion (\D \S \W), the rest selects d, s or w.
let CLASS_d: u32 = 0
let CLASS_D: u32 = 1
let CLASS_s: u32 = 2
let CLASS_S: u32 = 3
let CLASS_w: u32 = 4
let CLASS_W: u32 = 5

# get_class_atom's answer for a set rather than a character.
let CLASS_RANGE_BASE: i32 = 0x40000000

# cr_init_char_range
func init_char_range(ps: const EsParse*, s: StrSet*, c: u32) -> !:
    set_init(ps, s)
    errdefer set_free(s)
    var points: const u32[] = char_range_d
    if (c >> 1) == 1:
        points = char_range_s
    elif (c >> 1) == 2:
        points = char_range_w
    for v in points:
        try cr_check(unicode.cr_add_point(&s.cr, v))
    if (c & 1) != 0:
        try cr_check(unicode.cr_invert(&s.cr))

# mark: To the AST =============================================================================

# A class of the program holding the code points of `cr`.
func es_new_class(re: Regex*, cr: const unicode.CharRange*) -> i32!:
    let points = unicode.cr_points(cr)
    var cc = CharClass()
    cc.range_start = re.ranges.used
    var i: usize = 0
    while i + 1 < points.length:
        _ = try re.ranges.push(points[i])
        _ = try re.ranges.push(points[i + 1] - 1)
        i += 2
    cc.range_count = points.length // 2
    let index = try re.classes.push(cc)
    return (i32)index

# The node matching set `s` (re_emit_string_list): a class, or, with strings, an alternation
# of the strings from the longest to the shortest, then the class, then the empty string.
func set_to_node(ps: EsParse*, s: const StrSet*) -> i32!:
    let flags = F_IC if ps.ignore_case else (u8)0
    let re = ps.re
    if s.offs.used == 0:
        let n = try new_node(re, K_CLASS)
        re.nodes.data[(usize)n].a = try es_new_class(re, &s.cr)
        re.nodes.data[(usize)n].flags = flags
        return n
    var max_len: usize = 0
    var has_empty = false
    var i: usize = 0
    while i < s.offs.used:
        let n = set_string(s, i).length
        if n == 0:
            has_empty = true
        if n > max_len:
            max_len = n
        i += 1
    var head: i32 = -1
    var tail: i32 = -1
    var len = max_len
    while len > 0:
        var k: usize = 0
        while k < s.offs.used:
            let cps = set_string(s, k)
            if cps.length == len:
                let alt = try es_chars_node(ps, cps, flags)
                try link_sibling(re, &head, &tail, alt)
            k += 1
        len -= 1
    if unicode.cr_points(&s.cr).length != 0:
        let n = try new_node(re, K_CLASS)
        re.nodes.data[(usize)n].a = try es_new_class(re, &s.cr)
        re.nodes.data[(usize)n].flags = flags
        try link_sibling(re, &head, &tail, n)
    if has_empty:
        try link_sibling(re, &head, &tail, try new_node(re, K_EMPTY))
    if head == tail:
        return head
    let node = try new_node(re, K_ALT)
    re.nodes.data[(usize)node].first_child = head
    return node

# The concatenation of the characters `cps`.
func es_chars_node(ps: EsParse*, cps: const u32[], flags: u8) -> i32!:
    let re = ps.re
    var head: i32 = -1
    var tail: i32 = -1
    for c in cps:
        let n = try mk_char(re, c)
        re.nodes.data[(usize)n].flags = flags
        try link_sibling(re, &head, &tail, n)
    if head == tail:
        return head
    let node = try new_node(re, K_CONCAT)
    re.nodes.data[(usize)node].first_child = head
    return node

# Append `n` to the sibling list (head, tail).
func link_sibling(re: Regex*, head: i32*, tail: i32*, n: i32) -> !:
    if *head < 0:
        *head = n
    else:
        re.nodes.data[(usize)*tail].next_sibling = n
    *tail = n