[analyzer][UninitializedObjectChecker] Pointer/reference objects are dereferenced according to dynamic type

[Szelethus]

Summary

This diff fixes a long debated issues with pointers/references not being dereferenced according to their dynamic type. This also fixed an issue where regions that were pointed to by void pointers were not analyzed.

Note how I also added a test case about inheritance, clearly showing that it doesn't find an uninitialized field that it should. Because base class handling is still being discussed, I'm planning to fix that issue in a different patch. The reason why it's still in this patch is that it might be closely tied to these changes too.

Thumbs up to @NoQ for setting me on the right track!

[Szelethus]

lib/StaticAnalyzer/Checkers/UninitializedObjectChecker.cpp

598–616

I already have a fix for this, but I want to be extra sure, so I'm running the checker on LLVM to see whether anything breaks.

This is also important for nonloc::LocAsInteger, which I'm going add fix in yet another patch.

[Szelethus]

Rebased to the latest trunk.

[george.karpenkov]

Cf. my comments to https://reviews.llvm.org/D49437: is it possible to separate pointer-chasing from the rest of the checker?

[Szelethus]

@NoQ, we had quite a few conversations about this fix. How do you feel about this implementation?

[NoQ]

This looks roughly correct, but at the same time none of the tests actually exercise the dynamic type propagation. In these tests all the necessary information is obtained from the structure of the MemRegion (directly or via the initial StripCasts), not from the dynamic type map that is an additional layer of metadata over the program state. The actual test would assume, as an example, chasing undefined values through a symbolic pointer produced by operator new() - which is a symbolic void pointer, but it points to a well-defined type of object. Because we skip symbolic pointers for now, i guess you cannot really write such tests. But at the same time chasing through heap symbolic pointers (i.e., pointers in the heap memory space) should be safe (so safe that they shouldn't really have been implemented as symbolic pointers in the first place).

[Szelethus]

Thanks! I plan on revisiting how heap allocated regions are handled in the future.

[Szelethus]

Rebased to latest trunk.

lib/StaticAnalyzer/Checkers/UninitializedObjectChecker.cpp

 //  `-analyzer-config alpha.cplusplus.UninitializedObject:NotesAsWarnings=true`.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangSACheckers.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
-#include <algorithm>
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
 
 using namespace clang;
 using namespace clang::ento;
 
 namespace {
 
 class UninitializedObjectChecker : public Checker<check::EndFunction> {
   std::unique_ptr<BuiltinBug> BT_uninitField;

 /// possible.
 static Optional<nonloc::LazyCompoundVal>
 getObjectVal(const CXXConstructorDecl *CtorDecl, CheckerContext &Context);
 
 /// Checks whether the constructor under checking is called by another
 /// constructor.
 static bool isCalledByConstructor(const CheckerContext &Context);
 
-/// Returns whether FD can be (transitively) dereferenced to a void pointer type
+/// Returns whether T can be (transitively) dereferenced to a void pointer type
 /// (void*, void**, ...). The type of the region behind a void pointer isn't
 /// known, and thus FD can not be analyzed.
-static bool isVoidPointer(const FieldDecl *FD);
+static bool isVoidPointer(QualType T);
 
 /// Returns true if T is a primitive type. We defined this type so that for
 /// objects that we'd only like analyze as much as checking whether their
 /// value is undefined or not, such as ints and doubles, can be analyzed with
 /// ease. This also helps ensuring that every special field type is handled
 /// correctly.
 static bool isPrimitiveType(const QualType &T) {
   return T->isBuiltinType() || T->isEnumeralType() || T->isMemberPointerType();
bool FindUninitializedFields::isPointerOrReferenceUninit(
     const FieldRegion *FR, FieldChainInfo LocalChain) {
 
   assert((FR->getDecl()->getType()->isPointerType() ||
           FR->getDecl()->getType()->isReferenceType()) &&
          "This method only checks pointer/reference objects!");
 
   SVal V = State->getSVal(FR);
 
-  if (V.isUnknown() || V.isZeroConstant()) {
+  if (V.isUnknown() || V.getAs<loc::ConcreteInt>()) {
     IsAnyFieldInitialized = true;
     return false;
   }
 
   if (V.isUndef()) {
     return addFieldToUninits({LocalChain, FR});
   }
 
-  const FieldDecl *FD = FR->getDecl();
+  assert(V.getAs<loc::MemRegionVal>() &&
+         "At this point V must be loc::MemRegionVal!");
+  auto L = V.castAs<loc::MemRegionVal>();
 
-  // TODO: The dynamic type of a void pointer may be retrieved with
-  // `getDynamicTypeInfo`.
-  if (isVoidPointer(FD)) {
+  // We can't reason about symbolic regions, assume its initialized.
+  // Note that this also avoids a potential infinite recursion, because
+  // constructors for list-like classes are checked without being called, and
+  // the Static Analyzer will construct a symbolic region for Node *next; or
+  // similar code snippets.
+  if (L.getRegion()->getSymbolicBase()) {
+    IsAnyFieldInitialized = true;
+    return false;
+  }
+
+  DynamicTypeInfo DynTInfo = getDynamicTypeInfo(State, L.getRegion());
+  if (!DynTInfo.isValid()) {
     IsAnyFieldInitialized = true;
     return false;
   }
 
-  assert(V.getAs<Loc>() && "V should be Loc at this point!");
+  QualType DynT = DynTInfo.getType();
+
+  if (isVoidPointer(DynT)) {
+    IsAnyFieldInitialized = true;
+    return false;
+  }
 
   // At this point the pointer itself is initialized and points to a valid
   // location, we'll now check the pointee.
-  SVal DerefdV = State->getSVal(V.castAs<Loc>());
+  SVal DerefdV = State->getSVal(V.castAs<Loc>(), DynT);
 
-  // TODO: Dereferencing should be done according to the dynamic type.
-  while (Optional<Loc> L = DerefdV.getAs<Loc>()) {
-    DerefdV = State->getSVal(*L);
+  // If DerefdV is still a pointer value, we'll dereference it again (e.g.:
+  // int** -> int*).
+  while (auto Tmp = DerefdV.getAs<loc::MemRegionVal>()) {
+    if (Tmp->getRegion()->getSymbolicBase()) {
+      IsAnyFieldInitialized = true;
+      return false;
     }
 
-  // If V is a pointer pointing to a record type.
-  if (Optional<nonloc::LazyCompoundVal> RecordV =
-          DerefdV.getAs<nonloc::LazyCompoundVal>()) {
-
-    const TypedValueRegion *R = RecordV->getRegion();
+    DynTInfo = getDynamicTypeInfo(State, Tmp->getRegion());
+    if (!DynTInfo.isValid()) {
+      IsAnyFieldInitialized = true;
+      return false;
+    }
 
-    // We can't reason about symbolic regions, assume its initialized.
-    // Note that this also avoids a potential infinite recursion, because
-    // constructors for list-like classes are checked without being called, and
-    // the Static Analyzer will construct a symbolic region for Node *next; or
-    // similar code snippets.
-    if (R->getSymbolicBase()) {
+    DynT = DynTInfo.getType();
+    if (isVoidPointer(DynT)) {
       IsAnyFieldInitialized = true;
       return false;
     }
 
-    const QualType T = R->getValueType();
+    DerefdV = State->getSVal(*Tmp, DynT);
+  }
 
-    if (T->isStructureOrClassType())
+  // If FR is a pointer pointing to a non-primitive type.
+  if (Optional<nonloc::LazyCompoundVal> RecordV =
+          DerefdV.getAs<nonloc::LazyCompoundVal>()) {
+
+    const TypedValueRegion *R = RecordV->getRegion();
+
+    if (DynT->getPointeeType()->isStructureOrClassType())
       return isNonUnionUninit(R, {LocalChain, FR});
 
-    if (T->isUnionType()) {
+    if (DynT->getPointeeType()->isUnionType()) {
       if (isUnionUninit(R)) {
         return addFieldToUninits({LocalChain, FR, /*IsDereferenced*/ true});
       } else {
         IsAnyFieldInitialized = true;
         return false;
       }
     }
 
-    if (T->isArrayType()) {
+    if (DynT->getPointeeType()->isArrayType()) {
       IsAnyFieldInitialized = true;
       return false;
     }
 
     llvm_unreachable("All cases are handled!");
   }
 
-  // TODO: If possible, it should be asserted that the DerefdV at this point is
-  // primitive.
+  assert((isPrimitiveType(DynT->getPointeeType()) || DynT->isPointerType() ||
+          DynT->isReferenceType()) &&
+         "At this point FR must either have a primitive dynamic type, or it "
+         "must be a null, undefined, unknown or concrete pointer!");
 
   if (isPrimitiveUninit(DerefdV))
     return addFieldToUninits({LocalChain, FR, /*IsDereferenced*/ true});
 
   IsAnyFieldInitialized = true;
   return false;
 }
 
bool FieldChainInfo::isDereferenced() const {
   return IsDereferenced;
 }
 
 const FieldDecl *FieldChainInfo::getEndOfChain() const {
   assert(!Chain.isEmpty() && "Empty fieldchain!");
   return (*Chain.begin())->getDecl();
 }
 
+// TODO: This function constructs an incorrect string if a void pointer is a
+// part of the chain:
+//
+//   struct B { int x; }
+//
+//   struct A {
+//     void *vptr;
+//     A(void* vptr) : vptr(vptr) {}
+//   };
+//
+//   void f() {
+//     B b;
+//     A a(&b);
+//   }
+//
+// The note message will be "uninitialized field 'this->vptr->x'", even though
+// void pointers can't be dereferenced. This should be changed to "uninitialized
+// field 'static_cast<B*>(this->vptr)->x'".
+//
 // TODO: This function constructs an incorrect fieldchain string in the
 // following case:
 //
 //   struct Base { int x; };
 //   struct D1 : Base {}; struct D2 : Base {};
 //
 //   struct MostDerived : D1, D2 {
 //     MostDerived() {}
void FieldChainInfo::printTail(
   Out << getVariableName(Field);
   Out << (Field->getType()->isPointerType() ? "->" : ".");
 }
 
 //===----------------------------------------------------------------------===//
 //                           Utility functions.
 //===----------------------------------------------------------------------===//
 
-static bool isVoidPointer(const FieldDecl *FD) {
-  QualType T = FD->getType();
-
+static bool isVoidPointer(QualType T) {
   while (!T.isNull()) {
     if (T->isVoidPointerType())
       return true;
     T = T->getPointeeType();
   }
   return false;
 }
 

test/Analysis/cxx-uninitialized-object-inheritance.cpp

 public:
   VirtualDiamondInheritanceTest3() // expected-warning{{1 uninitialized field}}
       : VirtualFirst3(int{}) {}
 };
 
 void fVirtualDiamondInheritanceTest3() {
   VirtualDiamondInheritanceTest3();
 }
+
+//===----------------------------------------------------------------------===//
+// Dynamic type test.
+//===----------------------------------------------------------------------===//
+
+struct DynTBase {};
+struct DynTDerived : DynTBase {
+  // TODO: we'd expect the note: {{uninitialized field 'this->x'}}
+  int x; // no-note
+};
+
+struct DynamicTypeTest {
+  DynTBase *bptr;
+  int i = 0;
+
+  // TODO: we'd expect the warning: {{1 uninitialized field}}
+  DynamicTypeTest(DynTBase *bptr) : bptr(bptr) {} // no-warning
+};
+
+void f() {
+  DynTDerived d;
+  DynamicTypeTest t(&d);
+};

test/Analysis/cxx-uninitialized-object-ptr-ref.cpp

 };
 
 void fCharPointerTest() {
   CharPointerTest();
 }
 
 struct CyclicPointerTest {
   int *ptr;
-  CyclicPointerTest() : ptr(reinterpret_cast<int*>(&ptr)) {}
+  CyclicPointerTest() : ptr(reinterpret_cast<int *>(&ptr)) {}
 };
 
 void fCyclicPointerTest() {
   CyclicPointerTest();
 }
 
 //===----------------------------------------------------------------------===//
 // Void pointer tests.
void fVoidPointerLRefTest() {
   void *vptr = malloc(sizeof(int));
   VoidPointerLRefTest(vptr, char());
 }
 
 struct CyclicVoidPointerTest {
   void *vptr; // no-crash
 
   CyclicVoidPointerTest() : vptr(&vptr) {}
-
 };
 
 void fCyclicVoidPointerTest() {
   CyclicVoidPointerTest();
 }
 
+struct IntDynTypedVoidPointerTest1 {
+  void *vptr; // expected-note{{uninitialized pointee 'this->vptr'}}
+  int dontGetFilteredByNonPedanticMode = 0;
+
+  IntDynTypedVoidPointerTest1(void *vptr) : vptr(vptr) {} // expected-warning{{1 uninitialized field}}
+};
+
+void fIntDynTypedVoidPointerTest1() {
+  int a;
+  IntDynTypedVoidPointerTest1 tmp(&a);
+}
+
+struct RecordDynTypedVoidPointerTest {
+  struct RecordType {
+    int x; // expected-note{{uninitialized field 'this->vptr->x'}}
+    int y; // expected-note{{uninitialized field 'this->vptr->y'}}
+  };
+
+  void *vptr;
+  int dontGetFilteredByNonPedanticMode = 0;
+
+  RecordDynTypedVoidPointerTest(void *vptr) : vptr(vptr) {} // expected-warning{{2 uninitialized fields}}
+};
+
+void fRecordDynTypedVoidPointerTest() {
+  RecordDynTypedVoidPointerTest::RecordType a;
+  RecordDynTypedVoidPointerTest tmp(&a);
+}
+
+struct NestedNonVoidDynTypedVoidPointerTest {
+  struct RecordType {
+    int x;      // expected-note{{uninitialized field 'this->vptr->x'}}
+    int y;      // expected-note{{uninitialized field 'this->vptr->y'}}
+    void *vptr; // expected-note{{uninitialized pointee 'this->vptr->vptr'}}
+  };
+
+  void *vptr;
+  int dontGetFilteredByNonPedanticMode = 0;
+
+  NestedNonVoidDynTypedVoidPointerTest(void *vptr, void *c) : vptr(vptr) {
+    static_cast<RecordType *>(vptr)->vptr = c; // expected-warning{{3 uninitialized fields}}
+  }
+};
+
+void fNestedNonVoidDynTypedVoidPointerTest() {
+  NestedNonVoidDynTypedVoidPointerTest::RecordType a;
+  char c;
+  NestedNonVoidDynTypedVoidPointerTest tmp(&a, &c);
+}
+
 //===----------------------------------------------------------------------===//
 // Multipointer tests.
 //===----------------------------------------------------------------------===//
 
 #ifdef PEDANTIC
 class MultiPointerTest1 {
 public:
   struct RecordType {