CSE2410 Fall 2014 Bounce

// Copyright 2006-2009 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 "compiler.h"

#include "cpu.h"

#include "dateparser.h"

#include "dateparser-inl.h"

#include "debug.h"

#include "execution.h"

#include "jsregexp.h"

#include "platform.h"

#include "runtime.h"

#include "scopeinfo.h"

#include "v8threads.h"

#include "smart-pointer.h"

#include "parser.h"

namespace v8 { namespace internal {

#define RUNTIME_ASSERT(value) do {                                   \

  if (!(value)) return IllegalOperation();                           \

} while (false)

// 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_CHECKED(Type, name, obj)                             \

  RUNTIME_ASSERT(obj->Is##Type());                                   \

  Type* name = Type::cast(obj);

#define CONVERT_ARG_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_CHECKED(name, obj)                            \

  RUNTIME_ASSERT(obj->IsBoolean());                                   \

  bool name = (obj)->IsTrue();

// Cast the given object to a Smi and store its value in an int variable

// with the given name.  If the object is not a Smi call IllegalOperation

// and return.

#define CONVERT_SMI_CHECKED(name, obj)                            \

  RUNTIME_ASSERT(obj->IsSmi());                                   \

  int name = Smi::cast(obj)->value();

// Cast the given object to a double and store it in a variable with

// the given name.  If the object is not a number (as opposed to

// the number not-a-number) call IllegalOperation and return.

#define CONVERT_DOUBLE_CHECKED(name, obj)                            \

  RUNTIME_ASSERT(obj->IsNumber());                                   \

  double name = (obj)->Number();

// 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);

// Non-reentrant string buffer for efficient general use in this file.

static StaticResource<StringInputBuffer> runtime_string_input_buffer;

static Object* IllegalOperation() {

  return Top::Throw(Heap::illegal_access_symbol());

}

static Object* DeepCopyBoilerplate(JSObject* boilerplate) {

  StackLimitCheck check;

  if (check.HasOverflowed()) return Top::StackOverflow();

  Object* result = Heap::CopyJSObject(boilerplate);

  if (result->IsFailure()) return result;

  JSObject* copy = JSObject::cast(result);

  // Deep copy local properties.

  if (copy->HasFastProperties()) {

    FixedArray* properties = copy->properties();

    WriteBarrierMode mode = properties->GetWriteBarrierMode();

    for (int i = 0; i < properties->length(); i++) {

      Object* value = properties->get(i);

      if (value->IsJSObject()) {

        JSObject* jsObject = JSObject::cast(value);

        result = DeepCopyBoilerplate(jsObject);

        if (result->IsFailure()) return result;

        properties->set(i, result, mode);

      }

    }

    mode = copy->GetWriteBarrierMode();

    for (int i = 0; i < copy->map()->inobject_properties(); i++) {

      Object* value = copy->InObjectPropertyAt(i);

      if (value->IsJSObject()) {

        JSObject* jsObject = JSObject::cast(value);

        result = DeepCopyBoilerplate(jsObject);

        if (result->IsFailure()) return result;

        copy->InObjectPropertyAtPut(i, result, mode);

      }

    }

  } else {

    result = Heap::AllocateFixedArray(copy->NumberOfLocalProperties(NONE));

    if (result->IsFailure()) return result;

    FixedArray* names = FixedArray::cast(result);

    copy->GetLocalPropertyNames(names, 0);

    for (int i = 0; i < names->length(); i++) {

      ASSERT(names->get(i)->IsString());

      String* keyString = String::cast(names->get(i));

      PropertyAttributes attributes =

        copy->GetLocalPropertyAttribute(keyString);

      // 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(keyString, &attributes);

      ASSERT(!value->IsFailure());

      if (value->IsJSObject()) {

        JSObject* jsObject = JSObject::cast(value);

        result = DeepCopyBoilerplate(jsObject);

        if (result->IsFailure()) return result;

        result = copy->SetProperty(keyString, result, NONE);

        if (result->IsFailure()) return result;

      }

    }

  }

  // Deep copy local elements.

  if (copy->HasFastElements()) {

    FixedArray* elements = copy->elements();

    WriteBarrierMode mode = elements->GetWriteBarrierMode();

    for (int i = 0; i < elements->length(); i++) {

      Object* value = elements->get(i);

      if (value->IsJSObject()) {

        JSObject* jsObject = JSObject::cast(value);

        result = DeepCopyBoilerplate(jsObject);

        if (result->IsFailure()) return result;

        elements->set(i, result, mode);

      }

    }

  } else {

    Dictionary* 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* jsObject = JSObject::cast(value);

          result = DeepCopyBoilerplate(jsObject);

          if (result->IsFailure()) return result;

          element_dictionary->ValueAtPut(i, result);

        }

      }

    }

  }

  return copy;

}

static Object* Runtime_CloneLiteralBoilerplate(Arguments args) {

  CONVERT_CHECKED(JSObject, boilerplate, args[0]);

  return DeepCopyBoilerplate(boilerplate);

}

static Object* Runtime_CloneShallowLiteralBoilerplate(Arguments args) {

  CONVERT_CHECKED(JSObject, boilerplate, args[0]);

  return Heap::CopyJSObject(boilerplate);

}

static Handle<Map> ComputeObjectLiteralMap(

    Handle<Context> context,

    Handle<FixedArray> constant_properties,

    bool* is_result_from_cache) {

  int number_of_properties = constant_properties->length() / 2;

  if (FLAG_canonicalize_object_literal_maps) {

    // First find prefix of consecutive symbol keys.

    int number_of_symbol_keys = 0;

    while ((number_of_symbol_keys < number_of_properties) &&

           (constant_properties->get(number_of_symbol_keys*2)->IsSymbol())) {

      number_of_symbol_keys++;

    }

    // Based on the number of prefix symbols key we decide whether

    // to 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 = Factory::NewFixedArray(number_of_symbol_keys);

      for (int i = 0; i < number_of_symbol_keys; i++) {

        keys->set(i, constant_properties->get(i*2));

      }

      *is_result_from_cache = true;

      return Factory::ObjectLiteralMapFromCache(context, keys);

    }

  }

  *is_result_from_cache = false;

  return Factory::CopyMap(

      Handle<Map>(context->object_function()->initial_map()),

      number_of_properties);

}

static Handle<Object> CreateLiteralBoilerplate(

    Handle<FixedArray> literals,

    Handle<FixedArray> constant_properties);

static Handle<Object> CreateObjectLiteralBoilerplate(

    Handle<FixedArray> literals,

    Handle<FixedArray> constant_properties) {

  // 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));

  bool is_result_from_cache;

  Handle<Map> map = ComputeObjectLiteralMap(context,

                                            constant_properties,

                                            &is_result_from_cache);

  Handle<JSObject> boilerplate = Factory::NewJSObjectFromMap(map);

  {  // Add the constant properties to the boilerplate.

    int length = constant_properties->length();

    OptimizedObjectForAddingMultipleProperties opt(boilerplate,

                                                   !is_result_from_cache);

    for (int index = 0; index < length; index +=2) {

      Handle<Object> key(constant_properties->get(index+0));

      Handle<Object> value(constant_properties->get(index+1));

      if (value->IsFixedArray()) {

        // The value contains the constant_properties of a

        // simple object literal.

        Handle<FixedArray> array = Handle<FixedArray>::cast(value);

        value = CreateLiteralBoilerplate(literals, array);

        if (value.is_null()) return value;

      }

      Handle<Object> result;

      uint32_t element_index = 0;

      if (key->IsSymbol()) {

        // If key is a symbol it is not an array element.

        Handle<String> name(String::cast(*key));

        ASSERT(!name->AsArrayIndex(&element_index));

        result = SetProperty(boilerplate, name, value, NONE);

      } else if (Array::IndexFromObject(*key, &element_index)) {

        // Array index (uint32).

        result = SetElement(boilerplate, element_index, value);

      } 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 = Factory::NewStringFromAscii(CStrVector(str));

        result = SetProperty(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;

    }

  }

  return boilerplate;

}

static Handle<Object> CreateArrayLiteralBoilerplate(

    Handle<FixedArray> literals,

    Handle<FixedArray> elements) {

  // Create the JSArray.

  Handle<JSFunction> constructor(

      JSFunction::GlobalContextFromLiterals(*literals)->array_function());

  Handle<Object> object = Factory::NewJSObject(constructor);

  Handle<Object> copied_elements = Factory::CopyFixedArray(elements);

  Handle<FixedArray> content = Handle<FixedArray>::cast(copied_elements);

  for (int i = 0; i < content->length(); i++) {

    if (content->get(i)->IsFixedArray()) {

      // The value contains the constant_properties of a

      // simple object literal.

      Handle<FixedArray> fa(FixedArray::cast(content->get(i)));

      Handle<Object> result =

        CreateLiteralBoilerplate(literals, fa);

      if (result.is_null()) return result;

      content->set(i, *result);

    }

  }

  // Set the elements.

  Handle<JSArray>::cast(object)->SetContent(*content);

  return object;

}

static Handle<Object> CreateLiteralBoilerplate(

    Handle<FixedArray> literals,

    Handle<FixedArray> array) {

  Handle<FixedArray> elements = CompileTimeValue::GetElements(array);

  switch (CompileTimeValue::GetType(array)) {

    case CompileTimeValue::OBJECT_LITERAL:

      return CreateObjectLiteralBoilerplate(literals, elements);

    case CompileTimeValue::ARRAY_LITERAL:

      return CreateArrayLiteralBoilerplate(literals, elements);

    default:

      UNREACHABLE();

      return Handle<Object>::null();

  }

}

static Object* Runtime_CreateObjectLiteralBoilerplate(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 3);

  // Copy the arguments.

  CONVERT_ARG_CHECKED(FixedArray, literals, 0);

  CONVERT_SMI_CHECKED(literals_index, args[1]);

  CONVERT_ARG_CHECKED(FixedArray, constant_properties, 2);

  Handle<Object> result =

    CreateObjectLiteralBoilerplate(literals, constant_properties);

  if (result.is_null()) return Failure::Exception();

  // Update the functions literal and return the boilerplate.

  literals->set(literals_index, *result);

  return *result;

}

static Object* Runtime_CreateArrayLiteralBoilerplate(Arguments args) {

  // Takes a FixedArray of elements containing the literal elements of

  // the array literal and produces JSArray with those elements.

  // Additionally takes the literals array of the surrounding function

  // which contains the context from which to get the Array function

  // to use for creating the array literal.

  HandleScope scope;

  ASSERT(args.length() == 3);

  CONVERT_ARG_CHECKED(FixedArray, literals, 0);

  CONVERT_SMI_CHECKED(literals_index, args[1]);

  CONVERT_ARG_CHECKED(FixedArray, elements, 2);

  Handle<Object> object = CreateArrayLiteralBoilerplate(literals, elements);

  if (object.is_null()) return Failure::Exception();

  // Update the functions literal and return the boilerplate.

  literals->set(literals_index, *object);

  return *object;

}

static Object* Runtime_CreateCatchExtensionObject(Arguments args) {

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(String, key, args[0]);

  Object* value = args[1];

  // Create a catch context extension object.

  JSFunction* constructor =

      Top::context()->global_context()->context_extension_function();

  Object* object = Heap::AllocateJSObject(constructor);

  if (object->IsFailure()) return object;

  // Assign the exception value to the catch variable and make sure

  // that the catch variable is DontDelete.

  value = JSObject::cast(object)->SetProperty(key, value, DONT_DELETE);

  if (value->IsFailure()) return value;

  return object;

}

static Object* Runtime_ClassOf(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 1);

  Object* obj = args[0];

  if (!obj->IsJSObject()) return Heap::null_value();

  return JSObject::cast(obj)->class_name();

}

static Object* Runtime_HasStringClass(Arguments args) {

  return Heap::ToBoolean(args[0]->HasSpecificClassOf(Heap::String_symbol()));

}

static Object* Runtime_HasDateClass(Arguments args) {

  return Heap::ToBoolean(args[0]->HasSpecificClassOf(Heap::Date_symbol()));

}

static Object* Runtime_HasArrayClass(Arguments args) {

  return Heap::ToBoolean(args[0]->HasSpecificClassOf(Heap::Array_symbol()));

}

static Object* Runtime_HasFunctionClass(Arguments args) {

  return Heap::ToBoolean(

             args[0]->HasSpecificClassOf(Heap::function_class_symbol()));

}

static Object* Runtime_HasNumberClass(Arguments args) {

  return Heap::ToBoolean(args[0]->HasSpecificClassOf(Heap::Number_symbol()));

}

static Object* Runtime_HasBooleanClass(Arguments args) {

  return Heap::ToBoolean(args[0]->HasSpecificClassOf(Heap::Boolean_symbol()));

}

static Object* Runtime_HasArgumentsClass(Arguments args) {

  return Heap::ToBoolean(

             args[0]->HasSpecificClassOf(Heap::Arguments_symbol()));

}

static Object* Runtime_HasRegExpClass(Arguments args) {

  return Heap::ToBoolean(args[0]->HasSpecificClassOf(Heap::RegExp_symbol()));

}

static Object* Runtime_IsInPrototypeChain(Arguments args) {

  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 Heap::false_value();

    if (O == prototype) return Heap::true_value();

    V = prototype;

  }

}

static Object* Runtime_IsConstructCall(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 0);

  JavaScriptFrameIterator it;

  return Heap::ToBoolean(it.frame()->IsConstructor());

}

static Object* Runtime_RegExpCompile(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 3);

  CONVERT_CHECKED(JSRegExp, raw_re, args[0]);

  Handle<JSRegExp> re(raw_re);

  CONVERT_CHECKED(String, raw_pattern, args[1]);

  Handle<String> pattern(raw_pattern);

  CONVERT_CHECKED(String, raw_flags, args[2]);

  Handle<String> flags(raw_flags);

  Handle<Object> result = RegExpImpl::Compile(re, pattern, flags);

  if (result.is_null()) return Failure::Exception();

  return *result;

}

static Object* Runtime_CreateApiFunction(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(FunctionTemplateInfo, raw_data, args[0]);

  Handle<FunctionTemplateInfo> data(raw_data);

  return *Factory::CreateApiFunction(data);

}

static Object* Runtime_IsTemplate(Arguments args) {

  ASSERT(args.length() == 1);

  Object* arg = args[0];

  bool result = arg->IsObjectTemplateInfo() || arg->IsFunctionTemplateInfo();

  return Heap::ToBoolean(result);

}

static Object* Runtime_GetTemplateField(Arguments args) {

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(HeapObject, templ, args[0]);

  CONVERT_CHECKED(Smi, field, args[1]);

  int index = field->value();

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

}

static Object* Runtime_DisableAccessChecks(Arguments args) {

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(HeapObject, object, args[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 = old_map->CopyDropTransitions();

    if (new_map->IsFailure()) return new_map;

    Map::cast(new_map)->set_is_access_check_needed(false);

    object->set_map(Map::cast(new_map));

  }

  return needs_access_checks ? Heap::true_value() : Heap::false_value();

}

static Object* Runtime_EnableAccessChecks(Arguments args) {

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(HeapObject, object, args[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 = old_map->CopyDropTransitions();

    if (new_map->IsFailure()) return new_map;

    Map::cast(new_map)->set_is_access_check_needed(true);

    object->set_map(Map::cast(new_map));

  }

  return Heap::undefined_value();

}

static Object* ThrowRedeclarationError(const char* type, Handle<String> name) {

  HandleScope scope;

  Handle<Object> type_handle = Factory::NewStringFromAscii(CStrVector(type));

  Handle<Object> args[2] = { type_handle, name };

  Handle<Object> error =

      Factory::NewTypeError("redeclaration", HandleVector(args, 2));

  return Top::Throw(*error);

}

static Object* Runtime_DeclareGlobals(Arguments args) {

  HandleScope scope;

  Handle<GlobalObject> global = Handle<GlobalObject>(Top::context()->global());

  CONVERT_ARG_CHECKED(FixedArray, pairs, 0);

  Handle<Context> context = args.at<Context>(1);

  bool is_eval = Smi::cast(args[2])->value() == 1;

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

  PropertyAttributes base = is_eval ? NONE : DONT_DELETE;

  // Only optimize the object if we intend to add more than 5 properties.

  OptimizedObjectForAddingMultipleProperties ba(global, pairs->length()/2 > 5);

  // Traverse the name/value pairs and set the properties.

  int length = pairs->length();

  for (int i = 0; i < length; i += 2) {

    HandleScope scope;

    Handle<String> name(String::cast(pairs->get(i)));

    Handle<Object> value(pairs->get(i + 1));

    // 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();

    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;

      global->Lookup(*name, &lookup);

      if (lookup.IsProperty()) {

        // Determine if the property is local by comparing the holder

        // against the global object. The information will be used to

        // avoid throwing re-declaration errors when declaring

        // variables or constants that exist in the prototype chain.

        bool is_local = (*global == lookup.holder());

        // Get the property attributes and determine if the property is

        // read-only.

        PropertyAttributes attributes = global->GetPropertyAttribute(*name);

        bool is_read_only = (attributes & READ_ONLY) != 0;

        if (lookup.type() == INTERCEPTOR) {

          // If the interceptor says the property is there, we

          // just return undefined without overwriting the property.

          // Otherwise, we continue to setting the property.

          if (attributes != ABSENT) {

            // Check if the existing property conflicts with regards to const.

            if (is_local && (is_read_only || is_const_property)) {

              const char* type = (is_read_only) ? "const" : "var";

              return ThrowRedeclarationError(type, name);

            };

            // The property already exists without conflicting: Go to

            // the next declaration.

            continue;

          }

          // Fall-through and introduce the absent property by using

          // SetProperty.

        } else {

          if (is_local && (is_read_only || is_const_property)) {

            const char* type = (is_read_only) ? "const" : "var";

            return ThrowRedeclarationError(type, name);

          }

          // The property already exists without conflicting: Go to

          // the next declaration.

          continue;

        }

      }

    } else {

      // Copy the function and update its context. Use it as value.

      Handle<JSFunction> boilerplate = Handle<JSFunction>::cast(value);

      Handle<JSFunction> function =

          Factory::NewFunctionFromBoilerplate(boilerplate, context);

      value = function;

    }

    LookupResult lookup;

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

    PropertyAttributes attributes = is_const_property

        ? static_cast<PropertyAttributes>(base | READ_ONLY)

        : base;

    if (lookup.IsProperty()) {

      // There's a local property that we need to overwrite because

      // we're either declaring a function or there's an interceptor

      // that claims the property is absent.

      // Check for conflicting re-declarations. We cannot have

      // conflicting types in case of intercepted properties because

      // they are absent.

      if (lookup.type() != INTERCEPTOR &&

          (lookup.IsReadOnly() || is_const_property)) {

        const char* type = (lookup.IsReadOnly()) ? "const" : "var";

        return ThrowRedeclarationError(type, name);

      }

      SetProperty(global, name, value, attributes);

    } else {

      // If a property with this name does not already exist on the

      // global object add the property locally.  We 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).  Also, we must use the handle-based version to

      // avoid GC issues.

      IgnoreAttributesAndSetLocalProperty(global, name, value, attributes);

    }

  }

  return Heap::undefined_value();

}

static Object* Runtime_DeclareContextSlot(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 4);

  CONVERT_ARG_CHECKED(Context, context, 0);

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

  PropertyAttributes mode =

      static_cast<PropertyAttributes>(Smi::cast(args[2])->value());

  ASSERT(mode == READ_ONLY || mode == NONE);

  Handle<Object> initial_value(args[3]);

  // Declarations are always done in the function context.

  context = Handle<Context>(context->fcontext());

  int index;

  PropertyAttributes attributes;

  ContextLookupFlags flags = DONT_FOLLOW_CHAINS;

  Handle<Object> holder =

      context->Lookup(name, flags, &index, &attributes);

  if (attributes != ABSENT) {

    // The name was declared before; check for conflicting

    // re-declarations: This is similar to the code in parser.cc in

    // the AstBuildingParser::Declare function.

    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(type, name);

    }

    // Initialize it if necessary.

    if (*initial_value != NULL) {

      if (index >= 0) {

        // The variable or constant context slot should always be in

        // the function context; not in any outer context nor in the

        // arguments object.

        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 not in the FixedArray part of the context.

        Handle<JSObject> context_ext = Handle<JSObject>::cast(holder);

        SetProperty(context_ext, name, initial_value, mode);

      }

    }

  } else {

    // The property is not in the function context. It needs to be

    // "declared" in the function context's extension context, or in the

    // global context.

    Handle<JSObject> context_ext;

    if (context->has_extension()) {

      // The function context's extension context exists - use it.

      context_ext = Handle<JSObject>(context->extension());

    } else {

      // The function context's extension context does not exists - allocate

      // it.

      context_ext = Factory::NewJSObject(Top::context_extension_function());

      // And store it in the extension slot.

      context->set_extension(*context_ext);

    }

    ASSERT(*context_ext != 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(!context_ext->HasLocalProperty(*name));

    Handle<Object> value(Heap::undefined_value());

    if (*initial_value != NULL) value = initial_value;

    SetProperty(context_ext, name, value, mode);

    ASSERT(context_ext->GetLocalPropertyAttribute(*name) == mode);

  }

  return Heap::undefined_value();

}

static Object* Runtime_InitializeVarGlobal(Arguments args) {

  NoHandleAllocation nha;

  // Determine if we need to assign to the variable if it already

  // exists (based on the number of arguments).

  RUNTIME_ASSERT(args.length() == 1 || args.length() == 2);

  bool assign = args.length() == 2;

  CONVERT_ARG_CHECKED(String, name, 0);

  GlobalObject* global = Top::context()->global();

  // 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, 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 have IgnoreAttributesAndSetLocalProperty for this.

  LookupResult lookup;

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

  if (!lookup.IsProperty()) {

    Object* value = (assign) ? args[1] : Heap::undefined_value();

    return global->IgnoreAttributesAndSetLocalProperty(*name,

                                                       value,

                                                       attributes);

  }

  // Determine if this is a redeclaration of something read-only.

  if (lookup.IsReadOnly()) {

    return ThrowRedeclarationError("const", name);

  }

  // Determine if this is a redeclaration of an intercepted read-only

  // property and figure out if the property exists at all.

  bool found = true;

  PropertyType type = lookup.type();

  if (type == INTERCEPTOR) {

    PropertyAttributes intercepted = global->GetPropertyAttribute(*name);

    if (intercepted == ABSENT) {

      // The interceptor claims the property isn't there. We need to

      // make sure to introduce it.

      found = false;

    } else if ((intercepted & READ_ONLY) != 0) {

      // The property is present, but read-only. Since we're trying to

      // overwrite it with a variable declaration we must throw a

      // re-declaration error.

      return ThrowRedeclarationError("const", name);

    }

    // Restore global object from context (in case of GC).

    global = Top::context()->global();

  }

  if (found && !assign) {

    // The global property is there and we're not assigning any value

    // to it. Just return.

    return Heap::undefined_value();

  }

  // Assign the value (or undefined) to the property.

  Object* value = (assign) ? args[1] : Heap::undefined_value();

  return global->SetProperty(&lookup, *name, value, attributes);

}

static Object* Runtime_InitializeConstGlobal(Arguments args) {

  // 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_CHECKED(String, name, 0);

  Handle<Object> value = args.at<Object>(1);

  // Get the current global object from top.

  GlobalObject* global = Top::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 IgnoreAttributesAndSetLocalProperty instead

  LookupResult lookup;

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

  if (!lookup.IsProperty()) {

    return global->IgnoreAttributesAndSetLocalProperty(*name,

                                                       *value,

                                                       attributes);

  }

  // Determine if this is a redeclaration of something not

  // read-only. In case the result is hidden behind an interceptor we

  // need to ask it for the property attributes.

  if (!lookup.IsReadOnly()) {

    if (lookup.type() != INTERCEPTOR) {

      return ThrowRedeclarationError("var", name);

    }

    PropertyAttributes intercepted = global->GetPropertyAttribute(*name);

    // Throw re-declaration error if the intercepted property is present

    // but not read-only.

    if (intercepted != ABSENT && (intercepted & READ_ONLY) == 0) {

      return ThrowRedeclarationError("var", name);

    }

    // Restore global object from context (in case of GC) and continue

    // with setting the value because the property is either absent or

    // read-only. We also have to do redo the lookup.

    global = Top::context()->global();

    // BUG 1213579: 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...

    global->SetProperty(*name, *value, attributes);

    return *value;

  }

  // Set the value, but only we're assigning the initial value to a

  // constant. For now, we determine this by checking if the

  // current value is the hole.

  PropertyType type = lookup.type();

  if (type == FIELD) {

    FixedArray* properties = global->properties();

    int index = lookup.GetFieldIndex();

    if (properties->get(index)->IsTheHole()) {

      properties->set(index, *value);

    }

  } else if (type == NORMAL) {

    Dictionary* dictionary = global->property_dictionary();

    int entry = lookup.GetDictionaryEntry();

    if (dictionary->ValueAt(entry)->IsTheHole()) {

      dictionary->ValueAtPut(entry, *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;

}

static Object* Runtime_InitializeConstContextSlot(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 3);

  Handle<Object> value(args[0]);

  ASSERT(!value->IsTheHole());

  CONVERT_ARG_CHECKED(Context, context, 1);

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

  // Initializations are always done in the function context.

  context = Handle<Context>(context->fcontext());

  int index;

  PropertyAttributes attributes;

  ContextLookupFlags flags = FOLLOW_CHAINS;

  Handle<Object> holder =

      context->Lookup(name, flags, &index, &attributes);

  // In most situations, the property introduced by the const

  // declaration should be present in the context extension object.

  // However, because declaration and initialization are separate, the

  // property might have been deleted (if it was introduced by eval)

  // before we reach the initialization point.

  //

  // Example:

  //

  //    function f() { eval("delete x; const x;"); }

  //

  // In that case, the initialization behaves like a normal assignment

  // to property 'x'.

  if (index >= 0) {

    // Property was found in a context.

    if (holder->IsContext()) {

      // The holder cannot be the function context.  If it is, there

      // should have been a const redeclaration error when declaring

      // the const property.

      ASSERT(!holder.is_identical_to(context));

      if ((attributes & READ_ONLY) == 0) {

        Handle<Context>::cast(holder)->set(index, *value);

      }

    } else {

      // The holder is an arguments object.

      ASSERT((attributes & READ_ONLY) == 0);

      Handle<JSObject>::cast(holder)->SetElement(index, *value);

    }

    return *value;

  }

  // The property could not be found, we introduce it in the global

  // context.

  if (attributes == ABSENT) {

    Handle<JSObject> global = Handle<JSObject>(Top::context()->global());

    SetProperty(global, name, value, NONE);

    return *value;

  }

  // The property was present in a context extension object.

  Handle<JSObject> context_ext = Handle<JSObject>::cast(holder);

  if (*context_ext == 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;

    context_ext->LocalLookupRealNamedProperty(*name, &lookup);

    ASSERT(lookup.IsProperty());  // the property was declared

    ASSERT(lookup.IsReadOnly());  // and it was declared as read-only

    PropertyType type = lookup.type();

    if (type == FIELD) {

      FixedArray* properties = context_ext->properties();

      int index = lookup.GetFieldIndex();

      if (properties->get(index)->IsTheHole()) {

        properties->set(index, *value);

      }

    } else if (type == NORMAL) {

      Dictionary* dictionary = context_ext->property_dictionary();

      int entry = lookup.GetDictionaryEntry();

      if (dictionary->ValueAt(entry)->IsTheHole()) {

        dictionary->ValueAtPut(entry, *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 in a different context extension object.

    // Set it if it is not a read-only property.

    if ((attributes & READ_ONLY) == 0) {

      Handle<Object> set = SetProperty(context_ext, name, value, attributes);

      // Setting a property might throw an exception.  Exceptions

      // are converted to empty handles in handle operations.  We

      // need to convert back to exceptions here.

      if (set.is_null()) {

        ASSERT(Top::has_pending_exception());

        return Failure::Exception();

      }

    }

  }

  return *value;

}

static Object* Runtime_RegExpExec(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 4);

  CONVERT_CHECKED(JSRegExp, raw_regexp, args[0]);

  Handle<JSRegExp> regexp(raw_regexp);

  CONVERT_CHECKED(String, raw_subject, args[1]);

  Handle<String> subject(raw_subject);

  // Due to the way the JS files 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_CHECKED(Smi, index, args[2]);

  CONVERT_CHECKED(JSArray, raw_last_match_info, args[3]);

  Handle<JSArray> last_match_info(raw_last_match_info);

  RUNTIME_ASSERT(last_match_info->HasFastElements());

  RUNTIME_ASSERT(index->value() >= 0);

  RUNTIME_ASSERT(index->value() <= subject->length());

  Handle<Object> result = RegExpImpl::Exec(regexp,

                                           subject,

                                           index->value(),

                                           last_match_info);

  if (result.is_null()) return Failure::Exception();

  return *result;

}

static Object* Runtime_MaterializeRegExpLiteral(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 4);

  CONVERT_ARG_CHECKED(FixedArray, literals, 0);

  int index = Smi::cast(args[1])->value();

  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(Top::has_pending_exception());

    return Failure::Exception();

  }

  literals->set(index, *regexp);

  return *regexp;

}

static Object* Runtime_FunctionGetName(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(JSFunction, f, args[0]);

  return f->shared()->name();

}

static Object* Runtime_FunctionSetName(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(JSFunction, f, args[0]);

  CONVERT_CHECKED(String, name, args[1]);

  f->shared()->set_name(name);

  return Heap::undefined_value();

}

static Object* Runtime_FunctionGetScript(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(JSFunction, fun, args[0]);

  Handle<Object> script = Handle<Object>(fun->shared()->script());

  if (!script->IsScript()) return Heap::undefined_value();

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

}

static Object* Runtime_FunctionGetSourceCode(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(JSFunction, f, args[0]);

  return f->shared()->GetSourceCode();

}

static Object* Runtime_FunctionGetScriptSourcePosition(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(JSFunction, fun, args[0]);

  int pos = fun->shared()->start_position();

  return Smi::FromInt(pos);

}

static Object* Runtime_FunctionSetInstanceClassName(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(JSFunction, fun, args[0]);

  CONVERT_CHECKED(String, name, args[1]);

  fun->SetInstanceClassName(name);

  return Heap::undefined_value();

}

static Object* Runtime_FunctionSetLength(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(JSFunction, fun, args[0]);

  CONVERT_CHECKED(Smi, length, args[1]);

  fun->shared()->set_length(length->value());

  return length;

}

static Object* Runtime_FunctionSetPrototype(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(JSFunction, fun, args[0]);

  Object* obj = Accessors::FunctionSetPrototype(fun, args[1], NULL);

  if (obj->IsFailure()) return obj;

  return args[0];  // return TOS

}

static Object* Runtime_FunctionIsAPIFunction(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 1);

  CONVERT_CHECKED(JSFunction, f, args[0]);

  // The function_data field of the shared function info is used exclusively by

  // the API.

  return !f->shared()->function_data()->IsUndefined() ? Heap::true_value()

                                                      : Heap::false_value();

}

static Object* Runtime_SetCode(Arguments args) {

  HandleScope scope;

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(JSFunction, raw_target, args[0]);

  Handle<JSFunction> target(raw_target);

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

    SetExpectedNofProperties(target, fun->shared()->expected_nof_properties());

    if (!fun->is_compiled() && !CompileLazy(fun, KEEP_EXCEPTION)) {

      return Failure::Exception();

    }

    // Set the code, formal parameter count, and the length of the target

    // function.

    target->set_code(fun->code());

    target->shared()->set_length(fun->shared()->length());

    target->shared()->set_formal_parameter_count(

        fun->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(Heap::undefined_value());

    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 =

        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, SKIP_WRITE_BARRIER);

  }

  target->set_context(*context);

  return *target;

}

static Object* CharCodeAt(String* subject, Object* index) {

  uint32_t i = 0;

  if (!Array::IndexFromObject(index, &i)) return Heap::nan_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.

  subject->TryFlattenIfNotFlat();

  if (i >= static_cast<uint32_t>(subject->length())) {

    return Heap::nan_value();

  }

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

}

static Object* Runtime_StringCharCodeAt(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 2);

  CONVERT_CHECKED(String, subject, args[0]);

  Object* index = args[1];

  return CharCodeAt(subject, index);

}

static Object* Runtime_CharFromCode(Arguments args) {

  NoHandleAllocation ha;

  ASSERT(args.length() == 1);

  uint32_t code;

  if (Array::IndexFromObject(args[0], &code)) {

    if (code <= 0xffff) {

      return Heap::LookupSingleCharacterStringFromCode(code);

    }

  }

  return Heap::empty_string();

}

// Forward declarations.

static const int kStringBuilderConcatHelperLengthBits = 11;

static const int kStringBuilderConcatHelperPositionBits = 19;

template <typename schar>

static inline void StringBuilderConcatHelper(String*,

                                             schar*,

                                             FixedArray*,

                                             int);

typedef BitField<int, 0, 11> StringBuilderSubstringLength;

typedef BitField<int, 11, 19> StringBuilderSubstringPosition;

class ReplacementStringBuilder {

 public:

  ReplacementStringBuilder(Handle<String> subject, int estimated_part_count)

      : subject_(subject),

        parts_(Factory::NewFixedArray(estimated_part_count)),

        part_count_(0),

        character_count_(0),

        is_ascii_(StringShape(*subject).IsAsciiRepresentation()) {

    // Require a non-zero initial size. Ensures that doubling the size to

    // extend the array will work.

    ASSERT(estimated_part_count > 0);

  }

  void EnsureCapacity(int elements) {

    int length = parts_->length();

    int required_length = part_count_ + elements;

    if (length < required_length) {

      int new_length = length;

      do {

        new_length *= 2;

      } while (new_length < required_length);

      Handle<FixedArray> extended_array =

          Factory::NewFixedArray(new_length);

      parts_->CopyTo(0, *extended_array, 0, part_count_);

      parts_ = extended_array;

    }

  }

  void AddSubjectSlice(int from, int to) {

    ASSERT(from >= 0);

    int length = to - from;

    ASSERT(length > 0);

    // Can we encode the slice in 11 bits for length and 19 bits for

    // start position - as used by StringBuilderConcatHelper?

    if (StringBuilderSubstringLength::is_valid(length) &&

        StringBuilderSubstringPosition::is_valid(from)) {

      int encoded_slice = StringBuilderSubstringLength::encode(length) |

          StringBuilderSubstringPosition::encode(from);

      AddElement(Smi::FromInt(encoded_slice));

    } else {

      Handle<String> slice = Factory::NewStringSlice(subject_, from, to);

      AddElement(*slice);

    }

    IncrementCharacterCount(length);

  }

  void AddString(Handle<String> string) {

    int length = string->length();

    ASSERT(length > 0);

    AddElement(*string);

    if (!StringShape(*string).IsAsciiRepresentation()) {

      is_ascii_ = false;

    }

    IncrementCharacterCount(length);

  }

  Handle<String> ToString() {

    if (part_count_ == 0) {

      return Factory::empty_string();

    }

    Handle<String> joined_string;

    if (is_ascii_) {

      joined_string = NewRawAsciiString(character_count_);

      AssertNoAllocation no_alloc;

      SeqAsciiString* seq = SeqAsciiString::cast(*joined_string);

      char* char_buffer = seq->GetChars();

      StringBuilderConcatHelper(*subject_,

                                char_buffer,

                                *parts_,

                                part_count_);

    } else {

      // Non-ASCII.

      joined_string = NewRawTwoByteString(character_count_);

      AssertNoAllocation no_alloc;

      SeqTwoByteString* seq = SeqTwoByteString::cast(*joined_string);

      uc16* char_buffer = seq->GetChars();

      StringBuilderConcatHelper(*subject_,

                                char_buffer,

                                *parts_,

                                part_count_);

    }

    return joined_string;

  }

  void IncrementCharacterCount(int by) {

    if (character_count_ > Smi::kMaxValue - by) {

      V8::FatalProcessOutOfMemory("String.replace result too large.");

    }

    character_count_ += by;

  }

 private:

  Handle<String> NewRawAsciiString(int size) {

    CALL_HEAP_FUNCTION(Heap::AllocateRawAsciiString(size), String);

  }

  Handle<String> NewRawTwoByteString(int size) {

    CALL_HEAP_FUNCTION(Heap::AllocateRawTwoByteString(size), String);

  }

  void AddElement(Object* element) {

    ASSERT(element->IsSmi() || element->IsString());

    parts_->set(part_count_, element);

    part_count_++;

  }

  Handle<String> subject_;

  Handle<FixedArray> parts_;

  int part_count_;

  int character_count_;

  bool is_ascii_;

};