[clang-format] Fixed bad performance with enabled qualifier fixer.

[Sedeniono]

Summary

This fixes github issue #57117: If the "QualifierAlignment"
option of clang-format is set to anything else but "Leave", the
"QualifierAlignmentFixer" pass gets enabled. This pass scales
quadratically with the number of preprocessor branches, i.e.
with the number of elements in TokenAnalyzer::UnwrappedLines.
The reason is that QualifierAlignmentFixer::process() generates
the UnwrappedLines, but then QualifierAlignmentFixer::analyze()
calls LeftRightQualifierAlignmentFixer::process() several times
(once for each qualifier) which again each time generates the
UnwrappedLines.

This commit gets rid of this double loop by registering the
individual LeftRightQualifierAlignmentFixer passes directly in
the top most container of passes (local variable "Passes" in
reformat()).
With this change, the original example in the github issue #57117
now takes only around 3s instead of >300s to format.

Since QualifierAlignmentFixer::analyze() got deleted, we also
no longer have the code with the NonNoOpFixes. This causes
replacements that end up not changing anything to appear in the
list of final replacements. There is a unit test to check that
this does not happen: QualifierFixerTest.NoOpQualifierReplacements.
However, it got broken at some point in time. So this commit
fixes the test. To keep the behavior that no no-op replacements
should appear from the qualifier fixer, the corresponding code
from QualifierAlignmentFixer::analyze() was moved to the top
reformat() function. Thus, is now done for every replacement
of every formatting pass. If no-op replacements are a problem
for the qualifier fixer, then it seems to be a good idea to
filter them out always.

See
https://github.com/llvm/llvm-project/issues/57117#issuecomment-1546716934
for some more details.

[HazardyKnusperkeks]

I'm shocked, astonished and in awe how small this patch is. Great work and explanation!

clang/lib/Format/Format.cpp

3475–3476

Just increase here, and add a comment that there are multiple passes added in addQualifierAlignmentFixerPasses.

I think the idea was and should be that we always store the pointers on the stack.

clang/lib/Format/QualifierAlignmentFixer.cpp

36

I think we can drop this, see my other comment.

[Sedeniono]

As suggested by HazardyKnusperkeks, increased the number of stack elements and removed the reserve(). That causes all Passes to be stored on the stack. (I counted 17 distinct possible passes, but not all of them can be active at the same time: Some are javascript and some a C++ exclusive.)

[Sedeniono]

clang/lib/Format/Format.cpp

3475–3476

Ok, done.

[HazardyKnusperkeks]

Please wait for at least @MyDeveloperDay to say something, as he is the original author of the work.

clang/lib/Format/Format.cpp

3475–3476

You don't need to comment done. But please check the "Done" on my comment. :)

[owenpan]

clang/lib/Format/Format.cpp

3476–3477

This comment is unnecessary and too verbose IMO. I suggest that it be deleted.

3587–3588

You only need this for the QualifierAlignment passes as others (e.g. IntegerLiteralSeparatorFixer) already skip no-op replacements.

clang/lib/Format/QualifierAlignmentFixer.cpp

29

Ditto.

clang/lib/Format/QualifierAlignmentFixer.h

29

See https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h.

[MyDeveloperDay]

Thank you for the detailed analysis

[Sedeniono]

clang/lib/Format/Format.cpp

3587–3588

Yes, in principle I need to do this only after all QualifierAlignment passes ran. The key point is that it needs to be done only after all QualifierAlignment passes ran. In other words, I cannot move this to LeftRightQualifierAlignmentFixer::analyze(); it would do nothing there. The non-no-op code exists so that if e.g. const volatile becomes volatile const in one pass and then again const volatile in another pass, we end up with no replacements.

I also cannot simply put all the QualifierAlignment passes into a simple dedicated loop that directly runs them after one another; the part with applyAllReplacements() etc (line 3554 till 3566 above) would be missing between the passes. I could, of course, extract lines 3554 till 3566 into a new function and call it in both places. Should I do that?

Or do you mean that I should wrap the NonNoOpFixes code in an if (Style.QualifierAlignment != FormatStyle::QAS_Leave)?

[HazardyKnusperkeks]

clang/lib/Format/Format.cpp

3476–3477

This comment is unnecessary and too verbose IMO. I suggest that it be deleted.

I think one should note that there are more passes added than directly meets the eye here.

[owenpan]

clang/lib/Format/Format.cpp

3587–3588

Or do you mean that I should wrap the NonNoOpFixes code in an if (Style.QualifierAlignment != FormatStyle::QAS_Leave)?

I was thinking about something like that at the minimum.

[Sedeniono]

As suggested by the reviewers, the noop fixes are now filtered only if the qualifier alignment passes are active. Also implemented the other minor refactorings.

[Sedeniono]

clang/lib/Format/Format.cpp

3476–3477

After looking at the code again, I decided to remove the comment. I think the "structure" of the code below that adds the passes already highlights that there is something "special" going on with the qualifier alignment passes, since they aren't added via a lambda.

[MyDeveloperDay]

For us to land this for you we'll need your name and email

[Sedeniono]

In D153228#4446523, @MyDeveloperDay wrote:

For us to land this for you we'll need your name and email

Please use: Sedenion <[e-mail]>
Thanks!

clang/lib/Format/Format.cpp

reformat(const FormatStyle &Style, StringRef Code,
   auto Env = Environment::make(Code, FileName, Ranges, FirstStartColumn,
                                NextStartColumn, LastStartColumn);
   if (!Env)
     return {};
 
   typedef std::function<std::pair<tooling::Replacements, unsigned>(
       const Environment &)>
       AnalyzerPass;
-  SmallVector<AnalyzerPass, 8> Passes;
+
+  SmallVector<AnalyzerPass, 16> Passes;
 
   Passes.emplace_back([&](const Environment &Env) {
     return IntegerLiteralSeparatorFixer().process(Env, Expanded);
   });
 
   if (Style.isCpp()) {
-    if (Style.QualifierAlignment != FormatStyle::QAS_Leave) {
-      Passes.emplace_back([&](const Environment &Env) {
-        return QualifierAlignmentFixer(Env, Expanded, Code, Ranges,
-                                       FirstStartColumn, NextStartColumn,
-                                       LastStartColumn, FileName)
-            .process();
-      });
-    }
+    if (Style.QualifierAlignment != FormatStyle::QAS_Leave)
+      addQualifierAlignmentFixerPasses(Expanded, Passes);
 
     if (Style.InsertBraces) {
       FormatStyle S = Expanded;
       S.InsertBraces = true;
       Passes.emplace_back([&, S = std::move(S)](const Environment &Env) {
         return BracesInserter(Env, S).process(/*SkipAnnotation=*/true);
       });
     }
if (NewCode) {
             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
             FirstStartColumn, NextStartColumn, LastStartColumn);
         if (!Env)
           return {};
       }
     }
   }
 
+  if (Style.QualifierAlignment != FormatStyle::QAS_Leave) {
+    // Don't make replacements that replace nothing. QualifierAlignment can
+    // produce them if one of its early passes changes e.g. `const volatile` to
+    // `volatile const` and then a later pass changes it back again.
+    tooling::Replacements NonNoOpFixes;
+    for (const tooling::Replacement &Fix : Fixes) {
+      StringRef OriginalCode = Code.substr(Fix.getOffset(), Fix.getLength());
+      if (!OriginalCode.equals(Fix.getReplacementText())) {
+        auto Err = NonNoOpFixes.add(Fix);
+        if (Err) {
+          llvm::errs() << "Error adding replacements : "
+                       << llvm::toString(std::move(Err)) << "\n";
+        }
+      }
+    }
+    Fixes = std::move(NonNoOpFixes);
+  }
+
   return {Fixes, Penalty};
 }
 } // namespace internal
 
 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
                                ArrayRef<tooling::Range> Ranges,
                                StringRef FileName,
                                FormattingAttemptStatus *Status) {
   return internal::reformat(Style, Code, Ranges,
                             /*FirstStartColumn=*/0,

clang/lib/Format/QualifierAlignmentFixer.h

 
 namespace clang {
 namespace format {
 
 typedef std::function<std::pair<tooling::Replacements, unsigned>(
     const Environment &)>
     AnalyzerPass;
 
-class QualifierAlignmentFixer : public TokenAnalyzer {
-  // Left to Right ordering requires multiple passes
-  SmallVector<AnalyzerPass, 8> Passes;
-  StringRef &Code;
-  ArrayRef<tooling::Range> Ranges;
-  unsigned FirstStartColumn;
-  unsigned NextStartColumn;
-  unsigned LastStartColumn;
-  StringRef FileName;
+void addQualifierAlignmentFixerPasses(const FormatStyle &Style,
+                                      SmallVectorImpl<AnalyzerPass> &Passes);
 
-public:
-  QualifierAlignmentFixer(const Environment &Env, const FormatStyle &Style,
-                          StringRef &Code, ArrayRef<tooling::Range> Ranges,
-                          unsigned FirstStartColumn, unsigned NextStartColumn,
-                          unsigned LastStartColumn, StringRef FileName);
-
-  std::pair<tooling::Replacements, unsigned>
-  analyze(TokenAnnotator &Annotator,
-          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
-          FormatTokenLexer &Tokens) override;
-
-  static void PrepareLeftRightOrdering(const std::vector<std::string> &Order,
-                                       std::vector<std::string> &LeftOrder,
-                                       std::vector<std::string> &RightOrder,
-                                       std::vector<tok::TokenKind> &Qualifiers);
-};
+void prepareLeftRightOrderingForQualifierAlignmentFixer(
+    const std::vector<std::string> &Order, std::vector<std::string> &LeftOrder,
 
 class LeftRightQualifierAlignmentFixer : public TokenAnalyzer {
   std::string Qualifier;
   bool RightAlign;
   SmallVector<tok::TokenKind, 8> QualifierTokens;
   std::vector<tok::TokenKind> ConfiguredQualifierTokens;
 
 public:

clang/lib/Format/QualifierAlignmentFixer.cpp

 #include <algorithm>
 #include <optional>
 
 #define DEBUG_TYPE "format-qualifier-alignment-fixer"
 
 namespace clang {
 namespace format {
 
-QualifierAlignmentFixer::QualifierAlignmentFixer(
-    const Environment &Env, const FormatStyle &Style, StringRef &Code,
-    ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
-    unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName)
-    : TokenAnalyzer(Env, Style), Code(Code), Ranges(Ranges),
-      FirstStartColumn(FirstStartColumn), NextStartColumn(NextStartColumn),
-      LastStartColumn(LastStartColumn), FileName(FileName) {
+void addQualifierAlignmentFixerPasses(const FormatStyle &Style,
+                                      SmallVectorImpl<AnalyzerPass> &Passes) {
   std::vector<std::string> LeftOrder;
   std::vector<std::string> RightOrder;
   std::vector<tok::TokenKind> ConfiguredQualifierTokens;
-  PrepareLeftRightOrdering(Style.QualifierOrder, LeftOrder, RightOrder,
-                           ConfiguredQualifierTokens);
+  prepareLeftRightOrderingForQualifierAlignmentFixer(
+      Style.QualifierOrder, LeftOrder, RightOrder, ConfiguredQualifierTokens);
 
   // Handle the left and right alignment separately.
   for (const auto &Qualifier : LeftOrder) {
     Passes.emplace_back(
         [&, Qualifier, ConfiguredQualifierTokens](const Environment &Env) {
           return LeftRightQualifierAlignmentFixer(Env, Style, Qualifier,
                                                   ConfiguredQualifierTokens,
                                                   /*RightAlign=*/false)
               .process();
         });
   }
   for (const auto &Qualifier : RightOrder) {
     Passes.emplace_back(
         [&, Qualifier, ConfiguredQualifierTokens](const Environment &Env) {
           return LeftRightQualifierAlignmentFixer(Env, Style, Qualifier,
                                                   ConfiguredQualifierTokens,
                                                   /*RightAlign=*/true)
               .process();
         });
   }
 }
 
-std::pair<tooling::Replacements, unsigned> QualifierAlignmentFixer::analyze(
-    TokenAnnotator & /*Annotator*/,
-    SmallVectorImpl<AnnotatedLine *> & /*AnnotatedLines*/,
-    FormatTokenLexer & /*Tokens*/) {
-  auto Env = Environment::make(Code, FileName, Ranges, FirstStartColumn,
-                               NextStartColumn, LastStartColumn);
-  if (!Env)
-    return {};
-  std::optional<std::string> CurrentCode;
-  tooling::Replacements Fixes;
-  for (size_t I = 0, E = Passes.size(); I < E; ++I) {
-    std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
-    auto NewCode = applyAllReplacements(
-        CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
-    if (NewCode) {
-      Fixes = Fixes.merge(PassFixes.first);
-      if (I + 1 < E) {
-        CurrentCode = std::move(*NewCode);
-        Env = Environment::make(
-            *CurrentCode, FileName,
-            tooling::calculateRangesAfterReplacements(Fixes, Ranges),
-            FirstStartColumn, NextStartColumn, LastStartColumn);
-        if (!Env)
-          return {};
-      }
-    }
-  }
-
-  // Don't make replacements that replace nothing.
-  tooling::Replacements NonNoOpFixes;
-
-  for (const tooling::Replacement &Fix : Fixes) {
-    StringRef OriginalCode = Code.substr(Fix.getOffset(), Fix.getLength());
-
-    if (!OriginalCode.equals(Fix.getReplacementText())) {
-      auto Err = NonNoOpFixes.add(Fix);
-      if (Err) {
-        llvm::errs() << "Error adding replacements : "
-                     << llvm::toString(std::move(Err)) << "\n";
-      }
-    }
-  }
-  return {NonNoOpFixes, 0};
-}
-
 static void replaceToken(const SourceManager &SourceMgr,
                          tooling::Replacements &Fixes,
                          const CharSourceRange &Range, std::string NewText) {
   auto Replacement = tooling::Replacement(SourceMgr, Range, NewText);
   auto Err = Fixes.add(Replacement);
 
   if (Err) {
     llvm::errs() << "Error while rearranging Qualifier : "
for (const auto *Tok = First; Tok && Tok != Last && Tok->Next;
         Tok = analyzeLeft(SourceMgr, Keywords, Fixes, Tok, Qualifier,
                           QualifierToken);
       }
     }
   }
   return {Fixes, 0};
 }
 
-void QualifierAlignmentFixer::PrepareLeftRightOrdering(
+void prepareLeftRightOrderingForQualifierAlignmentFixer(
     const std::vector<std::string> &Order, std::vector<std::string> &LeftOrder,
     std::vector<std::string> &RightOrder,
     std::vector<tok::TokenKind> &Qualifiers) {
 
   // Depending on the position of type in the order you need
   // To iterate forward or backward through the order list as qualifier
   // can push through each other.
   // The Order list must define the position of "type" to signify

clang/unittests/Format/QualifierFixerTest.cpp

 TEST_F(QualifierFixerTest, PrepareLeftRightOrdering) {
   FormatStyle Style = getLLVMStyle();
   Style.QualifierAlignment = FormatStyle::QAS_Custom;
   Style.QualifierOrder = {"static", "inline", "type", "const", "volatile"};
 
   std::vector<std::string> Left;
   std::vector<std::string> Right;
   std::vector<tok::TokenKind> ConfiguredTokens;
-  QualifierAlignmentFixer::PrepareLeftRightOrdering(Style.QualifierOrder, Left,
+  prepareLeftRightOrderingForQualifierAlignmentFixer(Style.QualifierOrder, Left,
                                                      Right, ConfiguredTokens);
 
   EXPECT_EQ(Left.size(), (size_t)2);
   EXPECT_EQ(Right.size(), (size_t)2);
 
   std::vector<std::string> LeftResult = {"inline", "static"};
   std::vector<std::string> RightResult = {"const", "volatile"};
   EXPECT_EQ(Left, LeftResult);
   EXPECT_EQ(Right, RightResult);

 }
 
 TEST_F(QualifierFixerTest, NoOpQualifierReplacements) {
 
   FormatStyle Style = getLLVMStyle();
   Style.QualifierAlignment = FormatStyle::QAS_Custom;
   Style.QualifierOrder = {"static", "const", "type"};
 
-  ReplacementCount = 0;
-  EXPECT_EQ(ReplacementCount, 0);
   verifyFormat("static const uint32 foo[] = {0, 31};", Style);
+  EXPECT_EQ(ReplacementCount, 0);
+
   verifyFormat("#define MACRO static const", Style);
+  EXPECT_EQ(ReplacementCount, 0);
+
   verifyFormat("using sc = static const", Style);
   EXPECT_EQ(ReplacementCount, 0);
 }
 
 TEST_F(QualifierFixerTest, QualifierTemplates) {
   FormatStyle Style = getLLVMStyle();
   Style.QualifierAlignment = FormatStyle::QAS_Custom;
   Style.QualifierOrder = {"static", "const", "type"};