[clang-format] Minimize the damage caused by AlignArrayOfStructures when working on non square arrays

I have lost count of the number of times this has been reported, but it fundamentally comes down to the fact that the "AlignArrayLeft/Right" function is fundamentally broken for non-square arrays.

As a result, a pointer can end up running off the end of the array structure, I've spent the last 2 weekends trying to rewrite this algorithm but I've struggled to get it aligned correctly.

This is an interim fix, that ignores all array that are non-square and leaves them alone. I think this can allow us to close out most of the crashes (if not all).

I think this can help reduce the number of bugs coming in that are duplicates.

https://github.com/llvm/llvm-project/issues/53748
https://github.com/llvm/llvm-project/issues/51767
https://github.com/llvm/llvm-project/issues/51277

Reviewed By: curdeius, HazardyKnusperkeks, feg208

Differential Revision: https://reviews.llvm.org/D121069

5 files changed, 179 insertions, 16 deletions

diff --git a/clang/docs/ClangFormatStyleOptions.rst b/clang/docs/ClangFormatStyleOptions.rst
index 473cf9cb192e..1f2e94940b53 100644
--- a/clang/docs/ClangFormatStyleOptions.rst
+++ b/clang/docs/ClangFormatStyleOptions.rst
@@ -236,6 +236,9 @@ the configuration (without a prefix: ``Auto``).
   if not ``None``, when using initialization for an array of structs
   aligns the fields into columns.
 
+  NOTE: As of clang-format 15 this option only applied to arrays with equal
+  number of columns per row.
+
   Possible values:
 
   * ``AIAS_Left`` (in configuration: ``Left``)
diff --git a/clang/include/clang/Format/Format.h b/clang/include/clang/Format/Format.h
index 81f8190211ec..49b932c8d16e 100644
--- a/clang/include/clang/Format/Format.h
+++ b/clang/include/clang/Format/Format.h
@@ -131,6 +131,10 @@ struct FormatStyle {
   };
   /// if not ``None``, when using initialization for an array of structs
   /// aligns the fields into columns.
+  ///
+  /// NOTE: As of clang-format 15 this option only applied to arrays with equal
+  /// number of columns per row.
+  ///
   /// \version 13
   ArrayInitializerAlignmentStyle AlignArrayOfStructures;
 
diff --git a/clang/lib/Format/WhitespaceManager.cpp b/clang/lib/Format/WhitespaceManager.cpp
index 55e0b7f8e8d9..b62fdb33722a 100644
--- a/clang/lib/Format/WhitespaceManager.cpp
+++ b/clang/lib/Format/WhitespaceManager.cpp
@@ -1032,11 +1032,13 @@ void WhitespaceManager::alignArrayInitializers(unsigned Start, unsigned End) {
 
 void WhitespaceManager::alignArrayInitializersRightJustified(
     CellDescriptions &&CellDescs) {
-  auto &Cells = CellDescs.Cells;
+  if (!CellDescs.isRectangular())
+    return;
 
+  auto &Cells = CellDescs.Cells;
   // Now go through and fixup the spaces.
   auto *CellIter = Cells.begin();
-  for (auto i = 0U; i < CellDescs.CellCount; ++i, ++CellIter) {
+  for (auto i = 0U; i < CellDescs.CellCounts[0]; ++i, ++CellIter) {
     unsigned NetWidth = 0U;
     if (isSplitCell(*CellIter))
       NetWidth = getNetWidth(Cells.begin(), CellIter, CellDescs.InitialSpaces);
@@ -1058,16 +1060,16 @@ void WhitespaceManager::alignArrayInitializersRightJustified(
       if (CellIter != Cells.begin()) {
         auto ThisNetWidth =
             getNetWidth(Cells.begin(), CellIter, CellDescs.InitialSpaces);
-        auto MaxNetWidth =
-            getMaximumNetWidth(Cells.begin(), CellIter, CellDescs.InitialSpaces,
-                               CellDescs.CellCount);
+        auto MaxNetWidth = getMaximumNetWidth(
+            Cells.begin(), CellIter, CellDescs.InitialSpaces,
+            CellDescs.CellCounts[0], CellDescs.CellCounts.size());
         if (ThisNetWidth < MaxNetWidth)
           Changes[CellIter->Index].Spaces = (MaxNetWidth - ThisNetWidth);
         auto RowCount = 1U;
         auto Offset = std::distance(Cells.begin(), CellIter);
         for (const auto *Next = CellIter->NextColumnElement; Next != nullptr;
              Next = Next->NextColumnElement) {
-          auto *Start = (Cells.begin() + RowCount * CellDescs.CellCount);
+          auto *Start = (Cells.begin() + RowCount * CellDescs.CellCounts[0]);
           auto *End = Start + Offset;
           ThisNetWidth = getNetWidth(Start, End, CellDescs.InitialSpaces);
           if (ThisNetWidth < MaxNetWidth)
@@ -1100,8 +1102,11 @@ void WhitespaceManager::alignArrayInitializersRightJustified(
 
 void WhitespaceManager::alignArrayInitializersLeftJustified(
     CellDescriptions &&CellDescs) {
-  auto &Cells = CellDescs.Cells;
 
+  if (!CellDescs.isRectangular())
+    return;
+
+  auto &Cells = CellDescs.Cells;
   // Now go through and fixup the spaces.
   auto *CellIter = Cells.begin();
   // The first cell needs to be against the left brace.
@@ -1110,9 +1115,10 @@ void WhitespaceManager::alignArrayInitializersLeftJustified(
   else
     Changes[CellIter->Index].Spaces = CellDescs.InitialSpaces;
   ++CellIter;
-  for (auto i = 1U; i < CellDescs.CellCount; i++, ++CellIter) {
+  for (auto i = 1U; i < CellDescs.CellCounts[0]; i++, ++CellIter) {
     auto MaxNetWidth = getMaximumNetWidth(
-        Cells.begin(), CellIter, CellDescs.InitialSpaces, CellDescs.CellCount);
+        Cells.begin(), CellIter, CellDescs.InitialSpaces,
+        CellDescs.CellCounts[0], CellDescs.CellCounts.size());
     auto ThisNetWidth =
         getNetWidth(Cells.begin(), CellIter, CellDescs.InitialSpaces);
     if (Changes[CellIter->Index].NewlinesBefore == 0) {
@@ -1124,7 +1130,10 @@ void WhitespaceManager::alignArrayInitializersLeftJustified(
     auto Offset = std::distance(Cells.begin(), CellIter);
     for (const auto *Next = CellIter->NextColumnElement; Next != nullptr;
          Next = Next->NextColumnElement) {
-      auto *Start = (Cells.begin() + RowCount * CellDescs.CellCount);
+      if (RowCount > CellDescs.CellCounts.size()) {
+        break;
+      }
+      auto *Start = (Cells.begin() + RowCount * CellDescs.CellCounts[0]);
       auto *End = Start + Offset;
       auto ThisNetWidth = getNetWidth(Start, End, CellDescs.InitialSpaces);
       if (Changes[Next->Index].NewlinesBefore == 0) {
@@ -1152,7 +1161,7 @@ WhitespaceManager::CellDescriptions WhitespaceManager::getCells(unsigned Start,
 
   unsigned Depth = 0;
   unsigned Cell = 0;
-  unsigned CellCount = 0;
+  SmallVector<unsigned> CellCounts;
   unsigned InitialSpaces = 0;
   unsigned InitialTokenLength = 0;
   unsigned EndSpaces = 0;
@@ -1192,7 +1201,8 @@ WhitespaceManager::CellDescriptions WhitespaceManager::getCells(unsigned Start,
         if (!Cells.empty())
           Cells.back().EndIndex = i;
         Cells.push_back(CellDescription{i, ++Cell, i + 1, false, nullptr});
-        CellCount = C.Tok->Previous->isNot(tok::comma) ? Cell + 1 : Cell;
+        CellCounts.push_back(C.Tok->Previous->isNot(tok::comma) ? Cell + 1
+                                                                : Cell);
         // Go to the next non-comment and ensure there is a break in front
         const auto *NextNonComment = C.Tok->getNextNonComment();
         while (NextNonComment->is(tok::comma))
@@ -1262,7 +1272,7 @@ WhitespaceManager::CellDescriptions WhitespaceManager::getCells(unsigned Start,
     }
   }
 
-  return linkCells({Cells, CellCount, InitialSpaces});
+  return linkCells({Cells, CellCounts, InitialSpaces});
 }
 
 unsigned WhitespaceManager::calculateCellWidth(unsigned Start, unsigned End,
diff --git a/clang/lib/Format/WhitespaceManager.h b/clang/lib/Format/WhitespaceManager.h
index 42f958f68ba6..2be62338bc9a 100644
--- a/clang/lib/Format/WhitespaceManager.h
+++ b/clang/lib/Format/WhitespaceManager.h
@@ -196,8 +196,20 @@ private:
 
   struct CellDescriptions {
     SmallVector<CellDescription> Cells;
-    unsigned CellCount = 0;
+    SmallVector<unsigned> CellCounts;
     unsigned InitialSpaces = 0;
+
+    // Determine if every row in the the array
+    // has the same number of columns.
+    bool isRectangular() const {
+      if (CellCounts.empty())
+        return false;
+
+      for (auto NumberOfColumns : CellCounts)
+        if (NumberOfColumns != CellCounts[0])
+          return false;
+      return true;
+    }
   };
 
   /// Calculate \c IsTrailingComment, \c TokenLength for the last tokens
@@ -295,13 +307,15 @@ private:
   /// Get The maximum width of all columns to a given cell.
   template <typename I>
   unsigned getMaximumNetWidth(const I &CellStart, const I &CellStop,
-                              unsigned InitialSpaces,
-                              unsigned CellCount) const {
+                              unsigned InitialSpaces, unsigned CellCount,
+                              unsigned MaxRowCount) const {
     auto MaxNetWidth = getNetWidth(CellStart, CellStop, InitialSpaces);
     auto RowCount = 1U;
     auto Offset = std::distance(CellStart, CellStop);
     for (const auto *Next = CellStop->NextColumnElement; Next != nullptr;
          Next = Next->NextColumnElement) {
+      if (RowCount > MaxRowCount)
+        break;
       auto Start = (CellStart + RowCount * CellCount);
       auto End = Start + Offset;
       MaxNetWidth =
diff --git a/clang/unittests/Format/FormatTest.cpp b/clang/unittests/Format/FormatTest.cpp
index dab8f83fffe3..b344ac33cd58 100644
--- a/clang/unittests/Format/FormatTest.cpp
+++ b/clang/unittests/Format/FormatTest.cpp
@@ -25335,6 +25335,138 @@ TEST_F(FormatTest, UnderstandsDigraphs) {
   verifyFormat("#define A x%:%:y");
 }
 
+TEST_F(FormatTest, AlignArrayOfStructuresLeftAlignmentNonSquare) {
+  auto Style = getLLVMStyle();
+  Style.AlignArrayOfStructures = FormatStyle::AIAS_Left;
+  Style.AlignConsecutiveAssignments =
+      FormatStyle::AlignConsecutiveStyle::ACS_Consecutive;
+  Style.AlignConsecutiveDeclarations =
+      FormatStyle::AlignConsecutiveStyle::ACS_Consecutive;
+
+  // The AlignArray code is incorrect for non square Arrays and can cause
+  // crashes, these tests assert that the array is not changed but will
+  // also act as regression tests for when it is properly fixed
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8}\n"
+               "};",
+               Style);
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2, 3, 4, 5},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8}\n"
+               "};",
+               Style);
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2, 3, 4, 5},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8, 9, 10, 11, 12}\n"
+               "};",
+               Style);
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2, 3},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8, 9, 10, 11, 12}\n"
+               "};",
+               Style);
+
+  verifyFormat("S{\n"
+               "    {},\n"
+               "    {},\n"
+               "    {a, b}\n"
+               "};",
+               Style);
+  verifyFormat("S{\n"
+               "    {},\n"
+               "    {},\n"
+               "    {a, b},\n"
+               "};",
+               Style);
+  verifyFormat("void foo() {\n"
+               "  auto thing = test{\n"
+               "      {\n"
+               "       {13}, {something}, // A\n"
+               "      }\n"
+               "  };\n"
+               "}",
+               "void foo() {\n"
+               "  auto thing = test{\n"
+               "      {\n"
+               "       {13},\n"
+               "       {something}, // A\n"
+               "      }\n"
+               "  };\n"
+               "}",
+               Style);
+}
+
+TEST_F(FormatTest, AlignArrayOfStructuresRightAlignmentNonSquare) {
+  auto Style = getLLVMStyle();
+  Style.AlignArrayOfStructures = FormatStyle::AIAS_Right;
+  Style.AlignConsecutiveAssignments =
+      FormatStyle::AlignConsecutiveStyle::ACS_Consecutive;
+  Style.AlignConsecutiveDeclarations =
+      FormatStyle::AlignConsecutiveStyle::ACS_Consecutive;
+
+  // The AlignArray code is incorrect for non square Arrays and can cause
+  // crashes, these tests assert that the array is not changed but will
+  // also act as regression tests for when it is properly fixed
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8}\n"
+               "};",
+               Style);
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2, 3, 4, 5},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8}\n"
+               "};",
+               Style);
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2, 3, 4, 5},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8, 9, 10, 11, 12}\n"
+               "};",
+               Style);
+  verifyFormat("struct test demo[] = {\n"
+               "    {1, 2, 3},\n"
+               "    {3, 4, 5},\n"
+               "    {6, 7, 8, 9, 10, 11, 12}\n"
+               "};",
+               Style);
+
+  verifyFormat("S{\n"
+               "    {},\n"
+               "    {},\n"
+               "    {a, b}\n"
+               "};",
+               Style);
+  verifyFormat("S{\n"
+               "    {},\n"
+               "    {},\n"
+               "    {a, b},\n"
+               "};",
+               Style);
+  verifyFormat("void foo() {\n"
+               "  auto thing = test{\n"
+               "      {\n"
+               "       {13}, {something}, // A\n"
+               "      }\n"
+               "  };\n"
+               "}",
+               "void foo() {\n"
+               "  auto thing = test{\n"
+               "      {\n"
+               "       {13},\n"
+               "       {something}, // A\n"
+               "      }\n"
+               "  };\n"
+               "}",
+               Style);
+}
+
 } // namespace
 } // namespace format
 } // namespace clang