[analyzer][NFCI] Move a block from `getBindingForElement` to separate functions

[ASDenysPetrov]

Summary

1. Improve readability by moving deeply nested block of code from RegionStoreManager::getBindingForElement to new separate functions:
   • getConstantValFromConstArrayInitializer;
   • getSValFromInitListExpr.
2. Handle the case when index is a symbolic value. Write specific test cases.
3. Add test cases when there is no initialization expression presented.

This patch implies to make next patches clearer and easier for review process.

[ASDenysPetrov]

Rebased.

[ASDenysPetrov]

This patch is currently irrelevant after last changes in the parent revision. It's going to be reworked or permanently abandoned.

[ASDenysPetrov]

@martong
Please, look. As you suggested in D111542#inline-1064497 I made an intermediate patch making next patches easer for review.

[steakhal]

So, you return None instead of returning UndefinedVal.
All in all, it looks good, aside from a couple stuff inline.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1636

Please preserve the original comment.

1650

What if that is a typedef?

1686–1689

This should have been checked at L1642 to preserve the original behavior.
As of now, the code might return UndefinedVal at L1683 or Unknown at L1659, which is probably different than the original behavior - unless you prove otherwise.

1714

What other values could appear in this context other than constants?

[ASDenysPetrov]

@steakhal
All your comments are fair in terms of NFC. I also tried to improve some places. I think I should requalificate the revision to non-NFC, that I can be more untied to bring some improvements.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1636

OK.

1650

I'll add a test case.

1714

It's hard to say. I didn't do any investigation yet, but I think some symbolic or loc values.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1686–1689

Unknown at L1659 comes from RegionStoreManager::getBindingForFieldOrElementCommon. As you can see, there is a snippet in here:

if (hasSymbolicIndex)
  return UnknownVal();

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1686–1689

UndefinedVal at L1683 preserves exactly the previous behaviour.

[steakhal]

I think it's fine, maybe NFCi is would be slightly more accurate, while stating the minor behavior change and the reason for doing so in the patch summary could further improve the visibility of this issue.

That being said, since it actually changes some behavior, I'd like to request some tests covering the following (uncovered lines):
L1646, L1689, L1699

[ASDenysPetrov]

In D106681#3074678, @steakhal wrote:

I think it's fine, maybe NFCi is would be slightly more accurate, while stating the minor behavior change and the reason for doing so in the patch summary could further improve the visibility of this issue.

That being said, since it actually changes some behavior, I'd like to request some tests covering the following (uncovered lines):
L1646, L1689, L1699

For L1646 currently I'm not sure about the exact test, since it is a heritage of the old code, so it just jumped here from the past. If you could give an example I would appreciate this.
For L1689 I'll add it.
For L1699 I've added TODO cases in D104285.

[ASDenysPetrov]

Make changes according to comments. Thanks to @steakhal

[ASDenysPetrov]

Minor comment update.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1666

Item 2 from the Summary. This was borrowed from RegionStoreManager::getBindingForFieldOrElementCommon :

if (hasSymbolicIndex)
   return UnknownVal();

[ASDenysPetrov]

Fixed redefinition in test file initialization.cpp.

[steakhal]

In D106681#3074779, @ASDenysPetrov wrote:

In D106681#3074678, @steakhal wrote:

I think it's fine, maybe NFCi is would be slightly more accurate, while stating the minor behavior change and the reason for doing so in the patch summary could further improve the visibility of this issue.

That being said, since it actually changes some behavior, I'd like to request some tests covering the following (uncovered lines):
L1646, L1689, L1699

For L1646 currently I'm not sure about the exact test, since it is a heritage of the old code, so it just jumped here from the past. If you could give an example I would appreciate this.
For L1689 I'll add it.
For L1699 I've added TODO cases in D104285.

I just wanted you to think about these cases.
BTW this should work for L1646:

extern const int arr[]; // Incomplete array type
void top() {
  (void)arr[42];
}

And I'm okay with the rest of the uncovered lines.

clang/test/Analysis/initialization.c

103

I'm pretty sure we should not get Unknown for simply loading from a global variable.
That would imply that loading two times subsequently we could not prove that the value remained the same.
But that should remain the same, thus compare equal unless some other code modifier that memory region.

That could happen for two reasons:

1. There is a racecondition, and another thread modified that location. But that would be UB, so that could not happen.
2. The global variable is volatile, so the hardware might changed its content- but this global is not volatile so this does not apply.

That being said, this load should have resulted in a fresh conjured symbolic value instead of unknown.
Could you please check if it did result in unknown before your patch, or you did introduce this behavior?

[ASDenysPetrov]

In D106681#3075337, @steakhal wrote:

I just wanted you to think about these cases.
BTW this should work for L1646:

extern const int arr[]; // Incomplete array type
void top() {
  (void)arr[42];
}

Yes this will work for L1646. But I've already added similar tests for this line: glob_array_index4 and struct_arr_index1 functions in initialization.cpp. I mean it doesn't matter whether it is an incomplete or complete type.

clang/test/Analysis/initialization.c

103

I'm not sure I caught your thoughts.
But I think the things is much simplier:
clang_analyzer_eval can only produce UNKNOWN or TRUE or FALSE. If we know the constraint of glob_arr_no_init[2] we return TRUE or FALSE, and UNKNOWN otherwise.
But in fact I should use clang_analyzer_dump here instead of clang_analyzer_eval. This is actually my fault. I'll update this.

[martong]

Thanks, this looks good to me! But, please wait for an approve from @steakhal as well.

clang/test/Analysis/initialization.c

103

Could you please check if it did result in unknown before your patch, or you did introduce this behavior?

I've just checked it, it was Unknown before this patch as well.
And actually, that is wrong because the array has static storage duration and as such, we know that it is initialized with zeros according to the C standard. But, that should be addressed in a follow-up patch (if someone has the capacity).
https://stackoverflow.com/questions/32708161/value-of-uninitialized-elements-in-array-of-c-language/32708288

[steakhal]

clang/test/Analysis/initialization.c

103

Oh true. I was actually tricked by the initialization.cpp:38, where I actually caught this. And in that case, you use dump() yet you get Unknown as a result. But the issue remains the same.

[ASDenysPetrov]

clang/test/Analysis/initialization.c

103

C++ also states about zero-initialization for static storage lifetime duration: http://eel.is/c++draft/basic.start.static#2
I think it will be among my next patches.

[ASDenysPetrov]

clang/test/Analysis/initialization.c

103

And in that case, you use dump() yet you get Unknown as a result. But the issue remains the same.

I just realized that I was confused as well :) The dump returns a symbolic value like reg_$0<int Element{glob_arr_no_init,2 S64b,int}>, not Unknown. So my intention of using eval was deliberate. Anyway we should improve this to produce FALSE instead of UNKNOWN, since it has a static storage.

[steakhal]

clang/test/Analysis/initialization.c

103

It's a really complex topic. I would highly recommend taking baby steps to improve this area.

In C, you might have a chance to accomplish something, but in C++ static globals might be initialized by running a constructor, which means arbitrary user-defined code. This is actually why we disabled similar logic in the RegionStore::getInitialStore(). I highly recommend taking a look.

Consider this code:

// TU 1:
#include <cstdio>
static int a;  // zero-initialized initially
int *p2a = &a; // escapes the address of 'a'

int main() {
  printf("%d\n", a); // reports 42
}

// TU 2:
extern int *p2a;
static bool sentinel = (*p2a = 42, false);

[ASDenysPetrov]

Added a comment to initialization.c, that we can reason about values of constant array which doesn't have an initializer. This is not such simple for C++, since there are much more ways to initialize the array.

[ASDenysPetrov]

clang/test/Analysis/initialization.c

103

Yes, I see what you mean. I'm going to tough the part of C++ in the near future.

103

Yes, I see what you mean. I'm going to tough the part of C++ in the near future.

*Yes, I see what you mean. I'm not going to tough the part of C++ in the near future.

[steakhal]

Sorry for blocking the review of this one for so long.

clang/test/Analysis/initialization.c

103

Okay, I see now.

[ASDenysPetrov]

In D106681#3083409, @steakhal wrote:

Sorry for blocking the review of this one for so long.

Thank you for the review!

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

StoreRef invalidateRegions(Store store,
                              InvalidatedRegions *Invalidated,
                              InvalidatedRegions *InvalidatedTopLevel) override;
 
   bool scanReachableSymbols(Store S, const MemRegion *R,
                             ScanReachableSymbols &Callbacks) override;
 
   RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B,
                                             const SubRegion *R);
+  Optional<SVal> getConstantValFromConstArrayInitializer(
+      RegionBindingsConstRef B, const VarRegion *VR, const ElementRegion *R);
+  Optional<SVal> getSValFromInitListExpr(const InitListExpr *ILE,
+                                         uint64_t Offset, QualType ElemT);
 
 public: // Part of public interface to class.
 
   StoreRef Bind(Store store, Loc LV, SVal V) override {
     return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this);
   }
 
   RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V);
if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
     if (Result.second)
       Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
                                                             Result.second);
   }
 
   return Result;
 }
 
+Optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer(
+    RegionBindingsConstRef B, const VarRegion *VR, const ElementRegion *R) {
+  assert(R && VR && "Regions should not be null");
+
+  // Check if the containing array has an initialized value that we can trust.
+  // We can trust a const value or a value of a global initializer in main().
+  const VarDecl *VD = VR->getDecl();
+  if (!VD->getType().isConstQualified() &&
+      !R->getElementType().isConstQualified() &&
+      (!B.isMainAnalysis() || !VD->hasGlobalStorage()))
+    return None;
+
+  // Array's declaration should have an initializer.
+  const Expr *Init = VD->getAnyInitializer();
+  if (!Init)
+    return None;
+
+  // Array's declaration should have ConstantArrayType type, because only this
+  // type contains an array extent.
+  const ConstantArrayType *CAT = Ctx.getAsConstantArrayType(VD->getType());
+  if (!CAT)
+    return None;
+
+  // Array should be one-dimensional.
+  // TODO: Support multidimensional array.
+  if (isa<ConstantArrayType>(CAT->getElementType())) // is multidimensional
+    return None;
+
+  // Array's offset should be a concrete value.
+  // Return Unknown value if symbolic index presented.
+  // FIXME: We also need to take ElementRegions with symbolic
+  // indexes into account.
+  const auto OffsetVal = R->getIndex().getAs<nonloc::ConcreteInt>();
+  if (!OffsetVal.hasValue())
+    return UnknownVal();
+
+  // Check offset for being out of bounds.
+  // C++20 [expr.add] 7.6.6.4 (excerpt):
+  //   If P points to an array element i of an array object x with n
+  //   elements, where i < 0 or i > n, the behavior is undefined.
+  //   Dereferencing is not allowed on the "one past the last
+  //   element", when i == n.
+  // Example:
+  //   const int arr[4] = {1, 2};
+  //   const int *ptr = arr;
+  //   int x0 = ptr[0];  // 1
+  //   int x1 = ptr[1];  // 2
+  //   int x2 = ptr[2];  // 0
+  //   int x3 = ptr[3];  // 0
+  //   int x4 = ptr[4];  // UB
+  //   int x5 = ptr[-1]; // UB
+  const llvm::APSInt &OffsetInt = OffsetVal->getValue();
+  const auto Offset = static_cast<uint64_t>(OffsetInt.getExtValue());
+  // Use `getZExtValue` because array extent can not be negative.
+  const uint64_t Extent = CAT->getSize().getZExtValue();
+  // Check for `OffsetInt < 0` but NOT for `Offset < 0`, because `OffsetInt`
+  // CAN be negative, but `Offset` can NOT, because `Offset` is an uint64_t.
+  if (OffsetInt < 0 || Offset >= Extent)
+    return UndefinedVal();
+  // From here `Offset` is in the bounds.
+
+  // Handle InitListExpr.
+  if (const auto *ILE = dyn_cast<InitListExpr>(Init))
+    return getSValFromInitListExpr(ILE, Offset, R->getElementType());
+
+  // FIXME: Handle StringLiteral.
+
+  // FIXME: Handle CompoundLiteralExpr.
+
+  return None;
+}
+
+Optional<SVal>
+RegionStoreManager::getSValFromInitListExpr(const InitListExpr *ILE,
+                                            uint64_t Offset, QualType ElemT) {
+  assert(ILE && "InitListExpr should not be null");
+
+  // C++20 [expr.add] 9.4.17.5 (excerpt):
+  //   i-th array element is value-initialized for each k < i ≤ n,
+  //   where k is an expression-list size and n is an array extent.
+  if (Offset >= ILE->getNumInits())
+    return svalBuilder.makeZeroVal(ElemT);
+
+  // Return a constant value, if it is presented.
+  // FIXME: Support other SVals.
+  const Expr *E = ILE->getInit(Offset);
+  return svalBuilder.getConstantVal(E);
+}
+
 SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
                                               const ElementRegion* R) {
   // Check if the region has a binding.
   if (const Optional<SVal> &V = B.getDirectBinding(R))
     return *V;
 
   const MemRegion* superR = R->getSuperRegion();
 
if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) {
       // Technically, only i == length is guaranteed to be null.
       // However, such overflows should be caught before reaching this point;
       // the only time such an access would be made is if a string literal was
       // used to initialize a larger array.
       char c = (i >= length) ? '\0' : Str->getCodeUnit(i);
       return svalBuilder.makeIntVal(c, T);
     }
   } else if (const VarRegion *VR = dyn_cast<VarRegion>(superR)) {
-    // Check if the containing array has an initialized value that we can trust.
-    // We can trust a const value or a value of a global initializer in main().
-    const VarDecl *VD = VR->getDecl();
-    if (VD->getType().isConstQualified() ||
-        R->getElementType().isConstQualified() ||
-        (B.isMainAnalysis() && VD->hasGlobalStorage())) {
-      if (const Expr *Init = VD->getAnyInitializer()) {
-        if (const auto *InitList = dyn_cast<InitListExpr>(Init)) {
-          // The array index has to be known.
-          if (auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
-            // If it is not an array, return Undef.
-            QualType T = VD->getType();
-            const ConstantArrayType *CAT = Ctx.getAsConstantArrayType(T);
-            if (!CAT)
-              return UndefinedVal();
-
-            // Support one-dimensional array.
-            // C++20 [expr.add] 7.6.6.4 (excerpt):
-            //   If P points to an array element i of an array object x with n
-            //   elements, where i < 0 or i > n, the behavior is undefined.
-            //   Dereferencing is not allowed on the "one past the last
-            //   element", when i == n.
-            // Example:
-            //   const int arr[4] = {1, 2};
-            //   const int *ptr = arr;
-            //   int x0 = ptr[0]; // 1
-            //   int x1 = ptr[1]; // 2
-            //   int x2 = ptr[2]; // 0
-            //   int x3 = ptr[3]; // 0
-            //   int x4 = ptr[4]; // UB
-            // TODO: Support multidimensional array.
-            if (!isa<ConstantArrayType>(CAT->getElementType())) {
-              // One-dimensional array.
-              const llvm::APSInt &Idx = CI->getValue();
-              const auto I = static_cast<uint64_t>(Idx.getExtValue());
-              // Use `getZExtValue` because array extent can not be negative.
-              const uint64_t Extent = CAT->getSize().getZExtValue();
-              // Check for `Idx < 0`, NOT for `I < 0`, because `Idx` CAN be
-              // negative, but `I` can NOT.
-              if (Idx < 0 || I >= Extent)
-                return UndefinedVal();
-
-              // C++20 [expr.add] 9.4.17.5 (excerpt):
-              //   i-th array element is value-initialized for each k < i ≤ n,
-              //   where k is an expression-list size and n is an array extent.
-              if (I >= InitList->getNumInits())
-                return svalBuilder.makeZeroVal(R->getElementType());
-
-              // Return a constant value, if it is presented.
-              // FIXME: Support other SVals.
-              const Expr *E = InitList->getInit(I);
-              if (Optional<SVal> V = svalBuilder.getConstantVal(E))
-                return *V;
-            }
-          }
-        }
-      }
-    }
-  }
+    if (Optional<SVal> V = getConstantValFromConstArrayInitializer(B, VR, R))
 
   // Check for loads from a code text region.  For such loads, just give up.
   if (isa<CodeTextRegion>(superR))
     return UnknownVal();
 
   // Handle the case where we are indexing into a larger scalar object.
   // For example, this handles:
   //   int x = ...

clang/test/Analysis/initialization.c

 }
 
 // TODO: Support multidimensional array.
 void glob_invalid_index4() {
   int x = 3, y = 2;
   // FIXME: Should warn {{garbage or undefined}}.
   int res = glob_arr2[x][y]; // no-warning
 }
+
+const int glob_arr_no_init[10];
+void glob_arr_index4() {
+  // FIXME: Should warn {{FALSE}}, since the array has a static storage.
+  clang_analyzer_eval(glob_arr_no_init[2]); // expected-warning{{UNKNOWN}}
+}

clang/test/Analysis/initialization.cpp

 // RUN: %clang_cc1 -std=c++14 -triple i386-apple-darwin10 -analyze -analyzer-config eagerly-assume=false -analyzer-checker=core.uninitialized.Assign,core.builtin,debug.ExprInspection,core.uninitialized.UndefReturn -verify %s
 
+template <typename T>
+void clang_analyzer_dump(T x);
 void clang_analyzer_eval(int);
 
 struct S {
   int a = 3;
 };
 S const sarr[2] = {};
 void definit() {
   int i = 1;

 }
 
 void glob_invalid_index1() {
   const int *ptr = glob_arr1;
   int idx = -42;
   auto x = ptr[idx]; // expected-warning{{garbage or undefined}}
 }
 
+void glob_symbolic_index1(int idx) {
+  clang_analyzer_dump(glob_arr1[idx]); // expected-warning{{Unknown}}
+}
+
 int const glob_arr2[4] = {1, 2};
 void glob_ptr_index1() {
   int const *ptr = glob_arr2;
   clang_analyzer_eval(ptr[0] == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(ptr[1] == 2); // expected-warning{{TRUE}}
   clang_analyzer_eval(ptr[2] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(ptr[3] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(ptr[4] == 0); // expected-warning{{UNDEFINED}}

 
 // TODO: Support multidimensional array.
 void glob_invalid_index6() {
   int const *ptr = &glob_arr5[1][0];
   int idx = 42;
   // FIXME: Should warn {{garbage or undefined}}.
   auto x = ptr[idx]; // // no-warning
 }
+
+extern const int glob_arr_no_init[10];
+void glob_array_index4() {
+  clang_analyzer_eval(glob_arr_no_init[2]); // expected-warning{{UNKNOWN}}
+}
+
+struct S2 {
+  static const int arr_no_init[10];
+};
+void struct_arr_index1() {
+  clang_analyzer_eval(S2::arr_no_init[2]); // expected-warning{{UNKNOWN}}
+}