//===--- BranchCloneCheck.cpp - clang-tidy --------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "BranchCloneCheck.h"
#include "../utils/ASTUtils.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/Analysis/CloneDetection.h"
#include "clang/Lex/Lexer.h"
#include "llvm/Support/Casting.h"

using namespace clang;
using namespace clang::ast_matchers;

namespace {
/// A branch in a switch may consist of several statements; while a branch in
/// an if/else if/else chain is one statement (which may be a CompoundStmt).
using SwitchBranch = llvm::SmallVector<const Stmt *, 2>;
} // anonymous namespace

/// Determines if the bodies of two branches in a switch statements are Type I
/// clones of each other. This function only examines the body of the branch
/// and ignores the `case X:` or `default:` at the start of the branch.
static bool areSwitchBranchesIdentical(const SwitchBranch &LHS,
                                       const SwitchBranch &RHS,
                                       const ASTContext &Context) {
  if (LHS.size() != RHS.size())
    return false;

  for (size_t I = 0, Size = LHS.size(); I < Size; I++) {
    // NOTE: We strip goto labels and annotations in addition to stripping
    // the `case X:` or `default:` labels, but it is very unlikely that this
    // would cause false positives in real-world code.
    if (!tidy::utils::areStatementsIdentical(LHS[I]->stripLabelLikeStatements(),
                                             RHS[I]->stripLabelLikeStatements(),
                                             Context)) {
      return false;
    }
  }

  return true;
}

static bool isFallthroughSwitchBranch(const SwitchBranch &Branch) {
  struct SwitchCaseVisitor : RecursiveASTVisitor<SwitchCaseVisitor> {
    using RecursiveASTVisitor<SwitchCaseVisitor>::DataRecursionQueue;

    bool TraverseLambdaExpr(LambdaExpr *, DataRecursionQueue * = nullptr) {
      return true; // Ignore lambdas
    }

    bool TraverseDecl(Decl *) {
      return true; // No need to check declarations
    }

    bool TraverseSwitchStmt(SwitchStmt *, DataRecursionQueue * = nullptr) {
      return true; // Ignore sub-switches
    }

    bool TraverseSwitchCase(SwitchCase *, DataRecursionQueue * = nullptr) {
      return true; // Ignore cases
    }

    bool TraverseDefaultStmt(DefaultStmt *, DataRecursionQueue * = nullptr) {
      return true; // Ignore defaults
    }

    bool TraverseAttributedStmt(AttributedStmt *S) {
      if (!S)
        return true;

      for (const Attr *A : S->getAttrs()) {
        if (isa<FallThroughAttr>(A))
          return false;
      }

      return true;
    }
  } Visitor;

  for (const Stmt *Elem : Branch) {
    if (!Visitor.TraverseStmt(const_cast<Stmt *>(Elem)))
      return true;
  }
  return false;
}

namespace clang::tidy::bugprone {

void BranchCloneCheck::registerMatchers(MatchFinder *Finder) {
  Finder->addMatcher(
      ifStmt(unless(allOf(isConstexpr(), isInTemplateInstantiation())),
             stmt().bind("if"),
             hasParent(stmt(unless(ifStmt(hasElse(equalsBoundNode("if")))))),
             hasElse(stmt().bind("else"))),
      this);
  Finder->addMatcher(switchStmt().bind("switch"), this);
  Finder->addMatcher(conditionalOperator().bind("condOp"), this);
  Finder->addMatcher(
      ifStmt((hasThen(hasDescendant(ifStmt())))).bind("ifWithDescendantIf"),
      this);
}

/// Determines whether two statement trees are identical regarding
/// operators and symbols.
///
/// Exceptions: expressions containing macros or functions with possible side
/// effects are never considered identical.
/// Limitations: (t + u) and (u + t) are not considered identical.
/// t*(u + t) and t*u + t*t are not considered identical.
///
static bool isIdenticalStmt(const ASTContext &Ctx, const Stmt *Stmt1,
                            const Stmt *Stmt2, bool IgnoreSideEffects) {

  if (!Stmt1 || !Stmt2)
    return !Stmt1 && !Stmt2;

  // If Stmt1 & Stmt2 are of different class then they are not
  // identical statements.
  if (Stmt1->getStmtClass() != Stmt2->getStmtClass())
    return false;

  const auto *Expr1 = dyn_cast<Expr>(Stmt1);
  const auto *Expr2 = dyn_cast<Expr>(Stmt2);

  if (Expr1 && Expr2) {
    // If Stmt1 has side effects then don't warn even if expressions
    // are identical.
    if (!IgnoreSideEffects && Expr1->HasSideEffects(Ctx) &&
        Expr2->HasSideEffects(Ctx))
      return false;
    // If either expression comes from a macro then don't warn even if
    // the expressions are identical.
    if ((Expr1->getExprLoc().isMacroID()) || (Expr2->getExprLoc().isMacroID()))
      return false;

    // If all children of two expressions are identical, return true.
    Expr::const_child_iterator I1 = Expr1->child_begin();
    Expr::const_child_iterator I2 = Expr2->child_begin();
    while (I1 != Expr1->child_end() && I2 != Expr2->child_end()) {
      if (!isIdenticalStmt(Ctx, *I1, *I2, IgnoreSideEffects))
        return false;
      ++I1;
      ++I2;
    }
    // If there are different number of children in the statements, return
    // false.
    if (I1 != Expr1->child_end())
      return false;
    if (I2 != Expr2->child_end())
      return false;
  }

  switch (Stmt1->getStmtClass()) {
  default:
    return false;
  case Stmt::CallExprClass:
  case Stmt::ArraySubscriptExprClass:
  case Stmt::ArraySectionExprClass:
  case Stmt::OMPArrayShapingExprClass:
  case Stmt::OMPIteratorExprClass:
  case Stmt::ImplicitCastExprClass:
  case Stmt::ParenExprClass:
  case Stmt::BreakStmtClass:
  case Stmt::ContinueStmtClass:
  case Stmt::NullStmtClass:
    return true;
  case Stmt::CStyleCastExprClass: {
    const auto *CastExpr1 = cast<CStyleCastExpr>(Stmt1);
    const auto *CastExpr2 = cast<CStyleCastExpr>(Stmt2);

    return CastExpr1->getTypeAsWritten() == CastExpr2->getTypeAsWritten();
  }
  case Stmt::ReturnStmtClass: {
    const auto *ReturnStmt1 = cast<ReturnStmt>(Stmt1);
    const auto *ReturnStmt2 = cast<ReturnStmt>(Stmt2);

    return isIdenticalStmt(Ctx, ReturnStmt1->getRetValue(),
                           ReturnStmt2->getRetValue(), IgnoreSideEffects);
  }
  case Stmt::ForStmtClass: {
    const auto *ForStmt1 = cast<ForStmt>(Stmt1);
    const auto *ForStmt2 = cast<ForStmt>(Stmt2);

    if (!isIdenticalStmt(Ctx, ForStmt1->getInit(), ForStmt2->getInit(),
                         IgnoreSideEffects))
      return false;
    if (!isIdenticalStmt(Ctx, ForStmt1->getCond(), ForStmt2->getCond(),
                         IgnoreSideEffects))
      return false;
    if (!isIdenticalStmt(Ctx, ForStmt1->getInc(), ForStmt2->getInc(),
                         IgnoreSideEffects))
      return false;
    if (!isIdenticalStmt(Ctx, ForStmt1->getBody(), ForStmt2->getBody(),
                         IgnoreSideEffects))
      return false;
    return true;
  }
  case Stmt::DoStmtClass: {
    const auto *DStmt1 = cast<DoStmt>(Stmt1);
    const auto *DStmt2 = cast<DoStmt>(Stmt2);

    if (!isIdenticalStmt(Ctx, DStmt1->getCond(), DStmt2->getCond(),
                         IgnoreSideEffects))
      return false;
    if (!isIdenticalStmt(Ctx, DStmt1->getBody(), DStmt2->getBody(),
                         IgnoreSideEffects))
      return false;
    return true;
  }
  case Stmt::WhileStmtClass: {
    const auto *WStmt1 = cast<WhileStmt>(Stmt1);
    const auto *WStmt2 = cast<WhileStmt>(Stmt2);

    if (!isIdenticalStmt(Ctx, WStmt1->getCond(), WStmt2->getCond(),
                         IgnoreSideEffects))
      return false;
    if (!isIdenticalStmt(Ctx, WStmt1->getBody(), WStmt2->getBody(),
                         IgnoreSideEffects))
      return false;
    return true;
  }
  case Stmt::IfStmtClass: {
    const auto *IStmt1 = cast<IfStmt>(Stmt1);
    const auto *IStmt2 = cast<IfStmt>(Stmt2);

    if (!isIdenticalStmt(Ctx, IStmt1->getCond(), IStmt2->getCond(),
                         IgnoreSideEffects))
      return false;
    if (!isIdenticalStmt(Ctx, IStmt1->getThen(), IStmt2->getThen(),
                         IgnoreSideEffects))
      return false;
    if (!isIdenticalStmt(Ctx, IStmt1->getElse(), IStmt2->getElse(),
                         IgnoreSideEffects))
      return false;
    return true;
  }
  case Stmt::CompoundStmtClass: {
    const auto *CompStmt1 = cast<CompoundStmt>(Stmt1);
    const auto *CompStmt2 = cast<CompoundStmt>(Stmt2);

    if (CompStmt1->size() != CompStmt2->size())
      return false;

    if (!llvm::all_of(llvm::zip(CompStmt1->body(), CompStmt2->body()),
                      [&Ctx, IgnoreSideEffects](
                          std::tuple<const Stmt *, const Stmt *> stmtPair) {
                        const Stmt *stmt0 = std::get<0>(stmtPair);
                        const Stmt *stmt1 = std::get<1>(stmtPair);
                        return isIdenticalStmt(Ctx, stmt0, stmt1,
                                               IgnoreSideEffects);
                      })) {
      return false;
    }

    return true;
  }
  case Stmt::CompoundAssignOperatorClass:
  case Stmt::BinaryOperatorClass: {
    const auto *BinOp1 = cast<BinaryOperator>(Stmt1);
    const auto *BinOp2 = cast<BinaryOperator>(Stmt2);
    return BinOp1->getOpcode() == BinOp2->getOpcode();
  }
  case Stmt::CharacterLiteralClass: {
    const auto *CharLit1 = cast<CharacterLiteral>(Stmt1);
    const auto *CharLit2 = cast<CharacterLiteral>(Stmt2);
    return CharLit1->getValue() == CharLit2->getValue();
  }
  case Stmt::DeclRefExprClass: {
    const auto *DeclRef1 = cast<DeclRefExpr>(Stmt1);
    const auto *DeclRef2 = cast<DeclRefExpr>(Stmt2);
    return DeclRef1->getDecl() == DeclRef2->getDecl();
  }
  case Stmt::IntegerLiteralClass: {
    const auto *IntLit1 = cast<IntegerLiteral>(Stmt1);
    const auto *IntLit2 = cast<IntegerLiteral>(Stmt2);

    llvm::APInt I1 = IntLit1->getValue();
    llvm::APInt I2 = IntLit2->getValue();
    if (I1.getBitWidth() != I2.getBitWidth())
      return false;
    return I1 == I2;
  }
  case Stmt::FloatingLiteralClass: {
    const auto *FloatLit1 = cast<FloatingLiteral>(Stmt1);
    const auto *FloatLit2 = cast<FloatingLiteral>(Stmt2);
    return FloatLit1->getValue().bitwiseIsEqual(FloatLit2->getValue());
  }
  case Stmt::StringLiteralClass: {
    const auto *StringLit1 = cast<StringLiteral>(Stmt1);
    const auto *StringLit2 = cast<StringLiteral>(Stmt2);
    return StringLit1->getBytes() == StringLit2->getBytes();
  }
  case Stmt::MemberExprClass: {
    const auto *MemberStmt1 = cast<MemberExpr>(Stmt1);
    const auto *MemberStmt2 = cast<MemberExpr>(Stmt2);
    return MemberStmt1->getMemberDecl() == MemberStmt2->getMemberDecl();
  }
  case Stmt::UnaryOperatorClass: {
    const auto *UnaryOp1 = cast<UnaryOperator>(Stmt1);
    const auto *UnaryOp2 = cast<UnaryOperator>(Stmt2);
    return UnaryOp1->getOpcode() == UnaryOp2->getOpcode();
  }
  }
}

void BranchCloneCheck::check(const MatchFinder::MatchResult &Result) {
  const ASTContext &Context = *Result.Context;

  if (const auto *IS = Result.Nodes.getNodeAs<IfStmt>("if")) {
    const Stmt *Then = IS->getThen();
    assert(Then && "An IfStmt must have a `then` branch!");

    const Stmt *Else = Result.Nodes.getNodeAs<Stmt>("else");
    assert(Else && "We only look for `if` statements with an `else` branch!");

    if (!isa<IfStmt>(Else)) {
      // Just a simple if with no `else if` branch.
      if (utils::areStatementsIdentical(Then->IgnoreContainers(),
                                        Else->IgnoreContainers(), Context)) {
        diag(IS->getBeginLoc(), "if with identical then and else branches");
        diag(IS->getElseLoc(), "else branch starts here", DiagnosticIDs::Note);
      }
      return;
    }

    // This is the complicated case when we start an if/else if/else chain.
    // To find all the duplicates, we collect all the branches into a vector.
    llvm::SmallVector<const Stmt *, 4> Branches;
    const IfStmt *Cur = IS;
    while (true) {
      // Store the `then` branch.
      Branches.push_back(Cur->getThen());

      Else = Cur->getElse();
      // The chain ends if there is no `else` branch.
      if (!Else)
        break;

      // Check if there is another `else if`...
      Cur = dyn_cast<IfStmt>(Else);
      if (!Cur) {
        // ...this is just a plain `else` branch at the end of the chain.
        Branches.push_back(Else);
        break;
      }
    }

    size_t N = Branches.size();
    llvm::BitVector KnownAsClone(N);

    for (size_t I = 0; I + 1 < N; I++) {
      // We have already seen Branches[i] as a clone of an earlier branch.
      if (KnownAsClone[I])
        continue;

      int NumCopies = 1;

      for (size_t J = I + 1; J < N; J++) {
        if (KnownAsClone[J] || !utils::areStatementsIdentical(
                                   Branches[I]->IgnoreContainers(),
                                   Branches[J]->IgnoreContainers(), Context))
          continue;

        NumCopies++;
        KnownAsClone[J] = true;

        if (NumCopies == 2) {
          // We report the first occurrence only when we find the second one.
          diag(Branches[I]->getBeginLoc(),
               "repeated branch body in conditional chain");
          SourceLocation End =
              Lexer::getLocForEndOfToken(Branches[I]->getEndLoc(), 0,
                                         *Result.SourceManager, getLangOpts());
          if (End.isValid()) {
            diag(End, "end of the original", DiagnosticIDs::Note);
          }
        }

        diag(Branches[J]->getBeginLoc(), "clone %0 starts here",
             DiagnosticIDs::Note)
            << (NumCopies - 1);
      }
    }
    return;
  }

  if (const auto *CO = Result.Nodes.getNodeAs<ConditionalOperator>("condOp")) {
    // We do not try to detect chains of ?: operators.
    if (utils::areStatementsIdentical(CO->getTrueExpr(), CO->getFalseExpr(),
                                      Context))
      diag(CO->getQuestionLoc(),
           "conditional operator with identical true and false expressions");

    return;
  }

  if (const auto *SS = Result.Nodes.getNodeAs<SwitchStmt>("switch")) {
    const auto *Body = dyn_cast_or_null<CompoundStmt>(SS->getBody());

    // Code like
    //   switch (x) case 0: case 1: foobar();
    // is legal and calls foobar() if and only if x is either 0 or 1;
    // but we do not try to distinguish branches in such code.
    if (!Body)
      return;

    // We will first collect the branches of the switch statements. For the
    // sake of simplicity we say that branches are delimited by the SwitchCase
    // (`case:` or `default:`) children of Body; that is, we ignore `case:` or
    // `default:` labels embedded inside other statements and we do not follow
    // the effects of `break` and other manipulation of the control-flow.
    llvm::SmallVector<SwitchBranch, 4> Branches;
    for (const Stmt *S : Body->body()) {
      // If this is a `case` or `default`, we start a new, empty branch.
      if (isa<SwitchCase>(S))
        Branches.emplace_back();

      // There may be code before the first branch (which can be dead code
      // and can be code reached either through goto or through case labels
      // that are embedded inside e.g. inner compound statements); we do not
      // store those statements in branches.
      if (!Branches.empty())
        Branches.back().push_back(S);
    }

    auto *End = Branches.end();
    auto *BeginCurrent = Branches.begin();
    while (BeginCurrent < End) {
      if (isFallthroughSwitchBranch(*BeginCurrent)) {
        ++BeginCurrent;
        continue;
      }

      auto *EndCurrent = BeginCurrent + 1;
      while (EndCurrent < End &&
             areSwitchBranchesIdentical(*BeginCurrent, *EndCurrent, Context)) {
        ++EndCurrent;
      }
      // At this point the iterator range {BeginCurrent, EndCurrent} contains a
      // complete family of consecutive identical branches.

      if (EndCurrent == (BeginCurrent + 1)) {
        // No consecutive identical branches that start on BeginCurrent
        BeginCurrent = EndCurrent;
        continue;
      }

      diag(BeginCurrent->front()->getBeginLoc(),
           "switch has %0 consecutive identical branches")
          << static_cast<int>(std::distance(BeginCurrent, EndCurrent));

      SourceLocation EndLoc = (EndCurrent - 1)->back()->getEndLoc();
      // If the case statement is generated from a macro, it's SourceLocation
      // may be invalid, resulting in an assertion failure down the line.
      // While not optimal, try the begin location in this case, it's still
      // better then nothing.
      if (EndLoc.isInvalid())
        EndLoc = (EndCurrent - 1)->back()->getBeginLoc();
      if (EndLoc.isMacroID())
        EndLoc = Context.getSourceManager().getExpansionLoc(EndLoc);
      EndLoc = Lexer::getLocForEndOfToken(EndLoc, 0, *Result.SourceManager,
                                          getLangOpts());
      if (EndLoc.isValid()) {
        diag(EndLoc, "last of these clones ends here", DiagnosticIDs::Note);
      }
      BeginCurrent = EndCurrent;
    }
    return;
  }

  if (const auto *IS = Result.Nodes.getNodeAs<IfStmt>("ifWithDescendantIf")) {
    const Stmt *Then = IS->getThen();
    auto CS = dyn_cast<CompoundStmt>(Then);
    if (CS && (!CS->body_empty())) {
      const auto *InnerIf = dyn_cast<IfStmt>(*CS->body_begin());
      if (InnerIf && isIdenticalStmt(Context, IS->getCond(), InnerIf->getCond(),
                                     /*IgnoreSideEffects=*/false)) {
        diag(IS->getBeginLoc(), "if with identical inner if statement");
        diag(InnerIf->getBeginLoc(), "inner if starts here",
             DiagnosticIDs::Note);
      }
    }
    return;
  }

  llvm_unreachable("No if statement and no switch statement.");
}

} // namespace clang::tidy::bugprone