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

[MyDeveloperDay]

Summary

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.

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

[MyDeveloperDay]

Update to always use the first row number of columns or unit tests crash

[MyDeveloperDay]

Add more producers

[curdeius]

clang/lib/Format/WhitespaceManager.h

204

Don't really like the name...
Some suggestions:

• HasEqualRows
• HasEqualRowLengths
• HasSameRowLengths
• IsRectangular

clang/unittests/Format/FormatTest.cpp

25346

Not sure I understand the comment here, this formatting looks ok, no?

25377

This one is "square", isn't it?
I think you wanted to omit 3 in the first row

[MyDeveloperDay]

Fix review comments and clang-format

NOTE: part of me wants to remove this feature completely, it doesn't work correctly in a number of corner cases.

This is really a compromise to stabilize its use.

[HazardyKnusperkeks]

There should also be a warning or at least note on the option description about the current limitations.

clang/lib/Format/WhitespaceManager.h

202–203

This should also be adapted.
And a full stop at the end.

[MyDeveloperDay]

Lets get the comment aligned with the code

[MyDeveloperDay]

NOTE: I've tried to collate all the reported crashing examples and run this fix through them (both Left and Right) all pass except this one below

void foo()
{
auto thing = test{
    {
       {13},
       {something}, //A
    }
  };
}

This is not related to it being non-square because it's not.

clang/unittests/Format/FormatTest.cpp

25346

The test is testing that it's not changing it.. with the old code it would (but incorrectly or crash)

[curdeius]

Nits only.
+1 for adding a note in the option documentation.

clang/lib/Format/WhitespaceManager.h

203

clang/unittests/Format/FormatTest.cpp

25396

Nit: should be updated as above I guess.

[MyDeveloperDay]

There were no checks for if the cell would run off the end of the CellDescs structure, this is part of the reason for the crashes that the PrevIter->Index becomes invalid and is then used to index into the Changes.

The code just assumed it knew how many rows and columns there were, but in some circumstances it gets it wrong and just keeps going. This MaxRows check should at least prevent that by ensuring we just don't keep going off the end of the rows. (this was the final crash)

Added a warning to the documentation.

[MyDeveloperDay]

clang/lib/Format/WhitespaceManager.cpp

1117

I don't understand in Left alignment why we ignore the first cell, but in right alignment, we don't!

clang/lib/Format/WhitespaceManager.h

319

Ultimately these calculations are incorrect unless every CellCount for every row is the same, and for non-square they are not, this always had me confused as to why it starts at 1?

[feg208]

I have been watching the issues pile up around this but work has prevented me from focusing on them. This seems like a reasonable compromise but the note of disabling this feature is also reasonable. Given where it had to be placed in the formatting flow I suspect it will be challenging to resolve most of the troublesome corner cases. I did investigate one bug I picked up but ran into the problems you described earlier and was going down the same compromise path.

[MyDeveloperDay]

@feg208 I could do with some clarity on the algorithm, am I correct in thinking it requires that the first row, to contain at least the maximum number of columns for the rest of the array. I sort of noticed it was fine if the first row was larger

{
    {1,2,3 }
    {4,5}
    {6}
}

[MyDeveloperDay]

In D121069#3362448, @feg208 wrote:

This seems like a reasonable compromise

I kind of feel this might be the best initial option, I don't want to disable it completely because it looks like people are trying to use it, (and it seems to work for the square array case).

At present, I want to stop the "crash" haemorrhaging.

[curdeius]

clang/lib/Format/WhitespaceManager.h

317

You can elide braces. Personally I use RemoveBraces locally.

[feg208]

In D121069#3362450, @MyDeveloperDay wrote:

@feg208 I could do with some clarity on the algorithm, am I correct in thinking it requires that the first row, to contain at least the maximum number of columns for the rest of the array. I sort of noticed it was fine if the first row was larger

{
    {1,2,3 }
    {4,5}
    {6}
}

Honestly it really is best with the square option. The assumption is an array of simple initializers though default args to constructors complicate that in the case of an array of single constructors. I think that you are seeing it be okay with the maximum as the first row is just an accident of the implementation. The direction I was heading in in the bug I picked up was to start restricting the set of things it would consider as array of initializers. Does that answer your question?

[owenpan]

clang/lib/Format/WhitespaceManager.cpp

1073

Can we use CellCounts[0] instead? The outer parentheses are superfluous. Same in alignArrayInitializersLeftJustified below.

1117

Because the first cell is already left-aligned by default?

clang/lib/Format/WhitespaceManager.h

204

My top choice by far is isRectangular.

211

We can omit the braces here.

317

Why do we need this check? Is it because CellStop might not be null terminated? Or is it because CellCount may be zero? If the latter, we can check CellCount before the loop instead of this check in the loop.

clang/unittests/Format/FormatTest.cpp

25353

Please remove \n here and in other places below when it's the last line of a test case.

[owenpan]

In D121069#3362424, @MyDeveloperDay wrote:

NOTE: I've tried to collate all the reported crashing examples and run this fix through them (both Left and Right) all pass except this one below

void foo()
{
auto thing = test{
    {
       {13},
       {something}, //A
    }
  };
}

This is not related to it being non-square because it's not.

I think had a simple fix for this. I will revisit it after you land this patch.

clang/lib/Format/WhitespaceManager.h

202–203

Do they fit in one line?

[owenpan]

clang/lib/Format/WhitespaceManager.h

317

Ok, you already explained why you added the check, but I still wonder what causes it.

[owenpan]

clang/lib/Format/WhitespaceManager.h

319

Ultimately these calculations are incorrect unless every CellCount for every row is the same, and for non-square they are not, this always had me confused as to why it starts at 1?

Because the loop starts at CellStop->NextColumnElement, the 2nd row of the column?

[MyDeveloperDay]

Fixing final review comments prior to commit

clang/docs/ClangFormatStyleOptions.rst

* ``BAS_BlockIndent`` (in configuration: ``BlockIndent``)
      Note: This currently only applies to parentheses.
 
 
 
 **AlignArrayOfStructures** (``ArrayInitializerAlignmentStyle``) :versionbadge:`clang-format 13`
   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``)
     Align array column and left justify the columns e.g.:
 
     .. code-block:: c++
 
       struct test demo[] =

clang/include/clang/Format/Format.h

enum ArrayInitializerAlignmentStyle {
     ///   };
     /// \endcode
     AIAS_Right,
     /// Don't align array initializer columns.
     AIAS_None
   };
   /// 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;
 
   /// Styles for alignment of consecutive tokens. Tokens can be assignment signs
   /// (see
   /// ``AlignConsecutiveAssignments``), bitfield member separators (see
   /// ``AlignConsecutiveBitFields``), names in declarations (see
   /// ``AlignConsecutiveDeclarations``) or macro definitions (see

clang/lib/Format/WhitespaceManager.h

struct CellDescription {
     }
     constexpr bool operator!=(const CellDescription &Other) const {
       return !(*this == Other);
     }
   };
 
   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
   /// or token parts in a line and \c PreviousEndOfTokenColumn and
   /// \c EscapedNewlineColumn for the first tokens or token parts in a line.
   void calculateLineBreakInformation();
 
   /// \brief Align consecutive C/C++ preprocessor macros over all \c Changes.
for (const auto *Next = CellIter->NextColumnElement; Next != nullptr;
       CellWidth = std::max(CellWidth, ThisWidth);
     }
     return CellWidth;
   }
 
   /// 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 =
           std::max(MaxNetWidth, getNetWidth(Start, End, InitialSpaces));
       ++RowCount;
     }
     return MaxNetWidth;
   }
 

clang/lib/Format/WhitespaceManager.cpp

void WhitespaceManager::alignArrayInitializers(unsigned Start, unsigned End) {
   if (Style.AlignArrayOfStructures == FormatStyle::AIAS_Right)
     alignArrayInitializersRightJustified(getCells(Start, End));
   else if (Style.AlignArrayOfStructures == FormatStyle::AIAS_Left)
     alignArrayInitializersLeftJustified(getCells(Start, 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);
     auto CellWidth = getMaximumCellWidth(CellIter, NetWidth);
 
     if (Changes[CellIter->Index].Tok->is(tok::r_brace)) {
       // So in here we want to see if there is a brace that falls
       // on a line that was split. If so on that line we make sure that
       // the spaces in front of the brace are enough.
       Changes[CellIter->Index].NewlinesBefore = 0;
       Changes[CellIter->Index].Spaces = 0;
       for (const auto *Next = CellIter->NextColumnElement; Next != nullptr;
            Next = Next->NextColumnElement) {
         Changes[Next->Index].Spaces = 0;
         Changes[Next->Index].NewlinesBefore = 0;
       }
       // Unless the array is empty, we need the position of all the
       // immediately adjacent cells
       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)
             Changes[Next->Index].Spaces = (MaxNetWidth - ThisNetWidth);
           ++RowCount;
         }
       }
     } else {
       auto ThisWidth =
if (Changes[CellIter->Index].Tok->is(tok::r_brace)) {
         alignToStartOfCell(Next->Index, Next->EndIndex);
       }
     }
   }
 }
 
 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.
   if (Changes[CellIter->Index].NewlinesBefore == 0)
     Changes[CellIter->Index].Spaces = 0;
   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) {
       Changes[CellIter->Index].Spaces =
           MaxNetWidth - ThisNetWidth +
           (Changes[CellIter->Index].Tok->isNot(tok::r_brace) ? 1 : 0);
     }
     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);
+      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) {
         Changes[Next->Index].Spaces =
             MaxNetWidth - ThisNetWidth +
             (Changes[Next->Index].Tok->isNot(tok::r_brace) ? 1 : 0);
       }
       ++RowCount;
bool WhitespaceManager::isSplitCell(const CellDescription &Cell) {
   return false;
 }
 
 WhitespaceManager::CellDescriptions WhitespaceManager::getCells(unsigned Start,
                                                                 unsigned End) {
 
   unsigned Depth = 0;
   unsigned Cell = 0;
-  unsigned CellCount = 0;
+  SmallVector<unsigned> CellCounts;
   unsigned InitialSpaces = 0;
   unsigned InitialTokenLength = 0;
   unsigned EndSpaces = 0;
   SmallVector<CellDescription> Cells;
   const FormatToken *MatchingParen = nullptr;
   for (unsigned i = Start; i < End; ++i) {
     auto &C = Changes[i];
     if (C.Tok->is(tok::l_brace))
if (Depth == 2) {
         if (C.Tok->getNextNonComment()->isNot(tok::r_brace)) // dangling comma
           ++Cell;
       }
     } else if (Depth == 1) {
       if (C.Tok == MatchingParen) {
         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))
           NextNonComment = NextNonComment->getNextNonComment();
         auto j = i;
         while (Changes[j].Tok != NextNonComment && j < End)
           ++j;
         if (j < End && Changes[j].NewlinesBefore == 0 &&
if (C.Tok->StartsColumn) {
         HasSplit = true;
       }
       if (Changes[i].Tok != C.Tok)
         --i;
       Cells.push_back(CellDescription{i, Cell, i, HasSplit, nullptr});
     }
   }
 
-  return linkCells({Cells, CellCount, InitialSpaces});
+  return linkCells({Cells, CellCounts, InitialSpaces});
 }
 
 unsigned WhitespaceManager::calculateCellWidth(unsigned Start, unsigned End,
                                                bool WithSpaces) const {
   unsigned CellWidth = 0;
   for (auto i = Start; i < End; i++) {
     if (Changes[i].NewlinesBefore > 0)
       CellWidth = 0;

clang/unittests/Format/FormatTest.cpp

TEST_F(FormatTest, UnderstandsDigraphs) {
   verifyFormat("int arr[5] = <%%>;");
   verifyFormat("int arr<:::qualified_variable:> = {};");
   verifyFormat("int arr[::qualified_variable] = <%%>;");
   verifyFormat("%:include <header>");
   verifyFormat("%:define A x##y");
   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