/*

 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)

 *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.

 *  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"

#include "JSArray.h"

#include "ArrayPrototype.h"

#include "CachedCall.h"

#include "Error.h"

#include "Executable.h"

#include "PropertyNameArray.h"

#include <wtf/AVLTree.h>

#include <wtf/Assertions.h>

#include <wtf/OwnPtr.h>

#include <Operations.h>

using namespace std;

using namespace WTF;

namespace JSC {

ASSERT_CLASS_FITS_IN_CELL(JSArray);

// 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

// 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))

// 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)

// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.

#define MAX_ARRAY_INDEX 0xFFFFFFFEU

// Our policy for when to use a vector and when to use a sparse map.

// 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

// as long as it is 1/8 full. If more sparse than that, we use a map.

static const unsigned minDensityMultiplier = 8;

const ClassInfo JSArray::info = {"Array", 0, 0, 0};

static inline size_t storageSize(unsigned vectorLength)

{

    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.

    size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue));

    // Assertion to detect integer overflow in previous calculation (should not be possible, provided that

    // MAX_STORAGE_VECTOR_LENGTH is correctly defined).

    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));

    return size;

}

static inline unsigned increasedVectorLength(unsigned newLength)

{

    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);

}

static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)

{

    return length / minDensityMultiplier <= numValues;

}

#if !CHECK_ARRAY_CONSISTENCY

inline void JSArray::checkConsistency(ConsistencyCheckType)

{

}

#endif

JSArray::JSArray(NonNullPassRefPtr<Structure> structure)

    : JSObject(structure)

{

    unsigned initialCapacity = 0;

    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));

    m_vectorLength = initialCapacity;

    checkConsistency();

}

JSArray::JSArray(NonNullPassRefPtr<Structure> structure, unsigned initialLength, ArrayCreationMode creationMode)

    : JSObject(structure)

{

    unsigned initialCapacity;

    if (creationMode == CreateCompact)

        initialCapacity = initialLength;

    else

        initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);

    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));

    m_vectorLength = initialCapacity;

    m_storage->m_sparseValueMap = 0;

    m_storage->subclassData = 0;

    m_storage->reportedMapCapacity = 0;

    if (creationMode == CreateCompact) {

#if CHECK_ARRAY_CONSISTENCY

        m_storage->m_inCompactInitialization = !!initialCapacity;

#endif

        m_storage->m_length = 0;

        m_storage->m_numValuesInVector = initialCapacity;

    } else {

#if CHECK_ARRAY_CONSISTENCY

        m_storage->m_inCompactInitialization = false;

#endif

        m_storage->m_length = initialLength;

        m_storage->m_numValuesInVector = 0;

        JSValue* vector = m_storage->m_vector;

        for (size_t i = 0; i < initialCapacity; ++i)

            vector[i] = JSValue();

    }

    checkConsistency();

    Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));

}

JSArray::JSArray(NonNullPassRefPtr<Structure> structure, const ArgList& list)

    : JSObject(structure)

{

    unsigned initialCapacity = list.size();

    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));

    m_storage->m_length = initialCapacity;

    m_vectorLength = initialCapacity;

    m_storage->m_numValuesInVector = initialCapacity;

    m_storage->m_sparseValueMap = 0;

    m_storage->subclassData = 0;

    m_storage->reportedMapCapacity = 0;

#if CHECK_ARRAY_CONSISTENCY

    m_storage->m_inCompactInitialization = false;

#endif

    size_t i = 0;

    ArgList::const_iterator end = list.end();

    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)

        m_storage->m_vector[i] = *it;

    checkConsistency();

    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));

}

JSArray::~JSArray()

{

    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);

    checkConsistency(DestructorConsistencyCheck);

    delete m_storage->m_sparseValueMap;

    fastFree(m_storage);

}

bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)

{

    ArrayStorage* storage = m_storage;

    if (i >= storage->m_length) {

        if (i > MAX_ARRAY_INDEX)

            return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);

        return false;

    }

    if (i < m_vectorLength) {

        JSValue& valueSlot = storage->m_vector[i];

        if (valueSlot) {

            slot.setValueSlot(&valueSlot);

            return true;

        }

    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {

        if (i >= MIN_SPARSE_ARRAY_INDEX) {

            SparseArrayValueMap::iterator it = map->find(i);

            if (it != map->end()) {

                slot.setValueSlot(&it->second);

                return true;

            }

        }

    }

    return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot);

}

bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)

{

    if (propertyName == exec->propertyNames().length) {

        slot.setValue(jsNumber(exec, length()));

        return true;

    }

    bool isArrayIndex;

    unsigned i = propertyName.toArrayIndex(&isArrayIndex);

    if (isArrayIndex)

        return JSArray::getOwnPropertySlot(exec, i, slot);

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

}

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_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);

}

// ECMA 15.4.5.1

void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)

{

    bool isArrayIndex;

    unsigned i = propertyName.toArrayIndex(&isArrayIndex);

    if (isArrayIndex) {

        put(exec, i, value);

        return;

    }

    if (propertyName == exec->propertyNames().length) {

        unsigned newLength = value.toUInt32(exec);

        if (value.toNumber(exec) != static_cast<double>(newLength)) {

            throwError(exec, createRangeError(exec, "Invalid array length."));

            return;

        }

        setLength(newLength);

        return;

    }

    JSObject::put(exec, propertyName, value, slot);

}

void JSArray::put(ExecState* exec, unsigned i, JSValue value)

{

    checkConsistency();

    unsigned length = m_storage->m_length;

    if (i >= length && i <= MAX_ARRAY_INDEX) {

        length = i + 1;

        m_storage->m_length = length;

    }

    if (i < m_vectorLength) {

        JSValue& valueSlot = m_storage->m_vector[i];

        if (valueSlot) {

            valueSlot = value;

            checkConsistency();

            return;

        }

        valueSlot = value;

        ++m_storage->m_numValuesInVector;

        checkConsistency();

        return;

    }

    putSlowCase(exec, i, value);

}

NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)

{

    ArrayStorage* storage = m_storage;

    SparseArrayValueMap* map = storage->m_sparseValueMap;

    if (i >= MIN_SPARSE_ARRAY_INDEX) {

        if (i > MAX_ARRAY_INDEX) {

            PutPropertySlot slot;

            put(exec, Identifier::from(exec, i), value, slot);

            return;

        }

        // 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 MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.

        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {

            if (!map) {

                map = new SparseArrayValueMap;

                storage->m_sparseValueMap = map;

            }

            pair<SparseArrayValueMap::iterator, bool> result = map->add(i, value);

            if (!result.second) { // pre-existing entry

                result.first->second = value;

                return;

            }

            size_t capacity = map->capacity();

            if (capacity != storage->reportedMapCapacity) {

                Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));

                storage->reportedMapCapacity = capacity;

            }

            return;

        }

    }

    // 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()) {

        if (increaseVectorLength(i + 1)) {

            storage = m_storage;

            storage->m_vector[i] = value;

            ++storage->m_numValuesInVector;

            checkConsistency();

        } else

            throwOutOfMemoryError(exec);

        return;

    }

    // Decide how many values it would be best to move from the map.

    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;

    unsigned newVectorLength = increasedVectorLength(i + 1);

    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)

        newNumValuesInVector += map->contains(j);

    if (i >= MIN_SPARSE_ARRAY_INDEX)

        newNumValuesInVector -= map->contains(i);

    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {

        unsigned proposedNewNumValuesInVector = newNumValuesInVector;

        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.

        while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {

            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);

            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)

                proposedNewNumValuesInVector += map->contains(j);

            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))

                break;

            newVectorLength = proposedNewVectorLength;

            newNumValuesInVector = proposedNewNumValuesInVector;

        }

    }

    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) {

        throwOutOfMemoryError(exec);

        return;

    }

    unsigned vectorLength = m_vectorLength;

    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {

        for (unsigned j = vectorLength; j < newVectorLength; ++j)

            storage->m_vector[j] = JSValue();

        if (i > MIN_SPARSE_ARRAY_INDEX)

            map->remove(i);

    } else {

        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)

            storage->m_vector[j] = JSValue();

        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)

            storage->m_vector[j] = map->take(j);

    }

    storage->m_vector[i] = value;

    m_vectorLength = newVectorLength;

    storage->m_numValuesInVector = newNumValuesInVector;

    m_storage = storage;

    checkConsistency();

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

}

bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)

{

    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);

}

bool JSArray::deleteProperty(ExecState* exec, unsigned i)

{

    checkConsistency();

    ArrayStorage* storage = m_storage;

    if (i < m_vectorLength) {

        JSValue& valueSlot = storage->m_vector[i];

        if (!valueSlot) {

            checkConsistency();

            return false;

        }

        valueSlot = JSValue();

        --storage->m_numValuesInVector;

        checkConsistency();

        return true;

    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {

        if (i >= MIN_SPARSE_ARRAY_INDEX) {

            SparseArrayValueMap::iterator it = map->find(i);

            if (it != map->end()) {

                map->remove(it);

                checkConsistency();

                return true;

            }

        }

    }

    checkConsistency();

    if (i > MAX_ARRAY_INDEX)

        return deleteProperty(exec, Identifier::from(exec, i));

    return false;

}

void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)

{

    // FIXME: Filling PropertyNameArray with an identifier for every integer

    // is incredibly inefficient for large arrays. We need a different approach,

    // which almost certainly means a different structure for PropertyNameArray.

    ArrayStorage* storage = m_storage;

    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);

    for (unsigned i = 0; i < usedVectorLength; ++i) {

        if (storage->m_vector[i])

            propertyNames.add(Identifier::from(exec, i));

    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {

        SparseArrayValueMap::iterator end = map->end();

        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)

            propertyNames.add(Identifier::from(exec, it->first));

    }

    if (mode == IncludeDontEnumProperties)

        propertyNames.add(exec->propertyNames().length);

    JSObject::getOwnPropertyNames(exec, propertyNames, mode);

}

bool JSArray::increaseVectorLength(unsigned newLength)

{

    // 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.

    ArrayStorage* storage = m_storage;

    unsigned vectorLength = m_vectorLength;

    ASSERT(newLength > vectorLength);

    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);

    unsigned newVectorLength = increasedVectorLength(newLength);

    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage))

        return false;