[analyzer] Retrieve a value from list initialization of multi-dimensional array declaration.

[ASDenysPetrov]

Summary

Add support of multi-dimensional arrays in RegionStoreManager::getBindingForElement. Handle nested ElementRegion's getting offsets and checking for being in bounds. Get values from the nested initialization lists using obtained offsets.

Example:

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

[martong]

Could you please rebase on top of D111542? That would make the changes direct and clear and the review would be easier.

[ASDenysPetrov]

In D111654#3060822, @martong wrote:

Could you please rebase on top of D111542? That would make the changes direct and clear and the review would be easier.

OK. I'll rebase.

[ASDenysPetrov]

Improved. Rebased on top of D107339.
@martong kind ping.

[steakhal]

This is an important step towards better handling of global initializer expressions.
I'm looking forward to it. Although, I have concerns to address.

clang/lib/AST/Type.cpp

141–143 ↗

(On Diff #381562)

These comments should be in the header file instead.

149 ↗

(On Diff #381562)

I suspect this not gonna look through typedefs.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1750–1761

I dislike this part of code. It has side effects all over the place.
Please use immediately called lambdas to describe your intentions in a more pure manner.

Besides that, when I see ElementRegions, I'm always scared. They sometimes represent reinterpret casts.
Since you have dealt with so many casts and region store stuff in the past, I'm assuming you have thought about this here.
Although, I'm still scared slightly, and I'd like to have evidence of this thought process. Likely some assertions or at least some comments? Could you @ASDenysPetrov elaborate on this?

1814

I would rather take it by value. They are designed so.
A mutable reference is always a bad sign anyway.
BTW for a brief moment I thought reverse() returns a temporary, but it doesn't, so we don't dangle at least.

1820

Please use the isNegative(). And don't have sideffects in conditions. advance the iterator at the end of the if.
I also think you can eliminate the I variable.
That way the getExtValue() would be guarded by the negativity check. I know that your code would behave the same, but I would find that phrasing slightly easier to follow.
This way you could even spare the 2 comment lines.

1824

This is probably a rare case when a continue is preferred instead of the else statement.

1861–1872

Just spell out uint64_t here. We don't win much by using auto.

1879–1884

Please, restructure this. Probably negating the condition and returning on that path would do the job.

clang/test/Analysis/initialization.cpp

17–23

Sorry If I was misunderstood in the previous patches.
I think, for this instance, the key is that arr is const, so this TU is supposed to provide this linker symbol, thus any other definitions would violate the ODR.
So, the FIXME is actually accurate, and we should report 0 here.

56

Does this work if the = {} is not present?

99

Uh, this would be a regression.
Accessing Unknown is not a bug, unlike accessing Undefined - which is a clear indication that we must have had UB in the calculation previously, to get this. So, this is slightly similar to llvm poison on that sense.

110

typo

[martong]

clang/include/clang/AST/Type.h

2953 ↗

(On Diff #381562)

Could this be a free function (not a member function)? That way we could put it as an implementation detail of RegionStore.cpp and we could spare the timely review from the AST code owners.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

444–446

Could you please add docs to this function? Especially to ConcreteOffsets param.

1748–1761

I think this could be implemented in it's own separate function, couldn't it?

1763

Please address this TODO.

1799–1800

Perhaps this hunk could be in an individual implementation function?

clang/test/Analysis/initialization.c

76

Very good!

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1750–1761

Please use immediately called lambdas.

I'll do.

They sometimes represent reinterpret casts. ... I'm assuming you have thought about this here.

Yes. This is my another revision in the stack. You are welcome: D110927

1763

I found the tests:

• Analysis/MemRegion.cpp
• Analysis/ctor.mm
• Analysis/mpichecker.cpp
• Analysis/string.c

They cover this check.

[ASDenysPetrov]

clang/test/Analysis/initialization.cpp

17–23

Right. FALSE expected. And it is fixed with the patch. But this case duplicates some more detailed cases I've added below. So I decide to remove it.

56

The compiler (AST) doesn't pass you through without an initializer by emitting a warning. But still there is a case without initializer at the end of the file. Yes, it does work.

99

This is a big problem with casts (in SValBuilder::evalCast). I've investigated it. Relates to D89055. IMO the solution will take a separate patch stack. I'm going to fix this next.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1799–1800

There are two returns inside the loop. That would not such easy to do a separate function for this.

[ASDenysPetrov]

@martong @steakhal
Thank you for your remarks. Updated according to them (at least the best I could do for now).

[martong]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1799–1800

There are two returns inside the loop. That would not such easy to do a separate function for this.

I think you could return with an Optional<SVal> and then in the call site you could check if the optional is set.
Optional<SVal> areOffsetsOutOfBounds(...) ?

Then in the caller:

if (Optional<SVal> CheckResult = areOffsetsOutOfBounds(...))
  return *CheckResult;

[steakhal]

Please, try to focus on marking inline comments done if you accomplished them.
It takes some time to reevaluate them one-by-one on each update.
Aside from that, I'd like to apply these and play with them but I'm frequently having conflicts applying your patches.

Regarding the patch, I think it's in a pretty good shape, given that you fix the regression I pointed in an inline comment.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1810–1811

Can this be empty? If so, the subsequent .front() is UB.
Put here an assertion if you are sure that it cannot be empty.

clang/test/Analysis/initialization.cpp

17–23

Awesome, thanks!

56

Okay, thanks!

99

I think until you do that we should stick to the previous behavior.
Please address this regression, so report UNKNOWN for these cases or the correct answer.

[ASDenysPetrov]

I'll do an update soon taking into account all the suggestions.

Please, try to focus on marking inline comments done if you accomplished them.

In the next update.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1799–1800

Great idea.

[ASDenysPetrov]

@steakhal @martong Updated according to your comments.
I think I'm done with this patch.

[ASDenysPetrov]

• Added support of aliased types (work with canonical array type).
• Added tests aliased types.
• Added tests with initialization values in parentheses.

[ASDenysPetrov]

Changed test to fix a buildbot failure.

[steakhal]

I'm still worried about the fact that you assume that there is a correspondence between ElementRegions and InitListExprs.
I cannot see why this assumption holds, since reinterpret casts might introduce ElementRegions which could mess with this assumption.
Aside from that, I'm okay with the general idea of doing this kind of stuff.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1661–1662

If I'm right then this is called the base of the region more often than not.
It would be probably a better choice than using MR.

1663–1665

IMO this is not a concern in real-life code.

1666–1667

I would prefer returning a pair instead of an output parameter.

1788–1790

I think you can hide this within the getConstantArrayExtents(). That is the only function touching this variable anyway.
That way you could also spare the comments about CAT requiring it to be canonical.

[ASDenysPetrov]

@steakhal Thank you for your suggestion. I'll make corresponding changes.

I'm still worried about the fact that you assume that there is a correspondence between ElementRegions and InitListExprs.
I cannot see why this assumption holds, since reinterpret casts might introduce ElementRegions which could mess with this assumption.

Currently in practice ElementRegions for array element access expression look like InitListExprs structure. But you are right about mess with different casts. That's why I have FIXME's in glob_ptr_index2 and glob_invalid_index6.
Right now I'm working on fixing this stuff. I'm gonna refactor StoreManager::castRegion in a part of ElementRegions to distinguish between array indirections and casts.

[steakhal]

In D111654#3109585, @ASDenysPetrov wrote:

@steakhal Thank you for your suggestion. I'll make corresponding changes.

I'm still worried about the fact that you assume that there is a correspondence between ElementRegions and InitListExprs.
I cannot see why this assumption holds, since reinterpret casts might introduce ElementRegions which could mess with this assumption.

Currently in practice ElementRegions for array element access expression look like InitListExprs structure. But you are right about mess with different casts. That's why I have FIXME's in glob_ptr_index2 and glob_invalid_index6.
Right now I'm working on fixing this stuff. I'm gonna refactor StoreManager::castRegion in a part of ElementRegions to distinguish between array indirections and casts.

Awesome! Let's get the minor nits addressed and land it.
Thank you for working on this.

[ASDenysPetrov]

Updated according to @steakhal's comments.

[steakhal]

Feel free to commit your change given that you fix my final nits.
Yeah, I'm soo bad in review. I should have proposed these previously. Sorry.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1641

You don't need to document this.
Aside from that consider marking these implementation detail functions static if they are not yet in an anonymous namespace - I haven't checked.

1646

I think we will get it :D

1749

The std::tie() pattern is probably more readable.

[ASDenysPetrov]

Updated according to the nits.

[ASDenysPetrov]

@steakhal

Thanks for your effort!

Yeah, I'm soo bad in review. I should have proposed these previously. Sorry.

No, you're not! I'm telling you. Keep it up! :)

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);
+  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);
 
 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);
   }
if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
     if (Result.second)
       Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
                                                             Result.second);
   }
 
   return Result;
 }
 
+/// This is a helper function for `getConstantValFromConstArrayInitializer`.
+///
+/// Return an array of extents of the declared array type.
+///
+/// E.g. for `int x[1][2][3];` returns { 1, 2, 3 }.
+static SmallVector<uint64_t, 2>
+getConstantArrayExtents(const ConstantArrayType *CAT) {
+  assert(CAT && "ConstantArrayType should not be null");
+  CAT = cast<ConstantArrayType>(CAT->getCanonicalTypeInternal());
+  SmallVector<uint64_t, 2> Extents;
+  do {
+    Extents.push_back(CAT->getSize().getZExtValue());
+  } while ((CAT = dyn_cast<ConstantArrayType>(CAT->getElementType())));
+  return Extents;
+}
+
+/// This is a helper function for `getConstantValFromConstArrayInitializer`.
+///
+/// Return an array of offsets from nested ElementRegions and a root base
+/// region. The array is never empty and a base region is never null.
+///
+/// E.g. for `Element{Element{Element{VarRegion},1},2},3}` returns { 3, 2, 1 }.
+/// This represents an access through indirection: `arr[1][2][3];`
+///
+/// \param ER The given (possibly nested) ElementRegion.
+///
+/// \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. It may not affect performance in real-life
+/// code, though.
+static std::pair<SmallVector<SVal, 2>, const MemRegion *>
+getElementRegionOffsetsWithBase(const ElementRegion *ER) {
+  assert(ER && "ConstantArrayType should not be null");
+  const MemRegion *Base;
+  SmallVector<SVal, 2> SValOffsets;
+  do {
+    SValOffsets.push_back(ER->getIndex());
+    Base = ER->getSuperRegion();
+    ER = dyn_cast<ElementRegion>(Base);
+  } while (ER);
+  return {SValOffsets, Base};
+}
+
+/// This is a helper function for `getConstantValFromConstArrayInitializer`.
+///
+/// Convert array of offsets from `SVal` to `uint64_t` in consideration of
+/// respective array extents.
+/// \param SrcOffsets [in]   The array of offsets of type `SVal` in reversed
+///   order (expectedly received from `getElementRegionOffsetsWithBase`).
+/// \param ArrayExtents [in] The array of extents.
+/// \param DstOffsets [out]  The array of offsets of type `uint64_t`.
+/// \returns:
+/// - `None` for successful convertion.
+/// - `UndefinedVal` or `UnknownVal` otherwise. It's expected that this SVal
+///   will be returned as a suitable value of the access operation.
+///   which should be returned as a correct
+///
+/// \example:
+///   const int arr[10][20][30] = {}; // ArrayExtents { 10, 20, 30 }
+///   int x1 = arr[4][5][6]; // SrcOffsets { NonLoc(6), NonLoc(5), NonLoc(4) }
+///                          // DstOffsets { 4, 5, 6 }
+///                          // returns None
+///   int x2 = arr[42][5][-6]; // returns UndefinedVal
+///   int x3 = arr[4][5][x2];  // returns UnknownVal
+static Optional<SVal>
+convertOffsetsFromSvalToUnsigneds(const SmallVector<SVal, 2> &SrcOffsets,
+                                  const SmallVector<uint64_t, 2> ArrayExtents,
+                                  SmallVector<uint64_t, 2> &DstOffsets) {
+  // 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[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
+  DstOffsets.resize(SrcOffsets.size());
+  auto ExtentIt = ArrayExtents.begin();
+  auto OffsetIt = DstOffsets.begin();
+  // Reverse `SValOffsets` to make it consistent with `ArrayExtents`.
+  for (SVal V : llvm::reverse(SrcOffsets)) {
+    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();
+  }
+  return None;
+}
+
 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.
+  SmallVector<SVal, 2> SValOffsets;
+  const MemRegion *Base;
+  std::tie(SValOffsets, Base) = getElementRegionOffsetsWithBase(R);
+  const VarRegion *VR = dyn_cast<VarRegion>(Base);
+  if (!VR)
+    return None;
+
+  assert(!SValOffsets.empty() && "getElementRegionOffsets guarantees the "
+                                 "offsets vector is not empty.");
 
   // 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 `ConstantArrayType` type, because only this
   // type contains an array extent. It may happen that array type can be of
   // `IncompleteArrayType` type. To get the declaration of `ConstantArrayType`
   // type, we should find the declaration in the redeclarations chain that has
   // the initialization expression.
   // NOTE: `getAnyInitializer` has an out-parameter, which returns a new `VD`
   // from which an initializer is obtained. We replace current `VD` with the new
   // `VD`. If the return value of the function is null than `VD` won't be
   // replaced.
   const Expr *Init = VD->getAnyInitializer(VD);
   // NOTE: If `Init` is non-null, then a new `VD` is non-null for sure. So check
   // `Init` for null only and don't worry about the replaced `VD`.
   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;
+  // Get array extents.
+  SmallVector<uint64_t, 2> Extents = getConstantArrayExtents(CAT);
 
-  // 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
+  // FIXME: Should return UndefinedVal.
+  if (SValOffsets.size() != Extents.size())
+    return None;
 
-  // 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.
+  SmallVector<uint64_t, 2> ConcreteOffsets;
+  if (Optional<SVal> V = convertOffsetsFromSvalToUnsigneds(SValOffsets, Extents,
+                                                           ConcreteOffsets))
+    return *V;
 
   // 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) {
+/// Returns an SVal, if possible, for the specified position of an
+/// initialization list.
+///
+/// \param ILE The given initialization list.
+/// \param Offsets The array of unsigned offsets. E.g. for the expression
+///  `int x = arr[1][2][3];` an array should be { 1, 2, 3 }.
+/// \param ElemT The type of the result SVal expression.
+/// \return Optional SVal for the particular position in the initialization
+///   list. E.g. for the list `{{1, 2},[3, 4],{5, 6}, {}}` offsets:
+///   - {1, 1} returns SVal{4}, because it's the second position in the second
+///     sublist;
+///   - {3, 0} returns SVal{0}, because there's no explicit value at this
+///     position in the sublist.
+///
+/// NOTE: Inorder to get a valid SVal, a caller shall guarantee valid offsets
+/// for the given initialization list. Otherwise SVal can be an equivalent to 0
+/// or lead to assertion.
+Optional<SVal> RegionStoreManager::getSValFromInitListExpr(
+    const InitListExpr *ILE, const SmallVector<uint64_t, 2> &Offsets,
+    QualType ElemT) {
   assert(ILE && "InitListExpr should not be null");
 
+  for (uint64_t Offset : Offsets) {
     // 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);
 
+    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.
-  const Expr *E = ILE->getInit(Offset);
       return svalBuilder.getConstantVal(E);
+
+    // Go to the nested initializer list.
+    ILE = IL;
+  }
+  llvm_unreachable(
+      "Unhandled InitListExpr sub-expressions or invalid offsets.");
 }
 
 /// Returns an SVal, if possible, for the specified position in a string
 /// literal.
 ///
 /// \param SL The given string literal.
 /// \param Offset The unsigned offset. E.g. for the expression
 ///   `char x = str[42];` an offset should be 42.
 ///   E.g. for the string "abc" offset:
 ///   - 1 returns SVal{b}, because it's the second position in the string.
 ///   - 42 returns SVal{0}, because there's no explicit value at this
 ///     position in the string.
 /// \param ElemT The type of the result SVal expression.
 ///
 /// NOTE: We return `0` for every offset >= the literal length for array
 /// declarations, like:
 ///   const char str[42] = "123"; // Literal length is 4.
 ///   char c = str[41];           // Offset is 41.
 /// FIXME: Nevertheless, we can't do the same for pointer declaraions, like:
 ///   const char * const str = "123"; // Literal length is 4.
if (!Ctx.hasSameUnqualifiedType(T, R->getElementType()))
       return UnknownVal();
     if (const auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
       const llvm::APSInt &Idx = CI->getValue();
       if (Idx < 0)
         return UndefinedVal();
       const StringLiteral *SL = StrR->getStringLiteral();
       return getSValFromStringLiteral(SL, Idx.getZExtValue(), 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;
   }
 
   // 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.

clang/test/Analysis/initialization.c

 }
 
 void glob_invalid_index2() {
   const int *ptr = glob_arr1;
   int x = 42;
   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}}
+  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}}
 }
 
-// TODO: Support multidimensional array.
 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];
 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;
   // FIXME: Should recognize that it is 3.
   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}}
   clang_analyzer_eval(glob_arr1[1] == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_arr1[2] == 0); // expected-warning{{TRUE}}
 }
 
 void glob_invalid_index1() {

 }
 
 const float glob_arr3[] = {
     0.0000, 0.0235, 0.0470, 0.0706, 0.0941, 0.1176};
 float no_warn_garbage_value() {
   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
 }
 
-// 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}}
+  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}}
 }
 
-// TODO: Support multidimensional array.
 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}}
 }
 
-// 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]; // 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 {

 
 const char *const glob_ptr12 = u8"abc";
 void glob_ptr_index8() {
   clang_analyzer_eval(glob_ptr12[0] == 'a');  // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_ptr12[1] == 'b');  // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_ptr12[2] == 'c');  // expected-warning{{TRUE}}
   clang_analyzer_eval(glob_ptr12[3] == '\0'); // expected-warning{{TRUE}}
 }
+
+typedef int Int;
+typedef Int const CInt;
+typedef CInt Arr[2];
+typedef Arr Arr2[4];
+Arr2 glob_arr8 = {{1}, 3, 4, 5}; // const int[4][2]
+void glob_array_typedef1() {
+  clang_analyzer_eval(glob_arr8[0][0] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr8[0][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr8[1][0] == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr8[1][1] == 4); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr8[2][0] == 5); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr8[2][1] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr8[3][0] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr8[3][1] == 0); // expected-warning{{TRUE}}
+}
+
+const int glob_arr9[2][4] = {{(1), 2, ((3)), 4}, 5, 6, (((7)))};
+void glob_array_parentheses1() {
+  clang_analyzer_eval(glob_arr9[0][0] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr9[0][1] == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr9[0][2] == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr9[0][3] == 4); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr9[1][0] == 5); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr9[1][1] == 6); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr9[1][2] == 7); // expected-warning{{TRUE}}
+  clang_analyzer_eval(glob_arr9[1][3] == 0); // expected-warning{{TRUE}}
+}