Add basic #include sorting functionality to clang-format

[klimek]

lib/Format/Format.cpp

1594–1598

Perhaps document that Includes needs to be in strict source order.

1624

You'll probably want to allow more spaces if this is run before formatting:
\s*#\s*include\s+
Also, we'll probably want .*? in the middle (or [^">]) if there is a > or " in a comment afterwards.

1632–1634

Having the ! case first without early exit confused me.

1642–1644

Why does this work if Pos is npos here? Or can that not happen?

1647

Here I can see that npos doens't matter, because we'll not re-use Prev.

tools/clang-format/ClangFormat.cpp

218

Call this outputReplacementsXML (so it's consistent with outputReplacementXML), or rename all.

244–249

Aren't now the ranges incorrect?

279

This is not atomic, which has been a problem in the past (and which is why the rewriter's overwriteChangedFiles is carefully crafted).
Any reason to not use a second rewriter? Or even better, can we:

1. Create a rewriter
2. Get affected ranges
3. Iff include sorting, sort includes
4. Recompute affected ranges in new file
5. clang-format
6. Rewrite

Alternatively, do not support include sorting and clang-format in the same run and have editor integrations do 2 calls (?)

unittests/Format/SortIncludesTest.cpp

32–37

Nit: I find it slightly distracting that we're not calling them a.h, b.h, c.h (and perhaps have one test that checks that they support longer filenames).

51–60

Do we want to sort C vs C++ system headers?

[djasper]

lib/Format/Format.cpp

1642–1644

Simplified so that this isn't an issue any more.

1647

Ack.

tools/clang-format/ClangFormat.cpp

244–249

So, there are two cases:

1. Ranges outside of #include blocks. These should not change as the size of the include block doesn't change.
2. Ranges inside of a #include block. Yes, here we kind of format a #include statement that isn't necessarily the one that was included in the original range. I think the right fix here is to format the entire #include block if something is moved around (to re-align comments if necessary). What do you think? Is that ok as a follow-up patch?

279

Yes, using a second rewriter or recomputing the affected ranges is a significant calculation for the sole purpose of un-doing the offsets calculated in the rewriter. Furthermore, we already have the new code after #include sorting, which we simply calculate again, which seems like wasted efforts.

I don't know how the non-atomic-write has been a problem, but if it is, I'd prefer to pull out a function or the AtomicallyMovedFile.

I am strongly against letting this be handled by editor integrations so that the integrations exhibit consistent behavior and that we don't need to implement this N times.

unittests/Format/SortIncludesTest.cpp

51–60

Yes, but I want to do refinements to the actual sorting in a follow up. I have a bunch of ideas.

[djasper]

Addressed review comments.

[klimek]

tools/clang-format/ClangFormat.cpp

279

I don't understand yet why we can't use 1 rewriter. The rewriter should automatically use the updated ranges after we did the fixes, shouldn't it?

I definitely think we'll need to have 2 different runs anyway for all integrations that run on replacements, or otherwise we'd need to somehow group replacements in a way that it's clear in which order they need to be applied, and when the basis for the calculation of the ranges changes.

unittests/Format/SortIncludesTest.cpp

51–60

SG

[djasper]

tools/clang-format/ClangFormat.cpp

279

That's exactly what the rewriter does. It simply doesn't help us at all in this case. Other than writing the file atomically, it only makes our life harder.

I think clang-format outputting the replacements in the order in which they need to applied makes sense and is significantly easier to integrate with than a two-phase run.

[klimek]

tools/clang-format/ClangFormat.cpp

279

I'll need to tinker with that myself, but that's not a blocker. I'm still unhappy with the interface though. I think having a list of replacements where you can't select a single one and apply it is a very subtle interface. Have you tested this with the eclipse / visual studio integration?

[djasper]

tools/clang-format/ClangFormat.cpp

279

Oooo... I have a good idea to fix both of these things. Let me rewrite some stuff.

[djasper]

Added an alternative way to handle the two sets of Replacements: Merge them properly.

I haven't completely finished implementing / testing this. Wanted to get feedback first before going further down this road.

[djasper]

Now properly implemented merging of two replacement sets that are meant to be applied in sequence. I think this functionality will also be highly useful, e.g. when formatting the result of a clang-tidy fix or many other such things.

[djasper]

Ping?

[klimek]

First round of comments; some things are still a bit confusing, so I hope another round will help to weed them out.

include/clang/Tooling/Core/Replacement.h

223–224

s/to/two/

lib/Format/Format.cpp

1612–1620

I think this wants a comment along the lines of:
We create one large replacement for the block of includes.
If the order is already correct, we do not want to create that replacement.

1644

Do we want to use \s instead of "\ " so this also works for tab-using codebases?

1651

I'd have expected early exit, but I can see it'd introduce a one-line duplication. Not sure, just wanted to bring it up.

1660–1663

Nit: I think this would be a bit more readable if we only call sortInlucdes if !IncludesInBlock.empty() and add that as condition to the else.

lib/Tooling/Core/Replacement.cpp

310–313

Nit: remove the first ','.
s/shoud/should/
Also: 'non-overlapping in each set'? (or is that incorrect? the function comment in the header doesn't currently tell, I think we might want to change that)

314

Would be good to learn up here why SecondI == Second.end() implies "an element from 'Second' needs to be merged".
Ok, it looks like this implies that the other one is the one that is the basis for merging. Perhaps MergeIntoFirst?

332–336

This structure looks like we'd want 2 functions. I assume you had reasons not to pull out two local functions? What are they? Too many parameters? (I'd probably pull out a class to be able to put this into smaller methods, but I'm probably weird).

341

If SecondI == Second.end(), isn't this an undefined access?

354

I'm surprised the explicit Twine() is needed here...

[djasper]

lib/Format/Format.cpp

1651

It's actually three lines I think. Also, I think we'll significantly extend the logic here shortly (e.g. to properly support Google and LLVM styles), so I don't think it is worth thinking about too much.

1660–1663

Done and removed the check inside sortIncludes.

lib/Tooling/Core/Replacement.cpp

332–336

Maybe a class would be the way to go here. I'll try in a subsequent patch (don't think it should be a priority at this point).

341

Cannot happen. The while starts with MergeSecond && SecondI != Second.end().

354

How else would this know to use a Twine for efficient concatenation?

[djasper]

Addressed (most) comments

[djasper]

Restructured a bit. Not as many comments just yet. Do you think this is an improvement?

[klimek]

Sending another batch of comments.

lib/Tooling/Core/Replacement.cpp

305–307

Merge the two sets which are each sorted by offset:
Look at the the next replacement from both sets and check whether they overlap:

1. as long as they do not overlap, we add the replacement with the lower offset to the result set
2. when they do overlap, merge into the replacement with the lower offset: repeatedly take the next replacement from the other queue and merge it, until the end of the next replacement is past the end of the currently merged into replacement; in that case, the next replacement becomes the currently merged into replacement;

Invariants:

• we always merge replacements from the first set into a replacement from the second set or vice versa
• an invariant while merging is that the offset of the next replacement to merge is always >= the offset of the currently merged-into replacement
• more?

Position projections:
When comparing positions, we calculate the projection of positions in the second (later) set into where they would happen in the original string.
In the above algorithm, we can always project the start position of a replacement from the second set correctly: only a replacement with a smaller offset can influence the start position of a replacement from the second set; due to the invariant, we never try to merge a replacement from the second set before we have merged all replacements with a smaller offset.
We cannot generally project the end position of a replacement from the second set correctly, but:

• we can correctly project it correctly if it is smaller or equal to the end position of the replacement from the first set we currently compare to
• that means if we cannot correctly project it, we still know it is larger than the end position of the replacement from the first set we currently compare against, so the replacement from the second set will stay the element to merge into, and we will continuously adapt the end position's projection when we merge further replacements from the first set.

308–309

Comment:
We get here on the first run or when we ended a merge sequence (that is, we found that
we are at the start of a new replacement in the result set).

(not sure whether that comment carries it's weight; I started it because it took me a moment to figure out why we don't compute which one to take next during merging, and it's a bit more complex, but not sure where to put the comment yet; basically, the problem is that if the next replacement at the end doesn't overlap, it might also be after a non-overlapping replacement from the other set, which I think is not entirely obvious).

310–314

Ok, I think I now understand what confuses me here:
When we do *not* merge (the replacements don't overlap), we take the other element next into the result set. A less specific name like 'FirstNext', or 'NextFromFirst', or even 'MergedIsFirst' (which would fit the 'Merged' prefix of the attributes later) would probably fit my mental model better.
Note that for me there's also ambiguity (at least on the first read) between 'merge into the result set' and 'merge (subsume) one replacement into the current one'.

For me calling this:
NextIsFirst, NextOffset, NextLength, NextReplacement
would help.

326

This I'm less sure about, but I think 'Text' is somewhat ambiguous here - perhaps 'MergedReplaceWith'?

354

There are various overloads of + that yield Twine?

[djasper]

Added comments and did some renaming.

[klimek]

Ok, I think this is now understandable enough for me to go in.

include/clang/Format/Format.h

 ///
 /// When \c BasedOnStyle is not present, options not present in the YAML
 /// document, are retained in \p Style.
 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style);
 
 /// \brief Gets configuration in a YAML string.
 std::string configurationAsText(const FormatStyle &Style);
 
+/// \brief Returns the replacements necessary to sort all #include blocks that
+/// are affected by 'Ranges'.
+tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
+                                   ArrayRef<tooling::Range> Ranges,
+                                   StringRef FileName);
+
 /// \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 \c Replacements necessary to make all \p Ranges comply with
 /// \p Style.

include/clang/Tooling/Core/Replacement.h

bool applyAllReplacements(const std::vector<Replacement> &Replaces,
                           Rewriter &Rewrite);
 
 /// \brief Applies all replacements in \p Replaces to \p Code.
 ///
 /// This completely ignores the path stored in each replacement. If one or more
 /// replacements cannot be applied, this returns an empty \c string.
 std::string applyAllReplacements(StringRef Code, const Replacements &Replaces);
 
+/// \brief Merges two sets of replacements with the second set referring to the
+/// code after applying the first set. Within both 'First' and 'Second',
+/// replacements must not overlap.
+Replacements mergeReplacements(const Replacements &First,
+                               const Replacements &Second);
+
 template <typename Node>
 Replacement::Replacement(const SourceManager &Sources,
                          const Node &NodeToReplace, StringRef ReplacementText,
                          const LangOptions &LangOpts) {
   const CharSourceRange Range =
       CharSourceRange::getTokenRange(NodeToReplace->getSourceRange());
   setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
 }
 
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_CORE_REPLACEMENT_H

lib/Format/Format.cpp

if (Index >= Seq.size()) {
         Template = *((const FormatStyle *)IO.getContext());
         Template.Language = FormatStyle::LK_None;
       }
       Seq.resize(Index + 1, Template);
     }
     return Seq[Index];
   }
 };
-}
-}
+} // namespace yaml
+} // namespace llvm
 
 namespace clang {
 namespace format {
 
 const std::error_category &getParseCategory() {
   static ParseErrorCategory C;
   return C;
 }
private:
   WhitespaceManager Whitespaces;
   SmallVector<CharSourceRange, 8> Ranges;
   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
 
   encoding::Encoding Encoding;
   bool BinPackInconclusiveFunctions;
 };
 
+struct IncludeDirective {
+  StringRef Filename;
+  StringRef Text;
+  unsigned Offset;
+  bool IsAngled;
+};
+
 } // 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,
+                         ArrayRef<tooling::Range> Ranges, StringRef FileName,
+                         tooling::Replacements &Replaces) {
+  if (!affectsRange(Ranges, Includes.front().Offset,
+                    Includes.back().Offset + Includes.back().Text.size()))
+    return;
+  SmallVector<unsigned, 16> Indices;
+  for (unsigned i = 0, e = Includes.size(); i != e; ++i)
+    Indices.push_back(i);
+  std::sort(Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
+    return Includes[LHSI].Filename < Includes[RHSI].Filename;
+  });
+
+  // If the #includes are out of order, we generate a single replacement fixing
+  // the entire block. Otherwise, no replacement is generated.
+  bool OutOfOrder = false;
+  for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
+    if (Indices[i] != i) {
+      OutOfOrder = true;
+      break;
+    }
+  }
+  if (!OutOfOrder)
+    return;
+
+  std::string result = Includes[Indices[0]].Text;
+  for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
+    result += "\n";
+    result += Includes[Indices[i]].Text;
+  }
+
+  // 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) {
+  tooling::Replacements Replaces;
+  unsigned Prev = 0;
+  unsigned SearchFrom = 0;
+  llvm::Regex IncludeRegex(R"(^[\t\ ]*#[\t\ ]*include[^"<]*["<]([^">]*)([">]))");
+  SmallVector<StringRef, 4> Matches;
+  SmallVector<IncludeDirective, 16> IncludesInBlock;
+  for (;;) {
+    auto Pos = Code.find('\n', SearchFrom);
+    StringRef Line =
+        Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
+    if (!Line.endswith("\\")) {
+      if (IncludeRegex.match(Line, &Matches)) {
+        bool IsAngled = Matches[2] == ">";
+        if (!IncludesInBlock.empty() &&
+            IsAngled != IncludesInBlock.back().IsAngled) {
+          sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
+          IncludesInBlock.clear();
+        }
+        IncludesInBlock.push_back({Matches[1], Line, Prev, Matches[2] == ">"});
+      } else if (!IncludesInBlock.empty()) {
+        sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
+        IncludesInBlock.clear();
+      }
+      Prev = Pos + 1;
+    }
+    if (Pos == StringRef::npos || Pos + 1 == Code.size())
+      break;
+    SearchFrom = Pos + 1;
+  }
+  if (!IncludesInBlock.empty())
+    sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
+  return Replaces;
+}
+
 tooling::Replacements reformat(const FormatStyle &Style,
                                SourceManager &SourceMgr, FileID ID,
                                ArrayRef<CharSourceRange> Ranges,
                                bool *IncompleteFormat) {
   if (Style.DisableFormat)
     return tooling::Replacements();
   Formatter formatter(Style, SourceMgr, ID, Ranges);
   return formatter.format(IncompleteFormat);

lib/Format/FormatToken.cpp

 //===--- FormatToken.cpp - Format C++ code --------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief This file implements specific functions of \c FormatTokens and their
 /// roles.
 ///
 //===----------------------------------------------------------------------===//
 
-#include "FormatToken.h"
 #include "ContinuationIndenter.h"
+#include "FormatToken.h"
 #include "clang/Format/Format.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Debug.h"
 #include <climits>
 
 namespace clang {
 namespace format {
 

lib/Tooling/Core/Replacement.cpp

std::string applyAllReplacements(StringRef Code, const Replacements &Replaces) {
   }
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   Rewrite.getEditBuffer(ID).write(OS);
   OS.flush();
   return Result;
 }
 
+namespace {
+// Represents a merged replacement, i.e. a replacement consisting of multiple
+// overlapping replacements from 'First' and 'Second' in mergeReplacements.
+//
+// Position projection:
+// Offsets and lengths of the replacements can generally refer to two different
+// coordinate spaces. Replacements from 'First' refer to the original text
+// whereas replacements from 'Second' refer to the text after applying 'First'.
+//
+// MergedReplacement always operates in the coordinate space of the original
+// text, i.e. transforms elements from 'Second' to take into account what was
+// changed based on the elements from 'First'.
+//
+// We can correctly calculate this projection as we look at the replacements in
+// order of strictly increasing offsets.
+//
+// Invariants:
+// * We always merge elements from 'First' into elements from 'Second' and vice
+//   versa. Within each set, the replacements are non-overlapping.
+// * We only extend to the right, i.e. merge elements with strictly increasing
+//   offsets.
+class MergedReplacement {
+public:
+  MergedReplacement(const Replacement &R, bool MergeSecond, int D)
+      : MergeSecond(MergeSecond), Delta(D), FilePath(R.getFilePath()),
+        Offset(R.getOffset() + (MergeSecond ? 0 : Delta)), Length(R.getLength()),
+        Text(R.getReplacementText()) {
+    Delta += MergeSecond ? 0 : Text.size() - Length;
+    DeltaFirst = MergeSecond ? Text.size() - Length : 0;
+  }
+
+  // Merges the next element 'R' into this merged element. As we always merge
+  // from 'First' into 'Second' or vice versa, the MergedReplacement knows what
+  // set the next element is coming from. 
+  void merge(const Replacement &R) {
+    if (MergeSecond) {
+      unsigned REnd = R.getOffset() + Delta + R.getLength();
+      unsigned End = Offset + Text.size();
+      if (REnd > End) {
+        Length += REnd - End;
+        MergeSecond = false;
+      }
+      StringRef TextRef = Text;
+      StringRef Head = TextRef.substr(0, R.getOffset() + Delta - Offset);
+      StringRef Tail = TextRef.substr(REnd - Offset);
+      Text = (Head + R.getReplacementText() + Tail).str();
+      Delta += R.getReplacementText().size() - R.getLength();
+    } else {
+      unsigned End = Offset + Length;
+      StringRef RText = R.getReplacementText();
+      StringRef Tail = RText.substr(End - R.getOffset());
+      Text = (Text + Tail).str();
+      if (R.getOffset() + RText.size() > End) {
+        Length = R.getOffset() + R.getLength() - Offset;
+        MergeSecond = true;
+      } else {
+        Length += R.getLength() - RText.size();
+      }
+      DeltaFirst += RText.size() - R.getLength();
+    }
+  }
+
+  // Returns 'true' if 'R' starts strictly after the MergedReplacement and thus
+  // doesn't need to be merged.
+  bool endsBefore(const Replacement &R) const {
+    if (MergeSecond)
+      return Offset + Text.size() < R.getOffset() + Delta;
+    return Offset + Length < R.getOffset();
+  }
+
+  // Returns 'true' if an element from the second set should be merged next.
+  bool mergeSecond() const { return MergeSecond; }
+  int deltaFirst() const { return DeltaFirst; }
+  Replacement asReplacement() const { return {FilePath, Offset, Length, Text}; }
+
+private:
+  bool MergeSecond;
+
+  // Amount of characters that elements from 'Second' need to be shifted by in
+  // order to refer to the original text.
+  int Delta;
+
+  // Sum of all deltas (text-length - length) of elements from 'First' merged
+  // into this element. This is used to update 'Delta' once the
+  // MergedReplacement is completed.
+  int DeltaFirst;
+
+  // Data of the actually merged replacement. FilePath and Offset aren't changed
+  // as the element is only extended to the right.
+  const StringRef FilePath;
+  const unsigned Offset;
+  unsigned Length;
+  std::string Text;
+};
+} // namespace
+
+Replacements mergeReplacements(const Replacements &First,
+                               const Replacements &Second) {
+  if (First.empty() || Second.empty())
+    return First.empty() ? Second : First;
+
+  // Delta is the amount of characters that replacements from 'Second' need to
+  // be shifted so that their offsets refer to the original text.
+  int Delta = 0;
+  Replacements Result;
+
+  // Iterate over both sets and always add the next element (smallest total
+  // Offset) from either 'First' or 'Second'. Merge that element with
+  // subsequent replacements as long as they overlap. See more details in the
+  // comment on MergedReplacement.
+  for (auto FirstI = First.begin(), SecondI = Second.begin();
+       FirstI != First.end() || SecondI != Second.end();) {
+    bool NextIsFirst = SecondI == Second.end() ||
+                       FirstI->getOffset() < SecondI->getOffset() + Delta;
+    MergedReplacement Merged(NextIsFirst ? *FirstI : *SecondI, NextIsFirst,
+                             Delta);
+    ++(NextIsFirst ? FirstI : SecondI);
+
+    while ((Merged.mergeSecond() && SecondI != Second.end()) ||
+           (!Merged.mergeSecond() && FirstI != First.end())) {
+      auto &I = Merged.mergeSecond() ? SecondI : FirstI;
+      if (Merged.endsBefore(*I))
+        break;
+      Merged.merge(*I);
+      ++I;
+    }
+    Delta -= Merged.deltaFirst();
+    Result.insert(Merged.asReplacement());
+  }
+  return Result;
+}
+
 } // end namespace tooling
 } // end namespace clang
 

tools/clang-format/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_executable(clang-format
   ClangFormat.cpp
   )
 
 set(CLANG_FORMAT_LIB_DEPS
   clangBasic
   clangFormat
-  clangRewrite
   clangToolingCore
   )
 
 target_link_libraries(clang-format
   ${CLANG_FORMAT_LIB_DEPS}
   )
 
 if( LLVM_USE_SANITIZE_COVERAGE )

tools/clang-format/ClangFormat.cpp

 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/Version.h"
 #include "clang/Format/Format.h"
-#include "clang/Rewrite/Core/Rewriter.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Signals.h"
 
 using namespace llvm;
+using clang::tooling::Replacements;
 
 static cl::opt<bool> Help("h", cl::desc("Alias for -help"), cl::Hidden);
 
 // Mark all our options with this category, everything else (except for -version
 // and -help) will be hidden.
 static cl::OptionCategory ClangFormatCategory("Clang-format options");
 
 static cl::list<unsigned>
DumpConfig("dump-config",
                         "Can be used with -style option."),
                cl::cat(ClangFormatCategory));
 static cl::opt<unsigned>
     Cursor("cursor",
            cl::desc("The position of the cursor when invoking\n"
                     "clang-format from an editor integration"),
            cl::init(0), cl::cat(ClangFormatCategory));
 
+static cl::opt<bool> SortIncludes("sort-includes",
+                                  cl::desc("Sort touched include lines"),
+                                  cl::cat(ClangFormatCategory));
+
 static cl::list<std::string> FileNames(cl::Positional, cl::desc("[<file> ...]"),
                                        cl::cat(ClangFormatCategory));
 
 namespace clang {
 namespace format {
 
 static FileID createInMemoryFile(StringRef FileName, MemoryBuffer *Source,
                                  SourceManager &Sources, FileManager &Files) {
   const FileEntry *Entry = Files.getVirtualFile(FileName == "-" ? "<stdin>" :
                                                     FileName,
                                                 Source->getBufferSize(), 0);
   Sources.overrideFileContents(Entry, Source, true);
   return Sources.createFileID(Entry, SourceLocation(), SrcMgr::C_User);
 }
 
 // Parses <start line>:<end line> input to a pair of line numbers.
 // Returns true on error.
 static bool parseLineRange(StringRef Input, unsigned &FromLine,
                            unsigned &ToLine) {
   std::pair<StringRef, StringRef> LineRange = Input.split(':');
   return LineRange.first.getAsInteger(0, FromLine) ||
          LineRange.second.getAsInteger(0, ToLine);
 }
 
-static bool fillRanges(SourceManager &Sources, FileID ID,
-                       const MemoryBuffer *Code,
-                       std::vector<CharSourceRange> &Ranges) {
+static bool fillRanges(MemoryBuffer *Code,
+                       std::vector<tooling::Range> &Ranges) {
+  FileManager Files((FileSystemOptions()));
+  DiagnosticsEngine Diagnostics(
+      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
+      new DiagnosticOptions);
+  SourceManager Sources(Diagnostics, Files);
+  FileID ID = createInMemoryFile("-", Code, Sources, Files);
   if (!LineRanges.empty()) {
     if (!Offsets.empty() || !Lengths.empty()) {
       llvm::errs() << "error: cannot use -lines with -offset/-length\n";
       return true;
     }
 
     for (unsigned i = 0, e = LineRanges.size(); i < e; ++i) {
       unsigned FromLine, ToLine;
       if (parseLineRange(LineRanges[i], FromLine, ToLine)) {
         llvm::errs() << "error: invalid <start line>:<end line> pair\n";
         return true;
       }
       if (FromLine > ToLine) {
         llvm::errs() << "error: start line should be less than end line\n";
         return true;
       }
       SourceLocation Start = Sources.translateLineCol(ID, FromLine, 1);
       SourceLocation End = Sources.translateLineCol(ID, ToLine, UINT_MAX);
       if (Start.isInvalid() || End.isInvalid())
         return true;
-      Ranges.push_back(CharSourceRange::getCharRange(Start, End));
+      unsigned Offset = Sources.getFileOffset(Start);
+      unsigned Length = Sources.getFileOffset(End) - Offset;
+      Ranges.push_back(tooling::Range(Offset, Length));
     }
     return false;
   }
 
   if (Offsets.empty())
     Offsets.push_back(0);
   if (Offsets.size() != Lengths.size() &&
       !(Offsets.size() == 1 && Lengths.empty())) {
if (i < Lengths.size()) {
                      << ", offset + length (" << Offsets[i] + Lengths[i]
                      << ") is outside the file.\n";
         return true;
       }
       End = Start.getLocWithOffset(Lengths[i]);
     } else {
       End = Sources.getLocForEndOfFile(ID);
     }
-    Ranges.push_back(CharSourceRange::getCharRange(Start, End));
+    unsigned Offset = Sources.getFileOffset(Start);
+    unsigned Length = Sources.getFileOffset(End) - Offset;
+    Ranges.push_back(tooling::Range(Offset, Length));
   }
   return false;
 }
 
 static void outputReplacementXML(StringRef Text) {
   size_t From = 0;
   size_t Index;
   while ((Index = Text.find_first_of("\n\r", From)) != StringRef::npos) {
     llvm::outs() << Text.substr(From, Index - From);
     switch (Text[Index]) {
     case '\n':
       llvm::outs() << "&#10;";
       break;
     case '\r':
       llvm::outs() << "&#13;";
       break;
     default:
       llvm_unreachable("Unexpected character encountered!");
     }
     From = Index + 1;
   }
   llvm::outs() << Text.substr(From);
 }
 
+static void outputReplacementsXML(const Replacements &Replaces) {
+  for (const auto &R : Replaces) {
+    outs() << "<replacement "
+           << "offset='" << R.getOffset() << "' "
+           << "length='" << R.getLength() << "'>";
+    outputReplacementXML(R.getReplacementText());
+    outs() << "</replacement>\n";
+  }
+}
+
 // Returns true on error.
 static bool format(StringRef FileName) {
-  FileManager Files((FileSystemOptions()));
-  DiagnosticsEngine Diagnostics(
-      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
-      new DiagnosticOptions);
-  SourceManager Sources(Diagnostics, Files);
   ErrorOr<std::unique_ptr<MemoryBuffer>> CodeOrErr =
       MemoryBuffer::getFileOrSTDIN(FileName);
   if (std::error_code EC = CodeOrErr.getError()) {
     llvm::errs() << EC.message() << "\n";
     return true;
   }
   std::unique_ptr<llvm::MemoryBuffer> Code = std::move(CodeOrErr.get());
   if (Code->getBufferSize() == 0)
     return false; // Empty files are formatted correctly.
-  FileID ID = createInMemoryFile(FileName, Code.get(), Sources, Files);
-  std::vector<CharSourceRange> Ranges;
-  if (fillRanges(Sources, ID, Code.get(), Ranges))
+  std::vector<tooling::Range> Ranges;
+  if (fillRanges(Code.get(), Ranges))
     return true;
-
   FormatStyle FormatStyle = getStyle(
       Style, (FileName == "-") ? AssumeFilename : FileName, FallbackStyle);
+  Replacements Replaces;
+  std::string ChangedCode;
+  if (SortIncludes) {
+    Replaces =
+        sortIncludes(FormatStyle, Code->getBuffer(), Ranges, FileName);
+    ChangedCode = tooling::applyAllReplacements(Code->getBuffer(), Replaces);
+    for (const auto &R : Replaces)
+      Ranges.push_back({R.getOffset(), R.getLength()});
+  } else {
+    ChangedCode = Code->getBuffer().str();
+  }
+
   bool IncompleteFormat = false;
-  tooling::Replacements Replaces =
-      reformat(FormatStyle, Sources, ID, Ranges, &IncompleteFormat);
+  Replaces = tooling::mergeReplacements(
+      Replaces,
+      reformat(FormatStyle, ChangedCode, Ranges, FileName, &IncompleteFormat));
   if (OutputXML) {
     llvm::outs() << "<?xml version='1.0'?>\n<replacements "
                     "xml:space='preserve' incomplete_format='"
                  << (IncompleteFormat ? "true" : "false") << "'>\n";
     if (Cursor.getNumOccurrences() != 0)
       llvm::outs() << "<cursor>"
                    << tooling::shiftedCodePosition(Replaces, Cursor)
                    << "</cursor>\n";
 
-    for (tooling::Replacements::const_iterator I = Replaces.begin(),
-                                               E = Replaces.end();
-         I != E; ++I) {
-      llvm::outs() << "<replacement "
-                   << "offset='" << I->getOffset() << "' "
-                   << "length='" << I->getLength() << "'>";
-      outputReplacementXML(I->getReplacementText());
-      llvm::outs() << "</replacement>\n";
-    }
+    outputReplacementsXML(Replaces); 
     llvm::outs() << "</replacements>\n";
   } else {
-    Rewriter Rewrite(Sources, LangOptions());
-    tooling::applyAllReplacements(Replaces, Rewrite);
+    std::string FormattedCode =
+        applyAllReplacements(Code->getBuffer(), Replaces);
     if (Inplace) {
       if (FileName == "-")
         llvm::errs() << "error: cannot use -i when reading from stdin.\n";
-      else if (Rewrite.overwriteChangedFiles())
+      else {
+        std::error_code EC;
+        raw_fd_ostream FileOut(FileName, EC, llvm::sys::fs::F_Text);
+        if (EC) {
+          llvm::errs() << EC.message() << "\n";
           return true;
+        }
+        FileOut << FormattedCode;
+      }
     } else {
       if (Cursor.getNumOccurrences() != 0)
         outs() << "{ \"Cursor\": "
                << tooling::shiftedCodePosition(Replaces, Cursor)
                << ", \"IncompleteFormat\": "
                << (IncompleteFormat ? "true" : "false") << " }\n";
-      Rewrite.getEditBuffer(ID).write(outs());
+      outs() << FormattedCode;
     }
   }
   return false;
 }
 
 }  // namespace format
 }  // namespace clang
 

tools/clang-format/clang-format.py

def main():
   # Avoid flashing an ugly, ugly cmd prompt on Windows when invoking clang-format.
   startupinfo = None
   if sys.platform.startswith('win32'):
     startupinfo = subprocess.STARTUPINFO()
     startupinfo.dwFlags |= subprocess.STARTF_USESHOWWINDOW
     startupinfo.wShowWindow = subprocess.SW_HIDE
 
   # Call formatter.
-  command = [binary, '-style', style, '-cursor', str(cursor)]
+  command = [binary, '-style', style, '-cursor', str(cursor), '-sort-includes']
   if lines != 'all':
     command.extend(['-lines', lines])
   if fallback_style:
     command.extend(['-fallback-style', fallback_style])
   if vim.current.buffer.name:
     command.extend(['-assume-filename', vim.current.buffer.name])
   p = subprocess.Popen(command,
                        stdout=subprocess.PIPE, stderr=subprocess.PIPE,

unittests/Format/CMakeLists.txt

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

unittests/Format/SortIncludesTest.cpp

+//===- unittest/Format/SortIncludesTest.cpp - Include sort unit tests -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FormatTestUtils.h"
+#include "clang/Format/Format.h"
+#include "llvm/Support/Debug.h"
+#include "gtest/gtest.h"
+
+#define DEBUG_TYPE "format-test"
+
+namespace clang {
+namespace format {
+namespace {
+
+class SortIncludesTest : public ::testing::Test {
+protected:
+  std::string sort(llvm::StringRef Code) {
+    std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
+    std::string Sorted = applyAllReplacements(
+        Code, sortIncludes(getLLVMStyle(), Code, Ranges, "input.cpp"));
+    return applyAllReplacements(
+        Sorted, reformat(getLLVMStyle(), Sorted, Ranges, "input.cpp"));
+  }
+};
+
+TEST_F(SortIncludesTest, BasicSorting) {
+  EXPECT_EQ("#include \"a.h\"\n"
+            "#include \"b.h\"\n"
+            "#include \"c.h\"\n",
+            sort("#include \"a.h\"\n"
+                 "#include \"c.h\"\n"
+                 "#include \"b.h\"\n"));
+}
+
+TEST_F(SortIncludesTest, FixTrailingComments) {
+  EXPECT_EQ("#include \"a.h\"  // comment\n"
+            "#include \"bb.h\" // comment\n"
+            "#include \"ccc.h\"\n",
+            sort("#include \"a.h\" // comment\n"
+                 "#include \"ccc.h\"\n"
+                 "#include \"bb.h\" // comment\n"));
+}
+
+TEST_F(SortIncludesTest, LeadingWhitespace) {
+  EXPECT_EQ("#include \"a.h\"\n"
+            "#include \"b.h\"\n"
+            "#include \"c.h\"\n",
+            sort(" #include \"a.h\"\n"
+                 "  #include \"c.h\"\n"
+                 "   #include \"b.h\"\n"));
+  EXPECT_EQ("#include \"a.h\"\n"
+            "#include \"b.h\"\n"
+            "#include \"c.h\"\n",
+            sort("# include \"a.h\"\n"
+                 "#  include \"c.h\"\n"
+                 "#   include \"b.h\"\n"));
+}
+
+TEST_F(SortIncludesTest, GreaterInComment) {
+  EXPECT_EQ("#include \"a.h\"\n"
+            "#include \"b.h\" // >\n"
+            "#include \"c.h\"\n",
+            sort("#include \"a.h\"\n"
+                 "#include \"c.h\"\n"
+                 "#include \"b.h\" // >\n"));
+}
+
+TEST_F(SortIncludesTest, SortsLocallyInEachBlock) {
+  EXPECT_EQ("#include \"a.h\"\n"
+            "#include \"c.h\"\n"
+            "\n"
+            "#include \"b.h\"\n",
+            sort("#include \"c.h\"\n"
+                 "#include \"a.h\"\n"
+                 "\n"
+                 "#include \"b.h\"\n"));
+}
+
+TEST_F(SortIncludesTest, HandlesAngledIncludesAsSeparateBlocks) {
+  EXPECT_EQ("#include <b.h>\n"
+            "#include <d.h>\n"
+            "#include \"a.h\"\n"
+            "#include \"c.h\"\n",
+            sort("#include <d.h>\n"
+                 "#include <b.h>\n"
+                 "#include \"c.h\"\n"
+                 "#include \"a.h\"\n"));
+}
+
+TEST_F(SortIncludesTest, HandlesMultilineIncludes) {
+  EXPECT_EQ("#include \"a.h\"\n"
+            "#include \"b.h\"\n"
+            "#include \"c.h\"\n",
+            sort("#include \"a.h\"\n"
+                 "#include \\\n"
+                 "\"c.h\"\n"
+                 "#include \"b.h\"\n"));
+}
+
+} // end namespace
+} // end namespace format
+} // end namespace clang

unittests/Tooling/RefactoringTest.cpp

TEST(DeduplicateTest, detectsConflicts) {
     ASSERT_EQ(2u, Conflicts.size());
     ASSERT_EQ(1u, Conflicts[0].getOffset());
     ASSERT_EQ(4u, Conflicts[0].getLength());
     ASSERT_EQ(6u, Conflicts[1].getOffset());
     ASSERT_EQ(2u, Conflicts[1].getLength());
   }
 }
 
+class MergeReplacementsTest : public ::testing::Test {
+protected:
+  void mergeAndTestRewrite(StringRef Code, StringRef Intermediate,
+                           StringRef Result, const Replacements &First,
+                           const Replacements &Second) {
+    // These are mainly to verify the test itself and make it easier to read.
+    std::string AfterFirst = applyAllReplacements(Code, First);
+    std::string InSequenceRewrite = applyAllReplacements(AfterFirst, Second);
+    EXPECT_EQ(Intermediate, AfterFirst);
+    EXPECT_EQ(Result, InSequenceRewrite);
+
+    tooling::Replacements Merged = mergeReplacements(First, Second);
+    std::string MergedRewrite = applyAllReplacements(Code, Merged);
+    EXPECT_EQ(InSequenceRewrite, MergedRewrite);
+    if (InSequenceRewrite != MergedRewrite)
+      for (tooling::Replacement M : Merged)
+        llvm::errs() << M.getOffset() << " " << M.getLength() << " "
+                     << M.getReplacementText() << "\n";
+  }
+  void mergeAndTestRewrite(StringRef Code, const Replacements &First,
+                           const Replacements &Second) {
+    std::string InSequenceRewrite =
+        applyAllReplacements(applyAllReplacements(Code, First), Second);
+    tooling::Replacements Merged = mergeReplacements(First, Second);
+    std::string MergedRewrite = applyAllReplacements(Code, Merged);
+    EXPECT_EQ(InSequenceRewrite, MergedRewrite);
+    if (InSequenceRewrite != MergedRewrite)
+      for (tooling::Replacement M : Merged)
+        llvm::errs() << M.getOffset() << " " << M.getLength() << " "
+                     << M.getReplacementText() << "\n";
+  }
+};
+
+TEST_F(MergeReplacementsTest, Offsets) {
+  mergeAndTestRewrite("aaa", "aabab", "cacabab",
+                      {{"", 2, 0, "b"}, {"", 3, 0, "b"}},
+                      {{"", 0, 0, "c"}, {"", 1, 0, "c"}});
+  mergeAndTestRewrite("aaa", "babaa", "babacac",
+                      {{"", 0, 0, "b"}, {"", 1, 0, "b"}},
+                      {{"", 4, 0, "c"}, {"", 5, 0, "c"}});
+  mergeAndTestRewrite("aaaa", "aaa", "aac", {{"", 1, 1, ""}},
+                      {{"", 2, 1, "c"}});
+
+  mergeAndTestRewrite("aa", "bbabba", "bbabcba",
+                      {{"", 0, 0, "bb"}, {"", 1, 0, "bb"}}, {{"", 4, 0, "c"}});
+}
+
+TEST_F(MergeReplacementsTest, Concatenations) {
+  // Basic concatenations. It is important to merge these into a single
+  // replacement to ensure the correct order.
+  EXPECT_EQ((Replacements{{"", 0, 0, "ab"}}),
+            mergeReplacements({{"", 0, 0, "a"}}, {{"", 1, 0, "b"}}));
+  EXPECT_EQ((Replacements{{"", 0, 0, "ba"}}),
+            mergeReplacements({{"", 0, 0, "a"}}, {{"", 0, 0, "b"}}));
+  mergeAndTestRewrite("", "a", "ab", {{"", 0, 0, "a"}}, {{"", 1, 0, "b"}});
+  mergeAndTestRewrite("", "a", "ba", {{"", 0, 0, "a"}}, {{"", 0, 0, "b"}});
+}
+
+TEST_F(MergeReplacementsTest, NotChangingLengths) {
+  mergeAndTestRewrite("aaaa", "abba", "acca", {{"", 1, 2, "bb"}},
+                      {{"", 1, 2, "cc"}});
+  mergeAndTestRewrite("aaaa", "abba", "abcc", {{"", 1, 2, "bb"}},
+                      {{"", 2, 2, "cc"}});
+  mergeAndTestRewrite("aaaa", "abba", "ccba", {{"", 1, 2, "bb"}},
+                      {{"", 0, 2, "cc"}});
+  mergeAndTestRewrite("aaaaaa", "abbdda", "abccda",
+                      {{"", 1, 2, "bb"}, {"", 3, 2, "dd"}}, {{"", 2, 2, "cc"}});
+}
+
+TEST_F(MergeReplacementsTest, OverlappingRanges) {
+  mergeAndTestRewrite("aaa", "bbd", "bcbcd",
+                      {{"", 0, 1, "bb"}, {"", 1, 2, "d"}},
+                      {{"", 1, 0, "c"}, {"", 2, 0, "c"}});
+
+  mergeAndTestRewrite("aaaa", "aabbaa", "acccca", {{"", 2, 0, "bb"}},
+                      {{"", 1, 4, "cccc"}});
+  mergeAndTestRewrite("aaaa", "aababa", "acccca",
+                      {{"", 2, 0, "b"}, {"", 3, 0, "b"}}, {{"", 1, 4, "cccc"}});
+  mergeAndTestRewrite("aaaaaa", "abbbba", "abba", {{"", 1, 4, "bbbb"}},
+                      {{"", 2, 2, ""}});
+  mergeAndTestRewrite("aaaa", "aa", "cc", {{"", 1, 1, ""}, {"", 2, 1, ""}},
+                      {{"", 0, 2, "cc"}});
+  mergeAndTestRewrite("aa", "abbba", "abcbcba", {{"", 1, 0, "bbb"}},
+                      {{"", 2, 0, "c"}, {"", 3, 0, "c"}});
+
+  mergeAndTestRewrite("aaa", "abbab", "ccdd",
+                      {{"", 0, 1, ""}, {"", 2, 0, "bb"}, {"", 3, 0, "b"}},
+                      {{"", 0, 2, "cc"}, {"", 2, 3, "dd"}});
+  mergeAndTestRewrite("aa", "babbab", "ccdd",
+                      {{"", 0, 0, "b"}, {"", 1, 0, "bb"}, {"", 2, 0, "b"}},
+                      {{"", 0, 3, "cc"}, {"", 3, 3, "dd"}});
+}
+
 } // end namespace tooling
 } // end namespace clang