| File: | platform/mac/avmshell/../../../core/ArrayClass.cpp |
| Location: | line 598, column 9 |
| Description: | Value stored to 'iFirstUndefined' is never read |
| 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 | |
| 54 | using namespace MMgc; |
| 55 | |
| 56 | namespace 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 | } |