2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3 * Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
4 * Copyright (C) 2003 Peter Kelly (pmk@post.com)
5 * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
25 #include "array_object.h"
26 #include "array_object.lut.h"
28 #include "error_object.h"
30 #include "operations.h"
32 #include <wtf/Assertions.h>
33 #include <wtf/HashSet.h>
37 // ------------------------------ ArrayPrototype ----------------------------
39 const ClassInfo ArrayPrototype::info = {"Array", &ArrayInstance::info, &arrayTable};
41 /* Source for array_object.lut.h
43 toString ArrayProtoFunc::ToString DontEnum|Function 0
44 toLocaleString ArrayProtoFunc::ToLocaleString DontEnum|Function 0
45 concat ArrayProtoFunc::Concat DontEnum|Function 1
46 join ArrayProtoFunc::Join DontEnum|Function 1
47 pop ArrayProtoFunc::Pop DontEnum|Function 0
48 push ArrayProtoFunc::Push DontEnum|Function 1
49 reverse ArrayProtoFunc::Reverse DontEnum|Function 0
50 shift ArrayProtoFunc::Shift DontEnum|Function 0
51 slice ArrayProtoFunc::Slice DontEnum|Function 2
52 sort ArrayProtoFunc::Sort DontEnum|Function 1
53 splice ArrayProtoFunc::Splice DontEnum|Function 2
54 unshift ArrayProtoFunc::UnShift DontEnum|Function 1
55 every ArrayProtoFunc::Every DontEnum|Function 1
56 forEach ArrayProtoFunc::ForEach DontEnum|Function 1
57 some ArrayProtoFunc::Some DontEnum|Function 1
58 indexOf ArrayProtoFunc::IndexOf DontEnum|Function 1
59 lastIndexOf ArrayProtoFunc::LastIndexOf DontEnum|Function 1
60 filter ArrayProtoFunc::Filter DontEnum|Function 1
61 map ArrayProtoFunc::Map DontEnum|Function 1
66 ArrayPrototype::ArrayPrototype(ExecState*, ObjectPrototype* objProto)
67 : ArrayInstance(objProto, 0)
71 bool ArrayPrototype::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
73 return getStaticFunctionSlot<ArrayProtoFunc, ArrayInstance>(exec, &arrayTable, this, propertyName, slot);
76 // ------------------------------ ArrayProtoFunc ----------------------------
78 ArrayProtoFunc::ArrayProtoFunc(ExecState* exec, int i, int len, const Identifier& name)
79 : InternalFunctionImp(static_cast<FunctionPrototype*>
80 (exec->lexicalInterpreter()->builtinFunctionPrototype()), name)
83 put(exec, exec->propertyNames().length, jsNumber(len), DontDelete | ReadOnly | DontEnum);
86 static JSValue *getProperty(ExecState *exec, JSObject *obj, unsigned index)
89 if (!obj->getPropertySlot(exec, index, slot))
91 return slot.getValue(exec, obj, index);
95 JSValue* ArrayProtoFunc::callAsFunction(ExecState* exec, JSObject* thisObj, const List& args)
97 unsigned length = thisObj->get(exec, exec->propertyNames().length)->toUInt32(exec);
99 JSValue *result = 0; // work around gcc 4.0 bug in uninitialized variable warning
105 if (!thisObj->inherits(&ArrayInstance::info))
106 return throwError(exec, TypeError);
110 static HashSet<JSObject*> visitedElems;
111 static const UString* empty = new UString("");
112 static const UString* comma = new UString(",");
113 bool alreadyVisited = !visitedElems.add(thisObj).second;
115 return jsString(*empty);
116 UString separator = *comma;
117 UString str = *empty;
119 if (id == Join && !args[0]->isUndefined())
120 separator = args[0]->toString(exec);
121 for (unsigned int k = 0; k < length; k++) {
125 JSObject *error = Error::create(exec, GeneralError, "Out of memory");
126 exec->setException(error);
130 JSValue* element = thisObj->get(exec, k);
131 if (element->isUndefinedOrNull())
134 bool fallback = false;
135 if (id == ToLocaleString) {
136 JSObject* o = element->toObject(exec);
137 JSValue* conversionFunction = o->get(exec, exec->propertyNames().toLocaleString);
138 if (conversionFunction->isObject() && static_cast<JSObject*>(conversionFunction)->implementsCall()) {
140 str += static_cast<JSObject*>(conversionFunction)->call(exec, o, args)->toString(exec);
142 // try toString() fallback
147 if (id == ToString || id == Join || fallback)
148 str += element->toString(exec);
151 JSObject *error = Error::create(exec, GeneralError, "Out of memory");
152 exec->setException(error);
155 if (exec->hadException())
158 visitedElems.remove(thisObj);
159 result = jsString(str);
163 JSObject *arr = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
165 JSValue *curArg = thisObj;
166 JSObject *curObj = static_cast<JSObject *>(thisObj);
167 ListIterator it = args.begin();
169 if (curArg->isObject() &&
170 curObj->inherits(&ArrayInstance::info)) {
172 // Older versions tried to optimize out getting the length of thisObj
173 // by checking for n != 0, but that doesn't work if thisObj is an empty array.
174 length = curObj->get(exec, exec->propertyNames().length)->toUInt32(exec);
176 if (JSValue *v = getProperty(exec, curObj, k))
177 arr->put(exec, n, v);
182 arr->put(exec, n, curArg);
185 if (it == args.end())
188 curObj = static_cast<JSObject *>(it++); // may be 0
190 arr->put(exec, exec->propertyNames().length, jsNumber(n), DontEnum | DontDelete);
197 thisObj->put(exec, exec->propertyNames().length, jsNumber(length), DontEnum | DontDelete);
198 result = jsUndefined();
200 result = thisObj->get(exec, length - 1);
201 thisObj->put(exec, exec->propertyNames().length, jsNumber(length - 1), DontEnum | DontDelete);
206 for (int n = 0; n < args.size(); n++)
207 thisObj->put(exec, length + n, args[n]);
208 length += args.size();
209 thisObj->put(exec, exec->propertyNames().length, jsNumber(length), DontEnum | DontDelete);
210 result = jsNumber(length);
215 unsigned int middle = length / 2;
217 for (unsigned int k = 0; k < middle; k++) {
218 unsigned lk1 = length - k - 1;
219 JSValue *obj2 = getProperty(exec, thisObj, lk1);
220 JSValue *obj = getProperty(exec, thisObj, k);
223 thisObj->put(exec, k, obj2);
225 thisObj->deleteProperty(exec, k);
228 thisObj->put(exec, lk1, obj);
230 thisObj->deleteProperty(exec, lk1);
237 thisObj->put(exec, exec->propertyNames().length, jsNumber(length), DontEnum | DontDelete);
238 result = jsUndefined();
240 result = thisObj->get(exec, 0);
241 for(unsigned int k = 1; k < length; k++) {
242 if (JSValue *obj = getProperty(exec, thisObj, k))
243 thisObj->put(exec, k-1, obj);
245 thisObj->deleteProperty(exec, k-1);
247 thisObj->deleteProperty(exec, length - 1);
248 thisObj->put(exec, exec->propertyNames().length, jsNumber(length - 1), DontEnum | DontDelete);
253 // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
255 // We return a new array
256 JSObject *resObj = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
258 double begin = args[0]->toInteger(exec);
268 if (args[1]->isUndefined())
271 end = args[1]->toInteger(exec);
283 int b = static_cast<int>(begin);
284 int e = static_cast<int>(end);
285 for(int k = b; k < e; k++, n++) {
286 if (JSValue *v = getProperty(exec, thisObj, k))
287 resObj->put(exec, n, v);
289 resObj->put(exec, exec->propertyNames().length, jsNumber(n), DontEnum | DontDelete);
294 printf("KJS Array::Sort length=%d\n", length);
295 for ( unsigned int i = 0 ; i<length ; ++i )
296 printf("KJS Array::Sort: %d: %s\n", i, thisObj->get(exec, i)->toString(exec).ascii() );
298 JSObject *sortFunction = NULL;
299 if (!args[0]->isUndefined())
301 sortFunction = args[0]->toObject(exec);
302 if (!sortFunction->implementsCall())
306 if (thisObj->classInfo() == &ArrayInstance::info) {
308 ((ArrayInstance *)thisObj)->sort(exec, sortFunction);
310 ((ArrayInstance *)thisObj)->sort(exec);
316 thisObj->put(exec, exec->propertyNames().length, jsNumber(0), DontEnum | DontDelete);
321 // "Min" sort. Not the fastest, but definitely less code than heapsort
322 // or quicksort, and much less swapping than bubblesort/insertionsort.
323 for ( unsigned int i = 0 ; i<length-1 ; ++i )
325 JSValue *iObj = thisObj->get(exec,i);
326 unsigned int themin = i;
327 JSValue *minObj = iObj;
328 for ( unsigned int j = i+1 ; j<length ; ++j )
330 JSValue *jObj = thisObj->get(exec,j);
332 if (jObj->isUndefined()) {
333 cmp = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
334 } else if (minObj->isUndefined()) {
336 } else if (sortFunction) {
340 cmp = sortFunction->call(exec, exec->dynamicInterpreter()->globalObject(), l)->toNumber(exec);
342 cmp = (jObj->toString(exec) < minObj->toString(exec)) ? -1 : 1;
353 //printf("KJS Array::Sort: swapping %d and %d\n", i, themin );
354 thisObj->put( exec, i, minObj );
355 thisObj->put( exec, themin, iObj );
359 printf("KJS Array::Sort -- Resulting array:\n");
360 for ( unsigned int i = 0 ; i<length ; ++i )
361 printf("KJS Array::Sort: %d: %s\n", i, thisObj->get(exec, i)->toString(exec).ascii() );
367 // 15.4.4.12 - oh boy this is huge
368 JSObject *resObj = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
370 int begin = args[0]->toUInt32(exec);
372 begin = maxInt( begin + length, 0 );
374 begin = minInt( begin, length );
375 unsigned int deleteCount = minInt( maxInt( args[1]->toUInt32(exec), 0 ), length - begin );
377 //printf( "Splicing from %d, deleteCount=%d \n", begin, deleteCount );
378 for(unsigned int k = 0; k < deleteCount; k++) {
379 if (JSValue *v = getProperty(exec, thisObj, k+begin))
380 resObj->put(exec, k, v);
382 resObj->put(exec, exec->propertyNames().length, jsNumber(deleteCount), DontEnum | DontDelete);
384 unsigned int additionalArgs = maxInt( args.size() - 2, 0 );
385 if ( additionalArgs != deleteCount )
387 if ( additionalArgs < deleteCount )
389 for ( unsigned int k = begin; k < length - deleteCount; ++k )
391 if (JSValue *v = getProperty(exec, thisObj, k+deleteCount))
392 thisObj->put(exec, k+additionalArgs, v);
394 thisObj->deleteProperty(exec, k+additionalArgs);
396 for ( unsigned int k = length ; k > length - deleteCount + additionalArgs; --k )
397 thisObj->deleteProperty(exec, k-1);
401 for ( unsigned int k = length - deleteCount; (int)k > begin; --k )
403 if (JSValue *obj = getProperty(exec, thisObj, k + deleteCount - 1))
404 thisObj->put(exec, k + additionalArgs - 1, obj);
406 thisObj->deleteProperty(exec, k+additionalArgs-1);
410 for ( unsigned int k = 0; k < additionalArgs; ++k )
412 thisObj->put(exec, k+begin, args[k+2]);
414 thisObj->put(exec, exec->propertyNames().length, jsNumber(length - deleteCount + additionalArgs), DontEnum | DontDelete);
417 case UnShift: { // 15.4.4.13
418 unsigned int nrArgs = args.size();
419 for ( unsigned int k = length; k > 0; --k )
421 if (JSValue *v = getProperty(exec, thisObj, k - 1))
422 thisObj->put(exec, k+nrArgs-1, v);
424 thisObj->deleteProperty(exec, k+nrArgs-1);
426 for ( unsigned int k = 0; k < nrArgs; ++k )
427 thisObj->put(exec, k, args[k]);
428 result = jsNumber(length + nrArgs);
429 thisObj->put(exec, exec->propertyNames().length, result, DontEnum | DontDelete);
434 JSObject *eachFunction = args[0]->toObject(exec);
436 if (!eachFunction->implementsCall())
437 return throwError(exec, TypeError);
439 JSObject *applyThis = args[1]->isUndefinedOrNull() ? exec->dynamicInterpreter()->globalObject() : args[1]->toObject(exec);
440 JSObject *resultArray;
443 resultArray = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec, List::empty()));
446 args.append(jsNumber(length));
447 resultArray = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec, args));
450 unsigned filterIndex = 0;
451 for (unsigned k = 0; k < length && !exec->hadException(); ++k) {
454 if (!thisObj->getPropertySlot(exec, k, slot))
457 JSValue *v = slot.getValue(exec, thisObj, k);
461 eachArguments.append(v);
462 eachArguments.append(jsNumber(k));
463 eachArguments.append(thisObj);
465 JSValue *result = eachFunction->call(exec, applyThis, eachArguments);
468 resultArray->put(exec, k, result);
469 else if (result->toBoolean(exec))
470 resultArray->put(exec, filterIndex++, v);
478 //Documentation for these three is available at:
479 //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:every
480 //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:forEach
481 //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:some
483 JSObject *eachFunction = args[0]->toObject(exec);
485 if (!eachFunction->implementsCall())
486 return throwError(exec, TypeError);
488 JSObject *applyThis = args[1]->isUndefinedOrNull() ? exec->dynamicInterpreter()->globalObject() : args[1]->toObject(exec);
490 if (id == Some || id == Every)
491 result = jsBoolean(id == Every);
493 result = jsUndefined();
495 for (unsigned k = 0; k < length && !exec->hadException(); ++k) {
498 if (!thisObj->getPropertySlot(exec, k, slot))
503 eachArguments.append(slot.getValue(exec, thisObj, k));
504 eachArguments.append(jsNumber(k));
505 eachArguments.append(thisObj);
507 bool predicateResult = eachFunction->call(exec, applyThis, eachArguments)->toBoolean(exec);
509 if (id == Every && !predicateResult) {
510 result = jsBoolean(false);
513 if (id == Some && predicateResult) {
514 result = jsBoolean(true);
522 // JavaScript 1.5 Extension by Mozilla
523 // Documentation: http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:indexOf
526 double d = args[1]->toInteger(exec);
533 index = static_cast<unsigned>(d);
536 JSValue* searchElement = args[0];
537 for (; index < length; ++index) {
538 JSValue* e = getProperty(exec, thisObj, index);
541 if (strictEqual(exec, searchElement, e))
542 return jsNumber(index);
548 // JavaScript 1.6 Extension by Mozilla
549 // Documentation: http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:lastIndexOf
551 int index = length - 1;
552 double d = args[1]->toIntegerPreserveNaN(exec);
560 index = static_cast<int>(d);
562 JSValue* searchElement = args[0];
563 for (; index >= 0; --index) {
564 JSValue* e = getProperty(exec, thisObj, index);
567 if (strictEqual(exec, searchElement, e))
568 return jsNumber(index);
581 // ------------------------------ ArrayObjectImp -------------------------------
583 ArrayObjectImp::ArrayObjectImp(ExecState *exec,
584 FunctionPrototype *funcProto,
585 ArrayPrototype *arrayProto)
586 : InternalFunctionImp(funcProto)
588 // ECMA 15.4.3.1 Array.prototype
589 put(exec, exec->propertyNames().prototype, arrayProto, DontEnum|DontDelete|ReadOnly);
591 // no. of arguments for constructor
592 put(exec, exec->propertyNames().length, jsNumber(1), ReadOnly|DontDelete|DontEnum);
595 bool ArrayObjectImp::implementsConstruct() const
601 JSObject *ArrayObjectImp::construct(ExecState *exec, const List &args)
603 // a single numeric argument denotes the array size (!)
604 if (args.size() == 1 && args[0]->isNumber()) {
605 uint32_t n = args[0]->toUInt32(exec);
606 if (n != args[0]->toNumber(exec))
607 return throwError(exec, RangeError, "Array size is not a small enough positive integer.");
608 return new ArrayInstance(exec->lexicalInterpreter()->builtinArrayPrototype(), n);
611 // otherwise the array is constructed with the arguments in it
612 return new ArrayInstance(exec->lexicalInterpreter()->builtinArrayPrototype(), args);
616 JSValue *ArrayObjectImp::callAsFunction(ExecState *exec, JSObject *, const List &args)
618 // equivalent to 'new Array(....)'
619 return construct(exec,args);