ASDenysPetrov updated this revision to Diff 382361.
ASDenysPetrov added a comment.
@martong @steakhal
Thank you for your remarks. Updated according to them (at least the best I
could do for now).
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D111654/new/
https://reviews.llvm.org/D111654
Files:
clang/lib/StaticAnalyzer/Core/RegionStore.cpp
clang/test/Analysis/initialization.c
clang/test/Analysis/initialization.cpp
Index: clang/test/Analysis/initialization.cpp
===================================================================
--- clang/test/Analysis/initialization.cpp
+++ clang/test/Analysis/initialization.cpp
@@ -14,13 +14,6 @@
clang_analyzer_eval(sarr[i].a); // expected-warning{{UNKNOWN}}
}
-int const arr[2][2] = {};
-void arr2init() {
- int i = 1;
- // FIXME: Should recognize that it is 0.
- clang_analyzer_eval(arr[i][0]); // expected-warning{{UNKNOWN}}
-}
-
int const glob_arr1[3] = {};
void glob_array_index1() {
clang_analyzer_eval(glob_arr1[0] == 0); // expected-warning{{TRUE}}
@@ -60,79 +53,56 @@
return glob_arr3[0]; // no-warning (garbage or undefined)
}
-// TODO: Support multidimensional array.
int const glob_arr4[4][2] = {};
void glob_array_index2() {
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr4[1][0] == 0); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr4[1][1] == 0); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(glob_arr4[0][0] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr4[1][0] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr4[1][1] == 0); // expected-warning{{TRUE}}
}
-// TODO: Support multidimensional array.
void glob_invalid_index3() {
int idx = -42;
- // FIXME: Should warn {{garbage or undefined}}.
- auto x = glob_arr4[1][idx]; // no-warning
+ auto x = glob_arr4[1][idx]; // expected-warning{{garbage or undefined}}
}
-// TODO: Support multidimensional array.
void glob_invalid_index4() {
const int *ptr = glob_arr4[1];
int idx = -42;
- // FIXME: Should warn {{garbage or undefined}}.
- auto x = ptr[idx]; // no-warning
+ auto x = ptr[idx]; // expected-warning{{garbage or undefined}}
}
-// TODO: Support multidimensional array.
int const glob_arr5[4][2] = {{1}, 3, 4, 5};
void glob_array_index3() {
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[0][0] == 1); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[0][1] == 0); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[1][0] == 3); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[1][1] == 4); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[2][0] == 5); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[2][1] == 0); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[3][0] == 0); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(glob_arr5[3][1] == 0); // expected-warning{{UNKNOWN}}
-}
-
-// TODO: Support multidimensional array.
+ clang_analyzer_eval(glob_arr5[0][0] == 1); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr5[0][1] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr5[1][0] == 3); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr5[1][1] == 4); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr5[2][0] == 5); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr5[2][1] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr5[3][0] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr5[3][1] == 0); // expected-warning{{TRUE}}
+}
+
void glob_ptr_index2() {
int const *ptr = glob_arr5[1];
- // FIXME: Should be TRUE.
- clang_analyzer_eval(ptr[0] == 3); // expected-warning{{UNKNOWN}}
- // FIXME: Should be TRUE.
- clang_analyzer_eval(ptr[1] == 4); // expected-warning{{UNKNOWN}}
- // FIXME: Should be UNDEFINED.
- clang_analyzer_eval(ptr[2] == 5); // expected-warning{{UNKNOWN}}
- // FIXME: Should be UNDEFINED.
- clang_analyzer_eval(ptr[3] == 0); // expected-warning{{UNKNOWN}}
- // FIXME: Should be UNDEFINED.
- clang_analyzer_eval(ptr[4] == 0); // expected-warning{{UNKNOWN}}
+ // FIXME: Should be TRUE
+ clang_analyzer_eval(ptr[0] == 3); // expected-warning{{UNDEFINED}}
+ // FIXME: Should be TRUE
+ clang_analyzer_eval(ptr[1] == 4); // expected-warning{{UNDEFINED}}
+ clang_analyzer_eval(ptr[2] == 5); // expected-warning{{UNDEFINED}}
+ clang_analyzer_eval(ptr[3] == 0); // expected-warning{{UNDEFINED}}
+ clang_analyzer_eval(ptr[4] == 0); // expected-warning{{UNDEFINED}}
}
-// TODO: Support multidimensional array.
void glob_invalid_index5() {
int idx = -42;
- // FIXME: Should warn {{garbage or undefined}}.
- auto x = glob_arr5[1][idx]; // no-warning
+ auto x = glob_arr5[1][idx]; // expected-warning{{garbage or 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
+ auto x = ptr[idx]; // expected-warning{{garbage or undefined}}
}
extern const int glob_arr_no_init[10];
Index: clang/test/Analysis/initialization.c
===================================================================
--- clang/test/Analysis/initialization.c
+++ clang/test/Analysis/initialization.c
@@ -58,44 +58,35 @@
int res = ptr[x]; // expected-warning{{garbage or undefined}}
}
-// TODO: Support multidimensional array.
const int glob_arr2[3][3] = {[0][0] = 1, [1][1] = 5, [2][0] = 7};
void glob_arr_index3() {
- // FIXME: These all should be TRUE.
- clang_analyzer_eval(glob_arr2[0][0] == 1); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[0][1] == 0); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[0][2] == 0); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[1][0] == 0); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[1][1] == 5); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[1][2] == 0); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[2][0] == 7); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[2][1] == 0); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(glob_arr2[2][2] == 0); // expected-warning{{UNKNOWN}}
-}
-
-// TODO: Support multidimensional array.
+ clang_analyzer_eval(glob_arr2[0][0] == 1); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[0][1] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[0][2] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[1][0] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[1][1] == 5); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[1][2] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[2][0] == 7); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[2][1] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(glob_arr2[2][2] == 0); // expected-warning{{TRUE}}
+}
+
void negative_index() {
int x = 2, y = -2;
- // FIXME: Should be UNDEFINED.
- clang_analyzer_eval(glob_arr2[x][y] == 5); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(glob_arr2[x][y] == 5); // expected-warning{{UNDEFINED}}
x = 3;
y = -3;
- // FIXME: Should be UNDEFINED.
- clang_analyzer_eval(glob_arr2[x][y] == 7); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(glob_arr2[x][y] == 7); // expected-warning{{UNDEFINED}}
}
-// TODO: Support multidimensional array.
void glob_invalid_index3() {
int x = -1, y = -1;
- // FIXME: Should warn {{garbage or undefined}}.
- int res = glob_arr2[x][y]; // no-warning
+ int res = glob_arr2[x][y]; // expected-warning{{garbage or undefined}}
}
-// 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
+ int res = glob_arr2[x][y]; // expected-warning{{garbage or undefined}}
}
const int glob_arr_no_init[10];
Index: clang/lib/StaticAnalyzer/Core/RegionStore.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ clang/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -437,10 +437,13 @@
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);
+ Optional<SVal>
+ getConstantValFromConstArrayInitializer(RegionBindingsConstRef B,
+ const ElementRegion *R);
+ Optional<SVal>
+ getSValFromInitListExpr(const InitListExpr *ILE,
+ const SmallVector<uint64_t, 2> &ConcreteOffsets,
+ QualType ElemT);
SVal getSValFromStringLiteral(const StringLiteral *SL, uint64_t Offset,
QualType ElemT);
@@ -1631,9 +1634,49 @@
return Result;
}
+/// Return an array of extents of the declared array type.
+///
+/// E.g. for `int x[1][2][3];` returns { 1, 2, 3 }.
+SmallVector<uint64_t, 2> getConstantArrayExtents(const ConstantArrayType *CAT) {
+ assert(CAT && "ConstantArrayType should not be null");
+ SmallVector<uint64_t, 2> Extents;
+ do {
+ Extents.push_back(CAT->getSize().getZExtValue());
+ } while ((CAT = dyn_cast<ConstantArrayType>(CAT->getElementType())));
+ return Extents;
+}
+
+/// Return an array of offsets from nested ElementRegions.
+/// For `Element{Element{Element{VarRegion},1},2},3}` returns { 3, 2, 1 }.
+/// This represents an access through indirection: `arr[1][2][3];`
+/// \param ER [in] The given (possibly nested) ElementRegion.
+/// \param MR [out] The root MemRegion wrapped inside ElementRegion. It is
+/// guaranteed to be non-null.
+/// NOTE: The result array is in the reverse order of indirection expression:
+/// arr[1][2][3] -> { 3, 2, 1 }. This helps to provide complexity O(n), where n
+/// is a number of indirections.
+SmallVector<SVal, 2> getElementRegionOffsets(const ElementRegion *ER,
+ const MemRegion *&MR) {
+ assert(ER && "ConstantArrayType should not be null");
+ SmallVector<SVal, 2> SValOffsets;
+ do {
+ SValOffsets.push_back(ER->getIndex());
+ MR = ER->getSuperRegion();
+ ER = dyn_cast<ElementRegion>(MR);
+ } while (ER);
+ return SValOffsets;
+};
+
Optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer(
- RegionBindingsConstRef B, const VarRegion *VR, const ElementRegion *R) {
- assert(R && VR && "Regions should not be null");
+ RegionBindingsConstRef B, const ElementRegion *R) {
+ assert(R && "ElementRegion should not be null");
+
+ // Treat an n-dimensional array.
+ const MemRegion *MR;
+ SmallVector<SVal, 2> SValOffsets = getElementRegionOffsets(R, MR);
+ const VarRegion *VR = dyn_cast<VarRegion>(MR);
+ if (!VR)
+ return None;
// 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().
@@ -1664,85 +1707,104 @@
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();
+ // The number of offsets should equal to the numbers of extents,
+ // otherwise wrong type punning occured. For instance:
+ // int arr[1][2][3];
+ // auto ptr = (int(*)[42])arr;
+ // auto x = ptr[4][2]; // UB
+ // TODO: Add a test case for this check.
+ SmallVector<uint64_t, 2> Extents = getConstantArrayExtents(CAT);
+ if (SValOffsets.size() != Extents.size())
+ return UndefinedVal();
- // Check offset for being out of bounds.
+ // Check offsets 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.
+ // const int arr[3][2] = {{1, 2}, {3, 4}};
+ // arr[0][0]; // 1
+ // arr[0][1]; // 2
+ // arr[0][2]; // UB
+ // arr[1][0]; // 3
+ // arr[1][1]; // 4
+ // arr[1][-1]; // UB
+ // arr[2][0]; // 0
+ // arr[2][1]; // 0
+ // arr[-2][0]; // UB
+ SmallVector<uint64_t, 2> ConcreteOffsets;
+ ConcreteOffsets.resize(SValOffsets.size());
+ auto ExtentIt = Extents.begin();
+ auto OffsetIt = ConcreteOffsets.begin();
+ // Reverse `SValOffsets` to make it consistent with `Extents`.
+ for (SVal V : llvm::reverse(SValOffsets)) {
+ if (auto CI = V.getAs<nonloc::ConcreteInt>()) {
+ // When offset is out of array's bounds, result is UB.
+ const llvm::APSInt &Offset = CI->getValue();
+ if (Offset.isNegative() || Offset.uge(*(ExtentIt++)))
+ return UndefinedVal();
+ // Store index in a reversive order.
+ *(OffsetIt++) = Offset.getZExtValue();
+ continue;
+ }
+ // Symbolic index presented. Return Unknown value.
+ // FIXME: We also need to take ElementRegions with symbolic indexes into
+ // account.
+ return UnknownVal();
+ }
// Handle InitListExpr.
// Example:
- // const char arr[] = { 1, 2, 3 };
+ // const char arr[4][2] = { { 1, 2 }, { 3 }, 4, 5 };
if (const auto *ILE = dyn_cast<InitListExpr>(Init))
- return getSValFromInitListExpr(ILE, Offset, R->getElementType());
+ return getSValFromInitListExpr(ILE, ConcreteOffsets, R->getElementType());
// Handle StringLiteral.
// Example:
// const char arr[] = "abc";
if (const auto *SL = dyn_cast<StringLiteral>(Init))
- return getSValFromStringLiteral(SL, Offset, R->getElementType());
+ return getSValFromStringLiteral(SL, ConcreteOffsets.front(),
+ R->getElementType());
// FIXME: Handle CompoundLiteralExpr.
return None;
}
-Optional<SVal>
-RegionStoreManager::getSValFromInitListExpr(const InitListExpr *ILE,
- uint64_t Offset, QualType ElemT) {
+Optional<SVal> RegionStoreManager::getSValFromInitListExpr(
+ const InitListExpr *ILE, const SmallVector<uint64_t, 2> &ConcreteOffsets,
+ QualType ElemT) {
assert(ILE && "InitListExpr should not be null");
- // C++20 [dcl.init.string] 9.4.2.1:
- // An array of ordinary character type [...] can be initialized by [...]
- // an appropriately-typed string-literal enclosed in braces.
- // Example:
- // const char arr[] = { "abc" };
- if (ILE->isStringLiteralInit())
- if (const auto *SL = dyn_cast<StringLiteral>(ILE->getInit(0)))
- return getSValFromStringLiteral(SL, Offset, ElemT);
+ for (uint64_t Offset : ConcreteOffsets) {
+ // C++20 [dcl.init.string] 9.4.2.1:
+ // An array of ordinary character type [...] can be initialized by [...]
+ // an appropriately-typed string-literal enclosed in braces.
+ // Example:
+ // const char arr[] = { "abc" };
+ if (ILE->isStringLiteralInit())
+ if (const auto *SL = dyn_cast<StringLiteral>(ILE->getInit(0)))
+ return getSValFromStringLiteral(SL, Offset, ElemT);
- // 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);
+ // 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);
+ const Expr *E = ILE->getInit(Offset);
+ const auto *IL = dyn_cast<InitListExpr>(E);
+ if (!IL)
+ // Return a constant value, if it is presented.
+ // FIXME: Support other SVals.
+ return svalBuilder.getConstantVal(E);
+
+ // Go to the nested initializer list.
+ ILE = IL;
+ }
+ llvm_unreachable("Unknown InitListExpr construction.");
}
SVal RegionStoreManager::getSValFromStringLiteral(const StringLiteral *SL,
@@ -1787,8 +1849,8 @@
return UndefinedVal();
return getSValFromStringLiteral(SL, Offset, T);
}
- } else if (const VarRegion *VR = dyn_cast<VarRegion>(superR)) {
- if (Optional<SVal> V = getConstantValFromConstArrayInitializer(B, VR, R))
+ } else if (isa<ElementRegion, VarRegion>(superR)) {
+ if (Optional<SVal> V = getConstantValFromConstArrayInitializer(B, R))
return *V;
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
