// Copyright 2022 The Tint Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "src/tint/fuzzers/tint_ast_fuzzer/mutations/change_binary_operator.h"

#include <utility>

#include "src/tint/program_builder.h"
#include "src/tint/sem/bool.h"
#include "src/tint/sem/reference.h"

namespace tint::fuzzers::ast_fuzzer {

namespace {

bool IsSuitableForShift(const type::Type* lhs_type, const type::Type* rhs_type) {
    // `a << b` requires b to be an unsigned scalar or vector, and `a` to be an
    // integer scalar or vector with the same width as `b`. Similar for `a >> b`.

    if (rhs_type->is_unsigned_integer_scalar()) {
        return lhs_type->is_integer_scalar();
    }
    if (rhs_type->is_unsigned_integer_vector()) {
        return lhs_type->is_unsigned_integer_vector();
    }
    return false;
}

bool CanReplaceAddSubtractWith(const type::Type* lhs_type,
                               const type::Type* rhs_type,
                               ast::BinaryOp new_operator) {
    // The program is assumed to be well-typed, so this method determines when
    // 'new_operator' can be used as a type-preserving replacement in an '+' or
    // '-' expression.
    switch (new_operator) {
        case ast::BinaryOp::kAdd:
        case ast::BinaryOp::kSubtract:
            // '+' and '-' are fully type compatible.
            return true;
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
        case ast::BinaryOp::kXor:
            // These operators do not have a mixed vector-scalar form, and only work
            // on integer types.
            return lhs_type == rhs_type && lhs_type->is_integer_scalar_or_vector();
        case ast::BinaryOp::kMultiply:
            // '+' and '*' are largely type-compatible, but for matrices they are only
            // type-compatible if the matrices are square.
            return !lhs_type->is_float_matrix() || lhs_type->is_square_float_matrix();
        case ast::BinaryOp::kDivide:
        case ast::BinaryOp::kModulo:
            // '/' is not defined for matrices.
            return lhs_type->is_numeric_scalar_or_vector() &&
                   rhs_type->is_numeric_scalar_or_vector();
        case ast::BinaryOp::kShiftLeft:
        case ast::BinaryOp::kShiftRight:
            return IsSuitableForShift(lhs_type, rhs_type);
        default:
            return false;
    }
}

bool CanReplaceMultiplyWith(const type::Type* lhs_type,
                            const type::Type* rhs_type,
                            ast::BinaryOp new_operator) {
    // The program is assumed to be well-typed, so this method determines when
    // 'new_operator' can be used as a type-preserving replacement in a '*'
    // expression.
    switch (new_operator) {
        case ast::BinaryOp::kMultiply:
            return true;
        case ast::BinaryOp::kAdd:
        case ast::BinaryOp::kSubtract:
            // '*' is type-compatible with '+' and '-' for square matrices, and for
            // numeric scalars/vectors.
            if (lhs_type->is_square_float_matrix() && rhs_type->is_square_float_matrix()) {
                return true;
            }
            return lhs_type->is_numeric_scalar_or_vector() &&
                   rhs_type->is_numeric_scalar_or_vector();
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
        case ast::BinaryOp::kXor:
            // These operators require homogeneous integer types.
            return lhs_type == rhs_type && lhs_type->is_integer_scalar_or_vector();
        case ast::BinaryOp::kDivide:
        case ast::BinaryOp::kModulo:
            // '/' is not defined for matrices.
            return lhs_type->is_numeric_scalar_or_vector() &&
                   rhs_type->is_numeric_scalar_or_vector();
        case ast::BinaryOp::kShiftLeft:
        case ast::BinaryOp::kShiftRight:
            return IsSuitableForShift(lhs_type, rhs_type);
        default:
            return false;
    }
}

bool CanReplaceDivideOrModuloWith(const type::Type* lhs_type,
                                  const type::Type* rhs_type,
                                  ast::BinaryOp new_operator) {
    // The program is assumed to be well-typed, so this method determines when
    // 'new_operator' can be used as a type-preserving replacement in a '/'
    // expression.
    switch (new_operator) {
        case ast::BinaryOp::kAdd:
        case ast::BinaryOp::kSubtract:
        case ast::BinaryOp::kMultiply:
        case ast::BinaryOp::kDivide:
        case ast::BinaryOp::kModulo:
            // These operators work in all contexts where '/' works.
            return true;
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
        case ast::BinaryOp::kXor:
            // These operators require homogeneous integer types.
            return lhs_type == rhs_type && lhs_type->is_integer_scalar_or_vector();
        case ast::BinaryOp::kShiftLeft:
        case ast::BinaryOp::kShiftRight:
            return IsSuitableForShift(lhs_type, rhs_type);
        default:
            return false;
    }
}

bool CanReplaceLogicalAndLogicalOrWith(ast::BinaryOp new_operator) {
    switch (new_operator) {
        case ast::BinaryOp::kLogicalAnd:
        case ast::BinaryOp::kLogicalOr:
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
        case ast::BinaryOp::kEqual:
        case ast::BinaryOp::kNotEqual:
            // These operators all work whenever '&&' and '||' work.
            return true;
        default:
            return false;
    }
}

bool CanReplaceAndOrWith(const type::Type* lhs_type,
                         const type::Type* rhs_type,
                         ast::BinaryOp new_operator) {
    switch (new_operator) {
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
            // '&' and '|' work in all the same contexts.
            return true;
        case ast::BinaryOp::kAdd:
        case ast::BinaryOp::kSubtract:
        case ast::BinaryOp::kMultiply:
        case ast::BinaryOp::kDivide:
        case ast::BinaryOp::kModulo:
        case ast::BinaryOp::kXor:
            // '&' and '|' can be applied to booleans. In all other contexts,
            // integer numeric operators work.
            return !lhs_type->is_bool_scalar_or_vector();
        case ast::BinaryOp::kShiftLeft:
        case ast::BinaryOp::kShiftRight:
            return IsSuitableForShift(lhs_type, rhs_type);
        case ast::BinaryOp::kLogicalAnd:
        case ast::BinaryOp::kLogicalOr:
            // '&' and '|' can be applied to booleans, and for boolean scalar
            // scalar contexts, their logical counterparts work.
            return lhs_type->Is<sem::Bool>();
        case ast::BinaryOp::kEqual:
        case ast::BinaryOp::kNotEqual:
            // '&' and '|' can be applied to booleans, and in these contexts equality
            // comparison operators also work.
            return lhs_type->is_bool_scalar_or_vector();
        default:
            return false;
    }
}

bool CanReplaceXorWith(const type::Type* lhs_type,
                       const type::Type* rhs_type,
                       ast::BinaryOp new_operator) {
    switch (new_operator) {
        case ast::BinaryOp::kAdd:
        case ast::BinaryOp::kSubtract:
        case ast::BinaryOp::kMultiply:
        case ast::BinaryOp::kDivide:
        case ast::BinaryOp::kModulo:
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
        case ast::BinaryOp::kXor:
            // '^' only works on integer types, and in any such context, all other
            // integer operators also work.
            return true;
        case ast::BinaryOp::kShiftLeft:
        case ast::BinaryOp::kShiftRight:
            return IsSuitableForShift(lhs_type, rhs_type);
        default:
            return false;
    }
}

bool CanReplaceShiftLeftShiftRightWith(const type::Type* lhs_type,
                                       const type::Type* rhs_type,
                                       ast::BinaryOp new_operator) {
    switch (new_operator) {
        case ast::BinaryOp::kShiftLeft:
        case ast::BinaryOp::kShiftRight:
            // These operators are type-compatible.
            return true;
        case ast::BinaryOp::kAdd:
        case ast::BinaryOp::kSubtract:
        case ast::BinaryOp::kMultiply:
        case ast::BinaryOp::kDivide:
        case ast::BinaryOp::kModulo:
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
        case ast::BinaryOp::kXor:
            // Shift operators allow mixing of signed and unsigned arguments, but in
            // the case where the arguments are homogeneous, they are type-compatible
            // with other numeric operators.
            return lhs_type == rhs_type;
        default:
            return false;
    }
}

bool CanReplaceEqualNotEqualWith(const type::Type* lhs_type, ast::BinaryOp new_operator) {
    switch (new_operator) {
        case ast::BinaryOp::kEqual:
        case ast::BinaryOp::kNotEqual:
            // These operators are type-compatible.
            return true;
        case ast::BinaryOp::kLessThan:
        case ast::BinaryOp::kLessThanEqual:
        case ast::BinaryOp::kGreaterThan:
        case ast::BinaryOp::kGreaterThanEqual:
            // An equality comparison between numeric types can be changed to an
            // ordered comparison.
            return lhs_type->is_numeric_scalar_or_vector();
        case ast::BinaryOp::kLogicalAnd:
        case ast::BinaryOp::kLogicalOr:
            // An equality comparison between boolean scalars can be turned into a
            // logical operation.
            return lhs_type->Is<sem::Bool>();
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
            // An equality comparison between boolean scalars or vectors can be turned
            // into a component-wise non-short-circuit logical operation.
            return lhs_type->is_bool_scalar_or_vector();
        default:
            return false;
    }
}

bool CanReplaceLessThanLessThanEqualGreaterThanGreaterThanEqualWith(ast::BinaryOp new_operator) {
    switch (new_operator) {
        case ast::BinaryOp::kEqual:
        case ast::BinaryOp::kNotEqual:
        case ast::BinaryOp::kLessThan:
        case ast::BinaryOp::kLessThanEqual:
        case ast::BinaryOp::kGreaterThan:
        case ast::BinaryOp::kGreaterThanEqual:
            // Ordered comparison operators can be interchanged, and equality
            // operators can be used in their place.
            return true;
        default:
            return false;
    }
}
}  // namespace

MutationChangeBinaryOperator::MutationChangeBinaryOperator(
    protobufs::MutationChangeBinaryOperator message)
    : message_(std::move(message)) {}

MutationChangeBinaryOperator::MutationChangeBinaryOperator(uint32_t binary_expr_id,
                                                           ast::BinaryOp new_operator) {
    message_.set_binary_expr_id(binary_expr_id);
    message_.set_new_operator(static_cast<uint32_t>(new_operator));
}

bool MutationChangeBinaryOperator::CanReplaceBinaryOperator(
    const Program& program,
    const ast::BinaryExpression& binary_expr,
    ast::BinaryOp new_operator) {
    if (new_operator == binary_expr.op) {
        // An operator should not be replaced with itself, as this would be a no-op.
        return false;
    }

    // Get the types of the operators.
    const auto* lhs_type = program.Sem().Get(binary_expr.lhs)->Type();
    const auto* rhs_type = program.Sem().Get(binary_expr.rhs)->Type();

    // If these are reference types, unwrap them to get the pointee type.
    const type::Type* lhs_basic_type =
        lhs_type->Is<sem::Reference>() ? lhs_type->As<sem::Reference>()->StoreType() : lhs_type;
    const type::Type* rhs_basic_type =
        rhs_type->Is<sem::Reference>() ? rhs_type->As<sem::Reference>()->StoreType() : rhs_type;

    switch (binary_expr.op) {
        case ast::BinaryOp::kAdd:
        case ast::BinaryOp::kSubtract:
            return CanReplaceAddSubtractWith(lhs_basic_type, rhs_basic_type, new_operator);
        case ast::BinaryOp::kMultiply:
            return CanReplaceMultiplyWith(lhs_basic_type, rhs_basic_type, new_operator);
        case ast::BinaryOp::kDivide:
        case ast::BinaryOp::kModulo:
            return CanReplaceDivideOrModuloWith(lhs_basic_type, rhs_basic_type, new_operator);
        case ast::BinaryOp::kAnd:
        case ast::BinaryOp::kOr:
            return CanReplaceAndOrWith(lhs_basic_type, rhs_basic_type, new_operator);
        case ast::BinaryOp::kXor:
            return CanReplaceXorWith(lhs_basic_type, rhs_basic_type, new_operator);
        case ast::BinaryOp::kShiftLeft:
        case ast::BinaryOp::kShiftRight:
            return CanReplaceShiftLeftShiftRightWith(lhs_basic_type, rhs_basic_type, new_operator);
        case ast::BinaryOp::kLogicalAnd:
        case ast::BinaryOp::kLogicalOr:
            return CanReplaceLogicalAndLogicalOrWith(new_operator);
        case ast::BinaryOp::kEqual:
        case ast::BinaryOp::kNotEqual:
            return CanReplaceEqualNotEqualWith(lhs_basic_type, new_operator);
        case ast::BinaryOp::kLessThan:
        case ast::BinaryOp::kLessThanEqual:
        case ast::BinaryOp::kGreaterThan:
        case ast::BinaryOp::kGreaterThanEqual:
        case ast::BinaryOp::kNone:
            return CanReplaceLessThanLessThanEqualGreaterThanGreaterThanEqualWith(new_operator);
            assert(false && "Unreachable");
            return false;
    }
}

bool MutationChangeBinaryOperator::IsApplicable(const Program& program,
                                                const NodeIdMap& node_id_map) const {
    const auto* binary_expr_node =
        As<ast::BinaryExpression>(node_id_map.GetNode(message_.binary_expr_id()));
    if (binary_expr_node == nullptr) {
        // Either the id does not exist, or does not correspond to a binary
        // expression.
        return false;
    }
    // Check whether the replacement is acceptable.
    const auto new_operator = static_cast<ast::BinaryOp>(message_.new_operator());
    return CanReplaceBinaryOperator(program, *binary_expr_node, new_operator);
}

void MutationChangeBinaryOperator::Apply(const NodeIdMap& node_id_map,
                                         CloneContext* clone_context,
                                         NodeIdMap* new_node_id_map) const {
    // Get the node whose operator is to be replaced.
    const auto* binary_expr_node =
        As<ast::BinaryExpression>(node_id_map.GetNode(message_.binary_expr_id()));

    // Clone the binary expression, with the appropriate new operator.
    const ast::BinaryExpression* cloned_replacement;
    switch (static_cast<ast::BinaryOp>(message_.new_operator())) {
        case ast::BinaryOp::kAnd:
            cloned_replacement =
                clone_context->dst->And(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kOr:
            cloned_replacement =
                clone_context->dst->Or(clone_context->Clone(binary_expr_node->lhs),
                                       clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kXor:
            cloned_replacement =
                clone_context->dst->Xor(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kLogicalAnd:
            cloned_replacement =
                clone_context->dst->LogicalAnd(clone_context->Clone(binary_expr_node->lhs),
                                               clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kLogicalOr:
            cloned_replacement =
                clone_context->dst->LogicalOr(clone_context->Clone(binary_expr_node->lhs),
                                              clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kEqual:
            cloned_replacement =
                clone_context->dst->Equal(clone_context->Clone(binary_expr_node->lhs),
                                          clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kNotEqual:
            cloned_replacement =
                clone_context->dst->NotEqual(clone_context->Clone(binary_expr_node->lhs),
                                             clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kLessThan:
            cloned_replacement =
                clone_context->dst->LessThan(clone_context->Clone(binary_expr_node->lhs),
                                             clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kGreaterThan:
            cloned_replacement =
                clone_context->dst->GreaterThan(clone_context->Clone(binary_expr_node->lhs),
                                                clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kLessThanEqual:
            cloned_replacement =
                clone_context->dst->LessThanEqual(clone_context->Clone(binary_expr_node->lhs),
                                                  clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kGreaterThanEqual:
            cloned_replacement =
                clone_context->dst->GreaterThanEqual(clone_context->Clone(binary_expr_node->lhs),
                                                     clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kShiftLeft:
            cloned_replacement =
                clone_context->dst->Shl(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kShiftRight:
            cloned_replacement =
                clone_context->dst->Shr(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kAdd:
            cloned_replacement =
                clone_context->dst->Add(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kSubtract:
            cloned_replacement =
                clone_context->dst->Sub(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kMultiply:
            cloned_replacement =
                clone_context->dst->Mul(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kDivide:
            cloned_replacement =
                clone_context->dst->Div(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kModulo:
            cloned_replacement =
                clone_context->dst->Mod(clone_context->Clone(binary_expr_node->lhs),
                                        clone_context->Clone(binary_expr_node->rhs));
            break;
        case ast::BinaryOp::kNone:
            cloned_replacement = nullptr;
            assert(false && "Unreachable");
    }
    // Set things up so that the original binary expression will be replaced with
    // its clone, and update the id mapping.
    clone_context->Replace(binary_expr_node, cloned_replacement);
    new_node_id_map->Add(cloned_replacement, message_.binary_expr_id());
}

protobufs::Mutation MutationChangeBinaryOperator::ToMessage() const {
    protobufs::Mutation mutation;
    *mutation.mutable_change_binary_operator() = message_;
    return mutation;
}

}  // namespace tint::fuzzers::ast_fuzzer