4 * Note that most Array built-ins are intentionally generic and work even
5 * when the 'this' binding is not an Array instance. To ensure this,
6 * Array algorithms do not assume "magical" Array behavior for the "length"
7 * property, for instance.
9 * XXX: the "Throw" flag should be set for (almost?) all [[Put]] and
10 * [[Delete]] operations, but it's currently false throughout. Go through
11 * all put/delete cases and check throw flag use. Need a new API primitive
12 * which allows throws flag to be specified.
14 * XXX: array lengths above 2G won't work reliably. There are many places
15 * where one needs a full signed 32-bit range ([-0xffffffff, 0xffffffff],
16 * i.e. -33- bits). Although array 'length' cannot be written to be outside
17 * the unsigned 32-bit range (E5.1 Section 15.4.5.1 throws a RangeError if so)
18 * some intermediate values may be above 0xffffffff and this may not be always
19 * correctly handled now (duk_uint32_t is not enough for all algorithms).
21 * For instance, push() can legitimately write entries beyond length 0xffffffff
22 * and cause a RangeError only at the end. To do this properly, the current
23 * push() implementation tracks the array index using a 'double' instead of a
24 * duk_uint32_t (which is somewhat awkward). See test-bi-array-push-maxlen.js.
26 * On using "put" vs. "def" prop
27 * =============================
29 * Code below must be careful to use the appropriate primitive as it matters
30 * for compliance. When using "put" there may be inherited properties in
31 * Array.prototype which cause side effects when values are written. When
32 * using "define" there are no such side effects, and many test262 test cases
33 * check for this (for real world code, such side effects are very rare).
34 * Both "put" and "define" are used in the E5.1 specification; as a rule,
35 * "put" is used when modifying an existing array (or a non-array 'this'
36 * binding) and "define" for setting values into a fresh result array.
38 * Also note that Array instance 'length' should be writable, but not
39 * enumerable and definitely not configurable: even Duktape code internally
40 * assumes that an Array instance will always have a 'length' property.
41 * Preventing deletion of the property is critical.
44 #include "duk_internal.h"
46 /* Perform an intermediate join when this many elements have been pushed
49 #define DUK__ARRAY_MID_JOIN_LIMIT 4096
51 /* Shared entry code for many Array built-ins. Note that length is left
52 * on stack (it could be popped, but that's not necessary).
54 DUK_LOCAL duk_uint32_t
duk__push_this_obj_len_u32(duk_context
*ctx
) {
57 (void) duk_push_this_coercible_to_object(ctx
);
58 duk_get_prop_stridx(ctx
, -1, DUK_STRIDX_LENGTH
);
59 len
= duk_to_uint32(ctx
, -1);
61 /* -> [ ... ToObject(this) ToUint32(length) ] */
65 DUK_LOCAL duk_uint32_t
duk__push_this_obj_len_u32_limited(duk_context
*ctx
) {
66 /* Range limited to [0, 0x7fffffff] range, i.e. range that can be
67 * represented with duk_int32_t. Use this when the method doesn't
68 * handle the full 32-bit unsigned range correctly.
70 duk_uint32_t ret
= duk__push_this_obj_len_u32(ctx
);
71 if (DUK_UNLIKELY(ret
>= 0x80000000UL
)) {
72 DUK_ERROR((duk_hthread
*) ctx
, DUK_ERR_INTERNAL_ERROR
, DUK_STR_ARRAY_LENGTH_OVER_2G
);
81 DUK_INTERNAL duk_ret_t
duk_bi_array_constructor(duk_context
*ctx
) {
87 nargs
= duk_get_top(ctx
);
90 if (nargs
== 1 && duk_is_number(ctx
, 0)) {
91 /* XXX: expensive check (also shared elsewhere - so add a shared internal API call?) */
92 d
= duk_get_number(ctx
, 0);
93 len
= duk_to_uint32(ctx
, 0);
94 if (((duk_double_t
) len
) != d
) {
95 return DUK_RET_RANGE_ERROR
;
98 /* XXX: if 'len' is low, may want to ensure array part is kept:
99 * the caller is likely to want a dense array.
101 duk_push_u32(ctx
, len
);
102 duk_xdef_prop_stridx(ctx
, -2, DUK_STRIDX_LENGTH
, DUK_PROPDESC_FLAGS_W
); /* [ ToUint32(len) array ToUint32(len) ] -> [ ToUint32(len) array ] */
106 /* XXX: optimize by creating array into correct size directly, and
107 * operating on the array part directly; values can be memcpy()'d from
108 * value stack directly as long as refcounts are increased.
110 for (i
= 0; i
< nargs
; i
++) {
112 duk_xdef_prop_index_wec(ctx
, -2, (duk_uarridx_t
) i
);
115 duk_push_u32(ctx
, (duk_uint32_t
) nargs
);
116 duk_xdef_prop_stridx(ctx
, -2, DUK_STRIDX_LENGTH
, DUK_PROPDESC_FLAGS_W
);
124 DUK_INTERNAL duk_ret_t
duk_bi_array_constructor_is_array(duk_context
*ctx
) {
127 h
= duk_get_hobject_with_class(ctx
, 0, DUK_HOBJECT_CLASS_ARRAY
);
128 duk_push_boolean(ctx
, (h
!= NULL
));
136 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_to_string(duk_context
*ctx
) {
137 (void) duk_push_this_coercible_to_object(ctx
);
138 duk_get_prop_stridx(ctx
, -1, DUK_STRIDX_JOIN
);
140 /* [ ... this func ] */
141 if (!duk_is_callable(ctx
, -1)) {
142 /* Fall back to the initial (original) Object.toString(). We don't
143 * currently have pointers to the built-in functions, only the top
144 * level global objects (like "Array") so this is now done in a bit
145 * of a hacky manner. It would be cleaner to push the (original)
146 * function and use duk_call_method().
149 /* XXX: 'this' will be ToObject() coerced twice, which is incorrect
150 * but should have no visible side effects.
152 DUK_DDD(DUK_DDDPRINT("this.join is not callable, fall back to (original) Object.toString"));
154 return duk_bi_object_prototype_to_string(ctx
); /* has access to 'this' binding */
157 /* [ ... this func ] */
161 /* [ ... func this ] */
163 DUK_DDD(DUK_DDDPRINT("calling: func=%!iT, this=%!iT",
164 (duk_tval
*) duk_get_tval(ctx
, -2),
165 (duk_tval
*) duk_get_tval(ctx
, -1)));
166 duk_call_method(ctx
, 0);
175 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_concat(duk_context
*ctx
) {
177 duk_uarridx_t idx
, idx_last
;
178 duk_uarridx_t j
, len
;
181 /* XXX: the insert here is a bit expensive if there are a lot of items.
182 * It could also be special cased in the outermost for loop quite easily
183 * (as the element is dup()'d anyway).
186 (void) duk_push_this_coercible_to_object(ctx
);
188 n
= duk_get_top(ctx
);
189 duk_push_array(ctx
); /* -> [ ToObject(this) item1 ... itemN arr ] */
191 /* NOTE: The Array special behaviors are NOT invoked by duk_xdef_prop_index()
192 * (which differs from the official algorithm). If no error is thrown, this
193 * doesn't matter as the length is updated at the end. However, if an error
194 * is thrown, the length will be unset. That shouldn't matter because the
195 * caller won't get a reference to the intermediate value.
200 for (i
= 0; i
< n
; i
++) {
201 DUK_ASSERT_TOP(ctx
, n
+ 1);
203 /* [ ToObject(this) item1 ... itemN arr ] */
206 h
= duk_get_hobject_with_class(ctx
, -1, DUK_HOBJECT_CLASS_ARRAY
);
208 duk_xdef_prop_index_wec(ctx
, -2, idx
++);
213 /* [ ToObject(this) item1 ... itemN arr item(i) ] */
215 /* XXX: an array can have length higher than 32 bits; this is not handled
218 len
= (duk_uarridx_t
) duk_get_length(ctx
, -1);
219 for (j
= 0; j
< len
; j
++) {
220 if (duk_get_prop_index(ctx
, -1, j
)) {
221 /* [ ToObject(this) item1 ... itemN arr item(i) item(i)[j] ] */
222 duk_xdef_prop_index_wec(ctx
, -3, idx
++);
227 #if defined(DUK_USE_NONSTD_ARRAY_CONCAT_TRAILER)
228 /* According to E5.1 Section 15.4.4.4 nonexistent trailing
229 * elements do not affect 'length' of the result. Test262
230 * and other engines disagree, so update idx_last here too.
234 /* Strict standard behavior, ignore trailing elements for
243 /* The E5.1 Section 15.4.4.4 algorithm doesn't set the length explicitly
244 * in the end, but because we're operating with an internal value which
245 * is known to be an array, this should be equivalent.
247 duk_push_uarridx(ctx
, idx_last
);
248 duk_xdef_prop_stridx(ctx
, -2, DUK_STRIDX_LENGTH
, DUK_PROPDESC_FLAGS_W
);
250 DUK_ASSERT_TOP(ctx
, n
+ 1);
255 * join(), toLocaleString()
257 * Note: checking valstack is necessary, but only in the per-element loop.
259 * Note: the trivial approach of pushing all the elements on the value stack
260 * and then calling duk_join() fails when the array contains a large number
261 * of elements. This problem can't be offloaded to duk_join() because the
262 * elements to join must be handled here and have special handling. Current
263 * approach is to do intermediate joins with very large number of elements.
264 * There is no fancy handling; the prefix gets re-joined multiple times.
267 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_join_shared(duk_context
*ctx
) {
268 duk_uint32_t len
, count
;
270 duk_small_int_t to_locale_string
= duk_get_current_magic(ctx
);
271 duk_idx_t valstack_required
;
273 /* For join(), nargs is 1. For toLocaleString(), nargs is 0 and
274 * setting the top essentially pushes an undefined to the stack,
275 * thus defaulting to a comma separator.
278 if (duk_is_undefined(ctx
, 0)) {
280 duk_push_hstring_stridx(ctx
, DUK_STRIDX_COMMA
);
282 duk_to_string(ctx
, 0);
285 len
= duk__push_this_obj_len_u32(ctx
);
287 /* [ sep ToObject(this) len ] */
289 DUK_DDD(DUK_DDDPRINT("sep=%!T, this=%!T, len=%lu",
290 (duk_tval
*) duk_get_tval(ctx
, 0),
291 (duk_tval
*) duk_get_tval(ctx
, 1),
292 (unsigned long) len
));
294 /* The extra (+4) is tight. */
295 valstack_required
= (len
>= DUK__ARRAY_MID_JOIN_LIMIT
?
296 DUK__ARRAY_MID_JOIN_LIMIT
: len
) + 4;
297 duk_require_stack(ctx
, valstack_required
);
301 /* [ sep ToObject(this) len sep ] */
306 if (count
>= DUK__ARRAY_MID_JOIN_LIMIT
|| /* intermediate join to avoid valstack overflow */
307 idx
>= len
) { /* end of loop (careful with len==0) */
308 /* [ sep ToObject(this) len sep str0 ... str(count-1) ] */
309 DUK_DDD(DUK_DDDPRINT("mid/final join, count=%ld, idx=%ld, len=%ld",
310 (long) count
, (long) idx
, (long) len
));
311 duk_join(ctx
, (duk_idx_t
) count
); /* -> [ sep ToObject(this) len str ] */
312 duk_dup(ctx
, 0); /* -> [ sep ToObject(this) len str sep ] */
313 duk_insert(ctx
, -2); /* -> [ sep ToObject(this) len sep str ] */
317 /* if true, the stack already contains the final result */
321 duk_get_prop_index(ctx
, 1, (duk_uarridx_t
) idx
);
322 if (duk_is_null_or_undefined(ctx
, -1)) {
324 duk_push_hstring_stridx(ctx
, DUK_STRIDX_EMPTY_STRING
);
326 if (to_locale_string
) {
327 duk_to_object(ctx
, -1);
328 duk_get_prop_stridx(ctx
, -1, DUK_STRIDX_TO_LOCALE_STRING
);
329 duk_insert(ctx
, -2); /* -> [ ... toLocaleString ToObject(val) ] */
330 duk_call_method(ctx
, 0);
331 duk_to_string(ctx
, -1);
333 duk_to_string(ctx
, -1);
341 /* [ sep ToObject(this) len sep result ] */
350 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_pop(duk_context
*ctx
) {
354 DUK_ASSERT_TOP(ctx
, 0);
355 len
= duk__push_this_obj_len_u32(ctx
);
357 duk_push_int(ctx
, 0);
358 duk_put_prop_stridx(ctx
, 0, DUK_STRIDX_LENGTH
);
363 duk_get_prop_index(ctx
, 0, (duk_uarridx_t
) idx
);
364 duk_del_prop_index(ctx
, 0, (duk_uarridx_t
) idx
);
365 duk_push_u32(ctx
, idx
);
366 duk_put_prop_stridx(ctx
, 0, DUK_STRIDX_LENGTH
);
370 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_push(duk_context
*ctx
) {
371 /* Note: 'this' is not necessarily an Array object. The push()
372 * algorithm is supposed to work for other kinds of objects too,
373 * so the algorithm has e.g. an explicit update for the 'length'
374 * property which is normally "magical" in arrays.
380 n
= duk_get_top(ctx
);
381 len
= duk__push_this_obj_len_u32(ctx
);
383 /* [ arg1 ... argN obj length ] */
385 /* Technically Array.prototype.push() can create an Array with length
386 * longer than 2^32-1, i.e. outside the 32-bit range. The final length
387 * is *not* wrapped to 32 bits in the specification.
389 * This implementation tracks length with a uint32 because it's much
392 * See: test-bi-array-push-maxlen.js.
395 if (len
+ (duk_uint32_t
) n
< len
) {
396 DUK_D(DUK_DPRINT("Array.prototype.push() would go beyond 32-bit length, throw"));
397 return DUK_RET_RANGE_ERROR
;
400 for (i
= 0; i
< n
; i
++) {
402 duk_put_prop_index(ctx
, -3, len
+ i
);
406 duk_push_u32(ctx
, len
);
408 duk_put_prop_stridx(ctx
, -4, DUK_STRIDX_LENGTH
);
410 /* [ arg1 ... argN obj length new_length ] */
417 * Currently qsort with random pivot. This is now really, really slow,
418 * because there is no fast path for array parts.
420 * Signed indices are used because qsort() leaves and degenerate cases
421 * may use a negative offset.
424 DUK_LOCAL duk_small_int_t
duk__array_sort_compare(duk_context
*ctx
, duk_int_t idx1
, duk_int_t idx2
) {
425 duk_bool_t have1
, have2
;
426 duk_bool_t undef1
, undef2
;
428 duk_idx_t idx_obj
= 1; /* fixed offsets in valstack */
429 duk_idx_t idx_fn
= 0;
430 duk_hstring
*h1
, *h2
;
432 /* Fast exit if indices are identical. This is valid for a non-existent property,
433 * for an undefined value, and almost always for ToString() coerced comparison of
434 * arbitrary values (corner cases where this is not the case include e.g. a an
435 * object with varying ToString() coercion).
437 * The specification does not prohibit "caching" of values read from the array, so
438 * assuming equality for comparing an index with itself falls into the category of
441 * Also, compareFn may be inconsistent, so skipping a call to compareFn here may
442 * have an effect on the final result. The specification does not require any
443 * specific behavior for inconsistent compare functions, so again, this fast path
448 DUK_DDD(DUK_DDDPRINT("duk__array_sort_compare: idx1=%ld, idx2=%ld -> indices identical, quick exit",
449 (long) idx1
, (long) idx2
));
453 have1
= duk_get_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) idx1
);
454 have2
= duk_get_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) idx2
);
456 DUK_DDD(DUK_DDDPRINT("duk__array_sort_compare: idx1=%ld, idx2=%ld, have1=%ld, have2=%ld, val1=%!T, val2=%!T",
457 (long) idx1
, (long) idx2
, (long) have1
, (long) have2
,
458 (duk_tval
*) duk_get_tval(ctx
, -2), (duk_tval
*) duk_get_tval(ctx
, -1)));
477 undef1
= duk_is_undefined(ctx
, -2);
478 undef2
= duk_is_undefined(ctx
, -1);
496 if (!duk_is_undefined(ctx
, idx_fn
)) {
499 /* no need to check callable; duk_call() will do that */
500 duk_dup(ctx
, idx_fn
); /* -> [ ... x y fn ] */
501 duk_insert(ctx
, -3); /* -> [ ... fn x y ] */
502 duk_call(ctx
, 2); /* -> [ ... res ] */
504 /* The specification is a bit vague what to do if the return
505 * value is not a number. Other implementations seem to
506 * tolerate non-numbers but e.g. V8 won't apparently do a
510 /* XXX: best behavior for real world compatibility? */
512 d
= duk_to_number(ctx
, -1);
515 } else if (d
> 0.0) {
522 DUK_DDD(DUK_DDDPRINT("-> result %ld (from comparefn, after coercion)", (long) ret
));
526 /* string compare is the default (a bit oddly) */
528 h1
= duk_to_hstring(ctx
, -2);
529 h2
= duk_to_hstring(ctx
, -1);
530 DUK_ASSERT(h1
!= NULL
);
531 DUK_ASSERT(h2
!= NULL
);
533 ret
= duk_js_string_compare(h1
, h2
); /* retval is directly usable */
538 DUK_DDD(DUK_DDDPRINT("-> result %ld", (long) ret
));
542 DUK_LOCAL
void duk__array_sort_swap(duk_context
*ctx
, duk_int_t l
, duk_int_t r
) {
543 duk_bool_t have_l
, have_r
;
544 duk_idx_t idx_obj
= 1; /* fixed offset in valstack */
550 /* swap elements; deal with non-existent elements correctly */
551 have_l
= duk_get_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) l
);
552 have_r
= duk_get_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) r
);
555 /* right exists, [[Put]] regardless whether or not left exists */
556 duk_put_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) l
);
558 duk_del_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) l
);
563 duk_put_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) r
);
565 duk_del_prop_index(ctx
, idx_obj
, (duk_uarridx_t
) r
);
570 #if defined(DUK_USE_DDDPRINT)
571 /* Debug print which visualizes the qsort partitioning process. */
572 DUK_LOCAL
void duk__debuglog_qsort_state(duk_context
*ctx
, duk_int_t lo
, duk_int_t hi
, duk_int_t pivot
) {
576 n
= (duk_int_t
) duk_get_length(ctx
, 1);
581 for (i
= 0; i
< n
; i
++) {
584 } else if (i
== lo
) {
586 } else if (i
== hi
) {
588 } else if (i
>= lo
&& i
<= hi
) {
597 DUK_DDD(DUK_DDDPRINT("%s (lo=%ld, hi=%ld, pivot=%ld)",
598 (const char *) buf
, (long) lo
, (long) hi
, (long) pivot
));
602 DUK_LOCAL
void duk__array_qsort(duk_context
*ctx
, duk_int_t lo
, duk_int_t hi
) {
603 duk_hthread
*thr
= (duk_hthread
*) ctx
;
606 /* The lo/hi indices may be crossed and hi < 0 is possible at entry. */
608 DUK_DDD(DUK_DDDPRINT("duk__array_qsort: lo=%ld, hi=%ld, obj=%!T",
609 (long) lo
, (long) hi
, (duk_tval
*) duk_get_tval(ctx
, 1)));
611 DUK_ASSERT_TOP(ctx
, 3);
613 /* In some cases it may be that lo > hi, or hi < 0; these
614 * degenerate cases happen e.g. for empty arrays, and in
620 DUK_DDD(DUK_DDDPRINT("degenerate case, return immediately"));
624 DUK_ASSERT(hi
- lo
+ 1 >= 2);
626 /* randomized pivot selection */
627 p
= lo
+ (duk_util_tinyrandom_get_bits(thr
, 30) % (hi
- lo
+ 1)); /* rnd in [lo,hi] */
628 DUK_ASSERT(p
>= lo
&& p
<= hi
);
629 DUK_DDD(DUK_DDDPRINT("lo=%ld, hi=%ld, chose pivot p=%ld",
630 (long) lo
, (long) hi
, (long) p
));
632 /* move pivot out of the way */
633 duk__array_sort_swap(ctx
, p
, lo
);
635 DUK_DDD(DUK_DDDPRINT("pivot moved out of the way: %!T", (duk_tval
*) duk_get_tval(ctx
, 1)));
640 /* find elements to swap */
642 DUK_DDD(DUK_DDDPRINT("left scan: l=%ld, r=%ld, p=%ld",
643 (long) l
, (long) r
, (long) p
));
647 if (duk__array_sort_compare(ctx
, l
, p
) >= 0) { /* !(l < p) */
653 DUK_DDD(DUK_DDDPRINT("right scan: l=%ld, r=%ld, p=%ld",
654 (long) l
, (long) r
, (long) p
));
658 if (duk__array_sort_compare(ctx
, p
, r
) >= 0) { /* !(p < r) */
668 DUK_DDD(DUK_DDDPRINT("swap %ld and %ld", (long) l
, (long) r
));
670 duk__array_sort_swap(ctx
, l
, r
);
672 DUK_DDD(DUK_DDDPRINT("after swap: %!T", (duk_tval
*) duk_get_tval(ctx
, 1)));
677 /* Note that 'l' and 'r' may cross, i.e. r < l */
678 DUK_ASSERT(l
>= lo
&& l
<= hi
);
679 DUK_ASSERT(r
>= lo
&& r
<= hi
);
681 /* XXX: there's no explicit recursion bound here now. For the average
682 * qsort recursion depth O(log n) that's not really necessary: e.g. for
683 * 2**32 recursion depth would be about 32 which is OK. However, qsort
684 * worst case recursion depth is O(n) which may be a problem.
687 /* move pivot to its final place */
688 DUK_DDD(DUK_DDDPRINT("before final pivot swap: %!T", (duk_tval
*) duk_get_tval(ctx
, 1)));
689 duk__array_sort_swap(ctx
, lo
, r
);
691 #if defined(DUK_USE_DDDPRINT)
692 duk__debuglog_qsort_state(ctx
, lo
, hi
, r
);
695 DUK_DDD(DUK_DDDPRINT("recurse: pivot=%ld, obj=%!T", (long) r
, (duk_tval
*) duk_get_tval(ctx
, 1)));
696 duk__array_qsort(ctx
, lo
, r
- 1);
697 duk__array_qsort(ctx
, r
+ 1, hi
);
700 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_sort(duk_context
*ctx
) {
703 /* XXX: len >= 0x80000000 won't work below because a signed type
704 * is needed by qsort.
706 len
= duk__push_this_obj_len_u32_limited(ctx
);
708 /* stack[0] = compareFn
709 * stack[1] = ToObject(this)
710 * stack[2] = ToUint32(length)
714 /* avoid degenerate cases, so that (len - 1) won't underflow */
715 duk__array_qsort(ctx
, (duk_int_t
) 0, (duk_int_t
) (len
- 1));
718 DUK_ASSERT_TOP(ctx
, 3);
720 return 1; /* return ToObject(this) */
727 /* XXX: this compiles to over 500 bytes now, even without special handling
728 * for an array part. Uses signed ints so does not handle full array range correctly.
731 /* XXX: can shift() / unshift() use the same helper?
732 * shift() is (close to?) <--> splice(0, 1)
733 * unshift is (close to?) <--> splice(0, 0, [items])?
736 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_splice(duk_context
*ctx
) {
739 duk_bool_t have_delcount
;
740 duk_int_t item_count
;
745 DUK_UNREF(have_delcount
);
747 nargs
= duk_get_top(ctx
);
756 /* XXX: len >= 0x80000000 won't work below because we need to be
757 * able to represent -len.
759 len
= duk__push_this_obj_len_u32_limited(ctx
);
761 act_start
= duk_to_int_clamped(ctx
, 0, -((duk_int_t
) len
), (duk_int_t
) len
);
763 act_start
= len
+ act_start
;
765 DUK_ASSERT(act_start
>= 0 && act_start
<= (duk_int_t
) len
);
767 #ifdef DUK_USE_NONSTD_ARRAY_SPLICE_DELCOUNT
770 del_count
= duk_to_int_clamped(ctx
, 1, 0, len
- act_start
);
771 #ifdef DUK_USE_NONSTD_ARRAY_SPLICE_DELCOUNT
773 /* E5.1 standard behavior when deleteCount is not given would be
774 * to treat it just like if 'undefined' was given, which coerces
775 * ultimately to 0. Real world behavior is to splice to the end
776 * of array, see test-bi-array-proto-splice-no-delcount.js.
778 del_count
= len
- act_start
;
782 DUK_ASSERT(nargs
>= 2);
783 item_count
= (duk_int_t
) (nargs
- 2);
785 DUK_ASSERT(del_count
>= 0 && del_count
<= (duk_int_t
) len
- act_start
);
786 DUK_ASSERT(del_count
+ act_start
<= (duk_int_t
) len
);
788 /* For now, restrict result array into 32-bit length range. */
789 if (((duk_double_t
) len
) - ((duk_double_t
) del_count
) + ((duk_double_t
) item_count
) > (duk_double_t
) DUK_UINT32_MAX
) {
790 DUK_D(DUK_DPRINT("Array.prototype.splice() would go beyond 32-bit length, throw"));
791 return DUK_RET_RANGE_ERROR
;
797 * stack[1] = deleteCount
798 * stack[2...nargs-1] = items
799 * stack[nargs] = ToObject(this) -3
800 * stack[nargs+1] = ToUint32(length) -2
801 * stack[nargs+2] = result array -1
804 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
806 /* Step 9: copy elements-to-be-deleted into the result array */
808 for (i
= 0; i
< del_count
; i
++) {
809 if (duk_get_prop_index(ctx
, -3, (duk_uarridx_t
) (act_start
+ i
))) {
810 duk_xdef_prop_index_wec(ctx
, -2, i
); /* throw flag irrelevant (false in std alg) */
815 duk_push_u32(ctx
, (duk_uint32_t
) del_count
);
816 duk_xdef_prop_stridx(ctx
, -2, DUK_STRIDX_LENGTH
, DUK_PROPDESC_FLAGS_W
);
818 /* Steps 12 and 13: reorganize elements to make room for itemCount elements */
820 if (item_count
< del_count
) {
821 /* [ A B C D E F G H ] rel_index = 2, del_count 3, item count 1
822 * -> [ A B F G H ] (conceptual intermediate step)
823 * -> [ A B . F G H ] (placeholder marked)
824 * [ A B C F G H ] (actual result at this point, C will be replaced)
827 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
830 for (i
= act_start
; i
< n
; i
++) {
831 if (duk_get_prop_index(ctx
, -3, (duk_uarridx_t
) (i
+ del_count
))) {
832 duk_put_prop_index(ctx
, -4, (duk_uarridx_t
) (i
+ item_count
));
835 duk_del_prop_index(ctx
, -3, (duk_uarridx_t
) (i
+ item_count
));
839 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
841 /* loop iterator init and limit changed from standard algorithm */
842 n
= len
- del_count
+ item_count
;
843 for (i
= len
- 1; i
>= n
; i
--) {
844 duk_del_prop_index(ctx
, -3, (duk_uarridx_t
) i
);
847 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
848 } else if (item_count
> del_count
) {
849 /* [ A B C D E F G H ] rel_index = 2, del_count 3, item count 4
850 * -> [ A B F G H ] (conceptual intermediate step)
851 * -> [ A B . . . . F G H ] (placeholder marked)
852 * [ A B C D E F F G H ] (actual result at this point)
855 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
857 /* loop iterator init and limit changed from standard algorithm */
858 for (i
= len
- del_count
- 1; i
>= act_start
; i
--) {
859 if (duk_get_prop_index(ctx
, -3, (duk_uarridx_t
) (i
+ del_count
))) {
860 duk_put_prop_index(ctx
, -4, (duk_uarridx_t
) (i
+ item_count
));
863 duk_del_prop_index(ctx
, -3, (duk_uarridx_t
) (i
+ item_count
));
867 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
869 /* [ A B C D E F G H ] rel_index = 2, del_count 3, item count 3
870 * -> [ A B F G H ] (conceptual intermediate step)
871 * -> [ A B . . . F G H ] (placeholder marked)
872 * [ A B C D E F G H ] (actual result at this point)
875 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
877 /* Step 15: insert itemCount elements into the hole made above */
879 for (i
= 0; i
< item_count
; i
++) {
880 duk_dup(ctx
, i
+ 2); /* args start at index 2 */
881 duk_put_prop_index(ctx
, -4, (duk_uarridx_t
) (act_start
+ i
));
884 /* Step 16: update length; note that the final length may be above 32 bit range
885 * (but we checked above that this isn't the case here)
888 duk_push_u32(ctx
, len
- del_count
+ item_count
);
889 duk_put_prop_stridx(ctx
, -4, DUK_STRIDX_LENGTH
);
891 /* result array is already at the top of stack */
892 DUK_ASSERT_TOP(ctx
, nargs
+ 3);
900 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_reverse(duk_context
*ctx
) {
903 duk_uint32_t lower
, upper
;
904 duk_bool_t have_lower
, have_upper
;
906 len
= duk__push_this_obj_len_u32(ctx
);
909 /* If len <= 1, middle will be 0 and for-loop bails out
910 * immediately (0 < 0 -> false).
913 for (lower
= 0; lower
< middle
; lower
++) {
914 DUK_ASSERT(len
>= 2);
915 DUK_ASSERT_TOP(ctx
, 2);
917 DUK_ASSERT(len
>= lower
+ 1);
918 upper
= len
- lower
- 1;
920 have_lower
= duk_get_prop_index(ctx
, -2, (duk_uarridx_t
) lower
);
921 have_upper
= duk_get_prop_index(ctx
, -3, (duk_uarridx_t
) upper
);
923 /* [ ToObject(this) ToUint32(length) lowerValue upperValue ] */
926 duk_put_prop_index(ctx
, -4, (duk_uarridx_t
) lower
);
928 duk_del_prop_index(ctx
, -4, (duk_uarridx_t
) lower
);
933 duk_put_prop_index(ctx
, -3, (duk_uarridx_t
) upper
);
935 duk_del_prop_index(ctx
, -3, (duk_uarridx_t
) upper
);
939 DUK_ASSERT_TOP(ctx
, 2);
942 DUK_ASSERT_TOP(ctx
, 2);
943 duk_pop(ctx
); /* -> [ ToObject(this) ] */
951 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_slice(duk_context
*ctx
) {
953 duk_int_t start
, end
;
956 duk_uint32_t res_length
= 0;
958 /* XXX: len >= 0x80000000 won't work below because we need to be
959 * able to represent -len.
961 len
= duk__push_this_obj_len_u32_limited(ctx
);
966 * stack[2] = ToObject(this)
967 * stack[3] = ToUint32(length)
968 * stack[4] = result array
971 start
= duk_to_int_clamped(ctx
, 0, -((duk_int_t
) len
), (duk_int_t
) len
);
975 /* XXX: could duk_is_undefined() provide defaulting undefined to 'len'
978 if (duk_is_undefined(ctx
, 1)) {
981 end
= duk_to_int_clamped(ctx
, 1, -((duk_int_t
) len
), (duk_int_t
) len
);
986 DUK_ASSERT(start
>= 0 && (duk_uint32_t
) start
<= len
);
987 DUK_ASSERT(end
>= 0 && (duk_uint32_t
) end
<= len
);
990 for (i
= start
; i
< end
; i
++) {
991 DUK_ASSERT_TOP(ctx
, 5);
992 if (duk_get_prop_index(ctx
, 2, (duk_uarridx_t
) i
)) {
993 duk_xdef_prop_index_wec(ctx
, 4, idx
);
994 res_length
= idx
+ 1;
999 DUK_ASSERT_TOP(ctx
, 5);
1002 duk_push_u32(ctx
, res_length
);
1003 duk_xdef_prop_stridx(ctx
, 4, DUK_STRIDX_LENGTH
, DUK_PROPDESC_FLAGS_W
);
1005 DUK_ASSERT_TOP(ctx
, 5);
1013 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_shift(duk_context
*ctx
) {
1017 len
= duk__push_this_obj_len_u32(ctx
);
1019 duk_push_int(ctx
, 0);
1020 duk_put_prop_stridx(ctx
, 0, DUK_STRIDX_LENGTH
);
1024 duk_get_prop_index(ctx
, 0, 0);
1026 /* stack[0] = object (this)
1027 * stack[1] = ToUint32(length)
1028 * stack[2] = elem at index 0 (retval)
1031 for (i
= 1; i
< len
; i
++) {
1032 DUK_ASSERT_TOP(ctx
, 3);
1033 if (duk_get_prop_index(ctx
, 0, (duk_uarridx_t
) i
)) {
1034 /* fromPresent = true */
1035 duk_put_prop_index(ctx
, 0, (duk_uarridx_t
) (i
- 1));
1037 /* fromPresent = false */
1038 duk_del_prop_index(ctx
, 0, (duk_uarridx_t
) (i
- 1));
1042 duk_del_prop_index(ctx
, 0, (duk_uarridx_t
) (len
- 1));
1044 duk_push_u32(ctx
, (duk_uint32_t
) (len
- 1));
1045 duk_put_prop_stridx(ctx
, 0, DUK_STRIDX_LENGTH
);
1047 DUK_ASSERT_TOP(ctx
, 3);
1055 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_unshift(duk_context
*ctx
) {
1060 nargs
= duk_get_top(ctx
);
1061 len
= duk__push_this_obj_len_u32(ctx
);
1063 /* stack[0...nargs-1] = unshift args (vararg)
1064 * stack[nargs] = ToObject(this)
1065 * stack[nargs+1] = ToUint32(length)
1068 DUK_ASSERT_TOP(ctx
, nargs
+ 2);
1070 /* Note: unshift() may operate on indices above unsigned 32-bit range
1071 * and the final length may be >= 2**32. However, we restrict the
1072 * final result to 32-bit range for practicality.
1075 if (len
+ (duk_uint32_t
) nargs
< len
) {
1076 DUK_D(DUK_DPRINT("Array.prototype.unshift() would go beyond 32-bit length, throw"));
1077 return DUK_RET_RANGE_ERROR
;
1082 DUK_ASSERT_TOP(ctx
, nargs
+ 2);
1084 /* k+argCount-1; note that may be above 32-bit range */
1086 if (duk_get_prop_index(ctx
, -2, (duk_uarridx_t
) i
)) {
1087 /* fromPresent = true */
1088 /* [ ... ToObject(this) ToUint32(length) val ] */
1089 duk_put_prop_index(ctx
, -3, (duk_uarridx_t
) (i
+ nargs
)); /* -> [ ... ToObject(this) ToUint32(length) ] */
1091 /* fromPresent = false */
1092 /* [ ... ToObject(this) ToUint32(length) val ] */
1094 duk_del_prop_index(ctx
, -2, (duk_uarridx_t
) (i
+ nargs
)); /* -> [ ... ToObject(this) ToUint32(length) ] */
1096 DUK_ASSERT_TOP(ctx
, nargs
+ 2);
1099 for (i
= 0; i
< (duk_uint32_t
) nargs
; i
++) {
1100 DUK_ASSERT_TOP(ctx
, nargs
+ 2);
1101 duk_dup(ctx
, i
); /* -> [ ... ToObject(this) ToUint32(length) arg[i] ] */
1102 duk_put_prop_index(ctx
, -3, (duk_uarridx_t
) i
);
1103 DUK_ASSERT_TOP(ctx
, nargs
+ 2);
1106 DUK_ASSERT_TOP(ctx
, nargs
+ 2);
1107 duk_push_u32(ctx
, len
+ nargs
);
1108 duk_dup_top(ctx
); /* -> [ ... ToObject(this) ToUint32(length) final_len final_len ] */
1109 duk_put_prop_stridx(ctx
, -4, DUK_STRIDX_LENGTH
);
1114 * indexOf(), lastIndexOf()
1117 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_indexof_shared(duk_context
*ctx
) {
1120 duk_int_t from_index
;
1121 duk_small_int_t idx_step
= duk_get_current_magic(ctx
); /* idx_step is +1 for indexOf, -1 for lastIndexOf */
1123 /* lastIndexOf() needs to be a vararg function because we must distinguish
1124 * between an undefined fromIndex and a "not given" fromIndex; indexOf() is
1125 * made vararg for symmetry although it doesn't strictly need to be.
1128 nargs
= duk_get_top(ctx
);
1129 duk_set_top(ctx
, 2);
1131 /* XXX: must be able to represent -len */
1132 len
= (duk_int_t
) duk__push_this_obj_len_u32_limited(ctx
);
1137 /* Index clamping is a bit tricky, we must ensure that we'll only iterate
1138 * through elements that exist and that the specific requirements from E5.1
1139 * Sections 15.4.4.14 and 15.4.4.15 are fulfilled; especially:
1141 * - indexOf: clamp to [-len,len], negative handling -> [0,len],
1142 * if clamped result is len, for-loop bails out immediately
1144 * - lastIndexOf: clamp to [-len-1, len-1], negative handling -> [-1, len-1],
1145 * if clamped result is -1, for-loop bails out immediately
1147 * If fromIndex is not given, ToInteger(undefined) = 0, which is correct
1148 * for indexOf() but incorrect for lastIndexOf(). Hence special handling,
1149 * and why lastIndexOf() needs to be a vararg function.
1153 /* indexOf: clamp fromIndex to [-len, len]
1154 * (if fromIndex == len, for-loop terminates directly)
1156 * lastIndexOf: clamp fromIndex to [-len - 1, len - 1]
1157 * (if clamped to -len-1 -> fromIndex becomes -1, terminates for-loop directly)
1159 from_index
= duk_to_int_clamped(ctx
,
1161 (idx_step
> 0 ? -len
: -len
- 1),
1162 (idx_step
> 0 ? len
: len
- 1));
1163 if (from_index
< 0) {
1164 /* for lastIndexOf, result may be -1 (mark immediate termination) */
1165 from_index
= len
+ from_index
;
1168 /* for indexOf, ToInteger(undefined) would be 0, i.e. correct, but
1169 * handle both indexOf and lastIndexOf specially here.
1174 from_index
= len
- 1;
1178 /* stack[0] = searchElement
1179 * stack[1] = fromIndex
1181 * stack[3] = length (not needed, but not popped above)
1184 for (i
= from_index
; i
>= 0 && i
< len
; i
+= idx_step
) {
1185 DUK_ASSERT_TOP(ctx
, 4);
1187 if (duk_get_prop_index(ctx
, 2, (duk_uarridx_t
) i
)) {
1188 DUK_ASSERT_TOP(ctx
, 5);
1189 if (duk_strict_equals(ctx
, 0, 4)) {
1190 duk_push_int(ctx
, i
);
1199 duk_push_int(ctx
, -1);
1204 * every(), some(), forEach(), map(), filter()
1207 #define DUK__ITER_EVERY 0
1208 #define DUK__ITER_SOME 1
1209 #define DUK__ITER_FOREACH 2
1210 #define DUK__ITER_MAP 3
1211 #define DUK__ITER_FILTER 4
1213 /* XXX: This helper is a bit awkward because the handling for the different iteration
1214 * callers is quite different. This now compiles to a bit less than 500 bytes, so with
1215 * 5 callers the net result is about 100 bytes / caller.
1218 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_iter_shared(duk_context
*ctx
) {
1223 duk_small_int_t iter_type
= duk_get_current_magic(ctx
);
1224 duk_uint32_t res_length
= 0;
1226 /* each call this helper serves has nargs==2 */
1227 DUK_ASSERT_TOP(ctx
, 2);
1229 len
= duk__push_this_obj_len_u32(ctx
);
1230 if (!duk_is_callable(ctx
, 0)) {
1233 /* if thisArg not supplied, behave as if undefined was supplied */
1235 if (iter_type
== DUK__ITER_MAP
|| iter_type
== DUK__ITER_FILTER
) {
1236 duk_push_array(ctx
);
1238 duk_push_undefined(ctx
);
1241 /* stack[0] = callback
1242 * stack[1] = thisArg
1244 * stack[3] = ToUint32(length) (unused, but avoid unnecessary pop)
1245 * stack[4] = result array (or undefined)
1248 k
= 0; /* result index for filter() */
1249 for (i
= 0; i
< len
; i
++) {
1250 DUK_ASSERT_TOP(ctx
, 5);
1252 if (!duk_get_prop_index(ctx
, 2, (duk_uarridx_t
) i
)) {
1253 #if defined(DUK_USE_NONSTD_ARRAY_MAP_TRAILER)
1254 /* Real world behavior for map(): trailing non-existent
1255 * elements don't invoke the user callback, but are still
1256 * counted towards result 'length'.
1258 if (iter_type
== DUK__ITER_MAP
) {
1262 /* Standard behavior for map(): trailing non-existent
1263 * elements don't invoke the user callback and are not
1264 * counted towards result 'length'.
1271 /* The original value needs to be preserved for filter(), hence
1272 * this funny order. We can't re-get the value because of side
1279 duk_push_u32(ctx
, i
);
1280 duk_dup(ctx
, 2); /* [ ... val callback thisArg val i obj ] */
1281 duk_call_method(ctx
, 3); /* -> [ ... val retval ] */
1283 switch (iter_type
) {
1284 case DUK__ITER_EVERY
:
1285 bval
= duk_to_boolean(ctx
, -1);
1287 /* stack top contains 'false' */
1291 case DUK__ITER_SOME
:
1292 bval
= duk_to_boolean(ctx
, -1);
1294 /* stack top contains 'true' */
1298 case DUK__ITER_FOREACH
:
1303 duk_xdef_prop_index_wec(ctx
, 4, (duk_uarridx_t
) i
); /* retval to result[i] */
1306 case DUK__ITER_FILTER
:
1307 bval
= duk_to_boolean(ctx
, -1);
1309 duk_dup(ctx
, -2); /* orig value */
1310 duk_xdef_prop_index_wec(ctx
, 4, (duk_uarridx_t
) k
);
1321 DUK_ASSERT_TOP(ctx
, 5);
1324 switch (iter_type
) {
1325 case DUK__ITER_EVERY
:
1328 case DUK__ITER_SOME
:
1329 duk_push_false(ctx
);
1331 case DUK__ITER_FOREACH
:
1332 duk_push_undefined(ctx
);
1335 case DUK__ITER_FILTER
:
1336 DUK_ASSERT_TOP(ctx
, 5);
1337 DUK_ASSERT(duk_is_array(ctx
, -1)); /* topmost element is the result array already */
1338 duk_push_u32(ctx
, res_length
);
1339 duk_xdef_prop_stridx(ctx
, -2, DUK_STRIDX_LENGTH
, DUK_PROPDESC_FLAGS_W
);
1349 return DUK_RET_TYPE_ERROR
;
1353 * reduce(), reduceRight()
1356 DUK_INTERNAL duk_ret_t
duk_bi_array_prototype_reduce_shared(duk_context
*ctx
) {
1358 duk_bool_t have_acc
;
1359 duk_uint32_t i
, len
;
1360 duk_small_int_t idx_step
= duk_get_current_magic(ctx
); /* idx_step is +1 for reduce, -1 for reduceRight */
1362 /* We're a varargs function because we need to detect whether
1363 * initialValue was given or not.
1365 nargs
= duk_get_top(ctx
);
1366 DUK_DDD(DUK_DDDPRINT("nargs=%ld", (long) nargs
));
1368 duk_set_top(ctx
, 2);
1369 len
= duk__push_this_obj_len_u32(ctx
);
1370 if (!duk_is_callable(ctx
, 0)) {
1374 /* stack[0] = callback fn
1375 * stack[1] = initialValue
1376 * stack[2] = object (coerced this)
1377 * stack[3] = length (not needed, but not popped above)
1378 * stack[4] = accumulator
1386 DUK_DDD(DUK_DDDPRINT("have_acc=%ld, acc=%!T",
1387 (long) have_acc
, (duk_tval
*) duk_get_tval(ctx
, 3)));
1389 /* For len == 0, i is initialized to len - 1 which underflows.
1390 * The condition (i < len) will then exit the for-loop on the
1391 * first round which is correct. Similarly, loop termination
1392 * happens by i underflowing.
1395 for (i
= (idx_step
>= 0 ? 0 : len
- 1);
1396 i
< len
; /* i >= 0 would always be true */
1398 DUK_DDD(DUK_DDDPRINT("i=%ld, len=%ld, have_acc=%ld, top=%ld, acc=%!T",
1399 (long) i
, (long) len
, (long) have_acc
,
1400 (long) duk_get_top(ctx
),
1401 (duk_tval
*) duk_get_tval(ctx
, 4)));
1403 DUK_ASSERT((have_acc
&& duk_get_top(ctx
) == 5) ||
1404 (!have_acc
&& duk_get_top(ctx
) == 4));
1406 if (!duk_has_prop_index(ctx
, 2, (duk_uarridx_t
) i
)) {
1411 DUK_ASSERT_TOP(ctx
, 4);
1412 duk_get_prop_index(ctx
, 2, (duk_uarridx_t
) i
);
1414 DUK_ASSERT_TOP(ctx
, 5);
1416 DUK_ASSERT_TOP(ctx
, 5);
1419 duk_get_prop_index(ctx
, 2, (duk_uarridx_t
) i
);
1420 duk_push_u32(ctx
, i
);
1422 DUK_DDD(DUK_DDDPRINT("calling reduce function: func=%!T, prev=%!T, curr=%!T, idx=%!T, obj=%!T",
1423 (duk_tval
*) duk_get_tval(ctx
, -5), (duk_tval
*) duk_get_tval(ctx
, -4),
1424 (duk_tval
*) duk_get_tval(ctx
, -3), (duk_tval
*) duk_get_tval(ctx
, -2),
1425 (duk_tval
*) duk_get_tval(ctx
, -1)));
1427 DUK_DDD(DUK_DDDPRINT("-> result: %!T", (duk_tval
*) duk_get_tval(ctx
, -1)));
1428 duk_replace(ctx
, 4);
1429 DUK_ASSERT_TOP(ctx
, 5);
1437 DUK_ASSERT_TOP(ctx
, 5);
1441 return DUK_RET_TYPE_ERROR
;
1444 #undef DUK__ARRAY_MID_JOIN_LIMIT
1446 #undef DUK__ITER_EVERY
1447 #undef DUK__ITER_SOME
1448 #undef DUK__ITER_FOREACH
1449 #undef DUK__ITER_MAP
1450 #undef DUK__ITER_FILTER