It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Apr 2015 19:48:00 +0000 (19:48 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Apr 2015 19:48:00 +0000 (19:48 +0000)
https://bugs.webkit.org/show_bug.cgi?id=144013

Reviewed by Mark Lam.

Source/JavaScriptCore:

This patch implements Array.prototype.sort in JavaScript, removing the
C++ implementations. It is simpler and less error-prone to express our
operations in JavaScript, which provides memory safety, exception safety,
and recursion safety.

The performance result is mixed, but net positive in my opinion. It's
difficult to enumerate all the results, since we used to have so many
different sorting modes, and there are lots of different data patterns
across which you might want to measure sorting. Suffice it to say:

    (*) The benchmarks we track are faster or unchanged.

    (*) Sorting random input using a comparator -- which we think is
    common -- is 3X faster.

    (*) Sorting random input in a non-array object -- which jQuery does
    -- is 4X faster.

    (*) Sorting random input in a compact array of integers using a
    trivial pattern-matchable comparator is 2X *slower*.

* builtins/Array.prototype.js:
(sort.min):
(sort.stringComparator):
(sort.compactSparse): Special case compaction for sparse arrays because
we don't want to hang when sorting new Array(BIG).

(sort.compact):
(sort.merge):
(sort.mergeSort): Use merge sort because it's a reasonably efficient
stable sort. We have evidence that some sites depend on stable sort,
even though the ES6 spec does not mandate it. (See
<http://trac.webkit.org/changeset/33967>.)

This is a textbook implementation of merge sort with three optimizations:

    (1) Use iteration instead of recursion;

    (2) Use array subscripting instead of array copying in order to
    create logical sub-lists without creating physical sub-lists;

    (3) Swap src and dst at each iteration instead of copying src into
    dst, and only copy src into the subject array at the end if src is
    not the subject array.

(sort.inflate):
(sort.comparatorSort):
(sort): Sort in JavaScript for the win.

* builtins/BuiltinExecutables.cpp:
(JSC::BuiltinExecutables::createExecutableInternal): Allow non-private
names so we can use helper functions.

* bytecode/CodeBlock.h:
(JSC::CodeBlock::isNumericCompareFunction): Deleted.
* bytecode/UnlinkedCodeBlock.cpp:
(JSC::UnlinkedCodeBlock::UnlinkedCodeBlock):
* bytecode/UnlinkedCodeBlock.h:
(JSC::UnlinkedCodeBlock::setIsNumericCompareFunction): Deleted.
(JSC::UnlinkedCodeBlock::isNumericCompareFunction): Deleted.
* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::setIsNumericCompareFunction): Deleted.
* bytecompiler/BytecodeGenerator.h:
* bytecompiler/NodesCodegen.cpp:
(JSC::FunctionNode::emitBytecode): We don't do this special casing based
on pattern matching anymore. This was mainly an optimization to avoid
the overhead of calling from C++ to JS, which we now avoid by
sorting in JS.

* heap/Heap.cpp:
(JSC::Heap::markRoots):
(JSC::Heap::pushTempSortVector): Deleted.
(JSC::Heap::popTempSortVector): Deleted.
(JSC::Heap::visitTempSortVectors): Deleted.
* heap/Heap.h: We don't have temp sort vectors anymore because we sort
in JavaScript using a normal JavaScript array for our temporary storage.

* parser/Parser.cpp:
(JSC::Parser<LexerType>::parseInner): Allow capturing so we can use
helper functions.

* runtime/ArrayPrototype.cpp:
(JSC::isNumericCompareFunction): Deleted.
(JSC::attemptFastSort): Deleted.
(JSC::performSlowSort): Deleted.
(JSC::arrayProtoFuncSort): Deleted.

* runtime/CommonIdentifiers.h: New strings used by sort.

* runtime/JSArray.cpp:
(JSC::compareNumbersForQSortWithInt32): Deleted.
(JSC::compareNumbersForQSortWithDouble): Deleted.
(JSC::compareNumbersForQSort): Deleted.
(JSC::compareByStringPairForQSort): Deleted.
(JSC::JSArray::sortNumericVector): Deleted.
(JSC::JSArray::sortNumeric): Deleted.
(JSC::ContiguousTypeAccessor::getAsValue): Deleted.
(JSC::ContiguousTypeAccessor::setWithValue): Deleted.
(JSC::ContiguousTypeAccessor::replaceDataReference): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::getAsValue): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::setWithValue): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::replaceDataReference): Deleted.
(JSC::JSArray::sortCompactedVector): Deleted.
(JSC::JSArray::sort): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_less): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_less): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_greater): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_greater): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_balance_factor): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_balance_factor): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_key_key): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_key_node): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_node_node): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::null): Deleted.
(JSC::JSArray::sortVector): Deleted.
(JSC::JSArray::compactForSorting): Deleted.
* runtime/JSArray.h:

* runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::init):
* runtime/ObjectConstructor.cpp:
(JSC::ObjectConstructor::finishCreation): Provide some builtins used
by sort.

Source/WTF:

Remove this custom tree implementation because it is unused. (It was
previously used to achieve a stable array sort in certain cases.)

* WTF.vcxproj/WTF.vcxproj:
* WTF.vcxproj/WTF.vcxproj.filters:
* WTF.xcodeproj/project.pbxproj:
* wtf/AVLTree.h: Removed.
* wtf/CMakeLists.txt:

LayoutTests:

* js/script-tests/array-holes.js:
* js/array-holes-expected.txt: This result now matches Firefox. We see
'peekaboo', which is a prototype property, rather than a hole, because
sorting uses [[Get]], which sees prototype properties.

The ES6 spec says that sorting should use [[Get]], so this new result
matches the spec a little better -- although the spec also says that the
result of sorting is undefined in this case because of the presence of
an indexed property in the prototype chain.

* js/dom/array-prototype-properties-expected.txt: Updated error message
to match other array prototype error messages.

* js/comparefn-sort-stability-expected.txt:
* js/script-tests/comparefn-sort-stability.js: Made this test bigger in
order to demonstrate that Firefox and Safari use a stable sort, and
Chrome does not.

* js/script-tests/array-sort-sparse.js:
* js/array-sort-sparse-expected.txt: Added some tests for things I got
wrong in this patch.

* script-tests/sort-with-side-effecting-comparisons.js: Made this test
shorter so that it wouldn't hang debug builds. This test is O(N^2). It
used to terminate sooner because our sort implementation would (sometimes)
terminate sooner if you shrank the array. Our new sort does not accept
intermediate updates to the array's length, matching Firefox. I spoke
to Gavin and Alexey about this, and we think that going out of our way
to honor length changes mid-sort doesn't make much sense because it's
not possible to honor the general case of value changes in a predictable
way.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@183570 268f45cc-cd09-0410-ab3c-d52691b4dbfc

32 files changed:
LayoutTests/ChangeLog
LayoutTests/js/array-holes-expected.txt
LayoutTests/js/array-sort-sparse-expected.txt
LayoutTests/js/comparefn-sort-stability-expected.txt
LayoutTests/js/dom/array-prototype-properties-expected.txt
LayoutTests/js/script-tests/array-holes.js
LayoutTests/js/script-tests/array-sort-sparse.js
LayoutTests/js/script-tests/comparefn-sort-stability.js
LayoutTests/js/script-tests/sort-with-side-effecting-comparisons.js
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/builtins/Array.prototype.js
Source/JavaScriptCore/builtins/BuiltinExecutables.cpp
Source/JavaScriptCore/bytecode/CodeBlock.h
Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp
Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h
Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/runtime/ArrayPrototype.cpp
Source/JavaScriptCore/runtime/CommonIdentifiers.h
Source/JavaScriptCore/runtime/JSArray.cpp
Source/JavaScriptCore/runtime/JSArray.h
Source/JavaScriptCore/runtime/JSGlobalObject.cpp
Source/JavaScriptCore/runtime/ObjectConstructor.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.vcxproj/WTF.vcxproj
Source/WTF/WTF.vcxproj/WTF.vcxproj.filters
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/AVLTree.h [deleted file]
Source/WTF/wtf/CMakeLists.txt

index ea22bbe..a96fb0e 100644 (file)
@@ -1,3 +1,42 @@
+2015-04-28  Geoffrey Garen  <ggaren@apple.com>
+
+        It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
+        https://bugs.webkit.org/show_bug.cgi?id=144013
+
+        Reviewed by Mark Lam.
+
+        * js/script-tests/array-holes.js: 
+        * js/array-holes-expected.txt: This result now matches Firefox. We see
+        'peekaboo', which is a prototype property, rather than a hole, because
+        sorting uses [[Get]], which sees prototype properties.
+
+        The ES6 spec says that sorting should use [[Get]], so this new result
+        matches the spec a little better -- although the spec also says that the
+        result of sorting is undefined in this case because of the presence of
+        an indexed property in the prototype chain.
+
+        * js/dom/array-prototype-properties-expected.txt: Updated error message
+        to match other array prototype error messages.
+
+        * js/comparefn-sort-stability-expected.txt:
+        * js/script-tests/comparefn-sort-stability.js: Made this test bigger in
+        order to demonstrate that Firefox and Safari use a stable sort, and
+        Chrome does not.
+
+        * js/script-tests/array-sort-sparse.js:
+        * js/array-sort-sparse-expected.txt: Added some tests for things I got
+        wrong in this patch.
+
+        * script-tests/sort-with-side-effecting-comparisons.js: Made this test
+        shorter so that it wouldn't hang debug builds. This test is O(N^2). It
+        used to terminate sooner because our sort implementation would (sometimes)
+        terminate sooner if you shrank the array. Our new sort does not accept
+        intermediate updates to the array's length, matching Firefox. I spoke
+        to Gavin and Alexey about this, and we think that going out of our way
+        to honor length changes mid-sort doesn't make much sense because it's
+        not possible to honor the general case of value changes in a predictable
+        way.
+
 2015-04-29  Antti Koivisto  <antti@apple.com>
 
         Main resource loaded via 304 response becomes empty if reloaded by user
index ccb4550..468baf1 100644 (file)
@@ -36,7 +36,7 @@ PASS showHoles([0, , 2].concat([3, , 5])) is '[0, peekaboo, 2, 3, peekaboo, 5]'
 PASS showHoles([0, , 2, 3].reverse()) is '[3, 2, peekaboo, 0]'
 PASS a = [0, , 2, 3]; a.shift(); showHoles(a) is '[peekaboo, 2, 3]'
 PASS showHoles([0, , 2, 3].slice(0, 3)) is '[0, peekaboo, 2]'
-PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, hole]'
+PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, peekaboo]'
 PASS showHoles([0, undefined, 2, 3].sort()) is '[0, 2, 3, undefined]'
 PASS a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a) is '[0, hole, 5, 6]'
 PASS a = [0, , 2, 3]; a.unshift(4); showHoles(a) is '[4, 0, peekaboo, 2, 3]'
index 5074035..df6c06a 100644 (file)
@@ -5,6 +5,11 @@ On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE
 
 PASS testSort([,undefined,0,1]) is true
 PASS testSort({length:4,1:undefined,2:0,3:1}) is true
+PASS 0 in array is true
+PASS 1 in array is false
+PASS 0 in array is true
+PASS 1 in array is false
+PASS 2 in array is false
 PASS successfullyParsed is true
 
 TEST COMPLETE
index 417ef79..2df00fe 100644 (file)
@@ -3,14 +3,206 @@ This tests that sort(compareFn) is a stable sort.
 On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
 
 
-PASS arr[0] is sortArr[0]
-PASS arr[1] is sortArr[2]
-PASS arr[2] is sortArr[1]
-PASS arr[3] is sortArr[3]
-PASS arr[0] is sortArr[0]
-PASS arr[1] is sortArr[2]
-PASS arr[2] is sortArr[1]
-PASS arr[3] is sortArr[3]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[i] is ones[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
+PASS array[count + i] is twos[i]
 PASS successfullyParsed is true
 
 TEST COMPLETE
index 37e761e..cb5e8cf 100644 (file)
@@ -12,7 +12,7 @@ PASS Array.prototype.push.call(undefined, {}) threw exception TypeError: undefin
 PASS Array.prototype.reverse.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.reverse.call(undefined)').
 PASS Array.prototype.shift.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.shift.call(undefined)').
 PASS Array.prototype.slice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.slice.call(undefined, 0, 1)').
-PASS Array.prototype.sort.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.sort.call(undefined)').
+PASS Array.prototype.sort.call(undefined) threw exception TypeError: Array.prototype.sort requires that |this| not be undefined.
 PASS Array.prototype.splice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.splice.call(undefined, 0, 1)').
 PASS Array.prototype.unshift.call(undefined, {}) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.unshift.call(undefined, {})').
 PASS Array.prototype.every.call(undefined, toString) threw exception TypeError: Array.prototype.every requires that |this| not be undefined.
index 257a062..0027dc4 100644 (file)
@@ -87,7 +87,7 @@ shouldBe("showHoles([0, , 2].concat([3, , 5]))", "'[0, peekaboo, 2, 3, peekaboo,
 shouldBe("showHoles([0, , 2, 3].reverse())", "'[3, 2, peekaboo, 0]'");
 shouldBe("a = [0, , 2, 3]; a.shift(); showHoles(a)", "'[peekaboo, 2, 3]'");
 shouldBe("showHoles([0, , 2, 3].slice(0, 3))", "'[0, peekaboo, 2]'");
-shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, hole]'");
+shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, peekaboo]'");
 shouldBe("showHoles([0, undefined, 2, 3].sort())", "'[0, 2, 3, undefined]'");
 shouldBe("a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a)", "'[0, hole, 5, 6]'");
 shouldBe("a = [0, , 2, 3]; a.unshift(4); showHoles(a)", "'[4, 0, peekaboo, 2, 3]'");
index fc5e831..8854d9c 100644 (file)
@@ -10,3 +10,14 @@ function testSort(x)
 
 shouldBeTrue("testSort([,undefined,0,1])");
 shouldBeTrue("testSort({length:4,1:undefined,2:0,3:1})");
+
+var array = [ , undefined ];
+array.sort();
+shouldBeTrue("0 in array");
+shouldBeFalse("1 in array");
+
+var array = [ , 1, , ];
+array.sort();
+shouldBeTrue("0 in array");
+shouldBeFalse("1 in array");
+shouldBeFalse("2 in array");
index 5cdab10..267af1d 100644 (file)
@@ -2,30 +2,25 @@ description(
 "This tests that sort(compareFn) is a stable sort."
 );
 
-function clone(source, target) {
-    for (i = 0; i < source.length; i++) {
-        target[i] = source[i];
-    }
-}
+var count = 100;
+
+var ones = [];
+for (var i = 0; i < count; ++i)
+       ones.push(new Number(1));
 
-var arr = [];
-arr[0] = new Number(1);
-arr[1] = new Number(2);
-arr[2] = new Number(1);
-arr[3] = new Number(2);
+var twos = [];
+for (var i = 0; i < count; ++i)
+       twos.push(new Number(2));
 
-var sortArr = [];
-clone(arr, sortArr);
-sortArr.sort(function(a,b) { return a - b; });
+var array = [];
+for (var i = 0; i < count; ++i) {
+       array.push(ones[i]);
+       array.push(twos[i]);
+}
 
-shouldBe('arr[0]', 'sortArr[0]');
-shouldBe('arr[1]', 'sortArr[2]');
-shouldBe('arr[2]', 'sortArr[1]');
-shouldBe('arr[3]', 'sortArr[3]');
+array.sort(function(a,b) { return a - b; });
+for (var i = 0; i < count; ++i)
+       shouldBe('array[i]', 'ones[i]');
 
-// Just try again...
-sortArr.sort(function(a,b) { return a - b; });
-shouldBe('arr[0]', 'sortArr[0]');
-shouldBe('arr[1]', 'sortArr[2]');
-shouldBe('arr[2]', 'sortArr[1]');
-shouldBe('arr[3]', 'sortArr[3]');
+for (var i = 0; i < count; ++i)
+       shouldBe('array[count + i]', 'twos[i]');
index 63a35ec..a3a27d0 100644 (file)
@@ -4,7 +4,7 @@ description(
 
 var array = [];
 
-for (var i = 0; i < 20000; ++i)
+for (var i = 0; i < 2000; ++i)
     array.push(i);
 
 array.sort(function(a, b) {
index 088baea..6b4b42b 100644 (file)
@@ -1,3 +1,134 @@
+2015-04-28  Geoffrey Garen  <ggaren@apple.com>
+
+        It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
+        https://bugs.webkit.org/show_bug.cgi?id=144013
+
+        Reviewed by Mark Lam.
+
+        This patch implements Array.prototype.sort in JavaScript, removing the
+        C++ implementations. It is simpler and less error-prone to express our
+        operations in JavaScript, which provides memory safety, exception safety,
+        and recursion safety.
+
+        The performance result is mixed, but net positive in my opinion. It's
+        difficult to enumerate all the results, since we used to have so many
+        different sorting modes, and there are lots of different data patterns
+        across which you might want to measure sorting. Suffice it to say:
+
+            (*) The benchmarks we track are faster or unchanged.
+
+            (*) Sorting random input using a comparator -- which we think is
+            common -- is 3X faster.
+
+            (*) Sorting random input in a non-array object -- which jQuery does
+            -- is 4X faster.
+
+            (*) Sorting random input in a compact array of integers using a
+            trivial pattern-matchable comparator is 2X *slower*.
+
+        * builtins/Array.prototype.js:
+        (sort.min):
+        (sort.stringComparator):
+        (sort.compactSparse): Special case compaction for sparse arrays because
+        we don't want to hang when sorting new Array(BIG).
+
+        (sort.compact):
+        (sort.merge):
+        (sort.mergeSort): Use merge sort because it's a reasonably efficient
+        stable sort. We have evidence that some sites depend on stable sort,
+        even though the ES6 spec does not mandate it. (See
+        <http://trac.webkit.org/changeset/33967>.)
+
+        This is a textbook implementation of merge sort with three optimizations:
+
+            (1) Use iteration instead of recursion;
+
+            (2) Use array subscripting instead of array copying in order to
+            create logical sub-lists without creating physical sub-lists;
+
+            (3) Swap src and dst at each iteration instead of copying src into
+            dst, and only copy src into the subject array at the end if src is
+            not the subject array.
+
+        (sort.inflate):
+        (sort.comparatorSort):
+        (sort): Sort in JavaScript for the win.
+
+        * builtins/BuiltinExecutables.cpp:
+        (JSC::BuiltinExecutables::createExecutableInternal): Allow non-private
+        names so we can use helper functions.
+
+        * bytecode/CodeBlock.h:
+        (JSC::CodeBlock::isNumericCompareFunction): Deleted.
+        * bytecode/UnlinkedCodeBlock.cpp:
+        (JSC::UnlinkedCodeBlock::UnlinkedCodeBlock):
+        * bytecode/UnlinkedCodeBlock.h:
+        (JSC::UnlinkedCodeBlock::setIsNumericCompareFunction): Deleted.
+        (JSC::UnlinkedCodeBlock::isNumericCompareFunction): Deleted.
+        * bytecompiler/BytecodeGenerator.cpp:
+        (JSC::BytecodeGenerator::setIsNumericCompareFunction): Deleted.
+        * bytecompiler/BytecodeGenerator.h:
+        * bytecompiler/NodesCodegen.cpp:
+        (JSC::FunctionNode::emitBytecode): We don't do this special casing based
+        on pattern matching anymore. This was mainly an optimization to avoid 
+        the overhead of calling from C++ to JS, which we now avoid by
+        sorting in JS.
+
+        * heap/Heap.cpp:
+        (JSC::Heap::markRoots):
+        (JSC::Heap::pushTempSortVector): Deleted.
+        (JSC::Heap::popTempSortVector): Deleted.
+        (JSC::Heap::visitTempSortVectors): Deleted.
+        * heap/Heap.h: We don't have temp sort vectors anymore because we sort
+        in JavaScript using a normal JavaScript array for our temporary storage.
+
+        * parser/Parser.cpp:
+        (JSC::Parser<LexerType>::parseInner): Allow capturing so we can use
+        helper functions.
+
+        * runtime/ArrayPrototype.cpp:
+        (JSC::isNumericCompareFunction): Deleted.
+        (JSC::attemptFastSort): Deleted.
+        (JSC::performSlowSort): Deleted.
+        (JSC::arrayProtoFuncSort): Deleted.
+
+        * runtime/CommonIdentifiers.h: New strings used by sort.
+
+        * runtime/JSArray.cpp:
+        (JSC::compareNumbersForQSortWithInt32): Deleted.
+        (JSC::compareNumbersForQSortWithDouble): Deleted.
+        (JSC::compareNumbersForQSort): Deleted.
+        (JSC::compareByStringPairForQSort): Deleted.
+        (JSC::JSArray::sortNumericVector): Deleted.
+        (JSC::JSArray::sortNumeric): Deleted.
+        (JSC::ContiguousTypeAccessor::getAsValue): Deleted.
+        (JSC::ContiguousTypeAccessor::setWithValue): Deleted.
+        (JSC::ContiguousTypeAccessor::replaceDataReference): Deleted.
+        (JSC::ContiguousTypeAccessor<ArrayWithDouble>::getAsValue): Deleted.
+        (JSC::ContiguousTypeAccessor<ArrayWithDouble>::setWithValue): Deleted.
+        (JSC::ContiguousTypeAccessor<ArrayWithDouble>::replaceDataReference): Deleted.
+        (JSC::JSArray::sortCompactedVector): Deleted.
+        (JSC::JSArray::sort): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::get_less): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::set_less): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::get_greater): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::set_greater): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::get_balance_factor): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::set_balance_factor): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::compare_key_key): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::compare_key_node): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::compare_node_node): Deleted.
+        (JSC::AVLTreeAbstractorForArrayCompare::null): Deleted.
+        (JSC::JSArray::sortVector): Deleted.
+        (JSC::JSArray::compactForSorting): Deleted.
+        * runtime/JSArray.h:
+
+        * runtime/JSGlobalObject.cpp:
+        (JSC::JSGlobalObject::init):
+        * runtime/ObjectConstructor.cpp:
+        (JSC::ObjectConstructor::finishCreation): Provide some builtins used
+        by sort.
+
 2015-04-29  Mark Lam  <mark.lam@apple.com>
 
         Safari WebKit crash when loading Google Spreadsheet.
index d24de96..e756411 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -277,3 +277,185 @@ function includes(searchElement /*, fromIndex*/) {
     }
     return false;
 }
+
+function sort(comparator)
+{
+    "use strict";
+
+    function min(a, b)
+    {
+        return a < b ? a : b;
+    }
+
+    function stringComparator(a, b)
+    {
+        var aString = @String(a);
+        var bString = @String(b);
+
+        var aLength = aString.length;
+        var bLength = bString.length;
+        var length = min(aLength, bLength);
+
+        for (var i = 0; i < length; ++i) {
+            var aCharCode = aString.@charCodeAt(i);
+            var bCharCode = bString.@charCodeAt(i);
+
+            if (aCharCode == bCharCode)
+                continue;
+
+            if (aCharCode < bCharCode)
+                return -1;
+
+            return 1;
+        }
+
+        if (aLength == bLength)
+            return 0;
+
+        if (aLength < bLength)
+            return -1;
+
+        return 1;
+    }
+
+    // Move undefineds and holes to the end of a sparse array. Result is [values..., undefineds..., holes...].
+    function compactSparse(array, dst, src, length)
+    {
+        var values = [ ];
+        var seen = { };
+        var valueCount = 0;
+        var undefinedCount = 0;
+
+        // Clean up after the in-progress non-sparse compaction that failed.
+        for (var i = dst; i < src; ++i)
+            delete array[i];
+
+        for (var object = array; object; object = @Object.@getPrototypeOf(object)) {
+            var propertyNames = @Object.@getOwnPropertyNames(object);
+            for (var i = 0; i < propertyNames.length; ++i) {
+                var index = propertyNames[i];
+                if (index < length) { // Exclude non-numeric properties and properties past length.
+                    if (seen[index]) // Exclude duplicates.
+                        continue;
+                    seen[index] = 1;
+
+                    var value = array[index];
+                    delete array[index];
+
+                    if (value === undefined) {
+                        ++undefinedCount;
+                        continue;
+                    }
+
+                    array[valueCount++] = value;
+                }
+            }
+        }
+
+        for (var i = valueCount; i < valueCount + undefinedCount; ++i)
+            array[i] = undefined;
+
+        return valueCount;
+    }
+
+    // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
+    function compact(array, length)
+    {
+        var holeCount = 0;
+
+        for (var dst = 0, src = 0; src < length; ++src) {
+            if (!(src in array)) {
+                ++holeCount;
+                if (holeCount < 256)
+                    continue;
+                return compactSparse(array, dst, src, length);
+            }
+
+            var value = array[src];
+            if (value === undefined)
+                continue;
+            array[dst++] = value;
+        }
+
+        var valueCount = dst;
+        var undefinedCount = length - valueCount - holeCount;
+
+        for (var i = valueCount; i < valueCount + undefinedCount; ++i)
+            array[i] = undefined;
+
+        for (var i = valueCount + undefinedCount; i < length; ++i)
+            delete array[i];
+
+        return valueCount;
+    }
+
+    function merge(dst, src, srcIndex, srcEnd, width, comparator)
+    {
+        var left = srcIndex;
+        var leftEnd = min(left + width, srcEnd);
+        var right = leftEnd;
+        var rightEnd = min(right + width, srcEnd);
+
+        for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
+            if (right < rightEnd) {
+                if (left >= leftEnd || comparator(src[left], src[right]) > 0) {
+                    dst[dstIndex] = src[right++];
+                    continue;
+                }
+            }
+
+            dst[dstIndex] = src[left++];
+        }
+    }
+
+    function mergeSort(array, valueCount, comparator)
+    {
+        var buffer = [ ];
+        buffer.length = valueCount;
+
+        var dst = buffer;
+        var src = array;
+        for (var width = 1; width < valueCount; width *= 2) {
+            for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
+                merge(dst, src, srcIndex, valueCount, width, comparator);
+
+            var tmp = src;
+            src = dst;
+            dst = tmp;
+        }
+
+        if (src != array) {
+            for(var i = 0; i < valueCount; i++)
+                array[i] = src[i];
+        }
+    }
+
+    function comparatorSort(array, comparator)
+    {
+        var length = array.length >>> 0;
+
+        // For compatibility with Firefox and Chrome, do nothing observable
+        // to the target array if it has 0 or 1 sortable properties.
+        if (length < 2)
+            return;
+
+        var valueCount = compact(array, length);
+        mergeSort(array, valueCount, comparator);
+    }
+
+    if (this === null)
+        throw new @TypeError("Array.prototype.sort requires that |this| not be null");
+
+    if (this === undefined)
+        throw new @TypeError("Array.prototype.sort requires that |this| not be undefined");
+
+    if (typeof this == "string")
+        throw new @TypeError("Attempted to assign to readonly property.");
+
+    if (typeof comparator !== "function")
+        comparator = stringComparator;
+
+    var array = @Object(this);
+    comparatorSort(array, comparator);
+    return array;
+}
index 0b9627b..245eff3 100644 (file)
@@ -101,7 +101,6 @@ UnlinkedFunctionExecutable* BuiltinExecutables::createExecutableInternal(const S
         
         if (closedVariable == m_vm.propertyNames->undefinedKeyword.impl())
             continue;
-        RELEASE_ASSERT(m_vm.propertyNames->isPrivateName(closedVariable.get()));
     }
     body->overrideName(name);
     UnlinkedFunctionExecutable* functionExecutable = UnlinkedFunctionExecutable::create(&m_vm, source, body, kind, WTF::move(sourceOverride));
index 2fdfa30..af9ac6f 100644 (file)
@@ -249,8 +249,6 @@ public:
         return static_cast<Instruction*>(returnAddress) - instructions().begin();
     }
 
-    bool isNumericCompareFunction() { return m_unlinkedCode->isNumericCompareFunction(); }
-
     unsigned numberOfInstructions() const { return m_instructions.size(); }
     RefCountedArray<Instruction>& instructions() { return m_instructions; }
     const RefCountedArray<Instruction>& instructions() const { return m_instructions; }
index efd77ca..4a81501 100644 (file)
@@ -241,7 +241,6 @@ UnlinkedCodeBlock::UnlinkedCodeBlock(VM* vm, Structure* structure, CodeType code
     , m_globalObjectRegister(VirtualRegister())
     , m_needsFullScopeChain(info.needsActivation())
     , m_usesEval(info.usesEval())
-    , m_isNumericCompareFunction(false)
     , m_isStrictMode(info.isStrictMode())
     , m_isConstructor(info.isConstructor())
     , m_hasCapturedVariables(false)
index bedaac6..ca91e4a 100644 (file)
@@ -361,9 +361,6 @@ public:
     unsigned jumpTarget(int index) const { return m_jumpTargets[index]; }
     unsigned lastJumpTarget() const { return m_jumpTargets.last(); }
 
-    void setIsNumericCompareFunction(bool isNumericCompareFunction) { m_isNumericCompareFunction = isNumericCompareFunction; }
-    bool isNumericCompareFunction() const { return m_isNumericCompareFunction; }
-
     bool isBuiltinFunction() const { return m_isBuiltinFunction; }
 
     ConstructorKind constructorKind() const { return static_cast<ConstructorKind>(m_constructorKind); }
@@ -553,7 +550,6 @@ private:
 
     unsigned m_needsFullScopeChain : 1;
     unsigned m_usesEval : 1;
-    unsigned m_isNumericCompareFunction : 1;
     unsigned m_isStrictMode : 1;
     unsigned m_isConstructor : 1;
     unsigned m_hasCapturedVariables : 1;
index d472b2e..2f21e49 100644 (file)
@@ -2665,11 +2665,6 @@ RegisterID* BytecodeGenerator::emitThrowExpressionTooDeepException()
     return newTemporary();
 }
 
-void BytecodeGenerator::setIsNumericCompareFunction(bool isNumericCompareFunction)
-{
-    m_codeBlock->setIsNumericCompareFunction(isNumericCompareFunction);
-}
-
 bool BytecodeGenerator::isArgumentNumber(const Identifier& ident, int argumentNumber)
 {
     RegisterID* registerID = variable(ident).local();
index 4bf9bc6..9af8d4f 100644 (file)
@@ -276,8 +276,6 @@ namespace JSC {
 
         bool isArgumentNumber(const Identifier&, int);
 
-        void setIsNumericCompareFunction(bool isNumericCompareFunction);
-
         Variable variable(const Identifier&);
         
         // Ignores the possibility of intervening scopes.
index 2b1d0aa..0f0b78f 100644 (file)
@@ -2886,22 +2886,6 @@ void FunctionNode::emitBytecode(BytecodeGenerator& generator, RegisterID*)
         generator.emitReturn(r0);
         return;
     }
-
-    // If there is a return statment, and it is the only statement in the function, check if this is a numeric compare.
-    if (static_cast<BlockNode*>(singleStatement)->singleStatement()) {
-        ExpressionNode* returnValueExpression = returnNode->value();
-        if (returnValueExpression && returnValueExpression->isSubtract()) {
-            ExpressionNode* lhsExpression = static_cast<SubNode*>(returnValueExpression)->lhs();
-            ExpressionNode* rhsExpression = static_cast<SubNode*>(returnValueExpression)->rhs();
-            if (lhsExpression->isResolveNode()
-                && rhsExpression->isResolveNode()
-                && generator.isArgumentNumber(static_cast<ResolveNode*>(lhsExpression)->identifier(), 0)
-                && generator.isArgumentNumber(static_cast<ResolveNode*>(rhsExpression)->identifier(), 1)) {
-                
-                generator.setIsNumericCompareFunction(true);
-            }
-        }
-    }
 }
 
 // ------------------------------ FuncDeclNode ---------------------------------
index 6ae2ed7..1436f02 100644 (file)
@@ -481,17 +481,6 @@ void Heap::addReference(JSCell* cell, ArrayBuffer* buffer)
     }
 }
 
-void Heap::pushTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>* tempVector)
-{
-    m_tempSortingVectors.append(tempVector);
-}
-
-void Heap::popTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>* tempVector)
-{
-    ASSERT_UNUSED(tempVector, tempVector == m_tempSortingVectors.last());
-    m_tempSortingVectors.removeLast();
-}
-
 void Heap::harvestWeakReferences()
 {
     m_slotVisitor.harvestWeakReferences();
@@ -571,7 +560,6 @@ void Heap::markRoots(double gcStartTime, void* stackOrigin, void* stackTop, Mach
         visitSmallStrings();
         visitConservativeRoots(conservativeRoots);
         visitProtectedObjects(heapRootVisitor);
-        visitTempSortVectors(heapRootVisitor);
         visitArgumentBuffers(heapRootVisitor);
         visitException(heapRootVisitor);
         visitStrongHandles(heapRootVisitor);
@@ -710,23 +698,6 @@ void Heap::visitProtectedObjects(HeapRootVisitor& heapRootVisitor)
     m_slotVisitor.donateAndDrain();
 }
 
-void Heap::visitTempSortVectors(HeapRootVisitor& heapRootVisitor)
-{
-    GCPHASE(VisitTempSortVectors);
-
-    for (auto* vector : m_tempSortingVectors) {
-        for (auto& valueStringPair : *vector) {
-            if (valueStringPair.first)
-                heapRootVisitor.visit(&valueStringPair.first);
-        }
-    }
-
-    if (Options::logGC() == GCLogging::Verbose)
-        dataLog("Temp Sort Vectors:\n", m_slotVisitor);
-
-    m_slotVisitor.donateAndDrain();
-}
-
 void Heap::visitArgumentBuffers(HeapRootVisitor& visitor)
 {
     GCPHASE(MarkingArgumentBuffers);
index 3e0c051..d3e9688 100644 (file)
@@ -75,7 +75,6 @@ class Worklist;
 
 static void* const zombifiedBits = reinterpret_cast<void*>(0xdeadbeef);
 
-typedef std::pair<JSValue, WTF::String> ValueStringPair;
 typedef HashCountedSet<JSCell*> ProtectCountSet;
 typedef HashCountedSet<const char*> TypeCountSet;
 
@@ -186,9 +185,6 @@ public:
     JS_EXPORT_PRIVATE std::unique_ptr<TypeCountSet> objectTypeCounts();
     void showStatistics();
 
-    void pushTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
-    void popTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
-
     HashSet<MarkedArgumentBuffer*>& markListSet();
     
     template<typename Functor> typename Functor::ReturnType forEachProtectedCell(Functor&);
@@ -300,7 +296,6 @@ private:
     void visitCompilerWorklistWeakReferences();
     void removeDeadCompilerWorklistEntries();
     void visitProtectedObjects(HeapRootVisitor&);
-    void visitTempSortVectors(HeapRootVisitor&);
     void visitArgumentBuffers(HeapRootVisitor&);
     void visitException(HeapRootVisitor&);
     void visitStrongHandles(HeapRootVisitor&);
@@ -371,7 +366,6 @@ private:
     HashSet<const JSCell*> m_copyingRememberedSet;
 
     ProtectCountSet m_protectedValues;
-    Vector<Vector<ValueStringPair, 0, UnsafeVectorOverflow>*> m_tempSortingVectors;
     std::unique_ptr<HashSet<MarkedArgumentBuffer*>> m_markListSet;
 
     MachineThreads m_machineThreads;
index 8e61751..4077743 100644 (file)
@@ -54,7 +54,6 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState*);
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
-EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*);
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
@@ -70,21 +69,6 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState*);
 
 namespace JSC {
 
-static inline bool isNumericCompareFunction(ExecState* exec, JSValue function, CallType callType, const CallData& callData)
-{
-    if (callType != CallTypeJS)
-        return false;
-
-    FunctionExecutable* executable = callData.js.functionExecutable;
-    JSScope* scope = callData.js.scope;
-
-    JSObject* error = executable->prepareForExecution(exec, jsCast<JSFunction*>(function), scope, CodeForCall);
-    if (error)
-        return false;
-
-    return executable->codeBlockForCall()->isNumericCompareFunction();
-}
-
 // ------------------------------ ArrayPrototype ----------------------------
 
 const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, &arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)};
@@ -654,155 +638,6 @@ inline JSValue getOrHole(JSObject* obj, ExecState* exec, unsigned propertyName)
     return JSValue();
 }
 
-static bool attemptFastSort(ExecState* exec, JSObject* thisObj, JSValue function, CallData& callData, CallType& callType)
-{
-    if (thisObj->classInfo() != JSArray::info()
-        || asArray(thisObj)->hasSparseMap()
-        || shouldUseSlowPut(thisObj->indexingType()))
-        return false;
-    
-    if (isNumericCompareFunction(exec, function, callType, callData))
-        asArray(thisObj)->sortNumeric(exec, function, callType, callData);
-    else if (callType != CallTypeNone)
-        asArray(thisObj)->sort(exec, function, callType, callData);
-    else
-        asArray(thisObj)->sort(exec);
-    return true;
-}
-
-static bool performSlowSort(ExecState* exec, JSObject* thisObj, unsigned length, JSValue function, CallData& callData, CallType& callType)
-{
-    // "Min" sort. Not the fastest, but definitely less code than heapsort
-    // or quicksort, and much less swapping than bubblesort/insertionsort.
-    for (unsigned i = 0; i < length - 1; ++i) {
-        JSValue iObj = getOrHole(thisObj, exec, i);
-        if (exec->hadException())
-            return false;
-        unsigned themin = i;
-        JSValue minObj = iObj;
-        for (unsigned j = i + 1; j < length; ++j) {
-            JSValue jObj = getOrHole(thisObj, exec, j);
-            if (exec->hadException())
-                return false;
-            double compareResult;
-            if (!jObj)
-                compareResult = 1;
-            else if (!minObj)
-                compareResult = -1;
-            else if (jObj.isUndefined())
-                compareResult = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
-            else if (minObj.isUndefined())
-                compareResult = -1;
-            else if (callType != CallTypeNone) {
-                MarkedArgumentBuffer l;
-                l.append(jObj);
-                l.append(minObj);
-                compareResult = call(exec, function, callType, callData, jsUndefined(), l).toNumber(exec);
-            } else
-                compareResult = codePointCompareLessThan(jObj.toWTFStringInline(exec), minObj.toWTFStringInline(exec)) ? -1 : 1;
-
-            if (compareResult < 0) {
-                themin = j;
-                minObj = jObj;
-            }
-        }
-        // Swap themin and i
-        if (themin > i) {
-            if (minObj) {
-                thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, minObj, true);
-                if (exec->hadException())
-                    return false;
-            } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, i)) {
-                throwTypeError(exec, ASCIILiteral("Unable to delete property."));
-                return false;
-            }
-            if (iObj) {
-                thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, themin, iObj, true);
-                if (exec->hadException())
-                    return false;
-            } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, themin)) {
-                throwTypeError(exec, ASCIILiteral("Unable to delete property."));
-                return false;
-            }
-        }
-    }
-    return true;
-}
-
-EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec)
-{
-    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
-    unsigned length = getLength(exec, thisObj);
-    if (!length || exec->hadException())
-        return JSValue::encode(thisObj);
-
-    JSValue function = exec->argument(0);
-    CallData callData;
-    CallType callType = getCallData(function, callData);
-
-    if (attemptFastSort(exec, thisObj, function, callData, callType))
-        return JSValue::encode(thisObj);
-    
-    // Assume that for small-ish arrays, doing the slow sort directly is better.
-    if (length < 1000)
-        return performSlowSort(exec, thisObj, length, function, callData, callType) ? JSValue::encode(thisObj) : JSValue::encode(jsUndefined());
-    
-    JSGlobalObject* globalObject = JSGlobalObject::create(
-        exec->vm(), JSGlobalObject::createStructure(exec->vm(), jsNull()));
-    JSArray* flatArray = constructEmptyArray(globalObject->globalExec(), nullptr);
-    if (exec->hadException())
-        return JSValue::encode(jsUndefined());
-    
-    PropertyNameArray nameArray(exec);
-    thisObj->methodTable(exec->vm())->getPropertyNames(thisObj, exec, nameArray, EnumerationMode(DontEnumPropertiesMode::Include));
-    if (exec->hadException())
-        return JSValue::encode(jsUndefined());
-
-    Vector<uint32_t, 0, UnsafeVectorOverflow> keys;
-    for (size_t i = 0; i < nameArray.size(); ++i) {
-        PropertyName name = nameArray[i];
-        Optional<uint32_t> optionalIndex = parseIndex(name);
-        if (!optionalIndex)
-            continue;
-
-        uint32_t index = optionalIndex.value();
-        JSValue value = getOrHole(thisObj, exec, index);
-        if (exec->hadException())
-            return JSValue::encode(jsUndefined());
-        if (!value)
-            continue;
-        keys.append(index);
-        flatArray->push(exec, value);
-        if (exec->hadException())
-            return JSValue::encode(jsUndefined());
-    }
-    
-    if (!attemptFastSort(exec, flatArray, function, callData, callType)
-        && !performSlowSort(exec, flatArray, flatArray->length(), function, callData, callType))
-        return JSValue::encode(jsUndefined());
-    
-    for (size_t i = 0; i < keys.size(); ++i) {
-        size_t index = keys[i];
-        if (index < flatArray->length())
-            continue;
-        
-        if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, index)) {
-            throwTypeError(exec, ASCIILiteral("Unable to delete property."));
-            return JSValue::encode(jsUndefined());
-        }
-    }
-    
-    for (size_t i = flatArray->length(); i--;) {
-        JSValue value = getOrHole(flatArray, exec, i);
-        RELEASE_ASSERT(value);
-        thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, value, true);
-        if (exec->hadException())
-            return JSValue::encode(jsUndefined());
-    }
-    
-    return JSValue::encode(thisObj);
-}
-
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
 {
     // 15.4.4.12
index 6eeb111..79069ea 100644 (file)
     macro(objectGetOwnPropertySymbols) \
     macro(Number) \
     macro(Array) \
+    macro(String) \
     macro(abs) \
     macro(floor) \
     macro(isFinite) \
+    macro(getPrototypeOf) \
+    macro(getOwnPropertyNames) \
     macro(TypeError) \
     macro(undefined) \
     macro(BuiltinLog) \
index 76514d4..f0df029 100644 (file)
@@ -34,7 +34,6 @@
 #include "JSCInlines.h"
 #include "PropertyNameArray.h"
 #include "Reject.h"
-#include <wtf/AVLTree.h>
 #include <wtf/Assertions.h>
 
 using namespace std;
@@ -994,521 +993,6 @@ bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startInd
     }
 }
 
-static int compareNumbersForQSortWithInt32(const void* a, const void* b)
-{
-    int32_t ia = static_cast<const JSValue*>(a)->asInt32();
-    int32_t ib = static_cast<const JSValue*>(b)->asInt32();
-    return ia - ib;
-}
-
-static int compareNumbersForQSortWithDouble(const void* a, const void* b)
-{
-    double da = *static_cast<const double*>(a);
-    double db = *static_cast<const double*>(b);
-    return (da > db) - (da < db);
-}
-
-static int compareNumbersForQSort(const void* a, const void* b)
-{
-    double da = static_cast<const JSValue*>(a)->asNumber();
-    double db = static_cast<const JSValue*>(b)->asNumber();
-    return (da > db) - (da < db);
-}
-
-static int compareByStringPairForQSort(const void* a, const void* b)
-{
-    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
-    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
-    return codePointCompare(va->second, vb->second);
-}
-
-template<IndexingType arrayIndexingType>
-void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
-    ASSERT(arrayIndexingType == ArrayWithInt32 || arrayIndexingType == ArrayWithDouble || arrayIndexingType == ArrayWithContiguous || arrayIndexingType == ArrayWithArrayStorage);
-    
-    unsigned lengthNotIncludingUndefined;
-    unsigned newRelevantLength;
-    compactForSorting<arrayIndexingType>(
-        lengthNotIncludingUndefined,
-        newRelevantLength);
-    
-    ContiguousJSValues data = indexingData<arrayIndexingType>();
-    
-    if (arrayIndexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
-    
-    if (!lengthNotIncludingUndefined)
-        return;
-    
-    bool allValuesAreNumbers = true;
-    switch (arrayIndexingType) {
-    case ArrayWithInt32:
-    case ArrayWithDouble:
-        break;
-        
-    default:
-        for (size_t i = 0; i < newRelevantLength; ++i) {
-            if (!data[i].isNumber()) {
-                allValuesAreNumbers = false;
-                break;
-            }
-        }
-        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.
-    int (*compare)(const void*, const void*);
-    switch (arrayIndexingType) {
-    case ArrayWithInt32:
-        compare = compareNumbersForQSortWithInt32;
-        break;
-        
-    case ArrayWithDouble:
-        compare = compareNumbersForQSortWithDouble;
-        ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
-        break;
-        
-    default:
-        compare = compareNumbersForQSort;
-        break;
-    }
-    ASSERT(data.length() >= newRelevantLength);
-    qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
-    return;
-}
-
-void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
-    ASSERT(!inSparseIndexingMode());
-
-    switch (indexingType()) {
-    case ArrayClass:
-    case ArrayWithUndecided:
-        return;
-        
-    case ArrayWithInt32:
-        sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
-        return;
-        
-    case ArrayWithDouble:
-        sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
-        return;
-        
-    case ArrayWithContiguous:
-        sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
-        return;
-
-    case ArrayWithArrayStorage:
-        sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
-        return;
-        
-    default:
-        dataLog("Indexing type: ", indexingType(), "\n");
-        RELEASE_ASSERT_NOT_REACHED();
-        return;
-    }
-}
-
-template <IndexingType> struct ContiguousTypeAccessor {
-    typedef WriteBarrier<Unknown> Type;
-    static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); }
-    static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value)
-    {
-        data[i].set(vm, thisValue, value);
-    }
-    static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData)
-    {
-        *outData = inData;
-    }
-};
-
-template <> struct ContiguousTypeAccessor<ArrayWithDouble> {
-    typedef double Type;
-    static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); }
-    static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value)
-    {
-        data[i] = value.asNumber();
-    }
-    static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues)
-    {
-        RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort.");
-    }
-};
-
-
-template<IndexingType arrayIndexingType, typename StorageType>
-void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> data, unsigned relevantLength)
-{
-    if (!relevantLength)
-        return;
-    
-    VM& vm = exec->vm();
-
-    // 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<ValueStringPair, 0, UnsafeVectorOverflow> values(relevantLength);
-    if (!values.begin()) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
-        
-    Heap::heap(this)->pushTempSortVector(&values);
-        
-    bool isSortingPrimitiveValues = true;
-
-    for (size_t i = 0; i < relevantLength; i++) {
-        JSValue value = ContiguousTypeAccessor<arrayIndexingType>::getAsValue(data, i);
-        ASSERT(arrayIndexingType != ArrayWithInt32 || value.isInt32());
-        ASSERT(!value.isUndefined());
-        values[i].first = value;
-        if (arrayIndexingType != ArrayWithDouble && arrayIndexingType != ArrayWithInt32)
-            isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
-    }
-        
-    // 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 < relevantLength; i++)
-        values[i].second = values[i].first.toWTFStringInline(exec);
-        
-    if (exec->hadException()) {
-        Heap::heap(this)->popTempSortVector(&values);
-        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)
-    if (isSortingPrimitiveValues)
-        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
-    else
-        mergesort(values.begin(), values.size(), sizeof(ValueStringPair), 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(ValueStringPair), compareByStringPairForQSort);
-#endif
-    
-    // If the toString function changed the length of the array or vector storage,
-    // increase the length to handle the orignal number of actual values.
-    switch (arrayIndexingType) {
-    case ArrayWithInt32:
-    case ArrayWithDouble:
-    case ArrayWithContiguous:
-        ensureLength(vm, relevantLength);
-        break;
-        
-    case ArrayWithArrayStorage:
-        if (arrayStorage()->vectorLength() < relevantLength) {
-            increaseVectorLength(exec->vm(), relevantLength);
-            ContiguousTypeAccessor<arrayIndexingType>::replaceDataReference(&data, arrayStorage()->vector());
-        }
-        if (arrayStorage()->length() < relevantLength)
-            arrayStorage()->setLength(relevantLength);
-        break;
-        
-    default:
-        CRASH();
-    }
-
-    for (size_t i = 0; i < relevantLength; i++)
-        ContiguousTypeAccessor<arrayIndexingType>::setWithValue(vm, this, data, i, values[i].first);
-    
-    Heap::heap(this)->popTempSortVector(&values);
-}
-
-void JSArray::sort(ExecState* exec)
-{
-    ASSERT(!inSparseIndexingMode());
-    
-    switch (indexingType()) {
-    case ArrayClass:
-    case ArrayWithUndecided:
-        return;
-        
-    case ArrayWithInt32: {
-        unsigned lengthNotIncludingUndefined;
-        unsigned newRelevantLength;
-        compactForSorting<ArrayWithInt32>(
-            lengthNotIncludingUndefined, newRelevantLength);
-        
-        sortCompactedVector<ArrayWithInt32>(
-            exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
-        return;
-    }
-        
-    case ArrayWithDouble: {
-        unsigned lengthNotIncludingUndefined;
-        unsigned newRelevantLength;
-        compactForSorting<ArrayWithDouble>(
-            lengthNotIncludingUndefined, newRelevantLength);
-        
-        sortCompactedVector<ArrayWithDouble>(
-            exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
-        return;
-    }
-        
-    case ArrayWithContiguous: {
-        unsigned lengthNotIncludingUndefined;
-        unsigned newRelevantLength;
-        compactForSorting<ArrayWithContiguous>(
-            lengthNotIncludingUndefined, newRelevantLength);
-        
-        sortCompactedVector<ArrayWithContiguous>(
-            exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
-        return;
-    }
-        
-    case ArrayWithArrayStorage: {
-        unsigned lengthNotIncludingUndefined;
-        unsigned newRelevantLength;
-        compactForSorting<ArrayWithArrayStorage>(
-            lengthNotIncludingUndefined, newRelevantLength);
-        ArrayStorage* storage = m_butterfly->arrayStorage();
-        ASSERT(!storage->m_sparseMap);
-        
-        sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined);
-        return;
-    }
-        
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-    }
-}
-
-struct AVLTreeNodeForArrayCompare {
-    JSValue 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 JSValue key;
-    typedef int32_t size;
-
-    Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes;
-    ExecState* m_exec;
-    JSValue m_compareFunction;
-    CallType m_compareCallType;
-    const CallData* m_compareCallData;
-    std::unique_ptr<CachedCall> m_cachedCall;
-
-    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;
-
-        double compareResult;
-        if (m_cachedCall) {
-            m_cachedCall->setThis(jsUndefined());
-            m_cachedCall->setArgument(0, va);
-            m_cachedCall->setArgument(1, vb);
-            compareResult = m_cachedCall->call().toNumber(m_exec);
-        } else {
-            MarkedArgumentBuffer arguments;
-            arguments.append(va);
-            arguments.append(vb);
-            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), 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; }
-};
-
-template<IndexingType arrayIndexingType>
-void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
-    ASSERT(!inSparseIndexingMode());
-    ASSERT(arrayIndexingType == indexingType());
-    
-    // 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_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
-    if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
-        return;
-        
-    unsigned usedVectorLength = relevantLength<arrayIndexingType>();
-    unsigned nodeCount = usedVectorLength;
-        
-    if (!nodeCount)
-        return;
-        
-    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_nodes.grow(nodeCount);
-
-    if (callType == CallTypeJS)
-        tree.abstractor().m_cachedCall = std::make_unique<CachedCall>(exec, jsCast<JSFunction*>(compareFunction), 2);
-
-    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) {
-        if (numDefined >= m_butterfly->vectorLength())
-            break;
-        JSValue v = getHolyIndexQuickly(numDefined);
-        if (!v || v.isUndefined())
-            break;
-        tree.abstractor().m_nodes[numDefined].value = v;
-        tree.insert(numDefined);
-    }
-    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        if (i >= m_butterfly->vectorLength())
-            break;
-        JSValue v = getHolyIndexQuickly(i);
-        if (v) {
-            if (v.isUndefined())
-                ++numUndefined;
-            else {
-                tree.abstractor().m_nodes[numDefined].value = v;
-                tree.insert(numDefined);
-                ++numDefined;
-            }
-        }
-    }
-    
-    unsigned newUsedVectorLength = numDefined + numUndefined;
-        
-    // The array size may have changed. Figure out the new bounds.
-    unsigned newestUsedVectorLength = currentRelevantLength();
-        
-    unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
-    unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
-    unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
-        
-    // Copy the values back into m_storage.
-    AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
-    iter.start_iter_least(tree);
-    VM& vm = exec->vm();
-    for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
-        ASSERT(i < butterfly()->vectorLength());
-        if (indexingType() == ArrayWithDouble)
-            butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
-        else
-            currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value);
-        ++iter;
-    }
-    // Put undefined values back in.
-    switch (indexingType()) {
-    case ArrayWithInt32:
-    case ArrayWithDouble:
-        ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
-        break;
-        
-    default:
-        for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) {
-            ASSERT(i < butterfly()->vectorLength());
-            currentIndexingData()[i].setUndefined();
-        }
-    }
-
-    // Ensure that unused values in the vector are zeroed out.
-    for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
-        ASSERT(i < butterfly()->vectorLength());
-        if (indexingType() == ArrayWithDouble)
-            butterfly()->contiguousDouble()[i] = PNaN;
-        else
-            currentIndexingData()[i].clear();
-    }
-    
-    if (hasAnyArrayStorage(indexingType()))
-        arrayStorage()->m_numValuesInVector = newUsedVectorLength;
-}
-
-void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
-    ASSERT(!inSparseIndexingMode());
-    
-    switch (indexingType()) {
-    case ArrayClass:
-    case ArrayWithUndecided:
-        return;
-        
-    case ArrayWithInt32:
-        sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
-        return;
-
-    case ArrayWithDouble:
-        sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
-        return;
-
-    case ArrayWithContiguous:
-        sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
-        return;
-
-    case ArrayWithArrayStorage:
-        sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
-        return;
-        
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-    }
-}
-
 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 {
     unsigned i = 0;
@@ -1639,95 +1123,4 @@ void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest,
     }
 }
 
-template<IndexingType arrayIndexingType>
-void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
-{
-    ASSERT(!inSparseIndexingMode());
-    ASSERT(arrayIndexingType == indexingType());
-
-    unsigned myRelevantLength = relevantLength<arrayIndexingType>();
-    
-    numDefined = 0;
-    unsigned numUndefined = 0;
-        
-    for (; numDefined < myRelevantLength; ++numDefined) {
-        ASSERT(numDefined < m_butterfly->vectorLength());
-        if (arrayIndexingType == ArrayWithInt32) {
-            JSValue v = m_butterfly->contiguousInt32()[numDefined].get();
-            if (!v)
-                break;
-            ASSERT(v.isInt32());
-            continue;
-        }
-        if (arrayIndexingType == ArrayWithDouble) {
-            double v = m_butterfly->contiguousDouble()[numDefined];
-            if (v != v)
-                break;
-            continue;
-        }
-        JSValue v = indexingData<arrayIndexingType>()[numDefined].get();
-        if (!v || v.isUndefined())
-            break;
-    }
-        
-    for (unsigned i = numDefined; i < myRelevantLength; ++i) {
-        ASSERT(i < m_butterfly->vectorLength());
-        if (arrayIndexingType == ArrayWithInt32) {
-            JSValue v = m_butterfly->contiguousInt32()[i].get();
-            if (!v)
-                continue;
-            ASSERT(v.isInt32());
-            ASSERT(numDefined < m_butterfly->vectorLength());
-            m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v);
-            continue;
-        }
-        if (arrayIndexingType == ArrayWithDouble) {
-            double v = m_butterfly->contiguousDouble()[i];
-            if (v != v)
-                continue;
-            ASSERT(numDefined < m_butterfly->vectorLength());
-            m_butterfly->contiguousDouble()[numDefined++] = v;
-            continue;
-        }
-        JSValue v = indexingData<arrayIndexingType>()[i].get();
-        if (v) {
-            if (v.isUndefined())
-                ++numUndefined;
-            else {
-                ASSERT(numDefined < m_butterfly->vectorLength());
-                indexingData<arrayIndexingType>()[numDefined++].setWithoutWriteBarrier(v);
-            }
-        }
-    }
-        
-    newRelevantLength = numDefined + numUndefined;
-    
-    if (hasAnyArrayStorage(arrayIndexingType))
-        RELEASE_ASSERT(!arrayStorage()->m_sparseMap);
-    
-    switch (arrayIndexingType) {
-    case ArrayWithInt32:
-    case ArrayWithDouble:
-        RELEASE_ASSERT(numDefined == newRelevantLength);
-        break;
-        
-    default:
-        for (unsigned i = numDefined; i < newRelevantLength; ++i) {
-            ASSERT(i < m_butterfly->vectorLength());
-            indexingData<arrayIndexingType>()[i].setUndefined();
-        }
-        break;
-    }
-    for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
-        ASSERT(i < m_butterfly->vectorLength());
-        if (arrayIndexingType == ArrayWithDouble)
-            m_butterfly->contiguousDouble()[i] = PNaN;
-        else
-            indexingData<arrayIndexingType>()[i].clear();
-    }
-
-    if (hasAnyArrayStorage(arrayIndexingType))
-        arrayStorage()->m_numValuesInVector = newRelevantLength;
-}
-
 } // namespace JSC
index aabd55b..6208ba8 100644 (file)
@@ -70,10 +70,6 @@ public:
     // OK to use on new arrays, but not if it might be a RegExpMatchArray.
     JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
 
-    JS_EXPORT_PRIVATE void sort(ExecState*);
-    JS_EXPORT_PRIVATE void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
-    JS_EXPORT_PRIVATE void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
-
     JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
     JS_EXPORT_PRIVATE JSValue pop(ExecState*);
 
@@ -163,20 +159,8 @@ private:
     bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
     bool unshiftCountSlowCase(VM&, bool, unsigned);
 
-    template<IndexingType indexingType>
-    void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
-        
-    template<IndexingType indexingType, typename StorageType>
-    void sortCompactedVector(ExecState*, ContiguousData<StorageType>, unsigned relevantLength);
-        
-    template<IndexingType indexingType>
-    void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
-
     bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
     void setLengthWritable(ExecState*, bool writable);
-        
-    template<IndexingType indexingType>
-    void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength);
 };
 
 inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
index 1835168..507d8bc 100644 (file)
@@ -447,8 +447,11 @@ putDirectWithoutTransition(vm, vm.propertyNames-> jsName, lowerName ## Construct
         GlobalPropertyInfo(vm.propertyNames->BuiltinLogPrivateName, builtinLog, DontEnum | DontDelete | ReadOnly),
         GlobalPropertyInfo(vm.propertyNames->ArrayPrivateName, arrayConstructor, DontEnum | DontDelete | ReadOnly),
         GlobalPropertyInfo(vm.propertyNames->NumberPrivateName, numberConstructor, DontEnum | DontDelete | ReadOnly),
+        GlobalPropertyInfo(vm.propertyNames->StringPrivateName, stringConstructor, DontEnum | DontDelete | ReadOnly),
         GlobalPropertyInfo(vm.propertyNames->absPrivateName, privateFuncAbs, DontEnum | DontDelete | ReadOnly),
         GlobalPropertyInfo(vm.propertyNames->floorPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
+        GlobalPropertyInfo(vm.propertyNames->getPrototypeOfPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
+        GlobalPropertyInfo(vm.propertyNames->getOwnPropertyNamesPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
         GlobalPropertyInfo(vm.propertyNames->isFinitePrivateName, privateFuncIsFinite, DontEnum | DontDelete | ReadOnly),
         GlobalPropertyInfo(vm.propertyNames->arrayIterationKindKeyPrivateName, jsNumber(ArrayIterateKey), DontEnum | DontDelete | ReadOnly),
         GlobalPropertyInfo(vm.propertyNames->arrayIterationKindValuePrivateName, jsNumber(ArrayIterateValue), DontEnum | DontDelete | ReadOnly),
index 618dac3..d7b516a 100644 (file)
@@ -96,6 +96,9 @@ void ObjectConstructor::finishCreation(VM& vm, JSGlobalObject* globalObject, Obj
 
     if (!globalObject->runtimeFlags().isSymbolDisabled())
         JSC_NATIVE_FUNCTION("getOwnPropertySymbols", objectConstructorGetOwnPropertySymbols, DontEnum, 1);
+
+    JSC_NATIVE_FUNCTION(vm.propertyNames->getPrototypeOfPrivateName, objectConstructorGetPrototypeOf, DontEnum, 1);
+    JSC_NATIVE_FUNCTION(vm.propertyNames->getOwnPropertyNamesPrivateName, objectConstructorGetOwnPropertyNames, DontEnum, 1);
 }
 
 JSFunction* ObjectConstructor::addDefineProperty(ExecState* exec, JSGlobalObject* globalObject)
index a342e99..145d68c 100644 (file)
@@ -1,3 +1,19 @@
+2015-04-28  Geoffrey Garen  <ggaren@apple.com>
+
+        It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
+        https://bugs.webkit.org/show_bug.cgi?id=144013
+
+        Reviewed by Mark Lam.
+
+        Remove this custom tree implementation because it is unused. (It was
+        previously used to achieve a stable array sort in certain cases.)
+
+        * WTF.vcxproj/WTF.vcxproj:
+        * WTF.vcxproj/WTF.vcxproj.filters:
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/AVLTree.h: Removed.
+        * wtf/CMakeLists.txt:
+
 2015-04-29  Myles C. Maxfield  <mmaxfield@apple.com>
 
         [OS X] Use CTFontCreateForCSS instead of doing font search ourselves
index 6aa473d..a34247e 100644 (file)
     <ClInclude Include="..\wtf\Assertions.h" />
     <ClInclude Include="..\wtf\Atomics.h" />
     <ClInclude Include="..\wtf\AutodrainedPool.h" />
-    <ClInclude Include="..\wtf\AVLTree.h" />
     <ClInclude Include="..\wtf\Bag.h" />
     <ClInclude Include="..\wtf\BagToHashMap.h" />
     <ClInclude Include="..\wtf\Bitmap.h" />
index fae1069..cd92a31 100644 (file)
     <ClInclude Include="..\wtf\Atomics.h">
       <Filter>wtf</Filter>
     </ClInclude>
-    <ClInclude Include="..\wtf\AVLTree.h">
-      <Filter>wtf</Filter>
-    </ClInclude>
     <ClInclude Include="..\wtf\Bitmap.h">
       <Filter>wtf</Filter>
     </ClInclude>
index a038783..220d58d 100644 (file)
                A8A47386151A825B004123FF /* Assertions.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A4725B151A825A004123FF /* Assertions.cpp */; };
                A8A47387151A825B004123FF /* Assertions.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725C151A825A004123FF /* Assertions.h */; };
                A8A47388151A825B004123FF /* Atomics.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725D151A825A004123FF /* Atomics.h */; };
-               A8A47389151A825B004123FF /* AVLTree.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725E151A825A004123FF /* AVLTree.h */; };
                A8A4738A151A825B004123FF /* Bitmap.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725F151A825A004123FF /* Bitmap.h */; };
                A8A4738B151A825B004123FF /* BitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A47260151A825A004123FF /* BitVector.cpp */; };
                A8A4738C151A825B004123FF /* BitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47261151A825A004123FF /* BitVector.h */; };
                A8A4725B151A825A004123FF /* Assertions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Assertions.cpp; sourceTree = "<group>"; };
                A8A4725C151A825A004123FF /* Assertions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Assertions.h; sourceTree = "<group>"; };
                A8A4725D151A825A004123FF /* Atomics.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Atomics.h; sourceTree = "<group>"; };
-               A8A4725E151A825A004123FF /* AVLTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AVLTree.h; sourceTree = "<group>"; };
                A8A4725F151A825A004123FF /* Bitmap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Bitmap.h; sourceTree = "<group>"; };
                A8A47260151A825A004123FF /* BitVector.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BitVector.cpp; sourceTree = "<group>"; };
                A8A47261151A825A004123FF /* BitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BitVector.h; sourceTree = "<group>"; };
                                A8A4725D151A825A004123FF /* Atomics.h */,
                                1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
                                1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
-                               A8A4725E151A825A004123FF /* AVLTree.h */,
                                0FB14E18180FA218009B6B4D /* Bag.h */,
                                0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
                                A8A4725F151A825A004123FF /* Bitmap.h */,
                                A8A47438151A825B004123FF /* AtomicStringImpl.h in Headers */,
                                9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */,
                                1469419C16EAB10A0024E146 /* AutodrainedPool.h in Headers */,
-                               A8A47389151A825B004123FF /* AVLTree.h in Headers */,
                                8134013915B092FD001FF0B8 /* Base64.h in Headers */,
                                A8A473A9151A825B004123FF /* bignum-dtoa.h in Headers */,
                                A8A473AB151A825B004123FF /* bignum.h in Headers */,
diff --git a/Source/WTF/wtf/AVLTree.h b/Source/WTF/wtf/AVLTree.h
deleted file mode 100644 (file)
index 790e49f..0000000
+++ /dev/null
@@ -1,960 +0,0 @@
-/*
- * Copyright (C) 2008 Apple Inc. All rights reserved.
- *
- * Based on Abstract AVL Tree Template v1.5 by Walt Karas
- * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1.  Redistributions of source code must retain the above copyright
- *     notice, this list of conditions and the following disclaimer.
- * 2.  Redistributions in binary form must reproduce the above copyright
- *     notice, this list of conditions and the following disclaimer in the
- *     documentation and/or other materials provided with the distribution.
- * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
- *     its contributors may be used to endorse or promote products derived
- *     from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
- * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef AVL_TREE_H_
-#define AVL_TREE_H_
-
-#include <array>
-#include <wtf/Assertions.h>
-
-namespace WTF {
-
-// Here is the reference class for BSet.
-//
-// class BSet
-//   {
-//   public:
-//
-//     class ANY_bitref
-//       {
-//       public:
-//         operator bool ();
-//         void operator = (bool b);
-//       };
-//
-//     // Does not have to initialize bits.
-//     BSet();
-//
-//     // Must return a valid value for index when 0 <= index < maxDepth
-//     ANY_bitref operator [] (unsigned index);
-//
-//     // Set all bits to 1.
-//     void set();
-//
-//     // Set all bits to 0.
-//     void reset();
-//   };
-
-template<unsigned maxDepth>
-class AVLTreeDefaultBSet {
-public:
-    bool& operator[](unsigned i) { ASSERT_WITH_SECURITY_IMPLICATION(i < maxDepth); return m_data[i]; }
-    void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
-    void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }
-
-private:
-    std::array<bool, maxDepth> m_data;
-};
-
-// How to determine maxDepth:
-// d  Minimum number of nodes
-// 2  2
-// 3  4
-// 4  7
-// 5  12
-// 6  20
-// 7  33
-// 8  54
-// 9  88
-// 10 143
-// 11 232
-// 12 376
-// 13 609
-// 14 986
-// 15 1,596
-// 16 2,583
-// 17 4,180
-// 18 6,764
-// 19 10,945
-// 20 17,710
-// 21 28,656
-// 22 46,367
-// 23 75,024
-// 24 121,392
-// 25 196,417
-// 26 317,810
-// 27 514,228
-// 28 832,039
-// 29 1,346,268
-// 30 2,178,308
-// 31 3,524,577
-// 32 5,702,886
-// 33 9,227,464
-// 34 14,930,351
-// 35 24,157,816
-// 36 39,088,168
-// 37 63,245,985
-// 38 102,334,154
-// 39 165,580,140
-// 40 267,914,295
-// 41 433,494,436
-// 42 701,408,732
-// 43 1,134,903,169
-// 44 1,836,311,902
-// 45 2,971,215,072
-//
-// E.g., if, in a particular instantiation, the maximum number of nodes in a tree instance is 1,000,000, the maximum depth should be 28.
-// You pick 28 because MN(28) is 832,039, which is less than or equal to 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000.
-
-template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth>>
-class AVLTree {
-public:
-
-    typedef typename Abstractor::key key;
-    typedef typename Abstractor::handle handle;
-    typedef typename Abstractor::size size;
-
-    enum SearchType {
-        EQUAL = 1,
-        LESS = 2,
-        GREATER = 4,
-        LESS_EQUAL = EQUAL | LESS,
-        GREATER_EQUAL = EQUAL | GREATER
-    };
-
-
-    Abstractor& abstractor() { return abs; }
-
-    inline handle insert(handle h);
-
-    inline handle search(key k, SearchType st = EQUAL);
-    inline handle search_least();
-    inline handle search_greatest();
-
-    inline handle remove(key k);
-
-    inline handle subst(handle new_node);
-
-    void purge() { abs.root = null(); }
-
-    bool is_empty() { return abs.root == null(); }
-
-    AVLTree() { abs.root = null(); }
-
-    class Iterator {
-    public:
-
-        // Initialize depth to invalid value, to indicate iterator is
-        // invalid.   (Depth is zero-base.)
-        Iterator() { depth = ~0U; }
-
-        void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
-        {
-            // Mask of high bit in an int.
-            const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
-
-            // Save the tree that we're going to iterate through in a
-            // member variable.
-            tree_ = &tree;
-
-            int cmp, target_cmp;
-            handle h = tree_->abs.root;
-            unsigned d = 0;
-
-            depth = ~0U;
-
-            if (h == null())
-              // Tree is empty.
-              return;
-
-            if (st & LESS)
-              // Key can be greater than key of starting node.
-              target_cmp = 1;
-            else if (st & GREATER)
-              // Key can be less than key of starting node.
-              target_cmp = -1;
-            else
-              // Key must be same as key of starting node.
-              target_cmp = 0;
-
-            for (;;) {
-                cmp = cmp_k_n(k, h);
-                if (cmp == 0) {
-                    if (st & EQUAL) {
-                        // Equal node was sought and found as starting node.
-                        depth = d;
-                        break;
-                    }
-                    cmp = -target_cmp;
-                } else if (target_cmp != 0) {
-                    if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
-                        // cmp and target_cmp are both negative or both positive.
-                        depth = d;
-                    }
-                }
-                h = cmp < 0 ? get_lt(h) : get_gt(h);
-                if (h == null())
-                    break;
-                branch[d] = cmp > 0;
-                path_h[d++] = h;
-            }
-        }
-
-        void start_iter_least(AVLTree &tree)
-        {
-            tree_ = &tree;
-
-            handle h = tree_->abs.root;
-
-            depth = ~0U;
-
-            branch.reset();
-
-            while (h != null()) {
-                if (depth != ~0U)
-                    path_h[depth] = h;
-                depth++;
-                h = get_lt(h);
-            }
-        }
-
-        void start_iter_greatest(AVLTree &tree)
-        {
-            tree_ = &tree;
-
-            handle h = tree_->abs.root;
-
-            depth = ~0U;
-
-            branch.set();
-
-            while (h != null()) {
-                if (depth != ~0U)
-                    path_h[depth] = h;
-                depth++;
-                h = get_gt(h);
-            }
-        }
-
-        handle operator*()
-        {
-            if (depth == ~0U)
-                return null();
-
-            return depth == 0 ? tree_->abs.root : path_h[depth - 1];
-        }
-
-        void operator++()
-        {
-            if (depth != ~0U) {
-                handle h = get_gt(**this);
-                if (h == null()) {
-                    do {
-                        if (depth == 0) {
-                            depth = ~0U;
-                            break;
-                        }
-                        depth--;
-                    } while (branch[depth]);
-                } else {
-                    branch[depth] = true;
-                    path_h[depth++] = h;
-                    for (;;) {
-                        h = get_lt(h);
-                        if (h == null())
-                            break;
-                        branch[depth] = false;
-                        path_h[depth++] = h;
-                    }
-                }
-            }
-        }
-
-        void operator--()
-        {
-            if (depth != ~0U) {
-                handle h = get_lt(**this);
-                if (h == null())
-                    do {
-                        if (depth == 0) {
-                            depth = ~0U;
-                            break;
-                        }
-                        depth--;
-                    } while (!branch[depth]);
-                else {
-                    branch[depth] = false;
-                    path_h[depth++] = h;
-                    for (;;) {
-                        h = get_gt(h);
-                        if (h == null())
-                            break;
-                        branch[depth] = true;
-                        path_h[depth++] = h;
-                    }
-                }
-            }
-        }
-
-        void operator++(int) { ++(*this); }
-        void operator--(int) { --(*this); }
-
-    protected:
-
-        // Tree being iterated over.
-        AVLTree *tree_;
-
-        // Records a path into the tree.  If branch[n] is true, indicates
-        // take greater branch from the nth node in the path, otherwise
-        // take the less branch.  branch[0] gives branch from root, and
-        // so on.
-        BSet branch;
-
-        // Zero-based depth of path into tree.
-        unsigned depth;
-
-        // Handles of nodes in path from root to current node (returned by *).
-        handle path_h[maxDepth - 1];
-
-        int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
-        int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
-        handle get_lt(handle h) { return tree_->abs.get_less(h); }
-        handle get_gt(handle h) { return tree_->abs.get_greater(h); }
-        handle null() { return tree_->abs.null(); }
-    };
-
-    template<typename fwd_iter>
-    bool build(fwd_iter p, size num_nodes)
-    {
-        if (num_nodes == 0) {
-            abs.root = null();
-            return true;
-        }
-
-        // Gives path to subtree being built.  If branch[N] is false, branch
-        // less from the node at depth N, if true branch greater.
-        BSet branch;
-
-        // If rem[N] is true, then for the current subtree at depth N, it's
-        // greater subtree has one more node than it's less subtree.
-        BSet rem;
-
-            // Depth of root node of current subtree.
-        unsigned depth = 0;
-
-            // Number of nodes in current subtree.
-        size num_sub = num_nodes;
-
-        // The algorithm relies on a stack of nodes whose less subtree has
-        // been built, but whose right subtree has not yet been built.  The
-        // stack is implemented as linked list.  The nodes are linked
-        // together by having the "greater" handle of a node set to the
-        // next node in the list.  "less_parent" is the handle of the first
-        // node in the list.
-        handle less_parent = null();
-
-        // h is root of current subtree, child is one of its children.
-        handle h, child;
-
-        for (;;) {
-            while (num_sub > 2) {
-                // Subtract one for root of subtree.
-                num_sub--;
-                rem[depth] = !!(num_sub & 1);
-                branch[depth++] = false;
-                num_sub >>= 1;
-            }
-
-            if (num_sub == 2) {
-                // Build a subtree with two nodes, slanting to greater.
-                // I arbitrarily chose to always have the extra node in the
-                // greater subtree when there is an odd number of nodes to
-                // split between the two subtrees.
-
-                h = *p;
-                p++;
-                child = *p;
-                p++;
-                set_lt(child, null());
-                set_gt(child, null());
-                set_bf(child, 0);
-                set_gt(h, child);
-                set_lt(h, null());
-                set_bf(h, 1);
-            } else { // num_sub == 1
-                // Build a subtree with one node.
-
-                h = *p;
-                p++;
-                set_lt(h, null());
-                set_gt(h, null());
-                set_bf(h, 0);
-            }
-
-            while (depth) {
-                depth--;
-                if (!branch[depth])
-                    // We've completed a less subtree.
-                    break;
-
-                // We've completed a greater subtree, so attach it to
-                // its parent (that is less than it).  We pop the parent
-                // off the stack of less parents.
-                child = h;
-                h = less_parent;
-                less_parent = get_gt(h);
-                set_gt(h, child);
-                // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
-                num_sub <<= 1;
-                num_sub += 1 - rem[depth];
-                if (num_sub & (num_sub - 1))
-                    // num_sub is not a power of 2
-                    set_bf(h, 0);
-                else
-                    // num_sub is a power of 2
-                    set_bf(h, 1);
-            }
-
-            if (num_sub == num_nodes)
-                // We've completed the full tree.
-                break;
-
-            // The subtree we've completed is the less subtree of the
-            // next node in the sequence.
-
-            child = h;
-            h = *p;
-            p++;
-            set_lt(h, child);
-
-            // Put h into stack of less parents.
-            set_gt(h, less_parent);
-            less_parent = h;
-
-            // Proceed to creating greater than subtree of h.
-            branch[depth] = true;
-            num_sub += rem[depth++];
-
-        } // end for (;;)
-
-        abs.root = h;
-
-        return true;
-    }
-
-protected:
-
-    friend class Iterator;
-
-    // Create a class whose sole purpose is to take advantage of
-    // the "empty member" optimization.
-    struct abs_plus_root : public Abstractor {
-        // The handle of the root element in the AVL tree.
-        handle root;
-    };
-
-    abs_plus_root abs;
-
-
-    handle get_lt(handle h) { return abs.get_less(h); }
-    void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
-
-    handle get_gt(handle h) { return abs.get_greater(h); }
-    void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
-
-    int get_bf(handle h) { return abs.get_balance_factor(h); }
-    void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
-
-    int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
-    int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }
-
-    handle null() { return abs.null(); }
-
-private:
-
-    // Balances subtree, returns handle of root node of subtree
-    // after balancing.
-    handle balance(handle bal_h)
-    {
-        handle deep_h;
-
-        // Either the "greater than" or the "less than" subtree of
-        // this node has to be 2 levels deeper (or else it wouldn't
-        // need balancing).
-
-        if (get_bf(bal_h) > 0) {
-            // "Greater than" subtree is deeper.
-
-            deep_h = get_gt(bal_h);
-
-            if (get_bf(deep_h) < 0) {
-                handle old_h = bal_h;
-                bal_h = get_lt(deep_h);
-
-                set_gt(old_h, get_lt(bal_h));
-                set_lt(deep_h, get_gt(bal_h));
-                set_lt(bal_h, old_h);
-                set_gt(bal_h, deep_h);
-
-                int bf = get_bf(bal_h);
-                if (bf != 0) {
-                    if (bf > 0) {
-                        set_bf(old_h, -1);
-                        set_bf(deep_h, 0);
-                    } else {
-                        set_bf(deep_h, 1);
-                        set_bf(old_h, 0);
-                    }
-                    set_bf(bal_h, 0);
-                } else {
-                    set_bf(old_h, 0);
-                    set_bf(deep_h, 0);
-                }
-            } else {
-                set_gt(bal_h, get_lt(deep_h));
-                set_lt(deep_h, bal_h);
-                if (get_bf(deep_h) == 0) {
-                    set_bf(deep_h, -1);
-                    set_bf(bal_h, 1);
-                } else {
-                    set_bf(deep_h, 0);
-                    set_bf(bal_h, 0);
-                }
-                bal_h = deep_h;
-            }
-        } else {
-            // "Less than" subtree is deeper.
-
-            deep_h = get_lt(bal_h);
-
-            if (get_bf(deep_h) > 0) {
-                handle old_h = bal_h;
-                bal_h = get_gt(deep_h);
-                set_lt(old_h, get_gt(bal_h));
-                set_gt(deep_h, get_lt(bal_h));
-                set_gt(bal_h, old_h);
-                set_lt(bal_h, deep_h);
-
-                int bf = get_bf(bal_h);
-                if (bf != 0) {
-                    if (bf < 0) {
-                        set_bf(old_h, 1);
-                        set_bf(deep_h, 0);
-                    } else {
-                        set_bf(deep_h, -1);
-                        set_bf(old_h, 0);
-                    }
-                    set_bf(bal_h, 0);
-                } else {
-                    set_bf(old_h, 0);
-                    set_bf(deep_h, 0);
-                }
-            } else {
-                set_lt(bal_h, get_gt(deep_h));
-                set_gt(deep_h, bal_h);
-                if (get_bf(deep_h) == 0) {
-                    set_bf(deep_h, 1);
-                    set_bf(bal_h, -1);
-                } else {
-                    set_bf(deep_h, 0);
-                    set_bf(bal_h, 0);
-                }
-                bal_h = deep_h;
-            }
-        }
-
-        return bal_h;
-    }
-
-};
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
-{
-    set_lt(h, null());
-    set_gt(h, null());
-    set_bf(h, 0);
-
-    if (abs.root == null())
-        abs.root = h;
-    else {
-        // Last unbalanced node encountered in search for insertion point.
-        handle unbal = null();
-        // Parent of last unbalanced node.
-        handle parent_unbal = null();
-        // Balance factor of last unbalanced node.
-        int unbal_bf;
-
-        // Zero-based depth in tree.
-        unsigned depth = 0, unbal_depth = 0;
-
-        // Records a path into the tree.  If branch[n] is true, indicates
-        // take greater branch from the nth node in the path, otherwise
-        // take the less branch.  branch[0] gives branch from root, and
-        // so on.
-        BSet branch;
-
-        handle hh = abs.root;
-        handle parent = null();
-        int cmp;
-
-        do {
-            if (get_bf(hh) != 0) {
-                unbal = hh;
-                parent_unbal = parent;
-                unbal_depth = depth;
-            }
-            cmp = cmp_n_n(h, hh);
-            if (cmp == 0)
-                // Duplicate key.
-                return hh;
-            parent = hh;
-            hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
-            branch[depth++] = cmp > 0;
-        } while (hh != null());
-
-        //  Add node to insert as leaf of tree.
-        if (cmp < 0)
-            set_lt(parent, h);
-        else
-            set_gt(parent, h);
-
-        depth = unbal_depth;
-
-        if (unbal == null())
-            hh = abs.root;
-        else {
-            cmp = branch[depth++] ? 1 : -1;
-            unbal_bf = get_bf(unbal);
-            if (cmp < 0)
-                unbal_bf--;
-            else  // cmp > 0
-                unbal_bf++;
-            hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
-            if ((unbal_bf != -2) && (unbal_bf != 2)) {
-                // No rebalancing of tree is necessary.
-                set_bf(unbal, unbal_bf);
-                unbal = null();
-            }
-        }
-
-        if (hh != null())
-            while (h != hh) {
-                cmp = branch[depth++] ? 1 : -1;
-                if (cmp < 0) {
-                    set_bf(hh, -1);
-                    hh = get_lt(hh);
-                } else { // cmp > 0
-                    set_bf(hh, 1);
-                    hh = get_gt(hh);
-                }
-            }
-
-        if (unbal != null()) {
-            unbal = balance(unbal);
-            if (parent_unbal == null())
-                abs.root = unbal;
-            else {
-                depth = unbal_depth - 1;
-                cmp = branch[depth] ? 1 : -1;
-                if (cmp < 0)
-                    set_lt(parent_unbal, unbal);
-                else  // cmp > 0
-                    set_gt(parent_unbal, unbal);
-            }
-        }
-    }
-
-    return h;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
-{
-    const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
-
-    int cmp, target_cmp;
-    handle match_h = null();
-    handle h = abs.root;
-
-    if (st & LESS)
-        target_cmp = 1;
-    else if (st & GREATER)
-        target_cmp = -1;
-    else
-        target_cmp = 0;
-
-    while (h != null()) {
-        cmp = cmp_k_n(k, h);
-        if (cmp == 0) {
-            if (st & EQUAL) {
-                match_h = h;
-                break;
-            }
-            cmp = -target_cmp;
-        } else if (target_cmp != 0)
-            if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
-                // cmp and target_cmp are both positive or both negative.
-                match_h = h;
-        h = cmp < 0 ? get_lt(h) : get_gt(h);
-    }
-
-    return match_h;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::search_least()
-{
-    handle h = abs.root, parent = null();
-
-    while (h != null()) {
-        parent = h;
-        h = get_lt(h);
-    }
-
-    return parent;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
-{
-    handle h = abs.root, parent = null();
-
-    while (h != null()) {
-        parent = h;
-        h = get_gt(h);
-    }
-
-    return parent;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
-{
-    // Zero-based depth in tree.
-    unsigned depth = 0, rm_depth;
-
-    // Records a path into the tree.  If branch[n] is true, indicates
-    // take greater branch from the nth node in the path, otherwise
-    // take the less branch.  branch[0] gives branch from root, and
-    // so on.
-    BSet branch;
-
-    handle h = abs.root;
-    handle parent = null(), child;
-    int cmp, cmp_shortened_sub_with_path = 0;
-
-    for (;;) {
-        if (h == null())
-            // No node in tree with given key.
-            return null();
-        cmp = cmp_k_n(k, h);
-        if (cmp == 0)
-            // Found node to remove.
-            break;
-        parent = h;
-        h = cmp < 0 ? get_lt(h) : get_gt(h);
-        branch[depth++] = cmp > 0;
-        cmp_shortened_sub_with_path = cmp;
-    }
-    handle rm = h;
-    handle parent_rm = parent;
-    rm_depth = depth;
-
-    // If the node to remove is not a leaf node, we need to get a
-    // leaf node, or a node with a single leaf as its child, to put
-    // in the place of the node to remove.  We will get the greatest
-    // node in the less subtree (of the node to remove), or the least
-    // node in the greater subtree.  We take the leaf node from the
-    // deeper subtree, if there is one.
-
-    if (get_bf(h) < 0) {
-        child = get_lt(h);
-        branch[depth] = false;
-        cmp = -1;
-    } else {
-        child = get_gt(h);
-        branch[depth] = true;
-        cmp = 1;
-    }
-    depth++;
-
-    if (child != null()) {
-        cmp = -cmp;
-        do {
-            parent = h;
-            h = child;
-            if (cmp < 0) {
-                child = get_lt(h);
-                branch[depth] = false;
-            } else {
-                child = get_gt(h);
-                branch[depth] = true;
-            }
-            depth++;
-        } while (child != null());
-
-        if (parent == rm)
-            // Only went through do loop once.  Deleted node will be replaced
-            // in the tree structure by one of its immediate children.
-            cmp_shortened_sub_with_path = -cmp;
-        else
-            cmp_shortened_sub_with_path = cmp;
-
-        // Get the handle of the opposite child, which may not be null.
-        child = cmp > 0 ? get_lt(h) : get_gt(h);
-    }
-
-    if (parent == null())
-        // There were only 1 or 2 nodes in this tree.
-        abs.root = child;
-    else if (cmp_shortened_sub_with_path < 0)
-        set_lt(parent, child);
-    else
-        set_gt(parent, child);
-
-    // "path" is the parent of the subtree being eliminated or reduced
-    // from a depth of 2 to 1.  If "path" is the node to be removed, we
-    // set path to the node we're about to poke into the position of the
-    // node to be removed.
-    handle path = parent == rm ? h : parent;
-
-    if (h != rm) {
-        // Poke in the replacement for the node to be removed.
-        set_lt(h, get_lt(rm));
-        set_gt(h, get_gt(rm));
-        set_bf(h, get_bf(rm));
-        if (parent_rm == null())
-            abs.root = h;
-        else {
-            depth = rm_depth - 1;
-            if (branch[depth])
-                set_gt(parent_rm, h);
-            else
-                set_lt(parent_rm, h);
-        }
-    }
-
-    if (path != null()) {
-        // Create a temporary linked list from the parent of the path node
-        // to the root node.
-        h = abs.root;
-        parent = null();
-        depth = 0;
-        while (h != path) {
-            if (branch[depth++]) {
-                child = get_gt(h);
-                set_gt(h, parent);
-            } else {
-                child = get_lt(h);
-                set_lt(h, parent);
-            }
-            parent = h;
-            h = child;
-        }
-
-        // Climb from the path node to the root node using the linked
-        // list, restoring the tree structure and rebalancing as necessary.
-        bool reduced_depth = true;
-        int bf;
-        cmp = cmp_shortened_sub_with_path;
-        for (;;) {
-            if (reduced_depth) {
-                bf = get_bf(h);
-                if (cmp < 0)
-                    bf++;
-                else  // cmp > 0
-                    bf--;
-                if ((bf == -2) || (bf == 2)) {
-                    h = balance(h);
-                    bf = get_bf(h);
-                } else
-                    set_bf(h, bf);
-                reduced_depth = (bf == 0);
-            }
-            if (parent == null())
-                break;
-            child = h;
-            h = parent;
-            cmp = branch[--depth] ? 1 : -1;
-            if (cmp < 0)    {
-                parent = get_lt(h);
-                set_lt(h, child);
-            } else {
-                parent = get_gt(h);
-                set_gt(h, child);
-            }
-        }
-        abs.root = h;
-    }
-
-    return rm;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
-{
-    handle h = abs.root;
-    handle parent = null();
-    int cmp, last_cmp;
-
-    /* Search for node already in tree with same key. */
-    for (;;) {
-        if (h == null())
-            /* No node in tree with same key as new node. */
-            return null();
-        cmp = cmp_n_n(new_node, h);
-        if (cmp == 0)
-            /* Found the node to substitute new one for. */
-            break;
-        last_cmp = cmp;
-        parent = h;
-        h = cmp < 0 ? get_lt(h) : get_gt(h);
-    }
-
-    /* Copy tree housekeeping fields from node in tree to new node. */
-    set_lt(new_node, get_lt(h));
-    set_gt(new_node, get_gt(h));
-    set_bf(new_node, get_bf(h));
-
-    if (parent == null())
-        /* New node is also new root. */
-        abs.root = new_node;
-    else {
-        /* Make parent point to new node. */
-        if (last_cmp < 0)
-            set_lt(parent, new_node);
-        else
-            set_gt(parent, new_node);
-    }
-
-    return h;
-}
-
-}
-
-#endif
index 8623bac..2364dce 100644 (file)
@@ -1,6 +1,5 @@
 set(WTF_HEADERS
     ASCIICType.h
-    AVLTree.h
     Assertions.h
     Atomics.h
     Bag.h