recursiveEqual method

bool recursiveEqual(Value rhs)

Compare lhs and rhs for equality, in a way that traverses down the tree when it finds a list or map. For any other type, this just calls through to the regular Equality method.

Note that this works correctly for loops (maintaining a visited list to avoid recursing indefinitely).

Implementation

bool recursiveEqual(Value rhs) {
  var toDo = <ValuePair>[];
  var visited = <ValuePair>{};
  toDo.add(ValuePair(this, rhs));

  while (toDo.isNotEmpty) {
    var pair = toDo.removeLast();
    visited.add(pair);

    if (pair.a is ValList?) {
      var listA = pair.a as ValList?;
      var listB = pair.b as ValList?;
      if (listB == null) return false;
      if (identical(listA, listB)) continue;
      int aCount = listA!.values.length;
      if (aCount != listB.values.length) return false;
      for (int i = 0; i < aCount; i++) {
        var newPair = ValuePair(listA.values[i], listB.values[i]);
        if (!visited.contains(newPair)) toDo.add(newPair);
      }
    } else if (pair.a is ValMap?) {
      var mapA = pair.a as ValMap?;
      var mapB = pair.b as ValMap?;
      if (mapB == null) return false;
      if (identical(mapA, mapB)) continue;
      if (mapA!.map.length != mapB.map.length) return false;
      for (var kv in mapA.map.entries) {
        var valFromB = mapB.map[kv.key];
        if (valFromB == null && !mapB.map.containsKey(kv.key)) {
          return false;
        }
        var newPair = ValuePair(kv.value, valFromB);
        if (!visited.contains(newPair)) toDo.add(newPair);
      }
    } else if (pair.a == null || pair.b == null) {
      if (pair.a == null || pair.b == null) return false;
    } else {
      // No other types can recurse, so we can safely do:
      if (pair.a!.equality(pair.b) == 0) return false;
    }
  }

  // If we clear out our toDo list without finding anything unequal,
  // then the values as a whole must be equal.
  return true;
}