<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[183288] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/183288">183288</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2015-04-24 16:02:29 -0700 (Fri, 24 Apr 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>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.
Source/JavaScriptCore:
This patch implements Array.prototype.sort in JavaScript, removing the
C++ implementations. It is simpler and less error-prone to express our
operations in JavaScript, which provides memory safety, exception safety,
and recursion safety.
The performance result is mixed, but net positive in my opinion. It's
difficult to enumerate all the results, since we used to have so many
different sorting modes, and there are lots of different data patterns
across which you might want to measure sorting. Suffice it to say:
(*) The benchmarks we track are faster or unchanged.
(*) Sorting random input using a comparator -- which we think is
common -- is 3X faster.
(*) Sorting random input in a non-array object -- which jQuery does
-- is 4X faster.
(*) Sorting random input in a compact array of integers using a
trivial pattern-matchable comparator is 2X *slower*.
* builtins/Array.prototype.js:
(sort.min):
(sort.stringComparator):
(sort.compactSparse): Special case compaction for sparse arrays because
we don't want to hang when sorting new Array(BIG).
(sort.compact):
(sort.merge):
(sort.mergeSort): Use merge sort because it's a reasonably efficient
stable sort. We have evidence that some sites depend on stable sort,
even though the ES6 spec does not mandate it. (See
<http://trac.webkit.org/changeset/33967>.)
This is a textbook implementation of merge sort with three optimizations:
(1) Use iteration instead of recursion;
(2) Use array subscripting instead of array copying in order to
create logical sub-lists without creating physical sub-lists;
(3) Swap src and dst at each iteration instead of copying src into
dst, and only copy src into the subject array at the end if src is
not the subject array.
(sort.inflate):
(sort.comparatorSort):
(sort): Sort in JavaScript for the win.
* builtins/BuiltinExecutables.cpp:
(JSC::BuiltinExecutables::createExecutableInternal): Allow non-private
names so we can use helper functions.
* bytecode/CodeBlock.h:
(JSC::CodeBlock::isNumericCompareFunction): Deleted.
* bytecode/UnlinkedCodeBlock.cpp:
(JSC::UnlinkedCodeBlock::UnlinkedCodeBlock):
* bytecode/UnlinkedCodeBlock.h:
(JSC::UnlinkedCodeBlock::setIsNumericCompareFunction): Deleted.
(JSC::UnlinkedCodeBlock::isNumericCompareFunction): Deleted.
* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::setIsNumericCompareFunction): Deleted.
* bytecompiler/BytecodeGenerator.h:
* bytecompiler/NodesCodegen.cpp:
(JSC::FunctionNode::emitBytecode): We don't do this special casing based
on pattern matching anymore. This was mainly an optimization to avoid
the overhead of calling from C++ to JS, which we now avoid by
sorting in JS.
* heap/Heap.cpp:
(JSC::Heap::markRoots):
(JSC::Heap::pushTempSortVector): Deleted.
(JSC::Heap::popTempSortVector): Deleted.
(JSC::Heap::visitTempSortVectors): Deleted.
* heap/Heap.h: We don't have temp sort vectors anymore because we sort
in JavaScript using a normal JavaScript array for our temporary storage.
* parser/Parser.cpp:
(JSC::Parser<LexerType>::parseInner): Allow capturing so we can use
helper functions.
* runtime/ArrayPrototype.cpp:
(JSC::isNumericCompareFunction): Deleted.
(JSC::attemptFastSort): Deleted.
(JSC::performSlowSort): Deleted.
(JSC::arrayProtoFuncSort): Deleted.
* runtime/CommonIdentifiers.h: New strings used by sort.
* runtime/JSArray.cpp:
(JSC::compareNumbersForQSortWithInt32): Deleted.
(JSC::compareNumbersForQSortWithDouble): Deleted.
(JSC::compareNumbersForQSort): Deleted.
(JSC::compareByStringPairForQSort): Deleted.
(JSC::JSArray::sortNumericVector): Deleted.
(JSC::JSArray::sortNumeric): Deleted.
(JSC::ContiguousTypeAccessor::getAsValue): Deleted.
(JSC::ContiguousTypeAccessor::setWithValue): Deleted.
(JSC::ContiguousTypeAccessor::replaceDataReference): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::getAsValue): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::setWithValue): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::replaceDataReference): Deleted.
(JSC::JSArray::sortCompactedVector): Deleted.
(JSC::JSArray::sort): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_less): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_less): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_greater): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_greater): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_balance_factor): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_balance_factor): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_key_key): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_key_node): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_node_node): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::null): Deleted.
(JSC::JSArray::sortVector): Deleted.
(JSC::JSArray::compactForSorting): Deleted.
* runtime/JSArray.h:
* runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::init):
* runtime/ObjectConstructor.cpp:
(JSC::ObjectConstructor::finishCreation): Provide some builtins used
by sort.
Source/WTF:
Remove this custom tree implementation because it is unused. (It was
previously used to achieve a stable array sort in certain cases.)
* WTF.vcxproj/WTF.vcxproj:
* WTF.vcxproj/WTF.vcxproj.filters:
* WTF.xcodeproj/project.pbxproj:
* wtf/AVLTree.h: Removed.
* wtf/CMakeLists.txt:
LayoutTests:
* js/script-tests/array-holes.js:
* js/array-holes-expected.txt: This result now matches Firefox. We see
'peekaboo', which is a prototype property, rather than a hole, because
sorting uses [[Get]], which sees prototype properties.
The ES6 spec says that sorting should use [[Get]], so this new result
matches the spec a little better -- although the spec also says that the
result of sorting is undefined in this case because of the presence of
an indexed property in the prototype chain.
* js/dom/array-prototype-properties-expected.txt: Updated error message
to match other array prototype error messages.
* js/comparefn-sort-stability-expected.txt:
* js/script-tests/comparefn-sort-stability.js: Made this test bigger in
order to demonstrate that Firefox and Safari use a stable sort, and
Chrome does not.
* js/script-tests/array-sort-sparse.js:
* js/array-sort-sparse-expected.txt: Added some tests for things I got
wrong in this patch.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkLayoutTestsjsarrayholesexpectedtxt">trunk/LayoutTests/js/array-holes-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsarraysortsparseexpectedtxt">trunk/LayoutTests/js/array-sort-sparse-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjscomparefnsortstabilityexpectedtxt">trunk/LayoutTests/js/comparefn-sort-stability-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsdomarrayprototypepropertiesexpectedtxt">trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsscripttestsarrayholesjs">trunk/LayoutTests/js/script-tests/array-holes.js</a></li>
<li><a href="#trunkLayoutTestsjsscripttestsarraysortsparsejs">trunk/LayoutTests/js/script-tests/array-sort-sparse.js</a></li>
<li><a href="#trunkLayoutTestsjsscripttestscomparefnsortstabilityjs">trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCorebuiltinsArrayprototypejs">trunk/Source/JavaScriptCore/builtins/Array.prototype.js</a></li>
<li><a href="#trunkSourceJavaScriptCorebuiltinsBuiltinExecutablescpp">trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeCodeBlockh">trunk/Source/JavaScriptCore/bytecode/CodeBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockcpp">trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockh">trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorcpp">trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorh">trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecompilerNodesCodegencpp">trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapHeapcpp">trunk/Source/JavaScriptCore/heap/Heap.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapHeaph">trunk/Source/JavaScriptCore/heap/Heap.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreparserParsercpp">trunk/Source/JavaScriptCore/parser/Parser.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeArrayPrototypecpp">trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeCommonIdentifiersh">trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSArraycpp">trunk/Source/JavaScriptCore/runtime/JSArray.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSArrayh">trunk/Source/JavaScriptCore/runtime/JSArray.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSGlobalObjectcpp">trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeObjectConstructorcpp">trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFvcxprojWTFvcxproj">trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj</a></li>
<li><a href="#trunkSourceWTFWTFvcxprojWTFvcxprojfilters">trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
</ul>
<h3>Removed Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfAVLTreeh">trunk/Source/WTF/wtf/AVLTree.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/LayoutTests/ChangeLog 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -1,3 +1,32 @@
</span><ins>+2015-04-21 Geoffrey Garen <ggaren@apple.com>
+
+ It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+
+ Reviewed by Mark Lam.
+
+ * js/script-tests/array-holes.js:
+ * js/array-holes-expected.txt: This result now matches Firefox. We see
+ 'peekaboo', which is a prototype property, rather than a hole, because
+ sorting uses [[Get]], which sees prototype properties.
+
+ The ES6 spec says that sorting should use [[Get]], so this new result
+ matches the spec a little better -- although the spec also says that the
+ result of sorting is undefined in this case because of the presence of
+ an indexed property in the prototype chain.
+
+ * js/dom/array-prototype-properties-expected.txt: Updated error message
+ to match other array prototype error messages.
+
+ * js/comparefn-sort-stability-expected.txt:
+ * js/script-tests/comparefn-sort-stability.js: Made this test bigger in
+ order to demonstrate that Firefox and Safari use a stable sort, and
+ Chrome does not.
+
+ * js/script-tests/array-sort-sparse.js:
+ * js/array-sort-sparse-expected.txt: Added some tests for things I got
+ wrong in this patch.
+
</ins><span class="cx"> 2015-04-24 Alexey Proskuryakov <ap@apple.com>
</span><span class="cx">
</span><span class="cx"> fast/frames/flattening/iframe-flattening-resize-event-count.html times out on Yosemite WK2
</span></span></pre></div>
<a id="trunkLayoutTestsjsarrayholesexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/array-holes-expected.txt (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -36,7 +36,7 @@
</span><span class="cx"> PASS showHoles([0, , 2, 3].reverse()) is '[3, 2, peekaboo, 0]'
</span><span class="cx"> PASS a = [0, , 2, 3]; a.shift(); showHoles(a) is '[peekaboo, 2, 3]'
</span><span class="cx"> PASS showHoles([0, , 2, 3].slice(0, 3)) is '[0, peekaboo, 2]'
</span><del>-PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, hole]'
</del><ins>+PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, peekaboo]'
</ins><span class="cx"> PASS showHoles([0, undefined, 2, 3].sort()) is '[0, 2, 3, undefined]'
</span><span class="cx"> PASS a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a) is '[0, hole, 5, 6]'
</span><span class="cx"> PASS a = [0, , 2, 3]; a.unshift(4); showHoles(a) is '[4, 0, peekaboo, 2, 3]'
</span></span></pre></div>
<a id="trunkLayoutTestsjsarraysortsparseexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/array-sort-sparse-expected.txt (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -5,6 +5,11 @@
</span><span class="cx">
</span><span class="cx"> PASS testSort([,undefined,0,1]) is true
</span><span class="cx"> PASS testSort({length:4,1:undefined,2:0,3:1}) is true
</span><ins>+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
</ins><span class="cx"> PASS successfullyParsed is true
</span><span class="cx">
</span><span class="cx"> TEST COMPLETE
</span></span></pre></div>
<a id="trunkLayoutTestsjscomparefnsortstabilityexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/comparefn-sort-stability-expected.txt (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -3,14 +3,206 @@
</span><span class="cx"> On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
</span><span class="cx">
</span><span class="cx">
</span><del>-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]
</del><ins>+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]
</ins><span class="cx"> PASS successfullyParsed is true
</span><span class="cx">
</span><span class="cx"> TEST COMPLETE
</span></span></pre></div>
<a id="trunkLayoutTestsjsdomarrayprototypepropertiesexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -12,7 +12,7 @@
</span><span class="cx"> PASS Array.prototype.reverse.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.reverse.call(undefined)').
</span><span class="cx"> PASS Array.prototype.shift.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.shift.call(undefined)').
</span><span class="cx"> PASS Array.prototype.slice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.slice.call(undefined, 0, 1)').
</span><del>-PASS Array.prototype.sort.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.sort.call(undefined)').
</del><ins>+PASS Array.prototype.sort.call(undefined) threw exception TypeError: Array.prototype.sort requires that |this| not be undefined.
</ins><span class="cx"> PASS Array.prototype.splice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.splice.call(undefined, 0, 1)').
</span><span class="cx"> PASS Array.prototype.unshift.call(undefined, {}) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.unshift.call(undefined, {})').
</span><span class="cx"> PASS Array.prototype.every.call(undefined, toString) threw exception TypeError: Array.prototype.every requires that |this| not be undefined.
</span></span></pre></div>
<a id="trunkLayoutTestsjsscripttestsarrayholesjs"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/script-tests/array-holes.js (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -87,7 +87,7 @@
</span><span class="cx"> shouldBe("showHoles([0, , 2, 3].reverse())", "'[3, 2, peekaboo, 0]'");
</span><span class="cx"> shouldBe("a = [0, , 2, 3]; a.shift(); showHoles(a)", "'[peekaboo, 2, 3]'");
</span><span class="cx"> shouldBe("showHoles([0, , 2, 3].slice(0, 3))", "'[0, peekaboo, 2]'");
</span><del>-shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, hole]'");
</del><ins>+shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, peekaboo]'");
</ins><span class="cx"> shouldBe("showHoles([0, undefined, 2, 3].sort())", "'[0, 2, 3, undefined]'");
</span><span class="cx"> shouldBe("a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a)", "'[0, hole, 5, 6]'");
</span><span class="cx"> shouldBe("a = [0, , 2, 3]; a.unshift(4); showHoles(a)", "'[4, 0, peekaboo, 2, 3]'");
</span></span></pre></div>
<a id="trunkLayoutTestsjsscripttestsarraysortsparsejs"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/script-tests/array-sort-sparse.js (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -10,3 +10,14 @@
</span><span class="cx">
</span><span class="cx"> shouldBeTrue("testSort([,undefined,0,1])");
</span><span class="cx"> shouldBeTrue("testSort({length:4,1:undefined,2:0,3:1})");
</span><ins>+
+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");
</ins></span></pre></div>
<a id="trunkLayoutTestsjsscripttestscomparefnsortstabilityjs"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -2,30 +2,25 @@
</span><span class="cx"> "This tests that sort(compareFn) is a stable sort."
</span><span class="cx"> );
</span><span class="cx">
</span><del>-function clone(source, target) {
- for (i = 0; i < source.length; i++) {
- target[i] = source[i];
- }
-}
</del><ins>+var count = 100;
</ins><span class="cx">
</span><del>-var arr = [];
-arr[0] = new Number(1);
-arr[1] = new Number(2);
-arr[2] = new Number(1);
-arr[3] = new Number(2);
</del><ins>+var ones = [];
+for (var i = 0; i < count; ++i)
+ ones.push(new Number(1));
</ins><span class="cx">
</span><del>-var sortArr = [];
-clone(arr, sortArr);
-sortArr.sort(function(a,b) { return a - b; });
</del><ins>+var twos = [];
+for (var i = 0; i < count; ++i)
+ twos.push(new Number(2));
</ins><span class="cx">
</span><del>-shouldBe('arr[0]', 'sortArr[0]');
-shouldBe('arr[1]', 'sortArr[2]');
-shouldBe('arr[2]', 'sortArr[1]');
-shouldBe('arr[3]', 'sortArr[3]');
</del><ins>+var array = [];
+for (var i = 0; i < count; ++i) {
+ array.push(ones[i]);
+ array.push(twos[i]);
+}
</ins><span class="cx">
</span><del>-// 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]');
</del><ins>+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]');
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -1,3 +1,134 @@
</span><ins>+2015-04-21 Geoffrey Garen <ggaren@apple.com>
+
+ It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+
+ Reviewed by Mark Lam.
+
+ This patch implements Array.prototype.sort in JavaScript, removing the
+ C++ implementations. It is simpler and less error-prone to express our
+ operations in JavaScript, which provides memory safety, exception safety,
+ and recursion safety.
+
+ The performance result is mixed, but net positive in my opinion. It's
+ difficult to enumerate all the results, since we used to have so many
+ different sorting modes, and there are lots of different data patterns
+ across which you might want to measure sorting. Suffice it to say:
+
+ (*) The benchmarks we track are faster or unchanged.
+
+ (*) Sorting random input using a comparator -- which we think is
+ common -- is 3X faster.
+
+ (*) Sorting random input in a non-array object -- which jQuery does
+ -- is 4X faster.
+
+ (*) Sorting random input in a compact array of integers using a
+ trivial pattern-matchable comparator is 2X *slower*.
+
+ * builtins/Array.prototype.js:
+ (sort.min):
+ (sort.stringComparator):
+ (sort.compactSparse): Special case compaction for sparse arrays because
+ we don't want to hang when sorting new Array(BIG).
+
+ (sort.compact):
+ (sort.merge):
+ (sort.mergeSort): Use merge sort because it's a reasonably efficient
+ stable sort. We have evidence that some sites depend on stable sort,
+ even though the ES6 spec does not mandate it. (See
+ <http://trac.webkit.org/changeset/33967>.)
+
+ This is a textbook implementation of merge sort with three optimizations:
+
+ (1) Use iteration instead of recursion;
+
+ (2) Use array subscripting instead of array copying in order to
+ create logical sub-lists without creating physical sub-lists;
+
+ (3) Swap src and dst at each iteration instead of copying src into
+ dst, and only copy src into the subject array at the end if src is
+ not the subject array.
+
+ (sort.inflate):
+ (sort.comparatorSort):
+ (sort): Sort in JavaScript for the win.
+
+ * builtins/BuiltinExecutables.cpp:
+ (JSC::BuiltinExecutables::createExecutableInternal): Allow non-private
+ names so we can use helper functions.
+
+ * bytecode/CodeBlock.h:
+ (JSC::CodeBlock::isNumericCompareFunction): Deleted.
+ * bytecode/UnlinkedCodeBlock.cpp:
+ (JSC::UnlinkedCodeBlock::UnlinkedCodeBlock):
+ * bytecode/UnlinkedCodeBlock.h:
+ (JSC::UnlinkedCodeBlock::setIsNumericCompareFunction): Deleted.
+ (JSC::UnlinkedCodeBlock::isNumericCompareFunction): Deleted.
+ * bytecompiler/BytecodeGenerator.cpp:
+ (JSC::BytecodeGenerator::setIsNumericCompareFunction): Deleted.
+ * bytecompiler/BytecodeGenerator.h:
+ * bytecompiler/NodesCodegen.cpp:
+ (JSC::FunctionNode::emitBytecode): We don't do this special casing based
+ on pattern matching anymore. This was mainly an optimization to avoid
+ the overhead of calling from C++ to JS, which we now avoid by
+ sorting in JS.
+
+ * heap/Heap.cpp:
+ (JSC::Heap::markRoots):
+ (JSC::Heap::pushTempSortVector): Deleted.
+ (JSC::Heap::popTempSortVector): Deleted.
+ (JSC::Heap::visitTempSortVectors): Deleted.
+ * heap/Heap.h: We don't have temp sort vectors anymore because we sort
+ in JavaScript using a normal JavaScript array for our temporary storage.
+
+ * parser/Parser.cpp:
+ (JSC::Parser<LexerType>::parseInner): Allow capturing so we can use
+ helper functions.
+
+ * runtime/ArrayPrototype.cpp:
+ (JSC::isNumericCompareFunction): Deleted.
+ (JSC::attemptFastSort): Deleted.
+ (JSC::performSlowSort): Deleted.
+ (JSC::arrayProtoFuncSort): Deleted.
+
+ * runtime/CommonIdentifiers.h: New strings used by sort.
+
+ * runtime/JSArray.cpp:
+ (JSC::compareNumbersForQSortWithInt32): Deleted.
+ (JSC::compareNumbersForQSortWithDouble): Deleted.
+ (JSC::compareNumbersForQSort): Deleted.
+ (JSC::compareByStringPairForQSort): Deleted.
+ (JSC::JSArray::sortNumericVector): Deleted.
+ (JSC::JSArray::sortNumeric): Deleted.
+ (JSC::ContiguousTypeAccessor::getAsValue): Deleted.
+ (JSC::ContiguousTypeAccessor::setWithValue): Deleted.
+ (JSC::ContiguousTypeAccessor::replaceDataReference): Deleted.
+ (JSC::ContiguousTypeAccessor<ArrayWithDouble>::getAsValue): Deleted.
+ (JSC::ContiguousTypeAccessor<ArrayWithDouble>::setWithValue): Deleted.
+ (JSC::ContiguousTypeAccessor<ArrayWithDouble>::replaceDataReference): Deleted.
+ (JSC::JSArray::sortCompactedVector): Deleted.
+ (JSC::JSArray::sort): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::get_less): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::set_less): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::get_greater): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::set_greater): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::get_balance_factor): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::set_balance_factor): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::compare_key_key): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::compare_key_node): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::compare_node_node): Deleted.
+ (JSC::AVLTreeAbstractorForArrayCompare::null): Deleted.
+ (JSC::JSArray::sortVector): Deleted.
+ (JSC::JSArray::compactForSorting): Deleted.
+ * runtime/JSArray.h:
+
+ * runtime/JSGlobalObject.cpp:
+ (JSC::JSGlobalObject::init):
+ * runtime/ObjectConstructor.cpp:
+ (JSC::ObjectConstructor::finishCreation): Provide some builtins used
+ by sort.
+
</ins><span class="cx"> 2015-04-24 Matthew Mirman <mmirman@apple.com>
</span><span class="cx">
</span><span class="cx"> Made Object.prototype.__proto__ native getter and setter check that this object not null or undefined
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebuiltinsArrayprototypejs"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/builtins/Array.prototype.js (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/builtins/Array.prototype.js 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/builtins/Array.prototype.js 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -277,3 +277,185 @@
</span><span class="cx"> }
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><ins>+
+function sort(comparator)
+{
+ "use strict";
+
+ function min(a, b)
+ {
+ return a < b ? a : b;
+ }
+
+ function stringComparator(a, b)
+ {
+ var aString = @String(a);
+ var bString = @String(b);
+
+ var aLength = aString.length;
+ var bLength = bString.length;
+ var length = min(aLength, bLength);
+
+ for (var i = 0; i < length; ++i) {
+ var aCharCode = aString.@charCodeAt(i);
+ var bCharCode = bString.@charCodeAt(i);
+
+ if (aCharCode == bCharCode)
+ continue;
+
+ if (aCharCode < bCharCode)
+ return -1;
+
+ return 1;
+ }
+
+ if (aLength == bLength)
+ return 0;
+
+ if (aLength < bLength)
+ return -1;
+
+ return 1;
+ }
+
+ // Move undefineds and holes to the end of a sparse array. Result is [values..., undefineds..., holes...].
+ function compactSparse(array, dst, src, length)
+ {
+ var values = [ ];
+ var seen = { };
+ var valueCount = 0;
+ var undefinedCount = 0;
+
+ // Clean up after the in-progress non-sparse compaction that failed.
+ for (var i = dst; i < src; ++i)
+ delete array[i];
+
+ for (var object = array; object; object = @Object.@getPrototypeOf(object)) {
+ var propertyNames = @Object.@getOwnPropertyNames(object);
+ for (var i = 0; i < propertyNames.length; ++i) {
+ var index = propertyNames[i];
+ if (index < length) { // Exclude non-numeric properties and properties past length.
+ if (seen[index]) // Exclude duplicates.
+ continue;
+ seen[index] = 1;
+
+ var value = array[index];
+ delete array[index];
+
+ if (value === undefined) {
+ ++undefinedCount;
+ continue;
+ }
+
+ array[valueCount++] = value;
+ }
+ }
+ }
+
+ for (var i = valueCount; i < valueCount + undefinedCount; ++i)
+ array[i] = undefined;
+
+ return valueCount;
+ }
+
+ // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
+ function compact(array, length)
+ {
+ var holeCount = 0;
+
+ for (var dst = 0, src = 0; src < length; ++src) {
+ if (!(src in array)) {
+ ++holeCount;
+ if (holeCount < 256)
+ continue;
+ return compactSparse(array, dst, src, length);
+ }
+
+ var value = array[src];
+ if (value === undefined)
+ continue;
+ array[dst++] = value;
+ }
+
+ var valueCount = dst;
+ var undefinedCount = length - valueCount - holeCount;
+
+ for (var i = valueCount; i < valueCount + undefinedCount; ++i)
+ array[i] = undefined;
+
+ for (var i = valueCount + undefinedCount; i < length; ++i)
+ delete array[i];
+
+ return valueCount;
+ }
+
+ function merge(dst, src, srcIndex, srcEnd, width, comparator)
+ {
+ var left = srcIndex;
+ var leftEnd = min(left + width, srcEnd);
+ var right = leftEnd;
+ var rightEnd = min(right + width, srcEnd);
+
+ for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
+ if (right < rightEnd) {
+ if (left >= leftEnd || comparator(src[left], src[right]) > 0) {
+ dst[dstIndex] = src[right++];
+ continue;
+ }
+ }
+
+ dst[dstIndex] = src[left++];
+ }
+ }
+
+ function mergeSort(array, valueCount, comparator)
+ {
+ var buffer = [ ];
+ buffer.length = valueCount;
+
+ var dst = buffer;
+ var src = array;
+ for (var width = 1; width < valueCount; width *= 2) {
+ for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
+ merge(dst, src, srcIndex, valueCount, width, comparator);
+
+ var tmp = src;
+ src = dst;
+ dst = tmp;
+ }
+
+ if (src != array) {
+ for(var i = 0; i < valueCount; i++)
+ array[i] = src[i];
+ }
+ }
+
+ function comparatorSort(array, comparator)
+ {
+ var length = array.length >>> 0;
+
+ // For compatibility with Firefox and Chrome, do nothing observable
+ // to the target array if it has 0 or 1 sortable properties.
+ if (length < 2)
+ return;
+
+ var valueCount = compact(array, length);
+ mergeSort(array, valueCount, comparator);
+ }
+
+ if (this === null)
+ throw new @TypeError("Array.prototype.sort requires that |this| not be null");
+
+ if (this === undefined)
+ throw new @TypeError("Array.prototype.sort requires that |this| not be undefined");
+
+ if (typeof this == "string")
+ throw new @TypeError("Attempted to assign to readonly property.");
+
+ if (typeof comparator !== "function")
+ comparator = stringComparator;
+
+ var array = @Object(this);
+ comparatorSort(array, comparator);
+ return array;
+}
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCorebuiltinsBuiltinExecutablescpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -101,7 +101,6 @@
</span><span class="cx">
</span><span class="cx"> if (closedVariable == m_vm.propertyNames->undefinedKeyword.impl())
</span><span class="cx"> continue;
</span><del>- RELEASE_ASSERT(m_vm.propertyNames->isPrivateName(closedVariable.get()));
</del><span class="cx"> }
</span><span class="cx"> body->overrideName(name);
</span><span class="cx"> UnlinkedFunctionExecutable* functionExecutable = UnlinkedFunctionExecutable::create(&m_vm, source, body, kind, WTF::move(sourceOverride));
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeCodeBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/CodeBlock.h (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/CodeBlock.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/bytecode/CodeBlock.h 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -249,8 +249,6 @@
</span><span class="cx"> return static_cast<Instruction*>(returnAddress) - instructions().begin();
</span><span class="cx"> }
</span><span class="cx">
</span><del>- bool isNumericCompareFunction() { return m_unlinkedCode->isNumericCompareFunction(); }
-
</del><span class="cx"> unsigned numberOfInstructions() const { return m_instructions.size(); }
</span><span class="cx"> RefCountedArray<Instruction>& instructions() { return m_instructions; }
</span><span class="cx"> const RefCountedArray<Instruction>& instructions() const { return m_instructions; }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -241,7 +241,6 @@
</span><span class="cx"> , m_globalObjectRegister(VirtualRegister())
</span><span class="cx"> , m_needsFullScopeChain(info.needsActivation())
</span><span class="cx"> , m_usesEval(info.usesEval())
</span><del>- , m_isNumericCompareFunction(false)
</del><span class="cx"> , m_isStrictMode(info.isStrictMode())
</span><span class="cx"> , m_isConstructor(info.isConstructor())
</span><span class="cx"> , m_hasCapturedVariables(false)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -344,9 +344,6 @@
</span><span class="cx"> unsigned jumpTarget(int index) const { return m_jumpTargets[index]; }
</span><span class="cx"> unsigned lastJumpTarget() const { return m_jumpTargets.last(); }
</span><span class="cx">
</span><del>- void setIsNumericCompareFunction(bool isNumericCompareFunction) { m_isNumericCompareFunction = isNumericCompareFunction; }
- bool isNumericCompareFunction() const { return m_isNumericCompareFunction; }
-
</del><span class="cx"> bool isBuiltinFunction() const { return m_isBuiltinFunction; }
</span><span class="cx">
</span><span class="cx"> ConstructorKind constructorKind() const { return static_cast<ConstructorKind>(m_constructorKind); }
</span><span class="lines">@@ -536,7 +533,6 @@
</span><span class="cx">
</span><span class="cx"> unsigned m_needsFullScopeChain : 1;
</span><span class="cx"> unsigned m_usesEval : 1;
</span><del>- unsigned m_isNumericCompareFunction : 1;
</del><span class="cx"> unsigned m_isStrictMode : 1;
</span><span class="cx"> unsigned m_isConstructor : 1;
</span><span class="cx"> unsigned m_hasCapturedVariables : 1;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -2603,11 +2603,6 @@
</span><span class="cx"> return newTemporary();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void BytecodeGenerator::setIsNumericCompareFunction(bool isNumericCompareFunction)
-{
- m_codeBlock->setIsNumericCompareFunction(isNumericCompareFunction);
-}
-
</del><span class="cx"> bool BytecodeGenerator::isArgumentNumber(const Identifier& ident, int argumentNumber)
</span><span class="cx"> {
</span><span class="cx"> RegisterID* registerID = variable(ident).local();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -276,8 +276,6 @@
</span><span class="cx">
</span><span class="cx"> bool isArgumentNumber(const Identifier&, int);
</span><span class="cx">
</span><del>- void setIsNumericCompareFunction(bool isNumericCompareFunction);
-
</del><span class="cx"> Variable variable(const Identifier&);
</span><span class="cx">
</span><span class="cx"> // Ignores the possibility of intervening scopes.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecompilerNodesCodegencpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -2821,22 +2821,6 @@
</span><span class="cx"> generator.emitReturn(r0);
</span><span class="cx"> return;
</span><span class="cx"> }
</span><del>-
- // 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);
- }
- }
- }
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // ------------------------------ FuncDeclNode ---------------------------------
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/Heap.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/Heap.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/heap/Heap.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -481,17 +481,6 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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();
-}
-
</del><span class="cx"> void Heap::harvestWeakReferences()
</span><span class="cx"> {
</span><span class="cx"> m_slotVisitor.harvestWeakReferences();
</span><span class="lines">@@ -571,7 +560,6 @@
</span><span class="cx"> visitSmallStrings();
</span><span class="cx"> visitConservativeRoots(conservativeRoots);
</span><span class="cx"> visitProtectedObjects(heapRootVisitor);
</span><del>- visitTempSortVectors(heapRootVisitor);
</del><span class="cx"> visitArgumentBuffers(heapRootVisitor);
</span><span class="cx"> visitException(heapRootVisitor);
</span><span class="cx"> visitStrongHandles(heapRootVisitor);
</span><span class="lines">@@ -710,23 +698,6 @@
</span><span class="cx"> m_slotVisitor.donateAndDrain();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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();
-}
-
</del><span class="cx"> void Heap::visitArgumentBuffers(HeapRootVisitor& visitor)
</span><span class="cx"> {
</span><span class="cx"> GCPHASE(MarkingArgumentBuffers);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/Heap.h (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/Heap.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/heap/Heap.h 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -75,7 +75,6 @@
</span><span class="cx">
</span><span class="cx"> static void* const zombifiedBits = reinterpret_cast<void*>(0xdeadbeef);
</span><span class="cx">
</span><del>-typedef std::pair<JSValue, WTF::String> ValueStringPair;
</del><span class="cx"> typedef HashCountedSet<JSCell*> ProtectCountSet;
</span><span class="cx"> typedef HashCountedSet<const char*> TypeCountSet;
</span><span class="cx">
</span><span class="lines">@@ -186,9 +185,6 @@
</span><span class="cx"> JS_EXPORT_PRIVATE std::unique_ptr<TypeCountSet> objectTypeCounts();
</span><span class="cx"> void showStatistics();
</span><span class="cx">
</span><del>- void pushTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
- void popTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
-
</del><span class="cx"> HashSet<MarkedArgumentBuffer*>& markListSet();
</span><span class="cx">
</span><span class="cx"> template<typename Functor> typename Functor::ReturnType forEachProtectedCell(Functor&);
</span><span class="lines">@@ -300,7 +296,6 @@
</span><span class="cx"> void visitCompilerWorklistWeakReferences();
</span><span class="cx"> void removeDeadCompilerWorklistEntries();
</span><span class="cx"> void visitProtectedObjects(HeapRootVisitor&);
</span><del>- void visitTempSortVectors(HeapRootVisitor&);
</del><span class="cx"> void visitArgumentBuffers(HeapRootVisitor&);
</span><span class="cx"> void visitException(HeapRootVisitor&);
</span><span class="cx"> void visitStrongHandles(HeapRootVisitor&);
</span><span class="lines">@@ -371,7 +366,6 @@
</span><span class="cx"> HashSet<const JSCell*> m_copyingRememberedSet;
</span><span class="cx">
</span><span class="cx"> ProtectCountSet m_protectedValues;
</span><del>- Vector<Vector<ValueStringPair, 0, UnsafeVectorOverflow>*> m_tempSortingVectors;
</del><span class="cx"> std::unique_ptr<HashSet<MarkedArgumentBuffer*>> m_markListSet;
</span><span class="cx">
</span><span class="cx"> MachineThreads m_machineThreads;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreparserParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/parser/Parser.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/parser/Parser.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/parser/Parser.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -288,7 +288,6 @@
</span><span class="cx"> features |= ModifiedArgumentsFeature;
</span><span class="cx"> Vector<RefPtr<StringImpl>> closedVariables;
</span><span class="cx"> if (m_parsingBuiltin) {
</span><del>- RELEASE_ASSERT(!capturedVariables.size());
</del><span class="cx"> IdentifierSet usedVariables;
</span><span class="cx"> scope->getUsedVariables(usedVariables);
</span><span class="cx"> for (const auto& variable : usedVariables) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeArrayPrototypecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -54,7 +54,6 @@
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
</span><del>-EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*);
</del><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
</span><span class="lines">@@ -70,21 +69,6 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="cx">
</span><del>-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();
-}
-
</del><span class="cx"> // ------------------------------ ArrayPrototype ----------------------------
</span><span class="cx">
</span><span class="cx"> const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, &arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)};
</span><span class="lines">@@ -654,155 +638,6 @@
</span><span class="cx"> return JSValue();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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);
-}
-
</del><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
</span><span class="cx"> {
</span><span class="cx"> // 15.4.4.12
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeCommonIdentifiersh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -269,9 +269,12 @@
</span><span class="cx"> macro(objectGetOwnPropertySymbols) \
</span><span class="cx"> macro(Number) \
</span><span class="cx"> macro(Array) \
</span><ins>+ macro(String) \
</ins><span class="cx"> macro(abs) \
</span><span class="cx"> macro(floor) \
</span><span class="cx"> macro(isFinite) \
</span><ins>+ macro(getPrototypeOf) \
+ macro(getOwnPropertyNames) \
</ins><span class="cx"> macro(TypeError) \
</span><span class="cx"> macro(undefined) \
</span><span class="cx"> macro(BuiltinLog) \
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSArraycpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSArray.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSArray.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/runtime/JSArray.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -34,7 +34,6 @@
</span><span class="cx"> #include "JSCInlines.h"
</span><span class="cx"> #include "PropertyNameArray.h"
</span><span class="cx"> #include "Reject.h"
</span><del>-#include <wtf/AVLTree.h>
</del><span class="cx"> #include <wtf/Assertions.h>
</span><span class="cx">
</span><span class="cx"> using namespace std;
</span><span class="lines">@@ -994,521 +993,6 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static int compareNumbersForQSortWithInt32(const void* a, const void* b)
-{
- int32_t ia = static_cast<const JSValue*>(a)->asInt32();
- int32_t ib = static_cast<const JSValue*>(b)->asInt32();
- return ia - ib;
-}
-
-static int compareNumbersForQSortWithDouble(const void* a, const void* b)
-{
- double da = *static_cast<const double*>(a);
- double db = *static_cast<const double*>(b);
- return (da > db) - (da < db);
-}
-
-static int compareNumbersForQSort(const void* a, const void* b)
-{
- double da = static_cast<const JSValue*>(a)->asNumber();
- double db = static_cast<const JSValue*>(b)->asNumber();
- return (da > db) - (da < db);
-}
-
-static int compareByStringPairForQSort(const void* a, const void* b)
-{
- const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
- const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
- return codePointCompare(va->second, vb->second);
-}
-
-template<IndexingType arrayIndexingType>
-void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
- ASSERT(arrayIndexingType == ArrayWithInt32 || arrayIndexingType == ArrayWithDouble || arrayIndexingType == ArrayWithContiguous || arrayIndexingType == ArrayWithArrayStorage);
-
- unsigned lengthNotIncludingUndefined;
- unsigned newRelevantLength;
- compactForSorting<arrayIndexingType>(
- lengthNotIncludingUndefined,
- newRelevantLength);
-
- ContiguousJSValues data = indexingData<arrayIndexingType>();
-
- if (arrayIndexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
- throwOutOfMemoryError(exec);
- return;
- }
-
- if (!lengthNotIncludingUndefined)
- return;
-
- bool allValuesAreNumbers = true;
- switch (arrayIndexingType) {
- case ArrayWithInt32:
- case ArrayWithDouble:
- break;
-
- default:
- for (size_t i = 0; i < newRelevantLength; ++i) {
- if (!data[i].isNumber()) {
- allValuesAreNumbers = false;
- break;
- }
- }
- break;
- }
-
- if (!allValuesAreNumbers)
- return sort(exec, compareFunction, callType, callData);
-
- // For numeric comparison, which is fast, qsort is faster than mergesort. We
- // also don't require mergesort's stability, since there's no user visible
- // side-effect from swapping the order of equal primitive values.
- int (*compare)(const void*, const void*);
- switch (arrayIndexingType) {
- case ArrayWithInt32:
- compare = compareNumbersForQSortWithInt32;
- break;
-
- case ArrayWithDouble:
- compare = compareNumbersForQSortWithDouble;
- ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
- break;
-
- default:
- compare = compareNumbersForQSort;
- break;
- }
- ASSERT(data.length() >= newRelevantLength);
- qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
- return;
-}
-
-void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
- ASSERT(!inSparseIndexingMode());
-
- switch (indexingType()) {
- case ArrayClass:
- case ArrayWithUndecided:
- return;
-
- case ArrayWithInt32:
- sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
- return;
-
- case ArrayWithDouble:
- sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
- return;
-
- case ArrayWithContiguous:
- sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
- return;
-
- case ArrayWithArrayStorage:
- sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
- return;
-
- default:
- dataLog("Indexing type: ", indexingType(), "\n");
- RELEASE_ASSERT_NOT_REACHED();
- return;
- }
-}
-
-template <IndexingType> struct ContiguousTypeAccessor {
- typedef WriteBarrier<Unknown> Type;
- static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); }
- static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value)
- {
- data[i].set(vm, thisValue, value);
- }
- static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData)
- {
- *outData = inData;
- }
-};
-
-template <> struct ContiguousTypeAccessor<ArrayWithDouble> {
- typedef double Type;
- static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); }
- static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value)
- {
- data[i] = value.asNumber();
- }
- static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues)
- {
- RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort.");
- }
-};
-
-
-template<IndexingType arrayIndexingType, typename StorageType>
-void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> data, unsigned relevantLength)
-{
- if (!relevantLength)
- return;
-
- VM& vm = exec->vm();
-
- // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
- // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
- // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
- // random or otherwise changing results, effectively making compare function inconsistent.
-
- Vector<ValueStringPair, 0, UnsafeVectorOverflow> values(relevantLength);
- if (!values.begin()) {
- throwOutOfMemoryError(exec);
- return;
- }
-
- Heap::heap(this)->pushTempSortVector(&values);
-
- bool isSortingPrimitiveValues = true;
-
- for (size_t i = 0; i < relevantLength; i++) {
- JSValue value = ContiguousTypeAccessor<arrayIndexingType>::getAsValue(data, i);
- ASSERT(arrayIndexingType != ArrayWithInt32 || value.isInt32());
- ASSERT(!value.isUndefined());
- values[i].first = value;
- if (arrayIndexingType != ArrayWithDouble && arrayIndexingType != ArrayWithInt32)
- isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
- }
-
- // FIXME: The following loop continues to call toString on subsequent values even after
- // a toString call raises an exception.
-
- for (size_t i = 0; i < relevantLength; i++)
- values[i].second = values[i].first.toWTFStringInline(exec);
-
- if (exec->hadException()) {
- Heap::heap(this)->popTempSortVector(&values);
- return;
- }
-
- // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
- // than O(N log N).
-
-#if HAVE(MERGESORT)
- if (isSortingPrimitiveValues)
- qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
- else
- mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
-#else
- // FIXME: The qsort library function is likely to not be a stable sort.
- // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
- qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
-#endif
-
- // If the toString function changed the length of the array or vector storage,
- // increase the length to handle the orignal number of actual values.
- switch (arrayIndexingType) {
- case ArrayWithInt32:
- case ArrayWithDouble:
- case ArrayWithContiguous:
- ensureLength(vm, relevantLength);
- break;
-
- case ArrayWithArrayStorage:
- if (arrayStorage()->vectorLength() < relevantLength) {
- increaseVectorLength(exec->vm(), relevantLength);
- ContiguousTypeAccessor<arrayIndexingType>::replaceDataReference(&data, arrayStorage()->vector());
- }
- if (arrayStorage()->length() < relevantLength)
- arrayStorage()->setLength(relevantLength);
- break;
-
- default:
- CRASH();
- }
-
- for (size_t i = 0; i < relevantLength; i++)
- ContiguousTypeAccessor<arrayIndexingType>::setWithValue(vm, this, data, i, values[i].first);
-
- Heap::heap(this)->popTempSortVector(&values);
-}
-
-void JSArray::sort(ExecState* exec)
-{
- ASSERT(!inSparseIndexingMode());
-
- switch (indexingType()) {
- case ArrayClass:
- case ArrayWithUndecided:
- return;
-
- case ArrayWithInt32: {
- unsigned lengthNotIncludingUndefined;
- unsigned newRelevantLength;
- compactForSorting<ArrayWithInt32>(
- lengthNotIncludingUndefined, newRelevantLength);
-
- sortCompactedVector<ArrayWithInt32>(
- exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
- return;
- }
-
- case ArrayWithDouble: {
- unsigned lengthNotIncludingUndefined;
- unsigned newRelevantLength;
- compactForSorting<ArrayWithDouble>(
- lengthNotIncludingUndefined, newRelevantLength);
-
- sortCompactedVector<ArrayWithDouble>(
- exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
- return;
- }
-
- case ArrayWithContiguous: {
- unsigned lengthNotIncludingUndefined;
- unsigned newRelevantLength;
- compactForSorting<ArrayWithContiguous>(
- lengthNotIncludingUndefined, newRelevantLength);
-
- sortCompactedVector<ArrayWithContiguous>(
- exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
- return;
- }
-
- case ArrayWithArrayStorage: {
- unsigned lengthNotIncludingUndefined;
- unsigned newRelevantLength;
- compactForSorting<ArrayWithArrayStorage>(
- lengthNotIncludingUndefined, newRelevantLength);
- ArrayStorage* storage = m_butterfly->arrayStorage();
- ASSERT(!storage->m_sparseMap);
-
- sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined);
- return;
- }
-
- default:
- RELEASE_ASSERT_NOT_REACHED();
- }
-}
-
-struct AVLTreeNodeForArrayCompare {
- JSValue value;
-
- // Child pointers. The high bit of gt is robbed and used as the
- // balance factor sign. The high bit of lt is robbed and used as
- // the magnitude of the balance factor.
- int32_t gt;
- int32_t lt;
-};
-
-struct AVLTreeAbstractorForArrayCompare {
- typedef int32_t handle; // Handle is an index into m_nodes vector.
- typedef JSValue key;
- typedef int32_t size;
-
- Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes;
- ExecState* m_exec;
- JSValue m_compareFunction;
- CallType m_compareCallType;
- const CallData* m_compareCallData;
- std::unique_ptr<CachedCall> m_cachedCall;
-
- handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
- void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
- handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
- void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
-
- int get_balance_factor(handle h)
- {
- if (m_nodes[h].gt & 0x80000000)
- return -1;
- return static_cast<unsigned>(m_nodes[h].lt) >> 31;
- }
-
- void set_balance_factor(handle h, int bf)
- {
- if (bf == 0) {
- m_nodes[h].lt &= 0x7FFFFFFF;
- m_nodes[h].gt &= 0x7FFFFFFF;
- } else {
- m_nodes[h].lt |= 0x80000000;
- if (bf < 0)
- m_nodes[h].gt |= 0x80000000;
- else
- m_nodes[h].gt &= 0x7FFFFFFF;
- }
- }
-
- int compare_key_key(key va, key vb)
- {
- ASSERT(!va.isUndefined());
- ASSERT(!vb.isUndefined());
-
- if (m_exec->hadException())
- return 1;
-
- double compareResult;
- if (m_cachedCall) {
- m_cachedCall->setThis(jsUndefined());
- m_cachedCall->setArgument(0, va);
- m_cachedCall->setArgument(1, vb);
- compareResult = m_cachedCall->call().toNumber(m_exec);
- } else {
- MarkedArgumentBuffer arguments;
- arguments.append(va);
- arguments.append(vb);
- compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
- }
- return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
- }
-
- int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
- int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
-
- static handle null() { return 0x7FFFFFFF; }
-};
-
-template<IndexingType arrayIndexingType>
-void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
- ASSERT(!inSparseIndexingMode());
- ASSERT(arrayIndexingType == indexingType());
-
- // FIXME: This ignores exceptions raised in the compare function or in toNumber.
-
- // The maximum tree depth is compiled in - but the caller is clearly up to no good
- // if a larger array is passed.
- ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
- if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
- return;
-
- unsigned usedVectorLength = relevantLength<arrayIndexingType>();
- unsigned nodeCount = usedVectorLength;
-
- if (!nodeCount)
- return;
-
- AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
- tree.abstractor().m_exec = exec;
- tree.abstractor().m_compareFunction = compareFunction;
- tree.abstractor().m_compareCallType = callType;
- tree.abstractor().m_compareCallData = &callData;
- tree.abstractor().m_nodes.grow(nodeCount);
-
- if (callType == CallTypeJS)
- tree.abstractor().m_cachedCall = std::make_unique<CachedCall>(exec, jsCast<JSFunction*>(compareFunction), 2);
-
- if (!tree.abstractor().m_nodes.begin()) {
- throwOutOfMemoryError(exec);
- return;
- }
-
- // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
- // right out from under us while we're building the tree here.
-
- unsigned numDefined = 0;
- unsigned numUndefined = 0;
-
- // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
- for (; numDefined < usedVectorLength; ++numDefined) {
- if (numDefined >= m_butterfly->vectorLength())
- break;
- JSValue v = getHolyIndexQuickly(numDefined);
- if (!v || v.isUndefined())
- break;
- tree.abstractor().m_nodes[numDefined].value = v;
- tree.insert(numDefined);
- }
- for (unsigned i = numDefined; i < usedVectorLength; ++i) {
- if (i >= m_butterfly->vectorLength())
- break;
- JSValue v = getHolyIndexQuickly(i);
- if (v) {
- if (v.isUndefined())
- ++numUndefined;
- else {
- tree.abstractor().m_nodes[numDefined].value = v;
- tree.insert(numDefined);
- ++numDefined;
- }
- }
- }
-
- unsigned newUsedVectorLength = numDefined + numUndefined;
-
- // The array size may have changed. Figure out the new bounds.
- unsigned newestUsedVectorLength = currentRelevantLength();
-
- unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
- unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
- unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
-
- // Copy the values back into m_storage.
- AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
- iter.start_iter_least(tree);
- VM& vm = exec->vm();
- for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
- ASSERT(i < butterfly()->vectorLength());
- if (indexingType() == ArrayWithDouble)
- butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
- else
- currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value);
- ++iter;
- }
- // Put undefined values back in.
- switch (indexingType()) {
- case ArrayWithInt32:
- case ArrayWithDouble:
- ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
- break;
-
- default:
- for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) {
- ASSERT(i < butterfly()->vectorLength());
- currentIndexingData()[i].setUndefined();
- }
- }
-
- // Ensure that unused values in the vector are zeroed out.
- for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
- ASSERT(i < butterfly()->vectorLength());
- if (indexingType() == ArrayWithDouble)
- butterfly()->contiguousDouble()[i] = PNaN;
- else
- currentIndexingData()[i].clear();
- }
-
- if (hasAnyArrayStorage(indexingType()))
- arrayStorage()->m_numValuesInVector = newUsedVectorLength;
-}
-
-void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
- ASSERT(!inSparseIndexingMode());
-
- switch (indexingType()) {
- case ArrayClass:
- case ArrayWithUndecided:
- return;
-
- case ArrayWithInt32:
- sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
- return;
-
- case ArrayWithDouble:
- sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
- return;
-
- case ArrayWithContiguous:
- sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
- return;
-
- case ArrayWithArrayStorage:
- sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
- return;
-
- default:
- RELEASE_ASSERT_NOT_REACHED();
- }
-}
-
</del><span class="cx"> void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
</span><span class="cx"> {
</span><span class="cx"> unsigned i = 0;
</span><span class="lines">@@ -1639,95 +1123,4 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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;
-}
-
</del><span class="cx"> } // namespace JSC
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSArrayh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSArray.h (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSArray.h 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/runtime/JSArray.h 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -70,10 +70,6 @@
</span><span class="cx"> // OK to use on new arrays, but not if it might be a RegExpMatchArray.
</span><span class="cx"> JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
</span><span class="cx">
</span><del>- 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&);
-
</del><span class="cx"> JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
</span><span class="cx"> JS_EXPORT_PRIVATE JSValue pop(ExecState*);
</span><span class="cx">
</span><span class="lines">@@ -163,20 +159,8 @@
</span><span class="cx"> bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
</span><span class="cx"> bool unshiftCountSlowCase(VM&, bool, unsigned);
</span><span class="cx">
</span><del>- 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&);
-
</del><span class="cx"> bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
</span><span class="cx"> void setLengthWritable(ExecState*, bool writable);
</span><del>-
- template<IndexingType indexingType>
- void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength);
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSGlobalObjectcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -445,8 +445,11 @@
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->BuiltinLogPrivateName, builtinLog, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->ArrayPrivateName, arrayConstructor, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->NumberPrivateName, numberConstructor, DontEnum | DontDelete | ReadOnly),
</span><ins>+ GlobalPropertyInfo(vm.propertyNames->StringPrivateName, stringConstructor, DontEnum | DontDelete | ReadOnly),
</ins><span class="cx"> GlobalPropertyInfo(vm.propertyNames->absPrivateName, privateFuncAbs, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->floorPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
</span><ins>+ GlobalPropertyInfo(vm.propertyNames->getPrototypeOfPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
+ GlobalPropertyInfo(vm.propertyNames->getOwnPropertyNamesPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
</ins><span class="cx"> GlobalPropertyInfo(vm.propertyNames->isFinitePrivateName, privateFuncIsFinite, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->arrayIterationKindKeyPrivateName, jsNumber(ArrayIterateKey), DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->arrayIterationKindValuePrivateName, jsNumber(ArrayIterateValue), DontEnum | DontDelete | ReadOnly),
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeObjectConstructorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp 2015-04-24 22:31:31 UTC (rev 183287)
+++ trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp 2015-04-24 23:02:29 UTC (rev 183288)
</span><span class="lines">@@ -96,6 +96,9 @@
</span><span class="cx">
</span><span class="cx"> if (!globalObject->runtimeFlags().isSymbolDisabled())
</span><span class="cx"> JSC_NATIVE_FUNCTION("getOwnPropertySymbols", objectConstructorGetOwnPropertySymbols, DontEnum, 1);
</span><ins>+
+ JSC_NATIVE_FUNCTION(vm.propertyNames->getPrototypeOfPrivateName, objectConstructorGetPrototypeOf, DontEnum, 1);
+ JSC_NATIVE_FUNCTION(vm.propertyNames->getOwnPropertyNamesPrivateName, objectConstructorGetOwnPropertyNames, DontEnum, 1);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool ObjectConstructor::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot &slot)
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,3 +1,19 @@
</span><ins>+2015-04-21 Geoffrey Garen <ggaren@apple.com>
+
+ It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+
+ Reviewed by Mark Lam.
+
+ Remove this custom tree implementation because it is unused. (It was
+ previously used to achieve a stable array sort in certain cases.)
+
+ * WTF.vcxproj/WTF.vcxproj:
+ * WTF.vcxproj/WTF.vcxproj.filters:
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/AVLTree.h: Removed.
+ * wtf/CMakeLists.txt:
+
</ins><span class="cx"> 2015-04-24 Darin Adler <darin@apple.com>
</span><span class="cx">
</span><span class="cx"> Convert OwnPtr and PassOwnPtr uses to std::unique_ptr
</span></span></pre></div>
<a id="trunkSourceWTFWTFvcxprojWTFvcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -163,7 +163,6 @@
</span><span class="cx"> <ClInclude Include="..\wtf\Assertions.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\Atomics.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\AutodrainedPool.h" />
</span><del>- <ClInclude Include="..\wtf\AVLTree.h" />
</del><span class="cx"> <ClInclude Include="..\wtf\Bag.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\BagToHashMap.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\Bitmap.h" />
</span></span></pre></div>
<a id="trunkSourceWTFWTFvcxprojWTFvcxprojfilters"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -381,9 +381,6 @@
</span><span class="cx"> <ClInclude Include="..\wtf\Atomics.h">
</span><span class="cx"> <Filter>wtf</Filter>
</span><span class="cx"> </ClInclude>
</span><del>- <ClInclude Include="..\wtf\AVLTree.h">
- <Filter>wtf</Filter>
- </ClInclude>
</del><span class="cx"> <ClInclude Include="..\wtf\Bitmap.h">
</span><span class="cx"> <Filter>wtf</Filter>
</span><span class="cx"> </ClInclude>
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -107,7 +107,6 @@
</span><span class="cx"> A8A47386151A825B004123FF /* Assertions.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A4725B151A825A004123FF /* Assertions.cpp */; };
</span><span class="cx"> A8A47387151A825B004123FF /* Assertions.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725C151A825A004123FF /* Assertions.h */; };
</span><span class="cx"> A8A47388151A825B004123FF /* Atomics.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725D151A825A004123FF /* Atomics.h */; };
</span><del>- A8A47389151A825B004123FF /* AVLTree.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725E151A825A004123FF /* AVLTree.h */; };
</del><span class="cx"> A8A4738A151A825B004123FF /* Bitmap.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725F151A825A004123FF /* Bitmap.h */; };
</span><span class="cx"> A8A4738B151A825B004123FF /* BitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A47260151A825A004123FF /* BitVector.cpp */; };
</span><span class="cx"> A8A4738C151A825B004123FF /* BitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47261151A825A004123FF /* BitVector.h */; };
</span><span class="lines">@@ -392,7 +391,6 @@
</span><span class="cx"> A8A4725B151A825A004123FF /* Assertions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Assertions.cpp; sourceTree = "<group>"; };
</span><span class="cx"> A8A4725C151A825A004123FF /* Assertions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Assertions.h; sourceTree = "<group>"; };
</span><span class="cx"> A8A4725D151A825A004123FF /* Atomics.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Atomics.h; sourceTree = "<group>"; };
</span><del>- A8A4725E151A825A004123FF /* AVLTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AVLTree.h; sourceTree = "<group>"; };
</del><span class="cx"> A8A4725F151A825A004123FF /* Bitmap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Bitmap.h; sourceTree = "<group>"; };
</span><span class="cx"> A8A47260151A825A004123FF /* BitVector.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BitVector.cpp; sourceTree = "<group>"; };
</span><span class="cx"> A8A47261151A825A004123FF /* BitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BitVector.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -696,7 +694,6 @@
</span><span class="cx"> A8A4725D151A825A004123FF /* Atomics.h */,
</span><span class="cx"> 1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
</span><span class="cx"> 1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
</span><del>- A8A4725E151A825A004123FF /* AVLTree.h */,
</del><span class="cx"> 0FB14E18180FA218009B6B4D /* Bag.h */,
</span><span class="cx"> 0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
</span><span class="cx"> A8A4725F151A825A004123FF /* Bitmap.h */,
</span><span class="lines">@@ -1039,7 +1036,6 @@
</span><span class="cx"> A8A47438151A825B004123FF /* AtomicStringImpl.h in Headers */,
</span><span class="cx"> 9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */,
</span><span class="cx"> 1469419C16EAB10A0024E146 /* AutodrainedPool.h in Headers */,
</span><del>- A8A47389151A825B004123FF /* AVLTree.h in Headers */,
</del><span class="cx"> 8134013915B092FD001FF0B8 /* Base64.h in Headers */,
</span><span class="cx"> A8A473A9151A825B004123FF /* bignum-dtoa.h in Headers */,
</span><span class="cx"> A8A473AB151A825B004123FF /* bignum.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfAVLTreeh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/WTF/wtf/AVLTree.h (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,960 +0,0 @@
</span><del>-/*
- * 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
</del></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (183287 => 183288)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,6 +1,5 @@
</span><span class="cx"> set(WTF_HEADERS
</span><span class="cx"> ASCIICType.h
</span><del>- AVLTree.h
</del><span class="cx"> Assertions.h
</span><span class="cx"> Atomics.h
</span><span class="cx"> Bag.h
</span></span></pre>
</div>
</div>
</body>
</html>