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))