diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -348,10 +348,12 @@ /// Returns the `DeclContext` of the block being analysed, if any. Otherwise, /// returns null. - const DeclContext *getDeclCtx() { return DeclCtx; } + const DeclContext *getDeclCtx() { return CallStack.back(); } - /// Sets the `DeclContext` of the block being analysed. - void setDeclCtx(const DeclContext *Ctx) { DeclCtx = Ctx; } + /// Returns whether this `Environment` can be extended to analyze the given + /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a + /// given `MaxDepth`. + bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const; /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise, /// returns null. @@ -390,7 +392,7 @@ DataflowAnalysisContext *DACtx; // `DeclContext` of the block being analysed if provided. - const DeclContext *DeclCtx = nullptr; + std::vector CallStack; // In a properly initialized `Environment`, `ReturnLoc` should only be null if // its `DeclContext` could not be cast to a `FunctionDecl`. diff --git a/clang/include/clang/Analysis/FlowSensitive/Transfer.h b/clang/include/clang/Analysis/FlowSensitive/Transfer.h --- a/clang/include/clang/Analysis/FlowSensitive/Transfer.h +++ b/clang/include/clang/Analysis/FlowSensitive/Transfer.h @@ -21,7 +21,11 @@ namespace clang { namespace dataflow { -struct ContextSensitiveOptions {}; +struct ContextSensitiveOptions { + /// The maximum depth to analyze. A value of zero is equivalent to disabling + /// context-sensitive analysis entirely. + unsigned Depth = 2; +}; struct TransferOptions { /// Options for analyzing function bodies when present in the translation diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -154,10 +154,10 @@ : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {} Environment::Environment(const Environment &Other) - : DACtx(Other.DACtx), DeclCtx(Other.DeclCtx), ReturnLoc(Other.ReturnLoc), - ThisPointeeLoc(Other.ThisPointeeLoc), DeclToLoc(Other.DeclToLoc), - ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal), - MemberLocToStruct(Other.MemberLocToStruct), + : DACtx(Other.DACtx), CallStack(Other.CallStack), + ReturnLoc(Other.ReturnLoc), ThisPointeeLoc(Other.ThisPointeeLoc), + DeclToLoc(Other.DeclToLoc), ExprToLoc(Other.ExprToLoc), + LocToVal(Other.LocToVal), MemberLocToStruct(Other.MemberLocToStruct), FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) { } @@ -168,11 +168,11 @@ } Environment::Environment(DataflowAnalysisContext &DACtx, - const DeclContext &DeclCtxArg) + const DeclContext &DeclCtx) : Environment(DACtx) { - setDeclCtx(&DeclCtxArg); + CallStack.push_back(&DeclCtx); - if (const auto *FuncDecl = dyn_cast(DeclCtx)) { + if (const auto *FuncDecl = dyn_cast(&DeclCtx)) { assert(FuncDecl->getBody() != nullptr); initGlobalVars(*FuncDecl->getBody(), *this); for (const auto *ParamDecl : FuncDecl->parameters()) { @@ -187,7 +187,7 @@ ReturnLoc = &createStorageLocation(ReturnType); } - if (const auto *MethodDecl = dyn_cast(DeclCtx)) { + if (const auto *MethodDecl = dyn_cast(&DeclCtx)) { auto *Parent = MethodDecl->getParent(); assert(Parent != nullptr); if (Parent->isLambda()) @@ -205,6 +205,13 @@ } } +bool Environment::canDescend(unsigned MaxDepth, + const DeclContext *Callee) const { + return CallStack.size() <= MaxDepth && + std::find(CallStack.begin(), CallStack.end(), Callee) == + CallStack.end(); +} + Environment Environment::pushCall(const CallExpr *Call) const { Environment Env(*this); @@ -239,7 +246,7 @@ void Environment::pushCallInternal(const FunctionDecl *FuncDecl, ArrayRef Args) { - setDeclCtx(FuncDecl); + CallStack.push_back(FuncDecl); // FIXME: In order to allow the callee to reference globals, we probably need // to call `initGlobalVars` here in some way. @@ -326,13 +333,13 @@ assert(DACtx == Other.DACtx); assert(ReturnLoc == Other.ReturnLoc); assert(ThisPointeeLoc == Other.ThisPointeeLoc); - assert(DeclCtx == Other.DeclCtx); + assert(CallStack == Other.CallStack); auto Effect = LatticeJoinEffect::Unchanged; Environment JoinedEnv(*DACtx); - JoinedEnv.setDeclCtx(DeclCtx); + JoinedEnv.CallStack = CallStack; JoinedEnv.ReturnLoc = ReturnLoc; JoinedEnv.ThisPointeeLoc = ThisPointeeLoc; diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -661,7 +661,8 @@ // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`. template void transferInlineCall(const E *S, const FunctionDecl *F) { - if (!Options.ContextSensitiveOpts) + if (!(Options.ContextSensitiveOpts && + Env.canDescend(Options.ContextSensitiveOpts->Depth, F))) return; const ControlFlowContext *CFCtx = Env.getControlFlowContext(F); @@ -689,7 +690,7 @@ assert(CFCtx->getDecl() != nullptr && "ControlFlowContexts in the environment should always carry a decl"); auto Analysis = NoopAnalysis(CFCtx->getDecl()->getASTContext(), - DataflowAnalysisOptions()); + DataflowAnalysisOptions{Options}); auto BlockToOutputState = dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv); diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp @@ -3902,6 +3902,36 @@ {TransferOptions{/*.ContextSensitiveOpts=*/llvm::None}}); } +TEST(TransferTest, ContextSensitiveDepthZero) { + std::string Code = R"( + bool GiveBool(); + void SetBool(bool &Var) { Var = true; } + + void target() { + bool Foo = GiveBool(); + SetBool(Foo); + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + auto &FooVal = + *cast(Env.getValue(*FooDecl, SkipPast::None)); + EXPECT_FALSE(Env.flowConditionImplies(FooVal)); + EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal))); + }, + {TransferOptions{ContextSensitiveOptions{/*.Depth=*/0}}}); +} + TEST(TransferTest, ContextSensitiveSetTrue) { std::string Code = R"( bool GiveBool(); @@ -4000,7 +4030,7 @@ {TransferOptions{ContextSensitiveOptions{}}}); } -TEST(TransferTest, ContextSensitiveSetTwoLayers) { +TEST(TransferTest, ContextSensitiveSetTwoLayersDepthOne) { std::string Code = R"( bool GiveBool(); void SetBool1(bool &Var) { Var = true; } @@ -4028,7 +4058,146 @@ EXPECT_FALSE(Env.flowConditionImplies(FooVal)); EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal))); }, - {TransferOptions{ContextSensitiveOptions{}}}); + {TransferOptions{ContextSensitiveOptions{/*.Depth=*/1}}}); +} + +TEST(TransferTest, ContextSensitiveSetTwoLayersDepthTwo) { + std::string Code = R"( + bool GiveBool(); + void SetBool1(bool &Var) { Var = true; } + void SetBool2(bool &Var) { SetBool1(Var); } + + void target() { + bool Foo = GiveBool(); + SetBool2(Foo); + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + auto &FooVal = + *cast(Env.getValue(*FooDecl, SkipPast::None)); + EXPECT_TRUE(Env.flowConditionImplies(FooVal)); + }, + {TransferOptions{ContextSensitiveOptions{/*.Depth=*/2}}}); +} + +TEST(TransferTest, ContextSensitiveSetThreeLayersDepthTwo) { + std::string Code = R"( + bool GiveBool(); + void SetBool1(bool &Var) { Var = true; } + void SetBool2(bool &Var) { SetBool1(Var); } + void SetBool3(bool &Var) { SetBool2(Var); } + + void target() { + bool Foo = GiveBool(); + SetBool3(Foo); + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + auto &FooVal = + *cast(Env.getValue(*FooDecl, SkipPast::None)); + EXPECT_FALSE(Env.flowConditionImplies(FooVal)); + EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal))); + }, + {TransferOptions{ContextSensitiveOptions{/*.Depth=*/2}}}); +} + +TEST(TransferTest, ContextSensitiveSetThreeLayersDepthThree) { + std::string Code = R"( + bool GiveBool(); + void SetBool1(bool &Var) { Var = true; } + void SetBool2(bool &Var) { SetBool1(Var); } + void SetBool3(bool &Var) { SetBool2(Var); } + + void target() { + bool Foo = GiveBool(); + SetBool3(Foo); + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + auto &FooVal = + *cast(Env.getValue(*FooDecl, SkipPast::None)); + EXPECT_TRUE(Env.flowConditionImplies(FooVal)); + }, + {TransferOptions{ContextSensitiveOptions{/*.Depth=*/3}}}); +} + +TEST(TransferTest, ContextSensitiveMutualRecursion) { + std::string Code = R"( + bool Pong(bool X, bool Y); + + bool Ping(bool X, bool Y) { + if (X) { + return Y; + } else { + return Pong(!X, Y); + } + } + + bool Pong(bool X, bool Y) { + if (Y) { + return X; + } else { + return Ping(X, !Y); + } + } + + void target() { + bool Foo = Ping(false, false); + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + // The analysis doesn't crash... + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + auto &FooVal = + *cast(Env.getValue(*FooDecl, SkipPast::None)); + // ... but it also can't prove anything here. + EXPECT_FALSE(Env.flowConditionImplies(FooVal)); + EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal))); + }, + {TransferOptions{ContextSensitiveOptions{/*.Depth=*/4}}}); } TEST(TransferTest, ContextSensitiveSetMultipleLines) {