[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Kristóf Umann via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rL365207: [analyzer] Track terminator conditions on which a 
tracked expression depends (authored by Szelethus, committed by ).
Herald added a project: LLVM.
Herald added a subscriber: llvm-commits.

Changed prior to commit:
  https://reviews.llvm.org/D62883?vs=208084=208167#toc

Repository:
  rL LLVM

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883

Files:
  cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def
  cfe/trunk/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h
  cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
  cfe/trunk/test/Analysis/analyzer-config.c
  cfe/trunk/test/Analysis/track-control-dependency-conditions.cpp

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(>getCFG()) {}
+
+  void Profile(llvm::FoldingSetNodeID ) const override {
+static int x = 0;
+ID.AddPointer();
+  }
+
+  std::shared_ptr VisitNode(const ExplodedNode *N,
+ BugReporterContext ,
+ BugReport ) 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 ,
+   BugReport ) {
+  // 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.

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Artem Dergachev via Phabricator via cfe-commits]

NoQ accepted this revision.
NoQ added a comment.

Accept².




Comment at: clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp:1824-1825
+  // 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)

To think: not sure you want to do this for memory leak reports, because the 
place where the leak is discovered (i.e., where we randomly decided to run 
garbage collection and noticed a leak) may be fairly weird. Path to that point 
may still be moderately interesting (after all, it presumably doesn't leak on 
other paths), but i'm still worried that we may bring in some completely 
unrelated stuff. I might be wrong.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus updated this revision to Diff 208084.
Szelethus marked 6 inline comments as done.
Szelethus added a comment.

- Add two more test cases when a "Returning value" note is meaningful, and one 
where it's not
- Fix inlines!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883

Files:
  clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def
  clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h
  clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
  clang/test/Analysis/analyzer-config.c
  clang/test/Analysis/track-control-dependency-conditions.cpp

Index: clang/test/Analysis/track-control-dependency-conditions.cpp
===
--- /dev/null
+++ clang/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 

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus marked an inline comment as done.
Szelethus added a comment.

I usually do the final update right before commiting. There still are 
non-accepted dependencies, who knows what'll happen.




Comment at: 
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h:157
+  /// Conditions we're already tracking.
+  llvm::SmallPtrSet TrackedConditions;
+

xazax.hun wrote:
> Szelethus wrote:
> > xazax.hun wrote:
> > > Do we need this? I wonder if marking the result of the condition as 
> > > interesting is sufficient.
> > Later on, when I'm covering the "should-not-have-happened" case, it's 
> > possible that a condition would be added that wasn't even explored by the 
> > analyzer, so this is kinda necessary.
> When the analyzer did not explore a given code snippet we will not have an 
> exploded node, but we can change this in a followup patch.
Ugh, right. Let's keep this as is is for now, dunno how I forgot about it.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun accepted this revision.
xazax.hun added a comment.
This revision is now accepted and ready to land.

Artem had some comments that are not marked as done, but LGTM!




Comment at: 
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h:157
+  /// Conditions we're already tracking.
+  llvm::SmallPtrSet TrackedConditions;
+

Szelethus wrote:
> xazax.hun wrote:
> > Do we need this? I wonder if marking the result of the condition as 
> > interesting is sufficient.
> Later on, when I'm covering the "should-not-have-happened" case, it's 
> possible that a condition would be added that wasn't even explored by the 
> analyzer, so this is kinda necessary.
When the analyzer did not explore a given code snippet we will not have an 
exploded node, but we can change this in a followup patch.



Comment at: 
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h:355-357
+  bool addTrackedCondition(const ExplodedNode *Cond) {
+return TrackedConditions.insert(Cond).second;
+  }

NoQ wrote:
> Pls add a comment that explains when does this function return true or false. 
> I always forget what does insert().second do :)
This is not done yet :)



Comment at: clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp:1628
+if (const Expr *Condition = NB->getTerminatorConditionExpr())
+  if (BR.addTrackedCondition(N))
+bugreporter::trackExpressionValue(

NoQ wrote:
> Maybe let's add a comment that this is for inter-visitor communication only. 
> Because otherwise we won't visit the same node twice in the same visitor.
Also not done.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

In D62883#1554514 , @Szelethus wrote:

> In D62883#1554494 , @NoQ wrote:
>
> > It should be pretty easy to implement, just add your new visitor to the 
> > list of default visitors in `findValidReport()`.
>
>
> The thinking was to preserve this patch (roughly) in the state as the 
> analyses were run.


Sure!


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus marked an inline comment as done.
Szelethus added inline comments.



Comment at: clang/test/Analysis/track-control-dependency-conditions.cpp:1-8
+// RUN: %clang_analyze_cc1 %s -verify -DTRACKING_CONDITIONS \
+// RUN:   -analyzer-config track-conditions=true \
+// RUN:   -analyzer-output=text \
+// RUN:   -analyzer-checker=core
+//
+// RUN: %clang_analyze_cc1 %s -verify \
+// RUN:   -analyzer-output=text \

NoQ wrote:
> Btw did you try `-verify=` as in D60732? It might make the test more readable.
So //thats// how you do it! Yea, this looks a lot better.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus added a comment.

Woohoo! Thanks for everything, this is the most fun I've had working on this 
project! Let's wait for @xazax.hun to have the final say.

In D62883#1554494 , @NoQ wrote:

> It should be pretty easy to implement, just add your new visitor to the list 
> of default visitors in `findValidReport()`.


The thinking was to preserve this patch (roughly) in the state as the analyses 
were run. I also plan to patch CodeChecker so that it can diff two runs only 
only by bug report hash, but also by bug report length, which should make 
evaluation a lot easier. This may imply that I'll delay tracking control 
dependencies to all error nodes for later, as LLVM literally takes a day to 
analyze each time (and the sheer size of it gives invaluable data, which is why 
I plan doing it, but will check other projects too).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

It should be pretty easy to implement, just add your new visitor to the list of 
default visitors in `findValidReport()`.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Artem Dergachev via Phabricator via cfe-commits]

NoQ accepted this revision.
NoQ added a comment.

Aha, ok, got it. I guess the official term is "error node" (where "error" means 
"warning").




Comment at: clang/test/Analysis/track-control-dependency-conditions.cpp:1-8
+// RUN: %clang_analyze_cc1 %s -verify -DTRACKING_CONDITIONS \
+// RUN:   -analyzer-config track-conditions=true \
+// RUN:   -analyzer-output=text \
+// RUN:   -analyzer-checker=core
+//
+// RUN: %clang_analyze_cc1 %s -verify \
+// RUN:   -analyzer-output=text \

Btw did you try `-verify=` as in D60732? It might make the test more readable.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus added a comment.

In D62883#1554339 , @NoQ wrote:

> In D62883#1553248 , @Szelethus wrote:
>
> > - Add a `TODO:` in `trackExpressionValue` about maybe tracking conditions 
> > to all bug locations, rather than only for tracked variables.
>
>
> What do you mean by "all bug locations"?


This visitor is added when a variable is tracked, yet I feel the control 
dependency of every report is important (else we would never have discovered 
the error).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62883: [analyzer] Track terminator conditions on which a tracked expressions depends

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

In D62883#1553248 , @Szelethus wrote:

> - Add a `TODO:` in `trackExpressionValue` about maybe tracking conditions to 
> all bug locations, rather than only for tracked variables.


What do you mean by "all bug locations"?




Comment at: 
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h:355-357
+  bool addTrackedCondition(const ExplodedNode *Cond) {
+return TrackedConditions.insert(Cond).second;
+  }

Pls add a comment that explains when does this function return true or false. I 
always forget what does insert().second do :)



Comment at: clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp:1628
+if (const Expr *Condition = NB->getTerminatorConditionExpr())
+  if (BR.addTrackedCondition(N))
+bugreporter::trackExpressionValue(

Maybe let's add a comment that this is for inter-visitor communication only. 
Because otherwise we won't visit the same node twice in the same visitor.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62883/new/

https://reviews.llvm.org/D62883



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits