Make HashMap's delete key a const expression.

corelib/src/implementation/hash_map_set.dart

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // Hash map implementation with open addressing and quadratic probing.
 class HashMapImplementation<K extends Hashable, V> implements HashMap<K, V> {
 
   // The [_keys] list contains the keys inserted in the map.
   // The [_keys] list must be a raw list because it
-  // will contain both elements of type K, and the [_deletedKey] of type
-  // Object.
+  // will contain both elements of type K, and the [_DELETED_KEY] of type
+  // [_DeleteKeySentinel].

[Ivan Posva, 2011/11/17 18:57:47]

DeletedKeySentinel

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

Done (I expect you meant here to remove the _ from the type name).

[Ivan Posva, 2011/11/17 21:06:51]

You really, really want to keep this type private otherwise you suffer the same
problems as you did with const Object(). What I meant to say is that you want to
rename the type to _DeletedKeySentinel (note the d) because it refers to the
deleted key and not to the delete operation.

[Siggi Cherem (dart-lang), 2011/11/17 21:13:27]

Fixed - I was assuming that because this type is within corelib_impl (and not
corelib), it wasn't accessible elsewhere anyways.

   // The alternative of declaring the [_keys] list as of type Object
   // does not work, because the HashSetIterator constructor would fail:
   //  HashSetIterator(HashSet<E> set)
   //    : _nextValidIndex = -1,
   //      _entries = set_._backingMap._keys {
   //    _advance();
   //  }
   // With K being type int, for example, it would fail because
   // List<Object> is not assignable to type List<int> of entries.
   List _keys;
 
   // The values inserted in the map. For a filled entry index in this
   // list, there is always the corresponding key in the [keys_] list
   // at the same entry index.
   List<V> _values;
 
   // The load limit is the number of entries we allow until we double
   // the size of the lists.
   int _loadLimit;
 
   // The current number of entries in the map. Will never be greater
   // than [_loadLimit].
   int _numberOfEntries;
 
   // The current number of deleted entries in the map.
   int _numberOfDeleted;
 
-  // The sentinel when a key is deleted from the map. We cannot use static
-  // const here because we would need to allocate a "const Object()" which
-  // would end up canonicalized and then we cannot distinguish the deleted
-  // key from the canonicalized Object().
-  static Object _deletedKey;
+  // The sentinel when a key is deleted from the map.
+  static final Object _DELETED_KEY = const _DeleteKeySentinel();

[Siggi Cherem (dart-lang), 2011/11/17 18:40:32]

Is there an issue in using an instance that is not [Object], but
[_DeleteKeySentinel] here?

[Ivan Posva, 2011/11/17 18:57:47]

Why is there even a type on this value? I don't think it needs to be there and
if you want to specify a type then you should use _DeletedKeySentinel.

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

Done.

 
   // The initial capacity of a hash map.
   static final int _INITIAL_CAPACITY = 8;  // must be power of 2
 
   HashMapImplementation() {
-    if (_deletedKey === null) {
-      _deletedKey = new Object();
-    }
     _numberOfEntries = 0;
     _numberOfDeleted = 0;
     _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY);
     _keys = new List(_INITIAL_CAPACITY);
     _values = new List<V>(_INITIAL_CAPACITY);
   }
 
   // See bug 5257789.

[Ivan Posva, 2011/11/17 18:57:47]

This bug is claiming to be fixed?

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

Tried - works in the VM, but I still get some failures in the dartc tests.

   factory HashMapImplementation/* <K, V> */.from(Map/* <K, V> */other) {
     Map/* <K, V> */ result = new HashMapImplementation/* <K, V> */();
     other.forEach((/* K */ key, /* V */ value) { result[key] = value; });
     return result;
   }
 
   static int _computeLoadLimit(int capacity) {
     return (capacity * 3) ~/ 4;
   }
 
   static int _firstProbe(int hashCode, int length) {
     return hashCode & (length - 1);
   }
 
   static int _nextProbe(int currentProbe, int numberOfProbes, int length) {
     return (currentProbe + numberOfProbes) & (length - 1);
   }
 
   int _probeForAdding(K key) {
     int hash = _firstProbe(key.hashCode(), _keys.length);
     int numberOfProbes = 1;
     int initialHash = hash;
     // insertionIndex points to a slot where a key was deleted.
     int insertionIndex = -1;
     while (true) {
       Object existingKey = _keys[hash];

[Ivan Posva, 2011/11/17 18:57:47]

How about change Object here to var and adding a comment as to why not all _keys
are not necessarily of type K?

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

I added the comment, but left it as [Object] rather than [var].

I prefer to leave is as Object because it gives us better errors in checked
mode: having Object says that even though we don't know the precise type, we
don't plan to access anything on it and we should get a type error if we do.

       if (existingKey === null) {
         // We are sure the key is not already in the set.
         // If the current slot is empty and we didn't find any
         // insertion slot before, return this slot.
         if (insertionIndex < 0) return hash;
         // If we did find an insertion slot before, return it.
         return insertionIndex;
       } else if (existingKey == key) {
         // The key is already in the map. Return its slot.
         return hash;
-      } else if ((insertionIndex < 0) && (_deletedKey === existingKey)) {
+      } else if ((insertionIndex < 0) && (_DELETED_KEY === existingKey)) {
         // The slot contains a deleted element. Because previous calls to this
         // method may not have had this slot deleted, we must continue iterate
         // to find if there is a slot with the given key.
         insertionIndex = hash;
       }
 
       // We did not find an insertion slot. Look at the next one.
       hash = _nextProbe(hash, numberOfProbes++, _keys.length);
       // _ensureCapacity has guaranteed the following cannot happen.
       // assert(hash != initialHash);
     }
   }
 
   int _probeForLookup(K key) {
     int hash = _firstProbe(key.hashCode(), _keys.length);
     int numberOfProbes = 1;
     int initialHash = hash;
     while (true) {
       Object existingKey = _keys[hash];

[Ivan Posva, 2011/11/17 18:57:47]

ditto.

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

Done.

       // If the slot does not contain anything (in particular, it does not
       // contain a deleted key), we know the key is not in the map.
       if (existingKey === null) return -1;
       // The key is in the map, return its index.
       if (existingKey == key) return hash;
       // Go to the next probe.
       hash = _nextProbe(hash, numberOfProbes++, _keys.length);
       // _ensureCapacity has guaranteed the following cannot happen.
       // assert(hash != initialHash);
     }
@@ skipping 25 matching lines @@
 
   void _grow(int newCapacity) {
     assert(_isPowerOfTwo(newCapacity));
     int capacity = _keys.length;
     _loadLimit = _computeLoadLimit(newCapacity);
     List oldKeys = _keys;
     List<V> oldValues = _values;
     _keys = new List(newCapacity);
     _values = new List<V>(newCapacity);
     for (int i = 0; i < capacity; i++) {
       Object key = oldKeys[i];

[Ivan Posva, 2011/11/17 18:57:47]

ditto.

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

Done.

       // If there is no key, we don't need to deal with the current slot.
-      if (key === null || key === _deletedKey) {
+      if (key === null || key === _DELETED_KEY) {
         continue;
       }
       V value = oldValues[i];
       // Insert the {key, value} pair in their new slot.
       int newIndex = _probeForAdding(key);
       _keys[newIndex] = key;
       _values[newIndex] = value;
     }
     _numberOfDeleted = 0;
   }
 
   void clear() {
     _numberOfEntries = 0;
     _numberOfDeleted = 0;
     int length = _keys.length;
     for (int i = 0; i < length; i++) {
       _keys[i] = null;
       _values[i] = null;
     }
   }
 
   void operator []=(K key, V value) {
     _ensureCapacity();
     int index = _probeForAdding(key);
-    if ((_keys[index] === null) || (_keys[index] === _deletedKey)) {
+    if ((_keys[index] === null) || (_keys[index] === _DELETED_KEY)) {
       _numberOfEntries++;
     }
     _keys[index] = key;
     _values[index] = value;
   }
 
   V operator [](K key) {
     int index = _probeForLookup(key);
     if (index < 0) return null;
     return _values[index];
   }
 
   V putIfAbsent(K key, V ifAbsent()) {
     int index = _probeForLookup(key);
     if (index >=0) return _values[index];
 
     V value = ifAbsent();
     this[key] = value;
     return value;
   }
 
   V remove(K key) {
     int index = _probeForLookup(key);
     if (index >= 0) {
       _numberOfEntries--;
       V value = _values[index];
       _values[index] = null;
       // Set the key to the sentinel to not break the probing chain.
-      _keys[index] = _deletedKey;
+      _keys[index] = _DELETED_KEY;
       _numberOfDeleted++;
       return value;
     }
     return null;
   }
 
   bool isEmpty() {
     return _numberOfEntries == 0;
   }
 
   int get length() {
     return _numberOfEntries;
   }
 
   void forEach(void f(K key, V value)) {
     int length = _keys.length;
     for (int i = 0; i < length; i++) {
-      if ((_keys[i] !== null) && (_keys[i] !== _deletedKey)) {
+      if ((_keys[i] !== null) && (_keys[i] !== _DELETED_KEY)) {
         f(_keys[i], _values[i]);
       }
     }
   }
 
 
   Collection<K> getKeys() {
     List<K> list = new List<K>(length);
     int i = 0;
     forEach(void _(K key, V value) {
@@ skipping 11 matching lines @@
     return list;
   }
 
   bool containsKey(K key) {
     return (_probeForLookup(key) != -1);
   }
 
   bool containsValue(V value) {
     int length = _values.length;
     for (int i = 0; i < length; i++) {
-      if ((_keys[i] !== null) && (_keys[i] !== _deletedKey)) {
+      if ((_keys[i] !== null) && (_keys[i] !== _DELETED_KEY)) {
         if (_values[i] == value) return true;
       }
     }
     return false;
   }
 }
 
 class HashSetImplementation<E extends Hashable> implements HashSet<E> {
 
   HashSetImplementation() {
@@ skipping 103 matching lines @@
 
   // TODO(4504458): Replace set_ with set.
   HashSetIterator(HashSetImplementation<E> set_)
     : _nextValidIndex = -1,
       _entries = set_._backingMap._keys {
     _advance();
   }
 
   bool hasNext() {
     if (_nextValidIndex >= _entries.length) return false;
-    if (_entries[_nextValidIndex] === HashMapImplementation._deletedKey) {
+    if (_entries[_nextValidIndex] === HashMapImplementation._DELETED_KEY) {
       // This happens in case the set was modified in the meantime.
       // A modification on the set may make this iterator misbehave,
       // but we should never return the sentinel.
       _advance();
     }
     return _nextValidIndex < _entries.length;
   }
 
   E next() {
     if (!hasNext()) {
       throw const NoMoreElementsException();
     }
     E res = _entries[_nextValidIndex];
     _advance();
     return res;
   }
 
   void _advance() {
     int length = _entries.length;
     var entry;
-    Object deletedKey = HashMapImplementation._deletedKey;
+    Object deletedKey = HashMapImplementation._DELETED_KEY;

[Ivan Posva, 2011/11/17 18:57:47]

ditto: var or _DeletedKeySentinel

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

Done.

     do {
       if (++_nextValidIndex >= length) break;
       entry = _entries[_nextValidIndex];
     } while ((entry === null) || (entry === deletedKey));
   }
 
   // The entries in the set. May contain null or the sentinel value.
   List<E> _entries;
 
   // The next valid index in [_entries] or the length of [entries_].
   // If it is the length of [_entries], calling [hasNext] on the
   // iterator will return false.
   int _nextValidIndex;
 }
+
+/**
+ * A singleton sentinel used to represent when a key is deleted from the map.
+ * We can't use [: const Object() :] as a sentinel because it would end up
+ * canonicalized and then we cannot distinguish the deleted key from the
+ * canonicalized Object().
+ */
+class _DeleteKeySentinel implements Hashable {
+  const _DeleteKeySentinel();
+  int hashCode() => 1;

[Ivan Posva, 2011/11/17 18:57:47]

Why do you need the hashCode() method here at all? Object did not have it and
you also should not need to implement Hashable.

[Siggi Cherem (dart-lang), 2011/11/17 20:00:21]

removed. I had some failing tests while implementing static/globals in frog
isolates and this is something I was playing with to help me debug. I didn't
mean to leave it here.

+}