Index: lib/Format/Format.cpp
===================================================================
--- lib/Format/Format.cpp
+++ lib/Format/Format.cpp
@@ -1034,7 +1034,7 @@
       }
     }
 
-    return generateFixes();
+    return generateFixes(AnnotatedLines);
   }
 
 private:
@@ -1172,20 +1172,31 @@
       DeletedTokens.insert(Tok);
   }
 
-  tooling::Replacements generateFixes() {
+  tooling::Replacements
+  generateFixes(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
+    // A map from the last token of a line to the first token of the next line
+    // if it exists.
+    std::map<FormatToken *, FormatToken *> LastToNextLineFirst;
+    for (auto I = AnnotatedLines.begin(), E = std::prev(AnnotatedLines.end());
+         I != E; ++I)
+      LastToNextLineFirst[(*I)->Last] = (*std::next(I))->First;
     tooling::Replacements Fixes;
     std::vector<FormatToken *> Tokens;
     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
               std::back_inserter(Tokens));
 
+    auto NextTokenInFile = [&LastToNextLineFirst](FormatToken *Tok) {
+      return Tok->Next ? Tok->Next : LastToNextLineFirst[Tok];
+    };
     // Merge multiple continuous token deletions into one big deletion so that
     // the number of replacements can be reduced. This makes computing affected
     // ranges more efficient when we run reformat on the changed code.
+    // FIXME: delete trailing '\n' when deleting an entire line.
     unsigned Idx = 0;
     while (Idx < Tokens.size()) {
       unsigned St = Idx, End = Idx;
       while ((End + 1) < Tokens.size() &&
-             Tokens[End]->Next == Tokens[End + 1]) {
+             NextTokenInFile(Tokens[End]) == Tokens[End + 1]) {
         End++;
       }
       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
Index: unittests/Format/CleanupTest.cpp
===================================================================
--- unittests/Format/CleanupTest.cpp
+++ unittests/Format/CleanupTest.cpp
@@ -48,13 +48,13 @@
   std::string Code = "namespace A {\n"
                      "namespace B {\n"
                      "} // namespace B\n"
-                     "} // namespace A\n\n"
+                     "} // namespace A\n"
                      "namespace C {\n"
                      "namespace D { int i; }\n"
                      "inline namespace E { namespace { } }\n"
                      "}";
-  std::string Expected = "\n\n\n\n\nnamespace C {\n"
-                         "namespace D { int i; }\n   \n"
+  std::string Expected = "\nnamespace C {\n"
+                         "namespace D { int i; }\n\n"
                          "}";
   EXPECT_EQ(Expected, cleanupAroundOffsets({28, 91, 132}, Code));
 }
@@ -68,8 +68,8 @@
                      "inline namespace E { namespace { } }\n"
                      "}";
   std::string Expected = "namespace A {\n"
-                         "\n\n\nnamespace C {\n"
-                         "namespace D int i; }\n   \n"
+                         "\n\nnamespace C {\n"
+                         "namespace D int i; }\n\n"
                          "}";
   std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
   EXPECT_EQ(Expected, cleanup(Code, Ranges));
@@ -94,7 +94,7 @@
                      "} // namespace A\n"
                      "namespace C { // Yo\n"
                      "}";
-  std::string Expected = "\n\n\n\n\n\n";
+  std::string Expected = "";
   std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
   std::string Result = cleanup(Code, Ranges);
   EXPECT_EQ(Expected, Result);
@@ -111,7 +111,7 @@
                      "namespace C\n"
                      "{ // Yo\n"
                      "}\n";
-  std::string Expected = "\n\n\n\n\n\n\n\n\n\n";
+  std::string Expected = "\n";
   std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
   FormatStyle Style = getLLVMStyle();
   Style.BraceWrapping.AfterNamespace = true;
@@ -268,8 +268,8 @@
                      "inline namespace E { namespace { } }\n"
                      "}";
   std::string Expected = "namespace A {\n"
-                         "\n\n\nnamespace C {\n"
-                         "class A { A() : x(0) {} };\n   \n"
+                         "\n\nnamespace C {\n"
+                         "class A { A() : x(0) {} };\n\n"
                          "}";
   std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
   std::string Result = cleanup(Code, Ranges);