clang-format: Add initial #include sorting capabilities.

To implement this nicely, add a function that merges two sets of
replacements that are meant to be done in sequence. This functionality
will also be useful for other applications, e.g. formatting the result
of clang-tidy fixes.

llvm-svn: 248367

3 files changed, 235 insertions, 3 deletions

diff --git a/clang/lib/Format/Format.cpp b/clang/lib/Format/Format.cpp
index ae313c57dce..15aa50224bf 100644
--- a/clang/lib/Format/Format.cpp
+++ b/clang/lib/Format/Format.cpp
@@ -310,8 +310,8 @@ template <> struct DocumentListTraits<std::vector<FormatStyle>> {
     return Seq[Index];
   }
 };
-}
-}
+} // namespace yaml
+} // namespace llvm
 
 namespace clang {
 namespace format {
@@ -1571,8 +1571,108 @@ private:
   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,
diff --git a/clang/lib/Format/FormatToken.cpp b/clang/lib/Format/FormatToken.cpp
index 358a9a48ec8..b293cf25c35 100644
--- a/clang/lib/Format/FormatToken.cpp
+++ b/clang/lib/Format/FormatToken.cpp
@@ -13,8 +13,8 @@
 ///
 //===----------------------------------------------------------------------===//
 
-#include "FormatToken.h"
 #include "ContinuationIndenter.h"
+#include "FormatToken.h"
 #include "clang/Format/Format.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Debug.h"
diff --git a/clang/lib/Tooling/Core/Replacement.cpp b/clang/lib/Tooling/Core/Replacement.cpp
index 6d37a49db38..8de362fae8e 100644
--- a/clang/lib/Tooling/Core/Replacement.cpp
+++ b/clang/lib/Tooling/Core/Replacement.cpp
@@ -292,6 +292,138 @@ std::string applyAllReplacements(StringRef Code, const Replacements &Replaces) {
   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