[clang][dataflow] Model the behavior of non-standard optional constructors

[sgatev]

Summary

Model nullopt, inplace, value, and conversion constructors.

[ymandel]

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

42

This shouldn't be needed, since we now pass the MatchFinder::MatchResult in Action, which includes the ASTContext.

[xazax.hun]

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

55

Did you consider hasAnyName? Or would that not work in this context?

75

What is a non-standard constructor? This might be a well-known term I'm not aware of. If that is not the case I'd prefer a comment or a more descriptive name.

263

Do we need this + to force conversion to function pointer? Is it possible to fix CaseOf so it works with lambdas or is that not desirable?

[ymandel]

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

110

This could get expensive. Maybe add a FIXME to optimize this by avoiding getQualifiedNameAsString?

264

I realize this is consistent with the previous version, but just noticed this issue. By using assignOptionalValue for emplace (and reset), does that break the following case?

optional<int> opt;
if (p) opt.emplace(3);
someCode();
if (p) use(*opt);

[sgatev]

Address reviewers' comments.

[sgatev]

Add a FIXME.

[sgatev]

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

264

This isn't supported yet. Still, I don't think assignOptionalValue breaks it because this seems more related to the way information from different branches is joined than the way values are initialized. I'll add this case (and others) in a following patch that adds support for joining.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

150

Nit: looks like we need to repeat the action type. Should we restore the using above?

[xazax.hun]

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

120

Nit: some of these functions are static and some not. Should we have one big anonymous namespace instead?

[ymandel]

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

264

Sounds good. I think we can discuss further in the next patch as needed.

[sgatev]

Address reviewers' comments.

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

150

It's not the same. The one above is a template - it accepts an arbitrary Node instead of a Stmt.

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

120

We already have an anonymous namespace so I'll make the functions inside non-static.

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

 #include <utility>
 #include <vector>
 
 namespace clang {
 namespace dataflow {
 
 /// A common form of state shared between the cases of a transfer function.
 template <typename LatticeT> struct TransferState {
-  TransferState(LatticeT &Lattice, Environment &Env)
-      : Lattice(Lattice), Env(Env) {}
+  TransferState(ASTContext &ASTCtx, LatticeT &Lattice, Environment &Env)
+      : ASTCtx(ASTCtx), Lattice(Lattice), Env(Env) {}
 
-  /// Current lattice element.
+  ASTContext &ASTCtx;
   LatticeT &Lattice;
   Environment &Env;
 };
 
 /// Matches against `Stmt` and, based on its structure, dispatches to an
 /// appropriate handler.
 template <typename State>
 using MatchSwitch = std::function<void(const Stmt &, ASTContext &, State &)>;
ast_matchers::internal::DynTypedMatcher BuildMatcher() {
     // all of the matchers.
     return DynTypedMatcher::constructVariadic(
         DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<Stmt>(),
         std::move(Matchers));
   }
 
   std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
   std::vector<Action> Actions;
 };
 } // namespace dataflow
 } // namespace clang
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_

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

 
 static auto isMakeOptionalCall() {
   return callExpr(
       callee(functionDecl(hasAnyName(
           "std::make_optional", "base::make_optional", "absl::make_optional"))),
       hasOptionalType());
 }
 
+auto hasNulloptType() {
+  return hasType(
+      recordDecl(anyOf(hasName("std::nullopt_t"), hasName("absl::nullopt_t"),
+                       hasName("base::nullopt_t"))));
+}
+
+auto inPlaceClass() {
+  return recordDecl(anyOf(hasName("std::in_place_t"),
+                          hasName("absl::in_place_t"),
+                          hasName("base::in_place_t")));
+}
+
+auto isOptionalNulloptConstructor() {
+  return cxxConstructExpr(hasOptionalType(), argumentCountIs(1),
+                          hasArgument(0, hasNulloptType()));
+}
+
+auto isOptionalInPlaceConstructor() {
+  return cxxConstructExpr(hasOptionalType(),
+                          hasArgument(0, hasType(inPlaceClass())));
+}
+
+auto isOptionalNonStandardConstructor() {
+  return cxxConstructExpr(
+      hasOptionalType(),
+      unless(hasDeclaration(
+          cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
+      argumentCountIs(1), hasArgument(0, unless(hasNulloptType())));
+}
+
 /// 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;
 }
 
+/// 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) {
+  if (!Type->isRecordType())
+    return false;
+  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))
+    return 0;
+  return 1 + countOptionalWrappers(
+                 ASTCtx,
+                 cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
+                     ->getTemplateArgs()
+                     .get(0)
+                     .getAsType()
+                     .getDesugaredType(ASTCtx));
+}
+
 static void initializeOptionalReference(const Expr *OptionalExpr,
                                         LatticeTransferState &State) {
   if (auto *OptionalVal = cast_or_null<StructValue>(
           State.Env.getValue(*OptionalExpr, SkipPast::Reference))) {
     if (OptionalVal->getProperty("has_value") == nullptr) {
       OptionalVal->setProperty("has_value", State.Env.makeAtomicBoolValue());
     }
   }
if (auto *OptionalVal = cast_or_null<StructValue>(
     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 assignOptionalValue(const Expr &E, LatticeTransferState &State,
+                         BoolValue &HasValueVal) {
+  if (auto *OptionalLoc =
+          State.Env.getStorageLocation(E, SkipPast::ReferenceThenPointer)) {
+    State.Env.setValue(*OptionalLoc,
+                       createOptionalValue(State.Env, HasValueVal));
   }
 }
 
-void transferResetCall(const CXXMemberCallExpr *E,
+void transferNonStandardConstructor(const CXXConstructExpr *E,
                                     LatticeTransferState &State) {
-  if (auto *OptionalLoc = State.Env.getStorageLocation(
-          *E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer)) {
-    State.Env.setValue(
-        *OptionalLoc,
-        createOptionalValue(State.Env, State.Env.getBoolLiteralValue(false)));
-  }
+  assert(E->getConstructor()->getTemplateSpecializationArgs()->size() > 0);
+  assert(E->getNumArgs() > 0);
+
+  const int TemplateParamOptionalWrappersCount = countOptionalWrappers(
+      State.ASTCtx, stripReference(E->getConstructor()
+                                       ->getTemplateSpecializationArgs()
+                                       ->get(0)
+                                       .getAsType()));
+  const int ArgTypeOptionalWrappersCount = countOptionalWrappers(
+      State.ASTCtx, stripReference(E->getArg(0)->getType()));
+  auto *HasValueVal =
+      (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
+          // This is a constructor call for optional<T> with argument of type U
+          // such that T is constructible from U.
+          ? &State.Env.getBoolLiteralValue(true)
+          // This is a constructor call for optional<T> with argument of type
+          // optional<U> such that T is constructible from U.
+          : getHasValue(State.Env.getValue(*E->getArg(0), SkipPast::Reference));
+  if (HasValueVal == nullptr)
+    HasValueVal = &State.Env.makeAtomicBoolValue();
+
+  assignOptionalValue(*E, State, *HasValueVal);
 }
 
 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)
 
+      // constructors:
+      .CaseOf(
+          isOptionalInPlaceConstructor(),
+          +[](const CXXConstructExpr *E, LatticeTransferState &State) {
+            assignOptionalValue(*E, State, State.Env.getBoolLiteralValue(true));
+          })
+      .CaseOf(
+          isOptionalNulloptConstructor(),
+          +[](const CXXConstructExpr *E, LatticeTransferState &State) {
+            assignOptionalValue(*E, State,
+                                State.Env.getBoolLiteralValue(false));
+          })
+      .CaseOf(isOptionalNonStandardConstructor(),
+              transferNonStandardConstructor)
+
       // 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)
+      .CaseOf(
+          isOptionalMemberCallWithName("emplace"),
+          +[](const CXXMemberCallExpr *E, LatticeTransferState &State) {
+            assignOptionalValue(*E->getImplicitObjectArgument(), State,
+                                State.Env.getBoolLiteralValue(true));
+          })
 
       // optional::reset
-      .CaseOf(isOptionalMemberCallWithName("reset"), transferResetCall)
+      .CaseOf(
+          isOptionalMemberCallWithName("reset"),
+          +[](const CXXMemberCallExpr *E, LatticeTransferState &State) {
+            assignOptionalValue(*E->getImplicitObjectArgument(), State,
+                                State.Env.getBoolLiteralValue(false));
+          })
 
       .Build();
 }
 
 } // namespace
 
 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx)
     : DataflowAnalysis<UncheckedOptionalAccessModel, SourceLocationsLattice>(
           Ctx),
       TransferMatchSwitch(buildTransferMatchSwitch()) {}
 
 void UncheckedOptionalAccessModel::transfer(const Stmt *S,
                                             SourceLocationsLattice &L,
                                             Environment &Env) {
-  LatticeTransferState State(L, Env);
+  LatticeTransferState State(getASTContext(), L, Env);
   TransferMatchSwitch(*S, getASTContext(), State);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/Transfer.cpp

case CK_LValueToRValue: {
       if (SubExprVal == nullptr)
         break;
 
       auto &ExprLoc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, ExprLoc);
       Env.setValue(ExprLoc, *SubExprVal);
       break;
     }
+    case CK_UncheckedDerivedToBase:
+    case CK_ConstructorConversion:
+    case CK_UserDefinedConversion:
+      // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
+      // CK_ConstructorConversion, and CK_UserDefinedConversion.
     case CK_NoOp: {
       // FIXME: Consider making `Environment::getStorageLocation` skip noop
       // expressions (this and other similar expressions in the file) instead of
       // assigning them storage locations.
       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
       if (SubExprLoc == nullptr)
         break;
 
       Env.setStorageLocation(*S, *SubExprLoc);
       break;
     }
     default:
-      // FIXME: Add support for CK_UserDefinedConversion,
-      // CK_ConstructorConversion, CK_UncheckedDerivedToBase.
       break;
     }
   }
 
   void VisitUnaryOperator(const UnaryOperator *S) {
     // The CFG does not contain `ParenExpr` as top-level statements in basic
     // blocks, however sub-expressions can still be of that type.
     assert(S->getSubExpr() != nullptr);

clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp

TransferSwitch =
             .CaseOf(callExpr(callee(functionDecl(hasName("Foo")))),
                     TransferSetFalse)
             .Build();
   }
 
   static BooleanLattice initialElement() { return BooleanLattice::bottom(); }
 
   void transfer(const Stmt *S, BooleanLattice &L, Environment &Env) {
-    TransferState<BooleanLattice> State(L, Env);
+    TransferState<BooleanLattice> State(getASTContext(), L, Env);
     TransferSwitch(*S, getASTContext(), State);
   }
 };
 
 class MatchSwitchTest : public ::testing::Test {
 protected:
   template <typename Matcher>
   void RunDataflow(llvm::StringRef Code, Matcher Expectations) {

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

 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
+#ifndef STD_TYPE_TRAITS_H
+#define STD_TYPE_TRAITS_H
 
 namespace std {
 
 typedef decltype(sizeof(char)) size_t;
 
 template <typename T, T V>
 struct integral_constant {
   static constexpr T value = V;
struct remove_cv<volatile T> {
   typedef T type;
 };
 template <class T>
 struct remove_cv<const volatile T> {
   typedef T type;
 };
 
 template <class T>
+using remove_cv_t = typename remove_cv<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;
 };
 
+template <bool B, class T = void>
+struct enable_if {};
+
+template <class T>
+struct enable_if<true, T> {
+  typedef T type;
+};
+
+template <bool B, class T = void>
+using enable_if_t = typename enable_if<B, T>::type;
+
+template <class T, class U>
+struct is_same : false_type {};
+
+template <class T>
+struct is_same<T, T> : true_type {};
+
+template <class T>
+struct is_void : is_same<void, typename remove_cv<T>::type> {};
+
+namespace detail {
+
+template <class T>
+auto try_add_rvalue_reference(int) -> type_identity<T&&>;
+template <class T>
+auto try_add_rvalue_reference(...) -> type_identity<T>;
+
+}  // namespace detail
+
+template <class T>
+struct add_rvalue_reference : decltype(detail::try_add_rvalue_reference<T>(0)) {
+};
+
+template <class T>
+typename add_rvalue_reference<T>::type declval() noexcept;
+
+namespace detail {
+
+template <class T>
+auto test_returnable(int)
+    -> decltype(void(static_cast<T (*)()>(nullptr)), true_type{});
+template <class>
+auto test_returnable(...) -> false_type;
+
+template <class From, class To>
+auto test_implicitly_convertible(int)
+    -> decltype(void(declval<void (&)(To)>()(declval<From>())), true_type{});
+template <class, class>
+auto test_implicitly_convertible(...) -> false_type;
+
+}  // namespace detail
+
+template <class From, class To>
+struct is_convertible
+    : integral_constant<bool,
+                        (decltype(detail::test_returnable<To>(0))::value &&
+                         decltype(detail::test_implicitly_convertible<From, To>(
+                             0))::value) ||
+                            (is_void<From>::value && is_void<To>::value)> {};
+
+template <class From, class To>
+inline constexpr bool is_convertible_v = is_convertible<From, To>::value;
+
+template <class...>
+using void_t = void;
+
+template <class, class T, class... Args>
+struct is_constructible_ : false_type {};
+
+template <class T, class... Args>
+struct is_constructible_<void_t<decltype(T(declval<Args>()...))>, T, Args...>
+    : true_type {};
+
+template <class T, class... Args>
+using is_constructible = is_constructible_<void_t<>, T, Args...>;
+
+template <class T, class... Args>
+inline constexpr bool is_constructible_v = is_constructible<T, Args...>::value;
+
+template <class _Tp>
+struct __uncvref {
+  typedef typename remove_cv<typename remove_reference<_Tp>::type>::type type;
+};
+
+template <class _Tp>
+using __uncvref_t = typename __uncvref<_Tp>::type;
+
+template <bool _Val>
+using _BoolConstant = integral_constant<bool, _Val>;
+
+template <class _Tp, class _Up>
+using _IsSame = _BoolConstant<__is_same(_Tp, _Up)>;
+
+template <class _Tp, class _Up>
+using _IsNotSame = _BoolConstant<!__is_same(_Tp, _Up)>;
+
+template <bool>
+struct _MetaBase;
+template <>
+struct _MetaBase<true> {
+  template <class _Tp, class _Up>
+  using _SelectImpl = _Tp;
+  template <template <class...> class _FirstFn, template <class...> class,
+            class... _Args>
+  using _SelectApplyImpl = _FirstFn<_Args...>;
+  template <class _First, class...>
+  using _FirstImpl = _First;
+  template <class, class _Second, class...>
+  using _SecondImpl = _Second;
+  template <class _Result, class _First, class... _Rest>
+  using _OrImpl =
+      typename _MetaBase<_First::value != true && sizeof...(_Rest) != 0>::
+          template _OrImpl<_First, _Rest...>;
+};
+
+template <>
+struct _MetaBase<false> {
+  template <class _Tp, class _Up>
+  using _SelectImpl = _Up;
+  template <template <class...> class, template <class...> class _SecondFn,
+            class... _Args>
+  using _SelectApplyImpl = _SecondFn<_Args...>;
+  template <class _Result, class...>
+  using _OrImpl = _Result;
+};
+
+template <bool _Cond, class _IfRes, class _ElseRes>
+using _If = typename _MetaBase<_Cond>::template _SelectImpl<_IfRes, _ElseRes>;
+
+template <class... _Rest>
+using _Or = typename _MetaBase<sizeof...(_Rest) !=
+                               0>::template _OrImpl<false_type, _Rest...>;
+
+template <bool _Bp, class _Tp = void>
+using __enable_if_t = typename enable_if<_Bp, _Tp>::type;
+
+template <class...>
+using __expand_to_true = true_type;
+template <class... _Pred>
+__expand_to_true<__enable_if_t<_Pred::value>...> __and_helper(int);
+template <class...>
+false_type __and_helper(...);
+template <class... _Pred>
+using _And = decltype(__and_helper<_Pred...>(0));
+
+struct __check_tuple_constructor_fail {
+  static constexpr bool __enable_explicit_default() { return false; }
+  static constexpr bool __enable_implicit_default() { return false; }
+  template <class...>
+  static constexpr bool __enable_explicit() {
+    return false;
+  }
+  template <class...>
+  static constexpr bool __enable_implicit() {
+    return false;
+  }
+};
+
 } // namespace std
 
-#endif // TYPE_TRAITS_H
+#endif // STD_TYPE_TRAITS_H
+)";
+
+static constexpr char AbslTypeTraitsHeader[] = R"(
+#ifndef ABSL_TYPE_TRAITS_H
+#define ABSL_TYPE_TRAITS_H
+
+#include "std_type_traits.h"
+
+namespace absl {
+
+template <typename... Ts>
+struct conjunction : std::true_type {};
+
+template <typename T, typename... Ts>
+struct conjunction<T, Ts...>
+    : std::conditional<T::value, conjunction<Ts...>, T>::type {};
+
+template <typename T>
+struct conjunction<T> : T {};
+
+template <typename T>
+struct negation : std::integral_constant<bool, !T::value> {};
+
+template <bool B, typename T = void>
+using enable_if_t = typename std::enable_if<B, T>::type;
+
+} // namespace absl
+
+#endif // ABSL_TYPE_TRAITS_H
 )";
 
 static constexpr char StdUtilityHeader[] = R"(
 #ifndef UTILITY_H
 #define UTILITY_H
 
 #include "std_type_traits.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 {
+struct in_place_t {};
+constexpr in_place_t in_place;
+
+struct nullopt_t {
+  constexpr explicit nullopt_t() {}
+};
+constexpr nullopt_t nullopt;
+
+template <class _Tp>
+struct __optional_destruct_base {
+  constexpr void reset() noexcept;
+};
+
+template <class _Tp>
+struct __optional_storage_base : __optional_destruct_base<_Tp> {
+  constexpr bool has_value() const noexcept;
+};
+
+template <typename _Tp>
+class optional : private __optional_storage_base<_Tp> {
+  using __base = __optional_storage_base<_Tp>;
+
  public:
-  constexpr optional() noexcept;
+  using value_type = _Tp;
 
-  const T& operator*() const&;
-  T& operator*() &;
-  const T&& operator*() const&&;
-  T&& operator*() &&;
+ private:
+  struct _CheckOptionalArgsConstructor {
+    template <class _Up>
+    static constexpr bool __enable_implicit() {
+      return is_constructible_v<_Tp, _Up&&> && is_convertible_v<_Up&&, _Tp>;
+    }
+
+    template <class _Up>
+    static constexpr bool __enable_explicit() {
+      return is_constructible_v<_Tp, _Up&&> && !is_convertible_v<_Up&&, _Tp>;
+    }
+  };
+  template <class _Up>
+  using _CheckOptionalArgsCtor =
+      _If<_IsNotSame<__uncvref_t<_Up>, in_place_t>::value &&
+              _IsNotSame<__uncvref_t<_Up>, optional>::value,
+          _CheckOptionalArgsConstructor, __check_tuple_constructor_fail>;
+  template <class _QualUp>
+  struct _CheckOptionalLikeConstructor {
+    template <class _Up, class _Opt = optional<_Up>>
+    using __check_constructible_from_opt =
+        _Or<is_constructible<_Tp, _Opt&>, is_constructible<_Tp, _Opt const&>,
+            is_constructible<_Tp, _Opt&&>, is_constructible<_Tp, _Opt const&&>,
+            is_convertible<_Opt&, _Tp>, is_convertible<_Opt const&, _Tp>,
+            is_convertible<_Opt&&, _Tp>, is_convertible<_Opt const&&, _Tp>>;
+    template <class _Up, class _QUp = _QualUp>
+    static constexpr bool __enable_implicit() {
+      return is_convertible<_QUp, _Tp>::value &&
+             !__check_constructible_from_opt<_Up>::value;
+    }
+    template <class _Up, class _QUp = _QualUp>
+    static constexpr bool __enable_explicit() {
+      return !is_convertible<_QUp, _Tp>::value &&
+             !__check_constructible_from_opt<_Up>::value;
+    }
+  };
 
-  const T* operator->() const;
-  T* operator->();
+  template <class _Up, class _QualUp>
+  using _CheckOptionalLikeCtor =
+      _If<_And<_IsNotSame<_Up, _Tp>, is_constructible<_Tp, _QualUp>>::value,
+          _CheckOptionalLikeConstructor<_QualUp>,
+          __check_tuple_constructor_fail>;
 
-  const T& value() const&;
-  T& value() &;
-  const T&& value() const&&;
-  T&& value() &&;
+ public:
+  constexpr optional() noexcept {}
+  constexpr optional(const optional&) = default;
+  constexpr optional(optional&&) = default;
+  constexpr optional(nullopt_t) noexcept {}
+
+  template <
+      class _InPlaceT, class... _Args,
+      class = enable_if_t<_And<_IsSame<_InPlaceT, in_place_t>,
+                             is_constructible<value_type, _Args...>>::value>>
+  constexpr explicit optional(_InPlaceT, _Args&&... __args);
+
+  template <class _Up, class... _Args,
+            class = enable_if_t<is_constructible_v<
+                value_type, initializer_list<_Up>&, _Args...>>>
+  constexpr explicit optional(in_place_t, initializer_list<_Up> __il,
+                              _Args&&... __args);
+
+  template <
+      class _Up = value_type,
+      enable_if_t<_CheckOptionalArgsCtor<_Up>::template __enable_implicit<_Up>(),
+                int> = 0>
+  constexpr optional(_Up&& __v);
+
+  template <
+      class _Up,
+      enable_if_t<_CheckOptionalArgsCtor<_Up>::template __enable_explicit<_Up>(),
+                int> = 0>
+  constexpr explicit optional(_Up&& __v);
+
+  template <class _Up, enable_if_t<_CheckOptionalLikeCtor<_Up, _Up const&>::
+                                     template __enable_implicit<_Up>(),
+                                 int> = 0>
+  constexpr optional(const optional<_Up>& __v);
+
+  template <class _Up, enable_if_t<_CheckOptionalLikeCtor<_Up, _Up const&>::
+                                     template __enable_explicit<_Up>(),
+                                 int> = 0>
+  constexpr explicit optional(const optional<_Up>& __v);
+
+  template <class _Up, enable_if_t<_CheckOptionalLikeCtor<_Up, _Up&&>::
+                                     template __enable_implicit<_Up>(),
+                                 int> = 0>
+  constexpr optional(optional<_Up>&& __v);
+
+  template <class _Up, enable_if_t<_CheckOptionalLikeCtor<_Up, _Up&&>::
+                                     template __enable_explicit<_Up>(),
+                                 int> = 0>
+  constexpr explicit optional(optional<_Up>&& __v);
+
+  const _Tp& operator*() const&;
+  _Tp& operator*() &;
+  const _Tp&& operator*() const&&;
+  _Tp&& operator*() &&;
+
+  const _Tp* operator->() const;
+  _Tp* operator->();
+
+  const _Tp& value() const&;
+  _Tp& value() &;
+  const _Tp&& value() const&&;
+  _Tp&& value() &&;
 
   template <typename U>
-  constexpr T value_or(U&& v) const&;
+  constexpr _Tp value_or(U&& v) const&;
   template <typename U>
-  T value_or(U&& v) &&;
+  _Tp value_or(U&& v) &&;
 
   template <typename... Args>
-  T& emplace(Args&&... args);
+  _Tp& emplace(Args&&... args);
 
   template <typename U, typename... Args>
-  T& emplace(std::initializer_list<U> ilist, Args&&... args);
+  _Tp& emplace(std::initializer_list<U> ilist, Args&&... args);
 
-  void reset() noexcept;
+  using __base::reset;
 
   constexpr explicit operator bool() const noexcept;
-  constexpr bool has_value() const noexcept;
+  using __base::has_value;
 };
 
 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 "absl_type_traits.h"
 #include "std_initializer_list.h"
 #include "std_type_traits.h"
 #include "std_utility.h"
 
 namespace absl {
 
+struct nullopt_t {
+  constexpr explicit nullopt_t() {}
+};
+constexpr nullopt_t nullopt;
+
+struct in_place_t {};
+constexpr in_place_t in_place;
+
+template <typename T>
+class optional;
+
+namespace optional_internal {
+
+// Whether T is constructible or convertible from optional<U>.
+template <typename T, typename U>
+struct is_constructible_convertible_from_optional
+    : std::integral_constant<
+          bool, std::is_constructible<T, optional<U>&>::value ||
+                    std::is_constructible<T, optional<U>&&>::value ||
+                    std::is_constructible<T, const optional<U>&>::value ||
+                    std::is_constructible<T, const optional<U>&&>::value ||
+                    std::is_convertible<optional<U>&, T>::value ||
+                    std::is_convertible<optional<U>&&, T>::value ||
+                    std::is_convertible<const optional<U>&, T>::value ||
+                    std::is_convertible<const optional<U>&&, T>::value> {};
+
+}  // namespace optional_internal
+
 template <typename T>
 class optional {
  public:
   constexpr optional() noexcept;
 
+  constexpr optional(nullopt_t) noexcept;
+
+  optional(const optional&) = default;
+
+  optional(optional&&) = default;
+
+  template <typename InPlaceT, typename... Args,
+            absl::enable_if_t<absl::conjunction<
+                std::is_same<InPlaceT, in_place_t>,
+                std::is_constructible<T, Args&&...>>::value>* = nullptr>
+  constexpr explicit optional(InPlaceT, Args&&... args);
+
+  template <typename U, typename... Args,
+            typename = typename std::enable_if<std::is_constructible<
+                T, std::initializer_list<U>&, Args&&...>::value>::type>
+  constexpr explicit optional(in_place_t, std::initializer_list<U> il,
+                              Args&&... args);
+
+  template <
+      typename U = T,
+      typename std::enable_if<
+          absl::conjunction<absl::negation<std::is_same<
+                                in_place_t, typename std::decay<U>::type>>,
+                            absl::negation<std::is_same<
+                                optional<T>, typename std::decay<U>::type>>,
+                            std::is_convertible<U&&, T>,
+                            std::is_constructible<T, U&&>>::value,
+          bool>::type = false>
+  constexpr optional(U&& v);
+
+  template <
+      typename U = T,
+      typename std::enable_if<
+          absl::conjunction<absl::negation<std::is_same<
+                                in_place_t, typename std::decay<U>::type>>,
+                            absl::negation<std::is_same<
+                                optional<T>, typename std::decay<U>::type>>,
+                            absl::negation<std::is_convertible<U&&, T>>,
+                            std::is_constructible<T, U&&>>::value,
+          bool>::type = false>
+  explicit constexpr optional(U&& v);
+
+  template <typename U,
+            typename std::enable_if<
+                absl::conjunction<
+                    absl::negation<std::is_same<T, U>>,
+                    std::is_constructible<T, const U&>,
+                    absl::negation<
+                        optional_internal::
+                            is_constructible_convertible_from_optional<T, U>>,
+                    std::is_convertible<const U&, T>>::value,
+                bool>::type = false>
+  optional(const optional<U>& rhs);
+
+  template <typename U,
+            typename std::enable_if<
+                absl::conjunction<
+                    absl::negation<std::is_same<T, U>>,
+                    std::is_constructible<T, const U&>,
+                    absl::negation<
+                        optional_internal::
+                            is_constructible_convertible_from_optional<T, U>>,
+                    absl::negation<std::is_convertible<const U&, T>>>::value,
+                bool>::type = false>
+  explicit optional(const optional<U>& rhs);
+
+  template <
+      typename U,
+      typename std::enable_if<
+          absl::conjunction<
+              absl::negation<std::is_same<T, U>>, std::is_constructible<T, U&&>,
+              absl::negation<
+                  optional_internal::is_constructible_convertible_from_optional<
+                      T, U>>,
+              std::is_convertible<U&&, T>>::value,
+          bool>::type = false>
+  optional(optional<U>&& rhs);
+
+  template <
+      typename U,
+      typename std::enable_if<
+          absl::conjunction<
+              absl::negation<std::is_same<T, U>>, std::is_constructible<T, U&&>,
+              absl::negation<
+                  optional_internal::is_constructible_convertible_from_optional<
+                      T, U>>,
+              absl::negation<std::is_convertible<U&&, T>>>::value,
+          bool>::type = false>
+  explicit optional(optional<U>&& rhs);
+
   const T& operator*() const&;
   T& operator*() &;
   const T&& operator*() const&&;
   T&& operator*() &&;
 
   const T* operator->() const;
   T* operator->();
 

 
 static constexpr char BaseOptionalHeader[] = R"(
 #include "std_initializer_list.h"
 #include "std_type_traits.h"
 #include "std_utility.h"
 
 namespace base {
 
+struct in_place_t {};
+constexpr in_place_t in_place;
+
+struct nullopt_t {
+  constexpr explicit nullopt_t() {}
+};
+constexpr nullopt_t nullopt;
+
+template <typename T>
+class Optional;
+
+namespace internal {
+
+template <typename T>
+using RemoveCvRefT = std::remove_cv_t<std::remove_reference_t<T>>;
+
+template <typename T, typename U>
+struct IsConvertibleFromOptional
+    : std::integral_constant<
+          bool, std::is_constructible<T, Optional<U>&>::value ||
+                    std::is_constructible<T, const Optional<U>&>::value ||
+                    std::is_constructible<T, Optional<U>&&>::value ||
+                    std::is_constructible<T, const Optional<U>&&>::value ||
+                    std::is_convertible<Optional<U>&, T>::value ||
+                    std::is_convertible<const Optional<U>&, T>::value ||
+                    std::is_convertible<Optional<U>&&, T>::value ||
+                    std::is_convertible<const Optional<U>&&, T>::value> {};
+
+}  // namespace internal
+
 template <typename T>
 class Optional {
  public:
-  constexpr Optional() noexcept;
+  using value_type = T;
+
+  constexpr Optional() = default;
+  constexpr Optional(const Optional& other) noexcept = default;
+  constexpr Optional(Optional&& other) noexcept = default;
+
+  constexpr Optional(nullopt_t);
+
+  template <typename U,
+            typename std::enable_if<
+                std::is_constructible<T, const U&>::value &&
+                    !internal::IsConvertibleFromOptional<T, U>::value &&
+                    std::is_convertible<const U&, T>::value,
+                bool>::type = false>
+  Optional(const Optional<U>& other) noexcept;
+
+  template <typename U,
+            typename std::enable_if<
+                std::is_constructible<T, const U&>::value &&
+                    !internal::IsConvertibleFromOptional<T, U>::value &&
+                    !std::is_convertible<const U&, T>::value,
+                bool>::type = false>
+  explicit Optional(const Optional<U>& other) noexcept;
+
+  template <typename U,
+            typename std::enable_if<
+                std::is_constructible<T, U&&>::value &&
+                    !internal::IsConvertibleFromOptional<T, U>::value &&
+                    std::is_convertible<U&&, T>::value,
+                bool>::type = false>
+  Optional(Optional<U>&& other) noexcept;
+
+  template <typename U,
+            typename std::enable_if<
+                std::is_constructible<T, U&&>::value &&
+                    !internal::IsConvertibleFromOptional<T, U>::value &&
+                    !std::is_convertible<U&&, T>::value,
+                bool>::type = false>
+  explicit Optional(Optional<U>&& other) noexcept;
+
+  template <class... Args>
+  constexpr explicit Optional(in_place_t, Args&&... args);
+
+  template <class U, class... Args,
+            class = typename std::enable_if<std::is_constructible<
+                value_type, std::initializer_list<U>&, Args...>::value>::type>
+  constexpr explicit Optional(in_place_t, std::initializer_list<U> il,
+                              Args&&... args);
+
+  template <
+      typename U = value_type,
+      typename std::enable_if<
+          std::is_constructible<T, U&&>::value &&
+              !std::is_same<internal::RemoveCvRefT<U>, in_place_t>::value &&
+              !std::is_same<internal::RemoveCvRefT<U>, Optional<T>>::value &&
+              std::is_convertible<U&&, T>::value,
+          bool>::type = false>
+  constexpr Optional(U&& value);
+
+  template <
+      typename U = value_type,
+      typename std::enable_if<
+          std::is_constructible<T, U&&>::value &&
+              !std::is_same<internal::RemoveCvRefT<U>, in_place_t>::value &&
+              !std::is_same<internal::RemoveCvRefT<U>, Optional<T>>::value &&
+              !std::is_convertible<U&&, T>::value,
+          bool>::type = false>
+  constexpr explicit Optional(U&& value);
 
   const T& operator*() const&;
   T& operator*() &;
   const T&& operator*() const&&;
   T&& operator*() &&;
 
   const T* operator->() const;
   T* operator->();
void ExpectLatticeChecksFor(std::string SourceCode,
     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_type_traits.h", AbslTypeTraitsHeader);
     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"
void target() {
       $ns::$optional<int> opt;
       opt.value();
       /*[[check]]*/
     }
   )",
       UnorderedElementsAre(Pair("check", "unsafe: input.cc:6:7")));
 }
 
+TEST_P(UncheckedOptionalAccessTest, NulloptConstructor) {
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt($ns::nullopt);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:6:7")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, InPlaceConstructor) {
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt($ns::in_place, 3);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {};
+
+    void target() {
+      $ns::$optional<Foo> opt($ns::in_place);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {
+      explicit Foo(int, bool);
+    };
+
+    void target() {
+      $ns::$optional<Foo> opt($ns::in_place, 3, false);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {
+      explicit Foo(std::initializer_list<int>);
+    };
+
+    void target() {
+      $ns::$optional<Foo> opt($ns::in_place, {3});
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, ValueConstructor) {
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt(21);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt = $ns::$optional<int>(21);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<$ns::$optional<int>> opt(Make<$ns::$optional<int>>());
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct MyString {
+      MyString(const char*);
+    };
+
+    void target() {
+      $ns::$optional<MyString> opt("foo");
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {};
+
+    struct Bar {
+      Bar(const Foo&);
+    };
+
+    void target() {
+      $ns::$optional<Bar> opt(Make<Foo>());
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {
+      explicit Foo(int);
+    };
+
+    void target() {
+      $ns::$optional<Foo> opt(3);
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, ConvertibleOptionalConstructor) {
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {};
+
+    struct Bar {
+      Bar(const Foo&);
+    };
+
+    void target() {
+      $ns::$optional<Bar> opt(Make<$ns::$optional<Foo>>());
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:12:7")));
+
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {};
+
+    struct Bar {
+      explicit Bar(const Foo&);
+    };
+
+    void target() {
+      $ns::$optional<Bar> opt(Make<$ns::$optional<Foo>>());
+      opt.value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:12:7")));
+
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {};
+
+    struct Bar {
+      Bar(const Foo&);
+    };
+
+    void target() {
+      $ns::$optional<Foo> opt1 = $ns::nullopt;
+      $ns::$optional<Bar> opt2(opt1);
+      opt2.value();
+      /*[[check]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:13:7")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {};
+
+    struct Bar {
+      Bar(const Foo&);
+    };
+
+    void target() {
+      $ns::$optional<Foo> opt1(Make<Foo>());
+      $ns::$optional<Bar> opt2(opt1);
+      opt2.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+
+  ExpectLatticeChecksFor(R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {};
+
+    struct Bar {
+      explicit Bar(const Foo&);
+    };
+
+    void target() {
+      $ns::$optional<Foo> opt1(Make<Foo>());
+      $ns::$optional<Bar> opt2(opt1);
+      opt2.value();
+      /*[[check]]*/
+    }
+  )",
+                         UnorderedElementsAre(Pair("check", "safe")));
+}
+
 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]]*/
ExpectLatticeChecksFor(
     }
   )",
       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();
+    void target($ns::$optional<int> &opt) {
+      if (opt.has_value()) {
+        opt.reset();
+        opt.value();
         /*[[check]]*/
       }
+    }
   )",
-      UnorderedElementsAre(Pair("check", "unsafe: input.cc:8:7")));
+      UnorderedElementsAre(Pair("check", "unsafe: input.cc:7:9")));
 
   // FIXME: Add tests that call `reset` in conditional branches.
 }
 
 // FIXME: Add support for:
-// - constructors (copy, move, non-standard)
+// - constructors (copy, move)
 // - assignment operators (default, copy, move, non-standard)
 // - swap
 // - invalidation (passing optional by non-const reference/pointer)
 // - `value_or(nullptr) != nullptr`, `value_or(0) != 0`, `value_or("").empty()`
 // - nested `optional` values