cpython.git - https://github.com/python/cpython.git

diff options

Diffstat (limited to 'Python/Python-ast.c')

0 files changed, 0 insertions, 0 deletions

/* * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) * Copyright (C) 2003, 2007, 2008 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 "PropertyNameArray.h" #include <wtf/AVLTree.h> #include <wtf/Assertions.h> #include <Operations.h> #define CHECK_ARRAY_CONSISTENCY 0 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(JSValuePtr)) + // (vectorLength * sizeof(JSValuePtr)) must be <= 0xFFFFFFFFU (which is maximum value of size_t). #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr)) // 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(JSValuePtr)) + (vectorLength * sizeof(JSValuePtr)); // 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(JSValuePtr))) / sizeof(JSValuePtr) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValuePtr)))); 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(PassRefPtr<Structure> structure) : JSObject(structure) { unsigned initialCapacity = 0; m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity))); m_fastAccessCutoff = 0; m_storage->m_vectorLength = initialCapacity; m_storage->m_length = 0; checkConsistency(); } JSArray::JSArray(PassRefPtr<Structure> structure, unsigned initialLength) : JSObject(structure) { unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX); m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity))); m_fastAccessCutoff = 0; m_storage->m_vectorLength = initialCapacity; m_storage->m_length = initialLength; Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValuePtr)); checkConsistency(); } JSArray::JSArray(ExecState* exec, PassRefPtr<Structure> structure, const ArgList& list) : JSObject(structure) { unsigned length = list.size(); m_fastAccessCutoff = length; ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length))); storage->m_vectorLength = length; storage->m_numValuesInVector = length; storage->m_sparseValueMap = 0; storage->m_length = length; size_t i = 0; ArgList::const_iterator end = list.end(); for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) storage->m_vector[i] = (*it).jsValue(exec); m_storage = storage; // When the array is created non-empty, its cells are filled, so it's really no worse than // a property map. Therefore don't report extra memory cost. checkConsistency(); } JSArray::~JSArray() { 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 < storage->m_vectorLength) { JSValuePtr& 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 false; } 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); } // ECMA 15.4.5.1 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValuePtr 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, RangeError, "Invalid array length."); return; } setLength(newLength); return; } JSObject::put(exec, propertyName, value, slot); } void JSArray::put(ExecState* exec, unsigned i, JSValuePtr 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_storage->m_vectorLength) { JSValuePtr& valueSlot = m_storage->m_vector[i]; if (valueSlot) { valueSlot = value; checkConsistency(); return; } valueSlot = value; if (++m_storage->m_numValuesInVector == m_storage->m_length) m_fastAccessCutoff = m_storage->m_length; checkConsistency(); return; } putSlowCase(exec, i, value); } NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValuePtr 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 cutoff) - 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; } map->set(i, value); 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; if (++storage->m_numValuesInVector == storage->m_length) m_fastAccessCutoff = storage->m_length; 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(storage->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; } } storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength))); if (!storage) { throwOutOfMemoryError(exec); return; } unsigned vectorLength = storage->m_vectorLength; if (newNumValuesInVector == storage->m_numValuesInVector + 1) { for (unsigned j = vectorLength; j < newVectorLength; ++j) storage->m_vector[j] = noValue(); 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] = noValue(); for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) storage->m_vector[j] = map->take(j); } storage->m_vector[i] = value; storage->m_vectorLength = newVectorLength; storage->m_numValuesInVector = newNumValuesInVector; m_storage = storage; checkConsistency(); } 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 < storage->m_vectorLength) { JSValuePtr& valueSlot = storage->m_vector[i]; if (!valueSlot) { checkConsistency(); return false; } valueSlot = noValue(); --storage->m_numValuesInVector; if (m_fastAccessCutoff > i) m_fastAccessCutoff = i; 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::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames) { // 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, storage->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)); } JSObject::getPropertyNames(exec, propertyNames); } 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 = storage->m_vectorLength; ASSERT(newLength > vectorLength); ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); unsigned newVectorLength = increasedVectorLength(newLength); storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength))); if (!storage) return false; storage->m_vectorLength = newVectorLength; for (unsigned i = vectorLength; i < newVectorLength; ++i) storage->m_vector[i] = noValue(); m_storage = storage; return true; } void JSArray::setLength(unsigned newLength) { checkConsistency(); ArrayStorage* storage = m_storage; unsigned length = m_storage->m_length; if (newLength < length) { if (m_fastAccessCutoff > newLength) m_fastAccessCutoff = newLength; unsigned usedVectorLength = min(length, storage->m_vectorLength); for (unsigned i = newLength; i < usedVectorLength; ++i) { JSValuePtr& valueSlot = storage->m_vector[i]; bool hadValue = valueSlot; valueSlot = noValue(); 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; } } } m_storage->m_length = newLength; checkConsistency(); } JSValuePtr JSArray::pop() { checkConsistency(); unsigned length = m_storage->m_length; if (!length) return jsUndefined(); --length; JSValuePtr result; if (m_fastAccessCutoff > length) { JSValuePtr& valueSlot = m_storage->m_vector[length]; result = valueSlot; ASSERT(result); valueSlot = noValue(); --m_storage->m_numValuesInVector; m_fastAccessCutoff = length; } else if (length < m_storage->m_vectorLength) { JSValuePtr& valueSlot = m_storage->m_vector[length]; result = valueSlot; valueSlot = noValue(); 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; } void JSArray::push(ExecState* exec, JSValuePtr value) { 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); } void JSArray::mark() { JSObject::mark(); ArrayStorage* storage = m_storage; unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength); for (unsigned i = 0; i < usedVectorLength; ++i) { JSValuePtr value = storage->m_vector[i]; if (value && !value->marked()) value->mark(); } if (SparseArrayValueMap* map = storage->m_sparseValueMap) { SparseArrayValueMap::iterator end = map->end(); for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { JSValuePtr value = it->second; if (!value->marked()) value->mark(); } } } typedef std::pair<JSValuePtr, UString> ArrayQSortPair; static int compareByStringPairForQSort(const void* a, const void* b) { const ArrayQSortPair* va = static_cast<const ArrayQSortPair*>(a); const ArrayQSortPair* vb = static_cast<const ArrayQSortPair*>(b); return compare(va->second, vb->second); } void JSArray::sort(ExecState* exec) { unsigned lengthNotIncludingUndefined = compactForSorting(); if (m_storage->m_sparseValueMap) { throwOutOfMemoryError(exec); return; } 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. Vector<ArrayQSortPair> values(lengthNotIncludingUndefined); if (!values.begin()) { throwOutOfMemoryError(exec); return; } for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { JSValuePtr value = m_storage->m_vector[i]; ASSERT(!value->isUndefined()); values[i].first = value; } // 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++) values[i].second = values[i].first->toString(exec); 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). #if HAVE(MERGESORT) mergesort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort); #else // 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. qsort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort); #endif // FIXME: If the toString function changed the length of the array, this might be // modifying the vector incorrectly. for (size_t i = 0; i < lengthNotIncludingUndefined; i++) m_storage->m_vector[i] = values[i].first; checkConsistency(SortConsistencyCheck); } struct AVLTreeNodeForArrayCompare { JSValuePtr value; // 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. typedef JSValuePtr key; typedef int32_t size; Vector<AVLTreeNodeForArrayCompare> m_nodes; ExecState* m_exec; JSValuePtr m_compareFunction; CallType m_compareCallType; const CallData* m_compareCallData; JSValuePtr m_globalThisValue; 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) { 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; else m_nodes[h].gt &= 0x7FFFFFFF; } } int compare_key_key(key va, key vb) { ASSERT(!va->isUndefined()); ASSERT(!vb->isUndefined()); if (m_exec->hadException()) return 1; ArgList arguments; arguments.append(va); arguments.append(vb); double compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments)->toNumber(m_exec); return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. } 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; } }; void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData) { checkConsistency(); // FIXME: This ignores exceptions raised in the compare function or in toNumber. // The maximum tree depth is compiled in - but the caller is clearly up to no good // if a larger array is passed. 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())) return; if (!m_storage->m_length) return; unsigned usedVectorLength = min(m_storage->m_length, m_storage->m_vectorLength); AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items tree.abstractor().m_exec = exec; tree.abstractor().m_compareFunction = compareFunction; tree.abstractor().m_compareCallType = callType; tree.abstractor().m_compareCallData = &callData; tree.abstractor().m_globalThisValue = exec->globalThisValue(); tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0)); if (!tree.abstractor().m_nodes.begin()) { throwOutOfMemoryError(exec); return; } // 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. 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) { JSValuePtr v = m_storage->m_vector[numDefined]; if (!v || v->isUndefined()) break; tree.abstractor().m_nodes[numDefined].value = v; tree.insert(numDefined); } for (unsigned i = numDefined; i < usedVectorLength; ++i) { JSValuePtr v = m_storage->m_vector[i]; if (v) { if (v->isUndefined()) ++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(); if (newUsedVectorLength > m_storage->m_vectorLength) { // 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); 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; } ASSERT(tree.abstractor().m_nodes.size() >= numDefined); // FIXME: If the compare function changed the length of the array, the following might be // modifying the vector incorrectly. // 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) m_storage->m_vector[i] = noValue(); m_fastAccessCutoff = newUsedVectorLength; m_storage->m_numValuesInVector = newUsedVectorLength; checkConsistency(SortConsistencyCheck); } void JSArray::fillArgList(ExecState* exec, ArgList& args) { 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)); } unsigned JSArray::compactForSorting() { checkConsistency(); ArrayStorage* storage = m_storage; unsigned usedVectorLength = min(m_storage->m_length, storage->m_vectorLength); unsigned numDefined = 0; unsigned numUndefined = 0; for (; numDefined < usedVectorLength; ++numDefined) { JSValuePtr v = storage->m_vector[numDefined]; if (!v || v->isUndefined()) break; } for (unsigned i = numDefined; i < usedVectorLength; ++i) { JSValuePtr v = storage->m_vector[i]; if (v) { if (v->isUndefined()) ++numUndefined; else storage->m_vector[numDefined++] = v; } } unsigned newUsedVectorLength = numDefined + numUndefined; if (SparseArrayValueMap* map = storage->m_sparseValueMap) { newUsedVectorLength += map->size(); if (newUsedVectorLength > storage->m_vectorLength) { // Check that it is possible to allocate an array large enough to hold all the entries - if not, // exception is thrown by caller. if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) return 0; storage = m_storage; } SparseArrayValueMap::iterator end = map->end(); for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) storage->m_vector[numDefined++] = it->second; delete map; storage->m_sparseValueMap = 0; } for (unsigned i = numDefined; i < newUsedVectorLength; ++i) storage->m_vector[i] = jsUndefined(); for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) storage->m_vector[i] = noValue(); m_fastAccessCutoff = newUsedVectorLength; storage->m_numValuesInVector = newUsedVectorLength; checkConsistency(SortConsistencyCheck); return numDefined; } void* JSArray::lazyCreationData() { return m_storage->lazyCreationData; } void JSArray::setLazyCreationData(void* d) { m_storage->lazyCreationData = d; } #if CHECK_ARRAY_CONSISTENCY void JSArray::checkConsistency(ConsistencyCheckType type) { ASSERT(m_storage); if (type == SortConsistencyCheck) ASSERT(!m_storage->m_sparseValueMap); ASSERT(m_fastAccessCutoff <= m_storage->m_length); ASSERT(m_fastAccessCutoff <= m_storage->m_numValuesInVector); unsigned numValuesInVector = 0; for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) { if (JSValuePtr value = m_storage->m_vector[i]) { ASSERT(i < m_storage->m_length); if (type != DestructorConsistencyCheck) value->type(); // Likely to crash if the object was deallocated. ++numValuesInVector; } else { ASSERT(i >= m_fastAccessCutoff); if (type == SortConsistencyCheck) ASSERT(i >= m_storage->m_numValuesInVector); } } ASSERT(numValuesInVector == m_storage->m_numValuesInVector); if (m_storage->m_sparseValueMap) { SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end(); for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) { unsigned index = it->first; ASSERT(index < m_storage->m_length); ASSERT(index >= m_storage->m_vectorLength); ASSERT(index <= MAX_ARRAY_INDEX); ASSERT(it->second); if (type != DestructorConsistencyCheck) it->second->type(); // Likely to crash if the object was deallocated. } } } #endif JSArray* constructEmptyArray(ExecState* exec) { return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure()); } JSArray* constructEmptyArray(ExecState* exec, unsigned initialLength) { return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), initialLength); } JSArray* constructArray(ExecState* exec, JSValuePtr singleItemValue) { ArgList values; values.append(singleItemValue); return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values); } JSArray* constructArray(ExecState* exec, const ArgList& values) { return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values); } } // namespace JSC


context:
space:
mode: