Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-js

Source of release 0.6.0

0.6.0 / src / engine / ropes.lucb

#==============================================================================================
#
#   ropes - String ropes: indexing, iteration, comparison, flattening, balancing, and
#           JS_ConcatString
#
#   DESCRIPTION:
#       Port of quickjs.c lines 4723-5119. A rope (StringRope) is a lazy concatenation of
#       two strings or ropes. Concatenations of long strings build ropes; a rope deeper
#       than js_string_rope_max_depth is rebalanced with the Fibonacci buckets of Boehm,
#       Atkinson and Plass; a rope is flattened (linearized) when its characters are
#       needed as one string.
#
#==============================================================================================

# mark: Reading ropes ===========================================================================

# Return the character at position 'idx'. 'val' must be a string or rope.
func string_rope_get(val: Value, idx: u32) -> i32:
    if val.tag == Tag.string:
        return string_get(val.u.string, (i32)idx)
    let r = val.u.rope
    var len: u32 = 0
    if r.left.tag == Tag.string:
        len = r.left.u.string.len
    else:
        len = r.left.u.rope.len
    if idx < len:
        return string_rope_get(r.left, idx)
    return string_rope_get(r.right, idx - len)

## An in-order walk over the flat strings of a rope (JSStringRopeIter).
struct StringRopeIter:
    var stack: Value[60]
    var stack_len: i32

assert(js_string_rope_max_depth == 60, "StringRopeIter.stack holds js_string_rope_max_depth")

func string_rope_iter_init(s: StringRopeIter*, val: Value):
    s.stack_len = 0
    s.stack[s.stack_len] = val
    s.stack_len += 1

# iterate thru a rope and return the strings in order
func string_rope_iter_next(s: StringRopeIter*) -> String*?:
    if s.stack_len == 0:
        return none
    s.stack_len -= 1
    var val = s.stack[s.stack_len]
    while val.tag != Tag.string:
        let r = val.u.rope
        assert(s.stack_len < js_string_rope_max_depth)
        s.stack[s.stack_len] = r.right
        s.stack_len += 1
        val = r.left
    return val.u.string

func string_rope_get_len(val: Value) -> u32:
    if val.tag == Tag.string:
        return val.u.string.len
    return val.u.rope.len

# Compare two strings or ropes: < 0, 0 or > 0. With `eq_only`, only whether the result is
# 0 is meaningful.
func js_string_rope_compare(ctx: Context*, op1: Value, op2: Value, eq_only: bool) -> i32:
    let len1 = string_rope_get_len(op1)
    let len2 = string_rope_get_len(op2)
    # no need to go further for equality test if different length
    if eq_only and len1 != len2:
        return 1
    var len = cutils.min_uint32(len1, len2)
    var it1: StringRopeIter = ---
    var it2: StringRopeIter = ---
    string_rope_iter_init(&it1, op1)
    string_rope_iter_init(&it2, op2)
    var p1 = string_rope_iter_next(&it1)
    var p2 = string_rope_iter_next(&it2)
    var pos1: u32 = 0
    var pos2: u32 = 0
    while len != 0:
        # Both walks hold at least `len` more characters.
        let s1 = p1 else trap("rope shorter than its length")
        let s2 = p2 else trap("rope shorter than its length")
        var l = cutils.min_uint32(s1.len - pos1, s2.len - pos2)
        l = cutils.min_uint32(l, len)
        let res = js_string_memcmp(s1, (i32)pos1, s2, (i32)pos2, (i32)l)
        if res != 0:
            return res
        len -= l
        pos1 += l
        if pos1 >= s1.len:
            p1 = string_rope_iter_next(&it1)
            pos1 = 0
        pos2 += l
        if pos2 >= s2.len:
            p2 = string_rope_iter_next(&it2)
            pos2 = 0

    if len1 == len2:
        return 0
    if len1 < len2:
        return -1
    return 1

# mark: Building ropes ==========================================================================

# 'rope' must be a rope. return a string and modify the rope so that it won't need to be
# linearized again. Takes ownership of `rope`.
func js_linearize_string_rope(ctx: Context*, rope: Value) -> Value!:
    let r = rope.u.rope
    defer js_free_value(ctx, rope)

    # check whether it is already linearized
    if r.right.tag == Tag.string and r.right.u.string.len == 0:
        return js_dup_value(ctx, r.left)
    var b: StringBuffer = ---
    try string_buffer_init2(ctx, &b, (i32)r.len, r.is_wide_char != 0)
    try string_buffer_concat_value(&b, rope)
    let ret = try string_buffer_end(&b)
    if js_rc(r).ref_count > 1:
        # update the rope so that it won't need to be linearized again
        js_free_value(ctx, r.left)
        js_free_value(ctx, r.right)
        r.left = js_dup_value(ctx, ret)
        r.right = js_atom_to_string(ctx, atom_empty_string) catch: trap("the empty string atom")
    return ret

# op1 and op2 must be strings or string ropes; takes ownership of both.
func js_new_string_rope(ctx: Context*, op1: Value, op2: Value) -> Value!:
    var len: u32 = 0
    var is_wide_char = false
    var depth: i32 = 0
    if op1.tag == Tag.string:
        let p1 = op1.u.string
        len = p1.len
        is_wide_char = p1.is_wide_char
        depth = 0
    else:
        let r1 = op1.u.rope
        len = r1.len
        is_wide_char = r1.is_wide_char != 0
        depth = (i32)r1.depth

    if op2.tag == Tag.string:
        let p2 = op2.u.string
        len += p2.len
        is_wide_char = is_wide_char or p2.is_wide_char
    else:
        let r2 = op2.u.rope
        len += r2.len
        is_wide_char = is_wide_char or r2.is_wide_char != 0
        depth = cutils.max_int(depth, (i32)r2.depth)
    if len > (u32)js_string_len_max:
        js_throw_internal_error(ctx, "string too long") catch failure:
            js_free_value(ctx, op1)
            js_free_value(ctx, op2)
            error(failure.code, failure.message)
    let mem = js_malloc(ctx, memory.size_of(StringRope)) catch failure:
        js_free_value(ctx, op1)
        js_free_value(ctx, op2)
        error(failure.code, failure.message)
    let r = (StringRope*)mem
    js_rc(r).ref_count = 1
    r.len = len
    r.is_wide_char = (u8)is_wide_char
    r.depth = (u8)(depth + 1)
    r.left = op1
    r.right = op2
    let res = js_mkptr(Tag.string_rope, r)
    if (i32)r.depth > js_string_rope_max_depth:
        let res2 = js_rebalancee_string_rope(ctx, res) catch failure:
            js_free_value(ctx, res)
            error(failure.code, failure.message)
        js_free_value(ctx, res)
        return res2
    return res

let rope_n_buckets: usize = 44

# Fibonacci numbers starting from F_2
let rope_bucket_len: u32[44] = [
    1, 2, 3, 5,
    8, 13, 21, 34,
    55, 89, 144, 233,
    377, 610, 987, 1597,
    2584, 4181, 6765, 10946,
    17711, 28657, 46368, 75025,
    121393, 196418, 317811, 514229,
    832040, 1346269, 2178309, 3524578,
    5702887, 9227465, 14930352, 24157817,
    39088169, 63245986, 102334155, 165580141,
    267914296, 433494437, 701408733, 1134903170, # > JS_STRING_LEN_MAX
]

# Add the flat strings of `val` to the buckets: bucket i holds a rope whose length is at
# least rope_bucket_len[i], or null.
func js_rebalancee_string_rope_rec(ctx: Context*, buckets: Value[], val: Value) -> !:
    if val.tag == Tag.string:
        let p = val.u.string
        let len = p.len
        if len == 0:
            return  # nothing to do
        # find the bucket i so that rope_bucket_len[i] <= len < rope_bucket_len[i + 1] and
        # concatenate the ropes in the buckets before
        var a = js_null()
        var i: usize = 0
        while len >= rope_bucket_len[i + 1]:
            let b = buckets[i]
            if not js_is_null(b):
                buckets[i] = js_null()
                if js_is_null(a):
                    a = b
                else:
                    a = try js_new_string_rope(ctx, b, a)
            i += 1
        if not js_is_null(a):
            a = try js_new_string_rope(ctx, a, js_dup_value(ctx, val))
        else:
            a = js_dup_value(ctx, val)
        while not js_is_null(buckets[i]):
            let b = buckets[i]
            buckets[i] = js_null()
            a = try js_new_string_rope(ctx, b, a)
            i += 1
        buckets[i] = a
    else:
        let r = val.u.rope
        # QuickJS ignores a failure of these two calls; it is propagated here.
        try js_rebalancee_string_rope_rec(ctx, buckets, r.left)
        try js_rebalancee_string_rope_rec(ctx, buckets, r.right)

func free_rope_buckets(ctx: Context*, buckets: Value[]):
    for i in 0..<rope_n_buckets:
        js_free_value(ctx, buckets[i])

# Return a new rope which is balanced. Algorithm from "Ropes: an Alternative to Strings",
# Hans-J. Boehm, Russ Atkinson and Michael Plass.
func js_rebalancee_string_rope(ctx: Context*, rope: Value) -> Value!:
    var buckets: Value[44] = ---
    for i in 0..<rope_n_buckets:
        buckets[i] = js_null()
    errdefer free_rope_buckets(ctx, buckets)
    try js_rebalancee_string_rope_rec(ctx, buckets, rope)
    var a = js_null()
    for i in 0..<rope_n_buckets:
        let b = buckets[i]
        if not js_is_null(b):
            buckets[i] = js_null()
            if js_is_null(a):
                a = b
            else:
                a = try js_new_string_rope(ctx, b, a)
    # fail safe
    if js_is_null(a):
        return try js_atom_to_string(ctx, atom_empty_string)
    return a

# mark: Concatenation ===========================================================================

# op1 and op2 are converted to strings; takes ownership of both.
func js_concat_string(ctx: Context*, op1: Value, op2: Value) -> Value!:
    var v1 = op1
    var v2 = op2
    if v1.tag != Tag.string and v1.tag != Tag.string_rope:
        v1 = js_to_string_free(ctx, v1) catch failure:
            js_free_value(ctx, v2)
            error(failure.code, failure.message)
    if v2.tag != Tag.string and v2.tag != Tag.string_rope:
        v2 = js_to_string_free(ctx, v2) catch failure:
            js_free_value(ctx, v1)
            error(failure.code, failure.message)

    # normal concatenation for short strings
    if v2.tag == Tag.string:
        let p2 = v2.u.string
        if p2.len == 0:
            js_free_value(ctx, v2)
            return v1
        if p2.len <= (u32)js_string_rope_short_len:
            if v1.tag == Tag.string:
                let p1 = v1.u.string
                if p1.len <= (u32)js_string_rope_short2_len:
                    return try js_concat_string2(ctx, v1, v2)
                return try js_new_string_rope(ctx, v1, v2)
            let r1 = v1.u.rope
            if (r1.right.tag == Tag.string and r1.right.u.string.len <= (u32)js_string_rope_short_len):
                defer js_free_value(ctx, v1)
                let val = try js_concat_string2(ctx, js_dup_value(ctx, r1.right), v2)
                return try js_new_string_rope(ctx, js_dup_value(ctx, r1.left), val)
    elif v1.tag == Tag.string:
        let p1 = v1.u.string
        if p1.len == 0:
            js_free_value(ctx, v1)
            return v2
        let r2 = v2.u.rope
        if (r2.left.tag == Tag.string and r2.left.u.string.len <= (u32)js_string_rope_short_len):
            defer js_free_value(ctx, v2)
            let val = try js_concat_string2(ctx, v1, js_dup_value(ctx, r2.left))
            return try js_new_string_rope(ctx, val, js_dup_value(ctx, r2.right))
    return try js_new_string_rope(ctx, v1, v2)