xref: /external/v8/src/runtime.cc

// Copyright 2012 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 <stdlib.h>

#include "v8.h"

#include "accessors.h"
#include "api.h"
#include "arguments.h"
#include "bootstrapper.h"
#include "codegen.h"
#include "compilation-cache.h"
#include "compiler.h"
#include "cpu.h"
#include "dateparser-inl.h"
#include "debug.h"
#include "deoptimizer.h"
#include "date.h"
#include "execution.h"
#include "global-handles.h"
#include "isolate-inl.h"
#include "jsregexp.h"
#include "json-parser.h"
#include "liveedit.h"
#include "liveobjectlist-inl.h"
#include "misc-intrinsics.h"
#include "parser.h"
#include "platform.h"
#include "runtime-profiler.h"
#include "runtime.h"
#include "scopeinfo.h"
#include "smart-array-pointer.h"
#include "string-search.h"
#include "stub-cache.h"
#include "v8threads.h"
#include "vm-state-inl.h"

namespace v8 {
namespace internal {


#define RUNTIME_ASSERT(value) \
  if (!(value)) return isolate->ThrowIllegalOperation();

// Cast the given object to a value of the specified type and store
// it in a variable with the given name.  If the object is not of the
// expected type call IllegalOperation and return.
#define CONVERT_ARG_CHECKED(Type, name, index)                       \
  RUNTIME_ASSERT(args[index]->Is##Type());                           \
  Type* name = Type::cast(args[index]);

#define CONVERT_ARG_HANDLE_CHECKED(Type, name, index)                \
  RUNTIME_ASSERT(args[index]->Is##Type());                           \
  Handle<Type> name = args.at<Type>(index);

// Cast the given object to a boolean and store it in a variable with
// the given name.  If the object is not a boolean call IllegalOperation
// and return.
#define CONVERT_BOOLEAN_ARG_CHECKED(name, index)                     \
  RUNTIME_ASSERT(args[index]->IsBoolean());                          \
  bool name = args[index]->IsTrue();

// Cast the given argument to a Smi and store its value in an int variable
// with the given name.  If the argument is not a Smi call IllegalOperation
// and return.
#define CONVERT_SMI_ARG_CHECKED(name, index)                         \
  RUNTIME_ASSERT(args[index]->IsSmi());                              \
  int name = args.smi_at(index);

// Cast the given argument to a double and store it in a variable with
// the given name.  If the argument is not a number (as opposed to
// the number not-a-number) call IllegalOperation and return.
#define CONVERT_DOUBLE_ARG_CHECKED(name, index)                      \
  RUNTIME_ASSERT(args[index]->IsNumber());                           \
  double name = args.number_at(index);

// Call the specified converter on the object *comand store the result in
// a variable of the specified type with the given name.  If the
// object is not a Number call IllegalOperation and return.
#define CONVERT_NUMBER_CHECKED(type, name, Type, obj)                \
  RUNTIME_ASSERT(obj->IsNumber());                                   \
  type name = NumberTo##Type(obj);


// Cast the given argument to PropertyDetails and store its value in a
// variable with the given name.  If the argument is not a Smi call
// IllegalOperation and return.
#define CONVERT_PROPERTY_DETAILS_CHECKED(name, index)                \
  RUNTIME_ASSERT(args[index]->IsSmi());                              \
  PropertyDetails name = PropertyDetails(Smi::cast(args[index]));


// Assert that the given argument has a valid value for a StrictModeFlag
// and store it in a StrictModeFlag variable with the given name.
#define CONVERT_STRICT_MODE_ARG_CHECKED(name, index)                 \
  RUNTIME_ASSERT(args[index]->IsSmi());                              \
  RUNTIME_ASSERT(args.smi_at(index) == kStrictMode ||                \
                 args.smi_at(index) == kNonStrictMode);              \
  StrictModeFlag name =                                              \
      static_cast<StrictModeFlag>(args.smi_at(index));


// Assert that the given argument has a valid value for a LanguageMode
// and store it in a LanguageMode variable with the given name.
#define CONVERT_LANGUAGE_MODE_ARG(name, index)                       \
  ASSERT(args[index]->IsSmi());                                      \
  ASSERT(args.smi_at(index) == CLASSIC_MODE ||                       \
         args.smi_at(index) == STRICT_MODE ||                        \
         args.smi_at(index) == EXTENDED_MODE);                       \
  LanguageMode name =                                                \
      static_cast<LanguageMode>(args.smi_at(index));


MUST_USE_RESULT static MaybeObject* DeepCopyBoilerplate(Isolate* isolate,
                                                   JSObject* boilerplate) {
  StackLimitCheck check(isolate);
  if (check.HasOverflowed()) return isolate->StackOverflow();

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

  // Deep copy local properties.
  if (copy->HasFastProperties()) {
    FixedArray* properties = copy->properties();
    for (int i = 0; i < properties->length(); i++) {
      Object* value = properties->get(i);
      if (value->IsJSObject()) {
        JSObject* js_object = JSObject::cast(value);
        { MaybeObject* maybe_result = DeepCopyBoilerplate(isolate, js_object);
          if (!maybe_result->ToObject(&result)) return maybe_result;
        }
        properties->set(i, result);
      }
    }
    int nof = copy->map()->inobject_properties();
    for (int i = 0; i < nof; i++) {
      Object* value = copy->InObjectPropertyAt(i);
      if (value->IsJSObject()) {
        JSObject* js_object = JSObject::cast(value);
        { MaybeObject* maybe_result = DeepCopyBoilerplate(isolate, js_object);
          if (!maybe_result->ToObject(&result)) return maybe_result;
        }
        copy->InObjectPropertyAtPut(i, result);
      }
    }
  } 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 = DeepCopyBoilerplate(isolate, js_object);
          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_ONLY_ELEMENTS:
    case FAST_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() ||
                 (copy->GetElementsKind() == FAST_ELEMENTS));
          if (value->IsJSObject()) {
            JSObject* js_object = JSObject::cast(value);
            { MaybeObject* maybe_result = DeepCopyBoilerplate(isolate,
                                                              js_object);
              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 = DeepCopyBoilerplate(isolate,
                                                              js_object);
              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:
      // No contained objects, nothing to do.
      break;
  }
  return copy;
}


static Handle<Map> ComputeObjectLiteralMap(
    Handle<Context> context,
    Handle<FixedArray> constant_properties,
    bool* is_result_from_cache) {
  Isolate* isolate = context->GetIsolate();
  int properties_length = constant_properties->length();
  int number_of_properties = properties_length / 2;
  // Check that there are only symbols and array indices among keys.
  int number_of_symbol_keys = 0;
  for (int p = 0; p != properties_length; p += 2) {
    Object* key = constant_properties->get(p);
    uint32_t element_index = 0;
    if (key->IsSymbol()) {
      number_of_symbol_keys++;
    } else if (key->ToArrayIndex(&element_index)) {
      // An index key does not require space in the property backing store.
      number_of_properties--;
    } else {
      // Bail out as a non-symbol non-index key makes caching impossible.
      // ASSERT to make sure that the if condition after the loop is false.
      ASSERT(number_of_symbol_keys != number_of_properties);
      break;
    }
  }
  // If we only have symbols and array indices among keys then we can
  // use the map cache in the global context.
  const int kMaxKeys = 10;
  if ((number_of_symbol_keys == number_of_properties) &&
      (number_of_symbol_keys < kMaxKeys)) {
    // Create the fixed array with the key.
    Handle<FixedArray> keys =
        isolate->factory()->NewFixedArray(number_of_symbol_keys);
    if (number_of_symbol_keys > 0) {
      int index = 0;
      for (int p = 0; p < properties_length; p += 2) {
        Object* key = constant_properties->get(p);
        if (key->IsSymbol()) {
          keys->set(index++, key);
        }
      }
      ASSERT(index == number_of_symbol_keys);
    }
    *is_result_from_cache = true;
    return isolate->factory()->ObjectLiteralMapFromCache(context, keys);
  }
  *is_result_from_cache = false;
  return isolate->factory()->CopyMap(
      Handle<Map>(context->object_function()->initial_map()),
      number_of_properties);
}


static Handle<Object> CreateLiteralBoilerplate(
    Isolate* isolate,
    Handle<FixedArray> literals,
    Handle<FixedArray> constant_properties);


static Handle<Object> CreateObjectLiteralBoilerplate(
    Isolate* isolate,
    Handle<FixedArray> literals,
    Handle<FixedArray> constant_properties,
    bool should_have_fast_elements,
    bool has_function_literal) {
  // Get the global context from the literals array.  This is the
  // context in which the function was created and we use the object
  // function from this context to create the object literal.  We do
  // not use the object function from the current global context
  // because this might be the object function from another context
  // which we should not have access to.
  Handle<Context> context =
      Handle<Context>(JSFunction::GlobalContextFromLiterals(*literals));

  // In case we have function literals, we want the object to be in
  // slow properties mode for now. We don't go in the map cache because
  // maps with constant functions can't be shared if the functions are
  // not the same (which is the common case).
  bool is_result_from_cache = false;
  Handle<Map> map = has_function_literal
      ? Handle<Map>(context->object_function()->initial_map())
      : ComputeObjectLiteralMap(context,
                                constant_properties,
                                &is_result_from_cache);

  Handle<JSObject> boilerplate = isolate->factory()->NewJSObjectFromMap(map);

  // Normalize the elements of the boilerplate to save space if needed.
  if (!should_have_fast_elements) JSObject::NormalizeElements(boilerplate);

  // Add the constant properties to the boilerplate.
  int length = constant_properties->length();
  bool should_transform =
      !is_result_from_cache && boilerplate->HasFastProperties();
  if (should_transform || has_function_literal) {
    // Normalize the properties of object to avoid n^2 behavior
    // when extending the object multiple properties. Indicate the number of
    // properties to be added.
    JSObject::NormalizeProperties(
        boilerplate, KEEP_INOBJECT_PROPERTIES, length / 2);
  }

  for (int index = 0; index < length; index +=2) {
    Handle<Object> key(constant_properties->get(index+0), isolate);
    Handle<Object> value(constant_properties->get(index+1), isolate);
    if (value->IsFixedArray()) {
      // The value contains the constant_properties of a
      // simple object or array literal.
      Handle<FixedArray> array = Handle<FixedArray>::cast(value);
      value = CreateLiteralBoilerplate(isolate, literals, array);
      if (value.is_null()) return value;
    }
    Handle<Object> result;
    uint32_t element_index = 0;
    if (key->IsSymbol()) {
      if (Handle<String>::cast(key)->AsArrayIndex(&element_index)) {
        // Array index as string (uint32).
        result = JSObject::SetOwnElement(
            boilerplate, element_index, value, kNonStrictMode);
      } else {
        Handle<String> name(String::cast(*key));
        ASSERT(!name->AsArrayIndex(&element_index));
        result = JSObject::SetLocalPropertyIgnoreAttributes(
            boilerplate, name, value, NONE);
      }
    } else if (key->ToArrayIndex(&element_index)) {
      // Array index (uint32).
      result = JSObject::SetOwnElement(
          boilerplate, element_index, value, kNonStrictMode);
    } else {
      // Non-uint32 number.
      ASSERT(key->IsNumber());
      double num = key->Number();
      char arr[100];
      Vector<char> buffer(arr, ARRAY_SIZE(arr));
      const char* str = DoubleToCString(num, buffer);
      Handle<String> name =
          isolate->factory()->NewStringFromAscii(CStrVector(str));
      result = JSObject::SetLocalPropertyIgnoreAttributes(
          boilerplate, name, value, NONE);
    }
    // If setting the property on the boilerplate throws an
    // exception, the exception is converted to an empty handle in
    // the handle based operations.  In that case, we need to
    // convert back to an exception.
    if (result.is_null()) return result;
  }

  // Transform to fast properties if necessary. For object literals with
  // containing function literals we defer this operation until after all
  // computed properties have been assigned so that we can generate
  // constant function properties.
  if (should_transform && !has_function_literal) {
    JSObject::TransformToFastProperties(
        boilerplate, boilerplate->map()->unused_property_fields());
  }

  return boilerplate;
}


MaybeObject* TransitionElements(Handle<Object> object,
                                ElementsKind to_kind,
                                Isolate* isolate) {
  HandleScope scope(isolate);
  if (!object->IsJSObject()) return isolate->ThrowIllegalOperation();
  ElementsKind from_kind =
      Handle<JSObject>::cast(object)->map()->elements_kind();
  if (Map::IsValidElementsTransition(from_kind, to_kind)) {
    Handle<Object> result = JSObject::TransitionElementsKind(
        Handle<JSObject>::cast(object), to_kind);
    if (result.is_null()) return isolate->ThrowIllegalOperation();
    return *result;
  }
  return isolate->ThrowIllegalOperation();
}


static const int kSmiOnlyLiteralMinimumLength = 1024;


Handle<Object> Runtime::CreateArrayLiteralBoilerplate(
    Isolate* isolate,
    Handle<FixedArray> literals,
    Handle<FixedArray> elements) {
  // Create the JSArray.
  Handle<JSFunction> constructor(
      JSFunction::GlobalContextFromLiterals(*literals)->array_function());
  Handle<JSArray> object =
      Handle<JSArray>::cast(isolate->factory()->NewJSObject(constructor));

  ElementsKind constant_elements_kind =
      static_cast<ElementsKind>(Smi::cast(elements->get(0))->value());
  Handle<FixedArrayBase> constant_elements_values(
      FixedArrayBase::cast(elements->get(1)));

  Context* global_context = isolate->context()->global_context();
  if (constant_elements_kind == FAST_SMI_ONLY_ELEMENTS) {
    object->set_map(Map::cast(global_context->smi_js_array_map()));
  } else if (constant_elements_kind == FAST_DOUBLE_ELEMENTS) {
    object->set_map(Map::cast(global_context->double_js_array_map()));
  } else {
    object->set_map(Map::cast(global_context->object_js_array_map()));
  }

  Handle<FixedArrayBase> copied_elements_values;
  if (constant_elements_kind == FAST_DOUBLE_ELEMENTS) {
    ASSERT(FLAG_smi_only_arrays);
    copied_elements_values = isolate->factory()->CopyFixedDoubleArray(
        Handle<FixedDoubleArray>::cast(constant_elements_values));
  } else {
    ASSERT(constant_elements_kind == FAST_SMI_ONLY_ELEMENTS ||
           constant_elements_kind == FAST_ELEMENTS);
    const bool is_cow =
        (constant_elements_values->map() ==
         isolate->heap()->fixed_cow_array_map());
    if (is_cow) {
      copied_elements_values = constant_elements_values;
#if DEBUG
      Handle<FixedArray> fixed_array_values =
          Handle<FixedArray>::cast(copied_elements_values);
      for (int i = 0; i < fixed_array_values->length(); i++) {
        ASSERT(!fixed_array_values->get(i)->IsFixedArray());
      }
#endif
    } else {
      Handle<FixedArray> fixed_array_values =
          Handle<FixedArray>::cast(constant_elements_values);
      Handle<FixedArray> fixed_array_values_copy =
          isolate->factory()->CopyFixedArray(fixed_array_values);
      copied_elements_values = fixed_array_values_copy;
      for (int i = 0; i < fixed_array_values->length(); i++) {
        Object* current = fixed_array_values->get(i);
        if (current->IsFixedArray()) {
          // The value contains the constant_properties of a
          // simple object or array literal.
          Handle<FixedArray> fa(FixedArray::cast(fixed_array_values->get(i)));
          Handle<Object> result =
              CreateLiteralBoilerplate(isolate, literals, fa);
          if (result.is_null()) return result;
          fixed_array_values_copy->set(i, *result);
        }
      }
    }
  }
  object->set_elements(*copied_elements_values);
  object->set_length(Smi::FromInt(copied_elements_values->length()));

  //  Ensure that the boilerplate object has FAST_ELEMENTS, unless the flag is
  //  on or the object is larger than the threshold.
  if (!FLAG_smi_only_arrays &&
      constant_elements_values->length() < kSmiOnlyLiteralMinimumLength) {
    if (object->GetElementsKind() != FAST_ELEMENTS) {
      CHECK(!TransitionElements(object, FAST_ELEMENTS, isolate)->IsFailure());
    }
  }

  return object;
}


static Handle<Object> CreateLiteralBoilerplate(
    Isolate* isolate,
    Handle<FixedArray> literals,
    Handle<FixedArray> array) {
  Handle<FixedArray> elements = CompileTimeValue::GetElements(array);
  const bool kHasNoFunctionLiteral = false;
  switch (CompileTimeValue::GetType(array)) {
    case CompileTimeValue::OBJECT_LITERAL_FAST_ELEMENTS:
      return CreateObjectLiteralBoilerplate(isolate,
                                            literals,
                                            elements,
                                            true,
                                            kHasNoFunctionLiteral);
    case CompileTimeValue::OBJECT_LITERAL_SLOW_ELEMENTS:
      return CreateObjectLiteralBoilerplate(isolate,
                                            literals,
                                            elements,
                                            false,
                                            kHasNoFunctionLiteral);
    case CompileTimeValue::ARRAY_LITERAL:
      return Runtime::CreateArrayLiteralBoilerplate(
          isolate, literals, elements);
    default:
      UNREACHABLE();
      return Handle<Object>::null();
  }
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CreateObjectLiteral) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 4);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, literals, 0);
  CONVERT_SMI_ARG_CHECKED(literals_index, 1);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, constant_properties, 2);
  CONVERT_SMI_ARG_CHECKED(flags, 3);
  bool should_have_fast_elements = (flags & ObjectLiteral::kFastElements) != 0;
  bool has_function_literal = (flags & ObjectLiteral::kHasFunction) != 0;

  // Check if boilerplate exists. If not, create it first.
  Handle<Object> boilerplate(literals->get(literals_index), isolate);
  if (*boilerplate == isolate->heap()->undefined_value()) {
    boilerplate = CreateObjectLiteralBoilerplate(isolate,
                                                 literals,
                                                 constant_properties,
                                                 should_have_fast_elements,
                                                 has_function_literal);
    if (boilerplate.is_null()) return Failure::Exception();
    // Update the functions literal and return the boilerplate.
    literals->set(literals_index, *boilerplate);
  }
  return DeepCopyBoilerplate(isolate, JSObject::cast(*boilerplate));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CreateObjectLiteralShallow) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 4);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, literals, 0);
  CONVERT_SMI_ARG_CHECKED(literals_index, 1);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, constant_properties, 2);
  CONVERT_SMI_ARG_CHECKED(flags, 3);
  bool should_have_fast_elements = (flags & ObjectLiteral::kFastElements) != 0;
  bool has_function_literal = (flags & ObjectLiteral::kHasFunction) != 0;

  // Check if boilerplate exists. If not, create it first.
  Handle<Object> boilerplate(literals->get(literals_index), isolate);
  if (*boilerplate == isolate->heap()->undefined_value()) {
    boilerplate = CreateObjectLiteralBoilerplate(isolate,
                                                 literals,
                                                 constant_properties,
                                                 should_have_fast_elements,
                                                 has_function_literal);
    if (boilerplate.is_null()) return Failure::Exception();
    // Update the functions literal and return the boilerplate.
    literals->set(literals_index, *boilerplate);
  }
  return isolate->heap()->CopyJSObject(JSObject::cast(*boilerplate));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CreateArrayLiteral) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 3);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, literals, 0);
  CONVERT_SMI_ARG_CHECKED(literals_index, 1);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, elements, 2);

  // Check if boilerplate exists. If not, create it first.
  Handle<Object> boilerplate(literals->get(literals_index), isolate);
  if (*boilerplate == isolate->heap()->undefined_value()) {
    boilerplate =
        Runtime::CreateArrayLiteralBoilerplate(isolate, literals, elements);
    if (boilerplate.is_null()) return Failure::Exception();
    // Update the functions literal and return the boilerplate.
    literals->set(literals_index, *boilerplate);
  }
  return DeepCopyBoilerplate(isolate, JSObject::cast(*boilerplate));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CreateArrayLiteralShallow) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 3);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, literals, 0);
  CONVERT_SMI_ARG_CHECKED(literals_index, 1);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, elements, 2);

  // Check if boilerplate exists. If not, create it first.
  Handle<Object> boilerplate(literals->get(literals_index), isolate);
  if (*boilerplate == isolate->heap()->undefined_value()) {
    ASSERT(*elements != isolate->heap()->empty_fixed_array());
    boilerplate =
        Runtime::CreateArrayLiteralBoilerplate(isolate, literals, elements);
    if (boilerplate.is_null()) return Failure::Exception();
    // Update the functions literal and return the boilerplate.
    literals->set(literals_index, *boilerplate);
  }
  if (JSObject::cast(*boilerplate)->elements()->map() ==
      isolate->heap()->fixed_cow_array_map()) {
    isolate->counters()->cow_arrays_created_runtime()->Increment();
  }
  return isolate->heap()->CopyJSObject(JSObject::cast(*boilerplate));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CreateJSProxy) {
  ASSERT(args.length() == 2);
  Object* handler = args[0];
  Object* prototype = args[1];
  Object* used_prototype =
      prototype->IsJSReceiver() ? prototype : isolate->heap()->null_value();
  return isolate->heap()->AllocateJSProxy(handler, used_prototype);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CreateJSFunctionProxy) {
  ASSERT(args.length() == 4);
  Object* handler = args[0];
  Object* call_trap = args[1];
  Object* construct_trap = args[2];
  Object* prototype = args[3];
  Object* used_prototype =
      prototype->IsJSReceiver() ? prototype : isolate->heap()->null_value();
  return isolate->heap()->AllocateJSFunctionProxy(
      handler, call_trap, construct_trap, used_prototype);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_IsJSProxy) {
  ASSERT(args.length() == 1);
  Object* obj = args[0];
  return isolate->heap()->ToBoolean(obj->IsJSProxy());
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_IsJSFunctionProxy) {
  ASSERT(args.length() == 1);
  Object* obj = args[0];
  return isolate->heap()->ToBoolean(obj->IsJSFunctionProxy());
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_GetHandler) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSProxy, proxy, 0);
  return proxy->handler();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_GetCallTrap) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSFunctionProxy, proxy, 0);
  return proxy->call_trap();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_GetConstructTrap) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSFunctionProxy, proxy, 0);
  return proxy->construct_trap();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_Fix) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSProxy, proxy, 0);
  proxy->Fix();
  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SetInitialize) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);
  CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
  Handle<ObjectHashSet> table = isolate->factory()->NewObjectHashSet(0);
  holder->set_table(*table);
  return *holder;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SetAdd) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
  Handle<Object> key(args[1]);
  Handle<ObjectHashSet> table(ObjectHashSet::cast(holder->table()));
  table = ObjectHashSetAdd(table, key);
  holder->set_table(*table);
  return isolate->heap()->undefined_symbol();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SetHas) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
  Handle<Object> key(args[1]);
  Handle<ObjectHashSet> table(ObjectHashSet::cast(holder->table()));
  return isolate->heap()->ToBoolean(table->Contains(*key));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SetDelete) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
  Handle<Object> key(args[1]);
  Handle<ObjectHashSet> table(ObjectHashSet::cast(holder->table()));
  table = ObjectHashSetRemove(table, key);
  holder->set_table(*table);
  return isolate->heap()->undefined_symbol();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_MapInitialize) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);
  CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
  Handle<ObjectHashTable> table = isolate->factory()->NewObjectHashTable(0);
  holder->set_table(*table);
  return *holder;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_MapGet) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
  Handle<Object> key(args[1]);
  return ObjectHashTable::cast(holder->table())->Lookup(*key);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_MapSet) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 3);
  CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
  Handle<Object> key(args[1]);
  Handle<Object> value(args[2]);
  Handle<ObjectHashTable> table(ObjectHashTable::cast(holder->table()));
  Handle<ObjectHashTable> new_table = PutIntoObjectHashTable(table, key, value);
  holder->set_table(*new_table);
  return *value;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_WeakMapInitialize) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);
  CONVERT_ARG_HANDLE_CHECKED(JSWeakMap, weakmap, 0);
  ASSERT(weakmap->map()->inobject_properties() == 0);
  Handle<ObjectHashTable> table = isolate->factory()->NewObjectHashTable(0);
  weakmap->set_table(*table);
  weakmap->set_next(Smi::FromInt(0));
  return *weakmap;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_WeakMapGet) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(JSWeakMap, weakmap, 0);
  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, key, 1);
  return ObjectHashTable::cast(weakmap->table())->Lookup(*key);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_WeakMapSet) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 3);
  CONVERT_ARG_HANDLE_CHECKED(JSWeakMap, weakmap, 0);
  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, key, 1);
  Handle<Object> value(args[2]);
  Handle<ObjectHashTable> table(ObjectHashTable::cast(weakmap->table()));
  Handle<ObjectHashTable> new_table = PutIntoObjectHashTable(table, key, value);
  weakmap->set_table(*new_table);
  return *value;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_ClassOf) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);
  Object* obj = args[0];
  if (!obj->IsJSObject()) return isolate->heap()->null_value();
  return JSObject::cast(obj)->class_name();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_GetPrototype) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSReceiver, input_obj, 0);
  Object* obj = input_obj;
  // We don't expect access checks to be needed on JSProxy objects.
  ASSERT(!obj->IsAccessCheckNeeded() || obj->IsJSObject());
  do {
    if (obj->IsAccessCheckNeeded() &&
        !isolate->MayNamedAccess(JSObject::cast(obj),
                                 isolate->heap()->Proto_symbol(),
                                 v8::ACCESS_GET)) {
      isolate->ReportFailedAccessCheck(JSObject::cast(obj), v8::ACCESS_GET);
      return isolate->heap()->undefined_value();
    }
    obj = obj->GetPrototype();
  } while (obj->IsJSObject() &&
           JSObject::cast(obj)->map()->is_hidden_prototype());
  return obj;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_IsInPrototypeChain) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);
  // See ECMA-262, section 15.3.5.3, page 88 (steps 5 - 8).
  Object* O = args[0];
  Object* V = args[1];
  while (true) {
    Object* prototype = V->GetPrototype();
    if (prototype->IsNull()) return isolate->heap()->false_value();
    if (O == prototype) return isolate->heap()->true_value();
    V = prototype;
  }
}


// Recursively traverses hidden prototypes if property is not found
static void GetOwnPropertyImplementation(JSObject* obj,
                                         String* name,
                                         LookupResult* result) {
  obj->LocalLookupRealNamedProperty(name, result);

  if (!result->IsProperty()) {
    Object* proto = obj->GetPrototype();
    if (proto->IsJSObject() &&
      JSObject::cast(proto)->map()->is_hidden_prototype())
      GetOwnPropertyImplementation(JSObject::cast(proto),
                                   name, result);
  }
}


static bool CheckAccessException(LookupResult* result,
                                 v8::AccessType access_type) {
  if (result->type() == CALLBACKS) {
    Object* callback = result->GetCallbackObject();
    if (callback->IsAccessorInfo()) {
      AccessorInfo* info = AccessorInfo::cast(callback);
      bool can_access =
          (access_type == v8::ACCESS_HAS &&
              (info->all_can_read() || info->all_can_write())) ||
          (access_type == v8::ACCESS_GET && info->all_can_read()) ||
          (access_type == v8::ACCESS_SET && info->all_can_write());
      return can_access;
    }
  }

  return false;
}


static bool CheckAccess(JSObject* obj,
                        String* name,
                        LookupResult* result,
                        v8::AccessType access_type) {
  ASSERT(result->IsProperty());

  JSObject* holder = result->holder();
  JSObject* current = obj;
  Isolate* isolate = obj->GetIsolate();
  while (true) {
    if (current->IsAccessCheckNeeded() &&
        !isolate->MayNamedAccess(current, name, access_type)) {
      // Access check callback denied the access, but some properties
      // can have a special permissions which override callbacks descision
      // (currently see v8::AccessControl).
      break;
    }

    if (current == holder) {
      return true;
    }

    current = JSObject::cast(current->GetPrototype());
  }

  // API callbacks can have per callback access exceptions.
  switch (result->type()) {
    case CALLBACKS: {
      if (CheckAccessException(result, access_type)) {
        return true;
      }
      break;
    }
    case INTERCEPTOR: {
      // If the object has an interceptor, try real named properties.
      // Overwrite the result to fetch the correct property later.
      holder->LookupRealNamedProperty(name, result);
      if (result->IsProperty()) {
        if (CheckAccessException(result, access_type)) {
          return true;
        }
      }
      break;
    }
    default:
      break;
  }

  isolate->ReportFailedAccessCheck(current, access_type);
  return false;
}


// TODO(1095): we should traverse hidden prototype hierachy as well.
static bool CheckElementAccess(JSObject* obj,
                               uint32_t index,
                               v8::AccessType access_type) {
  if (obj->IsAccessCheckNeeded() &&
      !obj->GetIsolate()->MayIndexedAccess(obj, index, access_type)) {
    return false;
  }

  return true;
}


// Enumerator used as indices into the array returned from GetOwnProperty
enum PropertyDescriptorIndices {
  IS_ACCESSOR_INDEX,
  VALUE_INDEX,
  GETTER_INDEX,
  SETTER_INDEX,
  WRITABLE_INDEX,
  ENUMERABLE_INDEX,
  CONFIGURABLE_INDEX,
  DESCRIPTOR_SIZE
};


static MaybeObject* GetOwnProperty(Isolate* isolate,
                                   Handle<JSObject> obj,
                                   Handle<String> name) {
  Heap* heap = isolate->heap();
  Handle<FixedArray> elms = isolate->factory()->NewFixedArray(DESCRIPTOR_SIZE);
  Handle<JSArray> desc = isolate->factory()->NewJSArrayWithElements(elms);
  LookupResult result(isolate);
  // This could be an element.
  uint32_t index;
  if (name->AsArrayIndex(&index)) {
    switch (obj->HasLocalElement(index)) {
      case JSObject::UNDEFINED_ELEMENT:
        return heap->undefined_value();

      case JSObject::STRING_CHARACTER_ELEMENT: {
        // Special handling of string objects according to ECMAScript 5
        // 15.5.5.2. Note that this might be a string object with elements
        // other than the actual string value. This is covered by the
        // subsequent cases.
        Handle<JSValue> js_value = Handle<JSValue>::cast(obj);
        Handle<String> str(String::cast(js_value->value()));
        Handle<String> substr = SubString(str, index, index + 1, NOT_TENURED);

        elms->set(IS_ACCESSOR_INDEX, heap->false_value());
        elms->set(VALUE_INDEX, *substr);
        elms->set(WRITABLE_INDEX, heap->false_value());
        elms->set(ENUMERABLE_INDEX,  heap->true_value());
        elms->set(CONFIGURABLE_INDEX, heap->false_value());
        return *desc;
      }

      case JSObject::INTERCEPTED_ELEMENT:
      case JSObject::FAST_ELEMENT: {
        elms->set(IS_ACCESSOR_INDEX, heap->false_value());
        Handle<Object> value = Object::GetElement(obj, index);
        RETURN_IF_EMPTY_HANDLE(isolate, value);
        elms->set(VALUE_INDEX, *value);
        elms->set(WRITABLE_INDEX, heap->true_value());
        elms->set(ENUMERABLE_INDEX,  heap->true_value());
        elms->set(CONFIGURABLE_INDEX, heap->true_value());
        return *desc;
      }

      case JSObject::DICTIONARY_ELEMENT: {
        Handle<JSObject> holder = obj;
        if (obj->IsJSGlobalProxy()) {
          Object* proto = obj->GetPrototype();
          if (proto->IsNull()) return heap->undefined_value();
          ASSERT(proto->IsJSGlobalObject());
          holder = Handle<JSObject>(JSObject::cast(proto));
        }
        FixedArray* elements = FixedArray::cast(holder->elements());
        SeededNumberDictionary* dictionary = NULL;
        if (elements->map() == heap->non_strict_arguments_elements_map()) {
          dictionary = SeededNumberDictionary::cast(elements->get(1));
        } else {
          dictionary = SeededNumberDictionary::cast(elements);
        }
        int entry = dictionary->FindEntry(index);
        ASSERT(entry != SeededNumberDictionary::kNotFound);
        PropertyDetails details = dictionary->DetailsAt(entry);
        switch (details.type()) {
          case CALLBACKS: {
            // This is an accessor property with getter and/or setter.
            AccessorPair* accessors =
                AccessorPair::cast(dictionary->ValueAt(entry));
            elms->set(IS_ACCESSOR_INDEX, heap->true_value());
            if (CheckElementAccess(*obj, index, v8::ACCESS_GET)) {
              elms->set(GETTER_INDEX, accessors->GetComponent(ACCESSOR_GETTER));
            }
            if (CheckElementAccess(*obj, index, v8::ACCESS_SET)) {
              elms->set(SETTER_INDEX, accessors->GetComponent(ACCESSOR_SETTER));
            }
            break;
          }
          case NORMAL: {
            // This is a data property.
            elms->set(IS_ACCESSOR_INDEX, heap->false_value());
            Handle<Object> value = Object::GetElement(obj, index);
            ASSERT(!value.is_null());
            elms->set(VALUE_INDEX, *value);
            elms->set(WRITABLE_INDEX, heap->ToBoolean(!details.IsReadOnly()));
            break;
          }
          default:
            UNREACHABLE();
            break;
        }
        elms->set(ENUMERABLE_INDEX, heap->ToBoolean(!details.IsDontEnum()));
        elms->set(CONFIGURABLE_INDEX, heap->ToBoolean(!details.IsDontDelete()));
        return *desc;
      }
    }
  }

  // Use recursive implementation to also traverse hidden prototypes
  GetOwnPropertyImplementation(*obj, *name, &result);

  if (!result.IsProperty()) {
    return heap->undefined_value();
  }

  if (!CheckAccess(*obj, *name, &result, v8::ACCESS_HAS)) {
    return heap->false_value();
  }

  elms->set(ENUMERABLE_INDEX, heap->ToBoolean(!result.IsDontEnum()));
  elms->set(CONFIGURABLE_INDEX, heap->ToBoolean(!result.IsDontDelete()));

  bool is_js_accessor = (result.type() == CALLBACKS) &&
                        (result.GetCallbackObject()->IsAccessorPair());

  if (is_js_accessor) {
    // __defineGetter__/__defineSetter__ callback.
    elms->set(IS_ACCESSOR_INDEX, heap->true_value());

    AccessorPair* accessors = AccessorPair::cast(result.GetCallbackObject());
    if (CheckAccess(*obj, *name, &result, v8::ACCESS_GET)) {
      elms->set(GETTER_INDEX, accessors->GetComponent(ACCESSOR_GETTER));
    }
    if (CheckAccess(*obj, *name, &result, v8::ACCESS_SET)) {
      elms->set(SETTER_INDEX, accessors->GetComponent(ACCESSOR_SETTER));
    }
  } else {
    elms->set(IS_ACCESSOR_INDEX, heap->false_value());
    elms->set(WRITABLE_INDEX, heap->ToBoolean(!result.IsReadOnly()));

    PropertyAttributes attrs;
    Object* value;
    // GetProperty will check access and report any violations.
    { MaybeObject* maybe_value = obj->GetProperty(*obj, &result, *name, &attrs);
      if (!maybe_value->ToObject(&value)) return maybe_value;
    }
    elms->set(VALUE_INDEX, value);
  }

  return *desc;
}


// Returns an array with the property description:
//  if args[1] is not a property on args[0]
//          returns undefined
//  if args[1] is a data property on args[0]
//         [false, value, Writeable, Enumerable, Configurable]
//  if args[1] is an accessor on args[0]
//         [true, GetFunction, SetFunction, Enumerable, Configurable]
RUNTIME_FUNCTION(MaybeObject*, Runtime_GetOwnProperty) {
  ASSERT(args.length() == 2);
  HandleScope scope(isolate);
  CONVERT_ARG_HANDLE_CHECKED(JSObject, obj, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, name, 1);
  return GetOwnProperty(isolate, obj, name);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_PreventExtensions) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSObject, obj, 0);
  return obj->PreventExtensions();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_IsExtensible) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSObject, obj, 0);
  if (obj->IsJSGlobalProxy()) {
    Object* proto = obj->GetPrototype();
    if (proto->IsNull()) return isolate->heap()->false_value();
    ASSERT(proto->IsJSGlobalObject());
    obj = JSObject::cast(proto);
  }
  return isolate->heap()->ToBoolean(obj->map()->is_extensible());
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpCompile) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 3);
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, re, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, pattern, 1);
  CONVERT_ARG_HANDLE_CHECKED(String, flags, 2);
  Handle<Object> result = RegExpImpl::Compile(re, pattern, flags);
  if (result.is_null()) return Failure::Exception();
  return *result;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CreateApiFunction) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);
  CONVERT_ARG_HANDLE_CHECKED(FunctionTemplateInfo, data, 0);
  return *isolate->factory()->CreateApiFunction(data);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_IsTemplate) {
  ASSERT(args.length() == 1);
  Object* arg = args[0];
  bool result = arg->IsObjectTemplateInfo() || arg->IsFunctionTemplateInfo();
  return isolate->heap()->ToBoolean(result);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_GetTemplateField) {
  ASSERT(args.length() == 2);
  CONVERT_ARG_CHECKED(HeapObject, templ, 0);
  CONVERT_SMI_ARG_CHECKED(index, 1)
  int offset = index * kPointerSize + HeapObject::kHeaderSize;
  InstanceType type = templ->map()->instance_type();
  RUNTIME_ASSERT(type ==  FUNCTION_TEMPLATE_INFO_TYPE ||
                 type ==  OBJECT_TEMPLATE_INFO_TYPE);
  RUNTIME_ASSERT(offset > 0);
  if (type == FUNCTION_TEMPLATE_INFO_TYPE) {
    RUNTIME_ASSERT(offset < FunctionTemplateInfo::kSize);
  } else {
    RUNTIME_ASSERT(offset < ObjectTemplateInfo::kSize);
  }
  return *HeapObject::RawField(templ, offset);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_DisableAccessChecks) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(HeapObject, object, 0);
  Map* old_map = object->map();
  bool needs_access_checks = old_map->is_access_check_needed();
  if (needs_access_checks) {
    // Copy map so it won't interfere constructor's initial map.
    Object* new_map;
    { MaybeObject* maybe_new_map = old_map->CopyDropTransitions();
      if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
    }

    Map::cast(new_map)->set_is_access_check_needed(false);
    object->set_map(Map::cast(new_map));
  }
  return isolate->heap()->ToBoolean(needs_access_checks);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_EnableAccessChecks) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(HeapObject, object, 0);
  Map* old_map = object->map();
  if (!old_map->is_access_check_needed()) {
    // Copy map so it won't interfere constructor's initial map.
    Object* new_map;
    { MaybeObject* maybe_new_map = old_map->CopyDropTransitions();
      if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
    }

    Map::cast(new_map)->set_is_access_check_needed(true);
    object->set_map(Map::cast(new_map));
  }
  return isolate->heap()->undefined_value();
}


static Failure* ThrowRedeclarationError(Isolate* isolate,
                                        const char* type,
                                        Handle<String> name) {
  HandleScope scope(isolate);
  Handle<Object> type_handle =
      isolate->factory()->NewStringFromAscii(CStrVector(type));
  Handle<Object> args[2] = { type_handle, name };
  Handle<Object> error =
      isolate->factory()->NewTypeError("redeclaration", HandleVector(args, 2));
  return isolate->Throw(*error);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_DeclareGlobals) {
  ASSERT(args.length() == 3);
  HandleScope scope(isolate);
  Handle<GlobalObject> global = Handle<GlobalObject>(
      isolate->context()->global());

  Handle<Context> context = args.at<Context>(0);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, pairs, 1);
  CONVERT_SMI_ARG_CHECKED(flags, 2);

  // Traverse the name/value pairs and set the properties.
  int length = pairs->length();
  for (int i = 0; i < length; i += 2) {
    HandleScope scope(isolate);
    Handle<String> name(String::cast(pairs->get(i)));
    Handle<Object> value(pairs->get(i + 1), isolate);

    // We have to declare a global const property. To capture we only
    // assign to it when evaluating the assignment for "const x =
    // <expr>" the initial value is the hole.
    bool is_const_property = value->IsTheHole();
    bool is_function_declaration = false;
    if (value->IsUndefined() || is_const_property) {
      // Lookup the property in the global object, and don't set the
      // value of the variable if the property is already there.
      LookupResult lookup(isolate);
      global->Lookup(*name, &lookup);
      if (lookup.IsProperty()) {
        // We found an existing property. Unless it was an interceptor
        // that claims the property is absent, skip this declaration.
        if (lookup.type() != INTERCEPTOR) {
          continue;
        }
        PropertyAttributes attributes = global->GetPropertyAttribute(*name);
        if (attributes != ABSENT) {
          continue;
        }
        // Fall-through and introduce the absent property by using
        // SetProperty.
      }
    } else {
      is_function_declaration = true;
      // Copy the function and update its context. Use it as value.
      Handle<SharedFunctionInfo> shared =
          Handle<SharedFunctionInfo>::cast(value);
      Handle<JSFunction> function =
          isolate->factory()->NewFunctionFromSharedFunctionInfo(shared,
                                                                context,
                                                                TENURED);
      value = function;
    }

    LookupResult lookup(isolate);
    global->LocalLookup(*name, &lookup);

    // Compute the property attributes. According to ECMA-262, section
    // 13, page 71, the property must be read-only and
    // non-deletable. However, neither SpiderMonkey nor KJS creates the
    // property as read-only, so we don't either.
    int attr = NONE;
    if (!DeclareGlobalsEvalFlag::decode(flags)) {
      attr |= DONT_DELETE;
    }
    bool is_native = DeclareGlobalsNativeFlag::decode(flags);
    if (is_const_property || (is_native && is_function_declaration)) {
      attr |= READ_ONLY;
    }

    LanguageMode language_mode = DeclareGlobalsLanguageMode::decode(flags);

    // Safari does not allow the invocation of callback setters for
    // function declarations. To mimic this behavior, we do not allow
    // the invocation of setters for function values. This makes a
    // difference for global functions with the same names as event
    // handlers such as "function onload() {}". Firefox does call the
    // onload setter in those case and Safari does not. We follow
    // Safari for compatibility.
    if (is_function_declaration) {
      if (lookup.IsProperty() && (lookup.type() != INTERCEPTOR)) {
        // Do not overwrite READ_ONLY properties.
        if (lookup.GetAttributes() & READ_ONLY) {
          if (language_mode != CLASSIC_MODE) {
            Handle<Object> args[] = { name };
            return isolate->Throw(*isolate->factory()->NewTypeError(
                "strict_cannot_assign", HandleVector(args, ARRAY_SIZE(args))));
          }
          continue;
        }
        // Do not change DONT_DELETE to false from true.
        attr |= lookup.GetAttributes() & DONT_DELETE;
      }
      PropertyAttributes attributes = static_cast<PropertyAttributes>(attr);

      RETURN_IF_EMPTY_HANDLE(
          isolate,
          JSObject::SetLocalPropertyIgnoreAttributes(global, name, value,
                                                     attributes));
    } else {
      RETURN_IF_EMPTY_HANDLE(
          isolate,
          JSReceiver::SetProperty(global, name, value,
                                  static_cast<PropertyAttributes>(attr),
                                  language_mode == CLASSIC_MODE
                                      ? kNonStrictMode : kStrictMode));
    }
  }

  ASSERT(!isolate->has_pending_exception());
  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_DeclareContextSlot) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 4);

  // Declarations are always made in a function or global context.  In the
  // case of eval code, the context passed is the context of the caller,
  // which may be some nested context and not the declaration context.
  RUNTIME_ASSERT(args[0]->IsContext());
  Handle<Context> context(Context::cast(args[0])->declaration_context());

  Handle<String> name(String::cast(args[1]));
  PropertyAttributes mode = static_cast<PropertyAttributes>(args.smi_at(2));
  RUNTIME_ASSERT(mode == READ_ONLY || mode == NONE);
  Handle<Object> initial_value(args[3], isolate);

  int index;
  PropertyAttributes attributes;
  ContextLookupFlags flags = DONT_FOLLOW_CHAINS;
  BindingFlags binding_flags;
  Handle<Object> holder =
      context->Lookup(name, flags, &index, &attributes, &binding_flags);

  if (attributes != ABSENT) {
    // The name was declared before; check for conflicting re-declarations.
    if (((attributes & READ_ONLY) != 0) || (mode == READ_ONLY)) {
      // Functions are not read-only.
      ASSERT(mode != READ_ONLY || initial_value->IsTheHole());
      const char* type = ((attributes & READ_ONLY) != 0) ? "const" : "var";
      return ThrowRedeclarationError(isolate, type, name);
    }

    // Initialize it if necessary.
    if (*initial_value != NULL) {
      if (index >= 0) {
        ASSERT(holder.is_identical_to(context));
        if (((attributes & READ_ONLY) == 0) ||
            context->get(index)->IsTheHole()) {
          context->set(index, *initial_value);
        }
      } else {
        // Slow case: The property is in the context extension object of a
        // function context or the global object of a global context.
        Handle<JSObject> object = Handle<JSObject>::cast(holder);
        RETURN_IF_EMPTY_HANDLE(
            isolate,
            JSReceiver::SetProperty(object, name, initial_value, mode,
                                    kNonStrictMode));
      }
    }

  } else {
    // The property is not in the function context. It needs to be
    // "declared" in the function context's extension context or as a
    // property of the the global object.
    Handle<JSObject> object;
    if (context->has_extension()) {
      object = Handle<JSObject>(JSObject::cast(context->extension()));
    } else {
      // Context extension objects are allocated lazily.
      ASSERT(context->IsFunctionContext());
      object = isolate->factory()->NewJSObject(
          isolate->context_extension_function());
      context->set_extension(*object);
    }
    ASSERT(*object != NULL);

    // Declare the property by setting it to the initial value if provided,
    // or undefined, and use the correct mode (e.g. READ_ONLY attribute for
    // constant declarations).
    ASSERT(!object->HasLocalProperty(*name));
    Handle<Object> value(isolate->heap()->undefined_value(), isolate);
    if (*initial_value != NULL) value = initial_value;
    // Declaring a const context slot is a conflicting declaration if
    // there is a callback with that name in a prototype. It is
    // allowed to introduce const variables in
    // JSContextExtensionObjects. They are treated specially in
    // SetProperty and no setters are invoked for those since they are
    // not real JSObjects.
    if (initial_value->IsTheHole() &&
        !object->IsJSContextExtensionObject()) {
      LookupResult lookup(isolate);
      object->Lookup(*name, &lookup);
      if (lookup.IsFound() && (lookup.type() == CALLBACKS)) {
        return ThrowRedeclarationError(isolate, "const", name);
      }
    }
    RETURN_IF_EMPTY_HANDLE(
        isolate,
        JSReceiver::SetProperty(object, name, value, mode, kNonStrictMode));
  }

  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_InitializeVarGlobal) {
  NoHandleAllocation nha;
  // args[0] == name
  // args[1] == language_mode
  // args[2] == value (optional)

  // Determine if we need to assign to the variable if it already
  // exists (based on the number of arguments).
  RUNTIME_ASSERT(args.length() == 2 || args.length() == 3);
  bool assign = args.length() == 3;

  CONVERT_ARG_HANDLE_CHECKED(String, name, 0);
  GlobalObject* global = isolate->context()->global();
  RUNTIME_ASSERT(args[1]->IsSmi());
  CONVERT_LANGUAGE_MODE_ARG(language_mode, 1);
  StrictModeFlag strict_mode_flag = (language_mode == CLASSIC_MODE)
      ? kNonStrictMode : kStrictMode;

  // According to ECMA-262, section 12.2, page 62, the property must
  // not be deletable.
  PropertyAttributes attributes = DONT_DELETE;

  // Lookup the property locally in the global object. If it isn't
  // there, there is a property with this name in the prototype chain.
  // We follow Safari and Firefox behavior and only set the property
  // locally if there is an explicit initialization value that we have
  // to assign to the property.
  // Note that objects can have hidden prototypes, so we need to traverse
  // the whole chain of hidden prototypes to do a 'local' lookup.
  Object* object = global;
  LookupResult lookup(isolate);
  while (object->IsJSObject() &&
         JSObject::cast(object)->map()->is_hidden_prototype()) {
    JSObject* raw_holder = JSObject::cast(object);
    raw_holder->LocalLookup(*name, &lookup);
    if (lookup.IsFound() && lookup.type() == INTERCEPTOR) {
      HandleScope handle_scope(isolate);
      Handle<JSObject> holder(raw_holder);
      PropertyAttributes intercepted = holder->GetPropertyAttribute(*name);
      // Update the raw pointer in case it's changed due to GC.
      raw_holder = *holder;
      if (intercepted != ABSENT && (intercepted & READ_ONLY) == 0) {
        // Found an interceptor that's not read only.
        if (assign) {
          return raw_holder->SetProperty(
              &lookup, *name, args[2], attributes, strict_mode_flag);
        } else {
          return isolate->heap()->undefined_value();
        }
      }
    }
    object = raw_holder->GetPrototype();
  }

  // Reload global in case the loop above performed a GC.
  global = isolate->context()->global();
  if (assign) {
    return global->SetProperty(*name, args[2], attributes, strict_mode_flag);
  }
  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_InitializeConstGlobal) {
  // All constants are declared with an initial value. The name
  // of the constant is the first argument and the initial value
  // is the second.
  RUNTIME_ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(String, name, 0);
  Handle<Object> value = args.at<Object>(1);

  // Get the current global object from top.
  GlobalObject* global = isolate->context()->global();

  // According to ECMA-262, section 12.2, page 62, the property must
  // not be deletable. Since it's a const, it must be READ_ONLY too.
  PropertyAttributes attributes =
      static_cast<PropertyAttributes>(DONT_DELETE | READ_ONLY);

  // Lookup the property locally in the global object. If it isn't
  // there, we add the property and take special precautions to always
  // add it as a local property even in case of callbacks in the
  // prototype chain (this rules out using SetProperty).
  // We use SetLocalPropertyIgnoreAttributes instead
  LookupResult lookup(isolate);
  global->LocalLookup(*name, &lookup);
  if (!lookup.IsProperty()) {
    return global->SetLocalPropertyIgnoreAttributes(*name,
                                                    *value,
                                                    attributes);
  }

  if (!lookup.IsReadOnly()) {
    // Restore global object from context (in case of GC) and continue
    // with setting the value.
    HandleScope handle_scope(isolate);
    Handle<GlobalObject> global(isolate->context()->global());

    // BUG 1213575: Handle the case where we have to set a read-only
    // property through an interceptor and only do it if it's
    // uninitialized, e.g. the hole. Nirk...
    // Passing non-strict mode because the property is writable.
    RETURN_IF_EMPTY_HANDLE(
        isolate,
        JSReceiver::SetProperty(global, name, value, attributes,
                                kNonStrictMode));
    return *value;
  }

  // Set the value, but only if we're assigning the initial value to a
  // constant. For now, we determine this by checking if the
  // current value is the hole.
  // Strict mode handling not needed (const is disallowed in strict mode).
  PropertyType type = lookup.type();
  if (type == FIELD) {
    FixedArray* properties = global->properties();
    int index = lookup.GetFieldIndex();
    if (properties->get(index)->IsTheHole() || !lookup.IsReadOnly()) {
      properties->set(index, *value);
    }
  } else if (type == NORMAL) {
    if (global->GetNormalizedProperty(&lookup)->IsTheHole() ||
        !lookup.IsReadOnly()) {
      global->SetNormalizedProperty(&lookup, *value);
    }
  } else {
    // Ignore re-initialization of constants that have already been
    // assigned a function value.
    ASSERT(lookup.IsReadOnly() && type == CONSTANT_FUNCTION);
  }

  // Use the set value as the result of the operation.
  return *value;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_InitializeConstContextSlot) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 3);

  Handle<Object> value(args[0], isolate);
  ASSERT(!value->IsTheHole());

  // Initializations are always done in a function or global context.
  RUNTIME_ASSERT(args[1]->IsContext());
  Handle<Context> context(Context::cast(args[1])->declaration_context());

  Handle<String> name(String::cast(args[2]));

  int index;
  PropertyAttributes attributes;
  ContextLookupFlags flags = FOLLOW_CHAINS;
  BindingFlags binding_flags;
  Handle<Object> holder =
      context->Lookup(name, flags, &index, &attributes, &binding_flags);

  if (index >= 0) {
    ASSERT(holder->IsContext());
    // Property was found in a context.  Perform the assignment if we
    // found some non-constant or an uninitialized constant.
    Handle<Context> context = Handle<Context>::cast(holder);
    if ((attributes & READ_ONLY) == 0 || context->get(index)->IsTheHole()) {
      context->set(index, *value);
    }
    return *value;
  }

  // The property could not be found, we introduce it as a property of the
  // global object.
  if (attributes == ABSENT) {
    Handle<JSObject> global = Handle<JSObject>(
        isolate->context()->global());
    // Strict mode not needed (const disallowed in strict mode).
    RETURN_IF_EMPTY_HANDLE(
        isolate,
        JSReceiver::SetProperty(global, name, value, NONE, kNonStrictMode));
    return *value;
  }

  // The property was present in some function's context extension object,
  // as a property on the subject of a with, or as a property of the global
  // object.
  //
  // In most situations, eval-introduced consts should still be present in
  // the context extension object.  However, because declaration and
  // initialization are separate, the property might have been deleted
  // before we reach the initialization point.
  //
  // Example:
  //
  //    function f() { eval("delete x; const x;"); }
  //
  // In that case, the initialization behaves like a normal assignment.
  Handle<JSObject> object = Handle<JSObject>::cast(holder);

  if (*object == context->extension()) {
    // This is the property that was introduced by the const declaration.
    // Set it if it hasn't been set before.  NOTE: We cannot use
    // GetProperty() to get the current value as it 'unholes' the value.
    LookupResult lookup(isolate);
    object->LocalLookupRealNamedProperty(*name, &lookup);
    ASSERT(lookup.IsFound());  // the property was declared
    ASSERT(lookup.IsReadOnly());  // and it was declared as read-only

    PropertyType type = lookup.type();
    if (type == FIELD) {
      FixedArray* properties = object->properties();
      int index = lookup.GetFieldIndex();
      if (properties->get(index)->IsTheHole()) {
        properties->set(index, *value);
      }
    } else if (type == NORMAL) {
      if (object->GetNormalizedProperty(&lookup)->IsTheHole()) {
        object->SetNormalizedProperty(&lookup, *value);
      }
    } else {
      // We should not reach here. Any real, named property should be
      // either a field or a dictionary slot.
      UNREACHABLE();
    }
  } else {
    // The property was found on some other object.  Set it if it is not a
    // read-only property.
    if ((attributes & READ_ONLY) == 0) {
      // Strict mode not needed (const disallowed in strict mode).
      RETURN_IF_EMPTY_HANDLE(
          isolate,
          JSReceiver::SetProperty(object, name, value, attributes,
                                  kNonStrictMode));
    }
  }

  return *value;
}


RUNTIME_FUNCTION(MaybeObject*,
                 Runtime_OptimizeObjectForAddingMultipleProperties) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
  CONVERT_SMI_ARG_CHECKED(properties, 1);
  if (object->HasFastProperties()) {
    JSObject::NormalizeProperties(object, KEEP_INOBJECT_PROPERTIES, properties);
  }
  return *object;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExec) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 4);
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
  // Due to the way the JS calls are constructed this must be less than the
  // length of a string, i.e. it is always a Smi.  We check anyway for security.
  CONVERT_SMI_ARG_CHECKED(index, 2);
  CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 3);
  RUNTIME_ASSERT(last_match_info->HasFastElements());
  RUNTIME_ASSERT(index >= 0);
  RUNTIME_ASSERT(index <= subject->length());
  isolate->counters()->regexp_entry_runtime()->Increment();
  Handle<Object> result = RegExpImpl::Exec(regexp,
                                           subject,
                                           index,
                                           last_match_info);
  if (result.is_null()) return Failure::Exception();
  return *result;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpConstructResult) {
  ASSERT(args.length() == 3);
  CONVERT_SMI_ARG_CHECKED(elements_count, 0);
  if (elements_count < 0 ||
      elements_count > FixedArray::kMaxLength ||
      !Smi::IsValid(elements_count)) {
    return isolate->ThrowIllegalOperation();
  }
  Object* new_object;
  { MaybeObject* maybe_new_object =
        isolate->heap()->AllocateFixedArrayWithHoles(elements_count);
    if (!maybe_new_object->ToObject(&new_object)) return maybe_new_object;
  }
  FixedArray* elements = FixedArray::cast(new_object);
  { MaybeObject* maybe_new_object = isolate->heap()->AllocateRaw(
      JSRegExpResult::kSize, NEW_SPACE, OLD_POINTER_SPACE);
    if (!maybe_new_object->ToObject(&new_object)) return maybe_new_object;
  }
  {
    AssertNoAllocation no_gc;
    HandleScope scope(isolate);
    reinterpret_cast<HeapObject*>(new_object)->
        set_map(isolate->global_context()->regexp_result_map());
  }
  JSArray* array = JSArray::cast(new_object);
  array->set_properties(isolate->heap()->empty_fixed_array());
  array->set_elements(elements);
  array->set_length(Smi::FromInt(elements_count));
  // Write in-object properties after the length of the array.
  array->InObjectPropertyAtPut(JSRegExpResult::kIndexIndex, args[1]);
  array->InObjectPropertyAtPut(JSRegExpResult::kInputIndex, args[2]);
  return array;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpInitializeObject) {
  AssertNoAllocation no_alloc;
  ASSERT(args.length() == 5);
  CONVERT_ARG_CHECKED(JSRegExp, regexp, 0);
  CONVERT_ARG_CHECKED(String, source, 1);

  Object* global = args[2];
  if (!global->IsTrue()) global = isolate->heap()->false_value();

  Object* ignoreCase = args[3];
  if (!ignoreCase->IsTrue()) ignoreCase = isolate->heap()->false_value();

  Object* multiline = args[4];
  if (!multiline->IsTrue()) multiline = isolate->heap()->false_value();

  Map* map = regexp->map();
  Object* constructor = map->constructor();
  if (constructor->IsJSFunction() &&
      JSFunction::cast(constructor)->initial_map() == map) {
    // If we still have the original map, set in-object properties directly.
    regexp->InObjectPropertyAtPut(JSRegExp::kSourceFieldIndex, source);
    // Both true and false are immovable immortal objects so no need for write
    // barrier.
    regexp->InObjectPropertyAtPut(
        JSRegExp::kGlobalFieldIndex, global, SKIP_WRITE_BARRIER);
    regexp->InObjectPropertyAtPut(
        JSRegExp::kIgnoreCaseFieldIndex, ignoreCase, SKIP_WRITE_BARRIER);
    regexp->InObjectPropertyAtPut(
        JSRegExp::kMultilineFieldIndex, multiline, SKIP_WRITE_BARRIER);
    regexp->InObjectPropertyAtPut(JSRegExp::kLastIndexFieldIndex,
                                  Smi::FromInt(0),
                                  SKIP_WRITE_BARRIER);  // It's a Smi.
    return regexp;
  }

  // Map has changed, so use generic, but slower, method.
  PropertyAttributes final =
      static_cast<PropertyAttributes>(READ_ONLY | DONT_ENUM | DONT_DELETE);
  PropertyAttributes writable =
      static_cast<PropertyAttributes>(DONT_ENUM | DONT_DELETE);
  Heap* heap = isolate->heap();
  MaybeObject* result;
  result = regexp->SetLocalPropertyIgnoreAttributes(heap->source_symbol(),
                                                    source,
                                                    final);
  ASSERT(!result->IsFailure());
  result = regexp->SetLocalPropertyIgnoreAttributes(heap->global_symbol(),
                                                    global,
                                                    final);
  ASSERT(!result->IsFailure());
  result =
      regexp->SetLocalPropertyIgnoreAttributes(heap->ignore_case_symbol(),
                                               ignoreCase,
                                               final);
  ASSERT(!result->IsFailure());
  result = regexp->SetLocalPropertyIgnoreAttributes(heap->multiline_symbol(),
                                                    multiline,
                                                    final);
  ASSERT(!result->IsFailure());
  result =
      regexp->SetLocalPropertyIgnoreAttributes(heap->last_index_symbol(),
                                               Smi::FromInt(0),
                                               writable);
  ASSERT(!result->IsFailure());
  USE(result);
  return regexp;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FinishArrayPrototypeSetup) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);
  CONVERT_ARG_HANDLE_CHECKED(JSArray, prototype, 0);
  // This is necessary to enable fast checks for absence of elements
  // on Array.prototype and below.
  prototype->set_elements(isolate->heap()->empty_fixed_array());
  return Smi::FromInt(0);
}


static Handle<JSFunction> InstallBuiltin(Isolate* isolate,
                                         Handle<JSObject> holder,
                                         const char* name,
                                         Builtins::Name builtin_name) {
  Handle<String> key = isolate->factory()->LookupAsciiSymbol(name);
  Handle<Code> code(isolate->builtins()->builtin(builtin_name));
  Handle<JSFunction> optimized =
      isolate->factory()->NewFunction(key,
                                      JS_OBJECT_TYPE,
                                      JSObject::kHeaderSize,
                                      code,
                                      false);
  optimized->shared()->DontAdaptArguments();
  JSReceiver::SetProperty(holder, key, optimized, NONE, kStrictMode);
  return optimized;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SpecialArrayFunctions) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);
  CONVERT_ARG_HANDLE_CHECKED(JSObject, holder, 0);

  InstallBuiltin(isolate, holder, "pop", Builtins::kArrayPop);
  InstallBuiltin(isolate, holder, "push", Builtins::kArrayPush);
  InstallBuiltin(isolate, holder, "shift", Builtins::kArrayShift);
  InstallBuiltin(isolate, holder, "unshift", Builtins::kArrayUnshift);
  InstallBuiltin(isolate, holder, "slice", Builtins::kArraySlice);
  InstallBuiltin(isolate, holder, "splice", Builtins::kArraySplice);
  InstallBuiltin(isolate, holder, "concat", Builtins::kArrayConcat);

  return *holder;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_GetDefaultReceiver) {
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSReceiver, callable, 0);

  if (!callable->IsJSFunction()) {
    HandleScope scope(isolate);
    bool threw = false;
    Handle<Object> delegate =
        Execution::TryGetFunctionDelegate(Handle<JSReceiver>(callable), &threw);
    if (threw) return Failure::Exception();
    callable = JSFunction::cast(*delegate);
  }
  JSFunction* function = JSFunction::cast(callable);

  SharedFunctionInfo* shared = function->shared();
  if (shared->native() || !shared->is_classic_mode()) {
    return isolate->heap()->undefined_value();
  }
  // Returns undefined for strict or native functions, or
  // the associated global receiver for "normal" functions.

  Context* global_context =
      function->context()->global()->global_context();
  return global_context->global()->global_receiver();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_MaterializeRegExpLiteral) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 4);
  CONVERT_ARG_HANDLE_CHECKED(FixedArray, literals, 0);
  int index = args.smi_at(1);
  Handle<String> pattern = args.at<String>(2);
  Handle<String> flags = args.at<String>(3);

  // Get the RegExp function from the context in the literals array.
  // This is the RegExp function from the context in which the
  // function was created.  We do not use the RegExp function from the
  // current global context because this might be the RegExp function
  // from another context which we should not have access to.
  Handle<JSFunction> constructor =
      Handle<JSFunction>(
          JSFunction::GlobalContextFromLiterals(*literals)->regexp_function());
  // Compute the regular expression literal.
  bool has_pending_exception;
  Handle<Object> regexp =
      RegExpImpl::CreateRegExpLiteral(constructor, pattern, flags,
                                      &has_pending_exception);
  if (has_pending_exception) {
    ASSERT(isolate->has_pending_exception());
    return Failure::Exception();
  }
  literals->set(index, *regexp);
  return *regexp;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionGetName) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);

  CONVERT_ARG_CHECKED(JSFunction, f, 0);
  return f->shared()->name();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionSetName) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);

  CONVERT_ARG_CHECKED(JSFunction, f, 0);
  CONVERT_ARG_CHECKED(String, name, 1);
  f->shared()->set_name(name);
  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionNameShouldPrintAsAnonymous) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSFunction, f, 0);
  return isolate->heap()->ToBoolean(
      f->shared()->name_should_print_as_anonymous());
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionMarkNameShouldPrintAsAnonymous) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSFunction, f, 0);
  f->shared()->set_name_should_print_as_anonymous(true);
  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionRemovePrototype) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);

  CONVERT_ARG_CHECKED(JSFunction, f, 0);
  Object* obj = f->RemovePrototype();
  if (obj->IsFailure()) return obj;

  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionGetScript) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);

  CONVERT_ARG_CHECKED(JSFunction, fun, 0);
  Handle<Object> script = Handle<Object>(fun->shared()->script(), isolate);
  if (!script->IsScript()) return isolate->heap()->undefined_value();

  return *GetScriptWrapper(Handle<Script>::cast(script));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionGetSourceCode) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 1);

  CONVERT_ARG_HANDLE_CHECKED(JSFunction, f, 0);
  Handle<SharedFunctionInfo> shared(f->shared());
  return *shared->GetSourceCode();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionGetScriptSourcePosition) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);

  CONVERT_ARG_CHECKED(JSFunction, fun, 0);
  int pos = fun->shared()->start_position();
  return Smi::FromInt(pos);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionGetPositionForOffset) {
  ASSERT(args.length() == 2);

  CONVERT_ARG_CHECKED(Code, code, 0);
  CONVERT_NUMBER_CHECKED(int, offset, Int32, args[1]);

  RUNTIME_ASSERT(0 <= offset && offset < code->Size());

  Address pc = code->address() + offset;
  return Smi::FromInt(code->SourcePosition(pc));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionSetInstanceClassName) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);

  CONVERT_ARG_CHECKED(JSFunction, fun, 0);
  CONVERT_ARG_CHECKED(String, name, 1);
  fun->SetInstanceClassName(name);
  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionSetLength) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);

  CONVERT_ARG_CHECKED(JSFunction, fun, 0);
  CONVERT_SMI_ARG_CHECKED(length, 1);
  fun->shared()->set_length(length);
  return isolate->heap()->undefined_value();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionSetPrototype) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);

  CONVERT_ARG_CHECKED(JSFunction, fun, 0);
  ASSERT(fun->should_have_prototype());
  Object* obj;
  { MaybeObject* maybe_obj =
        Accessors::FunctionSetPrototype(fun, args[1], NULL);
    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
  }
  return args[0];  // return TOS
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionSetReadOnlyPrototype) {
  NoHandleAllocation ha;
  RUNTIME_ASSERT(args.length() == 1);
  CONVERT_ARG_CHECKED(JSFunction, function, 0);

  MaybeObject* maybe_name =
      isolate->heap()->AllocateStringFromAscii(CStrVector("prototype"));
  String* name;
  if (!maybe_name->To(&name)) return maybe_name;

  if (function->HasFastProperties()) {
    // Construct a new field descriptor with updated attributes.
    DescriptorArray* instance_desc = function->map()->instance_descriptors();
    int index = instance_desc->Search(name);
    ASSERT(index != DescriptorArray::kNotFound);
    PropertyDetails details(instance_desc->GetDetails(index));
    CallbacksDescriptor new_desc(name,
        instance_desc->GetValue(index),
        static_cast<PropertyAttributes>(details.attributes() | READ_ONLY),
        details.index());
    // Construct a new field descriptors array containing the new descriptor.
    Object* descriptors_unchecked;
    { MaybeObject* maybe_descriptors_unchecked =
        instance_desc->CopyInsert(&new_desc, REMOVE_TRANSITIONS);
      if (!maybe_descriptors_unchecked->ToObject(&descriptors_unchecked)) {
        return maybe_descriptors_unchecked;
      }
    }
    DescriptorArray* new_descriptors =
        DescriptorArray::cast(descriptors_unchecked);
    // Create a new map featuring the new field descriptors array.
    Object* map_unchecked;
    { MaybeObject* maybe_map_unchecked = function->map()->CopyDropDescriptors();
      if (!maybe_map_unchecked->ToObject(&map_unchecked)) {
        return maybe_map_unchecked;
      }
    }
    Map* new_map = Map::cast(map_unchecked);
    new_map->set_instance_descriptors(new_descriptors);
    function->set_map(new_map);
  } else {  // Dictionary properties.
    // Directly manipulate the property details.
    int entry = function->property_dictionary()->FindEntry(name);
    ASSERT(entry != StringDictionary::kNotFound);
    PropertyDetails details = function->property_dictionary()->DetailsAt(entry);
    PropertyDetails new_details(
        static_cast<PropertyAttributes>(details.attributes() | READ_ONLY),
        details.type(),
        details.index());
    function->property_dictionary()->DetailsAtPut(entry, new_details);
  }
  return function;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionIsAPIFunction) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);

  CONVERT_ARG_CHECKED(JSFunction, f, 0);
  return isolate->heap()->ToBoolean(f->shared()->IsApiFunction());
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionIsBuiltin) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);

  CONVERT_ARG_CHECKED(JSFunction, f, 0);
  return isolate->heap()->ToBoolean(f->IsBuiltin());
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SetCode) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 2);

  CONVERT_ARG_HANDLE_CHECKED(JSFunction, target, 0);
  Handle<Object> code = args.at<Object>(1);

  Handle<Context> context(target->context());

  if (!code->IsNull()) {
    RUNTIME_ASSERT(code->IsJSFunction());
    Handle<JSFunction> fun = Handle<JSFunction>::cast(code);
    Handle<SharedFunctionInfo> shared(fun->shared());

    if (!SharedFunctionInfo::EnsureCompiled(shared, KEEP_EXCEPTION)) {
      return Failure::Exception();
    }
    // Since we don't store the source for this we should never
    // optimize this.
    shared->code()->set_optimizable(false);
    // Set the code, scope info, formal parameter count,
    // and the length of the target function.
    target->shared()->set_code(shared->code());
    target->ReplaceCode(shared->code());
    target->shared()->set_scope_info(shared->scope_info());
    target->shared()->set_length(shared->length());
    target->shared()->set_formal_parameter_count(
        shared->formal_parameter_count());
    // Set the source code of the target function to undefined.
    // SetCode is only used for built-in constructors like String,
    // Array, and Object, and some web code
    // doesn't like seeing source code for constructors.
    target->shared()->set_script(isolate->heap()->undefined_value());
    target->shared()->code()->set_optimizable(false);
    // Clear the optimization hints related to the compiled code as these are no
    // longer valid when the code is overwritten.
    target->shared()->ClearThisPropertyAssignmentsInfo();
    context = Handle<Context>(fun->context());

    // Make sure we get a fresh copy of the literal vector to avoid
    // cross context contamination.
    int number_of_literals = fun->NumberOfLiterals();
    Handle<FixedArray> literals =
        isolate->factory()->NewFixedArray(number_of_literals, TENURED);
    if (number_of_literals > 0) {
      // Insert the object, regexp and array functions in the literals
      // array prefix.  These are the functions that will be used when
      // creating object, regexp and array literals.
      literals->set(JSFunction::kLiteralGlobalContextIndex,
                    context->global_context());
    }
    target->set_literals(*literals);
    target->set_next_function_link(isolate->heap()->undefined_value());

    if (isolate->logger()->is_logging() || CpuProfiler::is_profiling(isolate)) {
      isolate->logger()->LogExistingFunction(
          shared, Handle<Code>(shared->code()));
    }
  }

  target->set_context(*context);
  return *target;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SetExpectedNumberOfProperties) {
  HandleScope scope(isolate);
  ASSERT(args.length() == 2);
  CONVERT_ARG_HANDLE_CHECKED(JSFunction, function, 0);
  CONVERT_SMI_ARG_CHECKED(num, 1);
  RUNTIME_ASSERT(num >= 0);
  SetExpectedNofProperties(function, num);
  return isolate->heap()->undefined_value();
}


MUST_USE_RESULT static MaybeObject* CharFromCode(Isolate* isolate,
                                                 Object* char_code) {
  uint32_t code;
  if (char_code->ToArrayIndex(&code)) {
    if (code <= 0xffff) {
      return isolate->heap()->LookupSingleCharacterStringFromCode(code);
    }
  }
  return isolate->heap()->empty_string();
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_StringCharCodeAt) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);

  CONVERT_ARG_CHECKED(String, subject, 0);
  Object* index = args[1];
  RUNTIME_ASSERT(index->IsNumber());

  uint32_t i = 0;
  if (index->IsSmi()) {
    int value = Smi::cast(index)->value();
    if (value < 0) return isolate->heap()->nan_value();
    i = value;
  } else {
    ASSERT(index->IsHeapNumber());
    double value = HeapNumber::cast(index)->value();
    i = static_cast<uint32_t>(DoubleToInteger(value));
  }

  // Flatten the string.  If someone wants to get a char at an index
  // in a cons string, it is likely that more indices will be
  // accessed.
  Object* flat;
  { MaybeObject* maybe_flat = subject->TryFlatten();
    if (!maybe_flat->ToObject(&flat)) return maybe_flat;
  }
  subject = String::cast(flat);

  if (i >= static_cast<uint32_t>(subject->length())) {
    return isolate->heap()->nan_value();
  }

  return Smi::FromInt(subject->Get(i));
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_CharFromCode) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 1);
  return CharFromCode(isolate, args[0]);
}


class FixedArrayBuilder {
 public:
  explicit FixedArrayBuilder(Isolate* isolate, int initial_capacity)
      : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
        length_(0),
        has_non_smi_elements_(false) {
    // Require a non-zero initial size. Ensures that doubling the size to
    // extend the array will work.
    ASSERT(initial_capacity > 0);
  }

  explicit FixedArrayBuilder(Handle<FixedArray> backing_store)
      : array_(backing_store),
        length_(0),
        has_non_smi_elements_(false) {
    // Require a non-zero initial size. Ensures that doubling the size to
    // extend the array will work.
    ASSERT(backing_store->length() > 0);
  }

  bool HasCapacity(int elements) {
    int length = array_->length();
    int required_length = length_ + elements;
    return (length >= required_length);
  }

  void EnsureCapacity(int elements) {
    int length = array_->length();
    int required_length = length_ + elements;
    if (length < required_length) {
      int new_length = length;
      do {
        new_length *= 2;
      } while (new_length < required_length);
      Handle<FixedArray> extended_array =
          array_->GetIsolate()->factory()->NewFixedArrayWithHoles(new_length);
      array_->CopyTo(0, *extended_array, 0, length_);
      array_ = extended_array;
    }
  }

  void Add(Object* value) {
    ASSERT(!value->IsSmi());
    ASSERT(length_ < capacity());
    array_->set(length_, value);
    length_++;
    has_non_smi_elements_ = true;
  }

  void Add(Smi* value) {
    ASSERT(value->IsSmi());
    ASSERT(length_ < capacity());
    array_->set(length_, value);
    length_++;
  }

  Handle<FixedArray> array() {
    return array_;
  }

  int length() {
    return length_;
  }

  int capacity() {
    return array_->length();
  }

  Handle<JSArray> ToJSArray() {
    Handle<JSArray> result_array = FACTORY->NewJSArrayWithElements(array_);
    result_array->set_length(Smi::FromInt(length_));
    return result_array;
  }

  Handle<JSArray> ToJSArray(Handle<JSArray> target_array) {
    FACTORY->SetContent(target_array, array_);
    target_array->set_length(Smi::FromInt(length_));
    return target_array;
  }

 private:
  Handle<FixedArray> array_;
  int length_;
  bool has_non_smi_elements_;
};


// Forward declarations.
const int kStringBuilderConcatHelperLengthBits = 11;
const int kStringBuilderConcatHelperPositionBits = 19;

template <typename schar>
static inline void StringBuilderConcatHelper(String*,
                                             schar*,
                                             FixedArray*,
                                             int);

typedef BitField<int, 0, kStringBuilderConcatHelperLengthBits>
    StringBuilderSubstringLength;
typedef BitField<int,
                 kStringBuilderConcatHelperLengthBits,
                 kStringBuilderConcatHelperPositionBits>
    StringBuilderSubstringPosition;


class ReplacementStringBuilder {
 public:
  ReplacementStringBuilder(Heap* heap,
                           Handle<String> subject,
                           int estimated_part_count)
      : heap_(heap),
        array_builder_(heap->isolate(), estimated_part_count),
        subject_(subject),
        character_count_(0),
        is_ascii_(subject->IsAsciiRepresentation()) {
    // Require a non-zero initial size. Ensures that doubling the size to
    // extend the array will work.
    ASSERT(estimated_part_count > 0);
  }

  static inline void AddSubjectSlice(FixedArrayBuilder* builder,
                                     int from,
                                     int to) {
    ASSERT(from >= 0);
    int length = to - from;
    ASSERT(length > 0);
    if (StringBuilderSubstringLength::is_valid(length) &&
        StringBuilderSubstringPosition::is_valid(from)) {
      int encoded_slice = StringBuilderSubstringLength::encode(length) |
          StringBuilderSubstringPosition::encode(from);
      builder->Add(Smi::FromInt(encoded_slice));
    } else {
      // Otherwise encode as two smis.
      builder->Add(Smi::FromInt(-length));
      builder->Add(Smi::FromInt(from));
    }
  }


  void EnsureCapacity(int elements) {
    array_builder_.EnsureCapacity(elements);
  }


  void AddSubjectSlice(int from, int to) {
    AddSubjectSlice(&array_builder_, from, to);
    IncrementCharacterCount(to - from);
  }


  void AddString(Handle<String> string) {
    int length = string->length();
    ASSERT(length > 0);
    AddElement(*string);
    if (!string->IsAsciiRepresentation()) {
      is_ascii_ = false;
    }
    IncrementCharacterCount(length);
  }


  Handle<String> ToString() {
    if (array_builder_.length() == 0) {
      return heap_->isolate()->factory()->empty_string();
    }

    Handle<String> joined_string;
    if (is_ascii_) {
      Handle<SeqAsciiString> seq = NewRawAsciiString(character_count_);
      AssertNoAllocation no_alloc;
      char* char_buffer = seq->GetChars();
      StringBuilderConcatHelper(*subject_,
                                char_buffer,
                                *array_builder_.array(),
                                array_builder_.length());
      joined_string = Handle<String>::cast(seq);
    } else {
      // Non-ASCII.
      Handle<SeqTwoByteString> seq = NewRawTwoByteString(character_count_);
      AssertNoAllocation no_alloc;
      uc16* char_buffer = seq->GetChars();
      StringBuilderConcatHelper(*subject_,
                                char_buffer,
                                *array_builder_.array(),
                                array_builder_.length());
      joined_string = Handle<String>::cast(seq);
    }
    return joined_string;
  }


  void IncrementCharacterCount(int by) {
    if (character_count_ > String::kMaxLength - by) {
      V8::FatalProcessOutOfMemory("String.replace result too large.");
    }
    character_count_ += by;
  }

  Handle<JSArray> GetParts() {
    return array_builder_.ToJSArray();
  }

 private:
  Handle<SeqAsciiString> NewRawAsciiString(int length) {
    return heap_->isolate()->factory()->NewRawAsciiString(length);
  }


  Handle<SeqTwoByteString> NewRawTwoByteString(int length) {
    return heap_->isolate()->factory()->NewRawTwoByteString(length);
  }


  void AddElement(Object* element) {
    ASSERT(element->IsSmi() || element->IsString());
    ASSERT(array_builder_.capacity() > array_builder_.length());
    array_builder_.Add(element);
  }

  Heap* heap_;
  FixedArrayBuilder array_builder_;
  Handle<String> subject_;
  int character_count_;
  bool is_ascii_;
};


class CompiledReplacement {
 public:
  CompiledReplacement()
      : parts_(1), replacement_substrings_(0), simple_hint_(false) {}

  void Compile(Handle<String> replacement,
               int capture_count,
               int subject_length);

  void Apply(ReplacementStringBuilder* builder,
             int match_from,
             int match_to,
             Handle<JSArray> last_match_info);

  // Number of distinct parts of the replacement pattern.
  int parts() {
    return parts_.length();
  }

  bool simple_hint() {
    return simple_hint_;
  }

 private:
  enum PartType {
    SUBJECT_PREFIX = 1,
    SUBJECT_SUFFIX,
    SUBJECT_CAPTURE,
    REPLACEMENT_SUBSTRING,
    REPLACEMENT_STRING,

    NUMBER_OF_PART_TYPES
  };

  struct ReplacementPart {
    static inline ReplacementPart SubjectMatch() {
      return ReplacementPart(SUBJECT_CAPTURE, 0);
    }
    static inline ReplacementPart SubjectCapture(int capture_index) {
      return ReplacementPart(SUBJECT_CAPTURE, capture_index);
    }
    static inline ReplacementPart SubjectPrefix() {
      return ReplacementPart(SUBJECT_PREFIX, 0);
    }
    static inline ReplacementPart SubjectSuffix(int subject_length) {
      return ReplacementPart(SUBJECT_SUFFIX, subject_length);
    }
    static inline ReplacementPart ReplacementString() {
      return ReplacementPart(REPLACEMENT_STRING, 0);
    }
    static inline ReplacementPart ReplacementSubString(int from, int to) {
      ASSERT(from >= 0);
      ASSERT(to > from);
      return ReplacementPart(-from, to);
    }

    // If tag <= 0 then it is the negation of a start index of a substring of
    // the replacement pattern, otherwise it's a value from PartType.
    ReplacementPart(int tag, int data)
        : tag(tag), data(data) {
      // Must be non-positive or a PartType value.
      ASSERT(tag < NUMBER_OF_PART_TYPES);
    }
    // Either a value of PartType or a non-positive number that is
    // the negation of an index into the replacement string.
    int tag;
    // The data value's interpretation depends on the value of tag:
    // tag == SUBJECT_PREFIX ||
    // tag == SUBJECT_SUFFIX:  data is unused.
    // tag == SUBJECT_CAPTURE: data is the number of the capture.
    // tag == REPLACEMENT_SUBSTRING ||
    // tag == REPLACEMENT_STRING:    data is index into array of substrings
    //                               of the replacement string.
    // tag <= 0: Temporary representation of the substring of the replacement
    //           string ranging over -tag .. data.
    //           Is replaced by REPLACEMENT_{SUB,}STRING when we create the
    //           substring objects.
    int data;
  };

  template<typename Char>
  static bool ParseReplacementPattern(ZoneList<ReplacementPart>* parts,
                                      Vector<Char> characters,
                                      int capture_count,
                                      int subject_length) {
    int length = characters.length();
    int last = 0;
    for (int i = 0; i < length; i++) {
      Char c = characters[i];
      if (c == '$') {
        int next_index = i + 1;
        if (next_index == length) {  // No next character!
          break;
        }
        Char c2 = characters[next_index];
        switch (c2) {
        case '$':
          if (i > last) {
            // There is a substring before. Include the first "$".
            parts->Add(ReplacementPart::ReplacementSubString(last, next_index));
            last = next_index + 1;  // Continue after the second "$".
          } else {
            // Let the next substring start with the second "$".
            last = next_index;
          }
          i = next_index;
          break;
        case '`':
          if (i > last) {
            parts->Add(ReplacementPart::ReplacementSubString(last, i));
          }
          parts->Add(ReplacementPart::SubjectPrefix());
          i = next_index;
          last = i + 1;
          break;
        case '\'':
          if (i > last) {
            parts->Add(ReplacementPart::ReplacementSubString(last, i));
          }
          parts->Add(ReplacementPart::SubjectSuffix(subject_length));
          i = next_index;
          last = i + 1;
          break;
        case '&':
          if (i > last) {
            parts->Add(ReplacementPart::ReplacementSubString(last, i));
          }
          parts->Add(ReplacementPart::SubjectMatch());
          i = next_index;
          last = i + 1;
          break;
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9': {
          int capture_ref = c2 - '0';
          if (capture_ref > capture_count) {
            i = next_index;
            continue;
          }
          int second_digit_index = next_index + 1;
          if (second_digit_index < length) {
            // Peek ahead to see if we have two digits.
            Char c3 = characters[second_digit_index];
            if ('0' <= c3 && c3 <= '9') {  // Double digits.
              int double_digit_ref = capture_ref * 10 + c3 - '0';
              if (double_digit_ref <= capture_count) {
                next_index = second_digit_index;
                capture_ref = double_digit_ref;
              }
            }
          }
          if (capture_ref > 0) {
            if (i > last) {
              parts->Add(ReplacementPart::ReplacementSubString(last, i));
            }
            ASSERT(capture_ref <= capture_count);
            parts->Add(ReplacementPart::SubjectCapture(capture_ref));
            last = next_index + 1;
          }
          i = next_index;
          break;
        }
        default:
          i = next_index;
          break;
        }
      }
    }
    if (length > last) {
      if (last == 0) {
        parts->Add(ReplacementPart::ReplacementString());
        return true;
      } else {
        parts->Add(ReplacementPart::ReplacementSubString(last, length));
      }
    }
    return false;
  }

  ZoneList<ReplacementPart> parts_;
  ZoneList<Handle<String> > replacement_substrings_;
  bool simple_hint_;
};


void CompiledReplacement::Compile(Handle<String> replacement,
                                  int capture_count,
                                  int subject_length) {
  {
    AssertNoAllocation no_alloc;
    String::FlatContent content = replacement->GetFlatContent();
    ASSERT(content.IsFlat());
    if (content.IsAscii()) {
      simple_hint_ = ParseReplacementPattern(&parts_,
                                             content.ToAsciiVector(),
                                             capture_count,
                                             subject_length);
    } else {
      ASSERT(content.IsTwoByte());
      simple_hint_ = ParseReplacementPattern(&parts_,
                                             content.ToUC16Vector(),
                                             capture_count,
                                             subject_length);
    }
  }
  Isolate* isolate = replacement->GetIsolate();
  // Find substrings of replacement string and create them as String objects.
  int substring_index = 0;
  for (int i = 0, n = parts_.length(); i < n; i++) {
    int tag = parts_[i].tag;
    if (tag <= 0) {  // A replacement string slice.
      int from = -tag;
      int to = parts_[i].data;
      replacement_substrings_.Add(
          isolate->factory()->NewSubString(replacement, from, to));
      parts_[i].tag = REPLACEMENT_SUBSTRING;
      parts_[i].data = substring_index;
      substring_index++;
    } else if (tag == REPLACEMENT_STRING) {
      replacement_substrings_.Add(replacement);
      parts_[i].data = substring_index;
      substring_index++;
    }
  }
}


void CompiledReplacement::Apply(ReplacementStringBuilder* builder,
                                int match_from,
                                int match_to,
                                Handle<JSArray> last_match_info) {
  for (int i = 0, n = parts_.length(); i < n; i++) {
    ReplacementPart part = parts_[i];
    switch (part.tag) {
      case SUBJECT_PREFIX:
        if (match_from > 0) builder->AddSubjectSlice(0, match_from);
        break;
      case SUBJECT_SUFFIX: {
        int subject_length = part.data;
        if (match_to < subject_length) {
          builder->AddSubjectSlice(match_to, subject_length);
        }
        break;
      }
      case SUBJECT_CAPTURE: {
        int capture = part.data;
        FixedArray* match_info = FixedArray::cast(last_match_info->elements());
        int from = RegExpImpl::GetCapture(match_info, capture * 2);
        int to = RegExpImpl::GetCapture(match_info, capture * 2 + 1);
        if (from >= 0 && to > from) {
          builder->AddSubjectSlice(from, to);
        }
        break;
      }
      case REPLACEMENT_SUBSTRING:
      case REPLACEMENT_STRING:
        builder->AddString(replacement_substrings_[part.data]);
        break;
      default:
        UNREACHABLE();
    }
  }
}


void FindAsciiStringIndices(Vector<const char> subject,
                            char pattern,
                            ZoneList<int>* indices,
                            unsigned int limit) {
  ASSERT(limit > 0);
  // Collect indices of pattern in subject using memchr.
  // Stop after finding at most limit values.
  const char* subject_start = reinterpret_cast<const char*>(subject.start());
  const char* subject_end = subject_start + subject.length();
  const char* pos = subject_start;
  while (limit > 0) {
    pos = reinterpret_cast<const char*>(
        memchr(pos, pattern, subject_end - pos));
    if (pos == NULL) return;
    indices->Add(static_cast<int>(pos - subject_start));
    pos++;
    limit--;
  }
}


template <typename SubjectChar, typename PatternChar>
void FindStringIndices(Isolate* isolate,
                       Vector<const SubjectChar> subject,
                       Vector<const PatternChar> pattern,
                       ZoneList<int>* indices,
                       unsigned int limit) {
  ASSERT(limit > 0);
  // Collect indices of pattern in subject.
  // Stop after finding at most limit values.
  int pattern_length = pattern.length();
  int index = 0;
  StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
  while (limit > 0) {
    index = search.Search(subject, index);
    if (index < 0) return;
    indices->Add(index);
    index += pattern_length;
    limit--;
  }
}


void FindStringIndicesDispatch(Isolate* isolate,
                               String* subject,
                               String* pattern,
                               ZoneList<int>* indices,
                               unsigned int limit) {
  {
    AssertNoAllocation no_gc;
    String::FlatContent subject_content = subject->GetFlatContent();
    String::FlatContent pattern_content = pattern->GetFlatContent();
    ASSERT(subject_content.IsFlat());
    ASSERT(pattern_content.IsFlat());
    if (subject_content.IsAscii()) {
      Vector<const char> subject_vector = subject_content.ToAsciiVector();
      if (pattern_content.IsAscii()) {
        Vector<const char> pattern_vector = pattern_content.ToAsciiVector();
        if (pattern_vector.length() == 1) {
          FindAsciiStringIndices(subject_vector,
                                 pattern_vector[0],
                                 indices,
                                 limit);
        } else {
          FindStringIndices(isolate,
                            subject_vector,
                            pattern_vector,
                            indices,
                            limit);
        }
      } else {
        FindStringIndices(isolate,
                          subject_vector,
                          pattern_content.ToUC16Vector(),
                          indices,
                          limit);
      }
    } else {
      Vector<const uc16> subject_vector = subject_content.ToUC16Vector();
      if (pattern_content.IsAscii()) {
        FindStringIndices(isolate,
                          subject_vector,
                          pattern_content.ToAsciiVector(),
                          indices,
                          limit);
      } else {
        FindStringIndices(isolate,
                          subject_vector,
                          pattern_content.ToUC16Vector(),
                          indices,
                          limit);
      }
    }
  }
}


template<typename ResultSeqString>
MUST_USE_RESULT static MaybeObject* StringReplaceStringWithString(
    Isolate* isolate,
    Handle<String> subject,
    Handle<JSRegExp> pattern_regexp,
    Handle<String> replacement) {
  ASSERT(subject->IsFlat());
  ASSERT(replacement->IsFlat());

  ZoneScope zone_space(isolate, DELETE_ON_EXIT);
  ZoneList<int> indices(8);
  ASSERT_EQ(JSRegExp::ATOM, pattern_regexp->TypeTag());
  String* pattern =
      String::cast(pattern_regexp->DataAt(JSRegExp::kAtomPatternIndex));
  int subject_len = subject->length();
  int pattern_len = pattern->length();
  int replacement_len = replacement->length();

  FindStringIndicesDispatch(isolate, *subject, pattern, &indices, 0xffffffff);

  int matches = indices.length();
  if (matches == 0) return *subject;

  int result_len = (replacement_len - pattern_len) * matches + subject_len;
  int subject_pos = 0;
  int result_pos = 0;

  Handle<ResultSeqString> result;
  if (ResultSeqString::kHasAsciiEncoding) {
    result = Handle<ResultSeqString>::cast(
        isolate->factory()->NewRawAsciiString(result_len));
  } else {
    result = Handle<ResultSeqString>::cast(
        isolate->factory()->NewRawTwoByteString(result_len));
  }

  for (int i = 0; i < matches; i++) {
    // Copy non-matched subject content.
    if (subject_pos < indices.at(i)) {
      String::WriteToFlat(*subject,
                          result->GetChars() + result_pos,
                          subject_pos,
                          indices.at(i));
      result_pos += indices.at(i) - subject_pos;
    }

    // Replace match.
    if (replacement_len > 0) {
      String::WriteToFlat(*replacement,
                          result->GetChars() + result_pos,
                          0,
                          replacement_len);
      result_pos += replacement_len;
    }

    subject_pos = indices.at(i) + pattern_len;
  }
  // Add remaining subject content at the end.
  if (subject_pos < subject_len) {
    String::WriteToFlat(*subject,
                        result->GetChars() + result_pos,
                        subject_pos,
                        subject_len);
  }
  return *result;
}


MUST_USE_RESULT static MaybeObject* StringReplaceRegExpWithString(
    Isolate* isolate,
    String* subject,
    JSRegExp* regexp,
    String* replacement,
    JSArray* last_match_info) {
  ASSERT(subject->IsFlat());
  ASSERT(replacement->IsFlat());

  HandleScope handles(isolate);

  int length = subject->length();
  Handle<String> subject_handle(subject);
  Handle<JSRegExp> regexp_handle(regexp);
  Handle<String> replacement_handle(replacement);
  Handle<JSArray> last_match_info_handle(last_match_info);
  Handle<Object> match = RegExpImpl::Exec(regexp_handle,
                                          subject_handle,
                                          0,
                                          last_match_info_handle);
  if (match.is_null()) {
    return Failure::Exception();
  }
  if (match->IsNull()) {
    return *subject_handle;
  }

  int capture_count = regexp_handle->CaptureCount();

  // CompiledReplacement uses zone allocation.
  ZoneScope zone(isolate, DELETE_ON_EXIT);
  CompiledReplacement compiled_replacement;
  compiled_replacement.Compile(replacement_handle,
                               capture_count,
                               length);

  bool is_global = regexp_handle->GetFlags().is_global();

  // Shortcut for simple non-regexp global replacements
  if (is_global &&
      regexp_handle->TypeTag() == JSRegExp::ATOM &&
      compiled_replacement.simple_hint()) {
    if (subject_handle->HasOnlyAsciiChars() &&
        replacement_handle->HasOnlyAsciiChars()) {
      return StringReplaceStringWithString<SeqAsciiString>(
          isolate, subject_handle, regexp_handle, replacement_handle);
    } else {
      return StringReplaceStringWithString<SeqTwoByteString>(
          isolate, subject_handle, regexp_handle, replacement_handle);
    }
  }

  // Guessing the number of parts that the final result string is built
  // from. Global regexps can match any number of times, so we guess
  // conservatively.
  int expected_parts =
      (compiled_replacement.parts() + 1) * (is_global ? 4 : 1) + 1;
  ReplacementStringBuilder builder(isolate->heap(),
                                   subject_handle,
                                   expected_parts);

  // Index of end of last match.
  int prev = 0;

  // Number of parts added by compiled replacement plus preceeding
  // string and possibly suffix after last match.  It is possible for
  // all components to use two elements when encoded as two smis.
  const int parts_added_per_loop = 2 * (compiled_replacement.parts() + 2);
  bool matched = true;
  do {
    ASSERT(last_match_info_handle->HasFastElements());
    // Increase the capacity of the builder before entering local handle-scope,
    // so its internal buffer can safely allocate a new handle if it grows.
    builder.EnsureCapacity(parts_added_per_loop);

    HandleScope loop_scope(isolate);
    int start, end;
    {
      AssertNoAllocation match_info_array_is_not_in_a_handle;
      FixedArray* match_info_array =
          FixedArray::cast(last_match_info_handle->elements());

      ASSERT_EQ(capture_count * 2 + 2,
                RegExpImpl::GetLastCaptureCount(match_info_array));
      start = RegExpImpl::GetCapture(match_info_array, 0);
      end = RegExpImpl::GetCapture(match_info_array, 1);
    }

    if (prev < start) {
      builder.AddSubjectSlice(prev, start);
    }
    compiled_replacement.Apply(&builder,
                               start,
                               end,
                               last_match_info_handle);
    prev = end;

    // Only continue checking for global regexps.
    if (!is_global) break;

    // Continue from where the match ended, unless it was an empty match.
    int next = end;
    if (start == end) {
      next = end + 1;
      if (next > length) break;
    }

    match = RegExpImpl::Exec(regexp_handle,
                             subject_handle,
                             next,
                             last_match_info_handle);
    if (match.is_null()) {
      return Failure::Exception();
    }
    matched = !match->IsNull();
  } while (matched);

  if (prev < length) {
    builder.AddSubjectSlice(prev, length);
  }

  return *(builder.ToString());
}


template <typename ResultSeqString>
MUST_USE_RESULT static MaybeObject* StringReplaceRegExpWithEmptyString(
    Isolate* isolate,
    String* subject,
    JSRegExp* regexp,
    JSArray* last_match_info) {
  ASSERT(subject->IsFlat());

  HandleScope handles(isolate);

  Handle<String> subject_handle(subject);
  Handle<JSRegExp> regexp_handle(regexp);

  // Shortcut for simple non-regexp global replacements
  if (regexp_handle->GetFlags().is_global() &&
      regexp_handle->TypeTag() == JSRegExp::ATOM) {
    Handle<String> empty_string_handle(HEAP->empty_string());
    if (subject_handle->HasOnlyAsciiChars()) {
      return StringReplaceStringWithString<SeqAsciiString>(
          isolate, subject_handle, regexp_handle, empty_string_handle);
    } else {
      return StringReplaceStringWithString<SeqTwoByteString>(
          isolate, subject_handle, regexp_handle, empty_string_handle);
    }
  }

  Handle<JSArray> last_match_info_handle(last_match_info);
  Handle<Object> match = RegExpImpl::Exec(regexp_handle,
                                          subject_handle,
                                          0,
                                          last_match_info_handle);
  if (match.is_null()) return Failure::Exception();
  if (match->IsNull()) return *subject_handle;

  ASSERT(last_match_info_handle->HasFastElements());

  int start, end;
  {
    AssertNoAllocation match_info_array_is_not_in_a_handle;
    FixedArray* match_info_array =
        FixedArray::cast(last_match_info_handle->elements());

    start = RegExpImpl::GetCapture(match_info_array, 0);
    end = RegExpImpl::GetCapture(match_info_array, 1);
  }

  int length = subject_handle->length();
  int new_length = length - (end - start);
  if (new_length == 0) {
    return isolate->heap()->empty_string();
  }
  Handle<ResultSeqString> answer;
  if (ResultSeqString::kHasAsciiEncoding) {
    answer = Handle<ResultSeqString>::cast(
        isolate->factory()->NewRawAsciiString(new_length));
  } else {
    answer = Handle<ResultSeqString>::cast(
        isolate->factory()->NewRawTwoByteString(new_length));
  }

  // If the regexp isn't global, only match once.
  if (!regexp_handle->GetFlags().is_global()) {
    if (start > 0) {
      String::WriteToFlat(*subject_handle,
                          answer->GetChars(),
                          0,
                          start);
    }
    if (end < length) {
      String::WriteToFlat(*subject_handle,
                          answer->GetChars() + start,
                          end,
                          length);
    }
    return *answer;
  }

  int prev = 0;  // Index of end of last match.
  int next = 0;  // Start of next search (prev unless last match was empty).
  int position = 0;

  do {
    if (prev < start) {
      // Add substring subject[prev;start] to answer string.
      String::WriteToFlat(*subject_handle,
                          answer->GetChars() + position,
                          prev,
                          start);
      position += start - prev;
    }
    prev = end;
    next = end;
    // Continue from where the match ended, unless it was an empty match.
    if (start == end) {
      next++;
      if (next > length) break;
    }
    match = RegExpImpl::Exec(regexp_handle,
                             subject_handle,
                             next,
                             last_match_info_handle);
    if (match.is_null()) return Failure::Exception();
    if (match->IsNull()) break;

    ASSERT(last_match_info_handle->HasFastElements());
    HandleScope loop_scope(isolate);
    {
      AssertNoAllocation match_info_array_is_not_in_a_handle;
      FixedArray* match_info_array =
          FixedArray::cast(last_match_info_handle->elements());
      start = RegExpImpl::GetCapture(match_info_array, 0);
      end = RegExpImpl::GetCapture(match_info_array, 1);
    }
  } while (true);

  if (prev < length) {
    // Add substring subject[prev;length] to answer string.
    String::WriteToFlat(*subject_handle,
                        answer->GetChars() + position,
                        prev,
                        length);
    position += length - prev;
  }

  if (position == 0) {
    return isolate->heap()->empty_string();
  }

  // Shorten string and fill
  int string_size = ResultSeqString::SizeFor(position);
  int allocated_string_size = ResultSeqString::SizeFor(new_length);
  int delta = allocated_string_size - string_size;

  answer->set_length(position);
  if (delta == 0) return *answer;

  Address end_of_string = answer->address() + string_size;
  isolate->heap()->CreateFillerObjectAt(end_of_string, delta);
  if (Marking::IsBlack(Marking::MarkBitFrom(*answer))) {
    MemoryChunk::IncrementLiveBytesFromMutator(answer->address(), -delta);
  }

  return *answer;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_StringReplaceRegExpWithString) {
  ASSERT(args.length() == 4);

  CONVERT_ARG_CHECKED(String, subject, 0);
  if (!subject->IsFlat()) {
    Object* flat_subject;
    { MaybeObject* maybe_flat_subject = subject->TryFlatten();
      if (!maybe_flat_subject->ToObject(&flat_subject)) {
        return maybe_flat_subject;
      }
    }
    subject = String::cast(flat_subject);
  }

  CONVERT_ARG_CHECKED(String, replacement, 2);
  if (!replacement->IsFlat()) {
    Object* flat_replacement;
    { MaybeObject* maybe_flat_replacement = replacement->TryFlatten();
      if (!maybe_flat_replacement->ToObject(&flat_replacement)) {
        return maybe_flat_replacement;
      }
    }
    replacement = String::cast(flat_replacement);
  }

  CONVERT_ARG_CHECKED(JSRegExp, regexp, 1);
  CONVERT_ARG_CHECKED(JSArray, last_match_info, 3);

  ASSERT(last_match_info->HasFastElements());

  if (replacement->length() == 0) {
    if (subject->HasOnlyAsciiChars()) {
      return StringReplaceRegExpWithEmptyString<SeqAsciiString>(
          isolate, subject, regexp, last_match_info);
    } else {
      return StringReplaceRegExpWithEmptyString<SeqTwoByteString>(
          isolate, subject, regexp, last_match_info);
    }
  }

  return StringReplaceRegExpWithString(isolate,
                                       subject,
                                       regexp,
                                       replacement,
                                       last_match_info);
}


Handle<String> Runtime::StringReplaceOneCharWithString(Isolate* isolate,
                                                       Handle<String> subject,
                                                       Handle<String> search,
                                                       Handle<String> replace,
                                                       bool* found,
                                                       int recursion_limit) {
  if (recursion_limit == 0) return Handle<String>::null();
  if (subject->IsConsString()) {
    ConsString* cons = ConsString::cast(*subject);
    Handle<String> first = Handle<String>(cons->first());
    Handle<String> second = Handle<String>(cons->second());
    Handle<String> new_first =
        StringReplaceOneCharWithString(isolate,
                                       first,
                                       search,
                                       replace,
                                       found,
                                       recursion_limit - 1);
    if (*found) return isolate->factory()->NewConsString(new_first, second);
    if (new_first.is_null()) return new_first;

    Handle<String> new_second =
        StringReplaceOneCharWithString(isolate,
                                       second,
                                       search,
                                       replace,
                                       found,
                                       recursion_limit - 1);
    if (*found) return isolate->factory()->NewConsString(first, new_second);
    if (new_second.is_null()) return new_second;

    return subject;
  } else {
    int index = StringMatch(isolate, subject, search, 0);
    if (index == -1) return subject;
    *found = true;
    Handle<String> first = isolate->factory()->NewSubString(subject, 0, index);
    Handle<String> cons1 = isolate->factory()->NewConsString(first, replace);
    Handle<String> second =
        isolate->factory()->NewSubString(subject, index + 1, subject->length());
    return isolate->factory()->NewConsString(cons1, second);
  }
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_StringReplaceOneCharWithString) {
  ASSERT(args.length() == 3);
  HandleScope scope(isolate);
  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, search, 1);
  CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);

  // If the cons string tree is too deep, we simply abort the recursion and
  // retry with a flattened subject string.
  const int kRecursionLimit = 0x1000;
  bool found = false;
  Handle<String> result =
      Runtime::StringReplaceOneCharWithString(isolate,
                                              subject,
                                              search,
                                              replace,
                                              &found,
                                              kRecursionLimit);
  if (!result.is_null()) return *result;
  return *Runtime::StringReplaceOneCharWithString(isolate,
                                                  FlattenGetString(subject),
                                                  search,
                                                  replace,
                                                  &found,
                                                  kRecursionLimit);
}


// Perform string match of pattern on subject, starting at start index.
// Caller must ensure that 0 <= start_index <= sub->length(),
// and should check that pat->length() + start_index <= sub->length().
int Runtime::StringMatch(Isolate* isolate,
                         Handle<String> sub,
                         Handle<String> pat,
                         int start_index) {
  ASSERT(0 <= start_index);
  ASSERT(start_index <= sub->length());

  int pattern_length = pat->length();
  if (pattern_length == 0) return start_index;

  int subject_length = sub->length();
  if (start_index + pattern_length > subject_length) return -1;

  if (!sub->IsFlat()) FlattenString(sub);
  if (!pat->IsFlat()) FlattenString(pat);

  AssertNoAllocation no_heap_allocation;  // ensure vectors stay valid
  // Extract flattened substrings of cons strings before determining asciiness.
  String::FlatContent seq_sub = sub->GetFlatContent();
  String::FlatContent seq_pat = pat->GetFlatContent();

  // dispatch on type of strings
  if (seq_pat.IsAscii()) {
    Vector<const char> pat_vector = seq_pat.ToAsciiVector();
    if (seq_sub.IsAscii()) {
      return SearchString(isolate,
                          seq_sub.ToAsciiVector(),
                          pat_vector,
                          start_index);
    }
    return SearchString(isolate,
                        seq_sub.ToUC16Vector(),
                        pat_vector,
                        start_index);
  }
  Vector<const uc16> pat_vector = seq_pat.ToUC16Vector();
  if (seq_sub.IsAscii()) {
    return SearchString(isolate,
                        seq_sub.ToAsciiVector(),
                        pat_vector,
                        start_index);
  }
  return SearchString(isolate,
                      seq_sub.ToUC16Vector(),
                      pat_vector,
                      start_index);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_StringIndexOf) {
  HandleScope scope(isolate);  // create a new handle scope
  ASSERT(args.length() == 3);

  CONVERT_ARG_HANDLE_CHECKED(String, sub, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, pat, 1);

  Object* index = args[2];
  uint32_t start_index;
  if (!index->ToArrayIndex(&start_index)) return Smi::FromInt(-1);

  RUNTIME_ASSERT(start_index <= static_cast<uint32_t>(sub->length()));
  int position =
      Runtime::StringMatch(isolate, sub, pat, start_index);
  return Smi::FromInt(position);
}


template <typename schar, typename pchar>
static int StringMatchBackwards(Vector<const schar> subject,
                                Vector<const pchar> pattern,
                                int idx) {
  int pattern_length = pattern.length();
  ASSERT(pattern_length >= 1);
  ASSERT(idx + pattern_length <= subject.length());

  if (sizeof(schar) == 1 && sizeof(pchar) > 1) {
    for (int i = 0; i < pattern_length; i++) {
      uc16 c = pattern[i];
      if (c > String::kMaxAsciiCharCode) {
        return -1;
      }
    }
  }

  pchar pattern_first_char = pattern[0];
  for (int i = idx; i >= 0; i--) {
    if (subject[i] != pattern_first_char) continue;
    int j = 1;
    while (j < pattern_length) {
      if (pattern[j] != subject[i+j]) {
        break;
      }
      j++;
    }
    if (j == pattern_length) {
      return i;
    }
  }
  return -1;
}

RUNTIME_FUNCTION(MaybeObject*, Runtime_StringLastIndexOf) {
  HandleScope scope(isolate);  // create a new handle scope
  ASSERT(args.length() == 3);

  CONVERT_ARG_HANDLE_CHECKED(String, sub, 0);
  CONVERT_ARG_HANDLE_CHECKED(String, pat, 1);

  Object* index = args[2];
  uint32_t start_index;
  if (!index->ToArrayIndex(&start_index)) return Smi::FromInt(-1);

  uint32_t pat_length = pat->length();
  uint32_t sub_length = sub->length();

  if (start_index + pat_length > sub_length) {
    start_index = sub_length - pat_length;
  }

  if (pat_length == 0) {
    return Smi::FromInt(start_index);
  }

  if (!sub->IsFlat()) FlattenString(sub);
  if (!pat->IsFlat()) FlattenString(pat);

  int position = -1;
  AssertNoAllocation no_heap_allocation;  // ensure vectors stay valid

  String::FlatContent sub_content = sub->GetFlatContent();
  String::FlatContent pat_content = pat->GetFlatContent();

  if (pat_content.IsAscii()) {
    Vector<const char> pat_vector = pat_content.ToAsciiVector();
    if (sub_content.IsAscii()) {
      position = StringMatchBackwards(sub_content.ToAsciiVector(),
                                      pat_vector,
                                      start_index);
    } else {
      position = StringMatchBackwards(sub_content.ToUC16Vector(),
                                      pat_vector,
                                      start_index);
    }
  } else {
    Vector<const uc16> pat_vector = pat_content.ToUC16Vector();
    if (sub_content.IsAscii()) {
      position = StringMatchBackwards(sub_content.ToAsciiVector(),
                                      pat_vector,
                                      start_index);
    } else {
      position = StringMatchBackwards(sub_content.ToUC16Vector(),
                                      pat_vector,
                                      start_index);
    }
  }

  return Smi::FromInt(position);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_StringLocaleCompare) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 2);

  CONVERT_ARG_CHECKED(String, str1, 0);
  CONVERT_ARG_CHECKED(String, str2, 1);

  if (str1 == str2) return Smi::FromInt(0);  // Equal.
  int str1_length = str1->length();
  int str2_length = str2->length();

  // Decide trivial cases without flattening.
  if (str1_length == 0) {
    if (str2_length == 0) return Smi::FromInt(0);  // Equal.
    return Smi::FromInt(-str2_length);
  } else {
    if (str2_length == 0) return Smi::FromInt(str1_length);
  }

  int end = str1_length < str2_length ? str1_length : str2_length;

  // No need to flatten if we are going to find the answer on the first
  // character.  At this point we know there is at least one character
  // in each string, due to the trivial case handling above.
  int d = str1->Get(0) - str2->Get(0);
  if (d != 0) return Smi::FromInt(d);

  str1->TryFlatten();
  str2->TryFlatten();

  StringInputBuffer& buf1 =
      *isolate->runtime_state()->string_locale_compare_buf1();
  StringInputBuffer& buf2 =
      *isolate->runtime_state()->string_locale_compare_buf2();

  buf1.Reset(str1);
  buf2.Reset(str2);

  for (int i = 0; i < end; i++) {
    uint16_t char1 = buf1.GetNext();
    uint16_t char2 = buf2.GetNext();
    if (char1 != char2) return Smi::FromInt(char1 - char2);
  }

  return Smi::FromInt(str1_length - str2_length);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_SubString) {
  NoHandleAllocation ha;
  ASSERT(args.length() == 3);

  CONVERT_ARG_CHECKED(String, value, 0);
  int start, end;
  // We have a fast integer-only case here to avoid a conversion to double in
  // the common case where from and to are Smis.
  if (args[1]->IsSmi() && args[2]->IsSmi()) {
    CONVERT_SMI_ARG_CHECKED(from_number, 1);
    CONVERT_SMI_ARG_CHECKED(to_number, 2);
    start = from_number;
    end = to_number;
  } else {
    CONVERT_DOUBLE_ARG_CHECKED(from_number, 1);
    CONVERT_DOUBLE_ARG_CHECKED(to_number, 2);
    start = FastD2I(from_number);
    end = FastD2I(to_number);
  }
  RUNTIME_ASSERT(end >= start);
  RUNTIME_ASSERT(start >= 0);
  RUNTIME_ASSERT(end <= value->length());
  isolate->counters()->sub_string_runtime()->Increment();
  return value->SubString(start, end);
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_StringMatch) {
  ASSERT_EQ(3, args.length());

  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
  CONVERT_ARG_HANDLE_CHECKED(JSArray, regexp_info, 2);
  HandleScope handles;

  Handle<Object> match = RegExpImpl::Exec(regexp, subject, 0, regexp_info);

  if (match.is_null()) {
    return Failure::Exception();
  }
  if (match->IsNull()) {
    return isolate->heap()->null_value();
  }
  int length = subject->length();

  ZoneScope zone_space(isolate, DELETE_ON_EXIT);
  ZoneList<int> offsets(8);
  int start;
  int end;
  do {
    {
      AssertNoAllocation no_alloc;
      FixedArray* elements = FixedArray::cast(regexp_info->elements());
      start = Smi::cast(elements->get(RegExpImpl::kFirstCapture))->value();
      end = Smi::cast(elements->get(RegExpImpl::kFirstCapture + 1))->value();
    }
    offsets.Add(start);
    offsets.Add(end);
    if (start == end) if (++end > length) break;
    match = RegExpImpl::Exec(regexp, subject, end, regexp_info);
    if (match.is_null()) {
      return Failure::Exception();
    }
  } while (!match->IsNull());
  int matches = offsets.length() / 2;
  Handle<FixedArray> elements = isolate->factory()->NewFixedArray(matches);
  Handle<String> substring = isolate->factory()->
    NewSubString(subject, offsets.at(0), offsets.at(1));
  elements->set(0, *substring);
  for (int i = 1; i < matches ; i++) {
    int from = offsets.at(i * 2);
    int to = offsets.at(i * 2 + 1);
    Handle<String> substring = isolate->factory()->
        NewProperSubString(subject, from, to);
    elements->set(i, *substring);
  }
  Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements(elements);
  result->set_length(Smi::FromInt(matches));
  return *result;
}


// Two smis before and after the match, for very long strings.
const int kMaxBuilderEntriesPerRegExpMatch = 5;


static void SetLastMatchInfoNoCaptures(Handle<String> subject,
                                       Handle<JSArray> last_match_info,
                                       int match_start,
                                       int match_end) {
  // Fill last_match_info with a single capture.
  last_match_info->EnsureSize(2 + RegExpImpl::kLastMatchOverhead);
  AssertNoAllocation no_gc;
  FixedArray* elements = FixedArray::cast(last_match_info->elements());
  RegExpImpl::SetLastCaptureCount(elements, 2);
  RegExpImpl::SetLastInput(elements, *subject);
  RegExpImpl::SetLastSubject(elements, *subject);
  RegExpImpl::SetCapture(elements, 0, match_start);
  RegExpImpl::SetCapture(elements, 1, match_end);
}


template <typename SubjectChar, typename PatternChar>
static bool SearchStringMultiple(Isolate* isolate,
                                 Vector<const SubjectChar> subject,
                                 Vector<const PatternChar> pattern,
                                 String* pattern_string,
                                 FixedArrayBuilder* builder,
                                 int* match_pos) {
  int pos = *match_pos;
  int subject_length = subject.length();
  int pattern_length = pattern.length();
  int max_search_start = subject_length - pattern_length;
  StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
  while (pos <= max_search_start) {
    if (!builder->HasCapacity(kMaxBuilderEntriesPerRegExpMatch)) {
      *match_pos = pos;
      return false;
    }
    // Position of end of previous match.
    int match_end = pos + pattern_length;
    int new_pos = search.Search(subject, match_end);
    if (new_pos >= 0) {
      // A match.
      if (new_pos > match_end) {
        ReplacementStringBuilder::AddSubjectSlice(builder,
            match_end,
            new_pos);
      }
      pos = new_pos;
      builder->Add(pattern_string);
    } else {
      break;
    }
  }

  if (pos < max_search_start) {
    ReplacementStringBuilder::AddSubjectSlice(builder,
                                              pos + pattern_length,
                                              subject_length);
  }
  *match_pos = pos;
  return true;
}


static bool SearchStringMultiple(Isolate* isolate,
                                 Handle<String> subject,
                                 Handle<String> pattern,
                                 Handle<JSArray> last_match_info,
                                 FixedArrayBuilder* builder) {
  ASSERT(subject->IsFlat());
  ASSERT(pattern->IsFlat());

  // Treating as if a previous match was before first character.
  int match_pos = -pattern->length();

  for (;;) {  // Break when search complete.
    builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
    AssertNoAllocation no_gc;
    String::FlatContent subject_content = subject->GetFlatContent();
    String::FlatContent pattern_content = pattern->GetFlatContent();
    if (subject_content.IsAscii()) {
      Vector<const char> subject_vector = subject_content.ToAsciiVector();
      if (pattern_content.IsAscii()) {
        if (SearchStringMultiple(isolate,
                                 subject_vector,
                                 pattern_content.ToAsciiVector(),
                                 *pattern,
                                 builder,
                                 &match_pos)) break;
      } else {
        if (SearchStringMultiple(isolate,
                                 subject_vector,
                                 pattern_content.ToUC16Vector(),
                                 *pattern,
                                 builder,
                                 &match_pos)) break;
      }
    } else {
      Vector<const uc16> subject_vector = subject_content.ToUC16Vector();
      if (pattern_content.IsAscii()) {
        if (SearchStringMultiple(isolate,
                                 subject_vector,
                                 pattern_content.ToAsciiVector(),
                                 *pattern,
                                 builder,
                                 &match_pos)) break;
      } else {
        if (SearchStringMultiple(isolate,
                                 subject_vector,
                                 pattern_content.ToUC16Vector(),
                                 *pattern,
                                 builder,
                                 &match_pos)) break;
      }
    }
  }

  if (match_pos >= 0) {
    SetLastMatchInfoNoCaptures(subject,
                               last_match_info,
                               match_pos,
                               match_pos + pattern->length());
    return true;
  }
  return false;  // No matches at all.
}


static RegExpImpl::IrregexpResult SearchRegExpNoCaptureMultiple(
    Isolate* isolate,
    Handle<String> subject,
    Handle<JSRegExp> regexp,
    Handle<JSArray> last_match_array,
    FixedArrayBuilder* builder) {
  ASSERT(subject->IsFlat());
  int match_start = -1;
  int match_end = 0;
  int pos = 0;
  int required_registers = RegExpImpl::IrregexpPrepare(regexp, subject);
  if (required_registers < 0) return RegExpImpl::RE_EXCEPTION;

  OffsetsVector registers(required_registers, isolate);
  Vector<int32_t> register_vector(registers.vector(), registers.length());
  int subject_length = subject->length();
  bool first = true;

  for (;;) {  // Break on failure, return on exception.
    RegExpImpl::IrregexpResult result =
        RegExpImpl::IrregexpExecOnce(regexp,
                                     subject,
                                     pos,
                                     register_vector);
    if (result == RegExpImpl::RE_SUCCESS) {
      match_start = register_vector[0];
      builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
      if (match_end < match_start) {
        ReplacementStringBuilder::AddSubjectSlice(builder,
                                                  match_end,
                                                  match_start);
      }
      match_end = register_vector[1];
      HandleScope loop_scope(isolate);
      if (!first) {
        builder->Add(*isolate->factory()->NewProperSubString(subject,
                                                             match_start,
                                                             match_end));
      } else {
        builder->Add(*isolate->factory()->NewSubString(subject,
                                                       match_start,
                                                       match_end));
      }
      if (match_start != match_end) {
        pos = match_end;
      } else {
        pos = match_end + 1;
        if (pos > subject_length) break;
      }
    } else if (result == RegExpImpl::RE_FAILURE) {
      break;
    } else {
      ASSERT_EQ(result, RegExpImpl::RE_EXCEPTION);
      return result;
    }
    first = false;
  }

  if (match_start >= 0) {
    if (match_end < subject_length) {
      ReplacementStringBuilder::AddSubjectSlice(builder,
                                                match_end,
                                                subject_length);
    }
    SetLastMatchInfoNoCaptures(subject,
                               last_match_array,
                               match_start,
                               match_end);
    return RegExpImpl::RE_SUCCESS;
  } else {
    return RegExpImpl::RE_FAILURE;  // No matches at all.
  }
}


static RegExpImpl::IrregexpResult SearchRegExpMultiple(
    Isolate* isolate,
    Handle<String> subject,
    Handle<JSRegExp> regexp,
    Handle<JSArray> last_match_array,
    FixedArrayBuilder* builder) {

  ASSERT(subject->IsFlat());
  int required_registers = RegExpImpl::IrregexpPrepare(regexp, subject);
  if (required_registers < 0) return RegExpImpl::RE_EXCEPTION;

  OffsetsVector registers(required_registers, isolate);
  Vector<int32_t> register_vector(registers.vector(), registers.length());

  RegExpImpl::IrregexpResult result =
      RegExpImpl::IrregexpExecOnce(regexp,
                                   subject,
                                   0,
                                   register_vector);

  int capture_count = regexp->CaptureCount();
  int subject_length = subject->length();

  // Position to search from.
  int pos = 0;
  // End of previous match. Differs from pos if match was empty.
  int match_end = 0;
  if (result == RegExpImpl::RE_SUCCESS) {
    // Need to keep a copy of the previous match for creating last_match_info
    // at the end, so we have two vectors that we swap between.
    OffsetsVector registers2(required_registers, isolate);
    Vector<int> prev_register_vector(registers2.vector(), registers2.length());
    bool first = true;
    do {
      int match_start = register_vector[0];
      builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
      if (match_end < match_start) {
        ReplacementStringBuilder::AddSubjectSlice(builder,
                                                  match_end,
                                                  match_start);
      }
      match_end = register_vector[1];

      {
        // Avoid accumulating new handles inside loop.
        HandleScope temp_scope(isolate);
        // Arguments array to replace function is match, captures, index and
        // subject, i.e., 3 + capture count in total.
        Handle<FixedArray> elements =
            isolate->factory()->NewFixedArray(3 + capture_count);
        Handle<String> match;
        if (!first) {
          match = isolate->factory()->NewProperSubString(subject,
                                                         match_start,
                                                         match_end);
        } else {
          match = isolate->factory()->NewSubString(subject,
                                                   match_start,
                                                   match_end);
        }
        elements->set(0, *match);
        for (int i = 1; i <= capture_count; i++) {
          int start = register_vector[i * 2];
          if (start >= 0) {
            int end = register_vector[i * 2 + 1];
            ASSERT(start <= end);
            Handle<String> substring;
            if (!first) {
              substring = isolate->factory()->NewProperSubString(subject,
                                                                 start,
                                                                 end);
            } else {
              substring = isolate->factory()->NewSubString(subject, start, end);
            }
            elements->set(i, *substring);
          } else {
            ASSERT(register_vector[i * 2 + 1] < 0);
            elements->set(i, isolate->heap()->undefined_value());
          }
        }
        elements->set(capture_count + 1, Smi::FromInt(match_start));
        elements->set(capture_count + 2, *subject);
        builder->Add(*isolate->factory()->NewJSArrayWithElements(elements));
      }
      // Swap register vectors, so the last successful match is in
      // prev_register_vector.
      Vector<int32_t> tmp = prev_register_vector;
      prev_register_vector = register_vector;
      register_vector = tmp;

      if (match_end > match_start) {
        pos = match_end;
      } else {
        pos = match_end + 1;
        if (pos > subject_length) {
          break;
        }
      }

      result = RegExpImpl::IrregexpExecOnce(regexp,
                                            subject,
                                            pos,
                                            register_vector);
      first = false;
    } while (result == RegExpImpl::RE_SUCCESS);

    if (result != RegExpImpl::RE_EXCEPTION) {
      // Finished matching, with at least one match.
      if (match_end < subject_length) {
        ReplacementStringBuilder::AddSubjectSlice(builder,
                                                  match_end,
                                                  subject_length);
      }

      int last_match_capture_count = (capture_count + 1) * 2;
      int last_match_array_size =
          last_match_capture_count + RegExpImpl::kLastMatchOverhead;
      last_match_array->EnsureSize(last_match_array_size);
      AssertNoAllocation no_gc;
      FixedArray* elements = FixedArray::cast(last_match_array->elements());
      RegExpImpl::SetLastCaptureCount(elements, last_match_capture_count);
      RegExpImpl::SetLastSubject(elements, *subject);
      RegExpImpl::SetLastInput(elements, *subject);
      for (int i = 0; i < last_match_capture_count; i++) {
        RegExpImpl::SetCapture(elements, i, prev_register_vector[i]);
      }
      return RegExpImpl::RE_SUCCESS;
    }
  }
  // No matches at all, return failure or exception result directly.
  return result;
}


RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) {
  ASSERT(args.length() == 4);
  HandleScope handles(isolate);

  CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
  if (!subject->IsFlat()) FlattenString(subject);
  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
  CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 2);
  CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3);

  ASSERT(last_match_info->HasFastElements());
  ASSERT(regexp->GetFlags().is_global());
  Handle<FixedArray> result_elements;
  if (result_array->HasFastElements()) {
    result_elements =
        Handle<FixedArray>(FixedArray::cast(result_array->elements()));
  }
  if (result_elements.is_null() || result_elements->length() < 16) {
    result_elements = isolate->factory()->NewFixedArrayWithHoles(16);
  }
  FixedArrayBuilder builder(result_elements);

  if (regexp->TypeTag() == JSRegExp::ATOM) {
    Handle<