[analyzer][Dominators] Add unittests

[Szelethus]

Summary

Exactly what it says on the tin!

[kuhar]

clang/unittests/Analysis/CFGDominatorTree.cpp

95 ↗

(On Diff #201977)

Why not have a constructor that takes the cfg and constructs a domtree straight away? But this should probably go into a separate patch.

113 ↗

(On Diff #201977)

A tastcase with a virtual root postdominating other nodes would be welcome.

[kuhar]

clang/unittests/Analysis/CFGDominatorTree.cpp

37 ↗

(On Diff #201977)

You can use a raw string literal to make it more readable: https://en.cppreference.com/w/cpp/language/string_literal

[NoQ]

clang/unittests/Analysis/CFGDominatorTree.cpp

37 ↗

(On Diff #201977)

...or just omit \ns because the compiler doesn't really care.

[Szelethus]

Fixes according to reviewer comments, thanks! :)

[Szelethus]

clang/unittests/Analysis/CFGDominatorTree.cpp

95 ↗

(On Diff #201977)

Yea, it's been bothering me for a while, but apparently not enough to fix it (just yet!).

[xazax.hun]

Oh, I realized later that code I commented on were only moved from somewhere else. If you feel like tackling these comments feel free to do so in a separate patch so this one stays clean (no changes to moved code).

clang/unittests/Analysis/CFGBuilder.h

18 ↗

(On Diff #202004)

Is it actually sensible to write tests where the tool failed? I can imagine these status codes being helpful for debugging but they has little to do with the tests. I wonder if we actually need all these or a nullable pointer as a result is sufficient.

54 ↗

(On Diff #202004)

Do you expect the code to only contain one function? If so, you should enforce it.

65 ↗

(On Diff #202004)

Do you need the std::move here?

[Szelethus]

Ping.

[sanaanajjar231288]

In D62611#1521692, @Szelethus wrote:

Fixes according to reviewer comments, thanks! :)

[Szelethus]

Gentle ping :^)

[NoQ]

clang/unittests/Analysis/CFGBuilder.h

16 ↗

(On Diff #202004)

Given that now it's in a header, i guess we need to pick a less generic name. Eg., CFGBuildResult.

54 ↗

(On Diff #202004)

I guess it sucks that we can't re-use my findDeclByName() helper here.

clang/unittests/Analysis/CFGDominatorTree.cpp

22–28 ↗

(On Diff #202004)

Why isn't this a simple function template?

30–32 ↗

(On Diff #202004)

StmtType is unused. Did you mean FindStmt<StmtType>?

31 ↗

(On Diff #202004)

This looks like "hasNoStmtType" to me, did you mean !=?

[Szelethus]

clang/unittests/Analysis/CFGDominatorTree.cpp

22–32 ↗

(On Diff #202004)

Hmmm, this entire thing is pointless, really. It is used as a sanity check of some sort, whether for example the 4th block really is what I believe it would be. But this is anything but a reliable way to test it.

I think this causes far more confusion than value, I'll just remove it, the actual tests are thorough enough enough to break if the CFG changes.

[Szelethus]

Fixes according to reviewer comments!

[xazax.hun]

Looks good to me, some nits inline.

clang/unittests/Analysis/CFGBuildResult.h

1 ↗

(On Diff #207759)

Filename not updated?

clang/unittests/Analysis/CFGDominatorTree.cpp

1 ↗

(On Diff #207759)

Filename not updated?

13 ↗

(On Diff #207759)

Do you need the Tooling header here?

cfe/trunk/unittests/Analysis/CFGBuildResult.h

+//===- unittests/Analysis/CFGBuildResult.h - CFG tests --------------------===//
+//
+// 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 "clang/Analysis/CFG.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Tooling/Tooling.h"
+
+namespace clang {
+namespace analysis {
+
+class BuildResult {
+public:
+  enum Status {
+    ToolFailed,
+    ToolRan,
+    SawFunctionBody,
+    BuiltCFG,
+  };
+
+  BuildResult(Status S, std::unique_ptr<CFG> Cfg = nullptr)
+      : S(S), Cfg(std::move(Cfg)) {}
+
+  Status getStatus() const { return S; }
+  CFG *getCFG() const { return Cfg.get(); }
+
+private:
+  Status S;
+  std::unique_ptr<CFG> Cfg;
+};
+
+class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
+public:
+  BuildResult TheBuildResult = BuildResult::ToolRan;
+
+  void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
+    const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
+    Stmt *Body = Func->getBody();
+    if (!Body)
+      return;
+    TheBuildResult = BuildResult::SawFunctionBody;
+    CFG::BuildOptions Options;
+    Options.AddImplicitDtors = true;
+    if (std::unique_ptr<CFG> Cfg =
+            CFG::buildCFG(nullptr, Body, Result.Context, Options))
+      TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg)};
+  }
+};
+
+inline BuildResult BuildCFG(const char *Code) {
+  CFGCallback Callback;
+
+  ast_matchers::MatchFinder Finder;
+  Finder.addMatcher(ast_matchers::functionDecl().bind("func"), &Callback);
+  std::unique_ptr<tooling::FrontendActionFactory> Factory(
+      tooling::newFrontendActionFactory(&Finder));
+  std::vector<std::string> Args = {"-std=c++11",
+                                   "-fno-delayed-template-parsing"};
+  if (!tooling::runToolOnCodeWithArgs(Factory->create(), Code, Args))
+    return BuildResult::ToolFailed;
+  return std::move(Callback.TheBuildResult);
+}
+
+} // namespace analysis
+} // namespace clang

cfe/trunk/unittests/Analysis/CFGDominatorTree.cpp

+//===- unittests/Analysis/CFGDominatorTree.cpp - CFG tests ----------------===//
+//
+// 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 "CFGBuildResult.h"
+#include "clang/Analysis/Analyses/Dominators.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace analysis {
+namespace {
+
+TEST(CFGDominatorTree, DomTree) {
+  const char *Code = R"(enum Kind {
+                          A
+                        };
+
+                        void f() {
+                          switch(Kind{}) {
+                          case A:
+                            break;
+                          }
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  //  [B3 (ENTRY)]  -> [B1] -> [B2] -> [B0 (EXIT)]
+  //                  switch  case A
+
+  CFG *cfg = Result.getCFG();
+
+  // Sanity checks.
+  EXPECT_EQ(cfg->size(), 4u);
+
+  CFGBlock *ExitBlock = *cfg->begin();
+  EXPECT_EQ(ExitBlock, &cfg->getExit());
+
+  CFGBlock *SwitchBlock = *(cfg->begin() + 1);
+
+  CFGBlock *CaseABlock = *(cfg->begin() + 2);
+
+  CFGBlock *EntryBlock = *(cfg->begin() + 3);
+  EXPECT_EQ(EntryBlock, &cfg->getEntry());
+
+  // Test the dominator tree.
+  CFGDomTree Dom;
+  Dom.buildDominatorTree(cfg);
+
+  EXPECT_TRUE(Dom.dominates(ExitBlock, ExitBlock));
+  EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));
+  EXPECT_TRUE(Dom.dominates(CaseABlock, ExitBlock));
+  EXPECT_TRUE(Dom.dominates(SwitchBlock, ExitBlock));
+  EXPECT_TRUE(Dom.dominates(EntryBlock, ExitBlock));
+
+  EXPECT_TRUE(Dom.dominates(CaseABlock, CaseABlock));
+  EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));
+  EXPECT_TRUE(Dom.dominates(SwitchBlock, CaseABlock));
+  EXPECT_TRUE(Dom.dominates(EntryBlock, CaseABlock));
+
+  EXPECT_TRUE(Dom.dominates(SwitchBlock, SwitchBlock));
+  EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));
+  EXPECT_TRUE(Dom.dominates(EntryBlock, SwitchBlock));
+
+  EXPECT_TRUE(Dom.dominates(EntryBlock, EntryBlock));
+  EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));
+
+  // Test the post dominator tree.
+
+  CFGPostDomTree PostDom;
+  PostDom.buildDominatorTree(cfg);
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(CaseABlock, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(SwitchBlock, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(EntryBlock, EntryBlock));
+  EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, SwitchBlock));
+  EXPECT_TRUE(PostDom.dominates(CaseABlock, SwitchBlock));
+  EXPECT_TRUE(PostDom.dominates(SwitchBlock, SwitchBlock));
+  EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, CaseABlock));
+  EXPECT_TRUE(PostDom.dominates(CaseABlock, CaseABlock));
+  EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, ExitBlock));
+  EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));
+
+  // Tests for the post dominator tree's virtual root.
+  EXPECT_TRUE(PostDom.dominates(nullptr, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(nullptr, SwitchBlock));
+  EXPECT_TRUE(PostDom.dominates(nullptr, CaseABlock));
+  EXPECT_TRUE(PostDom.dominates(nullptr, ExitBlock));
+}
+
+} // namespace
+} // namespace analysis
+} // namespace clang

cfe/trunk/unittests/Analysis/CFGTest.cpp

 //===- unittests/Analysis/CFGTest.cpp - CFG tests -------------------------===//
 //
 // 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 "CFGBuildResult.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace analysis {
 namespace {
 
-class BuildResult {
-public:
-  enum Status {
-    ToolFailed,
-    ToolRan,
-    SawFunctionBody,
-    BuiltCFG,
-  };
-
-  BuildResult(Status S, std::unique_ptr<CFG> Cfg = nullptr)
-      : S(S), Cfg(std::move(Cfg)) {}
-
-  Status getStatus() const { return S; }
-  CFG *getCFG() const { return Cfg.get(); }
-
-private:
-  Status S;
-  std::unique_ptr<CFG> Cfg;
-};
-
-class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
-public:
-  BuildResult TheBuildResult = BuildResult::ToolRan;
-
-  void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
-    const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
-    Stmt *Body = Func->getBody();
-    if (!Body)
-      return;
-    TheBuildResult = BuildResult::SawFunctionBody;
-    CFG::BuildOptions Options;
-    Options.AddImplicitDtors = true;
-    if (std::unique_ptr<CFG> Cfg =
-            CFG::buildCFG(nullptr, Body, Result.Context, Options))
-      TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg)};
-  }
-};
-
-BuildResult BuildCFG(const char *Code) {
-  CFGCallback Callback;
-
-  ast_matchers::MatchFinder Finder;
-  Finder.addMatcher(ast_matchers::functionDecl().bind("func"), &Callback);
-  std::unique_ptr<tooling::FrontendActionFactory> Factory(
-      tooling::newFrontendActionFactory(&Finder));
-  std::vector<std::string> Args = {"-std=c++11", "-fno-delayed-template-parsing"};
-  if (!tooling::runToolOnCodeWithArgs(Factory->create(), Code, Args))
-    return BuildResult::ToolFailed;
-  return std::move(Callback.TheBuildResult);
-}
-
 // Constructing a CFG for a range-based for over a dependent type fails (but
 // should not crash).
 TEST(CFG, RangeBasedForOverDependentType) {
   const char *Code = "class Foo;\n"
                      "template <typename T>\n"
                      "void f(const T &Range) {\n"
                      "  for (const Foo *TheFoo : Range) {\n"
                      "  }\n"

cfe/trunk/unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(ClangAnalysisTests
+  CFGDominatorTree.cpp
   CFGTest.cpp
   CloneDetectionTest.cpp
   ExprMutationAnalyzerTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisTests
   PRIVATE
   clangAnalysis
   clangAST
   clangASTMatchers
   clangBasic
   clangFrontend
   clangSerialization
   clangTooling
   )