JSArray.cpp 36.5 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 139
{
    unsigned initialCapacity = 0;

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

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

    checkConsistency();
}

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

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

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

    m_fastAccessCutoff = 0;
163 164

    checkConsistency();
165 166

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

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

174 175 176 177 178
    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
179

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

185
    m_fastAccessCutoff = initialCapacity;
186 187

    checkConsistency();
188 189

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

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

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

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

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

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

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

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

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

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

244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274
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;
        if (i < m_storage->m_vectorLength) {
            JSValue value = m_storage->m_vector[i];
            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
275
// ECMA 15.4.5.1
ggaren@apple.com's avatar
ggaren@apple.com committed
276
void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
darin's avatar
darin committed
277 278 279 280
{
    bool isArrayIndex;
    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
    if (isArrayIndex) {
darin@apple.com's avatar
darin@apple.com committed
281
        put(exec, i, value);
darin's avatar
darin committed
282 283 284 285
        return;
    }

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

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

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

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

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

322 323 324
    putSlowCase(exec, i, value);
}

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

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

ap@webkit.org's avatar
ap@webkit.org committed
337 338
        // 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
339
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
340 341 342 343 344
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
            map->set(i, value);
darin's avatar
darin committed
345 346 347 348
            return;
        }
    }

ap@webkit.org's avatar
ap@webkit.org committed
349 350 351
    // 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
352 353 354
        if (increaseVectorLength(i + 1)) {
            storage = m_storage;
            storage->m_vector[i] = value;
355 356
            if (++storage->m_numValuesInVector == storage->m_length)
                m_fastAccessCutoff = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
357 358 359
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
360 361 362
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
363 364
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
darin's avatar
darin committed
365
    unsigned newVectorLength = increasedVectorLength(i + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
366
    for (unsigned j = max(storage->m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
367
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
368
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
369
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
370 371
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
372 373
        // 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
374
            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
375
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
376 377 378 379 380 381 382 383
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

384
    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
385 386 387
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
388

389
    unsigned vectorLength = storage->m_vectorLength;
390 391 392

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

darin's avatar
darin committed
393 394
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
ggaren@apple.com's avatar
ggaren@apple.com committed
395
            storage->m_vector[j] = JSValue();
barraclough@apple.com's avatar
barraclough@apple.com committed
396
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
397
            map->remove(i);
darin's avatar
darin committed
398
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
399
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++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
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin@apple.com's avatar
darin@apple.com committed
402
            storage->m_vector[j] = map->take(j);
darin's avatar
darin committed
403 404 405 406
    }

    storage->m_vector[i] = value;

407
    storage->m_vectorLength = newVectorLength;
darin's avatar
darin committed
408
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
409 410

    m_storage = storage;
411 412

    checkConsistency();
darin's avatar
darin committed
413 414
}

darin@apple.com's avatar
darin@apple.com committed
415
bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
darin's avatar
darin committed
416 417 418 419 420 421 422 423 424 425 426 427
{
    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
428
bool JSArray::deleteProperty(ExecState* exec, unsigned i)
darin's avatar
darin committed
429
{
430 431
    checkConsistency();

darin's avatar
darin committed
432 433
    ArrayStorage* storage = m_storage;

434
    if (i < storage->m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
435
        JSValue& valueSlot = storage->m_vector[i];
436 437 438 439
        if (!valueSlot) {
            checkConsistency();
            return false;
        }
ggaren@apple.com's avatar
ggaren@apple.com committed
440
        valueSlot = JSValue();
441 442 443
        --storage->m_numValuesInVector;
        if (m_fastAccessCutoff > i)
            m_fastAccessCutoff = i;
444
        checkConsistency();
445
        return true;
darin's avatar
darin committed
446 447 448
    }

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

459 460
    checkConsistency();

barraclough@apple.com's avatar
barraclough@apple.com committed
461
    if (i > MAX_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
462
        return deleteProperty(exec, Identifier::from(exec, i));
darin's avatar
darin committed
463 464 465 466

    return false;
}

oliver@apple.com's avatar
oliver@apple.com committed
467
void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
darin's avatar
darin committed
468 469
{
    // FIXME: Filling PropertyNameArray with an identifier for every integer
470 471
    // 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
472 473 474

    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
475
    unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
darin's avatar
darin committed
476 477
    for (unsigned i = 0; i < usedVectorLength; ++i) {
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
478
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
479 480 481 482 483
    }

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

oliver@apple.com's avatar
oliver@apple.com committed
487
    JSObject::getOwnPropertyNames(exec, propertyNames);
darin's avatar
darin committed
488 489
}

darin@apple.com's avatar
darin@apple.com committed
490
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
491
{
ap@webkit.org's avatar
ap@webkit.org committed
492 493 494
    // 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
495 496
    ArrayStorage* storage = m_storage;

497
    unsigned vectorLength = storage->m_vectorLength;
darin's avatar
darin committed
498
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
499
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
darin's avatar
darin committed
500 501
    unsigned newVectorLength = increasedVectorLength(newLength);

502
    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage))
ap@webkit.org's avatar
ap@webkit.org committed
503 504
        return false;

505
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
506
    storage->m_vectorLength = newVectorLength;
darin's avatar
darin committed
507 508

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

    m_storage = storage;
ap@webkit.org's avatar
ap@webkit.org committed
512
    return true;
darin's avatar
darin committed
513 514
}

darin@apple.com's avatar
darin@apple.com committed
515
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
516
{
517 518
    checkConsistency();

darin's avatar
darin committed
519 520
    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
521
    unsigned length = m_storage->m_length;
darin's avatar
darin committed
522 523

    if (newLength < length) {
524 525 526 527
        if (m_fastAccessCutoff > newLength)
            m_fastAccessCutoff = newLength;

        unsigned usedVectorLength = min(length, storage->m_vectorLength);
darin's avatar
darin committed
528
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
ggaren@apple.com's avatar
ggaren@apple.com committed
529
            JSValue& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
530
            bool hadValue = valueSlot;
ggaren@apple.com's avatar
ggaren@apple.com committed
531
            valueSlot = JSValue();
darin's avatar
darin committed
532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547
            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
548

ggaren@apple.com's avatar
ggaren@apple.com committed
549
    m_storage->m_length = newLength;
550 551

    checkConsistency();
darin's avatar
darin committed
552 553
}

ggaren@apple.com's avatar
ggaren@apple.com committed
554
JSValue JSArray::pop()
555 556 557 558 559 560 561 562 563
{
    checkConsistency();

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

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
564
    JSValue result;
565 566

    if (m_fastAccessCutoff > length) {
ggaren@apple.com's avatar
ggaren@apple.com committed
567
        JSValue& valueSlot = m_storage->m_vector[length];
568 569
        result = valueSlot;
        ASSERT(result);
ggaren@apple.com's avatar
ggaren@apple.com committed
570
        valueSlot = JSValue();
571 572 573
        --m_storage->m_numValuesInVector;
        m_fastAccessCutoff = length;
    } else if (length < m_storage->m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
574
        JSValue& valueSlot = m_storage->m_vector[length];
575
        result = valueSlot;
ggaren@apple.com's avatar
ggaren@apple.com committed
576
        valueSlot = JSValue();
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
        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
603
void JSArray::push(ExecState* exec, JSValue value)
604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634
{
    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);
}

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

ggaren@apple.com's avatar
ggaren@apple.com committed
640 641
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
642 643
    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
644 645 646
    return (da > db) - (da < db);
}

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

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

ggaren@apple.com's avatar
ggaren@apple.com committed
656
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681
{
    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
682
    qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
ggaren@apple.com's avatar
ggaren@apple.com committed
683 684 685 686

    checkConsistency(SortConsistencyCheck);
}

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

ap@webkit.org's avatar
ap@webkit.org committed
695 696 697 698 699 700 701 702
    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
703
    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
ap@webkit.org's avatar
ap@webkit.org committed
704
    if (!values.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
705
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
706 707
        return;
    }
darin's avatar
darin committed
708

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

715 716 717 718 719 720 721
    // 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
722
        values[i].second = values[i].first.toString(exec);
723

ap@webkit.org's avatar
ap@webkit.org committed
724 725 726 727 728
    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
729

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

738 739 740
    // 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
741 742
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
        m_storage->m_vector[i] = values[i].first;
743 744

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

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

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

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

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

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

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

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

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

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

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

ap@webkit.org's avatar
ap@webkit.org committed
831 832
    // 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
833 834
    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
835 836
        return;

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

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

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

850 851 852
    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
853
    if (!tree.abstractor().m_nodes.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
854
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
855 856 857
        return;
    }

858 859 860
    // 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
861 862 863 864 865
    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
866
        JSValue v = m_storage->m_vector[numDefined];
weinig@apple.com's avatar
weinig@apple.com committed
867
        if (!v || v.isUndefined())
ap@webkit.org's avatar
ap@webkit.org committed
868 869 870 871 872
            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
873
        JSValue v = m_storage->m_vector[i];
barraclough@apple.com's avatar
barraclough@apple.com committed
874