/*

* duk_hobject property access functionality.

*

* This is very central functionality for size, performance, and compliance.

* It is also rather intricate; see hobject-algorithms.rst for discussion on

* the algorithms and memory-management.rst for discussion on refcounts and

* side effect issues.

*

* Notes:

*

* - It might be tempting to assert "refcount nonzero" for objects

* being operated on, but that's not always correct: objects with

* a zero refcount may be operated on by the refcount implementation

* (finalization) for instance. Hence, no refcount assertions are made.

*

* - Many operations (memory allocation, identifier operations, etc)

* may cause arbitrary side effects (e.g. through GC and finalization).

* These side effects may invalidate duk_tval pointers which point to

* areas subject to reallocation (like value stack). Heap objects

* themselves have stable pointers. Holding heap object pointers or

* duk_tval copies is not problematic with respect to side effects;

* care must be taken when holding and using argument duk_tval pointers.

*

* - If a finalizer is executed, it may operate on the the same object

* we're currently dealing with. For instance, the finalizer might

* delete a certain property which has already been looked up and

* confirmed to exist. Ideally finalizers would be disabled if GC

* happens during property access. At the moment property table realloc

* disables finalizers, and all DECREFs may cause arbitrary changes so

* handle DECREF carefully.

*

* - The order of operations for a DECREF matters. When DECREF is executed,

* the entire object graph must be consistent; note that a refzero may

* lead to a mark-and-sweep through a refcount finalizer. Use NORZ macros

* and an explicit DUK_REFZERO_CHECK_xxx() if achieving correct order is hard.

*/

/*

* XXX: array indices are mostly typed as duk_uint32_t here; duk_uarridx_t

* might be more appropriate.

*/

#include "duk_internal.h"

/*

* Local defines

*/

#define DUK__NO_ARRAY_INDEX DUK_HSTRING_NO_ARRAY_INDEX

/* Marker values for hash part. */

#define DUK__HASH_UNUSED DUK_HOBJECT_HASHIDX_UNUSED

#define DUK__HASH_DELETED DUK_HOBJECT_HASHIDX_DELETED

/* Valstack space that suffices for all local calls, excluding any recursion

* into ECMAScript or Duktape/C calls (Proxy, getters, etc).

*/

#define DUK__VALSTACK_SPACE 10

/* Valstack space allocated especially for proxy lookup which does a

* recursive property lookup.

*/

#define DUK__VALSTACK_PROXY_LOOKUP 20

/*

* Local prototypes

*/

DUK_LOCAL_DECL duk_bool_t duk__check_arguments_map_for_get(duk_hthread *thr, duk_hobject *obj, duk_hstring *key, duk_propdesc *temp_desc);

DUK_LOCAL_DECL void duk__check_arguments_map_for_put(duk_hthread *thr, duk_hobject *obj, duk_hstring *key, duk_propdesc *temp_desc, duk_bool_t throw_flag);

DUK_LOCAL_DECL void duk__check_arguments_map_for_delete(duk_hthread *thr, duk_hobject *obj, duk_hstring *key, duk_propdesc *temp_desc);

DUK_LOCAL_DECL duk_bool_t duk__handle_put_array_length_smaller(duk_hthread *thr, duk_hobject *obj, duk_uint32_t old_len, duk_uint32_t new_len, duk_bool_t force_flag, duk_uint32_t *out_result_len);

DUK_LOCAL_DECL duk_bool_t duk__handle_put_array_length(duk_hthread *thr, duk_hobject *obj);

DUK_LOCAL_DECL duk_bool_t duk__get_propdesc(duk_hthread *thr, duk_hobject *obj, duk_hstring *key, duk_propdesc *out_desc, duk_small_uint_t flags);

DUK_LOCAL_DECL duk_bool_t duk__get_own_propdesc_raw(duk_hthread *thr, duk_hobject *obj, duk_hstring *key, duk_uint32_t arr_idx, duk_propdesc *out_desc, duk_small_uint_t flags);

DUK_LOCAL_DECL void duk__abandon_array_part(duk_hthread *thr, duk_hobject *obj);

DUK_LOCAL_DECL void duk__grow_props_for_array_item(duk_hthread *thr, duk_hobject *obj, duk_uint32_t highest_arr_idx);

/*

* Misc helpers

*/

/* Convert a duk_tval number (caller checks) to a 32-bit index. Returns

* DUK__NO_ARRAY_INDEX if the number is not whole or not a valid array

* index.

*/

/* XXX: for fastints, could use a variant which assumes a double duk_tval

* (and doesn't need to check for fastint again).

*/

DUK_LOCAL duk_uint32_t duk__tval_number_to_arr_idx(duk_tval *tv) {

duk_double_t dbl;

duk_uint32_t idx;

DUK_ASSERT(tv != NULL);

DUK_ASSERT(DUK_TVAL_IS_NUMBER(tv));

/* -0 is accepted here as index 0 because ToString(-0) == "0" which is

* in canonical form and thus an array index.

*/

dbl = DUK_TVAL_GET_NUMBER(tv);

idx = (duk_uint32_t) dbl;

if (duk_double_equals((duk_double_t) idx, dbl)) {

/* Is whole and within 32 bit range. If the value happens to be 0xFFFFFFFF,

* it's not a valid array index but will then match DUK__NO_ARRAY_INDEX.

*/

return idx;

}

return DUK__NO_ARRAY_INDEX;

}

#if defined(DUK_USE_FASTINT)

/* Convert a duk_tval fastint (caller checks) to a 32-bit index. */

DUK_LOCAL duk_uint32_t duk__tval_fastint_to_arr_idx(duk_tval *tv) {

duk_int64_t t;

DUK_ASSERT(tv != NULL);

DUK_ASSERT(DUK_TVAL_IS_FASTINT(tv));

t = DUK_TVAL_GET_FASTINT(tv);

if (((duk_uint64_t) t & ~DUK_U64_CONSTANT(0xffffffff)) != 0) {

/* Catches >0x100000000 and negative values. */

return DUK__NO_ARRAY_INDEX;

}

/* If the value happens to be 0xFFFFFFFF, it's not a valid array index

* but will then match DUK__NO_ARRAY_INDEX.

*/

return (duk_uint32_t) t;

}

#endif /* DUK_USE_FASTINT */

/* Convert a duk_tval on the value stack (in a trusted index we don't validate)

* to a string or symbol using ES2015 ToPropertyKey():

* http://www.ecma-international.org/ecma-262/6.0/#sec-topropertykey.

*

* Also check if it's a valid array index and return that (or DUK__NO_ARRAY_INDEX

* if not).

*/

DUK_LOCAL duk_uint32_t duk__to_property_key(duk_hthread *thr, duk_idx_t idx, duk_hstring **out_h) {

duk_uint32_t arr_idx;

duk_hstring *h;

duk_tval *tv_dst;

DUK_ASSERT(thr != NULL);

DUK_ASSERT(out_h != NULL);

DUK_ASSERT(duk_is_valid_index(thr, idx));

DUK_ASSERT(idx < 0);

/* XXX: The revised ES2015 ToPropertyKey() handling (ES5.1 was just

* ToString()) involves a ToPrimitive(), a symbol check, and finally

* a ToString(). Figure out the best way to have a good fast path

* but still be compliant and share code.

*/

tv_dst = DUK_GET_TVAL_NEGIDX(thr, idx); /* intentionally unvalidated */

if (DUK_TVAL_IS_STRING(tv_dst)) {

/* Most important path: strings and plain symbols are used as

* is. For symbols the array index check below is unnecessary

* (they're never valid array indices) but checking that the

* string is a symbol would make the plain string path slower

* unnecessarily.

*/

h = DUK_TVAL_GET_STRING(tv_dst);

} else {

h = duk_to_property_key_hstring(thr, idx);

}

DUK_ASSERT(h != NULL);

*out_h = h;

arr_idx = DUK_HSTRING_GET_ARRIDX_FAST(h);

return arr_idx;

}

DUK_LOCAL duk_uint32_t duk__push_tval_to_property_key(duk_hthread *thr, duk_tval *tv_key, duk_hstring **out_h) {

duk_push_tval(thr, tv_key); /* XXX: could use an unsafe push here */

return duk__to_property_key(thr, -1, out_h);

}

/* String is an own (virtual) property of a plain buffer. */

DUK_LOCAL duk_bool_t duk__key_is_plain_buf_ownprop(duk_hthread *thr, duk_hbuffer *buf, duk_hstring *key, duk_uint32_t arr_idx) {

DUK_UNREF(thr);

/* Virtual index properties. Checking explicitly for

* 'arr_idx != DUK__NO_ARRAY_INDEX' is not necessary

* because DUK__NO_ARRAY_INDEXi is always larger than

* maximum allowed buffer size.

*/

DUK_ASSERT(DUK__NO_ARRAY_INDEX >= DUK_HBUFFER_GET_SIZE(buf));

if (arr_idx < DUK_HBUFFER_GET_SIZE(buf)) {

return 1;

}

/* Other virtual properties. */

return (key == DUK_HTHREAD_STRING_LENGTH(thr));

}

/*

* Helpers for managing property storage size

*/

/* Get default hash part size for a certain entry part size. */

#if defined(DUK_USE_HOBJECT_HASH_PART)

DUK_LOCAL duk_uint32_t duk__get_default_h_size(duk_uint32_t e_size) {

DUK_ASSERT(e_size <= DUK_HOBJECT_MAX_PROPERTIES);

if (e_size >= DUK_USE_HOBJECT_HASH_PROP_LIMIT) {

duk_uint32_t res;

duk_uint32_t tmp;

/* Hash size should be 2^N where N is chosen so that 2^N is

* larger than e_size. Extra shifting is used to ensure hash

* is relatively sparse.

*/

tmp = e_size;

res = 2; /* Result will be 2 ** (N + 1). */

while (tmp >= 0x40) {

tmp >>= 6;

res <<= 6;

}

while (tmp != 0) {

tmp >>= 1;

res <<= 1;

}

DUK_ASSERT((DUK_HOBJECT_MAX_PROPERTIES << 2U) > DUK_HOBJECT_MAX_PROPERTIES); /* Won't wrap, even shifted by 2. */

DUK_ASSERT(res > e_size);

return res;

} else {

return 0;

}

}

#endif /* USE_PROP_HASH_PART */

/* Get minimum entry part growth for a certain size. */

DUK_LOCAL duk_uint32_t duk__get_min_grow_e(duk_uint32_t e_size) {

duk_uint32_t res;

res = (e_size + DUK_USE_HOBJECT_ENTRY_MINGROW_ADD) / DUK_USE_HOBJECT_ENTRY_MINGROW_DIVISOR;

DUK_ASSERT(res >= 1); /* important for callers */

return res;

}

/* Get minimum array part growth for a certain size. */

DUK_LOCAL duk_uint32_t duk__get_min_grow_a(duk_uint32_t a_size) {

duk_uint32_t res;

res = (a_size + DUK_USE_HOBJECT_ARRAY_MINGROW_ADD) / DUK_USE_HOBJECT_ARRAY_MINGROW_DIVISOR;

DUK_ASSERT(res >= 1); /* important for callers */

return res;

}

/* Count actually used entry part entries (non-NULL keys). */

DUK_LOCAL duk_uint32_t duk__count_used_e_keys(duk_hthread *thr, duk_hobject *obj) {

duk_uint_fast32_t i;

duk_uint_fast32_t n = 0;

duk_hstring **e;

DUK_ASSERT(obj != NULL);

DUK_UNREF(thr);

e = DUK_HOBJECT_E_GET_KEY_BASE(thr->heap, obj);

for (i = 0; i < DUK_HOBJECT_GET_ENEXT(obj); i++) {

if (*e++) {

n++;

}

}

return (duk_uint32_t) n;

}

/* Count actually used array part entries and array minimum size.

* NOTE: 'out_min_size' can be computed much faster by starting from the

* end and breaking out early when finding first used entry, but this is

* not needed now.

*/

DUK_LOCAL void duk__compute_a_stats(duk_hthread *thr, duk_hobject *obj, duk_uint32_t *out_used, duk_uint32_t *out_min_size) {

duk_uint_fast32_t i;

duk_uint_fast32_t used = 0;

duk_uint_fast32_t highest_idx = (duk_uint_fast32_t) -1; /* see below */

duk_tval *a;

DUK_ASSERT(obj != NULL);

DUK_ASSERT(out_used != NULL);

DUK_ASSERT(out_min_size != NULL);

DUK_UNREF(thr);

a = DUK_HOBJECT_A_GET_BASE(thr->heap, obj);

for (i = 0; i < DUK_HOBJECT_GET_ASIZE(obj); i++) {

duk_tval *tv = a++;

if (!DUK_TVAL_IS_UNUSED(tv)) {

used++;

highest_idx = i;

}

}

/* Initial value for highest_idx is -1 coerced to unsigned. This

* is a bit odd, but (highest_idx + 1) will then wrap to 0 below

* for out_min_size as intended.

*/

*out_used = (duk_uint32_t) used;

*out_min_size = (duk_uint32_t) (highest_idx + 1); /* 0 if no used entries */

}

/* Check array density and indicate whether or not the array part should be abandoned. */

DUK_LOCAL duk_bool_t duk__abandon_array_density_check(duk_uint32_t a_used, duk_uint32_t a_size) {

/*

* Array abandon check; abandon if:

*

* new_used / new_size < limit

* new_used < limit * new_size || limit is 3 bits fixed point

* new_used < limit' / 8 * new_size || *8

* 8*new_used < limit' * new_size || :8

* new_used < limit' * (new_size / 8)

*

* Here, new_used = a_used, new_size = a_size.

*

* Note: some callers use approximate values for a_used and/or a_size

* (e.g. dropping a '+1' term). This doesn't affect the usefulness

* of the check, but may confuse debugging.

*/

return (a_used < DUK_USE_HOBJECT_ARRAY_ABANDON_LIMIT * (a_size >> 3));

}

/* Fast check for extending array: check whether or not a slow density check is required. */

DUK_LOCAL duk_bool_t duk__abandon_array_slow_check_required(duk_uint32_t arr_idx, duk_uint32_t old_size) {

duk_uint32_t new_size_min;

/*

* In a fast check we assume old_size equals old_used (i.e., existing

* array is fully dense).

*

* Slow check if:

*

* (new_size - old_size) / old_size > limit

* new_size - old_size > limit * old_size

* new_size > (1 + limit) * old_size || limit' is 3 bits fixed point

* new_size > (1 + (limit' / 8)) * old_size || * 8

* 8 * new_size > (8 + limit') * old_size || : 8

* new_size > (8 + limit') * (old_size / 8)

* new_size > limit'' * (old_size / 8) || limit'' = 9 -> max 25% increase

* arr_idx + 1 > limit'' * (old_size / 8)

*

* This check doesn't work well for small values, so old_size is rounded

* up for the check (and the '+ 1' of arr_idx can be ignored in practice):

*

* arr_idx > limit'' * ((old_size + 7) / 8)

*/

new_size_min = arr_idx + 1;

return (new_size_min >= DUK_USE_HOBJECT_ARRAY_ABANDON_MINSIZE) &&

(arr_idx > DUK_USE_HOBJECT_ARRAY_FAST_RESIZE_LIMIT * ((old_size + 7) >> 3));

}

DUK_LOCAL duk_bool_t duk__abandon_array_check(duk_hthread *thr, duk_uint32_t arr_idx, duk_hobject *obj) {

duk_uint32_t min_size;

duk_uint32_t old_used;

duk_uint32_t old_size;

if (!duk__abandon_array_slow_check_required(arr_idx, DUK_HOBJECT_GET_ASIZE(obj))) {

DUK_DDD(DUK_DDDPRINT("=> fast resize is OK"));

return 0;

}

duk__compute_a_stats(thr, obj, &old_used, &old_size);

DUK_DDD(DUK_DDDPRINT("abandon check, array stats: old_used=%ld, old_size=%ld, arr_idx=%ld",

(long) old_used, (long) old_size, (long) arr_idx));

min_size = arr_idx + 1;

#if defined(DUK_USE_OBJSIZES16)

if (min_size > DUK_UINT16_MAX) {

goto do_abandon;

}

#endif

DUK_UNREF(min_size);

/* Note: intentionally use approximations to shave a few instructions:

* a_used = old_used (accurate: old_used + 1)

* a_size = arr_idx (accurate: arr_idx + 1)

*/

if (duk__abandon_array_density_check(old_used, arr_idx)) {

DUK_DD(DUK_DDPRINT("write to new array entry beyond current length, "

"decided to abandon array part (would become too sparse)"));

/* Abandoning requires a props allocation resize and

* 'rechecks' the valstack, invalidating any existing

* valstack value pointers.

*/

goto do_abandon;

}

DUK_DDD(DUK_DDDPRINT("=> decided to keep array part"));

return 0;

do_abandon:

duk__abandon_array_part(thr, obj);

DUK_ASSERT(!DUK_HOBJECT_HAS_ARRAY_PART(obj));

return 1;

}

DUK_LOCAL duk_tval *duk__obtain_arridx_slot_slowpath(duk_hthread *thr, duk_uint32_t arr_idx, duk_hobject *obj) {

/*

* Array needs to grow, but we don't want it becoming too sparse.

* If it were to become sparse, abandon array part, moving all

* array entries into the entries part (for good).

*

* Since we don't keep track of actual density (used vs. size) of

* the array part, we need to estimate somehow. The check is made

* in two parts:

*

* - Check whether the resize need is small compared to the

* current size (relatively); if so, resize without further

* checking (essentially we assume that the original part is

* "dense" so that the result would be dense enough).

*

* - Otherwise, compute the resize using an actual density

* measurement based on counting the used array entries.

*/

DUK_DDD(DUK_DDDPRINT("write to new array requires array resize, decide whether to do a "

"fast resize without abandon check (arr_idx=%ld, old_size=%ld)",

(long) arr_idx, (long) DUK_HOBJECT_GET_ASIZE(obj)));

if (DUK_UNLIKELY(duk__abandon_array_check(thr, arr_idx, obj) != 0)) {

DUK_ASSERT(!DUK_HOBJECT_HAS_ARRAY_PART(obj));

return NULL;

}

DUK_DD(DUK_DDPRINT("write to new array entry beyond current length, "

"decided to extend current allocation"));

/* In principle it's possible to run out of memory extending the

* array but with the allocation going through if we were to abandon

* the array part and try again. In practice this should be rare

* because abandoned arrays have a higher per-entry footprint.

*/

duk__grow_props_for_array_item(thr, obj, arr_idx);

DUK_ASSERT(DUK_HOBJECT_HAS_ARRAY_PART(obj));

DUK_ASSERT(arr_idx < DUK_HOBJECT_GET_ASIZE(obj));

return DUK_HOBJECT_A_GET_VALUE_PTR(thr->heap, obj, arr_idx);

}

DUK_LOCAL DUK_INLINE duk_tval *duk__obtain_arridx_slot(duk_hthread *thr, duk_uint32_t arr_idx, duk_hobject *obj) {

if (DUK_LIKELY(arr_idx < DUK_HOBJECT_GET_ASIZE(obj))) {

return DUK_HOBJECT_A_GET_VALUE_PTR(thr->heap, obj, arr_idx);

} else {

return duk__obtain_arridx_slot_slowpath(thr, arr_idx, obj);

}

}

/*

* Proxy helpers

*/

#if defined(DUK_USE_ES6_PROXY)

DUK_INTERNAL duk_bool_t duk_hobject_proxy_check(duk_hobject *obj, duk_hobject **out_target, duk_hobject **out_handler) {

duk_hproxy *h_proxy;

DUK_ASSERT(obj != NULL);

DUK_ASSERT(out_target != NULL);

DUK_ASSERT(out_handler != NULL);

/* Caller doesn't need to check exotic proxy behavior (but does so for

* some fast paths).

*/

if (DUK_LIKELY(!DUK_HOBJECT_IS_PROXY(obj))) {

return 0;

}

h_proxy = (duk_hproxy *) obj;

DUK_HPROXY_ASSERT_VALID(h_proxy);

DUK_ASSERT(h_proxy->handler != NULL);

DUK_ASSERT(h_proxy->target != NULL);

*out_handler = h_proxy->handler;

*out_target = h_proxy->target;

return 1;

}

#endif /* DUK_USE_ES6_PROXY */

/* Get Proxy target object. If the argument is not a Proxy, return it as is.

* If a Proxy is revoked, an error is thrown.

*/

#if defined(DUK_USE_ES6_PROXY)

DUK_INTERNAL duk_hobject *duk_hobject_resolve_proxy_target(duk_hobject *obj) {

DUK_ASSERT(obj != NULL);

/* Resolve Proxy targets until Proxy chain ends. No explicit check for

* a Proxy loop: user code cannot create such a loop (it would only be

* possible by editing duk_hproxy references directly).

*/

while (DUK_HOBJECT_IS_PROXY(obj)) {

duk_hproxy *h_proxy;

h_proxy = (duk_hproxy *) obj;

DUK_HPROXY_ASSERT_VALID(h_proxy);

obj = h_proxy->target;

DUK_ASSERT(obj != NULL);

}

DUK_ASSERT(obj != NULL);

return obj;

}

#endif /* DUK_USE_ES6_PROXY */

#if defined(DUK_USE_ES6_PROXY)

DUK_LOCAL duk_bool_t duk__proxy_check_prop(duk_hthread *thr, duk_hobject *obj, duk_small_uint_t stridx_trap, duk_tval *tv_key, duk_hobject **out_target) {

duk_hobject *h_handler;

DUK_ASSERT(thr != NULL);

DUK_ASSERT(obj != NULL);

DUK_ASSERT(tv_key != NULL);

DUK_ASSERT(out_target != NULL);

if (!duk_hobject_proxy_check(obj, out_target, &h_handler)) {

return 0;

}

DUK_ASSERT(*out_target != NULL);

DUK_ASSERT(h_handler != NULL);

/* XXX: At the moment Duktape accesses internal keys like _Finalizer using a

* normal property set/get which would allow a proxy handler to interfere with

* such behavior and to get access to internal key strings. This is not a problem

* as such because internal key strings can be created in other ways too (e.g.

* through buffers). The best fix is to change Duktape internal lookups to

* skip proxy behavior. Until that, internal property accesses bypass the

* proxy and are applied to the target (as if the handler did not exist).

* This has some side effects, see test-bi-proxy-internal-keys.js.

*/

if (DUK_TVAL_IS_STRING(tv_key)) {

duk_hstring *h_key = (duk_hstring *) DUK_TVAL_GET_STRING(tv_key);

DUK_ASSERT(h_key != NULL);

if (DUK_HSTRING_HAS_HIDDEN(h_key)) {

/* Symbol accesses must go through proxy lookup in ES2015.

* Hidden symbols behave like Duktape 1.x internal keys

* and currently won't.

*/

DUK_DDD(DUK_DDDPRINT("hidden key, skip proxy handler and apply to target"));

return 0;

}

}

/* The handler is looked up with a normal property lookup; it may be an

* accessor or the handler object itself may be a proxy object. If the

* handler is a proxy, we need to extend the valstack as we make a

* recursive proxy check without a function call in between (in fact

* there is no limit to the potential recursion here).

*

* (For sanity, proxy creation rejects another proxy object as either

* the handler or the target at the moment so recursive proxy cases

* are not realized now.)

*/

/* XXX: C recursion limit if proxies are allowed as handler/target values */

duk_require_stack(thr, DUK__VALSTACK_PROXY_LOOKUP);

duk_push_hobject(thr, h_handler);

if (duk_get_prop_stridx_short(thr, -1, stridx_trap)) {

/* -> [ ... handler trap ] */

duk_insert(thr, -2); /* -> [ ... trap handler ] */

/* stack prepped for func call: [ ... trap handler ] */

return 1;

} else {

duk_pop_2_unsafe(thr);

return 0;

}

}

#endif /* DUK_USE_ES6_PROXY */

/*

* Reallocate property allocation, moving properties to the new allocation.

*

* Includes key compaction, rehashing, and can also optionally abandon

* the array part, 'migrating' array entries into the beginning of the

* new entry part.

*

* There is no support for in-place reallocation or just compacting keys

* without resizing the property allocation. This is intentional to keep

* code size minimal, but would be useful future work.

*

* The implementation is relatively straightforward, except for the array

* abandonment process. Array abandonment requires that new string keys

* are interned, which may trigger GC. All keys interned so far must be

* reachable for GC at all times and correctly refcounted for; valstack is

* used for that now.

*

* Also, a GC triggered during this reallocation process must not interfere

* with the object being resized. This is currently controlled by preventing

* finalizers (as they may affect ANY object) and object compaction in

* mark-and-sweep. It would suffice to protect only this particular object

* from compaction, however. DECREF refzero cascades are side effect free

* and OK.

*

* Note: because we need to potentially resize the valstack (as part

* of abandoning the array part), any tval pointers to the valstack

* will become invalid after this call.

*/

DUK_INTERNAL void duk_hobject_realloc_props(duk_hthread *thr,

duk_hobject *obj,

duk_uint32_t new_e_size,

duk_uint32_t new_a_size,

duk_uint32_t new_h_size,

duk_bool_t abandon_array) {

duk_small_uint_t prev_ms_base_flags;

duk_uint32_t new_alloc_size;

duk_uint32_t new_e_size_adjusted;

duk_uint8_t *new_p;

duk_hstring **new_e_k;

duk_propvalue *new_e_pv;

duk_uint8_t *new_e_f;

duk_tval *new_a;

duk_uint32_t *new_h;

duk_uint32_t new_e_next;

duk_uint_fast32_t i;

duk_size_t array_copy_size;

#if defined(DUK_USE_ASSERTIONS)

duk_bool_t prev_error_not_allowed;

#endif

DUK_ASSERT(thr != NULL);

DUK_ASSERT(obj != NULL);

DUK_ASSERT(!abandon_array || new_a_size == 0); /* if abandon_array, new_a_size must be 0 */

DUK_ASSERT(DUK_HOBJECT_GET_PROPS(thr->heap, obj) != NULL || (DUK_HOBJECT_GET_ESIZE(obj) == 0 && DUK_HOBJECT_GET_ASIZE(obj) == 0));

DUK_ASSERT(new_h_size == 0 || new_h_size >= new_e_size); /* required to guarantee success of rehashing,

* intentionally use unadjusted new_e_size

*/

DUK_ASSERT(!DUK_HEAPHDR_HAS_READONLY((duk_heaphdr *) obj));

DUK_ASSERT_VALSTACK_SPACE(thr, DUK__VALSTACK_SPACE);

DUK_STATS_INC(thr->heap, stats_object_realloc_props);

/*

* Pre resize assertions.

*/

#if defined(DUK_USE_ASSERTIONS)

/* XXX: pre-checks (such as no duplicate keys) */

#endif

/*

* For property layout 1, tweak e_size to ensure that the whole entry

* part (key + val + flags) is a suitable multiple for alignment

* (platform specific).

*

* Property layout 2 does not require this tweaking and is preferred

* on low RAM platforms requiring alignment.

*/

#if defined(DUK_USE_HOBJECT_LAYOUT_2) || defined(DUK_USE_HOBJECT_LAYOUT_3)

DUK_DDD(DUK_DDDPRINT("using layout 2 or 3, no need to pad e_size: %ld", (long) new_e_size));

new_e_size_adjusted = new_e_size;

#elif defined(DUK_USE_HOBJECT_LAYOUT_1) && (DUK_HOBJECT_ALIGN_TARGET == 1)

DUK_DDD(DUK_DDDPRINT("using layout 1, but no need to pad e_size: %ld", (long) new_e_size));

new_e_size_adjusted = new_e_size;

#elif defined(DUK_USE_HOBJECT_LAYOUT_1) && ((DUK_HOBJECT_ALIGN_TARGET == 4) || (DUK_HOBJECT_ALIGN_TARGET == 8))

new_e_size_adjusted = (new_e_size + (duk_uint32_t) DUK_HOBJECT_ALIGN_TARGET - 1U) &

(~((duk_uint32_t) DUK_HOBJECT_ALIGN_TARGET - 1U));

DUK_DDD(DUK_DDDPRINT("using layout 1, and alignment target is %ld, adjusted e_size: %ld -> %ld",

(long) DUK_HOBJECT_ALIGN_TARGET, (long) new_e_size, (long) new_e_size_adjusted));

DUK_ASSERT(new_e_size_adjusted >= new_e_size);

#else

#error invalid hobject layout defines

#endif

/*

* Debug logging after adjustment.

*/

DUK_DDD(DUK_DDDPRINT("attempt to resize hobject %p props (%ld -> %ld bytes), from {p=%p,e_size=%ld,e_next=%ld,a_size=%ld,h_size=%ld} to "

"{e_size=%ld,a_size=%ld,h_size=%ld}, abandon_array=%ld, unadjusted new_e_size=%ld",

(void *) obj,

(long) DUK_HOBJECT_P_COMPUTE_SIZE(DUK_HOBJECT_GET_ESIZE(obj),

DUK_HOBJECT_GET_ASIZE(obj),

DUK_HOBJECT_GET_HSIZE(obj)),

(long) DUK_HOBJECT_P_COMPUTE_SIZE(new_e_size_adjusted, new_a_size, new_h_size),

(void *) DUK_HOBJECT_GET_PROPS(thr->heap, obj),

(long) DUK_HOBJECT_GET_ESIZE(obj),

(long) DUK_HOBJECT_GET_ENEXT(obj),

(long) DUK_HOBJECT_GET_ASIZE(obj),

(long) DUK_HOBJECT_GET_HSIZE(obj),

(long) new_e_size_adjusted,

(long) new_a_size,

(long) new_h_size,

(long) abandon_array,

(long) new_e_size));

/*

* Property count check. This is the only point where we ensure that

* we don't get more (allocated) property space that we can handle.

* There aren't hard limits as such, but some algorithms may fail

* if we get too close to the 4G property limit.

*

* Since this works based on allocation size (not actually used size),

* the limit is a bit approximate but good enough in practice.

*/

if (new_e_size_adjusted + new_a_size > DUK_HOBJECT_MAX_PROPERTIES) {

DUK_ERROR_ALLOC_FAILED(thr);

DUK_WO_NORETURN(return;);

}

#if defined(DUK_USE_OBJSIZES16)

if (new_e_size_adjusted > DUK_UINT16_MAX || new_a_size > DUK_UINT16_MAX) {

/* If caller gave us sizes larger than what we can store,

* fail memory safely with an internal error rather than

* truncating the sizes.

*/

DUK_ERROR_INTERNAL(thr);

DUK_WO_NORETURN(return;);

}

#endif

/*

* Compute new alloc size and alloc new area.

*

* The new area is not tracked in the heap at all, so it's critical

* we get to free/keep it in a controlled manner.

*/

#if defined(DUK_USE_ASSERTIONS)

/* Whole path must be error throw free, but we may be called from

* within error handling so can't assert for error_not_allowed == 0.

*/

prev_error_not_allowed = thr->heap->error_not_allowed;

thr->heap->error_not_allowed = 1;

#endif

prev_ms_base_flags = thr->heap->ms_base_flags;

thr->heap->ms_base_flags |=

DUK_MS_FLAG_NO_OBJECT_COMPACTION; /* Avoid attempt to compact the current object (all objects really). */

thr->heap->pf_prevent_count++; /* Avoid finalizers. */

DUK_ASSERT(thr->heap->pf_prevent_count != 0); /* Wrap. */

new_alloc_size = DUK_HOBJECT_P_COMPUTE_SIZE(new_e_size_adjusted, new_a_size, new_h_size);

DUK_DDD(DUK_DDDPRINT("new hobject allocation size is %ld", (long) new_alloc_size));

if (new_alloc_size == 0) {

DUK_ASSERT(new_e_size_adjusted == 0);

DUK_ASSERT(new_a_size == 0);

DUK_ASSERT(new_h_size == 0);

new_p = NULL;

} else {

/* Alloc may trigger mark-and-sweep but no compaction, and

* cannot throw.

*/

#if 0 /* XXX: inject test */

if (1) {

new_p = NULL;

goto alloc_failed;

}

#endif

new_p = (duk_uint8_t *) DUK_ALLOC(thr->heap, new_alloc_size);

if (new_p == NULL) {

/* NULL always indicates alloc failure because

* new_alloc_size > 0.

*/

goto alloc_failed;

}

}

/* Set up pointers to the new property area: this is hidden behind a macro

* because it is memory layout specific.

*/

DUK_HOBJECT_P_SET_REALLOC_PTRS(new_p, new_e_k, new_e_pv, new_e_f, new_a, new_h,

new_e_size_adjusted, new_a_size, new_h_size);

DUK_UNREF(new_h); /* happens when hash part dropped */

new_e_next = 0;

/* if new_p == NULL, all of these pointers are NULL */

DUK_ASSERT((new_p != NULL) ||

(new_e_k == NULL && new_e_pv == NULL && new_e_f == NULL &&

new_a == NULL && new_h == NULL));

DUK_DDD(DUK_DDDPRINT("new alloc size %ld, new_e_k=%p, new_e_pv=%p, new_e_f=%p, new_a=%p, new_h=%p",

(long) new_alloc_size, (void *) new_e_k, (void *) new_e_pv, (void *) new_e_f,

(void *) new_a, (void *) new_h));

/*

* Migrate array part to start of entries if requested.

*

* Note: from an enumeration perspective the order of entry keys matters.

* Array keys should appear wherever they appeared before the array abandon

* operation. (This no longer matters much because keys are ES2015 sorted.)

*/

if (abandon_array) {

/* Assuming new_a_size == 0, and that entry part contains

* no conflicting keys, refcounts do not need to be adjusted for

* the values, as they remain exactly the same.

*

* The keys, however, need to be interned, incref'd, and be

* reachable for GC. Any intern attempt may trigger a GC and

* claim any non-reachable strings, so every key must be reachable

* at all times. Refcounts must be correct to satisfy refcount

* assertions.

*

* A longjmp must not occur here, as the new_p allocation would

* leak. Refcounts would come out correctly as the interned

* strings are valstack tracked.

*/

DUK_ASSERT(new_a_size == 0);

DUK_STATS_INC(thr->heap, stats_object_abandon_array);

for (i = 0; i < DUK_HOBJECT_GET_ASIZE(obj); i++) {

duk_tval *tv1;

duk_tval *tv2;

duk_hstring *key;

DUK_ASSERT(DUK_HOBJECT_GET_PROPS(thr->heap, obj) != NULL);

tv1 = DUK_HOBJECT_A_GET_VALUE_PTR(thr->heap, obj, i);

if (DUK_TVAL_IS_UNUSED(tv1)) {

continue;

}

DUK_ASSERT(new_p != NULL && new_e_k != NULL &&

new_e_pv != NULL && new_e_f != NULL);

/*

* Intern key via the valstack to ensure reachability behaves

* properly. We must avoid longjmp's here so use non-checked

* primitives.

*

* Note: duk_check_stack() potentially reallocs the valstack,

* invalidating any duk_tval pointers to valstack. Callers

* must be careful.

*/

#if 0 /* XXX: inject test */

if (1) {

goto abandon_error;

}

#endif

/* Never shrinks; auto-adds DUK_VALSTACK_INTERNAL_EXTRA, which

* is generous.

*/

if (!duk_check_stack(thr, 1)) {

goto abandon_error;

}

DUK_ASSERT_VALSTACK_SPACE(thr, 1);

key = duk_heap_strtable_intern_u32(thr->heap, (duk_uint32_t) i);

if (key == NULL) {

goto abandon_error;

}

duk_push_hstring(thr, key); /* keep key reachable for GC etc; guaranteed not to fail */

/* Key is now reachable in the valstack, don't INCREF

* the new allocation yet (we'll steal the refcounts

* from the value stack once all keys are done).

*/

new_e_k[new_e_next] = key;

tv2 = &new_e_pv[new_e_next].v; /* array entries are all plain values */

DUK_TVAL_SET_TVAL(tv2, tv1);

new_e_f[new_e_next] = DUK_PROPDESC_FLAG_WRITABLE |

DUK_PROPDESC_FLAG_ENUMERABLE |

DUK_PROPDESC_FLAG_CONFIGURABLE;

new_e_next++;

/* Note: new_e_next matches pushed temp key count, and nothing can

* fail above between the push and this point.

*/

}

/* Steal refcounts from value stack. */

DUK_DDD(DUK_DDDPRINT("abandon array: pop %ld key temps from valstack", (long) new_e_next));

duk_pop_n_nodecref_unsafe(thr, (duk_idx_t) new_e_next);

}

/*

* Copy keys and values in the entry part (compacting them at the same time).

*/

for (i = 0; i < DUK_HOBJECT_GET_ENEXT(obj); i++) {

duk_hstring *key;

DUK_ASSERT(DUK_HOBJECT_GET_PROPS(thr->heap, obj) != NULL);

key = DUK_HOBJECT_E_GET_KEY(thr->heap, obj, i);

if (key == NULL) {

continue;

}

DUK_ASSERT(new_p != NULL && new_e_k != NULL &&

new_e_pv != NULL && new_e_f != NULL);

new_e_k[new_e_next] = key;

new_e_pv[new_e_next] = DUK_HOBJECT_E_GET_VALUE(thr->heap, obj, i);

new_e_f[new_e_next] = DUK_HOBJECT_E_GET_FLAGS(thr->heap, obj, i);

new_e_next++;

}

/* the entries [new_e_next, new_e_size_adjusted[ are left uninitialized on purpose (ok, not gc reachable) */

/*

* Copy array elements to new array part. If the new array part is

* larger, initialize the unused entries as UNUSED because they are

* GC reachable.

*/

#if defined(DUK_USE_ASSERTIONS)

/* Caller must have decref'd values above new_a_size (if that is necessary). */

if (!abandon_array) {

for (i = new_a_size; i < DUK_HOBJECT_GET_ASIZE(obj); i++) {

duk_tval *tv;

tv = DUK_HOBJECT_A_GET_VALUE_PTR(thr->heap, obj, i);

DUK_ASSERT(DUK_TVAL_IS_UNUSED(tv));

}

}

#endif

if (new_a_size > DUK_HOBJECT_GET_ASIZE(obj)) {

array_copy_size = sizeof(duk_tval) * DUK_HOBJECT_GET_ASIZE(obj);

} else {

array_copy_size = sizeof(duk_tval) * new_a_size;

}

DUK_ASSERT(new_a != NULL || array_copy_size == 0U);

DUK_ASSERT(DUK_HOBJECT_GET_PROPS(thr->heap, obj) != NULL || array_copy_size == 0U);

DUK_ASSERT(DUK_HOBJECT_GET_ASIZE(obj) > 0 || array_copy_size == 0U);

duk_memcpy_unsafe((void *) new_a,

(const void *) DUK_HOBJECT_A_GET_BASE(thr->heap, obj),

array_copy_size);

for (i = DUK_HOBJECT_GET_ASIZE(obj); i < new_a_size; i++) {

duk_tval *tv = &new_a[i];

DUK_TVAL_SET_UNUSED(tv);

}

/*

* Rebuild the hash part always from scratch (guaranteed to finish

* as long as caller gave consistent parameters).

*

* Any resize of hash part requires rehashing. In addition, by rehashing

* get rid of any elements marked deleted (DUK__HASH_DELETED) which is critical

* to ensuring the hash part never fills up.

*/

#if defined(DUK_USE_HOBJECT_HASH_PART)

if (new_h_size == 0) {

DUK_DDD(DUK_DDDPRINT("no hash part, no rehash"));

} else {

duk_uint32_t mask;

DUK_ASSERT(new_h != NULL);

/* fill new_h with u32 0xff = UNUSED */

DUK_ASSERT(new_h_size > 0);

duk_memset(new_h, 0xff, sizeof(duk_uint32_t) * new_h_size);

DUK_ASSERT(new_e_next <= new_h_size); /* equality not actually possible */

mask = new_h_size - 1;

for (i = 0; i < new_e_next; i++) {

duk_hstring *key = new_e_k[i];

duk_uint32_t j, step;

DUK_ASSERT(key != NULL);

j = DUK_HSTRING_GET_HASH(key) & mask;

step = 1; /* Cache friendly but clustering prone. */

for (;;) {

DUK_ASSERT(new_h[j] != DUK__HASH_DELETED); /* should never happen */

if (new_h[j] == DUK__HASH_UNUSED) {

DUK_DDD(DUK_DDDPRINT("rebuild hit %ld -> %ld", (long) j, (long) i));

new_h[j] = (duk_uint32_t) i;

break;

}

DUK_DDD(DUK_DDDPRINT("rebuild miss %ld, step %ld", (long) j, (long) step));

j = (j + step) & mask;

/* Guaranteed to finish (hash is larger than #props). */

}

}

}

#endif /* DUK_USE_HOBJECT_HASH_PART */

/*

* Nice debug log.

*/

DUK_DD(DUK_DDPRINT("resized hobject %p props (%ld -> %ld bytes), from {p=%p,e_size=%ld,e_next=%ld,a_size=%ld,h_size=%ld} to "

"{p=%p,e_size=%ld,e_next=%ld,a_size=%ld,h_size=%ld}, abandon_array=%ld, unadjusted new_e_size=%ld",

(void *) obj,

(long) DUK_HOBJECT_P_COMPUTE_SIZE(DUK_HOBJECT_GET_ESIZE(obj),

DUK_HOBJECT_GET_ASIZE(obj),

DUK_HOBJECT_GET_HSIZE(obj)),

(long) new_alloc_size,

(void *) DUK_HOBJECT_GET_PROPS(thr->heap, obj),

(long) DUK_HOBJECT_GET_ESIZE(obj),

(long) DUK_HOBJECT_GET_ENEXT(obj),

(long) DUK_HOBJECT_GET_ASIZE(obj),

(long) DUK_HOBJECT_GET_HSIZE(obj),

(void *) new_p,

(long) new_e_size_adjusted,