clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

   1 //===- unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp ===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "TestingSupport.h"
  10 #include "clang/AST/Decl.h"
  11 #include "clang/AST/ExprCXX.h"
  12 #include "clang/AST/Type.h"
  13 #include "clang/ASTMatchers/ASTMatchFinder.h"
  14 #include "clang/ASTMatchers/ASTMatchers.h"
  15 #include "clang/Analysis/CFG.h"
  16 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
  17 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
  18 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
  19 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
  20 #include "clang/Analysis/FlowSensitive/DebugSupport.h"
  21 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
  22 #include "clang/Analysis/FlowSensitive/Value.h"
  23 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
  24 #include "clang/Tooling/Tooling.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/SmallSet.h"
  27 #include "llvm/ADT/StringMap.h"
  28 #include "llvm/ADT/StringRef.h"
  29 #include "llvm/Support/Error.h"
  30 #include "llvm/Testing/ADT/StringMapEntry.h"
  31 #include "llvm/Testing/Support/Error.h"
  32 #include "gmock/gmock.h"
  33 #include "gtest/gtest.h"
  34 #include <cassert>
  35 #include <memory>
  36 #include <optional>
  37 #include <ostream>
  38 #include <string>
  39 #include <utility>
  40 #include <vector>
  41
  42 namespace {
  43
  44 using namespace clang;
  45 using namespace dataflow;
  46 using namespace test;
  47 using namespace ast_matchers;
  48 using llvm::IsStringMapEntry;
  49 using ::testing::DescribeMatcher;
  50 using ::testing::IsEmpty;
  51 using ::testing::NotNull;
  52 using ::testing::Test;
  53 using ::testing::UnorderedElementsAre;
  54
  55 template <typename AnalysisT>
  56 llvm::Expected<std::vector<
  57     std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
  58 runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
  59   std::unique_ptr<ASTUnit> AST =
  60       tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
  61
  62   auto *Func = selectFirst<FunctionDecl>(
  63       "func", match(functionDecl(ast_matchers::hasName("target")).bind("func"),
  64                     AST->getASTContext()));
  65   assert(Func != nullptr);
  66
  67   auto CFCtx =
  68       llvm::cantFail(ControlFlowContext::build(*Func));
  69
  70   AnalysisT Analysis = MakeAnalysis(AST->getASTContext());
  71   DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>());
  72   Environment Env(DACtx);
  73
  74   return runDataflowAnalysis(CFCtx, Analysis, Env);
  75 }
  76
  77 TEST(DataflowAnalysisTest, NoopAnalysis) {
  78   auto BlockStates = llvm::cantFail(
  79       runAnalysis<NoopAnalysis>("void target() {}", [](ASTContext &C) {
  80         return NoopAnalysis(C,
  81                             // Don't use builtin transfer function.
  82                             DataflowAnalysisOptions{std::nullopt});
  83       }));
  84   EXPECT_EQ(BlockStates.size(), 2u);
  85   EXPECT_TRUE(BlockStates[0].has_value());
  86   EXPECT_TRUE(BlockStates[1].has_value());
  87 }
  88
  89 // Basic test that `diagnoseFunction` calls the Diagnoser function for the
  90 // number of elements expected.
  91 TEST(DataflowAnalysisTest, DiagnoseFunctionDiagnoserCalledOnEachElement) {
  92   std::string Code = R"(void target() { int x = 0; ++x; })";
  93   std::unique_ptr<ASTUnit> AST =
  94       tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
  95
  96   auto *Func =
  97       cast<FunctionDecl>(findValueDecl(AST->getASTContext(), "target"));
  98   auto Diagnoser = [](const CFGElement &Elt, ASTContext &,
  99                       const TransferStateForDiagnostics<NoopLattice> &) {
 100     llvm::SmallVector<std::string> Diagnostics(1);
 101     llvm::raw_string_ostream OS(Diagnostics.front());
 102     Elt.dumpToStream(OS);
 103     return Diagnostics;
 104   };
 105   auto Result = diagnoseFunction<NoopAnalysis, std::string>(
 106       *Func, AST->getASTContext(), Diagnoser);
 107   // `diagnoseFunction` provides no guarantees about the order in which elements
 108   // are visited, so we use `UnorderedElementsAre`.
 109   EXPECT_THAT_EXPECTED(Result, llvm::HasValue(UnorderedElementsAre(
 110                                    "0\n", "int x = 0;\n", "x\n", "++x\n",
 111                                    " (Lifetime ends)\n")));
 112 }
 113
 114 struct NonConvergingLattice {
 115   int State;
 116
 117   bool operator==(const NonConvergingLattice &Other) const {
 118     return State == Other.State;
 119   }
 120
 121   LatticeJoinEffect join(const NonConvergingLattice &Other) {
 122     if (Other.State == 0)
 123       return LatticeJoinEffect::Unchanged;
 124     State += Other.State;
 125     return LatticeJoinEffect::Changed;
 126   }
 127 };
 128
 129 class NonConvergingAnalysis
 130     : public DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice> {
 131 public:
 132   explicit NonConvergingAnalysis(ASTContext &Context)
 133       : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(
 134             Context,
 135             // Don't apply builtin transfer function.
 136             DataflowAnalysisOptions{std::nullopt}) {}
 137
 138   static NonConvergingLattice initialElement() { return {0}; }
 139
 140   void transfer(const CFGElement &, NonConvergingLattice &E, Environment &) {
 141     ++E.State;
 142   }
 143 };
 144
 145 TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
 146   std::string Code = R"(
 147     void target() {
 148       while(true) {}
 149     }
 150   )";
 151   auto Res = runAnalysis<NonConvergingAnalysis>(
 152       Code, [](ASTContext &C) { return NonConvergingAnalysis(C); });
 153   EXPECT_EQ(llvm::toString(Res.takeError()),
 154             "maximum number of iterations reached");
 155 }
 156
 157 // Regression test for joins of bool-typed lvalue expressions. The first loop
 158 // results in two passes through the code that follows. Each pass results in a
 159 // different `StorageLocation` for the pointee of `v`. Then, the second loop
 160 // causes a join at the loop head where the two environments map expresssion
 161 // `*v` to different `StorageLocation`s.
 162 //
 163 // An earlier version crashed for this condition (for boolean-typed lvalues), so
 164 // this test only verifies that the analysis runs successfully, without
 165 // examining any details of the results.
 166 TEST(DataflowAnalysisTest, JoinBoolLValues) {
 167   std::string Code = R"(
 168     void target() {
 169       for (int x = 1; x; x = 0)
 170         (void)x;
 171       bool *v;
 172       if (*v)
 173         for (int x = 1; x; x = 0)
 174           (void)x;
 175     }
 176   )";
 177   ASSERT_THAT_ERROR(
 178       runAnalysis<NoopAnalysis>(Code,
 179                                 [](ASTContext &C) {
 180                                   auto EnableBuiltIns = DataflowAnalysisOptions{
 181                                       DataflowAnalysisContext::Options{}};
 182                                   return NoopAnalysis(C, EnableBuiltIns);
 183                                 })
 184           .takeError(),
 185       llvm::Succeeded());
 186 }
 187
 188 struct FunctionCallLattice {
 189   using FunctionSet = llvm::SmallSet<std::string, 8>;
 190   FunctionSet CalledFunctions;
 191
 192   bool operator==(const FunctionCallLattice &Other) const {
 193     return CalledFunctions == Other.CalledFunctions;
 194   }
 195
 196   LatticeJoinEffect join(const FunctionCallLattice &Other) {
 197     if (Other.CalledFunctions.empty())
 198       return LatticeJoinEffect::Unchanged;
 199     const size_t size_before = CalledFunctions.size();
 200     CalledFunctions.insert(Other.CalledFunctions.begin(),
 201                            Other.CalledFunctions.end());
 202     return CalledFunctions.size() == size_before ? LatticeJoinEffect::Unchanged
 203                                                  : LatticeJoinEffect::Changed;
 204   }
 205 };
 206
 207 std::ostream &operator<<(std::ostream &OS, const FunctionCallLattice &L) {
 208   std::string S;
 209   llvm::raw_string_ostream ROS(S);
 210   llvm::interleaveComma(L.CalledFunctions, ROS);
 211   return OS << "{" << S << "}";
 212 }
 213
 214 class FunctionCallAnalysis
 215     : public DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice> {
 216 public:
 217   explicit FunctionCallAnalysis(ASTContext &Context)
 218       : DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice>(Context) {}
 219
 220   static FunctionCallLattice initialElement() { return {}; }
 221
 222   void transfer(const CFGElement &Elt, FunctionCallLattice &E, Environment &) {
 223     auto CS = Elt.getAs<CFGStmt>();
 224     if (!CS)
 225       return;
 226     const auto *S = CS->getStmt();
 227     if (auto *C = dyn_cast<CallExpr>(S)) {
 228       if (auto *F = dyn_cast<FunctionDecl>(C->getCalleeDecl())) {
 229         E.CalledFunctions.insert(F->getNameInfo().getAsString());
 230       }
 231     }
 232   }
 233 };
 234
 235 class NoreturnDestructorTest : public Test {
 236 protected:
 237   template <typename Matcher>
 238   void runDataflow(llvm::StringRef Code, Matcher Expectations) {
 239     tooling::FileContentMappings FilesContents;
 240     FilesContents.push_back(std::make_pair<std::string, std::string>(
 241         "noreturn_destructor_test_defs.h", R"(
 242       int foo();
 243
 244       class Fatal {
 245        public:
 246         ~Fatal() __attribute__((noreturn));
 247         int bar();
 248         int baz();
 249       };
 250
 251       class NonFatal {
 252        public:
 253         ~NonFatal();
 254         int bar();
 255       };
 256     )"));
 257
 258     ASSERT_THAT_ERROR(
 259         test::checkDataflow<FunctionCallAnalysis>(
 260             AnalysisInputs<FunctionCallAnalysis>(
 261                 Code, ast_matchers::hasName("target"),
 262                 [](ASTContext &C, Environment &) {
 263                   return FunctionCallAnalysis(C);
 264                 })
 265                 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
 266                 .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
 267             /*VerifyResults=*/
 268             [&Expectations](
 269                 const llvm::StringMap<
 270                     DataflowAnalysisState<FunctionCallLattice>> &Results,
 271                 const AnalysisOutputs &) {
 272               EXPECT_THAT(Results, Expectations);
 273             }),
 274         llvm::Succeeded());
 275   }
 276 };
 277
 278 MATCHER_P(HoldsFunctionCallLattice, m,
 279           ((negation ? "doesn't hold" : "holds") +
 280            llvm::StringRef(" a lattice element that ") +
 281            DescribeMatcher<FunctionCallLattice>(m))
 282               .str()) {
 283   return ExplainMatchResult(m, arg.Lattice, result_listener);
 284 }
 285
 286 MATCHER_P(HasCalledFunctions, m,
 287           ((negation ? "doesn't hold" : "holds") +
 288            llvm::StringRef(" a set of called functions that ") +
 289            DescribeMatcher<FunctionCallLattice::FunctionSet>(m))
 290               .str()) {
 291   return ExplainMatchResult(m, arg.CalledFunctions, result_listener);
 292 }
 293
 294 TEST_F(NoreturnDestructorTest, ConditionalOperatorBothBranchesReturn) {
 295   std::string Code = R"(
 296     #include "noreturn_destructor_test_defs.h"
 297
 298     void target(bool b) {
 299       int value = b ? foo() : NonFatal().bar();
 300       (void)0;
 301       // [[p]]
 302     }
 303   )";
 304   runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
 305                         "p", HoldsFunctionCallLattice(HasCalledFunctions(
 306                                  UnorderedElementsAre("foo", "bar"))))));
 307 }
 308
 309 TEST_F(NoreturnDestructorTest, ConditionalOperatorLeftBranchReturns) {
 310   std::string Code = R"(
 311     #include "noreturn_destructor_test_defs.h"
 312
 313     void target(bool b) {
 314       int value = b ? foo() : Fatal().bar();
 315       (void)0;
 316       // [[p]]
 317     }
 318   )";
 319   runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
 320                         "p", HoldsFunctionCallLattice(HasCalledFunctions(
 321                                  UnorderedElementsAre("foo"))))));
 322 }
 323
 324 TEST_F(NoreturnDestructorTest,
 325        ConditionalOperatorConstantCondition_LeftBranchReturns) {
 326   std::string Code = R"(
 327     #include "noreturn_destructor_test_defs.h"
 328
 329     void target() {
 330       int value = true ? foo() : Fatal().bar();
 331       (void)0;
 332       // [[p]]
 333     }
 334   )";
 335   runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
 336                         "p", HoldsFunctionCallLattice(HasCalledFunctions(
 337                                  UnorderedElementsAre("foo"))))));
 338 }
 339
 340 TEST_F(NoreturnDestructorTest, ConditionalOperatorRightBranchReturns) {
 341   std::string Code = R"(
 342     #include "noreturn_destructor_test_defs.h"
 343
 344     void target(bool b) {
 345       int value = b ? Fatal().bar() : foo();
 346       (void)0;
 347       // [[p]]
 348     }
 349   )";
 350   runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
 351                         "p", HoldsFunctionCallLattice(HasCalledFunctions(
 352                                  UnorderedElementsAre("foo"))))));
 353 }
 354
 355 TEST_F(NoreturnDestructorTest,
 356        ConditionalOperatorConstantCondition_RightBranchReturns) {
 357   std::string Code = R"(
 358     #include "noreturn_destructor_test_defs.h"
 359
 360     void target() {
 361       int value = false ? Fatal().bar() : foo();
 362       (void)0;
 363       // [[p]]
 364     }
 365   )";
 366   runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
 367                         "p", HoldsFunctionCallLattice(HasCalledFunctions(
 368                                  UnorderedElementsAre("foo"))))));
 369 }
 370
 371 TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchesDoNotReturn) {
 372   std::string Code = R"(
 373     #include "noreturn_destructor_test_defs.h"
 374
 375     void target(bool b1, bool b2) {
 376       int value = b1 ? foo() : (b2 ? Fatal().bar() : Fatal().baz());
 377       (void)0;
 378       // [[p]]
 379     }
 380   )";
 381   runDataflow(Code, IsEmpty());
 382   // FIXME: Called functions at point `p` should contain "foo".
 383 }
 384
 385 TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchReturns) {
 386   std::string Code = R"(
 387     #include "noreturn_destructor_test_defs.h"
 388
 389     void target(bool b1, bool b2) {
 390       int value = b1 ? Fatal().bar() : (b2 ? Fatal().baz() : foo());
 391       (void)0;
 392       // [[p]]
 393     }
 394   )";
 395   runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
 396                         "p", HoldsFunctionCallLattice(HasCalledFunctions(
 397                                  UnorderedElementsAre("baz", "foo"))))));
 398   // FIXME: Called functions at point `p` should contain only "foo".
 399 }
 400
 401 // Models an analysis that uses flow conditions.
 402 class SpecialBoolAnalysis final
 403     : public DataflowAnalysis<SpecialBoolAnalysis, NoopLattice> {
 404 public:
 405   explicit SpecialBoolAnalysis(ASTContext &Context)
 406       : DataflowAnalysis<SpecialBoolAnalysis, NoopLattice>(Context) {}
 407
 408   static NoopLattice initialElement() { return {}; }
 409
 410   void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
 411     auto CS = Elt.getAs<CFGStmt>();
 412     if (!CS)
 413       return;
 414     const auto *S = CS->getStmt();
 415     auto SpecialBoolRecordDecl = recordDecl(hasName("SpecialBool"));
 416     auto HasSpecialBoolType = hasType(SpecialBoolRecordDecl);
 417
 418     if (const auto *E = selectFirst<CXXConstructExpr>(
 419             "call", match(cxxConstructExpr(HasSpecialBoolType).bind("call"), *S,
 420                           getASTContext()))) {
 421       cast<RecordValue>(Env.getValue(*E))
 422           ->setProperty("is_set", Env.getBoolLiteralValue(false));
 423     } else if (const auto *E = selectFirst<CXXMemberCallExpr>(
 424                    "call", match(cxxMemberCallExpr(callee(cxxMethodDecl(ofClass(
 425                                                        SpecialBoolRecordDecl))))
 426                                      .bind("call"),
 427                                  *S, getASTContext()))) {
 428       auto &ObjectLoc =
 429           *cast<RecordStorageLocation>(getImplicitObjectLocation(*E, Env));
 430
 431       refreshRecordValue(ObjectLoc, Env)
 432           .setProperty("is_set", Env.getBoolLiteralValue(true));
 433     }
 434   }
 435
 436   ComparisonResult compare(QualType Type, const Value &Val1,
 437                            const Environment &Env1, const Value &Val2,
 438                            const Environment &Env2) override {
 439     const auto *Decl = Type->getAsCXXRecordDecl();
 440     if (Decl == nullptr || Decl->getIdentifier() == nullptr ||
 441         Decl->getName() != "SpecialBool")
 442       return ComparisonResult::Unknown;
 443
 444     auto *IsSet1 = cast_or_null<BoolValue>(Val1.getProperty("is_set"));
 445     auto *IsSet2 = cast_or_null<BoolValue>(Val2.getProperty("is_set"));
 446     if (IsSet1 == nullptr)
 447       return IsSet2 == nullptr ? ComparisonResult::Same
 448                                : ComparisonResult::Different;
 449
 450     if (IsSet2 == nullptr)
 451       return ComparisonResult::Different;
 452
 453     return Env1.proves(IsSet1->formula()) == Env2.proves(IsSet2->formula())
 454                ? ComparisonResult::Same
 455                : ComparisonResult::Different;
 456   }
 457
 458   // Always returns `true` to accept the `MergedVal`.
 459   bool merge(QualType Type, const Value &Val1, const Environment &Env1,
 460              const Value &Val2, const Environment &Env2, Value &MergedVal,
 461              Environment &MergedEnv) override {
 462     const auto *Decl = Type->getAsCXXRecordDecl();
 463     if (Decl == nullptr || Decl->getIdentifier() == nullptr ||
 464         Decl->getName() != "SpecialBool")
 465       return true;
 466
 467     auto *IsSet1 = cast_or_null<BoolValue>(Val1.getProperty("is_set"));
 468     if (IsSet1 == nullptr)
 469       return true;
 470
 471     auto *IsSet2 = cast_or_null<BoolValue>(Val2.getProperty("is_set"));
 472     if (IsSet2 == nullptr)
 473       return true;
 474
 475     auto &IsSet = MergedEnv.makeAtomicBoolValue();
 476     MergedVal.setProperty("is_set", IsSet);
 477     if (Env1.proves(IsSet1->formula()) && Env2.proves(IsSet2->formula()))
 478       MergedEnv.assume(IsSet.formula());
 479
 480     return true;
 481   }
 482 };
 483
 484 class JoinFlowConditionsTest : public Test {
 485 protected:
 486   template <typename Matcher>
 487   void runDataflow(llvm::StringRef Code, Matcher Match) {
 488     ASSERT_THAT_ERROR(
 489         test::checkDataflow<SpecialBoolAnalysis>(
 490             AnalysisInputs<SpecialBoolAnalysis>(
 491                 Code, ast_matchers::hasName("target"),
 492                 [](ASTContext &Context, Environment &Env) {
 493                   return SpecialBoolAnalysis(Context);
 494                 })
 495                 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
 496             /*VerifyResults=*/[&Match](const llvm::StringMap<
 497                                            DataflowAnalysisState<NoopLattice>>
 498                                            &Results,
 499                                        const AnalysisOutputs
 500                                            &AO) { Match(Results, AO.ASTCtx); }),
 501         llvm::Succeeded());
 502   }
 503 };
 504
 505 TEST_F(JoinFlowConditionsTest, JoinDistinctButProvablyEquivalentValues) {
 506   std::string Code = R"(
 507     struct SpecialBool {
 508       SpecialBool() = default;
 509       void set();
 510     };
 511
 512     void target(bool Cond) {
 513       SpecialBool Foo;
 514       /*[[p1]]*/
 515       if (Cond) {
 516         Foo.set();
 517         /*[[p2]]*/
 518       } else {
 519         Foo.set();
 520         /*[[p3]]*/
 521       }
 522       (void)0;
 523       /*[[p4]]*/
 524     }
 525   )";
 526   runDataflow(
 527       Code,
 528       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 529          ASTContext &ASTCtx) {
 530         ASSERT_THAT(Results.keys(),
 531                     UnorderedElementsAre("p1", "p2", "p3", "p4"));
 532         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
 533         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 534         const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
 535         const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");
 536
 537         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 538         ASSERT_THAT(FooDecl, NotNull());
 539
 540         auto GetFoo = [FooDecl](const Environment &Env) -> const Formula & {
 541           return cast<BoolValue>(Env.getValue(*FooDecl)->getProperty("is_set"))
 542               ->formula();
 543         };
 544
 545         EXPECT_FALSE(Env1.proves(GetFoo(Env1)));
 546         EXPECT_TRUE(Env2.proves(GetFoo(Env2)));
 547         EXPECT_TRUE(Env3.proves(GetFoo(Env3)));
 548         EXPECT_TRUE(Env4.proves(GetFoo(Env4)));
 549       });
 550 }
 551
 552 class OptionalIntAnalysis final
 553     : public DataflowAnalysis<OptionalIntAnalysis, NoopLattice> {
 554 public:
 555   explicit OptionalIntAnalysis(ASTContext &Context)
 556       : DataflowAnalysis<OptionalIntAnalysis, NoopLattice>(Context) {}
 557
 558   static NoopLattice initialElement() { return {}; }
 559
 560   void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
 561     auto CS = Elt.getAs<CFGStmt>();
 562     if (!CS)
 563       return;
 564     const Stmt *S = CS->getStmt();
 565     auto OptionalIntRecordDecl = recordDecl(hasName("OptionalInt"));
 566     auto HasOptionalIntType = hasType(OptionalIntRecordDecl);
 567
 568     SmallVector<BoundNodes, 1> Matches = match(
 569         stmt(anyOf(cxxConstructExpr(HasOptionalIntType).bind("construct"),
 570                    cxxOperatorCallExpr(
 571                        callee(cxxMethodDecl(ofClass(OptionalIntRecordDecl))))
 572                        .bind("operator"))),
 573         *S, getASTContext());
 574     if (const auto *E = selectFirst<CXXConstructExpr>(
 575             "construct", Matches)) {
 576       cast<RecordValue>(Env.getValue(*E))
 577           ->setProperty("has_value", Env.getBoolLiteralValue(false));
 578     } else if (const auto *E =
 579                    selectFirst<CXXOperatorCallExpr>("operator", Matches)) {
 580       assert(E->getNumArgs() > 0);
 581       auto *Object = E->getArg(0);
 582       assert(Object != nullptr);
 583
 584       refreshRecordValue(*Object, Env)
 585           .setProperty("has_value", Env.getBoolLiteralValue(true));
 586     }
 587   }
 588
 589   ComparisonResult compare(QualType Type, const Value &Val1,
 590                            const Environment &Env1, const Value &Val2,
 591                            const Environment &Env2) override {
 592     // Nothing to say about a value that does not model an `OptionalInt`.
 593     if (!Type->isRecordType() ||
 594         Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
 595       return ComparisonResult::Unknown;
 596
 597     auto *Prop1 = Val1.getProperty("has_value");
 598     auto *Prop2 = Val2.getProperty("has_value");
 599     assert(Prop1 != nullptr && Prop2 != nullptr);
 600     return areEquivalentValues(*Prop1, *Prop2) ? ComparisonResult::Same
 601                                                : ComparisonResult::Different;
 602   }
 603
 604   bool merge(QualType Type, const Value &Val1, const Environment &Env1,
 605              const Value &Val2, const Environment &Env2, Value &MergedVal,
 606              Environment &MergedEnv) override {
 607     // Nothing to say about a value that does not model an `OptionalInt`.
 608     if (!Type->isRecordType() ||
 609         Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
 610       return false;
 611
 612     auto *HasValue1 = cast_or_null<BoolValue>(Val1.getProperty("has_value"));
 613     if (HasValue1 == nullptr)
 614       return false;
 615
 616     auto *HasValue2 = cast_or_null<BoolValue>(Val2.getProperty("has_value"));
 617     if (HasValue2 == nullptr)
 618       return false;
 619
 620     if (HasValue1 == HasValue2)
 621       MergedVal.setProperty("has_value", *HasValue1);
 622     else
 623       MergedVal.setProperty("has_value", MergedEnv.makeTopBoolValue());
 624     return true;
 625   }
 626 };
 627
 628 class WideningTest : public Test {
 629 protected:
 630   template <typename Matcher>
 631   void runDataflow(llvm::StringRef Code, Matcher Match) {
 632     tooling::FileContentMappings FilesContents;
 633     FilesContents.push_back(
 634         std::make_pair<std::string, std::string>("widening_test_defs.h", R"(
 635       struct OptionalInt {
 636         OptionalInt() = default;
 637         OptionalInt& operator=(int);
 638       };
 639     )"));
 640     ASSERT_THAT_ERROR(
 641         checkDataflow<OptionalIntAnalysis>(
 642             AnalysisInputs<OptionalIntAnalysis>(
 643                 Code, ast_matchers::hasName("target"),
 644                 [](ASTContext &Context, Environment &Env) {
 645                   return OptionalIntAnalysis(Context);
 646                 })
 647                 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
 648                 .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
 649             /*VerifyResults=*/[&Match](const llvm::StringMap<
 650                                            DataflowAnalysisState<NoopLattice>>
 651                                            &Results,
 652                                        const AnalysisOutputs
 653                                            &AO) { Match(Results, AO.ASTCtx); }),
 654         llvm::Succeeded());
 655   }
 656 };
 657
 658 TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) {
 659   std::string Code = R"(
 660     #include "widening_test_defs.h"
 661
 662     void target(bool Cond) {
 663       OptionalInt Foo;
 664       /*[[p1]]*/
 665       if (Cond) {
 666         Foo = 1;
 667         /*[[p2]]*/
 668       }
 669       (void)0;
 670       /*[[p3]]*/
 671     }
 672   )";
 673   runDataflow(
 674       Code,
 675       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 676          ASTContext &ASTCtx) {
 677         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2", "p3"));
 678         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
 679         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 680         const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
 681
 682         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 683         ASSERT_THAT(FooDecl, NotNull());
 684
 685         auto GetFooValue = [FooDecl](const Environment &Env) {
 686           return Env.getValue(*FooDecl);
 687         };
 688
 689         EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
 690                   &Env1.getBoolLiteralValue(false));
 691         EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
 692                   &Env2.getBoolLiteralValue(true));
 693         EXPECT_TRUE(
 694             isa<TopBoolValue>(GetFooValue(Env3)->getProperty("has_value")));
 695       });
 696 }
 697
 698 TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) {
 699   std::string Code = R"(
 700     #include "widening_test_defs.h"
 701
 702     void target(bool Cond) {
 703       OptionalInt Foo;
 704       /*[[p1]]*/
 705       if (Cond) {
 706         Foo = 1;
 707         /*[[p2]]*/
 708       } else {
 709         Foo = 2;
 710         /*[[p3]]*/
 711       }
 712       (void)0;
 713       /*[[p4]]*/
 714     }
 715   )";
 716   runDataflow(
 717       Code,
 718       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 719          ASTContext &ASTCtx) {
 720         ASSERT_THAT(Results.keys(),
 721                     UnorderedElementsAre("p1", "p2", "p3", "p4"));
 722         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
 723         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 724         const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
 725         const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");
 726
 727         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 728         ASSERT_THAT(FooDecl, NotNull());
 729
 730         auto GetFooValue = [FooDecl](const Environment &Env) {
 731           return Env.getValue(*FooDecl);
 732         };
 733
 734         EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
 735                   &Env1.getBoolLiteralValue(false));
 736         EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
 737                   &Env2.getBoolLiteralValue(true));
 738         EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
 739                   &Env3.getBoolLiteralValue(true));
 740         EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
 741                   &Env4.getBoolLiteralValue(true));
 742       });
 743 }
 744
 745 TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) {
 746   std::string Code = R"(
 747     void target(int Foo, bool Cond) {
 748       int *Bar = &Foo;
 749       while (Cond) {
 750         Bar = &Foo;
 751       }
 752       (void)0;
 753       // [[p]]
 754     }
 755   )";
 756   runDataflow(
 757       Code,
 758       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 759          ASTContext &ASTCtx) {
 760         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
 761         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 762
 763         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 764         ASSERT_THAT(FooDecl, NotNull());
 765
 766         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
 767         ASSERT_THAT(BarDecl, NotNull());
 768
 769         const auto *FooLoc =
 770             cast<ScalarStorageLocation>(Env.getStorageLocation(*FooDecl));
 771         const auto *BarVal = cast<PointerValue>(Env.getValue(*BarDecl));
 772         EXPECT_EQ(&BarVal->getPointeeLoc(), FooLoc);
 773       });
 774 }
 775
 776 TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) {
 777   std::string Code = R"(
 778     #include "widening_test_defs.h"
 779
 780     void target(bool Cond) {
 781       OptionalInt Foo;
 782       Foo = 1;
 783       while (Cond) {
 784         Foo = 2;
 785       }
 786       (void)0;
 787       /*[[p]]*/
 788     }
 789   )";
 790   runDataflow(
 791       Code,
 792       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 793          ASTContext &ASTCtx) {
 794         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
 795         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 796
 797         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 798         ASSERT_THAT(FooDecl, NotNull());
 799
 800         const auto *FooVal = Env.getValue(*FooDecl);
 801         EXPECT_EQ(FooVal->getProperty("has_value"),
 802                   &Env.getBoolLiteralValue(true));
 803       });
 804 }
 805
 806 class FlowConditionTest : public Test {
 807 protected:
 808   template <typename Matcher>
 809   void runDataflow(llvm::StringRef Code, Matcher Match) {
 810     ASSERT_THAT_ERROR(
 811         checkDataflow<NoopAnalysis>(
 812             AnalysisInputs<NoopAnalysis>(
 813                 Code, ast_matchers::hasName("target"),
 814                 [](ASTContext &Context, Environment &Env) {
 815                   return NoopAnalysis(Context);
 816                 })
 817                 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
 818             /*VerifyResults=*/[&Match](const llvm::StringMap<
 819                                            DataflowAnalysisState<NoopLattice>>
 820                                            &Results,
 821                                        const AnalysisOutputs
 822                                            &AO) { Match(Results, AO.ASTCtx); }),
 823         llvm::Succeeded());
 824   }
 825 };
 826
 827 TEST_F(FlowConditionTest, IfStmtSingleVar) {
 828   std::string Code = R"(
 829     void target(bool Foo) {
 830       if (Foo) {
 831         (void)0;
 832         /*[[p1]]*/
 833       } else {
 834         (void)1;
 835         /*[[p2]]*/
 836       }
 837     }
 838   )";
 839   runDataflow(
 840       Code,
 841       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 842          ASTContext &ASTCtx) {
 843         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 844         ASSERT_THAT(FooDecl, NotNull());
 845
 846         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
 847
 848         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
 849         auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
 850         EXPECT_TRUE(Env1.proves(FooVal1));
 851
 852         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 853         auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
 854         EXPECT_FALSE(Env2.proves(FooVal2));
 855       });
 856 }
 857
 858 TEST_F(FlowConditionTest, IfStmtSingleNegatedVar) {
 859   std::string Code = R"(
 860     void target(bool Foo) {
 861       if (!Foo) {
 862         (void)0;
 863         /*[[p1]]*/
 864       } else {
 865         (void)1;
 866         /*[[p2]]*/
 867       }
 868     }
 869   )";
 870   runDataflow(
 871       Code,
 872       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 873          ASTContext &ASTCtx) {
 874         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 875         ASSERT_THAT(FooDecl, NotNull());
 876
 877         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
 878
 879         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
 880         auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
 881         EXPECT_FALSE(Env1.proves(FooVal1));
 882
 883         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 884         auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
 885         EXPECT_TRUE(Env2.proves(FooVal2));
 886       });
 887 }
 888
 889 TEST_F(FlowConditionTest, WhileStmt) {
 890   std::string Code = R"(
 891     void target(bool Foo) {
 892       while (Foo) {
 893         (void)0;
 894         /*[[p]]*/
 895       }
 896     }
 897   )";
 898   runDataflow(
 899       Code,
 900       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 901          ASTContext &ASTCtx) {
 902         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 903         ASSERT_THAT(FooDecl, NotNull());
 904
 905         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
 906         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 907
 908         auto &FooVal = cast<BoolValue>(Env.getValue(*FooDecl))->formula();
 909         EXPECT_TRUE(Env.proves(FooVal));
 910       });
 911 }
 912
 913 TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
 914   std::string Code = R"(
 915     void target(bool Foo) {
 916       // This test checks whether the analysis preserves the connection between
 917       // the value of `Foo` and the assignment expression, despite widening.
 918       // The equality operator generates a fresh boolean variable on each
 919       // interpretation, which forces use of widening.
 920       while ((Foo = (3 == 4))) {
 921         (void)0;
 922         /*[[p]]*/
 923       }
 924     }
 925   )";
 926   runDataflow(
 927       Code,
 928       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 929          ASTContext &ASTCtx) {
 930         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 931         auto &FooVal = getValueForDecl<BoolValue>(ASTCtx, Env, "Foo").formula();
 932         EXPECT_TRUE(Env.proves(FooVal));
 933       });
 934 }
 935
 936 TEST_F(FlowConditionTest, Conjunction) {
 937   std::string Code = R"(
 938     void target(bool Foo, bool Bar) {
 939       if (Foo && Bar) {
 940         (void)0;
 941         /*[[p1]]*/
 942       } else {
 943         (void)1;
 944         /*[[p2]]*/
 945       }
 946     }
 947   )";
 948   runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
 949                            &Results,
 950                        ASTContext &ASTCtx) {
 951     const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 952     ASSERT_THAT(FooDecl, NotNull());
 953
 954     const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
 955     ASSERT_THAT(BarDecl, NotNull());
 956
 957     ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
 958
 959     const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
 960     auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
 961     auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
 962     EXPECT_TRUE(Env1.proves(FooVal1));
 963     EXPECT_TRUE(Env1.proves(BarVal1));
 964
 965     const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
 966     auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
 967     auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
 968     EXPECT_FALSE(Env2.proves(FooVal2));
 969     EXPECT_FALSE(Env2.proves(BarVal2));
 970   });
 971 }
 972
 973 TEST_F(FlowConditionTest, Disjunction) {
 974   std::string Code = R"(
 975     void target(bool Foo, bool Bar) {
 976       if (Foo || Bar) {
 977         (void)0;
 978         /*[[p1]]*/
 979       } else {
 980         (void)1;
 981         /*[[p2]]*/
 982       }
 983     }
 984   )";
 985   runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
 986                            &Results,
 987                        ASTContext &ASTCtx) {
 988     const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
 989     ASSERT_THAT(FooDecl, NotNull());
 990
 991     const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
 992     ASSERT_THAT(BarDecl, NotNull());
 993
 994     ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
 995
 996     const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
 997     auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
 998     auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
 999     EXPECT_FALSE(Env1.proves(FooVal1));
1000     EXPECT_FALSE(Env1.proves(BarVal1));
1001
1002     const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1003     auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
1004     auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
1005     EXPECT_FALSE(Env2.proves(FooVal2));
1006     EXPECT_FALSE(Env2.proves(BarVal2));
1007   });
1008 }
1009
1010 TEST_F(FlowConditionTest, NegatedConjunction) {
1011   std::string Code = R"(
1012     void target(bool Foo, bool Bar) {
1013       if (!(Foo && Bar)) {
1014         (void)0;
1015         /*[[p1]]*/
1016       } else {
1017         (void)1;
1018         /*[[p2]]*/
1019       }
1020     }
1021   )";
1022   runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
1023                            &Results,
1024                        ASTContext &ASTCtx) {
1025     const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
1026     ASSERT_THAT(FooDecl, NotNull());
1027
1028     const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1029     ASSERT_THAT(BarDecl, NotNull());
1030
1031     ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1032
1033     const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1034     auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
1035     auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
1036     EXPECT_FALSE(Env1.proves(FooVal1));
1037     EXPECT_FALSE(Env1.proves(BarVal1));
1038
1039     const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1040     auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
1041     auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
1042     EXPECT_TRUE(Env2.proves(FooVal2));
1043     EXPECT_TRUE(Env2.proves(BarVal2));
1044   });
1045 }
1046
1047 TEST_F(FlowConditionTest, DeMorgan) {
1048   std::string Code = R"(
1049     void target(bool Foo, bool Bar) {
1050       if (!(!Foo || !Bar)) {
1051         (void)0;
1052         /*[[p1]]*/
1053       } else {
1054         (void)1;
1055         /*[[p2]]*/
1056       }
1057     }
1058   )";
1059   runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
1060                            &Results,
1061                        ASTContext &ASTCtx) {
1062     const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
1063     ASSERT_THAT(FooDecl, NotNull());
1064
1065     const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1066     ASSERT_THAT(BarDecl, NotNull());
1067
1068     ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1069
1070     const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1071     auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
1072     auto &BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl))->formula();
1073     EXPECT_TRUE(Env1.proves(FooVal1));
1074     EXPECT_TRUE(Env1.proves(BarVal1));
1075
1076     const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1077     auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
1078     auto &BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl))->formula();
1079     EXPECT_FALSE(Env2.proves(FooVal2));
1080     EXPECT_FALSE(Env2.proves(BarVal2));
1081   });
1082 }
1083
1084 TEST_F(FlowConditionTest, Join) {
1085   std::string Code = R"(
1086     void target(bool Foo, bool Bar) {
1087       if (Bar) {
1088         if (!Foo)
1089           return;
1090       } else {
1091         if (!Foo)
1092           return;
1093       }
1094       (void)0;
1095       /*[[p]]*/
1096     }
1097   )";
1098   runDataflow(
1099       Code,
1100       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1101          ASTContext &ASTCtx) {
1102         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1103
1104         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
1105         ASSERT_THAT(FooDecl, NotNull());
1106
1107         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1108         auto &FooVal = cast<BoolValue>(Env.getValue(*FooDecl))->formula();
1109         EXPECT_TRUE(Env.proves(FooVal));
1110       });
1111 }
1112
1113 // Verifies that flow conditions are properly constructed even when the
1114 // condition is not meaningfully interpreted.
1115 //
1116 // Note: currently, arbitrary function calls are uninterpreted, so the test
1117 // exercises this case. If and when we change that, this test will not add to
1118 // coverage (although it may still test a valuable case).
1119 TEST_F(FlowConditionTest, OpaqueFlowConditionMergesToOpaqueBool) {
1120   std::string Code = R"(
1121     bool foo();
1122
1123     void target() {
1124       bool Bar = true;
1125       if (foo())
1126         Bar = false;
1127       (void)0;
1128       /*[[p]]*/
1129     }
1130   )";
1131   runDataflow(
1132       Code,
1133       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1134          ASTContext &ASTCtx) {
1135         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1136         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1137
1138         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1139         ASSERT_THAT(BarDecl, NotNull());
1140
1141         auto &BarVal = cast<BoolValue>(Env.getValue(*BarDecl))->formula();
1142
1143         EXPECT_FALSE(Env.proves(BarVal));
1144       });
1145 }
1146
1147 // Verifies that flow conditions are properly constructed even when the
1148 // condition is not meaningfully interpreted.
1149 //
1150 // Note: currently, fields with recursive type calls are uninterpreted (beneath
1151 // the first instance), so the test exercises this case. If and when we change
1152 // that, this test will not add to coverage (although it may still test a
1153 // valuable case).
1154 TEST_F(FlowConditionTest, OpaqueFieldFlowConditionMergesToOpaqueBool) {
1155   std::string Code = R"(
1156     struct Rec {
1157       Rec* Next;
1158     };
1159
1160     struct Foo {
1161       Rec* X;
1162     };
1163
1164     void target(Foo F) {
1165       bool Bar = true;
1166       if (F.X->Next)
1167         Bar = false;
1168       (void)0;
1169       /*[[p]]*/
1170     }
1171   )";
1172   runDataflow(
1173       Code,
1174       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1175          ASTContext &ASTCtx) {
1176         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1177         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1178
1179         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1180         ASSERT_THAT(BarDecl, NotNull());
1181
1182         auto &BarVal = cast<BoolValue>(Env.getValue(*BarDecl))->formula();
1183
1184         EXPECT_FALSE(Env.proves(BarVal));
1185       });
1186 }
1187
1188 // Verifies that flow conditions are properly constructed even when the
1189 // condition is not meaningfully interpreted. Adds to above by nesting the
1190 // interestnig case inside a normal branch. This protects against degenerate
1191 // solutions which only test for empty flow conditions, for example.
1192 TEST_F(FlowConditionTest, OpaqueFlowConditionInsideBranchMergesToOpaqueBool) {
1193   std::string Code = R"(
1194     bool foo();
1195
1196     void target(bool Cond) {
1197       bool Bar = true;
1198       if (Cond) {
1199         if (foo())
1200           Bar = false;
1201         (void)0;
1202         /*[[p]]*/
1203       }
1204     }
1205   )";
1206   runDataflow(
1207       Code,
1208       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1209          ASTContext &ASTCtx) {
1210         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1211         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1212
1213         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1214         ASSERT_THAT(BarDecl, NotNull());
1215
1216         auto &BarVal = cast<BoolValue>(Env.getValue(*BarDecl))->formula();
1217
1218         EXPECT_FALSE(Env.proves(BarVal));
1219       });
1220 }
1221
1222 TEST_F(FlowConditionTest, PointerToBoolImplicitCast) {
1223   std::string Code = R"(
1224     void target(int *Ptr) {
1225       bool Foo = false;
1226       if (Ptr) {
1227         Foo = true;
1228         /*[[p1]]*/
1229       }
1230
1231       (void)0;
1232       /*[[p2]]*/
1233     }
1234   )";
1235   runDataflow(
1236       Code,
1237       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1238          ASTContext &ASTCtx) {
1239         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1240
1241         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
1242         ASSERT_THAT(FooDecl, NotNull());
1243
1244         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1245         auto &FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl))->formula();
1246         EXPECT_TRUE(Env1.proves(FooVal1));
1247
1248         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1249         auto &FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl))->formula();
1250         EXPECT_FALSE(Env2.proves(FooVal2));
1251       });
1252 }
1253
1254 class TopAnalysis final : public DataflowAnalysis<TopAnalysis, NoopLattice> {
1255 public:
1256   explicit TopAnalysis(ASTContext &Context)
1257       : DataflowAnalysis<TopAnalysis, NoopLattice>(Context) {}
1258
1259   static NoopLattice initialElement() { return {}; }
1260
1261   void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
1262     auto CS = Elt.getAs<CFGStmt>();
1263     if (!CS)
1264       return;
1265     const Stmt *S = CS->getStmt();
1266     SmallVector<BoundNodes, 1> Matches =
1267         match(callExpr(callee(functionDecl(hasName("makeTop")))).bind("top"),
1268               *S, getASTContext());
1269     if (const auto *E = selectFirst<CallExpr>("top", Matches)) {
1270       Env.setValue(*E, Env.makeTopBoolValue());
1271     }
1272   }
1273
1274   ComparisonResult compare(QualType Type, const Value &Val1,
1275                            const Environment &Env1, const Value &Val2,
1276                            const Environment &Env2) override {
1277     // Changes to a sound approximation, which allows us to test whether we can
1278     // (soundly) converge for some loops.
1279     return ComparisonResult::Unknown;
1280   }
1281 };
1282
1283 class TopTest : public Test {
1284 protected:
1285   template <typename Matcher>
1286   void runDataflow(llvm::StringRef Code, Matcher VerifyResults) {
1287     ASSERT_THAT_ERROR(
1288         checkDataflow<TopAnalysis>(
1289             AnalysisInputs<TopAnalysis>(
1290                 Code, ast_matchers::hasName("target"),
1291                 [](ASTContext &Context, Environment &Env) {
1292                   return TopAnalysis(Context);
1293                 })
1294                 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
1295             VerifyResults),
1296         llvm::Succeeded());
1297   }
1298 };
1299
1300 // Tests that when Top is unused it remains Top.
1301 TEST_F(TopTest, UnusedTopInitializer) {
1302   std::string Code = R"(
1303     bool makeTop();
1304
1305     void target() {
1306       bool Foo = makeTop();
1307       /*[[p1]]*/
1308       (void)0;
1309       /*[[p2]]*/
1310     }
1311   )";
1312   runDataflow(
1313       Code,
1314       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1315          const AnalysisOutputs &AO) {
1316         ASSERT_THAT(Results.keys(),
1317                     UnorderedElementsAre("p1", "p2"));
1318         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1319         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1320
1321         const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1322         ASSERT_THAT(FooDecl, NotNull());
1323
1324         auto GetFooValue = [FooDecl](const Environment &Env) {
1325           return Env.getValue(*FooDecl);
1326         };
1327
1328         Value *FooVal1 = GetFooValue(Env1);
1329         ASSERT_THAT(FooVal1, NotNull());
1330         EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1331             << debugString(FooVal1->getKind());
1332
1333         Value *FooVal2 = GetFooValue(Env2);
1334         ASSERT_THAT(FooVal2, NotNull());
1335         EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1336             << debugString(FooVal2->getKind());
1337
1338         EXPECT_EQ(FooVal1, FooVal2);
1339       });
1340 }
1341
1342 // Tests that when Top is unused it remains Top. Like above, but uses the
1343 // assignment form rather than initialization, which uses Top as an lvalue that
1344 // is *not* in an rvalue position.
1345 TEST_F(TopTest, UnusedTopAssignment) {
1346   std::string Code = R"(
1347     bool makeTop();
1348
1349     void target() {
1350       bool Foo;
1351       Foo = makeTop();
1352       /*[[p1]]*/
1353       (void)0;
1354       /*[[p2]]*/
1355     }
1356   )";
1357   runDataflow(
1358       Code,
1359       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1360          const AnalysisOutputs &AO) {
1361         ASSERT_THAT(Results.keys(),
1362                     UnorderedElementsAre("p1", "p2"));
1363         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1364         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1365
1366         const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1367         ASSERT_THAT(FooDecl, NotNull());
1368
1369         auto GetFooValue = [FooDecl](const Environment &Env) {
1370           return Env.getValue(*FooDecl);
1371         };
1372
1373         Value *FooVal1 = GetFooValue(Env1);
1374         ASSERT_THAT(FooVal1, NotNull());
1375         EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1376             << debugString(FooVal1->getKind());
1377
1378         Value *FooVal2 = GetFooValue(Env2);
1379         ASSERT_THAT(FooVal2, NotNull());
1380         EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1381             << debugString(FooVal2->getKind());
1382
1383         EXPECT_EQ(FooVal1, FooVal2);
1384       });
1385 }
1386
1387 TEST_F(TopTest, UnusedTopJoinsToTop) {
1388   std::string Code = R"(
1389     bool makeTop();
1390
1391     void target(bool Cond, bool F) {
1392       bool Foo = makeTop();
1393       // Force a new CFG block.
1394       if (F) return;
1395       (void)0;
1396       /*[[p1]]*/
1397
1398       bool Zab1;
1399       bool Zab2;
1400       if (Cond) {
1401         Zab1 = true;
1402       } else {
1403         Zab2 = true;
1404       }
1405       (void)0;
1406       /*[[p2]]*/
1407     }
1408   )";
1409   runDataflow(
1410       Code,
1411       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1412          const AnalysisOutputs &AO) {
1413         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1414         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1415         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1416
1417         const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1418         ASSERT_THAT(FooDecl, NotNull());
1419
1420         auto GetFooValue = [FooDecl](const Environment &Env) {
1421           return Env.getValue(*FooDecl);
1422         };
1423
1424         Value *FooVal1 = GetFooValue(Env1);
1425         ASSERT_THAT(FooVal1, NotNull());
1426         EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1427             << debugString(FooVal1->getKind());
1428
1429         Value *FooVal2 = GetFooValue(Env2);
1430         ASSERT_THAT(FooVal2, NotNull());
1431         EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1432             << debugString(FooVal2->getKind());
1433       });
1434 }
1435
1436 TEST_F(TopTest, TopUsedBeforeBranchJoinsToSameAtomicBool) {
1437   std::string Code = R"(
1438     bool makeTop();
1439
1440     void target(bool Cond, bool F) {
1441       bool Foo = makeTop();
1442       /*[[p0]]*/
1443
1444       // Use `Top`.
1445       bool Bar = Foo;
1446       // Force a new CFG block.
1447       if (F) return;
1448       (void)0;
1449       /*[[p1]]*/
1450
1451       bool Zab1;
1452       bool Zab2;
1453       if (Cond) {
1454         Zab1 = true;
1455       } else {
1456         Zab2 = true;
1457       }
1458       (void)0;
1459       /*[[p2]]*/
1460     }
1461   )";
1462   runDataflow(
1463       Code,
1464       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1465          const AnalysisOutputs &AO) {
1466         ASSERT_THAT(Results.keys(),
1467                     UnorderedElementsAre("p0", "p1", "p2"));
1468         const Environment &Env0 = getEnvironmentAtAnnotation(Results, "p0");
1469         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1470         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1471
1472         const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1473         ASSERT_THAT(FooDecl, NotNull());
1474
1475         auto GetFooValue = [FooDecl](const Environment &Env) {
1476           return Env.getValue(*FooDecl);
1477         };
1478
1479         Value *FooVal0 = GetFooValue(Env0);
1480         ASSERT_THAT(FooVal0, NotNull());
1481         EXPECT_TRUE(isa<TopBoolValue>(FooVal0))
1482             << debugString(FooVal0->getKind());
1483
1484         Value *FooVal1 = GetFooValue(Env1);
1485         ASSERT_THAT(FooVal1, NotNull());
1486         EXPECT_TRUE(isa<AtomicBoolValue>(FooVal1))
1487             << debugString(FooVal1->getKind());
1488
1489         Value *FooVal2 = GetFooValue(Env2);
1490         ASSERT_THAT(FooVal2, NotNull());
1491         EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
1492             << debugString(FooVal2->getKind());
1493
1494         EXPECT_EQ(FooVal2, FooVal1);
1495       });
1496 }
1497
1498 TEST_F(TopTest, TopUsedInBothBranchesJoinsToAtomic) {
1499   std::string Code = R"(
1500     bool makeTop();
1501
1502     void target(bool Cond, bool F) {
1503       bool Foo = makeTop();
1504       // Force a new CFG block.
1505       if (F) return;
1506       (void)0;
1507       /*[[p1]]*/
1508
1509       bool Zab1;
1510       bool Zab2;
1511       if (Cond) {
1512         Zab1 = Foo;
1513       } else {
1514         Zab2 = Foo;
1515       }
1516       (void)0;
1517       /*[[p2]]*/
1518     }
1519   )";
1520   runDataflow(
1521       Code,
1522       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1523          const AnalysisOutputs &AO) {
1524         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1525         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1526         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1527
1528         const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1529         ASSERT_THAT(FooDecl, NotNull());
1530
1531         auto GetFooValue = [FooDecl](const Environment &Env) {
1532           return Env.getValue(*FooDecl);
1533         };
1534
1535         Value *FooVal1 = GetFooValue(Env1);
1536         ASSERT_THAT(FooVal1, NotNull());
1537         EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1538             << debugString(FooVal1->getKind());
1539
1540         Value *FooVal2 = GetFooValue(Env2);
1541         ASSERT_THAT(FooVal2, NotNull());
1542         EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
1543             << debugString(FooVal2->getKind());
1544       });
1545 }
1546
1547 TEST_F(TopTest, TopUsedInBothBranchesWithoutPrecisionLoss) {
1548   std::string Code = R"(
1549     bool makeTop();
1550
1551     void target(bool Cond, bool F) {
1552       bool Foo = makeTop();
1553       // Force a new CFG block.
1554       if (F) return;
1555       (void)0;
1556
1557       bool Bar;
1558       if (Cond) {
1559         Bar = Foo;
1560       } else {
1561         Bar = Foo;
1562       }
1563       (void)0;
1564       /*[[p]]*/
1565     }
1566   )";
1567   runDataflow(
1568       Code,
1569       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1570          const AnalysisOutputs &AO) {
1571         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1572         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1573
1574         const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1575         ASSERT_THAT(FooDecl, NotNull());
1576
1577         const ValueDecl *BarDecl = findValueDecl(AO.ASTCtx, "Bar");
1578         ASSERT_THAT(BarDecl, NotNull());
1579
1580         auto *FooVal = dyn_cast_or_null<BoolValue>(Env.getValue(*FooDecl));
1581         ASSERT_THAT(FooVal, NotNull());
1582
1583         auto *BarVal = dyn_cast_or_null<BoolValue>(Env.getValue(*BarDecl));
1584         ASSERT_THAT(BarVal, NotNull());
1585
1586         EXPECT_TRUE(Env.proves(
1587             Env.arena().makeEquals(FooVal->formula(), BarVal->formula())));
1588       });
1589 }
1590
1591 TEST_F(TopTest, TopUnusedBeforeLoopHeadJoinsToTop) {
1592   std::string Code = R"(
1593     bool makeTop();
1594
1595     void target(bool Cond, bool F) {
1596       bool Foo = makeTop();
1597       // Force a new CFG block.
1598       if (F) return;
1599       (void)0;
1600       /*[[p1]]*/
1601
1602       while (Cond) {
1603         // Use `Foo`.
1604         bool Zab = Foo;
1605         Zab = false;
1606         Foo = makeTop();
1607       }
1608       (void)0;
1609       /*[[p2]]*/
1610     }
1611   )";
1612   runDataflow(
1613       Code,
1614       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1615          const AnalysisOutputs &AO) {
1616         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1617         const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1618         const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1619
1620         const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1621         ASSERT_THAT(FooDecl, NotNull());
1622
1623         auto GetFooValue = [FooDecl](const Environment &Env) {
1624           return Env.getValue(*FooDecl);
1625         };
1626
1627         Value *FooVal1 = GetFooValue(Env1);
1628         ASSERT_THAT(FooVal1, NotNull());
1629         EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1630             << debugString(FooVal1->getKind());
1631
1632         Value *FooVal2 = GetFooValue(Env2);
1633         ASSERT_THAT(FooVal2, NotNull());
1634         EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1635             << debugString(FooVal2->getKind());
1636
1637       });
1638 }
1639
1640 TEST_F(TopTest, ForRangeStmtConverges) {
1641   std::string Code = R"(
1642     void target(bool Foo) {
1643       int Ints[10];
1644       bool B = false;
1645       for (int I : Ints)
1646         B = true;
1647     }
1648   )";
1649   runDataflow(Code,
1650               [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &,
1651                  const AnalysisOutputs &) {
1652                 // No additional expectations. We're only checking that the
1653                 // analysis converged.
1654               });
1655 }
1656 } // namespace