2 * Hobject enumeration support.
4 * Creates an internal enumeration state object to be used e.g. with for-in
5 * enumeration. The state object contains a snapshot of target object keys
6 * and internal control state for enumeration. Enumerator flags allow caller
7 * to e.g. request internal/non-enumerable properties, and to enumerate only
10 * Also creates the result value for e.g. Object.keys() based on the same
13 * This snapshot-based enumeration approach is used to simplify enumeration:
14 * non-snapshot-based approaches are difficult to reconcile with mutating
15 * the enumeration target, running multiple long-lived enumerators at the
16 * same time, garbage collection details, etc. The downside is that the
17 * enumerator object is memory inefficient especially for iterating arrays.
20 #include "duk_internal.h"
22 /* XXX: identify enumeration target with an object index (not top of stack) */
24 /* must match exactly the number of internal properties inserted to enumerator */
25 #define DUK__ENUM_START_INDEX 2
27 DUK_LOCAL
const duk_uint16_t duk__bufferobject_virtual_props
[] = {
29 DUK_STRIDX_BYTE_LENGTH
,
30 DUK_STRIDX_BYTE_OFFSET
,
31 DUK_STRIDX_BYTES_PER_ELEMENT
35 * Helper to sort array index keys. The keys are in the enumeration object
36 * entry part, starting from DUK__ENUM_START_INDEX, and the entry part is dense.
38 * We use insertion sort because it is simple (leading to compact code,)
39 * works nicely in-place, and minimizes operations if data is already sorted
40 * or nearly sorted (which is a very common case here). It also minimizes
41 * the use of element comparisons in general. This is nice because element
42 * comparisons here involve re-parsing the string keys into numbers each
43 * time, which is naturally very expensive.
45 * Note that the entry part values are all "true", e.g.
47 * "1" -> true, "3" -> true, "2" -> true
49 * so it suffices to only work in the key part without exchanging any keys,
50 * simplifying the sort.
52 * http://en.wikipedia.org/wiki/Insertion_sort
54 * (Compiles to about 160 bytes now as a stand-alone function.)
57 DUK_LOCAL
void duk__sort_array_indices(duk_hthread
*thr
, duk_hobject
*h_obj
) {
59 duk_hstring
**p_curr
, **p_insert
, **p_end
;
61 duk_uarridx_t val_highest
, val_curr
, val_insert
;
63 DUK_ASSERT(h_obj
!= NULL
);
64 DUK_ASSERT(DUK_HOBJECT_GET_ENEXT(h_obj
) >= 2); /* control props */
67 if (DUK_HOBJECT_GET_ENEXT(h_obj
) <= 1 + DUK__ENUM_START_INDEX
) {
71 keys
= DUK_HOBJECT_E_GET_KEY_BASE(thr
->heap
, h_obj
);
72 p_end
= keys
+ DUK_HOBJECT_GET_ENEXT(h_obj
);
73 keys
+= DUK__ENUM_START_INDEX
;
75 DUK_DDD(DUK_DDDPRINT("keys=%p, p_end=%p (after skipping enum props)",
76 (void *) keys
, (void *) p_end
));
78 #ifdef DUK_USE_DDDPRINT
81 for (i
= 0; i
< (duk_uint_fast32_t
) DUK_HOBJECT_GET_ENEXT(h_obj
); i
++) {
82 DUK_DDD(DUK_DDDPRINT("initial: %ld %p -> %!O",
84 (void *) DUK_HOBJECT_E_GET_KEY_PTR(thr
->heap
, h_obj
, i
),
85 (duk_heaphdr
*) DUK_HOBJECT_E_GET_KEY(thr
->heap
, h_obj
, i
)));
90 val_highest
= DUK_HSTRING_GET_ARRIDX_SLOW(keys
[0]);
91 for (p_curr
= keys
+ 1; p_curr
< p_end
; p_curr
++) {
92 DUK_ASSERT(*p_curr
!= NULL
);
93 val_curr
= DUK_HSTRING_GET_ARRIDX_SLOW(*p_curr
);
95 if (val_curr
>= val_highest
) {
96 DUK_DDD(DUK_DDDPRINT("p_curr=%p, p_end=%p, val_highest=%ld, val_curr=%ld -> "
97 "already in correct order, next",
98 (void *) p_curr
, (void *) p_end
, (long) val_highest
, (long) val_curr
));
99 val_highest
= val_curr
;
103 DUK_DDD(DUK_DDDPRINT("p_curr=%p, p_end=%p, val_highest=%ld, val_curr=%ld -> "
104 "needs to be inserted",
105 (void *) p_curr
, (void *) p_end
, (long) val_highest
, (long) val_curr
));
107 /* Needs to be inserted; scan backwards, since we optimize
108 * for the case where elements are nearly in order.
111 p_insert
= p_curr
- 1;
113 val_insert
= DUK_HSTRING_GET_ARRIDX_SLOW(*p_insert
);
114 if (val_insert
< val_curr
) {
115 DUK_DDD(DUK_DDDPRINT("p_insert=%p, val_insert=%ld, val_curr=%ld -> insert after this",
116 (void *) p_insert
, (long) val_insert
, (long) val_curr
));
120 if (p_insert
== keys
) {
121 DUK_DDD(DUK_DDDPRINT("p_insert=%p -> out of keys, insert to beginning", (void *) p_insert
));
124 DUK_DDD(DUK_DDDPRINT("p_insert=%p, val_insert=%ld, val_curr=%ld -> search backwards",
125 (void *) p_insert
, (long) val_insert
, (long) val_curr
));
129 DUK_DDD(DUK_DDDPRINT("final p_insert=%p", (void *) p_insert
));
131 /* .-- p_insert .-- p_curr
133 * | ... | insert | ... | curr
137 DUK_DDD(DUK_DDDPRINT("memmove: dest=%p, src=%p, size=%ld, h_curr=%p",
138 (void *) (p_insert
+ 1), (void *) p_insert
,
139 (long) (p_curr
- p_insert
), (void *) h_curr
));
141 DUK_MEMMOVE((void *) (p_insert
+ 1),
142 (const void *) p_insert
,
143 (size_t) ((p_curr
- p_insert
) * sizeof(duk_hstring
*)));
145 /* keep val_highest */
148 #ifdef DUK_USE_DDDPRINT
151 for (i
= 0; i
< (duk_uint_fast32_t
) DUK_HOBJECT_GET_ENEXT(h_obj
); i
++) {
152 DUK_DDD(DUK_DDDPRINT("final: %ld %p -> %!O",
154 (void *) DUK_HOBJECT_E_GET_KEY_PTR(thr
->heap
, h_obj
, i
),
155 (duk_heaphdr
*) DUK_HOBJECT_E_GET_KEY(thr
->heap
, h_obj
, i
)));
162 * Create an internal enumerator object E, which has its keys ordered
163 * to match desired enumeration ordering. Also initialize internal control
164 * properties for enumeration.
166 * Note: if an array was used to hold enumeration keys instead, an array
167 * scan would be needed to eliminate duplicates found in the prototype chain.
170 DUK_INTERNAL
void duk_hobject_enumerator_create(duk_context
*ctx
, duk_small_uint_t enum_flags
) {
171 duk_hthread
*thr
= (duk_hthread
*) ctx
;
172 duk_hobject
*enum_target
;
175 #if defined(DUK_USE_ES6_PROXY)
176 duk_hobject
*h_proxy_target
;
177 duk_hobject
*h_proxy_handler
;
178 duk_hobject
*h_trap_result
;
180 duk_uint_fast32_t i
, len
; /* used for array, stack, and entry indices */
182 DUK_ASSERT(ctx
!= NULL
);
184 DUK_DDD(DUK_DDDPRINT("create enumerator, stack top: %ld", (long) duk_get_top(ctx
)));
186 enum_target
= duk_require_hobject(ctx
, -1);
187 DUK_ASSERT(enum_target
!= NULL
);
189 duk_push_object_internal(ctx
);
190 res
= duk_require_hobject(ctx
, -1);
192 DUK_DDD(DUK_DDDPRINT("created internal object"));
194 /* [enum_target res] */
196 /* Target must be stored so that we can recheck whether or not
197 * keys still exist when we enumerate. This is not done if the
198 * enumeration result comes from a proxy trap as there is no
199 * real object to check against.
201 duk_push_hobject(ctx
, enum_target
);
202 duk_put_prop_stridx(ctx
, -2, DUK_STRIDX_INT_TARGET
);
204 /* Initialize index so that we skip internal control keys. */
205 duk_push_int(ctx
, DUK__ENUM_START_INDEX
);
206 duk_put_prop_stridx(ctx
, -2, DUK_STRIDX_INT_NEXT
);
209 * Proxy object handling
212 #if defined(DUK_USE_ES6_PROXY)
213 if (DUK_LIKELY((enum_flags
& DUK_ENUM_NO_PROXY_BEHAVIOR
) != 0)) {
216 if (DUK_LIKELY(!duk_hobject_proxy_check(thr
,
219 &h_proxy_handler
))) {
223 DUK_DDD(DUK_DDDPRINT("proxy enumeration"));
224 duk_push_hobject(ctx
, h_proxy_handler
);
225 if (!duk_get_prop_stridx(ctx
, -1, DUK_STRIDX_ENUMERATE
)) {
226 /* No need to replace the 'enum_target' value in stack, only the
227 * enum_target reference. This also ensures that the original
228 * enum target is reachable, which keeps the proxy and the proxy
229 * target reachable. We do need to replace the internal _Target.
231 DUK_DDD(DUK_DDDPRINT("no enumerate trap, enumerate proxy target instead"));
232 DUK_DDD(DUK_DDDPRINT("h_proxy_target=%!O", (duk_heaphdr
*) h_proxy_target
));
233 enum_target
= h_proxy_target
;
235 duk_push_hobject(ctx
, enum_target
); /* -> [ ... enum_target res handler undefined target ] */
236 duk_put_prop_stridx(ctx
, -4, DUK_STRIDX_INT_TARGET
);
238 duk_pop_2(ctx
); /* -> [ ... enum_target res ] */
242 /* [ ... enum_target res handler trap ] */
244 duk_push_hobject(ctx
, h_proxy_target
); /* -> [ ... enum_target res trap handler target ] */
245 duk_call_method(ctx
, 1 /*nargs*/); /* -> [ ... enum_target res trap_result ] */
246 h_trap_result
= duk_require_hobject(ctx
, -1);
247 DUK_UNREF(h_trap_result
);
249 /* Copy trap result keys into the enumerator object. */
250 len
= (duk_uint_fast32_t
) duk_get_length(ctx
, -1);
251 for (i
= 0; i
< len
; i
++) {
252 /* XXX: not sure what the correct semantic details are here,
253 * e.g. handling of missing values (gaps), handling of non-array
256 * For keys, we simply skip non-string keys which seems to be
257 * consistent with how e.g. Object.keys() will process proxy trap
258 * results (ES6, Section 19.1.2.14).
260 if (duk_get_prop_index(ctx
, -1, i
) && duk_is_string(ctx
, -1)) {
261 /* [ ... enum_target res trap_result val ] */
263 /* [ ... enum_target res trap_result val true ] */
264 duk_put_prop(ctx
, -4);
269 /* [ ... enum_target res trap_result ] */
275 /* The internal _Target property is kept pointing to the original
276 * enumeration target (the proxy object), so that the enumerator
277 * 'next' operation can read property values if so requested. The
278 * fact that the _Target is a proxy disables key existence check
279 * during enumeration.
281 DUK_DDD(DUK_DDDPRINT("proxy enumeration, final res: %!O", (duk_heaphdr
*) res
));
282 goto compact_and_return
;
285 #endif /* DUK_USE_ES6_PROXY */
290 * Virtual properties.
292 * String and buffer indices are virtual and always enumerable,
293 * 'length' is virtual and non-enumerable. Array and arguments
294 * object props have special behavior but are concrete.
297 if (DUK_HOBJECT_HAS_EXOTIC_STRINGOBJ(curr
) ||
298 DUK_HOBJECT_IS_BUFFEROBJECT(curr
)) {
299 /* String and buffer enumeration behavior is identical now,
300 * so use shared handler.
302 if (DUK_HOBJECT_HAS_EXOTIC_STRINGOBJ(curr
)) {
304 h_val
= duk_hobject_get_internal_value_string(thr
->heap
, curr
);
305 DUK_ASSERT(h_val
!= NULL
); /* string objects must not created without internal value */
306 len
= (duk_uint_fast32_t
) DUK_HSTRING_GET_CHARLEN(h_val
);
308 duk_hbufferobject
*h_bufobj
;
309 DUK_ASSERT(DUK_HOBJECT_IS_BUFFEROBJECT(curr
));
310 h_bufobj
= (duk_hbufferobject
*) curr
;
311 if (h_bufobj
== NULL
) {
312 /* Neutered buffer, zero length seems
313 * like good behavior here.
317 /* There's intentionally no check for
318 * current underlying buffer length.
320 len
= (duk_uint_fast32_t
) (h_bufobj
->length
>> h_bufobj
->shift
);
324 for (i
= 0; i
< len
; i
++) {
327 k
= duk_heap_string_intern_u32_checked(thr
, i
);
329 duk_push_hstring(ctx
, k
);
332 /* [enum_target res key true] */
333 duk_put_prop(ctx
, -3);
335 /* [enum_target res] */
338 /* 'length' and other virtual properties are not
339 * enumerable, but are included if non-enumerable
340 * properties are requested.
343 if (enum_flags
& DUK_ENUM_INCLUDE_NONENUMERABLE
) {
346 if (DUK_HOBJECT_IS_BUFFEROBJECT(curr
)) {
347 n
= sizeof(duk__bufferobject_virtual_props
) / sizeof(duk_uint16_t
);
349 DUK_ASSERT(DUK_HOBJECT_HAS_EXOTIC_STRINGOBJ(curr
));
350 DUK_ASSERT(duk__bufferobject_virtual_props
[0] == DUK_STRIDX_LENGTH
);
351 n
= 1; /* only 'length' */
354 for (i
= 0; i
< n
; i
++) {
355 duk_push_hstring_stridx(ctx
, duk__bufferobject_virtual_props
[i
]);
357 duk_put_prop(ctx
, -3);
361 } else if (DUK_HOBJECT_HAS_EXOTIC_DUKFUNC(curr
)) {
362 if (enum_flags
& DUK_ENUM_INCLUDE_NONENUMERABLE
) {
363 duk_push_hstring_stridx(ctx
, DUK_STRIDX_LENGTH
);
365 duk_put_prop(ctx
, -3);
372 * Note: ordering between array and entry part must match 'abandon array'
373 * behavior in duk_hobject_props.c: key order after an array is abandoned
377 for (i
= 0; i
< (duk_uint_fast32_t
) DUK_HOBJECT_GET_ASIZE(curr
); i
++) {
381 tv
= DUK_HOBJECT_A_GET_VALUE_PTR(thr
->heap
, curr
, i
);
382 if (DUK_TVAL_IS_UNUSED(tv
)) {
385 k
= duk_heap_string_intern_u32_checked(thr
, i
);
388 duk_push_hstring(ctx
, k
);
391 /* [enum_target res key true] */
392 duk_put_prop(ctx
, -3);
394 /* [enum_target res] */
401 for (i
= 0; i
< (duk_uint_fast32_t
) DUK_HOBJECT_GET_ENEXT(curr
); i
++) {
404 k
= DUK_HOBJECT_E_GET_KEY(thr
->heap
, curr
, i
);
408 if (!DUK_HOBJECT_E_SLOT_IS_ENUMERABLE(thr
->heap
, curr
, i
) &&
409 !(enum_flags
& DUK_ENUM_INCLUDE_NONENUMERABLE
)) {
412 if (DUK_HSTRING_HAS_INTERNAL(k
) &&
413 !(enum_flags
& DUK_ENUM_INCLUDE_INTERNAL
)) {
416 if ((enum_flags
& DUK_ENUM_ARRAY_INDICES_ONLY
) &&
417 (DUK_HSTRING_GET_ARRIDX_SLOW(k
) == DUK_HSTRING_NO_ARRAY_INDEX
)) {
421 DUK_ASSERT(DUK_HOBJECT_E_SLOT_IS_ACCESSOR(thr
->heap
, curr
, i
) ||
422 !DUK_TVAL_IS_UNUSED(&DUK_HOBJECT_E_GET_VALUE_PTR(thr
->heap
, curr
, i
)->v
));
424 duk_push_hstring(ctx
, k
);
427 /* [enum_target res key true] */
428 duk_put_prop(ctx
, -3);
430 /* [enum_target res] */
433 if (enum_flags
& DUK_ENUM_OWN_PROPERTIES_ONLY
) {
437 curr
= DUK_HOBJECT_GET_PROTOTYPE(thr
->heap
, curr
);
440 /* [enum_target res] */
446 if ((enum_flags
& (DUK_ENUM_ARRAY_INDICES_ONLY
| DUK_ENUM_SORT_ARRAY_INDICES
)) ==
447 (DUK_ENUM_ARRAY_INDICES_ONLY
| DUK_ENUM_SORT_ARRAY_INDICES
)) {
449 * Some E5/E5.1 algorithms require that array indices are iterated
450 * in a strictly ascending order. This is the case for e.g.
451 * Array.prototype.forEach() and JSON.stringify() PropertyList
454 * To ensure this property for arrays with an array part (and
455 * arbitrary objects too, since e.g. forEach() can be applied
456 * to an array), the caller can request that we sort the keys
460 /* XXX: avoid this at least when enum_target is an Array, it has an
461 * array part, and no ancestor properties were included? Not worth
462 * it for JSON, but maybe worth it for forEach().
465 /* XXX: may need a 'length' filter for forEach()
467 DUK_DDD(DUK_DDDPRINT("sort array indices by caller request"));
468 duk__sort_array_indices(thr
, res
);
471 #if defined(DUK_USE_ES6_PROXY)
474 /* compact; no need to seal because object is internal */
475 duk_hobject_compact_props(thr
, res
);
477 DUK_DDD(DUK_DDDPRINT("created enumerator object: %!iT", (duk_tval
*) duk_get_tval(ctx
, -1)));
481 * Returns non-zero if a key and/or value was enumerated, and:
483 * [enum] -> [key] (get_value == 0)
484 * [enum] -> [key value] (get_value == 1)
486 * Returns zero without pushing anything on the stack otherwise.
488 DUK_INTERNAL duk_bool_t
duk_hobject_enumerator_next(duk_context
*ctx
, duk_bool_t get_value
) {
489 duk_hthread
*thr
= (duk_hthread
*) ctx
;
491 duk_hobject
*enum_target
;
492 duk_hstring
*res
= NULL
;
493 duk_uint_fast32_t idx
;
494 duk_bool_t check_existence
;
496 DUK_ASSERT(ctx
!= NULL
);
500 e
= duk_require_hobject(ctx
, -1);
502 /* XXX use get tval ptr, more efficient */
503 duk_get_prop_stridx(ctx
, -1, DUK_STRIDX_INT_NEXT
);
504 idx
= (duk_uint_fast32_t
) duk_require_uint(ctx
, -1);
506 DUK_DDD(DUK_DDDPRINT("enumeration: index is: %ld", (long) idx
));
508 /* Enumeration keys are checked against the enumeration target (to see
509 * that they still exist). In the proxy enumeration case _Target will
510 * be the proxy, and checking key existence against the proxy is not
511 * required (or sensible, as the keys may be fully virtual).
513 duk_get_prop_stridx(ctx
, -1, DUK_STRIDX_INT_TARGET
);
514 enum_target
= duk_require_hobject(ctx
, -1);
515 DUK_ASSERT(enum_target
!= NULL
);
516 #if defined(DUK_USE_ES6_PROXY)
517 check_existence
= (!DUK_HOBJECT_HAS_EXOTIC_PROXYOBJ(enum_target
));
521 duk_pop(ctx
); /* still reachable */
523 DUK_DDD(DUK_DDDPRINT("getting next enum value, enum_target=%!iO, enumerator=%!iT",
524 (duk_heaphdr
*) enum_target
, (duk_tval
*) duk_get_tval(ctx
, -1)));
530 if (idx
>= DUK_HOBJECT_GET_ENEXT(e
)) {
531 DUK_DDD(DUK_DDDPRINT("enumeration: ran out of elements"));
535 /* we know these because enum objects are internally created */
536 k
= DUK_HOBJECT_E_GET_KEY(thr
->heap
, e
, idx
);
537 DUK_ASSERT(k
!= NULL
);
538 DUK_ASSERT(!DUK_HOBJECT_E_SLOT_IS_ACCESSOR(thr
->heap
, e
, idx
));
539 DUK_ASSERT(!DUK_TVAL_IS_UNUSED(&DUK_HOBJECT_E_GET_VALUE(thr
->heap
, e
, idx
).v
));
543 /* recheck that the property still exists */
544 if (check_existence
&& !duk_hobject_hasprop_raw(thr
, enum_target
, k
)) {
545 DUK_DDD(DUK_DDDPRINT("property deleted during enumeration, skip"));
549 DUK_DDD(DUK_DDDPRINT("enumeration: found element, key: %!O", (duk_heaphdr
*) k
));
554 DUK_DDD(DUK_DDDPRINT("enumeration: updating next index to %ld", (long) idx
));
556 duk_push_u32(ctx
, (duk_uint32_t
) idx
);
557 duk_put_prop_stridx(ctx
, -2, DUK_STRIDX_INT_NEXT
);
562 duk_push_hstring(ctx
, res
);
564 duk_push_hobject(ctx
, enum_target
);
565 duk_dup(ctx
, -2); /* -> [... enum key enum_target key] */
566 duk_get_prop(ctx
, -2); /* -> [... enum key enum_target val] */
567 duk_remove(ctx
, -2); /* -> [... enum key val] */
568 duk_remove(ctx
, -3); /* -> [... key val] */
570 duk_remove(ctx
, -2); /* -> [... key] */
574 duk_pop(ctx
); /* -> [...] */
580 * Get enumerated keys in an Ecmascript array. Matches Object.keys() behavior
581 * described in E5 Section 15.2.3.14.
584 DUK_INTERNAL duk_ret_t
duk_hobject_get_enumerated_keys(duk_context
*ctx
, duk_small_uint_t enum_flags
) {
585 duk_hthread
*thr
= (duk_hthread
*) ctx
;
588 duk_uint_fast32_t idx
;
590 DUK_ASSERT(ctx
!= NULL
);
591 DUK_ASSERT(duk_get_hobject(ctx
, -1) != NULL
);
594 /* Create a temporary enumerator to get the (non-duplicated) key list;
595 * the enumerator state is initialized without being needed, but that
599 duk_hobject_enumerator_create(ctx
, enum_flags
);
602 /* [enum_target enum res] */
604 e
= duk_require_hobject(ctx
, -2);
605 DUK_ASSERT(e
!= NULL
);
608 for (i
= DUK__ENUM_START_INDEX
; i
< (duk_uint_fast32_t
) DUK_HOBJECT_GET_ENEXT(e
); i
++) {
611 k
= DUK_HOBJECT_E_GET_KEY(thr
->heap
, e
, i
);
612 DUK_ASSERT(k
); /* enumerator must have no keys deleted */
614 /* [enum_target enum res] */
615 duk_push_hstring(ctx
, k
);
616 duk_put_prop_index(ctx
, -2, idx
);
620 /* [enum_target enum res] */
623 /* [enum_target res] */
625 return 1; /* return 1 to allow callers to tail call */