[Analyzer] Track RValue expressions

[martong]

Summary

It makes sense to track rvalue expressions in the case of special
concrete integer values. The most notable special value is zero (later
we may find other values). By tracking the origin of 0, we can provide a
better explanation for users e.g. in case of division by 0 warnings.
When the divisor is a product of a multiplication then now we can show
which operand (or both) was (were) zero and why.

[vsavchenko]

From the first glance, everything is looking good! Thanks for addressing this!
But I still need to have a deeper look.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1932–1933

I think this should become an assertion and the caller should ensure that E is actually an r-value

1950

APSInt

[steakhal]

I really like it. Looks good.
I'm letting someone else accept this as I've not really touched the trackExpression parts.

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

119–124

It is supposed to be called by the trackExpressionValue().
Why do we expose this function then?

[martong]

• Rebase

[martong]

• Assert in the callee and check in the caller
• Fix typo in comment

[martong]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

119–124

I was thinking about that maybe some Checkers could explicitly want to track RValues only. On the other hand, maybe it just complicates the public API. Anyway, I'd like to hear what other people say about this.

[NoQ]

I think this is a good targeted fix for that problem we've discussed, demonstrated by tests.

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

119–124

I suggest keep it private until there's an actual use case. As of now literally nobody understands how these functions are even supposed to work so it's way too early to give API promises.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1945

SVal::isZeroConstant() please ^.^

[martong]

• Use isZeroConstant()
• Make trackRValueExpression private (static function)
• Fix clang-tidy report: auto *BO ---> const auto *BO

[martong]

Guys, thanks for the review! :)

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1945

Yeah good catch, I wish I knew this before :)

[steakhal]

Some minor logical issues inline.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1944–1945

There are only 3 multiplicative operators:

BINARY_OPERATION(Mul, "*")
BINARY_OPERATION(Div, "/")
BINARY_OPERATION(Rem, "%")

So, the opcode can never be BO_MulAssign later.
The comment for the else block is also inaccurate for the same reason.

[martong]

• Remove handling of assignment

[martong]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1944–1945

Yep, good catch! The reason why the assignment test case passed is that we already handle assignment operations in the FindLastStoreBRVisitor.

// If this is an assignment expression, we can track the value
// being assigned.
if (Optional<PostStmt> P = Succ->getLocationAs<PostStmt>())
  if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>())
    if (BO->isAssignmentOp())
      InitE = BO->getRHS();

So, I could just remove the handling of the assignment from the new function.

[steakhal]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1958–1959

Both divisions and modulo operations can flow here.

[martong]

• Update comment

[martong]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1958–1959

Ok, I updated the comment.

[steakhal]

land it

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1938

This note is not strictly for this patch.

At first, it wasn't clear to me why you call getSValAsScalarOrLoc().
That just returns unknown if the Region is not boundable. Unfortunately, the MemRegion::isBoundable() has no documentation. IMO all virtual call deserves documentation.

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

 /// \return Whether or not the function was able to add visitors for this
 ///         statement. Note that returning \c true does not actually imply
 ///         that any visitors were added.
 bool trackExpressionValue(const ExplodedNode *N, const Expr *E,
                           PathSensitiveBugReport &R,
                           TrackingKind TKind = TrackingKind::Thorough,
                           bool EnableNullFPSuppression = true);
 
+/// Attempts to add visitors to track an RValue expression back to its point of
+/// origin. Works similarly to trackExpressionValue, but accepts only RValues.
+void trackRValueExpression(const ExplodedNode *N, const Expr *E,
+                           PathSensitiveBugReport &R,
+                           TrackingKind TKind = TrackingKind::Thorough,
+                           bool EnableNullFPSuppression = true);
+
 const Expr *getDerefExpr(const Stmt *S);
 
 } // namespace bugreporter
 
 /// Finds last store into the given region,
 /// which is different from a given symbolic value.
 class FindLastStoreBRVisitor final : public BugReporterVisitor {
   const MemRegion *R;

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

static const ExplodedNode* findNodeForExpression(const ExplodedNode *N,
   while (N) {
     if (N->getStmtForDiagnostics() == Inner)
       return N;
     N = N->getFirstPred();
   }
   return N;
 }
 
+void bugreporter::trackRValueExpression(const ExplodedNode *InputNode,
+                                        const Expr *E,
+                                        PathSensitiveBugReport &report,
+                                        bugreporter::TrackingKind TKind,
+                                        bool EnableNullFPSuppression) {
+  if (!E->isRValue())
+    return;
+  const ExplodedNode *RVNode = findNodeForExpression(InputNode, E);
+  if (!RVNode)
+    return;
+  ProgramStateRef RVState = RVNode->getState();
+  SVal V = RVState->getSValAsScalarOrLoc(E, RVNode->getLocationContext());
+  auto *BO = dyn_cast<BinaryOperator>(E);
+  if (!BO)
+    return;
+  ProgramStateManager &Mgr = RVState->getStateManager();
+  SValBuilder &SVB = Mgr.getSValBuilder();
+  BasicValueFactory &BVF = SVB.getBasicValueFactory();
+
+  auto IsZero = [&BVF](const Optional<nonloc::ConcreteInt> &CI) {
+    if (!CI)
+      return false;
+    const llvm::APSInt &Zero = BVF.getValue(0, BVF.getContext().IntTy);
+    // Do the comparison with the same canonical ASPInt.
+    return CI->getValue() == BVF.Convert(CI->getValue(), Zero);
+  };
+
+  auto CI = V.getAs<nonloc::ConcreteInt>();
+  if (!IsZero(CI))
+    return;
+
+  if (!BO->isMultiplicativeOp())
+    return;
+
+  SVal RHSV = RVState->getSVal(BO->getRHS(), RVNode->getLocationContext());
+  SVal LHSV = RVState->getSVal(BO->getLHS(), RVNode->getLocationContext());
+
+  // Track both LHS and RHS of a multiplication.
+  if (BO->getOpcode() == BO_Mul || BO->getOpcode() == BO_MulAssign) {
+    if (IsZero(LHSV.getAs<nonloc::ConcreteInt>())) {
+      trackExpressionValue(InputNode, BO->getLHS(), report, TKind,
+                           EnableNullFPSuppression);
+    }
+    if (IsZero(RHSV.getAs<nonloc::ConcreteInt>())) {
+      trackExpressionValue(InputNode, BO->getRHS(), report, TKind,
+                           EnableNullFPSuppression);
+    }
+    // Track only the LHS of divisions.
+  } else {
+    if (IsZero(LHSV.getAs<nonloc::ConcreteInt>())) {
+      trackExpressionValue(InputNode, BO->getLHS(), report, TKind,
+                           EnableNullFPSuppression);
+    }
+  }
+}
+
 bool bugreporter::trackExpressionValue(const ExplodedNode *InputNode,
                                        const Expr *E,
                                        PathSensitiveBugReport &report,
                                        bugreporter::TrackingKind TKind,
                                        bool EnableNullFPSuppression) {
 
   if (!E || !InputNode)
     return false;
if (auto L = V.getAs<loc::MemRegionVal>()) {
 
     const MemRegion *RegionRVal = RVal.getAsRegion();
     if (RegionRVal && isa<SymbolicRegion>(RegionRVal)) {
       report.markInteresting(RegionRVal, TKind);
       report.addVisitor(std::make_unique<TrackConstraintBRVisitor>(
             loc::MemRegionVal(RegionRVal), /*assumption=*/false));
     }
   }
+
+  trackRValueExpression(LVNode, Inner, report, TKind, EnableNullFPSuppression);
+
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 // Implementation of NulReceiverBRVisitor.
 //===----------------------------------------------------------------------===//
 
 const Expr *NilReceiverBRVisitor::getNilReceiver(const Stmt *S,

clang/test/Analysis/division-by-zero-track-zero.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core \
+// RUN:   -analyzer-output=text \
+// RUN:   -verify %s
+
+int track_mul_lhs_0(int x, int y) {
+  int p0 = x < 0;   // expected-note {{Assuming 'x' is >= 0}} \
+                    // expected-note {{'p0' initialized to 0}}
+  int div = p0 * y; // expected-note {{'div' initialized to 0}}
+  return 1 / div;   // expected-note {{Division by zero}} \
+                    // expected-warning {{Division by zero}}
+}

clang/test/Analysis/division-by-zero-track-zero.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core \
+// RUN:   -analyzer-output=text \
+// RUN:   -verify %s
+
+namespace test_tracking_of_lhs_multiplier {
+  int f(int x, int y) {
+    bool p0 = x < 0;  // expected-note {{Assuming 'x' is >= 0}} \
+                      // expected-note {{'p0' initialized to 0}}
+    int div = p0 * y; // expected-note {{'div' initialized to 0}}
+    return 1 / div;   // expected-note {{Division by zero}} \
+                      // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_of_lhs_multiplier
+
+namespace test_tracking_of_rhs_multiplier {
+  int f(int x, int y) {
+    bool p0 = x < 0;  // expected-note {{Assuming 'x' is >= 0}} \
+                      // expected-note {{'p0' initialized to 0}}
+    int div = y * p0; // expected-note {{'div' initialized to 0}}
+    return 1 / div;   // expected-note {{Division by zero}} \
+                      // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_of_rhs_multiplier
+
+namespace test_tracking_of_nested_multiplier {
+  int f(int x, int y, int z) {
+    bool p0 = x < 0;  // expected-note {{Assuming 'x' is >= 0}} \
+                      // expected-note {{'p0' initialized to 0}}
+    int div = y*z*p0; // expected-note {{'div' initialized to 0}}
+    return 1 / div;   // expected-note {{Division by zero}} \
+                      // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_of_nested_multiplier
+
+namespace test_tracking_through_multiple_stmts {
+  int f(int x, int y) {
+    bool p0 = x < 0;      // expected-note {{Assuming 'x' is >= 0}}
+    bool p1 = p0 ? 0 : 1; // expected-note {{'p0' is false}} \
+                          // expected-note {{'?' condition is false}}
+    bool p2 = 1 - p1;     // expected-note {{'p2' initialized to 0}}
+    int div = p2 * y;     // expected-note {{'div' initialized to 0}}
+    return 1 / div;       // expected-note {{Division by zero}} \
+                          // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_through_multiple_stmts
+
+namespace test_tracking_both_lhs_and_rhs {
+  int f(int x, int y) {
+    bool p0 = x < 0;   // expected-note {{Assuming 'x' is >= 0}} \
+                       // expected-note {{'p0' initialized to 0}}
+    bool p1 = y < 0;   // expected-note {{Assuming 'y' is >= 0}} \
+                       // expected-note {{'p1' initialized to 0}}
+    int div = p0 * p1; // expected-note {{'div' initialized to 0}}
+    return 1 / div;    // expected-note {{Division by zero}} \
+                       // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_both_lhs_and_rhs
+
+namespace test_tracking_of_multiplier_and_parens {
+  int f(int x, int y, int z) {
+    bool p0 = x < 0;    // expected-note {{Assuming 'x' is >= 0}} \
+                        // expected-note {{'p0' initialized to 0}}
+    int div = y*(z*p0); // expected-note {{'div' initialized to 0}}
+    return 1 / div;     // expected-note {{Division by zero}} \
+                        // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_of_multiplier_and_parens
+
+namespace test_tracking_of_divisible {
+  int f(int x, int y) {
+    bool p0 = x < 0;    // expected-note {{Assuming 'x' is >= 0}} \
+                        // expected-note {{'p0' initialized to 0}}
+    int div = p0 / y;   // expected-note {{'div' initialized to 0}}
+    return 1 / div;     // expected-note {{Division by zero}} \
+                        // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_of_divisible
+
+namespace test_tracking_of_modulo {
+  int f(int x, int y) {
+    bool p0 = x < 0;    // expected-note {{Assuming 'x' is >= 0}} \
+                        // expected-note {{'p0' initialized to 0}}
+    int div = p0 % y;   // expected-note {{'div' initialized to 0}}
+    return 1 / div;     // expected-note {{Division by zero}} \
+                        // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_of_modulo
+
+namespace test_tracking_of_assignment {
+  int f(int x) {
+    bool p0 = x < 0;    // expected-note {{Assuming 'x' is >= 0}} \
+                        // expected-note {{'p0' initialized to 0}}
+    int div = 1;
+    div *= p0;          // expected-note {{The value 0 is assigned to 'div'}}
+    return 1 / div;     // expected-note {{Division by zero}} \
+                        // expected-warning {{Division by zero}}
+  }
+} // namespace test_tracking_of_assignment

clang/test/Analysis/nullptr.cpp

 void zoo1backwards() {
   char **p = 0; // expected-note{{'p' initialized to a null pointer value}}
   delete *(0 + p); // expected-warning{{Dereference of null pointer}}
                    // expected-note@-1{{Dereference of null pointer}}
 }
 
 typedef __INTPTR_TYPE__ intptr_t;
 void zoo1multiply() {
-  char **p = 0; // FIXME-should-be-note:{{'p' initialized to a null pointer value}}
+  char **p = 0; // expected-note{{'p' initialized to a null pointer value}}
   delete *((char **)((intptr_t)p * 2)); // expected-warning{{Dereference of null pointer}}
                    // expected-note@-1{{Dereference of null pointer}}
 }
 
 void zoo2() {
   int **a = 0;
   int **b = 0; // expected-note{{'b' initialized to a null pointer value}}
   asm ("nop"