Reviewed by Darin.
authorap@webkit.org <ap@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 May 2008 17:17:37 +0000 (17:17 +0000)
committerap@webkit.org <ap@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 May 2008 17:17:37 +0000 (17:17 +0000)
commit9bbcd75009e91d9cae54781d7edb9fd73b5870ef
treecec4fb0bed08dc08438e405344a56048313655af
parent5f506ec21b2638fad059939b08d9a8bbd71ccc0b
    Reviewed by Darin.

        <rdar://problem/5908520> REGRESSION (3.1.1-r33033): Crash in WebKit when opening or
        refreshing page on people.com

        The problem was that STL algorithms do not work with non-conformant comparators, and the
        site used sort(function() { return 0.5 - Math.random(); } to randomly shuffle an array.

        https://bugs.webkit.org/show_bug.cgi?id=18687
        REGRESSION(r32220): ecma/Array/15.4.4.5-3.js test now fails in GMT(BST)

        Besides relying on sort stability, this test was just broken, and kept failing with the
        new stable sort.

        Tests: fast/js/sort-randomly.html
               fast/js/sort-stability.html
               fast/js/comparefn-sort-stability.html

        * kjs/avl_tree.h: Added an AVL tree implementation.

        * JavaScriptCore.xcodeproj/project.pbxproj:
        * wtf/AVLTree.h: Added.
        Added an AVL tree implementation.

        * kjs/array_instance.cpp:
        (KJS::ArrayInstance::increaseVectorLength):
        (KJS::ArrayInstance::sort):
        (KJS::AVLTreeAbstractorForArrayCompare::get_less):
        (KJS::AVLTreeAbstractorForArrayCompare::set_less):
        (KJS::AVLTreeAbstractorForArrayCompare::get_greater):
        (KJS::AVLTreeAbstractorForArrayCompare::set_greater):
        (KJS::AVLTreeAbstractorForArrayCompare::get_balance_factor):
        (KJS::AVLTreeAbstractorForArrayCompare::set_balance_factor):
        (KJS::AVLTreeAbstractorForArrayCompare::compare_key_key):
        (KJS::AVLTreeAbstractorForArrayCompare::compare_key_node):
        (KJS::AVLTreeAbstractorForArrayCompare::compare_node_node):
        (KJS::AVLTreeAbstractorForArrayCompare::null):
        (KJS::ArrayInstance::compactForSorting):

        * kjs/array_instance.h: increaseVectorLength() now returns a bool to indicate whether it was
        successful.

        * wtf/Vector.h:
        (WTF::Vector::Vector):
        (WTF::::operator=):
        (WTF::::fill):
        Make these methods fail instead instead of crash when allocation fails, matching resize() and
        reserveCapacity(), which already had this behavior. Callers need to check for null buffer
        after making any Vector call that can try to allocate.

        * tests/mozilla/ecma/Array/15.4.4.5-3.js: Fixed the test to use a consistent sort function,
        as suggested in comments to a Mozilla bug filed about it (I'll keep tracking the bug to see
        what the final resolution is).

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@33967 268f45cc-cd09-0410-ab3c-d52691b4dbfc
17 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
JavaScriptCore/kjs/array_instance.cpp
JavaScriptCore/kjs/array_instance.h
JavaScriptCore/tests/mozilla/ecma/Array/15.4.4.5-3.js
JavaScriptCore/wtf/AVLTree.h [new file with mode: 0644]
JavaScriptCore/wtf/Vector.h
LayoutTests/ChangeLog
LayoutTests/fast/js/comparefn-sort-stability-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/comparefn-sort-stability.html [new file with mode: 0644]
LayoutTests/fast/js/resources/comparefn-sort-stability.js [new file with mode: 0644]
LayoutTests/fast/js/resources/sort-randomly.js [new file with mode: 0644]
LayoutTests/fast/js/resources/sort-stability.js [new file with mode: 0644]
LayoutTests/fast/js/sort-randomly-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/sort-randomly.html [new file with mode: 0644]
LayoutTests/fast/js/sort-stability-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/sort-stability.html [new file with mode: 0644]