Attach source range information to parsed YAML nodes.

pkg/yaml/lib/src/equality.dart

-// 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
 /// detection.
 class _DeepEquals {
   final _parents1 = [];
   final _parents2 = [];
 
   /// 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]);
       var loop2 = identical(obj2, _parents2[i]);
       // If both structures loop in the same place, they're equal at that point
       // in the structure. If one loops and the other doesn't, they're not
       // equal.
       if (loop1 && loop2) return true;
       if (loop1 || loop2) return false;
     }
@@ skipping 41 matching lines @@
 
   /// Returns whether two numbers are equivalent.
   ///
   /// This differs from `n1 == n2` in that it considers `NaN` to be equal to
   /// itself.
   bool _numEquals(num n1, num n2) {
     if (n1.isNaN && n2.isNaN) return true;
     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);
+}