[analyzer] Fix static_cast on pointer-to-member handling

[RedDocMD]

Summary

This commit fixes bug #48739. The bug was caused by the way static_casts
on pointer-to-member caused the CXXBaseSpecifier list of a
MemberToPointer to grow instead of shrink.
The list is now grown by implicit casts and corresponding entries are
removed by static_casts. No-op static_casts cause no effect.

[vsavchenko]

Thanks for taking your time and getting to the root cause of it!

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

209

std::list is like the slowest container, and it should be avoided in almost every case.
Considering the semantics of it, you can definitely use llvm::SmallVector.

222

llvm::find_if with a lambda capturing PathBase?

223

It's better to be more verbose in the assertions.
Additionally, I'm not sure that it is clear what it is all about because pointer-to-members do not have base specifiers.

224

In order to avoid removals from the middle, you can use a more functional approach to collections and iterators and use llvm::make_filter_range and iterate over it in the loop below,

clang/test/Analysis/pointer-to-member.cpp

304

What about other type of casts?

[RedDocMD]

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

223

Well, the PointerToMember contains a PointerToMemberData, which has a list of CXXBaseSpecifier. Should I put something like: "PointerToMemberData has insufficient number of base specifiers"?

[RedDocMD]

Remoevd the use of std::list with llvm::SmallVector. Removed the need to delete elements.

[RedDocMD]

Made assertion more verbose

[RedDocMD]

@vsavchenko could you please see the current logic if it is better now?

clang/test/Analysis/pointer-to-member.cpp

304

I am looking into this.

[vsavchenko]

Also, all these PathRange and PathList don't really reflect what they stand for semantically and talk more about implementation. It's not the problem of this patch, but it doesn't make your logic easier to comprehend.

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

224

I think it's all a bit too complicated now.

Right now you have two nested loops:

1. over PathRange
2. over BaseList (in find_if)

It won't be a problem to put them in another order, so when you make a filter_range, you can have llvm::find_if which will iterate over PathRange and captures the given BaseList element. So, yes nested lambdas.

Here is a sketch of the solution:

auto BaseListFilteredRange = llvm::make_filter_range(
    BaseList, // you don't need to make_range here, BaseList IS a range
    [&PathRange](const CXXBaseSpecifier *Base) {
      return llvm::find_if(PathRange, [Base](const auto &It) {
        return Base->getType() == It.first->getType();
      }) == PathRange.end();
    });

Aaaand while I was writing that, it got me thinking that we don't need BaseList in the first place:

for (const CXXBaseSpecifier *Base : PathList)
  if (llvm::none_of(PathRange,
                    [Base](const auto &It) { return Base->getType() == It.first->getType(); })
      PathList = CXXBaseListFactory.add(Base, PathList);

[RedDocMD]

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

224

Hmm, I really should brush up on my functional programming and think more in terms of STL/LLVM algorithms. Thank you for pointing out this solution, @vsavchenko!

One thing I noticed though, the shortened logic that you suggested removes all matching instances from PathList, while my intention was to remove only the first one of every kind. If there are no repetitions, it is the same. And, normally, repetitions should not be present in the PathList retrieved from PTM. It is a bug elsewhere if that happens. So should I add an assert for that here?

[vsavchenko]

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

224

Yes, that's true.
Assertions will usually make intensions of the original author more clear for future readers.
Plus, I think it can be also good to add a comment (something similar to your summary for this change) to describe what is going on here and WHY it is done.

clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp

531–533

BTW, it looks like this can be replaced by CastE->path()

[RedDocMD]

Cleaner implementation of the popping logic, using STL/LLVM algorithms

[RedDocMD]

@vsavchenko , I have used the logic that you suggested and put in a better assertion.

[RedDocMD]

Updated to use new function

[RedDocMD]

@vsavchenko, after some experimentation, I found out that handling reinterpret_cast will be a real pain. Consider the following:

struct Base {
	int field;
};

struct Derived : public Base {};

struct DoubleDerived : public Derived {};

struct Some {};

void f() {
	int DoubleDerived::* ddf = &Base::field;
	int Base::* bf = reinterpret_cast<int Base::*>(reinterpret_cast<int Derived::*>(reinterpret_cast<int Base::*>(ddf)));
	int Some::* sf = reinterpret_cast<int Some::*>(ddf);
	Base base;
	base.*bf;
}

The definition of bf can be handled I guess by manually discovering when to insert a sub-class or when to remove. It will require a bit of code but I guess is doable.
As for the next one, also it has to be manually worked out whether it makes sense to process this statement further and add a node to the Exploded Graph. For the example I gave I don't think it makes a lot of sense. Multiple inheritance will make the task a lot worse as far as I can tell.
Should I try to achieve this in another commit? What are your thoughts on this?

[vsavchenko]

In D95877#2542578, @RedDocMD wrote:

@vsavchenko, after some experimentation, I found out that handling reinterpret_cast will be a real pain. Consider the following:

struct Base {
	int field;
};

struct Derived : public Base {};

struct DoubleDerived : public Derived {};

struct Some {};

void f() {
	int DoubleDerived::* ddf = &Base::field;
	int Base::* bf = reinterpret_cast<int Base::*>(reinterpret_cast<int Derived::*>(reinterpret_cast<int Base::*>(ddf)));
	int Some::* sf = reinterpret_cast<int Some::*>(ddf);
	Base base;
	base.*bf;
}

The definition of bf can be handled I guess by manually discovering when to insert a sub-class or when to remove. It will require a bit of code but I guess is doable.
As for the next one, also it has to be manually worked out whether it makes sense to process this statement further and add a node to the Exploded Graph. For the example I gave I don't think it makes a lot of sense. Multiple inheritance will make the task a lot worse as far as I can tell.
Should I try to achieve this in another commit? What are your thoughts on this?

Yes, another commit is fine. However, I'd say that it is still good to add test cases with TODOs with this commit.

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

27

We don't need this anymore :)

[vsavchenko]

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

210

Containers like map and set usually return a pair for insert, where the second element tells us whether that element was inserted or was already there. It is usually a bad practice to use find in the vicinity of insert for this very reason, you double the work.

Also, a not about this whole part of the code, if it's done only for assertions, none of this code should be executed in the build without assertions. You'll need to extract this into a function that you call from assert. It means that in release builds it will be unused and should be marked with LLVM_MAYBE_UNUSED.

[RedDocMD]

Added TODO for reinterpret_cast, moved assertion code to its own block

[RedDocMD]

@vsavchenko , does it look okay now?

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

27

Wow, sharp eyes!

[vsavchenko]

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

181

nit: functions represent actions, in languages verbs act the same way, so it's recommended to use verbs in functions (hasNoRepeatedElements)

+ LLVM_MAYBE_UNUSED because in the build without assertions it would be a warning otherwise.

182

ImmutableList is one of those value types that prefers copying for clarity.

185

LLVM Coding Style calls for very limited use of auto, so here and the next line would be better with actual types.

185

Let's also reiterate on using functional-style predicates and reimplement it in terms of llvm::all_of or llvm::none_of.

220

The same thing about auto

222

No need

clang/test/Analysis/pointer-to-member.cpp

314–333

Uncomment it, and expect the actual current result. This is where TODO will come in handy.

[RedDocMD]

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

181

nit: functions represent actions, in languages verbs act the same way, so it's recommended to use verbs in functions (hasNoRepeatedElements)

+ LLVM_MAYBE_UNUSED because in the build without assertions it would be a warning otherwise.

How do I put in the LLVM_MAYBE_UNUSED? Sorry for being annoying, but ripgrepping or Googling didn't return anything.

clang/test/Analysis/pointer-to-member.cpp

314–333

Uncomment it, and expect the actual current result. This is where TODO will come in handy.

Will do it.
Just one clarification: the static analyzer tests only serve to check whether the Static Analyzer crashes or hits an assertion error, or is it something more?

[vsavchenko]

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

181

Sorry, my bad, it's LLVM_ATTRIBUTE_UNUSED

clang/test/Analysis/pointer-to-member.cpp

314–333

Mostly they check for reported results, you can see special comments like // expect-warning{...} in almost every test.

[ASDenysPetrov]

I downloaded and tested this patch. On the whole it works OK. See my suggestions below.

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

205

I suggest to use explicit types instead of auto to increase readability.

217–220

It will look clearer if we use an intermediate variable for predicate here.

225–229

We can remove else branch here and move its body out unconditionally as the main one already has return at the end.

[RedDocMD]

Some more aesthetic cleanup, added a failing test.

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

185

I couldn't do this since calling llvm::all_of (or std::all_of) on an ImmutableList causes a compile error saying that the function std::__iterator_category cannot be found for its iterator.

clang/test/Analysis/pointer-to-member.cpp

314–333

So right now we have a failing test for this, I guess its my job in the next commit to make it pass. :)

[RedDocMD]

@vsavchenko are there some more changes you want done?

[vsavchenko]

In D95877#2547303, @RedDocMD wrote:

@vsavchenko are there some more changes you want done?

I think we had a bit of misunderstanding about the test. It still should pass (we can't have broken tests, it will disrupt CI bots). Try to put the test case, so it is THERE and you CHANGE the expected outcome when the analyzer behaves correctly. Right now, as I see above, the test crashes.

[RedDocMD]

In D95877#2547949, @vsavchenko wrote:

I think we had a bit of misunderstanding about the test. It still should pass (we can't have broken tests, it will disrupt CI bots). Try to put the test case, so it is THERE and you CHANGE the expected outcome when the analyzer behaves correctly. Right now, as I see above, the test crashes.

Actually, that is the reason why I initially had commented out the crashing test. Until reinterpret_cast is properly handled, the test will crash due to an assertion failure, irrespective of what is put as the expected outcome. Is there a way to flag that a test should crash? (I see that after the tests are run, there is an expectedly-failed category). The crash is caused when the static analyzer tries to evaluate base.*bf.

[vsavchenko]

In D95877#2548021, @RedDocMD wrote:

In D95877#2547949, @vsavchenko wrote:

I think we had a bit of misunderstanding about the test. It still should pass (we can't have broken tests, it will disrupt CI bots). Try to put the test case, so it is THERE and you CHANGE the expected outcome when the analyzer behaves correctly. Right now, as I see above, the test crashes.

Actually, that is the reason why I initially had commented out the crashing test. Until reinterpret_cast is properly handled, the test will crash due to an assertion failure, irrespective of what is put as the expected outcome. Is there a way to flag that a test should crash? (I see that after the tests are run, there is an expectedly-failed category). The crash is caused when the static analyzer tries to evaluate base.*bf.

Yes, it'd be better to extract this case into a separate file and mark it as XFAIL

[RedDocMD]

Moved failing test of reinterpret_cast to its own file, marked to failx

[RedDocMD]

In D95877#2548027, @vsavchenko wrote:

Yes, it'd be better to extract this case into a separate file and mark it as XFAIL

Done that.

[RedDocMD]

@vsavchenko, anything else to add?

[vsavchenko]

Great job! Thanks for dealing with all my nit-picking!

[RKSimon]

@RedDocMD Please can you take a look at this buildbot failure: http://lab.llvm.org:8011/#/builders/124

[RedDocMD]

In D95877#2563220, @RKSimon wrote:

@RedDocMD Please can you take a look at this buildbot failure: http://lab.llvm.org:8011/#/builders/124

Yes. Thanks for the ping 😀

[davezarzycki]

The test seems to be broken on Fedora 33 (x86-64 with clang-11):

XPASS: Clang :: Analysis/reinterpret-cast-pointer-to-member.cpp (6531 of 74360)
******************** TEST 'Clang :: Analysis/reinterpret-cast-pointer-to-member.cpp' FAILED ********************
Script:
--
: 'RUN: at line 1';   /tmp/_update_lc/r/bin/clang -cc1 -internal-isystem /tmp/_update_lc/r/lib/clang/13.0.0/include -nostdsysteminc -analyze -analyzer-constraints=range -setup-static-analyzer -analyzer-checker=core,debug.ExprInspection -verify /home/dave/ro_s/lp/clang/test/Analysis/reinterpret-cast-pointer-to-member.cpp
--
Exit Code: 0

[RedDocMD]

In D95877#2563383, @davezarzycki wrote:

The test seems to be broken on Fedora 33 (x86-64 with clang-11):

XPASS: Clang :: Analysis/reinterpret-cast-pointer-to-member.cpp (6531 of 74360)
******************** TEST 'Clang :: Analysis/reinterpret-cast-pointer-to-member.cpp' FAILED ********************
Script:
--
: 'RUN: at line 1';   /tmp/_update_lc/r/bin/clang -cc1 -internal-isystem /tmp/_update_lc/r/lib/clang/13.0.0/include -nostdsysteminc -analyze -analyzer-constraints=range -setup-static-analyzer -analyzer-checker=core,debug.ExprInspection -verify /home/dave/ro_s/lp/clang/test/Analysis/reinterpret-cast-pointer-to-member.cpp
--
Exit Code: 0

Yes this has been fixed by @vsavchenko in https://github.com/llvm/llvm-project/commit/6f21adac6dd7082f7231ae342d40ed04f4885e79

[vsavchenko]

In D95877#2563383, @davezarzycki wrote:

The test seems to be broken on Fedora 33 (x86-64 with clang-11):

XPASS: Clang :: Analysis/reinterpret-cast-pointer-to-member.cpp (6531 of 74360)
******************** TEST 'Clang :: Analysis/reinterpret-cast-pointer-to-member.cpp' FAILED ********************
Script:
--
: 'RUN: at line 1';   /tmp/_update_lc/r/bin/clang -cc1 -internal-isystem /tmp/_update_lc/r/lib/clang/13.0.0/include -nostdsysteminc -analyze -analyzer-constraints=range -setup-static-analyzer -analyzer-checker=core,debug.ExprInspection -verify /home/dave/ro_s/lp/clang/test/Analysis/reinterpret-cast-pointer-to-member.cpp
--
Exit Code: 0

Hi there, is it happening after this commit?
https://github.com/llvm/llvm-project/commit/6f21adac6dd7082f7231ae342d40ed04f4885e79

clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h

public:
   }
 
   llvm::ImmutableList<const CXXBaseSpecifier *> prependCXXBase(
       const CXXBaseSpecifier *CBS,
       llvm::ImmutableList<const CXXBaseSpecifier *> L) {
     return CXXBaseListFactory.add(CBS, L);
   }
 
-  const PointerToMemberData *accumCXXBase(
-      llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
-      const nonloc::PointerToMember &PTM);
+  const PointerToMemberData *
+  accumCXXBase(llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
+               const nonloc::PointerToMember &PTM, const clang::CastKind &kind);
 
   const llvm::APSInt* evalAPSInt(BinaryOperator::Opcode Op,
                                      const llvm::APSInt& V1,
                                      const llvm::APSInt& V2);
 
   const std::pair<SVal, uintptr_t>&
   getPersistentSValWithData(const SVal& V, uintptr_t Data);
 

clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h

 /// Value representing pointer-to-member.
 ///
 /// This value is qualified as NonLoc because neither loading nor storing
 /// operations are applied to it. Instead, the analyzer uses the L-value coming
 /// from pointer-to-member applied to an object.
 /// This SVal is represented by a DeclaratorDecl which can be a member function
 /// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list
 /// is required to accumulate the pointer-to-member cast history to figure out
-/// the correct subobject field.
+/// the correct subobject field. In particular, implicit casts grow this list
+/// and explicit casts like static_cast shrink this list.
 class PointerToMember : public NonLoc {
   friend class ento::SValBuilder;
 
 public:
   using PTMDataType =
       llvm::PointerUnion<const NamedDecl *, const PointerToMemberData *>;
 
   const PTMDataType getPTMData() const {

clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
 #include "llvm/ADT/APSInt.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableList.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include <cassert>
 #include <cstdint>
+#include <list>
 #include <utility>
 
 using namespace clang;
 using namespace ento;
 
 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
                               llvm::ImmutableList<SVal> L) {
   T.Profile(ID);
if (!D) {
     D = (PointerToMemberData *)BPAlloc.Allocate<PointerToMemberData>();
     new (D) PointerToMemberData(ND, L);
     PointerToMemberDataSet.InsertNode(D, InsertPos);
   }
 
   return D;
 }
 
 const PointerToMemberData *BasicValueFactory::accumCXXBase(
     llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
-    const nonloc::PointerToMember &PTM) {
+    const nonloc::PointerToMember &PTM, const CastKind &kind) {
+  assert((kind == CK_DerivedToBaseMemberPointer ||
+          kind == CK_BaseToDerivedMemberPointer ||
+          kind == CK_ReinterpretMemberPointer) &&
+         "accumCXXBase called with wrong CastKind");
   nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
   const NamedDecl *ND = nullptr;
-  llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
+  llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList;
 
   if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
     if (PTMDT.is<const NamedDecl *>())
       ND = PTMDT.get<const NamedDecl *>();
 
-    PathList = CXXBaseListFactory.getEmptyList();
+    BaseSpecList = CXXBaseListFactory.getEmptyList();
   } else { // const PointerToMemberData *
     const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
     ND = PTMD->getDeclaratorDecl();
 
-    PathList = PTMD->getCXXBaseList();
+    BaseSpecList = PTMD->getCXXBaseList();
   }
 
+  if (kind == CK_DerivedToBaseMemberPointer) {
+    // Here we pop off matching CXXBaseSpecifiers from BaseSpecList.
+    // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and
+    // serves to remove a matching implicit cast. Note that static_cast's that
+    // are no-ops do not count since they produce an empty PathRange, a nice
+    // thing about Clang AST.
+
+    // First we need to make sure that there are no-repetitions in BaseSpecList
+    llvm::SmallPtrSet<QualType, 16> BaseSpecSeen;
+    for (const auto &BaseSpec : BaseSpecList) {
+      auto BaseType = BaseSpec->getType();
+      assert(BaseSpecSeen.find(BaseType) == BaseSpecSeen.end() &&
+             "CXXBaseSpecifier list of PointerToMemberData must not have "
+             "repeated elements");
+      BaseSpecSeen.insert(BaseType);
+    }
+
+    // Now we know that there are no repetitions in BaseSpecList.
+    // So, popping the first element from it corresponding to each element in
+    // PathRange is equivalent to only including elements that are in
+    // BaseSpecList but not it PathRange
+    auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList();
+    for (const auto &BaseSpec : BaseSpecList)
+      if (llvm::none_of(
+              PathRange, [&BaseSpec](const auto &I) -> auto {
+                return BaseSpec->getType() == I->getType();
+              }))
+        ReducedBaseSpecList =
+            CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList);
+
+    return getPointerToMemberData(ND, ReducedBaseSpecList);
+  } else {
     for (const auto &I : llvm::reverse(PathRange))
-    PathList = prependCXXBase(I, PathList);
-  return getPointerToMemberData(ND, PathList);
+      BaseSpecList = prependCXXBase(I, BaseSpecList);
+    return getPointerToMemberData(ND, BaseSpecList);
+  }
 }
 
 const llvm::APSInt*
 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
                              const llvm::APSInt& V1, const llvm::APSInt& V2) {
   switch (Op) {
     default:
       llvm_unreachable("Invalid Opcode.");

clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp

switch (CastE->getCastKind()) {
         Bldr.generateNode(CastE, Pred, state);
         continue;
       }
       case CK_DerivedToBaseMemberPointer:
       case CK_BaseToDerivedMemberPointer:
       case CK_ReinterpretMemberPointer: {
         SVal V = state->getSVal(Ex, LCtx);
         if (auto PTMSV = V.getAs<nonloc::PointerToMember>()) {
-          SVal CastedPTMSV = svalBuilder.makePointerToMember(
-              getBasicVals().accumCXXBase(
+          SVal CastedPTMSV =
+              svalBuilder.makePointerToMember(getBasicVals().accumCXXBase(
                   llvm::make_range<CastExpr::path_const_iterator>(
-                      CastE->path_begin(), CastE->path_end()), *PTMSV));
+                      CastE->path_begin(), CastE->path_end()),
+                  *PTMSV, CastE->getCastKind()));
           state = state->BindExpr(CastE, LCtx, CastedPTMSV);
           Bldr.generateNode(CastE, Pred, state);
           continue;
         }
         // Explicitly proceed with default handler for this case cascade.
         state = handleLVectorSplat(state, LCtx, CastE, Bldr, Pred);
         continue;
       }

clang/test/Analysis/pointer-to-member.cpp

void test() {
 
   clang_analyzer_eval(a.*ap == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(a.*bp == 2); // expected-warning{{TRUE}}
   clang_analyzer_eval(a.*cp == 3); // expected-warning{{TRUE}}
   clang_analyzer_eval(a.*dp == 4); // expected-warning{{TRUE}}
   clang_analyzer_eval(a.*ep == 5); // expected-warning{{TRUE}}
 }
 } // namespace testAnonymousMember
+
+namespace testStaticCasting {
+// From bug #48739
+struct Grandfather {
+  int field;
+};
+
+struct Father : public Grandfather {};
+struct Son : public Father {};
+
+void test() {
+  int Son::*sf = &Son::field;
+  Grandfather grandpa;
+  grandpa.field = 10;
+  int Grandfather::*gpf1 = static_cast<int Grandfather::*>(sf);
+  int Grandfather::*gpf2 = static_cast<int Grandfather::*>(static_cast<int Father::*>(sf));
+  int Grandfather::*gpf3 = static_cast<int Grandfather::*>(static_cast<int Son::*>(static_cast<int Father::*>(sf)));
+  clang_analyzer_eval(grandpa.*gpf1 == 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(grandpa.*gpf2 == 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(grandpa.*gpf3 == 10); // expected-warning{{TRUE}}
+}
+} // namespace testStaticCasting