Home | History | Annotate | Download | only in runtime 
      1 // Copyright 2014 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/runtime/runtime-utils.h"
      6 
      7 #include "src/arguments.h"
      8 #include "src/conversions-inl.h"
      9 #include "src/elements.h"
     10 #include "src/factory.h"
     11 #include "src/isolate-inl.h"
     12 #include "src/key-accumulator.h"
     13 #include "src/messages.h"
     14 #include "src/prototype.h"
     15 
     16 namespace v8 {
     17 namespace internal {
     18 
     19 RUNTIME_FUNCTION(Runtime_FinishArrayPrototypeSetup) {
     20   HandleScope scope(isolate);
     21   DCHECK(args.length() == 1);
     22   CONVERT_ARG_HANDLE_CHECKED(JSArray, prototype, 0);
     23   Object* length = prototype->length();
     24   RUNTIME_ASSERT(length->IsSmi() && Smi::cast(length)->value() == 0);
     25   RUNTIME_ASSERT(prototype->HasFastSmiOrObjectElements());
     26   // This is necessary to enable fast checks for absence of elements
     27   // on Array.prototype and below.
     28   prototype->set_elements(isolate->heap()->empty_fixed_array());
     29   return Smi::FromInt(0);
     30 }
     31 
     32 
     33 static void InstallBuiltin(Isolate* isolate, Handle<JSObject> holder,
     34                            const char* name, Builtins::Name builtin_name) {
     35   Handle<String> key = isolate->factory()->InternalizeUtf8String(name);
     36   Handle<Code> code(isolate->builtins()->builtin(builtin_name));
     37   Handle<JSFunction> optimized =
     38       isolate->factory()->NewFunctionWithoutPrototype(key, code);
     39   optimized->shared()->DontAdaptArguments();
     40   JSObject::AddProperty(holder, key, optimized, NONE);
     41 }
     42 
     43 
     44 RUNTIME_FUNCTION(Runtime_SpecialArrayFunctions) {
     45   HandleScope scope(isolate);
     46   DCHECK(args.length() == 0);
     47   Handle<JSObject> holder =
     48       isolate->factory()->NewJSObject(isolate->object_function());
     49 
     50   InstallBuiltin(isolate, holder, "pop", Builtins::kArrayPop);
     51   InstallBuiltin(isolate, holder, "push", Builtins::kArrayPush);
     52   InstallBuiltin(isolate, holder, "shift", Builtins::kArrayShift);
     53   InstallBuiltin(isolate, holder, "unshift", Builtins::kArrayUnshift);
     54   InstallBuiltin(isolate, holder, "slice", Builtins::kArraySlice);
     55   InstallBuiltin(isolate, holder, "splice", Builtins::kArraySplice);
     56 
     57   return *holder;
     58 }
     59 
     60 
     61 RUNTIME_FUNCTION(Runtime_FixedArrayGet) {
     62   SealHandleScope shs(isolate);
     63   DCHECK(args.length() == 2);
     64   CONVERT_ARG_CHECKED(FixedArray, object, 0);
     65   CONVERT_SMI_ARG_CHECKED(index, 1);
     66   return object->get(index);
     67 }
     68 
     69 
     70 RUNTIME_FUNCTION(Runtime_FixedArraySet) {
     71   SealHandleScope shs(isolate);
     72   DCHECK(args.length() == 3);
     73   CONVERT_ARG_CHECKED(FixedArray, object, 0);
     74   CONVERT_SMI_ARG_CHECKED(index, 1);
     75   CONVERT_ARG_CHECKED(Object, value, 2);
     76   object->set(index, value);
     77   return isolate->heap()->undefined_value();
     78 }
     79 
     80 
     81 RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
     82   HandleScope scope(isolate);
     83   RUNTIME_ASSERT(args.length() == 2);
     84   CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
     85   CONVERT_ARG_HANDLE_CHECKED(Map, map, 1);
     86   JSObject::TransitionElementsKind(array, map->elements_kind());
     87   return *array;
     88 }
     89 
     90 
     91 // Push an object unto an array of objects if it is not already in the
     92 // array.  Returns true if the element was pushed on the stack and
     93 // false otherwise.
     94 RUNTIME_FUNCTION(Runtime_PushIfAbsent) {
     95   HandleScope scope(isolate);
     96   DCHECK(args.length() == 2);
     97   CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
     98   CONVERT_ARG_HANDLE_CHECKED(JSReceiver, element, 1);
     99   RUNTIME_ASSERT(array->HasFastSmiOrObjectElements());
    100   int length = Smi::cast(array->length())->value();
    101   FixedArray* elements = FixedArray::cast(array->elements());
    102   for (int i = 0; i < length; i++) {
    103     if (elements->get(i) == *element) return isolate->heap()->false_value();
    104   }
    105 
    106   // Strict not needed. Used for cycle detection in Array join implementation.
    107   RETURN_FAILURE_ON_EXCEPTION(
    108       isolate, JSObject::AddDataElement(array, length, element, NONE));
    109   JSObject::ValidateElements(array);
    110   return isolate->heap()->true_value();
    111 }
    112 
    113 
    114 // Moves all own elements of an object, that are below a limit, to positions
    115 // starting at zero. All undefined values are placed after non-undefined values,
    116 // and are followed by non-existing element. Does not change the length
    117 // property.
    118 // Returns the number of non-undefined elements collected.
    119 // Returns -1 if hole removal is not supported by this method.
    120 RUNTIME_FUNCTION(Runtime_RemoveArrayHoles) {
    121   HandleScope scope(isolate);
    122   DCHECK(args.length() == 2);
    123   CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
    124   CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);
    125   return *JSObject::PrepareElementsForSort(object, limit);
    126 }
    127 
    128 
    129 // Move contents of argument 0 (an array) to argument 1 (an array)
    130 RUNTIME_FUNCTION(Runtime_MoveArrayContents) {
    131   HandleScope scope(isolate);
    132   DCHECK(args.length() == 2);
    133   CONVERT_ARG_HANDLE_CHECKED(JSArray, from, 0);
    134   CONVERT_ARG_HANDLE_CHECKED(JSArray, to, 1);
    135   JSObject::ValidateElements(from);
    136   JSObject::ValidateElements(to);
    137 
    138   Handle<FixedArrayBase> new_elements(from->elements());
    139   ElementsKind from_kind = from->GetElementsKind();
    140   Handle<Map> new_map = JSObject::GetElementsTransitionMap(to, from_kind);
    141   JSObject::SetMapAndElements(to, new_map, new_elements);
    142   to->set_length(from->length());
    143 
    144   JSObject::ResetElements(from);
    145   from->set_length(Smi::FromInt(0));
    146 
    147   JSObject::ValidateElements(to);
    148   return *to;
    149 }
    150 
    151 
    152 // How many elements does this object/array have?
    153 RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) {
    154   HandleScope scope(isolate);
    155   DCHECK(args.length() == 1);
    156   CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
    157   Handle<FixedArrayBase> elements(array->elements(), isolate);
    158   SealHandleScope shs(isolate);
    159   if (elements->IsDictionary()) {
    160     int result =
    161         Handle<SeededNumberDictionary>::cast(elements)->NumberOfElements();
    162     return Smi::FromInt(result);
    163   } else {
    164     DCHECK(array->length()->IsSmi());
    165     // For packed elements, we know the exact number of elements
    166     int length = elements->length();
    167     ElementsKind kind = array->GetElementsKind();
    168     if (IsFastPackedElementsKind(kind)) {
    169       return Smi::FromInt(length);
    170     }
    171     // For holey elements, take samples from the buffer checking for holes
    172     // to generate the estimate.
    173     const int kNumberOfHoleCheckSamples = 97;
    174     int increment = (length < kNumberOfHoleCheckSamples)
    175                         ? 1
    176                         : static_cast<int>(length / kNumberOfHoleCheckSamples);
    177     ElementsAccessor* accessor = array->GetElementsAccessor();
    178     int holes = 0;
    179     for (int i = 0; i < length; i += increment) {
    180       if (!accessor->HasElement(array, i, elements)) {
    181         ++holes;
    182       }
    183     }
    184     int estimate = static_cast<int>((kNumberOfHoleCheckSamples - holes) /
    185                                     kNumberOfHoleCheckSamples * length);
    186     return Smi::FromInt(estimate);
    187   }
    188 }
    189 
    190 
    191 // Returns an array that tells you where in the [0, length) interval an array
    192 // might have elements.  Can either return an array of keys (positive integers
    193 // or undefined) or a number representing the positive length of an interval
    194 // starting at index 0.
    195 // Intervals can span over some keys that are not in the object.
    196 RUNTIME_FUNCTION(Runtime_GetArrayKeys) {
    197   HandleScope scope(isolate);
    198   DCHECK(args.length() == 2);
    199   CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
    200   CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
    201 
    202   if (!array->elements()->IsDictionary()) {
    203     RUNTIME_ASSERT(array->HasFastSmiOrObjectElements() ||
    204                    array->HasFastDoubleElements());
    205     uint32_t actual_length = static_cast<uint32_t>(array->elements()->length());
    206     return *isolate->factory()->NewNumberFromUint(Min(actual_length, length));
    207   }
    208 
    209   KeyAccumulator accumulator(isolate, ALL_PROPERTIES);
    210   // No need to separate protoype levels since we only get numbers/element keys
    211   for (PrototypeIterator iter(isolate, array,
    212                               PrototypeIterator::START_AT_RECEIVER);
    213        !iter.IsAtEnd(); iter.Advance()) {
    214     if (PrototypeIterator::GetCurrent(iter)->IsJSProxy() ||
    215         PrototypeIterator::GetCurrent<JSObject>(iter)
    216             ->HasIndexedInterceptor()) {
    217       // Bail out if we find a proxy or interceptor, likely not worth
    218       // collecting keys in that case.
    219       return *isolate->factory()->NewNumberFromUint(length);
    220     }
    221     accumulator.NextPrototype();
    222     Handle<JSObject> current = PrototypeIterator::GetCurrent<JSObject>(iter);
    223     JSObject::CollectOwnElementKeys(current, &accumulator, ALL_PROPERTIES);
    224   }
    225   // Erase any keys >= length.
    226   // TODO(adamk): Remove this step when the contract of %GetArrayKeys
    227   // is changed to let this happen on the JS side.
    228   Handle<FixedArray> keys = accumulator.GetKeys(KEEP_NUMBERS);
    229   for (int i = 0; i < keys->length(); i++) {
    230     if (NumberToUint32(keys->get(i)) >= length) keys->set_undefined(i);
    231   }
    232   return *isolate->factory()->NewJSArrayWithElements(keys);
    233 }
    234 
    235 
    236 namespace {
    237 
    238 Object* ArrayConstructorCommon(Isolate* isolate, Handle<JSFunction> constructor,
    239                                Handle<JSReceiver> new_target,
    240                                Handle<AllocationSite> site,
    241                                Arguments* caller_args) {
    242   Factory* factory = isolate->factory();
    243 
    244   // If called through new, new.target can be:
    245   // - a subclass of constructor,
    246   // - a proxy wrapper around constructor, or
    247   // - the constructor itself.
    248   // If called through Reflect.construct, it's guaranteed to be a constructor by
    249   // REFLECT_CONSTRUCT_PREPARE.
    250   DCHECK(new_target->IsConstructor());
    251 
    252   bool holey = false;
    253   bool can_use_type_feedback = !site.is_null();
    254   bool can_inline_array_constructor = true;
    255   if (caller_args->length() == 1) {
    256     Handle<Object> argument_one = caller_args->at<Object>(0);
    257     if (argument_one->IsSmi()) {
    258       int value = Handle<Smi>::cast(argument_one)->value();
    259       if (value < 0 ||
    260           JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
    261         // the array is a dictionary in this case.
    262         can_use_type_feedback = false;
    263       } else if (value != 0) {
    264         holey = true;
    265         if (value >= JSArray::kInitialMaxFastElementArray) {
    266           can_inline_array_constructor = false;
    267         }
    268       }
    269     } else {
    270       // Non-smi length argument produces a dictionary
    271       can_use_type_feedback = false;
    272     }
    273   }
    274 
    275   Handle<Map> initial_map;
    276   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    277       isolate, initial_map,
    278       JSFunction::GetDerivedMap(isolate, constructor, new_target));
    279 
    280   ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
    281                                                : initial_map->elements_kind();
    282   if (holey && !IsFastHoleyElementsKind(to_kind)) {
    283     to_kind = GetHoleyElementsKind(to_kind);
    284     // Update the allocation site info to reflect the advice alteration.
    285     if (!site.is_null()) site->SetElementsKind(to_kind);
    286   }
    287 
    288   // We should allocate with an initial map that reflects the allocation site
    289   // advice. Therefore we use AllocateJSObjectFromMap instead of passing
    290   // the constructor.
    291   if (to_kind != initial_map->elements_kind()) {
    292     initial_map = Map::AsElementsKind(initial_map, to_kind);
    293   }
    294 
    295   // If we don't care to track arrays of to_kind ElementsKind, then
    296   // don't emit a memento for them.
    297   Handle<AllocationSite> allocation_site;
    298   if (AllocationSite::GetMode(to_kind) == TRACK_ALLOCATION_SITE) {
    299     allocation_site = site;
    300   }
    301 
    302   Handle<JSArray> array = Handle<JSArray>::cast(
    303       factory->NewJSObjectFromMap(initial_map, NOT_TENURED, allocation_site));
    304 
    305   factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);
    306 
    307   ElementsKind old_kind = array->GetElementsKind();
    308   RETURN_FAILURE_ON_EXCEPTION(
    309       isolate, ArrayConstructInitializeElements(array, caller_args));
    310   if (!site.is_null() &&
    311       (old_kind != array->GetElementsKind() || !can_use_type_feedback ||
    312        !can_inline_array_constructor)) {
    313     // The arguments passed in caused a transition. This kind of complexity
    314     // can't be dealt with in the inlined hydrogen array constructor case.
    315     // We must mark the allocationsite as un-inlinable.
    316     site->SetDoNotInlineCall();
    317   }
    318 
    319   return *array;
    320 }
    321 
    322 }  // namespace
    323 
    324 
    325 RUNTIME_FUNCTION(Runtime_NewArray) {
    326   HandleScope scope(isolate);
    327   DCHECK_LE(3, args.length());
    328   int const argc = args.length() - 3;
    329   // TODO(bmeurer): Remove this Arguments nonsense.
    330   Arguments argv(argc, args.arguments() - 1);
    331   CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, 0);
    332   CONVERT_ARG_HANDLE_CHECKED(JSReceiver, new_target, argc + 1);
    333   CONVERT_ARG_HANDLE_CHECKED(HeapObject, type_info, argc + 2);
    334   // TODO(bmeurer): Use MaybeHandle to pass around the AllocationSite.
    335   Handle<AllocationSite> site = type_info->IsAllocationSite()
    336                                     ? Handle<AllocationSite>::cast(type_info)
    337                                     : Handle<AllocationSite>::null();
    338   return ArrayConstructorCommon(isolate, constructor, new_target, site, &argv);
    339 }
    340 
    341 
    342 RUNTIME_FUNCTION(Runtime_ArrayConstructor) {
    343   HandleScope scope(isolate);
    344   // If we get 2 arguments then they are the stub parameters (constructor, type
    345   // info).  If we get 4, then the first one is a pointer to the arguments
    346   // passed by the caller, and the last one is the length of the arguments
    347   // passed to the caller (redundant, but useful to check on the deoptimizer
    348   // with an assert).
    349   Arguments empty_args(0, NULL);
    350   bool no_caller_args = args.length() == 2;
    351   DCHECK(no_caller_args || args.length() == 4);
    352   int parameters_start = no_caller_args ? 0 : 1;
    353   Arguments* caller_args =
    354       no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]);
    355   CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start);
    356   CONVERT_ARG_HANDLE_CHECKED(Object, type_info, parameters_start + 1);
    357 #ifdef DEBUG
    358   if (!no_caller_args) {
    359     CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 2);
    360     DCHECK(arg_count == caller_args->length());
    361   }
    362 #endif
    363 
    364   Handle<AllocationSite> site;
    365   if (!type_info.is_null() &&
    366       *type_info != isolate->heap()->undefined_value()) {
    367     site = Handle<AllocationSite>::cast(type_info);
    368     DCHECK(!site->SitePointsToLiteral());
    369   }
    370 
    371   return ArrayConstructorCommon(isolate, constructor, constructor, site,
    372                                 caller_args);
    373 }
    374 
    375 
    376 RUNTIME_FUNCTION(Runtime_InternalArrayConstructor) {
    377   HandleScope scope(isolate);
    378   Arguments empty_args(0, NULL);
    379   bool no_caller_args = args.length() == 1;
    380   DCHECK(no_caller_args || args.length() == 3);
    381   int parameters_start = no_caller_args ? 0 : 1;
    382   Arguments* caller_args =
    383       no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]);
    384   CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start);
    385 #ifdef DEBUG
    386   if (!no_caller_args) {
    387     CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 1);
    388     DCHECK(arg_count == caller_args->length());
    389   }
    390 #endif
    391   return ArrayConstructorCommon(isolate, constructor, constructor,
    392                                 Handle<AllocationSite>::null(), caller_args);
    393 }
    394 
    395 
    396 RUNTIME_FUNCTION(Runtime_NormalizeElements) {
    397   HandleScope scope(isolate);
    398   DCHECK(args.length() == 1);
    399   CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
    400   RUNTIME_ASSERT(!array->HasFixedTypedArrayElements() &&
    401                  !array->IsJSGlobalProxy());
    402   JSObject::NormalizeElements(array);
    403   return *array;
    404 }
    405 
    406 
    407 // GrowArrayElements returns a sentinel Smi if the object was normalized.
    408 RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
    409   HandleScope scope(isolate);
    410   DCHECK(args.length() == 2);
    411   CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
    412   CONVERT_NUMBER_CHECKED(int, key, Int32, args[1]);
    413 
    414   if (key < 0) {
    415     return object->elements();
    416   }
    417 
    418   uint32_t capacity = static_cast<uint32_t>(object->elements()->length());
    419   uint32_t index = static_cast<uint32_t>(key);
    420 
    421   if (index >= capacity) {
    422     if (object->WouldConvertToSlowElements(index)) {
    423       // We don't want to allow operations that cause lazy deopt. Return a Smi
    424       // as a signal that optimized code should eagerly deoptimize.
    425       return Smi::FromInt(0);
    426     }
    427 
    428     uint32_t new_capacity = JSObject::NewElementsCapacity(index + 1);
    429     object->GetElementsAccessor()->GrowCapacityAndConvert(object, new_capacity);
    430   }
    431 
    432   // On success, return the fixed array elements.
    433   return object->elements();
    434 }
    435 
    436 
    437 RUNTIME_FUNCTION(Runtime_HasComplexElements) {
    438   HandleScope scope(isolate);
    439   DCHECK(args.length() == 1);
    440   CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
    441   for (PrototypeIterator iter(isolate, array,
    442                               PrototypeIterator::START_AT_RECEIVER);
    443        !iter.IsAtEnd(); iter.Advance()) {
    444     if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) {
    445       return isolate->heap()->true_value();
    446     }
    447     Handle<JSObject> current = PrototypeIterator::GetCurrent<JSObject>(iter);
    448     if (current->HasIndexedInterceptor()) {
    449       return isolate->heap()->true_value();
    450     }
    451     if (!current->HasDictionaryElements()) continue;
    452     if (current->element_dictionary()->HasComplexElements()) {
    453       return isolate->heap()->true_value();
    454     }
    455   }
    456   return isolate->heap()->false_value();
    457 }
    458 
    459 
    460 RUNTIME_FUNCTION(Runtime_IsArray) {
    461   SealHandleScope shs(isolate);
    462   DCHECK(args.length() == 1);
    463   CONVERT_ARG_CHECKED(Object, obj, 0);
    464   return isolate->heap()->ToBoolean(obj->IsJSArray());
    465 }
    466 
    467 
    468 RUNTIME_FUNCTION(Runtime_HasCachedArrayIndex) {
    469   SealHandleScope shs(isolate);
    470   DCHECK(args.length() == 1);
    471   return isolate->heap()->false_value();
    472 }
    473 
    474 
    475 RUNTIME_FUNCTION(Runtime_GetCachedArrayIndex) {
    476   // This can never be reached, because Runtime_HasCachedArrayIndex always
    477   // returns false.
    478   UNIMPLEMENTED();
    479   return nullptr;
    480 }
    481 
    482 
    483 RUNTIME_FUNCTION(Runtime_FastOneByteArrayJoin) {
    484   SealHandleScope shs(isolate);
    485   DCHECK(args.length() == 2);
    486   // Returning undefined means that this fast path fails and one has to resort
    487   // to a slow path.
    488   return isolate->heap()->undefined_value();
    489 }
    490 
    491 
    492 RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
    493   HandleScope scope(isolate);
    494   DCHECK(args.length() == 1);
    495   CONVERT_ARG_HANDLE_CHECKED(Object, original_array, 0);
    496   Handle<Object> constructor;
    497   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    498       isolate, constructor,
    499       Object::ArraySpeciesConstructor(isolate, original_array));
    500   return *constructor;
    501 }
    502 
    503 }  // namespace internal
    504 }  // namespace v8
    505