diff --git a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -3,6 +3,8 @@ ) add_clang_unittest(ClangAnalysisFlowSensitiveTests + TestingSupport.cpp + TestingSupportTest.cpp TypeErasedDataflowAnalysisTest.cpp ) diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -0,0 +1,190 @@ +//===--- DataflowValues.h - Data structure for dataflow values --*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines a skeleton data structure for encapsulating the dataflow +// values for a CFG. Typically this is subclassed to provide methods for +// computing these values from a CFG. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_ +#define LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_ + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchersInternal.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Basic/LLVM.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Error.h" +#include "llvm/Testing/Support/Annotations.h" +#include "gtest/gtest.h" +#include +#include +#include +#include + +namespace clang { +namespace dataflow { + +// Requires a `<<` operator for the `Lattice` type. +template () + << std::declval())> +std::ostream &operator<<(std::ostream &OS, + const DataflowAnalysisState &S) { + std::string Separator = ""; + OS << "{lattice="; + OS << S.Lattice; + // FIXME: add printing support for the environment. + OS << ", environment=...}"; + return OS; +} + +// Returns assertions based on annotations that are present after statements in +// `AnnotatedCode`. +llvm::Expected> +buildStatementToAnnotationMapping(const FunctionDecl *Func, + llvm::Annotations AnnotatedCode); + +// Returns a map from statement annotations to the state computed for the +// program point immediately after the annotated statement. +std::vector> +buildAnnotationToOutputStateMapping( + const CFG &Cfg, + std::vector> + &BlockToOutputState, + const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, + const llvm::DenseMap &StatementToAnnotationMap); + +// Invokes `Operation` with the ASTContext of the translation unit created from +// `Code`, passing the additional arguments provided in `Args`, and including +// the files provided in `VirtualMappedFiles`. +bool runOnCode(llvm::StringRef Code, + const std::function &Operation, + ArrayRef Args, + const tooling::FileContentMappings &VirtualMappedFiles = + tooling::FileContentMappings()); + +namespace testing { + +// Creates a CFG from the body of the function that matches `func_matcher`, +// suitable to testing a dataflow analysis. +std::pair> +buildCFG(ASTContext &Context, + ast_matchers::internal::Matcher FuncMatcher); + +// Runs dataflow on the body of the function that matches `func_matcher` in code +// snippet `code`. Requires: `Analysis` contains a type `Lattice`. +template +void runDataflow( + llvm::StringRef Code, + ast_matchers::internal::Matcher FuncMatcher, + std::function MakeAnalysis, + std::function>>, + ASTContext &)> + Expectations, + ArrayRef Args, + const tooling::FileContentMappings &VirtualMappedFiles = {}) { + llvm::Annotations Annotations(Code); + runOnCode( + Annotations.code(), + [FuncMatcher, &Annotations, &MakeAnalysis, + &Expectations](ASTContext &Context) { + if (Context.getDiagnostics().getClient()->getNumErrors() != 0) { + FAIL() + << "Source file has syntax or type errors, they were printed to " + "the test log"; + } + + std::pair> CFGResult = + buildCFG(Context, FuncMatcher); + const auto *f = CFGResult.first; + auto cfg = std::move(CFGResult.second); + ASSERT_TRUE(f != nullptr) << "Could not find target function"; + ASSERT_TRUE(cfg != nullptr) << "Could not build control flow graph."; + + Environment Env; + auto Analysis = MakeAnalysis(Context, Env); + + llvm::Expected> + StmtToAnnotations = + buildStatementToAnnotationMapping(f, Annotations); + if (auto E = StmtToAnnotations.takeError()) { + FAIL() << "Failed to build annotation map: " + << llvm::toString(std::move(E)); + return; + } + + std::vector> + TypeErasedBlockStates = + runTypeErasedDataflowAnalysis(*cfg, Analysis, Env); + + if (TypeErasedBlockStates.empty()) { + Expectations({}, Context); + return; + } + + std::vector> + TypeErasedResults = buildAnnotationToOutputStateMapping( + *cfg, TypeErasedBlockStates, Env, Analysis, *StmtToAnnotations); + + std::vector>> + Results; + Results.reserve(TypeErasedResults.size()); + for (auto &Entry : TypeErasedResults) { + auto *Lattice = llvm::any_cast( + &Entry.second.Lattice.Value); + if (Lattice == nullptr) { + FAIL() << "Could not cast lattice element to expected type."; + } + + Results.emplace_back( + std::move(Entry.first), + DataflowAnalysisState{ + std::move(*Lattice), std::move(Entry.second.Env)}); + } + Expectations(Results, Context); + }, + Args, VirtualMappedFiles); +} + +// Runs dataflow on the body of the function named `target_fun` in code snippet +// `code`. +template +void runDataflow( + llvm::StringRef Code, llvm::StringRef TargetFun, + std::function MakeAnalysis, + std::function>>, + ASTContext &)> + Expectations, + ArrayRef Args, + const tooling::FileContentMappings &VirtualMappedFiles = {}) { + runDataflow(Code, ast_matchers::hasName(TargetFun), std::move(MakeAnalysis), + std::move(Expectations), Args, VirtualMappedFiles); +} + +} // namespace testing +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_ diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp b/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp @@ -0,0 +1,216 @@ +#include "TestingSupport.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.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/DataflowEnvironment.h" +#include "clang/Basic/LLVM.h" +#include "clang/Basic/LangOptions.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Basic/TokenKinds.h" +#include "clang/Lex/Lexer.h" +#include "clang/Serialization/PCHContainerOperations.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" +#include "llvm/Support/Error.h" +#include "llvm/Testing/Support/Annotations.h" +#include "gtest/gtest.h" +#include +#include +#include +#include +#include +#include + +using namespace clang; +using namespace dataflow; + +namespace { +using ast_matchers::MatchFinder; + +class FindTranslationUnitCallback : public MatchFinder::MatchCallback { +public: + explicit FindTranslationUnitCallback( + std::function Operation) + : Operation{Operation} {} + + void run(const MatchFinder::MatchResult &Result) override { + const auto *TU = Result.Nodes.getNodeAs("tu"); + if (TU->getASTContext().getDiagnostics().getClient()->getNumErrors() != 0) { + FAIL() << "Source file has syntax or type errors, they were printed to " + "the test log"; + } + Operation(TU->getASTContext()); + } + + std::function Operation; +}; +} // namespace + +static bool +isAnnotationDirectlyAfterStatement(const Stmt *Stmt, unsigned AnnotationBegin, + const SourceManager &SourceManager, + const LangOptions &LangOptions) { + auto NextToken = + Lexer::findNextToken(Stmt->getEndLoc(), SourceManager, LangOptions); + + while (NextToken.hasValue() && + SourceManager.getFileOffset(NextToken->getLocation()) < + AnnotationBegin) { + if (NextToken->isNot(tok::semi)) + return false; + + NextToken = Lexer::findNextToken(NextToken->getEndLoc(), SourceManager, + LangOptions); + } + + return true; +} + +llvm::Expected> +buildStatementToAnnotationMapping(const FunctionDecl *Func, + llvm::Annotations AnnotatedCode) { + llvm::DenseMap Result; + + using namespace ast_matchers; // NOLINT: Too many names + auto StmtMatcher = + findAll(stmt(unless(anyOf(hasParent(expr()), hasParent(returnStmt())))) + .bind("stmt")); + + // This map should stay sorted because the binding algorithm relies on the + // ordering of statement offsets + std::map Stmts; + auto &Context = Func->getASTContext(); + auto &SourceManager = Context.getSourceManager(); + + for (auto &Match : match(StmtMatcher, *Func->getBody(), Context)) { + const auto *S = Match.getNodeAs("stmt"); + unsigned Offset = SourceManager.getFileOffset(S->getEndLoc()); + Stmts[Offset] = S; + } + + unsigned I = 0; + auto Annotations = AnnotatedCode.ranges(); + std::reverse(Annotations.begin(), Annotations.end()); + auto Code = AnnotatedCode.code(); + + for (auto OffsetAndStmt = Stmts.rbegin(); OffsetAndStmt != Stmts.rend(); + OffsetAndStmt++) { + unsigned Offset = OffsetAndStmt->first; + const Stmt *Stmt = OffsetAndStmt->second; + + if (I < Annotations.size() && Annotations[I].Begin >= Offset) { + auto Range = Annotations[I]; + + if (!isAnnotationDirectlyAfterStatement(Stmt, Range.Begin, SourceManager, + Context.getLangOpts())) { + return llvm::createStringError( + std::make_error_code(std::errc::invalid_argument), + "Annotation is not placed after a statement: %s", + SourceManager.getLocForStartOfFile(SourceManager.getMainFileID()) + .getLocWithOffset(Offset) + .printToString(SourceManager) + .data()); + } + + Result[Stmt] = Code.slice(Range.Begin, Range.End).str(); + I++; + + if (I < Annotations.size() && Annotations[I].Begin >= Offset) { + return llvm::createStringError( + std::make_error_code(std::errc::invalid_argument), + "Multiple annotations bound to the statement at the location: %s", + Stmt->getBeginLoc().printToString(SourceManager).data()); + } + } + } + + if (I < Annotations.size()) { + return llvm::createStringError( + std::make_error_code(std::errc::invalid_argument), + "Not all annotations were bound to statements. Unbound annotation at: " + "%s", + SourceManager.getLocForStartOfFile(SourceManager.getMainFileID()) + .getLocWithOffset(Annotations[I].Begin) + .printToString(SourceManager) + .data()); + } + + return Result; +} + +std::vector> +buildAnnotationToOutputStateMapping( + const CFG &Cfg, + std::vector> + &BlockToOutputState, + const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, + const llvm::DenseMap &StatementToAnnotationMap) { + std::vector> Result; + for (const CFGBlock *Block : Cfg) { + // Skip blocks that were not evaluated. + if (!BlockToOutputState[Block->getBlockID()].hasValue()) + continue; + + transferBlock(BlockToOutputState, *Block, InitEnv, Analysis, + [&Result, &StatementToAnnotationMap]( + const clang::CFGStmt &Stmt, + const TypeErasedDataflowAnalysisState &State) { + auto It = StatementToAnnotationMap.find(Stmt.getStmt()); + if (It == StatementToAnnotationMap.end()) + return; + Result.emplace_back(It->second, State); + }); + } + return Result; +} + +bool runOnCode(llvm::StringRef Code, + const std::function &Operation, + ArrayRef Args, + const tooling::FileContentMappings &VirtualMappedFiles) { + MatchFinder MatchFinder; + FindTranslationUnitCallback Callback(Operation); + + using namespace ast_matchers; // NOLINT: Too many names + + MatchFinder.addMatcher(translationUnitDecl().bind("tu"), &Callback); + + std::unique_ptr Factory( + tooling::newFrontendActionFactory(&MatchFinder)); + return tooling::runToolOnCodeWithArgs( + Factory->create(), Code, Args, "input.cc", "clang-data-flow-test-tool", + std::make_shared(), VirtualMappedFiles); +} + +namespace testing { + +std::pair> +buildCFG(ASTContext &Context, + ast_matchers::internal::Matcher FuncMatcher) { + CFG::BuildOptions Options; + Options.PruneTriviallyFalseEdges = false; + Options.AddInitializers = true; + Options.AddImplicitDtors = true; + Options.AddTemporaryDtors = true; + Options.setAllAlwaysAdd(); + + const FunctionDecl *F = ast_matchers::selectFirst( + "target", + ast_matchers::match( + ast_matchers::functionDecl(ast_matchers::isDefinition(), FuncMatcher) + .bind("target"), + Context)); + if (F == nullptr) + return std::make_pair(nullptr, nullptr); + + return std::make_pair( + F, clang::CFG::buildCFG(F, F->getBody(), &Context, Options)); +} + +} // namespace testing diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp b/clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp @@ -0,0 +1,174 @@ +#include "TestingSupport.h" +#include "clang/AST/ASTContext.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +using namespace clang; +using namespace dataflow; + +namespace { + +using ::clang::ast_matchers::functionDecl; +using ::clang::ast_matchers::hasName; +using ::clang::ast_matchers::isDefinition; +using ::testing::_; +using ::testing::IsEmpty; +using ::testing::Pair; +using ::testing::UnorderedElementsAre; + +class NoopLattice { +public: + bool operator==(const NoopLattice &) const { return true; } + + LatticeJoinEffect join(const NoopLattice &) { + return LatticeJoinEffect::Unchanged; + } +}; + +class NoopAnalysis : public DataflowAnalysis { +public: + NoopAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) {} + + static NoopLattice initialElement() { return {}; } + + NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) { + return {}; + } +}; + +template +const FunctionDecl *findTargetFunc(ASTContext &Context, T FunctionMatcher) { + auto TargetMatcher = + functionDecl(FunctionMatcher, isDefinition()).bind("target"); + for (const auto &Node : ast_matchers::match(TargetMatcher, Context)) { + const auto *Func = Node.template getNodeAs("target"); + if (Func == nullptr) + continue; + if (Func->isTemplated()) + continue; + return Func; + } + return nullptr; +} + +class BuildStatementToAnnotationMappingTest : public ::testing::Test { +public: + void + runTest(llvm::StringRef SourceCode, llvm::StringRef TargetName, + std::function &)> + RunChecks) { + llvm::Annotations AnnotatedCode(SourceCode); + + auto Test = [&AnnotatedCode, TargetName, &RunChecks](ASTContext &Context) { + const FunctionDecl *Func = findTargetFunc(Context, hasName(TargetName)); + ASSERT_NE(Func, nullptr); + + llvm::Expected> Mapping = + buildStatementToAnnotationMapping(Func, AnnotatedCode); + ASSERT_TRUE(static_cast(Mapping)); + RunChecks(Mapping.get()); + }; + + ASSERT_TRUE( + runOnCode(AnnotatedCode.code(), Test, {"-fsyntax-only", "-std=c++17"})); + } +}; + +TEST_F(BuildStatementToAnnotationMappingTest, ReturnStmt) { + runTest(R"( + int target() { + return 42; + /*[[ok]]*/ + } + )", + "target", + [](const llvm::DenseMap &Annotations) { + ASSERT_EQ(Annotations.size(), 1); + EXPECT_TRUE(isa(Annotations.begin()->first)); + EXPECT_EQ(Annotations.begin()->second, "ok"); + }); +} + +void runDataflow( + llvm::StringRef Code, llvm::StringRef Target, + std::function>>, + ASTContext &)> + Expectations) { + clang::dataflow::testing::runDataflow( + Code, Target, + [](ASTContext &Context, Environment &) { return NoopAnalysis(Context); }, + std::move(Expectations), {"-fsyntax-only", "-std=c++17"}); +} + +TEST(ProgramPointAnnotations, NoAnnotations) { + ::testing::MockFunction>>, + ASTContext &)> + Expectations; + + EXPECT_CALL(Expectations, Call(IsEmpty(), _)).Times(1); + + runDataflow("void target() {}", "target", Expectations.AsStdFunction()); +} + +TEST(ProgramPointAnnotations, NoAnnotationsDifferentTarget) { + ::testing::MockFunction>>, + ASTContext &)> + Expectations; + + EXPECT_CALL(Expectations, Call(IsEmpty(), _)).Times(1); + + runDataflow("void fun() {}", "fun", Expectations.AsStdFunction()); +} + +TEST(ProgramPointAnnotations, WithCodepoint) { + ::testing::MockFunction>>, + ASTContext &)> + Expectations; + + EXPECT_CALL(Expectations, + Call(UnorderedElementsAre(Pair("program-point", _)), _)) + .Times(1); + + runDataflow(R"cc(void target() { + int n; + // [[program-point]] + })cc", + "target", Expectations.AsStdFunction()); +} + +TEST(ProgramPointAnnotations, MultipleCodepoints) { + ::testing::MockFunction>>, + ASTContext &)> + Expectations; + + EXPECT_CALL(Expectations, + Call(UnorderedElementsAre(Pair("program-point-1", _), + Pair("program-point-2", _)), + _)) + .Times(1); + + runDataflow(R"cc(void target(bool b) { + if (b) { + int n; + // [[program-point-1]] + } else { + int m; + // [[program-point-2]] + } + })cc", + "target", Expectations.AsStdFunction()); +} + +} // namespace