[clang][dataflow] Generalize custom comparison to return tri-value result.

[ymandel]

Summary

Currently, the API for a model's custom value comparison returns a
boolean. Therefore, models cannot distinguish between situations where the
values are recognized by the model and different and those where the values are
just not recognized. This patch changes the return value to a tri-valued enum,
allowing models to express "don't know".

This patch is essentially a NFC -- no practical differences result from this
change in this patch. But, it prepares for future patches (particularly,
upcoming patches for widening) which will take advantage of the new flexibility.

Driveby: fixed spelling of IsOptionalType to match style guide.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

52

Alternative that I slightly prefer - ComparisonResult.

75

Perhaps replace "does not" with "can't"?

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

365–366

Why is it same if IsSet1 is null and IsSet2 isn't null?

1185

Why remove this? It's not the same as the default implementation, right?

[ymandel]

address comments

[ymandel]

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

365–366

Fixed. that was a mistake.

1185

Correct -- that was a mistake (I think my first version had a sound default, which I later put back as unsound to keep this NFC).

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

73–74

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

1188–1191

[ymandel]

address comments

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

enum class SkipPast {
   None,
   /// An optional reference should be skipped past.
   Reference,
   /// An optional reference should be skipped past, then an optional pointer
   /// should be skipped past.
   ReferenceThenPointer,
 };
 
+/// Indicates the result of a tentative comparison.
+enum class ComparisonResult {
+  Same,
+  Different,
+  Unknown,
+};
+
 /// Holds the state of the program (store and heap) at a given program point.
 ///
 /// WARNING: Symbolic values that are created by the environment for static
 /// local and global variables are not currently invalidated on function calls.
 /// This is unsound and should be taken into account when designing dataflow
 /// analyses.
 class Environment {
 public:
   /// Supplements `Environment` with non-standard comparison and join
   /// operations.
   class ValueModel {
   public:
     virtual ~ValueModel() = default;
 
-    /// Returns true if and only if `Val1` is equivalent to `Val2`.
+    /// Returns:
+    ///   `Same`: `Val1` is equivalent to `Val2`, according to the model.
+    ///   `Different`: `Val1` is distinct from `Val2`, according to the model.
+    ///   `Unknown`: The model can't determine a relationship between `Val1` and
+    ///    `Val2`.
     ///
     /// Requirements:
     ///
     ///  `Val1` and `Val2` must be distinct.
     ///
     ///  `Val1` and `Val2` must model values of type `Type`.
     ///
     ///  `Val1` and `Val2` must be assigned to the same storage location in
     ///  `Env1` and `Env2` respectively.
-    virtual bool compareEquivalent(QualType Type, const Value &Val1,
+    virtual ComparisonResult compare(QualType Type, const Value &Val1,
                                      const Environment &Env1, const Value &Val2,
                                      const Environment &Env2) {
       // FIXME: Consider adding QualType to StructValue and removing the Type
       // argument here.
       //
-      // FIXME: default to a sound comparison and/or expand the comparison logic
-      // built into the framework to support broader forms of equivalence than
-      // strict pointer equality.
-      return true;
+      // FIXME: default to a sound comparison (`Unknown`) and/or expand the
+      // comparison logic built into the framework to support broader forms of
+      // equivalence than strict pointer equality.
+      return ComparisonResult::Same;
     }
 
     /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could
     /// be a strict lattice join or a more general widening operation.
     ///
     /// If this function returns true, `MergedVal` will be assigned to a storage
     /// location of type `Type` in `MergedEnv`.
     ///

clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h

public:
 
   /// Returns a matcher for the optional classes covered by this model.
   static ast_matchers::DeclarationMatcher optionalClassDecl();
 
   static NoopLattice initialElement() { return {}; }
 
   void transfer(const CFGElement *Elt, NoopLattice &L, Environment &Env);
 
-  bool compareEquivalent(QualType Type, const Value &Val1,
+  ComparisonResult compare(QualType Type, const Value &Val1,
                            const Environment &Env1, const Value &Val2,
                            const Environment &Env2) override;
 
   bool merge(QualType Type, const Value &Val1, const Environment &Env1,
              const Value &Val2, const Environment &Env2, Value &MergedVal,
              Environment &MergedEnv) override;
 
 private:
   CFGMatchSwitch<TransferState<NoopLattice>> TransferMatchSwitch;
 };

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

for (auto &Entry : LocToVal) {
     assert(Val != nullptr);
 
     auto It = Other.LocToVal.find(Loc);
     if (It == Other.LocToVal.end())
       continue;
     assert(It->second != nullptr);
 
     if (!areEquivalentValues(*Val, *It->second) &&
-        !Model.compareEquivalent(Loc->getType(), *Val, *this, *It->second,
-                                 Other))
+        Model.compare(Loc->getType(), *Val, *this, *It->second, Other) !=
+            ComparisonResult::Same)
       return false;
   }
 
   return true;
 }
 
 LatticeJoinEffect Environment::join(const Environment &Other,
                                     Environment::ValueModel &Model) {

clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp

 
 /// If `Type` is a reference type, returns the type of its pointee. Otherwise,
 /// returns `Type` itself.
 QualType stripReference(QualType Type) {
   return Type->isReferenceType() ? Type->getPointeeType() : Type;
 }
 
 /// Returns true if and only if `Type` is an optional type.
-bool IsOptionalType(QualType Type) {
+bool isOptionalType(QualType Type) {
   if (!Type->isRecordType())
     return false;
   // FIXME: Optimize this by avoiding the `getQualifiedNameAsString` call.
   auto TypeName = Type->getAsCXXRecordDecl()->getQualifiedNameAsString();
   return TypeName == "std::optional" || TypeName == "absl::optional" ||
          TypeName == "base::Optional";
 }
 
 /// Returns the number of optional wrappers in `Type`.
 ///
 /// For example, if `Type` is `optional<optional<int>>`, the result of this
 /// function will be 2.
 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
-  if (!IsOptionalType(Type))
+  if (!isOptionalType(Type))
     return 0;
   return 1 + countOptionalWrappers(
                  ASTCtx,
                  cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
                      ->getTemplateArgs()
                      .get(0)
                      .getAsType()
                      .getDesugaredType(ASTCtx));
: DataflowAnalysis<UncheckedOptionalAccessModel, NoopLattice>(Ctx),
       TransferMatchSwitch(buildTransferMatchSwitch(Options)) {}
 
 void UncheckedOptionalAccessModel::transfer(const CFGElement *Elt,
                                             NoopLattice &L, Environment &Env) {
   LatticeTransferState State(L, Env);
   TransferMatchSwitch(*Elt, getASTContext(), State);
 }
 
-bool UncheckedOptionalAccessModel::compareEquivalent(QualType Type,
-                                                     const Value &Val1,
-                                                     const Environment &Env1,
-                                                     const Value &Val2,
-                                                     const Environment &Env2) {
-  return isNonEmptyOptional(Val1, Env1) == isNonEmptyOptional(Val2, Env2);
+ComparisonResult UncheckedOptionalAccessModel::compare(
+    QualType Type, const Value &Val1, const Environment &Env1,
+    const Value &Val2, const Environment &Env2) {
+  if (!isOptionalType(Type))
+    return ComparisonResult::Unknown;
+  return isNonEmptyOptional(Val1, Env1) == isNonEmptyOptional(Val2, Env2)
+             ? ComparisonResult::Same
+             : ComparisonResult::Different;
 }
 
 bool UncheckedOptionalAccessModel::merge(QualType Type, const Value &Val1,
                                          const Environment &Env1,
                                          const Value &Val2,
                                          const Environment &Env2,
                                          Value &MergedVal,
                                          Environment &MergedEnv) {
-  if (!IsOptionalType(Type))
+  if (!isOptionalType(Type))
     return true;
 
   auto &HasValueVal = MergedEnv.makeAtomicBoolValue();
   if (isNonEmptyOptional(Val1, Env1) && isNonEmptyOptional(Val2, Env2))
     MergedEnv.addToFlowCondition(HasValueVal);
   else if (isEmptyOptional(Val1, Env1) && isEmptyOptional(Val2, Env2))
     MergedEnv.addToFlowCondition(MergedEnv.makeNot(HasValueVal));
   setHasValue(MergedVal, HasValueVal);

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

if (const auto *E = selectFirst<CXXConstructExpr>(
       assert(ObjectLoc != nullptr);
 
       auto &ConstructorVal = *Env.createValue(Object->getType());
       ConstructorVal.setProperty("is_set", Env.getBoolLiteralValue(true));
       Env.setValue(*ObjectLoc, ConstructorVal);
     }
   }
 
-  bool compareEquivalent(QualType Type, const Value &Val1,
+  ComparisonResult compare(QualType Type, const Value &Val1,
                            const Environment &Env1, const Value &Val2,
                            const Environment &Env2) override {
     const auto *Decl = Type->getAsCXXRecordDecl();
     if (Decl == nullptr || Decl->getIdentifier() == nullptr ||
         Decl->getName() != "SpecialBool")
-      return false;
+      return ComparisonResult::Unknown;
 
     auto *IsSet1 = cast_or_null<BoolValue>(Val1.getProperty("is_set"));
+    auto *IsSet2 = cast_or_null<BoolValue>(Val2.getProperty("is_set"));
     if (IsSet1 == nullptr)
-      return true;
+      return IsSet2 == nullptr ? ComparisonResult::Same
+                               : ComparisonResult::Different;
 
-    auto *IsSet2 = cast_or_null<BoolValue>(Val2.getProperty("is_set"));
     if (IsSet2 == nullptr)
-      return false;
+      return ComparisonResult::Different;
 
     return Env1.flowConditionImplies(*IsSet1) ==
-           Env2.flowConditionImplies(*IsSet2);
+                   Env2.flowConditionImplies(*IsSet2)
+               ? ComparisonResult::Same
+               : ComparisonResult::Different;
   }
 
   // Always returns `true` to accept the `MergedVal`.
   bool merge(QualType Type, const Value &Val1, const Environment &Env1,
              const Value &Val2, const Environment &Env2, Value &MergedVal,
              Environment &MergedEnv) override {
     const auto *Decl = Type->getAsCXXRecordDecl();
     if (Decl == nullptr || Decl->getIdentifier() == nullptr ||
if (const auto *E = selectFirst<CXXConstructExpr>(
       assert(ObjectLoc != nullptr);
 
       auto &ConstructorVal = *Env.createValue(Object->getType());
       ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(true));
       Env.setValue(*ObjectLoc, ConstructorVal);
     }
   }
 
-  bool compareEquivalent(QualType Type, const Value &Val1,
+  ComparisonResult compare(QualType Type, const Value &Val1,
                            const Environment &Env1, const Value &Val2,
                            const Environment &Env2) override {
     // Nothing to say about a value that does not model an `OptionalInt`.
     if (!Type->isRecordType() ||
         Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
-      return false;
+      return ComparisonResult::Unknown;
 
     auto *Prop1 = Val1.getProperty("has_value");
     auto *Prop2 = Val2.getProperty("has_value");
     assert(Prop1 != nullptr && Prop2 != nullptr);
-    return areEquivalentValues(*Prop1, *Prop2);
+    return areEquivalentValues(*Prop1, *Prop2) ? ComparisonResult::Same
+                                               : ComparisonResult::Different;
   }
 
   bool merge(QualType Type, const Value &Val1, const Environment &Env1,
              const Value &Val2, const Environment &Env2, Value &MergedVal,
              Environment &MergedEnv) override {
     // Nothing to say about a value that does not model an `OptionalInt`.
     if (!Type->isRecordType() ||
         Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
SmallVector<BoundNodes, 1> Matches =
         match(callExpr(callee(functionDecl(hasName("makeTop")))).bind("top"),
               *S, getASTContext());
     if (const auto *E = selectFirst<CallExpr>("top", Matches)) {
       auto &Loc = Env.createStorageLocation(*E);
       Env.setValue(Loc, Env.makeTopBoolValue());
       Env.setStorageLocation(*E, Loc);
     }
   }
 
-  bool compareEquivalent(QualType Type, const Value &Val1,
+  ComparisonResult compare(QualType Type, const Value &Val1,
                            const Environment &Env1, const Value &Val2,
                            const Environment &Env2) override {
     // Changes to a sound approximation, which allows us to test whether we can
     // (soundly) converge for some loops.
-    return false;
+    return ComparisonResult::Unknown;
   }
 };
 
 class TopTest : public Test {
 protected:
   template <typename Matcher>
   void runDataflow(llvm::StringRef Code, Matcher VerifyResults) {
     ASSERT_THAT_ERROR(