Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-js

Source of release 0.6.0

0.6.0 / src / engine / shapes.lucb

#==============================================================================================
#
#   shapes - Shapes: the shared prototype and property layout of objects
#
#   DESCRIPTION:
#       Port of quickjs.c "Shape support" (lines 5119-5612). A shape is followed in memory
#       by its hash table (`prop_hash_mask + 1` u32 entries, 1-based property indexes) and
#       then by its `prop_size` ShapeProperty entries; `get_shape_hash_table` and
#       `get_shape_prop` reach them. Shapes of objects built the same way are shared
#       through the runtime's shape hash table, keyed by the prototype and the sequence
#       of (atom, flags) pairs. The debug dumps JS_DumpShape and JS_DumpShapes are only
#       used under DUMP_SHAPES and are not ported.
#
#==============================================================================================

# mark: Layout ==================================================================================

## The byte size of a shape with `hash_size` hash entries and `prop_size` properties.
func get_shape_size(hash_size: usize, prop_size: usize) -> usize:
    return memory.size_of(Shape) + hash_size * memory.size_of(u32) + prop_size * memory.size_of(ShapeProperty)

## The shape's hash table (the C flexible member `hash_table`): `prop_hash_mask + 1`
## entries, each 0 or the 1-based index of the first property of that bucket.
func get_shape_hash_table(sh: Shape*) -> u32*:
    return (u32*)((u8*)sh + memory.size_of(Shape))

## The shape's properties, after its hash table.
func get_shape_prop(sh: Shape*) -> ShapeProperty*:
    return (ShapeProperty*)(get_shape_hash_table(sh) + (usize)sh.prop_hash_mask + 1)

# mark: The shape hash table ====================================================================

## Allocate the runtime's empty shape hash table; -1 if out of memory (no exception).
func init_shape_hash(rt: Runtime*) -> i32:
    rt.shape_hash_bits = 4  # 16 shapes
    rt.shape_hash_size = 1 << rt.shape_hash_bits
    rt.shape_hash_count = 0
    let table = js_mallocz_rt(rt, memory.size_of(Shape*?) * (usize)rt.shape_hash_size) else return -1
    rt.shape_hash = (Shape*?*)table
    return 0

# same magic hash multiplier as the Linux kernel
func shape_hash(h: u32, val: u32) -> u32:
    return (h +% val) *% 0x9e370001

# truncate the shape hash to 'hash_bits' bits
func get_shape_hash(h: u32, hash_bits: i32) -> u32:
    return h >> (u32)(32 - hash_bits)

## The hash of an empty shape with prototype `proto`.
func shape_initial_hash(proto: Object*?) -> u32:
    var addr: usize = 0
    if let p = proto:
        addr = (usize)p
    var h = shape_hash(1, (u32)addr)
    if memory.size_of(usize) > 4:
        h = shape_hash(h, (u32)((u64)addr >> 32))
    return h

## The runtime's shape hash table (always allocated once the runtime exists).
func runtime_shape_hash(rt: Runtime*) -> Shape*?*:
    return rt.shape_hash else trap("the shape hash table is not allocated")

## Rehash every hashed shape into a table of 2^new_shape_hash_bits buckets; -1 if out of
## memory (no exception), leaving the old table in place.
func resize_shape_hash(rt: Runtime*, new_shape_hash_bits: i32) -> i32:
    let new_shape_hash_size: i32 = 1 << new_shape_hash_bits
    let raw = js_mallocz_rt(rt, memory.size_of(Shape*?) * (usize)new_shape_hash_size) else return -1
    let new_shape_hash = (Shape*?*)raw
    let old_shape_hash = runtime_shape_hash(rt)
    for i in 0..<(usize)rt.shape_hash_size:
        var cur = old_shape_hash[i]
        while let sh = cur:
            cur = sh.shape_hash_next
            let h = get_shape_hash(sh.hash, new_shape_hash_bits)
            sh.shape_hash_next = new_shape_hash[(usize)h]
            new_shape_hash[(usize)h] = sh
    js_free_rt(rt, old_shape_hash)
    rt.shape_hash_bits = new_shape_hash_bits
    rt.shape_hash_size = new_shape_hash_size
    rt.shape_hash = new_shape_hash
    return 0

## Insert `sh` in its bucket of the shape hash table.
func js_shape_hash_link(rt: Runtime*, sh: Shape*):
    let h = get_shape_hash(sh.hash, rt.shape_hash_bits)
    let table = runtime_shape_hash(rt)
    sh.shape_hash_next = table[(usize)h]
    table[(usize)h] = sh
    rt.shape_hash_count += 1

## Remove `sh` from its bucket of the shape hash table; it must be there.
func js_shape_hash_unlink(rt: Runtime*, sh: Shape*):
    let h = get_shape_hash(sh.hash, rt.shape_hash_bits)
    var psh: Shape*?* = runtime_shape_hash(rt) + (usize)h
    while true:
        let cur = *psh else trap("shape not in the shape hash table")
        if cur == sh:
            break
        psh = &cur.shape_hash_next
    *psh = sh.shape_hash_next
    rt.shape_hash_count -= 1

# mark: Creating and freeing shapes =============================================================

# create a new empty shape with prototype 'proto'. It is not hashed
func js_new_shape_nohash(ctx: Context*, proto: Object*?, hash_size: i32, prop_size: i32) -> Shape*!:
    let rt = ctx.rt
    let sh = (Shape*)(try js_malloc(ctx, get_shape_size((usize)hash_size, (usize)prop_size)))
    js_rc(sh).ref_count = 1
    add_gc_object(rt, &sh.header, GCObjectType.shape)
    if let p = proto:
        _ = js_dup_value(ctx, js_mkptr(Tag.object, p))
    sh.proto = proto
    _ = cutils.memset(get_shape_hash_table(sh), 0, memory.size_of(u32) * (usize)hash_size)
    sh.prop_hash_mask = (u32)hash_size - 1
    sh.prop_size = prop_size
    sh.prop_count = 0
    sh.deleted_prop_count = 0
    sh.is_hashed = 0
    sh.shape_hash_next = none
    return sh

# create a new empty shape with prototype 'proto'
func js_new_shape2(ctx: Context*, proto: Object*?, hash_size: i32, prop_size: i32) -> Shape*!:
    let rt = ctx.rt

    # resize the shape hash table if necessary
    if 2 * (rt.shape_hash_count + 1) > rt.shape_hash_size:
        _ = resize_shape_hash(rt, rt.shape_hash_bits + 1)

    let sh = try js_new_shape_nohash(ctx, proto, hash_size, prop_size)

    # insert in the hash table
    sh.hash = shape_initial_hash(proto)
    sh.is_hashed = 1
    js_shape_hash_link(ctx.rt, sh)
    return sh

## A new hashed empty shape with prototype `proto` and the initial sizes.
func js_new_shape(ctx: Context*, proto: Object*?) -> Shape*!:
    return try js_new_shape2(ctx, proto, js_prop_initial_hash_size, js_prop_initial_size)

# The shape is cloned. The new shape is not inserted in the shape
# hash table
func js_clone_shape(ctx: Context*, sh1: Shape*) -> Shape*!:
    let hash_size = sh1.prop_hash_mask + 1
    let size = get_shape_size((usize)hash_size, (usize)sh1.prop_size)
    let sh = (Shape*)(try js_malloc(ctx, size))
    _ = cutils.memcpy((u8*)sh + memory.size_of(GCObjectHeader), (u8*)sh1 + memory.size_of(GCObjectHeader),
                      size - memory.size_of(GCObjectHeader))
    js_rc(sh).ref_count = 1
    add_gc_object(ctx.rt, &sh.header, GCObjectType.shape)
    sh.is_hashed = 0
    if let proto = sh.proto:
        _ = js_dup_value(ctx, js_mkptr(Tag.object, proto))
    let pr = get_shape_prop(sh)
    for i in 0..<(usize)sh.prop_count:
        _ = js_dup_atom(ctx, pr[i].atom)
    return sh

## A new reference to `sh`.
func js_dup_shape(sh: Shape*) -> Shape*:
    js_rc(sh).ref_count += 1
    return sh

## Free a shape whose reference count reached zero.
func js_free_shape0(rt: Runtime*, sh: Shape*):
    assert(js_rc(sh).ref_count == 0)
    if sh.is_hashed != 0:
        js_shape_hash_unlink(rt, sh)
    if let proto = sh.proto:
        js_free_value_rt(rt, js_mkptr(Tag.object, proto))
    let pr = get_shape_prop(sh)
    for i in 0..<(usize)sh.prop_count:
        js_free_atom_rt(rt, pr[i].atom)
    remove_gc_object(&sh.header)
    js_free_rt(rt, sh)

## Release a reference to `sh`; the last one frees it.
func js_free_shape(rt: Runtime*, sh: Shape*):
    let rc = js_rc(sh)
    rc.ref_count -= 1
    if rc.ref_count <= 0:
        js_free_shape0(rt, sh)

## Release a reference to `sh` if there is one.
func js_free_shape_null(rt: Runtime*, sh: Shape*?):
    if let s = sh:
        js_free_shape(rt, s)

# mark: Growing and compacting ==================================================================

## Rebuild the hash chains of the first `count` properties of `sh` in its (cleared) hash
## table of mask `hash_mask`.
func rehash_shape_props(sh: Shape*, hash_mask: u32, count: u32):
    let hash_table = get_shape_hash_table(sh)
    let pr = get_shape_prop(sh)
    for i in 0..<count:
        if pr[i].atom != no_atom:
            let h = (usize)(pr[i].atom & hash_mask)
            pr[i].hash_next = hash_table[h]
            hash_table[h] = i + 1

# make space to hold at least 'count' properties
func resize_properties(ctx: Context*, psh: Shape**, p: Object*?, count: u32) -> !:
    var sh = *psh
    let new_size = (u32)cutils.max_int((i32)count, sh.prop_size * 3 // 2)
    # Reallocate prop array first to avoid crash or size inconsistency
    # in case of memory allocation failure
    if let obj = p:
        let new_prop = try js_realloc(ctx, obj.prop, memory.size_of(Property) * (usize)new_size)
        # js_realloc of a non-zero size never answers none
        obj.prop = (Property*)(new_prop else trap("js_realloc answered none"))
    var new_hash_size = sh.prop_hash_mask + 1
    while new_hash_size < new_size:
        new_hash_size = 2 * new_hash_size
    # resize the property shapes. Using js_realloc() is not possible in
    # case the GC runs during the allocation
    let old_sh = sh
    sh = (Shape*)(try js_malloc(ctx, get_shape_size((usize)new_hash_size, (usize)new_size)))
    remove_gc_object(&old_sh.header)

    js_rc(sh).ref_count = 1
    add_gc_object(ctx.rt, &sh.header, GCObjectType.shape)

    _ = cutils.memcpy((u8*)sh + memory.size_of(GCObjectHeader), (u8*)old_sh + memory.size_of(GCObjectHeader),
                      memory.size_of(Shape) - memory.size_of(GCObjectHeader))

    if new_hash_size != sh.prop_hash_mask + 1:
        # resize the hash table and the properties
        let new_hash_mask = new_hash_size - 1
        sh.prop_hash_mask = new_hash_mask
        _ = cutils.memset(get_shape_hash_table(sh), 0, memory.size_of(u32) * (usize)new_hash_size)
        _ = cutils.memcpy(get_shape_prop(sh), get_shape_prop(old_sh),
                          memory.size_of(ShapeProperty) * (usize)old_sh.prop_count)
        rehash_shape_props(sh, new_hash_mask, (u32)sh.prop_count)
    else:
        # just copy the previous hash table and the properties
        _ = cutils.memcpy(get_shape_hash_table(sh), get_shape_hash_table(old_sh),
                          memory.size_of(u32) * (usize)new_hash_size)

        _ = cutils.memcpy(get_shape_prop(sh), get_shape_prop(old_sh),
                          memory.size_of(ShapeProperty) * (usize)old_sh.prop_count)
    js_free(ctx, old_sh)
    *psh = sh
    sh.prop_size = (i32)new_size

# remove the deleted properties.
func compact_properties(ctx: Context*, p: Object*) -> !:
    var sh = p.shape
    assert(sh.is_hashed == 0)

    let new_size = (u32)cutils.max_int(js_prop_initial_size, sh.prop_count - sh.deleted_prop_count)
    assert(new_size <= (u32)sh.prop_size)

    var new_hash_size = sh.prop_hash_mask + 1
    while (new_hash_size // 2) >= new_size:
        new_hash_size = new_hash_size // 2
    let new_hash_mask = new_hash_size - 1

    # resize the hash table and the properties
    let old_sh = sh
    sh = (Shape*)(try js_malloc(ctx, get_shape_size((usize)new_hash_size, (usize)new_size)))
    remove_gc_object(&old_sh.header)

    js_rc(sh).ref_count = 1
    add_gc_object(ctx.rt, &sh.header, GCObjectType.shape)

    _ = cutils.memcpy((u8*)sh + memory.size_of(GCObjectHeader), (u8*)old_sh + memory.size_of(GCObjectHeader),
                      memory.size_of(Shape) - memory.size_of(GCObjectHeader))

    let hash_table = get_shape_hash_table(sh)
    _ = cutils.memset(hash_table, 0, memory.size_of(u32) * (usize)new_hash_size)
    sh.prop_hash_mask = new_hash_mask

    var j: u32 = 0
    let old_pr = get_shape_prop(old_sh)
    let pr = get_shape_prop(sh)
    let prop = p.prop
    for i in 0..<(usize)sh.prop_count:
        if old_pr[i].atom != no_atom:
            pr[j].atom = old_pr[i].atom
            pr[j].flags = old_pr[i].flags
            let h = (usize)(old_pr[i].atom & new_hash_mask)
            pr[j].hash_next = hash_table[h]
            hash_table[h] = j + 1
            prop[j] = prop[i]
            j += 1
    assert(j == (u32)(sh.prop_count - sh.deleted_prop_count))
    sh.prop_size = (i32)new_size
    sh.deleted_prop_count = 0
    sh.prop_count = (i32)j

    p.shape = sh
    js_free(ctx, old_sh)

    # reduce the size of the object properties
    # (a failure is not reported, as in QuickJS: the larger array stays in place)
    let new_prop = js_realloc(ctx, p.prop, memory.size_of(Property) * (usize)new_size) catch failure:
        return
    # js_realloc of a non-zero size never answers none
    p.prop = (Property*)(new_prop else trap("js_realloc answered none"))

## Append the property (`atom`, `prop_flags`) to `*psh`, growing it (and `p`'s property
## array when `p` is given) when full. The object property at p.prop[prop_count - 1] is
## left uninitialized.
func add_shape_property(ctx: Context*, psh: Shape**, p: Object*?, atom: Atom, prop_flags: i32) -> !:
    let rt = ctx.rt
    var sh = *psh
    var new_shape_hash: u32 = 0

    # update the shape hash
    if sh.is_hashed != 0:
        js_shape_hash_unlink(rt, sh)
        new_shape_hash = shape_hash(shape_hash(sh.hash, atom), (u32)prop_flags)

    if sh.prop_count >= sh.prop_size:
        resize_properties(ctx, psh, p, (u32)sh.prop_count + 1) catch failure:
            # in case of error, reinsert in the hash table.
            # sh is still valid if resize_properties() failed
            if sh.is_hashed != 0:
                js_shape_hash_link(rt, sh)
            error(failure.code, failure.message)
        sh = *psh
    if sh.is_hashed != 0:
        sh.hash = new_shape_hash
        js_shape_hash_link(rt, sh)
    # Initialize the new shape property.
    # The object property at p->prop[sh->prop_count] is uninitialized
    let pr = get_shape_prop(sh) + (usize)sh.prop_count
    sh.prop_count += 1
    pr.atom = js_dup_atom(ctx, atom)
    pr.flags = (u8)prop_flags
    # add in hash table
    let hash_mask = sh.prop_hash_mask
    let h = (usize)(atom & hash_mask)
    let hash_table = get_shape_hash_table(sh)
    pr.hash_next = hash_table[h]
    hash_table[h] = (u32)sh.prop_count

# mark: Finding shared shapes ===================================================================

# find a hashed empty shape matching the prototype. Return NULL if
# not found
func find_hashed_shape_proto(rt: Runtime*, proto: Object*?) -> Shape*?:
    let h = shape_initial_hash(proto)
    let h1 = get_shape_hash(h, rt.shape_hash_bits)
    var cur = runtime_shape_hash(rt)[(usize)h1]
    while let sh1 = cur:
        if sh1.hash == h and sh1.proto == proto and sh1.prop_count == 0:
            return sh1
        cur = sh1.shape_hash_next
    return none

# find a hashed shape matching sh + (prop, prop_flags). Return NULL if
# not found
func find_hashed_shape_prop(rt: Runtime*, sh: Shape*, atom: Atom, prop_flags: i32) -> Shape*?:
    var h = sh.hash
    h = shape_hash(h, atom)
    h = shape_hash(h, (u32)prop_flags)
    let h1 = get_shape_hash(h, rt.shape_hash_bits)
    var cur = runtime_shape_hash(rt)[(usize)h1]
    next: while let sh1 = cur:
        cur = sh1.shape_hash_next
        # we test the hash first so that the rest is done only if the
        # shapes really match
        let n = (usize)sh.prop_count
        if sh1.hash == h and sh1.proto == sh.proto and (usize)sh1.prop_count == n + 1:
            let prop = get_shape_prop(sh)
            let prop1 = get_shape_prop(sh1)
            for i in 0..<n:
                if prop1[i].atom != prop[i].atom or prop1[i].flags != prop[i].flags:
                    continue next
            if prop1[n].atom != atom or (i32)prop1[n].flags != prop_flags:
                continue next
            return sh1
    return none