Fix setting array length to be ES5 conform.

src/elements.cc

 // Copyright 2011 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
@@ skipping 13 matching lines @@
 // 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.
 
 #include "v8.h"
 
 #include "objects.h"
 #include "elements.h"
 #include "utils.h"
 
+
+// Each concrete ElementsAccessor can handle exactly one ElementsKind,
+// several abstract ElementsAccessor classes are used to allow sharing
+// common code.
+//
+// Inheritance hierarchy:
+// - ElementsAccessorBase                        (abstract)
+//   - FastElementsAccessor                      (abstract)
+//     - FastObjectElementsAccessor
+//     - FastDoubleElementsAccessor
+//   - ExternalElementsAccessor                  (abstract)
+//     - ExternalByteElementsAccessor
+//     - ExternalUnsignedByteElementsAccessor
+//     - ExternalShortElementsAccessor
+//     - ExternalUnsignedShortElementsAccessor
+//     - ExternalIntElementsAccessor
+//     - ExternalUnsignedIntElementsAccessor
+//     - ExternalFloatElementsAccessor
+//     - ExternalDoubleElementsAccessor
+//     - PixelElementsAccessor
+//   - DictionaryElementsAccessor
+//   - NonStrictArgumentsElementsAccessor
+
+
 namespace v8 {
 namespace internal {
 
 
 ElementsAccessor** ElementsAccessor::elements_accessors_;
 
 
-bool HasKey(FixedArray* array, Object* key) {
+static bool HasKey(FixedArray* array, Object* key) {
   int len0 = array->length();
   for (int i = 0; i < len0; i++) {
     Object* element = array->get(i);
     if (element->IsSmi() && element == key) return true;
     if (element->IsString() &&
         key->IsString() && String::cast(element)->Equals(String::cast(key))) {
       return true;
     }
   }
   return false;
 }
 
 
+static Failure* ArrayLengthRangeError(Heap* heap) {

[danno, 2011/11/07 19:26:02]

Call this ThrowArrayLengthRangeError

[Michael Starzinger, 2011/11/08 12:00:33]

Done.

+  HandleScope scope(heap->isolate());
+  return heap->isolate()->Throw(
+      *heap->isolate()->factory()->NewRangeError("invalid_array_length",
+          HandleVector<Object>(NULL, 0)));
+}
+
+
 // Base class for element handler implementations. Contains the
 // the common logic for objects with different ElementsKinds.
 // Subclasses must specialize method for which the element
 // implementation differs from the base class implementation.
 //
 // This class is intended to be used in the following way:
 //
 //   class SomeElementsAccessor :
 //       public ElementsAccessorBase<SomeElementsAccessor,
 //                                   BackingStoreClass> {
@@ skipping 19 matching lines @@
   static MaybeObject* Get(BackingStoreClass* backing_store,
                           uint32_t key,
                           JSObject* obj,
                           Object* receiver) {
     if (key < ElementsAccessorSubclass::GetCapacity(backing_store)) {
       return backing_store->get(key);
     }
     return backing_store->GetHeap()->the_hole_value();
   }
 
+  virtual MaybeObject* SetLength(JSObject* obj,
+                                 Object* length) {
+    ASSERT(obj->IsJSArray());
+    return ElementsAccessorSubclass::SetLength(
+        BackingStoreClass::cast(obj->elements()), obj, length);
+  }
+
+  static MaybeObject* SetLength(BackingStoreClass* backing_store,
+                                JSObject* obj,
+                                Object* length);
+
   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) = 0;
 
   virtual MaybeObject* AddElementsToFixedArray(FixedArrayBase* from,
                                                FixedArray* to,
                                                JSObject* holder,
                                                Object* receiver) {
     int len0 = to->length();
 #ifdef DEBUG
@@ skipping 111 matching lines @@
                                               uint32_t index) {
     return ElementsAccessorSubclass::GetKeyForIndex(
         BackingStoreClass::cast(backing_store), index);
   }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase);
 };
 
 
+// Super class for all fast element arrays.
+template<typename FastElementsAccessorSubclass,
+         typename BackingStore,
+         int ElementSize>
 class FastElementsAccessor
-    : public ElementsAccessorBase<FastElementsAccessor, FixedArray> {
+    : public ElementsAccessorBase<FastElementsAccessorSubclass, BackingStore> {
+ protected:
+  friend class ElementsAccessorBase<FastElementsAccessorSubclass, BackingStore>;
+
+  // Adjusts the length of the fast backing store or returns the new length or
+  // undefined in case conversion to a slow backing store should be performed.
+  static MaybeObject* SetLengthWithoutNormalize(BackingStore* backing_store,
+                                                JSArray* array,
+                                                Object* length_object,
+                                                uint32_t length) {
+    uint32_t old_capacity = backing_store->length();
+
+    // Check whether the backing store should be shrunk.
+    if (length <= old_capacity) {
+      if (array->HasFastTypeElements()) {
+        MaybeObject* maybe_obj = array->EnsureWritableFastElements();
+        if (!maybe_obj->To(&backing_store)) return maybe_obj;
+      }
+      if (2 * length <= old_capacity) {
+        // If more than half the elements won't be used, trim the array.
+        if (length == 0) {
+          array->initialize_elements();
+        } else {
+          backing_store->set_length(length);
+          Address filler_start = backing_store->address() +
+              BackingStore::OffsetOfElementAt(length);
+          int filler_size = (old_capacity - length) * ElementSize;
+          array->GetHeap()->CreateFillerObjectAt(filler_start, filler_size);
+        }
+      } else {
+        // Otherwise, fill the unused tail with holes.
+        int old_length = FastD2I(array->length()->Number());
+        for (int i = length; i < old_length; i++) {
+          backing_store->set_the_hole(i);
+        }
+      }
+      return length_object;
+    }
+
+    // Check whether the backing store should be expanded.
+    uint32_t min = JSObject::NewElementsCapacity(old_capacity);
+    uint32_t new_capacity = length > min ? length : min;
+    if (!array->ShouldConvertToSlowElements(new_capacity)) {
+      MaybeObject* result = FastElementsAccessorSubclass::
+          SetFastElementsCapacityAndLength(array, new_capacity, length);
+      if (result->IsFailure()) return result;
+      return length_object;
+    }
+
+    // Request conversion to slow elements.
+    return array->GetHeap()->undefined_value();
+  }
+};
+
+
+class FastObjectElementsAccessor
+    : public FastElementsAccessor<FastObjectElementsAccessor,
+                                  FixedArray,
+                                  kPointerSize> {
  public:
   static MaybeObject* DeleteCommon(JSObject* obj,
                                    uint32_t key) {
     ASSERT(obj->HasFastElements() ||
            obj->HasFastSmiOnlyElements() ||
            obj->HasFastArgumentsElements());
     Heap* heap = obj->GetHeap();
     FixedArray* backing_store = FixedArray::cast(obj->elements());
     if (backing_store->map() == heap->non_strict_arguments_elements_map()) {
       backing_store = FixedArray::cast(backing_store->get(1));
@@ skipping 28 matching lines @@
         if (4 * num_used <= backing_store->length()) {
           MaybeObject* result = obj->NormalizeElements();
           if (result->IsFailure()) return result;
         }
       }
     }
     return heap->true_value();
   }
 
  protected:
+  friend class FastElementsAccessor<FastObjectElementsAccessor,
+                                    FixedArray,
+                                    kPointerSize>;
+
+  static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
+                                                       uint32_t capacity,
+                                                       uint32_t length) {
+    JSObject::SetFastElementsCapacityMode set_capacity_mode =
+        obj->GetElementsKind() == FAST_SMI_ONLY_ELEMENTS

[danno, 2011/11/07 19:26:02]

Use obj->HasFastSmiOnlyElements()

[Michael Starzinger, 2011/11/08 12:00:33]

Done.

+            ? JSObject::kAllowSmiOnlyElements
+            : JSObject::kDontAllowSmiOnlyElements;
+    return obj->SetFastElementsCapacityAndLength(capacity,
+                                                 length,
+                                                 set_capacity_mode);
+  }
+
   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) {
     return DeleteCommon(obj, key);
   }
 };
 
 
 class FastDoubleElementsAccessor
-    : public ElementsAccessorBase<FastDoubleElementsAccessor,
-                                  FixedDoubleArray> {
+    : public FastElementsAccessor<FastDoubleElementsAccessor,
+                                  FixedDoubleArray,
+                                  kDoubleSize> {
  protected:
   friend class ElementsAccessorBase<FastDoubleElementsAccessor,
                                     FixedDoubleArray>;
+  friend class FastElementsAccessor<FastDoubleElementsAccessor,
+                                    FixedDoubleArray,
+                                    kDoubleSize>;
+
+  static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
+                                                       uint32_t capacity,
+                                                       uint32_t length) {
+    return obj->SetFastDoubleElementsCapacityAndLength(capacity, length);
+  }
 
   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) {
     int length = obj->IsJSArray()
         ? Smi::cast(JSArray::cast(obj)->length())->value()
         : FixedDoubleArray::cast(obj->elements())->length();
     if (key < static_cast<uint32_t>(length)) {
       FixedDoubleArray::cast(obj->elements())->set_the_hole(key);
     }
@@ skipping 23 matching lines @@
                           uint32_t key,
                           JSObject* obj,
                           Object* receiver) {
     if (key < ExternalElementsAccessorSubclass::GetCapacity(backing_store)) {
       return backing_store->get(key);
     } else {
       return backing_store->GetHeap()->undefined_value();
     }
   }
 
+  static MaybeObject* SetLength(ExternalArray* backing_store,
+                                JSObject* obj,
+                                Object* length) {
+    // External arrays do not support changing their length.
+    UNREACHABLE();
+    return obj;
+  }
+
   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) {
     // External arrays always ignore deletes.
     return obj->GetHeap()->true_value();
   }
 };
 
 
 class ExternalByteElementsAccessor
@@ skipping 47 matching lines @@
 class PixelElementsAccessor
     : public ExternalElementsAccessor<PixelElementsAccessor,
                                       ExternalPixelArray> {
 };
 
 
 class DictionaryElementsAccessor
     : public ElementsAccessorBase<DictionaryElementsAccessor,
                                   NumberDictionary> {
  public:
+  // Adjusts the length of the dictionary backing store and returns the new
+  // length according to ES5 section 15.4.5.2 behavior.
+  static MaybeObject* SetLengthWithoutNormalize(NumberDictionary* dict,
+                                                JSArray* array,
+                                                Object* length_object,
+                                                uint32_t length) {
+    if (length == 0) {
+      // If the length of a slow array is reset to zero, we clear
+      // the array and flush backing storage. This has the added
+      // benefit that the array returns to fast mode.
+      Object* obj;
+      { MaybeObject* maybe_obj = array->ResetElements();

[danno, 2011/11/07 19:26:02]

This weird formatting is an artifact of an automated GC-related change that went
in a long time ago. Take this opportunity to remove the unneeded extra scope and
clean this up. 

[Michael Starzinger, 2011/11/08 12:00:33]

Done.

+        if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+      }
+    } else {
+      uint32_t new_length = length;
+      uint32_t old_length = static_cast<uint32_t>(array->length()->Number());
+      if (new_length < old_length) {
+        // Find last non-deletable element in range of elements to be
+        // deleted and adjust range accordingly.
+        Heap* heap = array->GetHeap();
+        int capacity = dict->Capacity();
+        for (int i = 0; i < capacity; i++) {
+          Object* key = dict->KeyAt(i);
+          if (key->IsNumber()) {
+            uint32_t number = static_cast<uint32_t>(key->Number());
+            if (new_length <= number && number < old_length) {
+              PropertyDetails details = dict->DetailsAt(i);
+              if (details.IsDontDelete()) new_length = number + 1;
+            }
+          }
+        }
+        if (new_length != length) {
+          MaybeObject* maybe_object = heap->NumberFromUint32(new_length);
+          if (!maybe_object->To(&length_object)) return maybe_object;
+        }
+
+        // Remove elements that should be deleted.
+        int removed_entries = 0;
+        Object* sentinel = heap->null_value();
+        for (int i = 0; i < capacity; i++) {
+          Object* key = dict->KeyAt(i);
+          if (key->IsNumber()) {
+            uint32_t number = static_cast<uint32_t>(key->Number());
+            if (new_length <= number && number < old_length) {
+              dict->SetEntry(i, sentinel, sentinel);
+              removed_entries++;
+            }
+          }
+        }
+
+        // Update the number of elements.
+        dict->ElementsRemoved(removed_entries);
+      }
+    }
+    return length_object;
+  }
+
   static MaybeObject* DeleteCommon(JSObject* obj,
                                    uint32_t key,
                                    JSReceiver::DeleteMode mode) {
     Isolate* isolate = obj->GetIsolate();
     Heap* heap = isolate->heap();
     FixedArray* backing_store = FixedArray::cast(obj->elements());
     bool is_arguments =
         (obj->GetElementsKind() == NON_STRICT_ARGUMENTS_ELEMENTS);
     if (is_arguments) {
       backing_store = FixedArray::cast(backing_store->get(1));
@@ skipping 89 matching lines @@
     } else {
       // Object is not mapped, defer to the arguments.
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
       return ElementsAccessor::ForArray(arguments)->Get(arguments,
                                                         key,
                                                         obj,
                                                         receiver);
     }
   }
 
+  static MaybeObject* SetLength(FixedArray* parameter_map,
+                                JSObject* obj,
+                                Object* length) {
+    // TODO(mstarzinger): This was never implemented but will be used once we
+    // correctly implement [[DefineOwnProperty]] on arrays.
+    UNIMPLEMENTED();
+    return obj;
+  }
+
   virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t key
-                              ,
+                              uint32_t key,
                               JSReceiver::DeleteMode mode) {
     FixedArray* parameter_map = FixedArray::cast(obj->elements());
     Object* probe = GetParameterMapArg(parameter_map, key);
     if (!probe->IsTheHole()) {
       // TODO(kmillikin): We could check if this was the last aliased
       // parameter, and revert to normal elements in that case.  That
       // would enable GC of the context.
       parameter_map->set_the_hole(key + 2);
     } else {
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
       if (arguments->IsDictionary()) {
         return DictionaryElementsAccessor::DeleteCommon(obj, key, mode);
       } else {
-        return FastElementsAccessor::DeleteCommon(obj, key);
+        return FastObjectElementsAccessor::DeleteCommon(obj, key);
       }
     }
     return obj->GetHeap()->true_value();
   }
 
   static uint32_t GetCapacity(FixedArray* parameter_map) {
     FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
     return Max(static_cast<uint32_t>(parameter_map->length() - 2),
                ForArray(arguments)->GetCapacity(arguments));
   }
@@ skipping 58 matching lines @@
       UNREACHABLE();
       return NULL;
   }
 }
 
 
 void ElementsAccessor::InitializeOncePerProcess() {
   static struct ConcreteElementsAccessors {
     // Use the fast element handler for smi-only arrays. The implementation is
     // currently identical.
-    FastElementsAccessor fast_smi_elements_handler;
-    FastElementsAccessor fast_elements_handler;
+    FastObjectElementsAccessor fast_smi_elements_handler;
+    FastObjectElementsAccessor fast_elements_handler;
     FastDoubleElementsAccessor fast_double_elements_handler;
     DictionaryElementsAccessor dictionary_elements_handler;
     NonStrictArgumentsElementsAccessor non_strict_arguments_elements_handler;
     ExternalByteElementsAccessor byte_elements_handler;
     ExternalUnsignedByteElementsAccessor unsigned_byte_elements_handler;
     ExternalShortElementsAccessor short_elements_handler;
     ExternalUnsignedShortElementsAccessor unsigned_short_elements_handler;
     ExternalIntElementsAccessor int_elements_handler;
     ExternalUnsignedIntElementsAccessor unsigned_int_elements_handler;
     ExternalFloatElementsAccessor float_elements_handler;
@@ skipping 18 matching lines @@
     &element_accessors.pixel_elements_handler
   };
 
   STATIC_ASSERT((sizeof(accessor_array) / sizeof(*accessor_array)) ==
                 kElementsKindCount);
 
   elements_accessors_ = accessor_array;
 }
 
 
+template <typename ElementsAccessorSubclass, typename BackingStoreClass>
+MaybeObject* ElementsAccessorBase<ElementsAccessorSubclass, BackingStoreClass>::
+    SetLength(BackingStoreClass* backing_store,
+              JSObject* obj,
+              Object* length) {
+  JSArray* array = JSArray::cast(obj);
+
+  // Fast case: The new length fits into a Smi.
+  MaybeObject* maybe_smi_length = length->ToSmi();
+  Object* smi_length = Smi::FromInt(0);
+  if (maybe_smi_length->ToObject(&smi_length) && smi_length->IsSmi()) {
+    const int value = Smi::cast(smi_length)->value();
+    if (value >= 0) {
+      Object* new_length;
+      MaybeObject* result = ElementsAccessorSubclass::
+          SetLengthWithoutNormalize(backing_store, array, smi_length, value);
+      if (!result->ToObject(&new_length)) return result;
+      ASSERT(new_length->IsSmi() || new_length->IsUndefined());
+      if (new_length->IsSmi()) {
+        array->set_length(Smi::cast(new_length));
+        return array;
+      }
+    } else {
+      return ArrayLengthRangeError(array->GetHeap());
+    }
+  }
+
+  // Slow case: The new length does not fit into a Smi or conversion
+  // to slow elements is needed for other reasons.
+  if (length->IsNumber()) {
+    uint32_t value;
+    if (length->ToArrayIndex(&value)) {
+      NumberDictionary* dictionary;
+      { MaybeObject* maybe_object = array->NormalizeElements();
+        if (!maybe_object->To(&dictionary)) return maybe_object;

[danno, 2011/11/07 19:26:02]

remove extra scope

[Michael Starzinger, 2011/11/08 12:00:33]

Done.

+      }
+      Object* new_length;
+      MaybeObject* result = DictionaryElementsAccessor::
+          SetLengthWithoutNormalize(dictionary, array, length, value);
+      if (!result->ToObject(&new_length)) return result;
+      ASSERT(new_length->IsNumber());
+      array->set_length(new_length);
+      return array;
+    } else {
+      return ArrayLengthRangeError(array->GetHeap());
+    }
+  }
+
+  // Fall-back case: The new length is not a number so make the array
+  // size one and set only element to length.
+  FixedArray* new_backing_store;
+  { MaybeObject* maybe_obj = array->GetHeap()->AllocateFixedArray(1);

[danno, 2011/11/07 19:26:02]

prune extra scope

[Michael Starzinger, 2011/11/08 12:00:33]

Done.

+    if (!maybe_obj->To(&new_backing_store)) return maybe_obj;
+  }
+  new_backing_store->set(0, length);
+
+  { MaybeObject* maybe_obj = array->EnsureCanContainElements(&length, 1);

[danno, 2011/11/07 19:26:02]

prune extra scope

[Michael Starzinger, 2011/11/08 12:00:33]

Done.

+    if (maybe_obj->IsFailure()) return maybe_obj;
+  }
+
+  array->set_length(Smi::FromInt(1));
+  array->set_elements(new_backing_store);

[danno, 2011/11/07 19:26:02]

Consider using array->SetContent to simplify the previous several lines.

[Michael Starzinger, 2011/11/08 12:00:33]

Done.

+  return array;
+}
+
+
 } }  // namespace v8::internal