From db5783685e00d5cc5cd9b0d9a44e968e5d04590b Mon Sep 17 00:00:00 2001
From: Daniel Jasper <djasper@google.com>
Date: Tue, 15 Apr 2014 08:13:47 +0000
Subject: [PATCH] clang-format: Cache results of formatting nested blocks.

This somewhat improves the performance problem reported in
llvm.org/PR18761. No other behavior changes intended.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@206258 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Format/Format.cpp | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/lib/Format/Format.cpp b/lib/Format/Format.cpp
index b4eae19d47..2be21407f0 100644
--- a/lib/Format/Format.cpp
+++ b/lib/Format/Format.cpp
@@ -721,6 +721,13 @@ public:
 
   unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
                   int AdditionalIndent = 0, bool FixBadIndentation = false) {
+    // Try to look up already computed penalty in DryRun-mode.
+    std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey{
+        &Lines, AdditionalIndent};
+    auto CacheIt = PenaltyCache.find(CacheKey);
+    if (DryRun && CacheIt != PenaltyCache.end())
+      return CacheIt->second;
+
     assert(!Lines.empty());
     unsigned Penalty = 0;
     std::vector<int> IndentForLevel;
@@ -844,6 +851,7 @@ public:
       }
       PreviousLine = *I;
     }
+    PenaltyCache[CacheKey] = Penalty;
     return Penalty;
   }
 
@@ -1149,6 +1157,12 @@ private:
   LineJoiner Joiner;
 
   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
+
+  // Cache to store the penalty of formatting a vector of AnnotatedLines
+  // starting from a specific additional offset. Improves performance if there
+  // are many nested blocks.
+  std::map<std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned>,
+           unsigned> PenaltyCache;
 };
 
 class FormatTokenLexer {
-- 
2.40.0