Changeset 34496 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Jun 11, 2008, 12:37:44 PM (17 years ago)
Author:
Darin Adler
Message:

2008-06-11 Darin Adler <Darin Adler>

Reviewed by Alexey.

  • kjs/array_instance.cpp: (KJS::ArrayInstance::checkConsistency): Added. Empty inline version for when consistency checks are turned off. (KJS::ArrayInstance::ArrayInstance): Check consistency after construction. (KJS::ArrayInstance::~ArrayInstance): Check consistency before destruction. (KJS::ArrayInstance::put): Check consistency before and after. (KJS::ArrayInstance::deleteProperty): Ditto. (KJS::ArrayInstance::setLength): Ditto. (KJS::compareByStringPairForQSort): Use typedef for clarity. (KJS::ArrayInstance::sort): Check consistency before and after. Also broke the loop to set up sorting into two separate passes. Added FIXMEs about various exception safety issues. Added code to set m_numValuesInVector after sorting. (KJS::ArrayInstance::compactForSorting): Ditto.
  • kjs/array_instance.h: Added a definition of an enum for the types of consistency check and a declaration of the consistency checking function.
Location:
trunk/JavaScriptCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r34487 r34496  
     12008-06-11  Darin Adler  <[email protected]>
     2
     3        Reviewed by Alexey.
     4
     5        - fix https://bugs.webkit.org/show_bug.cgi?id=19442
     6          JavaScript array implementation doesn't maintain m_numValuesInVector when sorting
     7
     8        * kjs/array_instance.cpp:
     9        (KJS::ArrayInstance::checkConsistency): Added. Empty inline version for when
     10        consistency checks are turned off.
     11        (KJS::ArrayInstance::ArrayInstance): Check consistency after construction.
     12        (KJS::ArrayInstance::~ArrayInstance): Check consistency before destruction.
     13        (KJS::ArrayInstance::put): Check consistency before and after.
     14        (KJS::ArrayInstance::deleteProperty): Ditto.
     15        (KJS::ArrayInstance::setLength): Ditto.
     16        (KJS::compareByStringPairForQSort): Use typedef for clarity.
     17        (KJS::ArrayInstance::sort): Check consistency before and after. Also broke the loop
     18        to set up sorting into two separate passes. Added FIXMEs about various exception
     19        safety issues. Added code to set m_numValuesInVector after sorting.
     20        (KJS::ArrayInstance::compactForSorting): Ditto.
     21
     22        * kjs/array_instance.h: Added a definition of an enum for the types of consistency
     23        check and a declaration of the consistency checking function.
     24
    1252008-06-10  Kevin Ollivier  <[email protected]>
    226

  • trunk/JavaScriptCore/kjs/array_instance.cpp

    r34355 r34496  
    2828#include <wtf/AVLTree.h>
    2929
     30#define CHECK_ARRAY_CONSISTENCY 0
     31
    3032using namespace std;
    3133
    … …  
    4143};
    4244
    43 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
     45// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
    4446static const unsigned maxArrayIndex = 0xFFFFFFFEU;
    4547
    … …  
    7072}
    7173
     74#if !CHECK_ARRAY_CONSISTENCY
     75
     76inline void ArrayInstance::checkConsistency(ConsistencyCheckType)
     77{
     78}
     79
     80#endif
     81
    7282ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength)
    7383    : JSObject(prototype)
    … …  
    8090
    8191    Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
     92
     93    checkConsistency();
    8294}
    8395
    … …  
    104116    // When the array is created non-empty, its cells are filled, so it's really no worse than
    105117    // a property map. Therefore don't report extra memory cost.
     118
     119    checkConsistency();
    106120}
    107121
    108122ArrayInstance::~ArrayInstance()
    109123{
     124    checkConsistency(DestructorConsistencyCheck);
     125
    110126    delete m_storage->m_sparseValueMap;
    111127    fastFree(m_storage);
    … …  
    210226void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value)
    211227{
     228    checkConsistency();
     229
    212230    unsigned length = m_length;
    213231    if (i >= length) {
    … …  
    226244        storage->m_numValuesInVector += !valueSlot;
    227245        valueSlot = value;
     246        checkConsistency();
    228247        return;
    229248    }
    … …  
    251270        ++storage->m_numValuesInVector;
    252271        storage->m_vector[i] = value;
     272        checkConsistency();
    253273        return;
    254274    }
    … …  
    295315
    296316    m_storage = storage;
     317
     318    checkConsistency();
    297319}
    298320
    … …  
    312334bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i)
    313335{
     336    checkConsistency();
     337
    314338    ArrayStorage* storage = m_storage;
    315339
    … …  
    319343        valueSlot = 0;
    320344        storage->m_numValuesInVector -= hadValue;
     345        checkConsistency();
    321346        return hadValue;
    322347    }
    … …  
    327352            if (it != map->end()) {
    328353                map->remove(it);
     354                checkConsistency();
    329355                return true;
    330356            }
    … …  
    332358    }
    333359
     360    checkConsistency();
     361
    334362    if (i > maxArrayIndex)
    335363        return deleteProperty(exec, Identifier::from(i));
    … …  
    341369{
    342370    // FIXME: Filling PropertyNameArray with an identifier for every integer
    343     // is incredibly inefficient for large arrays. We need a different approach.
     371    // is incredibly inefficient for large arrays. We need a different approach,
     372    // which almost certainly means a different structure for PropertyNameArray.
    344373
    345374    ArrayStorage* storage = m_storage;
    … …  
    386415void ArrayInstance::setLength(unsigned newLength)
    387416{
     417    checkConsistency();
     418
    388419    ArrayStorage* storage = m_storage;
    389420
    … …  
    414445
    415446    m_length = newLength;
     447
     448    checkConsistency();
    416449}
    417450
    … …  
    439472}
    440473
     474typedef std::pair<JSValue*, UString> ArrayQSortPair;
     475
    441476static int compareByStringPairForQSort(const void* a, const void* b)
    442477{
    443     const std::pair<JSValue*, UString>* va = static_cast<const std::pair<JSValue*, UString>*>(a);
    444     const std::pair<JSValue*, UString>* vb = static_cast<const std::pair<JSValue*, UString>*>(b);
     478    const ArrayQSortPair* va = static_cast<const ArrayQSortPair*>(a);
     479    const ArrayQSortPair* vb = static_cast<const ArrayQSortPair*>(b);
    445480    return compare(va->second, vb->second);
    446481}
    … …  
    462497    // random or otherwise changing results, effectively making compare function inconsistent.
    463498
    464     Vector<std::pair<JSValue*, UString> > values(lengthNotIncludingUndefined);
     499    Vector<ArrayQSortPair> values(lengthNotIncludingUndefined);
    465500    if (!values.begin()) {
    466501        exec->setException(Error::create(exec, GeneralError, "Out of memory"));
    … …  
    472507        ASSERT(!value->isUndefined());
    473508        values[i].first = value;
    474         values[i].second = value->toString(exec);
    475     }
     509    }
     510
     511    // FIXME: While calling these toString functions, the array could be mutated.
     512    // In that case, objects pointed to by values in this vector might get garbage-collected!
     513
     514    // FIXME: The following loop continues to call toString on subsequent values even after
     515    // a toString call raises an exception.
     516
     517    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
     518        values[i].second = values[i].first->toString(exec);
    476519
    477520    if (exec->hadException())
    … …  
    482525
    483526#if HAVE(MERGESORT)
    484     mergesort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
     527    mergesort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
    485528#else
    486     // FIXME: QSort may not be stable in some implementations. ECMAScript-262 does not require this, but in practice, browsers perform stable sort.
    487     qsort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
     529    // FIXME: The qsort library function is likely to not be a stable sort.
     530    // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
     531    qsort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
    488532#endif
     533
     534    // FIXME: If the toString function changed the length of the array, this might be
     535    // modifying the vector incorrectly.
    489536
    490537    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
    491538        m_storage->m_vector[i] = values[i].first;
     539
     540    checkConsistency(SortConsistencyCheck);
    492541}
    493542
    … …  
    559608void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
    560609{
     610    checkConsistency();
     611
     612    // FIXME: This ignores exceptions raised in the compare function or in toNumber.
     613
    561614    // The maximum tree depth is compiled in - but the caller is clearly up to no good
    562615    // if a larger array is passed.
    … …  
    580633        return;
    581634    }
     635
     636    // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
     637    // right out from under us while we're building the tree here.
    582638
    583639    unsigned numDefined = 0;
    … …  
    628684    ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
    629685
     686    // FIXME: If the compare function changed the length of the array, the following might be
     687    // modifying the vector incorrectly.
     688
    630689    // Copy the values back into m_storage.
    631690    AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
    … …  
    643702    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
    644703        m_storage->m_vector[i] = 0;
     704
     705    m_storage->m_numValuesInVector = newUsedVectorLength;
     706
     707    checkConsistency(SortConsistencyCheck);
    645708}
    646709
    647710unsigned ArrayInstance::compactForSorting()
    648711{
     712    checkConsistency();
     713
    649714    ArrayStorage* storage = m_storage;
    650715
    … …  
    691756        storage->m_vector[i] = 0;
    692757
     758    storage->m_numValuesInVector = newUsedVectorLength;
     759
     760    checkConsistency(SortConsistencyCheck);
     761
    693762    return numDefined;
    694763}
    … …  
    704773}
    705774
    706 }
     775#if CHECK_ARRAY_CONSISTENCY
     776
     777void ArrayInstance::checkConsistency(ConsistencyCheckType type)
     778{
     779    ASSERT(m_storage);
     780    if (type == SortConsistencyCheck)
     781        ASSERT(!m_storage->m_sparseValueMap);
     782
     783    unsigned numValuesInVector = 0;
     784    for (unsigned i = 0; i < m_vectorLength; ++i) {
     785        if (JSValue* value = m_storage->m_vector[i]) {
     786            ASSERT(i < m_length);
     787            if (type != DestructorConsistencyCheck)
     788                value->type(); // Likely to crash if the object was deallocated.
     789            ++numValuesInVector;
     790        } else {
     791            if (type == SortConsistencyCheck)
     792                ASSERT(i >= m_storage->m_numValuesInVector);
     793        }
     794    }
     795    ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
     796
     797    if (m_storage->m_sparseValueMap) {
     798        SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
     799        for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
     800            unsigned index = it->first;
     801            ASSERT(index < m_length);
     802            ASSERT(index >= m_vectorLength);
     803            ASSERT(index <= maxArrayIndex);
     804            ASSERT(it->second);
     805            if (type != DestructorConsistencyCheck)
     806                it->second->type(); // Likely to crash if the object was deallocated.
     807        }
     808    }
     809}
     810
     811#endif
     812
     813}

  • trunk/JavaScriptCore/kjs/array_instance.h

    r34355 r34496  
    22/*
    33 *  Copyright (C) 1999-2000 Harri Porten ([email protected])
    4  *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
     4 *  Copyright (C) 2003, 2007, 2008 Apple Inc. All rights reserved.
    55 *
    66 *  This library is free software; you can redistribute it and/or
    … …  
    6565    bool increaseVectorLength(unsigned newLength);
    6666   
    67     unsigned compactForSorting();   
     67    unsigned compactForSorting();
     68
     69    enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
     70    void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
    6871
    6972    unsigned m_length;
Note: See TracChangeset for help on using the changeset viewer.