[analyzer] Track trivial copy/move constructors and initializer lists in the BugReporter

[isuckatcs]

Summary

1.) Constructors

Prior to this patch, if an object had a trivial copy/move constructor we couldn't track
a value further than the copy constructor invocation. The problem is that in such cases
the analyzer doesn't inline the constructor, but performs a trivial copy instead. A trivial
copy means, we just copy the values from one place to another.

This patch handles this case by matching the regions of the 2 objects involved in the
construction, and tracks the appropriate region.

2.) Initializer lists

Prior to this patch we ignored initializer lists.

This patch handles them up to some extent.

[NoQ]

Great! Sounds like the conspiracy to not work with constructors goes deeper than I thought.

The new behavior looks lovely, I heavily recommend adding these examples as -analyzer-output=text tests.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

2505

Hmmm so you're tracking *all* arguments. I'm worried that this will cause you to track values that aren't necessarily relevant to the report.

These notes are difficult to judge because it's usually important to maintain balance, too little information and the report becomes incomprehensible, too much information and people won't be able to navigate it. So we're only tracking things that are directly relevant (and we're trying our best to identify them).

For example, in this slightly more complicated case

int foo() {
    int *x = nullptr, *y = nullptr;
    S s{x, y};
    auto [a, b] = s;

    return *b;
}

we should ideally track the null pointer back to declaration of y but not x. A good long-term solution for that would probably be to track the individual *field* inside s (until we reach the field's initializer). I'm not sure how good are we at that right now, but I also don't immediately see any shortcuts that we could take here hmmm.

[isuckatcs]

• Addressed a comment
• Handling initializer lists.

I will add tests later.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

2505

What I can do is finding the field the value belongs to and extract it's initializer expression. Then mark that as the initializer instead of the constructor.

The problem we face here is that the bug reporter checks the statements inside the exploded nodes. If the field initializer is not in the egraph, the bug reporter won't be able to track it.

In the snippet above ExprEngine::performTrivialCopy() is called, so the copy constructor is not inlined, hence the field initializer expressions are not in the CFG.

As a result if the constructor is not inlined, there's no way to tell which argument to track. It's either all or none. Also initializer lists aren't handled either, so in case of S s{x, y} neither x nor y would be tracked.

[isuckatcs]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

2505

expressions are not in the CFG.

I meant egraph here instead of CFG.

[isuckatcs]

Updated

[NoQ]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

2505

Aha interesting.

Every time BugReporter doesn't have enough information to reverse-engineer what ExprEngine has done, ExprEngine can leave breadcrumbs to help BugReporter figure out what happened. One mechanism we have for that is ProgramPointTag. You can either add a simple tag that BugReporter can pattern-match, or the modern solution is NoteTag that can replace entire bug visitors (but it's probably hard to integrate with an existing visitor).

Then again, performTrivialCopy() isn't the typical case. If we handle the typical case (i.e., add a non-trivial copy constructor to the test and handle that), that'd already be an improvement.

[isuckatcs]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

2505

If we handle the typical case (i.e., add a non-trivial copy constructor to the test and handle that), that'd already be an improvement.

I'm handling one element copy constructors and initializer list, so for some simple snippets there are improvements.

E.g.:

struct S {
    int *a, *b;

    S(int *_a, int *_b) : a{_a}, b{_b} {}
};

void foo() {
    int *x = nullptr, *y = nullptr;

    S s{x, y};

    int i = *s.a;
}

The output before the patch:

test.cpp:12:7: note: Calling constructor for 'S'
    S s{x, y};
      ^~~~~~~
test.cpp:5:27: note: Null pointer value stored to 's.a'
    S(int *_a, int *_b) : a{_a}, b{_b} {}
                          ^
test.cpp:12:7: note: Returning from constructor for 'S'
    S s{x, y};
      ^~~~~~~
test.cpp:14:13: note: Dereference of null pointer (loaded from field 'a')
    int i = *s.a;
            ^  ~

The output after it:

test.cpp:10:10: note: 'x' initialized to a null pointer value
    int *x = nullptr, *y = nullptr;
         ^
test.cpp:12:9: note: Passing null pointer value via 1st parameter '_a'
    S s{x, y};
        ^
test.cpp:12:7: note: Calling constructor for 'S'
    S s{x, y};
      ^~~~~~~
test.cpp:5:27: note: Null pointer value stored to 's.a'
    S(int *_a, int *_b) : a{_a}, b{_b} {}
                          ^
test.cpp:12:7: note: Returning from constructor for 'S'
    S s{x, y};
      ^~~~~~~
test.cpp:14:13: note: Dereference of null pointer (loaded from field 'a')
    int i = *s.a;
            ^  ~

We can reach x because _a is tracked in the initializer list at a{_a}.

I think one solution would be to store somewhere where we started to track an expression and
where we ended it. Later when we encounter an initializer list or a constructor we can match the
parameters or the field initializers with the already tracked expressions and if we find a match
we know which value to track.

[isuckatcs]

New strategy for implicit copy/move ctor tracking.

Initializer lists are still not handled.

[isuckatcs]

• Progressed with initializer lists.
• Added more tests.

[xazax.hun]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1419

Nit: we have isCopyOrMoveConstructor.

1592

I think either the comment or the code might need to be updated. Trivial and user defined are not mutually exclusive terms.
Consider:

struct X {
  std::vector<int> v;
};

The copy constructor of X is neither trivial nor user provided.

[isuckatcs]

Rewrote from scratch

[isuckatcs]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1453–1454

This is still buggy and can result in false positives, so it's commented out for now. If we don't want to handle this situation, this will be removed.

[isuckatcs]

Updated

[isuckatcs]

Updated initializer list handling

[NoQ]

The current patch looks good to me, it matches my understanding of the problem. Excellent work!

There seem to be more loose ends to cover but I think it's better to commit this patch as-is, as a strict improvement, and follow-up later if you have time. Maybe leave comments for future generations to know where to look for trouble!

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1437

I suspect that another possibility is ElementRegion for initializer lists that define arrays. Maybe leave a FIXME to look into that?

On the other hand, isa<InitListExpr>(E) sounds like it could become the type of variable E, to promote a runtime check to a compile-time check.

1453

Nitpick: The coding convention recommends against using auto when the type isn't obvious from the initializer. "Initializer" doesn't necessarily refer to an expression (could be like CXXCtorInitializer).

1500–1502

This probably needs another recursive descend, eg. if we track a.y.e and encounter S a = b then we need to track b.y.e.

Maybe leave a fixme?

[isuckatcs]

Addressed comments

[xazax.hun]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1451

I am a bit anxious about this matching. It probably works ok for most types, but consider a class like:

struct Common { int x; };

struct Inner {
  Common c;
};

struct S {
  Common c;
  Inner;
};

The type Common can be found at multiple levels. Would we ever confuse S::Common with S::Inner::Common? When we see a FieldRegion for Common:x, we would have a match twice. What guarantees that we always pick the right one? Or do I miss something?

Fortunately, picking the wrong one might not result in a wrong warning text, as subsequent matching might end up failing.

1475–1494

I feel like the code here is almost identical to the one at the beginning. Is it possible to extract this to a lambda and call it twice?

1483

I wonder whether top-level is ambiguous. Some people might think of s as the top level. How about innermost?

[isuckatcs]

Addressed comments

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1451

Would we ever confuse S::Common with S::Inner::Common?

Consider this snippet that uses the structs you created above with Inner i and int *x.

int *x = nullptr, *y = nullptr;
S s{x, y};

int a = *s.i.c.x;

The region we track in this case is s.i.c.x. The InitListExpr is

InitListExpr 'S':'struct S'
|-InitListExpr 'Common':'struct Common'
| `-ImplicitCastExpr 'int *' <LValueToRValue>
|   `-DeclRefExpr 'int *' lvalue Var  'x' 'int *'
`-InitListExpr 'Inner':'struct Inner'
  `-InitListExpr 'Common':'struct Common'
    `-ImplicitCastExpr 'int *' <LValueToRValue>
      `-DeclRefExpr 'int *' lvalue Var 'y' 'int *'

The type of this InitListExpr is RecordType 'struct S', so we first move up the regions
until we hit one with a matching type, which is s. Then we start moving back down the
regions and now the InitListExpr too, always choosing the sub-expression that matches
the index of the region.

So basically the functions always searches for the initializers top-down based on the field
indices, so I think if it confuses 2 regions, we made a mistake somewhere else.

Also I've reworked this function to be iterative and less confusing.

[NoQ]

LGTM as long as other reviewers are happy!

[martong]

Thanks, you have nice tests with good coverage! LGTM!

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

static void showBRDefaultDiagnostics(llvm::raw_svector_ostream &OS,
   }
 
   if (HasSuffix) {
     OS << " to ";
     SI.Dest->printPretty(OS);
   }
 }
 
+static bool isTrivialCopyOrMoveCtor(const CXXConstructExpr *CE) {
+  if (!CE)
+    return false;
+
+  const auto *CtorDecl = CE->getConstructor();
+
+  return (CtorDecl->isCopyConstructor() || CtorDecl->isMoveConstructor()) &&
+         CtorDecl->isTrivial();
+}
+
 PathDiagnosticPieceRef StoreSiteFinder::VisitNode(const ExplodedNode *Succ,
                                                   BugReporterContext &BRC,
                                                   PathSensitiveBugReport &BR) {
   if (Satisfied)
     return nullptr;
 
   const ExplodedNode *StoreSite = nullptr;
   const ExplodedNode *Pred = Succ->getFirstPred();
   const Expr *InitE = nullptr;
   bool IsParam = false;
 
   // First see if we reached the declaration of the region.
   if (const auto *VR = dyn_cast<VarRegion>(R)) {
     if (isInitializationOfVar(Pred, VR)) {
       StoreSite = Pred;
       InitE = VR->getDecl()->getInit();
     }
   }
 
   // If this is a post initializer expression, initializing the region, we
   // should track the initializer expression.
   if (Optional<PostInitializer> PIP = Pred->getLocationAs<PostInitializer>()) {
     const MemRegion *FieldReg = (const MemRegion *)PIP->getLocationValue();
     if (FieldReg == R) {
       StoreSite = Pred;
       InitE = PIP->getInitializer()->getInit();
     }
   }
 
   // Otherwise, see if this is the store site:
   // (1) Succ has this binding and Pred does not, i.e. this is
   //     where the binding first occurred.
   // (2) Succ has this binding and is a PostStore node for this region, i.e.
   //     the same binding was re-assigned here.
   if (!StoreSite) {
     if (Succ->getState()->getSVal(R) != V)
       return nullptr;
 
     if (hasVisibleUpdate(Pred, Pred->getState()->getSVal(R), Succ, V)) {
       Optional<PostStore> PS = Succ->getLocationAs<PostStore>();
       if (!PS || PS->getLocationValue() != R)
         return nullptr;
     }
 
     StoreSite = Succ;
 
     // If this is an assignment expression, we can track the value
     // being assigned.
-    if (Optional<PostStmt> P = Succ->getLocationAs<PostStmt>())
+    if (Optional<PostStmt> P = Succ->getLocationAs<PostStmt>()) {
       if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>())
         if (BO->isAssignmentOp())
           InitE = BO->getRHS();
+    }
+
+    // We reached a copy/move constructor that hasn't been inlined (most likely
+    // because of ExprEngine::performTrivialCopy()). The idea is to track the
+    // value back to the first constructor call.
+    //
+    // Note that the copy/move constructors can be chained, so
+    // in that case we also track one constructor back to the other one.
+    // E.g.:
+    //
+    //  struct S {
+    //    int *a, *b;
+    //    S(int *a, int *b) : p1(a), p2(b) {}
+    //  };
+    //
+    //  void foo() {
+    //    int *x = nullptr, *y = nullptr;
+    //
+    //    S s(x, y);
+    //    S s2 = s;
+    //    S s3 = s2;      <-- here we track 's3.p1' all
+    //                        the way back to 's.p1' and
+    //                        launch a separate tracker
+    //                        to see where s2 comes from
+    //
+    //    int i = *s3.p1; <-- null dereference here
+    //  }
+    //
+    if (const auto *CE =
+            dyn_cast_or_null<CXXConstructExpr>(Succ->getStmtForDiagnostics())) {
+      const MemRegion *Reg = R;
+      const ExplodedNode *N = Succ;
+
+      // If the copy or move constructor is user defined it will be inlined and
+      // handled elsewhere.
+      while (isTrivialCopyOrMoveCtor(CE)) {
+        const auto *FR = dyn_cast<FieldRegion>(Reg);
+
+        if (!FR) {
+          N = nullptr;
+          break;
+        }
+
+        // Look up the value in the origin object.
+        auto OriginObject = CE->getArg(0);
+        auto OriginVal =
+            N->getState()->getSVal(OriginObject, N->getLocationContext());
+        auto OriginFieldVal =
+            N->getState()->getLValue(FR->getDecl(), OriginVal);
+        Reg = OriginFieldVal.getAsRegion();
+
+        // Find the node where the value in the origin object was initialized.
+        N = N->getFirstPred();
+        while (N && N->getState()->getSVal(Reg) == V)
+          N = N->getFirstPred();
+
+        if (!N)
+          break;
+
+        // Track the object, we copied or moved from.
+        CE = dyn_cast<CXXConstructExpr>(N->getStmtForDiagnostics());
+        getParentTracker().track(OriginVal, OriginVal.getAsRegion(), Options);
+      }
+
+      if (N)
+        InitE = dyn_cast<Expr>(N->getStmtForDiagnostics());
+    }
 
     // If this is a call entry, the variable should be a parameter.
     // FIXME: Handle CXXThisRegion as well. (This is not a priority because
     // 'this' should never be NULL, but this visitor isn't just for NULL and
     // UndefinedVal.)
     if (Optional<CallEnter> CE = Succ->getLocationAs<CallEnter>()) {
       if (const auto *VR = dyn_cast<VarRegion>(R)) {
 
if (InitE) {
     getParentTracker().track(InitE, StoreSite, Options);
   }
 
   // Let's try to find the region where the value came from.
   const MemRegion *OldRegion = nullptr;
 
   // If we have init expression, it might be simply a reference
   // to a variable, so we can use it.
   if (InitE) {
     // That region might still be not exactly what we are looking for.
     // In situations like `int &ref = val;`, we can't say that
     // `ref` is initialized with `val`, rather refers to `val`.
     //
     // In order, to mitigate situations like this, we check if the last
     // stored value in that region is the value that we track.
     //
     // TODO: support other situations better.
const auto track = [&CombinedResult, &Parent, ExprNode, Opts](Expr *Inner) {
       CombinedResult.combineWith(Parent.track(Inner, ExprNode, Opts));
     };
 
     if (BO->getOpcode() == BO_Mul) {
       if (LHSV.isZeroConstant())
         track(BO->getLHS());
       if (RHSV.isZeroConstant())
         track(BO->getRHS());
       } else { // Track only the LHS of a division or a modulo.
         if (LHSV.isZeroConstant())
           track(BO->getLHS());
       }
 
       return CombinedResult;
   }
 };
 
 Tracker::Tracker(PathSensitiveBugReport &Report) : Report(Report) {
   // Default expression handlers.
   addLowPriorityHandler<ControlDependencyHandler>();
   addLowPriorityHandler<NilReceiverHandler>();
   addLowPriorityHandler<ArrayIndexHandler>();
   addLowPriorityHandler<InterestingLValueHandler>();
   addLowPriorityHandler<InlinedFunctionCallHandler>();

clang/test/Analysis/ctor-bug-path.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-output=text -verify %s
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+namespace copyMoveTrack {
+struct S {
+  int *p1, *p2;
+  S(int *a, int *b) : p1(a), p2(b) {}
+};
+
+void foo() {
+  int *x = nullptr, *y = nullptr; //expected-note{{'x' initialized to a null pointer value}}
+
+  S s(x, y); //expected-note{{'s' initialized here}}
+  // expected-note@-1{{Passing null pointer value via 1st parameter 'a'}}
+  S s2 = s; //expected-note{{'s2' initialized here}}
+  S s3 = s2; //expected-note{{'s3' initialized here}}
+  S s4 = std::move(s3); //expected-note{{'s4' initialized here}}
+  S s5 = s4; // expected-note{{Null pointer value stored to 's5.p1'}}
+
+  int i = *s5.p1; // expected-warning{{Dereference of null pointer}}
+  // expected-note@-1{{Dereference of null pointer}}
+
+  (void) i;
+}
+} // namespace copyMoveTrack