JSArray.cpp 41.1 KB
Newer Older
darin's avatar
darin committed
1 2
/*
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3
 *  Copyright (C) 2003, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved.
darin's avatar
darin committed
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
 *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
 *
 *  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
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 */

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

darin@apple.com's avatar
darin@apple.com committed
26
#include "ArrayPrototype.h"
27
#include "ButterflyInlineMethods.h"
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
28 29
#include "CopiedSpace.h"
#include "CopiedSpaceInlineMethods.h"
30
#include "CachedCall.h"
31
#include "Error.h"
32
#include "Executable.h"
33
#include "GetterSetter.h"
34
#include "IndexingHeaderInlineMethods.h"
darin's avatar
darin committed
35
#include "PropertyNameArray.h"
36
#include "Reject.h"
ap@webkit.org's avatar
ap@webkit.org committed
37
#include <wtf/AVLTree.h>
38
#include <wtf/Assertions.h>
39
#include <wtf/OwnPtr.h>
40
#include <Operations.h>
darin's avatar
darin committed
41

42
using namespace std;
ap@webkit.org's avatar
ap@webkit.org committed
43
using namespace WTF;
bdash's avatar
bdash committed
44

45
namespace JSC {
darin's avatar
darin committed
46

47

ggaren@apple.com's avatar
ggaren@apple.com committed
48
ASSERT_CLASS_FITS_IN_CELL(JSArray);
49
ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
ggaren@apple.com's avatar
ggaren@apple.com committed
50

51
const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
darin's avatar
darin committed
52

53
Butterfly* createArrayButterflyInDictionaryIndexingMode(JSGlobalData& globalData, unsigned initialLength)
darin's avatar
darin committed
54
{
55 56 57 58 59 60 61 62 63
    Butterfly* butterfly = Butterfly::create(
        globalData, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0));
    ArrayStorage* storage = butterfly->arrayStorage();
    storage->setLength(initialLength);
    storage->setVectorLength(0);
    storage->m_indexBias = 0;
    storage->m_sparseMap.clear();
    storage->m_numValuesInVector = 0;
    return butterfly;
64 65 66 67 68 69 70 71
}

void JSArray::setLengthWritable(ExecState* exec, bool writable)
{
    ASSERT(isLengthWritable() || !writable);
    if (!isLengthWritable() || writable)
        return;

72
    enterDictionaryIndexingMode(exec->globalData());
73

74
    SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
75 76 77 78 79
    ASSERT(map);
    map->setLengthIsReadOnly();
}

// Defined in ES5.1 15.4.5.1
80
bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
81
{
82
    JSArray* array = jsCast<JSArray*>(object);
83 84 85 86 87

    // 3. If P is "length", then
    if (propertyName == exec->propertyNames().length) {
        // All paths through length definition call the default [[DefineOwnProperty]], hence:
        // from ES5.1 8.12.9 7.a.
88
        if (descriptor.configurablePresent() && descriptor.configurable())
89 90
            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
        // from ES5.1 8.12.9 7.b.
91
        if (descriptor.enumerablePresent() && descriptor.enumerable())
92 93 94 95 96 97 98
            return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");

        // a. If the [[Value]] field of Desc is absent, then
        // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
        if (descriptor.isAccessorDescriptor())
            return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
        // from ES5.1 8.12.9 10.a.
99
        if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
100 101 102
            return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
        // This descriptor is either just making length read-only, or changing nothing!
        if (!descriptor.value()) {
103 104
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
105 106 107 108 109 110 111 112 113 114 115 116 117 118
            return true;
        }
        
        // b. Let newLenDesc be a copy of Desc.
        // c. Let newLen be ToUint32(Desc.[[Value]]).
        unsigned newLen = descriptor.value().toUInt32(exec);
        // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
        if (newLen != descriptor.value().toNumber(exec)) {
            throwError(exec, createRangeError(exec, "Invalid array length"));
            return false;
        }

        // Based on SameValue check in 8.12.9, this is always okay.
        if (newLen == array->length()) {
119 120
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
            return true;
        }

        // e. Set newLenDesc.[[Value] to newLen.
        // f. If newLen >= oldLen, then
        // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
        // g. Reject if oldLenDesc.[[Writable]] is false.
        if (!array->isLengthWritable())
            return reject(exec, throwException, "Attempting to change value of a readonly property.");
        
        // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
        // i. Else,
        // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
        // i.ii. Let newWritable be false.
        // i.iii. Set newLenDesc.[[Writable] to true.
        // j. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
        // k. If succeeded is false, return false.
        // l. While newLen < oldLen repeat,
        // l.i. Set oldLen to oldLen – 1.
        // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
        // l.iii. If deleteSucceeded is false, then
142
        if (!array->setLength(exec, newLen, throwException)) {
143 144 145 146
            // 1. Set newLenDesc.[[Value] to oldLen+1.
            // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
            // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
            // 4. Reject.
147 148
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
149 150 151 152
            return false;
        }

        // m. If newWritable is false, then
153 154 155 156 157
        // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
        //    Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
        //    return true.
        if (descriptor.writablePresent())
            array->setLengthWritable(exec, descriptor.writable());
158 159 160 161 162 163
        // n. Return true.
        return true;
    }

    // 4. Else if P is an array index (15.4), then
    // a. Let index be ToUint32(P).
164 165
    unsigned index = propertyName.asIndex();
    if (index != PropertyName::NotAnIndex) {
166 167 168 169 170 171 172 173 174
        // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
        if (index >= array->length() && !array->isLengthWritable())
            return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property.");
        // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments.
        // d. Reject if succeeded is false.
        // e. If index >= oldLen
        // e.i. Set oldLenDesc.[[Value]] to index + 1.
        // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true.
        // f. Return true.
175
        return array->defineOwnIndexedProperty(exec, index, descriptor, throwException);
darin's avatar
darin committed
176 177
    }

178
    return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
darin's avatar
darin committed
179 180
}

181
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
182
{
183
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
184
    if (propertyName == exec->propertyNames().length) {
185
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
186 187 188
        return true;
    }

189
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
190 191
}

192
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
193
{
194
    JSArray* thisObject = jsCast<JSArray*>(object);
195
    if (propertyName == exec->propertyNames().length) {
196
        descriptor.setDescriptor(jsNumber(thisObject->length()), thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly);
197 198
        return true;
    }
199

200
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
201 202
}

203
// ECMA 15.4.5.1
204
void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
205
{
206
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
207 208

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
209 210
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
211
            throwError(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
darin's avatar
darin committed
212 213
            return;
        }
214
        thisObject->setLength(exec, newLength, slot.isStrictMode());
darin's avatar
darin committed
215 216 217
        return;
    }

218
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
219 220
}

221
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
222
{
223
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
224 225 226 227

    if (propertyName == exec->propertyNames().length)
        return false;

228
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
229 230
}

231 232
static int compareKeysForQSort(const void* a, const void* b)
{
233 234
    unsigned da = *static_cast<const unsigned*>(a);
    unsigned db = *static_cast<const unsigned*>(b);
235
    return (da > db) - (da < db);
darin's avatar
darin committed
236 237
}

238
void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
239
{
240
    JSArray* thisObject = jsCast<JSArray*>(object);
241

242 243 244
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

245
    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
246
}
darin's avatar
darin committed
247

248
// This method makes room in the vector, but leaves the new space for count slots uncleared.
249
bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, bool addToFront, unsigned count)
250
{
251 252 253 254
    ArrayStorage* storage = ensureArrayStorage(globalData);
    Butterfly* butterfly = storage->butterfly();
    unsigned propertyCapacity = structure()->outOfLineCapacity();
    unsigned propertySize = structure()->outOfLineSize();
255

256
    // If not, we should have handled this on the fast path.
257
    ASSERT(!addToFront || count > storage->m_indexBias);
258

259 260 261 262 263 264 265
    // Step 1:
    // Gather 4 key metrics:
    //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
    //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
    //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
    //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.

266 267
    unsigned length = storage->length();
    unsigned usedVectorLength = min(storage->vectorLength(), length);
268 269 270
    ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    // Check that required vector length is possible, in an overflow-safe fashion.
    if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
271
        return false;
272 273 274
    unsigned requiredVectorLength = usedVectorLength + count;
    ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
275 276
    ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
    unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
277 278 279 280
    // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
    unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);

    // Step 2:
281
    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
282

283
    void* newAllocBase = 0;
284 285 286
    unsigned newStorageCapacity;
    // If the current storage array is sufficiently large (but not too large!) then just keep using it.
    if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
287
        newAllocBase = butterfly->base(structure());
288 289
        newStorageCapacity = currentCapacity;
    } else {
290 291
        size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
        if (!globalData.heap.tryAllocateStorage(newSize, &newAllocBase))
292 293 294 295 296 297 298 299
            return false;
        newStorageCapacity = desiredCapacity;
    }

    // Step 3:
    // Work out where we're going to move things to.

    // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
300
    // If we're adding to the end, we'll add all the new space to the end.
301 302 303 304
    // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
    // If it did, we calculate the amount that will remain based on an atomic decay - leave the
    // vector with half the post-capacity it had previously.
    unsigned postCapacity = 0;
305 306 307
    if (!addToFront)
        postCapacity = max(newStorageCapacity - requiredVectorLength, count);
    else if (length < storage->vectorLength()) {
308
        // Atomic decay, + the post-capacity cannot be greater than what is available.
309 310 311
        postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
        // If we're moving contents within the same allocation, the post-capacity is being reduced.
        ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length);
312
    }
313

314 315 316 317
    unsigned newVectorLength = requiredVectorLength + postCapacity;
    unsigned newIndexBias = newStorageCapacity - newVectorLength;

    Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
318

319 320
    if (addToFront) {
        ASSERT(count + usedVectorLength <= newVectorLength);
321
        memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
322 323 324
        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
    } else if ((newAllocBase != butterfly->base(structure())) || (newIndexBias != storage->m_indexBias)) {
        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
325 326
        memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);

327 328 329 330 331
        WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector;
        for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
            newVector[i].clear();
    }

332 333
    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
334

335
    m_butterfly = newButterfly;
336

ap@webkit.org's avatar
ap@webkit.org committed
337
    return true;
darin's avatar
darin committed
338 339
}

340
bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
darin's avatar
darin committed
341
{
342 343
    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
    unsigned length = storage->length();
darin's avatar
darin committed
344

345
    // If the length is read only then we enter sparse mode, so should enter the following 'if'.
346
    ASSERT(isLengthWritable() || storage->m_sparseMap);
347

348
    if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
349 350 351 352 353 354 355 356 357 358
        // Fail if the length is not writable.
        if (map->lengthIsReadOnly())
            return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);

        if (newLength < length) {
            // Copy any keys we might be interested in into a vector.
            Vector<unsigned> keys;
            keys.reserveCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
            SparseArrayValueMap::const_iterator end = map->end();
            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
359
                unsigned index = static_cast<unsigned>(it->first);
360 361 362 363 364 365 366 367 368 369 370 371 372 373
                if (index < length && index >= newLength)
                    keys.append(index);
            }

            // Check if the array is in sparse mode. If so there may be non-configurable
            // properties, so we have to perform deletion with caution, if not we can
            // delete values in any order.
            if (map->sparseMode()) {
                qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
                unsigned i = keys.size();
                while (i) {
                    unsigned index = keys[--i];
                    SparseArrayValueMap::iterator it = map->find(index);
                    ASSERT(it != map->notFound());
374
                    if (it->second.attributes & DontDelete) {
375
                        storage->setLength(index + 1);
376 377 378 379 380 381 382
                        return reject(exec, throwException, "Unable to delete property.");
                    }
                    map->remove(it);
                }
            } else {
                for (unsigned i = 0; i < keys.size(); ++i)
                    map->remove(keys[i]);
383
                if (map->isEmpty())
384
                    deallocateSparseIndexMap();
385 386 387 388
            }
        }
    }

darin's avatar
darin committed
389
    if (newLength < length) {
390
        // Delete properties from the vector.
391
        unsigned usedVectorLength = min(length, storage->vectorLength());
darin's avatar
darin committed
392
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
393
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
394
            bool hadValue = valueSlot;
395
            valueSlot.clear();
darin's avatar
darin committed
396 397 398
            storage->m_numValuesInVector -= hadValue;
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
399

400
    storage->setLength(newLength);
401

402
    return true;
darin's avatar
darin committed
403 404
}

405
JSValue JSArray::pop(ExecState* exec)
406
{
407
    switch (structure()->indexingType()) {
408
    case ArrayClass:
409
        return jsUndefined();
410
        
411
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
412 413 414 415 416 417 418 419
        ArrayStorage* storage = m_butterfly->arrayStorage();
    
        unsigned length = storage->length();
        if (!length) {
            if (!isLengthWritable())
                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
            return jsUndefined();
        }
420

421 422 423 424 425 426 427
        unsigned index = length - 1;
        if (index < storage->vectorLength()) {
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
            if (valueSlot) {
                --storage->m_numValuesInVector;
                JSValue element = valueSlot.get();
                valueSlot.clear();
428
            
429 430 431 432
                ASSERT(isLengthWritable());
                storage->setLength(index);
                return element;
            }
433 434
        }

435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452
        // Let element be the result of calling the [[Get]] internal method of O with argument indx.
        JSValue element = get(exec, index);
        if (exec->hadException())
            return jsUndefined();
        // Call the [[Delete]] internal method of O with arguments indx and true.
        if (!deletePropertyByIndex(this, exec, index)) {
            throwTypeError(exec, "Unable to delete property.");
            return jsUndefined();
        }
        // Call the [[Put]] internal method of O with arguments "length", indx, and true.
        setLength(exec, index, true);
        // Return element.
        return element;
    }
        
    default:
        ASSERT_NOT_REACHED();
        return JSValue();
453
    }
454 455
}

456 457 458
// Push & putIndex are almost identical, with two small differences.
//  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
//  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
ggaren@apple.com's avatar
ggaren@apple.com committed
459
void JSArray::push(ExecState* exec, JSValue value)
460
{
461
    switch (structure()->indexingType()) {
462
    case ArrayClass: {
463 464
        putByIndexBeyondVectorLengthWithArrayStorage(exec, 0, value, true, createInitialArrayStorage(exec->globalData()));
        break;
465
    }
466
        
467 468 469 470 471 472 473 474 475 476
    case ArrayWithSlowPutArrayStorage: {
        unsigned oldLength = length();
        if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
            if (!exec->hadException() && oldLength < 0xFFFFFFFFu)
                setLength(exec, oldLength + 1, true);
            return;
        }
        // Fall through.
    }
        
477 478 479 480 481 482 483 484 485 486 487
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();

        // Fast case - push within vector, always update m_length & m_numValuesInVector.
        unsigned length = storage->length();
        if (length < storage->vectorLength()) {
            storage->m_vector[length].set(exec->globalData(), this, value);
            storage->setLength(length + 1);
            ++storage->m_numValuesInVector;
            return;
        }
488

489 490
        // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
        if (storage->length() > MAX_ARRAY_INDEX) {
491 492 493 494 495 496
            methodTable()->putByIndex(this, exec, storage->length(), value, true);
            // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
            if (!exec->hadException())
                throwError(exec, createRangeError(exec, "Invalid array length"));
            return;
        }
497

498 499 500 501 502 503 504 505
        // Handled the same as putIndex.
        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
        break;
    }
        
    default:
        ASSERT_NOT_REACHED();
    }
506 507
}

508
bool JSArray::shiftCount(ExecState* exec, unsigned startIndex, unsigned count)
509 510 511
{
    ASSERT(count > 0);
    
512
    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
513
    
514
    unsigned oldLength = storage->length();
515
    ASSERT(count <= oldLength);
516
    
517 518
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
519
    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode())
520
        return false;
521

522 523
    if (!oldLength)
        return true;
524
    
525 526
    unsigned length = oldLength - count;
    
527
    storage->m_numValuesInVector -= count;
528
    storage->setLength(length);
529
    
530
    unsigned vectorLength = storage->vectorLength();
531 532 533 534 535 536 537 538 539 540 541 542 543 544
    if (!vectorLength)
        return true;
    
    if (startIndex >= vectorLength)
        return true;
    
    if (startIndex + count > vectorLength)
        count = vectorLength - startIndex;
    
    unsigned usedVectorLength = min(vectorLength, oldLength);
    
    vectorLength -= count;
    storage->setVectorLength(vectorLength);
    
545
    if (vectorLength) {
546 547 548 549 550 551 552
        if (startIndex < usedVectorLength - (startIndex + count)) {
            if (startIndex) {
                memmove(
                    storage->m_vector + count,
                    storage->m_vector,
                    sizeof(JSValue) * startIndex);
            }
553 554 555
            m_butterfly = m_butterfly->shift(structure(), count);
            storage = m_butterfly->arrayStorage();
            storage->m_indexBias += count;
556 557 558 559 560 561 562
        } else {
            memmove(
                storage->m_vector + startIndex,
                storage->m_vector + startIndex + count,
                sizeof(JSValue) * (usedVectorLength - (startIndex + count)));
            for (unsigned i = usedVectorLength - count; i < usedVectorLength; ++i)
                storage->m_vector[i].clear();
563 564
        }
    }
565
    return true;
566
}
567 568

// Returns true if the unshift can be handled, false to fallback.    
569
bool JSArray::unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
570
{
571 572
    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
    unsigned length = storage->length();
573

574 575
    ASSERT(startIndex <= length);

576 577
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
578
    if (length != storage->m_numValuesInVector || storage->inSparseMode())
579 580
        return false;

581 582 583 584 585
    bool moveFront = !startIndex || startIndex < length / 2;

    unsigned vectorLength = storage->vectorLength();

    if (moveFront && storage->m_indexBias >= count) {
586 587 588
        m_butterfly = storage->butterfly()->unshift(structure(), count);
        storage = m_butterfly->arrayStorage();
        storage->m_indexBias -= count;
589 590 591 592
        storage->setVectorLength(vectorLength + count);
    } else if (!moveFront && vectorLength - length >= count)
        storage = storage->butterfly()->arrayStorage();
    else if (unshiftCountSlowCase(exec->globalData(), moveFront, count))
593 594
        storage = arrayStorage();
    else {
595
        throwOutOfMemoryError(exec);
596
        return true;
597
    }
598

599
    WriteBarrier<Unknown>* vector = storage->m_vector;
600 601 602 603

    if (startIndex) {
        if (moveFront)
            memmove(vector, vector + count, startIndex * sizeof(JSValue));
604
        else if (length - startIndex)
605 606 607
            memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
    }

608
    for (unsigned i = 0; i < count; i++)
609
        vector[i + startIndex].clear();
610
    return true;
611 612
}

ggaren@apple.com's avatar
ggaren@apple.com committed
613 614
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
615 616
    double da = static_cast<const JSValue*>(a)->asNumber();
    double db = static_cast<const JSValue*>(b)->asNumber();
ggaren@apple.com's avatar
ggaren@apple.com committed
617 618 619
    return (da > db) - (da < db);
}

620 621
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
622 623
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
624
    return codePointCompare(va->second, vb->second);
625
}
darin's avatar
darin committed
626

ggaren@apple.com's avatar
ggaren@apple.com committed
627
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
628
{
629
    ASSERT(!inSparseIndexingMode());
ggaren@apple.com's avatar
ggaren@apple.com committed
630

631
    switch (structure()->indexingType()) {
632
    case ArrayClass:
ggaren@apple.com's avatar
ggaren@apple.com committed
633 634
        return;
        
635
    case ArrayWithArrayStorage: {
636
        unsigned lengthNotIncludingUndefined = compactForSorting();
637
        ArrayStorage* storage = m_butterfly->arrayStorage();
638 639

        ASSERT(!storage->m_sparseMap);
640 641 642 643 644 645 646 647 648 649 650
        
        if (!lengthNotIncludingUndefined)
            return;
        
        bool allValuesAreNumbers = true;
        size_t size = storage->m_numValuesInVector;
        for (size_t i = 0; i < size; ++i) {
            if (!storage->m_vector[i].isNumber()) {
                allValuesAreNumbers = false;
                break;
            }
ggaren@apple.com's avatar
ggaren@apple.com committed
651
        }
652 653 654 655 656 657 658 659 660 661 662 663 664 665
        
        if (!allValuesAreNumbers)
            return sort(exec, compareFunction, callType, callData);
        
        // For numeric comparison, which is fast, qsort is faster than mergesort. We
        // also don't require mergesort's stability, since there's no user visible
        // side-effect from swapping the order of equal primitive values.
        qsort(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
        
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
ggaren@apple.com's avatar
ggaren@apple.com committed
666 667 668
    }
}

darin@apple.com's avatar
darin@apple.com committed
669
void JSArray::sort(ExecState* exec)
darin's avatar
darin committed
670
{
671
    ASSERT(!inSparseIndexingMode());
672
    
673
    switch (structure()->indexingType()) {
674
    case ArrayClass:
ap@webkit.org's avatar
ap@webkit.org committed
675
        return;
676 677
        
    case ArrayWithArrayStorage: {
678
        unsigned lengthNotIncludingUndefined = compactForSorting();
679
        ArrayStorage* storage = m_butterfly->arrayStorage();
680
        ASSERT(!storage->m_sparseMap);
681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719
        
        if (!lengthNotIncludingUndefined)
            return;
        
        // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
        // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
        // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
        // random or otherwise changing results, effectively making compare function inconsistent.
        
        Vector<ValueStringPair> values(lengthNotIncludingUndefined);
        if (!values.begin()) {
            throwOutOfMemoryError(exec);
            return;
        }
        
        Heap::heap(this)->pushTempSortVector(&values);
        
        bool isSortingPrimitiveValues = true;
        for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
            JSValue value = storage->m_vector[i].get();
            ASSERT(!value.isUndefined());
            values[i].first = value;
            isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
        }
        
        // FIXME: The following loop continues to call toString on subsequent values even after
        // a toString call raises an exception.
        
        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
            values[i].second = values[i].first.toWTFStringInline(exec);
        
        if (exec->hadException()) {
            Heap::heap(this)->popTempSortVector(&values);
            return;
        }
        
        // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
        // than O(N log N).
        
720
#if HAVE(MERGESORT)
721 722 723 724
        if (isSortingPrimitiveValues)
            qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
        else
            mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
725
#else
726 727 728
        // FIXME: The qsort library function is likely to not be a stable sort.
        // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
729
#endif
730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751
        
        // If the toString function changed the length of the array or vector storage,
        // increase the length to handle the orignal number of actual values.
        if (storage->vectorLength() < lengthNotIncludingUndefined) {
            increaseVectorLength(exec->globalData(), lengthNotIncludingUndefined);
            storage = m_butterfly->arrayStorage();
        }
        if (storage->length() < lengthNotIncludingUndefined)
            storage->setLength(lengthNotIncludingUndefined);
        
        JSGlobalData& globalData = exec->globalData();
        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
            storage->m_vector[i].set(globalData, this, values[i].first);
        
        Heap::heap(this)->popTempSortVector(&values);
        
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
    }
darin's avatar
darin committed
752 753
}

ap@webkit.org's avatar
ap@webkit.org committed
754
struct AVLTreeNodeForArrayCompare {
ggaren@apple.com's avatar
ggaren@apple.com committed
755
    JSValue value;
ap@webkit.org's avatar
ap@webkit.org committed
756 757 758 759 760 761 762 763 764 765

    // Child pointers.  The high bit of gt is robbed and used as the
    // balance factor sign.  The high bit of lt is robbed and used as
    // the magnitude of the balance factor.
    int32_t gt;
    int32_t lt;
};

struct AVLTreeAbstractorForArrayCompare {
    typedef int32_t handle; // Handle is an index into m_nodes vector.
ggaren@apple.com's avatar
ggaren@apple.com committed
766
    typedef JSValue key;
ap@webkit.org's avatar
ap@webkit.org committed
767 768 769 770
    typedef int32_t size;

    Vector<AVLTreeNodeForArrayCompare> m_nodes;
    ExecState* m_exec;
ggaren@apple.com's avatar
ggaren@apple.com committed
771
    JSValue m_compareFunction;
darin@apple.com's avatar
darin@apple.com committed
772 773
    CallType m_compareCallType;
    const CallData* m_compareCallData;
774
    OwnPtr<CachedCall> m_cachedCall;
ap@webkit.org's avatar
ap@webkit.org committed
775 776 777 778 779 780 781 782 783 784 785 786 787 788

    handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
    void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
    handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
    void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }

    int get_balance_factor(handle h)
    {
        if (m_nodes[h].gt & 0x80000000)
            return -1;
        return static_cast<unsigned>(m_nodes[h].lt) >> 31;
    }

    void set_balance_factor(handle h, int bf)
darin's avatar
darin committed
789
    {
ap@webkit.org's avatar
ap@webkit.org committed
790 791 792 793 794 795 796
        if (bf == 0) {
            m_nodes[h].lt &= 0x7FFFFFFF;
            m_nodes[h].gt &= 0x7FFFFFFF;
        } else {
            m_nodes[h].lt |= 0x80000000;
            if (bf < 0)
                m_nodes[h].gt |= 0x80000000;
ap@webkit.org's avatar
ap@webkit.org committed
797 798
            else
                m_nodes[h].gt &= 0x7FFFFFFF;
ap@webkit.org's avatar
ap@webkit.org committed
799
        }
darin's avatar
darin committed
800 801
    }

ap@webkit.org's avatar
ap@webkit.org committed
802
    int compare_key_key(key va, key vb)
ap@webkit.org's avatar
ap@webkit.org committed
803
    {
weinig@apple.com's avatar
weinig@apple.com committed
804 805
        ASSERT(!va.isUndefined());
        ASSERT(!vb.isUndefined());
darin's avatar
darin committed
806

ggaren@apple.com's avatar
ggaren@apple.com committed
807 808 809
        if (m_exec->hadException())
            return 1;

810 811
        double compareResult;
        if (m_cachedCall) {
812
            m_cachedCall->setThis(jsUndefined());
813 814
            m_cachedCall->setArgument(0, va);
            m_cachedCall->setArgument(1, vb);
815
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
816
        } else {
817
            MarkedArgumentBuffer arguments;
818 819
            arguments.append(va);
            arguments.append(vb);
820
            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
821
        }
ap@webkit.org's avatar
ap@webkit.org committed
822
        return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
ap@webkit.org's avatar
ap@webkit.org committed
823
    }
darin's avatar
darin committed
824

ap@webkit.org's avatar
ap@webkit.org committed
825 826 827 828
    int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
    int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }

    static handle null() { return 0x7FFFFFFF; }
ap@webkit.org's avatar
ap@webkit.org committed
829
};
darin's avatar
darin committed
830

ggaren@apple.com's avatar
ggaren@apple.com committed
831
void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
darin's avatar
darin committed
832
{
833 834 835
    ASSERT(!inSparseIndexingMode());
    
    switch (structure()->indexingType()) {
836
    case ArrayClass:
ap@webkit.org's avatar
ap@webkit.org committed
837
        return;
838 839 840 841 842 843
        
    case ArrayWithArrayStorage: {
        // FIXME: This ignores exceptions raised in the compare function or in toNumber.
        
        // The maximum tree depth is compiled in - but the caller is clearly up to no good
        // if a larger array is passed.
844 845
        ASSERT(arrayStorage()->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
        if (arrayStorage()->length() > static_cast<unsigned>(std::numeric_limits<int>::max()))
846 847
            return;
        
848 849 850
        unsigned usedVectorLength = min(arrayStorage()->length(), arrayStorage()->vectorLength());
        ASSERT(!arrayStorage()->m_sparseMap);
        unsigned nodeCount = usedVectorLength;
851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877
        
        if (!nodeCount)
            return;
        
        AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
        tree.abstractor().m_exec = exec;
        tree.abstractor().m_compareFunction = compareFunction;
        tree.abstractor().m_compareCallType = callType;
        tree.abstractor().m_compareCallData = &callData;
        tree.abstractor().m_nodes.grow(nodeCount);
        
        if (callType == CallTypeJS)
            tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
        
        if (!tree.abstractor().m_nodes.begin()) {
            throwOutOfMemoryError(exec);
            return;
        }
        
        // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
        // right out from under us while we're building the tree here.
        
        unsigned numDefined = 0;
        unsigned numUndefined = 0;
        
        // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
        for (; numDefined < usedVectorLength; ++numDefined) {
878 879 880
            if (numDefined > arrayStorage()->vectorLength())
                break;
            JSValue v = arrayStorage()->m_vector[numDefined].get();
881 882 883 884 885 886
            if (!v || v.isUndefined())
                break;
            tree.abstractor().m_nodes[numDefined].value = v;
            tree.insert(numDefined);
        }
        for (unsigned i = numDefined; i < usedVectorLength; ++i) {
887 888 889
            if (i > arrayStorage()->vectorLength())
                break;
            JSValue v = arrayStorage()->m_vector[i].get();
890 891 892 893 894 895 896 897
            if (v) {
                if (v.isUndefined())
                    ++numUndefined;
                else {
                    tree.abstractor().m_nodes[numDefined].value = v;
                    tree.insert(numDefined);
                    ++numDefined;
                }
ap@webkit.org's avatar
ap@webkit.org committed
898 899
            }
        }
900 901 902
        
        unsigned newUsedVectorLength = numDefined + numUndefined;
        
903
        ASSERT(!arrayStorage()->m_sparseMap);
904
        
905 906
        // The array size may have changed.  Figure out the new bounds.
        unsigned newestUsedVectorLength = min(arrayStorage()->length(), arrayStorage()->vectorLength());
907
        
908 909 910
        unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
        unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
        unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
911 912 913 914 915
        
        // Copy the values back into m_storage.
        AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
        iter.start_iter_least(tree);
        JSGlobalData& globalData = exec->globalData();
916 917
        for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
            arrayStorage()->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
918
            ++iter;
ap@webkit.org's avatar
ap@webkit.org committed
919
        }
920 921
        
        // Put undefined values back in.
922 923 924
        for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i)
            arrayStorage()->m_vector[i].setUndefined();

925
        // Ensure that unused values in the vector are zeroed out.
926 927
        for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i)
            arrayStorage()->m_vector[i].clear();
928
        
929 930
        arrayStorage()->m_numValuesInVector = undefinedElementsThreshold;

931
        return;
ap@webkit.org's avatar
ap@webkit.org committed
932
    }
933 934 935
        
    default:
        ASSERT_NOT_REACHED();
ap@webkit.org's avatar
ap@webkit.org committed
936
    }
darin's avatar
darin committed
937 938
}

939
void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
weinig@apple.com's avatar
weinig@apple.com committed
940
{
941
    switch (structure()->indexingType()) {
942
    case ArrayClass:
943 944
        return;
    
945
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964
        ArrayStorage* storage = m_butterfly->arrayStorage();
        
        WriteBarrier<Unknown>* vector = storage->m_vector;
        unsigned vectorEnd = min(storage->length(), storage->vectorLength());
        unsigned i = 0;
        for (; i < vectorEnd; ++i) {
            WriteBarrier<Unknown>& v = vector[i];
            if (!v)
                break;
            args.append(v.get());
        }
        
        for (; i < storage->length(); ++i)
            args.append(get(exec, i));
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
965
    }
weinig@apple.com's avatar
weinig@apple.com committed
966 967
}

968
void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
969
{
970
    ASSERT(length == this->length());
971
    switch (structure()->indexingType()) {
972
    case ArrayClass:
973 974
        return;
        
975
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993
        ArrayStorage* storage = m_butterfly->arrayStorage();
        unsigned i = 0;
        WriteBarrier<Unknown>* vector = storage->m_vector;
        unsigned vectorEnd = min(length, storage->vectorLength());
        for (; i < vectorEnd; ++i) {
            WriteBarrier<Unknown>& v = vector[i];
            if (!v)
                break;
            callFrame->setArgument(i, v.get());
        }
        
        for (; i < length; ++i)
            callFrame->setArgument(i, get(exec, i));
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
994
    }
995 996
}

997
unsigned JSArray::compactForSorting()
darin's avatar
darin committed
998
{
999
    ASSERT(!inSparseIndexingMode());
darin's avatar
darin committed
1000

1001
    switch (structure()->indexingType()) {
1002
    case ArrayClass:
1003
        return 0;
1004

1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();
        
        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
        
        unsigned numDefined = 0;
        unsigned numUndefined = 0;
        
        for (; numDefined < usedVectorLength; ++numDefined) {
            JSValue v = storage->m_vector[numDefined].get();
            if (!v || v.isUndefined())
                break;
darin's avatar
darin committed
1017
        }
1018 1019 1020 1021 1022 1023 1024 1025 1026
        
        for (unsigned i = numDefined; i < usedVectorLength; ++i) {
            JSValue v = storage->m_vector[i].get();
            if (v) {
                if (v.isUndefined())
                    ++numUndefined;
                else
                    storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
            }
darin's avatar
darin committed
1027
        }
1028 1029 1030
        
        unsigned newUsedVectorLength = numDefined + numUndefined;
        
1031
        ASSERT(!storage->m_sparseMap);
1032 1033 1034 1035 1036 1037 1038 1039 1040
        
        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
            storage->m_vector[i].setUndefined();
        for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
            storage->m_vector[i].clear();
        
        storage->m_numValuesInVector = newUsedVectorLength;
        
        return numDefined;