//===- unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp ===//
//
// 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 "NoopAnalysis.h"
#include "TestingSupport.h"
#include "clang/AST/Decl.h"
#include "clang/AST/ExprCXX.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "clang/Analysis/FlowSensitive/Value.h"
#include "clang/Tooling/Tooling.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Error.h"
#include "llvm/Testing/Support/Error.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include <cassert>
#include <memory>
#include <ostream>
#include <string>
#include <utility>
#include <vector>

namespace {

using namespace clang;
using namespace dataflow;
using namespace test;
using namespace ast_matchers;
using ::testing::_;
using ::testing::ElementsAre;
using ::testing::IsEmpty;
using ::testing::IsNull;
using ::testing::NotNull;
using ::testing::Pair;
using ::testing::Test;
using ::testing::UnorderedElementsAre;

template <typename AnalysisT>
class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback {
public:
  AnalysisCallback(AnalysisT (*MakeAnalysis)(ASTContext &))
      : MakeAnalysis(MakeAnalysis) {}
  void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
    assert(BlockStates.empty());

    const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
    assert(Func != nullptr);

    Stmt *Body = Func->getBody();
    assert(Body != nullptr);

    auto CFCtx = llvm::cantFail(
        ControlFlowContext::build(nullptr, Body, Result.Context));

    AnalysisT Analysis = MakeAnalysis(*Result.Context);
    DataflowAnalysisContext DACtx;
    Environment Env(DACtx);
    BlockStates = runDataflowAnalysis(CFCtx, Analysis, Env);
  }

  AnalysisT (*MakeAnalysis)(ASTContext &);
  std::vector<
      llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
      BlockStates;
};

template <typename AnalysisT>
std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
  std::unique_ptr<ASTUnit> AST =
      tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});

  AnalysisCallback<AnalysisT> Callback(MakeAnalysis);
  ast_matchers::MatchFinder Finder;
  Finder.addMatcher(
      ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"),
      &Callback);
  Finder.matchAST(AST->getASTContext());

  return Callback.BlockStates;
}

TEST(DataflowAnalysisTest, NoopAnalysis) {
  auto BlockStates = runAnalysis<NoopAnalysis>(
      "void target() {}", [](ASTContext &C) { return NoopAnalysis(C, false); });
  EXPECT_EQ(BlockStates.size(), 2u);
  EXPECT_TRUE(BlockStates[0].hasValue());
  EXPECT_TRUE(BlockStates[1].hasValue());
}

struct NonConvergingLattice {
  int State;

  bool operator==(const NonConvergingLattice &Other) const {
    return State == Other.State;
  }

  LatticeJoinEffect join(const NonConvergingLattice &Other) {
    if (Other.State == 0)
      return LatticeJoinEffect::Unchanged;
    State += Other.State;
    return LatticeJoinEffect::Changed;
  }
};

class NonConvergingAnalysis
    : public DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice> {
public:
  explicit NonConvergingAnalysis(ASTContext &Context)
      : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(
            Context,
            /*ApplyBuiltinTransfer=*/false) {}

  static NonConvergingLattice initialElement() { return {0}; }

  void transfer(const Stmt *S, NonConvergingLattice &E, Environment &Env) {
    ++E.State;
  }
};

TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
  auto BlockStates = runAnalysis<NonConvergingAnalysis>(
      R"(
    void target() {
      while(true) {}
    }
  )",
      [](ASTContext &C) { return NonConvergingAnalysis(C); });
  EXPECT_EQ(BlockStates.size(), 4u);
  EXPECT_TRUE(BlockStates[0].hasValue());
  EXPECT_TRUE(BlockStates[1].hasValue());
  EXPECT_TRUE(BlockStates[2].hasValue());
  EXPECT_TRUE(BlockStates[3].hasValue());
}

struct FunctionCallLattice {
  llvm::SmallSet<std::string, 8> CalledFunctions;

  bool operator==(const FunctionCallLattice &Other) const {
    return CalledFunctions == Other.CalledFunctions;
  }

  LatticeJoinEffect join(const FunctionCallLattice &Other) {
    if (Other.CalledFunctions.empty())
      return LatticeJoinEffect::Unchanged;
    const size_t size_before = CalledFunctions.size();
    CalledFunctions.insert(Other.CalledFunctions.begin(),
                           Other.CalledFunctions.end());
    return CalledFunctions.size() == size_before ? LatticeJoinEffect::Unchanged
                                                 : LatticeJoinEffect::Changed;
  }
};

std::ostream &operator<<(std::ostream &OS, const FunctionCallLattice &L) {
  std::string S;
  llvm::raw_string_ostream ROS(S);
  llvm::interleaveComma(L.CalledFunctions, ROS);
  return OS << "{" << S << "}";
}

class FunctionCallAnalysis
    : public DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice> {
public:
  explicit FunctionCallAnalysis(ASTContext &Context)
      : DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice>(Context) {}

  static FunctionCallLattice initialElement() { return {}; }

  void transfer(const Stmt *S, FunctionCallLattice &E, Environment &Env) {
    if (auto *C = dyn_cast<CallExpr>(S)) {
      if (auto *F = dyn_cast<FunctionDecl>(C->getCalleeDecl())) {
        E.CalledFunctions.insert(F->getNameInfo().getAsString());
      }
    }
  }
};

class NoreturnDestructorTest : public Test {
protected:
  template <typename Matcher>
  void runDataflow(llvm::StringRef Code, Matcher Expectations) {
    tooling::FileContentMappings FilesContents;
    FilesContents.push_back(std::make_pair<std::string, std::string>(
        "noreturn_destructor_test_defs.h", R"(
      int foo();

      class Fatal {
       public:
        ~Fatal() __attribute__((noreturn));
        int bar();
        int baz();
      };

      class NonFatal {
       public:
        ~NonFatal();
        int bar();
      };
    )"));

    ASSERT_THAT_ERROR(
        test::checkDataflow<FunctionCallAnalysis>(
            Code, "target",
            [](ASTContext &C, Environment &) {
              return FunctionCallAnalysis(C);
            },
            [&Expectations](
                llvm::ArrayRef<std::pair<
                    std::string, DataflowAnalysisState<FunctionCallLattice>>>
                    Results,
                ASTContext &) { EXPECT_THAT(Results, Expectations); },
            {"-fsyntax-only", "-std=c++17"}, FilesContents),
        llvm::Succeeded());
  }
};

MATCHER_P(HoldsFunctionCallLattice, m,
          ((negation ? "doesn't hold" : "holds") +
           llvm::StringRef(" a lattice element that ") +
           ::testing::DescribeMatcher<FunctionCallLattice>(m, negation))
              .str()) {
  return ExplainMatchResult(m, arg.Lattice, result_listener);
}

MATCHER_P(HasCalledFunctions, m, "") {
  return ExplainMatchResult(m, arg.CalledFunctions, result_listener);
}

TEST_F(NoreturnDestructorTest, ConditionalOperatorBothBranchesReturn) {
  std::string Code = R"(
    #include "noreturn_destructor_test_defs.h"

    void target(bool b) {
      int value = b ? foo() : NonFatal().bar();
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(Code, UnorderedElementsAre(
                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
                                      UnorderedElementsAre("foo", "bar"))))));
}

TEST_F(NoreturnDestructorTest, ConditionalOperatorLeftBranchReturns) {
  std::string Code = R"(
    #include "noreturn_destructor_test_defs.h"

    void target(bool b) {
      int value = b ? foo() : Fatal().bar();
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(Code, UnorderedElementsAre(
                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
                                      UnorderedElementsAre("foo"))))));
}

TEST_F(NoreturnDestructorTest, ConditionalOperatorRightBranchReturns) {
  std::string Code = R"(
    #include "noreturn_destructor_test_defs.h"

    void target(bool b) {
      int value = b ? Fatal().bar() : foo();
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(Code, UnorderedElementsAre(
                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
                                      UnorderedElementsAre("foo"))))));
}

TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchesDoNotReturn) {
  std::string Code = R"(
    #include "noreturn_destructor_test_defs.h"

    void target(bool b1, bool b2) {
      int value = b1 ? foo() : (b2 ? Fatal().bar() : Fatal().baz());
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(Code, IsEmpty());
  // FIXME: Called functions at point `p` should contain "foo".
}

TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchReturns) {
  std::string Code = R"(
    #include "noreturn_destructor_test_defs.h"

    void target(bool b1, bool b2) {
      int value = b1 ? Fatal().bar() : (b2 ? Fatal().baz() : foo());
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(Code, UnorderedElementsAre(
                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
                                      UnorderedElementsAre("baz", "foo"))))));
  // FIXME: Called functions at point `p` should contain only "foo".
}

class OptionalIntAnalysis
    : public DataflowAnalysis<OptionalIntAnalysis, NoopLattice> {
public:
  explicit OptionalIntAnalysis(ASTContext &Context)
      : DataflowAnalysis<OptionalIntAnalysis, NoopLattice>(Context) {}

  static NoopLattice initialElement() { return {}; }

  void transfer(const Stmt *S, NoopLattice &, Environment &Env) {
    auto OptionalIntRecordDecl = recordDecl(hasName("OptionalInt"));
    auto HasOptionalIntType = hasType(OptionalIntRecordDecl);

    if (const auto *E = selectFirst<CXXConstructExpr>(
            "call", match(cxxConstructExpr(HasOptionalIntType).bind("call"), *S,
                          getASTContext()))) {
      auto &ConstructorVal = *cast<StructValue>(Env.createValue(E->getType()));
      ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(false));
      Env.setValue(*Env.getStorageLocation(*E, SkipPast::None), ConstructorVal);
    } else if (const auto *E = selectFirst<CXXOperatorCallExpr>(
                   "call",
                   match(cxxOperatorCallExpr(callee(cxxMethodDecl(ofClass(
                                                 OptionalIntRecordDecl))))
                             .bind("call"),
                         *S, getASTContext()))) {
      assert(E->getNumArgs() > 0);
      auto *Object = E->getArg(0);
      assert(Object != nullptr);

      auto *ObjectLoc =
          Env.getStorageLocation(*Object, SkipPast::ReferenceThenPointer);
      assert(ObjectLoc != nullptr);

      auto &ConstructorVal =
          *cast<StructValue>(Env.createValue(Object->getType()));
      ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(true));
      Env.setValue(*ObjectLoc, ConstructorVal);
    }
  }

  bool merge(QualType Type, const Value &Val1, const Value &Val2,
             Value &MergedVal, Environment &Env) final {
    if (!Type->isRecordType() ||
        Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
      return false;

    auto *HasValue1 = cast_or_null<BoolValue>(
        cast<StructValue>(&Val1)->getProperty("has_value"));
    if (HasValue1 == nullptr)
      return false;

    auto *HasValue2 = cast_or_null<BoolValue>(
        cast<StructValue>(&Val2)->getProperty("has_value"));
    if (HasValue2 == nullptr)
      return false;

    if (HasValue1 != HasValue2)
      return false;

    cast<StructValue>(&MergedVal)->setProperty("has_value", *HasValue1);
    return true;
  }
};

class WideningTest : public Test {
protected:
  template <typename Matcher>
  void runDataflow(llvm::StringRef Code, Matcher Match) {
    tooling::FileContentMappings FilesContents;
    FilesContents.push_back(
        std::make_pair<std::string, std::string>("widening_test_defs.h", R"(
      struct OptionalInt {
        OptionalInt() = default;
        OptionalInt& operator=(int);
      };
    )"));
    ASSERT_THAT_ERROR(
        test::checkDataflow<OptionalIntAnalysis>(
            Code, "target",
            [](ASTContext &Context, Environment &Env) {
              return OptionalIntAnalysis(Context);
            },
            [&Match](
                llvm::ArrayRef<
                    std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                    Results,
                ASTContext &ASTCtx) { Match(Results, ASTCtx); },
            {"-fsyntax-only", "-std=c++17"}, FilesContents),
        llvm::Succeeded());
  }
};

TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) {
  std::string Code = R"(
    #include "widening_test_defs.h"

    void target(bool Cond) {
      OptionalInt Foo;
      /*[[p1]]*/
      if (Cond) {
        Foo = 1;
        /*[[p2]]*/
      }
      (void)0;
      /*[[p3]]*/
    }
  )";
  runDataflow(
      Code, [](llvm::ArrayRef<
                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                   Results,
               ASTContext &ASTCtx) {
        ASSERT_THAT(Results,
                    ElementsAre(Pair("p3", _), Pair("p2", _), Pair("p1", _)));
        const Environment &Env1 = Results[2].second.Env;
        const Environment &Env2 = Results[1].second.Env;
        const Environment &Env3 = Results[0].second.Env;

        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
        ASSERT_THAT(FooDecl, NotNull());

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return cast<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
        };

        EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
                  &Env1.getBoolLiteralValue(false));
        EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
                  &Env2.getBoolLiteralValue(true));
        EXPECT_THAT(Env3.getValue(*FooDecl, SkipPast::None), IsNull());
      });
}

TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) {
  std::string Code = R"(
    #include "widening_test_defs.h"

    void target(bool Cond) {
      OptionalInt Foo;
      /*[[p1]]*/
      if (Cond) {
        Foo = 1;
        /*[[p2]]*/
      } else {
        Foo = 2;
        /*[[p3]]*/
      }
      (void)0;
      /*[[p4]]*/
    }
  )";
  runDataflow(
      Code, [](llvm::ArrayRef<
                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                   Results,
               ASTContext &ASTCtx) {
        ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _),
                                         Pair("p2", _), Pair("p1", _)));
        const Environment &Env1 = Results[3].second.Env;
        const Environment &Env2 = Results[2].second.Env;
        const Environment &Env3 = Results[1].second.Env;
        const Environment &Env4 = Results[0].second.Env;

        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
        ASSERT_THAT(FooDecl, NotNull());

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return cast<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
        };

        EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
                  &Env1.getBoolLiteralValue(false));
        EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
                  &Env2.getBoolLiteralValue(true));
        EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
                  &Env3.getBoolLiteralValue(true));
        EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
                  &Env4.getBoolLiteralValue(true));
      });
}

} // namespace
