Title: [181968] trunk/Source/_javascript_Core
- Revision
- 181968
- Author
- [email protected]
- Date
- 2015-03-25 11:37:17 -0700 (Wed, 25 Mar 2015)
Log Message
New map and set modification tests in r181922 fails
https://bugs.webkit.org/show_bug.cgi?id=143031
Reviewed and tweaked by Geoffrey Garen.
When packing Map/Set backing store, we need to decrement Map/Set iterator's m_index
to adjust for the packed backing store.
Consider the following map data.
x: deleted, o: exists
0 1 2 3 4
x x x x o
And iterator with m_index 3.
When packing the map data, map data will become,
0
o
At that time, we perfom didRemoveEntry 4 times on iterators.
times => m_index/index/result
1 => 3/0/dec
2 => 2/1/dec
3 => 1/2/nothing
4 => 1/3/nothing
After iteration, iterator's m_index becomes 1. But we expected that becomes 0.
This is because if we use decremented m_index for comparison,
while provided deletedIndex is the index in old storage, m_index is the index in partially packed storage.
In this patch, we compare against the packed index instead.
times => m_index/packedIndex/result
1 => 3/0/dec
2 => 2/0/dec
3 => 1/0/dec
4 => 0/0/nothing
So m_index becomes 0 as expected.
And according to the spec, once the iterator is closed (becomes done: true),
its internal [[Map]]/[[Set]] is set to undefined.
So after the iterator is finished, we don't revive the iterator (e.g. by clearing m_index = 0).
In this patch, we change 2 things.
1.
Compare an iterator's index against the packed index when removing an entry.
2.
If the iterator is closed (isFinished()), we don't apply adjustment to the iterator.
Patch by Yusuke Suzuki <[email protected]> on 2015-03-25
* runtime/MapData.h:
(JSC::MapDataImpl::IteratorData::finish):
(JSC::MapDataImpl::IteratorData::isFinished):
(JSC::MapDataImpl::IteratorData::didRemoveEntry):
(JSC::MapDataImpl::IteratorData::didRemoveAllEntries):
(JSC::MapDataImpl::IteratorData::startPackBackingStore):
* runtime/MapDataInlines.h:
(JSC::JSIterator>::replaceAndPackBackingStore):
* tests/stress/modify-map-during-iteration.js:
* tests/stress/modify-set-during-iteration.js:
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (181967 => 181968)
--- trunk/Source/_javascript_Core/ChangeLog 2015-03-25 18:29:19 UTC (rev 181967)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-03-25 18:37:17 UTC (rev 181968)
@@ -1,3 +1,68 @@
+2015-03-25 Yusuke Suzuki <[email protected]>
+
+ New map and set modification tests in r181922 fails
+ https://bugs.webkit.org/show_bug.cgi?id=143031
+
+ Reviewed and tweaked by Geoffrey Garen.
+
+ When packing Map/Set backing store, we need to decrement Map/Set iterator's m_index
+ to adjust for the packed backing store.
+
+ Consider the following map data.
+
+ x: deleted, o: exists
+ 0 1 2 3 4
+ x x x x o
+
+ And iterator with m_index 3.
+
+ When packing the map data, map data will become,
+
+ 0
+ o
+
+ At that time, we perfom didRemoveEntry 4 times on iterators.
+ times => m_index/index/result
+ 1 => 3/0/dec
+ 2 => 2/1/dec
+ 3 => 1/2/nothing
+ 4 => 1/3/nothing
+
+ After iteration, iterator's m_index becomes 1. But we expected that becomes 0.
+ This is because if we use decremented m_index for comparison,
+ while provided deletedIndex is the index in old storage, m_index is the index in partially packed storage.
+
+ In this patch, we compare against the packed index instead.
+ times => m_index/packedIndex/result
+ 1 => 3/0/dec
+ 2 => 2/0/dec
+ 3 => 1/0/dec
+ 4 => 0/0/nothing
+
+ So m_index becomes 0 as expected.
+
+ And according to the spec, once the iterator is closed (becomes done: true),
+ its internal [[Map]]/[[Set]] is set to undefined.
+ So after the iterator is finished, we don't revive the iterator (e.g. by clearing m_index = 0).
+
+ In this patch, we change 2 things.
+ 1.
+ Compare an iterator's index against the packed index when removing an entry.
+
+ 2.
+ If the iterator is closed (isFinished()), we don't apply adjustment to the iterator.
+
+ * runtime/MapData.h:
+ (JSC::MapDataImpl::IteratorData::finish):
+ (JSC::MapDataImpl::IteratorData::isFinished):
+ (JSC::MapDataImpl::IteratorData::didRemoveEntry):
+ (JSC::MapDataImpl::IteratorData::didRemoveAllEntries):
+ (JSC::MapDataImpl::IteratorData::startPackBackingStore):
+ * runtime/MapDataInlines.h:
+ (JSC::JSIterator>::replaceAndPackBackingStore):
+ * tests/stress/modify-map-during-iteration.js:
+ * tests/stress/modify-set-during-iteration.js:
+
2015-03-24 Joseph Pecoraro <[email protected]>
Setter should have a single formal parameter, Getter no parameters
Modified: trunk/Source/_javascript_Core/runtime/MapData.h (181967 => 181968)
--- trunk/Source/_javascript_Core/runtime/MapData.h 2015-03-25 18:29:19 UTC (rev 181967)
+++ trunk/Source/_javascript_Core/runtime/MapData.h 2015-03-25 18:37:17 UTC (rev 181968)
@@ -54,15 +54,23 @@
IteratorData(const MapDataImpl*);
bool next(WTF::KeyValuePair<JSValue, JSValue>&);
- void didRemoveEntry(int32_t index)
+ // This function is called while packing a map's backing store. The
+ // passed-in index is the new index the entry would have after packing.
+ void didRemoveEntry(int32_t packedIndex)
{
- if (m_index <= index)
+ if (isFinished())
return;
+
+ if (m_index <= packedIndex)
+ return;
+
--m_index;
}
void didRemoveAllEntries()
{
+ if (isFinished())
+ return;
m_index = 0;
}
Modified: trunk/Source/_javascript_Core/runtime/MapDataInlines.h (181967 => 181968)
--- trunk/Source/_javascript_Core/runtime/MapDataInlines.h 2015-03-25 18:29:19 UTC (rev 181967)
+++ trunk/Source/_javascript_Core/runtime/MapDataInlines.h 2015-03-25 18:37:17 UTC (rev 181968)
@@ -178,8 +178,8 @@
for (int32_t i = 0; i < m_size; i++) {
Entry& entry = m_entries[i];
if (!entry.key()) {
- m_iterators.forEach([i](JSIterator* iterator, JSIterator*) {
- iterator->iteratorData()->didRemoveEntry(i);
+ m_iterators.forEach([newEnd](JSIterator* iterator, JSIterator*) {
+ iterator->iteratorData()->didRemoveEntry(newEnd);
});
continue;
}
Modified: trunk/Source/_javascript_Core/tests/stress/modify-map-during-iteration.js (181967 => 181968)
--- trunk/Source/_javascript_Core/tests/stress/modify-map-during-iteration.js 2015-03-25 18:29:19 UTC (rev 181967)
+++ trunk/Source/_javascript_Core/tests/stress/modify-map-during-iteration.js 2015-03-25 18:37:17 UTC (rev 181968)
@@ -74,3 +74,24 @@
throw new Error("unreeachable.");
}
+var map = new Map();
+for (var i = 0; i < 5; ++i)
+ map.set(i, i);
+testValue(map.size, 5);
+var iter = map.keys();
+testValue(iter.next().value, 0);
+testValue(iter.next().value, 1);
+testValue(iter.next().value, 2);
+testValue(iter.next().value, 3);
+map.delete(0);
+map.delete(1);
+map.delete(2);
+map.delete(3);
+// It will cause MapData packing.
+for (var i = 5; i < 1000; ++i)
+ map.set(i, i);
+gc();
+for (var i = 4; i < 1000; ++i)
+ testValue(iter.next().value, i);
+testValue(iter.next().value, undefined);
+
Modified: trunk/Source/_javascript_Core/tests/stress/modify-set-during-iteration.js (181967 => 181968)
--- trunk/Source/_javascript_Core/tests/stress/modify-set-during-iteration.js 2015-03-25 18:29:19 UTC (rev 181967)
+++ trunk/Source/_javascript_Core/tests/stress/modify-set-during-iteration.js 2015-03-25 18:37:17 UTC (rev 181968)
@@ -70,3 +70,22 @@
throw new Error("unreeachable.");
}
+var set = new Set([0, 1, 2, 3, 4]);
+var iter = set[Symbol.iterator]();
+testValue(set.size, 5);
+testValue(iter.next().value, 0);
+testValue(iter.next().value, 1);
+testValue(iter.next().value, 2);
+testValue(iter.next().value, 3);
+set.delete(0);
+set.delete(1);
+set.delete(2);
+set.delete(3);
+// It will cause MapData packing.
+for (var i = 5; i < 1000; ++i)
+ set.add(i);
+gc();
+for (var i = 4; i < 1000; ++i)
+ testValue(iter.next().value, i);
+testValue(iter.next().value, undefined);
+
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
