JSArray.cpp 36 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

darin@apple.com's avatar
darin@apple.com committed
133 134
JSArray::JSArray(PassRefPtr<Structure> structure)
    : 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();
}

darin@apple.com's avatar
darin@apple.com committed
146
JSArray::JSArray(PassRefPtr<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
}

ggaren@apple.com's avatar
ggaren@apple.com committed
169
JSArray::JSArray(PassRefPtr<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 227 228
        }
    }

    return false;
}

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 244

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

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

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

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

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

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

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

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

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

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

ap@webkit.org's avatar
ap@webkit.org committed
306 307
        // 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
308
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
309 310 311 312 313
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
            map->set(i, value);
darin's avatar
darin committed
314 315 316 317
            return;
        }
    }

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

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

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

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

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

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

    storage->m_vector[i] = value;

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

    m_storage = storage;
380 381

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

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

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

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

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

428 429
    checkConsistency();

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

    return false;
}

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

    ArrayStorage* storage = m_storage;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    --length;

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

    if (m_fastAccessCutoff > length) {
ggaren@apple.com's avatar
ggaren@apple.com committed
536
        JSValue& valueSlot = m_storage->m_vector[length];
537 538
        result = valueSlot;
        ASSERT(result);
ggaren@apple.com's avatar
ggaren@apple.com committed
539
        valueSlot = JSValue();
540 541 542
        --m_storage->m_numValuesInVector;
        m_fastAccessCutoff = length;
    } else if (length < m_storage->m_vectorLength) {
ggaren@apple.com's avatar
ggaren@apple.com committed
543
        JSValue& valueSlot = m_storage->m_vector[length];
544
        result = valueSlot;
ggaren@apple.com's avatar
ggaren@apple.com committed
545
        valueSlot = JSValue();
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 571
        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
572
void JSArray::push(ExecState* exec, JSValue value)
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 603
{
    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);
}

604
void JSArray::markChildren(MarkStack& markStack)
darin's avatar
darin committed
605
{
oliver@apple.com's avatar
oliver@apple.com committed
606
    markChildrenDirect(markStack);
darin's avatar
darin committed
607 608
}

ggaren@apple.com's avatar
ggaren@apple.com committed
609 610
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
611 612
    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
613 614 615
    return (da > db) - (da < db);
}

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

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

ggaren@apple.com's avatar
ggaren@apple.com committed
625
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650
{
    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
651
    qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
ggaren@apple.com's avatar
ggaren@apple.com committed
652 653 654 655

    checkConsistency(SortConsistencyCheck);
}

darin@apple.com's avatar
darin@apple.com committed
656
void JSArray::sort(ExecState* exec)
darin's avatar
darin committed
657 658
{
    unsigned lengthNotIncludingUndefined = compactForSorting();
ap@webkit.org's avatar
ap@webkit.org committed
659
    if (m_storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
660
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
661 662
        return;
    }
darin's avatar
darin committed
663

ap@webkit.org's avatar
ap@webkit.org committed
664 665 666 667 668 669 670 671
    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
672
    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
ap@webkit.org's avatar
ap@webkit.org committed
673
    if (!values.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
674
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
675 676
        return;
    }
darin's avatar
darin committed
677

ap@webkit.org's avatar
ap@webkit.org committed
678
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
ggaren@apple.com's avatar
ggaren@apple.com committed
679
        JSValue value = m_storage->m_vector[i];
weinig@apple.com's avatar
weinig@apple.com committed
680
        ASSERT(!value.isUndefined());
ap@webkit.org's avatar
ap@webkit.org committed
681 682 683
        values[i].first = value;
    }

684 685 686 687 688 689 690
    // 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
691
        values[i].second = values[i].first.toString(exec);
692

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

699
#if HAVE(MERGESORT)
ggaren@apple.com's avatar
ggaren@apple.com committed
700
    mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
701
#else
702 703
    // 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
704
    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
705
#endif
darin's avatar
darin committed
706

707 708 709
    // 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
710 711
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
        m_storage->m_vector[i] = values[i].first;
712 713

    checkConsistency(SortConsistencyCheck);
darin's avatar
darin committed
714 715
}

ap@webkit.org's avatar
ap@webkit.org committed
716
struct AVLTreeNodeForArrayCompare {
ggaren@apple.com's avatar
ggaren@apple.com committed
717
    JSValue value;
ap@webkit.org's avatar
ap@webkit.org committed
718 719 720 721 722 723 724 725 726 727

    // 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
728
    typedef JSValue key;
ap@webkit.org's avatar
ap@webkit.org committed
729 730 731 732
    typedef int32_t size;

    Vector<AVLTreeNodeForArrayCompare> m_nodes;
    ExecState* m_exec;
ggaren@apple.com's avatar
ggaren@apple.com committed
733
    JSValue m_compareFunction;
darin@apple.com's avatar
darin@apple.com committed
734 735
    CallType m_compareCallType;
    const CallData* m_compareCallData;
ggaren@apple.com's avatar
ggaren@apple.com committed
736
    JSValue m_globalThisValue;
737
    OwnPtr<CachedCall> m_cachedCall;
ap@webkit.org's avatar
ap@webkit.org committed
738 739 740 741 742 743 744 745 746 747 748 749 750 751

    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
752
    {
ap@webkit.org's avatar
ap@webkit.org committed
753 754 755 756 757 758 759
        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
760 761
            else
                m_nodes[h].gt &= 0x7FFFFFFF;
ap@webkit.org's avatar
ap@webkit.org committed
762
        }
darin's avatar
darin committed
763 764
    }

ap@webkit.org's avatar
ap@webkit.org committed
765
    int compare_key_key(key va, key vb)
ap@webkit.org's avatar
ap@webkit.org committed
766
    {
weinig@apple.com's avatar
weinig@apple.com committed
767 768
        ASSERT(!va.isUndefined());
        ASSERT(!vb.isUndefined());
darin's avatar
darin committed
769

ggaren@apple.com's avatar
ggaren@apple.com committed
770 771 772
        if (m_exec->hadException())
            return 1;

773 774 775 776 777
        double compareResult;
        if (m_cachedCall) {
            m_cachedCall->setThis(m_globalThisValue);
            m_cachedCall->setArgument(0, va);
            m_cachedCall->setArgument(1, vb);
778
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame());
779
        } else {
780
            MarkedArgumentBuffer arguments;
781 782 783 784
            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
785
        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
786
    }
darin's avatar
darin committed
787

ap@webkit.org's avatar
ap@webkit.org committed
788 789 790 791
    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
792
};
darin's avatar
darin committed
793

ggaren@apple.com's avatar
ggaren@apple.com committed
794
void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
darin's avatar
darin committed
795
{
796 797 798 799
    checkConsistency();

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

ap@webkit.org's avatar
ap@webkit.org committed
800 801
    // 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
802 803
    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
804 805
        return;

ggaren@apple.com's avatar
ggaren@apple.com committed
806
    if (!m_storage->m_length)
ap@webkit.org's avatar
ap@webkit.org committed
807 808
        return;

ggaren@apple.com's avatar
ggaren@apple.com committed
809
    unsigned usedVectorLength = min(m_storage->m_length, m_storage->m_vectorLength);
ap@webkit.org's avatar
ap@webkit.org committed
810 811 812 813

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

819 820 821
    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
822
    if (!tree.abstractor().m_nodes.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
823
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
824 825 826
        return;
    }

827 828 829
    // 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
830 831 832 833 834
    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
835
        JSValue v = m_storage->m_vector[numDefined];
weinig@apple.com's avatar
weinig@apple.com committed
836
        if (!v || v.isUndefined())
ap@webkit.org's avatar
ap@webkit.org committed
837 838 839 840 841
            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
842
        JSValue v = m_storage->m_vector[i];
barraclough@apple.com's avatar
barraclough@apple.com committed
843
        if (v) {
weinig@apple.com's avatar
weinig@apple.com committed
844
            if (v.isUndefined())
ap@webkit.org's avatar
ap@webkit.org committed
845 846 847 848 849 850 851 852 853 854 855 856 857
                ++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();
858
        if (newUsedVectorLength > m_storage->m_vectorLength) {
barraclough@apple.com's avatar
barraclough@apple.com committed
859 860 861
            // Check that it is possible to allocate an array large enough to hold all the entries.
            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
                throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
862 863 864 865 866 867 868 869 870 871 872 873 874 875
                return;
            }
        }

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

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

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

879 880 881
    // FIXME: If the compare function changed the length of the array, the following might be
    // modifying the vector incorrectly.

ap@webkit.org's avatar
ap@webkit.org committed
882 883 884 885 886 887 888 889 890 891 892 893 894 895
    // Copy the values back into m_storage.
    AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
    iter.start_iter_least(tree);
    for (unsigned i = 0; i < numDefined; ++i) {
        m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
        ++iter;
    }

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

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

898
    m_fastAccessCutoff = newUsedVectorLength;
899 900 901
    m_storage->m_numValuesInVector = newUsedVectorLength;

    checkConsistency(SortConsistencyCheck);
darin's avatar
darin committed
902 903
}

904
void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
weinig@apple.com's avatar
weinig@apple.com committed
905 906 907 908 909 910 911 912 913
{
    unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
    unsigned i = 0;
    for (; i < fastAccessLength; ++i)
        args.append(getIndex(i));
    for (; i < m_storage->m_length; ++i)
        args.append(get(exec, i));
}

914 915 916 917 918 919 920 921 922 923 924 925 926
void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
{
    ASSERT(m_storage->m_length == maxSize);
    UNUSED_PARAM(maxSize);
    unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
    unsigned i = 0;
    for (; i < fastAccessLength; ++i)
        buffer[i] = getIndex(i);
    uint32_t size = m_storage->m_length;
    for (; i < size; ++i)
        buffer[i] = get(exec, i);
}

darin@apple.com's avatar
darin@apple.com committed
927
unsigned JSArray::compactForSorting()
darin's avatar
darin committed
928
{
929 930
    checkConsistency();

darin's avatar
darin committed
931 932
    ArrayStorage* storage = m_storage;

ggaren@apple.com's avatar
ggaren@apple.com committed
933
    unsigned usedVectorLength = min(m_storage->m_length, storage->m_vectorLength);
darin's avatar
darin committed
934 935 936 937 938

    unsigned numDefined = 0;
    unsigned numUndefined = 0;

    for (; numDefined < usedVectorLength; ++numDefined) {
ggaren@apple.com's avatar
ggaren@apple.com committed
939
        JSValue v = storage->m_vector[numDefined];
weinig@apple.com's avatar
weinig@apple.com committed
940
        if (!v || v.isUndefined())
darin's avatar
darin committed
941 942 943
            break;
    }
    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
ggaren@apple.com's avatar
ggaren@apple.com committed
944
        JSValue v = storage->m_vector[i];
barraclough@apple.com's avatar
barraclough@apple.com committed
945
        if (v) {
weinig@apple.com's avatar
weinig@apple.com committed
946
            if (v.isUndefined())
darin's avatar
darin committed
947 948 949 950 951 952 953 954