[clang][dataflow] Enable merging distinct values in Environment::join

[sgatev]

Summary

Make specializations of DataflowAnalysis extendable with domain-specific
logic for merging distinct values when joining environments. This could be
a strict lattice join or a more general widening operation.

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[sgatev]

Add missing include.

[xazax.hun]

Interesting. So clients can affect how the environment is being merged. As a result, we potentially cannot run multiple clients in the same fixed-point iteration, each of them will require separate passes.

I think this is OK, just wanted to to be explicit.

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

66

Previously, when the values were distinct, we did not include anything in the merged environment. With the new model, we will end up creating "default" values for every one of them. I wonder if this is wasteful. We could potentially also defer this until we have some real world data and can benchmark this. But I think we could consider changing the return type to bool to specify if the merged value should be included in the resulting environment at all and this could return false by default.

[sgatev]

Address reviewers' comments.

[sgatev]

Right. To model the behavior of a language feature (e.g. a simple model that tracks whether a std::optional value is engaged) clients can attach properties to symbolic values and decide how distinct values are joined. This doesn't completely rule out the possibility of running multiple clients in the same fixed-point iteration. In fact, we think this could be beneficial as clients can use each others' results by enriching the environment (e.g. dead code analysis can take advantage of understanding of whether a std::optional value is always (not) engaged). This is a direction that we're currently exploring. It does require some care to ensure that the clients are not stepping on each others' toes. For example, we should probably replace the current Properties mechanism with something more robust to ensure that properties are stored in isolated namespaces.

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

66

Good idea. Let's only include the merge value if necessary for now. I changed the interface to return a bool indicating whether the merged value should be included or not. I added a FIXME to consider not storing the constructed value in the context if it isn't necessary. I'd prefer to address that separately, to keep the scope of this patch smaller.

[xazax.hun]

I think the canonical approach most of the time is to have a map lattice that maps from values to your lattice elements. Storing properties directly at the object sounds like an interesting approach. I'll be curious to see how it works out. Do we expect the framework to propagate these properties automatically across copy ctors/copy assignments, move operations etc?

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

364

An alternative approach would be to just return false here and whenever the property lookup fails just assume the top value. Since this is just a simple test, feel free to leave this as is.

[sgatev]

Address reviewers' comments.

[sgatev]

Yes, I think we should be able to propagate properties across copy and move operations in the framework. Clients can override this behavior by modeling the copy and move operations and storing different values in the environment.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

364

Right. This seems simpler so let's go with it for now.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

 ///
 ///  `Derived` must be derived from a specialization of this class template and
 ///  must provide the following public members:
 ///   * `LatticeT initialElement()` - returns a lattice element that models the
 ///     initial state of a basic block;
 ///   * `void transfer(const Stmt *, LatticeT &, Environment &)` - applies the
 ///     analysis transfer function for a given statement and lattice element.
 ///
+///  `Derived` can optionally override the following members:
+///   * `void merge(QualType, const Value &, const Value &, Value &,
+///     Environment &)` -  joins distinct values. This could be a strict
+///     lattice join or a more general widening operation.
+///
 ///  `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
 ///  provide the following public members:
 ///   * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
 ///     argument by computing their least upper bound, modifies the object if
 ///     necessary, and returns an effect indicating whether any changes were
 ///     made to it;
 ///   * `bool operator==(const LatticeT &) const` - returns true if and only if
 ///     the object is equal to the argument.

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

 
 #include "clang/AST/Decl.h"
 #include "clang/AST/Expr.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include <cassert>
 #include <memory>
+#include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace clang {
 namespace dataflow {
 
 /// Owns objects that encompass the state of a program and stores context that
 /// is used during dataflow analysis.
 class DataflowAnalysisContext {
 public:
+  DataflowAnalysisContext()
+      : TrueVal(&takeOwnership(std::make_unique<BoolValue>())),
+        FalseVal(&takeOwnership(std::make_unique<BoolValue>())) {}
+
   /// Takes ownership of `Loc` and returns a reference to it.
   ///
   /// Requirements:
   ///
   ///  `Loc` must not be null.
-  StorageLocation &takeOwnership(std::unique_ptr<StorageLocation> Loc) {
+  template <typename T>
+  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
+  takeOwnership(std::unique_ptr<T> Loc) {
     assert(Loc != nullptr);
     Locs.push_back(std::move(Loc));
-    return *Locs.back().get();
+    return *cast<T>(Locs.back().get());
   }
 
   /// Takes ownership of `Val` and returns a reference to it.
   ///
   /// Requirements:
   ///
   ///  `Val` must not be null.
-  Value &takeOwnership(std::unique_ptr<Value> Val) {
+  template <typename T>
+  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
+  takeOwnership(std::unique_ptr<T> Val) {
     assert(Val != nullptr);
     Vals.push_back(std::move(Val));
-    return *Vals.back().get();
+    return *cast<T>(Vals.back().get());
   }
 
   /// Assigns `Loc` as the storage location of `D`.
   ///
   /// Requirements:
   ///
   ///  `D` must not be assigned a storage location.
   void setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
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 symbolic boolean value that models a boolean literal equal to
+  /// `Value`.
+  BoolValue &getBoolLiteralValue(bool Value) const {
+    return Value ? *TrueVal : *FalseVal;
+  }
+
 private:
   // Storage for the state of a program.
   std::vector<std::unique_ptr<StorageLocation>> Locs;
   std::vector<std::unique_ptr<Value>> Vals;
 
   // Maps from program declarations and statements to storage locations that are
   // assigned to them. These assignments are global (aggregated across all basic
   // blocks) and are used to produce stable storage locations when the same
   // basic blocks are evaluated multiple times. The storage locations that are
   // in scope for a particular basic block are stored in `Environment`.
   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
   llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
 
   StorageLocation *ThisPointeeLoc = nullptr;
 
   // FIXME: Add support for boolean expressions.
+  BoolValue *TrueVal;
+  BoolValue *FalseVal;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H

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

 #include "clang/AST/Type.h"
 #include "clang/AST/TypeOrdering.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include <type_traits>
+#include <utility>
 
 namespace clang {
 namespace dataflow {
 
 /// Indicates what kind of indirections should be skipped past when retrieving
 /// storage locations or values.
 ///
 /// FIXME: Consider renaming this or replacing it with a more appropriate model.
 /// See the discussion in https://reviews.llvm.org/D116596 for context.
 enum class SkipPast {
   /// No indirections should be skipped past.
   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,
 };
 
 /// Holds the state of the program (store and heap) at a given program point.
 class Environment {
 public:
+  /// Supplements `Environment` with non-standard join operations.
+  class Merger {
+  public:
+    virtual ~Merger() = default;
+
+    /// Given distinct `Val1` and `Val2`, modifies `MergedVal` to approximate
+    /// both `Val1` and `Val2`. This could be a strict lattice join, or a more
+    /// general widening operation. `MergedVal` will be assigned to a storage
+    /// location of type `Type`.
+    ///
+    /// Requirements:
+    ///
+    ///  `Val1` and `Val2` must be distinct.
+    virtual void merge(QualType Type, const Value &Val1, const Value &Val2,
+                       Value &MergedVal, Environment &Env) {}
+  };
+
   /// Creates an environment that uses `DACtx` to store objects that encompass
   /// the state of a program.
   explicit Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {}
 
   /// Creates an environment that uses `DACtx` to store objects that encompass
   /// the state of a program.
   ///
   /// If `DeclCtx` is a function, initializes the environment with symbolic
   /// representations of the function parameters.
   ///
   /// If `DeclCtx` is a non-static member function, initializes the environment
   /// with a symbolic representation of the `this` pointee.
   Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);
 
   bool operator==(const Environment &) const;
 
-  LatticeJoinEffect join(const Environment &);
+  LatticeJoinEffect join(const Environment &, Environment::Merger &);
 
   // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
   // `getStableStorageLocation`, or something more appropriate.
 
   /// Creates a storage location appropriate for `Type`. Does not assign a value
   /// to the returned storage location in the environment.
   ///
   /// Requirements:
public:
   /// is assigned a storage location in the environment, otherwise returns null.
   Value *getValue(const ValueDecl &D, SkipPast SP) const;
 
   /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
   /// is assigned a storage location in the environment, otherwise returns null.
   Value *getValue(const Expr &E, SkipPast SP) const;
 
   /// Transfers ownership of `Loc` to the analysis context and returns a
-  /// reference to `Loc`.
-  StorageLocation &takeOwnership(std::unique_ptr<StorageLocation> Loc);
+  /// reference to it.
+  ///
+  /// Requirements:
+  ///
+  ///  `Loc` must not be null.
+  template <typename T>
+  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
+  takeOwnership(std::unique_ptr<T> Loc) {
+    return DACtx->takeOwnership(std::move(Loc));
+  }
 
   /// Transfers ownership of `Val` to the analysis context and returns a
-  /// reference to `Val`.
-  Value &takeOwnership(std::unique_ptr<Value> Val);
+  /// reference to it.
+  ///
+  /// Requirements:
+  ///
+  ///  `Val` must not be null.
+  template <typename T>
+  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
+  takeOwnership(std::unique_ptr<T> Val) {
+    return DACtx->takeOwnership(std::move(Val));
+  }
+
+  /// Returns a symbolic boolean value that models a boolean literal equal to
+  /// `Value`
+  BoolValue &getBoolLiteralValue(bool Value) const {
+    return DACtx->getBoolLiteralValue(Value);
+  }
 
 private:
   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
   /// return null.
   ///
   /// Recursively initializes storage locations and values until it sees a
   /// self-referential pointer or reference type. `Visited` is used to track
   /// which types appeared in the reference/pointer chain in order to avoid

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

 ///
 ///  The type of the object stored in the container must be a bounded
 ///  join-semilattice.
 struct TypeErasedLattice {
   llvm::Any Value;
 };
 
 /// Type-erased base class for dataflow analyses built on a single lattice type.
-class TypeErasedDataflowAnalysis {
+class TypeErasedDataflowAnalysis : public Environment::Merger {
 public:
   virtual ~TypeErasedDataflowAnalysis() {}
 
   /// Returns the `ASTContext` that is used by the analysis.
   virtual ASTContext &getASTContext() = 0;
 
   /// Returns a type-erased lattice element that models the initial state of a
   /// basic block.

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

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
 
 #include "clang/AST/Decl.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
 #include <cassert>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
 /// Base class for all values computed by abstract interpretation.
 class Value {
 public:
-  enum class Kind { Integer, Reference, Pointer, Struct };
+  enum class Kind { Bool, Integer, Reference, Pointer, Struct };
 
   explicit Value(Kind ValKind) : ValKind(ValKind) {}
 
   virtual ~Value() = default;
 
   Kind getKind() const { return ValKind; }
 
 private:
   Kind ValKind;
 };
 
+/// Models a boolean.
+class BoolValue : public Value {
+public:
+  explicit BoolValue() : Value(Kind::Bool) {}
+
+  static bool classof(const Value *Val) { return Val->getKind() == Kind::Bool; }
+};
+
 /// Models an integer.
 class IntegerValue : public Value {
 public:
   explicit IntegerValue() : Value(Kind::Integer) {}
 
   static bool classof(const Value *Val) {
     return Val->getKind() == Kind::Integer;
   }
public:
 
   /// Returns the child value for `D`.
   Value &getChild(const ValueDecl &D) const {
     auto It = Children.find(&D);
     assert(It != Children.end());
     return *It->second;
   }
 
+  /// 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 {
+    auto It = Properties.find(Name);
+    return It == Properties.end() ? nullptr : It->second;
+  }
+
+  /// Assigns `Val` as the value of the synthetic property with the given
+  /// `Name`.
+  void setProperty(llvm::StringRef Name, Value &Val) {
+    Properties.insert_or_assign(Name, &Val);
+  }
+
 private:
   const llvm::DenseMap<const ValueDecl *, Value *> Children;
+  llvm::StringMap<Value *> Properties;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

Environment::Environment(DataflowAnalysisContext &DACtx,
   }
 }
 
 bool Environment::operator==(const Environment &Other) const {
   assert(DACtx == Other.DACtx);
   return DeclToLoc == Other.DeclToLoc && LocToVal == Other.LocToVal;
 }
 
-LatticeJoinEffect Environment::join(const Environment &Other) {
+LatticeJoinEffect Environment::join(const Environment &Other,
+                                    Environment::Merger &Merger) {
   assert(DACtx == Other.DACtx);
 
   auto Effect = LatticeJoinEffect::Unchanged;
 
   const unsigned DeclToLocSizeBefore = DeclToLoc.size();
   DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
   if (DeclToLocSizeBefore != DeclToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
   const unsigned ExprToLocSizeBefore = ExprToLoc.size();
   ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
   if (ExprToLocSizeBefore != ExprToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
-  // FIXME: Add support for joining distinct values that are assigned to the
-  // same storage locations in `LocToVal` and `Other.LocToVal`.
   const unsigned LocToValSizeBefore = LocToVal.size();
-  LocToVal = intersectDenseMaps(LocToVal, Other.LocToVal);
+  for (auto &Entry : LocToVal) {
+    const StorageLocation *Loc = Entry.first;
+    assert(Loc != nullptr);
+
+    Value *Val = Entry.second;
+    assert(Val != nullptr);
+
+    auto It = Other.LocToVal.find(Loc);
+    if (It == Other.LocToVal.end() || It->second == Val)
+      continue;
+    assert(It->second != nullptr);
+
+    if (Value *MergedVal = createValue(Loc->getType())) {
+      Merger.merge(Loc->getType(), *Val, *It->second, *MergedVal, *this);
+      setValue(*Loc, *MergedVal);
+    }
+  }
   if (LocToValSizeBefore != LocToVal.size())
     Effect = LatticeJoinEffect::Changed;
 
   return Effect;
 }
 
 StorageLocation &Environment::createStorageLocation(QualType Type) {
   assert(!Type.isNull());
if (Type->isStructureOrClassType()) {
 
     return &takeOwnership(
         std::make_unique<StructValue>(std::move(FieldValues)));
   }
 
   return nullptr;
 }
 
-StorageLocation &
-Environment::takeOwnership(std::unique_ptr<StorageLocation> Loc) {
-  return DACtx->takeOwnership(std::move(Loc));
-}
-
-Value &Environment::takeOwnership(std::unique_ptr<Value> Val) {
-  return DACtx->takeOwnership(std::move(Val));
-}
-
 StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
   switch (SP) {
   case SkipPast::None:
     return Loc;
   case SkipPast::Reference:
     // References cannot be chained so we only need to skip past one level of
     // indirection.
     if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
         BlockStates[Pred->getBlockID()];
     if (!MaybePredState.hasValue())
       continue;
 
     const TypeErasedDataflowAnalysisState &PredState =
         MaybePredState.getValue();
     if (MaybeState.hasValue()) {
       Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
-      MaybeState->Env.join(PredState.Env);
+      MaybeState->Env.join(PredState.Env, Analysis);
     } else {
       MaybeState = PredState;
     }
   }
   if (!MaybeState.hasValue()) {
     // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
     // to enable building analyses like computation of dominators that
     // initialize the state of each basic block differently.

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

std::function<void(
         Expectations,
     ArrayRef<std::string> Args,
     const tooling::FileContentMappings &VirtualMappedFiles = {}) {
   return checkDataflow(Code, ast_matchers::hasName(TargetFun),
                        std::move(MakeAnalysis), std::move(Expectations), Args,
                        VirtualMappedFiles);
 }
 
+/// Returns the `ValueDecl` for the given identifier.
+///
+/// Requirements:
+///
+///  `Name` must be unique in `ASTCtx`.
+const ValueDecl *findValueDecl(ASTContext &ASTCtx, llvm::StringRef Name);
+
 } // namespace test
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_

clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp

 #include "clang/Basic/TokenKinds.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Serialization/PCHContainerOperations.h"
 #include "clang/Tooling/ArgumentsAdjusters.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Testing/Support/Annotations.h"
+#include <cassert>
 #include <functional>
 #include <memory>
 #include <string>
 #include <system_error>
 #include <utility>
 #include <vector>
 
 using namespace clang;
 using namespace dataflow;
+using namespace ast_matchers;
 
 static bool
 isAnnotationDirectlyAfterStatement(const Stmt *Stmt, unsigned AnnotationBegin,
                                    const SourceManager &SourceManager,
                                    const LangOptions &LangOptions) {
   auto NextToken =
       Lexer::findNextToken(Stmt->getEndLoc(), SourceManager, LangOptions);
 
isAnnotationDirectlyAfterStatement(const Stmt *Stmt, unsigned AnnotationBegin,
   return true;
 }
 
 llvm::Expected<llvm::DenseMap<const Stmt *, std::string>>
 test::buildStatementToAnnotationMapping(const FunctionDecl *Func,
                                         llvm::Annotations AnnotatedCode) {
   llvm::DenseMap<const Stmt *, std::string> Result;
 
-  using namespace ast_matchers; // NOLINT: Too many names
   auto StmtMatcher =
       findAll(stmt(unless(anyOf(hasParent(expr()), hasParent(returnStmt()))))
                   .bind("stmt"));
 
   // This map should stay sorted because the binding algorithm relies on the
   // ordering of statement offsets
   std::map<unsigned, const Stmt *> Stmts;
   auto &Context = Func->getASTContext();
return llvm::createStringError(
         SourceManager.getLocForStartOfFile(SourceManager.getMainFileID())
             .getLocWithOffset(Annotations[I].Begin)
             .printToString(SourceManager)
             .data());
   }
 
   return Result;
 }
+
+const ValueDecl *test::findValueDecl(ASTContext &ASTCtx, llvm::StringRef Name) {
+  auto TargetNodes = match(valueDecl(hasName(Name)).bind("v"), ASTCtx);
+  assert(TargetNodes.size() == 1 && "Name must be unique");
+  auto *const Result = selectFirst<ValueDecl>("v", TargetNodes);
+  assert(Result != nullptr);
+  return Result;
+}

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "clang/Basic/LangStandard.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
-#include <cassert>
 #include <string>
 #include <utility>
 
 namespace {
 
 using namespace clang;
 using namespace dataflow;
+using namespace test;
 using ::testing::_;
 using ::testing::ElementsAre;
 using ::testing::IsNull;
 using ::testing::NotNull;
 using ::testing::Pair;
 
 class TransferTest : public ::testing::Test {
 protected:
ASSERT_THAT_ERROR(
             {"-fsyntax-only", "-fno-delayed-template-parsing",
              "-std=" +
                  std::string(
                      LangStandard::getLangStandardForKind(Std).getName())}),
         llvm::Succeeded());
   }
 };
 
-/// Returns the `ValueDecl` for the given identifier.
-///
-/// Requirements:
-///
-///  `Name` must be unique in `ASTCtx`.
-static const ValueDecl *findValueDecl(ASTContext &ASTCtx,
-                                      llvm::StringRef Name) {
-  auto TargetNodes = ast_matchers::match(
-      ast_matchers::valueDecl(ast_matchers::hasName(Name)).bind("v"), ASTCtx);
-  assert(TargetNodes.size() == 1 && "Name must be unique");
-  auto *const Result = ast_matchers::selectFirst<ValueDecl>("v", TargetNodes);
-  assert(Result != nullptr);
-  return Result;
-}
-
 TEST_F(TransferTest, IntVarDecl) {
   std::string Code = R"(
     void target() {
       int Foo;
       // [[p]]
     }
   )";
   runDataflow(

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

 //===- unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.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 "NoopAnalysis.h"
 #include "TestingSupport.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/ExprCXX.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cassert>
 #include <memory>
 #include <ostream>
 #include <string>
 #include <utility>
 #include <vector>
 
 namespace {
 
 using namespace clang;
 using namespace dataflow;
+using namespace test;
+using namespace ast_matchers;
+using ::testing::_;
+using ::testing::ElementsAre;
 using ::testing::IsEmpty;
+using ::testing::NotNull;
 using ::testing::Pair;
+using ::testing::Test;
 using ::testing::UnorderedElementsAre;
 
 template <typename AnalysisT>
 class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback {
 public:
   void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
     assert(BlockStates.empty());
 
void transfer(const Stmt *S, FunctionCallLattice &E, Environment &Env) {
     if (auto *C = dyn_cast<CallExpr>(S)) {
       if (auto *F = dyn_cast<FunctionDecl>(C->getCalleeDecl())) {
         E.CalledFunctions.insert(F->getNameInfo().getAsString());
       }
     }
   }
 };
 
-class NoreturnDestructorTest : public ::testing::Test {
+class NoreturnDestructorTest : public Test {
 protected:
   template <typename Matcher>
   void runDataflow(llvm::StringRef Code, Matcher Expectations) {
     tooling::FileContentMappings FilesContents;
     FilesContents.push_back(std::make_pair<std::string, std::string>(
         "noreturn_destructor_test_defs.h", R"(
       int foo();
 
std::string Code = R"(
     }
   )";
   runDataflow(Code, UnorderedElementsAre(
                         Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
                                       UnorderedElementsAre("baz", "foo"))))));
   // FIXME: Called functions at point `p` should contain only "foo".
 }
 
+class OptionalIntAnalysis
+    : public DataflowAnalysis<OptionalIntAnalysis, NoopLattice> {
+public:
+  explicit OptionalIntAnalysis(ASTContext &Context, BoolValue &HasValueTop)
+      : DataflowAnalysis<OptionalIntAnalysis, NoopLattice>(Context),
+        HasValueTop(HasValueTop) {}
+
+  static NoopLattice initialElement() { return {}; }
+
+  void transfer(const Stmt *S, NoopLattice &, Environment &Env) {
+    auto OptionalIntRecordDecl = recordDecl(hasName("OptionalInt"));
+    auto HasOptionalIntType = hasType(OptionalIntRecordDecl);
+
+    if (const auto *E = selectFirst<CXXConstructExpr>(
+            "call", match(cxxConstructExpr(HasOptionalIntType).bind("call"), *S,
+                          getASTContext()))) {
+      auto &ConstructorVal = *cast<StructValue>(Env.createValue(E->getType()));
+      ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(false));
+      Env.setValue(*Env.getStorageLocation(*E, SkipPast::None), ConstructorVal);
+    } else if (const auto *E = selectFirst<CXXOperatorCallExpr>(
+                   "call",
+                   match(cxxOperatorCallExpr(callee(cxxMethodDecl(ofClass(
+                                                 OptionalIntRecordDecl))))
+                             .bind("call"),
+                         *S, getASTContext()))) {
+      assert(E->getNumArgs() > 0);
+      auto *Object = E->getArg(0);
+      assert(Object != nullptr);
+
+      auto *ObjectLoc =
+          Env.getStorageLocation(*Object, SkipPast::ReferenceThenPointer);
+      assert(ObjectLoc != nullptr);
+
+      auto &ConstructorVal =
+          *cast<StructValue>(Env.createValue(Object->getType()));
+      ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(true));
+      Env.setValue(*ObjectLoc, ConstructorVal);
+    }
+  }
+
+  void merge(QualType Type, const Value &Val1, const Value &Val2,
+             Value &MergedVal, Environment &Env) final {
+    if (!Type->isRecordType() ||
+        Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
+      return;
+
+    auto *HasValue1 =
+        cast<BoolValue>(cast<StructValue>(&Val1)->getProperty("has_value"));
+    auto *HasValue2 =
+        cast<BoolValue>(cast<StructValue>(&Val2)->getProperty("has_value"));
+    if (HasValue1 == HasValue2) {
+      cast<StructValue>(&MergedVal)->setProperty("has_value", *HasValue1);
+    } else {
+      cast<StructValue>(&MergedVal)->setProperty("has_value", HasValueTop);
+    }
+  }
+
+private:
+  BoolValue &HasValueTop;
+};
+
+class WideningTest : public Test {
+protected:
+  template <typename Matcher>
+  void runDataflow(llvm::StringRef Code, Matcher Match) {
+    tooling::FileContentMappings FilesContents;
+    FilesContents.push_back(
+        std::make_pair<std::string, std::string>("widening_test_defs.h", R"(
+      struct OptionalInt {
+        OptionalInt() = default;
+        OptionalInt& operator=(int);
+      };
+    )"));
+    ASSERT_THAT_ERROR(
+        test::checkDataflow<OptionalIntAnalysis>(
+            Code, "target",
+            [this](ASTContext &Context, Environment &Env) {
+              assert(HasValueTop == nullptr);
+              HasValueTop = &Env.takeOwnership(std::make_unique<BoolValue>());
+              return OptionalIntAnalysis(Context, *HasValueTop);
+            },
+            [&Match](
+                llvm::ArrayRef<
+                    std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                    Results,
+                ASTContext &ASTCtx) { Match(Results, ASTCtx); },
+            {"-fsyntax-only", "-std=c++17"}, FilesContents),
+        llvm::Succeeded());
+  }
+
+  BoolValue &getHasValueTop() const {
+    assert(HasValueTop != nullptr);
+    return *HasValueTop;
+  }
+
+private:
+  BoolValue *HasValueTop = nullptr;
+};
+
+TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) {
+  std::string Code = R"(
+    #include "widening_test_defs.h"
+
+    void target(bool Cond) {
+      OptionalInt Foo;
+      /*[[p1]]*/
+      if (Cond) {
+        Foo = 1;
+        /*[[p2]]*/
+      }
+      (void)0;
+      /*[[p3]]*/
+    }
+  )";
+  runDataflow(
+      Code,
+      [this](llvm::ArrayRef<
+                 std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                 Results,
+             ASTContext &ASTCtx) {
+        ASSERT_THAT(Results,
+                    ElementsAre(Pair("p3", _), Pair("p2", _), Pair("p1", _)));
+        const Environment &Env1 = Results[2].second.Env;
+        const Environment &Env2 = Results[1].second.Env;
+        const Environment &Env3 = Results[0].second.Env;
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        auto GetFooValue = [FooDecl](const Environment &Env) {
+          return cast<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
+        };
+
+        EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
+                  &Env1.getBoolLiteralValue(false));
+        EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
+                  &Env2.getBoolLiteralValue(true));
+        EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
+                  &getHasValueTop());
+      });
+}
+
+TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) {
+  std::string Code = R"(
+    #include "widening_test_defs.h"
+
+    void target(bool Cond) {
+      OptionalInt Foo;
+      /*[[p1]]*/
+      if (Cond) {
+        Foo = 1;
+        /*[[p2]]*/
+      } else {
+        Foo = 2;
+        /*[[p3]]*/
+      }
+      (void)0;
+      /*[[p4]]*/
+    }
+  )";
+  runDataflow(
+      Code, [](llvm::ArrayRef<
+                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                   Results,
+               ASTContext &ASTCtx) {
+        ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _),
+                                         Pair("p2", _), Pair("p1", _)));
+        const Environment &Env1 = Results[3].second.Env;
+        const Environment &Env2 = Results[2].second.Env;
+        const Environment &Env3 = Results[1].second.Env;
+        const Environment &Env4 = Results[0].second.Env;
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        auto GetFooValue = [FooDecl](const Environment &Env) {
+          return cast<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
+        };
+
+        EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
+                  &Env1.getBoolLiteralValue(false));
+        EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
+                  &Env2.getBoolLiteralValue(true));
+        EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
+                  &Env3.getBoolLiteralValue(true));
+        EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
+                  &Env4.getBoolLiteralValue(true));
+      });
+}
+
 } // namespace