pkgs/checks/lib/src/collection_equality.dart

// Copyright (c) 2023, 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 '../context.dart';

/// Returns a descriptive `which` for a rejection if the elements of [actual]
/// are unequal to the elements of [expected].
///
/// {@template deep_collection_equals}
/// Elements, keys, or values within [expected] which are a collections are
/// deeply compared for equality with a collection in the same position within
/// [actual]. Elements which are collection types are not compared with the
/// native identity based equality or custom equality operator overrides.
///
/// Elements, keys, or values within [expected] which are [Condition]
/// instances are run against the value in the same position within [actual].
/// Condition instances must be a `Condition<Object?>` or
/// `Condition<dynamic>` and may not use a more specific generic.
/// Use `Condition.it<Object?>()..isA<Type>()` to check expectations for
/// specific element types.
///
/// Elements and values within [expected] which are any other type are compared
/// using `operator ==` equality.
///
/// Deep equality checks for [Map] instances depend on the structure of the
/// expected map.
/// If all keys of the expectation are non-collection and non-condition values
/// the keys are compared through the map instances with [Map.containsKey].
///
/// If any key in the expectation is a `Condition` or a collection type the
/// map will be compared as a [Set] of entries where both the key and value must
/// match.
///
/// Comparing sets or maps with complex keys has a runtime which is polynomial
/// on the the size of those collections.
/// These comparisons do not use [Set.contains] or [Map.containsKey],
/// and there will not be runtime benefits from hashing.
/// Custom collection behavior of `contains` is ignored.
/// For example, it is not possible to distinguish between a `Set` and a
/// `Set.identity`.
///
/// Collections may be nested to a maximum depth of 1000. Recursive collections
/// are not allowed.
/// {@endtemplate}
Iterable<String>? deepCollectionEquals(Object actual, Object expected) {
  try {
    return _deepCollectionEquals(actual, expected, 0);
  } on _ExceededDepthError {
    return ['exceeds the depth limit of $_maxDepth'];
  }
}

const _maxDepth = 1000;

class _ExceededDepthError extends Error {}

Iterable<String>? _deepCollectionEquals(
  Object actual,
  Object expected,
  int depth,
) {
  assert(actual is Iterable || actual is Map);
  assert(expected is Iterable || expected is Map);

  final queue = Queue.of([_Search(_Path.root(), actual, expected, depth)]);
  while (queue.isNotEmpty) {
    final toCheck = queue.removeFirst();
    final currentActual = toCheck.actual;
    final currentExpected = toCheck.expected;
    final path = toCheck.path;
    final currentDepth = toCheck.depth;
    Iterable<String>? rejectionWhich;
    if (currentExpected is Set) {
      rejectionWhich = _findSetDifference(
        currentActual,
        currentExpected,
        path,
        currentDepth,
      );
    } else if (currentExpected is Iterable) {
      rejectionWhich = _findIterableDifference(
        currentActual,
        currentExpected,
        path,
        queue,
        currentDepth,
      );
    } else {
      currentExpected as Map;
      rejectionWhich = _findMapDifference(
        currentActual,
        currentExpected,
        path,
        queue,
        currentDepth,
      );
    }
    if (rejectionWhich != null) return rejectionWhich;
  }
  return null;
}

List<String>? _findIterableDifference(
  Object? actual,
  Iterable<Object?> expected,
  _Path path,
  Queue<_Search> queue,
  int depth,
) {
  if (actual is! Iterable) {
    return ['${path}is not an Iterable'];
  }
  var actualIterator = actual.iterator;
  var expectedIterator = expected.iterator;
  for (var index = 0; ; index++) {
    var actualNext = actualIterator.moveNext();
    var expectedNext = expectedIterator.moveNext();
    if (!expectedNext && !actualNext) break;
    if (!expectedNext) {
      return [
        '${path}has more elements than expected',
        'expected an iterable with $index element(s)',
      ];
    }
    if (!actualNext) {
      return [
        '${path}has too few elements',
        'expected an iterable with at least ${index + 1} element(s)',
      ];
    }
    final difference = _compareValue(
      actualIterator.current,
      expectedIterator.current,
      path,
      index,
      queue,
      depth,
    );
    if (difference != null) return difference;
  }
  return null;
}

List<String>? _compareValue(
  Object? actualValue,
  Object? expectedValue,
  _Path path,
  Object? pathAppend,
  Queue<_Search> queue,
  int depth,
) {
  if (expectedValue is Iterable || expectedValue is Map) {
    if (depth + 1 > _maxDepth) throw _ExceededDepthError();
    queue.addLast(
      _Search(path.append(pathAppend), actualValue, expectedValue, depth + 1),
    );
  } else if (expectedValue is Condition) {
    final failure = expectedValue.softCheckSync(actualValue);
    if (failure != null) {
      final which = failure.rejection.which;
      return [
        'has an element ${path.append(pathAppend)}that:',
        ...indent(failure.detail.actual.skip(1)),
        ...indent(
          prefixFirst('Actual: ', failure.rejection.actual),
          failure.detail.depth + 1,
        ),
        if (which != null)
          ...indent(prefixFirst('which ', which), failure.detail.depth + 1),
      ];
    }
  } else {
    if (actualValue != expectedValue) {
      return [
        ...prefixFirst('${path.append(pathAppend)}is ', literal(actualValue)),
        ...prefixFirst('which does not equal ', literal(expectedValue)),
      ];
    }
  }
  return null;
}

bool _elementMatches(Object? actual, Object? expected, int depth) {
  if (expected == null) return actual == null;
  if (expected is Iterable || expected is Map) {
    if (++depth > _maxDepth) throw _ExceededDepthError();
    return actual != null &&
        _deepCollectionEquals(actual, expected, depth) == null;
  }
  if (expected is Condition) {
    return expected.softCheckSync(actual) == null;
  }
  return expected == actual;
}

Iterable<String>? _findSetDifference(
  Object? actual,
  Set<Object?> expected,
  _Path path,
  int depth,
) {
  if (actual is! Set) {
    return ['${path}is not a Set'];
  }
  return unorderedCompare(
    actual,
    expected,
    (actual, expected) => _elementMatches(actual, expected, depth),
    (expected, _, count) => [
      ...prefixFirst('${path}has no element to match ', literal(expected)),
      if (count > 1) 'or ${count - 1} other elements',
    ],
    (actual, _, count) => [
      ...prefixFirst('${path}has an unexpected element ', literal(actual)),
      if (count > 1) 'and ${count - 1} other unexpected elements',
    ],
  );
}

Iterable<String>? _findMapDifference(
  Object? actual,
  Map<Object?, Object?> expected,
  _Path path,
  Queue<_Search> queue,
  int depth,
) {
  if (actual is! Map) {
    return ['${path}is not a Map'];
  }
  if (expected.keys.any(
    (key) => key is Condition || key is Iterable || key is Map,
  )) {
    return _findAmbiguousMapDifference(actual, expected, path, depth);
  } else {
    return _findUnambiguousMapDifference(actual, expected, path, queue, depth);
  }
}

Iterable<String> _describeEntry(MapEntry<Object?, Object?> entry) {
  final key = literal(entry.key);
  final value = literal(entry.value);
  return [
    ...key.take(key.length - 1),
    '${key.last}: ${value.first}',
    ...value.skip(1),
  ];
}

/// Returns a description of a difference found between [actual] and [expected]
/// when [expected] has only direct key values and there is a 1:1 mapping
/// between an expected value and a checked value in the map.
Iterable<String>? _findUnambiguousMapDifference(
  Map<Object?, Object?> actual,
  Map<Object?, Object?> expected,
  _Path path,
  Queue<_Search> queue,
  int depth,
) {
  for (final entry in expected.entries) {
    assert(entry.key is! Condition);
    assert(entry.key is! Iterable);
    assert(entry.key is! Map);
    if (!actual.containsKey(entry.key)) {
      return prefixFirst(
        '${path}has no key matching expected entry ',
        _describeEntry(entry),
      );
    }
    final difference = _compareValue(
      actual[entry.key],
      entry.value,
      path,
      entry.key,
      queue,
      depth,
    );
    if (difference != null) return difference;
  }
  for (final entry in actual.entries) {
    if (!expected.containsKey(entry.key)) {
      return prefixFirst(
        '${path}has an unexpected key for entry ',
        _describeEntry(entry),
      );
    }
  }
  return null;
}

Iterable<String>? _findAmbiguousMapDifference(
  Map<Object?, Object?> actual,
  Map<Object?, Object?> expected,
  _Path path,
  int depth,
) => unorderedCompare(
  actual.entries,
  expected.entries,
  (actual, expected) =>
      _elementMatches(actual.key, expected.key, depth) &&
      _elementMatches(actual.value, expected.value, depth),
  (expectedEntry, _, count) => [
    ...prefixFirst(
      '${path}has no entry to match ',
      _describeEntry(expectedEntry),
    ),
    if (count > 1) 'or ${count - 1} other entries',
  ],
  (actualEntry, _, count) => [
    ...prefixFirst('${path}has unexpected entry ', _describeEntry(actualEntry)),
    if (count > 1) 'and ${count - 1} other unexpected entries',
  ],
);

class _Path {
  final _Path? parent;
  final Object? index;
  _Path._(this.parent, this.index);
  _Path.root() : parent = null, index = '';
  _Path append(Object? index) => _Path._(this, index);

  @override
  String toString() {
    if (parent == null && index == '') return '';
    final stack = Queue.of([this]);
    var current = parent;
    while (current?.parent != null) {
      stack.addLast(current!);
      current = current.parent;
    }
    final result = StringBuffer('at ');
    while (stack.isNotEmpty) {
      result.write('[');
      result.write(literal(stack.removeLast().index).join(r'\n'));
      result.write(']');
    }
    result.write(' ');
    return result.toString();
  }
}

class _Search {
  final _Path path;
  final Object? actual;
  final Object? expected;
  final int depth;
  _Search(this.path, this.actual, this.expected, this.depth);
}

/// Returns the `which` for a Rejection if there is no pairing between the
/// elements of [actual] and [expected] using [elementsEqual].
///
/// If there are unmatched expected elements - either actual was too short, or
/// has mismatched elements - returns a rejection reason from calling
/// [unmatchedExpected] with an expected value that could not be paired, it's
/// index, and the count of unmatched elements.
///
/// Otherwise, if there are unmatched actual elements - actual was too long -
/// returns a rejection reason from calling [unmatchedActual] with an actual
/// value that could not be paired, it's index, and the count of unmatched
/// elements.
///
/// Runtime is at least `O(|actual||expected|)`, and for collections with many
/// elements which compare as equal the runtime can reach
/// `O((|actual| + |expected|)^2.5)`.
Iterable<String>? unorderedCompare<T, E>(
  Iterable<T> actual,
  Iterable<E> expected,
  bool Function(T, E) elementsEqual,
  Iterable<String> Function(E, int index, int count) unmatchedExpected,
  Iterable<String> Function(T, int index, int count) unmatchedActual,
) {
  final indexedExpected = expected.toList();
  final indexedActual = actual.toList();
  final adjacency = <List<int>>[];
  for (var i = 0; i < indexedExpected.length; i++) {
    final expectedElement = indexedExpected[i];
    final pairs = [
      for (var j = 0; j < indexedActual.length; j++)
        if (elementsEqual(indexedActual[j], expectedElement)) j,
    ];
    adjacency.add(pairs);
  }
  final unpaired = _findUnpaired(adjacency, indexedActual.length);
  if (unpaired.first.isNotEmpty) {
    final firstUnmatched = indexedExpected[unpaired.first.first];
    return unmatchedExpected(
      firstUnmatched,
      unpaired.first.first,
      unpaired.first.length,
    );
  }
  if (unpaired.last.isNotEmpty) {
    final firstUnmatched = indexedActual[unpaired.last.first];
    return unmatchedActual(
      firstUnmatched,
      unpaired.last.first,
      unpaired.last.length,
    );
  }
  return null;
}

/// Returns the indices which are unmatched in an optimal pairing in the
/// bipartite graph represented by [adjacency].
///
/// Vertices are represented as integers. The two sets of vertices (`U` and `V`)
/// in the biparte graph are represented as:
/// - `U` - the indices of [adjacency].
/// - `V` - values smaller than [rightVertexCount].
///
/// An edge from `U[n]` to `V[m]` is represented by the value `m` being present
/// in the list at index `n`.
/// The largest value within any list in [adjacency] must be smaller than
/// [rightVertexCount].
///
/// Returns a List with two values, the unpaired values of `U` and `V` in the
/// maximum-caridnality matching betweeen them.
///
/// If there is a perfect pairing, the returned lists will both be empty.
///
/// Uses the Hopcroft–Karp algorithm based on pseudocode from
/// https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
List<List<int>> _findUnpaired(List<List<int>> adjacency, int rightVertexCount) {
  final leftLength = adjacency.length;
  final rightLength = rightVertexCount;
  // The last index represents a "dummy vertex"
  final distances = List<num>.filled(leftLength + 1, double.infinity);
  // Initially everything is paired with the "dummy vertex" of the opposite set
  final leftPairs = List.filled(leftLength, rightLength);
  final rightPairs = List.filled(rightLength, leftLength);

  bool bfs() {
    final queue = Queue<int>();
    for (var leftIndex = 0; leftIndex < leftLength; leftIndex++) {
      if (leftPairs[leftIndex] == rightLength) {
        distances[leftIndex] = 0;
        queue.add(leftIndex);
      } else {
        distances[leftIndex] = double.infinity;
      }
    }
    distances.last = double.infinity;
    while (queue.isNotEmpty) {
      final current = queue.removeFirst();
      if (distances[current] < distances[leftLength]) {
        for (final rightIndex in adjacency[current]) {
          if (distances[rightPairs[rightIndex]].isInfinite) {
            distances[rightPairs[rightIndex]] = distances[current] + 1;
            queue.addLast(rightPairs[rightIndex]);
          }
        }
      }
    }
    return !distances.last.isInfinite;
  }

  bool dfs(int leftIndex) {
    if (leftIndex == leftLength) return true;
    for (final rightIndex in adjacency[leftIndex]) {
      if (distances[rightPairs[rightIndex]] == distances[leftIndex] + 1) {
        if (dfs(rightPairs[rightIndex])) {
          leftPairs[leftIndex] = rightIndex;
          rightPairs[rightIndex] = leftIndex;
          return true;
        }
      }
    }
    distances[leftIndex] = double.infinity;
    return false;
  }

  while (bfs()) {
    for (var leftIndex = 0; leftIndex < leftLength; leftIndex++) {
      if (leftPairs[leftIndex] == rightLength) {
        dfs(leftIndex);
      }
    }
  }
  return [
    [
      for (int i = 0; i < leftLength; i++)
        if (leftPairs[i] == rightLength) i,
    ],
    [
      for (int i = 0; i < rightLength; i++)
        if (rightPairs[i] == leftLength) i,
    ],
  ];
}