[analyzer] Disable direct binding from list initialization for constant arrays of local storage duration.

[ASDenysPetrov]

Summary

Ignore direct bindings for constant arrays of local storage duration with list initialization. Constant arrays don't change their values during a lifetime. Therefore, we don't have to bind values directly for each array element. Retrieve values from list initialization on-demand as it currently works for arrays of global storage duration (See https://reviews.llvm.org/D106681 for details).

Example: const int arr[42] = {1,2,3,4};.
We can get values directly from list initializaion in any time, no matter whether the array has global or local storage duration. Previously it works only for global arrays.

[ASDenysPetrov]

Fixed clang-tidy complaints.

[ASDenysPetrov]

Refined code a bit.

[ASDenysPetrov]

Fixed clang-tidy complaints.

[ASDenysPetrov]

Rebased.

[ASDenysPetrov]

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

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

Optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer(
   // Array should constant a const value or a value of a global initializer in
   // main().
   const VarDecl *VD = VR->getDecl();
   if (!VD->getType().isConstQualified() && !ElemT.isConstQualified() &&
       (!B.isMainAnalysis() || !VD->hasGlobalStorage()))
     return None;
   // Array should have an initialization list.
   const Expr *Init = VD->getAnyInitializer();
-  // FIXME: Support StringLiteral as an initializer as well.
+  // FIXME: Support StringLiteral and CompoundLiteralExpr as well.
   const auto *InitList = dyn_cast_or_null<InitListExpr>(Init);
   if (!InitList)
     return None;
   // Choose a correct function depending on index signedness.
   const int64_t I = Idx.getExtValue();
   const Expr *E =
       Idx.isSigned()
           ? InitList->getExprForConstArrayByRawIndex(I)
else {
     // should know how to default-initialize any value we can symbolicate.
     assert(!SymbolManager::canSymbolicate(T) && "This type is representable");
     V = UnknownVal();
   }
 
   return B.addBinding(R, BindingKey::Default, V);
 }
 
-RegionBindingsRef
-RegionStoreManager::bindArray(RegionBindingsConstRef B,
-                              const TypedValueRegion* R,
+RegionBindingsRef RegionStoreManager::bindArray(RegionBindingsConstRef B,
+                                                const TypedValueRegion *R,
                                                 SVal Init) {
+  // Ignore binding `InitListExpr` to arrays of const type,
+  // since we can directly retrieve values from initializer using
+  // `getConstantValFromConstArrayInitializer`.For example:
+  //   const int arr[42] = { 1, 2, 3 };
+  // The init values of this array will never change, so we don't have to
+  // store them additionally in the RegionStore.
+  if (const auto *VR = dyn_cast<VarRegion>(R)) {
+    const VarDecl *VD = VR->getDecl();
+    // Ignore only arrays which values can't change.
+    if (VD->getType().isConstQualified()) {
+      const Expr *Init = VD->getAnyInitializer();
+      // FIXME: Ignore `StringLiteral` and `CompoundLiteralExpr` as well when
+      // `getConstantValFromConstArrayInitializer` supports them.
+      if (Init && isa<InitListExpr>(Init))
+        return B;
+    }
+  }
 
-  const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
+  const ArrayType *AT =
+      cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
   QualType ElementTy = AT->getElementType();
   Optional<uint64_t> Size;
 
   if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
     Size = CAT->getSize().getZExtValue();
 
   // Check if the init expr is a literal. If so, bind the rvalue instead.
   // FIXME: It's not responsibility of the Store to transform this lvalue

clang/test/Analysis/initialization.c

void out_of_bound_index1() {
   int x = -1, y = -1;
   int res = glob_arr1[x][y]; // expected-warning{{garbage or undefined}}
 }
 
 void out_of_bound_index2() {
   int x = 3, y = 2;
   int res = glob_arr1[x][y]; // expected-warning{{garbage or undefined}}
 }
+
+void local_arr_index1() {
+  const int local_arr[8] = {[2] = 3, [0] = 1, [1] = 2, [3] = 4};
+  clang_analyzer_eval(local_arr[0] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1] == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[2] == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[3] == 4); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[4] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[5] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[6] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[7] == 0); // expected-warning{{TRUE}}
+}
+
+void local_arr_out_of_bound_index1() {
+  const int local_arr[8] = {[2] = 3, [0] = 1, [1] = 2, [3] = 4};
+  int x = -42;
+  int res = local_arr[x]; // expected-warning{{garbage or undefined}}
+}
+
+void local_arr_out_of_bound_index2() {
+  const int local_arr[8] = {[2] = 3, [0] = 1, [1] = 2, [3] = 4};
+  int x = 42;
+  int res = local_arr[x]; // expected-warning{{garbage or undefined}}
+}

clang/test/Analysis/initialization.cpp

void glob_arr_index3() {
   clang_analyzer_eval(glob_arr3[1][0] == 3); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr3[1][1] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr3[2][0] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr3[2][1] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr3[3][0] == 7); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr3[3][1] == 0); // expected-warning{{TRUE}}
 }
 
-void negative_index1() {
+void glob_arr_negative_index1() {
   int x = 2, y = -2;
   clang_analyzer_eval(glob_arr3[x][y] == 3); // expected-warning{{TRUE}}
   x = 4;
   y = -2;
   clang_analyzer_eval(glob_arr3[x][y] == 7); // expected-warning{{TRUE}}
 }
 
-void out_of_bound_index1() {
+void glob_arr_out_of_bound_index1() {
   int x = -3, y = 2;
   int res = glob_arr3[x][y]; // expected-warning{{garbage or undefined}}
 }
 
-void out_of_bound_index2() {
+void glob_arr_out_of_bound_index2() {
   int x = 3, y = 2;
   int res = glob_arr3[x][y]; // expected-warning{{garbage or undefined}}
 }
 
 const int glob_arr4[8] = {1, 2, 3, 4};
 void glob_arr_index4() {
   clang_analyzer_eval(glob_arr4[0] == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr4[1] == 2); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr4[2] == 3); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr4[3] == 4); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr4[4] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr4[5] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr4[6] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr4[7] == 0); // expected-warning{{TRUE}}
 }
 
-void out_of_bound_index3() {
+void glob_arr_out_of_bound_index3() {
   int x = -42;
   int res = glob_arr4[x]; // expected-warning{{garbage or undefined}}
 }
 
-void out_of_bound_index4() {
+void glob_arr_out_of_bound_index4() {
   int x = 42;
   int res = glob_arr4[x]; // expected-warning{{garbage or undefined}}
 }
+
+void local_arr_index1() {
+  const int local_arr[2][2][3] = {{{1, 2}}, {{7}}};
+  clang_analyzer_eval(local_arr[0][0][0] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][0][1] == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][0][2] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][1][0] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][1][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][1][2] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][0][0] == 7); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][0][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][0][2] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][1][0] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][1][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][1][2] == 0); // expected-warning{{TRUE}}
+}
+
+void local_arr_index2() {
+  int const local_arr[2][2][3] = {{{1, 2}, {}}, {{7, 8}, {10, 11, 12}}};
+  clang_analyzer_eval(local_arr[0][0][0] == 1);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][0][1] == 2);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][0][2] == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][1][0] == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][1][1] == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][1][2] == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][0][0] == 7);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][0][1] == 8);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][0][2] == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][1][0] == 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][1][1] == 11); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][1][2] == 12); // expected-warning{{TRUE}}
+}
+
+void local_arr_index3() {
+  const int local_arr[4][2] = {{}, {3}, {}, {7}};
+  clang_analyzer_eval(local_arr[0][0] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[0][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][0] == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[2][0] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[2][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[3][0] == 7); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[3][1] == 0); // expected-warning{{TRUE}}
+}
+
+void local_arr_negative_index1() {
+  const int local_arr[4][2] = {{}, {3}, {}, {7}};
+  int x = 2, y = -2;
+  clang_analyzer_eval(local_arr[x][y] == 3); // expected-warning{{TRUE}}
+  x = 4;
+  y = -2;
+  clang_analyzer_eval(local_arr[x][y] == 7); // expected-warning{{TRUE}}
+}
+
+void local_arr_out_of_bound_index1() {
+  const int local_arr[4][2] = {{}, {3}, {}, {7}};
+  int x = -3, y = 2;
+  int res = local_arr[x][y]; // expected-warning{{garbage or undefined}}
+}
+
+void local_arr_out_of_bound_index2() {
+  const int local_arr[4][2] = {{}, {3}, {}, {7}};
+  int x = 3, y = 2;
+  int res = local_arr[x][y]; // expected-warning{{garbage or undefined}}
+}
+
+void local_arr_index4() {
+  const int local_arr[8] = {1, 2, 3, 4};
+  clang_analyzer_eval(local_arr[0] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[1] == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[2] == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[3] == 4); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[4] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[5] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[6] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(local_arr[7] == 0); // expected-warning{{TRUE}}
+}
+
+void local_arr_out_of_bound_index3() {
+  const int local_arr[8] = {1, 2, 3, 4};
+  int x = -42;
+  int res = local_arr[x]; // expected-warning{{garbage or undefined}}
+}
+
+void local_arr_out_of_bound_index4() {
+  const int local_arr[8] = {1, 2, 3, 4};
+  int x = 42;
+  int res = local_arr[x]; // expected-warning{{garbage or undefined}}
+}