Merge r3560, r3562 and r3568 from bleeding_edge to 1.3 branch to fix...

src/runtime.cc

 // 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
@@ skipping 1388 matching lines @@
       StringBuilderConcatHelper(*subject_,
                                 char_buffer,
                                 *parts_,
                                 part_count_);
     }
     return joined_string;
   }
 
 
   void IncrementCharacterCount(int by) {
-    if (character_count_ > Smi::kMaxValue - by) {
+    if (character_count_ > String::kMaxLength - by) {
       V8::FatalProcessOutOfMemory("String.replace result too large.");
     }
     character_count_ += by;
   }
 
  private:
 
   Handle<String> NewRawAsciiString(int size) {
     CALL_HEAP_FUNCTION(Heap::AllocateRawAsciiString(size), String);
   }
@@ skipping 1825 matching lines @@
     while (buffer->has_more()) {
       uint16_t character = buffer->GetNext();
       if (character >= 256) {
         escaped_length += 6;
       } else if (IsNotEscaped(character)) {
         escaped_length++;
       } else {
         escaped_length += 3;
       }
       // We don't allow strings that are longer than a maximal length.
+      ASSERT(String::kMaxLength < 0x7fffffff - 6);  // Cannot overflow.
       if (escaped_length > String::kMaxLength) {
         Top::context()->mark_out_of_memory();
         return Failure::OutOfMemoryException();
       }
     }
   }
   // No length change implies no change.  Return original string if no change.
   if (escaped_length == length) {
     return source;
   }
@@ skipping 541 matching lines @@
 
   if (array_length == 0) {
     return Heap::empty_string();
   } else if (array_length == 1) {
     Object* first = fixed_array->get(0);
     if (first->IsString()) return first;
   }
 
   bool ascii = special->IsAsciiRepresentation();
   int position = 0;
+  int increment = 0;
   for (int i = 0; i < array_length; i++) {
     Object* elt = fixed_array->get(i);
     if (elt->IsSmi()) {
       int len = Smi::cast(elt)->value();
       int pos = len >> 11;
       len &= 0x7ff;
       if (pos + len > special_length) {
         return Top::Throw(Heap::illegal_argument_symbol());
       }
-      position += len;
+      increment = len;
     } else if (elt->IsString()) {
       String* element = String::cast(elt);
       int element_length = element->length();
-      position += element_length;
+      increment = element_length;
       if (ascii && !element->IsAsciiRepresentation()) {
         ascii = false;
       }
     } else {
       return Top::Throw(Heap::illegal_argument_symbol());
     }
-    if (position > String::kMaxLength) {
+    if (increment > String::kMaxLength - position) {
       Top::context()->mark_out_of_memory();
       return Failure::OutOfMemoryException();
     }
+    position += increment;
   }
 
   int length = position;
   Object* object;
 
   if (ascii) {
     object = Heap::AllocateRawAsciiString(length);
     if (object->IsFailure()) return object;
     SeqAsciiString* answer = SeqAsciiString::cast(object);
     StringBuilderConcatHelper(special,
@@ skipping 1375 matching lines @@
  *
  * 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) { }
+      index_offset_(0), fast_elements_(fast_elements) { }
 
   void visit(uint32_t i, Handle<Object> elm) {
-    uint32_t index = i + index_offset_;
-    if (index >= index_limit_) return;
+    if (i >= index_limit_ - index_offset_) return;
+    uint32_t index = index_offset_ + i;
 
     if (fast_elements_) {
       ASSERT(index < static_cast<uint32_t>(storage_->length()));
       storage_->set(index, *elm);
 
     } else {
       Handle<NumberDictionary> dict = Handle<NumberDictionary>::cast(storage_);
       Handle<NumberDictionary> result =
           Factory::DictionaryAtNumberPut(dict, index, elm);
       if (!result.is_identical_to(dict))
         storage_ = result;
     }
   }
 
   void increase_index_offset(uint32_t delta) {
-    index_offset_ += delta;
+    if (index_limit_ - index_offset_ < delta) {
+      index_offset_ = index_limit_;
+    } else {
+      index_offset_ += delta;
+    }
   }
 
   Handle<FixedArray> storage() { return storage_; }
 
  private:
   Handle<FixedArray> storage_;
+  // Limit on the accepted indices. Elements with indices larger than the
+  // limit are ignored by the visitor.
   uint32_t index_limit_;
+  // Index after last seen index. Always less than or equal to index_limit_.
+  uint32_t index_offset_;
   bool fast_elements_;
-  uint32_t index_offset_;
 };
 
 
 template<class ExternalArrayClass, class ElementType>
 static uint32_t IterateExternalArrayElements(Handle<JSObject> receiver,
                                              bool elements_are_ints,
                                              bool elements_are_guaranteed_smis,
                                              uint32_t range,
                                              ArrayConcatVisitor* visitor) {
   Handle<ExternalArrayClass> array(
@@ skipping 151 matching lines @@
 
 /**
  * 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.
+ *
+ * The returned number of elements is an upper bound on the actual number
+ * of elements added. If the same element occurs in more than one object
+ * in the array's prototype chain, it will be counted more than once, but
+ * will only occur once in the result.
  */
 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 +=
+    uint32_t encountered_elements =
         IterateElements(Handle<JSObject>::cast(obj), range, visitor);
+
+    if (encountered_elements > JSObject::kMaxElementCount - nof_elements) {
+      nof_elements = JSObject::kMaxElementCount;
+    } else {
+      nof_elements += encountered_elements;
+    }
   }
 
   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
+ * If the result array index overflows 32-bit unsigned 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.
+ * TODO(lrn) Change length behavior to ECMAScript 5 specification (length
+ * is one more than the last array index to get a value assigned).
  */
 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;
+      // the array length number of elements. We use the length as an estimate
+      // for the actual number of elements added.
+      uint32_t added_elements = (nof_elements > len) ? len : nof_elements;
+      if (JSArray::kMaxElementCount - visited_elements < added_elements) {
+        visited_elements = JSArray::kMaxElementCount;
+      } else {
+        visited_elements += added_elements;
+      }
       if (visitor) visitor->increase_index_offset(len);
-
     } else {
       if (visitor) {
         visitor->visit(0, obj);
         visitor->increase_index_offset(1);
       }
-      visited_elements++;
+      if (visited_elements < JSArray::kMaxElementCount) {
+        visited_elements++;
+      }
     }
   }
   return visited_elements;
 }
 
 
 /**
  * Array::concat implementation.
  * See ECMAScript 262, 15.4.4.4.
+ * TODO(lrn): Fix non-compliance for very large concatenations and update to
+ * following the ECMAScript 5 specification.
  */
 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);
+      uint32_t length_estimate;
       if (obj->IsJSArray()) {
-        result_length +=
+        length_estimate =
             static_cast<uint32_t>(JSArray::cast(obj)->length()->Number());
       } else {
-        result_length++;
+        length_estimate = 1;
       }
+      if (JSObject::kMaxElementCount - result_length < length_estimate) {
+        result_length = JSObject::kMaxElementCount;
+        break;
+      }
+      result_length += length_estimate;
     }
   }
 
   // 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.
@@ skipping 2312 matching lines @@
   } else {
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     Counters::gc_last_resort_from_js.Increment();
     Heap::CollectAllGarbage(false);
   }
 }
 
 
 } }  // namespace v8::internal