[clang-format] Fix multiple preprocessor if sections parsing incorrectly

[sstwcw]

Summary

In 2183fe2 I didn't notice that PPLevelBranchIndex was common to the
entire file. The commit caused problems when there are multiple
preprocessor if sections. Using a single PPLevelBranchIndex also
brings the problem that the extra branches in an if section with more
branches than other sections are parsed without other sections.

This patch fixes the problem by storing the structure of the
preprocessor if sections. This way, PPLevelBranchIndex is checked
against the stored structure, and if a nonexistent branch is called for
because another section has more branches, the first or second branch
will be parsed. The change in 2183fe2 setting PPLevelBranchIndex is
reverted. Instead the stored branch structure is used to determine when
the second branch should be parsed instead of the first.

The logic for determining when a branch is skipped in moved from
conditionalCompilationStart and conditionalCompilationAlternative
into conditionalCompilationCondition because the two cases now have
more overlap. PPChainbranchIndex is changed to include the section
number in addition to the branch number.

Fixes https://github.com/llvm/llvm-project/issues/58188

[sstwcw]

Should I add a test with comments to be aligned like in the bug report? I was not sure because I didn't find an existing test for alignment of comments.

[HazardyKnusperkeks]

In D135740#3851405, @sstwcw wrote:

Should I add a test with comments to be aligned like in the bug report? I was not sure because I didn't find an existing test for alignment of comments.

Yes you should.

[MyDeveloperDay]

Did you test this with nested #if #endif?

[sstwcw]

• add tests

[sstwcw]

In D135740#3858782, @MyDeveloperDay wrote:

Did you test this with nested #if #endif?

No. I added the tests now.

[sstwcw]

• correct spelling

[sstwcw]

• Merge
• use ArrayRef

[HazardyKnusperkeks]

I'm lost at this topic. Is this change still needed? Is it superseded by or additional to D137052?

[sstwcw]

It does some more than D137052. But the additional stuff is not very important and no one can review it. So I am closing it.

clang/lib/Format/UnwrappedLineParser.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEPARSER_H
 #define LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEPARSER_H
 
 #include "FormatToken.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Format/Format.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/Support/Regex.h"
 #include <list>
 #include <stack>
 #include <vector>
 
 namespace clang {
 namespace format {
private:
 
   // Contains the current branch (#if, #else or one of the #elif branches)
   // for each nesting level.
   SmallVector<int, 8> PPLevelBranchIndex;
 
   // Contains the maximum number of branches at each nesting level.
   SmallVector<int, 8> PPLevelBranchCount;
 
-  // Contains the number of branches per nesting level we are currently
-  // in while parsing a preprocessor branch sequence.
+  // Contains the indices of the current if-section and branch in that section
+  // we are currently in while parsing a preprocessor branch sequence, with one
+  // entry per nesting level.
   // This is used to update PPLevelBranchCount at the end of a branch
   // sequence.
-  std::stack<int> PPChainBranchIndex;
+  // For example:
+  //   PPSectionsTop = 0
+  //   PPChainBranchIndex = []
+  //   #if 0
+  //     PPSectionsTop = 0 -- It gets reset to 0 when a new level is entered.
+  //     PPChainBranchIndex = [{Section: 0, Branch: 0}]
+  //   #elif 1
+  //     PPSectionsTop = 0
+  //     PPChainBranchIndex = [{Section: 0, Branch: 1}]
+  //   #endif
+  //   PPSectionsTop = 1
+  //   PPChainBranchindex = []
+  //   #if 2
+  //     PPSectionsTop = 0
+  //     PPChainBranchIndex = [{Section: 1, Branch: 0}]
+  //     #if 3
+  //       PPSectionsTop = 0
+  //       PPChainBranchIndex = [{Section: 1, Branch: 0},
+  //                             {Section: 0, Branch: 0}]
+  //     #endif
+  //     PPSectionsTop = 1 -- It gets incremented when a section ends.
+  //     PPChainBranchIndex = [{Section: 1, Branch: 0}]
+  //   #endif
+  //   PPSectionsTop = 2
+  //   PPChainBranchIndex = []
+  // After parsing all this, PPBranchStructure is:
+  // {
+  //   Unreachable: true
+  //   Sections: [
+  //     [
+  //       {Unreachable: false, Sections: []},
+  //       {Unreachable: false, Sections: []}
+  //     ],
+  //     [
+  //       {
+  //         Unreachable: false,
+  //         Sections: [[{Unreachable: false, Sections: []}]]
+  //       }
+  //     ]
+  //   ]
+  // }
+  struct PPSectionGroupId {
+    int Section;
+    int Branch;
+  };
+  SmallVector<PPSectionGroupId> PPChainBranchIndex;
+
+  // The number of sections seen at the current level.
+  int PPSectionsCurrent;
+
+  // The structure of the #if branches.  'Sections' contains one entry for each
+  // section between #if and #endif regardless of how many #elsif there are in
+  // between.  For each of the sections, there is one entry for each branch.
+  struct PPBranchStructureT {
+    std::vector<std::vector<PPBranchStructureT>> Sections;
+    bool Unreachable = false;
+  } PPBranchStructure;
+
+  // Update the saved branch structure based on the current number of branches
+  // seen.  Returns the structure addressed by the indices.
+  PPBranchStructureT *findPPBranchStructure(PPBranchStructureT *Structure,
+                                            ArrayRef<PPSectionGroupId> Indices);
 
   // Include guard search state. Used to fixup preprocessor indent levels
   // so that include guards do not participate in indentation.
   enum IncludeGuardState {
     IG_Inited,   // Search started, looking for #ifndef.
     IG_IfNdefed, // #ifndef found, IncludeGuardToken points to condition.
     IG_Defined,  // Matching #define found, checking other requirements.
     IG_Found,    // All requirements met, need to fix indents.

clang/lib/Format/UnwrappedLineParser.cpp

void UnwrappedLineParser::reset() {
   FormatTok = nullptr;
   MustBreakBeforeNextToken = false;
   PreprocessorDirectives.clear();
   CurrentLines = &Lines;
   DeclarationScopeStack.clear();
   NestedTooDeep.clear();
   PPStack.clear();
   Line->FirstStartColumn = FirstStartColumn;
+  PPSectionsCurrent = 0;
 }
 
 void UnwrappedLineParser::parse() {
   IndexedTokenSource TokenSource(AllTokens);
   Line->FirstStartColumn = FirstStartColumn;
   do {
     LLVM_DEBUG(llvm::dbgs() << "----\n");
     reset();
case tok::pp_endif:
     break;
   default:
     parsePPUnknown();
     break;
   }
 }
 
 void UnwrappedLineParser::conditionalCompilationCondition(bool Unreachable) {
+  bool Skip;
+  if (PPChainBranchIndex.empty()) {
+    // This condition occurs when there is an #elif without an #if.
+    Skip = false;
+  } else {
+    assert(PPBranchLevel >= 0);
+    const auto &CurrentIndex = PPChainBranchIndex.back();
+    PPBranchStructureT *Structure = findPPBranchStructure(
+        &PPBranchStructure, makeArrayRef(PPChainBranchIndex).drop_back());
+    findPPBranchStructure(Structure,
+                          ArrayRef<PPSectionGroupId>(PPChainBranchIndex.back()))
+        ->Unreachable = Unreachable;
+    // The default branch to be parsed when PPLevelBranchIndex calls for a
+    // nonexistent branch is the first branch when it is reachable, otherwise
+    // the second branch.
+    bool IsDefaultBranch =
+        CurrentIndex.Branch == 0 ||
+        (CurrentIndex.Branch == 1 &&
+         Structure->Sections[CurrentIndex.Section][0].Unreachable);
+    if (PPLevelBranchIndex[PPBranchLevel] == CurrentIndex.Branch) {
+      // The branch is parsed when called for.
+      Skip = false;
+    } else if (IsDefaultBranch && PPLevelBranchIndex[PPBranchLevel] == 0) {
+      // When the branch called for is the first one, but it is unreachable, the
+      // second one is parsed.
+      Skip = false;
+    } else if (IsDefaultBranch &&
+               PPLevelBranchIndex[PPBranchLevel] >=
+                   static_cast<ptrdiff_t>(
+                       Structure->Sections[CurrentIndex.Section].size())) {
+      // When the branch called for doesn't exist, the default branch is parsed.
+      Skip = false;
+    } else {
+      Skip = true;
+    }
+  }
+
   size_t Line = CurrentLines->size();
   if (CurrentLines == &PreprocessorDirectives)
     Line += Lines.size();
 
-  if (Unreachable ||
+  if (Unreachable || Skip ||
       (!PPStack.empty() && PPStack.back().Kind == PP_Unreachable)) {
     PPStack.push_back({PP_Unreachable, Line});
   } else {
     PPStack.push_back({PP_Conditional, Line});
   }
 }
 
 void UnwrappedLineParser::conditionalCompilationStart(bool Unreachable) {
   ++PPBranchLevel;
   assert(PPBranchLevel >= 0 && PPBranchLevel <= (int)PPLevelBranchIndex.size());
   if (PPBranchLevel == (int)PPLevelBranchIndex.size()) {
-    // If the first branch is unreachable, set the BranchIndex to 1.  This way
-    // the next branch will be parsed if there is one.
-    PPLevelBranchIndex.push_back(Unreachable ? 1 : 0);
+    PPLevelBranchIndex.push_back(0);
     PPLevelBranchCount.push_back(0);
   }
-  PPChainBranchIndex.push(0);
-  bool Skip = PPLevelBranchIndex[PPBranchLevel] > 0;
-  conditionalCompilationCondition(Unreachable || Skip);
+  PPChainBranchIndex.push_back({/*Section=*/PPSectionsCurrent, /*Branch=*/0});
+  PPSectionsCurrent = 0;
+  conditionalCompilationCondition(Unreachable);
 }
 
 void UnwrappedLineParser::conditionalCompilationAlternative() {
   if (!PPStack.empty())
     PPStack.pop_back();
   assert(PPBranchLevel < (int)PPLevelBranchIndex.size());
   if (!PPChainBranchIndex.empty())
-    ++PPChainBranchIndex.top();
-  conditionalCompilationCondition(
-      PPBranchLevel >= 0 && !PPChainBranchIndex.empty() &&
-      PPLevelBranchIndex[PPBranchLevel] != PPChainBranchIndex.top());
+    ++PPChainBranchIndex.back().Branch;
+  conditionalCompilationCondition(/*Unreachable=*/false);
 }
 
 void UnwrappedLineParser::conditionalCompilationEnd() {
   assert(PPBranchLevel < (int)PPLevelBranchIndex.size());
   if (PPBranchLevel >= 0 && !PPChainBranchIndex.empty()) {
-    if (PPChainBranchIndex.top() + 1 > PPLevelBranchCount[PPBranchLevel])
-      PPLevelBranchCount[PPBranchLevel] = PPChainBranchIndex.top() + 1;
+    if (PPChainBranchIndex.back().Branch + 1 >
+        PPLevelBranchCount[PPBranchLevel]) {
+      PPLevelBranchCount[PPBranchLevel] = PPChainBranchIndex.back().Branch + 1;
+    }
   }
   // Guard against #endif's without #if.
   if (PPBranchLevel > -1)
     --PPBranchLevel;
-  if (!PPChainBranchIndex.empty())
-    PPChainBranchIndex.pop();
+  if (PPChainBranchIndex.empty()) {
+    PPSectionsCurrent = 0;
+  } else {
+    PPSectionsCurrent = PPChainBranchIndex.back().Section + 1;
+    PPChainBranchIndex.pop_back();
+  }
   if (!PPStack.empty())
     PPStack.pop_back();
 }
 
+UnwrappedLineParser::PPBranchStructureT *
+UnwrappedLineParser::findPPBranchStructure(PPBranchStructureT *Structure,
+                                           ArrayRef<PPSectionGroupId> Indices) {
+  if (Indices.empty())
+    return Structure;
+  if (Indices[0].Section >= static_cast<ptrdiff_t>(Structure->Sections.size()))
+    Structure->Sections.resize(Indices[0].Section + 1);
+  if (Indices[0].Branch >=
+      static_cast<ptrdiff_t>(Structure->Sections[Indices[0].Section].size())) {
+    Structure->Sections[Indices[0].Section].resize(Indices[0].Branch + 1);
+  }
+  return findPPBranchStructure(
+      &Structure->Sections[Indices[0].Section][Indices[0].Branch],
+      Indices.drop_front());
+}
+
 void UnwrappedLineParser::parsePPIf(bool IfDef) {
   bool IfNDef = FormatTok->is(tok::pp_ifndef);
   nextToken();
   bool Unreachable = false;
   if (!IfDef && (FormatTok->is(tok::kw_false) || FormatTok->TokenText == "0"))
     Unreachable = true;
   if (IfDef && !IfNDef && FormatTok->TokenText == "SWIG")
     Unreachable = true;

clang/unittests/Format/FormatTest.cpp

TEST_F(FormatTest, LayoutStatementsAroundPreprocessorDirectives) {
   // `#else`.
   verifyFormat("#if 0\n"
                "{\n"
                "#else\n"
                "{\n"
                "#endif\n"
                "  x;\n"
                "}");
+  // Verify that an `#if 0` at the start of a file doesn't affect other parts of
+  // the file.
+  verifyFormat("#if 0\n"
+               "#endif\n"
+               "#if X\n"
+               "int something_fairly_long;\n"
+               "if (1) {\n"
+               "  int something_fairly_long;\n"
+               "}\n"
+               "#endif\n");
+  // When sections have different numbers of branches, the extra branches should
+  // be parsed along with the first branches of the sections that have fewer
+  // branches if the condition of those first branches are not 0.
+  verifyFormat("#if 1\n"
+               "{\n"
+               "#endif\n"
+               "#if X\n"
+               "  x;\n"
+               "#else\n"
+               "  x;\n"
+               "#endif\n"
+               "}");
+  // When the condition is 0, the default branch is the second branch.
+  verifyFormat("#if 0\n"
+               "#elif 1\n"
+               "{\n"
+               "#endif\n"
+               "#if X\n"
+               "  x;\n"
+               "#elif X\n"
+               "  x;\n"
+               "#else\n"
+               "  x;\n"
+               "#endif");
+  // Nested.
+  verifyFormat("#if X\n"
+               "#if X\n"
+               "#if X\n"
+               "{\n"
+               "#endif\n"
+               "  x;\n"
+               "#endif\n"
+               "  x;\n"
+               "#endif\n"
+               "#if X\n"
+               "  x;\n"
+               "#else\n"
+               "  x;\n"
+               "#endif\n"
+               "}");
+  verifyFormat("#if X\n"
+               "#if X\n"
+               "#if X\n"
+               "{\n"
+               "#endif\n"
+               "#endif\n"
+               "#endif\n"
+               "#if X\n"
+               "#if X\n"
+               "#if X\n"
+               "  x;\n"
+               "#else\n"
+               "  x;\n"
+               "#endif\n"
+               "#endif\n"
+               "#endif\n"
+               "}");
 }
 
 TEST_F(FormatTest, GraciouslyHandleIncorrectPreprocessorConditions) {
   verifyFormat("#endif\n"
                "#if B");
 }
 
 TEST_F(FormatTest, FormatsJoinedLinesOnSubsequentRuns) {
verifyFormat("void foo4(void) {\n"
                "  A    B       = {.one_foooooooooooooooo = 2,\n"
                "                  .two_fooooooooooooo    = 3,\n"
                "                  .three_fooooooooooooo  = 4};\n"
                "  BYTE payload = 2;\n"
                "}",
                Style);
 }
 
+TEST_F(FormatTest, AlignComments) {
+  verifyFormat("int a;    // Do\n"
+               "double b; // align comments.");
+
+  FormatStyle Style = getLLVMStyle();
+  Style.AlignTrailingComments = false;
+  verifyFormat("int a; // Do not\n"
+               "double b; // align comments.",
+               Style);
+
+  // #58188 `#if 0` should not cause problems.
+  verifyFormat("#if X\n"
+               "int something_fairly_long; // Align here please\n"
+               "#endif                     // Should be aligned");
+  verifyFormat("#if 0\n"
+               "#endif\n"
+               "#if X\n"
+               "int something_fairly_long; // Align here please\n"
+               "#endif                     // Should be aligned");
+}
+
 TEST_F(FormatTest, LinuxBraceBreaking) {
   FormatStyle LinuxBraceStyle = getLLVMStyle();
   LinuxBraceStyle.BreakBeforeBraces = FormatStyle::BS_Linux;
   verifyFormat("namespace a\n"
                "{\n"
                "class A\n"
                "{\n"
                "  void f()\n"