Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-js

Source of release 0.6.0

0.6.0 / src / engine / atoms.lucb

#==============================================================================================
#
#   atoms - The atom table: interning strings and symbols as 32-bit ids
#
#   DESCRIPTION:
#       Port of quickjs.c "JSAtom support" (lines 2868-3433): tagged-integer atoms, the
#       string hashes, the atom hash table and its initialisation from `js_atom_init`,
#       atom reference counting, interning (__JS_NewAtom), lookup and freeing. The
#       conversions between atoms, numbers, strings and symbols are in atoms_convert.
#       JS_DumpChar, JS_DumpString and JS_DumpAtoms are not ported: QuickJS calls them
#       only from DUMP_* debug blocks.
#
#==============================================================================================

# mark: Tagged integers =========================================================================

let js_atom_tag_int: u32 = 1 << 31
let js_atom_max_int: u32 = js_atom_tag_int - 1
let js_atom_max: u32 = (1 << 30) - 1

## The max count from the hash size (JS_ATOM_COUNT_RESIZE).
func js_atom_count_resize(n: i32) -> i32:
    return n * 2

## Whether `v` is a predefined atom (or a tagged integer, or no_atom): not reference
## counted.
func js_atom_is_const_raw(v: Atom) -> bool:
    return (i32)v < (i32)atom_end

## Whether `v` is an integer carried in the atom itself.
func js_atom_is_tagged_int_raw(v: Atom) -> bool:
    return (v & js_atom_tag_int) != 0

## The tagged-integer atom of `v` (v <= js_atom_max_int).
func js_atom_from_uint32_raw(v: u32) -> Atom:
    return v | js_atom_tag_int

## The integer of a tagged-integer atom.
func js_atom_to_uint32_raw(atom: Atom) -> u32:
    return atom & ~js_atom_tag_int

func is_num(c: i32) -> bool:
    return c >= (i32)'0' and c <= (i32)'9'

# Return true if the string is a number n with 0 <= n <= 2^32-1.
func is_num_string(pval: u32*, p: const String*) -> bool:
    let len = (i32)p.len
    if len == 0 or len > 10:
        return false
    var c = string_get(p, 0)
    if is_num(c):
        var n: u32
        if c == (i32)'0':
            if len != 1:
                return false
            n = 0
        else:
            n = (u32)(c - (i32)'0')
            for i in 1..<len:
                c = string_get(p, i)
                if not is_num(c):
                    return false
                let n64 = (u64)n * 10 + (u64)(c - (i32)'0')
                if (n64 >> 32) != 0:
                    return false
                n = (u32)n64
        *pval = n
        return true
    else:
        return false

# mark: Hashing =================================================================================

# XXX: could use faster version ?
func hash_string8(str_: const u8*, len: usize, h: u32) -> u32:
    var hv = h
    for i in 0..<len:
        hv = hv *% 263 +% str_[i]
    return hv

func hash_string16(str_: const u16*, len: usize, h: u32) -> u32:
    var hv = h
    for i in 0..<len:
        hv = hv *% 263 +% str_[i]
    return hv

func hash_string(str_: const String*, h: u32) -> u32:
    if str_.is_wide_char:
        return hash_string16(str16(str_), (usize)str_.len, h)
    return hash_string8(str8(str_), (usize)str_.len, h)

func hash_string_rope(val: Value, h: u32) -> u32:
    if val.tag == Tag.string:
        return hash_string(val.u.string, h)
    let r = val.u.rope
    let hv = hash_string_rope(r.left, h)
    return hash_string_rope(r.right, hv)

# mark: The atom table ==========================================================================

## rt->atom_array[i]: an atom's string, or a free entry (see `atom_is_free`).
func atom_array_get(rt: Runtime*, i: u32) -> AtomStruct*:
    let atom_array = rt.atom_array else trap("atom table not initialized")
    return atom_array[i]

## rt->atom_hash, which exists once `js_init_atoms` has run.
func atom_hash_table(rt: Runtime*) -> u32*:
    return rt.atom_hash else trap("atom hash table not initialized")

func js_resize_atom_hash(rt: Runtime*, new_hash_size: i32) -> i32:
    assert((new_hash_size & (new_hash_size - 1)) == 0)  # power of two
    let new_hash_mask = (u32)(new_hash_size - 1)
    let mem = js_mallocz_rt(rt, memory.size_of(u32) * (usize)new_hash_size) else return -1
    let new_hash = (u32*)mem
    if let old_hash = rt.atom_hash:
        for i in 0..<(u32)rt.atom_hash_size:
            var h = old_hash[i]
            while h != 0:
                let p = atom_array_get(rt, h)
                let hash_next1 = p.hash_next
                # add in new hash table
                let j = p.hash & new_hash_mask
                p.hash_next = new_hash[j]
                new_hash[j] = h
                h = hash_next1
        js_free_rt(rt, old_hash)
    rt.atom_hash = new_hash
    rt.atom_hash_size = new_hash_size
    rt.atom_count_resize = js_atom_count_resize(new_hash_size)
    return 0

func js_init_atoms(rt: Runtime*) -> i32:
    rt.atom_hash_size = 0
    rt.atom_hash = none
    rt.atom_count = 0
    rt.atom_size = 0
    rt.atom_free_index = 0
    if js_resize_atom_hash(rt, 512) != 0:  # there are at least 504 predefined atoms
        return -1

    var p: usize = 0
    for i: u32 in 1..<atom_end:
        var atom_type: u8
        if i == atom_Private_brand:
            atom_type = js_atom_type_private
        elif i >= atom_Symbol_toPrimitive:
            atom_type = js_atom_type_symbol
        else:
            atom_type = js_atom_type_string
        let len = cutils.strlen(&js_atom_init[p])
        if js_new_atom_init_raw(rt, &js_atom_init[p], (i32)len, atom_type) == no_atom:
            return -1
        p = p + len + 1
    return 0

# mark: Reference counts and kinds ==============================================================

func js_dup_atom_rt(rt: Runtime*, v: Atom) -> Atom:
    if not js_atom_is_const_raw(v):
        let p = atom_array_get(rt, v)
        js_rc(p).ref_count += 1
    return v

## A new reference to the atom `v` (JS_DupAtom).
pub func js_dup_atom(ctx: Context*, v: Atom) -> Atom:
    if not js_atom_is_const_raw(v):
        let rt = ctx.rt
        let p = atom_array_get(rt, v)
        js_rc(p).ref_count += 1
    return v

func js_atom_get_kind(ctx: Context*, v: Atom) -> AtomKind:
    let rt = ctx.rt
    if js_atom_is_tagged_int_raw(v):
        return AtomKind.string
    let p = atom_array_get(rt, v)
    let atom_type = p.atom_type
    if atom_type == js_atom_type_string:
        return AtomKind.string
    elif atom_type == js_atom_type_global_symbol:
        return AtomKind.symbol
    elif atom_type == js_atom_type_symbol:
        if p.hash == js_atom_hash_private:
            return AtomKind.private
        else:
            return AtomKind.symbol
    trap("JS_AtomGetKind: invalid atom type")

func js_atom_is_string(ctx: Context*, v: Atom) -> bool:
    return js_atom_get_kind(ctx, v) == AtomKind.string

func js_get_atom_index(rt: Runtime*, p: AtomStruct*) -> Atom:
    var i = p.hash_next  # atom_index
    if p.atom_type != js_atom_type_symbol:
        let atom_hash = atom_hash_table(rt)
        i = atom_hash[p.hash & (u32)(rt.atom_hash_size - 1)]
        var p1 = atom_array_get(rt, i)
        while p1 != p:
            assert(i != 0)
            i = p1.hash_next
            p1 = atom_array_get(rt, i)
    return i

# mark: Interning ===============================================================================

# The `done` exit of __JS_NewAtom: release 'str' and answer `i`.
func js_new_atom_release(rt: Runtime*, str_: String*?, i: Atom) -> Atom:
    if let s = str_:
        js_free_string(rt, s)
    return i

# The `fail` exit of __JS_NewAtom: release 'str' and answer no_atom.
func js_new_atom_fail(rt: Runtime*, str_: String*?) -> Atom:
    return js_new_atom_release(rt, str_, no_atom)

# string case (internal). Return no_atom if error. 'str' is freed. A none 'str' makes a
# symbol without description.
func js_new_atom_raw(rt: Runtime*, str_: String*?, atom_type0: u8) -> Atom:
    var atom_type = atom_type0
    var h: u32
    var h1: u32
    var i: u32

    if atom_type < js_atom_type_symbol:
        # str is not none
        let s = str_ else trap("__JS_NewAtom: a string atom needs a string")
        if s.atom_type == atom_type:
            # str is the atom, return its index
            i = js_get_atom_index(rt, s)
            # reduce string refcount and increase atom's unless constant
            if js_atom_is_const_raw(i):
                js_rc(s).ref_count -= 1
            return i
        # try and locate an already registered atom
        let len = s.len
        h = hash_string(s, atom_type)
        h &= js_atom_hash_mask
        h1 = h & (u32)(rt.atom_hash_size - 1)
        i = atom_hash_table(rt)[h1]
        while i != 0:
            let p = atom_array_get(rt, i)
            if (p.hash == h and p.atom_type == atom_type and p.len == len and js_string_memcmp(p, 0, s, 0, (i32)len) == 0):
                if not js_atom_is_const_raw(i):
                    js_rc(p).ref_count += 1
                return js_new_atom_release(rt, str_, i)
            i = p.hash_next
    else:
        h1 = 0  # avoid warning
        if atom_type == js_atom_type_symbol:
            h = 0
        else:
            h = js_atom_hash_private
            atom_type = js_atom_type_symbol

    if rt.atom_free_index == 0:
        # allow new atom entries

        # alloc new with size progression 3/2:
        # 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066 1599 2398 3597 5395 8092
        # preallocating space for predefined atoms (at least 504).
        let new_size = (u32)cutils.max_int(711, rt.atom_size * 3 // 2)
        if new_size > js_atom_max:
            return js_new_atom_fail(rt, str_)
        # XXX: should use realloc2 to use slack space
        var old_array: void*? = none
        if let a = rt.atom_array:
            old_array = a
        let array_size = memory.size_of(AtomStruct*) * (usize)new_size
        let mem = js_realloc_rt(rt, old_array, array_size) else return js_new_atom_fail(rt, str_)
        let new_array = (AtomStruct**)mem
        # Note: the atom 0 is not used
        var start = (u32)rt.atom_size
        if start == 0:
            # no_atom entry
            if let pm = js_mallocz_rt(rt, memory.size_of(AtomStruct)):
                let p = (AtomStruct*)pm
                js_rc(p).ref_count = 1  # not refcounted
                p.atom_type = js_atom_type_symbol
                new_array[0] = p
                rt.atom_count += 1
                start = 1
            else:
                js_free_rt(rt, new_array)
                return js_new_atom_fail(rt, str_)
        rt.atom_size = (i32)new_size
        rt.atom_array = new_array
        rt.atom_free_index = (i32)start
        for k in start..<new_size:
            var next: u32
            if k == new_size - 1:
                next = 0
            else:
                next = k + 1
            new_array[k] = atom_set_free(next)

    var p: AtomStruct* = ---
    if let s = str_:
        if s.atom_type == 0:
            p = s
            p.atom_type = atom_type
        else:
            let data_size = ((usize)s.len << (usize)s.is_wide_char) + 1 - (usize)s.is_wide_char
            let size = memory.size_of(String) + data_size
            let pm = js_malloc_rt(rt, size) else return js_new_atom_fail(rt, str_)
            p = (AtomStruct*)pm
            js_rc(p).ref_count = 1
            p.is_wide_char = s.is_wide_char
            p.len = s.len
            _ = cutils.memcpy(str8(p), str8(s), data_size)
            js_free_string(rt, s)
    else:
        let pm = js_malloc_rt(rt, memory.size_of(AtomStruct)) else return no_atom  # empty wide string
        p = (AtomStruct*)pm
        js_rc(p).ref_count = 1
        p.is_wide_char = true  # Hack to represent NULL as a JSString
        p.len = 0

    # use an already free entry
    let atom_array = rt.atom_array else trap("atom table not initialized")
    i = (u32)rt.atom_free_index
    rt.atom_free_index = (i32)atom_get_free(atom_array[i])
    atom_array[i] = p

    p.hash = h
    p.hash_next = i  # atom_index
    p.atom_type = atom_type

    rt.atom_count += 1

    if atom_type != js_atom_type_symbol:
        let atom_hash = atom_hash_table(rt)
        p.hash_next = atom_hash[h1]
        atom_hash[h1] = i
        if rt.atom_count >= rt.atom_count_resize:
            _ = js_resize_atom_hash(rt, rt.atom_hash_size * 2)

    return i

# only works with zero terminated 8 bit strings
func js_new_atom_init_raw(rt: Runtime*, str_: const u8*, len: i32, atom_type: u8) -> Atom:
    let p = js_alloc_string_rt(rt, len, false) else return no_atom
    _ = cutils.memcpy(str8(p), str_, (usize)len)
    str8(p)[len] = 0
    return js_new_atom_raw(rt, p, atom_type)

# Warning: str must be ASCII only. Like QuickJS, the lookup is always for a string atom
# whatever `atom_type` says.
func js_find_atom_raw(rt: Runtime*, str_: const u8*, len: usize, atom_type: u8) -> Atom:
    var h = hash_string8(str_, len, js_atom_type_string)
    h &= js_atom_hash_mask
    let h1 = h & (u32)(rt.atom_hash_size - 1)
    var i = atom_hash_table(rt)[h1]
    while i != 0:
        let p = atom_array_get(rt, i)
        if (p.hash == h and p.atom_type == js_atom_type_string and (usize)p.len == len and not p.is_wide_char and cutils.memcmp(str8(p), str_, len) == 0):
            if not js_atom_is_const_raw(i):
                js_rc(p).ref_count += 1
            return i
        i = p.hash_next
    return no_atom

# mark: Freeing =================================================================================

func js_free_atom_struct(rt: Runtime*, p: AtomStruct*):
    # no_atom is not refcounted: js_atom_is_const_raw() includes 0
    var i = p.hash_next  # atom_index
    if p.atom_type != js_atom_type_symbol:
        let atom_hash = atom_hash_table(rt)
        let h0 = p.hash & (u32)(rt.atom_hash_size - 1)
        i = atom_hash[h0]
        var p1 = atom_array_get(rt, i)
        if p1 == p:
            atom_hash[h0] = p1.hash_next
        else:
            while true:
                assert(i != 0)
                let p0 = p1
                i = p1.hash_next
                p1 = atom_array_get(rt, i)
                if p1 == p:
                    p0.hash_next = p1.hash_next
                    break
    # insert in free atom list
    let atom_array = rt.atom_array else trap("atom table not initialized")
    atom_array[i] = atom_set_free((u32)rt.atom_free_index)
    rt.atom_free_index = (i32)i
    # free the string structure, unless live weak references are still present on this
    # object (a symbol whose hash, its weakref_count, is not zero): keep it then
    if not (p.atom_type == js_atom_type_symbol and p.hash != js_atom_hash_private and p.hash != 0):
        js_free_rt(rt, p)
    rt.atom_count -= 1
    assert(rt.atom_count >= 0)

func js_free_atom_raw(rt: Runtime*, i: u32):
    let p = atom_array_get(rt, i)
    js_rc(p).ref_count -= 1
    if js_rc(p).ref_count > 0:
        return
    js_free_atom_struct(rt, p)