src/elements.cc - platform/external/v8 - Git at Google

 // 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
 //       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.

 #include "v8.h"

 #include "objects.h"
 #include "elements.h"
 #include "utils.h"

 namespace v8 {
 namespace internal {


 ElementsAccessor** ElementsAccessor::elements_accessors_;


 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;
 }


 // 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> {
 //     ...
 //   }
 //
 // This is an example of the Curiously Recurring Template Pattern (see
 // http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).  We use
 // CRTP to guarantee aggressive compile time optimizations (i.e.  inlining and
 // specialization of SomeElementsAccessor methods).
 template <typename ElementsAccessorSubclass, typename BackingStoreClass>
 class ElementsAccessorBase : public ElementsAccessor {
  protected:
   ElementsAccessorBase() { }
   virtual MaybeObject* Get(FixedArrayBase* backing_store,
                            uint32_t key,
                            JSObject* obj,
                            Object* receiver) {
     return ElementsAccessorSubclass::Get(
         BackingStoreClass::cast(backing_store), key, obj, receiver);
   }

   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* 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
     if (FLAG_enable_slow_asserts) {
       for (int i = 0; i < len0; i++) {
         ASSERT(!to->get(i)->IsTheHole());
       }
     }
 #endif
     BackingStoreClass* backing_store = BackingStoreClass::cast(from);
     uint32_t len1 = ElementsAccessorSubclass::GetCapacity(backing_store);

     // Optimize if 'other' is empty.
     // We cannot optimize if 'this' is empty, as other may have holes.
     if (len1 == 0) return to;

     // Compute how many elements are not in other.
     int extra = 0;
     for (uint32_t y = 0; y < len1; y++) {
       if (ElementsAccessorSubclass::HasElementAtIndex(backing_store,
                                                       y,
                                                       holder,
                                                       receiver)) {
         uint32_t key =
             ElementsAccessorSubclass::GetKeyForIndex(backing_store, y);
         MaybeObject* maybe_value =
             ElementsAccessorSubclass::Get(backing_store, key, holder, receiver);
         Object* value;
         if (!maybe_value->ToObject(&value)) return maybe_value;
         ASSERT(!value->IsTheHole());
         if (!HasKey(to, value)) {
           extra++;
         }
       }
     }

     if (extra == 0) return to;

     // Allocate the result
     FixedArray* result;
     MaybeObject* maybe_obj =
         backing_store->GetHeap()->AllocateFixedArray(len0 + extra);
     if (!maybe_obj->To<FixedArray>(&result)) return maybe_obj;

     // Fill in the content
     {
       AssertNoAllocation no_gc;
       WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
       for (int i = 0; i < len0; i++) {
         Object* e = to->get(i);
         ASSERT(e->IsString() || e->IsNumber());
         result->set(i, e, mode);
       }
     }
     // Fill in the extra values.
     int index = 0;
     for (uint32_t y = 0; y < len1; y++) {
       if (ElementsAccessorSubclass::HasElementAtIndex(backing_store,
                                                       y,
                                                       holder,
                                                       receiver)) {
         uint32_t key =
             ElementsAccessorSubclass::GetKeyForIndex(backing_store, y);
         MaybeObject* maybe_value =
             ElementsAccessorSubclass::Get(backing_store, key, holder, receiver);
         Object* value;
         if (!maybe_value->ToObject(&value)) return maybe_value;
         if (!value->IsTheHole() && !HasKey(to, value)) {
           result->set(len0 + index, value);
           index++;
         }
       }
     }
     ASSERT(extra == index);
     return result;
   }

  protected:
   static uint32_t GetCapacity(BackingStoreClass* backing_store) {
     return backing_store->length();
   }

   virtual uint32_t GetCapacity(FixedArrayBase* backing_store) {
     return ElementsAccessorSubclass::GetCapacity(
         BackingStoreClass::cast(backing_store));
   }

   static bool HasElementAtIndex(BackingStoreClass* backing_store,
                                 uint32_t index,
                                 JSObject* holder,
                                 Object* receiver) {
     uint32_t key =
         ElementsAccessorSubclass::GetKeyForIndex(backing_store, index);
     MaybeObject* element = ElementsAccessorSubclass::Get(backing_store,
                                                          key,
                                                          holder,
                                                          receiver);
     return !element->IsTheHole();
   }

   virtual bool HasElementAtIndex(FixedArrayBase* backing_store,
                                  uint32_t index,
                                  JSObject* holder,
                                  Object* receiver) {
     return ElementsAccessorSubclass::HasElementAtIndex(
         BackingStoreClass::cast(backing_store), index, holder, receiver);
   }

   static uint32_t GetKeyForIndex(BackingStoreClass* backing_store,
                                  uint32_t index) {
     return index;
   }

   virtual uint32_t GetKeyForIndex(FixedArrayBase* backing_store,
                                               uint32_t index) {
     return ElementsAccessorSubclass::GetKeyForIndex(
         BackingStoreClass::cast(backing_store), index);
   }

  private:
   DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase);
 };


 class FastElementsAccessor
     : public ElementsAccessorBase<FastElementsAccessor, FixedArray> {
  public:
   static MaybeObject* DeleteCommon(JSObject* obj,
                                    uint32_t key) {
     ASSERT(obj->HasFastElements() || 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));
     } else {
       Object* writable;
       MaybeObject* maybe = obj->EnsureWritableFastElements();
       if (!maybe->ToObject(&writable)) return maybe;
       backing_store = FixedArray::cast(writable);
     }
     uint32_t length = static_cast<uint32_t>(
         obj->IsJSArray()
         ? Smi::cast(JSArray::cast(obj)->length())->value()
         : backing_store->length());
     if (key < length) {
       backing_store->set_the_hole(key);
       // If an old space backing store is larger than a certain size and
       // has too few used values, normalize it.
       // To avoid doing the check on every delete we require at least
       // one adjacent hole to the value being deleted.
       Object* hole = heap->the_hole_value();
       const int kMinLengthForSparsenessCheck = 64;
       if (backing_store->length() >= kMinLengthForSparsenessCheck &&
           !heap->InNewSpace(backing_store) &&
           ((key > 0 && backing_store->get(key - 1) == hole) ||
            (key + 1 < length && backing_store->get(key + 1) == hole))) {
         int num_used = 0;
         for (int i = 0; i < backing_store->length(); ++i) {
           if (backing_store->get(i) != hole) ++num_used;
           // Bail out early if more than 1/4 is used.
           if (4 * num_used > backing_store->length()) break;
         }
         if (4 * num_used <= backing_store->length()) {
           MaybeObject* result = obj->NormalizeElements();
           if (result->IsFailure()) return result;
         }
       }
     }
     return heap->true_value();
   }

  protected:
   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) {
     return DeleteCommon(obj, key);
   }
 };


 class FastDoubleElementsAccessor
     : public ElementsAccessorBase<FastDoubleElementsAccessor,
                                   FixedDoubleArray> {
  protected:
   friend class ElementsAccessorBase<FastDoubleElementsAccessor,
                                     FixedDoubleArray>;

   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);
     }
     return obj->GetHeap()->true_value();
   }

   static bool HasElementAtIndex(FixedDoubleArray* backing_store,
                                 uint32_t index,
                                 JSObject* holder,
                                 Object* receiver) {
     return !backing_store->is_the_hole(index);
   }
 };


 // Super class for all external element arrays.
 template<typename ExternalElementsAccessorSubclass,
          typename ExternalArray>
 class ExternalElementsAccessor
     : public ElementsAccessorBase<ExternalElementsAccessorSubclass,
                                   ExternalArray> {
  protected:
   friend class ElementsAccessorBase<ExternalElementsAccessorSubclass,
                                     ExternalArray>;

   static MaybeObject* Get(ExternalArray* backing_store,
                           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();
     }
   }

   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) {
     // External arrays always ignore deletes.
     return obj->GetHeap()->true_value();
   }
 };


 class ExternalByteElementsAccessor
     : public ExternalElementsAccessor<ExternalByteElementsAccessor,
                                       ExternalByteArray> {
 };


 class ExternalUnsignedByteElementsAccessor
     : public ExternalElementsAccessor<ExternalUnsignedByteElementsAccessor,
                                       ExternalUnsignedByteArray> {
 };


 class ExternalShortElementsAccessor
     : public ExternalElementsAccessor<ExternalShortElementsAccessor,
                                       ExternalShortArray> {
 };


 class ExternalUnsignedShortElementsAccessor
     : public ExternalElementsAccessor<ExternalUnsignedShortElementsAccessor,
                                       ExternalUnsignedShortArray> {
 };


 class ExternalIntElementsAccessor
     : public ExternalElementsAccessor<ExternalIntElementsAccessor,
                                       ExternalIntArray> {
 };


 class ExternalUnsignedIntElementsAccessor
     : public ExternalElementsAccessor<ExternalUnsignedIntElementsAccessor,
                                       ExternalUnsignedIntArray> {
 };


 class ExternalFloatElementsAccessor
     : public ExternalElementsAccessor<ExternalFloatElementsAccessor,
                                       ExternalFloatArray> {
 };


 class ExternalDoubleElementsAccessor
     : public ExternalElementsAccessor<ExternalDoubleElementsAccessor,
                                       ExternalDoubleArray> {
 };


 class PixelElementsAccessor
     : public ExternalElementsAccessor<PixelElementsAccessor,
                                       ExternalPixelArray> {
 };


 class DictionaryElementsAccessor
     : public ElementsAccessorBase<DictionaryElementsAccessor,
                                   NumberDictionary> {
  public:
   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() == JSObject::NON_STRICT_ARGUMENTS_ELEMENTS);
     if (is_arguments) {
       backing_store = FixedArray::cast(backing_store->get(1));
     }
     NumberDictionary* dictionary = NumberDictionary::cast(backing_store);
     int entry = dictionary->FindEntry(key);
     if (entry != NumberDictionary::kNotFound) {
       Object* result = dictionary->DeleteProperty(entry, mode);
       if (result == heap->true_value()) {
         MaybeObject* maybe_elements = dictionary->Shrink(key);
         FixedArray* new_elements = NULL;
         if (!maybe_elements->To(&new_elements)) {
           return maybe_elements;
         }
         if (is_arguments) {
           FixedArray::cast(obj->elements())->set(1, new_elements);
         } else {
           obj->set_elements(new_elements);
         }
       }
       if (mode == JSObject::STRICT_DELETION &&
           result == heap->false_value()) {
         // In strict mode, attempting to delete a non-configurable property
         // throws an exception.
         HandleScope scope(isolate);
         Handle<Object> holder(obj);
         Handle<Object> name = isolate->factory()->NewNumberFromUint(key);
         Handle<Object> args[2] = { name, holder };
         Handle<Object> error =
             isolate->factory()->NewTypeError("strict_delete_property",
                                              HandleVector(args, 2));
         return isolate->Throw(*error);
       }
     }
     return heap->true_value();
   }

  protected:
   friend class ElementsAccessorBase<DictionaryElementsAccessor,
                                     NumberDictionary>;

   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) {
     return DeleteCommon(obj, key, mode);
   }

   static MaybeObject* Get(NumberDictionary* backing_store,
                           uint32_t key,
                           JSObject* obj,
                           Object* receiver) {
     int entry = backing_store->FindEntry(key);
     if (entry != NumberDictionary::kNotFound) {
       Object* element = backing_store->ValueAt(entry);
       PropertyDetails details = backing_store->DetailsAt(entry);
       if (details.type() == CALLBACKS) {
         return obj->GetElementWithCallback(receiver,
                                            element,
                                            key,
                                            obj);
       } else {
         return element;
       }
     }
     return obj->GetHeap()->the_hole_value();
   }

   static uint32_t GetKeyForIndex(NumberDictionary* dict,
                                  uint32_t index) {
     Object* key = dict->KeyAt(index);
     return Smi::cast(key)->value();
   }
 };


 class NonStrictArgumentsElementsAccessor
     : public ElementsAccessorBase<NonStrictArgumentsElementsAccessor,
                                   FixedArray> {
  protected:
   friend class ElementsAccessorBase<NonStrictArgumentsElementsAccessor,
                                     FixedArray>;

   static MaybeObject* Get(FixedArray* parameter_map,
                           uint32_t key,
                           JSObject* obj,
                           Object* receiver) {
     Object* probe = GetParameterMapArg(parameter_map, key);
     if (!probe->IsTheHole()) {
       Context* context = Context::cast(parameter_map->get(0));
       int context_index = Smi::cast(probe)->value();
       ASSERT(!context->get(context_index)->IsTheHole());
       return context->get(context_index);
     } 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);
     }
   }

   virtual MaybeObject* Delete(JSObject* obj,
                               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 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));
   }

   static uint32_t GetKeyForIndex(FixedArray* dict,
                                  uint32_t index) {
     return index;
   }

   static bool HasElementAtIndex(FixedArray* parameter_map,
                                 uint32_t index,
                                 JSObject* holder,
                                 Object* receiver) {
     Object* probe = GetParameterMapArg(parameter_map, index);
     if (!probe->IsTheHole()) {
       return true;
     } else {
       FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
       ElementsAccessor* accessor = ElementsAccessor::ForArray(arguments);
       return !accessor->Get(arguments, index, holder, receiver)->IsTheHole();
     }
   }

  private:
   static Object* GetParameterMapArg(FixedArray* parameter_map,
                                     uint32_t key) {
     uint32_t length = parameter_map->length();
     return key < (length - 2 )
         ? parameter_map->get(key + 2)
         : parameter_map->GetHeap()->the_hole_value();
   }
 };


 ElementsAccessor* ElementsAccessor::ForArray(FixedArrayBase* array) {
   switch (array->map()->instance_type()) {
     case FIXED_ARRAY_TYPE:
       if (array->IsDictionary()) {
         return elements_accessors_[JSObject::DICTIONARY_ELEMENTS];
       } else {
         return elements_accessors_[JSObject::FAST_ELEMENTS];
       }
     case EXTERNAL_BYTE_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_BYTE_ELEMENTS];
     case EXTERNAL_UNSIGNED_BYTE_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_BYTE_ELEMENTS];
     case EXTERNAL_SHORT_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_SHORT_ELEMENTS];
     case EXTERNAL_UNSIGNED_SHORT_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_SHORT_ELEMENTS];
     case EXTERNAL_INT_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_INT_ELEMENTS];
     case EXTERNAL_UNSIGNED_INT_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_INT_ELEMENTS];
     case EXTERNAL_FLOAT_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_FLOAT_ELEMENTS];
     case EXTERNAL_DOUBLE_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_DOUBLE_ELEMENTS];
     case EXTERNAL_PIXEL_ARRAY_TYPE:
       return elements_accessors_[JSObject::EXTERNAL_PIXEL_ELEMENTS];
     default:
       UNREACHABLE();
       return NULL;
   }
 }


 void ElementsAccessor::InitializeOncePerProcess() {
   static struct ConcreteElementsAccessors {
     FastElementsAccessor 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;
     ExternalDoubleElementsAccessor double_elements_handler;
     PixelElementsAccessor pixel_elements_handler;
   } element_accessors;

   static ElementsAccessor* accessor_array[] = {
     &element_accessors.fast_elements_handler,
     &element_accessors.fast_double_elements_handler,
     &element_accessors.dictionary_elements_handler,
     &element_accessors.non_strict_arguments_elements_handler,
     &element_accessors.byte_elements_handler,
     &element_accessors.unsigned_byte_elements_handler,
     &element_accessors.short_elements_handler,
     &element_accessors.unsigned_short_elements_handler,
     &element_accessors.int_elements_handler,
     &element_accessors.unsigned_int_elements_handler,
     &element_accessors.float_elements_handler,
     &element_accessors.double_elements_handler,
     &element_accessors.pixel_elements_handler
   };

   elements_accessors_ = accessor_array;
 }


 } }  // namespace v8::internal
	// 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
	// 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.

	#include "v8.h"

	#include "objects.h"
	#include "elements.h"
	#include "utils.h"

	namespace v8 {
	namespace internal {


	ElementsAccessor** ElementsAccessor::elements_accessors_;


	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;
	}


	// 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> {
	// ...
	// }
	//
	// This is an example of the Curiously Recurring Template Pattern (see
	// http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern). We use
	// CRTP to guarantee aggressive compile time optimizations (i.e. inlining and
	// specialization of SomeElementsAccessor methods).
	template <typename ElementsAccessorSubclass, typename BackingStoreClass>
	class ElementsAccessorBase : public ElementsAccessor {
	protected:
	ElementsAccessorBase() { }
	virtual MaybeObject* Get(FixedArrayBase* backing_store,
	uint32_t key,
	JSObject* obj,
	Object* receiver) {
	return ElementsAccessorSubclass::Get(
	BackingStoreClass::cast(backing_store), key, obj, receiver);
	}

	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* 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
	if (FLAG_enable_slow_asserts) {
	for (int i = 0; i < len0; i++) {
	ASSERT(!to->get(i)->IsTheHole());
	}
	}
	#endif
	BackingStoreClass* backing_store = BackingStoreClass::cast(from);
	uint32_t len1 = ElementsAccessorSubclass::GetCapacity(backing_store);

	// Optimize if 'other' is empty.
	// We cannot optimize if 'this' is empty, as other may have holes.
	if (len1 == 0) return to;

	// Compute how many elements are not in other.
	int extra = 0;
	for (uint32_t y = 0; y < len1; y++) {
	if (ElementsAccessorSubclass::HasElementAtIndex(backing_store,
	y,
	holder,
	receiver)) {
	uint32_t key =
	ElementsAccessorSubclass::GetKeyForIndex(backing_store, y);
	MaybeObject* maybe_value =
	ElementsAccessorSubclass::Get(backing_store, key, holder, receiver);
	Object* value;
	if (!maybe_value->ToObject(&value)) return maybe_value;
	ASSERT(!value->IsTheHole());
	if (!HasKey(to, value)) {
	extra++;
	}
	}
	}

	if (extra == 0) return to;

	// Allocate the result
	FixedArray* result;
	MaybeObject* maybe_obj =
	backing_store->GetHeap()->AllocateFixedArray(len0 + extra);
	if (!maybe_obj->To<FixedArray>(&result)) return maybe_obj;

	// Fill in the content
	{
	AssertNoAllocation no_gc;
	WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
	for (int i = 0; i < len0; i++) {
	Object* e = to->get(i);
	ASSERT(e->IsString() \|\| e->IsNumber());
	result->set(i, e, mode);
	}
	}
	// Fill in the extra values.
	int index = 0;
	for (uint32_t y = 0; y < len1; y++) {
	if (ElementsAccessorSubclass::HasElementAtIndex(backing_store,
	y,
	holder,
	receiver)) {
	uint32_t key =
	ElementsAccessorSubclass::GetKeyForIndex(backing_store, y);
	MaybeObject* maybe_value =
	ElementsAccessorSubclass::Get(backing_store, key, holder, receiver);
	Object* value;
	if (!maybe_value->ToObject(&value)) return maybe_value;
	if (!value->IsTheHole() && !HasKey(to, value)) {
	result->set(len0 + index, value);
	index++;
	}
	}
	}
	ASSERT(extra == index);
	return result;
	}

	protected:
	static uint32_t GetCapacity(BackingStoreClass* backing_store) {
	return backing_store->length();
	}

	virtual uint32_t GetCapacity(FixedArrayBase* backing_store) {
	return ElementsAccessorSubclass::GetCapacity(
	BackingStoreClass::cast(backing_store));
	}

	static bool HasElementAtIndex(BackingStoreClass* backing_store,
	uint32_t index,
	JSObject* holder,
	Object* receiver) {
	uint32_t key =
	ElementsAccessorSubclass::GetKeyForIndex(backing_store, index);
	MaybeObject* element = ElementsAccessorSubclass::Get(backing_store,
	key,
	holder,
	receiver);
	return !element->IsTheHole();
	}

	virtual bool HasElementAtIndex(FixedArrayBase* backing_store,
	uint32_t index,
	JSObject* holder,
	Object* receiver) {
	return ElementsAccessorSubclass::HasElementAtIndex(
	BackingStoreClass::cast(backing_store), index, holder, receiver);
	}

	static uint32_t GetKeyForIndex(BackingStoreClass* backing_store,
	uint32_t index) {
	return index;
	}

	virtual uint32_t GetKeyForIndex(FixedArrayBase* backing_store,
	uint32_t index) {
	return ElementsAccessorSubclass::GetKeyForIndex(
	BackingStoreClass::cast(backing_store), index);
	}

	private:
	DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase);
	};


	class FastElementsAccessor
	: public ElementsAccessorBase<FastElementsAccessor, FixedArray> {
	public:
	static MaybeObject* DeleteCommon(JSObject* obj,
	uint32_t key) {
	ASSERT(obj->HasFastElements() \|\| 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));
	} else {
	Object* writable;
	MaybeObject* maybe = obj->EnsureWritableFastElements();
	if (!maybe->ToObject(&writable)) return maybe;
	backing_store = FixedArray::cast(writable);
	}
	uint32_t length = static_cast<uint32_t>(
	obj->IsJSArray()
	? Smi::cast(JSArray::cast(obj)->length())->value()
	: backing_store->length());
	if (key < length) {
	backing_store->set_the_hole(key);
	// If an old space backing store is larger than a certain size and
	// has too few used values, normalize it.
	// To avoid doing the check on every delete we require at least
	// one adjacent hole to the value being deleted.
	Object* hole = heap->the_hole_value();
	const int kMinLengthForSparsenessCheck = 64;
	if (backing_store->length() >= kMinLengthForSparsenessCheck &&
	!heap->InNewSpace(backing_store) &&
	((key > 0 && backing_store->get(key - 1) == hole) \|\|
	(key + 1 < length && backing_store->get(key + 1) == hole))) {
	int num_used = 0;
	for (int i = 0; i < backing_store->length(); ++i) {
	if (backing_store->get(i) != hole) ++num_used;
	// Bail out early if more than 1/4 is used.
	if (4 * num_used > backing_store->length()) break;
	}
	if (4 * num_used <= backing_store->length()) {
	MaybeObject* result = obj->NormalizeElements();
	if (result->IsFailure()) return result;
	}
	}
	}
	return heap->true_value();
	}

	protected:
	virtual MaybeObject* Delete(JSObject* obj,
	uint32_t key,
	JSReceiver::DeleteMode mode) {
	return DeleteCommon(obj, key);
	}
	};


	class FastDoubleElementsAccessor
	: public ElementsAccessorBase<FastDoubleElementsAccessor,
	FixedDoubleArray> {
	protected:
	friend class ElementsAccessorBase<FastDoubleElementsAccessor,
	FixedDoubleArray>;

	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);
	}
	return obj->GetHeap()->true_value();
	}

	static bool HasElementAtIndex(FixedDoubleArray* backing_store,
	uint32_t index,
	JSObject* holder,
	Object* receiver) {
	return !backing_store->is_the_hole(index);
	}
	};


	// Super class for all external element arrays.
	template<typename ExternalElementsAccessorSubclass,
	typename ExternalArray>
	class ExternalElementsAccessor
	: public ElementsAccessorBase<ExternalElementsAccessorSubclass,
	ExternalArray> {
	protected:
	friend class ElementsAccessorBase<ExternalElementsAccessorSubclass,
	ExternalArray>;

	static MaybeObject* Get(ExternalArray* backing_store,
	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();
	}
	}

	virtual MaybeObject* Delete(JSObject* obj,
	uint32_t key,
	JSReceiver::DeleteMode mode) {
	// External arrays always ignore deletes.
	return obj->GetHeap()->true_value();
	}
	};


	class ExternalByteElementsAccessor
	: public ExternalElementsAccessor<ExternalByteElementsAccessor,
	ExternalByteArray> {
	};


	class ExternalUnsignedByteElementsAccessor
	: public ExternalElementsAccessor<ExternalUnsignedByteElementsAccessor,
	ExternalUnsignedByteArray> {
	};


	class ExternalShortElementsAccessor
	: public ExternalElementsAccessor<ExternalShortElementsAccessor,
	ExternalShortArray> {
	};


	class ExternalUnsignedShortElementsAccessor
	: public ExternalElementsAccessor<ExternalUnsignedShortElementsAccessor,
	ExternalUnsignedShortArray> {
	};


	class ExternalIntElementsAccessor
	: public ExternalElementsAccessor<ExternalIntElementsAccessor,
	ExternalIntArray> {
	};


	class ExternalUnsignedIntElementsAccessor
	: public ExternalElementsAccessor<ExternalUnsignedIntElementsAccessor,
	ExternalUnsignedIntArray> {
	};


	class ExternalFloatElementsAccessor
	: public ExternalElementsAccessor<ExternalFloatElementsAccessor,
	ExternalFloatArray> {
	};


	class ExternalDoubleElementsAccessor
	: public ExternalElementsAccessor<ExternalDoubleElementsAccessor,
	ExternalDoubleArray> {
	};


	class PixelElementsAccessor
	: public ExternalElementsAccessor<PixelElementsAccessor,
	ExternalPixelArray> {
	};


	class DictionaryElementsAccessor
	: public ElementsAccessorBase<DictionaryElementsAccessor,
	NumberDictionary> {
	public:
	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() == JSObject::NON_STRICT_ARGUMENTS_ELEMENTS);
	if (is_arguments) {
	backing_store = FixedArray::cast(backing_store->get(1));
	}
	NumberDictionary* dictionary = NumberDictionary::cast(backing_store);
	int entry = dictionary->FindEntry(key);
	if (entry != NumberDictionary::kNotFound) {
	Object* result = dictionary->DeleteProperty(entry, mode);
	if (result == heap->true_value()) {
	MaybeObject* maybe_elements = dictionary->Shrink(key);
	FixedArray* new_elements = NULL;
	if (!maybe_elements->To(&new_elements)) {
	return maybe_elements;
	}
	if (is_arguments) {
	FixedArray::cast(obj->elements())->set(1, new_elements);
	} else {
	obj->set_elements(new_elements);
	}
	}
	if (mode == JSObject::STRICT_DELETION &&
	result == heap->false_value()) {
	// In strict mode, attempting to delete a non-configurable property
	// throws an exception.
	HandleScope scope(isolate);
	Handle<Object> holder(obj);
	Handle<Object> name = isolate->factory()->NewNumberFromUint(key);
	Handle<Object> args[2] = { name, holder };
	Handle<Object> error =
	isolate->factory()->NewTypeError("strict_delete_property",
	HandleVector(args, 2));
	return isolate->Throw(*error);
	}
	}
	return heap->true_value();
	}

	protected:
	friend class ElementsAccessorBase<DictionaryElementsAccessor,
	NumberDictionary>;

	virtual MaybeObject* Delete(JSObject* obj,
	uint32_t key,
	JSReceiver::DeleteMode mode) {
	return DeleteCommon(obj, key, mode);
	}

	static MaybeObject* Get(NumberDictionary* backing_store,
	uint32_t key,
	JSObject* obj,
	Object* receiver) {
	int entry = backing_store->FindEntry(key);
	if (entry != NumberDictionary::kNotFound) {
	Object* element = backing_store->ValueAt(entry);
	PropertyDetails details = backing_store->DetailsAt(entry);
	if (details.type() == CALLBACKS) {
	return obj->GetElementWithCallback(receiver,
	element,
	key,
	obj);
	} else {
	return element;
	}
	}
	return obj->GetHeap()->the_hole_value();
	}

	static uint32_t GetKeyForIndex(NumberDictionary* dict,
	uint32_t index) {
	Object* key = dict->KeyAt(index);
	return Smi::cast(key)->value();
	}
	};


	class NonStrictArgumentsElementsAccessor
	: public ElementsAccessorBase<NonStrictArgumentsElementsAccessor,
	FixedArray> {
	protected:
	friend class ElementsAccessorBase<NonStrictArgumentsElementsAccessor,
	FixedArray>;

	static MaybeObject* Get(FixedArray* parameter_map,
	uint32_t key,
	JSObject* obj,
	Object* receiver) {
	Object* probe = GetParameterMapArg(parameter_map, key);
	if (!probe->IsTheHole()) {
	Context* context = Context::cast(parameter_map->get(0));
	int context_index = Smi::cast(probe)->value();
	ASSERT(!context->get(context_index)->IsTheHole());
	return context->get(context_index);
	} 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);
	}
	}

	virtual MaybeObject* Delete(JSObject* obj,
	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 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));
	}

	static uint32_t GetKeyForIndex(FixedArray* dict,
	uint32_t index) {
	return index;
	}

	static bool HasElementAtIndex(FixedArray* parameter_map,
	uint32_t index,
	JSObject* holder,
	Object* receiver) {
	Object* probe = GetParameterMapArg(parameter_map, index);
	if (!probe->IsTheHole()) {
	return true;
	} else {
	FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
	ElementsAccessor* accessor = ElementsAccessor::ForArray(arguments);
	return !accessor->Get(arguments, index, holder, receiver)->IsTheHole();
	}
	}

	private:
	static Object* GetParameterMapArg(FixedArray* parameter_map,
	uint32_t key) {
	uint32_t length = parameter_map->length();
	return key < (length - 2 )
	? parameter_map->get(key + 2)
	: parameter_map->GetHeap()->the_hole_value();
	}
	};


	ElementsAccessor* ElementsAccessor::ForArray(FixedArrayBase* array) {
	switch (array->map()->instance_type()) {
	case FIXED_ARRAY_TYPE:
	if (array->IsDictionary()) {
	return elements_accessors_[JSObject::DICTIONARY_ELEMENTS];
	} else {
	return elements_accessors_[JSObject::FAST_ELEMENTS];
	}
	case EXTERNAL_BYTE_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_BYTE_ELEMENTS];
	case EXTERNAL_UNSIGNED_BYTE_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_BYTE_ELEMENTS];
	case EXTERNAL_SHORT_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_SHORT_ELEMENTS];
	case EXTERNAL_UNSIGNED_SHORT_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_SHORT_ELEMENTS];
	case EXTERNAL_INT_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_INT_ELEMENTS];
	case EXTERNAL_UNSIGNED_INT_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_INT_ELEMENTS];
	case EXTERNAL_FLOAT_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_FLOAT_ELEMENTS];
	case EXTERNAL_DOUBLE_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_DOUBLE_ELEMENTS];
	case EXTERNAL_PIXEL_ARRAY_TYPE:
	return elements_accessors_[JSObject::EXTERNAL_PIXEL_ELEMENTS];
	default:
	UNREACHABLE();
	return NULL;
	}
	}


	void ElementsAccessor::InitializeOncePerProcess() {
	static struct ConcreteElementsAccessors {
	FastElementsAccessor 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;
	ExternalDoubleElementsAccessor double_elements_handler;
	PixelElementsAccessor pixel_elements_handler;
	} element_accessors;

	static ElementsAccessor* accessor_array[] = {
	&element_accessors.fast_elements_handler,
	&element_accessors.fast_double_elements_handler,
	&element_accessors.dictionary_elements_handler,
	&element_accessors.non_strict_arguments_elements_handler,
	&element_accessors.byte_elements_handler,
	&element_accessors.unsigned_byte_elements_handler,
	&element_accessors.short_elements_handler,
	&element_accessors.unsigned_short_elements_handler,
	&element_accessors.int_elements_handler,
	&element_accessors.unsigned_int_elements_handler,
	&element_accessors.float_elements_handler,
	&element_accessors.double_elements_handler,
	&element_accessors.pixel_elements_handler
	};

	elements_accessors_ = accessor_array;
	}


	} } // namespace v8::internal