[clang][dataflow] Add unit tests for PostOrderCFGView

[sgatev]

Summary

This adds unit tests for the PostOrderCFGView class which will be
used as part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[ymandel]

Looks good, but why split the test into its own directory? I see that the implementation file is in clang/lib/Analysis and, in general, the lib and unittest directories are often flatter than the corresponding include directories. Maybe just put it directly into unittests/Analysis?

[xazax.hun]

I don't have strong opinions, just some small preferences, feel free to ignore them:

• Using ASTMatchers feels a bit heavy weight for this task to me. Simply enumerating the function definitions in the TranslationUnitDecl should be sufficient for these tests.
• The tests might be a bit too strict, but this might be by design. In fact, there are more than one (reverse) post orders traversals of the same Cfg. Do we want to bake that particular order into the tests? This makes it harder to do changes but makes sure the tests notify us about such changes. Alternatively, we could do property-based testing, and verify that the view has the fundamental property we are interested in. Namely, if we visit nodes in the right order, we always visit all the predecessors of a node first (before visiting the node itself). Property-based tests are resilient to changes in which order we pick, and they can also make it somewhat easier to write tests (we no longer need to know about basic block IDs).

clang/unittests/Analysis/Analyses/PostOrderCFGViewTest.cpp

23

We could use using namespace here.

clang/unittests/Analysis/Analyses/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_clang_unittest(ClangAnalysisAnalysesTests
+  PostOrderCFGViewTest.cpp
+  )
+
+clang_target_link_libraries(ClangAnalysisAnalysesTests
+  PRIVATE
+  clangAnalysis
+  clangAST
+  clangASTMatchers
+  clangBasic
+  clangFrontend
+  clangTesting
+  clangTooling
+  )
+
+target_link_libraries(ClangAnalysisAnalysesTests
+  PRIVATE
+  LLVMTestingSupport
+  )

clang/unittests/Analysis/Analyses/PostOrderCFGViewTest.cpp

+//===- unittests/Analysis/Analyses/PostOrderCFGViewTest.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 "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Tooling/Tooling.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <iterator>
+#include <memory>
+#include <queue>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace clang {
+namespace analysis {
+namespace analyses {
+namespace {
+
+using ::testing::ElementsAre;
+using ::testing::NotNull;
+
+class PostOrderBlockIDMatchCallback
+    : public ast_matchers::MatchFinder::MatchCallback {
+public:
+  const std::vector<unsigned> &getPostOrderBlockIDs() const {
+    return PostOrderBlockIDs;
+  }
+
+  void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
+    const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
+    ASSERT_THAT(Func, NotNull());
+
+    Stmt *Body = Func->getBody();
+    ASSERT_THAT(Body, NotNull());
+
+    CFG::BuildOptions Options;
+    Options.AddImplicitDtors = true;
+    Options.AddTemporaryDtors = true;
+    Options.setAllAlwaysAdd();
+
+    std::unique_ptr<CFG> Cfg =
+        CFG::buildCFG(nullptr, Body, Result.Context, Options);
+    ASSERT_THAT(Cfg, NotNull());
+
+    PostOrderCFGView POV(Cfg.get());
+    std::priority_queue<const CFGBlock *, std::vector<const CFGBlock *>,
+                        PostOrderCFGView::BlockOrderCompare>
+        BlocksQueue(POV.getComparator());
+    for (const CFGBlock *Block : *Cfg)
+      BlocksQueue.push(Block);
+
+    while (!BlocksQueue.empty()) {
+      PostOrderBlockIDs.push_back(BlocksQueue.top()->getBlockID());
+      BlocksQueue.pop();
+    }
+  }
+
+private:
+  std::vector<unsigned> PostOrderBlockIDs;
+};
+
+template <typename T>
+void expectPostOrderBlockIDs(const char *Code, T MatchesPostOrderBlockIDs) {
+  std::unique_ptr<ASTUnit> AST =
+      tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
+  ASSERT_THAT(AST, NotNull());
+
+  PostOrderBlockIDMatchCallback Callback;
+  ast_matchers::MatchFinder Finder;
+  Finder.addMatcher(
+      ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"),
+      &Callback);
+  Finder.matchAST(AST->getASTContext());
+
+  EXPECT_THAT(Callback.getPostOrderBlockIDs(), MatchesPostOrderBlockIDs);
+}
+
+TEST(PostOrderCFGViewTest, EmptyFunc) {
+  expectPostOrderBlockIDs(R"(
+    // B1 (succs: B0)
+    void target() {
+    }
+    // B0
+  )",
+                          ElementsAre(0, 1));
+}
+
+TEST(PostOrderCFGViewTest, IfStmt) {
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B5 (succs: B4)
+    void target() {
+      // B4 (succs: B3, B2)
+      foo();
+      if (foo()) {
+        // B3 (succs: B1)
+        foo();
+      } else {
+        // B2 (succs: B1)
+        foo();
+      }
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(0, 1, 3, 2, 4, 5));
+}
+
+TEST(PostOrderCFGViewTest, IfStmtLogicalAnd) {
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B6 (succs: B5)
+    void target() {
+      // B5 (succs: B4, B2)
+      foo();
+      if (foo() && /*B4 (succs: B3, B2)*/ foo()) {
+        // B3 (succs: B1)
+        foo();
+      } else {
+        // B2 (succs: B1)
+        foo();
+      }
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(0, 1, 3, 2, 4, 5, 6));
+}
+
+TEST(PostOrderCFGViewTest, IfStmtLogicalOr) {
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B6 (succs: B5)
+    void target() {
+      // B5 (succs: B3, B4)
+      foo();
+      if (foo() || /*B4 (succs: B3, B2)*/ foo()) {
+        // B2 (succs: B1)
+        foo();
+      } else {
+        // B3 (succs: B1)
+        foo();
+      }
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(0, 1, 3, 2, 4, 5, 6));
+}
+
+TEST(PostOrderCFGViewTest, ForStmt) {
+  expectPostOrderBlockIDs(R"(
+    void foo();
+
+    // B6 (succs: B5)
+    void target() {
+      // B5 (succs: B4)
+      foo();
+      for (int i = 0; /*B4 (succs: B3, B1)*/ i < 10; /*B2 (succs: B4)*/ i++) {
+        // B3 (succs: B2)
+        foo();
+      }
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(2, 3, 0, 1, 4, 5, 6));
+}
+
+TEST(PostOrderCFGViewTest, WhileStmt) {
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B6 (succs: B5)
+    void target() {
+      // B5 (succs: B4)
+      foo();
+      while (/*B4 (succs: B3, B1)*/ foo()) {
+        // B3 (succs: B2)
+        foo();
+      } // B2 (succs: B4 - back edge)
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(2, 3, 0, 1, 4, 5, 6));
+}
+
+TEST(PostOrderCFGViewTest, DoWhileStmt) {
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B6 (succs: B5)
+    void target() {
+      // B5 (succs: B3)
+      foo();
+      do {
+        // B3 (succs: B2)
+        foo();
+      } while (/*B2 (succs: B4, B1)*/ foo()); // B4 (succs: B3 - back edge)
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(4, 0, 1, 2, 3, 5, 6));
+}
+
+TEST(PostOrderCFGViewTest, TernaryCondStmt) {
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B5 (succs: B4)
+    void target() {
+      // B4 (succs: B2, B3)
+      foo();
+      int bar = foo() ? /*B2 (succs: B1)*/ 21 :  /*B3 (succs: B1)*/ 42;
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(0, 1, 2, 3, 4, 5));
+}
+
+TEST(PostOrderCFGViewTest, TernaryCondStmtTempDtor) {
+  expectPostOrderBlockIDs(R"(
+    class Fatal {
+     public:
+      ~Fatal() __attribute__((noreturn));
+      int value();
+    };
+
+    bool foo();
+
+    // B7 (succs: B6)
+    void target() {
+      // B6 (succs: B4, B5)
+      foo();
+      int bar = foo() ? /*B4 (succs: B3)*/ 21 :
+                        /*B5 (succs: B3)*/ Fatal().value();
+        // B3 (succs: B2, B1)
+        // B2 (succs: B0 - temp dtor, noreturn)
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(0, 2, 1, 3, 4, 5, 6, 7));
+}
+
+TEST(PostOrderCFGViewTest, GoToStmtForward) {
+  expectPostOrderBlockIDs(R"(
+    void foo();
+
+    // B4 (succs: B3)
+    void target() {
+      // B3 (succs: B1)
+      foo();
+      goto bar;
+      // B2 (succs: B1)
+      foo();
+      bar:
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(2, 0, 1, 3, 4));
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B6 (succs: B5)
+    void target() {
+      // B5 (succs: B4, B3)
+      foo();
+      if (foo()) {
+        // B4 (succs: B1)
+        foo();
+        goto bar;
+      } else {
+        // B3 (succs: B2)
+        foo();
+      }
+      // B2 (succs: B1)
+      foo();
+      bar:
+        // B1 (succs: B0)
+        foo();
+    }
+    // B0
+  )",
+                          ElementsAre(0, 1, 4, 2, 3, 5, 6));
+}
+
+TEST(PostOrderCFGViewTest, GoToStmtBackward) {
+  expectPostOrderBlockIDs(R"(
+    void foo();
+
+    // B3 (succs: B2)
+    void target() {
+      // B2 (succs: B2)
+      bar:
+      foo();
+      foo();
+      goto bar;
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(0, 1, 2, 3));
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B6 (succs: B5)
+    void target() {
+      // B5 (succs: B4)
+      foo();
+      bar:
+      // B4 (succs: B3, B2)
+      if (foo()) {
+        // B3 (succs: B4)
+        foo();
+        goto bar;
+      } else {
+        // B2 (succs: B1)
+        foo();
+      }
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(3, 0, 1, 2, 4, 5, 6));
+}
+
+TEST(PostOrderCFGViewTest, ComplexFlow) {
+  expectPostOrderBlockIDs(R"(
+    bool foo();
+
+    // B10 (succs: B9)
+    void target() {
+      // B9 (succs: B8)
+      foo();
+      for (int i = 0; /*B8 (succs: B7, B1)*/ i < 10; /*B2 (succs: B8)*/ i++) {
+        if ((/*B7 (succs: B6, B5)*/ foo() && /*B6 (succs: B4, B5)*/ foo()) ||
+            /*B5 (succs: B4, B3)*/ foo()) {
+          // B4 (succs: B2)
+          foo();
+        } else {
+          // B3 (succs: B2)
+          foo();
+        }
+      }
+      // B1 (succs: B0)
+      foo();
+    }
+    // B0
+  )",
+                          ElementsAre(2, 4, 3, 5, 6, 7, 0, 1, 8, 9, 10));
+}
+
+} // namespace
+} // namespace analyses
+} // namespace analysis
+} // namespace clang

clang/unittests/Analysis/CMakeLists.txt

clang_target_link_libraries(ClangAnalysisTests
   clangTesting
   clangTooling
   )
 
 target_link_libraries(ClangAnalysisTests
   PRIVATE
   LLVMTestingSupport
   )
+
+add_subdirectory(Analyses)