Reviewers: rossberg, Kevin Millikin,
Message:
PTAL.
Description:
Fix Harmony sets and maps to allow null as key.
This changes the internal convention for marking deleted entries in hash
tables from null_value to the_hole_value, which is consistent with other
usages of the_hole.
[email protected],[email protected]
BUG=v8:1622
TEST=mjsunit/harmony/collections
Please review this at http://codereview.chromium.org/8343056/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/heap-inl.h
M src/heap.cc
M src/mark-compact.cc
M src/objects-inl.h
M src/objects.h
M src/objects.cc
M test/mjsunit/harmony/collections.js
Index: src/heap-inl.h
diff --git a/src/heap-inl.h b/src/heap-inl.h
index
aaf2927f7f941a4f3cb9648a15ef6a7eae05df3b..c065b73daa70354c5652b7775d1f46b671b2d6d4
100644
--- a/src/heap-inl.h
+++ b/src/heap-inl.h
@@ -571,11 +571,11 @@ void ExternalStringTable::Verify() {
#ifdef DEBUG
for (int i = 0; i < new_space_strings_.length(); ++i) {
ASSERT(heap_->InNewSpace(new_space_strings_[i]));
- ASSERT(new_space_strings_[i] != HEAP->raw_unchecked_null_value());
+ ASSERT(new_space_strings_[i] != HEAP->raw_unchecked_the_hole_value());
}
for (int i = 0; i < old_space_strings_.length(); ++i) {
ASSERT(!heap_->InNewSpace(old_space_strings_[i]));
- ASSERT(old_space_strings_[i] != HEAP->raw_unchecked_null_value());
+ ASSERT(old_space_strings_[i] != HEAP->raw_unchecked_the_hole_value());
}
#endif
}
Index: src/heap.cc
diff --git a/src/heap.cc b/src/heap.cc
index
bbb9d3e26d1ffe0676d1bc720205d8dd8f6a67c7..b4060a98a72a6ae67c3e13522b574d28f9ee4290
100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -539,7 +539,7 @@ class SymbolTableVerifier : public ObjectVisitor {
for (Object** p = start; p < end; p++) {
if ((*p)->IsHeapObject()) {
// Check that the symbol is actually a symbol.
- ASSERT((*p)->IsNull() || (*p)->IsUndefined() || (*p)->IsSymbol());
+ ASSERT((*p)->IsTheHole() || (*p)->IsUndefined() ||
(*p)->IsSymbol());
}
}
}
@@ -6342,7 +6342,9 @@ void TranscendentalCache::Clear() {
void ExternalStringTable::CleanUp() {
int last = 0;
for (int i = 0; i < new_space_strings_.length(); ++i) {
- if (new_space_strings_[i] == heap_->raw_unchecked_null_value())
continue;
+ if (new_space_strings_[i] == heap_->raw_unchecked_the_hole_value()) {
+ continue;
+ }
if (heap_->InNewSpace(new_space_strings_[i])) {
new_space_strings_[last++] = new_space_strings_[i];
} else {
@@ -6352,7 +6354,9 @@ void ExternalStringTable::CleanUp() {
new_space_strings_.Rewind(last);
last = 0;
for (int i = 0; i < old_space_strings_.length(); ++i) {
- if (old_space_strings_[i] == heap_->raw_unchecked_null_value())
continue;
+ if (old_space_strings_[i] == heap_->raw_unchecked_the_hole_value()) {
+ continue;
+ }
ASSERT(!heap_->InNewSpace(old_space_strings_[i]));
old_space_strings_[last++] = old_space_strings_[i];
}
Index: src/mark-compact.cc
diff --git a/src/mark-compact.cc b/src/mark-compact.cc
index
b41b03367cede12168e48ffc81ef2a33c53031da..94e65fa3a3bdaf13681fca8a89ef1be6327561f7
100644
--- a/src/mark-compact.cc
+++ b/src/mark-compact.cc
@@ -1516,8 +1516,8 @@ class SymbolTableCleaner : public ObjectVisitor {
if (o->IsExternalString()) {
heap_->FinalizeExternalString(String::cast(*p));
}
- // Set the entry to null_value (as deleted).
- *p = heap_->null_value();
+ // Set the entry to the_hole_value (as deleted).
+ *p = heap_->the_hole_value();
pointers_removed_++;
}
}
@@ -2124,7 +2124,7 @@ void MarkCompactCollector::ProcessMapCaches() {
i += MapCache::kEntrySize) {
Object* raw_key = map_cache->get(i);
if (raw_key == heap()->undefined_value() ||
- raw_key == heap()->null_value()) continue;
+ raw_key == heap()->the_hole_value()) continue;
STATIC_ASSERT(MapCache::kEntrySize == 2);
Object* raw_map = map_cache->get(i + 1);
if (raw_map->IsHeapObject() && IsMarked(raw_map)) {
@@ -2132,8 +2132,8 @@ void MarkCompactCollector::ProcessMapCaches() {
} else {
// Delete useless entries with unmarked maps.
ASSERT(raw_map->IsMap());
- map_cache->set_null_unchecked(heap(), i);
- map_cache->set_null_unchecked(heap(), i + 1);
+ map_cache->set_the_hole(i);
+ map_cache->set_the_hole(i + 1);
}
}
if (used_elements == 0) {
@@ -2320,7 +2320,7 @@ void MarkCompactCollector::ClearWeakMaps() {
ObjectHashTable* table = weak_map->unchecked_table();
for (int i = 0; i < table->Capacity(); i++) {
if
(!MarkCompactCollector::IsMarked(HeapObject::cast(table->KeyAt(i)))) {
- table->RemoveEntry(i, heap());
+ table->RemoveEntry(i);
}
}
weak_map_obj = weak_map->next();
Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index
dc3aa466693f8cf7557fbcc3218171f9807b89d5..496f325618cbd3371d29058869f4a0595a3c14dc
100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -1975,7 +1975,7 @@ int HashTable<Shape, Key>::FindEntry(Isolate*
isolate, Key key) {
while (true) {
Object* element = KeyAt(entry);
if (element == isolate->heap()->undefined_value()) break; // Empty
entry.
- if (element != isolate->heap()->null_value() &&
+ if (element != isolate->heap()->the_hole_value() &&
Shape::IsMatch(key, element)) return entry;
entry = NextProbe(entry, count++, capacity);
}
@@ -4434,7 +4434,6 @@ bool ObjectHashTableShape<entrysize>::IsMatch(Object*
key, Object* other) {
template <int entrysize>
uint32_t ObjectHashTableShape<entrysize>::Hash(Object* key) {
- ASSERT(!key->IsUndefined() && !key->IsNull());
MaybeObject* maybe_hash = key->GetHash(OMIT_CREATION);
return Smi::cast(maybe_hash->ToObjectChecked())->value();
}
@@ -4443,7 +4442,6 @@ uint32_t
ObjectHashTableShape<entrysize>::Hash(Object* key) {
template <int entrysize>
uint32_t ObjectHashTableShape<entrysize>::HashForObject(Object* key,
Object* other) {
- ASSERT(!other->IsUndefined() && !other->IsNull());
MaybeObject* maybe_hash = other->GetHash(OMIT_CREATION);
return Smi::cast(maybe_hash->ToObjectChecked())->value();
}
@@ -4455,11 +4453,6 @@ MaybeObject*
ObjectHashTableShape<entrysize>::AsObject(Object* key) {
}
-void ObjectHashTable::RemoveEntry(int entry) {
- RemoveEntry(entry, GetHeap());
-}
-
-
void Map::ClearCodeCache(Heap* heap) {
// No write barrier is needed since empty_fixed_array is not in new
space.
// Please note this function is used during marking:
Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index
1e398a5a730e1625119e20d75fd580e4169fb18b..fb39b3691464a2fedfbb4831ee941a35ad9fa636
100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -5190,8 +5190,8 @@ int CodeCacheHashTable::GetIndex(String* name,
Code::Flags flags) {
void CodeCacheHashTable::RemoveByIndex(int index) {
ASSERT(index >= 0);
Heap* heap = GetHeap();
- set(EntryToIndex(index), heap->null_value());
- set(EntryToIndex(index) + 1, heap->null_value());
+ set(EntryToIndex(index), heap->the_hole_value());
+ set(EntryToIndex(index) + 1, heap->the_hole_value());
ElementRemoved();
}
@@ -10909,14 +10909,14 @@ int StringDictionary::FindEntry(String* key) {
if (element->IsUndefined()) break; // Empty entry.
if (key == element) return entry;
if (!element->IsSymbol() &&
- !element->IsNull() &&
+ !element->IsTheHole() &&
String::cast(element)->Equals(key)) {
// Replace a non-symbol key by the equivalent symbol for faster
further
// lookups.
set(index, key);
return entry;
}
- ASSERT(element->IsNull() || !String::cast(element)->Equals(key));
+ ASSERT(element->IsTheHole() || !String::cast(element)->Equals(key));
entry = NextProbe(entry, count++, capacity);
}
return kNotFound;
@@ -11020,7 +11020,7 @@ uint32_t HashTable<Shape,
Key>::FindInsertionEntry(uint32_t hash) {
// EnsureCapacity will guarantee the hash table is never full.
while (true) {
Object* element = KeyAt(entry);
- if (element->IsUndefined() || element->IsNull()) break;
+ if (element->IsUndefined() || element->IsTheHole()) break;
entry = NextProbe(entry, count++, capacity);
}
return entry;
@@ -11819,13 +11819,13 @@ MaybeObject*
CompilationCacheTable::PutRegExp(String* src,
void CompilationCacheTable::Remove(Object* value) {
- Object* null_value = GetHeap()->null_value();
+ Object* the_hole_value = GetHeap()->the_hole_value();
for (int entry = 0, size = Capacity(); entry < size; entry++) {
int entry_index = EntryToIndex(entry);
int value_index = entry_index + 1;
if (get(value_index) == value) {
- NoWriteBarrierSet(this, entry_index, null_value);
- NoWriteBarrierSet(this, value_index, null_value);
+ NoWriteBarrierSet(this, entry_index, the_hole_value);
+ NoWriteBarrierSet(this, value_index, the_hole_value);
ElementRemoved();
}
}
@@ -11984,14 +11984,14 @@ void
NumberDictionary::RemoveNumberEntries(uint32_t from, uint32_t to) {
Heap* heap = GetHeap();
int removed_entries = 0;
- Object* sentinel = heap->null_value();
+ Object* the_hole_value = heap->the_hole_value();
int capacity = Capacity();
for (int i = 0; i < capacity; i++) {
Object* key = KeyAt(i);
if (key->IsNumber()) {
uint32_t number = static_cast<uint32_t>(key->Number());
if (from <= number && number < to) {
- SetEntry(i, sentinel, sentinel);
+ SetEntry(i, the_hole_value, the_hole_value);
removed_entries++;
}
}
@@ -12011,7 +12011,7 @@ Object* Dictionary<Shape, Key>::DeleteProperty(int
entry,
if (details.IsDontDelete() && mode != JSReceiver::FORCE_DELETION) {
return heap->false_value();
}
- SetEntry(entry, heap->null_value(), heap->null_value());
+ SetEntry(entry, heap->the_hole_value(), heap->the_hole_value());
HashTable<Shape, Key>::ElementRemoved();
return heap->true_value();
}
@@ -12395,6 +12395,8 @@ MaybeObject*
StringDictionary::TransformPropertiesToFastFor(
bool ObjectHashSet::Contains(Object* key) {
+ ASSERT(IsKey(key));
+
// If the object does not have an identity hash, it was never used as a
key.
{ MaybeObject* maybe_hash = key->GetHash(OMIT_CREATION);
if (maybe_hash->ToObjectUnchecked()->IsUndefined()) return false;
@@ -12404,6 +12406,8 @@ bool ObjectHashSet::Contains(Object* key) {
MaybeObject* ObjectHashSet::Add(Object* key) {
+ ASSERT(IsKey(key));
+
// Make sure the key object has an identity hash code.
int hash;
{ MaybeObject* maybe_hash = key->GetHash(ALLOW_CREATION);
@@ -12429,6 +12433,8 @@ MaybeObject* ObjectHashSet::Add(Object* key) {
MaybeObject* ObjectHashSet::Remove(Object* key) {
+ ASSERT(IsKey(key));
+
// If the object does not have an identity hash, it was never used as a
key.
{ MaybeObject* maybe_hash = key->GetHash(OMIT_CREATION);
if (maybe_hash->ToObjectUnchecked()->IsUndefined()) return this;
@@ -12439,13 +12445,15 @@ MaybeObject* ObjectHashSet::Remove(Object* key) {
if (entry == kNotFound) return this;
// Remove entry and try to shrink this hash set.
- set_null(EntryToIndex(entry));
+ set_the_hole(EntryToIndex(entry));
ElementRemoved();
return Shrink(key);
}
Object* ObjectHashTable::Lookup(Object* key) {
+ ASSERT(IsKey(key));
+
// If the object does not have an identity hash, it was never used as a
key.
{ MaybeObject* maybe_hash = key->GetHash(OMIT_CREATION);
if (maybe_hash->ToObjectUnchecked()->IsUndefined()) {
@@ -12459,6 +12467,8 @@ Object* ObjectHashTable::Lookup(Object* key) {
MaybeObject* ObjectHashTable::Put(Object* key, Object* value) {
+ ASSERT(IsKey(key));
+
// Make sure the key object has an identity hash code.
int hash;
{ MaybeObject* maybe_hash = key->GetHash(ALLOW_CREATION);
@@ -12498,9 +12508,9 @@ void ObjectHashTable::AddEntry(int entry, Object*
key, Object* value) {
}
-void ObjectHashTable::RemoveEntry(int entry, Heap* heap) {
- set_null(heap, EntryToIndex(entry));
- set_null(heap, EntryToIndex(entry) + 1);
+void ObjectHashTable::RemoveEntry(int entry) {
+ set_the_hole(EntryToIndex(entry));
+ set_the_hole(EntryToIndex(entry) + 1);
ElementRemoved();
}
Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index
f7d21802270cfc93c19c7cbc7d573c2b01562c9d..de1c88b52106aad75eb976d8beb3fc92c9280da2
100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -2509,7 +2509,7 @@ class DescriptorArray: public FixedArray {
// encountered and stops when unused elements are encountered.
//
// - Elements with key == undefined have not been used yet.
-// - Elements with key == null have been deleted.
+// - Elements with key == the_hole have been deleted.
//
// The hash table class is parameterized with a Shape and a Key.
// Shape must be a class with the following interface:
@@ -2578,10 +2578,10 @@ class HashTable: public FixedArray {
// Returns the key at entry.
Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
- // Tells whether k is a real key. Null and undefined are not allowed
+ // Tells whether k is a real key. The hole and undefined are not allowed
// as keys and can be used to indicate missing or deleted elements.
bool IsKey(Object* k) {
- return !k->IsNull() && !k->IsUndefined();
+ return !k->IsTheHole() && !k->IsUndefined();
}
// Garbage collection support.
@@ -3050,8 +3050,7 @@ class ObjectHashTable: public
HashTable<ObjectHashTableShape<2>, Object*> {
friend class MarkCompactCollector;
void AddEntry(int entry, Object* key, Object* value);
- void RemoveEntry(int entry, Heap* heap);
- inline void RemoveEntry(int entry);
+ void RemoveEntry(int entry);
// Returns the index to the value of an entry.
static inline int EntryToValueIndex(int entry) {
@@ -7080,7 +7079,7 @@ class JSFunctionProxy: public JSProxy {
};
-// The JSSet describes EcmaScript Harmony maps
+// The JSSet describes EcmaScript Harmony sets
class JSSet: public JSObject {
public:
// [set]: the backing hash set containing keys.
Index: test/mjsunit/harmony/collections.js
diff --git a/test/mjsunit/harmony/collections.js
b/test/mjsunit/harmony/collections.js
index
1ad1c6f349749e4a674e250b0fbc531b760cc24e..d3c6c0f258030474dc717b27997c74c064630870
100644
--- a/test/mjsunit/harmony/collections.js
+++ b/test/mjsunit/harmony/collections.js
@@ -52,6 +52,8 @@ TestValidMapCalls(new WeakMap);
function TestInvalidCalls(m) {
assertThrows(function () { m.get(undefined) }, TypeError);
assertThrows(function () { m.set(undefined, 0) }, TypeError);
+ assertThrows(function () { m.get(null) }, TypeError);
+ assertThrows(function () { m.set(null, 0) }, TypeError);
assertThrows(function () { m.get(0) }, TypeError);
assertThrows(function () { m.set(0, 0) }, TypeError);
assertThrows(function () { m.get('a-key') }, TypeError);
@@ -69,7 +71,7 @@ function TestSet(set, key) {
assertFalse(set.has(key));
}
function TestSetBehavior(set) {
- for (i = 0; i < 20; i++) {
+ for (var i = 0; i < 20; i++) {
TestSet(set, new Object);
}
}
@@ -99,7 +101,7 @@ function TestMapBehavior2(m) {
TestMapping(m, i / 10, new Object);
TestMapping(m, 'key-' + i, new Object);
}
- var keys = [ +0, -0, +Infinity, -Infinity, true, false ];
+ var keys = [ +0, -0, +Infinity, -Infinity, true, false, null ];
for (var i = 0; i < keys.length; i++) {
TestMapping(m, keys[i], new Object);
}
@@ -184,7 +186,7 @@ function TestArbitrary(m) {
map[property] = value;
assertEquals(value, map[property]);
}
- for (i = 0; i < 20; i++) {
+ for (var i = 0; i < 20; i++) {
TestProperty(m, i, 'val' + i);
TestProperty(m, 'foo' + i, 'bar' + i);
}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
