xref: /external/chromium_org/v8/src/objects.cc

// Copyright 2013 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 "accessors.h"
#include "api.h"
#include "arguments.h"
#include "bootstrapper.h"
#include "codegen.h"
#include "debug.h"
#include "deoptimizer.h"
#include "date.h"
#include "elements.h"
#include "execution.h"
#include "full-codegen.h"
#include "hydrogen.h"
#include "isolate-inl.h"
#include "objects-inl.h"
#include "objects-visiting.h"
#include "objects-visiting-inl.h"
#include "macro-assembler.h"
#include "mark-compact.h"
#include "safepoint-table.h"
#include "string-stream.h"
#include "utils.h"

#ifdef ENABLE_DISASSEMBLER
#include "disasm.h"
#include "disassembler.h"
#endif

namespace v8 {
namespace internal {


MUST_USE_RESULT static MaybeObject* CreateJSValue(JSFunction* constructor,
                                                  Object* value) {
  Object* result;
  { MaybeObject* maybe_result =
        constructor->GetHeap()->AllocateJSObject(constructor);
    if (!maybe_result->ToObject(&result)) return maybe_result;
  }
  JSValue::cast(result)->set_value(value);
  return result;
}


MaybeObject* Object::ToObject(Context* native_context) {
  if (IsNumber()) {
    return CreateJSValue(native_context->number_function(), this);
  } else if (IsBoolean()) {
    return CreateJSValue(native_context->boolean_function(), this);
  } else if (IsString()) {
    return CreateJSValue(native_context->string_function(), this);
  }
  ASSERT(IsJSObject());
  return this;
}


MaybeObject* Object::ToObject() {
  if (IsJSReceiver()) {
    return this;
  } else if (IsNumber()) {
    Isolate* isolate = Isolate::Current();
    Context* native_context = isolate->context()->native_context();
    return CreateJSValue(native_context->number_function(), this);
  } else if (IsBoolean()) {
    Isolate* isolate = HeapObject::cast(this)->GetIsolate();
    Context* native_context = isolate->context()->native_context();
    return CreateJSValue(native_context->boolean_function(), this);
  } else if (IsString()) {
    Isolate* isolate = HeapObject::cast(this)->GetIsolate();
    Context* native_context = isolate->context()->native_context();
    return CreateJSValue(native_context->string_function(), this);
  } else if (IsSymbol()) {
    Isolate* isolate = HeapObject::cast(this)->GetIsolate();
    Context* native_context = isolate->context()->native_context();
    return CreateJSValue(native_context->symbol_function(), this);
  }

  // Throw a type error.
  return Failure::InternalError();
}


bool Object::BooleanValue() {
  if (IsBoolean()) return IsTrue();
  if (IsSmi()) return Smi::cast(this)->value() != 0;
  if (IsUndefined() || IsNull()) return false;
  if (IsUndetectableObject()) return false;   // Undetectable object is false.
  if (IsString()) return String::cast(this)->length() != 0;
  if (IsHeapNumber()) return HeapNumber::cast(this)->HeapNumberBooleanValue();
  return true;
}


void Object::Lookup(Name* name, LookupResult* result) {
  Object* holder = NULL;
  if (IsJSReceiver()) {
    holder = this;
  } else {
    Context* native_context = result->isolate()->context()->native_context();
    if (IsNumber()) {
      holder = native_context->number_function()->instance_prototype();
    } else if (IsString()) {
      holder = native_context->string_function()->instance_prototype();
    } else if (IsSymbol()) {
      holder = native_context->symbol_function()->instance_prototype();
    } else if (IsBoolean()) {
      holder = native_context->boolean_function()->instance_prototype();
    } else {
      Isolate::Current()->PushStackTraceAndDie(
          0xDEAD0000, this, JSReceiver::cast(this)->map(), 0xDEAD0001);
    }
  }
  ASSERT(holder != NULL);  // Cannot handle null or undefined.
  JSReceiver::cast(holder)->Lookup(name, result);
}


MaybeObject* Object::GetPropertyWithReceiver(Object* receiver,
                                             Name* name,
                                             PropertyAttributes* attributes) {
  LookupResult result(name->GetIsolate());
  Lookup(name, &result);
  MaybeObject* value = GetProperty(receiver, &result, name, attributes);
  ASSERT(*attributes <= ABSENT);
  return value;
}


bool Object::ToInt32(int32_t* value) {
  if (IsSmi()) {
    *value = Smi::cast(this)->value();
    return true;
  }
  if (IsHeapNumber()) {
    double num = HeapNumber::cast(this)->value();
    if (FastI2D(FastD2I(num)) == num) {
      *value = FastD2I(num);
      return true;
    }
  }
  return false;
}


bool Object::ToUint32(uint32_t* value) {
  if (IsSmi()) {
    int num = Smi::cast(this)->value();
    if (num >= 0) {
      *value = static_cast<uint32_t>(num);
      return true;
    }
  }
  if (IsHeapNumber()) {
    double num = HeapNumber::cast(this)->value();
    if (num >= 0 && FastUI2D(FastD2UI(num)) == num) {
      *value = FastD2UI(num);
      return true;
    }
  }
  return false;
}


template<typename To>
static inline To* CheckedCast(void *from) {
  uintptr_t temp = reinterpret_cast<uintptr_t>(from);
  ASSERT(temp % sizeof(To) == 0);
  return reinterpret_cast<To*>(temp);
}


static MaybeObject* PerformCompare(const BitmaskCompareDescriptor& descriptor,
                                   char* ptr,
                                   Heap* heap) {
  uint32_t bitmask = descriptor.bitmask;
  uint32_t compare_value = descriptor.compare_value;
  uint32_t value;
  switch (descriptor.size) {
    case 1:
      value = static_cast<uint32_t>(*CheckedCast<uint8_t>(ptr));
      compare_value &= 0xff;
      bitmask &= 0xff;
      break;
    case 2:
      value = static_cast<uint32_t>(*CheckedCast<uint16_t>(ptr));
      compare_value &= 0xffff;
      bitmask &= 0xffff;
      break;
    case 4:
      value = *CheckedCast<uint32_t>(ptr);
      break;
    default:
      UNREACHABLE();
      return NULL;
  }
  return heap->ToBoolean((bitmask & value) == (bitmask & compare_value));
}


static MaybeObject* PerformCompare(const PointerCompareDescriptor& descriptor,
                                   char* ptr,
                                   Heap* heap) {
  uintptr_t compare_value =
      reinterpret_cast<uintptr_t>(descriptor.compare_value);
  uintptr_t value = *CheckedCast<uintptr_t>(ptr);
  return heap->ToBoolean(compare_value == value);
}


static MaybeObject* GetPrimitiveValue(
    const PrimitiveValueDescriptor& descriptor,
    char* ptr,
    Heap* heap) {
  int32_t int32_value = 0;
  switch (descriptor.data_type) {
    case kDescriptorInt8Type:
      int32_value = *CheckedCast<int8_t>(ptr);
      break;
    case kDescriptorUint8Type:
      int32_value = *CheckedCast<uint8_t>(ptr);
      break;
    case kDescriptorInt16Type:
      int32_value = *CheckedCast<int16_t>(ptr);
      break;
    case kDescriptorUint16Type:
      int32_value = *CheckedCast<uint16_t>(ptr);
      break;
    case kDescriptorInt32Type:
      int32_value = *CheckedCast<int32_t>(ptr);
      break;
    case kDescriptorUint32Type: {
      uint32_t value = *CheckedCast<uint32_t>(ptr);
      return heap->NumberFromUint32(value);
    }
    case kDescriptorBoolType: {
      uint8_t byte = *CheckedCast<uint8_t>(ptr);
      return heap->ToBoolean(byte & (0x1 << descriptor.bool_offset));
    }
    case kDescriptorFloatType: {
      float value = *CheckedCast<float>(ptr);
      return heap->NumberFromDouble(value);
    }
    case kDescriptorDoubleType: {
      double value = *CheckedCast<double>(ptr);
      return heap->NumberFromDouble(value);
    }
  }
  return heap->NumberFromInt32(int32_value);
}


static MaybeObject* GetDeclaredAccessorProperty(Object* receiver,
                                                DeclaredAccessorInfo* info,
                                                Isolate* isolate) {
  char* current = reinterpret_cast<char*>(receiver);
  DeclaredAccessorDescriptorIterator iterator(info->descriptor());
  while (true) {
    const DeclaredAccessorDescriptorData* data = iterator.Next();
    switch (data->type) {
      case kDescriptorReturnObject: {
        ASSERT(iterator.Complete());
        current = *CheckedCast<char*>(current);
        return *CheckedCast<Object*>(current);
      }
      case kDescriptorPointerDereference:
        ASSERT(!iterator.Complete());
        current = *reinterpret_cast<char**>(current);
        break;
      case kDescriptorPointerShift:
        ASSERT(!iterator.Complete());
        current += data->pointer_shift_descriptor.byte_offset;
        break;
      case kDescriptorObjectDereference: {
        ASSERT(!iterator.Complete());
        Object* object = CheckedCast<Object>(current);
        int field = data->object_dereference_descriptor.internal_field;
        Object* smi = JSObject::cast(object)->GetInternalField(field);
        ASSERT(smi->IsSmi());
        current = reinterpret_cast<char*>(smi);
        break;
      }
      case kDescriptorBitmaskCompare:
        ASSERT(iterator.Complete());
        return PerformCompare(data->bitmask_compare_descriptor,
                              current,
                              isolate->heap());
      case kDescriptorPointerCompare:
        ASSERT(iterator.Complete());
        return PerformCompare(data->pointer_compare_descriptor,
                              current,
                              isolate->heap());
      case kDescriptorPrimitiveValue:
        ASSERT(iterator.Complete());
        return GetPrimitiveValue(data->primitive_value_descriptor,
                                 current,
                                 isolate->heap());
    }
  }
  UNREACHABLE();
  return NULL;
}


MaybeObject* JSObject::GetPropertyWithCallback(Object* receiver,
                                               Object* structure,
                                               Name* name) {
  Isolate* isolate = name->GetIsolate();
  // To accommodate both the old and the new api we switch on the
  // data structure used to store the callbacks.  Eventually foreign
  // callbacks should be phased out.
  if (structure->IsForeign()) {
    AccessorDescriptor* callback =
        reinterpret_cast<AccessorDescriptor*>(
            Foreign::cast(structure)->foreign_address());
    MaybeObject* value = (callback->getter)(receiver, callback->data);
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    return value;
  }

  // api style callbacks.
  if (structure->IsAccessorInfo()) {
    if (!AccessorInfo::cast(structure)->IsCompatibleReceiver(receiver)) {
      Handle<Object> name_handle(name, isolate);
      Handle<Object> receiver_handle(receiver, isolate);
      Handle<Object> args[2] = { name_handle, receiver_handle };
      Handle<Object> error =
          isolate->factory()->NewTypeError("incompatible_method_receiver",
                                           HandleVector(args,
                                                        ARRAY_SIZE(args)));
      return isolate->Throw(*error);
    }
    // TODO(rossberg): Handling symbols in the API requires changing the API,
    // so we do not support it for now.
    if (name->IsSymbol()) return isolate->heap()->undefined_value();
    if (structure->IsDeclaredAccessorInfo()) {
      return GetDeclaredAccessorProperty(receiver,
                                         DeclaredAccessorInfo::cast(structure),
                                         isolate);
    }
    ExecutableAccessorInfo* data = ExecutableAccessorInfo::cast(structure);
    Object* fun_obj = data->getter();
    v8::AccessorGetter call_fun = v8::ToCData<v8::AccessorGetter>(fun_obj);
    if (call_fun == NULL) return isolate->heap()->undefined_value();
    HandleScope scope(isolate);
    JSObject* self = JSObject::cast(receiver);
    Handle<String> key(String::cast(name));
    LOG(isolate, ApiNamedPropertyAccess("load", self, name));
    PropertyCallbackArguments args(isolate, data->data(), self, this);
    v8::Handle<v8::Value> result =
        args.Call(call_fun, v8::Utils::ToLocal(key));
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    if (result.IsEmpty()) {
      return isolate->heap()->undefined_value();
    }
    Object* return_value = *v8::Utils::OpenHandle(*result);
    return_value->VerifyApiCallResultType();
    return return_value;
  }

  // __defineGetter__ callback
  if (structure->IsAccessorPair()) {
    Object* getter = AccessorPair::cast(structure)->getter();
    if (getter->IsSpecFunction()) {
      // TODO(rossberg): nicer would be to cast to some JSCallable here...
      return GetPropertyWithDefinedGetter(receiver, JSReceiver::cast(getter));
    }
    // Getter is not a function.
    return isolate->heap()->undefined_value();
  }

  UNREACHABLE();
  return NULL;
}


MaybeObject* JSProxy::GetPropertyWithHandler(Object* receiver_raw,
                                             Name* name_raw) {
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<Object> receiver(receiver_raw, isolate);
  Handle<Object> name(name_raw, isolate);

  // TODO(rossberg): adjust once there is a story for symbols vs proxies.
  if (name->IsSymbol()) return isolate->heap()->undefined_value();

  Handle<Object> args[] = { receiver, name };
  Handle<Object> result = CallTrap(
    "get", isolate->derived_get_trap(), ARRAY_SIZE(args), args);
  if (isolate->has_pending_exception()) return Failure::Exception();

  return *result;
}


Handle<Object> Object::GetProperty(Handle<Object> object, Handle<Name> name) {
  // TODO(rossberg): The index test should not be here but in the GetProperty
  // method (or somewhere else entirely). Needs more global clean-up.
  uint32_t index;
  if (name->AsArrayIndex(&index))
    return GetElement(object, index);
  Isolate* isolate = object->IsHeapObject()
      ? Handle<HeapObject>::cast(object)->GetIsolate()
      : Isolate::Current();
  CALL_HEAP_FUNCTION(isolate, object->GetProperty(*name), Object);
}


Handle<Object> Object::GetElement(Handle<Object> object, uint32_t index) {
  Isolate* isolate = object->IsHeapObject()
      ? Handle<HeapObject>::cast(object)->GetIsolate()
      : Isolate::Current();
  CALL_HEAP_FUNCTION(isolate, object->GetElement(index), Object);
}


MaybeObject* JSProxy::GetElementWithHandler(Object* receiver,
                                            uint32_t index) {
  String* name;
  MaybeObject* maybe = GetHeap()->Uint32ToString(index);
  if (!maybe->To<String>(&name)) return maybe;
  return GetPropertyWithHandler(receiver, name);
}


MaybeObject* JSProxy::SetElementWithHandler(JSReceiver* receiver,
                                            uint32_t index,
                                            Object* value,
                                            StrictModeFlag strict_mode) {
  String* name;
  MaybeObject* maybe = GetHeap()->Uint32ToString(index);
  if (!maybe->To<String>(&name)) return maybe;
  return SetPropertyWithHandler(receiver, name, value, NONE, strict_mode);
}


bool JSProxy::HasElementWithHandler(uint32_t index) {
  String* name;
  MaybeObject* maybe = GetHeap()->Uint32ToString(index);
  if (!maybe->To<String>(&name)) return maybe;
  return HasPropertyWithHandler(name);
}


MaybeObject* Object::GetPropertyWithDefinedGetter(Object* receiver,
                                                  JSReceiver* getter) {
  Isolate* isolate = getter->GetIsolate();
  HandleScope scope(isolate);
  Handle<JSReceiver> fun(getter);
  Handle<Object> self(receiver, isolate);
#ifdef ENABLE_DEBUGGER_SUPPORT
  Debug* debug = isolate->debug();
  // Handle stepping into a getter if step into is active.
  // TODO(rossberg): should this apply to getters that are function proxies?
  if (debug->StepInActive() && fun->IsJSFunction()) {
    debug->HandleStepIn(
        Handle<JSFunction>::cast(fun), Handle<Object>::null(), 0, false);
  }
#endif

  bool has_pending_exception;
  Handle<Object> result =
      Execution::Call(fun, self, 0, NULL, &has_pending_exception, true);
  // Check for pending exception and return the result.
  if (has_pending_exception) return Failure::Exception();
  return *result;
}


// Only deal with CALLBACKS and INTERCEPTOR
MaybeObject* JSObject::GetPropertyWithFailedAccessCheck(
    Object* receiver,
    LookupResult* result,
    Name* name,
    PropertyAttributes* attributes) {
  if (result->IsProperty()) {
    switch (result->type()) {
      case CALLBACKS: {
        // Only allow API accessors.
        Object* obj = result->GetCallbackObject();
        if (obj->IsAccessorInfo()) {
          AccessorInfo* info = AccessorInfo::cast(obj);
          if (info->all_can_read()) {
            *attributes = result->GetAttributes();
            return result->holder()->GetPropertyWithCallback(
                receiver, result->GetCallbackObject(), name);
          }
        }
        break;
      }
      case NORMAL:
      case FIELD:
      case CONSTANT: {
        // Search ALL_CAN_READ accessors in prototype chain.
        LookupResult r(GetIsolate());
        result->holder()->LookupRealNamedPropertyInPrototypes(name, &r);
        if (r.IsProperty()) {
          return GetPropertyWithFailedAccessCheck(receiver,
                                                  &r,
                                                  name,
                                                  attributes);
        }
        break;
      }
      case INTERCEPTOR: {
        // If the object has an interceptor, try real named properties.
        // No access check in GetPropertyAttributeWithInterceptor.
        LookupResult r(GetIsolate());
        result->holder()->LookupRealNamedProperty(name, &r);
        if (r.IsProperty()) {
          return GetPropertyWithFailedAccessCheck(receiver,
                                                  &r,
                                                  name,
                                                  attributes);
        }
        break;
      }
      default:
        UNREACHABLE();
    }
  }

  // No accessible property found.
  *attributes = ABSENT;
  Heap* heap = name->GetHeap();
  Isolate* isolate = heap->isolate();
  isolate->ReportFailedAccessCheck(this, v8::ACCESS_GET);
  RETURN_IF_SCHEDULED_EXCEPTION(isolate);
  return heap->undefined_value();
}


PropertyAttributes JSObject::GetPropertyAttributeWithFailedAccessCheck(
    Object* receiver,
    LookupResult* result,
    Name* name,
    bool continue_search) {
  if (result->IsProperty()) {
    switch (result->type()) {
      case CALLBACKS: {
        // Only allow API accessors.
        Object* obj = result->GetCallbackObject();
        if (obj->IsAccessorInfo()) {
          AccessorInfo* info = AccessorInfo::cast(obj);
          if (info->all_can_read()) {
            return result->GetAttributes();
          }
        }
        break;
      }

      case NORMAL:
      case FIELD:
      case CONSTANT: {
        if (!continue_search) break;
        // Search ALL_CAN_READ accessors in prototype chain.
        LookupResult r(GetIsolate());
        result->holder()->LookupRealNamedPropertyInPrototypes(name, &r);
        if (r.IsProperty()) {
          return GetPropertyAttributeWithFailedAccessCheck(receiver,
                                                           &r,
                                                           name,
                                                           continue_search);
        }
        break;
      }

      case INTERCEPTOR: {
        // If the object has an interceptor, try real named properties.
        // No access check in GetPropertyAttributeWithInterceptor.
        LookupResult r(GetIsolate());
        if (continue_search) {
          result->holder()->LookupRealNamedProperty(name, &r);
        } else {
          result->holder()->LocalLookupRealNamedProperty(name, &r);
        }
        if (!r.IsFound()) break;
        return GetPropertyAttributeWithFailedAccessCheck(receiver,
                                                         &r,
                                                         name,
                                                         continue_search);
      }

      case HANDLER:
      case TRANSITION:
      case NONEXISTENT:
        UNREACHABLE();
    }
  }

  GetIsolate()->ReportFailedAccessCheck(this, v8::ACCESS_HAS);
  return ABSENT;
}


Object* JSObject::GetNormalizedProperty(LookupResult* result) {
  ASSERT(!HasFastProperties());
  Object* value = property_dictionary()->ValueAt(result->GetDictionaryEntry());
  if (IsGlobalObject()) {
    value = PropertyCell::cast(value)->value();
  }
  ASSERT(!value->IsPropertyCell() && !value->IsCell());
  return value;
}


Handle<Object> JSObject::SetNormalizedProperty(Handle<JSObject> object,
                                               LookupResult* result,
                                               Handle<Object> value) {
  CALL_HEAP_FUNCTION(object->GetIsolate(),
                     object->SetNormalizedProperty(result, *value),
                     Object);
}


MaybeObject* JSObject::SetNormalizedProperty(LookupResult* result,
                                             Object* value) {
  ASSERT(!HasFastProperties());
  if (IsGlobalObject()) {
    PropertyCell* cell = PropertyCell::cast(
        property_dictionary()->ValueAt(result->GetDictionaryEntry()));
    MaybeObject* maybe_type = cell->SetValueInferType(value);
    if (maybe_type->IsFailure()) return maybe_type;
  } else {
    property_dictionary()->ValueAtPut(result->GetDictionaryEntry(), value);
  }
  return value;
}


Handle<Object> JSObject::SetNormalizedProperty(Handle<JSObject> object,
                                               Handle<Name> key,
                                               Handle<Object> value,
                                               PropertyDetails details) {
  CALL_HEAP_FUNCTION(object->GetIsolate(),
                     object->SetNormalizedProperty(*key, *value, details),
                     Object);
}


MaybeObject* JSObject::SetNormalizedProperty(Name* name,
                                             Object* value,
                                             PropertyDetails details) {
  ASSERT(!HasFastProperties());
  int entry = property_dictionary()->FindEntry(name);
  if (entry == NameDictionary::kNotFound) {
    Object* store_value = value;
    if (IsGlobalObject()) {
      Heap* heap = name->GetHeap();
      MaybeObject* maybe_store_value = heap->AllocatePropertyCell(value);
      if (!maybe_store_value->ToObject(&store_value)) return maybe_store_value;
    }
    Object* dict;
    { MaybeObject* maybe_dict =
          property_dictionary()->Add(name, store_value, details);
      if (!maybe_dict->ToObject(&dict)) return maybe_dict;
    }
    set_properties(NameDictionary::cast(dict));
    return value;
  }

  PropertyDetails original_details = property_dictionary()->DetailsAt(entry);
  int enumeration_index;
  // Preserve the enumeration index unless the property was deleted.
  if (original_details.IsDeleted()) {
    enumeration_index = property_dictionary()->NextEnumerationIndex();
    property_dictionary()->SetNextEnumerationIndex(enumeration_index + 1);
  } else {
    enumeration_index = original_details.dictionary_index();
    ASSERT(enumeration_index > 0);
  }

  details = PropertyDetails(
      details.attributes(), details.type(), enumeration_index);

  if (IsGlobalObject()) {
    PropertyCell* cell =
        PropertyCell::cast(property_dictionary()->ValueAt(entry));
    MaybeObject* maybe_type = cell->SetValueInferType(value);
    if (maybe_type->IsFailure()) return maybe_type;
    // Please note we have to update the property details.
    property_dictionary()->DetailsAtPut(entry, details);
  } else {
    property_dictionary()->SetEntry(entry, name, value, details);
  }
  return value;
}


// TODO(mstarzinger): Temporary wrapper until target is handlified.
Handle<NameDictionary> NameDictionaryShrink(Handle<NameDictionary> dict,
                                            Handle<Name> name) {
  CALL_HEAP_FUNCTION(dict->GetIsolate(), dict->Shrink(*name), NameDictionary);
}


static void CellSetValueInferType(Handle<PropertyCell> cell,
                                  Handle<Object> value) {
  CALL_HEAP_FUNCTION_VOID(cell->GetIsolate(), cell->SetValueInferType(*value));
}


Handle<Object> JSObject::DeleteNormalizedProperty(Handle<JSObject> object,
                                                  Handle<Name> name,
                                                  DeleteMode mode) {
  ASSERT(!object->HasFastProperties());
  Isolate* isolate = object->GetIsolate();
  Handle<NameDictionary> dictionary(object->property_dictionary());
  int entry = dictionary->FindEntry(*name);
  if (entry != NameDictionary::kNotFound) {
    // If we have a global object set the cell to the hole.
    if (object->IsGlobalObject()) {
      PropertyDetails details = dictionary->DetailsAt(entry);
      if (details.IsDontDelete()) {
        if (mode != FORCE_DELETION) return isolate->factory()->false_value();
        // When forced to delete global properties, we have to make a
        // map change to invalidate any ICs that think they can load
        // from the DontDelete cell without checking if it contains
        // the hole value.
        Handle<Map> new_map = Map::CopyDropDescriptors(handle(object->map()));
        ASSERT(new_map->is_dictionary_map());
        object->set_map(*new_map);
      }
      Handle<PropertyCell> cell(PropertyCell::cast(dictionary->ValueAt(entry)));
      CellSetValueInferType(cell, isolate->factory()->the_hole_value());
      dictionary->DetailsAtPut(entry, details.AsDeleted());
    } else {
      Handle<Object> deleted(dictionary->DeleteProperty(entry, mode), isolate);
      if (*deleted == isolate->heap()->true_value()) {
        Handle<NameDictionary> new_properties =
            NameDictionaryShrink(dictionary, name);
        object->set_properties(*new_properties);
      }
      return deleted;
    }
  }
  return isolate->factory()->true_value();
}


bool JSObject::IsDirty() {
  Object* cons_obj = map()->constructor();
  if (!cons_obj->IsJSFunction())
    return true;
  JSFunction* fun = JSFunction::cast(cons_obj);
  if (!fun->shared()->IsApiFunction())
    return true;
  // If the object is fully fast case and has the same map it was
  // created with then no changes can have been made to it.
  return map() != fun->initial_map()
      || !HasFastObjectElements()
      || !HasFastProperties();
}


Handle<Object> Object::GetProperty(Handle<Object> object,
                                   Handle<Object> receiver,
                                   LookupResult* result,
                                   Handle<Name> key,
                                   PropertyAttributes* attributes) {
  Isolate* isolate = object->IsHeapObject()
      ? Handle<HeapObject>::cast(object)->GetIsolate()
      : Isolate::Current();
  CALL_HEAP_FUNCTION(
      isolate,
      object->GetProperty(*receiver, result, *key, attributes),
      Object);
}


MaybeObject* Object::GetPropertyOrFail(Handle<Object> object,
                                       Handle<Object> receiver,
                                       LookupResult* result,
                                       Handle<Name> key,
                                       PropertyAttributes* attributes) {
  Isolate* isolate = object->IsHeapObject()
      ? Handle<HeapObject>::cast(object)->GetIsolate()
      : Isolate::Current();
  CALL_HEAP_FUNCTION_PASS_EXCEPTION(
      isolate,
      object->GetProperty(*receiver, result, *key, attributes));
}


MaybeObject* Object::GetProperty(Object* receiver,
                                 LookupResult* result,
                                 Name* name,
                                 PropertyAttributes* attributes) {
  // Make sure that the top context does not change when doing
  // callbacks or interceptor calls.
  AssertNoContextChange ncc;
  Isolate* isolate = name->GetIsolate();
  Heap* heap = isolate->heap();

  // Traverse the prototype chain from the current object (this) to
  // the holder and check for access rights. This avoids traversing the
  // objects more than once in case of interceptors, because the
  // holder will always be the interceptor holder and the search may
  // only continue with a current object just after the interceptor
  // holder in the prototype chain.
  // Proxy handlers do not use the proxy's prototype, so we can skip this.
  if (!result->IsHandler()) {
    Object* last = result->IsProperty()
        ? result->holder()
        : Object::cast(heap->null_value());
    ASSERT(this != this->GetPrototype(isolate));
    for (Object* current = this;
         true;
         current = current->GetPrototype(isolate)) {
      if (current->IsAccessCheckNeeded()) {
        // Check if we're allowed to read from the current object. Note
        // that even though we may not actually end up loading the named
        // property from the current object, we still check that we have
        // access to it.
        JSObject* checked = JSObject::cast(current);
        if (!heap->isolate()->MayNamedAccess(checked, name, v8::ACCESS_GET)) {
          return checked->GetPropertyWithFailedAccessCheck(receiver,
                                                           result,
                                                           name,
                                                           attributes);
        }
      }
      // Stop traversing the chain once we reach the last object in the
      // chain; either the holder of the result or null in case of an
      // absent property.
      if (current == last) break;
    }
  }

  if (!result->IsProperty()) {
    *attributes = ABSENT;
    return heap->undefined_value();
  }
  *attributes = result->GetAttributes();
  Object* value;
  switch (result->type()) {
    case NORMAL:
      value = result->holder()->GetNormalizedProperty(result);
      ASSERT(!value->IsTheHole() || result->IsReadOnly());
      return value->IsTheHole() ? heap->undefined_value() : value;
    case FIELD: {
      MaybeObject* maybe_result = result->holder()->FastPropertyAt(
          result->representation(),
          result->GetFieldIndex().field_index());
      if (!maybe_result->To(&value)) return maybe_result;
      ASSERT(!value->IsTheHole() || result->IsReadOnly());
      return value->IsTheHole() ? heap->undefined_value() : value;
    }
    case CONSTANT:
      return result->GetConstant();
    case CALLBACKS:
      return result->holder()->GetPropertyWithCallback(
          receiver, result->GetCallbackObject(), name);
    case HANDLER:
      return result->proxy()->GetPropertyWithHandler(receiver, name);
    case INTERCEPTOR:
      return result->holder()->GetPropertyWithInterceptor(
          receiver, name, attributes);
    case TRANSITION:
    case NONEXISTENT:
      UNREACHABLE();
      break;
  }
  UNREACHABLE();
  return NULL;
}


MaybeObject* Object::GetElementWithReceiver(Object* receiver, uint32_t index) {
  Isolate* isolate = IsSmi()
      ? Isolate::Current()
      : HeapObject::cast(this)->GetIsolate();
  Heap* heap = isolate->heap();
  Object* holder = this;

  // Iterate up the prototype chain until an element is found or the null
  // prototype is encountered.
  for (holder = this;
       holder != heap->null_value();
       holder = holder->GetPrototype(isolate)) {
    if (!holder->IsJSObject()) {
      Context* native_context = isolate->context()->native_context();
      if (holder->IsNumber()) {
        holder = native_context->number_function()->instance_prototype();
      } else if (holder->IsString()) {
        holder = native_context->string_function()->instance_prototype();
      } else if (holder->IsSymbol()) {
        holder = native_context->symbol_function()->instance_prototype();
      } else if (holder->IsBoolean()) {
        holder = native_context->boolean_function()->instance_prototype();
      } else if (holder->IsJSProxy()) {
        return JSProxy::cast(holder)->GetElementWithHandler(receiver, index);
      } else {
        // Undefined and null have no indexed properties.
        ASSERT(holder->IsUndefined() || holder->IsNull());
        return heap->undefined_value();
      }
    }

    // Inline the case for JSObjects. Doing so significantly improves the
    // performance of fetching elements where checking the prototype chain is
    // necessary.
    JSObject* js_object = JSObject::cast(holder);

    // Check access rights if needed.
    if (js_object->IsAccessCheckNeeded()) {
      Isolate* isolate = heap->isolate();
      if (!isolate->MayIndexedAccess(js_object, index, v8::ACCESS_GET)) {
        isolate->ReportFailedAccessCheck(js_object, v8::ACCESS_GET);
        RETURN_IF_SCHEDULED_EXCEPTION(isolate);
        return heap->undefined_value();
      }
    }

    if (js_object->HasIndexedInterceptor()) {
      return js_object->GetElementWithInterceptor(receiver, index);
    }

    if (js_object->elements() != heap->empty_fixed_array()) {
      MaybeObject* result = js_object->GetElementsAccessor()->Get(
          receiver, js_object, index);
      if (result != heap->the_hole_value()) return result;
    }
  }

  return heap->undefined_value();
}


Object* Object::GetPrototype(Isolate* isolate) {
  if (IsSmi()) {
    Context* context = isolate->context()->native_context();
    return context->number_function()->instance_prototype();
  }

  HeapObject* heap_object = HeapObject::cast(this);

  // The object is either a number, a string, a boolean,
  // a real JS object, or a Harmony proxy.
  if (heap_object->IsJSReceiver()) {
    return heap_object->map()->prototype();
  }
  Context* context = isolate->context()->native_context();

  if (heap_object->IsHeapNumber()) {
    return context->number_function()->instance_prototype();
  }
  if (heap_object->IsString()) {
    return context->string_function()->instance_prototype();
  }
  if (heap_object->IsSymbol()) {
    return context->symbol_function()->instance_prototype();
  }
  if (heap_object->IsBoolean()) {
    return context->boolean_function()->instance_prototype();
  } else {
    return isolate->heap()->null_value();
  }
}


MaybeObject* Object::GetHash(CreationFlag flag) {
  // The object is either a number, a name, an odd-ball,
  // a real JS object, or a Harmony proxy.
  if (IsNumber()) {
    uint32_t hash = ComputeLongHash(double_to_uint64(Number()));
    return Smi::FromInt(hash & Smi::kMaxValue);
  }
  if (IsName()) {
    uint32_t hash = Name::cast(this)->Hash();
    return Smi::FromInt(hash);
  }
  if (IsOddball()) {
    uint32_t hash = Oddball::cast(this)->to_string()->Hash();
    return Smi::FromInt(hash);
  }
  if (IsJSReceiver()) {
    return JSReceiver::cast(this)->GetIdentityHash(flag);
  }

  UNREACHABLE();
  return Smi::FromInt(0);
}


bool Object::SameValue(Object* other) {
  if (other == this) return true;

  // The object is either a number, a name, an odd-ball,
  // a real JS object, or a Harmony proxy.
  if (IsNumber() && other->IsNumber()) {
    double this_value = Number();
    double other_value = other->Number();
    return (this_value == other_value) ||
        (std::isnan(this_value) && std::isnan(other_value));
  }
  if (IsString() && other->IsString()) {
    return String::cast(this)->Equals(String::cast(other));
  }
  return false;
}


void Object::ShortPrint(FILE* out) {
  HeapStringAllocator allocator;
  StringStream accumulator(&allocator);
  ShortPrint(&accumulator);
  accumulator.OutputToFile(out);
}


void Object::ShortPrint(StringStream* accumulator) {
  if (IsSmi()) {
    Smi::cast(this)->SmiPrint(accumulator);
  } else if (IsFailure()) {
    Failure::cast(this)->FailurePrint(accumulator);
  } else {
    HeapObject::cast(this)->HeapObjectShortPrint(accumulator);
  }
}


void Smi::SmiPrint(FILE* out) {
  PrintF(out, "%d", value());
}


void Smi::SmiPrint(StringStream* accumulator) {
  accumulator->Add("%d", value());
}


void Failure::FailurePrint(StringStream* accumulator) {
  accumulator->Add("Failure(%p)", reinterpret_cast<void*>(value()));
}


void Failure::FailurePrint(FILE* out) {
  PrintF(out, "Failure(%p)", reinterpret_cast<void*>(value()));
}


// Should a word be prefixed by 'a' or 'an' in order to read naturally in
// English?  Returns false for non-ASCII or words that don't start with
// a capital letter.  The a/an rule follows pronunciation in English.
// We don't use the BBC's overcorrect "an historic occasion" though if
// you speak a dialect you may well say "an 'istoric occasion".
static bool AnWord(String* str) {
  if (str->length() == 0) return false;  // A nothing.
  int c0 = str->Get(0);
  int c1 = str->length() > 1 ? str->Get(1) : 0;
  if (c0 == 'U') {
    if (c1 > 'Z') {
      return true;  // An Umpire, but a UTF8String, a U.
    }
  } else if (c0 == 'A' || c0 == 'E' || c0 == 'I' || c0 == 'O') {
    return true;    // An Ape, an ABCBook.
  } else if ((c1 == 0 || (c1 >= 'A' && c1 <= 'Z')) &&
           (c0 == 'F' || c0 == 'H' || c0 == 'M' || c0 == 'N' || c0 == 'R' ||
            c0 == 'S' || c0 == 'X')) {
    return true;    // An MP3File, an M.
  }
  return false;
}


MaybeObject* String::SlowTryFlatten(PretenureFlag pretenure) {
#ifdef DEBUG
  // Do not attempt to flatten in debug mode when allocation is not
  // allowed.  This is to avoid an assertion failure when allocating.
  // Flattening strings is the only case where we always allow
  // allocation because no GC is performed if the allocation fails.
  if (!AllowHeapAllocation::IsAllowed()) return this;
#endif

  Heap* heap = GetHeap();
  switch (StringShape(this).representation_tag()) {
    case kConsStringTag: {
      ConsString* cs = ConsString::cast(this);
      if (cs->second()->length() == 0) {
        return cs->first();
      }
      // There's little point in putting the flat string in new space if the
      // cons string is in old space.  It can never get GCed until there is
      // an old space GC.
      PretenureFlag tenure = heap->InNewSpace(this) ? pretenure : TENURED;
      int len = length();
      Object* object;
      String* result;
      if (IsOneByteRepresentation()) {
        { MaybeObject* maybe_object =
              heap->AllocateRawOneByteString(len, tenure);
          if (!maybe_object->ToObject(&object)) return maybe_object;
        }
        result = String::cast(object);
        String* first = cs->first();
        int first_length = first->length();
        uint8_t* dest = SeqOneByteString::cast(result)->GetChars();
        WriteToFlat(first, dest, 0, first_length);
        String* second = cs->second();
        WriteToFlat(second,
                    dest + first_length,
                    0,
                    len - first_length);
      } else {
        { MaybeObject* maybe_object =
              heap->AllocateRawTwoByteString(len, tenure);
          if (!maybe_object->ToObject(&object)) return maybe_object;
        }
        result = String::cast(object);
        uc16* dest = SeqTwoByteString::cast(result)->GetChars();
        String* first = cs->first();
        int first_length = first->length();
        WriteToFlat(first, dest, 0, first_length);
        String* second = cs->second();
        WriteToFlat(second,
                    dest + first_length,
                    0,
                    len - first_length);
      }
      cs->set_first(result);
      cs->set_second(heap->empty_string(), SKIP_WRITE_BARRIER);
      return result;
    }
    default:
      return this;
  }
}


bool String::MakeExternal(v8::String::ExternalStringResource* resource) {
  // Externalizing twice leaks the external resource, so it's
  // prohibited by the API.
  ASSERT(!this->IsExternalString());
#ifdef DEBUG
  if (FLAG_enable_slow_asserts) {
    // Assert that the resource and the string are equivalent.
    ASSERT(static_cast<size_t>(this->length()) == resource->length());
    ScopedVector<uc16> smart_chars(this->length());
    String::WriteToFlat(this, smart_chars.start(), 0, this->length());
    ASSERT(memcmp(smart_chars.start(),
                  resource->data(),
                  resource->length() * sizeof(smart_chars[0])) == 0);
  }
#endif  // DEBUG
  Heap* heap = GetHeap();
  int size = this->Size();  // Byte size of the original string.
  if (size < ExternalString::kShortSize) {
    return false;
  }
  bool is_ascii = this->IsOneByteRepresentation();
  bool is_internalized = this->IsInternalizedString();

  // Morph the object to an external string by adjusting the map and
  // reinitializing the fields.
  if (size >= ExternalString::kSize) {
    this->set_map_no_write_barrier(
        is_internalized
            ? (is_ascii
                   ? heap->external_internalized_string_with_one_byte_data_map()
                   : heap->external_internalized_string_map())
            : (is_ascii
                   ? heap->external_string_with_one_byte_data_map()
                   : heap->external_string_map()));
  } else {
    this->set_map_no_write_barrier(
        is_internalized
          ? (is_ascii
               ? heap->
                   short_external_internalized_string_with_one_byte_data_map()
               : heap->short_external_internalized_string_map())
          : (is_ascii
                 ? heap->short_external_string_with_one_byte_data_map()
                 : heap->short_external_string_map()));
  }
  ExternalTwoByteString* self = ExternalTwoByteString::cast(this);
  self->set_resource(resource);
  if (is_internalized) self->Hash();  // Force regeneration of the hash value.

  // Fill the remainder of the string with dead wood.
  int new_size = this->Size();  // Byte size of the external String object.
  heap->CreateFillerObjectAt(this->address() + new_size, size - new_size);
  if (Marking::IsBlack(Marking::MarkBitFrom(this))) {
    MemoryChunk::IncrementLiveBytesFromMutator(this->address(),
                                               new_size - size);
  }
  return true;
}


bool String::MakeExternal(v8::String::ExternalAsciiStringResource* resource) {
#ifdef DEBUG
  if (FLAG_enable_slow_asserts) {
    // Assert that the resource and the string are equivalent.
    ASSERT(static_cast<size_t>(this->length()) == resource->length());
    if (this->IsTwoByteRepresentation()) {
      ScopedVector<uint16_t> smart_chars(this->length());
      String::WriteToFlat(this, smart_chars.start(), 0, this->length());
      ASSERT(String::IsOneByte(smart_chars.start(), this->length()));
    }
    ScopedVector<char> smart_chars(this->length());
    String::WriteToFlat(this, smart_chars.start(), 0, this->length());
    ASSERT(memcmp(smart_chars.start(),
                  resource->data(),
                  resource->length() * sizeof(smart_chars[0])) == 0);
  }
#endif  // DEBUG
  Heap* heap = GetHeap();
  int size = this->Size();  // Byte size of the original string.
  if (size < ExternalString::kShortSize) {
    return false;
  }
  bool is_internalized = this->IsInternalizedString();

  // Morph the object to an external string by adjusting the map and
  // reinitializing the fields.  Use short version if space is limited.
  if (size >= ExternalString::kSize) {
    this->set_map_no_write_barrier(
        is_internalized ? heap->external_ascii_internalized_string_map()
                        : heap->external_ascii_string_map());
  } else {
    this->set_map_no_write_barrier(
        is_internalized ? heap->short_external_ascii_internalized_string_map()
                        : heap->short_external_ascii_string_map());
  }
  ExternalAsciiString* self = ExternalAsciiString::cast(this);
  self->set_resource(resource);
  if (is_internalized) self->Hash();  // Force regeneration of the hash value.

  // Fill the remainder of the string with dead wood.
  int new_size = this->Size();  // Byte size of the external String object.
  heap->CreateFillerObjectAt(this->address() + new_size, size - new_size);
  if (Marking::IsBlack(Marking::MarkBitFrom(this))) {
    MemoryChunk::IncrementLiveBytesFromMutator(this->address(),
                                               new_size - size);
  }
  return true;
}


void String::StringShortPrint(StringStream* accumulator) {
  int len = length();
  if (len > kMaxShortPrintLength) {
    accumulator->Add("<Very long string[%u]>", len);
    return;
  }

  if (!LooksValid()) {
    accumulator->Add("<Invalid String>");
    return;
  }

  ConsStringIteratorOp op;
  StringCharacterStream stream(this, &op);

  bool truncated = false;
  if (len > kMaxShortPrintLength) {
    len = kMaxShortPrintLength;
    truncated = true;
  }
  bool ascii = true;
  for (int i = 0; i < len; i++) {
    uint16_t c = stream.GetNext();

    if (c < 32 || c >= 127) {
      ascii = false;
    }
  }
  stream.Reset(this);
  if (ascii) {
    accumulator->Add("<String[%u]: ", length());
    for (int i = 0; i < len; i++) {
      accumulator->Put(static_cast<char>(stream.GetNext()));
    }
    accumulator->Put('>');
  } else {
    // Backslash indicates that the string contains control
    // characters and that backslashes are therefore escaped.
    accumulator->Add("<String[%u]\\: ", length());
    for (int i = 0; i < len; i++) {
      uint16_t c = stream.GetNext();
      if (c == '\n') {
        accumulator->Add("\\n");
      } else if (c == '\r') {
        accumulator->Add("\\r");
      } else if (c == '\\') {
        accumulator->Add("\\\\");
      } else if (c < 32 || c > 126) {
        accumulator->Add("\\x%02x", c);
      } else {
        accumulator->Put(static_cast<char>(c));
      }
    }
    if (truncated) {
      accumulator->Put('.');
      accumulator->Put('.');
      accumulator->Put('.');
    }
    accumulator->Put('>');
  }
  return;
}


void JSObject::JSObjectShortPrint(StringStream* accumulator) {
  switch (map()->instance_type()) {
    case JS_ARRAY_TYPE: {
      double length = JSArray::cast(this)->length()->IsUndefined()
          ? 0
          : JSArray::cast(this)->length()->Number();
      accumulator->Add("<JS Array[%u]>", static_cast<uint32_t>(length));
      break;
    }
    case JS_WEAK_MAP_TYPE: {
      accumulator->Add("<JS WeakMap>");
      break;
    }
    case JS_WEAK_SET_TYPE: {
      accumulator->Add("<JS WeakSet>");
      break;
    }
    case JS_REGEXP_TYPE: {
      accumulator->Add("<JS RegExp>");
      break;
    }
    case JS_FUNCTION_TYPE: {
      JSFunction* function = JSFunction::cast(this);
      Object* fun_name = function->shared()->DebugName();
      bool printed = false;
      if (fun_name->IsString()) {
        String* str = String::cast(fun_name);
        if (str->length() > 0) {
          accumulator->Add("<JS Function ");
          accumulator->Put(str);
          printed = true;
        }
      }
      if (!printed) {
        accumulator->Add("<JS Function");
      }
      accumulator->Add(" (SharedFunctionInfo %p)",
                       reinterpret_cast<void*>(function->shared()));
      accumulator->Put('>');
      break;
    }
    case JS_GENERATOR_OBJECT_TYPE: {
      accumulator->Add("<JS Generator>");
      break;
    }
    case JS_MODULE_TYPE: {
      accumulator->Add("<JS Module>");
      break;
    }
    // All other JSObjects are rather similar to each other (JSObject,
    // JSGlobalProxy, JSGlobalObject, JSUndetectableObject, JSValue).
    default: {
      Map* map_of_this = map();
      Heap* heap = GetHeap();
      Object* constructor = map_of_this->constructor();
      bool printed = false;
      if (constructor->IsHeapObject() &&
          !heap->Contains(HeapObject::cast(constructor))) {
        accumulator->Add("!!!INVALID CONSTRUCTOR!!!");
      } else {
        bool global_object = IsJSGlobalProxy();
        if (constructor->IsJSFunction()) {
          if (!heap->Contains(JSFunction::cast(constructor)->shared())) {
            accumulator->Add("!!!INVALID SHARED ON CONSTRUCTOR!!!");
          } else {
            Object* constructor_name =
                JSFunction::cast(constructor)->shared()->name();
            if (constructor_name->IsString()) {
              String* str = String::cast(constructor_name);
              if (str->length() > 0) {
                bool vowel = AnWord(str);
                accumulator->Add("<%sa%s ",
                       global_object ? "Global Object: " : "",
                       vowel ? "n" : "");
                accumulator->Put(str);
                accumulator->Add(" with %smap %p",
                    map_of_this->is_deprecated() ? "deprecated " : "",
                    map_of_this);
                printed = true;
              }
            }
          }
        }
        if (!printed) {
          accumulator->Add("<JS %sObject", global_object ? "Global " : "");
        }
      }
      if (IsJSValue()) {
        accumulator->Add(" value = ");
        JSValue::cast(this)->value()->ShortPrint(accumulator);
      }
      accumulator->Put('>');
      break;
    }
  }
}


void JSObject::PrintElementsTransition(
    FILE* file, ElementsKind from_kind, FixedArrayBase* from_elements,
    ElementsKind to_kind, FixedArrayBase* to_elements) {
  if (from_kind != to_kind) {
    PrintF(file, "elements transition [");
    PrintElementsKind(file, from_kind);
    PrintF(file, " -> ");
    PrintElementsKind(file, to_kind);
    PrintF(file, "] in ");
    JavaScriptFrame::PrintTop(GetIsolate(), file, false, true);
    PrintF(file, " for ");
    ShortPrint(file);
    PrintF(file, " from ");
    from_elements->ShortPrint(file);
    PrintF(file, " to ");
    to_elements->ShortPrint(file);
    PrintF(file, "\n");
  }
}


void HeapObject::HeapObjectShortPrint(StringStream* accumulator) {
  Heap* heap = GetHeap();
  if (!heap->Contains(this)) {
    accumulator->Add("!!!INVALID POINTER!!!");
    return;
  }
  if (!heap->Contains(map())) {
    accumulator->Add("!!!INVALID MAP!!!");
    return;
  }

  accumulator->Add("%p ", this);

  if (IsString()) {
    String::cast(this)->StringShortPrint(accumulator);
    return;
  }
  if (IsJSObject()) {
    JSObject::cast(this)->JSObjectShortPrint(accumulator);
    return;
  }
  switch (map()->instance_type()) {
    case MAP_TYPE:
      accumulator->Add("<Map(elements=%u)>", Map::cast(this)->elements_kind());
      break;
    case FIXED_ARRAY_TYPE:
      accumulator->Add("<FixedArray[%u]>", FixedArray::cast(this)->length());
      break;
    case FIXED_DOUBLE_ARRAY_TYPE:
      accumulator->Add("<FixedDoubleArray[%u]>",
                       FixedDoubleArray::cast(this)->length());
      break;
    case BYTE_ARRAY_TYPE:
      accumulator->Add("<ByteArray[%u]>", ByteArray::cast(this)->length());
      break;
    case FREE_SPACE_TYPE:
      accumulator->Add("<FreeSpace[%u]>", FreeSpace::cast(this)->Size());
      break;
    case EXTERNAL_PIXEL_ARRAY_TYPE:
      accumulator->Add("<ExternalPixelArray[%u]>",
                       ExternalPixelArray::cast(this)->length());
      break;
    case EXTERNAL_BYTE_ARRAY_TYPE:
      accumulator->Add("<ExternalByteArray[%u]>",
                       ExternalByteArray::cast(this)->length());
      break;
    case EXTERNAL_UNSIGNED_BYTE_ARRAY_TYPE:
      accumulator->Add("<ExternalUnsignedByteArray[%u]>",
                       ExternalUnsignedByteArray::cast(this)->length());
      break;
    case EXTERNAL_SHORT_ARRAY_TYPE:
      accumulator->Add("<ExternalShortArray[%u]>",
                       ExternalShortArray::cast(this)->length());
      break;
    case EXTERNAL_UNSIGNED_SHORT_ARRAY_TYPE:
      accumulator->Add("<ExternalUnsignedShortArray[%u]>",
                       ExternalUnsignedShortArray::cast(this)->length());
      break;
    case EXTERNAL_INT_ARRAY_TYPE:
      accumulator->Add("<ExternalIntArray[%u]>",
                       ExternalIntArray::cast(this)->length());
      break;
    case EXTERNAL_UNSIGNED_INT_ARRAY_TYPE:
      accumulator->Add("<ExternalUnsignedIntArray[%u]>",
                       ExternalUnsignedIntArray::cast(this)->length());
      break;
    case EXTERNAL_FLOAT_ARRAY_TYPE:
      accumulator->Add("<ExternalFloatArray[%u]>",
                       ExternalFloatArray::cast(this)->length());
      break;
    case EXTERNAL_DOUBLE_ARRAY_TYPE:
      accumulator->Add("<ExternalDoubleArray[%u]>",
                       ExternalDoubleArray::cast(this)->length());
      break;
    case SHARED_FUNCTION_INFO_TYPE: {
      SharedFunctionInfo* shared = SharedFunctionInfo::cast(this);
      SmartArrayPointer<char> debug_name =
          shared->DebugName()->ToCString();
      if (debug_name[0] != 0) {
        accumulator->Add("<SharedFunctionInfo %s>", *debug_name);
      } else {
        accumulator->Add("<SharedFunctionInfo>");
      }
      break;
    }
    case JS_MESSAGE_OBJECT_TYPE:
      accumulator->Add("<JSMessageObject>");
      break;
#define MAKE_STRUCT_CASE(NAME, Name, name) \
  case NAME##_TYPE:                        \
    accumulator->Put('<');                 \
    accumulator->Add(#Name);               \
    accumulator->Put('>');                 \
    break;
  STRUCT_LIST(MAKE_STRUCT_CASE)
#undef MAKE_STRUCT_CASE
    case CODE_TYPE:
      accumulator->Add("<Code>");
      break;
    case ODDBALL_TYPE: {
      if (IsUndefined())
        accumulator->Add("<undefined>");
      else if (IsTheHole())
        accumulator->Add("<the hole>");
      else if (IsNull())
        accumulator->Add("<null>");
      else if (IsTrue())
        accumulator->Add("<true>");
      else if (IsFalse())
        accumulator->Add("<false>");
      else
        accumulator->Add("<Odd Oddball>");
      break;
    }
    case SYMBOL_TYPE: {
      Symbol* symbol = Symbol::cast(this);
      accumulator->Add("<Symbol: %d", symbol->Hash());
      if (!symbol->name()->IsUndefined()) {
        accumulator->Add(" ");
        String::cast(symbol->name())->StringShortPrint(accumulator);
      }
      accumulator->Add(">");
      break;
    }
    case HEAP_NUMBER_TYPE:
      accumulator->Add("<Number: ");
      HeapNumber::cast(this)->HeapNumberPrint(accumulator);
      accumulator->Put('>');
      break;
    case JS_PROXY_TYPE:
      accumulator->Add("<JSProxy>");
      break;
    case JS_FUNCTION_PROXY_TYPE:
      accumulator->Add("<JSFunctionProxy>");
      break;
    case FOREIGN_TYPE:
      accumulator->Add("<Foreign>");
      break;
    case CELL_TYPE:
      accumulator->Add("Cell for ");
      Cell::cast(this)->value()->ShortPrint(accumulator);
      break;
    case PROPERTY_CELL_TYPE:
      accumulator->Add("PropertyCell for ");
      PropertyCell::cast(this)->value()->ShortPrint(accumulator);
      break;
    default:
      accumulator->Add("<Other heap object (%d)>", map()->instance_type());
      break;
  }
}


void HeapObject::Iterate(ObjectVisitor* v) {
  // Handle header
  IteratePointer(v, kMapOffset);
  // Handle object body
  Map* m = map();
  IterateBody(m->instance_type(), SizeFromMap(m), v);
}


void HeapObject::IterateBody(InstanceType type, int object_size,
                             ObjectVisitor* v) {
  // Avoiding <Type>::cast(this) because it accesses the map pointer field.
  // During GC, the map pointer field is encoded.
  if (type < FIRST_NONSTRING_TYPE) {
    switch (type & kStringRepresentationMask) {
      case kSeqStringTag:
        break;
      case kConsStringTag:
        ConsString::BodyDescriptor::IterateBody(this, v);
        break;
      case kSlicedStringTag:
        SlicedString::BodyDescriptor::IterateBody(this, v);
        break;
      case kExternalStringTag:
        if ((type & kStringEncodingMask) == kOneByteStringTag) {
          reinterpret_cast<ExternalAsciiString*>(this)->
              ExternalAsciiStringIterateBody(v);
        } else {
          reinterpret_cast<ExternalTwoByteString*>(this)->
              ExternalTwoByteStringIterateBody(v);
        }
        break;
    }
    return;
  }

  switch (type) {
    case FIXED_ARRAY_TYPE:
      FixedArray::BodyDescriptor::IterateBody(this, object_size, v);
      break;
    case FIXED_DOUBLE_ARRAY_TYPE:
      break;
    case JS_OBJECT_TYPE:
    case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
    case JS_GENERATOR_OBJECT_TYPE:
    case JS_MODULE_TYPE:
    case JS_VALUE_TYPE:
    case JS_DATE_TYPE:
    case JS_ARRAY_TYPE:
    case JS_ARRAY_BUFFER_TYPE:
    case JS_TYPED_ARRAY_TYPE:
    case JS_DATA_VIEW_TYPE:
    case JS_SET_TYPE:
    case JS_MAP_TYPE:
    case JS_WEAK_MAP_TYPE:
    case JS_WEAK_SET_TYPE:
    case JS_REGEXP_TYPE:
    case JS_GLOBAL_PROXY_TYPE:
    case JS_GLOBAL_OBJECT_TYPE:
    case JS_BUILTINS_OBJECT_TYPE:
    case JS_MESSAGE_OBJECT_TYPE:
      JSObject::BodyDescriptor::IterateBody(this, object_size, v);
      break;
    case JS_FUNCTION_TYPE:
      reinterpret_cast<JSFunction*>(this)
          ->JSFunctionIterateBody(object_size, v);
      break;
    case ODDBALL_TYPE:
      Oddball::BodyDescriptor::IterateBody(this, v);
      break;
    case JS_PROXY_TYPE:
      JSProxy::BodyDescriptor::IterateBody(this, v);
      break;
    case JS_FUNCTION_PROXY_TYPE:
      JSFunctionProxy::BodyDescriptor::IterateBody(this, v);
      break;
    case FOREIGN_TYPE:
      reinterpret_cast<Foreign*>(this)->ForeignIterateBody(v);
      break;
    case MAP_TYPE:
      Map::BodyDescriptor::IterateBody(this, v);
      break;
    case CODE_TYPE:
      reinterpret_cast<Code*>(this)->CodeIterateBody(v);
      break;
    case CELL_TYPE:
      Cell::BodyDescriptor::IterateBody(this, v);
      break;
    case PROPERTY_CELL_TYPE:
      PropertyCell::BodyDescriptor::IterateBody(this, v);
      break;
    case SYMBOL_TYPE:
      Symbol::BodyDescriptor::IterateBody(this, v);
      break;
    case HEAP_NUMBER_TYPE:
    case FILLER_TYPE:
    case BYTE_ARRAY_TYPE:
    case FREE_SPACE_TYPE:
    case EXTERNAL_PIXEL_ARRAY_TYPE:
    case EXTERNAL_BYTE_ARRAY_TYPE:
    case EXTERNAL_UNSIGNED_BYTE_ARRAY_TYPE:
    case EXTERNAL_SHORT_ARRAY_TYPE:
    case EXTERNAL_UNSIGNED_SHORT_ARRAY_TYPE:
    case EXTERNAL_INT_ARRAY_TYPE:
    case EXTERNAL_UNSIGNED_INT_ARRAY_TYPE:
    case EXTERNAL_FLOAT_ARRAY_TYPE:
    case EXTERNAL_DOUBLE_ARRAY_TYPE:
      break;
    case SHARED_FUNCTION_INFO_TYPE: {
      SharedFunctionInfo::BodyDescriptor::IterateBody(this, v);
      break;
    }

#define MAKE_STRUCT_CASE(NAME, Name, name) \
        case NAME##_TYPE:
      STRUCT_LIST(MAKE_STRUCT_CASE)
#undef MAKE_STRUCT_CASE
      if (type == ALLOCATION_SITE_TYPE) {
        AllocationSite::BodyDescriptor::IterateBody(this, v);
      } else {
        StructBodyDescriptor::IterateBody(this, object_size, v);
      }
      break;
    default:
      PrintF("Unknown type: %d\n", type);
      UNREACHABLE();
  }
}


bool HeapNumber::HeapNumberBooleanValue() {
  // NaN, +0, and -0 should return the false object
#if __BYTE_ORDER == __LITTLE_ENDIAN
  union IeeeDoubleLittleEndianArchType u;
#elif __BYTE_ORDER == __BIG_ENDIAN
  union IeeeDoubleBigEndianArchType u;
#endif
  u.d = value();
  if (u.bits.exp == 2047) {
    // Detect NaN for IEEE double precision floating point.
    if ((u.bits.man_low | u.bits.man_high) != 0) return false;
  }
  if (u.bits.exp == 0) {
    // Detect +0, and -0 for IEEE double precision floating point.
    if ((u.bits.man_low | u.bits.man_high) == 0) return false;
  }
  return true;
}


void HeapNumber::HeapNumberPrint(FILE* out) {
  PrintF(out, "%.16g", Number());
}


void HeapNumber::HeapNumberPrint(StringStream* accumulator) {
  // The Windows version of vsnprintf can allocate when printing a %g string
  // into a buffer that may not be big enough.  We don't want random memory
  // allocation when producing post-crash stack traces, so we print into a
  // buffer that is plenty big enough for any floating point number, then
  // print that using vsnprintf (which may truncate but never allocate if
  // there is no more space in the buffer).
  EmbeddedVector<char, 100> buffer;
  OS::SNPrintF(buffer, "%.16g", Number());
  accumulator->Add("%s", buffer.start());
}


String* JSReceiver::class_name() {
  if (IsJSFunction() && IsJSFunctionProxy()) {
    return GetHeap()->function_class_string();
  }
  if (map()->constructor()->IsJSFunction()) {
    JSFunction* constructor = JSFunction::cast(map()->constructor());
    return String::cast(constructor->shared()->instance_class_name());
  }
  // If the constructor is not present, return "Object".
  return GetHeap()->Object_string();
}


String* JSReceiver::constructor_name() {
  if (map()->constructor()->IsJSFunction()) {
    JSFunction* constructor = JSFunction::cast(map()->constructor());
    String* name = String::cast(constructor->shared()->name());
    if (name->length() > 0) return name;
    String* inferred_name = constructor->shared()->inferred_name();
    if (inferred_name->length() > 0) return inferred_name;
    Object* proto = GetPrototype();
    if (proto->IsJSObject()) return JSObject::cast(proto)->constructor_name();
  }
  // TODO(rossberg): what about proxies?
  // If the constructor is not present, return "Object".
  return GetHeap()->Object_string();
}


MaybeObject* JSObject::AddFastPropertyUsingMap(Map* new_map,
                                               Name* name,
                                               Object* value,
                                               int field_index,
                                               Representation representation) {
  // This method is used to transition to a field. If we are transitioning to a
  // double field, allocate new storage.
  Object* storage;
  MaybeObject* maybe_storage =
      value->AllocateNewStorageFor(GetHeap(), representation);
  if (!maybe_storage->To(&storage)) return maybe_storage;

  if (map()->unused_property_fields() == 0) {
    int new_unused = new_map->unused_property_fields();
    FixedArray* values;
    MaybeObject* maybe_values =
        properties()->CopySize(properties()->length() + new_unused + 1);
    if (!maybe_values->To(&values)) return maybe_values;

    set_properties(values);
  }

  set_map(new_map);

  FastPropertyAtPut(field_index, storage);
  return value;
}


static bool IsIdentifier(UnicodeCache* cache, Name* name) {
  // Checks whether the buffer contains an identifier (no escape).
  if (!name->IsString()) return false;
  String* string = String::cast(name);
  if (string->length() == 0) return false;
  ConsStringIteratorOp op;
  StringCharacterStream stream(string, &op);
  if (!cache->IsIdentifierStart(stream.GetNext())) {
    return false;
  }
  while (stream.HasMore()) {
    if (!cache->IsIdentifierPart(stream.GetNext())) {
      return false;
    }
  }
  return true;
}


MaybeObject* JSObject::AddFastProperty(Name* name,
                                       Object* value,
                                       PropertyAttributes attributes,
                                       StoreFromKeyed store_mode,
                                       ValueType value_type) {
  ASSERT(!IsJSGlobalProxy());
  ASSERT(DescriptorArray::kNotFound ==
         map()->instance_descriptors()->Search(
             name, map()->NumberOfOwnDescriptors()));

  // Normalize the object if the name is an actual name (not the
  // hidden strings) and is not a real identifier.
  // Normalize the object if it will have too many fast properties.
  Isolate* isolate = GetHeap()->isolate();
  if ((!name->IsSymbol() && !IsIdentifier(isolate->unicode_cache(), name)
       && name != isolate->heap()->hidden_string()) ||
      (map()->unused_property_fields() == 0 &&
       TooManyFastProperties(properties()->length(), store_mode))) {
    Object* obj;
    MaybeObject* maybe_obj =
        NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
    if (!maybe_obj->ToObject(&obj)) return maybe_obj;

    return AddSlowProperty(name, value, attributes);
  }

  // Compute the new index for new field.
  int index = map()->NextFreePropertyIndex();

  // Allocate new instance descriptors with (name, index) added
  if (IsJSContextExtensionObject()) value_type = FORCE_TAGGED;
  Representation representation = value->OptimalRepresentation(value_type);

  FieldDescriptor new_field(name, index, attributes, representation);

  ASSERT(index < map()->inobject_properties() ||
         (index - map()->inobject_properties()) < properties()->length() ||
         map()->unused_property_fields() == 0);

  FixedArray* values = NULL;

  // TODO(verwaest): Merge with AddFastPropertyUsingMap.
  if (map()->unused_property_fields() == 0) {
    // Make room for the new value
    MaybeObject* maybe_values =
        properties()->CopySize(properties()->length() + kFieldsAdded);
    if (!maybe_values->To(&values)) return maybe_values;
  }

  TransitionFlag flag = INSERT_TRANSITION;

  Heap* heap = isolate->heap();

  Object* storage;
  MaybeObject* maybe_storage =
      value->AllocateNewStorageFor(heap, representation);
  if (!maybe_storage->To(&storage)) return maybe_storage;

  // Note that Map::CopyAddDescriptor has side-effects, the new map is already
  // inserted in the transition tree. No more allocations that might fail are
  // allowed after this point.
  Map* new_map;
  MaybeObject* maybe_new_map = map()->CopyAddDescriptor(&new_field, flag);
  if (!maybe_new_map->To(&new_map)) return maybe_new_map;

  if (map()->unused_property_fields() == 0) {
    ASSERT(values != NULL);
    set_properties(values);
    new_map->set_unused_property_fields(kFieldsAdded - 1);
  } else {
    new_map->set_unused_property_fields(map()->unused_property_fields() - 1);
  }

  set_map(new_map);

  FastPropertyAtPut(index, storage);
  return value;
}


MaybeObject* JSObject::AddConstantProperty(
    Name* name,
    Object* constant,
    PropertyAttributes attributes) {
  // Allocate new instance descriptors with (name, constant) added
  ConstantDescriptor d(name, constant, attributes);

  TransitionFlag flag =
      // Do not add transitions to  global objects.
      (IsGlobalObject() ||
      // Don't add transitions to special properties with non-trivial
      // attributes.
       attributes != NONE)
      ? OMIT_TRANSITION
      : INSERT_TRANSITION;

  Map* new_map;
  MaybeObject* maybe_new_map = map()->CopyAddDescriptor(&d, flag);
  if (!maybe_new_map->To(&new_map)) return maybe_new_map;

  set_map(new_map);
  return constant;
}


// Add property in slow mode
MaybeObject* JSObject::AddSlowProperty(Name* name,
                                       Object* value,
                                       PropertyAttributes attributes) {
  ASSERT(!HasFastProperties());
  NameDictionary* dict = property_dictionary();
  Object* store_value = value;
  if (IsGlobalObject()) {
    // In case name is an orphaned property reuse the cell.
    int entry = dict->FindEntry(name);
    if (entry != NameDictionary::kNotFound) {
      store_value = dict->ValueAt(entry);
      MaybeObject* maybe_type =
          PropertyCell::cast(store_value)->SetValueInferType(value);
      if (maybe_type->IsFailure()) return maybe_type;
      // Assign an enumeration index to the property and update
      // SetNextEnumerationIndex.
      int index = dict->NextEnumerationIndex();
      PropertyDetails details = PropertyDetails(attributes, NORMAL, index);
      dict->SetNextEnumerationIndex(index + 1);
      dict->SetEntry(entry, name, store_value, details);
      return value;
    }
    Heap* heap = GetHeap();
    { MaybeObject* maybe_store_value =
          heap->AllocatePropertyCell(value);
      if (!maybe_store_value->ToObject(&store_value)) return maybe_store_value;
    }
    MaybeObject* maybe_type =
        PropertyCell::cast(store_value)->SetValueInferType(value);
    if (maybe_type->IsFailure()) return maybe_type;
  }
  PropertyDetails details = PropertyDetails(attributes, NORMAL, 0);
  Object* result;
  { MaybeObject* maybe_result = dict->Add(name, store_value, details);
    if (!maybe_result->ToObject(&result)) return maybe_result;
  }
  if (dict != result) set_properties(NameDictionary::cast(result));
  return value;
}


MaybeObject* JSObject::AddProperty(Name* name,
                                   Object* value,
                                   PropertyAttributes attributes,
                                   StrictModeFlag strict_mode,
                                   JSReceiver::StoreFromKeyed store_mode,
                                   ExtensibilityCheck extensibility_check,
                                   ValueType value_type,
                                   StoreMode mode) {
  ASSERT(!IsJSGlobalProxy());
  Map* map_of_this = map();
  Heap* heap = GetHeap();
  Isolate* isolate = heap->isolate();
  MaybeObject* result;
  if (extensibility_check == PERFORM_EXTENSIBILITY_CHECK &&
      !map_of_this->is_extensible()) {
    if (strict_mode == kNonStrictMode) {
      return value;
    } else {
      Handle<Object> args[1] = {Handle<Name>(name)};
      return isolate->Throw(
          *isolate->factory()->NewTypeError("object_not_extensible",
                                            HandleVector(args, 1)));
    }
  }

  if (HasFastProperties()) {
    // Ensure the descriptor array does not get too big.
    if (map_of_this->NumberOfOwnDescriptors() <
        DescriptorArray::kMaxNumberOfDescriptors) {
      // TODO(verwaest): Support other constants.
      // if (mode == ALLOW_AS_CONSTANT &&
      //     !value->IsTheHole() &&
      //     !value->IsConsString()) {
      if (value->IsJSFunction()) {
        result = AddConstantProperty(name, value, attributes);
      } else {
        result = AddFastProperty(
            name, value, attributes, store_mode, value_type);
      }
    } else {
      // Normalize the object to prevent very large instance descriptors.
      // This eliminates unwanted N^2 allocation and lookup behavior.
      Object* obj;
      MaybeObject* maybe = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
      if (!maybe->To(&obj)) return maybe;
      result = AddSlowProperty(name, value, attributes);
    }
  } else {
    result = AddSlowProperty(name, value, attributes);
  }

  Handle<Object> hresult;
  if (!result->ToHandle(&hresult, isolate)) return result;

  if (FLAG_harmony_observation && map()->is_observed()) {
    EnqueueChangeRecord(handle(this, isolate),
                        "new",
                        handle(name, isolate),
                        handle(heap->the_hole_value(), isolate));
  }

  return *hresult;
}


void JSObject::EnqueueChangeRecord(Handle<JSObject> object,
                                   const char* type_str,
                                   Handle<Name> name,
                                   Handle<Object> old_value) {
  Isolate* isolate = object->GetIsolate();
  HandleScope scope(isolate);
  Handle<String> type = isolate->factory()->InternalizeUtf8String(type_str);
  if (object->IsJSGlobalObject()) {
    object = handle(JSGlobalObject::cast(*object)->global_receiver(), isolate);
  }
  Handle<Object> args[] = { type, object, name, old_value };
  bool threw;
  Execution::Call(Handle<JSFunction>(isolate->observers_notify_change()),
                  isolate->factory()->undefined_value(),
                  old_value->IsTheHole() ? 3 : 4, args,
                  &threw);
  ASSERT(!threw);
}


void JSObject::DeliverChangeRecords(Isolate* isolate) {
  ASSERT(isolate->observer_delivery_pending());
  bool threw = false;
  Execution::Call(
      isolate->observers_deliver_changes(),
      isolate->factory()->undefined_value(),
      0,
      NULL,
      &threw);
  ASSERT(!threw);
  isolate->set_observer_delivery_pending(false);
}


MaybeObject* JSObject::SetPropertyPostInterceptor(
    Name* name,
    Object* value,
    PropertyAttributes attributes,
    StrictModeFlag strict_mode,
    ExtensibilityCheck extensibility_check,
    StoreMode mode) {
  // Check local property, ignore interceptor.
  LookupResult result(GetIsolate());
  LocalLookupRealNamedProperty(name, &result);
  if (!result.IsFound()) map()->LookupTransition(this, name, &result);
  if (result.IsFound()) {
    // An existing property or a map transition was found. Use set property to
    // handle all these cases.
    return SetProperty(&result, name, value, attributes, strict_mode);
  }
  bool done = false;
  MaybeObject* result_object;
  result_object =
      SetPropertyViaPrototypes(name, value, attributes, strict_mode, &done);
  if (done) return result_object;
  // Add a new real property.
  return AddProperty(name, value, attributes, strict_mode,
                     MAY_BE_STORE_FROM_KEYED, extensibility_check,
                     OPTIMAL_REPRESENTATION, mode);
}


MaybeObject* JSObject::ReplaceSlowProperty(Name* name,
                                           Object* value,
                                           PropertyAttributes attributes) {
  NameDictionary* dictionary = property_dictionary();
  int old_index = dictionary->FindEntry(name);
  int new_enumeration_index = 0;  // 0 means "Use the next available index."
  if (old_index != -1) {
    // All calls to ReplaceSlowProperty have had all transitions removed.
    new_enumeration_index = dictionary->DetailsAt(old_index).dictionary_index();
  }

  PropertyDetails new_details(attributes, NORMAL, new_enumeration_index);
  return SetNormalizedProperty(name, value, new_details);
}


MaybeObject* JSObject::ConvertTransitionToMapTransition(
    int transition_index,
    Name* name,
    Object* new_value,
    PropertyAttributes attributes) {
  Map* old_map = map();
  Map* old_target = old_map->GetTransition(transition_index);
  Object* result;

  MaybeObject* maybe_result = ConvertDescriptorToField(
      name, new_value, attributes, OMIT_TRANSITION_KEEP_REPRESENTATIONS);
  if (!maybe_result->To(&result)) return maybe_result;

  if (!HasFastProperties()) return result;

  // This method should only be used to convert existing transitions.
  Map* new_map = map();

  // TODO(verwaest): From here on we lose existing map transitions, causing
  // invalid back pointers. This will change once we can store multiple
  // transitions with the same key.
  bool owned_descriptors = old_map->owns_descriptors();
  if (owned_descriptors ||
      old_target->instance_descriptors() == old_map->instance_descriptors()) {
    // Since the conversion above generated a new fast map with an additional
    // property which can be shared as well, install this descriptor pointer
    // along the entire chain of smaller maps.
    Map* map;
    DescriptorArray* new_descriptors = new_map->instance_descriptors();
    DescriptorArray* old_descriptors = old_map->instance_descriptors();
    for (Object* current = old_map;
         !current->IsUndefined();
         current = map->GetBackPointer()) {
      map = Map::cast(current);
      if (map->instance_descriptors() != old_descriptors) break;
      map->SetEnumLength(Map::kInvalidEnumCache);
      map->set_instance_descriptors(new_descriptors);
    }
    old_map->set_owns_descriptors(false);
  }

  old_target->DeprecateTransitionTree();

  old_map->SetTransition(transition_index, new_map);
  new_map->SetBackPointer(old_map);
  return result;
}


MaybeObject* JSObject::ConvertDescriptorToField(Name* name,
                                                Object* new_value,
                                                PropertyAttributes attributes,
                                                TransitionFlag flag) {
  if (map()->unused_property_fields() == 0 &&
      TooManyFastProperties(properties()->length(), MAY_BE_STORE_FROM_KEYED)) {
    Object* obj;
    MaybeObject* maybe_obj = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
    return ReplaceSlowProperty(name, new_value, attributes);
  }

  Representation representation = IsJSContextExtensionObject()
      ? Representation::Tagged() : new_value->OptimalRepresentation();
  int index = map()->NextFreePropertyIndex();
  FieldDescriptor new_field(name, index, attributes, representation);

  // Make a new map for the object.
  Map* new_map;
  MaybeObject* maybe_new_map = map()->CopyInsertDescriptor(&new_field, flag);
  if (!maybe_new_map->To(&new_map)) return maybe_new_map;

  // Make new properties array if necessary.
  FixedArray* new_properties = NULL;
  int new_unused_property_fields = map()->unused_property_fields() - 1;
  if (map()->unused_property_fields() == 0) {
    new_unused_property_fields = kFieldsAdded - 1;
    MaybeObject* maybe_new_properties =
        properties()->CopySize(properties()->length() + kFieldsAdded);
    if (!maybe_new_properties->To(&new_properties)) return maybe_new_properties;
  }

  Heap* heap = GetHeap();
  Object* storage;
  MaybeObject* maybe_storage =
      new_value->AllocateNewStorageFor(heap, representation);
  if (!maybe_storage->To(&storage)) return maybe_storage;

  // Update pointers to commit changes.
  // Object points to the new map.
  new_map->set_unused_property_fields(new_unused_property_fields);
  set_map(new_map);
  if (new_properties != NULL) {
    set_properties(new_properties);
  }
  FastPropertyAtPut(index, new_value);
  return new_value;
}


const char* Representation::Mnemonic() const {
  switch (kind_) {
    case kNone: return "v";
    case kTagged: return "t";
    case kSmi: return "s";
    case kDouble: return "d";
    case kInteger32: return "i";
    case kHeapObject: return "h";
    case kExternal: return "x";
    default:
      UNREACHABLE();
      return NULL;
  }
}


enum RightTrimMode { FROM_GC, FROM_MUTATOR };


static void ZapEndOfFixedArray(Address new_end, int to_trim) {
  // If we are doing a big trim in old space then we zap the space.
  Object** zap = reinterpret_cast<Object**>(new_end);
  zap++;  // Header of filler must be at least one word so skip that.
  for (int i = 1; i < to_trim; i++) {
    *zap++ = Smi::FromInt(0);
  }
}


template<RightTrimMode trim_mode>
static void RightTrimFixedArray(Heap* heap, FixedArray* elms, int to_trim) {
  ASSERT(elms->map() != HEAP->fixed_cow_array_map());
  // For now this trick is only applied to fixed arrays in new and paged space.
  ASSERT(!HEAP->lo_space()->Contains(elms));

  const int len = elms->length();

  ASSERT(to_trim < len);

  Address new_end = elms->address() + FixedArray::SizeFor(len - to_trim);

  if (trim_mode != FROM_GC || Heap::ShouldZapGarbage()) {
    ZapEndOfFixedArray(new_end, to_trim);
  }

  int size_delta = to_trim * kPointerSize;

  // Technically in new space this write might be omitted (except for
  // debug mode which iterates through the heap), but to play safer
  // we still do it.
  heap->CreateFillerObjectAt(new_end, size_delta);

  elms->set_length(len - to_trim);

  // Maintain marking consistency for IncrementalMarking.
  if (Marking::IsBlack(Marking::MarkBitFrom(elms))) {
    if (trim_mode == FROM_GC) {
      MemoryChunk::IncrementLiveBytesFromGC(elms->address(), -size_delta);
    } else {
      MemoryChunk::IncrementLiveBytesFromMutator(elms->address(), -size_delta);
    }
  }
}


bool Map::InstancesNeedRewriting(Map* target,
                                 int target_number_of_fields,
                                 int target_inobject,
                                 int target_unused) {
  // If fields were added (or removed), rewrite the instance.
  int number_of_fields = NumberOfFields();
  ASSERT(target_number_of_fields >= number_of_fields);
  if (target_number_of_fields != number_of_fields) return true;

  if (FLAG_track_double_fields) {
    // If smi descriptors were replaced by double descriptors, rewrite.
    DescriptorArray* old_desc = instance_descriptors();
    DescriptorArray* new_desc = target->instance_descriptors();
    int limit = NumberOfOwnDescriptors();
    for (int i = 0; i < limit; i++) {
      if (new_desc->GetDetails(i).representation().IsDouble() &&
          !old_desc->GetDetails(i).representation().IsDouble()) {
        return true;
      }
    }
  }

  // If no fields were added, and no inobject properties were removed, setting
  // the map is sufficient.
  if (target_inobject == inobject_properties()) return false;
  // In-object slack tracking may have reduced the object size of the new map.
  // In that case, succeed if all existing fields were inobject, and they still
  // fit within the new inobject size.
  ASSERT(target_inobject < inobject_properties());
  if (target_number_of_fields <= target_inobject) {
    ASSERT(target_number_of_fields + target_unused == target_inobject);
    return false;
  }
  // Otherwise, properties will need to be moved to the backing store.
  return true;
}


// To migrate an instance to a map:
// - First check whether the instance needs to be rewritten. If not, simply
//   change the map.
// - Otherwise, allocate a fixed array large enough to hold all fields, in
//   addition to unused space.
// - Copy all existing properties in, in the following order: backing store
//   properties, unused fields, inobject properties.
// - If all allocation succeeded, commit the state atomically:
//   * Copy inobject properties from the backing store back into the object.
//   * Trim the difference in instance size of the object. This also cleanly
//     frees inobject properties that moved to the backing store.
//   * If there are properties left in the backing store, trim of the space used
//     to temporarily store the inobject properties.
//   * If there are properties left in the backing store, install the backing
//     store.
MaybeObject* JSObject::MigrateToMap(Map* new_map) {
  Heap* heap = GetHeap();
  Map* old_map = map();
  int number_of_fields = new_map->NumberOfFields();
  int inobject = new_map->inobject_properties();
  int unused = new_map->unused_property_fields();

  // Nothing to do if no functions were converted to fields.
  if (!old_map->InstancesNeedRewriting(
          new_map, number_of_fields, inobject, unused)) {
    set_map(new_map);
    return this;
  }

  int total_size = number_of_fields + unused;
  int external = total_size - inobject;
  FixedArray* array;
  MaybeObject* maybe_array = heap->AllocateFixedArray(total_size);
  if (!maybe_array->To(&array)) return maybe_array;

  DescriptorArray* old_descriptors = old_map->instance_descriptors();
  DescriptorArray* new_descriptors = new_map->instance_descriptors();
  int descriptors = new_map->NumberOfOwnDescriptors();

  for (int i = 0; i < descriptors; i++) {
    PropertyDetails details = new_descriptors->GetDetails(i);
    if (details.type() != FIELD) continue;
    PropertyDetails old_details = old_descriptors->GetDetails(i);
    ASSERT(old_details.type() == CONSTANT ||
           old_details.type() == FIELD);
    Object* value = old_details.type() == CONSTANT
        ? old_descriptors->GetValue(i)
        : RawFastPropertyAt(old_descriptors->GetFieldIndex(i));
    if (FLAG_track_double_fields &&
        !old_details.representation().IsDouble() &&
        details.representation().IsDouble()) {
      if (old_details.representation().IsNone()) value = Smi::FromInt(0);
      // Objects must be allocated in the old object space, since the
      // overall number of HeapNumbers needed for the conversion might
      // exceed the capacity of new space, and we would fail repeatedly
      // trying to migrate the instance.
      MaybeObject* maybe_storage =
          value->AllocateNewStorageFor(heap, details.representation(), TENURED);
      if (!maybe_storage->To(&value)) return maybe_storage;
    }
    ASSERT(!(FLAG_track_double_fields &&
             details.representation().IsDouble() &&
             value->IsSmi()));
    int target_index = new_descriptors->GetFieldIndex(i) - inobject;
    if (target_index < 0) target_index += total_size;
    array->set(target_index, value);
  }

  // From here on we cannot fail anymore.

  // Copy (real) inobject properties. If necessary, stop at number_of_fields to
  // avoid overwriting |one_pointer_filler_map|.
  int limit = Min(inobject, number_of_fields);
  for (int i = 0; i < limit; i++) {
    FastPropertyAtPut(i, array->get(external + i));
  }

  // Create filler object past the new instance size.
  int new_instance_size = new_map->instance_size();
  int instance_size_delta = old_map->instance_size() - new_instance_size;
  ASSERT(instance_size_delta >= 0);
  Address address = this->address() + new_instance_size;
  heap->CreateFillerObjectAt(address, instance_size_delta);

  // If there are properties in the new backing store, trim it to the correct
  // size and install the backing store into the object.
  if (external > 0) {
    RightTrimFixedArray<FROM_MUTATOR>(heap, array, inobject);
    set_properties(array);
  }

  set_map(new_map);

  return this;
}


MaybeObject* JSObject::GeneralizeFieldRepresentation(
    int modify_index,
    Representation new_representation) {
  Map* new_map;
  MaybeObject* maybe_new_map =
      map()->GeneralizeRepresentation(modify_index, new_representation);
  if (!maybe_new_map->To(&new_map)) return maybe_new_map;
  if (map() == new_map) return this;

  return MigrateToMap(new_map);
}


int Map::NumberOfFields() {
  DescriptorArray* descriptors = instance_descriptors();
  int result = 0;
  for (int i = 0; i < NumberOfOwnDescriptors(); i++) {
    if (descriptors->GetDetails(i).type() == FIELD) result++;
  }
  return result;
}


MaybeObject* Map::CopyGeneralizeAllRepresentations() {
  Map* new_map;
  MaybeObject* maybe_map = this->Copy();
  if (!maybe_map->To(&new_map)) return maybe_map;

  new_map->instance_descriptors()->InitializeRepresentations(
      Representation::Tagged());
  if (FLAG_trace_generalization) {
    PrintF("failed generalization %p -> %p\n",
           static_cast<void*>(this), static_cast<void*>(new_map));
  }
  return new_map;
}


void Map::DeprecateTransitionTree() {
  if (!FLAG_track_fields) return;
  if (is_deprecated()) return;
  if (HasTransitionArray()) {
    TransitionArray* transitions = this->transitions();
    for (int i = 0; i < transitions->number_of_transitions(); i++) {
      transitions->GetTarget(i)->DeprecateTransitionTree();
    }
  }
  deprecate();
  dependent_code()->DeoptimizeDependentCodeGroup(
      GetIsolate(), DependentCode::kTransitionGroup);
  NotifyLeafMapLayoutChange();
}


// Invalidates a transition target at |key|, and installs |new_descriptors| over
// the current instance_descriptors to ensure proper sharing of descriptor
// arrays.
void Map::DeprecateTarget(Name* key, DescriptorArray* new_descriptors) {
  if (HasTransitionArray()) {
    TransitionArray* transitions = this->transitions();
    int transition = transitions->Search(key);
    if (transition != TransitionArray::kNotFound) {
      transitions->GetTarget(transition)->DeprecateTransitionTree();
    }
  }

  // Don't overwrite the empty descriptor array.
  if (NumberOfOwnDescriptors() == 0) return;

  DescriptorArray* to_replace = instance_descriptors();
  Map* current = this;
  while (current->instance_descriptors() == to_replace) {
    current->SetEnumLength(Map::kInvalidEnumCache);
    current->set_instance_descriptors(new_descriptors);
    Object* next = current->GetBackPointer();
    if (next->IsUndefined()) break;
    current = Map::cast(next);
  }

  set_owns_descriptors(false);
}


Map* Map::FindRootMap() {
  Map* result = this;
  while (true) {
    Object* back = result->GetBackPointer();
    if (back->IsUndefined()) return result;
    result = Map::cast(back);
  }
}


// Returns NULL if the updated map is incompatible.
Map* Map::FindUpdatedMap(int verbatim,
                         int length,
                         DescriptorArray* descriptors) {
  // This can only be called on roots of transition trees.
  ASSERT(GetBackPointer()->IsUndefined());

  Map* current = this;

  for (int i = verbatim; i < length; i++) {
    if (!current->HasTransitionArray()) break;
    Name* name = descriptors->GetKey(i);
    TransitionArray* transitions = current->transitions();
    int transition = transitions->Search(name);
    if (transition == TransitionArray::kNotFound) break;
    current = transitions->GetTarget(transition);
    PropertyDetails details = descriptors->GetDetails(i);
    PropertyDetails target_details =
        current->instance_descriptors()->GetDetails(i);
    if (details.attributes() != target_details.attributes()) return NULL;
    if (details.type() == CALLBACKS) {
      if (target_details.type() != CALLBACKS) return NULL;
      if (descriptors->GetValue(i) !=
              current->instance_descriptors()->GetValue(i)) {
        return NULL;
      }
    }
  }

  return current;
}


Map* Map::FindLastMatchMap(int verbatim,
                           int length,
                           DescriptorArray* descriptors) {
  // This can only be called on roots of transition trees.
  ASSERT(GetBackPointer()->IsUndefined());

  Map* current = this;

  for (int i = verbatim; i < length; i++) {
    if (!current->HasTransitionArray()) break;
    Name* name = descriptors->GetKey(i);
    TransitionArray* transitions = current->transitions();
    int transition = transitions->Search(name);
    if (transition == TransitionArray::kNotFound) break;

    Map* next = transitions->GetTarget(transition);
    DescriptorArray* next_descriptors = next->instance_descriptors();

    if (next_descriptors->GetValue(i) != descriptors->GetValue(i)) break;

    PropertyDetails details = descriptors->GetDetails(i);
    PropertyDetails next_details = next_descriptors->GetDetails(i);
    if (details.type() != next_details.type()) break;
    if (details.attributes() != next_details.attributes()) break;
    if (!details.representation().Equals(next_details.representation())) break;

    current = next;
  }
  return current;
}


// Generalize the representation of the descriptor at |modify_index|.
// This method rewrites the transition tree to reflect the new change. To avoid
// high degrees over polymorphism, and to stabilize quickly, on every rewrite
// the new type is deduced by merging the current type with any potential new
// (partial) version of the type in the transition tree.
// To do this, on each rewrite:
// - Search the root of the transition tree using FindRootMap.
// - Find |updated|, the newest matching version of this map using
//   FindUpdatedMap. This uses the keys in the own map's descriptor array to
//   walk the transition tree.
// - Merge/generalize the descriptor array of the current map and |updated|.
// - Generalize the |modify_index| descriptor using |new_representation|.
// - Walk the tree again starting from the root towards |updated|. Stop at
//   |split_map|, the first map who's descriptor array does not match the merged
//   descriptor array.
// - If |updated| == |split_map|, |updated| is in the expected state. Return it.
// - Otherwise, invalidate the outdated transition target from |updated|, and
//   replace its transition tree with a new branch for the updated descriptors.
MaybeObject* Map::GeneralizeRepresentation(int modify_index,
                                           Representation new_representation) {
  Map* old_map = this;
  DescriptorArray* old_descriptors = old_map->instance_descriptors();
  Representation old_representation =
      old_descriptors->GetDetails(modify_index).representation();

  // It's fine to transition from None to anything but double without any
  // modification to the object, because the default uninitialized value for
  // representation None can be overwritten by both smi and tagged values.
  // Doubles, however, would require a box allocation.
  if (old_representation.IsNone() &&
      !new_representation.IsNone() &&
      !new_representation.IsDouble()) {
    if (FLAG_trace_generalization) {
      PrintF("initializing representation %i: %p -> %s\n",
             modify_index,
             static_cast<void*>(this),
             new_representation.Mnemonic());
    }
    old_descriptors->SetRepresentation(modify_index, new_representation);
    return old_map;
  }

  int descriptors = old_map->NumberOfOwnDescriptors();
  Map* root_map = old_map->FindRootMap();

  // Check the state of the root map.
  if (!old_map->EquivalentToForTransition(root_map)) {
    return CopyGeneralizeAllRepresentations();
  }

  int verbatim = root_map->NumberOfOwnDescriptors();

  Map* updated = root_map->FindUpdatedMap(
      verbatim, descriptors, old_descriptors);
  if (updated == NULL) return CopyGeneralizeAllRepresentations();

  DescriptorArray* updated_descriptors = updated->instance_descriptors();

  int valid = updated->NumberOfOwnDescriptors();
  if (updated_descriptors->IsMoreGeneralThan(
          verbatim, valid, descriptors, old_descriptors)) {
    Representation updated_representation =
        updated_descriptors->GetDetails(modify_index).representation();
    if (new_representation.fits_into(updated_representation)) {
      if (FLAG_trace_generalization &&
          !(modify_index == 0 && new_representation.IsNone())) {
        PropertyDetails old_details = old_descriptors->GetDetails(modify_index);
        PrintF("migrating to existing map %p(%s) -> %p(%s)\n",
               static_cast<void*>(this),
               old_details.representation().Mnemonic(),
               static_cast<void*>(updated),
               updated_representation.Mnemonic());
      }
      return updated;
    }
  }

  DescriptorArray* new_descriptors;
  MaybeObject* maybe_descriptors = updated_descriptors->Merge(
      verbatim, valid, descriptors, old_descriptors);
  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;

  old_representation =
      new_descriptors->GetDetails(modify_index).representation();
  Representation updated_representation =
      new_representation.generalize(old_representation);
  if (!updated_representation.Equals(old_representation)) {
    new_descriptors->SetRepresentation(modify_index, updated_representation);
  }

  Map* split_map = root_map->FindLastMatchMap(
      verbatim, descriptors, new_descriptors);

  int split_descriptors = split_map->NumberOfOwnDescriptors();
  // This is shadowed by |updated_descriptors| being more general than
  // |old_descriptors|.
  ASSERT(descriptors != split_descriptors);

  int descriptor = split_descriptors;
  split_map->DeprecateTarget(
      old_descriptors->GetKey(descriptor), new_descriptors);

  if (FLAG_trace_generalization &&
      !(modify_index == 0 && new_representation.IsNone())) {
    PrintF("migrating to new map %i: %p(%s) -> %p(%s) (%i steps)\n",
           modify_index,
           static_cast<void*>(this),
           old_representation.Mnemonic(),
           static_cast<void*>(new_descriptors),
           updated_representation.Mnemonic(),
           descriptors - descriptor);
  }

  Map* new_map = split_map;
  // Add missing transitions.
  for (; descriptor < descriptors; descriptor++) {
    MaybeObject* maybe_map = new_map->CopyInstallDescriptors(
        descriptor, new_descriptors);
    if (!maybe_map->To(&new_map)) {
      // Create a handle for the last created map to ensure it stays alive
      // during GC. Its descriptor array is too large, but it will be
      // overwritten during retry anyway.
      Handle<Map>(new_map);
      return maybe_map;
    }
    new_map->set_migration_target(true);
  }

  new_map->set_owns_descriptors(true);
  return new_map;
}


Map* Map::CurrentMapForDeprecated() {
  DisallowHeapAllocation no_allocation;
  if (!is_deprecated()) return this;

  DescriptorArray* old_descriptors = instance_descriptors();

  int descriptors = NumberOfOwnDescriptors();
  Map* root_map = FindRootMap();

  // Check the state of the root map.
  if (!EquivalentToForTransition(root_map)) return NULL;
  int verbatim = root_map->NumberOfOwnDescriptors();

  Map* updated = root_map->FindUpdatedMap(
      verbatim, descriptors, old_descriptors);
  if (updated == NULL) return NULL;

  DescriptorArray* updated_descriptors = updated->instance_descriptors();
  int valid = updated->NumberOfOwnDescriptors();
  if (!updated_descriptors->IsMoreGeneralThan(
          verbatim, valid, descriptors, old_descriptors)) {
    return NULL;
  }

  return updated;
}


MaybeObject* JSObject::SetPropertyWithInterceptor(
    Name* name,
    Object* value,
    PropertyAttributes attributes,
    StrictModeFlag strict_mode) {
  // TODO(rossberg): Support symbols in the API.
  if (name->IsSymbol()) return value;
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<JSObject> this_handle(this);
  Handle<String> name_handle(String::cast(name));
  Handle<Object> value_handle(value, isolate);
  Handle<InterceptorInfo> interceptor(GetNamedInterceptor());
  if (!interceptor->setter()->IsUndefined()) {
    LOG(isolate, ApiNamedPropertyAccess("interceptor-named-set", this, name));
    PropertyCallbackArguments args(isolate, interceptor->data(), this, this);
    v8::NamedPropertySetter setter =
        v8::ToCData<v8::NamedPropertySetter>(interceptor->setter());
    Handle<Object> value_unhole(value->IsTheHole() ?
                                isolate->heap()->undefined_value() :
                                value,
                                isolate);
    v8::Handle<v8::Value> result = args.Call(setter,
                                             v8::Utils::ToLocal(name_handle),
                                             v8::Utils::ToLocal(value_unhole));
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    if (!result.IsEmpty()) return *value_handle;
  }
  MaybeObject* raw_result =
      this_handle->SetPropertyPostInterceptor(*name_handle,
                                              *value_handle,
                                              attributes,
                                              strict_mode,
                                              PERFORM_EXTENSIBILITY_CHECK);
  RETURN_IF_SCHEDULED_EXCEPTION(isolate);
  return raw_result;
}


Handle<Object> JSReceiver::SetProperty(Handle<JSReceiver> object,
                                       Handle<Name> key,
                                       Handle<Object> value,
                                       PropertyAttributes attributes,
                                       StrictModeFlag strict_mode) {
  CALL_HEAP_FUNCTION(object->GetIsolate(),
                     object->SetProperty(*key, *value, attributes, strict_mode),
                     Object);
}


MaybeObject* JSReceiver::SetPropertyOrFail(
    Handle<JSReceiver> object,
    Handle<Name> key,
    Handle<Object> value,
    PropertyAttributes attributes,
    StrictModeFlag strict_mode,
    JSReceiver::StoreFromKeyed store_mode) {
  CALL_HEAP_FUNCTION_PASS_EXCEPTION(
      object->GetIsolate(),
      object->SetProperty(*key, *value, attributes, strict_mode, store_mode));
}


MaybeObject* JSReceiver::SetProperty(Name* name,
                                     Object* value,
                                     PropertyAttributes attributes,
                                     StrictModeFlag strict_mode,
                                     JSReceiver::StoreFromKeyed store_mode) {
  LookupResult result(GetIsolate());
  LocalLookup(name, &result, true);
  if (!result.IsFound()) {
    map()->LookupTransition(JSObject::cast(this), name, &result);
  }
  return SetProperty(&result, name, value, attributes, strict_mode, store_mode);
}


MaybeObject* JSObject::SetPropertyWithCallback(Object* structure,
                                               Name* name,
                                               Object* value,
                                               JSObject* holder,
                                               StrictModeFlag strict_mode) {
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);

  // We should never get here to initialize a const with the hole
  // value since a const declaration would conflict with the setter.
  ASSERT(!value->IsTheHole());
  Handle<Object> value_handle(value, isolate);

  // To accommodate both the old and the new api we switch on the
  // data structure used to store the callbacks.  Eventually foreign
  // callbacks should be phased out.
  if (structure->IsForeign()) {
    AccessorDescriptor* callback =
        reinterpret_cast<AccessorDescriptor*>(
            Foreign::cast(structure)->foreign_address());
    MaybeObject* obj = (callback->setter)(this,  value, callback->data);
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    if (obj->IsFailure()) return obj;
    return *value_handle;
  }

  if (structure->IsExecutableAccessorInfo()) {
    // api style callbacks
    ExecutableAccessorInfo* data = ExecutableAccessorInfo::cast(structure);
    if (!data->IsCompatibleReceiver(this)) {
      Handle<Object> name_handle(name, isolate);
      Handle<Object> receiver_handle(this, isolate);
      Handle<Object> args[2] = { name_handle, receiver_handle };
      Handle<Object> error =
          isolate->factory()->NewTypeError("incompatible_method_receiver",
                                           HandleVector(args,
                                                        ARRAY_SIZE(args)));
      return isolate->Throw(*error);
    }
    // TODO(rossberg): Support symbols in the API.
    if (name->IsSymbol()) return value;
    Object* call_obj = data->setter();
    v8::AccessorSetter call_fun = v8::ToCData<v8::AccessorSetter>(call_obj);
    if (call_fun == NULL) return value;
    Handle<String> key(String::cast(name));
    LOG(isolate, ApiNamedPropertyAccess("store", this, name));
    PropertyCallbackArguments args(
        isolate, data->data(), this, JSObject::cast(holder));
    args.Call(call_fun,
              v8::Utils::ToLocal(key),
              v8::Utils::ToLocal(value_handle));
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    return *value_handle;
  }

  if (structure->IsAccessorPair()) {
    Object* setter = AccessorPair::cast(structure)->setter();
    if (setter->IsSpecFunction()) {
      // TODO(rossberg): nicer would be to cast to some JSCallable here...
     return SetPropertyWithDefinedSetter(JSReceiver::cast(setter), value);
    } else {
      if (strict_mode == kNonStrictMode) {
        return value;
      }
      Handle<Name> key(name);
      Handle<Object> holder_handle(holder, isolate);
      Handle<Object> args[2] = { key, holder_handle };
      return isolate->Throw(
          *isolate->factory()->NewTypeError("no_setter_in_callback",
                                            HandleVector(args, 2)));
    }
  }

  // TODO(dcarney): Handle correctly.
  if (structure->IsDeclaredAccessorInfo()) {
    return value;
  }

  UNREACHABLE();
  return NULL;
}


MaybeObject* JSReceiver::SetPropertyWithDefinedSetter(JSReceiver* setter,
                                                      Object* value) {
  Isolate* isolate = GetIsolate();
  Handle<Object> value_handle(value, isolate);
  Handle<JSReceiver> fun(setter, isolate);
  Handle<JSReceiver> self(this, isolate);
#ifdef ENABLE_DEBUGGER_SUPPORT
  Debug* debug = isolate->debug();
  // Handle stepping into a setter if step into is active.
  // TODO(rossberg): should this apply to getters that are function proxies?
  if (debug->StepInActive() && fun->IsJSFunction()) {
    debug->HandleStepIn(
        Handle<JSFunction>::cast(fun), Handle<Object>::null(), 0, false);
  }
#endif
  bool has_pending_exception;
  Handle<Object> argv[] = { value_handle };
  Execution::Call(fun, self, ARRAY_SIZE(argv), argv, &has_pending_exception);
  // Check for pending exception and return the result.
  if (has_pending_exception) return Failure::Exception();
  return *value_handle;
}


MaybeObject* JSObject::SetElementWithCallbackSetterInPrototypes(
    uint32_t index,
    Object* value,
    bool* found,
    StrictModeFlag strict_mode) {
  Heap* heap = GetHeap();
  for (Object* pt = GetPrototype();
       pt != heap->null_value();
       pt = pt->GetPrototype(GetIsolate())) {
    if (pt->IsJSProxy()) {
      String* name;
      MaybeObject* maybe = heap->Uint32ToString(index);
      if (!maybe->To<String>(&name)) {
        *found = true;  // Force abort
        return maybe;
      }
      return JSProxy::cast(pt)->SetPropertyViaPrototypesWithHandler(
          this, name, value, NONE, strict_mode, found);
    }
    if (!JSObject::cast(pt)->HasDictionaryElements()) {
      continue;
    }
    SeededNumberDictionary* dictionary =
        JSObject::cast(pt)->element_dictionary();
    int entry = dictionary->FindEntry(index);
    if (entry != SeededNumberDictionary::kNotFound) {
      PropertyDetails details = dictionary->DetailsAt(entry);
      if (details.type() == CALLBACKS) {
        *found = true;
        return SetElementWithCallback(dictionary->ValueAt(entry),
                                      index,
                                      value,
                                      JSObject::cast(pt),
                                      strict_mode);
      }
    }
  }
  *found = false;
  return heap->the_hole_value();
}

MaybeObject* JSObject::SetPropertyViaPrototypes(
    Name* name,
    Object* value,
    PropertyAttributes attributes,
    StrictModeFlag strict_mode,
    bool* done) {
  Heap* heap = GetHeap();
  Isolate* isolate = heap->isolate();

  *done = false;
  // We could not find a local property so let's check whether there is an
  // accessor that wants to handle the property, or whether the property is
  // read-only on the prototype chain.
  LookupResult result(isolate);
  LookupRealNamedPropertyInPrototypes(name, &result);
  if (result.IsFound()) {
    switch (result.type()) {
      case NORMAL:
      case FIELD:
      case CONSTANT:
        *done = result.IsReadOnly();
        break;
      case INTERCEPTOR: {
        PropertyAttributes attr =
            result.holder()->GetPropertyAttributeWithInterceptor(
                this, name, true);
        *done = !!(attr & READ_ONLY);
        break;
      }
      case CALLBACKS: {
        if (!FLAG_es5_readonly && result.IsReadOnly()) break;
        *done = true;
        return SetPropertyWithCallback(result.GetCallbackObject(),
            name, value, result.holder(), strict_mode);
      }
      case HANDLER: {
        return result.proxy()->SetPropertyViaPrototypesWithHandler(
            this, name, value, attributes, strict_mode, done);
      }
      case TRANSITION:
      case NONEXISTENT:
        UNREACHABLE();
        break;
    }
  }

  // If we get here with *done true, we have encountered a read-only property.
  if (!FLAG_es5_readonly) *done = false;
  if (*done) {
    if (strict_mode == kNonStrictMode) return value;
    Handle<Object> args[] = { Handle<Object>(name, isolate),
                              Handle<Object>(this, isolate)};
    return isolate->Throw(*isolate->factory()->NewTypeError(
      "strict_read_only_property", HandleVector(args, ARRAY_SIZE(args))));
  }
  return heap->the_hole_value();
}


void Map::EnsureDescriptorSlack(Handle<Map> map, int slack) {
  Handle<DescriptorArray> descriptors(map->instance_descriptors());
  if (slack <= descriptors->NumberOfSlackDescriptors()) return;
  int number_of_descriptors = descriptors->number_of_descriptors();
  Isolate* isolate = map->GetIsolate();
  Handle<DescriptorArray> new_descriptors =
      isolate->factory()->NewDescriptorArray(number_of_descriptors, slack);
  DescriptorArray::WhitenessWitness witness(*new_descriptors);

  for (int i = 0; i < number_of_descriptors; ++i) {
    new_descriptors->CopyFrom(i, *descriptors, i, witness);
  }

  map->set_instance_descriptors(*new_descriptors);
}


void Map::AppendCallbackDescriptors(Handle<Map> map,
                                    Handle<Object> descriptors) {
  Isolate* isolate = map->GetIsolate();
  Handle<DescriptorArray> array(map->instance_descriptors());
  NeanderArray callbacks(descriptors);
  int nof_callbacks = callbacks.length();

  ASSERT(array->NumberOfSlackDescriptors() >= nof_callbacks);

  // Ensure the keys are unique names before writing them into the
  // instance descriptor. Since it may cause a GC, it has to be done before we
  // temporarily put the heap in an invalid state while appending descriptors.
  for (int i = 0; i < nof_callbacks; ++i) {
    Handle<AccessorInfo> entry(AccessorInfo::cast(callbacks.get(i)));
    if (!entry->name()->IsUniqueName()) {
      Handle<String> key =
          isolate->factory()->InternalizedStringFromString(
              Handle<String>(String::cast(entry->name())));
      entry->set_name(*key);
    }
  }

  int nof = map->NumberOfOwnDescriptors();

  // Fill in new callback descriptors.  Process the callbacks from
  // back to front so that the last callback with a given name takes
  // precedence over previously added callbacks with that name.
  for (int i = nof_callbacks - 1; i >= 0; i--) {
    AccessorInfo* entry = AccessorInfo::cast(callbacks.get(i));
    Name* key = Name::cast(entry->name());
    // Check if a descriptor with this name already exists before writing.
    if (array->Search(key, nof) == DescriptorArray::kNotFound) {
      CallbacksDescriptor desc(key, entry, entry->property_attributes());
      array->Append(&desc);
      nof += 1;
    }
  }

  map->SetNumberOfOwnDescriptors(nof);
}


static bool ContainsMap(MapHandleList* maps, Handle<Map> map) {
  ASSERT(!map.is_null());
  for (int i = 0; i < maps->length(); ++i) {
    if (!maps->at(i).is_null() && maps->at(i).is_identical_to(map)) return true;
  }
  return false;
}


template <class T>
static Handle<T> MaybeNull(T* p) {
  if (p == NULL) return Handle<T>::null();
  return Handle<T>(p);
}


Handle<Map> Map::FindTransitionedMap(MapHandleList* candidates) {
  ElementsKind kind = elements_kind();
  Handle<Map> transitioned_map = Handle<Map>::null();
  Handle<Map> current_map(this);
  bool packed = IsFastPackedElementsKind(kind);
  if (IsTransitionableFastElementsKind(kind)) {
    while (CanTransitionToMoreGeneralFastElementsKind(kind, false)) {
      kind = GetNextMoreGeneralFastElementsKind(kind, false);
      Handle<Map> maybe_transitioned_map =
          MaybeNull(current_map->LookupElementsTransitionMap(kind));
      if (maybe_transitioned_map.is_null()) break;
      if (ContainsMap(candidates, maybe_transitioned_map) &&
          (packed || !IsFastPackedElementsKind(kind))) {
        transitioned_map = maybe_transitioned_map;
        if (!IsFastPackedElementsKind(kind)) packed = false;
      }
      current_map = maybe_transitioned_map;
    }
  }
  return transitioned_map;
}


static Map* FindClosestElementsTransition(Map* map, ElementsKind to_kind) {
  Map* current_map = map;
  int index = GetSequenceIndexFromFastElementsKind(map->elements_kind());
  int to_index = IsFastElementsKind(to_kind)
      ? GetSequenceIndexFromFastElementsKind(to_kind)
      : GetSequenceIndexFromFastElementsKind(TERMINAL_FAST_ELEMENTS_KIND);

  ASSERT(index <= to_index);

  for (; index < to_index; ++index) {
    if (!current_map->HasElementsTransition()) return current_map;
    current_map = current_map->elements_transition_map();
  }
  if (!IsFastElementsKind(to_kind) && current_map->HasElementsTransition()) {
    Map* next_map = current_map->elements_transition_map();
    if (next_map->elements_kind() == to_kind) return next_map;
  }
  ASSERT(IsFastElementsKind(to_kind)
         ? current_map->elements_kind() == to_kind
         : current_map->elements_kind() == TERMINAL_FAST_ELEMENTS_KIND);
  return current_map;
}


Map* Map::LookupElementsTransitionMap(ElementsKind to_kind) {
  Map* to_map = FindClosestElementsTransition(this, to_kind);
  if (to_map->elements_kind() == to_kind) return to_map;
  return NULL;
}


bool Map::IsMapInArrayPrototypeChain() {
  Isolate* isolate = GetIsolate();
  if (isolate->initial_array_prototype()->map() == this) {
    return true;
  }

  if (isolate->initial_object_prototype()->map() == this) {
    return true;
  }

  return false;
}


static MaybeObject* AddMissingElementsTransitions(Map* map,
                                                  ElementsKind to_kind) {
  ASSERT(IsFastElementsKind(map->elements_kind()));
  int index = GetSequenceIndexFromFastElementsKind(map->elements_kind());
  int to_index = IsFastElementsKind(to_kind)
      ? GetSequenceIndexFromFastElementsKind(to_kind)
      : GetSequenceIndexFromFastElementsKind(TERMINAL_FAST_ELEMENTS_KIND);

  ASSERT(index <= to_index);

  Map* current_map = map;

  for (; index < to_index; ++index) {
    ElementsKind next_kind = GetFastElementsKindFromSequenceIndex(index + 1);
    MaybeObject* maybe_next_map =
        current_map->CopyAsElementsKind(next_kind, INSERT_TRANSITION);
    if (!maybe_next_map->To(&current_map)) return maybe_next_map;
  }

  // In case we are exiting the fast elements kind system, just add the map in
  // the end.
  if (!IsFastElementsKind(to_kind)) {
    MaybeObject* maybe_next_map =
        current_map->CopyAsElementsKind(to_kind, INSERT_TRANSITION);
    if (!maybe_next_map->To(&current_map)) return maybe_next_map;
  }

  ASSERT(current_map->elements_kind() == to_kind);
  return current_map;
}


Handle<Map> JSObject::GetElementsTransitionMap(Handle<JSObject> object,
                                               ElementsKind to_kind) {
  Isolate* isolate = object->GetIsolate();
  CALL_HEAP_FUNCTION(isolate,
                     object->GetElementsTransitionMap(isolate, to_kind),
                     Map);
}


MaybeObject* JSObject::GetElementsTransitionMapSlow(ElementsKind to_kind) {
  Map* start_map = map();
  ElementsKind from_kind = start_map->elements_kind();

  if (from_kind == to_kind) {
    return start_map;
  }

  bool allow_store_transition =
      // Only remember the map transition if there is not an already existing
      // non-matching element transition.
      !start_map->IsUndefined() && !start_map->is_shared() &&
      IsFastElementsKind(from_kind);

  // Only store fast element maps in ascending generality.
  if (IsFastElementsKind(to_kind)) {
    allow_store_transition &=
        IsTransitionableFastElementsKind(from_kind) &&
        IsMoreGeneralElementsKindTransition(from_kind, to_kind);
  }

  if (!allow_store_transition) {
    return start_map->CopyAsElementsKind(to_kind, OMIT_TRANSITION);
  }

  return start_map->AsElementsKind(to_kind);
}


MaybeObject* Map::AsElementsKind(ElementsKind kind) {
  Map* closest_map = FindClosestElementsTransition(this, kind);

  if (closest_map->elements_kind() == kind) {
    return closest_map;
  }

  return AddMissingElementsTransitions(closest_map, kind);
}


void JSObject::LocalLookupRealNamedProperty(Name* name, LookupResult* result) {
  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return result->NotFound();
    ASSERT(proto->IsJSGlobalObject());
    return JSObject::cast(proto)->LocalLookupRealNamedProperty(name, result);
  }

  if (HasFastProperties()) {
    map()->LookupDescriptor(this, name, result);
    // A property or a map transition was found. We return all of these result
    // types because LocalLookupRealNamedProperty is used when setting
    // properties where map transitions are handled.
    ASSERT(!result->IsFound() ||
           (result->holder() == this && result->IsFastPropertyType()));
    // Disallow caching for uninitialized constants. These can only
    // occur as fields.
    if (result->IsField() &&
        result->IsReadOnly() &&
        RawFastPropertyAt(result->GetFieldIndex().field_index())->IsTheHole()) {
      result->DisallowCaching();
    }
    return;
  }

  int entry = property_dictionary()->FindEntry(name);
  if (entry != NameDictionary::kNotFound) {
    Object* value = property_dictionary()->ValueAt(entry);
    if (IsGlobalObject()) {
      PropertyDetails d = property_dictionary()->DetailsAt(entry);
      if (d.IsDeleted()) {
        result->NotFound();
        return;
      }
      value = PropertyCell::cast(value)->value();
    }
    // Make sure to disallow caching for uninitialized constants
    // found in the dictionary-mode objects.
    if (value->IsTheHole()) result->DisallowCaching();
    result->DictionaryResult(this, entry);
    return;
  }

  result->NotFound();
}


void JSObject::LookupRealNamedProperty(Name* name, LookupResult* result) {
  LocalLookupRealNamedProperty(name, result);
  if (result->IsFound()) return;

  LookupRealNamedPropertyInPrototypes(name, result);
}


void JSObject::LookupRealNamedPropertyInPrototypes(Name* name,
                                                   LookupResult* result) {
  Isolate* isolate = GetIsolate();
  Heap* heap = isolate->heap();
  for (Object* pt = GetPrototype();
       pt != heap->null_value();
       pt = pt->GetPrototype(isolate)) {
    if (pt->IsJSProxy()) {
      return result->HandlerResult(JSProxy::cast(pt));
    }
    JSObject::cast(pt)->LocalLookupRealNamedProperty(name, result);
    ASSERT(!(result->IsFound() && result->type() == INTERCEPTOR));
    if (result->IsFound()) return;
  }
  result->NotFound();
}


// We only need to deal with CALLBACKS and INTERCEPTORS
MaybeObject* JSObject::SetPropertyWithFailedAccessCheck(
    LookupResult* result,
    Name* name,
    Object* value,
    bool check_prototype,
    StrictModeFlag strict_mode) {
  if (check_prototype && !result->IsProperty()) {
    LookupRealNamedPropertyInPrototypes(name, result);
  }

  if (result->IsProperty()) {
    if (!result->IsReadOnly()) {
      switch (result->type()) {
        case CALLBACKS: {
          Object* obj = result->GetCallbackObject();
          if (obj->IsAccessorInfo()) {
            AccessorInfo* info = AccessorInfo::cast(obj);
            if (info->all_can_write()) {
              return SetPropertyWithCallback(result->GetCallbackObject(),
                                             name,
                                             value,
                                             result->holder(),
                                             strict_mode);
            }
          }
          break;
        }
        case INTERCEPTOR: {
          // Try lookup real named properties. Note that only property can be
          // set is callbacks marked as ALL_CAN_WRITE on the prototype chain.
          LookupResult r(GetIsolate());
          LookupRealNamedProperty(name, &r);
          if (r.IsProperty()) {
            return SetPropertyWithFailedAccessCheck(&r,
                                                    name,
                                                    value,
                                                    check_prototype,
                                                    strict_mode);
          }
          break;
        }
        default: {
          break;
        }
      }
    }
  }

  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<Object> value_handle(value, isolate);
  isolate->ReportFailedAccessCheck(this, v8::ACCESS_SET);
  RETURN_IF_SCHEDULED_EXCEPTION(isolate);
  return *value_handle;
}


MaybeObject* JSReceiver::SetProperty(LookupResult* result,
                                     Name* key,
                                     Object* value,
                                     PropertyAttributes attributes,
                                     StrictModeFlag strict_mode,
                                     JSReceiver::StoreFromKeyed store_mode) {
  if (result->IsHandler()) {
    return result->proxy()->SetPropertyWithHandler(
        this, key, value, attributes, strict_mode);
  } else {
    return JSObject::cast(this)->SetPropertyForResult(
        result, key, value, attributes, strict_mode, store_mode);
  }
}


bool JSProxy::HasPropertyWithHandler(Name* name_raw) {
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<Object> receiver(this, isolate);
  Handle<Object> name(name_raw, isolate);

  // TODO(rossberg): adjust once there is a story for symbols vs proxies.
  if (name->IsSymbol()) return false;

  Handle<Object> args[] = { name };
  Handle<Object> result = CallTrap(
    "has", isolate->derived_has_trap(), ARRAY_SIZE(args), args);
  if (isolate->has_pending_exception()) return false;

  return result->BooleanValue();
}


MUST_USE_RESULT MaybeObject* JSProxy::SetPropertyWithHandler(
    JSReceiver* receiver_raw,
    Name* name_raw,
    Object* value_raw,
    PropertyAttributes attributes,
    StrictModeFlag strict_mode) {
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<JSReceiver> receiver(receiver_raw);
  Handle<Object> name(name_raw, isolate);
  Handle<Object> value(value_raw, isolate);

  // TODO(rossberg): adjust once there is a story for symbols vs proxies.
  if (name->IsSymbol()) return *value;

  Handle<Object> args[] = { receiver, name, value };
  CallTrap("set", isolate->derived_set_trap(), ARRAY_SIZE(args), args);
  if (isolate->has_pending_exception()) return Failure::Exception();

  return *value;
}


MUST_USE_RESULT MaybeObject* JSProxy::SetPropertyViaPrototypesWithHandler(
    JSReceiver* receiver_raw,
    Name* name_raw,
    Object* value_raw,
    PropertyAttributes attributes,
    StrictModeFlag strict_mode,
    bool* done) {
  Isolate* isolate = GetIsolate();
  Handle<JSProxy> proxy(this);
  Handle<JSReceiver> receiver(receiver_raw);
  Handle<Name> name(name_raw);
  Handle<Object> value(value_raw, isolate);
  Handle<Object> handler(this->handler(), isolate);  // Trap might morph proxy.

  // TODO(rossberg): adjust once there is a story for symbols vs proxies.
  if (name->IsSymbol()) {
    *done = false;
    return isolate->heap()->the_hole_value();
  }

  *done = true;  // except where redefined...
  Handle<Object> args[] = { name };
  Handle<Object> result = proxy->CallTrap(
      "getPropertyDescriptor", Handle<Object>(), ARRAY_SIZE(args), args);
  if (isolate->has_pending_exception()) return Failure::Exception();

  if (result->IsUndefined()) {
    *done = false;
    return isolate->heap()->the_hole_value();
  }

  // Emulate [[GetProperty]] semantics for proxies.
  bool has_pending_exception;
  Handle<Object> argv[] = { result };
  Handle<Object> desc =
      Execution::Call(isolate->to_complete_property_descriptor(), result,
                      ARRAY_SIZE(argv), argv, &has_pending_exception);
  if (has_pending_exception) return Failure::Exception();

  // [[GetProperty]] requires to check that all properties are configurable.
  Handle<String> configurable_name =
      isolate->factory()->InternalizeOneByteString(
          STATIC_ASCII_VECTOR("configurable_"));
  Handle<Object> configurable(
      v8::internal::GetProperty(isolate, desc, configurable_name));
  ASSERT(!isolate->has_pending_exception());
  ASSERT(configurable->IsTrue() || configurable->IsFalse());
  if (configurable->IsFalse()) {
    Handle<String> trap =
        isolate->factory()->InternalizeOneByteString(
            STATIC_ASCII_VECTOR("getPropertyDescriptor"));
    Handle<Object> args[] = { handler, trap, name };
    Handle<Object> error = isolate->factory()->NewTypeError(
        "proxy_prop_not_configurable", HandleVector(args, ARRAY_SIZE(args)));
    return isolate->Throw(*error);
  }
  ASSERT(configurable->IsTrue());

  // Check for DataDescriptor.
  Handle<String> hasWritable_name =
      isolate->factory()->InternalizeOneByteString(
          STATIC_ASCII_VECTOR("hasWritable_"));
  Handle<Object> hasWritable(
      v8::internal::GetProperty(isolate, desc, hasWritable_name));
  ASSERT(!isolate->has_pending_exception());
  ASSERT(hasWritable->IsTrue() || hasWritable->IsFalse());
  if (hasWritable->IsTrue()) {
    Handle<String> writable_name =
        isolate->factory()->InternalizeOneByteString(
            STATIC_ASCII_VECTOR("writable_"));
    Handle<Object> writable(
        v8::internal::GetProperty(isolate, desc, writable_name));
    ASSERT(!isolate->has_pending_exception());
    ASSERT(writable->IsTrue() || writable->IsFalse());
    *done = writable->IsFalse();
    if (!*done) return GetHeap()->the_hole_value();
    if (strict_mode == kNonStrictMode) return *value;
    Handle<Object> args[] = { name, receiver };
    Handle<Object> error = isolate->factory()->NewTypeError(
        "strict_read_only_property", HandleVector(args, ARRAY_SIZE(args)));
    return isolate->Throw(*error);
  }

  // We have an AccessorDescriptor.
  Handle<String> set_name = isolate->factory()->InternalizeOneByteString(
      STATIC_ASCII_VECTOR("set_"));
  Handle<Object> setter(v8::internal::GetProperty(isolate, desc, set_name));
  ASSERT(!isolate->has_pending_exception());
  if (!setter->IsUndefined()) {
    // TODO(rossberg): nicer would be to cast to some JSCallable here...
    return receiver->SetPropertyWithDefinedSetter(
        JSReceiver::cast(*setter), *value);
  }

  if (strict_mode == kNonStrictMode) return *value;
  Handle<Object> args2[] = { name, proxy };
  Handle<Object> error = isolate->factory()->NewTypeError(
      "no_setter_in_callback", HandleVector(args2, ARRAY_SIZE(args2)));
  return isolate->Throw(*error);
}


Handle<Object> JSProxy::DeletePropertyWithHandler(
    Handle<JSProxy> object, Handle<Name> name, DeleteMode mode) {
  Isolate* isolate = object->GetIsolate();

  // TODO(rossberg): adjust once there is a story for symbols vs proxies.
  if (name->IsSymbol()) return isolate->factory()->false_value();

  Handle<Object> args[] = { name };
  Handle<Object> result = object->CallTrap(
      "delete", Handle<Object>(), ARRAY_SIZE(args), args);
  if (isolate->has_pending_exception()) return Handle<Object>();

  bool result_bool = result->BooleanValue();
  if (mode == STRICT_DELETION && !result_bool) {
    Handle<Object> handler(object->handler(), isolate);
    Handle<String> trap_name = isolate->factory()->InternalizeOneByteString(
        STATIC_ASCII_VECTOR("delete"));
    Handle<Object> args[] = { handler, trap_name };
    Handle<Object> error = isolate->factory()->NewTypeError(
        "handler_failed", HandleVector(args, ARRAY_SIZE(args)));
    isolate->Throw(*error);
    return Handle<Object>();
  }
  return isolate->factory()->ToBoolean(result_bool);
}


Handle<Object> JSProxy::DeleteElementWithHandler(
    Handle<JSProxy> object, uint32_t index, DeleteMode mode) {
  Isolate* isolate = object->GetIsolate();
  Handle<String> name = isolate->factory()->Uint32ToString(index);
  return JSProxy::DeletePropertyWithHandler(object, name, mode);
}


MUST_USE_RESULT PropertyAttributes JSProxy::GetPropertyAttributeWithHandler(
    JSReceiver* receiver_raw,
    Name* name_raw) {
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<JSProxy> proxy(this);
  Handle<Object> handler(this->handler(), isolate);  // Trap might morph proxy.
  Handle<JSReceiver> receiver(receiver_raw);
  Handle<Object> name(name_raw, isolate);

  // TODO(rossberg): adjust once there is a story for symbols vs proxies.
  if (name->IsSymbol()) return ABSENT;

  Handle<Object> args[] = { name };
  Handle<Object> result = CallTrap(
    "getPropertyDescriptor", Handle<Object>(), ARRAY_SIZE(args), args);
  if (isolate->has_pending_exception()) return NONE;

  if (result->IsUndefined()) return ABSENT;

  bool has_pending_exception;
  Handle<Object> argv[] = { result };
  Handle<Object> desc =
      Execution::Call(isolate->to_complete_property_descriptor(), result,
                      ARRAY_SIZE(argv), argv, &has_pending_exception);
  if (has_pending_exception) return NONE;

  // Convert result to PropertyAttributes.
  Handle<String> enum_n = isolate->factory()->InternalizeOneByteString(
      STATIC_ASCII_VECTOR("enumerable_"));
  Handle<Object> enumerable(v8::internal::GetProperty(isolate, desc, enum_n));
  if (isolate->has_pending_exception()) return NONE;
  Handle<String> conf_n = isolate->factory()->InternalizeOneByteString(
      STATIC_ASCII_VECTOR("configurable_"));
  Handle<Object> configurable(v8::internal::GetProperty(isolate, desc, conf_n));
  if (isolate->has_pending_exception()) return NONE;
  Handle<String> writ_n = isolate->factory()->InternalizeOneByteString(
      STATIC_ASCII_VECTOR("writable_"));
  Handle<Object> writable(v8::internal::GetProperty(isolate, desc, writ_n));
  if (isolate->has_pending_exception()) return NONE;
  if (!writable->BooleanValue()) {
    Handle<String> set_n = isolate->factory()->InternalizeOneByteString(
        STATIC_ASCII_VECTOR("set_"));
    Handle<Object> setter(v8::internal::GetProperty(isolate, desc, set_n));
    if (isolate->has_pending_exception()) return NONE;
    writable = isolate->factory()->ToBoolean(!setter->IsUndefined());
  }

  if (configurable->IsFalse()) {
    Handle<String> trap = isolate->factory()->InternalizeOneByteString(
        STATIC_ASCII_VECTOR("getPropertyDescriptor"));
    Handle<Object> args[] = { handler, trap, name };
    Handle<Object> error = isolate->factory()->NewTypeError(
        "proxy_prop_not_configurable", HandleVector(args, ARRAY_SIZE(args)));
    isolate->Throw(*error);
    return NONE;
  }

  int attributes = NONE;
  if (!enumerable->BooleanValue()) attributes |= DONT_ENUM;
  if (!configurable->BooleanValue()) attributes |= DONT_DELETE;
  if (!writable->BooleanValue()) attributes |= READ_ONLY;
  return static_cast<PropertyAttributes>(attributes);
}


MUST_USE_RESULT PropertyAttributes JSProxy::GetElementAttributeWithHandler(
    JSReceiver* receiver_raw,
    uint32_t index) {
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<JSProxy> proxy(this);
  Handle<JSReceiver> receiver(receiver_raw);
  Handle<String> name = isolate->factory()->Uint32ToString(index);
  return proxy->GetPropertyAttributeWithHandler(*receiver, *name);
}


void JSProxy::Fix() {
  Isolate* isolate = GetIsolate();
  HandleScope scope(isolate);
  Handle<JSProxy> self(this);

  // Save identity hash.
  MaybeObject* maybe_hash = GetIdentityHash(OMIT_CREATION);

  if (IsJSFunctionProxy()) {
    isolate->factory()->BecomeJSFunction(self);
    // Code will be set on the JavaScript side.
  } else {
    isolate->factory()->BecomeJSObject(self);
  }
  ASSERT(self->IsJSObject());

  // Inherit identity, if it was present.
  Object* hash;
  if (maybe_hash->To<Object>(&hash) && hash->IsSmi()) {
    Handle<JSObject> new_self(JSObject::cast(*self));
    isolate->factory()->SetIdentityHash(new_self, Smi::cast(hash));
  }
}


MUST_USE_RESULT Handle<Object> JSProxy::CallTrap(const char* name,
                                                 Handle<Object> derived,
                                                 int argc,
                                                 Handle<Object> argv[]) {
  Isolate* isolate = GetIsolate();
  Handle<Object> handler(this->handler(), isolate);

  Handle<String> trap_name = isolate->factory()->InternalizeUtf8String(name);
  Handle<Object> trap(v8::internal::GetProperty(isolate, handler, trap_name));
  if (isolate->has_pending_exception()) return trap;

  if (trap->IsUndefined()) {
    if (derived.is_null()) {
      Handle<Object> args[] = { handler, trap_name };
      Handle<Object> error = isolate->factory()->NewTypeError(
        "handler_trap_missing", HandleVector(args, ARRAY_SIZE(args)));
      isolate->Throw(*error);
      return Handle<Object>();
    }
    trap = Handle<Object>(derived);
  }

  bool threw;
  return Execution::Call(trap, handler, argc, argv, &threw);
}


void JSObject::AllocateStorageForMap(Handle<JSObject> object, Handle<Map> map) {
  CALL_HEAP_FUNCTION_VOID(
      object->GetIsolate(),
      object->AllocateStorageForMap(*map));
}


void JSObject::MigrateInstance(Handle<JSObject> object) {
  if (FLAG_trace_migration) {
    PrintF("migrating instance %p (%p)\n",
           static_cast<void*>(*object),
           static_cast<void*>(object->map()));
  }
  CALL_HEAP_FUNCTION_VOID(
      object->GetIsolate(),
      object->MigrateInstance());
}


Handle<Object> JSObject::TryMigrateInstance(Handle<JSObject> object) {
  if (FLAG_trace_migration) {
    PrintF("migrating instance (no new maps) %p (%p)\n",
           static_cast<void*>(*object),
           static_cast<void*>(object->map()));
  }
  CALL_HEAP_FUNCTION(
      object->GetIsolate(),
      object->MigrateInstance(),
      Object);
}


Handle<Map> Map::GeneralizeRepresentation(Handle<Map> map,
                                          int modify_index,
                                          Representation representation) {
  CALL_HEAP_FUNCTION(
      map->GetIsolate(),
      map->GeneralizeRepresentation(modify_index, representation),
      Map);
}


MaybeObject* JSObject::SetPropertyForResult(LookupResult* lookup,
                                            Name* name_raw,
                                            Object* value_raw,
                                            PropertyAttributes attributes,
                                            StrictModeFlag strict_mode,
                                            StoreFromKeyed store_mode) {
  Heap* heap = GetHeap();
  Isolate* isolate = heap->isolate();
  // Make sure that the top context does not change when doing callbacks or
  // interceptor calls.
  AssertNoContextChange ncc;

  // Optimization for 2-byte strings often used as keys in a decompression
  // dictionary.  We internalize these short keys to avoid constantly
  // reallocating them.
  if (name_raw->IsString() && !name_raw->IsInternalizedString() &&
      String::cast(name_raw)->length() <= 2) {
    Object* internalized_version;
    { MaybeObject* maybe_string_version =
        heap->InternalizeString(String::cast(name_raw));
      if (maybe_string_version->ToObject(&internalized_version)) {
        name_raw = String::cast(internalized_version);
      }
    }
  }

  // Check access rights if needed.
  if (IsAccessCheckNeeded()) {
    if (!isolate->MayNamedAccess(this, name_raw, v8::ACCESS_SET)) {
      return SetPropertyWithFailedAccessCheck(
          lookup, name_raw, value_raw, true, strict_mode);
    }
  }

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return value_raw;
    ASSERT(proto->IsJSGlobalObject());
    return JSObject::cast(proto)->SetPropertyForResult(
        lookup, name_raw, value_raw, attributes, strict_mode, store_mode);
  }

  ASSERT(!lookup->IsFound() || lookup->holder() == this ||
         lookup->holder()->map()->is_hidden_prototype());

  // From this point on everything needs to be handlified, because
  // SetPropertyViaPrototypes might call back into JavaScript.
  HandleScope scope(isolate);
  Handle<JSObject> self(this);
  Handle<Name> name(name_raw);
  Handle<Object> value(value_raw, isolate);

  if (!lookup->IsProperty() && !self->IsJSContextExtensionObject()) {
    bool done = false;
    MaybeObject* result_object = self->SetPropertyViaPrototypes(
        *name, *value, attributes, strict_mode, &done);
    if (done) return result_object;
  }

  if (!lookup->IsFound()) {
    // Neither properties nor transitions found.
    return self->AddProperty(
        *name, *value, attributes, strict_mode, store_mode);
  }

  if (lookup->IsProperty() && lookup->IsReadOnly()) {
    if (strict_mode == kStrictMode) {
      Handle<Object> args[] = { name, self };
      return isolate->Throw(*isolate->factory()->NewTypeError(
          "strict_read_only_property", HandleVector(args, ARRAY_SIZE(args))));
    } else {
      return *value;
    }
  }

  Handle<Object> old_value(heap->the_hole_value(), isolate);
  if (FLAG_harmony_observation &&
      map()->is_observed() && lookup->IsDataProperty()) {
    old_value = Object::GetProperty(self, name);
  }

  // This is a real property that is not read-only, or it is a
  // transition or null descriptor and there are no setters in the prototypes.
  MaybeObject* result = *value;
  switch (lookup->type()) {
    case NORMAL:
      result = lookup->holder()->SetNormalizedProperty(lookup, *value);
      break;
    case FIELD: {
      Representation representation = lookup->representation();
      if (!value->FitsRepresentation(representation)) {
        MaybeObject* maybe_failure =
            lookup->holder()->GeneralizeFieldRepresentation(
                lookup->GetDescriptorIndex(), value->OptimalRepresentation());
        if (maybe_failure->IsFailure()) return maybe_failure;
        DescriptorArray* desc = lookup->holder()->map()->instance_descriptors();
        int descriptor = lookup->GetDescriptorIndex();
        representation = desc->GetDetails(descriptor).representation();
      }
      if (FLAG_track_double_fields && representation.IsDouble()) {
        HeapNumber* storage =
            HeapNumber::cast(lookup->holder()->RawFastPropertyAt(
                lookup->GetFieldIndex().field_index()));
        storage->set_value(value->Number());
        result = *value;
        break;
      }
      lookup->holder()->FastPropertyAtPut(
          lookup->GetFieldIndex().field_index(), *value);
      result = *value;
      break;
    }
    case CONSTANT:
      // Only replace the constant if necessary.
      if (*value == lookup->GetConstant()) return *value;
      // Preserve the attributes of this existing property.
      attributes = lookup->GetAttributes();
      result = lookup->holder()->ConvertDescriptorToField(
          *name, *value, attributes);
      break;
    case CALLBACKS: {
      Object* callback_object = lookup->GetCallbackObject();
      return self->SetPropertyWithCallback(
          callback_object, *name, *value, lookup->holder(), strict_mode);
    }
    case INTERCEPTOR:
      result = lookup->holder()->SetPropertyWithInterceptor(
          *name, *value, attributes, strict_mode);
      break;
    case TRANSITION: {
      Map* transition_map = lookup->GetTransitionTarget();
      int descriptor = transition_map->LastAdded();

      DescriptorArray* descriptors = transition_map->instance_descriptors();
      PropertyDetails details = descriptors->GetDetails(descriptor);

      if (details.type() == FIELD) {
        if (attributes == details.attributes()) {
          Representation representation = details.representation();
          if (!value->FitsRepresentation(representation)) {
            MaybeObject* maybe_map = transition_map->GeneralizeRepresentation(
                descriptor, value->OptimalRepresentation());
            if (!maybe_map->To(&transition_map)) return maybe_map;
            Object* back = transition_map->GetBackPointer();
            if (back->IsMap()) {
              MaybeObject* maybe_failure =
                  lookup->holder()->MigrateToMap(Map::cast(back));
              if (maybe_failure->IsFailure()) return maybe_failure;
            }
            descriptors = transition_map->instance_descriptors();
            representation =
                descriptors->GetDetails(descriptor).representation();
          }
          int field_index = descriptors->GetFieldIndex(descriptor);
          result = lookup->holder()->AddFastPropertyUsingMap(
              transition_map, *name, *value, field_index, representation);
        } else {
          result = lookup->holder()->ConvertDescriptorToField(
              *name, *value, attributes);
        }
      } else if (details.type() == CALLBACKS) {
        result = lookup->holder()->ConvertDescriptorToField(
            *name, *value, attributes);
      } else {
        ASSERT(details.type() == CONSTANT);

        Object* constant = descriptors->GetValue(descriptor);
        if (constant == *value) {
          // If the same constant function is being added we can simply
          // transition to the target map.
          lookup->holder()->set_map(transition_map);
          result = constant;
        } else {
          // Otherwise, replace with a map transition to a new map with a FIELD,
          // even if the value is a constant function.
          result = lookup->holder()->ConvertTransitionToMapTransition(
              lookup->GetTransitionIndex(), *name, *value, attributes);
        }
      }
      break;
    }
    case HANDLER:
    case NONEXISTENT:
      UNREACHABLE();
  }

  Handle<Object> hresult;
  if (!result->ToHandle(&hresult, isolate)) return result;

  if (FLAG_harmony_observation && self->map()->is_observed()) {
    if (lookup->IsTransition()) {
      EnqueueChangeRecord(self, "new", name, old_value);
    } else {
      LookupResult new_lookup(isolate);
      self->LocalLookup(*name, &new_lookup, true);
      if (new_lookup.IsDataProperty()) {
        Handle<Object> new_value = Object::GetProperty(self, name);
        if (!new_value->SameValue(*old_value)) {
          EnqueueChangeRecord(self, "updated", name, old_value);
        }
      }
    }
  }

  return *hresult;
}


// Set a real local property, even if it is READ_ONLY.  If the property is not
// present, add it with attributes NONE.  This code is an exact clone of
// SetProperty, with the check for IsReadOnly and the check for a
// callback setter removed.  The two lines looking up the LookupResult
// result are also added.  If one of the functions is changed, the other
// should be.
// Note that this method cannot be used to set the prototype of a function
// because ConvertDescriptorToField() which is called in "case CALLBACKS:"
// doesn't handle function prototypes correctly.
Handle<Object> JSObject::SetLocalPropertyIgnoreAttributes(
    Handle<JSObject> object,
    Handle<Name> key,
    Handle<Object> value,
    PropertyAttributes attributes,
    ValueType value_type,
    StoreMode mode) {
  CALL_HEAP_FUNCTION(
    object->GetIsolate(),
    object->SetLocalPropertyIgnoreAttributes(
        *key, *value, attributes, value_type, mode),
    Object);
}


MaybeObject* JSObject::SetLocalPropertyIgnoreAttributes(
    Name* name_raw,
    Object* value_raw,
    PropertyAttributes attributes,
    ValueType value_type,
    StoreMode mode) {
  // Make sure that the top context does not change when doing callbacks or
  // interceptor calls.
  AssertNoContextChange ncc;
  Isolate* isolate = GetIsolate();
  LookupResult lookup(isolate);
  LocalLookup(name_raw, &lookup, true);
  if (!lookup.IsFound()) map()->LookupTransition(this, name_raw, &lookup);
  // Check access rights if needed.
  if (IsAccessCheckNeeded()) {
    if (!isolate->MayNamedAccess(this, name_raw, v8::ACCESS_SET)) {
      return SetPropertyWithFailedAccessCheck(&lookup,
                                              name_raw,
                                              value_raw,
                                              false,
                                              kNonStrictMode);
    }
  }

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return value_raw;
    ASSERT(proto->IsJSGlobalObject());
    return JSObject::cast(proto)->SetLocalPropertyIgnoreAttributes(
        name_raw,
        value_raw,
        attributes,
        value_type,
        mode);
  }

  // Check for accessor in prototype chain removed here in clone.
  if (!lookup.IsFound()) {
    // Neither properties nor transitions found.
    return AddProperty(
        name_raw, value_raw, attributes, kNonStrictMode,
        MAY_BE_STORE_FROM_KEYED, PERFORM_EXTENSIBILITY_CHECK, value_type, mode);
  }

  // From this point on everything needs to be handlified.
  HandleScope scope(isolate);
  Handle<JSObject> self(this);
  Handle<Name> name(name_raw);
  Handle<Object> value(value_raw, isolate);

  Handle<Object> old_value(isolate->heap()->the_hole_value(), isolate);
  PropertyAttributes old_attributes = ABSENT;
  bool is_observed = FLAG_harmony_observation && self->map()->is_observed();
  if (is_observed && lookup.IsProperty()) {
    if (lookup.IsDataProperty()) old_value = Object::GetProperty(self, name);
    old_attributes = lookup.GetAttributes();
  }

  // Check of IsReadOnly removed from here in clone.
  MaybeObject* result = *value;
  switch (lookup.type()) {
    case NORMAL: {
      PropertyDetails details = PropertyDetails(attributes, NORMAL, 0);
      result = self->SetNormalizedProperty(*name, *value, details);
      break;
    }
    case FIELD: {
      Representation representation = lookup.representation();
      Representation value_representation =
          value->OptimalRepresentation(value_type);
      if (value_representation.IsNone()) break;
      if (!value_representation.fits_into(representation)) {
        MaybeObject* maybe_failure = self->GeneralizeFieldRepresentation(
            lookup.GetDescriptorIndex(), value_representation);
        if (maybe_failure->IsFailure()) return maybe_failure;
        DescriptorArray* desc = self->map()->instance_descriptors();
        int descriptor = lookup.GetDescriptorIndex();
        representation = desc->GetDetails(descriptor).representation();
      }
      if (FLAG_track_double_fields && representation.IsDouble()) {
        HeapNumber* storage =
            HeapNumber::cast(self->RawFastPropertyAt(
                lookup.GetFieldIndex().field_index()));
        storage->set_value(value->Number());
        result = *value;
        break;
      }
      self->FastPropertyAtPut(lookup.GetFieldIndex().field_index(), *value);
      result = *value;
      break;
    }
    case CONSTANT:
      // Only replace the function if necessary.
      if (*value != lookup.GetConstant()) {
        // Preserve the attributes of this existing property.
        attributes = lookup.GetAttributes();
        result = self->ConvertDescriptorToField(*name, *value, attributes);
      }
      break;
    case CALLBACKS:
    case INTERCEPTOR:
      // Override callback in clone
      result = self->ConvertDescriptorToField(*name, *value, attributes);
      break;
    case TRANSITION: {
      Map* transition_map = lookup.GetTransitionTarget();
      int descriptor = transition_map->LastAdded();

      DescriptorArray* descriptors = transition_map->instance_descriptors();
      PropertyDetails details = descriptors->GetDetails(descriptor);

      if (details.type() == FIELD) {
        if (attributes == details.attributes()) {
          Representation representation = details.representation();
          Representation value_representation =
              value->OptimalRepresentation(value_type);
          if (!value_representation.fits_into(representation)) {
            MaybeObject* maybe_map = transition_map->GeneralizeRepresentation(
                descriptor, value_representation);
            if (!maybe_map->To(&transition_map)) return maybe_map;
            Object* back = transition_map->GetBackPointer();
            if (back->IsMap()) {
              MaybeObject* maybe_failure = self->MigrateToMap(Map::cast(back));
              if (maybe_failure->IsFailure()) return maybe_failure;
            }
            descriptors = transition_map->instance_descriptors();
            representation =
                descriptors->GetDetails(descriptor).representation();
          }
          int field_index = descriptors->GetFieldIndex(descriptor);
          result = self->AddFastPropertyUsingMap(
              transition_map, *name, *value, field_index, representation);
        } else {
          result = self->ConvertDescriptorToField(*name, *value, attributes);
        }
      } else if (details.type() == CALLBACKS) {
        result = self->ConvertDescriptorToField(*name, *value, attributes);
      } else {
        ASSERT(details.type() == CONSTANT);

        // Replace transition to CONSTANT FUNCTION with a map transition to a
        // new map with a FIELD, even if the value is a function.
        result = self->ConvertTransitionToMapTransition(
            lookup.GetTransitionIndex(), *name, *value, attributes);
      }
      break;
    }
    case HANDLER:
    case NONEXISTENT:
      UNREACHABLE();
  }

  Handle<Object> hresult;
  if (!result->ToHandle(&hresult, isolate)) return result;

  if (is_observed) {
    if (lookup.IsTransition()) {
      EnqueueChangeRecord(self, "new", name, old_value);
    } else if (old_value->IsTheHole()) {
      EnqueueChangeRecord(self, "reconfigured", name, old_value);
    } else {
      LookupResult new_lookup(isolate);
      self->LocalLookup(*name, &new_lookup, true);
      bool value_changed = false;
      if (new_lookup.IsDataProperty()) {
        Handle<Object> new_value = Object::GetProperty(self, name);
        value_changed = !old_value->SameValue(*new_value);
      }
      if (new_lookup.GetAttributes() != old_attributes) {
        if (!value_changed) old_value = isolate->factory()->the_hole_value();
        EnqueueChangeRecord(self, "reconfigured", name, old_value);
      } else if (value_changed) {
        EnqueueChangeRecord(self, "updated", name, old_value);
      }
    }
  }

  return *hresult;
}


PropertyAttributes JSObject::GetPropertyAttributePostInterceptor(
      JSObject* receiver,
      Name* name,
      bool continue_search) {
  // Check local property, ignore interceptor.
  LookupResult result(GetIsolate());
  LocalLookupRealNamedProperty(name, &result);
  if (result.IsFound()) return result.GetAttributes();

  if (continue_search) {
    // Continue searching via the prototype chain.
    Object* pt = GetPrototype();
    if (!pt->IsNull()) {
      return JSObject::cast(pt)->
        GetPropertyAttributeWithReceiver(receiver, name);
    }
  }
  return ABSENT;
}


PropertyAttributes JSObject::GetPropertyAttributeWithInterceptor(
      JSObject* receiver,
      Name* name,
      bool continue_search) {
  // TODO(rossberg): Support symbols in the API.
  if (name->IsSymbol()) return ABSENT;

  Isolate* isolate = GetIsolate();

  // Make sure that the top context does not change when doing
  // callbacks or interceptor calls.
  AssertNoContextChange ncc;

  HandleScope scope(isolate);
  Handle<InterceptorInfo> interceptor(GetNamedInterceptor());
  Handle<JSObject> receiver_handle(receiver);
  Handle<JSObject> holder_handle(this);
  Handle<String> name_handle(String::cast(name));
  PropertyCallbackArguments args(isolate, interceptor->data(), receiver, this);
  if (!interceptor->query()->IsUndefined()) {
    v8::NamedPropertyQuery query =
        v8::ToCData<v8::NamedPropertyQuery>(interceptor->query());
    LOG(isolate,
        ApiNamedPropertyAccess("interceptor-named-has", *holder_handle, name));
    v8::Handle<v8::Integer> result =
        args.Call(query, v8::Utils::ToLocal(name_handle));
    if (!result.IsEmpty()) {
      ASSERT(result->IsInt32());
      return static_cast<PropertyAttributes>(result->Int32Value());
    }
  } else if (!interceptor->getter()->IsUndefined()) {
    v8::NamedPropertyGetter getter =
        v8::ToCData<v8::NamedPropertyGetter>(interceptor->getter());
    LOG(isolate,
        ApiNamedPropertyAccess("interceptor-named-get-has", this, name));
    v8::Handle<v8::Value> result =
        args.Call(getter, v8::Utils::ToLocal(name_handle));
    if (!result.IsEmpty()) return DONT_ENUM;
  }
  return holder_handle->GetPropertyAttributePostInterceptor(*receiver_handle,
                                                            *name_handle,
                                                            continue_search);
}


PropertyAttributes JSReceiver::GetPropertyAttributeWithReceiver(
      JSReceiver* receiver,
      Name* key) {
  uint32_t index = 0;
  if (IsJSObject() && key->AsArrayIndex(&index)) {
    return JSObject::cast(this)->GetElementAttributeWithReceiver(
        receiver, index, true);
  }
  // Named property.
  LookupResult lookup(GetIsolate());
  Lookup(key, &lookup);
  return GetPropertyAttributeForResult(receiver, &lookup, key, true);
}


PropertyAttributes JSReceiver::GetPropertyAttributeForResult(
    JSReceiver* receiver,
    LookupResult* lookup,
    Name* name,
    bool continue_search) {
  // Check access rights if needed.
  if (IsAccessCheckNeeded()) {
    JSObject* this_obj = JSObject::cast(this);
    Heap* heap = GetHeap();
    if (!heap->isolate()->MayNamedAccess(this_obj, name, v8::ACCESS_HAS)) {
      return this_obj->GetPropertyAttributeWithFailedAccessCheck(
          receiver, lookup, name, continue_search);
    }
  }
  if (lookup->IsFound()) {
    switch (lookup->type()) {
      case NORMAL:  // fall through
      case FIELD:
      case CONSTANT:
      case CALLBACKS:
        return lookup->GetAttributes();
      case HANDLER: {
        return JSProxy::cast(lookup->proxy())->GetPropertyAttributeWithHandler(
            receiver, name);
      }
      case INTERCEPTOR:
        return lookup->holder()->GetPropertyAttributeWithInterceptor(
            JSObject::cast(receiver), name, continue_search);
      case TRANSITION:
      case NONEXISTENT:
        UNREACHABLE();
    }
  }
  return ABSENT;
}


PropertyAttributes JSReceiver::GetLocalPropertyAttribute(Name* name) {
  // Check whether the name is an array index.
  uint32_t index = 0;
  if (IsJSObject() && name->AsArrayIndex(&index)) {
    return GetLocalElementAttribute(index);
  }
  // Named property.
  LookupResult lookup(GetIsolate());
  LocalLookup(name, &lookup, true);
  return GetPropertyAttributeForResult(this, &lookup, name, false);
}


PropertyAttributes JSObject::GetElementAttributeWithReceiver(
    JSReceiver* receiver, uint32_t index, bool continue_search) {
  Isolate* isolate = GetIsolate();

  // Check access rights if needed.
  if (IsAccessCheckNeeded()) {
    if (!isolate->MayIndexedAccess(this, index, v8::ACCESS_HAS)) {
      isolate->ReportFailedAccessCheck(this, v8::ACCESS_HAS);
      return ABSENT;
    }
  }

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return ABSENT;
    ASSERT(proto->IsJSGlobalObject());
    return JSObject::cast(proto)->GetElementAttributeWithReceiver(
        receiver, index, continue_search);
  }

  // Check for lookup interceptor except when bootstrapping.
  if (HasIndexedInterceptor() && !isolate->bootstrapper()->IsActive()) {
    return GetElementAttributeWithInterceptor(receiver, index, continue_search);
  }

  return GetElementAttributeWithoutInterceptor(
      receiver, index, continue_search);
}


PropertyAttributes JSObject::GetElementAttributeWithInterceptor(
    JSReceiver* receiver, uint32_t index, bool continue_search) {
  Isolate* isolate = GetIsolate();
  // Make sure that the top context does not change when doing
  // callbacks or interceptor calls.
  AssertNoContextChange ncc;
  HandleScope scope(isolate);
  Handle<InterceptorInfo> interceptor(GetIndexedInterceptor());
  Handle<JSReceiver> hreceiver(receiver);
  Handle<JSObject> holder(this);
  PropertyCallbackArguments args(isolate, interceptor->data(), receiver, this);
  if (!interceptor->query()->IsUndefined()) {
    v8::IndexedPropertyQuery query =
        v8::ToCData<v8::IndexedPropertyQuery>(interceptor->query());
    LOG(isolate,
        ApiIndexedPropertyAccess("interceptor-indexed-has", this, index));
    v8::Handle<v8::Integer> result = args.Call(query, index);
    if (!result.IsEmpty())
      return static_cast<PropertyAttributes>(result->Int32Value());
  } else if (!interceptor->getter()->IsUndefined()) {
    v8::IndexedPropertyGetter getter =
        v8::ToCData<v8::IndexedPropertyGetter>(interceptor->getter());
    LOG(isolate,
        ApiIndexedPropertyAccess("interceptor-indexed-get-has", this, index));
    v8::Handle<v8::Value> result = args.Call(getter, index);
    if (!result.IsEmpty()) return NONE;
  }

  return holder->GetElementAttributeWithoutInterceptor(
      *hreceiver, index, continue_search);
}


PropertyAttributes JSObject::GetElementAttributeWithoutInterceptor(
      JSReceiver* receiver, uint32_t index, bool continue_search) {
  PropertyAttributes attr = GetElementsAccessor()->GetAttributes(
      receiver, this, index);
  if (attr != ABSENT) return attr;

  // Handle [] on String objects.
  if (IsStringObjectWithCharacterAt(index)) {
    return static_cast<PropertyAttributes>(READ_ONLY | DONT_DELETE);
  }

  if (!continue_search) return ABSENT;

  Object* pt = GetPrototype();
  if (pt->IsJSProxy()) {
    // We need to follow the spec and simulate a call to [[GetOwnProperty]].
    return JSProxy::cast(pt)->GetElementAttributeWithHandler(receiver, index);
  }
  if (pt->IsNull()) return ABSENT;
  return JSObject::cast(pt)->GetElementAttributeWithReceiver(
      receiver, index, true);
}


MaybeObject* NormalizedMapCache::Get(JSObject* obj,
                                     PropertyNormalizationMode mode) {
  Isolate* isolate = obj->GetIsolate();
  Map* fast = obj->map();
  int index = fast->Hash() % kEntries;
  Object* result = get(index);
  if (result->IsMap() &&
      Map::cast(result)->EquivalentToForNormalization(fast, mode)) {
#ifdef VERIFY_HEAP
    if (FLAG_verify_heap) {
      Map::cast(result)->SharedMapVerify();
    }
#endif
#ifdef DEBUG
    if (FLAG_enable_slow_asserts) {
      // The cached map should match newly created normalized map bit-by-bit,
      // except for the code cache, which can contain some ics which can be
      // applied to the shared map.
      Object* fresh;
      MaybeObject* maybe_fresh =
          fast->CopyNormalized(mode, SHARED_NORMALIZED_MAP);
      if (maybe_fresh->ToObject(&fresh)) {
        ASSERT(memcmp(Map::cast(fresh)->address(),
                      Map::cast(result)->address(),
                      Map::kCodeCacheOffset) == 0);
        STATIC_ASSERT(Map::kDependentCodeOffset ==
                      Map::kCodeCacheOffset + kPointerSize);
        int offset = Map::kDependentCodeOffset + kPointerSize;
        ASSERT(memcmp(Map::cast(fresh)->address() + offset,
                      Map::cast(result)->address() + offset,
                      Map::kSize - offset) == 0);
      }
    }
#endif
    return result;
  }

  { MaybeObject* maybe_result =
        fast->CopyNormalized(mode, SHARED_NORMALIZED_MAP);
    if (!maybe_result->ToObject(&result)) return maybe_result;
  }
  ASSERT(Map::cast(result)->is_dictionary_map());
  set(index, result);
  isolate->counters()->normalized_maps()->Increment();

  return result;
}


void NormalizedMapCache::Clear() {
  int entries = length();
  for (int i = 0; i != entries; i++) {
    set_undefined(i);
  }
}


void JSObject::UpdateMapCodeCache(Handle<JSObject> object,
                                  Handle<Name> name,
                                  Handle<Code> code) {
  Isolate* isolate = object->GetIsolate();
  CALL_HEAP_FUNCTION_VOID(isolate,
                          object->UpdateMapCodeCache(*name, *code));
}


MaybeObject* JSObject::UpdateMapCodeCache(Name* name, Code* code) {
  if (map()->is_shared()) {
    // Fast case maps are never marked as shared.
    ASSERT(!HasFastProperties());
    // Replace the map with an identical copy that can be safely modified.
    Object* obj;
    { MaybeObject* maybe_obj = map()->CopyNormalized(KEEP_INOBJECT_PROPERTIES,
                                                     UNIQUE_NORMALIZED_MAP);
      if (!maybe_obj->ToObject(&obj)) return maybe_obj;
    }
    GetIsolate()->counters()->normalized_maps()->Increment();

    set_map(Map::cast(obj));
  }
  return map()->UpdateCodeCache(name, code);
}


void JSObject::NormalizeProperties(Handle<JSObject> object,
                                   PropertyNormalizationMode mode,
                                   int expected_additional_properties) {
  CALL_HEAP_FUNCTION_VOID(object->GetIsolate(),
                          object->NormalizeProperties(
                              mode, expected_additional_properties));
}


MaybeObject* JSObject::NormalizeProperties(PropertyNormalizationMode mode,
                                           int expected_additional_properties) {
  if (!HasFastProperties()) return this;

  // The global object is always normalized.
  ASSERT(!IsGlobalObject());
  // JSGlobalProxy must never be normalized
  ASSERT(!IsJSGlobalProxy());

  Map* map_of_this = map();

  // Allocate new content.
  int real_size = map_of_this->NumberOfOwnDescriptors();
  int property_count = real_size;
  if (expected_additional_properties > 0) {
    property_count += expected_additional_properties;
  } else {
    property_count += 2;  // Make space for two more properties.
  }
  NameDictionary* dictionary;
  MaybeObject* maybe_dictionary =
      NameDictionary::Allocate(GetHeap(), property_count);
  if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;

  DescriptorArray* descs = map_of_this->instance_descriptors();
  for (int i = 0; i < real_size; i++) {
    PropertyDetails details = descs->GetDetails(i);
    switch (details.type()) {
      case CONSTANT: {
        PropertyDetails d = PropertyDetails(
            details.attributes(), NORMAL, i + 1);
        Object* value = descs->GetConstant(i);
        MaybeObject* maybe_dictionary =
            dictionary->Add(descs->GetKey(i), value, d);
        if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
        break;
      }
      case FIELD: {
        PropertyDetails d =
            PropertyDetails(details.attributes(), NORMAL, i + 1);
        Object* value = RawFastPropertyAt(descs->GetFieldIndex(i));
        MaybeObject* maybe_dictionary =
            dictionary->Add(descs->GetKey(i), value, d);
        if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
        break;
      }
      case CALLBACKS: {
        Object* value = descs->GetCallbacksObject(i);
        PropertyDetails d = PropertyDetails(
            details.attributes(), CALLBACKS, i + 1);
        MaybeObject* maybe_dictionary =
            dictionary->Add(descs->GetKey(i), value, d);
        if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
        break;
      }
      case INTERCEPTOR:
        break;
      case HANDLER:
      case NORMAL:
      case TRANSITION:
      case NONEXISTENT:
        UNREACHABLE();
        break;
    }
  }

  Heap* current_heap = GetHeap();

  // Copy the next enumeration index from instance descriptor.
  dictionary->SetNextEnumerationIndex(real_size + 1);

  Map* new_map;
  MaybeObject* maybe_map =
      current_heap->isolate()->context()->native_context()->
      normalized_map_cache()->Get(this, mode);
  if (!maybe_map->To(&new_map)) return maybe_map;
  ASSERT(new_map->is_dictionary_map());

  // We have now successfully allocated all the necessary objects.
  // Changes can now be made with the guarantee that all of them take effect.

  // Resize the object in the heap if necessary.
  int new_instance_size = new_map->instance_size();
  int instance_size_delta = map_of_this->instance_size() - new_instance_size;
  ASSERT(instance_size_delta >= 0);
  current_heap->CreateFillerObjectAt(this->address() + new_instance_size,
                                     instance_size_delta);
  if (Marking::IsBlack(Marking::MarkBitFrom(this))) {
    MemoryChunk::IncrementLiveBytesFromMutator(this->address(),
                                               -instance_size_delta);
  }

  set_map(new_map);
  map_of_this->NotifyLeafMapLayoutChange();

  set_properties(dictionary);

  current_heap->isolate()->counters()->props_to_dictionary()->Increment();

#ifdef DEBUG
  if (FLAG_trace_normalization) {
    PrintF("Object properties have been normalized:\n");
    Print();
  }
#endif
  return this;
}


void JSObject::TransformToFastProperties(Handle<JSObject> object,
                                         int unused_property_fields) {
  CALL_HEAP_FUNCTION_VOID(
      object->GetIsolate(),
      object->TransformToFastProperties(unused_property_fields));
}


MaybeObject* JSObject::TransformToFastProperties(int unused_property_fields) {
  if (HasFastProperties()) return this;
  ASSERT(!IsGlobalObject());
  return property_dictionary()->
      TransformPropertiesToFastFor(this, unused_property_fields);
}


static MUST_USE_RESULT MaybeObject* CopyFastElementsToDictionary(
    Isolate* isolate,
    FixedArrayBase* array,
    int length,
    SeededNumberDictionary* dictionary) {
  Heap* heap = isolate->heap();
  bool has_double_elements = array->IsFixedDoubleArray();
  for (int i = 0; i < length; i++) {
    Object* value = NULL;
    if (has_double_elements) {
      FixedDoubleArray* double_array = FixedDoubleArray::cast(array);
      if (double_array->is_the_hole(i)) {
        value = isolate->heap()->the_hole_value();
      } else {
        // Objects must be allocated in the old object space, since the
        // overall number of HeapNumbers needed for the conversion might
        // exceed the capacity of new space, and we would fail repeatedly
        // trying to convert the FixedDoubleArray.
        MaybeObject* maybe_value_object =
            heap->AllocateHeapNumber(double_array->get_scalar(i), TENURED);
        if (!maybe_value_object->ToObject(&value)) return maybe_value_object;
      }
    } else {
      value = FixedArray::cast(array)->get(i);
    }
    if (!value->IsTheHole()) {
      PropertyDetails details = PropertyDetails(NONE, NORMAL, 0);
      MaybeObject* maybe_result =
          dictionary->AddNumberEntry(i, value, details);
      if (!maybe_result->To(&dictionary)) return maybe_result;
    }
  }
  return dictionary;
}


Handle<SeededNumberDictionary> JSObject::NormalizeElements(
    Handle<JSObject> object) {
  CALL_HEAP_FUNCTION(object->GetIsolate(),
                     object->NormalizeElements(),
                     SeededNumberDictionary);
}


MaybeObject* JSObject::NormalizeElements() {
  ASSERT(!HasExternalArrayElements());

  // Find the backing store.
  FixedArrayBase* array = FixedArrayBase::cast(elements());
  Map* old_map = array->map();
  bool is_arguments =
      (old_map == old_map->GetHeap()->non_strict_arguments_elements_map());
  if (is_arguments) {
    array = FixedArrayBase::cast(FixedArray::cast(array)->get(1));
  }
  if (array->IsDictionary()) return array;

  ASSERT(HasFastSmiOrObjectElements() ||
         HasFastDoubleElements() ||
         HasFastArgumentsElements());
  // Compute the effective length and allocate a new backing store.
  int length = IsJSArray()
      ? Smi::cast(JSArray::cast(this)->length())->value()
      : array->length();
  int old_capacity = 0;
  int used_elements = 0;
  GetElementsCapacityAndUsage(&old_capacity, &used_elements);
  SeededNumberDictionary* dictionary;
  MaybeObject* maybe_dictionary =
      SeededNumberDictionary::Allocate(GetHeap(), used_elements);
  if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;

  maybe_dictionary = CopyFastElementsToDictionary(
      GetIsolate(), array, length, dictionary);
  if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;

  // Switch to using the dictionary as the backing storage for elements.
  if (is_arguments) {
    FixedArray::cast(elements())->set(1, dictionary);
  } else {
    // Set the new map first to satify the elements type assert in
    // set_elements().
    Map* new_map;
    MaybeObject* maybe = GetElementsTransitionMap(GetIsolate(),
                                                  DICTIONARY_ELEMENTS);
    if (!maybe->To(&new_map)) return maybe;
    set_map(new_map);
    set_elements(dictionary);
  }

  old_map->GetHeap()->isolate()->counters()->elements_to_dictionary()->
      Increment();

#ifdef DEBUG
  if (FLAG_trace_normalization) {
    PrintF("Object elements have been normalized:\n");
    Print();
  }
#endif

  ASSERT(HasDictionaryElements() || HasDictionaryArgumentsElements());
  return dictionary;
}


Smi* JSReceiver::GenerateIdentityHash() {
  Isolate* isolate = GetIsolate();

  int hash_value;
  int attempts = 0;
  do {
    // Generate a random 32-bit hash value but limit range to fit
    // within a smi.
    hash_value = V8::RandomPrivate(isolate) & Smi::kMaxValue;
    attempts++;
  } while (hash_value == 0 && attempts < 30);
  hash_value = hash_value != 0 ? hash_value : 1;  // never return 0

  return Smi::FromInt(hash_value);
}


MaybeObject* JSObject::SetIdentityHash(Smi* hash, CreationFlag flag) {
  MaybeObject* maybe = SetHiddenProperty(GetHeap()->identity_hash_string(),
                                         hash);
  if (maybe->IsFailure()) return maybe;
  return this;
}


int JSObject::GetIdentityHash(Handle<JSObject> obj) {
  CALL_AND_RETRY_OR_DIE(obj->GetIsolate(),
                        obj->GetIdentityHash(ALLOW_CREATION),
                        return Smi::cast(__object__)->value(),
                        return 0);
}


MaybeObject* JSObject::GetIdentityHash(CreationFlag flag) {
  Object* stored_value = GetHiddenProperty(GetHeap()->identity_hash_string());
  if (stored_value->IsSmi()) return stored_value;

  // Do not generate permanent identity hash code if not requested.
  if (flag == OMIT_CREATION) return GetHeap()->undefined_value();

  Smi* hash = GenerateIdentityHash();
  MaybeObject* result = SetHiddenProperty(GetHeap()->identity_hash_string(),
                                          hash);
  if (result->IsFailure()) return result;
  if (result->ToObjectUnchecked()->IsUndefined()) {
    // Trying to get hash of detached proxy.
    return Smi::FromInt(0);
  }
  return hash;
}


MaybeObject* JSProxy::GetIdentityHash(CreationFlag flag) {
  Object* hash = this->hash();
  if (!hash->IsSmi() && flag == ALLOW_CREATION) {
    hash = GenerateIdentityHash();
    set_hash(hash);
  }
  return hash;
}


Object* JSObject::GetHiddenProperty(Name* key) {
  ASSERT(key->IsUniqueName());
  if (IsJSGlobalProxy()) {
    // For a proxy, use the prototype as target object.
    Object* proxy_parent = GetPrototype();
    // If the proxy is detached, return undefined.
    if (proxy_parent->IsNull()) return GetHeap()->the_hole_value();
    ASSERT(proxy_parent->IsJSGlobalObject());
    return JSObject::cast(proxy_parent)->GetHiddenProperty(key);
  }
  ASSERT(!IsJSGlobalProxy());
  MaybeObject* hidden_lookup =
      GetHiddenPropertiesHashTable(ONLY_RETURN_INLINE_VALUE);
  Object* inline_value = hidden_lookup->ToObjectUnchecked();

  if (inline_value->IsSmi()) {
    // Handle inline-stored identity hash.
    if (key == GetHeap()->identity_hash_string()) {
      return inline_value;
    } else {
      return GetHeap()->the_hole_value();
    }
  }

  if (inline_value->IsUndefined()) return GetHeap()->the_hole_value();

  ObjectHashTable* hashtable = ObjectHashTable::cast(inline_value);
  Object* entry = hashtable->Lookup(key);
  return entry;
}


Handle<Object> JSObject::SetHiddenProperty(Handle<JSObject> obj,
                                           Handle<Name> key,
                                           Handle<Object> value) {
  CALL_HEAP_FUNCTION(obj->GetIsolate(),
                     obj->SetHiddenProperty(*key, *value),
                     Object);
}


MaybeObject* JSObject::SetHiddenProperty(Name* key, Object* value) {
  ASSERT(key->IsUniqueName());
  if (IsJSGlobalProxy()) {
    // For a proxy, use the prototype as target object.
    Object* proxy_parent = GetPrototype();
    // If the proxy is detached, return undefined.
    if (proxy_parent->IsNull()) return GetHeap()->undefined_value();
    ASSERT(proxy_parent->IsJSGlobalObject());
    return JSObject::cast(proxy_parent)->SetHiddenProperty(key, value);
  }
  ASSERT(!IsJSGlobalProxy());
  MaybeObject* hidden_lookup =
      GetHiddenPropertiesHashTable(ONLY_RETURN_INLINE_VALUE);
  Object* inline_value = hidden_lookup->ToObjectUnchecked();

  // If there is no backing store yet, store the identity hash inline.
  if (value->IsSmi() &&
      key == GetHeap()->identity_hash_string() &&
      (inline_value->IsUndefined() || inline_value->IsSmi())) {
    return SetHiddenPropertiesHashTable(value);
  }

  hidden_lookup = GetHiddenPropertiesHashTable(CREATE_NEW_IF_ABSENT);
  ObjectHashTable* hashtable;
  if (!hidden_lookup->To(&hashtable)) return hidden_lookup;

  // If it was found, check if the key is already in the dictionary.
  MaybeObject* insert_result = hashtable->Put(key, value);
  ObjectHashTable* new_table;
  if (!insert_result->To(&new_table)) return insert_result;
  if (new_table != hashtable) {
    // If adding the key expanded the dictionary (i.e., Add returned a new
    // dictionary), store it back to the object.
    MaybeObject* store_result = SetHiddenPropertiesHashTable(new_table);
    if (store_result->IsFailure()) return store_result;
  }
  // Return this to mark success.
  return this;
}


void JSObject::DeleteHiddenProperty(Name* key) {
  ASSERT(key->IsUniqueName());
  if (IsJSGlobalProxy()) {
    // For a proxy, use the prototype as target object.
    Object* proxy_parent = GetPrototype();
    // If the proxy is detached, return immediately.
    if (proxy_parent->IsNull()) return;
    ASSERT(proxy_parent->IsJSGlobalObject());
    JSObject::cast(proxy_parent)->DeleteHiddenProperty(key);
    return;
  }
  ASSERT(!IsJSGlobalProxy());
  MaybeObject* hidden_lookup =
      GetHiddenPropertiesHashTable(ONLY_RETURN_INLINE_VALUE);
  Object* inline_value = hidden_lookup->ToObjectUnchecked();

  // We never delete (inline-stored) identity hashes.
  ASSERT(key != GetHeap()->identity_hash_string());
  if (inline_value->IsUndefined() || inline_value->IsSmi()) return;

  ObjectHashTable* hashtable = ObjectHashTable::cast(inline_value);
  MaybeObject* delete_result = hashtable->Put(key, GetHeap()->the_hole_value());
  USE(delete_result);
  ASSERT(!delete_result->IsFailure());  // Delete does not cause GC.
}


bool JSObject::HasHiddenProperties() {
  return GetPropertyAttributePostInterceptor(this,
                                             GetHeap()->hidden_string(),
                                             false) != ABSENT;
}


MaybeObject* JSObject::GetHiddenPropertiesHashTable(
    InitializeHiddenProperties init_option) {
  ASSERT(!IsJSGlobalProxy());
  Object* inline_value;
  if (HasFastProperties()) {
    // If the object has fast properties, check whether the first slot
    // in the descriptor array matches the hidden string. Since the
    // hidden strings hash code is zero (and no other name has hash
    // code zero) it will always occupy the first entry if present.
    DescriptorArray* descriptors = this->map()->instance_descriptors();
    if (descriptors->number_of_descriptors() > 0) {
      int sorted_index = descriptors->GetSortedKeyIndex(0);
      if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_string() &&
          sorted_index < map()->NumberOfOwnDescriptors()) {
        ASSERT(descriptors->GetType(sorted_index) == FIELD);
        MaybeObject* maybe_value = this->FastPropertyAt(
            descriptors->GetDetails(sorted_index).representation(),
            descriptors->GetFieldIndex(sorted_index));
        if (!maybe_value->To(&inline_value)) return maybe_value;
      } else {
        inline_value = GetHeap()->undefined_value();
      }
    } else {
      inline_value = GetHeap()->undefined_value();
    }
  } else {
    PropertyAttributes attributes;
    // You can't install a getter on a property indexed by the hidden string,
    // so we can be sure that GetLocalPropertyPostInterceptor returns a real
    // object.
    inline_value =
        GetLocalPropertyPostInterceptor(this,
                                        GetHeap()->hidden_string(),
                                        &attributes)->ToObjectUnchecked();
  }

  if (init_option == ONLY_RETURN_INLINE_VALUE ||
      inline_value->IsHashTable()) {
    return inline_value;
  }

  ObjectHashTable* hashtable;
  static const int kInitialCapacity = 4;
  MaybeObject* maybe_obj =
      ObjectHashTable::Allocate(GetHeap(),
                                kInitialCapacity,
                                ObjectHashTable::USE_CUSTOM_MINIMUM_CAPACITY);
  if (!maybe_obj->To<ObjectHashTable>(&hashtable)) return maybe_obj;

  if (inline_value->IsSmi()) {
    // We were storing the identity hash inline and now allocated an actual
    // dictionary.  Put the identity hash into the new dictionary.
    MaybeObject* insert_result =
        hashtable->Put(GetHeap()->identity_hash_string(), inline_value);
    ObjectHashTable* new_table;
    if (!insert_result->To(&new_table)) return insert_result;
    // We expect no resizing for the first insert.
    ASSERT_EQ(hashtable, new_table);
  }

  MaybeObject* store_result =
      SetPropertyPostInterceptor(GetHeap()->hidden_string(),
                                 hashtable,
                                 DONT_ENUM,
                                 kNonStrictMode,
                                 OMIT_EXTENSIBILITY_CHECK,
                                 FORCE_FIELD);
  if (store_result->IsFailure()) return store_result;
  return hashtable;
}


MaybeObject* JSObject::SetHiddenPropertiesHashTable(Object* value) {
  ASSERT(!IsJSGlobalProxy());
  // We can store the identity hash inline iff there is no backing store
  // for hidden properties yet.
  ASSERT(HasHiddenProperties() != value->IsSmi());
  if (HasFastProperties()) {
    // If the object has fast properties, check whether the first slot
    // in the descriptor array matches the hidden string. Since the
    // hidden strings hash code is zero (and no other name has hash
    // code zero) it will always occupy the first entry if present.
    DescriptorArray* descriptors = this->map()->instance_descriptors();
    if (descriptors->number_of_descriptors() > 0) {
      int sorted_index = descriptors->GetSortedKeyIndex(0);
      if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_string() &&
          sorted_index < map()->NumberOfOwnDescriptors()) {
        ASSERT(descriptors->GetType(sorted_index) == FIELD);
        FastPropertyAtPut(descriptors->GetFieldIndex(sorted_index), value);
        return this;
      }
    }
  }
  MaybeObject* store_result =
      SetPropertyPostInterceptor(GetHeap()->hidden_string(),
                                 value,
                                 DONT_ENUM,
                                 kNonStrictMode,
                                 OMIT_EXTENSIBILITY_CHECK,
                                 FORCE_FIELD);
  if (store_result->IsFailure()) return store_result;
  return this;
}


Handle<Object> JSObject::DeletePropertyPostInterceptor(Handle<JSObject> object,
                                                       Handle<Name> name,
                                                       DeleteMode mode) {
  // Check local property, ignore interceptor.
  Isolate* isolate = object->GetIsolate();
  LookupResult result(isolate);
  object->LocalLookupRealNamedProperty(*name, &result);
  if (!result.IsFound()) return isolate->factory()->true_value();

  // Normalize object if needed.
  NormalizeProperties(object, CLEAR_INOBJECT_PROPERTIES, 0);

  return DeleteNormalizedProperty(object, name, mode);
}


Handle<Object> JSObject::DeletePropertyWithInterceptor(Handle<JSObject> object,
                                                       Handle<Name> name) {
  Isolate* isolate = object->GetIsolate();

  // TODO(rossberg): Support symbols in the API.
  if (name->IsSymbol()) return isolate->factory()->false_value();

  Handle<InterceptorInfo> interceptor(object->GetNamedInterceptor());
  if (!interceptor->deleter()->IsUndefined()) {
    v8::NamedPropertyDeleter deleter =
        v8::ToCData<v8::NamedPropertyDeleter>(interceptor->deleter());
    LOG(isolate,
        ApiNamedPropertyAccess("interceptor-named-delete", *object, *name));
    PropertyCallbackArguments args(
        isolate, interceptor->data(), *object, *object);
    v8::Handle<v8::Boolean> result =
        args.Call(deleter, v8::Utils::ToLocal(Handle<String>::cast(name)));
    RETURN_HANDLE_IF_SCHEDULED_EXCEPTION(isolate, Object);
    if (!result.IsEmpty()) {
      ASSERT(result->IsBoolean());
      Handle<Object> result_internal = v8::Utils::OpenHandle(*result);
      result_internal->VerifyApiCallResultType();
      // Rebox CustomArguments::kReturnValueOffset before returning.
      return handle(*result_internal, isolate);
    }
  }
  Handle<Object> result =
      DeletePropertyPostInterceptor(object, name, NORMAL_DELETION);
  RETURN_HANDLE_IF_SCHEDULED_EXCEPTION(isolate, Object);
  return result;
}


MaybeObject* JSObject::DeleteElementWithInterceptor(uint32_t index) {
  Isolate* isolate = GetIsolate();
  Heap* heap = isolate->heap();
  // Make sure that the top context does not change when doing
  // callbacks or interceptor calls.
  AssertNoContextChange ncc;
  HandleScope scope(isolate);
  Handle<InterceptorInfo> interceptor(GetIndexedInterceptor());
  if (interceptor->deleter()->IsUndefined()) return heap->false_value();
  v8::IndexedPropertyDeleter deleter =
      v8::ToCData<v8::IndexedPropertyDeleter>(interceptor->deleter());
  Handle<JSObject> this_handle(this);
  LOG(isolate,
      ApiIndexedPropertyAccess("interceptor-indexed-delete", this, index));
  PropertyCallbackArguments args(isolate, interceptor->data(), this, this);
  v8::Handle<v8::Boolean> result = args.Call(deleter, index);
  RETURN_IF_SCHEDULED_EXCEPTION(isolate);
  if (!result.IsEmpty()) {
    ASSERT(result->IsBoolean());
    Handle<Object> result_internal = v8::Utils::OpenHandle(*result);
    result_internal->VerifyApiCallResultType();
    return *result_internal;
  }
  MaybeObject* raw_result = this_handle->GetElementsAccessor()->Delete(
      *this_handle,
      index,
      NORMAL_DELETION);
  RETURN_IF_SCHEDULED_EXCEPTION(isolate);
  return raw_result;
}


Handle<Object> JSObject::DeleteElement(Handle<JSObject> obj,
                                       uint32_t index,
                                       DeleteMode mode) {
  CALL_HEAP_FUNCTION(obj->GetIsolate(),
                     obj->DeleteElement(index, mode),
                     Object);
}


MaybeObject* JSObject::DeleteElement(uint32_t index, DeleteMode mode) {
  Isolate* isolate = GetIsolate();
  // Check access rights if needed.
  if (IsAccessCheckNeeded() &&
      !isolate->MayIndexedAccess(this, index, v8::ACCESS_DELETE)) {
    isolate->ReportFailedAccessCheck(this, v8::ACCESS_DELETE);
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    return isolate->heap()->false_value();
  }

  if (IsStringObjectWithCharacterAt(index)) {
    if (mode == STRICT_DELETION) {
      // Deleting a non-configurable property in strict mode.
      HandleScope scope(isolate);
      Handle<Object> holder(this, isolate);
      Handle<Object> name = isolate->factory()->NewNumberFromUint(index);
      Handle<Object> args[2] = { name, holder };
      Handle<Object> error =
          isolate->factory()->NewTypeError("strict_delete_property",
                                           HandleVector(args, 2));
      return isolate->Throw(*error);
    }
    return isolate->heap()->false_value();
  }

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return isolate->heap()->false_value();
    ASSERT(proto->IsJSGlobalObject());
    return JSGlobalObject::cast(proto)->DeleteElement(index, mode);
  }

  // From this point on everything needs to be handlified.
  HandleScope scope(isolate);
  Handle<JSObject> self(this);

  Handle<Object> old_value;
  bool should_enqueue_change_record = false;
  if (FLAG_harmony_observation && self->map()->is_observed()) {
    should_enqueue_change_record = self->HasLocalElement(index);
    if (should_enqueue_change_record) {
      old_value = self->GetLocalElementAccessorPair(index) != NULL
          ? Handle<Object>::cast(isolate->factory()->the_hole_value())
          : Object::GetElement(self, index);
    }
  }

  MaybeObject* result;
  // Skip interceptor if forcing deletion.
  if (self->HasIndexedInterceptor() && mode != FORCE_DELETION) {
    result = self->DeleteElementWithInterceptor(index);
  } else {
    result = self->GetElementsAccessor()->Delete(*self, index, mode);
  }

  Handle<Object> hresult;
  if (!result->ToHandle(&hresult, isolate)) return result;

  if (should_enqueue_change_record && !self->HasLocalElement(index)) {
    Handle<String> name = isolate->factory()->Uint32ToString(index);
    EnqueueChangeRecord(self, "deleted", name, old_value);
  }

  return *hresult;
}


Handle<Object> JSObject::DeleteProperty(Handle<JSObject> object,
                                        Handle<Name> name,
                                        DeleteMode mode) {
  Isolate* isolate = object->GetIsolate();
  // ECMA-262, 3rd, 8.6.2.5
  ASSERT(name->IsName());

  // Check access rights if needed.
  if (object->IsAccessCheckNeeded() &&
      !isolate->MayNamedAccess(*object, *name, v8::ACCESS_DELETE)) {
    isolate->ReportFailedAccessCheck(*object, v8::ACCESS_DELETE);
    RETURN_HANDLE_IF_SCHEDULED_EXCEPTION(isolate, Object);
    return isolate->factory()->false_value();
  }

  if (object->IsJSGlobalProxy()) {
    Object* proto = object->GetPrototype();
    if (proto->IsNull()) return isolate->factory()->false_value();
    ASSERT(proto->IsJSGlobalObject());
    return JSGlobalObject::DeleteProperty(
        handle(JSGlobalObject::cast(proto)), name, mode);
  }

  uint32_t index = 0;
  if (name->AsArrayIndex(&index)) {
    return DeleteElement(object, index, mode);
  }

  LookupResult lookup(isolate);
  object->LocalLookup(*name, &lookup, true);
  if (!lookup.IsFound()) return isolate->factory()->true_value();
  // Ignore attributes if forcing a deletion.
  if (lookup.IsDontDelete() && mode != FORCE_DELETION) {
    if (mode == STRICT_DELETION) {
      // Deleting a non-configurable property in strict mode.
      Handle<Object> args[2] = { name, object };
      Handle<Object> error = isolate->factory()->NewTypeError(
          "strict_delete_property", HandleVector(args, ARRAY_SIZE(args)));
      isolate->Throw(*error);
      return Handle<Object>();
    }
    return isolate->factory()->false_value();
  }

  Handle<Object> old_value = isolate->factory()->the_hole_value();
  bool is_observed = FLAG_harmony_observation && object->map()->is_observed();
  if (is_observed && lookup.IsDataProperty()) {
    old_value = Object::GetProperty(object, name);
  }
  Handle<Object> result;

  // Check for interceptor.
  if (lookup.IsInterceptor()) {
    // Skip interceptor if forcing a deletion.
    if (mode == FORCE_DELETION) {
      result = DeletePropertyPostInterceptor(object, name, mode);
    } else {
      result = DeletePropertyWithInterceptor(object, name);
    }
  } else {
    // Normalize object if needed.
    NormalizeProperties(object, CLEAR_INOBJECT_PROPERTIES, 0);
    // Make sure the properties are normalized before removing the entry.
    result = DeleteNormalizedProperty(object, name, mode);
  }

  if (is_observed && !object->HasLocalProperty(*name)) {
    EnqueueChangeRecord(object, "deleted", name, old_value);
  }

  return result;
}


Handle<Object> JSReceiver::DeleteElement(Handle<JSReceiver> object,
                                         uint32_t index,
                                         DeleteMode mode) {
  if (object->IsJSProxy()) {
    return JSProxy::DeleteElementWithHandler(
        Handle<JSProxy>::cast(object), index, mode);
  }
  return JSObject::DeleteElement(Handle<JSObject>::cast(object), index, mode);
}


Handle<Object> JSReceiver::DeleteProperty(Handle<JSReceiver> object,
                                          Handle<Name> name,
                                          DeleteMode mode) {
  if (object->IsJSProxy()) {
    return JSProxy::DeletePropertyWithHandler(
        Handle<JSProxy>::cast(object), name, mode);
  }
  return JSObject::DeleteProperty(Handle<JSObject>::cast(object), name, mode);
}


bool JSObject::ReferencesObjectFromElements(FixedArray* elements,
                                            ElementsKind kind,
                                            Object* object) {
  ASSERT(IsFastObjectElementsKind(kind) ||
         kind == DICTIONARY_ELEMENTS);
  if (IsFastObjectElementsKind(kind)) {
    int length = IsJSArray()
        ? Smi::cast(JSArray::cast(this)->length())->value()
        : elements->length();
    for (int i = 0; i < length; ++i) {
      Object* element = elements->get(i);
      if (!element->IsTheHole() && element == object) return true;
    }
  } else {
    Object* key =
        SeededNumberDictionary::cast(elements)->SlowReverseLookup(object);
    if (!key->IsUndefined()) return true;
  }
  return false;
}


// Check whether this object references another object.
bool JSObject::ReferencesObject(Object* obj) {
  Map* map_of_this = map();
  Heap* heap = GetHeap();
  DisallowHeapAllocation no_allocation;

  // Is the object the constructor for this object?
  if (map_of_this->constructor() == obj) {
    return true;
  }

  // Is the object the prototype for this object?
  if (map_of_this->prototype() == obj) {
    return true;
  }

  // Check if the object is among the named properties.
  Object* key = SlowReverseLookup(obj);
  if (!key->IsUndefined()) {
    return true;
  }

  // Check if the object is among the indexed properties.
  ElementsKind kind = GetElementsKind();
  switch (kind) {
    case EXTERNAL_PIXEL_ELEMENTS:
    case EXTERNAL_BYTE_ELEMENTS:
    case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
    case EXTERNAL_SHORT_ELEMENTS:
    case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
    case EXTERNAL_INT_ELEMENTS:
    case EXTERNAL_UNSIGNED_INT_ELEMENTS:
    case EXTERNAL_FLOAT_ELEMENTS:
    case EXTERNAL_DOUBLE_ELEMENTS:
    case FAST_DOUBLE_ELEMENTS:
    case FAST_HOLEY_DOUBLE_ELEMENTS:
      // Raw pixels and external arrays do not reference other
      // objects.
      break;
    case FAST_SMI_ELEMENTS:
    case FAST_HOLEY_SMI_ELEMENTS:
      break;
    case FAST_ELEMENTS:
    case FAST_HOLEY_ELEMENTS:
    case DICTIONARY_ELEMENTS: {
      FixedArray* elements = FixedArray::cast(this->elements());
      if (ReferencesObjectFromElements(elements, kind, obj)) return true;
      break;
    }
    case NON_STRICT_ARGUMENTS_ELEMENTS: {
      FixedArray* parameter_map = FixedArray::cast(elements());
      // Check the mapped parameters.
      int length = parameter_map->length();
      for (int i = 2; i < length; ++i) {
        Object* value = parameter_map->get(i);
        if (!value->IsTheHole() && value == obj) return true;
      }
      // Check the arguments.
      FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
      kind = arguments->IsDictionary() ? DICTIONARY_ELEMENTS :
          FAST_HOLEY_ELEMENTS;
      if (ReferencesObjectFromElements(arguments, kind, obj)) return true;
      break;
    }
  }

  // For functions check the context.
  if (IsJSFunction()) {
    // Get the constructor function for arguments array.
    JSObject* arguments_boilerplate =
        heap->isolate()->context()->native_context()->
            arguments_boilerplate();
    JSFunction* arguments_function =
        JSFunction::cast(arguments_boilerplate->map()->constructor());

    // Get the context and don't check if it is the native context.
    JSFunction* f = JSFunction::cast(this);
    Context* context = f->context();
    if (context->IsNativeContext()) {
      return false;
    }

    // Check the non-special context slots.
    for (int i = Context::MIN_CONTEXT_SLOTS; i < context->length(); i++) {
      // Only check JS objects.
      if (context->get(i)->IsJSObject()) {
        JSObject* ctxobj = JSObject::cast(context->get(i));
        // If it is an arguments array check the content.
        if (ctxobj->map()->constructor() == arguments_function) {
          if (ctxobj->ReferencesObject(obj)) {
            return true;
          }
        } else if (ctxobj == obj) {
          return true;
        }
      }
    }

    // Check the context extension (if any) if it can have references.
    if (context->has_extension() && !context->IsCatchContext()) {
      return JSObject::cast(context->extension())->ReferencesObject(obj);
    }
  }

  // No references to object.
  return false;
}


Handle<Object> JSObject::PreventExtensions(Handle<JSObject> object) {
  CALL_HEAP_FUNCTION(object->GetIsolate(), object->PreventExtensions(), Object);
}


MaybeObject* JSObject::PreventExtensions() {
  Isolate* isolate = GetIsolate();
  if (IsAccessCheckNeeded() &&
      !isolate->MayNamedAccess(this,
                               isolate->heap()->undefined_value(),
                               v8::ACCESS_KEYS)) {
    isolate->ReportFailedAccessCheck(this, v8::ACCESS_KEYS);
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    return isolate->heap()->false_value();
  }

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return this;
    ASSERT(proto->IsJSGlobalObject());
    return JSObject::cast(proto)->PreventExtensions();
  }

  // It's not possible to seal objects with external array elements
  if (HasExternalArrayElements()) {
    HandleScope scope(isolate);
    Handle<Object> object(this, isolate);
    Handle<Object> error  =
        isolate->factory()->NewTypeError(
            "cant_prevent_ext_external_array_elements",
            HandleVector(&object, 1));
    return isolate->Throw(*error);
  }

  // If there are fast elements we normalize.
  SeededNumberDictionary* dictionary = NULL;
  { MaybeObject* maybe = NormalizeElements();
    if (!maybe->To<SeededNumberDictionary>(&dictionary)) return maybe;
  }
  ASSERT(HasDictionaryElements() || HasDictionaryArgumentsElements());
  // Make sure that we never go back to fast case.
  dictionary->set_requires_slow_elements();

  // Do a map transition, other objects with this map may still
  // be extensible.
  // TODO(adamk): Extend the NormalizedMapCache to handle non-extensible maps.
  Map* new_map;
  MaybeObject* maybe = map()->Copy();
  if (!maybe->To(&new_map)) return maybe;

  new_map->set_is_extensible(false);
  set_map(new_map);
  ASSERT(!map()->is_extensible());
  return new_map;
}


template<typename Dictionary>
static void FreezeDictionary(Dictionary* dictionary) {
  int capacity = dictionary->Capacity();
  for (int i = 0; i < capacity; i++) {
    Object* k = dictionary->KeyAt(i);
    if (dictionary->IsKey(k)) {
      PropertyDetails details = dictionary->DetailsAt(i);
      int attrs = DONT_DELETE;
      // READ_ONLY is an invalid attribute for JS setters/getters.
      if (details.type() != CALLBACKS ||
          !dictionary->ValueAt(i)->IsAccessorPair()) {
        attrs |= READ_ONLY;
      }
      details = details.CopyAddAttributes(
          static_cast<PropertyAttributes>(attrs));
      dictionary->DetailsAtPut(i, details);
    }
  }
}


MUST_USE_RESULT MaybeObject* JSObject::Freeze(Isolate* isolate) {
  // Freezing non-strict arguments should be handled elsewhere.
  ASSERT(!HasNonStrictArgumentsElements());

  Heap* heap = isolate->heap();

  if (map()->is_frozen()) return this;

  if (IsAccessCheckNeeded() &&
      !isolate->MayNamedAccess(this,
                               heap->undefined_value(),
                               v8::ACCESS_KEYS)) {
    isolate->ReportFailedAccessCheck(this, v8::ACCESS_KEYS);
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    return heap->false_value();
  }

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return this;
    ASSERT(proto->IsJSGlobalObject());
    return JSObject::cast(proto)->Freeze(isolate);
  }

  // It's not possible to freeze objects with external array elements
  if (HasExternalArrayElements()) {
    HandleScope scope(isolate);
    Handle<Object> object(this, isolate);
    Handle<Object> error  =
        isolate->factory()->NewTypeError(
            "cant_prevent_ext_external_array_elements",
            HandleVector(&object, 1));
    return isolate->Throw(*error);
  }

  SeededNumberDictionary* new_element_dictionary = NULL;
  if (!elements()->IsDictionary()) {
    int length = IsJSArray()
        ? Smi::cast(JSArray::cast(this)->length())->value()
        : elements()->length();
    if (length > 0) {
      int capacity = 0;
      int used = 0;
      GetElementsCapacityAndUsage(&capacity, &used);
      MaybeObject* maybe_dict = SeededNumberDictionary::Allocate(heap, used);
      if (!maybe_dict->To(&new_element_dictionary)) return maybe_dict;

      // Move elements to a dictionary; avoid calling NormalizeElements to avoid
      // unnecessary transitions.
      maybe_dict = CopyFastElementsToDictionary(isolate, elements(), length,
                                                new_element_dictionary);
      if (!maybe_dict->To(&new_element_dictionary)) return maybe_dict;
    } else {
      // No existing elements, use a pre-allocated empty backing store
      new_element_dictionary = heap->empty_slow_element_dictionary();
    }
  }

  LookupResult result(isolate);
  map()->LookupTransition(this, heap->frozen_symbol(), &result);
  if (result.IsTransition()) {
    Map* transition_map = result.GetTransitionTarget();
    ASSERT(transition_map->has_dictionary_elements());
    ASSERT(transition_map->is_frozen());
    ASSERT(!transition_map->is_extensible());
    set_map(transition_map);
  } else if (HasFastProperties() && map()->CanHaveMoreTransitions()) {
    // Create a new descriptor array with fully-frozen properties
    int num_descriptors = map()->NumberOfOwnDescriptors();
    DescriptorArray* new_descriptors;
    MaybeObject* maybe_descriptors =
        map()->instance_descriptors()->CopyUpToAddAttributes(num_descriptors,
                                                             FROZEN);
    if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;

    Map* new_map;
    MaybeObject* maybe_new_map = map()->CopyReplaceDescriptors(
        new_descriptors, INSERT_TRANSITION, heap->frozen_symbol());
    if (!maybe_new_map->To(&new_map)) return maybe_new_map;
    new_map->freeze();
    new_map->set_is_extensible(false);
    new_map->set_elements_kind(DICTIONARY_ELEMENTS);
    set_map(new_map);
  } else {
    // Slow path: need to normalize properties for safety
    MaybeObject* maybe = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
    if (maybe->IsFailure()) return maybe;

    // Create a new map, since other objects with this map may be extensible.
    // TODO(adamk): Extend the NormalizedMapCache to handle non-extensible maps.
    Map* new_map;
    MaybeObject* maybe_copy = map()->Copy();
    if (!maybe_copy->To(&new_map)) return maybe_copy;
    new_map->freeze();
    new_map->set_is_extensible(false);
    new_map->set_elements_kind(DICTIONARY_ELEMENTS);
    set_map(new_map);

    // Freeze dictionary-mode properties
    FreezeDictionary(property_dictionary());
  }

  ASSERT(map()->has_dictionary_elements());
  if (new_element_dictionary != NULL) {
    set_elements(new_element_dictionary);
  }

  if (elements() != heap->empty_slow_element_dictionary()) {
    SeededNumberDictionary* dictionary = element_dictionary();
    // Make sure we never go back to the fast case
    dictionary->set_requires_slow_elements();
    // Freeze all elements in the dictionary
    FreezeDictionary(dictionary);
  }

  return this;
}


MUST_USE_RESULT MaybeObject* JSObject::SetObserved(Isolate* isolate) {
  if (map()->is_observed())
    return isolate->heap()->undefined_value();

  Heap* heap = isolate->heap();

  if (!HasExternalArrayElements()) {
    // Go to dictionary mode, so that we don't skip map checks.
    MaybeObject* maybe = NormalizeElements();
    if (maybe->IsFailure()) return maybe;
    ASSERT(!HasFastElements());
  }

  LookupResult result(isolate);
  map()->LookupTransition(this, heap->observed_symbol(), &result);

  Map* new_map;
  if (result.IsTransition()) {
    new_map = result.GetTransitionTarget();
    ASSERT(new_map->is_observed());
  } else if (map()->CanHaveMoreTransitions()) {
    MaybeObject* maybe_new_map = map()->CopyForObserved();
    if (!maybe_new_map->To(&new_map)) return maybe_new_map;
  } else {
    MaybeObject* maybe_copy = map()->Copy();
    if (!maybe_copy->To(&new_map)) return maybe_copy;
    new_map->set_is_observed(true);
  }
  set_map(new_map);

  return heap->undefined_value();
}


MUST_USE_RESULT MaybeObject* JSObject::DeepCopy(Isolate* isolate) {
  StackLimitCheck check(isolate);
  if (check.HasOverflowed()) return isolate->StackOverflow();

  if (map()->is_deprecated()) {
    MaybeObject* maybe_failure = MigrateInstance();
    if (maybe_failure->IsFailure()) return maybe_failure;
  }

  Heap* heap = isolate->heap();
  Object* result;
  { MaybeObject* maybe_result = heap->CopyJSObject(this);
    if (!maybe_result->ToObject(&result)) return maybe_result;
  }
  JSObject* copy = JSObject::cast(result);

  // Deep copy local properties.
  if (copy->HasFastProperties()) {
    DescriptorArray* descriptors = copy->map()->instance_descriptors();
    int limit = copy->map()->NumberOfOwnDescriptors();
    for (int i = 0; i < limit; i++) {
      PropertyDetails details = descriptors->GetDetails(i);
      if (details.type() != FIELD) continue;
      int index = descriptors->GetFieldIndex(i);
      Object* value = RawFastPropertyAt(index);
      if (value->IsJSObject()) {
        JSObject* js_object = JSObject::cast(value);
        MaybeObject* maybe_copy = js_object->DeepCopy(isolate);
        if (!maybe_copy->To(&value)) return maybe_copy;
      } else {
        Representation representation = details.representation();
        MaybeObject* maybe_storage =
            value->AllocateNewStorageFor(heap, representation);
        if (!maybe_storage->To(&value)) return maybe_storage;
      }
      copy->FastPropertyAtPut(index, value);
    }
  } else {
    { MaybeObject* maybe_result =
          heap->AllocateFixedArray(copy->NumberOfLocalProperties());
      if (!maybe_result->ToObject(&result)) return maybe_result;
    }
    FixedArray* names = FixedArray::cast(result);
    copy->GetLocalPropertyNames(names, 0);
    for (int i = 0; i < names->length(); i++) {
      ASSERT(names->get(i)->IsString());
      String* key_string = String::cast(names->get(i));
      PropertyAttributes attributes =
          copy->GetLocalPropertyAttribute(key_string);
      // Only deep copy fields from the object literal expression.
      // In particular, don't try to copy the length attribute of
      // an array.
      if (attributes != NONE) continue;
      Object* value =
          copy->GetProperty(key_string, &attributes)->ToObjectUnchecked();
      if (value->IsJSObject()) {
        JSObject* js_object = JSObject::cast(value);
        { MaybeObject* maybe_result = js_object->DeepCopy(isolate);
          if (!maybe_result->ToObject(&result)) return maybe_result;
        }
        { MaybeObject* maybe_result =
              // Creating object copy for literals. No strict mode needed.
              copy->SetProperty(key_string, result, NONE, kNonStrictMode);
          if (!maybe_result->ToObject(&result)) return maybe_result;
        }
      }
    }
  }

  // Deep copy local elements.
  // Pixel elements cannot be created using an object literal.
  ASSERT(!copy->HasExternalArrayElements());
  switch (copy->GetElementsKind()) {
    case FAST_SMI_ELEMENTS:
    case FAST_ELEMENTS:
    case FAST_HOLEY_SMI_ELEMENTS:
    case FAST_HOLEY_ELEMENTS: {
      FixedArray* elements = FixedArray::cast(copy->elements());
      if (elements->map() == heap->fixed_cow_array_map()) {
        isolate->counters()->cow_arrays_created_runtime()->Increment();
#ifdef DEBUG
        for (int i = 0; i < elements->length(); i++) {
          ASSERT(!elements->get(i)->IsJSObject());
        }
#endif
      } else {
        for (int i = 0; i < elements->length(); i++) {
          Object* value = elements->get(i);
          ASSERT(value->IsSmi() ||
                 value->IsTheHole() ||
                 (IsFastObjectElementsKind(copy->GetElementsKind())));
          if (value->IsJSObject()) {
            JSObject* js_object = JSObject::cast(value);
            { MaybeObject* maybe_result = js_object->DeepCopy(isolate);
              if (!maybe_result->ToObject(&result)) return maybe_result;
            }
            elements->set(i, result);
          }
        }
      }
      break;
    }
    case DICTIONARY_ELEMENTS: {
      SeededNumberDictionary* element_dictionary = copy->element_dictionary();
      int capacity = element_dictionary->Capacity();
      for (int i = 0; i < capacity; i++) {
        Object* k = element_dictionary->KeyAt(i);
        if (element_dictionary->IsKey(k)) {
          Object* value = element_dictionary->ValueAt(i);
          if (value->IsJSObject()) {
            JSObject* js_object = JSObject::cast(value);
            { MaybeObject* maybe_result = js_object->DeepCopy(isolate);
              if (!maybe_result->ToObject(&result)) return maybe_result;
            }
            element_dictionary->ValueAtPut(i, result);
          }
        }
      }
      break;
    }
    case NON_STRICT_ARGUMENTS_ELEMENTS:
      UNIMPLEMENTED();
      break;
    case EXTERNAL_PIXEL_ELEMENTS:
    case EXTERNAL_BYTE_ELEMENTS:
    case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
    case EXTERNAL_SHORT_ELEMENTS:
    case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
    case EXTERNAL_INT_ELEMENTS:
    case EXTERNAL_UNSIGNED_INT_ELEMENTS:
    case EXTERNAL_FLOAT_ELEMENTS:
    case EXTERNAL_DOUBLE_ELEMENTS:
    case FAST_DOUBLE_ELEMENTS:
    case FAST_HOLEY_DOUBLE_ELEMENTS:
      // No contained objects, nothing to do.
      break;
  }
  return copy;
}


// Tests for the fast common case for property enumeration:
// - This object and all prototypes has an enum cache (which means that
//   it is no proxy, has no interceptors and needs no access checks).
// - This object has no elements.
// - No prototype has enumerable properties/elements.
bool JSReceiver::IsSimpleEnum() {
  Heap* heap = GetHeap();
  for (Object* o = this;
       o != heap->null_value();
       o = JSObject::cast(o)->GetPrototype()) {
    if (!o->IsJSObject()) return false;
    JSObject* curr = JSObject::cast(o);
    int enum_length = curr->map()->EnumLength();
    if (enum_length == Map::kInvalidEnumCache) return false;
    ASSERT(!curr->HasNamedInterceptor());
    ASSERT(!curr->HasIndexedInterceptor());
    ASSERT(!curr->IsAccessCheckNeeded());
    if (curr->NumberOfEnumElements() > 0) return false;
    if (curr != this && enum_length != 0) return false;
  }
  return true;
}


int Map::NumberOfDescribedProperties(DescriptorFlag which,
                                     PropertyAttributes filter) {
  int result = 0;
  DescriptorArray* descs = instance_descriptors();
  int limit = which == ALL_DESCRIPTORS
      ? descs->number_of_descriptors()
      : NumberOfOwnDescriptors();
  for (int i = 0; i < limit; i++) {
    if ((descs->GetDetails(i).attributes() & filter) == 0 &&
        ((filter & SYMBOLIC) == 0 || !descs->GetKey(i)->IsSymbol())) {
      result++;
    }
  }
  return result;
}


int Map::NextFreePropertyIndex() {
  int max_index = -1;
  int number_of_own_descriptors = NumberOfOwnDescriptors();
  DescriptorArray* descs = instance_descriptors();
  for (int i = 0; i < number_of_own_descriptors; i++) {
    if (descs->GetType(i) == FIELD) {
      int current_index = descs->GetFieldIndex(i);
      if (current_index > max_index) max_index = current_index;
    }
  }
  return max_index + 1;
}


AccessorDescriptor* Map::FindAccessor(Name* name) {
  DescriptorArray* descs = instance_descriptors();
  int number_of_own_descriptors = NumberOfOwnDescriptors();
  for (int i = 0; i < number_of_own_descriptors; i++) {
    if (descs->GetType(i) == CALLBACKS && name->Equals(descs->GetKey(i))) {
      return descs->GetCallbacks(i);
    }
  }
  return NULL;
}


void JSReceiver::LocalLookup(
    Name* name, LookupResult* result, bool search_hidden_prototypes) {
  ASSERT(name->IsName());

  Heap* heap = GetHeap();

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return result->NotFound();
    ASSERT(proto->IsJSGlobalObject());
    return JSReceiver::cast(proto)->LocalLookup(
        name, result, search_hidden_prototypes);
  }

  if (IsJSProxy()) {
    result->HandlerResult(JSProxy::cast(this));
    return;
  }

  // Do not use inline caching if the object is a non-global object
  // that requires access checks.
  if (IsAccessCheckNeeded()) {
    result->DisallowCaching();
  }

  JSObject* js_object = JSObject::cast(this);

  // Check for lookup interceptor except when bootstrapping.
  if (js_object->HasNamedInterceptor() &&
      !heap->isolate()->bootstrapper()->IsActive()) {
    result->InterceptorResult(js_object);
    return;
  }

  js_object->LocalLookupRealNamedProperty(name, result);
  if (result->IsFound() || !search_hidden_prototypes) return;

  Object* proto = js_object->GetPrototype();
  if (!proto->IsJSReceiver()) return;
  JSReceiver* receiver = JSReceiver::cast(proto);
  if (receiver->map()->is_hidden_prototype()) {
    receiver->LocalLookup(name, result, search_hidden_prototypes);
  }
}


void JSReceiver::Lookup(Name* name, LookupResult* result) {
  // Ecma-262 3rd 8.6.2.4
  Heap* heap = GetHeap();
  for (Object* current = this;
       current != heap->null_value();
       current = JSObject::cast(current)->GetPrototype()) {
    JSReceiver::cast(current)->LocalLookup(name, result, false);
    if (result->IsFound()) return;
  }
  result->NotFound();
}


// Search object and its prototype chain for callback properties.
void JSObject::LookupCallbackProperty(Name* name, LookupResult* result) {
  Heap* heap = GetHeap();
  for (Object* current = this;
       current != heap->null_value() && current->IsJSObject();
       current = JSObject::cast(current)->GetPrototype()) {
    JSObject::cast(current)->LocalLookupRealNamedProperty(name, result);
    if (result->IsPropertyCallbacks()) return;
  }
  result->NotFound();
}


// Try to update an accessor in an elements dictionary. Return true if the
// update succeeded, and false otherwise.
static bool UpdateGetterSetterInDictionary(
    SeededNumberDictionary* dictionary,
    uint32_t index,
    Object* getter,
    Object* setter,
    PropertyAttributes attributes) {
  int entry = dictionary->FindEntry(index);
  if (entry != SeededNumberDictionary::kNotFound) {
    Object* result = dictionary->ValueAt(entry);
    PropertyDetails details = dictionary->DetailsAt(entry);
    if (details.type() == CALLBACKS && result->IsAccessorPair()) {
      ASSERT(!details.IsDontDelete());
      if (details.attributes() != attributes) {
        dictionary->DetailsAtPut(
            entry,
            PropertyDetails(attributes, CALLBACKS, index));
      }
      AccessorPair::cast(result)->SetComponents(getter, setter);
      return true;
    }
  }
  return false;
}


void JSObject::DefineElementAccessor(Handle<JSObject> object,
                                     uint32_t index,
                                     Handle<Object> getter,
                                     Handle<Object> setter,
                                     PropertyAttributes attributes) {
  switch (object->GetElementsKind()) {
    case FAST_SMI_ELEMENTS:
    case FAST_ELEMENTS:
    case FAST_DOUBLE_ELEMENTS:
    case FAST_HOLEY_SMI_ELEMENTS:
    case FAST_HOLEY_ELEMENTS:
    case FAST_HOLEY_DOUBLE_ELEMENTS:
      break;
    case EXTERNAL_PIXEL_ELEMENTS:
    case EXTERNAL_BYTE_ELEMENTS:
    case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
    case EXTERNAL_SHORT_ELEMENTS:
    case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
    case EXTERNAL_INT_ELEMENTS:
    case EXTERNAL_UNSIGNED_INT_ELEMENTS:
    case EXTERNAL_FLOAT_ELEMENTS:
    case EXTERNAL_DOUBLE_ELEMENTS:
      // Ignore getters and setters on pixel and external array elements.
      return;
    case DICTIONARY_ELEMENTS:
      if (UpdateGetterSetterInDictionary(object->element_dictionary(),
                                         index,
                                         *getter,
                                         *setter,
                                         attributes)) {
        return;
      }
      break;
    case NON_STRICT_ARGUMENTS_ELEMENTS: {
      // Ascertain whether we have read-only properties or an existing
      // getter/setter pair in an arguments elements dictionary backing
      // store.
      FixedArray* parameter_map = FixedArray::cast(object->elements());
      uint32_t length = parameter_map->length();
      Object* probe =
          index < (length - 2) ? parameter_map->get(index + 2) : NULL;
      if (probe == NULL || probe->IsTheHole()) {
        FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
        if (arguments->IsDictionary()) {
          SeededNumberDictionary* dictionary =
              SeededNumberDictionary::cast(arguments);
          if (UpdateGetterSetterInDictionary(dictionary,
                                             index,
                                             *getter,
                                             *setter,
                                             attributes)) {
            return;
          }
        }
      }
      break;
    }
  }

  Isolate* isolate = object->GetIsolate();
  Handle<AccessorPair> accessors = isolate->factory()->NewAccessorPair();
  accessors->SetComponents(*getter, *setter);

  CALL_HEAP_FUNCTION_VOID(
      isolate, object->SetElementCallback(index, *accessors, attributes));
}


Handle<AccessorPair> JSObject::CreateAccessorPairFor(Handle<JSObject> object,
                                                     Handle<Name> name) {
  Isolate* isolate = object->GetIsolate();
  LookupResult result(isolate);
  object->LocalLookupRealNamedProperty(*name, &result);
  if (result.IsPropertyCallbacks()) {
    // Note that the result can actually have IsDontDelete() == true when we
    // e.g. have to fall back to the slow case while adding a setter after
    // successfully reusing a map transition for a getter. Nevertheless, this is
    // OK, because the assertion only holds for the whole addition of both
    // accessors, not for the addition of each part. See first comment in
    // DefinePropertyAccessor below.
    Object* obj = result.GetCallbackObject();
    if (obj->IsAccessorPair()) {
      return AccessorPair::Copy(handle(AccessorPair::cast(obj), isolate));
    }
  }
  return isolate->factory()->NewAccessorPair();
}


void JSObject::DefinePropertyAccessor(Handle<JSObject> object,
                                      Handle<Name> name,
                                      Handle<Object> getter,
                                      Handle<Object> setter,
                                      PropertyAttributes attributes) {
  // We could assert that the property is configurable here, but we would need
  // to do a lookup, which seems to be a bit of overkill.
  bool only_attribute_changes = getter->IsNull() && setter->IsNull();
  if (object->HasFastProperties() && !only_attribute_changes &&
      (object->map()->NumberOfOwnDescriptors() <
       DescriptorArray::kMaxNumberOfDescriptors)) {
    bool getterOk = getter->IsNull() ||
        DefineFastAccessor(object, name, ACCESSOR_GETTER, getter, attributes);
    bool setterOk = !getterOk || setter->IsNull() ||
        DefineFastAccessor(object, name, ACCESSOR_SETTER, setter, attributes);
    if (getterOk && setterOk) return;
  }

  Handle<AccessorPair> accessors = CreateAccessorPairFor(object, name);
  accessors->SetComponents(*getter, *setter);

  CALL_HEAP_FUNCTION_VOID(
      object->GetIsolate(),
      object->SetPropertyCallback(*name, *accessors, attributes));
}


bool JSObject::CanSetCallback(Name* name) {
  ASSERT(!IsAccessCheckNeeded() ||
         GetIsolate()->MayNamedAccess(this, name, v8::ACCESS_SET));

  // Check if there is an API defined callback object which prohibits
  // callback overwriting in this object or its prototype chain.
  // This mechanism is needed for instance in a browser setting, where
  // certain accessors such as window.location should not be allowed
  // to be overwritten because allowing overwriting could potentially
  // cause security problems.
  LookupResult callback_result(GetIsolate());
  LookupCallbackProperty(name, &callback_result);
  if (callback_result.IsFound()) {
    Object* obj = callback_result.GetCallbackObject();
    if (obj->IsAccessorInfo() &&
        AccessorInfo::cast(obj)->prohibits_overwriting()) {
      return false;
    }
  }

  return true;
}


MaybeObject* JSObject::SetElementCallback(uint32_t index,
                                          Object* structure,
                                          PropertyAttributes attributes) {
  PropertyDetails details = PropertyDetails(attributes, CALLBACKS, 0);

  // Normalize elements to make this operation simple.
  SeededNumberDictionary* dictionary;
  { MaybeObject* maybe_dictionary = NormalizeElements();
    if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
  }
  ASSERT(HasDictionaryElements() || HasDictionaryArgumentsElements());

  // Update the dictionary with the new CALLBACKS property.
  { MaybeObject* maybe_dictionary = dictionary->Set(index, structure, details);
    if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
  }

  dictionary->set_requires_slow_elements();
  // Update the dictionary backing store on the object.
  if (elements()->map() == GetHeap()->non_strict_arguments_elements_map()) {
    // Also delete any parameter alias.
    //
    // TODO(kmillikin): when deleting the last parameter alias we could
    // switch to a direct backing store without the parameter map.  This
    // would allow GC of the context.
    FixedArray* parameter_map = FixedArray::cast(elements());
    if (index < static_cast<uint32_t>(parameter_map->length()) - 2) {
      parameter_map->set(index + 2, GetHeap()->the_hole_value());
    }
    parameter_map->set(1, dictionary);
  } else {
    set_elements(dictionary);
  }

  return GetHeap()->undefined_value();
}


MaybeObject* JSObject::SetPropertyCallback(Name* name,
                                           Object* structure,
                                           PropertyAttributes attributes) {
  // Normalize object to make this operation simple.
  MaybeObject* maybe_ok = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
  if (maybe_ok->IsFailure()) return maybe_ok;

  // For the global object allocate a new map to invalidate the global inline
  // caches which have a global property cell reference directly in the code.
  if (IsGlobalObject()) {
    Map* new_map;
    MaybeObject* maybe_new_map = map()->CopyDropDescriptors();
    if (!maybe_new_map->To(&new_map)) return maybe_new_map;
    ASSERT(new_map->is_dictionary_map());

    set_map(new_map);
    // When running crankshaft, changing the map is not enough. We
    // need to deoptimize all functions that rely on this global
    // object.
    Deoptimizer::DeoptimizeGlobalObject(this);
  }

  // Update the dictionary with the new CALLBACKS property.
  PropertyDetails details = PropertyDetails(attributes, CALLBACKS, 0);
  maybe_ok = SetNormalizedProperty(name, structure, details);
  if (maybe_ok->IsFailure()) return maybe_ok;

  return GetHeap()->undefined_value();
}


void JSObject::DefineAccessor(Handle<JSObject> object,
                              Handle<Name> name,
                              Handle<Object> getter,
                              Handle<Object> setter,
                              PropertyAttributes attributes) {
  Isolate* isolate = object->GetIsolate();
  // Check access rights if needed.
  if (object->IsAccessCheckNeeded() &&
      !isolate->MayNamedAccess(*object, *name, v8::ACCESS_SET)) {
    isolate->ReportFailedAccessCheck(*object, v8::ACCESS_SET);
    return;
  }

  if (object->IsJSGlobalProxy()) {
    Handle<Object> proto(object->GetPrototype(), isolate);
    if (proto->IsNull()) return;
    ASSERT(proto->IsJSGlobalObject());
    DefineAccessor(
        Handle<JSObject>::cast(proto), name, getter, setter, attributes);
    return;
  }

  // Make sure that the top context does not change when doing callbacks or
  // interceptor calls.
  AssertNoContextChange ncc;

  // Try to flatten before operating on the string.
  if (name->IsString()) String::cast(*name)->TryFlatten();

  if (!object->CanSetCallback(*name)) return;

  uint32_t index = 0;
  bool is_element = name->AsArrayIndex(&index);

  Handle<Object> old_value = isolate->factory()->the_hole_value();
  bool is_observed = FLAG_harmony_observation && object->map()->is_observed();
  bool preexists = false;
  if (is_observed) {
    if (is_element) {
      preexists = object->HasLocalElement(index);
      if (preexists && object->GetLocalElementAccessorPair(index) == NULL) {
        old_value = Object::GetElement(object, index);
      }
    } else {
      LookupResult lookup(isolate);
      object->LocalLookup(*name, &lookup, true);
      preexists = lookup.IsProperty();
      if (preexists && lookup.IsDataProperty()) {
        old_value = Object::GetProperty(object, name);
      }
    }
  }

  if (is_element) {
    DefineElementAccessor(object, index, getter, setter, attributes);
  } else {
    DefinePropertyAccessor(object, name, getter, setter, attributes);
  }

  if (is_observed) {
    const char* type = preexists ? "reconfigured" : "new";
    EnqueueChangeRecord(object, type, name, old_value);
  }
}


static bool TryAccessorTransition(JSObject* self,
                                  Map* transitioned_map,
                                  int target_descriptor,
                                  AccessorComponent component,
                                  Object* accessor,
                                  PropertyAttributes attributes) {
  DescriptorArray* descs = transitioned_map->instance_descriptors();
  PropertyDetails details = descs->GetDetails(target_descriptor);

  // If the transition target was not callbacks, fall back to the slow case.
  if (details.type() != CALLBACKS) return false;
  Object* descriptor = descs->GetCallbacksObject(target_descriptor);
  if (!descriptor->IsAccessorPair()) return false;

  Object* target_accessor = AccessorPair::cast(descriptor)->get(component);
  PropertyAttributes target_attributes = details.attributes();

  // Reuse transition if adding same accessor with same attributes.
  if (target_accessor == accessor && target_attributes == attributes) {
    self->set_map(transitioned_map);
    return true;
  }

  // If either not the same accessor, or not the same attributes, fall back to
  // the slow case.
  return false;
}


static MaybeObject* CopyInsertDescriptor(Map* map,
                                         Name* name,
                                         AccessorPair* accessors,
                                         PropertyAttributes attributes) {
  CallbacksDescriptor new_accessors_desc(name, accessors, attributes);
  return map->CopyInsertDescriptor(&new_accessors_desc, INSERT_TRANSITION);
}


static Handle<Map> CopyInsertDescriptor(Handle<Map> map,
                                        Handle<Name> name,
                                        Handle<AccessorPair> accessors,
                                        PropertyAttributes attributes) {
  CALL_HEAP_FUNCTION(map->GetIsolate(),
                     CopyInsertDescriptor(*map, *name, *accessors, attributes),
                     Map);
}


bool JSObject::DefineFastAccessor(Handle<JSObject> object,
                                  Handle<Name> name,
                                  AccessorComponent component,
                                  Handle<Object> accessor,
                                  PropertyAttributes attributes) {
  ASSERT(accessor->IsSpecFunction() || accessor->IsUndefined());
  Isolate* isolate = object->GetIsolate();
  LookupResult result(isolate);
  object->LocalLookup(*name, &result);

  if (result.IsFound() && !result.IsPropertyCallbacks()) {
    return false;
  }

  // Return success if the same accessor with the same attributes already exist.
  AccessorPair* source_accessors = NULL;
  if (result.IsPropertyCallbacks()) {
    Object* callback_value = result.GetCallbackObject();
    if (callback_value->IsAccessorPair()) {
      source_accessors = AccessorPair::cast(callback_value);
      Object* entry = source_accessors->get(component);
      if (entry == *accessor && result.GetAttributes() == attributes) {
        return true;
      }
    } else {
      return false;
    }

    int descriptor_number = result.GetDescriptorIndex();

    object->map()->LookupTransition(*object, *name, &result);

    if (result.IsFound()) {
      Map* target = result.GetTransitionTarget();
      ASSERT(target->NumberOfOwnDescriptors() ==
             object->map()->NumberOfOwnDescriptors());
      // This works since descriptors are sorted in order of addition.
      ASSERT(object->map()->instance_descriptors()->
             GetKey(descriptor_number) == *name);
      return TryAccessorTransition(*object, target, descriptor_number,
                                   component, *accessor, attributes);
    }
  } else {
    // If not, lookup a transition.
    object->map()->LookupTransition(*object, *name, &result);

    // If there is a transition, try to follow it.
    if (result.IsFound()) {
      Map* target = result.GetTransitionTarget();
      int descriptor_number = target->LastAdded();
      ASSERT(target->instance_descriptors()->GetKey(descriptor_number)
             ->Equals(*name));
      return TryAccessorTransition(*object, target, descriptor_number,
                                   component, *accessor, attributes);
    }
  }

  // If there is no transition yet, add a transition to the a new accessor pair
  // containing the accessor.  Allocate a new pair if there were no source
  // accessors.  Otherwise, copy the pair and modify the accessor.
  Handle<AccessorPair> accessors = source_accessors != NULL
      ? AccessorPair::Copy(Handle<AccessorPair>(source_accessors))
      : isolate->factory()->NewAccessorPair();
  accessors->set(component, *accessor);
  Handle<Map> new_map = CopyInsertDescriptor(Handle<Map>(object->map()),
                                             name, accessors, attributes);
  object->set_map(*new_map);
  return true;
}


MaybeObject* JSObject::DefineAccessor(AccessorInfo* info) {
  Isolate* isolate = GetIsolate();
  Name* name = Name::cast(info->name());
  // Check access rights if needed.
  if (IsAccessCheckNeeded() &&
      !isolate->MayNamedAccess(this, name, v8::ACCESS_SET)) {
    isolate->ReportFailedAccessCheck(this, v8::ACCESS_SET);
    RETURN_IF_SCHEDULED_EXCEPTION(isolate);
    return isolate->heap()->undefined_value();
  }

  if (IsJSGlobalProxy()) {
    Object* proto = GetPrototype();
    if (proto->IsNull()) return this;
    ASSERT(proto->IsJSGlobalObject());
    return JSObject::cast(proto)->DefineAccessor(info);
  }

  // Make sure that the top context does not change when doing callbacks or
  // interceptor calls.
  AssertNoContextChange ncc;

  // Try to flatten before operating on the string.
  if (name->IsString()) String::cast(name)->TryFlatten();

  if (!CanSetCallback(name)) return isolate->heap()->undefined_value();

  uint32_t index = 0;
  bool is_element = name->AsArrayIndex(&index);

  if (is_element) {
    if (IsJSArray()) return isolate->heap()->undefined_value();

    // Accessors overwrite previous callbacks (cf. with getters/setters).
    switch (GetElementsKind()) {
      case FAST_SMI_ELEMENTS:
      case FAST_ELEMENTS:
      case FAST_DOUBLE_ELEMENTS:
      case FAST_HOLEY_SMI_ELEMENTS:
      case FAST_HOLEY_ELEMENTS:
      case FAST_HOLEY_DOUBLE_ELEMENTS:
        break;
      case EXTERNAL_PIXEL_ELEMENTS:
      case EXTERNAL_BYTE_ELEMENTS:
      case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
      case EXTERNAL_SHORT_ELEMENTS:
      case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
      case EXTERNAL_INT_ELEMENTS:
      case EXTERNAL_UNSIGNED_INT_ELEMENTS:
      case EXTERNAL_FLOAT_ELEMENTS:
      case EXTERNAL_DOUBLE_ELEMENTS:
        // Ignore getters and setters on pixel and external array
        // elements.
        return isolate->heap()->undefined_value();
      case DICTIONARY_ELEMENTS:
        break;
      case NON_STRICT_ARGUMENTS_ELEMENTS:
        UNIMPLEMENTED();
        break;
    }

    MaybeObject* maybe_ok =
        SetElementCallback(index, info, info->property_attributes());
    if (maybe_ok->IsFailure()) return maybe_ok;
  } else {
    // Lookup the name.
    LookupResult result(isolate);
    LocalLookup(name, &result, true);
    // ES5 forbids turning a property into an accessor if it's not
    // configurable (that is IsDontDelete in ES3 and v8), see 8.6.1 (Table 5).
    if (result.IsFound() && (result.IsReadOnly() || result.IsDontDelete())) {
      return isolate->heap()->undefined_value();
    }

    MaybeObject* maybe_ok =
        SetPropertyCallback(name, info, info->property_attributes());
    if (maybe_ok->IsFailure()) return maybe_ok;
  }

  return this;
}


MaybeObject* JSObject::LookupAccessor(Name* name, AccessorComponent component) {
  Heap* heap = GetHeap();

  // Make sure that the top context does not change when doing callbacks or
  // interceptor calls.
  AssertNoContextChange ncc;

  // Check access rights if needed.
  if (IsAccessCheckNeeded() &&
      !heap->isolate()->MayNamedAccess(this, name, v8::ACCESS_HAS)) {
    heap->isolate()->ReportFailedAccessCheck(this, v8::ACCESS_HAS);
    RETURN_IF_SCHEDULED_EXCEPTION(heap->isolate());
    return heap->undefined_value();
  }

  // Make the lookup and include prototypes.
  uint32_t index = 0;
  if (name->AsArrayIndex(&index)) {
    for (Object* obj = this;
         obj != heap->null_value();
         obj = JSReceiver::cast(obj)->GetPrototype()) {
      if (obj->IsJSObject() && JSObject::cast(obj)->HasDictionaryElements()) {
        JSObject* js_object = JSObject::cast(obj);
        SeededNumberDictionary* dictionary = js_object->element_dictionary();
        int entry = dictionary->FindEntry(index);
        if (entry != SeededNumberDictionary::kNotFound) {
          Object* element = dictionary->ValueAt(entry);
          if (dictionary->DetailsAt(entry).type() == CALLBACKS &&
              element->IsAccessorPair()) {
            return AccessorPair::cast(element)->GetComponent(component);
          }
        }
      }
    }
  } else {
    for (Object* obj = this;
         obj != heap->null_value();
         obj = JSReceiver::cast(obj)->GetPrototype()) {
      LookupResult result(heap->isolate());
      JSReceiver::cast(obj)->LocalLookup(name, &result);
      if (result.IsFound()) {
        if (result.IsReadOnly()) return heap->undefined_value();
        if (result.IsPropertyCallbacks()) {
          Object* obj = result.GetCallbackObject();
          if (obj->IsAccessorPair()) {
            return AccessorPair::cast(obj)->GetComponent(component);
          }
        }
      }
    }
  }
  return heap->undefined_value();
}


Object* JSObject::SlowReverseLookup(Object* value) {
  if (HasFastProperties()) {
    int number_of_own_descriptors = map()->NumberOfOwnDescriptors();
    DescriptorArray* descs = map()->instance_descriptors();
    for (int i = 0; i < number_of_own_descriptors; i++) {
      if (descs->GetType(i) == FIELD) {
        Object* property = RawFastPropertyAt(descs->GetFieldIndex(i));
        if (FLAG_track_double_fields &&
            descs->GetDetails(i).representation().IsDouble()) {
          ASSERT(property->IsHeapNumber());
          if (value->IsNumber() && property->Number() == value->Number()) {
            return descs->GetKey(i);
          }
        } else if (property == value) {
          return descs->GetKey(i);
        }
      } else if (descs->GetType(i) == CONSTANT) {
        if (descs->GetConstant(i) == value) {
          return descs->GetKey(i);
        }
      }
    }
    return GetHeap()->undefined_value();
  } else {
    return property_dictionary()->SlowReverseLookup(value);
  }
}


MaybeObject* Map::RawCopy(int instance_size) {
  Map* result;
  MaybeObject* maybe_result =
      GetHeap()->AllocateMap(instance_type(), instance_size);
  if (!maybe_result->To(&result)) return maybe_result;

  result->set_prototype(prototype());
  result->set_constructor(constructor());
  result->set_bit_field(bit_field());
  result->set_bit_field2(bit_field2());
  int new_bit_field3 = bit_field3();
  new_bit_field3 = OwnsDescriptors::update(new_bit_field3, true);
  new_bit_field3 = NumberOfOwnDescriptorsBits::update(new_bit_field3, 0);
  new_bit_field3 = EnumLengthBits::update(new_bit_field3, kInvalidEnumCache);
  new_bit_field3 = Deprecated::update(new_bit_field3, false);
  new_bit_field3 = IsUnstable::update(new_bit_field3, false);
  result->set_bit_field3(new_bit_field3);
  return result;
}


MaybeObject* Map::CopyNormalized(PropertyNormalizationMode mode,
                                 NormalizedMapSharingMode sharing) {
  int new_instance_size = instance_size();
  if (mode == CLEAR_INOBJECT_PROPERTIES) {
    new_instance_size -= inobject_properties() * kPointerSize;
  }

  Map* result;
  MaybeObject* maybe_result = RawCopy(new_instance_size);
  if (!maybe_result->To(&result)) return maybe_result;

  if (mode != CLEAR_INOBJECT_PROPERTIES) {
    result->set_inobject_properties(inobject_properties());
  }

  result->set_is_shared(sharing == SHARED_NORMALIZED_MAP);
  result->set_dictionary_map(true);
  result->set_migration_target(false);

#ifdef VERIFY_HEAP
  if (FLAG_verify_heap && result->is_shared()) {
    result->SharedMapVerify();
  }
#endif

  return result;
}


Handle<Map> Map::CopyDropDescriptors(Handle<Map> map) {
  CALL_HEAP_FUNCTION(map->GetIsolate(), map->CopyDropDescriptors(), Map);
}


MaybeObject* Map::CopyDropDescriptors() {
  Map* result;
  MaybeObject* maybe_result = RawCopy(instance_size());
  if (!maybe_result->To(&result)) return maybe_result;

  // Please note instance_type and instance_size are set when allocated.
  result->set_inobject_properties(inobject_properties());
  result->set_unused_property_fields(unused_property_fields());

  result->set_pre_allocated_property_fields(pre_allocated_property_fields());
  result->set_is_shared(false);
  result->ClearCodeCache(GetHeap());
  NotifyLeafMapLayoutChange();
  return result;
}


MaybeObject* Map::ShareDescriptor(DescriptorArray* descriptors,
                                  Descriptor* descriptor) {
  // Sanity check. This path is only to be taken if the map owns its descriptor
  // array, implying that its NumberOfOwnDescriptors equals the number of
  // descriptors in the descriptor array.
  ASSERT(NumberOfOwnDescriptors() ==
         instance_descriptors()->number_of_descriptors());
  Map* result;
  MaybeObject* maybe_result = CopyDropDescriptors();
  if (!maybe_result->To(&result)) return maybe_result;

  Name* name = descriptor->GetKey();

  TransitionArray* transitions;
  MaybeObject* maybe_transitions =
      AddTransition(name, result, SIMPLE_TRANSITION);
  if (!maybe_transitions->To(&transitions)) return maybe_transitions;

  int old_size = descriptors->number_of_descriptors();

  DescriptorArray* new_descriptors;

  if (descriptors->NumberOfSlackDescriptors() > 0) {
    new_descriptors = descriptors;
    new_descriptors->Append(descriptor);
  } else {
    // Descriptor arrays grow by 50%.
    MaybeObject* maybe_descriptors = DescriptorArray::Allocate(
        old_size, old_size < 4 ? 1 : old_size / 2);
    if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;

    DescriptorArray::WhitenessWitness witness(new_descriptors);

    // Copy the descriptors, inserting a descriptor.
    for (int i = 0; i < old_size; ++i) {
      new_descriptors->CopyFrom(i, descriptors, i, witness);
    }

    new_descriptors->Append(descriptor, witness);

    if (old_size > 0) {
      // If the source descriptors had an enum cache we copy it. This ensures
      // that the maps to which we push the new descriptor array back can rely
      // on a cache always being available once it is set. If the map has more
      // enumerated descriptors than available in the original cache, the cache
      // will be lazily replaced by the extended cache when needed.
      if (descriptors->HasEnumCache()) {
        new_descriptors->CopyEnumCacheFrom(descriptors);
      }

      Map* map;
      // Replace descriptors by new_descriptors in all maps that share it.
      for (Object* current = GetBackPointer();
           !current->IsUndefined();
           current = map->GetBackPointer()) {
        map = Map::cast(current);
        if (map->instance_descriptors() != descriptors) break;
        map->set_instance_descriptors(new_descriptors);
      }

      set_instance_descriptors(new_descriptors);
    }
  }

  result->SetBackPointer(this);
  result->InitializeDescriptors(new_descriptors);
  ASSERT(result->NumberOfOwnDescriptors() == NumberOfOwnDescriptors() + 1);

  set_transitions(transitions);
  set_owns_descriptors(false);

  return result;
}


MaybeObject* Map::CopyReplaceDescriptors(DescriptorArray* descriptors,
                                         TransitionFlag flag,
                                         Name* name,
                                         SimpleTransitionFlag simple_flag) {
  ASSERT(descriptors->IsSortedNoDuplicates());

  Map* result;
  MaybeObject* maybe_result = CopyDropDescriptors();
  if (!maybe_result->To(&result)) return maybe_result;

  result->InitializeDescriptors(descriptors);

  if (flag == INSERT_TRANSITION && CanHaveMoreTransitions()) {
    TransitionArray* transitions;
    MaybeObject* maybe_transitions = AddTransition(name, result, simple_flag);
    if (!maybe_transitions->To(&transitions)) return maybe_transitions;
    set_transitions(transitions);
    result->SetBackPointer(this);
  } else if (flag != OMIT_TRANSITION_KEEP_REPRESENTATIONS) {
    descriptors->InitializeRepresentations(Representation::Tagged());
  }

  return result;
}


// Since this method is used to rewrite an existing transition tree, it can
// always insert transitions without checking.
MaybeObject* Map::CopyInstallDescriptors(int new_descriptor,
                                         DescriptorArray* descriptors) {
  ASSERT(descriptors->IsSortedNoDuplicates());

  Map* result;
  MaybeObject* maybe_result = CopyDropDescriptors();
  if (!maybe_result->To(&result)) return maybe_result;

  result->InitializeDescriptors(descriptors);
  result->SetNumberOfOwnDescriptors(new_descriptor + 1);

  int unused_property_fields = this->unused_property_fields();
  if (descriptors->GetDetails(new_descriptor).type() == FIELD) {
    unused_property_fields = this->unused_property_fields() - 1;
    if (unused_property_fields < 0) {
      unused_property_fields += JSObject::kFieldsAdded;
    }
  }

  result->set_unused_property_fields(unused_property_fields);
  result->set_owns_descriptors(false);

  Name* name = descriptors->GetKey(new_descriptor);
  TransitionArray* transitions;
  MaybeObject* maybe_transitions =
      AddTransition(name, result, SIMPLE_TRANSITION);
  if (!maybe_transitions->To(&transitions)) return maybe_transitions;

  set_transitions(transitions);
  result->SetBackPointer(this);

  return result;
}


MaybeObject* Map::CopyAsElementsKind(ElementsKind kind, TransitionFlag flag) {
  if (flag == INSERT_TRANSITION) {
    ASSERT(!HasElementsTransition() ||
        ((elements_transition_map()->elements_kind() == DICTIONARY_ELEMENTS ||
          IsExternalArrayElementsKind(
              elements_transition_map()->elements_kind())) &&
         (kind == DICTIONARY_ELEMENTS ||
          IsExternalArrayElementsKind(kind))));
    ASSERT(!IsFastElementsKind(kind) ||
           IsMoreGeneralElementsKindTransition(elements_kind(), kind));
    ASSERT(kind != elements_kind());
  }

  bool insert_transition =
      flag == INSERT_TRANSITION && !HasElementsTransition();

  if (insert_transition && owns_descriptors()) {
    // In case the map owned its own descriptors, share the descriptors and
    // transfer ownership to the new map.
    Map* new_map;
    MaybeObject* maybe_new_map = CopyDropDescriptors();
    if (!maybe_new_map->To(&new_map)) return maybe_new_map;

    MaybeObject* added_elements = set_elements_transition_map(new_map);
    if (added_elements->IsFailure()) return added_elements;

    new_map->set_elements_kind(kind);
    new_map->InitializeDescriptors(instance_descriptors());
    new_map->SetBackPointer(this);
    set_owns_descriptors(false);
    return new_map;
  }

  // In case the map did not own its own descriptors, a split is forced by
  // copying the map; creating a new descriptor array cell.
  // Create a new free-floating map only if we are not allowed to store it.
  Map* new_map;
  MaybeObject* maybe_new_map = Copy();
  if (!maybe_new_map->To(&new_map)) return maybe_new_map;

  new_map->set_elements_kind(kind);

  if (insert_transition) {
    MaybeObject* added_elements = set_elements_transition_map(new_map);
    if (added_elements->IsFailure()) return added_elements;
    new_map->SetBackPointer(this);
  }

  return new_map;
}


MaybeObject* Map::CopyForObserved() {
  ASSERT(!is_observed());

  // In case the map owned its own descriptors, share the descriptors and
  // transfer ownership to the new map.
  Map* new_map;
  MaybeObject* maybe_new_map;
  if (owns_descriptors()) {
    maybe_new_map = CopyDropDescriptors();
  } else {
    maybe_new_map = Copy();
  }
  if (!maybe_new_map->To(&new_map)) return maybe_new_map;

  TransitionArray* transitions;
  MaybeObject* maybe_transitions = AddTransition(GetHeap()->observed_symbol(),
                                                 new_map,
                                                 FULL_TRANSITION);
  if (!maybe_transitions->To(&transitions)) return maybe_transitions;
  set_transitions(transitions);

  new_map->set_is_observed(true);

  if (owns_descriptors()) {
    new_map->InitializeDescriptors(instance_descriptors());
    set_owns_descriptors(false);
  }

  new_map->SetBackPointer(this);
  return new_map;
}


MaybeObject* Map::CopyWithPreallocatedFieldDescriptors() {
  if (pre_allocated_property_fields() == 0) return CopyDropDescriptors();

  // If the map has pre-allocated properties always start out with a descriptor
  // array describing these properties.
  ASSERT(constructor()->IsJSFunction());
  JSFunction* ctor = JSFunction::cast(constructor());
  Map* map = ctor->initial_map();
  DescriptorArray* descriptors = map->instance_descriptors();

  int number_of_own_descriptors = map->NumberOfOwnDescriptors();
  DescriptorArray* new_descriptors;
  MaybeObject* maybe_descriptors =
      descriptors->CopyUpTo(number_of_own_descriptors);
  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;

  return CopyReplaceDescriptors(new_descriptors, OMIT_TRANSITION);
}


Handle<Map> Map::Copy(Handle<Map> map) {
  CALL_HEAP_FUNCTION(map->GetIsolate(), map->Copy(), Map);
}


MaybeObject* Map::Copy() {
  DescriptorArray* descriptors = instance_descriptors();
  DescriptorArray* new_descriptors;
  int number_of_own_descriptors = NumberOfOwnDescriptors();
  MaybeObject* maybe_descriptors =
      descriptors->CopyUpTo(number_of_own_descriptors);
  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;

  return CopyReplaceDescriptors(new_descriptors, OMIT_TRANSITION);
}


MaybeObject* Map::CopyAddDescriptor(Descriptor* descriptor,
                                    TransitionFlag flag) {
  DescriptorArray* descriptors = instance_descriptors();

  // Ensure the key is unique.
  MaybeObject* maybe_failure = descriptor->KeyToUniqueName();
  if (maybe_failure->IsFailure()) return maybe_failure;

  int old_size = NumberOfOwnDescriptors();
  int new_size = old_size + 1;

  if (flag == INSERT_TRANSITION &&
      owns_descriptors() &&
      CanHaveMoreTransitions()) {
    return ShareDescriptor(descriptors, descriptor);
  }

  DescriptorArray* new_descriptors;
  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size, 1);
  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;

  DescriptorArray::WhitenessWitness witness(new_descriptors);

  // Copy the descriptors, inserting a descriptor.
  for (int i = 0; i < old_size; ++i) {
    new_descriptors->CopyFrom(i, descriptors, i, witness);
  }

  if (old_size != descriptors->number_of_descriptors()) {
    new_descriptors->SetNumberOfDescriptors(new_size);
    new_descriptors->Set(old_size, descriptor, witness);
    new_descriptors->Sort();
  } else {
    new_descriptors->Append(descriptor, witness);
  }

  Name* key = descriptor->GetKey();
  return CopyReplaceDescriptors(new_descriptors, flag, key, SIMPLE_TRANSITION);
}


MaybeObject* Map::CopyInsertDescriptor(Descriptor* descriptor,
                                       TransitionFlag flag) {
  DescriptorArray* old_descriptors = instance_descriptors();

  // Ensure the key is unique.
  MaybeObject* maybe_result = descriptor->KeyToUniqueName();
  if (maybe_result->IsFailure()) return maybe_result;

  // We replace the key if it is already present.
  int index = old_descriptors->SearchWithCache(descriptor->GetKey(), this);
  if (index != DescriptorArray::kNotFound) {
    return CopyReplaceDescriptor(old_descriptors, descriptor, index, flag);
  }
  return CopyAddDescriptor(descriptor, flag);
}


MaybeObject* DescriptorArray::CopyUpToAddAttributes(
    int enumeration_index, PropertyAttributes attributes) {
  if (enumeration_index == 0) return GetHeap()->empty_descriptor_array();

  int size = enumeration_index;

  DescriptorArray* descriptors;
  MaybeObject* maybe_descriptors = Allocate(size);
  if (!maybe_descriptors->To(&descriptors)) return maybe_descriptors;
  DescriptorArray::WhitenessWitness witness(descriptors);

  if (attributes != NONE) {
    for (int i = 0; i < size; ++i) {
      Object* value = GetValue(i);
      PropertyDetails details = GetDetails(i);
      int mask = DONT_DELETE | DONT_ENUM;
      // READ_ONLY is an invalid attribute for JS setters/getters.
      if (details.type() != CALLBACKS || !value->IsAccessorPair()) {
        mask |= READ_ONLY;
      }
      details = details.CopyAddAttributes(
          static_cast<PropertyAttributes>(attributes & mask));
      Descriptor desc(GetKey(i), value, details);
      descriptors->Set(i, &desc, witness);
    }
  } else {
    for (int i = 0; i < size; ++i) {
      descriptors->CopyFrom(i, this, i, witness);
    }
  }

  if (number_of_descriptors() != enumeration_index) descriptors->Sort();

  return descriptors;
}


MaybeObject* Map::CopyReplaceDescriptor(DescriptorArray* descriptors,
                                        Descriptor* descriptor,
                                        int insertion_index,
                                        TransitionFlag flag) {
  // Ensure the key is unique.
  MaybeObject* maybe_failure = descriptor->KeyToUniqueName();
  if (maybe_failure->IsFailure()) return maybe_failure;

  Name* key = descriptor->GetKey();
  ASSERT(key == descriptors->GetKey(insertion_index));

  int new_size = NumberOfOwnDescriptors();
  ASSERT(0 <= insertion_index && insertion_index < new_size);

  ASSERT_LT(insertion_index, new_size);

  DescriptorArray* new_descriptors;
  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(new_size);
  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
  DescriptorArray::WhitenessWitness witness(new_descriptors);

  for (int i = 0; i < new_size; ++i) {
    if (i == insertion_index) {
      new_descriptors->Set(i, descriptor, witness);
    } else {
      new_descriptors->CopyFrom(i, descriptors, i, witness);
    }
  }

  // Re-sort if descriptors were removed.
  if (new_size != descriptors->length()) new_descriptors->Sort();

  SimpleTransitionFlag simple_flag =
      (insertion_index == descriptors->number_of_descriptors() - 1)
      ? SIMPLE_TRANSITION
      : FULL_TRANSITION;
  return CopyReplaceDescriptors(new_descriptors, flag, key, simple_flag);
}


void Map::UpdateCodeCache(Handle<Map> map,
                          Handle<Name> name,
                          Handle<Code> code) {
  Isolate* isolate = map->GetIsolate();
  CALL_HEAP_FUNCTION_VOID(isolate,
                          map->UpdateCodeCache(*name, *code));
}


MaybeObject* Map::UpdateCodeCache(Name* name, Code* code) {
  ASSERT(!is_shared() || code->allowed_in_shared_map_code_cache());

  // Allocate the code cache if not present.
  if (code_cache()->IsFixedArray()) {
    Object* result;
    { MaybeObject* maybe_result = GetHeap()->AllocateCodeCache();
      if (!maybe_result->ToObject(&result)) return maybe_result;
    }
    set_code_cache(result);
  }

  // Update the code cache.
  return CodeCache::cast(code_cache())->Update(name, code);
}


Object* Map::FindInCodeCache(Name* name, Code::Flags flags) {
  // Do a lookup if a code cache exists.
  if (!code_cache()->IsFixedArray()) {
    return CodeCache::cast(code_cache())->Lookup(name, flags);
  } else {
    return GetHeap()->undefined_value();
  }
}


int Map::IndexInCodeCache(Object* name, Code* code) {
  // Get the internal index if a code cache exists.
  if (!code_cache()->IsFixedArray()) {
    return CodeCache::cast(code_cache())->GetIndex(name, code);
  }
  return -1;
}


void Map::RemoveFromCodeCache(Name* name, Code* code, int index) {
  // No GC is supposed to happen between a call to IndexInCodeCache and
  // RemoveFromCodeCache so the code cache must be there.
  ASSERT(!code_cache()->IsFixedArray());
  CodeCache::cast(code_cache())->RemoveByIndex(name, code, index);
}


// An iterator over all map transitions in an descriptor array, reusing the map
// field of the contens array while it is running.
class IntrusiveMapTransitionIterator {
 public:
  explicit IntrusiveMapTransitionIterator(TransitionArray* transition_array)
      : transition_array_(transition_array) { }

  void Start() {
    ASSERT(!IsIterating());
    *TransitionArrayHeader() = Smi::FromInt(0);
  }

  bool IsIterating() {
    return (*TransitionArrayHeader())->IsSmi();
  }

  Map* Next() {
    ASSERT(IsIterating());
    int index = Smi::cast(*TransitionArrayHeader())->value();
    int number_of_transitions = transition_array_->number_of_transitions();
    while (index < number_of_transitions) {
      *TransitionArrayHeader() = Smi::FromInt(index + 1);
      return transition_array_->GetTarget(index);
    }

    *TransitionArrayHeader() = transition_array_->GetHeap()->fixed_array_map();
    return NULL;
  }

 private:
  Object** TransitionArrayHeader() {
    return HeapObject::RawField(transition_array_, TransitionArray::kMapOffset);
  }

  TransitionArray* transition_array_;
};


// An iterator over all prototype transitions, reusing the map field of the
// underlying array while it is running.
class IntrusivePrototypeTransitionIterator {
 public:
  explicit IntrusivePrototypeTransitionIterator(HeapObject* proto_trans)
      : proto_trans_(proto_trans) { }

  void Start() {
    ASSERT(!IsIterating());
    *Header() = Smi::FromInt(0);
  }

  bool IsIterating() {
    return (*Header())->IsSmi();
  }

  Map* Next() {
    ASSERT(IsIterating());
    int transitionNumber = Smi::cast(*Header())->value();
    if (transitionNumber < NumberOfTransitions()) {
      *Header() = Smi::FromInt(transitionNumber + 1);
      return GetTransition(transitionNumber);
    }
    *Header() = proto_trans_->GetHeap()->fixed_array_map();
    return NULL;
  }

 private:
  Object** Header() {
    return HeapObject::RawField(proto_trans_, FixedArray::kMapOffset);
  }

  int NumberOfTransitions() {
    FixedArray* proto_trans = reinterpret_cast<FixedArray*>(proto_trans_);
    Object* num = proto_trans->get(Map::kProtoTransitionNumberOfEntriesOffset);
    return Smi::cast(num)->value();
  }

  Map* GetTransition(int transitionNumber) {
    FixedArray* proto_trans = reinterpret_cast<FixedArray*>(proto_trans_);
    return Map::cast(proto_trans->get(IndexFor(transitionNumber)));
  }

  int IndexFor(int transitionNumber) {
    return Map::kProtoTransitionHeaderSize +
        Map::kProtoTransitionMapOffset +
        transitionNumber * Map::kProtoTransitionElementsPerEntry;
  }

  HeapObject* proto_trans_;
};


// To traverse the transition tree iteratively, we have to store two kinds of
// information in a map: The parent map in the traversal and which children of a
// node have already been visited. To do this without additional memory, we
// temporarily reuse two maps with known values:
//
//  (1) The map of the map temporarily holds the parent, and is restored to the
//      meta map afterwards.
//
//  (2) The info which children have already been visited depends on which part
//      of the map we currently iterate:
//
//    (a) If we currently follow normal map transitions, we temporarily store
//        the current index in the map of the FixedArray of the desciptor
//        array's contents, and restore it to the fixed array map afterwards.
//        Note that a single descriptor can have 0, 1, or 2 transitions.
//
//    (b) If we currently follow prototype transitions, we temporarily store
//        the current index in the map of the FixedArray holding the prototype
//        transitions, and restore it to the fixed array map afterwards.
//
// Note that the child iterator is just a concatenation of two iterators: One
// iterating over map transitions and one iterating over prototype transisitons.
class TraversableMap : public Map {
 public:
  // Record the parent in the traversal within this map. Note that this destroys
  // this map's map!
  void SetParent(TraversableMap* parent) { set_map_no_write_barrier(parent); }

  // Reset the current map's map, returning the parent previously stored in it.
  TraversableMap* GetAndResetParent() {
    TraversableMap* old_parent = static_cast<TraversableMap*>(map());
    set_map_no_write_barrier(GetHeap()->meta_map());
    return old_parent;
  }

  // Start iterating over this map's children, possibly destroying a FixedArray
  // map (see explanation above).
  void ChildIteratorStart() {
    if (HasTransitionArray()) {
      if (HasPrototypeTransitions()) {
        IntrusivePrototypeTransitionIterator(GetPrototypeTransitions()).Start();
      }

      IntrusiveMapTransitionIterator(transitions()).Start();
    }
  }

  // If we have an unvisited child map, return that one and advance. If we have
  // none, return NULL and reset any destroyed FixedArray maps.
  TraversableMap* ChildIteratorNext() {
    TransitionArray* transition_array = unchecked_transition_array();
    if (!transition_array->map()->IsSmi() &&
        !transition_array->IsTransitionArray()) {
      return NULL;
    }

    if (transition_array->HasPrototypeTransitions()) {
      HeapObject* proto_transitions =
          transition_array->UncheckedPrototypeTransitions();
      IntrusivePrototypeTransitionIterator proto_iterator(proto_transitions);
      if (proto_iterator.IsIterating()) {
        Map* next = proto_iterator.Next();
        if (next != NULL) return static_cast<TraversableMap*>(next);
      }
    }

    IntrusiveMapTransitionIterator transition_iterator(transition_array);
    if (transition_iterator.IsIterating()) {
      Map* next = transition_iterator.Next();
      if (next != NULL) return static_cast<TraversableMap*>(next);
    }

    return NULL;
  }
};


// Traverse the transition tree in postorder without using the C++ stack by
// doing pointer reversal.
void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
  TraversableMap* current = static_cast<TraversableMap*>(this);
  current->ChildIteratorStart();
  while (true) {
    TraversableMap* child = current->ChildIteratorNext();
    if (child != NULL) {
      child->ChildIteratorStart();
      child->SetParent(current);
      current = child;
    } else {
      TraversableMap* parent = current->GetAndResetParent();
      callback(current, data);
      if (current == this) break;
      current = parent;
    }
  }
}


MaybeObject* CodeCache::Update(Name* name, Code* code) {
  // The number of monomorphic stubs for normal load/store/call IC's can grow to
  // a large number and therefore they need to go into a hash table. They are
  // used to load global properties from cells.
  if (code->type() == Code::NORMAL) {
    // Make sure that a hash table is allocated for the normal load code cache.
    if (normal_type_cache()->IsUndefined()) {
      Object* result;
      { MaybeObject* maybe_result =
            CodeCacheHashTable::Allocate(GetHeap(),
                                         CodeCacheHashTable::kInitialSize);
        if (!maybe_result->ToObject(&result)) return maybe_result;
      }
      set_normal_type_cache(result);
    }
    return UpdateNormalTypeCache(name, code);
  } else {
    ASSERT(default_cache()->IsFixedArray());
    return UpdateDefaultCache(name, code);
  }
}


MaybeObject* CodeCache::UpdateDefaultCache(Name* name, Code* code) {
  // When updating the default code cache we disregard the type encoded in the
  // flags. This allows call constant stubs to overwrite call field
  // stubs, etc.
  Code::Flags flags = Code::RemoveTypeFromFlags(code->flags());

  // First check whether we can update existing code cache without
  // extending it.
  FixedArray* cache = default_cache();
  int length = cache->length();
  int deleted_index = -1;
  for (int i = 0; i < length; i += kCodeCacheEntrySize) {
    Object* key = cache->get(i);
    if (key->IsNull()) {
      if (deleted_index < 0) deleted_index = i;
      continue;
    }
    if (key->IsUndefined()) {
      if (deleted_index >= 0) i = deleted_index;
      cache->set(i + kCodeCacheEntryNameOffset, name);
      cache->set(i + kCodeCacheEntryCodeOffset, code);
      return this;
    }
    if (name->Equals(Name::cast(key))) {
      Code::Flags found =
          Code::cast(cache->get(i + kCodeCacheEntryCodeOffset))->flags();
      if (Code::RemoveTypeFromFlags(found) == flags) {
        cache->set(i + kCodeCacheEntryCodeOffset, code);
        return this;
      }
    }
  }

  // Reached the end of the code cache.  If there were deleted
  // elements, reuse the space for the first of them.
  if (deleted_index >= 0) {
    cache->set(deleted_index + kCodeCacheEntryNameOffset, name);
    cache->set(deleted_index + kCodeCacheEntryCodeOffset, code);
    return this;
  }

  // Extend the code cache with some new entries (at least one). Must be a
  // multiple of the entry size.
  int new_length = length + ((length >> 1)) + kCodeCacheEntrySize;
  new_length = new_length - new_length % kCodeCacheEntrySize;
  ASSERT((new_length % kCodeCacheEntrySize) == 0);
  Object* result;
  { MaybeObject* maybe_result = cache->CopySize(new_length);
    if (!maybe_result->ToObject(&result)) return maybe_result;
  }

  // Add the (name, code) pair to the new cache.
  cache = FixedArray::cast(result);
  cache->set(length + kCodeCacheEntryNameOffset, name);
  cache->set(length + kCodeCacheEntryCodeOffset, code);
  set_default_cache(cache);
  return this;
}


MaybeObject* CodeCache::UpdateNormalTypeCache(Name* name, Code* code) {
  // Adding a new entry can cause a new cache to be allocated.
  CodeCacheHashTable* cache = CodeCacheHashTable::cast(normal_type_cache());
  Object* new_cache;
  { MaybeObject* maybe_new_cache = cache->Put(name, code);
    if (!maybe_new_cache->ToObject(&new_cache)) return maybe_new_cache;
  }
  set_normal_type_cache(new_cache);
  return this;
}


Object* CodeCache::Lookup(Name* name, Code::Flags flags) {
  if (Code::ExtractTypeFromFlags(flags) == Code::NORMAL) {
    return LookupNormalTypeCache(name, flags);
  } else {
    return LookupDefaultCache(name, flags);
  }
}


Object* CodeCache::LookupDefaultCache(Name* name, Code::Flags flags) {
  FixedArray* cache = default_cache();
  int length = cache->length();
  for (int i = 0; i < length; i += kCodeCacheEntrySize) {
    Object* key = cache->get(i + kCodeCacheEntryNameOffset);
    // Skip deleted elements.
    if (key->IsNull()) continue;
    if (key->IsUndefined()) return key;
    if (name->Equals(Name::cast(key))) {
      Code* code = Code::cast(cache->get(i + kCodeCacheEntryCodeOffset));
      if (code->flags() == flags) {
        return code;
      }
    }
  }
  return GetHeap()->undefined_value();
}


Object* CodeCache::LookupNormalTypeCache(Name* name, Code::Flags flags) {
  if (!normal_type_cache()->IsUndefined()) {
    CodeCacheHashTable* cache = CodeCacheHashTable::cast(normal_type_cache());
    return cache->Lookup(name, flags);
  } else {
    return GetHeap()->undefined_value();
  }
}


int CodeCache::GetIndex(Object* name, Code* code) {
  if (code->type() == Code::NORMAL) {
    if (normal_type_cache()->IsUndefined()) return -1;
    CodeCacheHashTable* cache = CodeCacheHashTable::cast(normal_type_cache());
    return cache->GetIndex(Name::cast(name), code->flags());
  }

  FixedArray* array = default_cache();
  int len = array->length();
  for (int i = 0; i < len; i += kCodeCacheEntrySize) {
    if (array->get(i + kCodeCacheEntryCodeOffset) == code) return i + 1;
  }
  return -1;
}


void CodeCache::RemoveByIndex(Object* name, Code* code, int index) {
  if (code->type() == Code::NORMAL) {
    ASSERT(!normal_type_cache()->IsUndefined());
    CodeCacheHashTable* cache = CodeCacheHashTable::cast(normal_type_cache());
    ASSERT(cache->GetIndex(Name::cast(name), code->flags()) == index);
    cache->RemoveByIndex(index);
  } else {
    FixedArray* array = default_cache();
    ASSERT(array->length() >= index && array->get(index)->IsCode());
    // Use null instead of undefined for deleted elements to distinguish
    // deleted elements from unused elements.  This distinction is used
    // when looking up in the cache and when updating the cache.
    ASSERT_EQ(1, kCodeCacheEntryCodeOffset - kCodeCacheEntryNameOffset);
    array->set_null(index - 1);  // Name.
    array->set_null(index);  // Code.
  }
}


// The key in the code cache hash table consists of the property name and the
// code object. The actual match is on the name and the code flags. If a key
// is created using the flags and not a code object it can only be used for
// lookup not to create a new entry.
class CodeCacheHashTableKey : public HashTableKey {
 public:
  CodeCacheHashTableKey(Name* name, Code::Flags flags)
      : name_(name), flags_(flags), code_(NULL) { }

  CodeCacheHashTableKey(Name* name, Code* code)
      : name_(name),
        flags_(code->flags()),
        code_(code) { }


  bool IsMatch(Object* other) {
    if (!other->IsFixedArray()) return false;
    FixedArray* pair = FixedArray::cast(other);
    Name* name = Name::cast(pair->get(0));
    Code::Flags flags = Code::cast(pair->get(1))->flags();
    if (flags != flags_) {
      return false;
    }
    return name_->Equals(name);
  }

  static uint32_t NameFlagsHashHelper(Name* name, Code::Flags flags) {
    return name->Hash() ^ flags;
  }

  uint32_t Hash() { return NameFlagsHashHelper(name_, flags_); }

  uint32_t HashForObject(Object* obj) {
    FixedArray* pair = FixedArray::cast(obj);
    Name* name = Name::cast(pair->get(0));
    Code* code = Code::cast(pair->get(1));
    return NameFlagsHashHelper(name, code->flags());
  }

  MUST_USE_RESULT MaybeObject* AsObject(Heap* heap) {
    ASSERT(code_ != NULL);
    Object* obj;
    { MaybeObject* maybe_obj = heap->AllocateFixedArray(2);
      if (!maybe_obj->ToObject(&obj)) return maybe_obj;
    }
    FixedArray* pair = FixedArray::cast(obj);
    pair->set(0, name_);
    pair->set(1, code_);
    return pair;
  }

 private:
  Name* name_;
  Code::Flags flags_;
  // TODO(jkummerow): We should be able to get by without this.
  Code* code_;
};


Object* CodeCacheHashTable::Lookup(Name* name, Code::Flags flags) {
  CodeCacheHashTableKey key(name, flags);
  int entry = FindEntry(&key);
  if (entry == kNotFound) return GetHeap()->undefined_value();
  return get(EntryToIndex(entry) + 1);
}


MaybeObject* CodeCacheHashTable::Put(Name* name, Code* code) {
  CodeCacheHashTableKey key(name, code);
  Object* obj;
  { MaybeObject* maybe_obj = EnsureCapacity(1, &key);
    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
  }

  // Don't use |this|, as the table might have grown.
  CodeCacheHashTable* cache = reinterpret_cast<CodeCacheHashTable*>(obj);

  int entry = cache->FindInsertionEntry(key.Hash());
  Object* k;
  { MaybeObject* maybe_k = key.AsObject(GetHeap());
    if (!maybe_k->ToObject(&k)) return maybe_k;
  }

  cache->set(EntryToIndex(entry), k);
  cache->set(EntryToIndex(entry) + 1, code);
  cache->ElementAdded();
  return cache;
}


int CodeCacheHashTable::GetIndex(Name* name, Code::Flags flags) {
  CodeCacheHashTableKey key(name, flags);
  int entry = FindEntry(&key);
  return (entry == kNotFound) ? -1 : entry;
}


void CodeCacheHashTable::RemoveByIndex(int index) {
  ASSERT(index >= 0);
  Heap* heap = GetHeap();
  set(EntryToIndex(index), heap->the_hole_value());
  set(EntryToIndex(index) + 1, heap->the_hole_value());
  ElementRemoved();
}


void PolymorphicCodeCache::Update(Handle<PolymorphicCodeCache> cache,
                                  MapHandleList* maps,
                                  Code::Flags flags,
                                  Handle<Code> code) {
  Isolate* isolate = cache->GetIsolate();
  CALL_HEAP_FUNCTION_VOID(isolate, cache->Update(maps, flags, *code));
}


MaybeObject* PolymorphicCodeCache::Update(MapHandleList* maps,
                                          Code::Flags flags,
                                          Code* code) {
  // Initialize cache if necessary.
  if (cache()->IsUndefined()) {
    Object* result;
    { MaybeObject* maybe_result =
          PolymorphicCodeCacheHashTable::Allocate(
              GetHeap(),
              PolymorphicCodeCacheHashTable::kInitialSize);
      if (!maybe_result->ToObject(&result)) return maybe_result;
    }
    set_cache(result);
  } else {
    // This entry shouldn't be contained in the cache yet.
    ASSERT(PolymorphicCodeCacheHashTable::cast(cache())
               ->Lookup(maps, flags)->IsUndefined());
  }
  PolymorphicCodeCacheHashTable* hash_table =
      PolymorphicCodeCacheHashTable::cast(cache());
  Object* new_cache;
  { MaybeObject* maybe_new_cache = hash_table->Put(maps, flags, code);
    if (!maybe_new_cache->ToObject(&new_cache)) return maybe_new_cache;
  }
  set_cache(new_cache);
  return this;
}


Handle<Object> PolymorphicCodeCache::Lookup(MapHandleList* maps,
                                            Code::Flags flags) {
  if (!cache()->IsUndefined()) {
    PolymorphicCodeCacheHashTable* hash_table =
        PolymorphicCodeCacheHashTable::cast(cache());
    return Handle<Object>(hash_table->Lookup(maps, flags), GetIsolate());
  } else {
    return GetIsolate()->factory()->undefined_value();
  }
}


// Despite their name, object of this class are not stored in the actual
// hash table; instead they're temporarily used for lookups. It is therefore
// safe to have a weak (non-owning) pointer to a MapList as a member field.
class PolymorphicCodeCacheHashTableKey : public HashTableKey {
 public:
  // Callers must ensure that |maps| outlives the newly constructed object.
  PolymorphicCodeCacheHashTableKey(MapHandleList* maps, int code_flags)
      : maps_(maps),
        code_flags_(code_flags) {}

  bool IsMatch(Object* other) {
    MapHandleList other_maps(kDefaultListAllocationSize);
    int other_flags;
    FromObject(other, &other_flags, &other_maps);
    if (code_flags_ != other_flags) return false;
    if (maps_->length() != other_maps.length()) return false;
    // Compare just the hashes first because it's faster.
    int this_hash = MapsHashHelper(maps_, code_flags_);
    int other_hash = MapsHashHelper(&other_maps, other_flags);
    if (this_hash != other_hash) return false;

    // Full comparison: for each map in maps_, look for an equivalent map in
    // other_maps. This implementation is slow, but probably good enough for
    // now because the lists are short (<= 4 elements currently).
    for (int i = 0; i < maps_->length(); ++i) {
      bool match_found = false;
      for (int j = 0; j < other_maps.length(); ++j) {
        if (*(maps_->at(i)) == *(other_maps.at(j))) {
          match_found = true;
          break;
        }
      }
      if (!match_found) return false;
    }
    return true;
  }

  static uint32_t MapsHashHelper(MapHandleList* maps, int code_flags) {
    uint32_t hash = code_flags;
    for (int i = 0; i < maps->length(); ++i) {
      hash ^= maps->at(i)->Hash();
    }
    return hash;
  }

  uint32_t Hash() {
    return MapsHashHelper(maps_, code_flags_);
  }

  uint32_t HashForObject(Object* obj) {
    MapHandleList other_maps(kDefaultListAllocationSize);
    int other_flags;
    FromObject(obj, &other_flags, &other_maps);
    return MapsHashHelper(&other_maps, other_flags);
  }

  MUST_USE_RESULT MaybeObject* AsObject(Heap* heap) {
    Object* obj;
    // The maps in |maps_| must be copied to a newly allocated FixedArray,
    // both because the referenced MapList is short-lived, and because C++
    // objects can't be stored in the heap anyway.
    { MaybeObject* maybe_obj =
          heap->AllocateUninitializedFixedArray(maps_->length() + 1);
      if (!maybe_obj->ToObject(&obj)) return maybe_obj;
    }
    FixedArray* list = FixedArray::cast(obj);
    list->set(0, Smi::FromInt(code_flags_));
    for (int i = 0; i < maps_->length(); ++i) {
      list->set(i + 1, *maps_->at(i));
    }
    return list;
  }

 private:
  static MapHandleList* FromObject(Object* obj,
                                   int* code_flags,
                                   MapHandleList* maps) {
    FixedArray* list = FixedArray::cast(obj);
    maps->Rewind(0);
    *code_flags = Smi::cast(list->get(0))->value();
    for (int i = 1; i < list->length(); ++i) {
      maps->Add(Handle<Map>(Map::cast(list->get(i))));
    }
    return maps;
  }

  MapHandleList* maps_;  // weak.
  int code_flags_;
  static const int kDefaultListAllocationSize = kMaxKeyedPolymorphism + 1;
};


Object* PolymorphicCodeCacheHashTable::Lookup(MapHandleList* maps,
                                              int code_flags) {
  PolymorphicCodeCacheHashTableKey key(maps, code_flags);
  int entry = FindEntry(&key);
  if (entry == kNotFound) return GetHeap()->undefined_value();
  return get(EntryToIndex(entry) + 1);
}


MaybeObject* PolymorphicCodeCacheHashTable::Put(MapHandleList* maps,
                                                int code_flags,
                                                Code* code) {
  PolymorphicCodeCacheHashTableKey key(maps, code_flags);
  Object* obj;
  { MaybeObject* maybe_obj = EnsureCapacity(1, &key);
    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
  }
  PolymorphicCodeCacheHashTable* cache =
      reinterpret_cast<PolymorphicCodeCacheHashTable*>(obj);
  int entry = cache->FindInsertionEntry(key.Hash());
  { MaybeObject* maybe_obj = key.AsObject(GetHeap());
    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
  }
  cache->set(EntryToIndex(entry), obj);
  cache->set(EntryToIndex(entry) + 1, code);
  cache->ElementAdded();
  return cache;
}


MaybeObject* FixedArray::AddKeysFromJSArray(JSArray* array) {
  ElementsAccessor* accessor = array->GetElementsAccessor();
  MaybeObject* maybe_result =
      accessor->AddElementsToFixedArray(array, array, this);
  FixedArray* result;
  if (!maybe_result->To<FixedArray>(&result)) return maybe_result;
#ifdef DEBUG
  if (FLAG_enable_slow_asserts) {
    for (int i = 0; i < result->length(); i++) {
      Object* current = result->get(i);
      ASSERT(current->IsNumber() || current->IsName());
    }
  }
#endif
  return result;
}


MaybeObject* FixedArray::UnionOfKeys(FixedArray* other) {
  ElementsAccessor* accessor = ElementsAccessor::ForArray(other);
  MaybeObject* maybe_result =
      accessor->AddElementsToFixedArray(NULL, NULL, this, other);
  FixedArray* result;
  if (!maybe_result->To(&result)) return maybe_result;
#ifdef DEBUG
  if (FLAG_enable_slow_asserts) {
    for (int i = 0; i < result->length(); i++) {
      Object* current = result->get(i);
      ASSERT(current->IsNumber() || current->IsName());
    }
  }
#endif
  return result;
}


MaybeObject* FixedArray::CopySize(int new_length) {
  Heap* heap = GetHeap();
  if (new_length == 0) return heap->empty_fixed_array();
  Object* obj;
  { MaybeObject* maybe_obj = heap->AllocateFixedArray(new_length);
    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
  }
  FixedArray* result = FixedArray::cast(obj);
  // Copy the content
  DisallowHeapAllocation no_gc;
  int len = length();
  if (new_length < len) len = new_length;
  // We are taking the map from the old fixed array so the map is sure to
  // be an immortal immutable object.
  result->set_map_no_write_barrier(map());
  WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
  for (int i = 0; i < len; i++) {
    result->set(i, get(i), mode);
  }
  return result;
}


void FixedArray::CopyTo(int pos, FixedArray* dest, int dest_pos, int len) {
  DisallowHeapAllocation no_gc;
  WriteBarrierMode mode = dest->GetWriteBarrierMode(no_gc);
  for (int index = 0; index < len; index++) {
    dest->set(dest_pos+index, get(pos+index), mode);
  }
}


#ifdef DEBUG
bool FixedArray::IsEqualTo(FixedArray* other) {
  if (length() != other->length()) return false;
  for (int i = 0 ; i < length(); ++i) {
    if (get(i) != other->get(i)) return false;
  }
  return true;
}
#endif


MaybeObject* DescriptorArray::Allocate(int number_of_descriptors, int slack) {
  Heap* heap = Isolate::Current()->heap();
  // Do not use DescriptorArray::cast on incomplete object.
  int size = number_of_descriptors + slack;
  if (size == 0) return heap->empty_descriptor_array();
  FixedArray* result;
  // Allocate the array of keys.
  MaybeObject* maybe_array = heap->AllocateFixedArray(LengthFor(size));
  if (!maybe_array->To(&result)) return maybe_array;

  result->set(kDescriptorLengthIndex, Smi::FromInt(number_of_descriptors));
  result->set(kEnumCacheIndex, Smi::FromInt(0));
  return result;
}


void DescriptorArray::ClearEnumCache() {
  set(kEnumCacheIndex, Smi::FromInt(0));
}


void DescriptorArray::SetEnumCache(FixedArray* bridge_storage,
                                   FixedArray* new_cache,
                                   Object* new_index_cache) {
  ASSERT(bridge_storage->length() >= kEnumCacheBridgeLength);
  ASSERT(new_index_cache->IsSmi() || new_index_cache->IsFixedArray());
  ASSERT(!IsEmpty());
  ASSERT(!HasEnumCache() || new_cache->length() > GetEnumCache()->length());
  FixedArray::cast(bridge_storage)->
    set(kEnumCacheBridgeCacheIndex, new_cache);
  FixedArray::cast(bridge_storage)->
    set(kEnumCacheBridgeIndicesCacheIndex, new_index_cache);
  set(kEnumCacheIndex, bridge_storage);
}


void DescriptorArray::CopyFrom(int dst_index,
                               DescriptorArray* src,
                               int src_index,
                               const WhitenessWitness& witness) {
  Object* value = src->GetValue(src_index);
  PropertyDetails details = src->GetDetails(src_index);
  Descriptor desc(src->GetKey(src_index), value, details);
  Set(dst_index, &desc, witness);
}


// Generalize the |other| descriptor array by merging it into the (at least
// partly) updated |this| descriptor array.
// The method merges two descriptor array in three parts. Both descriptor arrays
// are identical up to |verbatim|. They also overlap in keys up to |valid|.
// Between |verbatim| and |valid|, the resulting descriptor type as well as the
// representation are generalized from both |this| and |other|. Beyond |valid|,
// the descriptors are copied verbatim from |other| up to |new_size|.
// In case of incompatible types, the type and representation of |other| is
// used.
MaybeObject* DescriptorArray::Merge(int verbatim,
                                    int valid,
                                    int new_size,
                                    DescriptorArray* other) {
  ASSERT(verbatim <= valid);
  ASSERT(valid <= new_size);

  DescriptorArray* result;
  // Allocate a new descriptor array large enough to hold the required
  // descriptors, with minimally the exact same size as this descriptor array.
  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(
      new_size, Max(new_size, other->number_of_descriptors()) - new_size);
  if (!maybe_descriptors->To(&result)) return maybe_descriptors;
  ASSERT(result->length() > length() ||
         result->NumberOfSlackDescriptors() > 0 ||
         result->number_of_descriptors() == other->number_of_descriptors());
  ASSERT(result->number_of_descriptors() == new_size);

  DescriptorArray::WhitenessWitness witness(result);

  int descriptor;

  // 0 -> |verbatim|
  int current_offset = 0;
  for (descriptor = 0; descriptor < verbatim; descriptor++) {
    if (GetDetails(descriptor).type() == FIELD) current_offset++;
    result->CopyFrom(descriptor, this, descriptor, witness);
  }

  // |verbatim| -> |valid|
  for (; descriptor < valid; descriptor++) {
    Name* key = GetKey(descriptor);
    PropertyDetails details = GetDetails(descriptor);
    PropertyDetails other_details = other->GetDetails(descriptor);

    if (details.type() == FIELD || other_details.type() == FIELD ||
        (details.type() == CONSTANT &&
         other_details.type() == CONSTANT &&
         GetValue(descriptor) != other->GetValue(descriptor))) {
      Representation representation =
          details.representation().generalize(other_details.representation());
      FieldDescriptor d(key,
                        current_offset++,
                        other_details.attributes(),
                        representation);
      result->Set(descriptor, &d, witness);
    } else {
      result->CopyFrom(descriptor, other, descriptor, witness);
    }
  }

  // |valid| -> |new_size|
  for (; descriptor < new_size; descriptor++) {
    PropertyDetails details = other->GetDetails(descriptor);
    if (details.type() == FIELD) {
      Name* key = other->GetKey(descriptor);
      FieldDescriptor d(key,
                        current_offset++,
                        details.attributes(),
                        details.representation());
      result->Set(descriptor, &d, witness);
    } else {
      result->CopyFrom(descriptor, other, descriptor, witness);
    }
  }

  result->Sort();
  return result;
}


// Checks whether a merge of |other| into |this| would return a copy of |this|.
bool DescriptorArray::IsMoreGeneralThan(int verbatim,
                                        int valid,
                                        int new_size,
                                        DescriptorArray* other) {
  ASSERT(verbatim <= valid);
  ASSERT(valid <= new_size);
  if (valid != new_size) return false;

  for (int descriptor = verbatim; descriptor < valid; descriptor++) {
    PropertyDetails details = GetDetails(descriptor);
    PropertyDetails other_details = other->GetDetails(descriptor);
    if (!other_details.representation().fits_into(details.representation())) {
      return false;
    }
    if (details.type() == CONSTANT) {
      if (other_details.type() != CONSTANT) return false;
      if (GetValue(descriptor) != other->GetValue(descriptor)) return false;
    }
  }

  return true;
}


// We need the whiteness witness since sort will reshuffle the entries in the
// descriptor array. If the descriptor array were to be black, the shuffling
// would move a slot that was already recorded as pointing into an evacuation
// candidate. This would result in missing updates upon evacuation.
void DescriptorArray::Sort() {
  // In-place heap sort.
  int len = number_of_descriptors();
  // Reset sorting since the descriptor array might contain invalid pointers.
  for (int i = 0; i < len; ++i) SetSortedKey(i, i);
  // Bottom-up max-heap construction.
  // Index of the last node with children
  const int max_parent_index = (len / 2) - 1;
  for (int i = max_parent_index; i >= 0; --i) {
    int parent_index = i;
    const uint32_t parent_hash = GetSortedKey(i)->Hash();
    while (parent_index <= max_parent_index) {
      int child_index = 2 * parent_index + 1;
      uint32_t child_hash = GetSortedKey(child_index)->Hash();
      if (child_index + 1 < len) {
        uint32_t right_child_hash = GetSortedKey(child_index + 1)->Hash();
        if (right_child_hash > child_hash) {
          child_index++;
          child_hash = right_child_hash;
        }
      }
      if (child_hash <= parent_hash) break;
      SwapSortedKeys(parent_index, child_index);
      // Now element at child_index could be < its children.
      parent_index = child_index;  // parent_hash remains correct.
    }
  }

  // Extract elements and create sorted array.
  for (int i = len - 1; i > 0; --i) {
    // Put max element at the back of the array.
    SwapSortedKeys(0, i);
    // Shift down the new top element.
    int parent_index = 0;
    const uint32_t parent_hash = GetSortedKey(parent_index)->Hash();
    const int max_parent_index = (i / 2) - 1;
    while (parent_index <= max_parent_index) {
      int child_index = parent_index * 2 + 1;
      uint32_t child_hash = GetSortedKey(child_index)->Hash();
      if (child_index + 1 < i) {
        uint32_t right_child_hash = GetSortedKey(child_index + 1)->Hash();
        if (right_child_hash > child_hash) {
          child_index++;
          child_hash = right_child_hash;
        }
      }
      if (child_hash <= parent_hash) break;
      SwapSortedKeys(parent_index, child_index);
      parent_index = child_index;
    }
  }
  ASSERT(IsSortedNoDuplicates());
}


Handle<AccessorPair> AccessorPair::Copy(Handle<AccessorPair> pair) {
  Handle<AccessorPair> copy = pair->GetIsolate()->factory()->NewAccessorPair();
  copy->set_getter(pair->getter());
  copy->set_setter(pair->setter());
  return copy;
}


Object* AccessorPair::GetComponent(AccessorComponent component) {
  Object* accessor = get(component);
  return accessor->IsTheHole() ? GetHeap()->undefined_value() : accessor;
}


MaybeObject* DeoptimizationInputData::Allocate(int deopt_entry_count,
                                               PretenureFlag pretenure) {
  ASSERT(deopt_entry_count > 0);
  return HEAP->AllocateFixedArray(LengthFor(deopt_entry_count),
                                  pretenure);
}


MaybeObject* DeoptimizationOutputData::Allocate(int number_of_deopt_points,
                                                PretenureFlag pretenure) {
  if (number_of_deopt_points == 0) return HEAP->empty_fixed_array();
  return HEAP->AllocateFixedArray(LengthOfFixedArray(number_of_deopt_points),
                                  pretenure);
}


#ifdef DEBUG
bool DescriptorArray::IsEqualTo(DescriptorArray* other) {
  if (IsEmpty()) return other->IsEmpty();
  if (other->IsEmpty()) return false;
  if (length() != other->length()) return false;
  for (int i = 0; i < length(); ++i) {
    if (get(i) != other->get(i)) return false;
  }
  return true;
}
#endif


bool String::LooksValid() {
  if (!Isolate::Current()->heap()->Contains(this)) return false;
  return true;
}


String::FlatContent String::GetFlatContent() {
  ASSERT(!AllowHeapAllocation::IsAllowed());
  int length = this->length();
  StringShape shape(this);
  String* string = this;
  int offset = 0;
  if (shape.representation_tag() == kConsStringTag) {
    ConsString* cons = ConsString::cast(string);
    if (cons->second()->length() != 0) {
      return FlatContent();
    }
    string = cons->first();
    shape = StringShape(string);
  }
  if (shape.representation_tag() == kSlicedStringTag) {
    SlicedString* slice = SlicedString::cast(string);
    offset = slice->offset();
    string = slice->parent();
    shape = StringShape(string);
    ASSERT(shape.representation_tag() != kConsStringTag &&
           shape.representation_tag() != kSlicedStringTag);
  }
  if (shape.encoding_tag() == kOneByteStringTag) {
    const uint8_t* start;
    if (shape.representation_tag() == kSeqStringTag) {
      start = SeqOneByteString::cast(string)->GetChars();
    } else {
      start = ExternalAsciiString::cast(string)->GetChars();
    }
    return FlatContent(Vector<const uint8_t>(start + offset, length));
  } else {
    ASSERT(shape.encoding_tag() == kTwoByteStringTag);
    const uc16* start;
    if (shape.representation_tag() == kSeqStringTag) {
      start = SeqTwoByteString::cast(string)->GetChars();
    } else {
      start = ExternalTwoByteString::cast(string)->GetChars();
    }
    return FlatContent(Vector<const uc16>(start + offset, length));
  }
}


SmartArrayPointer<char> String::ToCString(AllowNullsFlag allow_nulls,
                                          RobustnessFlag robust_flag,
                                          int offset,
                                          int length,
                                          int* length_return) {
  if (robust_flag == ROBUST_STRING_TRAVERSAL && !LooksValid()) {
    return SmartArrayPointer<char>(NULL);
  }
  Heap* heap = GetHeap();

  // Negative length means the to the end of the string.
  if (length < 0) length = kMaxInt - offset;

  // Compute the size of the UTF-8 string. Start at the specified offset.
  Access<ConsStringIteratorOp> op(
      heap->isolate()->objects_string_iterator());
  StringCharacterStream stream(this, op.value(), offset);
  int character_position = offset;
  int utf8_bytes = 0;
  int last = unibrow::Utf16::kNoPreviousCharacter;
  while (stream.HasMore() && character_position++ < offset + length) {
    uint16_t character = stream.GetNext();
    utf8_bytes += unibrow::Utf8::Length(character, last);
    last = character;
  }

  if (length_return) {
    *length_return = utf8_bytes;
  }

  char* result = NewArray<char>(utf8_bytes + 1);

  // Convert the UTF-16 string to a UTF-8 buffer. Start at the specified offset.
  stream.Reset(this, offset);
  character_position = offset;
  int utf8_byte_position = 0;
  last = unibrow::Utf16::kNoPreviousCharacter;
  while (stream.HasMore() && character_position++ < offset + length) {
    uint16_t character = stream.GetNext();
    if (allow_nulls == DISALLOW_NULLS && character == 0) {
      character = ' ';
    }
    utf8_byte_position +=
        unibrow::Utf8::Encode(result + utf8_byte_position, character, last);
    last = character;
  }
  result[utf8_byte_position] = 0;
  return SmartArrayPointer<char>(result);
}


SmartArrayPointer<char> String::ToCString(AllowNullsFlag allow_nulls,
                                          RobustnessFlag robust_flag,
                                          int* length_return) {
  return ToCString(allow_nulls, robust_flag, 0, -1, length_return);
}


const uc16* String::GetTwoByteData() {
  return GetTwoByteData(0);
}


const uc16* String::GetTwoByteData(unsigned start) {
  ASSERT(!IsOneByteRepresentationUnderneath());
  switch (StringShape(this).representation_tag()) {
    case kSeqStringTag:
      return SeqTwoByteString::cast(this)->SeqTwoByteStringGetData(start);
    case kExternalStringTag:
      return ExternalTwoByteString::cast(this)->
        ExternalTwoByteStringGetData(start);
    case kSlicedStringTag: {
      SlicedString* slice = SlicedString::cast(this);
      return slice->parent()->GetTwoByteData(start + slice->offset());
    }
    case kConsStringTag:
      UNREACHABLE();
      return NULL;
  }
  UNREACHABLE();
  return NULL;
}


SmartArrayPointer<uc16> String::ToWideCString(RobustnessFlag robust_flag) {
  if (robust_flag == ROBUST_STRING_TRAVERSAL && !LooksValid()) {
    return SmartArrayPointer<uc16>();
  }
  Heap* heap = GetHeap();

  Access<ConsStringIteratorOp> op(
      heap->isolate()->objects_string_iterator());
  StringCharacterStream stream(this, op.value());

  uc16* result = NewArray<uc16>(length() + 1);

  int i = 0;
  while (stream.HasMore()) {
    uint16_t character = stream.GetNext();
    result[i++] = character;
  }
  result[i] = 0;
  return SmartArrayPointer<uc16>(result);
}


const uc16* SeqTwoByteString::SeqTwoByteStringGetData(unsigned start) {
  return reinterpret_cast<uc16*>(
      reinterpret_cast<char*>(this) - kHeapObjectTag + kHeaderSize) + start;
}


void Relocatable::PostGarbageCollectionProcessing() {
  Isolate* isolate = Isolate::Current();
  Relocatable* current = isolate->relocatable_top();
  while (current != NULL) {
    current->PostGarbageCollection();
    current = current->prev_;
  }
}


// Reserve space for statics needing saving and restoring.
int Relocatable::ArchiveSpacePerThread() {
  return sizeof(Isolate::Current()->relocatable_top());
}


// Archive statics that are thread local.
char* Relocatable::ArchiveState(Isolate* isolate, char* to) {
  *reinterpret_cast<Relocatable**>(to) = isolate->relocatable_top();
  isolate->set_relocatable_top(NULL);
  return to + ArchiveSpacePerThread();
}


// Restore statics that are thread local.
char* Relocatable::RestoreState(Isolate* isolate, char* from) {
  isolate->set_relocatable_top(*reinterpret_cast<Relocatable**>(from));
  return from + ArchiveSpacePerThread();
}


char* Relocatable::Iterate(ObjectVisitor* v, char* thread_storage) {
  Relocatable* top = *reinterpret_cast<Relocatable**>(thread_storage);
  Iterate(v, top);
  return thread_storage + ArchiveSpacePerThread();
}


void Relocatable::Iterate(ObjectVisitor* v) {
  Isolate* isolate = Isolate::Current();
  Iterate(v, isolate->relocatable_top());
}


void Relocatable::Iterate(ObjectVisitor* v, Relocatable* top) {
  Relocatable* current = top;
  while (current != NULL) {
    current->IterateInstance(v);
    current = current->prev_;
  }
}


FlatStringReader::FlatStringReader(Isolate* isolate, Handle<String> str)
    : Relocatable(isolate),
      str_(str.location()),
      length_(str->length()) {
  PostGarbageCollection();
}


FlatStringReader::FlatStringReader(Isolate* isolate, Vector<const char> input)
    : Relocatable(isolate),
      str_(0),
      is_ascii_(true),
      length_(input.length()),
      start_(input.start()) { }


void FlatStringReader::PostGarbageCollection() {
  if (str_ == NULL) return;
  Handle<String> str(str_);
  ASSERT(str->IsFlat());
  DisallowHeapAllocation no_gc;
  // This does not actually prevent the vector from being relocated later.
  String::FlatContent content = str->GetFlatContent();
  ASSERT(content.IsFlat());
  is_ascii_ = content.IsAscii();
  if (is_ascii_) {
    start_ = content.ToOneByteVector().start();
  } else {
    start_ = content.ToUC16Vector().start();
  }
}


String* ConsStringIteratorOp::Operate(String* string,
                                      unsigned* offset_out,
                                      int32_t* type_out,
                                      unsigned* length_out) {
  ASSERT(string->IsConsString());
  ConsString* cons_string = ConsString::cast(string);
  // Set up search data.
  root_ = cons_string;
  consumed_ = *offset_out;
  // Now search.
  return Search(offset_out, type_out, length_out);
}


String* ConsStringIteratorOp::Search(unsigned* offset_out,
                                     int32_t* type_out,
                                     unsigned* length_out) {
  ConsString* cons_string = root_;
  // Reset the stack, pushing the root string.
  depth_ = 1;
  maximum_depth_ = 1;
  frames_[0] = cons_string;
  const unsigned consumed = consumed_;
  unsigned offset = 0;
  while (true) {
    // Loop until the string is found which contains the target offset.
    String* string = cons_string->first();
    unsigned length = string->length();
    int32_t type;
    if (consumed < offset + length) {
      // Target offset is in the left branch.
      // Keep going if we're still in a ConString.
      type = string->map()->instance_type();
      if ((type & kStringRepresentationMask) == kConsStringTag) {
        cons_string = ConsString::cast(string);
        PushLeft(cons_string);
        continue;
      }
      // Tell the stack we're done decending.
      AdjustMaximumDepth();
    } else {
      // Descend right.
      // Update progress through the string.
      offset += length;
      // Keep going if we're still in a ConString.
      string = cons_string->second();
      type = string->map()->instance_type();
      if ((type & kStringRepresentationMask) == kConsStringTag) {
        cons_string = ConsString::cast(string);
        PushRight(cons_string);
        // TODO(dcarney) Add back root optimization.
        continue;
      }
      // Need this to be updated for the current string.
      length = string->length();
      // Account for the possibility of an empty right leaf.
      // This happens only if we have asked for an offset outside the string.
      if (length == 0) {
        // Reset depth so future operations will return null immediately.
        Reset();
        return NULL;
      }
      // Tell the stack we're done decending.
      AdjustMaximumDepth();
      // Pop stack so next iteration is in correct place.
      Pop();
    }
    ASSERT(length != 0);
    // Adjust return values and exit.
    consumed_ = offset + length;
    *offset_out = consumed - offset;
    *type_out = type;
    *length_out = length;
    return string;
  }
  UNREACHABLE();
  return NULL;
}


String* ConsStringIteratorOp::NextLeaf(bool* blew_stack,
                                       int32_t* type_out,
                                       unsigned* length_out) {
  while (true) {
    // Tree traversal complete.
    if (depth_ == 0) {
      *blew_stack = false;
      return NULL;
    }
    // We've lost track of higher nodes.
    if (maximum_depth_ - depth_ == kStackSize) {
      *blew_stack = true;
      return NULL;
    }
    // Go right.
    ConsString* cons_string = frames_[OffsetForDepth(depth_ - 1)];
    String* string = cons_string->second();
    int32_t type = string->map()->instance_type();
    if ((type & kStringRepresentationMask) != kConsStringTag) {
      // Pop stack so next iteration is in correct place.
      Pop();
      unsigned length = static_cast<unsigned>(string->length());
      // Could be a flattened ConsString.
      if (length == 0) continue;
      *length_out = length;
      *type_out = type;
      consumed_ += length;
      return string;
    }
    cons_string = ConsString::cast(string);
    // TODO(dcarney) Add back root optimization.
    PushRight(cons_string);
    // Need to traverse all the way left.
    while (true) {
      // Continue left.
      string = cons_string->first();
      type = string->map()->instance_type();
      if ((type & kStringRepresentationMask) != kConsStringTag) {
        AdjustMaximumDepth();
        unsigned length = static_cast<unsigned>(string->length());
        ASSERT(length != 0);
        *length_out = length;
        *type_out = type;
        consumed_ += length;
        return string;
      }
      cons_string = ConsString::cast(string);
      PushLeft(cons_string);
    }
  }
  UNREACHABLE();
  return NULL;
}


uint16_t ConsString::ConsStringGet(int index) {
  ASSERT(index >= 0 && index < this->length());

  // Check for a flattened cons string
  if (second()->length() == 0) {
    String* left = first();
    return left->Get(index);
  }

  String* string = String::cast(this);

  while (true) {
    if (StringShape(string).IsCons()) {
      ConsString* cons_string = ConsString::cast(string);
      String* left = cons_string->first();
      if (left->length() > index) {
        string = left;
      } else {
        index -= left->length();
        string = cons_string->second();
      }
    } else {
      return string->Get(index);
    }
  }

  UNREACHABLE();
  return 0;
}


uint16_t SlicedString::SlicedStringGet(int index) {
  return parent()->Get(offset() + index);
}


template <typename sinkchar>
void String::WriteToFlat(String* src,
                         sinkchar* sink,
                         int f,
                         int t) {
  String* source = src;
  int from = f;
  int to = t;
  while (true) {
    ASSERT(0 <= from && from <= to && to <= source->length());
    switch (StringShape(source).full_representation_tag()) {
      case kOneByteStringTag | kExternalStringTag: {
        CopyChars(sink,
                  ExternalAsciiString::cast(source)->GetChars() + from,
                  to - from);
        return;
      }
      case kTwoByteStringTag | kExternalStringTag: {
        const uc16* data =
            ExternalTwoByteString::cast(source)->GetChars();
        CopyChars(sink,
                  data + from,
                  to - from);
        return;
      }
      case kOneByteStringTag | kSeqStringTag: {
        CopyChars(sink,
                  SeqOneByteString::cast(source)->GetChars() + from,
                  to - from);
        return;
      }
      case kTwoByteStringTag | kSeqStringTag: {
        CopyChars(sink,
                  SeqTwoByteString::cast(source)->GetChars() + from,
                  to - from);
        return;
      }
      case kOneByteStringTag | kConsStringTag:
      case kTwoByteStringTag | kConsStringTag: {
        ConsString* cons_string = ConsString::cast(source);
        String* first = cons_string->first();
        int boundary = first->length();
        if (to - boundary >= boundary - from) {
          // Right hand side is longer.  Recurse over left.
          if (from < boundary) {
            WriteToFlat(first, sink, from, boundary);
            sink += boundary - from;
            from = 0;
          } else {
            from -= boundary;
          }
          to -= boundary;
          source = cons_string->second();
        } else {
          // Left hand side is longer.  Recurse over right.
          if (to > boundary) {
            String* second = cons_string->second();
            // When repeatedly appending to a string, we get a cons string that
            // is unbalanced to the left, a list, essentially.  We inline the
            // common case of sequential ascii right child.
            if (to - boundary == 1) {
              sink[boundary - from] = static_cast<sinkchar>(second->Get(0));
            } else if (second->IsSeqOneByteString()) {
              CopyChars(sink + boundary - from,
                        SeqOneByteString::cast(second)->GetChars(),
                        to - boundary);
            } else {
              WriteToFlat(second,
                          sink + boundary - from,
                          0,
                          to - boundary);
            }
            to = boundary;
          }
          source = first;
        }
        break;
      }
      case kOneByteStringTag | kSlicedStringTag:
      case kTwoByteStringTag | kSlicedStringTag: {
        SlicedString* slice = SlicedString::cast(