From a1af5a2a2f30520e9e97c331099b28f9ce7a6426 Mon Sep 17 00:00:00 2001 From: "adamk@chromium.org" Date: Wed, 16 Apr 2014 00:40:03 +0000 Subject: [PATCH] ES6: Add support for Map/Set forEach This implements MapIterator and SetIterator which matches the same constructs in the ES6 spec. However, these 2 iterators are not exposed to user code yet. They are only used internally to implement Map.prototype.forEach and Set.prototype.forEach. Each iterator has a reference to the OrderedHashTable where it directly accesses the hash table's entries. The OrderedHashTable has a reference to the newest iterator and each iterator has a reference to the next and previous iterator, effectively creating a double linked list. When the OrderedHashTable is mutated (or replaced) all the iterators are updated. When the iterator iterates passed the end of the data table it closes itself. Closed iterators no longer have a reference to the OrderedHashTable and they are removed from the double linked list. In the case of Map/Set forEach, we manually call Close on the iterator in case an exception was thrown so that the iterator never reached the end. At this point the OrderedHashTable keeps all the non finished iterators alive but since the only thing we currently expose is forEach there are no unfinished iterators outside a forEach call. Once we expose the iterators to user code we will need to make the references from the OrderedHashTable to the iterators weak and have some mechanism to close an iterator when it is garbage collected. BUG=1793,2323 LOG=Y R=adamk@chromium.org, mstarzinger@chromium.org Review URL: https://codereview.chromium.org/236143002 Patch from Erik Arvidsson . git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@20781 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/full-codegen-arm.cc | 2 +- src/arm64/full-codegen-arm64.cc | 2 +- src/array-iterator.js | 15 +- src/bootstrapper.cc | 43 +++-- src/collection.js | 60 +++++- src/contexts.h | 8 +- src/factory.cc | 13 ++ src/factory.h | 2 + src/ia32/full-codegen-ia32.cc | 2 +- src/macros.py | 5 + src/mips/full-codegen-mips.cc | 2 +- src/objects-debug.cc | 40 ++++ src/objects-inl.h | 34 ++++ src/objects-printer.cc | 44 ++++- src/objects-visiting.cc | 2 + src/objects.cc | 282 +++++++++++++++++++++++++-- src/objects.h | 186 +++++++++++++++++- src/runtime.cc | 85 ++++++++ src/runtime.h | 10 + src/x64/full-codegen-x64.cc | 2 +- test/cctest/test-ordered-hash-table.cc | 81 ++++++++ test/mjsunit/harmony/collections.js | 344 +++++++++++++++++++++++++++++++++ 22 files changed, 1193 insertions(+), 71 deletions(-) diff --git a/src/arm/full-codegen-arm.cc b/src/arm/full-codegen-arm.cc index 92664ed..3679a6f 100644 --- a/src/arm/full-codegen-arm.cc +++ b/src/arm/full-codegen-arm.cc @@ -2278,7 +2278,7 @@ void FullCodeGenerator::EmitCreateIteratorResult(bool done) { Label gc_required; Label allocated; - Handle map(isolate()->native_context()->generator_result_map()); + Handle map(isolate()->native_context()->iterator_result_map()); __ Allocate(map->instance_size(), r0, r2, r3, &gc_required, TAG_OBJECT); __ jmp(&allocated); diff --git a/src/arm64/full-codegen-arm64.cc b/src/arm64/full-codegen-arm64.cc index 96e6d65..76bb1b5 100644 --- a/src/arm64/full-codegen-arm64.cc +++ b/src/arm64/full-codegen-arm64.cc @@ -4706,7 +4706,7 @@ void FullCodeGenerator::EmitCreateIteratorResult(bool done) { Label gc_required; Label allocated; - Handle map(isolate()->native_context()->generator_result_map()); + Handle map(isolate()->native_context()->iterator_result_map()); // Allocate and populate an object with this form: { value: VAL, done: DONE } diff --git a/src/array-iterator.js b/src/array-iterator.js index 3af659d..10116b1 100644 --- a/src/array-iterator.js +++ b/src/array-iterator.js @@ -31,11 +31,6 @@ // in runtime.js: // var $Array = global.Array; -var ARRAY_ITERATOR_KIND_KEYS = 1; -var ARRAY_ITERATOR_KIND_VALUES = 2; -var ARRAY_ITERATOR_KIND_ENTRIES = 3; -// The spec draft also has "sparse" but it is never used. - var arrayIteratorObjectSymbol = GLOBAL_PRIVATE("ArrayIterator#object"); var arrayIteratorNextIndexSymbol = GLOBAL_PRIVATE("ArrayIterator#next"); var arrayIterationKindSymbol = GLOBAL_PRIVATE("ArrayIterator#kind"); @@ -79,25 +74,25 @@ function ArrayIteratorNext() { SET_PRIVATE(iterator, arrayIteratorNextIndexSymbol, index + 1); - if (itemKind == ARRAY_ITERATOR_KIND_VALUES) + if (itemKind == ITERATOR_KIND_VALUES) return CreateIteratorResultObject(array[index], false); - if (itemKind == ARRAY_ITERATOR_KIND_ENTRIES) + if (itemKind == ITERATOR_KIND_ENTRIES) return CreateIteratorResultObject([index, array[index]], false); return CreateIteratorResultObject(index, false); } function ArrayEntries() { - return CreateArrayIterator(this, ARRAY_ITERATOR_KIND_ENTRIES); + return CreateArrayIterator(this, ITERATOR_KIND_ENTRIES); } function ArrayValues() { - return CreateArrayIterator(this, ARRAY_ITERATOR_KIND_VALUES); + return CreateArrayIterator(this, ITERATOR_KIND_VALUES); } function ArrayKeys() { - return CreateArrayIterator(this, ARRAY_ITERATOR_KIND_KEYS); + return CreateArrayIterator(this, ITERATOR_KIND_KEYS); } function SetUpArrayIterator() { diff --git a/src/bootstrapper.cc b/src/bootstrapper.cc index 45f55f8..7016b85 100644 --- a/src/bootstrapper.cc +++ b/src/bootstrapper.cc @@ -1304,6 +1304,16 @@ void Genesis::InitializeExperimentalGlobal() { isolate()->initial_object_prototype(), Builtins::kIllegal, true, true); } + { // -- S e t I t e r a t o r + Handle map = isolate()->factory()->NewMap( + JS_SET_ITERATOR_TYPE, JSSetIterator::kSize); + native_context()->set_set_iterator_map(*map); + } + { // -- M a p I t e r a t o r + Handle map = isolate()->factory()->NewMap( + JS_MAP_ITERATOR_TYPE, JSMapIterator::kSize); + native_context()->set_map_iterator_map(*map); + } } if (FLAG_harmony_weak_collections) { @@ -1358,37 +1368,38 @@ void Genesis::InitializeExperimentalGlobal() { *generator_object_prototype); native_context()->set_generator_object_prototype_map( *generator_object_prototype_map); + } + + if (FLAG_harmony_collections || FLAG_harmony_generators) { + // Collection forEach uses an iterator result object. + // Generators return iteraror result objects. - // Create a map for generator result objects. - ASSERT(object_function->initial_map()->inobject_properties() == 0); STATIC_ASSERT(JSGeneratorObject::kResultPropertyCount == 2); - Handle generator_result_map = Map::Create( + Handle object_function(native_context()->object_function()); + ASSERT(object_function->initial_map()->inobject_properties() == 0); + Handle iterator_result_map = Map::Create( object_function, JSGeneratorObject::kResultPropertyCount); - ASSERT(generator_result_map->inobject_properties() == + ASSERT(iterator_result_map->inobject_properties() == JSGeneratorObject::kResultPropertyCount); Map::EnsureDescriptorSlack( - generator_result_map, JSGeneratorObject::kResultPropertyCount); + iterator_result_map, JSGeneratorObject::kResultPropertyCount); - Handle value_string = factory()->InternalizeOneByteString( - STATIC_ASCII_VECTOR("value")); - FieldDescriptor value_descr(value_string, + FieldDescriptor value_descr(isolate()->factory()->value_string(), JSGeneratorObject::kResultValuePropertyIndex, NONE, Representation::Tagged()); - generator_result_map->AppendDescriptor(&value_descr); + iterator_result_map->AppendDescriptor(&value_descr); - Handle done_string = factory()->InternalizeOneByteString( - STATIC_ASCII_VECTOR("done")); - FieldDescriptor done_descr(done_string, + FieldDescriptor done_descr(isolate()->factory()->done_string(), JSGeneratorObject::kResultDonePropertyIndex, NONE, Representation::Tagged()); - generator_result_map->AppendDescriptor(&done_descr); + iterator_result_map->AppendDescriptor(&done_descr); - generator_result_map->set_unused_property_fields(0); + iterator_result_map->set_unused_property_fields(0); ASSERT_EQ(JSGeneratorObject::kResultSize, - generator_result_map->instance_size()); - native_context()->set_generator_result_map(*generator_result_map); + iterator_result_map->instance_size()); + native_context()->set_iterator_result_map(*iterator_result_map); } } diff --git a/src/collection.js b/src/collection.js index 9054187..f2b481b 100644 --- a/src/collection.js +++ b/src/collection.js @@ -113,8 +113,29 @@ function SetClear() { throw MakeTypeError('incompatible_method_receiver', ['Set.prototype.clear', this]); } - // Replace the internal table with a new empty table. - %SetInitialize(this); + %SetClear(this); +} + + +function SetForEach(f, receiver) { + if (!IS_SET(this)) { + throw MakeTypeError('incompatible_method_receiver', + ['Set.prototype.forEach', this]); + } + + if (!IS_SPEC_FUNCTION(f)) { + throw MakeTypeError('called_non_callable', [f]); + } + + var iterator = %SetCreateIterator(this, ITERATOR_KIND_VALUES); + var entry; + try { + while (!(entry = %SetIteratorNext(iterator)).done) { + %_CallFunction(receiver, entry.value, entry.value, this, f); + } + } finally { + %SetIteratorClose(iterator); + } } @@ -127,13 +148,16 @@ function SetUpSet() { %FunctionSetPrototype($Set, new $Object()); %SetProperty($Set.prototype, "constructor", $Set, DONT_ENUM); + %FunctionSetLength(SetForEach, 1); + // Set up the non-enumerable functions on the Set prototype object. InstallGetter($Set.prototype, "size", SetGetSize); InstallFunctions($Set.prototype, DONT_ENUM, $Array( "add", SetAdd, "has", SetHas, "delete", SetDelete, - "clear", SetClear + "clear", SetClear, + "forEach", SetForEach )); } @@ -202,8 +226,29 @@ function MapClear() { throw MakeTypeError('incompatible_method_receiver', ['Map.prototype.clear', this]); } - // Replace the internal table with a new empty table. - %MapInitialize(this); + %MapClear(this); +} + + +function MapForEach(f, receiver) { + if (!IS_MAP(this)) { + throw MakeTypeError('incompatible_method_receiver', + ['Map.prototype.forEach', this]); + } + + if (!IS_SPEC_FUNCTION(f)) { + throw MakeTypeError('called_non_callable', [f]); + } + + var iterator = %MapCreateIterator(this, ITERATOR_KIND_ENTRIES); + var entry; + try { + while (!(entry = %MapIteratorNext(iterator)).done) { + %_CallFunction(receiver, entry.value[1], entry.value[0], this, f); + } + } finally { + %MapIteratorClose(iterator); + } } @@ -216,6 +261,8 @@ function SetUpMap() { %FunctionSetPrototype($Map, new $Object()); %SetProperty($Map.prototype, "constructor", $Map, DONT_ENUM); + %FunctionSetLength(MapForEach, 1); + // Set up the non-enumerable functions on the Map prototype object. InstallGetter($Map.prototype, "size", MapGetSize); InstallFunctions($Map.prototype, DONT_ENUM, $Array( @@ -223,7 +270,8 @@ function SetUpMap() { "set", MapSet, "has", MapHas, "delete", MapDelete, - "clear", MapClear + "clear", MapClear, + "forEach", MapForEach )); } diff --git a/src/contexts.h b/src/contexts.h index 6ba9b3e..7bb6eb4 100644 --- a/src/contexts.h +++ b/src/contexts.h @@ -191,7 +191,9 @@ enum BindingFlags { V(STRICT_GENERATOR_FUNCTION_MAP_INDEX, Map, strict_generator_function_map) \ V(GENERATOR_OBJECT_PROTOTYPE_MAP_INDEX, Map, \ generator_object_prototype_map) \ - V(GENERATOR_RESULT_MAP_INDEX, Map, generator_result_map) + V(ITERATOR_RESULT_MAP_INDEX, Map, iterator_result_map) \ + V(MAP_ITERATOR_MAP_INDEX, Map, map_iterator_map) \ + V(SET_ITERATOR_MAP_INDEX, Map, set_iterator_map) // JSFunctions are pairs (context, function code), sometimes also called // closures. A Context object is used to represent function contexts and @@ -347,7 +349,9 @@ class Context: public FixedArray { SLOPPY_GENERATOR_FUNCTION_MAP_INDEX, STRICT_GENERATOR_FUNCTION_MAP_INDEX, GENERATOR_OBJECT_PROTOTYPE_MAP_INDEX, - GENERATOR_RESULT_MAP_INDEX, + ITERATOR_RESULT_MAP_INDEX, + MAP_ITERATOR_MAP_INDEX, + SET_ITERATOR_MAP_INDEX, // Properties from here are treated as weak references by the full GC. // Scavenge treats them as strong references. diff --git a/src/factory.cc b/src/factory.cc index 3c76e54..9d172bb 100644 --- a/src/factory.cc +++ b/src/factory.cc @@ -1258,6 +1258,18 @@ Handle Factory::NewFunctionWithoutPrototype(Handle name, } +Handle Factory::NewIteratorResultObject(Handle value, + bool done) { + Handle map(isolate()->native_context()->iterator_result_map()); + Handle result = NewJSObjectFromMap(map, NOT_TENURED, false); + result->InObjectPropertyAtPut( + JSGeneratorObject::kResultValuePropertyIndex, *value); + result->InObjectPropertyAtPut( + JSGeneratorObject::kResultDonePropertyIndex, *ToBoolean(done)); + return result; +} + + Handle Factory::NewScopeInfo(int length) { Handle array = NewFixedArray(length, TENURED); array->set_map_no_write_barrier(*scope_info_map()); @@ -2103,4 +2115,5 @@ Handle Factory::ToBoolean(bool value) { return value ? true_value() : false_value(); } + } } // namespace v8::internal diff --git a/src/factory.h b/src/factory.h index 241a19a..1b992c8 100644 --- a/src/factory.h +++ b/src/factory.h @@ -492,6 +492,8 @@ class Factory V8_FINAL { Handle NewEvalError(const char* message, Vector< Handle > args); + Handle NewIteratorResultObject(Handle value, bool done); + Handle NumberToString(Handle number, bool check_number_string_cache = true); Handle Uint32ToString(uint32_t value); diff --git a/src/ia32/full-codegen-ia32.cc b/src/ia32/full-codegen-ia32.cc index 3eacdd5..fbd9a21 100644 --- a/src/ia32/full-codegen-ia32.cc +++ b/src/ia32/full-codegen-ia32.cc @@ -2227,7 +2227,7 @@ void FullCodeGenerator::EmitCreateIteratorResult(bool done) { Label gc_required; Label allocated; - Handle map(isolate()->native_context()->generator_result_map()); + Handle map(isolate()->native_context()->iterator_result_map()); __ Allocate(map->instance_size(), eax, ecx, edx, &gc_required, TAG_OBJECT); __ jmp(&allocated); diff --git a/src/macros.py b/src/macros.py index 0b69e6b..2a7dbdd 100644 --- a/src/macros.py +++ b/src/macros.py @@ -272,3 +272,8 @@ const PROPERTY_ATTRIBUTES_NONE = 0; const PROPERTY_ATTRIBUTES_STRING = 8; const PROPERTY_ATTRIBUTES_SYMBOLIC = 16; const PROPERTY_ATTRIBUTES_PRIVATE_SYMBOL = 32; + +# Use for keys, values and entries iterators. +const ITERATOR_KIND_KEYS = 1; +const ITERATOR_KIND_VALUES = 2; +const ITERATOR_KIND_ENTRIES = 3; diff --git a/src/mips/full-codegen-mips.cc b/src/mips/full-codegen-mips.cc index ef6bc84..1466af6 100644 --- a/src/mips/full-codegen-mips.cc +++ b/src/mips/full-codegen-mips.cc @@ -2285,7 +2285,7 @@ void FullCodeGenerator::EmitCreateIteratorResult(bool done) { Label gc_required; Label allocated; - Handle map(isolate()->native_context()->generator_result_map()); + Handle map(isolate()->native_context()->iterator_result_map()); __ Allocate(map->instance_size(), v0, a2, a3, &gc_required, TAG_OBJECT); __ jmp(&allocated); diff --git a/src/objects-debug.cc b/src/objects-debug.cc index 2ff7058..6a9b230 100644 --- a/src/objects-debug.cc +++ b/src/objects-debug.cc @@ -170,6 +170,12 @@ void HeapObject::HeapObjectVerify() { case JS_MAP_TYPE: JSMap::cast(this)->JSMapVerify(); break; + case JS_SET_ITERATOR_TYPE: + JSSetIterator::cast(this)->JSSetIteratorVerify(); + break; + case JS_MAP_ITERATOR_TYPE: + JSMapIterator::cast(this)->JSMapIteratorVerify(); + break; case JS_WEAK_MAP_TYPE: JSWeakMap::cast(this)->JSWeakMapVerify(); break; @@ -711,6 +717,7 @@ void JSSet::JSSetVerify() { JSObjectVerify(); VerifyHeapPointer(table()); CHECK(table()->IsOrderedHashTable() || table()->IsUndefined()); + // TODO(arv): Verify OrderedHashTable too. } @@ -719,6 +726,39 @@ void JSMap::JSMapVerify() { JSObjectVerify(); VerifyHeapPointer(table()); CHECK(table()->IsOrderedHashTable() || table()->IsUndefined()); + // TODO(arv): Verify OrderedHashTable too. +} + + +void JSSetIterator::JSSetIteratorVerify() { + CHECK(IsJSSetIterator()); + JSObjectVerify(); + VerifyHeapPointer(table()); + CHECK(table()->IsOrderedHashTable() || table()->IsUndefined()); + CHECK(index()->IsSmi()); + CHECK(count()->IsSmi()); + CHECK(kind()->IsSmi()); + VerifyHeapPointer(next_iterator()); + CHECK(next_iterator()->IsJSSetIterator() || next_iterator()->IsUndefined()); + VerifyHeapPointer(table()); + CHECK(previous_iterator()->IsJSSetIterator() + || previous_iterator()->IsUndefined()); +} + + +void JSMapIterator::JSMapIteratorVerify() { + CHECK(IsJSMapIterator()); + JSObjectVerify(); + VerifyHeapPointer(table()); + CHECK(table()->IsOrderedHashTable() || table()->IsUndefined()); + CHECK(index()->IsSmi()); + CHECK(count()->IsSmi()); + CHECK(kind()->IsSmi()); + VerifyHeapPointer(next_iterator()); + CHECK(next_iterator()->IsJSMapIterator() || next_iterator()->IsUndefined()); + VerifyHeapPointer(table()); + CHECK(previous_iterator()->IsJSMapIterator() + || previous_iterator()->IsUndefined()); } diff --git a/src/objects-inl.h b/src/objects-inl.h index e4e1b59..15a2b08 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -713,6 +713,8 @@ bool Object::IsJSProxy() { TYPE_CHECKER(JSFunctionProxy, JS_FUNCTION_PROXY_TYPE) TYPE_CHECKER(JSSet, JS_SET_TYPE) TYPE_CHECKER(JSMap, JS_MAP_TYPE) +TYPE_CHECKER(JSSetIterator, JS_SET_ITERATOR_TYPE) +TYPE_CHECKER(JSMapIterator, JS_MAP_ITERATOR_TYPE) TYPE_CHECKER(JSWeakMap, JS_WEAK_MAP_TYPE) TYPE_CHECKER(JSWeakSet, JS_WEAK_SET_TYPE) TYPE_CHECKER(JSContextExtensionObject, JS_CONTEXT_EXTENSION_OBJECT_TYPE) @@ -1925,6 +1927,10 @@ int JSObject::GetHeaderSize() { return JSSet::kSize; case JS_MAP_TYPE: return JSMap::kSize; + case JS_SET_ITERATOR_TYPE: + return JSSetIterator::kSize; + case JS_MAP_ITERATOR_TYPE: + return JSMapIterator::kSize; case JS_WEAK_MAP_TYPE: return JSWeakMap::kSize; case JS_WEAK_SET_TYPE: @@ -2993,6 +2999,8 @@ CAST_ACCESSOR(JSProxy) CAST_ACCESSOR(JSFunctionProxy) CAST_ACCESSOR(JSSet) CAST_ACCESSOR(JSMap) +CAST_ACCESSOR(JSSetIterator) +CAST_ACCESSOR(JSMapIterator) CAST_ACCESSOR(JSWeakMap) CAST_ACCESSOR(JSWeakSet) CAST_ACCESSOR(Foreign) @@ -5920,6 +5928,32 @@ void JSProxy::InitializeBody(int object_size, Object* value) { ACCESSORS(JSSet, table, Object, kTableOffset) ACCESSORS(JSMap, table, Object, kTableOffset) + + +#define ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(name, type, offset) \ + template \ + type* OrderedHashTableIterator::name() { \ + return type::cast(READ_FIELD(this, offset)); \ + } \ + template \ + void OrderedHashTableIterator::set_##name( \ + type* value, WriteBarrierMode mode) { \ + WRITE_FIELD(this, offset, value); \ + CONDITIONAL_WRITE_BARRIER(GetHeap(), this, offset, value, mode); \ + } + +ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(table, Object, kTableOffset) +ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(index, Smi, kIndexOffset) +ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(count, Smi, kCountOffset) +ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(kind, Smi, kKindOffset) +ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(next_iterator, Object, + kNextIteratorOffset) +ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(previous_iterator, Object, + kPreviousIteratorOffset) + +#undef ORDERED_HASH_TABLE_ITERATOR_ACCESSORS + + ACCESSORS(JSWeakCollection, table, Object, kTableOffset) ACCESSORS(JSWeakCollection, next, Object, kNextOffset) diff --git a/src/objects-printer.cc b/src/objects-printer.cc index a59b1e9..ea57b1a 100644 --- a/src/objects-printer.cc +++ b/src/objects-printer.cc @@ -174,6 +174,12 @@ void HeapObject::HeapObjectPrint(FILE* out) { case JS_MAP_TYPE: JSMap::cast(this)->JSMapPrint(out); break; + case JS_SET_ITERATOR_TYPE: + JSSetIterator::cast(this)->JSSetIteratorPrint(out); + break; + case JS_MAP_ITERATOR_TYPE: + JSMapIterator::cast(this)->JSMapIteratorPrint(out); + break; case JS_WEAK_MAP_TYPE: JSWeakMap::cast(this)->JSWeakMapPrint(out); break; @@ -722,7 +728,7 @@ void JSProxy::JSProxyPrint(FILE* out) { PrintF(out, " - map = %p\n", reinterpret_cast(map())); PrintF(out, " - handler = "); handler()->Print(out); - PrintF(out, " - hash = "); + PrintF(out, "\n - hash = "); hash()->Print(out); PrintF(out, "\n"); } @@ -733,9 +739,9 @@ void JSFunctionProxy::JSFunctionProxyPrint(FILE* out) { PrintF(out, " - map = %p\n", reinterpret_cast(map())); PrintF(out, " - handler = "); handler()->Print(out); - PrintF(out, " - call_trap = "); + PrintF(out, "\n - call_trap = "); call_trap()->Print(out); - PrintF(out, " - construct_trap = "); + PrintF(out, "\n - construct_trap = "); construct_trap()->Print(out); PrintF(out, "\n"); } @@ -759,6 +765,38 @@ void JSMap::JSMapPrint(FILE* out) { } +template +void OrderedHashTableIterator:: + OrderedHashTableIteratorPrint(FILE* out) { + PrintF(out, " - map = %p\n", reinterpret_cast(map())); + PrintF(out, " - table = "); + table()->ShortPrint(out); + PrintF(out, "\n - index = "); + index()->ShortPrint(out); + PrintF(out, "\n - count = "); + count()->ShortPrint(out); + PrintF(out, "\n - kind = "); + kind()->ShortPrint(out); + PrintF(out, "\n - next_iterator = "); + next_iterator()->ShortPrint(out); + PrintF(out, "\n - previous_iterator = "); + previous_iterator()->ShortPrint(out); + PrintF(out, "\n"); +} + + +void JSSetIterator::JSSetIteratorPrint(FILE* out) { + HeapObject::PrintHeader(out, "JSSetIterator"); + OrderedHashTableIteratorPrint(out); +} + + +void JSMapIterator::JSMapIteratorPrint(FILE* out) { + HeapObject::PrintHeader(out, "JSMapIterator"); + OrderedHashTableIteratorPrint(out); +} + + void JSWeakMap::JSWeakMapPrint(FILE* out) { HeapObject::PrintHeader(out, "JSWeakMap"); PrintF(out, " - map = %p\n", reinterpret_cast(map())); diff --git a/src/objects-visiting.cc b/src/objects-visiting.cc index b314a47..89de85c 100644 --- a/src/objects-visiting.cc +++ b/src/objects-visiting.cc @@ -163,6 +163,8 @@ StaticVisitorBase::VisitorId StaticVisitorBase::GetVisitorId( case JS_GLOBAL_OBJECT_TYPE: case JS_BUILTINS_OBJECT_TYPE: case JS_MESSAGE_OBJECT_TYPE: + case JS_SET_ITERATOR_TYPE: + case JS_MAP_ITERATOR_TYPE: return GetVisitorIdForSize(kVisitJSObject, kVisitJSObjectGeneric, instance_size); diff --git a/src/objects.cc b/src/objects.cc index 9cca2ca..f620b94 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -1674,6 +1674,8 @@ void HeapObject::IterateBody(InstanceType type, int object_size, case JS_DATA_VIEW_TYPE: case JS_SET_TYPE: case JS_MAP_TYPE: + case JS_SET_ITERATOR_TYPE: + case JS_MAP_ITERATOR_TYPE: case JS_WEAK_MAP_TYPE: case JS_WEAK_SET_TYPE: case JS_REGEXP_TYPE: @@ -15819,15 +15821,14 @@ void WeakHashTable::AddEntry(int entry, Object* key, Object* value) { } -template -Handle OrderedHashTable::Allocate( +template +Handle OrderedHashTable::Allocate( Isolate* isolate, int capacity, PretenureFlag pretenure) { // Capacity must be a power of two, since we depend on being able // to divide and multiple by 2 (kLoadFactor) to derive capacity // from number of buckets. If we decide to change kLoadFactor // to something other than 2, capacity should be stored as another // field of this object. - const int kMinCapacity = 4; capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity)); if (capacity > kMaxCapacity) { v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true); @@ -15844,12 +15845,13 @@ Handle OrderedHashTable::Allocate( table->SetNumberOfBuckets(num_buckets); table->SetNumberOfElements(0); table->SetNumberOfDeletedElements(0); + table->set_iterators(isolate->heap()->undefined_value()); return table; } -template -Handle OrderedHashTable::EnsureGrowable( +template +Handle OrderedHashTable::EnsureGrowable( Handle table) { int nof = table->NumberOfElements(); int nod = table->NumberOfDeletedElements(); @@ -15862,8 +15864,8 @@ Handle OrderedHashTable::EnsureGrowable( } -template -Handle OrderedHashTable::Shrink( +template +Handle OrderedHashTable::Shrink( Handle table) { int nof = table->NumberOfElements(); int capacity = table->Capacity(); @@ -15872,8 +15874,31 @@ Handle OrderedHashTable::Shrink( } -template -Handle OrderedHashTable::Rehash( +template +Handle OrderedHashTable::Clear( + Handle table) { + Handle new_table = + Allocate(table->GetIsolate(), + kMinCapacity, + table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED); + + new_table->set_iterators(table->iterators()); + table->set_iterators(table->GetHeap()->undefined_value()); + + DisallowHeapAllocation no_allocation; + for (Object* object = new_table->iterators(); + !object->IsUndefined(); + object = Iterator::cast(object)->next_iterator()) { + Iterator::cast(object)->TableCleared(); + Iterator::cast(object)->set_table(*new_table); + } + + return new_table; +} + + +template +Handle OrderedHashTable::Rehash( Handle table, int new_capacity) { Handle new_table = Allocate(table->GetIsolate(), @@ -15900,12 +15925,24 @@ Handle OrderedHashTable::Rehash( ++new_entry; } new_table->SetNumberOfElements(nof); + + new_table->set_iterators(table->iterators()); + table->set_iterators(table->GetHeap()->undefined_value()); + + DisallowHeapAllocation no_allocation; + for (Object* object = new_table->iterators(); + !object->IsUndefined(); + object = Iterator::cast(object)->next_iterator()) { + Iterator::cast(object)->TableCompacted(); + Iterator::cast(object)->set_table(*new_table); + } + return new_table; } -template -int OrderedHashTable::FindEntry(Object* key) { +template +int OrderedHashTable::FindEntry(Object* key) { ASSERT(!key->IsTheHole()); Object* hash = key->GetHash(); if (hash->IsUndefined()) return kNotFound; @@ -15920,9 +15957,9 @@ int OrderedHashTable::FindEntry(Object* key) { } -template -int OrderedHashTable::AddEntry(int hash) { - int entry = NumberOfElements() + NumberOfDeletedElements(); +template +int OrderedHashTable::AddEntry(int hash) { + int entry = UsedCapacity(); int bucket = HashToBucket(hash); int index = EntryToIndex(entry); Object* chain_entry = get(kHashTableStartIndex + bucket); @@ -15933,19 +15970,26 @@ int OrderedHashTable::AddEntry(int hash) { } -template -void OrderedHashTable::RemoveEntry(int entry) { +template +void OrderedHashTable::RemoveEntry(int entry) { int index = EntryToIndex(entry); for (int i = 0; i < entrysize; ++i) { set_the_hole(index + i); } SetNumberOfElements(NumberOfElements() - 1); SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); + + DisallowHeapAllocation no_allocation; + for (Object* object = iterators(); + !object->IsUndefined(); + object = Iterator::cast(object)->next_iterator()) { + Iterator::cast(object)->EntryRemoved(entry); + } } -template class OrderedHashTable; -template class OrderedHashTable; +template class OrderedHashTable; +template class OrderedHashTable; bool OrderedHashSet::Contains(Object* key) { @@ -15971,7 +16015,6 @@ Handle OrderedHashSet::Remove(Handle table, int entry = table->FindEntry(*key); if (entry == kNotFound) return table; table->RemoveEntry(entry); - // TODO(adamk): Don't shrink if we're being iterated over return Shrink(table); } @@ -15991,7 +16034,6 @@ Handle OrderedHashMap::Put(Handle table, if (value->IsTheHole()) { if (entry == kNotFound) return table; table->RemoveEntry(entry); - // TODO(adamk): Only shrink if not iterating return Shrink(table); } @@ -16010,6 +16052,206 @@ Handle OrderedHashMap::Put(Handle table, } +template +void OrderedHashTableIterator::EntryRemoved(int index) { + int i = this->index()->value(); + if (index < i) { + set_count(Smi::FromInt(count()->value() - 1)); + } + if (index == i) { + Seek(); + } +} + + +template +void OrderedHashTableIterator::Close() { + if (Closed()) return; + + DisallowHeapAllocation no_allocation; + + Object* undefined = GetHeap()->undefined_value(); + TableType* table = TableType::cast(this->table()); + Object* previous = previous_iterator(); + Object* next = next_iterator(); + + if (previous == undefined) { + ASSERT_EQ(table->iterators(), this); + table->set_iterators(next); + } else { + ASSERT_EQ(Derived::cast(previous)->next_iterator(), this); + Derived::cast(previous)->set_next_iterator(next); + } + + if (!next->IsUndefined()) { + ASSERT_EQ(Derived::cast(next)->previous_iterator(), this); + Derived::cast(next)->set_previous_iterator(previous); + } + + set_previous_iterator(undefined); + set_next_iterator(undefined); + set_table(undefined); +} + + +template +void OrderedHashTableIterator::Seek() { + ASSERT(!Closed()); + + DisallowHeapAllocation no_allocation; + + int index = this->index()->value(); + + TableType* table = TableType::cast(this->table()); + int used_capacity = table->UsedCapacity(); + + while (index < used_capacity && table->KeyAt(index)->IsTheHole()) { + index++; + } + set_index(Smi::FromInt(index)); +} + + +template +void OrderedHashTableIterator::MoveNext() { + ASSERT(!Closed()); + + set_index(Smi::FromInt(index()->value() + 1)); + set_count(Smi::FromInt(count()->value() + 1)); + Seek(); +} + + +template +Handle OrderedHashTableIterator::Next( + Handle iterator) { + Isolate* isolate = iterator->GetIsolate(); + Factory* factory = isolate->factory(); + + Handle object(iterator->table(), isolate); + + if (!object->IsUndefined()) { + Handle table = Handle::cast(object); + int index = iterator->index()->value(); + if (index < table->UsedCapacity()) { + int entry_index = table->EntryToIndex(index); + iterator->MoveNext(); + Handle value = Derived::ValueForKind(iterator, entry_index); + return factory->NewIteratorResultObject(value, false); + } else { + iterator->Close(); + } + } + + return factory->NewIteratorResultObject(factory->undefined_value(), true); +} + + +template +Handle OrderedHashTableIterator::CreateInternal( + Handle map, + Handle table, + int kind) { + Isolate* isolate = table->GetIsolate(); + + Handle undefined = isolate->factory()->undefined_value(); + + Handle new_iterator = Handle::cast( + isolate->factory()->NewJSObjectFromMap(map)); + new_iterator->set_previous_iterator(*undefined); + new_iterator->set_table(*table); + new_iterator->set_index(Smi::FromInt(0)); + new_iterator->set_count(Smi::FromInt(0)); + new_iterator->set_kind(Smi::FromInt(kind)); + + Handle old_iterator(table->iterators(), isolate); + if (!old_iterator->IsUndefined()) { + Handle::cast(old_iterator)->set_previous_iterator(*new_iterator); + new_iterator->set_next_iterator(*old_iterator); + } else { + new_iterator->set_next_iterator(*undefined); + } + + table->set_iterators(*new_iterator); + + return new_iterator; +} + + +template class OrderedHashTableIterator; +template class OrderedHashTableIterator; + + +Handle JSSetIterator::Create( + Handle table, int kind) { + return CreateInternal(table->GetIsolate()->set_iterator_map(), table, kind); +} + + +Handle JSSetIterator::ValueForKind( + Handle iterator, int entry_index) { + int kind = iterator->kind()->value(); + // Set.prototype only has values and entries. + ASSERT(kind == kKindValues || kind == kKindEntries); + + Isolate* isolate = iterator->GetIsolate(); + Factory* factory = isolate->factory(); + + Handle table( + OrderedHashSet::cast(iterator->table()), isolate); + Handle value = Handle(table->get(entry_index), isolate); + + if (kind == kKindEntries) { + Handle array = factory->NewFixedArray(2); + array->set(0, *value); + array->set(1, *value); + return factory->NewJSArrayWithElements(array); + } + + return value; +} + + +Handle JSMapIterator::Create( + Handle table, + int kind) { + return CreateInternal(table->GetIsolate()->map_iterator_map(), table, kind); +} + + +Handle JSMapIterator::ValueForKind( + Handle iterator, int entry_index) { + int kind = iterator->kind()->value(); + ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries); + + Isolate* isolate = iterator->GetIsolate(); + Factory* factory = isolate->factory(); + + Handle table( + OrderedHashMap::cast(iterator->table()), isolate); + + switch (kind) { + case kKindKeys: + return Handle(table->get(entry_index), isolate); + + case kKindValues: + return Handle(table->get(entry_index + 1), isolate); + + case kKindEntries: { + Handle key(table->get(entry_index), isolate); + Handle value(table->get(entry_index + 1), isolate); + Handle array = factory->NewFixedArray(2); + array->set(0, *key); + array->set(1, *value); + return factory->NewJSArrayWithElements(array); + } + } + + UNREACHABLE(); + return factory->undefined_value(); +} + + DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( DeclaredAccessorDescriptor* descriptor) : array_(descriptor->serialized_data()->GetDataStartAddress()), diff --git a/src/objects.h b/src/objects.h index 4ba0d71..fe8f55b 100644 --- a/src/objects.h +++ b/src/objects.h @@ -66,6 +66,8 @@ // - JSDataView // - JSSet // - JSMap +// - JSSetIterator +// - JSMapIterator // - JSWeakCollection // - JSWeakMap // - JSWeakSet @@ -445,6 +447,8 @@ const int kStubMinorKeyBits = kBitsPerInt - kSmiTagSize - kStubMajorKeyBits; V(JS_PROXY_TYPE) \ V(JS_SET_TYPE) \ V(JS_MAP_TYPE) \ + V(JS_SET_ITERATOR_TYPE) \ + V(JS_MAP_ITERATOR_TYPE) \ V(JS_WEAK_MAP_TYPE) \ V(JS_WEAK_SET_TYPE) \ V(JS_REGEXP_TYPE) \ @@ -793,6 +797,8 @@ enum InstanceType { JS_DATA_VIEW_TYPE, JS_SET_TYPE, JS_MAP_TYPE, + JS_SET_ITERATOR_TYPE, + JS_MAP_ITERATOR_TYPE, JS_WEAK_MAP_TYPE, JS_WEAK_SET_TYPE, @@ -1053,6 +1059,8 @@ class MaybeObject BASE_EMBEDDED { V(JSFunctionProxy) \ V(JSSet) \ V(JSMap) \ + V(JSSetIterator) \ + V(JSMapIterator) \ V(JSWeakCollection) \ V(JSWeakMap) \ V(JSWeakSet) \ @@ -4315,16 +4323,17 @@ class ObjectHashTable: public HashTable +template class OrderedHashTable: public FixedArray { public: // Returns an OrderedHashTable with a capacity of at least |capacity|. @@ -4339,6 +4348,10 @@ class OrderedHashTable: public FixedArray { // if possible. static Handle Shrink(Handle table); + // Returns a new empty OrderedHashTable and updates all the iterators to + // point to the new table. + static Handle Clear(Handle table); + // Returns kNotFound if the key isn't present. int FindEntry(Object* key); @@ -4350,10 +4363,16 @@ class OrderedHashTable: public FixedArray { return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); } + int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } + int NumberOfBuckets() { return Smi::cast(get(kNumberOfBucketsIndex))->value(); } + Object* iterators() { return get(kIteratorsIndex); } + + void set_iterators(Object* value) { set(kIteratorsIndex, value); } + // Returns the index into the data table where the new entry // should be placed. The table is assumed to have enough space // for a new entry. @@ -4368,7 +4387,10 @@ class OrderedHashTable: public FixedArray { return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); } + Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } + static const int kNotFound = -1; + static const int kMinCapacity = 4; private: static Handle Rehash(Handle table, int new_capacity); @@ -4389,8 +4411,6 @@ class OrderedHashTable: public FixedArray { return NumberOfBuckets() * kLoadFactor; } - Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } - // Returns the next entry for the given entry. int ChainAt(int entry) { return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value(); @@ -4408,7 +4428,8 @@ class OrderedHashTable: public FixedArray { static const int kNumberOfBucketsIndex = 0; static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1; static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1; - static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex + 1; + static const int kIteratorsIndex = kNumberOfDeletedElementsIndex + 1; + static const int kHashTableStartIndex = kIteratorsIndex + 1; static const int kEntrySize = entrysize + 1; static const int kChainOffset = entrysize; @@ -4420,7 +4441,11 @@ class OrderedHashTable: public FixedArray { }; -class OrderedHashSet: public OrderedHashTable { +class JSSetIterator; + + +class OrderedHashSet: public OrderedHashTable< + OrderedHashSet, JSSetIterator, 1> { public: static OrderedHashSet* cast(Object* obj) { ASSERT(obj->IsOrderedHashTable()); @@ -4435,7 +4460,11 @@ class OrderedHashSet: public OrderedHashTable { }; -class OrderedHashMap: public OrderedHashTable { +class JSMapIterator; + + +class OrderedHashMap:public OrderedHashTable< + OrderedHashMap, JSMapIterator, 2> { public: static OrderedHashMap* cast(Object* obj) { ASSERT(obj->IsOrderedHashTable()); @@ -7574,7 +7603,7 @@ class JSGeneratorObject: public JSObject { enum ResumeMode { NEXT, THROW }; // Yielding from a generator returns an object with the following inobject - // properties. See Context::generator_result_map() for the map. + // properties. See Context::iterator_result_map() for the map. static const int kResultValuePropertyIndex = 0; static const int kResultDonePropertyIndex = 1; static const int kResultPropertyCount = 2; @@ -10045,6 +10074,145 @@ class JSMap: public JSObject { }; +// OrderedHashTableIterator is an iterator that iterates over the keys and +// values of an OrderedHashTable. +// +// The hash table has a reference to the iterator and the iterators themselves +// have references to the [next_iterator] and [previous_iterator], thus creating +// a double linked list. +// +// When the hash table changes the iterators are called to update their [index] +// and [count]. The hash table calls [EntryRemoved], [TableCompacted] as well +// as [TableCleared]. +// +// When an iterator is done it closes itself. It removes itself from the double +// linked list and it sets its [table] to undefined, no longer keeping the +// [table] alive. +template +class OrderedHashTableIterator: public JSObject { + public: + // [table]: the backing hash table mapping keys to values. + DECL_ACCESSORS(table, Object) + + // [index]: The index into the data table. + DECL_ACCESSORS(index, Smi) + + // [count]: The logical index into the data table, ignoring the holes. + DECL_ACCESSORS(count, Smi) + + // [kind]: The kind of iteration this is. One of the [Kind] enum values. + DECL_ACCESSORS(kind, Smi) + + // [next_iterator]: Used as a double linked list for the live iterators. + DECL_ACCESSORS(next_iterator, Object) + + // [previous_iterator]: Used as a double linked list for the live iterators. + DECL_ACCESSORS(previous_iterator, Object) + + void OrderedHashTableIteratorPrint(FILE* out); + + static const int kTableOffset = JSObject::kHeaderSize; + static const int kIndexOffset = kTableOffset + kPointerSize; + static const int kCountOffset = kIndexOffset + kPointerSize; + static const int kKindOffset = kCountOffset + kPointerSize; + static const int kNextIteratorOffset = kKindOffset + kPointerSize; + static const int kPreviousIteratorOffset = kNextIteratorOffset + kPointerSize; + static const int kSize = kPreviousIteratorOffset + kPointerSize; + + enum Kind { + kKindKeys = 1, + kKindValues = 2, + kKindEntries = 3 + }; + + // Called by the underlying [table] when an entry is removed. + void EntryRemoved(int index); + + // Called by the underlying [table] when it is compacted/rehashed. + void TableCompacted() { + // All holes have been removed so index is now same as count. + set_index(count()); + } + + // Called by the underlying [table] when it is cleared. + void TableCleared() { + set_index(Smi::FromInt(0)); + set_count(Smi::FromInt(0)); + } + + // Removes the iterator from the double linked list and removes its reference + // back to the [table]. + void Close(); + + // Returns an iterator result object: {value: any, done: boolean} and moves + // the index to the next valid entry. Closes the iterator if moving past the + // end. + static Handle Next(Handle iterator); + + protected: + static Handle CreateInternal( + Handle map, Handle table, int kind); + + private: + // Ensures [index] is not pointing to a hole. + void Seek(); + + // Moves [index] to next valid entry. Closes the iterator if moving past the + // end. + void MoveNext(); + + bool Closed() { + return table()->IsUndefined(); + } + + DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator); +}; + + +class JSSetIterator: public OrderedHashTableIterator { + public: + // Creates a new iterator associated with [table]. + // [kind] needs to be one of the OrderedHashTableIterator Kind enum values. + static Handle Create(Handle table, int kind); + + // Dispatched behavior. + DECLARE_PRINTER(JSSetIterator) + DECLARE_VERIFIER(JSSetIterator) + + // Casting. + static inline JSSetIterator* cast(Object* obj); + + static Handle ValueForKind( + Handle iterator, int entry_index); + + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator); +}; + + +class JSMapIterator: public OrderedHashTableIterator { + public: + // Creates a new iterator associated with [table]. + // [kind] needs to be one of the OrderedHashTableIterator Kind enum values. + static Handle Create(Handle table, int kind); + + // Dispatched behavior. + DECLARE_PRINTER(JSMapIterator) + DECLARE_VERIFIER(JSMapIterator) + + // Casting. + static inline JSMapIterator* cast(Object* obj); + + static Handle ValueForKind( + Handle iterator, int entry_index); + + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator); +}; + + // Base class for both JSWeakMap and JSWeakSet class JSWeakCollection: public JSObject { public: diff --git a/src/runtime.cc b/src/runtime.cc index 5cd4806..a287ec6 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -1552,6 +1552,17 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_SetDelete) { } +RUNTIME_FUNCTION(MaybeObject*, Runtime_SetClear) { + HandleScope scope(isolate); + ASSERT(args.length() == 1); + CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0); + Handle table(OrderedHashSet::cast(holder->table())); + table = OrderedHashSet::Clear(table); + holder->set_table(*table); + return isolate->heap()->undefined_value(); +} + + RUNTIME_FUNCTION(MaybeObject*, Runtime_SetGetSize) { HandleScope scope(isolate); ASSERT(args.length() == 1); @@ -1561,6 +1572,37 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_SetGetSize) { } +RUNTIME_FUNCTION(MaybeObject*, Runtime_SetCreateIterator) { + HandleScope scope(isolate); + ASSERT(args.length() == 2); + CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0); + CONVERT_SMI_ARG_CHECKED(kind, 1) + ASSERT(kind == JSSetIterator::kKindValues + || kind == JSSetIterator::kKindEntries); + Handle table(OrderedHashSet::cast(holder->table())); + Handle iterator = JSSetIterator::Create(table, kind); + return *iterator; +} + + +RUNTIME_FUNCTION(MaybeObject*, Runtime_SetIteratorNext) { + HandleScope scope(isolate); + ASSERT(args.length() == 1); + CONVERT_ARG_HANDLE_CHECKED(JSSetIterator, holder, 0); + Handle result = JSSetIterator::Next(holder); + return *result; +} + + +RUNTIME_FUNCTION(MaybeObject*, Runtime_SetIteratorClose) { + HandleScope scope(isolate); + ASSERT(args.length() == 1); + CONVERT_ARG_HANDLE_CHECKED(JSSetIterator, holder, 0); + holder->Close(); + return isolate->heap()->undefined_value(); +} + + RUNTIME_FUNCTION(MaybeObject*, Runtime_MapInitialize) { HandleScope scope(isolate); ASSERT(args.length() == 1); @@ -1607,6 +1649,17 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_MapDelete) { } +RUNTIME_FUNCTION(MaybeObject*, Runtime_MapClear) { + HandleScope scope(isolate); + ASSERT(args.length() == 1); + CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0); + Handle table(OrderedHashMap::cast(holder->table())); + table = OrderedHashMap::Clear(table); + holder->set_table(*table); + return isolate->heap()->undefined_value(); +} + + RUNTIME_FUNCTION(MaybeObject*, Runtime_MapSet) { HandleScope scope(isolate); ASSERT(args.length() == 3); @@ -1629,6 +1682,38 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_MapGetSize) { } +RUNTIME_FUNCTION(MaybeObject*, Runtime_MapCreateIterator) { + HandleScope scope(isolate); + ASSERT(args.length() == 2); + CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0); + CONVERT_SMI_ARG_CHECKED(kind, 1) + ASSERT(kind == JSMapIterator::kKindKeys + || kind == JSMapIterator::kKindValues + || kind == JSMapIterator::kKindEntries); + Handle table(OrderedHashMap::cast(holder->table())); + Handle iterator = JSMapIterator::Create(table, kind); + return *iterator; +} + + +RUNTIME_FUNCTION(MaybeObject*, Runtime_MapIteratorNext) { + HandleScope scope(isolate); + ASSERT(args.length() == 1); + CONVERT_ARG_HANDLE_CHECKED(JSMapIterator, holder, 0); + Handle result = JSMapIterator::Next(holder); + return *result; +} + + +RUNTIME_FUNCTION(MaybeObject*, Runtime_MapIteratorClose) { + HandleScope scope(isolate); + ASSERT(args.length() == 1); + CONVERT_ARG_HANDLE_CHECKED(JSMapIterator, holder, 0); + holder->Close(); + return isolate->heap()->undefined_value(); +} + + static JSWeakCollection* WeakCollectionInitialize(Isolate* isolate, Handle weak_collection) { ASSERT(weak_collection->map()->inobject_properties() == 0); diff --git a/src/runtime.h b/src/runtime.h index 5b92b12..a32db2c 100644 --- a/src/runtime.h +++ b/src/runtime.h @@ -297,15 +297,25 @@ namespace internal { F(SetAdd, 2, 1) \ F(SetHas, 2, 1) \ F(SetDelete, 2, 1) \ + F(SetClear, 1, 1) \ F(SetGetSize, 1, 1) \ + F(SetCreateIterator, 2, 1) \ + \ + F(SetIteratorNext, 1, 1) \ + F(SetIteratorClose, 1, 1) \ \ /* Harmony maps */ \ F(MapInitialize, 1, 1) \ F(MapGet, 2, 1) \ F(MapHas, 2, 1) \ F(MapDelete, 2, 1) \ + F(MapClear, 1, 1) \ F(MapSet, 3, 1) \ F(MapGetSize, 1, 1) \ + F(MapCreateIterator, 2, 1) \ + \ + F(MapIteratorNext, 1, 1) \ + F(MapIteratorClose, 1, 1) \ \ /* Harmony weak maps and sets */ \ F(WeakCollectionInitialize, 1, 1) \ diff --git a/src/x64/full-codegen-x64.cc b/src/x64/full-codegen-x64.cc index 4ebef21..4a6d125 100644 --- a/src/x64/full-codegen-x64.cc +++ b/src/x64/full-codegen-x64.cc @@ -2256,7 +2256,7 @@ void FullCodeGenerator::EmitCreateIteratorResult(bool done) { Label gc_required; Label allocated; - Handle map(isolate()->native_context()->generator_result_map()); + Handle map(isolate()->native_context()->iterator_result_map()); __ Allocate(map->instance_size(), rax, rcx, rdx, &gc_required, TAG_OBJECT); __ jmp(&allocated); diff --git a/test/cctest/test-ordered-hash-table.cc b/test/cctest/test-ordered-hash-table.cc index f6ebc16..f495804 100644 --- a/test/cctest/test-ordered-hash-table.cc +++ b/test/cctest/test-ordered-hash-table.cc @@ -36,7 +36,20 @@ namespace { using namespace v8::internal; + +void CheckIterResultObject(Factory* factory, + Handle result, + Handle value, + bool done) { + CHECK(GetProperty(result, "value").ToHandleChecked()->SameValue(*value)); + CHECK(GetProperty(result, "done").ToHandleChecked()->IsBoolean()); + CHECK_EQ(GetProperty(result, "done").ToHandleChecked()->BooleanValue(), done); +} + + TEST(Set) { + i::FLAG_harmony_collections = true; + LocalContext context; Isolate* isolate = CcTest::i_isolate(); Factory* factory = isolate->factory(); @@ -46,6 +59,11 @@ TEST(Set) { CHECK_EQ(0, ordered_set->NumberOfElements()); CHECK_EQ(0, ordered_set->NumberOfDeletedElements()); + Handle value_iterator = + JSSetIterator::Create(ordered_set, JSSetIterator::kKindValues); + Handle value_iterator_2 = + JSSetIterator::Create(ordered_set, JSSetIterator::kKindValues); + Handle map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize); Handle obj = factory->NewJSObjectFromMap(map); CHECK(!ordered_set->Contains(*obj)); @@ -68,6 +86,18 @@ TEST(Set) { CHECK(ordered_set->Contains(*obj2)); CHECK(ordered_set->Contains(*obj3)); + // Test iteration + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator), obj1, false); + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator), obj2, false); + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator), obj3, false); + CheckIterResultObject(factory, + JSSetIterator::Next(value_iterator), + factory->undefined_value(), + true); + // Test growth ordered_set = OrderedHashSet::Add(ordered_set, obj); Handle obj4 = factory->NewJSObjectFromMap(map); @@ -81,6 +111,22 @@ TEST(Set) { CHECK_EQ(0, ordered_set->NumberOfDeletedElements()); CHECK_EQ(4, ordered_set->NumberOfBuckets()); + // Test iteration after growth + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator_2), obj1, false); + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator_2), obj2, false); + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator_2), obj3, false); + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator_2), obj, false); + CheckIterResultObject( + factory, JSSetIterator::Next(value_iterator_2), obj4, false); + CheckIterResultObject(factory, + JSSetIterator::Next(value_iterator_2), + factory->undefined_value(), + true); + // Test shrinking ordered_set = OrderedHashSet::Remove(ordered_set, obj); ordered_set = OrderedHashSet::Remove(ordered_set, obj1); @@ -92,6 +138,8 @@ TEST(Set) { TEST(Map) { + i::FLAG_harmony_collections = true; + LocalContext context; Isolate* isolate = CcTest::i_isolate(); Factory* factory = isolate->factory(); @@ -101,6 +149,11 @@ TEST(Map) { CHECK_EQ(0, ordered_map->NumberOfElements()); CHECK_EQ(0, ordered_map->NumberOfDeletedElements()); + Handle value_iterator = + JSMapIterator::Create(ordered_map, JSMapIterator::kKindValues); + Handle key_iterator = + JSMapIterator::Create(ordered_map, JSMapIterator::kKindKeys); + Handle map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize); Handle obj = factory->NewJSObjectFromMap(map); Handle val = factory->NewJSObjectFromMap(map); @@ -128,6 +181,18 @@ TEST(Map) { CHECK(ordered_map->Lookup(*obj2)->SameValue(*val2)); CHECK(ordered_map->Lookup(*obj3)->SameValue(*val3)); + // Test iteration + CheckIterResultObject( + factory, JSMapIterator::Next(value_iterator), val1, false); + CheckIterResultObject( + factory, JSMapIterator::Next(value_iterator), val2, false); + CheckIterResultObject( + factory, JSMapIterator::Next(value_iterator), val3, false); + CheckIterResultObject(factory, + JSMapIterator::Next(value_iterator), + factory->undefined_value(), + true); + // Test growth ordered_map = OrderedHashMap::Put(ordered_map, obj, val); Handle obj4 = factory->NewJSObjectFromMap(map); @@ -141,6 +206,22 @@ TEST(Map) { CHECK_EQ(5, ordered_map->NumberOfElements()); CHECK_EQ(4, ordered_map->NumberOfBuckets()); + // Test iteration after growth + CheckIterResultObject( + factory, JSMapIterator::Next(key_iterator), obj1, false); + CheckIterResultObject( + factory, JSMapIterator::Next(key_iterator), obj2, false); + CheckIterResultObject( + factory, JSMapIterator::Next(key_iterator), obj3, false); + CheckIterResultObject( + factory, JSMapIterator::Next(key_iterator), obj, false); + CheckIterResultObject( + factory, JSMapIterator::Next(key_iterator), obj4, false); + CheckIterResultObject(factory, + JSMapIterator::Next(key_iterator), + factory->undefined_value(), + true); + // Test shrinking ordered_map = OrderedHashMap::Put( ordered_map, obj, factory->the_hole_value()); diff --git a/test/mjsunit/harmony/collections.js b/test/mjsunit/harmony/collections.js index b33d080..002adaa 100644 --- a/test/mjsunit/harmony/collections.js +++ b/test/mjsunit/harmony/collections.js @@ -507,3 +507,347 @@ for (var i = 9; i >= 0; i--) { assertEquals('minus', m.get(0)); assertEquals('minus', m.get(-0)); })(); + + +(function TestSetForEachInvalidTypes() { + assertThrows(function() { + Set.prototype.set.forEach.call({}); + }, TypeError); + + var set = new Set(); + assertThrows(function() { + set.forEach({}); + }, TypeError); +})(); + + +(function TestSetForEach() { + var set = new Set(); + set.add('a'); + set.add('b'); + set.add('c'); + + var buffer = ''; + var receiver = {}; + set.forEach(function(v, k, s) { + assertSame(v, k); + assertSame(set, s); + assertSame(this, receiver); + buffer += v; + if (v === 'a') { + set.delete('b'); + set.add('d'); + set.add('e'); + set.add('f'); + } else if (v === 'c') { + set.add('b'); + set.delete('e'); + } + }, receiver); + + assertEquals('acdfb', buffer); +})(); + + +(function TestSetForEachAddAtEnd() { + var set = new Set(); + set.add('a'); + set.add('b'); + + var buffer = ''; + set.forEach(function(v) { + buffer += v; + if (v === 'b') { + set.add('c'); + } + }); + + assertEquals('abc', buffer); +})(); + + +(function TestSetForEachDeleteNext() { + var set = new Set(); + set.add('a'); + set.add('b'); + set.add('c'); + + var buffer = ''; + set.forEach(function(v) { + buffer += v; + if (v === 'b') { + set.delete('c'); + } + }); + + assertEquals('ab', buffer); +})(); + + +(function TestSetForEachDeleteVisitedAndAddAgain() { + var set = new Set(); + set.add('a'); + set.add('b'); + set.add('c'); + + var buffer = ''; + set.forEach(function(v) { + buffer += v; + if (v === 'b') { + set.delete('a'); + } else if (v === 'c') { + set.add('a'); + } + }); + + assertEquals('abca', buffer); +})(); + + +(function TestSetForEachClear() { + var set = new Set(); + set.add('a'); + set.add('b'); + set.add('c'); + + var buffer = ''; + set.forEach(function(v) { + buffer += v; + if (v === 'a') { + set.clear(); + set.add('d'); + set.add('e'); + } + }); + + assertEquals('ade', buffer); +})(); + + +(function TestSetForEachNested() { + var set = new Set(); + set.add('a'); + set.add('b'); + set.add('c'); + + var buffer = ''; + set.forEach(function(v) { + buffer += v; + set.forEach(function(v) { + buffer += v; + if (v === 'a') { + set.delete('b'); + } + }); + }); + + assertEquals('aaccac', buffer); +})(); + + +(function TestSetForEachEarlyExit() { + var set = new Set(); + set.add('a'); + set.add('b'); + set.add('c'); + + var buffer = ''; + var ex = {}; + try { + set.forEach(function(v) { + buffer += v; + throw ex; + }); + } catch (e) { + assertEquals(ex, e); + } + assertEquals('a', buffer); +})(); + + +(function TestSetForEachGC() { + var set = new Set(); + for (var i = 0; i < 100; i++) { + set.add(i); + } + + var accumulated = 0; + set.forEach(function(v) { + accumulated += v; + if (v % 10 === 0) { + gc(); + } + }); + assertEquals(4950, accumulated); +})(); + +(function TestMapForEachInvalidTypes() { + assertThrows(function() { + Map.prototype.map.forEach.call({}); + }, TypeError); + + var map = new Map(); + assertThrows(function() { + map.forEach({}); + }, TypeError); +})(); + + +(function TestMapForEach() { + var map = new Map(); + map.set(0, 'a'); + map.set(1, 'b'); + map.set(2, 'c'); + + var buffer = []; + var receiver = {}; + map.forEach(function(v, k, m) { + assertEquals(map, m); + assertEquals(this, receiver); + buffer.push(k, v); + if (k === 0) { + map.delete(1); + map.set(3, 'd'); + map.set(4, 'e'); + map.set(5, 'f'); + } else if (k === 2) { + map.set(1, 'B'); + map.delete(4); + } + }, receiver); + + assertArrayEquals([0, 'a', 2, 'c', 3, 'd', 5, 'f', 1, 'B'], buffer); +})(); + + +(function TestMapForEachAddAtEnd() { + var map = new Map(); + map.set(0, 'a'); + map.set(1, 'b'); + + var buffer = []; + map.forEach(function(v, k) { + buffer.push(k, v); + if (k === 1) { + map.set(2, 'c'); + } + }); + + assertArrayEquals([0, 'a', 1, 'b', 2, 'c'], buffer); +})(); + + +(function TestMapForEachDeleteNext() { + var map = new Map(); + map.set(0, 'a'); + map.set(1, 'b'); + map.set(2, 'c'); + + var buffer = []; + map.forEach(function(v, k) { + buffer.push(k, v); + if (k === 1) { + map.delete(2); + } + }); + + assertArrayEquals([0, 'a', 1, 'b'], buffer); +})(); + + +(function TestSetForEachDeleteVisitedAndAddAgain() { + var map = new Map(); + map.set(0, 'a'); + map.set(1, 'b'); + map.set(2, 'c'); + + var buffer = []; + map.forEach(function(v, k) { + buffer.push(k, v); + if (k === 1) { + map.delete(0); + } else if (k === 2) { + map.set(0, 'a'); + } + }); + + assertArrayEquals([0, 'a', 1, 'b', 2, 'c', 0, 'a'], buffer); +})(); + + +(function TestMapForEachClear() { + var map = new Map(); + map.set(0, 'a'); + map.set(1, 'b'); + map.set(2, 'c'); + + var buffer = []; + map.forEach(function(v, k) { + buffer.push(k, v); + if (k === 0) { + map.clear(); + map.set(3, 'd'); + map.set(4, 'e'); + } + }); + + assertArrayEquals([0, 'a', 3, 'd', 4, 'e'], buffer); +})(); + + +(function TestMapForEachNested() { + var map = new Map(); + map.set(0, 'a'); + map.set(1, 'b'); + map.set(2, 'c'); + + var buffer = []; + map.forEach(function(v, k) { + buffer.push(k, v); + map.forEach(function(v, k) { + buffer.push(k, v); + if (k === 0) { + map.delete(1); + } + }); + }); + + assertArrayEquals([0, 'a', 0, 'a', 2, 'c', 2, 'c', 0, 'a', 2, 'c'], buffer); +})(); + + +(function TestMapForEachEarlyExit() { + var map = new Map(); + map.set(0, 'a'); + map.set(1, 'b'); + map.set(2, 'c'); + + var buffer = []; + var ex = {}; + try { + map.forEach(function(v, k) { + buffer.push(k, v); + throw ex; + }); + } catch (e) { + assertEquals(ex, e); + } + assertArrayEquals([0, 'a'], buffer); +})(); + + +(function TestMapForEachGC() { + var map = new Map(); + for (var i = 0; i < 100; i++) { + map.set(i, i); + } + + var accumulated = 0; + map.forEach(function(v) { + accumulated += v; + if (v % 10 === 0) { + gc(); + } + }); + assertEquals(4950, accumulated); +})(); -- 2.7.4