lib/src/util/tested_expressions.dart

// Copyright (c) 2016, 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:analyzer/dart/ast/ast.dart';
import 'package:analyzer/dart/ast/token.dart';
import '../util/boolean_expression_utilities.dart';

void _addNodeComparisons(Expression node, Set<Expression> comparisons) {
  if (_isComparison(node)) {
    comparisons.add(node);
  } else if (_isBooleanOperation(node)) {
    comparisons.addAll(_extractComparisons(node as BinaryExpression));
  }
}

Set<Expression> _extractComparisons(BinaryExpression node) {
  final Set<Expression> comparisons = HashSet<Expression>.identity();
  if (_isComparison(node)) {
    comparisons.add(node);
  }
  if (node.operator.type != TokenType.AMPERSAND_AMPERSAND) {
    return comparisons;
  }

  _addNodeComparisons(node.leftOperand, comparisons);
  _addNodeComparisons(node.rightOperand, comparisons);

  return comparisons;
}

bool _isBooleanOperation(Expression expression) =>
    expression is BinaryExpression &&
    BooleanExpressionUtilities.BOOLEAN_OPERATIONS
        .contains(expression.operator.type);

bool _isComparison(Expression expression) =>
    expression is BinaryExpression &&
    BooleanExpressionUtilities.COMPARISONS.contains(expression.operator.type);

bool _isNegationOrComparison(
    TokenType cOperatorType, TokenType eOperatorType, TokenType tokenType) {
  final isNegationOperation =
      cOperatorType == BooleanExpressionUtilities.NEGATIONS[eOperatorType] ||
          BooleanExpressionUtilities.IMPLICATIONS[cOperatorType] ==
              BooleanExpressionUtilities.NEGATIONS[eOperatorType];

  final isTrichotomyConjunction = BooleanExpressionUtilities
          .TRICHOTOMY_OPERATORS
          .contains(eOperatorType) &&
      BooleanExpressionUtilities.TRICHOTOMY_OPERATORS.contains(cOperatorType) &&
      tokenType == TokenType.AMPERSAND_AMPERSAND;
  final isNegationOrComparison = isNegationOperation || isTrichotomyConjunction;
  return isNegationOrComparison;
}

bool _sameOperands(String eLeftOperand, String bcLeftOperand,
    String eRightOperand, String bcRightOperand) {
  final sameOperandsSameOrder =
      eLeftOperand == bcLeftOperand && eRightOperand == bcRightOperand;
  final sameOperandsInverted =
      eRightOperand == bcLeftOperand && eLeftOperand == bcRightOperand;
  return sameOperandsSameOrder || sameOperandsInverted;
}

typedef _RecurseCallback = void Function(Expression expression);

class ContradictoryComparisons {
  final Expression first;
  final Expression second;

  ContradictoryComparisons(this.first, this.second);
}

class TestedExpressions {
  final Expression testingExpression;
  final Set<Expression> truths;
  final Set<Expression> negations;
  LinkedHashSet<ContradictoryComparisons> _contradictions;

  TestedExpressions(this.testingExpression, this.truths, this.negations);

  LinkedHashSet<ContradictoryComparisons> evaluateInvariant() {
    if (_contradictions != null) {
      return _contradictions;
    }

    final binaryExpression = testingExpression is BinaryExpression
        ? testingExpression as BinaryExpression
        : null;
    var facts = binaryExpression != null
        ? [binaryExpression.leftOperand, binaryExpression.rightOperand]
        : [testingExpression];
    _contradictions = _findContradictoryComparisons(
        LinkedHashSet.from(facts),
        binaryExpression != null
            ? binaryExpression.operator.type
            : TokenType.AMPERSAND_AMPERSAND);

    if (_contradictions.isEmpty) {
      final set = (binaryExpression != null
          ? _extractComparisons(testingExpression as BinaryExpression)
          : {testingExpression})
        ..addAll(truths)
        ..addAll(negations);
      // Here and in several places we proceed only for
      // TokenType.AMPERSAND_AMPERSAND because we then know that all comparisons
      // must be true.
      _contradictions.addAll(
          _findContradictoryComparisons(set, TokenType.AMPERSAND_AMPERSAND));
    }

    return _contradictions;
  }

  /// TODO: A truly smart implementation would detect
  /// (ref.prop && other.otherProp) && (!ref.prop || !other.otherProp)
  /// assuming properties are pure computations. i.e. dealing with De Morgan's
  /// laws https://en.wikipedia.org/wiki/De_Morgan%27s_laws
  LinkedHashSet<ContradictoryComparisons> _findContradictoryComparisons(
      Set<Expression> comparisons, TokenType tokenType) {
    final Iterable<Expression> binaryExpressions =
        comparisons.whereType<BinaryExpression>().toSet();
    final contradictions = LinkedHashSet<ContradictoryComparisons>.identity();

    if (testingExpression is SimpleIdentifier) {
      final identifier = testingExpression as SimpleIdentifier;
      bool sameIdentifier(n) =>
          n is SimpleIdentifier && identifier.staticElement == n.staticElement;
      if (negations.any(sameIdentifier)) {
        final otherIdentifier =
            negations.firstWhere(sameIdentifier) as SimpleIdentifier;
        contradictions
            .add(ContradictoryComparisons(otherIdentifier, identifier));
      }
    }

    binaryExpressions.forEach((Expression ex) {
      if (contradictions.isNotEmpty) {
        return;
      }

      final expression = ex as BinaryExpression;
      final eLeftOperand = expression.leftOperand.toString();
      final eRightOperand = expression.rightOperand.toString();
      final eOperatorType = expression.operator.type;
      comparisons
          .where((comparison) =>
              comparison != null &&
              comparison.offset < expression.offset &&
              comparison is BinaryExpression)
          .forEach((Expression c) {
        if (contradictions.isNotEmpty) {
          return;
        }

        final otherExpression = c as BinaryExpression;

        final bcLeftOperand = otherExpression.leftOperand.toString();
        final bcRightOperand = otherExpression.rightOperand.toString();
        final sameOperands = _sameOperands(
            eLeftOperand, bcLeftOperand, eRightOperand, bcRightOperand);

        final cOperatorType = negations.contains(c)
            ? BooleanExpressionUtilities
                .NEGATIONS[otherExpression.operator.type]
            : otherExpression.operator.type;
        final isNegationOrComparison =
            _isNegationOrComparison(cOperatorType, eOperatorType, tokenType);

        if (isNegationOrComparison && sameOperands) {
          contradictions
              .add(ContradictoryComparisons(otherExpression, expression));
        }
      });
    });

    if (contradictions.isEmpty) {
      binaryExpressions.forEach(_recurseOnChildNodes(contradictions));
    }

    return contradictions;
  }

  _RecurseCallback _recurseOnChildNodes(
          LinkedHashSet<ContradictoryComparisons> expressions) =>
      (Expression e) {
        final ex = e as BinaryExpression;
        if (ex.operator.type != TokenType.AMPERSAND_AMPERSAND) {
          return;
        }

        final set = _findContradictoryComparisons(
            HashSet.from([ex.leftOperand, ex.rightOperand]), ex.operator.type);
        expressions.addAll(set);
      };
}