JSArray.cpp 36.2 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 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 "CachedCall.h"
28
#include "Error.h"
29
#include "Executable.h"
darin's avatar
darin committed
30
#include "PropertyNameArray.h"
ap@webkit.org's avatar
ap@webkit.org committed
31
#include <wtf/AVLTree.h>
32
#include <wtf/Assertions.h>
33
#include <wtf/OwnPtr.h>
34
#include <Operations.h>
darin's avatar
darin committed
35

36 37
#define CHECK_ARRAY_CONSISTENCY 0

38
using namespace std;
ap@webkit.org's avatar
ap@webkit.org committed
39
using namespace WTF;
bdash's avatar
bdash committed
40

41
namespace JSC {
darin's avatar
darin committed
42

ggaren@apple.com's avatar
ggaren@apple.com committed
43 44
ASSERT_CLASS_FITS_IN_CELL(JSArray);

barraclough@apple.com's avatar
barraclough@apple.com committed
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
// Overview of JSArray
//
// Properties of JSArray objects may be stored in one of three locations:
//   * The regular JSObject property map.
//   * A storage vector.
//   * A sparse map of array entries.
//
// Properties with non-numeric identifiers, with identifiers that are not representable
// as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
// (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
// integer) are not considered array indices and will be stored in the JSObject property map.
//
// All properties with a numeric identifer, representable as an unsigned integer i,
// where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
// storage vector or the sparse map.  An array index i will be handled in the following
// fashion:
//
//   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
//   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
//     be stored in the storage vector or in the sparse array, depending on the density of
//     data that would be stored in the vector (a vector being used where at least
//     (1 / minDensityMultiplier) of the entries would be populated).
//   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
//     in the sparse array.

// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
ggaren@apple.com's avatar
ggaren@apple.com committed
72 73 74
// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(JSValue)) +
// (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue))
barraclough@apple.com's avatar
barraclough@apple.com committed
75 76 77 78 79

// These values have to be macros to be used in max() and min() without introducing
// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
#define MIN_SPARSE_ARRAY_INDEX 10000U
#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
80
// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
barraclough@apple.com's avatar
barraclough@apple.com committed
81
#define MAX_ARRAY_INDEX 0xFFFFFFFEU
darin's avatar
darin committed
82 83

// Our policy for when to use a vector and when to use a sparse map.
barraclough@apple.com's avatar
barraclough@apple.com committed
84 85
// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
darin's avatar
darin committed
86 87 88
// as long as it is 1/8 full. If more sparse than that, we use a map.
static const unsigned minDensityMultiplier = 8;

darin@apple.com's avatar
darin@apple.com committed
89
const ClassInfo JSArray::info = {"Array", 0, 0, 0};
darin's avatar
darin committed
90 91 92

static inline size_t storageSize(unsigned vectorLength)
{
barraclough@apple.com's avatar
barraclough@apple.com committed
93 94 95 96
    ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);

    // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
    // - as asserted above - the following calculation cannot overflow.
ggaren@apple.com's avatar
ggaren@apple.com committed
97
    size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue));
barraclough@apple.com's avatar
barraclough@apple.com committed
98 99
    // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
    // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
ggaren@apple.com's avatar
ggaren@apple.com committed
100
    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));
barraclough@apple.com's avatar
barraclough@apple.com committed
101 102

    return size;
darin's avatar
darin committed
103 104 105 106
}

static inline unsigned increasedVectorLength(unsigned newLength)
{
barraclough@apple.com's avatar
barraclough@apple.com committed
107 108 109 110 111 112 113 114 115 116 117
    ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);

    // Mathematically equivalent to:
    //   increasedLength = (newLength * 3 + 1) / 2;
    // or:
    //   increasedLength = (unsigned)ceil(newLength * 1.5));
    // This form is not prone to internal overflow.
    unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1);
    ASSERT(increasedLength >= newLength);

    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
darin's avatar
darin committed
118 119 120 121 122 123 124
}

static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
{
    return length / minDensityMultiplier <= numValues;
}

125 126
#if !CHECK_ARRAY_CONSISTENCY

darin@apple.com's avatar
darin@apple.com committed
127
inline void JSArray::checkConsistency(ConsistencyCheckType)
128 129 130 131 132
{
}

#endif

133
JSArray::JSArray(NonNullPassRefPtr<Structure> structure)
darin@apple.com's avatar
darin@apple.com committed
134
    : JSObject(structure)
weinig@apple.com's avatar
weinig@apple.com committed
135 136 137 138
{
    unsigned initialCapacity = 0;

    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
139
    m_vectorLength = initialCapacity;
weinig@apple.com's avatar
weinig@apple.com committed
140 141 142 143

    checkConsistency();
}

144
JSArray::JSArray(NonNullPassRefPtr<Structure> structure, unsigned initialLength)
darin@apple.com's avatar
darin@apple.com committed
145
    : JSObject(structure)
darin's avatar
darin committed
146
{
barraclough@apple.com's avatar
barraclough@apple.com committed
147
    unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
darin's avatar
darin committed
148

149
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
ggaren@apple.com's avatar
ggaren@apple.com committed
150
    m_storage->m_length = initialLength;
151
    m_vectorLength = initialCapacity;
152 153
    m_storage->m_numValuesInVector = 0;
    m_storage->m_sparseValueMap = 0;
ap@apple.com's avatar
ap@apple.com committed
154
    m_storage->subclassData = 0;
155
    m_storage->reportedMapCapacity = 0;
darin's avatar
darin committed
156

157 158 159 160
    JSValue* vector = m_storage->m_vector;
    for (size_t i = 0; i < initialCapacity; ++i)
        vector[i] = JSValue();

161
    checkConsistency();
162 163

    Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));
darin's avatar
darin committed
164 165
}

166
JSArray::JSArray(NonNullPassRefPtr<Structure> structure, const ArgList& list)
darin@apple.com's avatar
darin@apple.com committed
167
    : JSObject(structure)
darin's avatar
darin committed
168
{
169
    unsigned initialCapacity = list.size();
darin's avatar
darin committed
170

171 172
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
    m_storage->m_length = initialCapacity;
173
    m_vectorLength = initialCapacity;
174 175
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 0;
ap@apple.com's avatar
ap@apple.com committed
176
    m_storage->subclassData = 0;
177
    m_storage->reportedMapCapacity = 0;
darin's avatar
darin committed
178

ggaren's avatar
ggaren committed
179
    size_t i = 0;
darin@apple.com's avatar
darin@apple.com committed
180 181
    ArgList::const_iterator end = list.end();
    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
182
        m_storage->m_vector[i] = *it;
darin's avatar
darin committed
183

184
    checkConsistency();
185 186

    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
darin's avatar
darin committed
187 188
}

darin@apple.com's avatar
darin@apple.com committed
189
JSArray::~JSArray()
darin's avatar
darin committed
190
{
ap@apple.com's avatar
ap@apple.com committed
191
    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
192 193
    checkConsistency(DestructorConsistencyCheck);

darin's avatar
darin committed
194 195 196 197
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage);
}

198
bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
darin's avatar
darin committed
199 200 201
{
    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
202
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
203
        if (i > MAX_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
204
            return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
205 206 207
        return false;
    }

208
    if (i < m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
209
        JSValue& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
210
        if (valueSlot) {
darin@apple.com's avatar
darin@apple.com committed
211
            slot.setValueSlot(&valueSlot);
darin's avatar
darin committed
212 213 214
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
215
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
216 217
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
darin@apple.com's avatar
darin@apple.com committed
218
                slot.setValueSlot(&it->second);
darin@apple.com's avatar
darin@apple.com committed
219 220
                return true;
            }
darin's avatar
darin committed
221 222 223
        }
    }

224
    return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
225 226
}

darin@apple.com's avatar
darin@apple.com committed
227
bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
darin's avatar
darin committed
228 229
{
    if (propertyName == exec->propertyNames().length) {
ggaren@apple.com's avatar
ggaren@apple.com committed
230
        slot.setValue(jsNumber(exec, length()));
darin's avatar
darin committed
231 232 233 234 235 236
        return true;
    }

    bool isArrayIndex;
    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
    if (isArrayIndex)
237
        return JSArray::getOwnPropertySlot(exec, i, slot);
darin's avatar
darin committed
238 239 240 241

    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
}

242 243 244 245 246 247 248 249 250 251 252 253
bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
{
    if (propertyName == exec->propertyNames().length) {
        descriptor.setDescriptor(jsNumber(exec, length()), DontDelete | DontEnum);
        return true;
    }
    
    bool isArrayIndex;
    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
    if (isArrayIndex) {
        if (i >= m_storage->m_length)
            return false;
254 255
        if (i < m_vectorLength) {
            JSValue& value = m_storage->m_vector[i];
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
            if (value) {
                descriptor.setDescriptor(value, 0);
                return true;
            }
        } else if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
            if (i >= MIN_SPARSE_ARRAY_INDEX) {
                SparseArrayValueMap::iterator it = map->find(i);
                if (it != map->end()) {
                    descriptor.setDescriptor(it->second, 0);
                    return true;
                }
            }
        }
    }
    return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor);
}

darin's avatar
darin committed
273
// ECMA 15.4.5.1
ggaren@apple.com's avatar
ggaren@apple.com committed
274
void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
darin's avatar
darin committed
275 276 277 278
{
    bool isArrayIndex;
    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
    if (isArrayIndex) {
darin@apple.com's avatar
darin@apple.com committed
279
        put(exec, i, value);
darin's avatar
darin committed
280 281 282 283
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
284 285
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
darin's avatar
darin committed
286 287 288 289 290 291 292
            throwError(exec, RangeError, "Invalid array length.");
            return;
        }
        setLength(newLength);
        return;
    }

weinig@apple.com's avatar
weinig@apple.com committed
293
    JSObject::put(exec, propertyName, value, slot);
darin's avatar
darin committed
294 295
}

ggaren@apple.com's avatar
ggaren@apple.com committed
296
void JSArray::put(ExecState* exec, unsigned i, JSValue value)
darin's avatar
darin committed
297
{
298 299
    checkConsistency();

ggaren@apple.com's avatar
ggaren@apple.com committed
300
    unsigned length = m_storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
301
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
302
        length = i + 1;
ggaren@apple.com's avatar
ggaren@apple.com committed
303
        m_storage->m_length = length;
darin's avatar
darin committed
304 305
    }

306
    if (i < m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
307
        JSValue& valueSlot = m_storage->m_vector[i];
308 309 310 311 312
        if (valueSlot) {
            valueSlot = value;
            checkConsistency();
            return;
        }
darin's avatar
darin committed
313
        valueSlot = value;
314
        ++m_storage->m_numValuesInVector;
315
        checkConsistency();
darin's avatar
darin committed
316 317 318
        return;
    }

319 320 321
    putSlowCase(exec, i, value);
}

ggaren@apple.com's avatar
ggaren@apple.com committed
322
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
323 324
{
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
325
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
326

barraclough@apple.com's avatar
barraclough@apple.com committed
327 328
    if (i >= MIN_SPARSE_ARRAY_INDEX) {
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
329 330
            PutPropertySlot slot;
            put(exec, Identifier::from(exec, i), value, slot);
331 332 333
            return;
        }

ap@webkit.org's avatar
ap@webkit.org committed
334
        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
335
        // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.
barraclough@apple.com's avatar
barraclough@apple.com committed
336
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
337 338 339 340
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
341 342 343 344 345 346 347 348 349 350 351 352

            pair<SparseArrayValueMap::iterator, bool> result = map->add(i, value);
            if (!result.second) { // pre-existing entry
                result.first->second = value;
                return;
            }

            size_t capacity = map->capacity();
            if (capacity != storage->reportedMapCapacity) {
                Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
                storage->reportedMapCapacity = capacity;
            }
darin's avatar
darin committed
353 354 355 356
            return;
        }
    }

ap@webkit.org's avatar
ap@webkit.org committed
357 358 359
    // We have decided that we'll put the new item into the vector.
    // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
    if (!map || map->isEmpty()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
360 361 362
        if (increaseVectorLength(i + 1)) {
            storage = m_storage;
            storage->m_vector[i] = value;
363
            ++storage->m_numValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
364 365 366
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
367 368 369
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
370 371
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
darin's avatar
darin committed
372
    unsigned newVectorLength = increasedVectorLength(i + 1);
373
    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
374
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
375
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
376
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
377 378
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
379 380
        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
        while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {
darin's avatar
darin committed
381
            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
382
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
383 384 385 386 387 388 389 390
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

391
    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
392 393 394
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
395

396
    unsigned vectorLength = m_vectorLength;
397

darin's avatar
darin committed
398 399
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
ggaren@apple.com's avatar
ggaren@apple.com committed
400
            storage->m_vector[j] = JSValue();
barraclough@apple.com's avatar
barraclough@apple.com committed
401
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
402
            map->remove(i);
darin's avatar
darin committed
403
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
404
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
ggaren@apple.com's avatar
ggaren@apple.com committed
405
            storage->m_vector[j] = JSValue();
barraclough@apple.com's avatar
barraclough@apple.com committed
406
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin@apple.com's avatar
darin@apple.com committed
407
            storage->m_vector[j] = map->take(j);
darin's avatar
darin committed
408 409 410 411
    }

    storage->m_vector[i] = value;

412
    m_vectorLength = newVectorLength;
darin's avatar
darin committed
413
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
414 415

    m_storage = storage;
416 417

    checkConsistency();
418 419

    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
420 421
}

darin@apple.com's avatar
darin@apple.com committed
422
bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
darin's avatar
darin committed
423 424 425 426 427 428 429 430 431 432 433 434
{
    bool isArrayIndex;
    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
    if (isArrayIndex)
        return deleteProperty(exec, i);

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

    return JSObject::deleteProperty(exec, propertyName);
}

darin@apple.com's avatar
darin@apple.com committed
435
bool JSArray::deleteProperty(ExecState* exec, unsigned i)
darin's avatar
darin committed
436
{
437 438
    checkConsistency();

darin's avatar
darin committed
439 440
    ArrayStorage* storage = m_storage;

441
    if (i < m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
442
        JSValue& valueSlot = storage->m_vector[i];
443 444 445 446
        if (!valueSlot) {
            checkConsistency();
            return false;
        }
ggaren@apple.com's avatar
ggaren@apple.com committed
447
        valueSlot = JSValue();
448
        --storage->m_numValuesInVector;
449
        checkConsistency();
450
        return true;
darin's avatar
darin committed
451 452 453
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
454
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
455 456 457
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
                map->remove(it);
458
                checkConsistency();
darin@apple.com's avatar
darin@apple.com committed
459 460
                return true;
            }
darin's avatar
darin committed
461 462 463
        }
    }

464 465
    checkConsistency();

barraclough@apple.com's avatar
barraclough@apple.com committed
466
    if (i > MAX_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
467
        return deleteProperty(exec, Identifier::from(exec, i));
darin's avatar
darin committed
468 469 470 471

    return false;
}

472
void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
473 474
{
    // FIXME: Filling PropertyNameArray with an identifier for every integer
475 476
    // is incredibly inefficient for large arrays. We need a different approach,
    // which almost certainly means a different structure for PropertyNameArray.
darin's avatar
darin committed
477 478 479

    ArrayStorage* storage = m_storage;

480
    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
darin's avatar
darin committed
481 482
    for (unsigned i = 0; i < usedVectorLength; ++i) {
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
483
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
484 485 486 487 488
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
        SparseArrayValueMap::iterator end = map->end();
        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
ap@webkit.org's avatar
ap@webkit.org committed
489
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
490
    }
491

492 493 494 495
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

    JSObject::getOwnPropertyNames(exec, propertyNames, mode);
darin's avatar
darin committed
496 497
}

darin@apple.com's avatar
darin@apple.com committed
498
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
499
{
ap@webkit.org's avatar
ap@webkit.org committed
500 501 502
    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
    // to the vector. Callers have to account for that, because they can do it more efficiently.

darin's avatar
darin committed
503 504
    ArrayStorage* storage = m_storage;

505
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
506
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
507
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
darin's avatar
darin committed
508 509
    unsigned newVectorLength = increasedVectorLength(newLength);

510
    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage))
ap@webkit.org's avatar
ap@webkit.org committed
511 512
        return false;

513
    m_vectorLength = newVectorLength;
darin's avatar
darin committed
514 515

    for (unsigned i = vectorLength; i < newVectorLength; ++i)
ggaren@apple.com's avatar
ggaren@apple.com committed
516
        storage->m_vector[i] = JSValue();
darin's avatar
darin committed
517 518

    m_storage = storage;
519 520 521

    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));

ap@webkit.org's avatar
ap@webkit.org committed
522
    return true;
darin's avatar
darin committed
523 524
}

darin@apple.com's avatar
darin@apple.com committed
525
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
526
{
527 528
    checkConsistency();

darin's avatar
darin committed
529 530
    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
531
    unsigned length = m_storage->m_length;
darin's avatar
darin committed
532 533

    if (newLength < length) {
534
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
535
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
ggaren@apple.com's avatar
ggaren@apple.com committed
536
            JSValue& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
537
            bool hadValue = valueSlot;
ggaren@apple.com's avatar
ggaren@apple.com committed
538
            valueSlot = JSValue();
darin's avatar
darin committed
539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
            SparseArrayValueMap::iterator end = copy.end();
            for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
                if (it->first >= newLength)
                    map->remove(it->first);
            }
            if (map->isEmpty()) {
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
555

ggaren@apple.com's avatar
ggaren@apple.com committed
556
    m_storage->m_length = newLength;
557 558

    checkConsistency();
darin's avatar
darin committed
559 560
}

ggaren@apple.com's avatar
ggaren@apple.com committed
561
JSValue JSArray::pop()
562 563 564 565 566 567 568 569 570
{
    checkConsistency();

    unsigned length = m_storage->m_length;
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
571
    JSValue result;
572

573
    if (length < m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
574
        JSValue& valueSlot = m_storage->m_vector[length];
575
        if (valueSlot) {
576
            --m_storage->m_numValuesInVector;
577 578 579
            result = valueSlot;
            valueSlot = JSValue();
        } else
580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602
            result = jsUndefined();
    } else {
        result = jsUndefined();
        if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
            SparseArrayValueMap::iterator it = map->find(length);
            if (it != map->end()) {
                result = it->second;
                map->remove(it);
                if (map->isEmpty()) {
                    delete map;
                    m_storage->m_sparseValueMap = 0;
                }
            }
        }
    }

    m_storage->m_length = length;

    checkConsistency();

    return result;
}

ggaren@apple.com's avatar
ggaren@apple.com committed
603
void JSArray::push(ExecState* exec, JSValue value)
604 605 606
{
    checkConsistency();

607
    if (m_storage->m_length < m_vectorLength) {
608
        m_storage->m_vector[m_storage->m_length] = value;
609 610
        ++m_storage->m_numValuesInVector;
        ++m_storage->m_length;
611 612 613 614 615 616 617 618 619
        checkConsistency();
        return;
    }

    if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
        SparseArrayValueMap* map = m_storage->m_sparseValueMap;
        if (!map || map->isEmpty()) {
            if (increaseVectorLength(m_storage->m_length + 1)) {
                m_storage->m_vector[m_storage->m_length] = value;
620 621
                ++m_storage->m_numValuesInVector;
                ++m_storage->m_length;
622 623 624 625 626 627 628 629 630 631 632 633
                checkConsistency();
                return;
            }
            checkConsistency();
            throwOutOfMemoryError(exec);
            return;
        }
    }

    putSlowCase(exec, m_storage->m_length++, value);
}

634
void JSArray::markChildren(MarkStack& markStack)
darin's avatar
darin committed
635
{
oliver@apple.com's avatar
oliver@apple.com committed
636
    markChildrenDirect(markStack);
darin's avatar
darin committed
637 638
}

ggaren@apple.com's avatar
ggaren@apple.com committed
639 640
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
641 642
    double da = static_cast<const JSValue*>(a)->uncheckedGetNumber();
    double db = static_cast<const JSValue*>(b)->uncheckedGetNumber();
ggaren@apple.com's avatar
ggaren@apple.com committed
643 644 645
    return (da > db) - (da < db);
}

ggaren@apple.com's avatar
ggaren@apple.com committed
646
typedef std::pair<JSValue, UString> ValueStringPair;
647

648 649
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
650 651
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
652
    return codePointCompare(va->second, vb->second);
653
}
darin's avatar
darin committed
654

ggaren@apple.com's avatar
ggaren@apple.com committed
655
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680
{
    unsigned lengthNotIncludingUndefined = compactForSorting();
    if (m_storage->m_sparseValueMap) {
        throwOutOfMemoryError(exec);
        return;
    }

    if (!lengthNotIncludingUndefined)
        return;
        
    bool allValuesAreNumbers = true;
    size_t size = m_storage->m_numValuesInVector;
    for (size_t i = 0; i < size; ++i) {
        if (!m_storage->m_vector[i].isNumber()) {
            allValuesAreNumbers = false;
            break;
        }
    }

    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.
ggaren@apple.com's avatar
ggaren@apple.com committed
681
    qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
ggaren@apple.com's avatar
ggaren@apple.com committed
682 683 684 685

    checkConsistency(SortConsistencyCheck);
}

darin@apple.com's avatar
darin@apple.com committed
686
void JSArray::sort(ExecState* exec)
darin's avatar
darin committed
687 688
{
    unsigned lengthNotIncludingUndefined = compactForSorting();
ap@webkit.org's avatar
ap@webkit.org committed
689
    if (m_storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
690
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
691 692
        return;
    }
darin's avatar
darin committed
693

ap@webkit.org's avatar
ap@webkit.org committed
694 695 696 697 698 699 700 701
    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.

ggaren@apple.com's avatar
ggaren@apple.com committed
702
    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
ap@webkit.org's avatar
ap@webkit.org committed
703
    if (!values.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
704
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
705 706
        return;
    }
darin's avatar
darin committed
707

ap@webkit.org's avatar
ap@webkit.org committed
708
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
ggaren@apple.com's avatar
ggaren@apple.com committed
709
        JSValue value = m_storage->m_vector[i];
weinig@apple.com's avatar
weinig@apple.com committed
710
        ASSERT(!value.isUndefined());
ap@webkit.org's avatar
ap@webkit.org committed
711 712 713
        values[i].first = value;
    }

714 715 716 717 718 719 720
    // FIXME: While calling these toString functions, the array could be mutated.
    // In that case, objects pointed to by values in this vector might get garbage-collected!

    // 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++)
weinig@apple.com's avatar
weinig@apple.com committed
721
        values[i].second = values[i].first.toString(exec);
722

ap@webkit.org's avatar
ap@webkit.org committed
723 724 725 726 727
    if (exec->hadException())
        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).
darin's avatar
darin committed
728

729
#if HAVE(MERGESORT)
ggaren@apple.com's avatar
ggaren@apple.com committed
730
    mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
731
#else
732 733
    // 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.
ggaren@apple.com's avatar
ggaren@apple.com committed
734
    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
735
#endif
darin's avatar
darin committed
736

737 738 739
    // FIXME: If the toString function changed the length of the array, this might be
    // modifying the vector incorrectly.

ap@webkit.org's avatar
ap@webkit.org committed
740 741
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
        m_storage->m_vector[i] = values[i].first;
742 743

    checkConsistency(SortConsistencyCheck);
darin's avatar
darin committed
744 745
}

ap@webkit.org's avatar
ap@webkit.org committed
746
struct AVLTreeNodeForArrayCompare {
ggaren@apple.com's avatar
ggaren@apple.com committed
747
    JSValue value;
ap@webkit.org's avatar
ap@webkit.org committed
748 749 750 751 752 753 754 755 756 757

    // 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
758
    typedef JSValue key;
ap@webkit.org's avatar
ap@webkit.org committed
759 760 761 762
    typedef int32_t size;

    Vector<AVLTreeNodeForArrayCompare> m_nodes;
    ExecState* m_exec;
ggaren@apple.com's avatar
ggaren@apple.com committed
763
    JSValue m_compareFunction;
darin@apple.com's avatar
darin@apple.com committed
764 765
    CallType m_compareCallType;
    const CallData* m_compareCallData;
ggaren@apple.com's avatar
ggaren@apple.com committed
766
    JSValue m_globalThisValue;
767
    OwnPtr<CachedCall> m_cachedCall;
ap@webkit.org's avatar
ap@webkit.org committed
768 769 770 771 772 773 774 775 776 777 778 779 780 781

    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
782
    {
ap@webkit.org's avatar
ap@webkit.org committed
783 784 785 786 787 788 789
        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
790 791
            else
                m_nodes[h].gt &= 0x7FFFFFFF;
ap@webkit.org's avatar
ap@webkit.org committed
792
        }
darin's avatar
darin committed
793 794
    }

ap@webkit.org's avatar
ap@webkit.org committed
795
    int compare_key_key(key va, key vb)
ap@webkit.org's avatar
ap@webkit.org committed
796
    {
weinig@apple.com's avatar
weinig@apple.com committed
797 798
        ASSERT(!va.isUndefined());
        ASSERT(!vb.isUndefined());
darin's avatar
darin committed
799

ggaren@apple.com's avatar
ggaren@apple.com committed
800 801 802
        if (m_exec->hadException())
            return 1;

803 804 805 806 807
        double compareResult;
        if (m_cachedCall) {
            m_cachedCall->setThis(m_globalThisValue);
            m_cachedCall->setArgument(0, va);
            m_cachedCall->setArgument(1, vb);
808
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
809
        } else {
810
            MarkedArgumentBuffer arguments;
811 812 813 814
            arguments.append(va);
            arguments.append(vb);
            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec);
        }
ap@webkit.org's avatar
ap@webkit.org committed
815
        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
816
    }
darin's avatar
darin committed
817

ap@webkit.org's avatar
ap@webkit.org committed
818 819 820 821
    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
822
};
darin's avatar
darin committed
823

ggaren@apple.com's avatar
ggaren@apple.com committed
824
void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
darin's avatar
darin committed
825
{
826 827 828 829
    checkConsistency();

    // FIXME: This ignores exceptions raised in the compare function or in toNumber.

ap@webkit.org's avatar
ap@webkit.org committed
830 831
    // The maximum tree depth is compiled in - but the caller is clearly up to no good
    // if a larger array is passed.
ggaren@apple.com's avatar
ggaren@apple.com committed
832 833
    ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
    if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
ap@webkit.org's avatar
ap@webkit.org committed
834 835
        return;

ggaren@apple.com's avatar
ggaren@apple.com committed
836
    if (!m_storage->m_length)
ap@webkit.org's avatar
ap@webkit.org committed
837 838
        return;

839
    unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
ap@webkit.org's avatar
ap@webkit.org committed
840 841 842 843

    AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
    tree.abstractor().m_exec = exec;
    tree.abstractor().m_compareFunction = compareFunction;
darin@apple.com's avatar
darin@apple.com committed
844 845
    tree.abstractor().m_compareCallType = callType;
    tree.abstractor().m_compareCallData = &callData;
ap@webkit.org's avatar
ap@webkit.org committed
846 847 848
    tree.abstractor().m_globalThisValue = exec->globalThisValue();
    tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));

849 850 851
    if (callType == CallTypeJS)
        tree.abstractor().m_cachedCall.set(new CachedCall(exec, asFunction(compareFunction), 2, exec->exceptionSlot()));

ap@webkit.org's avatar
ap@webkit.org committed
852
    if (!tree.abstractor().m_nodes.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
853
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
854 855 856
        return;
    }

857 858 859
    // 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.

ap@webkit.org's avatar
ap@webkit.org committed
860 861 862 863 864
    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) {
ggaren@apple.com's avatar
ggaren@apple.com committed
865
        JSValue v = m_storage->m_vector[numDefined];
weinig@apple.com's avatar
weinig@apple.com committed
866
        if (!v || v.isUndefined())
ap@webkit.org's avatar
ap@webkit.org committed
867 868 869 870 871
            break;
        tree.abstractor().m_nodes[numDefined].value = v;
        tree.insert(numDefined);
    }
    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
ggaren@apple.com's avatar
ggaren@apple.com committed
872
        JSValue v = m_storage->m_vector[i];
barraclough@apple.com's avatar
barraclough@apple.com committed
873
        if (v) {
weinig@apple.com's avatar
weinig@apple.com committed
874
            if (v.isUndefined())
ap@webkit.org's avatar
ap@webkit.org committed
875 876 877 878 879 880 881 882 883 884 885 886 887
                ++numUndefined;
            else {
                tree.abstractor().m_nodes[numDefined].value = v;
                tree.insert(numDefined);
                ++numDefined;
            }
        }
    }

    unsigned newUsedVectorLength = numDefined + numUndefined;

    if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
        newUsedVectorLength += map->size();
888
        if (newUsedVectorLength > m_vectorLength) {
barraclough@apple.com's avatar
barraclough@apple.com committed
889 890 891
            // Check that it is possible to allocate an array large enough to hold all the entries.
            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
                throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
892 893 894 895 896 897 898 899 900 901 902 903 904 905
                return;
            }
        }

        SparseArrayValueMap::iterator end = map->end();
        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
            tree.abstractor().m_nodes[numDefined].value = it->second;
            tree.insert(numDefined);
            ++numDefined;
        }

        delete map;
        m_storage->m_sparseValueMap = 0;
    }
darin's avatar
darin committed
906

ap@webkit.org's avatar
ap@webkit.org committed
907
    ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
darin's avatar
darin committed
908

909 910 911
    // FIXME: If the compare function changed the length of the array, the following might be
    // modifying the vector incorrectly.

ap@webkit.org's avatar
ap@webkit.org committed
912 913 914 915 916 917 918 919 920 921 922 923 924 925
    // Copy the values back into m_storage.
    AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
    iter.start_iter_least(tree);
    for (unsigned i = 0; i < numDefined; ++i) {
        m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
        ++iter;
    }

    // Put undefined values back in.
    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
        m_storage->m_vector[i] = jsUndefined();

    // Ensure that unused values in the vector are zeroed out.
    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
ggaren@apple.com's avatar
ggaren@apple.com committed
926
        m_storage->m_vector[i] = JSValue();
927 928 929 930

    m_storage->