nephele
/
haikuwebkit
1
0
Fork 0
Code Issues Releases Activity
haikuwebkit/LayoutTests/js/array-sort-sparse-expected.txt

17 lines
436 B
Plaintext
Raw Permalink Normal View History

Sorting a non-array creates propreties (spec-violation) https://bugs.webkit.org/show_bug.cgi?id=25477 Reviewed by Oliver Hunt. Source/JavaScriptCore: We're just calling get() to get properties, which is converting missing properties to undefined. Hole values should be retained, and moved to the end of the array. * runtime/ArrayPrototype.cpp: (JSC::getOrHole): - Helper function, returns JSValue() instead of undefined for missing properties. (JSC::arrayProtoFuncSort): - Implemented per 15.4.4.11, see comments above. LayoutTests: Added test cases. * fast/js/array-sort-sparse-expected.txt: Added. * fast/js/array-sort-sparse.html: Added. * fast/js/script-tests/array-sort-sparse.js: Added. (testSort): Canonical link: https://commits.webkit.org/115357@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@129317 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2012-09-23 23:37:01 +00:00
This tests that arrays and array like objects containing holes are sorted correctly.
On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
PASS testSort([,undefined,0,1]) is true
PASS testSort({length:4,1:undefined,2:0,3:1}) is true
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. * script-tests/sort-with-side-effecting-comparisons.js: Made this test shorter so that it wouldn't hang debug builds. This test is O(N^2). It used to terminate sooner because our sort implementation would (sometimes) terminate sooner if you shrank the array. Our new sort does not accept intermediate updates to the array's length, matching Firefox. I spoke to Gavin and Alexey about this, and we think that going out of our way to honor length changes mid-sort doesn't make much sense because it's not possible to honor the general case of value changes in a predictable way. Canonical link: https://commits.webkit.org/162412@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@183570 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-04-29 19:48:00 +00:00
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
Sorting a non-array creates propreties (spec-violation) https://bugs.webkit.org/show_bug.cgi?id=25477 Reviewed by Oliver Hunt. Source/JavaScriptCore: We're just calling get() to get properties, which is converting missing properties to undefined. Hole values should be retained, and moved to the end of the array. * runtime/ArrayPrototype.cpp: (JSC::getOrHole): - Helper function, returns JSValue() instead of undefined for missing properties. (JSC::arrayProtoFuncSort): - Implemented per 15.4.4.11, see comments above. LayoutTests: Added test cases. * fast/js/array-sort-sparse-expected.txt: Added. * fast/js/array-sort-sparse.html: Added. * fast/js/script-tests/array-sort-sparse.js: Added. (testSort): Canonical link: https://commits.webkit.org/115357@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@129317 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2012-09-23 23:37:01 +00:00
PASS successfullyParsed is true
TEST COMPLETE