[clang][dataflow] Fix nullptr dereferencing error.

[ymandel]

Summary

When pre-initializing fields in the environment, the code assumed that all
fields of a struct would be initialized. However, given limits on value
construction, that assumption is incorrect. This patch changes the code to drop
that assumption and thereby avoid dereferencing a nullptr.

[xazax.hun]

When pre-initializing fields in the environment, the code assumed that all fields of a struct would be initialized

Was this assumption ever correct given that it was already skipping the initialization of recursive cases?

[ymandel]

Thanks for the review! That was impressively fast... :)

[ymandel]

In D121158#3365415, @xazax.hun wrote:

When pre-initializing fields in the environment, the code assumed that all fields of a struct would be initialized

Was this assumption ever correct given that it was already skipping the initialization of recursive cases?

Yeah, I had that thought of that and I'm pretty sure it wasn't. But that does provide a way to test this without creating a very large struct. Let me see if I can add a test to this patch. Otherwise, I'll write a followup.

[ymandel]

Add test for recursive type case.

[ymandel]

switch to c++11 for test.

[ymandel]

In D121158#3365494, @ymandel wrote:

In D121158#3365415, @xazax.hun wrote:

When pre-initializing fields in the environment, the code assumed that all fields of a struct would be initialized

Was this assumption ever correct given that it was already skipping the initialization of recursive cases?

Yeah, I had that thought of that and I'm pretty sure it wasn't. But that does provide a way to test this without creating a very large struct. Let me see if I can add a test to this patch. Otherwise, I'll write a followup.

I added a test for the recursive case and tested (a variant of) it on the code before this patch to verify that it triggered a failure. Interestingly, it triggers a different failure mode in getChild -- the assertion that the field will be present. The guard on the recursive case prevents the field from being added at all, so you don't have a nullptr added to the map. But, you also don't have the field added, so the (old) assert would fail. The patch addresses this by allowing for lack of field presence.

[xazax.hun]

Wonderful, thanks!

clang/include/clang/Analysis/FlowSensitive/Value.h

public:
 
   explicit StructValue(llvm::DenseMap<const ValueDecl *, Value *> Children)
       : Value(Kind::Struct), Children(std::move(Children)) {}
 
   static bool classof(const Value *Val) {
     return Val->getKind() == Kind::Struct;
   }
 
-  /// Returns the child value that is assigned for `D`.
-  Value &getChild(const ValueDecl &D) const {
+  /// Returns the child value that is assigned for `D` or null if the child is
+  /// not initialized.
+  Value *getChild(const ValueDecl &D) const {
     auto It = Children.find(&D);
-    assert(It != Children.end());
-    return *It->second;
+    if (It == Children.end())
+      return nullptr;
+    return It->second;
   }
 
   /// Assigns `Val` as the child value for `D`.
   void setChild(const ValueDecl &D, Value &Val) { Children[&D] = &Val; }
 
   /// Returns the value of the synthetic property with the given `Name` or null
   /// if the property isn't assigned a value.
   Value *getProperty(llvm::StringRef Name) const {

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
 
     const QualType Type = AggregateLoc.getType();
     assert(Type->isStructureOrClassType());
 
     for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
       assert(Field != nullptr);
       StorageLocation &FieldLoc = AggregateLoc.getChild(*Field);
       MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
-      setValue(FieldLoc, StructVal->getChild(*Field));
+      if (auto *FieldVal = StructVal->getChild(*Field))
+        setValue(FieldLoc, *FieldVal);
     }
   }
 
   auto IT = MemberLocToStruct.find(&Loc);
   if (IT != MemberLocToStruct.end()) {
     // `Loc` is the location of a struct member so we need to also update the
     // value of the member in the corresponding `StructValue`.
 
if (Type->isStructureOrClassType()) {
     for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
       assert(Field != nullptr);
 
       QualType FieldType = Field->getType();
       if (Visited.contains(FieldType.getCanonicalType()))
         continue;
 
       Visited.insert(FieldType.getCanonicalType());
-      FieldValues.insert(
-          {Field, createValueUnlessSelfReferential(
-                      FieldType, Visited, Depth + 1, CreatedValuesCount)});
+      if (auto *FieldValue = createValueUnlessSelfReferential(
+              FieldType, Visited, Depth + 1, CreatedValuesCount))
+        FieldValues.insert({Field, FieldValue});
       Visited.erase(FieldType.getCanonicalType());
     }
 
     return &takeOwnership(
         std::make_unique<StructValue>(std::move(FieldValues)));
   }
 
   return nullptr;

clang/unittests/Analysis/FlowSensitive/DataflowEnvironmentTest.cpp

 //===- unittests/Analysis/FlowSensitive/DataflowEnvironmentTest.cpp -------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "NoopAnalysis.h"
+#include "TestingSupport.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <memory>
 
 namespace {
 
 using namespace clang;
 using namespace dataflow;
+using ::testing::ElementsAre;
+using ::testing::Pair;
 
 class EnvironmentTest : public ::testing::Test {
   DataflowAnalysisContext Context;
 
 protected:
   EnvironmentTest()
       : Context(std::make_unique<WatchedLiteralsSolver>()), Env(Context) {}
 
TEST_F(EnvironmentTest, FlowCondition) {
 
   Env.addToFlowCondition(X);
   EXPECT_TRUE(Env.flowConditionImplies(X));
 
   auto &NotX = Env.makeNot(X);
   EXPECT_FALSE(Env.flowConditionImplies(NotX));
 }
 
+TEST_F(EnvironmentTest, CreateValueRecursiveType) {
+  using namespace ast_matchers;
+
+  std::string Code = R"cc(
+    struct Recursive {
+      bool X;
+      Recursive *R;
+    };
+  )cc";
+
+  auto Unit =
+      tooling::buildASTFromCodeWithArgs(Code, {"-fsyntax-only", "-std=c++11"});
+  auto &Context = Unit->getASTContext();
+
+  ASSERT_EQ(Context.getDiagnostics().getClient()->getNumErrors(), 0U);
+
+  auto Results =
+      match(qualType(hasDeclaration(recordDecl(
+                         hasName("Recursive"),
+                         has(fieldDecl(hasName("R")).bind("field-r")))))
+                .bind("target"),
+            Context);
+  const QualType *Ty = selectFirst<QualType>("target", Results);
+  const FieldDecl *R = selectFirst<FieldDecl>("field-r", Results);
+  ASSERT_TRUE(Ty != nullptr && !Ty->isNull());
+  ASSERT_TRUE(R != nullptr);
+
+  // Verify that the struct and the field (`R`) with first appearance of the
+  // type is created successfully.
+  Value *Val = Env.createValue(*Ty);
+  ASSERT_NE(Val, nullptr);
+  StructValue *SVal = clang::dyn_cast<StructValue>(Val);
+  ASSERT_NE(SVal, nullptr);
+  Val = SVal->getChild(*R);
+  ASSERT_NE(Val, nullptr);
+  PointerValue *PV = clang::dyn_cast<PointerValue>(Val);
+  EXPECT_NE(PV, nullptr);
+}
+
 } // namespace

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *BarLoc =
             cast<ScalarStorageLocation>(&FooLoc->getChild(*BarDecl));
 
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(*BarDecl));
         EXPECT_EQ(Env.getValue(*BarLoc), BarVal);
       });
 }
 
 TEST_F(TransferTest, ClassVarDecl) {
   std::string Code = R"(
     class A {
       int Bar;
runDataflow(
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *BarLoc =
             cast<ScalarStorageLocation>(&FooLoc->getChild(*BarDecl));
 
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(*BarDecl));
         EXPECT_EQ(Env.getValue(*BarLoc), BarVal);
       });
 }
 
 TEST_F(TransferTest, ReferenceVarDecl) {
   std::string Code = R"(
     struct A {};
 
runDataflow(Code, [](llvm::ArrayRef<std::pair<
 
     const auto *FooLoc = cast<ScalarStorageLocation>(
         Env.getStorageLocation(*FooDecl, SkipPast::None));
     const auto *FooVal = cast<ReferenceValue>(Env.getValue(*FooLoc));
     const auto *FooPointeeVal =
         cast<StructValue>(Env.getValue(FooVal->getPointeeLoc()));
 
     const auto *BarVal =
-        cast<ReferenceValue>(&FooPointeeVal->getChild(*BarDecl));
+        cast<ReferenceValue>(FooPointeeVal->getChild(*BarDecl));
     const auto *BarPointeeVal =
         cast<StructValue>(Env.getValue(BarVal->getPointeeLoc()));
 
     const auto *FooRefVal =
-        cast<ReferenceValue>(&BarPointeeVal->getChild(*FooRefDecl));
+        cast<ReferenceValue>(BarPointeeVal->getChild(*FooRefDecl));
     const StorageLocation &FooRefPointeeLoc = FooRefVal->getPointeeLoc();
     EXPECT_THAT(Env.getValue(FooRefPointeeLoc), IsNull());
 
     const auto *FooPtrVal =
-        cast<PointerValue>(&BarPointeeVal->getChild(*FooPtrDecl));
+        cast<PointerValue>(BarPointeeVal->getChild(*FooPtrDecl));
     const StorageLocation &FooPtrPointeeLoc = FooPtrVal->getPointeeLoc();
     EXPECT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull());
 
     const auto *BazRefVal =
-        cast<ReferenceValue>(&BarPointeeVal->getChild(*BazRefDecl));
+        cast<ReferenceValue>(BarPointeeVal->getChild(*BazRefDecl));
     const StorageLocation &BazRefPointeeLoc = BazRefVal->getPointeeLoc();
     EXPECT_THAT(Env.getValue(BazRefPointeeLoc), NotNull());
 
     const auto *BazPtrVal =
-        cast<PointerValue>(&BarPointeeVal->getChild(*BazPtrDecl));
+        cast<PointerValue>(BarPointeeVal->getChild(*BazPtrDecl));
     const StorageLocation &BazPtrPointeeLoc = BazPtrVal->getPointeeLoc();
     EXPECT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull());
   });
 }
 
 TEST_F(TransferTest, PointerVarDecl) {
   std::string Code = R"(
     struct A {};
runDataflow(
 
         const auto *FooLoc = cast<ScalarStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *FooVal = cast<PointerValue>(Env.getValue(*FooLoc));
         const auto *FooPointeeVal =
             cast<StructValue>(Env.getValue(FooVal->getPointeeLoc()));
 
         const auto *BarVal =
-            cast<PointerValue>(&FooPointeeVal->getChild(*BarDecl));
+            cast<PointerValue>(FooPointeeVal->getChild(*BarDecl));
         const auto *BarPointeeVal =
             cast<StructValue>(Env.getValue(BarVal->getPointeeLoc()));
 
         const auto *FooRefVal =
-            cast<ReferenceValue>(&BarPointeeVal->getChild(*FooRefDecl));
+            cast<ReferenceValue>(BarPointeeVal->getChild(*FooRefDecl));
         const StorageLocation &FooRefPointeeLoc = FooRefVal->getPointeeLoc();
         EXPECT_THAT(Env.getValue(FooRefPointeeLoc), IsNull());
 
         const auto *FooPtrVal =
-            cast<PointerValue>(&BarPointeeVal->getChild(*FooPtrDecl));
+            cast<PointerValue>(BarPointeeVal->getChild(*FooPtrDecl));
         const StorageLocation &FooPtrPointeeLoc = FooPtrVal->getPointeeLoc();
         EXPECT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull());
 
         const auto *BazRefVal =
-            cast<ReferenceValue>(&BarPointeeVal->getChild(*BazRefDecl));
+            cast<ReferenceValue>(BarPointeeVal->getChild(*BazRefDecl));
         const StorageLocation &BazRefPointeeLoc = BazRefVal->getPointeeLoc();
         EXPECT_THAT(Env.getValue(BazRefPointeeLoc), NotNull());
 
         const auto *BazPtrVal =
-            cast<PointerValue>(&BarPointeeVal->getChild(*BazPtrDecl));
+            cast<PointerValue>(BarPointeeVal->getChild(*BazPtrDecl));
         const StorageLocation &BazPtrPointeeLoc = BazPtrVal->getPointeeLoc();
         EXPECT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull());
       });
 }
 
 TEST_F(TransferTest, MultipleVarsDecl) {
   std::string Code = R"(
     void target() {
runDataflow(
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *BarLoc =
             cast<ScalarStorageLocation>(&FooLoc->getChild(*BarDecl));
 
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(*BarDecl));
         EXPECT_EQ(Env.getValue(*BarLoc), BarVal);
       });
 }
 
 TEST_F(TransferTest, ReferenceParamDecl) {
   std::string Code = R"(
     struct A {};
 
runDataflow(
             FAIL() << "Unexpected field: " << Field->getNameAsString();
           }
         }
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(*BarDecl));
 
         const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
         ASSERT_THAT(BazDecl, NotNull());
 
         EXPECT_EQ(Env.getValue(*BazDecl, SkipPast::None), BarVal);
       });
 }
 
runDataflow(
             FAIL() << "Unexpected field: " << Field->getNameAsString();
           }
         }
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(*BarDecl));
 
         const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
         ASSERT_THAT(BazDecl, NotNull());
 
         EXPECT_EQ(Env.getValue(*BazDecl, SkipPast::None), BarVal);
       });
 }
 
runDataflow(
             FAIL() << "Unexpected field: " << Field->getNameAsString();
           }
         }
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<ReferenceValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<ReferenceValue>(FooVal->getChild(*BarDecl));
         const auto *BarPointeeVal =
             cast<IntegerValue>(Env.getValue(BarVal->getPointeeLoc()));
 
         const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
         ASSERT_THAT(BazDecl, NotNull());
 
         EXPECT_EQ(Env.getValue(*BazDecl, SkipPast::None), BarPointeeVal);
       });
runDataflow(
 
         const auto *QuxLoc =
             cast<AggregateStorageLocation>(&ThisLoc->getChild(*QuxDecl));
         const auto *QuxVal = dyn_cast<StructValue>(Env.getValue(*QuxLoc));
         ASSERT_THAT(QuxVal, NotNull());
 
         const auto *BazLoc =
             cast<ScalarStorageLocation>(&QuxLoc->getChild(*BazDecl));
-        const auto *BazVal = cast<IntegerValue>(&QuxVal->getChild(*BazDecl));
+        const auto *BazVal = cast<IntegerValue>(QuxVal->getChild(*BazDecl));
         EXPECT_EQ(Env.getValue(*BazLoc), BazVal);
 
         const ValueDecl *QuuxDecl = findValueDecl(ASTCtx, "Quux");
         ASSERT_THAT(QuuxDecl, NotNull());
         EXPECT_EQ(Env.getValue(*QuuxDecl, SkipPast::None), BazVal);
       });
 }
 
runDataflow(
 
         const auto *QuxLoc =
             cast<AggregateStorageLocation>(&ThisLoc->getChild(*QuxDecl));
         const auto *QuxVal = dyn_cast<StructValue>(Env.getValue(*QuxLoc));
         ASSERT_THAT(QuxVal, NotNull());
 
         const auto *BazLoc =
             cast<ScalarStorageLocation>(&QuxLoc->getChild(*BazDecl));
-        const auto *BazVal = cast<IntegerValue>(&QuxVal->getChild(*BazDecl));
+        const auto *BazVal = cast<IntegerValue>(QuxVal->getChild(*BazDecl));
         EXPECT_EQ(Env.getValue(*BazLoc), BazVal);
 
         const ValueDecl *QuuxDecl = findValueDecl(ASTCtx, "Quux");
         ASSERT_THAT(QuuxDecl, NotNull());
         EXPECT_EQ(Env.getValue(*QuuxDecl, SkipPast::None), BazVal);
       });
 }
 
runDataflow(
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *BarLoc =
             cast<ScalarStorageLocation>(&FooLoc->getChild(*BarDecl));
 
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(*BarDecl));
         EXPECT_EQ(Env.getValue(*BarLoc), BarVal);
       });
 }
 
 TEST_F(TransferTest, ElidableConstructor) {
   // This test is effectively the same as TransferTest.TemporaryObject, but
   // the code is compiled as C++ 14.
   std::string Code = R"(
runDataflow(
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooLoc = cast<AggregateStorageLocation>(
             Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *BarLoc =
             cast<ScalarStorageLocation>(&FooLoc->getChild(*BarDecl));
 
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
-        const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(*BarDecl));
         EXPECT_EQ(Env.getValue(*BarLoc), BarVal);
       },
       LangStandard::lang_cxx14);
 }
 
 TEST_F(TransferTest, AssignmentOperator) {
   std::string Code = R"(
     struct A {
runDataflow(Code,
 
                 const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
                 ASSERT_THAT(BazDecl, NotNull());
 
                 const auto &FooVal =
                     *cast<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
                 const auto *BarVal =
                     cast<IntegerValue>(Env.getValue(*BarDecl, SkipPast::None));
-                EXPECT_EQ(BarVal, &FooVal.getChild(*BazDecl));
+                EXPECT_EQ(BarVal, FooVal.getChild(*BazDecl));
               });
 }
 
 TEST_F(TransferTest, StaticCast) {
   std::string Code = R"(
     void target(int Foo) {
       int Bar = static_cast<int>(Foo);
       // [[p]]
runDataflow(
               cast<IntegerValue>(Env.getValue(*BarArgDecl, SkipPast::None));
           const auto *QuxArgVal =
               cast<IntegerValue>(Env.getValue(*QuxArgDecl, SkipPast::None));
 
           const auto *QuuxVal =
               cast<StructValue>(Env.getValue(*QuuxDecl, SkipPast::None));
           ASSERT_THAT(QuuxVal, NotNull());
 
-          const auto *BazVal = cast<StructValue>(&QuuxVal->getChild(*BazDecl));
+          const auto *BazVal = cast<StructValue>(QuuxVal->getChild(*BazDecl));
           ASSERT_THAT(BazVal, NotNull());
 
-          EXPECT_EQ(&QuuxVal->getChild(*BarDecl), BarArgVal);
-          EXPECT_EQ(&BazVal->getChild(*FooDecl), FooArgVal);
-          EXPECT_EQ(&QuuxVal->getChild(*QuxDecl), QuxArgVal);
+          EXPECT_EQ(QuuxVal->getChild(*BarDecl), BarArgVal);
+          EXPECT_EQ(BazVal->getChild(*FooDecl), FooArgVal);
+          EXPECT_EQ(QuuxVal->getChild(*QuxDecl), QuxArgVal);
         });
   }
 }
 
 TEST_F(TransferTest, AssignToUnionMember) {
   std::string Code = R"(
     union A {
       int Foo;
runDataflow(Code,
                 const ValueDecl *A2Decl = findValueDecl(ASTCtx, "A2");
                 ASSERT_THAT(A2Decl, NotNull());
 
                 const auto *BarVal =
                     cast<IntegerValue>(Env.getValue(*BarDecl, SkipPast::None));
 
                 const auto *A2Val =
                     cast<StructValue>(Env.getValue(*A2Decl, SkipPast::None));
-                EXPECT_EQ(&A2Val->getChild(*FooDecl), BarVal);
+                EXPECT_EQ(A2Val->getChild(*FooDecl), BarVal);
               });
 }
 
 } // namespace