gn format: Have format sort sources

tools/gn/parse_tree.cc

Index: tools/gn/parse_tree.cc
diff --git a/tools/gn/parse_tree.cc b/tools/gn/parse_tree.cc
index 74f493b601741f7a36e970674118b79635a4ca55..ecfd5d4831c040ee9faffde147f0c80060d0f2ae 100644
--- a/tools/gn/parse_tree.cc
+++ b/tools/gn/parse_tree.cc
@@ -194,6 +194,12 @@ Value AccessorNode::ExecuteScopeAccess(Scope* scope, Err* err) const {
   return *result;
 }
 
+void AccessorNode::SetNewLocation(int line_number) {
+  Location old = base_.location();
+  base_.set_location(
+      Location(old.file(), line_number, old.char_offset(), old.byte()));
+}
+
 // BinaryOpNode ---------------------------------------------------------------
 
 BinaryOpNode::BinaryOpNode() {
@@ -436,6 +442,12 @@ void IdentifierNode::Print(std::ostream& out, int indent) const {
   PrintComments(out, indent);
 }
 
+void IdentifierNode::SetNewLocation(int line_number) {
+  Location old = value_.location();
+  value_.set_location(
+      Location(old.file(), line_number, old.char_offset(), old.byte()));
+}
+
 // ListNode -------------------------------------------------------------------
 
 ListNode::ListNode() : prefer_multiline_(false) {
@@ -490,6 +502,106 @@ void ListNode::Print(std::ostream& out, int indent) const {
     end_->Print(out, indent + 1);
 }
 
+using Range = std::pair<std::vector<const ParseNode*>::iterator,
+                        std::vector<const ParseNode*>::iterator>;
+
+bool IsSeparatorComment(const ParseNode* node, const ParseNode* prev) {

[brettw, 2015/02/27 22:27:27]

Seems like these standalone functions should be in an anon namespace at the top.

[scottmg, 2015/02/27 23:17:44]

Done.

+  // If it's a block comment, or has an attached comment with a blank line
+  // before it, then we break the range at this point.
+  return node->AsBlockComment() != nullptr ||
+         (prev && node->comments() && !node->comments()->before().empty() &&
+          (node->GetRange().begin().line_number() >
+           prev->GetRange().end().line_number() +
+               static_cast<int>(node->comments()->before().size() + 1)));
+}
+
+std::vector<Range> GetSortRanges(std::vector<const ParseNode*>& contents) {

[brettw, 2015/02/27 22:27:27]

Can you provide a function level comment of what this does?

[scottmg, 2015/02/27 23:17:44]

Done.

+  std::vector<Range> ranges;
+  auto begin = contents.begin();
+  const ParseNode* prev = nullptr;
+  for (auto it = begin; it != contents.end(); prev = *(it++)) {

[brettw, 2015/02/27 22:27:27]

This is pretty hard to wrap one's head around. Would this be a case where just
using ints would make it nicer? If it doesn't it's OK to keep as-is.

[scottmg, 2015/02/27 23:17:44]

Switched to size_ts. Not sure it helps, I think it's just badly written. I
fiddled with it for a too long to get it to handle all the cases in the test,
but it's very confusing.

... While adding an explanatory comment to try to rationalize the complexity
here I realized it could easily have a test. So moved this function to being a
member, and added a test for this range extraction which matches the comment.
(Using ints helped with the test.)

+    if (IsSeparatorComment(*it, prev)) {
+      if (it > begin) {
+        ranges.push_back(std::make_pair(begin, it));
+        if (!(*it)->AsBlockComment())
+          begin = it;
+        else
+          begin = it + 1;
+      } else {
+        begin = it + 1;
+      }
+      if (it == contents.end())

[brettw, 2015/02/27 22:27:27]

This could also go away if you used ints

[scottmg, 2015/02/27 23:17:44]

Might not have been necessary either way I think. (I previously had a nested
loop in here, but it wasn't necessary). Anyway, done.

+        break;
+    }
+  }
+  if (begin != contents.end())
+    ranges.push_back(std::make_pair(begin, contents.end()));
+  return ranges;
+}
+
+base::StringPiece GetStringRepresentation(const ParseNode* node) {
+  DCHECK(node->AsLiteral() || node->AsIdentifier() || node->AsAccessor());
+  if (node->AsLiteral())
+    return node->AsLiteral()->value().value();
+  else if (node->AsIdentifier())
+    return node->AsIdentifier()->value().value();
+  else if (node->AsAccessor())
+    return node->AsAccessor()->base().value();
+  return base::StringPiece();
+}
+
+void ListNode::SortAsStringsList() {
+  // Sorts alphabetically. Partitions first on BlockCommentNodes and sorts each
+  // partition separately.
+  std::vector<Range> ranges = GetSortRanges(contents_);
+  for (auto range : ranges) {

[brettw, 2015/02/27 22:27:27]

You couldn't do for (auto range : GetSortRanges(contents_))? Did you need a copy
or something?

[scottmg, 2015/02/27 23:17:44]

Done.

+    // Save the original line number so that we can re-assign ranges. We assume
+    // they're contiguous lines because GetSortRanges() does so above. We need
+    // to re-assign these line numbers primiarily because `gn format` uses them
+    // to determine whether two nodes were initially separated by a blank line
+    // or not.
+    int start_line = (*range.first)->GetRange().begin().line_number();
+    const ParseNode* original_first = *range.first;
+    std::sort(range.first, range.second,
+              [](const ParseNode* a, const ParseNode* b) {
+                base::StringPiece astr = GetStringRepresentation(a);
+                base::StringPiece bstr = GetStringRepresentation(b);
+                return astr < bstr;
+              });
+    // If the beginning of the range had before comments, and the first node
+    // moved during the sort, then move its comments to the new head of the
+    // range.
+    if (original_first->comments() && *range.first != original_first) {
+      for (const auto& hc : original_first->comments()->before()) {
+        const_cast<ParseNode*>(*range.first)
+            ->comments_mutable()
+            ->append_before(hc);
+      }
+      const_cast<ParseNode*>(original_first)
+          ->comments_mutable()
+          ->clear_before();
+    }
+    const ParseNode* prev = nullptr;
+    for (auto it = range.first; it != range.second; ++it) {
+      const ParseNode* node = *it;
+      DCHECK(node->AsLiteral() || node->AsIdentifier() || node->AsAccessor());
+      int line_number =
+          prev ? prev->GetRange().end().line_number() + 1 : start_line;
+      if (node->AsLiteral()) {
+        const_cast<LiteralNode*>(node->AsLiteral())
+            ->SetNewLocation(line_number);
+      } else if (node->AsIdentifier()) {
+        const_cast<IdentifierNode*>(node->AsIdentifier())
+            ->SetNewLocation(line_number);
+      } else if (node->AsAccessor()) {
+        const_cast<AccessorNode*>(node->AsAccessor())
+            ->SetNewLocation(line_number);
+      }
+      prev = node;
+    }
+  }
+}
+
 // LiteralNode -----------------------------------------------------------------
 
 LiteralNode::LiteralNode() {
@@ -544,6 +656,12 @@ void LiteralNode::Print(std::ostream& out, int indent) const {
   PrintComments(out, indent);
 }
 
+void LiteralNode::SetNewLocation(int line_number) {
+  Location old = value_.location();
+  value_.set_location(
+      Location(old.file(), line_number, old.char_offset(), old.byte()));
+}
+
 // UnaryOpNode ----------------------------------------------------------------
 
 UnaryOpNode::UnaryOpNode() {
@@ -608,7 +726,6 @@ void BlockCommentNode::Print(std::ostream& out, int indent) const {
   PrintComments(out, indent);
 }
 
-
 // EndNode ---------------------------------------------------------------------
 
 EndNode::EndNode(const Token& token) : value_(token) {