Diff
Modified: trunk/LayoutTests/ChangeLog (183287 => 183288)
--- trunk/LayoutTests/ChangeLog 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/ChangeLog 2015-04-24 23:02:29 UTC (rev 183288)
@@ -1,3 +1,32 @@
+2015-04-21 Geoffrey Garen <[email protected]>
+
+ 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.
+
2015-04-24 Alexey Proskuryakov <[email protected]>
fast/frames/flattening/iframe-flattening-resize-event-count.html times out on Yosemite WK2
Modified: trunk/LayoutTests/js/array-holes-expected.txt (183287 => 183288)
--- trunk/LayoutTests/js/array-holes-expected.txt 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/js/array-holes-expected.txt 2015-04-24 23:02:29 UTC (rev 183288)
@@ -36,7 +36,7 @@
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]'
Modified: trunk/LayoutTests/js/array-sort-sparse-expected.txt (183287 => 183288)
--- trunk/LayoutTests/js/array-sort-sparse-expected.txt 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/js/array-sort-sparse-expected.txt 2015-04-24 23:02:29 UTC (rev 183288)
@@ -5,6 +5,11 @@
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
Modified: trunk/LayoutTests/js/comparefn-sort-stability-expected.txt (183287 => 183288)
--- trunk/LayoutTests/js/comparefn-sort-stability-expected.txt 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/js/comparefn-sort-stability-expected.txt 2015-04-24 23:02:29 UTC (rev 183288)
@@ -3,14 +3,206 @@
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
Modified: trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt (183287 => 183288)
--- trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt 2015-04-24 23:02:29 UTC (rev 183288)
@@ -12,7 +12,7 @@
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.
Modified: trunk/LayoutTests/js/script-tests/array-holes.js (183287 => 183288)
--- trunk/LayoutTests/js/script-tests/array-holes.js 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/js/script-tests/array-holes.js 2015-04-24 23:02:29 UTC (rev 183288)
@@ -87,7 +87,7 @@
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]'");
Modified: trunk/LayoutTests/js/script-tests/array-sort-sparse.js (183287 => 183288)
--- trunk/LayoutTests/js/script-tests/array-sort-sparse.js 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/js/script-tests/array-sort-sparse.js 2015-04-24 23:02:29 UTC (rev 183288)
@@ -10,3 +10,14 @@
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");
Modified: trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js (183287 => 183288)
--- trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js 2015-04-24 23:02:29 UTC (rev 183288)
@@ -2,30 +2,25 @@
"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 arr = [];
-arr[0] = new Number(1);
-arr[1] = new Number(2);
-arr[2] = new Number(1);
-arr[3] = new Number(2);
+var _ones_ = [];
+for (var i = 0; i < count; ++i)
+ ones.push(new Number(1));
-var sortArr = [];
-clone(arr, sortArr);
-sortArr.sort(function(a,b) { return a - b; });
+var twos = [];
+for (var i = 0; i < count; ++i)
+ twos.push(new Number(2));
-shouldBe('arr[0]', 'sortArr[0]');
-shouldBe('arr[1]', 'sortArr[2]');
-shouldBe('arr[2]', 'sortArr[1]');
-shouldBe('arr[3]', 'sortArr[3]');
+var array = [];
+for (var i = 0; i < count; ++i) {
+ array.push(ones[i]);
+ array.push(twos[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]');
+array.sort(function(a,b) { return a - b; });
+for (var i = 0; i < count; ++i)
+ shouldBe('array[i]', 'ones[i]');
+
+for (var i = 0; i < count; ++i)
+ shouldBe('array[count + i]', 'twos[i]');
Modified: trunk/Source/_javascript_Core/ChangeLog (183287 => 183288)
--- trunk/Source/_javascript_Core/ChangeLog 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-04-24 23:02:29 UTC (rev 183288)
@@ -1,3 +1,134 @@
+2015-04-21 Geoffrey Garen <[email protected]>
+
+ 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-24 Matthew Mirman <[email protected]>
Made Object.prototype.__proto__ native getter and setter check that this object not null or undefined
Modified: trunk/Source/_javascript_Core/builtins/Array.prototype.js (183287 => 183288)
--- trunk/Source/_javascript_Core/builtins/Array.prototype.js 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/builtins/Array.prototype.js 2015-04-24 23:02:29 UTC (rev 183288)
@@ -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 @@
}
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 = "" 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 = ""
+ 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 = 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;
+}
Modified: trunk/Source/_javascript_Core/builtins/BuiltinExecutables.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/builtins/BuiltinExecutables.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/builtins/BuiltinExecutables.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -101,7 +101,6 @@
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));
Modified: trunk/Source/_javascript_Core/bytecode/CodeBlock.h (183287 => 183288)
--- trunk/Source/_javascript_Core/bytecode/CodeBlock.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/bytecode/CodeBlock.h 2015-04-24 23:02:29 UTC (rev 183288)
@@ -249,8 +249,6 @@
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; }
Modified: trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -241,7 +241,6 @@
, 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)
Modified: trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.h (183287 => 183288)
--- trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.h 2015-04-24 23:02:29 UTC (rev 183288)
@@ -344,9 +344,6 @@
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); }
@@ -536,7 +533,6 @@
unsigned m_needsFullScopeChain : 1;
unsigned m_usesEval : 1;
- unsigned m_isNumericCompareFunction : 1;
unsigned m_isStrictMode : 1;
unsigned m_isConstructor : 1;
unsigned m_hasCapturedVariables : 1;
Modified: trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -2603,11 +2603,6 @@
return newTemporary();
}
-void BytecodeGenerator::setIsNumericCompareFunction(bool isNumericCompareFunction)
-{
- m_codeBlock->setIsNumericCompareFunction(isNumericCompareFunction);
-}
-
bool BytecodeGenerator::isArgumentNumber(const Identifier& ident, int argumentNumber)
{
RegisterID* registerID = variable(ident).local();
Modified: trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.h (183287 => 183288)
--- trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.h 2015-04-24 23:02:29 UTC (rev 183288)
@@ -276,8 +276,6 @@
bool isArgumentNumber(const Identifier&, int);
- void setIsNumericCompareFunction(bool isNumericCompareFunction);
-
Variable variable(const Identifier&);
// Ignores the possibility of intervening scopes.
Modified: trunk/Source/_javascript_Core/bytecompiler/NodesCodegen.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/bytecompiler/NodesCodegen.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/bytecompiler/NodesCodegen.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -2821,22 +2821,6 @@
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 ---------------------------------
Modified: trunk/Source/_javascript_Core/heap/Heap.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/heap/Heap.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/heap/Heap.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -481,17 +481,6 @@
}
}
-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 @@
visitSmallStrings();
visitConservativeRoots(conservativeRoots);
visitProtectedObjects(heapRootVisitor);
- visitTempSortVectors(heapRootVisitor);
visitArgumentBuffers(heapRootVisitor);
visitException(heapRootVisitor);
visitStrongHandles(heapRootVisitor);
@@ -710,23 +698,6 @@
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);
Modified: trunk/Source/_javascript_Core/heap/Heap.h (183287 => 183288)
--- trunk/Source/_javascript_Core/heap/Heap.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/heap/Heap.h 2015-04-24 23:02:29 UTC (rev 183288)
@@ -75,7 +75,6 @@
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 @@
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 @@
void visitCompilerWorklistWeakReferences();
void removeDeadCompilerWorklistEntries();
void visitProtectedObjects(HeapRootVisitor&);
- void visitTempSortVectors(HeapRootVisitor&);
void visitArgumentBuffers(HeapRootVisitor&);
void visitException(HeapRootVisitor&);
void visitStrongHandles(HeapRootVisitor&);
@@ -371,7 +366,6 @@
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;
Modified: trunk/Source/_javascript_Core/parser/Parser.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/parser/Parser.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/parser/Parser.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -288,7 +288,6 @@
features |= ModifiedArgumentsFeature;
Vector<RefPtr<StringImpl>> closedVariables;
if (m_parsingBuiltin) {
- RELEASE_ASSERT(!capturedVariables.size());
IdentifierSet usedVariables;
scope->getUsedVariables(usedVariables);
for (const auto& variable : usedVariables) {
Modified: trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -54,7 +54,6 @@
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 @@
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 @@
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
Modified: trunk/Source/_javascript_Core/runtime/CommonIdentifiers.h (183287 => 183288)
--- trunk/Source/_javascript_Core/runtime/CommonIdentifiers.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/runtime/CommonIdentifiers.h 2015-04-24 23:02:29 UTC (rev 183288)
@@ -269,9 +269,12 @@
macro(objectGetOwnPropertySymbols) \
macro(Number) \
macro(Array) \
+ macro(String) \
macro(abs) \
macro(floor) \
macro(isFinite) \
+ macro(getPrototypeOf) \
+ macro(getOwnPropertyNames) \
macro(TypeError) \
macro(undefined) \
macro(BuiltinLog) \
Modified: trunk/Source/_javascript_Core/runtime/JSArray.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/runtime/JSArray.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/runtime/JSArray.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -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 @@
}
}
-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 = ""
-
- 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 @@
}
}
-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
Modified: trunk/Source/_javascript_Core/runtime/JSArray.h (183287 => 183288)
--- trunk/Source/_javascript_Core/runtime/JSArray.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/runtime/JSArray.h 2015-04-24 23:02:29 UTC (rev 183288)
@@ -70,10 +70,6 @@
// 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 @@
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)
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalObject.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/runtime/JSGlobalObject.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalObject.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -445,8 +445,11 @@
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),
Modified: trunk/Source/_javascript_Core/runtime/ObjectConstructor.cpp (183287 => 183288)
--- trunk/Source/_javascript_Core/runtime/ObjectConstructor.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/_javascript_Core/runtime/ObjectConstructor.cpp 2015-04-24 23:02:29 UTC (rev 183288)
@@ -96,6 +96,9 @@
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);
}
bool ObjectConstructor::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot &slot)
Modified: trunk/Source/WTF/ChangeLog (183287 => 183288)
--- trunk/Source/WTF/ChangeLog 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/WTF/ChangeLog 2015-04-24 23:02:29 UTC (rev 183288)
@@ -1,3 +1,19 @@
+2015-04-21 Geoffrey Garen <[email protected]>
+
+ 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-24 Darin Adler <[email protected]>
Convert OwnPtr and PassOwnPtr uses to std::unique_ptr
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (183287 => 183288)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-04-24 23:02:29 UTC (rev 183288)
@@ -163,7 +163,6 @@
<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" />
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters (183287 => 183288)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-04-24 23:02:29 UTC (rev 183288)
@@ -381,9 +381,6 @@
<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>
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (183287 => 183288)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-04-24 23:02:29 UTC (rev 183288)
@@ -107,7 +107,6 @@
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 */; };
@@ -392,7 +391,6 @@
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>"; };
@@ -696,7 +694,6 @@
A8A4725D151A825A004123FF /* Atomics.h */,
1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
- A8A4725E151A825A004123FF /* AVLTree.h */,
0FB14E18180FA218009B6B4D /* Bag.h */,
0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
A8A4725F151A825A004123FF /* Bitmap.h */,
@@ -1039,7 +1036,6 @@
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 */,
Deleted: trunk/Source/WTF/wtf/AVLTree.h (183287 => 183288)
--- trunk/Source/WTF/wtf/AVLTree.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/WTF/wtf/AVLTree.h 2015-04-24 23:02:29 UTC (rev 183288)
@@ -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
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (183287 => 183288)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-04-24 23:02:29 UTC (rev 183288)
@@ -1,6 +1,5 @@
set(WTF_HEADERS
ASCIICType.h
- AVLTree.h
Assertions.h
Atomics.h
Bag.h
