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

35 36
#define CHECK_ARRAY_CONSISTENCY 0

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

40
namespace JSC {
darin's avatar
darin committed
41

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

barraclough@apple.com's avatar
barraclough@apple.com committed
44 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
// 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
71 72 73
// 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
74 75 76 77 78

// 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)
79
// 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
80
#define MAX_ARRAY_INDEX 0xFFFFFFFEU
darin's avatar
darin committed
81 82

// Our policy for when to use a vector and when to use a sparse map.
barraclough@apple.com's avatar
barraclough@apple.com committed
83 84
// 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
85 86 87
// 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
88
const ClassInfo JSArray::info = {"Array", 0, 0, 0};
darin's avatar
darin committed
89 90 91

static inline size_t storageSize(unsigned vectorLength)
{
barraclough@apple.com's avatar
barraclough@apple.com committed
92 93 94 95
    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
96
    size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue));
barraclough@apple.com's avatar
barraclough@apple.com committed
97 98
    // 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
99
    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));
barraclough@apple.com's avatar
barraclough@apple.com committed
100 101

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

static inline unsigned increasedVectorLength(unsigned newLength)
{
barraclough@apple.com's avatar
barraclough@apple.com committed
106 107 108 109 110 111 112 113 114 115 116
    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
117 118 119 120 121 122 123
}

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

124 125
#if !CHECK_ARRAY_CONSISTENCY

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

#endif

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

    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
    m_storage->m_vectorLength = initialCapacity;
139 140

    m_fastAccessCutoff = 0;
weinig@apple.com's avatar
weinig@apple.com committed
141 142 143 144

    checkConsistency();
}

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

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

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

    m_fastAccessCutoff = 0;
162 163

    checkConsistency();
164 165

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

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

173 174 175 176 177
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
    m_storage->m_length = initialCapacity;
    m_storage->m_vectorLength = initialCapacity;
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 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
    m_fastAccessCutoff = initialCapacity;
185 186

    checkConsistency();
187 188

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

darin@apple.com's avatar
darin@apple.com committed
191
JSArray::~JSArray()
darin's avatar
darin committed
192
{
193 194
    checkConsistency(DestructorConsistencyCheck);

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

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

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

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

    return false;
}

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

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

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

// ECMA 15.4.5.1
ggaren@apple.com's avatar
ggaren@apple.com committed
244
void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
darin's avatar
darin committed
245 246 247 248
{
    bool isArrayIndex;
    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
    if (isArrayIndex) {
darin@apple.com's avatar
darin@apple.com committed
249
        put(exec, i, value);
darin's avatar
darin committed
250 251 252 253
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
254 255
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
darin's avatar
darin committed
256 257 258 259 260 261 262
            throwError(exec, RangeError, "Invalid array length.");
            return;
        }
        setLength(newLength);
        return;
    }

weinig@apple.com's avatar
weinig@apple.com committed
263
    JSObject::put(exec, propertyName, value, slot);
darin's avatar
darin committed
264 265
}

ggaren@apple.com's avatar
ggaren@apple.com committed
266
void JSArray::put(ExecState* exec, unsigned i, JSValue value)
darin's avatar
darin committed
267
{
268 269
    checkConsistency();

ggaren@apple.com's avatar
ggaren@apple.com committed
270
    unsigned length = m_storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
271
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
272
        length = i + 1;
ggaren@apple.com's avatar
ggaren@apple.com committed
273
        m_storage->m_length = length;
darin's avatar
darin committed
274 275
    }

276
    if (i < m_storage->m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
277
        JSValue& valueSlot = m_storage->m_vector[i];
278 279 280 281 282
        if (valueSlot) {
            valueSlot = value;
            checkConsistency();
            return;
        }
darin's avatar
darin committed
283
        valueSlot = value;
ggaren@apple.com's avatar
ggaren@apple.com committed
284 285
        if (++m_storage->m_numValuesInVector == m_storage->m_length)
            m_fastAccessCutoff = m_storage->m_length;
286
        checkConsistency();
darin's avatar
darin committed
287 288 289
        return;
    }

290 291 292
    putSlowCase(exec, i, value);
}

ggaren@apple.com's avatar
ggaren@apple.com committed
293
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
294 295
{
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
296
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
297

barraclough@apple.com's avatar
barraclough@apple.com committed
298 299
    if (i >= MIN_SPARSE_ARRAY_INDEX) {
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
300 301
            PutPropertySlot slot;
            put(exec, Identifier::from(exec, i), value, slot);
302 303 304
            return;
        }

ap@webkit.org's avatar
ap@webkit.org committed
305 306
        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
        // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
barraclough@apple.com's avatar
barraclough@apple.com committed
307
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
308 309 310 311 312
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
            map->set(i, value);
darin's avatar
darin committed
313 314 315 316
            return;
        }
    }

ap@webkit.org's avatar
ap@webkit.org committed
317 318 319
    // 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
320 321 322
        if (increaseVectorLength(i + 1)) {
            storage = m_storage;
            storage->m_vector[i] = value;
323 324
            if (++storage->m_numValuesInVector == storage->m_length)
                m_fastAccessCutoff = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
325 326 327
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
328 329 330
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
331 332
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
darin's avatar
darin committed
333
    unsigned newVectorLength = increasedVectorLength(i + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
334
    for (unsigned j = max(storage->m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
335
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
336
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
337
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
338 339
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
340 341
        // 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
342
            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
343
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
344 345 346 347 348 349 350 351
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

352
    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
353 354 355
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
356

357
    unsigned vectorLength = storage->m_vectorLength;
358 359 360

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

darin's avatar
darin committed
361 362
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
ggaren@apple.com's avatar
ggaren@apple.com committed
363
            storage->m_vector[j] = JSValue();
barraclough@apple.com's avatar
barraclough@apple.com committed
364
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
365
            map->remove(i);
darin's avatar
darin committed
366
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
367
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
ggaren@apple.com's avatar
ggaren@apple.com committed
368
            storage->m_vector[j] = JSValue();
barraclough@apple.com's avatar
barraclough@apple.com committed
369
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin@apple.com's avatar
darin@apple.com committed
370
            storage->m_vector[j] = map->take(j);
darin's avatar
darin committed
371 372 373 374
    }

    storage->m_vector[i] = value;

375
    storage->m_vectorLength = newVectorLength;
darin's avatar
darin committed
376
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
377 378

    m_storage = storage;
379 380

    checkConsistency();
darin's avatar
darin committed
381 382
}

darin@apple.com's avatar
darin@apple.com committed
383
bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
darin's avatar
darin committed
384 385 386 387 388 389 390 391 392 393 394 395
{
    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
396
bool JSArray::deleteProperty(ExecState* exec, unsigned i)
darin's avatar
darin committed
397
{
398 399
    checkConsistency();

darin's avatar
darin committed
400 401
    ArrayStorage* storage = m_storage;

402
    if (i < storage->m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
403
        JSValue& valueSlot = storage->m_vector[i];
404 405 406 407
        if (!valueSlot) {
            checkConsistency();
            return false;
        }
ggaren@apple.com's avatar
ggaren@apple.com committed
408
        valueSlot = JSValue();
409 410 411
        --storage->m_numValuesInVector;
        if (m_fastAccessCutoff > i)
            m_fastAccessCutoff = i;
412
        checkConsistency();
413
        return true;
darin's avatar
darin committed
414 415 416
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
417
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
418 419 420
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
                map->remove(it);
421
                checkConsistency();
darin@apple.com's avatar
darin@apple.com committed
422 423
                return true;
            }
darin's avatar
darin committed
424 425 426
        }
    }

427 428
    checkConsistency();

barraclough@apple.com's avatar
barraclough@apple.com committed
429
    if (i > MAX_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
430
        return deleteProperty(exec, Identifier::from(exec, i));
darin's avatar
darin committed
431 432 433 434

    return false;
}

darin@apple.com's avatar
darin@apple.com committed
435
void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
darin's avatar
darin committed
436 437
{
    // FIXME: Filling PropertyNameArray with an identifier for every integer
438 439
    // 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
440 441 442

    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
443
    unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
darin's avatar
darin committed
444 445
    for (unsigned i = 0; i < usedVectorLength; ++i) {
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
446
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
447 448 449 450 451
    }

    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
452
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
453
    }
454

darin's avatar
darin committed
455 456 457
    JSObject::getPropertyNames(exec, propertyNames);
}

darin@apple.com's avatar
darin@apple.com committed
458
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
459
{
ap@webkit.org's avatar
ap@webkit.org committed
460 461 462
    // 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
463 464
    ArrayStorage* storage = m_storage;

465
    unsigned vectorLength = storage->m_vectorLength;
darin's avatar
darin committed
466
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
467
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
darin's avatar
darin committed
468 469
    unsigned newVectorLength = increasedVectorLength(newLength);

470
    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage))
ap@webkit.org's avatar
ap@webkit.org committed
471 472
        return false;

473
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
474
    storage->m_vectorLength = newVectorLength;
darin's avatar
darin committed
475 476

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

    m_storage = storage;
ap@webkit.org's avatar
ap@webkit.org committed
480
    return true;
darin's avatar
darin committed
481 482
}

darin@apple.com's avatar
darin@apple.com committed
483
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
484
{
485 486
    checkConsistency();

darin's avatar
darin committed
487 488
    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
489
    unsigned length = m_storage->m_length;
darin's avatar
darin committed
490 491

    if (newLength < length) {
492 493 494 495
        if (m_fastAccessCutoff > newLength)
            m_fastAccessCutoff = newLength;

        unsigned usedVectorLength = min(length, storage->m_vectorLength);
darin's avatar
darin committed
496
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
ggaren@apple.com's avatar
ggaren@apple.com committed
497
            JSValue& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
498
            bool hadValue = valueSlot;
ggaren@apple.com's avatar
ggaren@apple.com committed
499
            valueSlot = JSValue();
darin's avatar
darin committed
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515
            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
516

ggaren@apple.com's avatar
ggaren@apple.com committed
517
    m_storage->m_length = newLength;
518 519

    checkConsistency();
darin's avatar
darin committed
520 521
}

ggaren@apple.com's avatar
ggaren@apple.com committed
522
JSValue JSArray::pop()
523 524 525 526 527 528 529 530 531
{
    checkConsistency();

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

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
532
    JSValue result;
533 534

    if (m_fastAccessCutoff > length) {
ggaren@apple.com's avatar
ggaren@apple.com committed
535
        JSValue& valueSlot = m_storage->m_vector[length];
536 537
        result = valueSlot;
        ASSERT(result);
ggaren@apple.com's avatar
ggaren@apple.com committed
538
        valueSlot = JSValue();
539 540 541
        --m_storage->m_numValuesInVector;
        m_fastAccessCutoff = length;
    } else if (length < m_storage->m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
542
        JSValue& valueSlot = m_storage->m_vector[length];
543
        result = valueSlot;
ggaren@apple.com's avatar
ggaren@apple.com committed
544
        valueSlot = JSValue();
545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570
        if (result)
            --m_storage->m_numValuesInVector;
        else
            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
571
void JSArray::push(ExecState* exec, JSValue value)
572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602
{
    checkConsistency();

    if (m_storage->m_length < m_storage->m_vectorLength) {
        ASSERT(!m_storage->m_vector[m_storage->m_length]);
        m_storage->m_vector[m_storage->m_length] = value;
        if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
            m_fastAccessCutoff = m_storage->m_length;
        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;
                if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
                    m_fastAccessCutoff = m_storage->m_length;
                checkConsistency();
                return;
            }
            checkConsistency();
            throwOutOfMemoryError(exec);
            return;
        }
    }

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

603
void JSArray::markChildren(MarkStack& markStack)
darin's avatar
darin committed
604
{
605
    JSObject::markChildren(markStack);
darin's avatar
darin committed
606 607 608

    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
609
    unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
610
    markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues);
darin's avatar
darin committed
611 612

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
darin's avatar
darin committed
613
        SparseArrayValueMap::iterator end = map->end();
614 615
        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
            markStack.append(it->second);
darin's avatar
darin committed
616 617 618
    }
}

ggaren@apple.com's avatar
ggaren@apple.com committed
619 620
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
621 622
    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
623 624 625
    return (da > db) - (da < db);
}

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

628 629
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
630 631
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
632 633
    return compare(va->second, vb->second);
}
darin's avatar
darin committed
634

ggaren@apple.com's avatar
ggaren@apple.com committed
635
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660
{
    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
661
    qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
ggaren@apple.com's avatar
ggaren@apple.com committed
662 663 664 665

    checkConsistency(SortConsistencyCheck);
}

darin@apple.com's avatar
darin@apple.com committed
666
void JSArray::sort(ExecState* exec)
darin's avatar
darin committed
667 668
{
    unsigned lengthNotIncludingUndefined = compactForSorting();
ap@webkit.org's avatar
ap@webkit.org committed
669
    if (m_storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
670
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
671 672
        return;
    }
darin's avatar
darin committed
673

ap@webkit.org's avatar
ap@webkit.org committed
674 675 676 677 678 679 680 681
    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
682
    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
ap@webkit.org's avatar
ap@webkit.org committed
683
    if (!values.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
684
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
685 686
        return;
    }
darin's avatar
darin committed
687

ap@webkit.org's avatar
ap@webkit.org committed
688
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
ggaren@apple.com's avatar
ggaren@apple.com committed
689
        JSValue value = m_storage->m_vector[i];
weinig@apple.com's avatar
weinig@apple.com committed
690
        ASSERT(!value.isUndefined());
ap@webkit.org's avatar
ap@webkit.org committed
691 692 693
        values[i].first = value;
    }

694 695 696 697 698 699 700
    // 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
701
        values[i].second = values[i].first.toString(exec);
702

ap@webkit.org's avatar
ap@webkit.org committed
703 704 705 706 707
    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
708

709
#if HAVE(MERGESORT)
ggaren@apple.com's avatar
ggaren@apple.com committed
710
    mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
711
#else
712 713
    // 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
714
    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
715
#endif
darin's avatar
darin committed
716

717 718 719
    // 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
720 721
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
        m_storage->m_vector[i] = values[i].first;
722 723

    checkConsistency(SortConsistencyCheck);
darin's avatar
darin committed
724 725
}

ap@webkit.org's avatar
ap@webkit.org committed
726
struct AVLTreeNodeForArrayCompare {
ggaren@apple.com's avatar
ggaren@apple.com committed
727
    JSValue value;
ap@webkit.org's avatar
ap@webkit.org committed
728 729 730 731 732 733 734 735 736 737

    // 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
738
    typedef JSValue key;
ap@webkit.org's avatar
ap@webkit.org committed
739 740 741 742
    typedef int32_t size;

    Vector<AVLTreeNodeForArrayCompare> m_nodes;
    ExecState* m_exec;
ggaren@apple.com's avatar
ggaren@apple.com committed
743
    JSValue m_compareFunction;
darin@apple.com's avatar
darin@apple.com committed
744 745
    CallType m_compareCallType;
    const CallData* m_compareCallData;
ggaren@apple.com's avatar
ggaren@apple.com committed
746
    JSValue m_globalThisValue;
747
    OwnPtr<CachedCall> m_cachedCall;
ap@webkit.org's avatar
ap@webkit.org committed
748 749 750 751 752 753 754 755 756 757 758 759 760 761

    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
762
    {
ap@webkit.org's avatar
ap@webkit.org committed
763 764 765 766 767 768 769
        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
770 771
            else
                m_nodes[h].gt &= 0x7FFFFFFF;
ap@webkit.org's avatar
ap@webkit.org committed
772
        }
darin's avatar
darin committed
773 774
    }

ap@webkit.org's avatar
ap@webkit.org committed
775
    int compare_key_key(key va, key vb)
ap@webkit.org's avatar
ap@webkit.org committed
776
    {
weinig@apple.com's avatar
weinig@apple.com committed
777 778
        ASSERT(!va.isUndefined());
        ASSERT(!vb.isUndefined());
darin's avatar
darin committed
779

ggaren@apple.com's avatar
ggaren@apple.com committed
780 781 782
        if (m_exec->hadException())
            return 1;

783 784 785 786 787
        double compareResult;
        if (m_cachedCall) {
            m_cachedCall->setThis(m_globalThisValue);
            m_cachedCall->setArgument(0, va);
            m_cachedCall->setArgument(1, vb);
788
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame());
789
        } else {
790
            MarkedArgumentBuffer arguments;
791 792 793 794
            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
795
        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
796
    }
darin's avatar
darin committed
797

ap@webkit.org's avatar
ap@webkit.org committed
798 799 800 801
    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
802
};
darin's avatar
darin committed
803

ggaren@apple.com's avatar
ggaren@apple.com committed
804
void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
darin's avatar
darin committed
805
{
806 807 808 809
    checkConsistency();

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

ap@webkit.org's avatar
ap@webkit.org committed
810 811
    // 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
812 813
    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
814 815
        return;

ggaren@apple.com's avatar
ggaren@apple.com committed
816
    if (!m_storage->m_length)
ap@webkit.org's avatar
ap@webkit.org committed
817 818
        return;

ggaren@apple.com's avatar
ggaren@apple.com committed
819
    unsigned usedVectorLength = min(m_storage->m_length, m_storage->m_vectorLength);
ap@webkit.org's avatar
ap@webkit.org committed
820 821 822 823

    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
824 825
    tree.abstractor().m_compareCallType = callType;
    tree.abstractor().m_compareCallData = &callData;
ap@webkit.org's avatar
ap@webkit.org committed
826 827 828
    tree.abstractor().m_globalThisValue = exec->globalThisValue();
    tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));

829 830 831
    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
832
    if (!tree.abstractor().m_nodes.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
833
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
834 835 836
        return;
    }

837 838 839
    // 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
840 841 842 843 844
    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
845
        JSValue v = m_storage->m_vector[numDefined];
weinig@apple.com's avatar
weinig@apple.com committed
846
        if (!v || v.isUndefined())
ap@webkit.org's avatar
ap@webkit.org committed
847 848 849 850 851
            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
852
        JSValue v = m_storage->m_vector[i];
barraclough@apple.com's avatar
barraclough@apple.com committed
853
        if (v) {
weinig@apple.com's avatar
weinig@apple.com committed
854
            if (v.isUndefined())
ap@webkit.org's avatar
ap@webkit.org committed
855 856 857 858 859 860 861 862 863 864 865 866 867
                ++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();
868
        if (newUsedVectorLength > m_storage->m_vectorLength) {
barraclough@apple.com's avatar