[clang][dataflow] Add support for `value_or` in a comparison.

[ymandel]

Summary

This patch adds limited modeling of the value_or method. Specifically, when
used in a particular idiom in a comparison to implicitly check whether the
optional holds a value.

[sgatev]

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

119

Why handle negation here? Would it work for if (opt.value_or("").empty()) { ... } else { opt.value(); }?

148

Why 0? How about opt_p->value_or(21) != 21?

521

Extreme nit for consistency with all comments above.

523

Why not hard-code this in the isValueOrCondition matcher?

524

The clang namespace can be removed. Same comment for other instances in the patch.

526

Why not pass transferOptionalValueOrCall as argument instead of wrapping it in a lambda? The function can take the "ValueOrCall" node from the MatchResult.

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

1722

Is the return important? I think having void return type would be simpler. Same comment for the cases below.

[xazax.hun]

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

271

There is an implication in the reverse direction as well. In case we know the optional is empty, we can prune one of the branches from the analysis. Is it possible to implement that with the current status of the framework?

[ymandel]

Addressed comments.

[ymandel]

remove stray comments

[ymandel]

adjust logical formula

[ymandel]

Thanks for the detailed review!

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

119

The negation is a simpler predicate, but you're right that it's too specific. I've rewritten the code to drop the constraint and handle the more general opt.value_or("").empty(). The new code also encodes a more precise relationship in the logic, per Gabor's comments below about the implication in the other direction. It also now directly attaches the formula to the value, rather than dropping an implication in the flow conditions.

Overall, I think the new approach is an improvement, but please let me know if you disagree.

148

This is addressed in the comment, but do you think we should add a FIXME to support some amount of expression comparision? Integers, floats, bools and variables would be an easy place to start, for example. But, we'd need to drop into regular code -- the matchers can't express that kind of constraint.

271

Yes, good point! Please see my response to Stanislav above. I think the new version handles this by modeling the value_or directly, rather than dropping in an implication.

523

Safety/hygiene. It's easier to see that the ID to which the node is bound is the same that's being used in getNodeAs. An alternative which I often use is to use a (static) global constant, so I've changed to that.

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

1722

Totally. Thanks for pointing that out.

[xazax.hun]

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

142

Yeah, I think Clang is in a very sad state in this regard. We have a lot of half done facilities littered all over the codebase, including:
https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Analysis/CloneDetection.h
https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/IdenticalExprChecker.cpp#L306
https://github.com/llvm/llvm-project/blob/main/clang-tools-extra/clang-tidy/misc/RedundantExpressionCheck.cpp#L60

147

I wonder if we want to add "" to support opt.value_or("") != "". Not sure how frequent would this be over the empty call.

273

Is this the right way to initialize ComparisonValue?

Considering the expression: opt.value_or(nullptr) != nullptr

• When has_value == false, opt.value_or(nullptr) will return nullptr, so != evaluates to false. This case seems to check out.
• However, when has_value == true, opt might still hold an nullptr and != could still evaluate to false.

[ymandel]

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

273

Thanks for digging into this. I think it's correct, but helpful to step through:

Its correctness depends on MakeValue, so I'll focus on that in particular. For the nullptr case, we'll get:

HasValueVal && ContentsNotEqX

So, when has_value == true, this basically reduces to ContentsNotEqX. Since that's an atom, the result is indeterminate, which I believe is the desired outcome.

WDYT? Also, even if I've convinced you, please let me know how i can improve the comments. For that matter, would MakeValue be better with a more specific name, like "MakePredicate" or somesuch?

[xazax.hun]

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

273

I think what confuses me is that we do something different for the 3 cases. You convinced me that HasValueVal && ContentsNotEqX is correct. But we only do this for one branch out of the 3. What is the reason for that?

[xazax.hun]

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

310

Typo: values.

[xazax.hun]

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

273

Oh, never mind. Yeah, I think changing MakeValue to MakePredicate would make this a bit clearer. After a second read now I understand better what is going on.

[ymandel]

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

273

Just to be clear: the three cases you mean are lines 273-283, or something else?

[ymandel]

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

273

and never mind my question, then (I rpelied before I saw your updated). I'll change the name and add comments.

[xazax.hun]

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

282

I am still wondering a bit about this case.

We generate: HasValueVal and ContentsNotEqX and CurrentValue.'
I wonder if we want: HasValueVal and (ContentsNotEqX <=> CurrentValue) instead? Or even HasValueVal and CurrentValue?

[xazax.hun]

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

298

Not related to this PR, but I think in the future we will want to associate names to the values to make debugging easier (or maybe to generate really nice error messages).

[ymandel]

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

282

I don't think that the iff version is right, but HasValueVal and CurrentValue could be. My concern is that we're not guaranteed that CurrentValue is populated. And, even if we were, it doesn't feel quite right. Assuming its a high fidelity model, we get (logically): HasValue(opt) and Ne(ValueOr(opt,X),X). Then, when negated (say, on an else branch) we get not(HasValue(opt)) or not(Ne(ValueOr(opt,X),X)) which is equivalent to not(HasValue(opt)) or Eq(ValueOr(opt,X),X). While true, it seems redundant, since the first clause should be derivable from the second (assuming an interpretatable semantics to the ValueOr predicate).

Regardless, it might be better to step back and figure out how this should be done systematically. I'll try to come back with a proposal on that.

[sgatev]

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

273

Can you elaborate on the three cases on lines 273-283? Why not simply do

auto &ComparisonExprLoc = Env.createStorageLocation(*ComparisonExpr);
Env.setStorageLocation(ComparisonExpr, ComparisonExprLoc);
Env.setValue(ComparisonExprLoc, ComparisonValue);

[ymandel]

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

273

Can you elaborate on the three cases on lines 273-283? Why not simply do

auto &ComparisonExprLoc = Env.createStorageLocation(*ComparisonExpr);
Env.setStorageLocation(ComparisonExpr, ComparisonExprLoc);
Env.setValue(ComparisonExprLoc, ComparisonValue);

for the second case: I think we should drop it -- I don't see a reason to maintain the previous value (if there is any). It might be a good idea for compositionality, but we're not doing that anywhere else, so it doesn't make sense here.

for the first and third case: I assumed that if the expression already has a location, we'd want to reuse it. But, based on your question, I take it that's incorrect?

282

Regardless, it might be better to step back and figure out how this should be done systematically. I'll try to come back with a proposal on that.

Here's what I have: in general, we're aiming for all models to be a sound (over) approximation of reality. That is what we're doing here as well. Yet, that poses a problem for the interpretation of the boolean not operator. If its operand is an overapproximation, then I believe the naive approach gives you an under approximation. That's the problem we're hitting when reasoning about the negation.

I'm not sure how to handle this. Stanislav -- have we dealt with this issue before?

That said, if we go back to the previous approach, of adding the information to the path condition, I think we avoid this problem, since the path conditions don't get negated. To Gabor's earlier point:

There is an implication in the reverse direction as well. In case we know the optional is empty, we can prune one of the branches from the analysis. Is it possible to implement that with the current status of the framework?

I think is covered by the condition we're adding. Namely:

ExprValue => has_value

where ExprValue is the truth value of the boolean expression.

So, the implication in the reverse direction is:

!has_value => !ExprValue

that is, if we know the optional doesn't hold a value, then we know that opt.value_or(X) = X

But, that implication is the contrapositive of our own, so I think it's already implicitly covered by adding the single implication. Does that sound right?

[sgatev]

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

273

Dropping the second case makes sense to me.

For the rest, createStorageLocation returns a stable storage location so the snippet above should be sufficient. However, setStorageLocation will fail if we try calling it again with the same expression, even if it's called with the same storage location. What do you think about making setStorageLocation not fail if it's called with the same arguments?

282

I'm not following where Env.makeAnd(*CurrentValue, ComparisonValue) comes from so I'd question whether it's sound or not. I would have expected to see something like ExprValue => has_value (which I believe was the case in the first iteration) and I see no issues with the contrapositive. If you have x => y and not y in the flow condition, you'll be able to infer that not x is true (assuming no other statements for x). How we use this to prune branches from the analysis is a question of its own.

[ymandel]

address comments

[ymandel]

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

142

Right. I've added a FIXME. I think an elegant solution in this case would be a relational matcher for built-in types.

147

Makes sense -- done.

273

for the code here -- I don't think that there's a case where there's not value associated with a comparison, yet there is a loc, so I think that snippet is fine.

for the general case, I think that setStorageLocation should be be no stricter than createStorageLocation. it seems strange for the set operation to fail when the create does not (since "set" is more commonly a repeatable operation). Otherwise, no strong opinion as long as we document the behavior.

282

I think the new version resolves this?

298

Good idea. I've noted that (to myself) as a todo to add a FIXME or somesuch.

[xazax.hun]

Wow. This did take some iterations and I feel like I just added to the confusion at some point :D But the latest iteration looks much simpler and I'm confident it is right this time. Thanks!

[ymandel]

In D122231#3414109, @xazax.hun wrote:

Wow. This did take some iterations and I feel like I just added to the confusion at some point :D But the latest iteration looks much simpler and I'm confident it is right this time. Thanks!

Not at all -- I think you raised some really good questions! Ultimately, my move from implication in the flow condition to tying it directly to the value was the wrong turn, and your questions effectively highlighted the issues. :)

[sgatev]

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

275

Why do this conditionally? I think we should set a value regardless of whether another model has already done so.

282

Yes, modelling these using implications looks good to me!

525

Call this isValueOrNotEqX for consistency?

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

1720

I suggest making opt a parameter of target in all tests because in the current setup a more advanced analysis would identify one of the code paths we exercise as dead.

1782

Let's move this to a string header and remove the definition in the test above.

1811–1812

These can be combined in a $ns::$optional<int> *opt parameter.

[ymandel]

address comments.

[ymandel]

delete line

[ymandel]

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

275

Why? I figured we're agnostic to the underlying value, and only care about relating it via the implication. We're setting it only so we have something to anchor that implication on. If we always set it, then we're erasing the information from another model.

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

1222

Note: this came from sync'ing to HEAD and picking up my other patch.

1811–1812

Unfortunately, that crashes (which must be why I did this to begin with). But, I did reduce to only one var and one param.

[sgatev]

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

275

Nevermind. I probably didn't follow carefully around all the comment blocks and thought that addToFlowCondition also happens conditionally. The current approach looks good to me.

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

 }
 
 auto isStdSwapCall() {
   return callExpr(callee(functionDecl(hasName("std::swap"))),
                   argumentCountIs(2), hasArgument(0, hasOptionalType()),
                   hasArgument(1, hasOptionalType()));
 }
 
+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 isValueOrCondition() {
+  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)))));
+}
+
 /// 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));
 }
 
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);
   }
 }
 
+/// `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,
+                         BoolValue &(*ModelPred)(Environment &Env,
+                                                 BoolValue &ExprVal,
+                                                 BoolValue &HasValueVal)) {
+  auto &Env = State.Env;
+
+  const auto *ObjectArgumentExpr =
+      Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID)
+          ->getImplicitObjectArgument();
+
+  auto *OptionalVal = cast_or_null<StructValue>(
+      Env.getValue(*ObjectArgumentExpr, SkipPast::ReferenceThenPointer));
+  if (OptionalVal == nullptr)
+    return;
+  auto *HasValueVal = getHasValue(OptionalVal);
+  assert(HasValueVal != nullptr);
+
+  auto *ExprValue = clang::cast_or_null<BoolValue>(
+      State.Env.getValue(*ValueOrPredExpr, SkipPast::None));
+  if (ExprValue == nullptr) {
+    auto &ExprLoc = State.Env.createStorageLocation(*ValueOrPredExpr);
+    ExprValue = &State.Env.makeAtomicBoolValue();
+    State.Env.setValue(ExprLoc, *ExprValue);
+    State.Env.setStorageLocation(*ValueOrPredExpr, ExprLoc);
+  }
+
+  Env.addToFlowCondition(ModelPred(Env, *ExprValue, *HasValueVal));
+}
+
+void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
+                                    const MatchFinder::MatchResult &Result,
+                                    LatticeTransferState &State) {
+  return transferValueOrImpl(ComparisonExpr, Result, State,
+                             [](Environment &Env, BoolValue &ExprVal,
+                                BoolValue &HasValueVal) -> BoolValue & {
+                               // 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 Env.makeImplication(Env.makeNot(ExprVal),
+                                                          HasValueVal);
+                             });
+}
+
+void transferValueOrNotEqX(const Expr *ComparisonExpr,
+                           const MatchFinder::MatchResult &Result,
+                           LatticeTransferState &State) {
+  transferValueOrImpl(ComparisonExpr, Result, State,
+                      [](Environment &Env, BoolValue &ExprVal,
+                         BoolValue &HasValueVal) -> BoolValue & {
+                        // We know that if `(opt.value_or(X) != X)` then
+                        // `opt.hasValue()`, even without knowing further
+                        // details about the contents of `opt`.
+                        return Env.makeImplication(ExprVal, HasValueVal);
+                      });
+}
+
 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));
   }
 }
return MatchSwitchBuilder<LatticeTransferState>()
 
       // optional::swap
       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("swap"),
                                  transferSwapCall)
 
       // std::swap
       .CaseOf<CallExpr>(isStdSwapCall(), transferStdSwapCall)
 
+      // opt.value_or("").empty()
+      .CaseOf<Expr>(isValueOrStringEmptyCall(), transferValueOrStringEmptyCall)
+
+      // opt.value_or(X) != X
+      .CaseOf<Expr>(isValueOrCondition(), transferValueOrNotEqX)
+
       .Build();
 }
 
 } // namespace
 
 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx)
     : DataflowAnalysis<UncheckedOptionalAccessModel, SourceLocationsLattice>(
           Ctx),

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

Headers.emplace_back("unchecked_optional_access_test.h", R"(
       template <typename T>
       T Make();
     )");
     const tooling::FileContentMappings FileContents(Headers.begin(),
                                                     Headers.end());
     llvm::Error Error = checkDataflow<UncheckedOptionalAccessModel>(
         SourceCode, FuncMatcher,
         [](ASTContext &Ctx, Environment &) {
           return UncheckedOptionalAccessModel(Ctx);
         },
         [&MatchesLatticeChecks](
             llvm::ArrayRef<std::pair<
                 std::string, DataflowAnalysisState<SourceLocationsLattice>>>
                 CheckToLatticeMap,
             ASTContext &Ctx) {
           // FIXME: Consider using a matcher instead of translating
           // `CheckToLatticeMap` to `CheckToStringifiedLatticeMap`.
void target() {
       opt.value_or(0);
       (void)0;
       /*[[check]]*/
     }
   )",
                          UnorderedElementsAre(Pair("check", "safe")));
 }
 
+TEST_P(UncheckedOptionalAccessTest, ValueOrComparison) {
+  // Pointers.
+  ExpectLatticeChecksFor(
+      R"code(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int*> opt;
+      if (opt.value_or(nullptr) != nullptr) {
+        opt.value();
+        /*[[check-ptrs-1]]*/
+      } else {
+        opt.value();
+        /*[[check-ptrs-2]]*/
+      }
+    }
+  )code",
+      UnorderedElementsAre(Pair("check-ptrs-1", "safe"),
+                           Pair("check-ptrs-2", "unsafe: input.cc:10:9")));
+
+  // Integers.
+  ExpectLatticeChecksFor(
+      R"code(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt;
+      if (opt.value_or(0) != 0) {
+        opt.value();
+        /*[[check-ints-1]]*/
+      } else {
+        opt.value();
+        /*[[check-ints-2]]*/
+      }
+    }
+  )code",
+      UnorderedElementsAre(Pair("check-ints-1", "safe"),
+                           Pair("check-ints-2", "unsafe: input.cc:10:9")));
+
+  // Strings.
+  ExpectLatticeChecksFor(
+      R"code(
+    #include "unchecked_optional_access_test.h"
+
+    namespace std {
+      struct string {
+        bool empty();
+      };
+    }
+
+    void target() {
+      $ns::$optional<std::string> opt;
+      if (!opt.value_or("").empty()) {
+        opt.value();
+        /*[[check-strings-1]]*/
+      } else {
+        opt.value();
+        /*[[check-strings-2]]*/
+      }
+    }
+  )code",
+      UnorderedElementsAre(Pair("check-strings-1", "safe"),
+                           Pair("check-strings-2", "unsafe: input.cc:16:9")));
+
+  ExpectLatticeChecksFor(
+      R"code(
+    #include "unchecked_optional_access_test.h"
+
+    namespace std {
+      struct string {
+        string(const char*);
+        ~string();
+        bool empty();
+      };
+      bool operator!=(const string &LHS, const char *RHS);
+    }
+
+    void target() {
+      $ns::$optional<std::string> opt;
+      if (opt.value_or("") != "") {
+        opt.value();
+        /*[[check-strings-neq-1]]*/
+      } else {
+        opt.value();
+        /*[[check-strings-neq-2]]*/
+      }
+    }
+  )code",
+      UnorderedElementsAre(
+          Pair("check-strings-neq-1", "safe"),
+          Pair("check-strings-neq-2", "unsafe: input.cc:19:9")));
+
+  // Pointer-to-optional.
+  ExpectLatticeChecksFor(
+      R"code(
+    #include "unchecked_optional_access_test.h"
+
+    void target() {
+      $ns::$optional<int> opt;
+      auto *opt_p = &opt;
+      if (opt_p->value_or(0) != 0) {
+        opt_p->value();
+        /*[[check-pto-1]]*/
+      } else {
+        opt_p->value();
+        /*[[check-pto-2]]*/
+      }
+    }
+  )code",
+      UnorderedElementsAre(Pair("check-pto-1", "safe"),
+                           Pair("check-pto-2", "unsafe: input.cc:11:9")));
+}
+
 TEST_P(UncheckedOptionalAccessTest, Emplace) {
   ExpectLatticeChecksFor(R"(
     #include "unchecked_optional_access_test.h"
 
     void target() {
       $ns::$optional<int> opt;
       opt.emplace(0);
       opt.value();
)",
       UnorderedElementsAre(Pair("check-3", "safe"),
                            Pair("check-4", "unsafe: input.cc:13:7")));
 }
 
 // FIXME: Add support for:
 // - constructors (copy, move)
 // - assignment operators (default, copy, move)
 // - invalidation (passing optional by non-const reference/pointer)
-// - `value_or(nullptr) != nullptr`, `value_or(0) != 0`, `value_or("").empty()`
 // - nested `optional` values