From ea1b4f0eb1cfd0e259a7fb7338c3690601b50677 Mon Sep 17 00:00:00 2001 From: "antonm@chromium.org" Date: Tue, 16 Feb 2010 12:14:23 +0000 Subject: [PATCH] Introduce builtin for Array.slice function. Review URL: http://codereview.chromium.org/604059 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@3871 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/bootstrapper.cc | 2 + src/builtins.cc | 104 ++++++++++++++++++++++++++++ src/builtins.h | 1 + src/execution.cc | 2 +- src/ic.cc | 2 +- test/mjsunit/array-slice.js | 162 ++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 271 insertions(+), 2 deletions(-) create mode 100644 test/mjsunit/array-slice.js diff --git a/src/bootstrapper.cc b/src/bootstrapper.cc index a5fbfa3..6dd9fc5 100644 --- a/src/bootstrapper.cc +++ b/src/bootstrapper.cc @@ -1495,6 +1495,8 @@ void Genesis::BuildSpecialFunctionTable() { Handle(Builtins::builtin(Builtins::ArrayShift))); AddSpecialFunction(special_prototype, "unshift", Handle(Builtins::builtin(Builtins::ArrayUnshift))); + AddSpecialFunction(special_prototype, "slice", + Handle(Builtins::builtin(Builtins::ArraySlice))); } diff --git a/src/builtins.cc b/src/builtins.cc index c68de9a..e8e7109 100644 --- a/src/builtins.cc +++ b/src/builtins.cc @@ -419,6 +419,110 @@ BUILTIN(ArrayUnshift) { } +static Object* SlowArraySlice(Handle receiver, + Object** arg0, + Object** arg1 = NULL) { + HandleScope handleScope; + + Handle slow_slice = + GetProperty(Handle(Top::global_context()->builtins()), + "ArraySlice"); + ASSERT(slow_slice->IsJSFunction()); + Handle function(Handle::cast(slow_slice)); + Object** args[] = { arg0, arg1 }; + bool pending_exception = false; + Handle result = Execution::Call(function, + receiver, + arg1 == NULL ? 1 : 2, + args, + &pending_exception); + if (pending_exception) return Failure::Exception(); + return *result; +} + + +BUILTIN(ArraySlice) { + JSArray* array = JSArray::cast(*args.receiver()); + ASSERT(array->HasFastElements()); + + int len = Smi::cast(array->length())->value(); + + int n_arguments = args.length() - 1; + + // Note carefully choosen defaults---if argument is missing, + // it's undefined which gets converted to 0 for relativeStart + // and to len for relativeEnd. + int relativeStart = 0; + int relativeEnd = len; + if (n_arguments > 0) { + Object* arg1 = args[1]; + 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]); + } + } + 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]); + } + } + } + + // ECMAScript 232, 3rd Edition, Section 15.4.4.10, step 6. + int k = (relativeStart < 0) ? Max(len + relativeStart, 0) + : Min(relativeStart, len); + + // ECMAScript 232, 3rd Edition, Section 15.4.4.10, step 8. + int final = (relativeEnd < 0) ? Max(len + relativeEnd, 0) + : Min(relativeEnd, len); + + // Calculate the length of result array. + int result_len = final - k; + if (result_len < 0) { + result_len = 0; + } + + JSFunction* array_function = + Top::context()->global_context()->array_function(); + Object* result = Heap::AllocateJSObject(array_function); + if (result->IsFailure()) return result; + JSArray* result_array = JSArray::cast(result); + + result = Heap::AllocateFixedArrayWithHoles(result_len); + 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 i = 0; i < result_len; i++) { + result_elms->set(i, + GetElementToMove(k + i, elms, prototype), + mode); + } + + // Set elements. + result_array->set_elements(result_elms); + + // Set the length. + result_array->set_length(Smi::FromInt(result_len)); + return result_array; +} + + // ----------------------------------------------------------------------------- // diff --git a/src/builtins.h b/src/builtins.h index b90a4d2..f1eb4ee 100644 --- a/src/builtins.h +++ b/src/builtins.h @@ -50,6 +50,7 @@ enum BuiltinExtraArguments { V(ArrayPop, NO_EXTRA_ARGUMENTS) \ V(ArrayShift, NO_EXTRA_ARGUMENTS) \ V(ArrayUnshift, NO_EXTRA_ARGUMENTS) \ + V(ArraySlice, NO_EXTRA_ARGUMENTS) \ \ V(HandleApiCall, NEEDS_CALLED_FUNCTION) \ V(FastHandleApiCall, NO_EXTRA_ARGUMENTS) \ diff --git a/src/execution.cc b/src/execution.cc index a79af23..2068413 100644 --- a/src/execution.cc +++ b/src/execution.cc @@ -91,7 +91,7 @@ static Handle Invoke(bool construct, JSEntryFunction entry = FUNCTION_CAST(code->entry()); // Call the function through the right JS entry stub. - byte* entry_address= func->code()->entry(); + byte* entry_address = func->code()->entry(); JSFunction* function = *func; Object* receiver_pointer = *receiver; value = CALL_GENERATED_CODE(entry, entry_address, function, diff --git a/src/ic.cc b/src/ic.cc index 1ab57da..e30e325 100644 --- a/src/ic.cc +++ b/src/ic.cc @@ -455,7 +455,7 @@ Object* CallIC::LoadFunction(State state, if (result->IsJSFunction()) { // Check if there is an optimized (builtin) version of the function. - // Ignored this will degrade performance for Array.prototype.{push,pop}. + // Ignored this will degrade performance for some Array functions. // Please note we only return the optimized function iff // the JSObject has FastElements. if (object->IsJSObject() && JSObject::cast(*object)->HasFastElements()) { diff --git a/test/mjsunit/array-slice.js b/test/mjsunit/array-slice.js new file mode 100644 index 0000000..c993a07 --- /dev/null +++ b/test/mjsunit/array-slice.js @@ -0,0 +1,162 @@ +// 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 slicing array of holes keeps it as array of holes +(function() { + var array = new Array(10); + for (var i = 0; i < 7; i++) { + var sliced = array.slice(); + assertEquals(array.length, sliced.length); + assertFalse(0 in sliced); + } +})(); + + +// Check various forms of arguments omission. +(function() { + var array = new Array(7); + + for (var i = 0; i < 7; i++) { + assertEquals(array, array.slice()); + assertEquals(array, array.slice(0)); + assertEquals(array, array.slice(undefined)); + assertEquals(array, array.slice("foobar")); + assertEquals(array, array.slice(undefined, undefined)); + } +})(); + + +// Check variants of negatives and positive indices. +(function() { + var array = new Array(7); + + for (var i = 0; i < 7; i++) { + assertEquals(7, array.slice(-100).length); + assertEquals(3, array.slice(-3).length); + assertEquals(3, array.slice(4).length); + assertEquals(1, array.slice(6).length); + assertEquals(0, array.slice(7).length); + assertEquals(0, array.slice(8).length); + assertEquals(0, array.slice(100).length); + + assertEquals(0, array.slice(0, -100).length); + assertEquals(4, array.slice(0, -3).length); + assertEquals(4, array.slice(0, 4).length); + assertEquals(6, array.slice(0, 6).length); + assertEquals(7, array.slice(0, 7).length); + assertEquals(7, array.slice(0, 8).length); + assertEquals(7, array.slice(0, 100).length); + + // Some exotic cases. + + obj = { toString: function() { throw 'Exception'; } }; + + // More than 2 arguments: + assertEquals(7, array.slice(0, 7, obj, null, undefined).length); + + // Custom conversion: + assertEquals(1, array.slice({valueOf: function() { return 1; }}, + {toString: function() { return 2; }}).length); + + // Throwing an exception in conversion: + try { + assertEquals(7, array.slice(0, obj).length); + throw 'Should have thrown'; + } catch (e) { + assertEquals('Exception', e); + } + } +})(); + + +// Nasty: modify the array in ToInteger. +(function() { + var array = []; + var expected = [] + bad_guy = { valueOf: function() { array.push(array.length); return -1; } }; + + for (var i = 0; i < 13; i++) { + var sliced = array.slice(bad_guy); + expected.push(i); + assertEquals(expected, array); + // According to the spec (15.4.4.10), length is calculated before + // performing ToInteger on arguments. + if (i == 0) { + assertEquals([], sliced); // Length was 0, nothing to get. + } else { + // Actually out of array [0..i] we get [i - 1] as length is i. + assertEquals([i - 1], sliced); + } + } +})(); + + +// Now check the case with array of holes and some elements on prototype. +(function() { + var len = 9; + var array = new Array(len); + + var at3 = "@3"; + var at7 = "@7"; + + for (var i = 0; i < 7; i++) { + Array.prototype[3] = at3; + Array.prototype[7] = at7; + + assertEquals(len, array.length); + for (var i = 0; i < array.length; i++) { + assertEquals(array[i], Array.prototype[i]); + } + + var sliced = array.slice(); + + assertEquals(len, sliced.length); + + assertTrue(delete Array.prototype[3]); + assertTrue(delete Array.prototype[7]); + + // Note that slice copies values from prototype into the array. + assertEquals(array[3], undefined); + assertFalse(array.hasOwnProperty(3)); + assertEquals(sliced[3], at3); + assertTrue(sliced.hasOwnProperty(3)); + + assertEquals(array[7], undefined); + assertFalse(array.hasOwnProperty(7)); + assertEquals(sliced[7], at7); + assertTrue(sliced.hasOwnProperty(7)); + + // ... but keeps the rest as holes: + Array.prototype[5] = "@5"; + assertEquals(array[5], Array.prototype[5]); + assertFalse(array.hasOwnProperty(5)); + assertEquals(sliced[5], Array.prototype[5]); + assertFalse(sliced.hasOwnProperty(5)); + + assertTrue(delete Array.prototype[5]); + } +})(); -- 2.7.4