blob: 846f7168ad22d458b253ceb919d57219b2476d14 [file] [log] [blame]
// 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.
import 'dart:collection';
import 'package:collection/collection.dart';
import 'yaml_node.dart';
/// Returns a [Map] that compares its keys based on [deepEquals].
Map/*<K, V>*/ deepEqualsMap/*<K, V>*/() =>
new HashMap(equals: deepEquals, hashCode: deepHashCode);
/// Returns whether two objects are structurally equivalent.
/// 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;
try {
if (obj1 is List && obj2 is List) {
return _listEquals(obj1, obj2);
} else if (obj1 is Map && obj2 is Map) {
return _mapEquals(obj1, obj2);
} else if (obj1 is num && obj2 is num) {
return _numEquals(obj1, obj2);
} else {
return obj1 == obj2;
} finally {
/// Returns whether [list1] and [list2] are structurally equal.
bool _listEquals(List list1, List list2) {
if (list1.length != list2.length) return false;
for (var i = 0; i < list1.length; i++) {
if (!equals(list1[i], list2[i])) return false;
return true;
/// Returns whether [map1] and [map2] are structurally equal.
bool _mapEquals(Map map1, Map map2) {
if (map1.length != map2.length) return false;
for (var key in map1.keys) {
if (!map2.containsKey(key)) return false;
if (!equals(map1[key], map2[key])) return false;
return true;
/// 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.
int deepHashCode(obj) {
var parents = [];
_deepHashCode(value) {
if (parents.any((parent) => identical(parent, value))) return -1;
try {
if (value is Map) {
var equality = const UnorderedIterableEquality();
return equality.hash( ^
} else if (value is Iterable) {
return const IterableEquality().hash(;
} else if (value is YamlScalar) {
return value.value.hashCode;
} else {
return value.hashCode;
} finally {
return _deepHashCode(obj);