OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 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 3969 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3980 FixedArray* elements = FixedArray::cast(array->elements()); | 3980 FixedArray* elements = FixedArray::cast(array->elements()); |
3981 for (int i = 0; i < length; i++) { | 3981 for (int i = 0; i < length; i++) { |
3982 if (elements->get(i) == element) return Heap::false_value(); | 3982 if (elements->get(i) == element) return Heap::false_value(); |
3983 } | 3983 } |
3984 Object* obj = array->SetFastElement(length, element); | 3984 Object* obj = array->SetFastElement(length, element); |
3985 if (obj->IsFailure()) return obj; | 3985 if (obj->IsFailure()) return obj; |
3986 return Heap::true_value(); | 3986 return Heap::true_value(); |
3987 } | 3987 } |
3988 | 3988 |
3989 | 3989 |
| 3990 /** |
| 3991 * A simple visitor visits every element of Array's. |
| 3992 * The backend storage can be a fixed array for fast elements case, |
| 3993 * or a dictionary for sparse array. Since Dictionary is a subtype |
| 3994 * of FixedArray, the class can be used by both fast and slow cases. |
| 3995 * The second parameter of the constructor, fast_elements, specifies |
| 3996 * whether the storage is a FixedArray or Dictionary. |
| 3997 */ |
| 3998 class ArrayConcatVisitor { |
| 3999 public: |
| 4000 ArrayConcatVisitor(Handle<FixedArray> storage, bool fast_elements) |
| 4001 : storage_(storage), fast_elements_(fast_elements), index_offset_(0) { } |
| 4002 |
| 4003 void visit(uint32_t i, Handle<Object> elm) { |
| 4004 uint32_t index = i + index_offset_; |
| 4005 |
| 4006 if (fast_elements_) { |
| 4007 ASSERT(index < static_cast<uint32_t>(storage_->length())); |
| 4008 storage_->set(index, *elm); |
| 4009 |
| 4010 } else { |
| 4011 Handle<Dictionary> dict = Handle<Dictionary>::cast(storage_); |
| 4012 Handle<Dictionary> result = |
| 4013 Factory::DictionaryAtNumberPut(dict, index, elm); |
| 4014 if (!result.is_identical_to(dict)) |
| 4015 storage_ = result; |
| 4016 } |
| 4017 } |
| 4018 |
| 4019 void increase_index_offset(uint32_t delta) { |
| 4020 index_offset_ += delta; |
| 4021 } |
| 4022 |
| 4023 private: |
| 4024 Handle<FixedArray> storage_; |
| 4025 bool fast_elements_; |
| 4026 uint32_t index_offset_; |
| 4027 }; |
| 4028 |
| 4029 |
| 4030 /** |
| 4031 * A helper function that visits elements of a JSObject. Only elements |
| 4032 * whose index between 0 and range (exclusive) are visited. |
| 4033 * |
| 4034 * If the third parameter, visitor, is not NULL, the visitor is called |
| 4035 * with parameters, 'visitor_index_offset + element index' and the element. |
| 4036 * |
| 4037 * It returns the number of visisted elements. |
| 4038 */ |
| 4039 static uint32_t IterateElements(Handle<JSObject> receiver, |
| 4040 uint32_t range, |
| 4041 ArrayConcatVisitor* visitor) { |
| 4042 uint32_t num_of_elements = 0; |
| 4043 |
| 4044 if (receiver->HasFastElements()) { |
| 4045 Handle<FixedArray> elements(FixedArray::cast(receiver->elements())); |
| 4046 uint32_t len = elements->length(); |
| 4047 if (range < len) len = range; |
| 4048 |
| 4049 for (uint32_t j = 0; j < len; j++) { |
| 4050 Handle<Object> e(elements->get(j)); |
| 4051 if (!e->IsTheHole()) { |
| 4052 num_of_elements++; |
| 4053 if (visitor) |
| 4054 visitor->visit(j, e); |
| 4055 } |
| 4056 } |
| 4057 |
| 4058 } else { |
| 4059 Handle<Dictionary> dict(receiver->element_dictionary()); |
| 4060 uint32_t capacity = dict->Capacity(); |
| 4061 for (uint32_t j = 0; j < capacity; j++) { |
| 4062 Handle<Object> k(dict->KeyAt(j)); |
| 4063 if (dict->IsKey(*k)) { |
| 4064 ASSERT(k->IsNumber()); |
| 4065 uint32_t index = static_cast<uint32_t>(k->Number()); |
| 4066 if (index < range) { |
| 4067 num_of_elements++; |
| 4068 if (visitor) { |
| 4069 visitor->visit(index, |
| 4070 Handle<Object>(dict->ValueAt(j))); |
| 4071 } |
| 4072 } |
| 4073 } |
| 4074 } |
| 4075 } |
| 4076 |
| 4077 return num_of_elements; |
| 4078 } |
| 4079 |
| 4080 |
| 4081 /** |
| 4082 * A helper function that visits elements of an Array object, and elements |
| 4083 * on its prototypes. |
| 4084 * |
| 4085 * Elements on prototypes are visited first, and only elements whose indices |
| 4086 * less than Array length are visited. |
| 4087 * |
| 4088 * If a ArrayConcatVisitor object is given, the visitor is called with |
| 4089 * parameters, element's index + visitor_index_offset and the element. |
| 4090 */ |
| 4091 static uint32_t IterateArrayAndPrototypeElements(Handle<JSArray> array, |
| 4092 ArrayConcatVisitor* visitor) { |
| 4093 uint32_t range = static_cast<uint32_t>(array->length()->Number()); |
| 4094 Handle<Object> obj = array; |
| 4095 |
| 4096 static const int kEstimatedPrototypes = 3; |
| 4097 List< Handle<JSObject> > objects(kEstimatedPrototypes); |
| 4098 |
| 4099 // Visit prototype first. If an element on the prototype is shadowed by |
| 4100 // the inheritor using the same index, the ArrayConcatVisitor visits |
| 4101 // the prototype element before the shadowing element. |
| 4102 // The visitor can simply overwrite the old value by new value using |
| 4103 // the same index. This follows Array::concat semantics. |
| 4104 while(!obj->IsNull()) { |
| 4105 objects.Add(obj); |
| 4106 obj = Handle<Object>(obj->GetPrototype()); |
| 4107 } |
| 4108 |
| 4109 uint32_t nof_elements = 0; |
| 4110 for (int i = objects.length() - 1; i >= 0; i--) { |
| 4111 Handle<JSObject> obj = objects[i]; |
| 4112 nof_elements += |
| 4113 IterateElements(Handle<JSObject>::cast(obj), range, visitor); |
| 4114 } |
| 4115 |
| 4116 return nof_elements; |
| 4117 } |
| 4118 |
| 4119 |
| 4120 /** |
| 4121 * A helper function of Runtime_ArrayConcat. |
| 4122 * |
| 4123 * The first argument is an Array of Arrays and objects. It is the same as |
| 4124 * the arguments array of Array::concat JS function. |
| 4125 * |
| 4126 * If an argument is an Array object, the function visits array elements. |
| 4127 * If an argument is not an Array object, the function visits the object |
| 4128 * as if it is an one-element array. |
| 4129 */ |
| 4130 static uint32_t IterateArguments(Handle<JSArray> arguments, |
| 4131 ArrayConcatVisitor* visitor) { |
| 4132 uint32_t visited_elements = 0; |
| 4133 uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number()); |
| 4134 |
| 4135 for (uint32_t i = 0; i < num_of_args; i++) { |
| 4136 Handle<Object> obj(arguments->GetElement(i)); |
| 4137 if (obj->IsJSArray()) { |
| 4138 Handle<JSArray> array = Handle<JSArray>::cast(obj); |
| 4139 uint32_t len = static_cast<uint32_t>(array->length()->Number()); |
| 4140 uint32_t nof_elements = |
| 4141 IterateArrayAndPrototypeElements(array, visitor); |
| 4142 // Total elements of array and its prototype chain can be more than |
| 4143 // the array length, but ArrayConcat can only concatenate at most |
| 4144 // the array length number of elements. |
| 4145 visited_elements += (nof_elements > len) ? len : nof_elements; |
| 4146 if (visitor) visitor->increase_index_offset(len); |
| 4147 |
| 4148 } else { |
| 4149 if (visitor) { |
| 4150 visitor->visit(0, obj); |
| 4151 visitor->increase_index_offset(1); |
| 4152 } |
| 4153 visited_elements++; |
| 4154 } |
| 4155 } |
| 4156 return visited_elements; |
| 4157 } |
| 4158 |
| 4159 |
| 4160 /** |
| 4161 * Array::concat implementation. |
| 4162 * See ECMAScript 262, 15.4.4.4. |
| 4163 */ |
| 4164 static Object* Runtime_ArrayConcat(Arguments args) { |
| 4165 ASSERT(args.length() == 1); |
| 4166 HandleScope handle_scope; |
| 4167 |
| 4168 CONVERT_CHECKED(JSArray, arg_arrays, args[0]); |
| 4169 Handle<JSArray> arguments(arg_arrays); |
| 4170 |
| 4171 // Pass 1: estimate the number of elements of the result |
| 4172 // (it could be more than real numbers if prototype has elements). |
| 4173 uint32_t result_length = 0; |
| 4174 uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number()); |
| 4175 |
| 4176 { AssertNoAllocation nogc; |
| 4177 for (uint32_t i = 0; i < num_of_args; i++) { |
| 4178 Object* obj = arguments->GetElement(i); |
| 4179 if (obj->IsJSArray()) { |
| 4180 result_length += |
| 4181 static_cast<uint32_t>(JSArray::cast(obj)->length()->Number()); |
| 4182 } else { |
| 4183 result_length++; |
| 4184 } |
| 4185 } |
| 4186 } |
| 4187 |
| 4188 // Allocate an empty array, will set length and content later. |
| 4189 Handle<JSArray> result = Factory::NewJSArray(0); |
| 4190 |
| 4191 uint32_t estimate_nof_elements = IterateArguments(arguments, NULL); |
| 4192 // If estimated number of elements is more than half of length, |
| 4193 // A fixed array (fast case) is more time & space-efficient than a dictionary. |
| 4194 bool fast_case = (estimate_nof_elements * 2) >= result_length; |
| 4195 |
| 4196 Handle<FixedArray> storage; |
| 4197 if (fast_case) { |
| 4198 storage = Factory::NewFixedArray(result_length); |
| 4199 |
| 4200 } else { |
| 4201 // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate |
| 4202 uint32_t at_least_space_for = estimate_nof_elements + |
| 4203 (estimate_nof_elements >> 2); |
| 4204 storage = Handle<FixedArray>::cast( |
| 4205 Factory::NewDictionary(at_least_space_for)); |
| 4206 } |
| 4207 |
| 4208 Handle<Object> len = Factory::NewNumber(static_cast<double>(result_length)); |
| 4209 |
| 4210 ArrayConcatVisitor visitor(storage, fast_case); |
| 4211 |
| 4212 IterateArguments(arguments, &visitor); |
| 4213 |
| 4214 result->set_length(*len); |
| 4215 result->set_elements(*storage); |
| 4216 |
| 4217 return *result; |
| 4218 } |
| 4219 |
| 4220 |
3990 // This will not allocate (flatten the string), but it may run | 4221 // This will not allocate (flatten the string), but it may run |
3991 // very slowly for very deeply nested ConsStrings. For debugging use only. | 4222 // very slowly for very deeply nested ConsStrings. For debugging use only. |
3992 static Object* Runtime_GlobalPrint(Arguments args) { | 4223 static Object* Runtime_GlobalPrint(Arguments args) { |
3993 NoHandleAllocation ha; | 4224 NoHandleAllocation ha; |
3994 ASSERT(args.length() == 1); | 4225 ASSERT(args.length() == 1); |
3995 | 4226 |
3996 CONVERT_CHECKED(String, string, args[0]); | 4227 CONVERT_CHECKED(String, string, args[0]); |
3997 StringInputBuffer buffer(string); | 4228 StringInputBuffer buffer(string); |
3998 while (buffer.has_more()) { | 4229 while (buffer.has_more()) { |
3999 uint16_t character = buffer.GetNext(); | 4230 uint16_t character = buffer.GetNext(); |
(...skipping 1523 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5523 | 5754 |
5524 void Runtime::PerformGC(Object* result) { | 5755 void Runtime::PerformGC(Object* result) { |
5525 Failure* failure = Failure::cast(result); | 5756 Failure* failure = Failure::cast(result); |
5526 // Try to do a garbage collection; ignore it if it fails. The C | 5757 // Try to do a garbage collection; ignore it if it fails. The C |
5527 // entry stub will throw an out-of-memory exception in that case. | 5758 // entry stub will throw an out-of-memory exception in that case. |
5528 Heap::CollectGarbage(failure->requested(), failure->allocation_space()); | 5759 Heap::CollectGarbage(failure->requested(), failure->allocation_space()); |
5529 } | 5760 } |
5530 | 5761 |
5531 | 5762 |
5532 } } // namespace v8::internal | 5763 } } // namespace v8::internal |
OLD | NEW |