// Copyright (c) 2018, 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 'feature_matcher.dart';
import 'interfaces.dart';
import 'util.dart';

/// Returns a matcher that matches if the value is structurally equal to
/// [expected].
///
/// If [expected] is a [Matcher], then it matches using that. Otherwise it tests
/// for equality using `==` on the expected value.
///
/// For [Iterable]s and [Map]s, this will recursively match the elements. To
/// handle cyclic structures a recursion depth [limit] can be provided. The
/// default limit is 100. [Set]s will be compared order-independently.
Matcher equals(Object? expected, [int limit = 100]) =>
    expected is String
        ? _StringEqualsMatcher(expected)
        : _DeepMatcher(expected, limit);

typedef _RecursiveMatcher = _Mismatch? Function(Object?, Object?, String, int);

/// A special equality matcher for strings.
class _StringEqualsMatcher extends FeatureMatcher<String> {
  final String _value;

  _StringEqualsMatcher(this._value);

  @override
  bool typedMatches(String item, Map matchState) => _value == item;

  @override
  Description describe(Description description) =>
      description.addDescriptionOf(_value);

  @override
  Description describeTypedMismatch(
    String item,
    Description mismatchDescription,
    Map matchState,
    bool verbose,
  ) {
    var buff = StringBuffer();
    buff.write('is different.');
    var escapedItem = escape(item);
    var escapedValue = escape(_value);
    var minLength =
        escapedItem.length < escapedValue.length
            ? escapedItem.length
            : escapedValue.length;
    var start = 0;
    for (; start < minLength; start++) {
      if (escapedValue.codeUnitAt(start) != escapedItem.codeUnitAt(start)) {
        break;
      }
    }
    if (start == minLength) {
      if (escapedValue.length < escapedItem.length) {
        buff.write(
          ' Both strings start the same, but the actual value also'
          ' has the following trailing characters: ',
        );
        _writeTrailing(buff, escapedItem, escapedValue.length);
      } else {
        buff.write(
          ' Both strings start the same, but the actual value is'
          ' missing the following trailing characters: ',
        );
        _writeTrailing(buff, escapedValue, escapedItem.length);
      }
    } else {
      buff.write('\nExpected: ');
      _writeLeading(buff, escapedValue, start);
      _writeTrailing(buff, escapedValue, start);
      buff.write('\n  Actual: ');
      _writeLeading(buff, escapedItem, start);
      _writeTrailing(buff, escapedItem, start);
      buff.write('\n          ');
      for (var i = start > 10 ? 14 : start; i > 0; i--) {
        buff.write(' ');
      }
      buff.write('^\n Differ at offset $start');
    }

    return mismatchDescription.add(buff.toString());
  }

  static void _writeLeading(StringBuffer buff, String s, int start) {
    if (start > 10) {
      buff.write('... ');
      buff.write(s.substring(start - 10, start));
    } else {
      buff.write(s.substring(0, start));
    }
  }

  static void _writeTrailing(StringBuffer buff, String s, int start) {
    if (start + 10 > s.length) {
      buff.write(s.substring(start));
    } else {
      buff.write(s.substring(start, start + 10));
      buff.write(' ...');
    }
  }
}

class _DeepMatcher extends Matcher {
  final Object? _expected;
  final int _limit;

  _DeepMatcher(this._expected, [int limit = 1000]) : _limit = limit;

  _Mismatch? _compareIterables(
    Iterable expected,
    Object? actual,
    _RecursiveMatcher matcher,
    int depth,
    String location,
  ) {
    if (actual is Iterable) {
      var expectedIterator = expected.iterator;
      var actualIterator = actual.iterator;
      for (var index = 0; ; index++) {
        // Advance in lockstep.
        var expectedNext = expectedIterator.moveNext();
        var actualNext = actualIterator.moveNext();

        // If we reached the end of both, we succeeded.
        if (!expectedNext && !actualNext) return null;

        // Fail if their lengths are different.
        var newLocation = '$location[$index]';
        if (!expectedNext) {
          return _Mismatch.simple(newLocation, actual, 'longer than expected');
        }
        if (!actualNext) {
          return _Mismatch.simple(newLocation, actual, 'shorter than expected');
        }

        // Match the elements.
        var rp = matcher(
          expectedIterator.current,
          actualIterator.current,
          newLocation,
          depth,
        );
        if (rp != null) return rp;
      }
    } else {
      return _Mismatch.simple(location, actual, 'is not Iterable');
    }
  }

  _Mismatch? _compareSets(
    Set expected,
    Object? actual,
    _RecursiveMatcher matcher,
    int depth,
    String location,
  ) {
    if (actual is Iterable) {
      var other = actual.toSet();

      for (var expectedElement in expected) {
        if (other.every(
          (actualElement) =>
              matcher(expectedElement, actualElement, location, depth) != null,
        )) {
          return _Mismatch(
            location,
            actual,
            (description, verbose) => description
                .add('does not contain ')
                .addDescriptionOf(expectedElement),
          );
        }
      }

      if (other.length > expected.length) {
        return _Mismatch.simple(location, actual, 'larger than expected');
      } else if (other.length < expected.length) {
        return _Mismatch.simple(location, actual, 'smaller than expected');
      } else {
        return null;
      }
    } else {
      return _Mismatch.simple(location, actual, 'is not Iterable');
    }
  }

  _Mismatch? _recursiveMatch(
    Object? expected,
    Object? actual,
    String location,
    int depth,
  ) {
    // If the expected value is a matcher, try to match it.
    if (expected is Matcher) {
      var matchState = <Object?, Object?>{};
      if (expected.matches(actual, matchState)) return null;
      return _Mismatch(location, actual, (description, verbose) {
        var oldLength = description.length;
        expected.describeMismatch(actual, description, matchState, verbose);
        if (depth > 0 && description.length == oldLength) {
          description.add('does not match ');
          expected.describe(description);
        }
      });
    } else {
      // Otherwise, test for equality, or both values NaN
      try {
        if (expected == actual ||
            (expected is num &&
                expected.isNaN &&
                actual is num &&
                actual.isNaN)) {
          return null;
        }
      } catch (e) {
        // TODO(gram): Add a test for this case.
        return _Mismatch(
          location,
          actual,
          (description, verbose) =>
              description.add('== threw ').addDescriptionOf(e),
        );
      }
    }

    if (depth > _limit) {
      return _Mismatch.simple(
        location,
        actual,
        'recursion depth limit exceeded',
      );
    }

    // If _limit is 1 we can only recurse one level into object.
    if (depth == 0 || _limit > 1) {
      if (expected is Set) {
        return _compareSets(
          expected,
          actual,
          _recursiveMatch,
          depth + 1,
          location,
        );
      } else if (expected is Iterable) {
        return _compareIterables(
          expected,
          actual,
          _recursiveMatch,
          depth + 1,
          location,
        );
      } else if (expected is Map) {
        if (actual is! Map) {
          return _Mismatch.simple(location, actual, 'expected a map');
        }
        var err =
            (expected.length == actual.length)
                ? ''
                : 'has different length and ';
        for (var key in expected.keys) {
          if (!actual.containsKey(key)) {
            return _Mismatch(
              location,
              actual,
              (description, verbose) => description
                  .add('${err}is missing map key ')
                  .addDescriptionOf(key),
            );
          }
        }

        for (var key in actual.keys) {
          if (!expected.containsKey(key)) {
            return _Mismatch(
              location,
              actual,
              (description, verbose) => description
                  .add('${err}has extra map key ')
                  .addDescriptionOf(key),
            );
          }
        }

        for (var key in expected.keys) {
          var rp = _recursiveMatch(
            expected[key],
            actual[key],
            "$location['$key']",
            depth + 1,
          );
          if (rp != null) return rp;
        }

        return null;
      }
    }

    // If we have recursed, show the expected value too; if not, expect() will
    // show it for us.
    if (depth > 0) {
      return _Mismatch(
        location,
        actual,
        (description, verbose) => description.addDescriptionOf(expected),
        instead: true,
      );
    } else {
      return _Mismatch(location, actual, null);
    }
  }

  @override
  bool matches(Object? actual, Map matchState) {
    var mismatch = _recursiveMatch(_expected, actual, '', 0);
    if (mismatch == null) return true;
    addStateInfo(matchState, {'mismatch': mismatch});
    return false;
  }

  @override
  Description describe(Description description) =>
      description.addDescriptionOf(_expected);

  @override
  Description describeMismatch(
    Object? item,
    Description mismatchDescription,
    Map matchState,
    bool verbose,
  ) {
    var mismatch = matchState['mismatch'] as _Mismatch;
    var describeProblem = mismatch.describeProblem;
    if (mismatch.location.isNotEmpty) {
      mismatchDescription
          .add('at location ')
          .add(mismatch.location)
          .add(' is ')
          .addDescriptionOf(mismatch.actual);
      if (describeProblem != null) {
        mismatchDescription.add(
          ' ${mismatch.instead ? 'instead of' : 'which'} ',
        );
        describeProblem(mismatchDescription, verbose);
      }
    } else {
      // If we didn't get a good reason, that would normally be a
      // simple 'is <value>' message. We only add that if the mismatch
      // description is non empty (so we are supplementing the mismatch
      // description).
      if (describeProblem == null) {
        if (mismatchDescription.length > 0) {
          mismatchDescription.add('is ').addDescriptionOf(item);
        }
      } else {
        describeProblem(mismatchDescription, verbose);
      }
    }
    return mismatchDescription;
  }
}

class _Mismatch {
  /// A human-readable description of the location within the collection where
  /// the mismatch occurred.
  final String location;

  /// The actual value found at [location].
  final Object? actual;

  /// Callback that can create a detailed description of the problem.
  final void Function(Description, bool verbose)? describeProblem;

  /// If `true`, [describeProblem] describes the expected value, so when the
  /// final mismatch description is pieced together, it will be preceded by
  /// `instead of` (e.g. `at location [2] is <3> instead of <4>`).  If `false`,
  /// [describeProblem] is a problem description from a sub-matcher, so when the
  /// final mismatch description is pieced together, it will be preceded by
  /// `which` (e.g. `at location [2] is <foo> which has length of 3`).
  final bool instead;

  _Mismatch(
    this.location,
    this.actual,
    this.describeProblem, {
    this.instead = false,
  });

  _Mismatch.simple(this.location, this.actual, String problem)
    : describeProblem = ((description, verbose) => description.add(problem)),
      instead = false;
}