[clang][dataflow] Model the behavior of various optional members

[sgatev]

Summary

Model make_optional, optional's default constructor, emplace,
reset, and operator bool members.

[xazax.hun]

Thanks!

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

64

Nit: unintended change?

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

34

I wonder if it is more sustainable in the long term to have these headers in a separate file and #include them here (and build the raw string literal with a macro if that is possible at all).

[sgatev]

Address reviewers' comments.

[sgatev]

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

34

Yeap, I agree that would be better. I'll consider some options and send a patch to move them out of here.

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

 #include "clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/Stmt.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/MatchSwitch.h"
 #include "clang/Analysis/FlowSensitive/SourceLocationsLattice.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
+#include <memory>
+#include <utility>
 
 namespace clang {
 namespace dataflow {
 namespace {
 
 using namespace ::clang::ast_matchers;
 
 using LatticeTransferState = TransferState<SourceLocationsLattice>;
return cxxMemberCallExpr(
       callee(cxxMethodDecl(hasName(MemberName), ofClass(optionalClass()))));
 }
 
 static auto isOptionalOperatorCallWithName(llvm::StringRef OperatorName) {
   return cxxOperatorCallExpr(hasOverloadedOperatorName(OperatorName),
                              callee(cxxMethodDecl(ofClass(optionalClass()))));
 }
 
+static auto isMakeOptionalCall() {
+  return callExpr(
+      callee(functionDecl(hasAnyName(
+          "std::make_optional", "base::make_optional", "absl::make_optional"))),
+      hasOptionalType());
+}
+
+/// Creates a symbolic value for an `optional` value using `HasValueVal` as the
+/// symbolic value of its "has_value" property.
+StructValue &createOptionalValue(Environment &Env, BoolValue &HasValueVal) {
+  auto OptionalVal = std::make_unique<StructValue>();
+  OptionalVal->setProperty("has_value", HasValueVal);
+  return Env.takeOwnership(std::move(OptionalVal));
+}
+
 /// Returns the symbolic value that represents the "has_value" property of the
 /// optional value `Val`. Returns null if `Val` is null.
 static BoolValue *getHasValue(Value *Val) {
   if (auto *OptionalVal = cast_or_null<StructValue>(Val)) {
     return cast<BoolValue>(OptionalVal->getProperty("has_value"));
   }
   return nullptr;
 }
 
 static void initializeOptionalReference(const Expr *OptionalExpr,
                                         LatticeTransferState &State) {
   if (auto *OptionalVal = cast_or_null<StructValue>(
if (auto *OptionalVal = cast_or_null<StructValue>(
     if (State.Env.flowConditionImplies(*HasValueVal))
       return;
   }
 
   // Record that this unwrap is *not* provably safe.
   State.Lattice.getSourceLocations().insert(ObjectExpr->getBeginLoc());
 }
 
+void transferMakeOptionalCall(const CallExpr *E, LatticeTransferState &State) {
+  auto &Loc = State.Env.createStorageLocation(*E);
+  State.Env.setStorageLocation(*E, Loc);
+  State.Env.setValue(
+      Loc, createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
+}
+
 static void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
                                          LatticeTransferState &State) {
   if (auto *OptionalVal = cast_or_null<StructValue>(
           State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
                              SkipPast::ReferenceThenPointer))) {
     auto *HasValueVal = getHasValue(OptionalVal);
     assert(HasValueVal != nullptr);
 
     auto &CallExprLoc = State.Env.createStorageLocation(*CallExpr);
     State.Env.setValue(CallExprLoc, *HasValueVal);
     State.Env.setStorageLocation(*CallExpr, CallExprLoc);
   }
 }
 
+void transferEmplaceCall(const CXXMemberCallExpr *E,
+                         LatticeTransferState &State) {
+  if (auto *OptionalLoc = State.Env.getStorageLocation(
+          *E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer)) {
+    State.Env.setValue(
+        *OptionalLoc,
+        createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
+  }
+}
+
+void transferResetCall(const CXXMemberCallExpr *E,
+                       LatticeTransferState &State) {
+  if (auto *OptionalLoc = State.Env.getStorageLocation(
+          *E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer)) {
+    State.Env.setValue(
+        *OptionalLoc,
+        createOptionalValue(State.Env, State.Env.getBoolLiteralValue(false)));
+  }
+}
+
 static auto buildTransferMatchSwitch() {
   return MatchSwitchBuilder<LatticeTransferState>()
       // Attach a symbolic "has_value" state to optional values that we see for
       // the first time.
       .CaseOf(expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()),
               initializeOptionalReference)
 
+      // make_optional
+      .CaseOf(isMakeOptionalCall(), transferMakeOptionalCall)
+
       // optional::value
       .CaseOf(
           isOptionalMemberCallWithName("value"),
           +[](const CXXMemberCallExpr *E, LatticeTransferState &State) {
             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
           })
 
       // optional::operator*, optional::operator->
       .CaseOf(
           expr(anyOf(isOptionalOperatorCallWithName("*"),
                      isOptionalOperatorCallWithName("->"))),
           +[](const CallExpr *E, LatticeTransferState &State) {
             transferUnwrapCall(E, E->getArg(0), State);
           })
 
       // optional::has_value
       .CaseOf(isOptionalMemberCallWithName("has_value"),
               transferOptionalHasValueCall)
 
+      // optional::operator bool
+      .CaseOf(isOptionalMemberCallWithName("operator bool"),
+              transferOptionalHasValueCall)
+
+      // optional::emplace
+      .CaseOf(isOptionalMemberCallWithName("emplace"), transferEmplaceCall)
+
+      // optional::reset
+      .CaseOf(isOptionalMemberCallWithName("reset"), transferResetCall)
+
       .Build();
 }
 
 } // namespace
 
 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx)
     : DataflowAnalysis<UncheckedOptionalAccessModel, SourceLocationsLattice>(
           Ctx),

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

 
 using namespace clang;
 using namespace dataflow;
 using namespace test;
 
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
+// FIXME: Move header definitions in separate file(s).
 static constexpr char StdTypeTraitsHeader[] = R"(
+#ifndef TYPE_TRAITS_H
+#define TYPE_TRAITS_H
+
 namespace std {
 
+typedef decltype(sizeof(char)) size_t;
+
+template <typename T, T V>
+struct integral_constant {
+  static constexpr T value = V;
+};
+
+using true_type = integral_constant<bool, true>;
+using false_type = integral_constant<bool, false>;
+
 template< class T > struct remove_reference      {typedef T type;};
 template< class T > struct remove_reference<T&>  {typedef T type;};
 template< class T > struct remove_reference<T&&> {typedef T type;};
 
 template <class T>
   using remove_reference_t = typename remove_reference<T>::type;
 
+template <class T>
+struct remove_extent {
+  typedef T type;
+};
+
+template <class T>
+struct remove_extent<T[]> {
+  typedef T type;
+};
+
+template <class T, size_t N>
+struct remove_extent<T[N]> {
+  typedef T type;
+};
+
+template <class T>
+struct is_array : false_type {};
+
+template <class T>
+struct is_array<T[]> : true_type {};
+
+template <class T, size_t N>
+struct is_array<T[N]> : true_type {};
+
+template <class>
+struct is_function : false_type {};
+
+template <class Ret, class... Args>
+struct is_function<Ret(Args...)> : true_type {};
+
+namespace detail {
+
+template <class T>
+struct type_identity {
+  using type = T;
+};  // or use type_identity (since C++20)
+
+template <class T>
+auto try_add_pointer(int) -> type_identity<typename remove_reference<T>::type*>;
+template <class T>
+auto try_add_pointer(...) -> type_identity<T>;
+
+}  // namespace detail
+
+template <class T>
+struct add_pointer : decltype(detail::try_add_pointer<T>(0)) {};
+
+template <bool B, class T, class F>
+struct conditional {
+  typedef T type;
+};
+
+template <class T, class F>
+struct conditional<false, T, F> {
+  typedef F type;
+};
+
+template <class T>
+struct remove_cv {
+  typedef T type;
+};
+template <class T>
+struct remove_cv<const T> {
+  typedef T type;
+};
+template <class T>
+struct remove_cv<volatile T> {
+  typedef T type;
+};
+template <class T>
+struct remove_cv<const volatile T> {
+  typedef T type;
+};
+
+template <class T>
+struct decay {
+ private:
+  typedef typename remove_reference<T>::type U;
+
+ public:
+  typedef typename conditional<
+      is_array<U>::value, typename remove_extent<U>::type*,
+      typename conditional<is_function<U>::value, typename add_pointer<U>::type,
+                           typename remove_cv<U>::type>::type>::type type;
+};
+
 } // namespace std
+
+#endif // TYPE_TRAITS_H
 )";
 
 static constexpr char StdUtilityHeader[] = R"(
+#ifndef UTILITY_H
+#define UTILITY_H
+
 #include "std_type_traits.h"
 
 namespace std {
 
 template <typename T>
-constexpr std::remove_reference_t<T>&& move(T&& x);
+constexpr remove_reference_t<T>&& move(T&& x);
+
+} // namespace std
+
+#endif // UTILITY_H
+)";
+
+static constexpr char StdInitializerListHeader[] = R"(
+#ifndef INITIALIZER_LIST_H
+#define INITIALIZER_LIST_H
+
+namespace std {
+
+template <typename T>
+class initializer_list {
+ public:
+  initializer_list() noexcept;
+};
 
 } // namespace std
+
+#endif // INITIALIZER_LIST_H
 )";
 
 static constexpr char StdOptionalHeader[] = R"(
+#include "std_initializer_list.h"
+#include "std_type_traits.h"
+#include "std_utility.h"
+
 namespace std {
 
 template <typename T>
 class optional {
  public:
   constexpr optional() noexcept;
 
   const T& operator*() const&;
   T& operator*() &;
   const T&& operator*() const&&;
   T&& operator*() &&;
 
   const T* operator->() const;
   T* operator->();
 
   const T& value() const&;
   T& value() &;
   const T&& value() const&&;
   T&& value() &&;
 
+  template <typename U>
+  constexpr T value_or(U&& v) const&;
+  template <typename U>
+  T value_or(U&& v) &&;
+
+  template <typename... Args>
+  T& emplace(Args&&... args);
+
+  template <typename U, typename... Args>
+  T& emplace(std::initializer_list<U> ilist, Args&&... args);
+
+  void reset() noexcept;
+
+  constexpr explicit operator bool() const noexcept;
   constexpr bool has_value() const noexcept;
 };
 
+template <typename T>
+constexpr optional<typename std::decay<T>::type> make_optional(T&& v);
+
+template <typename T, typename... Args>
+constexpr optional<T> make_optional(Args&&... args);
+
+template <typename T, typename U, typename... Args>
+constexpr optional<T> make_optional(std::initializer_list<U> il,
+                                    Args&&... args);
+
 } // namespace std
 )";
 
 static constexpr char AbslOptionalHeader[] = R"(
+#include "std_initializer_list.h"
+#include "std_type_traits.h"
+#include "std_utility.h"
+
 namespace absl {
 
 template <typename T>
 class optional {
  public:
   constexpr optional() noexcept;
 
   const T& operator*() const&;
   T& operator*() &;
   const T&& operator*() const&&;
   T&& operator*() &&;
 
   const T* operator->() const;
   T* operator->();
 
   const T& value() const&;
   T& value() &;
   const T&& value() const&&;
   T&& value() &&;
 
+  template <typename U>
+  constexpr T value_or(U&& v) const&;
+  template <typename U>
+  T value_or(U&& v) &&;
+
+  template <typename... Args>
+  T& emplace(Args&&... args);
+
+  template <typename U, typename... Args>
+  T& emplace(std::initializer_list<U> ilist, Args&&... args);
+
+  void reset() noexcept;
+
+  constexpr explicit operator bool() const noexcept;
   constexpr bool has_value() const noexcept;
 };
 
+template <typename T>
+constexpr optional<typename std::decay<T>::type> make_optional(T&& v);
+
+template <typename T, typename... Args>
+constexpr optional<T> make_optional(Args&&... args);
+
+template <typename T, typename U, typename... Args>
+constexpr optional<T> make_optional(std::initializer_list<U> il,
+                                    Args&&... args);
+
 } // namespace absl
 )";
 
 static constexpr char BaseOptionalHeader[] = R"(
+#include "std_initializer_list.h"
+#include "std_type_traits.h"
+#include "std_utility.h"
+
 namespace base {
 
 template <typename T>
 class Optional {
  public:
   constexpr Optional() noexcept;
 
   const T& operator*() const&;
   T& operator*() &;
   const T&& operator*() const&&;
   T&& operator*() &&;
 
   const T* operator->() const;
   T* operator->();
 
   const T& value() const&;
   T& value() &;
   const T&& value() const&&;
   T&& value() &&;
 
+  template <typename U>
+  constexpr T value_or(U&& v) const&;
+  template <typename U>
+  T value_or(U&& v) &&;
+
+  template <typename... Args>
+  T& emplace(Args&&... args);
+
+  template <typename U, typename... Args>
+  T& emplace(std::initializer_list<U> ilist, Args&&... args);
+
+  void reset() noexcept;
+
+  constexpr explicit operator bool() const noexcept;
   constexpr bool has_value() const noexcept;
 };
 
+template <typename T>
+constexpr Optional<typename std::decay<T>::type> make_optional(T&& v);
+
+template <typename T, typename... Args>
+constexpr Optional<T> make_optional(Args&&... args);
+
+template <typename T, typename U, typename... Args>
+constexpr Optional<T> make_optional(std::initializer_list<U> il,
+                                    Args&&... args);
+
 } // namespace base
 )";
 
 /// Converts `L` to string.
 static std::string ConvertToString(const SourceLocationsLattice &L,
                                    const ASTContext &Ctx) {
   return L.getSourceLocations().empty() ? "safe"
                                         : "unsafe: " + DebugString(L, Ctx);
private:
   template <typename FuncDeclMatcher, typename LatticeChecksMatcher>
   void ExpectLatticeChecksFor(std::string SourceCode,
                               FuncDeclMatcher FuncMatcher,
                               LatticeChecksMatcher MatchesLatticeChecks) {
     ReplaceAllOccurrences(SourceCode, "$ns", GetParam().NamespaceName);
     ReplaceAllOccurrences(SourceCode, "$optional", GetParam().TypeName);
 
     std::vector<std::pair<std::string, std::string>> Headers;
+    Headers.emplace_back("std_initializer_list.h", StdInitializerListHeader);
     Headers.emplace_back("std_type_traits.h", StdTypeTraitsHeader);
     Headers.emplace_back("std_utility.h", StdUtilityHeader);
     Headers.emplace_back("std_optional.h", StdOptionalHeader);
     Headers.emplace_back("absl_optional.h", AbslOptionalHeader);
     Headers.emplace_back("base_optional.h", BaseOptionalHeader);
     Headers.emplace_back("unchecked_optional_access_test.h", R"(
       #include "absl_optional.h"
       #include "base_optional.h"
+      #include "std_initializer_list.h"
       #include "std_optional.h"
       #include "std_utility.h"
+
+      template <typename T>
+      T Make();
     )");
     const tooling::FileContentMappings FileContents(Headers.begin(),
                                                     Headers.end());
     llvm::Error Error = checkDataflow<UncheckedOptionalAccessModel>(
         SourceCode, FuncMatcher,
         [](ASTContext &Ctx, Environment &) {
           return UncheckedOptionalAccessModel(Ctx);
         },
ExpectLatticeChecksFor(
     void target($ns::$optional<Foo> opt) {
       std::move(opt)->foo();
       /*[[check]]*/
     }
   )",
       UnorderedElementsAre(Pair("check", "unsafe: input.cc:9:7")));
 }
 
-TEST_P(UncheckedOptionalAccessTest, UnwrapWithCheck) {
+TEST_P(UncheckedOptionalAccessTest, HasValueCheck) {
   ExpectLatticeChecksFor(R"(
     #include "unchecked_optional_access_test.h"
 
     void target($ns::$optional<int> opt) {
       if (opt.has_value()) {
         opt.value();
         /*[[check]]*/
       }
     }
   )",
                          UnorderedElementsAre(Pair("check", "safe")));
 }
 
+TEST_P(UncheckedOptionalAccessTest, OperatorBoolCheck) {
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target($ns::$optional<int> opt) {
+      if (opt) {
+        opt.value();
+        /*[[check]]*/
+      }
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, UnwrapFunctionCallResultNoCheck) {
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      Make<$ns::$optional<int>>().value();
+      (void)0;
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:5:7")));
+
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target($ns::$optional<int> opt) {
+      std::move(opt).value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:5:7")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, DefaultConstructor) {
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt;
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:6:7")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, MakeOptional) {
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt = $ns::make_optional(0);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {
+      Foo(int, int);
+    };
+
+    void target() {
+      $ns::$optional<Foo> opt = $ns::make_optional<Foo>(21, 22);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {
+      constexpr Foo(std::initializer_list<char>);
+    };
+
+    void target() {
+      char a = 'a';
+      $ns::$optional<Foo> opt = $ns::make_optional<Foo>({a});
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, ValueOr) {
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt;
+      opt.value_or(0);
+      (void)0;
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, Emplace) {
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt;
+      opt.emplace(0);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target($ns::$optional<int> *opt) {
+      opt->emplace(0);
+      opt->value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  // FIXME: Add tests that call `emplace` in conditional branches.
+}
+
+TEST_P(UncheckedOptionalAccessTest, Reset) {
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt = $ns::make_optional(0);
+      opt.reset();
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:7:7")));
+
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> *opt;
+      *opt = $ns::make_optional(0);
+      opt->reset();
+      opt->value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:8:7")));
+
+  // FIXME: Add tests that call `reset` in conditional branches.
+}
+
 // FIXME: Add support for:
-// - constructors (default, copy, move, non-standard)
+// - constructors (copy, move, non-standard)
 // - assignment operators (default, copy, move, non-standard)
-// - operator bool
-// - emplace
-// - reset
-// - value_or
 // - swap
-// - make_optional
 // - invalidation (passing optional by non-const reference/pointer)
+// - `value_or(nullptr) != nullptr`, `value_or(0) != 0`, `value_or("").empty()`
+// - nested `optional` values