Merged bleeding_edge r599:645 into regexp2000.

src/runtime.cc

Index: src/runtime.cc
===================================================================
--- src/runtime.cc	(revision 645)
+++ src/runtime.cc	(working copy)
@@ -320,9 +320,19 @@
 static Object* Runtime_GetTemplateField(Arguments args) {
   ASSERT(args.length() == 2);
   CONVERT_CHECKED(HeapObject, templ, args[0]);
-  RUNTIME_ASSERT(templ->IsStruct());
   CONVERT_CHECKED(Smi, field, args[1]);
-  return HeapObject::GetHeapObjectField(templ, field->value());
+  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);
 }
 
 
@@ -3987,6 +3997,253 @@
 }
 
 
+/**
+ * A simple visitor visits every element of Array's.
+ * The backend storage can be a fixed array for fast elements case,
+ * or a dictionary for sparse array. Since Dictionary is a subtype
+ * of FixedArray, the class can be used by both fast and slow cases.
+ * The second parameter of the constructor, fast_elements, specifies
+ * whether the storage is a FixedArray or Dictionary.
+ *
+ * An index limit is used to deal with the situation that a result array
+ * length overflows 32-bit non-negative integer.
+ */
+class ArrayConcatVisitor {
+ public:
+  ArrayConcatVisitor(Handle<FixedArray> storage,
+                     uint32_t index_limit,
+                     bool fast_elements) :
+      storage_(storage), index_limit_(index_limit),
+      fast_elements_(fast_elements), index_offset_(0) { }
+
+  void visit(uint32_t i, Handle<Object> elm) {
+    uint32_t index = i + index_offset_;
+    if (index >= index_limit_) return;
+
+    if (fast_elements_) {
+      ASSERT(index < static_cast<uint32_t>(storage_->length()));
+      storage_->set(index, *elm);
+
+    } else {
+      Handle<Dictionary> dict = Handle<Dictionary>::cast(storage_);
+      Handle<Dictionary> result =
+          Factory::DictionaryAtNumberPut(dict, index, elm);
+      if (!result.is_identical_to(dict))
+        storage_ = result;
+    }
+  }
+
+  void increase_index_offset(uint32_t delta) {
+    index_offset_ += delta;
+  }
+
+ private:
+  Handle<FixedArray> storage_;
+  uint32_t index_limit_;
+  bool fast_elements_;
+  uint32_t index_offset_;
+};
+
+
+/**
+ * A helper function that visits elements of a JSObject. Only elements
+ * whose index between 0 and range (exclusive) are visited.
+ *
+ * If the third parameter, visitor, is not NULL, the visitor is called
+ * with parameters, 'visitor_index_offset + element index' and the element.
+ *
+ * It returns the number of visisted elements.
+ */
+static uint32_t IterateElements(Handle<JSObject> receiver,
+                                uint32_t range,
+                                ArrayConcatVisitor* visitor) {
+  uint32_t num_of_elements = 0;
+
+  if (receiver->HasFastElements()) {
+    Handle<FixedArray> elements(FixedArray::cast(receiver->elements()));
+    uint32_t len = elements->length();
+    if (range < len) len = range;
+
+    for (uint32_t j = 0; j < len; j++) {
+      Handle<Object> e(elements->get(j));
+      if (!e->IsTheHole()) {
+        num_of_elements++;
+        if (visitor)
+          visitor->visit(j, e);
+      }
+    }
+
+  } else {
+    Handle<Dictionary> dict(receiver->element_dictionary());
+    uint32_t capacity = dict->Capacity();
+    for (uint32_t j = 0; j < capacity; j++) {
+      Handle<Object> k(dict->KeyAt(j));
+      if (dict->IsKey(*k)) {
+        ASSERT(k->IsNumber());
+        uint32_t index = static_cast<uint32_t>(k->Number());
+        if (index < range) {
+          num_of_elements++;
+          if (visitor) {
+            visitor->visit(index,
+                           Handle<Object>(dict->ValueAt(j)));
+          }
+        }
+      }
+    }
+  }
+
+  return num_of_elements;
+}
+
+
+/**
+ * A helper function that visits elements of an Array object, and elements
+ * on its prototypes.
+ *
+ * Elements on prototypes are visited first, and only elements whose indices
+ * less than Array length are visited.
+ *
+ * If a ArrayConcatVisitor object is given, the visitor is called with
+ * parameters, element's index + visitor_index_offset and the element.
+ */
+static uint32_t IterateArrayAndPrototypeElements(Handle<JSArray> array,
+                                                 ArrayConcatVisitor* visitor) {
+  uint32_t range = static_cast<uint32_t>(array->length()->Number());
+  Handle<Object> obj = array;
+
+  static const int kEstimatedPrototypes = 3;
+  List< Handle<JSObject> > objects(kEstimatedPrototypes);
+
+  // Visit prototype first. If an element on the prototype is shadowed by
+  // the inheritor using the same index, the ArrayConcatVisitor visits
+  // the prototype element before the shadowing element.
+  // The visitor can simply overwrite the old value by new value using
+  // the same index.  This follows Array::concat semantics.
+  while (!obj->IsNull()) {
+    objects.Add(Handle<JSObject>::cast(obj));
+    obj = Handle<Object>(obj->GetPrototype());
+  }
+
+  uint32_t nof_elements = 0;
+  for (int i = objects.length() - 1; i >= 0; i--) {
+    Handle<JSObject> obj = objects[i];
+    nof_elements +=
+        IterateElements(Handle<JSObject>::cast(obj), range, visitor);
+  }
+
+  return nof_elements;
+}
+
+
+/**
+ * A helper function of Runtime_ArrayConcat.
+ *
+ * The first argument is an Array of arrays and objects. It is the
+ * same as the arguments array of Array::concat JS function.
+ *
+ * If an argument is an Array object, the function visits array
+ * elements.  If an argument is not an Array object, the function
+ * visits the object as if it is an one-element array.
+ *
+ * If the result array index overflows 32-bit integer, the rounded
+ * non-negative number is used as new length. For example, if one
+ * array length is 2^32 - 1, second array length is 1, the
+ * concatenated array length is 0.
+ */
+static uint32_t IterateArguments(Handle<JSArray> arguments,
+                                 ArrayConcatVisitor* visitor) {
+  uint32_t visited_elements = 0;
+  uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number());
+
+  for (uint32_t i = 0; i < num_of_args; i++) {
+    Handle<Object> obj(arguments->GetElement(i));
+    if (obj->IsJSArray()) {
+      Handle<JSArray> array = Handle<JSArray>::cast(obj);
+      uint32_t len = static_cast<uint32_t>(array->length()->Number());
+      uint32_t nof_elements =
+          IterateArrayAndPrototypeElements(array, visitor);
+      // Total elements of array and its prototype chain can be more than
+      // the array length, but ArrayConcat can only concatenate at most
+      // the array length number of elements.
+      visited_elements += (nof_elements > len) ? len : nof_elements;
+      if (visitor) visitor->increase_index_offset(len);
+
+    } else {
+      if (visitor) {
+        visitor->visit(0, obj);
+        visitor->increase_index_offset(1);
+      }
+      visited_elements++;
+    }
+  }
+  return visited_elements;
+}
+
+
+/**
+ * Array::concat implementation.
+ * See ECMAScript 262, 15.4.4.4.
+ */
+static Object* Runtime_ArrayConcat(Arguments args) {
+  ASSERT(args.length() == 1);
+  HandleScope handle_scope;
+
+  CONVERT_CHECKED(JSArray, arg_arrays, args[0]);
+  Handle<JSArray> arguments(arg_arrays);
+
+  // Pass 1: estimate the number of elements of the result
+  // (it could be more than real numbers if prototype has elements).
+  uint32_t result_length = 0;
+  uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number());
+
+  { AssertNoAllocation nogc;
+    for (uint32_t i = 0; i < num_of_args; i++) {
+      Object* obj = arguments->GetElement(i);
+      if (obj->IsJSArray()) {
+        result_length +=
+            static_cast<uint32_t>(JSArray::cast(obj)->length()->Number());
+      } else {
+        result_length++;
+      }
+    }
+  }
+
+  // Allocate an empty array, will set length and content later.
+  Handle<JSArray> result = Factory::NewJSArray(0);
+
+  uint32_t estimate_nof_elements = IterateArguments(arguments, NULL);
+  // If estimated number of elements is more than half of length, a
+  // fixed array (fast case) is more time and space-efficient than a
+  // dictionary.
+  bool fast_case = (estimate_nof_elements * 2) >= result_length;
+
+  Handle<FixedArray> storage;
+  if (fast_case) {
+    // The backing storage array must have non-existing elements to
+    // preserve holes across concat operations.
+    storage = Factory::NewFixedArrayWithHoles(result_length);
+
+  } else {
+    // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate
+    uint32_t at_least_space_for = estimate_nof_elements +
+                                  (estimate_nof_elements >> 2);
+    storage = Handle<FixedArray>::cast(
+                  Factory::NewDictionary(at_least_space_for));
+  }
+
+  Handle<Object> len = Factory::NewNumber(static_cast<double>(result_length));
+
+  ArrayConcatVisitor visitor(storage, result_length, fast_case);
+
+  IterateArguments(arguments, &visitor);
+
+  result->set_length(*len);
+  result->set_elements(*storage);
+
+  return *result;
+}
+
+
 // This will not allocate (flatten the string), but it may run
 // very slowly for very deeply nested ConsStrings.  For debugging use only.
 static Object* Runtime_GlobalPrint(Arguments args) {
@@ -5523,9 +5780,15 @@
 
 void Runtime::PerformGC(Object* result) {
   Failure* failure = Failure::cast(result);
-  // Try to do a garbage collection; ignore it if it fails. The C
-  // entry stub will throw an out-of-memory exception in that case.
-  Heap::CollectGarbage(failure->requested(), failure->allocation_space());
+  if (failure->IsRetryAfterGC()) {
+    // Try to do a garbage collection; ignore it if it fails. The C
+    // entry stub will throw an out-of-memory exception in that case.
+    Heap::CollectGarbage(failure->requested(), failure->allocation_space());
+  } else {
+    // Handle last resort GC and make sure to allow future allocations
+    // to grow the heap without causing GCs (if possible).
+    Heap::CollectAllGarbage();
+  }
 }