Skip to content

Commit 88f8fe1

Browse files
hashseedCommit Bot
hashseed
authored and
Commit Bot
committed
Fix collection iterator preview with deleted entries
We used to assume that we know the remaining entries returned by the iterator based on the current index. However, that is not accurate, since entries skipped by the current index could be deleted. In the new approach, we allocate conservatively and shrink the result. [email protected] Bug: v8:8433 Change-Id: I38a3004dc3af292daabb454bb76f38d65ef437e8 Reviewed-on: https://chromium-review.googlesource.com/c/1325966 Commit-Queue: Yang Guo <[email protected]> Reviewed-by: Georg Neis <[email protected]> Cr-Commit-Position: refs/heads/master@{#57360}
1 parent b208c45 commit 88f8fe1

File tree

2 files changed

+241
-25
lines changed

2 files changed

+241
-25
lines changed

‎src/api.cc‎

Lines changed: 27 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -7019,30 +7019,30 @@ i::Handle<i::JSArray> MapAsArray(i::Isolate* isolate, i::Object* table_obj,
70197019
i::Factory* factory = isolate->factory();
70207020
i::Handle<i::OrderedHashMap> table(i::OrderedHashMap::cast(table_obj),
70217021
isolate);
7022-
if (offset >= table->NumberOfElements()) return factory->NewJSArray(0);
7023-
int length = (table->NumberOfElements() - offset) *
7024-
(kind == MapAsArrayKind::kEntries ? 2 : 1);
7025-
i::Handle<i::FixedArray> result = factory->NewFixedArray(length);
7022+
const bool collect_keys =
7023+
kind == MapAsArrayKind::kEntries || kind == MapAsArrayKind::kKeys;
7024+
const bool collect_values =
7025+
kind == MapAsArrayKind::kEntries || kind == MapAsArrayKind::kValues;
7026+
int capacity = table->UsedCapacity();
7027+
int max_length =
7028+
(capacity - offset) * ((collect_keys && collect_values) ? 2 : 1);
7029+
i::Handle<i::FixedArray> result = factory->NewFixedArray(max_length);
70267030
int result_index = 0;
70277031
{
70287032
i::DisallowHeapAllocation no_gc;
7029-
int capacity = table->UsedCapacity();
70307033
i::Oddball* the_hole = i::ReadOnlyRoots(isolate).the_hole_value();
7031-
for (int i = 0; i < capacity; ++i) {
7034+
for (int i = offset; i < capacity; ++i) {
70327035
i::Object* key = table->KeyAt(i);
70337036
if (key == the_hole) continue;
7034-
if (offset-- > 0) continue;
7035-
if (kind == MapAsArrayKind::kEntries || kind == MapAsArrayKind::kKeys) {
7036-
result->set(result_index++, key);
7037-
}
7038-
if (kind == MapAsArrayKind::kEntries || kind == MapAsArrayKind::kValues) {
7039-
result->set(result_index++, table->ValueAt(i));
7040-
}
7037+
if (collect_keys) result->set(result_index++, key);
7038+
if (collect_values) result->set(result_index++, table->ValueAt(i));
70417039
}
70427040
}
7043-
DCHECK_EQ(result_index, result->length());
7044-
DCHECK_EQ(result_index, length);
7045-
return factory->NewJSArrayWithElements(result, i::PACKED_ELEMENTS, length);
7041+
DCHECK_GE(max_length, result_index);
7042+
if (result_index == 0) return factory->NewJSArray(0);
7043+
result->Shrink(isolate, result_index);
7044+
return factory->NewJSArrayWithElements(result, i::PACKED_ELEMENTS,
7045+
result_index);
70467046
}
70477047

70487048
} // namespace
@@ -7127,24 +7127,26 @@ i::Handle<i::JSArray> SetAsArray(i::Isolate* isolate, i::Object* table_obj,
71277127
i::Factory* factory = isolate->factory();
71287128
i::Handle<i::OrderedHashSet> table(i::OrderedHashSet::cast(table_obj),
71297129
isolate);
7130-
int length = table->NumberOfElements() - offset;
7131-
if (length <= 0) return factory->NewJSArray(0);
7132-
i::Handle<i::FixedArray> result = factory->NewFixedArray(length);
7130+
// Elements skipped by |offset| may already be deleted.
7131+
int capacity = table->UsedCapacity();
7132+
int max_length = capacity - offset;
7133+
if (max_length == 0) return factory->NewJSArray(0);
7134+
i::Handle<i::FixedArray> result = factory->NewFixedArray(max_length);
71337135
int result_index = 0;
71347136
{
71357137
i::DisallowHeapAllocation no_gc;
7136-
int capacity = table->UsedCapacity();
71377138
i::Oddball* the_hole = i::ReadOnlyRoots(isolate).the_hole_value();
7138-
for (int i = 0; i < capacity; ++i) {
7139+
for (int i = offset; i < capacity; ++i) {
71397140
i::Object* key = table->KeyAt(i);
71407141
if (key == the_hole) continue;
7141-
if (offset-- > 0) continue;
71427142
result->set(result_index++, key);
71437143
}
71447144
}
7145-
DCHECK_EQ(result_index, result->length());
7146-
DCHECK_EQ(result_index, length);
7147-
return factory->NewJSArrayWithElements(result, i::PACKED_ELEMENTS, length);
7145+
DCHECK_GE(max_length, result_index);
7146+
if (result_index == 0) return factory->NewJSArray(0);
7147+
result->Shrink(isolate, result_index);
7148+
return factory->NewJSArrayWithElements(result, i::PACKED_ELEMENTS,
7149+
result_index);
71487150
}
71497151
} // namespace
71507152

‎test/cctest/test-api.cc‎

Lines changed: 214 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28976,3 +28976,217 @@ TEST(MicrotaskContextShouldBeNativeContext) {
2897628976

2897728977
isolate->RunMicrotasks();
2897828978
}
28979+
28980+
TEST(PreviewSetIteratorEntriesWithDeleted) {
28981+
LocalContext env;
28982+
v8::HandleScope handle_scope(env->GetIsolate());
28983+
v8::Local<v8::Context> context = env.local();
28984+
28985+
{
28986+
// Create set, delete entry, create iterator, preview.
28987+
v8::Local<v8::Object> iterator =
28988+
CompileRun("var set = new Set([1,2,3]); set.delete(1); set.keys()")
28989+
->ToObject(context)
28990+
.ToLocalChecked();
28991+
bool is_key;
28992+
v8::Local<v8::Array> entries =
28993+
iterator->PreviewEntries(&is_key).ToLocalChecked();
28994+
CHECK(!is_key);
28995+
CHECK_EQ(2, entries->Length());
28996+
CHECK_EQ(2, entries->Get(context, 0)
28997+
.ToLocalChecked()
28998+
->Int32Value(context)
28999+
.FromJust());
29000+
CHECK_EQ(3, entries->Get(context, 1)
29001+
.ToLocalChecked()
29002+
->Int32Value(context)
29003+
.FromJust());
29004+
}
29005+
{
29006+
// Create set, create iterator, delete entry, preview.
29007+
v8::Local<v8::Object> iterator =
29008+
CompileRun("var set = new Set([1,2,3]); set.keys()")
29009+
->ToObject(context)
29010+
.ToLocalChecked();
29011+
CompileRun("set.delete(1);");
29012+
bool is_key;
29013+
v8::Local<v8::Array> entries =
29014+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29015+
CHECK(!is_key);
29016+
CHECK_EQ(2, entries->Length());
29017+
CHECK_EQ(2, entries->Get(context, 0)
29018+
.ToLocalChecked()
29019+
->Int32Value(context)
29020+
.FromJust());
29021+
CHECK_EQ(3, entries->Get(context, 1)
29022+
.ToLocalChecked()
29023+
->Int32Value(context)
29024+
.FromJust());
29025+
}
29026+
{
29027+
// Create set, create iterator, delete entry, iterate, preview.
29028+
v8::Local<v8::Object> iterator =
29029+
CompileRun("var set = new Set([1,2,3]); var it = set.keys(); it")
29030+
->ToObject(context)
29031+
.ToLocalChecked();
29032+
CompileRun("set.delete(1); it.next();");
29033+
bool is_key;
29034+
v8::Local<v8::Array> entries =
29035+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29036+
CHECK(!is_key);
29037+
CHECK_EQ(1, entries->Length());
29038+
CHECK_EQ(3, entries->Get(context, 0)
29039+
.ToLocalChecked()
29040+
->Int32Value(context)
29041+
.FromJust());
29042+
}
29043+
{
29044+
// Create set, create iterator, delete entry, iterate until empty, preview.
29045+
v8::Local<v8::Object> iterator =
29046+
CompileRun("var set = new Set([1,2,3]); var it = set.keys(); it")
29047+
->ToObject(context)
29048+
.ToLocalChecked();
29049+
CompileRun("set.delete(1); it.next(); it.next();");
29050+
bool is_key;
29051+
v8::Local<v8::Array> entries =
29052+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29053+
CHECK(!is_key);
29054+
CHECK_EQ(0, entries->Length());
29055+
}
29056+
{
29057+
// Create set, create iterator, delete entry, iterate, trigger rehash,
29058+
// preview.
29059+
v8::Local<v8::Object> iterator =
29060+
CompileRun("var set = new Set([1,2,3]); var it = set.keys(); it")
29061+
->ToObject(context)
29062+
.ToLocalChecked();
29063+
CompileRun("set.delete(1); it.next();");
29064+
CompileRun("for (var i = 4; i < 20; i++) set.add(i);");
29065+
bool is_key;
29066+
v8::Local<v8::Array> entries =
29067+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29068+
CHECK(!is_key);
29069+
CHECK_EQ(17, entries->Length());
29070+
for (uint32_t i = 0; i < 17; i++) {
29071+
CHECK_EQ(i + 3, entries->Get(context, i)
29072+
.ToLocalChecked()
29073+
->Int32Value(context)
29074+
.FromJust());
29075+
}
29076+
}
29077+
}
29078+
29079+
TEST(PreviewMapIteratorEntriesWithDeleted) {
29080+
LocalContext env;
29081+
v8::HandleScope handle_scope(env->GetIsolate());
29082+
v8::Local<v8::Context> context = env.local();
29083+
29084+
{
29085+
// Create map, delete entry, create iterator, preview.
29086+
v8::Local<v8::Object> iterator = CompileRun(
29087+
"var map = new Map();"
29088+
"var key = {}; map.set(key, 1);"
29089+
"map.set({}, 2); map.set({}, 3);"
29090+
"map.delete(key);"
29091+
"map.values()")
29092+
->ToObject(context)
29093+
.ToLocalChecked();
29094+
bool is_key;
29095+
v8::Local<v8::Array> entries =
29096+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29097+
CHECK(!is_key);
29098+
CHECK_EQ(2, entries->Length());
29099+
CHECK_EQ(2, entries->Get(context, 0)
29100+
.ToLocalChecked()
29101+
->Int32Value(context)
29102+
.FromJust());
29103+
CHECK_EQ(3, entries->Get(context, 1)
29104+
.ToLocalChecked()
29105+
->Int32Value(context)
29106+
.FromJust());
29107+
}
29108+
{
29109+
// Create map, create iterator, delete entry, preview.
29110+
v8::Local<v8::Object> iterator = CompileRun(
29111+
"var map = new Map();"
29112+
"var key = {}; map.set(key, 1);"
29113+
"map.set({}, 2); map.set({}, 3);"
29114+
"map.values()")
29115+
->ToObject(context)
29116+
.ToLocalChecked();
29117+
CompileRun("map.delete(key);");
29118+
bool is_key;
29119+
v8::Local<v8::Array> entries =
29120+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29121+
CHECK(!is_key);
29122+
CHECK_EQ(2, entries->Length());
29123+
CHECK_EQ(2, entries->Get(context, 0)
29124+
.ToLocalChecked()
29125+
->Int32Value(context)
29126+
.FromJust());
29127+
CHECK_EQ(3, entries->Get(context, 1)
29128+
.ToLocalChecked()
29129+
->Int32Value(context)
29130+
.FromJust());
29131+
}
29132+
{
29133+
// Create map, create iterator, delete entry, iterate, preview.
29134+
v8::Local<v8::Object> iterator = CompileRun(
29135+
"var map = new Map();"
29136+
"var key = {}; map.set(key, 1);"
29137+
"map.set({}, 2); map.set({}, 3);"
29138+
"var it = map.values(); it")
29139+
->ToObject(context)
29140+
.ToLocalChecked();
29141+
CompileRun("map.delete(key); it.next();");
29142+
bool is_key;
29143+
v8::Local<v8::Array> entries =
29144+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29145+
CHECK(!is_key);
29146+
CHECK_EQ(1, entries->Length());
29147+
CHECK_EQ(3, entries->Get(context, 0)
29148+
.ToLocalChecked()
29149+
->Int32Value(context)
29150+
.FromJust());
29151+
}
29152+
{
29153+
// Create map, create iterator, delete entry, iterate until empty, preview.
29154+
v8::Local<v8::Object> iterator = CompileRun(
29155+
"var map = new Map();"
29156+
"var key = {}; map.set(key, 1);"
29157+
"map.set({}, 2); map.set({}, 3);"
29158+
"var it = map.values(); it")
29159+
->ToObject(context)
29160+
.ToLocalChecked();
29161+
CompileRun("map.delete(key); it.next(); it.next();");
29162+
bool is_key;
29163+
v8::Local<v8::Array> entries =
29164+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29165+
CHECK(!is_key);
29166+
CHECK_EQ(0, entries->Length());
29167+
}
29168+
{
29169+
// Create map, create iterator, delete entry, iterate, trigger rehash,
29170+
// preview.
29171+
v8::Local<v8::Object> iterator = CompileRun(
29172+
"var map = new Map();"
29173+
"var key = {}; map.set(key, 1);"
29174+
"map.set({}, 2); map.set({}, 3);"
29175+
"var it = map.values(); it")
29176+
->ToObject(context)
29177+
.ToLocalChecked();
29178+
CompileRun("map.delete(key); it.next();");
29179+
CompileRun("for (var i = 4; i < 20; i++) map.set({}, i);");
29180+
bool is_key;
29181+
v8::Local<v8::Array> entries =
29182+
iterator->PreviewEntries(&is_key).ToLocalChecked();
29183+
CHECK(!is_key);
29184+
CHECK_EQ(17, entries->Length());
29185+
for (uint32_t i = 0; i < 17; i++) {
29186+
CHECK_EQ(i + 3, entries->Get(context, i)
29187+
.ToLocalChecked()
29188+
->Int32Value(context)
29189+
.FromJust());
29190+
}
29191+
}
29192+
}

0 commit comments

Comments
 (0)