[clang][dataflow] Track `optional` contents in `optional` model.

[ymandel]

Summary

This patch adds partial support for tracking (i.e. modeling) the contents of an
optional value. Specifically, it supports tracking the value after it is
accessed. We leave tracking constructed/assigned contents to a future patch.

[ymandel]

remove stray newline

[xazax.hun]

Overall looks good to me. I am curious what will the strategy be to properly support construction. Do you plan to introduce a customization point to Env.createValue to give checks/models a way to set properties up? Or do you have something else in mind?

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

229

I recall some problems with convergence due to creating fresh locations lazily in multiple branches. I wonder if doubling down before finding a proper solution could make it harder to fix this in the near future. If this is just a temporary solution until construction is better supported, it might be fine.

301

I wonder how well this strategy works in practice. If we have many unwrap calls to the same optional, we might end up emitting lots of diagnostics. An alternative approach is to assume that the optional has a value after the first unwrap. This would ensure that we only report a particular problem once and can reduce the noise.

[ymandel]

Fixed the FIXME

[ymandel]

In D124932#3492495, @xazax.hun wrote:

Overall looks good to me. I am curious what will the strategy be to properly support construction. Do you plan to introduce a customization point to Env.createValue to give checks/models a way to set properties up? Or do you have something else in mind?

If we want to go the eager route, than I think that's the "right" solution. Anything else is brittle, since it is easy to miss a construction point. However, I'm more inclined to move the whole framework to a lazy initialization process, if we can devise one.

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

229

Excellent question. Yes, you're right about the convergence issue this falls into the same category. That said, we intentionally reuse the same location in all branches, which mitigates that issue in this case -- we are at least assured that the two branches will have the contents value at the same location. In fact, the FIXME I added is wrong (and I've adjusted it accordingly). The property will be shared by all blocks that share the same value representing the Optional (which for the most part is done eagerly).

To your larger point, about the advisability of this approach, even for the short term:

1. I'm pushing on this largely because I have the data to support that it works in practice. We've done multiple surveys of significant size (~1000 files, 10k optional accesses) and found it does very well. So, this is not much of an issue in practice, in large part because the contents of optionals don't tend to further influence the outcome of the check (e.g. in the case of nested optionals).
2. I thought of redoing this in an eager fashion, but realized that ultimately we want to move everything to a lazy model, so it seemed less than ideal to start trying to be eager here.

301

I see your point, and agree that there does seem room for significantly reducing warnings, even if all are correct. But, in practice, we haven't gotten complaints (which is a little surprising, actually). I wonder if it would be good to pair the report with the surrounding compound statement, and limit to one per compound statement. I fear that shutting it off entirely after the first issue might be _too_ quiet. Either way, this is definitely something that we'll be actively tweaking.

[xazax.hun]

Thanks for the clarifications!

[sgatev]

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

180–181

Why is this necessary? Do we really need to create a new value on each getHasValue call? Can we centralize initialization to avoid this? I'm worried that "has_value" and "value" initialization isn't coordinated.

229

Perhaps call this maybeInitializeOptionalValueMember?

229

Let's pass the type instead of Expr, if that's the only thing we need.

232–234

It's unclear to me why we "need" a StorageLocation. Representing the value as a ReferenceValue seems good to me, but there are other options. What issues are we running into if we remove the indirection?

241–246

So we don't lose the ReferenceValue, but we do lose its pointee? Is that the behavior we want when merging?

291

Shouldn't we use getHasValue here?

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

2188–2260

Do we really need tests for all members that check/access/reset the content? These are already covered in tests above.

2280

2287

Do we really need this one or is it already covered by one of the tests in this file?

[ymandel]

I'm having trouble with arcanist -- arc diff is crashing, but wanted to respond in the meantime to your questions. I hope I'll be able to actually upload the new diff soon...

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

180–181

Why is this necessary? Do we really need to create a new value on each getHasValue call? Can we centralize initialization to avoid this? I'm worried that "has_value" and "value" initialization isn't coordinated.

We don't create a new one on each call, only when none is already populated. As for centralizing -- we could, but I'd like to move to lazy initialization anyhow, so it seemed less than ideal to put effort into centralizing at this point.

232–234

It's unclear to me why we "need" a StorageLocation. Representing the value as a ReferenceValue seems good to me, but there are other options. What issues are we running into if we remove the indirection?

We can't address it. Compare with a normal field, where the corresponding AggregateStorageLocation has a child that maps to a storage location for the field. We don't support properties on AggregateStorageLocation, so the location has to exist somewhere.

What other options do you see?

241–246

So we don't lose the ReferenceValue, but we do lose its pointee? Is that the behavior we want when merging?

Correct. No, that's not the behavior we want, hence the FIXME that follows. :) But, it at least accounts for the other two situations, so its a win overall.

291

Shouldn't we use getHasValue here?

Not quite:

1. its a bit a redundant since we already need to check whether the value is a StructValue, line 274-5. I tried to keep it to where its use would not cause unnecessary additional checks.
2. We don't want to create a new "has_value" here, given that the access is illegal in that case. We want the condition to fail in that case (line 282) and result in recording an error.

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

2188–2260

Great point. I rethought the tests in general -- I'd mostly been copying them over, without carefully rethinking them. I've reduced the number of tests and added comments explaining their purposes. Essentially, we need to test that the synthetic value can be used like a normal field.

2280

No longer relevant.

2287

Covered.

[ymandel]

address reviewer comments and fix bug in how the nested value as _re_created -- now uses the loc's type rather than the expression's type (which doesn't always match exactly).

[ymandel]

remove stray FIXME from previous diff

[ymandel]

sgatev@ -- gentle ping.

[ymandel]

rebase and merge

[ymandel]

add missing blank line to test

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

 /// 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 `OptionalVal`. Returns null if `OptionalVal` is null.
-BoolValue *getHasValue(Value *OptionalVal) {
-  if (OptionalVal) {
-    return cast<BoolValue>(OptionalVal->getProperty("has_value"));
+BoolValue *getHasValue(Environment &Env, Value *OptionalVal) {
+  if (OptionalVal != nullptr) {
+    auto *HasValueVal =
+        cast_or_null<BoolValue>(OptionalVal->getProperty("has_value"));
+    if (HasValueVal == nullptr) {
+      HasValueVal = &Env.makeAtomicBoolValue();
+      OptionalVal->setProperty("has_value", *HasValueVal);
+    }
+    return HasValueVal;
   }
   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;
return 1 + countOptionalWrappers(
                  ASTCtx,
                  cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
                      ->getTemplateArgs()
                      .get(0)
                      .getAsType()
                      .getDesugaredType(ASTCtx));
 }
 
+/// Tries to initialize the `optional`'s value (that is, contents), and return
+/// its location. Returns nullptr if the value can't be represented.
+StorageLocation *maybeInitializeOptionalValueMember(QualType Q,
+                                                    Value &OptionalVal,
+                                                    Environment &Env) {
+  // The "value" property represents a synthetic field. As such, it needs
+  // `StorageLocation`, like normal fields (and other variables). So, we model
+  // it with a `ReferenceValue`, since that includes a storage location.  Once
+  // the property is set, it will be shared by all environments that access the
+  // `Value` representing the optional (here, `OptionalVal`).
+  if (auto *ValueProp = OptionalVal.getProperty("value")) {
+    auto *ValueRef = clang::cast<ReferenceValue>(ValueProp);
+    auto &ValueLoc = ValueRef->getPointeeLoc();
+    if (Env.getValue(ValueLoc) == nullptr) {
+      // The property was previously set, but the value has been lost. This can
+      // happen, for example, because of an environment merge (where the two
+      // environments mapped the property to different values, which resulted in
+      // them both being discarded), or when two blocks in the CFG, with neither
+      // a dominator of the other, visit the same optional value, or even when a
+      // block is revisited during testing to collect per-statement state.
+      // FIXME: This situation means that the optional contents are not shared
+      // between branches and the like. Practically, this lack of sharing
+      // reduces the precision of the model when the contents are relevant to
+      // the check, like another optional or a boolean that influences control
+      // flow.
+      auto *ValueVal = Env.createValue(ValueLoc.getType());
+      if (ValueVal == nullptr)
+        return nullptr;
+      Env.setValue(ValueLoc, *ValueVal);
+    }
+    return &ValueLoc;
+  }
+
+  auto Ty = stripReference(Q);
+  auto *ValueVal = Env.createValue(Ty);
+  if (ValueVal == nullptr)
+    return nullptr;
+  auto &ValueLoc = Env.createStorageLocation(Ty);
+  Env.setValue(ValueLoc, *ValueVal);
+  auto ValueRef = std::make_unique<ReferenceValue>(ValueLoc);
+  OptionalVal.setProperty("value", Env.takeOwnership(std::move(ValueRef)));
+  return &ValueLoc;
+}
+
 void initializeOptionalReference(const Expr *OptionalExpr,
                                  const MatchFinder::MatchResult &,
                                  LatticeTransferState &State) {
   if (auto *OptionalVal =
           State.Env.getValue(*OptionalExpr, SkipPast::Reference)) {
     if (OptionalVal->getProperty("has_value") == nullptr) {
       OptionalVal->setProperty("has_value", State.Env.makeAtomicBoolValue());
     }
   }
 }
 
 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
                         LatticeTransferState &State) {
   if (auto *OptionalVal =
           State.Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer)) {
-    auto *HasValueVal = getHasValue(OptionalVal);
-    assert(HasValueVal != nullptr);
+    if (State.Env.getStorageLocation(*UnwrapExpr, SkipPast::None) == nullptr)
+      if (auto *Loc = maybeInitializeOptionalValueMember(
+              UnwrapExpr->getType(), *OptionalVal, State.Env))
+        State.Env.setStorageLocation(*UnwrapExpr, *Loc);
 
+    auto *Prop = OptionalVal->getProperty("has_value");
+    if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
       if (State.Env.flowConditionImplies(*HasValueVal))
         return;
     }
+  }
 
   // Record that this unwrap is *not* provably safe.
   // FIXME: include either the name of the optional (if applicable) or a source
   // range of the access for easier interpretation of the result.
   State.Lattice.getSourceLocations().insert(ObjectExpr->getBeginLoc());
 }
 
 void transferMakeOptionalCall(const CallExpr *E,
                               const MatchFinder::MatchResult &,
                               LatticeTransferState &State) {
   auto &Loc = State.Env.createStorageLocation(*E);
   State.Env.setStorageLocation(*E, Loc);
   State.Env.setValue(
       Loc, createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
 }
 
 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
                                   const MatchFinder::MatchResult &,
                                   LatticeTransferState &State) {
-  if (auto *OptionalVal = cast_or_null<StructValue>(
-          State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
+  if (auto *HasValueVal = getHasValue(
+          State.Env, State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
                                         SkipPast::ReferenceThenPointer))) {
-    auto *HasValueVal = getHasValue(OptionalVal);
-    assert(HasValueVal != nullptr);
-
     auto &CallExprLoc = State.Env.createStorageLocation(*CallExpr);
     State.Env.setValue(CallExprLoc, *HasValueVal);
     State.Env.setStorageLocation(*CallExpr, CallExprLoc);
   }
 }
 
 /// `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)
+  auto *HasValueVal = getHasValue(
+      State.Env,
+      State.Env.getValue(*ObjectArgumentExpr, SkipPast::ReferenceThenPointer));
+  if (HasValueVal == nullptr)
     return;
-  auto *HasValueVal = getHasValue(OptionalVal);
-  assert(HasValueVal != nullptr);
 
   auto *ExprValue = 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);
getValueOrConversionHasValue(const FunctionDecl &F, const Expr &E,
 
   // Check if this is a constructor/assignment call for `optional<T>` with
   // argument of type `U` such that `T` is constructible from `U`.
   if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
     return State.Env.getBoolLiteralValue(true);
 
   // This is a constructor/assignment call for `optional<T>` with argument of
   // type `optional<U>` such that `T` is constructible from `U`.
-  if (BoolValue *Val = getHasValue(State.Env.getValue(E, SkipPast::Reference)))
-    return *Val;
+  if (auto *HasValueVal =
+          getHasValue(State.Env, State.Env.getValue(E, SkipPast::Reference)))
+    return *HasValueVal;
   return State.Env.makeAtomicBoolValue();
 }
 
 void transferValueOrConversionConstructor(
     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
     LatticeTransferState &State) {
   assert(E->getNumArgs() > 0);
 

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

TEST_P(UncheckedOptionalAccessTest, UniquePtrToStructWithOptionalField) {
   )",
       UnorderedElementsAre(Pair("check-1", "safe"), Pair("check-2", "safe")));
 }
 
 TEST_P(UncheckedOptionalAccessTest, CallReturningOptional) {
   ExpectLatticeChecksFor(
       R"(
     #include "unchecked_optional_access_test.h"
-
     $ns::$optional<int> MakeOpt();
 
     void target() {
       $ns::$optional<int> opt = 0;
       opt = MakeOpt();
       opt.value();
       /*[[check-1]]*/
     }
   )",
       UnorderedElementsAre(Pair("check-1", "unsafe: input.cc:9:7")));
-
   ExpectLatticeChecksFor(
       R"(
     #include "unchecked_optional_access_test.h"
 
     const $ns::$optional<int>& MakeOpt();
 
     void target() {
       $ns::$optional<int> opt = 0;
       opt = MakeOpt();
       opt.value();
       /*[[check-2]]*/
     }
   )",
       UnorderedElementsAre(Pair("check-2", "unsafe: input.cc:9:7")));
 
   ExpectLatticeChecksFor(
       R"(
     #include "unchecked_optional_access_test.h"
 
     using IntOpt = $ns::$optional<int>;
     IntOpt MakeOpt();
 
     void target() {
       IntOpt opt = 0;
       opt = MakeOpt();
       opt.value();
       /*[[check-3]]*/
     }
   )",
       UnorderedElementsAre(Pair("check-3", "unsafe: input.cc:10:7")));
 
   ExpectLatticeChecksFor(
       R"(
     #include "unchecked_optional_access_test.h"
 
     using IntOpt = $ns::$optional<int>;
     const IntOpt& MakeOpt();
 
     void target() {
       IntOpt opt = 0;
       opt = MakeOpt();
       opt.value();
       /*[[check-4]]*/
     }
   )",
       UnorderedElementsAre(Pair("check-4", "unsafe: input.cc:10:7")));
 }
 
 // Verifies that the model sees through aliases.
 TEST_P(UncheckedOptionalAccessTest, WithAlias) {
   ExpectLatticeChecksFor(
       R"(
     #include "unchecked_optional_access_test.h"
 
     template <typename T>
     using MyOptional = $ns::$optional<T>;
 
     void target(MyOptional<int> opt) {
       opt.value();
       /*[[check]]*/
     }
   )",
       UnorderedElementsAre(Pair("check", "unsafe: input.cc:8:7")));
 }
 
+TEST_P(UncheckedOptionalAccessTest, OptionalValueOptional) {
+  // Basic test that nested values are populated.  We nest an optional because
+  // its easy to use in a test, but the type of the nested value shouldn't
+  // matter.
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    using Foo = $ns::$optional<std::string>;
+
+    void target($ns::$optional<Foo> foo) {
+      if (foo && *foo) {
+        foo->value();
+        /*[[access]]*/
+      }
+    }
+  )",
+      UnorderedElementsAre(Pair("access", "safe")));
+
+  // Mutation is supported for nested values.
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    using Foo = $ns::$optional<std::string>;
+
+    void target($ns::$optional<Foo> foo) {
+      if (foo && *foo) {
+        foo->reset();
+        foo->value();
+        /*[[reset]]*/
+      }
+    }
+  )",
+      UnorderedElementsAre(Pair("reset", "unsafe: input.cc:9:9")));
+}
+
+// Tests that structs can be nested. We use an optional field because its easy
+// to use in a test, but the type of the field shouldn't matter.
+TEST_P(UncheckedOptionalAccessTest, OptionalValueStruct) {
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct Foo {
+      $ns::$optional<std::string> opt;
+    };
+
+    void target($ns::$optional<Foo> foo) {
+      if (foo && foo->opt) {
+        foo->opt.value();
+        /*[[access]]*/
+      }
+    }
+  )",
+      UnorderedElementsAre(Pair("access", "safe")));
+}
+
+TEST_P(UncheckedOptionalAccessTest, OptionalValueInitialization) {
+  // FIXME: Fix when to initialize `value`. All unwrapping should be safe in
+  // this example, but `value` initialization is done multiple times during the
+  // fixpoint iterations and joining the environment won't correctly merge them.
+  ExpectLatticeChecksFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    using Foo = $ns::$optional<std::string>;
+
+    void target($ns::$optional<Foo> foo, bool b) {
+      if (!foo.has_value()) return;
+      if (b) {
+        if (!foo->has_value()) return;
+        // We have created `foo.value()`.
+        foo->value();
+      } else {
+        if (!foo->has_value()) return;
+        // We have created `foo.value()` again, in a different environment.
+        foo->value();
+      }
+      // Now we merge the two values. UncheckedOptionalAccessModel::merge() will
+      // throw away the "value" property.
+      foo->value();
+      /*[[merge]]*/
+    }
+  )",
+      UnorderedElementsAre(Pair("merge", "unsafe: input.cc:19:7")));
+}
+
 // FIXME: Add support for:
 // - constructors (copy, move)
 // - assignment operators (default, copy, move)
 // - invalidation (passing optional by non-const reference/pointer)
-// - nested `optional` values