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

sdk/lib/html/html_common/conversions_dartium.dart

 part of html_common;
 
 convertDartToNative_PrepareForStructuredClone(value) =>
     new _StructuredCloneDartium().convertDartToNative_PrepareForStructuredClone(value);
 
 convertNativeToDart_AcceptStructuredClone(object, {mustCopy: false}) =>
     new _AcceptStructuredCloneDartium().convertNativeToDart_AcceptStructuredClone(object, mustCopy: mustCopy);
 
 class _StructuredCloneDartium extends _StructuredClone {
   newJsMap() => new js.JsObject(js.context["Object"]);
   putIntoMap(map, key, value) => map[key] = value;
   // TODO(alanknight): Don't create two extra lists to get a fixed-length JS list.
   newJsList(length) => new js.JsArray.from(new List(length));
   cloneNotRequired(e) => e is js.JsObject;
 }
 
-class _AcceptStructuredCloneDartium extends _AcceptStructuredClone {
+/// A version of _AcceptStructuredClone, but using a different algorithm
+/// so we can take advantage of an identity HashMap on Dartium without
+/// the bad side-effect of modifying the JS source objects if we do the same in
+/// dart2js.
+///
+/// This no longer inherits anything from _AcceptStructuredClone
+/// and is never used polymorphically with it, so it doesn't inherit.
+class _AcceptStructuredCloneDartium {
   newDartList(length) => new List(length);
 
   // JsObjects won't be identical, but will be equal only if the underlying
   // Js entities are identical.
   bool identicalInJs(a, b) =>
       (a is js.JsObject) ? a == b : identical(a, b);
 
   void forEachJsField(jsObject, action) {
     var keys = js.context["Object"].callMethod("keys", [jsObject]);
     for (var key in keys) {
       action(key, jsObject[key]);
     }
   }
+
+  // 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;
+
+  Object findSlot(value) {
+    return clones.putIfAbsent(value, () => null);
+  }
+
+  writeSlot(original, x) { clones[original] = x; }
+
+  walk(e) {
+    if (e == null) return e;
+    if (e is bool) return e;
+    if (e is num) return e;
+    if (e is String) return e;
+
+    if (isJavaScriptDate(e)) {
+      return convertNativeToDart_DateTime(e);
+    }
+
+    if (isJavaScriptRegExp(e)) {
+      // TODO(sra).
+      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 copy = findSlot(e);
+      if (copy != null) return copy;
+      copy = {};
+
+      writeSlot(e, copy);
+      forEachJsField(e, (key, value) => copy[key] = walk(value));
+      return copy;
+    }
+
+    if (isJavaScriptArray(e)) {
+      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(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;
+  }
+
+  convertNativeToDart_AcceptStructuredClone(object, {mustCopy: false}) {
+    this.mustCopy = mustCopy;
+    var copy = walk(object);
+    return copy;
+  }
 }
 
 final _dateConstructor = js.context["Date"];
 final _regexConstructor = js.context["RegExp"];
 
 bool isJavaScriptDate(value) => value is js.JsObject && value.instanceof(_dateConstructor);
 bool isJavaScriptRegExp(value) => value is js.JsObject && value.instanceof(_regexConstructor);
 bool isJavaScriptArray(value) => value is js.JsArray;
 
 final _object = js.context["Object"];
@@ skipping 362 matching lines @@
       {'type': dartClass, 'extends': extendTag != null ? extendTag : "" };
 }
 
 Type getCustomElementType(object) {
   var entry = getCustomElementEntry(object);
   if (entry != null) {
     return entry['type'];
   }
   return null;
 }