array_object.cpp
00001 // -*- c-basic-offset: 2 -*- 00002 /* 00003 * This file is part of the KDE libraries 00004 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) 00005 * Copyright (C) 2003 Apple Computer, Inc. 00006 * 00007 * This library is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU Lesser General Public 00009 * License as published by the Free Software Foundation; either 00010 * version 2 of the License, or (at your option) any later version. 00011 * 00012 * This library is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 * Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public 00018 * License along with this library; if not, write to the Free Software 00019 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00020 * 00021 */ 00022 00023 #include "value.h" 00024 #include "object.h" 00025 #include "types.h" 00026 #include "interpreter.h" 00027 #include "operations.h" 00028 #include "array_object.h" 00029 #include "internal.h" 00030 #include "error_object.h" 00031 00032 #include "array_object.lut.h" 00033 00034 #include <stdio.h> 00035 #include <string.h> 00036 #include <assert.h> 00037 00038 #define MAX_INDEX 4294967294U // 2^32-2 00039 00040 using namespace KJS; 00041 00042 // ------------------------------ ArrayInstanceImp ----------------------------- 00043 00044 const unsigned sparseArrayCutoff = 10000; 00045 00046 const ClassInfo ArrayInstanceImp::info = {"Array", 0, 0, 0}; 00047 00048 ArrayInstanceImp::ArrayInstanceImp(ObjectImp *proto, unsigned initialLength) 00049 : ObjectImp(proto) 00050 , length(initialLength) 00051 , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0) 00052 , capacity(storageLength) 00053 , storage(capacity ? (ValueImp **)calloc(capacity, sizeof(ValueImp *)) : 0) 00054 { 00055 } 00056 00057 ArrayInstanceImp::ArrayInstanceImp(ObjectImp *proto, const List &list) 00058 : ObjectImp(proto) 00059 , length(list.size()) 00060 , storageLength(length) 00061 , capacity(storageLength) 00062 , storage(capacity ? (ValueImp **)malloc(sizeof(ValueImp *) * capacity) : 0) 00063 { 00064 ListIterator it = list.begin(); 00065 unsigned l = length; 00066 for (unsigned i = 0; i < l; ++i) { 00067 storage[i] = (it++).imp(); 00068 } 00069 } 00070 00071 ArrayInstanceImp::~ArrayInstanceImp() 00072 { 00073 free(storage); 00074 } 00075 00076 Value ArrayInstanceImp::get(ExecState *exec, const Identifier &propertyName) const 00077 { 00078 if (propertyName == lengthPropertyName) 00079 return Number(length); 00080 00081 bool ok; 00082 unsigned index = propertyName.toArrayIndex(&ok); 00083 if (ok) { 00084 if (index >= length) 00085 return Undefined(); 00086 if (index < storageLength) { 00087 ValueImp *v = storage[index]; 00088 return v ? Value(v) : Undefined(); 00089 } 00090 } 00091 00092 return ObjectImp::get(exec, propertyName); 00093 } 00094 00095 Value ArrayInstanceImp::getPropertyByIndex(ExecState *exec, 00096 unsigned index) const 00097 { 00098 if (index > MAX_INDEX) 00099 return ObjectImp::get(exec, Identifier::from(index)); 00100 if (index >= length) 00101 return Undefined(); 00102 if (index < storageLength) { 00103 ValueImp *v = storage[index]; 00104 return v ? Value(v) : Undefined(); 00105 } 00106 00107 return ObjectImp::get(exec, Identifier::from(index)); 00108 } 00109 00110 // Special implementation of [[Put]] - see ECMA 15.4.5.1 00111 void ArrayInstanceImp::put(ExecState *exec, const Identifier &propertyName, const Value &value, int attr) 00112 { 00113 if (propertyName == lengthPropertyName) { 00114 unsigned int newLen = value.toUInt32(exec); 00115 if (value.toNumber(exec) != double(newLen)) { 00116 Object err = Error::create(exec, RangeError, "Invalid array length."); 00117 exec->setException(err); 00118 return; 00119 } 00120 setLength(newLen, exec); 00121 return; 00122 } 00123 00124 bool ok; 00125 unsigned index = propertyName.toArrayIndex(&ok); 00126 if (ok) { 00127 putPropertyByIndex(exec, index, value, attr); 00128 return; 00129 } 00130 00131 ObjectImp::put(exec, propertyName, value, attr); 00132 } 00133 00134 void ArrayInstanceImp::putPropertyByIndex(ExecState *exec, unsigned index, 00135 const Value &value, int attr) 00136 { 00137 if (index < sparseArrayCutoff && index >= storageLength) { 00138 resizeStorage(index + 1); 00139 } 00140 00141 if (index >= length && index <= MAX_INDEX) { 00142 length = index + 1; 00143 } 00144 00145 if (index < storageLength) { 00146 storage[index] = value.imp(); 00147 return; 00148 } 00149 00150 assert(index >= sparseArrayCutoff); 00151 ObjectImp::put(exec, Identifier::from(index), value, attr); 00152 } 00153 00154 bool ArrayInstanceImp::hasProperty(ExecState *exec, const Identifier &propertyName) const 00155 { 00156 if (propertyName == lengthPropertyName) 00157 return true; 00158 00159 bool ok; 00160 unsigned index = propertyName.toArrayIndex(&ok); 00161 if (ok) { 00162 if (index >= length) 00163 return false; 00164 if (index < storageLength) { 00165 ValueImp *v = storage[index]; 00166 return v && v != UndefinedImp::staticUndefined; 00167 } 00168 } 00169 00170 return ObjectImp::hasProperty(exec, propertyName); 00171 } 00172 00173 bool ArrayInstanceImp::hasPropertyByIndex(ExecState *exec, unsigned index) const 00174 { 00175 if (index > MAX_INDEX) 00176 return ObjectImp::hasProperty(exec, Identifier::from(index)); 00177 if (index >= length) 00178 return false; 00179 if (index < storageLength) { 00180 ValueImp *v = storage[index]; 00181 return v && v != UndefinedImp::staticUndefined; 00182 } 00183 00184 return ObjectImp::hasProperty(exec, Identifier::from(index)); 00185 } 00186 00187 bool ArrayInstanceImp::deleteProperty(ExecState *exec, const Identifier &propertyName) 00188 { 00189 if (propertyName == lengthPropertyName) 00190 return false; 00191 00192 bool ok; 00193 unsigned index = propertyName.toArrayIndex(&ok); 00194 if (ok) { 00195 if (index >= length) 00196 return true; 00197 if (index < storageLength) { 00198 storage[index] = 0; 00199 return true; 00200 } 00201 } 00202 00203 return ObjectImp::deleteProperty(exec, propertyName); 00204 } 00205 00206 bool ArrayInstanceImp::deletePropertyByIndex(ExecState *exec, unsigned index) 00207 { 00208 if (index > MAX_INDEX) 00209 return ObjectImp::deleteProperty(exec, Identifier::from(index)); 00210 if (index >= length) 00211 return true; 00212 if (index < storageLength) { 00213 storage[index] = 0; 00214 return true; 00215 } 00216 00217 return ObjectImp::deleteProperty(exec, Identifier::from(index)); 00218 } 00219 00220 ReferenceList ArrayInstanceImp::propList(ExecState *exec, bool recursive) 00221 { 00222 ReferenceList properties = ObjectImp::propList(exec,recursive); 00223 00224 // avoid fetching this every time through the loop 00225 ValueImp *undefined = UndefinedImp::staticUndefined; 00226 00227 for (unsigned i = 0; i < storageLength; ++i) { 00228 ValueImp *imp = storage[i]; 00229 if (imp && imp != undefined && !ObjectImp::hasProperty(exec,Identifier::from(i))) { 00230 properties.append(Reference(this, i)); 00231 } 00232 } 00233 return properties; 00234 } 00235 00236 void ArrayInstanceImp::resizeStorage(unsigned newLength) 00237 { 00238 if (newLength < storageLength) { 00239 memset(storage + newLength, 0, sizeof(ValueImp *) * (storageLength - newLength)); 00240 } 00241 if (newLength > capacity) { 00242 unsigned newCapacity; 00243 if (newLength > sparseArrayCutoff) { 00244 newCapacity = newLength; 00245 } else { 00246 newCapacity = (newLength * 3 + 1) / 2; 00247 if (newCapacity > sparseArrayCutoff) { 00248 newCapacity = sparseArrayCutoff; 00249 } 00250 } 00251 storage = (ValueImp **)realloc(storage, newCapacity * sizeof (ValueImp *)); 00252 memset(storage + capacity, 0, sizeof(ValueImp *) * (newCapacity - capacity)); 00253 capacity = newCapacity; 00254 } 00255 storageLength = newLength; 00256 } 00257 00258 void ArrayInstanceImp::setLength(unsigned newLength, ExecState *exec) 00259 { 00260 if (newLength <= storageLength) { 00261 resizeStorage(newLength); 00262 } 00263 00264 if (newLength < length) { 00265 ReferenceList sparseProperties; 00266 00267 _prop.addSparseArrayPropertiesToReferenceList(sparseProperties, Object(this)); 00268 00269 ReferenceListIterator it = sparseProperties.begin(); 00270 while (it != sparseProperties.end()) { 00271 Reference ref = it++; 00272 bool ok; 00273 unsigned index = ref.getPropertyName(exec).toArrayIndex(&ok); 00274 if (ok && index > newLength) { 00275 ref.deleteValue(exec); 00276 } 00277 } 00278 } 00279 00280 length = newLength; 00281 } 00282 00283 void ArrayInstanceImp::mark() 00284 { 00285 ObjectImp::mark(); 00286 unsigned l = storageLength; 00287 for (unsigned i = 0; i < l; ++i) { 00288 ValueImp *imp = storage[i]; 00289 if (imp && !imp->marked()) 00290 imp->mark(); 00291 } 00292 } 00293 00294 static ExecState *execForCompareByStringForQSort; 00295 00296 static int compareByStringForQSort(const void *a, const void *b) 00297 { 00298 ExecState *exec = execForCompareByStringForQSort; 00299 ValueImp *va = *(ValueImp **)a; 00300 ValueImp *vb = *(ValueImp **)b; 00301 if (va->dispatchType() == UndefinedType) { 00302 return vb->dispatchType() == UndefinedType ? 0 : 1; 00303 } 00304 if (vb->dispatchType() == UndefinedType) { 00305 return -1; 00306 } 00307 return compare(va->dispatchToString(exec), vb->dispatchToString(exec)); 00308 } 00309 00310 void ArrayInstanceImp::sort(ExecState *exec) 00311 { 00312 int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec); 00313 00314 execForCompareByStringForQSort = exec; 00315 qsort(storage, lengthNotIncludingUndefined, sizeof(ValueImp *), compareByStringForQSort); 00316 execForCompareByStringForQSort = 0; 00317 } 00318 00319 namespace KJS { 00320 00321 struct CompareWithCompareFunctionArguments { 00322 CompareWithCompareFunctionArguments(ExecState *e, ObjectImp *cf) 00323 : exec(e) 00324 , compareFunction(cf) 00325 , globalObject(e->dynamicInterpreter()->globalObject()) 00326 { 00327 arguments.append(Undefined()); 00328 arguments.append(Undefined()); 00329 } 00330 00331 ExecState *exec; 00332 ObjectImp *compareFunction; 00333 List arguments; 00334 Object globalObject; 00335 }; 00336 00337 } 00338 00339 static CompareWithCompareFunctionArguments *compareWithCompareFunctionArguments; 00340 00341 static int compareWithCompareFunctionForQSort(const void *a, const void *b) 00342 { 00343 CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments; 00344 00345 ValueImp *va = *(ValueImp **)a; 00346 ValueImp *vb = *(ValueImp **)b; 00347 if (va->dispatchType() == UndefinedType) { 00348 return vb->dispatchType() == UndefinedType ? 0 : 1; 00349 } 00350 if (vb->dispatchType() == UndefinedType) { 00351 return -1; 00352 } 00353 00354 args->arguments.clear(); 00355 args->arguments.append(va); 00356 args->arguments.append(vb); 00357 double compareResult = args->compareFunction->call 00358 (args->exec, args->globalObject, args->arguments).toNumber(args->exec); 00359 return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0; 00360 } 00361 00362 void ArrayInstanceImp::sort(ExecState *exec, Object &compareFunction) 00363 { 00364 int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec); 00365 00366 CompareWithCompareFunctionArguments args(exec, compareFunction.imp()); 00367 compareWithCompareFunctionArguments = &args; 00368 qsort(storage, lengthNotIncludingUndefined, sizeof(ValueImp *), compareWithCompareFunctionForQSort); 00369 compareWithCompareFunctionArguments = 0; 00370 } 00371 00372 unsigned ArrayInstanceImp::pushUndefinedObjectsToEnd(ExecState *exec) 00373 { 00374 ValueImp *undefined = UndefinedImp::staticUndefined; 00375 00376 unsigned o = 0; 00377 00378 for (unsigned i = 0; i != storageLength; ++i) { 00379 ValueImp *v = storage[i]; 00380 if (v && v != undefined) { 00381 if (o != i) 00382 storage[o] = v; 00383 o++; 00384 } 00385 } 00386 00387 ReferenceList sparseProperties; 00388 _prop.addSparseArrayPropertiesToReferenceList(sparseProperties, Object(this)); 00389 unsigned newLength = o + sparseProperties.length(); 00390 00391 if (newLength > storageLength) { 00392 resizeStorage(newLength); 00393 } 00394 00395 ReferenceListIterator it = sparseProperties.begin(); 00396 while (it != sparseProperties.end()) { 00397 Reference ref = it++; 00398 storage[o] = ref.getValue(exec).imp(); 00399 ObjectImp::deleteProperty(exec, ref.getPropertyName(exec)); 00400 o++; 00401 } 00402 00403 if (newLength != storageLength) 00404 memset(storage + o, 0, sizeof(ValueImp *) * (storageLength - o)); 00405 00406 return o; 00407 } 00408 00409 // ------------------------------ ArrayPrototypeImp ---------------------------- 00410 00411 const ClassInfo ArrayPrototypeImp::info = {"Array", &ArrayInstanceImp::info, &arrayTable, 0}; 00412 00413 /* Source for array_object.lut.h 00414 @begin arrayTable 17 00415 toString ArrayProtoFuncImp::ToString DontEnum|Function 0 00416 toLocaleString ArrayProtoFuncImp::ToLocaleString DontEnum|Function 0 00417 concat ArrayProtoFuncImp::Concat DontEnum|Function 1 00418 join ArrayProtoFuncImp::Join DontEnum|Function 1 00419 pop ArrayProtoFuncImp::Pop DontEnum|Function 0 00420 push ArrayProtoFuncImp::Push DontEnum|Function 1 00421 reverse ArrayProtoFuncImp::Reverse DontEnum|Function 0 00422 shift ArrayProtoFuncImp::Shift DontEnum|Function 0 00423 slice ArrayProtoFuncImp::Slice DontEnum|Function 2 00424 sort ArrayProtoFuncImp::Sort DontEnum|Function 1 00425 splice ArrayProtoFuncImp::Splice DontEnum|Function 2 00426 unshift ArrayProtoFuncImp::UnShift DontEnum|Function 1 00427 @end 00428 */ 00429 00430 // ECMA 15.4.4 00431 ArrayPrototypeImp::ArrayPrototypeImp(ExecState */*exec*/, 00432 ObjectPrototypeImp *objProto) 00433 : ArrayInstanceImp(objProto, 0) 00434 { 00435 Value protect(this); 00436 setInternalValue(Null()); 00437 } 00438 00439 Value ArrayPrototypeImp::get(ExecState *exec, const Identifier &propertyName) const 00440 { 00441 //fprintf( stderr, "ArrayPrototypeImp::get(%s)\n", propertyName.ascii() ); 00442 return lookupGetFunction<ArrayProtoFuncImp, ArrayInstanceImp>( exec, propertyName, &arrayTable, this ); 00443 } 00444 00445 // ------------------------------ ArrayProtoFuncImp ---------------------------- 00446 00447 ArrayProtoFuncImp::ArrayProtoFuncImp(ExecState *exec, int i, int len) 00448 : InternalFunctionImp( 00449 static_cast<FunctionPrototypeImp*>(exec->lexicalInterpreter()->builtinFunctionPrototype().imp()) 00450 ), id(i) 00451 { 00452 Value protect(this); 00453 put(exec,lengthPropertyName,Number(len),DontDelete|ReadOnly|DontEnum); 00454 } 00455 00456 bool ArrayProtoFuncImp::implementsCall() const 00457 { 00458 return true; 00459 } 00460 00461 // ECMA 15.4.4 00462 Value ArrayProtoFuncImp::call(ExecState *exec, Object &thisObj, const List &args) 00463 { 00464 unsigned int length = thisObj.get(exec,lengthPropertyName).toUInt32(exec); 00465 00466 Value result; 00467 switch (id) { 00468 case ToLocaleString: 00469 case ToString: 00470 00471 if (!thisObj.inherits(&ArrayInstanceImp::info)) { 00472 Object err = Error::create(exec,TypeError); 00473 exec->setException(err); 00474 return err; 00475 } 00476 00477 // fall through 00478 case Join: { 00479 UString separator = ","; 00480 UString str = ""; 00481 00482 if (id == Join && args.size() > 0 && !args[0].isA(UndefinedType)) 00483 separator = args[0].toString(exec); 00484 for (unsigned int k = 0; k < length; k++) { 00485 if (k >= 1) 00486 str += separator; 00487 00488 Value element = thisObj.get(exec, k); 00489 if (element.type() == UndefinedType || element.type() == NullType) 00490 continue; 00491 00492 bool fallback = false; 00493 if (id == ToLocaleString) { 00494 Object o = element.toObject(exec); 00495 Object conversionFunction = 00496 Object::dynamicCast(o.get(exec, toLocaleStringPropertyName)); 00497 if (conversionFunction.isValid() && 00498 conversionFunction.implementsCall()) { 00499 str += conversionFunction.call(exec, o, List()).toString(exec); 00500 } else { 00501 // try toString() fallback 00502 fallback = true; 00503 } 00504 } 00505 if (id == ToString || id == Join || fallback) { 00506 if (element.type() == ObjectType) { 00507 Object o = Object::dynamicCast(element); 00508 Object conversionFunction = 00509 Object::dynamicCast(o.get(exec, toStringPropertyName)); 00510 if (conversionFunction.isValid() && 00511 conversionFunction.implementsCall()) { 00512 str += conversionFunction.call(exec, o, List()).toString(exec); 00513 } else { 00514 UString msg = "Can't convert " + o.className() + 00515 " object to string"; 00516 Object error = Error::create(exec, RangeError, 00517 msg.cstring().c_str()); 00518 exec->setException(error); 00519 return error; 00520 } 00521 } else { 00522 str += element.toString(exec); 00523 } 00524 } 00525 if ( exec->hadException() ) 00526 break; 00527 } 00528 result = String(str); 00529 break; 00530 } 00531 case Concat: { 00532 Object arr = Object::dynamicCast(exec->lexicalInterpreter()->builtinArray().construct(exec,List::empty())); 00533 int n = 0; 00534 Value curArg = thisObj; 00535 Object curObj = Object::dynamicCast(thisObj); 00536 ListIterator it = args.begin(); 00537 for (;;) { 00538 if (curArg.type() == ObjectType && 00539 curObj.inherits(&ArrayInstanceImp::info)) { 00540 unsigned int k = 0; 00541 // Older versions tried to optimize out getting the length of thisObj 00542 // by checking for n != 0, but that doesn't work if thisObj is an empty array. 00543 length = curObj.get(exec,lengthPropertyName).toUInt32(exec); 00544 while (k < length) { 00545 if (curObj.hasProperty(exec,k)) 00546 arr.put(exec, n, curObj.get(exec, k)); 00547 n++; 00548 k++; 00549 } 00550 } else { 00551 arr.put(exec, n, curArg); 00552 n++; 00553 } 00554 if (it == args.end()) 00555 break; 00556 curArg = *it; 00557 curObj = Object::dynamicCast(it++); // may be 0 00558 } 00559 arr.put(exec,lengthPropertyName, Number(n), DontEnum | DontDelete); 00560 00561 result = arr; 00562 break; 00563 } 00564 case Pop:{ 00565 if (length == 0) { 00566 thisObj.put(exec, lengthPropertyName, Number(length), DontEnum | DontDelete); 00567 result = Undefined(); 00568 } else { 00569 result = thisObj.get(exec, length - 1); 00570 thisObj.put(exec, lengthPropertyName, Number(length - 1), DontEnum | DontDelete); 00571 } 00572 break; 00573 } 00574 case Push: { 00575 for (int n = 0; n < args.size(); n++) 00576 thisObj.put(exec, length + n, args[n]); 00577 length += args.size(); 00578 thisObj.put(exec,lengthPropertyName, Number(length), DontEnum | DontDelete); 00579 result = Number(length); 00580 break; 00581 } 00582 case Reverse: { 00583 00584 unsigned int middle = length / 2; 00585 00586 for (unsigned int k = 0; k < middle; k++) { 00587 unsigned lk1 = length - k - 1; 00588 Value obj = thisObj.get(exec,k); 00589 Value obj2 = thisObj.get(exec,lk1); 00590 if (thisObj.hasProperty(exec,lk1)) { 00591 if (thisObj.hasProperty(exec,k)) { 00592 thisObj.put(exec, k, obj2); 00593 thisObj.put(exec, lk1, obj); 00594 } else { 00595 thisObj.put(exec, k, obj2); 00596 thisObj.deleteProperty(exec, lk1); 00597 } 00598 } else { 00599 if (thisObj.hasProperty(exec, k)) { 00600 thisObj.deleteProperty(exec, k); 00601 thisObj.put(exec, lk1, obj); 00602 } else { 00603 // why delete something that's not there ? Strange. 00604 thisObj.deleteProperty(exec, k); 00605 thisObj.deleteProperty(exec, lk1); 00606 } 00607 } 00608 } 00609 result = thisObj; 00610 break; 00611 } 00612 case Shift: { 00613 if (length == 0) { 00614 thisObj.put(exec, lengthPropertyName, Number(length), DontEnum | DontDelete); 00615 result = Undefined(); 00616 } else { 00617 result = thisObj.get(exec, 0); 00618 for(unsigned int k = 1; k < length; k++) { 00619 if (thisObj.hasProperty(exec, k)) { 00620 Value obj = thisObj.get(exec, k); 00621 thisObj.put(exec, k-1, obj); 00622 } else 00623 thisObj.deleteProperty(exec, k-1); 00624 } 00625 thisObj.deleteProperty(exec, length - 1); 00626 thisObj.put(exec, lengthPropertyName, Number(length - 1), DontEnum | DontDelete); 00627 } 00628 break; 00629 } 00630 case Slice: { 00631 // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10 00632 00633 // We return a new array 00634 Object resObj = Object::dynamicCast(exec->lexicalInterpreter()->builtinArray().construct(exec,List::empty())); 00635 result = resObj; 00636 int begin = 0; 00637 if (args[0].type() != UndefinedType) { 00638 begin = args[0].toInteger(exec); 00639 if ( begin < 0 ) 00640 begin = maxInt( begin + length, 0 ); 00641 else 00642 begin = minInt( begin, length ); 00643 } 00644 int end = length; 00645 if (args[1].type() != UndefinedType) 00646 { 00647 end = args[1].toInteger(exec); 00648 if ( end < 0 ) 00649 end = maxInt( end + length, 0 ); 00650 else 00651 end = minInt( end, length ); 00652 } 00653 00654 //printf( "Slicing from %d to %d \n", begin, end ); 00655 int n = 0; 00656 for(int k = begin; k < end; k++, n++) { 00657 if (thisObj.hasProperty(exec, k)) { 00658 Value obj = thisObj.get(exec, k); 00659 resObj.put(exec, n, obj); 00660 } 00661 } 00662 resObj.put(exec, lengthPropertyName, Number(n), DontEnum | DontDelete); 00663 break; 00664 } 00665 case Sort:{ 00666 #if 0 00667 printf("KJS Array::Sort length=%d\n", length); 00668 for ( unsigned int i = 0 ; i<length ; ++i ) 00669 printf("KJS Array::Sort: %d: %s\n", i, thisObj.get(exec, i).toString(exec).ascii() ); 00670 #endif 00671 Object sortFunction; 00672 bool useSortFunction = (args[0].type() != UndefinedType); 00673 if (useSortFunction) 00674 { 00675 sortFunction = args[0].toObject(exec); 00676 if (!sortFunction.implementsCall()) 00677 useSortFunction = false; 00678 } 00679 00680 if (thisObj.imp()->classInfo() == &ArrayInstanceImp::info) { 00681 if (useSortFunction) 00682 ((ArrayInstanceImp *)thisObj.imp())->sort(exec, sortFunction); 00683 else 00684 ((ArrayInstanceImp *)thisObj.imp())->sort(exec); 00685 result = thisObj; 00686 break; 00687 } 00688 00689 if (length == 0) { 00690 thisObj.put(exec, lengthPropertyName, Number(0), DontEnum | DontDelete); 00691 result = thisObj; 00692 break; 00693 } 00694 00695 // "Min" sort. Not the fastest, but definitely less code than heapsort 00696 // or quicksort, and much less swapping than bubblesort/insertionsort. 00697 for ( unsigned int i = 0 ; i<length-1 ; ++i ) 00698 { 00699 Value iObj = thisObj.get(exec,i); 00700 unsigned int themin = i; 00701 Value minObj = iObj; 00702 for ( unsigned int j = i+1 ; j<length ; ++j ) 00703 { 00704 Value jObj = thisObj.get(exec,j); 00705 double cmp; 00706 if (jObj.type() == UndefinedType) { 00707 cmp = 1; // don't check minObj because there's no need to differentiate == (0) from > (1) 00708 } else if (minObj.type() == UndefinedType) { 00709 cmp = -1; 00710 } else if (useSortFunction) { 00711 List l; 00712 l.append(jObj); 00713 l.append(minObj); 00714 cmp = sortFunction.call(exec, exec->dynamicInterpreter()->globalObject(), l).toNumber(exec); 00715 } else { 00716 cmp = (jObj.toString(exec) < minObj.toString(exec)) ? -1 : 1; 00717 } 00718 if ( cmp < 0 ) 00719 { 00720 themin = j; 00721 minObj = jObj; 00722 } 00723 } 00724 // Swap themin and i 00725 if ( themin > i ) 00726 { 00727 //printf("KJS Array::Sort: swapping %d and %d\n", i, themin ); 00728 thisObj.put( exec, i, minObj ); 00729 thisObj.put( exec, themin, iObj ); 00730 } 00731 } 00732 #if 0 00733 printf("KJS Array::Sort -- Resulting array:\n"); 00734 for ( unsigned int i = 0 ; i<length ; ++i ) 00735 printf("KJS Array::Sort: %d: %s\n", i, thisObj.get(exec, i).toString(exec).ascii() ); 00736 #endif 00737 result = thisObj; 00738 break; 00739 } 00740 case Splice: { 00741 // 15.4.4.12 - oh boy this is huge 00742 Object resObj = Object::dynamicCast(exec->lexicalInterpreter()->builtinArray().construct(exec,List::empty())); 00743 result = resObj; 00744 int begin = args[0].toUInt32(exec); 00745 if ( begin < 0 ) 00746 begin = maxInt( begin + length, 0 ); 00747 else 00748 begin = minInt( begin, length ); 00749 unsigned int deleteCount = minInt( maxInt( args[1].toUInt32(exec), 0 ), length - begin ); 00750 00751 //printf( "Splicing from %d, deleteCount=%d \n", begin, deleteCount ); 00752 for(unsigned int k = 0; k < deleteCount; k++) { 00753 if (thisObj.hasProperty(exec,k+begin)) { 00754 Value obj = thisObj.get(exec, k+begin); 00755 resObj.put(exec, k, obj); 00756 } 00757 } 00758 resObj.put(exec, lengthPropertyName, Number(deleteCount), DontEnum | DontDelete); 00759 00760 unsigned int additionalArgs = maxInt( args.size() - 2, 0 ); 00761 if ( additionalArgs != deleteCount ) 00762 { 00763 if ( additionalArgs < deleteCount ) 00764 { 00765 for ( unsigned int k = begin; k < length - deleteCount; ++k ) 00766 { 00767 if (thisObj.hasProperty(exec,k+deleteCount)) { 00768 Value obj = thisObj.get(exec, k+deleteCount); 00769 thisObj.put(exec, k+additionalArgs, obj); 00770 } 00771 else 00772 thisObj.deleteProperty(exec, k+additionalArgs); 00773 } 00774 for ( unsigned int k = length ; k > length - deleteCount + additionalArgs; --k ) 00775 thisObj.deleteProperty(exec, k-1); 00776 } 00777 else 00778 { 00779 for ( unsigned int k = length - deleteCount; (int)k > begin; --k ) 00780 { 00781 if (thisObj.hasProperty(exec,k+deleteCount-1)) { 00782 Value obj = thisObj.get(exec, k+deleteCount-1); 00783 thisObj.put(exec, k+additionalArgs-1, obj); 00784 } 00785 else 00786 thisObj.deleteProperty(exec, k+additionalArgs-1); 00787 } 00788 } 00789 } 00790 for ( unsigned int k = 0; k < additionalArgs; ++k ) 00791 { 00792 thisObj.put(exec, k+begin, args[k+2]); 00793 } 00794 thisObj.put(exec, lengthPropertyName, Number(length - deleteCount + additionalArgs), DontEnum | DontDelete); 00795 break; 00796 } 00797 case UnShift: { // 15.4.4.13 00798 unsigned int nrArgs = args.size(); 00799 for ( unsigned int k = length; k > 0; --k ) 00800 { 00801 if (thisObj.hasProperty(exec,k-1)) { 00802 Value obj = thisObj.get(exec, k-1); 00803 thisObj.put(exec, k+nrArgs-1, obj); 00804 } else { 00805 thisObj.deleteProperty(exec, k+nrArgs-1); 00806 } 00807 } 00808 for ( unsigned int k = 0; k < nrArgs; ++k ) 00809 thisObj.put(exec, k, args[k]); 00810 result = Number(length + nrArgs); 00811 thisObj.put(exec, lengthPropertyName, result, DontEnum | DontDelete); 00812 break; 00813 } 00814 default: 00815 assert(0); 00816 break; 00817 } 00818 return result; 00819 } 00820 00821 // ------------------------------ ArrayObjectImp ------------------------------- 00822 00823 ArrayObjectImp::ArrayObjectImp(ExecState *exec, 00824 FunctionPrototypeImp *funcProto, 00825 ArrayPrototypeImp *arrayProto) 00826 : InternalFunctionImp(funcProto) 00827 { 00828 Value protect(this); 00829 // ECMA 15.4.3.1 Array.prototype 00830 put(exec,prototypePropertyName, Object(arrayProto), DontEnum|DontDelete|ReadOnly); 00831 00832 // no. of arguments for constructor 00833 put(exec,lengthPropertyName, Number(1), ReadOnly|DontDelete|DontEnum); 00834 } 00835 00836 bool ArrayObjectImp::implementsConstruct() const 00837 { 00838 return true; 00839 } 00840 00841 // ECMA 15.4.2 00842 Object ArrayObjectImp::construct(ExecState *exec, const List &args) 00843 { 00844 // a single numeric argument denotes the array size (!) 00845 if (args.size() == 1 && args[0].type() == NumberType) { 00846 unsigned int n = args[0].toUInt32(exec); 00847 if (n != args[0].toNumber(exec)) { 00848 Object error = Error::create(exec, RangeError, "Invalid array length."); 00849 exec->setException(error); 00850 return error; 00851 } 00852 return Object(new ArrayInstanceImp(exec->lexicalInterpreter()->builtinArrayPrototype().imp(), n)); 00853 } 00854 00855 // otherwise the array is constructed with the arguments in it 00856 return Object(new ArrayInstanceImp(exec->lexicalInterpreter()->builtinArrayPrototype().imp(), args)); 00857 } 00858 00859 bool ArrayObjectImp::implementsCall() const 00860 { 00861 return true; 00862 } 00863 00864 // ECMA 15.6.1 00865 Value ArrayObjectImp::call(ExecState *exec, Object &/*thisObj*/, const List &args) 00866 { 00867 // equivalent to 'new Array(....)' 00868 return construct(exec,args); 00869 }