dymokomi/luce-js
Source of release 0.6.0
0.6.0 / src / engine / map_records.lucb
#==============================================================================================
#
# map_records - Map, Set, WeakMap and WeakSet: weak references, hashing and records
#
# DESCRIPTION:
# Port of quickjs.c "Set/Map/WeakSet/WeakMap" (lines 51688-52129): the weak
# reference counts of objects and symbols, the Map/Set/WeakMap/WeakSet constructor,
# the key hash, and the records of a MapState: finding, adding, resizing the hash
# table and deleting (a record an iterator holds stays as an empty "zombie" until
# released). The key of a weak map record holds a weak reference; map_delete_weakrefs
# drops the records whose key died.
#
#==============================================================================================
# mark: Weak references =========================================================================
## Whether `val` can be held weakly: an object or a symbol that is not registered and not
## private (js_weakref_is_target).
func js_weakref_is_target(val: Value) -> bool:
if val.tag == Tag.object:
return true
elif val.tag == Tag.symbol:
let p: AtomStruct* = val.u.string
if p.atom_type == js_atom_type_symbol and p.hash != js_atom_hash_private:
return true
return false
# JS_UNDEFINED is considered as a live weakref
# XXX: add a specific JSWeakRef value type ?
## Whether the weakly held `val` is still alive (js_weakref_is_live).
func js_weakref_is_live(val: Value) -> bool:
if js_is_undefined(val):
return true
return js_rc(val.u.ptr).ref_count != 0
## Release a weak reference to `val`, which can be undefined; the structure of a dead
## object or symbol is freed with its last weak reference (js_weakref_free).
func js_weakref_free(rt: Runtime*, val: Value):
if val.tag == Tag.object:
let p = val.u.obj
assert(p.weakref_count >= 1)
p.weakref_count -= 1
# 'mark' is tested to avoid freeing the object structure when it is about to be freed
# in a cycle or in free_zero_refcount()
if p.weakref_count == 0 and js_rc(p).ref_count == 0 and js_rc(p).mark() == 0:
js_free_rt(rt, p)
elif val.tag == Tag.symbol:
let p = val.u.string
assert(p.hash >= 1)
p.hash -= 1
if p.hash == 0 and js_rc(p).ref_count == 0:
# can remove the dummy structure
js_free_rt(rt, p)
## A weak reference to `val`, which must be an object, a symbol or undefined (see
## js_weakref_is_target) (js_weakref_new).
func js_weakref_new(ctx: Context*, val: Value) -> Value:
if val.tag == Tag.object:
let p = val.u.obj
p.weakref_count += 1
elif val.tag == Tag.symbol:
let p = val.u.string
# XXX: could return an exception if too many references
assert(p.hash < js_atom_hash_mask - 2)
p.hash += 1
else:
assert(js_is_undefined(val))
return val
# mark: The constructor =========================================================================
## The magic of the Map/Set builtins: bit 0 for a Set, bit 1 for a weak one; ClassId.map
## plus the magic is the class (MAGIC_SET, MAGIC_WEAK).
let magic_set: i32 = 1 << 0
let magic_weak: i32 = 1 << 1
## Free the value `*pv`. A `defer` target: the pointer is captured when the defer is
## registered and the value is read when it runs, as C's `goto fail` cleanup reads it.
func js_free_value_at(ctx: Context*, pv: const Value*):
js_free_value(ctx, *pv)
## One step of the constructor's loop: call `adder` on `obj` with `item` (a Set) or with its
## elements 0 and 1 (a Map). Takes ownership of `item`.
func js_map_constructor_add(ctx: Context*, adder: Value, obj: Value, item: Value, is_set: bool) -> !:
defer js_free_value(ctx, item)
if is_set:
var arg = item
let ret = try js_call(ctx, adder, obj, 1, &arg)
js_free_value(ctx, ret)
else:
if not js_is_object(item):
try js_throw_type_error_not_an_object(ctx)
let key = try js_get_property_uint32(ctx, item, 0)
defer js_free_value(ctx, key)
let value = try js_get_property_uint32(ctx, item, 1)
defer js_free_value(ctx, value)
var args: Value[2] = [key, value]
let ret = try js_call(ctx, adder, obj, 2, &args[0])
js_free_value(ctx, ret)
## Add the entries of the iterable `arr` to the new Map or Set `obj` through its own
## `set` or `add` method.
func js_map_constructor_fill(ctx: Context*, obj: Value, arr: Value, is_set: bool) -> !:
var adder = js_undefined()
var iter = js_undefined()
var next_method = js_undefined()
defer js_free_value_at(ctx, &adder)
defer js_free_value_at(ctx, &iter)
defer js_free_value_at(ctx, &next_method)
adder = try js_get_property(ctx, obj, atom_add if is_set else atom_set)
if not js_is_function(ctx, adder):
try js_throw_type_error(ctx, "set/add is not a function")
iter = try js_get_iterator(ctx, arr, false)
next_method = try js_get_property(ctx, iter, atom_next)
while true:
var done = false
var no_args = js_undefined()
let item = try js_iterator_next(ctx, iter, next_method, 0, &no_args, &done)
if done:
break
js_map_constructor_add(ctx, adder, obj, item, is_set) catch failure:
# close the iterator object, preserving pending exception
js_close_iterator_on_failure(ctx, iter)
error(failure.code, failure.message)
## new Map/Set/WeakMap/WeakSet(iterable); `magic` holds magic_set and magic_weak
## (js_map_constructor).
func js_map_constructor(ctx: Context*, new_target: Value, argc: i32, argv: Value*, magic: i32) -> Value!:
let is_set = (magic & magic_set) != 0
let is_weak = (magic & magic_weak) != 0
let obj = try js_create_from_ctor(ctx, new_target, (u32)((i32)ClassId.map + magic))
errdefer js_free_value(ctx, obj)
let raw = try js_mallocz(ctx, memory.size_of(MapState))
let s = (MapState*)raw
cutils.init_list_head(&s.records)
s.is_weak = is_weak
if is_weak:
s.weakref_header.weakref_type = WeakRefHeaderType.map
cutils.list_add_tail(&s.weakref_header.link, &ctx.rt.weakref_list)
js_set_opaque(obj, s)
s.hash_bits = 1
s.hash_size = (u32)1 << (u32)s.hash_bits
let table = try js_mallocz(ctx, memory.size_of(MapRecord*?) * (usize)s.hash_size)
s.hash_table = (MapRecord*?*)table
s.record_count_threshold = 4
var arr = js_undefined()
if argc > 0:
arr = argv[0]
if not js_is_undefined(arr) and not js_is_null(arr):
try js_map_constructor_fill(ctx, obj, arr, is_set)
return obj
# mark: Hashing =================================================================================
# XXX: could normalize strings to speed up comparison
## The key a record is stored under: -0.0 becomes +0 (map_normalize_key).
func map_normalize_key(ctx: Context*, key: Value) -> Value:
# convert -0.0 to +0.0
if js_tag_is_float64(key.tag) and js_value_get_float64(key) == 0.0:
return js_new_int32(0)
return key
## map_normalize_key of a borrowed key (map_normalize_key_const).
func map_normalize_key_const(ctx: Context*, key: Value) -> Value:
return map_normalize_key(ctx, key)
# hash multipliers, same as the Linux kernel (see Knuth vol 3, section 6.4, exercise 9)
let hash_mul32: u32 = 0x61C88647
let hash_mul64: u64 = 0x61C8864680B583EB
## The top `hash_bits` bits of `a` times the 32-bit multiplier (map_hash32).
func map_hash32(a: u32, hash_bits: i32) -> u32:
return (a *% hash_mul32) >> (u32)(32 - hash_bits)
## The top `hash_bits` bits of `a` times the 64-bit multiplier (map_hash64).
func map_hash64(a: u64, hash_bits: i32) -> u32:
return (u32)((a *% hash_mul64) >> (u64)(64 - hash_bits))
## The hash of an address; pointers are 64 bits wide on the port's targets
## (map_hash_pointer).
func map_hash_pointer(a: usize, hash_bits: i32) -> u32:
return map_hash64((u64)a, hash_bits)
## A tag as the unsigned 32-bit number C's JS_VALUE_GET_NORM_TAG gives when hashed.
func map_tag_bits(tag: Tag) -> u32:
return (u32)(i64)tag
## The hash of a number: of its float64 bits, so that 1 and 1.0 agree.
func map_hash_float64(d: f64, hash_bits: i32) -> u32:
return map_hash64(cutils.float64_as_uint64(d) ^ (u64)map_tag_bits(Tag.float64), hash_bits)
## The hash of a big integer's limbs.
func map_hash_bigint(p: const BigInt*, hash_bits: i32) -> u32:
let tab = js_bigint_tab(p)
var h: u32 = 1
var i = (i32)p.len - 1
while i >= 0:
h = h *% 263 +% tab[(usize)i]
i -= 1
# the final step is necessary otherwise h mod n only depends of p->tab[i] mod n
return map_hash32(h ^ map_tag_bits(Tag.big_int), hash_bits)
# XXX: better hash ?
## The hash of `key` on `hash_bits` bits; precondition: 1 <= hash_bits <= 32
## (map_hash_key).
func map_hash_key(key: Value, hash_bits: i32) -> u32:
var h: u32 = 0
match key.tag:
.boolean:
h = map_hash32((u32)js_value_get_int(key) ^ map_tag_bits(Tag.boolean), hash_bits)
.string:
h = map_hash32(hash_string(key.u.string, 0) ^ map_tag_bits(Tag.string), hash_bits)
.string_rope:
h = map_hash32(hash_string_rope(key, 0) ^ map_tag_bits(Tag.string), hash_bits)
.object, .symbol:
h = map_hash_pointer((usize)key.u.ptr ^ (usize)map_tag_bits(key.tag), hash_bits)
.int:
h = map_hash_float64(f64(js_value_get_int(key)), hash_bits)
.float64:
var d = js_value_get_float64(key)
# normalize the NaN
if d != d:
d = f64.bits(0x7ff8000000000000)
h = map_hash_float64(d, hash_bits)
.short_big_int:
var buf: BigIntBuf = ---
h = map_hash_bigint(js_bigint_set_short(&buf, key), hash_bits)
.big_int:
h = map_hash_bigint(key.u.big_int, hash_bits)
_:
h = 0
return h
# mark: Records =================================================================================
## The hash table of `s`, allocated by the constructor.
func map_hash_table(s: MapState*) -> MapRecord*?*:
return s.hash_table else trap("map without a hash table")
## The record of the list link `el` (list_entry(el, JSMapRecord, link)).
func map_record_of(el: cutils.ListHead*) -> MapRecord*:
return (MapRecord*)((u8*)el - memory.offset_of(MapRecord, link))
## The link after `el` in a record list.
func map_next_link(el: cutils.ListHead*) -> cutils.ListHead*:
return el.next else trap("map records: unlinked list")
## Whether the record can no longer match a key: deleted, or its weak key died.
func map_record_is_dead(s: MapState*, mr: MapRecord*) -> bool:
return mr.empty or (s.is_weak and not js_weakref_is_live(mr.key))
## The live record of `key` in `s`, or none (map_find_record).
func map_find_record(ctx: Context*, s: MapState*, key: Value) -> MapRecord*?:
let h = map_hash_key(key, s.hash_bits)
var cur = map_hash_table(s)[(usize)h]
while let mr = cur:
# a dead record cannot match
if not map_record_is_dead(s, mr) and js_same_value_zero(ctx, mr.key, key):
return mr
cur = mr.hash_next
return none
## Double the hash table of `s` (up to 2^31 entries) and rehash the live records
## (map_hash_resize). An allocation failure leaves the table as it was.
func map_hash_resize(ctx: Context*, s: MapState*):
# XXX: no reporting of memory allocation failure
let new_hash_bits = cutils.min_int(s.hash_bits + 1, 31)
let new_hash_size: u32 = (u32)1 << (u32)new_hash_bits
let raw = js_realloc(ctx, map_hash_table(s), memory.size_of(MapRecord*?) * (usize)new_hash_size) catch: return
let new_hash_table = (MapRecord*?*)(raw else return)
_ = cutils.memset(new_hash_table, 0, memory.size_of(MapRecord*?) * (usize)new_hash_size)
var el = map_next_link(&s.records)
while el != &s.records:
let mr = map_record_of(el)
if not map_record_is_dead(s, mr):
let h = map_hash_key(mr.key, new_hash_bits)
mr.hash_next = new_hash_table[(usize)h]
new_hash_table[(usize)h] = mr
el = map_next_link(el)
s.hash_table = new_hash_table
s.hash_bits = new_hash_bits
s.hash_size = new_hash_size
s.record_count_threshold = new_hash_size *% 2
## A new record of `key` in `s`, its value to be set by the caller; the key is held weakly
## in a weak map (map_add_record).
func map_add_record(ctx: Context*, s: MapState*, key: Value) -> MapRecord*!:
let raw = try js_malloc(ctx, memory.size_of(MapRecord))
let mr = (MapRecord*)raw
mr.ref_count = 1
mr.empty = false
if s.is_weak:
mr.key = js_weakref_new(ctx, key)
else:
mr.key = js_dup_value(ctx, key)
let h = map_hash_key(key, s.hash_bits)
let table = map_hash_table(s)
mr.hash_next = table[(usize)h]
table[(usize)h] = mr
cutils.list_add_tail(&mr.link, &s.records)
s.record_count += 1
if s.record_count >= s.record_count_threshold:
map_hash_resize(ctx, s)
return mr
## A new record of `key` with the value undefined, as a Set holds (set_add_record).
func set_add_record(ctx: Context*, s: MapState*, key: Value) -> MapRecord*!:
let mr = try map_add_record(ctx, s, key)
mr.value = js_undefined()
return mr
# warning: the record must be removed from the hash table before
## Delete the record `mr` of `s`: release its key and value, and free it unless an
## iterator holds it (map_delete_record_internal).
func map_delete_record_internal(rt: Runtime*, s: MapState*, mr: MapRecord*):
if mr.empty:
return
if s.is_weak:
js_weakref_free(rt, mr.key)
else:
js_free_value_rt(rt, mr.key)
js_free_value_rt(rt, mr.value)
mr.ref_count -= 1
if mr.ref_count == 0:
cutils.list_del(&mr.link)
js_free_rt(rt, mr)
else:
# keep a zombie record for iterators
mr.empty = true
mr.key = js_undefined()
mr.value = js_undefined()
s.record_count -= 1
## Release a reference an iterator held on the deleted record `mr` (map_decref_record).
func map_decref_record(rt: Runtime*, mr: MapRecord*):
mr.ref_count -= 1
if mr.ref_count == 0:
# the record can be safely removed
assert(mr.empty)
cutils.list_del(&mr.link)
js_free_rt(rt, mr)
## Delete the records of the weak map of `wh` whose key died (map_delete_weakrefs).
func map_delete_weakrefs(rt: Runtime*, wh: WeakRefHeader*):
let s = (MapState*)((u8*)wh - memory.offset_of(MapState, weakref_header))
var el = map_next_link(&s.records)
while el != &s.records:
let el1 = map_next_link(el)
let mr = map_record_of(el)
if not js_weakref_is_live(mr.key):
# even if key is not live it can be hashed as a pointer
let h = map_hash_key(mr.key, s.hash_bits)
var pmr: MapRecord*?* = &map_hash_table(s)[(usize)h]
while let mr1 = *pmr:
if mr1 == mr:
# remove from the hash table
*pmr = mr1.hash_next
break
pmr = &mr1.hash_next
# the entry may already be removed from the hash table if the map was resized
map_delete_record_internal(rt, s, mr)
el = el1