Sort "deps" and "public_deps" when running the "gn format" command.

tools/gn/parse_tree.cc

 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "tools/gn/parse_tree.h"
 
 #include <string>
+#include <tuple>
 
 #include "base/stl_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "tools/gn/functions.h"
 #include "tools/gn/operators.h"
 #include "tools/gn/scope.h"
 #include "tools/gn/string_utils.h"
 
 namespace {
 
+std::tuple<base::StringPiece, base::StringPiece> SplitAtFirst(
+    base::StringPiece str,
+    char c) {
+  if (!str.starts_with("\"") || !str.ends_with("\""))
+    return std::make_tuple(str, base::StringPiece());
+
+  str = str.substr(1, str.length() - 2);
+  size_t index_of_first = str.find(c);
+  return std::make_tuple(str.substr(0, index_of_first),
+                         index_of_first != base::StringPiece::npos
+                             ? str.substr(index_of_first + 1)
+                             : base::StringPiece());
+}
+
 std::string IndentFor(int value) {
   return std::string(value, ' ');
 }
 
 bool IsSortRangeSeparator(const ParseNode* node, const ParseNode* prev) {
   // 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() >
@@ skipping 467 matching lines @@
 void ListNode::Print(std::ostream& out, int indent) const {
   out << IndentFor(indent) << "LIST" << (prefer_multiline_ ? " multiline" : "")
       << "\n";
   PrintComments(out, indent);
   for (const auto& cur : contents_)
     cur->Print(out, indent + 1);
   if (end_ && end_->comments())
     end_->Print(out, indent + 1);
 }
 
-void ListNode::SortAsStringsList() {
-  // Sorts alphabetically. Partitions first on BlockCommentNodes and sorts each
-  // partition separately.
+template <typename Comparator>
+void ListNode::SortList(Comparator comparator) {
+  // Partitions first on BlockCommentNodes and sorts each partition separately.
   for (auto sr : GetSortRanges()) {
+    bool skip = false;
+    for (size_t i = sr.begin; i != sr.end; ++i) {
+      // Bails out if any of the nodes are unsupported.
+      const ParseNode* node = contents_[i];
+      if (!node->AsLiteral() && !node->AsIdentifier() && !node->AsAccessor()) {
+        skip = true;
+        continue;
+      }
+    }
+    if (skip)
+      continue;
     // 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 = contents_[sr.begin]->GetRange().begin().line_number();
     const ParseNode* original_first = contents_[sr.begin];
     std::sort(contents_.begin() + sr.begin, contents_.begin() + sr.end,
-              [](const ParseNode* a, const ParseNode* b) {
-                base::StringPiece astr = GetStringRepresentation(a);
-                base::StringPiece bstr = GetStringRepresentation(b);
-                return astr < bstr;
-              });
+              comparator);
     // 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() && contents_[sr.begin] != original_first) {
       for (const auto& hc : original_first->comments()->before()) {
         const_cast<ParseNode*>(contents_[sr.begin])
             ->comments_mutable()
             ->append_before(hc);
       }
       const_cast<ParseNode*>(original_first)
@@ skipping 14 matching lines @@
             ->SetNewLocation(line_number);
       } else if (node->AsAccessor()) {
         const_cast<AccessorNode*>(node->AsAccessor())
             ->SetNewLocation(line_number);
       }
       prev = node;
     }
   }
 }
 
+void ListNode::SortAsStringsList() {
+  // Sorts alphabetically.
+  SortList([](const ParseNode* a, const ParseNode* b) {
+    base::StringPiece astr = GetStringRepresentation(a);
+    base::StringPiece bstr = GetStringRepresentation(b);
+    return astr < bstr;
+  });
+}
+
+void ListNode::SortAsDepsList() {
+  // Sorts first relative targets, then absolute, each group is sorted
+  // alphabetically.
+  SortList([](const ParseNode* a, const ParseNode* b) {
+    base::StringPiece astr = GetStringRepresentation(a);
+    base::StringPiece bstr = GetStringRepresentation(b);
+    return SplitAtFirst(astr, ':') < SplitAtFirst(bstr, ':');
+  });
+}
+
 // Breaks the ParseNodes of |contents| up by ranges that should be separately
 // sorted. In particular, we break at a block comment, or an item that has an
 // attached "before" comment and is separated by a blank line from the item
 // before it. The assumption is that both of these indicate a separate 'section'
 // of a sources block across which items should not be inter-sorted.
 std::vector<ListNode::SortRange> ListNode::GetSortRanges() const {
   std::vector<SortRange> ranges;
   const ParseNode* prev = nullptr;
   size_t begin = 0;
   for (size_t i = begin; i < contents_.size(); prev = contents_[i++]) {
@@ skipping 200 matching lines @@
 
 Err EndNode::MakeErrorDescribing(const std::string& msg,
                                         const std::string& help) const {
   return Err(value_, msg, help);
 }
 
 void EndNode::Print(std::ostream& out, int indent) const {
   out << IndentFor(indent) << "END(" << value_.value() << ")\n";
   PrintComments(out, indent);
 }