Remove O(n^2) loop in serialized script value conversions

sdk/lib/html/html_common/conversions.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.
 
 
 // Conversions for IDBKey.
 //
 // Per http://www.w3.org/TR/IndexedDB/#key-construct
 //
 // "A value is said to be a valid key if it is one of the following types: Array
@@ skipping 40 matching lines @@
  * described at
  * http://www.whatwg.org/specs/web-apps/current-work/multipage/common-dom-interfaces.html#structured-clone
  * https://www.khronos.org/registry/typedarray/specs/latest/#9
  *
  * Since the result of this function is expected to be passed only to JavaScript
  * operations that perform the structured clone algorithm which does not mutate
  * its output, the result may share structure with the input [value].
  */
 abstract class _StructuredClone {
 
-  // TODO(sra): Replace slots with identity hash table.
-  var values = [];
-  var copies = [];  // initially 'null', 'true' during initial DFS, then a copy.
+  // Keep track of the clones, keyed by the original object. If we're
+  // not copying, these may be the same.
+  var clones = new HashMap.identity();

[sra1, 2016/03/22 00:54:21]

Be careful here.

The implementation of identityHashCode puts a property on the object.
The effect is to modify the data you are serializing.
It might be necessary to change how identity hash codes work.
Is it possible to add a property in such a way that it does not pass through all
the APIs that use structured clones?

[Alan Knight, 2016/03/22 18:00:01]

OK, I moved the code to use an identity map down into the Dartium-specific
version, and left the general/dart2js version as is. So it shares less code but
avoids the issue of polluting JS objects with the identityHash property. It's
only really a performance problem on Dartium, on accepting a structured clone.

 
-  int findSlot(value) {
-    int length = values.length;
-    for (int i = 0; i < length; i++) {
-      if (identical(values[i], value)) return i;
-    }
-    values.add(value);
-    copies.add(null);
-    return length;
+  Object findSlot(value) {
+    return clones.putIfAbsent(value, () => null);
   }
-  readSlot(int i) => copies[i];
-  writeSlot(int i, x) { copies[i] = x; }
+  readSlot(Object original) => clones[original];
+  writeSlot(Object original, clone) { clones[original] = clone; }
   cleanupSlots() {}  // Will be needed if we mark objects with a property.
   bool cloneNotRequired(object);
   newJsMap();
   newJsList(length);
   void putIntoMap(map, key, value);
 
   // Returns the input, or a clone of the input.
   walk(e) {
     if (e == null) return e;
     if (e is bool) return e;
@@ skipping 16 matching lines @@
 
     if (e is File) return e;
     if (e is Blob) return e;
     if (e is FileList) return e;
 
     // TODO(sra): Firefox: How to convert _TypedImageData on the other end?
     if (e is ImageData) return e;
     if (cloneNotRequired(e)) return e;
 
     if (e is Map) {
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
       copy = newJsMap();
-      writeSlot(slot, copy);
+      writeSlot(e, copy);
       e.forEach((key, value) {
         putIntoMap(copy, key, walk(value));
       });
       return copy;
     }
 
     if (e is List) {
       // Since a JavaScript Array is an instance of Dart List it is tempting
       // in dart2js to avoid making a copy of the list if there is no need
       // to copy anything reachable from the array.  However, the list may have
       // non-native properties or methods from interceptors and such, e.g.
       // an immutability marker. So we  had to stop doing that.
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
-      copy = copyList(e, slot);
+      copy = copyList(e);
       return copy;
     }
 
     throw new UnimplementedError('structured clone of other type');
   }
 
-  copyList(List e, int slot) {
+  copyList(List e) {
     int i = 0;
     int length = e.length;
     var copy = newJsList(length);
-    writeSlot(slot, copy);
+    writeSlot(e, copy);
     for ( ; i < length; i++) {
       copy[i] = walk(e[i]);
     }
     return copy;
   }
 
   convertDartToNative_PrepareForStructuredClone(value) {
     var copy = walk(value);
     cleanupSlots();
     return copy;
@@ skipping 13 matching lines @@
  * If necessary, JavaScript Dates are converted into Dart Dates.
  *
  * If [mustCopy] is [:true:], the entire object is copied and the original input
  * is not mutated.  This should be the case where Dart and JavaScript code can
  * access the value, for example, via multiple event listeners for
  * MessageEvents.  Mutating the object to make it more 'Dart-like' would corrupt
  * the value as seen from the JavaScript listeners.
  */
 abstract class _AcceptStructuredClone {
 
-  // TODO(sra): Replace slots with identity hash table.
-  var values = [];
-  var copies = [];  // initially 'null', 'true' during initial DFS, then a copy.
+  // Keep track of the clones, keyed by the original object. If we're
+  // not copying, these may be the same.
+  var clones = new HashMap.identity();
   bool mustCopy = false;
 
-  int findSlot(value) {
-    int length = values.length;
-    for (int i = 0; i < length; i++) {
-      if (identicalInJs(values[i], value)) return i;
-    }
-    values.add(value);
-    copies.add(null);
-    return length;
+  Object findSlot(value) {
+    return clones.putIfAbsent(value, () => null);
   }
 
   /// Are the two objects identical, but taking into account that two JsObject
   /// wrappers may not be identical, but their underlying Js Object might be.
   bool identicalInJs(a, b);
-  readSlot(int i) => copies[i];
-  writeSlot(int i, x) { copies[i] = x; }
+  writeSlot(original, x) { clones[original] = x; }
 
   /// Iterate over the JS properties.
   forEachJsField(object, action);
 
   /// Create a new Dart list of the given length. May create a native List or
   /// a JsArray, depending if we're in Dartium or dart2js.
   newDartList(length);
 
   walk(e) {
     if (e == null) return e;
@@ skipping 10 matching lines @@
       throw new UnimplementedError('structured clone of RegExp');
     }
 
     if (isJavaScriptPromise(e)) {
       return convertNativePromiseToDartFuture(e);
     }
 
     if (isJavaScriptSimpleObject(e)) {
       // TODO(sra): If mustCopy is false, swizzle the prototype for one of a Map
       // implementation that uses the properies as storage.
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
       copy = {};
 
-      writeSlot(slot, copy);
+      writeSlot(e, copy);
       forEachJsField(e, (key, value) => copy[key] = walk(value));
       return copy;
     }
 
     if (isJavaScriptArray(e)) {
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
 
       int length = e.length;
       // Since a JavaScript Array is an instance of Dart List, we can modify it
       // in-place unless we must copy.
       copy = mustCopy ? newDartList(length) : e;
-      writeSlot(slot, copy);
+      writeSlot(e, copy);
 
       for (int i = 0; i < length; i++) {
         copy[i] = walk(e[i]);
       }
       return copy;
     }
 
     // Assume anything else is already a valid Dart object, either by having
     // already been processed, or e.g. a clonable native class.
     return e;
@@ skipping 98 matching lines @@
 const String _serializedScriptValue =
     'num|String|bool|'
     'JSExtendableArray|=Object|'
     'Blob|File|NativeByteBuffer|NativeTypedData'
     // TODO(sra): Add Date, RegExp.
     ;
 const annotation_Creates_SerializedScriptValue =
     const Creates(_serializedScriptValue);
 const annotation_Returns_SerializedScriptValue =
     const Returns(_serializedScriptValue);