[analyzer] Copy and move constructors - ExprEngine extended for "almost trivial" copy and move constructors

[baloghadamsoftware]

Summary

Many classes (e.g. in common stl implementations) contain user-written copy and move constructors that are identical to the implicit ones. This far ExprEngine could only handle the official "trivial" case. This patch extends ExprEngine for copy and move constructors that are user provided but in all other aspects they are the same as trivial ones.

A typical example is the GNU implementation of the iterator of std::deque, where the user provided copy constructor of the non-const version also accepts an instance of the const version as parameter. This patch allows correct simulation of this iterator.

[xazax.hun]

Note that, once a constructor body is not available, we will conservatively treat it as nontrivial. This is not the case however for most of the templated code. Since the STL use templates heavily I think this patch is a great step forward in improving the modeling of C++ code.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

39

These two functions only used in this translation unit right? Maybe it would be better to make them static.

59

nit: need spaced around the operator.

65

Isn't this only applicable to ctors? Maybe you should reflect this in the name or change the type of the parameter accordingly.

69

Please document that, in case we do not see the body of a ctor, we treat it conservatively as non trivial. (hasTrivialBody returns false when the body is not available)

90

Maybe you could reduce the indentation if you use "early continue" here.

111

What types do we want to exclude and why? It might be a good idea to document them.

114

Instead of the O(n^2) algorithm, it might be better to just iterate through the initializers, and put each field into a llvm small pointer set, or something like that. Afterwards you can iterate through the fields of the struct and check whether each field is inside the set. This might be both more efficient and cleaner.

[baloghadamsoftware]

Revised version based on comments.

[a.sidorin]

test/Analysis/ctor.mm

179

Seems like we may lose some warnings due to this change. Did you test this change on some real code?

[baloghadamsoftware]

test/Analysis/ctor.mm

179

Sorry, but no. We got rid of a false positive (debug checker?). The member of the new object are no longer undefined since we do a trivial copy here because this copy constructor is "almost trivial".

[a.sidorin]

Adam,

It is not a debug checker. It is UndefinedAssignment checker which correctly tells us that Inner.y is assigned with an uninitialized value while copying. So I wonder if we are allowed to skip such warnings because these warnings don't look like false positives.
As I understand, these warnings disappeared because performTrivialCopy() doesn't run checkers for check::Bindevent. Not sure but maybe we should fix that?

[baloghadamsoftware]

Now I made a thorough check. Indeed, with the original version we get a warning because Other.y is not initialized. CheckerManager::runCheckersForBind() is called here during the default evaluation of the call. I tried to call the same function in performTrivialCopy, but without success, all members on the right hand side object are "Unknown" so no warnings are given. It seems like arguments are not bound to paremeters without executing evalCall(). I tried to copy some part of inlineCall(), but it did not help either. It seems evaluation of bindings in the constructor initializer list is strongly connected to its default evaluation.

[NoQ]

I see what's going on.

performTrivialCopy() already calls evalBind(), which in turn calls runCheckersForBind(), so no effort is needed there.

However, the bind event itself is now different - instead of a separate event for every bind, you're having only one event for binding the nonloc::LazyCompoundVal.

For example, in testNonPODWrapper (which calls the test on line 177), you used to have one bind of an UndefinedVal into w2.p.x (which produced the warning) and one bind of 1 S32b into w2.p.y, which didn't produce the warning. But now you're having just one bind event of lazyCompoundVal{0x7fb5b80ef3b8,w} into w2. By unpacking the compound value's store, you could see that w.p.y in it contains an undefined value (though you wouldn't see it in the store's dump directly, the StoreManager would produce one for you when you ask for it).

At a glance, this might be worth fixing on the checker's side. Essentially, that might still be a problem when truly-trivial (as opposed to almost-trivial) copies are performed, so i guess the checker might need fixing regardless.

Dropping such warnings is also a viable option. We can think of this warning as false, because perhaps the purpose of this code was to ensure that at least w2.p.y is initialized.

But if w was completely unitialized (that is, LCV contained only uninitialized values in its store in the cluster defined by its parent region), then the warning should be useful. So i'm also having this feature request for all Undefined* checkers - perhaps not only consider straightforward undefined values, but also passing uninitialized structures by value or by const pointer/reference?

[baloghadamsoftware]

I agree with you. Do I have to modify the checker (in a separate patch), or someone else can do it? I do not know how difficult it is to unpack the store of a LazyCompoundVal (it probably has to be done recursively).

[NoQ]

Hmm. I suggest:

1. Change this test's constructor so that it was no longer almost-trivial. Because it isn't significant for this test if the constructor is almost-trivial or not. The test would pass.

2. Add a FIXME-test for this checker, in which a completely undefined structure is being copied. Perhaps somebody implements this feature some day.

3. Leave out the situation that the current test checks as a grey-area. I'm still not convinced that this situation (copying a partially-initialized almost-trivial structure) deserves a warning from this checker.

Does this make any sense? :)

[baloghadamsoftware]

In D22374#504855, @NoQ wrote:

Hmm. I suggest:

1. Change this test's constructor so that it was no longer almost-trivial. Because it isn't significant for this test if the constructor is almost-trivial or not. The test would pass.

It is significant, because I want to test here the almost-trivial constructors.

2. Add a FIXME-test for this checker, in which a completely undefined structure is being copied. Perhaps somebody implements this feature some day.

So it would be a new function with the same structure, and commented out beginning with a FIXME?

3. Leave out the situation that the current test checks as a grey-area. I'm still not convinced that this situation (copying a partially-initialized almost-trivial structure) deserves a warning from this checker.

This is what I originally did here in the patch. Maybe a FIXME could be written there a well?

[NoQ]

In D22374#505672, @baloghadamsoftware wrote:

In D22374#504855, @NoQ wrote:

Hmm. I suggest:

1. Change this test's constructor so that it was no longer almost-trivial. Because it isn't significant for this test if the constructor is almost-trivial or not. The test would pass.

It is significant, because I want to test here the almost-trivial constructors.

I mean, the positive in Inner::Inner(), which has regressed, was written long before the notion of "almost-trivial constructor" was introduced by you. So it shouldn't be a problem if we modify this test to let the constructor become non-almost-trivial; that wasn't the purpose of that particular test.

And we could create another test with almost-trivial constructor elsewhere, which would prove the usefulness of your patch.

2. Add a FIXME-test for this checker, in which a completely undefined structure is being copied. Perhaps somebody implements this feature some day.

So it would be a new function with the same structure, and commented out beginning with a FIXME?

Yeah, that's what i thought - not completely commented out, just having an opposite expected-warning <=> no-warning, and a "FIXME: we should (not) warn here because *some hand-waving*". There are a few such tests around.

3. Leave out the situation that the current test checks as a grey-area. I'm still not convinced that this situation (copying a partially-initialized almost-trivial structure) deserves a warning from this checker.

This is what I originally did here in the patch. Maybe a FIXME could be written there a well?

I think this test should still test what it used to test - i've a feeling it's ok if we modify the part of it that was not related to what it used to test, but i'm feeling bad about removing it completely.

Essentially, this plan of mine has the sole purpose of keeping my (and perhaps somebody else's) conscience from biting me for removing the test; it seems that simpler approaches seem to carry more of the "no-no, this shouldn't happen" feeling. I guess i could post a patch-over-a-patch if what i'm expressing isn't clear.

[baloghadamsoftware]

In D22374#506098, @NoQ wrote:

I guess i could post a patch-over-a-patch if what i'm expressing isn't clear.

I think this would be the best :-)

[NoQ]

Something like this, what do you think?:

TestAlmostNonPOD.patch3 KBDownload

[NoQ]

Ping!~ Did my idea sound completely wrong to you? :)

Does D25660 depend on this patch? And/or did you find another workaround?

upd.: I also thought that this deserves more code comments - the purpose of the new mechanism should be more obvious by reading the code.

[baloghadamsoftware]

In D22374#575579, @NoQ wrote:

Ping!~ Did my idea sound completely wrong to you? :)

Does D25660 depend on this patch? And/or did you find another workaround?

upd.: I also thought that this deserves more code comments - the purpose of the new mechanism should be more obvious by reading the code.

Sorry, since it turned out that D25660 does not depend on this patch I downprioritized it.

By some mistake I missed the notification about your patch-over-patch. It seems OK to me.

[baloghadamsoftware]

DO I have to apply your path over patch and update the diff?

[baloghadamsoftware]

Tests updated.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/Basic/PrettyStackTrace.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 
+#include "llvm/ADT/SmallPtrSet.h"
+
 using namespace clang;
 using namespace ento;
 
 void ExprEngine::CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
                                           ExplodedNode *Pred,
                                           ExplodedNodeSet &Dst) {
   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
   const Expr *tempExpr = ME->GetTemporaryExpr()->IgnoreParens();
   ProgramStateRef state = Pred->getState();
   const LocationContext *LCtx = Pred->getLocationContext();
 
   state = createTemporaryRegionIfNeeded(state, LCtx, tempExpr, ME);
   Bldr.generateNode(ME, Pred, state);
 }
 
+static bool isCopyOrMoveLike(const CXXConstructorDecl *Constr) {
+  if (Constr->isCopyOrMoveConstructor())
+    return true;
+
+  if (Constr->getNumParams() != 1)
+    return false;
+
+  const auto ParamType =
+      Constr->getParamDecl(0)->getType()->getUnqualifiedDesugaredType();
+  if (!ParamType->isReferenceType())
+    return false;
+
+  const auto ParamPointeeType =
+      ParamType->getAs<ReferenceType>()->getPointeeType();
+  if (!ParamPointeeType->isRecordType())
+    return false;
+
+  const auto *ParamRecDecl = ParamPointeeType->getAs<RecordType>()->getDecl();
+  const auto *ThisRecDecl = Constr->getParent();
+
+  if (ParamRecDecl != ThisRecDecl)
+    return false;
+
+  return true;
+}
+
+static bool isAlmostTrivialConstructor(const CXXMethodDecl *Met) {
+  if (Met->isTrivial())
+    return true;
+
+  if (!Met->hasTrivialBody()) // Returns false if body is not available
+    return false;
+
+  if (Met->getNumParams() != 1)
+    return false;
+
+  const auto *Param = Met->getParamDecl(0);
+  const auto *ThisRecDecl = Met->getParent();
+
+  const auto *Constr = dyn_cast<CXXConstructorDecl>(Met);
+  if (!Constr)
+    return false;
+
+  if (ThisRecDecl->getNumVBases() > 0)
+    return false;
+
+  llvm::SmallPtrSet<const Type *, 32> InitBaseSet;
+  llvm::SmallPtrSet<const FieldDecl *, 32> InitFieldSet;
+
+  for (const auto *Initzer : Constr->inits()) {
+    if (Initzer->isBaseInitializer()) {
+      const auto *Base = Initzer->getBaseClass();
+      if (const auto *CtrCall = dyn_cast<CXXConstructExpr>(
+              Initzer->getInit()->IgnoreParenImpCasts())) {
+        if (!isCopyOrMoveLike(CtrCall->getConstructor()) ||
+            !isAlmostTrivialConstructor(CtrCall->getConstructor()))
+          return false;
+        if (const auto *Init = dyn_cast<DeclRefExpr>(
+                CtrCall->getArg(0)->IgnoreParenImpCasts())) {
+          if (Init->getDecl() != Param)
+            return false;
+        } else {
+          return false;
+        }
+      } else {
+        return false;
+      }
+      InitBaseSet.insert(Base);
+    } else if (Initzer->isMemberInitializer()) {
+      const auto *Field = Initzer->getMember();
+      const MemberExpr *InitMem;
+      if (Field->getType()->isScalarType()) {
+        InitMem =
+            dyn_cast<MemberExpr>(Initzer->getInit()->IgnoreParenImpCasts());
+      } else {
+        if (const auto *CtrCall = dyn_cast<CXXConstructExpr>(
+                Initzer->getInit()->IgnoreParenImpCasts())) {
+          if (!isCopyOrMoveLike(CtrCall->getConstructor()) ||
+              !isAlmostTrivialConstructor(CtrCall->getConstructor()))
+            return false;
+          InitMem =
+              dyn_cast<MemberExpr>(CtrCall->getArg(0)->IgnoreParenImpCasts());
+        } else {
+          return false;
+        }
+      }
+      if (!InitMem)
+        return false;
+      if (InitMem->getMemberDecl() != Field)
+        return false;
+      if (const auto *Base = dyn_cast<DeclRefExpr>(InitMem->getBase())) {
+        if (Base->getDecl() != Param)
+          return false;
+      } else {
+        return false;
+      }
+      InitFieldSet.insert(Field);
+    }
+  }
+
+  for (const auto Base : ThisRecDecl->bases()) {
+    if (Base.getType()->getAsCXXRecordDecl()->field_empty())
+      continue;
+    if (!InitBaseSet.count(&*Base.getType()))
+      return false;
+  }
+
+  for (const auto *Field : ThisRecDecl->fields()) {
+    if (!Field->getType()->isScalarType() && !Field->getType()->isRecordType())
+      return false;
+    if (!InitFieldSet.count(Field))
+      return false;
+  }
+
+  return true;
+}
+
 // FIXME: This is the sort of code that should eventually live in a Core
 // checker rather than as a special case in ExprEngine.
 void ExprEngine::performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred,
                                     const CallEvent &Call) {
   SVal ThisVal;
   bool AlwaysReturnsLValue;
   if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) {
-    assert(Ctor->getDecl()->isTrivial());
-    assert(Ctor->getDecl()->isCopyOrMoveConstructor());
+    assert(isAlmostTrivialConstructor(Ctor->getDecl()));
+    assert(isCopyOrMoveLike(Ctor->getDecl()));
     ThisVal = Ctor->getCXXThisVal();
     AlwaysReturnsLValue = false;
   } else {
-    assert(cast<CXXMethodDecl>(Call.getDecl())->isTrivial());
+    assert(isAlmostTrivialConstructor(cast<CXXMethodDecl>(Call.getDecl())));
     assert(cast<CXXMethodDecl>(Call.getDecl())->getOverloadedOperator() ==
            OO_Equal);
     ThisVal = cast<CXXInstanceCall>(Call).getCXXThisVal();
     AlwaysReturnsLValue = true;
   }
 
   const LocationContext *LCtx = Pred->getLocationContext();
 
void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE,
   ExplodedNodeSet DstPreCall;
   getCheckerManager().runCheckersForPreCall(DstPreCall, PreInitialized,
                                             *Call, *this);
 
   ExplodedNodeSet DstEvaluated;
   StmtNodeBuilder Bldr(DstPreCall, DstEvaluated, *currBldrCtx);
 
   bool IsArray = isa<ElementRegion>(Target);
-  if (CE->getConstructor()->isTrivial() &&
-      CE->getConstructor()->isCopyOrMoveConstructor() &&
-      !IsArray) {
+  if (isAlmostTrivialConstructor(CE->getConstructor()) &&
+      isCopyOrMoveLike(CE->getConstructor()) && !IsArray) {
     // FIXME: Handle other kinds of trivial constructors as well.
     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
          I != E; ++I)
       performTrivialCopy(Bldr, *I, *Call);
 
   } else {
     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
          I != E; ++I)

test/Analysis/ctor.mm

namespace PODUninitialized {
   class NonPOD {
   public:
     int x, y;
 
     NonPOD() {}
     NonPOD(const NonPOD &Other)
       : x(Other.x), y(Other.y) // expected-warning {{undefined}}
     {
+      int z = 1;
     }
     NonPOD(NonPOD &&Other)
     : x(Other.x), y(Other.y) // expected-warning {{undefined}}
     {
+      int z = 1;
     }
 
     NonPOD &operator=(const NonPOD &Other)
     {
       x = Other.x;
       y = Other.y; // expected-warning {{undefined}}
       return *this;
     }
     NonPOD &operator=(NonPOD &&Other)
     {
       x = Other.x;
       y = Other.y; // expected-warning {{undefined}}
       return *this;
     }
   };
 
   class NonPODWrapper {
   public:
     class Inner {
     public:
       int x, y;
 
       Inner() {}
       Inner(const Inner &Other)
         : x(Other.x), y(Other.y) // expected-warning {{undefined}}
       {
+        int z = 1;
       }
       Inner(Inner &&Other)
       : x(Other.x), y(Other.y) // expected-warning {{undefined}}
       {
+        int z = 1;
       }
 
       Inner &operator=(const Inner &Other)
       {
         x = Other.x; // expected-warning {{undefined}}
         y = Other.y;
         return *this;
       }
       Inner &operator=(Inner &&Other)
       {
         x = Other.x; // expected-warning {{undefined}}
         y = Other.y;
         return *this;
       }
     };
 
     Inner p;
   };
 
+  class AlmostPOD {
+  public:
+    int x, y;
+
+    AlmostPOD() {}
+    AlmostPOD(const AlmostPOD &Other)
+      : x(Other.x), y(Other.y) // no-warning
+    {}
+    AlmostPOD(AlmostPOD &&Other)
+    : x(Other.x), y(Other.y) // no-warning
+    {}
+  };
+
   void testPOD(const POD &pp) {
     POD p;
     p.x = 1;
     POD p2 = p; // no-warning
     clang_analyzer_eval(p2.x == 1); // expected-warning{{TRUE}}
     POD p3 = move(p); // no-warning
     clang_analyzer_eval(p3.x == 1); // expected-warning{{TRUE}}
 
namespace PODUninitialized {
   }
 
   void testNonPODWrapperMove() {
     NonPODWrapper w;
     w.p.y = 1;
     NonPODWrapper w2 = move(w);
   }
 
+  void testAlmostPOD() {
+    AlmostPOD p;
+    p.x = 1;
+    AlmostPOD p2 = p; // no-warning
+    clang_analyzer_eval(p2.x == 1); // expected-warning{{TRUE}}
+  }
+
+  void testAlmostPODMove() {
+    AlmostPOD p;
+    p.x = 1;
+    AlmostPOD p2 = move(p); // no-warning
+    clang_analyzer_eval(p2.x == 1); // expected-warning{{TRUE}}
+  }
+
+  // FIXME: These copies are now handled with a single per-structure bind,
+  // and the undefined assignment checker fails to realize that
+  // all contents of the structure that's being copied are undefined.
+  // Perhaps we could teach the checker to warn here.
+  void testCompletelyUndefined() {
+    POD p;
+    POD p2 = p; // no-warning
+    AlmostPOD ap;
+    AlmostPOD ap2 = ap; // no-warning
+  }
+
   // Not strictly about constructors, but trivial assignment operators should
   // essentially work the same way.
   namespace AssignmentOperator {
     void testPOD() {
       POD p;
       p.x = 1;
       POD p2;
       p2 = p; // no-warning