[clang][dataflow] Relax validity assumptions in `UncheckedOptionalAccessModel`.

[ymandel]

Summary

Currently, the interpretation of swap calls in the optional model assumes the
optional arguments are modeled (and therefore have valid storage locations and
values). This assumption is incorrect, for example, in the case of unmodeled
optional fields (which can be missing either value or location). This patch
relaxes these assumptions, to return rather than assert when either argument is
not modeled.

[sgatev]

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

524–540

What do you think about passing const StorageLocation* instead of const Expr&? This way we don't need to pass E1Skip.

534

Any reason to not set a fresh value for Loc1 in this case (similarly a fresh value for Loc2 below)?

[ymandel]

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

524–540

Sure, but means we'll be pushing the calls to getStorageLocation to callers. I'm fine with that, since it means a less janky API, but just want to call that out.

534

The new value for Loc1/Loc2 won't be connected to anything, so it won't bring any benefit to the modeling -- it will only make the code simpler.

[ymandel]

Gentle ping.

[xazax.hun]

This change looks good to me. I wonder, however, whether the behavior should be parameterized in the future. E.g., whether the user of the analysis should be able to make a decision whether the analysis should be pessimistic or optimistic about unmodeled values.

[ymandel]

In D142710#4094934, @xazax.hun wrote:

This change looks good to me. I wonder, however, whether the behavior should be parameterized in the future. E.g., whether the user of the analysis should be able to make a decision whether the analysis should be pessimistic or optimistic about unmodeled values.

Interesting idea. I think this goes along with other places where we are unsound. Here, we err on the side of soundness. but, in general, we should have a configuration mechanism for this. FWIW, the only reason we have uninitialized values at this point is recursive types. We also limit the depth of structs, but that should be removed given my recent patch to only model relevant fields. I have an idea for lazy initialization of values that I think could solve the recursion issue. Together, we could remove this concept of unmodeled values altogether from the framework.

[xazax.hun]

In D142710#4096325, @ymandel wrote:

In D142710#4094934, @xazax.hun wrote:

This change looks good to me. I wonder, however, whether the behavior should be parameterized in the future. E.g., whether the user of the analysis should be able to make a decision whether the analysis should be pessimistic or optimistic about unmodeled values.

Interesting idea. I think this goes along with other places where we are unsound. Here, we err on the side of soundness. but, in general, we should have a configuration mechanism for this. FWIW, the only reason we have uninitialized values at this point is recursive types. We also limit the depth of structs, but that should be removed given my recent patch to only model relevant fields. I have an idea for lazy initialization of values that I think could solve the recursion issue. Together, we could remove this concept of unmodeled values altogether from the framework.

Oh, sounds great! I do think lazy initialization will be really valuable to reduce the number of unmodeled values, but not entirely sure if we can completely eliminate them. In case we end up creating new locations (different from the earlier ones) in every iteration of the loop it might be harder to reach a fixed point.

[ymandel]

In D142710#4097032, @xazax.hun wrote:

In D142710#4096325, @ymandel wrote:

In D142710#4094934, @xazax.hun wrote:

This change looks good to me. I wonder, however, whether the behavior should be parameterized in the future. E.g., whether the user of the analysis should be able to make a decision whether the analysis should be pessimistic or optimistic about unmodeled values.

Interesting idea. I think this goes along with other places where we are unsound. Here, we err on the side of soundness. but, in general, we should have a configuration mechanism for this. FWIW, the only reason we have uninitialized values at this point is recursive types. We also limit the depth of structs, but that should be removed given my recent patch to only model relevant fields. I have an idea for lazy initialization of values that I think could solve the recursion issue. Together, we could remove this concept of unmodeled values altogether from the framework.

Oh, sounds great! I do think lazy initialization will be really valuable to reduce the number of unmodeled values, but not entirely sure if we can completely eliminate them. In case we end up creating new locations (different from the earlier ones) in every iteration of the loop it might be harder to reach a fixed point.

True, and in some sense TopBoolValue is already that. If we extended Top to other value domains (like struct) the code would end up looking very similar, just spelled "top" instead of "nullptr". I'd prefer Top over nullptr, but it admittedly wouldn't change things in a fundamental way.

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

 }
 
 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
                                const MatchFinder::MatchResult &,
                                LatticeTransferState &State) {
   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
 }
 
-void transferSwap(const StorageLocation &OptionalLoc1,
-                  const StorageLocation &OptionalLoc2,
-                  LatticeTransferState &State) {
-  auto *OptionalVal1 = State.Env.getValue(OptionalLoc1);
-  assert(OptionalVal1 != nullptr);
+void transferSwap(const Expr &E1, SkipPast E1Skip, const Expr &E2,
+                  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.
+  auto *Loc1 = Env.getStorageLocation(E1, E1Skip);
+  auto *Loc2 = Env.getStorageLocation(E2, SkipPast::Reference);
+
+  if (Loc1 == nullptr) {
+    if (Loc2 != nullptr)
+      Env.setValue(*Loc2, createOptionalValue(Env, Env.makeAtomicBoolValue()));
+    return;
+  }
+  if (Loc2 == nullptr) {
+    Env.setValue(*Loc1, createOptionalValue(Env, Env.makeAtomicBoolValue()));
+    return;
+  }
 
-  auto *OptionalVal2 = State.Env.getValue(OptionalLoc2);
-  assert(OptionalVal2 != nullptr);
+  // 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.
+  auto *Val1 = Env.getValue(*Loc1);
+  if (Val1 == nullptr)
+    Val1 = &createOptionalValue(Env, Env.makeAtomicBoolValue());
+
+  auto *Val2 = Env.getValue(*Loc2);
+  if (Val2 == nullptr)
+    Val2 = &createOptionalValue(Env, Env.makeAtomicBoolValue());
 
-  State.Env.setValue(OptionalLoc1, *OptionalVal2);
-  State.Env.setValue(OptionalLoc2, *OptionalVal1);
+  Env.setValue(*Loc1, *Val2);
+  Env.setValue(*Loc2, *Val1);
 }
 
 void transferSwapCall(const CXXMemberCallExpr *E,
                       const MatchFinder::MatchResult &,
                       LatticeTransferState &State) {
   assert(E->getNumArgs() == 1);
-
-  auto *OptionalLoc1 = State.Env.getStorageLocation(
-      *E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer);
-  assert(OptionalLoc1 != nullptr);
-
-  auto *OptionalLoc2 =
-      State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
-  assert(OptionalLoc2 != nullptr);
-
-  transferSwap(*OptionalLoc1, *OptionalLoc2, State);
+  transferSwap(*E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer,
+               *E->getArg(0), State.Env);
 }
 
 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
                          LatticeTransferState &State) {
   assert(E->getNumArgs() == 2);
-
-  auto *OptionalLoc1 =
-      State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
-  assert(OptionalLoc1 != nullptr);
-
-  auto *OptionalLoc2 =
-      State.Env.getStorageLocation(*E->getArg(1), SkipPast::Reference);
-  assert(OptionalLoc2 != nullptr);
-
-  transferSwap(*OptionalLoc1, *OptionalLoc2, State);
+  transferSwap(*E->getArg(0), SkipPast::Reference, *E->getArg(1), State.Env);
 }
 
 BoolValue &evaluateEquality(Environment &Env, BoolValue &EqVal, BoolValue &LHS,
                             BoolValue &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

clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp

 //===- UncheckedOptionalAccessModelTest.cpp -------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 // FIXME: Move this to clang/unittests/Analysis/FlowSensitive/Models.
 
 #include "clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h"
 #include "TestingSupport.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
-#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <optional>
void target() {
 
       opt1.value();
 
       opt2.value(); // [[unsafe]]
     }
   )");
 }
 
+TEST_P(UncheckedOptionalAccessTest, SwapUnmodeledLocLeft) {
+  ExpectDiagnosticsFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct L { $ns::$optional<int> hd; L* tl; };
+
+    void target() {
+      $ns::$optional<int> foo = 3;
+      L bar;
+
+      // Any `tl` beyond the first is not modeled.
+      bar.tl->tl->hd.swap(foo);
+
+      bar.tl->tl->hd.value(); // [[unsafe]]
+      foo.value(); // [[unsafe]]
+    }
+  )");
+}
+
+TEST_P(UncheckedOptionalAccessTest, SwapUnmodeledLocRight) {
+  ExpectDiagnosticsFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct L { $ns::$optional<int> hd; L* tl; };
+
+    void target() {
+      $ns::$optional<int> foo = 3;
+      L bar;
+
+      // Any `tl` beyond the first is not modeled.
+      foo.swap(bar.tl->tl->hd);
+
+      bar.tl->tl->hd.value(); // [[unsafe]]
+      foo.value(); // [[unsafe]]
+    }
+  )");
+}
+
+TEST_P(UncheckedOptionalAccessTest, SwapUnmodeledValueLeftSet) {
+  ExpectDiagnosticsFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct S { int x; };
+    struct A { $ns::$optional<S> late; };
+    struct B { A f3; };
+    struct C { B f2; };
+    struct D { C f1; };
+
+    void target() {
+      $ns::$optional<S> foo = S{3};
+      D bar;
+
+      bar.f1.f2.f3.late.swap(foo);
+
+      bar.f1.f2.f3.late.value();
+      foo.value(); // [[unsafe]]
+    }
+  )");
+}
+
+TEST_P(UncheckedOptionalAccessTest, SwapUnmodeledValueLeftUnset) {
+  ExpectDiagnosticsFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct S { int x; };
+    struct A { $ns::$optional<S> late; };
+    struct B { A f3; };
+    struct C { B f2; };
+    struct D { C f1; };
+
+    void target() {
+      $ns::$optional<S> foo;
+      D bar;
+
+      bar.f1.f2.f3.late.swap(foo);
+
+      bar.f1.f2.f3.late.value(); // [[unsafe]]
+      foo.value(); // [[unsafe]]
+    }
+  )");
+}
+
+// fixme: use recursion instead of depth.
+TEST_P(UncheckedOptionalAccessTest, SwapUnmodeledValueRightSet) {
+  ExpectDiagnosticsFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct S { int x; };
+    struct A { $ns::$optional<S> late; };
+    struct B { A f3; };
+    struct C { B f2; };
+    struct D { C f1; };
+
+    void target() {
+      $ns::$optional<S> foo = S{3};
+      D bar;
+
+      foo.swap(bar.f1.f2.f3.late);
+
+      bar.f1.f2.f3.late.value();
+      foo.value(); // [[unsafe]]
+    }
+  )");
+}
+
+TEST_P(UncheckedOptionalAccessTest, SwapUnmodeledValueRightUnset) {
+  ExpectDiagnosticsFor(
+      R"(
+    #include "unchecked_optional_access_test.h"
+
+    struct S { int x; };
+    struct A { $ns::$optional<S> late; };
+    struct B { A f3; };
+    struct C { B f2; };
+    struct D { C f1; };
+
+    void target() {
+      $ns::$optional<S> foo;
+      D bar;
+
+      foo.swap(bar.f1.f2.f3.late);
+
+      bar.f1.f2.f3.late.value(); // [[unsafe]]
+      foo.value(); // [[unsafe]]
+    }
+  )");
+}
+
 TEST_P(UncheckedOptionalAccessTest, UniquePtrToOptional) {
   // We suppress diagnostics for optionals in smart pointers (other than
   // `optional` itself).
   ExpectDiagnosticsFor(
       R"(
     #include "unchecked_optional_access_test.h"
 
     template <typename T>