From 5f1ae66d5634e43563b2d25ea652dfb94c31a3b4 Mon Sep 17 00:00:00 2001 From: "adamk@chromium.org" Date: Thu, 23 Oct 2014 18:21:50 +0000 Subject: [PATCH] Narrow cases where Sparse/Smart versions of Array methods are used Added a new %HasComplexElements runtime function (meaning elements that are non-writable, non-configurable, or have getters and setters) and use it in UseSparseVariant to filter out cases where the sparse optimizations can cause V8 to fall out of spec compliance. Renamed SmartMove/SmartSlice to SparseMove/SparseSlice and guarded them with the new and improved UseSparseVariant. These two changes combine let us pass nearly every test in bug-2615.js, as well as fixing reverse and join on sparse arrays. Note that there are various test changes in this patch that correct existing tests to match the correct-by-spec behavior. This patch depends on https://codereview.chromium.org/666883009, which better-aligns the behavior of SmartMove with SimpleMove. BUG=v8:2615,v8:3612,v8:3621 LOG=y R=mstarzinger@chromium.org Review URL: https://codereview.chromium.org/656423004 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24855 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/array.js | 23 +++--- src/objects.cc | 30 +++++-- src/objects.h | 4 + src/runtime/runtime-array.cc | 24 ++++++ src/runtime/runtime.h | 1 + test/mjsunit/array-natives-elements.js | 3 +- test/mjsunit/array-shift2.js | 16 +++- test/mjsunit/bugs/bug-2615.js | 86 ------------------- test/mjsunit/regress/regress-2615.js | 96 ++++++++++++++++++++++ .../{bugs/bug-3612.js => regress/regress-3612.js} | 0 .../{bugs/bug-3621.js => regress/regress-3621.js} | 0 test/mjsunit/regress/regress-crbug-412319.js | 2 +- test/mozilla/mozilla.status | 8 +- 13 files changed, 181 insertions(+), 112 deletions(-) create mode 100644 test/mjsunit/regress/regress-2615.js rename test/mjsunit/{bugs/bug-3612.js => regress/regress-3612.js} (100%) rename test/mjsunit/{bugs/bug-3621.js => regress/regress-3621.js} (100%) diff --git a/src/array.js b/src/array.js index 2a447d9..9fbc67c 100644 --- a/src/array.js +++ b/src/array.js @@ -90,7 +90,8 @@ function UseSparseVariant(array, length, is_array, touched) { // Only use the sparse variant on arrays that are likely to be sparse and the // number of elements touched in the operation is relatively small compared to // the overall size of the array. - if (!is_array || length < 1000 || %IsObserved(array)) { + if (!is_array || length < 1000 || %IsObserved(array) || + %HasComplexElements(array)) { return false; } if (!%_IsSmi(length)) { @@ -203,7 +204,7 @@ function ConvertToLocaleString(e) { // This function implements the optimized splice implementation that can use // special array operations to handle sparse arrays in a sensible fashion. -function SmartSlice(array, start_i, del_count, len, deleted_elements) { +function SparseSlice(array, start_i, del_count, len, deleted_elements) { // Move deleted elements to a new array (the return value from splice). var indices = %GetArrayKeys(array, start_i + del_count); if (IS_NUMBER(indices)) { @@ -233,7 +234,7 @@ function SmartSlice(array, start_i, del_count, len, deleted_elements) { // This function implements the optimized splice implementation that can use // special array operations to handle sparse arrays in a sensible fashion. -function SmartMove(array, start_i, del_count, len, num_additional_args) { +function SparseMove(array, start_i, del_count, len, num_additional_args) { // Bail out if no moving is necessary. if (num_additional_args === del_count) return; // Move data to new array. @@ -608,8 +609,8 @@ function ArrayShift() { var first = array[0]; - if (IS_ARRAY(array)) { - SmartMove(array, 0, 1, len, 0); + if (UseSparseVariant(array, len, IS_ARRAY(array), len)) { + SparseMove(array, 0, 1, len, 0); } else { SimpleMove(array, 0, 1, len, 0); } @@ -648,10 +649,10 @@ function ArrayUnshift(arg1) { // length == 1 var array = TO_OBJECT_INLINE(this); var len = TO_UINT32(array.length); var num_arguments = %_ArgumentsLength(); - var is_sealed = ObjectIsSealed(array); - if (IS_ARRAY(array) && !is_sealed && len > 0) { - SmartMove(array, 0, 0, len, num_arguments); + if (len > 0 && UseSparseVariant(array, len, IS_ARRAY(array), len) && + !ObjectIsSealed(array)) { + SparseMove(array, 0, 0, len, num_arguments); } else { SimpleMove(array, 0, 0, len, num_arguments); } @@ -697,7 +698,7 @@ function ArraySlice(start, end) { if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) { %NormalizeElements(array); %NormalizeElements(result); - SmartSlice(array, start_i, end_i - start_i, len, result); + SparseSlice(array, start_i, end_i - start_i, len, result); } else { SimpleSlice(array, start_i, end_i - start_i, len, result); } @@ -813,8 +814,8 @@ function ArraySplice(start, delete_count) { if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) { %NormalizeElements(array); %NormalizeElements(deleted_elements); - SmartSlice(array, start_i, del_count, len, deleted_elements); - SmartMove(array, start_i, del_count, len, num_elements_to_add); + SparseSlice(array, start_i, del_count, len, deleted_elements); + SparseMove(array, start_i, del_count, len, num_elements_to_add); } else { SimpleSlice(array, start_i, del_count, len, deleted_elements); SimpleMove(array, start_i, del_count, len, num_elements_to_add); diff --git a/src/objects.cc b/src/objects.cc index 5496b7e..4359f17 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -14212,9 +14212,11 @@ template int Dictionary >:: NumberOfEnumElements(); -template -int HashTable:: - FindEntry(uint32_t); +template bool Dictionary::HasComplexElements(); + +template int HashTable::FindEntry(uint32_t); Handle JSObject::PrepareSlowElementsForSort( @@ -15262,10 +15264,26 @@ int Dictionary::NumberOfEnumElements() { } -template +template +bool Dictionary::HasComplexElements() { + int capacity = DerivedHashTable::Capacity(); + for (int i = 0; i < capacity; i++) { + Object* k = DerivedHashTable::KeyAt(i); + if (DerivedHashTable::IsKey(k) && !FilterKey(k, NONE)) { + PropertyDetails details = DetailsAt(i); + if (details.IsDeleted()) continue; + if (details.type() == CALLBACKS) return true; + PropertyAttributes attr = details.attributes(); + if (attr & (READ_ONLY | DONT_DELETE)) return true; + } + } + return false; +} + + +template void Dictionary::CopyKeysTo( - FixedArray* storage, - PropertyAttributes filter, + FixedArray* storage, PropertyAttributes filter, typename Dictionary::SortMode sort_mode) { DCHECK(storage->length() >= NumberOfElementsFilterAttributes(filter)); int capacity = DerivedHashTable::Capacity(); diff --git a/src/objects.h b/src/objects.h index 6eb2697..649111d 100644 --- a/src/objects.h +++ b/src/objects.h @@ -3550,6 +3550,10 @@ class Dictionary: public HashTable { // Returns the number of enumerable elements in the dictionary. int NumberOfEnumElements(); + // Returns true if the dictionary contains any elements that are non-writable, + // non-configurable, or have getters/setters. + bool HasComplexElements(); + enum SortMode { UNSORTED, SORTED }; // Copies keys to preallocated fixed array. void CopyKeysTo(FixedArray* storage, diff --git a/src/runtime/runtime-array.cc b/src/runtime/runtime-array.cc index 5a6bba4..c3a6d80 100644 --- a/src/runtime/runtime-array.cc +++ b/src/runtime/runtime-array.cc @@ -1043,6 +1043,30 @@ RUNTIME_FUNCTION(Runtime_NormalizeElements) { } +RUNTIME_FUNCTION(Runtime_HasComplexElements) { + HandleScope scope(isolate); + DCHECK(args.length() == 1); + CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0); + for (PrototypeIterator iter(isolate, array, + PrototypeIterator::START_AT_RECEIVER); + !iter.IsAtEnd(); iter.Advance()) { + if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) { + return isolate->heap()->true_value(); + } + Handle current = + Handle::cast(PrototypeIterator::GetCurrent(iter)); + if (current->HasIndexedInterceptor()) { + return isolate->heap()->true_value(); + } + if (!current->HasDictionaryElements()) continue; + if (current->element_dictionary()->HasComplexElements()) { + return isolate->heap()->true_value(); + } + } + return isolate->heap()->false_value(); +} + + // TODO(dcarney): remove this function when TurboFan supports it. // Takes the object to be iterated over and the result of GetPropertyNamesFast // Returns pair (cache_array, cache_type). diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index 0217439..657a17d 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -268,6 +268,7 @@ namespace internal { F(MoveArrayContents, 2, 1) \ F(EstimateNumberOfElements, 1, 1) \ F(NormalizeElements, 1, 1) \ + F(HasComplexElements, 1, 1) \ \ /* Getters and Setters */ \ F(LookupAccessor, 3, 1) \ diff --git a/test/mjsunit/array-natives-elements.js b/test/mjsunit/array-natives-elements.js index d63346d..e567e7f 100644 --- a/test/mjsunit/array-natives-elements.js +++ b/test/mjsunit/array-natives-elements.js @@ -280,8 +280,7 @@ function array_natives_test() { assertEquals([1.1,1,2,3], a4); a4 = [1.1,2,3]; a4.unshift(1); - // assertTrue(%HasFastDoubleElements(a4)); - assertTrue(%HasFastObjectElements(a4)); + assertTrue(%HasFastDoubleElements(a4)); assertEquals([1,1.1,2,3], a4); a4 = [{},2,3]; a4.unshift(1); diff --git a/test/mjsunit/array-shift2.js b/test/mjsunit/array-shift2.js index 73d8cd4..75233ff 100644 --- a/test/mjsunit/array-shift2.js +++ b/test/mjsunit/array-shift2.js @@ -12,7 +12,17 @@ function test(array) { array.shift(); return array; } -assertEquals(["element 1",2], test(["0",,2])); -assertEquals(["element 1",{}], test([{},,{}])); + +var result = test(["0",,2]); +assertEquals(["element 1","element 1"], result); +assertTrue(result.hasOwnProperty("0")); +assertFalse(result.hasOwnProperty("1")); +result = test([{},,{}]); +assertEquals(["element 1","element 1"], result); +assertTrue(result.hasOwnProperty("0")); +assertFalse(result.hasOwnProperty("1")); %OptimizeFunctionOnNextCall(test); -assertEquals(["element 1",0], test([{},,0])); +result = test([{},,0]); +assertEquals(["element 1","element 1"], result); +assertTrue(result.hasOwnProperty("0")); +assertFalse(result.hasOwnProperty("1")); diff --git a/test/mjsunit/bugs/bug-2615.js b/test/mjsunit/bugs/bug-2615.js index 51aeaf4..5da17ee 100644 --- a/test/mjsunit/bugs/bug-2615.js +++ b/test/mjsunit/bugs/bug-2615.js @@ -38,89 +38,3 @@ assertThrows("a.splice(1,1,7,7,7,7,7);", RangeError); assertEquals([1,7,7,7,7,7,3], a.slice(0, 7)); assertEquals(0xffffffff, a.length); assertEquals(10, a[0xfffffffe + 5 - 1]); - -a = [1]; -Object.defineProperty(a, "1", {writable:false, configurable:false, value: 100}); -assertThrows("a.unshift(4);", TypeError); -assertEquals([1, 100, 100], a); -var desc = Object.getOwnPropertyDescriptor(a, "1"); -assertEquals(false, desc.writable); -assertEquals(false, desc.configurable); - -a = [1]; -var g = function() { return 100; }; -Object.defineProperty(a, "1", {get:g}); -assertThrows("a.unshift(0);", TypeError); -assertEquals([1, 100, 100], a); -desc = Object.getOwnPropertyDescriptor(a, "1"); -assertEquals(false, desc.configurable); -assertEquals(g, desc.get); - -a = [1]; -var c = 0; -var s = function(v) { c += 1; }; -Object.defineProperty(a, "1", {set:s}); -a.unshift(10); -assertEquals([10, undefined, undefined], a); -assertEquals(1, c); -desc = Object.getOwnPropertyDescriptor(a, "1"); -assertEquals(false, desc.configurable); -assertEquals(s, desc.set); - -a = [1]; -Object.defineProperty(a, "1", {configurable:false, value:10}); -assertThrows("a.splice(1,1);", TypeError); -assertEquals([1, 10], a); -desc = Object.getOwnPropertyDescriptor(a, "1"); -assertEquals(false, desc.configurable); - -a = [0,1,2,3,4,5,6]; -Object.defineProperty(a, "3", {configurable:false, writable:false, value:3}); -assertThrows("a.splice(1,4);", TypeError); -assertEquals([0,5,6,3,,,,,], a); -desc = Object.getOwnPropertyDescriptor(a, "3"); -assertEquals(false, desc.configurable); -assertEquals(false, desc.writable); - -a = [0,1,2,3,4,5,6]; -Object.defineProperty(a, "5", {configurable:false, value:5}); -assertThrows("a.splice(1,4);", TypeError); -assertEquals([0,5,6,3,4,5,,,], a); -desc = Object.getOwnPropertyDescriptor(a, "5"); -assertEquals(false, desc.configurable); - -a = [1,2,3,,5]; -Object.defineProperty(a, "1", {configurable:false, writable:true, value:2}); -assertEquals(1, a.shift()); -assertEquals([2,3,,5], a); -desc = Object.getOwnPropertyDescriptor(a, "1"); -assertEquals(false, desc.configurable); -assertEquals(true, desc.writable); -assertThrows("a.shift();", TypeError); -assertEquals([3,3,,5], a); -desc = Object.getOwnPropertyDescriptor(a, "1"); -assertEquals(false, desc.configurable); -assertEquals(true, desc.writable); - -a = [1,2,3]; -Object.defineProperty(a, "2", {configurable:false, value:3}); -assertThrows("a.pop();", TypeError); -assertEquals([1,2,3], a); -desc = Object.getOwnPropertyDescriptor(a, "2"); -assertEquals(false, desc.configurable); - -a = [1,2,,,5]; -Object.defineProperty(a, "4", {writable:true, configurable:false, value:5}); -assertThrows("a.sort();", TypeError); -assertEquals([1,2,5,,5], a); -desc = Object.getOwnPropertyDescriptor(a, "2"); -assertEquals(true, desc.configurable); -desc = Object.getOwnPropertyDescriptor(a, "4"); -assertEquals(false, desc.configurable); - -a = [1,2,3,,5,6]; -Object.defineProperty(a, "4", {value:5, writable:false}); -assertThrows("a.sort();", TypeError); -assertEquals([1,2,3,5,5,6], a); -desc = Object.getOwnPropertyDescriptor(a, "4"); -assertEquals(false, desc.writable); diff --git a/test/mjsunit/regress/regress-2615.js b/test/mjsunit/regress/regress-2615.js new file mode 100644 index 0000000..6b277e8 --- /dev/null +++ b/test/mjsunit/regress/regress-2615.js @@ -0,0 +1,96 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * 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. +// * Neither the name of Google Inc. 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 THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT +// OWNER OR 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. + +a = [1]; +Object.defineProperty(a, "1", {writable:false, configurable:false, value: 100}); +assertThrows("a.unshift(4);", TypeError); +assertEquals([1, 100, 100], a); +var desc = Object.getOwnPropertyDescriptor(a, "1"); +assertEquals(false, desc.writable); +assertEquals(false, desc.configurable); + +a = [1]; +var g = function() { return 100; }; +Object.defineProperty(a, "1", {get:g}); +assertThrows("a.unshift(0);", TypeError); +assertEquals([1, 100, 100], a); +desc = Object.getOwnPropertyDescriptor(a, "1"); +assertEquals(false, desc.configurable); +assertEquals(g, desc.get); + +a = [1]; +var c = 0; +var s = function(v) { c += 1; }; +Object.defineProperty(a, "1", {set:s}); +a.unshift(10); +assertEquals([10, undefined, undefined], a); +assertEquals(1, c); +desc = Object.getOwnPropertyDescriptor(a, "1"); +assertEquals(false, desc.configurable); +assertEquals(s, desc.set); + +a = [1]; +Object.defineProperty(a, "1", {configurable:false, value:10}); +assertThrows("a.splice(1,1);", TypeError); +assertEquals([1, 10], a); +desc = Object.getOwnPropertyDescriptor(a, "1"); +assertEquals(false, desc.configurable); + +a = [0,1,2,3,4,5,6]; +Object.defineProperty(a, "3", {configurable:false, writable:false, value:3}); +assertThrows("a.splice(1,4);", TypeError); +assertEquals([0,5,6,3,,,,], a); +desc = Object.getOwnPropertyDescriptor(a, "3"); +assertEquals(false, desc.configurable); +assertEquals(false, desc.writable); + +a = [0,1,2,3,4,5,6]; +Object.defineProperty(a, "5", {configurable:false, value:5}); +assertThrows("a.splice(1,4);", TypeError); +assertEquals([0,5,6,3,4,5,,], a); +desc = Object.getOwnPropertyDescriptor(a, "5"); +assertEquals(false, desc.configurable); + +a = [1,2,3,,5]; +Object.defineProperty(a, "1", {configurable:false, writable:true, value:2}); +assertEquals(1, a.shift()); +assertEquals([2,3,,5], a); +desc = Object.getOwnPropertyDescriptor(a, "1"); +assertEquals(false, desc.configurable); +assertEquals(true, desc.writable); +assertThrows("a.shift();", TypeError); +assertEquals([3,3,,5], a); +desc = Object.getOwnPropertyDescriptor(a, "1"); +assertEquals(false, desc.configurable); +assertEquals(true, desc.writable); + +a = [1,2,3]; +Object.defineProperty(a, "2", {configurable:false, value:3}); +assertThrows("a.pop();", TypeError); +assertEquals([1,2,3], a); +desc = Object.getOwnPropertyDescriptor(a, "2"); +assertEquals(false, desc.configurable); diff --git a/test/mjsunit/bugs/bug-3612.js b/test/mjsunit/regress/regress-3612.js similarity index 100% rename from test/mjsunit/bugs/bug-3612.js rename to test/mjsunit/regress/regress-3612.js diff --git a/test/mjsunit/bugs/bug-3621.js b/test/mjsunit/regress/regress-3621.js similarity index 100% rename from test/mjsunit/bugs/bug-3621.js rename to test/mjsunit/regress/regress-3621.js diff --git a/test/mjsunit/regress/regress-crbug-412319.js b/test/mjsunit/regress/regress-crbug-412319.js index 21386e3..c597b0d 100644 --- a/test/mjsunit/regress/regress-crbug-412319.js +++ b/test/mjsunit/regress/regress-crbug-412319.js @@ -15,5 +15,5 @@ __f_6(); %OptimizeFunctionOnNextCall(__f_6); __f_6(); function __f_7(__v_7) { - __v_7.push(Infinity); + __v_7.pop(); } diff --git a/test/mozilla/mozilla.status b/test/mozilla/mozilla.status index e9f58c6..00ba050 100644 --- a/test/mozilla/mozilla.status +++ b/test/mozilla/mozilla.status @@ -117,6 +117,11 @@ 'js1_5/GC/regress-348532': [SKIP], + # Runs for too long: huge array with getters and setters. As it says + # in the test: "This test will probably run out of memory". + 'js1_5/extensions/regress-345967': [SKIP], + + ##################### FLAKY TESTS ##################### # These tests time out in debug mode but pass in product mode @@ -674,7 +679,6 @@ 'js1_5/extensions/regress-311792-01': [FAIL_OK], 'js1_5/extensions/regress-312278': [FAIL_OK], 'js1_5/extensions/regress-313630': [FAIL_OK], - 'js1_5/extensions/regress-313763': [FAIL_OK], 'js1_5/extensions/regress-313803': [FAIL_OK], 'js1_5/extensions/regress-314874': [FAIL_OK], 'js1_5/extensions/regress-322957': [FAIL_OK], @@ -684,8 +688,6 @@ 'js1_5/extensions/regress-336409-1': [FAIL_OK], 'js1_5/extensions/regress-336409-2': [FAIL_OK], 'js1_5/extensions/regress-336410-2': [FAIL_OK], - 'js1_5/extensions/regress-341956-01': [FAIL_OK], - 'js1_5/extensions/regress-345967': [FAIL_OK], 'js1_5/extensions/regress-346494-01': [FAIL_OK], 'js1_5/extensions/regress-346494': [FAIL_OK], 'js1_5/extensions/regress-347306-02': [FAIL_OK], -- 2.7.4