js/src/builtin/Array.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* JS Array interface. */
   8
   9 #ifndef builtin_Array_h
  10 #define builtin_Array_h
  11
  12 #include "mozilla/Attributes.h"
  13
  14 #include "vm/JSObject.h"
  15
  16 namespace js {
  17
  18 namespace jit {
  19 class TrampolineNativeFrameLayout;
  20 }
  21
  22 class ArrayObject;
  23
  24 MOZ_ALWAYS_INLINE bool IdIsIndex(jsid id, uint32_t* indexp) {
  25   if (id.isInt()) {
  26     int32_t i = id.toInt();
  27     MOZ_ASSERT(i >= 0);
  28     *indexp = uint32_t(i);
  29     return true;
  30   }
  31
  32   if (MOZ_UNLIKELY(!id.isAtom())) {
  33     return false;
  34   }
  35
  36   JSAtom* atom = id.toAtom();
  37   return atom->isIndex(indexp);
  38 }
  39
  40 // The methods below only create dense boxed arrays.
  41
  42 // Create a dense array with no capacity allocated, length set to 0, in the
  43 // normal (i.e. non-tenured) heap.
  44 extern ArrayObject* NewDenseEmptyArray(JSContext* cx);
  45
  46 // Create a dense array with no capacity allocated, length set to 0, in the
  47 // tenured heap.
  48 extern ArrayObject* NewTenuredDenseEmptyArray(JSContext* cx);
  49
  50 // Create a dense array with a set length, but without allocating space for the
  51 // contents. This is useful, e.g., when accepting length from the user.
  52 extern ArrayObject* NewDenseUnallocatedArray(
  53     JSContext* cx, uint32_t length, NewObjectKind newKind = GenericObject);
  54
  55 // Create a dense array with length and capacity == 'length', initialized length
  56 // set to 0.
  57 extern ArrayObject* NewDenseFullyAllocatedArray(
  58     JSContext* cx, uint32_t length, NewObjectKind newKind = GenericObject,
  59     gc::AllocSite* site = nullptr);
  60
  61 // Create a dense array with length == 'length', initialized length set to 0,
  62 // and capacity == 'length' clamped to EagerAllocationMaxLength.
  63 extern ArrayObject* NewDensePartlyAllocatedArray(
  64     JSContext* cx, uint32_t length, NewObjectKind newKind = GenericObject);
  65
  66 // Like NewDensePartlyAllocatedArray, but the array will have |proto| as
  67 // prototype (or Array.prototype if |proto| is nullptr).
  68 extern ArrayObject* NewDensePartlyAllocatedArrayWithProto(JSContext* cx,
  69                                                           uint32_t length,
  70                                                           HandleObject proto);
  71
  72 // Create a dense array from the given array values, which must be rooted.
  73 extern ArrayObject* NewDenseCopiedArray(JSContext* cx, uint32_t length,
  74                                         const Value* values,
  75                                         NewObjectKind newKind = GenericObject);
  76
  77 // Create a dense array from the given (linear)string values, which must be
  78 // rooted
  79 extern ArrayObject* NewDenseCopiedArray(JSContext* cx, uint32_t length,
  80                                         JSLinearString** values,
  81                                         NewObjectKind newKind = GenericObject);
  82
  83 // Like NewDenseCopiedArray, but the array will have |proto| as prototype (or
  84 // Array.prototype if |proto| is nullptr).
  85 extern ArrayObject* NewDenseCopiedArrayWithProto(JSContext* cx, uint32_t length,
  86                                                  const Value* values,
  87                                                  HandleObject proto);
  88
  89 // Create a dense array with the given shape and length.
  90 extern ArrayObject* NewDenseFullyAllocatedArrayWithShape(
  91     JSContext* cx, uint32_t length, Handle<SharedShape*> shape);
  92
  93 extern ArrayObject* NewArrayWithShape(JSContext* cx, uint32_t length,
  94                                       Handle<Shape*> shape);
  95
  96 extern bool ToLength(JSContext* cx, HandleValue v, uint64_t* out);
  97
  98 extern bool GetLengthProperty(JSContext* cx, HandleObject obj,
  99                               uint64_t* lengthp);
 100
 101 extern bool SetLengthProperty(JSContext* cx, HandleObject obj, uint32_t length);
 102
 103 /*
 104  * Copy 'length' elements from aobj to vp.
 105  *
 106  * This function assumes 'length' is effectively the result of calling
 107  * GetLengthProperty on aobj. vp must point to rooted memory.
 108  */
 109 extern bool GetElements(JSContext* cx, HandleObject aobj, uint32_t length,
 110                         js::Value* vp);
 111
 112 /* Natives exposed for optimization by the interpreter and JITs. */
 113
 114 extern bool array_includes(JSContext* cx, unsigned argc, js::Value* vp);
 115 extern bool array_indexOf(JSContext* cx, unsigned argc, js::Value* vp);
 116 extern bool array_lastIndexOf(JSContext* cx, unsigned argc, js::Value* vp);
 117 extern bool array_pop(JSContext* cx, unsigned argc, js::Value* vp);
 118 extern bool array_join(JSContext* cx, unsigned argc, js::Value* vp);
 119 extern bool array_sort(JSContext* cx, unsigned argc, js::Value* vp);
 120
 121 extern void ArrayShiftMoveElements(ArrayObject* arr);
 122
 123 extern JSObject* ArraySliceDense(JSContext* cx, HandleObject obj, int32_t begin,
 124                                  int32_t end, HandleObject result);
 125
 126 extern JSObject* ArgumentsSliceDense(JSContext* cx, HandleObject obj,
 127                                      int32_t begin, int32_t end,
 128                                      HandleObject result);
 129
 130 extern ArrayObject* NewArrayWithNullProto(JSContext* cx);
 131
 132 /*
 133  * Append the given (non-hole) value to the end of an array.  The array must be
 134  * a newborn array -- that is, one which has not been exposed to script for
 135  * arbitrary manipulation.  (This method optimizes on the assumption that
 136  * extending the array to accommodate the element will never make the array
 137  * sparse, which requires that the array be completely filled.)
 138  */
 139 extern bool NewbornArrayPush(JSContext* cx, HandleObject obj, const Value& v);
 140
 141 extern ArrayObject* ArrayConstructorOneArg(JSContext* cx,
 142                                            Handle<ArrayObject*> templateObject,
 143                                            int32_t lengthInt);
 144
 145 #ifdef DEBUG
 146 extern bool ArrayInfo(JSContext* cx, unsigned argc, Value* vp);
 147 #endif
 148
 149 /* Array constructor native. Exposed only so the JIT can know its address. */
 150 extern bool ArrayConstructor(JSContext* cx, unsigned argc, Value* vp);
 151
 152 // Like Array constructor, but doesn't perform GetPrototypeFromConstructor.
 153 extern bool array_construct(JSContext* cx, unsigned argc, Value* vp);
 154
 155 extern JSString* ArrayToSource(JSContext* cx, HandleObject obj);
 156
 157 extern bool IsCrossRealmArrayConstructor(JSContext* cx, JSObject* obj,
 158                                          bool* result);
 159
 160 extern bool ObjectMayHaveExtraIndexedOwnProperties(JSObject* obj);
 161
 162 extern bool ObjectMayHaveExtraIndexedProperties(JSObject* obj);
 163
 164 extern bool PrototypeMayHaveIndexedProperties(NativeObject* obj);
 165
 166 // JS::IsArray has multiple overloads, use js::IsArrayFromJit to disambiguate.
 167 extern bool IsArrayFromJit(JSContext* cx, HandleObject obj, bool* isArray);
 168
 169 extern bool ArrayLengthGetter(JSContext* cx, HandleObject obj, HandleId id,
 170                               MutableHandleValue vp);
 171
 172 extern bool ArrayLengthSetter(JSContext* cx, HandleObject obj, HandleId id,
 173                               HandleValue v, ObjectOpResult& result);
 174
 175 // Note: we use uint32_t because the JIT code uses branch32.
 176 enum class ArraySortResult : uint32_t {
 177   Failure,
 178   Done,
 179   CallJS,
 180   CallJSSameRealmNoRectifier
 181 };
 182
 183 // We use a JIT trampoline to optimize sorting with a comparator function. The
 184 // trampoline frame has an ArraySortData instance that contains all state used
 185 // by the sorting algorithm. The sorting algorithm is implemented as a C++
 186 // "generator" that can yield to the trampoline to perform a fast JIT => JIT
 187 // call to the comparator function. When the comparator function returns, the
 188 // trampoline calls back into C++ to resume the sorting algorithm.
 189 //
 190 // ArraySortData stores the JS Values in a js::Vector. To ensure we don't leak
 191 // its memory, we have debug assertions to check that for each C++ constructor
 192 // call we call |freeMallocData| exactly once. C++ code calls |freeMallocData|
 193 // when it's done sorting and the JIT exception handler calls it when unwinding
 194 // the trampoline frame.
 195 class ArraySortData {
 196  public:
 197   enum class ComparatorKind : uint8_t {
 198     Unoptimized,
 199     JS,
 200     JSSameRealmNoRectifier,
 201   };
 202
 203   static constexpr size_t ComparatorActualArgs = 2;
 204
 205   // Insertion sort is used if the length is < InsertionSortLimit.
 206   static constexpr size_t InsertionSortLimit = 24;
 207
 208   using ValueVector = GCVector<Value, 8, SystemAllocPolicy>;
 209
 210  protected:  // Silence Clang warning about unused private fields.
 211   // Data for the comparator call. These fields must match the JitFrameLayout
 212   // to let us perform efficient calls to the comparator from JIT code.
 213   // This is asserted in the JIT trampoline code.
 214   // callArgs[0] is also used to store the return value of the sort function and
 215   // the comparator.
 216   uintptr_t descriptor_;
 217   JSObject* comparator_ = nullptr;
 218   Value thisv;
 219   Value callArgs[ComparatorActualArgs];
 220
 221  private:
 222   ValueVector vec;
 223   Value item;
 224   JSContext* cx_;
 225   JSObject* obj_ = nullptr;
 226
 227   Value* list;
 228   Value* out;
 229
 230   // The value of the .length property.
 231   uint32_t length;
 232
 233   // The number of items to sort. Can be less than |length| if the object has
 234   // holes.
 235   uint32_t denseLen;
 236
 237   uint32_t windowSize;
 238   uint32_t start;
 239   uint32_t mid;
 240   uint32_t end;
 241   uint32_t i, j, k;
 242
 243   // The state value determines where we resume in sortWithComparator.
 244   enum class State : uint8_t {
 245     Initial,
 246     InsertionSortCall1,
 247     InsertionSortCall2,
 248     MergeSortCall1,
 249     MergeSortCall2
 250   };
 251   State state = State::Initial;
 252   ComparatorKind comparatorKind_;
 253
 254   // Optional padding to ensure proper alignment of the comparator JIT frame.
 255 #if !defined(JS_64BIT) && !defined(DEBUG)
 256  protected:  // Silence Clang warning about unused private field.
 257   size_t padding;
 258 #endif
 259
 260  public:
 261   explicit ArraySortData(JSContext* cx);
 262
 263   void MOZ_ALWAYS_INLINE init(JSObject* obj, JSObject* comparator,
 264                               ValueVector&& vec, uint32_t length,
 265                               uint32_t denseLen);
 266
 267   JSContext* cx() const { return cx_; }
 268
 269   JSObject* comparator() const {
 270     MOZ_ASSERT(comparator_);
 271     return comparator_;
 272   }
 273
 274   Value returnValue() const { return callArgs[0]; }
 275   void setReturnValue(JSObject* obj) { callArgs[0].setObject(*obj); }
 276
 277   Value comparatorArg(size_t index) {
 278     MOZ_ASSERT(index < ComparatorActualArgs);
 279     return callArgs[index];
 280   }
 281   Value comparatorThisValue() const { return thisv; }
 282   Value comparatorReturnValue() const { return callArgs[0]; }
 283   void setComparatorArgs(const Value& x, const Value& y) {
 284     callArgs[0] = x;
 285     callArgs[1] = y;
 286   }
 287   void setComparatorReturnValue(const Value& v) { callArgs[0] = v; }
 288
 289   ComparatorKind comparatorKind() const { return comparatorKind_; }
 290
 291   static ArraySortResult sortWithComparator(ArraySortData* d);
 292
 293   void freeMallocData();
 294   void trace(JSTracer* trc);
 295
 296   static constexpr int32_t offsetOfDescriptor() {
 297     return offsetof(ArraySortData, descriptor_);
 298   }
 299   static constexpr int32_t offsetOfComparator() {
 300     return offsetof(ArraySortData, comparator_);
 301   }
 302   static constexpr int32_t offsetOfComparatorReturnValue() {
 303     return offsetof(ArraySortData, callArgs[0]);
 304   }
 305   static constexpr int32_t offsetOfComparatorThis() {
 306     return offsetof(ArraySortData, thisv);
 307   }
 308   static constexpr int32_t offsetOfComparatorArgs() {
 309     return offsetof(ArraySortData, callArgs);
 310   }
 311 };
 312
 313 extern ArraySortResult ArraySortFromJit(
 314     JSContext* cx, jit::TrampolineNativeFrameLayout* frame);
 315
 316 class MOZ_NON_TEMPORARY_CLASS ArraySpeciesLookup final {
 317   /*
 318    * An ArraySpeciesLookup holds the following:
 319    *
 320    *  Array.prototype (arrayProto_)
 321    *      To ensure that the incoming array has the standard proto.
 322    *
 323    *  Array.prototype's shape (arrayProtoShape_)
 324    *      To ensure that Array.prototype has not been modified.
 325    *
 326    *  Array (arrayConstructor_)
 327    *  Array's shape (arrayConstructorShape_)
 328    *       To ensure that Array has not been modified.
 329    *
 330    *  Array.prototype's slot number for constructor (arrayProtoConstructorSlot_)
 331    *      To quickly retrieve and ensure that the Array constructor
 332    *      stored in the slot has not changed.
 333    *
 334    *  Array's slot number for the @@species getter. (arraySpeciesGetterSlot_)
 335    *  Array's canonical value for @@species (canonicalSpeciesFunc_)
 336    *      To quickly retrieve and ensure that the @@species getter for Array
 337    *      has not changed.
 338    *
 339    * MOZ_INIT_OUTSIDE_CTOR fields below are set in |initialize()|.  The
 340    * constructor only initializes a |state_| field, that defines whether the
 341    * other fields are accessible.
 342    */
 343
 344   // Pointer to canonical Array.prototype and Array.
 345   MOZ_INIT_OUTSIDE_CTOR NativeObject* arrayProto_;
 346   MOZ_INIT_OUTSIDE_CTOR NativeObject* arrayConstructor_;
 347
 348   // Shape of matching Array, and slot containing the @@species property, and
 349   // the canonical value.
 350   MOZ_INIT_OUTSIDE_CTOR Shape* arrayConstructorShape_;
 351   MOZ_INIT_OUTSIDE_CTOR uint32_t arraySpeciesGetterSlot_;
 352   MOZ_INIT_OUTSIDE_CTOR JSFunction* canonicalSpeciesFunc_;
 353
 354   // Shape of matching Array.prototype object, and slot containing the
 355   // constructor for it.
 356   MOZ_INIT_OUTSIDE_CTOR Shape* arrayProtoShape_;
 357   MOZ_INIT_OUTSIDE_CTOR uint32_t arrayProtoConstructorSlot_;
 358
 359   enum class State : uint8_t {
 360     // Flags marking the lazy initialization of the above fields.
 361     Uninitialized,
 362     Initialized,
 363
 364     // The disabled flag is set when we don't want to try optimizing
 365     // anymore because core objects were changed.
 366     Disabled
 367   };
 368
 369   State state_ = State::Uninitialized;
 370
 371   // Initialize the internal fields.
 372   void initialize(JSContext* cx);
 373
 374   // Reset the cache.
 375   void reset();
 376
 377   // Check if the global array-related objects have not been messed with
 378   // in a way that would disable this cache.
 379   bool isArrayStateStillSane();
 380
 381  public:
 382   /** Construct an |ArraySpeciesLookup| in the uninitialized state. */
 383   ArraySpeciesLookup() { reset(); }
 384
 385   // Try to optimize the @@species lookup for an array.
 386   bool tryOptimizeArray(JSContext* cx, ArrayObject* array);
 387
 388   // Purge the cache and all info associated with it.
 389   void purge() {
 390     if (state_ == State::Initialized) {
 391       reset();
 392     }
 393   }
 394 };
 395
 396 } /* namespace js */
 397
 398 #endif /* builtin_Array_h */