ArrayPrototype.cpp 41 KB
Newer Older
1 2
/*
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3
 *  Copyright (C) 2003, 2007, 2008, 2009, 2011 Apple Inc. All rights reserved.
4
 *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
ap's avatar
ap committed
5
 *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
6 7 8 9 10 11 12 13 14 15 16 17 18
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
19 20
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
 *  USA
21
 *
22 23
 */

mjs's avatar
mjs committed
24
#include "config.h"
darin@apple.com's avatar
darin@apple.com committed
25
#include "ArrayPrototype.h"
darin's avatar
darin committed
26

27
#include "CachedCall.h"
28
#include "CodeBlock.h"
ggaren@apple.com's avatar
ggaren@apple.com committed
29
#include "Interpreter.h"
30
#include "JIT.h"
31
#include "JSStringBuilder.h"
32
#include "Lookup.h"
33
#include "ObjectPrototype.h"
34
#include "Operations.h"
35
#include "StringRecursionChecker.h"
36
#include <algorithm>
ggaren's avatar
ggaren committed
37 38
#include <wtf/Assertions.h>
#include <wtf/HashSet.h>
eric@webkit.org's avatar
eric@webkit.org committed
39

40
namespace JSC {
darin's avatar
darin committed
41

ggaren@apple.com's avatar
ggaren@apple.com committed
42 43
ASSERT_CLASS_FITS_IN_CELL(ArrayPrototype);

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncEvery(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncForEach(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSome(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncFilter(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncMap(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState*);
static EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState*);
darin@apple.com's avatar
darin@apple.com committed
65 66 67 68 69

}

#include "ArrayPrototype.lut.h"

70
namespace JSC {
darin@apple.com's avatar
darin@apple.com committed
71

72
static inline bool isNumericCompareFunction(ExecState* exec, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
73 74 75
{
    if (callType != CallTypeJS)
        return false;
76

77 78 79 80
    FunctionExecutable* executable = callData.js.functionExecutable;

    JSObject* error = executable->compileForCall(exec, callData.js.scopeChain);
    if (error)
81
        return false;
82

83
    return executable->generatedBytecodeForCall().isNumericCompareFunction();
ggaren@apple.com's avatar
ggaren@apple.com committed
84 85
}

darin's avatar
darin committed
86
// ------------------------------ ArrayPrototype ----------------------------
87

88
const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, 0, ExecState::arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)};
89

darin@apple.com's avatar
darin@apple.com committed
90
/* Source for ArrayPrototype.lut.h
91
@begin arrayPrototypeTable 16
weinig@apple.com's avatar
weinig@apple.com committed
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
  toString       arrayProtoFuncToString       DontEnum|Function 0
  toLocaleString arrayProtoFuncToLocaleString DontEnum|Function 0
  concat         arrayProtoFuncConcat         DontEnum|Function 1
  join           arrayProtoFuncJoin           DontEnum|Function 1
  pop            arrayProtoFuncPop            DontEnum|Function 0
  push           arrayProtoFuncPush           DontEnum|Function 1
  reverse        arrayProtoFuncReverse        DontEnum|Function 0
  shift          arrayProtoFuncShift          DontEnum|Function 0
  slice          arrayProtoFuncSlice          DontEnum|Function 2
  sort           arrayProtoFuncSort           DontEnum|Function 1
  splice         arrayProtoFuncSplice         DontEnum|Function 2
  unshift        arrayProtoFuncUnShift        DontEnum|Function 1
  every          arrayProtoFuncEvery          DontEnum|Function 1
  forEach        arrayProtoFuncForEach        DontEnum|Function 1
  some           arrayProtoFuncSome           DontEnum|Function 1
  indexOf        arrayProtoFuncIndexOf        DontEnum|Function 1
  lastIndexOf    arrayProtoFuncLastIndexOf    DontEnum|Function 1
  filter         arrayProtoFuncFilter         DontEnum|Function 1
110
  reduce         arrayProtoFuncReduce         DontEnum|Function 1
111
  reduceRight    arrayProtoFuncReduceRight    DontEnum|Function 1
weinig@apple.com's avatar
weinig@apple.com committed
112
  map            arrayProtoFuncMap            DontEnum|Function 1
113 114
@end
*/
115

116
// ECMA 15.4.4
117 118
ArrayPrototype::ArrayPrototype(JSGlobalObject* globalObject, Structure* structure)
    : JSArray(globalObject->globalData(), structure)
119
{
120 121 122 123 124
}

void ArrayPrototype::finishCreation(JSGlobalObject* globalObject)
{
    Base::finishCreation(globalObject->globalData());
125
    ASSERT(inherits(&s_info));
126 127
}

mjs's avatar
mjs committed
128
bool ArrayPrototype::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
129
{
130
    return getStaticFunctionSlot<JSArray>(exec, ExecState::arrayPrototypeTable(exec), this, propertyName, slot);
131 132
}

133 134
bool ArrayPrototype::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
{
135
    return getStaticFunctionDescriptor<JSArray>(exec, ExecState::arrayPrototypeTable(exec), this, propertyName, descriptor);
136 137
}

weinig@apple.com's avatar
weinig@apple.com committed
138
// ------------------------------ Array Functions ----------------------------
139

weinig@apple.com's avatar
weinig@apple.com committed
140
// Helper function
ggaren@apple.com's avatar
ggaren@apple.com committed
141
static JSValue getProperty(ExecState* exec, JSObject* obj, unsigned index)
darin's avatar
darin committed
142
{
darin@apple.com's avatar
darin@apple.com committed
143
    PropertySlot slot(obj);
darin's avatar
darin committed
144
    if (!obj->getPropertySlot(exec, index, slot))
ggaren@apple.com's avatar
ggaren@apple.com committed
145
        return JSValue();
darin@apple.com's avatar
darin@apple.com committed
146
    return slot.getValue(exec, index);
darin's avatar
darin committed
147 148
}

ggaren@apple.com's avatar
ggaren@apple.com committed
149
static void putProperty(ExecState* exec, JSObject* obj, const Identifier& propertyName, JSValue value)
weinig@apple.com's avatar
weinig@apple.com committed
150 151 152 153 154
{
    PutPropertySlot slot;
    obj->put(exec, propertyName, value, slot);
}

155 156 157 158 159 160 161 162 163 164 165 166 167 168
static unsigned argumentClampedIndexFromStartOrEnd(ExecState* exec, int argument, unsigned length, unsigned undefinedValue = 0)
{
    JSValue value = exec->argument(argument);
    if (value.isUndefined())
        return undefinedValue;

    double indexDouble = value.toInteger(exec);
    if (indexDouble < 0) {
        indexDouble += length;
        return indexDouble < 0 ? 0 : static_cast<unsigned>(indexDouble);
    }
    return indexDouble > length ? length : static_cast<unsigned>(indexDouble);
}

169
EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
170
{
171
    JSValue thisValue = exec->hostThisValue();
172

173
    bool isRealArray = isJSArray(&exec->globalData(), thisValue);
174
    if (!isRealArray && !thisValue.inherits(&JSArray::s_info))
175
        return throwVMTypeError(exec);
176 177
    JSArray* thisObj = asArray(thisValue);
    
178 179 180 181
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

182 183 184
    StringRecursionChecker checker(exec, thisObj);
    if (EncodedJSValue earlyReturnValue = checker.earlyReturnValue())
        return earlyReturnValue;
weinig@apple.com's avatar
weinig@apple.com committed
185

186
    unsigned totalSize = length ? length - 1 : 0;
187 188 189 190 191 192
#if OS(SYMBIAN)
    // Symbian has very limited stack size available.
    // This function could be called recursively and allocating 1K on stack here cause
    // stack overflow on Symbian devices.
    Vector<RefPtr<StringImpl> > strBuffer(length);
#else
193
    Vector<RefPtr<StringImpl>, 256> strBuffer(length);
194
#endif    
darin@apple.com's avatar
darin@apple.com committed
195
    for (unsigned k = 0; k < length; k++) {
196 197 198 199 200 201
        JSValue element;
        if (isRealArray && thisObj->canGetIndex(k))
            element = thisObj->getIndex(k);
        else
            element = thisObj->get(exec, k);
        
weinig@apple.com's avatar
weinig@apple.com committed
202
        if (element.isUndefinedOrNull())
weinig@apple.com's avatar
weinig@apple.com committed
203
            continue;
204
        
weinig@apple.com's avatar
weinig@apple.com committed
205
        UString str = element.toString(exec);
206
        strBuffer[k] = str.impl();
207
        totalSize += str.length();
208
        
ap@webkit.org's avatar
ap@webkit.org committed
209
        if (!strBuffer.data()) {
210
            throwOutOfMemoryError(exec);
weinig@apple.com's avatar
weinig@apple.com committed
211
        }
212
        
weinig@apple.com's avatar
weinig@apple.com committed
213 214 215
        if (exec->hadException())
            break;
    }
216
    if (!totalSize)
217
        return JSValue::encode(jsEmptyString(exec));
218 219 220
    Vector<UChar> buffer;
    buffer.reserveCapacity(totalSize);
    if (!buffer.data())
221
        return JSValue::encode(throwOutOfMemoryError(exec));
222 223 224 225
        
    for (unsigned i = 0; i < length; i++) {
        if (i)
            buffer.append(',');
226
        if (RefPtr<StringImpl> rep = strBuffer[i])
227
            buffer.append(rep->characters(), rep->length());
228 229
    }
    ASSERT(buffer.size() == totalSize);
230
    return JSValue::encode(jsString(exec, UString::adopt(buffer)));
weinig@apple.com's avatar
weinig@apple.com committed
231 232
}

233
EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
234
{
235
    JSValue thisValue = exec->hostThisValue();
236

237
    if (!thisValue.inherits(&JSArray::s_info))
238
        return throwVMTypeError(exec);
darin@apple.com's avatar
darin@apple.com committed
239
    JSObject* thisObj = asArray(thisValue);
240

241 242 243 244
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

245 246 247
    StringRecursionChecker checker(exec, thisObj);
    if (EncodedJSValue earlyReturnValue = checker.earlyReturnValue())
        return earlyReturnValue;
248

249
    JSStringBuilder strBuffer;
darin@apple.com's avatar
darin@apple.com committed
250
    for (unsigned k = 0; k < length; k++) {
251
        if (k >= 1)
ap@webkit.org's avatar
ap@webkit.org committed
252
            strBuffer.append(',');
253

ggaren@apple.com's avatar
ggaren@apple.com committed
254
        JSValue element = thisObj->get(exec, k);
255 256 257 258 259
        if (!element.isUndefinedOrNull()) {
            JSObject* o = element.toObject(exec);
            JSValue conversionFunction = o->get(exec, exec->propertyNames().toLocaleString);
            UString str;
            CallData callData;
260
            CallType callType = getCallData(conversionFunction, callData);
261 262 263 264 265
            if (callType != CallTypeNone)
                str = call(exec, conversionFunction, callType, callData, element, exec->emptyList()).toString(exec);
            else
                str = element.toString(exec);
            strBuffer.append(str);
bdash's avatar
bdash committed
266
        }
267
    }
268

269
    return JSValue::encode(strBuffer.build(exec));
weinig@apple.com's avatar
weinig@apple.com committed
270 271
}

272
EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
273
{
274
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
275 276 277
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());
darin@apple.com's avatar
darin@apple.com committed
278

279 280 281
    StringRecursionChecker checker(exec, thisObj);
    if (EncodedJSValue earlyReturnValue = checker.earlyReturnValue())
        return earlyReturnValue;
weinig@apple.com's avatar
weinig@apple.com committed
282

283
    JSStringBuilder strBuffer;
284

285
    UString separator;
286 287
    if (!exec->argument(0).isUndefined())
        separator = exec->argument(0).toString(exec);
weinig@apple.com's avatar
weinig@apple.com committed
288

289 290 291
    unsigned k = 0;
    if (isJSArray(&exec->globalData(), thisObj)) {
        JSArray* array = asArray(thisObj);
292 293 294 295

        if (length) {
            if (!array->canGetIndex(k)) 
                goto skipFirstLoop;
296 297 298
            JSValue element = array->getIndex(k);
            if (!element.isUndefinedOrNull())
                strBuffer.append(element.toString(exec));
299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319
            k++;
        }

        if (separator.isNull()) {
            for (; k < length; k++) {
                if (!array->canGetIndex(k))
                    break;
                strBuffer.append(',');
                JSValue element = array->getIndex(k);
                if (!element.isUndefinedOrNull())
                    strBuffer.append(element.toString(exec));
            }
        } else {
            for (; k < length; k++) {
                if (!array->canGetIndex(k))
                    break;
                strBuffer.append(separator);
                JSValue element = array->getIndex(k);
                if (!element.isUndefinedOrNull())
                    strBuffer.append(element.toString(exec));
            }
320 321
        }
    }
322
 skipFirstLoop:
323
    for (; k < length; k++) {
324 325 326 327 328
        if (k >= 1) {
            if (separator.isNull())
                strBuffer.append(',');
            else
                strBuffer.append(separator);
weinig@apple.com's avatar
weinig@apple.com committed
329 330
        }

ggaren@apple.com's avatar
ggaren@apple.com committed
331
        JSValue element = thisObj->get(exec, k);
332 333
        if (!element.isUndefinedOrNull())
            strBuffer.append(element.toString(exec));
weinig@apple.com's avatar
weinig@apple.com committed
334
    }
335

336
    return JSValue::encode(strBuffer.build(exec));
weinig@apple.com's avatar
weinig@apple.com committed
337 338
}

339
EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
340
{
341
    JSValue thisValue = exec->hostThisValue();
darin@apple.com's avatar
darin@apple.com committed
342
    JSArray* arr = constructEmptyArray(exec);
343
    unsigned n = 0;
344
    JSValue curArg = thisValue.toThisObject(exec);
345 346
    size_t i = 0;
    size_t argCount = exec->argumentCount();
eric@webkit.org's avatar
eric@webkit.org committed
347
    while (1) {
348
        if (curArg.inherits(&JSArray::s_info)) {
oliver@apple.com's avatar
oliver@apple.com committed
349 350
            unsigned length = curArg.get(exec, exec->propertyNames().length).toUInt32(exec);
            JSObject* curObject = curArg.toObject(exec);
darin@apple.com's avatar
darin@apple.com committed
351
            for (unsigned k = 0; k < length; ++k) {
ggaren@apple.com's avatar
ggaren@apple.com committed
352
                if (JSValue v = getProperty(exec, curObject, k))
weinig@apple.com's avatar
weinig@apple.com committed
353 354 355 356 357 358
                    arr->put(exec, n, v);
                n++;
            }
        } else {
            arr->put(exec, n, curArg);
            n++;
359
        }
360
        if (i == argCount)
weinig@apple.com's avatar
weinig@apple.com committed
361
            break;
362 363
        curArg = (exec->argument(i));
        ++i;
364
    }
darin@apple.com's avatar
darin@apple.com committed
365
    arr->setLength(n);
366
    return JSValue::encode(arr);
weinig@apple.com's avatar
weinig@apple.com committed
367
}
368

369
EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
370
{
371
    JSValue thisValue = exec->hostThisValue();
372

373
    if (isJSArray(&exec->globalData(), thisValue))
374
        return JSValue::encode(asArray(thisValue)->pop());
375

376
    JSObject* thisObj = thisValue.toThisObject(exec);
weinig@apple.com's avatar
weinig@apple.com committed
377
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
378 379 380 381
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

    JSValue result;
382
    if (length == 0) {
383
        putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(length));
eric@webkit.org's avatar
eric@webkit.org committed
384
        result = jsUndefined();
385
    } else {
eric@webkit.org's avatar
eric@webkit.org committed
386
        result = thisObj->get(exec, length - 1);
darin@apple.com's avatar
darin@apple.com committed
387
        thisObj->deleteProperty(exec, length - 1);
388
        putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(length - 1));
389
    }
390
    return JSValue::encode(result);
weinig@apple.com's avatar
weinig@apple.com committed
391 392
}

393
EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
394
{
395
    JSValue thisValue = exec->hostThisValue();
396

397
    if (isJSArray(&exec->globalData(), thisValue) && exec->argumentCount() == 1) {
darin@apple.com's avatar
darin@apple.com committed
398
        JSArray* array = asArray(thisValue);
399
        array->push(exec, exec->argument(0));
400
        return JSValue::encode(jsNumber(array->length()));
401 402
    }

403
    JSObject* thisObj = thisValue.toThisObject(exec);
weinig@apple.com's avatar
weinig@apple.com committed
404
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
405 406 407
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

408 409 410 411 412 413
    for (unsigned n = 0; n < exec->argumentCount(); n++) {
        // Check for integer overflow; where safe we can do a fast put by index.
        if (length + n >= length)
            thisObj->put(exec, length + n, exec->argument(n));
        else {
            PutPropertySlot slot;
414
            Identifier propertyName(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toString(exec));
415 416 417
            thisObj->put(exec, propertyName, exec->argument(n), slot);
        }
    }
418
    JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount()));
419 420
    putProperty(exec, thisObj, exec->propertyNames().length, newLength);
    return JSValue::encode(newLength);
weinig@apple.com's avatar
weinig@apple.com committed
421
}
422

423
EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
424
{
425
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
weinig@apple.com's avatar
weinig@apple.com committed
426
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
427 428
    if (exec->hadException())
        return JSValue::encode(jsUndefined());
429

430
    unsigned middle = length / 2;
darin@apple.com's avatar
darin@apple.com committed
431
    for (unsigned k = 0; k < middle; k++) {
weinig@apple.com's avatar
weinig@apple.com committed
432
        unsigned lk1 = length - k - 1;
ggaren@apple.com's avatar
ggaren@apple.com committed
433 434
        JSValue obj2 = getProperty(exec, thisObj, lk1);
        JSValue obj = getProperty(exec, thisObj, k);
mjs's avatar
mjs committed
435

eric@webkit.org's avatar
eric@webkit.org committed
436
        if (obj2)
weinig@apple.com's avatar
weinig@apple.com committed
437 438 439
            thisObj->put(exec, k, obj2);
        else
            thisObj->deleteProperty(exec, k);
mjs's avatar
mjs committed
440

weinig@apple.com's avatar
weinig@apple.com committed
441 442 443 444
        if (obj)
            thisObj->put(exec, lk1, obj);
        else
            thisObj->deleteProperty(exec, lk1);
445
    }
446
    return JSValue::encode(thisObj);
weinig@apple.com's avatar
weinig@apple.com committed
447 448
}

449
EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
450
{
451 452 453
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
    JSValue result;

weinig@apple.com's avatar
weinig@apple.com committed
454
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
455 456 457
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

458
    if (length == 0) {
459
        putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(length));
eric@webkit.org's avatar
eric@webkit.org committed
460
        result = jsUndefined();
461
    } else {
eric@webkit.org's avatar
eric@webkit.org committed
462
        result = thisObj->get(exec, 0);
463 464 465 466 467 468 469 470 471 472
        if (isJSArray(&exec->globalData(), thisObj))
            ((JSArray *)thisObj)->shiftCount(exec, 1);
        else {
            for (unsigned k = 1; k < length; k++) {
                if (JSValue obj = getProperty(exec, thisObj, k))
                    thisObj->put(exec, k - 1, obj);
                else
                    thisObj->deleteProperty(exec, k - 1);
            }
            thisObj->deleteProperty(exec, length - 1);
eric@webkit.org's avatar
eric@webkit.org committed
473
        }
474
        putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(length - 1));
475
    }
476
    return JSValue::encode(result);
weinig@apple.com's avatar
weinig@apple.com committed
477 478
}

479
EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
480
{
481
    // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
482
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
darin@apple.com's avatar
darin@apple.com committed
483

484
    // We return a new array
darin@apple.com's avatar
darin@apple.com committed
485
    JSArray* resObj = constructEmptyArray(exec);
ggaren@apple.com's avatar
ggaren@apple.com committed
486
    JSValue result = resObj;
487

488 489 490 491
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

492 493
    unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
    unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length);
494

495 496
    unsigned n = 0;
    for (unsigned k = begin; k < end; k++, n++) {
ggaren@apple.com's avatar
ggaren@apple.com committed
497
        if (JSValue v = getProperty(exec, thisObj, k))
weinig@apple.com's avatar
weinig@apple.com committed
498
            resObj->put(exec, n, v);
499
    }
darin@apple.com's avatar
darin@apple.com committed
500
    resObj->setLength(n);
501
    return JSValue::encode(result);
weinig@apple.com's avatar
weinig@apple.com committed
502 503
}

504
EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
505
{
506
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
507 508 509
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (!length || exec->hadException())
        return JSValue::encode(thisObj);
darin@apple.com's avatar
darin@apple.com committed
510

511
    JSValue function = exec->argument(0);
darin@apple.com's avatar
darin@apple.com committed
512
    CallData callData;
513
    CallType callType = getCallData(function, callData);
eric@webkit.org's avatar
eric@webkit.org committed
514

515
    if (thisObj->classInfo() == &JSArray::s_info) {
516
        if (isNumericCompareFunction(exec, callType, callData))
ggaren@apple.com's avatar
ggaren@apple.com committed
517 518
            asArray(thisObj)->sortNumeric(exec, function, callType, callData);
        else if (callType != CallTypeNone)
darin@apple.com's avatar
darin@apple.com committed
519
            asArray(thisObj)->sort(exec, function, callType, callData);
eric@webkit.org's avatar
eric@webkit.org committed
520
        else
darin@apple.com's avatar
darin@apple.com committed
521
            asArray(thisObj)->sort(exec);
522
        return JSValue::encode(thisObj);
523
    }
524

525 526
    // "Min" sort. Not the fastest, but definitely less code than heapsort
    // or quicksort, and much less swapping than bubblesort/insertionsort.
darin@apple.com's avatar
darin@apple.com committed
527
    for (unsigned i = 0; i < length - 1; ++i) {
ggaren@apple.com's avatar
ggaren@apple.com committed
528
        JSValue iObj = thisObj->get(exec, i);
529 530
        if (exec->hadException())
            return JSValue::encode(jsUndefined());
darin@apple.com's avatar
darin@apple.com committed
531
        unsigned themin = i;
ggaren@apple.com's avatar
ggaren@apple.com committed
532
        JSValue minObj = iObj;
darin@apple.com's avatar
darin@apple.com committed
533
        for (unsigned j = i + 1; j < length; ++j) {
ggaren@apple.com's avatar
ggaren@apple.com committed
534
            JSValue jObj = thisObj->get(exec, j);
535 536
            if (exec->hadException())
                return JSValue::encode(jsUndefined());
eric@webkit.org's avatar
eric@webkit.org committed
537
            double compareResult;
weinig@apple.com's avatar
weinig@apple.com committed
538
            if (jObj.isUndefined())
eric@webkit.org's avatar
eric@webkit.org committed
539
                compareResult = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
weinig@apple.com's avatar
weinig@apple.com committed
540
            else if (minObj.isUndefined())
eric@webkit.org's avatar
eric@webkit.org committed
541
                compareResult = -1;
darin@apple.com's avatar
darin@apple.com committed
542
            else if (callType != CallTypeNone) {
543
                MarkedArgumentBuffer l;
544 545
                l.append(jObj);
                l.append(minObj);
546
                compareResult = call(exec, function, callType, callData, jsUndefined(), l).toNumber(exec);
eric@webkit.org's avatar
eric@webkit.org committed
547
            } else
weinig@apple.com's avatar
weinig@apple.com committed
548
                compareResult = (jObj.toString(exec) < minObj.toString(exec)) ? -1 : 1;
eric@webkit.org's avatar
eric@webkit.org committed
549 550

            if (compareResult < 0) {
551 552
                themin = j;
                minObj = jObj;
eric@webkit.org's avatar
eric@webkit.org committed
553 554
            }
        }
555
        // Swap themin and i
eric@webkit.org's avatar
eric@webkit.org committed
556 557 558 559
        if (themin > i) {
            thisObj->put(exec, i, minObj);
            thisObj->put(exec, themin, iObj);
        }
weinig@apple.com's avatar
weinig@apple.com committed
560
    }
561
    return JSValue::encode(thisObj);
weinig@apple.com's avatar
weinig@apple.com committed
562 563
}

564
EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
565
{
eric@webkit.org's avatar
eric@webkit.org committed
566
    // 15.4.4.12
ap@apple.com's avatar
ap@apple.com committed
567

568
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
569 570 571 572
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

573
    if (!exec->argumentCount())
574
        return JSValue::encode(constructEmptyArray(exec));
ap@apple.com's avatar
ap@apple.com committed
575

576 577 578 579 580 581 582 583 584 585 586 587
    unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);

    unsigned deleteCount = length - begin;
    if (exec->argumentCount() > 1) {
        double deleteDouble = exec->argument(1).toInteger(exec);
        if (deleteDouble < 0)
            deleteCount = 0;
        else if (deleteDouble > length - begin)
            deleteCount = length - begin;
        else
            deleteCount = static_cast<unsigned>(deleteDouble);
    }
588

589
    JSArray* resObj = JSArray::create(exec->globalData(), exec->lexicalGlobalObject()->arrayStructure(), deleteCount, CreateCompact);
590
    JSValue result = resObj;
591
    JSGlobalData& globalData = exec->globalData();
592
    for (unsigned k = 0; k < deleteCount; k++)
593
        resObj->uncheckedSetIndex(globalData, k, getProperty(exec, thisObj, k + begin));
594

darin@apple.com's avatar
darin@apple.com committed
595
    resObj->setLength(deleteCount);
596

597
    unsigned additionalArgs = std::max<int>(exec->argumentCount() - 2, 0);
eric@webkit.org's avatar
eric@webkit.org committed
598 599
    if (additionalArgs != deleteCount) {
        if (additionalArgs < deleteCount) {
600 601 602 603 604 605 606 607 608 609 610
            if ((!begin) && (isJSArray(&exec->globalData(), thisObj)))
                ((JSArray *)thisObj)->shiftCount(exec, deleteCount - additionalArgs);
            else {
                for (unsigned k = begin; k < length - deleteCount; ++k) {
                    if (JSValue v = getProperty(exec, thisObj, k + deleteCount))
                        thisObj->put(exec, k + additionalArgs, v);
                    else
                        thisObj->deleteProperty(exec, k + additionalArgs);
                }
                for (unsigned k = length; k > length - deleteCount + additionalArgs; --k)
                    thisObj->deleteProperty(exec, k - 1);
eric@webkit.org's avatar
eric@webkit.org committed
611 612
            }
        } else {
613 614 615 616 617 618 619 620 621
            if ((!begin) && (isJSArray(&exec->globalData(), thisObj)))
                ((JSArray *)thisObj)->unshiftCount(exec, additionalArgs - deleteCount);
            else {
                for (unsigned k = length - deleteCount; k > begin; --k) {
                    if (JSValue obj = getProperty(exec, thisObj, k + deleteCount - 1))
                        thisObj->put(exec, k + additionalArgs - 1, obj);
                    else
                        thisObj->deleteProperty(exec, k + additionalArgs - 1);
                }
eric@webkit.org's avatar
eric@webkit.org committed
622
            }
623 624
        }
    }
darin@apple.com's avatar
darin@apple.com committed
625
    for (unsigned k = 0; k < additionalArgs; ++k)
626
        thisObj->put(exec, k + begin, exec->argument(k + 2));
eric@webkit.org's avatar
eric@webkit.org committed
627

628
    putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(length - deleteCount + additionalArgs));
629
    return JSValue::encode(result);
weinig@apple.com's avatar
weinig@apple.com committed
630 631
}

632
EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
633 634
{
    // 15.4.4.13
635

636
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
weinig@apple.com's avatar
weinig@apple.com committed
637
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
638 639 640
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

641
    unsigned nrArgs = exec->argumentCount();
642 643 644 645 646 647 648 649 650 651
    if ((nrArgs) && (length)) {
        if (isJSArray(&exec->globalData(), thisObj))
            ((JSArray *)thisObj)->unshiftCount(exec, nrArgs);
        else {
            for (unsigned k = length; k > 0; --k) {
                if (JSValue v = getProperty(exec, thisObj, k - 1))
                    thisObj->put(exec, k + nrArgs - 1, v);
                else
                    thisObj->deleteProperty(exec, k + nrArgs - 1);
            }
darin@apple.com's avatar
darin@apple.com committed
652
        }
653
    }
darin@apple.com's avatar
darin@apple.com committed
654
    for (unsigned k = 0; k < nrArgs; ++k)
655
        thisObj->put(exec, k, exec->argument(k));
656
    JSValue result = jsNumber(length + nrArgs);
weinig@apple.com's avatar
weinig@apple.com committed
657
    putProperty(exec, thisObj, exec->propertyNames().length, result);
658
    return JSValue::encode(result);
weinig@apple.com's avatar
weinig@apple.com committed
659 660
}

661
EncodedJSValue JSC_HOST_CALL arrayProtoFuncFilter(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
662
{
663
    JSObject* thisObj = exec->hostThisValue().toThisObject(exec);
664 665 666
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());
eric@webkit.org's avatar
eric@webkit.org committed
667

668
    JSValue function = exec->argument(0);
darin@apple.com's avatar
darin@apple.com committed
669
    CallData callData;
670
    CallType callType = getCallData(function, callData);
darin@apple.com's avatar
darin@apple.com committed
671
    if (callType == CallTypeNone)
672
        return throwVMTypeError(exec);
eric@webkit.org's avatar
eric@webkit.org committed
673

674
    JSValue applyThis = exec->argument(1);
darin@apple.com's avatar
darin@apple.com committed
675
    JSArray* resultArray = constructEmptyArray(exec);
weinig@apple.com's avatar
weinig@apple.com committed
676

677
    unsigned filterIndex = 0;
678 679
    unsigned k = 0;
    if (callType == CallTypeJS && isJSArray(&exec->globalData(), thisObj)) {
680 681
        JSFunction* f = asFunction(function);
        JSArray* array = asArray(thisObj);
682
        CachedCall cachedCall(exec, f, 3);
683 684 685
        for (; k < length && !exec->hadException(); ++k) {
            if (!array->canGetIndex(k))
                break;
ggaren@apple.com's avatar
ggaren@apple.com committed
686
            JSValue v = array->getIndex(k);
687 688
            cachedCall.setThis(applyThis);
            cachedCall.setArgument(0, v);
689
            cachedCall.setArgument(1, jsNumber(k));
690
            cachedCall.setArgument(2, thisObj);
691
            
ggaren@apple.com's avatar
ggaren@apple.com committed
692
            JSValue result = cachedCall.call();
693 694 695
            if (result.toBoolean(exec))
                resultArray->put(exec, filterIndex++, v);
        }
696
        if (k == length)
697
            return JSValue::encode(resultArray);
698 699 700 701 702
    }
    for (; k < length && !exec->hadException(); ++k) {
        PropertySlot slot(thisObj);
        if (!thisObj->getPropertySlot(exec, k, slot))
            continue;
ggaren@apple.com's avatar
ggaren@apple.com committed
703
        JSValue v = slot.getValue(exec, k);
704

705 706
        if (exec->hadException())
            return JSValue::encode(jsUndefined());
707

708
        MarkedArgumentBuffer eachArguments;
709
        eachArguments.append(v);
710
        eachArguments.append(jsNumber(k));
711 712
        eachArguments.append(thisObj);

ggaren@apple.com's avatar
ggaren@apple.com committed
713
        JSValue result = call(exec, function, callType, callData, applyThis, eachArguments);
714 715
        if (result.toBoolean(exec))
            resultArray->put(exec, filterIndex++, v);
716
    }
717
    return JSValue::encode(resultArray);
weinig@apple.com's avatar
weinig@apple.com committed
718 719
}

720
EncodedJSValue JSC_HOST_CALL arrayProtoFuncMap(ExecState* exec)
weinig@apple.com's avatar
weinig@apple.com committed
721
{