Fix setting array length to be ES5 conform.

src/elements.cc

Index: src/elements.cc
diff --git a/src/elements.cc b/src/elements.cc
index 5e7a84e38b8377a6009a93ecc4967832f168dc19..7bc8180477e56a171a8f5c7782001771f05f8c46 100644
--- a/src/elements.cc
+++ b/src/elements.cc
@@ -31,6 +31,30 @@
 #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 {
 
@@ -38,7 +62,7 @@ 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);
@@ -52,6 +76,14 @@ bool HasKey(FixedArray* array, Object* key) {
 }
 
 
+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
@@ -91,6 +123,17 @@ class ElementsAccessorBase : public ElementsAccessor {
     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;
@@ -222,8 +265,70 @@ class ElementsAccessorBase : public ElementsAccessor {
 };
 
 
+// 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) {
@@ -272,6 +377,22 @@ class FastElementsAccessor
   }
 
  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) {
@@ -281,11 +402,21 @@ class FastElementsAccessor
 
 
 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,
@@ -329,6 +460,14 @@ class ExternalElementsAccessor
     }
   }
 
+  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) {
@@ -396,6 +535,64 @@ 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) {
@@ -505,9 +702,17 @@ class NonStrictArgumentsElementsAccessor
     }
   }
 
+  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);
@@ -521,7 +726,7 @@ class NonStrictArgumentsElementsAccessor
       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();
@@ -600,8 +805,8 @@ 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;
@@ -640,4 +845,70 @@ void ElementsAccessor::InitializeOncePerProcess() {
 }
 
 
+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