[clang][dataflow] Handle null pointers of type std::nullptr_t

[li.zhe.hua]

Summary

Treat std::nullptr_t as a regular scalar type to avoid tripping
assertions when analyzing code that uses std::nullptr_t.

[gribozavr2]

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

61

Could you add a comment to the header that a caller may pass a null PointeeType as a "pointee" of a nullptr_t?

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

2217–2225

[li.zhe.hua]

Address comments.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

96

This is inconsistent with the change introduced by this patch.

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

27

What does that mean? We are analyzing an incomplete translation unit? Why would the type ever be null here?

[li.zhe.hua]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

96

Ah, you're correct. I can mail a fix out later today.

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

27

See the motivating test case:

// Alternatively, use `std::nullptr_t` instead of `my_nullptr_t`.
using my_nullptr_t = decltype(nullptr);
my_nullptr_t Null = 0;

This triggers getOrCreateNullPointerValue to be called with a null pointee type.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

takeOwnership(std::unique_ptr<T> Val) {
     Vals.push_back(std::move(Val));
     return *cast<T>(Vals.back().get());
   }
 
   /// Returns a stable storage location appropriate for `Type`.
   ///
   /// Requirements:
   ///
   ///  `Type` must not be null.
   StorageLocation &getStableStorageLocation(QualType Type);
 
   /// Returns a stable storage location for `D`.
   StorageLocation &getStableStorageLocation(const VarDecl &D);
 
   /// Returns a stable storage location for `E`.
   StorageLocation &getStableStorageLocation(const Expr &E);
 
public:
   /// Returns the storage location assigned to the `this` pointee or null if the
   /// `this` pointee has no assigned storage location.
   StorageLocation *getThisPointeeStorageLocation() const {
     return ThisPointeeLoc;
   }
 
   /// Returns a pointer value that represents a null pointer. Calls with
   /// `PointeeType` that are canonically equivalent will return the same result.
+  /// A null `PointeeType` can be used for the pointee of `std::nullptr_t`.
   PointerValue &getOrCreateNullPointerValue(QualType PointeeType);
 
   /// Returns a symbolic boolean value that models a boolean literal equal to
   /// `Value`.
   AtomicBoolValue &getBoolLiteralValue(bool Value) const {
     return Value ? TrueVal : FalseVal;
   }
 
public:
   bool flowConditionIsTautology(AtomicBoolValue &Token);
 
   /// Returns true if `Val1` is equivalent to `Val2`.
   /// Note: This function doesn't take into account constraints on `Val1` and
   /// `Val2` imposed by the flow condition.
   bool equivalentBoolValues(BoolValue &Val1, BoolValue &Val2);
 
 private:
+  struct NullableQualTypeDenseMapInfo : private llvm::DenseMapInfo<QualType> {
+    static QualType getEmptyKey() {
+      // Allow a NULL `QualType` by using a different value as the empty key.
+      return QualType::getFromOpaquePtr(reinterpret_cast<Type *>(1));
+    }
+
+    using DenseMapInfo::getHashValue;
+    using DenseMapInfo::getTombstoneKey;
+    using DenseMapInfo::isEqual;
+  };
+
   /// Adds all constraints of the flow condition identified by `Token` and all
   /// of its transitive dependencies to `Constraints`. `VisitedTokens` is used
   /// to track tokens of flow conditions that were already visited by recursive
   /// calls.
   void addTransitiveFlowConditionConstraints(
       AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
       llvm::DenseSet<AtomicBoolValue *> &VisitedTokens);
 
private:
   StorageLocation *ThisPointeeLoc = nullptr;
 
   // Null pointer values, keyed by the canonical pointee type.
   //
   // FIXME: The pointer values are indexed by the pointee types which are
   // required to initialize the `PointeeLoc` field in `PointerValue`. Consider
   // creating a type-independent `NullPointerValue` without a `PointeeLoc`
   // field.
-  llvm::DenseMap<QualType, PointerValue *> NullPointerVals;
+  llvm::DenseMap<QualType, PointerValue *, NullableQualTypeDenseMapInfo>
+      NullPointerVals;
 
   AtomicBoolValue &TrueVal;
   AtomicBoolValue &FalseVal;
 
   // Indices that are used to avoid recreating the same composite boolean
   // values.
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ConjunctionValue *>
       ConjunctionVals;

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
 StorageLocation &
 DataflowAnalysisContext::getStableStorageLocation(QualType Type) {
-  assert(!Type.isNull());
-  if (Type->isStructureOrClassType() || Type->isUnionType()) {
+  if (!Type.isNull() &&
+      (Type->isStructureOrClassType() || Type->isUnionType())) {
     // FIXME: Explore options to avoid eager initialization of fields as some of
     // them might not be needed for a particular analysis.
     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
     for (const FieldDecl *Field : getObjectFields(Type))
       FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())});
     return takeOwnership(
         std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
   }
if (auto *Loc = getStorageLocation(E))
     return *Loc;
   auto &Loc = getStableStorageLocation(E.getType());
   setStorageLocation(E, Loc);
   return Loc;
 }
 
 PointerValue &
 DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
-  assert(!PointeeType.isNull());
-  auto CanonicalPointeeType = PointeeType.getCanonicalType();
+  auto CanonicalPointeeType =
+      PointeeType.isNull() ? PointeeType : PointeeType.getCanonicalType();
   auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
   if (Res.second) {
     auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
     Res.first->second =
         &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
   }
   return *Res.first->second;
 }

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                 EXPECT_TRUE(isa<BoolValue>(FooVal));
                 EXPECT_TRUE(isa<BoolValue>(BarVal));
                 EXPECT_EQ(FooVal, BarVal);
               });
 }
 
 TEST(TransferTest, NullToPointerCast) {
   std::string Code = R"(
+    using my_nullptr_t = decltype(nullptr);
     struct Baz {};
     void target() {
       int *FooX = nullptr;
       int *FooY = nullptr;
       bool **Bar = nullptr;
       Baz *Baz = nullptr;
+      my_nullptr_t Null = 0;
       // [[p]]
     }
   )";
   runDataflow(Code,
               [](llvm::ArrayRef<
                      std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                      Results,
                  ASTContext &ASTCtx) {
                 ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
                 const Environment &Env = Results[0].second.Env;
 
                 const ValueDecl *FooXDecl = findValueDecl(ASTCtx, "FooX");
                 ASSERT_THAT(FooXDecl, NotNull());
 
                 const ValueDecl *FooYDecl = findValueDecl(ASTCtx, "FooY");
                 ASSERT_THAT(FooYDecl, NotNull());
 
                 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
                 ASSERT_THAT(BarDecl, NotNull());
 
                 const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
                 ASSERT_THAT(BazDecl, NotNull());
 
+                const ValueDecl *NullDecl = findValueDecl(ASTCtx, "Null");
+                ASSERT_THAT(NullDecl, NotNull());
+
                 const auto *FooXVal =
                     cast<PointerValue>(Env.getValue(*FooXDecl, SkipPast::None));
                 const auto *FooYVal =
                     cast<PointerValue>(Env.getValue(*FooYDecl, SkipPast::None));
                 const auto *BarVal =
                     cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
                 const auto *BazVal =
                     cast<PointerValue>(Env.getValue(*BazDecl, SkipPast::None));
+                const auto *NullVal =
+                    cast<PointerValue>(Env.getValue(*NullDecl, SkipPast::None));
 
                 EXPECT_EQ(FooXVal, FooYVal);
                 EXPECT_NE(FooXVal, BarVal);
                 EXPECT_NE(FooXVal, BazVal);
                 EXPECT_NE(BarVal, BazVal);
 
                 const StorageLocation &FooPointeeLoc = FooXVal->getPointeeLoc();
                 EXPECT_TRUE(isa<ScalarStorageLocation>(FooPointeeLoc));
                 EXPECT_THAT(Env.getValue(FooPointeeLoc), IsNull());
 
                 const StorageLocation &BarPointeeLoc = BarVal->getPointeeLoc();
                 EXPECT_TRUE(isa<ScalarStorageLocation>(BarPointeeLoc));
                 EXPECT_THAT(Env.getValue(BarPointeeLoc), IsNull());
 
                 const StorageLocation &BazPointeeLoc = BazVal->getPointeeLoc();
                 EXPECT_TRUE(isa<AggregateStorageLocation>(BazPointeeLoc));
                 EXPECT_THAT(Env.getValue(BazPointeeLoc), IsNull());
+
+                const StorageLocation &NullPointeeLoc =
+                    NullVal->getPointeeLoc();
+                EXPECT_TRUE(isa<ScalarStorageLocation>(NullPointeeLoc));
+                EXPECT_THAT(Env.getValue(NullPointeeLoc), IsNull());
               });
 }
 
 TEST(TransferTest, NullToMemberPointerCast) {
   std::string Code = R"(
     struct Foo {};
     void target(Foo *Foo) {
       int Foo::*MemberPointer = nullptr;