Added Fixer implementation and fix() interface in clang-format for removing redundant code.

[ioeric]

Summary

After applying replacements, redundant code like extra commas or empty namespaces
might be introduced. Fixer can detect and remove any redundant code introduced by replacements.
The current implementation only handles redundant commas.

[ioeric]

include/clang/Format/Format.h

803

I am adding reformatting after fixing, and I am wondering if we can get rid of the Style parameter here (since the style does not really matter in code fixing, I think?) and let the reformat handling the style with the use case like:

FinalReplaces = formatReplacements(Code, fixReplacements(Code, Replaces), Style);

where fixReplacements is a function parallel to formatReplacements.

[ioeric]

• Added fixReplacements() that fix and reformat replacements.

[ioeric]

• Added fix for empty namespace.
• Merge multiple continuous token deletions into one big replacement; minor code styling.
• refactored code to reduce redundancy.

[djasper]

include/clang/Format/Format.h

770

I think we should not automatically format the replacements after fixing. This function can easily be combined with formatReplacements if that is desired.

802

This sentence doesn't make sense.

803

I believe the style will become important as certain aspects of fixing are going to be controlled via the style. E.g. some styles might want to turn:

if (a)
  return;

into:

if (a) {
  return;
}

lib/Format/Format.cpp

1446

I'd probably move all of these out into a class so you don't need to pass the same set of parameters between all of them and so that you can make those private that aren't meant to be called directly.

1596

I am not sure, this is the right class to pull out. It still has a lot of overlap with formatter. Maybe it is instead a better idea to pull out each fixer into its own class and pull them into the formatter.

1651

The Tokens parameter is unused!?

1654

I am not (yet) convinced that the fundamental design here makes sense. So far it seems to me that all fixers will either operate within a single line (ctor fixer and probably most others) or that they do something specific on multiple lines (namespace fixer and empty public/private section fixer and maybe others). Creating a new way to iterate over all tokens of all lines doesn't really add useful functionality here AFAICT.

1657

No braces. Here and at all other single-statement ifs.

1690

Having a function called "reset" that is only called once is weird. Just do this in the constructor?

1748

Comment on what this is doing.

1749

Ed? Either use E or End.

1891

Why is this needed?

1909

A lot of these need documentation. What's the current line? What is the last token (last token that was read? last token of line? last token of file?). What are RedundantTokens?

2385

Too much code duplication. Find a way to avoid that (passing in the calls to either reformat() or fix() as lambdas to a shared internal function).

unittests/Format/FormatTest.cpp

11236

All of this should go into a different file.

[ioeric]

• Refactored the code to reduce code duplication. Code styling. Moved test cases for Fixer into a new file FixTest.cpp.
• Added RangeManager to manage affected ranges. make empty namespace fixer delete tokens not in an affected line.

lib/Format/Format.cpp

1596

But I'm not quite sure if implementing the fixer in formatter works better since they look like two parallel classes to me. And it might make the formatter more complicated to use if we mix it with fixer. I think adding another layer of abstraction might be one way to reduce duplication?

1654

I've also considered the way formatter does, which iterates over lines. But it seems to be easier to write fixer, especially multi-line fixer, if we can just ignore lines. Working with lines seems to add another layer of complexity here?

[djasper]

lib/Format/Format.cpp

1654

That I don't understand. Almost all fixers (cleaning up commas, constructor initializers, etc.) will only ever look at a single line.

The matchers that do make multiline fixes (empty namespaces, empty public/private sections) only look at complete lines, i.e. only ever use AnnotatedLine::startsWith(...) and don't iterate over the tokens, AFAICT.

I really think that giving the option to iterate over all tokens of multiple lines does more harm than good. Among several other things, error recovery is made harder. It never makes sense for the ctor-initializer fixer to leave its line (or else you'll just ignore some nice error recovery already implemented in the UnwrappedLineParser).

1693

I have a comment here (and in some other places), but I think this will be different anyway if we move to line-based fixers. So I am holding off with those comments for now.

1718

Just go to CurrentToken->MatchingParen!?

1824

I am happy to show you how the implementation here gets much simpler if you only iterate over AnnotatedLines.

1916

I think "redundant" is the wrong word here. How about DeletedTokens?

[ioeric]

• Change implementation of fixer to iterate by lines. TODO: refactor Formatter and Fixer to reduce duplication.

[djasper]

include/clang/Format/Format.h

769

I am actually not sure that fixReplacements is the right terminology here (sorry that I haven't discovered this earlier). It isn't really fixing the replacements (they aren't necessarily broken). How about cleanupAroundReplacements? Manuel, what do you think?

lib/Format/Format.cpp

1596

But like this, it is way to much code duplication for me, both in number of lines of code as well as code complexity. Basically everything in fix() is duplicated along with most of the class members etc. The main difference seems to be that runFix() is called instead of format. There must be a way to have only one implementation of that code.

I think (but cannot see all the consequences yet) you should merge the two classes. And if that leads to too much complexity, you can probably pull out runFix and everything it calls into a separate class as well as possibly format() and everything that format calls.

1597

Why are you doing this?

1664

Can you move the ConstructorInitializer fixer and everything that belongs to it to a different patch? I want to look at that in more detail and two smaller patches make this easier for me.

1672

No need for this boolean. Write this as:

for (FormatToken *Tok = Line.First;; Tok = Tok->Next) {
  if (!Tok->is(tok::comment))
    return false;
}
return true;

And maybe we should (in a separate patch) add an iterator interface to AnnotatedLine so that we can use range-based for loops.

1695

Why not return -1 here?

1699

Move the startsWith into containsOnlyComments.

1701

I'd write this in a very different order:

if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
  break;
if (AnnotatedLines[CurrentLine]->startsWith(kw_namespaces) || ..) {
  int NewLine = checkEmptyNamespace(CurrentLine);
  if (NewLine == -1)
    return -1;
  continue;
if (!containsOnlyComments(..))
  return -1;

1702

It's a bit subtle that this works correctly. At least I needed to think quickly why you wouldn't falsely run into this in

namespace N {
void f() {
}
}

But of course, then the namespace wouldn't be empty. Please leave a comment explaining this briefly.

1717

Hm, this seems very inelegant. If you have:

namespace A {
namespace B {
namespace C {
}
}
}

"namespace C {" and "}" gets delete three times. At the very least you should add

if (AnnotatedLines[i]->Deleted)
  continue;

Thinking about this some more, it will get deleted even more often has even the outer loop in runFix will call checkEmptyNamespace again for the inner namespaces even though they have been deleted already. So inner namespaces will bei deleted O(N^2) times if N is the nesting depth. Lets get that down to 1 instead ;-)

1818

Can you explain why you are doing this?

2340

Don't define a typedef for something that is only used once. Also, this is an internal function, how about writing this as:

template <typename T>
static tooling::Replacements
processReplacements(StringRef Code, const tooling::Replacements &Replaces, T ProcessFunc,
                    const FormatStyle &Style) {

}

No need to spell out the function type (I think).

[ioeric]

• Moved constructor initializer fixer to a separate patch; pull runFixer and runFormat into separate classes, and merge common code in CodeProcessor class.

[ioeric]

• Fixed a potential bug in checkEmptyNamespace.

[ioeric]

lib/Format/Format.cpp

1597

I am not quite sure here actually. This was copied from Formatter. And since consumeUnwrappedLine requires at lease one element in UnwrappedLines, I figured this is necessary initialization?

1818

I want to reduce the number of replacements so that when we do reformat on the fixed code, there could be fewer changed code ranges considering that the current implementation of computeAffectedLines is not that efficient when we have many ranges.

2065

I'm not quite sure if the name is accurate. Do you have a better name?

2340

Wow, this is really helpful! Thanks!

[djasper]

include/clang/Format/Format.h

800

Same as above, "fix" is probably not the right word. "cleanup" seems somewhat better. Here and everywhere else in this patch :-/.

lib/Format/Format.cpp

1920

Maybe call this AffectedRangeManager? That is the class's very specific purpose.

1939

It feels like these two functions increase the coupling between Formatter/Fixer and CodeProcesser and aren't really necessary. Can you just inline them at the locations where they are called?

1998

Lets not have this access. Provide getters.

2065

I think the difficulty of finding a name somewhat stems from the fact that it does multiple things at once. I think the main purpose is to encapsulate the "flattening" of the different #if/#else branches in successive runs.

Manuel, do you have an idea for a good name here?

2170

I see why you are doing it this way, but let me propose something else:

How about iterating over all of the lines for each thing to cleanup (namespaces, ctor-intializers, etc.). I don't think it makes a significant difference in the runtime. Then you can just skip all the lines that you have already looked at (i.e. the returned int).

Among other things, you can probably remove the duplication of the AnnotatedLines[CurrentLine]->startsWith(..) and maybe even the AnnotatedLine::Deleted field.

lib/Format/FormatToken.h

283

Do you need this? Wouldn't it be enough to add them to the set of deleted tokens and mark them as Finalized?

[ioeric]

• Addressed comments.

[ioeric]

• removed unused fields in AnnotatedLine.

[ioeric]

• minor changes in checkEmptyNamespace.

[djasper]

lib/Format/Format.cpp

2089

I think FormatStyle in the Processor should be const and Formatter should make its own copy to modify it.

2182

Why are you introducing a return value that you aren't using? I'd just return the number of subsequent lines to skip.

Overall, I'd do this a bit differently:

• Let it check the namespace starting at CurrentLine
• Delete empty namespaces within
• If it is empty, delete the outer namespace
• Always return how many lines it has looked at

That way, you don't need to store DeletedLines and you don't ever look at the same line multiple times.

2183

What about

namespace A { // really cool namespace

?

2243

I believe that this doesn't work in many circumstances. Not sure I can easily construct a test case for the namespace cleanup, but generally, AnnotatedLines are not in a strict order. The last token of a line isn't necessarily next to the first token of the next line. This happens, e.g. for nested blocks and if preprocessor lines are intermingled with other lines.

2246–2249

I think this should hardly matter considering that we are probably only going to have a few instances of cleanup replacements and the range calculation is not that inefficient.

2376

Do we also need that if we spell out the ProcessFunc above? Maybe that's actually less painful compared to writing these lambdas?

[ioeric]

• Do not merge multiple lines when generate fixes. Added test cases with comments around namespace.
• Refactor: pull Annotator into Formatter/Cleaner from CodeProcessor. Moved AffectedRangeManager to a separate file.

[klimek]

include/clang/Format/Format.h

769

cleanupAroundReplacements sounds good.

lib/Format/Format.cpp

1940

Nit: I think it's idiomatic to call this a "Callback".

2427

This is unexpected: I'd not have expected the CodeProcessor to be used to keep state apart from what's used during a Process() run. I think we'll need a different name.

2460

The way the Processor is passed into the callbacks so they can call stuff on the processor again makes me think this is really tightly coupled and should use inheritance.

Alternatively, we might want to try to break up the CodeProcessor into a part that just runs the callback and keeps the state for running the callback around, and an interface that is used by the callbacks - I'll need to look more closely into this though.

[klimek]

lib/Format/Format.cpp

1923

After pondering a bit more, it seems like CodeProcessor is too generic: this is more something that runs analyses based on annotated tokens, so I'd call it TokenAnalyzer or something. That would also make it obvious to push some of the duplicated functionality from Formatter and Cleaner down (namely everything up to where we have generated the annotated tokens).

I'm still not completely convinced either way regarding inheritance vs. composition, but if we have a TokenAnalyzer, we'd also have a nice is-a relationship. While I generally agree to prefer composition, I also think we need to look out for where inheritance actually makes things clearer.

[ioeric]

• Rebased
• Make Formatter and Cleaner inherit from TokenAnalyzer (new name for CodeProcessor).

[ioeric]

• Added comments for endsWithInternal().

[ioeric]

PING.

[djasper]

lib/Format/Format.cpp

1982–1984

Move this into the base class?

2394

Instead, create a class Environment that does all of these and makes SourceMgr, ID and CharRanges available via getters (maybe more). Then you should be able to just instantiate an environment and call the other reformat/cleanup function with the corresponding arguments.

[ioeric]

• Refactored - added Environment class.

[ioeric]

• Merged VirtualEnvironment into Environment.

[klimek]

We'll probably want Daniel to also take another look over it, as it's a pretty substantial change that will haunt us for a while, but I think this now pretty much looks like I expect it to look.

lib/Format/Format.cpp

1930

Won't deleting this line have the same effect?

1965–1966

There is no base class any more.

1986

Don't name it SourceMgr, as there is a class of that name. Unfortunately we'll probably want to name it SM, like everywhere else in clang :(

2188

In LLVM TODOs are spelled FIXME.

[ioeric]

• Addressed comments.

[ioeric]

@Daniel, sorry that I forgot to have you look at the final version before
submitting it...

[djasper]

cfe/trunk/lib/Format/AffectedRangeManager.h

59 ↗

(On Diff #54857)

And an empty line between functions and data members here.

66 ↗

(On Diff #54857)

Fix header guard comment

cfe/trunk/lib/Format/Format.cpp

1355 ↗

(On Diff #54857)

What happened here?

1463 ↗

(On Diff #54857)

Hand in CharRanges as ArrayRef or const vector&.

1471 ↗

(On Diff #54857)

Why don't you do this in the constructor? Seems asymmetric to just call a constructor in the one codepath but a factory function in the other one.

1519 ↗

(On Diff #54857)

Would it be sufficient to return a const SourceManager&? I guess not, but I'd like to understand where it breaks. If we could return a const source manager here, that would enable us to pass around a "const Environment&" at a few places.

[ioeric]

cfe/trunk/lib/Format/Format.cpp

1355 ↗

(On Diff #54857)

This line exceeded 80 characters and was formatted by clang-format when I ran clang-format across it...but I guess this change was out of the scope of this patch...sorry about that.

1471 ↗

(On Diff #54857)

We have a reference member "SourceManager &SM" that can only be initialized after setting up the environment...I didn't know if constructor would work in this case.

lib/Format/Format.cpp

1982–1984

The way we calculate affected ranges are the same for Cleaner and Formatter. But in the future, we might want more accurate affected ranges for Cleaner.

include/clang/Format/Format.h

tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
                                    unsigned *Cursor = nullptr);
 
 /// \brief Returns the replacements corresponding to applying and formatting
 /// \p Replaces.
 tooling::Replacements formatReplacements(StringRef Code,
                                          const tooling::Replacements &Replaces,
                                          const FormatStyle &Style);
 
+/// \brief Returns the replacements corresponding to applying and fixing
+/// \p Replaces.
+tooling::Replacements fixReplacements(StringRef Code,
+                                      const tooling::Replacements &Replaces,
+                                      const FormatStyle &Style);
+
 /// \brief Reformats the given \p Ranges in the file \p ID.
 ///
 /// Each range is extended on either end to its next bigger logic unit, i.e.
 /// everything that might influence its formatting or might be influenced by its
 /// formatting.
 ///
 /// Returns the ``Replacements`` necessary to make all \p Ranges comply with
 /// \p Style.

 /// \brief Reformats the given \p Ranges in \p Code.
 ///
 /// Otherwise identical to the reformat() function using a file ID.
 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
                                ArrayRef<tooling::Range> Ranges,
                                StringRef FileName = "<stdin>",
                                bool *IncompleteFormat = nullptr);
 
+/// \brief Fix any erroneous/redundant code in the given \p Ranges in \p Code.
+///
+/// Returns the ``Replacements`` that fix all \p Ranges in \p Code.
+tooling::Replacements fix(const FormatStyle &Style, StringRef Code,
+                          ArrayRef<tooling::Range> Ranges,
+                          StringRef FileName = "<stdin>");
+
 /// \brief Returns the ``LangOpts`` that the formatter expects you to set.
 ///
 /// \param Style determines specific settings for lexing mode.
 LangOptions getFormattingLangOpts(const FormatStyle &Style = getLLVMStyle());
 
 /// \brief Description to be used for help text for a ``llvm::cl`` option for
 /// specifying format style. The description is closely related to the operation
 /// of ``getStyle()``.

lib/Format/Format.cpp

case FormatStyle::LK_JavaScript:
     return "JavaScript";
   case FormatStyle::LK_Proto:
     return "Proto";
   default:
     return "Unknown";
   }
 }
 
+class RangeManager {
+public:
+  RangeManager(SourceManager &SourceMgr,
+               const SmallVector<CharSourceRange, 8> &Ranges)
+      : SourceMgr(SourceMgr), Ranges(Ranges) {}
+
+  // Determines which lines are affected by the SourceRanges given as input.
+  // Returns \c true if at least one line between I and E or one of their
+  // children is affected.
+  bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
+                            SmallVectorImpl<AnnotatedLine *>::iterator E) {
+    bool SomeLineAffected = false;
+    const AnnotatedLine *PreviousLine = nullptr;
+    while (I != E) {
+      AnnotatedLine *Line = *I;
+      Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
+
+      // If a line is part of a preprocessor directive, it needs to be formatted
+      // if any token within the directive is affected.
+      if (Line->InPPDirective) {
+        FormatToken *Last = Line->Last;
+        SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
+        while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
+          Last = (*PPEnd)->Last;
+          ++PPEnd;
+        }
+
+        if (affectsTokenRange(*Line->First, *Last,
+                              /*IncludeLeadingNewlines=*/false)) {
+          SomeLineAffected = true;
+          markAllAsAffected(I, PPEnd);
+        }
+        I = PPEnd;
+        continue;
+      }
+
+      if (nonPPLineAffected(Line, PreviousLine))
+        SomeLineAffected = true;
+
+      PreviousLine = Line;
+      ++I;
+    }
+    return SomeLineAffected;
+  }
+
+  // Returns true if 'Range' intersects with one of the input ranges.
+  bool affectsCharSourceRange(const CharSourceRange &Range) {
+    for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
+                                                          E = Ranges.end();
+         I != E; ++I) {
+      if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
+          !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
+        return true;
+    }
+    return false;
+  }
+
+private:
+  // Returns true if the range from 'First' to 'Last' intersects with one of the
+  // input ranges.
+  bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
+                         bool IncludeLeadingNewlines) {
+    SourceLocation Start = First.WhitespaceRange.getBegin();
+    if (!IncludeLeadingNewlines)
+      Start = Start.getLocWithOffset(First.LastNewlineOffset);
+    SourceLocation End = Last.getStartOfNonWhitespace();
+    End = End.getLocWithOffset(Last.TokenText.size());
+    CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
+    return affectsCharSourceRange(Range);
+  }
+
+  // Returns true if one of the input ranges intersect the leading empty lines
+  // before 'Tok'.
+  bool affectsLeadingEmptyLines(const FormatToken &Tok) {
+    CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
+        Tok.WhitespaceRange.getBegin(),
+        Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
+    return affectsCharSourceRange(EmptyLineRange);
+  }
+
+  // Marks all lines between I and E as well as all their children as affected.
+  void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
+                         SmallVectorImpl<AnnotatedLine *>::iterator E) {
+    while (I != E) {
+      (*I)->Affected = true;
+      markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
+      ++I;
+    }
+  }
+
+  // Determines whether 'Line' is affected by the SourceRanges given as input.
+  // Returns \c true if line or one if its children is affected.
+  bool nonPPLineAffected(AnnotatedLine *Line,
+                         const AnnotatedLine *PreviousLine) {
+    bool SomeLineAffected = false;
+    Line->ChildrenAffected =
+        computeAffectedLines(Line->Children.begin(), Line->Children.end());
+    if (Line->ChildrenAffected)
+      SomeLineAffected = true;
+
+    // Stores whether one of the line's tokens is directly affected.
+    bool SomeTokenAffected = false;
+    // Stores whether we need to look at the leading newlines of the next token
+    // in order to determine whether it was affected.
+    bool IncludeLeadingNewlines = false;
+
+    // Stores whether the first child line of any of this line's tokens is
+    // affected.
+    bool SomeFirstChildAffected = false;
+
+    for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
+      // Determine whether 'Tok' was affected.
+      if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
+        SomeTokenAffected = true;
+
+      // Determine whether the first child of 'Tok' was affected.
+      if (!Tok->Children.empty() && Tok->Children.front()->Affected)
+        SomeFirstChildAffected = true;
+
+      IncludeLeadingNewlines = Tok->Children.empty();
+    }
+
+    // Was this line moved, i.e. has it previously been on the same line as an
+    // affected line?
+    bool LineMoved = PreviousLine && PreviousLine->Affected &&
+                     Line->First->NewlinesBefore == 0;
+
+    bool IsContinuedComment =
+        Line->First->is(tok::comment) && Line->First->Next == nullptr &&
+        Line->First->NewlinesBefore < 2 && PreviousLine &&
+        PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
+
+    if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
+        IsContinuedComment) {
+      Line->Affected = true;
+      SomeLineAffected = true;
+    }
+    return SomeLineAffected;
+  }
+
+  SourceManager &SourceMgr;
+  const SmallVector<CharSourceRange, 8> Ranges;
+};
+
+class Fixer : public UnwrappedLineConsumer {
+public:
+  Fixer(const FormatStyle &Style, SourceManager &SourceMgr, FileID ID,
+        ArrayRef<CharSourceRange> Ranges)
+      : Style(Style), ID(ID), SourceMgr(SourceMgr),
+        RangeMgr(SourceMgr,
+                 SmallVector<CharSourceRange, 8>(Ranges.begin(), Ranges.end())),
+        UnwrappedLines(1),
+        Encoding(encoding::detectEncoding(SourceMgr.getBufferData(ID))),
+        RedundantTokens(FormatTokenLess(SourceMgr)) {
+    DummyToken.Tok.setKind(tok::unknown);
+  }
+
+  tooling::Replacements fix() {
+    tooling::Replacements Result;
+    FormatTokenLexer Tokens(SourceMgr, ID, Style, Encoding);
+
+    UnwrappedLineParser Parser(Style, Tokens.getKeywords(), Tokens.lex(),
+                               *this);
+    Parser.parse();
+    assert(UnwrappedLines.rbegin()->empty());
+
+    TokenAnnotator Annotator(Style, Tokens.getKeywords());
+    for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
+         ++Run) {
+      DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
+      for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
+        AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
+        Annotator.annotate(*AnnotatedLines.back());
+      }
+      // FIXME: in the current implementation the granularity of affected range
+      // is an annotated line. However, this is not sufficient. Furthermore,
+      // redundant code introduced by replacements does not necessarily
+      // intercept with ranges of replacements that result in the redundancy.
+      // To determine if some redundant code is actually introduced by
+      // replacements(e.g. deletions), we need to come up with a more
+      // sophisticated way of computing affected ranges.
+      RangeMgr.computeAffectedLines(AnnotatedLines.begin(),
+                                    AnnotatedLines.end());
+
+      tooling::Replacements RunResult = runFix();
+      DEBUG({
+        llvm::dbgs() << "Replacements for run " << Run << ":\n";
+        for (tooling::Replacements::iterator I = RunResult.begin(),
+                                             E = RunResult.end();
+             I != E; ++I) {
+          llvm::dbgs() << I->toString() << "\n";
+        }
+      });
+      for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i)
+        delete AnnotatedLines[i];
+      Result.insert(RunResult.begin(), RunResult.end());
+    }
+    return Result;
+  }
+
+private:
+  void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
+    assert(!UnwrappedLines.empty());
+    UnwrappedLines.back().push_back(TheLine);
+  }
+
+  void finishRun() override {
+    UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
+  }
+
+  tooling::Replacements runFix() {
+    CurrentLine = 0;
+    LastToken = nullptr;
+    // Make LastTokenNotDeleted point somewhere in the beginning so that we
+    // don't need to check nullptr every time we access it.
+    LastTokenNotDeleted = &DummyToken;
+    CurrentToken = AnnotatedLines[CurrentLine]->First;
+
+    while (CurrentToken->isNot(tok::eof)) {
+      switch (CurrentToken->Tok.getKind()) {
+      case tok::colon:
+        if (CurrentToken->Type == TT_CtorInitializerColon)
+          checkConstructorInitList();
+        else
+          nextToken();
+        break;
+      case tok::kw_namespace:
+        // Ignore using namespace ...;
+        if (!(CurrentToken->Previous &&
+              CurrentToken->Previous->is(tok::kw_using)))
+          checkEmptyNamespace();
+        nextToken();
+        break;
+      default:
+        nextToken();
+        break;
+      }
+    }
+
+    return generateFixes();
+  }
+
+  // Delete the given token.
+  // It will force delete a token even it's not in an affected line if \p Forced
+  // is set to true.
+  inline void deleteToken(FormatToken *Tok, bool Forced = false) {
+    // FIXME: we need better way to determine wether to delete this token.
+    if (!AnnotatedLines[CurrentLine]->Affected && !Forced) return;
+    Tok->Deleted = true;
+    RedundantTokens.insert(Tok);
+  }
+
+  void nextToken() {
+    if (CurrentToken->is(tok::eof)) return;
+    //llvm::errs() << "Current token is " << CurrentToken->Tok.getName() << "\n";
+    LastToken = CurrentToken;
+    if (!LastToken->Deleted && LastToken->isNot(tok::comment))
+      LastTokenNotDeleted = LastToken;
+
+    if (CurrentToken->Next) {
+      CurrentToken = CurrentToken->Next;
+      return;
+    }
+
+    ++CurrentLine;
+    assert(CurrentLine < AnnotatedLines.size());
+    CurrentToken = AnnotatedLines[CurrentLine]->First;
+    LastToken->Next = CurrentToken;
+    assert(CurrentToken);
+  }
+
+  void skipParens() {
+    assert(CurrentToken->is(tok::l_paren));
+    nextToken();
+    while (CurrentToken->isNot(tok::eof)) {
+      switch (CurrentToken->Tok.getKind()) {
+      case tok::l_paren:
+        skipParens();
+        break;
+      case tok::r_paren:
+        return;
+      default:
+        break;
+      }
+      nextToken();
+    }
+  }
+
+  tooling::Replacements generateFixes() {
+    tooling::Replacements Fixes;
+    std::vector<FormatToken *> Tokens;
+    std::copy(RedundantTokens.begin(), RedundantTokens.end(),
+              std::back_inserter(Tokens));
+
+    // Merge multiple continuous token deletions into one big deletion.
+    unsigned Idx = 0;
+    while (Idx < Tokens.size()) {
+      unsigned St = Idx, End = Idx;
+      while ((End + 1) < Tokens.size() &&
+             Tokens[End]->Next == Tokens[End + 1]) {
+        End++;
+      }
+      auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
+                                              Tokens[End]->Tok.getEndLoc());
+      Fixes.insert(tooling::Replacement(SourceMgr, SR, ""));
+      Idx = End + 1;
+    }
+    return Fixes;
+  }
+
+  void checkConstructorInitList() {
+    assert(CurrentToken->Type == TT_CtorInitializerColon &&
+           "Expect TT_CtorInitializerColon Token!");
+    FormatToken *CtorInitColonTok = CurrentToken;
+    nextToken();
+    bool IsListEmpty = true;
+    bool Done = false;
+    // This vector stores comments between the last token not deleted and the
+    // current token.
+    SmallVector<FormatToken *, 1> Comments;
+    while (!Done && CurrentToken->isNot(tok::eof)) {
+      switch (CurrentToken->Tok.getKind()) {
+      case tok::comma:
+        if (LastTokenNotDeleted->isOneOf(tok::comma, tok::colon)) {
+          deleteToken(CurrentToken);
+          // If there is a new line before the deleted comma, the comment may
+          // belong to the previous token.
+          if (!CurrentToken->HasUnescapedNewline)
+            for (auto *Comment : Comments)
+              deleteToken(Comment);
+        }
+        break;
+      case tok::l_paren:
+        // We need to skip a pair of parentheses here because it is possible
+        // that "({ ... })" appears in the initialization list, and we do not
+        // want to return when we get the "{" in the parentheses.
+        skipParens();
+        break;
+      case tok::l_brace:
+        if (LastTokenNotDeleted->is(tok::comma)) {
+          deleteToken(LastTokenNotDeleted);
+          for (auto *Comment : Comments)
+            deleteToken(Comment);
+          // FIXME: LastTokenNotDeleted should be the token before it now, but
+          // we do not have a pointer to it. Now we make it point to DummyToken
+          // in this case since we are finishing the checking.
+          LastTokenNotDeleted = &DummyToken;
+        }
+        Done = true;
+        break;
+      case tok::comment:
+        // If the last deleted token is followed by a comment "//...", then we
+        // delete the comment as well.
+        if (LastToken->Deleted && CurrentToken->TokenText.startswith("//"))
+          deleteToken(CurrentToken);
+        else
+          Comments.push_back(CurrentToken);
+        break;
+      default:
+        IsListEmpty = false;
+        break;
+      }
+      if (!Done) {
+        if (CurrentToken->isNot(tok::comment))
+          Comments.clear();
+        nextToken();
+      }
+    }
+    if (IsListEmpty)
+      // FIXME: LastTokenNotDeleted might also be affected. But since we are at
+      // the end of the check. This can be ignored now.
+      deleteToken(CtorInitColonTok);
+  }
+
+  // Check if a namespace is empty (i.e. contains nothing other than comments or
+  // nested namespace).
+  //
+  // Returns true if the namespace is empty .
+  bool checkEmptyNamespace() {
+    assert(CurrentToken->is(tok::kw_namespace));
+
+    FormatToken *InitialTok =
+        (CurrentToken->Previous && CurrentToken->Previous->is(tok::kw_inline))
+            ? CurrentToken->Previous
+            : CurrentToken;
+
+    nextToken();
+    while (CurrentToken->isOneOf(tok::identifier, tok::coloncolon)) {
+      nextToken();
+    }
+
+    if (CurrentToken->isNot(tok::l_brace))
+      return false;
+
+    nextToken();
+    bool IsEmpty = true;
+    // BracesDepth is used to find the matching brace.
+    // +1 on tok::l_brace; -1 on tok::r_brace.
+    int BracesDepth = 1;
+    while (BracesDepth > 0 && CurrentToken->isNot(tok::eof)) {
+      switch (CurrentToken->Tok.getKind()) {
+      case tok::kw_namespace:
+        IsEmpty = checkEmptyNamespace() && IsEmpty;
+        break;
+      case tok::l_brace:
+        BracesDepth++;
+        break;
+      case tok::r_brace:
+        BracesDepth--;
+        break;
+      default:
+        if (CurrentToken->isNot(tok::comment))
+          IsEmpty = false;
+      }
+      if (BracesDepth > 0)
+        nextToken();
+    }
+
+    if (CurrentToken->is(tok::eof) || !IsEmpty)
+      return false;
+
+    if (CurrentToken->Next && CurrentToken->Next->is(tok::comment) &&
+        !CurrentToken->Next->HasUnescapedNewline)
+      nextToken();
+
+    // Check if the empty namespace is actually affected by changed ranges.
+    if (!RangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
+            InitialTok->Tok.getLocation(), CurrentToken->Tok.getEndLoc())))
+      return false;
+
+    // Force delete the namespace block if it is affected by changed ranges
+    // since some tokens might not be in affected lines.
+    for (FormatToken *Tok = InitialTok; Tok != CurrentToken->Next;
+         Tok = Tok->Next) {
+      deleteToken(Tok, true); // Force delete the token.
+    }
+    return true;
+  }
+
+  // Class for less-than inequality comparason for the set `RedundantTokens`.
+  // We store tokens in the order they appear in the translation unit so that
+  // we do not need to sort them in `generateFixes()`.
+  struct FormatTokenLess {
+    FormatTokenLess(SourceManager &SM) : SM(SM) {}
+
+    bool operator()(const FormatToken *LHS, const FormatToken *RHS) {
+      return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
+                                          RHS->Tok.getLocation());
+    }
+
+    SourceManager &SM;
+  };
+
+  FormatStyle Style;
+  FileID ID;
+  SourceManager &SourceMgr;
+  // RangeMgr stores the ranges to be fixed.
+  RangeManager RangeMgr;
+  SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
+  encoding::Encoding Encoding;
+  SmallVector<AnnotatedLine *, 16> AnnotatedLines;
+  // The number of the current line we are fixing in AnnotatedLines.
+  size_t CurrentLine;
+  FormatToken DummyToken;
+  // The last token that was read.
+  FormatToken *LastToken;
+  // The last token that has not been deleted.
+  FormatToken *LastTokenNotDeleted;
+  // The current token we are considering.
+  FormatToken *CurrentToken;
+  // Redundant tokens to be deleted.
+  std::set<FormatToken *, FormatTokenLess> RedundantTokens;
+};
+
 class Formatter : public UnwrappedLineConsumer {
 public:
   Formatter(const FormatStyle &Style, SourceManager &SourceMgr, FileID ID,
             ArrayRef<CharSourceRange> Ranges)
       : Style(Style), ID(ID), SourceMgr(SourceMgr),
         Whitespaces(SourceMgr, Style,
                     inputUsesCRLF(SourceMgr.getBufferData(ID))),
-        Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
+        RangeMgr(SourceMgr,
+                 SmallVector<CharSourceRange, 8>(Ranges.begin(), Ranges.end())),
+        UnwrappedLines(1),
         Encoding(encoding::detectEncoding(SourceMgr.getBufferData(ID))) {
     DEBUG(llvm::dbgs() << "File encoding: "
                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
                                                                : "unknown")
                        << "\n");
     DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
                        << "\n");
   }
 
   tooling::Replacements format(bool *IncompleteFormat) {
     tooling::Replacements Result;
     FormatTokenLexer Tokens(SourceMgr, ID, Style, Encoding);
 
     UnwrappedLineParser Parser(Style, Tokens.getKeywords(), Tokens.lex(),
                                *this);
     Parser.parse();
     assert(UnwrappedLines.rbegin()->empty());
     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
          ++Run) {
       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
       }
       tooling::Replacements RunResult =
           format(AnnotatedLines, Tokens, Result, IncompleteFormat);
       DEBUG({
         llvm::dbgs() << "Replacements for run " << Run << ":\n";
         for (tooling::Replacements::iterator I = RunResult.begin(),
                                              E = RunResult.end();
              I != E; ++I) {
           llvm::dbgs() << I->toString() << "\n";
         }
       });
       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
         delete AnnotatedLines[i];
       }
       Result.insert(RunResult.begin(), RunResult.end());
       Whitespaces.reset();
     }
     return Result;
   }
 
   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
                                FormatTokenLexer &Tokens,
                                tooling::Replacements &Result,
                                bool *IncompleteFormat) {
     TokenAnnotator Annotator(Style, Tokens.getKeywords());
     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
       Annotator.annotate(*AnnotatedLines[i]);
     }
     deriveLocalStyle(AnnotatedLines);
-    computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
+
+    RangeMgr.computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
+
     if (Style.Language == FormatStyle::LK_JavaScript &&
         Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
       requoteJSStringLiteral(AnnotatedLines, Result);
 
     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
     }
 
     Annotator.setCommentLineLevels(AnnotatedLines);
     ContinuationIndenter Indenter(Style, Tokens.getKeywords(), SourceMgr,
                                   Whitespaces, Encoding,
                                   BinPackInconclusiveFunctions);
     UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
                            IncompleteFormat)
         .format(AnnotatedLines);
     return Whitespaces.generateReplacements();
   }
 
 private:
-  // Determines which lines are affected by the SourceRanges given as input.
-  // Returns \c true if at least one line between I and E or one of their
-  // children is affected.
-  bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
-                            SmallVectorImpl<AnnotatedLine *>::iterator E) {
-    bool SomeLineAffected = false;
-    const AnnotatedLine *PreviousLine = nullptr;
-    while (I != E) {
-      AnnotatedLine *Line = *I;
-      Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
-
-      // If a line is part of a preprocessor directive, it needs to be formatted
-      // if any token within the directive is affected.
-      if (Line->InPPDirective) {
-        FormatToken *Last = Line->Last;
-        SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
-        while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
-          Last = (*PPEnd)->Last;
-          ++PPEnd;
-        }
-
-        if (affectsTokenRange(*Line->First, *Last,
-                              /*IncludeLeadingNewlines=*/false)) {
-          SomeLineAffected = true;
-          markAllAsAffected(I, PPEnd);
-        }
-        I = PPEnd;
-        continue;
-      }
-
-      if (nonPPLineAffected(Line, PreviousLine))
-        SomeLineAffected = true;
-
-      PreviousLine = Line;
-      ++I;
-    }
-    return SomeLineAffected;
-  }
- 
   // If the last token is a double/single-quoted string literal, generates a
   // replacement with a single/double quoted string literal, re-escaping the
   // contents in the process.
   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
                                  tooling::Replacements &Result) {
     for (AnnotatedLine *Line : Lines) {
       requoteJSStringLiteral(Line->Children, Result);
       if (!Line->Affected)
for (AnnotatedLine *Line : Lines) {
               if (!Escaped && IsSingle == (Input[i] == '\'')) {
                 // Escape the quote.
                 Replace(Start.getLocWithOffset(i), 0, "\\");
                 ColumnWidth++;
               }
               Escaped = false;
               break;
             default:
               Escaped = false;
               break;
           }
         }
 
         // For formatting, count the number of non-escaped single quotes in them
         // and adjust ColumnWidth to take the added escapes into account.
         // FIXME(martinprobst): this might conflict with code breaking a long string
         // literal (which clang-format doesn't do, yet). For that to work, this code
         // would have to modify TokenText directly.
         FormatTok->ColumnWidth = ColumnWidth;
       }
     }
   }
 
-
-  // Determines whether 'Line' is affected by the SourceRanges given as input.
-  // Returns \c true if line or one if its children is affected.
-  bool nonPPLineAffected(AnnotatedLine *Line,
-                         const AnnotatedLine *PreviousLine) {
-    bool SomeLineAffected = false;
-    Line->ChildrenAffected =
-        computeAffectedLines(Line->Children.begin(), Line->Children.end());
-    if (Line->ChildrenAffected)
-      SomeLineAffected = true;
-
-    // Stores whether one of the line's tokens is directly affected.
-    bool SomeTokenAffected = false;
-    // Stores whether we need to look at the leading newlines of the next token
-    // in order to determine whether it was affected.
-    bool IncludeLeadingNewlines = false;
-
-    // Stores whether the first child line of any of this line's tokens is
-    // affected.
-    bool SomeFirstChildAffected = false;
-
-    for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
-      // Determine whether 'Tok' was affected.
-      if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
-        SomeTokenAffected = true;
-
-      // Determine whether the first child of 'Tok' was affected.
-      if (!Tok->Children.empty() && Tok->Children.front()->Affected)
-        SomeFirstChildAffected = true;
-
-      IncludeLeadingNewlines = Tok->Children.empty();
-    }
-
-    // Was this line moved, i.e. has it previously been on the same line as an
-    // affected line?
-    bool LineMoved = PreviousLine && PreviousLine->Affected &&
-                     Line->First->NewlinesBefore == 0;
-
-    bool IsContinuedComment =
-        Line->First->is(tok::comment) && Line->First->Next == nullptr &&
-        Line->First->NewlinesBefore < 2 && PreviousLine &&
-        PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
-
-    if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
-        IsContinuedComment) {
-      Line->Affected = true;
-      SomeLineAffected = true;
-    }
-    return SomeLineAffected;
-  }
-
-  // Marks all lines between I and E as well as all their children as affected.
-  void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
-                         SmallVectorImpl<AnnotatedLine *>::iterator E) {
-    while (I != E) {
-      (*I)->Affected = true;
-      markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
-      ++I;
-    }
-  }
-
-  // Returns true if the range from 'First' to 'Last' intersects with one of the
-  // input ranges.
-  bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
-                         bool IncludeLeadingNewlines) {
-    SourceLocation Start = First.WhitespaceRange.getBegin();
-    if (!IncludeLeadingNewlines)
-      Start = Start.getLocWithOffset(First.LastNewlineOffset);
-    SourceLocation End = Last.getStartOfNonWhitespace();
-    End = End.getLocWithOffset(Last.TokenText.size());
-    CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
-    return affectsCharSourceRange(Range);
-  }
-
-  // Returns true if one of the input ranges intersect the leading empty lines
-  // before 'Tok'.
-  bool affectsLeadingEmptyLines(const FormatToken &Tok) {
-    CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
-        Tok.WhitespaceRange.getBegin(),
-        Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
-    return affectsCharSourceRange(EmptyLineRange);
-  }
-
-  // Returns true if 'Range' intersects with one of the input ranges.
-  bool affectsCharSourceRange(const CharSourceRange &Range) {
-    for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
-                                                          E = Ranges.end();
-         I != E; ++I) {
-      if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
-          !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
-        return true;
-    }
-    return false;
-  }
-
   static bool inputUsesCRLF(StringRef Text) {
     return Text.count('\r') * 2 > Text.count('\n');
   }
 
   bool
   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
     for (const AnnotatedLine* Line : Lines) {
       if (hasCpp03IncompatibleFormat(Line->Children))
         return true;
       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
             return true;
           if (Tok->is(TT_TemplateCloser) &&
               Tok->Previous->is(TT_TemplateCloser))
             return true;
         }
       }
private:
   void finishRun() override {
     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
   }
 
   FormatStyle Style;
   FileID ID;
   SourceManager &SourceMgr;
   WhitespaceManager Whitespaces;
-  SmallVector<CharSourceRange, 8> Ranges;
+  // RangeMgr stores ranges to be fixed.
+  RangeManager RangeMgr;
   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
 
   encoding::Encoding Encoding;
   bool BinPackInconclusiveFunctions;
 };
 
 struct IncludeDirective {
   StringRef Filename;
   StringRef Text;
   unsigned Offset;
   int Category;
 };
 
 } // end anonymous namespace
 
 // Determines whether 'Ranges' intersects with ('Start', 'End').
 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
                          unsigned End) {
   for (auto Range : Ranges) {
     if (Range.getOffset() < End &&
         Range.getOffset() + Range.getLength() > Start)
       return true;
   }
   return false;
 }
 
 // Sorts a block of includes given by 'Includes' alphabetically adding the
 // necessary replacement to 'Replaces'. 'Includes' must be in strict source
 // order.
 static void sortIncludes(const FormatStyle &Style,
                          const SmallVectorImpl<IncludeDirective> &Includes,
if (Cursor && !CursorMoved) {
         CursorMoved = true;
       }
     }
   }
 
   // Sorting #includes shouldn't change their total number of characters.
   // This would otherwise mess up 'Ranges'.
   assert(result.size() ==
          Includes.back().Offset + Includes.back().Text.size() -
              Includes.front().Offset);
 
   Replaces.insert(tooling::Replacement(FileName, Includes.front().Offset,
                                        result.size(), result));
 }
 
 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
                                    ArrayRef<tooling::Range> Ranges,
                                    StringRef FileName, unsigned *Cursor) {
   tooling::Replacements Replaces;
   if (!Style.SortIncludes)
     return Replaces;
 
   unsigned Prev = 0;
if (Pos == StringRef::npos || Pos + 1 == Code.size())
       break;
     SearchFrom = Pos + 1;
   }
   if (!IncludesInBlock.empty())
     sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
   return Replaces;
 }
 
-tooling::Replacements formatReplacements(StringRef Code,
-                                         const tooling::Replacements &Replaces,
-                                         const FormatStyle &Style) {
+typedef std::function<tooling::Replacements(
+    const FormatStyle &, StringRef, std::vector<tooling::Range>, StringRef)>
+    ReplacementsProcessFunctionType;
+
+static tooling::Replacements
+processReplacements(StringRef Code, const tooling::Replacements &Replaces,
+                    ReplacementsProcessFunctionType ProcessFunc,
   if (Replaces.empty())
     return tooling::Replacements();
 
   std::string NewCode = applyAllReplacements(Code, Replaces);
   std::vector<tooling::Range> ChangedRanges =
       tooling::calculateChangedRanges(Replaces);
   StringRef FileName = Replaces.begin()->getFilePath();
+
   tooling::Replacements FormatReplaces =
-      reformat(Style, NewCode, ChangedRanges, FileName);
+      ProcessFunc(Style, NewCode, ChangedRanges, FileName);
 
-  tooling::Replacements MergedReplacements =
-      mergeReplacements(Replaces, FormatReplaces);
+  return mergeReplacements(Replaces, FormatReplaces);
+}
 
-  return MergedReplacements;
+tooling::Replacements formatReplacements(StringRef Code,
+                                         const tooling::Replacements &Replaces,
+                                         const FormatStyle &Style) {
+  // We need to use lambda function here since `reformat` has default parameter
+  // `IncompleteFormat`.
+  auto Reformat = [](const FormatStyle &Style, StringRef Code,
+                     std::vector<tooling::Range> Ranges,
+                     StringRef FileName) -> tooling::Replacements {
+    return reformat(Style, Code, Ranges, FileName);
+  };
+  return processReplacements(Code, Replaces, Reformat, Style);
+}
+
+tooling::Replacements fixReplacements(StringRef Code,
+                                      const tooling::Replacements &Replaces,
+                                      const FormatStyle &Style) {
+  return processReplacements(Code, Replaces, fix, Style);
 }
 
 tooling::Replacements reformat(const FormatStyle &Style,
                                SourceManager &SourceMgr, FileID ID,
                                ArrayRef<CharSourceRange> Ranges,
                                bool *IncompleteFormat) {
   FormatStyle Expanded = expandPresets(Style);
   if (Expanded.DisableFormat)
     return tooling::Replacements();
   Formatter formatter(Expanded, SourceMgr, ID, Ranges);
   return formatter.format(IncompleteFormat);
 }
 
 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
                                ArrayRef<tooling::Range> Ranges,
                                StringRef FileName, bool *IncompleteFormat) {
   if (Style.DisableFormat)
     return tooling::Replacements();
 
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
       new vfs::InMemoryFileSystem);
   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
   DiagnosticsEngine Diagnostics(
       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
       new DiagnosticOptions);
   SourceManager SourceMgr(Diagnostics, Files);
   InMemoryFileSystem->addFile(
       FileName, 0, llvm::MemoryBuffer::getMemBuffer(
                        Code, FileName, /*RequiresNullTerminator=*/false));
   FileID ID = SourceMgr.createFileID(Files.getFile(FileName), SourceLocation(),
                                      clang::SrcMgr::C_User);
   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
   std::vector<CharSourceRange> CharRanges;
   for (const tooling::Range &Range : Ranges) {
     SourceLocation Start = StartOfFile.getLocWithOffset(Range.getOffset());
     SourceLocation End = Start.getLocWithOffset(Range.getLength());
     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
   }
   return reformat(Style, SourceMgr, ID, CharRanges, IncompleteFormat);
 }
 
+tooling::Replacements fix(const FormatStyle &Style, StringRef Code,
+                          ArrayRef<tooling::Range> Ranges, StringRef FileName) {
+  if (Style.DisableFormat)
+    return tooling::Replacements();
+
+  IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
+      new vfs::InMemoryFileSystem);
+  FileManager Files(FileSystemOptions(), InMemoryFileSystem);
+  DiagnosticsEngine Diagnostics(
+      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
+      new DiagnosticOptions);
+  SourceManager SourceMgr(Diagnostics, Files);
+  InMemoryFileSystem->addFile(
+      FileName, 0, llvm::MemoryBuffer::getMemBuffer(
+                       Code, FileName, /*RequiresNullTerminator=*/false));
+  FileID ID = SourceMgr.createFileID(Files.getFile(FileName), SourceLocation(),
+                                     clang::SrcMgr::C_User);
+  SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
+  std::vector<CharSourceRange> CharRanges;
+  for (const tooling::Range &Range : Ranges) {
+    SourceLocation Start = StartOfFile.getLocWithOffset(Range.getOffset());
+    SourceLocation End = Start.getLocWithOffset(Range.getLength());
+    CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
+  }
+
+  Fixer Fix(Style, SourceMgr, ID, CharRanges);
+  return Fix.fix();
+}
+
 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
   LangOptions LangOpts;
   LangOpts.CPlusPlus = 1;
   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
   LangOpts.LineComment = 1;
   bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
   LangOpts.Bool = 1;
   LangOpts.ObjC1 = 1;
   LangOpts.ObjC2 = 1;
   LangOpts.MicrosoftExt = 1; // To get kw___try, kw___finally.
   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
   return LangOpts;
 }
 
 const char *StyleOptionHelpDescription =
     "Coding style, currently supports:\n"
     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
     "Use -style=file to load style configuration from\n"
     ".clang-format file located in one of the parent\n"
     "directories of the source file (or current\n"

lib/Format/FormatToken.h

struct FormatToken {
   /// \brief Stores the formatting decision for the token once it was made.
   FormatDecision Decision = FD_Unformatted;
 
   /// \brief If \c true, this token has been fully formatted (indented and
   /// potentially re-formatted inside), and we do not allow further formatting
   /// changes.
   bool Finalized = false;
 
+  // \brief Fixer will set this to true if the token is going to be deleted.
+  bool Deleted = false;
+
   bool is(tok::TokenKind Kind) const { return Tok.is(Kind); }
   bool is(TokenType TT) const { return Type == TT; }
   bool is(const IdentifierInfo *II) const {
     return II && II == Tok.getIdentifierInfo();
   }
   bool is(tok::PPKeywordKind Kind) const {
     return Tok.getIdentifierInfo() &&
            Tok.getIdentifierInfo()->getPPKeywordID() == Kind;

unittests/Format/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(FormatTests
+  FixTest.cpp
   FormatTest.cpp
   FormatTestJava.cpp
   FormatTestJS.cpp
   FormatTestProto.cpp
   FormatTestSelective.cpp
   SortIncludesTest.cpp
   )
 
 target_link_libraries(FormatTests
   clangBasic
   clangFormat
   clangFrontend
   clangRewrite
   clangToolingCore
   )

unittests/Format/FixTest.cpp

+//===- unittest/Format/FixTest.cpp - Code fixing unit tests ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Format/Format.h"
+
+#include "clang/Tooling/Core/Replacement.h"
+
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace format {
+namespace {
+
+class FixTest : public ::testing::Test {
+protected:
+  std::string fix(llvm::StringRef Code,
+                  const std::vector<tooling::Range> &Ranges,
+                  const FormatStyle &Style = getLLVMStyle()) {
+    tooling::Replacements Replaces = format::fix(Style, Code, Ranges);
+
+    std::string Result = applyAllReplacements(Code, Replaces);
+    EXPECT_NE("", Result);
+    return Result;
+  }
+};
+
+TEST_F(FixTest, CtorInitializationSimpleRedundantComma) {
+  std::string Code = "class A {\nA() : , {} };";
+  std::string Expected = "class A {\nA()  {} };";
+  std::vector<tooling::Range> Ranges;
+  Ranges.push_back(tooling::Range(17, 0));
+  Ranges.push_back(tooling::Range(19, 0));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+
+  Code = "class A {\nA() : x(1), {} };";
+  Expected = "class A {\nA() : x(1) {} };";
+  Ranges.clear();
+  Ranges.push_back(tooling::Range(23, 0));
+  Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+TEST_F(FixTest, CtorInitializationBracesInParens) {
+  std::string Code = "class A {\nA() : x({1}),, {} };";
+  std::string Expected = "class A {\nA() : x({1}) {} };";
+  std::vector<tooling::Range> Ranges;
+  Ranges.push_back(tooling::Range(24, 0));
+  Ranges.push_back(tooling::Range(26, 0));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+TEST_F(FixTest, RedundantCommaNotInAffectedRanges) {
+  std::string Code =
+      "class A {\nA() : x({1}), /* comment */, { int x = 0; } };";
+  std::string Expected =
+      "class A {\nA() : x({1}), /* comment */, { int x = 0; } };";
+  // Set the affected range to be "int x = 0", which does not intercept the
+  // constructor initialization list.
+  std::vector<tooling::Range> Ranges(1, tooling::Range(42, 9));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+
+  Code = "class A {\nA() : x(1), {} };";
+  Expected = "class A {\nA() : x(1), {} };";
+  // No range. Fixer should do nothing.
+  Ranges.clear();
+  Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+TEST_F(FixTest, CtorInitializationCommentAroundCommas) {
+  // Remove redundant commas and comment between them.
+  std::string Code = "class A {\nA() : x({1}), /* comment */, {} };";
+  std::string Expected = "class A {\nA() : x({1}) {} };";
+  std::vector<tooling::Range> Ranges;
+  Ranges.push_back(tooling::Range(25, 0));
+  Ranges.push_back(tooling::Range(40, 0));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+
+  // Remove trailing comma and comment.
+  Code = "class A {\nA() : x({1}), // comment\n{} };";
+  Expected = "class A {\nA() : x({1})\n{} };";
+  Ranges = std::vector<tooling::Range>(1, tooling::Range(25, 0));
+  Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+
+  // Remove trailing comma, but leave the comment.
+  Code = "class A {\nA() : x({1}), // comment\n , y(1),{} };";
+  Expected = "class A {\nA() : x({1}), // comment\n  y(1){} };";
+  Ranges = std::vector<tooling::Range>(1, tooling::Range(38, 0));
+  Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+
+  // Remove trailing comma and the comment before it.
+  Code = "class A {\nA() : x({1}), \n/* comment */, y(1),{} };";
+  Expected = "class A {\nA() : x({1}), \n y(1){} };";
+  Ranges = std::vector<tooling::Range>(1, tooling::Range(40, 0));
+  Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+
+  // Remove trailing comma and the comment after it.
+  Code = "class A {\nA() : , // comment\n y(1),{} };";
+  Expected = "class A {\nA() : \n y(1){} };";
+  Ranges = std::vector<tooling::Range>(1, tooling::Range(17, 0));
+  Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+TEST_F(FixTest, SkipImbalancedParentheses) {
+  std::string Code = "class A {\nA() : x((),, {} };";
+  std::string Expected = "class A {\nA() : x((),, {} };";
+  std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+TEST_F(FixTest, DeleteEmptyNamespaces) {
+  std::string Code = "namespace A {\n"
+                     "namespace B {\n"
+                     "} // namespace B\n"
+                     "} // namespace A\n\n"
+                     "namespace C {\n"
+                     "namespace D { int i; }\n"
+                     "inline namespace E { namespace { } }\n"
+                     "}";
+  std::string Expected = "\n\nnamespace C {\n"
+                         "namespace D { int i; }\n\n"
+                         "}";
+  std::vector<tooling::Range> Ranges;
+  Ranges.push_back(tooling::Range(28, 0));
+  Ranges.push_back(tooling::Range(91, 6));
+  Ranges.push_back(tooling::Range(132, 0));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+TEST_F(FixTest, NamespaceWithSyntaxError) {
+  std::string Code = "namespace A {\n"
+                     "namespace B {\n" // missing r_brace
+                     "} // namespace A\n\n"
+                     "namespace C {\n"
+                     "namespace D int i; }\n"
+                     "inline namespace E { namespace { } }\n"
+                     "}";
+  std::string Expected = "namespace A {\n"
+                         "\n\nnamespace C {\n"
+                         "namespace D int i; }\n\n"
+                         "}";
+  std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+TEST_F(FixTest, EmptyNamespaceNotAffected) {
+  std::string Code = "namespace A {\n\n"
+                     "namespace {\n\n}}";
+  // Even though the namespaces are empty, but the inner most empty namespace
+  // block is not affected by the changed ranges.
+  std::string Expected = "namespace A {\n\n"
+                         "namespace {\n\n}}";
+  // Set the changed range to be the second "\n".
+  std::vector<tooling::Range> Ranges(1, tooling::Range(14, 0));
+  std::string Result = fix(Code, Ranges);
+  EXPECT_EQ(Expected, Result);
+}
+
+} // end namespace
+} // end namespace format
+} // end namespace clang

unittests/Format/FormatTest.cpp

TEST(FormatStyle, GetStyleOfFile) {
   ASSERT_TRUE(FS.addFile("/c/sub/sub/sub/test.cpp", 0,
                          llvm::MemoryBuffer::getMemBuffer("int i;")));
   auto Style3 = getStyle("file", "/c/sub/sub/sub/test.cpp", "LLVM", &FS);
   ASSERT_EQ(Style3, getGoogleStyle());
 }
 
 #endif // _MSC_VER
 
 class ReplacementTest : public ::testing::Test {
 protected:
   tooling::Replacement createReplacement(SourceLocation Start, unsigned Length,
                                          llvm::StringRef ReplacementText) {
     return tooling::Replacement(Context.Sources, Start, Length,
                                 ReplacementText);
   }
 
   RewriterTestContext Context;
Replaces.insert(tooling::Replacement(
       Context.Sources, Context.getLocation(ID, 4, 13), 1, "nullptr"));
 
   format::FormatStyle Style = format::getLLVMStyle();
   Style.ColumnLimit = 20; // Set column limit to 20 to increase readibility.
   EXPECT_EQ(Expected, applyAllReplacements(
                           Code, formatReplacements(Code, Replaces, Style)));
 }
 
+TEST_F(ReplacementTest, FixCodeAfterReplacements) {
+  std::string Code = "class A {\n"
+                     "  A() : X(0), Y(0) {     }\n"
+                     "};";
+  std::string Expected = "class A {\n"
+                         "  A() : X(0) {}\n"
+                         "};";
+  FileID ID = Context.createInMemoryFile("format.cpp", Code);
+  tooling::Replacements Replaces;
+  Replaces.insert(tooling::Replacement(
+      Context.Sources, Context.getLocation(ID, 2, 15), 4, ""));
+
+  format::FormatStyle Style = format::getLLVMStyle();
+  auto FinalReplaces =
+      formatReplacements(Code, fixReplacements(Code, Replaces, Style), Style);
+  EXPECT_EQ(Expected, applyAllReplacements(Code, FinalReplaces));
+}
+
+TEST_F(ReplacementTest, DoNotReformatCodeNotAffectedByReplacements) {
+  std::string Code = "class A {\n"
+                     "  A() : X(0), Y(0) {}\n"
+                     "  f( int    x)    = 0;"
+                     "};";
+  std::string Expected = "class A {\n"
+                         "  A() : X(0) {}\n"
+                         "  f( int    x)    = 0;"
+                         "};";
+  FileID ID = Context.createInMemoryFile("format.cpp", Code);
+  tooling::Replacements Replaces;
+  Replaces.insert(tooling::Replacement(Context.Sources,
+                                       Context.getLocation(ID, 2, 15), 4, ""));
+
+  format::FormatStyle Style = format::getLLVMStyle();
+  auto FinalReplaces =
+      formatReplacements(Code, fixReplacements(Code, Replaces, Style), Style);
+  EXPECT_EQ(Expected, applyAllReplacements(Code, FinalReplaces));
+}
+
 } // end namespace
 } // end namespace format
 } // end namespace clang