Attach source range information to parsed YAML nodes.

pkg/yaml/lib/src/equality.dart

Index: pkg/yaml/lib/src/equality.dart
diff --git a/pkg/yaml/lib/src/deep_equals.dart b/pkg/yaml/lib/src/equality.dart
similarity index 59%
rename from pkg/yaml/lib/src/deep_equals.dart
rename to pkg/yaml/lib/src/equality.dart
index 68fb236a078e11594d979ad67b9a8f316e87c840..540813599c1f19c5d3b150749f6fb441bcd8a4dd 100644
--- a/pkg/yaml/lib/src/deep_equals.dart
+++ b/pkg/yaml/lib/src/equality.dart
@@ -1,13 +1,22 @@
-// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// Copyright (c) 2014, 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.
 
-library yaml.deep_equals;
+library yaml.equality;
+
+import 'dart:collection';
+
+import 'package:collection/collection.dart';
+
+import 'yaml_node.dart';
+
+/// Returns a [Map] that compares its keys based on [deepEquals].
+Map deepEqualsMap() => new HashMap(equals: deepEquals, hashCode: deepHashCode);
 
 /// Returns whether two objects are structurally equivalent.
 ///
-/// This considers `NaN` values to be equivalent. It also handles
-/// self-referential structures.
+/// This considers `NaN` values to be equivalent, handles self-referential
+/// structures, and considers [YamlScalar]s to be equal to their values.
 bool deepEquals(obj1, obj2) => new _DeepEquals().equals(obj1, obj2);
 
 /// A class that provides access to the list of parent objects used for loop
@@ -18,6 +27,9 @@ class _DeepEquals {
 
   /// Returns whether [obj1] and [obj2] are structurally equivalent.
   bool equals(obj1, obj2) {
+    if (obj1 is YamlScalar) obj1 = obj1.value;
+    if (obj2 is YamlScalar) obj2 = obj2.value;
+
     // _parents1 and _parents2 are guaranteed to be the same size.
     for (var i = 0; i < _parents1.length; i++) {
       var loop1 = identical(obj1, _parents1[i]);
@@ -79,3 +91,36 @@ class _DeepEquals {
     return n1 == n2;
   }
 }
+
+/// Returns a hash code for [obj] such that structurally equivalent objects
+/// will have the same hash code.
+///
+/// This supports deep equality for maps and lists, including those with
+/// self-referential structures, and returns the same hash code for
+/// [YamlScalar]s and their values.

[Bob Nystrom, 2014/06/03 00:33:14]

This has scary perf implications. Can we cache this inside YamlList and YamlMap?

[nweiz, 2014/06/03 02:03:21]

Not really; they don't override [hashCode], a custom version is defined for the
inner map.

I'm not too worried about people putting really complex objects in map keys, but
one possibility would be to have the hash code just hash the number of child
objects, and rely on equality to disambiguate between similarly-sized objects.

+int deepHashCode(obj) {
+  var parents = [];
+
+  _deepHashCode(value) {
+    if (parents.any((parent) => identical(parent, value))) return -1;
+
+    parents.add(value);
+    try {
+      if (value is Map) {
+        var equality = const UnorderedIterableEquality();
+        return equality.hash(value.keys.map(_deepHashCode)) ^
+            equality.hash(value.values.map(_deepHashCode));
+      } else if (value is Iterable) {
+        return const IterableEquality().hash(value.map(deepHashCode));
+      } else if (value is YamlScalar) {
+        return value.value.hashCode;
+      } else {

[Bob Nystrom, 2014/06/03 00:33:14]

Nit, may need to handle NaN here too. :-/

[nweiz, 2014/06/03 02:03:21]

NaN always has the same hash code, even though it's not equal to itself.

+        return value.hashCode;
+      }
+    } finally {
+      parents.removeLast();
+    }
+  }
+
+  return _deepHashCode(obj);
+}