Initial version of a serialization framework

pkg/serialization/lib/src/polyfill_identity_set.dart

+// Copyright (c) 2012, 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.
+
+/**
+ * This provides identity-hashed collections used in serialization. It is a
+ * direct copy of the normal collections with a few small changes to support
+ * identity. As soon as there are proper identity-based collections this should
+ * be removed.
+ */
+
+// TODO(alanknight): Replace with proper identity collection. Issue 4161
+library identity_set;

[Jennifer Messerly, 2012/11/15 08:02:14]

I'm going to assume this is basically a copy+paste from hash_map_set and not
look at it too closely...

[Alan Knight, 2012/11/15 20:51:03]

Yes, it's a cut and paste with two or three very small changes.

+
+// Hash map implementation with open addressing and quadratic probing.
+class IdentityMap<K, 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 [_DELETED_KEY] of type
+  // [_DeletedKeySentinel].
+  // 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.
+  static const _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel();
+
+  // The initial capacity of a hash map.
+  static const int _INITIAL_CAPACITY = 8;  // must be power of 2
+
+  IdentityMap() {
+    _numberOfEntries = 0;
+    _numberOfDeleted = 0;
+    _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY);
+    _keys = new List(_INITIAL_CAPACITY);
+    _values = new List<V>(_INITIAL_CAPACITY);
+  }
+
+  factory IdentityMap.from(Map<K, V> other) {
+    Map<K, V> result = new IdentityMap<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) {
+    if (key == null) throw const NullPointerException();
+    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) {
+      // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
+      Object existingKey = _keys[hash];
+      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;
+        /// TODO(alanknight): Note this is changed to be identity (alanknight)
+      } else if (existingKey === key) {

[Jennifer Messerly, 2012/11/15 08:02:14]

fwiw, I think === is going away in favor of identical(x, y)

[Alan Knight, 2012/11/15 20:51:03]

I think I'll hope I can delete this code entirely before that becomes mandatory.

+        // The key is already in the map. Return its slot.
+        return hash;
+      } 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) {
+    if (key == null) throw const NullPointerException();
+    int hash = _firstProbe(key.hashCode, _keys.length);
+    int numberOfProbes = 1;
+    int initialHash = hash;
+    while (true) {
+      // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
+      Object existingKey = _keys[hash];
+      // 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.
+      // TODO(alanknight): Changed to be identity
+      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);
+    }
+  }
+
+  void _ensureCapacity() {
+    int newNumberOfEntries = _numberOfEntries + 1;
+    // Test if adding an element will reach the load limit.
+    if (newNumberOfEntries >= _loadLimit) {
+      _grow(_keys.length * 2);
+      return;
+    }
+
+    // Make sure that we don't have poor performance when a map
+    // contains lots of deleted entries: we _grow if
+    // there are more deleted entried than free entries.
+    int capacity = _keys.length;
+    int numberOfFreeOrDeleted = capacity - newNumberOfEntries;
+    int numberOfFree = numberOfFreeOrDeleted - _numberOfDeleted;
+    // assert(numberOfFree > 0);
+    if (_numberOfDeleted > numberOfFree) {
+      _grow(_keys.length);
+    }
+  }
+
+  static bool _isPowerOfTwo(int x) {
+    return ((x & (x - 1)) == 0);
+  }
+
+  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++) {
+      // [key] can be either of type [K] or [_DeletedKeySentinel].
+      Object key = oldKeys[i];
+      // If there is no key, we don't need to deal with the current slot.
+      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] === _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] = _DELETED_KEY;
+      _numberOfDeleted++;
+      return value;
+    }
+    return null;
+  }
+
+  bool get 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++) {
+      var key = _keys[i];
+      if ((key !== null) && (key !== _DELETED_KEY)) {
+        f(key, _values[i]);
+      }
+    }
+  }
+
+
+  Collection<K> get keys {
+    List<K> list = new List<K>(length);
+    int i = 0;
+    forEach(void _(K key, V value) {
+      list[i++] = key;
+    });
+    return list;
+  }
+
+  Collection<V> get values {
+    List<V> list = new List<V>(length);
+    int i = 0;
+    forEach(void _(K key, V value) {
+      list[i++] = value;
+    });
+    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++) {
+      var key = _keys[i];
+      if ((key !== null) && (key !== _DELETED_KEY)) {
+        if (_values[i] == value) return true;
+      }
+    }
+    return false;
+  }
+
+  String toString() {
+    return Maps.mapToString(this);
+  }
+}
+
+class IdentitySet<E > implements HashSet<E> {
+
+  IdentitySet() {
+    _backingMap = new IdentityMap<E, E>();
+  }
+
+  factory IdentitySet.from(Iterable<E> other) {
+    Set<E> set = new IdentitySet<E>();
+    for (final e in other) {
+      set.add(e);
+    }
+    return set;
+  }
+
+  void clear() {
+    _backingMap.clear();
+  }
+
+  void add(E value) {
+    _backingMap[value] = value;
+  }
+
+  bool contains(E value) {
+    return _backingMap.containsKey(value);
+  }
+
+  bool remove(E value) {
+    if (!_backingMap.containsKey(value)) return false;
+    _backingMap.remove(value);
+    return true;
+  }
+
+  void addAll(Collection<E> collection) {
+    collection.forEach(void _(E value) {
+      add(value);
+    });
+  }
+
+  Set<E> intersection(Collection<E> collection) {
+    Set<E> result = new Set<E>();
+    collection.forEach(void _(E value) {
+      if (contains(value)) result.add(value);
+    });
+    return result;
+  }
+
+  bool isSubsetOf(Collection<E> other) {
+    return new Set<E>.from(other).containsAll(this);
+  }
+
+  void removeAll(Collection<E> collection) {
+    collection.forEach(void _(E value) {
+      remove(value);
+    });
+  }
+
+  bool containsAll(Collection<E> collection) {
+    return collection.every(bool _(E value) {
+      return contains(value);
+    });
+  }
+
+  void forEach(void f(E element)) {
+    _backingMap.forEach(void _(E key, E value) {
+      f(key);
+    });
+  }
+
+  Set map(f(E element)) {
+    Set result = new Set();
+    _backingMap.forEach(void _(E key, E value) {
+      result.add(f(key));
+    });
+    return result;
+  }
+
+  dynamic reduce(dynamic initialValue,
+                 dynamic combine(dynamic previousValue, E element)) {
+    return Collections.reduce(this, initialValue, combine);
+  }
+
+  Set<E> filter(bool f(E element)) {
+    Set<E> result = new Set<E>();
+    _backingMap.forEach(void _(E key, E value) {
+      if (f(key)) result.add(key);
+    });
+    return result;
+  }
+
+  bool every(bool f(E element)) {
+    Collection<E> keys = _backingMap.keys;
+    return keys.every(f);
+  }
+
+  bool some(bool f(E element)) {
+    Collection<E> keys = _backingMap.keys;
+    return keys.some(f);
+  }
+
+  bool get isEmpty {
+    return _backingMap.isEmpty;
+  }
+
+  int get length {
+    return _backingMap.length;
+  }
+
+  Iterator<E> iterator() {
+    return new HashSetIterator<E>(this);
+  }
+
+  String toString() {
+    return Collections.collectionToString(this);
+  }
+
+  // The map backing this set. The associations in this map are all
+  // of the form element -> element. If a value is not in the map,
+  // then it is not in the set.
+  IdentityMap<E, E> _backingMap;
+}
+
+class HashSetIterator<E> implements Iterator<E> {
+
+  // TODO(4504458): Replace set_ with set.
+  HashSetIterator(IdentitySet<E> set_)
+    : _nextValidIndex = -1,
+      _entries = set_._backingMap._keys {
+    _advance();
+  }
+
+  bool get hasNext {
+    if (_nextValidIndex >= _entries.length) return false;
+    if (_entries[_nextValidIndex] === IdentityMap._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 new StateError("No more elements");
+    }
+    E res = _entries[_nextValidIndex];
+    _advance();
+    return res;
+  }
+
+  void _advance() {
+    int length = _entries.length;
+    var entry;
+    final deletedKey = IdentityMap._DELETED_KEY;
+    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 _DeletedKeySentinel {
+  const _DeletedKeySentinel();
+}
+
+/************************************************************************/
+/** Code copied from Maps.dart and Collection.dart */
+
+
+// Copyright (c) 2012, 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.
+
+/*
+ * Helper class which implements complex [Map] operations
+ * in term of basic ones ([Map.getKeys], [Map.operator []],
+ * [Map.operator []=] and [Map.remove].)  Not all methods are
+ * necessary to implement each particular operation.
+ */
+class Maps {
+  static bool containsValue(Map map, value) {
+    for (final v in map.values) {
+      if (value == v) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  static bool containsKey(Map map, key) {
+    for (final k in map.keys) {
+      /// ################# Changed to be identity (alanknight)
+      if (key === k) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  static putIfAbsent(Map map, key, ifAbsent()) {
+    if (map.containsKey(key)) {
+      return map[key];
+    }
+    final v = ifAbsent();
+    map[key] = v;
+    return v;
+  }
+
+  static clear(Map map) {
+    for (final k in map.keys) {
+      map.remove(k);
+    }
+  }
+
+  static forEach(Map map, void f(key, value)) {
+    for (final k in map.keys) {
+      f(k, map[k]);
+    }
+  }
+
+  static Collection getValues(Map map) {
+    final result = [];
+    for (final k in map.keys) {
+      result.add(map[k]);
+    }
+    return result;
+  }
+
+  static int length(Map map) => map.keys.length;
+
+  static bool isEmpty(Map map) => length(map) == 0;
+
+  /**
+   * Returns a string representing the specified map. The returned string
+   * looks like this: [:'{key0: value0, key1: value1, ... keyN: valueN}':].
+   * The value returned by its [toString] method is used to represent each
+   * key or value.
+   *
+   * If the map collection contains a reference to itself, either
+   * directly as a key or value, or indirectly through other collections
+   * or maps, the contained reference is rendered as [:'{...}':]. This
+   * prevents the infinite regress that would otherwise occur. So, for example,
+   * calling this method on a map whose sole entry maps the string key 'me'
+   * to a reference to the map would return [:'{me: {...}}':].
+   *
+   * A typical implementation of a map's [toString] method will
+   * simply return the results of this method applied to the collection.
+   */
+  static String mapToString(Map m) {
+    var result = new StringBuffer();
+    _emitMap(m, result, new List());
+    return result.toString();
+  }
+
+  /**
+   * Appends a string representing the specified map to the specified
+   * string buffer. The string is formatted as per [mapToString].
+   * The [:visiting:] list contains references to all of the enclosing
+   * collections and maps (which are currently in the process of being
+   * emitted into [:result:]). The [:visiting:] parameter allows this method
+   * to generate a [:'[...]':] or [:'{...}':] where required. In other words,
+   * it allows this method and [_emitCollection] to identify recursive maps
+   * and collections.
+   */
+  static void _emitMap(Map m, StringBuffer result, List visiting) {
+    visiting.add(m);
+    result.add('{');
+
+    bool first = true;
+    m.forEach((k, v) {
+      if (!first) {
+        result.add(', ');
+      }
+      first = false;
+      Collections._emitObject(k, result, visiting);
+      result.add(': ');
+      Collections._emitObject(v, result, visiting);
+    });
+
+    result.add('}');
+    visiting.removeLast();
+  }
+}
+
+/***********************************************************************
+ * Collections.dart
+ */
+// Copyright (c) 2012, 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.
+
+/**
+ * The [Collections] class implements static methods useful when
+ * writing a class that implements [Collection] and the [iterator]
+ * method.
+ */
+class Collections {
+  static void forEach(Iterable iterable, void f(o)) {
+    for (final e in iterable) {
+      f(e);
+    }
+  }
+
+  static bool some(Iterable iterable, bool f(o)) {
+    for (final e in iterable) {
+      if (f(e)) return true;
+    }
+    return false;
+  }
+
+  static bool every(Iterable iterable, bool f(o)) {
+    for (final e in iterable) {
+      if (!f(e)) return false;
+    }
+    return true;
+  }
+
+  static List map(Iterable source, List destination, f(o)) {
+    for (final e in source) {
+      destination.add(f(e));
+    }
+    return destination;
+  }
+
+  static dynamic reduce(Iterable iterable,
+                        dynamic initialValue,
+                        dynamic combine(dynamic previousValue, element)) {
+    for (final element in iterable) {
+      initialValue = combine(initialValue, element);
+    }
+    return initialValue;
+  }
+
+  static List filter(Iterable source, List destination, bool f(o)) {
+    for (final e in source) {
+      if (f(e)) destination.add(e);
+    }
+    return destination;
+  }
+
+  static bool isEmpty(Iterable iterable) {
+    return !iterable.iterator().hasNext;
+  }
+
+  // TODO(jjb): visiting list should be an identityHashSet when it exists
+
+  /**
+   * Returns a string representing the specified collection. If the
+   * collection is a [List], the returned string looks like this:
+   * [:'[element0, element1, ... elementN]':]. The value returned by its
+   * [toString] method is used to represent each element. If the specified
+   * collection is not a list, the returned string looks like this:
+   * [:{element0, element1, ... elementN}:]. In other words, the strings
+   * returned for lists are surrounded by square brackets, while the strings
+   * returned for other collections are surrounded by curly braces.
+   *
+   * If the specified collection contains a reference to itself, either
+   * directly or indirectly through other collections or maps, the contained
+   * reference is rendered as [:'[...]':] if it is a list, or [:'{...}':] if
+   * it is not. This prevents the infinite regress that would otherwise occur.
+   * So, for example, calling this method on a list whose sole element is a
+   * reference to itself would return [:'[[...]]':].
+   *
+   * A typical implementation of a collection's [toString] method will
+   * simply return the results of this method applied to the collection.
+   */
+  static String collectionToString(Collection c) {
+    var result = new StringBuffer();
+    _emitCollection(c, result, new List());
+    return result.toString();
+  }
+
+  /**
+   * Appends a string representing the specified collection to the specified
+   * string buffer. The string is formatted as per [collectionToString].
+   * The [:visiting:] list contains references to all of the enclosing
+   * collections and maps (which are currently in the process of being
+   * emitted into [:result:]). The [:visiting:] parameter allows this method to
+   * generate a [:'[...]':] or [:'{...}':] where required. In other words,
+   * it allows this method and [_emitMap] to identify recursive collections
+   * and maps.
+   */
+  static void _emitCollection(Collection c, StringBuffer result, List visiting) {
+    visiting.add(c);
+    bool isList = c is List;
+    result.add(isList ? '[' : '{');
+
+    bool first = true;
+    for (var e in c) {
+      if (!first) {
+        result.add(', ');
+      }
+      first = false;
+      _emitObject(e, result, visiting);
+    }
+
+    result.add(isList ? ']' : '}');
+    visiting.removeLast();
+  }
+
+  /**
+   * Appends a string representing the specified object to the specified
+   * string buffer. If the object is a [Collection] or [Map], it is formatted
+   * as per [collectionToString] or [mapToString]; otherwise, it is formatted
+   * by invoking its own [toString] method.
+   *
+   * The [:visiting:] list contains references to all of the enclosing
+   * collections and maps (which are currently in the process of being
+   * emitted into [:result:]). The [:visiting:] parameter allows this method
+   * to generate a [:'[...]':] or [:'{...}':] where required. In other words,
+   * it allows this method and [_emitCollection] to identify recursive maps
+   * and collections.
+   */
+  static void _emitObject(Object o, StringBuffer result, List visiting) {
+    if (o is Collection) {
+      if (_containsRef(visiting, o)) {
+        result.add(o is List ? '[...]' : '{...}');
+      } else {
+        _emitCollection(o, result, visiting);
+      }
+    } else if (o is Map) {
+      if (_containsRef(visiting, o)) {
+        result.add('{...}');
+      } else {
+        Maps._emitMap(o, result, visiting);
+      }
+    } else { // o is neither a collection nor a map
+      result.add(o);
+    }
+  }
+
+  /**
+   * Returns true if the specified collection contains the specified object
+   * reference.
+   */
+  static _containsRef(Collection c, Object ref) {
+    for (var e in c) {
+      if (e === ref) return true;
+    }
+    return false;
+  }
+}
+