Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

//===- 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 "TestingSupport.h"
#include "clang/AST/Decl.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/OperationKinds.h"
#include "clang/AST/Type.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/DebugSupport.h"
#include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
#include "clang/Analysis/FlowSensitive/Value.h"
#include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
#include "clang/Tooling/Tooling.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Error.h"
#include "llvm/Testing/ADT/StringMapEntry.h"
#include "llvm/Testing/Support/Error.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include <cassert>
#include <memory>
#include <optional>
#include <ostream>
#include <string>
#include <utility>
#include <vector>

namespace {

using namespace clang;
using namespace dataflow;
using namespace test;
using namespace ast_matchers;
using llvm::IsStringMapEntry;
using ::testing::DescribeMatcher;
using ::testing::IsEmpty;
using ::testing::NotNull;
using ::testing::Test;
using ::testing::UnorderedElementsAre;

class DataflowAnalysisTest : public Test {
protected:
  template <typename AnalysisT>
  llvm::Expected<std::vector<
      std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
  runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
    AST = tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});

    auto *Func = selectFirst<FunctionDecl>(
        "func",
        match(functionDecl(ast_matchers::hasName("target")).bind("func"),
              AST->getASTContext()));
    assert(Func != nullptr);

    ACFG =
        std::make_unique<AdornedCFG>(llvm::cantFail(AdornedCFG::build(*Func)));

    AnalysisT Analysis = MakeAnalysis(AST->getASTContext());
    DACtx = std::make_unique<DataflowAnalysisContext>(
        std::make_unique<WatchedLiteralsSolver>());
    Environment Env(*DACtx, *Func);

    return runDataflowAnalysis(*ACFG, Analysis, Env);
  }

  /// Returns the `CFGBlock` containing `S` (and asserts that it exists).
  const CFGBlock *blockForStmt(const Stmt &S) {
    const CFGBlock *Block = ACFG->blockForStmt(S);
    assert(Block != nullptr);
    return Block;
  }

  template <typename StateT>
  const StateT &
  blockStateForStmt(const std::vector<std::optional<StateT>> &BlockStates,
                    const Stmt &S) {
    const std::optional<StateT> &MaybeState =
        BlockStates[blockForStmt(S)->getBlockID()];
    assert(MaybeState.has_value());
    return *MaybeState;
  }

  /// Returns the first node that matches `Matcher` (and asserts that the match
  /// was successful, i.e. the returned node is not null).
  template <typename NodeT, typename MatcherT>
  const NodeT &matchNode(MatcherT Matcher) {
    const auto *Node = selectFirst<NodeT>(
        "node", match(Matcher.bind("node"), AST->getASTContext()));
    assert(Node != nullptr);
    return *Node;
  }

  std::unique_ptr<ASTUnit> AST;
  std::unique_ptr<AdornedCFG> ACFG;
  std::unique_ptr<DataflowAnalysisContext> DACtx;
};

TEST_F(DataflowAnalysisTest, NoopAnalysis) {
  auto BlockStates = llvm::cantFail(
      runAnalysis<NoopAnalysis>("void target() {}", [](ASTContext &C) {
        return NoopAnalysis(C,
                            // Don't use builtin transfer function.
                            DataflowAnalysisOptions{std::nullopt});
      }));
  EXPECT_EQ(BlockStates.size(), 2u);
  EXPECT_TRUE(BlockStates[0].has_value());
  EXPECT_TRUE(BlockStates[1].has_value());
}

// Basic test that `diagnoseFunction` calls the Diagnoser function for the
// number of elements expected.
TEST_F(DataflowAnalysisTest, DiagnoseFunctionDiagnoserCalledOnEachElement) {
  std::string Code = R"(void target() { int x = 0; ++x; })";
  std::unique_ptr<ASTUnit> AST =
      tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});

  auto *Func =
      cast<FunctionDecl>(findValueDecl(AST->getASTContext(), "target"));
  auto Diagnoser = [](const CFGElement &Elt, ASTContext &,
                      const TransferStateForDiagnostics<NoopLattice> &) {
    llvm::SmallVector<std::string> Diagnostics(1);
    llvm::raw_string_ostream OS(Diagnostics.front());
    Elt.dumpToStream(OS);
    return Diagnostics;
  };
  auto Result = diagnoseFunction<NoopAnalysis, std::string>(
      *Func, AST->getASTContext(), Diagnoser);
  // `diagnoseFunction` provides no guarantees about the order in which elements
  // are visited, so we use `UnorderedElementsAre`.
  EXPECT_THAT_EXPECTED(Result, llvm::HasValue(UnorderedElementsAre(
                                   "0\n", "int x = 0;\n", "x\n", "++x\n",
                                   " (Lifetime ends)\n")));
}

TEST_F(DataflowAnalysisTest, CanAnalyzeStmt) {
  std::string Code = R"cc(
      struct S { bool b; };
      void foo() {
        S AnS = S{true};
      }
    )cc";
  AST = tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
  const auto &DeclStatement =
      matchNode<DeclStmt>(declStmt(hasSingleDecl(varDecl(hasName("AnS")))));
  const auto &Func = matchNode<FunctionDecl>(functionDecl(hasName("foo")));

  ACFG = std::make_unique<AdornedCFG>(llvm::cantFail(AdornedCFG::build(
      Func, const_cast<DeclStmt &>(DeclStatement), AST->getASTContext())));

  NoopAnalysis Analysis = NoopAnalysis(AST->getASTContext());
  DACtx = std::make_unique<DataflowAnalysisContext>(
      std::make_unique<WatchedLiteralsSolver>());
  Environment Env(*DACtx, const_cast<DeclStmt &>(DeclStatement));

  llvm::Expected<std::vector<std::optional<DataflowAnalysisState<NoopLattice>>>>
      Results = runDataflowAnalysis(*ACFG, Analysis, Env);

  ASSERT_THAT_ERROR(Results.takeError(), llvm::Succeeded());
  const Environment &ExitBlockEnv = Results->front()->Env;
  BoolValue *BoolFieldValue = cast<BoolValue>(
      getFieldValue(ExitBlockEnv.get<RecordStorageLocation>(
                        *cast<VarDecl>((*DeclStatement.decl_begin()))),
                    "b", AST->getASTContext(), ExitBlockEnv));
  EXPECT_TRUE(Env.proves(BoolFieldValue->formula()));
}

// Tests for the statement-to-block map.
using StmtToBlockTest = DataflowAnalysisTest;

TEST_F(StmtToBlockTest, ConditionalOperator) {
  std::string Code = R"(
    void target(bool b) {
      int i = b ? 1 : 0;
    }
  )";
  ASSERT_THAT_ERROR(runAnalysis<NoopAnalysis>(
                        Code, [](ASTContext &C) { return NoopAnalysis(C); })
                        .takeError(),
                    llvm::Succeeded());

  const auto &IDecl = matchNode<DeclStmt>(declStmt(has(varDecl(hasName("i")))));
  const auto &ConditionalOp =
      matchNode<ConditionalOperator>(conditionalOperator());

  // The conditional operator should be associated with the same block as the
  // `DeclStmt` for `i`. (Specifically, the conditional operator should not be
  // associated with the block for which it is the terminator.)
  EXPECT_EQ(blockForStmt(IDecl), blockForStmt(ConditionalOp));
}

TEST_F(StmtToBlockTest, LogicalAnd) {
  std::string Code = R"(
    void target(bool b1, bool b2) {
      bool b = b1 && b2;
    }
  )";
  ASSERT_THAT_ERROR(runAnalysis<NoopAnalysis>(
                        Code, [](ASTContext &C) { return NoopAnalysis(C); })
                        .takeError(),
                    llvm::Succeeded());

  const auto &BDecl = matchNode<DeclStmt>(declStmt(has(varDecl(hasName("b")))));
  const auto &AndOp =
      matchNode<BinaryOperator>(binaryOperator(hasOperatorName("&&")));

  // The `&&` operator should be associated with the same block as the
  // `DeclStmt` for `b`. (Specifically, the `&&` operator should not be
  // associated with the block for which it is the terminator.)
  EXPECT_EQ(blockForStmt(BDecl), blockForStmt(AndOp));
}

TEST_F(StmtToBlockTest, IfStatementWithLogicalAnd) {
  std::string Code = R"(
    void target(bool b1, bool b2) {
      if (b1 && b2)
        ;
    }
  )";
  ASSERT_THAT_ERROR(runAnalysis<NoopAnalysis>(
                        Code, [](ASTContext &C) { return NoopAnalysis(C); })
                        .takeError(),
                    llvm::Succeeded());

  const auto &If = matchNode<IfStmt>(ifStmt());
  const auto &B2 =
      matchNode<DeclRefExpr>(declRefExpr(to(varDecl(hasName("b2")))));
  const auto &AndOp =
      matchNode<BinaryOperator>(binaryOperator(hasOperatorName("&&")));

  // The if statement is the terminator for the block that contains both `b2`
  // and the `&&` operator (which appears only as a terminator condition, not
  // as a regular `CFGElement`).
  const CFGBlock *IfBlock = blockForStmt(If);
  const CFGBlock *B2Block = blockForStmt(B2);
  const CFGBlock *AndOpBlock = blockForStmt(AndOp);
  EXPECT_EQ(IfBlock, B2Block);
  EXPECT_EQ(IfBlock, AndOpBlock);
}

// Tests that check we discard state for expressions correctly.
using DiscardExprStateTest = DataflowAnalysisTest;

TEST_F(DiscardExprStateTest, WhileStatement) {
  std::string Code = R"(
    void foo(int *p);
    void target(int *p) {
      while (p != nullptr)
        foo(p);
    }
  )";
  auto BlockStates = llvm::cantFail(runAnalysis<NoopAnalysis>(
      Code, [](ASTContext &C) { return NoopAnalysis(C); }));

  const auto &NotEqOp =
      matchNode<BinaryOperator>(binaryOperator(hasOperatorName("!=")));
  const auto &CallFoo =
      matchNode<CallExpr>(callExpr(callee(functionDecl(hasName("foo")))));

  // In the block that evaluates the expression `p != nullptr`, this expression
  // is associated with a value.
  const auto &NotEqOpState = blockStateForStmt(BlockStates, NotEqOp);
  EXPECT_NE(NotEqOpState.Env.getValue(NotEqOp), nullptr);

  // In the block that calls `foo(p)`, the value for `p != nullptr` is discarded
  // because it is not consumed outside the block it is in.
  const auto &CallFooState = blockStateForStmt(BlockStates, CallFoo);
  EXPECT_EQ(CallFooState.Env.getValue(NotEqOp), nullptr);
}

TEST_F(DiscardExprStateTest, BooleanOperator) {
  std::string Code = R"(
    void f();
    void target(bool b1, bool b2) {
      if (b1 && b2)
        f();
    }
  )";
  auto BlockStates = llvm::cantFail(runAnalysis<NoopAnalysis>(
      Code, [](ASTContext &C) { return NoopAnalysis(C); }));

  const auto &AndOp =
      matchNode<BinaryOperator>(binaryOperator(hasOperatorName("&&")));
  const auto &CallF =
      matchNode<CallExpr>(callExpr(callee(functionDecl(hasName("f")))));

  // In the block that evaluates the LHS of the `&&` operator, the LHS is
  // associated with a value, while the right-hand side is not (unsurprisingly,
  // as it hasn't been evaluated yet).
  const auto &LHSState = blockStateForStmt(BlockStates, *AndOp.getLHS());
  auto *LHSValue = cast<BoolValue>(LHSState.Env.getValue(*AndOp.getLHS()));
  EXPECT_NE(LHSValue, nullptr);
  EXPECT_EQ(LHSState.Env.getValue(*AndOp.getRHS()), nullptr);

  // In the block that evaluates the RHS, both the LHS and RHS are associated
  // with values, as they are both subexpressions of the `&&` operator, which
  // is evaluated in a later block.
  const auto &RHSState = blockStateForStmt(BlockStates, *AndOp.getRHS());
  EXPECT_EQ(RHSState.Env.getValue(*AndOp.getLHS()), LHSValue);
  auto *RHSValue = RHSState.Env.get<BoolValue>(*AndOp.getRHS());
  EXPECT_NE(RHSValue, nullptr);

  // In the block that evaluates `b1 && b2`, the `&&` as well as its operands
  // are associated with values.
  const auto &AndOpState = blockStateForStmt(BlockStates, AndOp);
  EXPECT_EQ(AndOpState.Env.getValue(*AndOp.getLHS()), LHSValue);
  EXPECT_EQ(AndOpState.Env.getValue(*AndOp.getRHS()), RHSValue);
  EXPECT_EQ(AndOpState.Env.getValue(AndOp),
            &AndOpState.Env.makeAnd(*LHSValue, *RHSValue));

  // In the block that calls `f()`, none of `b1`, `b2`, or `b1 && b2` should be
  // associated with values.
  const auto &CallFState = blockStateForStmt(BlockStates, CallF);
  EXPECT_EQ(CallFState.Env.getValue(*AndOp.getLHS()), nullptr);
  EXPECT_EQ(CallFState.Env.getValue(*AndOp.getRHS()), nullptr);
  EXPECT_EQ(CallFState.Env.getValue(AndOp), nullptr);
}

TEST_F(DiscardExprStateTest, ConditionalOperator) {
  std::string Code = R"(
    void f(int*, int);
    void g();
    bool cond();

    void target() {
      int i = 0;
      if (cond())
        f(&i, cond() ? 1 : 0);
      g();
    }
  )";
  auto BlockStates = llvm::cantFail(runAnalysis<NoopAnalysis>(
      Code, [](ASTContext &C) { return NoopAnalysis(C); }));

  const auto &AddrOfI =
      matchNode<UnaryOperator>(unaryOperator(hasOperatorName("&")));
  const auto &CallF =
      matchNode<CallExpr>(callExpr(callee(functionDecl(hasName("f")))));
  const auto &CallG =
      matchNode<CallExpr>(callExpr(callee(functionDecl(hasName("g")))));

  // In the block that evaluates `&i`, it should obviously have a value.
  const auto &AddrOfIState = blockStateForStmt(BlockStates, AddrOfI);
  auto *AddrOfIVal = AddrOfIState.Env.get<PointerValue>(AddrOfI);
  EXPECT_NE(AddrOfIVal, nullptr);

  // Because of the conditional operator, the `f(...)` call is evaluated in a
  // different block than `&i`, but `&i` still needs to have a value here
  // because it's a subexpression of the call.
  const auto &CallFState = blockStateForStmt(BlockStates, CallF);
  EXPECT_NE(&CallFState, &AddrOfIState);
  EXPECT_EQ(CallFState.Env.get<PointerValue>(AddrOfI), AddrOfIVal);

  // In the block that calls `g()`, `&i` should no longer be associated with a
  // value.
  const auto &CallGState = blockStateForStmt(BlockStates, CallG);
  EXPECT_EQ(CallGState.Env.get<PointerValue>(AddrOfI), nullptr);
}

TEST_F(DiscardExprStateTest, CallWithParenExprTreatedCorrectly) {
  // This is a regression test.
  // In the CFG for `target()` below, the expression that evaluates the function
  // pointer for `expect` and the actual call are separated into different
  // baseic blocks (because of the control flow introduced by the `||`
  // operator).
  // The value for the `expect` function pointer was erroneously discarded
  // from the environment between these two blocks because the code that
  // determines whether the expression values for a block need to be preserved
  // did not ignore the `ParenExpr` around `(i == 1)` (which is not represented
  // in the CFG).
  std::string Code = R"(
    bool expect(bool, bool);
    void target(int i) {
      expect(false || (i == 1), false);
    }
  )";
  auto BlockStates = llvm::cantFail(runAnalysis<NoopAnalysis>(
      Code, [](ASTContext &C) { return NoopAnalysis(C); }));

  const auto &FnToPtrDecay = matchNode<ImplicitCastExpr>(
      implicitCastExpr(hasCastKind(CK_FunctionToPointerDecay)));
  const auto &CallExpect =
      matchNode<CallExpr>(callExpr(callee(functionDecl(hasName("expect")))));

  // In the block that evaluates the implicit cast of `expect` to a pointer,
  // this expression is associated with a value.
  const auto &FnToPtrDecayState = blockStateForStmt(BlockStates, FnToPtrDecay);
  EXPECT_NE(FnToPtrDecayState.Env.getValue(FnToPtrDecay), nullptr);

  // In the block that calls `expect()`, the implicit cast of `expect` to a
  // pointer is still associated with a value.
  const auto &CallExpectState = blockStateForStmt(BlockStates, CallExpect);
  EXPECT_NE(CallExpectState.Env.getValue(FnToPtrDecay), nullptr);
}

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,
            // Don't apply builtin transfer function.
            DataflowAnalysisOptions{std::nullopt}) {}

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

  void transfer(const CFGElement &, NonConvergingLattice &E, Environment &) {
    ++E.State;
  }
};

TEST_F(DataflowAnalysisTest, NonConvergingAnalysis) {
  std::string Code = R"(
    void target() {
      while(true) {}
    }
  )";
  auto Res = runAnalysis<NonConvergingAnalysis>(
      Code, [](ASTContext &C) { return NonConvergingAnalysis(C); });
  EXPECT_EQ(llvm::toString(Res.takeError()),
            "maximum number of blocks processed");
}

// Regression test for joins of bool-typed lvalue expressions. The first loop
// results in two passes through the code that follows. Each pass results in a
// different `StorageLocation` for the pointee of `v`. Then, the second loop
// causes a join at the loop head where the two environments map expresssion
// `*v` to different `StorageLocation`s.
//
// An earlier version crashed for this condition (for boolean-typed lvalues), so
// this test only verifies that the analysis runs successfully, without
// examining any details of the results.
TEST_F(DataflowAnalysisTest, JoinBoolLValues) {
  std::string Code = R"(
    void target() {
      for (int x = 1; x; x = 0)
        (void)x;
      bool *v;
      if (*v)
        for (int x = 1; x; x = 0)
          (void)x;
    }
  )";
  ASSERT_THAT_ERROR(
      runAnalysis<NoopAnalysis>(Code,
                                [](ASTContext &C) {
                                  auto EnableBuiltIns = DataflowAnalysisOptions{
                                      DataflowAnalysisContext::Options{}};
                                  return NoopAnalysis(C, EnableBuiltIns);
                                })
          .takeError(),
      llvm::Succeeded());
}

struct FunctionCallLattice {
  using FunctionSet = llvm::SmallSet<std::string, 8>;
  FunctionSet 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 CFGElement &Elt, FunctionCallLattice &E, Environment &) {
    auto CS = Elt.getAs<CFGStmt>();
    if (!CS)
      return;
    const auto *S = CS->getStmt();
    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>(
            AnalysisInputs<FunctionCallAnalysis>(
                Code, ast_matchers::hasName("target"),
                [](ASTContext &C, Environment &) {
                  return FunctionCallAnalysis(C);
                })
                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
                .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
            /*VerifyResults=*/
            [&Expectations](
                const llvm::StringMap<
                    DataflowAnalysisState<FunctionCallLattice>> &Results,
                const AnalysisOutputs &) {
              EXPECT_THAT(Results, Expectations);
            }),
        llvm::Succeeded());
  }
};

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

MATCHER_P(HasCalledFunctions, m,
          ((negation ? "doesn't hold" : "holds") +
           llvm::StringRef(" a set of called functions that ") +
           DescribeMatcher<FunctionCallLattice::FunctionSet>(m))
              .str()) {
  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(IsStringMapEntry(
                        "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(IsStringMapEntry(
                        "p", HoldsFunctionCallLattice(HasCalledFunctions(
                                 UnorderedElementsAre("foo"))))));
}

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

    void target() {
      int value = true ? foo() : Fatal().bar();
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
                        "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(IsStringMapEntry(
                        "p", HoldsFunctionCallLattice(HasCalledFunctions(
                                 UnorderedElementsAre("foo"))))));
}

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

    void target() {
      int value = false ? Fatal().bar() : foo();
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
                        "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(IsStringMapEntry(
                        "p", HoldsFunctionCallLattice(HasCalledFunctions(
                                 UnorderedElementsAre("baz", "foo"))))));
  // FIXME: Called functions at point `p` should contain only "foo".
}

// Models an analysis that uses flow conditions.
class SpecialBoolAnalysis final
    : public DataflowAnalysis<SpecialBoolAnalysis, NoopLattice> {
public:
  explicit SpecialBoolAnalysis(ASTContext &Context, Environment &Env)
      : DataflowAnalysis<SpecialBoolAnalysis, NoopLattice>(Context) {
    Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
        [](QualType Ty) -> llvm::StringMap<QualType> {
          RecordDecl *RD = Ty->getAsRecordDecl();
          if (RD == nullptr || RD->getIdentifier() == nullptr ||
              RD->getName() != "SpecialBool")
            return {};
          return {{"is_set", RD->getASTContext().BoolTy}};
        });
  }

  static NoopLattice initialElement() { return {}; }

  void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
    auto CS = Elt.getAs<CFGStmt>();
    if (!CS)
      return;
    const auto *S = CS->getStmt();
    auto SpecialBoolRecordDecl = recordDecl(hasName("SpecialBool"));
    auto HasSpecialBoolType = hasType(SpecialBoolRecordDecl);

    if (const auto *E = selectFirst<CXXConstructExpr>(
            "call", match(cxxConstructExpr(HasSpecialBoolType).bind("call"), *S,
                          getASTContext()))) {
      Env.setValue(Env.getResultObjectLocation(*E).getSyntheticField("is_set"),
                   Env.getBoolLiteralValue(false));
    } else if (const auto *E = selectFirst<CXXMemberCallExpr>(
                   "call", match(cxxMemberCallExpr(callee(cxxMethodDecl(ofClass(
                                                       SpecialBoolRecordDecl))))
                                     .bind("call"),
                                 *S, getASTContext()))) {
      if (RecordStorageLocation *ObjectLoc = getImplicitObjectLocation(*E, Env))
        Env.setValue(ObjectLoc->getSyntheticField("is_set"),
                     Env.getBoolLiteralValue(true));
    }
  }
};

class JoinFlowConditionsTest : public Test {
protected:
  template <typename Matcher>
  void runDataflow(llvm::StringRef Code, Matcher Match) {
    ASSERT_THAT_ERROR(
        test::checkDataflow<SpecialBoolAnalysis>(
            AnalysisInputs<SpecialBoolAnalysis>(
                Code, ast_matchers::hasName("target"),
                [](ASTContext &Context, Environment &Env) {
                  return SpecialBoolAnalysis(Context, Env);
                })
                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
            /*VerifyResults=*/[&Match](const llvm::StringMap<
                                           DataflowAnalysisState<NoopLattice>>
                                           &Results,
                                       const AnalysisOutputs
                                           &AO) { Match(Results, AO.ASTCtx); }),
        llvm::Succeeded());
  }
};

TEST_F(JoinFlowConditionsTest, JoinDistinctButProvablyEquivalentValues) {
  std::string Code = R"(
    struct SpecialBool {
      SpecialBool() = default;
      void set();
    };

    void target(bool Cond) {
      SpecialBool Foo;
      /*[[p1]]*/
      if (Cond) {
        Foo.set();
        /*[[p2]]*/
      } else {
        Foo.set();
        /*[[p3]]*/
      }
      (void)0;
      /*[[p4]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        ASSERT_THAT(Results.keys(),
                    UnorderedElementsAre("p1", "p2", "p3", "p4"));
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
        const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
        const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");

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

        auto GetFoo = [FooDecl](const Environment &Env) -> const Formula & {
          auto *Loc =
              cast<RecordStorageLocation>(Env.getStorageLocation(*FooDecl));
          return cast<BoolValue>(Env.getValue(Loc->getSyntheticField("is_set")))
              ->formula();
        };

        EXPECT_FALSE(Env1.proves(GetFoo(Env1)));
        EXPECT_TRUE(Env2.proves(GetFoo(Env2)));
        EXPECT_TRUE(Env3.proves(GetFoo(Env3)));
        EXPECT_TRUE(Env4.proves(GetFoo(Env4)));
      });
}

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

  static NoopLattice initialElement() { return {}; }

  void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
    auto CS = Elt.getAs<CFGStmt>();
    if (!CS)
      return;
    const Stmt *S = CS->getStmt();
    const Expr *E = dyn_cast<Expr>(S);
    if (!E)
      return;

    if (!E->getType()->isPointerType())
      return;

    // Make sure we have a `PointerValue` for `E`.
    auto *PtrVal = cast_or_null<PointerValue>(Env.getValue(*E));
    if (PtrVal == nullptr) {
      PtrVal = cast<PointerValue>(Env.createValue(E->getType()));
      Env.setValue(*E, *PtrVal);
    }

    if (auto *Cast = dyn_cast<ImplicitCastExpr>(E);
        Cast && Cast->getCastKind() == CK_NullToPointer)
      PtrVal->setProperty("is_null", Env.getBoolLiteralValue(true));
    else if (auto *Op = dyn_cast<UnaryOperator>(E);
             Op && Op->getOpcode() == UO_AddrOf)
      PtrVal->setProperty("is_null", Env.getBoolLiteralValue(false));
  }

  ComparisonResult compare(QualType Type, const Value &Val1,
                           const Environment &Env1, const Value &Val2,
                           const Environment &Env2) override {
    // Nothing to say about a value that is not a pointer.
    if (!Type->isPointerType())
      return ComparisonResult::Unknown;

    auto *Prop1 = Val1.getProperty("is_null");
    auto *Prop2 = Val2.getProperty("is_null");
    assert(Prop1 != nullptr && Prop2 != nullptr);
    return areEquivalentValues(*Prop1, *Prop2) ? ComparisonResult::Same
                                               : ComparisonResult::Different;
  }

  void join(QualType Type, const Value &Val1, const Environment &Env1,
            const Value &Val2, const Environment &Env2, Value &JoinedVal,
            Environment &JoinedEnv) override {
    // Nothing to say about a value that is not a pointer...
    if (!Type->isPointerType())
      return;

    // ... or, a pointer without the `is_null` property.
    auto *IsNull1 = cast_or_null<BoolValue>(Val1.getProperty("is_null"));
    auto *IsNull2 = cast_or_null<BoolValue>(Val2.getProperty("is_null"));
    if (IsNull1 == nullptr || IsNull2 == nullptr)
      return;

    if (IsNull1 == IsNull2)
      JoinedVal.setProperty("is_null", *IsNull1);
    else
      JoinedVal.setProperty("is_null", JoinedEnv.makeTopBoolValue());
  }

  std::optional<WidenResult> widen(QualType Type, Value &Prev,
                                   const Environment &PrevEnv, Value &Current,
                                   Environment &CurrentEnv) override {
    switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) {
    case ComparisonResult::Same:
      return WidenResult{&Current, LatticeJoinEffect::Unchanged};
    case ComparisonResult::Different: {
      auto &CurPtr = cast<PointerValue>(Current);
      auto &WidenedPtr =
          CurrentEnv.create<PointerValue>(CurPtr.getPointeeLoc());
      WidenedPtr.setProperty("is_null", CurrentEnv.makeTopBoolValue());
      return WidenResult{&WidenedPtr, LatticeJoinEffect::Changed};
    }
    case ComparisonResult::Unknown:
      return std::nullopt;
    }
    llvm_unreachable("all cases in switch covered");
  }
};

class WideningTest : public Test {
protected:
  template <typename Matcher>
  void runDataflow(llvm::StringRef Code, Matcher Match) {
    ASSERT_THAT_ERROR(
        checkDataflow<NullPointerAnalysis>(
            AnalysisInputs<NullPointerAnalysis>(
                Code, ast_matchers::hasName("target"),
                [](ASTContext &Context, Environment &Env) {
                  return NullPointerAnalysis(Context);
                })
                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
            /*VerifyResults=*/[&Match](const llvm::StringMap<
                                           DataflowAnalysisState<NoopLattice>>
                                           &Results,
                                       const AnalysisOutputs
                                           &AO) { Match(Results, AO.ASTCtx); }),
        llvm::Succeeded());
  }
};

TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) {
  std::string Code = R"(
    void target(bool Cond) {
      int *Foo = nullptr;
      int i = 0;
      /*[[p1]]*/
      if (Cond) {
        Foo = &i;
        /*[[p2]]*/
      }
      (void)0;
      /*[[p3]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
        const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

        EXPECT_EQ(GetFooValue(Env1)->getProperty("is_null"),
                  &Env1.getBoolLiteralValue(true));
        EXPECT_EQ(GetFooValue(Env2)->getProperty("is_null"),
                  &Env2.getBoolLiteralValue(false));
        EXPECT_TRUE(
            isa<TopBoolValue>(GetFooValue(Env3)->getProperty("is_null")));
      });
}

TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) {
  std::string Code = R"(
    void target(bool Cond) {
      int *Foo = nullptr;
      int i1 = 0;
      int i2 = 0;
      /*[[p1]]*/
      if (Cond) {
        Foo = &i1;
        /*[[p2]]*/
      } else {
        Foo = &i2;
        /*[[p3]]*/
      }
      (void)0;
      /*[[p4]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
        const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
        const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

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

TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) {
  std::string Code = R"(
    void target(int Foo, bool Cond) {
      int *Bar = &Foo;
      while (Cond) {
        Bar = &Foo;
      }
      (void)0;
      // [[p]]
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
        const auto &FooLoc =
            getLocForDecl<ScalarStorageLocation>(ASTCtx, Env, "Foo");
        const auto &BarVal = getValueForDecl<PointerValue>(ASTCtx, Env, "Bar");
        EXPECT_EQ(&BarVal.getPointeeLoc(), &FooLoc);
      });
}

TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) {
  std::string Code = R"(
    void target(bool Cond) {
      int *Foo;
      int i1 = 0;
      int i2 = 0;
      Foo = &i1;
      while (Cond) {
        Foo = &i2;
      }
      (void)0;
      /*[[p]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
        const auto &FooVal = getValueForDecl<Value>(ASTCtx, Env, "Foo");
        EXPECT_EQ(FooVal.getProperty("is_null"),
                  &Env.getBoolLiteralValue(false));
      });
}

TEST_F(WideningTest, DistinctValuesWithDifferentPropertiesWidenedToTop) {
  std::string Code = R"(
    void target(bool Cond) {
      int *Foo;
      int i = 0;
      Foo = nullptr;
      while (Cond) {
        Foo = &i;
      }
      (void)0;
      /*[[p]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
        const auto &FooVal = getValueForDecl<Value>(ASTCtx, Env, "Foo");
        ASSERT_THAT(FooVal.getProperty("is_null"), NotNull());
        EXPECT_TRUE(areEquivalentValues(*FooVal.getProperty("is_null"),
                                        Env.makeTopBoolValue()));
      });
}

class FlowConditionTest : public Test {
protected:
  template <typename Matcher>
  void runDataflow(llvm::StringRef Code, Matcher Match) {
    ASSERT_THAT_ERROR(
        checkDataflow<NoopAnalysis>(
            AnalysisInputs<NoopAnalysis>(
                Code, ast_matchers::hasName("target"),
                [](ASTContext &Context, Environment &Env) {
                  return NoopAnalysis(Context);
                })
                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
            /*VerifyResults=*/[&Match](const llvm::StringMap<
                                           DataflowAnalysisState<NoopLattice>>
                                           &Results,
                                       const AnalysisOutputs
                                           &AO) { Match(Results, AO.ASTCtx); }),
        llvm::Succeeded());
  }
};

TEST_F(FlowConditionTest, IfStmtSingleVar) {
  std::string Code = R"(
    void target(bool Foo) {
      if (Foo) {
        (void)0;
        /*[[p1]]*/
      } else {
        (void)1;
        /*[[p2]]*/
      }
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
        ASSERT_THAT(FooDecl, NotNull());

        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));

        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
        EXPECT_TRUE(Env1.proves(FooVal1));

        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
        auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
        EXPECT_FALSE(Env2.proves(FooVal2));
      });
}

TEST_F(FlowConditionTest, IfStmtSingleNegatedVar) {
  std::string Code = R"(
    void target(bool Foo) {
      if (!Foo) {
        (void)0;
        /*[[p1]]*/
      } else {
        (void)1;
        /*[[p2]]*/
      }
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
        ASSERT_THAT(FooDecl, NotNull());

        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));

        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
        EXPECT_FALSE(Env1.proves(FooVal1));

        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
        auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
        EXPECT_TRUE(Env2.proves(FooVal2));
      });
}

TEST_F(FlowConditionTest, WhileStmt) {
  std::string Code = R"(
    void target(bool Foo) {
      while (Foo) {
        (void)0;
        /*[[p]]*/
      }
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
        ASSERT_THAT(FooDecl, NotNull());

        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");

        auto &FooVal = cast<BoolValue>(Env.getValue(*FooDecl))->formula();
        EXPECT_TRUE(Env.proves(FooVal));
      });
}

TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
  std::string Code = R"(
    void target(bool Foo) {
      // This test checks whether the analysis preserves the connection between
      // the value of `Foo` and the assignment expression, despite widening.
      // The equality operator generates a fresh boolean variable on each
      // interpretation, which forces use of widening.
      while ((Foo = (3 == 4))) {
        (void)0;
        /*[[p]]*/
      }
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
        auto &FooVal = getValueForDecl<BoolValue>(ASTCtx, Env, "Foo").formula();
        EXPECT_TRUE(Env.proves(FooVal));
      });
}

TEST_F(FlowConditionTest, Conjunction) {
  std::string Code = R"(
    void target(bool Foo, bool Bar) {
      if (Foo && Bar) {
        (void)0;
        /*[[p1]]*/
      } else {
        (void)1;
        /*[[p2]]*/
      }
    }
  )";
  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
                           &Results,
                       ASTContext &ASTCtx) {
    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
    ASSERT_THAT(FooDecl, NotNull());

    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
    ASSERT_THAT(BarDecl, NotNull());

    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));

    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
    auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
    auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
    EXPECT_TRUE(Env1.proves(FooVal1));
    EXPECT_TRUE(Env1.proves(BarVal1));

    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
    auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
    auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
    EXPECT_FALSE(Env2.proves(FooVal2));
    EXPECT_FALSE(Env2.proves(BarVal2));
  });
}

TEST_F(FlowConditionTest, Disjunction) {
  std::string Code = R"(
    void target(bool Foo, bool Bar) {
      if (Foo || Bar) {
        (void)0;
        /*[[p1]]*/
      } else {
        (void)1;
        /*[[p2]]*/
      }
    }
  )";
  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
                           &Results,
                       ASTContext &ASTCtx) {
    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
    ASSERT_THAT(FooDecl, NotNull());

    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
    ASSERT_THAT(BarDecl, NotNull());

    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));

    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
    auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
    auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
    EXPECT_FALSE(Env1.proves(FooVal1));
    EXPECT_FALSE(Env1.proves(BarVal1));

    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
    auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
    auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
    EXPECT_FALSE(Env2.proves(FooVal2));
    EXPECT_FALSE(Env2.proves(BarVal2));
  });
}

TEST_F(FlowConditionTest, NegatedConjunction) {
  std::string Code = R"(
    void target(bool Foo, bool Bar) {
      if (!(Foo && Bar)) {
        (void)0;
        /*[[p1]]*/
      } else {
        (void)1;
        /*[[p2]]*/
      }
    }
  )";
  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
                           &Results,
                       ASTContext &ASTCtx) {
    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
    ASSERT_THAT(FooDecl, NotNull());

    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
    ASSERT_THAT(BarDecl, NotNull());

    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));

    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
    auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
    auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
    EXPECT_FALSE(Env1.proves(FooVal1));
    EXPECT_FALSE(Env1.proves(BarVal1));

    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
    auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
    auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
    EXPECT_TRUE(Env2.proves(FooVal2));
    EXPECT_TRUE(Env2.proves(BarVal2));
  });
}

TEST_F(FlowConditionTest, DeMorgan) {
  std::string Code = R"(
    void target(bool Foo, bool Bar) {
      if (!(!Foo || !Bar)) {
        (void)0;
        /*[[p1]]*/
      } else {
        (void)1;
        /*[[p2]]*/
      }
    }
  )";
  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
                           &Results,
                       ASTContext &ASTCtx) {
    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
    ASSERT_THAT(FooDecl, NotNull());

    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
    ASSERT_THAT(BarDecl, NotNull());

    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));

    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
    auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
    auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
    EXPECT_TRUE(Env1.proves(FooVal1));
    EXPECT_TRUE(Env1.proves(BarVal1));

    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
    auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
    auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
    EXPECT_FALSE(Env2.proves(FooVal2));
    EXPECT_FALSE(Env2.proves(BarVal2));
  });
}

TEST_F(FlowConditionTest, Join) {
  std::string Code = R"(
    void target(bool Foo, bool Bar) {
      if (Bar) {
        if (!Foo)
          return;
      } else {
        if (!Foo)
          return;
      }
      (void)0;
      /*[[p]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));

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

        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
        auto &FooVal = cast<BoolValue>(Env.getValue(*FooDecl))->formula();
        EXPECT_TRUE(Env.proves(FooVal));
      });
}

// Verifies that flow conditions are properly constructed even when the
// condition is not meaningfully interpreted.
//
// Note: currently, arbitrary function calls are uninterpreted, so the test
// exercises this case. If and when we change that, this test will not add to
// coverage (although it may still test a valuable case).
TEST_F(FlowConditionTest, OpaqueFlowConditionJoinsToOpaqueBool) {
  std::string Code = R"(
    bool foo();

    void target() {
      bool Bar = true;
      if (foo())
        Bar = false;
      (void)0;
      /*[[p]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");

        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
        ASSERT_THAT(BarDecl, NotNull());

        auto &BarVal = cast<BoolValue>(Env.getValue(*BarDecl))->formula();

        EXPECT_FALSE(Env.proves(BarVal));
      });
}

// Verifies that flow conditions are properly constructed even when the
// condition is not meaningfully interpreted.
//
// Note: currently, fields with recursive type calls are uninterpreted (beneath
// the first instance), so the test exercises this case. If and when we change
// that, this test will not add to coverage (although it may still test a
// valuable case).
TEST_F(FlowConditionTest, OpaqueFieldFlowConditionJoinsToOpaqueBool) {
  std::string Code = R"(
    struct Rec {
      Rec* Next;
    };

    struct Foo {
      Rec* X;
    };

    void target(Foo F) {
      bool Bar = true;
      if (F.X->Next)
        Bar = false;
      (void)0;
      /*[[p]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");

        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
        ASSERT_THAT(BarDecl, NotNull());

        auto &BarVal = cast<BoolValue>(Env.getValue(*BarDecl))->formula();

        EXPECT_FALSE(Env.proves(BarVal));
      });
}

// Verifies that flow conditions are properly constructed even when the
// condition is not meaningfully interpreted. Adds to above by nesting the
// interestnig case inside a normal branch. This protects against degenerate
// solutions which only test for empty flow conditions, for example.
TEST_F(FlowConditionTest, OpaqueFlowConditionInsideBranchJoinsToOpaqueBool) {
  std::string Code = R"(
    bool foo();

    void target(bool Cond) {
      bool Bar = true;
      if (Cond) {
        if (foo())
          Bar = false;
        (void)0;
        /*[[p]]*/
      }
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");

        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
        ASSERT_THAT(BarDecl, NotNull());

        auto &BarVal = cast<BoolValue>(Env.getValue(*BarDecl))->formula();

        EXPECT_FALSE(Env.proves(BarVal));
      });
}

TEST_F(FlowConditionTest, PointerToBoolImplicitCast) {
  std::string Code = R"(
    void target(int *Ptr) {
      bool Foo = false;
      if (Ptr) {
        Foo = true;
        /*[[p1]]*/
      }

      (void)0;
      /*[[p2]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         ASTContext &ASTCtx) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));

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

        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
        EXPECT_TRUE(Env1.proves(FooVal1));

        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
        auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
        EXPECT_FALSE(Env2.proves(FooVal2));
      });
}

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

  static NoopLattice initialElement() { return {}; }

  void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
    auto CS = Elt.getAs<CFGStmt>();
    if (!CS)
      return;
    const Stmt *S = CS->getStmt();
    SmallVector<BoundNodes, 1> Matches =
        match(callExpr(callee(functionDecl(hasName("makeTop")))).bind("top"),
              *S, getASTContext());
    if (const auto *E = selectFirst<CallExpr>("top", Matches)) {
      Env.setValue(*E, Env.makeTopBoolValue());
    }
  }

  ComparisonResult compare(QualType Type, const Value &Val1,
                           const Environment &Env1, const Value &Val2,
                           const Environment &Env2) override {
    // Changes to a sound approximation, which allows us to test whether we can
    // (soundly) converge for some loops.
    return ComparisonResult::Unknown;
  }
};

class TopTest : public Test {
protected:
  template <typename Matcher>
  void runDataflow(llvm::StringRef Code, Matcher VerifyResults) {
    ASSERT_THAT_ERROR(
        checkDataflow<TopAnalysis>(
            AnalysisInputs<TopAnalysis>(
                Code, ast_matchers::hasName("target"),
                [](ASTContext &Context, Environment &Env) {
                  return TopAnalysis(Context);
                })
                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
            VerifyResults),
        llvm::Succeeded());
  }
};

// Tests that when Top is unused it remains Top.
TEST_F(TopTest, UnusedTopInitializer) {
  std::string Code = R"(
    bool makeTop();

    void target() {
      bool Foo = makeTop();
      /*[[p1]]*/
      (void)0;
      /*[[p2]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         const AnalysisOutputs &AO) {
        ASSERT_THAT(Results.keys(),
                    UnorderedElementsAre("p1", "p2"));
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

        Value *FooVal1 = GetFooValue(Env1);
        ASSERT_THAT(FooVal1, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
            << debugString(FooVal1->getKind());

        Value *FooVal2 = GetFooValue(Env2);
        ASSERT_THAT(FooVal2, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
            << debugString(FooVal2->getKind());

        EXPECT_EQ(FooVal1, FooVal2);
      });
}

// Tests that when Top is unused it remains Top. Like above, but uses the
// assignment form rather than initialization, which uses Top as an lvalue that
// is *not* in an rvalue position.
TEST_F(TopTest, UnusedTopAssignment) {
  std::string Code = R"(
    bool makeTop();

    void target() {
      bool Foo;
      Foo = makeTop();
      /*[[p1]]*/
      (void)0;
      /*[[p2]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         const AnalysisOutputs &AO) {
        ASSERT_THAT(Results.keys(),
                    UnorderedElementsAre("p1", "p2"));
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

        Value *FooVal1 = GetFooValue(Env1);
        ASSERT_THAT(FooVal1, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
            << debugString(FooVal1->getKind());

        Value *FooVal2 = GetFooValue(Env2);
        ASSERT_THAT(FooVal2, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
            << debugString(FooVal2->getKind());

        EXPECT_EQ(FooVal1, FooVal2);
      });
}

TEST_F(TopTest, UnusedTopJoinsToTop) {
  std::string Code = R"(
    bool makeTop();

    void target(bool Cond, bool F) {
      bool Foo = makeTop();
      // Force a new CFG block.
      if (F) return;
      (void)0;
      /*[[p1]]*/

      bool Zab1;
      bool Zab2;
      if (Cond) {
        Zab1 = true;
      } else {
        Zab2 = true;
      }
      (void)0;
      /*[[p2]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         const AnalysisOutputs &AO) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

        Value *FooVal1 = GetFooValue(Env1);
        ASSERT_THAT(FooVal1, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
            << debugString(FooVal1->getKind());

        Value *FooVal2 = GetFooValue(Env2);
        ASSERT_THAT(FooVal2, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
            << debugString(FooVal2->getKind());
      });
}

TEST_F(TopTest, TopUsedBeforeBranchJoinsToSameAtomicBool) {
  std::string Code = R"(
    bool makeTop();

    void target(bool Cond, bool F) {
      bool Foo = makeTop();
      /*[[p0]]*/

      // Use `Top`.
      bool Bar = Foo;
      // Force a new CFG block.
      if (F) return;
      (void)0;
      /*[[p1]]*/

      bool Zab1;
      bool Zab2;
      if (Cond) {
        Zab1 = true;
      } else {
        Zab2 = true;
      }
      (void)0;
      /*[[p2]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         const AnalysisOutputs &AO) {
        ASSERT_THAT(Results.keys(),
                    UnorderedElementsAre("p0", "p1", "p2"));
        const Environment &Env0 = getEnvironmentAtAnnotation(Results, "p0");
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

        Value *FooVal0 = GetFooValue(Env0);
        ASSERT_THAT(FooVal0, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal0))
            << debugString(FooVal0->getKind());

        Value *FooVal1 = GetFooValue(Env1);
        ASSERT_THAT(FooVal1, NotNull());
        EXPECT_TRUE(isa<AtomicBoolValue>(FooVal1))
            << debugString(FooVal1->getKind());

        Value *FooVal2 = GetFooValue(Env2);
        ASSERT_THAT(FooVal2, NotNull());
        EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
            << debugString(FooVal2->getKind());

        EXPECT_EQ(FooVal2, FooVal1);
      });
}

TEST_F(TopTest, TopUsedInBothBranchesJoinsToAtomic) {
  std::string Code = R"(
    bool makeTop();

    void target(bool Cond, bool F) {
      bool Foo = makeTop();
      // Force a new CFG block.
      if (F) return;
      (void)0;
      /*[[p1]]*/

      bool Zab1;
      bool Zab2;
      if (Cond) {
        Zab1 = Foo;
      } else {
        Zab2 = Foo;
      }
      (void)0;
      /*[[p2]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         const AnalysisOutputs &AO) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

        Value *FooVal1 = GetFooValue(Env1);
        ASSERT_THAT(FooVal1, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
            << debugString(FooVal1->getKind());

        Value *FooVal2 = GetFooValue(Env2);
        ASSERT_THAT(FooVal2, NotNull());
        EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
            << debugString(FooVal2->getKind());
      });
}

TEST_F(TopTest, TopUsedInBothBranchesWithoutPrecisionLoss) {
  std::string Code = R"(
    bool makeTop();

    void target(bool Cond, bool F) {
      bool Foo = makeTop();
      // Force a new CFG block.
      if (F) return;
      (void)0;

      bool Bar;
      if (Cond) {
        Bar = Foo;
      } else {
        Bar = Foo;
      }
      (void)0;
      /*[[p]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         const AnalysisOutputs &AO) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");

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

        const ValueDecl *BarDecl = findValueDecl(AO.ASTCtx, "Bar");
        ASSERT_THAT(BarDecl, NotNull());

        auto *FooVal = dyn_cast_or_null<BoolValue>(Env.getValue(*FooDecl));
        ASSERT_THAT(FooVal, NotNull());

        auto *BarVal = dyn_cast_or_null<BoolValue>(Env.getValue(*BarDecl));
        ASSERT_THAT(BarVal, NotNull());

        EXPECT_TRUE(Env.proves(
            Env.arena().makeEquals(FooVal->formula(), BarVal->formula())));
      });
}

TEST_F(TopTest, TopUnusedBeforeLoopHeadJoinsToTop) {
  std::string Code = R"(
    bool makeTop();

    void target(bool Cond, bool F) {
      bool Foo = makeTop();
      // Force a new CFG block.
      if (F) return;
      (void)0;
      /*[[p1]]*/

      while (Cond) {
        // Use `Foo`.
        bool Zab = Foo;
        Zab = false;
        Foo = makeTop();
      }
      (void)0;
      /*[[p2]]*/
    }
  )";
  runDataflow(
      Code,
      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
         const AnalysisOutputs &AO) {
        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");

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

        auto GetFooValue = [FooDecl](const Environment &Env) {
          return Env.getValue(*FooDecl);
        };

        Value *FooVal1 = GetFooValue(Env1);
        ASSERT_THAT(FooVal1, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
            << debugString(FooVal1->getKind());

        Value *FooVal2 = GetFooValue(Env2);
        ASSERT_THAT(FooVal2, NotNull());
        EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
            << debugString(FooVal2->getKind());

      });
}

TEST_F(TopTest, ForRangeStmtConverges) {
  std::string Code = R"(
    void target(bool Foo) {
      int Ints[10];
      bool B = false;
      for (int I : Ints)
        B = true;
    }
  )";
  runDataflow(Code,
              [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &,
                 const AnalysisOutputs &) {
                // No additional expectations. We're only checking that the
                // analysis converged.
              });
}
} // namespace