Bug Summary

File:platform/mac/avmshell/../../../core/ArrayClass.cpp
Location:line 598, column 9
Description:Value stored to 'iFirstUndefined' is never read

Annotated Source Code

1/* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
2/* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
3/* ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5 *
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
10 *
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
14 * License.
15 *
16 * The Original Code is [Open Source Virtual Machine.].
17 *
18 * The Initial Developer of the Original Code is
19 * Adobe System Incorporated.
20 * Portions created by the Initial Developer are Copyright (C) 2004-2006
21 * the Initial Developer. All Rights Reserved.
22 *
23 * Contributor(s):
24 * Adobe AS3 Team
25 *
26 * Alternatively, the contents of this file may be used under the terms of
27 * either the GNU General Public License Version 2 or later (the "GPL"), or
28 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
37 *
38 * ***** END LICENSE BLOCK ***** */
39
40
41#include "avmplus.h"
42#include "BuiltinNatives.h"
43
44#ifdef _MAC1
45#ifndef __GNUC__4
46// inline_max_total_size() defaults to 10000.
47// This module includes so many inline functions that we
48// exceed this limit and we start getting compile warnings,
49// so bump up the limit for this file.
50#pragma inline_max_total_size(100000)
51#endif
52#endif
53
54using namespace MMgc;
55
56namespace avmplus
57{
58 // todo while close, the implementations here do not exactly match the
59 // ECMA spec, and probably in ways that the SpiderMonkey test suite won't
60 // catch... for instance, it will go haywire with array indices over
61 // 2^32 because we're not applying the ToInteger algorithm correctly.
62 // Indices have to handled as doubles until the last minute, then...
63 // the full 2^32 range is needed but there is behavior involving
64 // negative numbers too.
65
66 ArrayClass::ArrayClass(VTable* cvtable)
67 : ClassClosure(cvtable)
68 {
69 AvmCore* core = this->core();
70 Toplevel* toplevel = this->toplevel();
71
72 AvmAssert(traits()->getSizeOfInstance() == sizeof(ArrayClass))do { } while (0);
73
74 VTable* ivtable = this->ivtable();
75 ScriptObject* objectPrototype = toplevel->objectClass->prototypePtr();
76 setPrototypePtr(ArrayObject::create(core->GetGC(), ivtable, objectPrototype, 0));
77
78 // According to ECMAscript spec (ECMA-262.pdf)
79 // generic support: concat, join, pop, push, reverse, shift, slice, sort, splice, unshift
80 // NOT generic: toString, toLocaleString
81 // unknown: sortOn (our own extension)
82 }
83
84 static ArrayObject* toArray(Atom instance)
85 {
86 return AvmCore::isObject(instance) ? AvmCore::atomToScriptObject(instance)->toArrayObject() : NULL__null;
87 }
88
89 /**
90 15.4.4.4 Array.prototype.concat ( [ item1 [ , item2 [ , ] ] ] )
91 When the concat method is called with zero or more arguments item1, item2, etc., it returns an array containing
92 the array elements of the object followed by the array elements of each argument in order.
93 The following steps are taken:
94 1. Let A be a new array created as if by the expression new Array().
95 2. Let n be 0.
96 3. Let E be this object.
97 4. If E is not an Array object, go to step 16.
98 5. Let k be 0.
99 6. Call the [[Get]] method of E with argument "length".
100 7. If k equals Result(6) go to step 19.
101 8. Call ToString(k).
102 9. If E has a property named by Result(8), go to step 10,
103 but if E has no property named by Result(8), go to step 13.
104 10. Call ToString(n).
105 11. Call the [[Get]] method of E with argument Result(8).
106 12. Call the [[Put]] method of A with arguments Result(10) and Result(11).
107 13. Increase n by 1.
108 14. Increase k by 1.
109 15. Go to step 7.
110 16. Call ToString(n).
111 17. Call the [[Put]] method of A with arguments Result(16) and E.
112 18. Increase n by 1.
113 19. Get the next argument in the argument list; if there are no more arguments, go to step 22.
114 20. Let E be Result(19).
115 21. Go to step 4.
116 22. Call the [[Put]] method of A with arguments "length" and n.
117 23. Return A.
118 The length property of the concat method is 1.
119 NOTE The concat function is intentionally generic; it does not require that its this value be an Array object. Therefore it can be
120 transferred to other kinds of objects for use as a method. Whether the concat function can be applied successfully to a host
121 object is implementation-dependent.
122 */
123
124 /*static*/ void ArrayClass::array_concat(Toplevel* /*toplevel*/, ArrayObject* a, ArrayObject* b)
125 {
126 if (!a->try_concat(b))
127 {
128 for (uint32_t j = 0, n = b->getLengthProperty(); j < n; ++j)
129 {
130 Atom ba = b->getUintProperty(j);
131 a->push(&ba, 1);
132 }
133 }
134 }
135
136
137 /*static*/ ArrayObject* ArrayClass::generic_concat(Toplevel* toplevel, Atom thisAtom, ArrayObject* args)
138 {
139 ScriptObject* d = AvmCore::isObject(thisAtom) ? AvmCore::atomToScriptObject(thisAtom) : NULL__null;
140 uint32_t len = d ? d->getLengthProperty() : 0;
141
142 uint32_t newLength = len;
143 uint32_t argc = args->getLength();
144 for (uint32_t i = 0; i< argc; i++)
145 {
146 Atom atom = args->getUintProperty(i);
147 ArrayObject* b = toArray(atom);
148 newLength += b ? b->getLengthProperty() : 1;
149 }
150
151 ArrayObject* out = toplevel->arrayClass()->newArray(newLength);
152 ArrayObject* a = toArray(thisAtom);
153 if (a)
154 {
155 array_concat(toplevel, out, a);
156 }
157
158 for (uint32_t i = 0; i < argc; i++)
159 {
160 Atom atom = args->getUintProperty(i);
161 ArrayObject* b = toArray(atom);
162 if (b)
163 {
164 array_concat(toplevel, out, b);
165 }
166 else
167 {
168 out->push(&atom, 1);
169 }
170 }
171
172 return out;
173 }
174
175 /**
176 * Array.prototype.pop()
177 * TRANSFERABLE: Needs to support generic objects as well as Array objects
178 */
179 /*static*/ Atom ArrayClass::generic_pop(Toplevel* /*toplevel*/, Atom thisAtom)
180 {
181 ArrayObject* a = toArray(thisAtom);
182
183 if (a)
184 return a->pop();
185
186 if (!AvmCore::isObject(thisAtom))
187 return undefinedAtom;
188
189 // Different than Rhino (because of delete) but matches 262.pdf
190 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
191 uint32_t len = d->getLengthProperty();
192 if (!len)
193 {
194 d->setLengthProperty(0);
195 return undefinedAtom;
196 }
197 else
198 {
199 Atom outAtom = d->getUintProperty (len-1);
200 d->delUintProperty (len - 1);
201 d->setLengthProperty(len - 1);
202 return outAtom;
203 }
204 }
205
206 /**
207 * Array.prototype.reverse()
208 * TRANSFERABLE: Needs to support generic objects as well as Array objects
209 */
210 /*static*/ Atom ArrayClass::generic_reverse(Toplevel* /*toplevel*/, Atom thisAtom)
211 {
212 ArrayObject* a = toArray(thisAtom);
213 if (a && a->try_reverse())
214 {
215 return thisAtom;
216 }
217
218 // generic object version
219 if (!AvmCore::isObject(thisAtom))
220 return thisAtom;
221
222 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
223 uint32_t j = d->getLengthProperty();
224
225 uint32_t i = 0;
226 if (j)
227 j--;
228
229 while (i < j) {
230 Atom frontAtom = d->getUintProperty(i);
231 Atom backAtom = d->getUintProperty(j);
232
233 d->setUintProperty(i++, backAtom);
234 d->setUintProperty(j--, frontAtom);
235 }
236
237 return thisAtom;
238 }
239
240 /**
241 * Array.prototype.shift()
242 * TRANSFERABLE: Needs to support generic objects as well as Array objects
243 */
244 /*static*/ Atom ArrayClass::generic_shift(Toplevel* /*toplevel*/, Atom thisAtom)
245 {
246 ArrayObject* a = toArray(thisAtom);
247
248 Atom result;
249 if (a && a->try_shift(result))
250 {
251 return result;
252 }
253
254 if (!AvmCore::isObject(thisAtom))
255 return undefinedAtom;
256
257 Atom outAtom;
258 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
259 uint32_t len = d->getLengthProperty();
260
261 if (len == 0)
262 {
263 // set len to 0 (ecmascript spec)
264 d->setLengthProperty(0);
265 outAtom = undefinedAtom;
266 }
267 else
268 {
269 // Get the 0th element to return
270 outAtom = d->getUintProperty(0);
271
272 // Move all of the elements down
273 for (uint32_t i=0; i<len-1; i++) {
274 d->setUintProperty(i, d->getUintProperty(i+1));
275 }
276
277 d->delUintProperty (len - 1);
278 d->setLengthProperty(len - 1);
279 }
280
281 return outAtom;
282 }
283
284 /**
285 * Array.prototype.slice()
286 * TRANSFERABLE: Needs to support generic objects as well as Array objects
287 */
288 /*static*/ ArrayObject* ArrayClass::generic_slice(Toplevel* toplevel, Atom thisAtom, double A, double B)
289 {
290 if (!AvmCore::isObject(thisAtom))
291 return 0;
292
293 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
294 uint32_t len = d->getLengthProperty();
295
296 // if a param is passed then the first one is A
297 // if no params are passed then A = 0
298 uint32_t a = NativeObjectHelpers::ClampIndex(A, len);
299 uint32_t b = NativeObjectHelpers::ClampIndex(B, len);
300 if (b < a)
301 b = a;
302
303 ArrayObject *out = toplevel->arrayClass()->newArray(b-a);
304
305 uint32_t outIndex=0;
306 for (uint32_t i=a; i<b; i++) {
307 out->setUintProperty (outIndex++, d->getUintProperty (i));
308 }
309
310 return out;
311 }
312
313 static inline boolbool defined(Atom atom) { return (atom != undefinedAtom); }
314
315 typedef HeapList<AtomList> HeapAtomList;
316
317 /**
318 * ArraySort implements actionscript Array.sort().
319 * It's also the base class SortWithParameters, which handles all
320 * other permutations of Array.
321 *
322 * NOTE: Instances of ArraySort must be stack-allocated, as it uses
323 * VMPI_alloca for a temporary data structure.
324 */
325 class ArraySort
326 {
327 public:
328 /*************************************************************
329 * Forward declarations required by public methods
330 *************************************************************/
331
332 /** Options from script */
333 enum {
334 kCaseInsensitive = 1
335 ,kDescending = 2
336 ,kUniqueSort = 4
337 ,kReturnIndexedArray = 8
338 ,kNumeric = 16
339 };
340
341 /**
342 * Array.sortOn() will pass an array of field names, which is converted to a stack-
343 * allocated array of FieldName structures (hence no write barriers here).
344 */
345 struct FieldName
346 {
347 String* name;
348 int options;
349 };
350
351 typedef int (*CompareFuncPtr) (const ArraySort *s, uint32_t i, uint32_t j);
352
353 static int StringCompareFunc(const ArraySort *s, uint32_t j, uint32_t k) { return s->StringCompare(j, k); }
354 static int CaseInsensitiveStringCompareFunc(const ArraySort *s, uint32_t j, uint32_t k) { return s->CaseInsensitiveStringCompare(j, k); }
355 static int ScriptCompareFuncCompatible(const ArraySort *s, uint32_t j, uint32_t k) { return s->ScriptCompareCompatible(j, k); }
356 static int ScriptCompareFuncCorrect(const ArraySort *s, uint32_t j, uint32_t k) { return s->ScriptCompareCorrect(j, k); }
357 static int NumericCompareFuncCompatible(const ArraySort *s, uint32_t j, uint32_t k) { return s->NumericCompareCompatible(j, k); }
358 static int NumericCompareFuncCorrect(const ArraySort *s, uint32_t j, uint32_t k) { return s->NumericCompareCorrect(j, k); }
359 static int DescendingCompareFunc(const ArraySort *s, uint32_t j, uint32_t k) { return s->altCmpFunc(s, k, j); }
360 static int FieldCompareFunc(const ArraySort *s, uint32_t j, uint32_t k) { return s->FieldCompare(j, k); }
361
362 public:
363 /*************************************************************
364 * Public Functions
365 *************************************************************/
366
367 ArraySort(Atom &result, ArrayClass *f, ScriptObject *d, int options, CompareFuncPtr cmpFunc,
368 CompareFuncPtr altCmpFunc, Atom cmpActionScript, uint32_t numFields = 0, FieldName *fields = NULL__null);
369
370 ~ArraySort();
371
372 // do the sort
373 Atom sort();
374
375 private:
376 /*************************************************************
377 * Private Functions
378 *************************************************************/
379
380 // non-recursive quicksort implementation
381 void qsort(uint32_t lo, uint32_t hi);
382
383 // qsort() is abstracted from the array by swap() and compare()
384 // compare(), in turn, is abstracted from the array via get()
385 //
386 // cmpFunc is conditional, for instance :
387 // cmpFunc = DefaultCompareFunc; // Array.sort()
388 // cmpFunc = ScriptCompareFunc; // Array.sort(compareFunction)
389 int compare(uint32_t lhs, uint32_t rhs) const { return cmpFunc(this, lhs, rhs); }
390 Atom get(uint32_t i) const { return atoms->list.get(index[i]); }
391 void swap(uint32_t j, uint32_t k)
392 {
393 uint32_t temp = index[j];
394 index[j] = index[k];
395 index[k] = temp;
396 }
397
398 inline int StringCompare(uint32_t j, uint32_t k) const;
399 inline int CaseInsensitiveStringCompare(uint32_t j, uint32_t k) const;
400 inline int ScriptCompareCompatible(uint32_t j, uint32_t k) const;
401 inline int ScriptCompareCorrect(uint32_t j, uint32_t k) const;
402 inline int NumericCompareCompatible(uint32_t j, uint32_t k) const;
403 inline int NumericCompareCorrect(uint32_t j, uint32_t k) const;
404 inline int FieldCompare(uint32_t j, uint32_t k) const;
405
406 /**
407 * null check + pointer cast. only used in contexts where we know we
408 * have a ScriptObject* already (verified, etc)
409 */
410 ScriptObject* toFieldObject(Atom atom) const;
411
412 private:
413 /*************************************************************
414 * Private Member Variables
415 *************************************************************/
416
417 ScriptObject *d;
418 AvmCore* core;
419 Toplevel* toplevel;
420 int options;
421
422 CompareFuncPtr cmpFunc;
423 CompareFuncPtr altCmpFunc;
424 Atom cmpActionScript;
425
426
427 GC::AllocaAutoPtr index_autoptr;
428 uint32_t* index;
429 HeapAtomList* atoms;
430
431 uint32_t numFields;
432 FieldName *fields;
433 HeapAtomList* fieldatoms;
434 };
435
436 ArraySort::ArraySort(
437 Atom &result,
438 ArrayClass *f,
439 ScriptObject *d,
440 int options,
441 CompareFuncPtr cmpFunc,
442 CompareFuncPtr altCmpFunc,
443 Atom cmpActionScript,
444 uint32_t numFields,
445 FieldName *fields
446 ) :
447 d(d),
448 core(f->core()),
449 toplevel(f->toplevel()),
450 options(options),
451 cmpFunc(cmpFunc),
452 altCmpFunc(altCmpFunc),
453 cmpActionScript(cmpActionScript),
454 index_autoptr(),
455 index(NULL__null),
456 atoms(NULL__null),
457 numFields(numFields),
458 fields(fields),
459 fieldatoms(NULL__null)
460 {
461 uint32_t len = d->getLengthProperty();
462 uint32_t iFirstUndefined = len;
463 uint32_t iFirstAbsent = len;
464
465 // new class[n] compiles into code which tries to allocate n * sizeof(class).
466 // unfortunately, the generated assembly does not protect against this product overflowing int.
467 // So I limit the length -- for larger values, I expect new will fail anyways.
468 if ((len > 0) && (len < (0x10000000)))
469 {
470 index = (uint32_t*)VMPI_alloca(core, index_autoptr, GCHeap::CheckForCallocSizeOverflow(len, sizeof(uint32_t)))(GCHeap::CheckForCallocSizeOverflow(len, sizeof(uint32_t)) >
4000 ? core->gc->allocaPush(GCHeap::CheckForCallocSizeOverflow
(len, sizeof(uint32_t)), index_autoptr) : __builtin_alloca(GCHeap
::CheckForCallocSizeOverflow(len, sizeof(uint32_t))))
;
471 atoms = new (core->GetGC()) HeapAtomList(core->GetGC(), len);
472 }
473
474 if (!index || !atoms)
475 {
476 // return the unsorted array.
477
478 // todo : grandma : Should I be raising an exception? Sort too big?
479 // could also fallback to an unindexed sort, but with that many elements, it won't finish for hours
480 result = d->atom();
481 return;
482 }
483
484 uint32_t i, j;
485 uint32_t newlen = len;
486
487 // One field value - pre-get our field values so we can just do a regular sort
488 if (cmpFunc == ArraySort::FieldCompareFunc && numFields == 1)
489 {
490 fieldatoms = new (core->GetGC()) HeapAtomList(core->GetGC(), len);
491
492 // note, loop needs to go until i = -1, but i is unsigned. 0xffffffff is a valid index, so check (i+1) != 0.
493 for (i = (len - 1), j = len; (i+1) != 0; i--)
494 {
495 index[i] = i;
496 Atom a = d->getUintProperty(i);
497 fieldatoms->list.set(i, a);
498
499 if (AvmCore::isObject (a))
500 {
501 ScriptObject* obj = AvmCore::atomToScriptObject (a);
502
503 Stringp name = fields[0].name;
504
505 // NOTE we want to sort the public members of the caller's version
506 Multiname mname(core->findPublicNamespace(), name);
507
508 // An undefined prop just becomes undefined in our sort
509 Atom x = toplevel->getproperty(obj->atom(), &mname, obj->vtable);
510 atoms->list.set(i, x);
511 }
512 else
513 {
514 j--;
515
516 uint32_t temp = index[i];
517 index[i] = index[j];
518
519 if (!d->hasUintProperty(i)) {
520 newlen--;
521 index[j] = index[newlen];
522 index[newlen] = temp;
523 } else {
524 index[j] = temp;
525 }
526 }
527 }
528
529 int opt = fields[0].options;
530
531 if (opt & ArraySort::kNumeric) {
532 this->cmpFunc = core->currentBugCompatibility()->bugzilla524122 ?
533 ArraySort::NumericCompareFuncCorrect :
534 ArraySort::NumericCompareFuncCompatible;
535 } else if (opt & ArraySort::kCaseInsensitive) {
536 this->cmpFunc = ArraySort::CaseInsensitiveStringCompareFunc;
537 } else {
538 this->cmpFunc = ArraySort::StringCompareFunc;
539 }
540
541 if (opt & ArraySort::kDescending) {
542 this->altCmpFunc = this->cmpFunc;
543 this->cmpFunc = ArraySort::DescendingCompareFunc;
544 }
545 }
546 else
547 {
548 boolbool isNumericCompare = (cmpFunc == ArraySort::NumericCompareFuncCompatible) ||
549 (altCmpFunc == ArraySort::NumericCompareFuncCompatible) ||
550 (cmpFunc == ArraySort::NumericCompareFuncCorrect) ||
551 (altCmpFunc == ArraySort::NumericCompareFuncCorrect);
552 // note, loop needs to go until i = -1, but i is unsigned. 0xffffffff is a valid index, so check (i+1) != 0.
553 for (i = (len - 1), j = len; (i+1) != 0; i--)
554 {
555 index[i] = i;
556 atoms->list.set(i, d->getUintProperty(i));
557
558 // We want to throw if this is an Array.NUMERIC sort and any items are not numbers,
559 // and not strings that can be converted into numbers
560 if(isNumericCompare && !core->isNumber(atoms->list.get(i)))
561 {
562 double val = AvmCore::number(atoms->list.get(i));
563 if(MathUtils::isNaN(val))
564 // throw exception (not a Number)
565 toplevel->throwTypeError(kCheckTypeFailedError, core->atomToErrorString(atoms->list.get(i)), core->toErrorString(core->traits.number_itraits));
566
567 }
568
569 // getAtomProperty() returns undefined when that's the value of the property.
570 // It also returns undefined when the object does not have the property.
571 //
572 // SortCompare() from ECMA 262 distinguishes these two cases. The end
573 // result is undefined comes after everything else, and missing properties
574 // come after that.
575 //
576 // To simplify our compare, partitition the array into { defined | undefined | missing }
577 // Note that every missing element shrinks the length -- we'll set this new
578 // length at the end of this routine when we are done.
579
580 if (!defined(atoms->list.get(i))) {
581 j--;
582
583 uint32_t temp = index[i];
584 index[i] = index[j];
585
586 if (!d->hasUintProperty(i)) {
587 newlen--;
588 index[j] = index[newlen];
589 index[newlen] = temp;
590 } else {
591 index[j] = temp;
592 }
593 }
594 }
595 }
596
597 iFirstAbsent = newlen;
598 iFirstUndefined = j;
Value stored to 'iFirstUndefined' is never read
599
600 // The portion of the array containing defined values is now [0, iFirstUndefined).
601 // The portion of the array containing values undefined is now [iFirstUndefined, iFirstAbsent).
602 // The portion of the array containing absent values is now [iFirstAbsent, len).
603
604 // now sort the remaining defined() elements
605 qsort(0, j-1);
606
607 if (options & kUniqueSort)
608 {
609 // todo : kUniqueSort could throw an exception.
610 // todo : kUniqueSort could abort the sort once equal members are found
611 for (uint32_t i = 0; i < (len - 1); i++)
612 {
613 if (compare(i, (i+1)) == 0)
614 {
615 result = core->uintToAtom(0);
616 return;
617 }
618 }
619 }
620
621 if (options & kReturnIndexedArray)
622 {
623 // return the index array without modifying the original array
624 ArrayObject *obj = toplevel->arrayClass()->newArray(len);
625
626 for (uint32_t i = 0; i < len; i++)
627 {
628 obj->setUintProperty(i, core->uintToAtom(index[i]));
629 }
630
631 result = obj->atom();
632 }
633 else
634 {
635 // If we need to use our fieldatoms as results, temporarily swap them with
636 // our atoms array so the below code works on the right data. Fieldatoms contain
637 // our original objects while atoms contain our objects[field] values for faster
638 // sorting.
639 HeapAtomList* temp = atoms;
640 if (fieldatoms)
641 {
642 atoms = fieldatoms;
643 }
644
645 for (i = 0; i < iFirstAbsent; i++) {
646 d->setUintProperty(i, get(i));
647 }
648
649 for (i = iFirstAbsent; i < len; i++) {
650 d->delUintProperty(i);
651 }
652
653 //a->setLength(len); ES3: don't shrink array on sort. Seems silly
654 result = d->atom();
655 atoms = temp;
656
657 }
658
659 return;
660 }
661
662 ArraySort::~ArraySort()
663 {
664 delete atoms;
665 delete fieldatoms;
666 fields = NULL__null;
667 }
668
669 /*
670 * QuickSort a portion of the ArrayObject.
671 */
672 void ArraySort::qsort(uint32_t lo, uint32_t hi)
673 {
674 // This is an iterative implementation of the recursive quick sort.
675 // Recursive implementations are basically storing nested (lo,hi) pairs
676 // in the stack frame, so we can avoid the recursion by storing them
677 // in an array.
678 //
679 // Once partitioned, we sub-partition the smaller half first. This means
680 // the greatest stack depth happens with equal partitions, all the way down,
681 // which would be 1 + log2(size), which could never exceed 33.
682
683 uint32_t size;
684 struct StackFrame { uint32_t lo, hi; };
685 StackFrame stk[33];
686 int stkptr = 0;
687
688 // leave without doing anything if the array is empty (lo > hi) or only one element (lo == hi)
689 if (lo >= hi)
690 return;
691
692 // code below branches to this label instead of recursively calling qsort()
693 recurse:
694
695 size = (hi - lo) + 1; // number of elements in the partition
696
697 if (size < 4) {
698
699 // It is standard to use another sort for smaller partitions,
700 // for instance c library source uses insertion sort for 8 or less.
701 //
702 // However, as our swap() is essentially free, the relative cost of
703 // compare() is high, and with profiling, I found quicksort()-ing
704 // down to four had better performance.
705 //
706 // Although verbose, handling the remaining cases explicitly is faster,
707 // so I do so here.
708
709 if (size == 3) {
710 if (compare(lo, lo + 1) > 0) {
711 swap(lo, lo + 1);
712 if (compare(lo + 1, lo + 2) > 0) {
713 swap(lo + 1, lo + 2);
714 if (compare(lo, lo + 1) > 0) {
715 swap(lo, lo + 1);
716 }
717 }
718 } else {
719 if (compare(lo + 1, lo + 2) > 0) {
720 swap(lo + 1, lo + 2);
721 if (compare(lo, lo + 1) > 0) {
722 swap(lo, lo + 1);
723 }
724 }
725 }
726 } else if (size == 2) {
727 if (compare(lo, lo + 1) > 0)
728 swap(lo, lo + 1);
729 } else {
730 // size is one, zero or negative, so there isn't any sorting to be done
731 }
732 } else {
733 // qsort()-ing a near or already sorted list goes much better if
734 // you use the midpoint as the pivot, but the algorithm is simpler
735 // if the pivot is at the start of the list, so move the middle
736 // element to the front!
737 uint32_t pivot = lo + (size / 2);
738 swap(pivot, lo);
739
740
741 uint32_t left = lo;
742 uint32_t right = hi + 1;
743
744 for (;;) {
745 // Move the left right until it's at an element greater than the pivot.
746 // Move the right left until it's at an element less than the pivot.
747 // If left and right cross, we can terminate, otherwise swap and continue.
748 //
749 // As each pass of the outer loop increments left at least once,
750 // and decrements right at least once, this loop has to terminate.
751
752 do {
753 left++;
754 } while ((left <= hi) && (compare(left, lo) <= 0));
755
756 do {
757 right--;
758 } while ((right > lo) && (compare(right, lo) >= 0));
759
760 if (right < left)
761 break;
762
763 swap(left, right);
764 }
765
766 // move the pivot after the lower partition
767 swap(lo, right);
768
769 // The array is now in three partions:
770 // 1. left partition : i in [lo, right), elements less than or equal to pivot
771 // 2. center partition : i in [right, left], elements equal to pivot
772 // 3. right partition : i in (left, hi], elements greater than pivot
773 // NOTE : [ means the range includes the lower bounds, ( means it excludes it, with the same for ] and ).
774
775 // Many quick sorts recurse into the left partition, and then the right.
776 // The worst case of this can lead to a stack depth of size -- for instance,
777 // the left is empty, the center is just the pivot, and the right is everything else.
778 //
779 // If you recurse into the smaller partition first, then the worst case is an
780 // equal partitioning, which leads to a depth of log2(size).
781 if ((right - 1 - lo) >= (hi - left))
782 {
783 if ((lo + 1) < right)
784 {
785 stk[stkptr].lo = lo;
786 stk[stkptr].hi = right - 1;
787 ++stkptr;
788 }
789
790 if (left < hi)
791 {
792 lo = left;
793 goto recurse;
794 }
795 }
796 else
797 {
798 if (left < hi)
799 {
800 stk[stkptr].lo = left;
801 stk[stkptr].hi = hi;
802 ++stkptr;
803 }
804
805 if ((lo + 1) < right)
806 {
807 hi = right - 1;
808 goto recurse; /* do small recursion */
809 }
810 }
811 }
812
813 // we reached the bottom of the well, pop the nested stack frame
814 if (--stkptr >= 0)
815 {
816 lo = stk[stkptr].lo;
817 hi = stk[stkptr].hi;
818 goto recurse;
819 }
820
821 // we've returned to the top, so we are done!
822 return;
823 }
824
825 /*
826 * compare(j, k) as string's
827 */
828 int ArraySort::StringCompare(uint32_t j, uint32_t k) const
829 {
830 Atom x = get(j);
831 Atom y = get(k);
832
833 Stringp str_lhs = core->string(x);
834 Stringp str_rhs = core->string(y);
835
836 return str_rhs->Compare(*str_lhs);
837 }
838
839 /*
840 * compare(j, k) as case insensitive string's
841 */
842 int ArraySort::CaseInsensitiveStringCompare(uint32_t j, uint32_t k) const
843 {
844 Atom x = get(j);
845 Atom y = get(k);
846
847 Stringp str_lhs = core->string(x)->toLowerCase();
848 Stringp str_rhs = core->string(y)->toLowerCase();
849
850 return str_rhs->Compare(*str_lhs);
851 }
852
853 /*
854 * compare(j, k) using an actionscript function
855 */
856 int ArraySort::ScriptCompareCompatible(uint32_t j, uint32_t k) const
857 {
858 ScriptObject *o = (ScriptObject*) AvmCore::atomToScriptObject(cmpActionScript);
859
860 // Coercing result to integer may result in inccorect change of sign.
861 // See bug 532454.
862 Atom args[3] = { d->atom(), get(j), get(k) };
863 double result = AvmCore::toInteger(o->call(2, args));
864 return (result > 0 ? 1 : (result < 0 ? -1 : 0));
865 }
866
867 /*
868 * compare(j, k) using an actionscript function
869 */
870 int ArraySort::ScriptCompareCorrect(uint32_t j, uint32_t k) const
871 {
872 // todo must figure out the kosher way to invoke
873 // callbacks like the sort comparator.
874
875 // todo what is thisAtom supposed to be for the
876 // comparator? Passing in the array for now.
877
878 ScriptObject *o = (ScriptObject*) AvmCore::atomToScriptObject(cmpActionScript);
879
880 // cn: don't use AvmCore::integer on result of call. The returned
881 // value could be bigger than 2^32 and toInt32 will return the
882 // ((value % 2^32) - 2^31), which could change the intended sign of the number.
883
884 Atom args[3] = { d->atom(), get(j), get(k) };
885 double result = AvmCore::number(o->call(2, args));
886 return (result > 0 ? 1 : (result < 0 ? -1 : 0));
887 }
888
889 /*
890 * compare(j, k) as numbers
891 */
892 int ArraySort::NumericCompareCompatible(uint32_t j, uint32_t k) const
893 {
894 Atom atmj = get(j);
895 Atom atmk = get(k);
896 // Integer checks makes an int array sort about 3x faster.
897 // A double array sort is 5% slower because of this overhead
898 if (atomIsBothIntptr(atmj, atmk))
899 {
900 // This is incorrect, see bugzilla 524122. NumericCompareCorrect, below, fixes the bug.
901 return ((int)atmj - (int)atmk);
902 }
903
904 double x = AvmCore::number(atmj);
905 double y = AvmCore::number(atmk);
906 double diff = x - y;
907
908 if (diff == diff) { // same as !isNaN
909 return (diff < 0) ? -1 : ((diff > 0) ? 1 : 0);
910 } else if (!MathUtils::isNaN(y)) {
911 return 1;
912 } else if (!MathUtils::isNaN(x)) {
913 return -1;
914 } else {
915 return 0;
916 }
917 }
918
919 /*
920 * compare(j, k) as numbers
921 */
922 int ArraySort::NumericCompareCorrect(uint32_t j, uint32_t k) const
923 {
924 Atom atmj = get(j);
925 Atom atmk = get(k);
926 // Integer checks makes an int array sort about 3x faster.
927 // A double array sort is 5% slower because of this overhead
928 if (atomIsBothIntptr(atmj, atmk))
929 {
930 // Must convert to native values. Just subtracting the atoms may lead to
931 // overflows which result in the incorrect sign being returned. See
932 // NumericCompareCompatible, above.
933 intptr_t tmp = atomGetIntptr(atmj) - atomGetIntptr(atmk);
934#ifdef AVMPLUS_64BIT
935 // On 64-bit systems atoms carry more than 32 significant bits of integer
936 // data, so we need to be careful.
937 if (tmp < 0) return -1;
938 if (tmp == 0) return 0;
939 return 1;
940#else
941 return int(tmp);
942#endif
943 }
944
945 double x = AvmCore::number(atmj);
946 double y = AvmCore::number(atmk);
947 double diff = x - y;
948
949 if (diff == diff) { // same as !isNaN
950 return (diff < 0) ? -1 : ((diff > 0) ? 1 : 0);
951 } else if (!MathUtils::isNaN(y)) {
952 return 1;
953 } else if (!MathUtils::isNaN(x)) {
954 return -1;
955 } else {
956 return 0;
957 }
958 }
959
960 ScriptObject* ArraySort::toFieldObject(Atom atom) const
961 {
962 if (atomKind(atom)((avmplus::Atom)((uintptr_t(atom) & 7))) != kObjectType)
963 {
964 #if 0
965 /* cn: ifdefed out, not sure what the intent was here, but calling code in FieldCompare
966 * does null checking, apparently expecting this function to return null when the item
967 * isn't an object (and thus can't have custom properties added to it). */
968 // TypeError in ECMA
969 toplevel->throwTypeError(
970 (atom == undefinedAtom) ? kConvertUndefinedToObjectError :
971 kConvertNullToObjectError);
972 #endif
973 return NULL__null;
974 }
975 return AvmCore::atomToScriptObject(atom);
976 }
977
978 /*
979 * FieldCompare is for Array.sortOn()
980 */
981 inline int ArraySort::FieldCompare(uint32_t lhs, uint32_t rhs) const
982 {
983 Atom j, k;
984 int opt = options;
985 int result = 0;
986
987 j = get(lhs);
988 k = get(rhs);
989
990 ScriptObject* obj_j = toFieldObject(j);
991 ScriptObject* obj_k = toFieldObject(k);
992
993 if (!(obj_j && obj_k))
994 {
995 if (obj_k) {
996 result = 1;
997 } else if (obj_j) {
998 result = -1;
999 } else {
1000 result = 0;
1001 }
1002 return (opt & kDescending) ? -result : result;
1003 }
1004
1005 for (uint32_t i = 0; i < numFields; i++)
1006 {
1007 Stringp name = fields[i].name;
1008 // NOTE compare the names of the caller's version
1009 Multiname mname(core->findPublicNamespace(), name);
1010
1011 opt = fields[i].options; // override the group defaults with the current field
1012
1013 Atom x = toplevel->getproperty(obj_j->atom(), &mname, obj_j->vtable);
1014 Atom y = toplevel->getproperty(obj_k->atom(), &mname, obj_k->vtable);
1015
1016 boolbool def_x = defined(x);
1017 boolbool def_y = defined(y);
1018
1019 if (!(def_x && def_y))
1020 {
1021 // ECMA 262 : Section 15.4.4.11 lists the rules.
1022 // There is a difference between the object has a property
1023 // with value undefined, and it does not have the property,
1024 // for which getAtomProperty() returns undefined.
1025
1026 // def_x implies has_x
1027 // def_y implies has_y
1028
1029 if (def_y) {
1030 result = 1;
1031 } else if (def_x) {
1032 result = -1;
1033 } else {
1034 boolbool has_x = (toplevel->getBinding(obj_j->vtable->traits, &mname) != BIND_NONE) || obj_j->hasStringProperty(name);
1035 boolbool has_y = (toplevel->getBinding(obj_k->vtable->traits, &mname) != BIND_NONE) || obj_k->hasStringProperty(name);
1036
1037 if (!has_x && has_y) {
1038 result = 1;
1039 } else if (has_x && !has_y) {
1040 result = -1;
1041 } else {
1042 result = 0;
1043 }
1044 }
1045 } else if (opt & kNumeric) {
1046 double lhs = AvmCore::number(x);
1047 double rhs = AvmCore::number(y);
1048 double diff = lhs - rhs;
1049
1050 if (diff == diff) { // same as !isNaN
1051 result = (diff < 0) ? -1 : ((diff > 0) ? 1 : 0);
1052 } else if (!MathUtils::isNaN(rhs)) {
1053 result = 1;
1054 } else if (!MathUtils::isNaN(lhs)) {
1055 result = -1;
1056 } else {
1057 result = 0;
1058 }
1059 }
1060 else
1061 {
1062 Stringp str_lhs = core->string(x);
1063 Stringp str_rhs = core->string(y);
1064
1065 if (opt & kCaseInsensitive)
1066 {
1067 str_lhs = str_lhs->toLowerCase();
1068 str_rhs = str_rhs->toLowerCase();
1069 }
1070
1071 result = str_rhs->Compare(*str_lhs);
1072 }
1073
1074 if (result != 0)
1075 break;
1076 }
1077
1078 if (opt & kDescending)
1079 return -result;
1080 else
1081 return result;
1082 }
1083
1084 /**
1085 * Array.prototype.sort()
1086 * TRANSFERABLE: Needs to support generic objects as well as Array objects
1087 */
1088
1089 // thisAtom is object to process
1090 // 1st arg of args is a function or a number
1091 // 2nd arg of args is a number
1092 //
1093 // valid AS3 syntax:
1094 // sort()
1095 // sort(function object)
1096 // sort(number flags)
1097 // sort(function object, number flags)
1098
1099 // This takes a args object because there is no way to distinguigh between sort()
1100 // and sort(undefined, 0) if we take default parameters.
1101 /*static*/ Atom ArrayClass::generic_sort(Toplevel* toplevel, Atom thisAtom, ArrayObject *args)
1102 {
1103 AvmCore* core = toplevel->core();
1104 if (!AvmCore::isObject(thisAtom))
1105 return undefinedAtom;
1106
1107 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1108 ArraySort::CompareFuncPtr compare = NULL__null;
1109 ArraySort::CompareFuncPtr altCompare = NULL__null;
1110
1111 Atom cmp = undefinedAtom;
1112 int opt = 0;
1113 if (args->getLength() >= 1)
1114 {
1115 // function ptr
1116 Atom arg0 = args->getUintProperty(0);
1117 if (AvmCore::isObject (arg0))
1118 {
1119 // make sure the sort function is callable
1120 cmp = arg0;
1121 toplevel->coerce(cmp, core->traits.function_itraits);
1122 compare = core->currentBugCompatibility()->bugzilla532454 ?
1123 ArraySort::ScriptCompareFuncCorrect :
1124 ArraySort::ScriptCompareFuncCompatible;
1125 if (args->getLength() >= 2)
1126 {
1127 Atom arg1 = args->getUintProperty(1);
1128 if (core->isNumber(arg1))
1129 {
1130 opt = AvmCore::integer(arg1);
1131 }
1132 else
1133 {
1134 // throw exception (not a Number)
1135 toplevel->throwTypeError(kCheckTypeFailedError, core->atomToErrorString(arg1), core->toErrorString(core->traits.number_itraits));
1136 }
1137 }
1138 }
1139 else if (core->isNumber(arg0))
1140 {
1141 opt = AvmCore::integer(arg0);
1142 }
1143 else
1144 {
1145 // throw exception (not a function)
1146 toplevel->throwTypeError(kCheckTypeFailedError, core->atomToErrorString(arg0), core->toErrorString(core->traits.function_itraits));
1147 }
1148 }
1149
1150 if (cmp == undefinedAtom)
1151 {
1152 if (opt & ArraySort::kNumeric) {
1153 compare = core->currentBugCompatibility()->bugzilla524122 ?
1154 ArraySort::NumericCompareFuncCorrect :
1155 ArraySort::NumericCompareFuncCompatible;
1156 } else if (opt & ArraySort::kCaseInsensitive) {
1157 compare = ArraySort::CaseInsensitiveStringCompareFunc;
1158 } else {
1159 compare = ArraySort::StringCompareFunc;
1160 }
1161 }
1162
1163 if (opt & ArraySort::kDescending) {
1164 altCompare = compare;
1165 compare = ArraySort::DescendingCompareFunc;
1166 }
1167
1168 Atom result;
1169 ArraySort sort(result, toplevel->arrayClass(), d, opt, compare, altCompare, cmp);
1170
1171 return result;
1172 }
1173
1174
1175 /**
1176 * Array.prototype.sortOn()
1177 * TRANSFERABLE: Needs to support generic objects as well as Array objects
1178 */
1179 /*static*/ Atom ArrayClass::generic_sortOn(Toplevel* toplevel, Atom thisAtom, Atom namesAtom, Atom optionsAtom)
1180 {
1181 AvmCore* core = toplevel->core();
1182 if (!AvmCore::isObject(thisAtom))
1183 return undefinedAtom;
1184 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1185
1186 // Possible combinations:
1187 // Array.sortOn(String)
1188 // Array.sortOn(String, options)
1189 // Array.sortOn(Array of String)
1190 // Array.sortOn(Array of String, options)
1191 // Array.sortOn(Array of String, Array of options)
1192
1193 // What about options which must be global, such as kReturnIndexedArray?
1194 // Perhaps it is the union of all field's options?
1195
1196 ArraySort::FieldName *fn = NULL__null;
1197 GC::AllocaAutoPtr fn_autoptr;
1198 uint32_t nFields = 0;
1199 int options = 0;
1200
1201 if (toplevel->builtinClasses()->get_StringClass()->isType(namesAtom))
1202 {
1203 nFields = 1;
1204
1205 options = AvmCore::integer(optionsAtom);
1206
1207 fn = (ArraySort::FieldName*) VMPI_alloca(core, fn_autoptr, GCHeap::CheckForCallocSizeOverflow(nFields, sizeof(ArraySort::FieldName)))(GCHeap::CheckForCallocSizeOverflow(nFields, sizeof(ArraySort
::FieldName)) > 4000 ? core->gc->allocaPush(GCHeap::
CheckForCallocSizeOverflow(nFields, sizeof(ArraySort::FieldName
)), fn_autoptr) : __builtin_alloca(GCHeap::CheckForCallocSizeOverflow
(nFields, sizeof(ArraySort::FieldName))))
;
1208 fn[0].name = core->internString(namesAtom);
1209 fn[0].options = options;
1210 }
1211 else if (toplevel->builtinClasses()->get_ArrayClass()->isType(namesAtom))
1212 {
1213 ArrayObject *obj = (ArrayObject *)AvmCore::atomToScriptObject(namesAtom);
1214
1215 nFields = obj->getLength();
1216 fn = (ArraySort::FieldName*) VMPI_alloca(core, fn_autoptr, GCHeap::CheckForCallocSizeOverflow(nFields, sizeof(ArraySort::FieldName)))(GCHeap::CheckForCallocSizeOverflow(nFields, sizeof(ArraySort
::FieldName)) > 4000 ? core->gc->allocaPush(GCHeap::
CheckForCallocSizeOverflow(nFields, sizeof(ArraySort::FieldName
)), fn_autoptr) : __builtin_alloca(GCHeap::CheckForCallocSizeOverflow
(nFields, sizeof(ArraySort::FieldName))))
;
1217
1218 for (uint32_t i = 0; i < nFields; i++)
1219 {
1220 fn[i].name = core->intern(obj->getUintProperty(i));
1221 fn[i].options = 0;
1222 }
1223
1224 if (toplevel->builtinClasses()->get_ArrayClass()->isType(optionsAtom))
1225 {
1226 ArrayObject *obj = (ArrayObject *)AvmCore::atomToScriptObject(optionsAtom);
1227 uint32_t nOptions = obj->getLength();
1228 if (nOptions == nFields)
1229 {
1230 // The first options are used for uniqueSort and returnIndexedArray option
1231 options = AvmCore::integer(obj->getUintProperty(0));
1232 for (uint32_t i = 0; i < nFields; i++)
1233 {
1234 fn[i].options = AvmCore::integer(obj->getUintProperty (i));
1235 }
1236 }
1237 }
1238 else
1239 {
1240 options = AvmCore::integer(optionsAtom);
1241 for (uint32_t i = 0; i < nFields; i++)
1242 {
1243 fn[i].options = options;
1244 }
1245 }
1246 }
1247
1248 Atom result;
1249 ArraySort sort(result, toplevel->arrayClass(), d, options, ArraySort::FieldCompareFunc, NULL__null, undefinedAtom, nFields, fn);
1250 return result;
1251 }
1252
1253 /**
1254 * Array.prototype.splice()
1255 * TRANSFERABLE: Needs to support generic objects as well as Array objects
1256 */
1257
1258 // Spidermonkey behavior that we are mimicking...
1259 // splice() - no arguments - return undefined
1260 // splice(org arg) coerce the input to a number (otherwise it's zero) normal behavior
1261 // splice (two args) - coerce both args to numbers (otherwise they are zero)
1262 /*static*/ ArrayObject* ArrayClass::generic_splice(Toplevel* toplevel, Atom thisAtom, ArrayObject* args)
1263 {
1264 // This will return null but this case should never get hit (see Array.as)
1265 if (!args->getLength())
1266 return 0;
1267
1268 if (!AvmCore::isObject(thisAtom))
1269 return 0;
1270
1271 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1272
1273 uint32_t len = d->getLengthProperty();
1274
1275 uint32_t insertPoint = NativeObjectHelpers::ClampIndex(AvmCore::toInteger(args->getUintProperty(0)),len);
1276
1277 double d_deleteCount = args->getLength() > 1 ? AvmCore::toInteger(args->getUintProperty(1)) : (len - insertPoint);
1278 uint32_t deleteCount = (d_deleteCount < 0) ? 0 : AvmCore::integer_d(d_deleteCount);
1279 if (deleteCount > (len - insertPoint)) {
1280 deleteCount = len - insertPoint;
1281 }
1282 uint32_t end = insertPoint + deleteCount;
1283
1284 uint32_t insertCount = (args->getLength() > 2) ? (args->getLength() - 2) : 0;
1285 long l_shiftAmount = (long)insertCount - (long) deleteCount; // long because result could be negative
1286 uint32_t shiftAmount;
1287
1288 ArrayObject* a = toArray(thisAtom);
1289 ArrayObject* out;
1290 if (a && (out = a->try_splice(insertPoint, insertCount, deleteCount, args, 2)) != NULL__null)
1291 {
1292 return out;
1293 }
1294 // Copy out the elements we are going to remove
1295 out = toplevel->arrayClass()->newArray(deleteCount);
1296 for (uint32_t i=0; i< deleteCount; i++) {
1297 out->setUintProperty(i, d->getUintProperty(i+insertPoint));
1298 }
1299
1300 // delete items by shifting elements past end (of delete) by l_shiftAmount
1301 if (l_shiftAmount < 0) {
1302 // Shift the remaining elements down
1303 shiftAmount = (uint32_t)(-l_shiftAmount);
1304
1305 for (uint32_t i=end; i<len; i++) {
1306 d->setUintProperty(i-shiftAmount, d->getUintProperty(i));
1307 }
1308
1309 // delete top elements here to match ECMAscript spec (generic object support)
1310 for (uint32_t i=len-shiftAmount; i<len; i++) {
1311 d->delUintProperty (i);
1312 }
1313 } else {
1314 // Shift the remaining elements up.
1315 shiftAmount = (uint32_t)l_shiftAmount;
1316
1317 for (uint32_t i=len; i > end; ) { // Note: i is unsigned, can't check if --i >=0.
1318 --i;
1319 d->setUintProperty(i+shiftAmount, d->getUintProperty(i));
1320 }
1321 }
1322
1323 // Add the items to insert
1324 for (uint32_t i=0; i<insertCount; i++) {
1325 d->setUintProperty(insertPoint+i, args->getUintProperty(i + 2));
1326 }
1327
1328 // shrink array if shiftAmount is negative
1329 d->setLengthProperty(len+l_shiftAmount);
1330
1331 return out;
1332 }
1333
1334 ArrayObject* ArrayClass::newarray(Atom* argv, int argc)
1335 {
1336 return ArrayObject::create(core()->GetGC(), ivtable(), prototypePtr(), argv, argc);
1337 }
1338
1339 ArrayObject* ArrayClass::newArray(uint32_t capacity)
1340 {
1341 return ArrayObject::create(core()->GetGC(), ivtable(), prototypePtr(), capacity);
1342 }
1343
1344#ifdef VMCFG_AOT
1345 template <typename ADT>
1346 ArrayObject* ArrayClass::newArray(MethodEnv *env, ADT argDesc, va_list ap)
1347 {
1348 uint32_t argc = argDescArgCount(argDesc);
1349 AvmAssert(argc >= 0)do { } while (0);
1350 return ArrayObject::create<ADT>(core()->GetGC(), ivtable(), prototypePtr(), env, argDesc, argc, ap);
1351 }
1352
1353 template ArrayObject* ArrayClass::newArray(MethodEnv *env, uint32_t argDesc, va_list ap);
1354 template ArrayObject* ArrayClass::newArray(MethodEnv *env, char* argDesc, va_list ap);
1355#endif
1356
1357 /*static*/ int ArrayClass::generic_indexOf(Toplevel* toplevel, Atom thisAtom, Atom searchElement, int startIndex)
1358 {
1359 if (!AvmCore::isObject(thisAtom))
1360 return -1;
1361
1362 AvmCore* core = toplevel->core();
1363 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1364 uint32_t len = d->getLengthProperty();
1365
1366 uint32_t start = NativeObjectHelpers::ClampIndexInt(startIndex, len);
1367
1368 for (uint32_t i = start; i < len; i++)
1369 {
1370 Atom atom = d->getUintProperty(i);
1371 if (core->stricteq(atom, searchElement) == trueAtom)
1372 return i;
1373 }
1374
1375 return -1;
1376 }
1377
1378 /*static*/ int ArrayClass::generic_lastIndexOf(Toplevel* toplevel, Atom thisAtom, Atom searchElement, int startIndex)
1379 {
1380 if (!AvmCore::isObject(thisAtom))
1381 return -1;
1382
1383 AvmCore* core = toplevel->core();
1384 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1385 uint32_t len = d->getLengthProperty();
1386
1387 int start = NativeObjectHelpers::ClampIndexInt(startIndex, len);
1388 if (start == int(len))
1389 start--;
1390
1391 for (int i = start; i >= 0; i--)
1392 {
1393 Atom atom = d->getUintProperty(i);
1394 if (core->stricteq (atom, searchElement) == trueAtom)
1395 return i;
1396 }
1397
1398 return -1;
1399 }
1400
1401 /*static*/ boolbool ArrayClass::generic_every(Toplevel* toplevel, Atom thisAtom, ScriptObject *callback, Atom thisObject)
1402 {
1403 if (!AvmCore::isObject(thisAtom) || !callback)
1404 return truetrue;
1405
1406 if (callback->isMethodClosure() && !AvmCore::isNull(thisObject))
1407 {
1408 toplevel->throwTypeError(kArrayFilterNonNullObjectError);
1409 }
1410
1411 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1412 uint32_t len = d->getLengthProperty();
1413
1414 AvmCore* core = toplevel->core();
1415 for (uint32_t i = 0; i < len; i++)
1416 {
1417 // If thisObject is null, the call function will substitute the global object.
1418 // args are modified in place by callee
1419 Atom args[4] = { thisObject,
1420 d->getUintProperty(i), // element
1421 core->uintToAtom(i), // index
1422 thisAtom
1423 };
1424 Atom result = callback->call(3, args);
1425 if (result != trueAtom)
1426 return falsefalse;
1427 }
1428
1429 return truetrue;
1430 }
1431
1432 /*static*/ ArrayObject* ArrayClass::generic_filter(Toplevel* toplevel, Atom thisAtom, ScriptObject *callback, Atom thisObject)
1433 {
1434 ArrayObject *r = toplevel->arrayClass()->newArray();
1435
1436 if (!AvmCore::isObject(thisAtom) || !callback)
1437 return r;
1438
1439 if (callback->isMethodClosure() && !AvmCore::isNull(thisObject))
1440 {
1441 toplevel->throwTypeError(kArrayFilterNonNullObjectError);
1442 }
1443
1444 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1445 uint32_t len = d->getLengthProperty();
1446
1447 AvmCore* core = toplevel->core();
1448 for (uint32_t i = 0; i < len; i++)
1449 {
1450 // The Array and/or the args may be modified by the caller,
1451 // so get a local reference to the element.
1452 Atom element = d->getUintProperty(i);
1453 // If thisObject is null, the call function will substitute the global object
1454 // args are modified in place by callee
1455 Atom args[4] = {
1456 thisObject,
1457 element,
1458 core->uintToAtom(i), // index
1459 thisAtom
1460 };
1461 Atom result = callback->call(3, args);
1462 if (result == trueAtom)
1463 r->push(&element, 1);
1464 }
1465
1466 return r;
1467 }
1468
1469 /*static*/ void ArrayClass::generic_forEach(Toplevel* toplevel, Atom thisAtom, ScriptObject *callback, Atom thisObject)
1470 {
1471 if (!AvmCore::isObject(thisAtom) || !callback)
1472 return;
1473
1474 if (callback->isMethodClosure() && !AvmCore::isNull(thisObject))
1475 {
1476 toplevel->throwTypeError(kArrayFilterNonNullObjectError);
1477 }
1478
1479 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1480 uint32_t len = d->getLengthProperty();
1481
1482 AvmCore* core = toplevel->core();
1483 for (uint32_t i = 0; i < len; i++)
1484 {
1485 // If thisObject is null, the call function will substitute the global object
1486 // args are modified in place by callee
1487 Atom args[4] = { thisObject,
1488 d->getUintProperty(i), // element
1489 core->uintToAtom(i), // index
1490 thisAtom
1491 };
1492 callback->call(3, args);
1493 }
1494 }
1495
1496 /*static*/ boolbool ArrayClass::generic_some(Toplevel* toplevel, Atom thisAtom, ScriptObject *callback, Atom thisObject)
1497 {
1498 if (!AvmCore::isObject(thisAtom) || !callback)
1499 return falsefalse;
1500
1501 if (callback->isMethodClosure() && !AvmCore::isNull(thisObject))
1502 {
1503 toplevel->throwTypeError(kArrayFilterNonNullObjectError);
1504 }
1505
1506 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1507 uint32_t len = d->getLengthProperty();
1508
1509 AvmCore* core = toplevel->core();
1510 for (uint32_t i = 0; i < len; i++)
1511 {
1512 // If thisObject is null, the call function will substitute the global object
1513 // args are modified in place by callee
1514 Atom args[4] = {
1515 thisObject,
1516 d->getUintProperty(i), // element
1517 core->uintToAtom(i), // index
1518 thisAtom
1519 };
1520 Atom result = callback->call(3, args);
1521 if (result == trueAtom)
1522 return truetrue;
1523 }
1524
1525 return falsefalse;
1526 }
1527
1528 /*static*/ ArrayObject* ArrayClass::generic_map(Toplevel* toplevel, Atom thisAtom, ScriptObject *callback, Atom thisObject)
1529 {
1530 ArrayObject *r = toplevel->arrayClass()->newArray();
1531
1532 if (!AvmCore::isObject(thisAtom) || !callback)
1533 return r;
1534
1535 ScriptObject *d = AvmCore::atomToScriptObject(thisAtom);
1536 uint32_t len = d->getLengthProperty();
1537
1538 AvmCore* core = toplevel->core();
1539 for (uint32_t i = 0; i < len; i++)
1540 {
1541 // If thisObject is null, the call function will substitute the global object
1542 // args are modified in place by callee
1543 Atom args[4] = {
1544 thisObject,
1545 d->getUintProperty(i), // element
1546 core->uintToAtom(i), // index
1547 thisAtom
1548 };
1549 Atom result = callback->call(3, args);
1550 r->push(&result, 1);
1551 }
1552
1553 return r;
1554 }
1555
1556 /* static */ uint32_t ArrayClass::generic_unshift(Toplevel* /*toplevel*/, Atom thisAtom, ArrayObject* args)
1557 {
1558 ArrayObject* a = toArray(thisAtom);
1559 if (!a || !a->try_unshift(args))
1560 {
1561 for (uint32_t i = args->getLength() ; i > 0; i--)
1562 {
1563 Atom atom = args->getUintProperty(i - 1);
1564 a->unshift(&atom, 1);
1565 }
1566 }
1567 return a->getLengthProperty();
1568 }
1569}