From be21c71584fd16f88a1e65515737535a39e19548 Mon Sep 17 00:00:00 2001 From: "antonm@chromium.org" Date: Wed, 17 Feb 2010 10:54:49 +0000 Subject: [PATCH] Introduce Array.splice builtin. Review URL: http://codereview.chromium.org/618002 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@3885 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/array.js | 5 +- src/bootstrapper.cc | 2 + src/builtins.cc | 167 +++++++++++++++++++++++--- src/builtins.h | 1 + test/mjsunit/array-splice.js | 270 +++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 426 insertions(+), 19 deletions(-) create mode 100644 test/mjsunit/array-splice.js diff --git a/src/array.js b/src/array.js index c3ab179..c28a662 100644 --- a/src/array.js +++ b/src/array.js @@ -566,10 +566,11 @@ function ArraySlice(start, end) { function ArraySplice(start, delete_count) { var num_arguments = %_ArgumentsLength(); - // SpiderMonkey and KJS return undefined in the case where no + // SpiderMonkey and JSC return undefined in the case where no // arguments are given instead of using the implicit undefined // arguments. This does not follow ECMA-262, but we do the same for // compatibility. + // TraceMonkey follows ECMA-262 though. if (num_arguments == 0) return; var len = TO_UINT32(this.length); @@ -582,7 +583,7 @@ function ArraySplice(start, delete_count) { if (start_i > len) start_i = len; } - // SpiderMonkey and KJS treat the case where no delete count is + // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is // given differently from when an undefined delete count is given. // This does not follow ECMA-262, but we do the same for // compatibility. diff --git a/src/bootstrapper.cc b/src/bootstrapper.cc index 727d4a6..2cd4cce 100644 --- a/src/bootstrapper.cc +++ b/src/bootstrapper.cc @@ -1498,6 +1498,8 @@ void Genesis::BuildSpecialFunctionTable() { Handle(Builtins::builtin(Builtins::ArrayUnshift))); AddSpecialFunction(special_prototype, "slice", Handle(Builtins::builtin(Builtins::ArraySlice))); + AddSpecialFunction(special_prototype, "splice", + Handle(Builtins::builtin(Builtins::ArraySplice))); } diff --git a/src/builtins.cc b/src/builtins.cc index e8e7109..7ded532 100644 --- a/src/builtins.cc +++ b/src/builtins.cc @@ -419,22 +419,25 @@ BUILTIN(ArrayUnshift) { } -static Object* SlowArraySlice(Handle receiver, - Object** arg0, - Object** arg1 = NULL) { +static Object* CallJsBuiltin(const char* name, + BuiltinArguments args) { HandleScope handleScope; - Handle slow_slice = + Handle js_builtin = GetProperty(Handle(Top::global_context()->builtins()), - "ArraySlice"); - ASSERT(slow_slice->IsJSFunction()); - Handle function(Handle::cast(slow_slice)); - Object** args[] = { arg0, arg1 }; + name); + ASSERT(js_builtin->IsJSFunction()); + Handle function(Handle::cast(js_builtin)); + Vector argv(Vector::New(args.length() - 1)); + int n_args = args.length() - 1; + for (int i = 0; i < n_args; i++) { + argv[i] = &args[i + 1]; + } bool pending_exception = false; Handle result = Execution::Call(function, - receiver, - arg1 == NULL ? 1 : 2, - args, + args.receiver(), + n_args, + argv.start(), &pending_exception); if (pending_exception) return Failure::Exception(); return *result; @@ -459,18 +462,14 @@ BUILTIN(ArraySlice) { if (arg1->IsSmi()) { relativeStart = Smi::cast(arg1)->value(); } else if (!arg1->IsUndefined()) { - if (n_arguments > 1) { - return SlowArraySlice(args.receiver(), &args[1], &args[2]); - } else { - return SlowArraySlice(args.receiver(), &args[1]); - } + return CallJsBuiltin("ArraySlice", args); } if (n_arguments > 1) { Object* arg2 = args[2]; if (arg2->IsSmi()) { relativeEnd = Smi::cast(arg2)->value(); } else if (!arg2->IsUndefined()) { - return SlowArraySlice(args.receiver(), &args[1], &args[2]); + return CallJsBuiltin("ArraySlice", args); } } } @@ -523,6 +522,140 @@ BUILTIN(ArraySlice) { } +BUILTIN(ArraySplice) { + JSArray* array = JSArray::cast(*args.receiver()); + ASSERT(array->HasFastElements()); + + int len = Smi::cast(array->length())->value(); + + int n_arguments = args.length() - 1; + + // SpiderMonkey and JSC return undefined in the case where no + // arguments are given instead of using the implicit undefined + // arguments. This does not follow ECMA-262, but we do the same for + // compatibility. + // TraceMonkey follows ECMA-262 though. + if (n_arguments == 0) { + return Heap::undefined_value(); + } + + int relativeStart = 0; + Object* arg1 = args[1]; + if (arg1->IsSmi()) { + relativeStart = Smi::cast(arg1)->value(); + } else if (!arg1->IsUndefined()) { + return CallJsBuiltin("ArraySplice", args); + } + int actualStart = (relativeStart < 0) ? Max(len + relativeStart, 0) + : Min(relativeStart, len); + + // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is + // given differently from when an undefined delete count is given. + // This does not follow ECMA-262, but we do the same for + // compatibility. + int deleteCount = len; + if (n_arguments > 1) { + Object* arg2 = args[2]; + if (arg2->IsSmi()) { + deleteCount = Smi::cast(arg2)->value(); + } else { + return CallJsBuiltin("ArraySplice", args); + } + } + int actualDeleteCount = Min(Max(deleteCount, 0), len - actualStart); + + JSFunction* array_function = + Top::context()->global_context()->array_function(); + + // Allocate result array. + Object* result = Heap::AllocateJSObject(array_function); + if (result->IsFailure()) return result; + JSArray* result_array = JSArray::cast(result); + + result = Heap::AllocateFixedArrayWithHoles(actualDeleteCount); + if (result->IsFailure()) return result; + FixedArray* result_elms = FixedArray::cast(result); + + FixedArray* elms = FixedArray::cast(array->elements()); + + // Fetch the prototype. + JSObject* prototype = JSObject::cast(array_function->prototype()); + + AssertNoAllocation no_gc; + WriteBarrierMode mode = result_elms->GetWriteBarrierMode(no_gc); + + // Fill newly created array. + for (int k = 0; k < actualDeleteCount; k++) { + result_elms->set(k, + GetElementToMove(actualStart + k, elms, prototype), + mode); + } + + // Set elements. + result_array->set_elements(result_elms); + + // Set the length. + result_array->set_length(Smi::FromInt(actualDeleteCount)); + + int itemCount = (n_arguments > 1) ? (n_arguments - 2) : 0; + + int new_length = len - actualDeleteCount + itemCount; + + mode = elms->GetWriteBarrierMode(no_gc); + if (itemCount < actualDeleteCount) { + // Shrink the array. + for (int k = actualStart; k < (len - actualDeleteCount); k++) { + elms->set(k + itemCount, + GetElementToMove(k + actualDeleteCount, elms, prototype), + mode); + } + + for (int k = len; k > new_length; k--) { + elms->set(k - 1, Heap::the_hole_value()); + } + } else if (itemCount > actualDeleteCount) { + FixedArray* source_elms = elms; + + // Check if array need to grow. + if (new_length > elms->length()) { + // New backing storage is needed. + int capacity = new_length + (new_length >> 1) + 16; + Object* obj = Heap::AllocateFixedArrayWithHoles(capacity); + if (obj->IsFailure()) return obj; + + FixedArray* new_elms = FixedArray::cast(obj); + mode = new_elms->GetWriteBarrierMode(no_gc); + + // Copy the part before actualStart as is. + for (int k = 0; k < actualStart; k++) { + new_elms->set(k, elms->get(k), mode); + } + + source_elms = elms; + elms = new_elms; + array->set_elements(elms); + } + + for (int k = len - actualDeleteCount; k > actualStart; k--) { + elms->set(k + itemCount - 1, + GetElementToMove(k + actualDeleteCount - 1, + source_elms, + prototype), + mode); + } + } + + for (int k = actualStart; k < actualStart + itemCount; k++) { + elms->set(k, args[3 + k - actualStart], mode); + } + + // Set the length. + array->set_length(Smi::FromInt(new_length)); + + return result_array; +} + + // ----------------------------------------------------------------------------- // diff --git a/src/builtins.h b/src/builtins.h index f1eb4ee..13322c2 100644 --- a/src/builtins.h +++ b/src/builtins.h @@ -51,6 +51,7 @@ enum BuiltinExtraArguments { V(ArrayShift, NO_EXTRA_ARGUMENTS) \ V(ArrayUnshift, NO_EXTRA_ARGUMENTS) \ V(ArraySlice, NO_EXTRA_ARGUMENTS) \ + V(ArraySplice, NO_EXTRA_ARGUMENTS) \ \ V(HandleApiCall, NEEDS_CALLED_FUNCTION) \ V(FastHandleApiCall, NO_EXTRA_ARGUMENTS) \ diff --git a/test/mjsunit/array-splice.js b/test/mjsunit/array-splice.js new file mode 100644 index 0000000..2eaf6f0 --- /dev/null +++ b/test/mjsunit/array-splice.js @@ -0,0 +1,270 @@ +// Copyright 2010 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. + +// Check that splicing array of holes keeps it as array of holes +(function() { + for (var i = 0; i < 7; i++) { + var array = new Array(10); + var spliced = array.splice(1, 1, 'one', 'two'); + assertEquals(1, spliced.length); + assertFalse(0 in spliced); + + assertEquals(11, array.length); + assertFalse(0 in array); + assertTrue(1 in array); + assertTrue(2 in array); + assertFalse(3 in array); + } +})(); + + +// Check various forms of arguments omission. +(function() { + var array; + for (var i = 0; i < 7; i++) { + // SpiderMonkey and JSC return undefined in the case where no + // arguments are given instead of using the implicit undefined + // arguments. This does not follow ECMA-262, but we do the same for + // compatibility. + // TraceMonkey follows ECMA-262 though. + array = [1, 2, 3] + assertEquals(undefined, array.splice()); + assertEquals([1, 2, 3], array); + + // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is + // given differently from when an undefined delete count is given. + // This does not follow ECMA-262, but we do the same for + // compatibility. + array = [1, 2, 3] + assertEquals([1, 2, 3], array.splice(0)); + assertEquals([], array); + + array = [1, 2, 3] + assertEquals([1, 2, 3], array.splice(undefined)); + assertEquals([], array); + + array = [1, 2, 3] + assertEquals([1, 2, 3], array.splice("foobar")); + assertEquals([], array); + + array = [1, 2, 3] + assertEquals([], array.splice(undefined, undefined)); + assertEquals([1, 2, 3], array); + + array = [1, 2, 3] + assertEquals([], array.splice("foobar", undefined)); + assertEquals([1, 2, 3], array); + + array = [1, 2, 3] + assertEquals([], array.splice(undefined, "foobar")); + assertEquals([1, 2, 3], array); + + array = [1, 2, 3] + assertEquals([], array.splice("foobar", "foobar")); + assertEquals([1, 2, 3], array); + } +})(); + + +// Check variants of negatives and positive indices. +(function() { + var array, spliced; + for (var i = 0; i < 7; i++) { + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(-100); + assertEquals([], array); + assertEquals([1, 2, 3, 4, 5, 6, 7], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(-3); + assertEquals([1, 2, 3, 4], array); + assertEquals([5, 6, 7], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(4); + assertEquals([1, 2, 3, 4], array); + assertEquals([5, 6, 7], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(6); + assertEquals([1, 2, 3, 4, 5, 6], array); + assertEquals([7], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(7); + assertEquals([1, 2, 3, 4, 5, 6, 7], array); + assertEquals([], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(8); + assertEquals([1, 2, 3, 4, 5, 6, 7], array); + assertEquals([], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(100); + assertEquals([1, 2, 3, 4, 5, 6, 7], array); + assertEquals([], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(0, -100); + assertEquals([1, 2, 3, 4, 5, 6, 7], array); + assertEquals([], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(0, -3); + assertEquals([1, 2, 3, 4, 5, 6, 7], array); + assertEquals([], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(0, 4); + assertEquals([5, 6, 7], array); + assertEquals([1, 2, 3, 4], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(0, 6); + assertEquals([7], array); + assertEquals([1, 2, 3, 4, 5, 6], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(0, 7); + assertEquals([], array); + assertEquals([1, 2, 3, 4, 5, 6, 7], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(0, 8); + assertEquals([], array); + assertEquals([1, 2, 3, 4, 5, 6, 7], spliced); + + array = [1, 2, 3, 4, 5, 6, 7]; + spliced = array.splice(0, 100); + assertEquals([], array); + assertEquals([1, 2, 3, 4, 5, 6, 7], spliced); + + // Some exotic cases. + obj = { toString: function() { throw 'Exception'; } }; + + // Throwing an exception in conversion: + try { + [1, 2, 3].splice(obj, 3); + throw 'Should have thrown'; + } catch (e) { + assertEquals('Exception', e); + } + + try { + [1, 2, 3].splice(0, obj, 3); + throw 'Should have thrown'; + } catch (e) { + assertEquals('Exception', e); + } + + array = [1, 2, 3]; + array.splice(0, 3, obj); + assertEquals(1, array.length); + + // Custom conversion: + array = [1, 2, 3]; + spliced = array.splice({valueOf: function() { return 1; }}, + {toString: function() { return 2; }}, + 'one', 'two'); + assertEquals([2, 3], spliced); + assertEquals([1, 'one', 'two'], array); + } +})(); + + +// Nasty: modify the array in ToInteger. +(function() { + var array = []; + var spliced; + + for (var i = 0; i < 13; i++) { + bad_start = { valueOf: function() { array.push(2*i); return -1; } }; + bad_count = { valueOf: function() { array.push(2*i + 1); return 1; } }; + spliced = array.splice(bad_start, bad_count); + // According to the spec (15.4.4.12), length is calculated before + // performing ToInteger on arguments. However, v8 ignores elements + // we add while converting, so we need corrective pushes. + array.push(2*i); array.push(2*i + 1); + if (i == 0) { + assertEquals([], spliced); // Length was 0, nothing to get. + assertEquals([0, 1], array); + } else { + // When we start splice, array is [0 .. 2*i - 1], so we get + // as a result [2*i], this element is removed from the array, + // but [2 * i, 2 * i + 1] are added. + assertEquals([2 * i - 1], spliced); + assertEquals(2 * i, array[i]); + assertEquals(2 * i + 1, array[i + 1]); + } + } +})(); + + +// Now check the case with array of holes and some elements on prototype. +(function() { + var len = 9; + + var at3 = "@3"; + var at7 = "@7"; + + for (var i = 0; i < 7; i++) { + var array = new Array(len); + Array.prototype[3] = at3; + Array.prototype[7] = at7; + + var spliced = array.splice(2, 2, 'one', undefined, 'two'); + + // Second hole (at index 3) of array turns into + // value of Array.prototype[3] while copying. + assertEquals([, at3], spliced); + assertEquals([, , 'one', undefined, 'two', , , at7, at7, ,], array); + + // ... but array[7] is actually a hole: + assertTrue(delete Array.prototype[7]); + assertEquals(undefined, array[7]); + + // and now check hasOwnProperty + assertFalse(array.hasOwnProperty(0)); + assertFalse(array.hasOwnProperty(1)); + assertTrue(array.hasOwnProperty(2)); + assertTrue(array.hasOwnProperty(3)); + assertTrue(array.hasOwnProperty(4)); + assertFalse(array.hasOwnProperty(5)); + assertFalse(array.hasOwnProperty(6)); + assertFalse(array.hasOwnProperty(7)); + assertTrue(array.hasOwnProperty(8)); + assertFalse(array.hasOwnProperty(9)); + + // and now check couple of indices above length. + assertFalse(array.hasOwnProperty(10)); + assertFalse(array.hasOwnProperty(15)); + assertFalse(array.hasOwnProperty(31)); + assertFalse(array.hasOwnProperty(63)); + assertFalse(array.hasOwnProperty(2 << 32 - 1)); + } +})(); -- 2.7.4