Index: cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def =================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def +++ cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def @@ -291,6 +291,11 @@ "the analyzer's progress related to ctu.", false) +ANALYZER_OPTION(bool, ShouldTrackConditions, "track-conditions", + "Whether to track conditions that are a control dependency of " + "an already tracked variable.", + false) + //===----------------------------------------------------------------------===// // Unsinged analyzer options. //===----------------------------------------------------------------------===// Index: cfe/trunk/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h =================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h +++ cfe/trunk/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h @@ -153,6 +153,9 @@ /// \sa removeInvalidation llvm::SmallSet Invalidations; + /// Conditions we're already tracking. + llvm::SmallSet TrackedConditions; + private: // Used internally by BugReporter. Symbols &getInterestingSymbols(); @@ -349,6 +352,13 @@ visitor_iterator visitor_begin() { return Callbacks.begin(); } visitor_iterator visitor_end() { return Callbacks.end(); } + /// Notes that the condition of the CFGBlock associated with \p Cond is + /// being tracked. + /// \returns false if the condition is already being tracked. + bool addTrackedCondition(const ExplodedNode *Cond) { + return TrackedConditions.insert(Cond).second; + } + /// Profile to identify equivalent bug reports for error report coalescing. /// Reports are uniqued to ensure that we do not emit multiple diagnostics /// for each bug. Index: cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -22,6 +22,7 @@ #include "clang/AST/Stmt.h" #include "clang/AST/Type.h" #include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Analysis/Analyses/Dominators.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/CFGStmtMap.h" @@ -1619,6 +1620,89 @@ } //===----------------------------------------------------------------------===// +// TrackControlDependencyCondBRVisitor. +//===----------------------------------------------------------------------===// + +namespace { +/// Tracks the expressions that are a control dependency of the node that was +/// supplied to the constructor. +/// For example: +/// +/// cond = 1; +/// if (cond) +/// 10 / 0; +/// +/// An error is emitted at line 3. This visitor realizes that the branch +/// on line 2 is a control dependency of line 3, and tracks it's condition via +/// trackExpressionValue(). +class TrackControlDependencyCondBRVisitor final : public BugReporterVisitor { + const ExplodedNode *Origin; + ControlDependencyCalculator ControlDeps; + llvm::SmallSet VisitedBlocks; + +public: + TrackControlDependencyCondBRVisitor(const ExplodedNode *O) + : Origin(O), ControlDeps(&O->getCFG()) {} + + void Profile(llvm::FoldingSetNodeID &ID) const override { + static int x = 0; + ID.AddPointer(&x); + } + + std::shared_ptr VisitNode(const ExplodedNode *N, + BugReporterContext &BRC, + BugReport &BR) override; +}; +} // end of anonymous namespace + +static CFGBlock *GetRelevantBlock(const ExplodedNode *Node) { + if (auto SP = Node->getLocationAs()) { + const Stmt *S = SP->getStmt(); + assert(S); + + return const_cast(Node->getLocationContext() + ->getAnalysisDeclContext()->getCFGStmtMap()->getBlock(S)); + } + + return nullptr; +} + +std::shared_ptr +TrackControlDependencyCondBRVisitor::VisitNode(const ExplodedNode *N, + BugReporterContext &BRC, + BugReport &BR) { + // We can only reason about control dependencies within the same stack frame. + if (Origin->getStackFrame() != N->getStackFrame()) + return nullptr; + + CFGBlock *NB = GetRelevantBlock(N); + + // Skip if we already inspected this block. + if (!VisitedBlocks.insert(NB).second) + return nullptr; + + CFGBlock *OriginB = GetRelevantBlock(Origin); + + // TODO: Cache CFGBlocks for each ExplodedNode. + if (!OriginB || !NB) + return nullptr; + + if (ControlDeps.isControlDependent(OriginB, NB)) { + if (const Expr *Condition = NB->getLastCondition()) { + // Keeping track of the already tracked conditions on a visitor level + // isn't sufficient, because a new visitor is created for each tracked + // expression, hence the BugReport level set. + if (BR.addTrackedCondition(N)) { + bugreporter::trackExpressionValue( + N, Condition, BR, /*EnableNullFPSuppression=*/false); + } + } + } + + return nullptr; +} + +//===----------------------------------------------------------------------===// // Implementation of trackExpressionValue. //===----------------------------------------------------------------------===// @@ -1734,6 +1818,15 @@ ProgramStateRef LVState = LVNode->getState(); + // We only track expressions if we believe that they are important. Chances + // are good that control dependencies to the tracking point are also improtant + // because of this, let's explain why we believe control reached this point. + // TODO: Shouldn't we track control dependencies of every bug location, rather + // than only tracked expressions? + if (LVState->getAnalysisManager().getAnalyzerOptions().ShouldTrackConditions) + report.addVisitor(llvm::make_unique( + InputNode)); + // The message send could be nil due to the receiver being nil. // At this point in the path, the receiver should be live since we are at the // message send expr. If it is nil, start tracking it. Index: cfe/trunk/test/Analysis/analyzer-config.c =================================================================== --- cfe/trunk/test/Analysis/analyzer-config.c +++ cfe/trunk/test/Analysis/analyzer-config.c @@ -84,8 +84,9 @@ // CHECK-NEXT: suppress-c++-stdlib = true // CHECK-NEXT: suppress-inlined-defensive-checks = true // CHECK-NEXT: suppress-null-return-paths = true +// CHECK-NEXT: track-conditions = false // CHECK-NEXT: unix.DynamicMemoryModeling:Optimistic = false // CHECK-NEXT: unroll-loops = false // CHECK-NEXT: widen-loops = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 85 +// CHECK-NEXT: num-entries = 86 Index: cfe/trunk/test/Analysis/track-control-dependency-conditions.cpp =================================================================== --- cfe/trunk/test/Analysis/track-control-dependency-conditions.cpp +++ cfe/trunk/test/Analysis/track-control-dependency-conditions.cpp @@ -0,0 +1,285 @@ +// RUN: %clang_analyze_cc1 %s \ +// RUN: -verify=expected,tracking \ +// RUN: -analyzer-config track-conditions=true \ +// RUN: -analyzer-output=text \ +// RUN: -analyzer-checker=core +// +// RUN: %clang_analyze_cc1 %s -verify \ +// RUN: -analyzer-output=text \ +// RUN: -analyzer-checker=core + +namespace example_1 { +int flag; +bool coin(); + +void foo() { + flag = coin(); // tracking-note{{Value assigned to 'flag'}} +} + +void test() { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + flag = 1; + + foo(); // TODO: Add nodes here about flag's value being invalidated. + if (flag) // expected-note {{Assuming 'flag' is 0}} + // expected-note@-1{{Taking false branch}} + x = new int; + + foo(); // tracking-note{{Calling 'foo'}} + // tracking-note@-1{{Returning from 'foo'}} + + if (flag) // expected-note {{Assuming 'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace example_1 + +namespace example_2 { +int flag; +bool coin(); + +void foo() { + flag = coin(); // tracking-note{{Value assigned to 'flag'}} +} + +void test() { + int *x = 0; + flag = 1; + + foo(); + if (flag) // expected-note {{Assuming 'flag' is 0}} + // expected-note@-1{{Taking false branch}} + x = new int; + + x = 0; // expected-note{{Null pointer value stored to 'x'}} + + foo(); // tracking-note{{Calling 'foo'}} + // tracking-note@-1{{Returning from 'foo'}} + + if (flag) // expected-note {{Assuming 'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace example_2 + +namespace global_variable_invalidation { +int flag; +bool coin(); + +void foo() { + // coin() could write bar, do it's invalidated. + flag = coin(); // tracking-note{{Value assigned to 'flag'}} + // tracking-note@-1{{Value assigned to 'bar'}} +} + +int bar; + +void test() { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + flag = 1; + + foo(); // tracking-note{{Calling 'foo'}} + // tracking-note@-1{{Returning from 'foo'}} + + if (bar) // expected-note {{Assuming 'bar' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + if (flag) // expected-note {{Assuming 'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace global_variable_invalidation + +namespace variable_declaration_in_condition { +bool coin(); + +bool foo() { + return coin(); // tracking-note{{Returning value}} +} + +int bar; + +void test() { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + if (int flag = foo()) // tracking-note{{Calling 'foo'}} + // tracking-note@-1{{Returning from 'foo'}} + // tracking-note@-2{{'flag' initialized here}} + + // expected-note@-4{{Assuming 'flag' is not equal to 0}} + // expected-note@-5{{Taking true branch}} + + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace variable_declaration_in_condition + +namespace conversion_to_bool { +bool coin(); + +struct ConvertsToBool { + operator bool() const { return coin(); } // tracking-note{{Returning value}} +}; + +void test() { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + if (ConvertsToBool()) + // tracking-note@-1 {{Calling 'ConvertsToBool::operator bool'}} + // tracking-note@-2{{Returning from 'ConvertsToBool::operator bool'}} + + // expected-note@-4{{Assuming the condition is true}} + // expected-note@-5{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +} // end of namespace variable_declaration_in_condition + +namespace unimportant_returning_value_note { +bool coin(); + +bool flipCoin() { return coin(); } // tracking-note{{Returning value}} + +void i(int *ptr) { + if (ptr) // expected-note{{Assuming 'ptr' is null}} + // expected-note@-1{{Taking false branch}} + ; + if (!flipCoin()) + // tracking-note@-1{{Calling 'flipCoin'}} + // tracking-note@-2{{Returning from 'flipCoin'}} + // expected-note@-3{{Assuming the condition is true}} + // expected-note@-4{{Taking true branch}} + *ptr = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace unimportant_returning_value_note + +namespace important_returning_value_note { +bool coin(); + +bool flipCoin() { + if (coin()) // tracking-note{{Assuming the condition is false}} + // tracking-note@-1{{Taking false branch}} + return true; + return coin(); // tracking-note{{Returning value}} +} + +void i(int *ptr) { + if (ptr) // expected-note{{Assuming 'ptr' is null}} + // expected-note@-1{{Taking false branch}} + ; + if (!flipCoin()) + // tracking-note@-1{{Calling 'flipCoin'}} + // tracking-note@-2{{Returning from 'flipCoin'}} + // expected-note@-3{{Assuming the condition is true}} + // expected-note@-4{{Taking true branch}} + *ptr = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace important_returning_value_note + +namespace tracked_condition_is_only_initialized { +int getInt(); + +void f() { + int flag = getInt(); // tracking-note{{'flag' initialized here}} + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + if (flag) // expected-note{{Assuming 'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace tracked_condition_is_only_initialized + +namespace tracked_condition_written_in_same_stackframe { +int flag; +int getInt(); + +void f(int y) { + y = 1; // tracking-note{{The value 1 is assigned to 'y'}} + flag = y; // tracking-note{{The value 1 is assigned to 'flag'}} + + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + if (flag) // expected-note{{'flag' is 1}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace tracked_condition_written_in_same_stackframe + +namespace tracked_condition_written_in_nested_stackframe { +int flag; +int getInt(); + +void foo() { + int y; + y = 1; // tracking-note{{The value 1 is assigned to 'y'}} + flag = y; // tracking-note{{The value 1 is assigned to 'flag'}} + +} + +void f(int y) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + foo(); // tracking-note{{Calling 'foo'}} + // tracking-note@-1{{Returning from 'foo'}} + + if (flag) // expected-note{{'flag' is 1}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} +} // end of namespace tracked_condition_written_in_nested_stackframe + +namespace collapse_point_not_in_condition { + +[[noreturn]] void halt(); + +void assert(int b) { + if (!b) // tracking-note{{Assuming 'b' is not equal to 0}} + // tracking-note@-1{{Taking false branch}} + halt(); +} + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + assert(flag); // tracking-note{{Calling 'assert'}} + // tracking-note@-1{{Returning from 'assert'}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +} // end of namespace collapse_point_not_in_condition + +namespace unimportant_write_before_collapse_point { + +[[noreturn]] void halt(); + +void assert(int b) { + if (!b) // tracking-note{{Assuming 'b' is not equal to 0}} + // tracking-note@-1{{Taking false branch}} + halt(); +} +int getInt(); + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + flag = getInt(); // tracking-note{{Value assigned to 'flag'}} + assert(flag); // tracking-note{{Calling 'assert'}} + // tracking-note@-1{{Returning from 'assert'}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +} // end of namespace unimportant_write_before_collapse_point