OLD | NEW |
1 // Copyright 2006-2009 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2009 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 5353 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5364 */ | 5364 */ |
5365 class ArrayConcatVisitor { | 5365 class ArrayConcatVisitor { |
5366 public: | 5366 public: |
5367 ArrayConcatVisitor(Handle<FixedArray> storage, | 5367 ArrayConcatVisitor(Handle<FixedArray> storage, |
5368 uint32_t index_limit, | 5368 uint32_t index_limit, |
5369 bool fast_elements) : | 5369 bool fast_elements) : |
5370 storage_(storage), index_limit_(index_limit), | 5370 storage_(storage), index_limit_(index_limit), |
5371 fast_elements_(fast_elements), index_offset_(0) { } | 5371 fast_elements_(fast_elements), index_offset_(0) { } |
5372 | 5372 |
5373 void visit(uint32_t i, Handle<Object> elm) { | 5373 void visit(uint32_t i, Handle<Object> elm) { |
5374 uint32_t index = i + index_offset_; | 5374 if (i >= index_limit_ - index_offset_) return; |
5375 if (index >= index_limit_) return; | 5375 uint32_t index = index_offset_ + i; |
5376 | 5376 |
5377 if (fast_elements_) { | 5377 if (fast_elements_) { |
5378 ASSERT(index < static_cast<uint32_t>(storage_->length())); | 5378 ASSERT(index < static_cast<uint32_t>(storage_->length())); |
5379 storage_->set(index, *elm); | 5379 storage_->set(index, *elm); |
5380 | 5380 |
5381 } else { | 5381 } else { |
5382 Handle<NumberDictionary> dict = Handle<NumberDictionary>::cast(storage_); | 5382 Handle<NumberDictionary> dict = Handle<NumberDictionary>::cast(storage_); |
5383 Handle<NumberDictionary> result = | 5383 Handle<NumberDictionary> result = |
5384 Factory::DictionaryAtNumberPut(dict, index, elm); | 5384 Factory::DictionaryAtNumberPut(dict, index, elm); |
5385 if (!result.is_identical_to(dict)) | 5385 if (!result.is_identical_to(dict)) |
5386 storage_ = result; | 5386 storage_ = result; |
5387 } | 5387 } |
5388 } | 5388 } |
5389 | 5389 |
5390 void increase_index_offset(uint32_t delta) { | 5390 void increase_index_offset(uint32_t delta) { |
5391 index_offset_ += delta; | 5391 if (index_limit_ - index_offset_ < delta) { |
| 5392 index_offset_ = index_limit_; |
| 5393 } else { |
| 5394 index_offset_ += delta; |
| 5395 } |
5392 } | 5396 } |
5393 | 5397 |
5394 Handle<FixedArray> storage() { return storage_; } | 5398 Handle<FixedArray> storage() { return storage_; } |
5395 | 5399 |
5396 private: | 5400 private: |
5397 Handle<FixedArray> storage_; | 5401 Handle<FixedArray> storage_; |
| 5402 // Limit on the accepted indices. Elements with indices larger than the |
| 5403 // limit are ignored by the visitor. |
5398 uint32_t index_limit_; | 5404 uint32_t index_limit_; |
| 5405 // Index after last seen index. Always less than or equal to index_limit_. |
| 5406 uint32_t index_offset_; |
5399 bool fast_elements_; | 5407 bool fast_elements_; |
5400 uint32_t index_offset_; | |
5401 }; | 5408 }; |
5402 | 5409 |
5403 | 5410 |
5404 template<class ExternalArrayClass, class ElementType> | 5411 template<class ExternalArrayClass, class ElementType> |
5405 static uint32_t IterateExternalArrayElements(Handle<JSObject> receiver, | 5412 static uint32_t IterateExternalArrayElements(Handle<JSObject> receiver, |
5406 bool elements_are_ints, | 5413 bool elements_are_ints, |
5407 bool elements_are_guaranteed_smis, | 5414 bool elements_are_guaranteed_smis, |
5408 uint32_t range, | 5415 uint32_t range, |
5409 ArrayConcatVisitor* visitor) { | 5416 ArrayConcatVisitor* visitor) { |
5410 Handle<ExternalArrayClass> array( | 5417 Handle<ExternalArrayClass> array( |
(...skipping 151 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5562 | 5569 |
5563 /** | 5570 /** |
5564 * A helper function that visits elements of an Array object, and elements | 5571 * A helper function that visits elements of an Array object, and elements |
5565 * on its prototypes. | 5572 * on its prototypes. |
5566 * | 5573 * |
5567 * Elements on prototypes are visited first, and only elements whose indices | 5574 * Elements on prototypes are visited first, and only elements whose indices |
5568 * less than Array length are visited. | 5575 * less than Array length are visited. |
5569 * | 5576 * |
5570 * If a ArrayConcatVisitor object is given, the visitor is called with | 5577 * If a ArrayConcatVisitor object is given, the visitor is called with |
5571 * parameters, element's index + visitor_index_offset and the element. | 5578 * parameters, element's index + visitor_index_offset and the element. |
| 5579 * |
| 5580 * The returned number of elements is an upper bound on the actual number |
| 5581 * of elements added. If the same element occurs in more than one object |
| 5582 * in the array's prototype chain, it will be counted more than once, but |
| 5583 * will only occur once in the result. |
5572 */ | 5584 */ |
5573 static uint32_t IterateArrayAndPrototypeElements(Handle<JSArray> array, | 5585 static uint32_t IterateArrayAndPrototypeElements(Handle<JSArray> array, |
5574 ArrayConcatVisitor* visitor) { | 5586 ArrayConcatVisitor* visitor) { |
5575 uint32_t range = static_cast<uint32_t>(array->length()->Number()); | 5587 uint32_t range = static_cast<uint32_t>(array->length()->Number()); |
5576 Handle<Object> obj = array; | 5588 Handle<Object> obj = array; |
5577 | 5589 |
5578 static const int kEstimatedPrototypes = 3; | 5590 static const int kEstimatedPrototypes = 3; |
5579 List< Handle<JSObject> > objects(kEstimatedPrototypes); | 5591 List< Handle<JSObject> > objects(kEstimatedPrototypes); |
5580 | 5592 |
5581 // Visit prototype first. If an element on the prototype is shadowed by | 5593 // Visit prototype first. If an element on the prototype is shadowed by |
5582 // the inheritor using the same index, the ArrayConcatVisitor visits | 5594 // the inheritor using the same index, the ArrayConcatVisitor visits |
5583 // the prototype element before the shadowing element. | 5595 // the prototype element before the shadowing element. |
5584 // The visitor can simply overwrite the old value by new value using | 5596 // The visitor can simply overwrite the old value by new value using |
5585 // the same index. This follows Array::concat semantics. | 5597 // the same index. This follows Array::concat semantics. |
5586 while (!obj->IsNull()) { | 5598 while (!obj->IsNull()) { |
5587 objects.Add(Handle<JSObject>::cast(obj)); | 5599 objects.Add(Handle<JSObject>::cast(obj)); |
5588 obj = Handle<Object>(obj->GetPrototype()); | 5600 obj = Handle<Object>(obj->GetPrototype()); |
5589 } | 5601 } |
5590 | 5602 |
5591 uint32_t nof_elements = 0; | 5603 uint32_t nof_elements = 0; |
5592 for (int i = objects.length() - 1; i >= 0; i--) { | 5604 for (int i = objects.length() - 1; i >= 0; i--) { |
5593 Handle<JSObject> obj = objects[i]; | 5605 Handle<JSObject> obj = objects[i]; |
5594 nof_elements += | 5606 uint32_t encountered_elements = |
5595 IterateElements(Handle<JSObject>::cast(obj), range, visitor); | 5607 IterateElements(Handle<JSObject>::cast(obj), range, visitor); |
| 5608 |
| 5609 if (encountered_elements > JSObject::kMaxElementCount - nof_elements) { |
| 5610 nof_elements = JSObject::kMaxElementCount; |
| 5611 } else { |
| 5612 nof_elements += encountered_elements; |
| 5613 } |
5596 } | 5614 } |
5597 | 5615 |
5598 return nof_elements; | 5616 return nof_elements; |
5599 } | 5617 } |
5600 | 5618 |
5601 | 5619 |
5602 /** | 5620 /** |
5603 * A helper function of Runtime_ArrayConcat. | 5621 * A helper function of Runtime_ArrayConcat. |
5604 * | 5622 * |
5605 * The first argument is an Array of arrays and objects. It is the | 5623 * The first argument is an Array of arrays and objects. It is the |
5606 * same as the arguments array of Array::concat JS function. | 5624 * same as the arguments array of Array::concat JS function. |
5607 * | 5625 * |
5608 * If an argument is an Array object, the function visits array | 5626 * If an argument is an Array object, the function visits array |
5609 * elements. If an argument is not an Array object, the function | 5627 * elements. If an argument is not an Array object, the function |
5610 * visits the object as if it is an one-element array. | 5628 * visits the object as if it is an one-element array. |
5611 * | 5629 * |
5612 * If the result array index overflows 32-bit integer, the rounded | 5630 * If the result array index overflows 32-bit unsigned integer, the rounded |
5613 * non-negative number is used as new length. For example, if one | 5631 * non-negative number is used as new length. For example, if one |
5614 * array length is 2^32 - 1, second array length is 1, the | 5632 * array length is 2^32 - 1, second array length is 1, the |
5615 * concatenated array length is 0. | 5633 * concatenated array length is 0. |
| 5634 * TODO(lrn) Change length behavior to ECMAScript 5 specification (length |
| 5635 * is one more than the last array index to get a value assigned). |
5616 */ | 5636 */ |
5617 static uint32_t IterateArguments(Handle<JSArray> arguments, | 5637 static uint32_t IterateArguments(Handle<JSArray> arguments, |
5618 ArrayConcatVisitor* visitor) { | 5638 ArrayConcatVisitor* visitor) { |
| 5639 const uint32_t max_length = JSObject::kMaxElementCount; |
5619 uint32_t visited_elements = 0; | 5640 uint32_t visited_elements = 0; |
5620 uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number()); | 5641 uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number()); |
5621 | 5642 |
5622 for (uint32_t i = 0; i < num_of_args; i++) { | 5643 for (uint32_t i = 0; i < num_of_args; i++) { |
5623 Handle<Object> obj(arguments->GetElement(i)); | 5644 Handle<Object> obj(arguments->GetElement(i)); |
5624 if (obj->IsJSArray()) { | 5645 if (obj->IsJSArray()) { |
5625 Handle<JSArray> array = Handle<JSArray>::cast(obj); | 5646 Handle<JSArray> array = Handle<JSArray>::cast(obj); |
5626 uint32_t len = static_cast<uint32_t>(array->length()->Number()); | 5647 uint32_t len = static_cast<uint32_t>(array->length()->Number()); |
5627 uint32_t nof_elements = | 5648 uint32_t nof_elements = |
5628 IterateArrayAndPrototypeElements(array, visitor); | 5649 IterateArrayAndPrototypeElements(array, visitor); |
5629 // Total elements of array and its prototype chain can be more than | 5650 // Total elements of array and its prototype chain can be more than |
5630 // the array length, but ArrayConcat can only concatenate at most | 5651 // the array length, but ArrayConcat can only concatenate at most |
5631 // the array length number of elements. | 5652 // the array length number of elements. We use the length as an estimate |
5632 visited_elements += (nof_elements > len) ? len : nof_elements; | 5653 // for the actual number of elements added. |
| 5654 uint32_t added_elements = (nof_elements > len) ? len : nof_elements; |
| 5655 if (JSArray::kMaxElementCount - visited_elements < added_elements) { |
| 5656 visited_elements = JSArray::kMaxElementCount; |
| 5657 } else { |
| 5658 visited_elements += added_elements; |
| 5659 } |
5633 if (visitor) visitor->increase_index_offset(len); | 5660 if (visitor) visitor->increase_index_offset(len); |
5634 | |
5635 } else { | 5661 } else { |
5636 if (visitor) { | 5662 if (visitor) { |
5637 visitor->visit(0, obj); | 5663 visitor->visit(0, obj); |
5638 visitor->increase_index_offset(1); | 5664 visitor->increase_index_offset(1); |
5639 } | 5665 } |
5640 visited_elements++; | 5666 if (visited_elements < JSArray::kMaxElementCount) { |
| 5667 visited_elements++; |
| 5668 } |
5641 } | 5669 } |
5642 } | 5670 } |
5643 return visited_elements; | 5671 return visited_elements; |
5644 } | 5672 } |
5645 | 5673 |
5646 | 5674 |
5647 /** | 5675 /** |
5648 * Array::concat implementation. | 5676 * Array::concat implementation. |
5649 * See ECMAScript 262, 15.4.4.4. | 5677 * See ECMAScript 262, 15.4.4.4. |
| 5678 * TODO(lrn): Fix non-compliance for very large concatenations and update to |
| 5679 * following the ECMAScript 5 specification. |
5650 */ | 5680 */ |
5651 static Object* Runtime_ArrayConcat(Arguments args) { | 5681 static Object* Runtime_ArrayConcat(Arguments args) { |
5652 ASSERT(args.length() == 1); | 5682 ASSERT(args.length() == 1); |
5653 HandleScope handle_scope; | 5683 HandleScope handle_scope; |
5654 | 5684 |
5655 CONVERT_CHECKED(JSArray, arg_arrays, args[0]); | 5685 CONVERT_CHECKED(JSArray, arg_arrays, args[0]); |
5656 Handle<JSArray> arguments(arg_arrays); | 5686 Handle<JSArray> arguments(arg_arrays); |
5657 | 5687 |
5658 // Pass 1: estimate the number of elements of the result | 5688 // Pass 1: estimate the number of elements of the result |
5659 // (it could be more than real numbers if prototype has elements). | 5689 // (it could be more than real numbers if prototype has elements). |
5660 uint32_t result_length = 0; | 5690 uint32_t result_length = 0; |
5661 uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number()); | 5691 uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number()); |
5662 | 5692 |
5663 { AssertNoAllocation nogc; | 5693 { AssertNoAllocation nogc; |
5664 for (uint32_t i = 0; i < num_of_args; i++) { | 5694 for (uint32_t i = 0; i < num_of_args; i++) { |
5665 Object* obj = arguments->GetElement(i); | 5695 Object* obj = arguments->GetElement(i); |
| 5696 uint32_t length_estimate; |
5666 if (obj->IsJSArray()) { | 5697 if (obj->IsJSArray()) { |
5667 result_length += | 5698 length_estimate = |
5668 static_cast<uint32_t>(JSArray::cast(obj)->length()->Number()); | 5699 static_cast<uint32_t>(JSArray::cast(obj)->length()->Number()); |
5669 } else { | 5700 } else { |
5670 result_length++; | 5701 length_estimate = 1; |
5671 } | 5702 } |
| 5703 if (JSObject::kMaxElementCount - result_length < length_estimate) { |
| 5704 result_length = JSObject::kMaxElementCount; |
| 5705 break; |
| 5706 } |
| 5707 result_length += length_estimate; |
5672 } | 5708 } |
5673 } | 5709 } |
5674 | 5710 |
5675 // Allocate an empty array, will set length and content later. | 5711 // Allocate an empty array, will set length and content later. |
5676 Handle<JSArray> result = Factory::NewJSArray(0); | 5712 Handle<JSArray> result = Factory::NewJSArray(0); |
5677 | 5713 |
5678 uint32_t estimate_nof_elements = IterateArguments(arguments, NULL); | 5714 uint32_t estimate_nof_elements = IterateArguments(arguments, NULL); |
5679 // If estimated number of elements is more than half of length, a | 5715 // If estimated number of elements is more than half of length, a |
5680 // fixed array (fast case) is more time and space-efficient than a | 5716 // fixed array (fast case) is more time and space-efficient than a |
5681 // dictionary. | 5717 // dictionary. |
(...skipping 2345 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
8027 } else { | 8063 } else { |
8028 // Handle last resort GC and make sure to allow future allocations | 8064 // Handle last resort GC and make sure to allow future allocations |
8029 // to grow the heap without causing GCs (if possible). | 8065 // to grow the heap without causing GCs (if possible). |
8030 Counters::gc_last_resort_from_js.Increment(); | 8066 Counters::gc_last_resort_from_js.Increment(); |
8031 Heap::CollectAllGarbage(false); | 8067 Heap::CollectAllGarbage(false); |
8032 } | 8068 } |
8033 } | 8069 } |
8034 | 8070 |
8035 | 8071 |
8036 } } // namespace v8::internal | 8072 } } // namespace v8::internal |
OLD | NEW |