Make the JSON decoder (parser) create Dart maps lazily

sdk/lib/_internal/lib/convert_patch.dart

Index: sdk/lib/_internal/lib/convert_patch.dart
diff --git a/sdk/lib/_internal/lib/convert_patch.dart b/sdk/lib/_internal/lib/convert_patch.dart
index 3fe44df3310836447752685827915eda098f7aae..923ef2cec1e57d7356da75bc14a22bb532af1885 100644
--- a/sdk/lib/_internal/lib/convert_patch.dart
+++ b/sdk/lib/_internal/lib/convert_patch.dart
@@ -7,6 +7,8 @@
 import 'dart:_js_helper' show patch;
 import 'dart:_foreign_helper' show JS;
 import 'dart:_interceptors' show JSExtendableArray;
+import 'dart:_internal' show MappedIterable;
+import 'dart:collection' show Maps, LinkedHashMap;
 
 /**
  * Parses [json] and builds the corresponding parsed JSON value.
@@ -37,7 +39,11 @@ _parseJson(String source, reviver(key, value)) {
     throw new FormatException(JS('String', 'String(#)', e));
   }
 
-  return _convertJsonToDart(parsed, reviver);
+  if (reviver == null) {
+    return _convertJsonToDartLazy(parsed);
+  } else {
+    return _convertJsonToDart(parsed, reviver);
+  }
 }
 
 /**
@@ -46,7 +52,6 @@ _parseJson(String source, reviver(key, value)) {
  * in-place.
  */
 _convertJsonToDart(json, reviver(key, value)) {
-
   var revive = reviver == null ? (key, value) => value : reviver;
 
   walk(e) {
@@ -59,7 +64,8 @@ _convertJsonToDart(json, reviver(key, value)) {
     // TODO(sra): Replace this test with cheaper '#.constructor === Array' when
     // bug 621 below is fixed.
     if (JS('bool', 'Object.getPrototypeOf(#) === Array.prototype', e)) {
-      var list = JS('JSExtendableArray', '#', e);  // Teach compiler the type is known.
+      // Teach compiler the type is known by passing it through a JS-expression.
+      var list = JS('JSExtendableArray', '#', e);
       // In-place update of the elements since JS Array is a Dart List.
       for (int i = 0; i < list.length; i++) {
         // Use JS indexing to avoid range checks.  We know this is the only
@@ -95,6 +101,232 @@ _convertJsonToDart(json, reviver(key, value)) {
   return revive(null, walk(json));
 }
 
+_convertJsonToDartLazy(object) {
+  // JavaScript null and undefined are represented as null.
+  if (object == null) return null;
+
+  // JavaScript string, number, bool already has the correct representation.
+  if (JS('bool', 'typeof # != "object"', object)) {
+    return object;
+  }
+
+  // This test is needed to avoid identifing '{"__proto__":[]}' as an array.
+  // TODO(sra): Replace this test with cheaper '#.constructor === Array' when
+  // bug https://code.google.com/p/v8/issues/detail?id=621 is fixed.
+  if (JS('bool', 'Object.getPrototypeOf(#) !== Array.prototype', object)) {
+    return new _JsonMap(object);
+  }
+
+  // Update the elements in place since JS arrays are Dart lists.
+  for (int i = 0; i < JS('int', '#.length', object); i++) {
+    // Use JS indexing to avoid range checks.  We know this is the only
+    // reference to the list, but the compiler will likely never be able to
+    // tell that this instance of the list cannot have its length changed by
+    // the reviver even though it later will be passed to the reviver at the
+    // outer level.
+    var item = JS('', '#[#]', object, i);
+    JS('', '#[#]=#', object, i, _convertJsonToDartLazy(item));
+  }
+  return object;
+}
+
+class _JsonMap implements LinkedHashMap {
+  // The original JavaScript object remains unchanged until
+  // the map is eventually upgraded, in which case we null it
+  // out to reclaim the memory used by it.
+  var _original;
+
+  // We keep track of the map entries that we have already
+  // processed by adding them to a separate JavaScript object.
+  var _processed = _newJavaScriptObject();
+
+  // If the data slot isn't null, it represents either the list
+  // of keys (for non-upgraded JSON maps) or the upgraded map.
+  var _data = null;
+
+  _JsonMap(this._original);
+
+  operator[](key) {
+    if (_isUpgraded) {
+      return _upgradedMap[key];
+    } else if (key is !String) {
+      return null;
+    } else {
+      var result = _getProperty(_processed, key);
+      if (_isUnprocessed(result)) result = _process(key);
+      return result;
+    }
+  }
+
+  int get length => _isUpgraded
+      ? _upgradedMap.length
+      : _computeKeys().length;
+
+  bool get isEmpty => length == 0;
+  bool get isNotEmpty => length > 0;
+
+  Iterable get keys {
+    if (_isUpgraded) return _upgradedMap.keys;
+    return _computeKeys().skip(0);
+  }
+
+  Iterable get values {
+    if (_isUpgraded) return _upgradedMap.values;
+    return new MappedIterable(_computeKeys(), (each) => this[each]);
+  }
+
+  operator[]=(key, value) {
+    if (_isUpgraded) {
+      _upgradedMap[key] = value;
+    } else if (containsKey(key)) {
+      _setProperty(_processed, key, value);
+      _setProperty(_original, key, null);  // Reclaim memory.
+    } else {
+      _upgrade()[key] = value;
+    }
+  }
+
+  void addAll(Map other) {
+    other.forEach((key, value) {
+      this[key] = value;
+    });
+  }
+
+  bool containsValue(value) {
+    if (_isUpgraded) return _upgradedMap.containsValue(value);
+    List<String> keys = _computeKeys();
+    for (int i = 0; i < keys.length; i++) {
+      String key = keys[i];
+      if (this[key] == value) return true;
+    }
+    return false;
+  }
+
+  bool containsKey(key) {
+    if (_isUpgraded) return _upgradedMap.containsKey(key);
+    if (key is !String) return false;
+    return _hasProperty(_original, key);
+  }
+
+  putIfAbsent(key, ifAbsent()) {
+    if (containsKey(key)) return this[key];
+    var value = ifAbsent();
+    this[key] = value;
+    return value;
+  }
+
+  remove(Object key) {
+    if (!_isUpgraded && !containsKey(key)) return null;
+    return _upgrade().remove(key);
+  }
+
+  void clear() {
+    if (_isUpgraded) {
+      _upgradedMap.clear();
+    } else {
+      if (_data != null) {
+        // Clear the list of keys to make sure we force
+        // a concurrent modification error if anyone is
+        // currently iterating over it.
+        _data.clear();
+      }
+      _original = _processed = null;
+      _data = {};
+    }
+  }
+
+  void forEach(void f(key, value)) {
+    if (_isUpgraded) return _upgradedMap.forEach(f);
+    List<String> keys = _computeKeys();
+    for (int i = 0; i < keys.length; i++) {
+      String key = keys[i];
+      f(key, this[key]);
+
+      // Check if invoking the callback function changed
+      // the key set. If so, throw an exception.
+      if (!identical(keys, _data)) {
+        throw new ConcurrentModificationError(this);
+      }
+    }
+  }
+
+  String toString() => Maps.mapToString(this);
+
+
+  // ------------------------------------------
+  // Private helper methods.
+  // ------------------------------------------
+
+  bool get _isUpgraded => _processed == null;
+
+  Map get _upgradedMap {
+    assert(_isUpgraded);
+    return _data;
+  }
+
+  List<String> _computeKeys() {
+    assert(!_isUpgraded);
+    List keys = _data;
+    if (keys == null) {
+      keys = _data = _getPropertyNames(_original);
+    }
+    return keys;
+  }
+
+  Map _upgrade() {
+    if (_isUpgraded) return _upgradedMap;
+
+    // Copy all the (key, value) pairs to a freshly allocated
+    // linked hash map thus preserving the ordering.
+    Map result = {};
+    List<String> keys = _computeKeys();
+    for (int i = 0; i < keys.length; i++) {
+      String key = keys[i];
+      result[key] = this[key];
+    }
+
+    // We only upgrade when we need to extend the map, so we can
+    // safely force a concurrent modification error in case
+    // someone is iterating over the map here.
+    if (keys.isEmpty) {
+      keys.add(null);
+    } else {
+      keys.clear();
+    }
+
+    // Clear out the associated JavaScript objects and mark the
+    // map as having been upgraded.
+    _original = _processed = null;
+    _data = result;
+    assert(_isUpgraded);
+    return result;
+  }
+
+  _process(String key) {
+    if (!_hasProperty(_original, key)) return null;
+    var result = _convertJsonToDartLazy(_getProperty(_original, key));
+    return _setProperty(_processed, key, result);
+  }
+
+
+  // ------------------------------------------
+  // Private JavaScript helper methods.
+  // ------------------------------------------
+
+  static bool _hasProperty(object, String key)
+      => JS('bool', 'Object.prototype.hasOwnProperty.call(#,#)', object, key);
+  static _getProperty(object, String key)
+      => JS('', '#[#]', object, key);
+  static _setProperty(object, String key, value)
+      => JS('', '#[#]=#', object, key, value);
+  static List _getPropertyNames(object)
+      => JS('JSExtendableArray', 'Object.keys(#)', object);
+  static bool _isUnprocessed(object)
+      => JS('bool', 'typeof(#)=="undefined"', object);
+  static _newJavaScriptObject()
+      => JS('=Object', 'Object.create(null)');
+}
+
 @patch
 class _Utf8Encoder {
   // Use Uint8List when supported on all platforms.