Author: Sedenion Date: 2023-07-03T11:54:33+01:00 New Revision: 899c86779440dca84085fb53a1fbba6c5aa5a3b6
URL: https://github.com/llvm/llvm-project/commit/899c86779440dca84085fb53a1fbba6c5aa5a3b6 DIFF: https://github.com/llvm/llvm-project/commit/899c86779440dca84085fb53a1fbba6c5aa5a3b6.diff LOG: [clang-format] Fixed bad performance with enabled qualifier fixer. 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. Reviewed By: MyDeveloperDay, HazardyKnusperkeks, owenpan Differential Revision: https://reviews.llvm.org/D153228 Added: Modified: clang/lib/Format/Format.cpp clang/lib/Format/QualifierAlignmentFixer.cpp clang/lib/Format/QualifierAlignmentFixer.h clang/unittests/Format/QualifierFixerTest.cpp Removed: ################################################################################ diff --git a/clang/lib/Format/Format.cpp b/clang/lib/Format/Format.cpp index 5fee5e6c261a93..fd46dfec21d8de 100644 --- a/clang/lib/Format/Format.cpp +++ b/clang/lib/Format/Format.cpp @@ -3472,21 +3472,16 @@ reformat(const FormatStyle &Style, StringRef Code, 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; @@ -3571,6 +3566,24 @@ reformat(const FormatStyle &Style, StringRef Code, } } + 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 diff --git a/clang/lib/Format/QualifierAlignmentFixer.cpp b/clang/lib/Format/QualifierAlignmentFixer.cpp index ff54fb75b3dd98..2e3b21cfda79eb 100644 --- a/clang/lib/Format/QualifierAlignmentFixer.cpp +++ b/clang/lib/Format/QualifierAlignmentFixer.cpp @@ -25,18 +25,13 @@ 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) { @@ -59,51 +54,6 @@ QualifierAlignmentFixer::QualifierAlignmentFixer( } } -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) { @@ -612,7 +562,7 @@ LeftRightQualifierAlignmentFixer::analyze( 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) { diff --git a/clang/lib/Format/QualifierAlignmentFixer.h b/clang/lib/Format/QualifierAlignmentFixer.h index 3c908316a303f6..dc6f92e86ae7c7 100644 --- a/clang/lib/Format/QualifierAlignmentFixer.h +++ b/clang/lib/Format/QualifierAlignmentFixer.h @@ -25,32 +25,13 @@ 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, + std::vector<std::string> &RightOrder, + std::vector<tok::TokenKind> &Qualifiers); class LeftRightQualifierAlignmentFixer : public TokenAnalyzer { std::string Qualifier; diff --git a/clang/unittests/Format/QualifierFixerTest.cpp b/clang/unittests/Format/QualifierFixerTest.cpp index d938308d684966..a8f38593e5c40d 100755 --- a/clang/unittests/Format/QualifierFixerTest.cpp +++ b/clang/unittests/Format/QualifierFixerTest.cpp @@ -1016,8 +1016,8 @@ TEST_F(QualifierFixerTest, PrepareLeftRightOrdering) { std::vector<std::string> Left; std::vector<std::string> Right; std::vector<tok::TokenKind> ConfiguredTokens; - QualifierAlignmentFixer::PrepareLeftRightOrdering(Style.QualifierOrder, Left, - Right, ConfiguredTokens); + prepareLeftRightOrderingForQualifierAlignmentFixer(Style.QualifierOrder, Left, + Right, ConfiguredTokens); EXPECT_EQ(Left.size(), (size_t)2); EXPECT_EQ(Right.size(), (size_t)2); @@ -1181,10 +1181,12 @@ TEST_F(QualifierFixerTest, NoOpQualifierReplacements) { 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); } _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits