UncheckedOptionalAccessModel.cpp

Go to the documentation of this file.

//===-- UncheckedOptionalAccessModel.cpp ------------------------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
//  This file defines a dataflow analysis that detects unsafe uses of optional
//  values.
//
//===----------------------------------------------------------------------===//
 
#include "clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/Expr.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/Stmt.h"
#include "clang/AST/Type.h"
#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/ASTMatchers/ASTMatchersMacros.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/Formula.h"
#include "clang/Analysis/FlowSensitive/RecordOps.h"
#include "clang/Analysis/FlowSensitive/SmartPointerAccessorCaching.h"
#include "clang/Analysis/FlowSensitive/StorageLocation.h"
#include "clang/Analysis/FlowSensitive/Value.h"
#include "clang/Basic/OperatorKinds.h"
#include "clang/Basic/SourceLocation.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/ErrorHandling.h"
#include <cassert>
#include <optional>
 
#include "GtestModelHelpers.h"
 
namespace clang {
namespace dataflow {
 
// Note: the Names appear in reverse order. E.g., to check
// if NS is foo::bar::, call isFullyQualifiedNamespaceEqualTo(NS, "bar", "foo")
template <class... NameTypes>
static bool isFullyQualifiedNamespaceEqualTo(const NamespaceDecl &NS,
                                             llvm::StringRef Name,
                                             NameTypes... Names) {
  if (!(NS.getDeclName().isIdentifier() && NS.getName() == Name &&
        NS.getParent() != nullptr))
    return false;
 
  if constexpr (sizeof...(NameTypes) > 0) {
    if (NS.getParent()->isTranslationUnit())
      return false;
    if (const auto *NextNS = dyn_cast_or_null<NamespaceDecl>(NS.getParent()))
      return isFullyQualifiedNamespaceEqualTo(*NextNS, Names...);
    return false;
  } else {
    return NS.getParent()->isTranslationUnit();
  }
}
 
static bool hasOptionalClassName(const CXXRecordDecl &RD) {
  if (!RD.getDeclName().isIdentifier())
    return false;
 
  if (RD.getName() == "optional") {
    if (const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext()))
      return N->isStdNamespace() ||
             isFullyQualifiedNamespaceEqualTo(*N, "absl");
    return false;
  }
 
  if (RD.getName() == "Optional") {
    // Check whether namespace is "::base" or "::folly".
    const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
    return N != nullptr && (isFullyQualifiedNamespaceEqualTo(*N, "base") ||
                            isFullyQualifiedNamespaceEqualTo(*N, "folly"));
  }
 
  if (RD.getName() == "Optional_Base") {
    const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
    return N != nullptr &&
           isFullyQualifiedNamespaceEqualTo(*N, "bslstl", "BloombergLP");
  }
 
  if (RD.getName() == "NullableValue") {
    const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
    return N != nullptr &&
           isFullyQualifiedNamespaceEqualTo(*N, "bdlb", "BloombergLP");
  }
 
  return false;
}
 
static const CXXRecordDecl *getOptionalBaseClass(const CXXRecordDecl *RD) {
  if (RD == nullptr)
    return nullptr;
  if (hasOptionalClassName(*RD))
    return RD;
 
  if (!RD->hasDefinition())
    return nullptr;
 
  for (const CXXBaseSpecifier &Base : RD->bases())
    if (const CXXRecordDecl *BaseClass =
            getOptionalBaseClass(Base.getType()->getAsCXXRecordDecl()))
      return BaseClass;
 
  return nullptr;
}
 
static bool isSupportedOptionalType(QualType Ty) {
  const CXXRecordDecl *Optional =
      getOptionalBaseClass(Ty->getAsCXXRecordDecl());
  return Optional != nullptr;
}
 
static bool isAssertionResultType(QualType Type) {
  if (Type.isNull())
    return false;
 
  if (auto *RD = Type->getAsRecordDecl())
    if (RD->getName() == "AssertionResult")
      if (const auto *N = dyn_cast_or_null<NamespaceDecl>(RD->getDeclContext()))
        return isFullyQualifiedNamespaceEqualTo(*N, "testing");
 
  return false;
}
 
namespace {
 
using namespace ::clang::ast_matchers;
 
using LatticeTransferState = TransferState<UncheckedOptionalAccessLattice>;
 
AST_MATCHER(CXXRecordDecl, optionalClass) { return hasOptionalClassName(Node); }
 
AST_MATCHER(CXXRecordDecl, optionalOrDerivedClass) {
  return getOptionalBaseClass(&Node) != nullptr;
}
 
auto desugarsToOptionalType() {
  return hasUnqualifiedDesugaredType(
      recordType(hasDeclaration(cxxRecordDecl(optionalClass()))));
}
 
auto desugarsToOptionalOrDerivedType() {
  return hasUnqualifiedDesugaredType(
      recordType(hasDeclaration(cxxRecordDecl(optionalOrDerivedClass()))));
}
 
auto hasOptionalType() { return hasType(desugarsToOptionalType()); }
 
/// Matches any of the spellings of the optional types and sugar, aliases,
/// derived classes, etc.
auto hasOptionalOrDerivedType() {
  return hasType(desugarsToOptionalOrDerivedType());
}
 
bool isDesugaredTypeOptional(QualType Ty) {
  const Type &DesugaredTy = *Ty->getUnqualifiedDesugaredType();
  return DesugaredTy.isRecordType() &&
         hasOptionalClassName(*DesugaredTy.getAsCXXRecordDecl());
}
 
bool isDesugaredTypeOptionalOrPointerToOptional(QualType Ty) {
  if (Ty->isPointerType())
    Ty = Ty->getPointeeType();
  return isDesugaredTypeOptional(Ty);
}
 
// Returns true if `E` is intended to refer to an optional type, but may refer
// to an internal base class of the optional type, and involve an
// UncheckedDerivedToBase cast.
//
// This is needed to correctly match methods called on types derived from
// `std::optional`, as methods may be defined in a private base class like
// `std::__optional_storage_base`.
//
// Say we have a `struct Derived : public std::optional<int> {} d;` For a call
// `d.has_value()`, the `getImplicitObjectArgument()` looks like this:
//
//   ImplicitCastExpr 'const std::__optional_storage_base<int>' lvalue
//   |     <UncheckedDerivedToBase (optional -> ... -> __optional_storage_base)>
//   `-DeclRefExpr 'Derived' lvalue Var 'd' 'Derived'
//
// The type of the implicit object argument is `__optional_storage_base`
// (since this is the internal type that `has_value()` is declared on). If we
// call `IgnoreParenImpCasts()` on the implicit object argument, we get the
// `DeclRefExpr`, which has type `Derived`. Neither of these types is
// `optional`, and hence neither is sufficient for querying whether we are
// calling a method on `optional`.
//
// Instead, starting with the most derived type, we need to follow the chain of
// casts, until we reach a class that matches
// `isDesugaredTypeOptionalOrPointerToOptional` (if at all).
bool hasReceiverTypeDesugaringToOptional(const Expr *E) {
  auto *Cast = dyn_cast<ImplicitCastExpr>(E->IgnoreParens());
  if (Cast == nullptr || Cast->getCastKind() != CK_UncheckedDerivedToBase)
    return isDesugaredTypeOptionalOrPointerToOptional(E->getType());
 
  // Usually, the SubExpr is already an optional type, so check the SubExpr
  // first before trying the cast path. The cast path helps in the case when the
  // SubExpr is a derived class.
  if (isDesugaredTypeOptionalOrPointerToOptional(Cast->getSubExpr()->getType()))
    return true;
 
  // See if we hit an optional type in the cast path, going from derived
  // to base.
  for (const CXXBaseSpecifier *Base : Cast->path()) {
    if (isDesugaredTypeOptional(Base->getType()))
      return true;
  }
 
  // We didn't find a optional in the cast path and the subexpr isn't an
  // optional. It may be that the subexpression itself has more relevant
  // implicit casts, so recurse and search further.
  return hasReceiverTypeDesugaringToOptional(Cast->getSubExpr());
}
 
AST_MATCHER(CXXMemberCallExpr, hasOptionalReceiverType) {
  return hasReceiverTypeDesugaringToOptional(Node.getImplicitObjectArgument());
}
 
AST_MATCHER(CXXOperatorCallExpr, hasOptionalOperatorObjectType) {
  return hasReceiverTypeDesugaringToOptional(Node.getArg(0));
}
 
auto isOptionalMemberCallWithNameMatcher(
    ast_matchers::internal::Matcher<NamedDecl> matcher,
    const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
  return cxxMemberCallExpr(
      Ignorable ? on(expr(unless(*Ignorable))) : anything(),
      callee(cxxMethodDecl(matcher)), hasOptionalReceiverType());
}
 
auto isOptionalOperatorCallWithName(
    llvm::StringRef operator_name,
    const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
  return cxxOperatorCallExpr(
      hasOverloadedOperatorName(operator_name), hasOptionalOperatorObjectType(),
      Ignorable ? callExpr(unless(hasArgument(0, *Ignorable))) : callExpr());
}
 
auto isMakeOptionalCall() {
  return callExpr(
      callee(functionDecl(hasAnyName(
          "std::make_optional", "base::make_optional", "absl::make_optional",
          "folly::make_optional", "bsl::make_optional"))),
      hasOptionalOrDerivedType());
}
 
auto nulloptTypeDecl() {
  return namedDecl(hasAnyName("std::nullopt_t", "absl::nullopt_t",
                              "base::nullopt_t", "folly::None",
                              "bsl::nullopt_t"));
}
 
auto hasNulloptType() { return hasType(nulloptTypeDecl()); }
 
auto inPlaceClass() {
  return namedDecl(hasAnyName("std::in_place_t", "absl::in_place_t",
                              "base::in_place_t", "folly::in_place_t",
                              "bsl::in_place_t"));
}
 
auto allocatorArgClass() {
  return namedDecl(hasAnyName("std::allocator_arg_t", "bsl::allocator_arg_t"));
}
 
auto hasAllocatorArgType() { return hasType(allocatorArgClass()); }
 
auto isOptionalNulloptConstructor() {
  return cxxConstructExpr(
      hasDeclaration(cxxConstructorDecl(parameterCountIs(1),
                                        hasParameter(0, hasNulloptType()))),
      hasOptionalOrDerivedType());
}
 
auto isOptionalInPlaceConstructor() {
  return cxxConstructExpr(hasAnyArgument(hasType(inPlaceClass())),
                          hasOptionalOrDerivedType());
}
 
// `optional(value, ...)`. Arguments after the value are ignored. Tag types are
// excluded because they denote other constructions.
auto isOptionalValueOrConversionConstructor() {
  return cxxConstructExpr(
      unless(hasDeclaration(
          cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
      argumentCountAtLeast(1),
      hasArgument(0, unless(anyOf(hasNulloptType(), hasType(inPlaceClass()),
                                  hasAllocatorArgType()))),
      hasOptionalOrDerivedType());
}
 
// `optional(allocator_arg_t, allocator, value, ...)`.
// Used only for BDE components (`bsl::optional`, `bdlb::NullableValue`)
// which support allocators.
auto isOptionalAllocatorExtendedValueOrConversionConstructor() {
  return cxxConstructExpr(
      unless(hasDeclaration(
          cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
      hasArgument(0, hasAllocatorArgType()), argumentCountAtLeast(3),
      hasArgument(2, unless(anyOf(hasNulloptType(), hasType(inPlaceClass())))),
      hasOptionalOrDerivedType());
}
 
auto isOptionalValueOrConversionAssignment() {
  return cxxOperatorCallExpr(
      hasOverloadedOperatorName("="),
      callee(cxxMethodDecl(ofClass(optionalOrDerivedClass()))),
      unless(hasDeclaration(cxxMethodDecl(
          anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))),
      argumentCountIs(2), hasArgument(1, unless(hasNulloptType())));
}
 
auto isOptionalNulloptAssignment() {
  return cxxOperatorCallExpr(
      hasOverloadedOperatorName("="),
      callee(cxxMethodDecl(ofClass(optionalOrDerivedClass()))),
      argumentCountIs(2), hasArgument(1, hasNulloptType()));
}
 
auto isStdSwapCall() {
  return callExpr(callee(functionDecl(hasName("std::swap"))),
                  argumentCountIs(2),
                  hasArgument(0, hasOptionalOrDerivedType()),
                  hasArgument(1, hasOptionalOrDerivedType()));
}
 
auto isStdForwardCall() {
  return callExpr(callee(functionDecl(hasName("std::forward"))),
                  argumentCountIs(1),
                  hasArgument(0, hasOptionalOrDerivedType()));
}
 
auto isAssertionResultOperatorBoolCall() {
  return cxxMemberCallExpr(
      on(expr(unless(cxxThisExpr()))),
      callee(cxxMethodDecl(hasName("operator bool"),
                           ofClass(hasName("testing::AssertionResult")))));
}
 
auto isAssertionResultConstructFromBoolCall() {
  return cxxConstructExpr(
      hasType(recordDecl(hasName("testing::AssertionResult"))),
      hasArgument(0, hasType(booleanType())));
}
 
auto isAssertionResultConstructFromOptionalCall() {
  return cxxConstructExpr(
      hasType(recordDecl(hasName("testing::AssertionResult"))),
      hasArgument(0, hasOptionalOrDerivedType()));
}
 
constexpr llvm::StringLiteral ValueOrCallID = "ValueOrCall";
 
auto isValueOrStringEmptyCall() {
  // `opt.value_or("").empty()`
  return cxxMemberCallExpr(
      callee(cxxMethodDecl(hasName("empty"))),
      onImplicitObjectArgument(ignoringImplicit(
          cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
                            callee(cxxMethodDecl(hasName("value_or"),
                                                 ofClass(optionalClass()))),
                            hasArgument(0, stringLiteral(hasSize(0))))
              .bind(ValueOrCallID))));
}
 
auto isValueOrNotEqX() {
  auto ComparesToSame = [](ast_matchers::internal::Matcher<Stmt> Arg) {
    return hasOperands(
        ignoringImplicit(
            cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
                              callee(cxxMethodDecl(hasName("value_or"),
                                                   ofClass(optionalClass()))),
                              hasArgument(0, Arg))
                .bind(ValueOrCallID)),
        ignoringImplicit(Arg));
  };
 
  // `opt.value_or(X) != X`, for X is `nullptr`, `""`, or `0`. Ideally, we'd
  // support this pattern for any expression, but the AST does not have a
  // generic expression comparison facility, so we specialize to common cases
  // seen in practice.  FIXME: define a matcher that compares values across
  // nodes, which would let us generalize this to any `X`.
  return binaryOperation(hasOperatorName("!="),
                         anyOf(ComparesToSame(cxxNullPtrLiteralExpr()),
                               ComparesToSame(stringLiteral(hasSize(0))),
                               ComparesToSame(integerLiteral(equals(0)))));
}
 
auto isZeroParamConstMemberCall() {
  return cxxMemberCallExpr(
      callee(cxxMethodDecl(parameterCountIs(0), isConst())));
}
 
auto isZeroParamConstMemberOperatorCall() {
  return cxxOperatorCallExpr(
      callee(cxxMethodDecl(parameterCountIs(0), isConst())));
}
 
auto isNonConstMemberCall() {
  return cxxMemberCallExpr(callee(cxxMethodDecl(unless(isConst()))));
}
 
auto isNonConstMemberOperatorCall() {
  return cxxOperatorCallExpr(callee(cxxMethodDecl(unless(isConst()))));
}
 
auto isCallReturningOptional() {
  return callExpr(hasType(qualType(
      anyOf(desugarsToOptionalOrDerivedType(),
            referenceType(pointee(desugarsToOptionalOrDerivedType()))))));
}
 
template <typename L, typename R>
auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
  return cxxOperatorCallExpr(
      anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
      argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
      hasArgument(1, rhs_arg_matcher));
}
 
/// Ensures that `Expr` is mapped to a `BoolValue` and returns its formula.
const Formula &forceBoolValue(Environment &Env, const Expr &Expr) {
  auto *Value = Env.get<BoolValue>(Expr);
  if (Value != nullptr)
    return Value->formula();
 
  Value = &Env.makeAtomicBoolValue();
  Env.setValue(Expr, *Value);
  return Value->formula();
}
 
StorageLocation &locForHasValue(const RecordStorageLocation &OptionalLoc) {
  return OptionalLoc.getSyntheticField("has_value");
}
 
StorageLocation &locForValue(const RecordStorageLocation &OptionalLoc) {
  return OptionalLoc.getSyntheticField("value");
}
 
StorageLocation &
locForAssertResultSuccess(const RecordStorageLocation &AssertResultLoc) {
  return AssertResultLoc.getSyntheticField("success");
}
 
/// Sets `HasValueVal` as the symbolic value that represents the "has_value"
/// property of the optional at `OptionalLoc`.
void setHasValue(RecordStorageLocation &OptionalLoc, BoolValue &HasValueVal,
                 Environment &Env) {
  Env.setValue(locForHasValue(OptionalLoc), HasValueVal);
}
 
/// Returns the symbolic value that represents the "has_value" property of the
/// optional at `OptionalLoc`. Returns null if `OptionalLoc` is null.
BoolValue *getHasValue(Environment &Env, RecordStorageLocation *OptionalLoc) {
  if (OptionalLoc == nullptr)
    return nullptr;
  StorageLocation &HasValueLoc = locForHasValue(*OptionalLoc);
  auto *HasValueVal = Env.get<BoolValue>(HasValueLoc);
  if (HasValueVal == nullptr) {
    HasValueVal = &Env.makeAtomicBoolValue();
    Env.setValue(HasValueLoc, *HasValueVal);
  }
  return HasValueVal;
}
 
QualType valueTypeFromOptionalDecl(const CXXRecordDecl &RD) {
  auto &CTSD = cast<ClassTemplateSpecializationDecl>(RD);
  return CTSD.getTemplateArgs()[0].getAsType();
}
 
/// 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) {
  const CXXRecordDecl *Optional =
      getOptionalBaseClass(Type->getAsCXXRecordDecl());
  if (Optional == nullptr)
    return 0;
  return 1 + countOptionalWrappers(
                 ASTCtx,
                 valueTypeFromOptionalDecl(*Optional).getDesugaredType(ASTCtx));
}
 
StorageLocation *getLocBehindPossiblePointer(const Expr &E,
                                             const Environment &Env) {
  if (E.isPRValue()) {
    if (auto *PointerVal = dyn_cast_or_null<PointerValue>(Env.getValue(E)))
      return &PointerVal->getPointeeLoc();
    return nullptr;
  }
  return Env.getStorageLocation(E);
}
 
void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
                        LatticeTransferState &State) {
  if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
          getLocBehindPossiblePointer(*ObjectExpr, State.Env))) {
    if (State.Env.getStorageLocation(*UnwrapExpr) == nullptr)
      State.Env.setStorageLocation(*UnwrapExpr, locForValue(*OptionalLoc));
  }
}
 
void transferArrowOpCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
                         LatticeTransferState &State) {
  if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
          getLocBehindPossiblePointer(*ObjectExpr, State.Env)))
    State.Env.setValue(
        *UnwrapExpr, State.Env.create<PointerValue>(locForValue(*OptionalLoc)));
}
 
void transferMakeOptionalCall(const CallExpr *E,
                              const MatchFinder::MatchResult &,
                              LatticeTransferState &State) {
  setHasValue(State.Env.getResultObjectLocation(*E),
              State.Env.getBoolLiteralValue(true), State.Env);
}
 
void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
                                  const MatchFinder::MatchResult &,
                                  LatticeTransferState &State) {
  if (auto *HasValueVal = getHasValue(
          State.Env, getImplicitObjectLocation(*CallExpr, State.Env))) {
    State.Env.setValue(*CallExpr, *HasValueVal);
  }
}
 
void transferOptionalIsNullCall(const CXXMemberCallExpr *CallExpr,
                                const MatchFinder::MatchResult &,
                                LatticeTransferState &State) {
  if (auto *HasValueVal = getHasValue(
          State.Env, getImplicitObjectLocation(*CallExpr, State.Env))) {
    State.Env.setValue(*CallExpr, State.Env.makeNot(*HasValueVal));
  }
}
 
/// `ModelPred` builds a logical formula relating the predicate in
/// `ValueOrPredExpr` to the optional's `has_value` property.
void transferValueOrImpl(
    const clang::Expr *ValueOrPredExpr, const MatchFinder::MatchResult &Result,
    LatticeTransferState &State,
    const Formula &(*ModelPred)(Environment &Env, const Formula &ExprVal,
                                const Formula &HasValueVal)) {
  auto &Env = State.Env;
 
  const auto *MCE =
      Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID);
 
  auto *HasValueVal =
      getHasValue(State.Env, getImplicitObjectLocation(*MCE, State.Env));
  if (HasValueVal == nullptr)
    return;
 
  Env.assume(ModelPred(Env, forceBoolValue(Env, *ValueOrPredExpr),
                       HasValueVal->formula()));
}
 
void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
                                    const MatchFinder::MatchResult &Result,
                                    LatticeTransferState &State) {
  return transferValueOrImpl(ComparisonExpr, Result, State,
                             [](Environment &Env, const Formula &ExprVal,
                                const Formula &HasValueVal) -> const Formula & {
                               auto &A = Env.arena();
                               // If the result is *not* empty, then we know the
                               // optional must have been holding a value. If
                               // `ExprVal` is true, though, we don't learn
                               // anything definite about `has_value`, so we
                               // don't add any corresponding implications to
                               // the flow condition.
                               return A.makeImplies(A.makeNot(ExprVal),
                                                    HasValueVal);
                             });
}
 
void transferValueOrNotEqX(const Expr *ComparisonExpr,
                           const MatchFinder::MatchResult &Result,
                           LatticeTransferState &State) {
  transferValueOrImpl(ComparisonExpr, Result, State,
                      [](Environment &Env, const Formula &ExprVal,
                         const Formula &HasValueVal) -> const Formula & {
                        auto &A = Env.arena();
                        // We know that if `(opt.value_or(X) != X)` then
                        // `opt.hasValue()`, even without knowing further
                        // details about the contents of `opt`.
                        return A.makeImplies(ExprVal, HasValueVal);
                      });
}
 
void transferCallReturningOptional(const CallExpr *E,
                                   const MatchFinder::MatchResult &Result,
                                   LatticeTransferState &State) {
  RecordStorageLocation *Loc = nullptr;
  if (E->isPRValue()) {
    Loc = &State.Env.getResultObjectLocation(*E);
  } else {
    Loc = State.Env.get<RecordStorageLocation>(*E);
    if (Loc == nullptr) {
      Loc = &cast<RecordStorageLocation>(State.Env.createStorageLocation(*E));
      State.Env.setStorageLocation(*E, *Loc);
    }
  }
 
  if (State.Env.getValue(locForHasValue(*Loc)) != nullptr)
    return;
 
  setHasValue(*Loc, State.Env.makeAtomicBoolValue(), State.Env);
}
 
// Returns true if the const accessor is handled by caching.
// Returns false if we could not cache. We should perform default handling
// in that case.
bool handleConstMemberCall(const CallExpr *CE,
                           dataflow::RecordStorageLocation *RecordLoc,
                           const MatchFinder::MatchResult &Result,
                           LatticeTransferState &State) {
  if (RecordLoc == nullptr)
    return false;
 
  // Cache if the const method returns a reference.
  if (CE->isGLValue()) {
    const FunctionDecl *DirectCallee = CE->getDirectCallee();
    if (DirectCallee == nullptr)
      return false;
 
    // Initialize the optional's "has_value" property to true if the type is
    // optional, otherwise no-op. If we want to support const ref to pointers or
    // bools we should initialize their values here too.
    auto Init = [&](StorageLocation &Loc) {
      if (isSupportedOptionalType(CE->getType()))
        setHasValue(cast<RecordStorageLocation>(Loc),
                    State.Env.makeAtomicBoolValue(), State.Env);
    };
    StorageLocation &Loc =
        State.Lattice.getOrCreateConstMethodReturnStorageLocation(
            *RecordLoc, DirectCallee, State.Env, Init);
 
    State.Env.setStorageLocation(*CE, Loc);
    return true;
  }
  // PRValue cases:
  if (CE->getType()->isBooleanType() || CE->getType()->isPointerType()) {
    // If the const method returns a boolean or pointer type.
    Value *Val = State.Lattice.getOrCreateConstMethodReturnValue(*RecordLoc, CE,
                                                                 State.Env);
    if (Val == nullptr)
      return false;
    State.Env.setValue(*CE, *Val);
    return true;
  }
  if (isSupportedOptionalType(CE->getType())) {
    // If the const method returns an optional by value.
    const FunctionDecl *DirectCallee = CE->getDirectCallee();
    if (DirectCallee == nullptr)
      return false;
    StorageLocation &Loc =
        State.Lattice.getOrCreateConstMethodReturnStorageLocation(
            *RecordLoc, DirectCallee, State.Env, [&](StorageLocation &Loc) {
              setHasValue(cast<RecordStorageLocation>(Loc),
                          State.Env.makeAtomicBoolValue(), State.Env);
            });
    // Use copyRecord to link the optional to the result object of the call
    // expression.
    auto &ResultLoc = State.Env.getResultObjectLocation(*CE);
    copyRecord(cast<RecordStorageLocation>(Loc), ResultLoc, State.Env);
    return true;
  }
 
  return false;
}
 
void handleConstMemberCallWithFallbacks(
    const CallExpr *CE, dataflow::RecordStorageLocation *RecordLoc,
    const MatchFinder::MatchResult &Result, LatticeTransferState &State) {
  if (handleConstMemberCall(CE, RecordLoc, Result, State))
    return;
  // Perform default handling if the call returns an optional, but wasn't
  // handled by caching.
  if (isSupportedOptionalType(CE->getType()))
    transferCallReturningOptional(CE, Result, State);
}
 
void transferConstMemberCall(const CXXMemberCallExpr *MCE,
                             const MatchFinder::MatchResult &Result,
                             LatticeTransferState &State) {
  handleConstMemberCallWithFallbacks(
      MCE, dataflow::getImplicitObjectLocation(*MCE, State.Env), Result, State);
}
 
void transferConstMemberOperatorCall(const CXXOperatorCallExpr *OCE,
                                     const MatchFinder::MatchResult &Result,
                                     LatticeTransferState &State) {
  auto *RecordLoc = cast_or_null<dataflow::RecordStorageLocation>(
      State.Env.getStorageLocation(*OCE->getArg(0)));
  handleConstMemberCallWithFallbacks(OCE, RecordLoc, Result, State);
}
 
void handleNonConstMemberCall(const CallExpr *CE,
                              dataflow::RecordStorageLocation *RecordLoc,
                              const MatchFinder::MatchResult &Result,
                              LatticeTransferState &State) {
  if (RecordLoc != nullptr) {
    // When a non-const member function is called, clear all (non-const)
    // optional fields of the receiver. Const-qualified fields can't be
    // changed (at least, not without UB).
    for (const auto &[Field, FieldLoc] : RecordLoc->children()) {
      QualType FieldType = Field->getType();
      if (!FieldType.isConstQualified() &&
          isSupportedOptionalType(Field->getType())) {
        auto *FieldRecordLoc = cast_or_null<RecordStorageLocation>(FieldLoc);
        if (FieldRecordLoc) {
          setHasValue(*FieldRecordLoc, State.Env.makeAtomicBoolValue(),
                      State.Env);
        }
      }
    }
    State.Lattice.clearConstMethodReturnValues(*RecordLoc);
    State.Lattice.clearConstMethodReturnStorageLocations(*RecordLoc);
  }
 
  // Perform default handling if the call returns an optional.
  if (isSupportedOptionalType(CE->getType())) {
    transferCallReturningOptional(CE, Result, State);
  }
}
 
void transferValue_NonConstMemberCall(const CXXMemberCallExpr *MCE,
                                      const MatchFinder::MatchResult &Result,
                                      LatticeTransferState &State) {
  handleNonConstMemberCall(
      MCE, dataflow::getImplicitObjectLocation(*MCE, State.Env), Result, State);
}
 
void transferValue_NonConstMemberOperatorCall(
    const CXXOperatorCallExpr *OCE, const MatchFinder::MatchResult &Result,
    LatticeTransferState &State) {
  auto *RecordLoc = cast_or_null<dataflow::RecordStorageLocation>(
      State.Env.getStorageLocation(*OCE->getArg(0)));
  handleNonConstMemberCall(OCE, RecordLoc, Result, State);
}
 
void constructOptionalValue(const Expr &E, Environment &Env,
                            BoolValue &HasValueVal) {
  RecordStorageLocation &Loc = Env.getResultObjectLocation(E);
  setHasValue(Loc, HasValueVal, Env);
}
 
/// Returns a symbolic value for the "has_value" property of an `optional<T>`
/// value that is constructed/assigned from a value of type `U` or `optional<U>`
/// where `T` is constructible from `U`.
BoolValue &valueOrConversionHasValue(QualType DestType, const Expr &E,
                                     const MatchFinder::MatchResult &MatchRes,
                                     LatticeTransferState &State) {
  const int DestTypeOptionalWrappersCount =
      countOptionalWrappers(*MatchRes.Context, DestType);
  const int ArgTypeOptionalWrappersCount = countOptionalWrappers(
      *MatchRes.Context, E.getType().getNonReferenceType());
 
  // Is this an constructor of the form `template<class U> optional(U &&)` /
  // assignment of the form `template<class U> optional& operator=(U &&)`
  // (where `T` is assignable / constructible from `U`)?
  // We recognize this because the number of optionals in the optional being
  // assigned to is different from the function argument type.
  if (DestTypeOptionalWrappersCount != ArgTypeOptionalWrappersCount)
    return State.Env.getBoolLiteralValue(true);
 
  // Otherwise, this must be a constructor of the form
  // `template <class U> optional<optional<U> &&)` / assignment of the form
  // `template <class U> optional& operator=(optional<U> &&)
  // (where, again, `T` is assignable / constructible from `U`).
  auto *Loc = State.Env.get<RecordStorageLocation>(E);
  if (auto *HasValueVal = getHasValue(State.Env, Loc))
    return *HasValueVal;
  return State.Env.makeAtomicBoolValue();
}
 
void transferValueOrConversionConstructorImpl(
    const CXXConstructExpr *E, unsigned ValueArgIdx,
    const MatchFinder::MatchResult &MatchRes, LatticeTransferState &State) {
  assert(E->getNumArgs() > ValueArgIdx);
 
  constructOptionalValue(
      *E, State.Env,
      valueOrConversionHasValue(
          E->getConstructor()->getThisType()->getPointeeType(),
          *E->getArg(ValueArgIdx), MatchRes, State));
}
 
void transferValueOrConversionConstructor(
    const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
    LatticeTransferState &State) {
  transferValueOrConversionConstructorImpl(E, /*ValueArgIdx=*/0, MatchRes,
                                           State);
}
 
void transferAllocatorExtendedValueOrConversionConstructor(
    const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
    LatticeTransferState &State) {
  transferValueOrConversionConstructorImpl(E, /*ValueArgIdx=*/2, MatchRes,
                                           State);
}
 
void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
                        LatticeTransferState &State) {
  assert(E->getNumArgs() > 0);
 
  if (auto *Loc = State.Env.get<RecordStorageLocation>(*E->getArg(0))) {
    setHasValue(*Loc, HasValueVal, State.Env);
 
    // Assign a storage location for the whole expression.
    State.Env.setStorageLocation(*E, *Loc);
  }
}
 
void transferValueOrConversionAssignment(
    const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
    LatticeTransferState &State) {
  assert(E->getNumArgs() > 1);
  transferAssignment(
      E,
      valueOrConversionHasValue(E->getArg(0)->getType().getNonReferenceType(),
                                *E->getArg(1), MatchRes, State),
      State);
}
 
void transferNulloptAssignment(const CXXOperatorCallExpr *E,
                               const MatchFinder::MatchResult &,
                               LatticeTransferState &State) {
  transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
}
 
void transferSwap(RecordStorageLocation *Loc1, RecordStorageLocation *Loc2,
                  Environment &Env) {
  // We account for cases where one or both of the optionals are not modeled,
  // either lacking associated storage locations, or lacking values associated
  // to such storage locations.
 
  if (Loc1 == nullptr) {
    if (Loc2 != nullptr)
      setHasValue(*Loc2, Env.makeAtomicBoolValue(), Env);
    return;
  }
  if (Loc2 == nullptr) {
    setHasValue(*Loc1, Env.makeAtomicBoolValue(), Env);
    return;
  }
 
  // Both expressions have locations, though they may not have corresponding
  // values. In that case, we create a fresh value at this point. Note that if
  // two branches both do this, they will not share the value, but it at least
  // allows for local reasoning about the value. To avoid the above, we would
  // need *lazy* value allocation.
  // FIXME: allocate values lazily, instead of just creating a fresh value.
  BoolValue *BoolVal1 = getHasValue(Env, Loc1);
  if (BoolVal1 == nullptr)
    BoolVal1 = &Env.makeAtomicBoolValue();
 
  BoolValue *BoolVal2 = getHasValue(Env, Loc2);
  if (BoolVal2 == nullptr)
    BoolVal2 = &Env.makeAtomicBoolValue();
 
  setHasValue(*Loc1, *BoolVal2, Env);
  setHasValue(*Loc2, *BoolVal1, Env);
}
 
void transferSwapCall(const CXXMemberCallExpr *E,
                      const MatchFinder::MatchResult &,
                      LatticeTransferState &State) {
  assert(E->getNumArgs() == 1);
  auto *OtherLoc = State.Env.get<RecordStorageLocation>(*E->getArg(0));
  transferSwap(getImplicitObjectLocation(*E, State.Env), OtherLoc, State.Env);
}
 
void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
                         LatticeTransferState &State) {
  assert(E->getNumArgs() == 2);
  auto *Arg0Loc = State.Env.get<RecordStorageLocation>(*E->getArg(0));
  auto *Arg1Loc = State.Env.get<RecordStorageLocation>(*E->getArg(1));
  transferSwap(Arg0Loc, Arg1Loc, State.Env);
}
 
void transferStdForwardCall(const CallExpr *E, const MatchFinder::MatchResult &,
                            LatticeTransferState &State) {
  assert(E->getNumArgs() == 1);
 
  if (auto *Loc = State.Env.getStorageLocation(*E->getArg(0)))
    State.Env.setStorageLocation(*E, *Loc);
}
 
const Formula &evaluateEquality(Arena &A, const Formula &EqVal,
                                const Formula &LHS, const Formula &RHS) {
  // Logically, an optional<T> object is composed of two values - a `has_value`
  // bit and a value of type T. Equality of optional objects compares both
  // values. Therefore, merely comparing the `has_value` bits isn't sufficient:
  // when two optional objects are engaged, the equality of their respective
  // values of type T matters. Since we only track the `has_value` bits, we
  // can't make any conclusions about equality when we know that two optional
  // objects are engaged.
  //
  // We express this as two facts about the equality:
  // a) EqVal => (LHS == RHS)
  // b) (!LHS & !RHS) => EqVal
  //    If neither is set, then they are equal.
  // We rewrite b) as !EqVal => (LHS v RHS), for a more compact formula.
  return A.makeAnd(A.makeImplies(EqVal, A.makeEquals(LHS, RHS)),
                   A.makeImplies(A.makeNot(EqVal), A.makeOr(LHS, RHS)));
}
 
void transferOptionalAndOptionalCmp(const clang::CXXOperatorCallExpr *CmpExpr,
                                    const MatchFinder::MatchResult &,
                                    LatticeTransferState &State) {
  Environment &Env = State.Env;
  auto &A = Env.arena();
  auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
  auto *Arg0Loc = Env.get<RecordStorageLocation>(*CmpExpr->getArg(0));
  if (auto *LHasVal = getHasValue(Env, Arg0Loc)) {
    auto *Arg1Loc = Env.get<RecordStorageLocation>(*CmpExpr->getArg(1));
    if (auto *RHasVal = getHasValue(Env, Arg1Loc)) {
      if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
        CmpValue = &A.makeNot(*CmpValue);
      Env.assume(evaluateEquality(A, *CmpValue, LHasVal->formula(),
                                  RHasVal->formula()));
    }
  }
}
 
void transferOptionalAndValueCmp(const clang::CXXOperatorCallExpr *CmpExpr,
                                 const clang::Expr *E, Environment &Env) {
  auto &A = Env.arena();
  auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
  auto *Loc = Env.get<RecordStorageLocation>(*E);
  if (auto *HasVal = getHasValue(Env, Loc)) {
    if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
      CmpValue = &A.makeNot(*CmpValue);
    Env.assume(
        evaluateEquality(A, *CmpValue, HasVal->formula(), A.makeLiteral(true)));
  }
}
 
void transferOptionalAndNulloptCmp(const clang::CXXOperatorCallExpr *CmpExpr,
                                   const clang::Expr *E, Environment &Env) {
  auto &A = Env.arena();
  auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
  auto *Loc = Env.get<RecordStorageLocation>(*E);
  if (auto *HasVal = getHasValue(Env, Loc)) {
    if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
      CmpValue = &A.makeNot(*CmpValue);
    Env.assume(evaluateEquality(A, *CmpValue, HasVal->formula(),
                                A.makeLiteral(false)));
  }
}
 
void transferAssertionResultOperatorBoolCall(const CXXMemberCallExpr *Expr,
                                             const MatchFinder::MatchResult &,
                                             LatticeTransferState &State) {
  auto *AssertResultLoc = getImplicitObjectLocation(*Expr, State.Env);
  if (AssertResultLoc == nullptr)
    return;
 
  if (BoolValue *SuccessVal = State.Env.get<BoolValue>(
          locForAssertResultSuccess(*AssertResultLoc))) {
    State.Env.setValue(*Expr, *SuccessVal);
  }
}
 
void transferAssertionResultConstructFromBoolCall(
    const CXXConstructExpr *ConstructExpr, const MatchFinder::MatchResult &,
    LatticeTransferState &State) {
  assert(ConstructExpr->getNumArgs() > 0);
  const Expr *Arg = ConstructExpr->getArg(0)->IgnoreImplicit();
 
  if (BoolValue *SuccessVal = State.Env.get<BoolValue>(*Arg)) {
    auto &ResultLoc = State.Env.getResultObjectLocation(*ConstructExpr);
    State.Env.setValue(locForAssertResultSuccess(ResultLoc), *SuccessVal);
  }
}
 
void transferAssertionResultConstructFromOptionalCall(
    const CXXConstructExpr *ConstructExpr, const MatchFinder::MatchResult &,
    LatticeTransferState &State) {
  assert(ConstructExpr->getNumArgs() > 0);
 
  const Expr *Arg = ConstructExpr->getArg(0)->IgnoreImplicit();
  auto *OptionalLoc =
      cast_or_null<RecordStorageLocation>(State.Env.getStorageLocation(*Arg));
  if (OptionalLoc == nullptr)
    return;
 
  if (BoolValue *HasVal = getHasValue(State.Env, OptionalLoc)) {
    auto &ResultLoc = State.Env.getResultObjectLocation(*ConstructExpr);
    State.Env.setValue(locForAssertResultSuccess(ResultLoc), *HasVal);
  }
}
 
std::optional<StatementMatcher>
ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) {
  if (Options.IgnoreSmartPointerDereference) {
    auto SmartPtrUse = expr(ignoringParenImpCasts(cxxOperatorCallExpr(
        anyOf(hasOverloadedOperatorName("->"), hasOverloadedOperatorName("*")),
        unless(hasArgument(0, expr(hasOptionalType()))))));
    return expr(
        anyOf(SmartPtrUse, memberExpr(hasObjectExpression(SmartPtrUse))));
  }
  return std::nullopt;
}
 
StatementMatcher
valueCall(const std::optional<StatementMatcher> &IgnorableOptional) {
  return isOptionalMemberCallWithNameMatcher(hasName("value"),
                                             IgnorableOptional);
}
 
StatementMatcher
valueOperatorCall(const std::optional<StatementMatcher> &IgnorableOptional) {
  return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional),
                    isOptionalOperatorCallWithName("->", IgnorableOptional)));
}
 
auto buildTransferMatchSwitch() {
  // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
  // lot of duplicated work (e.g. string comparisons), consider providing APIs
  // that avoid it through memoization.
  return CFGMatchSwitchBuilder<LatticeTransferState>()
      // make_optional
      .CaseOfCFGStmt<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
 
      // optional::optional (in place)
      .CaseOfCFGStmt<CXXConstructExpr>(
          isOptionalInPlaceConstructor(),
          [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
             LatticeTransferState &State) {
            constructOptionalValue(*E, State.Env,
                                   State.Env.getBoolLiteralValue(true));
          })
      // optional::optional(nullopt_t)
      .CaseOfCFGStmt<CXXConstructExpr>(
          isOptionalNulloptConstructor(),
          [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
             LatticeTransferState &State) {
            constructOptionalValue(*E, State.Env,
                                   State.Env.getBoolLiteralValue(false));
          })
      // optional::optional (value/conversion)
      .CaseOfCFGStmt<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
                                       transferValueOrConversionConstructor)
      // optional::optional (allocator-extended value/conversion)
      .CaseOfCFGStmt<CXXConstructExpr>(
          isOptionalAllocatorExtendedValueOrConversionConstructor(),
          transferAllocatorExtendedValueOrConversionConstructor)
 
      // optional::operator=
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isOptionalValueOrConversionAssignment(),
          transferValueOrConversionAssignment)
      .CaseOfCFGStmt<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
                                          transferNulloptAssignment)
 
      // optional::value
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          valueCall(std::nullopt),
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
             LatticeTransferState &State) {
            transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
          })
 
      // optional::operator*
      .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("*"),
                               [](const CallExpr *E,
                                  const MatchFinder::MatchResult &,
                                  LatticeTransferState &State) {
                                 transferUnwrapCall(E, E->getArg(0), State);
                               })
 
      // optional::operator->
      .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("->"),
                               [](const CallExpr *E,
                                  const MatchFinder::MatchResult &,
                                  LatticeTransferState &State) {
                                 transferArrowOpCall(E, E->getArg(0), State);
                               })
 
      // optional::has_value, optional::hasValue
      // Of the supported optionals only folly::Optional uses hasValue, but this
      // will also pass for other types
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isOptionalMemberCallWithNameMatcher(
              hasAnyName("has_value", "hasValue")),
          transferOptionalHasValueCall)
 
      // optional::operator bool
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isOptionalMemberCallWithNameMatcher(hasName("operator bool")),
          transferOptionalHasValueCall)
 
      // NullableValue::isNull
      // Only NullableValue has isNull
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isOptionalMemberCallWithNameMatcher(hasName("isNull")),
          transferOptionalIsNullCall)
 
      // NullableValue::makeValue, NullableValue::makeValueInplace
      // Only NullableValue has these methods, but this
      // will also pass for other types
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isOptionalMemberCallWithNameMatcher(
              hasAnyName("makeValue", "makeValueInplace")),
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
             LatticeTransferState &State) {
            if (RecordStorageLocation *Loc =
                    getImplicitObjectLocation(*E, State.Env)) {
              setHasValue(*Loc, State.Env.getBoolLiteralValue(true), State.Env);
            }
          })
 
      // optional::emplace
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isOptionalMemberCallWithNameMatcher(hasName("emplace")),
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
             LatticeTransferState &State) {
            if (RecordStorageLocation *Loc =
                    getImplicitObjectLocation(*E, State.Env)) {
              setHasValue(*Loc, State.Env.getBoolLiteralValue(true), State.Env);
            }
          })
 
      // optional::reset
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isOptionalMemberCallWithNameMatcher(hasName("reset")),
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
             LatticeTransferState &State) {
            if (RecordStorageLocation *Loc =
                    getImplicitObjectLocation(*E, State.Env)) {
              setHasValue(*Loc, State.Env.getBoolLiteralValue(false),
                          State.Env);
            }
          })
 
      // optional::swap
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isOptionalMemberCallWithNameMatcher(hasName("swap")),
          transferSwapCall)
 
      // std::swap
      .CaseOfCFGStmt<CallExpr>(isStdSwapCall(), transferStdSwapCall)
 
      // std::forward
      .CaseOfCFGStmt<CallExpr>(isStdForwardCall(), transferStdForwardCall)
 
      // opt.value_or("").empty()
      .CaseOfCFGStmt<Expr>(isValueOrStringEmptyCall(),
                           transferValueOrStringEmptyCall)
 
      // opt.value_or(X) != X
      .CaseOfCFGStmt<Expr>(isValueOrNotEqX(), transferValueOrNotEqX)
 
      // Comparisons (==, !=):
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isComparisonOperatorCall(hasOptionalType(), hasOptionalType()),
          transferOptionalAndOptionalCmp)
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isComparisonOperatorCall(hasOptionalType(), hasNulloptType()),
          [](const clang::CXXOperatorCallExpr *Cmp,
             const MatchFinder::MatchResult &, LatticeTransferState &State) {
            transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(0), State.Env);
          })
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isComparisonOperatorCall(hasNulloptType(), hasOptionalType()),
          [](const clang::CXXOperatorCallExpr *Cmp,
             const MatchFinder::MatchResult &, LatticeTransferState &State) {
            transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(1), State.Env);
          })
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isComparisonOperatorCall(
              hasOptionalType(),
              unless(anyOf(hasOptionalType(), hasNulloptType()))),
          [](const clang::CXXOperatorCallExpr *Cmp,
             const MatchFinder::MatchResult &, LatticeTransferState &State) {
            transferOptionalAndValueCmp(Cmp, Cmp->getArg(0), State.Env);
          })
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isComparisonOperatorCall(
              unless(anyOf(hasOptionalType(), hasNulloptType())),
              hasOptionalType()),
          [](const clang::CXXOperatorCallExpr *Cmp,
             const MatchFinder::MatchResult &, LatticeTransferState &State) {
            transferOptionalAndValueCmp(Cmp, Cmp->getArg(1), State.Env);
          })
 
      // Smart-pointer-like operator* and operator-> calls that may look like
      // const accessors (below) but need special handling to allow mixing
      // the accessor calls.
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isSmartPointerLikeOperatorStar(),
          [](const CXXOperatorCallExpr *E,
             const MatchFinder::MatchResult &Result,
             LatticeTransferState &State) {
            transferSmartPointerLikeCachedDeref(
                E,
                dyn_cast_or_null<RecordStorageLocation>(
                    getLocBehindPossiblePointer(*E->getArg(0), State.Env)),
                State, [](StorageLocation &Loc) {});
          })
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isSmartPointerLikeOperatorArrow(),
          [](const CXXOperatorCallExpr *E,
             const MatchFinder::MatchResult &Result,
             LatticeTransferState &State) {
            transferSmartPointerLikeCachedGet(
                E,
                dyn_cast_or_null<RecordStorageLocation>(
                    getLocBehindPossiblePointer(*E->getArg(0), State.Env)),
                State, [](StorageLocation &Loc) {});
          })
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isSmartPointerLikeValueMethodCall(),
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &Result,
             LatticeTransferState &State) {
            transferSmartPointerLikeCachedDeref(
                E, getImplicitObjectLocation(*E, State.Env), State,
                [](StorageLocation &Loc) {});
          })
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          isSmartPointerLikeGetMethodCall(),
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &Result,
             LatticeTransferState &State) {
            transferSmartPointerLikeCachedGet(
                E, getImplicitObjectLocation(*E, State.Env), State,
                [](StorageLocation &Loc) {});
          })
 
      // gtest
      .CaseOfCFGStmt<CXXMemberCallExpr>(isAssertionResultOperatorBoolCall(),
                                        transferAssertionResultOperatorBoolCall)
      .CaseOfCFGStmt<CXXMemberCallExpr>(
          gtest::isAssertionResultExpectationOperatorBoolCall(),
          [](const CXXMemberCallExpr *Expr, const MatchFinder::MatchResult &,
             LatticeTransferState &State) {
            return gtest::transferAssertionResultExpectationOperatorBoolCall(
                Expr, State.Env, locForAssertResultSuccess);
          })
      .CaseOfCFGStmt<CXXConstructExpr>(
          isAssertionResultConstructFromBoolCall(),
          transferAssertionResultConstructFromBoolCall)
      .CaseOfCFGStmt<CXXConstructExpr>(
          isAssertionResultConstructFromOptionalCall(),
          transferAssertionResultConstructFromOptionalCall)
      // const accessor calls
      .CaseOfCFGStmt<CXXMemberCallExpr>(isZeroParamConstMemberCall(),
                                        transferConstMemberCall)
      .CaseOfCFGStmt<CXXOperatorCallExpr>(isZeroParamConstMemberOperatorCall(),
                                          transferConstMemberOperatorCall)
      // non-const member calls that may modify the state of an object.
      .CaseOfCFGStmt<CXXMemberCallExpr>(isNonConstMemberCall(),
                                        transferValue_NonConstMemberCall)
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
          isNonConstMemberOperatorCall(),
          transferValue_NonConstMemberOperatorCall)
 
      // other cases of returning optional
      .CaseOfCFGStmt<CallExpr>(isCallReturningOptional(),
                               transferCallReturningOptional)
 
      .Build();
}
 
llvm::SmallVector<UncheckedOptionalAccessDiagnostic>
diagnoseUnwrapCall(const Expr *ObjectExpr, const Environment &Env) {
  if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
          getLocBehindPossiblePointer(*ObjectExpr, Env))) {
    auto *Prop = Env.getValue(locForHasValue(*OptionalLoc));
    if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
      if (Env.proves(HasValueVal->formula()))
        return {};
    }
  }
 
  // Record that this unwrap is *not* provably safe.
  // FIXME: include the name of the optional (if applicable).
  auto Range = CharSourceRange::getTokenRange(ObjectExpr->getSourceRange());
  return {UncheckedOptionalAccessDiagnostic{Range}};
}
 
auto buildDiagnoseMatchSwitch(
    const UncheckedOptionalAccessModelOptions &Options) {
  // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
  // lot of duplicated work (e.g. string comparisons), consider providing APIs
  // that avoid it through memoization.
  const auto IgnorableOptional = ignorableOptional(Options);
 
  auto DiagBuilder =
      CFGMatchSwitchBuilder<
          const Environment,
          llvm::SmallVector<UncheckedOptionalAccessDiagnostic>>()
          // optional::operator*, optional::operator->
          .CaseOfCFGStmt<CallExpr>(
              valueOperatorCall(IgnorableOptional),
              [](const CallExpr *E, const MatchFinder::MatchResult &,
                 const Environment &Env) {
                return diagnoseUnwrapCall(E->getArg(0), Env);
              });
 
  auto Builder = Options.IgnoreValueCalls
                     ? std::move(DiagBuilder)
                     : std::move(DiagBuilder)
                           // optional::value
                           .CaseOfCFGStmt<CXXMemberCallExpr>(
                               valueCall(IgnorableOptional),
                               [](const CXXMemberCallExpr *E,
                                  const MatchFinder::MatchResult &,
                                  const Environment &Env) {
                                 return diagnoseUnwrapCall(
                                     E->getImplicitObjectArgument(), Env);
                               });
 
  return std::move(Builder).Build();
}
 
} // namespace
 
ast_matchers::StatementMatcher
UncheckedOptionalAccessModel::memberCallToOptionalClass() {
  return cxxMemberCallExpr(hasOptionalReceiverType());
}
 
ast_matchers::StatementMatcher
UncheckedOptionalAccessModel::operatorCallToOptionalClass() {
  return cxxOperatorCallExpr(hasOptionalOperatorObjectType());
}
 
UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx,
                                                           Environment &Env)
    : DataflowAnalysis<UncheckedOptionalAccessModel,
                       UncheckedOptionalAccessLattice>(Ctx),
      TransferMatchSwitch(buildTransferMatchSwitch()) {
  Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
      [&Ctx](QualType Ty) -> llvm::StringMap<QualType> {
        if (isAssertionResultType(Ty))
          return {{"success", Ctx.BoolTy}};
 
        const CXXRecordDecl *Optional =
            getOptionalBaseClass(Ty->getAsCXXRecordDecl());
        if (Optional == nullptr)
          return {};
        return {{"value", valueTypeFromOptionalDecl(*Optional)},
                {"has_value", Ctx.BoolTy}};
      });
}
 
void UncheckedOptionalAccessModel::transfer(const CFGElement &Elt,
                                            UncheckedOptionalAccessLattice &L,
                                            Environment &Env) {
  LatticeTransferState State(L, Env);
  TransferMatchSwitch(Elt, getASTContext(), State);
}
 
UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser(
    UncheckedOptionalAccessModelOptions Options)
    : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {}
 
} // namespace dataflow
} // namespace clang